CS计算机代考程序代写 chain CS3350B Computer Organization Chapter 2: Synchronous Circuits Part 2: Stateless Circuits

CS3350B Computer Organization Chapter 2: Synchronous Circuits Part 2: Stateless Circuits
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Wednesday February 03, 2021
Alex Brandt
Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 1 / 27

Outline
1 Combinational Circuits
2 Adders and Subtractors
3 MUX and DEMUX
4 Arithmetic Logic Units
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 2 / 27

Stateless Circuits are Combinational Circuits
Stateless ⇒ No memory.
Combinational ⇒ Output is a combination of the inputs alone.
Combinational circuits are formed from a combination of logic gates and other combinational cirtcuits.
ë Modular Design,
ë Reuse,
ë Simple to add new components.
Sometimes, these are called functional blocks, they implement functions.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 3 / 27

Increasing Arity
Arity: the number of inputs to a gate, function, etc.
How can we build an 𝑛-way add from simple 2-input and gates?
ë Simply chain together 𝑛 − 1 2-way gates. Example: 5-way AND
Works for AND, OR, XOR. Doesn’t work for NAND, NOR.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 4 / 27

Block Diagrams
A block diagram or schematic diagram can use used to express the high-level specification of a circuit.
How many inputs, how many bits for each input? How many outputs, how many bits for each output? What does the circuit do? Formula or truth table.
Alex Brandt
𝐹 ≡𝑎𝑏𝑐+𝑎𝑏𝑐
Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits
𝑎𝑏𝑐𝐹
0001 0010 0100 0110 1000 1010 1100 1111
Wednesday February 03, 2021
5 / 27

From Blocks to Gates (1/2)
𝑎𝑏𝑐𝐹
0000 0010 0100 0111 1000 1011 1101 1111
1 Generate truth table. 2 Get canonical form:
𝐹 ≡𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐 3 Simplify if possible:
𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐
≡ 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐
≡ 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 ≡ 𝑏𝑐 + 𝑎𝑐 + 𝑎𝑏
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 6 / 27

From Blocks to Gates (2/2)
𝑎𝑏𝑐𝐹
3 Simplify if possible:
𝐹 ≡𝑏𝑐+𝑎𝑐+𝑎𝑏
4 Draw your circuit from simplified formula.
0000
0010
0100
0111
1000
1011
1101
1111 This is called a majority circuit. Output is
true iff majority of inputs are true.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 7 / 27

1 Bit Adder
Adder interprets bits as a binary number and does addition.
𝑎𝑏𝑠c 0000 0110 1010 1101
𝑠 = 𝑎𝑑𝑑(𝑎, 𝑏)
𝑐 = carry (overflow) bit
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 9 / 27

1 Bit Full Adder
Full Adder does addition of 3 inputs: a, b, and carry𝑖𝑛. ë Previous adder was a half adder.
𝑠=(𝑎 𝑋𝑂𝑅 𝑏) 𝑋𝑂𝑅 𝑐𝑖𝑛 𝑐 = 𝑎𝑏 + (𝑋𝑂𝑅(𝑎, 𝑏) ⋅ 𝑐𝑖𝑛)
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 10 / 27

1 Bit Full Adder using Half Adders
A full adder can be built from half adders. ë Modular design, reuse, simplified view.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 11 / 27

n-Bit Full Adder
𝑛-bit adder: Add 𝑛 bits with carry.
ë Just like long addition done by hand.
ë Combine 𝑛 full adders, adding bit by bit, carrying the carry from lowest-ordered bit to highest-ordered bit.
ë Final carry bit is 𝑐𝑛.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 12 / 27

Addition Overflow (1/2)
Overflow occurs when arithmetic results in a number strictly larger than can fit in the predetermined number of bits.
For unsigned integers, overflow is detected by 𝑐𝑛 being 1.
For signed (i.e. twos-compliment) integers, overflow more interesting.
Example: Addition in 4 bits.
(carry bits)
10011 ⇒ 𝑐𝑛 is 1. Overflow?
1000
1101 + 0110
Alex Brandt
Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits
Wednesday February 03, 2021
13 / 27

Addition Overflow (1/2)
Overflow occurs when arithmetic results in a number strictly larger than can fit in the predetermined number of bits.
For unsigned integers, overflow is detected by 𝑐𝑛 being 1.
For signed (i.e. twos-compliment) integers, overflow more interesting.
Example: Addition in 4 bits.
1000
1101 + 0110 10011
(carry bits)
−3 +6
3 ⇒
⇒ 𝑐𝑛 is 1. Overflow?
Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits
No overflow
Discard last carry bit
Alex Brandt
Wednesday February 03, 2021 13 / 27

Addition Overflow (2/2)
In twos-compliment when is there overflow?
Most significant bit encodes a negative number in two’s compliment. If both operands are positive and 𝑐𝑛1 ≡ 1 then we have overflow.
If one positive and one negative, overflow impossible.
ë Their sum is always closer to zero than either of the operands.
If both operands are negative and 𝑐𝑛 ≡ 1 then we have overflow.
1000 ⇒ Overflow
0101 +0110 1011
1000 +1000
10000 ⇒ Overflow
1000
1101 + 0110
10011 ⇒ No overflow
Overflow in two’s compliment: 𝑐𝑛 XOR 𝑐𝑛1. Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits
Wednesday February 03, 2021 14 / 27

n-bit Subtractor (1/2)
𝑛-bit subtractor: Subtract two 𝑛-bit numbers. We want 𝑠=𝑎−𝑏.
Start with an 𝑛-bit adder.
XOR 𝑏 with a control signal for subtraction.
ë signal is 1 for subtraction, 0 for addition. XOR works as conditional inverter.
ë AXORB≡C 􏰸⇒ if(B)thenA ≡CelseA≡C.
A B A⊕B≡C 000 011 101 110
Alex Brandt
Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits
Wednesday February 03, 2021
15 / 27

n-bit Subtractor (2/2)
Control signal SUB acts as 𝑐0.
ë Recall: signed negation. Invert and add one. ë XOR does invert.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 16 / 27

Multiplexer
A multiplexer “mux” conditionally chooses among its inputs to set value of output.
Uses control signal to control which input is chosen.
Still no state, output depending only on inputs: input bits and control
signal.
2-way multiplexer
If 𝑠≡0 then 𝑐≡𝑎. If 𝑠≡1 then 𝑐≡𝑏.
Notice actual value of 𝑎 and 𝑏 have no effect on decision.
ë 0 and 1 in multiplexer is not the value of 𝑎 or 𝑏 but the “index”.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 18 / 27

2-way Multiplexer
How to encode this “if-then” behaviour without actual conditionals?
𝑐 ≡ 𝑀𝑈𝑋(𝑎,𝑏,𝑠)
≡ 𝑠𝑎(𝑏 + 𝑏) + 𝑠𝑏(𝑎 + 𝑎) ≡ 𝑠𝑎 + 𝑠𝑏
Note: 𝑋 ⋅ (𝑌 + 𝑌 ) encodes “𝑋 independent of what the value of 𝑌 is”.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 19 / 27

4-way Multiplexer
𝑒 ≡ 𝑀𝑈𝑋(𝑎,𝑏,𝑐,𝑑,𝑆) ≡ 𝑠1𝑠0𝑎 + 𝑠1𝑠0𝑏
+𝑠1𝑠0𝑐 + 𝑠1𝑠0𝑑
The index of each input is now 0 through 3. Need 2 bits to choose among 4 inputs. Control signal’s bit-width is now 2.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 20 / 27

Big Data Multiplexer
Bit-width of input and output must match, but bit-width of control signal only determined by number of inputs to choose from.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 21 / 27

Demultiplexer
Demultiplexer “demux” conditionally chooses among its outputs. ë Opposite of MUX.
ë Un-selected outputs are set to 0.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 22 / 27

Arithmetic Logic Unit
An ALU is a black-box type circuit which can do many different arithmetic or logic operations on its inputs.
ë Not many at one time, but selectively acts as many.
Depending on the implementation can do addition, subtraction,
multiplication, division, logical AND, logical OR, shifting, etc. Use a control signal to choose which operation to perform.
Essentially a big collection of MUX and combinational blocks for each operation.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 24 / 27

Simple ALU Circuit
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 25 / 27

Optimizing ALU
Remember, every additional gate increases delay and space. Instead, optimize via the normal four step process:
1 Generate a truth table,
2 Get canonical from from truth table, 3 Simplify expression,
4 Make circuit.
Another option: programmable logic array.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 26 / 27

Programmable Logic Array
A programmable logic array (PLA) directly implements a truth table/canonical disjunctive normal form.
Each AND row is a truth table row.
Each OR column is one output bit.
Each ⊕ is a programmable (i.e. optional) AND gate (on the AND plane; OR gate on the OR plane) joining the input to the circuit.
Alex Brandt Chapter 2: Synchronous Circuits, Part 2: Stateless Circuits Wednesday February 03, 2021 27 / 27

Related Posts