C Program for Bit Stuffing and Destuffing

Bit stuffing and destuffing are crucial techniques used in data link layer protocols to ensure reliable data transmission. They prevent sequences of data bits from being misinterpreted as control characters or flags, especially when the data itself contains patterns identical to these control sequences.

What is Bit Stuffing?

Bit stuffing is the process of adding one or more extra bits into a data stream to break up a sequence of identical bits that might otherwise be misinterpreted as a control signal. For example, in protocols like HDLC, a flag sequence (01111110) is used to mark the beginning and end of a frame. To prevent the actual data from containing this sequence, a '0' bit is stuffed after every five consecutive '1's in the data stream.

What is Bit Destuffing?

Bit destuffing is the reverse process of bit stuffing. When the receiver receives a stuffed frame, it removes the extra stuffed bits to recover the original data. For every sequence of five consecutive '1's followed by a '0', the receiver removes that '0' bit, effectively restoring the original data stream.

C Program Implementation

This C program demonstrates the implementation of both bit stuffing and destuffing. It takes a bit stream as input, performs stuffing, and then destuffs the resulting frame to recover the original data.

Program Setup

#include <stdio.h>
#include <conio.h> // For getch() and clrscr() - non-standard, often used in older compilers

int main()
{
    int src_frame[50], dest_frame[50], rev_frame[50];
    int n, j, i, count = 0;
    int k;
    // clrscr(); // Clear screen - specific to conio.h

    printf("\n Enter the size of the bit stream: ");
    scanf("%d", &n);

    printf("\n Enter %d bits for the stream (0 or 1): ", n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &src_frame[i]); // Accepting the bit stream and storing it in src_frame
    }
    i = 0;
    j = 0;

Bit Stuffing Logic

The stuffing process iterates through the source frame. If five consecutive '1's are encountered, a '0' bit is inserted into the destination frame.

// Code for Bit Stuffing
// dest_frame is an array used to hold the frame after stuffing
    while (i < n)
    {
        if (src_frame[i] == 1) // If the source frame bit is '1'
        {
            dest_frame[j++] = src_frame[i++];
            count++; // If source frame contains a '1' bit, then increment count value.
            if (count == 5)
            {
                // Five consecutive '1's are present in the source frame
                dest_frame[j++] = 0; // Add a '0' bit to the destination frame
                count = 0;           // Reset the count to zero
            }
        }
        else // If a '0' is encountered in the source frame
        {
            count = 0;
            dest_frame[j++] = src_frame[i++]; // Copy the source frame bit into the destination frame
        }
    }

Displaying Stuffed Frame

    printf("\n After Bit Stuffing: ");
    for (i = 0; i < j; i++)
    {
        printf(" %d", dest_frame[i]);
    }

Bit Destuffing Logic

The destuffing process takes the stuffed frame and removes the extra '0' bits. It looks for sequences of five '1's followed by a '0' and skips the '0'.

    i = 0;
    n = j; // Consider the size of the stuffed frame as n for destuffing.
    k = 0;
    j = 0;
    count = 0;

// rev_frame is used to hold the frame after destuffing
    while (j < n)
    {
        if (dest_frame[j] == 1)
        {
            rev_frame[k++] = dest_frame[j++];
            count++;
            if (count == 5) // If true, then dest_frame has five consecutive '1's.
            {
                j++; // Increment the dest_frame index to remove the stuffed '0' bit during destuffing.
                count = 0; // Reset count after removing the stuffed bit
            }
        }
        else // If the destination frame contains a '0' bit
        {
            count = 0;
            rev_frame[k++] = dest_frame[j++]; // Copy the '0' bit into the destuffed frame (rev_frame).
        }
    }

Displaying Destuffed Frame

    printf("\n After Bit Destuffing: ");
    for (i = 0; i < k; i++)
    {
        printf(" %d", rev_frame[i]);
    }

    getch(); // Waits for a key press - specific to conio.h
    return 0;
}

This program effectively demonstrates how bit stuffing and destuffing work to maintain data integrity in network communication by preventing flag sequences from appearing within the data payload.