$conf['savedir'] = '/app/www/public/data'; notes:elen30010

Table of Contents

ELEN30010 - Digital Systems Design

, , ,

Overview

Digital Systems are used mainly to process signals

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

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]'<base (b=binary, d=decimal,o=octal, h=hexadecimal)><number>. 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 :<name>” 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

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.

????
0001
0000

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

  1. Write the number in binary
  2. Flip every bit (1's compliment)
  3. 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

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

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

  1. Think of the extremes of a FET
    • Electronic switch, either open or closed
  2. 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. 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.

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.

Should act like an electronic switch

FET vs BJT

BJT looks like a resistor. FET looks like a capacitor. FETs draw less current.