Patent Publication Number: US-7218138-B2

Title: Efficient implementations of the threshold-2 function

Description:
FIELD OF THE INVENTION 
   The present invention relates to second monotone symmetric operations generally and, more particularly, to an efficient implementation of a threshold-2 function. 
   BACKGROUND OF THE INVENTION 
   A threshold-2 (or second threshold) function (i.e., T 2 ) has practical usage, particularly in content addressable memory (CAM) applications where the second threshold function can be used as part of a multiple match detector. A value generated by a second threshold function indicates whether more than one argument of the function is non-zero. The second threshold function is expressed by equation 1, shown in  FIG. 1 , where each of X 1  through X N  is a binary (i.e., 0 or 1) input argument. In terms of logical AND operations and logical OR operations, the second threshold function in equation 1 is expressed by equation 2, shown in  FIG. 1 . A standard method of implementation for T 2  is based on expansions shown in equations 3 through 5, also shown in  FIG. 1 . The standard method consists of a hierarchical set of units simultaneously implementing both functions T 1  and T 2 . 
   Referring to  FIG. 2 , a block diagram of a conventional 2-input unit  10  is shown. The Z 2  unit (or circuit)  10  consists of just two logic gates, a logical OR gate  12  and a logical AND gate  14 . Input signals X 1  and X 2  are applied to each of the logic gates  12  and  14 . Output signals T 1  and T 2  are generated by the logic gates  12  and  14 , respectively. 
   Referring to  FIG. 3 , a block diagram of a conventional N-input unit  20  is shown. Equations 3 and 4 suggest that a Z N  unit (or circuit)  20  can be implemented using (i) two logical units  22  and  24  and (ii) four logic gates  26 ,  28 ,  30  and  32 . The logic unit  22  (i.e., Z L  unit) implements both the T 1  and the T 2  functions for L input signals X 1  through XL (i.e., values X 1  through X L ). The logic unit  24  (i.e., Z N−L  unit) implements both the T 1  and the T 2  functions for the N−L input signals X(L+1) through XN (i.e., values X L+1  through X N ). 
   Starting with the Z 2  unit and recursively applying the decomposition shown just above can be used to construct Z N  units, for N=4, 8 and 16 inputs, using respectively 2×2+4=8, 2×8+4=20 and 2×20+4=44 logic gates. Generally, 3N−4 logic gates are used in a conventional design, where N is the number of inputs. A delay, measured as maximum number of logic gates along paths from the input signals X 1  through XN to the output signals T 1  and T 2  is one delay time for a Z 2  unit, three delay times for a Z 4  unit, five delay times for a Z 8  unit and seven delay times for a Z 16  unit. Generally, the delay for the conventional method may be expressed by equation 6, shown in  FIG. 1 . 
   Referring to  FIG. 4 , a block diagram of a conventional 16-input unit  50  is shown. The Z 16  unit  50  consists of multiple logical OR gates and multiple logical AND gates. The numbers at the inputs and/or outputs to each of the logical gates represent delays from the input signals X 1  through X 16 , assuming that all of the input signals X 1  through X 16  arrive and/or change simultaneously and no wire delay is taken into consideration. A longest input-to-output path in the Z 16  unit  50  goes from the input signal X 16  to the output signal T 2  and has a delay equal to seven. Many of the logic gates have non-synchronous inputs, that is, inputs with (essentially) different signal arrive times. 
   SUMMARY OF THE INVENTION 
   The present invention concerns a circuit and a method for operating the circuit. A first step of the method generally comprises generating a plurality of first intermediate signals in two parallel first operations each responsive to a respective half of a plurality of input signals. A second step involves generating a plurality of result signals in a plurality of first logical operations each responsive to at most two of the first intermediate signals. A third step includes generating a first output signal as a particular one of the result signals, wherein a first delay from the first intermediate signals to the first output signal is at most through one logical gate. A fourth step of the method generally comprises generating a second output signal for a second threshold function in a logical OR operation of the result signals except for the particular one result signal. 
   The objects, features and advantages of the present invention include providing an efficient implementation of a second threshold function that may (i) reduce logical gate delays compared to conventional designs and/or (ii) reduce a number of logical gates compared to a conventional design. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
       FIG. 1  is a set of formulae; 
       FIG. 2  is a block diagram of a conventional 2-input unit; 
       FIG. 3  is a block diagram of a conventional N-input unit; 
       FIG. 4  is a block diagram of a conventional 16-input unit; 
       FIG. 5  is a block diagram of an example implementation of a 16-input circuit; 
       FIG. 6  is a block diagram of an example implementation of a 2-input circuit in accordance with a preferred embodiment of the present invention; 
       FIG. 7  is a block diagram of an example implementation of a 4-input circuit; 
       FIG. 8  is a block diagram of an example implementation of an 8-input circuit; 
       FIG. 9  is a block diagram of an example implementation of a 16-input circuit; 
       FIG. 10  is a set of formulae; 
       FIG. 11  is a diagram for a grouping of input signals; 
       FIG. 12  is a block diagram of an example layout for a 1-input unit; 
       FIG. 13  is a block diagram of an example layout for a 2-input unit; 
       FIG. 14  is a block diagram of an example layout for a 4-input unit; 
       FIG. 15  is a block diagram of an example layout for an 8-input unit; 
       FIG. 16  is a block diagram of an example layout for a 16-input unit; 
       FIG. 17  is a diagram of an example logic structure; 
       FIG. 18  is a block diagram of an example implementation of another 16-input circuit; and 
       FIG. 19  is a table comparing a delay and a number of logic gates for conventional implementations and the present invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The present invention generally comprises generating a plurality of first intermediate signals, where a first one of the intermediate signals may represent a value of a function T 1 . A conjunction of the remaining intermediate values may represent another value of a second threshold function T 2 . Another step generally involves generating an output signal representing the value of T 2 . The step of generating the intermediate signals generally contains sub-steps for recursively generating internal intermediate signals similar to the intermediate signals for a respective halves of input signals and combining the internal intermediate signals using 2-input logic gates into the intermediate signals, thus adding a unit of delay. 
   Referring to  FIG. 5 , a block diagram of an example implementation of a circuit  100  is shown. The circuit (or system)  100  may be operational to implement the second threshold function for N=16 inputs, similar to the Z 16  unit  50  of  FIG. 4 . The circuit  100  may generally be implemented in more synchronized way than the Z 16  unit  50 . 
   The circuit  100  may be distinguished from the Z 16  unit  50  in that pairs of signals with a least delay may be grouped. One or more logical OR gates may further operate on the grouped signal pairs. The grouped signal pairs may then be replaced by output signals generated by the logic gates. The output signals may be grouped with signals having a next-least delay, and so on. For example, a highlighted part  102  of the circuit  100  generally has five logic gates having inputs with delays of 3, 3, 4, 4 and 4 logic gate delays. A logic gate  104  may combine signals having delays of 3 thus generating a delay of 4. Logic gate  106  and  108  may combine signals having delays of 4 to generate two sets of signals each having a delay of 5. Finally, a logic gate  110  may combine the signals having delays of 5 to generate a signal with a total delay of 6. The delay value of 6 units may be a single delay unit less than as originally illustrated in  FIG. 4 . 
   Implementation of a netlist generally having N=2 n  inputs (wherein n is an integer) may also be described using an hierarchical construction process. A netlist with the N inputs and 2 outputs may be considered as combination of two major blocks (i) a Y N  module (see  FIG. 6 ) with N inputs and n+1 outputs and (ii) an n-input balanced OR-tree. Y 2  modules, Y 4  modules, Y 8  modules and such, may be designed using of recursive process. The recursive process generally starts from a Y 2  module with 2 gates, 2 outputs and depth (delay) equal to 1 (where “1” may represent a number of logic gates from an input to an output and/or a maximum propagation time from the input to the output, with each logic gate generally contributing a unit of propagation time). A Y 4  module generally has 2×2+3=7 gates, 3 outputs and a depth (delay) equal to 2 (e.g., a depth of 2 logic gates and/or a propagation time of 2 units). A Y 8  module generally has 2×7+4=18 gates, 4 outputs and a depth (delay) equal to 3. A Y 16  module generally has 2×18+5=41 gates, 5 outputs and a depth (delay) equal to 4, and so on. 
   Referring to  FIG. 6 , a block diagram of an example implementation of a 2-input circuit (or system)  120  is shown in accordance with a preferred embodiment of the present invention. The circuit  120  generally comprises a circuit (or module)  122 A and a circuit (or module)  124 A. A signal (e.g., X 1 ) may be received at an input  126  of the circuit  122 A carrying a value X 1 . A signal (e.g., X 2 ) may be received at an input  128  of the circuit  122 A carrying a value X 2 . An output  130  of the circuit  122 A may present a signal (e.g., T 1 A) carrying a value T 1A . An output  132  of the circuit  122 A may present a signal (e.g., RA) carrying a value R A  to an input  132  of the circuit  124 A. The circuit  124 A may have an output  136  to present a signal (e.g., T 2 A) carrying a value T 2A . In general, a signal “Xyz” may have a value of X yz . 
   The circuit  120  may be operational to perform a second threshold (threshold-2 or second monotone symmetric) function (or operation) using the two signals X 1  and X 2  to supply input arguments. The circuit  122 A may be referred to as a Y 2  module (or unit). The Y 2  module  122 A may be operational to perform the functions as expressed by equations 2 and 3. The circuit  124 A may be referred to as an 1-input tree module. The 1-input tree module  124 A may have a simple design in which the signal RA is passed from the input  134  to the output  136  unaltered to present the signal T 2 A (e.g., T 2 A=RA). 
   The Y 2  unit  120  generally comprises a logic gate  138 A and a logic gate  140 A. Both logic gates  138 A and  140 A may be implemented as two-input logic gates. The logic gate  138 A may be operational to perform a logical OR operation of the input signals X 1  and X 2 . The logic gate  140 A may be operational to perform a logical AND operation of the input signals X 1  and X 2 . The logical OR gate  138 A may present the signal T 1 A. The logical AND gate  140 A may present the signal RA. A propagation delay from a change in one or more of the input signals X 1  and X 2  to a change in the output signals T 1 A and T 2 A may be at most a single delay unit (e.g., the delay through the logical gates  140 A and  138 A as the 1-input tree module  124 A introduces virtually no delay. 
   The signals T 1 A and T 2 A may carry results of a second threshold function. The signal RA may represent an intermediate result from the Y 2  module  122 A. Each of the signal X 1 , X 2 , RA, T 1 A and T 2 A may be implemented as a binary logic signal having a boolean one (or true) state and a boolean zero (or false) state. A delay from the input signals X 1  and X 2  and the output signals T 1 A and T 2 A may be at most a single delay unit long. 
   Referring to  FIG. 7 , a block diagram of an example implementation of a 4-input circuit (or system)  150  is shown. The circuit  150  may be operational to perform a second threshold function using multiple signals (e.g., X 1  through X 4 ) to convey input arguments. The circuit  150  generally comprises a circuit (or module)  122 B and a circuit (or module)  124 B. The input signals X 1  through X 4  may be received by the module  122 B. A first output signal (e.g., T 1 B) may be generated by the module  122 B. A second output signal (e.g., T 2 B) may be generated by the module  124 B. Two result signals (e.g., RB 1  and RB 2 ) may be generated by the module  122 B and received by the module  124 B. The signals T 1 B and T 2 B may be representative results of a second threshold function. 
   The module  122 B may be referred to as a Y 4  module. The Y 4  module generally comprises two of the Y 2  modules (e.g.,  122 A 1  and  122 A 2 ), a logic gate  138 B, a logic gate  140 B and a logic gate  152 . The logic OR gate  138 B may be configured to generate the first output signal T 1 B by performing a logical OR operation of multiple intermediate signals (e.g., T 1 A 1  and T 1 A 2 ), similar to the logical OR gate  138 A in  FIG. 6 . The logical AND gate  140 B may be configured to generate a result signal (e.g., RA 2 ) by performing a logical AND operation of the intermediate signals T 1 A 1  and T 1 A 2 , similar to the logical AND gate  140 A in  FIG. 6 . The logical OR gate  152  may be configured to generate another result signal (e.g., RB 2 ) by performing a logical OR operation of multiple intermediate signals (e.g., RA 1  and RA 2 ). A delay from the intermediate signals T 1 A 1  and T 1 A 2  to the first output signal TB 1  may be at most a single delay unit long. 
   The module  124 B may be referred to as a 2-input tree module. The 2-input tree module  124 B generally comprises a logic gate  154 . The logic OR gate  154  may be configured to generate the second output signal T 2 B by performing a logical OR operation on the result signals RB 1  and RB 2 . A delay from the intermediate signals T 1 A 1  and T 1 A 2  to the second output signal T 2 B may be at most two delay units long, (i) a first logic gate delay through the parallel logic gates  140 B and  152  and (ii) a second logic gate delay through the logic gate  154 . 
   Referring to  FIG. 8 , a block diagram of an example implementation of a 8-input circuit (or system)  160  is shown. The 8-input circuit  160  may be operational to perform a second threshold function using multiple signals (e.g., X 1  through X 8 ) as input arguments. The circuit  160  generally comprises a circuit (or module)  122 C and a circuit (or module)  124 C. The input signals X 1  through X 8  may be received by the module  122 C. A first output signal (e.g., T 1 C) may be generated by the module  122 C. A second output signal (e.g., T 2 C) may be generated by the module  124 C. Three result signals (e.g., RC 1 , RC 2  and RC 3 ) may be generated by the module  122 C and received by the module  124 C. The output signals T 1 C and T 2 C may be representative results of a second threshold function. 
   The module  122 C may be referred to as a Y 8  module. The Y 8  module  122 C generally comprises two of the Y 4  modules (e.g.,  122 B 1  and  122 B 2 ), a logic gate  138 C, a logic gate  140 C, a logic gate  162  and a logic gate  164 . The logic gate  138 C may be configured to generate the first output signal T 1 C in response to a logical OR operation of two intermediate signals (e.g., T 1 B 1  and T 1 B 2 ) received from the Y 4  modules, similar to the logic circuit  138 B in  FIG. 7 . The logic gate  140 C may be configured to generate the first result signal RC 1  in response to a logical AND operation of the two intermediate signals T 1 B 1  and T 1 B 2 . The logic gate  162  may be configured to generate intermediate signal RC 2  in response to a logical OR operation of two intermediate signals (e.g., RB 11  and RB 12 ) received from the Y 4  module  122 B 1 . The logic gate  164  may be configured to generate the intermediate signal RC 3  in response to a logical OR operation of two intermediate signals (e.g., RB 21  and RB 22 ) received from the Y 4  module  122 B 2 . A delay from the intermediate signals T 1 B 1  and T 1 B 2  to the first output signal T 1 C may be at most one delay. 
   The module  124 C may be referred to as a 3-input tree module. The 3-input tree module  124 C generally comprises a logic gate  166  and a logic gate  168 . The logic gates  166  and  168  may be configured to generate the second output signal T 2 C by performing a logical OR operation on the result signals RC 1 , RC 2  and RC 3 . In one embodiment, the 2-input logic OR gates  166  and  168  may be replaced by a single 3-input logic OR gate. A delay from the intermediate signals T 1 B 1 , T 1 B 2 , RB 11 , RB 12 , RB 21  and RB 22  to the second output signal T 2 C may be at most three delays. 
   Referring to  FIG. 9 , a block diagram of an example implementation of a 16-input circuit (or system)  170  is shown. The 16-input circuit  170  may be operational to perform a second threshold function using multiple signals (e.g., X 1  through X 16 ) as input arguments. The circuit  170  generally comprises a circuit (or module)  122 D and a circuit (or module)  124 D. The input signals X 1  through X 16  may be received by the module  122 D. A first output signal (e.g., T 1 D) may be generated by the module  122 D. A second output signal (e.g., T 2 D) may be generated by the module  124 D. Four result signals (e.g., RD 1 , RCD 2 , RD 3  and RD 4 ) may be generated by the module  122 D and received by the module  124 D. The output signals T 1 D and T 2 D may be representative results of a second threshold function. 
   The module  122 D may be referred to as a Y 16  module. The Y 16  module  122 D generally comprises two of the Y 8  modules (e.g.,  122 C 1  and  122 C 2 ), a logic gate  138 D, a logic gate  140 D, a logic gate  172 , a logic gate  174  and a logic gate  176 . The logic gate  138 D may be configured to generate the first output signal T 1 D in response to a logical OR operation of two intermediate signals (e.g., T 1 C 1  and T 1 C 2 ) received from the Y 8  modules  122 C 1  and  122 C 2 . The logic gate  140 D may be configured to generate the first result signal RD 1  in response to a logical AND operation of the two intermediate signals T 1 C 1  and T 1 C 2 . The logic gate  172  may be configured to generate intermediate signal RD 2  in response to a logical OR operation of two intermediate signals (e.g., RC 11  and RC 21 ) received from the Y 8  module  122 C 1 . The logic gate  174  may be configured to generate the intermediate signal RD 3  in response to a logical OR operation of an intermediate signal (e.g., RC 31 ) received from the Y 8  module  122 C 1  and an intermediate signal (e.g., RC 12 ) received from the Y 8  module  122 C 2 . The logic gate  176  may be configured to generate the intermediate signal RD 4  in response to a logical OR operation of two intermediate signals (e.g., RC 22  and RB 32 ) received from the Y 8  module  122 C 2 . A delay from the intermediate signals T 1 C 1 –T 1 C 2  to the first output signal T 1 D may be at most one delay. 
   The module  124 D may be referred to as a 4-input tree module. The 4-input tree module  124 D generally comprises a logic gate  178 , a logic gate  180  and a logic gate  182 . The logic gates  178 ,  180  and  182  may be configured to generate the second output signal T 2 D by performing a logical OR operation on the result signals RD 1 , RD 2 , RD 3  and RD 4 . In one embodiment, the 2-input logic OR gates  178 ,  180  and  182  may be replaced by a single 4-input logic OR gate. A delay from the intermediate signals T 1 C 1 , T 1 C 2 , RC 11 , RC 12 , RC 13 , RC 21 , RC 22  and RC 32  to the second output signal T 2 D may be at most four logic gate delays. 
   In general, a Y 2k  module may be built from two Y k  modules and 2+[ log 2 k] extra logic gates (e.g., a logical AND gate and one or more logical OR gates), where [x] generally means rounding up to a nearest integer. The first output signals of both Y k  modules may be connected by a logical OR gate and a logical AND gate to present a first output signal T 1  and a first result signal R, respectively. A total of [ log 2 k] additional 2-input logical OR gates may be included in the Y 2k  module to generate additional results signals from intermediate signals presented by the Y k  modules. Grouping of the intermediate signals (with an exception of the first output signals) may be in any order. Placement consideration generally hint that probably combining geometrically neighboring signals is preferred. 
   For N=2 n , (where n is an integer) a Y N  module may have 3N−n−3 gates, n+1 outputs and a depth (delay) of at most n from the input signals X 1  through XN to the second output signal T 2 . A first (e.g., top) output of the Y N  module generally implements the function T 1  whereas the function T 2  may be obtained by a logical OR operation of the remaining n outputs. Therefore, computing pair (T 1 , T 2 ) may be accomplished with 3N−n−3+(n−1)=3N−4 logical gates (the same number of logical gates as for conventional methods), but with maximum depth (depth) of only n+log 2 n (rounded up), where the term log 2 n generally reflects the delay through the n-input tree module. 
   The same depth (delay) may be achieved with about one-third less logic gates by recursively applying an expansion as follows. Considering the function T 2  with MN variables X ij  marked by pairs of indices, i and j, where 1≦i≦M and 1≦j≦N. Let A i  be expressed by equation 8 and B j  be expressed by equation 9, shown in  FIG. 10 . Therefore, an expansion in equation 11 generally takes place, and may be directly proven in the following way. 
   If all variables are zeros, then all A i  and B j  are zeros and the right-hand part in equation 11 also equals zero. If only one variable (e.g., X ij ) exists with a value of one, then only A i  and B j  will have non-zero values and the right-hand part in equation 11 again equal zero. 
   Consider a situation having at least two non-zero variables, for example X ij  and X pq . Equalities i=p and j=q cannot be simultaneously satisfied. If i differs from p, then A i  and A p  are both equal to one and the value of T 2 (A 1 , . . . , A M ) equals one. In another case where i=p, then j and q are distinct. Therefore, B j  and B q  are both equal to one and the value of T 2 (B 1 , . . . , B N ) equals one. In both cases, the right-hand part in equation 11 equals one, completing the proof of equation 11. 
   An implementation complexity for the function T 2  may be estimated. Using a standard notation: S(C) is the complexity size, number of gates of circuit C, S B  (T 2 ) is the complexity size, number of gates of the function T 2  over basis B (e.g., the complexity of minimal circuit over B implementing T 2 ). If the basis is not explicitly mentioned, assume {AND, OR}. 
   Using equation 11, an estimation for S(T 2 (X 11 , . . . , X MN )) is generally provided in formula 12, as shown in  FIG. 10 . Generally, a total gate count of the present invention includes (i) M expressions A i , (ii) N expressions B j , (iii) an M-argument threshold-2 function, (iv) an N-argument threshold-2 function and (v) a disjunction gate (OR), thus giving the estimation shown in formula 12 (the above mentioned conventional design was assumed for parts (iii) and (iv), the gate count for the conventional design of an n-input function T 2  equals 3n−4). 
   In a case M=N and n=NM, a sum in the equation 11 is 2n+o(n). Note that the same is also true for any n, because substitution of a zero value for one variable of an n-argument function T 2  also produces an (n−1)-argument function T 2  with the complexity decreased. It may be noted that a netlist produced by the above method is generally a best possible one (asymptotically) in the monotone basis {AND, OR} and in the basis B containing all possible 2-input logic gates. 
   Designing an optimized netlist for MN-input function T 2  (actually, for both T 2  and T 1 ; if T 1  is not utilized, then the gate count may be reduced by 1) generally starts with computing M+N intermediate values using MN variables X ij , 1≦i≦M, 1≦j≦N, per equations 7 through 11 as shown in  FIG. 10 . The expansion formulae generally show that a depth D(N) and a size (e.g., number of logic gates) S(N) of netlists computing pair of R-input functions T 1  and T 2  satisfy inequalities 13 and 14 shown in  FIG. 10 . The “−1” at the end of inequality 14 may be included because only one of T 1 (A) and T 1 (B) may be used for computing MN-input function T 2 , so at least one logic gate may be removed. 
   Starting with D(2)=1 and S(2)=2, estimations may be made per formulae 15 through 17. In general, for N=2 n  (where n=2 k ) input variables estimations may be expressed by formulae 18 and 19, as shown in  FIG. 10 . The depth estimation will generally still be the same even if N=2 n  is not such that n=2 k , S(N) for any N=2 n  may be estimated per formula 20. 
   The netlist should have careful placement, because straightforward placement may result in too many long and mutually crossing nets. Note that the valuable parts may be calculations of the intermediate signals Ai and Bj. A better solution may involve recursive grouping of the input signals like as shown in  FIG. 11  and creation of the corresponding part of a netlist as a hierarchy of units of the form U 1 , U 2 , U 4 , U 8 , . . . , where a U k  unit has k=pq inputs and p+q outputs, where p=q or p=2q. For example, the two inputs of a 2-input unit U 2  may be considered as if arranged in a column (e.g., X 12  and X 22 ). The four inputs of a 4-input unit U 4  may be considered as if arranged in a square (e.g., X 21 , X 32 , X 41  and X 42 ). The eight inputs of an 8-input unit U 8  may be considered as if arranged in a rectangle (e.g., X 13 , X 14 , X 23 , X 24 , X 33 , X 34 , X 43  and X 44 ), and so on. 
   Referring to  FIG. 12 , a block diagram of an example layout for a 1-input unit  200 A is shown.  FIG. 12  may be applied to each individual variable in  FIG. 11 . The unit  200 A may be referred to as a U 1  unit. Layout of the U 1  unit  200 A may be simple. The U 1  unit  200 A generally comprises an input signal (e.g., X) and two output signals (e.g., A and B) physically displaced from each other and the input signal X. 
   Referring to  FIG. 13 , a block diagram of an example layout for a 2-input unit  200 B is shown.  FIG. 13  may combine pairs of  FIG. 12  for each cell. The unit  200 B may be referred to as a U 2  unit. The U 2  unit  200 B generally has 2×1=2 inputs and 2+1=3 outputs. The U 2  unit  200 B generally comprises two U 1  units (e.g.,  200 A 1  and  200 A 2 ) and a logic gate  202 . The output All may be presented by the U 2  unit  200 B directly from the U 1  unit  200 A 1 . The output A 12  may be presented by the U 2  unit  200 B directly from the U 1  unit  200 A 2 . The logic gate  202  may generate an output (e.g., B 2 ) in response to a logical OR operation of an output (e.g., B 11 ) from the U 1  unit  200 A 1  and another output (e.g., B 12 ) from the U 1  unit  200 A 2 . 
   Referring to  FIG. 14 , a block diagram of an example layout of a 4-input unit  200 C is shown. The unit  200 C may be referred to as a U 4  unit. The U 4  unit generally comprises two U 2  units (e.g.,  200 B 1  and  200 B 2 ), a logic gate  204  and a logic gate  206 . The U 4  unit generally has 2×2=4 inputs and 2+2=4 outputs. The “B” outputs from the U 2  units may be directly presented by the U 4  unit. Pairs of the “A” outputs from the U 2  units may be combined by the logic OR gates  204  and  206 . 
   Referring to  FIG. 15 , a block diagram of an example layout of an 8-input unit  200 D is shown. The unit  200 D may be referred to as a U 8  unit. The U 8  unit generally comprises two U 4  units (e.g.,  200 C 1  and  200 C 2 ), a logic gate  208  and a logic gate  210 . The U 8  unit generally has 4×4=16 inputs and 4+2=6 outputs. The “A” outputs from the U 4  units may be directly presented by the U 8  unit. Pairs of the “B” outputs from the U 4  units may be combined by the logic OR gates  208  and  210 . 
   Referring to  FIG. 16 , a block diagram of an example layout of a 16-input unit  200 E is shown. The unit  200 E may be referred to as a U 16  unit. The U 16  unit generally comprises two U 8  units (e.g.,  200 D 1  and  200 D 2 ), a logic gate  212 , a logic gate  214 , a logic gate  216  and a logic gate  218 . The U 16  unit generally has 24×4=16 inputs and 4+4=8 outputs. The “B” outputs from the U 8  units may be directly presented by the U 16  unit unchanged. Pairs of the “A” outputs from the U 8  units may be combined by the logic OR gates  212 – 218 . 
   Larger units may be generated in the same pattern as the above units. In each successive step, (i) logical OR operations may be performed in a first (bottom-top-bottom-top-etc. . . ) group of outputs of subunits and (ii) a second (top-bottom-top-bottom-etc. . . ) group may remain untouched. 
   In the present invention, 2-input logic gates may be replaced (if appropriate and/or improves timing and/or area) by 3-input, 4-input or logic gates with larger fan-in. Using larger inputs logic gates generally results in modifications to the signal groupings by 3, 4, etc., instead of grouping by 2, as shown above. 
   All netlists proposed above generally use only AND and OR logic gates. Furthermore, almost all (with the exception of a few logic gates near outputs) gates of the netlists are generally such that both inputs have the same depth from the primary inputs. Having the same depth makes possible use of faster and smaller NAND and NOR gates instead of AND and OR gates while adding only a few extra NOT gates and not more than a single unit of delay (actually compensated by the smaller value of the unit). A standard transformation method generally includes: 
   1) Assign each logic gate to a set called “layer 1”, “layer 2”, “layer 3”, etc.: if a longest path from primary inputs to the output of the logic gate passes through K gates, then the logic gate belongs to the Kth layer. 
   2) If the input of Kth layer logic gate is driven by an output of Lth layer logic gate, where K−L is an even number, then one buffer (or an odd number R of buffers, where R&lt;K−L) is inserted between the Kth layer logic gate and the Lth layer logic gate. 
   3) In the same way, if the input of a Kth layer logic gate (where K is even) is driven by a primary input, one buffer (or and odd number R of buffers, where R&lt;K) is inserted between the primary input and the Kth layer logic gate. 
   4) If outputs of a netlist are driven by logic gates from layers 1, 3, 5, etc., insert an extra buffer before each such output. 
   5) For layers number 1, 3, 5, etc., replace all AND, OR and BUF logic gates with NAND, NOR, and NOT logic gates, respectively. 
   6) For layers number 2, 4, 6, etc., replace all AND, OR and BUF logic gates with NOR, NAND and NOT logic gates, respectively. 
   The present invention may further comprise steps of (i) logically organizing input signals into a two-dimensional grid or matrix, (ii) generating first intermediate signals representing disjunctions (OR) for each row of the matrix, (iii) generating second intermediate signals representing disjunctions (OR) for each column of the matrix, (iv) generating third intermediate signals representing a value of T 2  with the first intermediate signals as inputs, (v) generating fourth intermediate signals representing a value of T 2  with the second intermediate signals as inputs, (vi) generating an output value by a single OR-gate that takes the third and the fourth intermediate signals as inputs. Sub-steps (iv) and (v) may be implemented recursively applying the same method, or (if there are only a few intermediate inputs) by a conventional method. 
   Referring to  FIG. 17 , a diagram of an example logic structure  220  is shown. The logic structure  220  generally comprises a matrix  222 , a block (or module)  224 , a block (or module)  226 , a block (or module)  228 , a block (or module)  230  and a logical OR block (or module)  232 . Logical OR operation may be represented in the logic structure  220  by circles, logical AND operation may be represented by hexagons. 
   The matrix  222  may have multiple (e.g., 16) inputs receiving values (e.g., X 1  through X 16 ) for the second threshold function T 2 . Each column and row of the matrix  222  may be connected to one of the blocks  224  and  226 . The blocks  224  and  226  may generate first intermediate values (e.g., A 1  through A 4  and B 1  through B 4 ) through multiple logical OR operations on four values received from the matric  222 . 
   Each of the blocks  228  and  230  may be configured to generate second intermediate values (e.g., C 1  through C 4  and D 1  through D 4 ) through multiple logical OR operation on two of the four first intermediate values. Third intermediate value (e.g., E 1  through E 4  and F 1  through F 4 ) may be generated within each of the blocks  228  and  230  using the logic structure of two Y 2  modules. In the block  228 , the values E 1  and E 3  may generate a fourth intermediate value (e.g., G) through a logical OR operation. The value E 2  may equal the value T 1 . The value E 4  may be unused. In the block  230 , the values F 1  and F 3  may generate a fourth intermediate value (e.g., H) through a logical OR operation. The values F 2  and F 4  may be unused. The logical OR block  232  may generate the value T 2  from the values G and H. 
   Referring to  FIG. 18 , a block diagram of an example implementation of a circuit  240  is shown. The circuit  240  may be operational to perform the second threshold function T 2  for multiple input signals (e.g., X 1  through X 16 ) per the logic structure  220 . The matrix  222  of the logic structure  220  may be implemented in the circuit  240  as multiple level of U 1 , U 2  and U 4  units. Generation of half of the first intermediate signals (e.g., A 1  through A 4 ) may be implemented with logical OR gates  244 A– 244 D. Generation of the remaining intermediate signals (e.g., B 1  through B 4 ) may be implemented with logical OR gates  246 A– 246 D. 
   A circuit (or module)  248  may be implemented with logical OR gates and logical AND gates following the logic structure of the block  228 . The circuit  248  may be referred to as a 4-input T 1  and T 2  circuit. The circuit  248  may be operational to generate a signal (e.g., G).and the signal T 1  based on the signals A 1  through A 4 . Logic gates that would otherwise generate unused signals may not be implemented in the circuit  248 . 
   A circuit (or module)  250  may be implemented with logical OR gates and logical AND gates following the logic structure of the block  230 . The circuit  250  may be similar to the circuit  248  but without the logic gates that would otherwise generate the signal T 1  and the unused signals. A logical OR gate  252  may combine the signal G and and signal (e.g., H) generated by the circuit  250  to generate the signal T 2 . 
   Referring to  FIG. 19 , a table I comparing a delay and a number of logic gates for conventional implementations and the present invention is shown. Table I generally shows delay and depth for simultaneous implementations of T 2  and T 1 ; if T 1  is not utilized, reduce then numbers in the two last columns by 1. To estimate a quality of the presented method, note that a number of 2-input logic gates for T 2  cannot be less than 2×2 n −3, and the delay (depth) cannot be less than n (the later is common for any 2 n -input function that depends on all inputs.) 
   As used herein, the term “simultaneously” is meant to describe events that share some common time period but the term is not meant to be limited to events that begin at the same point in time, end at the same point in time, or have the same duration. 
   While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention.