ACS unit for a viterbi decoder

Details ACS unit for a viterbi decoder ACS unit for a viterbi decoder

2002-07-16

2004-11-02

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C375S262000

Reexamination Certificate

active

06813744

ABSTRACT:

TECHNICAL FIELD
The present invention relates to an ACS unit (Add Compare Select) as claimed in the preamble of claim
1
for a Viterbi decoder, which can be used in particular in mobile radio receivers for decoding channel-coded mobile radio signals.
BACKGROUND ART
A Viterbi decoder is used in most known digital mobile radio receivers. A Viterbi decoder is what is referred to as a maximum likelihood decoder, which is generally used for decoding channel-coded, in particular convolution-coded, mobile radio signals. During the channel coding process, redundant information is added in the transmitter to the symbols to be transmitted, in order to increase the transmission reliability. However, when a mobile radio signal is transmitted, noise is superimposed on it. The object of the receiver is thus to use the received sequence to find from all the possible transmission sequences that transmission sequence which most probably corresponds to the actual transmission sequence. This object is carried out by the Viterbi decoder.
The coding rule used for channel coding can be described by a corresponding trellis diagram. The Viterbi decoder calculates what are referred to as metrics to determine that path in the trellis diagram which has greatest or smallest path metric depending on the respective configuration of the decoder. The decoded sequence can then be determined and emitted, on the basis of this path in the trellis diagram.
The principles of Viterbi decoding will be explained in more detail, briefly, in the following text.
By way of example,
FIG. 4
shows a trellis diagram in each case having four different states at the times t . . . t+3, which correspond, for example, to the bit states ‘00’, ‘10’, ‘01’ and ‘11’. Each symbol sequence is allocated a corresponding path in the trellis diagram. A path in this case comprises a sequence of branches between two successive states in time. Each branch in this case symbolizes a state transition between two successive states in time, with, for example, the upper branch originating from one state corresponding to a received symbol with the binary value ‘0’, and the lower branch originating from the same state corresponding to a received symbol with the binary value ‘1’. Each of these state transitions, to which a branch metric (BM) &lgr;
t
is assigned, corresponds to a transmitted symbol. The branch metric &lgr;
t
is defined as follows:
&lgr;
1
=|y′
1
−r
1
2
|
In this case, r
t
corresponds to the received symbol at the time t, and y′
t
corresponds to the expected transmitted symbol, as a function of this, at the time t.
Furthermore, each path through the trellis diagram is assigned a path metric &ggr;
t
until the time or time step t.
The trellis diagram illustrated in
FIG. 4
is, in particular, a trellis diagram with what is referred to as a butterfly structure. This means that two states of a time step t+1 in the trellis diagram are in each case assigned two states from the previous time step t, whose branches each lead to the first-mentioned states in the time step t+1, with two branch metrics of the branches originating from different states in each case being identical. Thus, for example, the states shown in
FIG. 4
, to which the path metrics &ggr;
t
(1)
, &ggr;
t
(3)
, &ggr;
t−1
(2)
and &ggr;
t+1
(3)
are assigned, form such a butterfly structure, with the branch metric for the branch from the state with the path metric &ggr;
t
(1)
to the state with the path metric &ggr;
t+1
(2)
corresponding to the branch metric &lgr;
t
(3)
of the branch from the state with the path metric &ggr;
t
(3)
to the state with the path metric &ggr;
t−1
(3)
while, on the other hand, the branch metric of the branch from the state with the path metric &ggr;
t
(1)
to the state with the path metric &ggr;
t+1
(3)
corresponds to the branch metric &lgr;
t
(1)
of the branch from the state with the path metric &ggr;
t
(3)
to the state with the path metric &ggr;
t+1
(2)
. In this case, in general form, &ggr;
t
(s)
denote the path metric assigned to the state s in the time step t, while &ggr;
t
(S)
denotes the branch metric of the state transition, corresponding to the signal s, at the time t.
The Viterbi decoder now has to use the trellis diagram to determine that path which has the best path metric. In general, by definition, this is the path with the smallest path metric.
Each path metric of a path leading to a specific state is composed of the path metric of a previous state in time and of the branch metric of the branch leading from this previous state to the specific state. This means that there is no need to determine and evaluate all the possible paths and path metrics in the trellis diagram. Instead of this, that path which has the best path metric up to this time is determined for each state and for each time step in the trellis diagram only this path, which is referred to as the survivor path, and its path metric need be stored. All the other paths which lead to this state can be ignored. Accordingly, during each time step, there are a number of such survivor paths corresponding to the number of different states.
The above description makes it clear that the calculation of the path metric &ggr;
t+1
(s)
depends on the path metrics of the path metrics of the previous time step t connected to the state s via one branch. The path metrics can accordingly be calculated by means of a recursive algorithm, which is carried out by what is referred to as an Add Compare Select unit (ACS unit) in a Viterbi decoder.
FIG. 5
shows the typical configuration of a Viterbi decoder. In addition to the ACS unit, the Viterbi decoder has a branch metric unit (BMU) and a survivor memory unit. The object of the branch metric unit is to calculate the branch metrics &ggr;
t
(s)
, which are a measure of the difference between a received symbol and that symbol which causes the corresponding state transition in the trellis diagram. The branch metrics calculated by the branch metric unit are supplied to the ACS unit in order to determine the optimum paths (survivor paths), with the survivor memory unit storing these survivor paths so that, in the end, decoding can be carried out on the basis of that survivor path which has the best path metric. The symbol sequence associated with this path has the highest probability of corresponding with the actually transmitted sequence.
A processor element
1
in a conventional ACS unit can be designed as shown by way of example in FIG.
6
. In this case, it is assumed that each state in the trellis diagram is evaluated by a separate processor element
1
. The task of the processor element
1
is to select from two mutually competing paths which lead to one state in the trellis diagram that path which has the best, that is to say lowest, path metric. The stored values for the survivor path leading to this state, and its path metric, are then updated.
As can be seen from the trellis diagram shown in
FIG. 4
, each state s at the time t+1 is connected via an upper branch and a lower branch to a corresponding previous state. In order to determine the survivor path corresponding to this state s, the path metric of the path leading via the upper branch to the state s must therefore be compared with the path metric of the path leading via the lower branch to the state s, that is to say the task of the processor element
1
shown in
FIG. 6
, in order to determine the survivor path with the path metric &ggr;
t+1
(s)
is to select either the path which leads via the previous ‘upper’ state with the path metric &ggr;
t
(0)
and the ‘upper’ branch with the path metric &lgr;
t
(0)
and whose path metric corresponds to the sum &ggr;
t
(0)
+&lgr;
t
(0)
or the path which leads via the lower state with the path metric &ggr;
t
(1)
and the lower branch with the branch metric &lgr;
t
(1)
and whose path metric corresponds to the sum &ggr;
t
(1)
+&lgr;
t
(1)
.
The operation of the processor element described above can in consequence be carri

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3345773