Links:

Part 0: What & Why

Part 1: What is a number?

Part 2: Basic Arithmetic in Theory

12/7/22

We spent the last calculator post exploring some basics of binary arithmetic using discrete logic gates. We ended by imagining how large the mess of wires would grow if we built every desired operation separately, pointing out the many redundancies that would ensue. For example, with our current 8-bit capabilities:

• Addition is fairly straight forward and fundamental. Building this functionality would involve an estimated:

  • 16 XOR gates

  • 16 AND gates

  • 8 OR gates

• Building a standalone subtraction module would involve flipping all the bits, adding 1 to the result, then doing the addition, involving an estimated:

  • 8 NOT gates

  • 24 XOR gates

  • 24 AND gates

  • 8 OR gates

• Standalone multiplication doing seven (8-bits minus 1) additions, with a series of extra AND gates at each stop, for an estimated:

  • 112 XOR gates

  • 176 AND gates

  • 56 OR gates

• And the big one, division, involves iterating multiple multiplications, additions, and subtractions, several times. I think at a minimum, building a totally isolated circuit to do division would involve:

  • 24 NOT gates

  • 1104 XOR gates

  • 1680 AND gates

  • 536 OR gates

You can see the incentive to not build standalone modules for each of these operations. Rather than building nearly the same addition circuit seven times to do one multiplication problem, it would be better to build the addition circuit once and call upon it seven times, storing the intermediate results somewhere in the interim. Rather than building an isolated circuit to handle division all by itself, involving who-knows how many redundant addition and multiplication (addition) circuits, we can just store intermediate values somewhere and call on more generic logic when we actually need it. Basically, if we have identical functionality in multiple places, we should instead remove the redundancy and call on the singular generic function multiple times. We want our calculator to operate more like the architecture on the right, and thus far we've been thinking like the architecture on the left:

We'll largely ignore the Input and Output design (getting inputs from buttons, sending output to a display, and the conversion from machine-readable binary to more human-readable base-10 digits) for now to focus on the body of the calculator: the storage and functions. For the time being the Input is simplified to 8 switches with a tri-state buffer regulating their output. Once again, I'm no electrical engineer, but it seems like the "tri" refers to the three possible states of output being On, Off, or Undefined. Once the Write switch is enabled, the input switch can pass its data (or lack of data) along, but when the Write is disabled, nothing passes through.

Storing data is a little complicated, and I won't attempt to comprehensively explain how it works. Very basically, there are logic setups that allow one to capture or "latch" an electrical signal input and hold it as an output. Below is the diagram of a "D Flip-Flop", which can store the value of the Data input: 0 or 1. This is the first time we've seen a Clock involved, and again I'll ignore the intricacies of how it works for now. Essentially, it just supplies a steady alternating beat of 0's and 1's at a certain frequency. My understanding of why a clock gets involved in data storage is due to the behavior of logic outputs flowing back into logic inputs and the physical delay of electricity flowing through logic gates. I'm under the impression that without the clock in place to serve as somewhat of a metronome, the behavior of the circuit becomes ambiguous and unpredictable. With the clock incorporated into the logic, we can be certain that events and data refreshes only happen once per tick, only at the instant that the clock transitions from off to on. The wiring on top is the D flip-flop laid out bare, and the bottom is the D flip-fop condensed into a smaller package due to it's frequency of use:

Where this becomes powerful is the ability to control when the D flip-flops are allowed to take on new values, and when they should simply hold what they already have. By incorporating a little more logic, and another "Read" switch, we gain this control. Below, in Step 1 both the Read is enabled and the Data is set to 1, so the output on the right is a 1. In Step 2, the Read switches is disabled, so no new data should be read into the D flip-flop now. In Step 3, with the Read still disabled, I can turn the Data off to 0, but the output is still a 1. If I enabled the Read again after this, the output would change to 0. Without the Read enabled, whatever the previously read data value was will be preserved.

I started wiring up a 4-bit module that has 4 D flip-flops, Read functionality, and the Write functionality from above. We can control exactly when new data is read, preserve the last read data, and control when exactly the preserved data is allowed to output or write.

I combined two of these into the 8-bit module below, calling it a "Register", and cleaned up the wiring. I'll continue dealing with 8-bit data for now, but I wanted to leave the design fairly stackable so I can add more bits later:

Here's two of these registers hooked up to a shared central highway of wires, known as a "bus":

This is a super powerful breakthrough. We can now enter a number into our input, write that data onto the bus, and then read it into one of the registers that'll store it. Then we could repeat the same process and write a different number into the input, write that to the bus, and read the new data into a separate register. Either one of the values can then be written back out to the bus independently and displayed to the output. This may not seem terribly exciting, but I was pretty stoked. The ability to move around, save, and recall data will open up the door to many possibilities. We no longer have to build the logic for addition, subtraction, multiplication, and division separately, but rather we can build several of the basic functions necessary and reuse them over and over.

It's important to note that only one module or register should be allowed to write to the bus at once. Otherwise there can be conflicting data and things break:

I tacked on the (now heavily modified) 8-bit adder from last post to the bus as well. The adder has one 8-bit storage register built into it. I was initially tempted to hook the adder's two inputs directly to the X and Y registers, but then I figured that that choice would be too limiting down the line. I will add more registers, able to store intermediate answers to multi-step problems, and I'll want to be able to add data from those other registers as well. One of the inputs to an addition problem can be written to the bus and read into the adder's built-in storage. The second input can simply be written onto the bus. The adder is always calculating the sum of the number in its internal storage and the number currently on the bus, and saving that into built-in D flip-flops. Once the bus is cleared, the adder can write to the bus and some other register or function can read the sum.

So if you wanted to add the numbers 2, 5, and 7, you would follow these steps:

• INPUT 00000010

• INPUT WRITE ENABLE

• X-REG READ ENABLE (2 is stored in the X register)

• X-REG READ DISABLE

• INPUT 00000101

• Y-REG READ ENABLE (5 is stored in the Y register)

• Y-REG READ DISABLE

• INPUT 00000111

• ADDER READ ENABLE (7 is stored in the adder built-in register)

• ADDER READ DISABLE

• INPUT WRITE DISABLE

• Y-REG WRITE ENABLE (12 is stored in the adder's sum D flip-flops now)

• Y-REG WRITE DISABLE

• ADDER WRITE ENABLE

• Y-REG READ ENABLE

• Y-REG READ DISABLE (12 moved from the adder back to Y register)

• ADDER WRITE DISABLE

• Y-REG WRITE ENABLE

• ADDER READ ENABLE

• ADDER READ DISABLE

• Y-REG WRITE DISABLE

• X-REG WRITE ENABLE

• X-REG WRITE DISABLE

• ADDER WRITE ENABLE (14 is now on the bus, and can be read by whichever register)

• OUTPUT 00001110

Now this may seem like a lot of steps, but the goal is to have the calculator figure out all these steps internally from just a few user inputs. On my HP-12c I can enter:

• 2

• ENTER

• 5

• ENTER

• 7

• +

• +

and get the same result, but I'm sure internally the calculator is doing something like the steps above behind the scenes. I'll figure out how to decode human instructions to calculator instructions... eventually. For now, I got carried away making more arithmetic-focues modules. Let's take a tour:

The CHANGE SIGN module:

It reads a positive or negative 8-bit 2's compliment number from the bus, converts it to it's additive inverse, writes back out to the bus. With this and the Adder, we can now do subtraction!

LEFT-SHIFT and RIGHT-SHIFT modules:

These two simply take the number on the bus and shift everything either right or left by one bit. With these, the Change Sign module, the Adder module, and still some human thinking, believe it or not we can do multiplication via the Russian Binary method discussed last post.

On to division... Now I will caveat division by admitting that I have no idea whether my approach is the most efficient method or even close to it. I did a lot of pen and paper experimenting and some Google searching before concluding that the Newton's method iterative approach was the best. I could very well be wrong though. Recall that the method avoids actually doing division by instead finding an input's multiplicative inverse and then doing multiplication. The method finds the multiplicative inverse by iterating an equation that only uses subtraction (addition) and multiplication. We already have these tools built, but the iterative approach still needs an initial guess to get started though. Meet, what I'm calling, the Quick Reciprocal:

It's an original design, so it's a bit of a mess. Basically, everything to the left of the Q in "QUICK" is responsible for finding and isolating the left-most bit that appears in a number. Example:

00100110 returns 00100000

11111111 returns 10000000

00000001 returns 00000001

This is equivalent to rounding a number down to the nearest power of 2. Some numbers should round up, however, so the zigzag bit of logic in the middle checks if the number directly to the right of the leftmost number is a 1. If that is true, the number should be rounded up instead of down. From there the number gets mirrored about the 1's place like so:

(8) 1000.0000 returns 0000.0010 (0.125)

(4) 0100.0000 returns 0000.0100 (0.25)

(2) 0010.0000 returns 0000.1000 (0.5)

(1) 0001.0000 returns 0001.0000 (1)

(0.5) 0000.1000 returns 0010.0000 (2)

(0.25) 0000.0100 returns 0100.0000 (4)

(0.125) 0000.0010 returns 1000.0000 (8)

So long as the number read in is not negative, this appears to work fine. Negative numbers have to be converted back to positive when doing multiplication anyway, so there will definitely have to be logic in place to catch those cases. Also, I've been pretty comfortable switching back and forth between unscaled and scaled binary numbers haphazardly, because it doesn't affect most logic we've encountered so far (addition/subtraction unaffected, multiplication fixed just by right-shifting the product). Obviously, when dealing with division and "mirroring numbers about the 1's place", the scaling factor is hard-coded in to the logic. The final calculator build will have many more bits than 8 and the "Quick Reciprocal" module will need to be adjusted at that time. For the time being, I'm confident to say that, with a lot of patience and care, we have built the architecture of a calculator that can do addition, subtraction, multiplication, and division... given that you only want to handle numbers between -8 and 7.9375, with a maximum accuracy of 0.0625! We are certainly moving in the right direction. The next step, before any more modules are built, should probably be figuring out how to encode commands and the logic surrounding them. Basically, how to convert human actions to the calculator steps in the addition example above. Here's where the calculator stands now:

In the bottom right corner you can see I started working on a binary to 7-segment display decoder, in the hope that someday humans can actually read what the calculator is outputting. The logic shown is very inefficient with several redundancies and unnecessary logic. I started optimizing and condensing the logic but stopped and decided to leave the framework more open for now, so I can easily adjust, add the decimal point logic, and add new characters later. At this point it can display 0-9, but I have a feeling I'll be having to display this often:

Next up:

Stay tuned!