© P.Prinetto - all rights reserved Version 1.1 5.1.15.1 – RT level combinational blocksECE 465RT level combinational blocksPaolo PRINETTOPolitecnico di Torino (Italy)University of Illinois at Chicago, IL (USA)[email protected]@uic.eduwww.testgroup.polito.itLecture 5.125.1 Goal• This lecture presents the set of functional blocks that are usually considered to be “elementary” or “basic” at the RT level.35.1 Prerequisites• Lecture 3.345.1 Homework• No particular homework is foreseen55.1 Further readings• Students interested in making a reference to a text book on the arguments covered in this lecture can refer, for instance, to:− M. Morris Mano, C.R.Kime: “Logic and Computer Design Fundamentals,” 2nd edition updatedPrentice Hall, Upple Saddle River, NJ (USA), 2001, (chapter 3, pp. 111-148 )65.1 Elementary functional blocksMultiplexerAdder-SubtracterDecoderEncoderComparatorROMALUMultiplier1’s counterI/O interfaces© P.Prinetto - all rights reserved Version 1.1 5.1.25.1 – RT level combinational blocksECE 46575.1 AddersWe shall consider:• half adder• full adder• n-bits adders− Ripple carry adders− Carry look-ahead adders• Adder-subtracter85.1 Half-AdderA half-adder has:• 2 inputs Ai, Bi• 2 outputs Siand Ci+1and computes the binary sum of the 2 input bits, providing:• the sum Si• the carry Ci+195.1 Si = Ai ⊕ BiCi+1 = Ai ⋅ BiAiBiCi+1Si105.1 Full-AdderA full-adder has:• 3 inputs Ai, Biand Ci• 2 outputs Siand Ci+1and computes the binary sum of the 3 input bits, providing:• the sum Si• the carry Ci+1115.1 Si= Ai ⊕ Bi ⊕ CiCi+1= Ai Bi + AiCi+ BiCi = = Ai Bi + ( Ai ⊕ Bi )CiΣAiBiCiCi+1Si125.1 AiBiCi+1SiAiBiCi+1SiAlternative implementation© P.Prinetto - all rights reserved Version 1.1 5.1.35.1 – RT level combinational blocksECE 465135.1 ΣA[n-1:0] B[n-1:0] S[n-1:0] CnC0n-bit adder145.1 n-bit adderAn n-bit adder can be implemented resorting to n full-adders, connected according to two alterna-tive architectures:• ripple carry• look-ahead carry.155.1 Ripple carry adderThe implementation in based on the algorithm used when an addition is performed manually by paper and pencil:the carry input Ciof each cell is fed by the carry output Ci-1 of the adjacent less significant cell. 165.1 Ripple carry adderFA FA FAA0B0An-2Bn-2An-1Bn-1S0Sn-2Sn-1C0Cn…175.1 DelaysThe global delay of the adder is:n ⋅∆FAbeing ∆FAthe delay of each full-adder cell.185.1 Look-ahead carry adderA look-ahead carry adder is a faster, but more expensive, implementation.Each cell generates 2 outputs:Pi= Ai ⊕ Bi: propagation functionGi= Ai ⋅ Bi: generation function.© P.Prinetto - all rights reserved Version 1.1 5.1.45.1 – RT level combinational blocksECE 465195.1 The output of the i-th cell can be expressed as:Si= Ai ⊕ Bi ⊕ Ci= Pi ⊕ CiCi+1= Ai Bi + ( Ai ⊕ Bi )Ci=Gi+ Pi CiLook-ahead carry adder (cont’d)205.1 The output of the i-th cell can be expressed as:Si= Ai ⊕ Bi ⊕ Ci= Pi ⊕ CiCi+1= Ai Bi + ( Ai ⊕ Bi )Ci=Gi+ PiCi Carry signals are evaluated as follows: C1= G0 + P0 C0C2= G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0C3= G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1P0 C0…Look-ahead carry adder (cont’d)215.1 The output of the i-th cell can be expressed as:Si= Pi ⊕ CiCi+1=Gi + Pi CiCarry signals are evaluated as follows: C1= G0 + P0 C0C2= G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0C3= G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1P0 C0…Look-ahead carry adder (cont’d)All carry signals depend on A and B signals, only, and can be easily generated by a combinational 2 level circuit (carry look-ahead generator)225.1 P0S0A0B0P0 G0A1B1P1 G1A2B2P2 G2A3B3P3 G3P1S1P2S2P3S3C3C2C1C0C0C4Look-Ahead Carry Generator4-bit look-ahead carry adder235.1 The overflow signal OVFL is generated differently, according whether the internal carry signals are accessible, or not.Overflow signal generation245.1 The overflow signal OVFL is generated differently, according whether the internal carry signals are accessible, or not.Overflow signal generationOVFL = [ A(n-1)= B(n-1)] and [ A(n-1)≠ S(n-1)] = A(n-1)B(n-1)S(n-1)’ + A(n-1)’ B(n-1)’ S(n-1)© P.Prinetto - all rights reserved Version 1.1 5.1.55.1 – RT level combinational blocksECE 465255.1 The overflow signal OVFL is generated differently, according whether the internal carry signals are accessible, or not.Overflow signal generationOVFL = C(n-1)⊕ C(n-2)265.1 Adder-subtracterAn adder-subtracter is a combinational block capable of adding/subtracting two n-bits inputs operands, detecting overflow conditions. It has• 2 n-bits data inputs, both labeled from n-1 to 0• 1 control input to select one of the two operations • 1 n-bits data output• 1 control output asserted when an overflow condition is occurred.275.1 Adder-subtracter (cont’d)FUNC(n-1 downto 0)A(n-1 downto 0)B(n-1 downto 0)ADD/~SUBOVFLSymbol285.1 Elementary functional blocksAdder-SubtracterDecoderEncoderComparatorROMALUMultiplier1’s counterI/O interfacesMultiplexer295.1 MultiplexerA multiplexer is a combinational block capable of forcing its output to the current value of one of its inputs, according to the values of some control signals.Each input can be either a single wire or a bus.305.1 MultiplexerA multiplexer has:• 2kdata inputs, labeled from 2k-1 to 0• k control inputs• 1 data output.k2k-1 2k-2 2 1 0MUX…It gets the value present on the input labeled 2 i, wherei (0 ≤ i ≤ k-1) is the binary number present on the control inputs.© P.Prinetto - all rights reserved Version 1.1 5.1.65.1 – RT level combinational blocksECE 465315.1 OUTSEL(k-1 downto 0)Multiplexer (cont'd)SymbolIN(2k-1 downto 0)325.1 Multiplexer (cont’d)SymbolM0(n-1 downto 0)OUT(n-1 downto 0)M1(n-1 downto 0)M2(n-1 downto 0)M2k-1(n-1 downto 0)SEL(k-1 downto 0)335.1 Elementary functional blocksMultiplexerAdder-SubtracterDecoderEncoderComparatorROMALUMultiplier1’s counterI/O interfaces345.1 DecoderA decoder k →2k has:• 1 n-bit data input• 2 noutputs, labeled from 0 to 2 n-1• 1 enable.When enabled, just the output labeled 2jis active, where j is the value present on the data input.When disabled, no output is active.355.1 Decoder (cont’d)SymbolDOUT(0)DIN(n-1 downto 0)ENABLEDOUT(1)DOUT(2)DOUT(2n-1)365.1 Elementary functional blocksMultiplexerAdder-SubtracterDecoderEncoderComparatorROMALUMultiplier1’s counterI/O interfaces© P.Prinetto - all rights reserved