State metric memory of viterbi decoder and its decoding method

Details State metric memory of viterbi decoder and its decoding method State metric memory of viterbi decoder and its decoding method

1998-12-29

2002-02-26

Ton, David (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S796000

Reexamination Certificate

active

06351839

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a digital communication system, and more particularly to a state metric memory of a viterbi decoder for a digital communication system.
2. Discussion of Related Art
Generally, a viterbi decoder is frequently used in a transmission-reception apparatus for decoding via an optimal path in fields of a satellite communication and a digital communication. The viterbi decoder is a fairly recent technique and is shown in FIG.
1
(
a
). The viterbi decoder generally includes a branch metric calculator
10
calculating branch metrics from received code symbols and voluntary hypotheses by using a look-up table; an adder/comparator/selector (ACS)
20
adding the branch metrics and the current-state metrics, comparing path metrics, and selecting an optimal path metric; a memory
30
reading and writing the current-state metrics and the next-state metrics; and an address generator
40
selectively generating control signals for designating addresses of the memory to read and write the current or next-state metrics.
In a viterbi decoding method, a trellis diagram is built for all the transmitted code symbols. In the trellis diagram, the distance values of each node corresponding to input data are calculated and the distance values for each potential paths for decoding are accumulated. The path having a minimum accumulated distance value, i.e. the minimum evaluation quantity is determined to be a survival path.
The addresses of the viterbi decoder are generated through a process in which the current state metrics are read out from the memory according to a fixed period, thereby renewing the addresses for the next state metrics. Thus, the next state metrics are written into the renewed addresses of the memory.
To designate the optimal next-state metrics to be written according to the fixed period after the current-state metrics has been read, eight reading and writing operations must be executed. For example, (
000
,
001
→
000
), (
010
,
011
→
001
), (
100
,
101
→
010
), (
110
,
111
→
011
), (
000
,
001
→
100
), (
010
,
011
→
101
), (
100
,
101
→
110
) and (
110
,
111
→
111
) are executed in order to actively perform all state transitions as shown in the trellis diagram of FIG.
2
.
The state metrics in the eight states generated through the above eight reading and writing operations are regarded as the current-state metrics and the eight reading and writing operations are repeated again for a set of next state metrics. For a smooth implementation of this repeated state exchange of the metrics, the memory must store, at any given point of time, all the current-state metrics read according to the fixed period and must also have memory space for storing the next-state metrics written according to the fixed period.
Thus, if the memory space capable of storing all the current-state metrics is N, the memory requires additional memory space of N for writing the next-state metrics. In other words, the memory space capacity must overall be
2
N to completely accomplish the above repeated state exchange of the metrics.
The states in the trellis diagram of
FIG. 2
are limited by a constraint length. The number of stages in the encoder, which is equal to one more than the number of delay elements, is known as the constraint length. Supposing that C is the constraint length, the states exist in a range between “0” and “2
c-1
-1”. Thus, the constraint length in the trellis diagram of
FIG. 2
would be four resulting in eight states.
The operations of the state metric memory in the viterbi decoder as shown in FIG.
1
(
a
) will be described in reference to FIG.
2
. The memory
30
includes four submemories M
100
to M
400
as shown in FIG.
1
(
b
). All four memories are necessary for the current-state metrics read according to the fixed period and the next-state metrics written according to the fixed period.
Particularly, the first and second memories M
100
, M
200
are for the current-state metrics, and third and fourth memories M
300
, M
400
are for the next-state metrics. After a conversion from the current-states to the next-states, as shown in
FIG. 2
, the first and second memories M
100
, M
200
write the metrics of the next-states while the third and fourth memories M
300
, M
400
read the metrics of the current-states.
Also, the address generator
40
includes a counter
41
and a controller
42
controlling the counter
41
. The address generator
40
outputs control signals for designating a domain of the memory. The metrics of the first current-states
0
=000 and
1
=001, stored initially in the first and second memories M
100
, M
200
are read by according to the control signals output from the address generator
40
and are input to the ACS
20
.
Utilizing a look up table, the ACS
20
adds the branch metrics calculated from the code symbols and hypotheses transmitted within a fixed period, and the metrics of the current-states
0
=000 and
1
=001, respectively. The ACS compares summed path metrics of the metrics and selects an optimal path metric having the minimum evaluation quantity, thereby producing each path metrics. Such optimal path metric is the survival path metric and is written in the third memory M
300
as the next-state ‘
0
=000.’
Upon completion of the above process, the address generator
40
reads the metrics of the following current-states
2
=010 and
3
=011, stored at the first and second memories M
100
and M
200
, and writes a second survival path metric in the fourth memory M
400
as the next-state ‘
1
=001’ through the same process as the above process. Similarly, the remaining current-state metrics of the first and second memories M
100
and M
200
are read continuously according to a fixed period, and the selected survival path metrics are written according to the fixed period in the third and fourth memories M
300
and M
400
, respectively, as the next-states through the process as discussed above.
During the process, the current-state metrics of the first and second memories M
100
and M
200
are read according to the control signals in a fixed period. The survival path metrics are sequentially written in the third M
300
and fourth M
400
memories as the next-states, thereby a first 8-state transition process is completed.
FIG. 3
shows a sequential state transition process of the state metric memory based upon the conventional technique.
Referring to
FIG. 3
, the first eight current-state metrics are read from memories M
100
and M
200
by a fixed period, and are sequentially and alternately written into memories M
300
and M
400
by the fixed period. The eight current-state metrics are assigned to the next-state metrics by a designated sequence in a fixed period as follows {
000
and
001
→
010
and
011
→
100
and
101
→
110
and
111
→
000
and
001
→
010
and
011
→
100
and
101
→
110
and
111
}.
In assigning the current-state metrics, the first next-state metric of
0
′ is designated to assign the first current-state metrics
0
=000 and
1
=001 from the memories M
100
, M
200
to the third memory M
300
. A second current-state metrics
2
=010 and
3
=011 from the memories M
100
and M
200
are designated to a second next-state metric
1
′ in the fourth memory M
400
. A third current-state metrics
4
=100 and
5
=101 from the memories M
100
and M
200
are designated to a third next-state metric
2
′ in the third memory M
300
. A fourth current-state metrics
6
=110 and
7
=111 from the memories M
100
and M
200
are designated to a fourth next-state metric
3
′ in the fourth memory M
400
.
The address generator
40
generates control signals to output the metrics of the first and second current-state metrics
0
=000,
1
=001 from the first and second memories M
100
, M
200
in a predetermined order as discussed above and shown in FIG.

Affiliated with

Also associated with

Rating

State metric memory of viterbi decoder and its 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 State metric memory of viterbi decoder and its decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and State metric memory of viterbi decoder and its decoding method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2974444