Switching Theory & Logic Design

UNIT -1

NUMBER SYSTEMS AND CODES

1.1.NUMBER SYSTEMS

A digital system can understand positional number system only where there are a few symbols called digits and these symbols represent different values depending on the position they occupy in the number.

1.1.1.Decimal Number System

The number system that we use in our day-to-day life is the decimal number system. Decimal number system has base 10 as it uses 10 digits from 0 to 9. In decimal number system, the successive positions to the left of the decimal point represent units, tens, hundreds, thousands and so on.

Each position represents a specific power of the base (10). For example, the decimal number 1234 consists of the digit 4 in the units position, 3 in the tens position, 2 in the hundreds position, and 1 in the thousands position, and its value can be written as

(1×1000) + (2×100) + (3×10) + (4×l) = (1×103) + (2×102) + (3×101)  + (4×l00)
=	1000 + 200 + 30 + 1 
=	1234 

1.1.2. Binary Number System:

Characteristics of binary No. system:

•	Uses two digits, 0 and 1. 
•	Also called base 2 number system 
•	Each position in a binary number represents a 0 power of the base (2). Example: 20 
•	Last position in a binary number represents an x power of the base (2). Example: 2x where x represents the last position - 1. 

Example:

101012  = ((1 × 24) + (0 × 23) + (1 × 22) + (0 × 21) + (1 × 20))10

=2110

1.1.3.Octal Number System;

Characteristics of octal No.System:

•	Uses eight digits, 0,1,2,3,4,5,6,7. 
•	Also called base 8 number system 

•	Each position in an octal number represents a 0 power of the base (8). Example: 80 
•	Last position in an octal number represents an x power of the base (8). Example: 8x where x represents the last position - 1. 

Example:

Octal Number – 125708

1.1.4.Hexadecimal Number System

Characteristics of Hexadecimal No.System:

•	Uses 10 digits and 6 letters, 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. 

•	Letters represents numbers starting from 10. A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. 

•	Also called base 16 number system. 

•	Each position in a hexadecimal number represents a 0 power of the base (16). Example 160. 

•	Last position in a hexadecimal number represents an x power of the base (16). Example 16x where x represents the last position - 1. 

Example :

Hexadecimal Number: 19FDE16

1.2. NUMBER CONVERSIONS

The following methods or techniques which can be used to convert numbers from one base to another. Those are:

1.2.1.	Other Base System to Decimal 

1.2.2.	Decimal to Other Base System 

1.2.3.	Binary to Octal 

1.2.4.	Octal to Binary 

1.2.5.	Binary to Hexadecimal 

1.2.6.	Hexadecimal to Binary 

1.2.7.	Octal to Hexadecimal 

1.2.8.	Hexadecimal to Octal 

1.2.1. Other Base System to Decimal System

Steps to convert other base system to decimal system:

•	Step 1 − Determine the column (positional) value of each digit (this depends on the position of the digit and the base of the number system). 

•	Step 2 − multiply the obtained column values (in Step 1) by the digits in the corresponding columns. 

•	Step 3 − Sum the products calculated in Step 2. The total is the equivalent value in decimal. 

Example:

a) Binary  to Decimal conversion:

•	Binary Number − 111012 
•	Step 1= ((1 × 24) + (1 × 23) + (1 × 22) + (0 × 21) + (1 × 20))10 
•	Step 2= (16 + 8 + 4 + 0 + 1)10 

•	Step 3= 2910 

•	Decimal Number − 2910 

b)	Octal to decimal conversion: Octal Number – 125708 

Decimal Number=((1 × 84) + (2 × 83) + (5 × 83) + (7 × 82) + (0 × 80))10 

=549610 

c)	Hexadecimal to decimal conversion: 

Hexadecimal Number: 19FDE16

Decimal Number = ((1 × 164) + (9 × 163) + (F × 162) + (D × 161) + (E × 160))10

=	((1 × 164) + (9 × 163) + (15 × 162) + (13 × 161) + (14 × 160))10 

=	(65536 + 36864 + 3840 + 208 + 14)1 

=	10646210 

1.2.2.Decimal to Other Base System:

Steps to convert decimal to other base system:

•	Step 1 − Divide the decimal number to be converted by the value of the new base. 

•	Step 2 − Get the remainder from Step 1 as the rightmost digit (least significant digit) of new base number. 

•	Step 3 − Divide the quotient of the previous divide by the new base. 

•	Step 4 − Record the remainder from Step 3 as the next digit (to the left) of the new base number. 

Repeat Steps 3 and 4, getting remainders from right to left, until the quotient becomes zero in Step 3.The last remainder thus obtained will be the Most Significant Digit (MSD) of the new base number.

Example:

A)	Decimal to binary Decimal Number: 2910 

Step	Operation	Result	Remainder	
Step 1	29 / 2	14	14	
Step 2	14 / 2	7	0	
Step 3	7 / 2	3	1	
Step 4	3 / 2	1	1	
Step 5	1 / 2	0	1	

As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that the first remainder becomes the Least Significant Digit (LSD) and the last remainder becomes the Most Significant Digit (MSD).

Decimal Number − 2910 = Binary Number − 111012.

1.2.4.Binary to Octal

Steps to convert binary to octal:

•	Step 1 − Divide the binary digits into groups of three (starting from the right). 

•	Step 2 − Convert each group of three binary digits to one octal digit. 

Example

Binary Number − 101012

Step 1: 010 101

Step 2: 28 58

Step 3: 258

1.2.4.Octal to Binary:

Steps to convert octal to binary:

Step 1 − Convert each octal digit to a 3 digit binary number (the octal digits may be treated as decimal for this conversion)
Step 2 − Combine all the resulting binary groups (of 3 digits each) into a single binary number.

Example:

Octal Number − 258

Step 1: 210 510

Step 2:0102 1012

Step 3: 0101012

1.2.5.Binary to Hexadecimal

Steps to convert binary to hexadecimal:

Step 1 − Divide the binary digits into groups of four (starting from the right).

Step 2 − Convert each group of four binary digits to one hexadecimal symbol.

Example:

Binary Number − 101012

Step 1: 0001 0101

Step 2: 110 510

Step 3: 1516

1.2.6.Hexadecimal to Binary

Steps to convert hexadecimal to binary:

•	Step 1 − Convert each hexadecimal digit to a 4 digit binary number (the hexadecimal digits may be treated as decimal for this conversion). 

•	Step 2 − Combine all the resulting binary groups (of 4 digits each) into a single binary number. 

Example:

Hexadecimal Number − 1516

Step 1: 110 510

Step 2: 00012 01012

Step 3: 000101012

1.2.6. Hexadecimal to Octal

When converting from hexadecimal to octal, it is often easier to first convert the hexadecimal number into binary and then from binary into octal

Example:

Convert A2DE hex into octal

Hexadecimal =	A	2	D	E			

Binary =	1010	0010	1101	1110	= 1010001011011110 binary		

Add leading zeros or remove leading zeros to group into sets of three binary digits.

Binary: 1010001011011110 = 001 010 001 011 011 110

Binary =001010001011011110

Octal =		1		2		1		3		3		6		= 121336 octal	

Therefore, through a two-step conversion process, hexadecimal A2DE equals binary 1010001011011110 equals octal 121336.

1.2.7.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.

Example:

Convert 345 octal into hex

Octal =		3		4		5			

Binary =		011		100		101		= 011100101 binary	

Drop any leading zeros or pad with leading zeros to get groups of four binary digits (bits): Binary 011100101 = 1110 0101

Binary =	1110	0101			

Hexadecimal =	E	5	= E5 hex		

Therefore, through a two-step conversion process, octal 345 equals binary 011100101 equals hexadecimal E5.

1.3.Complements

Complements are used in the digital computers in order to simplify the subtraction operation and for the logical manipulations. For each radix-r system (radix r represents base of number system) there are two types of complements.

S.NO.	Complement	Description		

1	Radix Complement	The radix complement is referred to		
		as the r's complement		
				
2				
	Diminished Radix Complement	The  diminished  radix  complement		
		is   referred   to   as   the   (r-1)'s		
		complement		

1.3.1.Binary system complements

As the binary system has base r = 2. So the two types of complements for the binary system are 2's complement and 1's complement.

1's complement

The 1's complement of a number is found by changing all 1's to 0's and all 0's to 1's. This is called as taking complement or 1's complement. Example of 1's Complement is as follows.

2's complement:

The 2's complement of binary number is obtained by adding 1 to the Least Significant Bit (LSB) of 1's complement of the number.

2's complement = 1's complement + 1

Example of 2's Complement is as follows.

1.4.Arithmetic operations :

1.4.1.Binary Addition

It  is  a  key  for  binary  subtraction,  multiplication,  division.  There  are  four  rules  of  binary

addition.

In fourth case, a binary addition is creating a sum of (1 + 1 = 10) i.e. 0 is written in the given column and a carry of 1 over to the next column.

Example :

1.4.2.Binary Subtraction

Subtraction and Borrow, these two words will be used very frequently for the binary subtraction. There are four rules of binary subtraction.

Example :

1.4.3.Binary Multiplication

Binary multiplication is similar to decimal multiplication. It is simpler than decimal multiplication because only 0s and 1s are involved. There are four rules of binary multiplication.

Example :

1.4.4.Binary Division

Binary division is similar to decimal division. It is called as the long division procedure.

Example:

1.4.5.Octal Arithmetic

1.4.5.1.Octal Addition:-

Following octal addition table will help you to handle octal addition.

To use this table, simply follow the directions used in this example: Add 68 and 58. Locate 6 in the A column then locate the 5 in the B column. The point in 'sum' area where these two columns intersect is the 'sum' of two numbers.

Example :

1.4.5.2. Octal Subtraction:-

The subtraction of octal numbers follows the same rules as the subtraction of numbers in any other number system. The only variation is in borrowed number. In the decimal system, you borrow a group of 1010. In the binary system, you borrow a group of 210. In the octal system you borrow a group of 810.

Example :

1.4.7.Hexadecimal Arithmetic:

Following hexadecimal addition table will help you greatly to handle Hexadecimal
addition.

Example:

1.4.8.Hexadecimal Subtraction

The subtraction of hexadecimal numbers follows the same rules as the subtraction of numbers in any other number system. The only variation is in borrowed number. In the decimal system, you borrow a group of 1010. In the binary system, you borrow a group of 210. In the hexadecimal system you borrow a group of 1610.

Example:

1.5.Signed Binary Numbers

In mathematics, positive numbers (including zero) are represented as unsigned numbers. That is we do not put the +ve sign in front of them to show that they are positive numbers.

However, when dealing with negative numbers we do use a -ve sign in front of the number to show that the number is negative in value and different from a positive unsigned value, and the same is true with signed binary numbers.

However, in digital circuits there is no provision made to put a plus or even a minus sign to a number, since digital systems operate with binary numbers that are represented in terms of

“0’s” and “1’s”. When used together in microelectronics, these “1’s” and “0’s”, called a bit (being a contraction of BInary digiT), fall into several range sizes of numbers which are referred to by common names, such as a byte or a word.

We have also seen previously that an 8-bit binary number (a byte) can have a value ranging from 0 (000000002) to 255 (111111112), that is 28 = 256 different combinations of bits forming a single 8-bit byte. So for example an unsigned binary number such as: 010011012 = 64 + 8 + 4 + 1 = 7710 in decimal. But Digital Systems and computers must also be able to use and to manipulate negative numbers as well as positive numbers.

Mathematical numbers are generally made up of a sign and a value (magnitude) in which the sign indicates whether the number is positive, ( + ) or negative, ( – ) with the value indicating the size of the number, for example 23, +156 or -274. Presenting numbers is this fashion is called

“sign-magnitude” representation since the left most digit can be used to indicate the sign and the remaining digits the magnitude or value of the number.

Sign-magnitude notation is the simplest and one of the most common methods of representing positive and negative numbers either side of zero, (0). Thus negative numbers are obtained simply by changing the sign of the corresponding positive number as each positive or unsigned number will have a signed opposite, for example, +2 and -2, +10 and -10, etc.

But how do we represent signed binary numbers if all we have is a bunch of one’s and zero’s. We know that binary digits, or bits only have two values, either a “1” or a “0”, and conveniently a sign also has only two values, a “+” or a “–“. Then we can use a single bit to identify the sign of a signed binary number.

So to represent a positive (N) and a negative (-N) binary number we can use the binary numbers with sign. For signed binary numbers the most significant bit (MSB) is used as the sign. If the sign bit is “0”, this means the number is positive. If the sign bit is “1”, then the number is negative. The remaining bits are used to represent the magnitude of the binary number in the usual unsigned binary number format.

Examples:

1510 as   a   6-bit	10 101111211112	
number		
		
+2310 as  a  6-bit	0101112	
number		
		
-5610 as  a  8-bit	101110002	
number		
		
+8510 as  a  8-bit	010101012	
number		
		
-12710  as  a  8-bit	111111112	
number		

1.6.Binary Coded Decimal (BCD) code

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). But in BCD code only first ten of these are used (0000 to 1001). The remaining six code combinations i.e. 1010 to 1111 are invalid in BCD.

Advantages of BCD Codes

•	It is very similar to decimal system. 

•	We need to remember binary equivalent of decimal numbers 0 to 9 only. 

Disadvantages of BCD Codes

•	The addition and subtraction of BCD have different rules. 

•	The BCD arithmetic is little more complicated. 

•	BCD needs more number of bits than binary to represent the decimal number. So BCD is less efficient than binary. 

1.7.Gray Code

It is the non-weighted code and it is not arithmetic codes. That means there are no specific weights assigned to the bit position. It has a very special feature that, only one bit will change each time the decimal number is incremented as shown in fig. As only one bit changes at a time, the gray code is called as a unit distance code. The gray code is a cyclic code. Gray code cannot be used for arithmetic operation.

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. 

1.8.PARITY CODE

It is the simplest technique for detecting and correcting errors. The MSB of an 8-bits word is used as the parity bit and the remaining 7 bits are used as data or message bits. The parity of 8-bits transmitted word can be either even parity or odd parity.

Even parity -- Even parity means the number of 1's in the given word including the parity bit should be even (2,4,6,....).

Odd parity -- Odd parity means the number of 1's in the given word including the parity bit should be odd (1,3,5,....).

Use of Parity Bit

The parity bit can be set to 0 and 1 depending on the type of the parity required.

•	For even parity, this bit is set to 1 or 0 such that the no. of "1 bits" in the entire word is even. Shown in fig. (a). 

•	For odd parity, this bit is set to 1 or 0 such that the no. of "1 bits" in the entire word is odd. Shown in fig. (b). 

1.9.Hamming code

Hamming code is a set of error-correction code s that can be used to detect and correct biterrors that can occur when computer data is moved or stored. Hamming code is named for R. W. Hamming of Bell Labs.

Like other error-correction code, Hamming code makes use of the concept of  parity andparity  bit s, which are bits that are added to data so that the validity of the data can

be checked when it is read or after it has been received in a data transmission. Using more than one parity bit, an error-correction code can not only identify a single bit error in the data unit, but also its location in the data unit.

In data transmission, the ability of a receiving station to correct errors in the received data is called  forward error correction (FEC) and can increase  throughput on a data link when there is a lot of  noise present. To enable this, a transmitting station must add extra data (called error correction bits ) to the transmission. However, the correction may not always represent a cost saving over that of simply resending the information. Hamming codes make FEC less expensive to implement through the use of a block parity mechanism.

1.10.ASCII:American standard code information interchange code:

•	It is 7-bit or 8-bit alphanumeric code. 
•	7-bit code is standard supports 127 characters ASCII. 

•	Standard ASCII series starts from 00h to 7Fh, where 00h-1Fh are used as control characters and 20h-7Fh as graphics symbols. 

•	8-bit code is extended ASCII supports 256 symbols where special graphics and math's symbols are added. 

•	Extended ASCII series starts from 80h to FFh. 

1.11.Boolean Algebra

Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. It is also called as Binary Algebra orlogical Algebra. Boolean algebra was invented by George Boole in 1854.

Boolean Laws

There are six types of Boolean Laws.

Commutative law

Any binary operation which satisfies the following expression is referred to as commutative operation.

Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit.

Associative law

This law states that the order in which the logic operations are performed is irrelevant as their effect is the same.

Distributive law

Distributive law states the following condition.

AND law

These laws use the AND operation. Therefore they are called as AND laws.

OR law

These laws use the OR operation. Therefore they are called as OR laws.

INVERSION law

This law uses the NOT operation. The inversion law states that double inversion of variable results in the original variable itself.

1.12.De Morgan's Theorems

Theorem 1

•	The left hand side (LHS) of this theorem represents a NAND gate with inputs A and B, whereas the right hand side (RHS) of the theorem represents an OR gate with inverted inputs. 

•	This OR gate is called as Bubbled OR. 

Table showing verification of the De Morgan's first theorem –

Theorem 2

•	The LHS of this theorem represents a NOR gate with inputs A and B, whereas the RHS represents an AND gate with inverted inputs. 

•	This AND gate is called as Bubbled AND. 

Table showing verification of the De Morgan's second theorem −

1.13.Logic Gates:

A logic gate is an elementary building block of a  digital  circuit. Most logic gates have two inputs and one output. At any given moment, every terminal is in one of the two  binary conditions low (0) or high (1), represented by different  voltage levels. The logic state of a terminal can, and generally does, 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 XNOR.

1.13.1.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."

Logic diagram

Truth Table

1.13.2.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."

Logic diagram

Truth Table

1.13.3.NOT Gate:

NOT gate is also known as Inverter. It has one input A and one output Y.

Logic diagram

Truth Table

1.13.4.NAND Gate:

The NAND gate operates as an AND gate followed by a NOT gate. It acts in the manner of the logical operation "and" followed by negation. The output is "false" if both inputs are

"true." Otherwise, the output is "true."

Logic diagram

Truth Table

1.13.5.NOR Gate

The NOR gate is a combination OR gate followed by an inverter. Its output is "true" if

both inputs are "false." Otherwise, the output is "false."

Logic diagram

Truth Table

1.13.6.XOR Gate:

The XOR ( exclusive-OR ) gate acts in the same way as the logical "either/or." The output is "true" if either, but not both, of the inputs are "true." The output is "false" if both inputs are "false" or if both inputs are "true." Another way of looking at this circuit is to observe that the

output is 1 if the inputs are different, but 0 if the inputs are the same.

Logic diagram

Truth Table

1.13.7. XNOR Gate:

The XNOR (exclusive-NOR) gate is a combination XOR gate followed by an inverter. Its

output is "true" if the inputs are the same,  and " false" if the inputs are different.

Logic diagram

Truth Table