[MUSIC] In this lesson and in the following one, some prior knowledge necessarily to follow our course on digital systems will be presented. This first lesson is about binary numeration system. Computers receive, store, proces, transmit data of different types, for example, numbers, characterss, sounds, or pictures. The common point is that all those data must be encoded using zeroes and ones, and computer technology is based on electronic circuits that process this kind of information, that is to say that they process vectors of zeroes and ones, the so-called binary encoding system. Among the data processed by computers, an essential type is constituted by numbers. How can we represent numbers and perform arithmetic operations with only two digits, 0 and 1? We already know the decimal system, and we are going to define the binary and the hexadecimal systems. First, some comments about a traditional numeration system: the decimal system. Decimal system uses ten digits: 0, 1, 2 and so on up to 9, and it is a positional system. That means that a weight is associated to every digit position. So, the position of the digit within the number is relevant. An example, when we write 653, what we mean is: 6 times 10 to the power 2, plus 5 times 10 to the power 1, plus 3 times 10 to the power 0. Six hundredths, five tenths, and three units. Then, we can do the same, but with 10 replaced by 2, so that in binary there are two digits instead of 10, called binary digit or, in short, bits. It is a position system and to the positions of the bits are associated weights that are powers of 2 instead of powers of 10. Let us see an example: the binary number 1101 represents 1 times 2 to the power of 3, that is to say 8, plus 1 times 2 to the power 4, plus 0 times 2 to the power 1, plus 1 times 2 to the power 0. So that this is 8 plus 4 plus 1 equal to 13. So that this binary vector is the binary representation of decimal 13. Now, an exercise: compute the decimal representation of this binary number. The solution is this one. Here, there are six bits that correspond to weights 2 to the 5, that is to say 32. 2 the 4: 16, 2 to the 3: 8, square 2: 4. 2 and 1, and the represented number is 32 plus 8 plus 1, that is to say, 41. Now, some comments about the range of representable numbers. With n bits we can represent all natural numbers from 0 to 2 to the n minus 1. There are exactly 2 to the n combinations of 0's and 1's in an n bit vector. Here is an example with n equal to 4: There are 16 combinations of 4 bits and in this table we see all the combinations from 0000 up to 1111, that correspond to decimal numbers from 0 to 15. Let us see more examples: with 3 bits we can represent all numbers from 0 to 7. With 4 bits, all naturals from 0 to 15. With 5 bits, all naturals from 0 to 31, and with 6 bits, all natural numbers from 0 to 63. Conversely, how many bits do we need to represent some given natural number? For example, to represent 48 we must look for a value of n such that 48 is smaller than 2 to the n, but greater than or equal to 2 to the n minus 1. In this case, the solution is 6, because actually, 48 is greater than or equal to 32, but is smaller than 64. And you can check that number 48 can be represented in this form. Actually, this is 32. The weight corresponding to this bit is 32, and the weight corresponding to this one is 16. So that the represented number is 48. Sometimes, instead of base 2 system, a base 2 to the 4 that is 16 system is used, the so-called hexadecimal system. Then, there are 16 digits, from 0 to 15 but, as regards digits 10,11,12,13,14,15, letters are used instead of digits. It's a positional system. As an example, this hexadecimal number is 3 times 16 to the 3, plus 10 times (A represents 10) 16 to the square, plus 9 times 16, plus 15 (F represents 15). Then you can compute the result of this arithmetic expression, and you will check that this hexadecimal number in decimal is 15,007. As a matter of fact, the hexadecimal system is nothing else than an easier and more dense way to represent numbers in binary. The conversion from one system to the other is straightforward. An example: consider the hexadecimal number 3 A 9. This one. To convert it to binary, we just replace each hexadecimal digit by its 4-bit binary representation. For example, 9 in binary is 1001; A, that is to say 10, in binary is 1010, and 3 in binary is 0011. So that the representation of hexadecimal 3 A 9 is binary 0011 1010 1001. Conversely, to translate a binary representation to a hexadecimal representation, we partition the binary number into 4-bit vectors from right to left. In this case, first group, second one, the third one and the fourth one, and then, we replace those vectors by hexadecimal digits. For example, 0101 is equal to 5. 1010 is 10, and, in hexadecimal we write it as A. 1011 is equal to eleven. We represent eleven, and in hexadecimal, we write it as B, and finally 0100 is equal to 4. So, the conversion from binary to hexadecimal is straightforward. An exercise: compute the hexadecimal representation of this binary number, and then (second part of the exercise) compute the binary representation of this hexadecimal number. This is the solution: to represent this binary number in hexadecimal we define four bit groups: 1100 is 12, that is to say, C; 0100 is 4; 1101 is 13, that is to say D, and 0110 is 6. Now, given this hexadecimal number, we just substitute C by 1100,2 by 0010, F by 1111 and 5 by 0101, and, we get the binary representation of this hexadecimal number. The conversion of decimal to binary is not as simple as from hexadecimal to binary. The conversion algorithm consists of a sequence of divisions by 2. Let us see an example. We want to represent 18 in binary. Then, the sequence of divisions is as follows: 18 divided by 2 is equal to 9 with the remainder equal to 0; 9 divided by 2 is equal to 4 with the remainder equal to 1; 4 divided by 2 is equal to 2 with the remainder equal to 0, 2 divided by 2 is equal to 1 with remainder equal to 0, and the computation ends when the obtained quotient is equal to 1, as in this case. Then, the result of the conversion is this latest quotient and the sequence of remainders in reverse order, that is to say 0010, and, you can check that this binary vector represents 16 plus 2, that is to say 18. Exercise: write number 43 in binary. Here is the solution: 43 divided by 2 is equal to 21, and, the remainder is equal to 1. 21 divided by 2 is equal to 10, and the remainder is equal to 1. 10 divided by 2 is equal to 5, remainder equal to 0. 5 divided by 2 is equal to 2, remainder equal to 1, and finally, 2 divided by 2 is equal to 1, remainder equal to 0, and, the result of the conversion is this 1 and the set of remainders in reverse order, that is to say 01011. You can check that the weight of this bit is 1, 2, 4, 8, 16 and 32. Adding them you get 32 plus 8 (40) plus 2, plus 1. This is 43. It remains to see how sums and differences are performed in binary. Actually, it is just an adaptation of the classical decimal addition and difference adapted to the binary system. When we add up two bits, they are four possibilities: 0 plus 0 is 0: 0 plus 1 and 1 plus 0 is equal to 1; and 1 plus 1 is equal to 2 that, in binary, can be written under this form, so that the current step bit is 0 and the carry to the next step is 1. An example: if we must compute A plus B, then 1 plus 1 is 2 so that the bit of this step is 0 and there is a carry equal to 1; 1 plus 1 equal to 0, carry 1; 1 plus 1 plus 1 is equal to 3, that is to say the bit of this step is 1, and there is a carry 1; 1 plus 0 plus 0, 1, carry equal to 0; 0 plus 1, 1, carry 0; 1 plus 0, 1, carry 0; 0 plus 1, 1, carry equal to 0, and 1 plus 0 equal to 1, and this is the result. When computing the difference between two bits, there are also 4 possibilities: 0 minus 0 is 0, 1 minus 0 is 1, 1 minus 1 is 0, and 0 minus 1 is equal to -1 that can be written as minus 2 plus 1. So, the current step bit is equal to 1, but there is a borrow from the next step equal to 1. An example:: if we compute a minus b, then 1 minus 1 is 0; 0 minus 1 is 1, but with a borrow equal to 1; 1 minus 1 minus 1 is -1, so I write 1 and there is a below to the next step equal to 1; 0 minus 0 minus 1, once again it's -1; 0 minus 1 minus 1 minus 1 is -2, so 0 and borrow equal to 1; 1 minus 1 is 0, there is no borrow; 0 minus 1, 1 with borrow equal to 1, and finally, 1 minus 1, 0. So, the result is this one. Now, an exercise: compute A plus B, and A minus B. Solution. First A plus B: 1 plus 1, 0, carry 1; 0 plus 1 plus 1, 1, carry 1; 1 plus 0 plus 0, 1, carry 0; 0 plus 1 plus 0, 1, carry 0; 1 plus 1, 0, carry 1; 1 plus 0 plus 0, 1, carry 0; 0 plus 1, 1, carry 0, and 0 plus 1, 1. The difference: 1 minus 1 equal to 0; 0 minus 1 1, borrow 1; 0 minus 0 minus 1, 1; 1 minus 0 minus 1 equal to 0; 1 minus 1, equal to 0; 0 minus 0 0, borrow equal to 0; 0 minus 1, 1, borrow equal to 1, and finally, 1 minus 1, 0. And this is the result. Summary: we have seen that in computers data are represented with 0's and 1's. The binary numeration system has been defined, as well as the the hexadecimal system. The range of representable numbers have been computed. Conversion methods between numeration systems have been seen, and finally addition and difference algorithms for binary numbers have been described.
