advertisement

Computer Components Combinational Logic Circuits CIT 595 Spring 2010 Computer components are made from both combinational and sequential logic circuits We will apply the knowledge of Boolean Algebra to realize these circuits First we will look at Combinational Logic Circuit CIT 595 Combinational Logic Circuits Always gives the same output for a given set of inputs Do not store any information (memoryless) Examples: adder, decoder, multiplexer (mux), shifter ■ These Th are combined bi d tto fform llarger units it such h as ALU CIT 595 2 1 Bit Addition Unit (Half Adder) This circuit is known as half adder ■ 3 CIT 595 Does half the job – does not account for carry-in input 4 1 1 Bit Addition Unit (Full Adder) 1 Bit Addition Unit (Full Adder) contd.. Sum = NOTE: Carry Out = CIT 595 5 CIT 595 1 Bit Full Adder Half Adder N-bit Adder Half Adder Just as we combined half adders to make a full adder, full adders can connected in series The carryy bit “ripples” pp from one full adder to the next; hence, this configuration is called a ripplecarry adder Two half adders make a full adder CIT 595 6 16-bit Ripple Carry Adder 7 CIT 595 C0 is assumed to be 0 8 2 Multiplexer 2-to-1 MUX A multiplexer sets its single output to the same value as one of its many inputs Selects between two inputs 0 x1 Output is determined by the value of the multiplexer’s control lines (a.k.a selector) To be able to select among n inputs, log2n control lines are needed x2 This is a block diagram for a multiplexer CIT 595 9 x1 x2 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 CIT 595 x1 x2 x2 CIT 595 10 Subtraction F(s,x1,x2) 0 x1 What is the logic behind selection? 2 to 1 MUX s 1 The adder logic circuit seen before does only addition Recall that X – Y = X + (-Y) ■ We find 1’s complement of Y and add 1 to get negative ti value l off Y ii.e. –Y Y ■ Then we add X and -Y 01101000 (104) 11110110 -00010000(16) -11110111 s’x1 ’ 1 + sx2 2 (-10) (-9) 01101000 (104) 11110110 (-10) +11110000(-16) +00001001 (9) 01011000 (88) 11111111 (-1) 11 CIT 595 12 3 Modification to the 1 Bit Adder (w/ Subtraction) Implementing Subtraction Logic in 1 Bit Adder Unit Let Y be the 2nd input We need both the Y and Y complement (Y’) To choose between addition and subtraction we will use a select signal “S” (we will learn later that S is actually generated by the control unit) ■ S = 0, then addition i.e. Y input is chosen ■ S = 1, then subtraction i.e. Y complement is chosen S y _ y 0 1 If subtraction then we need to add 1 to Y complement (Y’)) so as to get –Y (Y Y ■ +1 can be achieved by making the first carry C0 into the adder be 1 ■ Hence, C0 = S (this will allow both operations i.e. add/sub) CIT 595 13 CIT 595 14 Detecting Overflow Detecting Arithmetic Overflow Overflow is said to occur if result is too large to fit in the number of bits used in the representation Carry into MSB Carry Out 1 01000 ((8)) +01001 (9) + 0 10001 (-15) 11000 10111 1 01111 ( ) (-8) (-9) (+15) Circuit outputs 1 when the Carry into MSB (MCin) does not equal carry out (Cout) If you observe carefully, the output is equivalent to XOR gate Thus to detect overflow we XOR the values of Cout and MCin We have overflow if ■ Signs of both numbers are the same, and Sign of sum is different ■ If Positive number is subtracted from a Negative number number, result is positive and vice versa Overflow = Cn test (easy for hardware) Carry into MSB does not equal carry out CIT 595 Cout 15 MCin Overflow 0 0 0 0 1 1 1 0 1 1 1 0 In general general, for n n-bit bit adder Another ■ Cout CIT 595 + Cn-1 Cin into MSB 16 4 Bit Shifter Creating Logic for 2-bit Shifter Lets see the design of an unsigned 2-bit shifter O0 O1 S To determine 1-bit shift to left or right Assume th A thatt this thi d decided id d b by control t l variable/signal input called S ■ ■ Inputs If S = 0, then we do 1 bit left shift Else, we do 1 bit right shift Lets say the input is 2-bit value D(D1, D0) where D1 is the most significant bit(MSB) Lets call the output of the shift be O(O1, O0) CIT 595 17 D1 D0 O1 O0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 O1 = 0 S D1D0 00 01 11 10 0 0 0 0 0 1 0 0 1 1 O0 = SD1 Logic circuit diagram 18 Decoder Similarly, we can make 4-bit shifter that moves the bits of a nibble (half of a byte) one position to the left or right CIT 595 00 01 11 10 0 0 1 1 0 CIT 595 4-Bit Bit Shifter Outputs S D1D0 19 Decoders are circuits used to decode encoded information A binary decoder converts binary information from n-bit input code to a maximum of 2n unique outputs ■ Decoder logic uses n-bit input value to chose exactly one of the 2n outputs (only a particular output is active) ■ Example: Memory Address Decoding CIT 595 20 5 Address Decoder Example 2-to-4 Decoder Logic A binary Read/ Write n-bit Address Decoder 2n locations number with 2 bits as its input Selects exactly 1 of 4 outputs At any time, only 1 output line is “ON'' or “1” and all others are “OFF” or “0” (referred to as one-hot encoded) Memory Array (2n x m) m bits (data) Decoder will select only 1 memory location (row) based on address 1 – active/asserted/chosen CIT 595 21 CIT 595 Opposite of decoder Given information is transformed into more compact form Example: ■ ■ In Interrupt Driven I/O - need to determine higher priority among devices who interrupted at the same time Priority encoder circuit determines which interrupt request should be serviced by the processor ¾ ¾ CIT 595 22 Resolving Interrupts Encoder 0 – not active/deasserted/not chosen In priority encoder each input has a priority level associated with it The encoder outputs indicate active input that has the highest priority 23 CIT 595 24 6 Example: 4:2 Priority Encoder Code Converters x3 has highest priority ■ x2 the next highest…x0 has lowest priority y1y0 are outputs determine the which request goes to processor for servicing Inputs Outputs x3 x2 x1 x0 y1 y0 1 x x x 1 1 0 1 x x 1 0 0 0 1 x 0 1 0 0 0 1 0 0 0 0 0 0 x x In general encoders and decoders are known as code converters Convert from one type of coded information (encoding) to another output encoding Example: BCD to 7 segment display (calculators and digital number displays etc) ■ ■ X – don’t care CIT 595 25 Binary-Coded Binary Coded Decimal (BCD) is an encoding for decimal numbers in which each digit is represented by its own binary sequence. see “Handout” on code converters CIT 595 26 Enabling/Gating Outputs 2-Bit ALU Combinational logic circuits produce an output based on certain inputs f0 and f1 control lines (generated by control unit) We may not want to use its output all the time The value of control lines determine dete e which c ope operation: at o ■ ■ Same inputs are shared amongst different logic units Some how we only want to make one unit active and disable all others Hence we want some sort of control to temporarily disable the circuit and only enable it if the control is set ■ ■ ■ ■ Who decides value of EN? Basic gates allow us to achieve this: ■ ■ CIT 595 AND gate - Figure a. EN = 1, F = X OR gate - Figure b. ~EN = 0, F = X 00 – A + B (Addition) 01 – NOT A 10 – A OR B 11 – A AND B Similarly a N-Bit ALU can be made All sub units form their operation, but final output is chosen only if enabled (EN = 1). Here EN is decided by the decoder logic. Example on the next slide 27 CIT 595 28 7 2-Bit ALU 8-bit ALU made from eight “bit slices” Cin CIT 595 29 CIT 595 Propagation/Gate Delay Bit slices allow designers to build an ALU of any desired bit capacity Carry out of each bit slice connects to carry in of next (more significant bit) slice F0 and d F1 (d (decoder d iinputs) t ) connectt simultaneously i lt l tto all slices so that the identical operation is selected in all slices at a given time There is a single input to the least significant slice i.e. carry-in (Cin) input Efficient Design E.g. Carry Look Ahead Recap ■ Si = Ai ^ Bi ^ Ci ¾ Si = Pi ^ Ci where Pi = Ai ^ Bi ■ Ci+1 = Ci (Ai ^ Bi) + AiBi ¾ Ci+1 = Ci Pi + Gi where Gi = AiBi The levels of gate for digital can add to more delay E.g. in Ripple Carry adder, the carry bit has to propagate through, end to end Gi is called carry generate and it produces a carry of 1 when both Ai and Bi are 1 regardless of the carry in Ci Pi is called carry propagate and is associated with propagation of Ci to Ci+1 ■ The addition will carry whenever there is an input carry, but will not carry if there is no input carry The length of time starting from when the input to a logic gate becomes stable and valid, to the time that the output of that logic gate is stable and valid. ■ ¾ ¾ ¾ CIT 595 30 Assume one gate has a propagation delay of x units Carry passes through 2 gate levels per adder Total carry propagation time for n-bit adder = 2*n*x units 31 CIT 595 32 8 Carry Look Ahead Programmable Logic Array (PLA) A digit of addition will carry: Note that carry C1, C2, C3 are calculated at the same time A PLA is a prepackaged circuit that can be tailored to suit various needs Any truth table can be represented by some AND gates feeding into an OR gate ■ CIT 595 Source: Digital Design 3rd Ed Morris mano 33 # of AND gates determines how many truth table rows can have 1’s in them over all the functions implemented CIT 595 FPGAs Typically has small number of inputs and one output > 20K gates Contains Look Up Table (LUT) which contains storage cells used to implement a small logic function Contains ■ ■ ■ I/O blocks Logic blocks for implementing required q functions Interconnection (contain wires & programmable switches so as allow logic blocks to interconnected in many ways) CIT 595 34 FPGA logic block Field Programmable Gate Arrays Used to implement larger circuit i it ■ Sum Of Product form 35 CIT 595 36 9 Hardware Descriptive Languages E.g. Verilog code Language to describe the circuit's operation, its design and organization, and tests to verify its operation by means of simulation 2-input (32-bit) mux A simulation program, designed to implement the underlying semantics of the language statements, coupled with simulating the progress of time provides the hardware designer with the ability to model a piece of hardware before it is created physically parameter word_size = 32 output [word_size – 1: 0] mux_out; input [word_size – 1: 0] data_1, data_0; Input select; module Mux_2_32(mux_out, data_1, data 0 select); data_0, assign mux_out = select ? data_1: data_0; ??? module circuit_1 (q, a, b) output q; i input t a, b b; always@(a or b) begin if(a == 1’b1) q = b; else q=1 1’b0; b0; end endmodule endmodule CIT 595 37 CIT 595 38 10