A question about mathematical algorithm in Digital Systems.

Question

My question is related to math technique that must be used to solve a question in Digital Systems subject. and I know Its not so related to this forum, but I couldn't find another related place in which I can ask such questions (I will be glad if u suggest any).

For those who have learned this subject: I want to build a machine (Which is type Mealy, if that helps clarifying), with one input and one output that: $$ \text{gives "1" only if at least 2 from last 3 input digits were "1"} $$ I know that it must be 4 States, (A,B,C,D). How can I name these states?, and what are they? for example: A: initial state that remembers that last two 3 digits were zero.

Important note: we suggest that before getting any input, the machine had received zero values.

here is an example for how the machine works in general:

Answer 1

You need to remember the previous two bits. There are four choices for what the previous two bits were, so if you know you can get by with four states those are a likely way to define (and name) them. The names do not actually matter except for communicating to another human how your machine works. Your machine needs to define, given a state and an input bit, a state to go to and an output bit. As you say, state A could be that the last two bits were both zeros. Now if you get a zero, what is the output and what were the last two bits? If you get a one, what is the output and what were the last two bits? Do this for all the previous two bit states and you are done.

Answer 2

Away from the theories of the finite state machines, you can easily implement this functionality using a 3-bits shift register (SR). Assuming:

• the bits in the register are labeled $b_2, b_1$ and $b_0$,
• the serial in of the SR is connected to the most significant bit (b_2), and
• it is initially all zeros.

Then, the output you need is simply Majority($b_2,b_1,b_0$). Where the majority function outputs 1 if and only if the majority of the inputs are 1's.