Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-09-29
2003-11-25
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S792000, C714S794000, C714S796000, C375S262000, C375S341000
Reexamination Certificate
active
06654929
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a technique on Viterbi decoding for decoding a trellis-coded modulated signal.
As a conventional configuration for decoding a trellis-coded modulated signal, a Viterbi decoder as shown in
FIG. 13
has been proposed (Japanese Laid-Open Patent Publication No. 5-335972; corresponding U.S. Pat. No. 5,509,021).
FIG. 11
shows a trellis encoder that generates the trellis-coded modulated signal to be decoded by the above conventional decoder.
FIG. 12
is a trellis diagram for the trellis encoder in FIG.
11
. The trellis encoder in
FIG. 11
has an encoding rate of ¾ with one noncoding bit and a constraint length of 4. Therefore, this trellis encoder has 2
(4−1)
=8 states that are represented by values of registers D
2
, D
1
, and D
0
of the encoder, that is, {000}, {001}, {010}, {011}, {100}, {101}, {110}, and {111}. In addition, the values of outputs {y
2
, y
1
, y
0
} of the encoder constitute a subset, and the value of this bit string as binary notation is herein defined as the number of this subset. For example, if {y
2
, y
1
, y
0
}={1, 0, 1}, the subset number is “5”, and this subset is referred to as “subset s5”. Such subsets s
0
through s
7
are called subsets A through H in the aforementioned prior art.
The operation of the Viterbi decoder in
FIG. 13
is as follows.
A branch metric generator
601
determines Euclidean distances between a reception signal point and respective transmission symbol points, and outputs the results as branch metrics “BMs” (“s” denotes any of the subset numbers
0
to
7
). One subset includes two transmission symbol candidates. A branch metric corresponding to the transmission symbol string of which the noncoding bit is “0” is denoted by BMs
0
, while a branch metric corresponding to the transmission symbol string of which the noncoding bit is “1” is denoted by BMs
1
.
A subset maximum likelihood estimator
602
selects one of the two transmission symbol candidates of each subset that has a smaller Euclidean distance, and outputs the selected one as the branch metric BMs for the subset concerned.
A noncoding bit detector
603
extracts the noncoding bit in each selected transmission symbol candidate based on the selection information output from the subset maximum likelihood estimator
602
, and outputs the extracted noncoding bit. The noncoding bits are then delayed by j-level shift registers
604
by j levels that correspond to the number of delay levels in a path memory circuit
607
.
An add-compare-select (ACS) circuit
605
adds the branch metrics output from the subset maximum likelihood estimator
602
to path metrics of survivor paths in each state at time t−1, that is, in a state before transition to a state at time t in the trellis diagram shown in FIG.
12
. The ACS circuit
605
then selects one of the added values that has the highest likelihood as a path metric PM
0
to PM
7
of the survivor path. Simultaneously, the selection information is output as a select signal PS
0
to PS
7
.
FIG. 14
is a block diagram of a basic unit of the ACS circuit. For simplifying the description,
FIG. 14
illustrates only a basic unit corresponding to state i. In the case of the above conventional decoder, since the number of states is 8, a total of eight basic units with the configuration shown in
FIG. 14
are arranged in parallel in the ACS circuit
605
.
Adders
700
a
to
700
d
receive path metrics PMa to PMd and branch metrics BMa to BMd in accordance with the trellis diagram shown in FIG.
12
. The respective added results a to d are input into a comparator
701
. The comparator
701
compares the added results a to d, selects one having the highest likelihood, and outputs a select signal PSi representing the selected result. Specifically, if the added result a is selected, “0” is output. Likewise, if the added results b, c, and d are selected, “1”, “2”, and “3” are output, respectively. A selector
702
receives the added results a to d and the select signal PSi, and outputs to a register
703
one of the added results that corresponds to the select signal PSi as a new path metric PMi for state i.
The order of {(PMa,BMa), (PMb,BMb), (PMc,BMc), (PMd,BMd)} input into the basic unit is set as follows for the respective states in the above conventional decoder.
<State 0>
{(PM
0
,BM
0
), (PM
2
,BM
4
), (PM
4
,BM
2
), (PM
6
,BM
6
)}
<State 1>
{(PM
0
,BM
4
), (PM
2
,BM
0
), (PM
4
,BM
6
), (PM
6
,BM
2
)}
<State 2>
{(PM
0
,BM
2
), (PM
2
,BM
6
), (PM
4
,BM
0
), (PM
6
,BM
4
)}
<State 3>
{(PM
0
,BM
6
), (PM
2
,BM
2
), (PM
4
,BM
4
), (PM
6
,BM
0
)}
<State 4>
{(PM
1
,BM
1
), (PM
3
,BM
5
), (PM
5
,BM
3
), (PM
7
,BM
7
)}
<State 5>
{(PM
1
,BM
5
), (PM
3
,BM
1
), (PM
5
,BM
7
), (PM
7
,BM
3
)}
<State 6>
{(PM
1
,BM
3
), (PM
3
,BM
7
), (PM
5
,BM
1
), (PM
7
,BM
5
)}
<State 7>
{(PM
1
,BM
7
), (PM
3
,BM
3
), (PM
5
,BM
5
), (PM
7
,BM
1
)}
The path select signals PS
0
to PS
7
output from the ACS circuit
605
are input into the path memory
607
.
FIG. 15
illustrates the path memory
607
, which is basically configured to concretize the transitions to respective nodes in the trellis diagram. Registers disposed at positions corresponding to the nodes store values selected among those output from the immediately preceding registers in accordance with the respective path select signals PS
0
to PS
7
.
At the first level, the subset number itself is selected by the path select signal PSi. Accordingly, the subset numbers at each branch in the trellis diagram in
FIG. 12
are input into a selector
800
. For example, in state 0, when the path select signal PS
0
is “0”, (PM
0
,BM
0
) has been selected. Therefore, the selector
800
outputs the subset number “0”, which is stored in a register
801
. Likewise, when the path select signal PS
0
is “1”, “2”, and “3”, the selector
800
outputs the subset number “4”, “2”, and “6”, respectively. In states 1 to 7, also, the selector
800
outputs a subset number x corresponding to each of the path select signals PS
1
to PS
7
. The output results are stored in the respective registers
801
.
At the second level, a value stored in a register corresponding to the node number at the first level is selected. For example, in state 0, when the path select signal PS
0
is “0”, (PM
0
,BM
0
) has been selected. Therefore, a selector
802
outputs the content of the register corresponding to state 0 at the first level, which is then stored in a register
803
. Likewise, when the path select signal PS
0
is “1”, “2”, and “3”, the selector
802
outputs the content of register
2
,
4
, and
6
, respectively. In states 1 to 7, also, the selector
802
outputs the content of register x at the first level corresponding to the state number x represented by the value of each of the path select signals PS
1
to PS
7
. The output results are stored in the respective registers
803
.
The above configuration at the second level is repeated for the third and subsequent levels until the j-th level. In this way, values are shifted from the first level through the j-th level for j clocks. Thus, a value stored in register n at the j-th level is equal to the subset number in the state through which the survivor path in state n has passed j time points earlier. The outputs from the registers at the j-th level are input into a selector
608
.
A most likely path decision circuit
606
receives the outputs PM
0
to PM
7
from the registers of the respective basic units of the ACS circuit
605
, detects the state having the highest likelihood among the inputs, and outputs the number of the detected state. Selector
608
receives the output of the most likely path decision circuit
606
and selects the corresponding register output value. The register output value is equal to the subset number that will be obtained b
De'cady Albert
McDermott & Will & Emery
Torres Joseph D.
LandOfFree
Viterbi decoder and Viterbi decoding method 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 and Viterbi decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder and Viterbi decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172862