Apparatus for interleaving and de-interleaving data

• US 4,394,642 A
• Filed: 09/21/1981
• Issued: 07/19/1983
• Est. Priority Date: 09/21/1981
• Status: Expired due to Term

• Current Assignee: Sperry Corporation (Unisys Corporation)
• Original Assignee: Sperry Corporation (Unisys Corporation)
• Inventors: Zscheile, John W. Jr., Spencer, Billie M., Rattlingourd, Glen D., Currie, Robert J.
• Primary Examiner(s): Miller, C. D.
• Application Number:
  US06/304,434
• Time in Patent Office: 666 Days
• Field of Search: 340/347 DD, 371/40, 364/200, 364/900
• US Class Current: 341/81
• CPC Class Codes: G06F 7/76 Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/2785 Interleaver using in-place interleaving, i.e. writing to and reading from the memory is performed at the same memory location

Abstract

A novel interleaver-de-interleaver is provided which is adapted to store bits of a data stream after being error encoded. The data bits are stored in a random access memory in addresses identifiable by an array of columns and rows. The interleaver comprises address pointer means and logic for reading the data bits out of the memory addresses in a predetermined reordered sequence to provide a quasi-random pattern sequence of data bits which when transmitted are substantially immune to periodic bursts of radio frequency interference signals.

Claims

1. A data transmitting system of the type having an interleaver for changing the order of data bits in a data stream to be transmitted comprising:

a data source for providing a stream of data bits to be transmitted,

interleaver means coupled to said stream of data bits,

transmitter means coupled to said interleaver means for transmitting said data bits in a quasi-random pattern sequence,

said interleaver means comprising buffer memory means for storing a block of said stream of said data bits in a predetermined sequential pattern of memory addresses,

said addresses being definable in terms of an array of columns and rows,

first address pointer means coupled to said buffer memory means for generating said predetermined pattern of memory addresses and for storing said data bits in said buffer memory means in rows,

second address pointer means coupled to said buffer memory means for generating a predetermined quasi-random pattern of memory addresses and for reading said stored data bits out of said buffer memory means by columns,

said predetermined quasi-random pattern of memory addresses being generated by a predetermined rotation of bits within columns, and

control means coupled to said buffer memory means and said first and second pointer means for alternately storing said stream of data bits into said buffer memory means as rows of data bits and for reading said stored data bits out of said buffer memory means as columns of data bits in a predetermined quasi-random stream of data bits.

2. A data transmitting system as set forth in claim 1 which further includes generating said predetermined quasi-random pattern of memory addresses by further rotating said bits within rows.

3. A data transmitting system as set forth in claim 1 which further includes generating said predetermined quasi-random pattern of memory addresses by first rotating the order of said columns in said array.

4. A data transmitting system as set forth in claim 2 wherein the rotation of bits is a permutation in which the new position is equal to the old position plus one multiplied by one-half of the old position.

5. A data transmitting system as set forth in claim 3 wherein the rotation of columns is a permutation in which the new position is equal to the old position plus one multiplied by one-half of the old position.

6. A data transmitting system of the type set forth in claim 1 which comprises a forward error correction encoder coupled between said data source and said interleaver.

7. A data transmitting system of the type set forth in claim 6 which further includes;

receiving means for receiving said transmitted quasi-random stream of data bits,

de-interleaver means coupled to said receiving means for generating said stream of data bits in the same order as generated by said data source, and

forward error correction decoding means coupled to said de-interleaving means coupled to said de-interleaving means for correcting bit errors in said stream of data bits introduced by a burst of high energy interference signals.

8. A data transmitting system of the type set forth in claim 1 wherein buffer memory means comprise a random access memory.

9. A data transmitting system of the type set forth in claim 8 wherein said first and second address pointers comprise a counter and a read only memory.

10. A data transmitting system of the type set forth in claim 9 wherein said counter is adapted to supply the same address to said random access memory and to said read only memory.

11. A data transmitting system of the type set forth in claim 10 wherein said read only memory is adapted to supply an address to said counter.