### Digital Electronics 1st Year (Unit 1)

**Unit-1 Introduction to Digital Electronics and Number Systems ** Contact Hours: 15

**Unit-1 Introduction to Digital Electronics and Number Systems**Contact Hours: 15**Basics Introduction to digital electronics:** Need of digital, Merits and Demerits, Difference between Analog and Digital Electronics.

**Number System:** Introduction, Binary, Octal and Hexadecimal number system. Signed and unsigned number; Binary operations: Addition, Subtraction, Multiplication and division; Subtractions using 1’s and 2’s compliment, 9’s Compliment, Codes (BCD, Gray, Excess 3, 2421) code, Error detection and correction techniques(Hamming code, Parity check)

**Logic gates and Minimization:** Basic theorem of Boolean algebra, sum of products and product of sums, canonical form, Simplifications using K-map (4 variable)

*Self-Study Topics: Error Detection and ASCII codes.*

## Lecture Topic 1.1.1

*CO1(REMEMBERING):*

*To identify the different types of digital circuits and their difference and to illustrate the various types of gates.*

**Why Computer Engineers need to know about Digital Electronics system?**

Suppose you have to write a code or to design software. You feel that you have written a very perfect errorless code but still machine do not respond accordingly. You don’t know how, or why, but due to some fault or bottleneck in the hardware, or its architecture, your code is either not running or is running but not effectively. In this scenario, if you have an idea of how your hardware is actually interacting with the code that you have written then you can easily fix the problem and get on with your work. And because most of the components on a computer are electronic and work on digital signals only studying DIGITAL ELECTRONICS is useful.

Computer Science and Engineering has several fields of electrical engineering and it required to form computer hardware and software. Computer engineers have training in electronic engineering, software design, and hardware-software integration instead of only software engineering or electronic engineering. Right from the design of individual micro-controllers, microprocessors, personal computers, and supercomputers, to circuit design computer engineers participate in many hardware and software factors of computing.

** History of Digital Electronics**

The binary number system was refined by Gottfried Wilhelm Leibniz (published in 1705) and he also established that by using the binary system, the principles of arithmetic and logic could be joined. Digital logic, was the brain-child of George Boole in the mid 19th century. The inception of digital electronics started with the electronic circuit or gate which was invented in 1835 by Joseph Henry. In the next century, a vacuum tube was invented.

After the invention of various devices, different gadgets were introduced later on. The most useful invention was that of microprocessors and integrated circuits which helped in the development of the present digital electronics. In an 1886 letter,** ****Charles Sanders Peirce**** **described how logical operations could be carried out by electrical switching circuits. Eventually, vacuum tubes replaced relays for logic operations. Lee De Forest’s modification, in 1907, of the Fleming valve can be used as an AND gate. Walther Bothe, inventor of the coincidence circuit, shared the 1954 Nobel Prize in physics, for the first modern electronic AND gate in 1924.

The latest developments which are taking place in the sector of digital electronics have a great influence on kids and teenagers. And thus the present generation has earned the title of ‘digital generation’. It’s a common sight to notice children all around the world with digital phones, interactive TVs, palm pilots, laptops and many other such devices. This is exactly why young people are considered the main target group of companies which manufacture digital electronics.

**What is Digital Electronics?**

Analog signal is a continuous signal as represented in figure 1, in which one time-varying quantity represents another time-based variable. These kind of signals works with physical values and natural phenomena such as earthquake, frequency, volcano, speed of wind, weight, lighting, etc.

Figure 1 Analog Signal

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals. Digital Electronics is very important in today’s life because if digital circuits compared to analog circuits are that signals represented digitally can be transmitted without degradation due to noise. Also in digital system information stored is easier than that of analog system. In figure 2, the representation of digital signal is presented.

Fig 2 Digital signal representation

- Digital stand for digit, digital electronics basically has two conditions which are possible, 0 (low logic) and1 (high logic).(Fig 2)
- Digital electronic systems use a digital signal that is composed of mathematical features to work. “1” as true and “0” as false are called bit and the group of bits are named byte.
- Digital describes electronic technology that generates, stores, and processes data in terms of two states: 1 and number0
- Digital electronic circuits are usually made from large assemblies of logic gates.
- A modem is used to convert the digital information into analog signals. Similarly, to convert analog signals to digital information for different applications.

__Needs of Digital Electronics__

Digital Electronics is very important in today’s life because if digital circuits compared to analog circuits are that signals represented digitally can be transmitted without degradation due to noise.

- Digital signal is used in communication process to minimize the effect of noise.
- Digital Signals carry more information per unit time as compared to analog signals.
- Quality of digital signal is better overlong distance transmission.
- Use of bandwidth is less in case of transmission using digital signals.
- Data is represented in a digital system as a vector of binary variables.
- Digital Systems can provide accuracy limited only by the number of bits used to represent a variable
- Digital systems are less prone to error than analog systems.
- Data representation in a digital system is suitable for error detection and correction.
- Digital systems are designed in a hierarchical manner using re-useable modules.
- Digital techniques are very useful because it is easier to get an electronic device to switch into one of a number of known states than accurately reproduce a continuous range of values.
- Digital electronic circuits are main part in digital electronics which is usually made from large assemblies of logic gates.
- The significance of digital electronics is that are inherently more reliable than analog, in terms of information processing.

**Merits of Digital System:**

- It is economical and easy to design.
- It is very well suited for both numerical and non-numerical information processing.
- It has high noise immunity. But in case of high speed designs a small noise can be induce in the signal.
- It has higher precision rate in terms of accuracy.
- Transmitted signals are not lost over long distance.
- Digital data can be easily stored.
- The voltage at any point in a digital circuit can be either high or low, hence there is less chance of confusion.
- It is easy to duplicate similar circuits and complex digital ICs are manufactured with the advent of microelectronics Technology.
- Adjustable precision and easily controllable by Computer.
- Digital Circuits have the flexibility that can change the functionality of digital circuits by making changes in software instead of changing actual circuit

**Detail Description of important Merits.**

**Easier Designing:**The Digital systems can be easily designed as they involve digital signals. These signals do not require exact value at a particular time but it consists of range of particular values of voltage. Thus, it comprises of basically two values 1 and 0 i.e. high or low.-
**Noise Immune:**Digital systems are noise immune because digital signal consists of range of particular values. Thus, when noise is introduced in the medium and digital signal and analog signal both passes through it. The analog signal will be affected more because it varies continuous with time so it is difficult to identify that noise has destroyed which value of voltage. While in case of digital system, noise affect the particular range of the signal thus, it is clear to identify the particular range of filtering is also easy in case of digital signals. **Information Storage is Simpler:**The storage of information in digital systems is easy. It can be stored by latching thus, the it can be stored for a long period of time.**High Accuracy and Precision:**The digital signal offers high accuracy and precision. This is because the processing of digital signal is done through the switching circuit. While in case of analog signals the processing and its output is highly dependent on circuit components. The accuracy obtained in analog circuits is restricted to 3-4 digits while in case of digital signals the accuracy is far more than the analog circuit.**Programmable:**The digital systems are easily programmable but analog system becomes complex when excessive programming of components is done.

**Demerits of Digital System:**

- Digital systems are expensive because it involves switching elements.
- There need converters, e.g., Analog to Digital (A/D) converter and Digital to Analog (D/A) converter, because physical world is analog.
- Digital electronics circuits require more energy than the analog circuits which are accomplish to do the same tasks. And so these are producing too much heat and so it increases the complexity of the digital electronics circuits

__Analog Vs Digital Sytem__

Analog and Digital signals are the types of signals carrying information. The major difference between both signals is that the analog signals that have a continuous electrical, while digital signals non-continuous electrical. The difference between analog and digital signal can be observed with the various examples of different types of waves.

Figure: Venn diagram showing difference between Analog & Digital

In analog technology, a wave is recorded or used in its original form. So, for example, in an analog tape recorder, a signal is taken straight from the microphone and laid onto tape. In digital technology, the analog wave is sampled at some interval, and then turned into numbers that are stored in the digital device.

Examples of Analog &Digital Devices

Characteristics of Analog Signals:

- These are time-varying electronic signals.
- Lowest and highest values which is either positive or negative.
- It is often either periodic or non-periodic.
- Analog Signal works on continuous data.
- The accuracy of the analog signal isn’t high in comparison to the digital signal.
- It helps you to live natural or physical values.
- Analog signal output form is like Curve, Line, or Graph, so it’s going to not be meaningful to all or any.

**Advantages of Analog Signals:**

Here, are some pros/benefits of Analog Signals.

- It is Easier in processing.
- Analog Signals are best fitted to audio and video transmission.
- It has a coffee cost and is portable.
- It posses higher density.
- Not necessary in Analog Signals to shop for a replacement graphics board.
- It uses less bandwidth than digital sounds.
- It Provide more accurate representation of a sound.
- It is the natural sort of a sound.
- It has less bandwidth.
- Binary digits 0 and 1 represent the optical pulse for storing, processing and transmitting information.

**Disadvantages of Analog Signals:**

Here are some drawbacks of Analog Signals:

- Analog tends to possess a lower quality signal than digital.
- The cables are sensitive to external influences.
- Analog wire is expensive and not easily portable.
- In this, it has Low availability of models with digital interfaces.
- Recording analog sound on tape is sort of expensive if the tape is broken.
- It offers limitations in editing.
- Tape is becoming hard to seek out.
- It is quite difficult to synchronize analog sound.
- Quality is definitely lost.
- Data can become corrupted in analog signals.
- Most of sound capturing devices such as phones etc which may become confusing to store a digital signal.
- Digital sounds can cut an analog acoustic wave which suggests that you simply can’t get an ideal reproduction of a sound.
- It offers poor multi-user interfaces.

**Advantages of Digital Systems**

- The frequency of the carrier wave is usually higher
- The combined wave is transmitted
- Carry more information per second than analogue signals
- Maintain quality over long distances better than analogue signals.
- They’re automatic
- Easier to remove noise
- Can be very immune to noise
- Produces fewer errors: Easier to detect and correct errors, since transmitted data is binary (1s and 0s, only two distinct values).
- They Permits higher maximum transmission rates, for e.g., Optical fiber designed for digital transmission.
- These are more efficient as it is possible to send more digital data through a given circuit.
- They are more secure and easier to encrypt. I
- t is simpler to integrate voice, video and data with these systems.

**Conclusion**

- Analog communication is entirely the use of continuous time varying signal for the transmission of information from the sender to receiver. On the other hand, digital communication utilizes the usage of digital technology for sending the information over the channel.
- Analog communication is becoming obsolete in contemporary times with the advent of digital technology. The drawback of using digital communication is that it requires more bandwidth for transmission which makes it costly. Thus, if cost is not the issue we can use digital communication for our purpose, but if we need an economical system then choose Analog.

**Application of Digital Electronics (Real Life Application)**

Digital systems are designed to store, process, and communicate information in digital form. They are found in a wide range of applications, including process control, communication systems, digital instruments, and consumer products. A computer manipulates information in digital, or more precisely, binary form. Digital electronics includes many applications in real life. **Here are three different and most important application of Digital Electronics.**

- Simple combination lock: This is a simple but effective code lock circuit that has an automatic reset facility. Using XOR gates as bit comparators Build simple gate functions with diodes and a pull up/down resistor Using NOR gates as controlled inverters

Digital Combinational Clock

- A Digital Stopwatch: A digital stopwatch circuit can be worked as a clock in this counter will advance after every one second. The circuit operation begins once open switch is changed to closed position.

- Smartcard: It contains an integrated circuit chip, microprocessor with memory exchange, store the data and manipulate data. Areas of Smart Card Applications includes telecommunications, domestic, ecommerce and retail, banking Application, Government Applications and Secured Physical access.

**Conclusion**

It is therefore essential for engineers and students to understand the fundamentals, implementation and application principles of digital electronics, devices and integrated circuits. This is so that they can use the most appropriate and effective technique to suit their technical need.

**Summary:**

**Topics covered in this lecture are:**

- Difference between analog and digital
- Pros and cons of analog
- Real life applications of digital
- Need of Digital Electronics
- Its advantages
- Its disadvantages

**Introduction**

A number system is a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. Number systems are sometimes also called numeral systems. One of the most ancient and common system of numbers was the Indian number system is the place-value notation developed by Aryabhata in the 5th Century. In the 6th century Brahm gupta introduced the symbol for zero and this number system then spread throughout the world to become the decimal number system that is presently universally used in human writing. Ideally, a number system will:

• Represent a useful set of numbers for example: Integers

• Give every number represented a unique representation

• Reflect the algebraic and arithmetic structure of the numbers.

For example, the decimal representation of whole numbers gives every nonzero whole number a unique representation as a finite sequence of digits beginning with a non-zero digit. For eg the number 56484 has a value.

Number systems are a technique that is also used in representing numbers in computer system architecture. The digital computer represents all kinds of data and information in binary numbers. This implies every value or number that you are saving or feeding into or fetching from the computer system memory has a defined number system. The total number of digits used in a number system is called its base or radix. The base is written after the number as subscript; for instance.

1000110_{2 }= 1000110 base 2

56_{10} = 56 to base of 10

71_{8} = 71 base 8

**Types of number systems**

The four most common number system types are:

- Decimal number system
- Octal number system
- Hexadecimal number system

**1. Binary number system**:

A Binary number system has only two digits that are **0 and 1**. Every number (value) represents with 0 and 1 in this number system. The base of binary number system is 2, because it has only two digits. eg(1101)_{2}

2**. Decimal number system:**

Decimal number system has only ten (10) digits from 0 to 9. Every number (value) is represented with 0,1,2,3,4,5,6,7,8 and 9 in this number system. The base of decimal number system is 10, because it has only 10 digits. Example (234.12)_{10} , (954.01)_{10}

**3. Octal number system:**

Octal number system has only eight (8) digits from **0 to 7**. Every number (value) represents with 0,1,2,3,4,5,6 and 7 in this number system. The base of octal number system is 8, because it has only 8 digits. Example (234.67)_{8}

**4. Hexadecimal number system:**

A Hexadecimal number system has sixteen (16) alphanumeric values from **0 to 9 **and **A to F**. Every number (value) represents with 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E and F in this number system. The base of hexadecimal number system is 16, because it has 16 alphanumeric values. Here A is 10, B is 11, C is 12, D is 14, E is 15 and F is 16.Example (AB92.32)_{16.}

**Conversion of number system**

**Decimal to other**

**RULES:** To convert Number system from **Decimal Number System **to **Any Other Base **is quite easy; you have to follow just two steps:

**A) **Divide the Number (Decimal Number) by the base of target base system (in which you want to convert the number: Binary (2), octal (8) and Hexadecimal (16)).

**B) **Write the remainder from step 1 as a Least Signification Bit (LSB) to Step last as a Most Significant Bit (MSB).

C) In case of decimal point number, the number before decimal point is to be divided by base of desired number system and the number after decimal point is to be multiplied by base of the desired number system.

**Decimal to binary:**

**Example**: Convert (12345)_{10} into binary

**Decimal to octal:**

**Example**: Convert (12345)_{10 into} octal

**Decimal to hexadecimal:**

**Example**: Convert (12345)_{10 }and (725)_{10 }into Hexadecimal

**CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various types of gates.**

**Number systems**

**Conversion of Number System from **Other number system to decimal:

- BINARY TO DECIMAL
- OCTAL TO DECIMAL
- HEXADECIMAL TO DECIMAL

**Binary to Decimal:**

Multiply the digit by 2. Eventually add all the multiplication becomes the Decimal number.

** ****Example**: Convert (1110010)_{2} into decimal

(0 * 2^{0}) + (1 * 2^{1}) + (0 * 2^{2}) + (0 * 2^{3}) + (1 * 2^{4}) + (1 * 2^{5}) + (1 * 2^{6})

= (0 * 1) + (1 * 2) + (0 * 4) + (0 * 8) + (1 * 16) + (1 * 32) + (1 * 64)

= 0 + 2 + 0 + 0 + 16 + 32 + 64 = 114

**Octal to decimal**

**Example: **Convert (345)_{8} into decimal

345 octal = (3 * 8^{2}) + (4 * 8^{1}) + (5 * 8^{0}) = (3 * 64) + (4 * 8) + (5 * 1) = 229 decimal

**Hexadecimal to decimal**

**Example: **Convert the number **35432** HEXADECIMAL to DECIMAL

2x(16^0) + 3x(16^1) + 4x(16^2) + 5x(16^3) + 3x(16^4) =

2 + 3×16 + 4*256 + 5*4096 + 3*65536 =

2 + 48 + 1024 + 20480 + 196608 =

218162

**Binary-Hexadecimal**

An equally easy way to convert from binary to hexadecimal is to group binary digits into sets of four, starting with the least significant (rightmost) digits.

Binary: 11100101 = 1110 0101

Then, look up each group in a table:

**Example: **Convert (** **11101010)_{2} it to hexadecimal** . **

Group the bits into four’s starting from the right hand side

= 1110 1010

Find the Decimal equivalent of each individual group

= 14 10 (in decimal)

Convert to Hexadecimal using the table above

= E A (in Hex)

Then, the hexadecimal equivalent of the binary number1110 10102 is #EA16

Hexadecimal number is (DF7.0A)_{16}

**Hexadecimal to Binary**

Converting from hexadecimal to binary is as easy as converting from binary to hexadecimal. Simply look up each hexadecimal digit to obtain the equivalent group of four binary digits.

**Example: **Convert (240A.3C)_{16} into binary .

2 4 0 A . 3 C

0010 0100 0000 1010 . 0011 110

Answer is (0010010000001010.00111100)_{2}

**Binary to Octal**

An easy way to convert from binary to octal is to group binary digits into sets of three, starting with the least significant (rightmost) digits.

_{}Base 2 (binary) number Base 8 (octal) number

000 0

001 1

010 2

011 3

100 4

101 5

110 6

111 7

**Example:** Convert the binary number (01110101) to an octal number.

Using the grouping method, set the binary number into three numbers in each group.

(01110101)

= 001 110 101 = (1 6 5)_{8}

**Octal to Binary**

Converting from octal to binary is as easy as converting from binary to octal. Simply look up each octal digit to obtain the equivalent group of three binary digits.

**Example: **Convert Octal value of 3058 into its binary representation.

= 3058

= (011 000 101)2

= (011000101)2

**Octal to hexadecimal**

When converting from octal to hexadecimal, it is often easier to first convert the octal number into binary and then from binary into hexadecimal. For example, to convert 345 octal into hex:

**Example:** **Convert 536 from octal to hexadecimal number**

Convert 536(octal) into its binary equivalent we get

(536)_{8} = (101) (011) (110)

=(101011110)_{2}

Now forming the group of 4 binary bits to obtain its hexadecimal equivalent,

(101011110)_{2}= (0001) (0101) (1110)

= (15E)_{16}

So the hexadecimal number of 536 is 15E.

**Hexadecimal to octal**

To convert a hexadecimal number into an octal number, firstly convert it into binary and then by making pairs of three convert it into octal number.

**Example**: Convert (FF)_{16} into (?)_{8}

Step 1: Convert into Binary

In order to convert the hexadecimal number into binary, we need to express every hexadecimal value using 4 binary bits.

Binary equivalent of **F** is **(1111) _{2}**

= (FF)_{16}

= (1111)(1111)

= (11111111**) _{2}**

#### Step 2 : Convert (11111111)2 into Octal

In order to convert the binary number into octal, we need to group every 3 binary bits and calculate the value[From left to right].

#### (11111111**)**_{2 } in Octal

_{2 }

= (11111111**) _{2}**

= (11)(111)(111)

= (377)8

** ****Points to remember**

- Drop any leading zeros or pad with leading zeros to get groups of three or four.
- When converting from octal to hexadecimal, it is easier to first convert the octal number into binary and then from binary into hexadecimal.
- When converting from hexadecimal to octal, it is easier to first convert the hexadecimal number into binary and then from binary into octal.
- While converting from HD to binary, obtain group of four binary digits and from binary to HD pair the binary bits in group of four.
- While converting from octal to binary obtain group of three binary digits and from binary to octal pair the binary bits in group of three.
- Start the pairing in case of fractional number from the decimal point i.e decimal point to left pairing and decimal point to right.

**Summary:**

**In this lecture, the topics covered are:**

- Various Number System
- Conversion of one system to another

## Lecture 1.2.3

**CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various types of gates.**

**CO2(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.**

**Binary Arithmetic**

**Binary number system** employ 2 as the base and so requiring only two different symbols for its digits, 0 and 1, instead of the usual 10 different symbols needed in the decimal system. The numbers from 0 to 10 are thus in binary 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, and 1010. The importance of the binary system to information theory and computer technology derives mainly from the compact and reliable manner in which 0s and 1s can be represented in electromechanical devices with two states—such as “on-off,” “open-closed,” or “go–no go.”

In binary number system there are only 2 digits 0 and 1, and any number can be represented by these two digits. The arithmetic of binary numbers means the operation of addition, subtraction, multiplication and division. Binary arithmetic operation starts from the least significant bit i.e. from the right most side

**Binary Addition**

There are 3 basic rules for adding binary numbers:

0 + 0 = 0

0 + 1 = 1

1 + 1 = 10.

If the sum of 2 bits is greater than 1, we need to shift a column on the left. In decimal system, 1 + 1 = 2. Binary notation of 2 is 10 (1 * 2^1 + 0 * 2^0). So we keep 0 in the 1’s column and shift (carry over) 1 to the 2’s column.

Other rules are same as the decimal system, i.e. we add from right to left and the carry over get’s added to the digits in the next column.

Now lets try adding 11 to 13. Binary for 11 is 1011 and that for 13 is 1101.

1011+ 1101

1’s col = 1 + 1 = 10. We keep 0 in 1’s col and carry over 1 to 2’s col.

2’s col = 1 + 0 + 1 (carry over) = (1 + 0) + 1 = 1 + 1 = 10. Once again we keep 0 in 2’s col and carry over 1 to 4’s col.

4’s col = 0 + 1 + 1 (carry over) = (0 + 1) + 1 = 1 + 1 = 10. Keep 0 in 4’s col and carry over 1 in 8’s col.

8’s col = 1 + 1 + 1 (carry over) = (1 + 1) + 1 = 10 + 1 = 11. Keep 1 in 8’s col and carry over 1 in 16’s col.

The sum is 11000. 11000 = 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0 = 16 + 8 + 0 + 0 + 0 = 24 = 11 + 13.

**Binary Multiplication**

Multiplication in binary is exactly as it is in decimal, i.e. multiply numbers right to left and multiply each digit of one number to every digit of the other number, then sum them up. The 3 basic binary multiplication rules are also similar to decimal.

1 * 1 = 1

1 * 0 = 0 * 1 = 0

0 * 0 = 0

Also, remember that for every left shift of digit of the multiplier, an extra zero needs to be appended to the product. This is similar to the decimal system as well.

1011 X 1101

1011 * 1 (multiplier 1’s col) = 1011

1011 * 0 (multiplier 2’s col) = 00000 (one zero appended at the end)

1011 * 1 (multiplier 4’s col) = 101100 (two zero’s appended at the end)

1011 * 1 (multiplier 8’s col) = 1011000 (three zero’s appended at the end)

Sum up. 1011 + 00000 + 101100 + 1011000 = ((1011 + 00000) + 101100) + 1011000 = (01011 + 101100) + 1011000 = 110111 + 1011000 = 10001111

So the product is 10001111 which is = 1 * 2^7 + 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = 128 + 8 + 4 + 2 + 1 = 143 = 11 * 13.

**Example.**

**Example.**

**Signed Magnitude**

In this notation, an extra bit is added to the left of the number to notate its sign. 0 indicates +ve and 1 indicates -ve. Using 8 bits, +13 is 00001101 and +11 is 00001011. -13 is 10001101 and -11 is 10001011.

(+1100101)2 (01100101)

(+101.001)2 (0101.001)2

(-10010)2 (110010)2

(-110.101)2 (1110.101)2

**Example: Represent the given numbers into sign magnitude format. (+41) ad (-41)**

8-bits Binary equivalent of 41 = 00101001

Sign representation of (+41) = 0 **0101001**

Sign bit = 0

Magnitude = **0101001**

Sign representation of (-41) = 1 **0101001**

**Complement form representation**

**1’s Complement**

In this notation positive numbers are represented exactly as regular binary numbers. So 13 will be 00001101 and 11 will be 00001011. Negative numbers are represented simply by flipping the bit, i.e. 0’s become 1 and 1’s become 0. So -13 will be 11110010 and -11 will be 11110100.

Example: Represent the given numbers in 1’s complement form: +7, -7, +8, -8, +15, and 15.

Decimal Signed 1’s Complement Decimal Signed 1’s Complement

+7 0111 -7 1000

+8 01000 -8 10111

+15 01111 -15 10000

**Two’s Complement representation: **It is obtained by adding one in the one’s complemented form of the binary number. For example, 2’s complement of 0110 is 1010. Since 0110 is (+6)_{10}, therefore, 1010 is (-6)_{10} in 2’s complemented form. MSB is 1, number is negative whereas if the MSB is 0 the number is positive. The maximum positive numbers represented in 1’s complement form is (2^{n-1 }-1) and the negative numbers is – (2^{n-1}). In two’s complement form, maximum seven positive and eight negative numbers can be represented by four binary bits. 2’s complement of a 2’s complement number is number itself.

**Example: Find two’s complement of given numbers:**

Number 1’s complement 1’s complement+1 = 2’s complement

01100100 10011011 10011011+1 = 10011100

10010010 01101101 01101101+1 = 01101110

11011000 00100111 00100111+1 = 00101000

01100111 10011000 10011000+1 = 10011001

**Example: Represent (-17) _{10} in sign magnitude, one’s and two’s complemented form.**

Solution: (+17)_{10} in sign magnitude is represented as (010001)_{2}.

(-17)_{10} in sign magnitude is represented as (110001)_{2}.

_{ }(-17)_{10} in 1’s complemented form is (101110)_{ 2}.

(-17)_{10} in 2’s complemented form is (101111)_{ 2}.

**Binary Subtraction:**

Rules for binary subtraction are listed below.

**Example:** Subtract 111.111 from 1010.010

**Binary Division**

Binary division is similar to decimal division. The only difference is that in decimal system, since we are dividing traditional numbers, the dividend (or portion of it) can be 0, 1 or more than 1 times of the divisor. However in binary, it can only be 0 or 1 times, i.e. the dividend (or portion of it) is >= or < than the divisor.

Let’s try dividing 6 by 3. Binary of 6 is 110 and that or 3 is 11. Following decimal division convention.

We check for a portion of dividend from its left that is >= the divisor.

Then we subtract the multiple of the divisor that is <= the portion of the dividend. The multiplier (1) gets appended to the quotient and result of the subtraction is the remainder.

We bring down 1 bit at the time (going left to right) for the remaining portion of the dividend and check if the expression (remainder + brought down bit) is >= the divisor. If not, we append 0 to the quotient, or else we follow step 2 again.

So the steps for 6 / 3 or 110 / 11 are

Is 1 (left most bit of 110) >= 11. No (we don’t need to add 0 to quotient here since 0s on the left are insignificant).

Is 11 (left 2 most bits of 110) >= 11. Yes. We add 1 (multiplier) to the quotient, and subtract 11 from 11. That gives us a remainder of 0. Note, we are subtracting “one-one from one-one NOT eleven from eleven”.

Now we bring down the remaining bit (0) from 110. Is 0 >= 11. No. So we append 0 to the quotient.

Since we have no more bits remaining in the dividend, we stop here and check. Our remainder is 0 and quotient is 10 (binary) = 2.

**Example**

**Summary:**

**Topics covered here are:**

- Binary Addition
- Subtraction
- Division
- Multiplication

## Lecture Topic 1.2.4

**CO1(REMEMBERING):** To identify the different types of digital circuits and their difference and to illustrate the various

types of gates.

**CO2(UNDERSTANDING):** To understand the various elements of digital system and to implement their applications.

**Signed Number Representations**

**Signed Numbers Representation**

Every number System can be represent in two ways

1. Signed

2. Unsigned

Signed numbers means having both negative values and positive values. Whereas unsigned numbers stored only positive numbers. Number representation techniques like: Binary, Octal, Decimal and Hexadecimal number representation techniques can represent numbers in both signed and unsigned ways. In Decimal system, we know there are positive as well negative numbers like +55,-55.We knows binary equivalent for positive decimal number then what about negative decimal numbers.

**Representation of Binary Numbers:**

Binary numbers can be represented in signed and unsigned way.

Unsigned binary numbers do not have sign bit, whereas signed binary numbers uses sign bit as well or these can be distinguishable between positive and negative numbers.

Figure: Classification of Binary Number System

**1. Unsigned Numbers:**

Unsigned numbers don’t have any sign, means contain only magnitude of the number. So, representation of unsigned binary numbers is all positive numbers only. For example, sign of positive decimal numbers are positive by default. We always assume that there is a positive sign symbol in front of every number.

**Representation of Unsigned Binary Numbers:**

Since there is no sign bit in this unsigned binary number, so N bit binary number represent its magnitude only.

Zero (0) is also unsigned number. This representation has only one zero (0), which is always positive. Every number in unsigned number representation has only one unique binary equivalent form, so this is unambiguous representation technique. The range of unsigned binary number is from 0 to (2^{n}-1).

**Example: convert +20 into binary.**

Simply divide and write in terms of 0s & 1s.** **

** **Ans. (20)_{10} = (10100)_{2}

**Representation of Signed Binary Numbers:**

**Signed** numbers can have positive or negative sign. There are three methods to represent signed numbers:

1. Sign Magnitude

2. 1’s complement

3. 2’s complement

**Sign Magnitude Format:**

For n bit binary number, 1 bit is reserved for sign symbol. If the value of sign bit is 0, then the given number will be positive, else if the value of sign bit is 1, then the given number will be negative. Remaining (n-1) bits represent magnitude of the number.

Generally sign bit is a most significant bit (MSB) of representation,

If MSB=0 means number is positive

If MSB=1 means number is negative.

Write down the magnitude of the number in binary, add extra bit to represent sign bit, whereas in case specified bit format, MSB is considered as sign bit and remaining bits representing as magnitude of the number.

**Example: Represent +18 &-18 in sign magnitude Format.**

Sol. Binary representation of 18=10010

**1’s Complement Form**

1’s complement is required for negative numbers.1’s complement of a number will change the sign of the number.

1’s complement of A= -A

1’s complement of -A= +A

**How to find 1’s complement**:- Write magnitude of number in binary form then for 1’s complement change 0 to 1 and 1 to 0 means just flipping of 0 and 1.Simple NOT operation will change binary number to its complement. The range of 1’s complement form is from -(2^{n-1}-1) to (2^{n-1}-1) .

**Example: Find 1’s complement of 101010.**

Sol.** **1’s complement** **101010 is =010101

Representation of positive numbers in binary form (means nothing is done for positive numbers) and negative numbers in 1’s complement form. Negative number can be obtained by 1’s complement of a positive number and positive number by using 1’s complement of a negative number.

**To verify Negative numbers**: Check out MSB if it is zero means number is positive then directly you can find its magnitude by multiplying each bit with its weight respectively. If MSB is 1, it shows that number is positive then to find its magnitude firstly take 1’s complement of the number after that convert it into decimal by multiplying with weight.

**Example: Represent +12 and -12 in 1’s complement format.**

Binary of 12 = 1100

For +12

=0 1100

For -12

= 1’s compliment of 12 = (01100)’ = 1 0011 =-12

**2’s Complement Form:**

2’s complement is required for negative numbers.2’s complement of a number will change the sign of the number.

2’s complement of A= -A

2’s complement of -A= +A

2’s complement of a number is obtained by adding 1 {least significant bit (LSB)} to 1’s complement.

**2’s complement= 1’s complement +1.**

Represent positive numbers in binary form and negative numbers is represented using 2’s complement. The range of 2’s complement form is from -(2^{n-1}) to (2^{n-1}-1) .

**Example: Represent +33 and -33 in 2’s complement format.**

Sol.** ** Binary form for 33 =1000 1 (already know)

For +33

= 100001

For -33

= 1’s compliment of 33 +1 = (100001)’ + 1 = 011110 + 1 = 011111 = -33

Represent positive numbers in binary form (means nothing is done for positive numbers) and negative numbers in 2’s complement form. Negative number can be obtained by 2’s complement of a positive number and positive number by using 2’s complement of a negative number.

**To Verify Negative Numbers**: Check out MSB if it is zero means number is positive then directly you can find its magnitude by multiplying each bit with its weight respectively. If MSB is 1, it shows that number is negative then to find its magnitude firstly take 2’s complement of the resulted number after that convert it into decimal by multiplying with weight.

**Example: Represent -23 &+23 into 2’s complement format.**

Sol. Represent 23 into binary:

23= (10111)_{2}

**+23 = 010111**

**-23 = 1’s compliment of (010111) + 1 = 101000 + 1 = 101001**

**Example: **Find out decimal equivalent of 10110 if it is represented in

i) Sign magnitude

ii) 1’s complement

iii) 2’s complement

Sol:

10110= -6 in sign magnitude, 10110= -9 in 1’s complement and 10110= -10 in 2’s complement.

**SUMMARY:**

**The topic covered are:**

**1.**** ****Signed Number**

**2.**** ****Representation of Unsigned number**

**CO1(REMEMBERING):** To identify the different types of digital circuits and their difference and to illustrate the various

types of gates.

**CO2(UNDERSTANDING):** To understand the various elements of digital system and to implement their applications.

**Subtraction using 1’s & 2’s complement**

In subtraction by 1’s complement, subtract two binary numbers using 1’s complement.

**The steps to be followed in** **subtraction by 1’s complement** **are:**

· Find 1’s complement of the subtrahend.

· Add this complement with the minuend.

· If the result of addition has a carry from MSB bit then it is added in the last bit LSB.

To verify answer: Check MSB bit:

If MSB= 0 , means number is positive then for magnitude directly convert into decimal by multiplying each bit wit its respective weight.

If MSB= 0 , means number is negative then for magnitude take 1’s complement and covert it into decimal as mentioned above .

**Example: Solve -23 & 36 using 1’s complement.**

**Example: **Find the sum of the following negative numbers represented in a sign-plus-magnitude 5-bit register:

(i) -1010 and -0101

**Question based on 2’s Complement:**

These are steps followed for 2’s complement subtraction:-

- Take 2’s complement for the positive numbers.
- Perform addition.
- If carry is out from MSB then discard carry.

**To verify answer:** Check out MSB of final result

If MSB is 1 then number is negative . Take its 2’s complement to obtain its magnitude.

If MSB is 0 then number is positive then convert it into decimal.

**Example:** Solve -12& 7 using 2’s complement.

**9’s Compliment**

If the number is binary, then we use 1’s complement and 2’s complement. But in case, when the number is a decimal number, we will use the 9’s and 10’s complement. The 10’s complement is obtained from the 9’s complement of the number.

#### 9’s Complement

The 9’s complement is used to find the subtraction of the decimal numbers. The 9’s complement of a number is calculated by subtracting each digit of the number by 9. For example, suppose we have a number 1423, and we want to find the 9’s complement of the number. For this, we subtract each digit of the number 1423 by 9. So, the 9’s complement of the number 1423 is 9999-1423= 8576

#### 10’s Complement

The 10’s complement is also used to find the subtraction of the decimal numbers. The 10’s complement of a number is calculated by subtracting each digit by 9 and then adding 1 to the result. Simply, by adding 1 to its 9’s complement we can get its 10’s complement value. For example, suppose we have a number 1423, and we want to find the 10’s complement of the number. For this, we find the 9’s complement of the number 1423 that is 9999-1423= 8576, and now we will add 1 to the result. So the 10’s complement of the number 1423 is 8576+1=8577.

**Summary:**

**Topics covered here are:**

- Subtraction using 1’s Compliment
- Subtraction using 2’s Compliment
- 9’s and 10’s Compliment

**CO1(REMEMBERING):** To identify the different types of digital circuits and their difference and to illustrate the various

types of gates.

**CO2(UNDERSTANDING):** To understand the various elements of digital system and to implement their applications.

**Types of Digital codes**

- The group of symbols is called as code. The digital data is represented, stored and transmitted as group of binary bits. This group is also called as binary code, given in figure. The binary code is represented by the number as well as alphanumeric letter.

Figure: Types of Binary codes

**Weighted Codes**

Weighted binary codes are those binary codes which obey the positional weight principle. Each position of the number represents a specific weight. Several systems of the codes are used to express the decimal digits 0 through 9. In these codes each decimal digit is represented by a group of four bits.

**BCD Weighted Codes**

In this code each decimal digit is represented by a 4-bit binary number. BCD is a way to express each of the decimal digits with a binary code. In the BCD, with four bits we can represent sixteen numbers (0000 to 1111).

DECIMAL NUMBER | BINARY NUMBER | 4 BIT EXPRESSION(8421) |
---|---|---|

0 | 0 | 0000 |

1 | 1 | 0001 |

2 | 10 | 0010 |

3 | 11 | 0011 |

4 | 100 | 0100 |

5 | 101 | 0101 |

6 | 110 | 0110 |

7 | 111 | 0111 |

8 | 1000 | 1000 |

9 | 1001 | 1001 |

Figure BCD representation in 4 bit

The main advantage of binary coded decimal is that it allows easy conversion between decimal (base-10) and binary (base-2) form.

**Example:**

**a.)**Convert the following decimal (denary) numbers: 85_{10}, 572_{10} and 8579_{10} into their 8421 BCD equivalents.

85_{10} = 1000 0101 (BCD)

572_{10} = 0101 0111 0010 (BCD)

8579_{10} = 1000 0101 0111 1001 (BCD)

**b.)** Convert the following binary numbers: 1001_{2}, 1010_{2}, 1000111_{2} and 10100111000.101_{2} into their decimal equivalents.

1001_{2} = 1001_{BCD} = 9_{10}

1010_{2} = this will produce an error as it is decimal 10_{10} and not a valid BCD number

1000111_{2} = 0100 0111_{BCD} = 47_{10}

10100111000.101_{2} = 0101 0011 0001.1010_{BCD} = 538.625_{10}

**Application of BCD code**

The main advantage of the Binary Coded Decimal system is that it is a fast and efficient system to convert the decimal numbers into binary numbers as compared to the pure binary system. But the **BCD code** is wasteful as many of the 4-bit states (10-to-16) are not used but decimal displays have important **applications**.

**Non-weighted Codes**

Non-weighted or un-weighted codes are those codes in which the digit value does not depend upon their position i.e., each digit position within the number is not assigned fixed value.

**Excess-3 code**

The Excess-3 code is also called as XS-3 code. It is non-weighted code used to express decimal numbers. The Excess-3 code words are derived from the 8421 BCD code words adding (0011)_{2} or (3)10 to each code word in 8421.

2412 code

This code also a 4 bit application code where the binary weights carry 2, 4, 2, 1 from left to right.

DECIMAL NUMBER | BINARY NUMBER | 2421 CODE |

0 | 0 | 0000 |

1 | 1 | 0001 |

2 | 10 | 0010 |

3 | 11 | 0011 |

4 | 100 | 0100 |

5 | 101 | 1011 |

6 | 110 | 1100 |

7 | 111 | 1101 |

8 | 1000 | 1110 |

9 | 1001 | 1111 |

**Gray Codes**

It is the non-weighted code and it is not arithmetic codes. Gray code –also known as Cyclic Code, Reflected Binary Code (RBC), Reflected Binary (RB) or Grey code – is defined as an ordering of the binary number system such that each incremental value can only differ by one bit.

**Steps to obtain Gray code from Binary**

- The MSB (Most Significant Bit) of the gray code will be exactly equal to the first bit of the given binary number.
- The second bit of the code will be exclusive-or (XOR) of the first and second bit of the given binary number, i.e if both the bits are same the result will be 0 and if they are different the result will be 1.
- The third bit of gray code will be equal to the exclusive-or (XOR) of the second and third bit of the given binary number. Thus the binary to gray code conversion goes on. An example is given below to illustrate these steps.

__Steps to obtain Binary code from Gray code__

- The MSB of the binary number will be equal to the MSB of the given gray code.
- Now if the second gray bit is 0, then the second binary bit will be the same as the previous or the first bit. If the gray bit is 1 the second binary bit will alter. If it was 1 it will be 0 and if it was 0 it will be 1.
- This step is continued for all the bits to do
**Gray code to binary conversion**.

**Example:**

Figure: ** **Logic Gate circuit for gray to binary code conversion

**Application of Gray code**

· Gray code is popularly used in the shaft position encoders.

· A shaft position encoder produces a code word which represents the angular position of the shaft.

#### Advantages of Binary Code

Following is the list of advantages that binary code offers.

· Binary codes are suitable for the computer applications.

· Binary codes are suitable for the digital communications.

· Binary codes make the analysis and designing of digital circuits if we use the binary codes.

· Since only 0 & 1 are being used, implementation becomes easy.

#### **Error Detection & Correction Codes**

**Error detection codes** − are used to detect the error undefined present in the received data undefined bitstream. These codes contain some bit undefined, which are included undefined appended to the original bit stream. These codes detect the error, if it is occurred during transmission of the original data undefined bitstream. **Example** − Parity code, Hamming code.

**Error correction codes** − are used to correct the error undefined present in the received data undefined bitstream so that, we will get the original data. Error correction codes also use the similar strategy of error detection codes. **Example** − Hamming code.

Therefore, to detect and correct the errors, additional bit undefined are appended to the data bits at the time of transmission.

#### Parity Code

It is easy to include undefined append one parity bit either to the left of MSB or to the right of LSB of original bit stream. There are two types of parity codes, namely even parity code and odd parity code based on the type of parity being chosen.

#### Even Parity Code

The value of even parity bit should be zero, if even number of ones present in the binary code. Otherwise, it should be one. So that, even number of ones present in **even parity code**. Even parity code contains the data bits and even parity bit.

The following table shows the **even parity codes** corresponding to each 3-bit binary code. Here, the even parity bit is included to the right of LSB of binary code.

Binary Code | Even Parity bit | Even Parity Code |
---|---|---|

000 | 0 | 0000 |

001 | 1 | 0011 |

010 | 1 | 0101 |

011 | 0 | 0110 |

100 | 1 | 1001 |

101 | 0 | 1010 |

110 | 0 | 1100 |

111 | 1 | 1111 |

Here, the number of bits present in the even parity codes is 4. So, the possible even number of ones in these even parity codes are 0, 2 & 4.

- If the other system receives one of these even parity codes, then there is no error in the received data. The bits other than even parity bit are same as that of binary code.
- If the other system receives other than even parity codes, then there will be an error undefined in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position undefined of error.

Therefore, even parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.

#### Odd Parity Code

The value of odd parity bit should be zero, if odd number of ones present in the binary code. Otherwise, it should be one. So that, odd number of ones present in **odd parity code**. Odd parity code contains the data bits and odd parity bit.

The following table shows the **odd parity codes** corresponding to each 3-bit binary code. Here, the odd parity bit is included to the right of LSB of binary code.

Binary Code | Odd Parity bit | Odd Parity Code |
---|---|---|

000 | 1 | 0001 |

001 | 0 | 0010 |

010 | 0 | 0100 |

011 | 1 | 0111 |

100 | 0 | 1000 |

101 | 1 | 1011 |

110 | 1 | 1101 |

111 | 0 | 1110 |

Here, the number of bits present in the odd parity codes is 4. So, the possible odd number of ones in these odd parity codes are 1 & 3.

- If the other system receives one of these odd parity codes, then there is no error in the received data. The bits other than odd parity bit are same as that of binary code.
- If the other system receives other than odd parity codes, then there is an error undefined in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position undefined of error.

Therefore, odd parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.

#### Hamming Code

Hamming code is useful for both detection and correction of error present in the received data. This code uses multiple parity bits and we have to place these parity bits in the positions of powers of 2.

The **minimum value of ‘k’** for which the following relation is correct undefined valid is nothing but the required number of parity bits.

undefined2k≥n+k+1

Where,

‘n’ is the number of bits in the binary code undefined information

‘k’ is the number of parity bits

Therefore, the number of bits in the Hamming code is equal to n + k.

Let the **Hamming code** is undefined bn+k bn+k−1 ….. b3 b2 b1 & parity bits undefined pk, pk−1 ,…. p1. We can place the ‘k’ parity bits in powers of 2 positions only. In remaining bit positions, we can place the ‘n’ bits of binary code.

Based on requirement, we can use either even parity or odd parity while forming a Hamming code. But, the same parity technique should be used in order to find whether any error present in the received data.

Follow this procedure for finding **parity bits**.

- Find the value of
**p1**, based on the number of ones present in bit positions b3, b5, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 20. - Find the value of
**p2**, based on the number of ones present in bit positions b3, b6, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 21. - Find the value of
**p3**, based on the number of ones present in bit positions b5, b6, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 22. - Similarly, find other values of parity bits.

Follow this procedure for finding **check bits**.

- Find the value of c1, based on the number of ones present in bit positions b1, b3, b5, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 20.
- Find the value of c2, based on the number of ones present in bit positions b2, b3, b6, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 21.
- Find the value of c3, based on the number of ones present in bit positions b4, b5, b6, b7 and so on. All these bit positions undefined suffixes in their equivalent binary have ‘1’ in the place value of 22.
- Similarly, find other values of check bits.

The decimal equivalent of the check bits in the received data gives the value of bit position, where the error is present. Just complement the value present in that bit position. Therefore, we will get the original binary code after removing parity bits.

#### Example 1

Let us find the Hamming code for binary code, *d4d3d2d1* = 1000. Consider even parity bits.

The number of bits in the given binary code is n=4.

We can find the required number of parity bits by using the following mathematical relation.

undefined2k≥n+k+1

Substitute, n=4 in the above mathematical relation.

undefined⇒2k≥4+k+1

undefined⇒2k≥5+k

The minimum value of k that satisfied the above relation is 3. Hence, we require 3 parity bits p1, p2, and p3. Therefore, the number of bits in Hamming code will be 7, since there are 4 bits in binary code and 3 parity bits. We have to place the parity bits and bits of binary code in the Hamming code as shown below.

The **7-bit Hamming code** is undefinedb7b6b5b4b3b2b1=d4d3d2p3d1p2bp1

By substituting the bits of binary code, the Hamming code will be undefinedb7b6b5b4b3b2b1=100p3Op2p1. Now, let us find the parity bits.

undefinedp1=b7⊕b5⊕b3=1⊕0⊕0=1

undefinedp2=b7⊕b6⊕b3=1⊕0⊕0=1

undefinedp3=b7⊕b6⊕b5=1⊕0⊕0=1

By substituting these parity bits, the **Hamming code** will be undefinedb7b6b5b4b3b2b1=1001011.

**Summary:**

**BCD codes****Gray Codes****Parity Code****Hamming Code**

## Lecture Topic 1.3.1

**CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various**

**types of gates.**

**CO2(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.**

LOGIC GATES

**Introduction to basic Logic Gate**

- Most logic gates have two inputs and one output and at any given moment, every terminal is in one of the two binary conditions either low (0) or high (1), represented by different voltage levels. The logic state of a terminal change often, as the circuit processes data. In most logic gates, the low state is approximately zero volts(0 V), while the high state is approximately five volts positive (+5 V).

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and NOR.

**AND Gate (.)**

The *AND gate* is so named because, if 0 is called “false” and 1 is called “true,” the gate acts in the same way as the logical “and” operator. The following illustration and table show the circuit symbol and logic combinations for an AND gate. (In the symbol, the input terminals are at left and the output terminal is at right.) The output is “true” when both inputs are “true.” Otherwise, the output is “false.” In other words, the output is 1 only when both inputs one AND two are 1.

**Boolean Expression**: – A.B = Q.

**The Multi-Input Logic AND Gate**

Because the Boolean expression for the logic AND function is defined as (.), which is a binary operation, AND gates can be cascaded together to form any number of individual inputs. However, commercial available AND gate IC’s are only available in standard 2, 3, or 4-input packages. If additional inputs are required, then standard AND gates will be cascaded together to obtain the required input value, for example.

**OR Gate (+)**

The *OR gate* gets its name from the fact that it behaves after the fashion of the logical inclusive “or.” The output is “true” if either or both of the inputs are “true.” If both inputs are “false,” then the output is “false.” In other words, for the output to be 1, at least input one OR two must be 1.

Boolean Expression: – A+B = Q.

**NOT Gate (‘ )**

Inverting NOT gates are single input device which have an output level that is normally at logic level “1” and goes “LOW” to a logic level “0” when its single input is at logic level “1”, in other words it “inverts” (complements) its input signal. The output from a NOT gate only returns “HIGH” again when its input is at logic level “0”.

Boolean Expression: – A = A’

**XOR Gate (**Å**)**

The XOR gate stands for the Exclusive-OR gate. This gate is a special type of gate used in different types of computational circuits. Apart from the AND, OR, NOT, NAND, and NOR gate, there are two special gates, i.e., Ex-OR and Ex-NOR. These gates are not basic gates in their own and are constructed by combining with other logic gates. Their Boolean output function is significant enough to be considered as a complete logic gate. The XOR and XNOR gates are the hybrids gates.

Boolean Expression:- = A Å B

** XNOR Gate**

The XNOR gate is the complement of the XOR gate. It is a hybrid gate. Simply, it is the combination of the XOR gate and NOT gate. The output level of the XNOR gate is high only when both of its inputs are the same, either 0 or 1. The symbol of the XNOR gate is the same as XOR, only complement sign is added. Sometimes, the XNOR gate is also called the **Equivalence gate**.

Boolean Expression:- = AʘB

The logic function implemented by a 2-input Ex-NOR gate is given as “when both A AND B are the SAME” will give an output at Q. In general, an Exclusive-NOR gate will give an output value of logic “1” ONLY when there are an EVEN number of 1’s on the inputs to the gate (the inverse of the Ex-OR gate) except when all its inputs are “LOW”. Then an Ex-NOR function with more than two inputs is called an “even function” or modulo-2-sum (Mod-2-SUM), not an Ex-NOR. This description can be expanded to apply to any number of individual inputs as shown below for a 3-input Exclusive-NOR gate.

**UNIVERSAL GATES**

Individual logic gates can be connected together to form a variety of different switching functions and combinational logic circuits. As we have seen through this *Digital Logic* tutorial section, the three most basic logic gates are the: AND, OR and NOT gates, and given this set of logic gates it is possible to implement all of the possible Boolean switching functions, thus making them a “full set” of **Universal Logic Gates**. There are two universal gates:

- NAND
- NOR

**NAND Gate**

The NAND gate is a special type of logic gate in the digital logic circuit. The NAND gate is the universal gate. It means all the basic gates such as AND, OR, and NOT gate can be constructed using a NAND gate. The NAND gate is the combination of the NOT-AND gate. The output state of the NAND gate will be low only when all the inputs are high. Simply, this gate returns the complement result of the AND gate.

Boolean Expression: – Q = A.B

**NOR Gate**

The NOR gate is also a universal gate. So, we can also form all the basic gates using the NOR gate. The NOR gate is the combination of the NOT-OR gate. The output state of the NOR gate will be high only when all of the inputs are low. Simply, this gate returns the complement result of the OR gate.

Boolean Expression:- A+B = Q

## Lecture Topic 1.3.2

**CO1(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various ****types of gates.**

**CO2(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.****Boolean Theorems of Boolean Algebra**

** **Fundamental Concepts of Boolean algebra:

Boolean algebra is a division of mathematics which deals with operations on logical values and incorporates binary variables in digital electronics. Boolean algebra is a logical algebra in which symbols are used to represent logic levels. Since the logic levels are generally associated with the symbols 1 and 0, whatever letters are used as variables that can take the values of 1 or 0. Boolean algebra has only two mathematical operations, addition and multiplication. These operations are associated with the OR gate and the AND gate, respectively.

**Important rules used in Boolean algebra**

- Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.
- Complement of a variable is represented by an overbar (-). Thus, complement of variable Bis represented as . Thus if B = 0 then =1 and B = 1 then =0.
- ORing of the variables is represented by a plus (+) sign between them. For example ORing of A, B, C is represented as A+ B + C.
- Logical ANDing of the two or more variable is represented by writing a dot between them such as A.B.C. Some time the dot may be omitted like ABC.

**Boolean Theorems/Laws**

In order to simplify the digital logical expressions and circuits, the Boolean equations and expressions representing that logic must be simplified. So, to simplify the Boolean equations and expression, there are some laws and theorems proposed.

**AND Law: **These laws use the AND operation. Therefore they are called AND laws.

- A .0 = 0
- A. 1 = A
- AA = A
- A. A¯=0

**OR Law: **These laws use the OR operation. Therefore they are called OR laws.

- A + 0 = A
- A + 1 = 1
- A + A = A
- A+A¯=1

**Annulment law** – A variable ANDed with 0 gives 0, while a variable ORed with 1 gives 1, i.e.,

- A.0 = 0
- A + 1 = 1

**Identity law** – In this law variable remain unchanged it is ORed with ‘0’ or ANDed with ‘1’, i.e.,

- A.1 = A
- A + 0 = A

**Idempotent law** – A variable remain unchanged when it is ORed or ANDed with itself, i.e.,

- A + A = A
- A.A = A

**Complement law** – In this Law if a complement is added to a variable it gives one, if a variable is multiplied with its complement it results in ‘0’, i.e.,

- A + A’ = 1
- A.A’ = 0

**Double negation law** – A variable with two negation its symbol gets cancelled out and original variable is obtained, i.e.

- ((A)’)’=A

**Commutative law** – Any binary operation which satisfies the following expression is referred to as a commutative operation. Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit. A variable order does not matter in this law, i.e.,

- A + B = B + A
- A.B = B.A

**Associative law** – It states that the order in which the logic operations are performed is irrelevant as their effect is the same. the order of operation does not matter if the priority of variables are same like ‘*’ and ‘/’, i.e.,

- A+(B+C) = (A+B)+C
- A.(B.C) = (A.B).C

**Distributive law** – This law governs opening up of brackets, i.e.,

- A.(B+C) = (A.B)+(A.C)
- A+(B.C) = (A+B).(A+C)

Figure: Logic Gate Implementation of laws.

**Absorption law** -This law involved absorbing the similar variables, i.e.,

- A.(A+B) = A
- A + AB = A

**De Morgan law** – the operation of an AND or OR logic circuit is unchanged if all inputs are inverted, the operator is changed from AND to OR, the output is inverted, i.e.,

- (A.B)’ = A’ + B’
- (A+B)’ = A’.B’

**Example** : De Morgans Law

Expression:

**Duality law** – Duality principle states that “The Dual of the expression can be achieved by replacing the AND operator with OR operator, along with replacing the binary variables, such as replacing 1 with 0 and replacing 0 with 1.This law explains that, replacing the variables doesn’t change the value of the Boolean function.

**Proof**

If we have the Boolean equation like A + B = 0, then the equation formed by replacing the variable 0 with 1 and replacing the OR operator with AND operator is A * B = 1. This means both the Boolean functions are represents the operation of logic circuit. As per Duality principle, if A, B are two variables then both the equations A + B = 0 and A * B = 1 are true in case of same logic circuit.

** Application of Boolean laws:**

- A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the number of logic gates needed to perform a particular logic operation resulting in a list of functions or theorems.
- By reducing the number of logic gates over all delay of the circuit also reduces hence make digital circuits to operate faster with lesser number of logical gates.
- Boolean algebra provides the basis for analyzing the validity of logical propositions because it captures the two-valued character (binary) of statements that may be either true or false
- In particular, by taking the variables to represent values of on and off (or 0 and1),Boolean algebra is used to design and analyze digital switching circuitry, such as that found in personal computers, pocket calculators, CD players, cellular telephones, and a host of other electronic products.

**Examples: **Simplify :Y= (A+C) (AD+AD) +AC+C

Sol. Expression along with Rule(s) Used

Y= (A + C)(AD + AD) + AC + C…………… ……..Original Expression

= (A + C)A(D + D) + AC + C…………………..using Distributive law.

= (A + C)A + AC + C…………………………..using Complement, Identity.

= A((A + C) + C) + C …………………………..Commutative, Distributive.

Y= A.(A + C) + C……………………………………… Associative, Idempotent.

= AA + AC + C ……………………………………..Distributive.

= A + (A + 1) C ……………………………………….Idempotent, Identity, Distributive.

Y =A + C ……………………………..………………. Identity, twice.

You can also use distribution law above and from starting A (A+C)+C to reach the same result by another route.

**Example**: Simplify the following expression: C+BC’

Sol. Given: C+BC’

According to Demorgan’s law, we can write the above expressions as

= C+(B’+C’)

From Commutative law:

= (C+C’)+B’

From Complement law

= 1+B’ = 1

Therefore, C+BC’=1

**SUMMARY:**

- Boolean Algebra
- Boolean Laws
- Expression Minimization

## Lecture 1.3.3

**Sum of Products and Product of Sums, Canonical form**

All Boolean expression can be expressed in either SOP (Sum of Product) or POS (Product of SUM).

y = AB’ + BC’ is the SOP form

In above equation firstly AND gate is used then all are ORed with each other .in this expression each ANDed term is termed as Minterm (m_{i}).

Y= (A + B’)(B + C’) is the POS form

In above equation, each literal is firstly ORed and then all are ANDed. Each ORed term is called as Maxterm (M_{i}). Literal means either a variable or its complement.

**Canonical Form:**

If each minterm/ maxterm is having all the literal (variable or its complement), then it is called as Canonical or Standard Form.

Y = ABC + AB’C + A’BC

Y = (A+B+C)(A’+B+C)(A+B’+C’)

In above equations, each is having all literal so these are on canonical SOP and canonical POS respectively.

**Conversion into canonical SOP form: **For SOP form, replace missing variable with 1 then 1 can be changed to variable using Boolean identity A+A’=1then do simplification by Boolean algebra.

**Example: Convert Y= ABC +B’C’ + A’B’ into canonical SOP form.**

**If expression is be converted into canonical form:**

For POS form, replace missing variable with 0 then 0 can be changed to variable using Boolean identity AA’=0, apply distributive law after that do simplification by Boolean algebra.

**Example: **Convert Y= (A’+B’+C’) (A+C’) into canonical POS form.

**Applications**: In modern area, we want everything should be compact like:

- Mobile Phone
- Integrated Circuits
- Microcontroller
- Laptop etc.

Not only electronics gadgets, we are focusing on maximum applications can be performed by each IC, so to obtain this number of components should be reduced. For reduction K map is one method by which we can reduce number of gates used for a particular circuit.

***Nanotechnology** is the best example.

**SUMMARY:**

- SOP
- POS
- Canonical Forms

## Lecture 1.3.4

**CO(REMEMBERING): To identify the different types of digital circuits and their difference and to illustrate the various ****types of gates.**

**CO(UNDERSTANDING): To understand the various elements of digital system and to implement their applications.**

**CO(APPLYING): To solve the basic problems related to different types of digital circuits and to calculate it using various numerical problems.**

**Karnaugh Map**

Boolean Simplification is divided into two types:

- Boolean Algebra
- K – map

Karnaugh maps (K-maps) are graphical method for the simplification of Boolean functions.

K- maps consists of cell

Where no. of cells =2^{n } as n being no. of input variables

K-map cells are arranged so that adjacent cells differ in only one bit position (based on gray code).

**K maps for SOP & POS form shown below: **

Cell number can be written as in each cell, note down the values of variables as ABCD according to variables in K map. Change the binary into decimal values, which will be the cell number in K-map. For SOP form according to minterms, 1 should be filled in cell, whereas 0 should be filled in cells for POS form as given in questions.

**K- maps according to number of variables:**

According to number of variables, SOP & POS form , k-maps are drawn below:

**For two variables: **

For SOP form and For POS form

**For three variables:**

** **For SOP form and POS form

**For four variables:**

For SOP form and POS form

**Steps to solve expression using K map**

- Identify minterms (SOP ) and Maxterms (POS) as given in problem.
- For SOP put 1’s in blocks of K map according to minterms.
- For POS put 0’s in blocks of K map according to maxterms.
- Make groups/pairs containing total terms in power of 2 like (2,4,8,16) Try to make the largest possible pair.
- Find product terms with variables (that are unchanged along rows and columns) for each group and sum up for SOP form.
- Find sum terms with variables (that are unchanged along rows and column ) for each group and ANDED them for POS form.

**Pairing Rules of K map**

- Adjust cells can be paired. Pairing involves 2(pair), 4 (Quad) & 8 (Octet) cells
- Corner elements can be paired.
- Outermost rows as well as outermost columns can be paired respectively.
- Try to make largest possible pair as shown.
- Groups may overlap.
- Diagonal pair is not possible.
- Make sure in each pair, there must be at least one unpaired 1(sop) or 0(pos).

**Example: **Simply y=∑m(1, 3,4,5,7) using K map.

Output Expression: Y = C + AB’

**Example: **Simply F(A,B,C,D) = ∑ m( 2,3,8,10,11,12,14,15) using K – map and realize the circuit using AOI gates.** **

**Don’t Care Condition:**

The “Don’t Care” conditions allow us to replace the empty cell of a K-Map to form a grouping of the variables. While forming groups of cells, we can consider a “Don’t Care” cell as either 1 or 0 or we can simply ignore that cell. Therefore, “Don’t Care” condition can help us to form a larger group of cells.

A Don’t Care cell is represented by a cross(X) in K-Maps.

Examples: F = ∑m(1, 5, 6, 12, 13, 14) + d(4)

F(A, B, C, D) = M(6, 7, 8, 9) +Փ (10, 11, 12, 13, 14, 15)

**Applications of Topic**: In modern area, we want everything should be compact like:

- Mobile Phone
- Integrated Circuits
- Microcontroller
- Laptop etc.

Not only electronics gadgets, but we are also focusing on maximum applications can be performed by each IC, so to obtain this number of components should be reduced. For reduction K map is one method by which we can reduce number of gates used for a particular circuit.

***Nanotechnology** is the best example.

**SUMMARY:**

- Simplification of Boolean Expression using K-Map
- K Map for SOP
- K Map for POS
- K Map with Don’t Care

Check out other subject study materials: Visit me