Exploiting Sparsity for Uncoordinated Grant-Free Random Access
Final Report Abstract
The goal of this project was to investigate the use of sparsity for uncoordinated communication scenarios. With a specific focus on sparse regression codes (SPARCs), which encode information by superposing a comparably small number of columns from a codebook. Unsourced random access is a recent paradigm for realising uncoordinated communication, where each device uses the exact same encoder for transmitting data. The identity of the device is not used in the encoding or decoding process. Some of the most efficient solutions for the unsourced random access problem consist of a combination of spreading, interleaving, and the use of strong short block-length point-to-point codes. The receiver leverages the spreading and interleaving patterns of the users to perform multi-user detection, followed by single-user decoding and interference cancelation. The choice of the single-user code has been predominantly based on empirical trial-and-error. The was no attempt at designing codes that are specifically suited for the described transmitter/receiver design. During this project, me and collaborators made a couple of important contributions to the development of unsourced communication. One of them was the design of low-density parity check (LDPC) codes that are particularly well suited for unsourced communication in the sense that they achieve the fundamental limits on a simplified channel model. Specifically, we leveraged the theoretical understanding of LDPC codes to compute degree distributions that are optimised for belief propagation decoding on the joint sparse graph. This presents a step towards unsourced multiple-access codes that are both rate efficient and have a low decoding complexity. Another particularly interesting class of codes for unsourced communication is a multi-user version of SPARCs. This class of codes relies on a coupling of message fragments through an outer code. In fact, the set of symbols recovered by the inner decoder resembles the output of a so called A-channel. The A-channel is a discrete memoryless multiple-access over q-ary inputs, and the problem of recovering the sent messages is equivalent to decoding on the A-channel. In the course of this project, we analysed the achievable rates on the A-channel by developing new random coding achievability bounds. These bounds revealed that all known coding schemes for the A- channel were systematically sub-optimal because they used a decoder whose achievable rates were bounded away from capacity by non-zero gap at any given number of K and q. We have shown that joint decoding, taking into account all combinations of messages, is necessary to close this gap, which none of the known coding schemes attempted. Unfortunately, naive joint decoding would result in an exponential decoding complexity. Nonetheless, we have shown that the use of linear programming relaxations allows to approximate joint decoding with a low-complexity decoder.
Publications
-
Finite-Blocklength Results for the A-channel: Applications to Unsourced Random Access and Group Testing. 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 1-8. IEEE.
Lancho, Alejandro; Fengler, Alexander & Polyanskiy, Yury
-
Sparse Graph Codes for the 2-User Unsourced MAC. 2022 56th Asilomar Conference on Signals, Systems, and Computers, 682-686. IEEE.
Fengler, Alexander; Liva, Gianluigi & Polyanskiy, Yury
-
Coded Orthogonal Modulation for the Multi-Antenna MAC. 2023 12th International Symposium on Topics in Coding (ISTC), 1-5. IEEE.
Fengler, Alexander; Lancho, Alejandro & Polyanskiy, Yury
-
On the Advantages of Asynchrony in the Unsourced MAC. 2023 IEEE International Symposium on Information Theory (ISIT), 2523-2528. IEEE.
Fengler, Alexander; Lancho, Alejandro; Narayanan, Krishna & Polyanskiy, Yury
