Introduction to digital systems

[Master_Ghost_Knight]

Ever wonder how computers work? Now you can know "in theory" how you can build a computer almost from the sand and other raw materials.
I am busy at the moment to invest much on this project as I would like to, but I will try my best to make it as clear subject, with some examples and exercises, although at a very slow pace.
I leave you for now a motivational video:

==========================================================

EDIT: This page is target for content only, and I intend to expand on this subject broadly. So to keep it clean and wasy to read, please posts your questions regarding this subject HERE

 

[ormaaj]

.

 

[Master_Ghost_Knight]

I'm only thinking to go as far as assembly with this, I'm already compiling lesson 1, probably out on the weekend or sooner.

 

[Master_Ghost_Knight]

#1 - Base Systems
To be able to understand the representation systems generally use in computation, it is a valuable skill to be able to understand and perform operation on numbers represented in other numerical systems, specifically in binary.
The reason why binary in particularly will be touched upon later when addressing circuitry, however it is very often useful to also be able to work in other base system such as octal and hexadecimal. Independently of the base system you are going to work on, the following theory that I am about to show you will be able to work in any of them.

To be able to identify the numbers at their respective base representations, we are going to use the following notation:

Where "n" is the representation of the number in base 10, and "k" is the representation of that same number in the base "b" (explicitly putting "k" within parenthesis with the lower index b to express that "k" is a number of base "b"). Throughout this post, any number which is not represented with a index is assumed to be in base 10 (decimal).
To start let's take a look to our very familiar base 10 system.
Take as a example the number "

", in the representation we call the Arabic numerals (which is an excellent method of representing numbers as we are about to see), the number is generally read with the left most "digit" (digit here being an abusive language, meaning a individual character used to represent) being the most valuable one (most significant) and as we proceed to the right the digits getting increasingly less significant until we get to the right most digit which is the less significant of all.
The way this base 10 system works is by having a table of 10 basic characters, that ranges from 0 to 9 (10-1) to which we attribute the generic mathematical values (that we are already familiar with):

(looks obvious but necessary), where the previous number is the increment of the previous.
Once the "9", the representation of "9+1" is done by resetting the count of the current digit position and incrementing the digit on the left (or add a digit to the left if there isn't one).
Ex. 9+1=10
Ex. 29+1= [2][9+1]=[2+1][0]=20
Ex. 99+1=[0][9][9+1]=[0][9+1][0]=[0+1][0][0]=100
Note that on the last example I have conveniently placed a zero on the left of the last number, this however does not change the number (and why I will explain in a bit).
Notice that for the digit to the left of the right most digit can only increment 1 in each 10 increments of the right most digit, respectively the third right most digit only increments 1 in each 10 increments of the second right most digit, which in terms corresponds to each 100 increments of the right most digit (

). Generically the (n+1)-th right most will only increment once each

increments of the right most digit.


Generic base representation
So it is not surprising that in terms of mathematical value, the number of our example

can be expressed as:

And that a number represented with "n" digits can represent up to

different numbers (ranging from 0 to

-1, note: 0 counts as a number that can be represented).
(Note:

), And now it is also easy to see that adding zeros to the left of the most significant digit does not change the value of the number:
Ex. 99=099=0099=00099, simply

The same way for a base 2 we have 2 characters (0 and 1) that range from 0 to 2-1 (=1).
And for the same reason:

And a number with n digits is able to represent

different numbers (ranging from 0 to

-1)

Now given this basic introduction, we can easily see how to generalize the same formalization for any base system

, There are b number of character that represent numbers from 0 to b-1 for which a generic representation:

has the mathematical value of:

And "n" digits can represent up to

different numbers (ranging from 0 to

-1).

Question: Why we can't use base 1?

Base system >10:
Now what? How are we going to represent 10 in base 16? Since we ran out of character trivially associated to numerals, it is a common practice to start using letters of the alphabet instead, so:
A=10
B=11
C=12
D=13
E=14
F=15

Note:

,

Converting from base b to base 10
How do we convert a generic number represented in base b and convert it to base 10? The process is extremely easy and I have already explained it without perhaps you even noticing it. Because given a generic number written in base b:

has the mathematical value

which all it takes is to perform this calculation in base 10.
Ex.

but we already know that

and

, so we replace A and C by their respective values:

Converting from base 10 to base b
Now what we would like to do is be able to convert any number represented in base 10 into a generic base "b".
This process is a bit trickier and requires a greater attention to this mathematical gimmick.
Notice again that:

Even if I don't know what digits go on the left, the mathematical value of the number on the left must be equal mathematical to the value of the number on the right since they are both a representation of the same number.
Now look to what happens when I divide both sides by "b":

Since all individual "

" represent positive integers smaller than "b", then all the terms highlighted in green are all positive integers except for the term highlighted in red which is necessarily a number smaller than one (because b >

) and therefore d_0 must be the remainder of the whole division of the number "k" (represented in base 10) by "b" and that the number highlighted in green are the result of the whole division.
But now notice that the result of the whole division has right shifted ("i.e. the n-th digit to the left of the unit digit is now the (n-1)-the digit to the left of the unit digit"), putting the "

" on the unit position as where there previously was "

". So by the same process, the "

" is the remainder of the whole division by "b" of the result of the whole division of "k" by "b".
You can then continue the process until all digits are obtained.
Here is an example, try to convert the number 976 into base 16 (hexadecimal):
To give you a better idea of how the process works, I have already converted the number to hexadecimal, and I will show you as well every step of the process but in hexadecimal operations:

Also as an example 976 to base 2:

Q: Convert 546 to base 8.

If you try to use these methods to convert non-integer numbers you will see that they will boggle up and simply not work. So, on the next lesson we will be going trough how to convert non-integer numbers, tricks on how to quickly and directly convert between special base system, and how we perform operations on those base systems.

 

[Master_Ghost_Knight]

#2-HOW TO CONVER FRACTIONAL NUMBERS:
Before starting this section, I need to bring to attention to how we represent decimal numbers, which unfortunately it is not equal for everyone. To this day there isn't any worldwide convention that standardizes what symbol should be used to represent the separation of the integer part of the number from the fractional part. In the US it is widely used the dot (".") to separate the fractional side of the number while comma (",") is used to group 3 digits together (to help read large numbers). However in various countries in Europe (Including Portugal, where I come from) it is the other way around, comma (",") is used to separate the fractional part while the dot (".") is used to help read the number.
Here is the important part: I WILL BE USING COMMA (",") AS A FRACTIONAL SEPERATOR in this tutorial.

Fractional numbers conversion:
Lets first look a prototype of a number written in base "b" with a fractional component.
We should have something like:

and again has before, you will need "b" increments of

in order to get 1 increment of d0, and so on as we have seen before, this in turn will make it easy to see that it has the numeric value of:

So again to convert this number from base "b" to base 10 all you have to do is to perform the calculation in base 10 exactly as before.
Now to convert a number from base 10 to base "b", you will notice that the method explained in the previous lesson no longer works, because as you perform the first integer division you will notice that the remainder will not be the unit digit, but the unit digit plus everything in the fractional part:

Our problem is that the fractional part is already not an integer; further dividing will not solve the problem. So how to get around the problem? Generally the solution is to get rid of what is causing the problem altogether. So what we will do is to split the number into the sum of the integer part with the fractional part like this:

And we can always do this with any number with a factional part. The numerical result of the addition must be the same either preformed in base 10 or base "b", because base conversions do not change the intrinsic value of the number. Now because the fractional part is smaller than 1 in base 10, it must also be smaller than 1 in base "b" and therefore also fractional (without integer part). It is important to note with this that the fractional part will not mix with the integer part when converting between bases. So we can go forth and convert the integer part of the number into base b (which you should already know that by now) and then we will simply add fractional part in the end of the number.
Now how do we convert a number with only fractional part?
Let's look at its representation in base "b":

Now if we multiply the number by "b" we get:

Notice that now the digit

has now skipped into the integer part and everything to the right has left shifted (but remains fractional), which we can easily split from the rest of the number (remember that in base "b" the operation multiply by "b" followed by right shift returns the number to its original aspect, so does divide by "b" followed by left shift). So now all we have to do is to remove

and repeat the process until we get all the digits (and do not forget to right shift the final number for every time you make a multiplication by "b").
So let's see an example. Convert the number represented in base 10 to base 2.
12,375
1. Split the number integer and fractional part:
12,375=12+0,375
Convert the integer part:

Convert the fractional part:

Join the 2 parts together:

So far so good. Now try to convert the number 0,2 into base 2.

Ops!!! You got a recurring number. It does happen that some numbers with a finite representation in base "p" when converted to a base "b" can have a recurring representation. These occurrences are related to prime numbers, in this particular case it is because 0.2=1/5, because 10 can be made through the multiplication of 2 and 5, so a multiplication of 1/5 by 10 followed with a right shift results in:

And as we see because the prime number "5" is a factor of base 10 we are able to cancel the factor "5" of the dividing number. If the number had been 1/3 or any other combination putting a prime other than 2 or 5 in the denominator (while the fraction is in its simplest form) will result in a recurring number (ex 1/14; 14=2x7; 1/13; 4/11 and so forth; 3/6 does not count because it there is a factor 3 both on top and on the bottom and they cancel each other out and therefore not in its simplest form).
For a number to have a finite representation there must also be a finite number of left shifts necessary to transform the number into an integer number.
Let's assume that I was lying, and there was a number "k" which puts a prime number "p" in the denominator of a fraction in its simplest form and it is not a factor of base b and its representation is finite. Now for it to have a finite representation there must be a finite number "n" of left shifts that makes the number an integer.
So that number "k" can be expressed as such:

were "a" is a co-prime of "c" and "p", and "a" and "c" are positive integer.
And therefore there must be an "n" where:

and "l" is a positive integer. Now I can re-arrange the equation like this:

Now given that "p" is a prime factor not shared by "a" or "b", it means that this number would have to violate the unique decomposition theorem, and therefore by reductio ad absurdum false.

So now the problem arises, even though I don't know how to build a computer at this stage, it cannot represent numbers ad infinitum, so what do we do then?
Well generally it means making an error by approximation, but there are several things you can do and the solutions vary from machine to machine, some solutions produce quicker but less precise results, others more sophisticated produce better or exact results (sometimes) but are generally slower. I will develop into this later when discussing finite representation.

INSTANTANEOUS BASE CONVERSIONS:
When you want to convert between bases where one base is a power of the other, there is a method that allows you to directly convert between those 2 bases without having to convert the number into base 10 first as middle step.
Take for instance a conversion from base 2 to base 16 (or vice versa) notice that 16=2^4 and this mean that to represent the same number in base 2 you need about 4 times the number of digits required to represent that same number in base 16. And you can get a 1 to 1 match by grouping 4 digits in base 2, to 1 digit in base 16 (or 3 binary digits to 1 octal).
So to convert between this bases is simple, all you have to do is to remember that each hexadecimal digit will produce 4 binary digits, or that 4 binary digits will produce 1 hexadecimal digit. Example:

BINARY CODED DECIMAL
The binary coded decimal or "BCD" for short is another numeric system, slightly different from what we have seen so far. It has arisen from the fact that everyone else works in base 10, and it tries to benefit from the 1 to 1 quick conversion mechanism as the previous case we just seen (why would we want that, you will only understand later).
So what this is, is a binary codification that groups 4 binary digits and we say that it represents 1 decimal digit. So when we increment a number in this codification, whenever each group of 4 binary digits represents 10 that group will reset to zero incrementing 1 unit to the next group of 4 binary digits. We will be using this codification later along with the previous method further down the line. But for now be quite contempt to know that they exist and how they work.

NEXT
Until now to do operation (addition, subtraction, multiplication, division) with numbers in other bases other than 10 we will have to convert the numbers into base 10 first, do the operation in base 10 and then convert it back into whatever base you were working with. But computers will not have that benefit so we will have to do one better, on the next lesson we will see how to perform operations directly in any base system without having to convert it into base 10, and how do we represent negative numbers when a computer only has 1's and 0's and some quick tricks exploiting the fact that there is a finite numbers of bits to represent numbers. Hopefully after that we can move on to the electronics.

 

[Master_Ghost_Knight]

RESERVED

 

[Master_Ghost_Knight]

UPDATED AND RESERVED!