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 stages 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.