Bài giảng Digital Electronics - Bài 1 - Pham Ngoc Nam

Digital Electronics Dr. Pham Ngoc Nam 1/ 2 Acknowledgement The main part of the slides was adopted and modified from the original slides of Prof. Rudy Lauwereins, Vice president of IMEC, Leuven, Belgium with his permission. Your instructor Bộ môn kỹ thuật điện tử tin học Office: C9-401 Email: pnnam-fet@mail.hut.edu.vn Research: FPGA, PSoC , hệ nhúng Trí tuệ nhân tạo Education: K37 điện tử -ĐHBK Hà nội (1997) Master về trí tuệ nhân tạo 1999, Đại học K.U. Leuven , vương quốc Bỉ Đề tài : Nhận dạng chữ viết tay Tiến sỹ kỹ thuật chuyên ngành điện tử -tin học , 9/ 2004, Đại học K.U. Leuven -IMEC, Vương Quốc Bỉ Đề tài : quản lý chất lượng dịch vụ trong các ứng dụng đa phương tiện tiên tiến 1/ 4 Course contents Digital design Combinatorial circuits: without status Sequential circuits: with status FSMD design: hardwired processors Language based HW design: VHDL 1/ 5 Course contents Digital design Combinatorial circuits: without status Sequential circuits: with status FSMD design: hardwired processors Language based HW design: VHDL 1/ 6 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates 1/ 7 Contents of “Digital Design” Introduction to the course Course book Goal Exercises and laboratory sessions Exam Data representation Boolean algebra Logical gates 1/ 8 Contents of “Digital Design” Introduction to the course Course book Goal Exercises and laboratory sessions Exam Data representation Boolean algebra Logical gates 1/ 9 Course books Mandatory: “ Principles of Digital Design ”, Daniel D. Gajski, Prentice Hall, 1997, ISBN 0-13-301144-5 References: Douglas L. Perry, VHDL: Programming by Examples, McGraw-Hill, fourth Edition, 2002. “Logic and Computer Design Fundamentals”, M. Morris Mano & Charles R. Kime , Prentice Hall, 2nd edition, 2000, ISBN 0-13-016176-4 TS. Nguyễn Nam Quân : “ Toán logic và Kỹ thuật số ”, Nhà xuất bản khoa học và kỹ thuật , 2006 1/ 10 Contents of “Digital Design” Introduction to the course Course book Goal Exercises and laboratory sessions Exam Data representation Boolean algebra Logical gates 1/ 11 Goal of the course Give insight in the design of digital electronic systems at the gate and register-transfer level Teach the use of modern design tools Offer all building blocks needed to construct complex digital circuits, including processors Present the difference between functional requirements (operation) and non-functional requirements (cost, speed, power, area) Introduce modern implementation platforms: PLA, PLD, FPGA 1/ 12 Contents of “Digital Design” Introduction to the course Course book Goal Exercises and laboratory sessions Exam Data representation Boolean algebra Logical gates 1/ 13 Exercises and laboratory sessions Bài 1: Các phần tử logic cơ bản – Bộ chọn dữ liệu phân kênh Bài 2: Các Trigơ RS, D, JK – Bộ đếm LED 7 thanh Bài 3: Làm quen với phần mềm thí nghiệm thông qua một ví dụ thiết kế đơn giản Bài 4: Thiết kế bộ so sánh hai số 3 bit: Bài thí nghiệm này giúp sinh viên luyện tập tối thiểu hóa bìa Karnaugh 6 biến và biết cách thiết kế mạch logic tổ hợp từ các phần tử logic cơ bản Bài 5: Thiết kế bộ phát hiện tổ hợp bit trong một chuỗi bit: Giúp sinh viên biết cách xây dựng máy trạng thái và thiết kế hệ thông số bằng máy trạng thái Bài 6: Thực hiện thuật toán FIR dùng cấu trúc FSMD 1/ 14 Contents of “Digital Design” Introduction to the course Course book Goal Exercises and laboratory sessions Exam Data representation Boolean algebra Logical gates 1/ 15 Exam Close book Midterm exam: 30% Final exam: 70% Completing lab sessions is a must before taking the exam 1/ 16 Contents of “Digital Design” Introduction to the course Data representation Decimal, Binary, Octal, Hexadecimal Addition, subtraction, multiplication, division Negative numbers Integer, fixed point, fractional, floating point, BCD, ASCII Boolean algebra Logical gates 1/ 17 Contents of “Digital Design” Introduction to the course Data representation Decimal, Binary, Octal, Hexadecimal Addition, subtraction, multiplication, division Negative numbers Integer, fixed point, fractional, floating point, BCD, ASCII Boolean algebra Logical gates 1/ 18 Decimal 1234.567 10 = 1•1000+2•100+3•10+4•1+5•0.1+6•0.01+7•0.001 1•10 3 +2•10 2 +3•10 1 +4•10 0 +5•10 -1 +6•10 -2 +7•10 -3 r = radix (r = 10), d=digit (0  d  9), m = #digits before radix point (decimal point), n = #digits after decimal point 1/ 19 Binary 1011.011 2 = 1•8+0•4+1•2+1•1+0•0.5+1•0.25+1•0.125 1•2 3 +0•2 2 +1•2 1 +1•2 0 +0•2 -1 +1•2 -2 +1•2 -3 r = radix (r = 2), d = digit (0  d  1) , m = #digits before radix point (binary point), n = #digits after radix point 1/ 20 Octal 7654.32 8 = 7•512+6•64+5•8+4•1+3•0.125+2•0.015625 7•8 3 +6•8 2 +5•8 1 +4•8 0 +3•8 -1 +2•8 -2 r = radix (r = 8), d = digit (0  d  7) , m = #digits before radix point (octal point), n = #digits after radix point 1/ 21 Hexadecimal FEDC.76 16 = 15•4096+14•256+13•16+12•1+7•1/16+6•1/256 15•16 3 +14•16 2 +13•16 1 +12•16 0 +7•16 -1 +6•16 -2 r = radix (r = 16), d = digit (0  d  F) , m = #digits before radix point (hexadecimal point), n = #digits after radix point 1/ 22 Contents of “Digital Design” Introduction to the course Data representation Decimal, Binary, Octal, Hexadecimal Addition, subtraction, multiplication, division Negative numbers Integer, fixed point, fractional, floating point, BCD, ASCII Boolean algebra Logical gates 1/ 23 3 5 6 5 7 2 8 3 2 carry x y sum 8 8 0 1 0 Binary addition Binary addition Decimal addition carry x y sum 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1/ 24 Binary subtraction x y borrow result 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1/ 25 Binary multiplication 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 Multiplication by repeated add & shift: number of cycles = number of bits of multiplier Can be implemented in a faster way 1/ 26 Binary division 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 Division by repeated subtract & shift: number of cycles = number of bits of result Mostly done this way 1/ 27 Contents of “Digital Design” Introduction to the course Data representation Decimal, Binary, Octal, Hexadecimal Addition, subtraction, multiplication, division Negative numbers Integer, fixed point, fractional, floating point, BCD, ASCII Boolean algebra Logical gates 1/ 28 Sign-Magnitude representation Each number consists of two parts : sign and magnitude Decimal example: + 123 10 (by convention also ‘123’) and - 123 10 Binary: sign represented by MSB; ‘0’ = positive, ‘1’ = negative Binary example: 0 1100 2 = + 12 10 en 1 1100 2 = - 12 10 A sign-magnitude integer with n bits lies between -(2 n-1 -1) and +(2 n-1 -1) with two representations for 0: 0 00...0 en 1 00...0 Generic representation of a sign-magnitude integer: B = 1/ 29 Sign-Magnitude addition and subtraction Start addition Start subtraction s 2 =s’ 2 End m 1 <m 2 no m1>m2 no s 1 =s 2 yes m r =m 2 -m 1 s r =s 2 m r =0 s r =0 no m r =m 1 +m 2 s r =s 1 yes m r =m 1 -m 2 s r =s 1 yes 1/ 30 Sign-Magnitude addition and subtraction Multiplication and division are repeated add/subtract & shift and can hence be carried out with such an adder/subtractor Sign-magnitude representation leads to slow, expensive adder/subtractor due to repeated comparison and test of sign and magnitude This is why we represent numbers mostly using two’s complement notation 1/ 31 Two’s complement notation Radix-complement of a number D with m digits is D* = r m - D eg. The 10-complement of 123 10 is10 3 - 123 10 = 877 10 eg. The 2-complement of 1101 2 is2 4 - 13 10 = 3 10 = 0011 2 Call D’ the digit complement, then D*=D’+1 (proof in book); this offers us an easier way of determining the two’s complement: eg. The 2-complement of 1101 2 is0010 2 + 0001 2 = 0011 2 1/ 32 Two’s complement notation How do we negate a number D, i.o.w. how do we obtain -D? D* = r m - D  D* + D = r m = 0 when we retain only the m least significant digits  D* = -D eg. D=0011 2  D*=1100 2 +0001 2 =1101 2 D+D*=0011 2 +1101 2 =10000 2 =2 4 =0 when we retain only the m least significant bits; we may hence use D*=1101 2 for the binary representation of -D=-3 10 What is the negation of D=0000 2 ? D*=1111 2 +0001 2 =10000 2 =0000 2 There is only 1 notation for ‘zero’ A 2-complement integer with n bits lies between -(2 n-1 ) and +(2 n-1 -1) 1/ 33 Two’s complement notation Negating a 2-complement number requires many more bit-flips than negating a sign-magnitude number: sign-magnitude is less power hungry than 2-complement 1/ 34 Two’s complement addition and subtraction Start addition B r =B 1 +B 2 End Start subtraction B 2 =B’ 2 +1 The negation needed for the subtraction is done by taking the bit-complement of B 2 ; the addition of the ‘1’ is done by putting the LSB carry-in of the next addition to 1. 1/ 35 Two’s complement addition and subtraction 0010 +2 0100 +4 00 00 0 0110 +6 Addition + 0010 +2 1100 - 4 00 00 0 1110 - 2 + 1110 - 2 1100 - 4 11 00 0 1010 - 6 + 0010 +2 1011 (+4)’ 00 11 1 1110 - 2 Subtraction + 0010 +2 0011 (- 4)’ 00 11 1 0110 +6 + 1110 - 2 0011 (- 4)’ 11 11 1 0010 +2 + 0111 +7 0110 +6 01 10 0 1101 - 3 Overflow + 1001 - 7 1010 - 6 10 00 0 0011 +3 + 1/ 36 Contents of “Digital Design” Introduction to the course Data representation Decimal, Binary, Octal, Hexadecimal Addition, subtraction, multiplication, division Negative numbers Integer, fixed point, fractional, floating point, BCD, ASCII Boolean algebra Logical gates 1/ 37 Integer, fixed point, fractional, floating point Integer int: 101011.  m=6 int+int = int and m max(m 1 ,m 2 )+1 int•int = int and m=m 1 +m 2 Fixed point fix: 1101.010  i = 4, f = 3 fix+fix = fix and imax(i 1 ,i 2 )+1 & fmax(f 1 ,f 2 ) fix(i 1 ,f 1 )•fix(i 2 ,f 2 ) = fix and i=i 1 +i 2 & f=f 1 +f 2 How many bits are needed for ? m m 1 +log 2 16 How many bits are needed for ? m =16 • m 1 How many bits are needed for: ? i i 1 +log 2 16 & f=f 1 1/ 38 Integer, fixed point, fractional, floating point Fractional frac: 0.01101  f = 5 frac+frac = fix and fmax(f 1 ,f 2 ) frac•frac = frac and f=f 1 +f 2 Floating point float: 0. 1 1010•2^101  m = 5, e = 3 How many bits are needed for ? i log 2 16 & f=f 1 1/ 39 BCD B inary C oded D ecimal number 1/ 40 ASCII A merican S tandard C ode for I nformation I nterchange (7-bit code) 1/ 41 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 42 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 43 Axiomatic definition of Boolean algebra A1 (Closure): B is closed w.r.t. + (OR) B is closed w.r.t. • (AND) A2 (Identity element) B has an identity element w.r.t. +, designated by 0 B has an identity element w.r.t. •, designated by 1 A3 (Commutativity) B is commutative w.r.t. +, i.o.w. x+y=y+x B is commutative w.r.t. •, i.o.w. x•y=y•x 1/ 44 Axiomatic definition of Boolean algebra A4 (Distributivity) • is distributive w.r.t. +, i.o.w. x•(y+z)=(x•y)+(x•z) + is distributive w.r.t. •, i.o.w. x+(y•z)=(x+y)•(x+z) A5 (Complement element -- NOT operator) xB, x’B: x+x’=1 xB, x’B: x•x’=0 A6 (Cardinality bound) There exist at least two different elements in B 1/ 45 Axiomatic definition of Boolean algebra Differences w.r.t. ordinary algebra In ordinary algebra + is not distributive w.r.t. •:5+(2•4)  (5+2) • (5+4) In boolean algebra, an inverse operation for the addition (OR) does not exist, neither for the multiplication (AND); subtraction and division hence do not exist In ordinary algebra it is not true that x + x’ = 1 and x • x’ = 0 Boolean algebra works with a finite set of elements, whereas ordinary algebra has an infinite set 1/ 46 Axiomatic definition of Boolean algebra Two-valued Boolean algebra (defined by Shannon) AND operator OR operator NOT operator 1/ 47 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 48 Theorems of Boolean algebra Theorem 1: idempotency x + x = x x • x = x (Note the duality!!) Theorem 2 x + 1 = 1 Dual: x • 0 = 0 Theorem 3: absorption y • x + x = x (priority: • before +) Dual: (y + x) • x = x Theorem 4: involution (x’)’ = x 1/ 49 Theorems of Boolean algebra Theorem 5: associativity (x + y) + z = x + (y + z) Dual: (xy)z = x(yz) Theorem 6: De Morgan’s law (x+y)’ = x’y’ Dual: (xy)’ = x’+y’ Proof: using axioms or truth table Duality: Replace each OR by AND and AND by OR Replace each 0 by 1 and x by x’ 1/ 50 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 51 Boolean functions What: expression in binary variables and the operators AND, OR, NOT Priority: parenthesis NOT AND OR Eg. F 1 =xy+xy’z+x’yz F 1 =1 when x=1 and y=1 or when x=1, y=0 and z=1 or when x=0, y=1 and z=1; in all other cases F 1 =0 F 1 consists of 3 AND-terms and 1 OR-term 1/ 52 Boolean functions Realisation of F 1 =xy+xy’z+x’yz x y z F 1 1/ 53 Boolean functions Truth table for F 1 =xy+xy’z+x’yz n variables  2 n rows standard numbering x y z F 1 x y z F 1 x y z F 1 x y z F 1 x y z F 1 1/ 54 Boolean functions Building up a truth table using standard numbering: X Y Z 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1/ 55 Boolean functions Truth table for F 1 =xy+xy’z+x’yz numbering following the Gray code (two consecutive rows only differ in 1 variable) 1/ 56 Boolean functions Building up a truth table using the Gray code: X Y Z 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1/ 57 Boolean functions Complement of a Boolean function F 1 ’ =(xy+xy’z+x’yz)’ =(xy)’(xy’z)’(x’yz)’ (De Morgan) =(x’+y’)(x’+y+z’)(x+y’+z’) (De Morgan) This gives us the opportunity to convert an AND-OR implementation in an OR-AND implementation (see next slide) 1/ 58 Boolean functions Realisation as AND-OR: F 1 =xy+xy’z+x’yz Realisation as OR-AND: F 1 =((x’+y’) (x’+y+z’) (x+y’+z’))’ x y z F 1 x y z F 1 1/ 59 Boolean functions Algebraic manipulation F 1 =xy+xy’z+x’yz = xy + xyz +xy’z+x’yz (absorption) =xy+ x(y+y’)z +x’yz (distributive) =xy+x 1 z+x’yz (complement) =xy+ xz +x’yz (identity) =xy+ xyz +xz+x’yz (absorption) =xy+xz+ (x+x’)yz (distributive) =xy+xz+ 1yz (complement) =xy+xz+ yz (identity) This alternative form is cheaper (see next slide) There does not exist a fixed rule to combine theorems to guarantee a cheaper result Further slides will present a non-algebraic method that always leads to the cheapest solution 1/ 60 Boolean functions F 1 =xy+xz+yz F 1 =xy+xy’z+x’yz x y z F 1 x y z F 1 1/ 61 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 62 Canonical form How do we translate a truth table into a Boolean expression? Definition: a minterm is a Boolean function that is true in 1 row of the truth table and false elsewhere 1/ 63 Canonical form A 1-minterm is a minterm for which the function equals 1; a 0-minterm is a minterm for which the function equals 0 For F 1 =xy+xy’z+x’yz Each Boolean function can be expressed as the sum of its 1-minterms : F 1 =x’yz+xy’z+xyz’+xyz=m 3 +m 5 +m 6 +m 7 =  (3,5,6,7) 1/ 64 Canonical form Dual definition: a maxterm is a Boolean function that is false in 1 row of the truth table and true elsewhere 1/ 65 Canonical form A 0-maxterm is a maxterm for which the function equals 0; a 1-maxterm is a maxterm for which the function equals 1 For F 1 =xy+xy’z+x’yz Each Boolean function can be expressed as the product of its 0-maxterms:F 1 =(x+y+z)(x+y+z’)(x+y’+z)(x’+y+z) =M 0 M 1 M 2 M 4 =  (0,1,2,4) 1/ 66 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 67 Standard form -- minimal implementation in two layers In the canonical form each function is a sum of 1-minterms or a product of 0-maxterms Each minterm or maxterm contains all variables => expensive implementation The standard form is a sum of product terms or a product of sum terms with the smallest number of variables A product term or sum term does not necessarily contain all variables => cheaper implementation 1/ 68 Standard form -- minimal implementation in two layers Example 1 F 2 =xyz+xyz’+xy’z+xy’z’ =xy(z+z’)+xy’(z+z’) =xy+xy’ =x(y+y’) =x Example 2 F 3 =xyz+xyz’+xy’z+x’yz+x’y’z’ =xyz+xyz’+ xyz +xy’z+ xyz +x’yz+x’y’z’ =xy(z+z’)+x(y+y’)z+(x+x’)yz+x’y’z’ =xy+xz+yz+x’y’z’ 1/ 69 Standard form -- minimal implementation in two layers The standard form is the cheapest implementation in two layers Eg. F 2 =xy+xz+yz A non-standard form in more than two layers may be cheaper Eg. F 2 =x(y+z)+yz x z y F 2 Multiplier: O(e n ) x z y F 2 Multiplier: O(n 2 ) 1/ 70 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Axiomatic definition of Boolean algebra Theorems of Boolean algebra Boolean functions Canonical form Standard form The 16 functions of 2 variables Logical gates 1/ 71 The 16 functions of 2 variables Why 16 functions? There exist 4 possible combinations for x and y and each combination can have a different functional value. Each function F(x,y) is hence characterized by 4 bits, i.e. the 4 functional values for xy, xy’, x’y and x’y’. With 4 bits 2 4 th different patterns for truth table are possible. Hence, there are 2 4 =16 different functions F(x,y) possible, i.e. all possible combinations of 4 bits. 1/ 72 The 16 functions of 2 variables 1/ 73 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies 1/ 74 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Switching transistor Basic logical gates Gates with multiple inputs (fan-in) Multiple operators in a single gate Non-functional properties Implementation technologies 1/ 75 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Switching transistor Basic logical gates Gates with multiple inputs (fan-in) Multiple operators in a single gate Non-functional properties Implementation technologies 1/ 76 Switching transistor p n+ n+ Gate Source Drain Metal Isolator n-MOS transistor 1/ 77 Switching transistor p n+ n+ Vss Vss Vss n-MOS transistor Infinite number of free electrons Many free electrons Many free electrons Hardly any free electrons: no conducting path between Source and Drain S= Vss D= Vss G= Vss 1/ 78 Switching transistor p n+ n+ Vss Vss Vss n-MOS transistor Vcc Many free electrons attracted by positive gate voltage: conducting channel between Source and Drain S= Vss D= Vss G= Vcc 1/ 79 Switching transistor p-MOS transistor Similar construction, but ‘p’ and ‘n’ doping reversed S= Vss D= Vss G= Vss Conducts when gate voltage = Vss S= Vss D= Vss G= Vcc Does not conduct when gate voltage = Vcc 1/ 80 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Switching transistor Basic logical gates Gates with multiple inputs (fan-in) Multiple operators in a single gate Non-functional properties Implementation technologies 1/ 81 Basic logical gates Invertor F=x’, 2 transistors, relative propagation delay: 1 x=0 F=1 x=0 F=1 V cc V ss x F x F V cc V ss x F x F V cc V ss x=1 F=0 x=1 F=0 V cc V ss 1/ 82 Basic logical gates Driver F=x, 4 transistors, relative propagation-delay: 2; goal: higher power drive x F x V cc V ss F V cc V ss x F x V cc V ss F V cc V ss x=1 F=1 x=1 V cc V ss F=1 V cc V ss x=0 F=0 x=0 V cc V ss F=0 V cc V ss 1/ 83 Basic logical gates NAND F=(xy)’, 4 TOR, relative propagation-delay: 1.4 x F y V cc V ss x y x y F x F y V cc V ss x y x y F x=0 F=1 y=0 V cc V ss y=0 x=0 y=0 F=1 x=0 x=0 F=1 y=1 V cc V ss x=0 y=1 x=0 y=1 F=1 x=1 F=1 y=0 V cc V ss x=1 y=0 x=1 y=0 F=1 x=1 F=0 y=1 V cc V ss x=1 y=1 x=1 y=1 F=0 1/ 84 Basic logical gates NOR F=(x+y)’, 4 TOR, relative propagation-delay: 1.4 x F y V cc V ss x y x y F x F y V cc V ss x y x y F x=0 F=1 y=0 V cc V ss x=0 y=0 x=0 y=0 F=1 x=0 F=0 y=1 V cc V ss x=0 y=1 x=0 y=1 F=0 x=1 F=0 y=0 V cc V ss x=1 y=0 x=1 y=0 F=0 x=1 F=0 y=1 V cc V ss x=1 y=1 x=1 y=1 F=0 1/ 85 Basic logical gates AND F=xy, 6 TOR, relative propagation-delay: 2.4 x F y V cc V ss x y x y F V cc V ss 1/ 86 Basic logical gates OR F=x+y, 6 TOR, relative propagation-delay: 2.4 x F y V cc V ss x y x y F V cc V ss 1/ 87 Basic logical gates XNOR F=(x  y)’, 12 TOR,relativepropagation-delay: 3.2 x F y V cc V ss x y x y x’ y’ x’ y’ F x’ V cc V ss x y’ V cc V ss y x F y V cc V ss x y x y x’ y’ x’ y’ F x’ V cc V ss x y’ V cc V ss y x=0 F=1 y=0 x’=1 V cc V ss x y’=1 V cc V ss y V cc V ss x=0 y=0 x=0 y=0 x’=1 y’=1 x’=1 y’=1 F=1 x=0 F=0 y=1 x’=1 V cc V ss x y’=0 V cc V ss y V cc V ss x=0 y=1 x=0 y=1 x’=1 y’=0 x’=1 y’=0 F=0 x=1 F=0 y=0 x’=0 V cc V ss x y’=1 V cc V ss y V cc V ss x=1 y=0 x=1 y=0 x’=0 y’=1 x’=0 y’=1 F=0 x=1 F=1 y=1 x’=0 V cc V ss x y’=0 V cc V ss y V cc V ss x=1 y=1 x=1 y=1 x’=0 y’=0 x’=0 y’=0 F=1 1/ 88 Basic logical gates XOR F=(x  y), 12 TOR,relativepropagation-delay: 3.2 x F y V cc V ss x y’ x y’ x’ y x’ y F x’ V cc V ss x y’ V cc V ss y 1/ 89 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Switching transistor Basic logical gates Gates with multiple inputs (fan-in) Multiple operators in a single gate Non-functional properties Implementation technologies 1/ 90 Gates with multiple inputs (fan-in) 3-input NAND F=(xyz)’, 6 TOR,relativepropagation-delay: 1.8 z F y V cc V ss x y x y F x z z 1/ 91 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Switching transistor Basic logical gates Gates with multiple inputs (fan-in) Multiple operators in a single gate Non-functional properties Implementation technologies 1/ 92 Multiple operators in a single gate 2-wide 2-inputAND-OR-Invert F=(xy + zw)’, 8 TOR,relativepropagation-delay: 2.2 y V cc V ss x y x y x w z z w z w F F 1/ 93 Multiple operators in a single gate 2-wide 2-inputOR-AND-Invert F=((x+y)(z+w))’,8 TOR,relativepropagation-delay: 2.2 y V cc V ss x y x y x w z z w z w F F 1/ 94 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Logical voltage levels and noise margin Fan-out Power dissipation Propagation delay Implementation technologies 1/ 95 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Logical voltage levels and noise margin Fan-out Power dissipation Propagation delay Implementation technologies 1/ 96 Logic voltage levels and noise margin For CMOS and TTL, 0V corresponds to the logical ‘0’ and 5V to ‘1’ (ideal and in steady state) Realistically and during transition for TTL invertor: V out V in High Low 5 2.4 0.4 0 0 0.8 2.0 5 Low High Variation function of: - temperature - power supply voltage - manufacturing 1/ 97 Logic voltage levels and noise margin TTL guarantees a low output level between 0V and 0.4V (=V OL ) and recognizes voltages between 0V and 0.8V (=V IL ) as logic ‘0’ Noise up to 0.4V peak between output and next input are interpreted correctly The noise margin is hence V IL -V OL =0.4V TTL guarantees a high output level between 2.4V (=V OH ) and 5V and recognizes voltages between 2.0V (=V IH ) and 5V as logic ‘1’ Noise up to 0.4V peak between output and next input are interpreted correctly The noise margin is hence V OH -V IH =0.4V 1/ 98 Logic voltage levels and noise margin Graphical representation of noise margin: Low Low High High V ss V ss V cc V cc Output Input V OL V OH V IL V IH Margin Margin 1/ 99 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Logical voltage levels and noise margin Fan-out Power dissipation Propagation delay Implementation technologies 1/ 100 Fan-out: ‘current driven’ technologies cf. TTL, ECL, ... Fan-out: maximum number of inputs that may be connected to a single output Depends on the current that may be delivered by the driving gate (source) (I OH ) w.r.t. the current consumed by the driven gate (I IH ) and on the current sinked by the driving gate (sink) (I OL ) w.r.t. the current delivered by the driven gate (I IL ) Fan-out = min (I OH /I IH ,I OL /I IL ) I OH I IH I OL I IL 1/ 101 Fan-out: ‘charge driven’ technologies cf. CMOS Fan-out: maximum number of inputs that may be connected to a single output Depends on the current that may be sourced resp. sinked by the driving gate (I OH resp. I OL ) w.r.t. the capacity of the connected inputs and the connecting wire and to the switching time allowed I=dQ/dt=C.dV/dt=C.f. D V => determines maximum switching frequency e.g. based on realistic values for Xilinx Virtex: 10 pF input capacity, 20 mA drive current, 0.8 pF/cm PCB connect, V cc =3.3 V For fan-out=3 and 10 cm PCB connect: C=3*10+0.8*10=38 pF and switching frequency = I/(C. D V)=20 mA/(38 pF * 3.3 V)=160 MHz 1/ 102 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Logical voltage levels and noise margin Fan-out Power dissipation Propagation delay Implementation technologies 1/ 103 Power dissipation TTL dissipates continuously P=V CC *I CC 10mW/gate 1 million gates: 10 KW!! Only used when high voltages or large currents are needed (busdrivers, ) CMOS dissipates only while switching P=C.f.V 2 since I=C.f.V C: proportional to chip area (trend: increase) f: trend: steep increase: 1MHz  1 GHz V: trend: steady decrease: 5  3.3  2.5  1.8  1.5  1.2  0.9 Virtex example: P=38 pF*160 MHz*(3.3 V) 2 =66 mW per switching pin; assuming 200 pins, half of which switch concurrently, gives 6.6 W for driving the external pins Advanced microprocessors: 40W  Cooling!!! Is currently the limiting design factor 1/ 104 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Logical voltage levels and noise margin Fan-out Power dissipation Propagation delay Implementation technologies 1/ 105 Propagation delay 90% 50% 10% t PLH t PHL Propagation delay: t P =(t PLH +t PHL )/2 90% 50% 10% Rise time Fall time Rise time > Fall time 1/ 106 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies SSI, MSI, LSI, VLSI Custom design, standard cell design Gate array PLA, PLD, FPGA 1/ 107 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies SSI, MSI, LSI, VLSI Custom design, standard cell design Gate array PLA, PLD, FPGA 1/ 108 SSI, MSI, LSI, VLSI (I) SSI: Small Scale Integration < 10 gates per package gates directly connected to package pins designed using transistor level design used using gate level design MSI: Medium Scale Integration 10 - 100 gates per package registers, adders, parity generators, designed using gate level design used using RTL design LSI: Large Scale Integration 100 - 10K gates per package controllers, data paths designed using RTL design used using behavioral level design 1/ 109 SSI, MSI, LSI, VLSI (II) VLSI: Very Large Scale Integration 10K - 1M gates per package memory, microprocessor, microcontroller, FFT designed using behavioral level design used using system level design ULSI: Ultra Large Scale Integration??? 1M - ?? Gates per package 2  controllers, 20 DSP processors, 16 Mbyte memory, 10 accelerators, 1 Mgate FPGA, Analog interface, RF designed using system level design only one chip needed for complete application ?? 1/ 110 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies SSI, MSI, LSI, VLSI Custom design, standard cell design Gate array PLA, PLD, FPGA 1/ 111 Custom design Each transistor and each connection is designed individually as a set of rectangles. Excellent for optimal design of library elements that are re-used multiple times Companies design and sell such optimized libraries Has to be completely re-done each time technology changes (every 18 months!) 1/ 112 Standard cell design Library of standard cells each cell is a gate standard height, variable width, interleaved by routing channels all inputs at the top, all outputs at the bottom Faster design of more complex building blocks Silicon foundries design and sell such optimized libraries for their processing technology Placement and routing 1/ 113 Standard cell design Design Flow Design entry Placement Routing Simulation Timing simulation Fabrication: n masks Testing 1/ 114 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies SSI, MSI, LSI, VLSI Custom design, standard cell design Gate array PLA, PLD, FPGA 1/ 115 Gate array design Two-dimensional grid of identical gates each cell is for example a 3-input NAND gate standard height, standard width, interleaved by routing channels all inputs at the top, all outputs at the bottom Cheaper: Only the last metallisation layer is project specific 1/ 116 Gate array design Design Flow Design entry Placement Routing Simulation Timing simulation Fabrication: 1 mask Testing Map all functions to the available 3-input NANDs Technology mapping 1/ 117 Contents of “Digital Design” Introduction to the course Data representation Boolean algebra Logical gates Gates Non-functional properties Implementation technologies SSI, MSI, LSI, VLSI Custom design, standard cell design Gate array PLA, PLD, FPGA 1/ 118 Field-programmable design Fuse programmable One time customer programmable by selectively blowing fuses PLA: Programmable Logic Array PLD: Programmable Logic Device CPLD: Complex PLD SRAM based FPGA: Field Programmable Gate Array (see laboratory sessions) Properties: Excellent for prototypes Excellent for medium volumes (<100K pieces/year) For SRAM based: reconfiguration (static or dynamic) possible 2 Mgates @ 200 MHz (in 2000) 1/ 119 Field-programmable design PLA 1/ 120 Field-programmable design PLD D D 1/ 121 Field-programmable design CPLD AND-OR Plane O I/O Switch matrix I/O O AND-OR Plane AND-OR Plane O I/O I/O AND-OR Plane O 1/ 122 Field-programmable design XC95216 6 Functional blocks (36V18 each) Flash programmable 1/ 123 Field-programmable design FPGA: XC40xx CLB CLB CLB CLB CLB CLB Direct connections Long lines SM SM SM SM SM SM SM SM SM SM SM SM Routing via switching matrices I/O I/O I/O I/O I/O I/O I/O 1/ 124 Field-programmable design 1/ 125 Field-programmable design FPGA: Configurable Logic Block CLB 16x1 LUT: Bool-function of 4 variables 16x1 LUT: Bool-function of 4 variables FF G G GQ FF F F FQ 1/ 126 Field-programmable design 1/ 127 Field-programmable design FPGA: Switching Matrix SM Pass TOR 1/ 128 Field programmable design Design Flow Design entry Placement Routing Simulation Timing simulation Downloading Testing Technology mapping