US 5,220,570 AGrant
Programmable Viterbi Signal Processor
Issue Date:1993-06-15
•3 Claims
•9 Drawing Sheets
Abstract
A signal processor which is specially adapted for decoding sequential codes, including trellis codes, convolutional codes and detecting signals in partial response channels. The processor has three units, a branch metric generator unit, an add-compare-select unit and a survivor-trace and decoding unit, each of which is independently programmable. A central control unit synchronizes operations between the units at the received symbol rate. Between synchronizations, each of the units operate concurrently and independently of the others.
Metadata
Assignee
- The Board of Trustees of the Leland Stanford Junior University
Inventors
- Huiling Lou
- John M. Cioffi
Application Information
Application Number:US 6214606
Filing Date:1990-11-30
Priority Date:1990-11-30
Art Unit:233
Classifications
IPC:
H03M 1300H03M 1312H03M 728
Field of Search:
37134143;44;45;46107;94;79;78
Patent Drawings (9 sheets)
Description
BACKGROUND OF THE INVENTION
The present invention relates to a signal processor for decoding and/or encoding digital communication signals and, more particularly, to a programmable signal processor which efficiently decodes sequential codes by the Viterbi algorithm.
Over the past few decades, electronic communications have been increasingly implemented by digital signals. To preserve the integrity of the communication channels, various forms of coding have been studied. One generalized and useful type of coding is sequential coding including trellis codes, convolutional codes, partial response coded data channels and some compression methods. Sequential decoders for codes and channels with memory have been studied for many years, and many dedicated high speed architectures for such decoders have been created for specific codes.
However, the programming of the Viterbi and other sequential decoding algorithms on general purpose computers or digital signal processors is highly inefficient for almost all trellis codes, convolutional codes and partial response coded data channels. Though apparently straight-forward, the programming of the Viterbi and other sequential decoding algorithms is not readily executable. The large amounts of memory access operations and calculations to find the survivor trace render the implementation of these algorithms inefficient in general purpose computers having the standard arithmetic-logic-unit architecture.
With the increasing use of digital communications there has been a growing interest in the application of sequential decoding to various fields, including digital subscriber lines, voiceband modems, digital mobile radio, digital satellite transmissions, and speech and audio compression.
Thus there is an increasing need for a signal processor which may be used in a wide range of applications. Such a signal processor should be able to handle the different sequential codes in the various applications in contrast to the specialized processor architectures that have been created for specific codes. The present invention addresses this need and provides for a programmable signal processor which decodes various sequential codes in a highly efficient manner.
SUMMARY OF THE INVENTION
The present invention provides for a signal processor which is specially adapted for decoding sequential codes, including trellis codes, convolutional codes and detecting signals in partial response channels. The processor has three units, a branch metric generator unit, an add-compare-select unit and a survivor-trace and decoding unit, each of which is independently programmable. A central control unit synchronizes operations between the units at the received symbol rate. Between synchronizations, each of the units operates concurrently and independently of the others.
Special memory organizations permit each of the units, each a subprocessor, to access memory locations quickly in operation and easily from the user's programming standpoint. Furthermore, the partial tables are used with adder and logic functions so that all branch metrics for an application may be accessed with reduced memory requirements.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagrammatic view of the overall system according to the present invention.
FIG. 2 is a block diagram of the branch metric generator unit of the present invention.
FIG. 3 is a block diagram of the add-compare-select unit of the present invention.
FIG. 4 is a block diagram of the survivor-trace and decoding unit of the present invention.
FIGS. 5A and 5B are a table of instructions for the branch metric generator unit.
FIG. 6 is a table of instructions for the add-compare-select unit.
FIG. 7 is a table of instructions for the survivor trace and decode unit.
FIG. 8A illustrates a trellis for an example of decoding.
FIG. 8B shows the state transition diagram for the same example as FIG. 8A.
DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS
In accordance with the present invention, the Viterbi algorithm is implemented in the architecture of a signal processor for the efficient decoding of convolutional codes, trellis codes and partial-response coded data channels. The Viterbi algorithm is the maximum likelihood solution to the problem of estimating the original uncoded input sequence, based on some received sequence of symbols indicative of the transitions of one state to another in the sequence, which symbols are corrupted by additive white Gaussian noise.
The algorithm has three major steps for decoding:
Step 1. For each symbol, i.e. transition code, in a received sequence of symbols, the branch metrics for all possible transitions to all states are generated. The branch metric of a given transition is the squared distance between the noisy received symbol, i.e., the received transition code, and a noiseless symbol, i.e., the ideal transition code.
Step 2. For all the incoming transitions to each state, add the branch metrics to their corresponding previous path metrics. The path with the minimum sum is selected to be the most likely incoming path for that state. This path is appended to the appropriate survivor path. The survivor path records the most likely incoming sequence for each state.
Step 3. The survivor path is traced backwards and the most likely symbol at that point is determined and decoded. The steps are repeated iteratively to find the input sequence to the original encoder.
The Overall System
To implement this algorithm, an architecture as illustrated in FIG. 1 is used. The signal processor of the present invention is divided into three parts, a branch metric generator (BMG) unit 11, an add-compare-select (ACS) unit 12, and a survivor-trace and decoding (STD) unit 13, under control of a central control unit 10. The BMG unit 11, the ACS unit 12, and the STD unit 13 act as three largely independent subprocessors. Each of these units 11, 12 and 13 have separate control units 17, 18 and 19, respectively, which are programmed independently for the user's contemplated application. The units 11, 12 and 13 also operate concurrently and independently of each other to a certain extent. They are synchronous with each other only at the symbol rate of the corresponding data transmission or compression coding system being implemented.
Operational speed of the system is greatly increased because of the special structure and instruction sets of these subprocessor units. These subprocessor units, which do not require multiplication functions, are implemented with a significantly shorter instruction-execution time than is possible with conventional digital signal processors.
The BMG unit 11 computes the branch metrics and transfers them in and out of the register file unit 16 which is also accessed by the ACS unit 12. The ACS unit 12 efficiently implements the add-compare-select computations prevalent in sequential decoding. The STD processor 13 performs the survivor tracing and symbol decoding functions.
The three subprocessor units, 11, 12, and 13 form the stages of a pipeline. At sampling time k, the BMG unit 11 computes the branch metrics from the received symbol at time k and stores these metrics in the register unit 16. At the same time, the ACS unit 12 determines the best incoming path for each state of the trellis given the branch metrics based on the received symbol at time k-1. The STD unit 13 traces the survivor path starting from the stage which corresponds to the sampling time k-2.
As stated above, all subprocessor units 11, 12 and 13 run concurrently and are controlled independently. This enables a programmer to code and test each unit 11, 12 and 13 separately. The control memory stores containing the programs for each of the units 11, 12 and 13 are respectively located in the control units 17, 18 and 19.
Within each subprocessor unit 11, 12 and 13, the instructions are executed in pipelined manner to ensure short overall instruction-execution times.
The central control unit 10 synchronizes the three units 11, 12 and 13 at the symbol rate. That is, each of the subprocessor units 11, 12 and 13 runs concurrently with the others. Having completed its operations, the unit then waits until the other two units 11, 12 and 13 have completed their operations on the current set of data before proceeding to the next set. Therefore, the sampling rate of the overall system is determined by the unit 11, 12 or 13 that requires the maximum execution time.
The memory of the signal processor is optimally arranged for high speed operation. The BMG unit 11 accesses a memory unit 14 which contains tables for the unit 11 to generate branch metrics. These generated branch metrics are stored in a register block 16 having branch metric register file and a path metric register file. These two files are accessed by the ACS unit 12 to find the optimum path into each state.
A memory unit 15 is divided into several parts, which are used by the STD unit 13 in tracing the survivor path. This memory division aids the user in the programming of the survivor-trace function.
Furthermore, by minimizing the memory requirements of the signal processor, it is possible to implement the processor on a single chip so that the processor may be readily adapted to a variety of applications, such as discussed above.
The Branch Metric Generator Unit
The branch metric generator unit 11 of FIG. 1 is shown in greater detail in FIG. 2. Each received symbol is stored in a register in a input register file 20 having several registers. The BMG unit 11 operates with a memory block 14 which has a table of branch metrics M1, a table of closest points M2, a memory of closest points M5 or M6, a memory of labels for parallel transitions M3 and a memory manager 52 for the memory of closest points M5 or M6 and memory of labels of parallel transitions M3.
The branch metrics for each particular application, i.e., code, are stored in the table M1. Ideally, the digital signals from the file 20A of a received symbol and the ideal symbol are used as the address to access the table M1 to obtain the branch metric. If the memory space required to store all the branch metrics between all possible received symbols and all ideal symbols in the selected code is small enough, then the table M1 can hold all the branch metrics in a straightforward manner. For an implementation of a Viterbi signal processor into a single integrated circuit as contemplated by the present invention, such is not the case typically.
In a typical application the table m1 stores only a portion of the branch metrics. With other function elements, such as adders and logic, in the BMG unit 11, the remaining portions of the branch metrics are readily calculated with programmed instructions from the control unit 17. The table m2, the two memory parts for closest points M5 or M6, the memory of labels for parallel transitions M3 and their manager 52 are used and adapted for decoding of multi-dimensional trellis codes and some convolutional codes.
For convolutional codes and partial response channels, the metric for each input bit is read from the table m1 and an adder 22 is used to add these metrics to form the branch metric of the whole input symbol.
For multi-dimensional trellis codes, the memory requirements to store the table of branch metrics can become quite large indeed. To save memory space, the branch metrics for the one-dimensional inputs are stored in table m1 and the higher dimensional cosets are built from these one-dimensional points. The adder 22 is used to add two one-dimensional metrics to form the branch metric of a two-dimensional symbol. The adder 22 is also used together with a 3:2 adder 23 to perform the ADD and add-compare-select (ACS) operations to generate the branch metrics for the higher dimensional cosets. These ACS operations are similar to those in the ACS unit 12. However, these operations are left in the BMG unit 11 to balance the computational load with the ACS unit 12.
Memory requirements may be further reduced if different cosets of a trellis code share the same table. For example, the same table may be used to look up the branch metrics of another coset by displacing the memory address to the table by a distance d. The adder 21 is used to displace the address to memory m1 and m2 by d, and the adder 22 is used to displace the nearest points read from the memory m2 by -d before storing it to the memory M5 or M6.
Since the branch metric register file 16A is accessed by both the BMG and ACS units 11 and 12, the register file 16A is divided into two banks. The two units 11 and 12 access registers in each bank alternately. This eliminates the requirement that the user make sure that the two units 11 and 12 do not read from and write to the same register.
The Add-Compare-Select Unit
A more detailed block diagram of the add-compare-select unit 12 in FIG. 1 is illustrated in FIG. 3. The unit 12 finds the most likely incoming path for each state by comparing the sums of the branch metrics and their corresponding path metrics, and selecting the path with the minimum sum as the most likely path.
The branch metric and its corresponding path metric are sent to a 4:2 adder 40 to be compared with the minimum sum. During the search operation for the minimum sum, the minimum is stored in a carry-save form to enable fast comparison. At the end of the search, the minimum is converted back into a single number and stored in a path metric register file 16B. This allows the user to deal with conventional numbers and saves the number of registers required to store the path metrics. A sign generator 41 uses the carry-select algorithm for a fast carry generation in order to determine the sign of the sum.
A memory manager 44 stores the pointer to the resulting survivor path into a survivor path memory M1. The manager 44 runs in parallel with the rest of the ACS unit 12.
The ACS unit 12 executes two classes of instructions: ACS and memory referencing. With ACS instructions, the program determines the most likely incoming path to each state, i.e., the path with the minimum metric. Then the pointer to this most likely path is stored into the survivor path memory M1 by memory referencing instructions. The pointer can be a previous state number or a ideal transition output.
The operands for the ACS instructions, the branch metrics and path metrics, are stored in the register files 16A and 16B respectively. As in the case for the branch metric register file 16A, the path metric register file 16B is divided into two banks of registers, one for storing the previous path metrics and the other for the updated path metrics.
The Survivor-Trace and Decoding Unit
The survivor-trace and decoding unit 13 of FIG. 1 is illustrated in greater detail in FIG. 4. The STD unit 13 traces the survivor path and finds a most likely symbol. The survivor path memory M1 is divided into several blocks. Each block corresponds to one stage of the trellis or equivalently one symbol period. Each block contains pointers to the survivor paths for all states. The pointers are implemented as offsets within a block. To trace one step of the survivor path, the block counter is decremented and concatenated with the offset within the block to form the address of the memory location that contains the offset within the next block. When the block counter overflows, the overflow bit is ignored to ensure automatic wraparound. An ALU 71 decodes the most likely symbol before transmitting the data out as output.
The STD unit 13 has memory referencing instructions to trace the survivor path. One instruction traces one stage, i.e., one symbol period, of the trellis backwards. Each instruction decrements the block counter 73, concatenates it with the offset counter 74 to form the memory address, and then reads the contents of the addressed memory M1 to M8 depending upon the specific instruction. The trace of the optimum path, the path with the smallest metric, yields the most likely symbol. Logic operations, such as EXCLUSIVE-OR, are used to decode and find the most likely input sequence to the encoder.
The counter 73 is used so that the block pointer wraps around when the limit of the survivor path memory is reached. If the length of the survivor is L, there should be at least L+1 blocks in the survivor path memory so that the ACS unit 12 does not overwrite the data before the STD unit 13 reads the data. The ACS unit 12 operates in a first-in, first-out manner to continuously overwrite the oldest block of data in the survivor path memory. The decoder block counter 73, on the other hand, starts tracing the survivor from this same block of most recently stored data at the next period, but in the opposite direction from the ACS unit 12.
Instruction Set for the Branch Metric Generator (BMG) Unit
A set of the instructions for the architecture in FIG. 2 is listed in FIG. 5. Rx represents a register location in the branch metric register file 16A, while rx represents a location in the input register file 20A. The symbol m1[xxx] means contents of the location pointed by xxx in m1.
In order to minimize the instruction word size, many instructions use implied return memory or register locations. The load instructions (ldR and ldM) initialize the starting locations of the implied addresses. Other load instructions (ld) are used to read the metric and the nearest points from the memories m1 and m2. These instructions can shift the register contents by an offset of d or negate the register contents before accessing the memories m1 and m2. Ldadd instructions add the two branch metrics for each dimension directly to form the branch metric for a two-dimensional symbol.
Rotation instructions are used, for example, for different cosets of the trellis codes with depth 1 and 3 to generate the branch metrics one dimension at a time from the branch metrics table. For all the rotation operations, the first operand stores the value in the x-axis and the second operand stores the value in the y-axis. The instruction rcc rotates the two points given in the operands by 45.degree. in the counter-clockwise direction and multiplies the rotated points by .sqroot.2. That is, if the two operands are r1 and r2, the operations
are performed. The instruction rc is used to rotate the operands by 45.degree. in the clockwise direction and multiply the rotated points by .sqroot.2. Thus, the operations,
The instructions rccst and rcst perform the same rotation operations as the rcc and rc respectively. However, the rotated points are divided by .sqroot.2, rather than multiplied by .sqroot.2, and they are also stored into memory M5 and M6.
When there are multiple transitions (or parallel transitions) from one state to another state, the ACS instructions are used to find the transition within the parallel transitions that has the minimum metric. This metric is the branch metric of that path.
Instruction Set for the Add-Compare-Select (ACS) unit
The instruction set for the ACS unit in FIG. 3 is listed in FIG. 6. In the table, Rx represents the register location x in the branch metric register file 16A, while Px represents the register location x in the path metric register 16B.
Similar to the BMG units, some instructions in the ACS unit use implied return memory or register locations. The instruction ldP initializes the implied return register location in the path metric register file 16B. The ACS control unit increments the block counter 53 by 1 and resets the offset counter 54 to zero after every symbol period. Rx represents the register location x in the branch metric register file 16A, while Px represents the register location x in the path metric register 16B.
Instruction Set for the Survivor-Trace and Decoding (STD) Unit
The instruction set based on the architecture of the STD unit shown in FIG. 4 is listed in FIG. 7. Note that the standard I/O instructions are not listed here. The STD consists of memory referencing operations and the basic logic operations in the ALU (see FIG. 4). The memory referencing operations are used to trace the optimal path and the logic operations are used for decoding the symbol into bits.
Mx[MARx] means contents in location MARx (memory address register x) in memory Mx 15. Sx represents the register location x in the register file 72.
An Example of Decoding Program For a Convolutional Code
An example of how the signal processor above could be programmed may be beneficial in understanding the operations of the signal processor. In this example a convolutional code without parallel transitions (4-state rate 1/2) is used. The trellis for the code is shown in FIG. 8A; the state diagram for the code is shown in FIG. 8B. The received inputs bits are stored in registers r0 and r1.
In this example, there is assumed to be only one table of metrics listed for ideal transition output=0. Therefore, the input bit must be flipped about the y-axis in order to use the same table to look-up the metric for ideal output transition -1.
While the description above provides a full and complete disclosure of the preferred embodiments of the present invention, various modifications, alternate constructions and equivalents may be employed without departing from the true scope and spirit of the invention. For example, while a signal processor with three independently programmable subprocessor units has been described, signal processors of lesser programmability (and lesser flexibility) are possible. For a selected set of convolutional codes the BMG unit may be hard-wired, and the ACS and STD units left programmable for the particular code desired. Another variation is to use the transition probabilities as the branch metrics, and to select the maximum sum of the branch metrics and its previous path metric to determine the most likely path.
Thus the present invention teaches a signal processor for sequential codes which is suitable for high-speed operation, flexible for many decoding functions, and adaptable for implementation into a single chip. Therefore, the present invention should be limited only by the metes and bounds of the appended claims.
Claims
What is claimed is:
1. A signal processor for decoding sequential codes, said processor receiving a sequence of symbols reflecting transitions between sequential states, said sequence time-indexed by an integer k, said signal processor comprising a first unit having a first control unit with programmed instructions for generating control signals, said first unit receiving said symbol sequence for generating the branch metrics between each received symbol and the set of possible symbols for time k responsive to said programmed instructions in said first control unit; a second unit having a second control unit with programmed instructions for generating control signals, said second unit coupled to said first unit for adding the branch metrics to the partial path metrics for each coded state, comparing the sums of the partial path metrics and the branch metrics for each coded state, and selecting the sum of the most likely path as the partial path metric for said coded state and appending said most likely path to the associated survivor path for each coded state for time k-1 responsive to said programmed instructions in said second control unit; a third unit having a third control unit with programmed instructions for generating control signals, said third unit coupled to said second unit for determining the coded state having the lowest partial path metric and the survivor-trace and decoding said symbol for a preselected time before time k-2 responsive to said programmed instruction in said third control unit; and a central control unit coupled to said first unit, said second unit and said third unit for synchronizing operations between said units; whereby said first unit, said second unit and said third unit operate concurrently and are independently programmable.
2. The signal processor as in claim 1 wherein said central control unit synchronizes said units at a rate of reception of said symbol sequence.
3. The signal processor as in claim 2 wherein each of said units operates independently until said central control unit synchronizes said units.
Non-Patent Literature (4)
- Clark, G. et al., Error-Correction Coding for Digital Communications, Plenum Press, New York, 1981, pp. 254-264.
- Gulak, P. et al., "VLSI Structures for Viterbi Receivers: Part I-General Theory and Applications", IEEE Journal on Selected Areas in Communications, vol. SAC-4, No. 1, Jan. 1986, pp. 142-154.
- Frenet, N. et al., "Implementation of a Viterbi Processor for a Digital Communications System with a Time-Dispersive Channel", IEEE Journal on Selected Areas in Communications, vol. SAC-4, No. 1, Jan. 1986, pp. 160-167.
- Fettweis, G. et al., "A 100 MBit/S Viterbi Decoder Chip: Novel Architecture and Its Realization", 1990 Int'l Conference on Communications, Apr. 1990, Paper No. 307.4.