Electrical computers and digital processing systems: memory – Address formation – Generating a particular pattern/sequence of addresses
Reexamination Certificate
1999-12-27
2002-12-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Generating a particular pattern/sequence of addresses
C711S005000, C711S203000, C711S218000, C714S756000, C714S790000, C370S335000, C375S265000
Reexamination Certificate
active
06493815
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an interleaving/deinterleaving device and method, and in particular, to an interleaving/deinterleaving device and method for a turbo encoder used in radio communication systems such as satellite, ISDN (Integrated Services Digital Network), digital cellular, W-CDMA (Wideband Code Division Multiple Access), IMT-2000 and W-ATM (Wideband Asynchronous Transfer Mode) communication systems.
2. Description of the Related Art
In a turbo encoder, interleaving is performed to randomize information input to the encoder and to improve the distance property of a codeword. In particular, it is expected that the turbo encoder will be used in a supplemental channel (or traffic channel) of an IMT-2000 (or CDMA-2000) communication system and in a data channel of a UMTS (Universal Mobile Telecommunication System) as proposed by the ETSI (European Telecommunication Standards Institute). Thus, a method for embodying an interleaver for this purpose is required. In addition, the use of turbo encoders results in an increase in the reliability of a digital communication system, and in particular, in a performance improvement of existing and future digital mobile communication systems.
The turbo encoder encodes an input frame of L information bits into parity symbols using two simple parallel concatenated codes, typically using recursive systematic convolutional (RSC) codes for component codes.
FIG. 7
shows a common turbo encoder, which is disclosed in detail in U.S. Pat. No. 5,446,474, issued on Aug. 29, 1995, which is hereby incorporated by reference.
Referring to
FIG. 7
, the turbo encoder includes a first component encoder
11
for encoding input frame data, an interleaver
12
for interleaving the input frame data, and a second component encoder
13
for encoding an output of the interleaver
12
. A RSC encoder is typically used for the first and second component encoders
11
and
13
. Further, the interleaver
12
has the same size frame as the input information bit frame, and rearranges the sequence of the information bits provided to the second component encoder
13
to reduce a correlation between the information bits.
Various interleavers have been proposed for the internal interleaver (or a turbo interleaver)
12
of the turbo encoder, such as a PN (Pseudo Noise) random interleaver, random interleaver, block interleaver, non-linear interleaver, and S-random interleaver. However, thus far, such interleavers are mere algorithms designed to improve the performance of the system based on scientific research, rather than actual implementation. Therefore, when implementing an actual system, the hardware implementation complexity must be taken into consideration. A description will now be made of the properties and problems associated with the conventional interleaver for the turbo encoder.
Performance of the turbo encoder is dependent upon the internal interleaver. In general, it is not possible to design an interleaver guaranteeing optimal performance of the system because an increase in interleaver size requires a geometric increase in calculations. Therefore, in general, the interleavers are implemented by determining conditions satisfying several given criteria. The criteria are as follows:
Distance Property: The distance between adjacent codeword symbols should be maintained to a certain extent. Since this has the same function as a codeword distance property of the convolutional code, it is preferable that the interleaver be designed to have a longer distance, if possible.
Weight Property: The weight of a codeword corresponding to a non-zero information word should be higher than a threshold value. Since this has the same function as the minimum distance property of the convolutional code, it is preferable that the interleaver be designed to have a greater weight, wherever possible.
Random Property: The correlation factor between output word symbols after interleaving should be much lower than a correlation factor between original input word symbols before interleaving. That is, randomization between the output word symbols should be completely performed. This has a direct effect on improving the quality of extrinsic information generated during continuous decoding.
Although the above three design criteria are applied to the turbo interleaver, the properties are not definitely analyzed. According to experiments, the random interleaver is superior in performance to the block interleaver. However, the random interleaver is disadvantageous in that an increase in the variety and size of the frame causes an increase in the required memory capacity for storing an interleaver index (i.e., mapping rule or address). Therefore, taking the hardware size into consideration, it is preferable to employ an enumeration method for reading data stored at a corresponding address by generating an address at every symbol clock using an index generating rule rather than a look-up table method for storing the interleaver index.
In conclusion, when various interleaver sizes are required and the hardware implementation complexity is limited in the IMT-2000 or UTMS system, the turbo interleaver should be designed to guarantee the optimal interleaver performance by taking the limitations into consideration. That is, it is necessary to define an address generating rule and then perform interleaving/deinterleaving according to the address generating rule. Of course, the interleaver should be designed to completely satisfy the above stated turbo interleaver's properties.
The IMT-2000 or UMTS specification has not yet given any definition to the turbo interleaver. The forward link and the reverse link defined by the IMT-2000 specification have various types of logical channels and various interleaver sizes. Therefore, in order to meet these varying requirements, an increase in memory capacity is required. For example, in a N=3 forward link transmission mode, an interleaver of various sizes ranging from 144 bits/frame to 36864 bits/frame may be used.
To sum up, the prior art has the following disadvantages.
First, for the conventional internal interleaver of the turbo encoder, PN random interleavers, random interleavers, block interleavers, non-linear interleavers, and S-random interleavers may be used. However, such interleavers are mere algorithms designed to improve their performances based on scientific research rather than actual implementation. Therefore, when implementing an actual system, the hardware implementation complexity of such interleavers must be considered. However, this is not specifically defined.
Second, since a controller (CPU or host) of the transceiver stores interleaving rules according to the respective interleaver sizes in the conventional interleaving method using a look-up table, a host memory requires a separate capacity in addition to an interleaver buffer. That is, when the frame size varies and increases in size, an increased memory capacity for storing the interleaver index (i.e., mapping rule or address) is required.
Third, it is not easy to implement an interleaver satisfying both the distance property and the random property.
Fourth, a detailed turbo interleaver design specification for the turbo encoder of the CDMA-2000 forward link is not established yet.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a device and method for interleaving/deinterleaving data of various sizes in a communication system.
It is another object of the present invention to provide an interleaving/deinterleaving device and method satisfying all the properties of a turbo encoder, including the distance property, weight property and random property, in a communication system.
It is yet further another object of the present invention to provide an offset controlled interleaving/deinterleaving device and method in a communication system.
To achieve the above objects, an interleaving method is provided which comprises storing input data in a memory according to a
Kim Beong-Jo
Kim Min Goo
Lee Young-Hwan
Dilworth & Barrese LLP
Kim Matthew
Samsung Electronics Co,. Ltd.
Vital Pierre M.
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-2941559