# ENGG 1015 Tutorial - University of Hong Kong

ENGG 1203 Tutorial Combinational Logic (II) and Sequential Logic (I) 8 Feb Learning Objectives News Apply Karnaugh map for logic simplification Design a finite state machine HW1 (Feb 22, 2013, 11:55pm) Ack.: HKU ELEC1008, ISU CprE 281x, PSU CMPEN270, Wikipedia 1 Simplification using K-map

Simplify the Boolean expression of the circuit Change each NAND gate in the circuit to a NOR gate, and simplify the Boolean expression of the circuit M N Q x 2 Solution (a) M 0 0 0 0 1 1 1 1 N 0 0 1 1 0

0 1 1 Q 0 1 0 1 0 1 0 1 x 0 0 0 1 0 1 0 1 From truth table to K-map NQ M

00 01 11 10 0 0 0 1 0 1 0 1 1 0 x MQ NQ M

N Q A B x C 3 Solution (b) M 0 0 0 0 1 1 1 1 N 0 0 1 1 0 0

1 1 Q 0 1 0 1 0 1 0 1 x 0 1 0 1 0 1 1 1 NQ M 00 01

11 10 0 0 1 1 0 1 0 1 1 1 x MN Q M N Q A

B x C 4 Finite State Machine (FSM) State transition diagram Truth table K-Map Circuit State Present state: before the register Next state: after the register State transition: during clock 2n states: n FFs 5 A simple Finite State Machine (FSM)

Turnstile Control access Depositing a token in a slot on the turnstile unlocks the arms, allowing a single customer to push through. After the customer passes through, the arms are locked again until another coin is inserted. Current State Locked Unlocked Input coin push coin push Next State Unlocked Locked Unlocked Locked Output

Release turnstile so customer can push through None None When customer has pushed through, lock turnstile 6 A simple FSM Current State Locked Unlocked Input Next State Output coin Release turnstile so customer can push through Unlocked push Locked None coin None

Unlocked push Locked When customer has pushed through, lock turnstile Specification FSM Arm: 0 State Arm: 1 Transition Transition condition 7 Steps in designing a state machine Draw a state transition diagram An initial state

Other states to keep track of various activities Transitions Generate a state transition table and a output table Write state transition table and output table in binary State assignment, i.e., the code used for each state Derive canonical sum-of-product expressions Draw the circuit 8 From state transition diagram to truth table Four states Two-bit state q: Present state q*: Next state z: Output

Condition/Output 9 From truth table to K-map A B DA DB DA DB 10 From K-map to circuit State register Logic for output Logic for state transition 11 A simple FSM design Design a state machine that will repeatedly display in binary values 1 (001), 3 (011), 5 (101), and 7 (111)

How many states we need? S0, S1, S2, S3 Simplified state transition diagram? 12 Solution Current Output Current state Output X Y L2 L1 L0 S0 (00)

0 0 0 0 1 1 0 1 1 0 1 0 1 1 1

1 1 1 (001) Output table S1 (01) 3 (011) 0 5 (101) L2 = XY'+XY = X S2 (10) 1 7 (111) 1 L1 = X'Y+XY = Y S3 (11) L0 = X'Y'+X'Y+XY'+XY = 1 State transition table Current state Next state X = X'Y+XY' S0 (00) S1 (01) Y = X'Y+XY' = Y' Current Next

X Y X Y 0 0 0 1 S1 (01) S2 (10) 0 1 1 0 S2 (10)

S3 (11) 1 0 1 1 S3 (11) S0 (00) 1 1 0 0 13 A complicated FSM design Vending Machine

Collect money, deliver product and change Vending machine may get three inputs Inputs are nickel (5c), dime (10c), and quarter (25c) Only one coin input at a time Product cost is 40c Does not accept more than 50c Returns 5c or 10c back Exact change appreciated 14 Solution We are designing a Mealy state machine (i.e., output depends on both current state and inputs). Suppose we ask the machine to directly return the coin if

it cannot accept an input coin. Input specification: I1 I2 Represent the coin inserted 00 - no coin (0 cent), 01 nickel (5 cents), 10 dime (10 cents), 11 quarter (25 cents) Output specification: C1C2P C1C2 represent the coin returned 00, 01, 10, 11 P indicates whether to deliver product 0, 1 15 Solution States: S1S2S3 Represent the money inside the machine now 3 bits are enough to encode the states

S00 (0 cents) 000 S05 (5 cents) 001 S10 010 S15 011 S20 100 S25 101 S30 110 S35 111 16 Solution 17 Solution 11/110 11/000 01/000 10/000

Next state Input Output S35 11/110 S35 10/011 S00 01/001 S00 00/000 S35 S35: Currently the machine has 35 cents e.g. 11/110 : If we insert a quarter (11), then the machine should return one quarter and zero product (110) 35c (35 cents inside the machine now) + 25c (insert 25 cents) = 35c (35 cents inside the machine in the next state) + 25c (return 25 cents) + 0c (return no product) 18 Solution S35

11/110 S35 10/011 S00 01/001 S00 00/000 S35 e.g. 10/011: If we insert a dime (10), then the machine should return one nickel and one product (011) 11/110 11/000 01/000 10/000 35c (35 cents inside the machine now) + 10c (insert 10 cents) = 0c (zero cent inside the machine in the next state) + 5c (return 5 cents) + 40c (return one product) e.g. 01/001: If we insert a nickel (01), then the machine should return zero coin and one product (001) 35c (35 cents inside the machine now) + 5c (insert 5 cents) = 0c (zero cent inside the machine in the next state) + 0c (return zero cent) + 40c (return one product) 19

(Appendix) Simplification using K-map Simplify the following Boolean expressions using Karnaugh map. i) A B A B ii) B BC ABC AB 20 Solution i) A/B 0 1 0 0

0 1 1 1 ii) A/BC A B A B A 00 01 11 10 0 0 0 1 1

1 1 1 1 1 B BC ABC AB B A 21 (Appendix) Counter Figure a) shows a complete four-bit parallel adder with registers and b) shows the signals used to add binary numbers from memory and store their sum in the accumulator. Suppose the numbers being added are 1001 and 0101. Also assume that Co=0. Describe what happen at t1, t2, t3, t4 and t5. 22

Solution 23 At time t1, is active low FF at the bottom will be cleared 24 At time t2, load is active high Set A numbers will be loaded into the upper register At time t3, transfer is active high Adder process between A3A2A1A0 = 0000 and B3B2B1B0 = 1001 The sum S3S2S1S0 = 1001 are transferred to register A on PGT due to this transfer pulse at t 3 25

At time t4, the load is active high, the set B numbers will be loaded into register B on PGT of LOAD pulse B3B2B1B0 = 0101 At time t5, A3A2A1A0 = 1001 and B3B2B1B0 = 0101, the adder produces S3S2S1S0 = 1110. This sum is transferred into register A when TRANSFER pulse occur at t5. 26 (Appendix) State changing in FSM Design a 2-bit counter with input x that can be A down counter when x = 0 (1110010011) A Johnson counter when x = 1 ( 0001111000) 27 Solution 28

(Appendix) A typical FSM FSM Truth table Circuit State register Logic for state transition Logic for output 29

## Recently Viewed Presentations

• A football field, including both end zones, is approximately 1.33 acres in size. That means a forested area, equivalent to 2 football fields, is cut down. Every second. Population Growth. The world's population increases by more than 200,000 people per...
• Citizenship in the World. Every Rotarian wears a pin that says "Rotary International." There are few places on the globe that do not have a Rotary club, 34,216 clubs in 350 nations and geographical regions. Please raise your hand if...
• OBESITY AND SMOKING IN PATIENTS WITH BARRETT'S OESOPHAGUS OR OESOPHAGEAL ADENOCARCINOMA - PRELIMINARY RESLUTS FROM ... McManus Dr Anna Gavin DUBLIN Prof Dermot Kelleher Dr Ross McManus Dr Lisa Higgins CORK Prof Gerry O'Sullivan LEEDS Prof Chris Wild Dr Laura...
• Bianca L. Tristan, PhD Student. Walden University. PUBH 8165-Environmental Health. Instructor: Dr. Howard Rubin. Summer, 2010. Public Health Department Staff Presentation Epidemiology of Viral Gastroenteritis in Adults
• 1 安全保障貿易管理（制度の紹介） 平成17年5月 経済産業省貿易管理部 1．我が国の安全保障貿易管理制度 （1）リスト規制とは、 役務取引と輸出の発生時点と許可対象地域の違い 2．制度に関連した情報の入手 1．我が国の安全保障貿易管理制度 （1）リスト規制とは、 役務取引と輸出の発生 ...
• Juxtaposition - Making one idea more dramatic by placing it next to an opposite. In art it is called chiaroscuro, where a bright white object is placed next to a black object and thus both are made or visible.
• * Spatial resolution Our ability to resolve small details (spatial resolution) is maximal at fovea and declines as we move away from fixation Most everyday life tasks benefit from heightened resolution Antis, 1974 Landolt squares Broken lines Vernier Performance Eccentricity...
• American Realism and Naturalism. An Era of New Beginnings. ... lost his wife and 2 sons. Mostly wrote short stories about the South and the Civil War. The Devil's Dictionary - definitions of words that reveal his pessimism ...