COMP 2421 Computer Organization
Lecture7 DigitalLogic(II)
Review – Combinational Logic
Copyright By PowCoder代写 加微信 powcoder
Input, Output, Boolean Functions
Combinational Circuits
Design Implementation
The mathematical foundation of Design & Implementation: Boolean Algebra
Real-world Problem
Important Concepts ◆Switching function
– Z = F(A,B,C, …, ), relating inputs and output
– Mathematical foundation: Boolean Algebra
– Use properties of Boolean algebra for simplification: FàF’, such that F’ has less operations and less types of operations
Important Concepts ◆Truth table
– Another form to represent the relation between inputs and output
– One important usage: given any F, build a truth table, and then derive the SOP/POS formàcombination circuits
Important Concepts ◆Combinational Circuits
– From SOP/POS, obtain 2-level AND- OR/ 2-level OR-AND circuits
– Digital components: MUX, DEMUX, Adder
Three Equivalent Representations
Switching Function (logical expression)
Truth table
A Motivative Example: One-bit Binary Adder
Problem: derive the SOP form for the two outputs S and 𝐶!”# Cin
One-bit Binary Adder
Simplification
◆Given a Boolean expression, can it be simplified? – if you got a simplified form, is it the simplest?
𝐶!”# =𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶
= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶
= (𝐴𝐵𝐶 + 𝐴𝐵𝐶) + (𝐴𝐵𝐶 + 𝐴𝐵𝐶) + (𝐴𝐵𝐶 + 𝐴𝐵𝐶)
= (𝐴 + 𝐴)𝐵𝐶 + 𝐴(𝐵 + 𝐵)𝐶 + 𝐴𝐵(𝐶 + 𝐶)
Association reverse Distribution
= 𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵
Complement
Idempotence
Three methods to Achieve Simplification ◆Algebraic simplification
– applying the properties of Boolean algebra
– essentially, it is done by observation — not good for
complex expressions ◆Karnaugh map (K-map)
– a systematical way to deal with expressions with few (up to 4, 5) variables
◆Quine-McKluskey tables (more variables)
Outline of Today’s Lecture ◆Combinational Circuits
– Karnaugh map for simplification
– The procedure of designing combinational circuits
◆Basics of Sequential Circuits
– flip-flops – register – counter
Learning Objectives ◆K-map
– Understand the meaning of K-map
– Know how to construct a K-map
– Know how to use K-map for simplification
◆Design of combinational circuits – Know the general procedure
– Use what we have learned so far to design a combinational circuit to solve simple real-world problems
Karnaugh Map
◆A representation of Boolean function
– an array of squares, for n variables, there are 2! squares
– each square represent a combination of input values AB BC CD
00 01 11 10
Note the order of “00, 01, 11, 10” — adjacent terms different in one bit
00 01 1110
00 01 1110
Karnaugh Map
◆A representation of Boolean function
– For each square, a combination of inputs represents a corresponding product term
– square 10 represents 𝐴𝐵; general rule: if 1, use X; if 0, use NOT X
– Mark the squares: if a square is marked with 1, the
corresponding “product term” is included in the SOP form of that
Boolean function
00 01 11 10
Karnaugh Map
◆In summary, K-map is a representation of Boolean Function, where:
– Squares represent product terms
– 1-sequares indicate whether the product term should be
included in the function
00 01 11 10
Using K-map for Simplification
◆Given any Boolean function, how to do simplification using Karnaugh map?
– transform the Boolean function to canonical form: each term must contain every variable
– example: consider three variables, 𝐴𝐵 = 𝐴𝐵(𝐶 + 𝐶) = 𝐴𝐵𝐶 +𝐴𝐵𝐶
– use K-map to represent this canonical form
– do some operations on this K-map to achieve simplification
Using K-map for Simplification ◆Operation: group “1-squares” to blocks
“1-square”: a product term in the Boolean function
𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷
Group two 1-squares into one block — now, each block corresponds to one product term
𝐴𝐵𝐷 — simplified!
We need to answer two questions:
1. How to merge 1-squares into blocks correctly?
2. How to derive the simplified term from the block?
Using K-map for Simplification ◆Game of Grouping Squares
Merge into blocks
Then “something” got cancelled — simplified!
Step 1: Grouping Squares into Blocks ◆Rules of grouping 1-squares into blocks
– group adjacent 1-squares into one block
– one block can contain 2″ 1-squares (1, 2, 4, 8,…)
◆Goals of grouping 1-squares into blocks
– number of blocks should be minimized – size of a block should be maximized
Examples of Grouping
Adjacent squares
Note: “00, 01, 11, 10” are arranged in this order such that adjacent squares differ in one variable
We want to minimize the number of blocks
Examples of Grouping
How to group this one?
we can reuse the 1-square to increase the size of the block
Examples of Grouping
Which one is better?
Choose blocks with larger size even there are more overlaps — the first one can result in the simplest form
Examples of Grouping
How to group this one?
the blue circle is not necessary to reduce the number of blocks
if all the 1-squares in a block are already within other blocks, that block is not necessary
Examples of Grouping
Exercise: try to group this one?
How many blocks and what’s the size of each block?
There could be different results
Step 2: Derive Term from Block ◆Each block represents a term
– cancel the variable which has inconsistent values in the block
Check the two 1-squares in the block ABCD = 0101, ABCD = 0111
C has inconsistent values
Cancel C —> 01-1 —> 𝐴𝐵𝐷
Intuition: inconsistent values mean that there are 𝑿
and 𝑿 in the terms 𝐴𝐵𝐶𝐷+𝐴𝐵𝐶𝐷=𝐴𝐵 𝐶+𝐶 𝐷=𝐴𝐵𝐷
(this explains why adjacent squares differ in 1 bit and a block should have 2^k squares)
00 01 11 10 00
Summary of K-map
◆Steps of using K-map for simplification
– given any Boolean function
– transform it canonical form
– draw the K-map
– group the 1-squares into blocks – derive terms from blocks
Exercise of One-bit Adder
𝐶!”# =𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶
00 01 11 10 0
which positions are filled with 1? Can you derive the simplified form?
Exercise of One-bit Adder
𝐶!”# =𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶
00 01 11 10 0
𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵
Another feature of K-map — “don’t care” conditions ◆Motivation: for some problems, we do not need to
define a complete truth table
– that is, some combinations of input values are not meaningful
– we do not need to care about them
– example: consider decimal incrementor. input = X, output =
(X+1) mod 10, where X ranges from 0 to 9
– we use 4 bits to represent the input/output — there is redundant
Another feature of K-map — “don’t care” conditions
for don’t care conditions, we mark the corresponding squares in K- map as “d”
Another feature of K-map — “don’t care” conditions ◆d-square in K-map
– you can specify the value of “d” (1 or blank) in the K-map
– goal: reduce the number of blocks & increase the size of blocks
some “d” are treated as 1 so that more 1-squares are connected
Procedure of Designing Combinational Circuits ◆Example: design a circuit to implement access control
– There are 12 students, with ID 0 to 11.
– Students with ID 2, 3, 4, 8, 11 can enter the Lab – Design a digital lock to achieve access control
Procedure of Designing Combinational Circuits
◆Mathematical modelling: define the input/output and the relation (switching function)
– Use 4 bits ABCD to represent the ID
– Use a single bit Y to represent the decision (Y = 1àaccess
– Use truth table to represent the relation
Procedure of Designing Combinational Circuits
Now, based on the truth table, we could write the SOP form.
But usually, it is not the simplest.
We can use K-map for simplification
Procedure of Designing Combinational Circuits ◆Use K-map for simplification
00 01 11 10
Procedure of Designing Combinational Circuits ◆Exercise: Use K-map for simplification
00 01 11 10
Procedure of Designing Combinational Circuits ◆Use K-map for simplification
Procedure of Designing Combinational Circuits ◆Simplified SOP to circuit (try after class)
Outline of Today’s Lecture
◆Combinational Circuits
– Karnaugh map for simplification
◆Sequential Circuits
– flip-flops – register – counter
Combinational Circuits vs. Sequential Circuits ◆Combinational Circuits are memoryless
– the output depends only on the current input (there is an exceptional case of ROM)
– there is another class of logic circuits with such property: the outputs depend not only on the current inputs, but also on the
past behavior of the circuit — there are storage elements (memory) in the circuits
The Concept of Sequential Circuits ◆Sequential circuits
– the contents of the storage elements represent the state of the circuit
– the input may leave the circuit in the same state, or cause it to a new state; output (next state) = current input + current state
– over time, the circuit changes through a sequence of states as a result of changes in the inputs
– circuits that exhibit this behavior are referred to as sequential circuits
Examples of Sequential Circuits
◆Simple but useful examples of sequential circuits
– different types of Flip-Flops – registers
– counters
Flip-Flops
◆There are a variety of flip-flops, all of which share two
properties
– it is a bistable device: it exists in one of two states and, in the
absence of input, remains in that (stable) state
– it has two outputs, 𝑄 and 𝑄 (the complement of each other)
S-R Latch (S-R Flip-Flop)
Use the output Q as the state of the Latch it has two stable states: Q = 1 and Q = 0
To show Q = 1 is a stable state: check 𝑄 = 1,𝑄
= 0, 𝑤𝑒 𝑐𝑎𝑛 𝑓𝑖𝑛𝑑 𝑖𝑛𝑝𝑢𝑡𝑠 𝑅 = 𝑆 = 0
(note: stable state means that the circuit will stay in this state (Q=1) if the inputs do not change)
ToshowQ=0 isastablestate:check𝑄=0,𝑄 = 1, 𝑤𝑒 𝑐𝑎𝑛 𝑓𝑖𝑛𝑑 𝑖𝑛𝑝𝑢𝑡𝑠 𝑆 = 𝑅 = 0
We can see that S-R Latch can be used as a storage element to store 1 bit (1-bit memory)
Note the feedback path in the circuit
Changing the Inputs
◆Output depends on input and state
– given the current state, what would the outputs be if we change the inputs?
– case 1: 𝑄 = 0, 𝑄 = 1, change the inputs as S = 1, R = 0, what will Q become?
– 𝑄 = 1, 𝑄 = 0
– that is S =1 writes bit 1 to the memory (S is called Set)
Changing the Inputs
◆Output depends on input and state
– case 2: 𝑄 = 1, 𝑄 = 0, change the inputs as S =0, R = 1, what will Q become?
– 𝑄 = 0, 𝑄 = 1
– that is R =1 writes bit 0 to the memory (R is called Reset)
Characteristic Table
◆Use characteristic table to describe a sequential circuit
– describe the relations between next state (output) and input & current state
note the meanings of the inputs
inputs not allowed: cause inconsistent outputs
Timing Diagram of S-R Latch
S changes from 0 to 1 (a pulse)
R changes from 0 to 1
Timing diagram is another way of describing sequential circuits
Synchronization Issue caused by Gate Delay ◆The changes of inputs could happen at any time
– Because of delay, unexpected error may happen when different inputs change in a short period
– So, we want to control the timing of input changes – solution: use a clock signal for control
duty cycle (in this case, 50%)
cycle time = 25ns (frequency = 40 MHz)
Use Clock to Control the Timing ◆Result: Edge-triggered Flip-Flops
– the input changes at the “edge” of the clock signal (when the clock signal changes)
positive edge (rising edge) negative edge (falling edge)
◆How to achieve this?
flip-flops could be positive- edge-trigged or negative edge trigged
How to Achieve Edge-triggered F-F (Not Required) ◆Basic idea: input AND clock
Clock signal
Output of clock
Consider rising edge (clock 0 -> 1): the output has a very narrow pulse (gate delay) only when the clock signal changes from 0 to 1 (rising edge)
How to Achieve Edge-triggered F-F (Not Required)
◆Basic idea: input AND clock
We further connect the input with the output of clock using an AND gate:
The change of input will only take effect at the narrow pulse (rising edge)
Clock signal
Output of clock
For more detailed explanation: reference link
Edge-triggered Flip-Flops ◆Edge-triggered (or Clocked) S-R Flip-Flop
use the bubble for indication
Idealized Timing Diagram
these changes will not take effect
change will only take effect at the rising edge
Summary of Edge-triggered S-R Flip-Flop ◆Usage: 1-bit memory
– Characteristic table and timing diagram to describe FF
– use S and R to control the writing of bit 0/1
– use clock to control when to write —when the flip-flop is “triggered”
Other Common Flip-Flops ◆D Flip-Flop
– one problem with S-R flip-flop is that R = S = 1 should be avoid
– D flop-flop uses a single input source: it is a S-R flip-flop with 𝑆 =
Characteristic table
Other Common Flip-Flops ◆D Flip-Flop
– the output is always equal to the most recent input value D – storage for one bit of data
Other Common Flip-Flops ◆J-K Flip-Flop
– all combinations of two input values are valid (including 1 1)
– How to derive the characteristic table of J-K Flip-Flop?
– two steps: first a table of J, K, Q_n, Q_{n+1}, then reduce to a simpler table
◆Exercise: derive the characteristic table
◆Exercise: derive the characteristic table
Other Common Flip-Flops
◆J-K Flip-Flop
– when input is (1,1), it is a toggle function: the output is reversed
Registers — The Example of Using Flip-Flops ◆Registers
– used in CPU to store one or more bits (multiple flip-flops)
– two types: shift registers and parallel registers
– parallel registers: a set of 1-bit memories that change state simultaneously
– shift registers: states are changed sequentially
Example: 8-bit Parallel Registers
source of data
(can use MUX to connect to multiple sources)
note: the D flip-flops are not interconnected
A “Load” control signal (when there is a pulse, the data is loaded)
Example: 5-bit Shift Registers
input: 010101101001111
note: the D flip-flops are interconnected
with each clock pulse, data are shifted to the right on position, and the rightmost bit is transferred out
shift registers can be used to interface to serial I/O devices, or perform logical shift in ALU
output: bit by bit
◆A register whose value will increment by 1
– for a counter composed of N flip-flops, the value ranges from 0 to 2# − 1; that is, the output of each flip-flop serves as one bit
of the N-bit number
– asynchronous counter: states of flip-flops will NOT change at the same time
– synchronous counter: states of flip-flops WILL change at the same time
◆An asynchronous counter is also referred to as a ripple counter
– the change that occurs to increment the counter starts at one end and “ripples” through to the other end
output of flip- flops
note: the states (outputs) of the flip-flops does not change at the same time; instead, the change ripples through to the other end
timing diagram of 4-bit ripple counter
J = K = 1: toggle function
all the inputs to the JK flip-flops are 1
the clock controls the toggling of output: if there is a clock pulse, the output is toggled
the JK flip-flops are sequentially connected: the output of the previous flip-flop serves as the clock (control signal) of the next flip-flop
0 1 2 3 4 5 6 7 15 0
Synchronous Counter ◆Synchronous counter
– use the outputs of N flip-flops to denote the number
– states change at the same time
– use synchronous counter as the example to show the design process of sequential circuits — from truth table to SOP to circuits
Example: 3-bit Synchronous Counter
◆Use 3 J-K flip-flops to implement 3-bit counter
– output of 3 J-K flip-flops: CBA
– states: 000 -> 001 -> 010 -> 011 -> 100 -> 101 -> 110 ->111 -> 000
– key: identify the required inputs to change one state to the next state
Example: 3-bit Synchronous Counter
conditions
state 1: 000
input: 0 d 0 d 1 d
state 2: 001
How can we obtain this table?
Goal: a truth table indicating the conditions for state transitioning
Example: 3-bit Synchronous Counter
Characteristic table of J-K
present output next output (current state) inputs (next state)
Excitation table of J-K
Example: 3-bit Synchronous Counter
Truth table
Now, we can use the same way in the designing of combinatorial circuits:
treat A, B, C as inputs (feedback path)
treat each J, K as a function of A, B,C
then construct a Karnaugh map for each J, K
Example: 3-bit Synchronous Counter
Truth table
Karnaugh map and simplified function
Example: 3-bit Synchronous Counter
Combinational Circuits
storage elements
Exercise after class: draw the timing diagram for this sequential circuit (how A, B, C would change with Clock?)
◆Use Karnaugh map for simplification
◆Sequential circuits
– different representations: characteristic table, circuits, and
timing diagram (the transformation among these)
– Use Flip-Flops to construct useful components
– Next Lecture: the procedure of designing sequential circuits
◆Reading: chapter 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com