Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-18
2004-03-02
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S792000
Reexamination Certificate
active
06701483
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the decoding of digital signals, and more particularly to a search-based decoding scheme that can be used, for example, in connection with a communication system to decode symbols received over a noisy communication channel.
There are many sequential search algorithms that search through graphs (such as, for example, trellises) using various criteria to determine whether to proceed forward or backward through the graph and likewise which edges to take.
Some of the commonly known algorithms of this type are the minimum distance search algorithm well known in the art and the Fano decoding algorithm. The Fano algorithm is described, for example, in J. M. Wozencraft and I. M. Jacobs,
Principles of Communications Engineering
, section 6.4 and in S. Lin and D. J. Costello, Jr.,
Error Control Coding: Fundamentals and Applications
, section 12.2.
The minimum distance search algorithm calculates the minimum distance between two vertices in the graph based on the weighting function. If the two vertices represent two towns, the edges represent highways between all towns, and a function is defined on each edge that corresponds to the distance between the two towns represented by the two vertices associated with the edge, then the minimum distance search algorithm finds the shortest possible way to travel between the two towns.
In the Fano algorithm, a sequential decoder searches through a trellis in a path that best matches a received sequence of symbols. An advantage of the Fano algorithm is its independence to the number of states of the trellis. However, the execution time of such algorithm may be very lengthy under a noisy environment, making the use of the Fano algorithm impractical for delay-sensitive applications.
It is desirable to estimate the most likely path through the trellis as fast and accurately as possible, since the most likely path can be used directly to estimate the message that was transmitted through the communications channel. In general, for the Fano Algorithm, the faster the trellis can be searched, the more reliable the estimate can be. Additionally, the faster the trellis can be searched, the faster data may be transmitted through the communications channel, which results in a higher data transmission rate for the communications system.
For the foregoing reasons, there is a need for a method and apparatus for providing an improvement to search-based decoding algorithms. In particular there is a need for reducing the latency inherent to the search-based decoding algorithms including the Fano algorithm.
SUMMARY OF THE INVENTION
The present invention encompasses the use of a search-based decoding algorithm in combination with a fast search-based decoding scheme to reduce the latency inherent with such algorithm. In accordance with the principles of the present invention, distance functions needed in the determination of which edge to follow from one vertex to another vertex at a next stage are pre-computed. This allows the algorithm to proceed at a rate equal to the amount of time it takes to perform said determination.
A method in accordance with one embodiment of the present invention comprises the steps of: (1) computing input values to distance functions associated with a set of edges wherein the edges are at a distance d at least equal to 2 from a current vertex; (2) evaluating the distance functions associated with the edges at distance d=1; and (3) determining an edge to follow from the current vertex to a next vertex, based upon said evaluated distances. The method according this embodiment may be used in conjunction with the Fano algorithm.
In another embodiment, a method for performing a fast search-based decoding in a graph defined by a plurality of vertices and edges is disclosed. The method comprises the steps of: (1) computing input values to distance functions associated with a set of edges wherein the edges are at a distance d at least equal to 2 from a present vertex; (2) obtaining the distance functions associated with the edges at distance d=1; and (3) determining an edge to follow from the current vertex to a next vertex based upon said obtained distance functions. The method may further comprise the step of evaluating distance functions associated with the edges at distance d−2 from the current vertex and wherein the evaluated distance functions are used in a next stage to determine which edge to follow from said next vertex.
In yet another embodiment, the fast search based decoding is used in conjunction with the Fano algorithm.
REFERENCES:
patent: 6088405 (2000-07-01), Hladik et al.
patent: 6205444 (2001-03-01), Floratos et al.
patent: 6343105 (2002-01-01), Saegusa
patent: 6484285 (2002-11-01), Dent
patent: 6510538 (2003-01-01), Jakobsen
Wozencraft, John M. et al., “Principles of Communication Engineering”, John Wiley & Sons, Inc., 1965, pp. 425-439.
Lin, Shu et al., “Error Control Coding: Fundamentals and Applications”, Prentice-Hall, Inc., 1983, pp. 350-365.
www:http://jungfrau. usc.edu/ee577b/fano.html, “Class Project: The Fano Algorithm, An Introduction.”
Heegard Chris
Petler Scott
Shoemake Matthew B.
Alantro Communications, Inc.
Brady III W. James
Telecky , Jr. Frederick J.
Ton David
LandOfFree
Fast search-based decoding scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast search-based decoding scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast search-based decoding scheme will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3190445