Browse Prior Art Database

A NEW VITERBI ADD, COMPARE SELECT BUTTERFLY FOR USE WITH MOTOROLA 56300 AND 56600 FAMILIES OF DIGITAL SIGNAL PROCESSORS

IP.com Disclosure Number: IPCOM000008026D
Original Publication Date: 1997-Mar-01
Included in the Prior Art Database: 2002-May-13
Document File: 2 page(s) / 95K

Publishing Venue

Motorola

Related People

Dana Taipale: AUTHOR

Abstract

The Viterbi algorithm is the optimal algorithm used for decoding of convolutional error correcting codes, decoding of trellis codes and maximum like- lihood sequence estimators, The core of the algo- rithm consists of a state and path update. The num- ber of states varies from about 2-4 for simple equal- ization to 128 or more for some advanced error cor- recting codes. Each state must be updated once for each received symbol. The result is that a digital signal processing implementation can often be the most computation intensive task. Our innovation to this basic state update requires 14% fewer cycles to do the same task.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

MO7VROLA Technical Developments

A NEW VITERBI ADD, COMPARE SELECT BUTTERFLY FOR USE WITH MOTOROLA 56300 AND 56600 FAMILIES OF DIGITAL SIGNAL PROCESSORS

by Dana Taipale

  The Viterbi algorithm is the optimal algorithm used for decoding of convolutional error correcting codes, decoding of trellis codes and maximum like- lihood sequence estimators, The core of the algo- rithm consists of a state and path update. The num- ber of states varies from about 2-4 for simple equal- ization to 128 or more for some advanced error cor- recting codes. Each state must be updated once for each received symbol. The result is that a digital signal processing implementation can often be the most computation intensive task. Our innovation to this basic state update requires 14% fewer cycles to do the same task.

  State/path updates are done using an add, com- pare, select butterfly. Two states each are used in a butterfly to compute two updated states (the updat- ed states are not the same states as those used in the butterfly). The state inputs are called path metrics, There are two additional inputs related to the state transition. These are called branch metrics.

  SA and SB are the state metric inputs, NSA and NSB are the updated state outputs, and C and D are the branch metrics. The add, compare select opera- tion compares SA+C to SB+D, and chooses the maximum for NSA. SA and SB also have path words. The path is updated by taking the path word that is paired with the survivor state (the source for

.

the chosen max), and appending a 0.

  The update for state NSB is similar, SA+D is compared to SB+C and the max is chosen. The path is updated by appending a 1 for this state.

A NEW VITERBI ADD, COMPARE, SELECT BUTTERFLY

  The following is the new assembly code for implementing the add, compare, select butterfly on the Motorola 56300/56600 family of Digital Signal Processors.

1.

2.

3.

4.

5.

6.

I.

8.

9.

10.

NEXT

DO

ADD

ADD

MAX

ADD

ADD

MAX

ADDL

MOVE

MOVE

#NUMSTATES,NEXT

XA L:(RS)+,B

YB Y(R5)-N5,XO

A3 L:(RS)+,A

B,L:(R4+N4)

Yl,A L:...