Efficient Algorithmic Interleaver for Turbo Decoder

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 e-mail 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.