Number System
Data Representation
- Computers are digital devices which uses 1 and 0.
- These 1s and 0s are refered to as binary digits.
- Computers use sequences of bits to digitally represent numbers, letters, punctuation marks, music, picture, and videos.
- Binary information in digital computers is stored in memory or processor registers. Registers contain either data or control information. Data are numbers and other binary-coded information such as ASCII codes, EBCDIC codes etc.
- Numeric data consists of numbers that might be used in arithmetic operations. Computers represent numeric data using the binary number system.
- Character data is composed of letters, symbols, and numerals that are not used in arithmetic
operations. Computers uses several types of codes to represent character data, such as ASCII,
EBCDIC, and Unicode.
- ASCII (American Standard Code for Information Interchange,) requires only 7 bits for each character. ASCII provides codes for 128 characters.
- To work with music and pictures, they must be digitalized. The term to digitize means to convert raw, analog data into digital format representation.
Quantifying Bits and Bytes
- A byte is composed of eight bits.
- Transmission speeds are expressed in bits, whereas storage space is expressed in bytes.
Binary, Octal and Hex-decimal number systems
- The decimal system is also called the base-10 system because it has 10 discrete numerals or symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) so its base or radix is 10. Decimal Examples: 3.1410, 5210, 12.0310
- A binary numbers system has 2 discrete numbers (0, 1) so its base or radix is 2.
- An octal numbers system has 8 discrete numbers (0, 1, 2, 3, 4, 5, 6, 7) so its base or radix is 8.
- A hexa-decimal numbers system has 16 discrete numbers (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F) so its base or radix is 16.
Arithmetic operation on Binary numbers
- The binary arithmetic operations such as addition, subtraction, multiplication and division are similar to the decimal number system. Binary arithmetics are simpler than decimal because they involve only two digits (bits) 1 and 0.
Binary addition
sum carry
0 + 0 = 0 0
1 + 0 = 1 0
0 + 1 = 1 0
1 + 1 = 0 1
example ↓
1 1 0
+ 1 0 1
--------
1 0 1 1
1 1 0 1 1
+ 1 1 1 1
----------
1 0 1 0 1 0
Binary subtraction
1 1 1 0
- 1 1 1
-------
0 1 1 1
1 1 0 1 1
- 1 0 1 1 0
---------
0 0 1 0 1
Binary multiplication
product
↓
0 x 0 = 0
1 x 0 = 0
0 x 1 = 0
1 x 1 = 1
example ↓
1 0 1 0
x 1 0 1
-------
1 0 1 0
0 0 0 0 x
+ 1 0 1 0 x x
-----------
1 1 0 0 1 0
1 1 0 1
x 1 1
--------
1 1 0 1
+ 1 1 0 1 x
-----------
1 0 0 1 1 1
Binary division
1's complement
- 1's complement of a binary number is obtained simply by replacing each 1 by 0 and each 0 by 1.
- Example ↓
0 1 1 0 0 1
↓ ↓ ↓ ↓ ↓ ↓
1 0 0 1 1 0
2's complement
- 2's complement of a binary number can be obtained by adding 1 to it's 1's complement.
- Example ↓
0 1 1 0 0 1 ← number
1 0 0 1 1 0 ← 1's complement
+ 1 ← add 1 to 1's complement
------------
1 0 0 1 1 1 ← 2's complement
- Shortcut for 2's complement
- Steps ↓
- Write down the given number.
- Starting from LSB, copy all the zeros till the first 1.
- Copy the first 1.
- Complement all the remaining bits.
1 0 1 1 1 0 0 0
↓
0 1 0 0 1 0 0 0
Subtraction using 1's and 2's complement
- Before using any complement method for subtraction equate the length of both minuend and subtrahend by attaching zeros.
- Following are the rules for subtraction using 1's complement.
- Take 1's complement of subtrahend.
- Add this complement to minued.
- 5 - 7, here 7 is subtrahend and 5 is minued.
- If a carry is produced by addition then add this carry to the LSB of result. This is called as end around carry (EAC).
- If no carry generated result is negative, and is in 1's complement form. Take 1's complement of result and assign -ve sign to it.
Example 1. Perform following subtraction using 1's complement.
(i) 7 - 3
(ii) 3 -
7
Solution. (i) 7 - 3
Solution. (ii) 3 - 7
2's complement subtraction
- Method of 2's complement is similar to 1's complement subtraction except the end around
carry (EAC). The rules are listed below.
- Take 2's complement of subtrahend.
- Add this complement to minued.
- If a carry is produced, then discard the carry and the result is positive. If no carry is produced result is negative and is in 2's compliment form.
Example 2. Perform following subtraction using 2's complement.
(i) 7 - 5
(ii) 5 -
7
Solution. (i) 7 - 5
Solution. (ii) 5 - 7
Subtraction of decimal using 10's and 9's complement
10's complement subtraction
Steps ↓
- Find 10's complement of subtrahend.
- Add 10's complement of subtrahend to minuend.
- If there is a carry then drop it and you will get your result in positive.
- If there is no carry then find 10's complement of your result and your result will be in negative.
9's complement subtraction
Steps ↓
- Find 9's complement of subtrahend.
- Add 9's complement of subtrahend to minuend.
- If there is a carry then add it to result and your answer will be in positive.
- If there is no carry then find 9's complement of your result and your answer will in negative form.
Overflow & underflow
- Overflow and underflow are both are the errors that occured in arithmetic operations due to a shortage of memory space.
- When some operation is performed on two n-bit numbers and we get result of n+1 bits, this is called
an overflow occurs. Let us consider the addition of two 4-bit numbers
9 ---> 1 0 0 1 +8 ---> 1 0 0 0 --------------- 17 ---> 1 0 0 0 1 - Underflow errors occurs when some operation is performed on floating point numbers. A
floating point number has some fractional part. For ex- 1101.110.
- Suppose a computer can store only 3 fraction digits. So we can store .005 easily. But, when we want to store .005 x .005 =.000025 then only .000 can be stored. This is called underflow error.
Fixed and Floating Point Representation
- There are various types of digital number representation, for example: Binary, octal, decimal, and hexadecimal number system etc. But Binary number system is most relevant and popular for representing numbers in digital computer system.
- There are two major approaches to store real numbers (i.e., numbers with fractional component) in modern computing. These are (i) Fixed Point Notation and (ii) Floating Point Notation. whereas floating point number allows for a varying number of digits after the decimal point.
Fixed Point Representation
- In fixed point notation, there are a fixed number of digits after the decimal point. Fixed point
representation has a fixed number of bits for the integral and fractional parts. There are three
parts of the fixed-point number representation: Sign bit, Integral
part, and Fractional part. The below figure depicts it.
Sign bit: The fixed point number representation uses a sign bit. The negative number has a sign bit 1, while a positive number has a bit 0.
Integral Part: The integral part depends on the register's size; for an 8-bit register, the integral part is 4 bits.
Fractional part: Fractional part is also of different lengths at different places. It depends on the register's size, like in an 8-bit register, integral part is of 3 bits.- 8 bits = 1 Sign bit + 4 bits (integral) + 3 bits (fractional part)
- 16 bits = 1 Sign bit + 9 bits (integral) + 6 bits (fractional part)
- 32 bits = 1 Sign bit + 15 bits (integral) + 9 bits (fractional part)
- If we want to store 4.5
- Step 1: We will convert the number 4.5 to fixed-point notation with the following
format.
- Step 1: We will convert the number 4.5 to fixed-point notation with the following
format.
Floating Point Representation
- Floating Point representation doesn't reserve any specific number of bits for the integer or fractional parts. But instead, it reserves certain bits for the mantissa and the exponent.
- The floating-point representation has two types of notation:
- Scientific notation: it uses a x be form. It is further converted into
floating-point representation. For example, Number = 32635
Number in Scientific Notation = 32.625 x 103
Number is binary form = 1101.101 * 2101 - Normalization notation: It is a special case of scientific notaiton. Normalized
means that we have at least one non-zero digit after the decimal point.
A floating-point representation has three parts: Sign bit, Exponent Part, and Mantissa. We can see the below diagraam to understand these parts.
Sign bit: A negative number has a sign bit 1, while a positive number has a sign bit 0. The sign of any number depends on mantissa, not on exponenet.
Mantissa Part: The mantissa part is of different lengths at different places. It depends on registers like for a 16-bit register, and mantissa part is of 8 bits.
Exponent Part: It is the power of the number. It depends on the size of the register. For example, in the 16-bit register, the exponent part is of 7 bits.
- Scientific notation: it uses a x be form. It is further converted into
floating-point representation. For example, Number = 32635
- How to write numbers in Floating-point notation
- Let the number is 53.5
step 1: We will convert the number 53.5 to binary form 53.5 =110101.1
step 2: Normalize the number (base 2) = (1.101011)*25.
step 3: Represent the binary number in floating-point notation with the following format.
- Let the number is 53.5
ASCII Code
- Many digital applications require the handling of both numerical and alphabetical characters, as well as special characters such as %, $, &, #, etc. These code are called alphanumeric codes, or alphanumeric character set.
- The two most widely used alphanumeric codes are the ASCII code (American Standard Code for Information Interchange) and the EBCDIC (Extended Binary Coded Decimal Interchange Code).
- ASCII is a seven-bit code and includes special control characters.
- It has the 10 decimal numbers, the 26 upper-case and 26 lower-case character of the English language
- as well as large number of special characters, such as SOH (Start of Heading), etc.
- Seven bits gives 27 = 128 code words. The numerals and the upper and lowercase letters add up to 62 characters, leaving 66 7-bit binary strings available for other words.
Gray Code
- There are applications in which it is desirable to represent numerical that changes in only one bit position from one code word to the next adjacent word. This class of code is called a unit distance code (UDC). These are sometimes also called as 'cyclic', 'reflective' or 'gray' code.
- Gray code is binary numeral system where two successive value differ in only one bit.
- Binary number is converted to gray code to reduce switching operation.
- These codes finds great applications in Boolean function minimization using Karnaugh map.
Binary to Gray code conversion lecture
XOR table
- copy the most significant bit as it is
- ( b4 b3 b2 b1 b0 )2 = b4 ( b4 ^ b3) ( b3 ^ b2 ) ( b2 ^ b1 ) ( b1 ^ b0 )
Example 1
1 0 1 1 = 1 ( 1 ^ 0 ) ( 0 ^ 1 ) ( 1 ^ 1 )
= 1 1 1 0
(1011)2 = (1110)gray
Example 2
11001 = 1 ( 1 ^ 1 ) ( 1 ^ 0 ) ( 0 ^ 0 ) ( 0 ^ 1)
= 10101
Excess-3 code
- A decimal code that has been used in some old computers is the excess-3 code. This is an unweighted code.
- It is obtained from the corresponding value of BCD after the addition of 3.
Decimal BCD X-3
0 0000 0011
1 0001 0100
2 0010 0101
3 0011 0110
4 0100 0111
5 0101 1000
6 0110 1001
7 0111 1010
BCD
- In BCD codes, individual decimal digits are coded in binary notation. Thus binary codes representing 0 to 9 decimal digits are allowed.
- Therefore, all BCD codes have atleast four bits (∵ min. no. of bits required to encode to decimal digits = 4)
- For example, decimal 364 in BCD
3 → 0011 6 → 0110 4 → 0100 364 → 0011 0110 0100 - However, we should realize that with 4 bits, total 16 combinations are possible (0000, 0001, ..., 1111) but only 10 are used (0 to 9). The remaining 6 combinations are unvalid and commonly referred to as "UNUSED CODES".
- Example → convert (643)10 into XS3 code
Decimal 6 4 3 Add 3 to each 3 3 3 Sum → 976 Converting the sum into BCD code we have 9 7 6 ↓ ↓ ↓ 1001 0111 0110
BCD Addition
- In many application it is required to add two BCD numbers. But the adder circuits used are
simple binary adders, which does not take care of peculiarity of BCD representation. Thus we
must verify the result for valid BCD by using following rules:
- If the sum is less then or equal to 9, it is valid BCD number.
- If sum is greater than 9, it is invalid. Add 6 (0110) to the sum, to make it valid.
- If a carry is generated when 6 is added, attach this carry at MSB.
- Example 1. Add the following BCD numbers. (i) 1000 and 0101 (ii) 00011001 and 00011000
Solution. (i)1 0 0 0 → 8 + 0 1 0 1 → + 5 ----------- ----- 1 1 0 1 13 since, (1101)2 > (9)10 add 6 (0110) to it 1 1 0 1 0 1 1 0 ------- 1 0 0 1 1 ↓ ↓ 1 3 So, result = 000100111 ← ← ← Carry generated 0 0 0 1 1 0 0 1 → 19 0 0 0 1 1 0 0 0 → +18 ----------------- ---- 0 0 1 1 0 0 0 1 37 Since, a carry is generated we must add 6 (0110) to it. So, 0 0 1 1 0 0 0 1 0 1 1 0 ------------------- 0 0 1 1 0 1 1 1 → (37)10 So, result = 00110111
Error Detection and Error Correction
We know that data is transmitted in binary form.
While transmission of data, if noise are added to the data then it will not be same in receiving
side as it will contain some error.
- To solve this error we use error detection and correction methods.
- To detect the error we use parity bits.
Parity bits A.K.A check bit, these are added with message
Message + parity bit = parity bit code. - Now parity bit code is transmitted to receiver.
- The appended parity bit determines whether the message has any error or not.
There are two types of parity bit code
1- Even parity bit code
- It ensures that message including parity bit must contain even number of 1's.
2- Odd parity bit code
- It ensures that message including parity bit must contain odd 1's.
Drawback of parity bit code
- Only single bit error can be deducted.
- Can't tell in which position the bit is manipulated.
Hamming code
- It is an error detecting and correcting code.
- It uses a number of parity bits located at certain positions.
How many parity bit can 'm' number of bit message can have?
Now we will see where to place the parity bits within the message.
Let the code is of 7 bits.
There is a rule: the parity bits can always be place at position 2n where n = 0,
1, 2, 3, ...
What will be the value of parity bits?
Example question:
Encode the binary word 1011 into seven bit even parity hamming code.
Determine the hamming code for 10111 for odd parity.
Assume that the even parity hamming code 0110011 is transmitted & that 0100011 is recevied. The receiver does not know what was transmitted, determine the error location.
