### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Digital System Design ECE 331

Mason

GPA 3.94

### View Full Document

## 10

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 86 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 331 at George Mason University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/215033/ece-331-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

## Reviews for Digital System Design

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15

ECE 331 Modeling Finite State Machines in VHDL ECE 3317 Digital System Desth George Mason Umversxty Structure of a Typical Digital System Data Inputs Control Inputs Control Execution S39gnals Control Unit I Unit Datapath Control Data Outputs Control Outputs ECE 331 Digital System Design Execution Unit Datapath Provides All Necessary Resources and Interconnects Among Them to Perform Specified Task Examples of Resources Adders Multipliers Registers Memories etc ECE 331 Digital System Design Control Unit Control Controls Data Movements in an Operational Circuit by Switching Multiplexers and Enabling or Disabling Resources Follows Some Program or Schedule Often Implemented as Finite State Machine or collection of Finite State Machines ECE 331 Digital System Design Finite State Machines FSMs Any Circuit with Memory Is a Finite State Machine Even computers can be viewed as huge FSMs Design of FSMs Involves Defining states Defining transitions between states Optimization minimization Above Approach ls Practical for Small FSMs Only ECE 331 Digital System Design Moore FSM Output Is a Function of a Present State Only Next State Present State clock Present State reset Register Output Outputs function 39 ECE 331 Digital System Design Mealy FSM Output Is a Function of a Present State and Inputs nputs Next State Present State Present State Register Output Outputs function 39 ECE 331 Digital System Design Moore Machine transition condition 1 transition condition 2 ECE 331 Digital System Design Mealy Machine transition condition 1 I output 1 transition condition 2 output 2 ECE 331 Digital System Design Moore vs Mealy FSM 1 Moore and Mealy FSMs Can Be Functionally Equivalent Equivalent Mealy FSM can be derived from Moore FSM and vice versa Mealy FSM Has Richer Description and Usually Requires Smaller Number of States Smaller circuit area ECE 331 Digital System Design 10 Moore vs Mealy FSM 2 Mealy FSM Computes Outputs as soon as Inputs Change Mealy FSM responds one clock cycle sooner than equivalent Moore FSM Moore FSM Has No Combinational Path Between Inputs and Outputs Moore FSM is more likely to have a shorter critical path ECE 331 Digital System Design 11 Moore FSM Example 1 Moore FSM that Recognizes Sequence 10 reset 0 80 No S1 1 82 10 Meaning elements observed observed of states of the sequence observed ECE 331 Digital System Design Mealy FSM Example 1 Mealy FSM that Recognizes Sequence 10 00 10 10 A reset 0 1 80 No 81 1 Meaning elements observed of states of the sequence observed ECE 331 Digital System Design 13 Moore amp Mealy FSMS Example 1 clock 14 ECE 331 Digital System Design FSMs in VHDL Finite State Machines Can Be Easily Described With Processes Synthesis Tools Understand FSM Description If Certain Rules Are Followed State transitions should be described in a process sensitive to clock and asynchronous reset signals only Outputs described as concurrent statements outside the process ECE 331 Digital System Design 15 Moore FSM processcock reset Present State Register clock reset concurrent Present State E Outputs statements function Output I I ECE 331 Digital System Design Mealy FSM processcock reset clock Present State reset Register Output E function i concurrent statements Present State Outputs ECE 331 Digital System Design Moore FSM Example 1 Moore FSM that Recognizes Sequence 10 ECE 331 Digital System Design Moore FSM in VHDL 1 TYPE state IS SO S1 SZ SIGNAL Moorestate state UMoore PROCESS clock reset BEGIN Freset 1 THEN Moorestate lt SO ELSIF clock 1 AND clock event THEN CASE Moorestate IS WHEN SO gt IF input 1 THEN Moorestate lt S1 ELSE Moorestate lt SO END IF ECE 331 Digital System Design 19 Moore FSM in VHDL 2 WHEN S1 gt IF input 0 THEN Moorestate lt SZ ELSE Moorestate lt S1 END IF WHEN SZ gt IF input 0 THEN Moorestate lt SO ELSE Moorestate lt S1 END IF END CASE END IF END PROCESS Output lt 1 WHEN Moorestate 2 ELSE 0 ECE 331 Digital System Design 20 Mealy FSM Example 1 Mealy FSM that Recognizes Sequence 10 reset ECE 331 Digital System Design 21 Mealy FSM in VHDL 1 TYPE state IS SO S1 SIGNAL Mealystate state UMealy PROCESScock reset BEGIN Freset 1 THEN Mealystate lt SO ELSIF clock 1 AND clock event THEN CASE Mealystate IS WHEN SO gt IF input 1 THEN Mealystate lt S1 ELSE Mealystate lt SO END IF ECE 331 Digital System Design 22 Mealy FSM in VHDL 2 WHEN S1 gt F input 0 THEN Mealystate lt SO ELSE Mealystate lt S1 END IF END CASE END IF END PROCESS Output lt 1 WHEN Mealystate 31 AND input 0 ELSE 0 ECE 331 Digital System Design 23 Moore FSM Example 2 State diagram ECE 331 Digital System Design 24 Moore FSM Example 2 State table Present NeXt State Output state w 0 w 2 1 z A A B 0 B A C 0 C A C 1 ECE 331 Digital System Design Moore FSM processcock reset concurrent statements Output I function I Present State y I I Output 2 r ECE 331 Digital System Design 26 Moore FSM Example 2 VHDL code 1 USE ieeestdlogic1164al ENTITY simple IS PORT clock IN STDLOGIC resetn IN STDLOGIC w IN STDLOGIC z OUT STDLOGIC END simple ARCHITECTURE Behavior OF simple IS TYPE Statetype IS A B C SIGNAL y Statetype BEGIN PROCESS resetn clock BEGIN IF resetn 39039 THEN y lt A ELSIF CIock39EVENT AND Clock 39139 THEN ECE 331 Digital System Design 27 Moore FSM Example 2 VHDL code 2 CASE y IS WHEN A gt IFw 39039 THEN I ltA ELSE y lt B END IF WHEN B gt IFw 39039 THEN I ltA ELSE y lt 0 END IF WHEN 0 gt IFw 39039 THEN I ltA ELSE y lt 0 END IF END CASF ECE 331 Digital System Design 28 Moore FSM Example 2 VHDL code 3 END IF END PROCESS 2 lt 39139 WHEN y C ELSE 39039 END Behavior ECE 331 Digital System Design 29 Moore FSM process I l W Input w I 39 ypresent I gt i 7 7 I I Next State dynext process I39 39 39 39 I clock clock 39 Present State Present State resetn resetn Register ypresent 39 39 39 39 39 39 39 39 39 39 l concurrent Output 5 Outputz statements I function i V I ECE 331 Digital System Design 30 Alternative VHDL code 1 ARCHITECTURE Behavior OF simple IS TYPE Statetype IS A B C SIGNAL ypresent ynext Statetype BEGIN PROCESS w ypresent BEGIN CASE ypresent IS WHEN A gt IF w 39039 THEN ynext lt A ELSE ynext lt B END IF WHEN B gt IF w 39039 THEN ynext lt A ELSE ynext lt C END IF ECE 331 Digital System Design 31 Alternative VHDL code 2 WHEN 0 gt F w 39039 THEN ynext lt A ELSE ynext lt C END IF END CASE END PROCESS PROCESS clock resetn BEGIN F resetn 39039 THEN ypresent lt A ELSIF clock39EVENT AND clock 39139 THEN ypresent lt ynext END IF END PROCESS 2 lt 39139 WHEN ypresent C ELSE 39039 END Behavior 39 ECE 331 Digital System Design 32 Mealy FSM Example 2 State diagram resetn t w1Z0 w0z0 ECE 331 Digital System Design 33 Mealy FSM Example 2 State table Present Next state Output 2 State w O w1w0 w1 A A B 0 B A B 0 1 ECE 331 Digital System Design Mealy FSM processcock reset Input w Present State Register I Output E concurrent statements function i Output 2 ECE 331 Digital System Design 35 Mealy FSM Example 2 VHDL code 1 LIBRARY ieee USE ieeestdlogic1164al ENTITY Mealy IS PORT clock IN STDLOGIC resetn IN STDLOGIC w IN STDLOGIC z OUT STDLOGIC END Mealy ARCHITECTURE Behavior OF Mealy IS TYPE Statetype IS A B SIGNAL y Statetype BEGIN PROCESS resetn clock BEGIN IF resetn 39039 THEN y lt A ELSIF clock39EVENT AND clock 39139 THEN ECE 331 Digital System Design 36 Mealy FSM Example 2 VHDL code 2 CASE y IS WHEN A gt IFw 39039 THEN y ltA ELSE y lt B END IF WHEN B gt IFw 39039 THEN y ltA ELSE y lt B END IF END CASE ECE 331 Digital System Design 37 Mealy FSM Example 2 VHDL code 3 END IF END PROCESS WITH y SELECT 2 lt w WHEN B 2 lt 0 WHEN others END Behavior ECE 331 Digital System Design 38 State Encoding Problem State Encoding Can Have a Big Influence on Optimality of the FSM Implementation No methods other than checking all possible encodings are known to produce optimal circuit Feasible for small circuits only Using Enumerated Types for States in VHDL Leaves Encoding Problem for Synthesis Tool ECE 331 Digital System Design 39 Types of State Encodings 1 Binary Sequential States Encoded as Consecutive Binary Numbers Small number of used flipflops Potentially complex transition functions leading to slow implementations OneHot Only One Bit ls Active Number of used flipflops as big as number of states Simple and fast transition functions Preferable coding technique in FPGAs ECE 331 Digital System Design 40 Types of State Encodings 2 State Binary Code OneHot Code SD 000 10000000 S1 001 01000000 SZ 010 00100000 83 011 00010000 S4 100 00001000 S5 101 00000100 S6 110 00000010 S7 111 00000001 ECE 331 Digital System Design 41 A userdefined attribute for manual state assignment ENTITY declaration not shown ARCHITECTURE Behavior OF simple IS TYPE Statetype IS A B C ATTRIBUTE ENUMENCODNG STRING ATTRIBUTE ENUMENCODNG OF Statetype TYPE IS quot00 01 11quot SIGNAL ypresent ynext Statetype BEGIN con t Figure 8 34 ECE 331 Digital System Design 42 ECE331 KJH Implementation of Combinational Design Example ECE33 1 Dig ital Design Prof Hinlz Electrical and Computer Engineerin mm W meliisns33Ln i Discrete Logic Design 69 Dsign a 4bit arithmetic logic unit ALU with two binaw operations Multiplication selector 0 Bitwise Exclusive0R XOR selector 1 How many inpu 4 Operand A 4 Operand B 1 Operation Selector mamas 9K Hnlx1995 mm 2 Discrete ALU Design How many outputs I XOR same width as input 4 biis Mult Sbiis eq1111quot11112 11100001 Specify using truth table 9inputs 8outputsooks like QM 8 tims mamas 9K Hnlx1995 mm 2 10212006 ECE3 31 KJH Alternative Multiplier Approach Shift left and add 1101110 01 1101 1001 11011 1101 11010 0000 11010 0000 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1n212uns K Hm 199515 33111 BCD to 7Segment Decoder sta 7 7A gtQ 7 7 5 x5 7 70 F B x4 LSE D E G BCD in 7Segmmt Dsocds G E C 1n212uns K Hm 199515 33111 7Segment Display Numbers 1n212uns K Hm 199515 33111 10212006 ECE3 31 KJH BCD to 7Seg Truth Table x2x3 AB D 1D212UE6 K Hm 19mm 33111 7 BCD to 7Seg Truth Table x2 x3 ngm A B D 1D212UE6 K Hm 19mm 33111 3 BCD to 7Seg Truth Table 1316 1D212UE6 K Hm 19mm 33111 9 10212006 ECE3 31 KJH BCD to 7Seg Truth Table x2 x3 ngxt A B D 1D212UE6 K Hm 19mm 33111 m x Minterm Form of Outputs 102356789ZdALhroughF Az BZl01234789ZdALhroughF CZl013through92dALhroughF DZl0235689ZdALhroughF Egt 0268ZdALhroughF Fz 045689ZdALhroughF Gz 2345689ZdALhroughF 1 1 1 1n212Uns K Htm 1996 5 33111 1 Output A A 21 02356789 2d AthIoughF Axlxzx4 xZ x4 x3 1D212UE6 K Hm 19mm 3111 12 10212006 ECE3 31 KJH Circuit for Output A AI xlr x2 x3 x4 1n212Uns K Him 19ru5 33111 3 Output B B 21 01234789 2d A throughF x1 Bx xx l 3 4 x4 x3 xZ 1D212UE6 K Hm 19mm 3111 14 Output C C 21 013 through 9 2 d A through F after minimization C 21 013 through 93 through Fz39eno A zxn Cm T C L1 x8 2 E Ai run2me K Hm iguana aspilt2 15 10212006 ECE3 31 KJH Output D D 21 0235689 2 AthroughF d gtlt 1n212Uns K Hmu whip 33111 5 Output E E 21 0268 2d A throughF X 1D212UE6 K me 199mg 33111 7 Output F F 21 04568 9 2d AthIoughF gtlt 1n212um K Hm 1996115 3311 JE 10212006 ECE331 KJH Output G G 21 2345689 zd AmmughF x3 mamas 9K Hnlx1995 mm m MSI Partsquot msway Dewdnum vels mm Openvcallenmv mums 141 m Rm 137 Smnuml mum We 7 Seg ment Display Fm Oonnecuons 1 a 2 1 3 CA 4 N F39 5 N F39 6 N C 7 e 3 d 5 DP 1E I 1 1 g 1 2 N F39 13 b 14 CA Havve 1 mmnnns p 9K Run ms awn Zl 10212006 Representing Data ECE331 Digital Design Prof Hintz Electrical and Computer Engineering 8272006 K Hintz 962006 33102 Weighted Codes Arbitrary Weight Assigned to Each Position Binary Coded Decimal BCD o 8 4 2 1 eg1001819 0 Not all codewords used 69 1101BCD 5272005 ilt Hiniz 952006 33102 Weighted Codes Arbitrary Weight Assigned to Each Position o 2 4 2 1 oeg11012417 39 May have missing or duplicate numbers not unique 5272005 ilt Hiniz 952006 33102 NonWeighted Codes Excess 3 Used for decimal arithmetic Representation is 3 more than binary value SelfComplementing 5272005 K HiniZ 952006 33102 4 NonWeighted Codes Cyclical Sequential codewords differ by only one bit and wrap Particularly useful for electromechanical inte aces where all bits must be mechanically aligned to generate code May have minor inaccuracy but no largejumps Reflected Gray Code is most common example eg Shaftencoders 9 Portable equipment c o Queue counters for inputoutput buffer oomparison 8272006 llt Hintz 9672006 33102 Re ected Gray Code Q Benefits Easy to construct to any resolution number of its Cyclic Unique Construct by prepending each codeword with zero and mirroring codes complementing MSB of mirrored codewords 8272006 K Hintz 9672006 33102 6 2bit Reflected Gray Code E Angle Codewora39 089 0 0 90179 0 180269 1 270359 1 0 8272006 K HintZ 962006 33102 3bit Reflected Gray Code 7 8272006 Angle Codeword 044 0 O 0 4589 O 0 1 90134 0 1 1 135179 O 1 O 180224 1 1 O 225269 1 1 1 270314 1 O 1 315359 1 O O K Hintz 962006 33102 Binary Number System Binary Positional number system Two symbols B 0 1 Easily implemented using switches Easy to implement in electronic circuitry Algebra invented by Boole allows easy manipulation of symbols 5272005 ilt Hiniz 952006 33102 General Positional Notation Consider a Positional Number System Using an Arbitrary Radix r Let S SE SI r Number of symbols E radix SH SH Set of Symbols N Natural or Counting Number not an integer because N 2 0 q Number of positions required to represent N in radix r 5272005 ilt Hiniz 952006 33102 Counting Number A Representation Then for Counting Numbers eg Decimal 5272005 234 w 02r2 clrl cor0 letr10 s0189 234 10 2102 31014 4100 234 10 2100 310 41 234 020043O4 ilt Hiniz 952006 33102 11 Counting Number A Representation 559 Binary radix 2 1011Zc3 F3 02 F2 01 V1 cor letr 2 S 01 1011Z1023002210211020 1011Z 11000Z 0100Z 100Z 11Z 1011Z 110 810 010 410 110 210 110 110 1011Z821w1110 5272005 ilt Hiniz 952006 33102 12 Representation of Fractions Let Ss0sl s s Set0fSymbols quot9 r Z r l r Number of symbols 2 radix 1 gt F 2 O p Number of positions required to represent F in radix r or the number allowed 8272006 K HintZ 962006 33102 13 Decimal Fraction Example Let p 3 r 10 F cilr l 0121 2 ci3r 3 062510 6 101 2 10 2 5 103 062510 6 01 2 001 5 0001 062510 0600 00200 0005 5272005 K Hm Z 952006 33102 14 quotBinary Fraction Examples 0101 21o2 1 02 21o2 3 010121 mini 0101 2 01002 00002 00012 5272005 K Hmu 952006 33102 Combined Positional Representation q l 1 NFZ Gil2 6 i0 i p q l NF 2 2 611quot 8272006 K HintZ 962006 33102 16 A Radix Conversion Desire to convert VF1 gt F2 R F El 26762510 r1 10 P 14 3 371 El Z 0110 173 R102qucliqlcouqocilu lci2uq 2c73q393 T radix point 5272005 K Hm Z 952006 33102 Conversion of N Number Part of R in r1 can be Represented by a Polynomial in r2 a1 gel N391 471 392 6472 392 c rlc r0 1 2 0 2 Tradix point If N is Divided bv the Second Radix 39i qiz 1 3 u Cu 7q rz cq4rz clrz r2 2 l iradiX point 5272005 ilt Hiniz 952006 33102 la Conversion of N Repeated Division Yields All Coef cients N Q0 remalnder r2 i Q0 00 Q 0 Q1 01 r2 etc 5272005 ilt Hiniz 952006 33102 19 Counting Number Example 7 er 26710 r1 10 old radix r2 2 desired new radix r2 r1 2 new radix represented in old radix 267 gt10 Q0 c01331 210 Q0 133 Q1 01661 210 210 8272006 K HintZ 962006 33102 20 Counting Number Example i 6610 Q2 c2330 210 210 Q2 3310 Q3 c3zl61 210 210 amp 1610 Q4 c48O 210 210 8272006 K HintZ 962006 33102 21 Counting Number Example therefore N 26710 1000010112 256 8 2 110 8272006 K HintZ 962006 33102 22 quotConversion of F Fraction Part of R in r1 can be Represented by a Polynomial in r2 Fn 071 r1 02 r2 Tradix point If Fis Multiplied by the Second Radix ip1 07F r2 391 cpr2 Fr 02 11 12 271 lradix point 5272005 llt HlniZ 952006 33102 quotConversion of F Repeated Multiplication Yields All Coef cients Fr1 r2r1 ci1Ro R0 397392r1 C72 R1 etc 5272005 llt Hmiz 952006 33102 Fraction Conversion Example Frl 062510 r1 10 old radix r2 2 desired new radix r2r1 2 new radix represented in old radix 0 62510 210 c1 R0 1 025 0 2510 210 c2 R1 0 05 0510 210 c3 R2 1 00 therefore F 062510 01012 05 0 012510 8272006 K HintZ 962006 33102 25 Conversion Considerations Purpose of Binary Representation is to Put Numbers in a Form which can be Manipulated by Digital Logic Register Size Limits Resolution Not All Numbers in One Radix Can Be Accurately Represented in Another Radix 5272005 ilt Him 952005 33102 Binary Octal Hexadecimal It Is Easy to Convert Binary Numbers to Other More Convenient Representations by Grouping Bits Together and Then Converting by Inspection Octal 0 1 7 o 3bit groups Hexadecimal 0 9 A F o 4bit groups 5272005 llt Hiniz 952006 33102 Binary to Octal Example N2 1010001110101001010100 grouping in 3 bit groups from right N2 1 M M m 101 001 pad leading 1 with two zeros to make it an octal number N2 1010 001 110101001010100 Convert each 3 bit group N8 1 2 1 6 5 1 2 4 N8 12165124 8 8272006 K HintZ 962006 33102 28 Binary to Hex Example N2 1010001110101001010100 grouping in 4 bit groups from right N2 10100011101010 01010100 pad leading 10 with two zeros to make it a heX number N2 10100011101010 01010100 Convert each 4 bit group N16 2 2 8 E A 5 4 N16 2 28EA54 16 28EA54 H 8272006 K HintZ 962006 33102 29 Negative Numbers Signed Magnitude Leftmost bit represents sign 0 1 negative 0 positive Rightmost bits represent magnitude I I qbits ofmagnitude 5272005 ilt Hiniz 952006 33102 Signed Magnitude Example Letq 2 2 zeroes 2 Shifting 1 Does not 0 muItdiv by radix Shifting does account 2 for sign 3 Decimal s mag2 3 1 OOOO O 0 5272005 ilt Hiniz 952006 33102 31 Negative Numbers Reduced Radix 1 s complement 9 s complement etc NF r Lr P7NF rely C For 1 s complement alternative to subtraction is to complement each bit 1011011021Sc 01001001 2 5272005 ilt Hiniz 952006 33102 Reduced Radix Example Let q 2 2 zeroes 2 1 5272005 Decimal K Hmu 952006 33102 1 s C 011 010 001 000 111 110 101 100 Negative Numbers Radix Complement 2 s complement 10 s complement etc NF rquot NF r39s C For 2 s complement alternative to subtraction is to take the one s complement and add 1 5272005 ilt Hiniz 952006 33102 Radix Complement Example Letq 2 1 zero ll 5272005 Decimal K Hmu 952006 33102 2 s C 100 011 010 001 111 110 101 100 Advantages of Radix Comp One Zero 2 s Complement of Negative Number Yields Magnitude Multiplication and Division by Radix Yield Scaled Results with Correct Sign if Sign Replicated in MSB on Divide 5272005 ilt Hiniz 952006 33102 as 2 s Complement Forming the 2 s Complement is an Operation and Can be Done with no Reference to a Negative Number 2 s Complement Notation is an Agreement to use the 2 s Complement Representation of a Positive Number to Represent the Associated Negative Number 5272005 llt Hmlz 952006 33102 37

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.