In LogicWorks, I have to create a finite sequential machine using this criteria:

"Develop a synchronous sequential machine which examines the received data as input and produces as output the negative of the input number by performing the two's complement operation on the incoming data."

Circuit should have 2 inputs: DATA & SYNC
Circuit should have 1 output: two's complement of data


Help on getting started would be greatly appreciated!

 

This is a reasonably lucid explanation of the process - http://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html.

 

I understand how 2's complement works, I just don't understand how to build a 2's complement Mealy machine in LogicWorks with 2 inputs and 1 output (I'll probably use D or JK flip-flops).

 

You have to know how many bits you're going to have, or is the number of bits for which the complement needs to be computed going to change? Are the bits coming in least significant bit or most significant bit first? Does the output have to be generated as the bits come in or can you receive a slug of bits, compute the complement, and output the result? Somebody really needs to learn to write better specifications -- too many unanswered questions and ill-defined requirements.

 

I apologize for the ambiguity of my post.

# of bits all depends on the input SYNC. When SYNC is high, this means a new number is starting. The LSB is entered first through the DATA input. So for example:

SYNC: 1 0 0 0 0 0 1 0 0 0 0 0 0 0...
DATA: 1 0 0 1 1 1 0 0 0 1 1 0 1 0...
Output: 1 1 1 0 0 0 0 0 0 1 0 1 0 1...

The inputs are entered one at a time, not all at once. There is also a clock attached to this... It should be relatively easy, but I'm just not getting Mealy machines... Oh and, we have to use D or JK flip-flops.

 

So now we have a new problem. It would seem that this machine is required to predict the final result before all the bits have been received. I'm going to out on a limb and say I think that this assignment defined the way you have defined it is quite plainly impossible. This is not about Mealy machines it is about a set of requirements and specifications that make sense.

There are many other problems with this specification but lets concentrate on precognition and the length of a maximum sequence. It comes back to the realm of possibility if the output can be delayed until the next sysnc pulse so you know how long the data is.

This is why we used ones complement Arithmetic in the serial arithmetic logic units that we designed with TTL parts in the early 1970's. The complementer is a simple combinatorial circuit, no memory required, and a ones complement ALU only needs an end around carry to complete the process.

 

While I realize this is an old thread and reviving them is usually considered a bad thing to do, I felt compelled to answer for the sake of newcomers discovering this thread as I just did. While I am sure the OP has long ago found a satisfactory answer, the reply by Papabravo needs some rebuttal.

I'm going to out on a limb and say I think that this assignment defined the way you have defined it is quite plainly impossible.

Saying it is 'quite plainly impossible' only signifies a lack of understanding of the problem. This is most definitely a solvable problem, and quite easily doable with both Mealy and Moore FSMs. Without giving away the 'answer' (so as not to provide a cheat for EE students that have this or a similar problem to solve in their class), I will just give the following hint: Use the short-cut method to finding 2's complement on a serial bitstream. This method states, starting with SYNC=1, with every CLOCK pulse, received 0's remain 0's until the first 1 is received. That first 1 remains a 1, then every bit afterward is complemented until the next SYNC=1. Using this method, the DATA input can be any number of bits long in frames bounded by SYNC. Another hint: Use JK flip flops.

So, using the first SYNC frame of the OP's given example data:
SYNC: 1 0 0 0 0 0
DATA: 1 0 0 1 1 1
The first bit is not a zero, it is a one, so output a one. Now complement each bit as it comes in until the next SYNC=1.
Output: 1 1 1 0 0 0

For the second SYNC frame:
SYNC: 1 0 0 0 0 0 0 0
DATA: 0 0 0 1 1 0 1 0
The first three bits as they come in are zero, so output the zeros. The next bit received is a one, so output the one, then complement the rest as they are received until the next SYNC=1:
Output: 0 0 0 1 0 1 0 1

 

Checking the math. Understanding that the bitstreams are LSB-first, then if you look at the first data frame, 100111, reoriented MSB-first, you get the number 111001. Performing standard 2's complement on this, the 1's complement is 000110, and then converting to 2's complement by adding 1, results in 000111. Reorienting this result to LSB-first gives 111000, which matches the output of the first frame in the above post.

Doing the same for the second frame: LSB-first = 00011010. Reorienting to MSB-first = 01011000. Taking 1's complement = 10100111. Adding 1 = 10101000. Reorienting to LSB-first = 00010101, which matches the output of the second frame in the above post.

This proves that the method described is at least one way to solve the problem as it is given.

 

Since the original post has aged out, I don't think there's a danger of spoiling the homework problem.

I would do the state machine this way:

As bits come in (LSB first), pass them to the output unchanged.

If a '1' bit is seen, on the NEXT bit and all following, invert input bits to output (and XOR gate would be handy here).

The Sync signal immediately resets to passing non-inverted bits.

 

The basis for WHY this works is very straightforward.

We know that if we had wanted to take the one's complement that we would simply invert all the bits, which would mean that our machine would be trivial.

All our machine really needs to do is add one to an lsb-first serial bit stream (in which we have inverted each bit beforehand).

So now we just need to ask what the practical effect is of adding one to a binary value?

If the lsb is a 1 we invert it and perform a carry. If it is a 0 then we invert it and do not perform a carry. This can be generalized to if we have a carry in then we invert the bit and the carry out is equal to the original value of the bit. If we do not have a carry in, then we do not invert the bit and do not have a carry out.

Taking into account that we are taking the one's comp of the bitstream at the same time, we need to tweak this to the following:

If we have a carry-in, then we preserve the bit value and the carry-out is the opposite of the original bit value. If we do not have a carry-in, then the output is simply the inverse of the bit value and there is no carry-out.

We start off with a carry-in (as indicated by the sync bit), so we pass all bits unchanged up to and including the first 1 bit and invert all bits after that.

BTW: I think that this was a reasonable necropost.