Bit Stuffing Program in C

Last Updated on July 13, 2023 by Mayank Dham

Bit stuffing is a technique commonly used in data communication to ensure reliable and accurate transmission of information. In this article, we will explore the concept of bit stuffing and present a program implemented in the C programming language that demonstrates how bit stuffing can be implemented.
Bit stuffing is employed when transmitting data over a communication channel that may introduce synchronization issues due to the occurrence of specific bit patterns. By inserting additional bits into the data stream, bit stuffing helps maintain synchronization between the sender and the receiver.

What is Bit Stuffing?

A Bit Stuffing Program in C programming is a software application that implements the process of bit stuffing, which is used in data communication to ensure synchronization and reliable transmission of information. The program takes a stream of data bits as input and performs bit stuffing by inserting additional bits into the data stream. These additional bits, known as stuffed bits, help maintain synchronization between the sender and receiver in the presence of specific bit patterns that might cause synchronization issues.

The purpose of a Bit Stuffing Program is to automate the bit stuffing process and provide an efficient and reliable solution for handling data transmission in communication systems. It allows developers to implement bit stuffing in their applications, protocols, or networking systems, ensuring the accurate delivery of data across different communication channels.

The trailer and header are known as the control characters and they are used to denote the end and start of the node. They are specific bit patterns that are not likely to occur in actual data. They are used as they make the receiver easily identify the start and end of the actual data in the packet. That is useful in extracting the actual data from the total data.

But this will also create a problem in the case that the actual data and the control characters contain the same bit pattern. As of now the receiver will be confused and might interpret the data as the control characters and then ignore the data which will lead to data loss or corruption. We use bit stuffing to overcome this problem.
In bit stuffing, we use a specific bit pattern to indicate the start and end of the packet. And as explained in the above case, there might be a scenario when the control characters and the actual data contain the same bit pattern. In this case the bit stuffing inserts an extra bit into the data to differentiate it from the control characters.

Bit Stuffing Program in C

Now we will see a bit stuffing program in c with its code and implementation and explanation of the above code.

#include <stdio.h>
#include <string.h>
 
void bitStuffing(int N, int arr[])
{
    // Here we will store the stuffed array.
    int brr[30];
 
 
    int i, j, k;
    i = 0;
    j = 0;
 
    while (i < N) {
 
        if (arr[i] == 1) {
 
            //Will store the count of consecutive ones
            int count = 1;
 
 
            brr[j] = arr[i];
 
 
            for (k = i + 1;
                arr[k] == 1 && k < N && count < 5; k++) {
                j++;
                brr[j] = arr[k];
                count++;
 
                // if we found 5 consecutive ones then will insert a zero.
                if (count == 5) {
                    j++;
                    brr[j] = 0;
                }
                i = k;
            }
        }
 
    // otherwise will copy the array directly without any modification.
        else {
            brr[j] = arr[i];
        }
        i++;
        j++;
    }
 
 
    for (i = 0; i < j; i++)
        printf("%d", brr[i]);
}
 
 
int main()
{
    int N = 9;
    int arr[] = { 1, 1, 1, 0, 1, 1, 1, 1, 1 };
 
    bitStuffing(N, arr);
 
    return 0;
}

Output

1110111110

Explanation of the above code for Bit Stuffing Program in C
In the above program we are traversing the original data array and after that when we encounter a set bit we will count the number of consecutive set bits if the theory is 5 then we will insert a zero bit at their end and then repeat the operation for the remaining array.

Time Complexity: O(n) will be the time complexity for writing bit stuffing code in C.

Space Complexity: O(N) will be the space complexity for bit stuffing program in C Language.

Bit Destuffing Program in C

Bit destuffing in C is the process of removing the stuffed bits from a bitstream to retrieve the original data. It is the reverse operation of bit stuffing and is used to decode the data received after transmission.

Approach for Bit Destuffing Program in C

1. Start by defining a function, let’s call it bitDestuffing, which takes two parameters: the array arr[] representing the bitstream and an integer n representing the size of the array.
2. Inside the bitDestuffing function, create a new array destuffedBits[] to store the destuffed bits. Also, initialize a variable count to keep track of consecutive 1’s.
3. Use a loop to traverse the arr[] bitstream array. Initialize two variables, i and j, to iterate over the input and output arrays, respectively.
4. Within the loop, check if the current bit arr[i] is equal to 1. If it is, increment the count variable.
5. If the count reaches 5 and the next bit arr[i + 1] is a 0, it means that the 0 bit was inserted as a stuffed bit. In this case, skip the next bit by incrementing i and reset the count to 0.
6. Store the bits in the destuffedBits[] array by assigning arr[i] to destuffedBits[j]. Then increment both i and j by 1.
7. After the loop completes, you will have the destuffed bits stored in the destuffedBits[] array.
8. Print or process the destuffed bits as per your requirements.

Code Implementation of Bit Destuffing program in C

#include <stdio.h>

void bitDestuffing(int arr[], int n) {
    int destuffedBits[n];
    int count = 0;
    int i, j;

    for (i = 0, j = 0; i < n; i++) {
        if (arr[i] == 1) {
            count++;

            if (count == 5 && arr[i + 1] == 0) {
                i++;
                count = 0;
            }
        }

        destuffedBits[j] = arr[i];
        j++;
    }

    // Process or print the destuffed bits as needed
    for (i = 0; i < j; i++) {
        printf("%d ", destuffedBits[i]);
    }
}

int main() {
    int arr[] = {1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    bitDestuffing(arr, n);

    return 0;
}

Output

1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 

Time Complexity: The time complexity of bit destuffing program in c is O(N).
Space Complexity: The space complexity of bit destuffing program in c is O(N).

Applications of Bit Stuffing

Bit Stuffing has many applications some of which are mentioned below:

• It is used in network communication protocols like HDLC, and Ethernet as it ensures reliable data transmission.
• It is used in serial communication protocols like USB and RS-232 to prevent data loss due to synchronization errors.
• We can use bit stuffing in file transferring protocols as they allow us to transfer the data without errors.
• The synchronization in bit stuffing allows it to be used in image and video processing.

Conclusion
In conclusion, the implementation of a bit stuffing program in the C programming language provides a powerful tool for ensuring reliable and accurate data transmission in communication systems. Bit stuffing helps maintain synchronization and prevent synchronization issues caused by specific bit patterns.

By following the steps outlined in the article, developers can create a functional bit stuffing program in C. The program identifies consecutive 1’s in the input bitstream and inserts additional bits, known as stuffed bits, to maintain synchronization. The resulting modified bitstream with stuffed bits can then be transmitted over a communication channel.

Frequently Asked Questions

Here are some of the frequently asked questions about the bit stuffing program in c.

1. What are control characters?
Control characters are specific bit patterns used in communication systems to indicate the start and end of data packets or to control the flow of data.

2. What is the difference between byte stuffing and bit stuffing?
Byte stuffing involves adding an extra byte to the data packet, whereas bit stuffing involves adding an extra bit to the data packet.

3. What are bitwise operators?
Bitwise operators are operators used in C to perform operations on individual bits within a byte.

4. How is bit stuffing used in Ethernet?
Ethernet frames use a specific bit pattern called the preamble and start of frame delimiter (SFD) to indicate the start of a packet. Bit stuffing is used to ensure that the data in the packet does not contain the same bit pattern as the preamble and SFD.

5. How is bit stuffing used in USB?
USB uses bit stuffing to ensure that the data does not contain the same bit pattern as the USB packet synchronization characters.