Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-02-18
2003-04-22
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
06553516
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the turbo encoding technique that effectively copes with a burst error. More particularly, the present invention is concerned with an interleaving method, an interleaving apparatus, a turbo encoding method, and a turbo encoder in which pruning is not performed at all or only a small number of bits is pruned away, so that computational complexity can be reduced.
The present invention can be applied to fields required to improve reliability of communications using error correction codes, such as digital transmissions and digital recording. The present invention is particularly effective in fields which require flexibility of communications such as multimedia.
2. Description of the Related Art
Recently, a turbo encoder has been proposed which utilizes a code having high capability in error correction. Such a turbo encoder is made up of a plurality of encoders, which are coupled together via an interleaver (which is means for performing interleaving processing) in order to reduce the correlation between redundant sequences associated with the respective encoders. The interleaver is a key element which determines the performance of turbo encoding.
FIGS. 1A and 1B
show an example of the turbo encoder. As shown in
FIG. 1A
, the turbo encoder includes recursive systematic convolutional encoders
12
(RSC
1
) and
13
(RSC
2
), and an interleaver
11
. As shown in
FIG. 1B
, each of the encoders
12
and
13
is made up of adders
14
and
15
and delay elements (D)
16
and
17
connected as shown therein. The turbo encoder receives an input data sequence d (K bits) and outputs encoded data sequences X
1
-X
3
. In order to reduce the correlation between the redundant bits X
1
and X
2
, the interleaver
11
is provided at the input side of the encoder (RSC
2
)
13
. As shown in
FIG. 1C
, a turbo decoder is made up to two decoders
1
and
2
, two interleavers
3
and
4
, and a deinterleaver
5
.
In digital systems, permutation in interleaving is performed on a given unit basis of bit or symbol. The permutation is implemented by using a buffer or a pattern for permutation. When the buffer is used, data is written therein and is then read therefrom in a different sequence. When the pattern for permutation is used, data is permuted by referring to the pattern, which describes information concerning a permutation based on interleaving. The pattern described will be referred to as an interleave pattern.
A description will now be given of bit-based permutation processing using the interleave pattern.
FIG. 2
shows interleaving of a 16-bit sequence. In
FIG. 2
, a 16-bit sequence
67
is interleaved on the bit unit basis by referring to an interleave pattern table
68
, which defines a sequence of interleaving. More particularly, the zeroth to 15th bits of the sequence
67
is written into a two-dimensional buffer by the interleave pattern table
68
, and is then read therefrom in the order of 0, 8, 4, 12, . . . , as indicated by an arrow in FIG.
2
. Thus, a bit sequence after interleaving is obtained as shown in FIG.
2
.
The interleaver involved in interleaving is required to have the following three capabilities of:
(1) handling a variety of frame lengths (for example, thousands to ten thousands);
(2) producing the interleaved sequence with a small number of parameters; and
(3) reducing computational complexity in creating the interleave pattern.
As to the first capability, if the parameters are merely prepared for all of the different frame lengths, a huge number of parameters will be prepared, and a huge memory capacity will be required to store the parameters. Thus, the above is impractical. There is another disadvantage that it takes a long time to compute respective optimal parameters for each of the different frame lengths.
The above problems may be solved by designing interleavers with a small number of parameters. This is related to the second capability. Interleavers equal in number to a power of 2 are prepared and pruning of data is performed. However, pruning of data requires an increased number of parameters for optimization, and the interleavers may not have good performance with respect to all of the frame lengths. That is, the interleavers have good performance for some frame lengths but do not operate well for other frame lengths.
Reduction in the amount of data to be pruned away is also related to the third capability. In this regard, the present inventors have proposed an improvement in pruning and performance (International Application No. PCT/JP98/05027). However, even the proposed improvement has high computational complexity in producing the interleave patterns.
SUMMARY OF THE INVENTION
It is a general object of the present invention to provide an improved interleaving technique having the above-mentioned three capabilities.
A more specific object of the present invention is to provide an interleaving method, an interleaving apparatus, a turbo encoding method and a turbo encoder capable of efficiently achieving randomization of input sequences of a variety of frame lengths with reduced computational complexity.
The above objects of the present invention are achieved by 1. An interleaving method comprising the steps of: receiving a data sequence having a plurality of blocks each having a length based on a prime number P; generating sequence permutation data by performing a given operation on elements of a Galois field of a characteristic P and permuting results of the given operation, so that sequence permutation data are generated; and permuting a sequence of data of the data sequence in accordance with the sequence permutation data.
The above objects of the present invention are also achieved by an interleaving method comprising the steps of: (a) generating or recording a prime number P; (b) dividing an input sequence into N blocks B
1
, B
2
, . . . , B
N
each having a length equal to P where N is an integer equal to or greater than 2; (c) generating or recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements; (d) generating or recording (N−1) integers p
1
, p
2
, . . . , p
N−1
which are mutually prime with respect to (P−1); (e) generating or recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of p
1
; (f) permuting data in the blocks B
1
-B
N
in accordance with the first through Nth sequence permutation data; and (g) reading permuted data from the blocks B
1
-B
N
in a given order.
The above-mentioned objects of the present invention are also achieved by an interleaving method comprising the steps of: (a) generating or recording a prime number P; (b) dividing an input sequence into N blocks B
1
, B
2
, . . . , B
N
each having a length equal to P where N is an integer equal to or greater than 2; (c) generating or recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements; (d) generating or recording N integers p
1
, p
2
, . . . , p
N
which are mutually prime with respect to a primitive root used in the power notation; (e) generating or recording first through Nth sequence permutation data by repeating, ith times (i=1−N), a process for generating ith sequence permutation data which is a sequence of values of exponent parts in power notation of elements obtained by adding q
i
to data of the zeroth sequence permutation data; (f) permuting data in the blocks B
1
-B
N
in accordance with the first through Nth sequence permutation data; and (g) reading permuted data from the blocks B
1
-B
N
in a given order.
In the above step (b), each of the blocks may have a length equal to (P−1
Shibutani Akira
Suda Hirohito
Chase Shelly A
De'cady Albert
NTT Mobile Communications Network Inc.
LandOfFree
Interleaving method, interleaving apparatus, turbo encoding... 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 method, interleaving apparatus, turbo encoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving method, interleaving apparatus, turbo encoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3036288