EECS 150 - Components and Design Techniques for Digital Systems Lec 07 – PLAs and FSMs 9/21-04Review: minimum sum-of-products expression from a Karnaugh mapBig Idea: boolean functions <> gatesOutlineHow to quickly implement SofPs?One Answer: Xilinx 4000 CLBTwo 4-input functions, registered output5-input function, combinational outputProgrammable LogicProgrammable Logic Arrays (PLAs)Shared Product TermsBefore ProgrammingAfter ProgrammingAlternate Representation for High Fan-in StructuresProgrammable Logic Array ExamplePLAs Design ExamplePLAs Design Example (cont’d)PLAs Design Example (revisited)Slide 19PLA Second Design ExampleOther OptionsAnnouncementsRecall: What makes Digital Systems tick?Recall 61C: Single-Cycle MIPSRecall 61C: 5-cycle Datapath - pipelineTypical Controller: stateTypical Controller: state + outputTypical Controller: state + output + inputTwo Kinds of FSMsParity Checker ExampleFormal Design ProcessFormal Design ProcessSlide 33Finite State Machines (FSMs)FSM ImplementationAnother exampleImplementation in softwareImplementation as a sequential digital systemSequential example: abstract controldata-path vs. controlSequential example (cont’d): finite-state machineSlide 42Sequential example: encodingSequential example (cont’d): encodingSequential example (cont’d): controller implementationOne-hot encoded FSMFSM Implementation NotesDesign hierarchy9/21/04EECS150 F04 Culler1EECS 150 - Components and Design Techniques for Digital Systems Lec 07 – PLAs and FSMs9/21-04 David CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp://www-inst.eecs.berkeley.edu/~cs1509/21/04EECS150 F04 Culler2Review: minimum sum-of-products expression from a Karnaugh map•Step 1: choose an element of the ON-set•Step 2: find "maximal" groupings of 1s and Xs adjacent to that element–consider top/bottom row, left/right column, and corner adjacencies–this forms prime implicants (number of elements always a power of 2)•Repeat Steps 1 and 2 to find all prime implicants•Step 3: revisit the 1s in the K-map–if covered by single prime implicant, it is essential, and participates in final cover–1s covered by essential prime implicant do not need to be revisited•Step 4: if there remain 1s not covered by essential prime implicants–select the smallest number of prime implicants that cover the remaining 1s9/21/04EECS150 F04 Culler3Big Idea: boolean functions <> gates•22^n boolean functions of n inputs–Each represented uniquely by a Truth Table–Describes the mapping of inputs to outputs•Each boolean function represented by many boolean expressions–Axioms establish equivalence–Transform expressions to optimize•Each boolean expression has many implementations in logic gates–Canonical: Sum of Products, Product of Sums–Minimal–K-maps as a systematic means of reducing Sum of Products•Any acyclic network of gates implements a boolean function9/21/04EECS150 F04 Culler4Outline•Programmable Logic to Implement Sum of Products•Designing with PLAs•Announcements•FSM Concept•Example: history sensitive computation•Example: Combo lock•Encodings and implementations9/21/04EECS150 F04 Culler5How to quickly implement SofPs?9/21/04EECS150 F04 Culler6One Answer: Xilinx 4000 CLB9/21/04EECS150 F04 Culler7Two 4-input functions, registered output9/21/04EECS150 F04 Culler85-input function, combinational output9/21/04EECS150 F04 Culler9Programmable Logic•Regular logic–Programmable Logic Arrays–Multiplexers/Decoders–ROMs•Field Programmable Gate Arrays (FPGAs)–Xilinx9/21/04EECS150 F04 Culler10• • •inputsANDarray• • •outputsORarrayproducttermsProgrammable Logic Arrays (PLAs)•Pre-fabricated building block of many AND/OR gates–Actually NOR or NAND–”Personalized" by making or breaking connections among gates–Programmable array block diagram for sum of products form9/21/04EECS150 F04 Culler11example:F0 = A + B' C'F1 = A C' + A BF2 = B' C' + A BF3 = B' C + Apersonality matrix1 = uncomplemented in term0 = complemented in term– = does not participate1 = term connected to output0 = no connection to outputinput side:output side:product inputs outputsterm A B C F0 F1 F2 F3AB 1 1 – 0 1 1 0B'C – 0 1 0 0 0 1AC' 1 – 0 0 1 0 0B'C' – 0 0 1 0 1 0A 1 – – 1 0 0 1reuse of termsShared Product Terms9/21/04EECS150 F04 Culler12Before Programming•All possible connections available before "programming"–In reality, all AND and OR gates are NANDs9/21/04EECS150 F04 Culler13AB CF1 F2 F3F0ABB'CAC'B'C'AAfter Programming•Unwanted connections are "blown"–Fuse (normally connected, break unwanted ones)–Anti-fuse (normally disconnected, make wanted connections)9/21/04EECS150 F04 Culler14notation for implementingF0 = A B + A' B'F1 = C D' + C' DAB+A'B'CD'+C'DABA'B'CD'C'DA B C DAlternate Representation for High Fan-in Structures•Short-hand notation--don't have to draw all the wires–Signifies a connection is present and perpendicular signal is an input to gate9/21/04EECS150 F04 Culler15A B C F1 F2 F3 F4 F5 F60 0 0 0 0 1 1 0 00 0 1 0 1 0 1 1 10 1 0 0 1 0 1 1 10 1 1 0 1 0 1 0 01 0 0 0 1 0 1 1 11 0 1 0 1 0 1 0 01 1 0 0 1 0 1 0 01 1 1 1 1 0 0 1 1A'B'C'A'B'CA'BC'A'BCAB'C'AB'CABC'ABCA B CF1 F2 F3 F4 F5F6full decoder as for memory addressbits stored in memoryProgrammable Logic Array Example•Multiple functions of A, B, C–F1 = A B C–F2 = A + B + C–F3 = A' B' C'–F4 = A' + B' + C'–F5 = A xor B xor C–F6 = A xnor B xnor C9/21/04EECS150 F04 Culler160 1 X 00 1 X 0 0 0 X X0 0 X X DABCminimized functions:W = A + B D + B CX = B C'Y = B + CZ = A'B'C'D + B C D + A D' + B' C D'A B C D W X Y Z0 0 0 0 0 0 0 00 0 0 1 0 0 0 10 0 1 0 0 0 1 10 0 1 1 0 0 1 00 1 0 0 0 1 1 00 1 0 1 1 1 1 00 1 1 0 1 0 1 00 1 1 1 1 0 1 11 0 0 0 1 0 0 11 0 0 1 1 0 0 01 0 1 – – – – –1 1 – – – – – –0 0 X 10 1 X 1 0 1 X X0 1 X X DABCK-map for W K-map for X0 1 X 00 1 X 0 1 1 X X1 1 X X DABCK-map for YPLAs Design Example•BCD to Gray code converterK-map for Z0 0 X 11 0 X 0 0 1 X X1 0 X X DABC9/21/04EECS150 F04 Culler17not a particularly goodcandidate for PLAimplementation since no terms are shared among outputshowever, much more compact and regular implementation when compared with discrete AND and OR gatesA B C DW X Y
View Full Document
Unlocking...