Question

can you explain how we design a digital sequence detector

Answer 1

Before I explain your question, you first know about what Sequence Detector is?

In a computer network like Ethernet, digital data is sent one bit at a time, at a very high rate.  Such a movement of data is commonly called a bit stream.  One characteristic is unfortunate, particularly that any one bit in a bit stream looks identical to many other bits.  Clearly it is important that a receiver can identify important features in a bit stream.  As an example, it is important to identify the beginning and ending of a message.  This is the job of special bit sequences called flags.  A flag is simply a bit sequence that serves as a marker in the bit stream.  To detect a flag in a bit stream a sequence detector is used.  This document shows you how to produce a Moore type state diagram for a binary sequence detector. 

We define a bit sequence B_n to be a set of bits, as shown below.  The bit b₁ is the oldest and is received first.  The bit b_n is the youngest and is last.  If another bit is received, it will be inserted into the sequence as b_n+1. 

B_n = b₁, b₂, ... , b_n

To define sequence detection, suppose a sequence of bits R_n = r₁, r₂, ... , r_n is received.  The flag sequence F_k = f₁, f₁, ... , f_k is said to occur at time n if the corresponding bits match. 

f_k = r_n, f_k-1 = r_n-1, ... , f₁ = r_n-k+1

For instance, consider the flag sequence F₄ = 0, 1, 0, 1.  Given the received sequence below, detection occurs at times 5, 7, and 13. 

R₁₃ = 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1

The difference between a Mealy and a Moore type sequence detector is that a Mealy sequence detector immediately flags the detection.  With the Moore machine, you must wait for the next clock tick to allow the machine to enter a detection state that flags the detection. 

One way to construct a sequence detector is to use a string of flip-flops wired as a shift register, along with a large AND gate.  The circuit below will produce logic high at its output for one clock cycle, whenever the sequence 0, 1, 0, 0 is received.

Simple Sequence Detector

Identifying the Initial State

Non-Minimized State Table

State	Input = 0	Input = 1
-----	----------	----------
S0	S0, 0	S8,  0
S1	S0, 0	S8,  0
S2	S1, 1	S9,  1
S3	S1, 0	S9,  0
S4	S2, 0	S10, 0
S5	S2, 0	S10, 0
S6	S3, 0	S11, 0
S7	S3, 0	S11, 0
S8	S4, 0	S12, 0
S9	S4, 0	S12, 0
S10	S5, 0	S13, 0
S11	S5, 0	S13, 0
S12	S6, 0	S14, 0
S13	S6, 0	S14, 0
S14	S7, 0	S15, 0
S15	S7, 0	S15, 0
	----------	----------
	State+,	detect

For a pair of states to be equivalent the following two conditions must be true. 

• Both states must lead to the same next state.
• The current outputs for both states must be the same.

Minimized State Table

State	Input = 0	Input = 1
-----	----------	----------
S0	S0, 0	S8,  0
S2	S0, 1	S8,  1
S4	S2, 0	S8,  0
S8	S4, 0	S12, 0
S12	S0, 0	S12, 0
	----------	----------
	State+,	detect

STATE DIAGRAM:-

Comments

@Ashish; This is an engineering paper question.