How do I solve this on paper? For logisim assignment? I$\text{'}$m getting it wrong each time.

For our first lab assignment, you will apply what we have learned so far about finite state machines and sequential logic design using state diagrams and state tables. In this assignment, you will derive the next$-$state and output logic of a pattern detector which can detect the pattern $101$ in an input bit stream. $($This input stream is similar to the serial input stream depicted on Page $6$ of the "Finite State Machines, Part One" lecture notes; as shown there, the input arrives one bit at a time serially, as opposed to multiple bits in parallel.$)$ The input value X represents the most recent bit from the input stream; the resulting output Z should be a $1$ if the last digit of a new occurrence of the pattern was found in the stream, and a $0$ otherwise. Your design should allow for bit overlaps.

For example, if the input stream is $...$

$0010101011101$

$...$ then the corresponding output stream should be $...$

$0000101010001$

$($Hint: For convenience, use the same Q$1$Q$0$ state coding values seen in previous assignments and in the lecture notes: Q$1$Q$0=00$ means S$0$; Q$1$Q$0=01$ means S$1$; Q$1$Q$0=10$ means S$2$; and Q$1$Q$0=11$ means S$3.$ Note that four states are needed to respectively represent zero, one, two, or three matching digits of the pattern. Arrival in state S$3,$ then, indicates that a complete occurrence of the pattern was found.$)$

Completing This Assignment

Begin by deriving a state diagram for this pattern detector logic; next, from this diagram, derive a state table. Your table should include the Q$1$Q$0$ values for the present state, the input value X$,$ the new Q$1$Q$0$ values for the next state$$here$,$ called Q$1+$ and Q$0+$and the output value Z$.$

Once you have a complete state table, the next step is to design logic circuits for the next$-$state values Q$1+$ and Q$0+$ as well as the output Z$.$ Implement this logic within the corresponding subcircuits in the attached Logisim circuit file.

Finally, complete the "test harness" shown in the main circuit by adding your Q$1+,$ Q$0+,$ and Z subcircuits. Note that several components are already provided for you, including a ROM containing example input stream data, a counter $($in the upper$-$left$)$ to generate the ROM addresses which will produce the input stream data, and a register $($in the center$-$left$)$ to hold the current state of the machine. You will also find a stack of output terminals on the right side of the circuit, as well as two splitters, one from the register to provide the current$-$state inputs, and another to connect the next$-$state values to the output terminals. $($Note that the next$-$state outputs are also connected to the register input so that the new state is saved to the register.$)$ Remember that bit $0$ of the splitters correspond to the Q$0$ and Q$0+$ signals, and that bit $1$ of the splitters correspond to the Q$1$ and Q$1+$ signals. Add your subcircuits into the empty area near the center of the main circuit, and provide the necessary interconnections by adding wires.