Turbo Decoding with Tailbiting Codes

A scientific breakthrough in error-correction coding for communications and storage of digital data was reported by a French research team in 1993: they showed that it is possible to come very close to the Shannon limit of reliable communications by using iterative decoding of parallel concatenated convolutional codes generated by feedback encoders. As one part of the decoder’s output is fed back to its input for the next iteration step, these codes were dubbed “turbo codes” in an allusion to the turbo engine. Since the announcement of this result, many researchers have extended this principle to numerous other forms of code concatenations.

Christian Bettstetter worked in this field of communication theory at TU München and as part of a research visit at the University of Notre Dame, IN, USA, early in his career in the late 1990s. He investigated the parallel concatenation of tailbiting codes and its iterative (turbo) decoding. He explains: “A tailbiting code is generated by a convolutional encoder. Usually, such an encoder starts in a predefined state with all memory elements filled with zero bits. The basic idea behind tailbiting is that the encoding process may also start in a different state, and it must then be controlled in a way that it finishes the encoding process in the same state.” Tailbiting codes have the advantage that the termination of the code, which is necessary for convolutional codes to achieve a good performance, can be omitted. Thus, the code does not suffer from the rate loss due to termination, which is especially interesting for short codes. Tailbiting basically converts a convolutional code into a block code.

A tailbiting trellis

A tailbiting trellis

Together with his advisors Christian Weiß and Sven Riedel and with Daniel J. Costello from Notre Dame, the question as how to choose good tailbiting codes for turbo decoding was addressed. A methodology to answer this question was proposed that uses the two-dimensional weight distributions of tailbiting codes. “Encoders should be designed such that they map low-weight information words to high-weight codewords. All minimum-weight codewords of the component code should be generated by information words of high weight. If these criteria are fulfilled, a parallel concatenated block code with high minimum distance and a small number of low-weight codewords results.” Using this method, the team found tailbiting codes that are well suited for parallel concatenation and studied their error correction capabilities by extensive simulations. As a final result, they tabulated well-suited tailbiting codes of different rate, length, and complexity.