

THE SERIAL ADDER

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 
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.


S = A B 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 carryout 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
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 
Although it is often convenient to use Dflipflops 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 
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 
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 B z 
J  =  A•B 
K  =  ( A + B )’ 