Decoder for implementing an approximation of the Viterbi algorithm using analog processing techniques

• US 4,087,787 A
• Filed: 04/19/1977
• Issued: 05/02/1978
• Est. Priority Date: 04/19/1977
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Inventors: Acampora, Anthony
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/788,887
• Time in Patent Office: 378 Days
• Field of Search: 340/146.1 AQ, 340/146.1 AV
• US Class Current: 714/795
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms

Abstract

The present invention relates to two novel approaches for implementing an approximation of the Viterbi decoding algorithm using analog processing techniques which offer the potential for decoding at higher rates than currently achievable with digital processing decoders. The first approach employs at least one tapped delay means having a plurality of taps to enable the provision of the inverted and noninverted received analog channel waveform while path metric operations are performed by selectively switching between corresponding inverting and noninverting provisions of the at least one delay means according to the contents of a decision-directed digital memory. The second approach employs sample-and-hold circuits to store and update the path metrics based upon previous maximum-likelihood decisions.

Claims

1. A decoder for decoding a stream of received convolutionally encoded data, which may be corrupted by noise, having a predetermined plurality of possible states and an arbitrary predetermined code rate, comprising

an input terminal capable of receiving the stream of convolutionally encoded data;

first means connected to said input terminal capable of both (a) effecting the availability of at least a first and a second inverted and noninverted sample of the analog waveform received at said input terminal, each of said samples being separated by a time interval which corresponds to the data rate of the received signal and said first sample corresponds to the most recently received sample, and (b) computing likelihood functions represented by analog voltage signals for all possible transitions into each state of the convolutional code which has a plurality of possible states, said first means selectively using the inverted and noninverted analog waveforms of said first and second samples and the analog voltage signal representative of the most recently computed most probable likelihood function for each of said plurality of possible states for computing said likelihood functions;

second means connected to said first means capable of temporarily storing the most recently computed analog voltage signal generated by said first means representative of the most probable likelihood function for each state for subsequent use by said first means for computing the likelihood functions for each possible transition during the next time interval;

third means connected to the output of said first means for comparing the analog voltage signals representative of the likelihood functions associated with each state and generating an output signal indicating the most probable transition into each state of said plurality of possible states; and

fourth means responsive to the output of said third means for storing the most likely data sequence into each state over a predetermined length and for producing at an output terminal thereof a stream of data corresponding to the decoded data.

2. A decoder according to claim 1 wherein said first means comprises

at least one analog signal delay means including taps spaced at time intervals corresponding to the arbitrary predetermined code rate;

and

fifth means capable of effecting the availability of the inverted and noninverted samples representative of the analog input signals at said taps for computing said likelihood functions.

3. A decoder according to claim 1 wherein said first means comprises

a first and a second parallel transmission line coupled to said decoder input terminal for concurrently providing said first and second analog samples of the input waveform, respectively, said first transmission line including an analog signal storage means and said second transmission line including in sequence a means for delaying the input signal by one time interval of the arbitrary predetermined code rate and an analog signal storage means;

and said decoder further comprises

fifth means connected to the output of the analog signal storage means of said first and second transmission lines for effecting the availability of inverted and noninverted samples of each of the signals stored in each said storage means for computing said likelihood functions.

4. A decoder according to claim 1 wherein said first means comprises a separate adder means for each possible transition between states of the convolutional code, each adder means being capable of adding both the analog voltage signal stored in the second means for the associated state and the appropriate inverted and noninverted analog waveforms of the first and second input signal samples for computing the likelihood function for the associated transition between states.

5. A decoder according to claim 1 wherein

said first means comprises at least one delay means including a plurality of at least four taps spaced at time intervals corresponding to the arbitrary predetermined code rate for concurrently providing said first and second samples and at least a third and fourth noninverted samples of the analog waveform received at said input terminal;

and

said second means comprises a plurality of analog signal switching devices disposed in a predetermined array, each switching device being associated with both a separate one of the plurality of possible states and a separate one of the at least third and fourth taps of said at least one delay means and comprising a first and a second fixed terminal and an armature for switching between said first and second fixed terminals to selectively make available either one of the appropriate inverted and noninverted analog signal for the associated time interval to enable computation of the most probable likelihood function for the associated state.

6. A decoder according to claim 5 wherein said second means further comprises a plurality of digital storage devices disposed in an array corresponding to the array of said plurality of analog switching devices for storing, in response to the output signals from said third means, digital representations of the channel symbols along the most likely path leading to each state for each of the at least third and fourth time intervals of the arbitrary predetermined code rate, the digital signal stored in each storage device of the array causing the corresponding analog switching device in said array of switching devices to selectively make available the preferred one of the inverted and noninverted analog signal sample for computing the most probable likelihood function for the associated state.

7. A decoder according to claim 5 wherein said second means further comprises a separate second adder means for each state of said plurality of possible states having a plurality of input terminals which are each connected to the output from a separate one of the analog signal switching devices associated with the same state, each second adder means being capable of generating an output signal representative of the most recently computed most probable likelihood function for the associated state in response to the output signals from the associated analog signal switching devices.

8. A decoder according to claim 1 wherein said second means comprises a separate sample-and-hold circuit for each state of the plurality of possible states, each sample-and-hold circuit comprising storage means capable of storing the analog voltage signal representative of the most recently computed most probable likelihood function for the associated state in response to the output signal from said third means.

9. A decoder according to claim 8 wherein said storage means of each sample-and-hold circuit comprises a capacitor and each sample-and-hold circuit further comprises an analog signal switching means which is capable of selectively causing, in response to the output signal from said third means, the analog voltage signal of the most likely transition into the associated state as computed by said first means to be passed therethrough for storage in said capacitor.

10. A decoder according to claim 8 wherein the decoder further comprises

fifth means connected between said first and second means capable of temporarily storing said likelihood functions for all possible transitions into each state as computed by said first means for a period of time which is at least equal to the time needed for said third means to generate its output signal and convey said output signal to said second means.

11. A decoder according to claim 8 wherein the decoder further comprises

fifth means connected between said first and second means capable of temporarily delaying the likelihood functions for all possible transitions into each state as computed by said first means for a period of time which is at least equal to the acquisition time of said sample-and-hold circuits.

12. A decoder according to claim 8 wherein said sample-and-hold circuits are connected to said first means in a manner to cause the analog signal voltage stored in a first one of the sample-and-hold circuits to be effectively subtracted in the computation of said all possible transitions into each of said states.

13. A decoder according to claim 1 wherein said fourth means comprises a plurality of digital storage devices arranged in a predetermined array with each storage device being associated with both a separate one of the plurality of possible states and a separate one of the integers of said predetermined length to store said most likely data sequence into each state, the storage devices of the array being interconnected such that in response to the output signals from said third means a binary value indicating the most likely data bit representing the most probable transition into each state is stored in the first register of the sequence for that state while the data bit previously stored in each storage device is concurrently shifted into no more than two digital storage devices of the next stage of the array.

14. A decoder according to claim 13 wherein the output of the last storage device in one of the most likely data sequences in the array is selectively coupled to the output terminal of said fourth means for providing said stream of data corresponding to the decoded data.

15. A decoder according to claim 13 wherein said fourth means further comprises a majority logic gate connected to the output of the last storage device in each most likely data sequence stored in the array, said majority logic gate generating an output binary value indicated by the majority of said last storage devices and in the event of a tie generating a predetermined binary value.

16. A decoder according to claim 6 wherein said plurality of storage devices are interconnected such that in response to the output signals from said third means two binary values indicating the most likely channel bits corresponding to the most probable transition into each state are stored in the first and second storage devices associated with the most likely path leading into each state while data bits previously stored in each of said storage devices is concurrently shifted into no more than two digital storage devices of the subsequent alternate stage of the array.

17. A method of decoding a stream of received convolutionally encoded data having a predetermined plurality of possible states and an arbitrary predetermined code rate which may be corrupted by noise, the method comprising the steps of:

(a) making available at least a first and a second inverted and noninverted sample of the received analog waveform, each of said samples being separated by a time interval corresponding to the data rate of the received signal and said first sample corresponds to the most recently received sample;

(b) computing likelihood functions for all possible transitions into each state of the convolutional code by selectively using the inverted and noninverted analog waveforms of said first and second samples and analog voltage signals representative of the most recently computed most probable likelihood function for each of said plurality of possible states to generate analog voltage signals representative of the computed likelihood functions;

(c) temporarily storing the most recently computed analog voltage signal generated in step (b) which is representative of the most probable likelihood function for each state for subsequent use in step (b) for computing the likelihood functions for each possible transition during the next time interval;

(d) comparing the analog voltage signals representative of the likelihood functions associated with each state as generated in step (b) for determining the most probable transition into each state of said plurality of possible states; and

(e) in response to the determination made in step (d), generating a binary bit corresponding to the decoded data for the most probable transition into each state and concurrently storing the most likely data sequence into each state over a predetermined length for producing an output stream of data corresponding to the decoded data.