Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – For multiple memory modules
Patent
1996-06-26
1999-11-02
Lane, Jack A.
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
For multiple memory modules
G06F 1206
Patent
active
059788836
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND
The present invention relates to a process for blockwise interleaving and deinterleaving of data, as well as to a device implementing this process. The invention applies in particular to the interleaving of digital data before their transmission and to the deinterleaving after reception.
It is known from the prior art to associate the techniques of error detection and correction and interleaving in order to make the transmission of digital data reliable.
For an error correcting code such as the Reed-Solomon code, the packet of binary words to be transmitted is supplemented with a number of extra words, making it possible to correct up to a given maximum number of transmission errors. When this maximum number of errors is exceeded, the correcting code is no longer adequate. This may be the case in particular if a burst of errors corrupts several contiguous words.
In order to increase the effectiveness of the correcting code, several data packets are interleaved. This technique consists in transmitting in succession words arising from different packets. By not transmitting each packet in one go, it is possible to spread the consequences of a burst of errors over several packets, and thus to remain within the limits of the correcting code.
The interleaving, at the sending module, is generally carried out by writing the data to a memory in a certain order, and by reading them back in a different order for transmission. The deinterleaving, at the receiver, is carried out in the inverse manner, by writing the data to the deinterleaving memory in accordance with the order for reading the interleaving memory, and by reading the data back in accordance with the order for writing to the interleaving memory.
Consider P packets to be interleaved, each comprising L bytes. These P packets constitute a block B. An interleaving of depth P is said to be carried out by rearranging the bytes of the P packets in such a way as to separate two successive bytes of a given packet by P-1 bytes arising from the P-1 other packets.
FIG. 1 shows a memory making it possible to carry out this interleaving. In order to simplify the account of the prior art, this memory includes P columns of bytes. The addresses increase from left to right and from top to bottom, as FIG. 1 shows.
This memory is written to by writing the first byte of the first packet at the address 0, the second byte at the address P, and so on until the last byte (byte L-1) at the address (L-1)P. These addresses correspond to the first column of the memory. In the same way, the second packet will be written at the addresses 1, P+1, . . . (L-1)P+1 of the second column. We continue thus up to the last packet and the last column. The order of writing is illustrated in FIG. 2.
By generalizing, it may be stated that byte 1 (with 1 .epsilon. [1,L]) of packet p (with p .epsilon. [1,P]) of block b (with b .epsilon. [1,B]) will be written at the address (b-1)LP+(p-1)+(l-1)P of the memory.
Reading will be performed in the order of the addresses, that is to say by reading row after row (see FIG. 3). Hence, the first bytes of all the packets are read initially, followed by the second bytes and so on. Interlacing is therefore achieved.
This write/read scheme implies that it is necessary to write a large part of the data of a block B before being able to read it. Specifically, E=(L-1) (P-1)+1 bytes will have to have been written before reading the first byte at the address 0. If this criterion is not complied with, reading will occur at some time or another at an address which has not yet been swept by the writing.
FIG. 4 illustrates the progress of the write address and read address in the case where P is taken equal to 3 and L is taken equal to 7. Time is represented as abscissae, whilst the addresses of the interleaving memory form the ordinates. T represents an elementary clock cycle. It will be assumed that for a given cycle, writing is performed before reading.
SUMMARY OF THE INVENTION
Thereby, when the write address is equal to the read address for the same cycle
REFERENCES:
patent: 3652998 (1972-03-01), Forney
patent: 5276827 (1994-01-01), DeLaruelle et al.
Patent Abstracts of Japan vol. 9, No. 318 JP, A, 60 152 130, Tetsuchi, Itoi, Aug. 1985.
"Realization of Optimum Interleavers", Ramsey, John L. IEEE transactions on Information Theory vol. 16, No. 3, May 1970.
Patent Abstracts of Japan vol. 7, No. 152, JP,A, 58 062 752, Hidehiko, Kobayashi, Apr. 1983.
Patent Abstracts of Japan vol. 17, No. 182, JP, A, 04 335 266, Masaaki Ishibashi, Nov. 1992.
Emanuel Peter M.
Lane Jack A.
Thomson multimedia SA
Tripoli Joseph S.
Wein Frederick A.
LandOfFree
Block interleaving and deinterleaving method and device therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block interleaving and deinterleaving method and device therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block interleaving and deinterleaving method and device therefor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2150657