Dies ist eine alte Version des Dokuments!

2. Number System

2.1 Number System

In the previous chapter we had a look onto the way a processor (and a computer) can deal with the digital values '0' and '1'. However, we haven't seen how the processor can handle larger numbers. In order to approach this, first a short historical outline is shown.

2.1.1 Addition Systems

The first used number system were addition systems. These are also still in use: when enjoying a German beer in the beer garden the waiter is counting the 'progress' by dropping dashes onto the coaster (see Abbildung 1)

In ancient Rome these systems were deeper elaborated. There were different symbols which represent numbers of various sizes:

• $I = 1$
• $V = 5$
• $X = 10$
• $L = 50$
• $C = 100$
• $D = 500$
• $M = 1000$

Besides this represenation for quantities also the position of the symbol in the numeral were important:

• In general: the letters have to be arranged decreasing from left to right. For example $MDCI = 1601$
• There are deviations of this rule: When up to three of the a lower symbol is written to the left, these have to be subtracted. Sounds complicated?
  A kind of…. for example $\color{blue}{M}\color{green}{CCD}\color{red}{L}IV = \color{blue}{1}\color{green}{3}\color{red}{5}4$.
  Luckily, we do not have to learn this, but by this trick the length of the numeral could de shortened,

It becomes even more complicated, when trying to calculate with the numbers: what is the result of the multiplication $CCMXXXVII \cdot DDDIIX$$?

2.1.2 Decimal and Binary

Luckily, we have nowadays a better system for writing numbers: the positional system.

We 'just know' what a number like $23$ means. However, for understanding how the computer works we have to investigate this gut feeling and put some technical terms onto it.

1. We are accustomed to count with our fingers from $1$ to $10$. For this we have 10 symbols to count: $0,1,2,3,4,5,6,7,8,9$. These group of distinguishable symbols are called digits.
2. The amount of the digits is called base $B$. We are used to the decimal base $B=10$, in logic we used binary (also called dual) $B=2$.
3. When we count beyond the maximum number we are used to 'enlarge the number to the left': after the $9$, we count $10$. But the digit $1$ in $10$ is more worth than the $1$ in $31$ (of course). It is on a different position, on the position of the tens.
4. Each position gets numbered: the ones count 0, the tens 1, the hundreds 2, the thousands 3 and so on. This 'position number' is called index $i$.
5. Knowing the index, also the 'worth of the position' can be derived: the place factor $p$ (like one, ten, hundred) can be calculated with the base and the index: $p=B^i$.
6. A numeral as a group of digits represents what is commonly known as a number.
7. A code or encoding means a way to translate one way to display information into another. E.g. A decimal numeral into a Binary, or an idea of an algorithm into a computer language.

In order to recapitulate this for $B=10$ we will calculate the amount of a dezimal numeral here once in detail (click on the arrow to the right „>“ to see the next step, alternatively see here):

Ok, that was simple. But what about a binary number? Let's calculate the amount of a binary numeral:

So, what did we find out?

• The shown process is a relatively simple way to convert binary numerals to decimal.
• A 8 digit binary numeral is equal an up to 3 digit decimal numeral. --> Numerals in binary become lengthy

Therefore, a it would be better to have a more structured way in presenting the numerals in the which are used in the processor. Internally, the processor just knows 0's and 1's. But investigating a huge bunch of these (e.g. when analyzing the internal memory or a file) is not really catchy in order to understand anything.

The first step is to group the bits:

• 4 bits are called a nibble (the name derives from 'to bit' and 'to nibble')
• 8 bits are called a byte
• 16 bits are (usually) called a word. In details, this depends on the processor.
• 32 bits are (usually) called a double word. Like the word this also depends on the processor.

By this, one can separate parts of information (e.g. in a file) better. It is also important to mark the order of the bits. For decimal numerals like $42$ the rightmost digit has always the lowest value. The technical term for the 'lowest value' in a binary numeral is called lowest significant bit or *LSB*. When the LSB is on position 0 (= rightmost) this order is called LSB 0. This was used in the calculation above and is commonly used. Is some cases (some memonry setup and communication protocols) the order is just the other way around. In this cas the most significant bit is on position 0. This order is therefore called MSB 0. Example: $3_{10} = 0000\;0011_{2}\text{ (LSB 0)}$, $3_{10} = 1100\;0000_{2}\text{ (MSB 0)}$

What is still missing are expressions for large amounts of data. We can describe these using prefixes and the powers of two. You may already know the prefixes such as kilo and mega, but it is worth brushing up on the powers of two. The easiest way to illustrate this is with a chessboard. Maybe you know the legend of the inventor of the chessboard, who was granted a wish by the king. His wish was that the king would give him one grain of rice on the first chessboard square and every time twice as much on each subsequent squares. We'll play through this briefly, here to write down the powers of two:

• in the first square we enter two to the power of 0, which results in 1.
• In the second square, two to the power of 1, resulting in two.
• Then 4, 8, 16, 32, 64, 128, 256, 512 and then in the next line two to the power of ten, resulting in 1024.

You should definitely remember these sequence of the values for the power of 2! They are not only important for the exam, but also for the following semesters and computer science.

1024 bit is also called kbit or kilobit in the semiconductor industry. You will notice here that the kilo is slightly more than 1000. To make it easier to distinguish, according to the ISO or ECE standard you should say kibi instead of „kilo“ and write kibibit. The same applies to 2^20, i.e. 1024 to the power of two: megabit has become common there. However, mebibit, should be used to differentiate. The nomenclature continues in the same way for 2^30 and 2^40: gibibit and tebibit.

2.1.3 Other bases

When looking onto multiple bases, it is important to clearly mark the base of the numberals. Already in the chapter before a numeral like $110$ could either be $110$ in decimal or $110$ in binary, which is $6$ in decimal.
In the following the base will be written as a subscript: $110_2 = 6_{10}$. In the end of this subchapter we will also see other ways to mark the base.

Hexadecimal

With the ideas of the prevoius subchapter we already can structure the bits. In order not to use the lengthy binary presentation it is common to use other bases. One important base is $16$ for hexadecimal numerals. There, we need 16 distinguishable symbols: $0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$. With this digits it is possible to encode (=rewrite by other means) exactly 4 bit or one nibble. The encoding will be as follows:

This directly reduces the necessary amount of digits to show data. The hexadecimal representation is for example used in the file type *.hex. This is the output file of an embedded c compiler and contains code in an machine-readable representation. An example of a c code and its hex-file is shown in Abbildung 3. In the hex-file the bytes (= 2 nibbles = 2 digits) are visibly grouped.

The bytes in the first line are:

But what the decimal value of this numerals?
This transfer is also possible the process shown in 2.1.1:

$ Z_{10}=\sum_{i=-n}^m z_i \cdot B^i$, where $z_i$ is the digit on position i.

As an example the Byte4 shall be written in decimal:

$ Z_{10}(Byte4)= Z_{10}(19_{16}) \\ =\sum_{i=0}^1 z_i \cdot 16^i = \\ 1 \cdot 16^1 + 9 \cdot 16^0 = 16 + 9 = 25_{10}$

Octal

Another - much less common - base is 8. This number system is called octal. In this case only $0,1,2,3,4,5,6,7$ can be used for digits.

Similar to the number systems before, the following formula applies for the transfer in decimal: $ Z_{8}(X)= \sum_{i=-n}^m z_i \cdot 8^i

2.1.4 From decimal to other bases

Up to this point chapter, we only have converted other $B$-based numerals to decimal.
Now we want to try to convert a decimal into hexadecimal, for example the numeral $315_{10}$. One way is to first convert to binary by „try and subtract“ and then convert the nibbles into hexadecimal:

For this example, we first try to subtract the highest power of 2, which not results in a negative number. \begin{align*} 315_{10} &- 256_{10} &= 59_{10} \quad \quad 2^8\quad \\ 59_{10} &-32_{10} &= 27_{10} \quad \quad 2^5\quad \\ 27_{10} &-16_{10} &= 11_{10} \quad \quad 2^4\quad \\ 11_{10} &-8_{10} &= 3_{10} \quad \quad 2^3\quad \\ 3_{10} &-2_{10} &= 1_{10} \quad \quad 2^1\quad \\ 1_{10} &-1_{10} &= 0_{10} \quad \quad 2^0\quad \\ \end{align*}

The number $307_{10}$ is similar to $2^8 + 2^5 + 2^4 + 2^3 + 2^1 + 2^0$. This is equal to $100111011_2$ or $0001\;0011\;1011_2$. For the hexadecimal value these nibbles have to be converted, which leads to $13B_{16}$. This is often the fastest way, but is based on the constraint, that one remember the power of 2.

But how can we convert a decimal numeral like $452.12_{10}$ e.g. to hexadecimal?
The easiest way is to at first separate the value in integer decimal $z$ and decimal places $f$:

$452.12 \rightarrow z = 452 , f = 0.12$

Results:

1. A decimal numeral has to be separated into integer decimal and decimal places.
2. By dividing / multiplying with the base the integer decimal / decimal places can be converted to another base. This works for all other bases like $2$ or $8$.
3. The results have to be converted (as least for base $B > 10$, like hexadecimal).
4. A small decimal places can lead to a longer (or even infinite) numerals in another base.

Especially the last result has a mayor impact for calulations on microcontrollers and computer:
The internal logic is only based on binary, which also show this problem. However, the internal memory for a numeral is limited.

Even when stored in 32bit - it is not possible to exactly convert the $0.12_{10}$ to binary. In the following table the $n$-bit equivalent of $0.12_{10}$ in binary and hexadecimal system is shown. Additionaly, this value is also re-converted to a decimal numeral.

This might seem as a little issue. But there are a lot of areas, where exact decimal places are mandatory, like banking, or simulations.

2.1.5 Binary Coded Decimals

The first approach to this was the development of Binary Coded Decimals.

The encoding algorithm from a decimal numeral into BCD is simple: „don't use the division/multiplication method mendioned before - just take the same hexadecimal digit on each decimal position like the decimal one“.

This means the decimal numeral $391.21_{10}$ is encoded to $391.21_{BCD}$. Inside the processor each digit is handled as hexadecimal number: $3\;9\;1\;.\;2\;1_{BCD}$ equals $0011\;1001\;0001\;.\;0010\;0001_{2}$.

The main disadvantage is the ineffective storage management and more complex algorithms for addition, subtraction an so on.

2.1.6 Marking the base of a numeral

Up to here, the marking was done by the subscript. Poxtfixes cannot be used in the software development environment, and sometimes are also not used in datasheets. Alternative ways for the marking are the following:

Be aware, that in the code 01027 is not equal to 1027!

When to use which base?

When programming code for an embedded system, the system will always see 0's and 1's after compiling. So, the microprocessor does not have to be considered.
In some cases on the other hand, the binary or hexadecimal numeral is much more convenient to read:

Here an example, where the binary numeral shows a smiley (e.g. for writing this on the screen), but the hexadecimal (or decimal) value does not give a clue what the output will be:

int disp1[8] = {
    0b00000000,
    0b01000100,
    0b01000100,
    0b00000000,
    0b10000001,
    0b01000010,
    0b00111100,
    0b00000000
};
int disp1[4] = {
    0x00, 0x44, 0x44, 0x00, 
    0x81, 0x42, 0x3C, 0x00
};

2.2 basic arithmetic operations in binary and hexadecimal

In this subchapter we will have a look onto the way how the arithmetic operations have to be executed manually in other bases. For math it does not matter in which number system one calculates: a calculation like $2_{10} + 5_{10} = 7_{10}$, will be in binary $0010_2 + 0101_2 = 0111_2$. The values behind the numerals are still the same, they are only encoded differently.

The execution is similar to the well known experience of calculating in the decimal system.

Important for all of the operations: Never forget the carry!
Just a small reminder in decimal:

\begin{align*} \color{white}{+}192 \\ +378 \\ +672 \\ \hline 1\overset{\color{red}{2}}{1}\overset{\color{red}{1}}{4}\overset{}{2} \end{align*}

The red numbers are the carry over of the calculation to the right. If a calculation exceeds the limits of the base, a new digit is added and the carry is taken into account in it. Similar carry will happen in the next subchapters.

2.2.1 Addition

In Binary

In the following some examples shall show the concept for binary:

\begin{align*} \begin{array}{lll} { a) \\ \color{white}{+}0_2 \\ +0_2\\ \,\overline{\color{white}{+}\overset{}{0_2}} }&{ b) \\ \color{white}{+}0_2 \\ +1_2\\ \,\overline{\color{white}{+}\overset{}{1_2}} }&{ c) \\ \color{white}{+}1_2 \\ +0_2\\ \,\overline{\color{white}{+}\overset{}{1_2}} }&{ d) \\ \color{white}{+}1_2 \\ +1_2\\ \;\;\overline{\overset{\color{red}{1}}{1}\overset{}{0_2}} } \end{array} \end{align*}

The four simplest examples show the carry only for $d) \quad 1_2 + 1_2$. Now we can also connect the number system with the logic gates! The addends are called $A$ and $B$ (e.g. $A=1_2$, $B=1_2$), the sum is the numeral $CS_2$ (e.g. $C=1$, $S=0 \rightarrow CS_2=10_2$).
When analysing the calculations above, we need one logic gate for $S$, which only results $1$, when either $A=1$ or $B=1$: this is the XOR gate.
For the carry $C$ we only get $1$, when both of the inputs are one: Here a AND gate have to be used.

THe Abbildung 4 show the resulting logic. This is also called a half adder.

The next step shall be a bit more complicated - or better: some bit more complicated. We want to do the calculation $A + B = 0011_2 + 0111_2$.

\begin{align*} \color{white}{+}\,00\boldsymbol{1}1_2 \\ +01\boldsymbol{1}1_2\\ \,\overline{\color{white}{+}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{0}\overset{\color{red}{\boldsymbol{1}}}{\boldsymbol{1}}\overset{}{0_2}} \end{align*}

The rightmost, first step is easy, sind we already had this in the examples before. The next step (marked in bold) is differing: not only do we have to consider the digits from $A$ and $B$, but also the carry from the calculation before. The carry from before has to be added for all the next steps similarly.

For the calculation by hand, we did four individual additions from right to the left. The processor has to do the same. But first we have to expand the half adder. For a complete addition step we need a logic with the inputs $A$, $B$ and and carry from the step before $Cin$. The output will be still $S$ and $C$.

In Abbildung 5 the full adder is shown. It is an alternative representation from what we have done for calculation by hand:

1. first add one bit from $A$ to one bit from $B$ (half adder). The result is in $S'$ and $C'$.
2. Then, take the result $S'$ and add it with $Cin$ (second half adder). The result is in $S$ and $C''$. $C$ is already the wanted output.
3. For the carry output we need to consider both carries $C'$ and $C''$. When two or all of the inputs $A$, $B$, $Cin$ are high, then the carry has to be set to high. This can be implemented with $C'$ OR $C''$.

This full adder can now be stacked together in order to add multiple bits $A0, A1, ...$ to $B0, B1; ...$.

In Hexadecimal

The calculation in hexadecimal is conceptually the same. Some examples, which we will discuss below:

\begin{align*} \begin{array}{lll} { a) \\ \color{white}{+}5_{16} \\ +3_{16}\\ \,\overline{\color{white}{+}\overset{}{8_{16}}} }&{ b) \\ \color{white}{+}7_{16} \\ +3_{16}\\ \,\overline{\color{white}{+}\overset{}{A_{16}}} }&{ c) \\ \color{white}{+}\,1_{16} \\ +D_{16}\\ \,\overline{\color{white}{+}\overset{}{E_{16}}} }&{ d) \\ \color{white}{+}E_{16} \\ +A_{16}\\ \;\;\overline{\overset{\color{red}{1}}{1}\overset{}{8_{16}}} } \end{array} \end{align*}

a) This one is simple: looks like a decimal formula..
b) Here, the summands look like decimal numerals, but the result $7_{10} + 3_{10} = 10_{10}$ is still within the range ob the base. The correct symbol would be $10_{10} = A_{16}$
c) Now, the summands are a 'bit more hexadecimal'ly. The easiest way is: „convert the single digit from hex to decimal, do the operation, re-convert to hex“. For the given example: $1_{10} + 13_{10} = 14_{10} = D_{16}$
d) Also for this calculation the described way is beneficial: $E_{16} + A_{16} = 14_{10} + 10_{10} = 24_{10}$. The result is larger than the base, and therefore the value has to be separated in more digits: $24_{10} = 16_{10} + 8_{10} = 10_{16} + 8_{16} = 18_{10}$

For a hexadecimal value with more digits the carry of the calculation before has to be added - otherwise every step remains the same.

2.2.2 Subtraction

In Binary

In the following some examples shall show the concept for binary:

\begin{align*} \begin{array}{lll} { a) \\ \color{white}{-}0_2 \\ -0_2\\ \,\overline{\color{white}{-}\overset{}{0_2}} }&{ b) \\ \color{white}{-}1_2 \\ -1_2\\ \,\overline{\color{white}{-}\overset{}{0_2}} }&{ c) \\ \color{white}{-}1_2 \\ -0_2\\ \,\overline{\color{white}{-}\overset{}{1_2}} }&{ d) \\ \color{white}{-}0_2 \\ -1_2\\ \;\;\overline{\overset{\color{red}{1}}{\color{white}{0}}\overset{}{1_2}} } \end{array} \end{align*}

The calculation for $d)$ shows the carry, which here has to borrow a bit from the next upper digit. This is similar to the calculation: \begin{align*} \color{white}{-}42_{10} \\ -23_{10}\\ \;\;\overline{\overset{\color{red}{1}}{1}\overset{}{9_{10}}} \end{align*}

With more digits the calculation in the binary system will look like the following:

\begin{align*} \color{white}{-}\,10\boldsymbol{1}0_2 \\ -01\boldsymbol{1}1_2\\ \,\overline{\color{white}{+}\overset{\color{red}{1}}{0}\overset{\color{red}{1}}{0}\overset{\color{red}{\boldsymbol{1}}}{\boldsymbol{1}}\overset{}{1_2}} \end{align*}

In this example the bold column will be explained shortly:

\begin{align*} \color{white}{-}\,\boldsymbol{1}_2 \\ -\boldsymbol{1}_2\\ \overline{ \overset{\color{red}{1}} {\color{white}{0}} \overset{\color{red}{\boldsymbol{1}}} {\boldsymbol{1}}_2 } \end{align*}

The calculation has to be executed as follows: $\boldsymbol{1}_2 - (\boldsymbol{1}_2 + \color{red}{\small{\boldsymbol{1}}} ) = {\boldsymbol{1}}_2 $. Additionally, another carry has to be taken from the next digit.

In Hexadecimal

The calculation in hexadecimal is conceptually again the same. Some examples, which we will discuss below:

\begin{align*} \begin{array}{lll} { a) \\ \color{white}{-}15_{16} \\ -\color{white}{1}3_{16}\\ \,\overline{\color{white}{-}\overset{}{12_{16}}} }&{ b) \\ \color{white}{-}23_{16} \\ -\color{white}{B}6_{16}\\ \overline{\color{white}{-}\overset{\color{red}{1}}{1}D_{16}} }&{ c) \\ \color{white}{-}3F_{16} \\ -1A_{16}\\ \color{white}{-}\overline{\color{white}{B}\overset{}{25_{16}}} }&{ d) \\ \color{white}{+}\,38_{16} \\ +1A_{16}\\ \color{white}{+}\overline{\overset{\color{red}{1}}{1}\overset{}{B_{16}}} } \end{array} \end{align*}

a) This one is (again) simple: looks (again) like a decimal formula..
b) Here, the both hexadecimal numerals look like decimal numerals, but the result $3_{10} - 6_{10} = 7_{10} + C$ lead to an underflow, where we have to take a carry of $C=-10_{10}$ for a decimal calculation. In hexadecimal the carry differs. A better way to solve such a subtraction in hexadecimal is to add the carry before: $3_{16} - 6_{16} + \color{red}{10_{16}}$. Then the calculation can be converted to decimal: $3_{10} - 6_{10} + \color{red}{16_{10}} = 19_{10} - 6_{10} = 13_{10}$. This result has to be converted back to hexadecimal: $13_{10} = D_{16}$. For the next column the carry has to be considered.
c) For this formula the idea from b) helps, too: for each digit by digit subtraction, we will have a look, whether a transformation to decimal is beneficial. For the rightmost it is: $F_{16}- A_{16} = 15_{10} - 10_{10} = 5_{10}$. The rightmost result is now: $5_{10} = 5_{16}$
d) We can do the same thing here, for $8_{16}-A_{16}$: consider the carry, convert to decimal, calulate, re-convert to hexadecimal. $8_{10}-10_{10}+ \color{red}{16_{10}} = 24_{10}-10_{10}= 14_{10}$. The result is $E_{16}$.

2.2.3 Multiplication and Division

The multiplication table for binary is simple:

\begin{align*} 0_2\cdot 0_2 = 0_2 \\ 0_2\cdot 1_2 = 0_2 \\ 1_2\cdot 0_2 = 0_2 \\ 1_2\cdot 1_2 = 1_2 \end{align*}

Multiplication of longer binary numerals have to be executed similar to decimal numerals:

\begin{align*} \begin{array}{lll} 1011_2 \cdot 1101_2 \\ \hline \color{white}{+0_0}1011 \\ +\color{white}{00_0}1011 \\ +\color{white}{0000_0}1011 \\ \hline \color{white}{+}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{1}\overset{\color{red}{1}}{1} \end{array} \end{align*}

further links

• Conversion tool from decimal to hexadecimal, this tool shows also the steps and can be used vice versa