Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-10
2003-12-23
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C711S217000
Reexamination Certificate
active
06668350
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a communication system, and in particular, to an interleaving/deinterleaving device and method for a radio communication system.
2. Description of the Related Art
Interleaving is typically used in mobile communications to increase the performance of an error correction code in a fading channel, and is intimately associated with decoding of a random error correction code. Particularly, an air interface for an IMT-2000 communication system requires a concrete method for implementing various interleaving techniques. In addition, the methods for interleaving have resulted in an increase in the reliability of digital communication systems, and in particular, have resulted in a performance improvement for existing and future digital communication systems alike.
The IMT-2000 standard provisionally recommends using a bit reverse interleaver for a channel interleaver. However, the forward link and the reverse link defined by the IMT-2000 standard have various types of logical channels, and the interleaver has various sizes. Therefore, in order to solve this variety requirement, there is required the increased memory capacity. For example, in a N=3 forward link transmission mode, there is used an interleaver of various sizes from 144 bits/frame to 36864 bits/frame. A brief description of the bit reversal interleaver will be made below.
FIG. 1
shows a permutation method of the bit reversal interleaver. Referring to
FIG. 1
, the bit reversal interleaver rearranges frame bits by exchanging bit positions from the most significant bit (MSB) to the least significant bit (LSB), thereby to generate an interleaving address. This interleaving method has the following advantage. Since the interleaver is implemented using an enumeration function, it is simple to use the memory and it is easy to implement interleavers of various sizes. In addition, the bit positions of the permuted sequence are distributed at random in major locations. However, an interleaver having a size which cannot be expressed in terms of a power of 2 has a reduced memory efficiency. For example, to implement the 36864-bit interleaver, there is required a 64 Kbit (65536=2
16
) memory. Since the value 36864 is higher than 32 Kbits (32768=2
15
) an additional bit is needed to represent the number. Therefore, 28672 (=65536−36864) bits are unused in the memory, thereby causing a memory loss. In addition, even though the memory has a sufficient capacity, it is very difficult to implement a method for transmitting the symbols. Further, it is also difficult for the receiver to detect an accurate position of the received symbols. Finally, since various types of interleavers are used, it is necessary to store various interleaving rules in memory thereby requiring a controller (CPU) to have a high memory capacity as well.
The conventional interleaving method has the following disadvantages. First, in the existing interleaving method, the size of the interleaver cannot be expressed in terms of a power of 2, and the interleaver having the larger size is less memory efficient. That is, in most cases, the size of each logical channel is not expressed in terms of 2
m
, therefore the interleaver has a large size when designing an interleaver for the IMT-2000 forward link. Therefore, it is ineffective to use the bit reversal interleaving method.
Second, in the existing interleaving method, it is necessary to store various interleaving rules according to the interleaver sizes in the controller (CPU or host) of the transceiver. Therefore, the host memory requires a separate storage in addition to an interleaver buffer.
Third, the interleaver/deinterleaver has a complex transmission scheme because invalid address should be removed when the interleaver size is set to 2
m
to perform bit reversal interleaving. Further, the interleaver/deinterleaver has difficulty in synchronizing the symbols.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide an interleaving device and method for generating an address for various interleaver sizes using a single algorithm in a communication system.
It is another object of the present invention to provide an interleaving device and method for allowing an interleaver memory to use only a capacity corresponding to a frame size N in a communication system.
To achieve the above objects, there is provided a device for sequentially storing input bit symbols of a given interleaver size N in a memory at an address from 0 to N−1 and reading the stored bit symbols from the memory. The device comprises a look-up table for providing a first variable m and a second variable J satisfying the equation N=2
m
×J; and an address generator for generating a read address depending on the first and second variables m and J provided from the look-up table. The read address is determined by 2
m
(K mod J)+BRO(K/J), where K (0≦K≦(N−1)) denotes a reading sequence and BRO (“Bit Reverse Ordering”) is a function for converting a binary value to a decimal value by bit reversing.
REFERENCES:
patent: 6314534 (2001-11-01), Agrawal et al.
patent: 6334197 (2001-12-01), Eroz et al.
patent: 6493815 (2002-12-01), Kim et al.
patent: 6507629 (2003-01-01), Hatakeyama
patent: 10-013252 (1998-01-01), None
patent: 10-303854 (1998-11-01), None
patent: 11-205159 (1999-07-01), None
patent: WO 99/255069 (1999-05-01), None
patent: WO 00/35101 (2000-06-01), None
patent: WO 00/35103 (2000-06-01), None
Japanese Office Action dated Jun. 10, 2003 issued in a counterpart application, namely Appln. No. 2000-587454.
Chaudry Mujtaba
Dilworth & Barrese LLP
Moise Emmanuel L.
Samsung Electronics Co,. Ltd.
LandOfFree
Interleaving/deinterleaving device and method for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaving/deinterleaving device and method for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving/deinterleaving device and method for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121488