We propose a class of codes, referred to as staircase matrix codes (SMCs), which have staircase-like generator matrices or parity-check matrices. We illustrate that polar codes and Reed-Muller (RM) codes are (equivalent to) two instances of SMCs. The most distinguished feature of the SMCs is that the staircase-like matrices enable parallel implementation of the Gaussian elimination (GE). Then we propose a representative ordered statistics decoding (ROSD) algorithm for the SMCs. Different from the conventional OSD, which forms the most reliable basis (MRB) by selecting reliable bits globally, the proposed ROSD forms an extended basis by selecting relatively reliable bits locally at least one from each staircase. We demonstrate by simulation that the ROSD has a similar performance to the OSD with local constraints (LC-OSD) and that the proposed random SMCs can outperform the RM codes and the polar codes. To further reduce the decoding delay and improve the performance, we propose a heuristic construction of staircase generator matrix codes (SGMCs) and analyze the ensemble weight spectrum (related to performance) and the quality of MRB (related to average number of test error patterns (TEPs)) for the heuristic construction. The simulation results show that, the proposed heuristic construction can reduce the average number of TEPs of the ROSD and provide a potential reduction in average decoding delay in the high signal-to-noise ratio (SNR) region. Furthermore, the proposed heuristic construction can approach the RCU bounds in a wide range of code rates.

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 a two-stage soft-decision decoding (SDD) algorithm for BCH codes. At the first stage, we search for test error patterns (TEPs) according to the reliabilities of the received bits by using the flipping pattern tree (FPT) algorithm or the ordered reliability bits (ORB) technique, with a bounded number of searches. At the second stage, traditional algebraic hard-decision decoding (HDD), say, Berlekamp-Massey (BM) algorithm, is performed for these TEPs to find codewords. The proposed algorithm, referred to as FPT-BM algorithm or ORB-BM algorithm, can achieve near-optimal performance with a significantly small number of searches (dozens to hundreds). This enables efficient parallel implementation, ensuring low decoding latency and high throughput. To justify the sufficiency of the small number of searches, we provide qualitative reasoning and quantitative evaluation (using saddlepoint approximation) to show that the transmitted codeword under the proposed FPT-BM decoding strategy is reached much earlier in the search list than that under the single stage decoding (FPT-only). To analyze the performance, we calculate the upper bound on the performance gap between the proposed algorithm and maximum likelihood (ML) decoding based on the saddlepoint approximation, showing that the proposed algorithm can effectively approach the ML lower bound for high rate BCH codes. To reduce computational complexity, we introduce a filtering criterion, where the algebraic hard-decision decoding (BM decoding) is performed only for those candidates satisfying a sufficient number of parity-check equations. To determine the key parameters, we provide an intuitive criterion for the threshold in the filtering step based on the statistical analysis and a quantitative criterion for the maximum list size based on the upper bound on the performance gap to ML decoding. Numerical results demonstrate that: 1) By introducing the filtering criterion, the proposed FPT-BM algorithm effectively reduces the number of BM calls by half, with negligible performance loss, and outperforms the Chase-BM algorithm under the same filtering criterion; 2) The proposed decoding algorithm outperforms single stage decoding (FPT only) under limited search sizes; 3) For high rate BCH codes, the proposed decoding algorithm can approach the finite-length capacity, while for medium rate regions, the proposed decoding algorithm also exhibits better performance over FPT-only and BM-only decoding algorithms.

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.

In this paper, we propose a new ordered statistics decoding (OSD) algorithm called representative OSD (ROSD), specifically designed for polar codes. The generator matrices of polar codes are composed of the rows indexed by an information index set in a lower triangular matrix with ones on the diagonal. Therefore, the generator matrices of polar codes have a staircase-like structure that enables us to present the parallel implemen-tation of Gaussian elimination (GE) in ROSD avoiding the serial GE in conventional OSD. Different from the conventional OSD which forms the most reliable basis (MRB) by selecting reliable bits globally, the proposed ROSD forms an extended basis by selecting relatively reliable bits locally at least one from each staircase. Simulation results show that the ROSD has a similar performance to the LC-OSD and conventional OSD for 5G polar codes and Reed-Muller (RM) construction polar codes.

In this paper, we propose a new joint source-channel coding (JSCC) for short-packet communications, especially for the uplink from the sensor to the base station. At the transmitter, the sensing information is first encoded by a two-stage description, referred to as classified enumerative (CE) coding, and then encoded by a random multiple-rate code. The two-stage CE coding describes a binary sequence by its type class indicator and its rank in the associated type class, which can approach the entropy for biased sources. The random multiple rate coding transforms the variable-length output of the CE coding into a fixed-length channel input, allocating lower energy to lower-rate component codes. At the receiver, the sensing information can be recovered by a trial-and-error (for type classes) decoding either serially or parallelly. The serial decoding has a low implementation complexity, while the parallel decoding has a low decoding delay. To alleviate the mis-correction probability and stop the decoding earlier, we turn to the cyclic redundancy check (CRC) coding. To predict the performance of the proposed JSCC scheme, we present the weighted random-coding union (RCU) bounds based on the conventional RCU bound. The proposed JSCC scheme is universal in the sense that it does not require knowledge of source statistics. Simulation results show that the performance matches well with the presented bounds, validating our analysis. Simulation results also show that the proposed JSCC scheme can outperform the double polar JSCC scheme (exhibiting a coding gain of up to 0.3 dB) and can approach the JSCC bounds (exhibiting a gap of less than 0.5 dB).

We present a tandem scheme for Gaussian source compression, where a dead-zone quantizer is concatenated with a ternary low density generator matrix (LDGM) code. Both theoretical analysis and simulation results show that the LDGM codes can be universally optimal for near-lossless compression of ternary sources. Consequently, the distortion with the tandem scheme is mainly caused by the quantization, which can be negligible for high-rate quantizer. The most distinguished feature of the proposed scheme is its flexibility. The dead-zone quantizer can choose a suitable quantization level according to the distortion allowed, while the LDGM codes can adapt the code rate to approach the entropy of the quantized sequence. This is helpful to trade off between bandwith and distortion. In the meanwhile, the proposed scheme is robust when combined with the channel codes for transmission over noisy channels because of the fixed-length feature.

We present a ternary source coding scheme in this paper, which is a special class of low density generator matrix (LDGM) codes. We prove that a ternary linear block LDGM code, whose generator matrix is randomly generated with each element independent and identically distributed, is universal for source coding in terms of the symbol-error rate (SER). To circumvent the high-complex maximum likelihood decoding, we introduce a special class of convolutional LDGM codes, called block Markov superposition transmission of repetition (BMST-R) codes, which are iteratively decodable by a sliding window algorithm. Then the presented BMST-R codes are applied to construct a tandem scheme for Gaussian source compression, where a dead-zone quantizer is introduced before the ternary source coding. The main advantages of this scheme are its universality and flexibility. The dead-zone quantizer can choose a proper quantization level according to the distortion requirement, while the LDGM codes can adapt the code rate to approach the entropy of the quantized sequence. Numerical results show that the proposed scheme performs well for ternary sources over a wide range of code rates and that the distortion introduced by quantization dominates provided that the code rate is slightly greater than the discrete entropy.

In this paper, we propose a new ordered statistics decoding (OSD) for linear block codes, which is referred to as local constraint-based OSD (LC-OSD). Distinguished from the conventional OSD, which chooses the most reliable basis (MRB) for re-encoding, the LC-OSD chooses an extended MRB on which local constraints are naturally imposed. A list of candidate codewords is then generated by performing a serial list Viterbi algorithm (SLVA) over the trellis specified with the local constraints. To terminate early the SLVA for complexity reduction, we present a simple criterion which monitors the ratio of the bound on the likelihood of the unexplored candidate codewords to the sum of the hard-decision vector’s likelihood and the up-to-date optimal candidate’s likelihood. Simulation results show that the LC-OSD can have a much less number of test patterns than that of the conventional OSD but cause negligible performance loss. Comparisons with other complexity-reduced OSDs are also conducted, showing the advantages of the LC-OSD in terms of complexity.