New deterministic interleaver designs for turbo codes

It is well known that an interleaver with random properties, quite often ge nerated by pseudo-random algorithms, is one of the essential building block s of turbo codes. However, randomly generated interleavers have two major d rawbacks: lack of an adequate analysis that guarantees their performance an d lack of a compact representation that leads to a simple implementation. I n this paper we present several new classes of deterministic interleavers o f length N, with construction complexity O(N), that permute a sequence of b its with nearly the same statistical distribution as a random interleaver a nd perform as well as or better than the average of a set of random interle avers, The new classes of deterministic interleavers have a very simple rep resentation based on quadratic congruences and hence have a structure that allows the possibility of analysis as well as a straightforward implementat ion. Using the new interleavers, a turbo code of length 16384 that is only 0.7 dB away from capacy at a bit-error rate (BER) of 10(-5) is constructed. We also generalize the theory of previously known deterministic interleave rs that are based on block interleavers, and we apply this theory to the co nstruction of a nonrandom turbo code of length 16384 with a very regular st ructure whose performance is only 1.1 dB away from capacity at a BER of 10( -5).