Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-19
2003-07-22
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S788000
Reexamination Certificate
active
06598202
ABSTRACT:
PRIORITY
This application claims priority to an application entitled “Turbo Interleaving Apparatus and Method” filed in the Korean Industrial Property Office on May 19, 1999 and assigned Serial No. 99-18928 and an application filed in the Korean Industrial Property Office on May 21, 1999 and assigned Serial No. 99-18560, the contents of which are hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a turbo encoder used for radio communication systems (including satellite, ISDN, digital cellular, W-CDMA, and IMT-2000 systems), and in particular, to an internal interleaver of a turbo encoder.
2. Description of the Related Art
In general, an interleaver used for a turbo encoder randomizes an address of input information word and improves a distance property of a codeword. In particular, it has been decided that a turbo code will be used in a supplemental channel (or data transmission channel) of IMT-2000 (or CDMA-2000) and IS-95C air interfaces and in a data channel of UMTS (Universal Mobile Telecommunication System) proposed by ETSI (European Telecommunication Standards Institute). Thus, a method for embodying an interleaver for this purpose is required. In addition, the invention relates to an error correction code which greatly affects performance improvement of the existing and future digital communication systems.
For an existing internal interleaver for a turbo encoder (hereinafter, referred to as a turbo interleaver), there have been proposed various interleavers such as PN (Pseudo Noise) random interleaver, random interleaver, block interleaver, non-linear interleaver, and S-random interleaver. However, so far, 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 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 its internal interleaver. In general, an increase in the input frame size (i.e., the number of information bits included in one frame) enhances the effectiveness of the turbo encoder. However, an increase in interleaver size causes a geometric increase in calculations. Therefore, in general, it is not possible to implement the interleaver for the large frame size.
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. This has the same function as a codeword distance property of the convolutional code, and as a criterion indicating this, a minimum free distance is used which is a value of a codeword path or a codeword sequence with the minimum Hamming weight out of the code symbol sequences (or codeword paths) output on the trellis. In general, it is preferable that the interleaver should be designed to have the longer free distance, if possible.
Random Property: A 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 makes a direct effect on the quality of extrinsic information generated in continuous decoding.
Although the above criteria are applicable to a general turbo interleaver, it is difficult to clearly analyze the properties when the interleaver increases in size.
In addition, another problem occurring when designing the turbo interleaver is that the minimum free distance of the turbo code varies according to the type of the input codeword. That is, when the input information word has a specific sequence pattern defined as a critical information sequence pattern (CISP), the free distance of the output code symbols generated from the turbo encoder has a very small value. If the input information word has a Hamming weight
2
, the CISP occurs when the input information word has two information bits of ‘1’ and can also occur when the input information word has 3 or more information bits of ‘1’. However, in most cases, when the input information word has 2 information bits of ‘1’, the minimum free distance is formed and most error events occur in this condition. Therefore, when designing the turbo interleaver, an analysis is generally made on the case where the input information word has the Hamming weight
2
. A reason that the CISP exists is because the turbo encoder generally uses RSC (Recursive Systematic Convolutional Codes) encoders for the component encoders shown in
FIG. 1
(described further below). To improve performance of the turbo encoder, a primitive polynomial should be used for a feedback polynomial (gf(x) of
FIG. 1
) out of the generator polynomials for the component encoder. Therefore, when the number of the memories of the RSC encoder is m, a feedback sequence generated by the feedback polynomial continuously repeats the same pattern at a period of 2
m
−1. Therefore, if an input information word ‘1’ is received at the instance corresponding to this period, the same information bits are exclusive-ORed, so that the state of the RSC encoder becomes an all-zero state henceforth, thus generating the output symbols of all 0's. This means that the Hamming weight of the codeword generated by the RSC encoder has a constant value after this event. That is, the free distance of the turbo code is maintained after this time, and the CISP becomes a main cause of a reduction in the free distance of the turbo encoder, whereas, as noted above, a larger free distance is desirable.
In this case (in the prior art of turbo interleaver), to increase the free distance, the turbo interleaver randomly disperses the CISP input information word so as to prevent a decrease in the free distance at the output symbol of the other component RSC encoder.
The above-stated properties are fundamental features of the known turbo interleaver. However, for the CISP, it is conventional that the information word has the minimum Hamming weight, when the input information word has the Hamming weight
2
. In other words, the fact that the CISP can be generated even when the input information word has the Hamming weight
1
(i.e., when the input information word has one information bit of ‘1’) was overlooked, when the information word input to the turbo encoder had the type of a block comprised of frames.
For example, a prime interleaver (PIL) designated as the working model of the turbo code interleaver specified by the present UMTS standard exhibits such problems, thus having a degraded free distance property. That is, the implementation algorithm of the model PIL turbo interleaver include 3 stages, of which the second stage, which plays the most important role, performs random permutation on the information bits of the respective groups. The second stage is divided into three cases of Case A, Case B and Case C, and the Case B always involves the case where the free distance is decreased due to the event where the input information word has the Hamming weight
1
. In addition, even the Case C involves a possibility that such an event will occur. The detailed problems will be described later with reference to the PIL.
In conclusion, when various interleaver sizes are required and the hardware implementation complexity is limited in the IMT-2000 or UMTS system, the turbo interleaver should be designed to guarantee the optimal interleaver performance by taking the limitations into consideration. That is, the required interleaver should be able to guarantee uniform performance for the various interleaver sizes, while satisfying the above-stated properties. More recently, there have been proposed several types of the interleavers for a PCCC (Parallel Concatenated Convolu
Choi Soon-Jae
Kim Beong-Jo
Kim Min-Goo
Lee Young-Hwan
Dilworth & Barrese LLP
Samsung Electronics Co,. Ltd.
Ton David
LandOfFree
Turbo 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 Turbo interleaving apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo interleaving apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015786