Viterbi decoder

Details Viterbi decoder Viterbi decoder

1998-08-06

2001-11-13

Pham, Chi (Department: 2631)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

C375S262000, C714S794000, C714S795000, C714S796000

Reexamination Certificate

active

06317472

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Viterbi decoder, and more particularly, to an apparatus configuration for supplying and storing a state metric used during add-compare-select (ACS) operations in a Viterbi decoder that uses a number of ACS units to enhance decoding speed.
2. Description of the Related Art
A Viterbi decoder is an apparatus that decodes codewords, encoded by a convolutional code, by using a maximum likelihood method. The Viterbi decoder compares an encoding state of a predetermined encoder with that of a received codeword, selects the closest encoding path, and decodes information transmitted from the selected path.
FIG. 1
is a block diagram showing a conventional Viterbi decoder. The Viterbi decoder shown in
FIG. 1
includes a branch metric calculator
10
, an ACS unit
12
, a state metric memory
14
, a path memory
16
, and a path tracing logic unit
18
.
When the apparatus shown in
FIG. 1
receives a codeword, the branch metric calculator
10
calculates the similarity (Hamming distance) between the received codeword and a predetermined codeword, which can be output from an encoder (not shown), and outputs a branch metric BM. The ACS unit
12
receives the branch metric BM provided from the branch metric calculator
10
and a previous (old) state metric OSM stored in the state metric memory
14
as inputs, and performs an add-compare operation to select a survival path showing an encoding sequence closest to that of the received codeword and calculate a current (new) state metric NSM of the survival path. The selected survival path is stored in the path memory
16
and the calculated current state metric NSM is stored in the state metric memory
14
. The path tracing logic unit
18
refers to the survival path memory in the path memory
16
and outputs decoded data based on an encoding path of the received codeword.
The number of states N which can exist for a single codeword, among the received codewords in Viterbi decoding, is defined as 2
K−1
, where K is defined as a constraint length. When the ACS unit
12
of
FIG. 1
, which calculates the state metric of the survival path, has N number of states, the apparatus shown in
FIG. 1
maintains the fastest processing speed. This is because N ACS units each simultaneously perform an ACS operation, with respect to the N states which can exist in correspondence to a single codeword.
Therefore, with respect to decoding speed, it is preferable that N ACS units be used for codeword having N states. However, it is difficult to make a large capacity ACS unit. Thus, as the state number N becomes larger, the number of ACS units must be selected appropriately.
A convolutional code having a constraint length K of 9 is used in a general code division multiple access (CDMA) system, therefore, the state number becomes 256 (2
a−1
). If a Viterbi decoder uses 256 ACS units, decoding speed is fast, but more hardware is required. However, when a single ACS unit is used in a Viterbi decoder, less hardware is required, but decoding speed is slow.
A Viterbi decoder using a single ACS unit is disclosed in Korean patent application No. 90-20808 filed on Dec. 17, 1990, by the same applicants, entitled “State metric storage device”. This device can perform fast input and output processing of a state metric when a single ACS unit is used, but cannot be used when a number of ACS units are used.
A technology for enhancing decoding speed using a number of ACS units is disclosed in Korean patent application No. 96-7208 filed on Mar. 18, 1996, by the same applicants, entitled “ACS device of Viterbi decoder”. This device uses four ACS units to enhance decoding speed. However, since the device includes a typical state metric memory, that is comprised of a single memory device, the input and output speed of the state metric are somewhat slow.
A technology for solving the above problems is disclosed in Korean patent application No. 97-8603, filed on Mar. 14, 1997, by the same applicants, entitled “State metric storing method and apparatus for Viterbi decoder”. This apparatus uses two-state metric storing units that are comprised of two memory devices, to efficiently supply and store the state metric used during add-compare-select operations. However, since a memory capacity of
2
N is required, where N is the number of states, the memory capacity of the state metric storing unit becomes larger as N increases, which is burdensome.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide a small capacity Viterbi decoder that uses a number of ACS units to enhance decoding speed that can supply and store a state metric.
To achieve the above objective, there is provided a Viterbi decoder comprising: a state metric storing portion that has a single memory bank for reading and writing a state metric of a first half; and two memory banks for reading and writing the state metric of the second half alternately, whenever a codeword is applied; wherein the state metric storing portion is comprised of a single two-port memory, which is used by all of the add-compare-select units.
Thus, because a memory for storing a state metric of a first half is not used, storage capacity for storing the state metrics is greatly reduced when compared with a conventional apparatus.


REFERENCES:
patent: 5272706 (1993-12-01), Park
patent: 5559837 (1996-09-01), Blaker et al.
patent: 5923713 (1999-07-01), Hatakeyama
patent: 5946361 (1999-08-01), Araki et al.
patent: 5960011 (1999-09-01), Oh
patent: 6041433 (2000-03-01), Kamada
patent: 2 311 447 A (1997-09-01), None
patent: 60-183824 (1985-09-01), None
patent: 61-62235 (1986-03-01), None
patent: 96/31953 (1996-10-01), None

Affiliated with

Also associated with

Rating

Viterbi decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2590318