B B.1 B.2 B.3 B.4 B.5
B.1 2 (Boolean algebra). 1854 An Investigation of the Laws of Thought on Which to Found the Mathematical Theories of Logic and Probabilities George Boole. 1938 MIT Claude Sannon [SHAN38]. Shannon.. :. :,. (variable) (operation).. 1( : TRUE) 0( : FALSE). AND, OR, NOT, dot(.), (1) overbar( _ ). A AND B 5 A B A OR B 5 A 1 B NOT A 5 2 A AND 1 1. OR 1 1. (unary operation) NOT.. D 5 A 1 (B 2 C) A 1, B 0 C 1 D 1. D
B 0.. AND OR. AND dot. B C AND, A OR. A + B. C = A + (B. C) = A + BC B.1 (truth table).. B.1 XOR, NAND, NOR. XOR(exclusive-or) 1. NAND AND NOT, NOR OR NOT. A NAND B 5 NOT (A AND B) 5 2 AB A NOR B 5 NOT (A OR B) 5 A 1 B. B.2 (identity). AND OR (complementary), (dual). : ( 3
),... A 1 (B C) 5 (A 1 B) (A 1 C) (DeMorgan s theorem),. A NOR B = 2 A AND 2 B A NAND B = 2 A OR 2 B B.2 A, B, C (1 0). B.2... AND, OR, NOT, NAND, NOR. B.2. (,, ). IEEE IEEE std 91. NOT (circle).., ( ). B.3. B.1 3, 4. X 1 Y 1 Z OR... (functionally complete set)... AND, OR, NOT AND, NOT OR, NOT NAND NOR 4
B AND, OR, NOT.. AND NOT AND NOT OR.. A 1 B 5 2 A 2 B A OR B 5 NOT((NOT A) AND (NOT B)) OR NOT AND. B.2 NAND AND, OR, NOT, B.3 NOR. NAND NOR.,.., 5
. B.3,., (gate delays). n 2 m 2.. : 2 n m. 6
B :. :... B.3. F 1 A, B, C. F 5 2 A BC 2 1 2 A BC 1 ABC 2 (B.1) F 1, 1. (B.1) (Sum Of Products). B.4 AND, OR, NOT.. SOP 1 (true) 1. 0 true 1., F 5 (A 22 B 2 C ) (A 22 B C) (AB 22 C ) (AB 2 C) (ABC). (X Y Z) 5 2 X + 2 Y + 2 Z, F 5 (A 2 2 2 1 B 1 C ) (A 2 2 1 B 1 2 C ) (A 2 1 2 2 B 1 C ) (A 2 1 2 B 1 2 C ) (A 2 1 2 B 1 2 C ) 7
5 (A 1 B 1 C) (A 1 B 1 C 2 ) (A 2 1 B 1 C) (A 2 1 B 1 C 2 ) (A 2 1 B 2 1 C 2 ) (B.2) (Product Of Sums), B.5., NOT.,.,., SOP POS. 1 0. SOP 1, POS 0.. SOP POS.. ( ).. (Algebraic simplification) (Karnaugh map) Quine-McKluskey B.2., (B.1). 8
B F 5 A 2 B 1 BC 2, F 5 B(A 2 1 C 2 ) B.6. (B.1) (observation).. (Karnaugh Map) (4 6 ). n 2 2 n (square). B.7a 2 4. 00 01 11 10.,. 8,, ( B.7b). 4 B.7c 16. 9
. SOP, 1, NOT 0. B.7a AB 2, 1. 2 ( B.7a) AB 2 1 2 A B. B.7b B.3., :., (B.3), (B.1). B.7d. A A 1., A A 0. B, C, D. 1,.., 1,. B.8a 1 2 A BC 2 D 2 A BCD.. 2 A BC 2 D 1 2 A BCD 5 2 A BD..,. B.8b c., 2 n (, 4, 8 ). B.8,. 8,. 10
B. 1. (1 ), 1, 2, 4, 8, (circle). 2.,..,,,., 1. 3.,,,, ;,. 11
B.3 B.9a. 1., 1. B.9b.,..,. don t care. d., 1 0. [HAYE88] : 10 1. 9.2, 10 10 4-., 0 5 0000, 1 5 0001,..., 9 5 1001. 4, 1010 1111. Binary Coded Decimal(BCD). B.4 4 BCD 1 4. modulo 10( 10 )., 9 1 1 5 0. BCD don t care. B.10. d. Quine-McKluskey 4. 5 16 3 16, 12
B 3. 6 4 16 3 16 4., Quine-McKluskey.. 13
.. ABCD 1 ABC 2 D 1 ABC 2 D 2 1 AB 2 CD 1 A 2 BCD 1 A 2 BCD 2 1 A 2 BC 2 D 1 A 2 B 2 C 2 D,. (row) (term). (complemented variables).,,,,.... B.5.., 1, 0. 1. (index column) 10,..,, 0 1.,,.,,.... ( ), ( )., 2 A BCD 2 2 A BCD ABC..,. 2 A 2 C D ABC 2 ABD BC 2 D ACD 2 A BC BCD 2 A BD 14
B..,,., : BD...,. B.6 (matrix). (row) ( ). (column). (element), X.., X X (circle)., X X. X. X.,. ABC 2 1 ACD 1 2 A BC 1 2 A 2 C D.. Quine-McKluskey.. product. ABC + ABC AB., ABC 1 ABC 2 5 AB(C 1 2 C ) 5 AB,.,,.. 15
NAND NOR. NAND NOR.,. (B.3). F 5 B(A 2 1 2 C ), F 5 B(A 2 1 2 C ) 5 (A 2 B) 1 (BC 2 )., F = (A 2 B) (BC 2 ), B.11 NAND..,. B.12. 4-to-1. 4 D0, D1, D2, D3, F. (S1, S2) (select code). 16
B 4-to-1 B.7.., D0, D1, D2, D3. B.13 AND, OR, NOT. S1 S2 AND 0, S1 S2 AND. AND 0 1., OR 0, OR. 8-to-1 16-to-1. (routing). (PC). PC. 2 (binary counter): PC (instruction register): (direct address) 17
ALU : (displacement mode)., PC. PC. PC ( ). B.14 16.,. n 2 n. B.15 3 8. 18
B. (address decoding). 4 256 3 8 bit RAM 1 Kbyte.. Address Chip 0000-00FF 0 0100-01FF 1 0200-02FF 2 0300-03FF 3 8, 8. 10 2 4 RAM. B.16, 2-to-4., (demultiplexer)..,. B.17. n 2 n. 2 n AND. n, (0 1). 19
.. (Integrated Circuit, IC). 20
B B.18 10 SSI(Small-Scale Integration). (PCB).,.,, ( )...,. PLA(programmable logic array). PLA () SOP(sum-of-products). PLA NOT, AND, OR. NOT AND. AND OR, OR. SOP. B.19(a) 3 8, 2 PLA. PLA, 15 25 5 15. AND, AND OR,. PLA ( ). (intersection point) (fuse).. PLA Field-Programmable Logic Array(FPLA: ). (mask)., PLA. B.19b PLA. (memoryless).,,., - (Read-Only Memory, ROM). ROM (read)., 2 ROM 21
,. ROM ( ) (). ROM. ROM OR. B.8 22
B. 4 4. 16. 16 4 64 ROM. 4, 4. B.20 4-to-16 4 OR 23
. PLA,., ROM. (arithmetic).. 2 (carry). 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 10. B.9a... n.. B.21 4. 24
B (multiple-bit adder) 1 3,. B.9b,. (Sum) 5 2 A 2 B C 1 2 A BC 2 1 ABC 1 AB 22 C (Carry) 5 AB 1 AC 1 BC B.22 AND, OR, NOT. B.23.,.,.,,. (carry lookahead). 25
4.. C 0 5 A 0 B 0 C 1 5 A 1 B 1 1 A 1 A 0 B 0 1 B 1 A 0 B 0 (B.4) (B.5),. C 2 5 A 2 B 2 1 A 2 A 1 B 1 1 A 2 A 1 A 0 B 0 1 A 2 B 1 A 0 B 0 1 B 2 A 1 B 1 1 B 2 A 1 A 0 B 0 1 B 2 B 1 A 0 B 0. SOP,... n n 2 1 OR 2 n 1 1 n AND. B.23 4 8 32. 4 8, 32 1. B.4. ROM,.,.., (current state)..,. -. -,. - (bistable),., - 1 (1-bit memory). -. (complement) 26
B, Q Q 2. S-R B.24 S-R - S-R (S-R Latch). S(set) R(reset) Q 2 Q, (feedback) NOR.,. S R 0, Q 0. NOR Q 5 0 S 5 0. 2 Q 1, NOR 2 Q 5 1 R 5 0 Q 5 0. - S 5 R 5 0., R 5 S 5 0 Q 5 1, 2 Q 5 0. 1, Q (value). S R 1 0. Q 5 0, 2 Q 5 1, S 5 0, R 5 0. S 1, NOR S 5 1, Q 5 0, Dt 27
2 Q 5 0 ( B.25 )., NOR R 5 0, 2 Q 5 0. (Dt) Q 5 1. NOR S 5 1, Q 5 1, Q 0, S 5 1, R 5 0 Q 1., S 0. R. R 1, Q 2 Q Q 5 0, 2 Q 5 1. 2Dt. S-R (truth table) (character table),. S-R, Q, B.10a. S 5 1, R 5 1 (Q 2 Q 0). B.10b. S-R B.10c. 28
B S-R - S-R. (asynchronous operation). (clock pulse). B.26. clocked S-R flip-flop. R S NOR. D - S-R - R S 1.. D -. B.27 D -. AND. D - - (data flip-flop),. D -.,. - (delay flip-flop), 0 1. J-K - - J-K -. S-R - 29
.. B.28 J-K -, B.29 -. - S-R -.. J set 1, K reset 0. 1 (toggle),. Q 1 J K 1 Q 0. B.28. - CPU. CPU. (parallel register) (shift register). 30
B 1... B.30 8 D -. load D11 D18. (multiplexer),. (serial). B.31, 5 D -. -.,. (serial I/O device interface). ALU (logical shift) (rotate). / (parallel read/write circuit). 31
. 1. n - 2 n 2 1. 0. CPU (program counter). (synchronous) (asynchronous). - -. -., CPU.. (ripple counter).. B.32 J-K - 4 (timing diagram). (propagation delay). - (Q 0 ). - (cascade).. - J K 1. Q. (falling edge) ; 32
B - (edge triggered flip-flop)., (transition) -. 0000, 0001,..., 1110, 1111, 0000,..... CPU (synchronous counter). -. 3. 3 -. J-K -. - A, B, C, C. J, K ( B.33a).. A, B, C,. A, B, C, - A, B, C. B.33a J-K -. J K... ( ). (excitation table). B.33a., A B 0 C 0 1., 0 J 5 0 K don t care. 0 1 J 5 1, K 5 d.,. B.33a A, B, C J, K. 6. b 33
., Ja( A - J ) Ja 5 BC. 6, c. B.5 [GREG98]. [STON96] 34
B. ; [MANO04] [FARH04]. FARH04 Farhat, H. Digital Design and Computer Organization. Boca Ratan: CRC Press, 2004. GREG98 Gregg, J. Ones and Zeros: Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets. New York: Wiley, 1998. MANO04 Mano, M., and Kime, C. Logic and Computer Design Fundamentals. Upper Saddle River, NJ: Prentice Hall, 2004. STON96 Stonham, T. Digital Logic Techniques. London: Chapman & Hall, 1996. Problems B.1. a. 2 2 2 b. 2 2 2 2 2 c. 2 2 d. 2 2 B.2. a. 2 2 2 2 b. c. d. 2 2 B.3. a. b. 2 2 2 2 B.4. a. a. a. a. a. 2 2 a. 2 2 a. B.5. B.6. 35
B.7. B.8. a. b. c. d. B.9. B.10. B.11. B.12. 3 3 3 3 36
B B.13. B.14. a. b. 37