Multi-rate viterbi decoder

Abstract

A method and system for decoding a data symbol sequence that has been previously encoded using one or more unique code word polynomials in which at least one unique code word polynomial is used more than once. A set of 2 d-1 unique branch metrics is computed, using the unique code word polynomials, where d is the number of unique code word polynomials. The computed set of 2 d-1 unique branch metrics is stored in a memory. Path metrics are then calculated, based on the stored set of 2 d-1 unique branch metrics. A decoded data symbol sequence is generated based on the computed path metrics.

1 - 6 . (canceled)  
     
     
         7 . A Viterbi decoder for decoding a data symbol sequence encoded using one or more unique code word polynomials, wherein the encoding process uses at least one unique code word polynomial more than once, the decoder comprising: 
 a branch metric unit for computing a set of 2 d  unique branch metrics, using the unique code word polynomials, based on the encoded data symbol sequence, where d is the number of unique code word polynomials, and identifying complementary branch metric pairs from amongst the computed set of 2 d  unique branch metrics;    a first memory, connected to the branch metric unit, for storing the computed set of unique branch metrics;    a path metric unit, connected to the first memory, for calculating a set of path metrics and decision bits based on the stored set of unique branch metrics; and    a traceback unit, connected to the path metric unit, for generating a decoded data symbol sequence based on the computed decision bits.    
     
     
         8 . The Viterbi decoder of  claim 7 , further comprising an output register for storing the generated decoded data symbol sequence.  
     
     
         9 . The Viterbi decoder of  claim 7 , wherein the branch metric unit comprises: 
 a write logic unit for identifying complementary branch metric pairs from amongst the computed set of unique branch metrics and selecting one branch metric from each identified complementary branch metric pair;    an address generator for generating the addresses for storing the selected branch metrics in the first memory; and    a memory read logic unit for reading the stored branch metrics in the first memory and passing the read branch metrics to the path metric unit.    
     
     
         10 . The Viterbi decoder of  claim 7 , wherein the first memory for storing branch metrics is a Random Access Memory (RAM).  
     
     
         11 . The Viterbi decoder of  claim 7 , wherein the path metric unit comprises: 
 an accumulator for adding the computed branch metrics for a stage to the path metrics for the previous stage;    a path selector for selecting a path based on the accumulated path metrics; and    a second memory for storing the path metrics of the selected path.    
     
     
         12 . The Viterbi decoder of  claim 7 , wherein the traceback unit further comprises a third memory for storing the decision bits.  
     
     
         13 . A Viterbi decoder for decoding a data symbol sequence previously encoded using one or more unique code word polynomials, the encoding process using at least one unique code word polynomial more than once, the Viterbi decoder comprising: 
 a branch metric unit for computing a set of unique branch metrics based on the data symbol sequence using the unique code word polynomials, wherein the number of branch metrics computed is 2 d-1 , where d is the number of unique code polynomials;    a first memory, connected to the branch metric unit, for storing the set of unique branch metrics;    a path metric unit, connected to the first memory, for calculating a set of path metrics based on the stored set of unique branch metrics;    a traceback unit, connected to the path metric unit, which generates a decoded data symbol sequence based on the calculated path metrics and decision bits; and    an output register for storing the generated decoded data symbol sequence,    wherein the branch metric unit comprises: 
 a write logic unit for identifying complementary branch metric pairs from amongst the computed set of unique branch metrics and selecting one branch metric from each identified complementary branch metric pair pairs, wherein only the selected branch metrics are stored in the first memory;  
 an address generator for generating the addresses for storing the selected branch metrics in the first memory; and  
 a memory read logic unit for reading the stored branch metrics in the first memory and passing the read branch metrics to the path metric unit.  
   
     
     
         14 . The Viterbi decoder of  claim 13 , wherein the path metric unit further includes: 
 an accumulator for adding the computed branch metrics for a stage to the path metrics for the previous stage;    a path selector for selecting a path based on the accumulator output; and    a second memory for storing the accumulated path metrics for the selected path.    
     
     
         15 . The Viterbi decoder of  claim 13 , wherein the traceback unit further comprises a third memory for storing the decision bits.  
     
     
         16 . The Viterbi decoder of  claim 13 , wherein the first memory for storing branch metrics is a Random Access Memory (RAM).  
     
     
         17 - 18 . (canceled)