Add-compare-select circuit for viterbi decoder

Details Add-compare-select circuit for viterbi decoder Add-compare-select circuit for viterbi decoder

1999-09-16

2003-01-07

Ghayour, Mohammad H. (Department: 2734)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

C375S262000, C375S265000, C714S790000, C714S795000, C714S796000

Reexamination Certificate

active

06504882

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a viterbi decoder and, more particularly, to a viterbi decoder having a reduced decoding time with respect to encoded convolutional codes.
BACKGROUND OF THE INVENTION
A viterbi decoder uses the well known viterbi algorithm when a received convolutional codeword is to be decoded. The viterbi algorithm depends on maximum likelihood decoding. The Viterbi algorithm compares aplurality of known code sequences with received code sequences, selects the path having the shortest code distance as a maximum likelihood path, and obtains decoded data corresponding to the selected path. The viterbi algorithm exhibits excellent error correction capability. Thus, it is widely used in satellite, ground network, and mobile communications.
The principles of viterbi decoding are described, for example, in “CDMA Principles of Spread Spectrum Communication” by A. J. VITERBI, ADDISON-WESLEY PUBLISHING COMPANY, pp.132-138, April, 1995. An example of the viterbi decoder is disclosed in U.S. Pat. No. 5,295,142 issued on Mar. 15, 1994.
In a code division multiple access (CDMA) mobile station, the operational timing of the viterbi decoder relates to three channel types (i.e., sync, paging, and traffic channels) of the four forward CDMA channels. The forward CDMA channel corresponds to communications from a base station (cell) to a mobile station.
In mobile communications, technical requirements are specified by air interface standards such as IS-95A and ANSI J-STD-008. They ensure that mobile stations can obtain service in any cellular system manufactured according to these standards. The IS-95A specification for wideband spread spectrum cellular mobile telephones, supports a 9,600 bps rate family in the three data channeling types (sync, paging, and traffic channels). This is referred to as Rate Set
1
. In all cases, the forward error correction (FEC) code rate is ½. The J-STD-008 specification for CDMA personal communications services systems (PCS) supplies, in addition to the above Rate Set
1
, a second traffic channel rate family with a maximum rate of 14,400 bps. This is referred to as Rate Set
2
. Rate Set
2
uses an FEC code rate of ¾, created by puncturing (deleting) the code used in Rate Set
1
.
Rate Set
2
yields the same code symbol rate as Rate Set
1
with {fraction (3/2)} times the data rate. Traffic channels carry variable traffic frames of either 1, ½, ¼, or ⅛ times the full rate. The rate variation is accomplished by 1, 2, 4, or 8-way repetition of code symbols.
A system employing the CDMA communication method uses a viterbi decoder that includes a single add-compare-select (ACS) unit. The decoder usually uses a convolutional codeword with a constrained length K of 9 and, thus, the number of states is 2
9−1
, namely, 256. Therefore, the single ACS unit performs addition, comparison, and selection on 256 states for one symbol.
FIG. 1
is a schematic block diagram of a conventional viterbi decoder. The viterbi decoder includes a controller
10
, an input buffer
20
, a symbol metric table (SMT) unit
30
, a branch metric calculate unit
40
, an ACS unit
50
, a traceback unit
60
, and an output buffer
70
. The controller
10
generates a variety of control signals (hereinafter collectively represented by the reference symbol “CTL”) after a frame synchronous signal F_Sync is activated. The viterbi decoder decodes an input symbol IN_DATA and outputs decoded data DECODED DATA under the control of the control signals CTL from the controller
10
.
FIG. 2
is a block diagram illustrating the ACS unit
50
of FIG.
1
. The ACS unit
50
includes an ACS controller
51
, an ACS calculating unit
52
, a first register
53
, delays
54
, first and second memories
55
and
56
, a multiplexer
57
, and a second register
58
.
The first and the second memories
55
and
56
are random access memories (RAMs) for storing state metrics. Each state metric includes 5 bits and 1 quality bit. The first and the second memories
55
and
56
can store 128*12 bits, respectively.
The first register
53
is used for storing a current state metric SM(i+1) from the ACS calculating unit
52
. The second register
58
is used for storing a previous state metric SM(i) from the multiplexer
57
.
The ACS controller
51
generates a write enable signal WEN, an access control signal CSN, and a selection signal S in response to the control signals CTL from the controller
10
. The write enable signal WEN and the access control signal CSN are supplied to the first and the second memories
55
and
56
to write and access the state metrics, respectively. The multiplexer
57
outputs the previous state metric SM(i) stored in the first memory
55
or the second memory
56
to the register
58
in response to the selection signal S. The ACS calculating unit
52
has an adder for adding the state metric SM(i) and branch metric BM(i) to obtain new state metric SM(i+1), a comparator for comparing the new state metric, and a selector for selecting one of the new state metrics SM(i+1) to be output in response to the output of the comparator.
When the input data IN_DATA is input, the branch metric unit
40
calculates the Euclidean distance or the Hamming distance between the received data and a codeword to be transmitted, and supplies the result of the calculation (i.e., branch metric) to the ACS unit
50
. In the ACS calculating unit
52
, the branch metric BM(i) is added to previous state metric SM(i) in the adder according to a trellis diagram, currently received state metrics are compared in the comparator, and small state metrics are selected in the selector. The selected state metrics are stored in the memory
55
or
56
as a current state metric SM(i+1). Meanwhile, selected path information P(i+1) of the current state is stored in a path memory (not shown) after passing through the traceback unit
60
. The traceback unit
60
traces the path information to look for a state having the largest maximum likelihood, finds the most approximate path to that of data sent from a transmitting encoder (not shown), and outputs decoded data DECODED DATA through the output buffer
70
.
FIG. 3
is a trellis diagram illustrating the allowable transitions from state to state for the ACS unit
50
of FIG.
2
. The state metric of an ‘a’ state in the ith stage is expressed as SM
a
i
, and the branch metric from the ‘a’ state in the ith stage to a ‘b’ state in the (i+1) stage is expressed as BM
a,b
i
. In that case, the state metric of the (i+1)th stage is defined as follows:
SM
c
i+1
=min(
SM
a
i
+BM
a,c
i
,SM
b
i
+BM
b,c
i
)  (1)
For example, as shown in
FIG. 3
, the state metric SM
128
i+1
is obtained from the state metrics SM
0
i
and SM
1
i
and the branch metrics BM
0,128
i
and BM
1,128
i
. The process of obtaining the current state metric is called ACS calculating, since adding, comparing and selecting are required to determine the current state metric, as shown in equation (1).
Referring to
FIGS. 2 and 3
, in the ith stage, the first memory
55
stores the state metrics of ‘a’ state in the ith stage SM
a
i
, and the second memory
56
stores the state metrics of ‘b’ state in the (i+1)th stage SM
b
i+1
.
In the ACS unit
50
, the first and the second memories
55
and
56
are initialized at the first stage. After initialization, the state metric SM(i) is read from the first memory
55
to calculate the current state metric SM(i+1). The calculated current state metric SM(i+1) is stored in the second memory
56
. Reading and writing periods of the first and the second memories
55
and
56
are repeated every other stage. Each of the memories
55
and
56
spends 2 clock cycles for the reading/writing operation. Thus, (256+&agr;) clock cycles are needed for 1 stage processing, wherein &agr; is a delay time of the ACS calculating unit
52
.
For example, in the ith stage, the ACS unit
50
calculates SM
0
i+1
and SM
128
i+1
by

Affiliated with

Also associated with

Rating

Add-compare-select circuit for 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 Add-compare-select circuit for viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Add-compare-select circuit for viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3007982