Kerala Plus One Computer Science Notes Chapter 2 Data Representation and Boolean Algebra
Computer is a machine that can handle different types of data items. All electronic circuits have two states open and closed. The two-state operation is called binary operation.
Data representation is the method used internally to represent data in a computer. Data can be represented in many ways.
It is a systematic way to represent numbers. A number system has a unique base, which depends upon the number of symbols. The number of symbols used in a number system is called base or radix of a number system. Various number systems are:
1.Decimal number system:
This system involves ten symbols o, 1, 2, 3, 4, 5, 6, 7, 8 and 9 to form a number. Its base is 10. So it is also known as base-10 number system.
The weight of a digit depends on its relative position. Such a number system is known as positional number system. All positional number systems have a base and the place value of a digit is some power of this base. The digit with most weight is called Most Significant Digit (MSD) and the digit with least weight is called Least Significant Digit (LSD)
eg., Consider a decimal number 347.
347 = 3 × 102 + 4 × 101 + 7×10°
= 3× 100 + 4×10 + 7×1 = 300 + 40 + 7 = 347
Here the weight of 3 is 100 and that of 7 is
1. MSD is 3 and LSD is 7.
Consider another example 256.437,
256.437= 2 × 102 + 5 x 101 + 6 x 10° + 4 × 10-1 + 3 x 10-2 + 7 × 10-3
= 200 + 50 + 6 +4 × 0.1+3 × 0.01+ 7 × 0.001
= 256 + 0.4 + 0.03 + 0.007
Here MSD is 2 and LSD is 7.
2. Binary number system:
A number system which uses only two symbols 0 and 1 to form a number is called binary number system. Base of this number system is 2. So it is also called base-2 number system. Each digit of a binary number is called bit. A bit stands for binary digit.
eg., (1100)2= 1 × 23 + 1 ×22 + 0 × 2+ 0×2°
=8+4+o+o = 12
Here MSD is 1 and LSD is 0.
Consider another example 11.01,
11.01= 1 × 21 + 1 ×20 + 0 x 2-1 + 1 × 2-2
= 2 + 1 + 0 + 1 × 1/4
= 3 + 0.25
Here MSD is 1 and LSD is 1.
3. Octal number system:
A number system which uses eight symbols 0, 1, 2, 3,4,5, 6 and 7 to form a number is called octal number system. Base of this number system is 8 and hence it is also called base- 8 number system.
eg., Consider an octal number (267)g
267= 2 ×82 + 6×8-1 + 7×8°
= 2×64 + 6×8 + 7×1 = 128 + 48 + 7 = 183
Consider another example (172.4)g
172.4 = 1 × 82 + 7 × 81 + 2 × 8° + 4 × 8-1 = 64 + 56 + 2 + 4 ×1/8 = 122 + 0.5 = 122.5
4. Hexadecimal number system:
A number system which uses 16 symbols o, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F to form a number is called hexadecimal number system. Base of this number system is 16, so it is also called base-16 number system.
The symbols A, B, C, D, E and F are used to represent the decimal numbers to, it, 12, 13, 14 and 15 respectively.
eg., Consider hexadecimal number (12A)16 12A= 1 × 162 + 2 ×161 + 10 x 160
= 256 + 2 × 16 + 10 × 1
= 256 + 32 + 10
Consider another example (3D.E)16 3D.E= 3 ×161 + 13×160 + 14 x 16-1
= 48 + 13 + 14 × 1/16
= 61 + 0.875
Importance of octal and hexadecimal number system
Digital hardware uses the binary number system for its operations and data. Representing numbers and operations in binary form requires too many bits and needs lot of effort. With octal and hexadecimal, bits are grouped. These groups are replaced with the respective octal or hexadecimal symbol. This conversion processes of binary numbers to octal and hexadecimal number systems and vice versa are very easy.
There are different types of number conversions.
1. Decimal to binary conversion:
The method of converting decimal number to binary number is by repeated division. In this method the decimal number is successively divided by 2 and the remainders are recorded. The binary equivalent is obtained by grouping all the remainders.
In all these cases the remainders will be either o or 1 (binary digit).
eg., Consider a decimal number (75)10
Binary equivalent of an odd decimal number ends with 1 and binary of even decimal number ends with zero.
Decimal fraction to binary conversion: To convert a fractional decimal number to binary, we use the method of repeated multiplication by 2.
2. Decimal to octal conversion:
In this method the number is successively divided by 8 and the remainders are recorded. The octal equivalent is obtained by grouping all the remainders. Remainders will be o, 1, 2, 4, 5, 6 or 7.
3. Decimal to hexadecimal conversion:
In this method, the number is successively divided by 16 and the remainders are recorded. The hexadecimal equivalent is obtained by grouping all the remainders. Remainders will be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E or F.
4. Binary to decimal conversion:
A binary number can be converted into its decimal equivalent by summing up the product of each bit and its weight.
eg., Convert (1110)2 to decimal.
(1110)2 = 1 ×23 + 1×22 + 1 ×21 + o ×2°
(1110)2 = (14)10 Convert (n.n)2 to decimal.
(11.11) = 1 ×21 + 1 ×2° + 1 ×2-1 + 1×2-2
= 2 + 1 + 1/2 + 1/4
= 3 + 0.5 + 0.25
(11. 11)2= (3.75)10
5. Octal to decimal conversion:
An octal number can be converted into its decimal equivalent by summing up the product of each octal digit and its weight.
eg., Convert (156)8 to decimal.
(159)8= 1 × 82 + 5 × 81 + 9×8°
= 64 + 40 + 9
6. Hexadecimal to decimal conversion:
An hexadecimal number can be converted into its decimal equivalent by summing up the product of each hexadecimal digit and its weight.
eg., Convert (3D7)16 to decimal.
(3D7)16 = 3 × 162 + 13 x 161 + 7 x 160
= 3 ×256 + 13 × 16 + 7 ×1
= 768 + 208 + 7
(3D7)16 = (983)10
7. Octal to binary conversion:
An octal number can be converted into binary by converting each octal digit to its 3 bit binary equivalent.
eg., Convert (526)8 to binary.
5 → 101, 2 → 010, 6 → 110 (526)8 = (101010110)2
8. Hexadecimal to binary conversion:
A hexadecimal number can be converted into binary by converting each hexadecimal digit to its 4 bit binary equivalent.
e.g;Convert (4B8)16 to binary.
4 → 0100, B → 1011, 8 → 1000
(4B8)16 = (010010111000)2
9. Binary to octal conversion:
A binary number can be converted into its octal equivalent by grouping binary digits to group of 3 bits and then each group is converted to its octal equivalent. Start grouping from right to left.
eg., Convert (111010001)2 to octal.
111 →7, 010 → 2,001→1 (111010001)2 = (721)g
After grouping, if the left most group has no 3 bits, then add leading zeros to form 3 bit binary.
10. Binary to hexadecimal conversion:
A binary number can be converted into its hexadecimal equivalent by grouping binary digits to group of 4 bits and then each group is converted to its hexadecimal equivalent. Start grouping from right to left.
eg., Convert (101100110100)2 to hexadecimal.
1011 → B, 0011 → 3,0100 → 4
(101100110100)2 = (B34)l6
After grouping, if the left most group has no 4 bits, then add leading zeros to form 4 bit binary.
11. Octal to hexadecimal conversion:
Conversion of an octal number to hexadecimal number is a two step process. Octal number is first converted into binary. This binary equivalent is then converted into hexadecimal.
eg., Convert (457)8 to hexadecimal.
First convert 457 to binary,
4 → 100, 5→ 101, 7→ 111
(457)8 = (100101111)2
Then convert (100101111)2 to hexadecimal
0001 →1, 0010 → 2, 1111 → F
(100101111)2 = (12F)16
Therefore (457)8 = (12F)l6
12. Hexadecimal to octal conversion:
Conversion of an hexadecimal to octal number is also a two step process. Hexadecimal number is first converted into binary. This binary equivalent is then converted into octal, eg., Convert (A2D)16 to octal equivalent. First convert A2D to binary,
A →1010, 2 → 0010, D → 1101
(A2D)16 = (101000101101)2
Then convert (101000101101)2 to octal,
101→ 5, 000 → o, 101→ 5, 101 → 5
(101000101101)2 = (5055)3
Therefore (A2D)16 = (5055)3
Data representation is the method used internally to represent data in a computer.
Representation of Numbers:
Numbers can be classified into integer numbers and floating point numbers. Integers are whole numbers or numbers without any fractional part. A floating point number or a real number is a number with fractional part. These two numbers are treated differently in computer memory.
1. Representation of Integers:
There are three methods for representing an integer number in computer memory. They are:
- Sign and magnitude representation
- 1’s complement representation
- 2’s complement representation
A word is basically a fixed-sized group of bits that are handled as a unit by a processor. Number of bits in a word is called word length.
Sign and magnitude representation: In this method, first bit from left (MSB) is used for representing sign of integer and remaining 7-bits are used for representing magnitude of integer. For negative integers sign bit is 1 and for positive integers sign bit is o.
eg., represent + 25 in sign and magnitude representation.
The number is positive, so the first bit (MSB) is 0.
7 bit binary equivalent of 25 = (0011001)2
So +25 can be represented as (0011001)2
An n-bit word can represent 2n-1 numbers i.e., -(2n-1 -1) to +(2n–1 -1) .
1’s complement representation:
In this method, first find binary equivalent of absolute value of integer. If number of digits in binary equivalent is less than 8, provide zero(s) at the left to make it 8-bit form, 1’s complement of a binary number is obtained by replacing every 0 with 1 and every 1 with 0.
eg., Represent -119 in 1’s complement form. Binary of 119 in 8-bit form = (01110111)2 -119 in 1’s complement form= (1001000)2
Represent +119 in 1’s complement form. Binary of 119 in 8-bit form = (01110111)2 +119 in 1’s complement form= (01110111)2
If the number is negative it is represented as l’s complement of 8-bit form binary. If the number is positive, the 8-bit form binary equivalent itself is the l’s complement representation.
2’s complement representation:
In this method, first find binary equivalent of absolute value of integer and write it in 8- bit form. If the number is negative, it is represented as 2’s complement of 8-bit form binary. If the number is positive, 8-bit form binary itself is the representation.
2’s complement of a binary number is calculated by adding 1 to its 1’s complement.
eg., Represent -38 in 2’s complement form.
Binary of 38 in 8-bit form=(001000110)2
+38 in 2’s complement form is (00100110)2
2. Representation Floating point numbers:
A floating point number or real number consists of an integer part and a fractional part. A real number can be written in a special notation called the floating point notation. Any number in this notation contains two parts, mantissa and exponent.
eg., 15.36 can be written as 0.1536× 102, where 0.1536 is mantissa and power 2 is exponent.
Representation of Characters: Characters can be represented as:
The code called ASCII (American Standard Code for Information Interchange) uses 7 bits to represent each character in computer memory. A unique integer number is assigned to each character. This number called ASCII code of that character is converted into binary for storing in memory. New version ASCII-8, also called extended ASCII, which uses 8 bits for each character, eg., ASCII code for A is 65.
2. EBCDIC (Extended Binary Coded Decimal Interchange Code):
This is similar to ASCII and is an 8 bit code used in computers. If ASCII coded data is to be used in a computer which uses EBCDIC representation, it is necessary to transform ASCII code to EBCDIC code and vice versa.
3. ISCII (Indian Standard Code for Information Interchange/Indian Script Code for Information Interchange):
It is an encoding scheme for representing various writing systems of India. ISCII uses 8-bits for data representation. Nowadays ISCII has been replaced by Unicode.
It is used to represent all characters of written languages of the world and other symbols. Unicode originally used 16 bits. It is maintained by a non-profit organisation called the Unicode Consortium
Representation of Audio, image, video:
- Image: This file consists of two parts – header information and image data.
eg., JPEG (Joint Picture Experts Group), bitmap file format (BMP), Tagged Image File Format (TIFF), Graphics Interchange Format (GIF), Portable (Public) Network Graphic (PNG).
- Audio: This file describes a format, referred to as the ‘container format’, for storing digital audio data, eg., Digital audio data can be stored in different file formats like WAV, MP3, MIDI (Musical Instrument Digital Interface), AIFF, etc.
- Video: It can be represented in AVI (Audio Video Interleave).
3. Subtraction using Complements:
i. Subtraction using 1’s complement:
The steps for subtracting a smaller binary number from a larger binary number are:
Step 1: Add os to the left of smaller number, if necessary, to make two numbers with same number of bits.
Step 2: Find l’s complement of subtrahend (Number to be subtracted, here small number).
Step 3: Add the complement with minu end (Number from which subracting, here larger number).
Step 4: Add the carry 1 to the sum to get the answer.
ii. Subtraction using 2’s complement:
To subtract a smaller binary number from a larger binary number the following are the steps.
Step 1: Add os to the left of smaller number, if necessary, to make the two numbers have the same number of bits.
Step 2: Find 2’s complement of subtrahend (Number to be subtracted, here the smaller number).
Step 3: Add the 2’s complement with minuend
(Number from which subtracting, here the larger number).
Step 4: Ignore the carry.
Binary values or Boolean values:
The values 0 and 1.
The algebra of logic which is a part of mathematical algebra that deals with the operations on variables that represent the values 1 and 0.
Logical statements or truth functions:
The sentences which can be determined to be TRUE or FALSE .
Represented by 1 and 0.
Logical variables or Boolean variables:
The variables which can store (hold) logical constants 1 and 0.
A table that shows Boolean operations and their results. It lists all possible inputs for the given operation and their corresponding output.
The operations performed on these Boolean values.
It is the operands and operators together. A Boolean expression with ‘m’ operands (variables) and ‘n’ operators require 2m rows and m+n columns.
Boolean operators or logical operators
Operators are required to perform Boolean operations. There are three basic logical operators in Boolean algebra. OR – Logical addition, AND- Logical multiplication, NOT – Logical negation.
The first two operators require two operands and the third requires only one operand.
It is a physical device that can perform logical operations on one or more logical inputs and produce a single logical output. Logic gates are primarily implemented using diodes or transistors acting as electronic switches. There are three basic logic gates and they represent the three basic Boolean operations. These gates are:
1. OR gate:
It performs logical addition and the symbol used for this operation is +.
For three inputs A, B, C the output will be A+B+C.
2. AND gate:
It performs logical multiplication and the symbol used for this operation is . (dot)
For three inputs A,B,C the output will be A.B.C
3. NOT gate:
It is a unary operator and hence it requires only one operand. The NOT operator performs logical negation and the symbol used for this operation is (over-bar). The output will be the opposite value of the input. A NOT gate is also called inverter. It can be represented as or A’.
Basic Postulates of Boolean algebra
Boolean algebra being a system of mathematics, consists of certain fundamental laws. These fundamental laws are called postulates.
- Postulate 1: Principles of 0 and 1; If A≠ o, then A = 1 and if A ≠ 1, then A=o
- Postulate 2: OR Operation (Logical Addition); 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1+1 = 1
- Postulate 3: AND Operation (Logical Multiplication); 0.0 = 0, 0.1 = 0, 1.0 =1 = 1
- Postulate 4: NOT Operation (Logical Negation or Compliment Rule); 0 = 1, 1 = 0
Principle of Duality
The principle of duality states that for a Boolean statement, there exists its dual form, which can be derived by
- changing each OR sign (+) to AND sign (.)
- changing each AND sign (.) to OR sign (+)
- replacing each o by 1 and each 1 by o
Basic Theorems of Boolean algebra
The set of rules are known as axioms of the theory. A conclusion can be derived from a set of presumptions by using these axioms or postulates. This conclusion is called law or theorem. Theorems of Boolean algebra provide tools for simplification and manipulation of Boolean expressions.
If X is Boolean variable, the law states that:
- o + X = X; 1 + X = 1 (additive identity)
- o. X = 0; 1.X= X (multiplicative identity)
2. Idempotent law:
It states that: X + X = X and X . X = X
3. Involution law:
This law states that = X
4. Complimentary law:
States that X + X = 1 and X . X = 0
5. Commutative law:
It allows to change the position of variables in OR and AND operations. If X and Y are two variables, the law states that X + Y = Y + X and X . Y = Y. X
6. Associative law:
If X, Y and Z are three variables, the law states that X + (Y + Z) = (X + Y) + Z and X.(Y.Z) = (X.Y).Z
7. Distributive law:
It supports expansion of addition operation over multiplication. If X, Y and Z are variables, the law states that X. (Y + Z) = X. Y + X. Z and X + Y. Z = ( X + Y). ( X + Z)
(X+Y) . (X+Z)= (X+Y) . X + (X+Y) . Z
= X . (X+Y) + Z . (X +Y)
= X.X + X.Y + Z.X + Z.Y
= X + X. Y + Z.X + Z.Y
= X.(1 + Y) + Z.X + Z.Y
= X.(1 + Z) + Z.Y
= X + (Y. Z)
8. Absorption law:
It is a kind of distributive law in which two variables are used and the result will he one of them. If X and Y are variables, the absorption law states that X + (X.γ) = X and X.(X +γ) = X
LHS = X . ( X + Y)
= X . X + X . Y
= X + X . Y
= X. 1
De Morgan’s Theorems
De Morgan proposed two theorems to simplify complicated Boolean expressions. These theorems are known as De Morgan’s theorems. The two theorems are
Literally these theorems can be stated as:
- “The complement of sum of Boolean variables is equal to product of their individual complements”.
- “The complement of product of Boolean variables is equal to sum of their individual complements”.
The NAND and NOR gates are called universal gates. A universal gate is a gate which can implement any Boolean function without using any other gate type.
This is an AND gate with its output inverted by a NOT gate.
This is an OR gate with its output inverted by a NOT gate.