Back to results
US 6,603,412 B2Granted
Interleaved coder and method
AssigneeTexas Instruments Incorporated
InventorsAlan Gatherer, Anand Dabak, Timothy M. Schmidl, John Linn
Life of this patent
Estimating the term…
Abstract
Quasi-parallel read/write interleaver architecture for data blocks by sequential spreading of variable size data subblocks into memory banks with bank address contention initiating the next data subblock. Iterative Turbo decoders with MAP decoders use such quasi-parallel interleavers and deinterleavers.
Claims11
A method of interleaving a block of data, comprising:
- (a) providing a block of K data, x(k), for k=1, 2, . . . , K where K is a positive integer;
- (b) providing output addresses a(k) for k=1, 2, . . . , K, said output addresses partitioned into N banks where N is an integer greater than 1 and less than K;
- (c) writing data x(k1), x(k2), . . . to addresses a(π(k1)), a(π(k2)), . . . in parallel for addresses a(π(k1)), a(π(k2)), . . . in different ones of said N banks and with π(k) a permutation of {1,2, . . . . K}.
A method of interleaving a block of data, comprising:
- (a) providing a block of K data, x(k), for k=1, 2, . . . , K where K is a positive integer;
- (b) providing an output memory with addresses a(k) for k=1, 2, . . . , K, said output memory partitioned into N banks where N is an integer greater than 1 and less than K;
- (c) interleaving said block of K data by the steps of:
- (i) finding permutations π(k) for k=1, 2, . . . , N;
- (ii) finding the largest positive integer M for the permutations π(k) of step (i) so the addresses a(π(k1)) and a(π(k2)) are for different ones of said memory banks for each k1 and k2 not equal to k1 in the first M values of k from step (i) with a default value M=1 and a maximum value M=N;
- (iii) for the first M values of k from step (i) writing x(k) to address a(π(k));
- (iv) increasing each of the N values of k in step (i) by M but with a maximum of k=K, and
- (v) repeating steps (i)-(iv) until all of said block of K data has been written to said output memory.
5 more elements
A method of interleaving, comprising:
- (a) providing a data block of size RC with R and C positive integers;
- (b) partitioning said data block into sets of size R and permuting the data within each of said sets of size R;
- (c) partitioning said permuted data block from step (b) into sets of size C and permuting the data within each of said sets of size C;
- and
- (d) partitioning said permuted data block from step (c) into sets of size R and permuting the data within each of said sets of size R.
2 more elements
An interleaver, comprising:
- (a) an input memory;
- (b) a permutation unit;
- (c) an index counter coupled to said input memory and to said permutation unit;
- (d) an output memory, said output memory partitioned into N banks where N is an integer greater than 1 and each of said banks has a write circuit;
- (e) a decision-allocation unit coupled to said input memory, said output memory, said index counter, and said permutation unit, wherein said decision-allocation unit includes
- (i) an output-memory-bank-address-contention decision unit for a block of N index permutations from said permutation unit,
- (ii) an allocation unit for data in said input memory at locations corresponding to indices from said index counter and for output memory locations corresponding to non-contentious permutations of said indices from said decision unit, and
- (iii) an index counter increment output from said decision unit;
- (f) wherein said allocation unit yields writes of data from said input memory to said output memory in aggregates of size according to the number of non-contentious permutations from said decision unit and the corresponding index increment allows repeated aggregate writes to step through data in said input memory.
6 more elements
An interleaver, comprising:
- (a) an input memory;
- (b) an output memory partitioned into N banks where N is an integer greater than 1;
- (c) a programmable processor coupled to said input memory and said output memory, said processor programmed to interleave data x(k) for k=1, 2, . . . , K in said input memory and write such interleaved data to output memory with addresses a(k) by the steps of:
- (i) finding permutations T(k) for k=1, 2, . . . , N;
- (ii) finding the largest positive integer M for the permutations π(k) of step (i) so the addresses a(π(k1)) and a(π(k2)) are for different ones of said memory banks for each k1 and k2 not equal to k1 in the first M values of k from step (i) with a default value M=1 and a maximum value M=N;
- (iii) for the first M values of k from step (i) writing x(k) to address a(π(k));
- (iv) increasing each of the N values of k in step (i) by M but with a maximum of k=K, and
- (v) repeating steps (i)-(iv) until all of said data x(k) has been written to said output memory;
- (d) whereby the data writes of step (c)(iii) may be in parallel.
6 more elements
An interleaver, comprising:
- (a) a first crossbar switch, said first crossbar switch with a first sequence of settings;
- (b) a memory coupled to said first crossbar switch, said memory with a sequence of addresses;
- and
- (c) a second crossbar switch coupled to said memory, said second crossbar switch with a second sequence of settings.
1 more element
Dependencies are inferred from the claim text.