The Basics of Logic Design for EECS2021
Table of Contents
– Gates, Truth Tables, and Logic Equations
Copyright By PowCoder代写 加微信 powcoder
– Combinational Logic
– Constructing a Basic Arithmetic Logic Unit
– Faster Addition: Carry Lookahead
– Memory Elelments: Flip-flops, Latches, and
Gates, Truth Tables, and Logic Equations
• Computer electronics is digital – only two voltages of interest
• high = 1 = asserted = active = true
• low = 0 = deasserted = inactive = false
– Simplified: a single voltage level (threshold)
• all voltages above are high
• all voltages below are low
• Logic blocks
– combinational logic = no memory elements – sequential logic = memory elements
Truth Tables
• A table of all possible inputs and the associated outputs for a particular circuit
• All combinational logic can be completely described using a truth table
• Non-zero output truth tables only list the inputs that result in non-zero outputs
• Text example: for all values of A, B, and C, let D be true if at least one input is true, let E be true if exactly two inputs are true, and let F be true only if all three inputs are true.
Boolean Algebra
• Binary OR is denoted by +, e.g. A+B.
– it is a logical sum
– result is 1 if at least one variable is 1
• Binary AND is denoted by *, e.g. A*B. Sometimes it denoted by . Or even omitted, e.g. A.B or just AB.
– it is a logical product
– result is 1 only if both variables are 1
• Unary NOT is denoted by , e.g. A. Sometimes it is denoted by ‘ e.g. A’.
Boolean Algebra Laws
Identity A+0=A
Zero and One A+1=1
Complementation A+A’=1
Commutative A+B=B+A
Associative A+(B+C)=(A+B)+C
Distributive A*(B+C)=(A*B)+(A*C) A+(B*C)=(A+B)*(A+C)
A*1=A A*0=0 A*A’=0 A*B=B*A A*(B*C)=(A*B)*C
Boolean Algebra Laws
A*A=A A+(A*B)=A
(A*B)’=A’+B’
Try to prove DeMorgan’s Laws using a truth table!
Idempotence
Absorption
Double Negation
DeMorgan’s Laws(A+B)’=A’*B’
A+A=A A*(A+B)=A (A’)’=A
DeMorgan’s Theorems
Perhaps like this one.
•Principle of Duality
•AND and OR are symmetric •So is 0 and 1
Boolean Algebra: Optimization
• Two different logic expressions can have exactly the same behavior.
• Two different expressions with identical behavior may have different costs Optimization: minimizing the cost
– Minimize the implementation cost in terms of the number of gates or transistors
– Minimize the performance cost in terms of the incurred propagation delays
Boolean Algebra: Optimization
AB + AB’ =A(B+B’)
(A’B’ + A)(A’B’ + B)
=A’B’A’B’ + AA’B’ + A’B’B + AB =A’B’ + 0 + 0 + AB
=A’B’ + AB
Boolean Algebra: Optimization
A’B’ + A = (A’ + A)(B’ + A) = B’ + A
A’B’C + ABC = (A’B’ + AB)C
=(A’B’ + A)(A’B’ + B)C =(B’ + A)(A’ + B)C
cost=8 delay=2 cost=8 delay=3
cost=11 delay=3
cost=7 delay=2 2x3AND+1x2OR=8 2x2OR+1x3AND=7
The above is a simplified illustration that uses calculations ignoring the negations. The obtained results are, therefore, incomplete.
Definition: A gate is a device that implements
basic logic functions, such as AND or OR. Logic blocks are built from gates that implement
basic logic functions.
Since AND is commutative and associative, an AND gate can have multiple inputs, with the output equal to the AND of all the inputs.
The same is true of OR.
The logical function NOT is implemented with an inverter that always has a single input.
AND gate OR gate NOT gate (inverter)
NAND and NOR Gates
In fact, all logic functions can be constructed with only a single gate type, if that gate is inverting.
The two common inverting gates are called NOR and NAND and correspond to inverted OR and AND gates, respectively.
NOR and NAND gates are called universal, since any logic function can be built using only this one gate type.
Gate Examples
• NOT gate (inverter)
• 3-inputs NOR gate (not-OR)
• 2-inputs NAND gate
Gate Examples
• It is the opposite of an AND gate
• So it is a 3-input NAND gate
Gates: TTL Conventions (Transistor-Transistor Logic)
• Zero volts is logic-0
• 5 volt is logic-1
• Unless we use negative logic
• Most computers use smaller voltages now
• 1.5 volt is used by DDR3 memories
• In this case 1.5 volt is logic-1
• Due to electrical noise the logic levels are actually defined by ranges of voltages.
• Input 0:[0.0,0.8]; 1:[2.0,5.0]
• Output 0:[0.0,0.5]; 1:[2.7,5.0]
Gates: TTL Conventions
TTL voltage ranges:
Implementation NOT gate
NOT gate: cost =1 transistor, delay=1 time unit Note that the NOT gate has a costs and incurs a delay when implemented separately but in some cases it may incur no extra cost, e.g. as in the NAND and NOR gates
NAND gate ++
Implementation
2 input AND gate: cost =2, delay=1
2 input NAND gate: cost =2, delay=1 (no extra cost!)
Implementation
2 input OR gate: cost =2, delay=1
2 input NOR gate: cost =2, delay=1 (no extra cost!)
Verilog Introduction (Outline)
Today most digital design of processors and related hardware systems is done using a hardware description language.
•First, it provides an abstract description of the hardware to simulate and debug the design.
•Second, with the use of logic synthesis and hardware compilation tools, this description can be compiled into the hardware implementation.
•Verilog is somewhat more heavily used in industry and is based on C, as opposed to VHDL, which is based on Ada.
Verilog Introduction (Outline)
Verilog can specify both a behavioral and a structural definition of a digital system.
• A behavioral specification describes how a digital system functionally operates.
• A structural specification describes the detailed organization of a digital system, usually using a hierarchical description
A structural specification can be used to describe a hardware system in terms of a hierarchy of basic elements such as gates and switches.
Thus, we could use Verilog to describe the exact contents of the truth tables and datapath.
Verilog Introduction (Datatypes and Operators)
There are two primary data types in Verilog:
• A wire specifies a combinational signal.
• A reg (register) holds a value, which can vary with time. A reg need not necessarily correspond to an actual register in an implementation, although it often will.
A register or wire, named X, that is 64 bits wide is declared as an array:
reg [63:0] X
wire [63:0] X
To refer to a contiguous subset of bits (both indices must be constant values):
[starting bit: ending bit]
Verilog Introduction (Datatypes and Operators)
The possible values for a register or wire in Verilog are:
•0 or 1, representing logical false or true
•X, representing unknown, the initial value given to all
registers and to any wire not connected to something
•Z, representing the high-impedance state for tristate gates, which we will not discuss in this appendix
Verilog Introduction (Datatypes and Operators)
Constant values can be specified as decimal numbers as well as binary, octal, or hexadecimal.
We often want to say exactly how large a constant field is in bits.
This is done by prefixing the value with a decimal number specifying its size in bits.
For example:
•4’b0100 specifies a 4-bit binary constant with the
value 4, as does 4’d4.
•−8’h4 specifies an 8-bit constant with the value −4 (in two’s complement representation)
Verilog Introduction (Datatypes and Operators)
Values can also be concatenated by placing them within { } separated by commas.
The notation {x{bitfield}} replicates bitfield x times.
For example:
• {32{2’b01}} creates a 64-bit value with the pattern 0101 … 01.
• {A[31:16],B[15:0]} creates a value whose upper 16 bits come from A and whose lower 16 bits come from B.
Verilog Introduction (Datatypes and Operators)
Verilog provides the full set of unary and binary operators from C, including:
•the arithmetic operators (+, −, *, /, %), •the bitwise logical operators (&, |, ^, ~), •the comparisons (!=,==,! ’,>,<,<=,>=), •the shift operators (<<, >>),
•the C’s conditional operator (cond? expr1 :expr2) Verilog adds:
•a set of unary logic reduction operators (&, |, ^)
They yield a single bit by applying the logical operator to all the bits of an operand.
Verilog Introduction (Structure of a Verilog Program)
A Verilog program is structured as a set of modules, which may represent anything from a collection of logic gates to a complete system.
The body of a module consists of:
•initial constructs, which can initialize reg variables
•continuous assignments, which define only combinational logic
•always constructs, which can define either sequential or combinational logic
•instances of other modules, which are used to implement the module being defined
Combinational Logic
• Multiplexors
• Arrays of Logic Elements
• Adders (Don’t Cares)
• Decoders
• Two-Level Logic and PLAs
Multiplexors
A basic logic function that is used quite often
A multiplexor could be called a selector
• its output is one of the inputs
• the input which is to be output is selected by a
special input
Definition: A selector value (or control value) is the control signal that is used to select one of the input values of a multiplexor as the output of the multiplexor.
A Multiplexor with 2 1-bit Inputs
The way we draw it. The implementation with gates.
2 1-bit inputs multiplexor: cost =7, delay=3 for S and 2 for A and B
A Multiplexor (2 1-bit inputs) (Verilog Module with gates)
module muxa(C,A,B,S);
input A,B,S;
wire nS, AnS, BS;
not not1(nS, S); //instantiation of not
and and1(AnS, A, nS);
and and2(BS, B, S);
or or1(C, AnS, BS);
C=A*S’+B*S; (AAND(NOTS))OR(BANDS)
A Multiplexor (2 1-bit inputs) (Verilog Module with assign)
module muxb(C,A,B,S);
input A,B,S;
assign C = A&~S|B&S;
C=A*S’+B*S; (AAND(NOTS))OR(BANDS)
Multiplexor (2 1-bit inputs) (Verilog Module with always)
module muxc(C,A,B,S);
output C; reg C;
input A,B,S;
always @(A,B,S)
case ({A,B,S})
3’b000: C=0;
3’b010: C=0;
3’b100: C=1;
3’b110: C=1;
3’b001: C=0;
3’b011: C=1;
3’b101: C=0;
3’b111: C=1;
default: ;
C=A*S’+B*S; (AAND(NOTS))OR(BANDS)
Multiplexor (2 2-bit inputs) Verilog Module
module mux2(C,A,B,S);
output [1:0] C;
input [1:0] A,B;
muxa muxb20(C[0], A[0], B[0], S);
muxb muxb21(C[1], A[1], B[1], S);
Instantiates 2 multiplexors for a 2-bit wide bus
A Multiplexor That Selects Between Two 64-bit Buses
Multiplexor (64 2-bit inputs) Array-based Instantiation
module muxn(C,A,B,S);
parameter SIZE=2;
output [SIZE-1:0] C;
input [SIZE-1:0] A,B;
muxa muxan[SIZE-1:0](C,A,B,S);
muxn mux2(C,A,B,S); //SIZE=2 (default)
muxn #(64) mux64(C,A,B,S); //SIZE=64
muxn #(.SIZE(64)) mux64(C,A,B,S);
The SIZE parameter specifies the number of multiplexors that need to be instantiated
Arrays of Logic Elements
• Many of the combinational operations to be performed on data have to be done to an entire word (64 bits) of data.
• Definition: A bus is a collection of data lines that is treated together as a single logical signal (also, a shared collection of lines with multiple sources and uses)
Multiplexor (2 2-bit inputs) Module for exhaustive testing
module test1;
reg [1:0] a, b;
reg s; // reg without size means 1-bit
wire [1:0] c;
integer ci,ai,bi;
mux2 my_mux21(c,a,b,s);
for (ci = 0; ci < 2; ci = ci + 1)
for (ai = 0; ai < 4; ai = ai + 1)
for (bi = 0; bi < 4; bi = bi + 1) begin
assign a = ai; b = bi; s = ci;
#5 $display("s=%b a=%b b=%b c=%b",s,a,b,c);
test1 does exhaustive testing of the mux2 multiplexor. Put the test1 and the mux modules in the same file.
Multiplexor (2 2-bit inputs) Module for random testing
module test2;
wire [1:0] C; reg [1:0] A,B; reg S;
mux2 mymux2(C,A,B,S);
initial repeat (15) begin
A=$random; B=$random; S=$random;
#1 $display("C=%b A=%b B=%b S=%b",C,A,B,S);
test2 does random testing of the mux2 multiplexor. Put the test2 and the mux modules in the same file.
Half Adder
Sum = A'B + AB' Carry = AB
A B Sum Carry 00 0 0 01 1 0 10 1 0 11 0 1
Sum = A’*B+A*B’=(A XOR B); //cost=8, delay=3 ((NOT A)AND B) OR (A AND (NOT B))
Carry = A*B; //cost=2 delay=1 (A AND B)
Half Adder
(Verilog Module with assign)
half_adder(A,B,Sum,Carry);
input A,B;
output Sum, Carry;
assign Sum = ~A&B | A&~B;
assign Carry = A&B;
Sum = A’*B+A*B’; // ((NOT A)AND B) OR (A AND (NOT B))
Carry = A*B; //(A AND B)
Half Adder
(Verilog Module with always)
Module half_adder(A,B,S,C);
input A,B;
output reg S, C
always @(A,B)
case ({A,B})
2'b00: begin S=0; C=0; end;
2'b01: begin S=1; C=0; end;
2'b10: begin S=1; C=0; end;
2'b11: begin S=0; C=1; end;
default: ;
A 1-bit Adder (Half Adder with XOR)
S = A’*B+A*B’ = A ⊕ B; //(A XOR B) cost=8 delay=3 C=A*B; (AANDB)
A 1-bit Adder with Cin (Full Adder with XOR)
S = (A ⊕ B) ⊕ Cin; //(A XOR B) XOR Cin) cost=8+8=16, delay=3+3=6 We will use the SumOfProducts design.
Cout = (A * B) + (Cin * (A ⊕ B)); //(A AND B) OR (Cin AND (A XOR B))
Input and Output Specification for the Full Adder
Full Adder
S=(A XOR B XOR C)
The cost of a 3-input XOR gate designed as SumOfProducts (SOP) is calculated as follows: 3*1+4*3+1*4=19
Unless explicitly stated otherwise, this SumOfProducts (SOP) design should be
used in the cost and delay calculations for the 3-input XOR (A XOR B XOR C) gates.
delay=3 A B C S Cout 00000 00110 01010 01101 10010 10101 11001 11111
Full Adder
A B C S Cout 00000 00110 01010 01101 10010 10101 11001 11111
Full Adder
S = A'B'C + A'BC' + AB'C' + ABC
Cout =ABC+A'BC+ABC'+AB'C Cout = AB + BC + CA (optimized)
One possible way to optimize Cout : ABC+A'BC=(A+A')BC=BC A: don’t care ABC+AB'C=A(B+B')C=AC (B: don’t care) ABC+ABC'=AB(C+C')=AB (C: don’t care)
ABC SCout 000 00 001 10 010 10 011 01 100 10 101 01 110 01 111 11
Don’t Cares
Definition: A “don’t care” is a situation where we do not care what the value of some input or some output is
“Don’t cares” occur often in implementing some combinational logic
We don’t care about an input or output either because another output is true or because a subset of the input combinations determines the values of the outputs
The optimized Adder Hardware for the CarryOut Signal
Values of the inputs when CarryOut is 1
2-level logic design (SOP):
Optimized:
Cout=A'BC+AB’C+ABC'+ABC; //cost=3*1+4*3+1*4=19 delay=3
Cout = AB+AC+BC; //cost=3*2+1*3=9 delay=2
Full Adder
(Verilog Module with assign)
Module full_adder(Cin,A,B,Sum,Cout);
input Cin,A,B;
output Sum, Cout;
assign Sum =
~A&~B&Cin|~A&B&~Cin|A&~B&~Cin|A&B&Cin;
assign Cout = A&B|A&Cin|B&Cin;
S = A'B'C + A'BC' + AB'C' + ABC; Cout = AB+AC+BC;
Definition: A decoder is a logic block that has an n-bit input and 2n outputs where only one output is asserted for each input combination.
A 3-to-8 Decoder
The Truth Table for a 3-to-8 Decoder
Combinational Logic Diagram of a 3-to-8 Decoder
Two-Level Logic and PLAs
• Any logic function can be implemented with only AND, OR, and NOT functions.
• A canonical form is used, where every input is either a true or complemented (inverted) variable and there are only two levels of gates
– one AND and the other OR
– with a possible inversion on the final
• Definition: The sum of products (SOP) is a
logical representation that uses a logical sum (OR) of products (terms using AND).
Programmable Logic Array
Definition: A programmable logic array (PLA) is a structured-logic element composed of a set of inputs and corresponding input complements and two stages of logic
– the first stage generates product terms of the inputs and input complements
– the second stage generates sum terms of the product terms
Definition: Minterms (or product terms) are a set of logic inputs joined by conjunction (AND)
Product terms form the first logic stage of a PLA.
Programmable Logic Array (PLA)
Programmable Logic Array (PLA)
For a given Boolean function with n 1-rows in its truth table we need n AND gates and 1 OR gate with n inputs.
Based on the above, in 2-level logic designs, delay=3 when inverted inputs are included
Programmable Logic Array (PLA)
Definition: A read-only memory (ROM) is a memory whose contents are designated at creation time, after which the contents can only be read
ROMs can be used as structured logic to implement a set of logic functions
– use the terms in the logic functions as address inputs
– use the outputs as bits in each memory word
Definition: A programmable ROM (PROM) is a form of ROM that can be programmed when a designer knows what to put into it
Each column is a Boolean function (3 inputs, 23=8 outputs, 28=256 Bfs)
D0 D1 D2 D3 D4 D5 D6 D7 ... D255
Constructing a Basic Arithmetic Logic Unit
• A 1-Bit ALU
• A 64-Bit ALU
A 1-Bit ALU
The logical operations are easiest, because they map directly onto the hardware components:
– AND gate – OR gate – Inverter
The 1-bit Logical Unit for AND and OR
A 1-bit Adder with CarryIn (Full Adder)
A 1-bit ALU that Performs AND, OR, and Addition
The multiplexor with 3 1-bit inputs can be constructed using a 2-to-4 decoder
The ALU calculates AND, OR, and ADD in parallel. The multiplexor selects the result to be used.
The 64-bit ALU on the right is created by connecting adjacent “black boxes”.
In our case it is constructed
from 64 1-bit ALUs
A 64-Bit ALU
1-bit ALU that ANDs, ORs, or ADDs a and b or a and ~b
1-bit ALU that ANDs, ORs, or ADDs a or ~a to b or ~b
Adding a Comparison Function to the 64-Bit ALU
• The four operations—add, subtract, AND, OR—are found in the ALU of almost every computer, and the operations of most instructions can be performed by this ALU. But the design of the ALU is incomplete.
• One instruction that still needs support is the a comparison function:
– set on less than (slt).
1-bit ALU: ANDs, ORs, ADDs, and Compares a or ~a, b or ~b
1-bit ALU for
the Most Significant Bit
Set is the MSB which is the sign bit and will be used for the Less signal
A 64-bit ALU Constructed from 64 copies of the 4-function 1-bit ALU and one special 4-function 1-bit ALU
for the MSB
The Final 64-bit ALU
Bnegate is employed for subtraction (it is Binvert with additional connection to CarryIn0)
Set is the MSB which is the sign bit and is used for the Less signal. When slt is executed the Less signal sets the LSB to 1 and all other bits are set to 0.
The values of the three ALU control lines, Ainvert, Bnegate, and Operation, and the corresponding ALU operations
11:SLT(ADD)
= a’AND b’
The Symbol Commonly Used to Represent an ALU
Faster Addition: Carry Lookahead
• Fast Carry Using “Infinite” Hardware
• Fast Carry Using the First Level of Abstraction: Propagate and Generate
Fast Carry Using “Infinite” Hardware
c2 = (b1*c1)+(a1*c1)+(a1*b1)
c1 = (b0*c0)+(a0*c0)+(a0*b0)
(at least 2 out of 3 inputs are 1s)
c2 = (a1*a0*b0)+(a1*a0*c0)+(a1*b0*c0)
+(b1*a0*b0)+(b1*a0*c0)+(b1*b0*c0)
Imagine how the equation expands as we get to higher bits in the adder!
This complexity causes high hardware cost for
fast carry, making this simple scheme
prohibitively expensive for wide adders. 80
Fast Carry Using
the First Level of Abstraction: Propagate and Generate
Most fast carry schemes limit the complexity of the equations to simplify the hardware, while still making substantial speed improvements over ripple carry.
One such scheme is a carry-lookahead adder There are two important factors called
generate(gi
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com