Sequential decoder for decoding of convolutional codes

DETAILED DESCRIPTION The decoding of a convolutional code with known channel parameters can be viewed as a tree-search problem.
The Fano technique provides one method of decoding convolutional code.
When operated with sufficiently high SNR, the Fano technique may perform near-optimal decoding of convolutional codes with significantly lower average complexity than fixed-complexity techniques such as the Viterbi technique.
The Fano technique is a tree-search technique.
FIG.
1 shows an example of a tree 50 that provides a representation of possible decoded sequences.
The tree 50 comprises nodes 52 and branches 54 that extend from a root 56 to leaf nodes 58.
Associated with each branch 54 is a branch metric (or weight) that indicates the likelihood that the corresponding branch 54 lies on the optimal path.
A path 60 is a sequence of nodes connected by branches 54 with the path metric defined as the sum of the corresponding branch metrics in the path 60.
A current node metric is the sum of branch metrics extending along the path 60 up to the current node.
FIG.
2 illustrates a flow chart of a Fano technique 100 for decoding convolutional code.
The Fano technique searches through a tree sequentially, moving from one node to a neighboring node until a leaf node is reached.
The Fano technique is a depth-first tree-search technique, meaning that it attempts to search as few paths as possible to obtain a good path.
Beginning at block 101, the technique starts at the origin and initializes the threshold T.
Continuing on to block 102, the metric of a path being considered is compared against the threshold T.
The relation between T and the metric is determined by the statistics of the branch metrics (i.
e.
, the underlying model) and the results of partial path exploration.
The latter is reflected by dynamically adjusting the threshold to minimize the number of paths explored, blocks 104 and 106.
The basic technique includes deciding whether to move forward (deeper) or backward into the tree, and threshold adjustment