Error correcting Viterbi decoder
View Patent ↗Methods and corresponding systems in a Viterbi decoder include computing a maximum likelihood (ML) path in a Viterbi trellis in response to executing a first Viterbi algorithm. Thereafter, one or more merge points are selected on the ML path in a second Viterbi algorithm, wherein the merge points each have a path metric difference, which is a difference between an ML path metric at the merge point and a non-surviving path metric at the merge point. Merge points are selected based upon relative path metric differences associated with nodes on the ML path. Next, alternate paths in the Viterbi trellis are computed based on the ML path with alternate paths substituted at corresponding merge points. A passing decoded bit sequence is output in response to passing an error check, wherein the passing decoded bit sequence is associated with one of the one or more alternate paths.
1. A method in a Viterbi decoder comprising:
computing, including executing a first Viterbi algorithm, a maximum likelihood (ML) path in a Viterbi trellis, wherein the Viterbi trellis has a plurality of nodes corresponding to a plurality of trellis states at a plurality of trellis stages;
selecting during executing a second Viterbi algorithm, a first merge point, wherein the first merge point is a node on the ML path that has a smallest difference between an ML path metric at the first merge point and a first non-surviving path metric at the first merge point compared to other path metric differences at other nodes on the ML path;
computing a second path in the Viterbi trellis, wherein the second path is based on the ML path with a portion of the first non-surviving path substituted for a corresponding portion of the ML path at the first merge point; and
in response to a second decoded bit sequence passing an error check, outputting the second decoded bit sequence, wherein the second decoded bit sequence corresponds to the second path.
2. The method in a Viterbi decoder according to claim 1 wherein the selecting a first merge point in the ML path further comprises selecting a first merge point in the ML path in response to a decoded bit sequence corresponding to the ML path failing the error check.
3. The method in a Viterbi decoder according to claim 1 wherein the computing a second path in the Viterbi trellis further comprises:
tracing back a portion of the first non-surviving path at the first merge point to identify a plurality of second path nodes preceding the first merge point; and
substituting the plurality of second path nodes for a corresponding plurality of ML nodes to produce the second path.
4. The method in a Viterbi decoder according to claim 1 wherein the outputting the second decoded bit sequence in response to the second decoded bit sequence passing the error check further comprises outputting the second decoded bit sequence in response to a cyclic redundancy check (CRC) value computed on a first portion of the second decoded bit sequence matching a CRC value in a second portion of the second decoded bit sequence.
5. The method in a Viterbi decoder according to claim 1 wherein the selecting the first merge point in the ML path further comprises selecting N merge points in the ML path in response to the executing a second Viterbi algorithm, wherein N is an integer greater than 1, and wherein each of the N merge points is a node on the ML path, and each of the N merge points has one of N smallest path metric differences between an Nth ML path metric at a respective one of the N merge points and an Nth non-surviving path metric at the respective one of the N merge points compared to other path metric differences at other nodes on the ML path.
6. The method in a Viterbi decoder according to claim 5 wherein the selecting N merge points in the ML path in response to executing a second Viterbi algorithm comprises:
computing path metric differences between surviving and non-surviving paths at nodes on the ML path;
ranking path metric differences between surviving and non-surviving paths; and
selecting N nodes in the ML path associated with N smallest path metric differences.
7. The method in a Viterbi decoder according to claim 5 wherein the computing a second path in the Viterbi trellis further comprises computing 2 N −1 paths in the Viterbi trellis, wherein each of the 2 N −1 paths is based on the ML path with Boolean combinations of portions of the N non-surviving paths at the respective N merge points substituted for a corresponding portion of the ML path at the respective N merge points; and wherein the outputting the second decoded bit sequence in response to a second decoded bit sequence passing an error check further comprises outputting a selected one of 2 N −1 decoded bit sequences that passes the error check, wherein the selected one of 2 N −1 decoded bit sequences corresponds to one of the 2 N −1 paths in the Viterbi trellis.
8. The method in a Viterbi decoder according to claim 7 wherein the outputting a selected one of 2 N −1 decoded bit sequences that passes the error check further comprises:
rank ordering the 2 N −1 paths in order of path metric differences between an overall path metric of the ML path and an overall path metric of each respective one of the 2 N −1 paths;
error-checking the 2 N −1 paths in order of path metric differences; and
outputting a selected one of 2 N −1 decoded bit sequences in response to passing the error check, wherein the selected one of 2 N −1 decoded bit sequences corresponds to one of the 2 N −1 paths in the Viterbi trellis.
9. A Viterbi decoder comprising:
a controller;
a Viterbi decoder coupled to the controller for calculating ML path data corresponding to a maximum-likelihood (ML) path, during execution of a first Viterbi algorithm, and alternate path data corresponding to an alternate path, during execution of a second Viterbi algorithm in a Viterbi trellis, wherein the Viterbi trellis has a plurality of nodes corresponding to a plurality of trellis states at a plurality of trellis stages;
a decoder path memory coupled to the Viterbi decoder for storing data associated with the ML path and the alternate path;
a merge point selector for selecting a first merge point in the ML path, wherein the merge point selector is coupled to the decoder path memory and the controller, and wherein the first merge point is a node on the ML path that has a smallest path metric difference between an ML path metric at the first merge point and a non-surviving path metric at the first merge point compared to other path metric differences at other nodes on the ML path;
an alternate path calculator for calculating an alternate path in the Viterbi trellis, wherein the alternate path calculator is coupled to the merge point selector and the decoder path memory, and wherein the alternate path is based on the ML path with a portion of the non-surviving path substituted for a corresponding portion of the ML path at the merge point;
a path selector for outputting a decoded bit sequence associated with a selected path, wherein the selected path is one of the ML path and the alternate path, the path selector coupled to the controller and the decoder path memory; and
a path error detector coupled to the path selector for detecting an error in the decoded bit sequence associated with the selected path.
10. The Viterbi decoder according to claim 9 wherein the alternate path calculator comprises:
a trace-back unit for determining a plurality of alternate path nodes in a non-surviving path at the first merge point; and
a node substitution unit for substituting the plurality of alternate path nodes for corresponding nodes in the ML path to calculate the alternate path.
11. The Viterbi decoder according to claim 9 wherein the path error detector comprises a cyclic redundancy check (CRC) type error detector.
12. The Viterbi decoder according to claim 9 wherein the merge point selector comprises an N-point merge point selector for selecting N merge points in the ML path, wherein each of the N merge points is a node on the ML path that has one of N smallest path metric differences between an Nth ML path metric at an Nth merge point and an Nth non-surviving path metric at the Nth merge point compared to other path metric differences at other nodes on the ML path.
13. The Viterbi decoder according to claim 12 wherein the N-point merge point selector comprises an N-point merge point selector for selecting N merge points in the ML path during the execution of the second Viterbi algorithm in the Viterbi decoder, wherein the second Viterbi algorithm follows execution of the first Viterbi algorithm that calculates the ML path.
14. The Viterbi decoder according to claim 12 wherein the alternate path calculator comprises an alternate path calculator for computing 2 N −1 paths in the Viterbi trellis, wherein each of the 2 N −1 paths is based on the ML path with Boolean combinations of portions of N non-surviving paths at respective N merge points substituted for a corresponding portion of the ML path at the respective N merge points; and wherein the outputting the second decoded bit sequence in response to a second decoded bit sequence passing an error check further comprises outputting a selected one of 2 N −1 decoded bit sequences that passes the error check, wherein the selected one of 2 N −1 decoded bit sequences corresponds to one of the 2 N −1 paths in the Viterbi trellis.
15. The Viterbi decoder according to claim 14 wherein the path selector comprises a path selector for selecting one of the 2 N −1 paths in the Viterbi trellis and outputting, to the path error detector, a decoded bit sequence corresponding to a selected one of the 2 N −1 paths.
16. A method in Viterbi decoder comprising:
computing a maximum likelihood (ML) path in a Viterbi trellis in response to executing a first Viterbi algorithm, wherein the Viterbi trellis includes a matrix of nodes corresponding to a plurality of trellis states at a plurality of trellis stages;
selecting one or more merge points, during execution of a second Viterbi algorithm, wherein the one or more merge points are each nodes on the ML path, and wherein the one or more merge points each have a path metric difference, wherein the path metric difference at a respective merge point is a difference between an ML path metric at the respective merge point and a non-surviving path metric at the respective merge point, and wherein the one or more merge points are selected based upon relative path metric differences associated with a plurality of nodes on the ML path;
computing one or more alternate paths in the Viterbi trellis, wherein the one or more alternate paths are based on the ML path with portions of one or more non-surviving paths substituted for a corresponding portion the ML path at one or more corresponding merge points; and
in response to a passing decoded bit sequence passing an error check, outputting the passing decoded bit sequence, wherein the passing decoded bit sequence is associated with one of the one or more alternate paths.
17. The method in Viterbi decoder according to claim 16 wherein the outputting the passing decoded bit sequence comprises outputting the passing decoded bit sequence in response to the passing decoded bit sequence passing a cyclic redundancy check (CRC) type of error check.
18. The method in Viterbi decoder according to claim 16 wherein the selecting one or more merge points based upon relative path metric differences comprises selecting N merge points corresponding to N number of smallest path metric differences.
19. The method in Viterbi decoder according to claim 16 wherein the selecting one or more merge points based upon relative path metric differences comprises selecting merge points corresponding to path metric differences that fall below a difference threshold.
20. The method in a Viterbi decoder according to claim 16 wherein the selecting one or more merge points further comprises selecting N merge points in the ML path in response to the executing a second Viterbi algorithm, wherein N is an integer greater than 1, and wherein each of the N merge points has one of N smallest path metric differences between an Nth ML path metric at a respective one of the N merge points and an Nth non-surviving path metric at the respective one of the N merge points compared to other path metric differences at other nodes on the ML path.