A sequence detector is designed to detect precisely 3 digital inputs, with overlapping sequences detectable. For the sequence (1,0,1) and input data (1,1,0,1,0,0,1,1,0,1,0,1,1,0), what is the output of this detector?
1,1,0,0,0,0,1,1,0,1,0,0
0,1,0,0,0,0,0,1,0,1,0,0
0,1,0,0,0,0,0,1,0,1,1,0
0,1,0,0,0,0,0,0,1,0,0,0
ANSWER
The detector outputs 0,1,0,0,0,0,0,1,0,1,0,0, which is option (B). It finds 101 in the windows ending at the 4th, 10th and 12th input bits. The last two share a bit, so both count only because overlapping is allowed.
Official answer: BSource: Official answer key, GATE 2020 EE (IIT Delhi)
Output count. The detector looks at exactly 3 inputs at a time, so its first output appears once the 3rd bit has arrived. 14 input bits therefore give outputs. That matches the 12 entries in every option.
Overlap rule. Overlap is allowed, so the 3-bit window moves forward one bit at a time and a bit can belong to more than one detected sequence. At each clock the output is 1 exactly when the last three bits received are .
Label the input .
Slide the window (bits for to ): .
The windows ending at , and match . The windows ending at and share the bit , and only an overlapping detector counts both.
Output sequence: . This is option (B).
KEY IDEA
An overlapping 3-bit sequence detector works like a sliding window. After each new bit, compare the last three bits received with the target (here ) and output 1 on a match. With 14 inputs there are complete windows, so there are 12 outputs. A detected sequence may reuse bits from the previous detection.
WATCH OUT FOR
The usual mistake is to treat the detector as non-overlapping, resetting after the match that ends at . That misses the ending at , because it reuses , and gives , which is not an option. Another mistake is to put each 1 at the first bit of the window instead of the last, or to expect 14 outputs rather than one per complete 3-bit window.
From the GATE 2020 EE paper. Every question of this paper · Download the full paper · All 30 Sequential questions, with notes
