less_retarded_wiki

Logic Circuit

Logic circuits are circuits made of logic gates that implement Boolean functions, i.e. they are "schematics to process 1s and 0s". They are used to design computers. Logic circuits are a bit similar to electronic circuits but are a level of abstraction higher: they don't work with continuous voltages but rather with discrete binary logic values: 1s and 0s. Logical circuits can be designed and simulated with specialized software and languages such as VHDL.

Generally a logic circuit has N input bits and M output bits. Then we divide logic circuits into two main categories:

• combinational: The output values only depend on the input values, i.e. the circuit implements a pure mathematical function. Behavior of such circuit can be described with a truth table, i.e. a table that for any combination of input values list their corresponding output.
• sequential: The output values generally depend on the input values and the internal state of the circuit, i.e. the circuit has a kind of memory (it can be seen as a finite state machine). The internal state is normally implemented with so called flip-flops (logic gates that take as input their own output). Truth tables can't be used for describing these circuits. These circuits also often work with clock synchronization, i.e. they have a specialized input called clock that periodically switches between 1 and 0 which drives the circuit's operation (this is where overclocking comes from).

With logic circuits it is possible to implement any boolean function; undecidability doesn't apply here as we're not dealing with Turing machines computations because the output always has a finite, fixed width, the computation can't end up in an infinite loop as there are no repeating steps, just a straightforward propagation of input values to the output. It is always possible to implement any function at least as a look up table (which can be created with a multiplexer).

Once we've designed a logic circuit, we can optimize it which usually means making it use fewer logic gates, i.e. make it cheaper to manufacture (but optimization can also aim for other things, e.g. shortening the maximum length from input to output, i.e. minimizing the circuit's delay). The optimization can be done with a number of techniques such as manual simplification of the circuit's logic expression or with Karnaugh maps.

Some common logic circuits include:

• adder: Performs addition. It has many parameters such as the bit width, optional carry output etc.
• multiplier: Performs multiplication.
• multiplexer (mux): Has M address input bits plus another 2^M data input bits. The output of the gate is the value of Nth data bit where N is the number specified by the address input. I.e. the circuit selects one of its inputs and sends it to the output. This can be used to implement e.g. memory, look up tables, bus arbiters and many more things.
• demultiplexer (demux): Does the opposite of multiplexer, i.e. has one M address inputs and 1 data input and 2^M outputs. Depending on the given address, the input is redirected to Nth output (while other outputs are 0).
• decoder: Has M inputs and 2^M outputs. It sets Nth output to 1 (others are 0) where N is the binary number on the input. I.e. decoder converts a binary number into one specific signal. It can be implemented as a demultiplexer whose data input is always 1.
• encoder: Does the opposite of encoder, i.e. has 2^M inputs and M outputs, expects exactly one of the inputs to be 1 and the rest 0s, the output is a binary number representing the input that's 1.
• ALU (arithmetic logic unit): A more complex circuit capable of performing a number of logic and arithmetic operations. It is a part of a CPU.
• TODO: more

Example

TODO

All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.