AN AREA-EFFICIENT PATH MEMORY STRUCTURE FOR VLSI IMPLEMENTATION OF HIGH-SPEED VITERBI DECODERS

Path storage and selection methods for Viterbi decoders are investigated with special emphasis on VLSI implementations. Two well-known algorithms, the register exchange algorithm, REA, and the trace back algorithm, TBA, are considered. The REA requires the smallest number of storage elements, but the storage elements must be provided with multiplexers on the input and they have a poor density compared to RAM cells. Furthermore, a rather complicated interconnection structure is required. The TBA requires more than three times as many storage elements, but these can be realized as RAM cells. A new algorithm which combines the advantages of both the REA and the TBA is proposed. It requires only slightly more storage elements than the REA and most of the storage elements can be realized as RAM cells. For a standard decoder with constraint length K = 7, rate R = 1/2 and decoding depth L = 56, significant area savings compared to the REA and the TBA are achieved. Furthermore, the relative area savings increase for larger decoding depths, which might be desirable for punctured codes. Based on the new algorithm a test chip has been designed and fabricated in a 2 micron CMOS process using MOSIS like simplified design rules. The chip operates at 20 Mbit/s. The core of the chip measures 3.5 x 8.1 mm2, and it contains approximately 50,000 transistors.