bclose

23 – SOME BASIC IDEAS ON COMPUTING SCIENCE

Objectives

 

 

    • Introduce other number systems as binary and hexadecimal.
    • Show the foundations on which they are based.
    • Know where does come from computer science slang
 

Bill of materials

 Coffe cup
  Patience and 20 minutes to spare.

The problem

 

In the previous chapter we introduced a circuit with a Shift Register to operate 8 digital (or more) outputs using only 3 pins of our Arduino, assembled a prototype with 8 LEDs and wrote a first program in which we iterated a number from 0 to 255, sending it to the shift register´s output.

We said that the LED would count in binary and show those values in the prototype. But so far we have not talked at all of what the binary system is or why computers are based on it. Is our old familiar decimal system not good enough for computers? Is it part of an international conspiracy to torture computer science students or to defend the shameful interests of science faculties?

According to my own experience, people who have studied digital electronics or computer science, usually have more or less clear ideas on these issues, but the rest of college students and younger people, hardly have a basic minimum understanding, even though we live in a world in which we daily handle technology and computer terms without a minimum of understanding of the basis on which they are based.

As these tutorials are intended not to assume any prior knowledge, it is time to introduce some concepts and basic ideas about digital technology.

We are well aware of the stampede that such a claim can produce between the valiant followers of these tutorials, so we will promise first we will try to make it easy and even pleasant and second, that it is worthwhile, because you can’t understand modern technology without having minimum notions of its foundations.

 

THE DECIMAL SYSTEM

 

We are so accustomed to the decimal system that the very idea that any others can be used may at first sound absurd or even malicious. And yet this is only one among an great number of possibilities.

Since we were children, we have been taught in the school to use it and in the end we have learnt it by heart, so we have even forgotten the basic rules that we apply, we just do it and that’s all.

We’ll have to remember these rules. The first is that it is called decimal system because we use ten digits from 0 to 9. No sir, we do not use the numbers from 1 to 10. Why?

Well, probably due to the fact that we have 10 fingers on each hand, and remember that hands were the first calculator, we tend to think we have to use the numbers from 1 to 10. In fact, the symbolic representation of a number is called digit, that comes from the Latin digitus, that is, finger. But, although we have assumed the number system that we were taught when we were children, it is not easy to understand the conceptual leap that means representing nothing using the symbol 0. And this is the key.

The ancient Greeks and Romans, for example, had a numbering system that didn’t worked very well, it was chaotic because it was not a positional but a symbolic system and it included neither the concept nor the notation of zero. Addition was difficult but multiplication or division was almost impossible.

It was an Indian mathematician in the 3rd century, who understood the concept of 0 and its importance as a digit, and established the first modern number system.

From there it went to the Arabs, big traders, who immediately understood the advantage of this number system for their business (for when money is involved, piasters or euros, one’s brains racks), and through the Arabs it came to the West in much later times and with the so familiar current notation. So you may have heard that in the West we use Arabic numerals.
What rules do we apply to count? You have a good command, I know, but do remember the procedure. We use only two rules:

 
  • First: we use the numbers in increasing order 0, 1, 2,3, … 9 and when we run out of digits we come back to 0 and increase by 1 the digits on the left, applying the same rule. That is, we carry one to the left.
  • Second: If there isn’t any digits on the left we understand that it is a zero and we apply the first rule to increase it.
 

Thus, the number that follows 9 will be a 0 to the right (as the following 9 is 0) and as there is nothing on the left, we consider it a 0, so we increase it becoming a 1. So, at the end, we have the desired result, that is, 10. The following numbers are easy:

11, 12,13,….. 19

The following is obtained 19 back to zero position 9 and apply the rule to 1 to 2

20, 21,22…..29
……………
90, 91,92…..99

What happens now? Well, the same. We apply the first rule to 9 on the right, 9 to 0, and increased 9 on your right, 9 to 0 and apply the rule to non-existent nonentity that becomes 0 to 1. So the next number is 100 . This is a procedure to create unlimitedly large numbers that greatly simplifies calculations.

But choosing a number system based on 10 digits is an arbitrary decision (which in fact has not been the only one in the history of humanity) and is not justified by any logical reason. It’s just a habit.

And as mathematicians are people who hate the simple things, they like to make their life difficult and upset our own, they began asking themselves questions such as… is there a limit, upper or lower, in the number of digits that can be used in a number system ? Are they equivalent? Can we convert a number from one number system to another? And there is where the gates of hell were opened (or digital paradise, depending how you look).

 

THE BINARY SYSTEM

 

The simplest numbering system that we can imagine is called binary and contains only two digits: 0 and 1. With this system you can write any number, no matter how big, and you can also count, calculate and do anything you can do using the decimal system, without exception.

How do we count using so an odd system? Well, actually, applying exactly the same rules as with the decimal system, but limited to only two digits:

Zero is followed by 1 and the number that follows 1 is 0, and then we apply the second rule to nonexistent 0 on the left
So the first numbers in binary are:

     0     -   0 
     1     -   1
    10     -   2
    11     -   3
   100     -   4
   101     -   5
   110     -   6
   111     -   7
  1000     -   8

The binary notation makes representation much longer, so what? But it has another drawback. Besides the rules for addition and multiplication would delight schoolchildren.

ADDITION RULES MULTIPLICATION RULES
0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0  And I carry one.

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

And now comes the key question, why should the binary system be used on computers instead of the familiar decimal system?
It is quite simple, just a matter and technology, because we do not know any material that provides 10 different stable states that can be used as a foundation for building decimal computers.

However, there are available materials that provide two easily distinguishable stable states, called semiconductors. Semiconductors allow us to build transistors that, by applying a control signal on the base, enable conduction between the emitter and collector (when operating in saturation) or short full (when it works cut). And this is what we recognize as logic 0 and 1.

Or what it is the same, applying a logic 1 on the base (a HIGH signal or 5V) we can obtain a logic 1 or HIGH output voltage signal. And when we apply a LOW signal at the base we will obtain a LOW signal in the output of the transistor. We build binary computers because we have a stable technology that lends itself to it.

Is the binary system superior or better than the decimal binary system in any twisted aspect of the theory? Not at all, they are completely equivalent.

If we had a technology which provided 10 stable states and allowed us to build computers based on the decimal system, would we continue using the binary system? No way, so the binary system will be relegated to history faculties only (and, of course, to math faculties).

 
  • In the very early 19th century Charles Babbage already built mechanical machines in England which make calculations based on a similar logic, but the technology available then only allowed to use mechanical systems and unfortunately the calculation speed was disgusting compared to current computing.
  • Indeed it is feasible to build computers with mechanical gears, pneumatic systems, relays and even taps, but the cost and computing speed does not worth the effort..
 

Although IBM already built computers in the 40s of the 20th century, they were expensive and problematic because they were built based on (the famous valves of Grandma’s radio) thermionic vacuum tubes. It was with the advent of the transistor in 1947 (which involved the Nobel of physics for their discoverers) which began the current technological race.

At the beginning transistors were made one at a time, but as people are not stupid, they realized they could make more transistors on a silicon wafer, interconnected, plus all the necessary components to integrate an electronic circuit on a single chip.

And here began a race to put more transistors and more components on a single chip. Build factories is expensive but what is made there is almost free, as silicon comes from sand of the beach. So the more components you integrate, the more things does the circuit and can be sold at a higher price.

In late 2014, the commercial circuit that more transistors integrated was an Intel processor with about 4,300,000,000 transistors. (Yeah, okay, more or less four thousand million transistors).
And to end this chapter we must quote the famous Moore’s Law which says that the number of transistors that we are able to integrate on a chip doubles every two years (more or less). Although it has been achieved quite faithfully in the last 50 years, it seems to be doubtful to be accomplished in the future.

 

OTHER NUMBER SYSTEMS

 

If anyone thought that once established the binary system, apart from the decimal, mathematicians would leave you alone once and for all, then he is a naive and does not know these people.

In computer science octal and hexadecimal systems are also used, and they use 8 digits (from 0 to 7) and 16 respectively.

One moment, have we said 16 digits? There are not so many digits, are there? So what, we can invent the rest!

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
 
  • When we saw the keypad in a previous chapter, do you remember that it contained all those symbols? Do you think it was coincidence?
  • Your humble Arduino supports also the hexadecimal system and we’ll find some example to illustrate it.
 

Why should we use another pair of so odd number systems? Because they are powers of 2, 234, and it is quite easy to convert a number from one to another, especially to hexadecimal. We will ignore the octal system because it is hardly used, but the hexadecimal system is quite used in fact. To understand why, we need to make a detour.

In the decimal system, we call digits to each of the symbols representing the numbers although its correct name would be decimal digit.

In the binary system we call bits to each of its symbols, that is, 0 and 1. Bit is binary digit for short, and it is one of
the magic words of computing.

For example, in the decimal system the number 4327 has four digits and in the binary system the number 11000101 has 8 digits, or 8 bits.

In the real world, in addition to the ten digits we use twenty six uppercase and lowercase letters and besides special symbols such as +, -, *, /, € ….

But using digital technology, there is simply no more available numbers. So, how can we represent all this chaos? There is only one solution: creating a character representation code, so that each symbol is represented in a table by a certain combination of bits.

This is something that we had already seen when we talked in chapter 7 about the ASCII code. What we did not say there is that in order to represent all the characters of the Latin alphabet (and made room for some surprising characters such as €), we need to use 8-bit numbers because that way we are able to encode 28 = 256 characters.

As we take these bits in groups of eight bits, we call them byte (By eight-e), for short.
So a bit is a single binary digit and the information that it can encode is either 0 or 1. It is difficult to codify an smaller information element.

 
  •  If anyone thinks that only with 1, would be less, you forget that there is no way to get rid of 0 and a single digit, all numbers would be the same, think, would have gone back to the caves, putting a stick for each bison..
  •  Si alguien piensa que solo con el 1, sería menor, se olvida de que no hay manera de librarse del 0 y con un solo dígito, todos los números serian iguales, piénsalo, habríamos vuelto a las cavernas, poniendo un palito por cada bisonte..
 

A group of 8 bits, which can carry text encoded information, is called byte. But due to modern technology the storing capacity has grown so much that we need larger units to name our HDDs, pendrives, RAM cards… so we use Greek prefixes before the word byte:

PREFIX DECIMAL VALUE BINARY VALUE
Kilo 103 One thousand 210 = 1.024
Mega 106 One Million 220 = 1.048.576
Giga 109 One thousand Millions 230
Tera 1012 European Billion 240
Peta 1015 250
Exa 1018 260
Zetta 1021 270

I bet you didn’t know the latter!

Decimal prefixes are the powers of the base 10, but to make the most of this, in the binary system we should use the powers of 2 and take advantage of the round remaining numbering, but remember that Mega binary is 1024 × 1024, although nobody remembers how much it is exactly.

Now we can understand why the hexadecimal system is so useful in computing. A character is encoded using 8 bits and an hexadecimal number represents exactly 4 bits, that’s why any 8-bit number can be translated into two hexadecimal digits. The conversion is automatic and its representation is much more shorter:

ASCII CODE Decimal Binary Hexadecimal
A 65 0100  0001 41
B 66 0100  0010 42
C 67 0100  0011 43
D 68 0100  0100 44

 

Look at the characters of the ASCII code on the first column and compare their representation in the different number systems. In the binary system we need 8 digits, one for each bit, and in the hexadecimal system we only need two. To convert a number from binary to hexadecimal we only have to take the digits in groups of four and assign them the equivalent hexadecimal value. For example, the ASCII character “D” is encoded in hexadecimal as two fours, 44.

 
  • I think we have quite abused the goodwill of our resigned readers and therefore we will avoid explaining how to convert a number from one system to another.
 

All programming languages can handle binary, decimal, octal and hexadecimal numbers and C ++ is no exception. In the coming chapters we will see it (No, it’s not a threat).

 

Summary

 

 
    • We have remembered the basis of the decimal system.
    • We have introduced the binary system:
      • It is neither better nor worse than the decimal, but different.
      • We use it because it suits perfectly to the available technology.
    • Not to get bored, we have also introduced the hexadecimal system, which is used very often in computer science.
    • We have seen where do the terms bit, byte, Kilobyte or Megabyte come from.
 

 

 

 

 

 

No Comments

Give a Reply