Figure 4-1 Serial Adder With Accumulator
Figure 4-1 Serial Adder with AccumulatorAccumulatorN (Start Signal)ControlCircuitShSIShSIShxix 3 x2 x 1 x 0sum iy 3 y2 y 1 y 0ci 1ciAddend RegisterClockFullAdderyiQDQ' CKSerial AdderShClockXt0t1t2t3t4Ycisumi ci 101010101 01110010 1011010001 11011111000 11101101100 01110(1)(0)
Figure 4-2 Control State Graph and Table for Serial Adder0/0N/Sh–/1S0S31/1S1–/1–/1S2Present Next StateState N 0 N 1S0 S0 S1S1 S2 S2S2 S3 S3S3 S0 S0Present Output (Sh)N 0 N 101111111
Constraints on Input Labels for Every State Sk (From Page 123-124)1. If Ii and Ij are any pair of input labels on arcs exiting state Sk, then IiIj 0 if i j.2. If n arcs exit state Sk and the n arcs have input labels I1, I2, ., In,respectively, then I1 I2 . In 1.X1X1'X2'SkX1'X2SqSpInputs are X1 X2 X3(X1 X2 1 not allowed)X1'X2'X1Sp(X1)(X1'X2') 0(X1)(X1'X2) 0(X1'X2')(X1'X2) 0X1 X1'X2' X1'X2 1Sk000 001 010 011 100 101 110 111Sk Sk Sk Sq Sq Sp Sp – –X2Sq
Multiplication of 1310 by 1110 In Binary – From Page 124MultiplicandMultiplierPartialProductsinitial contents of product register(add multiplicand since M 1)after additionafter shift(add multiplicand since M 1)after additionafter shift(skip addition since M 0)after shift(add multiplicand since M 1)after additionafter shift (final answer)1101 (13)1011 (11)110111011001110000100111110110001111 (143)0 010 10 011 00 10111100000101001101111 0 1 10 011 00 1110000000 1 1 1 111 1 1 1 10 1 1 1 1M (11)(13)1 0 1 11 1 0 1M1 1 0 11 1 1 0Mdividing line between product and multiplierM(143)
Figure 4-3 Block Diagram for Binary Cm4-BIT ADDERStMmultiplicandmultiplier0
Figure 4-4 State graph for Binary Multiplier ControlSt'/0S9– /Sh– /DoneS0St/LoadS1S8M'/ShM/AdM/AdM'/ShS7– /ShM'/Sh– /ShS6M/AdM'/ShS3M/AdS5S2– /ShS4
Figure 4-5(a) Behavioral Model for 4 x 4 Binary Multiplier-- This is a behavioral model of a multiplier for unsigned binary numbers. It multiplies a-- 4-bit multiplicand by a 4-bit multiplier to give an 8-bit product.-- The maximum number of clock cycles needed for a multiply is 10.library BITLIB;use BITLIB.bit pack.all;entity mult4X4 isport (Clk, St: in bit;Mplier,Mcand : in bit vector(3 downto 0);Done: out bit);end mult4X4;architecture behave1 of mult4X4 issignal State: integer range 0 to 9;signal ACC: bit vector(8 downto 0);-- accumulatoralias M: bit is ACC(0);-- M is bit 0 of ACCbeginprocessbeginwait until Clk '1';-- executes on rising edge of clockcase State iswhen 0 -- initial Stateif St '1' thenACC(8 downto 4) "00000";-- Begin cycleACC(3 downto 0) Mplier;-- load the multiplierState 1;end if;
Figure 4-5(b) Behavioral Model for 4 x 4 Binary Multiplierwhen 1 3 5 7 if M '1' thenACC(8 downto 4) add4(ACC(7State State 1;elseACC '0' & ACC(8 downto 1);State State 2;end if;when 2 4 6 8 ACC '0' & ACC(8 downto 1);State State 1;when 9 State 0;end case;end process;Done '1' when State 9 else '0';end behave1;-- "add/shift" State-- Add multiplicanddownto 4),Mcand,'0');--Shift accumulator right-- "shift" State-- Right shift-- End of cycle
Figure 4-6 Multiplier Control with St/LoadS1M/Ad-/ShKCounterS2(a) Multipler control(b) State graph for add-shift /AdS2K/Sh(c) Final state graph for add-shift control
Table 4-2 Operation of Multiplier Using a CounterTimeState Countert0t1S0S00000ProductSt MRegister000000000 0 0000000000 1 0K Load Ad Sh 111000111110110010t9S3000100011110100001
Table 4-3 4-bit Multiplier Partial X2Y0X1Y0X0Y0 partial product 0X3Y1X2Y1X1Y1X0Y1partial product 7P6P5P4P31st row carriesS101st row sumspartial product 22nd row carriesS202nd row sumspartial product 33rd row carries3rd row sumsP2P1P0final product
Figure 4-7 Block Diagram of 4 x 4 Array P7C31C30FAS33FAS32FAS31HAS30P6P5P4P3
From Page 1330. 1 1 1X 0. 1 0 1( 0. 0 0) 0 1 1 1( 0.)0 1 1 10. 1 0 0 0 1 11. 1 0 1X 0. 1 0 1( 1. 1 1) 1 1 0 1( 1.)1 1 0 11. 1 1 0 0 0 1 ( 7/64) ( 7/16) ( 7/8)( 5/8)( 35/64)MultiplicandMultiplierNote: The proper representation of the fractional partialproducts requires extension of the sign bit past the binarypoint, as indicated in parentheses. (Such extension is notnecessary in the hardware.)(–3/8)( 5/8)(–3/64)(–3/16)(–15/64) Note: The extension of the sign bit providesproper representation of the negative products.
From Pages 133 – 1340. 1 0 1X 1. 1 0 1( 5/8)(–3/8)( 0. 0 0) 0 1 0 1( 0.)0 1 0 1( 5/64)( 5/16)( 0.)0 1 1 0 0 11. 0 1 1(–5/8)1. 1 1 0 0 0 11. 1 0 1X 1. 1 0 1(–15/64)Note: The two's complement of the multiplicandis added at this point.(–3/8)(–3/8)( 1. 1 1) 1 1 0 1( 1.)1 1 0 1(–3/64)(–3/16)( 1.)1 1 0 0 0 10. 0 1 1( 3/8)0. 0 0 1 0 0 1 ( 9/64) Add the two's complement of the multiplicand
Figure 4-8 Block Diagram for 2's Complement erTRDoneO5-BIT FULL ADDERCinStLCm1's COMPLEMENTERMmultiplicandCm0
Figure 4-9 State Graph for 2's Complement MultiplierSt'/0- /DoneS0S8St/LoadM/Cm AdS1M'/0M/AdS7M'/Sh– /ShS6– /ShM'/ShM'/ShM/AdS2S3M/AdS5– /ShS4
Figure 4-10 Block Diagram for Faster MultiplierproductLoadShAdShCBA (accumulator)3210321ONTDoneRO4-BIT FULL ADDER CinStLCm1's COMPLEMENTERMmultiplicandCmmultiplier0
Figure 4-11 State Graph for Faster MultiplierSt'/0–/DoneS0S1S5M/AdShM'/ShM/Cm AdShM'/ShS2S4M/AdShM'/ShSt/LoadS3M/AdShM'/Sh
Figure 4-12(a) Behavioral Model for 2’s Complement Multiplierlibrary BITLIB;use BITLIB.bit pack.all;entity mult2C isport (CLK, St: in bit;Mplier,Mcand : in bit vector(3 downto 0);Product: out bit vector (6 downto 0);Done: out bit);end mult2C;architecture behave1 of mult2C issignal State : integer range 0 to 5;signal A, B: bit vector(3 downto 0);alias M: bit is B(0);beginprocessvariable addout: bit vector(4 downto 0);beginwait until CLK '1';case State iswhen 0 if St '1' thenA "0000";B Mplier;State 1;end if;-- initial State-- Begin cycle-- load the multiplier
Figure 4-12(b) Behavioral Model for 2’s Complement Multiplierwhen 1 2 3 -- "add/shift" Stateif M '1' thenaddout : add4(A,Mcand,'0'); -- Add multiplicand to A and shiftA Mcand(3) & addout(3 downto 1);B addout(0) & B(3 downto 1);elseA A(3) & A(3 downto 1); -- Arithmetic right shiftB A(0) & B(3 downto 1);end if;State State 1;when 4 -- add complement if sign bitif M '1' then-- of multiplier is 1addout : add4(A, not Mcand,'1');A not Mcand(3) & addout(3 downto 1);B addout(0) & B(3 downto 1);elseA A(3) & A(3 downto 1); -- Arithmetic right shiftB A(0) & B(3 downto 1);end if;State 5; wait for 0 ns;Done '1'; Product A(2 downto 0) & B;when 5 -- output productState 0;Done '0';end case;end process;end behave1;
Figure 4-13 Command File and Simulation Results for ( 5/8 by -3/8)-- command file to test signed multiplierlist CLK St State A B Done Productforce st 1 2, 0 22force clk 1 0, 0 10 - repeat 20-- (5/8 * -3/8)force Mcand 0101force Mplier 1101run 120ns0210202230405060708090100110120delta 1 0 0 1 0 0 1 0 1 0 1 0 2 0 011110001
Figure 4-14 Test Bench for Signed Multiplierlibrary BITLIB;use BITLIB.bit pack.all;entity testmult is end testmult;architecture test1 of testmult iscomponent mult2Cport(CLK, St: in bit;Mplier,Mcand : in bit vector(3 downto 0);Product: out bit vector (6 downto 0);Done: out bit);end component;constant N: integer : 11; type arr is array(1 to N) of bit vector(3 downto 0);constant Mcandarr: arr : ("0111", "1101", "0101", "1101", "0111", "1000", "0111","1000", "0000", "1111", "1011");constant Mplierarr: arr : ("0101", "0101", "1101", "1101", "0111", "0111", "1000","1000", "1101", "1111", "0000");signal CLK, St, Done: bit; signal Mplier, Mcand: bit vector(3 downto 0);signal Product: bit vector(6 downto 0);beginCLK not CLK after 10 ns;processbeginfor i in 1 to N loopMcand Mcandarr(i); Mplier Mplierarr(i); St '1';wait until rising edge(CLK); St '0'; wait until falling edge(Done);end loop;end process;mult1: mult2c port map(Clk, St, Mplier, Mcand, Product, Done);end test1;
Figure 4-15 Command File and Simulation of Signed Multiplier-- Command file to test results of signed multiplierlist -NOtrigger Mplier Mcand product -Trigger donerun 0950105010701170119012901310delta mplier mcand product done 10101 0111 00000000 20101 0111 01000111 20101 1101 01000110 20101 1101 11100011 21101 0101 11100010 21101 0101 11100011 21101 1101 11100010 21101 1101 00010011 20111 0111 00010010 20111 0111 01100011 20111 1000 01100010 20111 1000 10010001 21000 0111 10010000 21000 0111 10010001 21000 1000 10010000 21000 1000 10000001 21101 0000 10000000 21101 0000 00000001 21111 1111 00000000 21111 1111 00000011 20000 1011 00000010 20000 1011 00000001 20101 0111 000000005/8 * 7/8 35/645/8 * -3/8 -15/64-3/8 * 5/8 -15/64-3/8 * -3/8 9/647/8 * 7/8 49/647/8 * -1 -7/8-1 * 7/8 -7/8-1 * -1 -1 (error)-3/8 * 0 0-1/8 * -1/8 1/640 * -3/8 0
Figure 4-16(a) [revised] Model for 2’s Complement Multiplier with Control Signalslibrary BITLIB;use BITLIB.bit pack.all;entity mult2Cs isport (CLK, St: in bit;Mplier,Mcand : in bit vector(3 downto 0);Product: out bit vector (6 downto 0); Done: out bit);end mult2Cs;architecture behave2 of mult2Cs issignal State, Nextstate: integer range 0 to 5; signal A, B: bit vector(3 downto 0);signal AdSh, Sh, Load, Cm: bit; signal addout: bit vector(4 downto 0);alias M: bit is B(0);beginprocess (state, st, M)beginLoad '0'; AdSh '0'; Sh '0'; Cm '0'; Done '0';case State iswhen 0 -- initial Stateif St '1' then Load '1'; Nextstate 1; end if;when 1 2 3 -- "add/shift" Stateif M '1' then AdSh '1'; else Sh '1'; end if;Nextstate State 1;when 4 -- add complement if signif M '1' then Cm '1'; AdSh '1'; -- bit of multiplier is 1else Sh '1'; end if;nextstate 5;
Figure 4-16(b) [revised] Model for 2’s Complement Multiplier with Control Signalswhen 5 done '1';nextstate 0;end case;end process;-- Output productaddout add4(A, Mcand, '0') when Cm '0' else add4(A, not Mcand, '1');processbeginwait until CLK '1';-- executes on rising edgeif Load '1' then-- Load the multiplierA "0000";B Mplier;end if;if AdSh '1' then-- Add multiplicand to A and ShiftA (Mcand(3) xor Cm) & addout(3 downto 1);B addout(0) & B(3 downto 1);end if;if Sh '1' thenA A(3) & A(3 downto 1); B A(0) & B(3 downto 1);end if;State Nextstate;end process;Product A(2 downto 0) & B;end behave2;
Figure 4-17 Realization of Multiplier Control NetworkP1Ld1Clr11Q3 Q2 Q1 Q074163D3 D2 D1LOGICCLKD0LoadDoneShStAdShMCo0100
Figure 4-18(a) Model for 2’s Complement Multiplier Using Control Equations-- This model of a 4-bit multiplier for 2's complement numbers-- implements the controller using a counter and logic equations.library BITLIB;use BITLIB.bit pack.all;entity mult2CEQ isport(CLK, St: in bit;Mplier,Mcand: in bit vector(3 downto 0);Product: out bit vector(6 downto 0));end mult2CEQ;architecture m2ceq of mult2CEQ issignal A, B, Q, Comp: bit vector(3 downto 0);signal addout: bit vector(4 downto 0);signal AdSh, Sh, Load, Cm, Done, Ld1, CLR1, P1: bit;Signal One: bit: '1';Signal Din: bit vector(3 downto 0) : "0100";alias M: bit is B(0);beginCount1: C74163 port map (Ld1, CLR1, P1, One, CLK, Din, open, Q);P1 Q(2); CLR1 not Q(3); Done Q(3); Sh not M and Q(2);AdSh M and Q(2); Cm Q(1) and Q(0) and M;Load not Q(3) and not Q(2) and St; Ld1 not Load;Comp Mcand xor (Cm & Cm & Cm & Cm);-- complement Mcand if Cm '1'addout add4(A,Comp,Cm);-- add complementer output to A
Figure 4-18(b) Model for 2’s Complement Multiplier Using Control Equationsprocessbeginwait until CLK '1';-if Load '1' then-A "0000";B Mplier;end if;if AdSh '1' then-A (Mcand(3) xor Cm) & addout(3B addout(0) & B(3 downto 1);end if;if Sh '1' then-A A(3) & A(3 downto 1);B A(0) & B(3 downto 1);end if;if Done '1' thenProduct A(2 downto 0) & B;end if;end process;end m2ceq;executes on rising edgeload the multiplierAdd multiplicand to A and shiftdownto 1);Right shift with sign extend
Parallel Divider for Positive Binary Numbers – From Page 144divisor1101(135 13 10 witha remainder of 5)load:(can't subtract)shift L:subtract:shift L:(can't subtract)shift L:subtract:shift L:(can't subtract)done1010 quotient10000111 dividend11010111000011111101010100000101 tientDividing line betweendividend and quotientNote that after the shift, therightmost position in the dividendregister is "empty."First quotient digitThird quotient digit
Figure 4-19 Block Diagram for Parallel Binary DividerDividend RegisterX8X7X6X5X4X3X2X1X0ShShLdSt (Start lockV(overflowIndicator)
Figure 4-20 State Diagram for Divider Control 0C'/ShC'/ShS5S4C'/ShC/SuS3C/SuStCState uSuSu11Load–––––10Load–––––
Control Signals for Signed DividerLdULoad upper half of dividend from busLdLLoad lower half of dividend from busLdsLoad sign of dividend into sign flip-flopSSign of dividendCm1Complement dividend register (2's complement)LddLoad divisor from busSuEnable adder output onto bus (Ena) and load upper half of dividend from busCm2Enable complementer (Cm2 equals the complement of the sign bit of the divisor,so that a positive divisor is complemented and a negative divisor is not)ShShift the dividend register left one place and increment the counterCCarry output from adder (If C 1, the divisor can be subtracted from the upperdividend.)StStartVOverflowQnegQuotient will be negative (Qneg 1 when sign of dividend and divisor aredifferent)
Figure 4-21 Block Diagram for Signed DividerDbusData in1616DividendAcc (Remainder)Q (Quotient)LduLdl161616-bit Full ControlControlCm21616-bit ComplementerSh4 -bitCounterKLddVSLdsSign
Figure 4-22 State Graph for Signed Divider Control NetworkSt'/0S0 St/ Ldu LdsRdyS1–/LdlS2S/Co1 LddS'/LddC/VC' Qneg'/0C' Qneg/Co1–/ShK' C'/ShS6KC'/ShC/SuS3S4C'/ShS5C/Su
Figure 4-23(a) VHDL Model of 32-bit Signed Dividerlibrary BITLIB;use BITLIB.bit pack.all;entity sdiv isport(Clk,St: in bit;Dbus: in bit vector(15 downto 0); Quotient: out bit vector(15 downto 0);V, Rdy: out bit);end sdiv;architecture Signdiv of Sdiv isconstant zero vector: bit vector(31 downto 0): (others '0');signal State: integer range 0 to 6; signal Count : integer range 0 to 15;signal Sign,C,NC: bit; signal Divisor,Sum,Compout: bit vector(15 downto 0);signal Dividend: bit vector(31 downto 0);alias Q: bit vector(15 downto 0) is Dividend(15 downto 0);alias Acc: bit vector(15 downto 0) is Dividend(31 downto 16);begin-- concurrent statementscompout divisor when divisor(15) '1'-- 1's complementerelse not divisor;Addvec(Acc,compout,not divisor(15),Sum,C,16); -- 16-bit adderQuotient Q; Rdy '1' when State 0 else '0';
Figure 4-23(b) VHDL Model of 32-bit Signed Dividerprocessbeginwait until Clk '1';-- wait for rising edge of clockcase State iswhen 0 if St '1' thenAcc Dbus;-- load upper dividendSign Dbus(15); State 1;V '0'; Count 0;-- initialize overflow// initialize counterend if;when 1 Q Dbus; State 2;-- load lower dividendwhen 2 Divisor Dbus;if Sign '1'then-- two's complement Dividend if necessaryaddvec(not Dividend,zero vector,'1',Dividend,NC,32);end if; State 3;when 3 Dividend Dividend(30 downto 0) & '0';-- left shiftCount Count 1; State 4;when 4 if C '1' then-- Cv '1'; State 0;else-- C'Dividend Dividend(30 downto 0) & '0'; -- left shiftCount Count 1; State 5;end if;
Figure 4-23(c) VHDL Model of 32-bit Signed Dividerwhen 5 if C '1' then-- CACC Sum;-- subtractQ(0) '1';elseDividend Dividend(30 downto 0) & '0'; -- left shiftif Count 15 then-- KC'count 0; State 6;else Count Count 1;end if;end if;when 6 if C '1' then-- CAcc Sum;-- subtractQ(0) '1';else if (Sign xor Divisor(15)) '1' then-- C'Qnegaddvec(not Dividend,zero vector,'1',Dividend,NC,32);end if;-- 2's complement Dividendstate 0;end if;end case;end process;end signdiv;
Figure 4-24(a) Test Bench for Signed Dividerlibrary BITLIB;use BITLIB.bit pack.all;entity testsdiv isend testsdiv;architecture test1 of testsdiv iscomponent sdivport(Clk,St: in bit;Dbus: in bit vector(15 downto 0); Quotient: out bit vector(15 downto 0);V, Rdy: out bit);end component;constant N: integer : 12;-- test sdiv1 N timestype arr1 is array(1 to N) of bit vector(31 downto 0);type arr2 is array(1 to N) of bit vector(15 downto 0);constant dividendarr: arr1 : tant divisorarr: arr2 : (X"0007", X"E005", X"001E", X"EFFA", X"7FFF", X"7FFF", X"7FFF",X"8000", X"7FFF", X"0001", X"7FFF", X"0000");signal CLK, St, V, Rdy: bit; signal Dbus, Quotient, divisor: bit vector(15 downto 0);signal Dividend: bit vector(31 downto 0); signal count: integer range 0 to N;
Figure 4-24(b) Test Bench for Signed DividerbeginCLK not CLK after 10 ns;processbeginfor i in 1 to N loopSt '1';Dbus dividendarr(i) (31 downto 16);wait until rising edge(CLK);Dbus dividendarr(i) (15 downto 0);wait until rising edge(CLK);Dbus divisorarr(i);St '0';dividend dividendarr(i);-- save dividend for listingdivisor divisorarr(i);-- save divisor for listingwait until (Rdy '1');count i;-- save index for triggeringend loop;end process;sdiv1: sdiv port map(Clk, St, Dbus, Quotient, V, Rdy);end test1;
Figure 4-25 Simulation Test Results for Signed Divider-- Command file to test results of signed dividerlist -hex -Notrigger dividend divisor Quotient V -Trigger countrun 5300nsdelta dividenddivisor quotient vcount0 0000000000000000000470 30000006F0007000F01910 307FF00BBE005BFFE021330 3FFFFFE08001EFFF0031910 3FF80030AEFFA07FC042010 33FFF80007FFF0000152710 33FFF7FFF7FFF7FFF062810 3C00080007FFF0000173510 3C000800080007FFF084210 3C00080017FFF8001094610 300000000000100000A5010 3FFFFFFFF7FFF00000B5110 3FFFFFFFF000000021C
Figure 4-1 Serial Adder with Accumulator X Y ci sumi ci 1 t0 0101 0111 0 0 1 t1 0010 1011 1 0 1 t2 0001 1101 1 1 1 t3 1000 1110 1 1 0 t4 1100 0111 0 (1) (0) y 3 y 2 y 1 y 0 Full Adder Q D Q' CK xi yi ci ci 1 sumi x 3 x 2 x 1 x 0 Addend Register Accumulator Control Circuit Clock N (Start Signal) SI Sh Sh SI Sh Sh Clock Serial Adder
designs, in digital design we use adders such as half adder, full adder. By using both adders we can implement ripple carry adder, using ripple carry adder we can perform addition for any number of bits. It is a serial adder. It has a huge delay problem. With the use of half adder, full adder delay increases.
1st half adder 2nd half adder Fig. 2.4 : A full adder circuit using half adder. This partial carry combines with the other partial carry and gives the final carry output. The three inputs to such a full adder, A,B and C are completely interchangeable. A full adder circuit constructed by using two half adder circuit.
Adder Aim:To verify the truth table of half adder and full adder by using XOR and NAND gates respectively and analyse the working of half adder and full adder circuit with the help of LEDs in simulator 1 and verify the truth table only of half adder and full adder in simulator 2. Theory Introduction
The Full adder itself is built by 2 half adder and one OR gate. The Half adder block is built by an AND gate and an XOR gate. We will show the schematic of each of these blocks. Figure 19: XOR gate implementation using NAND gates Figure 17: Half adder Figure 18: Full Adder using Half Adder. Next 3 figures show the layout of the XOR gate, Half .
Figure 4.1: Gate-level diagram for full adder Figure 4.2: Verilog code for full adder with parameters Figure 4.3: Ripple carry adder diagram for 4 full adder Figure 4.4: Verilog code for RCA with option parameter Figure 4.5: Example operations for two’s complement Figure 4.6: Verilog code of adder-subtractor top module
Server, and the ADDER.NET VNC-URI client. In a typical installation, the ADDER.NET Server is installed just once, but the ADDER.NET VNC-URI client may be installed on any PC from which ADDER.NET Server needs to be accessed. ADDER.NET Server requires a Wind
adder is a full adder block. A full adder computes the sum bit Si and the carry output c i 1 based on addend inputs a and b and carry input c. The output expressions for a ripple carry adder are (1) Si a xor b xor c; (2) Ci 1 ab bc ca; (i 0,1,2, .) Fig 3a shows the ripple carry adder circuit implemented using Fredkin gates [3].
Full Adder is designed using Half Adders. In this paper half adder is designed taking into consideration that Parallel feedback carry adder (PFCA) is based on the unit of half adder. So in this paper Half adder is designed using NAND Gates only and using EX-OR and AND Gates in
