Help with sequential circuit and sequence detector

[DanteOlivieri]

Hello everyone,
This is one of the exercises from last year's exam in my university, and I would appreciate it if someone could help me.

Design a sequential circuit with one input x and two outputs z1 and z0. The exit z1 must equal 1 if the last three input bits contain at least two 0s, while z0 must be 1 if the last 3 bits are equal. Do not consider overlapping. Use a ROM for the combinational part and a JK-FF for the MSB. Draw the obtained circuit.

Example: (i have added the '-' just to display it correctly in column)
x - 10100000111
z1 00010010000
z0 00000010001

I'm really not understanding what they mean by "Use a ROM for the combinational part and a JK-FF for the MSB."

I have already done the state diagram, the state table and, since I didn't know what to do with the flip flops (I don't know what they mean by "use a JK-FF for the MSB"), I also wrote the expressions for the inputs of the 3 JK flip flops (J2, K2, J1, K1, J0, K0, using the JK-FF excitation table) and the outputs (z1, z0).
I've used 3 JK-FF's because I'm getting 7 states from the initial analysis and I couldn't reduce anything.
At this point, I'm only missing the circuit drawing, but I'm not doing that for now because I'm not sure if I did everything correctly, and I'm also confused on how to use a ROM here.

Help appreciated!

 

[kaz1]

Problem simplifies to (if x is parallel bits):

if x(2 downto 0) /= '011' then
z1 = '1';
else
z1 <= '0';
end if;

if x(2 downto 0) = '000' or x(2 downto 0) = "111" then
z0 = '1';
else
z0 <= '0';
end if;

as two other requests like rom or JK I got no idea what the professor is after.

 

[betwixt]

Just a guess: the use of a ROM implies some of the data bits must be in parallel to form an address. Perhaps the JK are wired as a counter to make the ROM address and the output is taken from the ROM data. I'm not sure what they mean by "Do not consider overlapping" though.

Brian.

 

[DanteOlivieri]

I'm not sure what they mean by "Do not consider overlapping" though.

Overlapping basically is considering previous bits when doing the initial analysis

Look at this example:
the output z is 1 when we detect 3 consecutive zero's in the input x
x: 1110100001
- without overlapping:
z: 0000000100

- with overlapping:
z: 0000000110

In positions 5-8 we have 4 consecutive zero's.
When we don't consider overlapping, when we detect the third consecutive zero we go back checking from the initial state, where we still have to find the first 0 in the sequence. So if we have "0000", the output will be "0010", because we detect the third zero, then we're in the last element of the input where all the previous bits don't count anymore. If we had "000000", the output would be "001001".

When we consider overlapping, when we detect the third consecutive zero the output still becomes 1, but since we are considering the previous bits too, when we move to the next position the output will be 1 again because we have another zero. If we had "000000", the output would be "001111"

 

[FvM]

If you take post #1 spec literally, there's no room for "overlapping" considerations. You'll process the three last inputs bits in every clock cycle. No other conditions
z1=1 if x in {001, 010, 100, 000} else =0

I would prefer a result representation that shows z in the next clock cycle (registered outputs), but the excercise problem is unclear also in this point. Regarding FF utilization, you'll need at least 2 FFs to remember previous input states. z0 and z1 can be registered or combinational. The term MSB seems to be unrelated to the problem (as far as posted).

 

[D.A.(Tony)Stewart]

A JK FF can do divide by 2 so if MSB was meant to mean "most significant bit" we usually say in lower case "msb". If trailing bit or 1st is msb then using a JK FF has certain outputs like JK=1 on 1st and 3rd bit toggles output. (1/2f) which isn't really useful but satisfies this question. XORing the toggled output with the previous output tells you '1x1' was detected.

The ROM stores the logical values for Z0, Z1 using the 3 bit inputs

 

[BradtheRad]

I think 'don't consider overlapping' means you must start a new count to 3 after you already found one group of 3 equal bits.
In other words 4 or 5 equal bits together should not be considered as two occurrences of the target outcome.

However 6 bits in a row can be called two occurrences.

 

[D.A.(Tony)Stewart]

then the "word" consider is a requirement, not an option to neglect for simplicity. It now adds complexity to have a 3bit sequential counter.

Give the examiner -1 pt for ambiguous specs.
define endian big or little -1 ... is msb 1st or last?

Better to say examine each sequence as a 3bit word FIFO msb 1st

 

[D.A.(Tony)Stewart]

x 10100000111
z1 00010010000
z0 00000010001

One z0 state=1 seems in error. Why7?

 

[FvM]

Apparently wrong assumption about input bit grouping. It seems to start dynamically with the first hit and is reset if the next group of three has both z0 and z1 criterion false.

The conditions that need to be applied to make the example work are arbitrary and in no way covered by the original problem specification. The implementation requirements are incomplete, it needs 4 FF, two for previous input register and at least two for state register.

 

[Akanimo]

Hi,

Verify this:
z1[n]=0 if z1[n-1]=1 or z1[n-2]=1 else z1[n]=Q[n], where Q is the output of the J-K flipflop. So the J-K flipflop would have an active-high RESET pin that is derived as RESET[n]=(z1[n-1] OR z1[n-2]). If this is verified correct, then we can proceed to derive what feeds the J and K inputs. J and K inputs can then be fed by ROM LUT whose selected address depends on x[n], x[n-1], x[n-2] or so.

 

[Akanimo]

Hi,

Verify this:
z1[n]=0 if z1[n-1]=1 or z1[n-2]=1 else z1[n]=Q[n], where Q is the output of the J-K flipflop. So the J-K flipflop would have an active-high RESET pin that is derived as RESET[n]=(z1[n-1] OR z1[n-2]). If this is verified correct, then we can proceed to derive what feeds the J and K inputs. J and K inputs can then be fed by ROM LUT whose selected address depends on x[n], x[n-1], x[n-2] or so.

I didn't present that well enough. So please find the update below.

Update:
z1[n+1]=0 if z1[n]=1 or z1[n-1]=1 else z1[n+1]=Q[n+1], where Q is the output of the J-K flipflop. So the J-K flipflop would have an active-high RESET signal that is derived as RESET[n]=(z1[n] OR z1[n-1]).

If the above is verified correct, then we can proceed to derive what feeds the J and K inputs. J and K inputs can then be fed from the ROM LUT whose selected address depends on x[n], x[n-1], x[n-2] or so.

However, this might provide result in a subsequent clock cycle, and, as have been pointed out, you may need to look again at the "-" that you inserted.

 

[Akanimo]

I didn't present that well enough. So please find the update below.

Update:
z1[n+1]=0 if z1[n]=1 or z1[n-1]=1 else z1[n+1]=Q[n+1], where Q is the output of the J-K flipflop. So the J-K flipflop would have an active-high RESET signal that is derived as RESET[n]=(z1[n] OR z1[n-1]).

If the above is verified correct, then we can proceed to derive what feeds the J and K inputs. J and K inputs can then be fed from the ROM LUT whose selected address depends on x[n], x[n-1], x[n-2] or so.

However, this might provide result in a subsequent clock cycle, and, as have been pointed out, you may need to look again at the "-" that you inserted.

Looking back at the question, considering that the question stipulates that you use a ROM for the combinational part, "RESET[n]=(z1[n] OR z1[n-1])" also has to be implemented in ROM. This would mean that the ROM address will be 5 bits, namely, x[n-2], x[n-1], x[n], z1[n-1] and z[n]. The ROM data will be two bits J1 and K1. J1 and K1 will feed the J and K inputs, respectively, of the J-K FF that generates z1. At ROM locations where z1[n]=1, make J1=0 and K1=1. This will make Q[n+1]=0. Also at ROM locations where z1[n-1]=1, make J1=0 and K1=1 so that Q[n+1]=0. Notice that the event that z1[n]=1 and z1[n-1]=1 will never occur together, so there is no need to bother about the content of those ROM locations. Those are effectively don't-care conditions. At ROM locations where z1[n]=0 and z1[n-1]=0 and x[n-2], x[n-1] and x[n] respectively equal 000, 001, 010 or 100, make J1=1 and K1=0 so that Q[n+1]=1.

Note: doing all of this, MSB is z1 is assumed.

For z0, I couldn't find any constraint in the question in its implementation. So, using combinational logic to implement z0[n+1]=((x[n-2] AND x[n-1] AND x[n]) OR NOT(x[n-2] AND x[n-1] AND x[n])) will do. However, if the question meant to say that z0 should also be implemented using a J-K FF, then the ROM data would have to be four bits, the additional two bits being J0 and K0. J0 and K0 will then feed the J and K inputs, respectively, of the J-K FF that generates z0. J0=0 and K0=1 should be stored at all ROM locations, except locations where the ROM addresses where [x[n-2] x[n-1] x[n] z1[n-1] z[n]]=[00000] and [x[n-2] x[n-1] x[n] z1[n-1] z[n]]=[11100] where the stored data should be J0=1 and K0=0. The don't-care conditions still hold at ROM addresses where z1[n]=1 and z1[n-1]=1.

I hope this helps.
Cheers!

 

[FvM]

Using previous z1 to take account of "overlap" condition isn't sufficient, previous z0 has to be evaluated as well. A more straightforward solution is a state machine with a counter that is reset on z0 or z1 match. It has three states, can be represented by minimal two FF. Unregistered z0 and z1 outputs correspond to Mealy machine.

 

[Akanimo]

Thank you FvM. Really good catch. I didn't see that there could be z0=1 at any instance where z1=0. A simple simulation (which I didn't do because I expected it to be done by the OP) would have caught that. I'm following the requirements to implement the system using ROM lookup. I only allowed extra registers because they are inevitable. So I'd quickly correct the error as follows:

z0[n] and z0[n-1] would have to be added to the ROM address bits. This would result in a 7-bit address. ROM data would remain four bits, namely, J1, K1, J0 and K0.

J0=0 and K0=1 should be stored at all ROM locations, except locations where the ROM address [x[n-2] x[n-1] x[n] z1[n-1] z1[n] z0[n-1] z0[n]]=[000--00] and [x[n-2] x[n-1] x[n] z1[n-1] z1[n] z0[n-1] z0[n]]=[111--00] where the stored data should be J0=1 and K0=0 (where "-" represents don't-care condition). Also, don't-care condition exists at ROM addresses where z0[n]=1 and z0[n-1]=1 because they cannot both have the value 1.

J1=0 and K1=1 should be stored at all ROM locations, except locations where the ROM address [x[n-2] x[n-1] x[n] z1[n-1] z1[n] z0[n-1] z0[n]]=[00000--], [00100--],[01000--] or [10000--] where the stored data should be J1=1 and K1=0. Again, don't-care condition exists at ROM addresses where z1[n]=1 and z1[n-1]=1 because they cannot both occur.

Also, I just realized that I did not add a delay to the expression of z0 in my first z0 design instance for combinational z0. Therefore z0[n+1]=z^-1((x[n-2] AND x[n-1] AND x[n]) OR NOT(x[n-2] AND x[n-1] AND x[n]))

--- Updated Dec 27, 2023 ---

And yes, the system as implemented is a Mealy machine and can be modified slightly to produce z0 and z1 in the same clock cycle. I can still post that solution later if the OP insists.

 

[D.A.(Tony)Stewart]

Better specs would have made it easier. -10 examiner

 

[Akanimo]

In addition to errors by the examiner, by adding '-' and then telling us it was added to display the bits correctly in columns, the OP also casted doubt on which clock cycle the outputs are desired, present or next. I believe a snippet of the question as presented by the examiner should have been posted instead.

But it's like that some times. If you have noticed in the expression z0[n+1]=Z^-1((x[n-2] AND x[n-1] AND x[n]) OR NOT(x[n-2] AND x[n-1] AND x[n])), I borrowed the notation "Z^-1" to indicate that ((x[n-2] AND x[n-1] AND x[n]) OR NOT(x[n-2] AND x[n-1] AND x[n])) will have to be delayed for one clock cycle. Then I'm hoping that it would be understood that its only purpose in the expression is to indicate that and nothing else.

It's a trivial task nonetheless.

The OP seems to be having a holiday this season. So I'll go ahead and post the modification so the output is in the current clock cycle rather than the next.

--- Updated Dec 28, 2023 ---

In the solution that's presented, the outputs, z0 and z1, were taken at the outputs of the J-K FFs. For this design case, the Q outputs are delayed copies of the J inputs. So taking the outputs z0 at J0 and z1 at J1 removes the delay. Therefore, instead of the ROM address being [x[n-2] x[n-1] x[n] z1[n-1] z1[n] z0[n-1] z0[n]], it will be [x[n-2] x[n-1] x[n] Q1[n-1] Q1[n] Q0[n-1] Q0[n]]. The content of the ROM does not change. And we have z0[n]=J0 and z1[n]=J1.

So what we have done is that we have provided solution for both cases: one for delayed output, another for the non-delayed output. We have also provided solution for a case where the z0 output is implemented with combinational logic outside of the ROM.

I suggest that the task to draw the circuit be undertaken by the OP to help him understand the implementation. We are still available where there are questions about the implementation.

Cheers!