Patent Publication Number: US-6909767-B2

Title: Logic circuit

Description:
RELATED APPLICATION 
     This application claims priority under 35 U.S.C 119(e) from U.S. Provisional Application Ser. No. 60/439,852 filed Jan. 14, 2003, which application is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to digital electronic devices, and in particular, to a digital electronic device performing binary logic. 
     BACKGROUND TO THE INVENTION 
     A fundamental requirement in digital electronics is a circuit which, depending on the number of highs amongst a second plurality of inputs, selects one of a first plurality of inputs. Such a circuit can be provided to indicate if the number of highs amongst k inputs belongs to any particular subset of the integers {0, 1, . . . , k}. 
     Examples of such circuits include threshold circuits, which indicate if j or more of k total inputs are high. The threshold function [k,j] is low if there are less than j high inputs within k total inputs, but [k,j] is high if there are j or more high inputs within k total inputs. For example, [ 10 , 4 ] is low for 0 to 3 high inputs, but is high for 4 to 10 high inputs. 
     Further examples of such circuits include circuits to indicate whether or not an exact number of high inputs are present amongst k total inputs, the circuit outputting a high value only for this exact number of high inputs. This circuit implements the selection function &lt;k,j&gt;, which is defined to be high when k inputs has exactly j high inputs, and low when the number of high inputs in not equal to j. For example, the function &lt; 10 , 4 &gt; represents a system with 10 inputs, and is high only when exactly four of these ten inputs are high, otherwise it is low. This function &lt; 10 , 4 &gt;, when plotted for a range of different numbers of high inputs, gives a “top-hat” shape—i.e. it is zero if the system has 0 to 3 high inputs, it is 1 if the system has 4 high inputs, and it is zero if the system has 5 to 10 high inputs, where zero represents a low and 1 represents a high. 
     Such circuits as described above find applications in multiplication, counting, memory control, etc. These circuits often appear on the frequency-limiting paths of systems and can consume large silicon area, and much importance is placed on achieving speed and area improvements in their implementation. 
     For example, it is instrumental for many applications to have a parallel counter that adds n inputs of the same binary weight together, and produces an output that is a binary representation of the number of high inputs. Such parallel counters (L. Dadda,  Some Schemes for Parallel Multipliers , Alta Freq 34: 349-356 (1965); E. E. Swartzlander Jr.,  Parallel Counters , IEEE Trans. Comput. C-22: 1021-1024 (1973)) are used in circuits performing binary multiplication. There are other applications of a parallel counter, for instance, majority-voting decoders or RSA encoders and decoders. It is important to have an implementation of a parallel counter that achieves a maximal speed. 
     The following notation is used for logical operations on Boolean variables (such that take one of two values, high and low):
         a b denotes the AND of a and b, which is high if a and b are high.   a+b denotes the OR of a and b, which is high if a is high or b is high.   a⊕b denotes the exclusive OR of a and b, which is high if a and b have different values.   a-bar is the complement of a, which is high if a is low.   Σ i=a i=b  S(i) denotes the OR of a plurality of Boolean expressions, i.e. S(a)+S(a+1)+ . . . +S(b).       

     SUMMARY OF THE INVENTION 
     The present invention provides a circuit for selecting one binary input from a set of binary inputs, according to the number of high input signals applied to a further set of binary inputs. The circuit includes a first subcircuit with a first set of binary inputs, and logic to generate a set of control output signals. In many applications, this first set of binary inputs will be a plurality of binary inputs, although it is also possible to use a single binary input and determine whether one or zero high input signals are present at any time. Each of the generated control output signal represents whether or not the first set of binary inputs has exactly a predetermined number of high inputs signals. Each control output signal corresponds to a different predetermined number of high input signals. The circuit may generate a control output signal for each possible number of high input signals, or it may generate a control output signal for only some of the possible numbers of high input signals. 
     The circuit also includes a second subcircuit with a second set of binary inputs, a set of control inputs for receiving control output signals from the first subcircuit, and logic which includes a plurality of switching components. Some or all of the switching components can comprise at least one pass gate. Each switching component is switchable to connect or isolate one of the second set of inputs to a common output. The switching of each switching component is controlled using a signal from one of the control inputs. The first and/or second subcircuits are configured such that only one switching element can be switched to connect at any one time. 
     The number of control inputs to the second subcircuit is preferably equal to the number of control output signals from the first subcircuit, although this is not essential. 
     Some of the second binary inputs may be fixed low or ma high voltage, for example, by being connected to the earth terminal of the circuit or to the positive voltage supply terminal of the circuit. In that case, it not necessary for these binary inputs to be separate inputs, and they may be combined or connected together. 
     Embodiments of the present invention may be used in standard cells, and in this case, it is advantageous for the circuit to have well defined input and output impedences. The circuit may be provided with a high output impedence by connecting high impedence buffer means between the pass gate outputs and the common output of the circuit. Alternative types of switching components may also benefit from a high impedence buffer means. Either a single buffer may be connected at the common output, or a plurality of individual buffers may be connected to each switching component output. 
     The switching components used in the invention are not limited to include only pass gates and transistors, and other types of switching components may also be used. 
     Embodiments of the present invention have several advantages over the prior art. The use of non-hierarchical multiplexers (muxes), built from pass-gates, as switching components has the advantage of achieving greater speed of evaluation, and reducing the silicon area needed to implement the circuit. It also provides a greater ease of layout compared with previous methods. 
     A pass gate may be constructed from an n-type and a p-type transistor, each with a source, a drain and a gate terminal. The p-type source terminal is connected to the n-type source terminal, and the p-type drain terminal is connected to the n-type drain terminal. The p-type and n-type gate terminals are not connected together, so that each can receive a different input signal. 
     When a high input is applied to the gate of the n-type transistor, the transistor can conduct a signal from source to drain, but when a low input is applied, the transistor can no longer conduct the signal. The opposite is true for the p-type transistor, which can conduct only when a low input is applied to its gate. Thus, a pair of opposite binary signals may be applied to the gates of the p-type and n-type transistors to open or close the pass gate. The pass gate is closed when the n-type transistor gate input is low and the p-type transistor gate input is high, such that neither transistor can conduct a signal from source to drain. 
     When the pass gate is open (i.e. when the n-type transistor gate input is high and the p-type transistor gate input is low), the p-type transistor can conduct a high signal from source to drain, and the n-type transistor can conduct a low signal from source to drain. Therefore both transistors are necessary to allow either a high or a low signal to be conducted through the pass gate. 
     The circuit may include a third subcircuit to generate a function such as a selection function or threshold function. One of the functions outputted by the third subcircuit may be selected by the second subcircuit according to the number of high inputs in the first set of binary inputs. Selection may be configured such that the output of the third subcircuit reflects the total number of high inputs to both the first and the third subcircuits. This has the advantage that instead of one subcircuit having to deal with a large number of inputs, the total number of inputs to be counted can be split between a plurality of subcircuits, and the logic provided in each subcircuit can thus be more straightforward. 
     The total number of inputs may be divided yet further by employing a circuit with a tree-like structure, where a plurality of first and third subcircuits are provided at the first level of the tree structure, and each of these passes its outputs to a second subcircuit to generate an intermediate count signal. The intermediate count signals are passed to the second level of the tree structure, where they are summed by further first, second and third subcircuits. Thus, selection functions &lt;kj&gt; or threshold functions [k,j] or other functions relating to a count of the number of high inputs may be generated easily for high values of k. This has application in a parallel counter circuit which generates a binary representation of the number of high signals on its inputs. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram illustrating the circuit according to a first embodiment of the invention; 
         FIG. 2  is a schematic diagram of the non-hierarchical multiplexer of  FIG. 1 ; 
         FIG. 3  is a circuit diagram showing a transistor-level implementation of the non-hierarchical multiplexer of  FIG. 1 ; 
         FIG. 4  is a block diagram showing a circuit according to a second embodiment of the invention; 
         FIG. 5  is a block diagram showing a circuit according to a third embodiment of the invention; 
         FIG. 6  is a block diagram showing a circuit according to a fourth embodiment of the invention; 
         FIG. 7  is a block diagram showing a circuit according to a fifth embodiment of the invention; 
         FIG. 8  is a block diagram of a ( 7 ,  3 ) counter according to a sixth embodiment of the invention; 
         FIG. 9  is a circuit diagram showing a logic gate and transistor implementation of part of the circuitry of the ( 7 , 3 ) counter of  FIG. 8 ; 
         FIG. 10  is a block diagram of a ( 15 , 4 ) counter according to a seventh embodiment of the invention; and 
         FIGS. 11A and 11B  are circuit diagrams showing a transistor level implementation of part of the circuitry of the ( 15 , 4 ) counter of FIG.  10 . 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION 
       FIG. 1  is a block diagram of a circuit according to a first embodiment of the invention. 
     The circuit selects one of a plurality of binary inputs M 0 , . . . ,Mk, depending on the number of highs amongst a further plurality of binary inputs X 1 , . . . ,Xk. The circuit has two subcircuits: a first subcircuit  100  and a second subcircuit  110 . 
     The first subcircuit  100  determines the number of highs amongst the further plurality of binary inputs, X 1 , . . . X k . There are a total of k binary inputs X 1 , . . . ,X k  to subcircuit  100 . Subcircuit  100  generates k+1 outputs, consisting of a series of selection functions &lt;k,j&gt;, where j is an integer between 0 and k. Each selection function outputs a high value if there are exactly j high inputs amongst the k inputs to subcircuit  100 , and outputs a low value if there are less than or greater than j high inputs amongst the k inputs to subcircuit  100 . Each of the selection functions from j=0 to j=k is generated as a separate output signal, giving k+1 output signals. Only one of these output signals can be high at any one time, because each output signal relates to a different number of highs in the inputs X 1 , . . . ,Xk. 
     Thus, for example, if only one input to subcircuit  100  is high, then the first output signal &lt;k, 0 &gt; is low, the second output signal &lt;k, 1 &gt; is high, and the subsequent output signals &lt;k,j&gt; for j&gt;1 are all low. If instead, exactly two inputs are high, then the first and second output signals &lt;k, 0 &gt; and &lt;k, 1 &gt; are low, the third output signal &lt;k, 2 &gt; is high, and the subsequent output signals &lt;k,j&gt; for j&gt;2 are all low. 
     The function &lt;k,j&gt; is a symmetric function, because its value is determined only by the total number of high inputs, and not by their order. Thus, the inputs X 1 , . . . ,Xk of subcircuit  100  are interchangeable with one another. 
     The k+1 output signals, &lt;k, 0 &gt; to &lt;k,k&gt;, of subcircuit  100  are passed to control inputs S 0 , . . . ,Sk of subcircuit  110 . 
     The second subcircuit  110  is a non-hierarchical multiplexer. It has k+1 control inputs So, . . . ,Sk, of which only one can be high at once. This condition is met by the set of functions &lt;kj&gt;, because for a given number of highs within k inputs, only one value of j will correspond to that given number, thus only one of the set of functions &lt;k,j&gt; will be high. Subcircuit  110  also has k+1 inputs Mo, . . . ,Mk, and one output Y. The control inputs S 0 , . . . ,Sk determine, in a one-to-one correspondence, which of the inputs M 0 , . . . ,Mk is passed to the output Y. 
     Since the control inputs S 0 , . . . ,Sk of multiplexer  110  receive the functions &lt;k,j&gt; generated by subcircuit  100  as input signals, then the multiplexer input selected from M 0 , . . . ,Mk depends on how many of the inputs X 1 , . . . , Xk to subcircuit  100  are high. 
     Although the control inputs S 0 , . . . ,Sk of the multiplexer  110  are controlled by a symmetric function &lt;k,j&gt;, it is not necessary that the signals on inputs M 0 , . . . ,Mk of the multiplexer  110  should be symmetric. 
       FIG. 2  shows a schematic diagram of the internal connections within the multiplexer  110 . In the example, a value of k=5 is used, such that the multiplexer  110  has six inputs M 0  to M 5 , six control inputs S 0  to S 5  and one output Y. The control inputs S 0 , . . . ,S 5  each, in effect, open or close a switch to select one of the multiplexer inputs M 0 , . . . ,M 5  as the final output Y. As is shown, S 0  controls the M 0  input, S 1  controls the M 1  input, S 2  controls the M 2  input, etc. Only one of the So, . . . ,Sk control lines may be high at once, such that only one of the switches will be open at any time. In the circuit of  FIG. 1 , there will always be exactly one high control line S 0 , . . . ,Sk regardless of the number of highs on the inputs X 1 , . . . ,Xk, therefore there will always be precisely one of the switches open at any time. 
       FIG. 3  shows a transistor level implementation of the non-hierarchical multiplexer  110  of FIG.  1 . Each input M 0 , . . . ,Mk of the multiplexer is connected via a pass gate  200  to a common output Y. Each pass gate  200  has one of inputs Mo, . . . ,Mk connected to its source terminal. The drain terminals of each of the pass gates  200  are all connected to the common output Y. 
     The gate terminal of the p-type side of the pass gate  200  is symbolised by a circle. When a high input is applied to the gate terminal of the n-type side, and a low input is applied to the gate terminal of the p-type side, the pass gate  200  will be open. When a low input is applied to the gate terminal of the n-type side, and a high input is applied to the gate terminal of the p-type side, the pass gate  200  will be closed. 
     To maintain opposite binary signals on each of the two gate terminals, each n-type gate terminal is connected directly to one of the control inputs S 0 , . . . ,Sk, and each corresponding p-type gate terminal is connected via an inverter  210  to that same one control input. Thus, for any integer j, when control input Sj is high, the j-th pass gate will be open, and the input Mj will be passed to the output Y. When Sj is low, the j-th pass gate will be closed, and the input Mj will be isolated from the output Y. 
     No short circuits between the pass gates are possible, because only one of the outputs of subcircuit  100  will ever be high at a time. The use of pass gates is faster than using NAND gates. 
       FIG. 4  shows a block diagram of a circuit according to a second embodiment of the invention. This circuit has k inputs, and generates the selection function &lt;k, 2 &gt;, which indicates whether or not exactly two of the k inputs are high. The inputs are divided into two separate groups of inputs, X 1 , . . . ,X k1  and Y 1 , . . . ,Y k2 . The first group has k 1  inputs, and the second group has k 2  inputs, such that the total number of inputs k=k 1 +k 2 . 
     The circuit of  FIG. 4  includes a subcircuit  300 , a subcircuit  305 , and a subcircuit  310 . The subcircuit  300  is similar to the first subcircuit  100  of  FIG. 1 , but has k 1  inputs X 1 , . . . ,Xk 1  and generates k 1 +1 output signals &lt;k 1 , 0 &gt; to &lt;k 1 ,k 1 &gt;, each indicating whether or not a particular number of the inputs X 1 , . . . ,Xk 1  are high. 
     The subcircuit  305  has k 2  inputs Y 1 , . . . ,Yk 2 . Subcircuit  305  also generates functions to indicate whether or not a given number of highs are present on the inputs. However, unlike in subcircuit  300 , instead of all of the functions &lt;k 2 , 0 &gt; to &lt;k 2 ,k 2 &gt; being generated, only &lt;k 2 , 0 &gt;, &lt;k 2 , 1 &gt; and &lt;k 2 , 2 &gt; are generated. Thus, subcircuit  305  produces three output signals. Each of these output signals is passed to an input of subcircuit  310 . 
     The subcircuit  310  is a non-hierarchical multiplexer similar to subcircuit  110  shown in  FIG. 1 , but having k 1 +1 inputs M 0 , . . . ,Mk 1 , and k 1 +1 control inputs S 0 , . . . ,Sk 1 . The outputs of subcircuit  300  are connected to the control inputs S 0 , . . . ,Sk of the multiplexer  310 . The outputs &lt;k 2 , 2 &gt;, &lt;k 2 , 1 &gt; and &lt;k 2 , 0 &gt; of subcircuit  305  are connected to the inputs M 0 , M 1  and M 2  of the multiplexer  310  respectively. 
     The multiplexer inputs M 3 , . . . ,Mk 2  that do not receive an output signal from subcircuit  305  are set to a fixed low value by connecting them to the circuit&#39;s earth terminal. 
     In order to output a high value from the multiplexer if and only if exactly two highs are present amongst the k=k 1 +k 2  inputs, the output signals &lt;k 2 , 0 &gt;, &lt;k 2 , 1 &gt; and &lt;k 2 , 2 &gt; of subcircuit  305  are arranged on the inputs M 2 , M 1  and M 0  of the multiplexer  310  respectively. If none of the inputs to subcircuit  300  are high then S 0  is high and M 0  is selected, thus the output of the multiplexer  310  is &lt;k 2 , 2 &gt;, which is high only if two of the inputs to subcircuit  305  are high. If one of the inputs to subcircuit  300  is high, then S 1  is high, and M 1  is selected. Thus, the multiplexer output is high only if exactly one high is present amongst the inputs to subcircuit  305 . If two of the inputs to subcircuit  300  are high, then S 2  is high and M 2  is selected. Thus, the multiplexer output is high only if none of the inputs to subcircuit  305  are high. 
     It is straightforward to adapt the circuit of  FIG. 4  to generate &lt;k,j&gt; for other values of j, instead of the value of j=2 that is used in FIG.  4 . For larger j than j=2, additional values of &lt;k 2 ,i&gt; are generated, up to &lt;k 2 ,j&gt;. The number of preset zero inputs for the multiplexer is reduced accordingly. However, for values of j larger than k 2 , at least some of the inputs X 1 , . . . ,Xk 1  must be high to make up a total of j high inputs between X 1 , . . . ,Xk 1  and Y 1 , . . . ,Yk 2 . Therefore, if none of these is high, and S 0  is selected, then the required output will always be zero. Thus, for j greater than k 2 , the lowest of the inputs M 0 , . . . ,M 0  can be connected to the earth rail to generate the required zero, and there would no longer be a need for subcircuit  305  to generate the lowest &lt;k 2 ,i&gt; functions. 
     Each function &lt;k 2 ,i&gt;, which refers to i highs amongst the k 2  inputs of subcircuit  305 , should be input to the (j-i)th M input of the multiplexer, unless it is to be replaced by a constant zero voltage. The multiplexer output will then be &lt;kj&gt; for our chosen value of j, because the multiplexer will, in effect, add the number of high inputs of subcircuit  300  to the number of high inputs of subcircuit  305 , by selecting the appropriate output signal from subcircuit  305 . 
     Although subcircuit  300  itself generates functions of the form &lt;n,j&gt;, the larger the value of n, the more complicated it becomes to generate each function &lt;n,j&gt; using combinations of logic gates. The circuit of  FIG. 4  provides an efficient means of generating the &lt;n,j&gt; functions for a larger number of inputs n. The splitting of the inputs into two groups makes each level of the circuit simpler. In  FIG. 4 , the total set of k inputs is preferably split such that the number of inputs k 1  to subcircuit  300  is greater than or just less than the number of inputs k 2  to subcircuit  305 . Thus, the multiplexer  310  has a control signal S 0 , . . . ,Sk 1  provided by subcircuit  300  on each of its control inputs, whilst allowing all outputs of subcircuit  305  to be input to the multiplexer, and any one of them selected. 
       FIG. 5  shows a circuit for generating the functions &lt;k,j&gt; for each value of j from 0 to k. The circuit comprises a subcircuit  300 , a subcircuit  306 , and subcircuits  3 _ 0  to  3 _k. Subcircuit  300  is identical to subcircuit  300  in  FIG. 4 , generating the functions &lt;k 1 ,j&gt; for values of j from 0 to k 1 . Subcircuit  306  is similar to subcircuit  305  of  FIG. 4 , but generates functions &lt;k 2 ,j&gt; for all values of j from 0 to k 2 . Subcircuit  3 _ 2  (not shown) is identical to subcircuit  310  in FIG.  3 . The set of subcircuits  3 _ 0 , . . . , 3 _k 1  form a series, in which the functions &lt;k, 0 &gt;, &lt;k, 1 &gt;, . . . ,&lt;k,k- 1 &gt; and &lt;k,k&gt; are generated. Each of these subcircuits  3 _j functions as a multiplexer with k 1 +1 inputs, k 1 +1 control inputs and one output. The same set of control input signals is input to each one of subcircuits  3 _ 0  to  3 _k. However, the arrangement of the &lt;k 2 ,j&gt; signals on the multiplexer Mj is chosen for each subcircuit such that each function &lt;k 2 ,i&gt; is input to the (j-i)th M input of the multiplexer, unless j-i does not correspond to an integer between zero and k 1 , and thus is to be replaced by a constant zero voltage. The effect is to add together the number of high inputs of subcircuit  300  to the number of high inputs of subcircuit  306 . 
     Only one of the output functions &lt;k, 0 &gt;, . . . ,&lt;k,k&gt;from the multiplexer subcircuits  3 _ 0 , . . . ,  3 _k will be high at any time, and all the others will be low, according to the total number of high inputs to both subcircuits  300  and  306 . 
     Subcircuit  3 _ 0  generates &lt;k, 0 &gt;, which indicates if no highs are present amongst k input. Thus if one or more of the inputs X 1 , . . . ,Xk 1  to subcircuit  400  are high, then &lt;k, 0 &gt; will be zero. If none of inputs X 1  . . . Xk 1  are high, and if also none of inputs Y 1  . . . Yk 2  are high, then &lt;k, 0 &gt; will be high. Thus, control input S 0  switches the M 0  input of the multiplexer, which has input function &lt;k 2 , 0 &gt;, thereby giving an effective output of &lt;k, 0 &gt; which is high when there are no high inputs. 
     Subcircuit  3 _ 1  generates &lt;k, 1 &gt;. If two or more of inputs X 1  . . . X k1  are high, then &lt;k, 1 &gt; will be zero. If exactly one of inputs X 1  . . . X k1  are high, then we need exactly none of inputs Y 1  . . . Y k2  to be high in order to give an output of &lt;k, 1 &gt; being high. Thus, &lt;k 2 , 0 &gt; is selected on the M inputs. If none of inputs X 1  . . . X k1  are high, then we need exactly one of inputs Y 1  . . . Y k2  to be high, in order to give an output of &lt;k, 1 &gt; being high, thus &lt;k 2 , 1 &gt; is selected on the M inputs. 
     Subcircuit  3 _(k- 1 ) generates &lt;k,k- 1 &gt;, which is high only when a single input is low and the remaining inputs are high. If any less than k 1 - 1  of inputs X 1  . . . X k1  are high, then &lt;k,k- 1 &gt; will be zero, because the total number of high inputs will fall short of k- 1 . If exactly k 1 - 1  of inputs X 1  . . . X k1  are high, then all of inputs Y 1  . . . Y k2  must be high in order to give an output of &lt;k,k- 1 &gt; that is high, thus &lt;k 2 ,k 2 &gt; is selected on the M inputs. If all of inputs X 1  . . . X k1  are high, then we need exactly k 2 - 1  of inputs Y 1  . . . Yk 2  to be high, in order to give an output of &lt;k,k- 1 &gt; that is high, thus &lt;k 2 ,k 2 - 1 &gt; is selected on the M inputs. 
     Subcircuit  3 _k generates &lt;k,k&gt;. Unless all of inputs X 1  . . . X k1  are high, then &lt;k,k&gt; will be zero. If all of inputs X 1  . . . X k1  are high, then we also need all of inputs Y 1  . . . Y k2  to be high in order to give an output of &lt;k,k&gt; as high, thus &lt;k 2 ,k 2 &gt; is selected on the M inputs. 
       FIG. 6  shows a circuit for generating the threshold function [k, 2 ], which is high if two or more of the k inputs are high, but low if zero or one of the k inputs are high. Again, the k inputs are split into two groups, X 1 , . . . ,Xk 1  and Y 1 , . . . ,Yk 2 , where the first group consists of k 1  inputs, and the second group consists of k 2  inputs. k 1  is chosen to be larger than or equal to k 2 . 
     The circuit of  FIG. 6  is built from three subcircuits. Subcircuit  400  generates the function &lt;k 1 , j&gt; for each value of j from 0 to k 1 , and this subcircuit is identical to subcircuit  300  of FIG.  4 . Subcircuit  405  generates the threshold functions [k 2 , 0 ] and [k 2 , 1 ]. Subcircuit  410  is a multiplexer with control inputs S 0 , . . . ,Sk 1  receiving input signals from subcircuit  400 , and multiplexer inputs M 0 , . . . ,Mk 1  receiving input signals from subcircuit  405 . 
     If none of the inputs X 1  . . . Xk 1  of subcircuit  400  are high, then control input S 0  is high, thus [k 2 , 2 ] is selected as the output, as at least two high inputs must be found from Y 1 , . . . ,Yk 2  to give a high value of [k, 2 ]. If exactly one of the inputs X 1  . . . Xk 1  of subcircuit  400  is high, then control input S 1  is high, and [k 2 , 1 ] is selected as the output, as at least one high input must be found from Y 1 , . . . ,Yk 2  to give a high value of [k, 2 ]. If two or more of the inputs X 1  . . . Xk 1  of subcircuit  400  are high, then one of control inputs S 2 , . . . ,Sk 1  is high. The corresponding M inputs M 2 , . . . ,Mk 1  are all connected to the positive voltage rail of the circuit to automatically hold these inputs at a high value, as [k, 2 ] will be then be high regardless of how many of Y 1 , . . . ,Yk 2  are high, since at least two out of the total of k inputs are already high. 
       FIG. 7  shows a circuit for generating a series of threshold functions [k,j] for j from 1 to k. The first stage is the same as that shown in  FIG. 6 , i.e. subcircuit  400  is used to generate &lt;k 1 ,j&gt;. Subcircuit  406 , which is very similar to subcircuit  405 , generates the [k 2 ,j] threshold functions, but for all values of j from 0 to k 2 . A plurality of multiplexers are provided, one for each threshold function to be generated. Only those for [k, 1 ], [k, 2 ], [k,k- 1 ] and [k,k] are shown in the figure. Again, for each multiplexer, the control input Sj controls the switching of the multiplexer input Mj to the output of the multiplexer. 
     The [k, 1 ] function is generated by connecting [k 2 , 1 ] to the M 0  input of the multiplexer  3 _ 1  and holding every other input Mj to the multiplexer at a high value. The [k, 2 ] function is generated by connecting [k 2 , 2 ] to the M 0  input of the multiplexer  3 _ 1 , connecting [k 2 , 1 ] to the M 1  input of the multiplexer  3 _ 2 , and holding each other input to the multiplexer Mj as high. The [k,k- 1 ] function is generated by connecting [k 2 ,k 2 ] to the Mk 2  input of the multiplexer  3 _k- 1 , connecting the [k 2 ,k 2 - 1 ] function to the Mk 2 - 1  input of the multiplexer  3 _k- 1 , and holding each other input to the multiplexer Mj as high. The [k,k] function is generated by connecting [k 2 ,k 2 ] to the M 0  input of the multiplexer  3 _k and holding each other input to the multiplexer Mj as low. 
     The M inputs are chosen for each threshold function [k 2 ,j] to give an additive effect with the selection functions &lt;k 1 ,i&gt;, in a similar manner to that used in FIG.  5 . 
     The embodiments of  FIGS. 4  to  7  show how a counter or threshold circuit for determining whether a predetermined number of inputs are high out of a small number of inputs can be used to generate a function indicating whether a counter or threshold circuit for determining whether a predetermined number of inputs are high out of a larger total number of inputs. 
     This property can be used recursively to generate a circuit with a tree structure. An application of this method is in the implementation of a (n,k) counter, which counts the number of highs amongst n inputs and represents it in binary on k outputs. For a ( 7 , 3 ) counter having inputs X 1  to X 7  and outputs S 1 , S 2  and S 3  labelled in ascending order of binary weight, a method of implementation is as follows. 
     The lowest binary weight output can be generated by an XOR function between the inputs, i.e. S 1 ={7,1}=X 1 ⊕X 2 ⊕X 3 ⊕X 4 ⊕X 5 ⊕X 6 ⊕X 7   
     The middle binary weight output can be generated from the threshold functions [ 7 , 2 ], [ 7 , 6 ] and the complemented threshold function [ 7 , 4 ] c . S 2 =[ 7 , 2 ] [ 7 , 4 ] c  [ 7 , 6 ] 
     The highest binary weight output is simply equal to the threshold function +[ 7 , 6 ]. 
       FIG. 8  shows an implementation of a ( 7 , 4 ) counter A tree structure is used to generate threshold functions [ 2 ,k] and selection functions &lt; 2 ,k&gt;_ 0 , &lt; 2 ,k&gt;_ 1  and &lt; 1 ,k&gt;from pairs of inputs, X 1  and X 2 ; X 3  and X 4 , X 5  and X 6 , and using single input X 7  respectively. (The “ — 0” and “ — 1” labels differentiate between the two different sets of functions of the same order but generated using different pairs of inputs).Then, pairs of first level outputs, are combined to give [ 4 ,k] and &lt; 3 ,k&gt; type functions at second level outputs. Finally, the second level outputs are combined to give [ 7 ,k] threshold functions, in particular the [ 7 , 2 ], [ 7 , 4 ] and [ 7 , 6 ] threshold functions. The [ 7 , 4 ] value directly gives the S 3  output, and the S 2  output is found by setting [ 7 , 2 ] and [ 7 , 6 ] as multiplexer inputs, and selecting between them using the [ 7 . 4 ] output. 
       FIG. 9  shows a logic implementation of functions &lt; 1 ,i&gt;, &lt; 2 ,i&gt; and [ 2 ,i]. The circuit on the left hand side shows an implementation of the function &lt; 1  ,i&gt;, from a single input of X. The value of X itself gives &lt; 1 , 1 &gt;, without a need for any logic gates. The function &lt; 1 , 0 &gt; can be simply generated by connecting input X to an inverter, and taking the output of the inverter. 
     The circuit in the middle of  FIG. 9  is an implementation of &lt; 2 ,i&gt;, generated from inputs X 1  and X 2 . X 1  and X 2  are connected to the inputs of an AND gate to produce &lt; 2 , 2 &gt;. X 1  and X 2  are connected to the inputs of an XOR gate, giving an output of &lt; 2 , 1 &gt;. X 1  and X 2  are also connected to the inputs of a NOR gate, giving an output of &lt; 2 , 0 &gt;. 
     The circuit on the right hand side of  FIG. 9  is an implementation of [ 2 ,i]. Inputs X 1  and X 2  are connected to the inputs of an AND gate, giving an output of [ 2 , 2 ]. X 1  and X 2  are also connected to the inputs of an OR gate, giving an output of [ 2 , 1 ]. 
       FIG. 10  shows an implementation of a ( 15 , 4 ) counter with maximum binary weight. The counter has 15 inputs, X 1  to X 15 . In the first level, inputs X 1  to X 14  are combined in groups of two to generate the functions [ 2 ,i] for X 1  and X 2 , &lt; 2 ,i&gt;_ 0  for X 3  and X 4  (where the 0 is a label to differentiate from &lt; 2 ,i&gt; for other inputs), &lt; 2 ,i&gt;_ 1  for X 5  and X 6 , &lt; 2 ,i&gt;_ 2  for X 7  and X 8 , &lt; 2 ,i&gt;_ 3  for X 9  and X 10 , &lt; 2 ,i&gt;_ 4  for X 11  and X 12 , and &lt; 2 ,i&gt;_ 5  for X 13  and X 14 . X 15  is used to generate &lt; 1 ,i&gt; in the first level of the binary tree. 
     In the second level of the binary tree, the functions, &lt; 4 ,i&gt;_ 0 , &lt; 4 ,i&gt;_ 1 , and &lt; 3 ,i&gt; are generated from pairs of functions generated in the first level. 
     In the third level, the functions and &lt; 7 ,i&gt; are generated from [ 4 ,i] and &lt; 4 ,i&gt;_ 0 , and from &lt; 4 ,i&gt;_ 2  and &lt; 3 ,i&gt; respectively. 
     In the fourth level [ 15 ,i] is generated from [ 8 ,i] and &lt; 7 ,i&gt;. 
     [ 15 , 12 ] and [ 15 , 4 ] are then used as inputs to a multiplexer switched by [ 15 , 8 ] to generate S 3 , the third output bit of the ( 15 , 4 ) counter. [ 15 , 8 ] corresponds directly to the fourth output bit of the ( 15 , 4 ) counter. The first output bit of the ( 15 , 4 ) counter can be generated by an XOR function between each of the inputs. 
     On a component level, the selection functions &lt;k,j&gt; and/or the threshold functions [k,j] can be generated using a non-hierarchical multiplexer built from pass gates. However, where the multiplexer has some fixed high or low inputs, it is unnecessary to use full pass gates for these inputs, and single transistors will suffice in their place. 
     If the fixed input is a fixed high, a p-type transistor can be used, and the transistor can be connected between the positive voltage rail Vcc and the common output. If the fixed input is a fixed low, an n-type transistor can be used, and the transistor can be connected between ground and the common output. 
     The number of components can be further reduced for circuits in which only two possibilities exist for the M inputs of the multiplexer, e.g. a threshold function or selection function as an input to M 0  and all other M inputs connected to the earth rail of the circuit. Similarly for a threshold or selection function input to M 0  and all other M inputs connected to the positive voltage rail. In cases such as these, several pass gates may be replaced with a single transistor, as is described with reference to  FIGS. 11A and B . 
       FIGS. 11A and 11B  show a design optimised circuit for producing the threshold functions [ 4 ,j], and may be used in the implementation of the circuit of FIG.  10 .  FIG. 11A  shows the generation of functions in the first level of the circuit of  FIG. 10 , and  FIG. 11B  shows the generation of the second level functions, using the first level functions. 
       FIG. 11A  shows four circuit diagrams. The first is a circuit to produce &lt; 2 , 0 &gt; and its inverse using two inputs X 3  and X 4 . The X 3  and X 4  inputs are connected to a NOR gate, giving an output of &lt; 2 , 0 &gt;, which is written as XA 20 . The output is also passed through an inverter U 11  to give the inverse, which is written as XA 20 bar. 
     The second circuit of  FIG. 11A  is to produce &lt; 2 , 1 &gt; and its inverse using two inputs X 3  and X 4 . Input X 3  is passed through an inverter U 13 , and the output of the inverter U 13  is connected to the source inputs of pass gates U 9  and U 6 . The output of the inverter U 13  is also connected to the input of a second inverter U 3 . The output of inverter U 3  is connected to the source inputs of pass gates U 4  and U 5 . 
     Input X 4  is connected to the inverse gate inputs of pass gates U 4  and U 6 , and to the gate input of pass gates U 5  and U 9 . Input X 4  is also connected to inverter U 7 , and the output of inverter U 7  is connected to the inverse gate inputs of pass gates U 5  and U 9 , and to the gate inputs of pass gates U 4  and U 6 . 
     The outputs of pass gates U 9  and U 4  are connected together, and give &lt; 2 , 1 &gt;, which is labelled as XA 21 . The outputs of pass gates U 5  and U 6  are connected together and give the inverse of &lt; 2 , 1 &gt;, which is labelled as XA 21 bar. The combination of pass gates and inverters thus effectively acts as an XOR gate and an XNOR gate. 
     The third circuit of  FIG. 11A  is to produce &lt; 2 , 2 &gt;. The circuit has inputs X 3  and X 4 , which are connected to the inputs of a NAND gate U 10 . The output of the NAND gate U 10  is the inverse of &lt; 2 , 2 &gt;, which is written as XA 22 bar. The output of NAND gate U 10  is also connected to an inverter to produce &lt; 2 , 2 &gt;, written as XA 22 . 
     The fourth circuit of  FIG. 11A  is to produce the inverse threshold functions [ 2 , 2 ]-bar and [ 2 , 1 ] -bar. Two inputs X 1  and X 2  are connected to a NAND gate U 1 . The output of the NAND gate U 1  is [ 2 , 2 ]-bar, written as X 22 bar. [ 2 , 2 ]-bar is equivalent to the inverse of &lt; 2 , 2 &gt;. The two inputs X 1  and X 2  are also connected to the inputs of a NOR gate, which produces the output [ 2 , 1 ]-bar, written as X 21 bar. [ 2 , 1 ]-bar is equivalent to &lt; 2 , 0 &gt;. 
       FIG. 11B  shows four circuits, one for generating each of the threshold functions [ 4 , 1 ], [ 4 , 2 ], [ 4 , 3 ] and [ 4 , 4 ]. These circuits are an optimised implementation of the non-hierarchical multiplexers shown in previous figures. 
     The first circuit is for generating the threshold function [ 4 , 1 ]. The input XA 20  (which is the &lt; 2 , 0 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 17 , and its inverse XA 20 bar is provided to the inverse gate terminal of pass gate U 17 . Thus, when neither of inputs X 3  and X 4  are high, XA 20  is high, and pass gate U 17  is open. 
     On its source input, the pass gate U 17  has X 21 bar (which is the inverse of [ 2 , 1 ] for inputs X 1  and X 2 , and is equivalent to &lt; 2 , 0 &gt;). If the pass gate is open, and neither of X 1  or X 2  are high, then the pass gate output is high, which is inverted by the inverter U 18 , such that the circuit output is low. However, if either or both of X 1  or X 2  are high, then the inverter output is low, which is inverted by the inverter U 18  such that the circuit output is high. 
     The circuit also has a n-type transistor Q 1  with its source connected to ground, its gate connected to the XA 20 bar input (which is the inverse of the &lt; 2 , 0 &gt; function for inputs X 3  and X 4 ), and its drain connected to the input of inverter U  18 . Thus, if one or both of X 3  and X 4  are high, then the transistor Q 1  conducts, and the input to inverter U 18  is low. The inverter U 18  inverts this such that the circuit output is high. 
     It is possible to replace the n-type transistor Q 1  with a pass gate. However, the use of a full pass gate is unnecessary, because the current will only flow in one direction through the transistor Q 1  or replacement pass gate, due to the fixed ground connection. Thus, the use of a transistor instead of a pass gate provides a saving in cost and area. 
     The second circuit of  FIG. 11B  is for generating the threshold function [ 4 , 2 ]. The input XA 20  (which is the &lt; 2 , 0 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 16 , and its inverse XA 20 bar is provided to the inverse gate terminal of pass gate U 16 . Thus, when neither of inputs X 3  and X 4  is high, XA 20  is high, and pass gate U 16  is open. 
     The input XA 21  (which is the &lt; 2 , 1 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 15 , and its inverse XA 21 bar is provided to the inverse gate terminal of pass gate U 15 . Thus, when only one of inputs X 3  and X 4  are high, XA 21  is high, and pass gate U 15  is open. 
     The input XA 22  (which is the &lt; 2 , 2 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of an n-type transistor Q 4 . Thus, when both of inputs X 3  and X 4  are high, XA 22  is high, and transistor Q 4  conducts. The transistor Q 4  has its source connected to ground, and its drain connected to the input of inverter U 14 . Thus, when the transistor Q 4  conducts, the input to the inverter U 14  is low, and the circuit output is high. 
     If instead, pass gate U 15  is open, then X 21 bar (which is the inverse of [ 2 , 1 ] for inputs X 1  and X 2 , and is equivalent to &lt; 2 , 0 &gt;) is output to the input of inverter U 14 . The pass gate U 15  is open when only one of X 3  and X 4  are high. When one or two of X 1  and X 2  are high, the inverter U 14  input is thus low, and the circuit output is high. However, if neither of X 1  or X 2  are high, then the inverter U 14  input is high, and the circuit output is low. 
     If the open pass gate is pass gate U 16 , then X 22 bar (which is the inverse of [ 2 , 2 ] for inputs X 1  and X 2 ) is output to the input of inverter U 14 . The pass gate U 16  is open when neither of X 3  and X 4  are high. When one or none of X 1  and X 2  are high, the inverter U 14  input is thus high, and the circuit output is low. However, if both X 1  and X 2  are high, then the inverter U 14  input is low, and the circuit output is high. 
     The third circuit of  FIG. 11B  is for generating the threshold function [ 4 , 3 ]. The input XA 21  (which is the &lt; 2 , 1 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 21 , and its inverse XA 21 bar is provided to the inverse gate terminal of pass gate U 21 . Thus, when only one of inputs X 3  and X 4  are high, XA 21  is high, and pass gate U 21  is open. 
     The input XA 22  (which is the &lt; 2 , 2 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 19 , and its inverse XA 22 bar is provided to the inverse gate terminal of pass gate U 19 . Thus, when both of inputs X 3  and X 4  are high, XA 22  is high, and pass gate U 19  is open. 
     The input XA 20  (which is the &lt; 2 , 0 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of an p-type transistor Q 3 . Thus, when neither of inputs X 3  and X 4  are high, XA 20  is high, and transistor Q 3  conducts. The transistor Q 3  has its source connected to a voltage VDD, and its drain connected to the input of inverter U 20 . 
     Thus, when the transistor Q 3  conducts, the input to the inverter U 20  is high, and the circuit output is low. 
     If instead, pass gate U 19  is open, then X 21 bar (which is the inverse of [ 2 , 1 ] for inputs X 1  and X 2 ) is output to the input of inverter U 20 . The pass gate U 19  is open when both of X 3  and X 4  are high. When one or two of X 1  and X 2  are high, the inverter U 20  input is thus low, and the circuit output is high. However, if neither of X 1  and X 2  are high, then the inverter U 20  input is high, and the circuit output is low. 
     If the open pass gate is pass gate U 21 , then X 22 bar (which is the inverse of [ 2 , 2 ] for inputs X 1  and X 2 ) is output to the input of inverter U 20 . The pass gate U 21  is open when only one of X 3  and X 4  is high. When both of X 1  and X 2  are high, the inverter U 20  input is thus low, and the circuit output is high. However, if at least one of X 1  and X 2  is low, then the inverter U 20  input is high, and the circuit output is low. 
     The fourth circuit of  FIG. 11B  is for generating the threshold function [ 4 , 4 ]. The input XA 22  (which is the &lt; 2 , 2 &gt; function for inputs X 3  and X 4 ) is provided to the gate terminal of a pass gate U 22 , and its inverse XA 22 bar is provided to the inverse gate terminal of pass gate U 22 . Thus, when both of inputs X 3  and X 4  are high, XA 22  is high, and pass gate U 22  is open. 
     The input XA 22  is also provided at the gate terminal of an p-type transistor Q 2 . Thus, when both of inputs X 3  and X 4  are high, XA 22  is high, and transistor Q 2  does not conduct, due to being p-type. However, when at least one of X 3  and X 4  is not high, the transistor Q 2  conducts. The transistor Q 2  has its source connected to a voltage VDD, and its drain connected to the input of inverter U 23 . Thus, when the transistor Q 2  conducts, the input to the inverter U 23  is high, and the circuit output is low. 
     If pass gate U 22  is open, then X 22 bar (which is the inverse of [ 2 , 2 ] for inputs X 1  and X 2 ) is output to the input of inverter U 23 . The pass gate U 22  is open when both of X 3  and X 4  are high. When both of X 1  and X 2  are high, the inverter U 23  input is thus low, and the circuit output is high. However, if at least one of X 1  and X 2  is low, then the inverter U 23  input is high, and the circuit output is low. 
     Although the embodiment of  FIGS. 11A and 11B  use a single transistor, embodiments of the present invention encompass the use of any number. Any number of fixed low or high inputs to one multiplexer with &lt;n,i&gt; select signals can be replaced by k n/p transistors in parallel or alternatively by n+1-k n/p transistors in series. 
     In particular embodiments, the circuit of the invention may be a parallel counter, or a multiplier circuit, or a memory control circuit. 
     A further embodiment of the invention is an integrated circuit including any circuit according to the invention. The invention also encompasses circuit boards including any circuit according to the invention, and digital electronic devices including any circuit according to the invention. 
     Embodiments of the present invention provides an implementation of a generalised high-speed digital circuit to count any given number of bits. 
     Embodiments of the present invention are suitable for standard cell technology in which the inputs and outputs are well defined. The use of high input impedance devices such as inverters at the inputs and outputs of the pass gates facilities this. 
     Embodiments of the present invention described herein include a circuit for selecting one of a second set of binary inputs according to the number of high input signals applied to a first set of binary inputs, the circuit including: a first subcircuit having said first set of binary inputs, and logic for generating a set of control output signals, wherein each control output signal represents whether or not the first set of binary inputs has exactly a predetermined number of high input signals, and wherein each control output signal corresponds to a different said predetermined number of high input signals; and a second subcircuit having said second set of binary inputs, a set of control inputs for receiving control output signals from the first subcircuit, and logic comprising a plurality of switching components including one or more pass gates, each said switching component being switchable to connect or isolate one of the second set of inputs to a common output, wherein the control inputs are used to control the switching of the switching components, and wherein the first and second subcircuits are configured such that only one switching component can be switched to connect at any one time. 
     While the invention has been described in terms of what are at present its preferred embodiments, it will be apparent to those skilled in the art that various changes can be made to the preferred embodiments without departing from the spirit and scope of the invention.