Download RLE-TR-450-047433

Transcript
to examine at box 1 by setting a subscripted variable LI(N) to the likelihood of the branch to be
tried next.
In Fig. A-2, we draw a distinction between the two kinds of boxes in the word flow diagram
by drawing the question boxes as diamonds.
of two algebraic expressions,
inequality.
All questions must be formulated as comparison
with the routes leaving the diamond labeled with the appropriate
The other boxes, where operations are carried out, can almost always be formulated
in terms of evaluating an algebraic expression and assigning this value to a variable.
After all the boxes have been numbered, a translation to Fortran can be made.
Each diamond
box becomes an IF statement, and each of the other boxes will usually be a series of assignment
statements, terminated by a GO TO n statement,
box in the flow diagram.
where n is the number assigned to the next
The Fortran statements for each box are then written down, labeling
the first statement with the box number.
These groups of statements may be written down in
any order, but following more or less the same order as the flow diagram enables removal of
many GO TO statements and the use of the IF statement of one argument, since the following
statements are those to be executed next.
Fortran program shown in Fig. A-3.
Making this translation, we obtain the skeleton
Clearly,
statement labels 2, 3, 4, 6, 9, 13, 14, 15, 16, 17
and 19 are unnecessary since they are never used in a GO TO or an IF; however,
since they
do no harm, we shall leave them.
2.
Statements for Metric and Coder
Before going further, we must specialize the algorithm to a particular tree structure and
metric function.
We will use the example of a binary tree, alphabet of 8,
ordered list length
of 4, and a metric that is only a function of the position of the hypothesis on the list.
now add to the skeleton program, obtaining the program shown in Fig. A-4.
We shall
The additions will
be made by inserting statements according to type rather than by starting at the beginning of
the program and working forward.
The evaluation of the metric increase LMBD takes place at statement 1 in the program, and
for a given hypothesis consists only of getting a value from a table, say IDIST, of 4 + 1 = 5
entries, where the index to be used on the table is the position of the hypothesis on the ordered
list.
(If not on the list, use 5 as the index.)
POS of the LI(N)
th
most likely branch.
We can use the subroutine FIND to get the position
When we compute LMBD for a branch, we must save this
value in case we back up - thus, LMBD is a table (indexed by the node depth) and must appear
in a SAVE statement.
The values shown for the table IDIST represent metric increments ap-
propriate for an S/N ratio
2E/N
= 2.5, when the additive Gaussian channel is modulated with
eight orthogonal signals.t
Next, we must insert the statements for using the convolutional coder.
First of all, the
SEQUENCE statement will be
SEQUENCE 1 (S,I,PI, P2)
The CONSTRAINT statement and the definitions of Pi and P2 must also be entered at the beginning
of the program.
We must insert the GENERATE statement before computing the new LMBD, at
statement 1 in the program.
After selection of a particular branch to try, the information bit
tThese numbers were computed from data supplied by K. Jordan of Lincoln Laboratory.
53
_
__
I·
___
___11
I
__
I __
__1_1