Apparatus and method for decoding and trace back of convolution codes using the viterbi decoding algorithm

Abstract

A system for generating and storing trace bits for Viterbi decoding of binary convolution codes includes at least one arithmetic logic unit (ALU) for determining the trace bits, and a first register and a second register for storing the trace bits. The first register stores a first half of a series of trace bits for N states in sequential order and the second register stores a second half of the series in sequential order. A binary convolution decoder having multiple states each having N states includes at least one arithmetic logic unit (ALU), a first register and a second register, and a storage device. The at least one ALU determines trace bits for each of the N states for each of the multiple stages. The first and second registers store trace bits of at least a portion of one stage. The storage device has memory cells. For each of the multiple stages, a group of at least one memory cell stores the N trace bits in sequential order. The system also includes means for tracing back, stage by stage, through the memory cells using the trace bits. Each of the memory cells has a length of at least N bits and the means for tracing back is operative to trace back in as few as two cycles per stage.

1 . A system comprising: 
 at least one arithmetic logic unit to determine trace bits for Viterbi decoding of a binary convolution code;    a first register to hold a first portion of a series of trace bits for states of said code in consecutive order; and    a second register to hold a second portion of said series in consecutive order,    wherein said first portion and said second portion jointly include at most a single copy of said series.    
   
   
       2 . The system according to  claim 1  wherein said first portion comprises trace bits for a first half of said states in consecutive order and said second portion comprises trace bits for a second half of said states in consecutive order.  
   
   
       3 . The system according to  claim 1  and wherein said first register and said second register are shift registers.  
   
   
       4 . The system according to  claim 1  further comprising: 
 a first barrel shifter between said first register and said arithmetic logic unit and a second barrel shifter between said second register and said arithmetic logic unit.    
   
   
       5 . The system according to  claim 1  further comprising: 
 storage device coupled to said first and second registers having memory cells, wherein one or more memory cells store in consecutive order all trace bits for a stage of Viterbi decoding of said convolution code.    
   
   
       6 . The system according to  claim 1  further comprising: 
 a trace back unit coupled to said memory storage to receive said trace bits.    
   
   
       7 . A binary convolution decoder having multiple stages, each stage having states of a binary convolution code, the decoder comprising: 
 at least one arithmetic logic unit to determine trace bits for each of said states for each of said multiple stages;    a first register and a second register to jointly store a single copy of trace bits of at least a portion of one stage in consecutive order;    a storage device having memory cells, wherein for each of said multiple stages, one or more memory cells are able to store said trace bits in consecutive order; and    means for tracing back, stage by stage, through said memory cells using said trace bits.    
   
   
       8 . The decoder according to  claim 7 , wherein said means for tracing back is to trace back in as few as two clock cycles per stage.  
   
   
       9 . The decoder according to  claim 7 , wherein each of said stages has 16 states, each of said memory cells has a length of at least 16 bits and said means for tracing back is to trace back in as few as two clock cycles per stage.  
   
   
       10 . The decoder according to  claim 7 , wherein each of said stages has 32 states, each of said memory cells has a length of at least 32 bits and said means for tracing back is to trace back in as few as two clock cycles per stage.  
   
   
       11 . A method comprising: 
 generating a series of trace bits for Viterbi decoding of a binary convolution code;    storing a first half of said series in consecutive order in a first register and a second half of said series in consecutive order in a second register; and    saving in consecutive order the trace bits stored in said first and second registers to one or more memory cells.    
   
   
       12 . The method according to  claim 11 , wherein said first half comprises trace bits for a first half of states of said code and said second half comprises trace bits for a second half of said states.  
   
   
       13 . The method according to  claim 11  further comprising: 
 storing said trace bits in consecutive order in groups of memory cells, wherein the number of memory cells in each of said groups is a power of 2 and at least 2,    wherein in each of said groups, a first half of said memory cells jointly store said first half of said series of trace bits and a second half of said memory cells jointly store said second half of said series.    
   
   
       14 . A method for Viterbi decoding of binary convolution codes, the decoding involving multiple stages each having states of a binary convolution code, the method comprising: 
 determining trace bits for each of said states for each of said multiple stages;    storing in consecutive order a single copy of trace bits of at least a portion of one stage jointly in a first register and a second register;    for each of said multiple stages, storing said trace bits in consecutive order in a group of one or more memory cells of a storage device such that the trace bits of at least three of said stages are simultaneously maintained by said storage device; and    tracing back, stage by stage, through said memory cells using said trace bits.    
   
   
       15 . The method according to  claim 14 , wherein tracing back through said memory cells is performed in as few as two clock cycles per stage.  
   
   
       16 . The method according to  claim 14 , wherein each of said stages has 16 states, each of said memory cells has a length of at least 16 bits and tracing back through said memory cells is performed in as few as two clock cycles per stage.  
   
   
       17 . The method according to  claim 14 , wherein each of said stages has 32 states, each of said memory cells has a length of at least 32 bits and tracing back through said memory cells is performed in as few as two clock cycles per stage.