Designing a sequence detector of a sequence having 100 bits

[FvM]

The initial question is for a sequence detector, means one bit per clock cycle. This should be possible without pipelining.

 

[std_match]

The initial question is for a sequence detector, means one bit per clock cycle. This should be possible without pipelining.

I assume that it isn't known in advance which bit is the first in the sequence.
For a simple implementation you then need to compare the 100 last received bits every clock cycle. A 100-bit comparator can be difficult without pipelining for high clock frequencies.
If you want to compare only one bit per clock cycle you need a very complex state machine, similar to the ones generated by flex/bison (yacc/lex) in the software world.

 

[FvM]

I assume that it isn't known in advance which bit is the first in the sequence.

O.k. I see. Problem is, you can assume anything with vague question like this.

 

[fragnen]

I assume that it isn't known in advance which bit is the first in the sequence.
For a simple implementation you then need to compare the 100 last received bits every clock cycle. A 100-bit comparator can be difficult without pipelining for high clock frequencies.
If you want to compare only one bit per clock cycle you need a very complex state machine, similar to the ones generated by flex/bison (yacc/lex) in the software world.

Bits are coming in sequentially every clock cycle.

Can you please elaborate what you are thinking and how knowing which bit is coming first will help?

Can you please also state what you are stating by stating comparing the 100 last bits received in one clock cycle?

 

[std_match]

Bits are coming in sequentially every clock cycle.

Can you please elaborate what you are thinking and how knowing which bit is coming first will help?

Can you please also state what you are stating by stating comparing the 100 last bits received in one clock cycle?

If you know which bit is the first, you know the "wanted" value for each incoming bit, so you only have to check the current bit. The previous bits are already "approved". As soon as one incoming bit is "wrong", you know that the sequence isn't the wanted, so you can just wait for the next "first bit".

If you don't know which bit is the first, you must assume that every incoming bit can be the last bit in the 100-bit sequence.
To check this, the 100 last received bits must be compared with the wanted sequence, for each incoming bit (except for the first 99 received bits, of course).

 

[fragnen]

If you know which bit is the first, you know the "wanted" value for each incoming bit, so you only have to check the current bit. The previous bits are already "approved". As soon as one incoming bit is "wrong", you know that the sequence isn't the wanted, so you can just wait for the next "first bit".

If you don't know which bit is the first, you must assume that every incoming bit can be the last bit in the 100-bit sequence.
To check this, the 100 last received bits must be compared with the wanted sequence, for each incoming bit (except for the first 99 received bits, of course).

The sequence will be like 10110110010........0110.
The above sequence will be of 100 bits size. The starting bit is 1 and the ending bit is 0.

Only detecting whether the first bit as one or not does not help much.

In similar way checking the last bit only also will not help.

 

[std_match]

The sequence will be like 10110110010........0110.
The above sequence will be of 100 bits size. The starting bit is 1 and the ending bit is 0.

Only detecting whether the first bit as one or not does not help much.

In similar way checking the last bit only also will not help.

There is a misunderstanding here. To know in advance "which bit is the first bit" means that there is some syncing/framing mechanism, so the detector can know when a sequence starts, and then only check if it is the correct sequence or not. This is the easy version. It is enough to compare the current bit with the wanted value because the previous bits are already checked. The implementation can just be a 100-bit shift register pre-loaded with the wanted sequence. As long as the incoming bit matches the first bit in the shift register, you just keep shifting the shift register for each incoming bit.

The more difficult version is when the detector must use a "sliding window" because any bit (with the correct value) can be the first bit of the sequence. In this case the 100 last bits must be compared with the wanted sequence for each incoming bit. A 100-bit comparator can be difficult in one clock cycle for high clock frequencies, but it can easily be pipelined. The compare result will just be delayed a few clock cycles.