Artificial neural network viterbi decoding system and method

• US 5,548,684 A
• Filed: 04/22/1994
• Issued: 08/20/1996
• Est. Priority Date: 04/22/1994
• Status: Expired due to Fees

• Current Assignee: Georgia Tech Research Corporation (University System of Georgia)
• Original Assignee: Georgia Tech Research Corporation (University System of Georgia)
• Inventors: Wang, Xiao-an, Wicker, Stephen B.
• Primary Examiner(s): Downs, Robert W.
• Assistant Examiner(s): KATBAB, ABDOLLAH
• Application Number:
  US08/232,812
• Time in Patent Office: 851 Days
• Field of Search: 395/21, 395/22, 395/2.51, 371/43
• US Class Current: 706/16
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/4184 using register-exchange H03M13/4192 takes precedence
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

An artificial neural network (ANN) decoding system decodes a convolutionally-encoded data stream at high speed and with high efficiency. The ANN decoding system implements the Viterbi algorithm and is significantly faster than comparable digital-only designs due to its fully parallel architecture. Several modifications to the fully analog system are described, including an analog/digital hybrid design that results in an extremely fast and efficient Viterbi decoding system. A complexity and analysis shows that the modified ANN decoding system is much simpler and easier to implement than its fully digital counterpart. The structure of the ANN decoding system of the invention provides a natural fit for VLSI implementation. Simulation results show that the performance of the ANN decoding system exactly matches that of an ideal Viterbi decoding system.

Claims

1. A maximum likelihood decoding system for high speed and efficient decoding of convolutionally-encoded data streams of constraint lengths greater than 6, comprising an analog neural network having a plurality of analog neurons, said analog neurons for mathematically combining analog signals, said analog neural network adapted to receive a convolutionally-encoded digital data stream and adapted to decode said data stream using said analog neurons into a sequence of digital values by performing a Viterbi algorithm, said analog network minimizing error in said digital values.

2. The system of claim 1, wherein said analog neural network comprises an analog means for determining a maximum likelihood code word corresponding with said digital data stream based upon path metrics associated with paths in said analog neural network.

3. The system of claim 1, further comprising a digital means connected to said analog neural network, said digital means for storing a digital information sequence and for updating said information sequence.

4. The system of claim 1, further comprising an analog means connected to said analog neural network, said analog means for storing a digital information sequence and for updating said information sequence.

5. The system of claim 1, further comprising a means for identifying a minimum path metric among various states and for reducing path metrics by a proportional amount.

6. The system of claim 1, further comprising a digital shift register using analog neurons.

7. The system of claim 1, further comprising a branch metric computer for processing analog metric values associated with neurons in said analog neural network.

8. The system of claim 1 situated within an integrated circuit.

9. The system of claim 1, wherein said plurality of analog neurons include threshold-limiting neurons and hard-limiting neurons.

10. A decoding system for high speed and efficient decoding of convolutionally-encoded data streams utilizing an artificial neural network and the Viterbi algorithm, comprising:

(a) a correlation computation means having first and second neurons, said first and second neurons being adapted to mathematically combine analog signals, said first neurons for receiving said convolutionally-encoded data stream and for generating branch metrics, said second neurons for mathematically combining said branch metrics from said first neurons with previous partial path metrics to derive current partial path metrics;

(b) a surviving path selection means in communication with said correlation computation means, said surviving path selection means having third and fourth neurons, said third neurons for identifying surviving partial path metrics, said fourth neurons for providing said surviving partial path metrics to said second neurons, said surviving partial path metrics being used by said second neurons as previous partial path metrics during a subsequent time increment;

(c) a maximum path metric selection means in communication with said surviving path selection means, said maximum path metric selection means for determining identities of largest surviving partial path metrics;

(d) a register exchange means in communication with said surviving path selection means, said register exchange means for storing and updating the magnitudes of surviving partial path metrics; and

(e) an output register selection means in communication with said maximum path metric selection means and said register exchange means, said output register selection means for providing a convolutionally-decoded output data stream with digital values corresponding with said surviving partial path metrics.

11. The system of claim 10, wherein said register exchange means comprises a digital means for storing a digital information sequence and for updating said information sequence.

12. The system of claim 10, wherein said register exchange means comprises an analog means for storing a digital information sequence and for updating said information sequence.

13. The system of claim 10, further comprising a means in communication with said second and fourth neurons, said means for identifying a minimum partial path metric output from said fourth neurons and for reducing partial path metrics by an amount corresponding with said minimum partial path metric at said second neurons.

14. The system of claim 10 wherein said output register selection means comprises a digital shift register comprising analog neurons.

15. The system of claim 10 implemented within an integrated circuit.

16. A decoding system for high speed and efficient decoding of convolutionally-encoded data streams utilizing an artificial neural network and the Viterbi algorithm, comprising:

(a) a correlation computation means having first and second neurons, said first neurons for receiving said convolutionally-encoded data stream and for generating branch metrics, said second neurons for mathematically combining said branch metrics from said first neurons with previous partial path metrics to derive current partial path metrics;

(b) a surviving path selection means in communication with said correlation computation means, said surviving path selection means having third and fourth neurons, said third neurons for identifying surviving partial path metrics, said fourth neurons for providing said surviving partial path metrics to said second neurons, said surviving partial path metrics being used by said second neurons as previous partial path metrics during a subsequent time increment;

(c) a register exchange means in communication with said surviving path selection means, said register exchange means for storing and updating magnitudes of said surviving partial path metrics;

(d) an output register selection means in communication with said register exchange means, said output register selection means for providing a convolutionally-decoded output data stream with digital values corresponding with said surviving partial path metrics; and

wherein a decoding depth associated with a trellis defined by said first, second, and third neurons is sufficiently large so that a magnitude of any one of said surviving partial path metrics output from said register exchange means is selected for output by said output register selection means.

17. A method for high speed and efficient decoding of convolutionally-encoded data streams with maximum likelihood using the Viterbi algorithm, comprising steps of:

receiving a convolutionally-encoded digital data stream of constraint lengths greater than 6; and

decoding said data stream into a sequence of digital values using an analog neural network having a plurality of analog neurons and the Viterbi algorithm, thereby minimizing error in said digital values.

18. A method for high speed and efficient decoding of convolutionally-encoded data streams utilizing a neural network and the Viterbi algorithm, comprising:

receiving the convolutionally-encoded data stream;

generating branch metrics by passing said data stream through first neurons;

mathematically combining at third neurons said branch metrics from said first neurons and said previous surviving partial path metrics from said second neurons;

comparing at fourth neurons potential surviving partial path metrics output from said third neurons;

determining identities at said fourth neurons of current surviving partial path metrics from said comparisons of said potential surviving partial path metrics;

determining largest magnitudes of said current surviving partial path metrics; and

providing a convolutionally-decoded output data stream having a sequence of digital values corresponding with predetermined states corresponding with said current surviving partial path metrics, thereby minimizing error in said digital values.

19. The method of claim 18, further comprising the step of using a trellis defined by said first, second, and third neurons having a decoding depth which is sufficiently large so that said largest magnitudes are selected arbitrarily from said current surviving partial path metrics.