Convolutional decoding

Abstract

In one aspect the invention is a method for sequence estimating. The method includes receiving convolutional codes. The method further includes using a lazy Viterbi decoder to decode the convolutional codes. The convolutional codes may be stream convolutional codes. The convolutional codes may also be block convolutional codes. The lazy Viterbi decoder may be used in a software radio environment.

1 . A method for decoding convolutional codes, comprising:
 receiving convolutional codes; and   using a lazy Viterbi decoder to decode the convolutional codes, wherein using the lazy Viterbi decoder to decode the convolutional codes comprises:   maintaining a trellis data structure; and   maintaining a priority queue data structure.   
   
   
       2 . The method of  claim 1 , wherein the convolutional codes comprise block convolutional codes. 
   
   
       3 . The method of  claim 1 , wherein the convolutional codes comprises stream convolutional codes. 
   
   
       4 . The method of  claim 1 , wherein the lazy Viterbi decoder is used in a software radio environment. 
   
   
       5 . The method of  claim 1 , wherein using the lazy Viterbi decoder further comprises:
 initializing the trellis data structure and the priority queue data structure.   
   
   
       6 . The method of  claim 5 , wherein using the lazy Viterbi decoder further comprises:
 extracting a lowest-metric shadow node û in the priority queue until a “real” version u of û is not already in the trellis data structure;   inserting the node u into the trellis data structure;   for all successors of u′ of u, generating a new shadow node û′ with a corresponding accumulated metric; and   inserting the new shadow node û′ into the priority queue and a time list.   
   
   
       7 . The method of  claim 1 , wherein maintaining a trellis data structure comprises maintaining a data structure that includes a plurality of nodes of a trellis graph. 
   
   
       8 . The method of  claim 7 , wherein maintaining a data structure that includes the nodes of a trellis graph comprises:
 computing the shortest path from a start node to other nodes of the trellis graph; and   for at least some of the nodes of the trellis graph, storing a pointer to a predecessor node on a shortest path to the start node.   
   
   
       9 . The method of  claim 7 , wherein maintaining a priority queue comprises maintaining proposed path extensions for the trellis graph. 
   
   
       10 . Apparatus for decoding convolutional codes, comprising:
 a memory that stores executable instruction signals; and   a processor that executes the instruction signals to:
 initialize a lazy Viterbi decoder, the lazy Viterbi decoder comprising a trellis data structure and a priority queue data structure; 
 receive convolutional codes; and 
 use the lazy Viterbi decoder to decode the convolutional codes. 
   
   
   
       11 . The apparatus of  claim 10 , wherein the convolutional codes comprise block convolutional codes. 
   
   
       12 . The apparatus of  claim 10 , wherein the convolutional codes comprises stream convolutional codes. 
   
   
       13 . The apparatus of  claim 10 , wherein the lazy Viterbi decoder is used in a software radio environment. 
   
   
       14 . The apparatus of  claim 10 , wherein the instructional signals to use the lazy Viterbi decoder comprises instructional signals to:
 extract a lowest-metric shadow node u in the priority queue until a “real” version u of û is not already in the trellis data structure;   insert the node u into the trellis data structure; and   for all successors of u′ of u, generate a new shadow node û′ with a corresponding accumulated metric; and   inserting the new shadow node û′ into the priority queue and a time list.   
   
   
       15 . An article comprising a machine-readable medium that stores executable instruction signals decoding convolutional codes, the instruction signals causing a machine to:
 initialize a trellis data structure;   initialize a priority queue data structure;   receive the convolutional codes; and   use the trellis data structure and the priority queue data structure to decode the convolutional codes.   
   
   
       16 . The article of  claim 15 , wherein the convolutional codes comprise block convolutional codes. 
   
   
       17 . The article of  claim 15 , wherein the convolutional codes comprises stream convolutional codes. 
   
   
       18 . The article of  claim 15 , wherein the trellis data structure and the priority queue data structure are included in a lazy Viterbi decoder used in a software radio environment. 
   
   
       19 . The article of  claim 15 , wherein instructions causing a machine to use the lazy Viterbi decoder comprises instructions causing a machine to:
 extract a lowest-metric shadow node û in the priority queue until a “real” version u of û is not already in the trellis data structure;   insert the node u into the trellis data structure; and   for all successors of u′ of u, generate a new shadow node û′ with a corresponding accumulated metric; and   insert the new shadow node û′ into the priority queue and a time list.   
   
   
       20 . A receiver, comprising:
 a lazy Viterbi decoder comprising:
 a trellis data structure; and 
 a priority queue data structure. 
   
   
   
       21 . The receiver of  claim 20 , wherein the receiver is in a software radio environment. 
   
   
       22 . The receiver of  claim 20 , wherein the receiver is in a high-definition television.