Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
1999-12-30
2004-02-10
Chin, Stephen (Department: 2634)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C375S262000
Reexamination Certificate
active
06690737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication systems such as satellite, ISDN, digital cellular, W-CDMA and IMT-2000 communication systems, and in particular, to a device and method for selecting (or determining) a maximum likelihood (ML) state in a decoding device.
2. Description of the Related Art
The present invention is applied to a Viterbi algorithm used for a Viterbi decoder, Viterbi equalizer, ML sequence detector, turbo decoder, SISO (Soft-In, Soft-Out) decoder and trellis coded modulator (TCM).
In particular, the invention is applied to a supplemental channel (or data channel) in an air interface of an IMT-2000 system and to a turbo coder which will be used in a data channel of UMTS (Universal Mobile Telecommunication System) proposed by ETSI (European Telecommunication Standards Institute). In addition, the invention contributes to an increase in the reliability of a digital communication system, and in particular, to a performance improvement of existing and future digital mobile communication systems.
Conventionally, a trace-back method is used to determine ML states. This method calculates a vector for minimizing the Euclidean distance between a symbol vector R=(r1,r2, . . . ,rn) received during Viterbi decoding and a code vector C=(c1,c2, . . . ,cn) on an encoder trellis, and then outputs an ML state at a corresponding branch at a desired time while tracing back the states on a trellis path, along which the code vector progresses, beginning at the present time. For example, in order to determine an ML state at a present time k, it is necessary to perform an ACS (Add-Compare-Select) operation and a path selection of the Viterbi decoder until a time which is a time (k+W) ahead of the present time, and trace back an ML path by W from the time (k+W). Here, W is a predetermined size and has a value of W>5 m, where m is a memory size (or capacity) of a convolutional coder. Herein, W is a sliding window, and a memory size of m is 8 in the case of the constraint length K=9.
For a high-speed Viterbi decoder, the trace-back method has some disadvantages. Using the trace-back method causes a considerable delay. For example, when a decoding depth or sliding window depth is W, it is necessary to perform a back search by W in order to select an ML state. Therefore, when the total frame size is FL, a processing delay required for the whole ML state search increases by W×(FL−W). It is noted that the processing delay increases considerably, as compared with a processing delay L occurring when the Viterbi decoder performs the trace-back operation only once (i.e., when the Viterbi decoder operates in a frame mode (W=FL)). More accurately, the delay increases by (W(FL−W)−FL). For example, for FL=2000 and W=60, the processing delay for ML state search in the frame mode is 2000, which identical to FL. However, in the sliding window mode, the processing delay for ML state search is W(FL−W)=60(2000−60)=116400, which is 58.2 times the processing delay in the frame mode. That is, it is noted that the processing delay increases by about W times. Therefore, the prior art requires many internal operations resulting in processing delays when searching an ML state.
For a turbo decoder, there are various proposed decoders such as a MAP (Maximum A Posteriori probability) decoder and a SOVA (Soft Output Viterbi Algorithm) decoder. The SOVA decoder requires an algorithm for searching the ML state in order to improve performance. A low-speed turbo coder can be implemented by the trace-back method stated above. However, since an actual complexity of the turbo decoder is very high, resulting in processing delays, the ML state search of the trace-back method can be performed only at relatively low data rate.
In summation, the prior art has the following disadvantages.
First, the trace-back method has a considerable delay in determining the ML state. For example, when the decoding depth (or sliding window depth) is W, it is necessary to perform a back-search by W in order to select an ML state at every trace-back process. Therefore, when the whole frame size is FL, the processing delay required for the whole ML state search considerably increases by W(FL−W).
Second, when a SOVA decoder is used to implement a turbo decoder, an algorithm for searching an ML state is essentially required to improve performance. However, the trace-back method is undesirable due to its processing delay problem.
Therefore, there is a demand for a new ML state determining method having the reduced processing delay. Thus, the present invention proposes a new ML state determining method, in which the above stated conditions and the hardware implementation complexity are taken into consideration.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a device and method for determining an ML state in a decoding device using a trellis decoding method.
It is another object of the present invention to provide a device and method for determining an ML state in a SOVA decoder.
To achieve the above objects, there is provided a device for selecting an ML (Maximum Likelihood) state comprising: a plurality of cells arranged in a matrix of rows and columns; and a plurality of select lines, wherein each select line is connected to all cells in a corresponding row, the select lines receive associated path select signals, each cell in a column is connected to cells in an immediately preceding column so that the cell receives a plurality of state values according to a trellis structure of the decoding device, each cell in a first column receives a plurality of state values determined according to a trellis structure of an encoder, said each first column cell selects one of the received state values in response to the select signal to store the selected state value, and cells in a last column output a state value corresponding to the ML state.
REFERENCES:
patent: 5410555 (1995-04-01), Itakura et al.
patent: 62-109661 (1987-05-01), None
patent: 05-035460 (1993-02-01), None
patent: 08-051349 (1996-03-01), None
patent: 08-073847 (1996-03-01), None
Chin Stephen
Dilworth & Barrese LLP
Odom Curtis
LandOfFree
Device and method for determining maximum likelihood state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for determining maximum likelihood state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for determining maximum likelihood state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3303796