Number Systems

Before we delve further into designing digital systems, I think it is important to know a little more about another very basic concept - that of different number systems used in the digital world. All our design methods later on will depend on these number systems, especially one in particular - the binary system.

Let's start with the number system we are most familiar with. It is called the decimal system, since it is based on powers of ten. Why did the decimal system become so popular amongst us humans? Some say that is because we have ten digits on our hands, and hence prefer to count in multiples of ten. Well, that is at least how the decimal system started. So, let's take a deeper look into the system. The system is based on 10 numbers, or "digits", {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} = {0 to (10-1)}. Any number you want to express in this system, can be written as a combination of these ten digits and a power of 10. Eg.,

\(\begin{equation} 173=1*10^{2}+7*10^{1}+3*10^{0} \end{equation}\)

And so can any other number be decomposed. Here, the number 10 is called the "base" or "radix" (Latin for "root") of the number system.

Let us now take any general number system, with a radix, say, N, where N is an integer. Such a number system will consist of N digits, viz., \( \{0, 1, 2, ... , N-1\} \). (In case of decimal systems, N = 10, and so the digits are \( \{0, 1, 2, ... , 9\} \)). Any number in that system can be expressed as,

\(\begin{equation} (xyz)_{N}=x*N^{2}+y*N^{1}+z*N^{0} \end{equation}\)

where \( x,y,z\in\{1,2,...,N-1\} \). The right side of the above equation evaluates to the value of the number in the decimal system. The left hand side is the value of the number in the base-N numbering system, as is denoted by the subscript_N.

Now equipped with these terms, we are beginning to get an idea of what these number systems are all about. Well, from a bird's eye view, they appeared really complicated, didn't they? I mean, what are binary, ternary, hexadecimal systems all about! Even their names are so complicated! But now that we know how these systems work, they don't seem so formidable after all.

So, how does the binary system work? Binary means the system has only two digits, \( \{0,1\} \). Hence its radix is? That's right, 2. So, say I give you a binary number \( (11001011)_{2} \), what is the number in decimal?

$$ (11001011)_{2}=1*2^{0}+1*2^{1}+0*2^{2}+1*2^{3}+0*2^{4}+0*2^{5}+1*2^{6}+1*2^{7} $$

$$=1+2+0+8+0+0+64+128=(203)_{10} $$

Till now we have understood what the number systems mean and what any number in any number system is in the decimal system. Now, let us divert our attention to another important aspect - how to convert from the decimal number system to any other number system. Since we multiplied each digit of the number by its radix_to_some_power and added them all up to get the decimal number, it seems logical that while converting back to radix_N, we should divide the decimal number by the radix and take the remainder at each stage. Let us try and see this more mathematically. As we saw in the previous example,

$$ (203)_{10}=1+2+0+8+0+0+64+128 $$

$$ =1*2^{0}+1*2^{1}+0*2^{2}+1*2^{3}+0*2^{4}+0*2^{5}+1*2^{6}+1*2^{7} $$

$$ \Longrightarrow(203)_{10}/2=\frac{1}{2}(1*2^{0}+1*2^{1}+0*2^{2}+1*2^{3}+0*2^{4}+0*2^{5}+1*2^{6}+1*2^{7}) $$

which leaves a remainder $ 1 $ and a quotient $ 1*2^{0}+0*2^{1}+1*2^{2}+0*2^{3}+0*2^{4}+1*2^{5}+1*2^{6} $. Thus, we get the LSB (Least Significant Bit) or the right-most digit of the binary number. If we continue this process with the quotient obtained, we'll get the next right-most digit, and so on, until the quotient becomes 0 and we get the MSB (Most Significant Bit) as the remainder.

That's a pretty easy procedure to follow! Just be very careful that you get back the digits in the reverse order. But some of you may wonder why do we have to remember two different processes from converting from decimal to base N and vice-versa. Shouldn't there be a single process that covers both? Turns out, you can apply a similar process, only complication being that the numbers now have to be all represented in radix N. Let's see in the next example what this means:

$$ (203)_{10} = 2*10^{2}+0*10^{1}+3*10^{0} $$

$$ = (10)_{2}*(1010)_{2}^{2}+0*(1010)_{2}^{1}+(11)_{2}*(1010)_{2}^{0} $$

where we have represented all decimal numbers as their binary equivalents. Thus $2_{10}=10_{2}$, $3_{10}=11_{2}$ and $10_{10}=1010_{2}$. As you can see, this makes the whole process very complicated and defeats the entire purpose, as now you are supposed to know the binary values of all these decimal numbers, and then you are also supposed to be good at binary multiplications! And even if you manage to do that, imagine what happens when we change the radix! 

The only purpose this entire procedure serves is that now we know how to convert from any base to any other base; not just to and from base 10. Say we want to convert the number $122_{3}$ to its binary equivalent. We can straightaway proceed as follows:

$$ (122)_{3}=1*3^{2}+2*3^{1}+2*3^{0} $$

$$ =1*(11)_{2}^{2}+(10)_{2}*(11)_{2}^{1}+(10)_{2}*(11)_{2}^{0} $$

$$ =1*(11)_{2}*(11)_{2}+(110)_{2}+(10)_{2} $$

$$ =(1001)_{2}+(110)_{2}+(10)_{2} $$

$$ =(10001)_{2} $$

The result can be verified readily by converting each of the representations to the corresponding decimal value. This I am leaving as an exercise you can try yourselves.

We have thus seen some of the bases in which we can represent numbers - binary (base 2), ternary (base 3), and decimal (base 10). Some of the other important radices (plural of radix) are 8 (octal number system) and 16 (hexadecimal number system). These systems are used extensively in computer programming and digital system design since they can represent binary numbers in more compressed formats (please note that 8 and 16 are powers of two after all - can you explain why this fact helps?). One thing to note in hexadecimal systems is how the digits are represented (sadly we have only 10 digits due to the shortage of fingers (digits) in our hands (the ancients should have considered the 10 toes as well when counting!)). The hexadecimal digits are $ \{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\} $. The last six digits are represented (sadly, in need of a better choice) as the first 6 alphabets in the English language.

So, start playing around with the number systems. Till the next time.

Digital Circuit Design Problem #1

Hi everybody. Well, first of all, I would like to apologize for the long delay in this post. Actually, I've been a bit busy over the past few months. Anyways, here I am again, continuing forward on our digital path.

Now that we know the basic gates and some of their properties, we would like to build some circuits using these gates. Let us get our hands dirty then. Let's try one.

Well, here is a problem statement:

You have an automatic lock in your home. It has a 8-bit key set into it, which can be set  as and when required from inside the house. There is a 8-bit keypad outside the door. Only if you type in the right key, the door will open. You have to design this lock.

Before going to find the solution, I would strongly suggest that you download this jar software and try to simulate the solution on this first.

Solution:

Before looking at the solution, please put your brain cells to some work. Fire them up and try to analyze the problem. Try to find a solution yourself. If it becomes impossible or difficult, then move onto the solution I'm providing here. Also, your solution may be different from what I'm proposing here. Please post your solution too for the benefit of others.

So, how to proceed? Let's say the key set into the lock is 10010010. So, when we set the same key in the keypad, only then the door will open. That means each of the bits have to be matched to the corresponding bit of the key set. Now, is there any gate we've studied so far that does this trick of comparing? Let's take a look again at the truth tables of the gates. Do you find any such gate that gives a logic '1' only when both the inputs match?

On taking a close look, we find that EXNOR gate does exactly that.

So, now all we need to do is put one exnor gate between every bit of the keypad and the corresponding bit of set key. But does this solve the problem? Let's say we have typed in the right key. So that every EXNOR gate gives a logic '1'. We have 8 exnor gates giving a logic '1' at its output. So, which do I connect to the lock to open it? The answer should be all of them. But then the lock will open on only one signal. So, what do we do now? Now, let's think a bit more. What if there was a gate that would give '1' as an output only if all of its inputs are '1'? That is, a '1' is obtained only when all the bits of the keypad match with those of the key. And voila, we find such a gate yet again. It's an AND gate. Now I'm loving these gates. They do exactly what we want them to do, don't they?

We can use a 8 input AND gate here. We connect the outputs of all the EXNOR gates to this AND gate, and the output we connect to the lock. The final circuit would look somewhat like this. 

The circuit I've shown here has been simulated on Logisim. Do try out your circuits on this software.

We'll try out other circuits in upcoming posts. In the meantime, try out your designs and try to find out other digital circuit problems. And most important, don't forget to post your comments/suggestions.

A Walk through the Gates

So now that we have digital signals, what to do with them? Obviously, we would definitely like to build some circuits that can use these signals. We said that computers use digital signals. Wouldn't it be great if we could make one, or at least design it?

We will move on to that. But before that, we need to know what digital circuits are made of. If we look into any analog circuit, the basic building blocks are resistors, capacitors and inductors. Similarly, in digital domain, we have what are called as "Logic Gates". Gates? What are these , now? Well, they are simply 'gates'. What does a normal gate do in our daily life? It lets you pass. Or, it may stop you. Similarly, for logic gates. They either let a signal pass, or they stop a signal. Why called logic gates? Because they work on simple logic. Consider an AND gate. Now, when we say Rahul and Arun, it means both of them. Similarly, an AND gate gives an output only if both the signals at its input are present.Now can you explain what an OR gate does? Write a comment to explain.

Before going into more details about logic gates, we need to know what is known as Boolean algebra. It is named after George Boole(1815-1864), an English mathematician, who invented it. We said before that digital circuits use only 0's and 1's as its signals. 0 repesents an off signal, a false logic. 1 represents an on signal, or a true logic. Based on these two logical levels, the algebra which has been developed is called Boolean algebra. Since we use only two numbers to represent this system (viz., 0 and 1), it is also called as binary algebra, and the numbers formed using this system are called binary numbers.

In Boolean algebra, we define a few operations, as follows:

• AND: If 'a' and 'b' are the inputs, then the output is 1 only if both a and b are 1, otherwise the output is 0. Symbolically, this is represented as a.b.

• OR: If 'a' and 'b' are the inputs, then the output is 1 if either a or b is 1., otherwise the output is 0.Symbolically, this is represented as a+b.

• NOT: If 'a' is the input, then the output is 1 if a is 0, otherwise the output is 0. Symbolically, this is written as ~a.

• NAND: If 'a' and 'b' are the inputs, then the output is 0 only if both a and b are 1, otherwise the output is 1. Symbolically, this is represented as ~(a.b).

• NOR:  If 'a' and 'b' are the inputs, then the output is 0 if either a or b is 1., otherwise the output is 1.Symbolically, this is represented as ~(a+b).

• XOR:  If 'a' and 'b' are the inputs, then the output is 1 only if a and b are unequal, otherwise the output is 0. 

• XNOR:  If 'a' and 'b' are the inputs, then the output is 1 only if a and b are both equal, otherwise the output is 0.

These are the basic gates we use to implement any digital circuit. These logic gates are available in the market in the form of integrated circuits (ICs). We shall talk about that later on. Now let us focus on basic operations on binary digits, ie., 0 and 1.

The basic operations that can be done on binary digits are OR, AND & NOT. All other operations are combination of these three operations. For example, XOR can be obtained from these basic operations as follows:

a xor b = a.(~b)+(~a).b

Just try the above equation with all possible values of a and b, and you will know the justification of the same.

In order to make these basic operations, viz. AND, OR and NOT simpler, we have to go through some basic properties related to these operations. Let us look through these one by one:

• Identity Property:  

             a + 0 = a
             a.1 = a

• Zero Property:

             a.0 = 0
             a.(~a) = 0

• Unity Property:

             a +1 = 1
             a + (~a) = 1

• Commutative Property:

             a + b = b + a
             a.b = b.a

• Associative Property:

             a + (b + c) = (a + b) + c
             a.(b.c) = (a.b).c

• Distributive Property:

             a.(b + c) = (a.b) + (a.c)
             a + (b.c) = (a + b).(a + c)

• De Morgan's Law:

             ~(a + b) = (~a).(~b)
             ~(a.b) = (~a) + (~b)
In all the above examples, a,b,c are binary digits.

Thus, keeping these properties in mind, we can go forward on our journey into the digital world. In fact, we have come quite far into the world of digital electronics. We have now known how the digital or binary data operate on each other. We have seen what logic gates are. The next problem would be how to use all these to implement a digital circuit. For this purpose, we will consider some real world problems and try to find out their solutions using the knowledge we have gained so far. But for that, we have to wait till my next post. Till then, keep your brain cells busy by solving a few questions.

Try to reduce the following Boolean expressions into the simplest form possible:

a) (a+b+c).(a.b+a.c).(~(a+b))

b) ((~a).b.(~c)) + (a.(~b).(~c)) + ((~a).(~b).(~c))

c) ~(a.b.c + (~a).b.c + a.(~b).c + a.b.(~c))

Note: While solving, you can use another notation for (~a) denoted as follows: 

Well, any comment will be highly appreciated. So please don't forget to leave a comment before you leave the page. And don't forget to express your reactions below.

Sampling, Quantization & Encoding

Since we have discussed on what digital signals are, the next question that obviously comes up is how do we generate a digital signal? Digital signals can be generated from analog signals by the means of 3 basic steps:

• Sampling
• Quantization
• Encoding

We will take a look at each of these steps one by one.

What should be the first step in getting a digital signal? You need to discretize the analog signal in time. This process is called the process of sampling. For the purpose of sampling, the analog signal values are measured at discrete intervals of time, say at an interval of 1 second each. Physically this can be done with the help of a simple circuit that uses a switch. The switch is on for a very small amount of time at an interval of one second. Thus, the analog signal passes through the switch during this small amount of time only, when the switch is on. Hence we approximately get the amplitude of the analog signal at these discrete periods of time.

Theoretically, this is represented as multiplying the analog signal by a train of impulses. An impulse is a signal that has some value only during the present time instant, ie, at time t = 0, but is zero elsewhere.A train of impulses are impulse signals occurring periodically over time. The train of impulses can thus be represented by the following diagram.

Thus, on applying the following input to the sampling circuit, the output is obtained as:

Once a signal is sampled, it is called a discrete signal. The next step towards digitization is Quantization. In this step, we do what is left for a signal to be called as digital, that is, amplitude discretization. We divide the amplitude into discrete levels. Usually the number of levels is a power of 2. This is done for easier binary representation. This will be further illustrated when we look into encoding. The resulting signal looks like this:

 

 Here, discretization of amplitude has been done with unit amplitude as the step.

The resulting signal is a digital signal. However, the digital systems we generally use, have binary representations only, that is, they can understand only two states, zero or one, or on or off. This is due to the fact that they are implemented using switches, namely, transistors, which can be either switched on or off. For this reason, the number of levels we have divided the amplitude into, have to be encoded in binary. This process is known as Encoding. Here we find the use of taking 2^n levels in amplitude. Any radix 2 number (having number of values equal to 2^n),  can be encoded into binary using n-bits, where each bit represents either zero or one. Any value within this 2^n can then be represented by an n-bit number. This can be demonstrated by a simple example.

Let us consider that we divide the amplitude into 8 equal levels. Now we know,

8  = 2^3

Thus, according to the previous argument, the number of bits required to represent any of these levels is 3. This is shown as follows:

Level 0 = 000 binary

1 = 001

2 = 010

3 = 011

4 = 100

5 = 101

6 = 110

7 = 111

Thus, we get 8 levels, from level 0 to level 7, which can be represented by 3-bit binary numbers. It is to be noted that the levels are numbered from 0 to 7, thus making a total of 8 levels.

For the digital signal we have generated, the encoded signal is as follows. We need 4-bits for encoding here, as 2^4 = 16:

The process of encoding provides us with the required digital signal, which can be transmitted over any transmission medium and can also be used by digital systems for different purposes.

We will try to explore the world of digital further in the up-coming posts. And as we move on, we'll try to focus on the practical aspect of designing a digital circuit. But before that, I must keep my promise. Here is the solution to the question that I asked: 

Why do we need a usb programmer rather than serial programmer on laptops?

Well, the answer is simply because laptops do not have a serial port for communication. Hence we are obliged to use a usb port and hence a usb programmer.

An Introduction to Digital Electronics

Ever wondered what the term digital really means? Literally, digital means 'relating to digits or fingers'. In other words, something that is countable. The signals we come across in nature are continuous in nature. By continuous I mean that they vary continuously in both time and amplitude. For example, take the case of your voice signal. As you speak, it produces a continuous variation, maybe in its amplitude or frequency with respect to time. Such signals are called analog signals. The following is an example of a typical analog signal.

Do you think this signal is countable? Yes, maybe in terms of peak amplitude or frequency, but will you be able to measure accurately the amplitude of the signal at any given time? Even the variation in time is infinitesimally small, which is not possible to measure or count. As a result, we get infinite number of  amplitude levels possible and infinite number of time durations. Thus, the signal is not countable.

So, how can we make this signal countable? We do this by measuring the signal at specific intervals in time, say after 1 second duration. This leads to discretization in time. What about the amplitude? That can also be discritized or divided into levels. For example, any amplitude between 0 and 0.9 Volts may be treated as 0 Volts, considering the signal is a voltage signal. The resulting signal may be as follows:

Here, we have discretized in time taking each sample after 3 seconds. The first diagram shows the signal discretized in amplitude, each amplitude level differing by one unit. The second diagram shows a discrete signal, that is the signal discretized in time. These two together result in a digital signal, as shown in the third figure, since at every point, its amplitude and time can be measured with 100% accuracy.

So, now that we have got a more clear idea of what a digital signal is, let us see what digital electronics deals with. Well, obviously digital signals. Digital systems are systems that can work on digital signals and transform them for various purposes according to our needs. However, I said a little while ago that most of the signals we come across in nature are analog signals. Then why do we need digital signals? It is due to the fact, that digital systems such as our computers can deal only with the digital signals. Digital electronics grew in demand due to the fact that the digital systems can be implemented very easily, using only switches. In the present day market, switches are implemented using transistors, thus making a system able to incorporate a huge number of switches as well as increasing the speed of operation of systems manifold. Digital systems ensure better security and less noise on transmission. Due to all these factors, digital electronics has become a very important and fast developing branch of electronics.

Having said so, we will next concentrate on how an analog signal may be converted into a digital signal in my next post.

As for the question I asked you in my last post,

"Why do we need a usb programmer rather than serial programmer on laptops?"

think a little more. I'll give you the answer on my next post. Till then, happy electronizing!