Bit Stuffing Program in C
What is a Bit Stuffing?
The process of inserting one or more extra bits (0) into data is known as bit stuffing. To provide signalling information to a recipient, these are the non-information bits.
Why Bit stuffing is used?
The OSI model's variable-length frames can have data frames of varying sizes. In such cases, it might be extremely difficult to pinpoint the beginning and end of a frame. Bit stuffing is therefore used to signal the end and beginning of the frames during variable-length data frame transfer.
The bit stuffing application can be used to quickly create new files and folders. With only one click, you may utilize the application to create new files or directories.
Process in Bit Stuffing
With the new method known as "bit stuffing," character codes can have any number of bits per character, and data frames can include any number of bits.A flag byte, also known as the unusual bit pattern 01111110, begins and ends each frame.
When the data link layer of the sender encounters five consecutive 1s, it immediately adds a 0 bit to the outgoing bit stream.
Complexities of bit stuffing in c
Complexity of Time
O(N), where "N" is the array's size "arr."
The array is only once traversed, hence the time complexity is O. (N).
Complexity of Space
O(N), where "N" is the array's size "arr."
As we are merely initializing the vector "ANS," which has a size of "N." The space complexity is therefore O. (N).
Example 1
N = 6, arr[] = 1, 1, 1, 1, 1, 1 as an input
Results: 1111101
Explanation: After the fourth index in the given array, there are 5 consecutive 1s encountered while traversing the array. As a result, after the fourth index, a zero bit has been added to the packed array.
Example 2
N = 6, arr[] = 1, 0, 1, 0, 1, 0 as an input.
Result: 101010
The approach in Bit Stuffing
The goal is to determine whether the provided array has 5 consecutive 1s.
There are two steps to be followed for the approach of bit stuffing in c
They are
- Initializing the array
- Traversing in a while loop
Initializing the array
set the array brr[], which houses the packed array, to zero. Make a variable count that keeps track of the number of consecutive 1s
Traversing in a while loop
The following actions using a variable iin the range [0, N] and a while loop:
If arr[i] is 1, then see if the next 4 bits are also set. If they are, add a 0 bit to the array brr[after adding all 5 set bits].
If not, then in that case add the value of arr[i] to the brr[ array ].
Software and hardware requirements
We have software and hardware requirements for the execution of bit stuffing in c programming
The software requirements are given as intel-based desktop pc: RAM of 1GB
The Hardware requirements aregiven as Turbo c or Turbo C++
Example programs
Example 1
// C program for the bit stuffing
#include <stdio.h>
#include <string.h>
void bitStuffing(int n, int arr[])
{
int brr[40];
int i, j, k;
i = 0;
j = 0;
int count = 1;
while (i< n)
{
if (arr[i] == 1)
{
brr[j] = arr[i];
for (k = i + 1;arr[k] == 1 && k < n && count < 5;k++)
{
j++;
brr[j] = arr[k];
count++;
if (count == 5)
{
j++;
brr[j] = 0;
}
i = k;
}
}
else
{
brr[j] = arr[i];
}
i++;
j++;
}
for (i = 0; i< j; i++)
printf("%d", brr[i]);
}
int main()
{
int n = 6;
int arr[] = { 1, 1, 1, 1, 1, 1 };
bitStuffing(n, arr);
return 0;
}Output
1111101
Example 2
#include<stdio.h>
#include<string.h>
int main()
{
int a[20],b[30],i,j,k,count,n;
printf("Enter frame size :");
scanf("%d",&n);
printf("Enter the frame in the form of 0 and 1 :");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
i=0;
count=1;
j=0;
while(i<n)
{
if(a[i]==1)
{
b[j]=a[i];
for(k=i+1; a[k]==1 && k<n && count<5; k++)
{
j++;
b[j]=a[k];
count++;
if(count==5)
{
j++;
b[j]=0;
}
i=k;
}
}
else
{
b[j]=a[i];
}
i++;
j++;
}
printf("After Bit Stuffing :");
for(i=0; i<j; i++)
printf("%d",b[i]);
return 0;
}
Output
Enter frame size : 8
8
Enter the frame in the form of 0 and 1 :1 0 1 0 1 1 0 0
After Bit Stuffing :10101100