Circuits Flashcards
A XOR B
OR with an extra curved line, symbol: circle with plus in it
True of only one of A or B is true
XOR in terms of 3 basic gates
A XOR B = (A+B) and not(A and B)
What is a functionally complete set of Boolean operators?
One which can be used to express all possible truth tables by combining them into a Boolean expression
Examples: AND+OR+NOT, NAND, NOR
Abstraction
Hiding details when they aren’t important
Discipline
Restricting design choices to make things easier to model, design and combine
What does a circuit have?
At least one input terminal, at least one output terminal
Specifies relationship between inputs and outputs
Has a specification of the delay between inputs changing and outputs responding
Combinatorial logic rules
Individual gates are combinatorial, all circuit elements are combinatorial, no cyclic paths
Turning a truth table into a sum of products
OR together the 1 values
X, Y, Z, F
0, 0, 0, 1
0, 0, 1, 0
0, 1, 0, 0
0, 1, 1, 1
F = (X’ . Y’ . Z’) + (X’ . Y . Z) + …
These are all minterms
Turning a truth table into a product of sums
AND together the zero values
X, Y, Z, F
0, 0, 0, 1
0, 0, 1, 0
0, 1, 0, 0
0, 1, 1, 1
F = (X + Y + Z’)(X + Y’ + Z)…
These are all maxterms
Axioms of boolean algebra
B = 0 if B != 1, B = 1 if B != 0 (binary field)
not(0) = 1, not(1) = 0
0.0 = 0, 1+1 = 1
1.1 = 1, 0+0 = 0
0.1 = 1.0 = 0, 1+0 = 0+1 = 1
Theorems of one variable
B.1 = B, B+0 = B (identity)
B.0 = 0, B+1 = 1 (null element)
B.B = B, B+B=B (idempotency)
not(not(B)) = B (involution)
B.not(B)=0, B+not(B) = 1 (complements)
Associativity
(B.C).D = B.(C.D)
(B+C)+D = B+(C+D)
Distributivity
B.(C+D) = B.C + B.D
B+(C.D) = (B+C).(B+D)
Covering
B.(B+C) = B
B+(B.C) = B
Combining
B.C + B.C’ = B
(B+C).(B.C’) = B
Consensus
B.C + B’.D + C.D = B.C + B’.D
(B+C).(B’+D).(C+D) = (B+C).(B’+D)
De Morgan’s
not(A.B.C.D…) = not(A)+not(B)+not(C)+not(D)+…
not(A+B+C+D+…) = not(A).not(B).not(C).not(D)….
Describe a half-adder
Output: Sum = A XOR B
Output: Carry = A AND B
1+1 = 0 with carry
Carry + 0 + 0 = 1
Carry + anything else = results in carry
Describe an adder
Made up of two half-adders
Overall input: A, B, Carry in
First adder input: A, B
First adder output: S1, C1
Second adder input: Carry, S1
Output: S2, C1 OR C2
What does an n-bit ripple carry adder consist of?
Made up of n full-adders
Overall input: b1, a1, C_in = 0
Each adder input: b_n, a_2, carry
Each adder output: S_n, carry
Overall output: S_n, C_out
How to create an n-bit subtractor?
n-bit adder but set the first carry bit to 1, and negate all the B values
This creates a twos-complement negative
How to create an n-bit subtractor?
n-bit adder but set the first carry bit to 1, and negate all the B values using NOT gates
This creates a twos-complement negative
What is a decoder?
Translates a set of n inputs into a set of 2^n outputs, with only one output being 1
Example:
0,0 => 0,0,0,1
0,1 => 0,0,1,0
1,0 => 0,1,0,0
1,1 => 1,0,0,0
Mux (multiplexor)
A n-bit multiplexor has n+2^n inputs and 1 output
The first n inputs (selector) represent a binary number
The output is the nth bit of the size 2^n part of the input
What is a tristate?
A buffer that can be disconnected from the bus wire. When disconnected (enable = 0, or 1 for an inverting tristate) the output is weak/”floating”
Types of delay in a circuit
Contamination delay (t_cd): The minimum delay before the output changes for the first time
Propagation delay (t_pd): The maximum delay before the output is stable
Input changes, output stays at old value for t_cd, starts oscillating, eventually stabilises t_pd after the input changes
Causes of delay
Capacitance and resistance in a circuit
Speed of light limitation
t_pd and t_cd are different because of different rising and falling delays, multiple inputs and outputs some of which are faster, and because circuits slow down when hot
Critical path and short path
Critical path: Longest path in the circuit, determines the propagation delay
Short path: Shortest path in the circuit, determines the contamination delay
Delays can be expressed like this: t_pd = 2*t_pd_AND + t_pd_OR
Static and dynamic hazards
Static hazards: Output undergoes momentary transition when one input changes when it is supposed to remain unchanged. A 1-hazard is where the signal randomly becomes 0 and vice versa.
Dynamic hazards: Output changes multiple times when it’s only supposed to change once
Timing diagrams
Show the value of a signal as a function of time. The transitions between logic levels are assumed to take place instantaneously.
Removing a 1-hazard
Draw a Karnaugh map of the output concerned. The 1-hazard occurs where two adjacent 1s are not covered by the same circle. Add another term which overlaps them to the circuit.
Removing a 0-hazard
Draw a Karnaugh map of the output concerned. The 1-hazard occurs where two adjacent 1s are not covered by the same circle. Identify another term which overlaps them and then add the complement of that term to the circuit.
Turning a sum of products into a product of sums
F = sum of products
!F = !(sum of products) = product of products = product of sums
Expand this product of sums and simplify to get a sum of products again
now !F = sum of products
F = !(sum of products) = product of products = product of sums
Unwanted terms in a sum of products can be removed by multiplying them by (X + !X)
What is a sequential circuit?
Output depends on history as well as current input. Fundamental components include latches and flip-flops
SR-latch
Truth table (SR NOR):
S, R, Q, Q’
0, 0, Q_prev, Q’_prev
0, 1, 0, 1
1, 0, 1, 0
1, 1, 0, 0 (illegal)
Both inputs usually set to 0
If the input S (set) has a pulse of 1, the output becomes 1 and remains 1 even when the pulse is over
If the input R (reset) has a pulse of 1, the output becomes 0 and remains 0 even when the pulse is over
SR NAND has SR NOR’s truth table in reverse
D-latch
Inputs: D, CLK
The latch value changes to D when CLK is 1
D flip-flop
The output/stored value changes only at the moment the clock goes high.
The D flip-flop sets the latch value (Q) to D on the rising edge of the clock and remembers its state at all other times
Registers are a bank of flip-flops all driven by the same clock
Enabled flip-flop
Incorporates an additional input (enable) to control whether the data is loaded into the flip-flop or not
Uses a multiplexor
Either controls the input or the clock (gated clock)
Gated clocks can cause timing errors and glitches
What are race conditions?
When the behaviour of a circuit depends on which route carries the signal the fastest
How do we avoid cyclic paths?
Insert registers into them, the registers contain the state of the circuit and only update on a clock edge (synchronised to the clock). If the clock is sufficiently slow, race conditions cannot arise.
Formal definition of a synchronous sequential circuit
It consists of interconnected elements such that:
- Every circuit element is either a combinatorial circuit or a register
- At least one circuit element is a register
- All registers receive the same clock signal
- Every cyclic path contains at least one register
It has:
- A discrete set of states S0 to S_k-1
- A clock input, whose rising edge indicates when a state change occurs
- A functional specification which details the next state and all outputs for each possible state and set of inputs
Timing of a synchronous sequential circuit
t_setup = time before rising edge during which inputs must be stable
t_hold = time after rising edge during which inputs must be stable
t_ccq = time until output starts to change
t_pcq = time by which output has stabilised
The time between ticks (T_c) must be at least t_pcq + t_pd + t_setup (time for R1 to stabilise + propagation delay of circuit + time needed for R2 to stabilise)
Sequencing overhead
t_pd < T_c - (t_pcq + t_setup)
(t_pcq + t_setup) is the sequencing overhead
T_c and the sequencing overhead are fixed and the designer must get all elements of combinatorial logic to work within the bound on t_pd
Minimum delay requirement
t_cd > t_hold - t_ccq
We add buffers to fix the hold time violation
Latency and throughput
Latency = time it takes for a single block of data to get from the beginning to the end
Throughput = Rate at which we get data through
T_c = T_c of the longest block
Throughput = 1/T_c
