Discriminate bits after "bit stuffing"

Question

I have written a piece of code to add a '0' after 6 consecutive '1' in a bit stream. But how to decode it?

Here an example of one bits stream:

original = {01101111110111000101111110001100...etc...}

stuffed  = {011011111O101110001011111O10001100...etc...}

(The 'O' stand for the stuffed '0'.)

As you can see a '0' was added after each '111111' and to retrieve the original stream one has to remove it. Easy.

But... What if the original stream had the same form as the stuffed one? How do I know if I have to remove these bits?!

Your output has only five 1-bits before the first 'stuffed' 0 (marked as O), and loses the sixth 1. Is that a typo and there should be six 1-bits? A similar problem afflicts the second stuffed 0; there a five 1-bits before it, but this time the sixth 1-bit was preserved. What are you really trying to? Your words say one thing and your sample output says something else. — Jonathan Leffler, Feb 11 '19 at 02:36
If in your original data stream you had six ones in a row and then a zero your output would be six ones in a row and then two zeroes. Removing a zero gives you the original stream. This assumes all data you wish to decode will go through your encoder first. — Retired Ninja, Feb 11 '19 at 02:37
No it's okay. The first bit is stuffed after five '1'. "0110111111011100" => "011011111.O.101110". — , Feb 11 '19 at 02:52
But I do I know if the original byte was a 0b01111101 or a 0b01111110 stuffed: 0b011111O1 ? — , Feb 11 '19 at 03:00
Your question text says "add a '0' after **6** consecutive '1'"; your comment text and your examples effectively show "add a '0' after **5** consecutive '1'". Please decide which is right and fix the other. — Jonathan Leffler, Feb 11 '19 at 03:14
You're right! Sorry ! So, 0b01111110 is stuffed which it lead to a 0b011111O1. How to know if there is a '0' to remove when receiving a 0b01111101 ? — , Feb 11 '19 at 03:27
@joe.garage Why are you deleting 0's? 0b01111110 is stuffed which leads to 0b01111101**0**. Why did you delete the last 0? — user253751, Feb 11 '19 at 03:29
Okay well then you need to look at the MSB in the next byte when decoding. Bit stuffing doesn't know about bytes. — user253751, Feb 11 '19 at 04:11
The stream of bits is transmitted in a packet of bytes and looking at the next byte don't tell any information. — , Feb 11 '19 at 04:27
When you receive 0b01111101 you see 5 1's in a row, so the next 0 is stuffing and you remove it, right? — user253751, Feb 11 '19 at 04:56
suggest you read about the 'bit sync' communication protocol. All the details are laid out there/ Suggest reading: [bit sync protocol](https://en.wikipedia.org/wiki/Bit-oriented_protocol) and [synchronous communication protocol](https://en.wikipedia.org/wiki/Synchronous_serial_communication) — user3629249, Feb 12 '19 at 04:50

score 2 · Answer 1 · answered Feb 11 '19 at 04:07

I think you are confused with the basics. Pretend you want a B added after 2 As. This is not 'stuffed':

AAAAA

'Stuffing' it gives you:

AABAABA

The above is either 'stuffed' or 'not stuffed'. In other words you can stuff it again:

AABBAABBA

Or you could 'unstuff' it:

AAAAAA

What if the original stream had the same form as the stuffed one?

So if a bitstream has 10 consecutive 1s in it then it has clearly not been stuffed. You can't say the same for a bitstream that could have been stuffed.

score 0 · Answer 2 · answered Feb 13 '19 at 00:58

My question was so dumb... But it was late !

Here the piece of code I wrote. It takes two streams of bits. The length of the stream to be stuffed is in its first byte. It works well except the new length after stuffing is not yet updated. I used macro so it's more readable.

#include    "bitstuff.h"
#include    <stdio.h>
#include    <stdlib.h>
#include    <inttypes.h>
#define     sbi(byte, bit)  (byte = byte  |  (1 << bit))
#define     cbi(byte, bit)  (byte = byte & ~ (1 << bit))
#define     ibc(byte, bit)  (~byte & (1 << bit))
#define     ibs(byte, bit)  (byte & (1 << bit))
#define     clr(byte)       (byte = 0)

void    bitstuff(uint8_t* stream, uint8_t* stuff) {

        int8_t      k = 7, b = 7;
        uint8_t     row = 0;
        uint8_t    len = 8**stream++;

        stuff++;

        while(len--) {

            if(ibs(*stream, k--)) {

                row++;

                if(row==5) {

                    cbi(*stuff, b--);
                    if(b<0) {b=7; stuff++;};
                    sbi(*stuff, b--);
                    if(b<0) {b=7; stuff++;};
                }

                else {

                    sbi(*stuff, b--);
                    if(b<0) {b=7; stuff++;};
                }
            }
            else {

                clr(row);
                cbi(*stuff, b--);
                if(b<0) {b=7; stuff++;};
            }

        if(k<0) {k=7; stream++;};
    }
}

Discriminate bits after "bit stuffing"

2 Answers2