w1 Flashcards
combinatorial circuit
When gates are connected such that an output of one gate is never connected to one of its inputs, not even via other gates
a circuit where outputs are connected to inputs
sequential circuit
a two-way multiplexer
If the selector sel is 0, the output out equals in1 and if sel is 1, the output is equal to in2
the output is 1 only if exactly one input is equal to 0. - Draw a circuit realising this function
Implement an and gate with three inputs and a three-input or gate using only the basic and, or and not gates. Generalise to an n input and gate and n input or gate. How many basic gates are necessary? Can you give a proof?
The nand gate
¬(in1∧in2)
The nor gate
¬(in1∨in2)
The buffer gate and why it exists
Buffers are often used to enhance the input signal. If the buffer is sufficiently strong, in which case it is called an amplifier, it can even be used to drive a light or a motor.
The xor gate
The xnor gate
in1↔in2
the parity function
the output is 1 if the number of inputs equal to 1 is odd
can be for more than 3 inputs too
could also be constructed with nand gates
transistors
were first demonstrated by Bardeen, Brattain, and Shockley in 1947, although the concept was patented two decades earlier.
are constructed by covering specific parts of pure semiconductor wafers, made of e.g. silicon or germanium, with dopants, such as boron and phosphorus. Doping changes the available charge carriers of a semiconductor, thereby affecting its conductivity in very precise ways and places
if a small current flows from the base to the emitter than a big current can flow from the collector to the emitter. Otherwise isolated.
main types of transistors
the bipolar transistor and the FET (Field Effect Transistor)
FETs are more energy efficient and faster than bipolar transistors, so nobody uses bipolar anymore
FET
has three connections, a gate G, a source S and a drain D
By putting a positive voltage on the gate relative to the source, electrons can be pushed away or be attracted to form or break an electrical connection between the source and the drain
MOSFET
Metal Oxide Semiconductor FET
the gate is made of metal which is isolated using an oxide layer from the connection between the source and the drain
nMOSFET: elements, how it works
If the voltage at the gate is sufficiently higher than the voltage at the source, electrons are pulled to the gate. If there are enough electrons, they can seep away to the drain, and a current can flow from the drain to the source.
If the voltage at the gate is equal to the voltage at the source, there are no free electrons to carry the current, and the connection between drain and source acts as an insulator.
pMOSFET: structure, how it works
a current can flow if electrons are pushed away from the gate. If the voltage at the gate is sufficiently lower than that of the source, there are free holes for electrons to travel from the drain to the source and current can flow freely. If the voltage at the gate and the source are the same, the connection between the source and the drain behaves as an insulator.
CMOS
Complementary MOS
first you had to use either pMOSFET or nMOSFET + resistors
then they started to use both types together, they complement each other and you don’t need resistors. This approach is CMOS
how the not gate works
A high-voltage is a logical 1 and a low voltage is a logical 0. When a high-voltage is put on the input in, the nMOSFET is on and the pMOSFET is off. The voltage at the output out is pulled down, meaning the logical 1 is inverted to a logical 0. In contrast, when a low voltage is put on the input in, the pMOSFET is on and the nMOSFET is off. The output out is pulled up. The logical 0 is inverted in a logical 1.
switching delays: why, influence
Transistors are physical objects. switching can still take several picoseconds.
influence of delays:
- digital circuits have a maximum speed at which they can operate
- glitch: a temporary change in voltage or logic level before the level settles at the intended value
The circuit on the pic should always output 0. But some time passes between the moment in switches to 1 and out1 switches to 0, and therefore out produces 1 for this time.
Solution: For a digital circuit, it is important to wait sufficiently long to be sure that all glitches have levelled out and the circuit has become stable
Moore’s law
In 1965 Moore wrote a short note in which he observed that the number of transistors that could be put on a wafer was growing exponentially with time. He predicted that if the growth was sustained, wonders such as a computer in each home (“or at least a terminal to a central computer”) would take place
Until about 2014, an increase in the clock speed followed the increase in transistor counts. Because of physical limitations, this increase in clock speed stopped. Modern architectures obtain more performance by increasing the level of parallelism, for instance, by increasing the number of processor cores
what are these?
these are TTL, old-fashioned transistors. These all use current, it flows through the route with arrows. They heat up. Modern computers don’t use those.
and, or, and after the break
minterm
corresponds to every line in the truth table where the result is 1
the conjunction of all inputs;
the input is negated if the truth table contains 0 at that point
the minterm of the line 1 0 0 is in1 ∧ ¬in2 ∧ ¬in3
disjunctive normal form
the disjunction of all minterms that represents the truth table
how to construct a circuit from a disjunctive normal form?
it’s a circuit of and gates feeding into an or gate
Due to duality, it is also possible to directly construct a circuit consisting of or gates feeding into an and gate
construct a circuit from this
maxterm
a logical expression used for constructing circuits consisting of or gates feeding into an and gate
are constructed for each entry in the truth table where the result is 0
the disjunction of all inputs, where each input that is equal to 1 is negated
conjunctive normal form
the conjunction of all maxterms
construct the conjunctive normal form and the associated circuit
tool to obtain a minimal two-layer circuit for up to five inputs
Karnaugh maps
write a truth table in a matrix of dimension 2 × 2, 2 × 4, 4 × 4 or even 8 × 4
To make a disjunctive circuit, clusters of neighbours of size 2k × 2l for k, l = 0,1,2,… must be selected that cover exactly all 1’s in the Karnaugh map.
By putting disjunctions between the expressions expressing clusters we obtain an expression that is exactly 1 when the truth table is also 1
this expression can immediately be transformed into a two-layer circuit, which is minimal
Dually, by covering the 0’s in a Karnaugh map, a conjunctive circuit can be created
create a conjunctive circuit
find maximal clusters of neighbouring nodes that have a value of 0
write down a maxterm that equals 1 outside the cluster
There are three clusters that correspond to ¬a∨c, ¬b∨d, and b∨c. The minimal conjunctive two-layer expression corresponding to the truth table is (¬a∨c)∧(¬b∨d)∧(b∨c).
A gate is functionally complete if …
any boolean function can be computed by a circuit constructed using only this gate
also universal
the nand gate and the nor gate
