WIXLIB

CSE140L: Components and DesignTechniques for Digital Systems LabFSMsTajana Simunic RosingSource: Vahid, Katz1

Hardware Description Languagesand Sequential Logic Flip-flops– representation of clocks - timing of state changes– asynchronous vs. synchronous FSMs– structural view (FFs separate from combinational logic)– behavioral view (synthesis of sequencers – not in this course) Datapath data computation (e.g., ALUs, comparators) registers– use of arithmetic/logical operators– control of storage elements

FSM design example – Moore vs. Mealy Remove one 1 from every string of 1s on the 0]10/01/0one1[0]1/1

Verilog FSM - Reduce 1s example Moore machinemodule reduce (clk, reset, in, out);input clk, reset, in;output out;state assignment(easy to change,if in one place)parameter zero 2’b00;parameter one1 2’b01;parameter two1s 2’b10;reg out;reg [2:1] state;reg [2:1] next state;zero[0]1// state variablesalways @(posedge clk)if (reset) state zero;elsestate next state;000one1[0]1two1s[1]1

Moore Verilog FSM (cont’d)always @(in or state)case (state)zero:// last input was a zerobeginif (in) next state one1;elsenext state zero;endone1:// we've seen one 1beginif (in) next state two1s;elsenext state zero;endtwo1s:// we've seen at least 2 onesbeginif (in) next state two1s;elsenext state zero;endendcasecrucial to includeall signals that areinput to state determinationnote that outputdepends only on statealways @(state)case (state)zero: out 0;one1: out 0;two1s: out 1;endcaseendmodule

Mealy Verilog FSMmodule reduce (clk, reset, in, out);input clk, reset, in;output out;reg out;reg state; // state variablesreg next state;always @(posedge clk)if (reset) state zero;elsestate next state;always @(in or state)case (state)zero:// last input was a zerobeginout 0;if (in) next state one;elsenext state zero;endone:// we've seen one 1if (in) beginnext state one; out 1;end else beginnext state zero; out 0;endendcaseendmodulezero[0]0/00/01/0one1[0]1/1

Synchronous Mealy Machinemodule reduce (clk, reset, in, out);input clk, reset, in;output out;reg out;reg state; // state variablesalways @(posedge clk)if (reset) state zero;elsecase (state)zero:// last input was a zerobeginout 0;if (in) state one;elsestate zero;endone:// we've seen one 1if (in) beginstate one; out 1;end else beginstate zero; out 0;endendcaseendmodule

Example: Traffic light controller Highway/farm road intersectionfarm roadcar sensorshighway

Traffic light controller (cont.) Detectors C sense the presence of cars waiting on the farm road– with no car on farm road, light remain green in highway direction– if vehicle on farm road, highway lights go from Green to Yellow to Red, allowingthe farm road lights to become green– these stay green only as long as a farm road car is detected but never longer thana set interval; after the interval expires, farm lights transition from Green to Yellowto Red, allowing highway to return to green– even if farm road vehicles are waiting, highway gets at least a set interval of green Assume you have an interval timer that generates:––––a short time pulse (TS) anda long time pulse (TL),in response to a set (ST) signal.TS is to be used for timing yellow lights and TL for green lights

Traffic light controller (cont.) inputsresetCTSTLdescriptionplace FSM in initial statedetect vehicle on the farm roadshort time interval expiredlong time interval expired stateHGHYFGFYdescriptionhighway green (farm road red)highway yellow (farm road red)farm road green (highway red)farm road yellow (highway red)outputsHG, HY, HRFG, FY, FRSTdescriptionassert green/yellow/red highway lightsassert green/yellow/red highway lightsstart timing a short or long intervalReset(TL C)'HGTL C / STTS'TS / STHYFYTS / STFGTS'TL C' / ST(TL C')'

Traffic light controller (cont.) Generate state table with symbolic states Consider state assignmentsoutput encoding – similar problemto state assignment(Green 00, Yellow 01, Red ––SA1:SA2:SA3:TS–––01–––01Present StateHGHGHGHYHYFGFGFGFYFYHG 00HG 00HG 0001Next StateHGHGHYHYFGFGFYFYFYHGHY 01HY 10HY 0010FG 11FG 01FG 0100OutputsST RedFY 10FY 11FY e-hot)

Traffic light controller FSM Specification of inputs, outputs, and state elementsmodule FSM(HR, HY, HG, FR, FY, FG, ST, TS, TL, C, reset, Clk);outputHR;outputHY;outputHG;parameter highwaygreenoutputFR;parameter highwayyellowoutputFY;parameter farmroadgreenoutputFG;parameter farmroadyellowoutputST;inputTS;inputTL;assign HR state[6];inputC;assign HY state[5];inputreset;assign HG state[4];inputClk;assign FR state[3];assign FY state[2];reg [6:1] state;assign FG state[1];regST;specify state bits and codesfor each state as well asconnections to outputs 6'b001100;6'b010100;6'b100001;6'b100010;

Traffic light controller FSMinitial begin state highwaygreen; ST 0; endalways @(posedge Clk)case statementbegintriggerred byif (reset)clock edgebegin state highwaygreen; ST 1; endelsebeginST 0;case (state)highwaygreen:if (TL & C) begin state highwayyellow; ST 1; endhighwayyellow:if (TS) begin state farmroadgreen; ST 1; endfarmroadgreen:if (TL !C) begin state farmroadyellow; ST 1; endfarmroadyellow:if (TS) begin state highwaygreen; ST 1; endendcaseendendendmodule

Timer FSM for traffic light controllermodule Timer(TS, TL, ST, Clk);output TS;output TL;inputST;inputClk;integervalue;assign TS (value 4); // 5 cycles after resetassign TL (value 14); // 15 cycles after resetalways @(posedge ST) value 0; // async resetalways @(posedge Clk) value value 1;endmodule

Complete traffic light controller Tying it all together (FSM timer) with structural Verilog (same as aschematic drawing)module main(HR, HY, HG, FR, FY, FG, reset, C, Clk);output HR, HY, HG, FR, FY, FG;input reset, C, Clk;Timer part1(TS, TL, ST, Clk);FSMpart2(HR, HY, HG, FR, FY, FG, ST, TS, TL, C, reset, Clk);endmoduletraffic lightcontrollerSTTS TLtimer

Finite state machines summary Models for representing sequential circuits––––abstraction of sequential elementsfinite state machines and their state diagramsinputs/outputsMealy, Moore, and synchronous Mealy machines Finite state machine design procedure––––deriving state diagramderiving state transition tabledetermining next state and output functionsimplementing combinational logic Hardware description languages– Use good coding style– Communicating FSMs

CSE140L: Components and DesignTechniques for Digital Systems LabProgrammable Logic DevicesTajana Simunic RosingSource: Vahid, Katz, Culler17

Evolution of Programmable Technologies Discrete devices: relays, transistors (1940s-50s)Discrete logic gates (1950s-60s)Integrated circuits (1960s-70s)– Map circuit to Data Book parts– e.g. TTL packages: Data Book for 100’s of different parts trend towardhigher levelsof integrationGate Arrays (IBM 1970s)––––––“Custom” integrated circuit chipsTransistors are already on the chipPlace and route software puts the chip together automatically Large circuits on a chip Automatic design tools (no tedious custom layout)- Only good if you want 1000’s of parts

Programmable Logic Technologies Fuse and anti-fuse–––– Fuse makes or breaks link between two wiresTypical connections are 50-300 ohmOne-time programmable (testing before programming?)Very high densityEPROM and EEPROM– High power consumption– Typical connections are 2K-4K ohm– Fairly high density RAM-based––––Memory bit controls a switch that connects/disconnects two wiresTypical connections are .5K-1K ohmCan be programmed and re-programmed in the circuitLow density

Comparing RAM Register fileREGISTER FILE– Fastest– But biggest sizeOUT1OUT2R SD QR SD QOUT3R SD QOUT4R SD QCLKIN1 IN2SRAM– Fast (e.g. 10ns)– More compact than register fileData'IN3SRAMIN4DataW DRAM– Slowest (e.g. 20ns)DRAM And refreshing takes time– But very compact– Different technology for large caps.DataW20

ROM Types1data line0data linecell Mask-programmed ROM– Programmed at manufacturing timewordenableFuse-Based Programmable ROM1– Programming blows fuses– One-Time Programmable ROM EPROM– Erase with ultraviolet light celldata line1celldata linecellwordenableEEPROMfuseblown fuse Flash– Erase large blocks of words simultaneouslyfloating-gatetransistor– Erasing one word at a time electronicallywordenabledata linedata linecellcell10eÐeÐtrapped electrons21

Memory in Verilog Modeled as an array of registers22Source: John Wawrzynek

Programmable Logic Devices (PLD) PLDs combine PLA/PAL with memory and other advancedstructures– Similar to PLA/PAL, hence Field-Programmable Gate Arrays Types:––––Antifuse PLDsEPLD & EEPLDFPGAs with RAMsFPGA with processing Digital Signal Processing General purpose CPU23

Field-Programmable Gate Arrays Logic blocks– To implement combinationaland sequential logic Interconnect– Wires to connect inputs andoutputs to logic blocks I/O blocks– Special logic blocks atperiphery of device forexternal connections Key questions:– How to make logic blocks programmable?– How to connect the wires?– After the chip has been manufactured

Antifuse PLDs Actel’s Axcelerator Family Antifuse:– open when not programmed– Low resistance when programmed25

Actel’s Axcelerator C-Cell C-Cell– Basic multiplexer logic plusmore inputs and support for fastcarry calculation– Carry connections are “direct”and do not require propagationthrough the programmableinterconnect

Actel’s Accelerator R-Cell R-Cell– Core is D flip-flop– Muxes for altering the clock andselecting an input– Feed back path for current valueof the flip-flop for simple hold– Direct connection from one C-celloutput of logic module to an R-cellinput; Eliminates need to use theprogrammable interconnect Interconnection Fabric– Partitioned wires– Special long wires

Altera’s Erasable Programmable Logic Devices (EPLDs) Historical Perspective– PALs: same technology as programmed once bipolar PROM– EPLDs: CMOS erasable programmable ROM (EPROM) erased by UV light Altera building block MACROCELLCLK8 Product TermAND-OR Array ProgrammableMUX'sClkMUXANDARRAYOutputMUXQI/O PinInv ertControlF/BMUXProgrammable polaritypadSeq. LogicBlockProgrammable feedback

Altera EPLD: Synchronous vs. Asynchronous ModeAltera EPLDs contain 10s-100s of independently programmed macrocellsGlobalCLKPersonalizedby EPROMbits:ClkMUXSynchronous Mode1Flipflop controlledby global clock signalOE/Local CLKQEPROMCellGlobalCLKClkMUXlocal signal computesoutput enableAsynchronous Mode1OE/Local CLKQFlipflop controlledby locally generatedclock signalEPROMCell Seq Logic: could be D, T positive or negative edge triggered product term to implement clear function

Altera Multiple Array Matrix (MAX)AND-OR structures are relatively limitedCannot share signals/product terms among macrocellsLogicArrayBlocks(similar tomacrocells)LAB ALAB HLAB BLAB CLAB DLAB GPIALAB FLAB EGlobal Routing:ProgrammableInterconnectArrayEPM5128:8 Fixed Inputs52 I/O Pins8 LABs16 Macrocells/LAB32 Expanders/LAB

Altera’s EEPLD Altera’s MAX 7k Block Diagram31

EEPLD Altera’s MAX 7k Logic Block32

SRAM based PLD Altera’s Flex 10k Block Diagram33

SRAM based PLD Altera’s Flex 10k Logic Array Block (LAB)34

SRAM based PLD Altera’s Flex 10k Logic Element (LE)35

FPGA with DSP Altera’s Stratix II: Block Diagram36

FPGA with DSP Altera’s Stratix II:– DSP Detail37

FPGA with General Purpose CPU & Analog Actel’s Fusion Family Diagram– FPGA with ARM 7 CPU and Analog Components38

Programmable Logic Summary Discrete GatesPackaged LogicPLAsEver more general architectures of programmable combinational sequential logic and interconnect– Altera– Actel– Xilinx

Traffic light controller (cont.) Detectors C sense the presence of cars waiting on the farm road – with no car on farm road, light remain green in highway direction – if vehicle on farm road, highway lights go from Green to Yel