Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-04-06
2003-07-08
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S786000
Reexamination Certificate
active
06591381
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 a 2-dimensional 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
A turbo code is a type of error correction code which affects the reliability of a digital communication system. Conventionally, turbo codes are divided into serial turbo codes and parallel turbo codes. A parallel turbo encoder encodes an input frame of L information bit streams into parity symbols using two simple parallel concatenated codes, wherein recursive systematic convolutional (RSC) encoders are typically used as the component encoders. In addition, the parallel turbo encoder includes an interleaver connected between the component encoders.
In the turbo encoder, interleaving is performed to randomize data streams on a frame unit basis 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 UMTS (Universal Mobile Telecommunication System), as proposed by ETSI (European Telecommunication Standards Institute). Therefore, a reliable method for employing a turbo interleaver with a turbo encoder for this purpose is required.
FIG. 1
shows a common parallel turbo encoder, which is disclosed in detail in U.S. Pat. No. 5,446,747, issued on Aug. 29, 1995, which is hereby incorporated by reference.
Referring to
FIG. 1
, the turbo encoder includes a first component encoder
111
for encoding input frame data, an interleaver
112
for interleaving the input frame data, and a second component encoder
113
for encoding an output of the interleaver
112
. A known RSC (Recursive Systematic Convolutional) encoder or NSC (Non-Recursive Systematic Convolutional) encoder is typically used for the first and second component encoders
111
and
113
. Such component encoders have different structure according to a coding rate, a constraint length K and a generator polynomial. Further, the interleaver
112
has the same size as the input information bit frame, and rearranges the sequence of the information bits provided to the second component encoder
113
to reduce a correlation between the information bits.
For the internal interleaver (or a turbo interleaver)
112
of the turbo encoder, various interleavers are proposed, such as PN (Pseudo Noise) random interleavers, random interleavers, block interleavers, non-linear interleavers, and S-random interleavers. However, so far, such interleavers are mere algorithms designed to improve their performances in terms of scientific researches rather than implementation. When implementing an actual system, the hardware implementation complexity must be taken into consideration. A description will now be made of 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, an increase in the input frame size (i.e., the number of information bits included in one frame) gives rise to an increase in the performance of the turbo encoder. However, an increase in interleaver size requires an increase in calculations. Therefore, in general, if the frame size is very large, it is not practical to implement the interleaver.
According to experiments, random interleaver is superior in performance to a 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). That is, the memory capacity required for addressing greatly increases. Therefore, taking the required hardware size into consideration, it is preferable to employ an address 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 complexity is restricted in an IMT-2000 or UMTS system, the turbo interleaver should be designed to guarantee optimal interleaver performance by taking inherent restrictions into consideration. That is, an interleaver which performs interleaving/deinterleaving according to a specific interleaving rule is required. In addition, the turbo interleaver requires good interleaver properties (e.g., distance property, weight property and random property).
The IMT-2000 or UMTS specification is yet to provide any definition for 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 various requirements, an increased memory capacity is required. For example, in a CDMA-2000 forward link transmission mode, an interleaver of various sizes ranging from 144 bits/frame to 36864 bits/frame may be used. In addition, the interleaver can be classified into a 1-dimensional interleaver for performing interleaving by regarding the whole input frame as one area and a 2-dimensional interleaver for dividing the input frame into several partial areas to perform interleaving according to the divided areas.
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 in terms of scientific researches rather than 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 must store interleaving rules according to the respective interleaver sizes in the existing 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 is varied and increased, an increase in memory capacity for storing the interleaver index (i.e., mapping rule or address) is required. That is, it has a disadvantage of requiring a large increase in memory capacity.
Third, it is not easy to implement an interleaver satisfying both the distance property and the random property.
Fourth, when a 2-dimensional interleaver is used, the areas are selected without consideration of the periodicity of the component encoder, so that a state of the component encoder may be reset.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide an interleaving/deinterleaving device and method for maximizing a distance property of a turbo encoder in a communication system.
It is another object of the present invention to provide an interleaving device and method for a turbo encoder, which divides input frame data by specific size before interleaving.
It is yet another object of the present invention to provide a 2-dimensional interleaving device and method for controlling group selection such that a period for selecting a specific group should be different from a period of a component encoder in the turbo encoder.
To achieve the above object, an encoding device is provided, including a first feedback convolutional encoder for encoding n data streams using a primitive polynomial of m'th order, a 2-dimensional interleaver for segmenting the n data streams into k and interleaving the n data streams
Kim Beong-Jo
Kim Min-Goo
Britt Cynthia
De'cady Albert
Dilworth & Barrese LLP
Samsung Electronics Co,. Ltd.
LandOfFree
2-dimensional interleaving apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with 2-dimensional interleaving apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 2-dimensional interleaving apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3022732