Trellis decoder with soft decision outputs

Details Trellis decoder with soft decision outputs Trellis decoder with soft decision outputs

1998-02-04

2001-04-24

Vo, Don N. (Department: 2631)

Pulse or digital communications

Systems using alternating or pulsating current

Plural channels for transmission of a single pulse train

C375S341000, C714S792000

Reexamination Certificate

active

06222889

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates generally to trellis decoders and more particularly to trellis decoders which produce soft decision (SD) outputs.
As is known in the art, trellis decoders are used in receivers of digital communication systems to reduce or eliminate errors caused by noise or distortion in a communication channel through which a sequence of data is transmitted. With such system, a coder is provided at the transmitter to encode the sequence of data into a sequence of symbols, each symbol representing an allowed transition from an originating trellis state of a state machine to a limited number of terminating trellis states. Referring to
FIG. 1
, the allowed transitions are shown for a state machine adapted to have four trellis states: S
1
, S
2
, S
3
, and S
4
. The coder encodes the sequence of data into a sequence of symbols; here symbols A
1
, A
2
, A
3
, and A
4
, such that:
symbol A
1
, represents an allowed transition from originating state S
1
to terminating state S
1
, as a result of an input X, here 0, and from originating state S
2
to terminating state S
3
as a result of an input Y, here 1;
symbol A
2
represents an allowed transition from originating state S
3
to terminating state S
4
as a result of an input Y, here 1, and from originating state S
4
to terminating state S
2
as a result of an input X, here 0;
symbol A
3
represents an allowed transition from originating state S
1
to terminating state S
3
as a result of an input Y, here 1, and from originating state S
2
to terminating state S
1
as a result of an input X, here 0 and
symbol A
4
represents an allowed transition from originating state S
3
to terminating state S
2
as a result of an input X, here 0 and from originating state S
4
to terminating state S
4
as a result of an input Y, here 1.
It should be noted that the current, (i.e., originating), state and the input value (i.e X or Y) specifies which symbols out of the entire set of symbols, here A
1
, A
2
, A
3
and A
4
, may validly appear next in the sequence of transmitted symbols (i.e., the terminating state, or node, N). (For example, originating State S
1
specifies that only symbols A
1
and A
3
may validly appear next in the sequence of symbols to be transmitted.) Thus, only selected sequences of transmitted symbols are permitted by the coding scheme. These permitted sequences are referred to as branches, here in this example, branches B
1
-B
8
in a trellis diagram shown in FIG.
1
. Thus, each branch is defined by the originating state, the input value, the terminating state, and the symbol which uniquely represents the transition between such states. Thus, for example, from state S
1
with an input value of Y, here 1, the only branch traversed is B
2
to terminating state S
3
, and the only valid symbol which may exist in this transition through branch B
2
is the symbol A
3
. (Note that irrespective of the starting (or initiating) state, two consecutive X inputs (i.e., here two consecutive inputs of 0) will bring the trellis to state S
1
, as this is a property of the trellis in this example, FIG.
2
. Thus, the trellis shown in
FIG. 1
, having four trellis states S
1
-S
4
has two memory states MS, where 2
MS
=the number of trellis states).
Consider, as an example, that the symbols A
1
, A
2
, A
3
, and A
4
are represented by values as follows: A
1
=(+2, +2); A
2
=(−2, +2); A
3
=(−2, −2); and A
4
=(+2, −2). Further, let the following sequence of input values is to be transmitted:
{X, X, X, Y, Y, Y, X, X, Y, X, X},
i.e., here,
{0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0}.
Assuming that we started at the start state S
3
, then the output from the encoding mapping process will result in the output symbols:
{A
4
, A
3
, A
1
, A
3
, A
2
, A
4
, A
4
, A
2
, A
3
, A
3
, A
4
, A
3
},
i.e., here,
{(+2, −2), (−2, −2), (+2, +2), (−2, −2), (−2, +2), (+2, −2), (−2, +2), (−2, −2), (−2, −2), (+2, −2), (−2, −2)}.
However, because noise and/or distortion in the communication channel, let it be assumed that the signals sequentially received at the receiver are:
{(+2, −2), (−2, −2), (+2, +2), (−2, −2), (−2, +2), (+1, −1), (−2, +2), (−2, −2), (−2, −2), (+2, −2), (−2, −2)}.
It is noted that while all the received symbols except one are correct, the sixth symbol, (i.e., the signal (+1, −1)) is not one of the values of the symbols in the set because of channel noise and/or distortion. A trellis decoder at the receiver is used to determine the sixth received “corrupted” symbol.
In order to decode the received sequence, one obvious method is the brute-force method whereby one forms an expected output symbol sequence of {A
1
, A
2
, A
3
, A
4
} for every possible input sequence values of X and Y, and compares these with the received sequence of {A
1
, A
2
, A
3
, A
4
}. It is obvious that the locally generated sequences which best matches the received sequence for a given criteria is the best estimate of the original input sequence. However, it is clear that the number of possible output sequences grows non-linearly (i.e., by the power of 2) as the number of states and length of the input sequence growths. Thus this brute-force method is not optimal in terms of computational efficiency.
In order to increase the computational efficiency and keeping the optimality criteria, one can adopt a different strategy. The trellis decoder shown in
FIG. 4
, determines, in this example, a “branch metric” for each of the branches in the trellis. The branch metric is the Euclidian distance, D, between the value of a received signal at a given time and the value represented by a symbol in the set of symbols, i.e., if (a,b) represents one of the valid set of symbols (A
1
, A
2
, A
3
A
4
), and (c,d) represents the received symbol, then the Euclidian distance (D) is given by D=(a-c)
2
+(b-d)
2
. Thus, in proceeding from one transition to the next transition, the processes that are required to be performed can be summarized as:
(i) For every starting state SI and corresponding end state S
E
compute the Euclidian distance D between the expected transition output symbol and the received symbol where the expected symbols take on the values {A
1
, A
2
, A
3
, A
4
} as defined. This is carried out by a Branch Metric Calculation (BMC) Generation Unit.
(ii) For every starting state SI and corresponding end state S
E
compute the sum of the branch metric (D) calculated in step (i) and the Accumulated Path Metric (APM) memory retained for that particular starting state S
I
from the previous transition. This is sum-compare-select function is performed by an Add-Compare-Select (ACS) unit.
(iii) For each end state, retain only the transition which has produced the lowest sum G from all the possible start states to reach the end state S
E
and store it back in the Accumulated Path Metric (APM) memory.
(iv) Repeat the procedure (i) to (iii) for every received symbol.
The above decoding procedure is generally known as the Viterbi Algorithm and is applicable for the decoding of any type of coding which follows a pre-determined trellis. The Viterbi algorithm for sequence detection is described in the IEEE Transactions on information Theory, Vol. IT-13, pp. 260-269 (April 1967). Thus all forms of convolutional coding and types channel modelling can use the Viterbi Algorithm for data recovery.
Thus, in this example, and referring also to
FIG. 3
, one can compute a table of values as given below to decode the received sequence of symbols to give an estimate of the original sequence of inputs. It is assumed that the starting state is S
3
.
Frame 1: (+2, −2)
Expected
Distance
Initial
Final
S
E
S
I
symbol
D
APM
APM
Keep?
S
1
S

Affiliated with

Also associated with

Rating

Trellis decoder with soft decision outputs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Trellis decoder with soft decision outputs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trellis decoder with soft decision outputs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2455413