Signal processing circuit to implement a Viterbi algorithm

• US 5,881,106 A
• Filed: 08/30/1995
• Issued: 03/09/1999
• Est. Priority Date: 09/05/1994
• Status: Expired due to Term

• Current Assignee: SGS-Thomson Microelectronics (STMicroelectronics NV)
• Original Assignee: SGS-Thomson Microelectronics (STMicroelectronics NV)
• Inventors: Cartier, Michel
• Primary Examiner(s): LE, AMANDA T
• Application Number:
  US08/521,519
• Time in Patent Office: 1,287 Days
• Field of Search: 375/262, 375/340, 375/341, 371/43, 371/41, 371/43.6-43.8, 341/107, 341/94, 364/133, 364/769
• US Class Current: 375/262
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/4169 using traceback H03M13/4192 takes precedence

Abstract

To carry out the processing operations relating to the implementation of a Viterbi algorithm, an integrated circuit comprising a processor and a coprocessor is made. The coprocessor is constructed so as to carry out operations of accumulation, comparison and selection in order to limit or reduce the work of a processor that would have to carry out these operations. By judiciously choosing the structure of the coprocessor, it is possible to make this co-processor sufficiently programmable so that it is suited to various situations of implementation of the Viterbi algorithm.

Claims

1. A signal processing circuit comprising a processor, a data memory to store data received and data processed by the signal processing circuit, a program memory to store a plurality of instructions of a processing program, wherein a portion of said plurality of instructions implement a Viterbi algorithm, wherein said circuit comprises a coprocessor linked with the program memory to carry out a processing operation of accumulation, comparison and selection corresponding to the Viterbi algorithm, wherein the coprocessor comprises

adder/subtractor type adders to limit iterative computations undertaken by the coprocessor.

2. The circuit according to claim 1, wherein the coprocessor has only one ACS type circuit to carry out two simultaneous additions, compare the results of the two simultaneous additions and select one of the two simultaneous additions.

3. A signal processing circuit comprising a processor, a data memory to store data received and data processed by the signal processing circuit, a program memory to store a plurality of instructions of a processing program, wherein a portion of said plurality of instructions implement a Viterbi algorithm, wherein said circuit comprises a coprocessor linked with the program memory to carry out a processing operation of accumulation, comparison and selection corresponding to the Viterbi algorithm, wherein the coprocessor comprises

a set of registers whose inputs and outputs are connected to multiplexers to make the coprocessor carry out several simultaneous processing operations at each memory access operation.

4. A circuit according to claim 3, wherein the coprocessor has only one ACS type circuit to carry out two additions simultaneously, compare the results of the two additions and select one of the two additions.

5. The circuit according to claim 3, wherein the coprocessor comprises adder/subtractor type adders to limit iterative computations undertaken by the coprocessor.

6. A signal processing circuit comprising a processor, a data memory to store data received and data processed by the signal processing circuit, a program memory to store a plurality of instructions of a processing program, wherein a portion of said plurality of instructions implement a Viterbi algorithm, wherein said circuit comprises a coprocessor linked with the program memory to carry out a processing operation of accumulation, comparison and selection corresponding to the Viterbi algorithm, wherein the coprocessor comprises

two buses so that the coprocessor can alternately be linked, in reading mode and then in writing mode, with two memories and wherein the processor has a circuit to alternate the connections of the coprocessor with each of the buses.

7. The circuit according to claim 6, wherein the coprocessor has only one ACS type circuit to carry out two simultaneous additions, compare the results of the two simultaneous additions and select one of the two simultaneous additions.

8. A circuit according to claim 6, wherein the coprocessor comprises a set of registers whose inputs and outputs are connected to multiplexers to make the coprocessor carry out several simultaneous processing operations at each memory access operation.

9. A method for decoding a received signal implementing a Viterbi algorithm, the method comprising the following steps:

a first adding step for adding a first old path metric to a first branch metric to produce a first new path metric;

a second adding step for adding a second old path metric to a second branch metric to produce a second new path metric, wherein the first adding step and the second adding step are performed simultaneously;

a first comparing step for comparing the first new path metric and the second new path metric to determine a first minimum path metric;

a selecting step for selecting one of the first and second new path metrics as the first minimum path metric wherein the first minimum path metric is determined by a comparator, the comparator producing a control signal to control a multiplexer, and wherein the first minimum path metric is selected by the multiplexer; and

determining a survivor value based on the control signal of the multiplexer wherein the control signal is stored as the survivor value.

10. The method of claim 9, further comprising the following steps:

a third adding step for adding a third old path metric to a third branch metric to produce a third new path metric;

a fourth adding step for adding a fourth old path metric to a fourth branch metric to produce a fourth new path metric, wherein the third adding step and the fourth adding step are performed simultaneously and wherein the third and fourth adding steps are performed sequentially after the first and second adding steps; and

a second comparing step for comparing the third new path metric and the fourth new path metric to determine a second minimum path metric, wherein the second comparing step is performed sequentially after the first comparing step.

11. The method of claim 9, further including a step of encoding the survivor value as a single bit.

12. The method of claim 11, further including a step of storing the survivor in a shift register, the shift register being capable of storing a finite number of oldest survivors.

13. A signal processing system for implementing a Viterbi algorithm, the system comprising:

processing means;

data memory to store data received and data processed by the signal processing system;

program memory to store a plurality of instructions of a processing program, wherein a portion of said plurality of instructions implement a Viterbi algorithm, and

coprocessing means operable with program memory for performing a processing operation of accumulations, comparison and selection corresponding to the Viterbi algorithm, wherein coprocessing means includes;

means for performing two simultaneous additions;

means for comparing the two simultaneous additions; and

means for selecting one of the two simultaneous additions.

14. The system of claim 13, wherein the coprocessing means includes two buses allowing the coprocessing means to be linked, in reading mode and then in writing mode, with two memories, and wherein the processing means includes means for alternating connections of the coprocessing means with each of the buses.

15. The system of claim 13, wherein the coprocessing means includes means for limiting iterative computations performed by the coprocessing means.