TL;DR
This paper introduces CRC-aided convolutional codes (CRC-CCs) designed for short blocklengths, combining convolutional codes with optimized Cyclic Redundancy Check (CRC) codes. By using Serial List Viterbi Decoding (SLVD), these codes achieve near maximum-likelihood performance with manageable complexity, approaching theoretical bounds and even outperforming them in some cases.
What Problem Does This Paper Address?
The paper tackles the challenge of designing efficient and reliable error-correcting codes for short blocklengths (e.g., fewer than 1000 information bits). This is crucial for emerging technologies like 5G that demand ultra-reliable, low-latency communication. While theoretical bounds like the Random Coding Union (RCU) and Minimum Converse (MC) bounds exist, constructing practical codes that approach these bounds with reasonable decoding complexity has been a significant hurdle. Specifically, the paper addresses how to design optimal CRC codes to work with convolutional codes (both zero-terminated and tail-biting) to minimize undetected errors, and how to efficiently decode these concatenated codes using SLVD.
Methods
The core contribution lies in the design and analysis of CRC-aided convolutional codes (CRC-CCs). Key methods include:
- Distance-Spectrum Optimal (DSO) CRC Polynomial Design: The authors propose a method to find CRC polynomials that minimize the union bound on undetected error probability. This involves a search algorithm, particularly for tail-biting convolutional codes (TBCCs).
- Serial List Viterbi Decoding (SLVD): This decoding technique is employed to achieve near maximum-likelihood performance. SLVD generates a ranked list of candidate codewords, allowing for a more flexible termination criterion based on CRC verification.
- Performance and Complexity Analysis: The paper provides theoretical bounds and approximations for the probabilities of correct decoding, undetected errors, and negative acknowledgments (NACKs). It also analyzes the decoding complexity, showing it's primarily governed by the expected list rank, which converges to 1 at high Signal-to-Noise Ratios (SNRs).
- Two-Phase DSO CRC Design Algorithm: A novel algorithm is presented for designing DSO CRC polynomials for TBCCs, involving a collection phase for error events and a search phase for optimal polynomials.
Datasets
Not discussed in the paper. The paper focuses on theoretical design and simulation-based performance evaluation rather than training on specific datasets.
Key Insights and Ideas
- CRC as a powerful tool for short blocklengths: Concatenating a convolutional code with a well-designed CRC code significantly improves error detection and correction capabilities, especially in the short blocklength regime.
- DSO CRC polynomials are crucial: Simply choosing a standard CRC polynomial is suboptimal. Designing CRC polynomials specifically for the underlying convolutional code (DSO CRCs) is essential for minimizing undetected errors and achieving near-bound performance.
- SLVD bridges the gap: Serial List Viterbi Decoding allows the CRC-CC to approach maximum-likelihood performance without an exorbitant increase in complexity, as its complexity scales with the expected list rank, which is manageable at practical SNRs.
- Tail-biting offers advantages but complicates decoding: TBCCs avoid the rate loss associated with zero-termination but require more sophisticated decoding algorithms due to the state-closure constraint.
- Performance can exceed theoretical bounds: In some cases, the proposed CRC-TBCCs were shown to outperform the RCU bound, highlighting the effectiveness of the design.
Key Results
- Near-RCU bound performance: For transmitting 64 information bits with a rate-1/2 convolutional encoder, the best CRC-ZTCC approaches the RCU bound within 0.4 dB at a target error probability of $10^{-4}$.
- Outperforming RCU bound: Several CRC-TBCCs were shown to outperform the RCU bound at moderate SNRs.
- Complexity scaling: The complexity of SLVD for CRC-CCs is shown to be manageable, converging to a low value at high SNRs, making it practical for real-world applications.
- DSO CRC design effectiveness: Simulations demonstrate that using DSO CRC polynomials leads to significant performance gains compared to arbitrary CRC choices.
Limitations and Future Work
- Supremum list rank (λ) estimation: While the paper defines the supremum list rank (λ), it notes that finding a tighter bound on λ and developing an efficient algorithm to compute it remains an open problem.
- E[L|X=0] estimation: Estimating E[L|X=0] (expected list rank given zero input) is challenging and is an area for future investigation.
- Suboptimal convolutional codes: The paper focuses on optimal convolutional codes. Investigating the performance of suboptimal convolutional codes with DSO CRCs is suggested.
- Moderately short blocklengths: The paper's focus is on short blocklengths. Exploring the performance of CRC-CCs in the moderately short blocklength regime (e.g., 256 < n < 1000) is a promising direction.
- Joint design of puncturing and CRC: For punctured codes, jointly designing the puncturing pattern and the optimal CRC polynomial is an open research question.
Summary updated