Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability.
more »
« less
Graceful degradation over the BEC via non-linear codes
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
- Award ID(s):
- 1717842
- NSF-PAR ID:
- 10273761
- Date Published:
- Journal Name:
- IEEE International Symposium on Information Theory
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Reed–Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly- symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.more » « less
-
null (Ed.)In 2018, Renes [IEEE Trans. Inf. Theory, vol. 64, no. 1, pp. 577-592 (2018)] developed a general theory of channel duality for classical-input quantum-output channels. His result shows that a number of well-known duality results for linear codes on the binary erasure channel can be extended to general classical channels at the expense of using dual problems which are intrinsically quantum mechanical. One special case of this duality is a connection between coding for error correction on the quantum pure-state channel (PSC) and coding for wiretap secrecy on the classical binary symmetric channel (BSC). Similarly, coding for error correction on the BSC is related to wire-tap secrecy on the PSC. While this result has important implications for classical coding, the machinery behind the general duality result is rather challenging for researchers without a strong background in quantum information theory. In this work, we leverage prior results for linear codes on PSCs to give an alternate derivation of the aforementioned special case by computing closed-form expressions for the performance metrics. The noted prior results include the optimality of square-root measurement for linear codes on the PSC and the Fourier duality of linear codes.more » « less
-
With increasing needs of fast and reliable commu- nication between devices, wireless communication techniques are rapidly evolving to meet such needs. Multiple input and output (MIMO) systems are one of the key techniques that utilize multiple antennas for high-throughput and reliable communication. However, increasing the number of antennas in communication also adds to the complexity of channel esti- mation, which is essential to accurately decode the transmitted data. Therefore, development of accurate and efficient channel estimation methods is necessary. We report the performance of machine learning-based channel estimation approaches to enhance channel estimation performance in high-noise envi- ronments. More specifically, bit error rate (BER) performance of 2 × 2 and 4 × 4 MIMO communication systems with space- time block coding model (STBC) and two neural network-based channel estimation algorithms is analyzed. Most significantly, the results demonstrate that a generalized regression neural network (GRNN) model matches BER results of a known-channel communication for 4 × 4 MIMO with 8-bit pilots, when trained in a specific signal to noise ratio (SNR) regime. Moreover, up to 9dB improvement in signal-to-noise ratio (SNR) for a target BER is observed, compared to least square (LS) channel estimation, especially when the model is trained in the low SNR regime. A deep artificial neural network (Deep ANN) model shows worse BER performance compared to LS in all tested environments. These preliminary results present an opportunity for achieving better performance in channel estimation through GRNN and highlight further research topics for deployment in the wild.more » « less
-
We consider the storage–retrieval rate trade-off in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate trade-off can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ISIT44484.2020.9174501
