Viterbi decoder and Viterbi decoding method

Details Viterbi decoder and Viterbi decoding method Viterbi decoder and Viterbi decoding method

2000-01-31

2001-07-17

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06263473

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a path trace type Viterbi decoder for use in error correction decoding of convolutional codes and to a Viterbi decoding method.
Viterbi decoders for use in maximum likelihood decoding of convolutional codes find applications in transmission systems susceptible to transmission errors such as satellite communications systems and satellite broadcasting because of their high error correction performance. As demodulating circuits evolve in the rate of operation and in the level of integration, low-power, fast Viterbi decoders are in great demand.
FIG. 14
shows an example of a convolutional code encoder having three shift registers
13
a-c
. This encoder generates from data Y of one bit a convolutional code X
1
of one bit and a convolutional code X
0
of one bit. The shift register
13
a
holds data S
1
that was inputted earlier than data Y by two data items. The shift register
13
b
holds data S
0
that was inputted earlier than data Y by one data item. The shift register
13
c
holds data Y that is the currently-inputted data. Code X
1
is obtained from data S
1
and data Y, which is represented as [
1
+D
2
]. Code X
0
is found from data S
1
, data S
0
, and data Y, which is represented as [
1
+D+D
2
]. The number of shift registers contained in an encoder is the encoder constraint length (the number is three in FIG.
14
).
The state of the encoder shown in
FIG. 14
is determined by two bits, i.e., data S
1
held in the shift register
13
a
and data S
0
held in the shift register
13
b
(the state S
1
S
0
). Codes X
1
and X
0
, which are convolutional codes produced in respective states, are univocally defined according to the input data Y. Suppose that FIG.
15
(a) shows a situation in which codes X
1
and X
0
are outputted when data Y is inputted in the state S
1
S
0
. In this case, the operation of the encoder of
FIG. 14
may be represented by a state transition diagram of FIG.
15
(b). For instance, when data
1
is entered in state
01
,
10
is produced as a convolutional code and, at the same time, the encoder makes a transition to state
11
by the shift operation of a shift register. The number of encoder states is 2
(K−1)
where K is the constraint length of a convolutional code.
The trellis diagram is a diagram in which paths stretching out from respective states are time-arranged in the horizontal direction.
FIG. 16
is a trellis diagram that is prepared on the basis of the state transition diagram of FIG.
15
(b). With reference to
FIG. 16
, solid line arrows extending from the individual states
00
,
01
,
10
, and
11
each indicate a path when input data Y is
0
and broken line arrows each indicate a path when input data Y is
1
. A point corresponding to a state is called a node.
In Viterbi decoding, a path having a distance nearest to a transmitted code series, known in the art as a most likely path, is found on a trellis diagram such as the one shown in
FIG. 16
, and decoding processing is carried out by tracing back the most likely path.
For example, with respect to the point a of the trellis diagram of
FIG. 16
, the encoder is in state
01
. This encoder state results from the fact that data
1
is fed in state
00
or the fact that data
1
is fed in state
10
. The operation of the encoder at this time is shown in FIG.
17
. As can be seen from
FIG. 17
, input of data
1
in state
00
results in a shift-out of data
0
from the shift register. On the other hand, input of data
1
in state
10
results in a shift-out of data
1
from the shift register. The data shifted out becomes a path select (PS) signal indicative of from which of the states the path arrives. In other words, a PS signal becomes
0
when a path arrives from above (i.e., from state
00
) and, on the other hand, it becomes
1
when a path arrives from below (from state
10
).
Accordingly, PS signals at nodes through which the most likely path passes become shifted-out signals from the encoder (previously-input signals) and decoding processing is carried out by tracing back the most likely path to find the PS signals at the nodes.
A commonly-used Viterbi decoder is now described below.
A Viterbi decoder was reported in a paper entitled “A 45-Mbit/sec. VLSI Viterbi Decoder for Digital Video Applications,” IEEE Natl Telesystems Conf. Vol. 1993, p. 127-130, 93. STANFORD TELECOM. In this Viterbi decoder, a multiported memory is divided into four trace-back memories and the operation of each of the trace-back memories is pipelined with a view to achieving a high-speed and low-power Viterbi decoder.
FIG. 18
illustrates in block form the structure of a conventional Viterbi decoder.
801
is an add-compare-select (ACS) circuit for generating path select (PS) signals from input received codes.
802
is a trace-back memory formed of a multiported memory.
803
is a trace-back circuit. 804 is an address generating circuit.
805
is a timing generating circuit for controlling the operation timing of the entire Viterbi decoder. Trace-back memory
802
is divided into four banks (bank
0
, bank
1
, bank
2
, bank
3
). In each bankO-
3
, the data bit width is 2
(K−1)
and the number of words is m, where K is the constraint length of an encoder on the sending side and m is the trace-back length which is used as a trace-back unit in decoding operation.
ACS circuit
801
comprises a branch metric generating means
806
which inputs received codes and generates a plurality of branch metrics, an adder
807
, a comparator
808
, a selector
809
, and a path metric memory
810
for storing a path metric.
With reference to FIG.
19
(a), a way of finding a PS signal by ACS circuit
801
is described. FIG.
19
(a) is a trellis diagram of an encoder with a constraint length of three, showing only paths indicated by PS signals at respective nodes at respective times. The symbol rate, f, represents the time at which the received code is inputted.
An example case of finding a PS signal at node
2
at time (T
0
+f), is explained. The path metric of a path which has the possibility of arriving at node
2
at time (T
0
+f), is first calculated. The path with the possibility of arriving at node
2
at time (T
0
+f) is a path which passes node
1
or node
3
at time T
0
. Suppose that the path metric of a path that passes through node
1
at time T
0
is PM
1
and the path metric of a path that passes through node
3
at time T
0
is PM
3
. The path metrics are stored in path metric storing means
810
.
Branch metric generating means
806
generates a plurality of branch metrics for received codes which were entered at time (T
0
+f). Suppose that the branch metric at the time of branching from node
1
to node
2
is BM
12
and the branch metric at the time of branching from node
3
to node
2
is BM
32
. At this time, the path metric of a path that reaches node
2
by way of node
1
is (PM
1
+BM
12
) and the path metric of a path that reaches node
2
by way of node
3
is (PM
3
+BM
32
). These add operations are performed in adder
807
.
The more likely Path has a lower metric. Two path metrics of two paths are compared in comparator
808
. Comparator
808
produces a PS signal corresponding to a path having a smaller path metric. In response to the PS signal received from comparator
808
, selector
809
selects a path metric which is then stored in path metric storing means
810
.
Since a path, which reaches node
2
by way of node
1
, is selected at node
2
in time (T
0
+f), the PS signal is
0
. ACS circuit
801
performs arithmetic operations of PS signals for the respective nodes when the received code is inputted. For this reason, the number of bits of a PS signal produced from ACS circuit
801
is equal to the number of nodes, that is, the number of states of the encoder. In
FIG. 19
, the number of nodes is
4
, for the encoder constraint length is three. Accordingly, the number of PS signal bits becomes four. As shown in FIG.
19
(b), the output PS signals

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2436615