Hello,

I stumbled across this site which has been very helpful for the digital circuit design course I have been taking. I appreciate all of the content. My instructor has given us an assignment that I have challenged as being inconsistent and I would appreciate some advice if anyone has time to look at this. The problem statement:

A Universal Serial Bus (USB) communication link requires a circuit that produces the sequence 00000001. Since this sequence is a flag used in the USB communication network, that represents the beginning of a message, this flag must be unique. As a consequence, at most five 1s in the sequence may appear anywhere else in the message. Since this is unrealistic for normal message context, a trick called zero insertion is used. The normal message which can contain strings of 1s longer than 5, enters input X of a sequential zero-insertion circuit. After a fifth 1 in sequence appears on X, a 0 is inserted in the stream of outputs appearing on Z and the output S = 1, indicating to the circuit supplying the zero-insertion circuit with inputs that it must stall and not apply a new input for one clock cycle. This is necessary because the insertion of 0s in the output sequence causes it to be longer than the input sequence without the stall.

An example is given: 01111100111111100001011110101
Sequence on X without any stalls: 01111110001111111100001011110101
Sequence on X with stalls 0111110001111101100001011110101
Sequence on Z:
Sequence on S: 0000001000000010000000000000000


I have bolded the inconsistent portion. I believe that this is meant to be 01111110 (as I understand is a common flag), and that zero-bit insertion is not possible with 00000001. Is this an incorrect assumption?
Example sequence: 0-0-0-0-0-0-0 (if I see a 1, it's the flag now, so I should insert a 0) - 0 (if I see a 1, it's the flag now, so I should insert a 0).... This pattern would repeat indefinitely - this flag simply does not allow for zero-bit insertion.

I would appreciate any help, as I am convinced there is errata that needs to be corrected here. If I am incorrect, please point me in the right direction as I am completely lost.

Thank you.

 

You said you indicated the inconsistent pattern in bold, but I don't see any bold text except in the first line of the second paragraph where you are describing a flag.

This is from the wiki

SDLC and Low- and full-speed USB data are sent NRZI encoded: a 0 bit causes a signal transition, whereas a 1 bit causes no change. After a long sequence of 1 bits there could be no transitions in the transmitted data, and it would be possible for the transmitter and receiver clocks to lose synchronisation. By inserting a 0 after five (SDLC) or six (USB) sequential 1s the transmitter guarantees a maximum time between transitions. The receiver can synchronise its clock against the transitions to ensure proper data recovery.

In SDLC the transmitted bit sequence "01111110" containing six adjacent 1 bits is the Flag byte. Bit stuffing ensures that this pattern can never occur in normal data, so it can be used as a marker for the beginning and end of frame without any possibility of being confused with normal data.[1]

Don't confuse the SDLC and the USB algorithms, they are not the same. Make sure you get your bit ordering correct in terms of in memory and "on the wire". Make sure you know, then double check your assumptions.

 

Thank you for your reply. What I am having trouble with is that in the problem statement the flag (to indicate the beginning of a transmission) is said to be 00000001. How would zero-bit insertion work with this flag?

This might be a little confusing because it does not tie to any actual protocols - just theoretical, because the instructor took a problem from our textbook that initially was designed to model USB and then changed the flag - The original problem asks to use 01111110 as the flag which would work. This sounds plausible, as zero-insertion after 5 consecutive 1s would ensure that if the flag is present in the transmission, that a 0 is inserted as to not reproduce the unique flag. Am I understanding this correctly? I don't understand how this would work if the flag was 00000001, as it is in the theoretical problem presented by the instructor.

 

AFAIK the flag of interest consisting of seven 0's and a single 1 would go through the bit stuffing process without modification. You only stuff 0's into strings of 1's. So the question comes down to whether the terminal 1 in the flag is the first potential 1 in a string of 1's.

 

That is the conclusions that I came to as well. Do you agree that the problem is difficult to interpret in its current state? It doesn't seem that zero-bit insertion is related to this particular flag.

 

That is the conclusions that I came to as well. Do you agree that the problem is difficult to interpret in its current state? It doesn't seem that zero-bit insertion is related to this particular flag.

Maybe, but it is clear that if the byte following the flag begins with four consecutive 1's a zero will be stuffed.

 

Thank you for taking a look - that is my interpretation as well. I appreciate that you took the time to read and respond.

 

I agree that it looks like the instructor changed the flag and didn't update the rest of the fake protocol to match. What did the instructor say when you pointed this out?

 

WBahn,

Unfortunately she is holding her ground saying there is nothing wrong with the problem and that zero-insertion can occur with this flag. I don't know for sure whether it is stubbornness or if I am simply completely missing something. I sent over a paper showing why it was not possible in my opinion. I've included a portion of that (attached) - does what I'm explaining sound correct?

 

I think that your example is good. You might also point out that the purpose of 0-insertion is specifically to prevent an unacceptably long string of consecutive 1-bits from appearing in the data. If the flag is changed so that the concern is an unacceptably long string of consecutive 0-bits appearing in the data, then the algorithm needs to be modified so that it performs 1-insertions.

 

Thank you for your insight. I indeed mentioned that possibility later in my assignment. Is 1-bit insertion used anywhere in the real world? In my research I found that 0-bit insertion appears to be an ISO standard for protocol data units, but I did not find anything on 1-bit insertion that was widely used. I'm new to this though so I could have missed it.

 

The general concept is "bit stuffing" and what gets stuffed when and where depends on the specifics of the protocol. My guess is that 0-insertion is more prevalent because of commonly used NRZI protocols in which a 0 bit is encoded as a level transition while a 1 bit is not. This makes it hard to recover the clock at the receiver if a string with two many consecutive 1 bits is sent. So inserting a 0-bit when some maximum length of 1 bits is transmitted alleviates this. This is completely separate from flags, but offered a convenient way to implement a flag character that systems were already set up to suppress -- no you just had to intentionally NOT suppress them when you really did want to transmit a flag.

 

Great, thank you for the information. I appreciate your help with this.

 

No problem.

Oh, and for what it's worth, keep in mind that teachers frequently have to write assignments and release them to students without actually working them first -- they just run out of time and have to get the assignment released. As a result, we sometimes think we know the solution but didn't really think it through carefully enough. We can get blinders on where we really do think we know that everything is fine. Still, we should always be receptive to the possibility that we are wrong and have overlooked something -- but it can be hard to do at times.

 

I appreciate your perspective - sounds like you are a teacher as well. Thanks again!