DIGITAL ELECTRONICS BASICS Suresh P. Nair [AIE, ME, (PhD)] MIEEE Professor & Head Department of Electronics and Communication Engineering Royal College of Engineering and Technology Chiramanangad PO, Akkikkavu, Thrissur, Kerala, India

Module 1:

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Module 1:

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Introduction to Digital Electronics:

Introduction to Digital Electronics

Slide 5:

Most natural quantities that we see are analog and vary continuously. Analog systems can generally handle higher power than digital systems. Analog Quantities

Slide 6:

A digital quantity has a set of discrete values. Digital Quantities Digital systems can process, store, and transmit data more efficiently but can only assign discrete values to each point.

Slide 7:

Digital waveforms change between the LOW and HIGH levels. A positive going pulse is one that goes from a normally LOW logic level to a HIGH level and then back again. Digital waveforms are made up of a series of pulses. Digital Waveforms

Analog Example:

Analog Example A public address system, used to amplify sound so that it can be heard by large audience, is one example of an application of analog electronics.

Digital Example:

Digital Example A computer system is one example of an application of digital electronics.

A Mixed System:

A Mixed System The compact disk (CD) player is an example of a system in which both digital and analog circuits are used.

Analog Vs. Digital:

Analog Vs. Digital Analog Continuous Can take on any values in a given range Very susceptible to noise Digital Discrete Can only take on certain values in a given range Can be less susceptible to noise

Advantages Over Analog:

Advantages Over Analog Programmability Predictable accuracy Maintainability Processed more efficiently and reliably Compact storage Does not affected by noise as well as analog values

Slide 13:

Example Controlling a storage tank system for a pancake syrup manufacturing

Slide 14:

Example A key-coded deadbolt

What digital electronics do you use?:

What digital electronics do you use? Computer CD & DVD players IPod Cell phone HDTV Digital cameras

What are digital electronics?:

What are digital electronics? Sound is an analog signal. On a CD, digital sound is encoded as 44.1 kHz, 16 bit audio. The original wave is 'sliced' 44,100 times a second - and an average amplitude level is applied to each sample. 16 bit means that a total of 65,536 different values can be assigned, or quantized to each sample. DVD-Audio can be 96 or 192 kHz and up to 24 bits resolution

Slide 17:

ADC Analog to digital converder -Sampling time/sampling frequency fs -Number of bits Sample and hold Analog To Digital 1 0 0 1 1 0 0 1 1.4V

Slide 18:

Sampling Time Level Level

Slide 19:

Data can be transmitted by either serial transfer or parallel transfer. Serial and Parallel Data

Serial communication between computers. :

Serial communication between computers.

Parallel communication between a computer and a printer.:

Parallel communication between a computer and a printer.

A Computer is…:

A digital electronics device that combine hardware and software to accept the input of data, process and store the data, and produce some useful output . A Computer is…

Digital Electronics:

Digital Electronics Digital electronics devices store and process bits electronically. A bit represents data using 1’s and 0’s Eight bits is a byte – the standard grouping in digital electronics Digitization is the process of transforming information into 1’s and 0’s

Microprocessor:

Microprocessor The computer you are using to read this page uses a microprocessor to do its work. The microprocessor is the heart of any normal computer . The microprocessor you are using might be a Pentium, a K6, a PowerPC, a Sparc or any of the many other brands and types of microprocessors.

Microprocessor (Processor):

Microprocessor (Processor) Designed to process instructions Largest chip on motherboard Intel: world’s largest chipmaker (Pentiums) AMD: Cheaper chips (Athlons)

Motherboard :

Motherboard Main circuit board

Processor Components:

Processor Components

Processor Performance:

Processor Performance Speed: processor clock set clock speed (MHz or GHz ) Word Size: number of bits the processor can manipulate at one time (32-bit or 64-bit) Cache: high speed memory (kilobytes)

Physical File Storage Storage medium formatted into tracks /sectors electronically File system keeps track of names and file locations. Clusters : a group of sectors that speeds up storage and retrieval

Digital Data Representation :

Digital Data Representation The form in which information is conceived, manipulated and recorded on a digital device . Uses discrete digits/electronic signals Byte = 8 bits = 1 character

Numeric Data:

Numeric Data Consists of numbers representing quantities used in arithmetic operations. Binary system, “Base 2” 1,0 (bits - binary digits) On/Off, Yes/No

Digital Technology Metrics:

Digital Technology Metrics Kilo, Mega, Giga, what comes next?

Binary Digits:

Binary Digits The two digits in the binary system, 1 and 0, are called bits, which is a contraction of the words binary digit.

How to represent 0 and 1?:

How to represent 0 and 1? In digital circuits, two different voltage levels are used to represent the two bits. The higher/lower voltage level is referred to as a HIGH/LOW, or H/L.

Logic Levels:

Logic Levels The voltages used to represent a 1 and a 0 are called logic levels. HIGH can be any voltage between a specified minimum value and a specified maximum value. LOW can be any voltage between a specified minimum and a specified maximum.

Binary Representations:

Binary Representations

Positive Logic System:

Positive Logic System A 1 is represented by HIGH and a 0 is represented by LOW . Also called ACTIVE HIGH LOGIC

Negative Logic System:

Negative Logic System A 0 is represented by HIGH and a 1 is represented by LOW . Also called ACTIVE LOW LOGIC

Codes:

Codes Groups of bits (combination of 1s and 0s), called codes, are used to represent numbers, letters, symbols, instructions, and anything else required in a given application. The American Standard Code for Information Interchange (ASCII) – pronounced “ askee ” – is a universally accepted alphanumeric code used in most computers and other electronic equipment. 1

ASCII:

ASCII

Digital Waveforms :

Digital Waveforms Digital waveforms consists of a series of pulses, (voltage levels that are changing back and forth between the HIGH and LOW levels).

Pulse Train :

Pulse Train Digital waveforms are sometimes called pulse trains.

Ideal Pulses:

Ideal Pulses A single positive-going pulse is generated when the voltage goes from its normally LOW level to its HIGH level and then back to its LOW level. A single negative-going pulse is generated when the voltage goes from its normally HIGH level to its LOW level and then back to its HIGH level.

Nonideal Pulse:

Nonideal Pulse The time required for the pulse to go from its LOW (HIGH) level to its HIGH (LOW) level is called the rise (fall) time. In practice, it is common to measure rise (fall) time from 10%(90%) of the pulse amplitude to 90%(10%) of the pulse amplitude.

Nonideal Pulse:

Nonideal Pulse The pulse width is a measure of the duration of the pulse and is often defined as the time interval between the 50% points on the rising and falling edges.

Periodic Pulse:

Periodic Pulse A periodic waveform is one that repeats itself at a fixed interval, called a period ( T ). The frequency ( f ) is the rate at which it repeats itself and is measured in hertz (Hz). The relationship between f and T is expressed as follows:

Periodic Pulse:

Periodic Pulse The duty cycle ( D ) is defined as the ratio of the pulse width ( t w ) to the period ( T ) and can be expressed as a percentage.

Nonperiodic Pulse:

Nonperiodic Pulse A nonperiodic waveform, of course, does not repeat itself at fixed intervals. They are composed of pulses of randomly differing pulses widths and/or randomly differing time intervals between the pulses.

A Digital Waveform Carries Binary Information:

A Digital Waveform Carries Binary Information Binary information that is handled by digital systems appears as waveforms that represent sequences of bits. When the waveform is HIGH, a binary 1 is present; when the waveform is LOW, a binary 0 is present. Each bits in a sequence occupies a defined time interval called a bit time, or bit interval.

The Clock:

The Clock In digital systems, all digital waveforms are synchronized with a basic timing waveform, called the clock. The clock is a periodic waveform. The clock waveform itself does not carry information.

Timing Diagrams:

Timing Diagrams A timing diagram is a graph of digital waveforms showing the actual time relationship of two or more waveforms and how each changes in relation to the others.

Data Transfer:

Data Transfer Data refers to groups of bits that convey some type of information . Binary data, which are represented by digital waveforms, must be transferred from one circuit to another within a digital system or from one system to another in order to accomplish a given purpose.

Serial Data Transfer:

Serial Data Transfer When bits are transferred in serial form from one point to another, they are sent one bit at a time along a single conductor. To transfer n bits in series, it takes n time intervals.

Parallel Data Transfer:

Parallel Data Transfer When bits are transferred in parallel form, all the bits in a group are sent out on separate lines at the same time. There is one line for each bit. To transfer n bits in parallel, it takes one time interval.

Module 1:

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Number System:

Number System

Slide 60:

10 ?? It depends on the number system

Number Systems:

Number Systems To talk about binary data, we must first talk about number systems The decimal number system (base 10) you should be familiar with! Positional number system

Positional Notation:

Positional Notation Value of number is determined by multiplying each digit by a weight and then summing. The weight of each digit is a POWER of the RADIX (also called BASE) and is determined by position.

Radix (Base) of a Number System:

Radix (Base) of a Number System Decimal Number System (Radix = 10) Eg:- 7392 = 7x10 3 +3x10 2 +9x10 1 +2x10 0 Binary Number System (Radix = 2) Eg:- 101.101 = 1x2 2 +0x1 1 +1x2 0 +1x2 -1 +0x2 -1 1x2 -2 Octal number system (radix = 8) Hexadecimal number system (radix = 16)

Radix (Base) of a Number System:

64 Radix (Base) of a Number System When counting upwards in base-10, we increase the units digit until we get to 10 when we reset the units to zero and increase the tens digit. So, in base- n , we increase the units until we get to n when we reset the units to zero and increase the n- s digit. Consider hours-minutes-seconds as an example of a base-60 number system: Eg. 12:58:43 + 00:03:20 = 13:02:03 NB. The base of a number is often indicated by a subscript. E.g. (123) 10 indicates the base-10 number 123.

Decimal Number Systems :

Decimal Number Systems Base 10 Ten digits, 0-9 Columns represent (from right to left) units, tens, hundreds etc. 123 1 ´ 10 2 + 2 ´ 10 1 + 3 ´ 10 0 or 1 hundred, 2 tens and 3 units

Binary Numbers Each binary digit (called bit) is either 1 or 0 Bits have no inherent meaning, can represent Unsigned and signed integers Characters Floating-point numbers Images, sound, etc. Bit Numbering Least significant bit (LSB) is rightmost (bit 0) Most significant bit (MSB) is leftmost (bit 7 in an 8-bit number) 1 0 0 1 1 1 0 1 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 0 1 2 3 4 5 6 7 Most Significant Bit Least Significant Bit

Data Organization :

Data Organization Bits or one, true or false, on or off, male or female, and right or wrong. Nibbles Group of 4 bits

Bytes :

Bytes

Words :

Words

Double Words :

Double Words

Octal Number System:

Octal Number System Base 8 Eight digits, 0-7 Columns represent (from right to left) units, 8s , 64s , 512s etc. 173 1´8 2 + 7 ´8 1 + 3´8 0 = 123

Hexadecimal Number System:

Hexadecimal Number System Base 16 Sixteen digits, 0-9 and A-F (ten to fifteen) Columns represent (from right to left) units, 16s, 256s, 4096s etc. 7B 7 ´ 16 1 + 11 ´ 16 0 = 123

Hexadecimal Integers:

Hexadecimal Integers More convenient to use than binary numbers Binary, Decimal, and Hexadecimal Equivalents

Decimal to Binary Conversion The quotient is divided by 2 until the new quotient becomes 0 Integer Remainder 41 20 1 10 0 5 0 2 1 1 0 0 1 101001 answer

Converting Decimal to Binary:

Converting Decimal to Binary To convert a fraction, keep multiplying the fractional part by 2 until it becomes 0. Collect the integer parts in forward order Example: 162.375: So, ( 162.375 ) 10 = ( 10100010 . 011 ) 2 162 / 2 = 81 rem 0 81 / 2 = 40 rem 1 40 / 2 = 20 rem 0 20 / 2 = 10 rem 0 10 / 2 = 5 rem 0 5 / 2 = 2 rem 1 2 / 2 = 1 rem 0 1 / 2 = 0 rem 1 0.375 x 2 = 0 .750 0.750 x 2 = 1 .500 0.500 x 2 = 1 .000

Why does this work?:

Why does this work? This works for converting from decimal to any base Why? Think about converting 162 . 375 from decimal to decimal 162 / 10 = 16 rem 2 16 / 10 = 1 rem 6 1 / 10 = 0 rem 1 0.375 x 10 = 3 .750 0.750 x 10 = 7 .500 0.500 x 10 = 5 .000

Binary to Decimal Conversion:

Binary to Decimal Conversion Each bit represents a power of 2 Every binary number is a sum of powers of 2 Decimal Value = ( d n -1 2 n -1 ) + ... + ( d 1 2 1 ) + ( d 0 2 0 ) Binary (10011101) 2 = 2 7 + 2 4 + 2 3 + 2 2 + 1 = 157 1 0 0 1 1 1 0 1 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0 0 1 2 3 4 5 6 7 Some common powers of 2

Converting Binary to Decimal:

Converting Binary to Decimal For example, here is 1101.01 in binary: ( 1 x 2 3 ) + ( 1 x 2 2 ) + ( 0 x 2 1 ) + ( 1 x 2 0 ) + ( 0 x 2 -1 ) + ( 1 x 2 -2 ) = 8 + 4 + 0 + 1 + 0 + 0.25 = 13.25 (1101.01) 2 = (13.25) 10

Binary and Octal Conversions Converting from binary to octal : Make groups of 3 bits, starting from the binary point. Add 0s to the ends of the number if needed. Convert each bit group to its corresponding octal digit. 10110100.001011 2 = 01 0 1 1 0 100 . 001 0 11 2 = 2 6 4 . 1 3 8 111 7 011 3 110 6 010 2 101 5 001 1 100 4 000 0 Binary Octal Binary Octal

Binary and Hex Conversions:

Binary and H ex Conversions Converting from hex to binary : Replace each hex digit with its equivalent 4-bit binary sequence 261.35 16 = 2 6 1 . 3 5 16 = 0010 0110 0001 . 0011 0101 2 1111 F 1011 B 0111 7 0011 3 1110 E 1010 A 0110 6 0010 2 1101 D 1001 9 0101 5 0001 1 1100 C 1000 8 0100 4 0000 0 Binary Hex Binary Hex Binary Hex Binary Hex

Binary and Hex Conversions:

Binary and H ex Conversions Converting from binary to hex : Make groups of 4 bits, starting from the binary point. Add 0s to the ends of the number if needed. Convert each bit group to its corresponding hex digit 10110100.001011 2 = 1011 0100 . 0010 1100 2 = B 4 . 2 C 16 1111 F 1011 B 0111 7 0011 3 1110 E 1010 A 0110 6 0010 2 1101 D 1001 9 0101 5 0001 1 1100 C 1000 8 0100 4 0000 0 Binary Hex Binary Hex Binary Hex Binary Hex

Numbers with Different Bases:

Numbers with Different Bases

Two Interpretations :

Two Interpretations 10100111 2 167 10 -89 10 Signed vs. unsigned is a matter of interpretation; thus a single bit pattern can represent two different values. Allowing both interpretations is useful: Some data (e.g., count, age) can never be negative, and having a greater range is useful. unsigned signed

Why Not Sign+Magnitude? Complicates addition : To add, first check the signs. If they agree, then add the magnitudes and use the same sign; else subtract the smaller from the larger and use the sign of the larger. How do you determine which is smaller/larger? Complicates comparators: Two zeroes! +3 0011 +2 0010 +1 0001 +0 0000 -0 1000 -1 1001 -2 1010 -3 1011

Which is Greater: 1001 or 0011?:

Which is Greater: 1001 or 0011? Answer: It depends! It’s a matter of interpretation , and depends on how x and y were declared: signed? Or unsigned?

Why Not Sign+Magnitude?:

Why Not Sign+Magnitude? 9 3 + 12 + -1 +3 - 4 0011 Hardware Adder 1100 1001 Right! Wrong! Manipulates bit patterns, not numbers!

Why 2’s Complement?:

Why 2’s Complement? +3 0011 +2 0010 +1 0001 0 0000 -1 1111 -2 1110 -3 1101 -4 1100 Just as easy to determine sign as in sign+magnitude. Almost as easy to change the sign of a number. Addition can proceed w/out worrying about which operand is larger. A single zero! One hardware adder works for both signed and unsigned operands.

Easier Hand Method:

Easier Hand Method +6 = 01 10 -6 = 10 10 Step 1: Copy the bits from right to left, through and including the first 1. Step 2: Copy the inverse of the remaining bits.

One Hardware Adder Handles Both! (or subtractor):

One Hardware Adder Handles Both! (or subtractor) 9 3 + 12 + -7 +3 - 4 0011 Hardware Adder 1100 1001 Manipulates bit patterns, not numbers!

Twos Complement:

Twos Complement Most common scheme of representing negative numbers in computers Affords natural arithmetic (no special rules!) To represent a negative number in 2’s complement notation… Decide upon the number of bits ( n ) Find the binary representation of the + ve value in n -bits Flip all the bits (change 1’s to 0’s and vice versa) Add 1

Twos Complement Example:

Twos Complement Example Represent -5 in binary using 2’s complement notation Decide on the number of bits Find the binary representation of the + ve value in 6 bits Flip all the bits Add 1 6 bits(for example) 111010 111010 + 1 111011 -5 000101 +5

“Complementary” Notation:

“Complementary” Notation Conversions between positive and negative numbers are easy For binary (base 2)… +ve -ve 2’s C 2’s C

Properties of Two's Complement Numbers X plus the complement of X equals 0. There is one unique 0. Positive numbers have 0 as their leading bit (MSB); while negatives have 1 as their MSB. The range for an n-bit binary number in 2’s complement representation is: from -2 (n-1) to 2 (n-1) - 1 The complement of the complement of a number is the original number. Subtraction is done by addition to the complement of the number.

The Two’s Complement Representation:

The Two’s Complement Representation

Range of Unsigned Integers:

Range of Unsigned Integers Total no. of patterns of n bits = 2 2 2 … 2 ‘ n’ 2’s = 2 n If n-bits are used to represent an unsigned integer value: Range: 0 to 2 n -1 (2 n different values)

Range of Signed Integers:

Range of Signed Integers Half of the 2 n patterns will be used for positive values, and half for negative. Half is 2 n-1 . Positive Range: 0 to 2 n-1 -1 (2 n-1 patterns) Negative Range: -2 n-1 to -1 (2 n-1 patterns) 8-Bits (n = 8): -2 7 (-128) to +2 7 -1 (+127)

What Values Can Be Represented in N Bits? Unsigned: 0 to 2 N - 1 2s Complement : - 2 N-1 to 2 N-1 - 1 BCD 0 to 10 N/4 - 1 For 32 bits: Unsigned : 0 to 4,294,967,295 2s Complement: - 2,147,483,648 to 2,147,483,647 BCD: 0 to 99,999,999

What Values Can Be Represented in N Bits?:

But , what about Very large numbers? 9,369,396,989,487,762,367,254,859,087,678 . . . or very small number? 0.0000000000000000000000000318579157 What Values Can Be Represented in N Bits?

Only Solution is ……..:

Only Solution is …….. FLOATING POINT REPRESENTATION Floating point representation allows much larger range at the expense of accuracy Floating point representation is otherwise called as SCIENTIFIC REPRESENTATION

Floating Point Representation:

Floating Point Representation 1 . 02 x 10 -1 . 673 x 10 23 -24 Radix (Base ) Mantissa( Significand ): Exponent: It contain both Sign and magnitude Decimal It contain both Sign and magnitude Decimal point

Floating Point Representation:

Binary 1 . xxxxx X 2 yyyyyyy Number of ‘ x’ s determines accuracy Number of ‘ y’ s determines range Radix (Base ) Binary point Mantissa( Significand ): May be Unsigned or Signed Exponent: It contain both Sign and magnitude Floating Point Representation

IEEE floating point format:

IEEE floating point format IEEE defines two formats with different precisions : IEEE Single Precision format IEEE Double Precision format

Decimal Addition Explanation 1 1 1 3 7 5 8 + 4 6 5 7 8 4 1 5 What just happened? 1 1 1 (carry) 3 7 5 8 + 4 6 5 7 8 14 11 15 (sum) 10 10 10 (subtract the base) 8 4 1 5 So when the sum of a column is equal to or greater than the base , we subtract the base from the sum , record the difference , and carry one to the next column to the left.

Binary Addition Rules:

Binary Addition Rules Rules: 0 + 0 = 0 0 + 1 = 1 (just like in decimal) 1 + 0 = 1 1 + 1 = 2 10 = 10 2 = 0 with 1 to carry 1 + 1 + 1 = 3 10 = 11 2 = 1 with 1 to carry

Binary Addition Example 1:

Binary Addition Example 1 1 1 0 1 1 1 + 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 Example 1: Add binary 110111 to 11100 Col 1) Add 1 + 0 = 1 Write 1 Col 2) Add 1 + 0 = 1 Write 1 Col 3) Add 1 + 1 = 2 ( 10 in binary) Write 0 , carry 1 Col 4) Add 1+ 0 + 1 = 2 Write 0 , carry 1 Col 6) Add 1 + 1 + 0 = 2 Write 0 , carry 1 Col 5) Add 1 + 1 + 1 = 3 ( 11 in binary) Write 1 , carry 1 Col 7) Bring down the carried 1 Write 1

Binary Addition Explanation:

Binary Addition Explanation 1 1 0 1 1 1 + 0 1 1 1 0 0 - . 1 1 1 1 1 0 1 0 0 1 1 In the first two columns, there were no carries. In column 3, we add 1 + 1 = 2 Since 2 is equal to the base, subtract the base from the sum and carry 1 . In column 4, we also subtract the base from the sum and carry 1 . In column 6, we also subtract the base from the sum and carry 1 . In column 5, we also subtract the base from the sum and carry 1 . In column 7, we just bring down the carried 1 2 2 2 2 3 2 2 2 What is actually happened when we carried in binary?

Binary Addition Verification:

Binary Addition Verification Verification 110111 2 55 10 + 011100 2 + 28 10 83 10 1 0 1 0 0 1 1 2 = 64+0+16+0+0+2+1 = 83 10 1 1 0 1 1 1 + 0 1 1 1 0 0 1 0 1 0 0 1 1 You can always check your answer by converting the figures to decimal, doing the addition, and comparing the answers.

BCD Addition 965 - 1001 0110 0101 + 672 - 0110 0111 0010 1111 1101 0111 + 0110 0110 0001 0110 0011 0111 (1637) 10 Greater than 9. So add 6 with the nibble Add 965 and 672 Greater than 9. So add 6 with the nibble

Decimal Subtraction Example:

Decimal Subtraction Example 8 0 2 5 - 4 6 5 7 Subtract 4657 from 8025 : 7 9 1 1 1 1 8 6 3 3 Try to subtract 5 – 7 can’t. Must borrow 10 from next column. 4) Subtract 7 – 4 = 3 3) Subtract 9 – 6 = 3 Try to subtract 1 – 5 can’t. Must borrow 10 from next column. But next column is 0, so must go to column after next to borrow. Add the borrowed 10 to the original 0. Now you can borrow 10 from this column. Add the borrowed 10 to the original 5. Then subtract 15 – 7 = 8 . Add the borrowed 10 to the original 1.. Then subract 11 – 5 = 6

Decimal Subtraction Explanation:

Decimal Subtraction Explanation So when you cannot subtract, you borrow from the column to the left . The amount borrowed is 1 base unit , which in decimal is 10 The 10 is added to the original column value , so you will be able to subtract. 8 6 3 3 8 0 2 5 - 4 6 5 7

Binary Subtraction Explanation:

Binary Subtraction Explanation In binary, the base unit is 2 So when you cannot subtract, you borrow from the column to the left. The amount borrowed is 2 . The 2 is added to the original column value, so you will be able to subtract.

Binary Subtraction Example 1:

Binary Subtraction Example 1 1 1 0 0 1 1 - 1 1 1 0 0 Example 1: Subtract binary 11100 from 110011 2 0 0 2 1 2 1 1 0 1 Col 1) Subtract 1 – 0 = 1 Col 5) Try to subtract 0 – 1 can’t. Must borrow from next column. Col 4) Subtract 1 – 1 = 0 Col 3) Try to subtract 0 – 1 can’t. Must borrow 2 from next column. But next column is 0, so must go to column after next to borrow. Add the borrowed 2 to the 0 on the right. Now you can borrow from this column (leaving 1 remaining). Col 2) Subtract 1 – 0 = 1 Add the borrowed 2 to the original 0. Then subtract 2 – 1 = 1 1 Add the borrowed 2 to the remaining 0. Then subtract 2 – 1 = 1 Col 6) Remaining leading 0 can be ignored.

1’s complement Subtraction Steps: First find out the 1’s Complement of the subtrahend. Then do unsigned addition on the numbers. If there is a carry, then take the carry out and add it to the sum for getting the final result. If there is no carry, the result will be negative and we should take the 1’s Complement of the sum to get final result

1’s complement Subtraction Example: 4 – 7 = ? 0 1 0 0 (+4) + 1 0 0 0 + (- 7) 1 1 0 0 No carry, so take the 1’s complement of the result and will be negative. 1’s complement of 1 1 0 0 is 0 0 1 1 = (-3)

Slide 131:

To Subtract two binary numbers, take the 2’s Complement of the Subtrahend and add it with the Minuend. If there is a final carry after the leftmost column addition, discard it and the final result is the obtained one. If there is no carry, the result is negative. So the final result will be the 2’s Complement of the obtained and put a “ – “ sign 2’s Complement Subtraction

Slide 132:

Example without CARRY:- Q: 20 - 25 Write -25 in two's complement format. 1 1 1 0 0 1 1 0 one's complement 1 1 1 0 0 1 1 1 two's complement 1 1 1 0 0 1 1 1 (-25) 0 0 0 1 0 1 0 0 ( 20) 1 1 1 1 1 0 1 1 No carry , so take 2’s Complement of the result. Final Result = 0 0 0 0 0 1 0 1 = (- 5) 2’s Complement Subtraction

Slide 133:

Example with CARRY:- Q: 10 – 5 2’s Complement of 5 = 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 + 1 1 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 Now discard the carry and the obtained is the result Final result = 0 0 0 0 0 1 0 1 = (5) 2’s Complement Subtraction

Slide 134:

The difference, (a – b) is computed as: ( a – b) = a + [2’s complement(b)] In General ………………. 2’s Complement Subtraction

Slide 135:

Since the negative of any number is its two's complement, the sum of a number and its two's complement is always 0 Add +12 and -12 +12 = 00001100 2 -12 = 11110100 2 0 00000000 2 2’s Complement Subtraction

Binary Multiplication:

Binary Multiplication Multiplication can’t be that hard! It’s just repeated addition If we have adders, we can do multiplication also Remember that the AND operation is equivalent to multiplication on two bits :

Binary multiplication example:

Binary multiplication example Since we always multiply by either 0 or 1, the partial products are always either 0000 or the multiplicand ( 1101 in this example) There are four partial products which are added to form the result 1 1 0 1 Multiplicand x 0 1 1 0 Multiplier 0 0 0 0 Partial products 1 1 0 1 1 1 0 1 + 0 0 0 0 1 0 0 1 1 1 0 Product

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Logic Functions:

Logic Functions

Introductory Paragraph:

Introductory Paragraph In its basic form, logic is the realm of human reasoning that tells you a certain proposition (declarative statement) is true if certain conditions are true. Propositions can be classified as true or false . Many situations and processes that you encounter in your daily life can be expressed in the form of propositional, or logic, functions. Since such functions are true/false or yes/no statements, digital circuits with their two-state characteristics are applicable.

Logic Functions:

Logic Functions Several propositions, when combined, form propositional, or logic functions. For example, the propositional statement “The light is on” will be true if the “The bulb is not burned out” is true and if “The switch is on” is true. The first statement is then the basic proposition, and the other two statements are the conditions on which the proposition depends.

Basis for digital computers.:

Basis for digital computers. The true-false nature of logic makes it compatible with binary logic used in digital computers. Electronic circuits can produce logic operations. Circuits are called gates. NOT AND OR

Basic Logic Operations:

Basic Logic Operations There are three basic logic operations: NOT, AND, and OR . Each of the three basic logic operations produces a unique response (output) to a given set of conditions (inputs ). The standard distinctive shape symbols for the three basic logic operations are shown below.

Logic Gates:

Logic Gates A circuit that performs a specified basic logic operation is called a logic gate. Logic gates form the building blocks for digital systems. The true/false statements mentioned earlier are represented by a HIGH (true) and a LOW (false). AND & OR gates can have any number of inputs.

The AND operator (both, all):

The AND operator (both, all) rivers AND salinity dairy products AND export AND Europe

The OR operator (either, any):

The OR operator (either, any) fruit OR vegetables fruit OR vegetables OR cereal

The NOT operator:

The NOT operator fruit NOT apples

Let’s use logic to examine class.:

Let’s use logic to examine class. Please stand up if you are: girl AND black hair AND left handed Please stand up if you are: girl OR black hair OR left handed Please stand up if you are a girl NOT left handed How has the group changed depending on the logical operator used.

Nesting:

Nesting When more than one element is in parentheses, the sequence is left to right. This is called "nesting." (foxes OR rabbits) AND pest control foxes OR rabbits AND pest control (animal pests OR pest animals) NOT rabbits

Order of precedence of logic operators:

Order of precedence of logic operators The order of operations is: AND, NOT, OR Parentheses are used to override priority. Expressions in parentheses are processed first. Parentheses are used to organize the sequence and groups of concepts.

Write out logic statements using logic operators for these.:

Write out logic statements using logic operators for these. You have a buzzer in your car that sounds when your keys are in the ignition and the door is open. You have a fire alarm installed in your house. This alarm will sound if it senses heat or smoke. There is an election coming up. People are allowed to vote if they are a citizen and they are 18. To complete an assignment the students must do a presentation or write an essay.

Truth Tables:

Truth Tables Truth tables provide a way to describe the relationship between inputs and outputs of a logic circuit. Typically , “A” is considered to be the least significant variable in a truth table.

Timing Diagrams:

Timing Diagrams Timing diagrams also show relationships between input and output conditions in a logic circuit.

Logic Gates:

Logic Gates

NOT gate:

NOT gate The simplest possible gate is called an "inverter" or a NOT gate. One bit as input produces its opposite as output. The symbol for a NOT gate is shown below. The truth table for the NOT gate shows input and output. A Q 0 1 1 0 A X 0 1 1 0

Inside NOT Gate:

Inside NOT Gate Transistor as a Switch

Timing analysis of an inverter gate:

Timing analysis of an inverter gate

NOT gate application:

NOT gate application Binary number 1’s complement 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 A group of inverters can be used to form the 1’s complement of a binary number

AND gate:

AND gate The AND gate has the following symbol and truth table. Two or more input bits produce one output bit. Both inputs must be true (1) for the output to be true. Otherwise the output is false (0). A B X 0 0 0 0 1 0 1 0 0 1 1 1

AND gate:

AND gate Multiple Input AND Gate

Inside the AND gate:

Inside the AND gate A B X 0 0 0 0 1 0 1 0 0 1 1 1

Timing analysis of an AND gate:

Timing analysis of an AND gate A B X 0 0 0 0 1 0 1 0 0 1 1 1

Timing analysis of 3 input AND gate:

Timing analysis of 3 input AND gate

Slide 168:

Timing analysis of 3 input AND gate

AND Gate Application:

AND Gate Application The AND operation is used in computer programming as a selective mask . If you want to retain certain bits of a binary number but reset the other bits to 0, you could set a mask with 1’s in the position of the retained bits. If the binary number 10100011 is ANDed with the mask code - 00001111 , what is the result? 00000011

AND Gate Application:

Application of the AND Gate for calculating frequency AND Gate Application

OR gate:

OR gate The OR gate has the following symbol and truth table . Two or more input bits produce one output bit. Either inputs must be true (1) for the output to be true. A B X 0 0 0 0 1 1 1 0 1 1 1 1

OR gate:

OR gate Multiple Input OR Gate

Inside the OR gate:

Inside the OR gate A B X 0 0 0 0 1 1 1 0 1 1 1 1

Timing analysis of OR gate:

Timing analysis of OR gate A B X 0 0 0 0 1 1 1 0 1 1 1 1

Timing analysis of OR gate:

Timing analysis of OR gate A B X 0 0 0 0 1 1 1 0 1 1 1 1

OR Gate Application:

OR Gate Application OR operation can be used in computer programming to SET / RESET certain bits of a binary number. Example: ASCII letters have a 1 in the bit 5 position for all lower case letters and a 0 in this position for all upper case letters.(Bit positions are numbered from right to left starting with 0) What will be the result if you OR an ASCII letter with the 8-bit mask 00100000 ? The resulting letter will be lower case.

Basic AND & OR gate operation:

Basic AND & OR gate operation OR AND OR AND = 0 = 1 0 + 0 = 0 0 + 1 = 1 = 0 = 1 1 • 0 = 0 1 • 1 = 1

Timing analysis of an AND gate Logic analyzer display.:

Timing analysis of an AND gate Logic analyzer display.

Using an AND gate to enable/disable a clock oscillator.:

Using an AND gate to enable/disable a clock oscillator.

Using an OR gate to enable/disable a clock oscillator.:

Using an OR gate to enable/disable a clock oscillator.

An Example: A Burglar Alarm:

An Example: A Burglar Alarm This circuit shows how the elements discussed so far could be used to build a burglar alarm . If any of the switches A or B or C is ON and the Alarm SET switch, D is ON then the Siren E is ON. This is written as :-

Combine gates.:

Combine gates. Gates can be combined. The output of one gate can become the input of another. Try to determine the logic table for this circuit. p q Y = NOT((p AND q) OR q) 0 0 1 0 1 0 1 0 1 1 1 0 Y

Construct the logic table for these circuits.:

Construct the logic table for these circuits.

What happens when you add a NOT to an AND gate?:

What happens when you add a NOT to an AND gate? “N ot AND” = NAND A B X 0 0 1 0 1 1 1 0 1 1 1 0

Symbols for 3 and 8-input NAND gates.:

Symbols for 3 and 8-input NAND gates.

Timing analysis of a NAND gate.:

Timing analysis of a NAND gate.

Timing analysis of a NAND gate.:

Timing analysis of a NAND gate.

What happens when you add a NOT to an OR gate?:

What happens when you add a NOT to an OR gate? “N ot OR” = NOR A B X 0 0 1 0 1 0 1 0 0 1 1 0

NOR gate timing analysis.:

NOR gate timing analysis.

NOR gate timing analysis.:

NOR gate timing analysis.

NOR Gate Application:

NOR Gate Application When is the LED is ON for the circuit shown? The LED will be on when any of the four inputs are HIGH.

“Exclusive” gates:

“Exclusive” gates There are 2 Exclusive Gates in Digital Electronics. Exclusively OR Gate and Exclusive NOR Gate Exclusive OR Gate – XOR Gate & Exclusive NOR Gate – XNOR Gate

XOR Gate:

XOR Gate Exclusive OR gate are true if either input is true but not both. The Symbol and Truth Table is shown below. Output will be high for different inputs A B X 0 0 0 0 1 1 1 0 1 1 1 0

XNOR Gate:

XNOR Gate The Symbol and Truth Table is shown below. Output will be high for same inputs A B X 0 0 1 0 1 0 1 0 0 1 1 1

Logic Gates Review:

Logic Gates Review

NOT Operator:

NOT Operator Y = A

AND Operator:

AND Operator Y = A B

OR Operator:

OR Operator Y = A + B

NAND Operator:

NAND Operator Y = A B

NOR Operator:

NOR Operator Y = A + B

Exclusive OR (XOR) Operator:

Exclusive OR (XOR) Operator Y = A + B

Exclusive NOR (XNOR) Operator:

Exclusive NOR (XNOR) Operator Y = A + B

Universal Gates:

Universal Gates NAND Gate and NOR Gate are known as Universal Gates. All other basic Gates can be constructed using NAND or NOR Gates.

NOT gate from a NAND:

NOT gate from a NAND A Q 0 1 1 0 Universal Gates A Q A Q

AND gate from a NAND:

AND gate from a NAND Universal Gates A B Q 0 0 0 0 1 0 1 0 0 1 1 1 A Q B A B Q

OR gate from a NAND:

OR gate from a NAND Universal Gates We will study after proving DE- MORGAN’S LAW

NOT gate from a NOR:

NOT gate from a NOR A Q 0 1 1 0 Universal Gates A Q

AND gate from a NOR:

AND gate from a NOR Universal Gates We will study after proving DE- MORGAN’S LAW

OR gate from a NOR:

OR gate from a NOR Universal Gates A B X 0 0 0 0 1 1 1 0 1 1 1 1

Logic Gates summary:

Logic Gates summary

Electronic 2 input Logic Gate ICs:

Electronic 2 input Logic Gate ICs

Electronic 2 input Logic Gate ICs:

Electronic 2 input Logic Gate ICs

Electronic 3 input Logic Gate ICs:

Electronic 3 input Logic Gate ICs

Electronic 8 input Logic Gate IC:

Electronic 8 input Logic Gate IC

Slide 215:

Selected Key Terms Inverter Truth table Timing diagram Boolean algebra AND gate A logic circuit that inverts or complements its inputs. A table showing the inputs and corresponding output(s) of a logic circuit. A diagram of waveforms showing the proper time relationship of all of the waveforms. The mathematics of logic circuits. A logic gate that produces a HIGH output only when all of its inputs are HIGH.

Slide 216:

OR gate NAND gate NOR gate Exclusive-OR gate Exclusive-NOR gate A logic gate that produces a HIGH output when one or more inputs are HIGH. A logic gate that produces a LOW output only when all of its inputs are HIGH. A logic gate that produces a LOW output when one or more inputs are HIGH. A logic gate that produces a HIGH output only when its two inputs are at opposite levels. A logic gate that produces a LOW output only when its two inputs are at opposite levels. Selected Key Terms

Class Question: Basic Components:

Class Question: Basic Components AND NAND OR NOR XOR XNOR NOT Name and Symbol Truth table Notation A · B=out A B out AB out 00 0 01 0 10 0 11 1

Slide 218:

The truth table for a 2-input AND gate is Quiz 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 a. b. c. d. 0 1 1 0 0 0 0 1

Slide 219:

The truth table for a 2-input NOR gate is Quiz 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 a. b. c. d. 0 1 1 0 0 0 0 1

Slide 220:

The truth table for a 2-input XOR gate is Quiz 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 a. b. c. d. 0 1 1 0 0 0 0 1

Slide 221:

Quiz 4. The symbol is for which gate a. OR gate b. AND gate c. NOR gate d. XOR gate A B X

Slide 222:

Quiz 5. The symbol is for which gate a. OR gate b. AND gate c. NOR gate d. XOR gate A B X

Slide 223:

Quiz 6. A logic gate that produces a HIGH output only when all of its inputs are HIGH a. OR gate b. AND gate c. NOR gate d. NAND gate

Slide 224:

Quiz 7. The expression X = A + B means a. A OR B b. A AND B c. A XOR B d. A XNOR B

Slide 225:

Quiz 8. A 2-input gate produces the output shown. ( X represents the output) a. OR gate b. AND gate c. NOR gate d. NAND gate A X B

Slide 226:

Quiz 9. A 2-input gate produces a HIGH output only when the inputs agree . a. OR gate b. AND gate c. NOR gate d. XNOR gate

Slide 227:

Answers: 1. c 2. b 3. a 4. a 5. d 6. b 7. c 8. d 9. d Quiz

Logic Gate Characteristics:

Logic Gate Characteristics Gate Voltages and Currents Fan – in Fan – out Propagation Delay Power Requirements Noise Margin or Noise Immunity Speed – Power Product (SPP)

Gate Voltages and Currents:

V IH (min) – High level input voltage. The minimum level required for a logical 1 at an input. Any voltage below this level will not be accepted as a HIGH by the logic circuit V IL (max) – The maximum input voltage for logic zero V OH (min) – The minimum voltage level at a logic circuit output in the logic 1 state under defined load conditions Gate Voltages and Currents

Gate Voltages and Currents:

V OL (max) – Low level output voltage. The maximum voltage level at a logic circuit output in the logical 0 state under defined load conditions I IH – High level input current. The current that flows into an input when a specified high level voltage is applied to that input I IL – Low level input current. The current that flows into an input when a specified low level voltage is applied to that input Gate Voltages and Currents

Gate Voltages and Currents:

I OH – High level output current. The current that flows from an output when a specified high level voltage is obtained at that output I OL – Low level output current. The current that flows from an output when a specified low level voltage is obtained at that output Gate Voltages and Currents

Gate Voltages and Currents:

V IH (min) – High level input voltage V IL (max) – Low level input voltage V OH (min) – High level output voltage V OL (max) – Low level output voltage I IH – High level input current I IL – Low level input current I OH – High level output current I OL – Low level output current Gate Voltages and Currents

Gate Voltages and Currents:

Gate Voltages and Currents

Fan - in:

Fan - in Fan-in specifies the number of inputs available on a gate . Gate primitives often limit the number of inputs to 4 or 5. To build gates with lower fan-in, multiple gates can be interconnected. Implementation of a 7-input NAND gate using NAND gates with 4 or fewer inputs.

Fan - in:

Fan - in Fan-in – the number of inputs to the gate gates with large fan-in are bigger and slower

Fan out:

Fan out Also known as loading factor Defined as the maximum number of logic inputs that an output can drive reliably A logic circuit that specify to have 10 fan out can drive 10 logic inputs

Slide 237:

The inverter has a fan-out of 3 (i.e., the inverter drives 3 inputs). Fan out

Slide 238:

Fanout is the number of standard loads that the output can drive . The number of standard loads is limited by the amount of input current each load requires as compared to the current that the driving gate can deliver. Fanout , therefore, is generally considered to be the smaller of the following two items: Fan out

Propagation Delay:

Propagation Delay Every logic gate experiences some delay (though very small) in propagating signals forward from input to output . This delay is called Gate (Propagation) Delay . Formally, it is the average transition time taken for the output signal of the gate to change in response to changes in the input signals. Three different propagation delay times associated with a logic gate: t PHL : output changing from the High level to Low level t PLH : output changing from the Low level to High level t PD =(t PLH + t PHL )/2 (average propagation delay)

Propagation Delay:

Propagation Delay t PHL : output changing from the High level to Low level t PLH : output changing from the Low level to High level t PD =(t PLH + t PHL )/2 (average propagation delay)

Propagation Delay:

Propagation Delay In reality, output signals normally lag behind input signals. Ideally, there will not be any delay.

Propagation Delay:

Propagation Delay A glitch in the output of the AND gate caused by propagation delay in the inverter . Note that we have assumed zero delay for the AND gate.

Calculation of Circuit Delays:

Calculation of Circuit Delays Amount of propagation delay per gate depends on: ( i ) gate type (AND, OR, NOT, etc) (ii) transistor technology used (TTL,ECL,CMOS etc), (iii) miniaturisation (SSI, MSI, LSI, VLSI) Propagation delay of logic circuit = longest time it takes for the input signal(s) to propagate to the output(s). = earliest time for output signal(s) to stabilise , given that input signals are stable at time 0.

Calculation of Circuit Delays:

Calculation of Circuit Delays In general, given a logic gate with delay, t. If inputs are stable at times t 1 ,t 2 ,..,t n , respectively; then the earliest time in which the output will be stable is: max(t 1 , t 2 , .., t n ) + t To calculate the delays of all outputs of a combinational circuit, repeat above rule for all gates.

Calculation of Circuit Delays:

Calculation of Circuit Delays As a simple example, consider the full adder circuit where all inputs are available at time 0. (Assume each gate has delay t.) where outputs S and C , experience delays of 2t and 3t, respectively.

Power Requirements:

Power Requirements Every IC need a certain power requirement to operate This power supply comes from the voltage supply that connected to the pin on the chip labeled V CC The amount of power require by ICs is determined by the current that it draws from the V CC The actual power is I CC x V CC

Power Requirements:

I CC ( avg ) = (I CCH + I CCL )/2 P D ( avg ) = I CC ( avg ) X Vcc Power Requirements

Noise Margin or Immunity:

Noise Margin or Immunity Stray electric and magnetic fields can induce voltages on the connecting wires between logic circuits – this unwanted signal called noise These cause the input signal to a logic circuit drop below V IH (min) or rise above V IL (max ) Noise Margin or Noise Immunity refers to the circuit’s ability to tolerate noise without causing spurious changes in the output voltage

Noise Margin:

Below given is a diagram showing the range of voltages that can occur at a logic circuit output . Noise Margin

Slide 250:

The high state noise margin V NH is defined as V NH = V OH (min) – V IH (min ) The low state noise margin V NL is defined as V NL = V IL (max) – V OL (max) Noise Margin

Speed – Power Product:

Speed – Power Product Product of Propagation Delay and Power of a Digital IC SPP = Propagation delay X Power Also known as Power – Delay Product . Helps measure quality of a logic family .

Module 1:

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Boolean Algebra:

Boolean Algebra

George Boole:

George Boole My name is George Boole and I lived in England in the 19th century. My work on mathematical logic, algebra, and the binary number system has had a unique influence upon the development of computers. Boolean Algebra is named after me.

What is Boolean Algebra ?:

What is Boolean Algebra ? Boolean Algebra is a mathematical technique that provides the ability to algebraically simplify logic expressions . These simplified expressions will result in a logic circuit that is equivalent to the original circuit, yet requires fewer gates.

Boolean Theorems (1 of 7):

X Y Z 0 0 0 0 1 0 1 0 0 1 1 1 Boolean Theorems (1 of 7) X Y Z 0 0 0 0 1 0 1 0 0 1 1 1 X Y Z 0 0 0 0 1 0 1 0 0 1 1 1 X Y Z 0 0 0 0 1 0 1 0 0 1 1 1 Single Variable - AND Function Theorem #1 Theorem #2 Theorem #3 Theorem #4

Boolean Theorems (2 of 7):

X Y Z 0 0 0 0 1 1 1 0 1 1 1 1 Boolean Theorems (2 of 7) X Y Z 0 0 0 0 1 1 1 0 1 1 1 1 X Y Z 0 0 0 0 1 1 1 0 1 1 1 1 X Y Z 0 0 0 0 1 1 1 0 1 1 1 1 Single Variable - OR Function Theorem #5 Theorem #6 Theorem #7 Theorem #8

Boolean Theorems (3 of 7):

0 1 0 1 0 1 Single Variable – Invert (NOT) Function Boolean Theorems (3 of 7) Theorem #9

Summary of Theorems (1,2 & 3 of 7):

Summary of Theorems (1,2 & 3 of 7) AND Function OR Function NOT Function Theorem #1 Theorem #2 Theorem #3 Theorem #4 Theorem #5 Theorem #6 Theorem #7 Theorem #8 Theorem #9

Example #1: Boolean Algebra:

Example #1: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form . SOP – Sum Of Product (Sum of MINTERMS ) Y = AB + BC POS – Product Of Sum (Product of MAXTERMS ) Y = (A+B) (B+C)

Example #1: Boolean Algebra:

Example #1: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form . Solution ; Theorem #3 ; Theorem #4 ; Theorem #1 ; Theorem #5

Example #2: Boolean Algebra:

Example #2: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form.

Example #2: Boolean Algebra:

Example #2: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form. Solution ; Theorem #3 (twice) ; Theorem #7 ; Theorem #2 ; Theorem #1 ; Theorem #5

Boolean Theorems (4 of 7):

Boolean Theorems (4 of 7) Commutative Law Theorem #10A – AND Function

Boolean Theorems (4 of 7):

Boolean Theorems (4 of 7) Commutative Law Theorem #10B – OR Function

Boolean Theorems (5 of 7):

Boolean Theorems (5 of 7) Associative Law Theorem #11A – AND Function

Boolean Theorems (5 of 7):

Boolean Theorems (5 of 7) Associative Law Theorem #11B – OR Function

Boolean Theorems (6 of 7):

Boolean Theorems (6 of 7) Distributive Law Theorem #12A – AND Function

Boolean Theorems (6 of 7):

Boolean Theorems (6 of 7) Distributive Law Theorem #12B – OR Function

Example #3: Boolean Algebra:

Example #3: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form.

Example #3: Boolean Algebra:

Example #3: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form. Solution ; Theorem #12B ; Theorem #4 ; Theorem #5 ; Theorem #12A ; Theorem #8 ; Theorem #6 ; Theorem #2

Example #4: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form.

Example #4: Boolean Algebra:

Example #4: Boolean Algebra Simplify the following Boolean expression and note the Boolean theorem used at each step. Put the answer in SOP form. ; Theorem #12A ; Theorem #13C ; Theorem #12A ; Theorem #12A ; Theorem #6 ; Theorem #2 Solution

Augustus DeMorgan:

Augustus DeMorgan My name is Augustus DeMorgan. I’m an Englishman born in India in 1806. I was instrumental in the advancement of mathematics and am best known for the logic theorems that bear my name. P.S. George Boolean gets WAY too much credit. He has more theorems, but mine are WAY Cooler!

DeMorgan’s Theorems:

DeMorgan’s Theorems DeMorgan’s Theorems are two additional simplification techniques that can be used to simplify Boolean expressions. Again, the simpler the Boolean expression, the simpler the resulting logic.

DeMorgan Shortcut BREAK THE LINE, CHANGE THE SIGN Break the LINE over the two variables, and change the SIGN directly under the line. For Theorem #14A, break the line, and change the AND function to an OR function. Be sure to keep the lines over the variables. For Theorem #14B, break the line, and change the OR function to an AND function. Be sure to keep the lines over the variables.

DeMorgan’s Theorems:

DeMorgan’s Theorems In other words NAND = bubbled OR NOR = bubbled AND

AND Gate using NOR Gate:

AND Gate using NOR Gate

OR Gate using NAND Gates:

OR Gate using NAND Gates

Summary:

Summary Commutative Law Associative Law Distributive Law Consensus Theorem Boolean & DeMorgan’s Theorems DeMorgan’s Theorem AND OR NOT

DeMorgan’s: Example #1:

DeMorgan’s: Example #1 Example Simplify the following Boolean expression and note the Boolean or DeMorgan’s theorem used at each step. Put the answer in SOP form.

DeMorgan’s: Example #1:

DeMorgan’s: Example #1 Example Simplify the following Boolean expression and note the Boolean or DeMorgan’s theorem used at each step. Put the answer in SOP form. Solution ; Theorem #14A ; Theorem #9 & #14B ; Theorem #9 ; Rewritten without AND symbols and parentheses

DeMorgan’s: Example #2:

DeMorgan’s: Example #2 Example Simplify the output function F 2 shown in the logic circuit. Be sure to note the Boolean or DeMorgan’s theorem used at each step. Put the answer in SOP form.

DeMorgan’s: Example #2:

DeMorgan’s: Example #2 Solution ; Theorem #14A ; Theorem #9 ; Theorem #14B ; Theorem #9 ; Rewritten without AND symbols

Module 1:

Module 1 Introduction Number Systems Binary Arithmetic Logic Functions Boolean Algebra Minimization Techniques

Algebraic expressions f ( x, y, z ) = xy+z Tabular forms Venn diagrams Cubical representations x y z f 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 x z y Representations of Boolean Functions

Cubical Representation:

Cubical Representation

Cubical Representation:

Cubical Representation

0-cube in cubic notation:

x z 00 10 11 01 0-cube in cubic notation 10

0-cube by product terms:

x z 00 10 11 01 0-cube by product terms x z ’

0-cube in cubic notation:

x y z 000 100 101 001 010 011 110 0-cube in cubic notation 111

0-cube by product terms:

x y z 000 111 100 101 001 010 011 110 0-cube by product terms x y z

1-cube in cubic notation:

x y z 000 111 100 101 001 010 011 110 1-cube in cubic notation 1_0

1-cube by product terms:

x y z 000 111 100 101 001 010 011 110 xz’ 1-cube by product terms

2-cube in cubic notation:

x y z 000 111 100 101 001 010 011 110 _0_ 2-cube in cubic notation

2-cube by product terms:

x y z 000 111 100 101 001 010 011 110 Y’ 2-cube by product terms

Cubical Representation of Minterms and Implicants:

Cubical Representation of Minterms and Implicants f1 = a’b’c’+a’b’c+ab’c+abc+abc’ f2 = a’b’c+ab’c

Cubical representation of minterms:

Cubical representation of minterms f 1 = a’b’c ’ + a’b’c + ab’c + abc + abc ’ f 2 = a’b’c + ab’c 111 f1 c b a 000 001 110 101 α β γ δ f2 001 101 α β γ δ β β

Implicants:

IMPLICANT : An implicant of a function is a product term that is included in the function . PRIME IMPLICANT : An implicant is prime if it cannot be included in any other implicants . ESSENTIAL PRIME IMPLICANT : A prime implicant is essential if it is the only one that includes a minterm. Implicants

Implicants:

Example : f( x,y,z ) = xy ’ + yz xy (not I ), xyz(I , not PI), xz ( PI,not EPI ), yz (EPI) Implicants

Exact Minimization of Two-Level Logic:

Exact Minimization of Two-Level Logic Quine-McClusky (1) generate all primes (2) find a minimum cover

Quine-McClusky (2) select a subset of primes f ( x, y, z, w ) = x’z’w ’+ y’z’w ’ + xy’z ’ + xy’w ’ + xz’w + x’y+yw => the selected sum for f is f ( x, y, z, w ) = xy’w ’ + xz’w + x’y A subset of implicant is a cover of the function if each minterm for which the function is 1 is included in at least one implicant of the subset.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.