Bit-stuffing
P
r
o
g
r
a
m
:
-
#
i
n
c
l
u
d
e
<
s
t
d
i
o
.
h
>
#
i
n
c
l
u
d
e
<
s
tr
i
n
g
.
h
>
i
n
t
m
a
i
n
(
)
{
int i, k = 0, count = 0;
char
str[100],stuffed[
100];
printf("Enter the
bit string: ");
scanf("%s", str);
for (i = 0; i <strlen(str); i++)
{
if
(
s
t
r
[
i
]
=
=
'
1
'
)
{
c
o
u
n
t
+
+
;
}
else {
c
o
u
n
t
0
;
}
if (count == 6)
{
stuffed[k++] = '0';
c
o
u
n
t
0
;
}
stuffed[k++] = str[i];
}
stuffed[k++] = '\0';
printf("String after bit-stuffing:
%s\n", stuffed); return 0;
}
Output :-
EXP 4:
Implement on a data set of characters the two CRC polynomials: CRC 12 - CRC 16
Cyclic Redundancy Check
This Cyclic Redundancy Check is the most powerful and easy to implement
technique. Unlike checksum scheme, which is based on addition, CRC is based on
binary division. In CRC, a sequence of redundant bits, called cyclic redundancy check
bits, are appended to the end of data unit so that the resulting data unit becomes exactly
divisible by a second, predetermined binary number. At the destination, the incoming
data unit is divided by the same number. If at this step there is no remainder, the data
unit is assumed to be correct and is therefore accepted.
A remainder indicates that the data unit has been damaged in transit and
therefore must be rejected.
1. Bit strings are created as representation of polynomials with coefficients ‘0’ and
‘1’only.
2. A k-bit frame is regarded as coefficients list for a polynomial with
‘k’ terms (xk-1 to x0 ) Eg: x5 + x4 +x0 = 110001
When this method is used, the sender and the receiver should agree upon a
generator polynomial, G(x) in advance.
Both the high and low order bits of G(x) must be ‘1’
To compute checksum for some frame with ‘m’ bits (polynomial = M(x), append ‘r’ zero
bits to the lower end of the frame (r = degree of the generator polynomial) so that this
check summed frame is divisible by G(x).
Divide M(x) by G(x) using modulo-2 division and subtract the remainder from M(x)
using modulo-2subtraction. let the resultant be called as T(x)
T(x) is passed to the receiver and the receiver
divides it by G(x). If there is a remainder, there
has been a transmission error.
Eg: frame
=
11010110
11 G(x) =
x4 +x +1
= 10011
è degree = 4
Therefore, frame = 1101011011 + 0000
èM(x) = 11010110110000
Commonly used
divisor polynomials
are: CRC 12: x12 +
x11 + x3 + x2 + x + 1
CRC 16: x16 + x15 +
x2 + 1
CRC CCITT: x16 + x12 + x5 + 1
Program :-
#include <stdio.h>
#include <string.h>
char data[20], divi[20], temp[40], total[100];
int i, j, choice, datalen, divlen, len, flag =1;
void check(void);
int main()
{
printf("Enter the total bit of data: ");
scanf("%d", &datalen);
printf("Enter 0 for CRC-12 and 1 for CRC-16: ");
scanf("%d", &choice);
if (choice == 0)
{
strcpy(divi, "1100000001111");
divlen = 13;
}
else
{
strcpy(divi, "11000000000000101");
divlen = 17;
}
len = datalen + divlen - 1;
printf("Enter the data: ");
scanf("%s", data);
for (i = 0; i<datalen; i++) {
total[i] = data[i];
temp[i] =data[i];
}
for (i = datalen; i<len; i++) { total[i] = '0';
}
check();
for (i = 0; i<divlen; i++)
{
temp[i + datalen] = data[i];
}
printf("Remainder = %s, Divisor = %s\n", data, divi);
printf("Transmitted Code Word: %s\n",temp);
printf("Enter the received code word: ");
scanf("%s", total);
check();
for (i = 0; i<divlen - 1; i++)
{
if (data[i] == '1')
{
flag = 0;
break;
}
}
if (flag ==1)
printf("Received code word contains no errors...!!!\n");
else
printf("Received code word contains errors...!!!\n");
return 0;
}
void check()
{
for (j = 0; j <divlen; j++)
{
data[j] = total[j];
}
while (j <= len)
{
if (data[0] =='1')
{
for (i = 1; i<divlen ; i++)
{
data[i] = ((data[i] == divi[i]) ? '0' : '1');
}
}
for (i = 0; i<divlen - 1; i++)
{
data[i] = data[i + 1];
}
data[i] = total[j++];
}
}