Multiple codeword interleaver method and apparatus

• US 5,898,698 A
• Filed: 09/23/1997
• Issued: 04/27/1999
• Est. Priority Date: 09/24/1996
• Status: Expired due to Term

• Current Assignee: STMicroelectronics NV
• Original Assignee: Orckit Communications Ltd. (Orckit-Corrigent )
• Inventors: Bross, Shraga
• Primary Examiner(s): Chung, Phung M.
• Application Number:
  US08/935,621
• Time in Patent Office: 581 Days
• Field of Search: 371/2.1
• US Class Current: 714/701
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

An interleaver which allows the use of consecutive groups of codewords within a frame, where the maximum size of each codeword is constrained to be equal to or less than a certain maximum size. In accordance with required performance standards, i.e., the specification of a maximum number of data errors that the system is supposed to withstand, the interleaver is capable of limiting the number of errors which occur within a specific codeword to be less than the maximum number of errors that can be corrected by the particular coding scheme. The interleaver is able to achieve this result even for codewords of uneven length. The interleaver attempts to divide the total number of symbols to be transmitted in a frame into equal size codewords. If the codeword size cannot be made equal, then unequal size codewords are used, however, the difference in size between codewords cannot be greater than one symbol. The R dimension of the interleaver memory is then generally determined based on the largest codeword size, except with certain modifications. Based on whether the codeword lengths are even, odd or a mix of even odd, a variable number of "dummy" symbols is inserted into the codewords to maintain the R and C dimensions of the interleaver memory such that R and C do not have any common multiple factors. A de-interleaver may also be realized by essentially performing the reverse process as the interleaver.

Claims

1. A method of arranging a frame of data comprising a plurality of codewords into an interleaver memory having a length R and a depth C, the method comprising the following steps:

dividing said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

optionally modifying said codewords according to the following rules;

if the codewords are of equal length R and (R,C)=1, then the codewords are interleaved into said memory;

if the codewords are of equal length R, (R,C)≠

1 and (R+1,C)=1, each said codeword is modified to include an additional dummy symbol, and the modified codewords are interleaved into said memory;

if the codewords are of different size R and R+1, and (R+1,C)=1, each said codeword of length R is modified to include an additional dummy symbol, and the R+1 length codewords and the modified R length codewords are interleaved into said memory;

if the codewords are of different size R and R+1, (R+1,C)≠

1, and (R+2,C)=1, each said codeword of length R+1 is modified to include an additional dummy symbol, each said codeword of length R is modified to include an additional two dummy symbols, and said modified codewords are interleaved into said memory.

2. The method of claim 1, wherein said modifying step comprises the step of adding one or more dummy symbols to the beginning of said codewords.

3. The method of claim 1, wherein said modifying step comprises the step of appending one or more dummy symbols to the end of said codewords.

4. A method of arranging a frame of data comprising a plurality of codewords into an interleaver memory having a length R and a depth C, wherein C is a power of 2, the method comprising the following steps:

dividing said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

optionally modifying said codewords according to the following rules;

if the codewords are all of odd size, the codewords are interleaved into said memory;

if the codewords are all of even size, each said codeword is modified to include an additional symbol, and the modified even codewords are interleaved into said memory;

if the codewords are of odd and even size, and said odd size is greater than said even size, each said even codeword is modified to include an additional symbol, and said odd codewords and said modified even codewords are interleaved into said memory;

if the codewords are of odd and even size, and said even size is greater than said odd size, each said even codeword is modified to include an additional symbol, each said odd codeword is modified to include an additional two symbols, and said modified odd codewords and said modified even codewords are interleaved into said memory.

5. The method of claim 4, wherein said modifying step comprises the step of adding one or more dummy symbols to the beginning of said codewords.

6. The method of claim 4, wherein said modifying step comprises the step of appending one or more dummy symbols to the end of said codewords.

7. An interleaver circuit in which a frame of data comprising a plurality of codewords is arranged, comprising:

a memory circuit having a length R and a depth C;

a frame division circuit which divides said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

a codeword modification circuit which optionally modifies said codewords according to the following rules;

if the codewords are of equal length R and (R,C)=1, then the codewords are interleaved into said memory;

if the codewords are of equal length R, (R,C)≠

1 and (R+1,C)=1, each said codeword is modified to include an additional dummy symbol, and the modified codewords are interleaved into said memory;

if the codewords are of different size R and R+1, and (R+1,C)=1, each said codeword of length R is modified to include an additional dummy symbol, and the R+1 length codewords and the modified R length codewords are interleaved into said memory;

if the codewords are of different size R and R+1, (R+1,C)≠

1, and (R+2,C)=1, each said codeword of length R+1 is modified to include an additional dummy symbol, each said codeword of length R is modified to include an additional two dummy symbols, and said modified codewords are interleaved into said memory.

8. The interleaver circuit of claim 7, wherein said modification circuit adds one or more dummy symbols to the beginning of said codewords.

9. The interleaver circuit of claim 7, wherein said modification circuit appends one or more dummy symbols to the end of said codewords.

10. An interleaver circuit in which a frame of data comprising a plurality of codewords is arranged, comprising:

an interleaver memory circuit having a length R and a depth C, wherein C is a power of 2;

a frame division circuit which divides said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

a codeword modification circuit which optionally modifies said codewords according to the following rules;

if the codewords are all of odd size, the codewords are interleaved into said memory;

if the codewords are all of even size, each said codeword is modified to include an additional symbol, and the modified even codewords are interleaved into said memory;

if the codewords are of odd and even size, and said odd size is greater than said even size, each said even codeword is modified to include an additional symbol, and said odd codewords and said modified even codewords are interleaved into said memory;

if the codewords are of odd and even size, and said even size is greater than said odd size, each said even codeword is modified to include an additional symbol, each said odd codeword is modified to include an additional two symbols, and said modified odd codewords and said modified even codewords are interleaved into said memory.

11. The interleaver circuit of claim 10, wherein said modification circuit adds one or more dummy symbols to the beginning of said codewords.

12. The interleaver circuit of claim 10, wherein said modification circuit appends one or more dummy symbols to the end of said codewords.

13. A method of rearranging a frame of data comprising a plurality of codewords into a de-interleaver memory having a length R and depth C, the method comprising the following steps:

dividing said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

optionally modifying said codewords and writing said codewords into said de-interleaver memory according to the following rules;

if the codewords are of equal length R and (R,C)=1 then the codewords are de-interleaved into said memory by reading then writing each incoming symbol;

if the codewords are of equal length R and (R,C)≠

1 and (R+1,c)=1, then one dummy symbol is added by the de-interleave write process into the de-interleave memory at the beginning of each codeword;

if the codewords are of different size R and R+1, and (R+1,C)=1, then at the beginning of each said codeword of length R the de-interleave write process inserts an extra dummy symbol, while performing its regular write operation for each length R+1 codeword;

if the codewords are of different size R and R+1, and (R+1,C)≠

1, and (R+2,C)=1, then at the beginning of each said codeword of length R+1 the de-interleave write process inserts an extra dummy symbol, while for each length R codeword it inserts an extra symbol at the beginning of each such codeword and at the C+1 symbol of each such codeword.

14. A method of rearranging a frame of data comprising a plurality of codewords into a de-interleaver memory having a length R and a depth C, wherein C is a power of 2, the method comprising the following steps:

dividing said frame into a plurality of codewords, wherein the length of said codewords is either equal or within one symbol of each other;

optionally modifying said codewords and writing said codewords into said de-interleaver memory according to the following rules;

if the codewords are all of odd size, the codewords are deinterleaved into said memory by reading then writing each incoming symbol;

if the codewords are all of even size, each said codeword is modified to include an additional symbol, and the modified even codewords are de-interleaved into said memory by reading then writing the modified even codewords;

if the codewords are of odd and even size, and said odd size is greater than said even size, each said even codeword is modified to include an additional symbol, and said odd codewords and said modified even codewords are de-interleaved into said memory by reading then writing the odd codewords and modified even codewords;

if the codewords are of odd and even size, and said even size is greater than said odd size, each said even codeword is modified to include an additional symbol, each said odd codeword is modified to include an additional two symbols, and said modified odd codewords and said modified even codewords are de-interleaved into said memory by reading then writing said modified odd and even codewords.