This paper is concerned with a new list decoding algorithm called list coset decoding. With the recently proposed linear coding framework, we first give a theorem for the optimality of the list coset decoding. Different from the commonly accepted list decoding, which attempts to find a list ofLmost probable candidate codewords, we form a list (with a constrained size) that may not contain all theLmost reliable candidate codewords but still contains the transmitted (uncoded) vector with high probability. The list coset decoding divides the space into subspaces so that the transmitted vector can be reached with high probability. We then apply the list coset decoding to the ordered statistics decoding with local constraints (LC-OSD) to implement the parallel decoding for linear block codes. With the dynamic approximate ideal (DAI) early stopping criterion, the newly proposed algorithm can reduce the decoding delay, compared with the serial implementation. To numerically evaluate the decoding delay, we propose to use the saddlepoint approximation, which is a high-accuracy counting method. Simulation results show that the estimation matches well with the simulation results in high signal-to-noise ratio (SNR) region. To further reduce the decoding delay, we propose several offline test error pattern (TEP) generation methods. Then, the parallel decoding can exploit the pre-stored TEPs for each coset list. Simulation results demonstrate that the parallel list coset decoding in LC-OSD, utilizing offline TEP generation based on empirical reliability, has minimal performance degradation. The simulation results also show that, on average, one or two trials in parallel are sufficient for near maximum-likelihood (ML) performance.

In this paper, we propose to transmit sparse data by exploiting block Markov superposition transmission (BMST) of high-rate low-density parity-check (LDPC) codes. The high-rate LDPC codes are taken as the basic codes to lower down the error floors, while the BMST serves as joint source-channel coding (JSCC). The most distinguished feature of the BMST-LDPC codes is their flexible construction, which requires no complicated optimization and applies to a wide range of code rates. More importantly, embedding LDPC codes into the BMST system allows us to carry the sparsity information by free-ride coding without any loss of code rate, which may find applications especially in the scenario when the source sparsity varies from block to block. Numerical results show that the proposed BMST-LDPC coded system performs well for sparse sources with entropy < 0.5 bits, providing an easy way to trade off between the transmission power and the system bandwidth.

In this paper, we present a class of codes, referred to as random staircase generator matrix codes (SGMCs), which have staircase-like generator matrices. In the infinite-length region, we prove that the random SGMC is capacity-achieving over binary-input output-symmetric (BIOS) channels. In the finite-length region, we propose the generalized representative ordered statistics decoding with local constraints (LC-ROSD) algorithm for the SGMCs. The most distinguished feature of the SGMCs with LC-ROSD is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE), avoiding the serial GE of conventional OSD and supporting a potential low decoding latency, as implied from simulations. To analyze the performance of random SGMCs in the finite-length region, we derive the ensemble weight spectrum and invoke the conventional union bound. We also derive a partially random coding union (RCU) bound, which is tighter than the conventional one and is used as a criterion to design the SGMCs. Staircase-like generator matrices allow us to derive a series of (tighter and tighter) lower bounds based on the second-order Bonferroni inequality with the incremental number of codewords. The numerical results show that the decoding performance can match well with the proposed partially RCU bound for different code rates and different profiles. The numerical results also show that the tailored SGMCs with the LC-ROSD algorithm can approach the finite-length performance bound, outperforming the 5G low-density parity-check (LDPC) codes, 5G polar codes, and Reed-Muller (RM) codes.

In this paper, we propose a class of codes, referred to as random staircase generator matrix codes (SGMCs), which have staircase-like generator matrices. In the infinite-length region, we prove that the random SGMC is capacity-achieving over binary-input output-symmetric (BIOS) channels. In the finite-length region, we present the representative ordered statistics decoding with local constraints (LC-ROSD) for the SGMCs. The most distinguished feature of the SGMCs with LC-ROSD is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE), avoiding the serial GE of conventional OSD and supporting a potential low decoding latency, as implied from simulations. To analyze the performance of random SGMCs in the finite-length region, we derive the ensemble weight spectrum and invoke the conventional union bound. We also derive a partially random coding union (RCU) bound, which is tighter than the conventional one and can be used as a criterion to design the SGMCs. The numerical results show that the random SGMCs with the LC-ROSD exhibit a significant decoding time improvement compared to that with the conventional OSD. They also show that the tailored SGMCs with the LC-ROSD can approach the finite-length performance bound, outperforming the 5G low-density parity-check (LDPC) codes, 5G polar codes and Reed-Muller (RM) codes.

It is well-known that a linearly coded vector over an erasure channel can be decoded uniquely if the sub-generator matrix formed by the unerased columns has full row rank. This property is generalized in this paper to a necessary and sufficient condition for an information bit to be retrieved uniquely from a received vector with erasures. We show that an information bit of a linear code can be uniquely decodable if and only if its corresponding row of the sub-generator matrix is linearly independent from the other rows. Then we prove that, for semi-random linear codes over binary-input output-symmetric (BIOS) memoryless channels, the information bits associated with the random part of the generator matrices can be decoded with arbitrarily small error probability as the codelength increases. This in turn is applied to prove the coding theorem for time-invariant convolutional codes.

A new framework is presented in this paper for proving coding theorems for linear codes, where the systematic bits and the corresponding parity-check bits play different roles. Precisely, the noisy systematic bits are used to limit the list size of typical codewords, while the noisy parity-check bits are used to select from the list the maximum likelihood codeword. This new framework for linear codes allows that the systematic bits and the parity-check bits are transmitted in different ways and over different channels. In particular, this new framework unifies the source coding theorems and the channel coding theorems. With this framework, we prove that the Bernoulli generator matrix codes (BGMCs) are capacity-achieving over binary-input output symmetric (BIOS) channels and also entropy-achieving for Bernoulli sources.