The impressive performance of Turbo Codes with iterative decoding has triggered in the last decade an extensive research addressing their use in practical applications. Today, Turbo Codes have already abandoned the mystical reality of theory and have become an integral part of (or are being discussed for) many actual standards. In spite of the extensive literature on Turbo Codes, little progresses have been made on Turbo Codes employing high-rate constituent codes. For high-rates, state-of-the- art systems are based on the use of punctured codes, which represent a good compromise between performance and decoding complexity. Moreover, with respect to truly high- rate codes, punctured codes yield the advantage of a simpler code search and a high rate versatility.
The aim of this talk is to tackle challenging problems of high-rate codes to provide a unique framework for their practical utilization in powerful concatenated codes structures. In particular, we introduce a new structural model for high rate convolutional encoders facilitating the exhaustive search of very high rate codes that significantly improve punctured codes of the same rate/complexity, and describe a new technique to provide to truly high-rate codes the same rate versatility of punctured codes. We also give an overview of iterative decoding of Turbo Codes, and show that a proper modification of the soft information exchanged in the iterative decoding process makes the decoding algorithm based on the dual code recently proposed to efficiently decode high-rate codes, perfectly equivalent to the SISO algorithm of the original code. As an important result, both the original code and its dual can be decoded working on the same trellis, provided that the input and output metrics are suitably modified.
Seminar outline compiled by Antonio San Martino Pace
Turbo Codes Overview
From the first primitive communications systems, the most
prevalent efforts of the research community have been
aimed at seeking for improving transmission reliability
Transmitting at High power
Using larger bandwidth than strictly necessary.
Shannon’s Channel Coding Theorem:
There exists a channel coding scheme which allows to
achieve arbitrarily reliable transmission as long as the
code rate does not exceed the channel capacity.
Channel coding provides the desired reliability by adding
structured redundancy to the transmitted information,
which can be used at the receiver side to correct some of the
errors introduced by the channel.
Channel coding is an essential part of almost all digital
communication systems.
In future communication systems the demand for efficient
and powerful encoding/ decoding techniques will even
increase.
Seminar outline compiled by Eva Rodríguez
Turbo Codes
Turbo Codes are a class of error correcting codes introduced in 1993 by Berrou
that come closer to approaching Shannon's limit than any other class of error
correcting codes. The Shannon's Channel Coding Theorem explains that exists
a channel coding scheme which allows to achieve arbitrarily reliable transmission
as long as the code rate does not exceed the channel capacity.
The basic properties of Turbo Coder are: its code structure formed by two constituent
convolutional encoders concatenated in parallel through a pseudo-random interleaver.
A decoding strategy based on the exchange of soft information between SISO component
decoders in an iterative fashion. Decoding is split in two steps in correspondence
with the two encoding stages.
After a brief description of Turbo Codes, the coding and decoding dilemmas
and possible solutions to them were presented.
The Coding dilemma is related to the large block-length random codes, sowed
by Shannon, that achieve channel capacity. But they must have an structure that
permits decoding with reasonable complexity and that codes with structure don't
perform as well as random codes. The solution proposed was to make the code
appear random, while maintaining enough structure to permit decoding. This can
be accomplished adding a pseudo-random interleaver because of turbo codes possess
random-like properties and if the interleaving pattern is known, decoding is
possible.
The decoding dilemma is related with the difficulty to find codes that can be
feasibly decoded at rates close to the Shannon limit. The problem lies in the
fact that while encoding is in general a rather simple task, the computational
complexity of optimal ML decoding increases exponentially with the block size,
and thus becomes unmanageable. Therefore, the most prevalent research efforts
have been focused on designing powerful codes whose structures permit near maximum
likelihood decoding by breaking the decoding process into simpler steps, thus
reducing the computational complexity.
Figure below shows two encoders that share the same sequence (u). The
Upper encoder directly encodes u and lower encoder is fed with a permuted
version of u. The function of the interleaver is to permute low weight
code words in one encoder into high weight code words for the other encoder.
Iterative Decoding: the SISO algorithm
In Iterative Decoding, decoding is broken into the cascade of two simpler decoders,
decoders exchange soft information on their decoding results in an iterative
fashion, cooperating in finding the correct information word. The input bits
to the individual encoders are decoded separately using a soft-input soft-output
(SISO) APP decoding algorithm. Therefore, the reliability of the estimate increases
with the number of iterations.
The SISO decoder has as a inputs a priori values for all information bits and
soft channel output for all code bits: and as outputs extrinsic values for all
information bits and a posteriori values for all information bits.
The optimum SISO component decoder employs the MAP principle to compute the
a posteriori L-value of a symbol u based on the entire received vector y.
The simplest algorithm to compute the a posteriori L-values was proposed by Bahl, Cocke, Jelinek, and Raviv, BCJR algorithm that works for encoders represented in their trellis form.
High-rate Turbo Codes
Currently, High-rate codes are used in several applications, like fiber optics,
magnetic recording, digital video broadcasting, etc.
Traditionally, algebraic block codes have been preferred for very high coding
rates because of the better performance/complexity comparison with respect to
convolutional codes. Indeed, to keep the decoding complexity reasonably low
for high-rate convolutional codes, one needs to resort to punctured codes, which
become rather weak in terms of distance spectrum for the heavy puncturing required
to get very high rates. On the other hand, punctured convolutional codes yield
the advantage of flexibility, i.e., they offer a wide range of code rates without
modifying the co-decoding algorithm, which remains essentially the same needed
to decode the rate-1=2 mother code.
With the advent of concatenated codes with interleavers (or turbo-like codes),
hard-in hard-out and soft-in hard-out decoding algorithms must be replaced by
SISO symbol decoding algorithms to be embedded into the iterative decoding strategies
adopted for those codes. This has increased the interest for high-rate convolutional
codes, since the trellis regularity of convolutional codes makes a posteriori
probability (APP) SISO algorithms more attractive. Still, the trellis complexity
of high-rate (n; n-1) convolutional codes prevents from applying the SISO algorithms
directly to the original trellis. In those cases, a drastic simplification stems
from the use of algorithms working on the trellis of the dual code, or syndrome-decoding
algorithms. Another advantage of punctured convolutional codes lies in the easiness
in searching for optimum puncturing patterns, with respect to the high complexity
of exhaustive searches for optimum high-rate convolutional codes.
In this correspondence, we address several aspects related to high-rate convolutional
codes like the search for "optimum" codes, The decoding algorithm
based on the dual code trellis, and its additive form, An inverse puncturing
technique that adds to the newly found codes the same versatility of punctured
convolutional codes and a new trellis termination method for high-rate convolutional
codes.
Encoder properties
An (n; k; v) convolutional encoder can be described by a trellis diagram
formed by repeated copies of a trellis section, consisting of a set of 2^v
initial states and 2^v final states. Each initial state is connected
to 2^k final states by oriented arrows, called edges. In a trellis section there
can be multiple (parallel) edges connecting two states.
To search for good high-rate (n; n-1) convolutional codes, The basic idea is
to build an overall convolutional encoder composed of two constituent encoders:
a block encoder associated to the parallel edges, and a low-to-moderate rate
convolutional encoder that defines the dynamical part of the trellis.
To design the encoder, first the relationship between u and c can also be expressed
in a compact form as, c(D)=u(D)G(D), where G(D) is the polynomial generator
matrix.
The high complexity of ML decoding or MAP decoding algorithm for high-rate codes
requires a decoding algorithm working on the dual code, which, in turn, requires
the encoder to be in systematic form. The overall systematic encoder is non
systematic, then we must obtain the equivalent systematic encoder from G(D)
by linearly combining matrix rows.
Decoding high-rates codes
A straightforward application of MAP decoding to high-rate codes becomes rapidly
impractical as the code rate increases. New decoding algorithms are needed to
perform efficient decoding of high-rate codes. Hartmann and Rudolph showed that
it is possible to derive the MAP decision for a code working on its dual. The
advantage of this approach is a reduction of the decoding complexity when k>n-k.
Dual Code
A convolutional code G(D) can also be characterized in terms of its parity check
matrix H(D). A parity-check matrix of a rate-k/n convolutional code is an (n-k)*n
matrix:
where H(D) generates an (n,n-k) convolutional code.
Decoding high-rate convolutional codes: Dual-SISO
algorithm
A straightforward application of APP decoding to high-rate codes becomes quickly
impractical as the coding rate increases, since its complexity increases with
the number of transitions.
They rederive the APP decoding algorithm in the dual domain to show that with
a proper modification of the bit soft information, it is perfectly equal to
the one pertaining to the original code. Therefore, their main contribution
is the derivation of the dual algorithm in the log domain, completing the correspondence
between the decoding algorithm in the original and dual domains.
References
Find more information in the paper: Design and Decoding of Optimal High-rate Convolutional Codes