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