Representation of Data: Bits & Bytes

Film: 

To complete the exercises you should copy and paste them into Word and either fill out the document with a keyboard or print it and fill it out by hand (the second method is probably the best).

Pure Binary Representation of Denary Integers

Describe the representation of unsigned denary integers in binary.

Perform conversion from denary to binary and vice-versa.

Base 10 (Denary)

In the denary or decimal number system (sometimes called the Hindu-Arabic number system) numbers are formed from powers of 10. Working from the right we have units, tens, hundreds, thousands, etc., or 10^0, 10^1, 10^2, 10^3, etc.

10^0=1, 10^1=10, 10^2=100, 10^3=1,000, etc.  (Note that the ^ or caret symbol is used for 'power of'.)

In base 10 we multiply each column by the actual number there, so for example:

2,345 = 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 10^0

= 2,000 + 300 + 40 + 5 = 2,345

Base 2 (Binary)

In binary we proceed in the same way but we use powers of 2. In binary (base 2) there are just 2 symbols, 0 and 1. This is useful in computing because transistors have 2 states, off and on, so there is a neat correspondence of 0=off and 1=on. A great deal can be done with just these two digits and they have formed the basis of electronic digital computing.

Thus the right hand column of a whole number is 2^0, that is zero or 1 (2^0=1, in fact, by convention, any number ^ 0 = 1, 3^0=1, 4^0=1, etc.) Its possible values are 1 or 0 so it can be 0 * 2^0 = 0, or 1 * 2^0 = 1.

The second column from the right is 2^1 = 2. Its possible values are 1 or 0 so it can be:

0 * 2^1 = 0 or 1 * 2^1 = 2.

Thus the numerical 'weight' of binary digits ('bits'):

The largest number in n bits is 2^n-1 e.g. in 8 bits 2^8-1 = 256 -1 = 255. Largest bit value is 2^(n-1) e.g. in 8 bits = 2^7 = 128.

Translate denary to binary: divide successively by 2, placing remainder (0 or 1) in result, adding to left side. 

For example, 71:

71/2=35 remainder 1 (binary=1); 
35/2=17 remainder 1 (binary=11); 
17/2=8 remainder 1(binary = 111); 
8/2=4 remainder 0 (binary = 0111); 
4/2=2 remainder 0 (binary = 00111)
2/2=1 remainder 0 (binary = 000111);
1/2=0 remainder 1 (binary = 1000111);

1000111 = 64 + 0 + 0 + 0 + 4 + 2 + 1 = 71

Note that in a programming language like Pascal you would use the mod operator to find a remainder (e.g. 71 mod 2=1) and the div operator to find the integer quotient (e.g. 71 div 2 = 35).

Exercises 1: Binary to Denary

Convert the following to denary (base 10):

0110, 1000, 0101, 1011, 1110, 0111, 0010, 1010, 0001, 1100

00001111, 00010000, 00010001, 00011000, 00010011, 00100000, 00100011,

00111000, 00111100, 00111110, 01000000, 01100001, 10000001, 11000000.

Exercises 2: Denary to Binary

Convert the following to 8 bit binary:

12, 7, 65, 128, 96, 234, 147, 202

Addition In Binary

Binary Arithmetic: Add two binary numbers and multiply two binary numbers.

The rules for binary addition, allowing for the fact that there are just two digits, are similar to those for addition in any other base.

0+0=0
0+1=1
1+0=1
1+1=0 carry 1
1+1+ carry=1 carry 1

Exercises 3: Binary Addition

Add the following and convert the answers to denary:

0011 + 0101 

0010 + 0111

0100 + 0011 

0111 + 0010

1000 + 0111 

1100 + 1110

0110 + 1001 

1000 + 1000

00010000 + 00001111 

00010011 + 00010001

00011000 + 01000000 

10000001 + 00111000

Multiplication in Binary

The rules are:

0x0=0
0x1=0
1x1=1
0+1=1

Example: 24 x 17

We multiply the partial products. Similarly in binary:

As in base 10 we add an extra zero from line 2 onwards in the partial products. As the multiplier is 0 for 3 rows we have 3 rows of zeroes but it helps to keep track of the columns if we write them in. The answer is 256+128+16+8=408.

Exercises 4: Binary Multiplication

Multiply the following numbers in binary; show full workings.

0011 x 0100

0111 x 0010

0101 x 0011

0101 x 0100

00110000 x 00000010

10000000 x 00000100

Fractional Numbers in Binary (Fixed Point)

Integers and Numbers with a Fractional Part

Draw a distinction between integers and numbers with a fractional part in a computer context.

Describe how an unsigned denary number with a fractional part is represented in fixed-point form in binary.

Binary numbers to the right of the fractional point continue in a familiar pattern:

The four notations in each column are equivalent: one half is 0.5, which is the same as 1/2^1 and 1/2-1; these are different ways of saying the same thing.

Exercises 5: Fixed Point Binary Fractions

What are these binary fractions in denary?

0.0100  0.1010  0.1100  0.1011  0.1111  0.0111

How many fractions are there between 0.0000 and 0.1111? There are 16 combinations (2^4) of 0s and 1s in 4 bits so there are 16 possible fractions from 0.0 to 0.9375.

What is the denary value of the smallest binary fraction in 4 bits? Answer: 0.0625 or 1/16 or 1/2^4 or 2^-4.

Note that the degree of accuracy in a binary fraction is the smallest negative power of 2 - 2^-4 in this case. This is often called the precision of the binary representation. In 4 bits it is only possible to show 16 values (including zero); no other value can be represented. In 4 bits the numbers are 1/16, 1/8, 3/16... Complete this sequence up to binary 0.1111.

It may come as a surprise to learn that the common denary fraction 0.1 (1/10) cannot be represented in binary. In binary 1/10 is a recurring fraction: there is no combination of negative powers of 2 that will ever sum to exactly 0.1. This is like 1/3 in denary. If you get a computer to calculate 1-0.9 then you will get the answer 0.1 but this value has been rounded to make it convenient for human use: the underlying binary pattern is not 0.1 but something like: 0.00011001100110011... (Note how the pattern repeats indefinitely) (link)

The system of fractional values described above is known as fixed point because the fractional point stays in the same place and the values of each bit are fixed. This is in distinction to floating point numbers, which you will learn about in the A2 part of the course.

Negative Numbers in Binary

Representation of signed integers by Two’s Complement

Describe the use of Two’s Complement to perform subtraction.

Convert a denary integer into Two’s Complement and vice versa.

Negative numbers are represented in binary by complementing a positive number. The 'one's complement' of a binary number is its inverse - flip the bits from 0 to 1 and 1 to 0. The 'two's complement' in binary is the one's complement plus 1. Two's complement is generally preferred to one's complement.

For example, -2 in 4 bits is:

0010 becomes 1101; add 1 = 1110

-2 in 8 bits is 11111110; in 16 bits it is 1111111111111110

The 1 in bit 7 is an indication that a binary number is a complement and therefore negative, though this may not always be the case as it is perfectly possible to use unsigned numbers. It is very important to know when a binary number is signed or unsigned.

For example, -1 in 4 bits is:

0001 becomes 1110; add 1 = 1111

-1 in 8 bits is 11111111; in 16 bits it is 1111111111111111 (-1 is easy to remember!)

For example, -100 in 8 bits is:

01100100 becomes 10011011; add 1 = 10011100

An alternative conversion method is to take a positive binary number such as 01010100; copy bits from the left up to and including the first 1 and then invert the rest: 10101100 (check: 10101100 inverted is 01010011; add 1 = 01010100).

Another alternative conversion method is to subtract the positive denary value from 256 and write out the binary. e.g. 55: 256-55=201, which is 11001001 (which converts to 0110110 + 1 = 00110111, which is 32+16+4+2+1 = 55. And 256-1=255, which is 11111111 (any string of 1s is -1 in two's complement binary).

Exercises 6: Negative Numbers in Binary

Convert the following to 8 bit binary:

-1, -2, -10, -32, -40, -75, -100, -128

Subtraction

Subtraction is performed by adding the negative of a number. In denary this might be: 5-2 is equivalent to 5 + -2. In binary we convert the subtrahend to negative format (two's complement) and add it to the minuend. Thus:

5=00000101; 2= 00000010; -2 = 11111110; so:

  00000101
  11111110
  00000011

Now, 00000011 = 3.

Exercises 7: Subtraction

Perform the following in 8 bit binary:

17-13, 15-11, 20-12, 12-20, 35-18, 77-55, 113-46,

Hexadecimal

The Concept of Number Bases: Denary, Binary and Hexadecimal

Describe the conversion of a denary integer to hexadecimal form and vice versa. Describe the use of hexadecimal as shorthand for binary.

Binary is rather cumbersome for humans to read and write so a shorthand has been developed called hexadecimal. Binary has 2 digits, denary has 10 digits and hexadecimal has 16 digits. The characters used in hexadecimal are: 0-9 + A, B, C, D, E, F. These represent the 4-bit patterns from 0-15:

Thus an 8-bit number can be represented by two hexadecimal digits and a 16-bit number can be represented by 4 hexadecimal digits. The link between binary and hexadecimal is more obvious than that between binary and denary. If you want to know the denary value you will still have to convert from binary or hexadecimal - the 16-times table will come in handy here!

Examples:

AB = 1010 1011 (=10 x 16 + 11 = 171 in denary)

4F = 0100 1111 (=4 x 16 + 15 = 79 in denary)

Exercises 8: Hexadecimal

Convert the following to hexadecimal:

10, 20, 30, 48, 75, 98, 120, 140, 180, 220, 240, 255

Convert the following hexadecimal values to denary:

10, 0A, 25, 37, 4C, 5D, 6A, 9F, A8, BC, DF, FF

Gray Coding

Gray coding

Describe Gray coding. Explain why and where it is used.

Wikipedia

The reflected binary code devised by Frank Gray (though others may have thought of it first, Baudot in particular) maps values in standard binary to a different set of binary patterns whose distinguishing quality is that only one of the digits changes as the numbers increase. For example 01 to 10 involves a change in both bits. In an electro-mechanical system this may result in mis-readings as there will be slight differences in the time that the devices take to change. This is significant in many devices that use digital logic where errors must be kept to a minimum, for example early computers and TVs.

For example:

One way to remember this sequence of Gray codes is to note the vertical patterns for numbers 0-7: 01100110 in the right hand column, 00111100 in the middle column and 00001111 in the left column. These pattern will repeat as the range of Gray codes is increased e.g. in 4 bits the right column will be 01100110 01100110.

Alternatively:

note that 0 and 1 are the same as in standard binary: 000 and 001

Then, as only 1 bit at a time may change, the pattern for 2 is 011

Again, changing 1 bit and using up the remaining pattern, the pattern for 3 is 010

Thus 2 and 3 are reversed, compared with standard binary.

We have used up all 2 bit combinations (00, 01, 11, 10) so we change the third bit to 1, giving 110 for 4 (3 was 010 and only one bit can change)

There are two choices for 5, 100 and 111; we will need 100 as the last in the sequence so it can change to 000 in the required way so we choose 111 for 5.

Thus the next number, 6, is 101 (as we have already used 110)

And the last number in the sequence, 7,is 100, so there is a change of just one bit to zero.

Exercises 9: Gray Code

Write out the sequence of Gray codes for numbers 0-7 in 3 bits without copying from a source, using either of the methods outlined above. Check that the numbers are correct and practise until you can do it perfectly.

Write out numbers 0-7 in Gray code in 4 bits. Now add numbers 8-15 in Gray code, folloing the rule of changing 1 bit between each pair of numbers and ensuring that 15 is just one bit-change from 0000. Check your answers from a source.

Write down the binary patterns in 3 bit Gray code for the following: 4, 3, 7, 1, 2, 6, 0, 5

Write down the binary patterns in 4 bit Gray code for the following: 9, 12, 15, 8, 11, 13, 10, 14

(Binary Coded Decimal (BCD))

Ignore: not in the AQA spec.

(Binary Coded Decimal (BCD) is a way of representing decimal or denary numbers accurately, without rounding. Denary 1 maps to 0001 in BCD, 2 to 0010, etc. Thus 123.1 is stored as 0001 0010 0011 . 0001 (Need a code for the point, there are 6 to spare in BCD, 10-15.)

Character Encoding

Information Coding Schemes Describe standard coding systems for coding character data.
• ASCII Differentiate between the character code representation of a denary digit and its pure binary representation
• Unicode digit and its pure binary representation.

Information Coding Schemes

Describe standard coding systems for coding character data.

ASCII Differentiate between the character code representation of a denary

Unicode digit and its pure binary representation.

The ASCII and Unicode values for common codes are as follows:

0 (zero) : 48

Subsequent ASCII codes are 49, 50, 51, 52, 53, 54, 55, 56, 57

A : 65

Subsequent letter codes are 66, 67, etc. Lower case 'a' is 97, others follow on in sequence.

Translate a short message into character codes and pass it to a neighbour to decode.

Your message is encoded but not encrypted. What is the difference between these two words? Can you use a simple strategy to encrypt your message? Compose a different message in code values, encrypt it with a simple method and then pass it to your neighbour to decode. How will they set about decoding it? Hints here.

Useful program here. You can use this to encrypt your emails and stop all those pesky adverts for things you happen to mention.

Cryptography is an enormous and complicated field and a significant branch of mathematics.

Checking for Errors