Efficient Error-Correcting Codes in the Short Blocklength Regime

Mustafa Cemil Coşkun; Giuseppe Durisi; Thomas Jerkovits; Gianluigi Liva; William Ryan; Brian Stein; Fabian Steiner

Source-linked AI summary

Efficient Error-Correcting Codes in the Short Blocklength Regime

Mustafa Cemil Coşkun, Giuseppe Durisi, Thomas Jerkovits, Gianluigi Liva, William Ryan, Brian Stein, Fabian Steiner

arXiv:1812.08562v2Dec 20, 2018cs.IT

TL;DR

Short-block coding remains difficult because classical design tools and exact finite-length optimization are limited, yet it matters for emerging short-data applications. The paper reviews code constructions and decoding methods, comparing binary and high-order modulation schemes with finite-length bounds over AWGN channels. It finds a broad spectrum of approaches that can approach tight bounds with different performance–complexity tradeoffs, while fixed-length AWGN-focused analysis leaves fading and feedback settings open.

Problem
Designing efficient codes for short information blocks is an open problem motivated by applications that transmit short data units, while classical short-block design tools can fail to model iterative decoding accurately.
Method
The paper reviews short-block code constructions and decoding algorithms, comparing binary and high-order modulation schemes with finite-length bounds over the AWGN channel.
Results
The review finds a wide spectrum of short-block transmission solutions, including codes approaching finite-length bounds with different decoding-complexity tradeoffs.
Takeaways & Limitations
Short-block designs can approach tight finite-length benchmarks, but practical choices trade error-correction performance against decoding complexity.
Takeaways & Limitations
The paper focuses on fixed-length coding and leaves unknown-state channels such as fading without channel-state information as open problems.

Abstract

from arXiv · show

The design of block codes for short information blocks (e.g., a thousand or less information bits) is an open research problem that is gaining relevance thanks to emerging applications in wireless communication networks. In this paper, we review some of the most promising code constructions targeting the short block regime, and we compare them with both finite-length performance bounds and classical error-correction coding schemes. The work addresses the use of both binary and high-order modulations over the additive white Gaussian noise channel. We will illustrate how to effectively approach the theoretical bounds with various performance versus decoding complexity tradeoffs.

1. Introduction

Short-block coding has regained importance for applications transmitting short data units, while asymptotic design tools may be unreliable and practical performance must be compared against finite-length limits.

1. Introduction: Short and medium blocklength codes support emerging applications that transmit short data units, motivating renewed interest in efficient constructions and tight performance bounds.The paper identifies machine-type communications, smart metering, Internet of Things, remote command links, and messaging services as examples.
1. Introduction: Classical density-evolution and EXIT-chart methods can fail to model short-block iterative decoders accurately, although heuristic LDPC and turbo designs remain competitive.More sophisticated decoding algorithms are also feasible for short blocks and can compete with iterative decoding.
1. Introduction: The paper reviews short-block code constructions and compares them with finite-length performance bounds and classical error-correction schemes.The comparison covers unfaded AWGN channels with binary and high-order modulations.
1. Introduction: For high-order modulation, the comparison examines coding schemes coupled with modulation, with and without shaping, using block error rate versus Eb/N0 or Es/N0.Eb denotes energy per information bit, while Es denotes energy per modulation symbol.
1. Introduction: The paper organizes the review around short-block limits, classical codes and decoders, modern constructions, comparative evaluations, and conclusions.These topics are covered in Sections 2 through 6.

2. Finite-Length Performance Limits

Finite-length coding asks how closely short codes can approach the minimum achievable error probability, which is difficult to compute exactly but can be bounded and evaluated numerically.

2. Finite-Length Performance Limits: The channel model transmits k bits over n uses of a binary-input AWGN channel, with binary inputs, unit-variance Gaussian noise, and received symbols defined by the channel equation.The rate is R = k/n, and the codeword error probability measures whether the decoded message differs from the transmitted message.
2. Finite-Length Performance Limits: The finite-length objective is ϵ*(R, n), the minimum error probability attainable at rate R and blocklength n, but exact computation requires an infeasible exhaustive code search.Different decoders applied to the same code can yield different error probabilities.
2. Finite-Length Performance Limits: The metaconverse and random coding union bounds provide converse and achievability benchmarks for short-block performance, with the latter extending naturally to mismatched decoding metrics.The metaconverse uses a binary-hypothesis-testing relation and an auxiliary output distribution; RCU analyzes random coding under maximum-likelihood decoding.
2. Finite-Length Performance Limits: At n = 128 and k = 64, MC and RCU bounds predict a minimum Eb/N0 of 3.5–3.7 dB at CER 10^-6, tighter than SPB59 and RCB estimates of 3.3–4.2 dB.The normal approximation places the minimum codeword error probability between the MC and RCU bounds for this example.
2. Finite-Length Performance Limits: As n increases, MC and RCU converge more closely, while at R = 1/2 and CER 10^-6 the n = 1024 gap to the asymptotic limit is about 1.4 dB.The asymptotic limit is Eb/N0 = 0.189 dB for capacity C = 1/2.
2. Finite-Length Performance Limits: The normal approximation is accurate in several tested settings but loses accuracy at small error probabilities and small rates, including a relevant ultra-reliable low-latency regime.The bounds also become increasingly tight as blocklength grows.

3. Classical Short Codes

Classical short-code approaches use near-maximum-likelihood decoding for algebraic and tailbiting convolutional codes, while CRC concatenation trades error correction against error detection. Their performance can approach finite-length bounds, but complexity or required memory limits scalability.

3.1. Short Algebraic Codes under Ordered Statistics Decoding: OSD reduces exponentially costly ML search by limiting decoding to a list of candidate codewords ranked from the most reliable channel observations.The list size grows quickly with t, so small t values preserve manageable complexity for short codes.
3.1. Short Algebraic Codes under Ordered Statistics Decoding: Within 0.1 dB: OSD with t = 4 approaches the NA for the (128, 64) extended BCH code at CER ≈10−4, whereas t = 3 has a ≈0.5 dB gap.OSD achieves near-ML decoding by searching a list generated from low-weight error patterns on the most reliable information positions.
3.2. Tailbiting Convolutional Codes: WAVA decodes tailbiting convolutional codes by recursively applying Viterbi decoding and checking whether the selected path satisfies the tailbiting state constraint.This avoids the potentially expensive parallel decoding of all possible starting states.
3.2. Tailbiting Convolutional Codes: 0.07 dB: (128, 64) binary TBCCs with memory m = 14 operate within this distance of the NA at CER ≈10−4.The required memory must increase with blocklength to approach finite-length bounds, reducing practicality.
3.3. CRC/TBCC Concatenation: CRC/TB CC decoding jointly balances correction and detection, with a list-based or iterative trellis procedure that tests candidate paths against the CRC.A direct WAVA approach can require many states and may sacrifice reliable output-error detection.
3.3. CRC/TBCC Concatenation: At MaxWeak = 4, undetected-error probability is below 0.001, while the known-state and unknown-state CER curves shift rightward by about 0.4 dB and 0.7 dB.At MaxWeak = 10, the measured undetected-error probability is just under 0.1 for both cases.

4. Modern Short Codes

Modern short-block codes include binary and non-binary turbo, LDPC, and polar constructions, with performance shaped by code design, modulation field, and decoding complexity.

Binary Turbo and LDPC Codes: A designed memory-4 turbo code performs close to Gallager’s random-coding bound and nearly 1 dB from the normal approximation at CER = 10^-4.The LTE turbo code loses almost 0.4 dB at the same target CER.
Binary Turbo and LDPC Codes: ARA codes perform close to the LTE turbo code at (128, 64), but exhibit an error floor below CER = 10^-5.
Binary Turbo and LDPC Codes: For (128, 64) binary codes, the 5G NR LDPC construction based on BG 2 slightly outperforms ARA, while BG 1 suffers from poor minimum distance.BG 2 targets smaller blocklengths and lower rates; BG 1 is optimized for larger blocklengths and higher rates.
Binary Turbo and LDPC Codes: Applying OSD after BP improves regular-LDPC performance by around 1 dB at CER ≈10^-4, while bit flipping gains more than 0.5 dB at CER ≈10^-5.The OSD gain decreases to 0.5 dB at CER ≈10^-5.
Non-Binary Turbo and LDPC Codes: Over F256, (128, 64) non-binary turbo and LDPC codes perform almost identically down to very low error rates and nearly match the random-coding bound.Applying OSD to the binary image of the non-binary LDPC code gains 0.5 dB over BP decoding and approaches extended-BCH performance.
Polar Codes: Polar codes use channel polarization and can approach maximum-likelihood performance as the successive-cancellation list size increases.The cited construction is a (128, 64) polar code designed for the bi-AWGN channel.

5. Code Comparison: Examples

The comparisons show that several short-block code constructions approach finite-length bounds, while performance depends on blocklength, decoding complexity, modulation, and shaping.

5.1. Very Short Codes: The (128, 64) comparisons show BG2 5G-NR LDPC codes outperforming ARA, while non-binary LDPC, polar concatenation, and turbo codes provide stronger alternatives.The CCSDS LDPC reference performs poorly in coding gain, although its distance properties can help at CER ≈10^-6.
5.2. Moderate-length Codes: At n = 512 and rate 1/2, polar coding with list size 32 is only marginally better than binary LDPC and turbo codes, whereas list size 1024 is needed to approach finite-length bounds.Tail-biting convolutional codes remain far from the bounds even with memory 14 in this setting.
5.3. Short Codes in Coded Modulation Schemes: The coded-modulation comparisons use 64-QAM at spectral efficiency 3.0 bpcu, corresponding to 192 coded bits over 32 channel uses.The study contrasts uniform signaling with probabilistic shaping.
5.3. Short Codes in Coded Modulation Schemes: For 64-QAM at spectral efficiency 3.0 bpcu and 32 channel uses, the non-binary LDPC code has a gap of about 0.4 dB to the RCB at CER = 10^-4.The comparison uses uniform signaling and includes binary and non-binary coded-modulation schemes.
5.3. Short Codes in Coded Modulation Schemes: PAS with SMDM improves power efficiency over CCDM by 0.4 dB for binary LDPC and about 0.6 dB for non-binary LDPC at the stated operating conditions.The target spectral efficiency is 3.0 bits per channel use; SMDM is designed for favorable finite-blocklength behavior.

6. Conclusions

The paper concludes that short-block transmission offers many efficient coding options, but important design challenges remain for error detection, unknown channel states, and feedback-assisted variable-length coding.

6. Conclusions: The review finds a wide spectrum of short-block code and decoder solutions whose performance is compared with tight information-theoretic bounds.The comparison covers code constructions tailored to short information blocks.
6. Conclusions: Incomplete decoders can detect decoding failures, but critical applications may require very low undetected error rates and therefore additional error-detection mechanisms.Outer error-detection codes may impose unacceptable overhead in short blocks; post-decoding threshold tests are presented as an alternative.
6. Conclusions: Coding for fading channels with unknown state and no channel-state information at either endpoint remains open because large pilot fields cause considerable short-block rate losses.The paper suggests jointly performing channel estimation and decoding in this setting.
6. Conclusions: The review focuses on fixed-length coding, while variable-length schemes with ACK/NACK feedback have less-tight finite-blocklength bounds and an unexplored overall design space.Feedback signaling consumes channel uses that would otherwise carry coded bits.