Abstract:
In one aspect the invention is a method for sequence estimating. The method includes generating a dynamic programming table, which represents a trellis. The trellis includes a set of time steps, which have a set of states. The trellis also includes a number of branches that connect the states. The method also includes expanding a search along the branches having a least accumulated error, inserting a pointer into a priority queue, where the pointer indicates an end of a partially completed path within the trellis, searching other branches when the accumulated error is no longer the least accumulated error, and continuing the search until the time step equals a current time.

Description:
[0001]    This invention relates to communications and in particular to sequence estimating.  
         BACKGROUND OF THE INVENTION  
         [0002]    Sequence estimation is used for a variety of purposes in communications systems, including the decoding of convolutional codes and the equalization of signals containing inter-symbol interference (ISI). In a typical communications system, a transmitter sends an information stream over a channel to a receiver. Typically, not all of the information stream sent by the transmitter is received by the receiver due to interference in the channel. In other situations, the information stream is distorted due to the information stream bouncing off or passing through additional mediums and received by the receiver after the primary information stream was received (phase distortion) or with less intensity (amplitude distortion).  
           [0003]    Convolutional encoding is used to build redundancy into a data stream to detect errors and to correct errors caused by interference in the channel or distortion in the information stream. Convolutional codes have the advantage of being reliable, efficient, and able to handle high data-rate communications through low bandwidth channels.  
           [0004]    One known method of estimating the sequence of convolutionally encoded symbols transmitted over a channel is through a Viterbi decoder. The Viterbi decoder keeps track of all the possible information streams, and outputs an information stream that is the most likely information stream sent by a sender. The Viterbi decoder uses a trellis. The trellis is a dynamic programming table whose entries are indexed by (t,s), where t is a time step and s is a state. The Viterbi decoder is limited in the time steps by a traceback length, L. At each time step, the Viterbi decoder outputs the (t-L)-th bit of the most likely information stream at time step, t, after at least L bits have been received.  
           [0005]    Another method of decoding a convolutional code uses a sequential decoder, such as a Fano decoder or a Stack decoder. The Fano and Stack decoders search a tree, instead of the trellis, for all the possible decoder state sequences over a fixed length sequence of information symbols. The tree has the same type of states and transitions as the trellis; however, the tree has 2 t  nodes, where t is time. Each node represents a unique state transition path from the root. The tree is not necessarily stored explicitly, but searched implicitly via some heuristic. An error metric is used and once a leaf of the tree is found that has a good error metric, the entire path leading to that leaf is outputted. The particular error metric and search strategy chosen make one sequential decoder different from another sequential decoder. The Fano and Stack decoders use an error metric that depends not only on the received symbols and the true bits of the transition, but also on the tree level of the node being expanded. In other words, the closer the node is to a leaf of the tree, the fewer errors are likely to be introduced.  
           [0006]    The transmission of data often requires that an equalizer be incorporated in the receiver to correct for the distortions produced by the transmission medium. These distortions can include effects such as amplitude variations and multi-path propagation. Sequence estimation is used in equalizers to correct for certain types of distortions, such as inter-symbol interference. Equalizers typically employ the same methods for sequence estimation (i.e. Viterbi, Stack and Fano) as are used for the decoding of convolutional codes.  
           [0007]    It is an important object of the invention to provide improved recovery of information from a received signal having both desired and undesired information.  
         BRIEF SUMMARY OF THE INVENTION  
         [0008]    In one aspect the invention is a method for sequence estimating. The method includes generating a dynamic programming table, which represents a trellis. The trellis includes a set of time steps, which have a set of states. The trellis also includes a number of branches that connect the states. The method also includes expanding a search along the branches having a least accumulated error, inserting a pointer into a priority queue, where the pointer indicates an end of a partially completed path within the trellis, searching other branches when the accumulated error is no longer the least accumulated error, and continuing the search until the time step equals a current time.  
           [0009]    The method may include one or more of the following features. The method includes outputting a bit on the least error path. The method may also include maintaining a list of active states for each time step, and clearing the list of active states at the beginning of every time step. In addition, the method includes transmitting an information sequence with a transmitter, determining an expected format of the information sequence received from the transmitter with a receiver, and building the dynamic programming table to conform to the expected format of the information sequence.  
           [0010]    The priority queue contains a set of accumulated error paths. The priority queue has a least accumulated error path at the top of the queue.  
           [0011]    The method also includes using a first matrix to record the accumulated error for a state at each time step. The method further includes using a second matrix to record a previous state on a best path for the state at a time step. The method includes using a third matrix for locating the states where the third matrix has entries having one of three different values. The third matrix is used to record values of empty, in queue, or expanded.  
           [0012]    In another aspect of the invention an apparatus for sequence estimating, includes a memory that stores executable instruction signals and a processor. The processor executes instruction signals to generate a dynamic programming table, which represents a trellis. The trellis includes a set of time steps, which have a set of states. The trellis also includes a plurality of branches connecting to the states. The processor also executes instructions to expand a search along the branches having a least accumulated error, to insert a pointer into a priority queue that indicate an end of a partially completed path within the trellis, to search other branches when the accumulated error is no longer the least accumulated error, and to expand the search until the time step equals a current time.  
           [0013]    The apparatus may include one or more of the following features. The processor includes instruction signals to output a bit on the least error path. The processor further includes instruction signals to maintain a list of active states for each time step, and to clear the list of active states at the beginning of every time step.  
           [0014]    The apparatus further includes instruction signals to transmit an information sequence with a transmitter, to determine an expected format of the information sequence received from the transmitter with a receiver, and to build the dynamic programming table to conform to the expected format of the information sequence.  
           [0015]    The priority queue contains a set of accumulated error paths. The priority queue has a least accumulated error path at the top of the queue.  
           [0016]    In addition, the apparatus includes instruction signals to use a first matrix to record the accumulated error for a state at each time step. The apparatus includes instruction signals to use a second matrix to record a previous state on a best path for the state at a time step. The apparatus includes instruction signals to use a third matrix for locating the states. The third matrix has entries having one of three different values. The third matrix records values of empty, in queue, or expanded.  
           [0017]    In a still further aspect, an article includes a machine-readable medium that stores executable instruction signals for sequence estimating. The instruction signals cause a machine to generate a dynamic programming table, which represents a trellis. The trellis includes a set of time steps where each time step has a set of states. The trellis also includes a number of branches connecting the states. The instruction signals also cause a machine to expand a search along the branches having a least accumulated error, insert a pointer into a priority queue so that the pointer indicates an end of a partially completed path within the trellis, search other branches when the accumulated error is no longer the least accumulated error, and expand the search until the time step equals a current time.  
           [0018]    The article may include one or more of the following features. The article further includes instruction signals causing the machine to output a bit on the least error path. The instruction signals causing the machine to maintain a list of active states for each time step, and to clear the list of active states at the beginning of every time step.  
           [0019]    In addition, the instruction signals cause the machine to transmit an information sequence with a transmitter, to determine an expected format of the information sequence received from the transmitter with a receiver, and to build the dynamic programming table to conform to the expected format of the information sequence.  
           [0020]    The priority queue contains a set of accumulated error paths. The priority queue has a least accumulated error path at the top of the queue.  
           [0021]    The instruction signals further include causing the machine to use a first matrix to record the accumulated error for a state at each time step. In addition, instruction signals cause a machine to use a second matrix to record a previous state on a best path for the state at a time step. The instruction signals cause the machine to use a third matrix for locating the states, where the third matrix has entries having one of three different values. The third matrix has values of empty, in queue, or expanded.  
           [0022]    The invention searches only those states within the trellis that have the highest probability of having the least error path. Thus, the invention saves in processing time but still ensures a high level of accuracy. Other features, objects and advantages will become apparent from the following detailed description when read in connection with the accompanying drawing in which:  
       
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING  
       [0023]    [0023]FIG. 1 is a state diagram of a trellis;  
         [0024]    [0024]FIG. 2 is a block diagram of a convolutional encoder that generates the trellis in FIG. 1;  
         [0025]    [0025]FIG. 3 is a block diagram of the encoder of FIG. 2 depicting the encoder at state 01;  
         [0026]    [0026]FIG. 4 is a state diagram of a trellis showing a path through the trellis for an encoded sequence;  
         [0027]    [0027]FIG. 5 is a state diagram of a trellis depicting an accumulated error in brackets;  
         [0028]    [0028]FIG. 6 is a flowchart for decoding a convolutional code; and  
         [0029]    [0029]FIG. 7 is a block diagram of a computer system on which the process of FIG. 6 may be implemented. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0030]    A heap estimator decodes and equalizes an information stream that may include undesired signals to provide an estimate of the transmitted information. In this embodiment, the process for equalizing the information stream and decoding the information stream are similar except in a heap equalization process an intersymbol interference of a channel is accounted for in determining an error distance wherein in a heap decoding process the intersymbol interference of the channel is not accounted for. Therefore, in this description, only the heap decoding process is described in detail but the description of the heap decoding process applies to the heap equalization process.  
         [0031]    Referring to FIG. 1, the heap decoding process decodes a convolutional code by combining the efficiency of sequential decoding with the quality of Viterbi decoding. The heap decoding process uses a trellis  10  with branches  16   a  and  16   b  to determine a least error path similar to a Viterbi decoding scheme. However, unlike the Viterbi decoding scheme, the heap decoding process does not search every branch  16   a  and  16   b  along trellis  10 ; but rather, the heap decoding process searches those branches that will most likely yield the least error path. As will be explained below, the heap decoding process uses a priority queue similar to a Stack decoder and a Fano decoder to keep a record of the least accumulated error path and a time list to keep track of previously measured branches  16   a  and  16   b.    
         [0032]    Referring to FIG. 2, before a receiver decodes a convolutional code transmitted by a sender, the receiver has an expectation of an encoded convolutional code format. An encoder  20  used to generate trellis  10  has delay elements  22   a  and  22   b  and adders  23   a  and  23   b . When encoder  20  receives an input bit  24 , encoder  20  transmits two output bits  26   a  and  26   b . Encoder  20  has a rate equal to the number of input bits  24  received divided by output bits  22   a  and  22   b  transmitted. Therefore, the rate of encoder  20  is ½. The constraint length, c, of an encoder is equal to one more than the number of delay elements so that the constraint length of encoder  20  is 3.  
         [0033]    Referring to FIGS. 1 &amp; 2, trellis  10  includes states 12 arranged in time steps (e.g., first time step  14   a  and second time step  14   b ). State 12 of encoder  20  at a time step, t, is described by the contents of the delay elements. Each state can transition to one of two other states in a subsequent time step depending on an information bit. Each state 12 is connected to these other states by branches  16   a  and  16   b . One branch  16   a  corresponds to a ‘1’ information bit (represented by dashed lines in trellis  10 ) and another branch  16   b  corresponds to a ‘0’ information bit (represented by solid line in trellis  10 ).  
         [0034]    Referring to FIGS. 2 and 3, encoder  20  is used to complete trellis  10 . For example, encoder  20  at state 01 is depicted where delay element  22   a  is ‘0’ and delay element  22   b  is ‘1.’ When a ‘1’ information bit  24  is received, encoder  20  outputs a ‘11’ as output bits  26   a  and  26   b . When a ‘0’ information bit is received, encoder  20  outputs a ‘00’ as output bit  26   a  and  26   b . Likewise, encoder  20  is used for the remaining states (00, 10, and 11) to complete trellis  10 .  
         [0035]    Referring to FIG. 4, trellis  10  can then be used to encode a sequence. For example, encoder  20  encodes an input sequence of 0 1 0 1 1 . . . to be 00 11 01 00 10 . . . A path  38  through trellis  10  corresponds to the encoded output sequence, and path  38  is depicted in bold.  
         [0036]    Referring to FIG. 5, once trellis  10  is used to encode a sequence, trellis  10  can be used by the receiver to decode the sequence. However, errors may be introduced into the sequence. How a decoder decodes the sequence separates the decoders from one another. Trellis  10  is used to decode a received word sequence 00 10 01 00 where the second bit of the second word is an error bit since the proper sequence is 00 11 01 00. A Hamming distance is used to measure the accumulated error at each time step  14   a - d  and is depicted in bracketed numbers  42  above each state. The Hamming distance of a path is the measure of unlike bits between the received word sequence and the encoding corresponding to the path. For example, the Hamming distance of 11 00 and 11 11 is two because the last two bits do not match.  
         [0037]    The heap decoder expands only along those branches  16   a  and  16   b  (FIG. 1) that have the least accumulated error. Suppose the best accumulated error at time step, t, among all states was 10 at some state s, and all other states had an accumulated error of at least 12. Now, consider some state, S′, which is a transition state from state, s, and suppose that the error metric along the transition with respect to the received encoded bits is 1. Thus, when the heap decoder gets to state s′ at processing time step, t+1, the accumulated error will be 11. This is less than all the accumulated errors of the states previous to time step, t. Thus, without looking at the other states at time t+1, state s′ will be the state with the smallest accumulated error for t+1.  
         [0038]    For example, referring back to FIG. 5, a path starting at state 10 of second time step  14   b  is not expanded by the heap decoder because state 00 of second time step  14   b  has an accumulated error of 0 whereas state 10 of second time step  14   b  has an accumulated error of 2. In another example, the path starting at state 11 of fourth time step  14   d  is not expanded by the heap decoder because state 11 of fourth time step  14   d  has an accumulated error of 2 as opposed to state 01 of the fourth step  14   d , which has an accumulated error of 1.  
         [0039]    Referring to FIG. 6, a process  50  decodes a received signal using the heap decoder. Process  50  includes a subprocess  51 , which initializes the heap decoder. A subprocess  52  processes a received word, the encoded word that may have been corrupted by the channel, and produces an information bit. Like sequential decoding, process  50  extends a hypothesized best path until the accumulated error becomes worse than other possible paths. However, when the accumulated error of what was thought was the best path gets too high, instead of backtracking like in the sequential decoding scheme, process  50  fills in those parts of trellis  10  not previously observed.  
         [0040]    Subprocess  51  creates and initializes ( 53 ) data structures in order to be used in subprocess  52 . These data structures include a dynamic programming table with three matrices, a priority queue, and a time list. Subprocess  51  generates the dynamic programming table that corresponds to trellis  10 . Thus, the dynamic programming table cannot be created without first knowing the expected format of the encoded sequence. The dynamic programming table matrices are indexed by (s,t) where s is the state and t is the time step. Unlike the dynamic programming table used in the Viterbi decoder, the dynamic programming table will only be filled-in by process  50  for those states and time steps that have a high likelihood of being the least error path. Like in Viterbi decoders, trellis  10  is limited in the time steps by the traceback length, L. At each time step, an output of the (t-L)-th bit of the most likely input stream after at least L bits is observed.  
         [0041]    In order for process  50  to search trellis  10  efficiently, a priority queue Q is maintained whose elements have the form (&lt;s,t&gt;,accum) where accum represents the accumulated error at time step t for state s. Each element is a pointer, which refers to the end of a partially completed path within trellis  10 . Priority queue, Q, supports the following operations:  
         [0042]    1. PQ-Insert(Q,(&lt;s,t&gt;, accum)) inserts an element into the queue.  
         [0043]    2. PQ-Extract-Min(Q) removes the top element of the queue with the smallest error and returns it.  
         [0044]    3. PQ-Min-Element (Q) returns the top element of the queue, but does not delete it.  
         [0045]    4. PQ-Delete(Q,&lt;s,t&gt;) deletes an arbitrary element from the queue.  
         [0046]    Process  50  maintains three matrices corresponding to trellis  10 . A first matrix, Error[s,t], provides the accumulated error for state s at a time step, t. The second matrix, Prev[s,t], provides the previous state of the best path for state s at time step t. Prev[s,t] is used to perform a traceback once the search is completed. Process  50  uses the Prev[s,t] matrix to trace back through states 12 for each time step  14  along the least accumulated path to produce an output information bit.  
         [0047]    The third matrix, Loc[s,t] provides the location of each state. Each entry in Loc[s,t] has one of three values: “Empty,” “In Queue,” or “Expanded.” If Loc[s,t]=“Empty” the values in Error[s,t] and Prev[s,t] are meaningless because these values have never been filled-in or these values represent values computed more than L time steps before T. The entries in matrix Loc[s,t] is initially set to “Empty.” If Loc[s,t]=“in Queue,” or “Expanded,” the values in Error[s,t] and Prev[s,t] are meaningful for some time less than L time steps in the past. If Loc[s,t]=“In Queue,” then &lt;s,t&gt; is present in priority queue, Q, and represents the end of a partially completed path through trellis. If Loc[s,t]=“Expanded,” then &lt;s,t&gt; had the lowest accumulated error among all partially completed paths at some point during process  50  and was expanded.  
         [0048]    Process  50  uses a time list called Time-List(t) which contains all states s such that Loc[s,t]=“In Queue” or “Expanded.” Time-List(t) is used to “clean-up” a time step so that process  50  can increment one time step in the search for the least error path. A subroutine, Time-List-Insert(t,s), inserts states, s, into Time-List(t).  
         [0049]    In general, subprocess  52  processes a received word, x, received at some time T*. Subprocess  52  outputs the information bit at time step T*-L of the information sequence that is most likely at time step T*.  
         [0050]    Specifically, subprocess  52  receives ( 54 ) a word, x, from the channel. When looking back L time steps, the heap decoder maintains a current time modulo L. The current time is stored in a variable T. Subprocess  52  increases ( 55 ) T by one (mod L). The time steps, t, will always be in the range {0, . . . , L-1}. In absolute time, t always represents a time between T*-L and T*, and T represents time T*. So for example, if L=10, T=6, as process  50  is searching data at t=9, t represents the time 7 steps in the past (6-9≡7 mod 10).  
         [0051]    Subprocess  52  clears ( 56 ) Time-List (t). Subprocess  52  sets ( 57 ) (s,t) to be the time step and the state of the end of the best path.  
         [0052]    Subprocess  52  extends a path ( 58 ) along a branch not previously observed. Subprocess  52  operates on the state s and time step t with the lowest accumulated metric among all partially completed paths. Subprocess  52  also looks at all possible states reachable from state, s, and computes the new error metrics.  
         [0053]    Subprocess  52  continues the search along the hypothesized best path until the time step of the end of the best path equals the current time. Subprocess  52  determines whether the end of the best path equals the current time ( 59 ). During this process, the particular path that has the least error may change. If the end of the best path does not have time equal to the current time, subprocess  52  sets (s,t) to be the end of the best path ( 57 ). If the end of the best path is equal to the current time, subprocess  52  outputs ( 60 ) the (T−L)-th bit along the least accumulated path by tracing back through trellis  10  using Prev[s,t].  
         [0054]    A pseudocode that implements process  50  is listed below called Process-Word(x). Included in the Process-Word(x) pseudocode is the subroutine, Expand(s,t,x), which expands the search to unobserved branches one step along the hypothesized best path. Also included in the pseudocode is Distance(x,x′), a distance function, which returns the distance between the received word x, and a true encode word x′. Altering the way the distance function is computed adapts process  50  for the specific channel model. For the binary symmetric channel, the Hamming distance is used. Encoded-Word(s,s′) is the word output by the encoder when transitioning from state s to state s′. If knowledge about intersymbol interference in the channel is known, the distance function and Encoded-Word(s,s′) can be adapted to give process  50  equalization capabilities. Transition-Bit(s,s′) is an information bit that causes the encoder to transition from state s to state s′. For example, referring back to FIG. 1, Transition-Bit(00,00)=0 corresponding to branch  16   b , and Transition-Bit(00,10)=1 corresponding to branch  16   a.    
         [0055]    In the pseudocode, time begins at T=0. 0 c−1  represents an all-zeros state. The priority queue, Q, is initialized to contain only (0,0 c−1 ), which has a value of 0. The matrix Error[s,t] is initialized with Error[0,0 c−1 ]=0, and all other entries are irrelevant. The matrix Loc[s,t] is initialized with all entries as “Empty,” except Loc[0,0 c−1 ], which is set to “In Queue.” The code is considered in a steady state if at least L encoded words have been processed. Until steady state is achieved, no output is produced by Process-Word(x). All Time-List(t) entries are empty except Time-List(t) contains {0 c−1 }. In the pseudocode below, indentations represent control structures. For example, lines 4 through 6 in the Process-Word(x) code below represent the contents of a while loop. An arrow represents the assignment operator. For example, line 13 of the Expand subroutine changes the value of Loc[s,t] to “Expanded.” 
         [0056]    Process-Word(x)  
         [0057]    1 T←T+1(mod L)  
         [0058]    2 Clear-Time(T)  
         [0059]    3 while(true)  
         [0060]    4 (s,t)←PQ-Extract-Min(Q)  
         [0061]    5 Expand(s,t,x)  
         [0062]    6 (s,t) PQ-Min-Element(Q)  
         [0063]    7 if (t=T) break  
         [0064]    8 if(steady state) return Traceback (PQ-min-Element(Q))  
         [0065]    Expand(s,t,x)  
         [0066]    1 For all states s′ reachable from s.  
         [0067]    2 accum←Distance(x,Encoded-Word(s,s′))+Error(s,t)  
         [0068]    3 if Loc[s′,t+1]=“Empty” 
         [0069]    4 PQ-Insert(Q,((s′t+1, accum))  
         [0070]    5 Time-List-Insert(t+1,s′)  
         [0071]    6 Prev[s′,t+1]←s  
         [0072]    7 Loc[s′,t+1]=“In Queue” 
         [0073]    8 Error[s′,t+1]←accum  
         [0074]    9 else if Loc[s′,t+1]=“In Queue” 
         [0075]    10 if accum&lt;Error[s′,t+1] 
         [0076]    11 Decrease-Key((s′,t+1),accum)  
         [0077]    12 Prev[s′,t+1]←s  
         [0078]    13 Loc[s,t]←“Expanded” 
         [0079]    14 return  
         [0080]    Clear-Time(t)  
         [0081]    1 For all s as an element of Time-List(t)  
         [0082]    2 if Loc[s,t]=“In Queue” 
         [0083]    3 PQ-Delete(Q, (s,t))  
         [0084]    4 Loc[s′,t+1]←“Empty” 
         [0085]    5 return  
         [0086]    Traceback(s,t)  
         [0087]    1 while(t≠T−L+1 mod L)  
         [0088]    2 s′←s  
         [0089]    3 s←Prev[s,t] 
         [0090]    4 t←t-1  
         [0091]    5 return Transition-Bit(s,s′)  
         [0092]    [0092]FIG. 7 shows a decoding system  70  that includes a computer  71 , a receiver  72 , and a transmitter  73  for decoding convolutional codes using process  50 . Computer  71  includes a processor  74  for processing convolutional codes sent from transmitter  73  and received by receiver  72 , a memory  79 , and a storage medium  81  (e.g., hard disk). Storage medium  81  stores operating system  83 , data  84 , and computer instructions  82  which are executed by processor  74  out of memory  79  to perform process  50 . In one embodiment, computer instructions include executable instruction signals.  
         [0093]    Process  50  is not limited to use with the hardware and software of FIG. 7; process  50  may find applicability in any computing or processing environment and with any type of machine that is capable of running a computer program. Process  50  may be implemented in hardware, software, or a combination of the two. Process  50  may be implemented in computer programs executed on programmable computers/machines that each include a processor, a storage medium/article of manufacture readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device to perform process  50  and to generate output information.  
         [0094]    Each such program may be implemented in a high level procedural or objected-oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language. The language may be a compiled or an interpreted language. Each computer program may be stored on a storage medium (article) or device (e.g., CD-ROM, hard disk, or magnetic diskette) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform process  50 . Process  50  may also be implemented as a machine-readable storage medium, configured with a computer program, where upon execution, instructions in the computer program cause the computer to operate in accordance with process  50 .  
         [0095]    The estimator uses process  50  for equalization of the information stream. However, the error distance in an equalization process accounts for the known intersymbol interference of the channel.  
         [0096]    The invention is not limited to the specific embodiments described herein. The invention is not limited to the specific processing order of FIG. 6. Rather, the blocks of FIG. 6 may be re-ordered, as necessary, to achieve the results set forth above.  
         [0097]    Other embodiments not described here are also within the scope of the following claims.