Design a Mealy detector that flags every 1101 in a serial stream, overlapping matches included, in the cycle of the last bit.
Hardware context: A serial receiver that marks each block with a short bit pattern, where marks may share bits. Design a Mealy detector for 1101 that counts overlapping marks.
A serial receiver marks the start of each block with the bits 1101. Blocks can be short, so the last 1 of one mark may be the first 1 of the next. Every mark must be flagged.
This is an Implement problem. Complete det1101 as a Mealy machine: z is 1 in the same cycle as the last bit of 1101. The starter has the states and the forward arcs only.
The check feeds streams of 24 bits after a reset and compares z in every cycle with a model. The design must synthesize with no latches.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
xs | 24 | input of each check |
Full specification
module det1101 (
input logic clk,
input logic rst, // synchronous reset, active high: nothing seen
input logic x, // one bit per clock cycle
output logic z // 1 in the cycle of the last bit of 1101
);
...
endmodule
| Rule | Detail |
|---|---|
| Match | The last four bits received, oldest first, are 1, 1, 0, 1. Bits before reset do not count. |
| Overlap | Matches may share bits: 1101101 holds two. |
| Timing | x is set at the start of a cycle. z must be 1 in the middle of that same cycle, and 0 in every other cycle. |
Examples
Example 1
One Match, Then Zeros- Input
x = 011010000000000000000000 (cycle 0 first)
- Output
z_cycles = {4}
Bits 1 to 4 are 1101, so z is 1 in cycle 4, the cycle of the last bit, and nowhere else.
Example 2
Two Matches That Share a 1- Input
x = 110110100000000000000000 (cycle 0 first)
- Output
z_cycles = {3, 6}
The 1 of cycle 3 ends the first match and starts the second, which ends in cycle 6.
Example 3
A Third 1 Before the 0- Input
x = 011101000000000000000000 (cycle 0 first)
- Output
z_cycles = {5}
After 111 the detector must still hold "11": 1110 then 1 completes a match in cycle 4.
Constraints and Contract
- All inputs are known 0/1 values and change only between edges.
- Keep the module name and the ports.
Hints
Hint 1
Each state stands for the prefix of 1101 seen so far. For each state and each bit, append the bit and keep the longest ending that still starts 1101.
Hint 2
Three 1s in a row still end in 11. And after a match, its last 1 is the start of a new one.
Hint 3
z belongs to the arc that completes the match, so set it in the combinational block from the state and x.
What the grader checks: Eight directed and fourteen seeded streams of 24 bits after a reset. In every cycle z is compared with a JavaScript model that flags each 1101. Any design that behaves the same passes. Synthesis must report no latches.
The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.
22 checks on Icarus Verilog + Yosys · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 2 steps and the final capstone