# Serial 2's Complementer with One Input and One Output

I know this question has been asked and there already are answers to this question on the Internet. I just want to ask you where I am wrong in my way of thinking.

When I first saw this question, the shortcut -keep copying until you see a 1 and then complement the rest- hadn't occurred to me. So I thought I would just complement the bit, add 1 to it and if I get a carry then I would keep it in the flip flop to add it to the next bit coming from the input.

Meaning that,

In State-0

if the input is 0 then I should output "0" (after complementing) and keep that carry "1" in the flip-flop so flip-flop goes from state-0 to state-1.

If the input is 1 then I should output "1" but the flip-flop remains in the same state which is state-0.

In State-1

if the input is 0 then I should output "1" -since 2's complement would be 10 and I have a carry "1" in the flip-flop- I would get another carry so the state remains the same.

If the input is 1 then I should output "0" and the flip-flop remains in the same state as well.

Here is my state diagram : +---------+-------+-------+--------+
| Present |       | Next  |        |
| State   | Input | State | Output |
|    A    |   x   |   A   |   y    |
|    0    |   0   |   1   |   0    |
|    0    |   1   |   0   |   1    |
|    1    |   0   |   1   |   1    |
|    1    |   1   |   1   |   0    |
+---------+-------+-------+--------+



After getting the equations from the table above. I get a circuit like so: simulate this circuit – Schematic created using CircuitLab

According to the State Table given by you,

S(t + 1) = X' + S(t)

Y = X + S(t).

But, in this circuit diagram Y turns out to be Y = X xor S(t).

Also according to your State Diagram Y turns out to be Y = X xor S(t).

So either the State Table is wrong and the State Diagram and the circuit is correct,

Or

State Table is correct and the State Diagram and the circuit is wrong,

I just figured out the problem and here I am explaining. If you were trying to solve this problem the same way I was trying (without thinking about the shortcut like "output the same value till you see a bit of value 1 and then complement others in the string.") then we will have 2 states.

State-1 (Initial State - Carry-1 State)

Which we have a carry-1 to add to the least significant bit of the string after complementing. Because that's what you would normally do when you are trying to get the 2's complement of a bit string. You just complement the entire string and add 1 to the least significant bit.

You could name this state, State-0 as well but I am just naming it State-1 not to get confused. So that I know I have a carry 1 in the flip-flop.

State-0 (Which signifies that you don't have any carry left)

This state means that you have no carry left in hand. So you just complement the bit at the input.

Let's inspect what possibilities we can get when trying to get the 2's complement of a bit string.

• In the initial state you could get a 1 whose 1's complement is 0 and with a carry in hand equals to 1. Since that sum doesn't generate a carry. You have no carry left in hand and you go to State-0.
• Again in the initial state you could get a 0 whose 1's complement is 1 and with a carry in hand this sum equals to 10, which means you will again have a carry in hand and therefore remain in the same state which is State-1. But the output will be 0.
• In State-0 you could get a 0 again and since you don't have any carry in hand you just output the 1's complement of 0 which is equal to 1.
• Again in State-0 you could have 1 at the input and since you don't have any carry your output would be equal to 0.

Having that said, we draw a state table as follows :

+---------+-------+-------+--------+
| Present |       | Next  |        |
| State   | Input | State | Output |
|    A    |   x   |   A   |   y    |
|    1    |   0   |   1   |   0    |
|    1    |   1   |   0   |   1    |
|    0    |   0   |   0   |   1    |
|    0    |   1   |   0   |   0    |
+---------+-------+-------+--------+


Looking at the table, we get a state diagram like so : Then we get this circuit : simulate this circuit – Schematic created using CircuitLab