Circuits

Question 1

A XOR B

Answer 1

OR with an extra curved line, symbol: circle with plus in it
True of only one of A or B is true

Question 2

XOR in terms of 3 basic gates

Answer 2

A XOR B = (A+B) and not(A and B)

Question 3

What is a functionally complete set of Boolean operators?

Answer 3

One which can be used to express all possible truth tables by combining them into a Boolean expression
Examples: AND+OR+NOT, NAND, NOR

Question 4

Abstraction

Answer 4

Hiding details when they aren’t important

Question 5

Discipline

Answer 5

Restricting design choices to make things easier to model, design and combine

Question 6

What does a circuit have?

Answer 6

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

Question 7

Combinatorial logic rules

Answer 7

Individual gates are combinatorial, all circuit elements are combinatorial, no cyclic paths

Question 8

Turning a truth table into a sum of products

Answer 8

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

Question 9

Turning a truth table into a product of sums

Answer 9

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

Question 10

Axioms of boolean algebra

Answer 10

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

Question 11

Theorems of one variable

Answer 11

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)

Question 12

Associativity

Answer 12

(B.C).D = B.(C.D)
(B+C)+D = B+(C+D)

Question 13

Distributivity

Answer 13

B.(C+D) = B.C + B.D
B+(C.D) = (B+C).(B+D)

Question 14

Covering

Answer 14

B.(B+C) = B
B+(B.C) = B

Question 15

Combining

Answer 15

B.C + B.C’ = B
(B+C).(B.C’) = B

Question 16

Consensus

Answer 16

B.C + B’.D + C.D = B.C + B’.D
(B+C).(B’+D).(C+D) = (B+C).(B’+D)

Question 17

De Morgan’s

Answer 17

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)….

Question 18

Describe a half-adder

Answer 18

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

Question 19

Describe an adder

Answer 19

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

Question 20

What does an n-bit ripple carry adder consist of?

Answer 20

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

Question 21

How to create an n-bit subtractor?

Answer 21

n-bit adder but set the first carry bit to 1, and negate all the B values

This creates a twos-complement negative

Question 22

How to create an n-bit subtractor?

Answer 22

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

Question 23

What is a decoder?

Answer 23

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

Question 24

Mux (multiplexor)

Answer 24

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

Question 25

What is a tristate?

Answer 25

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"

Question 26

Types of delay in a circuit

Answer 26

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

Question 27

Causes of delay

Answer 27

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

Question 28

Critical path and short path

Answer 28

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

Question 29

Static and dynamic hazards

Answer 29

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

Question 30

Timing diagrams

Answer 30

Show the value of a signal as a function of time. The transitions between logic levels are assumed to take place instantaneously.

Question 31

Removing a 1-hazard

Answer 31

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.

Question 32

Removing a 0-hazard

Answer 32

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.

Question 33

Turning a sum of products into a product of sums

Answer 33

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)

Question 34

What is a sequential circuit?

Answer 34

Output depends on history as well as current input. Fundamental components include latches and flip-flops

Question 35

SR-latch

Answer 35

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

Question 36

D-latch

Answer 36

Inputs: D, CLK The latch value changes to D when CLK is 1

Question 37

D flip-flop

Answer 37

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

Question 38

Enabled flip-flop

Answer 38

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

Question 39

What are race conditions?

Answer 39

When the behaviour of a circuit depends on which route carries the signal the fastest

Question 40

How do we avoid cyclic paths?

Answer 40

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.

Question 41

Formal definition of a synchronous sequential circuit

Answer 41

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

Question 42

Timing of a synchronous sequential circuit

Answer 42

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)

Question 43

Sequencing overhead

Answer 43

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

Question 44

Minimum delay requirement

Answer 44

t_cd > t_hold - t_ccq We add buffers to fix the hold time violation

Question 45

Latency and throughput

Answer 45

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