Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-10-17
2004-07-27
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S774000
Reexamination Certificate
active
06769091
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Related Art
2. Description of the Related Art
Communication systems often use compression techniques for services such as voice and video. Because these compression techniques are non-ideal, the transmitted bits of data can have different importance to the end user. For voice, this is because certain audible artifacts are perceived differently than others by the human mind. To exploit this, many wireless systems employ unequal error protection (UEP) instead of equal error protection (EEP) when transmitting information. These systems advantageously provide more error protection to the bits that are the most perceptually significant, thus limiting the degradation caused by channel impairments such as noise and interference. In systems such as the GSM cellular standard, speech bits are ranked and categorized based on significance. Bits that are perceptually significance are classified as class 1 bits and are coded while less significant bits are labeled as class 2 bits and are uncoded. The class 1 bits can also be partitioned into classes such as class 1a and class 1b bits.
FIG. 1
illustrates a schematic block diagram of a prior art unequal error protection encoder for speech-coded information block. Speech bits
100
are one type of information block. A multiplexing switch
120
partitions the speech bits
100
into two classes of information blocks, a class 1 block
130
and a class 2 block
140
. The multiplexing switch
120
partitions the speech bits
100
using human perceivable characteristics. The class 1 block
130
represents a portion of information that is perceptually more important. In
FIG. 1
, the class 1 block
130
is encoded using a convolutional encoder
160
and a puncture block
170
channel coding scheme. The class 2 block
140
represents perceptually less important portions of information and channel coding scheme for the class 2 block
140
is not to perform any coding. The output of the puncture block
170
and the class 2 block
140
are then combined using a multplexer
180
to produce an information block with unequal error protection
190
.
Although the prior art does provide acceptable performance for several speech applications, there are drawbacks with the prior art. The complexity of the decoder for the convolutional encoder is related to the number of states in the convolutional encoder and the number of class 1 bits. When complexity is a factor in the design of the decoder, to use the prior art, the number of states in the convolutional encoder may have to be reduced so that complexity constraints can be satisfied. However, reducing the number of states can reduce the error protection capability of the convolutional code, thereby possibly degrading the performance of the code.
Another drawback of the prior art is that the puncture block may become very complicated to implement and/or store its puncturing pattern. The complexity of the puncture block can thereby undesirably increase. A larger puncture pattern can undesirably increase memory requirements. A further drawback of the prior art is that in order to protect all of the bits, parts of the trellis (e.g., convolutional code) are often severely punctured. Such weak coding can act as an error generator in poor channel conditions.
Several other unequal error protection methods exist but the decoders for these methods have drawbacks. Two such methods are the known M and T-reduced state algorithms. Both algorithms perform all valid branch calculations in a trellis stage and then sort the resulting path metrics. The M algorithm keeps the best M states. The T algorithm keeps all states with path metrics within T of the best path metric. Unfortunately, while the M and T algorithms greatly reduce path storage in the decoder, the operation complexity may not be decreased as compared to the non-reduced state (e.g., conventional decoder) algorithm.
Another possible unequal error protection method is to two separate convolutional codes, one for the class 1 and 1b bits and the previously uncoded bits. But this has drawbacks and do not solve the problem of low complexity. For example, a strong trellis code, such as a 64-state convolutional code, could be used for the first code and a weak trellis code, such as a 16-state convolutional code, could be used for the second code while satisfying the complexity constraints. In addition, this method can incorporate the puncturing to provide unequal error protection within each code. However, one issue with the use of two separate codes is that there is a significant increase in the overhead for the code. In general, convolutional codes are tailed (forced to state zero) after the information block has been encoded to improve decoder performance at the expense of overhead. Tailing adds m bits of overhead for a 2
m
-state convolutional code. Thus when two separate convolutional codes are used with individual tailing requirements of m
0
and m
1
bits, the combined overhead increases to m
0
+m
1
. This overhead, in some applications, can be difficult to eliminate. Another method that can use multiple codes for unequal error protection and that eliminates the overhead due to tailing is to use a tail-biting technique. However, a major disadvantage of the tail-biting is that decoding complexity can triple over conventional decoding.
Therefore, there is a need for a unequal error protection coding method using several convolutional codes with several numbers of states with fewer tail bits than required for full tailing of the codes and a joint decoder for the codes on a single trellis with decoding complexity approximately equal to separately decoding the codes.
SUMMARY OF THE INVENTION
A trellis encoder according to the present invention has unequal error correction. A multiplexing switch partitions an information block such as speech into a first portion of information and a second portion of information. A first trellis encoder having a first number of states encodes the first portion of information. A second trellis encoder having a second number of states encodes the second portion of information. An initial state information generator establishes initial conditions for the states of the second trellis encoder based on the states of the first trellis encoder by mapping the states of the first trellis encoder to the second trellis encoder. A delay delays the second portion of information from processing by the second trellis encoder until the initial state information generator has mapped the states of the first trellis encoder to the second trellis encoder. A decoder in a system decodes data from the squished trellis encoder using either the above squished approach or other alternate approach.
The details of the preferred embodiments of the invention may be readily understood from the following detailed description when read in conjunction with the accompanying drawings wherein:
REFERENCES:
patent: 5768613 (1998-06-01), Asghar
patent: 6128322 (2000-10-01), Rasanen et al.
patent: 6216107 (2001-04-01), Rydbeck et al.
patent: 6256487 (2001-07-01), Bruhn
patent: 6442176 (2002-08-01), Yahagi
patent: 2002/0006138 (2002-01-01), Odenwalder
Stanley J. Simmons; “Breadth-First Trellis Decoding with Adaptive Effort”; IEEE Transactions on Communications, vol. 38, No. 1, Jan. 1990; pp. 3-12.
Peter A. Bengough and Stanley J. Simmons; Sorting-Based VLSI Architectures for the M-algorithm and T-algorithm Trellis Decoders; IEEE Transactions on Communications, vol. 43, No. 2/3/4, Feb./Mar./Apr., 1995, pp. 514-522.
Blankenship Yufei Wu
Classon Brian
Desai Vipul Anil
Johnson John
De'cady Albert
Haas Kenneth A.
Motorola Inc.
Torres Joseph D.
LandOfFree
Encoding method and apparatus using squished trellis codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding method and apparatus using squished trellis codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding method and apparatus using squished trellis codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244125