bit stuffing example

Question

I'm going over an example that reads

Bit Stuffing. Suppose the following bit string is received by the data link layer from the network layer: 01110111101111101111110. What is the resulting string after bit stuffing? Bold each bit that has been added.

Answer:

0111011110111110011111010
               ^      ^

How is this answer reached? My understanding is that bit stuffing works by inserting a certain sequence of bits (known as a flag value) at the beginning and end of a frame. What I don't get is:

We aren't told the flag value!
We aren't told how big a frame is, so how do we know where to put the flag?

Aditional Information: I think this network is Ethernet.

Aditional Information 2: The bit flag is 01111110

Honestly I think I understand but isn't the answer incomplete because they didn't add the flag 01111110 to the end or beginging? They just took care of when that pattern of bits appeared in the message.

Other example: here they do it too.

Bit stuffing is a general concept. You're right that there isn't enough information in what you posted to know what particular bit-stuffing algorithm is being used. This is probably given in the context. What protocol is being discussed? — Gilles 'SO- stop being evil', Oct 04 '12 at 08:29
@Gilles that it's Ethernet? I kid you not this is all the information I was given. — Celeritas, Oct 04 '12 at 08:33
@Celeritas Ethernet was a rather vital part of information, the ethernet specification contains full specifications on how bit stuffing is supposed to be done. — Joachim Isaksson, Oct 04 '12 at 08:34
What happens if a delimiter is in the middle of the string. Would you remove it to turn it into the original string as I thought delimiters from the start and end are only removed. (New Question — dijam, May 09 '16 at 07:49

score 12 · Answer 1 · edited Feb 14 '17 at 00:17

For framing in the network in the data link layer, there are some approaches that the bit-oriented is one of them.

It should be a way to know the start and the end of a frame which is transmitting on the link in the receiver side, so there are some format for framing like HDLC. You can see this.

In the many types of frame formats there are begging sequence (shows the start of frame) and ending sequence (shows the end of frame) and the body of frame which is the data. The problem that might be occur is the appearance of the ending sequence in the body which may make discern of frame end incorrect.

For preventing from this problem, the sender of frame stuff some bit on the body for disarranging the pattern of ending sequence, this technique known as bit stuffing.

Look at this example:

bit sequence: 110101111101011111101011111110 (without bit stuffing)

bit sequence: 110101111100101111101010111110110 (with bit stuffing)

after 5 consecutive 1-bits, a 0-bit is stuffed.

stuffed bits are marked bold.

bit stuffing used in bit stream connection! – Meysam PH Nov 09 '14 at 20:58 — Meysam PH, Nov 09 '14 at 20:58

score 11 · Accepted Answer · edited Jul 04 '13 at 22:22

11

Consider: 0111011110111110*0111110*10

After it finds a 0 and then five consecutive 1 bits it stuffs with a 0. This assumes 0 bit stuffing which is common.

edited Jul 04 '13 at 22:22

will-hart

3,742
2
38
48

answered Apr 19 '13 at 10:05

mani deepak

401
1
4
15

score 2 · Answer 3 · edited Jan 10 '18 at 07:33

2

Bit Stuffing:

Input Stream: 0110111111100111110111111111100000
Stuffed Stream: 01101111101100111110011111011111000000
Unstuffed Stream: 0110111111100111110111111111100000

edited Jan 10 '18 at 07:33

Rob

26,989
16
82
98

answered Jan 10 '18 at 07:20

user9197045

21
1

should the newly stuffed 0 be considered further for detecting the sequence 011111 ? According to your example it seems so, from the last stuffing. Can you direct to some sources for validating this info pls – Mayank Madhav Dec 25 '19 at 19:34

Joachim Isaksson · Answer 4 · 2012-10-04T08:38:51.457

There isn't enough information in the question to answer it fully for "any" protocol, but Ethernet for example bit-stuffs frame content with a 0-bit after 5 consecutive 1-bits, which seems to be the case here.

As for the rest of your question about the framing, a hint is to look at what is supposed to be passed from the data link layer to the network layer. Is it a pre-framed bit of data or just the frame's content you're looking at?

score 0 · Answer 5 · answered Nov 18 '17 at 03:54

Whenever you have to perform bit stuffing , you will always be given the starting and ending marker FLAG bit value The easiest trick is to remove the last two bits of the flag and note down the new bit series , whenever you get the same series in your data , you have to stuff one bit there . For eg - Given data is 011111011110 Here my FLAG is 0111110 So my my new FLAG will be 01111 I will stuff a bit whenever I get (01111) in my data series , So , the data after stuffing will be - 01111(0)101111(0)0 Brackets imply stuffing here .

bit stuffing example

5 Answers5