Error correcting Viterbi decoder
View Patent ↗Methods and corresponding systems in a Viterbi decoder include selecting an input symbol in an input block, wherein the input block has a plurality of input symbols, wherein each input symbol has a Boolean value, a quality value, and an associated stage, and wherein the selected symbol is selected based upon the quality value of the selected symbol relative to a quality value of other input symbols in the input block. Thereafter, the Boolean value of the selected symbol is complemented to produce a complemented symbol. The complemented symbol is substituted for the selected symbol to produce an alternate input block. A Viterbi algorithm is executed using the alternate input block to produce an alternate decoded bit sequence, which is then checked for errors using an error check. The alternate decoded bit sequence is output in response to the alternate decoded bit sequence passing the error check.
1. A method in a Viterbi decoder comprising:
selecting an input symbol in an input block to provide a selected symbol, wherein the input block has a plurality of input symbols, wherein each input symbol has a Boolean value, a quality value, and an associated stage, and wherein the selected symbol is selected based upon the quality value of the selected symbol relative to a quality value of other input symbols in the input block;
complementing the Boolean value of the selected symbol to produce a complemented symbol;
substituting the complemented symbol for the selected symbol at the associated stage of the selected symbol to produce an alternate input block;
executing a Viterbi algorithm using the alternate input block to produce an alternate decoded bit sequence;
checking the alternate decoded bit sequence for errors using an error check; and
outputting the alternate decoded bit sequence in response to the alternate decoded bit sequence passing the error check.
2. The method in a Viterbi decoder according to claim 1 wherein the selecting the input symbol comprises selecting an input symbol having a quality value equal to a lowest quality value of the plurality of input symbols in the input block.
3. The method in a Viterbi decoder according to claim 1 wherein the complementing the Boolean value of the selected symbol comprises changing the Boolean value of the selected symbol while maintaining an absolute value of the quality value of the selected symbol.
4. The method in a Viterbi decoder according to claim 1 wherein the checking the alternate decoded bit sequence for errors comprises checking the alternate decoded bit sequence for errors using a cyclic redundancy check (CRC) type error check, wherein a CRC value computed on a first portion of the alternate decoded bit sequence is compared to a CRC value contained in a second portion of the alternate decoded bit sequence.
5. The method in a Viterbi decoder according to claim 1 wherein the plurality of input symbols comprises a plurality of input symbols produced with a rate one encoder.
6. The method in a Viterbi decoder according to claim 1 wherein the selecting the input symbol and the complementing the Boolean value comprises:
selecting N input symbols in the input block to provide N selected symbols, the selecting based upon the quality value of each of the N selected symbols relative to the quality value of other input symbols in the input block, wherein N is an integer greater than one; and
complementing the Boolean value of each of the N selected symbols to produce N complemented symbols.
7. The method in a Viterbi decoder according to claim 6 wherein the quality value of each of the N selected symbols is less than or equal to an Nth smallest quality value of the quality value of each of the plurality of input symbols.
8. The method in a Viterbi decoder according to claim 6 wherein the substituting the complemented symbol comprises substituting a Boolean combination of the N complemented symbols for corresponding ones of the N selected symbols at corresponding stages to produce one or more of 2 N −1 possible alternate input blocks.
9. A Viterbi decoder comprising:
a controller;
an alternate path stage selector coupled to the controller, wherein the alternate path stage selector selects a selected symbol in an input block, wherein the input block has a plurality of input symbols, wherein each input symbol has a Boolean value, a quality value, and an associated stage, and wherein the selected symbol is selected based upon the quality value of the selected symbol relative to a quality value of other input symbols in the input block;
alternate input block calculator coupled to the controller, wherein the alternate input block calculator calculates an alternate input block by complementing the Boolean value of the selected symbol to produce a complemented symbol, and substituting the complemented symbol for the selected symbol to produce an alternate input block;
a Viterbi decoder coupled to the controller for decoding the alternate input block to produce an alternate decoded bit sequence, and for outputting the alternate decoded bit sequence; and
an error detector coupled to the controller for detecting an error in the alternate decoded bit sequence.
10. The Viterbi decoder according to claim 9 wherein the alternate path stage selector comprises an alternate path stage selector for selecting an input symbol having a quality value equal to a lowest quality value of the plurality of input symbols.
11. The Viterbi decoder according to claim 9 wherein the error detector comprises an error detector for detecting an error using a CRC type error check.
12. The Viterbi decoder according to claim 9 wherein the plurality of input symbols comprises a plurality of input symbols encoded with a rate one encoder.
13. The Viterbi decoder according to claim 9 wherein the alternate path stage selector comprises an alternate path stage selector for providing N selected symbols based upon the quality value of each of the N selected symbols relative to the quality value of other input symbols in the input block, wherein N is an integer greater than one.
14. The Viterbi decoder according to claim 13 wherein the alternate path stage selector comprises an alternate path stage selector for providing N selected symbols, wherein each of the N selected symbols has a quality value less than or equal to the Nth smallest quality value of the quality value of each of the plurality of input symbols.
15. The Viterbi decoder according to claim 13 wherein the alternate input block calculator comprises an alternate input block calculator for producing up to 2 N −1 possible alternate input blocks by complementing the Boolean value of each of the N selected symbols to produce N complemented symbols, and substituting Boolean combinations of the N complemented symbols for corresponding ones of the N selected symbols at corresponding stages.
16. A method in Viterbi decoder comprising:
selecting N input symbols in an input block to provide N selected symbols, wherein the input block has a plurality of input symbols, wherein each input symbol has a Boolean value, a quality value, and an associated stage, and wherein the N selected symbols are selected based on the quality value of each of the N selected symbols relative to the quality value of other input symbols in the input block;
complementing the Boolean values of the N selected symbols to produce N complemented symbols;
substituting one or more of the N complemented symbols for corresponding ones of the N selected symbols at corresponding stages to produce an alternate input block, wherein the one or more of the N complemented symbols comprises a Boolean combination of the N complemented symbols;
executing a Viterbi algorithm using the alternate input block to produce an alternate decoded bit sequence;
checking the alternate decoded bit sequence for errors using an error check; and
outputting the alternate decoded bit sequence in response to the alternate decoded bit sequence passing the error check.
17. The method in Viterbi decoder according to claim 16 wherein the selecting N input symbols comprises selecting N input symbols from a plurality of input symbols produced with a rate one encoder.
18. The method in Viterbi decoder according to claim 16 wherein the checking the alternate decoded bit sequence for errors comprises checking the alternate decoded bit sequence for errors using a CRC type error check, wherein a CRC value computed on a first portion of the alternate decoded bit sequence is compared to a CRC value contained in a second portion of the alternate decoded bit sequence.
19. The method in Viterbi decoder according to claim 16 wherein the selecting N input symbols comprises selecting N input symbols in response to failing an error check of a decoded bit sequence corresponding to the plurality of input symbols.
20. The method in Viterbi decoder according to claim 16 wherein the N input symbols have N lowest quality values of a rank-ordered list of quality values of the plurality of input symbols.