Abstract:
A novel majority logic circuit is disclosed to determine whether the majority of the inputs are a one, within a constant number of clock cycles, regardless of the number of inputs. The majority logic circuit according to the present invention includes a plurality of current mirror stages and an amplifier stage. For each input, one current mirror stage is used, which outputs either a current source if the input is a one, or a current sink if the input is a zero. The current sources of all the input current mirror stages are connected in parallel to the current source input node of the amplifier stage. The current sinks of all the input current mirror stages are connected in parallel to the current sink input node of the amplifier stage. The amplifier is a differential type, which outputs either a positive voltage or a zero voltage depending upon the majority of the inputs.

Description:
FIELD OF THE INVENTION 
   The present invention relates, in general, to electronic digital logic circuitry, and, in particular to determining the value of a majority of the inputs. 
   BACKGROUND OF THE INVENTION 
   A majority logic circuit indicates whether a majority of binary inputs are equal to one. Prior art techniques accomplish this by either counting the number of inputs, or by using Boolean logic. Typically, an odd number of inputs are used to eliminate the possibility of having an equal number of ones and zeros. 
   U.S. Pat. No. 4,091,293, entitled “MAJORITY DECISION LOGIC CIRCUIT,” discloses a method of detecting buffer overflow exploits by searching for pointer fingerprints. A pointer fingerprint is a portion of a pointer containing at least a portion of the return address. Preferably, the method searches for the return address of a jump function only in portions of the stack where jump functions are not expected. This method requires extensive use of processor resources and requires a determination of which return addresses are valid and which are invalid. U.S. Pat. No. 4,091,293 is hereby incorporated by reference into the specification of the present invention. 
   U.S. Pat. No. 4,692,640, entitled “MAJORITY CIRCUIT COMPRISING BINARY COUNTER,” discloses a circuit comprising a series of binary counters. Each counter is initially set to zero, with data entered serially over multiple clock cycles. If the input data is a one, the binary counter is incremented. After all data has been entered, if the output is greater than the number of inputs divided by two, the circuit indicates that the majority of the inputs were a one. The time to determine the output increases with each additional input. The present invention is not limited in this regard. U.S. Pat. No. 4,692,640 is hereby incorporated by reference into the specification of the present invention. 
   U.S. Pat. No. 5,680,408, entitled “METHOD AND APPARATUS FOR DETERMINING A VALUE OF A MAJORITY OF OPERANDS,” discloses a circuit that can determine the output in a short number of clock cycles. Multiple operands are received, and only the minimum number of inputs is tested to insure that the majority of the inputs are equal to one. The invention works well for small number of inputs, but does not scale well for large numbers of inputs, and becomes very complex. The present invention is not limited in this regard. U.S. Pat. No. 5,680,408 is hereby incorporated by reference into the specification of the present invention. 
   SUMMARY OF THE INVENTION 
   It is an object of the present invention to provide a majority logic circuit to determine the binary state of a plurality of inputs in a constant number of clock cycles. 
   The majority logic circuit determines whether the majority of the inputs are a one, within a constant number of clock cycles, regardless of the number of inputs. 
   The majority logic circuit according to the present invention includes a plurality of current mirror stages and an amplifier stage. For each input, one current mirror stage is used, which outputs either a current source if the input is a one, or a current sink if the input is a zero. 
   The current sources of all the input current mirror stages are connected in parallel to the current source input node of the amplifier stage. The current sinks of all the input current mirror stages are connected in parallel to the current sink input node of the amplifier stage. The source input to the amplifier stage will be the equal to the combined source current from all the input current mirror stages divided by the number of inputs. Likewise, the sink input to the amplifier stage will be the equal to the combined sink current from all the input current mirror stages divided by the number of inputs. 
   The amplifier is a differential type, which outputs either a positive voltage or a zero voltage depending upon the majority of the inputs. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a circuit diagram of the present invention; 
       FIG. 2  is a circuit diagram of the current mirror portion of the circuit shown in  FIG. 1 ; and 
       FIG. 3  is a circuit diagram of the amplifier portion of the circuit shown in  FIG. 1 . 
   

   DETAILED DESCRIPTION 
   The present invention comprises a novel majority logic circuit to provide an indication of the binary state of the majority of the inputs. The output of the present invention is provided in the same number of clock cycles, regardless of the number of inputs. 
   Referring to  FIG. 1 , a majority logic circuit  10  according to the present invention is shown. The majority logic circuit  10  has a plurality of current mirrors  12 , and an amplifier  14 . The number of the plurality of current mirrors  12  equals the number of inputs  16  to the majority logic circuit  10 . In the preferred embodiment, the majority logic circuit  10  has an odd number of inputs  16 . Only the first current mirror  18  and the Nth current mirror  20  are shown. 
   The majority logic circuit  10  employs a number of bipolar transistors, either of the NPN type or the PNP type. Each transistor has an emitter, a base, and a collector. 
   Each of the plurality of current mirrors  12  is identical, and only the first current mirror  18  will be described. 
   Referring to  FIG. 2 , the first current mirror  24  has an input node  26 , a sink node  28 , and a source node  30 . The first current mirror  24  has a first PNP transistor  32 , having an emitter, a base, and a collector. A current connection path connects the collector of the first PNP transistor  30  to the source node  30 . 
   A first resistor  34  has a first terminal and a second terminal. The first terminal of the first resistor  34  is connected to the input node  26  by a current connection path. The second terminal is connected to the base of the first PNP transistor  32  by a current connection path. 
   A second resistor  36  has a first terminal and a second terminal. The first terminal of the second resistor  36  is connected to the base of the first PNP transistor  32  by a current connection path. The second terminal is connected to the emitter of the first PNP transistor  32  by a current connection path. 
   A current connection path connects the emitter of the second PNP transistor  38  to the emitter of the first PNP transistor  32 . The base of the second PNP transistor  38  is connected to the collector of the second PNP transistor  38  by a current connection path, and the collector is connected to the sink node  28 , also by a current connection path. 
   A current connection path connects the base of the third NPN transistor  40  to the collector of the third NPN transistor  40 . The collector is connected by a current connection path to the collector of the first PNP transistor  32 . 
   A current connection path connects the emitter of the fourth NPN transistor  42  to the emitter of the third NPN transistor  40 . A current connection path connects the collector to the collector of the second PNP transistor  38 . 
   A third resistor  44  has a first terminal and a second terminal. The first terminal of the third resistor  44  is connected to the first terminal of the first resistor  34  by a current connection path. The second terminal is connected to the base of the fourth NPN transistor  42  by a current connection path. 
   A fourth resistor  46  has a first terminal and a second terminal. The first terminal of the fourth resistor  46  is connected to the base of the fourth NPN transistor  42  by a current connection path. The second terminal is connected to the emitter of the third NPN transistor  40  by a current connection path. 
   In the preferred embodiment, the emitter of the third NPN transistor  40  is connected to ground, and the emitter of the first PNP transistor  32  is connected to a positive supply voltage. Those persons skilled in the art will recognize that a positive supply voltage of five volts is preferred. 
   When the first input is applied to the input node  26 , the first resistor  34  and the second resistor  36  acts as a voltage divider. If the first input is a one (five volts), the first PNP transistor  32  will be actively biased, sourcing current to the third NPN transistor  40 , and to the source node  30 . 
   The first input is also applied through the input node  26  to the voltage divider formed from the third resistor  44  and the fourth resistor  46 . If the input is zero, the fourth NPN transistor  42  will be actively biased, sinking current from the second PNP transistor  38 . 
   Referring to  FIG. 1 , each current mirror from the first  18  to the Nth  20  will produce a current source if the respective input is a one, and a current sink if the respective input is a zero. Referring again to  FIG. 2 , the source node  30  of the first current mirror  24  and all the remaining source nodes from the second through Nth current mirrors (not shown) are connected in parallel to the source input node  50  of the amplifier  52  shown in  FIG. 3 . Referring again to  FIG. 2 , the sink node  28  of the first current mirror  24  and all the remaining source nodes from the second through Nth current mirrors (not shown) are connected in parallel to the sink input node  54  of the amplifier  52  shown in  FIG. 3 . 
   Because all of the source nodes from all of the current mirrors are connected in parallel to the source input node  50 , the current generated will be equal to the combined input currents divided by the total number of inputs. Likewise, because all of the sink nodes from all of the current mirrors are connected in parallel to the sink input node  54 , the current generated will be equal to the combined input currents divided by the total number of inputs. 
   As shown in  FIG. 3 , the source input node  50  is connected to the base of a fifth NPN transistor  56  by a current connection path. 
   A current connection path connects the base of the sixth PNP transistor  58  to the collector of the sixth PNP transistor  58 . The collector is connected to the collector of the fifth NPN transistor  56 , also by a current connection path. 
   A fifth resistor  60  has a first terminal and a second terminal. The first terminal of the fifth resistor  60  is connected to the emitter of the fifth NPN transistor  56  by a current connection path. 
   A sixth resistor  62  has a first terminal and a second terminal. The first terminal of the sixth resistor  62  is connected to the emitter of the sixth PNP transistor  58  by a current connection path. 
   A seventh PNP transistor  64  has an emitter, a base, and a collector. A current connection path connects the emitter of the seventh PNP transistor  64  to the emitter of the sixth PNP transistor  58 . The base of the seventh PNP transistor  64  is connected to the base of the sixth PNP transistor  58  by a current connection path, and the collector is connected to the second terminal of the fifth resistor  60  by a current connection path. 
   The sixth PNP transistor  58  and the seventh PNP transistor  60  form a current mirror, which generates a control voltage in fifth resistor  60 . 
   A current connection path connects the emitter of the eighth PNP transistor  64  to the second terminal of the sixth resistor  62 . The base of the seventh PNP transistor  64  is connected to the second terminal of the fifth resistor  60  by a current connection path, and the collector is connected to the emitter of the fifth NPN transistor  56  by a current connection path. 
   A current connection path connects the emitter of the ninth NPN transistor  66  to the emitter of the fifth NPN transistor  56 . The base of the ninth NPN transistor  66  is connected to the collector of the ninth NPN transistor  66  by a current connection path. 
   A current connection path connects the emitter of the tenth NPN transistor  66  to the emitter of the fifth NPN transistor  56 . The base of the ninth NPN transistor  66  is connected to the base of the ninth NPN transistor  66  by a current connection path. 
   A current connection path connects the base of the eleventh PNP transistor  70  to the emitter of the eighth PNP transistor  64 . The collector of the eleventh PNP transistor  70  is connected to the collector of the ninth NPN transistor  66  by a current connection path. 
   A current connection path connects the emitter of the twelfth PNP transistor  72  to the emitter of the eleventh PNP transistor  70 , and a current connection path connects the collector of the twelfth PNP transistor  72  to the collector of the tenth NPN transistor  68 . 
   A current connection path connects the emitter of the thirteenth PNP transistor  74  to the emitter of the sixth PNP transistor  58 , and a current connection path connects the collector of the thirteenth PNP transistor  74  to the emitter of the eleventh PNP transistor  70 . 
   A current connection path connects the emitter of the fourteenth PNP transistor  76  to the emitter of the sixth PNP transistor  58 . The base of the fourteenth PNP transistor  76  is connected to the base of the thirteenth PNP  74  transistor by a current connection path, and the collector is connected to the base of the thirteenth PNP transistor  74  by a current connection path. 
   A seventh resistor  78  has a first terminal and a second terminal. The first terminal of the seventh resistor  78  is connected to the emitter of the fifth NPN transistor  56  by a current connection path, and the second terminal is connected to the base of the thirteenth PNP transistor  74  by a current connection path. 
   An eighth resistor  80  has a first terminal and a second terminal. The first terminal of the seventh resistor  78  is connected to the emitter of the fifth NPN transistor  56  by a current connection path, and the second terminal is connected to the base of the twelfth PNP transistor  72  by a current connection path. 
   A current connection path connects the emitter of the fifteenth NPN transistor  82  to the base of the twelfth PNP transistor  72 , and the collector of the fifteenth NPN transistor  82  is connected to the emitter of the sixth PNP transistor  58  by a current connection path. 
   A current connection path connects the emitter of the sixteenth PNP transistor  84  to the emitter of the sixth PNP transistor  58 , the base of the sixteenth PNP transistor  84  is connected to the sink input node  54  by a current connection path, and the collector of the sixteenth PNP transistor  84  is connected to the base of the fifteenth NPN transistor  82  by a current connection path. 
   A ninth resistor  86  has a first terminal and a second terminal. The first terminal of the ninth resistor  86  is connected to the emitter of the fifth NPN transistor  56  by a current connection path, and the second terminal is connected to the base of the fifteenth NPN transistor  82  by a current connection path. 
   A tenth resistor  88  has a first terminal and a second terminal. The first terminal of the tenth resistor  88  is connected to the emitter of the fifth NPN transistor  56  by a current connection path. 
   A current connection path connects the base of the seventeenth PNP transistor  90  to the collector of the seventeenth PNP transistor  90 . The collector of the seventeenth PNP transistor  90  is connected to the second terminal of the tenth resistor  88  by a current connection path. 
   A current connection path connects the emitter of the eighteenth PNP transistor  92  to the emitter of the seventeenth PNP transistor  90 , and a current connection path connects the base of the eighteenth PNP transistor  92  to the base of the seventeenth PNP transistor  90 . 
   A current connection path connects the emitter of the nineteenth PNP transistor  94  to the collector of the eighteenth PNP transistor  92 . The base of the nineteenth PNP transistor  94  is connected by a current connection path to the collector of the tenth PNP transistor  72 , and the collector of the nineteenth PNP transistor  94  is connected to the emitter of the fifth NPN transistor  56  by a current connection path. 
   A current connection path connects the base of the twentieth NPN transistor  96  to the collector of the eighteenth PNP transistor  92 , and the collector of the twentieth NPN transistor  96  is connected to the emitter of the seventeenth PNP transistor  90  by a current connection path. 
   An eleventh resistor  98  has a first terminal and a second terminal. The first terminal of the eleventh resistor  98  is connected to the emitter of the fifth NPN transistor  56  by a current connection path, and the second terminal is connected to the emitter of the twentieth NPN transistor  96  by a current connection path. 
   A twelfth resistor  100  has a first terminal and a second terminal. The first terminal of the twelfth resistor  100  is connected to the emitter of the twentieth NPN transistor  96  by a current connection path. 
   A current connection path connects the emitter of the twenty-first NPN transistor  102  to the emitter of the fifth NPN transistor  56 . The base of the twenty-first NPN transistor is connected to the second terminal of the twelfth resistor  100  by a current connection path, and the collector of the twenty-first NPN transistor  102  is connected to the output node  104  by a current connection path. 
   A thirteenth resistor  106  has a first terminal and a second terminal. The first terminal of the thirteenth resistor  106  is connected to the emitter of the seventeenth PNP transistor  90  by a current connection path, and the second terminal is connected by a current connection path to the collector of the twenty-first NPN transistor  102 . 
   In the preferred embodiment, the emitter of the fifth NPN transistor  56  is connected to ground, and the emitter of the sixth PNP transistor  58 , and the emitter of the seventeenth PNP transistor  90  are connected to a positive supply voltage. Those persons skilled in the art will recognize that a positive supply voltage of five volts is preferred. 
   While the preferred embodiments of the invention have been illustrated and described, it will be apparent to those of ordinary skill in the art that various changes and modifications may be made without deviating from the inventive concepts set forth above.