How Do You Design a Moore State Machine for Two's Complement Operations?

[electroguy02]

Homework Statement

Can someone check my work?

[...] Receiving DATA in binary. The string length of each word is unknown. You are told that each word, demarcated by SYNC signals, is a two's complement number.

Your task is to 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. Your circuit should have two inputs: DATA and SYNC.

Homework Equations

If the DATA string 10011100011010 is given (where the first digit is the first input), along with the SYNC string 10000010000000, the output should be 11100000010101.

The LSB is the DATA bit that shows up when SYNC = 1.

Short-cut rule for performing a two's complement operation on a string of data:

"Starting with the LSB and moving toward the MSB, transcribe all zeros until you reach the first '1', transcribe that '1' then complement every bit after (more significant than) that."

The Attempt at a Solution

I have already made a working Mealy machine with this functional specification. I'm just having trouble on the Moore machine. SYNC is equal to 1 for only one positive-edge clock pulse.

For the Moore machine, there are three states:

[State 00]: Only zeros are received when SYNC = 1. Output is 0.
[State 01]: First one received when SYNC = 1. Also, zeros after first one is received (and SYNC = 0). Output is 1.
[State 10]: 1 received after first one is received. Output is 0.

I'm trying to use D flip-flops for this, so I made the following state transition table:

Inputs Present State Next State Output D flip-flops
SYNC DATA | A B | A+ B+ | z | D_A D_B
0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 1 0 0 1 0 0 1
0 0 1 1 X X 0 1 1
0 1 0 0 0 1 0 0 1
0 1 0 1 1 0 1 1 0
0 1 1 0 1 0 0 1 0
0 1 1 1 X X 0 1 1
1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0
1 0 1 0 0 0 0 0 0
1 0 1 1 X X 0 1 1
1 1 0 0 0 1 0 0 1
1 1 0 1 0 1 1 0 1
1 1 1 0 0 1 0 0 1
1 1 1 1 X X 0 1 1

I did Karnaugh maps for the D_A, D_B, and z, and this is what I got (S=SYNC, D=DATA. S' means NOT SYNC):

D_A: AB+S'DB+S'DA
D_B: SD'+D'B+D'A+AB+S'DA'B'
z : A'B

I'm pretty sure of the Next State and z columns of my table; I've checked it against my teacher's answer. But somehow, the equations aren't working for me. Can you please check my work? Thanks in advance.

 

[berkeman]

Homework Statement

Can someone check my work?

[...] Receiving DATA in binary. The string length of each word is unknown. You are told that each word, demarcated by SYNC signals, is a two's complement number.

Your task is to 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. Your circuit should have two inputs: DATA and SYNC.

Homework Equations

If the DATA string 10011100011010 is given (where the first digit is the first input), along with the SYNC string 10000010000000, the output should be 11100000010101.

The LSB is the DATA bit that shows up when SYNC = 1.

Short-cut rule for performing a two's complement operation on a string of data:

"Starting with the LSB and moving toward the MSB, transcribe all zeros until you reach the first '1', transcribe that '1' then complement every bit after (more significant than) that."

The Attempt at a Solution

I have already made a working Mealy machine with this functional specification. I'm just having trouble on the Moore machine. SYNC is equal to 1 for only one positive-edge clock pulse.

For the Moore machine, there are three states:

[State 00]: Only zeros are received when SYNC = 1. Output is 0.
[State 01]: First one received when SYNC = 1. Also, zeros after first one is received (and SYNC = 0). Output is 1.
[State 10]: 1 received after first one is received. Output is 0.

I'm trying to use D flip-flops for this, so I made the following state transition table:

Inputs Present State Next State Output D flip-flops
SYNC DATA | A B | A+ B+ | z | D_A D_B
0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 1 0 0 1 0 0 1
0 0 1 1 X X 0 1 1
0 1 0 0 0 1 0 0 1
0 1 0 1 1 0 1 1 0
0 1 1 0 1 0 0 1 0
0 1 1 1 X X 0 1 1
1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0
1 0 1 0 0 0 0 0 0
1 0 1 1 X X 0 1 1
1 1 0 0 0 1 0 0 1
1 1 0 1 0 1 1 0 1
1 1 1 0 0 1 0 0 1
1 1 1 1 X X 0 1 1

I did Karnaugh maps for the D_A, D_B, and z, and this is what I got (S=SYNC, D=DATA. S' means NOT SYNC):

D_A: AB+S'DB+S'DA
D_B: SD'+D'B+D'A+AB+S'DA'B'
z : A'B

I'm pretty sure of the Next State and z columns of my table; I've checked it against my teacher's answer. But somehow, the equations aren't working for me. Can you please check my work? Thanks in advance.

Well, a few thoughts (I didn't go through your tables in detail yet).

1) You should always have a binary number of states in your state machine. Unused states can just flow back to the reset/initial state, but you definitely need to not have any illegal or dangling states. That's not good design practice. So if you think you can do the state machine control circuit with 3 states, add in the 4th state, and have it always flow back to your idle or starting state.

2) I'm a bit confused by the example string given, and where you say "The LSB is the DATA bit that shows up when SYNC = 1." If I space out the example strings to make them more readable, then it looks like this:

1 001110 0011010 Input Data
1 000001 0000000 SYNC
1 110000 0010101 Output Data

Which looks like there is an initial 1-bit word, then a 6-bit word, and then an unterminated word of undefined length which is not getting inverted bit-by-bit, which the 2's compliment should require. Sorry if I'm completely off base here.

3) To do the 2's complement, you will invert each bit of the word, until the last bit is recognzed, where you do the inversion, but add back in a 1. That addition can force carrys to propagate up the bits of the word until a 0 is encountered. So it seems like you would need to store the output data string until you get the SYNC, then do the addition and any carrys, and then shift out that output string. Is there some way to do this with only 1 bit of memory? It seems like in addition to the state machine FFs, you need to know the max word length and add that many FFs in for temporary memory storage...?