fundamentals of logic design

728 Appendix E 15.6 (a) (b) A 0 1 A 0 1 BC S1 S2 BC S1 S8 00 00 01 S4 S3 01 S7 S5 DA = A+ = A′B′ + XA′ + X′AC ′ DB = B+ = etc. Z=A DC = C+ = etc. 11 S6 S5 11 S3 S4 10 S7 S8 10 S2 S6 15.7 (a) Q1 0 1 C Q2Q3 (b) D1 ϭ XQ1 D2 ϭ QЈ1QЈ3 ϩ XЈQЈ1 00 A D3 ϭ XЈQЈ1QЈ3 ϩ XQЈ1Q3 ϩ {XQЈ2 or Q2Q3} Z ϭ XQ1 01 B E 11 F 10 D 15.8 (a) A ϭ 00, B ϭ 01, C ϭ 10, D ϭ 11 (b) T1 ϭ XЈ1X2QЈ2 ϩ XЈ1Q1Q2 ϩ X1QЈ1Q2 ϩ X1XЈ2 T2 ϭ X1QЈ1QЈ2 ϩ X1Q1Q2 Z1 ϭ X1Q2, Z2 ϭ XЈ1Q1 ϩ Q1QЈ2 15.9 Assign S0 Q1 Q2 Q3 D1 ϭ XЈQ1 ϩ XYЈQ3 S1 S2 100 D2 ϭ XQ1 ϩ YQ3 ϩ XЈQ2 010 D3 ϭ XQ2 ϩ XЈYЈQ3 001 P ϭ XQ1 ϩ YЈQ3 ϩ XQ2 S ϭ XЈQ1 ϩ XYЈQ3UNIT 16 Study Guide Answers 1. (a) Because the input sequences are listed in reverse order. 2. (b) m leads, where 2m Ϫ 1 Ͻ n Յ 2m 3. (b) 64 words ϫ 7 bits (d) Z ϭ 0, D1 ϭ 1, D2 ϭ 1, D3 ϭ 0; Q1Q2Q3 ϭ 110 8. (a) Yes (c) Yes 9. (a) After the clock (when the state has just changed) and before the input is set to its new value, the output may be wrong (false output). (b) No, because the output is always correct before the active clock edge.

Answers to Selected Study Guide Questions and Problems 729UNIT 16 Answers to Problems 16.15X1 Z1 X1 X2 Q1 Q2 Q1ϩ Q2ϩ Z1 Z2 Z2X2 00 0 0 1 1 00 Q + 00 0 1 0 0 10 1 D 00 1 0 1 1 00 00 1 1 1 0 00 ROM Q1 01 0 0 1 0 10 24 Words Q2 01 0 1 0 1 10 01 1 0 0 0 10 4 Bits Per Word 01 1 1 1 0 00 10 0 0 0 1 11 Q + D 10 0 1 1 0 11 2 10 1 0 0 1 11 10 1 1 0 1 01 Clock 11 0 0 0 0 01 11 0 1 1 1 11 11 1 0 0 1 01 11 1 1 0 0 0116.16 (a) Same as Figure 16-10 with ROM replaced by PLA. (b) XAB C Z DA DB DC 0-- - 01 0 0 0- -0 00 1 0 -0-1 00 1 0 - 01 - 00 1 0 -1- - 00 0 1 1-0- 00 0 1 0101 10 0 0 1010 10 0 016.17 (a) 0 S0 1 S1 1 S2 1 S3 0 0 011 000 (b) ai ϩ 1 ϭ ai ϩ xibi ϭ [aЈi (xibi)Ј]Ј bi ϩ 1 ϭ xibЈi ϩ xЈibi ϭ [(xibЈi)Ј (xЈibi)Ј]Ј z ϭ an ϩ 1bn ϩ 1 (c) a1 ϭ b1 ϭ 0, a2 ϭ 0, b2 ϭ x1 (d) Similar to Figure 16-9 with one output

730 Appendix EUNIT 17 Study Guide Answers 1. (a) When a falling edge of CLK occurs (b) Whenever there is a change in St or Q1 or V (c) Statements S3 and S4 will execute (d) The code represents a rising-edge-triggered D flip-flop with asynchronous, active-low clear and preset. Because ClrN has higher priority, Q will be set to ‘0’ when both ClrN and SetN are ‘0’. (e) SN and RN override J and K, including at a clock edge. Q will be ‘0’. (f ) They will get the old value of Qint because of the 8-ns delay. 2. (a) entity register is port (CLK, CLR, Ld: in bit; D: in bit_vector (3 downto 0); Q: out bit_vector (3 downto 0)); end register; architecture eqn of register is begin -- Given code here end eqn; (b) Q will change at time 10 ϩ ⌬ ns (c) On line 6 of the VHDL code, make this change— elsif LS ϭ ‘1’ then Q Ͻϭ Q (2 downto 0) & Q (3); (d) Change the indicated lines of code as shown— line 3: process (ClrN, CLK) lines 5 to 7: if ClrN ϭ ‘0’ then Q Ͻϭ “0000”; elsif CLK’event and CLK ϭ ‘1’ then if En ϭ ‘1’ then Q Ͻϭ Q ϩ 1; (e) When Carry1 ϭ ‘1’ and Qout2 ϭ “1111” (f) No overloaded “ϩ” operator is defined for bit_vectors (g) After the rising edge, Qout1 ϭ “0000” and Qout2 ϭ “1010” (h) Control Signals Next State Q1ϩ Q0ϩ ClrN LdN PT Q3ϩ Q2ϩ D0 X0X D3 D2 D1 0 X11 Present state ϩ 1 Q0 0 10 1 10 000 Q3 Q2 Q1 3. (a) process (A, B, D) begin E Ͻϭ (A and B) or D after 5 ns; end process; 4. (a) Nextstate ϭ S4 and Z ϭ 1 (b) Because there are only seven states. Also, specifying the range restricts the number of bits used to represent the integer

Answers to Selected Study Guide Questions and Problems 731 When X changes to 1, Nextstate ϭ 2, and Z ϭ 0.Then, when CLK changes to 1, State ϭ 2, Nextstate ϭ 4, and Z ϭ 1 (c) The glitch occurs because the change in state and change in the value of X a little while later causes process (State, X) to execute two times, thereby up- dating the value of Nextstate two times. This glitch does not affect the ‘state’ because the state will not be updated until the next positive clock edge. (d) Because Q1, Q2, and Q3 must be updated only on the CLK edge, the other signals must not appear on the sensitivity list. The new values will be com- puted at 5 ns, and the values are updated at 15 ns. (e) The statements of lines 13, 14, and 18 will execute. (f) ROM output ϭ 1100 5. (a) Connect En to CE and A to D (b) See Figure 11-27(c) (change to rising-edge trigger) (c) Use four D-CE flip-flops. Connect ASR to every CE input, D3 to Q3, D2 to Q3, D1 to Q2, and D0 to Q1. Label Q3 . . . Q0 as A(3) . . . A(0). 6. (a) process begin A Ͻϭ B or C; wait on B, C; end process; (b) 2 ns (Both sequential statements execute immediately with no delay.)UNIT 17 Answers to Problems 17.1 Code to implement a T flip-flop entity tff is port (t, clk, clrn: in bit; q, qn: out bit); end tff; architecture eqn of tff is signal qint: bit; -- Internal value of q begin q Ͻϭ qint; qn Ͻϭ not qint; process (clk, clrn) begin if clrn ϭ ‘0’ then qint Ͻϭ ‘0’; elsif clk’event and clk ϭ ‘1’ then qint Ͻϭ (t and not qint) or (not t and qint); end if; end process; end eqn;

732 Appendix E 17.2 Right-shift register with synchronous reset entity rsr is Port (clk, clr, ld, rs, lin: in bit; d: in bit_vector(3 downto 0); q: out bit_vector(3 downto 0)); end rsr; architecture eqn of rsr is signal qint: bit_vector(3 downto 0); begin q Ͻϭ qint; process (clk) begin if clk’event and clk ϭ ’1’ then if clr ϭ ’1’ then qint Ͻϭ “0000”; elsif ld ϭ ’1’ then qint Ͻϭ d; elsif rs ϭ ’1’ then qint Ͻϭ lin & qint(3 downto 1); end if; end if; end process; end eqn; 17.3 (a) 4-bit binary up/down counter entity updown is Port (clrn, clk, load, ent, enp, up: in std_logic; d: in std_logic_vector(3 downto 0); q: out std_logic_vector(3 downto 0); co: out std_logic); end updown; architecture eqn of updown is signal qint: std_logic_vector(3 downto 0) :ϭ “0000”; begin q Ͻϭ qint; co Ͻϭ (qint(3) and qint(2) and qint(1) and qint(0) and ent and up) or (not qint(3) and not qint(2) and not qint(1) and not qint(0) and ent and not up); process (clrn, clk) begin if clrn ϭ ’0’ then qint Ͻϭ “0000”; elsif clk’event and clk ϭ ’1’ then if load ϭ ’0’ then qint Ͻϭ d; elsif (ent and enp and up) ϭ ’1’ then qint Ͻϭ qint ϩ 1;

Answers to Selected Study Guide Questions and Problems 733 elsif (ent and enp and not up) ϭ ’1’ then qint Ͻϭ qint Ϫ 1; end if; end if; end process; end eqn;17.3 (b) 8-bit binary up/down counter. (For block diagram, connect the Carry-out of the first counter to ENT of the second.) entity updown8bit is Port (clrn, clk, load, ent, enp, up: in std_logic; d: in std_logic_vector(7 downto 0); q: out std_logic_vector(7 downto 0); co: out std_logic); end updown8bit; architecture structure of updown8bit is component updown is Port (clrn, clk, load, ent, enp, up: in std_logic; d: in std_logic_vector(3 downto 0); q: out std_logic_vector(3 downto 0); co: out std_logic); end component; signal co1: std_logic; signal q1,q2: std_logic_vector(3 downto 0); begin c1: updown port map (clrn, clk, load, ent, enp, up, d(3 downto 0),q1,co1); c2: updown port map (clrn, clk, load, co1, enp, up, d(7 downto 4),q2, co); q Ͻϭ q2 & q1; end structure;17.4 MUX with a and b as control inputs entity mymux is Port (a, b, c, d: in bit; z: out bit); end mymux; architecture eqn of mymux is signal sel: bit_vector(1 downto 0); begin sel Ͻϭ a & b; process (a, b, c, d) begin case sel is when “00” ϭϾ z Ͻϭ not c or d; when “01” ϭϾ z Ͻϭ c;

734 Appendix E when “10” ϭϾ z Ͻϭ not c xor d; when “11” ϭϾ z Ͻϭ not d; end case; end process; end eqn; 17.5 Implements the state machine of Table 14-1 entity sm1 is Port (x, clk: in bit; z: out bit); end sm1; architecture table of sm1 is signal State, Nextstate: integer range 0 to 2 :ϭ 0; begin process (State, x) begin case State is when 0 ϭϾ if x ϭ ’0’ then Nextstate Ͻϭ 0; else Nextstate Ͻϭ 1; end if; z Ͻϭ ‘0’; when 1 ϭϾ if x ϭ ’0’ then Nextstate Ͻϭ 2; else Nextstate Ͻϭ 1; end if; z Ͻϭ ‘0’; when 2 ϭϾ if x ϭ ’0’ then Nextstate Ͻϭ 0; z Ͻϭ ‘0’; else Nextstate Ͻϭ 1; z Ͻϭ ‘1’; end if; end case; end process; process (clk) begin if clk’event and clk ϭ ’0’ then State Ͻϭ Nextstate; end if; end process; end table; 17.6 (a) See Figure 13-17, with m ϭ 2, n ϭ 2, and k ϭ 2. (b) Implements the state machine of Table 13-4 library BITLIB; use BITLIB.bit_pack.all; entity sm is Port (x1, x2, clk: in bit; z1,z2: out bit);

Answers to Selected Study Guide Questions and Problems 735 end sm; architecture Behavioral of sm is type rom16_4 is array (0 to 15) of bit_vector(3 downto 0); -- Input is in the order X1 X2 Q1 Q2 -- Output in order Q1 Q2 Z1 Z2 constant myrom: rom16_4 :ϭ (“1100”, “0010”, “1100”, “1000”, “1010”, “0110”,“0010”, “1000”, “0111”, “1011”, “0111”, “0101”, “0001”, “1111”, “0101”, “0001”); signal index: integer range 0 to 15; signal q1,q2: bit; signal rom_out: bit_vector(3 downto 0); begin index Ͻϭ vec2int(x1&x2&q1&q2); rom_out Ͻϭ myrom(index); z1 Ͻϭ rom_out(1); z2 Ͻϭ rom_out(0); process(clk) begin if clk’event and clk ϭ ’1’ then q1 Ͻϭ rom_out(3); q2 Ͻϭ rom_out(2); end if; end process; end Behavioral;17.7 (a) There are two D-CE flip-flops. For each, CE ϭ LdA ϩ LdB. D1 ϭ LdA A1 ϩ LdAЈ LdB B1, D2 ϭ LdA A2 ϩ LdAЈ LdB B2. (b) CE does not change. For each D input, replace the gates with a 2-to-1 MUX, with LdA as the control input, and B and A as the data inputs for 0 and 1, respectively. (Alternately, use LdB as the control input, and swap A and B on the data inputs.)17.8 All statements execute at time ϭ 20 ns A becomes 1 at 35 ns (not the final value) B becomes 1 at 20 ns ϩ ⌬ (not the final value) C becomes 1 at 30 ns D becomes 2 at 23 ns A becomes 5 at 35 ns (overrides the previous value) B becomes 7 at 20 ns ϩ ⌬ (overrides the previous value)UNIT 18 Study Guide Answers X Y ci si cϩi 1. (a) 0110 0011 0 1 0 1011 1001 0 0 1 t0 0101 1100 1 0 1 t1 0010 0110 1 1 0 t2 1001 0011 0 (0) (1) t3 t4

736 Appendix E (b) Y would fill up with 0’s from the left: 0011, 0001, 0000, 0000, 0000. (c) S0 and Y0, no. 2. (a) add 0 0 0 0 0 1 1 0 1 1111 shift 0 1 1 1 1 1 1 0 1 shift 0 0 1 1 1 1 1 1 0 add 0 0 0 1 1 1 1 1 1 1111 shift 1 0 0 1 0 1 1 1 1 add 0 1 0 0 1 0 1 1 1 1111 shift 1 1 0 0 0 0 1 1 1 011000011 (b) 10, 6. (c) 10, 6. (d) 15 bits (f) Product register has 17 bits.Adder is 8 bits wide, multiplicand has 8 bits. 18 states. 3-bit counter, K ϭ 1 when counter is in state 7 (1112), control graph unchanged. 3. (b) Change Y to 2’s complement by inverting each bit and adding 1 (by setting the carry input of the first full adder to 1). Also change C so that it is equal to the carry out of the last full adder. (c) An overflow will occur if X8X7X6X5X4 Ն Y3Y2Y1Y0, because subtraction is possible but there is no place to store the quotient bit, since there are only 4 bits available to store the quotient. (f) To set the quotient bit to 1.UNIT 18 Answers to Problems 18.3 SI x4 x3 x2 x1 x0 x Sh d St SI y4 y3 y2 y1 y0 b Control Sh Sh Circuit yQ CE D Clock x′ y y x′

Answers to Selected Study Guide Questions and Problems 73718.4 1 Z1 0x1y1 1 S1 Z2 0 0x1 Fully2 1 Adderx2y1 1 C2 S2 Full S4 Z3 1 1 1 Adder 0x1 x3y3 Full y1 1 C5x2 1 Addery2 S3 Full S5 Z4 1 C3 0 1 Adder 0x2 0 x3y3 y2 Full 1 Adder 1 C6 1 C4 x3 Full S6 Z5 y3 1 Adder 1 1 C7 Z618.5 18.6 – St ′ St′ St S5 Done 0 0 Load S0 S0 C (Stop) VM′ St S1 Sh Load C Su C′M S4 M Sh Ad Ad C′ 0 C S1 S2 SuM′ S3 KC ′ Sh M′ Sh K ′C ′ Sh Sh S3 S2 M′M Ad Sh M Ad18.7 (a) V ϭ y0Јy1Јy2Јy3Јy4Ј ϭ (y0 ϩ y1 ϩ y2 ϩ y3 ϩ y4)Ј

738 Appendix E (b) (c) (0 0 1 0 1) Sh Su V , St ′ 0 00 0 0 0 0 011010 1 0 0 0 0 0 0 110100 1 1 C′ 0 C0 0 0 0 1 101000 1 0 S0 StV ′ C 1 Su Sh Su 0 0 1 1 010000 0 S5 C′ 0 0 0 0 110001 1 Sh S1 0 0 0 1 100010 1 0 0 1 1 000100 0 C′ Sh 0 0 0 0 100101 remainder ϭ 1 quotient ϭ 5 S4 S2 C′ C C′ S3 C Su Sh Sh Su (d) After five shifts, the division is complete. C Su 18.8 (a) xin ϭ KЈ1KЈ2aЈ ϩ KЈ1K2b ϩ K1KЈ2(a ⊕ b) ϩ K1K2a yin ϭ KЈ1KЈ2b ϩ KЈ1K2a ϩ K1KЈ2 и 0 ϩ K1K2 и 1 (b) Use the state graph of Figure 18-6(b), with nine states total. (c) a 00 xin b 00 yin b 01 a 01 a 0 10 b 10 1 11 a 11 k1 k2UNIT 19 Study Guide Answers 1. (b) Z1, Z2, Z4 (for both charts) (d) 2. (a) Clock0 0 0 0 1 1 1 0 0 C ϭ 0, Sh State S0 S0 S1 S2 S000 0111000 C ϭ 0, Sh X00 1110000 C ϭ 1, Su00 0100001 C ϭ 0, Sh Za00 1000010 C ϭ 0, Sh01 0000100 C ϭ 1, Su Zb00 0110101 (result) 3. (a) Aϩ ϭ BX Bϩ ϭ AЈX ϩ BX Zc Z1 Z2

Answers to Selected Study Guide Questions and Problems 739UNIT 19 Answers to Problems 19.2 19.1 S0/ P 01 S3/ 10 X 10 Z D X Q S1/ Z10 01 F 10 X E S Z S2/ R 10 (1) (2) X Z19.3 Clock State S0 S1 S2 S1 S1 S2 S3 M K Ad Sh

740 Appendix E 19.4 S0/ 01 St S1/ 10 M Ad Sh ... S4/ 1M 0 Ad Sh 19.5 S0/ 01 1 N 0 X S1/ Z 01 S2/ X 0 Z 0 K Z 1 X 10 1 K 01 K

Answers to Selected Study Guide Questions and Problems 74119.6 S0/01 1 St 0 CSh VS1/10 Sh CSu 1 0 K S2/0 C 1 Su19.7 (a) Qϩ0 ϭ QЈ0QЈ1Q2CЈ ϩ Q0QЈ1 ϩ Q0QЈ2 Qϩ1 ϭ Q0QЈ1Q2CЈ ϩ Q0Q1QЈ2 Qϩ2 ϭ QЈ0QЈ1QЈ2St ϩ Q0QЈ2CЈ ϩ Q0QЈ1Q2C Load ϭ QЈ0QЈ1QЈ2St, Su ϭ Q0C, Sh ϭ QЈ1Q2CЈ ϩ Q0QЈ2CЈ, V ϭ QЈ0QЈ1Q2C (These equations could be further simplified using don’t-cares.) (b) Qϩ0 ϭ QЈ0Q1M ϩ QЈ0Q1MЈK ϩ Q0Q1K` Q1ϩ ϭ QЈ0QЈ1St ϩ QЈ0Q1MЈKЈ ϩ QЈ0Q1M ϩ Q0Q1KЈ Load ϭ Q0ЈQ1ЈSt, Sh ϭ Q0Q1 ϩ QЈ0Q1MЈ, Ad ϭ QЈ0Q1M, Done ϭ Q0QЈ119.8 (a) Aϩ ϭ AЈBЈC и RbЈDЈ711DЈ2312 ϩ ABЈCЈ ϩ ABЈ и Rb ϩ ABЈEqЈDЈ7 Bϩ ϭ AЈBЈC и D711 ϩ AЈB и ResetЈ ϩ ABЈC и RbЈEqЈDЈ7 Cϩ ϭ AЈBЈRb ϩ AЈBC и ResetЈ ϩ BЈCЈRb ϩ ABЈC и RbЈEqЈD7 Roll ϭ BЈC и Rb Sp ϭ AЈBЈC и RbЈDЈ711DЈ2312 Win ϭ AЈBCЈ Lose ϭ AЈBC(These equations could be further simplified using don’t-cares.)(b) If the input from the adder is S3S2S1S0, then the equations realized by the test logic block areD7 ϭ S2S1S0 D711 ϭ S1S0(S2 ϩ S3) D2312 ϭ SЈ3SЈ2 ϩ S3S219.9 (a) Aϩ ϭ BX Za ϭ AЈBЈ Z1 ϭ ABXЈ Bϩ ϭ AЈX ϩ BX Zb ϭ AЈB Z2 ϭ ABX Zc ϭ AB

742 Appendix E XAB Aϩ Bϩ Za Zb Zc Z1 Z2 1-1 1 100000 10- 0 100000 - 00 0 010000 - 01 0 001000 - 11 0 000100 011 0 000010 111 0 000001 19.10 (a) Clock State S0 S0 S1 S2 S1 S1 S2 X1 X2 X3 Z1 Z2 Z3 (b) D1 ϭ QЈ1XЈ1XЈ2X3 ϩ Q2XЈ2 D2 ϭ QЈ2X1 ϩ QЈ1QЈ2XЈ2XЈ3 ϩ Q2X2 Z1 ϭ QЈ2XЈ1 ϩ Q1 Z2 ϭ QЈ1QЈ2X1 Z3 ϭ QЈ1XЈ1X2 ϩ Q2 (c) Q1 Q2 X1 X2 X3 D1 D2 Z1 Z2 Z3 001 - - 01010 0001 - 00101 00001 10100 00000 01100 01 - 0 - 10001 01 - 1 - 01001 100 - - 00100 101 - - 01100 (d) 25 ϫ 5 ROM D1 D2 Z1 Z2 Z3 Q1 Q2 X1 X2 X3 01100 00000 10100 00001 00101 00010 00101 00011 01010 00100

Answers to Selected Study Guide Questions and Problems 743UNIT 20 Study Guide Answers 1. (a) lines 15 and 16 The full adder is combinational logic. Lines 34 and 35, which are in clocked process because it is a clocked register (b) In line 31, change clk ϭ ‘0’ to clk ϭ ‘1’. 2. (a) So we can use the overloaded “ϩ” operator The change from state 9 to state 0 To make the result be 5 bits Lines 35 and 36 will execute when State is 2, 4, 6, or 8. (b) ACC is uninitialized and is not loaded until St ϭ ‘1’ at a rising clock edge. When Done ϭ 1, i.e., in state 9, 160-180 ns. (c) X ϭ 101111001, 60 ns (d) Mcand ϭ 1101, Mplier ϭ 1011, and product is 10001111 ϭ 143 (e) Line 19 To avoid having to set them to 0 in each case where they are not 1.When they are set to 1, it overrides line 22 because these are sequential statements. ACC Ͻϭ “00000” & Mplier; Because it is a clocked register that is updated on the rising clock edge. The process executes on the rising clock edge, and when state is 9 at the rising clock edge, it is too late; the state is about to change to 0. The process of lines 20–34 is not clocked; it executes when State changes to 9. (f) Whenever the value of count changes. Lines 51 and 52. 10 ns ϩ ⌬. Sequential statements execute in 0 time, so A and B update simultaneously. (g) At time 60 ns, we are in state 2 when K ϭ 0, so Sh ϭ 1. So A ϭ 00B16 ϭ 0000010112 shifts to the right to become 00516 ϭ 0000001012. At time 140 ns, we are in state 1 and M ϭ 1, so Ad ϭ 1. So we add the multipicand, 0000010112, to A ϭ 00616 ϭ 0000001102 to get 01116 ϭ 0000100012. 3. (a) 0; 1 C should be 1 iff we can subtract, i.e., Dividend(8 downto 4) Ͼ Divisor.UNIT 20 Answers to Problems 20.1 First process executes at t ϭ 2 ns. Lines 22–25 execute. Second process executes at t ϭ 10 ns. Lines 38–40 and 43 execute. Because the state changes, first process executes again at 10 ϩ ⌬ ns. Lines 22–23 and lines 27–30 execute. 20.2 entity complementer is Port (clk, n: in std_logic; Regout: out std_logic_vector(15 downto 0)); end complementer; architecture Behavioral of complementer is signal State, NextState: integer range 0 to 2 :ϭ 0; signal count: std_logic_vector(3 downto 0) :ϭ “0000”;--4-bit counter

744 Appendix E signal X, Z, Sh: std_logic; signal K: std_logic :ϭ ‘0’; signal Reg: std_logic_vector(15 downto 0); begin Regout Ͻϭ Reg; X Ͻϭ Reg(0); K Ͻϭ ‘1’ when count ϭ “1111” else ‘0’; process (State, X, N, K) begin case State is when 0 ϭϾ if N ϭ ‘0’ then NextState Ͻϭ 0; Sh Ͻϭ ‘0’; Z Ͻϭ ‘0’; elsif X ϭ ‘1’ then NextState Ͻϭ 2; Sh Ͻϭ ‘1’; Z Ͻϭ ‘1’; else NextState Ͻϭ 1; Sh Ͻϭ ‘1’; Z Ͻϭ ‘0’; end if; when 1 ϭϾ Sh Ͻϭ ‘1’; if K ϭ ‘1’ then NextState Ͻϭ 0; if X ϭ ‘1’ then Z Ͻϭ ‘1’; else Z Ͻϭ ‘0’; end if; elsif X ϭ ‘0’ then NextState Ͻϭ 1; Z Ͻϭ ‘0’; else NextState Ͻϭ 2; Z Ͻϭ ‘1’; end if; when 2 ϭϾ Sh Ͻϭ ‘1’; if K ϭ ‘1’ then NextState Ͻϭ 0; if X ϭ ‘1’ then Z Ͻϭ ‘0’; else Z Ͻϭ ‘1’; end if; elsif X ϭ ‘0’ then NextState Ͻϭ 2; Z Ͻϭ ‘1’; else NextState Ͻϭ 2; Z Ͻϭ ‘0’; end if; end case; end process; process (clk) begin if clk’event and clk ϭ ‘1’ then if Sh ϭ ‘1’ then Reg Ͻϭ Z & Reg(15 downto 1); count Ͻϭ count ϩ 1; end if; State Ͻϭ NextState; end if; end process; end Behavioral; 20.4 entity test is end test; architecture Behavioral of test is component sm17_2 is Port (x,clk: in std_logic; z: out std_logic); end component; constant N: integer:ϭ 40;

Answers to Selected Study Guide Questions and Problems 745 signal flag: std_logic:ϭ ’0’; signal clk: std_logic:ϭ ’1’; signal x,z: std_logic; constant x_seq: std_logic_vector(1 to 40) :ϭ (“0000100001001100001010100110111000011001”); constant z_seq: std_logic_vector(1 to 40) :ϭ (“1100001010100110111000011001010111010011”); begin sm1: sm17_2 port map(x,clk,z); clk Ͻϭ not clk after 10 ns; -- clock has 20 ns period process begin for i in 1 to N loop x Ͻϭ x_seq(i); wait for 5 ns; -- wait for z to become stable if z ϭ z_seq(i) then flag Ͻϭ ’0’; else flag Ͻϭ ’1’; end if; wait until clk’event and clk ϭ ’1’; wait for 5 ns; end loop; end process; end Behavioral;20.5 Product Down Counter 8Add Ld Add Dec Mplier (3:0)Init Clr Accumulator (7:0) Init LdClk 8 8 Clk 4 K Sum MplierData Control Adder Add Circuit Done Start Init 4Init Ld Start′/0 Mcand (3:0) Clk 4 S0 McandData Start/Init Start′/0 S2 S1 K′/Add Start/Done K/Done

746 Appendix E 20.6 entity prob20_6 is Port (st, clk: in std_logic; X: in std_logic_vector(7 downto 0); Z: out std_logic_vector(9 downto 0)); end prob20_6; architecture Behavioral of prob20_6 is signal State, NextState: integer range 0 to 3 :ϭ 0; signal lda, ldb, ldc, ad: std_logic; signal B, C: std_logic_vector(7 downto 0); signal A: std_logic_vector(9 downto 0); signal sumAB: std_logic_vector(8 downto 0); signal sumABC: std_logic_vector(9 downto 0); begin sumAB Ͻϭ (“0”&A(7 downto 0)) ϩ B; sumABC Ͻϭ (“0”&sumAB) ϩ C; Z Ͻϭ A; process (st, State) begin lda Ͻϭ ‘0’; ldb Ͻϭ ‘0’; ldc Ͻϭ ‘0’; ad Ͻϭ ‘0’; case State is when 0 ϭϾ if st ϭ ‘1’ then lda Ͻϭ ‘1’; NextState Ͻϭ 1; else NextState Ͻϭ 0; end if; when 1 ϭϾ ldb Ͻϭ ‘1’; NextState Ͻϭ 2; when 2 ϭϾ ldc Ͻϭ ‘1’; NextState Ͻϭ 3; when 3 ϭϾ ad Ͻϭ ‘1’; lda Ͻϭ ‘1’; NextState Ͻϭ 0; end case; end process; process(clk) begin if clk’event and clk ϭ ‘1’ then if lda ϭ ‘1’ then if ad ϭ ‘1’ then A Ͻϭ sumABC; else A Ͻϭ (“00” & X); end if; elsif ldb ϭ ‘1’ then B Ͻϭ X; elsif ldc ϭ ‘1’ then C Ͻϭ X; end if; State Ͻϭ NextState; end if; end process; end Behavioral;

References 1. Ashenden, Peter J. The Designer’s Guide to VHDL, 2nd ed. San Francisco: Morgan Kaufmann Publishers, 2002. 2. Bhasker, J. A Guide to VHDL Syntax. Upper Saddle River, NJ: Prentice-Hall, 1995. 3. Bhasker, J. VHDL Primer, 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 1999. 4. Brayton, Robert, et al. Logic Minimization Algorithms for VLSI Synthesis. Secaucus, NJ: Springer, 1984. 5. Givone, Donald D. Digital Principles and Design. New York: McGraw-Hill, 2003. 6. Katz, Randy H. and Gaetano Borriello. Contemporary Logic Design, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2004. 7. Mano, M. Morris. Digital Design, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 2001. 8. Mano, M. Morris and Charles R. Kime. Logic and Computer Design Fundamentals, 4th ed. Old Tappan, NJ: Pearson Prentice Hall, 2008. 9. Marcovitz, Alan B. Introduction to Logic Design, 2nd ed. New York: McGraw- Hill, 2002.10. McCluskey, Edward J. Logic Design Principles. Upper Saddle River, NJ: Prentice Hall, 1986.11. Miczo, Alexander. Digital Logic Testing and Simulation, 2nd ed. New York: John Wiley & Sons, Ltd West Sussex, England, 2003.12. Patt, Yale N. and Sanjay J. Patel. Introduction to Computing Systems: From Bits and Gates to C and Beyond, 2nd ed. New York: McGraw-Hill, 2004.13. Roth, Charles H. Jr. and Lizy Kurian John. Digital Systems Design Using VHDL, 2nd ed. Toronto, Ontario: Thomson, 2008.14. Rushton, Andrew. VHDL for Logic Synthesis, 2nd ed. West Sussex, England: John Wiley & Sons, Ltd, 1998.15. Wakerly, John F. Digital Design Principles & Practices, 4th ed. Upper Saddle River, NJ: Prentice Hall, 2006.16. Weste, Neil and Kaamran Eshraghian. Principles of CMOS VLSI Design, 2nd ed. Reading, MA: Addison-Wesley, 1993. 747

Index 74163, 561–563 Arithmetic, binary, 12–15. 74178, 380 See also Addition, Subtraction, Multiplication, Division. A Accumulator ASCII code, 22–23, 240–241 ASIC, 491 parallel, 356–358 ASM chart. See SM chart. serial, 594–596 Associative law, 40–41 Active low, 253, 334 clear and preset inputs 334–335, Asynchronous clear (ClrN), 334–336, 355, 366 555–556 Adder, binary, 100–101 VHDL, 555 Asynchronous preset (PreN), 334–336 parallel, 104–105 Asynchronous sequential circuit, 336 parallel with accumulator, 356–358 serial, 404–405 B serial with accumulator, 594–596 Base (number systems) 9 VHDL serial adder, 650–651 Addition, binary, 12 conversion, 9–12 1’s complement, 19–20 Bi-directional I/O Pin, 256 2’s complement, 17–19 Algebraic simplification, 68–70, 127–128 VHDL, 306 theorems 42–43, 55 Binary addition. See Addition, binary. Algorithmic state machine. See State Binary numbers machine. conversion to decimal, 10–11 Alphanumeric state graph notation, 448–450 signed, 16–17 Alternative gate symbols, 201 Binary subtraction. See Subtraction, circuit conversion using, 201–204 binary. Analog systems, 6 Binary-coded-decimal (BCD), 20 AND BITLIB, 278, 619 Boolean algebra, 33–47, 58–68 gate, 35 operation, 36 basic operations, 35–37 VHDL, 286 basic theorems, 39–40 laws and theorems, 55 simplification theorems, 42–43748

Boolean expressions, 36–37 Index 749Borrow, 13–14, 106–107Buffer, 253–254 Contact bounce, 326–327 Control circuit three-state (tri-state) 254–255Bus, 253, 355 for dice game, 632–633 for divider, 605 merger 606 for multiplier, 600–602 three-state (tri-state) 255–256, 355–356 for serial adder, 594–597 splitter 607 Conversion of gate circuits, 200–204 VHDL 304–305 Converting English sentences to BooleanC equations, 90–91Carry, 12 Counters, 333–345 end-around, 19–21 binary, 362–366 flip-flop, 404, 595–596 design using D flip-flops, 370–371Characteristic equations, 309 design using J-K flip-flops, 373–374Clear input design using S-R flip-flops, 371–373 asynchronous, 334–336 design using T flip-flops, 367–370 synchronous, 560, 561 fully synchronous, 561Clocked sequential circuit ripple, 344, 362 analysis 395–411. up-down, 364–365 See also Sequential circuit. VHDL, 560–563CMOS Logic, 675–679 CPLD, 268–269, 525–526Code converter sequential circuit design using, 525–528 hexadecimal to ASCII, 262 Cyclic shift register, 358–359 sequential, 515–523 VHDL, 558–559 sequential in VHDL, 565Codes (BCD, 8-4-2-1, 6-3-1-1, excess-3, D D (delay) flip-flop, 328–330 Gray, 2-out-of-5, weighted), 21–23Combinational circuit CMOS, 680 derivation of input equations, 364, 370, 485 definition, 7 modeling in VHDL, 554–555 design, 92–93, 219–220 with clock enable, 335–337 testing, 229, 231 Data path, 644Commutative law, 40 Data selector. See Multiplexer.Comparator, 519–522 Debouncing switches, 326 VHDL, 301 Decimal numbersComplementation, 35, 45–47 binary codes for, 21–22Computer-aided design (CAD), 284, conversion to binary, 9–11 Decoder, 256–258 536–538 Decomposition of switching functions,Configurable logic block (CLB), 270–271 271–273 Xilinx Virtex / Spartan II, 536–538 Degenerate forms, 199Consensus theorem, 55, 66–68 Delay dual, 67 inertial, 225, 289, 682 illustrated by map, 133 transport, 225, 289, 682

750 Index Delta (⌬) delay, 287, 307 F DeMorgan’s laws, 47–49 Factoring, 45–46, 62 Dice game, 631–639 False output, 399–400, 406–408 Fan-in, 220 VHDL, 662–664 Digital systems, 6–8 reduction of, 220–222 Flip-flop design with FPGA, 437–538 Distributive law, 42 characteristic equation, 326 Divider, parallel binary, 602–607, 630 clear, preset inputs, 334–336 D, 328–330 VHDL, 662–664 D-CE, 335 Division definition, 322 edge-triggered, 328–330 binary, 15, 602–607 J-K, 332–333 Don’t care minterm, 99–100 master-slave, 331 Don’t care term modeling using VHDL, 544–557 S-R, 331–333 in Karnaugh map, 135 T, 333–334 in prime implicant chart, 173–174 type conversion, 334 Dual, 48 Flip-flop input equations, derivation Dynamic hazard. See Hazards. D, 364, 370, 485, 493–494 J-K, 373–374, 484–486 E S-R, 371–373, 486 EEPROM, 261 summary, 374–377, 484 Encoder, priority, 258 T, 362–363, 368–370 Equation Flowchart, 632–633 FPGA, 270–271, 535–536 proving validity, 70–72 sequential circuit design using, Equivalence gate, 65–66 Equivalent sequential circuits, 537–538 FPLA, 266 481–482 Full adder, 104–105 by implication table, 481–482 definition, 481 implemented using a PAL, 268 determination of, 481 VHDL, 293–296 Equivalent states, 476–478 Full subtracter, 106–107 definition, 476 Function block, 268 in SM chart, 635 Function generator, 270–271 theorem, 477 Functionally complete, 196 Espresso-II method, 176 Essential prime implicant G definition, 138, 169 Gate circuits, 46 from Karnaugh map, 138–141 from prime implicant chart, 169 multi-level, 190–194, 200–201 multiple output, 206–207 multiple-output, 204–206, 219–221 proof, 689 two-level NAND and NOR, 197–200 Exclusive-OR, 64–65 Gate delays, 191, 222–223 Exclusive-NOR gate, 66 Expansion theorem, 272–273

Gate level, 190–192 Index 751Gates J AND, 36 J-K flip-flop, 332–333 equivalence, 65–66 exclusive-or, 64 derivation of input equations, 373–374, NAND. See NAND gate. 484–486 NOR. See NOR gate. OR, 36 master-slave, 333 transmission, 678 VHDL, 508–509Glitches, 224–225, 229, 400, 446–447. See also False outputs. K Karnaugh map, 129–144HHalf adder, 81, 115, 314 3-variable, 129–133Hardware description languages (HDLs), 4-variable, 133–141 5-variable, 141–144 264, 537. See also VHDL. complementation, 132Hazards, 224–229 multiple-output minimization, 204–207Hexadecimal number, 9, 12 other forms, 146Hi-Z (high impedance), 230, 254, 304Hold time, 329–330 LIEEE standard logic, 304, 570 Laboratory testingI combinational circuits, 229–231Implicant sequential circuits, 531–536 Latch definition, 136, 168 CMOS, 679–680Implication table (chart), 478–481 definition, 322Incompletely specified function, 99–100 Gated D, 327 S-R, 323–327 simplification, 135, 173–174 transparent, 327Incompletely specified sequential circuits, unwanted in VHDL processes, 574 VHDL model, 555 483–484 Left shift registerInertial delay, 225, 289, 682 VHDL, 510Integrated circuits Link path, 626, 636 Literal design and layout, 491 definition, 38 in combinational circuit design, elimination of, 69 VHDL, 300 230–250 LogicAid, 124, 163, 218, 429, 513, MOS, CMOS, 675–680 SSI, MSI, LSI, VLSI, 250 536, 639 TTL, 561 Lookup table (LUT), 270–271, 667Interconnect array (IA), 268–269 Looping terms on a Karnaugh map, 129–131Inverter, 35, 201, 676, 677Iterative circuits, 519–522 M definition, 519 Macrocell, 268–269, 525–529 design, 519–522 Xilinx CoolRunner, 527

752 Index Manchester code, 445–447 Multiplexer (MUX), 251–253 Map-entered variables, 174–176, 639 data selection, 252–253 Maxterm VHDL, 290–292 definition, 94 Multiplication, binary, 14, 598–601 Maxterm expansion, 93–96 Multiplier, parallel binary, 598–601, 631, general form, 97–98 636–637 simplification of, 128 VHDL, 652–654 Mealy machine, 398 Multiplying out, 44, 62–64 design, 431 general model, 408–409 N state table and graph, 403 NAND gate, 195 VHDL model, 565–567 Mealy sequential circuit. See Mealy CMOS, 678 functionally complete, 196 machine. multi-level circuits, 200–201 Metal-oxide semiconductor. See MOS. two-level circuits, 197–200 Minimum product of sums, 128 Nanosecond, 222 Negative logic, 556, 676 from Karnaugh map, 135 Negative number representation, 16–18. See Minimum sum of products, 127, 137 also One’s complement, Two’s from Karnaugh map, 132, 135 complement. from prime implicant chart, sign and magnitude, 16 Next state, 325 169–171 equation, 326 Min-max delay, 532 map, 367–368 Minterm Nominal delay, 532 NOR gate, 195 definition, 93 CMOS, 678 Minterm expansion, 93–96 multi-level circuits, 200–201 two-level circuits, 197–200 general form, 96–99 NOT gate. See Inverter. simplification of, 130 NRZ, NRZI codes, 445–446 Moore machine, 398 Number systems, 8–12 design, 433–435 state table and graph, 368–369 O general model, 410–411 One’s complement Moore sequential circuit. See Moore addition, 19–21 machine. representation of negative number, 16–18 MOS logic, 675–680 One-hot state assignment, 495–497, 605 MOSFET, 675 OR gate, 36 Overflow n-channel, 675 division, 604–605 p-channel, 675 one’s complement addition, 19–21 Multi-level gate circuits two’s complement addition, 18–19, design, 190–194, 206–208 NAND and NOR gates, 200–201 105–106 Multiple-output gate circuit design, 192–195, 206–228 determination of essential prime implicants, 206–207

Index 753P ROM (read-only memory), 259–262PAL (Programmable Array Logic), 266–267 in sequential circuit design, 522–524, 638 in sequential circuit design, 525 VHDL, 300, 570–571Parallel adder, 104Parity, 395 RZ code, 445Parity checker S sequential, 395–397 Schematic capture, 536PC board layout, 537 Sequence detector design, 431–440,Petrick’s method, 171–172Phase-locked loop, 445 475–476PLA, 263–266 Sequential circuit in sequential circuit design, 523–525, definition, 7 636–638 Sequential circuit. See also State graph, table, 264–266 State machine, State table, MealyPLD, 263 sequential circuit, Moore sequential circuit, State assignment. programming, 269, 536 analysis, 395–411Positive logic, 625 design with a PAL, 525Present state, 325 design with flip-flops, 484–486, 514–518Prime implicant. See also Essential prime design with PLA, 523–525 design with ROM, 523–525 implicant. general model, 408–411 chart, 168–170 testing, 531–536 definition, 136, 168 timing charts, 399–400 from Karnaugh map, 136–137 unused state, 381, 422Product of sums (POS), 45 Serial adder. See Adder, serial. standard, 94 Serial dataProgrammable array logic. See PAL. code conversion, 444–447Programmable logic array. See PLA. transmission of, 444–445Programmable logic device, 263–268 Set-Reset (S-R) flip-flop, 331–332PROM, 261–262 derivation of input equations, 371–372, 486 compared with PLA, 266 Setup time, 329–330, 410 programmer, 262 Seven-segment indicator, 236Proofs of theorems, 689–690 Shift register, 358–362Propagation delay, 222, 329, 410 cyclic, 558 VHDL, 558–560Q Sign and magnitude, 16Quine-McCluskey method, 165–174 Signal tracing, 397 Simplification. See Algebraic simplification.R SimUaid, 318–320, 379, 537Radix, 9 SimulationRedundant states, elimination of, logic circuits, 229–331 sequential circuits, 531–536 474–475 VHDL, 307–308Register transfers, 355–356Registers, 354–362Ripple counters, 344, 362

754 Index SM block, 626 Switching algebra, 34. See Boolean algebra. SM chart (State machine chart), 625–639 Switching circuit derivation, 630–636 definition, 7 for binary divider, 630 Switching function for binary multiplier, 631 for dice game, 631–635 decomposition of, 271–273 realization, 635–639 Synchronizer, 535 Stable state, 323, 325 Synchronous sequential circuit. See Standard product of sums, 94 Standard sum of products, 93 Sequential circuit. State assignment for sequential circuits, Synthesis, 302, 307–308 487–497 tools, 537, 572–575 equivalent assignments, 487–490 guidelines, 490–495 T one-hot, 495–497 T (toggle) flip-flop, 333–334 State equivalence theorem, 477, 689–690 State graph derivation of input equations, 362–363, alphanumeric notation, 448–450 367–370 conversion to SM chart, 628–629 derivation, 431–444 Test generation, 537 for control circuits, 597–598, Testing of circuits. See Laboratory testing. Three-state buffer 253–256. See also 600–601, 605 for counter, 365, 367, 370 Tri-state buffer. guidelines for construction, 439–443 Three-state bus 255–256. See also Tri-state Mealy, 403–404 Moore, 402 bus. State machine, 435, 495, 570. See also Timing chart (diagram), 222–223 Sequential circuit. for counter, 369–370 design using SM charts, 625–639 for flip-flops, 329, 330 State table for latches, 325, 327 derivation of, 430–444 for sequential circuits, 397–400, 406–408 incompletely specified, 483 for SM chart, 629–630 Mealy, 403 Transients Moore, 401–402 in output, 224 reduction, 474–481 Transition table, 401–403 Static-0 hazard. See Hazards. Transmission gate (TG), 678 Static-1 hazard. See Hazards. Tri-state buffer. See also Three-state buffer. Subtracter VHDL, 304, 306 full, 106–107 Tri-state bus, 355–356. See also Three-state in binary divider, 604–607 Sum of products (SOP), 44 bus. standard, 94 Truth table, 38 Switches circuits of, 36–37, 39–40 construction, 100–103 TTL logic, 561 Two’s complement addition, 17–19 representation of negative numbers, 16–17 Two-level circuits, 46 AND-OR, 197–200 NAND-NAND, 197–200