skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, May 23 until 2:00 AM ET on Friday, May 24 due to maintenance. We apologize for the inconvenience.

Search for: All records

Award ID contains: 1717842

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. null (Ed.)
  2. null (Ed.)
    Abstract—We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (“graceful”) input-output BER curves (as opposed to threshold-like curves typical for long error-correcting codes). This paper restricts attention to binary erasure channels (BEC) and contains two contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are non-linear sparse-graph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained input-output curves provably improve upon performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications where LDGMs have been used traditionally. Second, we establish several two-point converse bounds that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specific to subclasses of codes (linear systematic and non-linear systematic) and outperform similar bounds implied by the area theorem for the EXIT function 
    more » « less
  3. 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 Eb/N0 (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. 
    more » « less
  4. We consider the Gaussian multiple-access channel with two critical departures from the classical asymptotics: a) number of users proportional to blocklength and b) each user sends a fixed number of data bits. We provide improved bounds on the tradeoff between the user density and the energy-per-bit. Interestingly, in this information-theoretic problem we rely on Gordon’s lemma from Gaussian process theory. From the engineering standpoint, we discover a surprising new effect: good coded-access schemes can achieve perfect multi-user interference cancellation at low user density. In addition, by a similar method we analyze the limits of false-discovery in binary sparse regression problem in the asymptotic regime of number of measurements going to infinity at fixed ratios with problem dimension, sparsity and noise level. Our rigorous bound matches the formal replica-method prediction for some range of parameters with imperceptible numerical precision. 
    more » « less