Viterbi decoder

Details Viterbi decoder Viterbi decoder

1998-06-10

2002-01-29

Pham, Chi (Department: 2631)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

Reexamination Certificate

active

06343105

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a viterbi decoder used for mobile communication, satellite communication, and a memory device and, more particularly, to a viterbi decoder for time-divisionally performing series arithmetic processing in an ACS (Add-Compare-Select) circuit.
2. Description of the Prior Art
A viterbi decoder is used for maximum likelihood decoding of convolution codes to select, as a maximum likelihood path, a path whose inter-code distance is the nearest to, of a plurality of known code sequences, a reception code sequence and to set data corresponding to the selected path as decoded data.
Conventional viterbi decoders are classified into a scheme (parallel scheme) of performing calculation and comparison of path-metric values in the ACS circuit parallel for all states by arranging ACS circuits equal in number to states, and a scheme (series scheme) of time-divisionally performing series arithmetic processing in the ACS circuit by one ACS circuit.
For example, Japanese Examined Patent Publication No. 1-44058 discloses a viterbi decoder for pipeline processing in an ACS circuit in order to increase the throughput of the viterbi decoder. This viterbi decoder is of the parallel scheme in which ACS circuits are arranged equal in number to states. By doubling the numbers of adders and metric memories in each ACS circuit, pipeline processing of comparing the path-metric values of previous sum outputs by a comparator in a decoding cycle of adding outputs by an adder is realized.
Japanese Examined Patent Publication No. 3-49217 also discloses a viterbi decoder for pipeline processing in an ACS circuit in order to increase the throughput of the viterbi decoder. This viterbi decoder is also of the parallel scheme in which ACS circuits are arranged equal in number to states. Pipeline processing is realized on the decoder side by encoding transmission information sequences after dividing them into even sequences and odd sequences on the encoder side. In a convolution encoder, one conventional delay flip-flop is replaced with two shift registers. In the viterbi decoder, one clock delay circuit is inserted between an adder group and a comparator/selector group. With this arrangement, pipeline processing of separately executing addition and comparison/selection using one clock is realized.
A viterbi decoder of time-divisionally performing series arithmetic processing in a conventional ACS circuit will be explained. This prior art will exemplify decoding of a convolution code with a code ratio R=1/2 and a guide distance K=3. The number of states in the viterbi decoder is therefore four. The arrangement of the viterbi decoder will be first explained.
FIG. 1
is a block diagram showing a path-metric calculation unit
12
and a minimum path-metric value detector
13
in a viterbi decoder of time-divisionally performing series arithmetic processing in a conventional ACS circuit.
The path-metric calculation unit
12
is a so-called ACS circuit, which adds, compares, and selects path-metric values. The path-metric calculation unit comprises a path-metric X memory
20
and a path-metric Y memory
21
, which store the path-metric values of the respective states, subtracters
22
and
23
for respectively subtracting the minimum path-metric value during one previous decoding time from path-metric values read out from the path-metric memories
20
and
21
, adders
24
and
25
for respectively adding branch metrics X and Y and outputs from the subtracters
22
and
23
, a comparator
26
for comparing outputs from the adders
24
and
25
, and a selector
27
for selecting a smaller one of outputs from the adders
24
and
25
.
The minimum path-metric value detector
13
constitutes a comparator
30
for comparing an updated path-metric value as an output from the selector
27
with an output from a flip-flop (FF)
32
, a selector
31
for selecting a smaller one of outputs from the selector
27
and the FF
32
in accordance with an output from the comparator
30
, the FF
32
for holding an output from the selector
31
at the leading edge of a clock signal CLK, and a level-through latch
33
for holding an output from the FF
32
in accordance with a minimum value update signal.
The operation of this viterbi decoder will be described.
FIG. 2
is a timing chart of the viterbi decoder in FIG.
1
. Since the number of states is four, one decoding time is made up of four clocks during which path-metric values corresponding to states “0” to “3” are calculated for a pair of reception signals. A calculation operation for a path-metric corresponding to state “0” will be explained. A branch metric as the calculation result of the Hamming distance between reception data and a candidate value is input to the path-metric calculation unit
12
. Branch metrics X and Y corresponding to two paths conceivable for one state are respectively input to the adders
24
and
25
. Branch metrics obtained from candidate values corresponding to transmission from state “0” and state “2” are used for path-metric calculation of state “0”. Path-metric values corresponding to the four states are respectively stored in the path-metric X memory
20
and the path-metric Y memory
21
. Their contents are the same though (states corresponding to) path-metric values read out at the same timing are different. To calculate the path-metric value of state “0”, a path-metric value corresponding to the previous state “0” and a path-metric value corresponding to state “2” are respectively read out from the path-metric X memory
20
and the path-metric Y memory
21
. The minimum path-metric value during one previous decoding time is subtracted from the readout path-metric values by the subtracters
22
and
23
in order to prevent the path-metric value from increasing infinitely. The branch metric X and an output from the subtracter
22
are added by the adder
24
, whereas the branch metric Y and an output from the subtracter
23
are added by the adder
25
. A smaller one of the sums is selected by the comparator
26
and the selector
27
and output as an updated path-metric value to the path-metric X memory
20
, the path-metric Y memory
21
, and the minimum path-metric value detector
13
. The updated path-metric value is stored as the path-metric value of state “0” in the path-metric X memory
20
and the path-metric Y memory
21
. The path-metric values of states “1”, “2”, and “3” are similarly calculated. When the updated path-metric value of state “0” is input to the minimum path-metric value detector
13
, it is unconditionally selected by the selector
31
and held by the FF
32
at the leading edge of the clock signal CLK. Upon reception of the updated path-metric value of state “1”, it is compared with the path-metric value of the previous state (state “0”) by the comparator
30
. A smaller value is selected by the selector
31
and held by the FF
32
at the leading edge of the clock signal CLK. The same operation is performed upon reception of the updated path-metric values of states “2” and “3”. The minimum one of the path-metric values of the four states is held by the latch
33
in accordance with a minimum value update signal generated every decoding time.
As described above, the conventional viterbi decoder must perform, within the duration of one clock, (1) read of path-metric values from the memories
20
and
21
, (2) subtraction of the minimum path-metric value from a pair of previous reception signals by the subtracters
22
and
23
, (3) addition of branch metrics by the adders
24
and
25
, (4) selection of a smaller value by the comparator
26
and the selector
27
, (5) storage of the updated path-metric value in the memories
20
and
21
, (6) update of the minimum candidate path-metric value by the comparator
30
, the selector
31
, and the FF
32
, and (7) update of the minimum path-metric value by the latch
33
at the last clock (fourth clock) during the one decoding time.
The viterbi decoders in Japanese Examined Patent

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-2837469