$conf['savedir'] = '/app/www/public/data'; ======= ELEN30010 - Digital Systems Design ======= {{tag>notes unimelb code electrical_engineering}} ====== Overview ====== Digital Systems are used mainly to process signals * Audio and Visual processing * Computer games and robotics * Nuclear Spectroscopy Signals often start as analogue. Analogue signals are affected by noise, digital signals are not. C implementations are generic but slow. Using Verilog, code can be implemented in hardware. Field Programmable Gate Array (FPGA) can be used to build digital circuits once configured. FPGAs are generic, so they are slower than custom silicon. They can be useful for prototyping. This course is about * Processing sequences of numbers * implementing what we want to do to the numbers in hardware * Anything digital can be made using logic gates and flip-flops * FPGAs are useful for implementing circuits ===== Digital Logic ===== Logic is 1s and 0s. A CPU can be made from logic gates and flip-flops. To be good at digital design, we need to understand logic gates, flip-flops and design principles. ==== How are Logic gates made ==== Logic gates are made using transistors. FETs are the current "best" type of transistor. Use low voltage (OFF) as 0 and high (ON) as 1. A NAND gate can be built using 4 transistors, two in parallel from source for each input and two in series shorting the output to ground. ==== Programming FPGAs ==== Can use Schematic entry but has problems === Hardware Description Language === Verilog and VHDL exist, Verilog is more concise than VHDL. Faster than schematic entry. ====== Verilog ====== ===== Introduction ===== Create an and gate: module MyAND(input A,B, output C); assign C = A & B; endmodule A four input and gate using a tree: module Fred(input A,B,C,D, output E); wire F,G; MyAND G1(.A(A),.B(B),.C(F)); MyAND G2(.A(C),.B(D),.C(G)); MyAND G3(.A(F),.B(G),.C(E)); endmodule ===== Verilog details ===== Verilog is concurrent, order does not matter. Default integer size is 32 bits. Specify number as [size]'. Numbers are truncated with least significant bits taking priority. ''initial'' block is simulator instruction. Have to name blocks which have variables which are declared. Naming is "begin :" reg size carries over commas unless size is redefined. ===== Combinational and Sequential ===== Combinational (time-independent) logic is only dependent on inputs. Sequential logic is dependent on past inputs as well as current. ===== Wire vs reg ===== Wire is a junction, has input and outputs. Assign and wire go together. Outputs of an instantiated module connect to wires. Inputs of a module are wires. Reg has an assigned value (can change). RULE OF THUMB: make everything a wire. Assignment with out ''assign'' statement must be a reg. ===== Simulation period ===== ''$display(x)'' statement prints out the current value of x. ''$strobe(x)'' statement prints out the final value of x. Regs can be reassigned many times within the same time period. module main; reg [7:0]x; initial begin x=1; $display("Display 1. x=%d at time %d.",x,$time); $strobe("Strobe 1. x=%d at time %d.",x,$time); x=2; $display("Display 2. x=%d at time %d.",x,$time); $strobe("Strobe 2. x=%d at time %d.",x,$time); #1 x=3; $display("Display 3. x=%d at time %d.",x,$time); $strobe("Strobe 3. x=%d at time %d.",x,$time); x=4; $display("Display 4. x=%d at time %d.",x,$time); $strobe("Strobe 4. x=%d at time %d.",x,$time); end // initial begin endmodule // main ''$strobe'' statements won't trigger until ''#1'';. ''$monitor'' statements are like ''$strobe''; except it will update every time a watched value is changed before a break. i.e. x=2; #1 x=2; would only trigger it once. ===== Bit values ===== Bits can have 4 values * 0 * 1 * x (don't know) * z (high impedance (floating)) Can't synthesise x values. Need to explicitly initialise values. ===== Numbers ===== Numbers are represented by the way they are initialised. wire [3:0]number1; wire [0:3]number2; number 1's most significant digit is 3, and 2's is 0. Can have signed numbers by using the signed keyword. ==== 2's compliment ==== Allows adders to work the same with negative and positive numbers. Means that \(-1\) must be constructed such that \((-1)+1=0\), and \((-2)+2=0\), etc. |?|?|?|?| |0|0|0|1| |0|0|0|0| Need to find the ? number. In this circumstance \(1111\) works, so is \(-1\). The carry, being 1 is overflowed as it is too large for our number to store. If we continue with this, \(1110\) is \(-2\), \(1101\) is \(-3\) and etc. Made such that if the MSB is 1, the number is negative. To make a number negative in 2's compliment - Write the number in binary - Flip every bit (1's compliment) - Add 1 (2's compliment) Doing the same thing turns a negative number to a positive. ====== Basic FPGA Architecture ====== Exact details vary in many ways. Can be divided into basic units called Logic Elements (or Logic Cells, or Configurable Logic Blocks). Logic Elements are often grouped into blocks called Logic Array Blocks. (Typically 10 LEs in a LAB) LABs can be connected through programmable interconnects. Typically a LE will contain a Lookup Table (LUT) and a Flip-flop (FF). Since an arbitrary combinational circuit can be implemented using only NAND gates, and a LUT can be used to implement a NAND gate, a LUT can be used to create any combinational circuit. ====== Flip-flops ====== Only looking at D-type flip-flops code: module basicFF(input d,clk, output reg q,qbar); always @(posedge clk) begin q <= d; // non-blocking assignment qbar <= !d; end endmodule // basicFF The flip-flop takes a photograph of the data line (d) and stores the value on the q line. q is the same until there is a rising edge of the clock. A reg could be synthesised as a flip-flop. ===== Counter ===== module Counter(input clk, output reg [7:0] cnt); always @(posedge clk) cnt <= cnt+1; endmodule // Counter A simple counter is an example of a finite state machine. Has input feeding into transition logic with the current state. Transition logic feeds into state memory and then into output logic then to output. ===== Cascaded Flip-flops ===== Can be used as a synchroniser or a shift-register. ''<='' in Verilog introduces an assignment to the process queue so shifts work. ====== Models ====== Models are only approximations to the real world. By increasing the accuracy of the model, you increase the computational cost. ===== Transport delay ===== Shifts the input signal by a fixed amount. Accounts for signals not travelling faster than the speed of light. Implementation in Verilog: must use non-blocking assignment, with stated delay on the right of the number to be assigned. module TransportDelay(input in, output reg out); always @(in) out <= #1 in; endmodule // TransportDelay ===== Transient Behaviour ===== Real gates have delays, introduces transient behaviour and steady state behaviour. Truth table only accounts for steady-state behaviour. Transient behaviour can be difficult to predict and cause out design to fail. Can be overcome by interspersing flip-flops in between combinational logic parts to eliminate glitches if the clock is slow enough. Possible due to the low cost of flip-flops. ====== Clocks ====== Square wave generator. All flip-flops will be driven by the same clock. Clocks determine the meaning of symbols, e.g. 110011 or 101. ===== Crossing clock domains ===== Happens when you have two clocks that are out of sync. Signals from each will be out of alignment from each other. ==== Two types of problems ==== * Cannot align sequences * Receiver doesn't know when to sample * Protocol issue, can be fixed with a robust protocol for transmitting and receiving data * Flip-flops can misbehave if the input changes too near to a rising edge of a clock, creates meta-stability * Engineering issue, use of a synchroniser to reduce the chance of a meta-stable state from entering the main circuit * Can cause the whole design to fail as it can propagate through the rest of the circuit === Alignment === Need a "signalling mechanism" so the receiver knows when to sample. Can use a shared clock, but we often don't want the receiver to run off the same clock. Sometimes a new value isn't sent every cycle, e.g. a temperature sensor. Also humans do not like sharing clocks with hardware. Assuming the receiver's clock speed is much faster than the data rate, i.e. the input changes slowly compared to its clock. The input signal will be sampled many times by the receiver, so if the input signal has a "ready" wire, the input can be sampled once while the input is "ready". Otherwise there is a double flip-flop synchroniser. The input signal is put into an initial d flip-flop, which may enter a meta-stable state, and hopefully the state will resolve by the time a second flip-flop receives input. As the probability of staying in a meta-stable state decreases exponentially with time, it is likely that the second flip-flop will have a stable signal that can be sent into the circuit. Can't eliminate the probability of a meta-stable state, but can reduce the probability to practically 0. If the data stays constant for a while, a double flip-flop synchroniser can be used for the ready signal. The clock period must be at most half as much as the shortest pulse period. Multiple bits can't be synchronised in parallel, as if all the bits become meta-stable, the message could become any given message, due to the random collapse of bits. This can be partially overcome by restricting what a message could be based on past messages. A FIFO Synchroniser can be used to synchronise multiple bits more reliably. ====== Finite state machines (FSM) ====== 2 types, Mealy (general) and Moore (specific). A Mealy FSM can depend on both the current state and the current input. A Moore FSM depends only on the current state. Can convert a Mealy to a Moore. Equivalent state diagrams can be rearranged to be the same. Non-equivalent state diagrams can have the same external behaviour but cannot be made to resemble each other. ===== Writing a FSM ===== We will implement this FSM. {{ example_fsm.jpg?200}} ==== Test bench ==== Start with a test bench, allows testing while writing. module test; reg clk, in; // work out what the inputs are wire out; MyFSM fsm(.clk(clk), .w(in), .z(out)); initial begin clk=0; forever #1 clk=!clk; end initial begin $monitor($time,,in,,out); in=0; #2 in=1; #6 in=0; #4 in=1; #8 in=0; #8 in=1; #10 in=0; #10 in=1; #12 $stop; end endmodule // test ==== Map states to binary values ==== n flip-flops can represent 2n binary states. Assign a unique number to each state. A FSM will work regardless of the encoding. Good practice is to write the states in Verilog. module MyFSM(input clk, in, output z); localparam A=4'b0, B=4'b1, C=4'b2, D=4'b3. E=4'b4, F=4'b5, G=4'b6, H=4'b7, I=4'b8; endmodule // MyFSM ''localparam''; is the equivalent of ''const int''. Equivalent of ''#define'' is ''`define'', however localparam is safer. ==== Flip-flops for storing states ==== reg [3:0] state = A; reg [3:0] next_state; always @(posedge clk) state <= next_state; ==== Output logic ==== assign z = (state == E) || (state == I); ==== Transition logic ==== Will always work with a case, but other ways may be faster. Is combinational. always @(*) case (state) A: next_state = w ? F : B; B: next_state = w ? F : C; C: next_state = w ? F : D; D: next_state = w ? F : E; E: next_state = w ? F : E; F: next_state = w ? G : B; G: next_state = w ? H : B; H: next_state = w ? I : B; I: next_state = w ? I : B; default: next_state = A; endcase // case (state) ==== A less algorithmic approach ==== By thinking about what the FSM does, we can change the code from the algorithmic approach to something simpler. module MyFSM2(input clk, w, output z); reg [3:0] sr0 = 4'b1111; // used to detect 0000 reg [3:0] sr1 = 4'b0000; // used to detect 1111 always @(posedge clk) begin sr0 <= {sr0[2:0],w}; sr1 <= {sr1[2:0],w}; end assign z = (sr0 == 4'b0000) || (sr1 == 4'b1111); endmodule // MyFSM2 This is equivalent to the above but doesn't follow the above model in its implementation. The state here is 8 bits instead of 4. Allows for easy transition logic. ===== State Encoding ===== One way to encode states is to use 0, 1, 2, 3, ... Another choice is to use one-hot encoding, where a unique wire represents a state. Each state has a wire, and only one wire can be a 1 at a time. Inefficient in terms of flip-flops used, but allows for faster run-time and more efficient transition logic. Changing the state encoding can change the cost of the design and the fastest speed it can run at. ====== Characterisation of logic gate behaviour ====== ===== Contamination Delay ===== The gate can't react immediately. The contamination delay is the minimum period of time for a combinational logic circuit's output to change. The output will not change before the contamination delay period. ===== Propagation delay ===== The maximum amount of time for a combinational logic circuit's output to change. The output is known to be stable after the propagation delay has passed, but the output is unknown between the contamination and propagation delays. ===== Bounds ===== There is no problem, other than extra time, of reducing the contamination delay and increasing the propagation delay. There is a problem with increasing the contamination delay and reducing the propagation delay. As such these bounds are approximate. Glitches can occur within this bounds, so the clock period needs to be longer to account for the glitches. ===== Flip-flops ===== Flip-flops have both delays and timing requirements. They have both a contamination and propagation delay. The timing delays are taken from the rising edge of the clock. Flip-flops also have a setup time and hold time. A flip-flop is guaranteed not to become meta-stable if the input is not changed within the interval \((\text{rising edge})-(\text{setup time})\) to \((\text{rising edge})+(\text{hold time})\) If a flip-flop becomes meta-stable, its state can collapse due to thermal noise. The probability that it remains meta-stable is constant for a given time, hence its probability of remaining metastable decreases geometrically with time. ====== Transistors and logic gates ====== Logic gates use Field Effect Transistors (FETs), due to their speed and efficiency. They have 4 pins, one for the substrate that is often ignored, a gate, source and drain that are commonly used. Gate-to-Source voltage determines whether the channel is open or closed. Source-to-Drain voltage is the channel through which current flows. A logic gate designed with FETs will always be "inverting", i.e. NOT, NAND, NOR, ... Steps to design a logic gate - Think of the extremes of a FET * Electronic switch, either open or closed - Design the bottom half first * Imagine a pull-up resistor on top ===== NAND gate example ===== Once designed for the bottom half using a pull up resistor. {{ nand_gate.png?100}} Trying to design from this to the top half. Need the top half to be open when the bottom is closed, and vice versa. If both are closed, there is a short circuit. If both are open, there is a floating output. {{ cmos_nand.png?100}} ===== Power consumption and delays ===== Digital electronics are analogue, deal with real voltages. Has large analogue characteristics, esp at high speeds. **Digital Abstraction** is useful to simplify design, thinking in terms of 0 and 1, infinitely fast rise times, etc. ===== Ideal FET (for digital logic) ===== Its input should draw no current. * \(C=0,L=0,R=\infty\) Should act like an electronic switch * Off \(\implies R=\infty\) * On \(\implies R=0\) ==== FET vs BJT ==== BJT looks like a resistor. FET looks like a capacitor. FETs draw less current.