Patent Document

FIELD OF THE INVENTION 
   The present invention relates to digital communications. More particularly, the present invention relates to pipelined add-compare-select circuits and methods, and applications thereof. 
   BACKGROUND OF THE INVENTION 
   Communicating information via the intemet and other digital communications systems has become common in the United States and elsewhere. As the number of people using these communications systems has increased so has the need for transmitting digital data at ever increasing rates. 
   As will be understood by persons skilled in the relevant arts, digital communications systems are designed, for example, using conventional pipelining, look-ahead, and parallelism techniques. These conventional design techniques have enabled engineers to build digital communications systems, using available manufacturing technologies, which operate at data rates in excess of 1 Gb/s. Applying these conventional techniques to the design of high-speed digital circuits, however, is difficult particularly when dealing with feedback and/or recursive operations. Furthermore, many of these conventional techniques will not improve the performance of the digital circuit to which they are applied, and some of these conventional techniques can even degrade circuit performance. 
   There is a current need for new design techniques and digital logic circuits that can be used to build high-speed digital communications systems. In particular, design techniques and digital logic circuits are needed that improve the throughput of add-compare-select circuits used in digital communications systems. 
   BRIEF SUMMARY OF THE INVENTION 
   Digital communications devices having high-speed add-compare-select circuits, and methods for designing the same are provided. The add-compare-select circuits include logic segments separated by delay devices. The separation of the logic segments allows for pipelining of the add-compare-select processes and advantageous circuit retiming. The pipelining and advantageous circuit retiming permit the digital communications devices to be clocked at higher rates than similar digital communications devices having conventional add-compare-select circuits. 
   In an embodiment, an add-compare-select (ACS) circuit is provided. The ACS circuit includes an adder, two code converters, a maximum or minimum select circuit, two decision logic circuits, and a delay circuit. The adder has an input port, a sum output port, and a carry output port. A first one of the code converters has an input port and an output port. The input port of this code converter is coupled to the sum output port of the adder. The second code converter also has an input port and an output port. The input port of this code converter is coupled to the carry output port of the adder. The maximum or minimum select circuit has a first input port, a second input port, and an output port. The first input port is coupled to the output port of the first code converter. The output is coupled to the input port of the adder. A first one of the decision logic circuits has an input port and an output port. The input port is coupled to the output port of the second code converter. The delay circuit has an input port and an output port. The input port is coupled to the output port of the first decision logic circuit. The second decision logic circuit has an input port and an output port. The input port is coupled to the output port of the delay device. The output port is coupled to the second input port of the maximum or minimum select circuit. 
   In an embodiment, a method for designing an add-compare-select circuit is provided. A number of bits (B) to be compared is selected. An initial most-significant bit first add-compare-select circuit capable of operating on B-bits is formed. A critical path in the initial most-significant-bit-first add-compare-select circuit is identified. The processing time of this critical path is designated as T. A sub-circuit of the initial most-significant-bit-first add-compare-select circuit is divided into a first sub-circuit segment and a second sub-circuit segment. This divided sub-circuit forms part of the identified critical path. A delay circuit is added between the first sub-circuit segment and the second sub-circuit segment to form a modified most-significant bit first add-compare-select circuit. A clocking circuit is formed to clock the modified most-significant bit first add-compare-select circuit. The clocking circuit formed has a clock period less than T. 
   Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES 
     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 leftmost 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. 
       FIG. 1A  is a block diagram of a Viterbi decoder. 
       FIG. 1B  is a block diagram of an add-compare-select circuit. 
       FIG. 2  is a trellis diagram for a 4-state Viterbi decoder. 
       FIG. 3  is a trellis diagram for a 4-state Viterbi decoder using 2-step look-ahead. 
       FIG. 4  is a trellis diagram for three time-steps of a 4-state Viterbi decoder. 
       FIG. 5  is a trellis diagram for an 8-state Viterbi decoder using 2-step look-ahead. 
       FIG. 6  is a trellis diagram for an 8-state Viterbi decoder using 3-step look-ahead. 
       FIG. 7  is a trellis diagram for an 8-state Viterbi decoder using 4-step look-ahead. 
       FIG. 8  is a circuit diagram of one bit-slice of a most-significant-bit first add-compare-select circuit. 
       FIG. 9A  is a circuit diagram for a feedback loop of the circuit of  FIG. 8 . 
       FIG. 9B  is a circuit diagram for a feedback loop of the circuit of  FIG. 8 . 
       FIG. 9C  is a circuit diagram for a critical path of the circuit of  FIG. 8 . 
       FIG. 10  is a circuit diagram illustrating cut-sets that can be used to retime the circuit of  FIG. 8 . 
       FIG. 11  is a circuit diagram illustrating the retimed circuit of  FIG. 10 . 
       FIG. 12  is a circuit diagram for a critical path of the circuit of  FIG. 11 . 
       FIG. 13  illustrates how to segment a decision logic circuit to achieve advantageous retiming results. 
       FIG. 14A  is a circuit diagram illustrating the use of segmented decision logic circuits. 
       FIG. 14B  is a circuit diagram illustrating how to retime the circuit of  FIG. 14A . 
       FIG. 15  is a circuit diagram of a code converter. 
       FIG. 16  is a circuit diagram of a maximum select circuit. 
       FIG. 17  is a circuit diagram of a decision logic circuit. 
       FIG. 18  is a circuit diagram of a decision logic circuit. 
       FIG. 19  is a circuit diagram of a maximum select circuit. 
       FIG. 20  is a circuit diagram of a minimum select circuit. 
       FIG. 21  is a circuit diagram of a decision logic circuit. 
       FIG. 22  is a circuit diagram of a decision logic circuit. 
       FIG. 23  is a circuit diagram of a minimum select circuit. 
       FIGS. 24A and 24B  illustrate how to implement a preprocessing block. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The present invention presents add-compare-select circuits and methods, and applications thereof. Add-compare-select circuits and methods are used to implement digital communications systems such as, for example, digital communications systems employing convolutional encoding with Viterbi decoding. Convolutional encoding with Viterbi decoding is a forward error correction technique that improves the capacity of a digital communications channel. Viterbi decoding can be viewed as a process for identifying a most likely transition path through a trellis diagram representing possible state transitions in a digital communications system. 
     FIG. 1A  illustrates an example Viterbi decoder  102  that can be implemented using the add-compare-select circuits and methods of the present invention. Viterbi decoder  102  includes a branch metric unit  104 , an add-compare-select (ACS) unit  106 , and a survivor path memory  108 . Viterbi decoder  102  implements the Viterbi algorithm to decode digital data sequences that have been encoded using a convolutional encoder (not shown). 
   The branch metric unit  104  computes minimum or maximum branch metrics, λ ij , for a trellis diagram. As described herein, these branch metrics represent the difference between a received symbol and one or more symbols responsible for a state transition in the trellis diagram. Once computed, the branch metrics, λ ij , are passed to the ACS unit  106 . 
   The ACS unit  106  computes state metrics, γ j . This computation is performed using the branch metrics, λ ij , computed by branch metric unit  104 . ACS unit  106  then compares the computed state metrics, γ j , and selects maximum or minimum state metrics, γ j , associated with survivor paths of the trellis diagram. Survivor paths represent the paths in the trellis diagram that have the best metric (e.g., maximum or minimum state metric) at a point in time under consideration. 
   The survivor path memory  108  stores the survivor paths selected by ACS unit  106 . A final determination of the best path is made from the stored survivor paths residing in the survivor path memory  108 . 
     FIG. 1B  further illustrates the ACS unit  106  shown in  FIG. 1A . As illustrated in  FIG. 1B , the ACS unit  106  includes an adder  110 , a code converter  112 , and a maximum/minimum select circuit  114 . The adder  10  is used to add state metrics and branch metrics to form new state metrics. These new state metrics are provided to code converter  112 . The code converter  112  re-codes the output of adder  110  (the new state metrics) and provides the re-coded output to the maximum/minimum select circuit  114 . This re-coding performed by code converter  112  simplifies the logic needed to implement the maximum/minimum select circuit  114 . In embodiments, the maximum/minimum select circuit  114  compares and selects either a maximum state metric or a minimum state metric from a group of state metrics. Circuits according to the invention for implementing ACS unit  106  are described in detail below. 
   While only one adder  110 , one code converter  112 , and one maximum/minimum select circuit  114  are shown in  FIG. 1B , it will be apparent to persons skilled in the relevant arts given the description herein that more than one adder  110 , more than one code converter  112 , and more than one maximum/minimum select circuit  114  can be used to implement ACS unit  106  without departing from the scope of the present invention (see, e.g.,  FIG. 8 ). 
     FIG. 2  illustrates an example trellis diagram  200  for a four-state Viterbi decoder that can be implemented in accordance with the circuits and the methods of the present invention. The four states 0, 1, 2, and 3 at time index “n” are indicated along the left side of the trellis diagram  200 . These four states each have an associated state metric (i.e., γ 0 (n), γ 1 (n), γ 2 (n), and γ 3 (n)) that represents the accumulated metric along the shortest or longest path leading to the particular state. The four states 0, 1, 2, and 3 at time index “n+1” are indicated on the right side of the trellis diagram  200 . 
   As would be known to persons skilled in the relevant arts, the Viterbi algorithm implemented by a Viterbi decoder can be used to correct data transmission errors in a digital communication system. The Viterbi algorithm involves, for example, determining the most likely path taken to reach a particular state of a given trellis diagram such as trellis diagram  200 . In embodiments, this is achieved by calculating all possible metrics for a particular state of the trellis diagram and selecting the path associated with either the maximum metric or the minimum metric as the most likely path taken to reach the particular state. 
   The branch metrics λ ij (n) for the trellis diagram  200  are indicated along each path leading from one state at time index “n” to another state at time index “n+1”. The branch metric λ 01 (n), for example, represents the metric associated with a transition from state 0 to state 1 along branch  202 . The metric associated with the state 0, for a transition along branch  202 , is equal to the sum of the metric associated with state 0 (i.e., γ 0 (n)) and the metric λ 01 (n). As illustrated in  FIG. 2 , a state at time index “n+1” can be reached from more than one state at time index “n”. For example, the state 0 can be reached from 0 or from 1. The metric for states 0, 1, 2, and 3 of trellis diagram  200  at time index “n+1” are given by γ 0 (n+1), γ 1 (n+1), γ 2 (n+1), and γ 3 (n+1), respectively. 
   In an embodiment, the state metrics γ 0 (n+1), γ 1 (n+1), γ 2 (n+1), and γ 3 (n+1) represent maximum metrics. The maximum metric for each state of trellis diagram  200  at time index “n+1” can be calculated using EQs. 1–4 below.
 
γ 0 ( n+ 1)=max[γ 0 ( n )+λ 00 ( n ),γ 2 ( n )+λ 20 ( n )]  EQ. 1
 
γ 2 ( n+ 1)=max[γ 1 ( n )+λ 12 ( n ),γ 3 ( n )+λ 32 ( n )]  EQ. 2
 
γ 1 ( n+ 1)=max[γ 0 ( n )+λ 01 ( n ),γ 2 ( n )+λ 21 ( n )]  EQ. 3
 
γ 3 ( n+ 1)=max[γ 1 ( n )+λ 13 ( n ),γ 3 ( n )+λ 33 ( n )]  EQ. 4
 
Where it is desired to identify the minimum metric for each state, the minimum (min) function can be used in place of the maximum (max) function in EQs. 1–4.
 
   As would be known to persons skilled in the relevant arts, the operation of a Viterbi decoder is often limited by speed bottlenecks found in add-compare-select circuits. These speed bottlenecks are created, for example, as a result of applying conventional design techniques to the recursive nature of add-compare-select operations. One technique that can be used to accelerate the operating speed of a Viterbi decoder is to use an N-step look-ahead network, where N is an integer greater than 0, to provide inputs to parallel processing pipelines. An advantage of using an N-step look-ahead network is that it will result in a fully connected trellis diagram such as the one illustrated in  FIG. 3 . 
     FIG. 3  illustrates a four-state trellis diagram  300  using 2-steps of look-ahead. EQ. 5 illustrates how to calculate the maximum path metric or state metric, γ 0 (n+2), for state 2 at a time index “n+2”.
 γ 0 ( n+ 2)=max[γ 0 ( n )+λ′ 00 ( n+ 1),γ 1 ( n )+λ′ 10 ( n+ 1),γ 2 ( n )+λ′ 20 ( n+ 1),γ 3 ( n )+λ′ 30 ( n+ 1)]  EQ. 5 
where λ′ ij (n) is the combined branch metric of the path i-j. The path metric, γ j (n+2), for the state “j” of trellis diagram  300  is given by EQ. 6.
 γ j ( n +2)=max j [γ i ( n )+λ ij ′( n )] ∀  i, j =0, 1, 2, 3  EQ.6 
Where it is desired to identify the minimum metric for each state, the minimum (min) function can be used in place of the maximum (max) function in EQ. 6.
 
     FIG. 4  illustrates state transitions for three time-steps of a trellis diagram  402  for a four-state Viterbi decoder. Trellis diagram  402  can be used, for example, to form the trellis diagram  300  illustrated in  FIG. 3 . As described herein, the minimum metric for the states 0, 1, 2, and 3 at time index “n+3” can be found using EQ. 7 below. The computations for the state metrics γ 0 (n+ 2 ), γ 1 (n+2), γ 2 (n+2), and γ 3 (n+2) are given by EQs. 8–11 below. The state metric for the state γ 0 (n+3) is given by EQ. 12 below. 
               ⁢     EQ   .           ⁢   7                       γ   j     ⁡     (     n   +   3     )       =       max   j     ⁢       [         γ   i     ⁡     (   n   )       +       λ   ij   ′     ⁡     (   n   )         ]     ⁢           ⁢     ∀   i           ,     j   =   0     ,   1   ,   2   ,   3                       ⁢     EQ   .           ⁢   8                     γ   0     ⁡     (     n   +   2     )       =     min   ⁡     [                 γ   0     ⁡     (   n   )       +     {         λ   00     ⁡     (   n   )       +       λ   00     ⁡     (     n   +   1     )         }       ,         γ   1     ⁡     (   n   )       +     {         λ   12     ⁡     (   n   )       +       λ   20     ⁡     (     n   +   1     )         }       ,                     γ   2     ⁡     (   n   )       +     {         λ   20     ⁡     (   n   )       +       λ   00     ⁡     (     n   +   1     )         }       ,         γ   3     ⁡     (   n   )       +     {         λ   32     ⁡     (   n   )       +       λ   20     ⁡     (     n   +   1     )         }               ]                           ⁢     EQ   .           ⁢   9                     γ   1     ⁡     (     n   +   2     )       =     min   ⁡     [                 γ   0     ⁡     (   n   )       +     {         λ   00     ⁡     (   n   )       +       λ   01     ⁡     (     n   +   1     )         }       ,         γ   1     ⁡     (   n   )       +     {         λ   12     ⁡     (   n   )       +       λ   21     ⁡     (     n   +   1     )         }       ,                     γ   2     ⁡     (   n   )       +     {         λ   20     ⁡     (   n   )       +       λ   01     ⁡     (     n   +   1     )         }       ,         γ   3     ⁡     (   n   )       +     {         λ   32     ⁡     (   n   )       +       λ   21     ⁡     (     n   +   1     )         }               ]                           ⁢     EQ   .           ⁢   10                     γ   2     ⁡     (     n   +   2     )       =     min   ⁡     [                 γ   0     ⁡     (   n   )       +     {         λ   01     ⁡     (   n   )       +       λ   12     ⁡     (     n   +   1     )         }       ,         γ   1     ⁡     (   n   )       +     {         λ   13     ⁡     (   n   )       +       λ   32     ⁡     (     n   +   1     )         }       ,                     γ   2     ⁡     (   n   )       +     {         λ   21     ⁡     (   n   )       +       λ   12     ⁡     (     n   +   1     )         }       ,         γ   3     ⁡     (   n   )       +     {         λ   33     ⁡     (   n   )       +       λ   32     ⁡     (     n   +   1     )         }               ]                           ⁢     EQ   .           ⁢   11                     γ   3     ⁡     (     n   +   2     )       =     min   ⁡     [                 γ   0     ⁡     (   n   )       +     {         λ   01     ⁡     (   n   )       +       λ   13     ⁡     (     n   +   1     )         }       ,         γ   1     ⁡     (   n   )       +     {         γ   13     ⁡     (   n   )       +       λ   33     ⁡     (     n   +   1     )         }       ,                     γ   2     ⁡     (   n   )       +     {         λ   21     ⁡     (   n   )       +       λ   13     ⁡     (     n   +   1     )         }       ,         γ   3     ⁡     (   n   )       +     {         γ   33     ⁡     (   n   )       +       λ   33     ⁡     (     n   +   1     )         }               ]                           ⁢     EQ   .           ⁢   12                     γ   0     ⁡     (     n   +   3     )       =     min   ⁡     [               γ   0     ⁡     (   n   )       +     min   ⁢     {                 λ   00     ⁡     (   n   )       +       λ   00     ⁡     (     n   +   1     )       +       λ   00     ⁡     (     n   +   2     )         ,                   λ   01     ⁡     (   n   )       +       λ   12     ⁡     (     n   +   1     )       +       λ   20     ⁡     (     n   +   2     )               }                       γ   1     ⁡     (   n   )       +     min   ⁢     {                 λ   12     ⁡     (   n   )       +       λ   20     ⁡     (     n   +   1     )       +       λ   00     ⁡     (     n   +   2     )         ,                   λ   13     ⁡     (   n   )       +       λ   32     ⁡     (     n   +   1     )       +       λ   20     ⁡     (     n   +   2     )               }                       γ   2     ⁡     (   n   )       +     min   ⁢     {                 λ   20     ⁡     (   n   )       +       λ   00     ⁡     (     n   +   1     )       +       λ   00     ⁡     (     n   +   2     )         ,                   λ   21     ⁡     (   n   )       +       λ   12     ⁡     (     n   +   1     )       +       λ   20     ⁡     (     n   +   2     )               }                       γ   3     ⁡     (   n   )       +     min   ⁢     {                 λ   32     ⁡     (   n   )       +       λ   20     ⁡     (     n   +   1     )       +       λ   00     ⁡     (     n   +   2     )         ,                   λ   33     ⁡     (   n   )       +       λ   32     ⁡     (     n   +   1     )       +       λ   20     ⁡     (     n   +   2     )               }               ]             
   The four-state trellis diagrams of  FIG. 3  and  FIG. 4  are provided for example only and not limitation. Based on the teachings described herein, persons skilled in the relevant arts will recognize that other multi-state N-step look-ahead configurations can be formed and implemented in accordance with the present invention. For example,  FIG. 5  illustrates an 8-state trellis diagram  502 , using 2-steps of look-ahead, formed from a trellis diagram  504 .  FIG. 6  illustrates an 8-state trellis diagram  602 , using 3-steps of look-ahead, formed from a trellis diagram  604 .  FIG. 7  illustrates a partial 8-state trellis diagram  702 , using 4-steps of look-ahead, formed from a trellis diagram  704 . 
     FIG. 8  illustrates a section of an example most-significant-bit (MSB) first ACS unit  800 . ACS unit  800  is used for processing 8-bit words. ACS unit  800  performs bit-wise operations. ACS unit  800  shows only one bit-slice out of N-slices, where N is the number of states in the Viterbi decoder. 
   As shown in  FIG. 8 , ACS unit  800  is formed from eight ACS circuits  802   a–h . Each ACS circuit  802  includes an adder  110 , a code converter  112 , and a maximum/minimum select (MS) circuit  114 . For each ACS circuit  802 , a feedback loop  804  couples a state metric output, γ 0,i (n+1), of MS circuit  114  to an input of adder  110 . A delay device  806  placed in each feedback path  804  delays the state metrics, γ 0,i (n+1), from reaching the input of adder  110  for a period of time (T). The eight ACS circuits  802   a–h  are interconnected as shown in  FIG. 8 . 
   In some embodiments of the invention, each adder  110  is replaced by two adders. A first adder is used to perform the carry computation shown in  FIG. 8 . The second adder is used to perform the sum computation shown in  FIG. 8 . 
   ACS unit  800  contains a number of loops or paths. These loops or paths are illustrated in  FIGS. 9A–C . 
     FIG. 9A  illustrates a loop  902 . Loop  902  includes adder  110   a , code converter  112   a , MS circuit  114   a , feedback path  804   a , and delay device  806   a . As shown in  FIG. 9A , in embodiments, MS circuit  114   a  comprises both a maximum/minimum select circuit (M)  904   a  and a decision logic circuit (D)  906   a . The decision logic circuit  906   a  is not included in loop  902 . Loop  902  is representative of other similar loops in ACS unit  800 . 
     FIG. 9B  illustrates a loop  910 . Loop  910  includes adder  110   b , code converter  112   a , decision logic circuit  906   a , maximum/minimum select circuit  904   b , feedback path  804   b , and delay device  806   b . As can be seen by comparing loop  910  to loop  902 , loop  910  includes more devices than loop  902 . Thus, the settling time of loop  910  following a change in branch metric inputs, λ 00,j (n), is longer than the settling time of loop  902 . Loop  902  is representative of other similar loops in ACS unit  800 . 
     FIG. 9C  illustrates a path  920  of ACS unit  800 . Path  920  is a critical path for ACS unit  920  (i.e., path  920  has the longest path settling time or operating time of any path in ACS unit  800  following a change in inputs). 
   As shown in  FIG. 9C , critical path  920  includes adder  110   a , code converter  112   a , and MS circuits  114   a–h . As can be seen from  FIG. 9C , the critical path  920  of ACS unit  800  will grow linearly with word-length if ACS unit  800  is used to process longer length words (e.g., word lengths of 16-bits, 32-bits, or 64-bits). ACS unit  800  can be retimed, however, to eliminate path  920  as the critical path of ACS unit  800 . 
     FIG. 10  illustrates four cut-sets  1002 ,  1004 ,  10006 , and  1008  that can be used to retime ACS unit  800 . The retiming of ACS unit  800  using the cut-sets  1002 ,  1004 ,  1006 , and  1008  leads to the circuit  1100  shown in  FIG. 11 . 
     FIG. 11  illustrates the retimed circuit  1100  formed from ACS unit  800 . The critical path of circuit  1100  is path  1102 . As shown in  FIG. 11 , path  1102  includes adders  110   b  and  110   c , code converters  112   a  and  112   b , MS circuits  114   a  and  114   b , and feedback path  804   b . The settling time of path  1102  is the settling time of two adders, two code converters, and two MS circuits. An advantage of the retimed circuit  1100  is that its critical path will not grow with word-length. 
   In a typical implementation, the computation time for an adder  110  is approximately 0.4 ns, the computation time for a code converter  112  is approximately 0.15 ns, and the computation time for an MS circuit  114  varies with the total number of states being implemented. For example, in a typical 8-state Viterbi decoder, the computation time for a MS circuit  114  is approximately 1.2 ns. A computation time of 1.2 ns is attributable to the decision logic circuit  906  and 0.8 ns is attributable to the maximum/minimum select circuit  904 . The maximum time of these two computation times is the computation time of MS circuit  114 . In a typical 4-state Viterbi decoder, the computation time for a MS circuit  114  is approximately 0.7 ns. This is because 0.7 ns is attributable to the decision logic circuit  906  and 0.4 ns is attributable to the maximum/minimum select circuit  904 . The increased computation time of the MS circuit  114  in an 8-state Viterbi decoder is due to the extra logic needed to select among a larger number of states. 
   Using the typical computation times stated above, the settling time of the critical path  1102  in  FIG. 11  (for an 8-state Viterbi decoder) is 3.1 ns. This time is the computation time of two adders  110  (0.4 ns+0.4 ns=0.8 ns), the computation time of two code converters 112 (0.15 ns +0.15 ns =0.3 ns), the computation time of one maximum/minimum select circuit  904  (0.8 ns), and the computation time of one decision logic circuit  906  (1.2 ns). This is greater than the loop bound of circuit  1100  (i.e., loop  910  shown in  FIG. 9B ), which is 2.55 ns (i.e., the computation time of one adder  110  (0.4 ns), the computation time of one code converter (0.15 ns), the computation time of one maximum/minimum select circuit  904  (0.8 ns), and the computation time of one decision logic circuit  906  (1.2 ns)). The loop bound of loop  910  is also the iteration bound of circuit  1100 . 
   Using the typical computation times stated above for a 4-state Viterbi decoder, the settling time of the critical path  1102  is 2.2 ns. This time is the computation time of two adders  110  (0.4 ns+0.4 ns=0.8 ns), the computation time of two code converters  112  (0.15 ns+0.15 ns=0.3 ns), the computation time of one maximum/minimum select circuit  904  (0.4 ns), and the computation time of one decision logic circuit  906  (0.7 ns). This is greater than the loop bound of a 4-state Viterbi decoder circuit (i.e., loop  910  shown in  FIG. 9B ), which is 1.65 ns (i.e., the computation time of one adder  110  (0.4 ns), the computation time of one code converter (0.15 ns), the computation time of one maximum/minimum select circuit  904  (0.4 ns), and the computation time of one decision logic circuit  906  (0.7 ns)). 
   Table 1 below summarizes the iteration bound times and the critical path times of a typical 4-state Viterbi decoder and a typical 8-state Viterbi decoder implemented using the circuits and methods described above. 
   
     
       
             
             
             
           
             
             
             
             
           
         
             
                 
               TABLE 1 
             
             
                 
                 
             
             
                 
               4-State Viterbi Decoder 
               8-State Viterbi Decoder 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
               Iteration 
               1.65 ns 
               2.55 ns 
             
             
                 
               Bound 
             
             
                 
               Critical 
                2.2 ns 
                3.1 ns 
             
             
                 
               Path 
             
             
                 
                 
             
           
        
       
     
   
   Using the circuits and methods of the invention described below, the critical path times shown in Table 1 can be further reduced. As described below, the present invention improves the retiming technique applied to ACS unit  800  to form circuit  1100  by pipelining the functions of the ACS unit. In this way, the ACS unit can be retimed to achieve a critical path time that is closer to the iteration bound. 
     FIG. 12  illustrates a detailed view of the critical path  1102  of circuit  1100 . 
   As shown in  FIG. 12 , during the retiming of ACS unit  800  described above, delay devices  806  were placed between decision logic circuit  906   a  and maximum/minimum select circuit  904   b  and between decision logic circuit  906   a  and between decision logic circuit  906   b . This is because the decision logic circuits  906  and the maximum/minimum select circuits  904  are conventionally not thought of and implemented as a single unit. This is also not so in accordance with the present invention. 
   As shown in  FIG. 13 , in accordance with the invention, decision logic device  906  can be divided into a first decision logic segment (d 1 )  1302  and a second decision logic segment (d 2 )  1304 . This division allows for pipelining of the decision logic computations in accordance with the invention. The first decision logic segment  1302  has a first computation time T d1 . The second decision logic segment  1304  has a second computation time T d2 . By dividing up decision logic circuit  906  into two segments  1302  and  1304 , it becomes possible to place a pipelining delay (e.g., a delay  806 ) between segment  1302  and segment  1304 . Placing a delay between the two segments  1302  and  1304  shortens the path  1102  formed during retiming of ACS unit  800 . This feature of the present invention is further described below with reference to  FIG. 14A  and  FIG. 14B . 
   The computation times T d1 , and T d2  represent the time required for each decision logic segment to perform its computation. In an embodiment of the present invention, the computation time T d2  is set equal to a propagation delay time (T). The propagation delay time (T) is used to ensure that the calculations performed by the decision logic segment  1304  are completed at approximately the same time as the calculations performed in the code converter  112 . Since decision logic segment  1304  and code converter  112  each provide an input to a decision logic segment  1302 , it is advantageous in embodiments to have these input values available for input to decision logic segment  1302  at approximately the same time. Thus, in embodiments, the decision logic segment  1304  is designed to have a computation time approximately equal to the computation time of an adder  110  and code converter  112  (i.e., 0.4 ns+0.15 ns=0.55 ns or approximately 0.6 ns). 
   Although  FIG. 13  illustrates dividing up decision logic circuit  906 , the invention is not limited to dividing up just decision logic circuit  906  to achieve pipelining and better retiming results. Decision logic circuit  906  was selected for division in  FIG. 13  because it had the longest computation time of the devices included in critical path  1102 . In accordance with the present invention, other devices, units, or circuits in the critical path can be divided to achieve pipelining and better retiming results. 
     FIG. 14A  illustrates a circuit  1400  formed from ACS unit  800  by dividing each of the decision logic circuits  906  of the MS circuits  114  into a first decision logic segment  1302  and a second decision logic segment  1304  as shown in  FIG. 13 . Four cut-sets  1402 ,  1404 ,  1406 , and  1408  are shown in  FIG. 14A . These four cut-sets are used to retime circuit  1400  and thereby form the circuit  1420  shown in  FIG. 14B . As can be seen in  FIG. 14A , the cut-set  1402  intersects the circuit branch between decision logic segment  1302   a  and decision logic segment  1304   a . The cut-set  1404  intersects the circuit branch between decision logic segment  1302   c  and decision logic segment  1304   c . The cut-set  1406  intersects the circuit branch between decision logic segment  1302   e  and decision logic segment  1304   e . The cut-set  1408  intersects the circuit branch between decision logic segment  1302   g  and decision logic segment  1304   g.    
     FIG. 14B  illustrates the retimed circuit  1420  formed from circuit  1400 . For the retimed circuit  1420 , the path  1422  includes adders  110   b  and  110   c , code converters  112   a  and  112   b , maximum/minimum select circuit  904   a , decision logic segment  1302   a , and feedback path  804   b . Using the typical computation times stated above for an 8-state Viterbi decode, the settling time of the path  1422  is approximately 2.5 ns. This time is the computation time of two adders  110  (0.4 ns +0.4 ns=0.8 ns), the computation time of two code converters  112  (0.15 ns+0.15 ns=0.3 ns), the computation time of one maximum/minimum select circuit  904  (0.8 ns), and the computation time of one decision logic segment  1302  (0.6 ns) (i.e., assuming segment  1304  has a computation time of 0.6 ns, the approximate computation time of an adder  110  and a code converter  112 ). This is less than the iteration bound of 2.55 ns (see loop  902  in  FIG. 9B ), thus path  1422  is no longer the critical path. 
   Two other paths present in circuit  1420  are path  1424  and path  1426 . Path  1424  includes two adders  110 , two code converters  112 , and two maximum/minimum select circuits  904 . Using the typical computation times stated above for an 8-state Viterbi decode, the settling time of the path  1424  is approximately 2.7 ns. This time is the computation time of two adders  110  (0.4 ns +0.4 ns=0.8 ns), the computation time of two code converters  112  (0.15 ns+0.15 ns=0.3 ns), and the computation time of two maximum/minimum select circuit  904  (0.8 ns+0.8 ns=1.6 ns). Path  1426  includes one decision logic segment  1304 , one adder  110 , code converter  112 , and two maximum/minimum select circuits  904 . Using the typical computation times stated above for an 8-state Viterbi decode, the settling time of the path  1424  is approximately 2.75 ns. This time is the computation time of one decision logic segment  1304  (0.6 ns), the computation time of one adder  110  (0.4 ns), the computation time of one code converter  112  (0.15 ns), and the computation time of two maximum/minimum select circuit  904  (0.8 ns+0.8 ns=1.6 ns). Thus, based on the above stated computation times, path  1424  is the critical path of circuit  1420 . 
   For the retimed circuit  1420 , using the typical computation times stated herein for a 4-state Viterbi decode, the settling time of the path  1424  is approximately 1.9 ns. This time is the computation time of two adders  110  (0.4 ns +0.4 ns=0.8 ns), the computation time of two code converters  112  (0.15 ns+0.15 ns=0.3 ns), and the computation time of two maximum/minimum select circuit  904  (0.4 ns+0.4 ns=0.8 ns). The settling time of the path  1424  is approximately 1.7 ns. This time is the computation time of one decision logic segment  1304  (0.35 ns or one-half of the total computation time (0.7 ns) of decision logic circuit  906 ), the computation time of one adder  110  (0.4 ns), the computation time of one code converter  112  (0.15 ns), and the computation time of two maximum/minimum select circuit  904  (0.4 ns+0.4 ns=0.8 ns). Based on these computation times, path  1424  is the critical path for a 4-state Viterbi decoder. 
   As would be known to persons skilled in the relevant arts, once the critical path of a circuit has been determined, a clock period for the circuit can be set equal to the settling time of the critical path plus a margin factor. 
   Table 2 below shows the iteration bound and critical path results for a 4-state Viterbi decoder and an 8-state Viterbi decoder designed in accordance with both the pipelining and retiming techniques of the present invention described herein. 
                                                 TABLE 2                       4-State Viterbi Decoder   8-State Viterbi Decoder                                        Iteration   1.65   2.55           Bound           Critical   1.9   2.75           Path                        
As shown in Table 2, the present invention achieves critical path computation times that are close to the iteration bound. Such computation times are not possible using conventional design techniques.
 
     FIG. 15  illustrates an example circuit  1500  that can be used to implement code converter  112  in embodiments of the invention. Circuit  1500  includes an AND gate  1502  and an OR gate  1504 . Circuit  1500  recodes input sum and carry bits as illustrated in Table 3 below. The digit (C, S) equals (1, 0) is not permitted. 
   
     
       
             
             
             
             
             
           
             
             
             
             
             
           
         
             
                 
               TABLE 3 
             
           
           
             
                 
                 
             
             
                 
               Original Bits 
                 
               Recoded Bits 
                 
             
           
        
         
             
               γ 
               γ C   
               γ S   
               γ C   r   
               γ S   r   
             
             
                 
             
             
               0 
               0 
               0 
               0 
               0 
             
             
               1 
               0 
               1 
               0 
               1 
             
             
               1 
               1 
               0 
               0 
               1 
             
             
               2 
               1 
               1 
               1 
               1 
             
             
                 
             
           
        
       
     
   
     FIG. 16  illustrates an example circuit  1600  for implementing MS circuit  114  in embodiments of the invention. Circuit  1600  performs bit-level maximum-select operations for a four-digit sequence {(C A , S A ), (C B , S B ), (C C , S C ), (C D , S D )}. 
   Circuit  1600  operates as follows. A maximum select circuit  1602  is used to select the maximum digit of the digits (C B , S B ), (C C , S C ), and (C D , S D . This maximum digit is shown in  FIG. 16  as (C i   MAX , S i   MAX ) The digit (C i   MAX , S i   MAX ) is passed to decision logic circuit  1604 . C i   MAX  is passed to OR gate  1606 . S i   MAX  is passed to OR gate  1608 . The digit (C A , S A ) is combined with a preliminary decision value d i   p,0  using AND gates  1610  and  1612  to produce a preliminary digit (C i   p , S i   p ). C i   p  is provided to OR gate  1606 . S i   p  is provided to OR gate  1608 . OR gates  1606  and  1608  are used to select the maximum digit (C i   0(n+1) , S i   0(n+1) ) of the two digits (C i   p , S i   p ) and (C i   MAX , S i   MAX ). The maximum digit (C i   0(n+1) , S i   0(n+1) ) is fed back to an adder  110  (not shown). 
   As shown in  FIG. 16 , decision state values d i   f,0  and d i   p,0  are used in the selection of maximum digit (C i   0(n+1) , S i   0(n+1) ), The value d i   f,0  is a final decision state value. The value d i   p,0  is a preliminary decision state value. When the values of the decision state values d i   f,0  and d i   p,0  equal (0, 0), the preliminary digit (C i   p, S i   p ) has lost in the comparison to digit (C i   MAX , S i   MAX ) to be selected as the maximum digit (C i   0(n+1) , S i   0(n+1) ). When the values of the decision state values d i   f,0  and d i   p,0  equal (0, 1), the preliminary digit (C i   p , S i   p ) still has the potential to be selected over the digit (C i   MAX , S i   MAX ) as the maximum digit (C i   0(n+1) , S i   0(n+1) ). When the values of the decision state values d i   f,0  and d i   p,0  equal (1, 1), the preliminary digit (C i   p , S i   p ) is winning the comparison to digit (C i   MAX , S i   MAX ) to be selected as the maximum digit (C i   0(n+1) , S i   0(n+1) ) The decision state values d i   f,0  and d i   p,0  may never equal (1, 0). 
   The inputs to the decision logic circuit  1604  include the values C i   MAX , S i   MAX , d i   f , d i   p , C i   f , and S i   f . The digit (C A , S A ) is combined with the final decision value d i   f,0  using AND gates  1614  and  1616  to produce the final digit value (C i   f , S i   f ). Using some or all of these inputs, decision logic circuit  1604  computes two decision state values d i−1   f,0  and d i−1   p,0 . 
     FIG. 17  illustrates an example circuit  1700  that can be used for the decision logic circuit  1604  shown in  FIG. 16 . Circuit  1700  includes three stages of 2-to-1 multiplexers. The first stage includes 2-to-1 multiplexers  1702   a ,  1702   b ,  1702   c  and  1702   d . The second stage includes 2-to-1 multiplexers  1704   a ,  1704   b , and  1704   c . The third stage includes 2-to-1 multiplexers  1706   a  and  1706   b . The inputs to the first stage of 2-to-1 multiplexers include C i   f , S i   f , and d i   p . The inputs to the second stage of 2-to-1 multiplexers include S i   MAX  and the outputs of the first stage of 2-to-1 multiplexers. The inputs to the third stage of 2-to-1 multiplexers include C i   MAX  and the outputs of the second stage of 2-to-1 multiplexers. 
   Circuit  1700  generates the two decision state values d i−1   f,0  and d i−1   p,0  in accordance with the mapping shown in Table 4 below. 
   
     
       
             
             
             
           
             
             
             
             
             
           
             
             
             
             
             
           
         
             
               TABLE 4 
             
           
           
             
                 
             
             
               Inputs 
               Outputs 
                 
             
           
        
         
             
               d i   p   
               d i   f   
               (C i   f , S i   f )–(C i   MAX , S i   MAX ) 
               d i-1   p   
               d i-1   f   
             
             
                 
             
           
        
         
             
               1 
               1 
               −2 
               0 
               0 
             
             
               1 
               1 
               −1 
               0 
               1 
             
             
               1 
               1 
               ≧0 
               1 
               1 
             
             
               0 
               1 
               ≦0 
               0 
               0 
             
             
               0 
               1 
               1 
               0 
               1 
             
             
               0 
               1 
               2 
               1 
               1 
             
             
               0 
               0 
               X 
               0 
               0 
             
             
                 
             
           
        
       
     
   
     FIG. 18  illustrates a circuit  1800  formed by applying the pipelining technique of the present invention to the circuit  1700 . As shown in  FIG. 18 , circuit  1800  includes four delays  1802 ,  1804 ,  1806 , and  1808 . Delay  1802  is located in the circuit branch connecting the output of 2-to-1 multiplexer  1702   a  to the input of 2-to-1 multiplexer  1704   a . Delay  1804  is located in the circuit branch connecting the output of 2-to-1 multiplexer  1702   c  to the inputs of 2-to-1 multiplexers  1704   a  and  1704   b . Delay  1806  is located in the circuit branch connecting the output of 2-to-1 multiplexer  1702   b  to the inputs of 2-to-1 multiplexers  1704   b  and  1704   c . Delay  1808  is located in the circuit branch connecting the output of 2-to-1 multiplexer  1702   d  to the input of 2-to-1 multiplexer  1704   c.    
   The four delays  1802 ,  1804 ,  1806 , and  1808  in circuit  1800  divide the circuit  1800  into part of a first decision logic segment  1820  and a second decision logic segment  1840 . The first decision logic segment  1820  includes the four 2-to-1 multiplexers  1702   a–d  (shown in  FIG. 18 ), the maximum select circuit  1602  (shown in  FIG. 16 ), and the two AND gates  1614  and  1616  (shown in  FIG. 16 ). Assume the computation time of each 2-to-1 multiplexer in circuit  1800  is approximately 0.2 ns. Further assume, the computation time of AND gates  1614  and  1616  are 0.2 ns each, and the computation time of maximum select circuit  1602  is 0.4 ns. Then, the operating time or critical path of decision logic segment  1820  is approximately 0.4 ns. The operating time of decision logic segment  1840  is also approximately 0.4 ns. 
     FIG. 19  illustrates a circuit  1900  formed by applying the pipelining technique of the present invention to the circuit  1600 . As shown in  FIG. 19 , circuit  1900  includes two delays  1902  and  1904 . Delay  1902  is located in the circuit branch that connect OR gate  1906  to the decision logic circuit  1604 . Delay  1904  is located in the circuit branch that connect OR gate  1908  to the decision logic circuit  1604 . 
     FIG. 20  illustrates a minimum-select circuit  2000  that can be used to implement a minimum-select embodiment of MS circuit  114 . Circuit  2000  operates as follows. A minimum select circuit  2002  is used to select the minimum digit of the digits (C B , S B ), (C C , S C ), and (C D , S D ). This minimum digit is shown in  FIG. 20  as (C i   MIN , S i   MIN ) The digit (C i   MIN , S i   MIN ) is passed to decision logic circuit  2004 . C i   MIN  is passed to AND gate  2006 . S i   MIN  is passed to AND gate  2008 . The digit (C A , S A ) is combined with a preliminary decision value d i   p,0  using OR gates  2010  and  2012  to produce a preliminary digit (C i   p , S i   p ). C i   p  is provided to AND gate  2006 . S i   p  is provided to AND gate  2008 . AND gates  2006  and  2008  are used to select the minimum digit (C i   0(n+1) , S i   0(n+1) ) of the two digits (C i   p ,S i   p ) and (C i   MIN , S i   MIN ). The minimum digit (C i   0(n+1) , S i   0(n+1) ) is fed back to an adder  110  (not shown). Features similar to those described above with reference to circuit  1600  are also found in circuit  2000 . 
     FIG. 21  illustrates an example circuit  2100  that can be used for the decision logic circuit  2004  shown in  FIG. 20 . Circuit  2100  includes three stages of 2-to-1 multiplexers. The first stage includes 2-to-1 multiplexers  2102   a ,  2102   b ,  2102   c  and  2102   d . The second stage includes 2-to-1 multiplexers  2104   a ,  2104   b , and  2104   c . The third stage includes 2-to-1 multiplexers  2106   a  and  2106   b . The inputs to the first stage of 2-to-1 multiplexers include C i   f , S i   f , and d i   p . The inputs to the second stage of 2-to-1 multiplexers include S i   MIN  and the outputs of the first stage of 2-to-1 multiplexers. The inputs to the third stage of 2-to-1 multiplexers include C i   MIN  and the outputs of the second stage of 2-to-1 multiplexers. 
   Circuit  2100  generates two decision state values d i−1   f,0  and d i−1   p,0  in accordance with the mapping shown in Table 5 below. 
   
     
       
             
             
             
           
             
             
             
             
             
           
             
             
             
             
             
           
         
             
               TABLE 5 
             
           
           
             
                 
             
             
               Inputs 
               Outputs 
                 
             
           
        
         
             
               d i   p   
               d i   f   
               (C i   f , S i   f )–(C i   MAX , S i   MAX ) 
               d i-1   p   
               d i-1   f   
             
             
                 
             
           
        
         
             
               1 
               1 
               2 
               0 
               0 
             
             
               1 
               1 
               1 
               0 
               1 
             
             
               1 
               1 
               ≦0 
               1 
               1 
             
             
               0 
               1 
               ≧0 
               0 
               0 
             
             
               0 
               1 
               −1 
               0 
               1 
             
             
               0 
               1 
               −2 
               1 
               1 
             
             
               0 
               0 
               X 
               0 
               0 
             
             
                 
             
           
        
       
     
   
     FIG. 22  illustrates a circuit  2200  formed by applying the pipelining technique of the present invention to the circuit  2100 . As shown in  FIG. 22 , circuit  2200  includes four delays  2202 ,  2204 ,  2206 , and  2208 . Delay  2202  is located in the circuit branch connecting the output of 2-to-1 multiplexer  2102   a  to the input of 2-to-1 multiplexer  2104   a . Delay  2204  is located in the circuit branch connecting the output of 2-to-1 multiplexer  2102   c  to the inputs of 2-to-1 multiplexers  2104   a  and  2104   b . Delay  2206  is located in the circuit branch connecting the output of 2-to-1 multiplexer  2102   b  to the inputs of 2-to-1 multiplexers  2104   b  and  2104   c . Delay  2208  is located in the circuit branch connecting the output of 2-to-1 multiplexer  2102   d  to the input of 2-to-1 multiplexer  2104   c.    
   The four delays  2202 ,  2204 ,  2206 , and  2208  in circuit  2200  divide the circuit  2200  into part of a first decision logic segment  2220  and a second decision logic segment  2240 . The first decision logic segment  2220  includes the four 2-to-1 multiplexers  2102   a–d  (shown in  FIG. 22 ), the minimum select circuit  2002  (shown in  FIG. 20 ), and the two AND gates  2014  and  2016  (shown in  FIG. 20 ). Assume the computation time of each 2-to-1 multiplexer in circuit  2200  is approximately 0.2 ns. Further assume, the computation time of AND gates  2014  and  2016  are 0.2 ns each, and the computation time of minimum select circuit  2002  is 0.4 ns. Then, the operating time or critical path of decision logic segment  2220  is approximately 0.4 ns. The operating time of decision logic segment  2240  is also approximately 0.4 ns. 
     FIG. 23  illustrates a circuit  2300  formed by applying the pipelining technique of the present invention to the circuit  2000 . As shown in  FIG. 23 , circuit  2300  includes two delays  2302  and  2304 . Delay  2302  is located in the circuit branch that connect AND gate  2306  to the decision logic circuit  2004 . Delay  2304  is located in the circuit branch that connect AND gate  2308  to the decision logic circuit  2004 . 
   Referring to  FIG. 24A  and  FIG. 24B , it has been observed that a number of common computations are used by the various decision logic circuits and the various maximum/minimum select circuits described herein. These decision logic circuits and maximum/minimum select circuits are represented in  FIG. 24A  by a decision logic circuit  2402  and a maximum/minimum select circuit  2404 . Accordingly, in an embodiment of the present invention, a preprocessing block  2406  is provided to calculate at least one common computation for use by the decision logic circuit  2402  and the maximum/minimum select circuit  2404 . This allows for the removal of at least some common hardware from decision logic circuit  2402  and the maximum/minimum select circuit  2404  to form the decision logic circuit  2408  and the maximum/minimum select circuit  2409  shown in  FIG. 24B . 
   As described herein, the present invention can be used to design and implement high-speed digital communications circuits and systems that cannot be designed and implemented using conventional circuits and techniques. This point is illustrated by the following example. 
   Consider, for a moment, how to implement a 10 Gb/s Viterbi decoder. As would be known to persons skilled in the relevant arts, in order to implement a 10 Gb/s Viterbi decoder some form of parallel Viterbi decoding using look-ahead or a sliding block Viterbi decoder is needed. In a conventional implementation, an 8-state Viterbi decoder requires a clock period of at least 3.4 ns. This is based on a 3.1 ns critical path and a clock setup/hold time of 0.3 ns. Unfortunately, this does not permit a 32-parallel design using conventional MSB-first pipelined operations because a 32-parallel design must be clocked with a clock period of 3.2 ns to achieve a decoding speed of 10 Gb/s. Thus, using conventional circuits and design techniques, a 10 Gb/s Viterbi decoder must be implemented using either a 64-parallel design in a look-ahead Viterbi decoder or a 48-parallel design in a sliding-block Viterbi decoder. In a look-ahead parallel Viterbi decoder, the level of parallelism is constrained to be a power of two (e.g., 2 x ). In a sliding-block Viterbi decoder, the level of parallelism is assumed to be a multiple of eight (e.g., 8×). 
   Using the circuits and methods of the present invention described herein, an 8-state Viterbi decoder can be implemented that has a critical path of only 2.7 ns. How this is achieved is described above. Thus, using a clock setup/hold time of 0.3 ns, an 8-state Viterbi decoder designed and implemented in accordance with the present invention can be clocked with a clock period of 3 ns. In this way, a 32-parallel implementation for achieving a 10 Gb/s Viterbi decoder is feasible. 
   Further features and advantages of the present invention will become apparent to persons skilled in the relevant arts given the description herein. 
   CONCLUSION 
   Various embodiments of the present invention have been described above. 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 arts 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.

Technology Category: h