Unformatted text preview:

COMP 411 Computer Organization Memories and State Machines Don Porter Lecture 13 1 COMP 411 Computer Organization Topics Memory Arrays Transparent Latches Edge Triggered Registers Finite State Machines Read Only Memory a Lookup Table COMP 411 Computer Organization A B MUX Logic Read Only Memory ROM Fn A B AB Fn A B 00 01 10 11 0 1 1 0 A multiplexer can implement a lookup table for an N input function we need a 2N input multiplexer simply select one row out of 2N 2N values go into the mux only one comes out N bit select input is now the address of data being accessed Limitations mux can get really big 10 bit address 1024 rows read only we also would like to write COMP 411 Computer Organization A Mux s Guts Decoder Selector Selector A decoder generates all possible product terms for a set of inputs 0 1 Decoder A B A B A B A B 2 3 I 00 I 01 I 10 I 11 Multiplexers can be partitioned into two sections Y A DECODER that identifies the desired input and a SELECTOR that enables that input onto the output Hmmm by sharing the decoder part of the logic MUXs could be adapted to make lookup tables with any number of outputs COMP 411 Computer Organization Decoder DECODER k SELECT inputs N 2k DATA OUTPUTs Selected Dj HIGH all others LOW D1D2 DN k NOW we are well on our way to building a general purpose table lookup device We can build a 2 dimensional ARRAY of decoders and selectors as follows COMP 411 Computer Organization Shared Decoding Logic We can build a general purpose table lookup device called a Read Only Memory ROM from which we can implement any truth table and thus any combinational device COMP 411 Computer Organization Logic According to ROMs Different ROM implementation technologies Mask old ROM read only memory Fuses old PROM Erasable EPROM Electrically erasable EEPROM programmable read only memory erasable programmable read only memory electrically erasable programmable read only memory today called FLASH Used everywhere Model LOOK UP value of function in truth table Inputs ADDRESS of a truth table entry ROM SIZE truth table entries 2N x outputs for an N input boolean function size COMP 411 Computer Organization Read Write Memories RAM Read Write often called random access memories RAM Dynamic RAM uses analog storage word line bit line encode information using voltages from physics we can store a voltage as charge on a capacitor Pros Cons compact it leaks refresh complex interface reading a bit destroys it you have to rewrite the value after each read it s NOT a digital circuit N transistor serves as an access switch VREF To write Drive bit line turn on access transistor force storage cap to new voltage To read precharge bit line turn on access trans detect small change in bit line voltage This storage circuit is the basis for commodity DRAMs COMP 411 Computer Organization Static RAM A Digital Storage Element It s also easy to build a DIGITAL storage element called a latch using a MUX and FEEDBACK Here s a feedback path so it s no longer a combinational circuit state signal appears as both input and output A D B S G 0 1 Y Q G 0 0 1 1 D 0 1 QIN 0 1 QOUT 0 1 0 1 Q stable Q follows D COMP 411 Computer Organization Static D Latch D Q G Positive latch Q follows D D G Q Q stable D Q G Negative latch 1 0 Q D G static means latch will hold data i e value of Q while G is inactive however long that may be COMP 411 Computer Organization Latch Timing Circuits with memory must follow some rules when they may influence state changes This is assured with additional timing specifications tPULSE Guarantee that inputs to sequential devices are valid and stable during periods G D tSETUP tHOLD tPULSE minimum pulse width guarantee G is active for long enough for latch to capture data tSETUP setup time guarantee that D value has propagated through feedback path before latch becomes opaque tHOLD hold time guarantee latch is opaque and Q is stable before allowing D to change again COMP 411 Computer Organization Effects of transparency Toll Booth Analogy 12 COMP 411 Computer Organization Flakey Control Systems Here s a strategy for saving 2 bucks the next time you find yourself at a toll booth COMP 411 Computer Organization Flakey Control Systems Here s a strategy for saving 2 bucks the next time you find yourself at a toll booth COMP 411 Computer Organization Flakey Control Systems Here s a strategy for saving 2 bucks the next time you find yourself at a toll booth WARNING DON T try this At home COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time COMP 411 Computer Organization Escapement Strategy The Solution Add two gates and only open one at a time Key Idea At no time is there an open path through both gates COMP 411 Computer Organization D Flip Flop Edge Triggered Flip Flop Q D Q Q D D Q L1 G D Q L2 G D CLK CLK Logical escapement Observations Double gated toll booth built using logic gates only one latch transparent at any time L1 opaque when L2 is transparent CLK is high L2 opaque when L1


View Full Document

UNC-Chapel Hill COMP 411 - Memories and State Machines

Download Memories and State Machines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memories and State Machines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memories and State Machines and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?