Abstract:
Digital circuits and methods for designing digital circuits are presented. More particularly, the present invention relates to error correction circuits and methods in communications and other systems. In the present invention, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high through-put rate Viterbi decoder circuits. The main idea of the present invention involves combining K-trellis steps as a pipeline structure and then combining the resulting look-ahead branch metrics as a tree structure in a layered manner to decrease the ACS precomputation latency of look-ahead Viterbi decoder circuits. The proposed method guarantees parallel paths between any two trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. The main advantage of this invention is that it has the least latency among all known look-ahead Viterbi decoder circuits for a given level of parallelism.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application is a continuation-in-part of U.S. Provisional Patent Application No. 60/496,307, filed on Aug. 19, 2003, which is incorporated herein by reference in its entirety. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates to digital communications. More particularly, the present invention relates to error correction circuits and methods in digital communication systems.  
       BACKGROUND OF THE INVENTION  
       [0003]     A convolutional code has been widely used in many communication systems as a forward error correction (FEC) method. The Viterbi decoding algorithm is optimum for decoding of the received data, which is transmitted after convolutional encoding.  
         [0004]     The decoding speed of the Viterbi decoding algorithm is limited by the iteration bound because the add-compare-select (ACS) recursion in the Viterbi decoding algorithm contains feedback loops. A look-ahead technique, which combines several trellis steps into one trellis step in time sequence, has been used for breaking the iteration bound of the Viterbi decoding algorithm. In the look-ahead technique, the combined branch metrics can be computed outside of the ACS recursion (referred as ACS precomputation). This allows the ACS loop to be pipelined or computed in parallel. Thereby, the decoding throughput rate can be increased. This is an advantage of the look-ahead technique. The look-ahead step (M) for a given throughput rate is obtained as the desired throughput rate divided by the ACS recursion clock rate since the overall decoding speed is limited by the allowed maximum frequency of the ACS recursion clock. Therefore, large number of look-ahead steps or high parallelism factor is needed to implement high-throughput rate Viterbi decoding.  
         [0005]     In this invention, the ACS computation without the addition of the previous state metrics (or path metrics or accumulated branch metrics) is referred as the ACS precomputation to distinguish it from the ACS recursion, which adds the previous state metrics to the look-ahead branch metrics used for state update operation inside the feedback loop.  
         [0006]     The main drawback of the traditional M-step look-ahead technique is that it leads to long latency for look-ahead ACS precomputation, especially when very large number of look-ahead steps is required. When the ACS precomputation unit is implemented as a pipeline structure, the ACS precomputation latency of the traditional M-step look-ahead method increases linearly with respect to the look-ahead step.  
         [0007]     In this invention, an alternate approach is considered where the method of combining trellis steps is changed such that the inherent decoding latency can be. It combines K-trellis (where K is the encoder constraint length) steps into one trellis-step and then combines resulting sub-trellises in a layered manner (refereed as K-nested layered look-ahead, LLA). In this approach, the ACS precomputation latency can be significantly decased for high order look-ahead cases as long as the level of parallelism, M, is a multiple of the encoder constraint length, K.  
         [0008]     The practical use of this invention is extremely important for implementation of high speed, i.e., 5 or 10 Gb/s, serializer-deserializer (SERDES), where the latency constraint is critical. The SERDES can be used in 10 Gb/s fiber channel synchronous optical network (SONET) or 10 Gb/s Ethernet local area network (LAN), etc. The low-latency Viterbi detector based on this invention may also be used in high density optical or magnetic storage y such as digital video disk (DVD) and hard disk drive (HDD) systems.  
       BRIEF SUMMARY OF THE INVENTION  
       [0009]     For a binary convolutional code, parallel paths exist when the number of incoming paths into a trellis state (2 M ) is larger than the number of trellis states (2 K−1 ): 2 M &gt;2 K−1           M≧K. Each trellis transition in an M-step look-ahead trellis has 2 M−K+1  parallel path. As a result, combining K-trellis steps guarantees two parallel paths between any two-trellis states. Parallel paths are the paths that have the same strung trellis state and same ending trellis state. The existence of parallel paths guarantees that it is possible to use look-ahead ACS precomputation. However, if there are no parallel paths in the look-ahead trellis, only the look-ahead additions of the branch metrics (λ), which are distances between the received data and codewords, are allowed.  
         [0010]     The main idea of this invention involves combining K-trellis steps as a pipeline structure and then combining the resulting look-ahead branch metrics as a tree structure in a layered manner to decrease the ACS precomputation latency. This leads to a regular and simple high throughput rate Viterbi decoder architecture with logarithmic increase in latency, as opposed to linear increase in traditional look-ahead, with respect to the look-ahead factor. A restriction of this method is that the look-ahead step M should be a multiple of the encoder constraint length K.  
         [0011]     In this invention, each layer- 1  processor combines K-trellis steps into one trellis step (K-nesting). The higher layer processors combine two sub-layer trellises, and each layer processor executes the ACS computations in a distributed manner referred as layered look-ahead. The ACS recursion is executed at the top layer. For each trellis state, the layer- 1  processor selects one path from two parallel paths and leads to a fully connected trellis with no parallel paths. When two fully connected trellises with no parallel paths are combined into one, 2 K−1  parallel paths are generated between any two-trellis states. Therefore, the layer- 2  and higher layer processors select one path from 2 K−1  parallel paths instead of 2 M−K+1  parallel paths. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES  
       [0012]     The present invention is described with reference to the accompanying figures in the figures, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit or digits of a reference number identify the figure in which the reference number first appears. The accompanying figures, which are incorporated herein and form part of the specification, illustrate the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the relevant art to make and use the invention.  
         [0013]      FIG. 1  illustrates a traditional M-step look-ahead Viterbi decoder circuit.  
         [0014]      FIG. 2  illustrates a proposed M-step look-ahead Viterbi decoder circuit.  
         [0015]      FIG. 3  illustrates trellis diagrams of the proposed M-step K-nested layered look-ahead method for the encoder constraint length, K, equal to 3 and the look-ahead step, M, equal to 12.  
         [0016]      FIG. 4  illustrates an example of the proposed M-step K-nested LLA Viterbi decoder circuit for M=12 and K=3.  
         [0017]      FIG. 5  illustrates the proposed layer- 1  processor (P 1 ) circuit of  FIG. 4 .  
         [0018]      FIG. 6  illustrates the proposed layer- 2  processor (P 2 ) circuit of  FIG. 4 .  
         [0019]      FIG. 7  illustrates the proposed layer- 3  processor (P 2 ) circuit of  FIG. 4 . For 2≦k≦log 2 (M/K)+1, each layer-k processor uses same type of processor, P 2 .  
         [0020]      FIG. 8  illustrates the proposed ACS recursion processor (P 3 ) circuit of  FIG. 4 .  
         [0021]      FIG. 9  illustrates the proposed survivor path management circuit for layer- 2  (M 2 ) of  FIG. 4 .  
         [0022]      FIG. 10  illustrates the proposed survivor path management circuit for layer- 3  (M 3 ) of  FIG. 4 .  
         [0023]      FIG. 11  illustrates the proposed survivor path management circuit for ACS recursion part (MA) of  FIG. 4 . 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0024]     In the look-ahead technique, the combined branch metrics can be computed outside of the ACS recursion. This allows the ACS loop to be pipelined or computed in parallel. Thereby, the decoding throughput rate can be increased. This is an advantage of the look-ahead technique, which has been explored for Viterbi decoding algorithm and the dynamic programming problems.  FIG. 1  illustrates that a circuit  100  consists of ACS precomputation part (circuit  110 ) and ACS recursion part (circuit  120 ) for traditional M-step look-ahead Viterbi decoding circuit.  
         [0025]     The ACS precomputation part (circuit  110 ) consists of 2-input adders (circuit  112 ), radix- 2  ACS circuits ( 114 ), and pipelining latches (circuit  116 ). Each radix- 2  ACS circuit consists of two 2-input adders and a radix- 2  compare-select (CS) circuit. Circuit  110  uses M-parallel incoming branch metrics (signal  101 ) for its ACS precomputation. For the first (K- 1 )-steps branch metrics inputs, compare-select operations are not necessary. Therefore, 2-input adders (circuit  112 ) can be used for those inputs. From the K-th branch metrics inputs, radix- 2  ACS circuits ( 114 ) are used for add-compare-select operations. From the ACS precomputation part (circuit  110 ), M-step look-ahead branch metrics (signal  103 ) are obtained. The M-step look-ahead branch metrics (signal  103 ) are used as inputs of ACS recursion part (circuit  120 ).  
         [0026]     The ACS recursion part (circuit  120 ) consists of radix-2 K−1  ACS circuits ( 122 ) and pipelining latches (circuit  124 ). Each radix-2 K−1  ACS circuit ( 122 ) consists of 2-input adders and a radix-2 k−1  ACS circuit. It adds M-step look-ahead branch metrics (signal  103 ) and state metrics (signal  107 ) of the previous step and performs compare-select operation to select a maximum likelihood path. The state metrics (signal  105 ) of the selected path is used for computation of the next ACS recursion.  
         [0027]      FIG. 2  illustrates the proposed M-step K-nested look-ahead Viterbi decoder circuit It also consists of ACS precomputation part (circuits  210 ,  220 , and  230 ) and ACS recursion part (circuits  240  and  250 ). However, the present invention differs from the prior work, that is, it combines K-trellis steps as a pipeline structure and then combines the resulting look-ahead branch metrics as a tree structure in a layered manner. The proposed mK-step K-nested layered look-ahead (LLA) method, where m is a positive power-of-two integer equal to M/K, consists of (log 2  m+1) ACS precomputation layers and one ACS recursion layer. This invention requires (2m−1) ACS precomputation units and one ACS recursion it as shown in  FIG. 2  (circuit  200 ) and  FIG. 3  (diagram  300 ).  
         [0028]     ACS computation units (circuits  210 ,  220 , and  230 ) contain P 1  (circuit  210 ) and P 2  (circuits  220  and  230 ) for ACS precomputation and P 3  (circuit  240 ) for ACS recursion with pipelining latches (circuits  216 ,  224 ,  234 , and  250 ). The required numbers of processors for ACS computation are as follows: m for P 1  (circuit  210 ), (m−1) for P 2  (circuits  220  and  230 ), and 1 for P 3  (circuit  240 ).  
         [0029]     The ACS computations are executed in a layered manner by circuits ( 210 ,  220 ,  230 ,  240 , and  250 ) as follows.  
         [0030]     Layer- 1  processor, P 1  (circuit  210 ): Layer- 1  ACS precomputation needs m-P 1  processors. Each P 1  (circuit  210 ) executes K-step look-ahead ACS precomputation with K-parallel incoming branch metrics (signal  211 ) as follows: 
 
 p   1   h,j ( n+K ( i+ 1)−1)=min{ p   h,j ( n+K ( i+ 1)−1),  q   h,j ( n+K ( i+ 1)−1)}.   EQ. 1 
 
 Here subscripts h and j stand for trellis states: 0≦h,j≦2 K−1 −1. The parameter i is a sequence index starting from 0. Signals p h,j (n+K(i+1)−1) and q h,j (n+K(i+1)−1) in EQ. 1 are the K-step look-ahead branch metrics of the two parallel paths between starting trellis state and ending trellis state-j, which are the sums of the K-parallel incoming branch metrics (signal  211 ): λ h,0 (n+Ki)+ . . . +λ c,l (n+K(i+1)−2)+λ l,j (n+K(i+1)−1). The signal  215 , p 1   h,j (n+K(i+1)−1), is the selected K-step look-ahead branch metrics from the two parallel paths (signals  213   a  and  213   b ). 
 
         [0032]     The parallel-path-select (PPS) signals for the trellis state-j in layer- 1 , which contain survivor path information of each selected parallel path between starting trellis state-h and ending trellis state-j, are obtained as follows:  
                 PPS     h   ,   j   ,   i     1     ⁡     [   0   ]       =     {         0           when   ⁢           ⁢       p     h   ,   j       ⁡     (     n   +     K   ⁡     (     i   +   1     )       -   1     )       ⁢           ⁢   is   ⁢           ⁢   selected     ,             1         when   ⁢           ⁢       q     h   ,   j       ⁡     (     n   +     K   ⁡     (     i   +   1     )       -   1     )       ⁢           ⁢   is   ⁢           ⁢     selected   .                       EQ   .           ⁢   2             
 
 The superscript of PPS represents the ACS precomputation layer. In layer- 1 , each trellis state has 2 K−1  one-bit PPS signals. These are referred as PPS 1   h,j,i [0]. 
 
         [0034]     Layer-k Processor, P 2  (circuits  220  and  230 ) for 2≦k≦log 2  m+1: For layer-k ACS precomputation, m/2 k−2 -P 2  processors are needed Each P 2  executes 2 k−1 ·K-step look-ahead ACS precomputation using two 2 k−2 ·K-step look-ahead branch metrics as follows:  
                 p     h   ,   j     k     (     n   +       2     k   -   1       ⁢     K   ⁡     (     i   +   1     )         -   1     )     =     min   ⁢     {                     p     h   ,   0       k   -   1       (     n   +       2     k   -   2       ⁢     K   ⁡     (     i   +   1     )         -   1     )     +                   p     0   ,   j       k   -   1       (     n   +       2     k   -   1       ⁢     K   ⁡     (     i   +   1     )         -   1     )     ,                               p     h   ,   1       k   -   1       (     n   +       2     k   -   2       ⁢     K   ⁡     (     i   +   1     )         -   1     )     +                   p     1   ,   j       k   -   1       (     n   +       2     k   -   1       ⁢     K   ⁡     (     i   +   1     )         -   1     )     ,                     ⋯   ⁢           ,                         p     h   ,     N   -   1         k   -   1       (     n   +       2     k   -   2       ⁢     K   ⁡     (     i   +   1     )         -   1     )     +                 p       N   -   1     ,   j       k   -   1       (     n   +       2     k   -   1       ⁢     K   ⁡     (     i   +   1     )         -   1     )                 }               EQ   .           ⁢   3             
 
 where the subscript, N repesents the number of trellis states: N=2 K−1 . 
 
         [0036]     In layer-k each trellis state has 2 K−1 -PPS signals, which consist of (K−1)bits because there are 2 K−1  parallel paths between starting trellis state-h and ending trellis state-j with  2 K- leading trellis states. These are referred as PPS k   h,j,i [K−2:0].  
         [0037]     ACS recursion processor (circuits  240  and  250 ): The ACS recursion processor consists of a P 3  (circuit  240 ) and pipelining latches (circuit  250 ). The P 3  and the pipelining latch execute the ACS recursion using 2 m−1 ·K-step look-ahead branch metrics and the previous state metrics, γ j (n+mKi), as follows:  
                 γ   j     (     n   +     m   ⁢           ⁢     K   ⁡     (     i   +   1     )           )     =     min   ⁢     {                 γ   0     ⁡     (     n   +   mKi     )       +       p     0   ,   j     l     (     n   +     mK   ⁡     (     i   +   1     )       -   1     )       ,                     γ   1     ⁡     (     n   +   mKi     )       +       p     1   ,   j     l     (     n   +     mK   ⁡     (     i   +   1     )       -   1     )       ,               ⋯   ⁢           ,                   γ     N   -   1       ⁡     (     n   +   mKi     )       +       p       N   -   1     ,   j     l     (     n   +     mK   ⁡     (     i   +   1     )       -   1     )             }               EQ   .           ⁢   4             
 
 where signal p l   h,j (n+mK(i+1)−1) is the mK-step look-ahead branch metric that starts from trellis state and ends a trellis state-j and l=log 2  m+1. The parameter γ j (n+mK(i+1)) is the new state metrics of the trellis state-j. 
 
         [0039]     In P 3  (circuit  240 ), each trellis state needs 2 K−1  path-select (PS) signals, which consist of (K−1)-bits to distinguish 2 K−1  incoming paths to a trellis state-j from 2 K−1  leading trellis states: PS j,i [K−2:0].  
         [0040]     In  FIG. 3 , diagram  310  illustrates trellis diagrams for the encoder constraint length K=3 and the look-ahead step M=12. Each layer- 1  processor combines K-trellis steps (signal  301   a +signal  301   b +signal  301   c  and signal  303   a +signal  303   b +signal  303   c ) and selects a trellis path (signal  321 ) from two parallel trellis paths (signal  301   a +signal  301   b +signal  301   c  and signal  303   a +signal  303   b +signal  303   c ).  
         [0041]     The diagram  320  is the resulting trellis diagram of the layer- 1  processor. Each layer- 2  processor combines resulting signals (signal  321 +signal  323  and signal  325 +signal  327 ) of layer- 1  processors and selects a trellis path (signal  331 ) from two parallel trellis paths (signal  321 +signal  323  and signal  325 +signal  327 ).  
         [0042]     The diagram  330  is the resulting trellis diagram of the layer- 2  processor. Each layer- 3  processor combines resulting signals (signal  331 +signal  333  and signal  335 +signal  337 ) of layer- 2  processors and selects a trellis path (signal  341 ) from two parallel trellis paths (signal  331 +signal  333  and signal  335 +signal  337 ).  
         [0043]     The diagram  340  is the resulting trellis diagram of the layer- 3  processor. Each ACS recursion processor adds signals (signal  341   a +signal  343   a,  signal  341   b +signal  343 b, signal  341   c +signal  34  and signal  341   d +signal  343   d ) and selects a trellis path from four trellis paths (signal  341   a +signal  343   a,  signal  341   b +signal  343   b,  signal  341   c +signal  343   c,  and signal  341   d +signal  343   d ).  
         [0044]     In  FIG. 3 , the numbers ( 1  through  12 ) represent the decoded data sequence. PPS 1   h,j,0 [0] becomes the first decoded data since the PS j,0 [0:1] represent the encoder initial states. The PS j,l [0:1] become the 13 th  and the 14 th  decoded data, etc. Consequently, the survivor path information for mK-step look-ahead method consists of mK-bits per each trellis state: mK−(K−1) bits for PPS and (K−1) bits for PS. With this mK-parallel survivor path information, the effective decoding speed of the Viterbi decoder can be increased by a factor of mK.  
         [0045]     The mK-step K-nested LLA Viterbi decoder consists of serial-to-parallel converter (SPC), branch metrics calculator (BMC), ACS computation units, and survivor path management (M#) units. The serially received data sequence is converted into parallel data sequences by the SPC. The BMC computes Euclidean (soft decision) or Haag (hard decision) distances of the received data with respect to the codeword. Architectures of SPC and BMC are for the traditional M-step look-ahead method and the proposed method are same and not considered in this invention.  
         [0046]      FIG. 6  (circuit  400 ) illustrates an example of this invention for 12-step K-nested look-ahead Viterbi decoder circuit with K=3. It consists of P 1  processors (circuits  402 ,  404 ,  406 , and  408 ), P 2  processors (circuits  410 ,  412 , and  414 ), ACS recursion processor (circuits  416  and  434 ), survivor path management circuits ( 420 ,  422 ,  424 , and  426 ), and pipelining latches (circuits  430 ,  432 , and  434 ).  
         [0047]     In the layer- 1  ACS precomputation, four P 1  processors (circuits  402 ,  404 ,  406 , and  408 ), which have 3-parallel incoming branch metrics each, are needed. Each P 1  executes the ACS precomputation as follows: add 3-parallel incoming branch metrics and compare select two resulting parallel paths.  
         [0048]     Each P 1  processor executes the ACS precomputation for {λ(n), λ(n+1), and λ(n+2)}, {λ(n+3), λ(n+4), and λ(n+5)}, {λ(n+6), λ(n+7), and λ(n+8)}, and {λ(n+11)} as follows: 
 
 p   0,0 ( n+ 3 i +2)=λ 0,0 ( n+ 3 i )+λ 0,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 q   0,0 ( n+ 3 i +2)=λ 0,2 ( n+ 3 i )+λ 2,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2), 
 
 p   1,0 ( n+ 3 i +2)=λ 1,0 ( n+ 3 i )+λ 0,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 q   1,0 ( n+ 3 i +2)=λ 1,2 ( n+ 3 i )+λ 2,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2), 
 
 p   2,0 ( n+ 3 i +2)=λ 2,1 ( n+ 3 i )+λ 1,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 q   2,0 ( n+ 3 i +2)=λ 2,3 ( n+ 3 i )+λ 3,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2), 
 
 p   3,0 ( n+ 3 i +2)=λ 3,1 ( n+ 3 i )+λ 1,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 q   3,0 ( n+ 3 i +2)=λ 3,3 ( n+ 3 i )+λ 3,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2),   EQ. 5 
 
 where index i=0, 1, 2, and 3. p h,j (n+3i+ 2 ) and q h,j  (n+ 3 i+2) are 3-step look-ahead branch metrics of two parallel paths, which start from trellis state-h and end at trellis state-j. EQ. 5 only shows that the ACS precomputations for trellis state- 0 . The ACS precomputations for other trellis states are similar with that of the trellis state- 0 . 
 
         [0050]     The common teems in the K-nested look-ahead branch metrics computation equations (EQ. 5) for trellis state-j can be grouped as 
 
 A=λ   0,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 B=λ   1,0 ( n+ 3 i+ 1)+λ 0,0 ( n+ 3 i+ 2), 
 
 C=λ   2,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2), 
 
 D=λ   3,1 ( n+ 3 i+ 1)+λ 1,0 ( n+ 3 i+ 2), 
 
         [0051]     For each trellis state-j, P 1  selects the minimum paths as follows 
 
 p   1   h,j ( n+ 3 i+ 2)=min{ p   h,j ( n+ 3 i+ 2), q   h,j ( n+ 3 i+ 2)}  EQ. 7 
 
 where subscripts h and j stand for trellis states: 0≦h,j≦3. 
 
         [0053]      FIG. 5  (circuit  500 ) illustrates the P 1  processor for trellis state- 0  for the case of index i=0 in EQ. 5, EQ. 6, and EQ. 7. It has 12 two-input adders (circuit  502 ), 4 compare-select (CS) circuits ( 510 ,  512 ,  514 , and  516 ), and pipelining latches (circuit  520 ). The required number of two input adders and radix-2 CS units for layer- 1  processing are  192  and  64 , respectively.  
         [0054]     Four PPS signals are needed for each trellis state: PPS 1   0,j,i [0], PPS 1   1,j,i [0], PPS 1   2,j,i [0], and PPS 1   3,j,i [0], which consist of one-bit each, since each trellis state has four selected 3-step look-ahead branch metrics, such as p 1   0,j , p 1   1,j , p 1   2,j , and p 1   3,j .  
         [0055]     In layer-k, where 2≦k≦3, P 2  processors select the minimum paths for trellis state-j as follows:  
                 p     h   ,   j     k     (     n   +       2     k   -   1       ⁢   3   ⁢     (     i   +   1     )       -   1     )     =     min   ⁢     {                     p     h   ,   0       k   -   1       ⁡     (     n   +       2     k   -   2       ⁢   3   ⁢     (     i   +   1     )       -   1     )       +                   p     0   ,   j       k   -   1       ⁡     (     n   +       2     k   -   1       ⁢   3   ⁢     (     i   +   1     )       -   1     )       ,                               p     h   ,   1       k   -   1       ⁡     (     n   +       2     k   -   2       ⁢   3   ⁢     (     i   +   1     )       -   1     )       +                   p     1   ,   j       k   -   1       ⁡     (     n   +       2     k   -   1       ⁢   3   ⁢     (     i   +   1     )       -   1     )       ,                               p     h   ,   2       k   -   1       ⁡     (     n   +       2     k   -   2       ⁢   3   ⁢     (     i   +   1     )       -   1     )       +                   p     2   ,   j       k   -   1       ⁡     (     n   +       2     k   -   1       ⁢   3   ⁢     (     i   +   1     )       -   1     )       ,                               p     h   ,   3       k   -   1       ⁡     (     n   +       2     k   -   2       ⁢   3   ⁢     (     i   +   1     )       -   1     )       +                 p     3   ,   j       k   -   1       ⁡     (     n   +       2     k   -   1       ⁢   3   ⁢     (     i   +   1     )       -   1     )                   }               EQ   .           ⁢   8             
 
 Each trellis state has four PPS signals: PPS k   0,j,i [1:0], PPS k   2,j,i [1:0], PPS k   2,j,i [1:0], and PPS k   3,j,i [1:0], which consist of two-bits each. 
 
         [0057]      FIG. 6  (circuit  600 ) illustrates the P 2  processor in layer- 2  for trellis states for the case of index i=0 in EQ. 8. It has 16 two-input adders (circuits  612   a,    612   b,    612   c,  and  612   d ), 4 radix- 4  compare-select (CS) circuits ( 614 ,  624 ,  634 , and  644 ), and pipelining latches (circuit  616 ). For layer- 2  processing, the required number of two input adders and radix- 4  CS units are  128  and  32 , respectively.  
         [0058]      FIG. 7  (circuit  700 ) illustrates the P 2  processor in layer- 3  for trellis state- 4  for the case of index i=0 in EQ. 8. It has  16  two input adders (circuits  712   a,    712   b,    712   c,  and  712   d ), 4 radix- 4  compare-select (CS) circuits ( 714 ,  724 ,  734 , and  744 ), and pipelining latches (circuit  716 ). For layer- 2  processing, the required number of two input adders and radix- 4  CS units are  64  and  16 , respectively.  
         [0059]     For each trellis state-j, the P 3 &#39;s execute the ACS recursions as  
                 γ   j     ⁡     (     n   +   12     )       =     min   ⁢     {                 γ   0     ⁡     (   n   )       +       p     0   ,   j     3     ⁡     (     n   +   11     )         ,                     γ   1     ⁡     (   n   )       +       p     1   ,   j     3     ⁡     (     n   +   11     )         ,                     γ   2     ⁡     (   n   )       +       p     2   ,   j     3     ⁡     (     n   +   11     )         ,                   γ   3     ⁡     (   n   )       +       p     3   ,   j     3     ⁡     (     n   +   11     )               }               EQ   .           ⁢   9             
 
 where the subscript-j=0, 1, 2, and 3 when K=3. For each trellis state, P 3  produces one-survivor path information: PS j,i [1:0], which consists of two bits. 
 
         [0061]      FIG. 8  (circuit  800 ) illustrates the P 3  processor for trellis state- 0 , which is the case for the subscript j=0 in EQ. 9. It has 16 two input adders (circuits  812   a,    812   b,    812   c,  and  812   d ), 4 radix- 4  compare-select (CS) circuits ( 814 ,  824 ,  834 , and  844 ), and pipelining latches (circuit  816 ). The required number of two input adders and radix- 4  CS units for ACS recursion processing are  16  and  4 , respectively.  
         [0062]     In  FIG. 5-8 , CS represents a compare-select unit, which compares look-ahead branch metrics and selects a branch at has minimum metrics. The CS in P 2  and P 3  can be implemented by using a staged architecture, or a branch local architecture. The present invention considers a staged-CS architecture, where 2 K−1  branches can be compared in (K−1) stages of compare-select operations. The latency (L CS     —     staged ) and the complexity (C CS     —     staged ) of radix-R staged CS architecture are as follows: 
 
L CS     —     staged =log 2  R   EQ. 10 
 
C CS     —     staged =R−1   EQ. 11 
 
 In EQ. 11, the complexity represents the number of two input adders (or subtractors) for compare operations. 
 
         [0064]     The survivor path information is easily controlled in a step by step manner, sonar in Table I, since the proposed 12-step K-nested LLA method has the layered structure. The layer- 1  survivor path signals (PPS 1   h,j,i [0] and PPS 1   1,j,i+1 [0]) are selected by the layer- 2  survivor path signal (PPS 2   h,j,i [1:0]). The layer- 2  survivor path signals (PPS 2   h,j,i [1,0] and PPS 2   h,j,i+1 [1:0]) are selected by the layer- 3  survivor path signal (PPS 3   h,j,i [1:0]).  
                         TABLE I                       THE FUNCTION OF SURVIVOR PATH MANAGEMENT UNITS                                PPS 2   h,j,i [1:0]   M2: Y 2   h,j,i [0:3]               00   PPS 1   h,0,i [0] &amp; PPS 2   h,j,i [0:1] &amp; PPS 1   0,j,i+1 [0]       01   PPS 1   h,1,i [0] &amp; PPS 2   h,j,i [0:1] &amp; PPS 1   1,j,i+1 [0]       10   PPS 1   h,2,i [0] &amp; PPS 2   h,j,i [0:1] &amp; PPS 1   2,j,i+1 [0]       11   PPS 1   h,3,i [0] &amp; PPS 2   h,j,i [0:1] &amp; PPS 1   3,j,i+1 [0]               PPS 3   h,j,i [1:0]   M3: Y 3   h,j,i [0:9]               00   Y 2   h,0,i [0:3] &amp; PPS 3   h,j,i [0:1] &amp; Y 2   0,j,i+1 [0:3]       01   Y 2   h,1,i [0:3] &amp; PPS 3   h,j,i [0:1] &amp; Y 2   1,j,i+1 [0:3]       10   Y 2   h,2,i [0:3] &amp; PPS 3   h,j,i [0:1] &amp; Y 2   2,j,i+1 [0:3]       11   Y 2   h,3,i [0:3] &amp; PPS 3   h,j,i [0:1] &amp; Y 2   3,j,i+1 [0:3]               PS j,i [1:0]   MA: Y ACSr   j,i [0:11]               00   PS j,i [0:1] &amp; Y 3   0,j,i [0:9]       01   PS j,i [0:1] &amp; Y 3   1,j,i [0:9]       10   PS j,i [0:1] &amp; Y 3   2,j,i [0:9]       11   PS j,i [0:1] &amp; Y 3   3,j,i [0:9]                  
 
         [0065]     The survivor path management (SPM: M 2 , M 3 , and MA) circuits ( 900 ,  1000 , and  1100 ) are modified multiplexers for survivor path selection in each ACS computation layer. They select and rearrange the PPS&#39;s of the sub-layers. The required number of SPM units is the same as the number of P 2  and P 3  units, since layer- 1  does not need SPM.  
         [0066]     In M 2 , signal PPS 2   h,j,i [1:0] selects one PPS signal pair from four PPS signal pairs which start at trellis state-h and end at trellis state-j according to its value and rearrange them as an output Y 2   h,j,i [0:3]. In  FIG. 9  (circuit  900 ), circuit  910  manages the survivor path for the trellis path from the previous trellis state- 0  to the present trellis state- 0  in layer- 2 . Circuit  920  manages the survivor path for the trellis path from the previous trellis state- 1  to the present trellis state- 0  in layer- 2 . Circuit  930  manages the survivor path for the trellis path from the previous trellis state- 2  to the present trellis state- 0  in layer- 2 . Circuit  940  rearranges the survivor path for the trellis path from the previous trellis state- 3  to the present trellis state- 0  in layer- 2 . The function of M 2  is shown in Table I.  
         [0067]     In M 3 , PPS 3   h,j,i [1:0] selects one PPS signal pair from four PPS signal pairs which start at trellis state-h and end at trellis state-j according to its value and rearrange them as an output Y 3   h,j,i [0:9]. In  FIG. 10  (circuit  1000 ), circuit  1010  manages the survivor path for the trellis path from the previous trellis state- 0  to the present trellis state- 0  in layer- 3 . Circuit  1020  manages the survivor path for the trellis path from the previous trellis state- 1  to the present trellis state- 0  in layer- 3 . Circuit  1030  manages the survivor path for the trellis path from the previous trellis state- 2  to the present trellis state in layer- 3 . Circuit  1040  manages the survivor path for the trellis path from the previous trellis state- 3  to the present trellis state- 0  in layer- 3 . The function of M 3  is shown in Table I.  
         [0068]     In MA, PS j,i [1:0] selects one PPS signal from four PPS signals and concatenates it with the selected PPS signal. In  FIG. 11  (circuit  1100 ), circuit  1110  manages the survivor path for the trellis path from the previous trellis state- 0  to the present trellis state- 0  in ACS recursion layer. Circuit  1120  manages the survivor path for the trellis path from the previous trellis state- 1  to the present trellis state- 0  in ACS recursion layer. Circuit  1130  manages the survivor path for the trellis path from the previous trellis state- 2  to the present trellis state- 0  in ACS recursion layer. Circuit  1140  manages the survivor path for the trellis path from the previous trellis state- 3  to the present trellis state- 0  in ACS recursion layer. The function of MA is shown in Table I.  
         [0069]     The  
         Y     j   ,   i     ACSr     ⁡     [     0   :   11     ]         
 
 signals become the decoded data sequence when the trellis state-j has the smallest state metrics. When the look-ahead step is large (e.g., mK≧4K), all states have the same Y ACSr , i.e.,  
         Y     0   ,   i     ACSr     =       Y     1   ,   i     ACSr     =       Y     2   ,   i     ACSr     =       Y     3   ,   i     ACSr     .             
 
 Therefore, any one of the Y ACSr  sequences can be used as the decoded data sequence without minimum state finding as shown in  FIG. 4 .  
         Y     j   ,   i     ACSr     ⁡     [   0   ]         
 
 becomes the first decoded data bit. This survivor path management method can be systematically expanded for higher order look-ahead architectures. 
 
         [0073]     MA processors (circuits  1110 ,  1120 ,  1130 , and  1140 ) have 4-to-1 multiplexers (circuits  1112 ,  1122 ,  1132 , and  1142 ) and pipelining latches (circuits  1114   a,    1114   b,    1124   a,    1124   b,    1134   a,    1134   b,    1144   a,  and  1144   b ).  
         [0074]     The latency of ACS precomputation for the proposed (L proposed ) and the traditional (L conv ) M-step look-ahead architecture can be calculated as follows:  
               L   proposed     =       L   proposed_add     +     L     CS_radix   -   2       +             EQ   .           ⁢   12                       ⁢       (       log   2     ⁡     (     M   /   K     )       )     ·     L     CS_radix   -     2     K   -   1                                             ⁢     =       (       (     K   -   1     )     +       log   2     ⁡     (     M   /   K     )         )     +   1   +                                       ⁢       (       log   2     ⁡     (     M   /   K     )       )     ·     L     CS_radix   -     2     K   -   1                                             ⁢     =     K   +     K   ·       log   2     ⁡     (     M   /   K     )                                       L   conv     =       L   conv_add     +       (     M   -   K   +   1     )     ·     L     CS_radix   -   2                   EQ   .           ⁢   13                       ⁢     =       (     M   -   1     )     +     (     M   -   K   +   1     )                                         ⁢     =       2   ⁢   M     -   K                             
 
 In EQ. 12, the first term K comes from computing the parallel branch metrics and CS of the sub-trellis, and the second term K·log 2  (M/K) corresponds to the ACS unit in each layered stage. As shown in  FIG. 1-2  and EQ. 12-13, the ACS precomputation latency increases linearly with respect to the look-ahead step M and logarithmically with respect to M/K for the traditional and for the proposed methods, respectively. If M/K is not a power-of-two, ┌log 2  (M/K)┐ is used for latency calculation instead of log 2  (M/K) in EQ. 12. Where the function ┌x┐ is the smallest integer greater than or equal to x. 
 
         [0076]     The complexity of the ACS precomputation can be represented as the number of two-input adders required for the ACS precomputation. For the proposed M-step K-nested LLA architecture, the number of two-input adders (C proposed ) is 
 
 C   proposed   =C   proposed     —     add   +C   proposed     —     CS     —     r2   +C   proposed     —     CS     —     rx ·(2 K−1 −1) EQ. 14 
 
 where the number of two input adders (C proposed     —     add ), mdx- 2  CS units (C proposed     —     CS     —     r2 ) and radix-2 K−1  CS units (C proposed     —     CS     —     rx ) for the ACS precomputation are calculated as  
                 C   proposed_add     =       2     K   -   1       ⁡     [         M   K     ⁢           ⁢       ∑     i   =   2     K     ⁢     2   i         +         (     2     K   -   1       )     2     ⁢     (       M   K     -   1     )         ]         ,             EQ   .           ⁢   14.     ⁢   a                   C     proposed_CS   ⁢   _r2       =         (     2     K   -   1       )     2     ⁢     (     M   K     )         ,             EQ   .           ⁢   14.     ⁢   b                 C     proposed_CS   ⁢   _rx       =         (     2     K   -   1       )     2     ⁢     (       M   K     -   1     )                 EQ   .           ⁢   14.     ⁢   c             
 
         [0078]     For the traditional M-step look-ahead architectures with pipeline structure, the number of two-input adders (C conv ) required for the ACS precomputation is  
                     C   conv     =       ⁢       C   conv_add     +     C     conv_CS   ⁢   _r2                     =       ⁢       2     K   -   1       ⁡     [         ∑     i   =   2       K   -   1       ⁢           ⁢     2   i       +       3.2     K   -   1       ⁢     (     M   -   K   +   1     )         ]                     EQ   .           ⁢   15             
 
 where the number of two input adders (C conv     —     add ) and radix-2 CS units (C conv     —     CS     —     r2 ) are  
                 C   conv_add     =       2     K   -   1       ⁡     [         ∑     i   =   2       K   -   1       ⁢           ⁢     2   i       +       2   K     ⁢     (     M   -   K   +   1     )         ]         ,             EQ   .           ⁢   15.     ⁢   a             
 
 C   conv     —CS       —     r2 =(2 K−i ) 2 ( M−K+ 1)   EQ. 15.b 
 
         [0080]     The decoding latency and the complexity of the ACS precomputation for M-step look-ahead architecture are m in Table II. As can be seen in Table II, even if the look-ahead step (M) is not a power-of-two multiple of the encoder constraint length (K), low-latency Viterbi decoders can be implemented efficiently. For example, if K=7, a 49-parallel design has equivalent latency but fewer functional units than a 56-parallel (2 3 -multiple of K) design.  
                                                                                                                                                                                                                                                               TABLE II                       LATENCY AND COMPLEXITY OF ACS PRECOMPUTATION                                    K = 3                COMPLEXITY                LATENCY   proposed:   traditional:            M   Proposed   traditional   176.(M/3)-112   48.M-80                3 (K)    3 &lt;100.00%&gt;   3    64 &lt;100.00%&gt;   64        6 (2K)    6 &lt;66.67%&gt;   9    240 &lt;115.38%&gt;   208        9 (3K)    9 &lt;60.00%&gt;   15    416 &lt;118.18%&gt;   352       12 (2 2 K = 4K)    9 &lt;42.86%&gt;   21    592 &lt;119.35%&gt;   496       15 (5K)   12 &lt;44.44%&gt;   27    768 &lt;120.00%&gt;   640       18 (6K)   12 &lt;36.36%&gt;   33    944 &lt;120.41%&gt;   784       21 (7K)   12 &lt;30.77%&gt;   39   1120 &lt;120.69%&gt;   928       24 (2 3 K = 8K)   12 &lt;26.67%&gt;   45   1296 &lt;120.90%&gt;   1072       48 (2 4 K = 16K)   15 &lt;16.13%&gt;   93   2704 &lt;121.58%&gt;   2224                        K = 4                COMPLEXITY                LATENCY   proposed:   conventional:            M   Proposed   traditional   1248.(M/4)-960   192.M-480                4 (K)    4 &lt;100.00%&gt;   4    288 &lt;100.00%&gt;   288        8 (2K)    8 &lt;66.67%&gt;   12    1536 &lt;145.45%&gt;   1056       16 (2 2 K = 4K)   12 &lt;42.86%&gt;   28    4032 &lt;155.56%&gt;   2592       32 (2 3 K = 8K)   16 &lt;26.67%&gt;   60    9024 &lt;159.32%&gt;   5664       48 (12K)   20 &lt;21.74%&gt;   92   14016 &lt;160.44%&gt;   8736                        K = 5                COMPLEXITY                LATENCY   proposed:   conventional:            M   Proposed   traditional   9152.(M/5)-7936   768.M-2624                5 (K)    5 &lt;100.00%&gt;   5    1216 &lt;100.00%&gt;   1216       10 (2K)   10 &lt;66.67%&gt;   15   10368 &lt;205.06%&gt;   5056       20 (2 2 K = 4K)   15 &lt;42.86%&gt;   35   28672 &lt;225.13%&gt;   12736       40 (2 3 K = 8K)   20 &lt;26.67%&gt;   75   65280 &lt;232.35%&gt;   28096       50 (10K)   25 &lt;26.32%&gt;   95   83584 &lt;233.63%&gt;   35776                        K = 7                COMPLEXITY                LATENCY   proposed:   conventional:            M   Proposed   conventional   1326848.(M/7)-1306624   12288.M-65792                7 (K)    7 &lt;100.00%&gt;   7    20224 &lt;100.00%&gt;   20224       14 (2K)   14 &lt;66.67%&gt;   21   1347072 &lt;1267.95%&gt;   106240       28 (2 2 K = 4K)   21 &lt;42.86%&gt;   49   4000768 &lt;1437.72%&gt;   278272       35 (5K)   28 &lt;44.44%&gt;   63   5327616 &lt;1462.47%&gt;   364288       42 (6K)   28 &lt;36.36%&gt;   77   6654464 &lt;1477.77%&gt;   450304       49 (7K)   28 &lt;30.77%&gt;   91   7981312 &lt;1488.16%&gt;   536320       56 (2 3 K = 8K)   28 &lt;26.67%&gt;   105   9308160 &lt;1495.68%&gt;   622336                  
 
       Conclusion  
       [0081]     Various embodiments of the present invention have been described above. These various embodiments can be implemented, for example, in optical fiber, twisted-pair, coaxial cable, and wireless communication receivers. These various embodiments can also be implemented in systems other than communications systems. It should be understood that these embodiments have been presented by way of example only, and not limitation. It will be understood by those skilled in the relevant art that various changes in form and details of the embodiments described above may be made without departing from the spirit and scope of the present invention as defined in the claims. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.