Intro Electrical & Comp Engin
Intro Electrical & Comp Engin ENGIN 112
Popular in Course
verified elite notetaker
Popular in Engineering and Tech
This 136 page Class Notes was uploaded by Tony Gutkowski on Friday October 30, 2015. The Class Notes belongs to ENGIN 112 at University of Massachusetts taught by Maciej Ciesielski in Fall. Since its upload, it has received 11 views. For similar materials see /class/232296/engin-112-university-of-massachusetts in Engineering and Tech at University of Massachusetts.
Reviews for Intro Electrical & Comp Engin
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/30/15
A 0 311533 r a quotz e A l 8 l w l i a r J J i University of Massachusetts Amherst Engin112 Lectures 3637 Programmable Logic Maciej Ciesielski Department of Electrical and Computer Engineering 12032008 Recap from last lecture Memories 0 RAM 0 ROM 0 Programmable ROM Today s lecture PLA 0 PAL 0 PLDS gtgt Combinational gtgt Sequential FPGAS gtgt LUTbased 12032008 Engin 112 Intro to ECE Combinational PLDs Combinational Programmable Logic Device PLD 0 Convenient method for implementing combinatorial logic 0 Regular structure of AN DOR array Three possible implementations Programmable ROM PROM Inputs Programmable Array Logic PAL Inputs gt Outputs o Programmable Logic Array PLA Inputs r gt Outputs leed AND army programmable OR array decoder programmable Fixed AND array OR array programmable programmable AND array OR array 12032008 Engin 112 Intro to ECE Outputs Programmable Logic Array PLA Programmable AND and OR AD arrays B Q AND array c generates products D i OR array generates Ll sum of products Output XOR allows E inversion c as M W AB39 AC BC A BC What is the function of this PLA l F1 AB AC A BC F2 AC BC inverters 12032008 Engin 112 Intro to ECE Fl Programmable Programmable Logic Array PLA x Vt j Xryrzr x yz Xyz Programmable inverters 0 xyz 6 Implement F1Xyz H0356 i2 X y z X yz xy z xyz F2Xyz 470124 7 E356 F2 X y z X y z X yz xy z xyz 12032008 Engin 112 Intro to ECE 5 U U U U F1 l 12032008 Programmable Array Logic PAL AA39 Product term Programmable AND array and fixed OR array Section of PLA A 0 Threewide AN DOR array 0 AND generates product term 0 OR generates sum 139 All fuses intact always 0 V Additional feedback 0 First output is fed back Limitations 0 Only three wide AN DOR 0 Not all functions can be 0 implemented x Fuse imam Fuse blown Engin 112 Intro to ECE 6 Programmable Array Logic Implement W W 39 F1Xyz 20 3 5 6 lelzl Xy z xyz 39 F2Xyz x 20 124 7 23 5 6 lelzl le12 X yz xy z xyz W2356 F 50 3 5 5 V G Z356 12032008 Engin 112 Intro to ECE 7 Sequential Programmable Devices PLDs convenient for combinatorial circuits 0 Can we design something similar for sequential circuits Wilma Combinational gtOU P t5 circuit BaSIc sequential cwcunt T What can we use for 0 combinatorial portion mm AND 01mm PALorPLA Fl Outputs O S memory I p p Sequential programmable devices 0 Sequential programmable logic device SPLD 0 Complex programmable logic device CPLD 0 Field programmable gate array FPGA 12032008 Engin 112 Intro to ECE 8 Sequential Programmable Logic Device SPLDs are mode from macrocells 0 Contains sumof product combinatorial logic PAL 0 Contains flipflop Dtype Macrocell 0 Typically Sum of Tristate CLK 0E output products 810 per IC package j 12032008 Engin 112 Intro to ECE Complex Programmable Logic Device CPLDs for larger circuits 0 Combine multiple SPLDs 0 Switch matrix connects SPLDs m I m pm I m lO block with tristate lO no I I I I 0 Details are I I I I quotm vendorspecific M m M m Altera CPLD 239 PAL or PLA structures 12032008 Engin 112 Intro to ECE 10 Field Programmable Gate Arrays Gate Array 0 An array of programmable logic function blocks 0 Gate array is manufactured ahead of time prefabricated 0 Customer programs configures the gate array gtgt provides logic functions and interconnections Field Programmable Gate Array FPGA 0 An array of identical programmable logic function blocks gtgt Each block has a m number of inputs k gtgt Each block is able to implement an arbitram logic function 0 Customer programs FPGA after manufacturing in field gtgt Reprogrammable Easier to debug and cheaper in smaller quantity than ASIC An alternative to ASIC 0 High production cost amortized over large quantity of chips gtgt ASIC Application Specific Integrated Circuit high volume of custom design chip gtgt FPGAs high volume of programmable flexible chips 12032008 Engin 112 Intro to ECE 11 t Lookup Table based FPGA Lookup Table 0 Truth table implemented in hardware Can implement arbitram function with fixed number of inputs typically 45 by programming the storage bits customizing the truth table Read or Write P Data Example F X X X X lProgramming bitP 1 2 1 2 2lnput LUT X1 X2 F F gt 12032008 Engin 112 Intro to ECE 12 LUT Programming Implement the following function using 3input LUT F ab ac be a b c F Programming bit LUT 12032008 Engin 112 Intro to ECE 13 Logic Element Logic Element the basic programmable element of FPGA 0 Contains LUT lookup table Inputs Clock Enable 12032008 Engin 112 Intro to ECE 14 FPGA Architecture Logic Element LE Tracks LE LE LE 39 LE LE LE LE LE Ill Each programmable logic element outputs one data bit 0 Interconnects are programmable between elements 0 Interconnect tracks grouped into channels 12032008 Engin 112 Intro to ECE 15 FPGA Routing EE ES Basic Logic Element Programmable routing 0 SwitchboxesS 0 IO connectors C o 1 2 o 1 2 a 5 block b c block 12032008 Engin 112 Intro to ECE 16 12032008 Mult 1 U m U Tr Tr Z I 11 J O 11 O 3 FPGA S stem Target Architectures A I I I L I I I r Microprocessor Reconfigurable ASIC SW hardware HVV ASIC gives high performance at cost of inflexibility Processor is very flexible but not tuned to the appHca on Reconfigurable hardware is a nice compromise gtgt Uses CPLDs and FPGAs 12032008 Engin 112 Intro to ECE 18 Reading Assignment Read Mano 81 85 RTL 12032008 Engin 112 Intro to ECE 19 t e r p I 5 University of Massachusetts Amherst Engin112 Lectures 3435 MemoryRAM ROM Maciej Ciesielski Department of Electrical and Computer Engineering 11262008 Recap from last lectures Timing in digital logic 0 Combinational logic 0 Sequential logic 0 Timing analysis Today s lecture Computer Memory 0 Random Access Memory RAM 0 Read Only Memory ROM 11262008 Engin 112 Intro to ECE Memories Where is a memory used 0 Memory hierarchy next slide What are the differences between memories 0 Technology magnetic voltage charge fuse 0 Volatility volatile nonvolatile 0 Access sequence random sequential 0 Speed access time and throughput 0 Access type gtgt Random Access Memory RAM gtgt Read Only memory ROM ls memory combinatorial or sequential logic 0 RAM sequential similar to register 0 ROM combinatorial programmable logic 11262008 Engin 112 Intro to ECE Memory Hierarchy Processor I I l v Main Memory L2 Memory Data 3 L1 Cache path 1 Cache Speed ns 1ns 2ns 6ns 100ns 10000000ns Size MB 00005 01 14 1001000 100000 Cost M B 100 30 1 005 Technology Regs SRAM SRAM DRAM Disk 11262008 Engin 112 Intro to ECE Randomaccess Memory RAM Memory terminology 0 Smallest unit is word n bits wide in data input lines 0 Identified by address k address lines gt 39 Memor unit Block diagram Read k kao ds 0 kaddress lines n bit perword gtgt At most 2quot words storage wrlte 0 n data lines input and output l n data output lines What is the total memory size in bits 0 Size 2quot x n bits Example 0 1024 bit memory with 16bit words 0 How many address lines 11262008 Engin 112 Intro to ECE 5 Memory Layout Example 0 1024 16bit word storage Memory address 0 10 bits identify address Binary 0 16 bits stored at each location 0000000000 0000000001 0000000010 Why not make memory bitwise addressable Remember kKilo 210 0 M Mega 220 GGiga230 11262008 1111111101 1111111110 1111111111 Engin 112 Intro to ECE decimal 1021 1 022 1023 Memory content 10 110103910391013913910391 391010101110001001 0000110101000110 1001110100010100 000011010001113910 3913910391139110001003910391 RAM Read and Write Control inputs 0 Address i n data input lines 0 Read Write k address lines 1 Memory unit Read gt 2quot words n llJit er word Write a p Write operation 1 Apply address to address lines 2 Apply data to data input lines 3 Activate write input l I data output lines Read operation 1 Apply address to address line 2 Activate read input 3 Read value from data output lines 11262008 Engin 112 Intro to ECE 7 RAM Read and Write Control inputs on commercial memories 0 Memory enable 0 Read and write often readwrite Memory Read Memory enable write operation 0 X none 1 0 write to selected word 1 1 read from selected word What timing constraints need to be considered 0 Access time time to read a word 0 Cycle time time to write a word 0 Also setup and hold time on address 11262008 Engin 112 Intro to ECE RAM Timing Example 0 Processor clock f 5OMHz 20ns 0 RAM access time RAM cycle time 50 ns Write timing 4 2011596 2 T1 T2 T3 T1 Clock Memory Address valid address Memory 4 enable gtC L Read f gtC W te Data D t r 1d 0 Address and data needs to be valid before memory enable 11262008 Engin 112 Intro to ECE i 11262008 RAM Timing Read timing 1 Sl nsec Clock T1 T2 T3 T1 Memory X Address valid gtC address Memory 39t enable Read Write Data gtltData valid gtC output 0 Address needs to be valid before memory enable 0 Data becomes valid before access time expires Processor and memory often not in sync 0 Memory access can take multiple clock cycles Engin 112 Intro to ECE 10 Memory Cell Design Binary memory cell implemented with SR latch Select Select Output Input Output Readl Write Readlwntle 0 Note memory is not clocked 11262008 Engin 112 Intro to ECE 11 RAM Types Static random access memory SRAM 0 Operates like a latch 0 Implemented with 6 transistors 0 Fast operation 0 Memory retains information while power is applied Dynamic random access memory DRAM 0 Data stored as charge in capacitance word quot8 0 Implemented with 1 transistor 0 Slower operation 0 Memory needs to be refreshed 11262008 Engin 112 Intro to ECE 6transistor CMOS SRAM Cell 5141 QJM sL 11262008 WL VDD M2 lo 5 J o l M3 Engin 112 Intro to ECE BL 13 1Transistor DRAM Cell Design Capacitor Metal word line Diffused 39 I I bitline Poly nversnon ayer induceq by Polysilicon 39 Polysilicon plate blas gate ate Crosssection Layout Uses PolysiliconDiffusion Capacitance 11262008 Engin 112 Intro to ECE 14 Memory Organization IlmemaHawm ofmemow Immm 0 One word per row 1 da a 0 Each binary cell word 0 I39 39 39 39 39 439 39 quot quot39 39 39 39 39 quot stores one bit 33565 Word 1 r r r Memory cell 1331 9 w Select Word 2 Input a BC Output g gw EN w d 3 f f f r r Reaerite ReadWrite a Decoder 7 7 SGIGCtS word 2 H Outpuldata E nventional symbol Array logic symbol 11262008 Engin 112 Intro to ECE 15 Larger Memories Address Decoding What is the problem with larger memories 0 Number of binary cells increases that s expected 0 Decoder becomes really large How many gates in a k X 2quot line decoder 0 2k AND gates with k inputs each Example 0 1024word memory decoder requires 1024 AND gates with 10 inputs Solution 0 address decoding De 07 11262008 Engin 112 Intro to ECE 16 Coincident Decoding Address Splitting Split decoders into two dimensions 0 k2 x 2 decoder in each dimension Y Hill 5 X 32 decoder Coincidence of selected lines determines word 0 1 2 A 2t 3 1 How many gates are required 323264ANDs f 5 binary address X 5x32 M M decoder 12 X Y 31 11262008 Engin 112 Intro to ECE 17 Address Multiplexing DRAM Number of pins on memory chip impacts cost 0 How can we reduce the number of pins necessary Address multiplexing 0 Address is transmitted in parts 8bit column register Example 64k word DRAM 0 CAS Column Address 1275 Strobe RAS Row Address m 2mm Strobe address lt Readrwme What does timing diagram look like 0 3 11262008 Engin 112 Intro to ECE 18 ReadOnly Memory ROM Storage for memory that does not need to change Block diagram kinputsaddms 2K 0 Address ROM 0 Outputs n outputs data 0 No data inputs Internal design I W X 8 decoder 0 256 internal connec ons Connections 0 No connection O 0 Connection 1 11262008 Engin 112 Intro to ECE 19 ReadOnly Memory Example of programmed ROM 0 x indicates connection Programming of ROM All connection exist as fuses Higher voltage can blow fuse Blown fuse indicates O A7 A6 A5 A4 A An 11262008 Engin 112 Intro to ECE 20 Types of ROM Mask Programmed ROM 0 During fabrication of ROM 0 Only economical in large quantities Programmable ROM PROM 0 ROM with all fuses intact 0 Highvoltage pulse on special pin can irreversibly blow fuses 0 Note hardware procedure despite programmable Erasable PROM EPROM 0 Connections can be restored 0 Exposure to UV light resets EPROM Electricallyerasable PROM EEPROM 0 Electric signal can reset connections no UV required 11262008 Engin 112 Intro to ECE 21 Programmable ROM Any Boolean function can be implemented with a decoder and an OR gate 1 Decoder produces minterms 12 5223 0 OR gate makes sum How many Boolean function can be implemented on 32x8 ROM 0 8 Boolean functions with 5 inputs One Boolean function per column AN DOR structure OR ing of minterms ANDing of inputs The biggest part of ROM 0 Decoder 11262008 Engin 112 Intro to ECE 22 11262008 Programmable ROM core 5 X 32 decoder Engin 112 Intro to ECE 23 Programmable ROM example Implement D0 39 F1Xyz 20 3 5 6 lelzl Xy z xyz 3x8 decoder 39 F2Xyz AZHZ1JZ4JO lelzl le12 Xyz xy2 xyz 11262008 Engin 112 Intro to ECE lCDU39lhUONI lo 24 Reading Assignment Read Mano 76 77 Programmable Logic 11262008 Engin 112 Intro to ECE 25 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 13 Timing and Random Access Memory Timing In circuits data are transferred from input to output via electrical currents that cause changes in voltage levels It takes some small but not zero time for currents to propagate through the devices that make up the circuits which causes some delay between the time a voltage change is applied at the input indicating new input data and the resulting change starts and is completed at the output That delay determines how rapidly the circuit is able to process data In combinational circuits with no clock two types of delay are important contamination delay denoted ted and propagation delay denoted tpd Contamination delay is the time it takes from the a change in the input to sz i39tto cause a change in the output so a change in the output does not start until ted seconds after the input change Propagation delay is the time it takes from a change in the input to the completion of the change in the output so after tpd seconds the output will not further change in response to the input change Example Suppose that we have AND gates with contamination delays 5 nsec 5 nanoseconds 5 x 10399 sec and propagation delays 10 nsec and OR gates with contamination delays 3 nsec and propagation delays 8 nsec Find the overall contamination and propagation delays for the circuit shown below tpd path x output y ted path ted 3 nsec 3 nsec 6 nsec tpd 10 nsec 8 nsec 18 nsec Propagation delays and setup times determine the minimum required clock period that is the time from one triggering clock edge to the next the period must be long enough to allow the desired input to propagate through all circuits leading to the output flipflop plus allow for enough setup time at the output The clock frequency is defined to be 1period this is a measure of how fast the overall system is able to operate Frequency is expressed in units of Hertz Hz sec391 So for example a clock having a period of 100 nsec 1 x 10397 sec has a frequency of 11 x 107 1 x 107 Hz 10 x 106 Hz 10 megahertz 10 MHz Note that the maximum allowed clock frequency is 1minimum allowed clock period In circuits with multiple paths from input to output it is the path with the largest sum of propagation delays and output setup time that determines the maximum clock frequency Example In the circuit shown below each flipflop has propagation delay tckQ 10 nsec and setup time 2 s 2 nsec Combinational circuit 1 has a propagation delay tpm 5 nsec combinational circuit 2 has propagation delay tpd2 8 nsec and the AND gate has propagation delay tpd3 1 nsec What is the maximum possible clock frequency for the circuit D1 Q1 Input gtC Comb Circuit 1 D2 gtC Q2 Comb Circuit 2 Clock Output After the initial triggering clock pulse edge 1 It takes tckQ 10 nsec for the input to propagate from D1 to Q1 2 It takes tpm 5 nsec for the value at Q1 to propagate through Combinational Circuit 1 and tpd2 8 nsec for it to propagate through Combinational Circuit 2 so the inputs to the AND gate will be correct 8 nsec after Q1 is set 3 It takes 2 1 nsec for the AND gate inputs to propagate to D2 pd3 4 The value at D2 must be set for t8 2 nsec before the next triggering clock pulse edge So the minimum required time between clock pulse edges is 10812 21 nsec and the maximum possible clock frequency is 121 x 109 476 x 107 476 MHz One last issue in timing We must insure that there are no hold time violations at flipflop inputs that is we must make sure that the input into a flipflop does not change for at least 2 7 seconds after a triggering clock pulse edge Recall that contamination delays determine when a change will m appear at a circuit s output So we must make sure that contamination delays are such that no change will start to appear in a flipflop input for at least th seconds that is the smallest sum of contamination delays along paths into a flipflop must be 2 th Example In our previous example suppose that each flipflop has contamination delay ted 2 nsec and hold time 2 7 5 nsec Combinational circuit 1 has ted 3 nsec combinational circuit 2 has ted 4 nsec and the AND gate has ted 05 nsec Does the circuit satisfy the hold time requirements The time from when a transfer is initiated at the first flipflop on a clock pulse edge until the effects begin to appear at DZ is 2305 55 nsec path through combinational circuit 1 This is gt th 5 nsec so hold time requirements are satisfied II Memory A memory unit is a collection of cells registers that are used to store binary data During processing selected data are transferred from the memory unit where they are stored to registers in the particular processor The processing results are then transferred back into the memory unit The transfer of data out of a memory unit is called a read while the transfer of data in is called a write One type of memory unit called Random Access Memory RAM allows for both read and write operations Another type called Read Only Memory ROM allows data to be written in only once after that only read operations are allowed 80 data in ROM are stored permanently One note on logic symbols In memory operations it is common for a logic gate to have many inputs For graphical simplicity instead of drawing many lines going into the gate we usually draw a single line in with the actual input lines drawn perpendicular to that ingoing line For example QQiA 3 isdrawnas I l l l gt First let s consider RAM The key requirements for RAM are that we need to be able to specify whether we want to write or read data and to specify where that is the specific memory cells the data are to be written to or read from ID I IUJIJgt Inside the memory data are stored as groups of bits called words An 8bit word is called a byte Typically each word consists of some fixed number of bytes for example a word may consist of 4 bytes 32 bits The memory unit stores 2quot words where k is some integer The capacity of the memory unit is usually given as the total number of bytes it can store for example a RAM that stores 228 4byte words has a capacity of 228 0 22 230 10737 x 109 bytes this is usually written as 1 GB 1 gigabyte When a write or read operation is performed One entire word is transferred into or out of RAM So A RAM that stores 2quot m byte words needs to have 1 n 8m data input lines so that a new word can be written into memory 2 n 8m data output lines so that a word can be read from memory 3 A readwrite line to specify which operation is to be performed 4 k address lines to specify which of the 2quot words is to be writtenread 5 Usually a memory enable line that enablesdisables operations on the memory unit n data Input lines Block symbol lquot J k gt RAM lt ReadWrite address 2quot words lines n bitsword gt Hl n data output lines MemOIy enable Note Word locations are indexed by kbit binary numbers 0000 to 1111 so the bits on the address lines tell which word location is to be accessed 1 2 3 1 2 Steps for a Write operation Put the binary code for the desired word location on the address lines Put the bits to be written in on the data input lines Activate Write and Memory Enable inputs The bits from the data input lines will then be transferred into the register that is word location specified by the address bits Steps for a Read operation Put the binary code for the desired word location on the address lines Activate Read and Memory Enable inputs The bits stored in the register word location specified by the address bits are then transferred to the data output lines Action of ReadWrite and Memory Enable inputs Memory Enable ReadNVrite Operation 0 X no operation 1 0 Write 1 1 Read Timinq requirements The memory unit requires time to perform read and write operations The time required to select and read a word is called the memory access time The time required to write to a selected location is called the memory cycle time For a write operation The input lines containing the address of the selected word the data to be written Memory Enable 1 and Read Write 0 must all be held stable for a number of clock cycles that at least cover the cycle time Til T2 T3 T1 Clock Memory address Address valid Memory enable ReaIi Write Data input Data valid BJJLBJ gtC gtC For a read operation the address lines Memory Enable 1 and ReadWrite 1 must all be held stable for a period of time at least equal to the access time Clack T1 T2 T3 T1 Mammy Address 1valid gtC address Dlt Mammy l 39i enable RataerIr Write Data X ata valid gtlt autput One type of RAM is called static RAM SRAM it uses latches to store the data one latch per bit The basic binary cell BC for storing one bit can be represented using a D latch as follows Input Select En 3 Output 79 ReadWrite ldea When Select 1 and ReadWrite0 the input bit is written into the latch the output bit is fixed at 0 When Select1 and ReadWrite1 The latch is disabled so the stored bit is unchanged the output bit the stored bit Q When Select0 the latch is disabled and the output bit is fixed at 0 transistors In a typical RAM Block symbol for Binary Cell A real SRAM binary cell is typically constructed in CMOS with a total of six Select 1 BC l ReadWrite Input gt 39 gt Output there are thousands of words each consisting of some number of bytes so there are many thousands or millions of binary cells Example of RAM storing four 4bit words Input data Address inputs quotmy Idccoder 39 word39 Memo enable ReadWrite Output data University of Massachusetts Amherst Engin112 Lecture 26 Sequential Circuit Design FSM Maciej Ciesielski Department of Electrical and Computer Engineering 11032008 Recap from last lecture Sequential circuit analysis 0 State equations 0 State table 0 State diagram Today s lecture 0 Finite state machines FSM gtgt Mealy gtgt Moore 0 Sequential circuit design procedure 11032008 Engin 112 Intro to ECE Finite State Machines State diagrams are representations of Finite State Machines FSM 00 y lllo 0 Two flavors of FSMs V 7 7 7 V gtgt Mealy FSM ll gtgt Moore FSM 3 Difference I How output is determined quot Mealy FSM 0 Output depends on M and state 0 Output is not synchronized with clock gtgt can have temporarily unstable output Moore FSM 0 Output depends only on state liO 11032008 Engin 112 Intro to ECE Two Flavors of FSM Mealy vs Moore machine Mme Mud Fm Ilapuu I 395 Nerf Stare Combinatianal Lang OM fpu r5 Mealytype Inputs 0 Next Stare Combinationa Output i Srqu r L Regurer Logic Moon Mud in 0111le RENT Combilm onal egmer L ogic Logic 11032008 Engin 112 Intro to ECE Ompem Maturewe Mealy Machine Output based on state and present input 0 Output changes durin transition inout inputs f h h outputs present state 11032008 Engin 112 Intro to ECE Moore Machine Output based on state only 0 Output is associated with state inputs I CL next state CL Hquot0utputs 11032008 Engin 112 Intro to ECE Design of Sequential Circuits How can we design a sequential circuit 0 Eg circuit that detects 3 or more consecutive 1 s in input Desiqn procedure Derive state diagram from description Reduce number of states if necessary Assign binary values to states Obtain binary coded state table transition table Choose type of flipflops Derive flipflop input equations and output equations Draw logic diagram NQFNPWNT Steps 1 amp 3 require insight Steps 2 4 7 can be automated 0 Design that follows welldefined procedure called synthesis 11032008 Engin 112 Intro to ECE Canonical form of Sequential Circuits Graphs are hard to compare 0 Arbitrary state names 0 Arbitrary coding Graphs are generally very difficult to deal with 0 Determining if two graphs are identical is the graph isomorphism problem gtgt No known algorithm exists that can determine isomorphism in polynomial time for arbitrary graphs gtgt Problem reduces to trying every possible matching gtgt Requires exponential time very very long for large graphs Canonical form of sequential circuit would require solution to graph isomorphism problem No canonical form for sequential circuits exists 11032008 Engin 112 Intro to ECE 8 State Assignment States are represented by flipflop values in circuit 0 Need to encode state in binary Many possible encodings Terminology 0 State table uses uncoded states 0 Transition table uses coded states 1 1032008 What is the minimum number of flipflops that are necessary to encode m states 0 Need at least l log2m bits I is ceiling function State Binary Gray Onehot a 000 000 00001 b 001 001 00010 c 01 0 01 1 001 00 d 01 1 010 01 000 e 100 1 10 1 0000 Engin 112 Intro to ECE Example 1 Sequence Detector Circuit specification 0 Design a circuit that outputs a 1 when three consecutive 1s have been applied to input and 0 othenvise Step 1 derive state diagram 0 What should a state represent gtgt Eg number of 1 s seen so far 0 Moore or Mealy FSM gtgt Both possible gtgt Chose Moore to simplify diagram 0 State diagram gtgt State SO zero 1s detected gtgt State S1 one 1 detected gtgt State 82 two 1s detected gtgt State SS three 1s detected 11032008 Engin 112 Intro to ECE 10 Example 1 Sequence Detector Step 2 reduce number of states 0 State table current next state output 0 state x0 I x1 q 0 SO 80 S1 39 S1 80 82 82 So 83 0 83 So 83 OOO 0 Which states are equivalent gtgt None no state reduction possible Step 3 state assignment 391 J 0 Two flipflops 0 Binary state coding 11032008 Engin 112 Intro to ECE Example 1 Sequence Detector Step 4 Binary coded state table 0 Name flipflops A and B current state next state output xO x1 A B A B A B O O O O O 1 O O 1 O O 1 O O 1 O O O 1 1 O 1 1 O O 1 1 1 Step 5 Choose type of flipflops 0 Eg Dflipflop 0 Characteristic equation Qz 1DQ 11032008 Engin 112 Intro to ECE 12 Example 1 Sequence Detector Step 6 derive flipflop input equations and output equation 0 Use state table current state input next state output 0 DAABX A l B X A l B y 23 5 7 o o o o o o B2 1 D AB O O 1 O 1 O o B X E157 0 1 0 0 0 0 0 1 1 1 0 0 mm 26 7 1 O O O O O or yAB 23 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 11032008 Engin 112 Intro to ECE 13 t Example 1 Sequence Detector Step 6b minimize equations Az 12357 Bz 12157 yAB 23 easy y AB Karnaugh maps forA and B Bx B 00 01 1t 10 39l DAAxBx DBAxB39x 11032008 Engin 112 Intro to ECE 14 Example 1 Sequence Detector Step 7 Circuitdiagram 0 DA AXBX 0 DB AXB X YAB 11032008 Engin 112 Intro to ECE 15 Terminology W 1 L t Next state 1 f logic 1 D 6 E w Wquot gtm 3 Jack J Output logic l I Y if I 11032008 Engin 112 Intro to ECE 16 Summary Finite state machines form the basis of many digital systems Designs often start from clear specifications Develop state diagram and state table Optimize using combinational design techniques 0 Output logic 0 Next state logic Mealy or Moore implementations possible 11032008 Engin 112 Intro to ECE 17 Homework Read Mano 57 state reduction and 56 Verilog Midterm 2 exam Wed Nov 12 at 630 pm 0 Material Chapters 4 and 5 gtgt No Verilog HDL QampA session on Monday Nov 10 2008 11032008 Engin 112 Intro to ECE 18 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 8 Comparators Encoders and Multiplexers We ve discussed a number of combinational circuits that are used for arithmetic adders subtractors an multipliers Several other combinational circuits perform operations that are important for digital computation these include magnitude comparators multiplexers and encodersdecoders A magnitude comparator determines which of two input binary numbers is larger A multiplexer has multiple input lines and a single output line that is connected to one of the inputs A set of control bits is used to determine which input line is mapped to the output An encoder is a circuit that maps some set of inputs into binary representations for example a BCD encoder would have ten input lines representing decimal digits 01 9 and four output bits A decoder reverses the encoding a BCD decoder would have four input bits and ten output lines each one representing a decimal digit I Magnitude Comparator Say we have two n digit binary numbers A An7An2 A0 and B Bn1Bn2B0 We want to determine which of the following is true 1 A B 2 A gt B or 3 A lt B How do we develop a circuit to do this First define three circuit outputs F 1 if and only ifA B F2 1 if and only ifA gt B and F3 1 if and only ifA lt B Then our goal is to design a combinational circuit having 2n inputs A and B and three outputs F7 F2 F3 Note that this is impractical to do with our standard method of truth tables and Karnaugh maps once n gets to be reasonably large since the truth table will have 22 rows 4bit words 28 256 rows 8 bit words 216 65536 rowsl Instead we develop an algorithm that is a stepbystep set of rules that the comparator must satisfy and design a circuit that performs the algorithm First Develop a circuit that computes F7 that is that indicates when A B Note that A B if and only if AK Bk for every k 01n1 For each k 01n1 define the bit xk by Xk1ifAkBk39Xk 0ifAk Bk Draw the Karnaugh map for in Bk AK 0 1 So xk AkBk Ak Bk O 1 AKXOR Bk AKIBK AkBk 1 1 this is sometimes written as xk AKXNOR Bk Then F1X0X1Xn1 Circuit for computing in Bk gtO A gt B k k AkBk Block symbol A Ak Bk Now we can use these blocks in quot Xk developing the rest of the circuit Bk AkBk Now consider F2 F2 1 if and only ifA gt B when does this occur A An1An2A0 gt B Bn1Bn2B0 when 1 An11 AND Bn10 gtAn1Bn7 OR 2 An1Bn1 AND An21 AND Bn20 gt Xn1An2Bn2 OR n An1Bn1 AND An2Bn2 AND AND A1B1 AND A01 AND 300 gt xn7x2 X1A0B0 803 F 2 An1Bn1 Xn 1An2Bn2 Xn1 Xn 2An3Bn3 Xn7Xn2 X7A0B0 To get F3 1 when B gt A just reverse A and B from F2 F3 An 1an1 Xn1An2an2 Xn1Xn2An3an3 Xn7Xn2 X7A0 B0 Magnitude comparator circuit for n 3 A2 B2 II Multiplexer A multiplexer MUX uses control bits to direct one of a set of multiple inputs into a single output for example an Arithmetic Logic Unit ALU uses a multiplexer that outputs the result of one of four possible operations on a pair of bits AND OR addition subtraction So it is a fourtoone multiplexer Let s consider the general design of a fourtoone multiplexer Let the inputs into the multiplexer be denoted l0 l7 l2 3 For example given two bits A and B being processed by an ALU we might set 0 A AND B I A OR B 2 sum bit forAB addition not OR 3 sum bit forAB Let Ybe the MUX output Since we need to select one of the inputs to direct to the output we must be able to make four choices so we need two control 80 and 87 bits to indicate which choice we make Suppose we use the following rule the input that is directed to the output is lk when k 8780 So 87 80 0 means Y I0 87 0 80 1 means Y 7 etc Note that this can be implemented by Fourto one MUX Block symbol for fourtoone MUX 4x1 MUX One important use of multiplexers is to implement logical functions in fact a fourtoone MUX can be used to implement any function of three bits Xyz Idea Set 87 X 80 y then set each of the inputs 0 l7 l2 and 3 to have one of the values 0 1 z or 2 as needed to agree with the truth table which variable is on which input line determines the function that is implemented Example Implement the function FXyz xz yz using a 4to1 MUX xyz F 4x1MUX 000 o y 0 FQ0 001 o x 81 010 o Fl z 011 1 7 0 0 y F 100 1 z 1 Fl2z39 101 o 2 2 110 1 FI31 7 I3 111 1 III In general Afunction of n binary variables can be implemented with a 2 7391 by 1 MUX using n1 control bits and 2 1 input lines So multiplexers provide a very flexible modular technique for function implementation EncodersDecoders An encoder maps 2 or fewer input lines into n output lines Only one input line at a time can have value 1 all others are supposed to be 0 The output line values represent the binary code for the input line that has value 1 Example A BCD encoder has 10 input lines each representing a decimal digit and 4 output lines so the output is the binary code representing a given decimal digit Let the inputs be denoted DO D7 09 with Dk 1 meaning that we have decimal digit k1O Let the output bits be denoted as w X y 2 So we have wxyz D 1 0000 What functions generate the output bits 0 u from the Inputs 011 0001 021 0010 WDBDQ 031 0011 041 0100 XD4D5DGD7 D1 0101 5 yD2D3DGD7 061 0110 071 0111 zD1D3D5D7DQ 081 1000 091 1001 D1 05 D7 09 D4 05 06 D7 y Dz D3 L Z l De D7 W 08 09 X W It D Priority and validity As noted the encoder assumes that exactly one input line has value 1 and all others are 0 However in real circuits the values on lines change over time and the timing synchronization may not be perfect This leads to two possible problems All input lines might be 0 The usual convention in this case is to set all output lines to O but in our BCD example this is also the binary code for the Do How do we distinguish the output for input D0 from the output for no input One approach Define an extra bit Vcalled a valid bit indicator We set V 0 when all inputs are 0 and V 1 othenvise So How is V represented as a function of the inputs Then we can distinguish the output for D0 wxyz v 0000 1 from the output for no input wxyz v 0000 0 ii Two or more lines might have value 1 at the same time To resolve the conflict we can set a priority rule that establishes which input line is to be encoded when two or more have value 1 As one possibility we might say that numerically larger inputs have priority over those that are smaller for example in the BCD encoder if both D6 1 and D3 1 we will output the code for D6 and ignore D3 Then In the BCD example we have an encoding rule that looks like this X Don t Care D0D1D2D3D4D5D6D7D8D9 wxyz v 0000000000 00000 XXXXXXXXXl 10011 XXXXXXXXlO 10001 XXXXXXXlOO 01111 1000000000 00001 Example In the BCD encoder we saw that without priority ecoding the function for output bit X is X D4 D5 D6 D7 How is this changed when we use priority encoding V th priority encoding The output encodes D7 only when both 09 and 08 are 0 Similarly we encode D6 only when both 09 08 and D7 are all 0 etc So the new function for X becomes x D7081 06071381794 05061371381 04051761771381 07081 D6Dg Dg 05081 04081 D7 De D5 D4DBDQ o A decoder is the opposite of an encoder it maps n input lines whose values represent the binary code for some object into 2 or fewer output lines Only one output line has value 1 at any given time that is the output whose code is given by the values on the input lines Example A BCD decoder has four input bits w X y z and ten output bits DO D7 09 with Dk 1 when wXyz is the binary code for decimal digit k1O We have the inputoutput relation shown previously slide 13 So DO w x y z Note that the function generating each D7 w x y z output bit is a minterm of the set of inputs 09 WX y z In general We can think of a decoder having n inputs and 2quot outputs as a circuit that generates all of the possible minterms of the input bits these decoders are called n to 2quot line decoders D Xrylzr Example 3to8 line decoder D4 1 fquot39z39 D5 xyquot D5 ms Block symbol for 3to8 ine decoder m0 m 3x8 Decoder 7 m2 m3 m4 m5 m6 m7 Note that since any function can be written as a sum of minterms an n to 2n ine decoder can be used along with OR gates to implement any function of n bits Example For the example considered previously FXyz xz yz X xy z x yzxyz m6m4m3m7 quot70 X 77 3x8 Decoder 7 quot72 m y 3 mi r 77 m5 39 m6 College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 9 Synchronous Sequential Circuits Enable for Combinational Circuits Combinational circuits are often provided with an enable input to further control circuit operations For example consider the 3 X 8 line decoder shown last week D n 1quotiquot39 Suppose we add an Di enable variable w as input to each of the AND gates Then when w1 the decoder is enabled and the output is as shown in the figure But when w0 all outputs are zero D4 Jay39z Ds xiiquotz D5 t39yz39 Example application using two 3 x 8 line decoders to make a 4 x 16 line X decoder output is 1 on the line that corresponds to the minterm for the values of WXyz 3x8 Decoder 1 m0 1m1 1m2 1m3 3x8 Decoder enable 0m2 0m4 0m5 0 m6 0m7 1m4 z 1m5 1m6 enable L 1m7 II Synchronous Sequential Circuits Sequential circuits are those in which part of the circuit s output is fed back to form part of the circuit s input The feedback path necessarily includes some delay so the same signal is not simultaneously at the input and output and data storage registers memory elements Data gt Combinational gt Data Input circuit output Memory element Synchronous sequential circuits have an associated clock that allows for data transfer into or out of the memory elements only at discrete points in time So the circuit performs computations on the data at times that are determined by the clock As in any circuit the output of a sequential circuit is a function of the inputs but the introduction of timing and feedback into the circuit operation both expands the types of operations the circuit can perform and complicates the circuit description and analysis In particular in describing the action of a sequential circuit that is the output that is generated at any given time we need to consider both the data input to the circuit and the state that is the binary information being stored of the memory elements Example As an example consider the circuit shown below XI Input at time i lXJ Yi1 State at time i output at time iT As a function of the input and state y FX y7 1cycle delay memory yl lt Output at timei One cycle period lt gt Clock sngnal A T T T time i1 time i time i1 time simple expression If we try to write the output as a function ofjust the inputs Using yk FXk ym for every time k we have y FXi Yi1 F09 F094 Yi2 F09 F094 FX2 Yi3 very complicated L First We will look at the memory elements that can store 1 bit 1 Latches A latch is a storage element whose operation is controlled by the clock level that is either high voltage 1 or low voltage 0 1 0 lllll l Latches are simple circuits consisting of coupled NAND or NOR gates We ll look at a few different examples i SR Latch First note that for a twoinput NOR gate if one input is set at 1 then the output is 0 no matter what the other input is For a NAND gate if one input is set at 0 then the output is 1 no matter what the other input is 1 O O 1 29 D Consider this circuit The bit stored by this latch is the value Q When the latch is acting as a storage element the inputs R and S are both 0 The stored value of Q is set by temporarily changing either R or S but not both to 1 d l Say that we set S1 R0 Then and Q 1 and Q 0 This is called the set state Note that after the set state is established and we revert back to the standard inputs S0 R0 the outputs remain in the set state That is In the set state the value Q 1 is stored as long as S0 R0 Now say that we set S0 R1 Then and Q 0 and Q 1 This is called the reset state Note that after the reset state is established and we revert back to the standard inputs S0 R0 the outputs remain in the reset state That is In the reset state the value Q 0 is stored as long as S0 R0 A similar circuit can be built with NAND gates S In this circuit S0 R1 sets Q1 Q 0 9 the set state The inputs then revert to the standard conditions of 81 R1 the circuit remains in the set state as long as we keep S1 R1 Q R S1 R0 sets Q0 Q 1 the reset state The inputs revert to 81 R1 and the circuit remains in the reset state as long as we keep S1 R1 Since this circuit sets and resets with inputs that are the complements of those used in the NOR gate SR latch this NAND circuit latch is usually called an S R Laz ch S C S Bubbles on R 3 inputs indicate c R o latch is S R Symbol for SR latch Symbol for SP latch o A latch can be supplied with an enable input that controls when the state can be set or reset Consider the circuit S Di L S Q EN enable R o Q39 3Y When EN0 The inputsXand Yinto the S R latch are both 1 meaning that the state QQ will not change no matter what we set as the values of S and R that is latch operation is disabled When EN1 Note that S1R0 produces X0Y1 which in the S R latch stage generates the set state Q1Q 0 S0R1 produces X1Y0 which in the S R latch stage generates the reset state Q0Q 1 and when S0R0 produces X1Y1 which maintains the latch in whatever state it is So this overall circuit acts like an SR latch when EN1 that is it is an SR latch with enable Note that there is one problem with an SR latch We cannot allow the inputs S1R1 when the latch is enabled Why S1R1EN1 gives X0Y0 which in turn produces Q1Q 1 which can t be true the state is actually indeterminate A simple way to make sure that we never go into this disallowed state is to modify the SR latch with enable into a D latch D m S Q EN l cR o Q39 W o In this circuit D1 generates the set state Q1 and D0 generates the reset state Q0 when EN1 that is when the latch is enabled it sets QD When EN0 the latch maintains whatever state it is in Block symbol for D latch D latch with enable D 2 Flipflops One problem with a latch is that states are set or reset by the level of the enable input for example in a D latch the circuit is able to be set or reset as long as EN1 This can cause difficulties when a circuit needs multiple bits of memory storage because outputs of some latches become inputs that is D lines of others Then if timing is not properly synchronized intended state changes in some latches can cause unintended changes in others Example Consider the connection of D latches shown below along with their enable pulses D latch X D latch D Q 39 EN 0 39 EN 0 Q EN2 EN1 I l EN1 Say thatA0 and thatX1 initially then Q is set to 1 when EN1 becomes 1 We want IEN2 to store this value But before EN1 goes to zero and saves the bit Q1 EN2 goes to 1 and Xis reset to 0 this in turn causes Q to be reset to 0 A flipflop is a memory storage device that is designed so that state transitions can only happen at the positive edge or negative edge of a clock pulse rather than during the whole time that the pulse is high This lets us synchronize the timing so that we don t have inadvertent state transitions Positive pulse edge gt I lt Negative pulse edge time gt Flipflops an be constructed from D latches and logic gates The most commonly used is the D flipflop which has the following implementation D latch Y D latch D master slave Q EN EN 0 Q 3 2 4 CLK 39 CLK clock 1 Circuit operation 1 During time 1 CLK0 the value YYOLD is stored at the master latch output and the slave latch output Q takes the value YYOLD 2 At time 2 the enable input into the slave latch transitions to 0 and the value QYOLD is saved 3 During time 3 CLK1 Ytakes the new value YNEWD while Q maintains the value YOLD 4 At time 4 the enable input into the slave latch transitions to 1 and Q takes the new value QYNEWD So in this flipflop The value of the flipflop output stored bit Q can change only on negative edges of the clock pulses Block symbol for D flipflop D flipflop The bubble indicates that the dynamic input acts on negative pulse edges 01gt CLK o The gt indicates a dynamic input this denotes that the flipflop acts only during clock transitions It is also possible to build a D flipflop that whose dynamic input is triggered by positive clock D flipflop transitions this has block symbol gt CLK No bubble indicates that dynamic input acts on positive pulse edges Positive edge triggered D flipflop Q o Q39 CLK The action of a flipflop is indicated by its characteristic equation and characteristic table The characteristic equation tells how the flipflop state after the next triggering clock transition denoted Qz 1 depends on the current input For a D flipflop the characteristic equation is Qt1 D This is also represented by the characteristic table D Qt1 O O reset 1 1 set D flipflops are most commonly used in practice because it is relatively simple to construct in CMOS However other types of flipflops can be developed T fiQfOQ Consider the Tflipflop Circuit D fli ro D p p gt CLK Characteristicequation Qt1 D T Qt TQz T Qt1 0 Qt 1 Qt Characteristic table JK fliQ og Now consider the JK flipflop circuit D flipflop gt CLK O Characteristic equation Qz 1 D JQz K Ql JKfIipflop characteristictable J K an o o W o 1 O reset 1 o 1 set 1 1 Qt Next week Analyze circuits that contain flipflops College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 2 Number Systems Decimal and Binary Number Systems Number representations make use of a base or radix A radixr system uses the r digits 0 1 r l Convention Let 01 02 be digits in the radixr set Then the radixr number 0K aKl 0100 3901 aIVI r T quotradix pointquot means 0K x rKaK1 x rK391 01 x r1 00 x r0 a1 x r391 0M x r39M We most commonly use decimal radix10 number representations so decimal digits are 0 1 9 But computer arithmetic is based on binary radix2 number representations so binary digits or bits are 0 1 Converting a binary representation to a decimal representation is easy for example 1001110012 1x24 1x21 1x20 1x2391 1x2394 162112116 19562510 How do we convert decimal to binary Shorthand for procedure 25 2 12 remainder 1 9 00 1 1226 remainder0 9 010 6 2 3 remainder O 9 02 O 321remainder1 9 031a41 So 2510 110012 v Now Find the binary representation for 3810 ans 1001102 For numbers that have both integer and fractional parts Convert the two parts separately then put together Now Find the binary representation to 6 fractional bits of 6310 ans 1100100112 Other Number Systems Sometimes it is convenient to represent numbers using bases other than 10 or 2 In particular large binary numbers are often converted to octal radix 8 using digits 0 1 2 7 or hexadecimal radix 16 using digits 0 1 9 A B C D E F where A digit for quot10 B digit for quot11 F digit for quot15 Since three bits can be used to represent 0 1 7 we can convert binary to octal just by grouping bits in sets of three starting from the radix point Similarly four bits can be used to represent 0 1 15 so to convert binary to hexadecimal we group bits in sets of four starting from the radix point Now Convert 282510 to octal and hexadecimal ans 3428 10416 II Binary Arithmetic Addition and multiplication of binary numbers is done in the same way as with decimal numbers except that we can only use binary digits Examples 111 4 Carries 10101 10111 101100 Check 101012 10510 101112 11510 105 11 510 221o 101102 I 10111 x 10101 10111 0 It s easiest to do 10111 the addition two 00 terms at a time 1011100 1110011 1011100 111100011 ChECC x 12075101111000112 u Now Find 1010112 100112 and 1010112 x 100112 ans 1010112 100112 11010012 1010112 x 100112 11001100012 Subtraction and Signed Binary Numbers Subtraction can be done using standard binary numbers but it is awkward to program Also if we want to allow for negative numbers we need some way to represent the sign or of a binary number Various ways of doing this are discussed in the textbook in Secs 15 and 16 We ll discuss the most commonlyused approach Signed2 s Complement representations Suppose we want to represent the positive integers 0 1 2 1 using n bits The nbit 2 scomplement representation for an integer N in this set is de ned to be the binary representation for the number 2 N The 2 s complement representation for 0 is de ned to be the binary representation for 0 Example Say we use 4 bits to represent the integers 0 1 15 Find the 4bit binary and 2 scomplement representations for 1410 n4 N14 2 N2 So binary representation is 1110 2 scomplement representation is 0010 Now suppose we need to represent the positive and negative integers in the set 2 391 2 391 1 1 O 1 2W 1 total of 2 digits This is most commonly done as follows we use the standard n bit binary representations for integers in the set 0 1 2 391 1 for negative integer N in the set 2 391 2 391 1 1 we use the nbit 2 scomplement representation for N Note that in this format All nonnegative integer representations have leftmost bit 0 while all negative integer representations have leftmost bit 1 so the leftmost bit is the sign bit This is called a signed 2 scompement representation Example Find the 4bit signed 2 scomplement representations of 610 and 410 610 0110 4bit 2 s complement representation of 410 4bit representation of 16 4 1210 11002 So 410 1100 Now Suppose have signed 2 scomplement numbersA and B A B is computed in exactly the same way as with standard binary numbers except there is no carry of the sign bit A B is computed as A 2 s complement of B again with no carry of the sign bit Example Say we are using 5bit signed 2 s complement representations Show the binary operations for i 510 39 710 5bit 2 scomplement for 710 5bit rep for 32710 2510 110012 So have 00101 11001 11110 5bit signed 2 s complement representation for 321684210 210 t ii 151o 3961o 610 is represented by the 2 scomplement of 610 5bit rep for 32 610 11010 So have 01111 11010 01001 no carry of sign bit 910 t Now Using 4bit signed 2 s complement representations calculate 510 39610 ans 1111 110 Now suppose have numbers represented in 5bit signed 2 s complement format Say that we add 00111 to some number B and the result is 11110 What is B ans B 10111 910