Interleaver with linear feedback shift register

• US 7,788,560 B2
• Filed: 03/20/2008
• Issued: 08/31/2010
• Est. Priority Date: 05/18/2005
• Status: Expired due to Fees

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Vasiliev, Peter Igorevich, Souvignier, Thomas Victor, Born, Richard Martin, Silvus, Gregory Lee, Argon, Cenk
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US12/051,927
• Publication Number:
  US 20080215831A1
• Time in Patent Office: 894 Days
• Field of Search: 714/763, 714/728, 714/739
• US Class Current: 714/728
• CPC Class Codes: H03M 13/2742 Irregular interleaver wherein the permutation pattern is not obtained by a computation rule, e.g. interleaver based on random generators
• CPC Class Codes: H03M 13/276 Interleaving address generation

Abstract

An interleaver has an input multiplexer that receives a data sequence at an interleaver input and that separates the data sequence into multiple data sub-blocks. The interleaver has a linear feedback shift register that generates an input address sequence. The interleaver has adder circuits that generate output address sequences associated with each data sub-block. The interleaver has memory that stores the data sub-blocks at addresses controlled by the input address sequence. The memory reproduces each data sub-block in an interleaved sequence controlled by the associated output address sequence. The interleaver has an output multiplexer that assembles the interleaved sequences to provide an interleaver output.

Claims

1. A circuit, comprising:

an address generator that comprises a linear feedback shift register and that provides an input address sequence and an output address sequence, the output address sequence having a pseudorandom mapping with respect to the input address sequence;

a random access memory that has a data sequence input, an interleaved sequence output and an address input that receives the input address sequence and the output address sequence, the random access memory storing the data sequence input according to the input address sequence and the random access memory generating the interleaved sequence output according the output address sequence;

wherein the address generator generates an input address sequence that comprises AG1 and the address generator generates an output address sequence that comprises (AG1+a constant) mod L, where L is a size of a data sequence received at the data sequence input.

2. The circuit of claim 1, wherein the linear feedback shift register comprises:

a plurality of clocked registers connected in cascade and including a first clocked register with a first register input, each of the clocked registers comprising a register output; and

an adder that receives a plurality of the register outputs and that provides an adder output that couples to the first register input.

3. The circuit of claim 1, wherein the address generator adds a constant to at least one of the input address sequence and the output address sequence.

4. The circuit of claim 1, further comprising:

an input multiplexer that receives a data sequence and that separates the data sequence into at least first and second sub-b locks of data; and

the first sub-block of data couples to the data sequence input of the random access memory.

5. The circuit of claim 1, further comprising:

an output multiplexer that has a first output multiplexer input that receives the interleaved sequence output and that has at least a second output multiplexer input adapted to receive a second interleaved sequence, the output multiplexer combining the first and second output multiplexer inputs at an output multiplexer output.

6. The circuit of claim 1 wherein the random access memory comprises first and second memory buffers, and the first memory buffer loads data from the data sequence input while the second memory buffer unloads data to the interleaved sequence output.

7. The circuit of claim 1, wherein the pseudorandom mapping comprises a mapping in which data points x_i, x_i+1, x_i+2 have pseudorandom disordered distributions as a function of i.

8. A circuit, comprising:

an address generator that comprises first and second linear feedback shift registers and that provides an input address sequence and an output address sequence, the output address sequence having a pseudorandom mapping with respect to the input address sequence;

a random access memory that has a data sequence input, an interleaved sequence output, and an address input that receives the input address sequence and the output address sequence, the random access memory storing the data sequence input according to the input address sequence, and the random access memory generating the interleaved sequence output according the output address sequence;

wherein the first linear feedback shift register implements a first primitive polynomial having a first polynomial degree, and the second linear feedback shift register implements a second primitive polynomial that is different than the first primitive polynomial, and the second primitive polynomial has a second polynomial degree that is the same as the first polynomial degree.

9. The circuit of claim 8 wherein at least one of the first and second linear feedback shift registers has a shift register output that is added to a constant to form at least one of the input and output address sequences.

10. The circuit of claim 8 wherein both the first and second linear feedback shift registers implement the same first primitive polynomial.

11. The circuit of claim 8, wherein at least one of the linear feedback shift registers comprises:

a plurality of clocked registers connected in cascade and including a first clocked register with a first register input, each of the clocked registers comprising a register output; and

an adder that receives a plurality of the register outputs and that provides an adder output that couples to the first register input.

12. The circuit of claim 8 wherein the random access memory comprises first and second memory buffers, and the first memory buffer loads data from the data sequence input while the second memory buffer unloads data to the interleaved sequence output.

13. A method, comprising:

providing a random access memory with a data sequence input and an interleaved sequence output;

providing the random access memory with an address input that receives an input address sequence and an output address sequence, the random access memory storing the data sequence input according to the input address sequence, and the random access memory generating the interleaved sequence output according the output address sequence;

generating the input address sequence and output address sequence with respective first and second linear feedback shift registers;

providing the output address sequence with a pseudorandom mapping with respect to the input address sequence;

implementing the first linear feedback shift register with a first primitive polynomial of a selected degree; and

implementing the second linear feedback shift register with a second primitive polynomial that is different than the first primitive polynomial, the second primitive polynomial having the same degree as the selected degree.

14. The method of claim 13, further comprising:

providing the input address sequence from the first linear feedback shift register; and

providing the second address sequence from a sum of a constant and an output of the second linear feedback shift register.

15. The method of claim 13, further comprising:

implementing the same first primitive polynomial in both the first and second linear feedback shift registers.

16. The method of claim 13, further comprising:

forming at least one of the linear feedback shift registers from a plurality of clocked registers connecting in cascade and including a first clocked register with a first register input, each of the clocked registers comprising a register output; and

providing an adder that receives a plurality of the register outputs and that provides an adder output that couples to the first register input.

17. The method of claim 13, further comprising:

forming the random access memory from first and second memory buffers; and

loading the data sequence input into the first memory buffer while the second memory buffer is unloading data to the interleaved sequence output.