A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert-Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets.
8 June 2020 in IEEE Transactions on Communications
We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free, and uncoordinated uplink for densely packed wireless nodes. Specifically, we study random-access codes, previously introduced for the AWGN MAC in [2], in the practically more relevant case of Rayleigh fading, when channel gains are unknown to the decoder. We propose a random coding achievability bound, which we analyze both non-asymptotically and asymptotically. As a candidate practical solution, we propose an explicit iterative coding scheme. The performance of such a solution is surprisingly close to the finite blocklength bounds. Our main findings are twofold. First, just like in the AWGN MAC, we see that jointly decoding a large number of users leads to a surprising phase transition effect, where, at spectral efficiencies below a critical threshold, a perfect multi-user interference cancellation is possible. Second, while the presence of Rayleigh fading significantly increases the minimal required energy-per-bit, the inherent randomization introduced by the channel makes it much easier to attain the optimal performance via iterative schemes. We hope that a principled definition of the random-access model, together with their information-theoretic analysis, will open the road towards unified benchmarking and performance comparison of various random-access solutions for the 5G/6G.
Massive machine-type communications (mMTC) is one of the key application scenarios for future 5G networks. In the literature, this problem is known as unsourced random access. We propose a polar code based scheme for the unsourced random access Gaussian channel. This scheme is based on T-fold irregular repetition slotted ALOHA (IRSA). We use polar codes as slot codes and investigate their practical performance in T-user MAC. We compare two possible decoding techniques: joint successive cancellation algorithm and joint iterative algorithm. In order to optimize the codes (choose frozen bits), we propose a specialized and efficient design algorithm. Finally, we investigate the performance of the resulting scheme by means of simulations and conclude that replacing of LDPC codes with polar codes in IRSA scheme leads to a significant performance gain.
We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free and uncoordinated uplink for densely packed wireless nodes. Specifically, we extend the concept of random-access code introduced at ISIT’2017 by one of the authors to the practically more relevant case of the AWGN multiple-access channel (MAC) subject to Rayleigh fading, unknown to the decoder. We derive bounds on the fundamental limits of random-access coding and propose an alternating belief-propagation scheme as a candidate practical solution. The latter’s performance was found to be surprisingly close to the information-theoretic bounds. It is curious, thus, that while fading significantly increases the minimal required energy-per-bit E b /N 0 (from about 0-2 dB to about 8-11 dB), it appears that it is much easier to attain the optimal performance over the fading channel with a practical scheme by leveraging the inherent randomization introduced by the channel. Finally, we mention that while a number of candidate solutions (MUSA, SCMA, RSMA, etc.) are being discussed for the 5G, the information-theoretic analysis and benchmarking has not been attempted before (in part due to lack of common random-access model). Our work may be seen as a step towards unifying performance comparisons of these methods.
We address the problem of uncoordinated massive random-access in the Gaussian multiple access channel (MAC). The performance of low-complexity T-fold irregular repetition slotted ALOHA (IRSA) scheme is investigated and achievability bounds are derived. The main difference of this scheme in comparison to IRSA is as follows: any collisions of order up to T can be resolved with some probability of error introduced by noise. In order to optimize the parameters of the scheme we combine the density evolution method (DE) proposed by G. Liva and a finite length random coding bound for the Gaussian MAC proposed by Y. Polyanskiy. As energy efficiency is of critical importance for massive machine-type communication (mMTC), then our main goal is to minimize the energy-per-bit required to achieve the target packet loss ratio (PLR). We consider two scenarios: (a) the number of active users is fixed; (b) the number of active users is a Poisson random variable.
25 October 2022 in IEEE Transactions on Communications
We consider a coded compressed sensing approach for the unsourced random access and replace the outer tree code proposed by Amalladinne et al. (2020) with the list recoverable code capable of correcting t errors. A finite-length random coding bound for such codes is derived. The numerical experiments in the single-antenna quasi-static Rayleigh fading channel show that transition to list recoverable codes correcting t errors improves the performance of the coded compressed sensing scheme by 7-10 dB compared to the tree code-based scheme. We propose two practical constructions of outer codes. The first is a modification of the tree code called t -tree code. It utilizes the same code structure, and a key difference is a decoder capable of correcting up to t errors. The second is based on the Reed–Solomon codes and Guruswami–Sudan list decoding algorithm. The first scheme provides energy efficiency very close to the random coding bound when the decoding complexity (number of decoding paths) is unbounded. But when we restrict the number of decoding paths with a practical value, the second scheme outperforms the first one. Both schemes improve the performance of a tree code-based scheme for a small and moderate number of active users.