• When we subtract M - N then 'M' is referred to as 'Minuend' and 'subtraend' respectively.

• We take the 1's complement of N and add it to M. Then if carry is obtained we discard it and add 1 to the result. This is the final answer.

• In case no carry is generated we take the 1's complement of the result and add minus sign to it. This is the final answer.

Q. Using 1's complement get 1010100 - 1000011

Q. Using 1's complement get 1000011 - 1010100

### SIGNED BINARY NUMBERS

• Positive integers (including zero) can be represented as unsigned numbers. However, to rep­resent negative integers, we need a notation for negative values.

• It is customary to represent the sign with a bit placed in the leftmost position of the number. The convention is to make the sign bit 0 for positive and 1 for negative.

• If the binary number is signed, then the leftmost bit represents the sign and the rest of the bits represent the number.

• If the binary number is assumed to be unsigned, then the left­ most bit is the most significant bit of the number.

• Example of unsigned number:

01001 can be 9 (unsigned bit) or +9 (signed bit)

• Example of signed number:

11001 can be considered as 25 (unsigned) and -9 (signed number) representation.

• When arithmetic operations are implemented in a computer, it is more convenient to use the signed-complement system, for repre­senting negative numbers.

• In this system, a negative number is represented by its complement.

• 1's complement or 2's complement may be used but 2's complement is more common.

• Binary representation of +9:

00001001

• signed-magnitude representation of -9:

10001001

• signed- 1's-complement representation of -9:

11110110

• signed- 2's-complement representation of -9:

11110111

### Points to Remember

• In signed-magnitude representation - 9 is obtained from +9 by changing the sign bit in the leftmost position from 0 to 1.

• In signed-1's complement, - 9 is obtained by complementing all the bits of +9, including the sign bit.

• The signed-2's-complement representation of - 9 is obtained by taking the 2' s complement of the positive number, including the sign bit.

• Positive numbers in all three representations are: identical and have 0 in the leftmost position.

• The signed-2's­ complement system has only one representation for 0 which is always positive.

• Signed 1's complement and signed magnitude systems have two representations for 0 i.e. +0 and -0.

• All negative numbers have a '1' in the leftmost bit position

• In the signed- magnitude and the 1's-complement representations there are eight positive numbers and eight negative numbers including two zeros. In the 2's-complement representation there are eight positive numbers, including one zero and eight negative numbers.

• The signed-complement system is normally used in computer arithmetic.

• The addition of two numbers in the signed-magnitude system follows the rules of ordinary arithmetic.

• If the signs are the same, we add the two magnitudes and give the sum the common sign.

• If the signs are different, we subtract the smaller magnitude from the larger and give the differ­ence the sign of the larger magnitude.

• For example, (+15) + ( - 20) = -(20 - 15) = - 5 and is done by subtracting the smaller magnitude, 15 from the larger magnitude 20 and appending the sign of 20 to the result.

### Addition of two signed Binary Numbers

• Negative numbers must be initially in 2's-complement form and that if the sum ob­tained after the addition is negative, it is in 2's-complement form

• Any carry out of the sign-bit position is discarded

### Arithmetic Subtraction

• Take the 2's complement of the subtrahend (including the sign bit) and add it to the minuend ( including the sign bit ). A carry out of the sign-bit position is discarded .

• Binary numbers in the signed-complement system are added and sub­tracted by the same basic addition and subtraction rules as unsigned numbers. Therefore, com­puters need only one common hardware circuit to handle both types of arithmetic

• Note: Negative numbers must be in 2's complement form for this rule to be applicable.

Q: Solve ( - 6 ) - ( -13 )

1. In binary with eight bits, this operation is written as ( 11111010 - 11110011 )

2. The subtraction is changed to addition by taking the 2' s complement of the subtrahend (-13), giving ( + 13)

3. In binary, this is 11111010 + 00001101 = 100000111 Removing the end carry, we obtain the correct answer: 00000111 (+7)

### BINARY CODED DECIMAL

• A binary code will have some unassigned bit combinations if the number of elements in the set is not a multiple power of 2.

• For example, if 10 numbers are to be represented in binary form we will need at least 4 bits and so we can form 24 combination i.e. 16 possibilities.

• However, we have 6 possibilities remaining in such a scheme.

• Different binary codes can be obtained by arranging four bits into 10 distinct combinations. The code most commonly used for the decimal digits is the straight binary assignment listed below. This scheme is called binary-coded-decimal and is commonly referred to as BCD

• A number with k decimal digits will require 4k bits in BCD.

• Each digit in decimal is represented in BCD by a group of 4 bits of binary. A decimal number in BCD is the same as its equivalent binary number only when the number is between 0 and 9.

• Moreover, the binary combinations 1010 through 1111 are not used and have no meaning in BCD.

• Example: (185)10 = (0001 1000 0101)BCD = (10111001)2

• The BCD value has 12 bits to encode the characters of the decimal value. But the equivalent binary number needs only 8 bits. The representation of a BCD number needs more bits then its equivalent binary value . However, there is an advantage in the use of decimal numbers because computer input and output data are generated by people who use the dec­imal system.

• BCD numbers are decimal numbers and not binary numbers even though they are represented in 0/1 form.

### Rules of Addition - BCD

• Step 1: The given numbers are to be added using the rule of binary addition.

• Step 2: If the result of addition of two binary number is greater than 9, which is not valid for BCD number then we add (0110)2 to the sum obtained. This will give the correct result.

• Step 3: If the result of addition of two binary number is less than 9, do nothing. The answer is in valid BCD.

• Example 1: Produces a value less than 9 so it is correct BCD and no further calculations needed

• Example 2: Produces a sum greater than 9 and no carry and so we add (0110)2 to the result to get valid BCD. The result obtained is 10010 and isnt in binary form but BCD and should be interpreted as (0001 0010) i.e. (12)10.

• Example 3: Produces a carry and a sum greater than 9, so we add (0110)2 to the result to get valid BCD. The result obtained is 10111 and isnt in binary form but BCD and should be interpreted as (0001 0111) i.e. (17)10.

### Other Decimal Codes

• BCD (8421): The digits of BCD have the weights 8421 and so a number 0110 is interpreted as 8 * 0 + 4 * 1 + 2 * 1 + 1 * 0 = 6. This is decimal number 6.

• Code (2421): Similarly, the same number 1100 in this scheme is weighted as 2 * 1 + 4 * 1 + 2 * 0 + 1 * 0 = 6. This is decimal number 6. Note that some digits can be coded in two possible ways in the 2421 code . For instance decimal 4 can be assigned to bit combination 0100 or 1010 since both combinations add up to a total weight of 4.

• Excess - 3: This scheme is an unweighted code in which each coded combination is obtained from the corresponding binary value plus 3.

• 8 4 -2 -1: This code is an example of assigning both positive and negative weights to a decimal code. In this case, the bit combination 0110 is interpreted as decimal 2 and is calculated from 8 * 0 + 4 * 1 + (-2) * 1 + (-1) * 0 = 2.

• Excess 3 and 2421 codes are self complementing as 9's complement of a decimal number is obtained directly by chang­ing 1's to 0's and 0's to 1's.

• BCD isnt a self complementing code.

### Gray Codes

• The output data of many physical systems are quantities that are continuous. These data must be converted into digital form before they are applied to a digital system. Continuous or analog information is converted into digital form by means of an analog-to-digital converter.

• Gray code is convenient to use to represent digital data that has been converted from analog form as only one bit changes in going from a number to the next.

• Many applications of digital computers require the handling not only of numbers but also of other characters or symbols such as the letters of the alphabet. The standard binary code for the alphanumeric characters is the American Standard Code for Information Interchange (ASCII), which uses seven bits to code 128 characters.

• To detect errors in data communication and processing an eighth bit is sometimes added to the ASCII character to indicate its parity. A parity bit is an extra bit included with a message to make the total number of 1's either even or odd.

• As shown above, we insert an extra 1 to make the 1's present in the code to even number (in case of even parity) or odd number (in case of odd parity).

• At the receivers end, if the parity check is violated then it means that either 1 / 3 / 5 or odd combination of errors have occured in the characters that were transmitted.

• An even combination of errors however goes undetected and additional error detec­tion codes may he needed to take care of that possibility.

• Binary Cell: A device that possesses two stable states and is ca­pable of storing one bit (0 or 1) of information.

• Register: A register is a group of binary cells. A register with n cells can store any discrete quantity of information that contains n bits. The state of a register is an n-tuple of 1's and 0's with each bit designating the state of one cell in the register

### Boolean Gates

• Binary logic deals with variables that take on two discrete values and with operations that as­sume logical meaning.

• Logic gates are electronic circuits that operate on one or more input signals to produce an output signal.

• For example a partic­ular digital system may define logic 0 as a signal equal to 0 volts and logic 1 as a signal equal to 3 volts.

### Solved Question Papers - GATE, UGC-NET, Maharashtra-SET

Q.The representation of the value of a 16-bit unsigned integer X in a hexadecimal number system is (BCA)9. The representation of the value of X in octal number system is:

• 571244

• 736251

• 571247

• 136251

Q.Given the following binary number in 32 bit (single precision) IEEE-754 format: 00111110011011010000000000000000 The decimal value closest to this floating-point number is:

• 1.45 X 101

• 1.45 X 10-1

• 2.27 X 10-1

• 2.27 X 101

Solution:

• In 32-bit IEEE-754 format 1st bit represent sign, 2-9th bit represent exponent and 10-32 represents Mantissa (Fraction part)

• Sign = 0, so positive 2 to 9 bits are 01111100 when subtracted by 01111111 i.e., 126 decimal value gives -> 0000 0011

• Which is -3.(negative as the value is less than 126)

• As number is less than 126 it is subtracted otherwise 126 would have been subtracted from it in 32 bit representation.

• Mantissa (M) is normal , hence, 1.M can be used Which is 1.1101101 Thus, Data + 1.1101101 * 2-3 Since (±M * B(±e)

• Mantissa shift right 3 times -> +0.0011101101

• = 0.228

• = 2.28 * 10-1

• Thus, option c is correct.

Q.Consider a binary code that consists only four valid codewords as given below. 00000, 01011, 10101, 11110 Let minimum Hamming distance of code be p and maximum number of erroneous bits that can be corrected by the code be q. The value of p and q are:

• p = 3 and q = 1
• p = 3 and q = 2
• p = 4 and q = 1
• p = 4 and q = 2

Solution:

• We need to find minimum hamming distance (difference in their corresponding bit position) 00000, 01011, 10101, 11110
• For two binary strings, hamming distance is number of ones in XOR of the two strings.
• Hamming distance of first and second is 3. Hamming distance of first and fourth is 4.
• Hamming distance of second and third is 4, and second and fourth is 3.
• Hamming distance of third and fourth is 3.
• Thus a code with minimum Hamming distance d between its codewords can detect at most d-1 errors and can correct (d-1)/2 errors.
• Here d = 3. So number of errors that can be corrected is 1.

Q. (1217)8 is equivalent to (GATE-CS-2009)

• (1217)16
• (028F)16
• (2297)10
• (0B17)16

• Explanation: (1217)8 = (001 010 001 111)8 = (0010 1000 1111) = (28F)16

Q. The base (or radix) of the number system such that the following equation holds is____________.
312/20=13.1

• 3
• 4
• 5
• 6

• Explanation: Let x (≠ 0) be the base of the given equation.
• We have,
• LHS = ( 3x2 + x + 2 ) / ( 2x) = ( 3x / 2 ) + ( 1 / 2 ) + ( 1 / x )
• RHS = x + 3 + ( 1 / x )
• Now, for the equation to hold true, LHS = RHS
• ( 3x / 2 ) + ( 1 / 2 ) + ( 1 / x ) = x + 3 + ( 1 / x )
• ⇒ 3x + 1 = 2x + 6
• ⇒ x = 5
• So, the base is 5

Q.Consider the equation (123)5 = (x8)y with x and y as unknown. The number of possible solutions is _____ .

• 1
• 2
• 3
• 4

• Explanation :
• Changing (123) base 5 into base 10 = 1 * 25 + 2 * 5 + 3 * 1 = 38
• Changing x8 base y in decimal = x * y + 8
• Equating both we get xy + 8 = 38
• xy = 30
• possible combinations = (1,30),(2,15),(3,10) but we have ‘8’ present in x8 so base y > 8
• as all three are satisfying the conditions so total solutions = 3 hence ans is (C) part

Q.The addition of 4-bit, two's complement, binary numbers 1101 and 0100 results in (UPSC 2006)

• 0001 and an overflow
• 1001 and no overflow
• 0001 and no overflow
• 1001 and an overflow

-3 + 4 = 1, so no overflow

Q. A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

• 0111110100
• 0111110101
• 011111110
• 0111111111

• Solution : 8-bit delimiter pattern is 01111110.
• The output bit-string after stuffing is 01111100101.
• The additional bits are stuffed bit.
• So input bit-string must be 0111110101.

Q. The number of 1's present in the binary representation of 10 * 256 + 5 * 16 + 5 is UGNET JUNE 2011

• 5
• 6
• 7
• 8

Q.The decimal number equivalent of (4057.06)8 is

1. 2095.75
2. 2095.075
3. 2095.937
4. 2095.0937

Q.12-bit 2’s complement of –73.75 is

• 01001001.1100
• 11001001.1100
• 10110110.0100
• 10110110.1100

Q.Encoding of data bits 0011 into 7-bit even Parity Hamming Code is

• 0011110
• 0101110
• 0010110
• 0011100

Q.In octal, the twelve-bit two's complement of the hexadecimal number 2AF is:

• 6251
• 5261
• 6512
• 6521

Solution: 2AF in hex = 001010101111 . Binary two's complement of 001010101111 = 110101010001. 110101010001 in binary is 6521 in octal.

Q.let an ,an-1 , ........, a1, a0 be the binary representation of an integer 'b' then b is divisible by 3 if:

• number of 1's is divisible by 3
• number of 0's is divisible by 3
• number of 1's is divisible by 6
• difference of alternate sum, i.e. (a0 + a2 + ....) - (a1 + a2 + ....) is divisible by 3

Solution: by taking examples

Q. In octal,the twelve bit two's complement of the hexdecimal number 2AF16 is : (UPSC 2016 SET B)

1. 62518
2. 52618
3. 65128
4. 65218

• Two's complement of the hexdecimal number 2AF16 is :52618

Q. In order that a code is 't' error correcting, the minimum Hamming distance should be : (UGC NET CS 2009)

• t

• 2t -1

• 2t

• 2t+1