Logic gate

Logic gate

Overview
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time
Rise time
In electronics, when describing a voltage or current step function, rise time refers to the time required for a signal to change from a specified low value to a specified high value...

 and unlimited fan-out, or it may refer to a non-ideal physical device.
Discussion
Ask a question about 'Logic gate'
Start a new discussion about 'Logic gate'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Encyclopedia
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time
Rise time
In electronics, when describing a voltage or current step function, rise time refers to the time required for a signal to change from a specified low value to a specified high value...

 and unlimited fan-out, or it may refer to a non-ideal physical device. (see Ideal and real op-amps for comparison)

Logic gates are primarily implemented using diode
Diode
In electronics, a diode is a type of two-terminal electronic component with a nonlinear current–voltage characteristic. A semiconductor diode, the most common type today, is a crystalline piece of semiconductor material connected to two electrical terminals...

s or transistor
Transistor
A transistor is a semiconductor device used to amplify and switch electronic signals and power. It is composed of a semiconductor material with at least three terminals for connection to an external circuit. A voltage or current applied to one pair of the transistor's terminals changes the current...

s acting as electronic switches, but can also be constructed using electromagnetic relay
Relay
A relay is an electrically operated switch. Many relays use an electromagnet to operate a switching mechanism mechanically, but other operating principles are also used. Relays are used where it is necessary to control a circuit by a low-power signal , or where several circuits must be controlled...

s (relay logic
Relay logic
Relay logic is a method of controlling industrial electronic circuits by using relays and contacts.-Ladder logic:The schematic diagrams for relay logic circuits are often called line diagrams, because the inputs and outputs are essentially drawn in a series of lines...

), fluidic logic, pneumatic logic, optics
Optics
Optics is the branch of physics which involves the behavior and properties of light, including its interactions with matter and the construction of instruments that use or detect it. Optics usually describes the behavior of visible, ultraviolet, and infrared light...

, molecules
Molecular logic gate
A molecular logic gate is a molecule that performs a logical operation on one or more logic inputs and produces a single logic output. Much academic research is dedicated to the development of these systems and several prototypes now exist...

, or even mechanical
Analytical engine
The Analytical Engine was a proposed mechanical general-purpose computer designed by English mathematician Charles Babbage. It was first described in 1837 as the successor to Babbage's difference engine, a design for a mechanical calculator...

 elements. With amplification, logic gates can be cascaded in the same way that Boolean functions can be composed, allowing the construction of a physical model of all of Boolean logic
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...

, and therefore, all of the algorithms and mathematics that can be described with Boolean logic.

Background



The simplest form of electronic logic is diode logic
Diode logic
Diode logic or diode-resistor logic constructs Boolean logic gates from diodes acting as electrically operated switches. While diode logic has the advantage of simplicity, the lack of an amplifying stage in each gate limits its application...

. This allows AND and OR gates to be built, but not inverters, and so is an incomplete form of logic. Further, without some kind of amplification it is not possible to have such basic logic operations cascaded as required for more complex logic functions. To build a functionally complete logic system, relay
Relay
A relay is an electrically operated switch. Many relays use an electromagnet to operate a switching mechanism mechanically, but other operating principles are also used. Relays are used where it is necessary to control a circuit by a low-power signal , or where several circuits must be controlled...

s, valves (vacuum tubes), or transistor
Transistor
A transistor is a semiconductor device used to amplify and switch electronic signals and power. It is composed of a semiconductor material with at least three terminals for connection to an external circuit. A voltage or current applied to one pair of the transistor's terminals changes the current...

s can be used. The simplest family of logic gates using bipolar transistors is called resistor-transistor logic
Resistor-transistor logic
Resistor–transistor logic is a class of digital circuits built using resistors as the input network and bipolar junction transistors as switching devices...

 (RTL). Unlike diode logic gates, RTL gates can be cascaded indefinitely to produce more complex logic functions. These gates were used in early integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

s. For higher speed, the resistors used in RTL were replaced by diodes, leading to diode-transistor logic
Diode-transistor logic
Diode–transistor logic is a class of digital circuits that is the direct ancestor of transistor–transistor logic. It is called so because the logic gating function is performed by a diode network and the amplifying function is performed by a transistor .- Implementations :The DTL circuit shown in...

 (DTL). Transistor-transistor logic
Transistor-transistor logic
Transistor–transistor logic is a class of digital circuits built from bipolar junction transistors and resistors. It is called transistor–transistor logic because both the logic gating function and the amplifying function are performed by transistors .TTL is notable for being a widespread...

 (TTL) then supplanted DTL with the observation that one transistor could do the job of two diodes even more quickly, using only half the space. In virtually every type of contemporary chip implementation of digital systems, the bipolar transistors have been replaced by complementary field-effect transistor
Field-effect transistor
The field-effect transistor is a transistor that relies on an electric field to control the shape and hence the conductivity of a channel of one type of charge carrier in a semiconductor material. FETs are sometimes called unipolar transistors to contrast their single-carrier-type operation with...

s (MOSFET
MOSFET
The metal–oxide–semiconductor field-effect transistor is a transistor used for amplifying or switching electronic signals. The basic principle of this kind of transistor was first patented by Julius Edgar Lilienfeld in 1925...

s) to reduce size and power consumption still further, thereby resulting in complementary metal–oxide–semiconductor (CMOS
CMOS
Complementary metal–oxide–semiconductor is a technology for constructing integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits...

) logic.

For small-scale logic, designers now use prefabricated logic gates from families of devices such as the TTL
Transistor-transistor logic
Transistor–transistor logic is a class of digital circuits built from bipolar junction transistors and resistors. It is called transistor–transistor logic because both the logic gating function and the amplifying function are performed by transistors .TTL is notable for being a widespread...

 7400 series
7400 series
The 7400 series of transistor-transistor logic integrated circuits are historically important as the first widespread family of TTL integrated circuit logic. It was used to build the mini and mainframe computers of the 1960s and 1970s...

 by Texas Instruments
Texas Instruments
Texas Instruments Inc. , widely known as TI, is an American company based in Dallas, Texas, United States, which develops and commercializes semiconductor and computer technology...

 and the CMOS
CMOS
Complementary metal–oxide–semiconductor is a technology for constructing integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits...

 4000 series
4000 series
The 4000 series is a family of industry standard integrated circuits which implement a variety of logic functions using Complementary Metal–Oxide–Semiconductor technology, and are still in use today. They were introduced by RCA as CD4000 COS/MOS series in 1968, as a lower power and more versatile...

 by RCA
RCA
RCA Corporation, founded as the Radio Corporation of America, was an American electronics company in existence from 1919 to 1986. The RCA trademark is currently owned by the French conglomerate Technicolor SA through RCA Trademark Management S.A., a company owned by Technicolor...

, and their more recent descendants. Increasingly, these fixed-function logic gates are being replaced by programmable logic device
Programmable logic device
A programmable logic device or PLD is an electronic component used to build reconfigurable digital circuits. Unlike a logic gate, which has a fixed function, a PLD has an undefined function at the time of manufacture...

s, which allow designers to pack a large number of mixed logic gates into a single integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

. The field-programmable nature of programmable logic device
Programmable logic device
A programmable logic device or PLD is an electronic component used to build reconfigurable digital circuits. Unlike a logic gate, which has a fixed function, a PLD has an undefined function at the time of manufacture...

s such as FPGA
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...

s has removed the 'hard' property of hardware; it is now possible to change the logic design of a hardware system by reprogramming some of its components, thus allowing the features or function of a hardware implementation of a logic system to be changed.

Electronic logic gates differ significantly from their relay-and-switch equivalents. They are much faster, consume much less power, and are much smaller (all by a factor of a million or more in most cases). Also, there is a fundamental structural difference. The switch circuit creates a continuous metallic path for current to flow (in either direction) between its input and its output. The semiconductor logic gate, on the other hand, acts as a high-gain
Gain
In electronics, gain is a measure of the ability of a circuit to increase the power or amplitude of a signal from the input to the output. It is usually defined as the mean ratio of the signal output of a system to the signal input of the same system. It may also be defined on a logarithmic scale,...

 voltage
Voltage
Voltage, otherwise known as electrical potential difference or electric tension is the difference in electric potential between two points — or the difference in electric potential energy per unit charge between two points...

 amplifier
Electronic amplifier
An electronic amplifier is a device for increasing the power of a signal.It does this by taking energy from a power supply and controlling the output to match the input signal shape but with a larger amplitude...

, which sinks a tiny current at its input and produces a low-impedance voltage at its output. It is not possible for current to flow between the output and the input of a semiconductor logic gate.

Another important advantage of standardized integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

 logic families, such as the 7400 and 4000 families, is that they can be cascaded. This means that the output of one gate can be wired to the inputs of one or several other gates, and so on. Systems with varying degrees of complexity can be built without great concern of the designer for the internal workings of the gates, provided the limitations of each integrated circuit are considered.

The output of one gate can only drive a finite number of inputs to other gates, a number called the 'fanout
Fanout
In digital electronics, the fan-out of a logic gate output is the number of gate inputs to which it is connected.In most designs, logic gates are connected together to form more complex circuits. While no more than one logic gate output is connected to any single input, it is common for one output...

 limit'. Also, there is always a delay, called the 'propagation delay
Propagation delay
Propagation delay is a technical term that can have a different meaning depending on the context. It can relate to networking, electronics or physics...

', from a change in input of a gate to the corresponding change in its output. When gates are cascaded, the total propagation delay is approximately the sum of the individual delays, an effect which can become a problem in high-speed circuits. Additional delay can be caused when a large number of inputs are connected to an output, due to the distributed capacitance
Capacitance
In electromagnetism and electronics, capacitance is the ability of a capacitor to store energy in an electric field. Capacitance is also a measure of the amount of electric potential energy stored for a given electric potential. A common form of energy storage device is a parallel-plate capacitor...

 of all the inputs and wiring and the finite amount of current that each output can provide.

Logic gates



All other types of Boolean logic gates (i.e., AND
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...

, OR
OR gate
The OR gate is a digital logic gate that implements logical disjunction - it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH . If neither input is HIGH, a LOW output results...

, NOT, XOR
XOR gate
The XOR gate is a digital logic gate that implements an exclusive or; that is, a true output results if one, and only one, of the inputs to the gate is true . If both inputs are false or both are true , a false output results. Its behavior is summarized in the truth table shown on the right...

, XNOR
XNOR gate
The XNOR gate is a digital logic gate whose function is the inverse of the exclusive OR gate. The two-input version implements logical equality, behaving according to the truth table to the right. A HIGH output results if both of the inputs to the gate are the same...

) can be created from a suitable network of NAND
NAND gate
The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the right. A LOW output results only if both the inputs to the gate are HIGH...

 gates. Similarly all gates can be created from a network of NOR
NOR gate
The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output results if both the inputs to the gate are LOW . If one or both input is HIGH , a LOW output results. NOR is the result of the negation of the OR operator...

 gates. Historically, NAND gates were easier to construct from MOS technology and thus NAND gates served as the first pillar of Boolean logic in electronic computation.

For an input of 2 boolean variables, there are 16 possible boolean algebraic functions. These 16 functions are enumerated below, together with their outputs for each combination of input variables.
The four functions denoted by arrows are the logical implication functions. These functions are not usually implemented as elementary circuits, but rather as combinations of a gate with an inverter at one input.

Symbols



There are two sets of symbols for elementary logic gates in common use, both defined in ANSI
American National Standards Institute
The American National Standards Institute is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organization also coordinates U.S. standards with international...

/IEEE
Institute of Electrical and Electronics Engineers
The Institute of Electrical and Electronics Engineers is a non-profit professional association headquartered in New York City that is dedicated to advancing technological innovation and excellence...

 Std 91-1984 and its supplement ANSI/IEEE Std 91a-1991. The "distinctive shape" set, based on traditional schematics, is used for simple drawings, and derives from MIL-STD-806 of the 1950s and 1960s. It is sometimes unofficially described as "military", reflecting its origin. The "rectangular shape" set, based on IEC
International Electrotechnical Commission
The International Electrotechnical Commission is a non-profit, non-governmental international standards organization that prepares and publishes International Standards for all electrical, electronic and related technologies – collectively known as "electrotechnology"...

 60617-12 and other early industry standards, has rectangular outlines for all types of gate, and allows representation of a much wider range of devices than is possible with the traditional symbols. The IEC's system has been adopted by other standards, such as EN
European Committee for Standardization
The European Committee for Standardization or Comité Européen de Normalisation , is a non-profit organisation whose mission is to foster the European economy in global trading, the welfare of European citizens and the environment by providing an efficient infrastructure to interested parties for...

 60617-12:1999 in Europe and BS EN 60617-12:1999 in the United Kingdom.

The goal of IEEE Std 91-1984 was to provide a uniform method of describing the complex logic functions of digital circuits with schematic symbols. These functions were more complex than simple AND and OR gates. They could be medium scale circuits such as a 4-bit counter to a large scale circuits such as a microprocessor. IEC 617-12 and its successor IEC 60617-12 do not explicitly show the "distinctive shape" symbols, but do not prohibit them. http://focus.ti.com/lit/ml/sdyz001a/sdyz001a.pdf These are, however, shown in ANSI/IEEE 91 (and 91a) with this note: "The distinctive-shape symbol is, according to IEC Publication 617, Part 12, not preferred, but is not considered to be in contradiction to that standard." This compromise was reached between the respective IEEE and IEC working groups to permit the IEEE and IEC standards to be in mutual compliance with one another.

In the 1980s, schematics were the predominant method to design both circuit boards and custom ICs known as gate array
Gate array
A gate array or uncommitted logic array is an approach to the design and manufacture of application-specific integrated circuits...

s. Today custom ICs and the field-programmable gate array
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...

 are typically designed with Hardware Description Languages
Hardware description language
In electronics, a hardware description language or HDL is any language from a class of computer languages, specification languages, or modeling languages for formal description and design of electronic circuits, and most-commonly, digital logic...

 (HDL) such as Verilog
Verilog
In the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...

 or VHDL.
Type Distinctive shape Rectangular shape Boolean algebra between A & B Truth table
AND
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...

INPUT OUTPUT
A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1
OR
OR gate
The OR gate is a digital logic gate that implements logical disjunction - it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH . If neither input is HIGH, a LOW output results...

INPUT OUTPUT
A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1
NOT
INPUT OUTPUT
A NOT A
0 1
1 0
In electronics a NOT gate is more commonly called an inverter. The circle on the symbol is called a bubble, and is used in logic diagrams to indicate a logic negation between the external logic state and the internal logic state (1 to 0 or vice versa). On a circuit diagram it must be accompanied by a statement asserting that the positive logic convention or negative logic convention is being used (high voltage level = 1 or high voltage level = 0, respectively). The wedge is used in circuit diagrams to directly indicate an active-low (high voltage level = 0) input or output without requiring a uniform convention throughout the circuit diagram. This is called Direct Polarity Indication. See IEEE Std 91/91A and IEC 60617-12. Both the bubble and the wedge can be used on distinctive-shape and rectangular-shape symbols on circuit diagrams, depending on the logic convention used. On pure logic diagrams, only the bubble is meaningful.
NAND
NAND gate
The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the right. A LOW output results only if both the inputs to the gate are HIGH...

INPUT OUTPUT
A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0
NOR
NOR gate
The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output results if both the inputs to the gate are LOW . If one or both input is HIGH , a LOW output results. NOR is the result of the negation of the OR operator...

INPUT OUTPUT
A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0
XOR
XOR gate
The XOR gate is a digital logic gate that implements an exclusive or; that is, a true output results if one, and only one, of the inputs to the gate is true . If both inputs are false or both are true , a false output results. Its behavior is summarized in the truth table shown on the right...

INPUT OUTPUT
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
XNOR
XNOR gate
The XNOR gate is a digital logic gate whose function is the inverse of the exclusive OR gate. The two-input version implements logical equality, behaving according to the truth table to the right. A HIGH output results if both of the inputs to the gate are the same...

or
INPUT OUTPUT
A B A XNOR B
0 0 1
0 1 0
1 0 0
1 1 1


Two more gates are the exclusive-OR or XOR function and its inverse, exclusive-NOR or XNOR. The two input Exclusive-OR is true only when the two input values are different, false if they are equal, regardless of the value. If there are more than two inputs, the gate generates a true at its output if the number of trues at its input is odd (http://www-inst.eecs.berkeley.edu/~cs61c/resources/dg-BOOL-handout.pdf). In practice, these gates are built from combinations of simpler logic gates.

Universal logic gates




Charles Sanders Peirce (winter of 1880–81) showed that NOR gates alone (or alternatively NAND gates alone) can be used to reproduce the functions of all the other logic gates, but his work on it was unpublished until 1933. The first published proof was by Henry M. Sheffer
Henry M. Sheffer
Henry Maurice Sheffer was an American logician.Sheffer was a Polish Jew born in the western Ukraine, who immigrated to the USA in 1892 with his parents and six siblings. He studied at the Boston Latin School before entering Harvard University, learning logic from Josiah Royce, and completing his...

 in 1913, so the NAND logical operation is sometimes called Sheffer stroke
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...

; the logical NOR
Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...

 is sometimes called Peirce's arrow. Consequently, these gates are sometimes called universal logic gates.

De Morgan equivalent symbols


By use of De Morgan's theorem, an AND function is identical to an OR function with negated inputs and outputs. Likewise, an OR function is identical to an AND function with negated inputs and outputs. Similarly, a NAND gate is equivalent to an OR gate with negated inputs, and a NOR gate is equivalent to an AND gate with negated inputs.

This leads to an alternative set of symbols for basic gates that use the opposite core symbol (AND or OR) but with the inputs and outputs negated or inverted. Use of these alternative symbols can make logic circuit diagrams much clearer and help to show accidental connection of an active high output to an active low input or vice-versa. Any connection that has logic negations at both ends can be replaced by a negationless connection and a suitable change of gate or vice-versa. Any connection that has a negation at one end and no negation at the other can be made easier to interpret by instead using the De Morgan equivalent symbol at either of the two ends. When negation or polarity indicators on both ends of a connection match, there is no logic negation in that path (effectively, bubbles "cancel"), making it easier to follow logic states from one symbol to the next. This is commonly seen in real logic diagrams - thus the reader must not get into the habit of associating the shapes exclusively as OR or AND shapes, but also take into account the bubbles at both inputs and outputs in order to determine the "true" logic function indicated.

All logic relations can be realized by using NAND gates (this can also be done using NOR gates). De Morgan's theorem is most commonly used to transform all logic gates to NAND gates or NOR gates. This is done mainly since it is easy to buy logic gates in bulk and because many electronics labs stock only NAND and NOR gates.

Data storage


Logic gates can also be used to store data. A storage element can be constructed by connecting several gates in a "latch" circuit. More complicated designs that use clock signal
Clock signal
In electronics and especially synchronous digital circuits, a clock signal is a particular type of signal that oscillates between a high and a low state and is utilized like a metronome to coordinate actions of circuits...

s and that change only on a rising or falling edge of the clock are called edge-triggered "flip-flop
Flip-flop (electronics)
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic...

s". The combination of multiple flip-flops in parallel, to store a multiple-bit value, is known as a register. When using any of these gate setups the overall system has memory; it is then called a sequential logic
Sequential logic
In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic, whose output is a function of, and only of, the present input...

 system since its output can be influenced by its previous state(s).

These logic circuits are known as computer memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

. They vary in performance, based on factors of speed, complexity, and reliability of storage, and many different types of designs are used based on the application.

Three-state logic gates




Three-state, or 3-state, logic gates are a type of logic gates that have three states of the output: high (H), low (L) and high-impedance (Z). The high-impedance state plays no role in the logic, which remains strictly binary. These devices are used on buses also known as the Data Buses of the CPU to allow multiple chips to send data. A group of three-states driving a line with a suitable control circuit is basically equivalent to a multiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...

, which may be physically distributed over separate devices or plug-in cards.

In electronics, a high output would mean the output is sourcing current from the positive power terminal (positive voltage). A low output would mean the output is sinking current to the negative power terminal (zero voltage). High impedance would mean that the output is effectively disconnected from the circuit.

'Tri-state', a widely-used synonym of 'three-state', is a trademark of the National Semiconductor Corporation
National Semiconductor
National Semiconductor was an American semiconductor manufacturer, that specialized in analog devices and subsystems,formerly headquartered in Santa Clara, California, USA. The products of National Semiconductor included power management circuits, display drivers, audio and operational amplifiers,...

.

Miscellaneous


Logic circuits include such devices as multiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...

s, registers
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...

, arithmetic logic unit
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...

s (ALUs), and computer memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

, all the way up through complete microprocessor
Microprocessor
A microprocessor incorporates the functions of a computer's central processing unit on a single integrated circuit, or at most a few integrated circuits. It is a multipurpose, programmable device that accepts digital data as input, processes it according to instructions stored in its memory, and...

s, which may contain more than 100 million gates. In practice, the gates are made from field-effect transistor
Field-effect transistor
The field-effect transistor is a transistor that relies on an electric field to control the shape and hence the conductivity of a channel of one type of charge carrier in a semiconductor material. FETs are sometimes called unipolar transistors to contrast their single-carrier-type operation with...

s (FETs), particularly MOSFET
MOSFET
The metal–oxide–semiconductor field-effect transistor is a transistor used for amplifying or switching electronic signals. The basic principle of this kind of transistor was first patented by Julius Edgar Lilienfeld in 1925...

s (metal–oxide–semiconductor field-effect transistors).

Compound logic gates AND-OR-Invert
AND-OR-Invert
AND-OR-Invert logic and AOI gates are two-level compound logic functions constructed from the combination of one or more AND gates followed by a NOR gate. Construction of AOI cells is particularly efficient using CMOS technology where the total number of transistor gates can be compared to the...

 (AOI) and OR-AND-Invert (OAI) are often employed in circuit design because their construction using MOSFET's is simpler and more efficient than the sum of the individual gates.

In reversible logic
Reversible computing
Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...

, Toffoli gate
Toffoli gate
In computer science, the Toffoli gate , invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates...

s are used.

History and development


In a 1886 letter, Charles Sanders Peirce described how logical operations could be carried out by electrical switching circuits. Starting in 1898, Nikola Tesla
Nikola Tesla
Nikola Tesla was a Serbian-American inventor, mechanical engineer, and electrical engineer...

 filed for patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....

s of devices containing electro-mechanical logic gate circuits (see List of Tesla patents). Eventually, vacuum tube
Vacuum tube
In electronics, a vacuum tube, electron tube , or thermionic valve , reduced to simply "tube" or "valve" in everyday parlance, is a device that relies on the flow of electric current through a vacuum...

s replaced relays for logic operations. Lee De Forest
Lee De Forest
Lee De Forest was an American inventor with over 180 patents to his credit. De Forest invented the Audion, a vacuum tube that takes relatively weak electrical signals and amplifies them. De Forest is one of the fathers of the "electronic age", as the Audion helped to usher in the widespread use...

's modification, in 1907, of the Fleming valve
Vacuum tube
In electronics, a vacuum tube, electron tube , or thermionic valve , reduced to simply "tube" or "valve" in everyday parlance, is a device that relies on the flow of electric current through a vacuum...

 can be used as AND logic gate. Ludwig Wittgenstein
Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein was an Austrian philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He was professor in philosophy at the University of Cambridge from 1939 until 1947...

 introduced a version of the 16-row truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

, which is shown above, as proposition 5.101 of Tractatus Logico-Philosophicus
Tractatus Logico-Philosophicus
The Tractatus Logico-Philosophicus is the only book-length philosophical work published by the Austrian philosopher Ludwig Wittgenstein in his lifetime. It was an ambitious project: to identify the relationship between language and reality and to define the limits of science...

(1921). Claude E. Shannon introduced the use of Boolean algebra in the analysis and design of switching circuits in 1937. Walther Bothe
Walther Bothe
Walther Wilhelm Georg Bothe was a German nuclear physicist, who shared the Nobel Prize in Physics in 1954 with Max Born....

, inventor of the coincidence circuit
Coincidence circuit
In physics, a coincidence circuit is an electronic device with one output and two inputs. The output is activated only when signals are received within a time window accepted as at the same time and in parallel at both inputs...

, got part of the 1954 Nobel Prize
Nobel Prize
The Nobel Prizes are annual international awards bestowed by Scandinavian committees in recognition of cultural and scientific advances. The will of the Swedish chemist Alfred Nobel, the inventor of dynamite, established the prizes in 1895...

 in physics, for the first modern electronic AND gate in 1924. Active research is taking place in molecular logic gate
Molecular logic gate
A molecular logic gate is a molecule that performs a logical operation on one or more logic inputs and produces a single logic output. Much academic research is dedicated to the development of these systems and several prototypes now exist...

s.

Implementations


Since the 1990s, most logic gates are made of CMOS
CMOS
Complementary metal–oxide–semiconductor is a technology for constructing integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits...

 transistors (i.e. NMOS and PMOS transistors are used). Often millions of logic gates are packaged in a single integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

.

There are several logic families
Logic family
In computer engineering, a logic family may refer to one of two related concepts. A logic family of monolithic digital integrated circuit devices is a group of electronic logic gates constructed using one of several different designs, usually with compatible logic levels and power supply...

 with different characteristics (power consumption, speed, cost, size) such as: RDL
Diode logic
Diode logic or diode-resistor logic constructs Boolean logic gates from diodes acting as electrically operated switches. While diode logic has the advantage of simplicity, the lack of an amplifying stage in each gate limits its application...

 (resistor-diode logic), RTL
Resistor-transistor logic
Resistor–transistor logic is a class of digital circuits built using resistors as the input network and bipolar junction transistors as switching devices...

 (resistor-transistor logic), DTL
Diode-transistor logic
Diode–transistor logic is a class of digital circuits that is the direct ancestor of transistor–transistor logic. It is called so because the logic gating function is performed by a diode network and the amplifying function is performed by a transistor .- Implementations :The DTL circuit shown in...

 (diode-transistor logic), TTL
Transistor-transistor logic
Transistor–transistor logic is a class of digital circuits built from bipolar junction transistors and resistors. It is called transistor–transistor logic because both the logic gating function and the amplifying function are performed by transistors .TTL is notable for being a widespread...

 (transistor-transistor logic) and CMOS
CMOS
Complementary metal–oxide–semiconductor is a technology for constructing integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits...

 (complementary metal oxide semiconductor). There are also sub-variants, e.g. standard CMOS logic vs. advanced types using still CMOS technology, but with some optimizations for avoiding loss of speed due to slower PMOS transistors.

Non-electronic implementations are varied, though few of them are used in practical applications. Many early electromechanical digital computers, such as the Harvard Mark I
Harvard Mark I
The IBM Automatic Sequence Controlled Calculator , called the Mark I by Harvard University, was an electro-mechanical computer....

, were built from relay logic
Relay logic
Relay logic is a method of controlling industrial electronic circuits by using relays and contacts.-Ladder logic:The schematic diagrams for relay logic circuits are often called line diagrams, because the inputs and outputs are essentially drawn in a series of lines...

 gates, using electro-mechanical relay
Relay
A relay is an electrically operated switch. Many relays use an electromagnet to operate a switching mechanism mechanically, but other operating principles are also used. Relays are used where it is necessary to control a circuit by a low-power signal , or where several circuits must be controlled...

s. Logic gates can be made using pneumatic devices, such as the Sorteberg relay
Sorteberg relay
The Sorteberg relay, or Sorteberg force bridge pneumatic relay is a form of analog pneumatic computer, calibrated to calculate a predefined function. They were sold by Sorteberg Controls Corp....

 or mechanical logic gates, including on a molecular scale. Logic gates have been made out of DNA
DNA
Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...

 (see DNA nanotechnology
DNA nanotechnology
DNA nanotechnology is a branch of nanotechnology which uses the molecular recognition properties of DNA and other nucleic acids to create designed, artificial structures out of DNA for technological purposes. In this field, DNA is used as a structural material rather than as a carrier of genetic...

) and used to create a computer called MAYA (see MAYA II). Logic gates can be made from quantum mechanical
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...

 effects (though quantum computing usually diverges from boolean design). Photonic logic gates use non-linear optical effects

See also

  • And-inverter graph
    And-inverter graph
    An and-inverter graph is a directed, acyclic graph that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labeled with variable names, and edges optionally containing...

  • Boolean algebra topics
  • Boolean function
  • Digital circuit
    Digital circuit
    Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...

  • Espresso heuristic logic minimizer
  • Fanout
    Fanout
    In digital electronics, the fan-out of a logic gate output is the number of gate inputs to which it is connected.In most designs, logic gates are connected together to form more complex circuits. While no more than one logic gate output is connected to any single input, it is common for one output...

  • Flip-flop (electronics)
    Flip-flop (electronics)
    In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic...

  • Karnaugh map
    Karnaugh map
    The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...

  • Combinational logic
    Combinational logic
    In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...

  • Logic family
    Logic family
    In computer engineering, a logic family may refer to one of two related concepts. A logic family of monolithic digital integrated circuit devices is a group of electronic logic gates constructed using one of several different designs, usually with compatible logic levels and power supply...

  • Logical graph
    Logical graph
    A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....

  • NMOS logic
    NMOS logic
    N-type metal-oxide-semiconductor logic uses n-type metal-oxide-semiconductor field effect transistors to implement logic gates and other digital circuits...

  • Propositional calculus
    Propositional calculus
    In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...

  • Race hazard
  • Reversible computing
    Reversible computing
    Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...

  • Truth table
    Truth table
    A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...


Further reading

  • Awschalom, D., D. Loss, and N. Samarth, Semiconductor Spintronics and Quantum Computation (2002), Springer-Verlag, Berlin, Germany.
  • Bostock, Geoff, Programmable Logic Devices. Technology and Applications (1988), McGraw-Hill, New York, NY.
  • Brown, Stephen D. et al., Field-Programmable Gate Arrays (1992), Kluwer Academic Publishers, Boston, MA.

External links