advertisement

Lecture 2-3: Digital Circuits & Components (1) Logic Gates (2) Boolean Algebra (6) Registers Parallel Load Shift Register Counter (3) Logic Simplification (4) Combinatorial Circuits Adder Decoder Encoder Multiplexers (5) Flip-Flops SR Flip-Flop JK Flip-Flop D Flip-Flop T Flip-Flop (7) Sequential Circuits Input Equations State Tables (8) Memory Random-Access Read-Only Logic Gates Transmission Gates & Switches Gate Implementations Using Switches Logic Gates Gate-Level Components Gate-Level Components Name Symbol VHDL Equation Truth Table AND A B X X <= A and B A 0 0 1 1 B 0 1 0 1 X 0 0 0 1 OR A B X X <= A or B A 0 0 1 1 B 0 1 0 1 X 0 1 1 1 NOT A X X <= not A A X 0 1 1 0 Composite Gates Name Symbol VHDL Equation Truth Table NAND A B X X <= not (A and B) A 0 0 1 1 B 0 1 0 1 X 1 1 1 0 NOR A B X X <= not (A or B) A 0 0 1 1 B 0 1 0 1 X 1 0 0 0 X <= A xor B A 0 0 1 1 B 0 1 0 1 X 0 1 1 0 XOR A B X Boolean Algebra Functional Operators Axiomatic Definitions Other Identities Logic Simplification Two basic methods: Boolean Algebra Complicated Accident Prone Only way when the number of variables > 5 Karnaugh Map Graphical - Pictorial Simple when the number of variables <= 5 Map Simplification B A 0 0 (A,B) =0 1 (A,B) =2 1 (A,B) =1 (A,B) =3 BC A 00 0 (A,B,C) =0 1 (A,B,C) =4 01 11 (A,B,C) =1 (A,B,C) =5 CD 00 AB 00 (A,B,C,D) =0 01 (A,B,C,D) =4 (A,B,C,D) 11 = 12 (A,B,C,D) 10 = 8 10 (A,B,C) =3 (A,B,C) =7 01 (A,B,C,D) =1 (A,B,C,D) =5 (A,B,C,D) = 13 (A,B,C,D) =9 (A,B,C) =2 (A,B,C) =6 11 (A,B,C,D) =3 (A,B,C,D) =7 (A,B,C,D) = 15 (A,B,C,D) = 11 10 (A,B,C,D) =2 (A,B,C,D) =6 (A,B,C,D) = 14 (A,B,C,D) = 10 Map Simplification Example A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 X 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 => X = sum(1,2,3,6,7,9,10,11,12,15) CD 00 AB 00 01 11 10 01 11 10 Circuit Types Combinatorial Circuit Example- Half-adder Half-adder has no Carry-in input Function table: A 0 0 1 1 B 0 1 0 1 Sum 0 1 1 0 Logic diagram: A B Carry-out 0 0 0 1 VHDL Code: Sum Carry-out HALF_ADDER: process (A,B) begin Sum <= A xor B; Carry_out <= A and B; end process HALF_ADDER; Combinatorial Circuit Example- Full-adder Full-adder has a Carry-in input Function table: Carry-in 0 0 0 0 1 1 1 1 A 0 0 1 1 0 0 1 1 B 0 1 0 1 0 1 0 1 Sum 0 1 1 0 1 0 0 1 Carry-out 0 0 0 1 0 1 1 1 Combinatorial Circuit Example- Full-adder Logic diagram: A B CI Sum Carry-out VHDL Code: FULL_ADDER: process (A,B) begin Sum <= A xor B xor Carry-in; Carry_out <= (A and B) or ((A xor B) and Carry_in); end process FULL_ADDER; Combinatorial Circuit Example- Decoder n inputs and 2n outputs Function table: I2 0 0 0 0 1 1 1 1 I1 0 0 1 1 0 0 1 1 I0 0 1 0 1 0 1 0 1 Y7 0 0 0 0 0 0 0 1 Y6 0 0 0 0 0 0 1 0 Y5 0 0 0 0 0 1 0 0 Y4 0 0 0 0 1 0 0 0 Y3 0 0 0 1 0 0 0 0 Y2 0 0 1 0 0 0 0 0 Y1 0 1 0 0 0 0 0 0 Y0 1 0 0 0 0 0 0 0 Combinatorial Circuit Example- Decoder VHDL Code: DECODER : process ( I(2 downto 0) ) begin Y(7 downto 0) <= others => ‘0’; case ( I(2 downto 0) ) is when “000” => Y(0) <= ‘1’; when “001” => Y(1) <= ‘1’; when “010” => Y(2) <= ‘1’; when “011” => Y(3) <= ‘1’; when “100” => Y(4) <= ‘1’; when “101” => Y(5) <= ‘1’; when “110” => Y(6) <= ‘1’; when “111” => Y(7) <= ‘1’; end case; end process DECODER; Combinatorial Circuit Example- Encoder Combinatorial Circuit Example- Encoder VHDL Code: ENCODER : process ( I(7 downto 0) ) begin case ( I(7 downto 0) ) is when “00000001” => Y <= “000”; when “00000010” => Y <= “001”; when “00000100” => Y <= “010”; when “00001000” => Y <= “011”; when “00010000” => Y <= “100”; when “00100000” => Y <= “101”; when “01000000” => Y <= “110”; when “10000000” => Y <= “111”; end case; end process ENCODER; Combinatorial Circuit Example- Multiplexer Combinatorial Circuit Example- Multiplexer VHDL Code: MULTIPLEXER : process ( S(1 downto 0) ) begin case ( S(2 downto 0) ) is when “00” => Y <= I(0); when “01” => Y <= I(1); when “10” => Y <= I(2); when “11” => Y <= I(3); end case; end process MULTIPLEXER; Flip-Flops Flip-flops are the most basic of sequential (clocked) circuits Inputs are only considered valid during a clock edge transition ==> Inputs must be held stable during the transition (called setup and hold interval) Outputs only change after a clock edge transition ==> Outputs change after an interval called the clock-to-output time Flip-Flop Types - SR SR flip-flops have two inputs, set and reset, that act as follows: Truth Table (set dominant): S R C x x 0 x x 1 1 x 0 1 Q Q_last Q_last 1 0 Truth Table (reset dominant): S R C x x 0 x x 1 1 0 x 1 Q Q_last Q_last 1 0 Flip-Flop Types - SR Symbolic representation: S R C Q VHDL code (set dominant): SR_FF : process (C) begin if (C’event and (C = ‘1’)) then if (S = ‘1’) then Q <= ‘1’; elsif (R = ‘1’) then Q <= ‘0’; else Q <= Q_last; end if; end if; end process SR_FF; Q_last <= Q; Flip-Flop Types - JK JK flip-flops have two inputs, that act as follows: Truth Table: J x x 0 0 1 1 K x x 0 1 0 1 C 0 1 Q Q_last Q_last Q_last 0 1 /Q_last Flip-Flop Types - JK Symbolic representation: J K C Q VHDL code: JK_FF : process (C) begin if (C’event and (C = ‘1’)) then if ((J = ‘0’) and (K = ‘0’)) then Q <= Q_last; elsif ((J = ‘1’) and (K = ‘0’)) then Q <= ‘1’; elsif ((J = ‘0’) and (K = ‘1’)) then Q <= ‘0’; else Q <= not Q_last; end if; end if; end process JK_FF; Q_last <= Q; Flip-Flop Types - D D flip-flops have one input, data, that act as follows: Truth Table: D x x 0 1 C 0 1 Q Q_last Q_last 0 1 Flip-Flop Types - D Symbolic representation: D C Q VHDL code: D_FF : process (C) begin if (C’event and (C = ‘1’)) then Q <= D; end if; end process D_FF; Flip-Flop Types - T T flip-flops have one input, toggle, that act as follows: Truth Table: T x x 0 1 C 0 1 Q Q_last Q_last Q_last / Q_last Flip-Flop Types - T Symbolic representation: T C Q VHDL code: T_FF : process (C) begin if (C’event and (C = ‘1’)) then if (T = ‘1’) then Q <= not Q_last; else Q <= Q_last; end if; end process T_FF; Q_last <= Q; Registers Groups of D-type flip-flops, with each FF holding 1 bit of information ==> A 32-bit register would require 32 FF’s to implement Registers can be loaded: In parallel -- all bits at once In serial -- one bit at a time, from either end Registers are used to: Temporarily store information for arithmetic operations Implement control functions -- sets, resets, enables, etc. Report status -- overflows, error conditions, etc. Implement interrupts Registers- Parallel Load Symbolic representation: D(n-1..0) Q(n-1..0) LOAD C Truth table: LOAD x x 0 1 C 0 1 Q Q_last Q_last Q_last D VHDL code: REGISTER : process (C) begin if (C’event and (C = ‘1’)) then if (LOAD = ‘1’) then Q <= D; else Q <= Q_last; end if; end process REGISTER; Q_last <= Q; Registers- Serial Load (Shift) Symbolic representation: D Q(n-1..0) SHIFT C Truth table: SHIFT x x 0 1 C 0 1 Q(0) Q_last(0) Q_last(0) Q_last(0) D Q(n-1..1) Q_last(n-1..1) Q_last(n-1..1) Q_last(n-1..1) Q_last(n-2..0) Registers- Serial Load (Shift) VHDL code (8-bit register, for example): REGISTER : process (C) begin if (C’event and (C = ‘1’)) then if (SHIFT = ‘1’) then Q (7 downto 1) <= Q_last (6 downto 0); Q (0) <= D; else Q <= Q_last; end if; end process REGISTER; Q_last <= Q; Counters A counter is a register capable of incrementing or decrementing its contents Q <= Q plus n Q <= Q minus n The definition of "plus" and "minus" depend on the way the register contents encode the integers Binary Counters: Encode the integers with the binary number code Counters - Example: 3-bit Binary Up Counter Truth Table: CNT C x 0 x 1 0 1 1 1 1 State Diagram: Symbolic Representation Q_last xxx xxx xxx 000 ... 110 111 Q Q_last Q_last Q_last Q_last+1 Q_last+1 Q_last+1 000 CNT CNT 001 010 000 CNT 011 CNT CNT 111 CNT 100 110 101 CNT CNT Q(2..0) CNT C Counters - Example: 3-bit Binary Up Counter Truth Table: CNT C x 0 x 1 0 1 1 1 1 State Diagram: Q_last xxx xxx xxx 000 ... 110 111 Q Q_last Q_last Q_last Q_last+1 Q_last+1 Q_last+1 000 CNT CNT 001 010 000 CNT 011 CNT CNT 111 CNT 100 110 101 CNT CNT Counter Design: Bit Q(0) Toggles on every CNT = 1 Bit Q(1) Toggles on every CNT = 1 and Q(0) = 1 Bit Q(2) Toggles on every CNT = 1 and Q(0) = 1 Q(1) = 1 Counters - Example: 3-bit Binary Up Counter Logic Diagram (one design): CNT T T T Q Q Q C This is called series (or ripple) carry logic Q(0) Logic Diagram (another design): CNT T Q Q(1) T Q Q(2) T Q C This is called parallel (or look-ahead) carry logic Q(0) Q(1) Q(2) Counters - Example: 3-bit Binary Up Counter VHDL Code: COUNTER : process (C) begin if (C’event = (C = ‘1’)) then if (CNT = ‘1’) then if (Q_last = “111”) then Q <= “000”; else Q <= Q_last + ‘1’; end if; end if; end if; end process COUNTER; Q_last <= Q; Does this make ripple or look-ahead carry logic? Sequential Circuits A sequential circuit which satisfies the following conditions: There is at least one flip-flop in every loop All flip-flops have the same type of dynamic clock All clock inputs of all the flip-flops are driven by the same clock signal. Is called a synchronous sequential circuit Sequential Circuits Any synchronous sequential circuit can be drawn in Canonical form by pulling the flip-flops to the bottom of the figure (think of the lines as elastic). Since all loops have a flip-flop in them, this will leave the remaining circuit without loops, and hence combinational. Outputs Combinatorial Logic Inputs C Combinatorial Logic D Q State This is called a Moore state machine outputs depend only on current state Sequential Circuits Another way to design a state machine is a follows: Outputs Combinatorial Logic Inputs C Combinatorial Logic D Q State This is called a Mealy state machine outputs depend on current state and inputs Sequential Circuit Descriptions Structural Logic diagram Excitation Equations Logical equations for the flip-flop inputs as a function of current flip-flop states and circuit input signals Output equations Logical equations for circuit outputs as a function of current flip-flop states and circuit inputs signals Sequential Circuit Descriptions Behavioral Transition and output equations Logical equations for next flip-flop states and circuit outputs in terms of current flip-flop states and circuit input signals Transition table Two-dimensional truth table of transition and output equations State table Transition table with the states given descriptive names State diagram (graph) A graph with nodes corresponding to states and directed edges corresponding to state transistions Sequential Circuit Description- Example Problem: Build a 2-bit binary up/down counter, with the following I/O: UP in : increment the count DN in : decrement Q(1..0) out : count State diagram: VHDL Code: Sequential Circuit Description- Example Transition Table: UP DN Q State Table: Q_next UP DN Q Q_next Sequential Circuit Description- Example Excitation Equation Q(1): Excitation Equation Q(0): Q_next(1) = Q_next(0) = Q(1..0) UP DN Q(1..0) 00 01 11 10 UP DN 00 00 01 01 11 11 10 10 00 01 11 10 Sequential Circuit Timing The following global timing parameters are important to the reliable working of a sequential circuit: Global Setup and Hold: The window around any FF’s clock edge during which its input must be valid Global Clock-to-out: The amount of time that it takes to get a signal, from the input clock, out of a circuit. Maximum Clock Frequency: The fastest a global clock can be run within a design. Maximum Clock Skew: The greatest difference between when a clock hits two different FF’s clock inputs Global Setup,Hold,&Propagation Delay Consider the following circuit: tPNI D_ext Combinatorial Logic Delay D_int CLK_ext Clock Tree Network Delay CLK_int tPC D Q Q_int Output Net Q_ext Delay tPNO tPFF Global Setup,Hold,&Propagation Delay Consider the following timing diagram: CLK_ext tSU_E tHD_E tSU_E = tSU_I + tPNI - tPC D_ext tPNI tPC tHD_E = tHD_I - tPNI + tPC CLK_int tSU_I tHD_I D_int tPFF Q_int tPNO Q_ext tP tP = tPC + tPFF + tPNO Maximum Clock Frequency The maximum clock frequency, minimum clock width, is determined by the time required for changes at one flip-flop output to be seen at another flip-flop input. Consider the following circuit: tPFF D1 D Q tPN Q1 Combinatorial D2 Logic Delay Skew Between C1 Clocks C1 tSKEW D Q Q2 Maximum Clock Frequency Consider the following timing diagram: tPER C1 tSKEW tSKEW C2 tPER = tPFF + tPN + tSU + tSKEW tPFF Q1 tPN tSU D2 Note the skewing C1 after C2 is the worst case. If the skew had delayed C2 after C1, it would have increased the maximum clock frequency. Maximum Clock Skew Consider the same circuit as above: tPFF D1 D Q tPN Q1 Combinatorial D2 Logic Delay Skew Between C1 Clocks C1 tSKEW D Q Q2 Maximum Clock Skew Consider the same timing diagram as above: C1 tSKEW tHD tSKEW = tPFF + tPN - tHD C2 tPFF Q1 tPN D2 Note the skewing C2 after C1 is the worst case. If the skew had delayed C1 after C2, it would have increased the maximum clock skew allowed. Introduction to Memory Memory Hierarchy Technology Random Access: “Random” is good: access time is the same for all locations DRAM: Dynamic Random Access Memory High density, low power, cheap, slow Dynamic: need to be “refreshed” regularly SRAM: Static Random Access Memory Low density, high power, expensive, fast Static: content will last “forever”(until lose power) “Non-so-random” Access Technology: Access time varies from location to location and from time to time Examples: Disk, CDROM Sequential Access Technology: access time linear in location (e.g.,Tape) Introduction to Memory Performance of Main Memory: Latency: Cache Miss Penalty Access Time: time between request and word arrives Cycle Time: time between requests Bandwidth: I/O & Large Block Miss Penalty (L2) Main Memory is DRAM: Dynamic Random Access Memory Dynamic since needs to be refreshed periodically (8 ms) Addresses divided into 2 halves (Memory as a 2D matrix): RAS: Row Access Strobe CAS: Column Access Strobe Cache uses SRAM: Static Random Access Memory No refresh (6 transistors/bit vs. 1 transistorSize: DRAM/SRAM 4-8, Cost/Cycle time: SRAM/DRAM 8-16 Introduction to Memory Why do computer designers need to know about RAM technology? Processor performance is usually limited by memory bandwidth As IC densities increase, lots of memory will fit on processor chip Tailor on-chip memory to specific needs Instruction cache Data cache Write buffer What makes RAM different from a bunch of flip-flops? Density: RAM is much more denser Logic Diagram of a Typical SRAM A N WE_L OE_L 2 N words x M bit SRAM M D Write Enable is usually active low (WE_L) Din and Dout are combined to save pins: A new control signal, output enable (OE_L) is needed WE_L is asserted (Low), OE_L is disasserted (High) D serves as the data input pin WE_L is disasserted (High), OE_L is asserted (Low) D is the data output pin Both WE_L and OE_L are asserted: Result is unknown. Don’t do that!!! Timing of a Typical SRAM A N WE_L 2 N words x M bit SRAM OE_L M Write Timing: D Data In D Read Timing: High Z Data Out Data Out Junk A Write Address Read Address Read Address OE_L WE_L Write Hold Time Write Setup Time Read Access Time Read Access Time Logic Diagram of a Typical DRAM RAS_L A 9 CAS_L WE_L 256K x 8 DRAM OE_L 8 D Control Signals (RAS_L, CAS_L, WE_L, OE_L) are all active low Din and Dout are combined (D): WE_L is asserted (Low), OE_L is disasserted (High) D serves as the data input pin WE_L is disasserted (High), OE_L is asserted (Low) D is the data output pin Row and column addresses share the same pins (A) RAS_L goes low: Pins A are latched in as row address CAS_L goes low: Pins A are latched in as column address RAS/CAS edge-sensitive Timing of a Typical DRAM Write Every DRAM access begins at: The assertion of the RAS_L 2 ways to write: early or late v. CAS RAS_L A CAS_L WE_L 256K x 8 DRAM 9 OE_L D 8 DRAM WR Cycle Time RAS_L CAS_L A Row Address Col Address Junk Row Address Col Address Junk OE_L WE_L D Junk Data In WR Access Time Early Wr Cycle: WE_L asserted before CAS_L Junk Data In Junk WR Access Time Late Wr Cycle: WE_L asserted after CAS_L Timing of a Typical DRAM Read Every DRAM access begins at: The assertion of the RAS_L 2 ways to read: early or late v. CAS RAS_L CAS_L A WE_L 256K x 8 DRAM 9 OE_L D 8 DRAM Read Cycle Time RAS_L CAS_L A Row Address Col Address Junk Row Address Col Address Junk WE_L OE_L D High Z Junk Data Out Read Access Time Early Read Cycle: OE_L asserted before CAS_L High Z Data Out Output Enable Delay Late Read Cycle: OE_L asserted after CAS_L Motivation for Fast Page Mode DRAM Column Address N cols DRAM N rows Regular DRAM Organization: N rows x N column x M-bit Read & Write M-bit at a time Each M-bit access requires a RAS / CAS cycle Fast Page Mode DRAM N x M “register” to save a row Row Address M-bit Output 1st M-bit Access M bits 2nd M-bit Access RAS_L CAS_L A Row Address Col Address Junk Row Address Col Address Junk Operation of Fast Page Mode DRAM N cols DRAM Row Address N rows Fast Page Mode DRAM N x M “SRAM” to save a row After a row is read into the register Only CAS is needed to access other M-bit blocks on that row RAS_L remains asserted while CAS_L is toggled Column Address N x M “SRAM” M-bit Output 1st M-bit Access 2nd M-bit 3rd M-bit M bits 4th M-bit RAS_L CAS_L A Row Address Col Address Col Address Col Address Col Address Logic Families Design Considerations Programmable Logic Things have changed . . .