High-performance low-memory interleaver banks for turbo-codes
View Patent ↗An interleaver for interleaving a set of K ordered elements is disclosed herein. The disclosed interleaver can be expressed as a single permutation that corresponds to two local dithering operations and a global permutation operation. The single permutation can be represented as a small collection of short vectors, and can be calculated recursively, allowing the interleaver to be both stored and implemented using a smaller amount of memory than conventionally possible.
1. A method of interleaving a set of K ordered elements, the K ordered elements organisable as m subsets, the subsets having an average size of R elements, the method comprising:
permuting the elements within each of the m subsets to produce a dithered set of K ordered elements;
permuting the K elements in the dithered set of ordered elements to produce a permuted set of K ordered elements, the permuted set organisable as n subsets having an average size of W elements; and
permuting the elements within each of the n subsets to produce an interleaved set of K ordered elements.
2. The method of claim 1 , wherein each of the m subsets has R elements.
3. The method of claim 1 , wherein each of the n subsets has W elements.
4. The method of claim 1 , wherein each of the m subsets are distinct and each of the n subsets are distinct.
5. The method of claim 1 , wherein each of the m subsets is permuted in an identical fashion.
6. The method of claim 1 , wherein the step of permuting the K elements in the dithered set produces a relative prime interleaving of the K elements.
7. The method of claim 1 , wherein each of the n subsets is permuted in an identical fashion.
8. A method of designing an interleaving method, for interleaving a set of K ordered elements, the K ordered elements organisable as m subsets having an average size of R elements, the method of designing comprising:
selecting a permutation of the elements in each of the m subsets for dithering the set of K ordered elements;
selecting a permutation of the K elements in the dithered set for permuting the set of K dithered elements, the permuted set organisable as n subsets having an average size of W elements;
selecting a permutation of the elements in each of the n subsets for dithering the set of K permuted elements; and
combining the three permutation operations to create an interleaving method.
9. The method of claim 8 , wherein each of the m subsets has R elements.
10. The method of claim 8 , wherein each of the n subsets has W elements.
11. The method of claim 8 , wherein each of the m subsets are distinct and each of the n subsets are distinct.
12. The method of claim 8 , wherein the selected permutations of the m subsets are identical.
13. The method of claim 8 , wherein the selected permutation of the K dithered elements results in a relative prime interleaving of the dithered set of K ordered elements.
14. The method of claim 8 , wherein the selected permutations of the n subsets are identical.
15. The method of claim 8 , wherein the step of combining includes the step of determining a global permutation equivalent to the combination of the three permutation operations.
16. The method of claim 15 , wherein the global permutation is a recursive function based on M ordered index increments.
17. The method of claim 16 , wherein M is the lowest common multiple of R and W.
18. The method of claim 16 , (or 16 ) wherein M, R, and W are identical.
19. An interleaver, having a memory for storing K ordered elements, the ordered elements organisable into m subsets having an average length of R elements, the interleaver comprising:
a first ditherer, operatively connected to the memory, for performing a local permutation of the elements in each of the m subsets to produce a dithered set of K ordered elements;
a permuter, operatively connected to the first ditherer, for performing a global permutation of the K elements in the dithered set to produce a permuted set of K ordered elements, the permuted set organisable as n subsets having an average length of W elements; and
a second ditherer, operatively connected to the permuter, for performing a local permutation of the elements within each of the n subsets to produce an interleaved set of K ordered elements.
20. The interleaver of claim 19 , wherein the permuter is a relative prime interleaver for interleaving the dithered set with an interleaving index increment that is relatively prime to K.
21. The interleaver of claim 19 , wherein the first ditherer, the permuter, and the second ditherer are integrated for providing the interleaved set directly from the K ordered elements based on a mapping corresponding to the combining of the first ditherer, the permuter, and the second ditherer.
22. The interleaver of claim 21 , wherein the mapping is stored as a recursive function based on M ordered index increments.
23. The interleaver of claim 22 , wherein M, R, and W are identical.
24. A plurality of the interleavers of claim 19 , connected as a bank, each interleaver having its own first dither, permuter, and second dither specifications.
25. The interleaver bank of claim 24 , further comprising an interleaver selector for selecting an interleaver from the plurality to interleave K ordered input elements into an interleaved set of K ordered output elements.
26. The interleaver of claim 19 , wherein the interleaver is connected to a recursive systematic convolutional encoder of a Turbo-code encoder, for providing the recursive systematic convolutional encoder with the interleaved set of K ordered elements.
27. An interleaving system, for permuting a variable number of elements, using a recursively derived set of interleaver indices, the interleaving system comprising:
a memory for receiving and storing the variable number of elements;
an interleaver bank memory, for storing B sets of interleaver specification parameters, the B sets corresponding to B interleavers; and
an interleaver index generator operatively connected to the memory and to the interleaver bank memory, for selecting one of the B sets of interleaver specification parameters from the interleaver bank memory, deriving M index increments from the selected set of specification parameters, for generating a set of interleaver indices from the set of M index increments, and for outputting the contents of the memory in an order determined by the generated set of interleaver indices.
28. The interleaving system of claim 27 , where the set of specification parameters includes a set of M index increments.
29. The interleaving system of claim 27 , where the set of specification parameters includes a read dither vector of length R and a write dither vector of length W.
30. The interleaving system of claim 29 , where M is a common multiple of R and W.
31. The interleaving system of claim 29 , where M is the least common multiple of R and W.
32. The interleaving system of claim 29 , where M, R and W are identical.