Frame-based modulus interleaver

• US 5,933,431 A
• Filed: 08/15/1996
• Issued: 08/03/1999
• Est. Priority Date: 08/15/1996
• Status: Expired due to Fees

• Current Assignee: IPR 3 Pty Limited
• Original Assignee: Paradyne Corporation (Dasan Networks Incorporated)
• Inventors: Ko, Kenneth David
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): LUTHER, WILLIAM A
• Application Number:
  US08/699,124
• Time in Patent Office: 1,083 Days
• Field of Search: 370/336, 370/345, 370/389, 370/470, 370/471, 370/473, 370/476, 370/498, 371/2.1, 371/2.2, 371/37.5, 341/81, 380/36, 380/37, 360/48
• US Class Current: 370/476
• CPC Class Codes: H03M 13/275 Interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c

Abstract

The frame based modulus interleaver is used in a digital communications system. The interleaver uses an algorithm which insures that all of the data blocks which are present in the each input frame are output in a single output frame. This is accomplished, in accordance with the invention, by using a modulus operation to determine the location of each block which is input into the interleaver.

Claims

1. An improved interleaver capable of handling variable-sized frames, for use in a communications system, of the type which receives an input frame comprising a plurality of data blocks, and outputs an output frame having said data blocks interleaved therein, the interleaver comprising interleaver logic configured to ensure that each output frame has the same frame size, FS, as said input frame, wherein said logic provides that each output frame contains all of the data blocks which were contained in said input frame and wherein said logic makes use of an interleaver delay sequence of length P, wherein the increment between respective values in said delay sequence is D, and wherein said logic receives the frame size, FS, the delay sequence length, P, and the increment, D, as parameters to be used to produce the output frame having the data blocks interleaved therein, and wherein the interleaver logic is configured to ensure that the output frame has the frame size, FS.

2. The improved interleaver of claim 1, wherein said interleaver further includes a base value, S, and an offset value, Offset, which are determined from the values of P, D and FS, such that for K equal to (FS-P*D) mod P, values of S and Offset are selected from the following table:

space="preserve" listing-type="tabular">______________________________________D K S Offset______________________________________Any P - 2 1 2Any P - 1 0 1Any 0 0 0Any 1 0 D(P -

     1) - 1Any 2 P - 1 D(P -

     1) - 21 Even (P - K/2) mod P 01 Odd (P - K)/2 0none of the above not valid______________________________________

3. The improved interleaver of claim 2, wherein said interleaver logic data blocks from a location, n, within an input frame to a location, m, in an output frame associated with said input frame, whereby all of the data blocks in said input frame are moved into said output frame, said interleaving interleaver operating in accordance with procedure set forth in the following steps:

##EQU7##

4. A de-interleaver for use with the invention defined in claim 3, said de-interleaver rearranging data blocks in a received frame of data into the sequence corresponding to the sequence which said data blocks had when they were input into said interleaver.

5. The de-interleaver of claim 4, wherein said de-interleaver logic makes use of P delay values, DelayVal( ), said delay values being determined in accordance with the following procedure:

6. The de-interleaver of claim 5, which receives a frame of data having data blocks y(n), where n ranges from 0 to FS-1, said de-interleaver logic moving a data block from position n to position m in a de-interleaver output data block, z(m), said de-interleaver logic operating in accordance with the following steps:

7. An improved de-interleaver, for use in a communications system, of the type which receives an input frame comprising a plurality of interleaved data blocks, and outputs an output frame having said interleaved data blocks de-interleaved therein, the de-interleaver logic configured to ensure that each output frame has the same frame size, FS, as said input frame and for providing that each output frame contains all of the data blocks which were contained in said input frame, wherein said de-interleaver logic makes use of a de-interleaver delay sequence of length P, wherein the increment between respective values in said delay sequence is D, and wherein said de-inteleaver logic receives the frame size, FS, the delay sequence length, P, and the increment, D, as parameters to be used to produce the output frame having the de-interleaved data blocks therein, and wherein the de-interleaver logic is configured to ensure that the output frame has the frame size, FS.

8. The improved de-interleaver logic of claim 7, wherein said de-interleaver further includes a base value, S, and an offset value, Offset, which are determined from the values of P, D and FS, such that for FS greater than or equal to the interleaver propagation delay of D(P-1) and for K equal to (FS-P*D) mod P, values of S and Offset are selected from the following table:

space="preserve" listing-type="tabular">______________________________________D K S Offset______________________________________Any 0 P - 1 0Any 1 P - 1 D(P -

     1) - 1Any P - 1 D + 1 1P - 2 2 D D(P -

     1) - 2P - 2 P - 2 0 21 2 P - 1 P - 21 P - 2 2 11 4n + 1 P - 2n P - (2n +

     1)1 P - (4n +

     1) 2n + 1 2nnone of the above not valid______________________________________

9. The improved de-interleaver of claim 8, wherein said de-interleaver logic moves data blocks from a location, n, within an input frame to a location, m, in an output frame associated with said input frame, whereby all of the data blocks in said input frame are moved into said output frame, said de-interleaver logic operating in accordance with the following steps:

##EQU8##