Join Sarthaks eConnect Today - India's Largest Online Education Community!

can you explain how we design a digital sequence detector

+7 votes
asked May 24, 2016 in Computer by ashish

1 Answer

+2 votes
answered May 24, 2016 by vikash (21,277 points) 4 18 65
selected May 28, 2016 by sarthaks
Best answer

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 Bn to be a set of bits, as shown below.  The bit b1 is the oldest and is received first.  The bit bn is the youngest and is last.  If another bit is received, it will be inserted into the sequence as bn+1

Bn = b1, b2, ... , bn

To define sequence detection, suppose a sequence of bits Rn = r1, r2, ... , rn is received.  The flag sequence Fk = f1, f1, ... , fk is said to occur at time n if the corresponding bits match. 

fk = rn, fk-1 = rn-1, ... , f1 = rn-k+1

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

R13 = 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


commented May 24, 2016 by vikash (21,277 points) 4 18 65
@Ashish; This is an engineering paper question.

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

One Thought Forever

“There is a close connection between getting up in the world and getting up in the morning.“
– Anon