skip to main content


Title: CRC-Aided List Decoding of Convolutional and Polar Codes for Short Messages in 5G
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/N0 performance of this polar code, where Eb/N0 is the ratio of the energy per data bit to the noise power spectral density. Furthermore, even better Eb/N0 performance 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/N0 performance 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.  more » « less
Award ID(s):
2008918
NSF-PAR ID:
10347999
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
IEEE International Conference on Communications
Date Published:
Journal Name:
2022 International Conference on Communications
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Tal, Ido (Ed.)
    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 dmin . 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. 
    more » « less
  2. null (Ed.)
    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. 
    more » « less
  3. List Viterbi decoders are a very effective way to improve the performance of block codes in combination with an error detection outer code. In this work, we combine an efficient serial list Viterbi decoder design with an existing serially concatenated, convolutionally-encoded, pulse position modulated code (SCPPM) used in space communication, that exhibits poor performance because of an error floor. The SCPPM code features a 32-bit CRC that provides powerful error detection capability and an outer four-state convolutional code that makes it suitable for a list Viterbi decoder. The system’s code is very long, consisting of 15, 120 bits, which renders a high complexity decoder impractical, while the high error detection allows for a list decoder with very low undetected error probability. We use a very efficient list Viterbi decoder algorithm to avoid most of the redundant operations to produce low complexity serial list Viterbi decoder. The combined system reduces the error floor, moderately for the original version of the system, and completely suppresses it when the code length is increased to four times longer. 
    more » « less
  4. 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 CRCs 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 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 a blocklength of 128. 
    more » « less
  5. This paper derives a union bound on the frame error rate (FER) of a probabilistic amplitude shaping (PAS) system which uses a CRC-aided, rate −k/k+1 , systematic, recursive trellis-coded modulation (TCM). A tail-biting convolutional code (TBCC) provides the feed-forward error correction (FEC) code for the TCM. The system is referred as CRC-TCM-PAS [1]. In order to derive the union bound, we first prove that the concatenation of a CRC and a rate −k/k+1 convolutional code is equivalent to a new convolutional code. Then, we give the generating function of the new convolutional code using Biglieri's product-state-diagram approach. A union bound can be calculated using the generating function. Simulation results show that the derived union bound is tight in the high signal-to-noise ratio (SNR) regime and can be used to design the convolutional and CRC codes. Simulation results also show that the optimized CRC-TCM-PAS system exceeds the random coding union (RCU) bound and outperforms the PAS systems with various FEC codes studied in [2] for the same number of input bits and the same transmission rate. 
    more » « less