Decoding method and apparatus using trace deletion for viterbi algorithm

Abstract

A decoding apparatus for decoding input data using a Viterbi algorithm includes a first unit for repetitively performing determination of a survivor path corresponding to each state at each time unit based on the input data and a Trellis diagram, and for generating decision vectors and path number information whenever a branch path is determined. A second unit is provided for storing the decision vectors generated in the first unit and for outputting path information representing each survivor path determined by the stored decision vectors. A third unit stores the path number information output from the first unit and the path information output from the second unit, and deletes the branch path information corresponding to the path number information of the first unit from the stored path information, while retracing the previous states during the time when the branch path to be deleted does not overlap the other survivor path having a branch path connected to the next state. The third unit generates decoded data corresponding to input data based on the finally remaining survivor path.