Logic Circuits & Switching Theory PDF

# Logic Circuits & Switching Theory ## Engr. Dennis Edward E. Diano Professor # Part 1 ## Digital System ### DIGITAL SYSTEMS - have such a prominent role in everyday life ### DIGITAL AGE - present technological period - used in communications, business transactions, traffic control, space guida...

# Logic Circuits & Switching Theory ## Engr. Dennis Edward E. Diano Professor # Part 1 ## Digital System ### DIGITAL SYSTEMS - have such a prominent role in everyday life ### DIGITAL AGE - present technological period - used in communications, business transactions, traffic control, space guidance, medical treatment, weather monitoring, internet and many other commercial, industrial and scientific enterprises such as: - digital telephones, digital television, digital versatile disk, digital cameras, handheld devices, and digital computers. ### DIGITAL COMPUTER - most striking property is generality - it can follow a sequence of instructions called a program ### PROGRAM - operates on given data - the user can specify and change the program or data according to specific need ### Characteristics of Digital System #### FLEXIBILITY - enables general purpose digital computers to perform variety of information-processing tasks that range over a wide spectrum of application ### REPRESENTATION & MANIPULATION OF DISCRETE ELEMENTS OF INFORMATION - any set that is restricted to a finite number of elements contains discrete information #### Example: - 10 decimal digits - 26 letters of the alphabets - 52 playing cards - 64 squares of chessboard ### EARLY DIGITAL COMPUTERS - used for numeric computation - digits were the discrete elements - from this application, digital computers emerged ### SIGNAL - physical quantities which represents the discrete elements of information in a digital system #### Most Common Signals: - electrical signals such as voltage and currents ### TRANSISTORS - electronic device that predominate in the circuitry that implements signal ### BINARY - two discrete values used as signals in the most present-day electronic digital system ### BIT - binary digits that use two values, 0 and 1 ### BINARY CODES - group of bits which represents discrete elements of information #### Example: - Number 7 is represented by 0 111; decimal digits, 0 through 9 are represented in a digital system with a code of four bits. ### DIGITAL SYSTEM - a system that manipulates discrete elements of information represented internally in binary form - THROUGH VARIOUS TECHNIQUES - group of bits can be made to present discrete symbols which are then used to develop the system in digital format. ### DISCRETE QUANTITIES OF INFORMATION - emerge from the nature of data being processed - may also be quantized from a continuous process #### Example: 1. PAYROLL SCHEDULE - discrete process that contains employee name, social security number, weekly/monthly salaries, income taxes, etc. - EMPLOYEE'S PAYCHECK - processed by means of discrete data values such as letters of alphabet for names, digits for salary, and special symbols such as peso sign. 2. A research scientist observes a continuous process but record only specific quantities in tabular form. The scientist is quantizing continuous data, making each number in his or her table a discrete quantity. - QUANTIZATION OF A PROCESS - can be performed automatically by an analog to digital converter ### GENERAL PURPOSE DIGITAL COMPUTER - best known example of digital system. - it can perform arithmetic and logical operations - it can be programmed to make decisions based on internal and external conditions. ### MAJOR PARTS OF A COMPUTER 1. **Memory Unit** - stores program as well as input, output and intermediate data. 2. **Central Processing Unit** - performs arithmetic and other data processing operations as specified by the program. 3. **Input Device** - the program and data prepared by a user are transferred into memory by means of input device such as keyboard 4. **Output Device** - such as printer, receives the result of computations and the printed results are presented to the user. ### COMMUNICATION UNIT - a very useful device that provides interaction with other users through the internet. ### FUNDAMENTAL REASONS WHY COMMERCIAL PRODUCTS ARE MADE WITH DIGITAL CIRCUITS - Most digital devices are programmable. By changing the program, the same underlying hardware can be used for many different applications. - Dramatic cost reduction in digital devices have become about because of advances in digital integrated circuit technology. As the number of transistors increases to produce complex functions, the cost per unit decreases. Digital devices can be bought at reduced price. - Equipment built with digital integrated circuits can perform at a speed of hundreds of millions of operations per second. - Digital Systems can be made to operate with extreme reliability by using error-correcting codes. ### EXAMPLE: - Digital versatile disk (DVD), digital information representing video, audio and other data is recorded without the loss of a single item. - Digital information on a DVD is recorded in such a way that by examining the code in each digital sample before it is played back, any error can be automatically identified and corrected. ### DIGITAL SYSTEM - interconnection of digital modules ### OPERATION OF DIGITAL MODULES - basic knowledge of digital circuits and their logical function is necessary to understand the operations. # 1.2 Binary Numbers ### Decimal Number System - 7,392 = 7 x 10³ + 3 x 10² + 9 x 10¹ + 2 x 10⁰ - THOUSANDS HUNDREDS TENS ONES - Coefficients and their position, deduce necessary powers of 10 - A5 A4 A3 A2 A1 Ao • a-1 A-2A-3 ### BASE 10 or RADIX 10 - uses 10 digits (0 to 9), coefficients are multiplied by powers of 10 ### Coefficients: aj (0 to 9) ### Subscript: j (place value, powers of 10 by which coefficient is multiplied - 10⁵a⁵ + 10⁴a⁴ + 10³a³ + 10²a² + 10¹a¹ + 10⁰ao + 10⁻¹a⁻¹ + 10⁻²a⁻² + 10⁻³a⁻³ ### Binary Number System - Coefficients: aj (0 and 1) - Decimal Equivalent: multiplied by 2j, results are added - 11010.11= 26.75 - 1 x 2⁴ + 1 x 2³ + 0 x 2² + 1 x 2¹ + 0 x 2⁰ + 1 x 2⁻¹ + 1 x 2⁻² ### RADIX POINT - distinguishes positive powers of 10 from negative powers of 10. - A number in base - r system has coefficient multiplied by powers of r. ### An rn + An-1 rn-1 + ... + a2 r² + A1 r¹ + A0 + A-1 r⁻¹ + a-2 r⁻² + ... + a-m. r⁻m ### RANGE OF COEFFICIENT: Aj is 0 to (r-1) ### NUMBERS OF DIFFERENT BASES 1. **BASE 5 NUMBERS SYSTEM** - coefficient values 0, 1, 2, 3, 4 only. - (4021.2)5 = 4 x 5³ + 0 x 5² + 2 x 5¹ + 1 x 5⁰ + 2 x 5⁻¹ - = (511.4)¹⁰ 2. **BASE 8 NUMBERS SYSTEM (octal)**- 8 digits 0, 1, 2, 3, 4, 5, 6, & 7 - Determine the equivalent decimal value by expanding the number in power series with a base of 8. - (127.4)8 = 1 x 8² + 2 x 8¹ + 7 x 8⁰+ 4 x 8⁻¹ - = (87.5)¹⁰ 3. **BASE 16 NUMBERS SYSTEM (hexadecimal)** - digits 10 to 15 is equivalent to A to F respectively. - (B65F)16 = 11 x 16³ + 6 x 16² + 5 x 16¹ + 15 x 16⁰ - = (46,687)¹⁰ - There are four "Is" in the binary number → the corresponding decimal number is the sum of the four powers of 2) ### In computer work: - 2¹⁰ → K (kilo); 2²⁰ M (mega); 2³⁰ → G (giga); 2⁴⁰ → T (tera) ### EXAMPLE: - **Powers of Two** | n | 2n | n | 2n | n | 2n | |:---:|:---:|:---:|:---:|:---:|:---:| | 0 | 1 | 8 | 256 | 16 | 65,536 | | 1 | 2 | 9 | 512 | 17 | 131,072 | | 2 | 4 | 10 | 1,024 | 18 | 262,144 | | 3 | 8 | 11 | 2,048 | 19 | 524,288 | | 4 | 16 | 12 | 4,096 | 20 | 1,048,576 | | 5 | 32 | 13 | 8,192 | 21 | 2,097,152 | | 6 | 64 | 14 | 16,384 | 22 | 4,194,304 | | 7 | 128 | 15 | 32,768 | 23 | 8,388,608 | - 4K = 2¹² = 4,096 (1K = 2¹⁰, 2K = 2¹¹, 4K = 2¹²) - 16M = 2²⁴ = 16, 777, 216 (1M = 2²⁰, 2M = 2²¹, 4M = 2²², 8M = 2²³, 16M = 2²⁴) ### BYTE - computer capacity - equal to 8 bits and can accommodate or represent the code of one keyboard character - Computer hard disk with 4 gigabytes of storage has a capacity of 4GB = 2³² bytes (approximately 4 billion bytes) ### ARITHMETIC OPERATIONS OF BINARY NUMBERS #### ADDITION RULES: - 0 + 0 = 0; 0+1=1;1 + 0 = 1; 1+1=0 carry 1 ##### Example: 1010 → 10 +  1001 → 9 ------- 10011 → 19 ↓ 16 8 4 2 1 #### SUBTRACTION RULES: - 1-0=1; 1-1=0; 0 - 1= cannot be borrow ##### Example: 02    100 → 4 -      10 → 2 -------     010 → 2      ↓     4 2 1 #### MULTIPLICATION RULES: ##### Example:    101 → 5 x     11 → 3 -------      101 +    101 -------    1111 → 15      ↓     8 4 2 1 #### DIVISION RULES: - 11 ↓ 21 001101    -  012      100111    -  11      0011    -  11       0011    -  11        0 ------- {       11>1 ; 3>1 {       11>10:3>2 {       11<100; 3<4 {       11>001; 3>1 {       11 = 0011; 3=3 - - 100111 32 168 4 2 1 39 ÷ ÷    11    21 ↓     3 ------- 001101 32 168 4 2 1 = = 13 ### Number-Base Conversion #### BASE r TO DECIMAL - expand the number in power series then add all the terms. #### DECIMAL TO NUMBER IN THE BASE r - number with radix point - separate the number into an integer and fraction part. - decimal integer to a number in base r - divide the number and all quotients by r and accumulating the remainder. ##### 1. Convert decimal 41 to binary | Integer Quotient | Remainder | Coefficient | |---|---|---| | 41/2 = 20 |  1/2 | a0 = 1 | | 20/2 = 10 |  0 | a1 = 0 | | 10/2 = 5 |  0 | a2 = 0 | | 5/2 = 2 |  1/2 | a3 = 1 | | 2/2 = 1 |  0 | a4 = 0 | | 1/2 = 0 |  1/2 | a5 = 1 | ------- .. (41)¹⁰ = (a5 a4 a3 a2 a1 a0)₂ = (101001)₂ ##### 2. Convert decimal 153 to octal. | Integer Quotient | Remainder | Coefficient | |---|---|---| | 153/8 = 19 |  1 | a0 = 1 | | 19/8 = 2 |  3 | a1 = 3 | | 2/8 = 0 | 2 | a2 = 2 | ------- ... (153)¹⁰ = (231)⁸ ##### 3. Convert (0.6875)¹⁰ to binary | Integer Quotient | Remainder | Coefficient | |---|---|---| | 0.6875 x 2 = 1 | 0.3750 | a-1=1 | | 0.3750 x 2 = 0 | 0.7500 | a-2 = 0 | | 0.7500 x 2 = 1 | 0.5000 | a-3 = 1 | | 0.5000 x 2 = 1 | 0.0000 | a-4=1 | ------- ... (0.6875)¹⁰ = (0.a-1 a-2 a-3 a-4)₂ = (0.1011)₂ ##### 4. Convert (0.513)¹⁰ to octal, 6 fractional digit accuracy | Integer Quotient | Remainder | Coefficient | |---|---|---| | 0.513 x 8 = 4.104 | a-1=4 | | | 0.104 x 8 = 0.832 | a-2 = 0 | | | 0.832 x 8 = 6.656 | a-3=6 | | | 0.656 x 8 = 5.248 | a-4= 5 | | | 0.248 x 8 = 1.984 | a-5 = 1 | | | 0.984 x 8 = 7.872 | a-6=7 | | ------- .. (0.513)¹⁰ = (0.406517 ...)⁸ = (0.1011)₂ ### Conversion of decimal numbers with integer & fraction parts by converting each separately and then combining their answers: - (41.6875)¹⁰ = (101001.1011)₂ - (153.513)¹⁰ = (231.406517)⁸ ### Octal and Hexadecimal Numbers - Since 2³ = 8, each octal digits corresponds to 3 binary digits. - Since 2⁴ = 16, each hexadecimal digits corresponds to 4 binary digits. ### CONVERSION FROM BINARY TO OCTAL - partition the binary number into group of 3 digits each starting from the binary point and proceeding to the left and to the right, corresponding octal digit is then assigned to each group. ##### Example: (10 110 001 101 011 111 100 000 110)₂ 2 6 1 5 3 7 4 0 6 = (26 153.7406)⁸ ### CONVERSION FROM BINARY TO HEXADECIMAL - same as octal except groupings shall be 4 digits. ##### Example: (10 1100 0110 1011 • 1111 0010)₂ 2 C 6 B F 2 = (2C6B.F2)¹⁶ ### CONVERSION FROM OCTAL OR HEXADECIMAL TO BINARY - reverse the procedure. Each octal digit or hexadecimal digit is converted to its 3 digit or 4 digit binary equivalent. ##### Example: (673.124)⁸ = (110 111 011 • 001 010 100)₂ 6 7 3 1 2 4 (306.D)¹⁶ = (0011 0000 0110 • 1101)₂ 3 0 6 D # Signed Binary Numbers ### POSITIVE INTEGERS (including zero) - unsigned numbers ### NEGATIVE INTEGERS - with notation of negative values ### In ordinary arithmetic: - Negative Number minus sign - Positive Number plus sign ### Due to hardware limitations, Computers represent everything with binary digits (0 for positive, 1 for negative) ### SIGNED BINARY - left most bit represent the sign, the rest of the bit represent the number ### UNSIGNED BINARY - left most bit is the significant bit of the number ### SIGNED MAGNITUDE SYSTEM - negates a number by changing its sign ### EXAMPLE: Signed Magnitude Convention - String of bits, 01001 => 9 unsigned => + 9 signed - 11001 => 25 unsigned => - 9 signed ### SIGNED - COMPLEMENT SYSTEM - arithmetic operation implemented in computers to represent negative numbers - a negative number indicated by its complement - or negates a number by taking its complement ### EXAMPLE: - Number 9, represented in binary with 8 bits - +9 0 0001001 - -9 Signed Magnitude System 1 0001001 - Signed 1's complement representation 11110110 - Signed 2's complement representation 11110111 ### Signed Complement System a. **1'S COMPLEMENT** - complementing all the bits of +9 including the sign bit b. **2'S COMPLEMENT** - take 1's complement & add 1 ### SIGNED MAGNITUDE - used in ordinary arithmetic ### SIGNED COMPLEMENT - used in computer arithmetic ### SEPARATE HANDLING OF THE SIGN & THE MAGNITUDE ### 1'S COMPLEMENT - used in logical operation change from 0 to 1 & 1 to 0 is equivalent to logical complement operation. ### Arithmetic Addition - In signed magnitude representation of binary numbers, same as rules of ordinary arithmetic. #### EXAMPLE: (+25) + (-37) = -(37-25) = -12 - Addition of two signed binary numbers with negative numbers represented in 2’s complement form, obtained from the addition of the two numbers including their sign bits. A carry out of the sign bit position is discarded. #### EXAMPLE: | | Value | Binary | |---|---|---| | +6 | 00000110 | 11111010 | | +13 | 00001101 | 00001101 | | +19 | 00010011 | 00000111 | ------- | +6 | 00000110 | 11111010 | | -13 | 11110011 | 11110011 | | -7 | 1111 1001 | 11101101 | **NOTE:** Negative results are in 2's complement form ### Value of Negative Number in Z's Complement - Signed Binary Number, 11111001 → -7 - 2's Complement, 00000111- binary equivalent of +7 - Converted to a positive number, from the original negative number which is -7 ### Arithmetic Subtraction - Subtraction of two signed binary numbers when negative numbers are in 2’s complement form. - Take the 2’s complement of the subtrahend including the sign bit and add it to the minuend including the sign bit. A carry out of the sign bit position is discarded. (-6) - (-13) = +7 -6 + 13 = +7 11111010 11110011 11111010 + 00001101 = 100000111 removing the end carry = 00000111 (+7) ### Binary Codes ### DIGITAL SYSTEMS - use signals that have two distinctive values and circuit elements that have two distinct states - there is a direct analogy between binary signals, binary circuit elements and binary digits ### BINARY NUMBER OF N - DIGITS - maybe represented by n-binary elements, each having an output signal equivalent to 0 or 1. ### CODES MUST BE IN BINARY - in today's technology only circuits that represents and manipulate patterns of 0's and 1's can be manufactured economically for use in computers. - codes merely change the symbols not the meaning of information they represent. ### Binary Coded Decimal (BCD) - DECIMALS ARE WRITTEN WITH SYMBOLS → 0, 1, 2 ... 9 - BCD NUMBERS USES BINARY CODES → 0000, 0001, 0010 ... 1001 ### EXAMPLE: - 10-0001 0000 - 15-0001 0101 - (185)¹⁰ = (0001 1000 0101)BCD = (10111001)₂ ### Addition of BCD - digits should not exceed by 9 ##### EXAMPLE: | | Value | Binary | |---|---|---| | 4 | 0100 | 0100 | | +5 | + 0101 | + 1000 | ------- | 9 | 1001 | 1100 (IF EXCEEDED BY 9, ADD 00110) | | | | + 0110 | | | | 10010 | ### Addition of Two n- digit BCD Numbers ##### EXAMPLE: | | | Binary | |---|---|---| | |        184 | 0001 | | |        + 576 | + 0101 | ------- | Binary | Sum | 0111 | | Sum | Add 6 | 10000 | | BCD Sum | | 0110 | ------- | | | 0111 | | | | 0110 | | |        760 | 0000 | **NOTE:** | | Value | |---|---| | Decimal | max value = 9 (per digit) | | Binary | max value = 15 (for 4 bits) | | Difference | 6 | | | | (if exceeded 9) | ### Decimal Arithmetic - The representation of signed decimal numbers in BCD is similar to the representation of signed numbers in binary. - The signed magnitude system is seldom used in computers. - The signed complement system can either be 9's or the 10's complement. - The procedures for the signed 2’s complement system is also applicable to the signed 10’s complement system for decimal numbers. #### EXAMPLE: (+375)+(-240) 0 375 << O means positive + 0 760 1 means negative, 9 240 ------- 0 135 << 760 is 10's complement of 0 759 <<< end carry is discarded - The subtraction of decimal numbers, either unsigned or in the signed-10's complement system, is the same as in the binary case. - Take the 10's complement of the subtrahend and add it to the minuend. ### GRAY CODE: - Output data of many physical systems must be converted to digital form from continuous or analog information before they are applied to a digital system. - Gray Code is used to represent digital data that have been converted from analog. - The advantage of Gray Code over the straight binary number sequence is that only one bit in the code group changes in going from one number to the next. #### EXAMPLE: - Going from 7 to 8 - Gray code changes 0100 to 1100 ; only the 1st bit changes from 0 to 1 - Binary Number changes 0111 to 1000; all the 4 bits changes values | GRAY | DECIMAL | GRAY | DECIMAL | GRAY | DECIMAL | |---|---|---|---|---|---| | CODE | | CODE | | CODE | | | 0001 | 1 | 0101 | 6 | 1110 | 11 | | 0011 | 2 | 0100 | 7 | 1010 | 12 | | 0010 | 3 | 1100 | 8 | 1011 | 13 | | 0110 | 4 | 1101 | 9 | 1001 | 14 | | 0111 | 5 | 1111 | 10 | 1000 | 15 | - The GRAY CODE is used in applications in which the normal sequence of binary number may produce error or ambiguity during the transition from one number to the next. ### ASCII Character Codes - Many applications of digital computers require the handling not only of numbers but also of other character or symbols such as letters of alphabet. - The standard binary code for alpha numeric characters is the American Standard Code for Information Interchange (ASCII) which uses 7-bits to code 128 characters, the 7-bits code are designated by b1 through b7, with b7 as the most significant bit. #### EXAMPLE: - Letter A-1000001 (column 100, row 0001) **NOTE:** Page 24, table 1.7 (Digital Design 4th Edition by Morris Mano) # Part 2 ## Binary Logic - Deals with variables that take on two discrete values and with operations that assume logical meaning. - The two values the variable assume maybe called by different names such as true or false, yes and no, etc. Thinking in terms of bits and assigning values, 1 and 0. - Equivalent to Boolean Algebra, relating to digital logic circuits and binary signals. - Consists of binary variables and a set of logical operations. The variables are designated by letters of alphabet such as A, B, C, x, y, z, etc. with each variable having two and only two distinct possible values 1 and 0. ### Basic Logical Operations 1. **AND** - this operation is represented by dot or by absence of operator. ##### Example: - x • y = z or xy=z ##### Read as: - x and y is equal to z ##### AND means: - z = 1 if x = 1 & y = 1 ##### Otherwise: - z = 0 2. **OR** - this operation is represented by a plus sign. ##### Example: - x + y = z ##### Read as: - x or y is equal to z ##### OR means: - z = 1 if x = 1 or y = 1 or if both = 1 ##### Otherwise: - If x = 0 & y = 0 then z = 0 3. **NOT** - this operation is represented by a prime (sometimes by an over bar) ##### Example: - x' = z or X = z ##### Read as: - not x is equal to z ##### Not means: - z is what x is not ##### Otherwise: - z=1 if x = 0 ; 2 = 0 if x = 1 ##### NOTE: NOT operation is sometimes called complement operation since it changes a 1 to 0 and a 0 to 1. ### TRUTH TABLES - list of definition for logical operation - table all possible combination of the variables showing the relation between the values that the variable may take and the result of operation. #### TRUTH TABLES FOR LOGICAL OPERATIONS | | | | |---|---|---| |**AND** | **OR** | **NOT** | | xy | xy | x x' | | 0 0 | 0 0 | 0 1 | | 0 1 | 0 1 | 1 0 | | 1 0 | 1 0 | | | 1 1 | 1 1 | | # Introduction to Logic Gates - electronic circuits that operate on one or more input signals to produce an output signal. ### ELECTRICAL SIGNALS (Voltage or Current) - exist as analog signals having values over a given range e.g. 0 to 3 V. - but in a digital system are integrated to be either of two recognizable values, 0 or 1. ### VOLTAGE OPERATED LOGIC CIRCUITS - respond to two separate voltage level that represent a binary variable equal to logic 1 or logic 0. ##### EXAMPLE: - Logic 0 = signal equal to 0 volts. - Logic 1 = signal equal to 3 volts. ### INPUT TERMINAL OF DIGITAL CIRCUIT - accept binary signal within the allowable range. ### OUTPUT TERMINAL OF DIGITAL CIRCUIT - respond with binary signal that fall within the specified range. ### INTERMEDIATE REGION BETWEEN THE ALLOWED REGIONS - crossed only during a state transition. ### INFORMATION FOR COMPUTING A CONTROL - can be operated on by passing binary signals through various combinations of logic gates with each signal representing a particular binary variable ### GATES - blocks of hardware that produce the equivalent of logic-1 or logic-0 output signals. - Volts | 3 | 2 | 1 | 0 ------- - Transition occurs between these limits - Signal range for logic 1 - Signal range for logic 0 ### Binary Signals - TWO INPUT AND GATE X y z = x • y - TWO INPUT OR GATE X y z = x + y - NOT GATE OR INVERTER X x' ### Input-Output Signals for Gates - X 0 1 1 0 0 - y 0 0 1 1 0 - HORIZONTAL LINE → time - VERTICAL LINE → change in signal - LOGIC-O → lower - LOGIC-1 → higher - if input is logic 1, output is logic 1 - if input is logic 0, output is logic 0 | | | | |---|---|---| | AND: x•y | 0 0 1 0 0 | | | OR: x+y | 0 1 1 1 0 | | | NOT: x' | 1 0 0 1 1 | | - x = 0; y = 0 x•y = 0 - x = 0; y = 0 x+y=0 - x = 0 x' = 1 inverted ### Gates with Multiple Inputs - THREE INPUT AND GATE ABC F = ABC - FOUR INPUT OR GATE ABCD G=A+B+C+D