Patent Publication Number: US-6701483-B1

Title: Fast search-based decoding scheme

Description:
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. 
    
    
     These and other features and objects of the invention will be more fully understood from the following detailed description of the preferred embodiments which should be read in light of the accompanying drawings. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and form a part of the specification, illustrate the embodiments of the present invention and, together with the description serve to explain the principles of the invention. 
     In the drawings: 
     FIG. 1 is an example graph structure used in describing the invention; 
     FIG. 2 is a flowchart for performing an operation in accordance with one embodiment of the present invention; 
     FIG. 3 is a flowchart for performing an operation in accordance with another embodiment of the present invention; 
     FIG. 4 is an illustration of the fast search-based decoding algorithm as applied to the Fano decoder; and 
     FIG. 5 is a block diagram of a Fano decoder using the principles of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In describing a preferred embodiment of the invention illustrated in the drawings, specific terminology will be used for the sake of clarity. However, the invention is not intended to be limited to the specific terms so selected, and it is to be understood that each specific term includes all technical equivalents which operate in a similar manner to accomplish a similar purpose. 
     With reference to the drawings in general and FIGS. 1 through 5 in particular, the apparatus of the present invention is disclosed. 
     FIG. 1 shows a graph structure which can be defined by its set of nodes or “vertices”, V={V 1 , . . . V 11 }, and its set of branches or “edges”, E={e 1 , . . . e 13 }. Each edge connects two vertices in the set V. An edge may be specified as a pair (V i , V k ), where the edge connects vertices V i  and V k  in V. Associated with any vertex V i  in the graph is a set of connected edges. This set of edges may be thought of as the set of edges that may be reached by starting at vertex V i  and following a valid sequence of one edge from V i . Likewise, there is a set of edges which may be defined as the set of edges that may be reached by starting at vertex V i  and following a valid sequence of two edges from V i . The set E v     1     n  shall refer to the set of edges that may be reached by starting at vertex V i  and following a valid sequence of n edges. Edges in this set will be defined herein as edges at distance d=n from vertex V i . 
     In FIG. 1, vertex V 1  has four edges attached to it. This means that E v     1     1 ={e 2 , e 3 , e 8 , e 9 }. If we consider all of the edges that are two steps away from V 1 , the set E v     1     2 ={e 1 , e 4 , e 7 , e 10 , e 12 , e 13 } is obtained. Note that self loops and parallel edges are included. The invention described herein applies to the most general of graphs, including those with self-loops, parallel edges, and cycles. 
     Algorithms that search through graphs typically make their decisions as to how to proceed through the graph based on some weighting or measure on each edge. For example, a metric function f: E→R associates a real valued measure with each edge in the graph. The metric function may be based on a distance metric or on a correlation metric. 
     When searching through a graph, it is typical for the processing at each vertex, current vertex V c , and at each stage of the search procedure to consist of performing the three following steps: 
     (A) obtaining or computing values that are the inputs to the distance or weight function for all edges in E v     c     1 ; 
     (B) evaluating the distance or weight function for all edges (or a subset of the edges) in E v     c     1 ; and 
     (C) determining which edge to follow from the current vertex, V c , to the next vertex based upon the values calculated in step (B). 
     The rate at which the algorithm may proceed through the graph is a function of the amount of time that it takes to perform steps (A), (B) and (C) in sequence. Let T A  be the time (in seconds) that it takes to perform step (A), T B  be the time (in seconds) that it takes to perform step (B), and let T C  be the time (in seconds) that it takes to perform step (C). Then, the search algorithm may process each vertex in (T A +T B +T C ) seconds. The invention described herein allows searching of the graph at rates faster than T A +T B +T C  seconds per vertex, without reduction of T A  or T B  or T C . 
     FIG. 2 illustrates a flowchart for performing a fast search through a graph in accordance with one embodiment of the present invention. In searching through a graph defined by its vertices and edges, the process described in the flowchart of FIG. 2 provides a reduction in the latency inherent in such search by pre-computing values needed in the evaluation of a distance or weight function. The distance or weight function may be used as a metric to determine which edge or branch to proceed on at each stage of the search. 
     As illustrated in FIG. 2, the process begins at step  200 . The inputs to the distance or weight functions associated with the edges in the set E 2   vc  are computed or retrieved at step  210 . As an example, the inputs may be the estimated transmitted symbols and the received symbols. At step  220 , the distance or weight functions associated with the edges in the set E 1   vc  are evaluated and at step  230  the next vertex is determined based on the result of the evaluation performed at step  220 . As an example, for a distance function based on the Euclidean distance between the estimated transmitted symbol and the received symbol, the next vertex will be the one along the edge which has the lowest Euclidean distance associated with it. The process ends at step  240  as illustrated in FIG.  2 . 
     The steps as illustrated with reference to FIG. 2 may be carried iteratively, at every stage of the search procedure. Also, initialization steps may be performed prior to carrying the steps in the flowchart of FIG.  2 . The initialization steps may be performed at the first stage of the search procedure. In one embodiment, the initialization may comprise the steps of computing or retrieving the values needed in the evaluation of the distance functions associated with the edges in the sets E 1   vc  and E 2   vc . 
     When the steps of FIG. 2 are applied for search-based decoding, the determination of which edge to follow only takes (T B +T C ) seconds, assuming T A &lt;(T B +T C ). The algorithm may thus proceed at a rate (T B +T C ) seconds per vertex since the result of the operation performed at step  210  is not needed for that determination. In one embodiment, step  210  is performed in parallel with steps  220  and  230  which allows for the algorithm to process a vertex at a faster rate as compared to the prior art. In the case where T A &gt;(T B +T C ), the algorithm proceeds at a rate T A  seconds per vertex. 
     When performing step  210 , the inputs to the distance functions associated with all the edges in the set E 2   vc  are the values needed at the next stage to evaluate the distance functions and to determine the next vertex. 
     FIG. 3 is a flowchart of an algorithm that reduces the amount of time it takes for a search-based decoding algorithm to proceed from one vertex to another in accordance with another embodiment of the present invention. The flowchart begins at step  300  and at step  310 , the inputs to the distance functions associated with the edges in the set E 2   vc  are computed. At step  320 , the distance functions associated with those edges (in the set E 2   vc ) are evaluated. In this embodiment, the only processing step that needs to be done in the determination of which edge to follow from the current vertex V c  is step  320 , where the next vertex is determined based on a previous evaluation of the distance functions associated with the edges in the set E 1   vc . In fact, E 1   vc  at stage k is a subset of E 2   vp  at stage (k−1) where V p  is the vertex from which the edge (V p , V c ) originates, followed by the algorithm in accessing the current vertex V c . The operations performed by the flowchart terminate at step  340 . 
     The pre-evaluation of the distance functions associated with the set E 2   vc  allows the algorithm to proceed at a rate T C  seconds per vertex assuming (T A +T B )&lt;T C  since steps  310  and  320  are performed in parallel with step  330  (if (T A +T B )&gt;T C  then the algorithm would proceed at (T A +T B ) seconds per vertex). 
     The principles of the present invention as described with reference to FIG.  2  and FIG. 3 may be applied to the Fano sequential decoding algorithm. The Fano algorithm is typically used to search a specific type of graph known as a trellis. The trellises are often used to represent error control codes or trellis codes that are used in digital communications systems. The Fano algorithm is used at the receiver to search for the minimum weight path through the trellis based on weightings that are obtained from a metric function that determines the weight on each edge as a function of received values from a communications channel and estimated received symbols. 
     FIG. 4 illustrates a portion of a trellis that may be searched by using the Fano algorithm in conjunction with the principles of the present invention. 
     When using the Fano algorithm, the distance metrics may be calculated as f({tilde over (x)}−{circumflex over (x)}), where {circumflex over (x)} is an estimate of the value from the channel and {tilde over (x)} is the possibly corrupted value received from the channel. The distance function f may be computationally simple. Let T f  be the time it takes to evaluate f. The decision as to which way to proceed through the trellis also takes a small amount of time, T d . However, the computation of the channel estimate {circumflex over (x)} takes a considerable amount of time, T {circumflex over (x)} . The Fano algorithm uses the distance metrics associated with each branch or edge of the trellis to determine the next vertex. In the trellis representation of a finite state machine (FSM), a vertex is representative of a state of the FSM at a specific moment. The current vertex is represented, in FIG. 4, by CSTATE, the previous vertex is represented by PSTATE and the set of next vertices by FSTATE 0 , FSTATE 1 , FSTATE 2  and FSTATE 3  which represent the possible states that the FSM can reach from CSTATE. The stage n represents a current trellis section and contains the edges or branches labeled with X fa , X fb , X fc , and X fd . Stage (n+1) represents one forward trellis section and stage (n−1) one reverse or backward trellis section. 
     In one embodiment, the flowchart described in FIG. 2 is used in conjunction with the Fano algorithm to search through a trellis. According to this embodiment, the values of {circumflex over (x)} for the current decision have already been calculated (from a previous computation of values in E 2   vp ) and are labeled as X fa , X fb , X fc , and X fd . While f is being evaluated on these values and the decision as to which edge to follow to the next vertex is being made, the possible values of {circumflex over (x)} for all edges in E v     c     2  are also being obtained or calculated. These values include X f0 , X f1 , X f2  and X f3  as illustrated in FIG.  4 . 
     In another embodiment using the method described in the flowchart of FIG. 3, the Fano algorithm may proceed at a faster rate by evaluating the distance function f associated with the edges in E v     c     2  while determining the next state from the current state, CSTATE. 
     The invention may be used to calculate the channel estimates {circumflex over (x)} in advance for all edges one step in the future. This means the algorithm may proceed at a rate of T f +T d  seconds for each vertex assuming that T {circumflex over (x)} &lt;(T f +T d ) (when using the method described in the flowchart of FIG.  2 ), or it may proceed at T d  seconds for each vertex assuming that T d &gt;(T f +T {circumflex over (x)} ) (when using the method described in the flowchart of FIG.  2 ). 
     FIG. 5 shows a block diagram of a search-based decoding algorithm using the Fano algorithm for sequential decoding. As illustrated in FIG. 5, the block diagram is composed of four modules: a Fano state machine  400 , a symbol estimator  410 , a branch metric calculator  420  and an uncoder  430 . The Fano algorithm is implemented with the fast search-based decoding scheme which pre-computes metrics on forward branches to reduce the latency inherent in such algorithm. 
     The symbol estimator  410  provides the branch metric calculator  420  with sets of estimates of received symbols that correspond to all possible symbols along the edges in E v     c     2 . These sets, represented herein as X b , X f0 , X f1 , X f2 , X f3 , contain the estimates of the channel outputs. The branch metric calculator  420 , which also has as input the received symbols X R   k , computes all of the distance metrics associated with the edges in E v     c     2 . 
     The branch metric calculator  420  pre-calculates sets of distance metrics (D b , D f0 , D f1, D   f2 , D f3 ) from the sets of estimates of received symbols and the received symbols X r  and then passes the metrics to the Fano state machine module (FSM)  400 . The Fano state machine  400  determines on which direction to proceed (forward or backward) based on comparisons between path metrics associated with the branches in the current trellis section and a threshold. The path metrics are a function of distance metrics for edges or branches in E 1   vc  previously calculated. The Fano state machine  400  also determines which branch the symbol estimator  410  should proceed with based on said distance metrics. The sets of metrics (D b , D f0 , D f1 , D f2 , D f3 ) will be used by the FSM  400  to determine which edge to follow from the next stage. The Fano state machine  400 , by instructing the symbol estimator  410  to proceed on a specific direction and branch, traces a path through the trellis wherein the symbols along the path have the best match with the symbols received from the transmission channel. This match is measured by a metric, which can be based on correlation or Euclidean distance. 
     The uncoder  430  retrieves estimates û n  of the information bits u. In one embodiment, the estimates of the information bits are computed from estimates {circumflex over (X)} n  of the trellis code symbols along the path which best matches the received symbols. 
     In one embodiment, the fast search-based decoding scheme can be selectively toggled on or off based on the latency of the decoding process. The Fano sequential decoding algorithm, under noisy conditions, can delay the decoding process by searching forward and backward to find the branch that has the best match with the received symbols. In this embodiment, the fast-search process is toggled on only when the decoding delay is above a threshold. The decoding delay can be measured from the number of received symbols stored in a received symbols buffer not yet processed by the decoder. A pointer corresponding to the number of symbols stored in the received symbols buffer is maintained and can be used to determine the number of symbols not yet processed. Other methods may also be used to determine the decoding delay. Use of the fast search-based decoding scheme allows reducing the latency by providing the Fano state machine  400  with distance metrics associated with the edges in E v     c     2  while the Fano state machine  400  is processing information related to the current state. 
     In this embodiment, if the Fano state machine  400  determines that the decoder should step back to search a different branch (on trellis section n−1), it may then, without further calculation by the symbol estimator  410  or branch metric calculator  420 , direct the symbol estimator to proceed to a specific branch determined from the pre-computed set of branch metrics. Similarly, for the forward direction, the Fano state machine  400  may instruct the symbol estimator  410  to proceed on the branch with the best match on trellis section (n+1). 
     The fast search-based decoding scheme provides an improvement over the prior art method for implementing the Fano sequential decoder in terms of latency and speed of operation by changing the sequential processing of information into a parallel processing to determine the next stage. 
     The present invention may be implemented in a number of different ways including software, hardware or a combination thereof. It can be implemented as embedded software in a Digital Signal Processor (DSP) or implemented as an Application Specific Integrated Circuit (ASIC). Other implementation methods well-known to those skilled in the art may also be used. 
     Although this invention has been illustrated by reference to specific embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made which clearly fall within the scope of the invention. The invention is intended to be protected broadly within the spirit and scope of the appended claims.