Minimum memory implementation of high speed viterbi decoder

Details Minimum memory implementation of high speed viterbi decoder Minimum memory implementation of high speed viterbi decoder

1998-12-29

2001-08-07

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S786000, C714S796000

Reexamination Certificate

active

06272661

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention pertains in general to maximum-likelihood decoders and, more particularly, to a Viterbi decoder structure utilizing minimal memory.
BACKGROUND OF THE INVENTION
In digital communications systems, received data may have been corrupted by noise and distortion. As such, digital data obtained at the receiving station may not be an accurate replica of the data transmitted. Such errors may be reduced by encoding the transmitted data to add redundancy to the data before transmission.
Redundancy may be introduced by increasing the symbol rate. For example, error checking and error correcting codes may be appended to fixed-length blocks of source data and the combination then sent at a higher data rate. The resulting increase in bandwidth, however, subjects the receiver to additional noise.
As an alternative, signal-space codes may be utilized to add redundancy by converting the source data into a “line code” which may be sent at the same symbol rate but which utilizes an enlarged number of possible symbols (discrete points within the signal space). The bandwidth required by such codes is no larger than that of an equivalent encoded system, such that there is no increase in noise at the receiver. However, due to the fact that symbols must be more closely spaced to avoid an increase in transmitted power, noise immunity is reduced. In transmission systems having a limited, fixed bandwidth, such as a voice-grade telephone link, signal-spaced coding permits significantly higher rates of error-corrected transmission to be realized.
One class of signal-spaced code which has seen increasing acceptance due to its superior performance is the “trellis code,” a convolutional code best explained utilizing a trellis diagram. In the trellis diagram, vertical columns of nodes represent the possible states which can be assumed at successive points in time by a “state machine” which encodes the source data. Before transmission begins, the encoding machine is initialized to a predetermined state. Thereafter, each transmitted symbol specifies the transition from the current state to a limited number of permissible successor states. The sequence of symbols previously transmitted specifies the current state of the encoding machine. The current state in turn specifies which symbols out of the entire alphabet may validly appear next in the transmitted sequence. Thus, only selected sequences of transmitted symbols are permitted by the coding scheme and these legitimate sequences may be represented by paths through the trellis diagram.
Each transmitted symbol accordingly represents not only a source code, but also contains historical information, reflected in the state information which can be derived from the received sequence of symbols. This redundancy permits the transmitted symbol sequence to be accurately reconstructed in a decoding operation even though noise and distortion have altered the message-bearing signal during transmission.
Trellis coding is utilized to particular advantage in the implementation of voice band data modems of the type used to provide high, error-free data rates over dial-up and leased line analog telephone facilities. In order to process these structures, the highly efficient Viterbi algorithm has been utilized, named after its originator, A. J. Viterbi. The Viterbi technique makes use of the fact that a number of the transitions to a given state can be deleted, as they do not represent the least-likely path to that transition. In this matter, a lower number of transitions is required to be stored when determining the most likely path between states.
SUMMARY OF THE INVENTION
The present invention disclosed and claimed herein comprises a method for decoding an encoded data sequence with the Viterbi algorithm, wherein convolutionally encoded symbols are transmitted and received. The encoded data is received wherein the encoded data sequence has a known state at the end of the sequence. A table of information nodes is built for each received symbol and each state of the convolutional encoding process. There are M states and M nodes and, for each state and corresponding node associated with each received symbol, there is associated therewith both a decoded data bit and a path pointer to the most likely state and corresponding node associated with the preceding received symbol. The decoded data word from the information in the table is extracted from the table. This is achieved by first selecting from the table associated with the last received symbol at the end of the sequence a node corresponding to a known state therefor that constitutes a selected node. The data bit is then extracted from the select node and appended to an encoded data word. A path is traversed from the selected node for the associated symbol to the state and corresponding node of the preceding symbol indicated by the path pointer for the selected node. The steps of extracting and traversing are repeated for each received symbol until the data for the first symbol is examined and the associated decoded data bit is appended to the decoded data word.


REFERENCES:
patent: 4757506 (1988-07-01), Heichler
patent: 4829575 (1989-05-01), Lloyd
patent: 5095484 (1992-03-01), Karabed et al.
patent: 5144644 (1992-09-01), Borth
patent: 5331665 (1994-07-01), Busschaert et al.
patent: 5410556 (1995-04-01), Yeh et al.
patent: 5432803 (1995-07-01), Liu et al.
patent: 5502736 (1996-03-01), Todoroki
patent: 5509021 (1996-04-01), Todoroki
patent: 5539757 (1996-07-01), Cox et al.
patent: 5588028 (1996-12-01), Parizhsky
patent: 5608737 (1997-03-01), Kimura et al.
patent: 5646950 (1997-07-01), Varanasi et al.
patent: 5867408 (1999-02-01), Chauvel et al.
patent: 5946361 (1999-08-01), Araki et al.
patent: 5996112 (1999-11-01), Dabiri et al.
patent: 6108374 (2000-08-01), Balachandran et al.
patent: WO 95/01032 (1995-01-01), None
Droma & Zeng. “Memory savings in Viterbi decoders for (n, 1, m) convolutional codes”. Electronics Letters. Oct. 9, 1997. vol. 33 Issue 21. pp. 1758-1759.

Affiliated with

Also associated with

Rating

Minimum memory implementation of high speed viterbi decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Minimum memory implementation of high speed viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum memory implementation of high speed viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2520791