Abstract:
The invention relates to techniques for pipelining parallel decision feedback decoders (PDFDs) for high speed communication systems, such as 10 Gigabit Ethernet over copper medium (10GBASE-T). In one aspect, the decoder applies look-ahead methods to two concurrent computation paths. In another aspect of the invention, retiming and reformulation techniques are applied to a parallel computation scheme of the decoder to remove all or a portion of a decision feedback unit (DFU) from a critical path of the computations of the pipelined decoder. In addition, the decoder may apply a pre-cancellation technique to a parallel computation scheme to remove the entire DFU from the critical path.

Description:
[0001]     This application claims the benefit of U.S. Provisional Application No. 60/609,304, to Parhi et al., entitled “PIPELINED PARALLEL DECISION FEEDBACK DECODERS FOR HIGH-SPEED COMMUNICATION SYSTEMS,” filed Sep. 13, 2004, and U.S. Provisional Application No. ______, to Parhi et al., entitled “PIPELINED PARALLEL DECISION FEEDBACK DECODERS FOR HIGH-SPEED COMMUNICATION SYSTEMS,” having attorney docket no. 1008-030USP2, filed Sep. 9, 2005, the entire contents of each being incorporated herein by reference. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH FOR DEVELOPMENT  
       [0002]     The invention was made with Government support from the National Science Foundation No. CCF-0429979. The Government may have certain rights in this invention. 
     
    
     TECHNICAL FIELD  
       [0003]     The invention relates to computer networks, more specifically to decoding data received from computer networks.  
       BACKGROUND  
       [0004]     Currently, local area networks (LANs) are utilizing Gigabit Ethernet over copper medium, a protocol commonly referred to as 1000BASE-T. The next generation high-speed Ethernet is 10 Gigabit Ethernet over copper medium, a protocol commonly referred to as 10GBASE-T. The Institute of Electrical and Electronic Engineers (IEEE) 802.3 10GBASE-T study group is investigating the feasibility of transmission of 10 Gigabits per second over 4 unshielded twisted pairs.  
         [0005]     10GBASE-T will probably use a pulse amplitude modulation (PAM) scheme, such as PAM10 combined with a four dimensional trellis code as the basis for its transmission scheme. The symbol rate of this scheme is 833 M baud with each symbol representing 3 bits of information. One of the powerful yet simple algorithms to decode the code as well as to combat inter-symbol interference is the parallel decision-feedback decoding algorithm. However, the implementation and design of a parallel decision-feedback decoder (PDFD) which operates at 833 MHz is challenging due to the long critical path in the decoder structure.  
         [0006]     Existing literature describes high-speed PDFD designs suitable for 1000BASE-T applications. However, most of the proposed techniques may not be suitable for 10GBASE-T. For example, the decision feedback pre-filtering technique only works for channels where the postcursor ISI&#39;s energy is concentrated on the first one or two taps. Otherwise, it may result in significant performance loss. Furthermore, the complexity is exponential with channel memory length, so it is only suitable for channels with short memory length while the channel memory length of 10GBASE-T is substantially longer than that of 1000BASE-T.  
       SUMMARY  
       [0007]     In general, the invention relates to techniques for pipelining parallel decision feedback decoders (PDFDs) for high speed communication systems, such as 10 Gigabit Ethernet over copper medium (10GBASE-T). In one aspect, the decoder applies look-ahead methods to two concurrent computation paths. In another aspect of the invention, retiming and reformulation techniques are applied to a parallel computation scheme of the decoder to remove all or a portion of a decision feedback unit (DFU) from a critical path of the computations of the pipelined decoder. In addition, the decoder may apply a pre-cancellation technique to a parallel computation scheme to remove the entire DFU from the critical path.  
         [0008]     Utilization of pipelined PDFDs may enable network providers to operate 10 Gigabit Ethernet with copper cable rather than fiber optic cable. Thus, network providers may operate existing copper cable networks at higher speeds without having to incur the expense of converting copper cables to more expensive fiber optic cables. Furthermore, the pipelined PDFD techniques may reduce hardware overhead and complexity of the decoder.  
         [0009]     In one embodiment, a parallel decision feedback decoder (PDFD) comprises a plurality of computational units, wherein the computational units are pipelined to produce a decoded symbol for each computational iteration.  
         [0010]     In another embodiment, a method comprises receiving a signal from a network, and processing the signal with a parallel decision feedback decoder (PDFD) having a plurality of pipelined computational units to produce a decoded symbol for each computational iteration of the PDFD.  
         [0011]     The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims. 
     
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0012]      FIG. 1  is a block diagram illustrating an exemplary network communication system.  
         [0013]      FIG. 2  is a block diagram illustrating an exemplary improved scheduling of computations in a PDFD algorithm.  
         [0014]      FIG. 3  is a block diagram of a first exemplary high-speed PDFD architecture.  
         [0015]      FIG. 4  is a block diagram illustrating an exemplary computation of look-ahead ID branch metrics.  
         [0016]      FIG. 5  is a block diagram illustrating an exemplary 1D branch metric selection unit.  
         [0017]      FIG. 6  is a block diagram illustrating an exemplary calculation of 4D branch metrics.  
         [0018]      FIG. 7  is a block diagram illustrating an exemplary architecture of an ACSU for one code state.  
         [0019]      FIG. 8  is a block diagram illustrating an exemplary architecture of a SMU.  
         [0020]      FIGS. 9A-9E  are block diagrams illustrating exemplary retiming and reformulation techniques for removing the LA DFU from the critical path.  
         [0021]      FIG. 10  is a block diagram of a second exemplary high-speed PDFD architecture.  
         [0022]      FIG. 11  is a block diagram illustrating an exemplary pre-cancellation technique and computation of LA 1D branch metrics.  
         [0023]      FIG. 12  is a block diagram of a third exemplary high-speed PDFD architecture. 
     
    
     DETAILED DESCRIPTION  
       [0024]      FIG. 1  is a block diagram of an exemplary network communication system  2 . For purposes of the present description, communication system  2  will be assumed to be a 10 Gigabit Ethernet over copper network. Although the system will be described with respect to 10 Gigabit Ethernet over copper, it shall be understood that the present invention is not limited in this respect, and that the techniques described herein are not dependent upon the properties of the network. For example, communication system  2  could also be implemented within networks of various configurations utilizing one of many protocols without departing from the scope of the present invention.  
         [0025]     In the example of  FIG. 1 , communication system  2  includes transmitter  6  and receiver  14 . Transmitter  6  comprises encoder  10 , which encodes outbound data  4  for transmission via network connection  12 . Outbound data  4  may take the form of a stream of symbols for transmission to receiver  4 . Once receiver  14  receives the encoded data, decoder  16  decodes the data resulting in decoded data  18 , which may represent a stream of estimated symbols. In some cases decoded data  18  may then be utilized by applications within a network device that includes receiver  14 .  
         [0026]     In one embodiment, transmitter  6 , located within a first network device (not shown), may transmit data to receiver  14 , which may be located within a second network device (not shown). The first network device may also include a receiver substantially similar to receiver  14 . The second network device may also include a transmitter substantially similar to transmitter  6 . In this way, the first and second network devices may achieve two way communication with each other or other network devices. Examples of network devices that may incorporate transmitter  6  or receiver  14  include desktop computers, laptop computers, network enabled personal digital assistants (PDAs), digital televisions, or network appliances generally.  
         [0027]     Decoder  16  may be a high-speed decoder such as a pipelined parallel decision feedback decoder (PDFD). Utilization of pipelined PDFDs may enable network providers to operate 10 Gigabit Ethernet with copper cable. For example, network providers may operate existing copper cable networks at higher speeds without having to incur the expense of converting copper cables to more expensive media, such as fiber optic cables. Furthermore, in certain embodiments of the invention, the pipelined PDFD design may reduce hardware overhead of the decoder. Although the invention will be described with respect to PDFD decoders, it shall be understood that the present invention is not limited in this respect, and that the techniques described herein may apply to other types of decoders.  
         [0028]     Conventional PDFD algorithms perform computations in a serial manner. At time n, the conventional PDFD first computes inter-symbol interference (ISI) estimates. Next, these ISI estimates and the received samples are used to compute one dimensional (1D) branch metrics. Then the 1D branch metrics are added up to obtain four dimensional (4D) branch metrics. Lastly, the 4D branch metrics are used to update state metrics and survivor paths. This entire process is repeated at the next iteration. In this serial process, all of the computations are on the critical path.  
         [0029]      FIG. 2  is a block diagram illustrating an exemplary improved scheduling  20  of computations in a PDFD algorithm. Right after finishing the computation of 1D branch metrics (1D BM) for iteration n, the PDFD algorithm begins to pre-compute the branch metrics for the next iteration (n+1) since the two possible candidate 1D symbols for each wire are already known. The real 1D branch metrics are selected upon the completion of the add-compare-select (ACS) operation of iteration n. This process is repeated at the next time as illustrated in  FIG. 2 .  
         [0030]      FIG. 3  is a block diagram of a first exemplary high-speed PDFD architecture  30 , corresponding to the computation scheduling of  FIG. 2 . PDFD architecture  30  comprises two concurrent computation paths. Path one consists of look-ahead DFU (LA DFU)  32 , look-ahead 1D branch metric unit (LA 1D BMU)  34 , and 1D branch metric selection unit  35 . The computation time of path one is 6 additions, one slicing operation, one random logic, and two multiplexing operations. The second path includes 4D BMU  36 , add-compare-select unit (ACSU)  38 , and survivor memory unit (SMU)  39 . The computation time of the second path is 5 additions, one 4-to-1 multiplex operation, one 2-to-1 multiplex operation, and a random select logic. Thus, path one dominates the computation time and becomes the critical path in the proposed design. Compared with a straightforward implementation, it can achieve a speedup of around 1.5. The term “straightforward” refers to non-pipelined PDFDs and will be used throughout this detailed description.  
         [0031]     At time n, look-ahead DFU  32  is used to compute partial ISI estimates for code state ρ n+1  due to the channel coefficients {f 2,j , f 3,j , . . . , f N,j } based on the already known survivor symbol sequence. Assuming there is a state transition between ρ n  and ρ n+1 , then the partial ISI estimate for ρ n+1  corresponding to the transition can be calculated as:  
                   u   ~         n   +   1     ,   j       ⁡     (     ρ   n     )       =     -       ∑     i   =   2     L     ⁢           ⁢       f     i   ,   j       ⁢         a       n   -   i   +   1     ,   j       ⁡     (     ρ   n     )       .                   (   1   )             
 
 Since there are 8 code states and 4 wires, altogether 32 look-ahead ISI estimates are needed to compute. The computation time of look-ahead DFU  32  is around 4 additions if we use carry-save adder structure. 
 
         [0032]     The look-ahead 1D BMU  34  computes look-ahead 1D branch metrics for transitions departing from code states {ρ n+1 } Inputs to the look-ahead 1D BMU are partial ISI estimates {û n+1,j (ρ n )} due to {f 2,j , f 3,j , . . . , f N,j } and the received sample z n+1,j . In addition, look-ahead 1D BMU  34  needs to consider the ISI partial contribution due to the channel coefficient f 1,j  and the 1D symbol decision a n,j (ρ n →ρ n+1 ) associated with state transitions ρ n →ρ n+1 . A speculative ISI estimate for the state transition ρ n →ρ n+1  can be calculated as  
                   u   ^         n   +   1     ,   j       ⁡     (       ρ   n     →     ρ     n   +   1         )       =             u   ^         n   +   1     ,   j       ⁡     (     ρ   n     )       -       f     1   ,   j       ⁢     a     n   ,   j       ⁢     (       ρ   n     →     ρ     n   +   1         )         =         ∑     i   =   2     L     ⁢           ⁢       f     i   ,   j       ⁢       a       n   -   i   +   1     ,   j       ⁡     (     ρ   n     )           -       f     1   ,   j       ⁢       a     n   ,   j       ⁡     (       ρ   n     →     ρ     n   +   1         )                     (   2   )             
 
         [0033]     Since pulse amplitude modulation ten (PAM10) is utilized, there are 10 possible choices for a n,j (ρ n →ρ n+1 ) and in turn 10 possibilities for û n+1,j (ρ n →ρ n+1 ). The high-speed PDFD architecture  30  ( FIG. 3 ) enables a reduction in hardware overhead by feedbacking the previous 1D branch metric results (for transitions {ρ n }→{ρ n+1 }) to the current calculation of the look-ahead 1D branch metrics. After the completion of 1D branch metrics for transitions departing from a state ρ n , there are only two possible choices for a n,j  associated with the state transition ρ n →ρ n+1 , one a n,j (ρ n , A)) from subset A and the other a n,j (ρ n , B)) from subset B. In addition, as is evident from equation: 
 
λ n (r n,j ,a n,j ,ρ n )=(r n,j −a n,j +u n,j (ρ n )) 2    (3) 
 
 the two possibilities for a n,j  are only dependent on ρ n . Thus, there are only two possibilities for û n+1,j (ρ n →ρ n+1 ). Therefore, the only pre-computations needed are look-ahead 1D branch metrics for the 2 possibilities, resulting in a high hardware reduction. 
 
         [0034]     As the two possible choices for a n,j (ρ n →ρ n+1 ) are only dependent on the initial state ρ n , the possible ISI estimates for state ρ n+1  are only dependent on ρ n  too. For code states {ρ n+1 =0,1,2,3}, as they have the same predecessor states {ρ n =0,2,4,6}, their LA 1D branch metrics are the same. Therefore, LA 1D branch metrics for only one of them needs to be computed. This is also true for code states {ρ n+1 =4,5,6,7}. For wire j and initial code state ρ n  four look-ahead 1D branch metrics are needed to be calculated according to: 
 
{circumflex over (λ)} n+1,j (r n+1,j ,a n+1,j ,ρ n na n,j )=(r n+1,j −a n+1 +u n+1,j (ρ n )−f 1,j a n.,j ) 2    (4) 
 
 with two (one per 1D subset for a n+1,j ) for a n,j =a n,j (ρ n , A) and two for a n,j =a n,j (ρ n , B). As there are eight code states and four wires, altogether 8×4×4=128 1D look-ahead branch metrics are needed to compute. This is a reduction to the 640 look-ahead branch metrics which are needed to compute in straightforward implementations. 
 
         [0035]      FIG. 4  is a block diagram illustrating an exemplary computation of look-ahead 1D branch metrics  34 , corresponding to LA 1D BMU within high-speed PDFD architecture  30  ( FIG. 3 ). The inputs are the received sample r n+1,j  the look-ahead ISI estimate u n+1,j (ρ n ), and the two possible candidates for the transmittal symbol a n,i  associated with the state ρ n , obtained from the last iteration. As illustrated in  FIG. 4 , the computation time of look-ahead 1D BMU  34  consist of two additions, one slicing operation, and one squaring function.  
         [0036]     For code state ρ n+1  and wire j, two real 1D metrics (one for a n,j εA and one for B) need to be selected among 16 precomputed branch metrics (four from each of 4 predecessor states of ρ n+1 ).  
         [0037]      FIG. 5  is a block diagram illustrating an exemplary 1D branch metric selection unit  35 , corresponding to 1D branch metric selection unit within high-speed PDFD architecture  30  ( FIG. 3 ).  FIG. 5  shows the selection for the A-type branch metric λ n+1,j (r n+1 , a n+1,j (ρ n+1 =0, A), ρ +1 =0). The inputs are 8 eight precomputed branch metrics with two from each of 4 predecessor states, the 1D symbol decision associated with state transition ρ n →ρ n+1  from the 4D BMU, and the ACSU decision d n (ρ n+1 ). The computation time of the selection operation is two multiplexing operations.  
         [0038]     4D branch metrics  36  ( FIG. 3 ) are obtained by just adding up the 1D branch metrics from the 1D BMU according to:  
                 λ   n     ⁡     (       r   n     ,     a   n     ,     ρ   n       )       =       ∑     j   =   1     4     ⁢           ⁢       λ     n   ,   j       ⁡     (       r     n   ,   j       ,     a     n   ,   j       ,     ρ   n       )                 (   5   )             
 
 For each state transition ρ n →ρ n+1  two 4D branch metrics (one is associated with an A-type 4D symbol and the other B-type) are needed to be computed. The smaller metric (referred to as λ n (r n , a n , ρ n →ρ n+1 ) and its associated 4D symbol a n (ρ n →ρ n+1 ) are selected to be used in ACSU  38 . 
 
         [0039]      FIG. 6  is a block diagram illustrating an exemplary calculation of 4D branch metrics  36  of branches departing from state 0, corresponding with 4D branch metrics within high-speed PDFD architecture  30  ( FIG. 3 ). The computation time of the 4D BMU is 3 additions and one 2-to-1 multiplexing operation.  
         [0040]     ACSU 38 ( FIG. 3 ) is used to determine the best survivor path into code state ρ n+1  from its four predecessor states by performing the four-way add-compare-select (ACS) operation:  
                 Γ     n   +   1       ⁡     (     ρ     n   +   1       )       ⁢     =       ρ   n     →     ρ     n   +   1         min     ⁢     {         Γ   n     ⁡     (     ρ   n     )       +       λ   n     ⁡     (       r   n     ,       a   n     ⁡     (       ρ   n     →     ρ     n   +   1         )       ,       ρ   n     →     ρ     n   +           )         }             (   6   )             
 
 The outputs of ACSU  38  are the newly decoded 4D survivor symbol a n (ρ n+1 ) and path selection decision d n (ρ n+1 ). The outputs are used to update the survivor sequence. The new sequence will be used to compute ISI estimates in the next iteration. 
 
         [0041]      FIG. 7  is a block diagram illustrating an exemplary architecture of ACSU  38  for one code state, corresponding with 4D branch metrics within high-speed PDFD architecture  30  ( FIG. 3 ). The computation time of ACSU  38  consists of two additions, one random select operation and one 4-to-1 multiplexing operation.  
         [0042]      FIG. 8  is a block diagram illustrating an exemplary architecture of SMU  39 , corresponding with SMU within high-speed PDFD architecture  30  ( FIG. 3 ). SMU  39  is register exchange architecture, which is applicable to high-speed applications. Optionally, SMU  39  may utilize a trace-back architecture. The survivor sequences merge after 5 to 6 times code memory length. Thus, the decoding depth is assumed to be 18. The computation time of SMU  39  is one 4-to-1 multiplexing operation.  
         [0043]     As illustrated in  FIG. 3 , path one of high-speed PDFD architecture  30 , consisting of LA DFU, LA 1D BMU, and 1D branch metric selection unit, dominates the computation time and becomes the critical path in high-speed PDFD architecture  30 . As will be described below, removing all or a portion of the LA DFU from the critical path results in additional high-speed PDFD architectures.  
         [0044]      FIGS. 9A-9E  are block diagrams illustrating exemplary retiming and reformulation techniques for removing the LA DFU from the critical path.  FIG. 9A  is a block diagram of an exemplary composite architecture 50 for LA DFU  34  and SMU  39  within high-speed PDFD architecture  30  ( FIG. 3 ).  FIG. 9A  illustrates a long-chain of adders, as shown by dashed line  51 , which are directly connected to the 1D BMU, resulting in a long critical path.  
         [0045]      FIG. 9B  is a block diagram illustrating an exemplary first retiming cutset  52 . The long chain of adders from the BMU are isolated by using the retime cutsets shown by dotted lines  53  in  FIG. 9B . The resulting circuit  54  is illustrated in  FIG. 9C . Applying retiming again using cutest  55  illustrated in  FIG. 9C , the retimed DFU  56  of  FIG. 9D  is obtained. However, in  FIG. 9D  the long chain of adders is now connected to the ACSU through a multiplexer, and the DFU is still on the critical path. Moving the multipliers before the corresponding multiplexers results in delays between the long chain of adders and the ACSU. This is done by performing the following reformulation:  
                     ∑     i   =   3     L     ⁢           ⁢     Sel   (         d   n     ⁡     (       ρ     n   +   1       =   0     )       ,       a     n   -   i   +   2       ⁡     (       ρ   n     =   0     )       ,                       a     n   -   i   +   2       ⁡     (       ρ   n     =   2     )       ,       a     n   -   i   +   2       ⁡     (       p   n     =   4     )       ,                     a     n   -   i   +   2       ⁡     (       ρ   n     =   6     )       )     ⋆     f   i                 =     Sel   (         d   n     ⁡     (       ρ     n   +   1       =   0     )       ,       ∑     i   =   3     L     ⁢         a     n   -   1   +   2       ⁡     (       ρ   n     =   0     )       ⁢     f   i         ,                       ∑     i   =   3     L     ⁢         a     n   -   i   +   2       ⁡     (       ρ   n     =   2     )       ⁢     f   i         ,       ∑     i   =     3               L     ⁢         a     n   -   1   +   2       ⁡     (       ρ   n     =   4     )       ⁢     f   i         ⁢     ,                               ∑     i   =   3     L     ⁢           ⁢         a     n   -   1   +   2       ⁡     (       ρ   n     =   6     )       ⁢     f   i         )     ,                 (   7   )               
 where Sel(d, x 0 ,x 1 ,x 2 ,x 3 ) is a 4-to-1 multiplexing function and depending on d, Sel(d, x 0 ,x 1 ,x 2  ,x 3 ) selects one of x i , i=0,1,2,3 as its output. 
 
         [0046]      FIG. 9E  illustrates reformulated DFU  58 . DFU  58  is divided into two parts, DFU  1  ( 59 ) and DFU  2  ( 60 ). The major part, DFU  2  ( 60 ), which has a long chain of adders, is now isolated from both of the BMU and ACSU and is no longer on the critical path. Part of the DFU, DFU  1  ( 59 ) is still directly connected to the BMU, which may contribute to the critical path of the design in  FIG. 3 . The DFU may be completely removed from the critical path by using pre-computation to DFU  1  ( 59 ).  
         [0047]      FIG. 10  is a block diagram of a second exemplary high-speed PDFD architecture  70 . By utilizing the retiming and reformulating techniques illustrated in  FIG. 9E , LA DFU  1  ( 74 ) and LA DFU  2  ( 72 ) are included in high-speed PDFD architecture  70 . The computation path is pipelined into three stages. The critical path only includes 4-D BMU  76 , ACSU  78 , and SMU  80 . LA DFU  1  ( 74 ) is moved to the LA 1D BMU path. As illustrated in  FIG. 9E , the computation time of the LA DFU  1  ( 74 ) is only one addition. Depending on the detailed design, the critical path may be the one which includes 4D BMU, ACSU and SMU or the one with LA DFU  1  and LA 1D BMU. Compared with the straightforward design, high-speed PDFD architecture  70  achieves a speedup of around 2.  
         [0048]      FIG. 11  is a block diagram illustrating an exemplary pre-cancellation technique and computation of LA 1D branch metrics ( 90 ), which may further reduce hardware overhead. The ISI contribution from the postcursor coefficient f 2,j  for the received sample r n+1,j  is pre-cancelled, and the DFU  1  is removed. Since there are five possibilities for each transmitted symbol a n−1,j , pre-computation technique is used to compute r n+1,j −f 2,j a n−1,j . The real transmitted symbol is chosen by using a multiplexer, and then the transmitted symbol is sent to the BMU. The precomputation of r n+1,j −f 2,j a n−1,j  is easily isolated from the critical path by cutset pipelining. The hardware overhead is reduced to 4*5=20 adders and a multiplexer array.  
         [0049]      FIG. 12  is a block diagram of a third exemplary high-speed PDFD architecture  100 , which utilizes the pre-cancellation technique  90  ( FIG. 11 ). The computation path in high-speed PDFD architecture  100  is also pipelined into three stages. The critical path is the path which includes 4D-BMU  102 , ACSU  104  and SMU  106 . The LA DFU  2  ( 108 ) is removed from the critical path. Compared with the straight-forward implementation, high-speed PDFD architecture  100  achieves a speedup of around 2.  
         [0050]     The proposed techniques in the previous sections are also applicable to other applications and trellis coded modulation schemes other than the one described in this paper. The proposed techniques may be used for any applications where it is necessary to decode trellis encoded signals in the presence of inter-symbol interference and noise. For example, the proposed techniques may be used for 1000BASE-T which uses a 5-level PAM modulation combined with a 4D 8-state trellis code.  
         [0051]     Various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.