Header Image - Randall Morgan

Blog

24 Articles

Designing The MiniMips – Part 3 A Basic ALU

by SysOps 0 Comments
<span class="entry-title-primary">Designing The MiniMips – Part 3</span> <span class="entry-subtitle">A Basic ALU</span>
This entry is part 3 of 4 in the series Designing the MiniMips

Ok, we left off last time discussing the issues involved in binary arithmetic. Specifically, we discussed subtraction and negative numbers. We watched a Compuphile video about the issues and the Prof. showed us how to use 2’s complement to use negative numbers and addition to complete subtraction. I had asked you to play around with your own ideas on how to implement this in hardware using Logisim to simulate your ideas. I hope you had fun doing that. Here’s my idea for implementing a binary adder that uses two’s complement to do subtraction.

Now this is only one stage of the circuit. What I’ve done is taken a typical full-adder circuit and added an XOR gate to the B input. The other leg of the XOR gate is used to control the inversion of the B input value. Additionally, I’ve also tied the Sub input control bit to an OR gate used to force a carry-in bit into the adder. This has the effect of inverting B to get the 1;s complement and then adding 1 to get the 2’s complement. Only the first bit needs the OR gate for a carry-in. However, every bit in B will need the XOR gate to invert the bit.

The ALU

Ok, now that we’ve taken care of old business it is time to look at the next stage of our Microprocessor development. The core of any Microprocessor or Micro-controller is it’s Arithmetic Logic Unit. This piece of hardware is responsible for completing arithmetic and logic operations. If a basic logic or arithmetic operation is not implemented in the ALU it is much more difficult to implement that function in the systems built around the microprocessor. There are a few exceptions to that… We’ll discuss some of those later. For now, let’s look at how we might build an ALU for the MiniMips.

If you’ve followed this series so far, I assume you have the basic understanding of the primitive logic operations AND, OR, NOT, and XOR. We need to implement AND, OR, NOT, and XOR as well as Addition and Subtraction in our ALU. The simplest way to do this is to include a hardware circuit for each operation and then complete them in parallel. We can then select the desired operation from the various results. Since our hardware operates in parallel it takes no extra time to implement additional operations in our ALU this way.

So our ALU operations should look something like this:

One thing we haven’t discussed yet is Signal Bus’s. A signal buss is simply a group of conductors with a common implementation theme. For example, our ALU takes two inputs A and B. Each of these inputs contains 16 signal lines, one for each bit in the 16-bit value. We could refer to these signals as the A input Bus and B input Bus. You may have also heard of the Address bus and Data Bus in a computer system. These are just groups of Address or Data signals just like our A and B inputs. A simple way to think of a bus is just to think of them as a bundle of wires all carrying related signals.

Our simple ALU has six operations. It can Add, Subtract, NOT, AND, OR, and XOR our input values. Note that Inverting is only supported on the B input. This was a choice made for our design that helped reduce the number of logic gates needed to implement the design. This is great! We can now do multiple operations on our two input values. But how do we select the results of just a single operation? Well, that’s where multiplexer come in.

Multiplexers

A multiplexer can be thought of as a rotary switch that selects one of many input signals:

This image show’s a two pole rotary switch. But let’s just concentrate on the top portion of the image. S1a is the first pole and the center armature or wiper simply rotates to make and break contact with the outer contact points as the user turns the rotor. To allow multiple conductors like our two input values A and B to be selected, these switches are manufactured with many sets of switches stacked on top of each other and connected to a single rotor. This way when the user turns the rotor, all the wipers rotate at the same time. With the switch shown a user can select from 1 of 6 positions. If we used rotary switches in our computer we would have to rotate these switches by hand to the proper positions and at the proper times, just to complete a single operation. Luckily there are solid state implementations of these devices called multiplexers and demultiplexers. A multiplexer simply takes many input values and switches one of them to a single output. A demultiplexer works the other way around. So a multiplexer is a many to one and demultiplexer of a one to many switch. In Logisim you’ll find multiplexers and demultiplexers under the Plexer components.

You may be asking how we tell a mux or demux (multiplexer/demultiplexer) which contacts to use or how each input to select? Well, we have to provide a selection signal. This is just a binary value. Let’s look at a simple four bit to one bit multiplex circuit.

Build the Mux and Demux circuits shown below and see that the input or output is selected buy the two select bits S0 and S1. These are simple 4-to-1 and 1-to-4 circuits that control a single bit. We will need circuits that control 16-bit inputs with as many as 16 selectable inputs.

As you can see, we’ve used a set of AND gates and wired the the selection inputs and their complements to the gates to provide activation of each gate with a specific binary value. This allows only one AND gate to be active at a time. The AND gate outputs are all then fed into a single OR gate. That gate outputs is the signal on the input to the selected AND gate.

To convert the mux into a demux, we only need to tie all the signal inputs together and remove the OR gate.  Try this in logisim. Build the two circuits above and tie the output of the mux to the input of the demux. Then tie S1 together on both circuits. Next tie S0 together on both circuits. Now you should be able to select one input on the mux and get the signal out of the same input on the demux.

Now let’s see how we can tie a mux to our ALU so that we can select a single operation from the ALU:

Ok, so here we have our ALU with a few extras. First and foremost is Mux we added to the output. I’ve labeled the select lines for the Mux as OPCODE. If you look at the miring of the mux you’ll notice that I wired the out of the adder to the first two inputs of the mux. I then created a decoder that decodes the value 1 from the four OPCODE bits. The resulting signal is used to tell the Adder/Subtractor to subtract. This allows us to select Addition as 0 and subtraction as 1. Here’s a table of OPCODE values and ALU operations:

OPCODE OPERATION
0000 A+B
0001 A-B
0010 ~B
0011 A AND B
0100 A OR B
0101 A XOR B

Now you may have noticed that I used a mux with four select inputs. This allows up to 16 operations but I’ve only included six here. We will be adding more operations to our ALU later. Now you may be asking “Where does the values for A, B and OPCODE come from” ? Well, that all depends on our instruction set and how we implement it. We’ll be discussing that soon. For now, try and build an ALU that matches the operation of this one.

Designing The MiniMips – Part 2 Subtraction and Negative Numbers

by SysOps 0 Comments
This entry is part 2 of 4 in the series Designing the MiniMips

Last time we discussed binary addition and how we could use a few logic gates to do arithmetic. I showed you a few simple circuits and left you with a simple assignment to use the full adder circuit to build a multi-bit full adder. I told you I’d show you a solution to the exercise. So here it is:

As you can see the full adders are simply cascaded by connecting the carry-out of the previous stage to the carry-in on the next stage. This cascading can be continued until the propagation delay of the carry signal become intolerable. If that happens there are techniques for improving the circuit. Checkout the Carry Lookahead Adder circuit.

Binary subtraction

We’ve seen how binary adders can be built from simple logic gates. Now let’s look at binary subtraction. The binary subtraction rules are very simple:

0-0 = 0 1-0=1 1-1 = 1 10-1 = 1

Binary subtraction is similar to decimal subtraction with the difference that when 1 is subtracted from 0, it is necessary to borrow 1 from the next higher order bit. That bit is reduced by 1 and the remainder is 1. The one thing that confuses most people when doing a binary borrow is that when you borrow in decimal you add it as 10 to the previous column. In binary we are using powers of 2. So when we borrow we must add the borrow as two bits of half the original value:

1  1  1
1  1
1 0 0 0
0 1 0 1
0 1 1

In the above, starting from the left most bit. First we can’t subtract 1 from 0 so we try to borrow 1 from the next column to the right (the tow’s column). However, it too is 0. We can’t borrow 1 from 0 so we move on to the third column left (the fours column). Next, in the fourth column left we find a 1 in the eights column. Now this one represents an 8 in decimal. So when we move it to the fours column. We have to split that 8 into two 4s. So we place two 1’s above the fours column. Next we borrow one of them and move it to the two’s column as two 2s. Again, we borrow a two from the 2s column and move it as two ones and place them in the 1s column. Now we can subtract the 1 in the right most the two ones we placed there. This leaves a one which we bring down.  In the two’s column we can now subtract 0 from the remaining 1 and get 1. We then move left to the fours column and subtract 1 from the remaining 1 we carried over and get 0. The eights column is now 0 and being a leading 0 we don’t really need to bring it down as it adds no value to our answer. Now to check our answer we can see that our original problem was: 8-5=3. And indeed 11 in binary is 3 in decimal.

Now let’s look at the logic needed to do a single bit binary subtraction. The truth table for subtraction is:

A B Diff Barrow
0 0 0 0
1 0 1 0
1 1 0 0
0 1 1 1

 

Looking at the table we can see that the difference is computed using an XOR gate. The borrow out however is a slightly more complex. Borrow out is only 1 when A is 0 and B is 1. This looks like and AND gate with an inverter on B.  Let’s try it out in logisim. Build the following circuit in logisim and see if it matches the truth table above:

Now this circuit is called a half subtractor. Just as the half adder is missing a carry in, the half subtractor is missing a borrow in. However, a similar cascading trick like that used for the half adder can be used to build a full subtractor. Let’s try this out. Build the circuit below in logisim and give it a try:

Negative Numbers

Now this kind of subtractor is great if you are only working with positive numbers. But if we ever need to work with a negative value as an operand or a resulting value, we are out of luck. So how do we handle negative numbers? Well, the most typical way is to reserve the left-most bit for use as a sign bit. The sign bit is set to 1 to indicate a negative value and 0 to indicate a positive value.  So if we have 8 bits we can represent -127 through +127.  There is an issue however, To demonstrate it let’s reduce this to a bit bit signed number. So we can represent -7 to +7 with the three bits know as the magnitude and the fourth bit as the sign bit.

 

Value Sign 4 2 1
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
-0 1 0 0 0
-1 1 0 0 1
-2 1 0 1 0
-3 1 0 1 1
-4 1 1 0 0
-5 1 1 0 1
-6 1 1 1 0
-7 1 1 1 1

Notice anything odd about this arrangement? Look closely, there are two zero values. Zero and negative zero. Who ever heard of negative zero? Sign magnitude presents it’s own issues. A program or hardware would have to check for two values of zero if this was implemented in our microprocessor. So what can we do about this? How about flipping the bits and using one’s complements. This too has it’s own issues. The issues with negative numbers is solved by something called two’s-complement. I found a Computerphile video that I think gives one of the best explanations available. Watch the video to learn more about binary math and negative numbers:

 

Now I am sure you have a good grasp on the problems and solutions to binary mathematics. I’ll leave you with this: How can we modify our multi-bit adder for use in both addition and subtraction? I’ll show you my solution next time. Until then, play around with your own ideas in logisim and try to build an adder/subtractor circuit using 2’s-complement.

 

Desgning the MiniMips A Simple 16 bit Microprocessor

by SysOps 0 Comments
This entry is part 1 of 4 in the series Designing the MiniMips

A while back I designed and built my own 16-bit microprocessor. I wanted to be able to use my processor in my own projects. My requirements were very simple. It had to be easy to understand, have an instruction set that is simple to use, as this makes it easy to generate a simple compiler for the instruction set. My desired instructions were pretty simple. I wanted something akin to the MIPS instruction set. Instructions should take one or two source operands, and a destination register or memory address. In the case of comparative instructions, it should simply discard the results. The processor should include a hardware stack. It should contain at least 16 general purpose registers and at least four I/O ports. I would prefer instructions to take a single cycle. But If I include a multiply and divide instruction this isn’t practical.  My last requirement was that I should be able to use free and open-source tools. I did a basic design in Logisim and then moved the design to VHDL and place it on an FPGA.

The project started off great but hit a few bumps in the road along the way. I eventually worked them out and got everything working. But I never really documented the project. So that’s what I’ll attempt to do here. I’ll step back and walk through the process I took; errors and all.

Designing a microprocessor isn’t a task for the faint of heart, however, it isn’t a task that should be impossible either.

This serries of blog posts will be more a record of how I proceeded with this project. I’ll include my mistakes, faux pas, and hopefully, the solutions I found, so readers may amuse themselves at my expense… If you follow along and find these posts interesting, have helpful hints or information, or if you build the MiniMips let me know in the contact form. I’d love to hear from you.

So how do we get started? Well, I’ll assume like myself, you have a grasp of digital logic basics. So let’s start by writing some requirements for the ALU. The ALU is the core of the processor. It’s the part that provides the Arithmetic and Logic functions. The ALU has at least three inputs: Operand 1, Operand 2, and the operation code. It should produce at least two outputs; the result of the operation, and a set of status indicators or flags.The ALU will perform the following operations:

  • Binary Addition
  • Binary Two’s Complement Subtraction
  • Binary Bitwise Inversion
  • Logical And of two binary values
  • Logical Or of two binary values
  • Logical XOR of two binary values
  • Logic Shift Left
  • Logical Shift Right
  • Logical Rotate Left
  • Logical Rotate Right

So if I count correctly that’s ten ALU operations we need circuitry for. Let’s start with the arithmetic first, Add and Subtract:

Let’s first review the laws of binary arithmetic:

Addition 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0
Subtraction 0 – 0 = 0 1 – 0 = 1 1 -1 = 0 10 – 1 = 1

Now let’s look at a couple simple logic operations:

AND Operation OR Operation XOR Operation
1 AND 1 = 1   1 OR 1 = 0  1 XOR 1 = 0
0 AND 1 = 0   1 OR 0 = 1  1 XOR 0 = 1
1 AND 0 = 0  0 OR 1 = 1  0 XOR 1 = 1
0 AND 0 = 0  0 OR 0 = 0 0 XOR 0 = 0

You might notice that adding to binary digits produces the same results as XORing two binary digits. So to add to binary digits together we only need to XOR them. However, when we try to do arithmetic operations on multi-digit numbers we have the issue of carrys and barrows. Let’s just look at addition for the moment. When we add two two-bit binary numbers and have a one in the same column in both numbers we must carry a one to the next column. Just as we do in decimal arithmetic.

Carries 1 1
1 0 1 1
+ 0 0 0 1
Results 1 1 0 0

 

If you look closely you will notice that the carry happens anytime there are two ones in the same column. This is basically the AND logic operation.

To follow along download Logisim or Logisim-Evolution and create the circuit show below. (I reccomend you open the Logisim help and locate the tutorial and complete that first if you have little or no experience with logisim.)

Above you see a simple XOR gate. Play with it and test it to see if the output is high only when A+B = 1 and low when A+B <> 1. These condition only hold true if only A * -B | B * -A is true.Remember if A and B are both 1 or high, then the addition results in the output being low and a 1 carried over to the second bit condition. However, here we have no second bit to handle the carry out. So let’s see how to add the carry out to our simple 1-bit adder circuit.

Above you can see the addition of a simple AND gate. The AND gate only generates a 1 on it’s output when both inputs are high. So in this circuit it makes the perfect carry out generator. This type of adder is known as a Half Adder because it only does half the job…

Ok, that’s fine and good you may say however, what about adding multi-bit numbers? How can we do that?

Adding multi-bit numbers requires more than a carry out signal… We also need a carry-in signal. The carry-in allows the carry-out from the previous column to be added into the result of A + B. So our new circuit needs to include the carry-in as part of the sum. To do this, we just need to add the carry-in to the result of A + B. We can do this with another Adder:

So here’s two Half-Adders cascaded together to allow for a Carry-in signal from the prevous column. There is an issue however. We now have two carry-outs. The original and the carry out from the second half adder used to add the carry-in bit. As it turns out, you can’t have both carry-outs active at the same time. To see why simply follow the logic;

  • If A=1, B=1 Cin=1: Sum 1 = 0 and Carry-out 1 = 1, Sum-out 2 = 1 and Carry-out 2 = 0
  • If A=1, B=1, Cin=0: Sum 1 = 0 and Carry-out 1 = 1, Sum-out 2 = 0 and Carry-out 2 = 0

Check the rest of the conditions by building a truth table. You’ll see that only one carry-out bit can be active at a time. So we simply need to detect when one or the other is active. That’s a perfect job for an OR gate:

OK, build these circuits in Logisim and play with them. Work out the a truth table for them all and prove to yourself they work as expected.

With the full adder you can create N-bit Adders by simply feeding the Carry-out of the previous column to the Carry-in of the next column. As an exercise use our full adder circuit to create an 8-Bit Adder.  Next time I’ll show you my 8-Bit Adder and then we’ll look at subtraction.

 

 

 

 

 

 

 

Flutter A New Erra In Mobile Development

by SysOps 0 Comments
I started using Dart a few months ago. I’ve been using Dart for small projects and some web development. It’s proven itself to be up to the challenges I thrown it’s way and capable of much more. When I started looking into developing a new mobile app for a friend. I dreaded the long development times and having to build two versions of the app. One for Android and one for iOS. Let’s face it, mobile development has never been fun, or easy. That’s why so many have built websites and wrapped them in a web browser and called it a mobile app. Native apps are tedious to develop.  At least they have been in the past. Working with Dart lead me to another Google project. Flutter; A cross platform mobile development framework. Flutter leverages Dart’s cross platform operation and speed to provide real performance in a cross platform framework. Furthermore, it’s fun! It’s been awhile since I had fun coding a mobile app! Flutter makes mobile development fun and basic apps are quick and easy to produce.
The one drawback to using a cutting edge technology is the lack of example code and poor documentation. The docs for Flutter are actually pretty good but not perfect. Also, since Flutter is still in the Alpha development stage, it tends to changed. A few changes have broken code in the past year. But very few. It seems the Flutter team now has a better picture of where they are going and how their going to get there, than they had a year or two ago. This has helped greatly to stabilize the existing code base. New features are being added almost daily.
There is one thing I will take my hat off to the Flutter team for: They’re very social and responsive! If you have a question, need to know how to accomplish as certain task, etc., they are responsive and informative. How often do you get to give the developer’s your input or get inside information on a library you’re using? Well, with the Flutter team it seems to happen contently!

There are several Flutter tutorials on youtube, at the official site: www.flutter.io and elsewhere on the web. So if you haven’t checked out Flutter yet, you need to…

 

Newsletter Powered By : XYZScripts.com