Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

In this paper, we present fast encoding algorithms for Hermitian codes based on the Lin-Chung-Han fast Fourier transform (LCH-FFT). For non-systematic encoding, we extend the LCH basis to the bivariate polynomial space and develop a two-dimensional FFT algorithm. For systematic encoding, we propose a modified partial FFT algorithm and present a procedure for computing the unknown intermediates. For a Hermitian code of length $n$, the computational complexity of the presented non-systematic and systematic encoding algorithms are both $O(n{\text{log}}n)$, improving upon the currently best-known encoding complexity $O\left( {n{\text{lo}}{{\text{g}}^2}n{\text{loglog}}n} \right)$.

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.

Free-ride coding, as an approach that admits transmission of a few extra bits over a low-density parity-check (LDPC) coded link without bandwidth expansion, is applied in this paper to construct coupled LDPC codes. Firstly, we present a syndrome channel model and derive the lower and upper bounds on its capacity (referred to as accessible capacity), indicating the feasibility of the reliable transmission of extra bits. Secondly, we present the performance evaluation on both the word error rate (WER) and the bit error rate (BER) for the free-ride codes with simple lower and upper bounds. Then we propose three applications of free-ride coding to construct coupled LDPC codes, including implicit globally-coupled LDPC (GC-LDPC) codes, partial product-LDPC codes, and terminated spatially-coupled LDPC (SC-LDPC) codes, all of which have the figure of merits that they share the same code rates with the basic component LDPC codes. Simulation results show that: 1) the proposed GC-LDPC codes can outperform the component LDPC codes, yielding a coding gain of up to 0.8 dB; 2) the proposed product codes with$(3,6)$-regular LDPC component codes of length 1024 can lower the WER from$10^{-2}$down to$10^{-6}$at the SNR around 2 dB; 3) the proposed terminated SC-LDPC codes can perform as well as the conventional terminated SC-LDPC codes but without any rate loss.

In this paper, we propose a new transmission scheme for the scenario where two nodes attempt to exchange messages and the conventional low-density parity-check (LDPC) codes are implemented for error correction. In the proposed scheme, the ACK/NACK feedback information is transmitted along with the payload data by free-ride codes, while the re-transmitted codewords are superimposed (XORed) on the current codewords, both of which cost neither extra bandwidth nor transmission power. Firstly, we present a syndrome channel model and derive its capacity (referred to as accessible capacity) with a lower bound, implying that the reliable transmission of extra bits (feedback information) is possible. Then, the performance of the extra bits is analyzed by the dependency testing (DT) bound for the syndrome channels. Moreover, motivated by the DT bound, we present a low-complexity DT-like decoder for the free-ride codes. For the superposition retransmission, we present a practical implementation, where those unsuccessfully decoded codewords are sparsely interleaved and superimposed onto the current codewords. In addition, the presented transmission scheme is combined with the conventional hybrid automatic repeat request (HARQ) protocol, resulting in a throughput-enhanced conjunction HARQ scheme. Numerical results show that the word error rate (WER) of the LDPC codes can be significantly reduced by using the presented transmission scheme, but without any extra bandwidth or transmission power. They also show that the presented conjunction HARQ schemes can achieve a throughput improvement up to 80% over fading channels in comparison with the original 5G HARQ scheme.

In this paper, we propose a new construction of product codes, where the whole information array is protected row-by-row by a low-density parity-check (LDPC) code while only a portion of the information array is protected column-by-column by an algebraic code. The most distinguished feature of the proposed product code is that, thanks to the free-ride coding technique, the additional column check bits are transmitted implicitly rather than explicitly. The constructed codes are referred to as implicit partial product-LDPC codes, which have the same rates as the row component LDPC codes. The decoding algorithm can be divided into four stages, including decoding of the free-ride codes, first-round decoding of the row codes, decoding of the column codes, and second-round decoding of the row codes by exploiting the messages associated with those successfully decoded columns. To predict the extremely low error rate of the doubly-protected (by both the row code and the column code) information bits, we derive an approximate upper bound. The simulation results show that, with a (3,6)-regular LDPC code of length 1024 as the component code, the proposed product code can lower the word error rate (WER) from 10−2down to 10−6at the SNR around 2 dB. The numerical results also show that the doubly-protected information bits are more reliable, which can have a bit error rate (BER) down to 10−15at SNR around 2.6 dB as implied by the presented approximate upper bound.

In this paper, we present a new construction of the globally-coupled LDPC (GC-LDPC) codes, referred to as implicit GC-LDPC codes, where the additional global parity-check bits are transmitted using the free-ride coding. The presented GC-LDPC codes have the same rates as the component LDPC codes, avoiding the rate reduction caused by the global parity checks for the conventional GC-LDPC codes. Moreover, the encoders of the component LDPC codes are reusable in the presented GC-LDPC codes, a distinguished feature as compared with the conventional GC-LDPC codes. The simulation results show that the proposed implicit GC-LDPC codes can improve the performance of the component LDPC codes, yielding extra coding gain of up to 0.7 dB (with (3,6)-regular LDPC codes as the component codes) and 0.5 dB (with IEEE 802.16e LDPC codes as the component codes).

This paper focuses on the real-time status update in a multiaccess vehicular network, in which multiple vehicles transmit not only the payload data (e.g., monitoring data) but also the extra data (e.g., driving intention) to a road side unit for scheduling vehicles to improve traffic efficiency and safety. A free-ride code is implemented, where the extra data is encoded by a random but fixed generator matrix and is delivered by superposition on the low-density parity-check (LDPC) coded payload data, consuming neither extra bandwidth nor extra transmit power. Considering the time slotted ALOHA random access protocol, we derive the closed-form expression for average age of information (AoI), and evaluate the AoI for both payload data and extra data. Numerical simulations demonstrate that free-ride codes can not only transmit extra data without extra transmit power, but also reduce the average AoI of extra data without affecting the average AoI of payload data.

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed asaccessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (calledsyndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064.

In this paper, we propose a new coding scheme called dual coupled polar (DC-polar) code, which is constructed by coupling two basic polar codes. We present a successive cancellation list (SCL) decoding algorithm, where a list of candidates are generated from the first basic polar code and the most likely one is identified by combining the second basic polar code. For performance analysis and code construction, we derive lower bounds and estimate the performance by the union bounds based on the low-weight codewords. We employ the adaptive SCL decoding for DC-polar codes with early termination to reduce the decoding complexity. It is shown by numerical simulations that the proposed DC-polar codes can attain a near-capacity performance in the short-length regime.

We propose in this paper a new coding scheme called twisted-pair superposition transmission (TPST). The encoding is to “mix together” a pair of basic codes by superposition, while the decoding can be implemented as a successive cancellation list decoding algorithm. The most significant features of the TPST code are its predictable performance that can be estimated numerically from the basic codes and its flexible construction in the sense that it can be easily adapted to different coding rates. To construct good TPST codes in the finite length regime, we propose two design approaches – rate allocation and partial superposition. By taking tail-biting convolutional codes (TBCC) as basic codes, we show by numerical results that the constructed TPST-TBCCs have performance close to the random coding union bound in the short length regime.

This paper is concerned with a special class of unit memory convolutional codes (UMCCs), called block oriented UMCCs (BOUMCCs). Distinguished from conventional UMCCs, which usually have small constraint lengths, the BOUMCCs have relatively large constraint lengths. We conduct the performance analysis by assuming a first-order Markov model, which indicates that the performance of the BOUMCCs depends critically on both the error propagation and the sub-frame error rate of the first layer. The error propagation can be alleviated by the use of partial superposition, which is specified by a superposition matrix with a fraction of columns being nulled. Given a superposition fraction, we propose a tree growing and pruning algorithm (TGPA) with a tunable sliding window, which provides a convenient way to trade off the decoding delay and the performance. We also present a structured construction and show by simulation that there is no performance degradation compared with random construction. Numerical results also show that, by taking the TBCCs as basic codes, the performance of BOUMCCs with TGPA is comparable to that of other short codes but with a more flexible construction or a lower complexity.

In this paper, we propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SysConv-LDGM) codes by a random splitting process. The SysConv-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SysConv-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis.

In this paper, we propose a novel coding scheme, which is referred to as twisted-pair superposition transmission (TPST) and can be constructed from any given basic code by "mixing together" a pair of basic codewords in a "twisted" manner. We present a successive cancellation list decoding algorithm for TPST, where a list of candidates for the first layer is generated serially and the most competitive one is identified by combining the second layer. Thresholds on empirical divergence function (EDF) are introduced for early termination to trade off performance with decoding complexity. Genie-aided bounds are derived, indicating that the performance of TPST codes can be improved by employing partial superposition. Numerical simulation results show that, by taking tail-biting convolutional codes (TBCCs) as basic codes, we can construct TPST-TBCCs with near-capacity performance in the short length regime. The construction is flexible in the sense that it can be easily adapted to a wide range of coding rates.

This paper is concerned with block Markov superposition transmission (BMST) of tail-biting convolutional code (TBCC). We propose a new decoding algorithm for BMST-TBCC, which integrates a serial list Viterbi algorithm (SLVA) with a soft check instead of conventional cyclic redundancy check (CRC). The basic idea is that, compared with an erroneous candidate codeword, the correct candidate codeword for the first sub-frame has less influence on the output of Viterbi algorithm for the second sub-frame. The threshold is then determined by statistical learning based on the introduced empirical divergence function. The numerical results illustrate that, under the constraint of equivalent decoding delay, the BMST-TBCC has comparable performance with the polar codes. As a result, BMST-TBCCs may find applications in the scenarios of the streaming ultra-reliable and low latency communication (URLLC) data services.

In this paper, we present a new class of spatially coupled low-density parity-check (SC-LDPC) codes, which are constructed by sending codewords of LDPC block code (LDPCBC) in a block Markov superposition transmission (BMST) manner. Different from the conventional SC-LDPC codes, the proposed SC-LDPC codes can have encoder/decoder implemented with the basis of the hardware components of the corresponding LDPC-BCs. The proposed SC-LDPC codes are also a special class of BMST-LDPC codes. Distinguished from other types of BMST codes, BMST-LDPC codes have lower error floors even with an encoding memory of one and hence have lower decoding latency. Also different from the original BMST codes, partial superposition is implemented to alleviate error propagation. To analyze the bit error rate (BER) performance, we present the genie-aided (GA) bounds, which can be obtained by simulation or estimated from the performance of the basic code. Numerical results are presented to validate our analysis and demonstrate the performance advantage of the BMST-LDPC codes over the LDPC-BCs.

In this study, the authors propose a class of exclusive OR (XOR)‐based maximum distance separable (MDS) array codes, referred to as horizontal–vertical–diagonal (HVD) codes, which can tolerate triple disk failures with optimal update complexity. The HVD code has a similar data/parity layout to the horizontal–vertical (HV) code and has many figures of merits as the HV code. Also, an efficient recovery algorithm is proposed, which can be implemented to accelerate the recovery process of double disk failures by making full use of all kinds of parities in the HVD code. The authors evaluate the encoding/decoding efficiency of the HVD code by comparing the number of XORs and the number of disk reads with other MDS array codes. Results show that the HVD code inherits most of the merits of the HV code and requires less number of disk reads when recovering single disk failure.

In this paper, we present the block Markov superposition transmission of BCH (BMST-BCH) codes, which can be constructed to obtain a very low error floor. To reduce the implementation complexity, we design a low complexity iterative sliding-window decoding algorithm, in which only binary and/or erasure messages are processed and exchanged between processing units. The error floor can be predicted by the proposed genie-aided lower bounds, while the waterfall performance can be analyzed by the density evolution method. To evaluate the error floor of the constructed BMST-BCH codes at a very low bit error rate (BER) region, we propose a fast simulation approach. Numerical results show that, at a target BER of 10-15, the proposed BMST-BCH code with hard-decision can achieve a net coding gain (NCG) of 10.55 dB with 25% overhead, while a soft-decision design can yield an NCG of 10.74 dB. The construction of BMST-BCH codes is flexible to trade off latency against performance at all overheads of interest and may find applications in optical transport networks as an attractive candidate.

This paper is concerned with the delayed bit-interleaved coded modulation with iterative decoding (DBICM-ID). We present new criteria for bit-labeling in the DBICM-ID system based on the harmonic mean of the minimum squared Euclidean distance (HMMSED) and the mean average bit-wise mutual information (MABMI) criteria. Different from the conventional HMMSED criterion, taking into account the conditions varying from no feedback to perfect feedback, we also evaluate the variance of the harmonic mean, which is then deployed to reveal the convergence rate. We take 16-QAM as an example to confirm our analysis. Numerical results show that, DBICM-ID with the designed bit-labeling scheme can obtain an extra coding gain of about 0.5 dB.

This paper is concerned with three ensembles of systematic low density generator matrix (LDGM) codes, all of which were provably capacity-achieving in terms of bit error rate (BER). This, however, does not necessarily imply that they achieve the capacity in terms of frame error rate (FER), as seen from a counterexample constructed in this paper. We then show that the first and second ensembles are capacity-achieving under list decoding over binary-input output symmetric (BIOS) memoryless channels. We point out that, in principle, the equivocation due to list decoding can be removed with negligible rate loss by the use of the concatenated codes. Simulation results show that the considered convolutional (spatially-coupled) LDGM code is capacity-approaching with an iterative belief propagation decoding algorithm.

This paper is concerned with block Markov super-position transmission of BCH (BMST-BCH) codes. Compared with other BMST codes, BMST-BCH codes can achieve a lower error floor with an encoding memory of two, which is critical to reduce both delay and implementation complexity. To further reduce the implementation complexity, we propose a hard-decision sliding-window decoding algorithm, in which only binary and/or erasure messages are processed and exchanged between nodes. A fast simulation approach is proposed, with the help of the genie-aided lower bound and the density evolution analysis, to evaluate the performance of BMST-BCH codes at the BER of 10-15. BMST-BCH codes are constructed with overheads ranging from 15% to 25%, exhibiting performances comparable to staircase codes with similar latencies. The proposed construction is more flexible to trade off latency against performance, and may find applications in optical transport networks as an attractive candidate.