Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1998-05-08
2001-08-07
Chin, Stephen (Department: 2634)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S261000, C375S264000, C375S265000, 36
Reexamination Certificate
active
06272188
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to finding a maximum or minimum quantity in a group and an associated index and particularly to finding a minimum or maximum accumulated cost and the associated state at a symbol instant in the process of decoding a signal in a viterbi decoder.
BACKGROUND OF THE INVENTION
A viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoding is used in decoding a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a system that is transmitted through various media in a system with each set of bits representing a symbol instant. Viterbi decoding is employed in digital communications over communication channels such as satellite-to-earth, cellular telephony, microprocessor-to-disk, modem-to-modem and others. Viterbi decoders have been implemented on hardware microprocessors, microcontrollers, and digital signal processors. Viterbi decoding is well-known and applications can be found in U.S. Pat. Nos. 5,490,178; 5,454,014; 5,559,837; 5,465,275; 5,471,500; 5,144,644; and 4,493,082, the disclosures of which are hereby incorporated by reference.
A viterbi implementation consists of four steps: branch and path metric computation; a compare-select operation; a minimum or maximum state cost determination; and a traceback operation to determine a decoded symbol. In the decoding process, a viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which bit sequence was most likely to have been transmitted. The possible transitions from a state at one symbol instant, or present state, to a state at a next, subsequent symbol instant, or next state, is limited. Each possible transition from a present state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can only transition to a limited number of next states upon receipt of the next bit or bits in the bitstream. Thus, some branches survive to become part of a path and other branches do not survive to become part of a path. By eliminating those transitions or branches that are not permissible, computational efficiency can be achieved in determining the most likely paths to survive. A viterbi decoder typically defines and calculates a branch metric associated with each branch and employs the branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric or accumulated cost that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as a sum of the branch metric and the path accumulated cost at the present state origin of the branch metric. A maximum or minimum extremum may be selected.
While several branches, and several paths, survive the transition from one symbol instant to the next symbol instant, a traceback operation through the surviving paths is employed to select the most likely bit or bit sequence to have been transmitted. The sequential symbol instants may be represented in an array referred to as a trellis. Identifying the extremum accumulated cost path starting with a given symbol instant is referred to as a traceback operation. The number of symbol instants back through the trellis that the extremum accumulated cost path extends is the length, or depth, of the traceback operation. At the end of the traceback operation, the individual state in the trellis associated with the surviving path that originated at an extremum accumulated cost is translated into the most likely bit or bits to have been transmitted in that symbol instant. The bit or groups of bits is referred to as a decoded symbol.
In communications applications employing viterbi decoding in which a single bit is transmitted each symbol instant, two possible present states can transition, or branch, into a single next state and a single bit is sufficient to uniquely determine which of the two possible branches transitioned into a given next state.
What is needed is an efficient method for identifying an extremum accumulated cost, such as a maximum or minimum, for use in decoding a received digital signal in a viterbi decoder.
SUMMARY OF THE INVENTION
The invention includes a method of identifying an extremum value and an index in a group of values where each value has an associated index. A count register is initialized to an initial count. A value from the group as well as a predetermined value are provided simultaneously to an arithmetic logic unit and a multiplexer. The value from the group and the predetermined value are compared in the arithmetic logic unit. A selector is set to one of a first or second logic state. In the first logic state the selector selects a minimum; in the second logic state the selector selects a maximum. One of the value and the predetermined value are selected as an extremum based on a flag set by the comparison in the arithmetic logic unit and the selector. The predetermined value is replaced with the extremum and the count register count is stored when the selector is set to a first state and the value is less than the predetermined value. The predetermined value is replaced with the extremum and the count register count is stored when the selector is set to the second state and the value is greater than the predetermined value.
REFERENCES:
patent: 5537445 (1996-07-01), Blaker et al.
patent: 5726923 (1998-03-01), Okumura et al.
patent: 6009128 (1999-12-01), Mobin et al.
patent: 6029267 (2000-02-01), Simanapalli et al.
Mobin Mohammad Shafiul
Simanapalli Sivanand
Tate Larry R.
Agere Systems Guardian Corp.
Chin Stephen
Liu Shuwang
Smith David L.
LandOfFree
Single-cycle accelerator for extremun state search does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single-cycle accelerator for extremun state search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-cycle accelerator for extremun state search will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476458