Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-09-14
2002-09-03
Ghebretinsae, Temesghen (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000, C714S795000, C714S796000
Reexamination Certificate
active
06445755
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a two-step soft output Viterbi algorithm decoder. The present application is based on Korean Application No. 99-39334 which is incorporated herein by reference.
2. Description of the Related Art
Turbo-Codes, a type of error correction code used for the correction of errors that occur in channels of digital communication systems, were introduced for the first time in 1993 by Claude Berrou, Alain Glavieux and Punva Thitimajshima, in an article entitled “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes (1)”, ICC'93, Geneva, Switzerland, pp. 1064-1070. Also, Turbo-Codes have been adopted as wireless transmission specifications for International Mobile Telecommunication by the year 2000 (IMT-2000), and the number of potential applications is continuing to expand.
As for parallel concatenated convolutional codes (PCCCs) of the Turbo-Codes, an information bit stream is encoded by two component encoders connected in parallel at both ends of an interleaver, and is decoded by two component decoders which are serially connected with n interleaver therebetween.
A two-step soft output Viterbi algorithm (SOVA) is applicable for turbo decoding. Application of the SOVA to a turbo decoder was described in articles entitled “Decoding Turbo-Codes with the Soft Output Viterbi Algorithm” (Joachim Hagenauer and Lutz Papke, IEEE International Symposium on Information Theory, pp. 164, Trondheim, Norway, Jun. 27 through July 1994) and “An IC for Turbo-Codes Encoding and Decoding” (C. Berrou, P. Combelles, P. Penard and B. Talibart, IEEE International Solid-State Circuits Conference, pp. 90-91, San Francisco, Calif., USA, Feb. 15 through 17, 1995).
The two-step SOVA is implemented by applying a trace back operation in two steps. A general Viterbi algorithm applies a single trace back algorithm to decide the state of a start node so as to update a soft decision value. The two-step SOVA finds a survivor path and a concurrent path by applying a double trace back algorithm from the state decided by the Viterbi algorithm. Next, if the hard decision values from the paths are different, the soft decision value for the survivor path at the state is updated.
FIG. 1
is a diagram illustrating a conventional two-step SOVA. In
FIG. 1
, the decoding depth of the system is equal to L+L′, and the update depth for soft decision values is L′. Survivor information and soft decision values used to find the survivor path at all states, corresponding to a depth of L+L′, are stored in a memory. A trace back is carried out for the depth L′ from the survivor state at a time k for hard decision and soft decision using the survivor information to find the most reliable survivor state. The longer the depth for trace back is, the higher the reliability of the survivor state is. Accordingly, the soft decision value can be updated with a more reliable soft decision value.
As shown in
FIG. 1
, a Viterbi algorithm is carried out with a trellis T. In other words, the survivor state m
L
(k) and the soft decision value at time k are found by trace back. A delay line having a depth of L delays input symbols by the depth L to make the input symbols available for a trellis T′. In the trellis T′, a double trace back is carried out from the survivor state m
L
(k). The branch and state metrics are calculated from the input symbols. The state metric can be also referred to as “path metric”.
The important characteristic of the Viterbi algorithm is that if every state from a current time unit k is traced backwards through its maximum likelihood path, all of the paths converge at a state m
L
(k).
The double trace back is carried out to obtain the survivor path and the concurrent path from the survivor state determined by the Viterbi algorithm. Two hard decision values are yielded by the two paths and compared. If the compared hard decision values are different, the soft decision value of the survivor path is compared with he soft decision value of the survivor state given by the first track back and replaced by a smaller soft decision value.
However, the hard and soft decision described above are started by reading the survivor information from the memory. To get a reliable survivor state using the trace back algorithm, the survivor information stored in the memory, which is engaged in the depth L, must be read. Finding the survivor path and the concurrent path in the double trace back algorithm also begins with reading the survivor information from the memory. Also, when updating a soft decision value, the soft decision values for the states engaged in the depth L′ are stored in the memory, and a soft decision value of the state which needs updating is read, updated and stored back in the memory. Such successive processes are started by reading information from the memory, which retards the processing speed, and increases complexity in proportion to the number of memories.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide a two-step Viterbi algorithm decoder for tracing the survivor path and the concurrent path and updating a soft decision value, including a soft output Viterbi algorithm-state metric unit (SOVA-SMU), which is constructed of registers and multiplexers, instead of a memory for storing survivor information for all states.
The above objective of the present invention is achieved by a two-step soft output Viterbi algorithm decoder, comprising: a branch metric unit for calculating branch metrics for received data from the degree of similarity between data symbols, which appear to be received if a transmission channel has no error, and the actually received data symbols; a state metric memory for storing state metrics for all states of the received data symbols; an add-compare-select unit for adding the branch metrics of the branches for each state of the current time unit and the state metrics for each state of the previous time unit stored in the state metric memory, storing the results of the additions, which satisfies a predetermined condition, as the state metrics of the current time unit in the state metric memory, and outputting a difference between the results of the additions as a delta value, and as many selector bits as the number of bits of the received data symbols so as to select a path; a survivor state output unit for outputting a survivor state satisfying a predetermined condition among the current state metrics for all states output from the add-compare-select unit; and a soft output Viterbi algorithm-state metric unit (SOVA-SMU) for back tracing a first survivor path for a first time unit from the survivor state output from the survivor state output unit, using the delta values for all states and the selector bits, to obtain the survivor state at the end of the first survivor path and a soft decision value of the first survivor path, for performing a double trace back for a second time unit from the survivor state at the end of the first survivor path to find a second survivor path and a concurrent path, for updating the soft decision value of the second survivor path by the soft decision value of the first survivor path if the hard decision values of the second survivor path and the concurrent path for the second period are different and if a soft decision value of the second survivor path is larger than the soft decision value of the first survivor path, and for outputting the hard and soft decision values of the second survivor path at the end of the second time unit.
REFERENCES:
patent: 5295142 (1994-03-01), Hatakeyama
patent: 5881075 (1999-03-01), Kong et al.
patent: 6301314 (2001-10-01), Murayama
patent: 6301684 (2001-10-01), Watanabe et al.
patent: 6317472 (2001-11-01), Choi et al.
patent: 7-254861 (1995-10-01), None
patent: 11-163742 (1999-06-01), None
Choi Jun-rim
Chung Won-hee
Kim Dae-won
Kong Jun-jin
Kwon Taek-won
Ghebretinsae Temesghen
Samsung Electronics Co Ltd.
Sughrue & Mion, PLLC
LandOfFree
Two-step soft output viterbi algorithm decoder using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Two-step soft output viterbi algorithm decoder using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-step soft output viterbi algorithm decoder using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876664