Homework answers / question archive / COMBINATIONAL LOGIC Osameh Al-Kofahi TYPES OF LOGIC CIRCUITS Combinational Circuits ? Output is a function of the input only Sequential Circuits ? Output is a function of the current input and previous input state ? How can we know previous input state? ? We need storage (memory) COMBINATIONAL CIRCUITS A combinational circuit is an interconnection of logic gates

COMBINATIONAL LOGIC Osameh Al-Kofahi TYPES OF LOGIC CIRCUITS Combinational Circuits ? Output is a function of the input only Sequential Circuits ? Output is a function of the current input and previous input state ? How can we know previous input state? ? We need storage (memory) COMBINATIONAL CIRCUITS A combinational circuit is an interconnection of logic gates

Computer Science

Share With

COMBINATIONAL LOGIC Osameh Al-Kofahi TYPES OF LOGIC CIRCUITS Combinational Circuits ? Output is a function of the input only Sequential Circuits ? Output is a function of the current input and previous input state ? How can we know previous input state? ? We need storage (memory) COMBINATIONAL CIRCUITS A combinational circuit is an interconnection of logic gates. ? Transforms binary information from the given input data to a required output data ? The ? inputs come from an external source ? The produced ? outputs go to a certain destination ANALYSIS AND DESIGN Analysis Starts with Ends up with Design A digital circuit Specifications: clarify the required operation of the circuit Truth table, Boolean function, and understanding the operation of the circuit (what it does) A digital circuit ANALYSIS: EXAMPLE Label outputs of gates that are functions of input variables Label outputs of gates that are functions of input variables and previously labeled outputs Repeat labelling Write outputs and intermediate values as functions of input variables Build truth tables for all outputs Try to figure out what the circuit does ANALYSIS: EXAMPLE The truth table for all the outputs is shown to the right ?1 and ?2 are the outputs of the circuit How many 1’s in the input will set ?1 to 1? How many 1’s in the input will set ?2 to 1? Can you identify the function of this circuit? The circuit represents a full adder, where ?1 is the sum and ?2 is the carry DESIGN: EXAMPLE Objective: Build a BCD code to excess-3 code convertor. We know BCD from previous chapter. Excess-3 code adds 3 to each BCD code. For example, 1 ??? becomes 4 ??????−3 . Steps: Determine number of input and output bits Derive the truth table for each output Obtain the simplified Boolean expression Draw the logic circuit diagram DESIGN: EXAMPLE Valid BCD values range from 0 to 9 ? Are there any don’t-care conditions? Valid excess-3 values range from 3 to 12 ? 4-bits needed ? Their values are obtained by adding 3 to BCD values For each output, use the techniques learned in previous chapters to obtain the simplified Boolean expressions. Draw the corresponding digital circuit DESIGN: EXAMPLE The result is digital circuit (enclosed inside the square) that converts 4-bit BCD input to 4-bit excess-3 output COMBINATIONAL CIRCUITS There is a set of Standard Components that are extensively used in the design of digital systems. In the remaining of this chapter we will study: Binary Adder-Subtractor Decimal Adder Binary Multiplier Magnitude Comparator Decoders and Encoders Multiplexers and Demultiplexers HALF ADDER Description: performs binary addition of two bits Inputs: two bits Outputs: Sum and Carry bits Create the truth table The Boolean expressions can be easily obtained from the truth table HALF ADDER The logic circuit is very simple and can be implemented using an AND gate for the carry and an XOR gate for the sum. If multiple bits are being added, a half adder does not consider carry from the previous lower significant position. FULL ADDER Description: A full adder adds two significant bits in addition to the carry bit from the previous lower significant position Inputs: Bits ? and ? are the two significant bits ? is the carry bit from previous position Outputs: Sum bit ?, and Carry bit ? ? ? ? ? Full Adder ? FULL ADDER Create the truth table for the full adder Use K-maps to obtain the simplified forms of ? and ? FULL ADDER FULL ADDER It is easy to note that ? is the odd function, i.e., ? = 1 when an odd number of ones is present in input It is also easy to note that C is 1 if: 1. Bit ? and bit ? are 1’s. OR 2. One of ? or ? is a 1, and ? is a 1 A full adder can be implemented with two half adders FULL ADDER ? ? ? ? Full Adder ? BINARY ADDER Description: Add two ?-bit binary numbers with carry Inputs: 2? + 1 bits, ? bits for each number and a carry bit Output: ?-bit sum, and a carry bit If ? = 4, how many rows will the truth table have? The total number of bits will be 9. Eight bits for the two numbers and 1 carry bit. This means that the truth table will have 29 = 512 rows Is it feasible to deal with a truth table of this size? What can we do? Use modular design to create the ?-bit adder from ? full adders 4-BIT BINARY ADDER First number ?3 ?2 ?1 ?0 Second number ?3 ?2 ?1 ?0 Result ?4 ?3 ?2 ?1 ?0 The addition is done similar to regular addition. Start from least significant bits ?0 and ?0 (and ?0 if needed) and propagate carry to higher order bits. CARRY PROPAGATION The inputs of the n-bit adder are voltage signals with values of 0 or 5 volts. Similarly, the outputs are also voltage signals with values of 0 or 5 volts. If the output is read instantly (in 0 seconds) after the input signals are supplied, will the obtained result be correct? How long should we wait? We need to wait for the carry to propagate through all full adders. CARRY PROPAGATION We need to minimize the time needed for addition ? Addition is a basic building block in many digital circuits ? It is also the basis for other arithmetic operations Faster gates can be employed ? Physical limits prevent us from obtaining arbitrarily high speeds Smarter designs ? Time vs. Complexity ? Time can be improved, but the circuit will be more complicated ? Carry Lookahead Logic is typically used CARRY LOOKAHEAD LOGIC The ? ?? carry bit ?? is equal to: ?? = ??−1 ??−1 + ??−1 (??−1 ⊕ ??−1 ) Define the following: ?? = (?? ⊕ ?? ) and ?? = ?? ?? . Then ?? can be rewritten as: ?? = ??−1 + ??−1 ??−1 this recursive formula implies that we can write all carry bits in terms of ?0 as follows: CARRY LOOKAHEAD LOGIC Since the function for each output carry is a sum of products it can be implemented using a two-level implementation as we have seen in previous chapters. BINARY SUBTRACTOR Recall that subtraction can be done by using addition with complements To calculate ? − ?: ? Find ?′ the 2’s complement of ? ? Then calculate ? + ?′ Recall also: ? The 2’s complement can be calculated by adding 1 to the 1’complement ? The 1’s complement is simply bitwise inversion An n-bit binary subtractor can be implemented with ? full adders BINARY SUBTRACTOR This circuit performs the operation: ?−? Note that inverting ? and making carry ?0 = 1 is equivalent to adding ? with the 2’s complement of ?. This circuit is very similar to the addition circuit. Can we have one circuit that does both operation? 1 OVERFLOW EXAMPLES Can you explain the output of the following C++ programs? OVERFLOW When doing computations, computers store binary numbers in memory units called registers. ? A register can store a limited number of bits Assume we have a 4-bit computer that uses 4-bit registers. Suppose we want to add 12 and 6 using this computer. We need three registers, one holding 1100 2 , another for 0110 2 , and a third to store the result. What is the result of adding these binary numbers? And how will it be stored in the third register? 12 + 6 = 18 or 1100 + 0110 = 10010 since we have 4-bit registers, the MSB bit cannot be stored ? 1100 + 0110 = 0010 !!! This is an OVERFLOW It is important to be able to detect overflows when doing addition and subtraction. OVERFLOW IN UNSIGNED NUMBERS For unsigned numbers, overflow occurs when a carry out is produced. For example, add 15 The result is 16 10 10 = 1111 = ?0000 2 with 1 10 = 0001 2 2 The carry out bit indicates that the output will not fit and needs more bits OVERFLOW IN SIGNED NUMBERS Recall that in signed numbers the range of numbers is halved because the most significant bit represents sign. When does an overflow occur in signed arithmetic? Two cases to consider: 1. Will adding numbers with different signs result in an overflow? 2. Will adding numbers with the same sign result in an overflow? How can we detect overflow in signed arithmetic? Consider sign bits of operands and the sign bit of the result ? Construct a truth table of ?4 and ?3 in inputs ?3 , ?3 , ?3 and try to figure out the condition to detect overflow BINARY ADDER SUBTRACTOR WITH OVERFLOW DETECTION DECIMAL ADDER Description: Add two decimal digits in BCD Inputs: two BCD values and in carry Outputs: BCD sum and out carry BCD values range from 0 to 9 The largest sum that can be obtained is 9 + 9 + 1 = 19 ? The 1 is from carry in DECIMAL ADDER Note that the sum is valid if it is less than 9 A correction is needed if the sum exceeds 9 or a carry out in the binary sum occurs How can we convert the invalid binary output to valid BCD output? DECIMAL ADDER A B 4 4 ???? Decimal Adder 4 S ??? BINARY MULTIPLIER Binary multiplication is done in a fashion similar to decimal multiplication. ? Multiplicand is multiplied by each digit in multiplier to produce a partial product ? Starting from the least significant bit in multiplier, for each higher order bit the partial product needs to be shifted by one position. ? Sum all partial products to get the final product What is the maximum number of bit needed to represent the product of two ?-bit numbers? ? Try 11 2 × 10 2 and 11 2 × 11 2 Possible carry BINARY MULTIPLIER If ? had 3-bits (?2 ?1 ?0 ), will Half adders be sufficient? There will be the term ?0 ?2 that needs to be added with ?1 ?1 and the carry from the first half adder. We need to use full adders Build a 3-bit by 4-bit binary multiplier to calculate: ?2 ?1 ?0 × ?3 ?2 ?1 ?0 BINARY MULTIPLIER MAGNITUDE COMPARATOR Description: Compare two 4-bit numbers ? ands ?. Decide if ? = ?, ? > ?, or ? < ? Inputs: two 4-bit numbers (a total of 8-bits) Outputs: three inputs to signal one of the possible cases Assume ? = ?3 ?2 ?1 ?0 and ? = ?3 ?2 ?1 ?0 How to tell if ? = ?, ? > ?, or ? < ?? MAGNITUDE COMPARATOR Starting from the most significant bit, check if ?? and ?? If ?? = ?? , then go to lower order bits ??−1 and ??−1 If ?? > ?? , then ? > ? If ?? < ?? , then ? < ? What is the appropriate logic gate that checks for equality? How can we check if ?? > ?? or ?? < ?? ? MAGNITUDE COMPARATOR A B 4 4 4-bit Magnitude Comparator ?? ?=? DECODER Description: Decode an n-bit input into a 2? -bit output, where only one bit is 1 and all others are 0’s, such that the index of the high bit equals the value of the n-bit input Inputs: n-bits Outputs: 2? -bits A decoder is a combinational circuit that converts binary information from ? input lines to a maximum of 22 unique output lines n-to-m decoders produce ? ≤ 2? outputs where each output represents a minterm DECODERS Example: 2-to-4 decoder What is the truth table for this decoder ?0 ? ? 2x4 Decoder ?1 ?2 ?3 ? ? ?? ?? ?? ?? 0 0 ? 0 0 0 0 1 0 ? 0 0 1 0 0 0 ? 0 1 1 0 0 0 ? DECODERS Example2: 3x8 Decoder How to design such a decoder? DECODERS What is the use of decoders? They can be very helpful in implementing Logic Functions Implement the following functions using a 3x8 Decoder DECODERS Example: Can we use decoders to implement product of sums? Use a 3x8 decoder to implement the following functions as POSs and SOPs: ?1 ?, ?, ? = Π(0,1,3) ?2 ?, ?, ? = ∑(0, 2, 4,5) DECODERS If the decoder is implemented using NAND gates it will produce maxterms. This results in a decoder with Active-Low outputs. A 4x16 decoder with Active-Low outputs DECODERS Decoders and other building blocks often have one or more Enable inputs When the decoder is enabled, it operates normally otherwise it is disabled The Enable (??) input can be ActiveHigh or Active-Low Active-High: the decoder is enabled when the ?? is HIGH Active-Low: the decoder is enabled when the ?? is LOW DECODERS Decoders with ?? can be used to create larger decoders In-class exercise: A 4x16 decoder has 4 inputs ?3 ?2 ?1 ?0 and produces 16 outputs ?0 , ?1 , … , ?15 Construct a 4x16 decoder using two 3x8 decoders with enable Construct a 4x16 decoder using five 2x4 decoders with enable. 7-SEGMENT DISPLAY DECODER In class exercise: 1. Design a 4x10 decoder using 3x8 and 1x2 decoders 2. Use the 4x10 decoder to build a 7segment display decoder A 7-segment display decoder: ? Used to drive the 7-segment display ? Produces the suitable outputs to display digits from 0 to 9 on a 7-segment display ENCODERS Description: Inverse of a decoder. Takes 2? inputs numbered from 0 to 2?−1 , only one is HIGH and the rest are LOW, and produces ? outputs corresponding to the value of the high input number. Inputs: 2? -bits numbered from 0 to 2?−1 . Only one is HIGH. Outputs: ?-bits representing the value of the high input number In general, the inputs could be less than 2? ENCODERS Example: 4x2 encoder What is the truth table? ?0 ?1 ?2 ?3 4x2 Encoder ? ? ?? ?? ?? ?? ? ? 0 0 0 ? 0 0 0 0 ? 0 0 1 0 ? 0 0 1 0 ? 0 0 0 1 1 ENCODERS Two problems with encoders: 1. How to distinguish between the case when all inputs are 0’s and the case when no inputs are present? 2. What if the user asserted two or more inputs at the same time? Solutions: 1. Valid output indicator (?) 2. Priority encoders: produce the code for the largest asserted input ENCODERS 4x2 priority encoder What is the output if: ?2 = 1 and ?1 = 1 Note that ? is the most significant bit, and ? is the least significant. EXAMPLE In-class exercise: Use what you have learned so far to build a logic circuit to display the value of the pressed key on the numerical pad on the 7-segment display. Assume the keypad does not provide any kind of logic. It is just a group of buttons labeled from 0 to 9. MULTIPLEXERS Description: A multiplexer has multiple inputs and only one output. It directs one of the inputs to the single output based on a selection made using input selection lines. Inputs: 2? inputs, ? selection lines Outputs: only one output Often labeled MUX Think of a MUX as a data selector MULTIPLEXERS Example: 4x1 MUX What is the truth table for a MUX? ?0 ?1 ?2 4x1 MUX ?3 ?1 ?0 ?????? ?? ?? ? 0 0 ?0 0 1 ?1 1 0 ?2 1 1 ?3 MULTIPLEXERS Implementation of a 4x1 MUX A MUX may have an Enable input ? Not shown in the diagram A MUX can be also implemented using decoders Design an 8x1 MUX using a 3x8 decoder MULTIPLEXERS Multiplexers can be combined to provide multi-bit selection logic. ? Instead of selecting from 1-bit inputs, we can select from n-bit inputs Example 1: Build a Quadruple 2-to-1 MUX using 4 2-to-1 MUXs Inputs: two inputs (? and ?) each is 4-bits wide Output: 4-bit output (either ? or ?) Multiplexers can be combined to build larger MUXs. Example 2: Build a 4-to-1 MUX using three 2-to-1 MUXs MULTIPLEXERS Gate-level implementation of a Quadruple 2-to-1 MUX MULTIPLEXERS Multiplexers can be also used to implement Boolean Functions An n-bit Boolean function can be implemented using a MUX with n-1 selection lines How? 1. Use the n-1 most significant bits as selection lines 2. Express the function in terms of the remaining least significant input. Note that each of the 2?−1 combinations will be repeated twice. One with the LSB = 0 and the other with the LSB = 1 Four possible cases: ? = ?, ? = ?′, ? = 0, or ? = 1 MULTIPLEXERS Implement the following function using a multiplexer From the truth table, see how ? is expressed in terms of ? Do the same for the following: ? ?, ?, ? = ∑(1,2,6,7) DEMULTIPLEXERS Description: Demultiplexers do the opposite job of multiplexers. Directs a single input to one of the outputs based on the selection made using a set of selection lines. Inputs: a single input signal and ? selection lines Outputs: 2? output lines Abbreviated as a DMUX DEMULTIPLEXERS The truth table of a DMUX looks very similar to that of a decoder A decoder with Enable can be thought of a DMUX where the Enable value is the input and the decoder inputs are the selection lines ? 4x1 DMUX ?1 ?0 ?0 ?? ?? ?? ?? ?? ?? ?1 0 0 ? 0 0 0 ?2 0 1 0 ? 0 0 ?3 1 0 0 0 ? 0 1 1 0 0 0 ? SYNCHRONOUS SEQUENTIAL LOGIC Osameh Al-Kofahi INTRODUCTION Combinational Logic: Output depends only on input Sequential Logic: Output depends on input and previous state ? To know previous state we need to store it ? In this chapter we will study basic memory elements Feedback path SEQUENTIAL CIRCUITS A sequential circuit usually has a combinational circuit that does a certain task The combinational logic will be affected by the external inputs and the current state External inputs will also determine the conditions to change the memory state Feedback path SEQUENTIAL CIRCUITS Synchronous There are two types of Sequential Circuits: Synchronous Sequential Circuits: behavior can be defined from the knowledge of its signals at discrete instants of time. ? Clocked-Circuit: the discrete time instants are defined by a clock ? The clock orchestrates the operation of the circuit ? Easier to analyze and design Asynchronous Sequential Circuits: behavior depends upon the input signals at any instant of time and the order in which the inputs change ? Hard to analyze and design Asynchronous SYNCHRONOUS SEQUENTIAL CIRCUITS Synchronization depends on a clock generator ? Denoted by ????? or ??? ? Clock signal is distributed to all components Clock pulses will determine when the computations will take place based on the external inputs ? State and calculations are affected by either the rising edge or the falling edge of the clock ? The clock period must be enough to allow the outputs of circuit components to stabilize The storage or memory elements used in synchronous circuits are called Flip-Flops ? A flip-flop is capable of storing only one bit ? The output of a flip-flop is either a 1 or a 0 ? The output of a flip-flop will be determined by its inputs and the current bit its storing STORAGE ELEMENTS: LATCHES VS. FLIP-FLOPS A storage element can maintain a binary state ? The stored state is controlled by circuit inputs ? State is maintained as long as power is supplied Latches vs. Flip-flops Latch: a storage element that changes state based on input signal levels (level-sensitive) Flip-Flop: a storage element that changes state based on a clock transition (edge-sensitive) Latches are used to build Flip-Flops SR LATCH WITH NOR GATES The SR latch can be in one of two states: When ? = 1, ? = 0 the latch is Set (stores a 1) When ? = 0, ? = 1 the latch is Reset (stores a 0) The latch preserves state when S and R are zeros When ? = 0, ? = 0 the output depends on the previous state S and R cannot be both ones because this may result in unpredictable output. How? SR Latch using NOR gates SR LATCH WITH NAND GATES The SR latch can be in one of two states: When ? = 0, ? = 1 the latch is Set (stores a 1) When ? = 1, ? = 0 the latch is Reset (stores a 0) The latch preserves state when S and R are zeros When ? = 1, ? =1 the output depends on the previous state S and R cannot be both zeros Also known as ? ′ ?′ Latch SR Latch using NAND gates SR LATCH WITH ENABLE Note that the NAND acts as an inverter when EN=1 ? (? . 1)′ = ?′ The operation will be similar to the SR latch using NOR gates State will not change if the latch is disabled (EN=0) or S=R=0 The state EN=S=R=1 is not allowed because it will result in unpredictable output Can we avoid this unwanted state? D LATCH Instead of using two inputs, use one input as shown in the figure This eliminates the undesired state When EN=1, the value of D shows at the output ? ? Transparent Latch When EN goes to 0, the value of D is retained LATCHES: BLOCK DIAGRAMS THE PROBLEM WITH LATCHES A sequential circuit has memory elements and a combinational circuit that provides a certain functionality ? Input of memory element = output of combinational circuit = ? ? Input of combinational circuit = ?(external inputs, ?) Latches are level sensitive, i.e., as long as the memory elements are enabled: If Inputs change ? ? may change ? ? may change ? ? may change again ? ? may change again ? ? may change … and so on. ? ? Feedback path ? THE PROBLEM WITH LATCHES To solve the problem we need to make the latches change state only at specific time instants. In practice, these time instants are defined by the transitions of a clock signal That is, instead of being level-sensitive, we want to have latches that are edge-sensitive Edge sensitive latches are called Flip-Flops Synchronous EDGE-TRIGGERED D FLIP-FLOP When ??? = 0: A D Flip-Flop that changes state on The negative edge of the clock ?1 = 0? ? does not change ?2 = 1? ? can change, but it won’t. Why? Because ? = ? When ??? = 1: ?1 = 1? ? changes with ? ?2 = 0? ? stays the same regardless of ? On the falling edge: ? = ? and it stays the same until the next falling edge ?1 ?2 EDGE-TRIGGERED D FLIP-FLOP Another implementation uses three SR latches ? = ? when ??? = 0 If ??? = 0: ? = ? = 1? No change in ? or ?′ Since ? = 1? ? = 1. ? ? ? = 1. ? ′ ′ ′ = ?′ =? ? = ?′ when ??? = 0 EDGE-TRIGGERED D FLIP-FLOP At the rising edge of the clock, when ??? becomes 1 ? = 1. ? ′ ? = 1. ?. ? = (1. ?)′ = ?′ ′ ? = ? when ??? = 0 = (1. ? ′ . ?′)′ = ? ? = ?. ? ′ = ?. ? ′ ? = ?. ? ′ = ? ′ . ? ′ = ?′ (no change) ′ = ? (no change) 1) If ? = ??? = 0??′ = ?. ? ′ = (0. ?)′ = 1 ?? = 1?? = ?. ? ′ ′ = 1.1 ′ = 0 2) If ? =1?? = 0?? = ?. ?′ ′ = (0. ?)′ = 1 ?? =1??′ = ?. ? ′ = 1.1 ′ = 0 That is: ? = ? and ?′ = ?′ ? = ?′ when ??? = 0 EDGE-TRIGGERED D FLIP-FLOP What happens if ? changes while ??? = 1? ? = ? when ??? = 1 That is ? changed to ?′ ? = ?. ? ′ = ?′. ? ? = ?. ? ′ = 1. ? ′ ? = ???. ? ′ ? = ???. ?. ? ′ ′ = 1. ? ′ ′ = 0 =1 ? = ?′ on rising edge = ? (no change) ′ = ?′ (no change) = 1.1. ? ′ ′ = ? (no change) Since ? and ? stayed the same ? and ?′ will stay the same also ? = ? on rising edge ? = ?′ when ??? = 1 D FLIP-FLOPS ??? ? 0 OR 1 X ↑ ↑ Next State Next State ??? ? No change 0 OR 1 X No change 0 ? = 0, ? ′ = 1 ↓ 0 ? = 0, ? ′ = 1 1 ? = 1, ? ′ = 0 ↓ 1 ? = 1, ? ′ = 0 JK FLIP-FLOPS D Flip-Flops can either set or reset on the rising clock edge. JK Flip-Flops can set, reset, complement, store on the rising clock edge Characteristic Table JK FLIP-FLOP: EXAMPLE T FLIP-FLOPS Toggle Flip-Flop A T flip-flop provides two functionalities ? Preserve ? Complement Can be obtained from JK or D flip-flops Characteristic Table CHARACTERISTIC TABLES Characteristic tables define the next state in terms of the current state and the input ?(?) is the current state ? Before clock edge ?(? + 1) is the next state ? After the clock edge CHARACTERISTIC EQUATIONS Provide the same information in the characteristic tables D flip-flop: ? ?+? =? JK flip-flop: ? ? + ? = ??′ + ?′ ? T flip-flop: ? ? + ? = ??′ + ?′ ? How can we derive the characteristic equations from the characteristic tables? DIRECT INPUTS When power is first turned on, what is the state of a flip-flop? Direct inputs are used to initialize the flip-flop to a set or reset state 0 1 1 ASYNCHRONOUS INPUTS PREset (PRE): Sets the flip-flop CLearR (CLR): Resets the flip-flop In this example, both are active-low ANALYSIS OF SEQUENTIAL CIRCUITS Analysis describes what a given circuit will do under certain operating conditions To understand the operation of a sequential circuit we need to understand the relationship between its states. A state diagram provides an abstract view of these relationships. To obtain a state diagram the analysis proceeds as follows: State Equations: algebraic expression describing next state in terms of current state and input ? Also called transition equations State Tables: the same information of a state equation in tabular form State Diagrams: the same information shown by a diagram ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE A sequential circuit with two D flip-flops ? Let’s call them ? and ? D flip-flops are transparent: their input shows on the output on clock edge. Therefore, the state equations are: ? ? + 1 = ? ? ? ? + ? ? ?(?) ? ? + 1 = ?′ ? ?(?) Can be also written as: ? ? + 1 = ?? + ?? ? ?? = ?? + ?? ? ? + 1 = ?′ ? ? ?? = ?′ ? The present-state value of output ? will be: ? = ? + ? ?′ ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE State equations can be expressed in state tables For a sequential circuit with ? flip-flops and ? inputs the table needs to have 2?+? rows The table will have ? columns for the flip-flops The table will also have a column for each output Build the state table using the following state equations: ? ? + 1 = ?? + ?? ? ? + 1 = ?′ ? ? = ? + ? ?′ ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE The state table can be written in a different way: The input conditions are enumerated under the nextstate and output sections. For each present state, there are two possible next states and outputs, depending on the value of the input ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE A sequential circuit with ? flip-flops, has ?? different states. The relationship between these states and how the circuit changes state can be expressed in a state diagram. The numbers inside circles are the states The labels on arrows are ?????/?????? Note that the bit value of the output occurs during the present state and with the indicated input ? It has nothing to do with the transition to the next state. What does the circuit do? ANALYSIS OF SEQUENTIAL CIRCUITS Derive the state equation, state table, and state diagram for the following sequential circuit: What is the functionality provided by this circuit? ANALYSIS OF SEQUENTIAL CIRCUITS Analysis for sequential circuits using other flip-flop types: ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Analyze the sequential circuit shown to the right: Steps: ? ? ? ? Determine input equations Use input equations to determine state equations From state equations create state table From state table create state diagram Note: the only outputs in the circuit are the outputs of flip-flops themselves. ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Input equations: State equations: State Table ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Note that: ? Edges only have one number (the input) ? The output is a function of current state only Such a state diagram represents a Moore Finite State Machine ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Analyze the sequential circuit shown to the right Same steps: ? ? ? ? Determine input equations Use input equations to determine state equations From state equations create state table From state table create state diagram Note that the output is dependent on only the current state ? this is also a Moore machine ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Input equations: State equations: Output equation: State Table ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Note that since the output only depends on the current state, it should be indicated inside each state This sequential circuit counts from 00 to 11 (and repeats again from 00) as long as the input is 1 ? It preserves the count when the input is 0 ? It produces 1 when a full count to 11 is made MOORE VS. MEALY STATE MACHINES Mealy: - Output is a function of input and current state - Outputs may change if input changes during clock cycle Moore: - Output is a function of current state - Output is synchronized with clock edges. Why? STATE REDUCTION State reduction: The reduction in the number of flip-flops in a sequential circuit State-reduction algorithms aim to reduce the number of states, while keeping the external input–output requirements unchanged. A reduction in the number of states may (or may not) result in a reduction in the number of flip-flops. Reducing the number of flip-flops may sometimes result in needing more combinational gates for inputs and/or outputs. STATE REDUCTION State reduction works by identifying equivalent states then removing the duplicates State equivalency: two states are equivalent if, for each member of the set of inputs, they give exactly the same output and send the circuit either to the same state or to an equivalent state Consider the state table for the zero-detection example and try to find equivalent states. THE DESIGN PROCEDURE The design of a sequential circuit starts from a set of specifications and produces a logic diagram. The procedure usually goes through the following steps: THE DESIGN PROCEDURE: AN EXAMPLE Objective: Design a sequence detector that detects three consecutive 1’s in a stream of input bits. Identify states and the transition rules between them What are the states? ?0 : no 1’s received, ?1 : one 1 is received, ?2 : two 1’s are received, and ?3 : three 1’s are received How many flip-flops are needed? How do we go from a state to another? And how is the output related to states and input? Mealy vs. Moore THE DESIGN PROCEDURE: AN EXAMPLE The circuit can be modeled using a Moore FSM ? Mealy is also possible The state table can be built from the state diagram Next step? Assuming D flip-flops are used, what are the input equations? THE DESIGN PROCEDURE: AN EXAMPLE For D flip-flops the input equations are the same as the next state equations Input equations are: Now we can draw the circuit THE DESIGN PROCEDURE: AN EXAMPLE The circuit using D flip-flops DESIGN USING OTHER FLIP-FLOPS Can we use other types of flip-flops to design sequential circuits? How will the procedure change if JK flip-flops are used? In D flip-flops, the input equations can be obtained directly from the state equations because ?? = ?(? + 1) In JK flip-flops, we need excitation tables Excitation tables show the needed inputs for a given change of state EXCITATION TABLES JK flip-flop Characteristic Table ? ? ? ?(? + ?) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 JK flip-flop Excitation Table + DESIGN USING JK FLIP-FLOPS Assume we have the following state table How should we continue? We should use the excitation table for JK flipflops to figure out the inputs causing the shown changes in state. JK flip-flop Excitation Table + DESIGN USING JK FLIP-FLOPS DESIGN USING JK FLIP-FLOPS DESIGN USING JK FLIP-FLOPS DESIGN USING T FLIP-FLOPS The process is the same, but we need to use the excitation tables for T flip-flops to figure out the input equations. Example: Design a binary counter that counts from 0 to 7 An ?-bit binary counter counts up with every clock edge, and when it reaches 2? − 1 it will go back to 0 The state diagram is shown to the right ? In this example, the only input is the clock. That is why the transitions are not labeled DESIGN USING T FLIP-FLOPS From the state diagram, construct the state table for the binary counter and use the excitation table for the T flip-flop to show the needed input values T flip-flop Characteristic Table T flip-flop Excitation Table ? ? ?(? + ?) 0 0 0 0 1 1 1 0 1 1 1 0 + DESIGN USING T FLIP-FLOPS DESIGN USING T FLIP-FLOPS REGISTERS AND COUNTERS Osameh Al-Kofahi INTRODUCTION In this chapter we study two types of sequential circuits 1. Registers: An n?bit register consists of a group of ? flip?flops ? Stores n-bits of binary information 2. Counters: A counter is a register that goes through a predetermined sequence of binary states ? Synchronous vs Asynchronous counters We will start with counters to continue from where we left at the end of Chapter 5 COUNTERS Counters are of two types: 1. Synchronous: all flip-flops in the counter are triggered by the same clock 2. Asynchronous: flip-flops are triggered by different clocks ? Usually, a flip-flop uses the output of another flip-flop as clock What is the type of the counter we saw in Chapter 5? BINARY COUNTERS Binary counters are easy to implement Note the pattern in state changes: The LSB ?0 is always changing state (always toggling) ?1 only changes state when the current state of ?0 is 1 ?2 only changes when all lower order bits are 1 If the counter had 4-bits, can you guess how will ?3 change? It will change when all lower order bits are 1 BINARY COUNTERS The figure shows a 4-bit counter implemented using JK flip-flops Recall that a JK flip-flop can work like a T flip-flop ? If J and K are tied together For a specific bit in the counter, note how the JK inputs will be both 1 (and thus toggle the bit) only if all lower order bits in the count are 1. This counter counts up. Can we build a counter that counts down? How will the individual states toggle? BINARY COUNTERS Note how each bit in the count changes state ?? ?? ?? 1 1 1 1 1 0 To count down, each bit in the count toggles when all lower order bits are 0’s 1 0 1 1 0 0 The design of a down counter is very similar to the design of the up counter. 0 1 1 0 1 0 Can the same counter circuit count up or down? 0 0 1 0 0 0 ?0 is always changing state (always toggling) How about ?1 and ?2 ? BINARY COUNTERS If ?? = 1: ? ?1 = 0??2 = ?4 = ?6 = 0? ???? does not affect the circuit ? The T flip-flop inputs (?0 , ?1 , ?2 , ??? ?3 ) are controlled by ??. This will be similar to the up counter using JK from before. If ?? = 0: ? ? ? ? ? ?3 = ?5 = ?7 = 0 ? ?? does not affect the circuit The T flip-flop inputs (?0 , ?1 , ?2 , ??? ?3 ) are controlled by ????, ?2 , ?4 , and ?6 . ?2 = 1 (?1 will toggle) when ?? = 0, ???? = 1, and ?0 = 0 (i. e. , ?′0 = 1) ?4 = 1 (?2 will toggle) when ?? = 0, ???? = 1, and ?0 = ?1 = 0 ?6 = 1 (?3 will toggle) when ?? = 0, ???? = 1, and ?0 = ?1 = ?2 = 0 Up and Down work like selection lines in MUXs BCD COUNTERS BCD counters count from 0000 to 1001 and go back to 0000 In-class exercise: Build a BCD up/down counter 1) Figure out input equations to count up 2) Figure out input equations to count down 3) Use selection lines and MUXs to choose between counting up or down RIPPLE COUNTERS Ripple counters are asynchronous counters because flipflops trigger other flip-flops Ripple counters can be easily designed using T flip-flops In binary ripple counters the flip-flop inputs are held at logic 1, and toggling is controlled by the clock alone The transitions of lower order bits are fed as a clock to higher order bits. ? ?0 is fed to the clock of ?1 , ?1 is fed to the clock of ?2 , and so on. Does ?1 change on the rising or the falling edge of ?0 ? How about ?2 using ?1 as a clock? RIPPLE COUNTERS To count up, the T flip-flops should be negative-edge flip-flops In-class exercise: Draw the timing diagram RIPPLE COUNTERS How will the design be different if we want to count down? ?? ?? ?? ?? Again, note how each bit changes if we use the lower order bit as a clock. 1 1 1 1 1 1 1 0 Does ?1 change on the rising or the falling edge of ?0 ? 1 1 0 1 Does ?2 change on the rising or the falling edge of ?1 ? 1 1 0 0 1 0 1 1 1 0 1 0 To count down, each bit needs to toggle at the rising edge of the lower order bit transition 1 0 0 1 1 0 0 0 ? only change the flip-flops to positive edge flip-flops 0 1 1 1 How about ?3 using ?2 as a clock? BCD RIPPLE COUNTERS The operation is normal from 0 to 9, then we need to go back to 0 ? We need to handle this exceptional transition from 9 to 0. Taking a look on state transitions in the BCD counter, we can see that the exceptional transitions are for ?1 (should be 1 but it is a 0) and ?3 (should be a 1 but it is a 0 also) Normal operation BCD ripple counters count from 0 to 9 in a loop ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Exceptions BCD RIPPLE COUNTERS The only negative edge is at ?0 (other bits will not change) ? ?1 and ?3 need to be clocked by ?0 ?1 is already clocked by ?0 , but ?3 is clocked by ?2 ? ?3 clock needs to be changed to ?0 Modifying ?3 ’s clock to ?0 requires modifying its input equation also, i.e., ?3 and ?3 cannot be 1’s always. Normal operation Note that for ?1 and ?3 to change state then a negative edge should occur on their clock inputs ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Exceptions By examining state transitions we note that the exceptional case for ?1 can be identified by a negative clock edge from ?0 having ?3 = 1. We need to modify ?1 and ?1 to handle this exceptional case. But other than that, ?1 ands ?1 need to be 1’s for ?1 to toggle properly. If we keep ?1 = 1 and make ?1 = ?3 ′, then ?1 will toggle normally and when ?3 becomes a 1 and ?0 toggles from 1 to 0 ?1 will be reset (since ?1 = 0 and ?1 = 1). Normal operation BCD RIPPLE COUNTERS ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Instead of becoming 1, ?1 is reset on a negative clock edge from ?0 having ?3 = 1 BCD RIPPLE COUNTERS ?3 will change to 1 only if the previous states of ?1 and ?2 are both ones when a negative clock edge from ?0 occurs. Other than that ?3 = 0, i.e., it can be held at reset Keeping ?3 = 1 and having ?3 = ?2 ?1 will keep ?3 reset at 0 except if both ?1 and ?2 are ones Normal operation For ?3 , we can see that it can be derived from ?1 and ?2 ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 BCD RIPPLE COUNTERS Note that: ?1 = 1 and ?1 = ?3 ′ ?3 = 1 and ?3 = ?2 ?1 There is a much simpler way to implement BCD ripple counters BCD ripple counters can be cascaded REGISTERS A register is an n-bit storage element To store n bits, a register needs n flip-flops Registers may also include additional logic gates to perform certain tasks The logic gates usually control how the data is transferred to the register The figure to the right shows a very simple 4-bit register Without external control logic the stored state will change with every clock cycle based on inputs REGISTERS WITH PARALLEL LOAD Transferring new information into a register is referred to as loading the register If all bits are loaded simultaneously with a common clock pulse, we say that the loading is done in parallel If we want to hold the contents unchanged, we have two options: 1. Disable clock by an AND gate and an Enable signal ? It is not advised to do logic operations with clock signals. ? Clocks should control when but not what to do. 2. Use logic gates to control the inputs REGISTERS WITH PARALLEL LOAD When ???? = 0, the state will be kept the same since Q ? + 1 = ? for D flip-flops When ???? = 1, the flip-flops will be loaded from inputs in parallel The logic gates work as MUXs In-class exercise: Design a 4-bit register with parallel load using JK flip-flops SHIFT REGISTERS A shift register is a register capable of shifting the binary information held in each cell to its neighboring cell The logical configuration of a shift register consists of a chain of flip?flops in cascade, with the output of one flip?flop connected to the input of the next flip?flop In the figure, the content gets shifted one step to the right with every clock pulse ? This is called right shift In-class exercise: Design a 4-bit shift register with shift control line SHIFT REGISTERS Shift registers have many application. One important application is serial-to-parallel and parallel-to-serial conversion. Data is processed in bytes (or words), but it is commonly transferred in bits For example USB (Universal Serial Bus) ports transmit data serially In-class exercise: 1. Design a 4-bit serial-to-parallel convertor 2. Design a 4-bit parallel-to-serial convertor UNIVERSAL SHIFT REGISTER A register is called a universal shift register if it can shift in both directions and it has parallel?load capabilities Such a register can be easily designed using multiplexers SERIAL ADDITION Binary numbers can be added serially ? ? ? ? The two binary numbers are stored in shift registers Bits get shifted one at a time from both numbers The shifted bits are added with a 1-bit binary adder The carry bit is kept to be used when adding the next pair of bits ? The sum can be shifted into a third register or it can replace the augend In-class exercise: Build the same circuit using a JK flip-flop to keep carry and without using the clock in logic BINARY COUNTER WITH PARALLEL LOAD A parallel load register that can count Assume the following functionalities are to be provided: ? Hold value ? Parallel Load ? Count up We want to have the capability to store. Therefore, we can use JK flip-flops since they provide this functionality To choose between these three functionalities we need two control lines Let us call them Count and Load. Start with the truth table for a single flip-flop BINARY COUNTER WITH PARALLEL LOAD We have seen at the beginning of the chapter that in a counter a flip-flop changes state (toggels) if all lower order counter bits are 1’s ?−1 ? Recall that to toggle a JK flip-flop, we need ? = ? = 1 = Π?=0 ?? To load an input ?? into a JK flip-flop ? If ?? = 0 ? J=0, K=1 to Reset ? If ?? = 1 ? J=1, K=0 to Set ? Note that ? = ?? and ? = ?? ′ The truth table for a single flip-flop is: ????? ???? ? ? ?????? Design using: 0 0 0 0 Hold ? JK flip-flops ? 4x1 MUXs 0 1 ?? ?? ′ Load 1 ? 1 1 ?−1 Count (Π?=0 ?? ) BINARY COUNTER WITH PARALLEL LOAD The gate level implementation BLOCK DIAGRAMS To design sequential circuits, it is important to be able to work with block diagrams of sequential circuits components. For each block, there should be a function table that explains what it does in response to inputs. For example: IN-CLASS EXERCISE 1) Design an 8-bit counter using two 4-bit counters with Count and Load functions. 2) Using 4-bit binary counters, design a binary counter that counts from 0 to 128. 3) Design a serial to parallel convertor using a 4-bit shift register, a 4-bit parallel load register, and a binary counter of suitable size. The result of the conversion is stored in the parallel load register 4-bits at a time. That is, 4-bits will be loaded and kept until the next 4-bits are ready to be loaded. American University of Sharjah Lab Instructor: Mr. Mohmmed Elnawawy Office: EB2-001 Phone: 971-6-5152975 e-mail: melnawawy@aus.edu Semester: Fall 2020 College of Engineering Dept of Computer Science & Engg P. O. Box 26666 Sharjah, UAE COE221 Lab Final Exam Name: ............................................................................................... Student ID: Enter the rightmost 5 digits of your ID in the boxes below Symbol I J K L M ID The letters I, J, K, L, and M are parameters that you will use in this exam. They will be italicized, otherwise they are not parameters. Example: L = 2, and M = 5 à LM = 25, L+M = 2+5 = 7, and so on. NOTE: Your need to show all the steps for every question. QUESTION 1 Design a circuit with four inputs and one output. The inputs represent a number from 0 to 15. The output should be TRUE if the number is greater than or equal to (M+1), and FALSE otherwise. A. Draw the truth table of the system. (2 points) B. Find the simplified expression using k-map. (1 points) C. Specify the chip number and the quantity of chips required to implement the unsimplified and the simplified expressions. (3 points) For example: Chip: 7400 Quantity: 4 Chip: 7402 Quantity: 3 D. Draw the simplified circuit. (1 points) QUESTION 2 Design a home security system using the 74999 (2-to-4 decoder) chip shown below and any necessary extra gates. The home security system consists of some sensors, namely a pressure sensor (P), an infrared sensor (I), a motion sensor (M), and a glass break sensor (G). The home security system also contains a siren (S) that produces sound if motion, and glass break are detected or if pressure, infrared, and motion are detected. A. List the truth table of the circuit. (2 points) 1 B. How many 74999 chips are needed to implement the fire alarm system? (1 point) C. Draw the system using the minimum possible number of 74999 chips. You are only allowed to use the 74999 chip and 2-input gates. Show all the connections to the 74999 chips. (2 points) QUESTION 3 Design a mealy sequence recognizer that: • Detects the sequence L or 1010. • Allows Overlapping. • Uses binary encoding. • Uses the 7476 JK Flip-Flop IC. Important: • L is a 3-bit number. So, if your L is 1 the sequence recognizer detects 001 or 1010. • If your L is 8, your machine should detect 100 or 1010 instead. • If your L is 9, your machine should detect 101 or 1010 instead. • You are not allowed to use the shift register approach. A. Show all the steps of the state design approach. Ø Draw the state diagram. (3 points) Ø Write the state table. (2 points) Ø Show the state encoding. (1 point) Ø List the truth table entries. (3 points) Ø Use k-maps to derive the simplified functions. Use the minimum number of gates. (3 points) B. How many 7476 chips are needed to implement the circuit? (1 point) 2 REGISTERS AND COUNTERS Osameh Al-Kofahi INTRODUCTION In this chapter we study two types of sequential circuits 1. Registers: An n?bit register consists of a group of ? flip?flops ? Stores n-bits of binary information 2. Counters: A counter is a register that goes through a predetermined sequence of binary states ? Synchronous vs Asynchronous counters We will start with counters to continue from where we left at the end of Chapter 5 COUNTERS Counters are of two types: 1. Synchronous: all flip-flops in the counter are triggered by the same clock 2. Asynchronous: flip-flops are triggered by different clocks ? Usually, a flip-flop uses the output of another flip-flop as clock What is the type of the counter we saw in Chapter 5? BINARY COUNTERS Binary counters are easy to implement Note the pattern in state changes: The LSB ?0 is always changing state (always toggling) ?1 only changes state when the current state of ?0 is 1 ?2 only changes when all lower order bits are 1 If the counter had 4-bits, can you guess how will ?3 change? It will change when all lower order bits are 1 BINARY COUNTERS The figure shows a 4-bit counter implemented using JK flip-flops Recall that a JK flip-flop can work like a T flip-flop ? If J and K are tied together For a specific bit in the counter, note how the JK inputs will be both 1 (and thus toggle the bit) only if all lower order bits in the count are 1. This counter counts up. Can we build a counter that counts down? How will the individual states toggle? BINARY COUNTERS Note how each bit in the count changes state ?? ?? ?? 1 1 1 1 1 0 To count down, each bit in the count toggles when all lower order bits are 0’s 1 0 1 1 0 0 The design of a down counter is very similar to the design of the up counter. 0 1 1 0 1 0 Can the same counter circuit count up or down? 0 0 1 0 0 0 ?0 is always changing state (always toggling) How about ?1 and ?2 ? BINARY COUNTERS If ?? = 1: ? ?1 = 0??2 = ?4 = ?6 = 0? ???? does not affect the circuit ? The T flip-flop inputs (?0 , ?1 , ?2 , ??? ?3 ) are controlled by ??. This will be similar to the up counter using JK from before. If ?? = 0: ? ? ? ? ? ?3 = ?5 = ?7 = 0 ? ?? does not affect the circuit The T flip-flop inputs (?0 , ?1 , ?2 , ??? ?3 ) are controlled by ????, ?2 , ?4 , and ?6 . ?2 = 1 (?1 will toggle) when ?? = 0, ???? = 1, and ?0 = 0 (i. e. , ?′0 = 1) ?4 = 1 (?2 will toggle) when ?? = 0, ???? = 1, and ?0 = ?1 = 0 ?6 = 1 (?3 will toggle) when ?? = 0, ???? = 1, and ?0 = ?1 = ?2 = 0 Up and Down work like selection lines in MUXs BCD COUNTERS BCD counters count from 0000 to 1001 and go back to 0000 In-class exercise: Build a BCD up/down counter 1) Figure out input equations to count up 2) Figure out input equations to count down 3) Use selection lines and MUXs to choose between counting up or down RIPPLE COUNTERS Ripple counters are asynchronous counters because flipflops trigger other flip-flops Ripple counters can be easily designed using T flip-flops In binary ripple counters the flip-flop inputs are held at logic 1, and toggling is controlled by the clock alone The transitions of lower order bits are fed as a clock to higher order bits. ? ?0 is fed to the clock of ?1 , ?1 is fed to the clock of ?2 , and so on. Does ?1 change on the rising or the falling edge of ?0 ? How about ?2 using ?1 as a clock? RIPPLE COUNTERS To count up, the T flip-flops should be negative-edge flip-flops In-class exercise: Draw the timing diagram RIPPLE COUNTERS How will the design be different if we want to count down? ?? ?? ?? ?? Again, note how each bit changes if we use the lower order bit as a clock. 1 1 1 1 1 1 1 0 Does ?1 change on the rising or the falling edge of ?0 ? 1 1 0 1 Does ?2 change on the rising or the falling edge of ?1 ? 1 1 0 0 1 0 1 1 1 0 1 0 To count down, each bit needs to toggle at the rising edge of the lower order bit transition 1 0 0 1 1 0 0 0 ? only change the flip-flops to positive edge flip-flops 0 1 1 1 How about ?3 using ?2 as a clock? BCD RIPPLE COUNTERS The operation is normal from 0 to 9, then we need to go back to 0 ? We need to handle this exceptional transition from 9 to 0. Taking a look on state transitions in the BCD counter, we can see that the exceptional transitions are for ?1 (should be 1 but it is a 0) and ?3 (should be a 1 but it is a 0 also) Normal operation BCD ripple counters count from 0 to 9 in a loop ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Exceptions BCD RIPPLE COUNTERS The only negative edge is at ?0 (other bits will not change) ? ?1 and ?3 need to be clocked by ?0 ?1 is already clocked by ?0 , but ?3 is clocked by ?2 ? ?3 clock needs to be changed to ?0 Modifying ?3 ’s clock to ?0 requires modifying its input equation also, i.e., ?3 and ?3 cannot be 1’s always. Normal operation Note that for ?1 and ?3 to change state then a negative edge should occur on their clock inputs ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Exceptions By examining state transitions we note that the exceptional case for ?1 can be identified by a negative clock edge from ?0 having ?3 = 1. We need to modify ?1 and ?1 to handle this exceptional case. But other than that, ?1 ands ?1 need to be 1’s for ?1 to toggle properly. If we keep ?1 = 1 and make ?1 = ?3 ′, then ?1 will toggle normally and when ?3 becomes a 1 and ?0 toggles from 1 to 0 ?1 will be reset (since ?1 = 0 and ?1 = 1). Normal operation BCD RIPPLE COUNTERS ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 Instead of becoming 1, ?1 is reset on a negative clock edge from ?0 having ?3 = 1 BCD RIPPLE COUNTERS ?3 will change to 1 only if the previous states of ?1 and ?2 are both ones when a negative clock edge from ?0 occurs. Other than that ?3 = 0, i.e., it can be held at reset Keeping ?3 = 1 and having ?3 = ?2 ?1 will keep ?3 reset at 0 except if both ?1 and ?2 are ones Normal operation For ?3 , we can see that it can be derived from ?1 and ?2 ?? ?? ?? ?? 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 BCD RIPPLE COUNTERS Note that: ?1 = 1 and ?1 = ?3 ′ ?3 = 1 and ?3 = ?2 ?1 There is a much simpler way to implement BCD ripple counters BCD ripple counters can be cascaded REGISTERS A register is an n-bit storage element To store n bits, a register needs n flip-flops Registers may also include additional logic gates to perform certain tasks The logic gates usually control how the data is transferred to the register The figure to the right shows a very simple 4-bit register Without external control logic the stored state will change with every clock cycle based on inputs REGISTERS WITH PARALLEL LOAD Transferring new information into a register is referred to as loading the register If all bits are loaded simultaneously with a common clock pulse, we say that the loading is done in parallel If we want to hold the contents unchanged, we have two options: 1. Disable clock by an AND gate and an Enable signal ? It is not advised to do logic operations with clock signals. ? Clocks should control when but not what to do. 2. Use logic gates to control the inputs REGISTERS WITH PARALLEL LOAD When ???? = 0, the state will be kept the same since Q ? + 1 = ? for D flip-flops When ???? = 1, the flip-flops will be loaded from inputs in parallel The logic gates work as MUXs In-class exercise: Design a 4-bit register with parallel load using JK flip-flops SHIFT REGISTERS A shift register is a register capable of shifting the binary information held in each cell to its neighboring cell The logical configuration of a shift register consists of a chain of flip?flops in cascade, with the output of one flip?flop connected to the input of the next flip?flop In the figure, the content gets shifted one step to the right with every clock pulse ? This is called right shift In-class exercise: Design a 4-bit shift register with shift control line SHIFT REGISTERS Shift registers have many application. One important application is serial-to-parallel and parallel-to-serial conversion. Data is processed in bytes (or words), but it is commonly transferred in bits For example USB (Universal Serial Bus) ports transmit data serially In-class exercise: 1. Design a 4-bit serial-to-parallel convertor 2. Design a 4-bit parallel-to-serial convertor UNIVERSAL SHIFT REGISTER A register is called a universal shift register if it can shift in both directions and it has parallel?load capabilities Such a register can be easily designed using multiplexers SERIAL ADDITION Binary numbers can be added serially ? ? ? ? The two binary numbers are stored in shift registers Bits get shifted one at a time from both numbers The shifted bits are added with a 1-bit binary adder The carry bit is kept to be used when adding the next pair of bits ? The sum can be shifted into a third register or it can replace the augend In-class exercise: Build the same circuit using a JK flip-flop to keep carry and without using the clock in logic BINARY COUNTER WITH PARALLEL LOAD A parallel load register that can count Assume the following functionalities are to be provided: ? Hold value ? Parallel Load ? Count up We want to have the capability to store. Therefore, we can use JK flip-flops since they provide this functionality To choose between these three functionalities we need two control lines Let us call them Count and Load. Start with the truth table for a single flip-flop BINARY COUNTER WITH PARALLEL LOAD We have seen at the beginning of the chapter that in a counter a flip-flop changes state (toggels) if all lower order counter bits are 1’s ?−1 ? Recall that to toggle a JK flip-flop, we need ? = ? = 1 = Π?=0 ?? To load an input ?? into a JK flip-flop ? If ?? = 0 ? J=0, K=1 to Reset ? If ?? = 1 ? J=1, K=0 to Set ? Note that ? = ?? and ? = ?? ′ The truth table for a single flip-flop is: ????? ???? ? ? ?????? Design using: 0 0 0 0 Hold ? JK flip-flops ? 4x1 MUXs 0 1 ?? ?? ′ Load 1 ? 1 1 ?−1 Count (Π?=0 ?? ) BINARY COUNTER WITH PARALLEL LOAD The gate level implementation BLOCK DIAGRAMS To design sequential circuits, it is important to be able to work with block diagrams of sequential circuits components. For each block, there should be a function table that explains what it does in response to inputs. For example: IN-CLASS EXERCISE 1) Design an 8-bit counter using two 4-bit counters with Count and Load functions. 2) Using 4-bit binary counters, design a binary counter that counts from 0 to 128. 3) Design a serial to parallel convertor using a 4-bit shift register, a 4-bit parallel load register, and a binary counter of suitable size. The result of the conversion is stored in the parallel load register 4-bits at a time. That is, 4-bits will be loaded and kept until the next 4-bits are ready to be loaded. COMBINATIONAL LOGIC Osameh Al-Kofahi TYPES OF LOGIC CIRCUITS Combinational Circuits ? Output is a function of the input only Sequential Circuits ? Output is a function of the current input and previous input state ? How can we know previous input state? ? We need storage (memory) COMBINATIONAL CIRCUITS A combinational circuit is an interconnection of logic gates. ? Transforms binary information from the given input data to a required output data ? The ? inputs come from an external source ? The produced ? outputs go to a certain destination ANALYSIS AND DESIGN Analysis Starts with Ends up with Design A digital circuit Specifications: clarify the required operation of the circuit Truth table, Boolean function, and understanding the operation of the circuit (what it does) A digital circuit ANALYSIS: EXAMPLE Label outputs of gates that are functions of input variables Label outputs of gates that are functions of input variables and previously labeled outputs Repeat labelling Write outputs and intermediate values as functions of input variables Build truth tables for all outputs Try to figure out what the circuit does ANALYSIS: EXAMPLE The truth table for all the outputs is shown to the right ?1 and ?2 are the outputs of the circuit How many 1’s in the input will set ?1 to 1? How many 1’s in the input will set ?2 to 1? Can you identify the function of this circuit? The circuit represents a full adder, where ?1 is the sum and ?2 is the carry DESIGN: EXAMPLE Objective: Build a BCD code to excess-3 code convertor. We know BCD from previous chapter. Excess-3 code adds 3 to each BCD code. For example, 1 ??? becomes 4 ??????−3 . Steps: Determine number of input and output bits Derive the truth table for each output Obtain the simplified Boolean expression Draw the logic circuit diagram DESIGN: EXAMPLE Valid BCD values range from 0 to 9 ? Are there any don’t-care conditions? Valid excess-3 values range from 3 to 12 ? 4-bits needed ? Their values are obtained by adding 3 to BCD values For each output, use the techniques learned in previous chapters to obtain the simplified Boolean expressions. Draw the corresponding digital circuit DESIGN: EXAMPLE The result is digital circuit (enclosed inside the square) that converts 4-bit BCD input to 4-bit excess-3 output COMBINATIONAL CIRCUITS There is a set of Standard Components that are extensively used in the design of digital systems. In the remaining of this chapter we will study: Binary Adder-Subtractor Decimal Adder Binary Multiplier Magnitude Comparator Decoders and Encoders Multiplexers and Demultiplexers HALF ADDER Description: performs binary addition of two bits Inputs: two bits Outputs: Sum and Carry bits Create the truth table The Boolean expressions can be easily obtained from the truth table HALF ADDER The logic circuit is very simple and can be implemented using an AND gate for the carry and an XOR gate for the sum. If multiple bits are being added, a half adder does not consider carry from the previous lower significant position. FULL ADDER Description: A full adder adds two significant bits in addition to the carry bit from the previous lower significant position Inputs: Bits ? and ? are the two significant bits ? is the carry bit from previous position Outputs: Sum bit ?, and Carry bit ? ? ? ? ? Full Adder ? FULL ADDER Create the truth table for the full adder Use K-maps to obtain the simplified forms of ? and ? FULL ADDER FULL ADDER It is easy to note that ? is the odd function, i.e., ? = 1 when an odd number of ones is present in input It is also easy to note that C is 1 if: 1. Bit ? and bit ? are 1’s. OR 2. One of ? or ? is a 1, and ? is a 1 A full adder can be implemented with two half adders FULL ADDER ? ? ? ? Full Adder ? BINARY ADDER Description: Add two ?-bit binary numbers with carry Inputs: 2? + 1 bits, ? bits for each number and a carry bit Output: ?-bit sum, and a carry bit If ? = 4, how many rows will the truth table have? The total number of bits will be 9. Eight bits for the two numbers and 1 carry bit. This means that the truth table will have 29 = 512 rows Is it feasible to deal with a truth table of this size? What can we do? Use modular design to create the ?-bit adder from ? full adders 4-BIT BINARY ADDER First number ?3 ?2 ?1 ?0 Second number ?3 ?2 ?1 ?0 Result ?4 ?3 ?2 ?1 ?0 The addition is done similar to regular addition. Start from least significant bits ?0 and ?0 (and ?0 if needed) and propagate carry to higher order bits. CARRY PROPAGATION The inputs of the n-bit adder are voltage signals with values of 0 or 5 volts. Similarly, the outputs are also voltage signals with values of 0 or 5 volts. If the output is read instantly (in 0 seconds) after the input signals are supplied, will the obtained result be correct? How long should we wait? We need to wait for the carry to propagate through all full adders. CARRY PROPAGATION We need to minimize the time needed for addition ? Addition is a basic building block in many digital circuits ? It is also the basis for other arithmetic operations Faster gates can be employed ? Physical limits prevent us from obtaining arbitrarily high speeds Smarter designs ? Time vs. Complexity ? Time can be improved, but the circuit will be more complicated ? Carry Lookahead Logic is typically used CARRY LOOKAHEAD LOGIC The ? ?? carry bit ?? is equal to: ?? = ??−1 ??−1 + ??−1 (??−1 ⊕ ??−1 ) Define the following: ?? = (?? ⊕ ?? ) and ?? = ?? ?? . Then ?? can be rewritten as: ?? = ??−1 + ??−1 ??−1 this recursive formula implies that we can write all carry bits in terms of ?0 as follows: CARRY LOOKAHEAD LOGIC Since the function for each output carry is a sum of products it can be implemented using a two-level implementation as we have seen in previous chapters. BINARY SUBTRACTOR Recall that subtraction can be done by using addition with complements To calculate ? − ?: ? Find ?′ the 2’s complement of ? ? Then calculate ? + ?′ Recall also: ? The 2’s complement can be calculated by adding 1 to the 1’complement ? The 1’s complement is simply bitwise inversion An n-bit binary subtractor can be implemented with ? full adders BINARY SUBTRACTOR This circuit performs the operation: ?−? Note that inverting ? and making carry ?0 = 1 is equivalent to adding ? with the 2’s complement of ?. This circuit is very similar to the addition circuit. Can we have one circuit that does both operation? 1 OVERFLOW EXAMPLES Can you explain the output of the following C++ programs? OVERFLOW When doing computations, computers store binary numbers in memory units called registers. ? A register can store a limited number of bits Assume we have a 4-bit computer that uses 4-bit registers. Suppose we want to add 12 and 6 using this computer. We need three registers, one holding 1100 2 , another for 0110 2 , and a third to store the result. What is the result of adding these binary numbers? And how will it be stored in the third register? 12 + 6 = 18 or 1100 + 0110 = 10010 since we have 4-bit registers, the MSB bit cannot be stored ? 1100 + 0110 = 0010 !!! This is an OVERFLOW It is important to be able to detect overflows when doing addition and subtraction. OVERFLOW IN UNSIGNED NUMBERS For unsigned numbers, overflow occurs when a carry out is produced. For example, add 15 The result is 16 10 10 = 1111 = ?0000 2 with 1 10 = 0001 2 2 The carry out bit indicates that the output will not fit and needs more bits OVERFLOW IN SIGNED NUMBERS Recall that in signed numbers the range of numbers is halved because the most significant bit represents sign. When does an overflow occur in signed arithmetic? Two cases to consider: 1. Will adding numbers with different signs result in an overflow? 2. Will adding numbers with the same sign result in an overflow? How can we detect overflow in signed arithmetic? Consider sign bits of operands and the sign bit of the result ? Construct a truth table of ?4 and ?3 in inputs ?3 , ?3 , ?3 and try to figure out the condition to detect overflow BINARY ADDER SUBTRACTOR WITH OVERFLOW DETECTION DECIMAL ADDER Description: Add two decimal digits in BCD Inputs: two BCD values and in carry Outputs: BCD sum and out carry BCD values range from 0 to 9 The largest sum that can be obtained is 9 + 9 + 1 = 19 ? The 1 is from carry in DECIMAL ADDER Note that the sum is valid if it is less than 9 A correction is needed if the sum exceeds 9 or a carry out in the binary sum occurs How can we convert the invalid binary output to valid BCD output? DECIMAL ADDER A B 4 4 ???? Decimal Adder 4 S ??? BINARY MULTIPLIER Binary multiplication is done in a fashion similar to decimal multiplication. ? Multiplicand is multiplied by each digit in multiplier to produce a partial product ? Starting from the least significant bit in multiplier, for each higher order bit the partial product needs to be shifted by one position. ? Sum all partial products to get the final product What is the maximum number of bit needed to represent the product of two ?-bit numbers? ? Try 11 2 × 10 2 and 11 2 × 11 2 Possible carry BINARY MULTIPLIER If ? had 3-bits (?2 ?1 ?0 ), will Half adders be sufficient? There will be the term ?0 ?2 that needs to be added with ?1 ?1 and the carry from the first half adder. We need to use full adders Build a 3-bit by 4-bit binary multiplier to calculate: ?2 ?1 ?0 × ?3 ?2 ?1 ?0 BINARY MULTIPLIER MAGNITUDE COMPARATOR Description: Compare two 4-bit numbers ? ands ?. Decide if ? = ?, ? > ?, or ? < ? Inputs: two 4-bit numbers (a total of 8-bits) Outputs: three inputs to signal one of the possible cases Assume ? = ?3 ?2 ?1 ?0 and ? = ?3 ?2 ?1 ?0 How to tell if ? = ?, ? > ?, or ? < ?? MAGNITUDE COMPARATOR Starting from the most significant bit, check if ?? and ?? If ?? = ?? , then go to lower order bits ??−1 and ??−1 If ?? > ?? , then ? > ? If ?? < ?? , then ? < ? What is the appropriate logic gate that checks for equality? How can we check if ?? > ?? or ?? < ?? ? MAGNITUDE COMPARATOR A B 4 4 4-bit Magnitude Comparator ?? ?=? DECODER Description: Decode an n-bit input into a 2? -bit output, where only one bit is 1 and all others are 0’s, such that the index of the high bit equals the value of the n-bit input Inputs: n-bits Outputs: 2? -bits A decoder is a combinational circuit that converts binary information from ? input lines to a maximum of 22 unique output lines n-to-m decoders produce ? ≤ 2? outputs where each output represents a minterm DECODERS Example: 2-to-4 decoder What is the truth table for this decoder ?0 ? ? 2x4 Decoder ?1 ?2 ?3 ? ? ?? ?? ?? ?? 0 0 ? 0 0 0 0 1 0 ? 0 0 1 0 0 0 ? 0 1 1 0 0 0 ? DECODERS Example2: 3x8 Decoder How to design such a decoder? DECODERS What is the use of decoders? They can be very helpful in implementing Logic Functions Implement the following functions using a 3x8 Decoder DECODERS Example: Can we use decoders to implement product of sums? Use a 3x8 decoder to implement the following functions as POSs and SOPs: ?1 ?, ?, ? = Π(0,1,3) ?2 ?, ?, ? = ∑(0, 2, 4,5) DECODERS If the decoder is implemented using NAND gates it will produce maxterms. This results in a decoder with Active-Low outputs. A 4x16 decoder with Active-Low outputs DECODERS Decoders and other building blocks often have one or more Enable inputs When the decoder is enabled, it operates normally otherwise it is disabled The Enable (??) input can be ActiveHigh or Active-Low Active-High: the decoder is enabled when the ?? is HIGH Active-Low: the decoder is enabled when the ?? is LOW DECODERS Decoders with ?? can be used to create larger decoders In-class exercise: A 4x16 decoder has 4 inputs ?3 ?2 ?1 ?0 and produces 16 outputs ?0 , ?1 , … , ?15 Construct a 4x16 decoder using two 3x8 decoders with enable Construct a 4x16 decoder using five 2x4 decoders with enable. 7-SEGMENT DISPLAY DECODER In class exercise: 1. Design a 4x10 decoder using 3x8 and 1x2 decoders 2. Use the 4x10 decoder to build a 7segment display decoder A 7-segment display decoder: ? Used to drive the 7-segment display ? Produces the suitable outputs to display digits from 0 to 9 on a 7-segment display ENCODERS Description: Inverse of a decoder. Takes 2? inputs numbered from 0 to 2?−1 , only one is HIGH and the rest are LOW, and produces ? outputs corresponding to the value of the high input number. Inputs: 2? -bits numbered from 0 to 2?−1 . Only one is HIGH. Outputs: ?-bits representing the value of the high input number In general, the inputs could be less than 2? ENCODERS Example: 4x2 encoder What is the truth table? ?0 ?1 ?2 ?3 4x2 Encoder ? ? ?? ?? ?? ?? ? ? 0 0 0 ? 0 0 0 0 ? 0 0 1 0 ? 0 0 1 0 ? 0 0 0 1 1 ENCODERS Two problems with encoders: 1. How to distinguish between the case when all inputs are 0’s and the case when no inputs are present? 2. What if the user asserted two or more inputs at the same time? Solutions: 1. Valid output indicator (?) 2. Priority encoders: produce the code for the largest asserted input ENCODERS 4x2 priority encoder What is the output if: ?2 = 1 and ?1 = 1 Note that ? is the most significant bit, and ? is the least significant. EXAMPLE In-class exercise: Use what you have learned so far to build a logic circuit to display the value of the pressed key on the numerical pad on the 7-segment display. Assume the keypad does not provide any kind of logic. It is just a group of buttons labeled from 0 to 9. MULTIPLEXERS Description: A multiplexer has multiple inputs and only one output. It directs one of the inputs to the single output based on a selection made using input selection lines. Inputs: 2? inputs, ? selection lines Outputs: only one output Often labeled MUX Think of a MUX as a data selector MULTIPLEXERS Example: 4x1 MUX What is the truth table for a MUX? ?0 ?1 ?2 4x1 MUX ?3 ?1 ?0 ?????? ?? ?? ? 0 0 ?0 0 1 ?1 1 0 ?2 1 1 ?3 MULTIPLEXERS Implementation of a 4x1 MUX A MUX may have an Enable input ? Not shown in the diagram A MUX can be also implemented using decoders Design an 8x1 MUX using a 3x8 decoder MULTIPLEXERS Multiplexers can be combined to provide multi-bit selection logic. ? Instead of selecting from 1-bit inputs, we can select from n-bit inputs Example 1: Build a Quadruple 2-to-1 MUX using 4 2-to-1 MUXs Inputs: two inputs (? and ?) each is 4-bits wide Output: 4-bit output (either ? or ?) Multiplexers can be combined to build larger MUXs. Example 2: Build a 4-to-1 MUX using three 2-to-1 MUXs MULTIPLEXERS Gate-level implementation of a Quadruple 2-to-1 MUX MULTIPLEXERS Multiplexers can be also used to implement Boolean Functions An n-bit Boolean function can be implemented using a MUX with n-1 selection lines How? 1. Use the n-1 most significant bits as selection lines 2. Express the function in terms of the remaining least significant input. Note that each of the 2?−1 combinations will be repeated twice. One with the LSB = 0 and the other with the LSB = 1 Four possible cases: ? = ?, ? = ?′, ? = 0, or ? = 1 MULTIPLEXERS Implement the following function using a multiplexer From the truth table, see how ? is expressed in terms of ? Do the same for the following: ? ?, ?, ? = ∑(1,2,6,7) DEMULTIPLEXERS Description: Demultiplexers do the opposite job of multiplexers. Directs a single input to one of the outputs based on the selection made using a set of selection lines. Inputs: a single input signal and ? selection lines Outputs: 2? output lines Abbreviated as a DMUX DEMULTIPLEXERS The truth table of a DMUX looks very similar to that of a decoder A decoder with Enable can be thought of a DMUX where the Enable value is the input and the decoder inputs are the selection lines ? 4x1 DMUX ?1 ?0 ?0 ?? ?? ?? ?? ?? ?? ?1 0 0 ? 0 0 0 ?2 0 1 0 ? 0 0 ?3 1 0 0 0 ? 0 1 1 0 0 0 ? SYNCHRONOUS SEQUENTIAL LOGIC Osameh Al-Kofahi INTRODUCTION Combinational Logic: Output depends only on input Sequential Logic: Output depends on input and previous state ? To know previous state we need to store it ? In this chapter we will study basic memory elements Feedback path SEQUENTIAL CIRCUITS A sequential circuit usually has a combinational circuit that does a certain task The combinational logic will be affected by the external inputs and the current state External inputs will also determine the conditions to change the memory state Feedback path SEQUENTIAL CIRCUITS Synchronous There are two types of Sequential Circuits: Synchronous Sequential Circuits: behavior can be defined from the knowledge of its signals at discrete instants of time. ? Clocked-Circuit: the discrete time instants are defined by a clock ? The clock orchestrates the operation of the circuit ? Easier to analyze and design Asynchronous Sequential Circuits: behavior depends upon the input signals at any instant of time and the order in which the inputs change ? Hard to analyze and design Asynchronous SYNCHRONOUS SEQUENTIAL CIRCUITS Synchronization depends on a clock generator ? Denoted by ????? or ??? ? Clock signal is distributed to all components Clock pulses will determine when the computations will take place based on the external inputs ? State and calculations are affected by either the rising edge or the falling edge of the clock ? The clock period must be enough to allow the outputs of circuit components to stabilize The storage or memory elements used in synchronous circuits are called Flip-Flops ? A flip-flop is capable of storing only one bit ? The output of a flip-flop is either a 1 or a 0 ? The output of a flip-flop will be determined by its inputs and the current bit its storing STORAGE ELEMENTS: LATCHES VS. FLIP-FLOPS A storage element can maintain a binary state ? The stored state is controlled by circuit inputs ? State is maintained as long as power is supplied Latches vs. Flip-flops Latch: a storage element that changes state based on input signal levels (level-sensitive) Flip-Flop: a storage element that changes state based on a clock transition (edge-sensitive) Latches are used to build Flip-Flops SR LATCH WITH NOR GATES The SR latch can be in one of two states: When ? = 1, ? = 0 the latch is Set (stores a 1) When ? = 0, ? = 1 the latch is Reset (stores a 0) The latch preserves state when S and R are zeros When ? = 0, ? = 0 the output depends on the previous state S and R cannot be both ones because this may result in unpredictable output. How? SR Latch using NOR gates SR LATCH WITH NAND GATES The SR latch can be in one of two states: When ? = 0, ? = 1 the latch is Set (stores a 1) When ? = 1, ? = 0 the latch is Reset (stores a 0) The latch preserves state when S and R are zeros When ? = 1, ? =1 the output depends on the previous state S and R cannot be both zeros Also known as ? ′ ?′ Latch SR Latch using NAND gates SR LATCH WITH ENABLE Note that the NAND acts as an inverter when EN=1 ? (? . 1)′ = ?′ The operation will be similar to the SR latch using NOR gates State will not change if the latch is disabled (EN=0) or S=R=0 The state EN=S=R=1 is not allowed because it will result in unpredictable output Can we avoid this unwanted state? D LATCH Instead of using two inputs, use one input as shown in the figure This eliminates the undesired state When EN=1, the value of D shows at the output ? ? Transparent Latch When EN goes to 0, the value of D is retained LATCHES: BLOCK DIAGRAMS THE PROBLEM WITH LATCHES A sequential circuit has memory elements and a combinational circuit that provides a certain functionality ? Input of memory element = output of combinational circuit = ? ? Input of combinational circuit = ?(external inputs, ?) Latches are level sensitive, i.e., as long as the memory elements are enabled: If Inputs change ? ? may change ? ? may change ? ? may change again ? ? may change again ? ? may change … and so on. ? ? Feedback path ? THE PROBLEM WITH LATCHES To solve the problem we need to make the latches change state only at specific time instants. In practice, these time instants are defined by the transitions of a clock signal That is, instead of being level-sensitive, we want to have latches that are edge-sensitive Edge sensitive latches are called Flip-Flops Synchronous EDGE-TRIGGERED D FLIP-FLOP When ??? = 0: A D Flip-Flop that changes state on The negative edge of the clock ?1 = 0? ? does not change ?2 = 1? ? can change, but it won’t. Why? Because ? = ? When ??? = 1: ?1 = 1? ? changes with ? ?2 = 0? ? stays the same regardless of ? On the falling edge: ? = ? and it stays the same until the next falling edge ?1 ?2 EDGE-TRIGGERED D FLIP-FLOP Another implementation uses three SR latches ? = ? when ??? = 0 If ??? = 0: ? = ? = 1? No change in ? or ?′ Since ? = 1? ? = 1. ? ? ? = 1. ? ′ ′ ′ = ?′ =? ? = ?′ when ??? = 0 EDGE-TRIGGERED D FLIP-FLOP At the rising edge of the clock, when ??? becomes 1 ? = 1. ? ′ ? = 1. ?. ? = (1. ?)′ = ?′ ′ ? = ? when ??? = 0 = (1. ? ′ . ?′)′ = ? ? = ?. ? ′ = ?. ? ′ ? = ?. ? ′ = ? ′ . ? ′ = ?′ (no change) ′ = ? (no change) 1) If ? = ??? = 0??′ = ?. ? ′ = (0. ?)′ = 1 ?? = 1?? = ?. ? ′ ′ = 1.1 ′ = 0 2) If ? =1?? = 0?? = ?. ?′ ′ = (0. ?)′ = 1 ?? =1??′ = ?. ? ′ = 1.1 ′ = 0 That is: ? = ? and ?′ = ?′ ? = ?′ when ??? = 0 EDGE-TRIGGERED D FLIP-FLOP What happens if ? changes while ??? = 1? ? = ? when ??? = 1 That is ? changed to ?′ ? = ?. ? ′ = ?′. ? ? = ?. ? ′ = 1. ? ′ ? = ???. ? ′ ? = ???. ?. ? ′ ′ = 1. ? ′ ′ = 0 =1 ? = ?′ on rising edge = ? (no change) ′ = ?′ (no change) = 1.1. ? ′ ′ = ? (no change) Since ? and ? stayed the same ? and ?′ will stay the same also ? = ? on rising edge ? = ?′ when ??? = 1 D FLIP-FLOPS ??? ? 0 OR 1 X ↑ ↑ Next State Next State ??? ? No change 0 OR 1 X No change 0 ? = 0, ? ′ = 1 ↓ 0 ? = 0, ? ′ = 1 1 ? = 1, ? ′ = 0 ↓ 1 ? = 1, ? ′ = 0 JK FLIP-FLOPS D Flip-Flops can either set or reset on the rising clock edge. JK Flip-Flops can set, reset, complement, store on the rising clock edge Characteristic Table JK FLIP-FLOP: EXAMPLE T FLIP-FLOPS Toggle Flip-Flop A T flip-flop provides two functionalities ? Preserve ? Complement Can be obtained from JK or D flip-flops Characteristic Table CHARACTERISTIC TABLES Characteristic tables define the next state in terms of the current state and the input ?(?) is the current state ? Before clock edge ?(? + 1) is the next state ? After the clock edge CHARACTERISTIC EQUATIONS Provide the same information in the characteristic tables D flip-flop: ? ?+? =? JK flip-flop: ? ? + ? = ??′ + ?′ ? T flip-flop: ? ? + ? = ??′ + ?′ ? How can we derive the characteristic equations from the characteristic tables? DIRECT INPUTS When power is first turned on, what is the state of a flip-flop? Direct inputs are used to initialize the flip-flop to a set or reset state 0 1 1 ASYNCHRONOUS INPUTS PREset (PRE): Sets the flip-flop CLearR (CLR): Resets the flip-flop In this example, both are active-low ANALYSIS OF SEQUENTIAL CIRCUITS Analysis describes what a given circuit will do under certain operating conditions To understand the operation of a sequential circuit we need to understand the relationship between its states. A state diagram provides an abstract view of these relationships. To obtain a state diagram the analysis proceeds as follows: State Equations: algebraic expression describing next state in terms of current state and input ? Also called transition equations State Tables: the same information of a state equation in tabular form State Diagrams: the same information shown by a diagram ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE A sequential circuit with two D flip-flops ? Let’s call them ? and ? D flip-flops are transparent: their input shows on the output on clock edge. Therefore, the state equations are: ? ? + 1 = ? ? ? ? + ? ? ?(?) ? ? + 1 = ?′ ? ?(?) Can be also written as: ? ? + 1 = ?? + ?? ? ?? = ?? + ?? ? ? + 1 = ?′ ? ? ?? = ?′ ? The present-state value of output ? will be: ? = ? + ? ?′ ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE State equations can be expressed in state tables For a sequential circuit with ? flip-flops and ? inputs the table needs to have 2?+? rows The table will have ? columns for the flip-flops The table will also have a column for each output Build the state table using the following state equations: ? ? + 1 = ?? + ?? ? ? + 1 = ?′ ? ? = ? + ? ?′ ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE The state table can be written in a different way: The input conditions are enumerated under the nextstate and output sections. For each present state, there are two possible next states and outputs, depending on the value of the input ANALYSIS OF SEQUENTIAL CIRCUITS: EXAMPLE A sequential circuit with ? flip-flops, has ?? different states. The relationship between these states and how the circuit changes state can be expressed in a state diagram. The numbers inside circles are the states The labels on arrows are ?????/?????? Note that the bit value of the output occurs during the present state and with the indicated input ? It has nothing to do with the transition to the next state. What does the circuit do? ANALYSIS OF SEQUENTIAL CIRCUITS Derive the state equation, state table, and state diagram for the following sequential circuit: What is the functionality provided by this circuit? ANALYSIS OF SEQUENTIAL CIRCUITS Analysis for sequential circuits using other flip-flop types: ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Analyze the sequential circuit shown to the right: Steps: ? ? ? ? Determine input equations Use input equations to determine state equations From state equations create state table From state table create state diagram Note: the only outputs in the circuit are the outputs of flip-flops themselves. ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Input equations: State equations: State Table ANALYSIS OF SEQUENTIAL CIRCUITS: JK FLIP-FLOPS Note that: ? Edges only have one number (the input) ? The output is a function of current state only Such a state diagram represents a Moore Finite State Machine ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Analyze the sequential circuit shown to the right Same steps: ? ? ? ? Determine input equations Use input equations to determine state equations From state equations create state table From state table create state diagram Note that the output is dependent on only the current state ? this is also a Moore machine ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Input equations: State equations: Output equation: State Table ANALYSIS OF SEQUENTIAL CIRCUITS: T FLIP-FLOPS Note that since the output only depends on the current state, it should be indicated inside each state This sequential circuit counts from 00 to 11 (and repeats again from 00) as long as the input is 1 ? It preserves the count when the input is 0 ? It produces 1 when a full count to 11 is made MOORE VS. MEALY STATE MACHINES Mealy: - Output is a function of input and current state - Outputs may change if input changes during clock cycle Moore: - Output is a function of current state - Output is synchronized with clock edges. Why? STATE REDUCTION State reduction: The reduction in the number of flip-flops in a sequential circuit State-reduction algorithms aim to reduce the number of states, while keeping the external input–output requirements unchanged. A reduction in the number of states may (or may not) result in a reduction in the number of flip-flops. Reducing the number of flip-flops may sometimes result in needing more combinational gates for inputs and/or outputs. STATE REDUCTION State reduction works by identifying equivalent states then removing the duplicates State equivalency: two states are equivalent if, for each member of the set of inputs, they give exactly the same output and send the circuit either to the same state or to an equivalent state Consider the state table for the zero-detection example and try to find equivalent states. THE DESIGN PROCEDURE The design of a sequential circuit starts from a set of specifications and produces a logic diagram. The procedure usually goes through the following steps: THE DESIGN PROCEDURE: AN EXAMPLE Objective: Design a sequence detector that detects three consecutive 1’s in a stream of input bits. Identify states and the transition rules between them What are the states? ?0 : no 1’s received, ?1 : one 1 is received, ?2 : two 1’s are received, and ?3 : three 1’s are received How many flip-flops are needed? How do we go from a state to another? And how is the output related to states and input? Mealy vs. Moore THE DESIGN PROCEDURE: AN EXAMPLE The circuit can be modeled using a Moore FSM ? Mealy is also possible The state table can be built from the state diagram Next step? Assuming D flip-flops are used, what are the input equations? THE DESIGN PROCEDURE: AN EXAMPLE For D flip-flops the input equations are the same as the next state equations Input equations are: Now we can draw the circuit THE DESIGN PROCEDURE: AN EXAMPLE The circuit using D flip-flops DESIGN USING OTHER FLIP-FLOPS Can we use other types of flip-flops to design sequential circuits? How will the procedure change if JK flip-flops are used? In D flip-flops, the input equations can be obtained directly from the state equations because ?? = ?(? + 1) In JK flip-flops, we need excitation tables Excitation tables show the needed inputs for a given change of state EXCITATION TABLES JK flip-flop Characteristic Table ? ? ? ?(? + ?) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 JK flip-flop Excitation Table + DESIGN USING JK FLIP-FLOPS Assume we have the following state table How should we continue? We should use the excitation table for JK flipflops to figure out the inputs causing the shown changes in state. JK flip-flop Excitation Table + DESIGN USING JK FLIP-FLOPS DESIGN USING JK FLIP-FLOPS DESIGN USING JK FLIP-FLOPS DESIGN USING T FLIP-FLOPS The process is the same, but we need to use the excitation tables for T flip-flops to figure out the input equations. Example: Design a binary counter that counts from 0 to 7 An ?-bit binary counter counts up with every clock edge, and when it reaches 2? − 1 it will go back to 0 The state diagram is shown to the right ? In this example, the only input is the clock. That is why the transitions are not labeled DESIGN USING T FLIP-FLOPS From the state diagram, construct the state table for the binary counter and use the excitation table for the T flip-flop to show the needed input values T flip-flop Characteristic Table T flip-flop Excitation Table ? ? ?(? + ?) 0 0 0 0 1 1 1 0 1 1 1 0 + DESIGN USING T FLIP-FLOPS DESIGN USING T FLIP-FLOPS Blackboard CA Remaining Time: 1 hour, 29 minutes, 27 seconds. Question Completion Status: QUESTION 1 Design a circuit that accepts a 4-bit input. The circuit should output a one if the input represents a valid BCD number, and a zero otherwise. A. List the truth table of the system. (2 points) B. Find the simplified expression using k-map. Use the minimum number of gates. (1 points) C. Specify the chip number and the quantity of chips required to implement the unsimplified and the simplified expressions. (3 points) For example: Chip: 7400 Quantity: 4 Chip: 7402 Quantity: 3 D. Draw the simplified circuit. (1 points) A For the toolbar, press ALT+F10 (PC) or ALT+FN+F10 (Mac). B I U S Paragraph Arial 14px .. A < Ix 6 je and Submit to save and submit. Click Save All Answers to save all answers. MacBook Air 0 Parang Blackboard ? Ä Remaining Time: 1 hour, 29 minutes, 20 seconds. Question completion Status: QUESTION 2 A given circuit accepts a 4-bit input which represents a month (e.g., input 0001 represents January). The circuit should output a one if a given month has only 30 days in it. Design the circuit using the 74999 (2-to-4 decoder) chip shown below and any necessary extra gates. A. List the truth table of the circuit. (2 points) B. Draw the system using the 74999 (2-to-4 decoder) chip and extra logic gates. You are only allowed to use the 74999 chips and 2-input gates. Show all the connections to the 74999 chips. (2 points) C. What is the minimum number of 74999 chips needed to implement the circuit? (1 point) A1 1 10 Voc Y3' ?? N 9 YO II E1 3 NOOO 8 Y1' Inputs Enable Address Outputs E3 E1 A1 ?? YO' Y1 Y2' ? H X ? H H H L X X ? H H H H L L L H H ? L L H H L H H L H L H H L H L ? H H H H H = High Voltage Level, L = Low Voltage Level, X = Don't care H H E3 4 7 Y2 GND 5 H L 6 Y3' e and Submit to save and submit. Click Save All Answers to save all answers. MacBook Air 888 3 10 (0 ON 8 R u D F G I Is 2 X ? V B N 33 cemenang Remaining Time hour. 29 minutes, 1 seconds Question completion Status QUESTION 3 Design a moore FSM of a sequence recognizer that: Detects the sequences 10 and/or 001. Allows Overlapping. Uses binary encoding. Uses the 7476 JK Flip-Flop IC. Important: Use proper names for your states. For example, got1. A. Show all the steps of the state design approach. Draw the state diagram. (3 points) > Write the state table. (2 points) → Show the state encoding. (1 point) ? List the truth table entries. (3 points) > Use k-maps to derive the simplified functions. Use the minimum number points) B. How many 7476 chips are needed to implement the circuit? (1 point) 01 K2 02 K1 01 GND 02 12 16 15 14 13 12 10 9 Save and Submit to save and submit. Click Save All Answers to save all answers. MacBook Air & 2 99ng x2 A Remaining Time: 1 hour, 29 minutes, 07 seconds Question completion Status: Write the state table. (2 points) Show the state encoding, (1 point) >> List the truth table entries. (3 points) Use k-maps to derive the simplified functions. Use the minimum number points) B. How many 7476 chips are needed to implement the circuit? (1 point) GND K2 02 J2 KI 0 01 02 16 15 12 11 10 9 2 3 5 6 8 CLK 1 PR 1 CLR 1 J1 Vec CLK 2 CLR 2. For the toolbar, press ALT+F10 (PC) or ALT+FN+F10 (Mac). Save and Submit to save and submit. Click Save All Answers to save all answers, MacBook Air 2 FOR Arane