This paper presents new achievability bounds on the maximal achievable rate of variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC) at a fixed message size${M}=2^{k}$. We provide bounds for two cases: The first case considers VLSF codes with possibly infinite decoding times and zero error probability. The second case limits the maximum (finite) number of decoding times and specifies a maximum tolerable probability of error. Both new achievability bounds are proved by constructing a new VLSF code that employs systematic transmission of the first$k$message bits followed by random linear fountain parity bits decoded with a rank decoder. For VLSF codes with infinite decoding times, our new bound outperforms the state-of-the-art result for BEC by Devassy et al. in 2016. We show that the backoff from capacity reduces to zero as the erasure probability decreases, thus giving a negative answer to the open question Devassy et al. posed on whether the 23.4% backoff to capacity at$k=3$is fundamental to all BECs. For VLSF codes with finite decoding times, numerical evaluations show that the systematic transmission followed by random linear fountain coding performs better than random linear coding in terms of achievable rates.

Recently, rate-$1/n$zero-terminated (ZT) and tail-biting (TB) convolutional codes (CCs) with cyclic redundancy check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-$(n-1)/n$ZT and TB CCs with short blocklengths. This paper considers both standard rate-$(n-1)/n$CC polynomials and rate-$(n-1)/n$designs resulting from puncturing a rate-$1/2$code. The CRC polynomials are chosen to maximize the minimum distance$d_{\min }$and minimize the number of nearest neighbors$A_{d_{\min }}$. For the standard rate-$(n-1)/n$codes, utilization of the dual trellis proposed by Yamada et al. lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD). CRC-aided SLVD of the TBCCs closely approaches the RCU bound at a blocklength of 128. This paper compares the FER performance (gap to the RCU bound) and complexity of the CRC-aided standard and punctured ZTCCs and TBCCs. This paper also explores the complexity-performance trade-off for three TBCC decoders: a single-trellis approach, a multi-trellis approach, and a modified single-trellis approach with pre-processing using the wrap around Viterbi algorithm.

While constructing polar codes for successive-cancellation decoding can be implemented efficiently by sorting the bit channels, finding optimal polar codes for cyclic-redundancy-check-aided successive-cancellation list (CA-SCL) decoding in an efficient and scalable manner still awaits investigation. This paper first maps a polar code to a unique heterogeneous graph called the polar-code-construction message-passing (PCCMP) graph. Next, a heterogeneous graph-neural-network-based iterative message-passing (IMP) algorithm is proposed which aims to find a PCCMP graph that corresponds to the polar code with minimum frame error rate under CA-SCL decoding. This new IMP algorithm’s major advantage lies in its scalability power. That is, the model complexity is independent of the blocklength and code rate, and a trained IMP model over a short polar code can be readily applied to a long polar code’s construction. Numerical experiments show that IMP-based polar-code constructions outperform classical constructions under CA-SCL decoding. In addition, when an IMP model trained on a length-128 polar code directly applies to the construction of polar codes with different code rates and blocklengths, simulations show that these polar-code constructions deliver comparable performance to the 5G polar codes.

This paper explores list decoding of convolutional and polar codes for short messages such as those found in the 5G physical broadcast channel. A cyclic redundancy check (CRC) is used to select a codeword from a list of likely codewords. One example in the 5G standard encodes a 32-bit message with a 24-bit CRC and a 512-bit polar code with additional bits added by repetition to achieve a very low rate of 32/864. This paper shows that optimizing the CRC length improves the Eb/N0performance of this polar code, where Eb/N0is the ratio of the energy per data bit to the noise power spectral density. Furthermore, even better Eb/ N0performance is achieved by replacing the polar code with a tail-biting convolutional code (TBCC) with a distance-spectrum-optimal (DSO) CRC. This paper identifies the optimal CRC length to minimize the frame error rate (FER) of a rate-1/5 TBCC at a specific value of Eb/ N0. We also show that this optimized TBCC/CRC can attain the same excellent Eb/ N0performance with the very low rate of 32/864 of the 5G polar code, where the low rate is achieved through repetition. We show that the proposed TBCC/CRC concatenated code outperforms the PBCH polar code described in the 5G standard both in terms of FER and decoding run time. We also explore the tradeoff between undetected error rate and erasure rate as the CRC size varies.

Recently, rate-1/ω zero-terminated and tail-biting convolutional codes (ZTCCs and TBCCs) with cyclic-redundancy-check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-(ω – 1)/ω CCs with short blocklengths, considering both the ZT and TB cases. The CRC design seeks to optimize the frame error rate (FER) performance of the code resulting from the concatenation of the CRC code and the CC. Utilization of the dual trellis proposed by Yamada et al. lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD) of ZTCCs and TBCCs. CRC-aided SLVD of the TBCCs closely approaches the RCU bound at blocklength of 128.

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with m optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations to the tail probability of length-n cumulative information density. Building on the work of Yavas et al., for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally optimal upper bounds over all thresholds yields the globally minimum upper bound and the above method is called the two-step minimization. Relaxing to allow positive real-valued decoding times activates the gap constraint. We develop gap-constrained sequential differential optimization (SDO) procedure to find the optimal, gap-constrained, real-valued decoding times. In the error regime of practical interest, Polyanskiy's scheme of stopping at zero does not help. In this region, the achievability bounds estimated by the two-step minimization and gap-constrained SDO show that Polyanskiy’s achievability bound for VLSF codes can be approached with a small number of decoding times.

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate-$1/\omega $and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose thedistance-spectrum optimal (DSO)CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to 1 at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting 64 information bits with a rate-1/2 convolutional encoder. For a target error probability$10^{-4}$, simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within 0.4 dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values.

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes.

Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al., this paper presents algorithms for low-complexity sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial k binary transmissions can be sent before any feedback is required and groups messages with equal posteriors to reduce the number of posterior updates from exponential in k to linear in k. Simulation results demonstrate that achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of average blocklength, faster than known finite-blocklength lower bounds on achievable rate with noiseless active feedback and significantly faster than finite-blocklength lower bounds for a stop feedback system.

Cyclic redundancy check (CRC) codes combined with convolutional codes yield a powerful concatenated code that can be efficiently decoded using list decoding. To help design such systems, this paper presents an efficient algorithm for identifying the distance-spectrum-optimal (DSO) CRC polynomial for a given tail-biting convolutional code (TBCC) when the target undetected error rate (UER) is small. Lou et al. found that the DSO CRC design for a given zero-terminated convolutional code under low UER is equivalent to maximizing the undetected minimum distance (the minimum distance of the concatenated code). This paper applies the same principle to design the DSO CRC for a given TBCC under low target UER. Our algorithm is based on partitioning the tail-biting trellis into several disjoint sets of tail-biting paths that are closed under cyclic shifts. This paper shows that the tail-biting path in each set can be constructed by concatenating the irreducible error events (IEEs) and circularly shifting the resultant path. This motivates an efficient collection algorithm that aims at gathering IEEs, and a search algorithm that reconstructs the full list of error events with bounded distance of interest, which can be used to find the DSO CRC. Simulation results show that DSO CRCs can significantly outperform suboptimal CRCs in the low UER regime.

In this paper, we consider the problem of sequential transmission over the binary symmetric channel (BSC) with full, noiseless feedback. Naghshvar et al. proposed a one-phase encoding scheme, for which we refer to as the small-enough difference (SED) encoder, which can achieve capacity and Burnashev's optimal error exponent for symmetric binary-input channels. They also provided a non-asymptotic upper bound on the average blocklength, which implies an achievability bound on rates. However, their achievability bound is loose compared to the simulated performance of SED encoder, and even lies beneath Polyanskiy's achievability bound of a system limited to stop feedback. This paper significantly tightens the achievability bound by using a Markovian analysis that leverages both the submartingale and Markov properties of the transmitted message. Our new non-asymptotic lower bound on achievable rate lies above Polyanskiy's bound and is close to the actual performance of the SED encoder over the BSC.

This paper uses convolutional codes (CCs) with distance-spectrum optimal (DSO) cyclic redundancy checks (CRCs) and the serial list Viterbi algorithm (S-LVA) to approach the random coding union (RCU) bound with low decoding complexity at the target FER. We show, for example, that a 64-state zero-terminated CC with a DSO CRC can achieve performance within 0.5 dB of the RCU bound for information blocklength k=64 at FER of 10-3. We also show that a tail-biting CC with a DSO CRC can achieve even better performance, within 0.05 dB of the RCU bound at FER of 10-4for a 256-state CC with k=64. This paper provides analysis of decoding complexity, which for S-LVA depends on the expected list size. We show that if the target FER is low enough, the expected list size approaches one so that the average complexity of S-LVA approaches that of standard soft Viterbi on the CC, i.e., with no list decoding. We also provide DSO CRCs for CCs with k=64 and rates of 1/2, 1/3, 1/6 and 1/12 for the 5G new radio control channel and compare their performance with polar codes.

This paper provides a reduced-complexity approach to maximum likelihood (ML) decoding of cyclic codes. A cyclic code with generator polynomial gcyclic(x) may be considered a terminated convolutional code with a nominal rate of 1. The trellis termination redundancy lowers the rate from 1 to the actual rate of the cyclic code. The proposed decoder represents gcyclic(x) as the product of two polynomials, a convolutional code (CC) polynomial gcc(x) and a cyclic redundancy check (CRC) polynomial gcrc(x), i.e., gcyclic(x) = gcc(x)gcrc(x). This representation facilitates serial list Viterbi algorithm (S-LVA) decoding. Viterbi decoding is performed on the natural trellis for gcc(x), and gcrc(x) is used as a CRC to determine when the S-LVA should conclude. At typical target frame error rates, the expected list size of S-LVA is small, and the average decoding complexity is dominated by the trellis complexity of gcc(x) rather than gcyclic(x). Some high-rate binary Bose-Chaudhuri- Hocquenghem (BCH) examples show that the proposed use of S-LVA via factorization significantly lowers complexity as compared to using the minimum-complexity trellis representation of gcyclic(x) for soft ML decoding.

Let Xnbe a uniformly distributed n-dimensional binary vector, and Ynbe the result of passing Xnthrough a binary symmetric channel (BSC) with crossover probability α. A recent conjecture postulated by Courtade and Kumar states that I(f(Xn); Yn) ≤ 1 - H(α). Although the conjecture has been proved to be true in the dimension-free high noise regime by Samorodnitsky, here we present a calculus-based approach to show a dimension-dependent result by examining the second derivative of H(α) - H(f(Xn)|Yn) at α = 1/2. Along the way, we show that the dictator function is the most informative function in the high noise regime.

This paper analyzes the serial list Viterbi algorithm (S-LVA) used in conjunction with optimal CRC codes that minimize probability of undetected error by maximizing the minimum distance between convolutional codewords that pass the CRC check, following Lou et al. In particular, the paper identifies such optimal CRC codes for the 3GPP standard convolutional code (561,753). As SNR varies and the maximum list size L ranges from one to its maximum, this paper uses bounds, approximations, and simulation to characterize decoding complexity and the trade-off between erasure probability and undetected error probability. The complexity of S-LVA is captured by the expected value of the number of decoding attempts required before a CRC check passes or L codewords have been examined. For S-LVA with a degree-m CRC and maximum possible L, which is the cardinality of the set of all possible convolutional codewords, the expected value of the number of decoding attempts converges to one as SNR increases and to 2m(1 - ϵ), for a small ϵ > 0, as SNR decreases. For S-LVA with the maximum possible L, the erasure probability is zero. As L decreases from this maximum, the erasure probability increases and the TIE probability decreases to that of L = 1, for which TIE probability is well approximated by a nearest-neighbor bound.

The decoding problem is addressed in this paper for the scenario that convolutional codes are employed at the source node of the network with linear or convolutional network coding for error correction. Since network errors may disperse or neutralize due to network coding, decoding cannot be done at sink nodes merely based on the minimum Hamming distance between the received and sent sequence. Source decoding is proposed in previous work by multiplying the inverse of the network transfer matrix, where the inverse is hard to compute and sometimes the result is noncausal. Starting from the Maximum A Posteriori (MAP) decoding criterion, we find that it is equivalent to the minimum error weight under our model. Inspired by classical Viterbi algorithm, we propose a Viterbi-like decoding algorithm based on the minimum error weight of combined error vectors, which can be carried out directly at sink nodes and can correct any network errors within the capability of convolutional network error correction codes (CNECC). We then study the distributed decoding of CNECC and give a sufficient condition that is able to realize such a decoding process with the proposed algorithm.