G7.4.1 Detect 1101 with Overlap

MediumImplementIcarus Verilog + Yosys · serverReview the topic

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

SignalWidthRole
xs24input of each check
Full specification
The module (keep the name and the ports)
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
RuleDetail
MatchThe last four bits received, oldest first, are 1, 1, 0, 1. Bits before reset do not count.
OverlapMatches may share bits: 1101101 holds two.
Timingx 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

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

One Match, Then Zeros

Input
x = 011010000000000000000000 (cycle 0 first)
Expected 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.

Run samples executes all 3 public checks. Check all tests runs 22 checks on the server.

Icarus Verilog + Yosys · server