Addressing scheme for convolutional interleaver/de-interleaver

• US 6,178,530 B1
• Filed: 04/24/1998
• Issued: 01/23/2001
• Est. Priority Date: 04/24/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Weckenbrock, Hermann J., Aman, Ahmad K.
• Primary Examiner(s): De Cady, Albert
• Assistant Examiner(s): Lamarre, Guy J.
• Application Number:
  US09/065,854
• Time in Patent Office: 1,005 Days
• Field of Search: 714/702-704, 714/786, 711/220, 711/157, 711/212
• US Class Current: 714/702
• CPC Class Codes: H03M 13/2732 Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver
• CPC Class Codes: H03M 13/2764 Circuits therefore
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

A memory addressing scheme suitable for use for either interleaving or de-interleaving data bytes of, e.g., a broadcast digital television (DTV) data stream. A number of memory branches are configured in a random access memory (RAM), wherein at least some of the branches have different numbers of memory locations for reading out and for storing data bytes, thus defining memory branches of different lengths in the RAM. A start address is determined for each of the memory branches in the RAM, corresponding to a first memory location of each branch. An offset value is determined for each memory branch, to be added to the start address for the branch for addressing a memory location of the branch. If an offset value does not exceed the length of a corresponding branch, an address corresponding to the sum of the branch start address and the offset value is generated for addressing a successive memory location of the branch, and the offset value for the branch is incremented by one. When an offset value equals the length of a corresponding branch, an address corresponding to a last memory location of the branch is generated, and the offset value for the branch is reset to zero.

Claims

1. A method of generating successive addresses suitable for carrying out data interleaving or de-interleaving in a data stream using a random access memory (RAM), comprising:

configuring a number of memory branches in a given interleaving or de-interleaving RAM wherein the branches have different numbers of memory locations for reading out and for storing bytes of a data stream, thus defining memory branches of different lengths in the given RAM;

determining the length of a given memory branch by using a first adder;

determining a start address for a given memory branch in the RAM corresponding to a first memory location of the given branch, by using a second adder that adds the length and the start address of a previous branch;

determining for each memory branch corresponding offset values, and storing the offset values in an offset RAM;

addressing a memory location in a given memory branch by using a third adder that adds the start address for the given branch to a current offset value stored in the offset RAM for the given branch; and

if the current offset value does not exceed the length of the given memory branch, generating an address corresponding to the sum of the branch start address and the current offset value for addressing a successive memory location of the branch, and incrementing the offset value for the branch by one; and

when the current offset value equals the length of the given memory branch, generating an address corresponding to a last memory location of the branch, and resetting the offset value for the branch to zero.

2. The method of claim 1, including incrementing an offset value initially set for each memory branch by “

1”

each time an address for a memory location in the branch is generated.

3. The method of claim 2, including re-setting a determined offset value for a given branch to “

0”

after an offset value determined for the given branch exceeds the length of the branch.

4. The method of claim 1, including reading out from the given RAM a data byte of the data stream stored at a memory location corresponding to a generated address during a first phase of a clock cycle, and writing another data byte of the data stream into said memory location during a second phase of said clock cycle.

5. The method of claim 1, including reading out from the offset RAM an offset value stored at a memory cell corresponding to a selected memory branch in the given RAM during a first phase of a clock cycle, and writing an updated offset value for the selected memory branch into said memory cell of the offset RAM during a second phase of said clock cycle.

6. The method of claim 1, including repeatedly generating a number of addresses in an order corresponding to an order of the memory branches configured in the given RAM, wherein each generated address corresponds to one memory location of the corresponding memory branch.

7. The method of claim 1, including reading out from the given RAM a stored data byte of the data stream during a clock cycle and supplying the stored data byte at an output of a corresponding interleaver or de-interleaver circuit, and passing another data byte of the data stream directly to the output of the circuit during another clock cycle.

8. A convolutional interleaver/de-interleaver circuit for interleaving/de-interleaving data bytes of a data stream, comprising:

a processor configured to exchange control signals with other components of the circuit;

a random access memory (RAM) configured to have a number of memory branches, wherein the branches have different numbers of memory locations for reading out and for storing bytes of a data stream applied to an input of the circuit, thus defining memory branches of different lengths in the RAM;

a memory branch length determination stage including a first adder configured to determine the number of memory locations in each of the memory branches in the RAM;

a start address determination stage including a second adder configured to determine a start address corresponding to a first memory location of a given memory branch in the RAM by adding the length and the start address of a previous branch; and

an offset value determination stage configured to determine for each memory branch corresponding offset values, and an offset RAM arranged to store a current offset value for each branch; and

an address generation stage including a third adder and coupled to the memory branch length, the start address, and the offset value determination stages, and configured to address a memory location in a given memory branch in the RAM by adding the start address for the given branch to a current offset value stored in the offset RAM for the given branch wherein, if the current offset value determined for the given branch does not exceed the length of the branch, an address is generated which corresponds to the sum of the branch start address the current offset value, and, when the current offset value determined for the given branch equals the length of the branch, an address is generated which corresponds to a last memory location of the branch, and the current offset value for the branch is reset to zero.

9. The circuit of claim 8, wherein said processor is configured to read out from the de-interleaving RAM a byte of the interleaved data stream stored at a memory location corresponding to a generated address during a first phase of a clock cycle, and to write another data byte of the data stream into said memory location during a second phase of said clock cycle.

10. The circuit of claim 8, wherein said processor is configured to read out from the offset RAM an offset value stored at a memory cell corresponding to a selected memory branch in the de-interleaving RAM during a first phase of a clock cycle, and to write an updated offset value for the selected memory branch into said memory cell during a second phase of said clock cycle.

11. The circuit of claim 8, wherein said address generation stage is configured to generate repeatedly a number of addresses in an order corresponding to an order of the memory branches configured in the de-interleaving RAM, such that each generated address corresponds to one memory location of the corresponding memory branch.

12. The circuit of claim 8, including a multiplexer coupled to the de-interleaving RAM and to a circuit input, wherein the multiplexer is configured to output data bytes of an input interleaved data stream which bytes are read out from addressed memory locations of the RAM during a number of clock cycles, and to output at least one data byte of the input data stream directly during at least one other clock cycle to produce a de-interleaved data stream.