Patent ID: 7031407

Claim:
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; a storage device having memory cells, wherein for each of said multiple stages, a group of one or more memory cells is to store said trace bits in sequential order; means for tracing back, stage by stage, through said memory cells using said trace bits; and a trace back register whose L+P−1 least significant bits indicate the location in said group of a bit whose trace bit is to be saved into the least significant bit of the trace back register after the trace back register is shifted right one bit, said location comprising the bit number given by the L least significant bits of the trace back register and the memory cell whose number in said group is given by the value in the P−1 bits of the trace back register immediately to the left of said L least significant bits, where L is the integer part of the logarithm to base 2 of the length of the memory cell and P is the number of memory cells in said group.