### Topics

### features

### Publications

### Issue Archive

# Efficient Algorithmic Interleaver for Turbo Decoder

- Wednesday, 23 December 2009

### Permutations are computed when needed, rather than stored in lookup tables.

An efficient bit-interleaving algorithm for a turbo encoder differs from prior such algorithms in that it does not require memory to store permutation mappings and can work with constituent decoders that produce multiple bit reliabilities per decoding stage. The algorithm can be implemented in hardware: The original version of the algorithm applies to a serially concatenated pulse position modulation (SCPPM) decoder that has been implemented in a field-programmable gate array (FPGA). The specific decoder can perform within 1 dB of the Shannon capacity on a Poisson channel and is suitable for use in optical data communications at megabit-per-second speeds. A bit interleaver is an essential component of any turbolike decoder, and the bit interleaver embodied in the present algorithm is essential for obtaining the capacity approaching performance of the specific SCPPM decoder and the affected SCPPM scheme. The algorithm can also be adapted to turbo decoders for modulation/coding schemes other than SCPPM.

The development of the present algorithm addresses two issues that arise in the design and operation of turbo decoders:

- An interleaver permutes bit reliabilities that are passed
between the constituent decoders. A permutation involves
mapping a reliability at a given bit position,
*i*, to a different bit position,*j*. In a turbo coder or decoder of prior design, the mapping from all addresses*i*to all addresses*j*is typically stored in an address-permutation table (a lookup table), to which the interleaver gains access. Additional memory circuitry is needed to store the address-permutation table. - In a turbo decoder for non-binary symbols (for example, as in SCPPM), a large latency may be incurred in the operation of the interleaver. The trellis that characterizes the non-binary code contains parallel transitions, and decoding of each trellis stage produces multiple bit reliabilities. It therefore becomes desirable to devise an interleaver having a capability for parallelism in order to avoid unnecessary latency. Heretofore, it has been possible to interleave or deinterleave only one bit per hardware clock cycle. It would be desirable to interleave or deinterleave an entire code symbol per hardware clock cycle.

To eliminate the need for additional memory circuitry to store
the address-permutation table, the present algorithm computes
the next bit position, *j*, as a function (specifically, a quadratic polynomial)
of the current bit position, *i*. Moreover, the polynomial
has a recursive property, such that the current address can be computed
from previous addresses. Of course, additional logic circuitry
is needed to perform this computation. It has been found that
in the trade-off between logic and memory circuitry, this choice of
computation over memory results in an overall net gain.

The solution of the latency problem involves partitioning of the
interleaver memory (not to be confused with the additional memory needed for the address-permutation
table in a decoder of prior design) into m
submodules corresponding to m bits per
symbol in the affected SCPPM scheme.
The m bits produced by a constituent
decoder in one decoding stage are written
simultaneously into these *m* distinct memory
submodules. Subsequently, bits are read
simultaneously from the *m* submodules.

*This work was done by Michael Cheng, Bruce
Moision, and Jon Hamkins of Caltech and
Michael Nakashima of SkillStorm Inc. for
NASA’s Jet Propulsion Laboratory. For more
information, contact This email address is being protected from spambots. You need JavaScript enabled to view it..
*

*The software used in this innovation is available
for commercial licensing. Please contact Karina
Edmonds of the California Institute of Technology
at (626) 395-2322. Refer to NPO-44342. *

### White Papers

| ||||||