Turbo code interleaver with near optimal performance

• US 7,761,750 B2
• Filed: 10/31/2007
• Issued: 07/20/2010
• Est. Priority Date: 08/17/1998
• Status: Expired due to Fees

• Current Assignee: DTVG Licensing, Inc. (AT&T, Inc.)
• Original Assignee: The DIRECTV Group, Inc. (AT&T, Inc.)
• Inventors: Sun, Feng-Wen, Eroz, Mustafa, Hammons, A. Roger Jr.
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/980,916
• Publication Number:
  US 20080059727A1
• Time in Patent Office: 993 Days
• Field of Search: 714/701, 714/755
• US Class Current: 714/701
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/2735 Interleaver using powers of a primitive element, e.g. Galois field [GF] interleaver
• CPC Class Codes: H03M 13/2746 S-random interleaver
• CPC Class Codes: H03M 13/276 Interleaving address generation
• CPC Class Codes: H03M 13/2767 Interleaver wherein the permutation pattern or a portion thereof is stored
• CPC Class Codes: H03M 13/2771 Internal interleaver for turbo codes H03M13/2714 and H03M13/2725 take precedence
• CPC Class Codes: H03M 13/2789 Interleaver providing variable interleaving, e.g. variable block sizes
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding

Abstract

A method of interleaving blocks of indexed data of varying length is disclosed. The method includes the steps of: providing a set of basic Interleavers comprising a family of one or more permutations of the indexed data and having a variable length; selecting one of the basic Interleavers based upon a desired Interleaver length L; and adapting the selected basic Interleaver to produce an Interleaver having the desired Interleaver length L.

Claims

1. A method for constructing an interleaver for interleaving blocks of indexed data having indices, the blocks having a varying length, the method comprising:

determining at least one value based on a desired interleaver size; and

utilizing the determined at least one value to construct an interleaver comprising one or more permutations of the indexed data, wherein constructing the interleaver comprises;

determining a first index according to the at least one value;

comparing the first index to a desired range of the interleaver size, and

constructing the interleaver using the first index if the first index is within the desired range and constructing the interleaver using a second index selected according to the at least one value if the first index is outside the desired range.

2. The method of claim 1, wherein the desired interleaver size is selected among a plurality of interleaver sizes.

3. The method of claim 1, wherein the at least one value is associated with determining an interleaving pattern of the desired interleaver.

4. A method for constructing an interleaver for interleaving blocks of indexed data having indices, the method comprising:

determining at least one value based on a desired interleaver size;

utilizing the determined at least one value to construct an interleaver comprising one or more permutations of the indexed data;

providing a turbo encoder comprising at least two connected constituent encoders; and

interleaving the blocks of indexed data with the turbo encoder.

5. A method of interleaving blocks of indexed data having indices, the blocks having a varying length, the method including the steps of:

providing a set of basic interleavers comprising a family of one or more permutations of the indexed data X(t) and having a variable length;

selecting one of the basic interleavers based upon a desired interleaver length L; and

adapting the selected basic interleaver to produce an interleaver having the desired interleaver length L,

wherein the step of adapting the selected basic interleaver includes deleting indexed data having indices higher than the desired interleaver length L.

6. The method of claim 5, 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; and

selecting one of the basic interleavers having a selected length which is smallest among the identified group of basic interleavers.

7. The method of claim 6, wherein the family of basic interleavers consists of “

two-dimensional permutations” and

further comprising the steps of;

computing the “

two-dimensional permutations”

, including 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 the one or more rows 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; and

reading out the indexed data from the interleaver matrix.

8. The method of claim 7, further including the steps of:

providing an interleaver device for the interleaving blocks of indexed data, the interleaver device further comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

9. The method of claim 8, 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 a totality of permuted indices of the constituent permutations.

10. The method of claim 9, further including the step of:

providing a turbo code encoder comprising two or more constituent code encoders connected together and to the interleaver device; and

turbo encoding the indexed data after the interleaving by the interleaver device of the turbo code encoder.

11. 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; and

an interleaver device coupled to the parallel concatenation of the two or more constituent encoders,

wherein the interleaver device defines a set of basic interleavers comprising a family of one or more permutations of the indexed data X(t) and having a variable length, and

wherein the interleaver device is configured to;

select one of the basic interleavers based upon a desired interleaver length L; and

adapt the selected basic interleaver to produce an interleaver having the desired interleaver length L by deleting indexed data having indices higher than the desired interleaver length L.

12. A method of interleaving blocks of indexed data having indices, the blocks having a varying length, the method including the steps of:

providing a set of basic interleavers comprising a family of one or more permutations of the indexed data X(t) and having a variable length;

selecting one of the basic interleavers based upon a desired interleaver length L; and

adapting the selected basic interleaver to produce an interleaver having the desired interleaver length L,

wherein the step of adapting the selected basic interleaver includes deleting indexed data having indices higher than the desired interleaver length L,

wherein the family of basic interleavers consists of “

two-dimensional permutations” and

the method further comprises the steps of;

computing the “

two-dimensional permutations”

, including 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 the one or more rows 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; and

reading out the indexed data from the interleaver matrix.

13. The method of claim 12, 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; and

selecting one of the basic interleavers having a selected length which is smallest among the identified group of basic interleavers.

14. The method of claim 13, further including the steps of:

providing an interleaver device for the interleaving blocks of indexed data, the interleaver device further comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

15. The method of claim 14, 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 a totality of permuted indices of the constituent permutations.

16. The method of claim 15, further including the step of:

providing a turbo code encoder comprising two or more constituent code encoders connected together and to the interleaver device; and

turbo encoding the indexed data after the interleaving by the interleaver device of the turbo code encoder.

17. 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; and

an interleaver device coupled to the parallel concatenation of the two or more constituent encoders,

wherein the interleaver device defines a set of basic interleavers comprising a family of one or more permutations of the indexed data X(t) and having a variable length, and

wherein the interleaver device is configured to;

select one of the basic interleavers based upon a desired interleaver length L; and

adapt the selected basic interleaver to produce an interleaver having the desired interleaver length L by deleting indexed data having indices higher than the desired interleaver length L,

wherein the family of basic interleavers consists of “

two-dimensional permutations”

, and wherein the interleaver device is further configured to;

compute the “

two-dimensional permutations”

, including;

writing the indexed data into an interleaver matrix having one or more rows R in each of two dimensions;

permuting the indexed data in the one or more rows 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; and

reading out the indexed data from the interleaver matrix.

18. A method of interleaving blocks of indexed data having indices, the blocks having a varying length, the method including the steps of:

providing a set of basic interleavers comprising one or more permutations of the indexed data, each having a variable length;

selecting one of the basic interleavers based upon a desired interleaver length L, wherein the selected interleaver has the shortest length which is greater than or equal to the desired interleaver length; and

adapting the selected basic interleaver to produce a new interleaver having the desired interleaver length L,

wherein the selected basic interleaver defines mappings, each of which is of a position of indexed data to a new mapped position, and

wherein a mapping of the selected basic interleaver is retained if the position of indexed data in the selected basic interleaver is less than L and the mapping is rejected if the position of indexed data in the selected basic interleaver is not less than L.

19. The method of claim 18, wherein the position of indexed data starts from 0.

20. The method of claim 18, wherein the set of basic interleavers comprises two-dimensional permutations and further comprising computing the two-dimensional permutations by:

writing the indexed data into an interleaver matrix having one or more rows in each of two dimensions;

permuting the indexed data in the one or more rows in at least one of the two dimensions to produce constituent permutations; and

reading out the indexed data from the interleaver matrix.

21. The method of claim 20, further comprising:

providing an interleaver device for interleaving blocks of indexed data, the interleaver device comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

22. The method of claim 21, 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 a totality of permuted indices of the constituent permutations.

23. The method of claim 20, wherein said constituent permutations are different from one row to another row in each of the two dimensions.

24. The method of claim 23, further comprising:

providing an interleaver device for interleaving the blocks of indexed data, the interleaver device comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

25. The method of claim 24, 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 a totality of permuted indices of the constituent permutations.

26. 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; 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 each 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, the selected interleaver having the shortest length which is greater than or equal to the desired interleaver length; and

adapting the selected one of the basic interleavers to produce a new interleaver having the desired interleaver length L,

wherein the selected basic interleaver defines mappings of a position of indexed data to a new position,

wherein for each mapping, the mapping of the selected basic interleaver is retained if the indexed position in the selected basic interleaver is less than L, otherwise the mapping is rejected.

27. A method of interleaving blocks of indexed data having indices, the blocks having a varying length, the method comprising:

providing a set of basic interleavers comprising a family of one or more permutations of the indexed data, each of the basic interleavers having a variable length;

selecting one of the basic interleavers, I₂^m, having a size 2^m based upon a desired interleaver length L, such that 2m−

1<

L<

2m; and

adapting the selected one of the basic interleavers to produce an interleaver, I_L, having the desired interleaver length L, wherein adapting the selected one of the basic interleavers comprises for j=0 to 2<sup>L−

1</sup> and i=0 to 2<sup>L−

1</sup>;

setting I_L<sup>−

1</sup>(i) if I_2m<sup>−

1</sup>(j); and

rejecting I_L<sup>−

1</sup>(i) if I_2m<sup>−

1</sup>(j)≧

L.

28. The method of claim 27, wherein the set of basic interleavers comprises two-dimensional permutations and further comprising computing the two-dimensional permutations by:

writing the indexed data into an interleaver matrix having one or more rows in each of two dimensions;

permuting the indexed data in the one or more rows in at least one of the two dimensions to produce constituent permutations; and

reading out the indexed data from the interleaver matrix.

29. The method of claim 28, further comprising:

providing an interleaver device for interleaving the blocks of indexed data, the interleaver device comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

30. The method of claim 29, 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 a totality of permuted indices of the constituent permutations.

31. The method of claim 28, wherein said constituent permutations are different from one row to another row in each of the two dimensions.

32. The method of claim 31, further comprising:

providing an interleaver device for interleaving the blocks of indexed data, the interleaver device comprising a memory device for storing descriptions of the basic interleavers; and

storing the descriptions of the basic interleavers in the memory device.

33. The method of claim 32, 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 a totality of permuted indices of the constituent permutations.