Code Design for Short Blocks: A Survey
---
paper_title: List decoding of polar codes

paper_content:

We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Thus it appears that the proposed list decoder bridges the gap between successive-cancellation and maximum-likelihood decoding of polar codes. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L “best” paths. In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, straightforward implementation still requires O(L · n2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L · n log n) time and O(L · n) space.
---
paper_title: Soft decision decoding of linear block codes based on ordered statistics

paper_content:

Soft decision decoding of linear block codes has been investigated for many years and several decoding schemes based on the reordering of the received symbols according to their reliability have been proposed. In this paper, we derive the ordered statistics of the noise after ordering and develop a simple algorithm based on these ordered statistics. This algorithm consists of successive reprocessing stages. For each stage, the error performance can be evaluated. For short codes of lengths up to 64, the optimum bit error performance is achieved in two stages of reprocessing, with at most a computation complexity of o(K/sup 2/) constructed codewords. For longer codes three or more reprocessing stages are required to achieve optimum decoding. The proposed algorithm applies to any linear block code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents the overflow problem at low SNR.<<ETX>>
---
paper_title: Reliability Options for Data Communications in the Future Deep-Space Missions

paper_content:

Availability of higher capacity for both uplinks and downlinks is expected in the future deep-space missions on Mars, thus enabling a large range of services that could eventually support human remote operations. The provisioning for deep-space links offering data rate up to several megabits per second will be a crucial element to allow new services for the space domain along with the common telecommand and telemetry services with enhanced communication capabilities. On the other hand, also the geometry proper of this scenario with orbiting and landed elements sharing only partial visibility among them and towards Earth provides another challenge. This paper surveys the reliability options that are available in the Consultative Committee for Space Data Systems (CCSDS) Protocol Stack for application in the deep-space missions. In particular, the solutions implemented from the physical up to the application layer are illustrated in terms of channel coding and Automatic Retransmission reQuest (ARQ) schemes. Finally, advanced reliability strategies possibly applicable in next-generation deep-space missions are explored as well.
---
paper_title: Error Free Coding

paper_content:

An adap~ive ~ransform coding technique followed bya OPCM technique is employed ~o code mul~ispectral data. A method of ins~antaneous expansion of quantization levels by reserving two oodewords in the codebook ~ perform a folding over in quantization is implemented for data with incomplete knowledge of probability density funotion. Controlled redundancy is inserted periodioally as fixed length codewords into the bit strinq of data paoked with variable lenqth codes to facilitate fast retrieval and to detect errors. preliminary results of several sets of data from the ERTS-l data frame and the ERIM· airoraft data frame showed that an error· free reconstruction of the data can be achieved with four bits per picture element or less. 1 The work reported in this paper was sponsored by the National Aeronautics and Space Administration (NASA) under Grant Number NGL 15-005-112 at the Laboratory for Applications of Remote Sensinq (LARS) and under Grant Number NGR 15-005-152. Paper was presented at the 1973 Picture Coding Symposium, January 1973, University of Southern California. 2 J. R. Duan is a graduate student in Electrical Enqineering and P. A. Wintz is Professor of Electrical Enqineerinq, both at Purdue University. • Earth Resources Institute of Michigan. Formerly: University of Michigan/WRL.
---
paper_title: Interleaver design for short block length turbo codes

paper_content:

The performance of a turbo code with short block length depends critically on the interleaver design. There are two major criteria in the design of an interleaver: the distance spectrum of the code and the correlation between the information input data and the soft output of each decoder corresponding to its parity bits. This paper describes a new interleaver design based on these two criteria. Simulation results compare the new interleaver design with different existing interleavers.
---
paper_title: Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs

paper_content:

This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.
---
paper_title: Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC

paper_content:

Convolutional LDPC ensembles, introduced by Felstrom and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing as a function of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism which explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum-a-posteriori (MAP) threshold of the underlying ensemble. For this reason we call this phenomenon “threshold saturation”. This gives an entirely new way of approaching capacity. One significant advantage of such a construction is that one can create capacity-approaching ensembles with an error correcting radius which is increasing in the blocklength. Our proof makes use of the area theorem of the BP-EXIT curve and the connection between the MAP and BP threshold recently pointed out by Measson, Montanari, Richardson, and Urbanke. Although we prove the connection between the MAP and the BP threshold only for a very specific ensemble and only for the binary erasure channel, empirically the same statement holds for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar collapse of thresholds occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms as well as to new techniques for analysis.
---
paper_title: Information Theory and Reliable Communication

paper_content:

Communication Systems and Information Theory. A Measure of Information. Coding for Discrete Sources. Discrete Memoryless Channels and Capacity. The Noisy-Channel Coding Theorem. Techniques for Coding and Decoding. Memoryless Channels with Discrete Time. Waveform Channels. Source Coding with a Fidelity Criterion. Index.
---
paper_title: Short Protograph-Based LDPC Codes

paper_content:

In this paper we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.
---
paper_title: Multiple-Bases Belief-Propagation Decoding of High-Density Cyclic Codes

paper_content:

We introduce a new method for decoding short and moderate-length linear block codes with dense parity check matrix representations of cyclic form. This approach is termed multiple-bases belief-propagation. The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard belief-propagation decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the multiple-bases belief propagation decoding performance can be shown to closely follow that of the maximum-likelihood decoder.
---
paper_title: List decoding of polar codes

paper_content:

We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Thus it appears that the proposed list decoder bridges the gap between successive-cancellation and maximum-likelihood decoding of polar codes. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L “best” paths. In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, straightforward implementation still requires O(L · n2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L · n log n) time and O(L · n) space.
---
paper_title: Soft decision decoding of linear block codes based on ordered statistics

paper_content:

Soft decision decoding of linear block codes has been investigated for many years and several decoding schemes based on the reordering of the received symbols according to their reliability have been proposed. In this paper, we derive the ordered statistics of the noise after ordering and develop a simple algorithm based on these ordered statistics. This algorithm consists of successive reprocessing stages. For each stage, the error performance can be evaluated. For short codes of lengths up to 64, the optimum bit error performance is achieved in two stages of reprocessing, with at most a computation complexity of o(K/sup 2/) constructed codewords. For longer codes three or more reprocessing stages are required to achieve optimum decoding. The proposed algorithm applies to any linear block code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents the overflow problem at low SNR.<<ETX>>
---
paper_title: Advanced channel coding for space mission telecommand links

paper_content:

We investigate and compare different options for updating the error correcting code currently used in space mission telecommand links. Taking as a reference the solutions recently emerged as the most promising ones, based on Low-Density Parity-Check codes, we explore the behavior of alternative schemes, based on parallel concatenated turbo codes and soft-decision decoded BCH codes. Our analysis shows that these further options can offer similar or even better performance.
---
paper_title: Multiple-Bases Belief-Propagation for Decoding of Short Block Codes

paper_content:

A novel soft-decoding method for algebraic block codes is presented. The algorithm is designed for soft-decision decoding and is based on belief-propagation (BP) decoding using multiple bases of the dual code. Compared to other approaches for high-performance BP decoding, this method is conceptually simple and does not change at each stage of the decoding process. With its multiple BP decoders the proposed scheme achieves the performance of a standard BP algorithm with a significantly lower number of iterations per decoder realization. By this means the data delay introduced by decoding is reduced. Moreover, a significant improvement in decoding performance is achieved while keeping the data delay small. It is shown that for selected codes the proposed scheme approaches near maximum likelihood (ML) performance for very small data processing delays.
---
paper_title: Two decoding algorithms for tailbiting codes

paper_content:

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.
---
paper_title: Error Free Coding

paper_content:

An adap~ive ~ransform coding technique followed bya OPCM technique is employed ~o code mul~ispectral data. A method of ins~antaneous expansion of quantization levels by reserving two oodewords in the codebook ~ perform a folding over in quantization is implemented for data with incomplete knowledge of probability density funotion. Controlled redundancy is inserted periodioally as fixed length codewords into the bit strinq of data paoked with variable lenqth codes to facilitate fast retrieval and to detect errors. preliminary results of several sets of data from the ERTS-l data frame and the ERIM· airoraft data frame showed that an error· free reconstruction of the data can be achieved with four bits per picture element or less. 1 The work reported in this paper was sponsored by the National Aeronautics and Space Administration (NASA) under Grant Number NGL 15-005-112 at the Laboratory for Applications of Remote Sensinq (LARS) and under Grant Number NGR 15-005-152. Paper was presented at the 1973 Picture Coding Symposium, January 1973, University of Southern California. 2 J. R. Duan is a graduate student in Electrical Enqineering and P. A. Wintz is Professor of Electrical Enqineerinq, both at Purdue University. • Earth Resources Institute of Michigan. Formerly: University of Michigan/WRL.
---
paper_title: Optimal and near-optimal encoders for short and moderate-length tail-biting trellises

paper_content:

The results of an extensive search for short and moderate length polynomial convolutional encoders for time-invariant tail-biting representations of block codes at rates R=1/4, 1/3, 1/2, and 2/3 are reported. The tail-biting representations found are typically as good as the best known block codes.
---
paper_title: An improved sphere-packing bound for finite-length codes over symmetric memoryless channels

paper_content:

We present an improved sphere-packing (ISP) bound for finite-length error-correcting codes whose transmission takes place over symmetric memoryless channels, and the codes are decoded by an arbitrary list decoder. Some applications of the ISP bound are also exemplified. Its tightness under maximum-likelihood (ML) decoding is studied by comparing the ISP bound to previously reported upper and lower bounds on the ML decoding error probability, and also to computer simulations of iteratively decoded turbo-like codes.
---
paper_title: Fundamentals of Convolutional Coding

paper_content:

From the Publisher: ::: Convolutional codes, among the main error control codes, are routinely used in applications for mobile telephony, satellite communications, and voice-band modems. Written by two leading authorities in coding and information theory, this book brings you a clear and comprehensive discussion of the basic principles underlying convolutional coding. This book can be used as a textbook for graduate-level electrical engineering students. It will be of key interest to researchers and engineers of wireless and mobile communication, satellite communication, and data communication.
---
paper_title: Channel Coding Rate in the Finite Blocklength Regime

paper_content:

This paper investigates the maximal channel coding rate achievable at a given blocklength and error probability. For general classes of channels new achievability and converse bounds are given, which are tighter than existing bounds for wide ranges of parameters of interest, and lead to tight approximations of the maximal achievable rate for blocklengths n as short as 100. It is also shown analytically that the maximal rate achievable with error probability ? isclosely approximated by C - ?(V/n) Q-1(?) where C is the capacity, V is a characteristic of the channel referred to as channel dispersion , and Q is the complementary Gaussian cumulative distribution function.
---
paper_title: Short Turbo Codes over High Order Fields

paper_content:

Two classes of turbo codes constructed on high-order finite fields are introduced. The codes are derived from a particular protograph sub-ensemble of the (2,3) regular low-density parity-check (LDPC) code ensemble. The first construction results in a parallel concatenation of two non-binary, time-variant accumulators. The second construction consists of the serial concatenation of a non-binary time-variant differentiator with a non-binary time-variant accumulator, and provides a highly structured flexible encoding scheme for (2,4) LDPC codes. A cycle graph representation is also provided. The proposed codes can be decoded efficiently either as LDPC codes (via belief propagation decoding on their bipartite graphs) or as turbo codes (via the forward-backward algorithm applied to the component code trellises) by means of the fast Fourier transform. The proposed codes provide remarkable coding gains (more than 1 dB at a codeword error rate 10-4) over binary LDPC and turbo codes in the moderate-short block length regime.
---
paper_title: Accumulate repeat accumulate codes

paper_content:

In this paper we propose an innovative channel coding scheme called Accumulate Repeat Accumulate codes (ARA). This class of codes can be viewed as serial turbo-like codes, or as a subclass of Low Density Parity Check (LDPC) codes, thus belief propagation can be used for iterative decoding of ARA codes on a graph. The structure of encoder for this class can be viewed as precoded Repeat Accumulate (RA) code or as preceded Irregular Repeat Accumulate (IRA) code, where simply an accumulator is chosen as the precoder. Thus ARA codes have simple, and very fast encoder structure when they representing LDPC codes. Based on density evolution for LDPC codes through some examples for ARA codes, we show that for maximum variable node degree 5 a minimum bit SNR as low as 0.08 dB from channel capacity for rate 1/2 can be achieved as the block size goes to infinity. Thus based on fixed low maximum variable node degree, its threshold outperforms not only the RA and IRA codes but also the best known unstructured irregular LDPC codes with the same maximum node degree. Furthermore by puncturing the accumulators any desired high rate codes close to code rate 1 can be obtained with thresholds that stay close to the channel capacity thresholds uniformly. Iterative decoding simulation results are provided. The ARA codes also have projected graph or protograph representation, that allows for high speed decoder implementation.
---
paper_title: On Dualizing Trellis-Based APP Decoding Algorithms

paper_content:

The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.
---
paper_title: Codes on high-order fields for the CCSDS next generation uplink

paper_content:

Recently, short binary and non-binary iteratively-decodable codes have been proposed within the Next Generation Uplink (NGU) working group (WG) of the Consultative Committee for Space Data Systems (CCSDS). The NGU WG targets the design of an enhanced uplink mainly for telecommand with the aim of updating the current uplink standard that employs a short (63, 56) BCH code to protect the telecommand messages. The proposed non-binary turbo/LDPC codes attain large coding gains over the standardized BCH codes, but also over their binary turbo/LDPC counterparts (up to 1.5 dB of coding gain for information blocks of 64 bits). This paper overviews the proposed non-binary code construction, illustrating the potential of non-binary turbo/LDPC codes in the short block length regime. The impact of the proposed solution at system level is investigated, together with its integration in the CCSDS protocol stack.
---
paper_title: Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels. I

paper_content:

New lower bounds are presented for the minimum error probability that can be achieved through the use of block coding on noisy discrete memoryless channels. Like previous upper bounds, these lower bounds decrease exponentially with the block length N . The coefficient of N in the exponent is a convex function of the rate. From a certain rate of transmission up to channel capacity, the exponents of the upper and lower bounds coincide. Below this particular rate, the exponents of the upper and lower bounds differ, although they approach the same limit as the rate approaches zero. Examples are given and various incidental results and techniques relating to coding theory are developed. The paper is presented in two parts: the first, appearing here, summarizes the major results and treats the case of high transmission rates in detail; the second, to appear in the subsequent issue, treats the case of low transmission rates.
---
paper_title: Low-density parity-check (LDPC) codes constructed from protographs

paper_content:

We introduce a new class of low-density parity-check (LDPC) codes constructed from a template called a protograph. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. We apply standard density evolution techniques to predict the performance of large protograph codes. Finally, we use a randomized search algorithm to find good protographs.
---
paper_title: Fast Decoding Algorithm for LDPC over GF(2q)

paper_content:

In this paper, we present a modification of Belief Propagation that enable us to decode LDPC codes defined on high order Galois fields with a complexity that scales as ploga(p), p being the field order. With this low complexity algorithm, we are able to decode GF(2q) LDPC codes up to a field order value of 256. We show by simulation that ultra-sparse regular LDPC codes in GF(64) and GF(256) exhibit very good performance.
---
paper_title: Box and match techniques applied to soft-decision decoding

paper_content:

In this paper, we improve the ordered statistics decoding algorithm by using matching techniques. This allows us: to reduce the worst case complexity of decoding (the error performance being fixed) or to improve the error performance (for a same complexity); to reduce the ratio between average complexity and worst case complexity; to achieve practically optimal decoding of rate-1/2 codes of lengths up to 128 (rate-1/2 codes are a traditional benchmark, for coding rates different from 1/2, the decoding is easier); to achieve near-optimal decoding of a rate-1/2 code of length 192, which could never be performed before.
---
paper_title: Performance Bounds for Erasure, List, and Decision Feedback Schemes With Linear Block Codes

paper_content:

A message independence property and some new performance upper bounds are derived in this work for erasure, list, and decision-feedback schemes with linear block codes transmitted over memoryless symmetric channels. Similar to the classical work of Forney, this work is focused on the derivation of some Gallager-type bounds on the achievable tradeoffs for these coding schemes, where the main novelty is the suitability of the bounds for both random and structured linear block codes (or code ensembles). The bounds are applicable to finite-length codes and to the asymptotic case of infinite block length, and they are applied to low-density parity-check code ensembles.
---
paper_title: Bounded angle iterative decoding of LDPC codes

paper_content:

A modification to the usual iterative decoding algorithm for LDPC codes, called bounded angle iterative (BA-I) decoding, is introduced. The modified decoder erases codewords detected during iterations that fall outside a maximum decoding angle with respect to the received observation. The new algorithm is applicable in scenarios that demand a very low undetected error rate but require short LDPC codes that are too vulnerable to undetected errors when the usual iterative decoding algorithm is used. BA-I decoding provides a means of reducing the maximum undetected error rate for short LDPC codes significantly, by incorporating a simple extra condition into the iterative decoder structure without redesigning the code. The reduction in undetected error rate comes at a price of increasing the threshold signal-to-noise ratio (SNR) required for achieving a good overall error rate, but this increase in channel threshold can be minimized by allowing the decoderpsilas maximum decoding angle to vary with SNR.
---
paper_title: Exponential error bounds for erasure, list, and decision feedback schemes

paper_content:

By an extension of Gallager's bounding methods, exponential error bounds applicable to coding schemes involving erasures, variable-size lists, and decision feedback are obtained. The bounds are everywhere the tightest known.
---
paper_title: Reliability-output Decoding of Tail-biting Convolutional Codes

paper_content:

We present extensions to Raghavan and Baum's reliability-output Viterbi algorithm (ROVA) to accommodate tail-biting convolutional codes. These tail-biting reliability-output algorithms compute the exact word-error probability of the decoded codeword after first calculating the posterior probability of the decoded tail-biting codeword's starting state. One approach employs a state-estimation algorithm that selects the maximum a posteriori state based on the posterior distribution of the starting states. Another approach is an approximation to the exact tail-biting ROVA that estimates the word-error probability. A comparison of the computational complexity of each approach is discussed in detail. The presented reliability-output algorithms apply to both feedforward and feedback tail-biting convolutional encoders. These tail-biting reliability-output algorithms are suitable for use in reliability-based retransmission schemes with short blocklengths, in which terminated convolutional codes would introduce rate loss.
---

Title: Code Design for Short Blocks: A Survey

Section 1: Introduction
Description 1: Overview of the research on capacity-approaching error correcting codes with a focus on short and medium-length linear block codes and their applications in modern communication systems.

Section 2: A Case Study
Description 2: Provide an exemplary comparison of short codes, focusing on codes with block length n = 128 and code dimension k = 64, and discuss their performance metrics.

Section 3: The Elephant in the Room: Complexity
Description 3: Discuss the complexity aspects of decoding algorithms used for short block codes and provide qualitative remarks on their algorithmic complexity.

Section 4: Error Detection
Description 4: Outline the error detection capabilities of different decoding algorithms and the importance of low undetected error rates in critical applications.

Section 5: Conclusions
Description 5: Summarize the recent efforts in the design and analysis of efficient error-correcting codes for short block lengths, and highlight trade-offs between coding gain and decoding complexity.