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.