Turbo code interleaver with near optimal performance

A method of interleaving blocks of indexed data, the blocks having a variable length, the method including the steps of:

• 1) providing a family of basic Interleavers comprising “two-dimensional permutations” including the step of computing the “two-dimensional permutations” further comprising the steps of:
• writing the indexed data into an Interleaver matrix having one or more rows R in each of two dimensions;
• permuting the indexed data in one or more rows R in at least one of the two dimensions, to produce “constituent permutations”, said constituent permutations possibly being different from one row to another row in each of the two dimensions, wherein the constituent permutations are pseudo-random permutations described by mathematical operations involving a limited number of parameters, wherein an amount of storage required for storing the limited number of parameters is less than another amount of storage required for storing a vector representation of permuted indices of the constituent permutations;
• reading out the indexed data from the Interleaver matrix;
• 2) selecting one of the basic Interleavers for use in encoding based upon a desired Interleaver length L;
• 3) adapting the selected basic Interleaver to produce an Interleaver having the desired Interleaver length L;
• wherein the step of selecting includes:
• identifying a group of the basic Interleavers having a length greater than or equal to the desired Interleaver length L;
• selecting one of the basic Interleavers having a length which is smallest among the identified group of the basic Interleavers;
• wherein the steps of adapting the selected basic Interleaver includes:
• deleting indexed data having indices higher than required for a permutation of length L;
• 4) providing an Interleaver device for interleaving blocks of indexed data, the Interleaver device further comprising a memory device for storing descriptions of the basic Interleavers;
• and
• 5) storing the descriptions of the basic Interleavers in the memory device.

A system for interleaving and turbo encoding blocks of indexed data, having indices, the blocks having a varying length, the system comprising:

• a parallel concatenation of two or more constituent encoders for recursive convolutional codes having a recursion period p;
• and
• an Interleaver device coupled to the parallel concatenation of the two or more constituent encoders for performing the steps of:
• accessing stored descriptions of basic Interleavers, the basic Interleavers comprising a family of one or more permutations of the indexed data and having a variable length;
• identifying a group of the basic Interleavers having a length greater than or equal to a desired Interleaver length L;
• selecting one of the basic Interleavers having a length which is smallest among the group of the basic interleaves;
• and
• adapting the selected one of the basic Interleavers to produce an Interleaver having the desired Interleaver length L.