Survivor memory device in viterbi decoder using trace deletion method

Abstract

A survivor memory device in a Viterbi decoder determines a final survivor path using a trellis diagram and decision vectors, and outputs decoded data corresponding to the determined survivor path. The survivor memory device includes a path existence information generator for receiving a plurality of decision vectors, and for generating first branch path existence information representing whether a branch path exists between each state and the corresponding next states in the trellis diagram. A plurality of units are serially connected with respect to the outputs of the path existence information generator. Each unit comprises a path existence information store for receiving and storing the first branch path existence information, a path removal signal generator for generating corresponding path removal signals when the first branch path existence information corresponding to each current state represents that corresponding branch paths do not exist between each current state and the corresponding next states, and a path existence information updator for receiving the first branch path existence information stored in the path existence information store and the path removal signals generated by the path removal signal generator, and for updating values of second branch path existence information corresponding to each current state to represent that corresponding branch paths do not exist between each current state and the corresponding previous states.