0
718views
Draw state diagram of sequence detector to detect a non-overlapping sequence 10001. write its state table. Find the equivalent state if they are present
0
7views

A sequence detector detect both overlapping sequence and non-overlapping sequence.

The given sequence is 10001.

The number of states in the state diagram is equal to the number of bits in the given seuquence.

Here, we have 5 bits in the seuquence, so we will have 5 states in the state diagram.

Once the number of states is known, we have to draw the detected lines with inputs and outputs as weights between the two states.

Let the initial state be 'A'.

State A:

In this state, the machine can receive either an input '0' or '1'. For each of these inputs, an arc is drawn originating in state A and terminating in the appropriate next state.

When the input is '1', we have detected the first bit in the sequence 10001, hence we have to go to the next state to detect the next bit in the sequence.

When the input is '0', we have to remain in state A, because bit '0' is not the first bit in the sequence, in both the cases, the output is '0' since we have not detected all bits in the sequence.

Note: The arc labelled indicates input bit is '1' and output bit is '0'.

State B:

When the input is '0', we have detected the second bit in the sequence, hence we have to go to the next state (C) to detect the next bit in the sequence.

When the input is '1', we have to remain in the state B because '1' which we have detected may not start the sequence. Output is still 'zero'.

State C:

When the input is '0', we have detected the third bit in the sequence. Hence we have to go to the next state (D) to detect the next bit in the sequence.

When the input is '1' we have to remain in the state (C) because '1' which we have detected may not the next bit of the sequence.

output is still 'zero'

State D:

When the input is '0', we have detected the fourth bit in the sequence. Hence we have to go to the next state (E) to detect the next bit of the sequence.

When the input is '1', we have to remain in the state (D) because '1' which we have detected may not be the next bit of the sequence.

output is still zero

State E:

When the input is '0', we have to remain in the state (E) because '0' which we have detected may not be the next bit of the sequence.

When the input is '1', we have detected the fifth bit of the sequence.

Output is '1', since the sequence has been detected.