High-performance low-memory interleaver banks for turbo-codes
AssigneeHer Majesty the Queen in right of Canada, as represented by the Secretary of State for Industry through the Communication Research Centre
InventorsStewart N. Crozier, Paul Guinand
Life of this patent
Estimating the term…
Abstract
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.
Claims32
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.
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.
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.
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.
Dependencies are inferred from the claim text.