Interleaving and de-interleaving method for digital data, interleaving and de-interleaving devices, and communication system
AssigneeAlcatel
InventorMiguel Peeters
Life of this patent
Estimating the term…
Abstract
A triangular interleaver (INTERLEAVER) contains a triangular shaped matrix (MAT) of memory cells, each row of which constitutes a first-in-first-out queue. To increase or decrease the interleave depth of the interleaver (INTERLEAVER), the number of interleaved data bytes read from each row of the matrix (MAT) is positively or negatively linearly related to the ordinate number (0, 1, 2, 3, 4) of this row. In this way, impulse noise immunity of transmission of the outgoing interleaved data stream (OID) over a transmission line (TL) is kept substantially independent from transmit rate changes.
Claims18
Method for interleaving incoming data bytes (w1, . . . , w10) of an incoming data stream (ID) to thereby generate an outgoing interleaved data stream (OID) of outgoing interleaved data bytes (r1, . . . r10), characterized by writing said incoming data bytes (w1, . . . , w10) in tail memory cells of rows of a triangular shaped matrix (MAT) of memory cells, each row of memory cells in said matrix (MAT) representing a first-in-first-out queue (Fifo0, Fifo1, Fifo2, Fifo3, Fifo4), and reading said outgoing interleaved data bytes (r1, . . . , r10) from head memory cells of said rows thereby reading said outgoing itnerleaved data stream (OID),
- characterized by reading from each row an amount of said outgoing interleaved data bytes (r1, . . . , r10) which is linearly related to an ordinate number (0, 1, 2, 3, 4) of said row in said triangular shaped matrix (MAT).
Method for de-interleaving incoming interleaved data bytes (w1', . . . , w10') of an incoming interleaved data stream (IID) to thereby generate an outgoing data stream (OD) of outgoing data bytes (r1', . . . , r10'), characterized by writing said incoming interleaved data bytes (w1', . . . , w10') in tail memory cells of rows of a triangular shaped matrix (MAT') of memory cells, each row of memory cells in said matrix (MAT') representing a first-in-first-out queue (Fifo0', Fifo1', Fifo2', Fifo3', Fifo4'), and reading said outgoing data bytes (r1', . . . , r10') from head memory cells of said rows thereby realizing said outgoing data stream (OD),
- characterized by writing in each row of said triangular shaped matrix (MAT') an amount of said incoming interleaved data bytes (w1', . . . , w10') which is linearly related to a ordinate number (0, 1, 2, 3, 4) of said row in said triangular shaped matrix (MAT').
Interleaving device (INTERLEAVER) used to re-sequence incoming data bytes (w1, . . . , w10) of an incoming data stream (ID) to thereby generate an outgoing interleaved data stream (OID) of outgoing interleaved data bytes (r1, . . . , r10), said interleaving device (INTERLEAVER) comprising:
- a. memory means (MEM) including a plurality of first-in-first-out queues (Fifo0, Fifo1, Fifo2, Fifo3, Fifo4) adapted to represent respective rows of a triangular shaped matrix (MAT) of memory cells;
- b. writing means (WRITE) with an output coupled to an input of said memory means (MEM), said writing means (WRITE) being adapted to write each one of said incoming data bytes (w1, . . . , w10) in a tail memory cell of one of said rows identified by a write address;
- c. reading means (READ) with an input coupled to an output of said memory means (MEM), said reading means (READ) being adapted to read each one of said outgoing interleaved data bytes (r1, . . . , r10) from a head memory cell of one of said rows identified by a read address;
- and
- d. address generating means (ADDRESS), a first output of which is coupled to an address input (AI1) of said writing means (WRITE) and a second output of which is coupled to an address input (AI2) of said reading means (READ), said address generating means (ADDRESS) being adapted to generate said write address and said read address,
- characterized in that said address generating means (ADDRESS) is further adapted to generate for each row an amount of read addresses which is linearly related to an ordinate number (0, 1, 2, 3, 4) of said row in said triangular shaped matrix (MAT).
De-interleaving device (DE-INTERLEAVER) used to re-sequence incoming interleaved data bytes (w1', . . . w10') of an incoming interleaved data stream (IID) to thereby generate an outgoing data stream (OD) of outgoing data bytes (r1', . . . , r10'), said de-interleaving device (DE-INTERLEAVER) comprising:
- a. memory means (MEM') including a plurality of first-in-first-out queues (Fifo0', Fifo1', Fifo2', Fifo3', Fifo4') adapted to represent respective rows of a triangular shaped matrix (MAT') of memory cells;
- b. writing means (WRITE') with an output coupled to an input of said memory means (MEM'), said writing means (WRITE') being adapted to write each one of said incoming interleaved data bytes (w1', . . . , w10') in a tail memory cell of one of said rows identified by a write address;
- c. reading means (READ') with an input coupled to an output of said memory means (MEM'), said reading means (READ') being adapted to read each one of said outgoing data bytes (r1', . . . , r10') from a head memory cell of one of said rows identified by a read address;
- and
- d. address generating means (ADDRESS'), a first output of which is coupled to an address input (AI1') of said writing means (WRITE') and a second output of which is coupled to an address input (AI2') of said reading means (READ'), said address generating means (ADDRESS') being adapted to generate said write address and said read address,
- characterized in that said address generating means (ADDRESS') further is adapted to generate for each row of said triangular shaped matrix (MAT') an amount of write addresses which is linearly related to an ordinate number (0, 1, 2, 3, 4) of said row in said triangular shaped matrix (MAT').
A communication system comprising a transmitter (TX) coupled via a transmission line (TL) to a receiver (RX), said transmitter (TX) comprising the cascade connection of:
- a. a data source (DATA SOURCE) provided to generate a data stream;
- b. encoding means (ENCODER) provided to extend words of said data stream with redundant information to thereby generate codewords of an incoming data stream (ID);
- c. interleaving means (INTERLEAVER) provided to re-sequence incoming data bytes (w1, . . . , w10) of said incoming data stream (ID) to thereby generate an outgoing interleaved data stream (OID) of outgoing interleaved data bytes (r1, . . . , r10);
- and
- d. modulating means (MOD) provided to modulate said outgoing interleaved data stream (OID) on at least one data carrier to be transmitted over said transmission line (TL),
- said interleaving means (INTERLEAVER) comprising:
- c1. first memory means (MEM) including a plurality of first-in-first-out queues (Fifo0, Fifo1, Fifo2, Fifo3, Fifo4) adapted to represent respective rows of a first triangular shaped matrix (MAT) of memory cells;
- c2. first writing means (WRITE) with an output coupled to an input of said first memory means (MEM), said first writing means (WRITE) being adapted to write each one of said incoming data bytes (w1, . . . , w10) in a tail memory cell of one of said rows identified by a write address;
- c3. first reading means (READ) with an input coupled to an output of said first memory means (MEM), said reading means (READ) being adapted to read each one of said outgoing interleaved data bytes (r1, . . . , r10) from a head memory cell of one of said rows identified by a read address;
- and
- c4. first address generating means (ADDRESS), a first output of which is coupled to an address input (AI1) of said first writing means (WRITE) and a second output of which is coupled to an address input (AI2) of said first reading means (READ), said first address generating means (ADDRESS) being adapted to generate said write address and said read address,
- and said receiver (RX) comprising the cascade connection of:
- e. de-modulating means (DMOD) provided to de-modulate incoming interleaved data bytes (w1', . . . , w10') from said at least one carrier to thereby produce an incoming interleaved data stream (IID);
- f. de-interleaving means (DE-INTERLEAVER) provided to re-sequence said incoming interleaved data bytes (w1', . . . , w10') in said incoming interleaved data stream (IID) to thereby generate an outgoing data stream (OD) of outgoing data bytes (r1', . . . , r10') grouped in codewords;
- g. decoding means (DECODER) provided to detect and correct errors in said codewords by interpretation of redundant information therein to thereby produce a data stream of words;
- and
- h. a data sink (DATA SINK) provided to receive said data stream from said decoding means (DECODER),
- said de-interleaving means (DE-INTERLEAVER) comprising:
- f1. second memory means (MEM') including a plurality of first-in-first-out queues (Fifo0', Fifo1', Fifo2', Fifo3', Fifo4') adapted to represent respective rows of a second triangular shaped matrix (MAT') of memory cells;
- f2. second writing means (WRITE') with an output coupled to an input of said second memory means (MEM'), said second writing means (WRITE') being adapted to write each one of said incoming interleaved data bytes (w1', . . . , w10') in a tail memory cell of one of said rows identified by a write address;
- f3. second reading means (READ') with an input coupled to an output of said second memory means (MEM'), said reading means (READ') being adapted to read each one of said outgoing data bytes (r1', . . . , r10') from a head memory cell of one of said rows identified by a read address;
- and
- f4. second address generating means (ADDRESS'), a first output of which is coupled to an address input (AI1') of said second writing means (WRITE') and a second output of which is coupled to an address input (AI2') of said second reading means (READ'), said second address generating means (ADDRESS') being adapted to generate said write address and said read address,
- characterized in that said first address generating means (ADDRESS) is further adapted to generate for each row an amount of read addresses which is linearly related to an ordinate number (0, 1, 2, 3, 4) of said row in said first triangular shaped matrix (MAT), and further in that said second address generating means (ADDRESS') further is adapted to generate for each row of said second triangular shaped matrix (MAT') an amount of write addresses which is linearly related to an ordinate number (0, 1, 2, 3, 4) of said row in said second triangular shaped matrix (MAT').
Dependencies are inferred from the claim text.