Java Circuit Simulation Workaround ▾

Due to recent changes by Oracle, java applets have become difficult to run in the browser. To mitigate the troubles, Oracle has provided the following websites to help users troubleshoot: http://java.com/en/download/help/enable_browser.xml and https://www.java.com/en/download/mac_download.jsp

Even after following the above instructions, loading applets may still show warning concerning “unsigned application” and “unknown publisher”. For Teahlab in particular, these warnings are due to the fact that we have opted not to pay a third party such as Verisign to sign our applets. Any warning that comes up when you try to run our applets should emphasize that our applets will always run with “limited access”, which is Oracle’s way of letting you know that teahlab doesn’t do anything on your computer except running the circuits you see: in other words, our applets are safe to run.

Sincerely,

The Teahlab Team

THE SERIAL ADDER
by Isai Damier (Let's connect on twitter @isaidamier )

The interactive Serial Adder digital logic circuit, with Boolean function

Introduction

A serial adder is a digital circuit that can add any two arbitrarily large numbers using a single full adder. Just as humans, the serial adder operates on one pair of bits/digits at a time. When you add the two 4–digit numbers 7852 and 1974, for example, you typically start by adding 2 plus 4 equal 6, then 5 plus 7 equal 12 (place 2 and carry the 1), and so on. Similarly, given the two 4–bit numbers 1011 and 0110, the serial adder starts by adding 1 plus 0 equal to 1, and then 1 plus 1 equal to 10 (place 0 and carry the 1), and so on.

For a general demonstration, both a human person and a serial adder follow the same sequential method. Given two 4–figure numbers A3A2A1A0 and B3B2B1B0, we add two figures at a time starting with the least significant pair, and so on. First, we do A0 + B0 = S0. Second, we do A1 + B1 + carry = S1, and so on; where the S figures represent the sum: A + B = S.

Notice that in the operation A1 + B1 + carry = S1, carry is not one of the inputs being added; the inputs being added are A1 and B1. Furthermore, the value of carry does not depend on the inputs A1 and B1. Carry is simply a given condition, the consequence of something that happened in the past; namely, A0 + B0.

Therefore, if we were tasked to “build a circuit that can add any two binary numbers using the sequential method that humans use,” we would treat the carry variable as a state variable. (In computer engineering talk, any circuit with one or more state variables is referred to as a finite state machine.)

Since the carry variable can either be 1 or 0, we say that our circuit will be a two states machine. When the circuit is in the state where carry = 0, the relationship between the inputs A and B and the output S is such that: if AB = 00 then S = 0; if AB = 01 then S = 1; if AB = 10 then S = 1; and if AB = 11 then S = 0. When the circuit is in the state where carry = 1, it also follows that: if AB = 00 then S = 1; if AB = 01 then S = 0; if AB = 10 then S = 0; and if AB = 11 then S = 1. We illustrate these relationships in the state diagram in Figure 1.


Figure 1: State transition diagram for serial adder FSM


To present the information in the state diagram in table form, we re-label the carry variable Z (Z for carry–out and z for carry–in) for convenience. We show the tabulated information in Table 1 below.
From a finite state machine analysis perspective, we say z is the present state of the machine because z is presently available as one of the inputs to the full adder; Z on the other hand is the next state because it is one of the variables we are solving for — given the inputs A, B and the present state (or the carry–in) z.


Given state of door q AB = 00 AB = 01 AB = 10 AB = 11 AB = 00 AB = 01 AB = 10 AB = 11
Next state Output
z Z S
0 0 0 0 1 0 1 1 0
1 0 1 1 1 1 0 0 1

Table 1: State transition table for serial adder FSM


At this point we can formulate the Boolean expressions for S and Z, where S is the sum output bit and Z is the carry output bit. Just in case you can’t see the Boolean functions in the Table1, we recast the transition table as two K–maps in Table 2 for your convenience.


K-map For Z
z/AB 00 01 10 11
0 0 0 0 1
1 0 1 1 1
K-map For S
z/AB 00 01 10 11
0 0 1 1 0
1 1 0 0 1

Table 2: K-maps for the next state variable Z and the output variable S

S = A xor symbol: a cirle with a plus sign inside B xor symbol: a cirle with a plus sign inside z
Z = A • B + A • z + B • z


The reason these Boolean expressions look similar to the full adder equation is because they are the full adder expression. Here z is the carry–in signal and Z is the carry–out signal. Since the carry–out of the full adder becomes the carry–in to the full adder on the next operation, we us a D flipflop to save the carry signal. We use a D flipflop because we need the data in Z to pass to z intact for the next operation. Any other flipflop will return some z that may or may not be equal to Z.

We show our finite state machine in Figure 2. It is a full adder whose carry-out signal Z returns as carry–in z for the next operation. A D–flipflop is used as the storage element. For those of you concerned with titles, the serial adder in Figure 2 is a Mealy–type finite state machine. It is a Mealy model because the output S is a function of both the present state z and the inputs A and B. (If it were a Moore model S would effectively be a function of the present state only.)


Figure 2: Serial Adder

Two Shift Registers is Better than Three

Beyond presenting the serial adder circuit, our main interactive digital system at the top of the page also demonstrates how we use two 4–bit shift registers to store the addends and the sum of the addition. Our configuration is a bit creative, so we will go through an example to show that two registers is as good as three — in fact better since we save on cost.

To add the two 4–bit numbers 1011 and 0010 using three shift registers would be simple enough: you would load 1011 into shift register A and 0010 into shift register B either in parallel or in series; and then register C would hold the sum 1101 after another four clock cycles.

However to add the two numbers using only two shift registers is a bit more elegant. We show the entire operation in Table 3 below. Initially we start with two empty shift registers: A = 0000 and B = 0000. Then, as the clock cycles we push the number 1011 into register A. Over the next four clock cycles, we kill two birds with one stone. We add 1011 to the 0000 in register B so that B becomes 1011. During the very same period we push 0010 into register A. Hence, after T8 A = 0010 and B = 1011. Finally, from time T9 to T12, we add 0010 to the number in register B, resulting in B = 1101, which is the sum of 0010 and 1011!

Clock cycle Serial
Input		 Register A Register B
T A3 A2 A1 A0 B3 B2 B1 B0
Initially 1 0 0 0 0 0 0 0 0
After T1 1 1 0 0 0 0 0 0 0
After T2 0 1 1 0 0 0 0 0 1
After T3 1 0 1 1 0 0 0 0 0
After T4 0 1 0 1 1 0 0 0 1
After T5 1 0 1 0 1 1 0 0 0
After T6 0 1 0 1 0 1 1 0 0
After T7 0 0 1 0 1 0 1 1 0
After T8 0 0 0 1 0 1 0 1 1
After T9 0 0 0 0 1 1 1 0 1
After T10 0 0 0 0 0 0 1 1 0
After T11 0 0 0 0 0 0 0 1 1
After T12 0 0 0 0 0 1 1 0 1

Table 3: Serial Adder Data Transfer

Alternate Design

Although it is often convenient to use D-flipflops in the synthesis of finite state machines, it is never necessary. We could very well use a JK flipflop to synthesize the specifications in Table 1. To do so we use the excitation table of the JK flipflop (Table 4) to map the JK inputs onto the serial adder state transition table (Table 1). We show the result in Table 5. Notice that q and Q in table 4 map onto z and Z in table 5.

q Q J K
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0

Table 4: JK flipflop excitation table



Present state Inputs Next state Output Flipflop inputs
z A B Z S J K
0 0 0 0 0 0 X
0 0 1 0 1 0 X
0 1 0 0 1 0 X
0 1 1 1 0 1 X
1 0 0 0 1 X 1
1 0 1 1 0 X 0
1 1 0 1 0 X 0
1 1 1 1 1 X 0

Table 5: JK State Table for Serial Adder

From the table we extract the output equation for S and the input equations for J and K. z of course is still the output of the flipflop.

S = A xor symbol: a cirle with a plus sign inside B xor symbol: a cirle with a plus sign inside z
J = A•B
K= ( A + B )’
The resulting circuit is in Figure 3. It is still a Mealy machine, as the output S still depends on both the state variable z and the output variables A and B.

Figure 3: Serial Adder with JK flipflop