Low complexity pseudo-random interleaver

• US 7,395,461 B2
• Filed: 05/18/2005
• Issued: 07/01/2008
• 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: Argon, Cenk, Vasiliev, Peter Igorevich, Souvignier, Thomas Victor, Born, Richard Martin, Silvus, Gregory Lee
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US11/131,518
• Publication Number:
  US 20060282712A1
• Time in Patent Office: 1,140 Days
• Field of Search: 714/701, 714/702
• US Class Current: 714/701
• 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. An interleaver, comprising:

an input multiplexer receiving a data sequence at an interleaver input and separating the data sequence into multiple data sub-blocks;

a first linear feedback shift register generating an input address sequence;

adder circuits generating an output address sequence associated with each data sub-block;

memory that stores the data sub-blocks at addresses controlled by the input address sequence, the memory reproducing each data sub-block in an interleaved sequence controlled by the associated output address sequence; and

an output multiplexer assembling the interleaved sequences to provide an interleaver output.

2. The interleaver of claim 1 wherein the adder circuits receive an output from the first linear feedback shift register.

3. The interleaver of claim 1, further comprising:

a second linear feedback shift register generating a shift register output coupling to the adder circuits.

4. The interleaver of claim 3 wherein the second linear feedback shift register generates an output LFSR2 and the output address sequence AG2 is of the form:

AG2=(LSFR2+C)mod 2^N

where C is a fixed constant and N is the degree of the primitive polynomial with which the LFSR was constructed, and LFSR2 denotes a decimal equivalent of a linear feedback shift register state.

5. The interleaver of claim 1 wherein the input address sequence alternates with the output address sequence one address at a time, and a memory reproduction of data from any designated data address is followed by a memory storage of successive data in that same designated data address one address at a time.

6. The interleaver of claim 1 wherein the first linear feedback shift register is implemented with a primitive polynomial of degree N.

7. The interleaver of claim 1 wherein the first linear feedback shift register generates addresses from 1 through 2^N−

1.

8. The interleaver of claim 7 and further comprising a circuit generate a zero address.

9. The interleaver of claim 1 wherein the first linear feedback shift register generates an output LFSR and the output address sequence AG2 is of the form:

AG2=(LSFR+C_k)mod L

where Ck is a constant associated with the kth data sub-block, L is a sub-block length, and LFSR denotes a decimal equivalent a linear feedback shift register state.

10. A method of data interleaving, comprising:

receiving a data sequence at an interleaver input and separating the data sequence into multiple data sub-blocks;

generating an input address sequence with a first linear feedback shift register;

generating an output address sequence associated with each data sub-block;

storing the data sub-blocks at memory addresses controlled by the input address sequence;

reproducing each data sub-block in an interleaved sequence controlled by the associated output address sequence; and

assembling the interleaved sequences to provide an interleaver output.

11. The method of claim 10 and generating the output address sequence using adder circuits that receive an output from the first linear feedback shift register an.

12. The method of claim 11, further comprising:

generating a shift register output coupling to the adder circuits using a second linear feedback shift register.

13. The method of claim 12 and the second linear feedback shift register generating an output LFSR2 and the output address sequence AG2 is of the form:

AG2=(LSFR2+C)mod 2^N

where C is a fixed constant and N is a degree of a primitive polynomial with which the LFSR is constructed, and LFSR2 denotes a decimal equivalent of a linear feedback shift register state.

14. The method of claim 10 and further comprising:

alternating the input address sequence with the output address sequence one address at a time, and

reproducing data from any designated data address followed by storing of successive data in that same designated data address one address at a time.

15. The method of claim 10, further comprising:

implementing the first linear feedback shift register with a primitive polynomial of degree N.

16. The method of claim 10 further comprising:

generating addresses from 1 through 2^N−

1 using the first linear feedback register.

17. The method of claim 16 further comprising:

generating a zero address with a zero address circuit.

18. The method of claim 10 further comprising:

generating an output LFSR of the first linear shift register with an output address sequence AG2 is of the form;

AG2=(LSFR+C_k)mod L

where Ck is a constant associated with the kth data sub-block, L is a sub-block length, and LFSR denotes a decimal equivalent of a linear feedback shift register state.

19. An interleaver, comprising:

an input multiplexer receiving a data sequence at an interleaver input and separating the data sequence into multiple data sub-blocks;

linear feedback shift register means for generating an input address sequence;

adder circuits generating an output address sequence associated with each data sub-block;

memory that stores the data sub-blocks at addresses controlled by the input address sequence, the memory reproducing each data sub-block in an interleaved sequence controlled by the associated output address sequence; and

an output multiplexer assembling the interleaved sequences to provide an interleaver output.

20. The interleaver of claim 19 wherein the adder circuits receive an output from the linear feedback shift register means.