Patent ID: 7900123
Filing Date: 2011-03-01
Classification: H03M

Abstract:
1. A method for near maximum-likelihood sequential decoding, suitable for a decoding diagram with a convolution code to determine an optimum path in the decoding diagram, wherein the decoding diagram represents paths including a message sequence passing there-through when a message sequence is encoded and codewords corresponding the paths, the decoding method comprising: (a) placing a origin node of the decoding diagram into an open stack; (b) comparing a level threshold, wherein when the difference between a level of an end node of a smallest metric path in the open stack and a maximum level being greater than or equal to the level threshold, the smallest metric path in the open stack is deleted, the step of comparing a level threshold is continued until the difference between the level of the end node of the smallest metric path in the open stack and the maximum level is smaller than the level threshold; (c) determining whether the level of the end node of the smallest metric path in the open stack being more than the maximum level, if so, assigning the maximum level as the level of the end node in the open stack and proceeding to step (d), otherwise, proceeding to step (d); (d) calculating the metrics of a plurality of successor paths extended from the end node of the smallest metric path in the open stack; (e) deleting the smallest metric path in the open stack and placing the successor paths into the open stack; and (f) determining whether the smallest metric path in the open stack having ended at a goal node of the decoding diagram, wherein if the smallest metric path in the open stack has not ended at the goal node of the decoding diagram, steps (b)˜(f) are repeated, if the smallest metric path in the open stack has ended at the end node of the decoding diagram, the smallest metric path is the optimum path in the decoding diagram.