Framing, Bit Stuffing & Cyclic Redundancy Check (CRC)
“Flag bytes, HDLC bit-stuffing, and binary modulo-2 CRC division.”
1.Framing Techniques & Bit Stuffing
§ 2.1.The Data Link Layer encapsulates network datagrams into distinct frames. To delimit frame boundaries, modern protocols use byte stuffing (character-oriented) or bit stuffing (bit-oriented).
HDLC Bit Stuffing Rule: HDLC frames begin and end with the special flag byte 01111110 (0x7E, six consecutive 1s). Whenever the transmitting hardware detects five consecutive 1s in the user data stream, it automatically inserts ('stuffs') an extra 0 bit into the output stream. The receiver hardware detects five consecutive 1s followed by a 0 and automatically discards the stuffed 0 bit.
If the receiver detects five 1s followed by a 1 and then a 0, it recognizes the valid end-of-frame flag (01111110). If it detects seven consecutive 1s, it flags a physical channel transmission error.
Always count consecutive 1s strictly from left to right. When five 1s are encountered, insert a 0 immediately, and restart the counting sequence after that stuffed 0.
2.Cyclic Redundancy Check (CRC) Polynomial Mathematics
§ 2.2.CRC is the most powerful hardware error-detecting code in modern data link protocols (Ethernet uses CRC-32). It treats bit sequences as polynomials with coefficients in Galois Field GF(2).
Modulo-2 Arithmetic: Addition and subtraction in GF(2) are identical and correspond to the bitwise XOR operation (no carries and no borrows): 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0.
CRC Algorithm Steps:
1. Let the original data bit sequence be D (length k bits), and let the agreed Generator Polynomial be G(x) of degree r (length r + 1 bits).
2. Append r zeros to the right of the data bits D: D' = D * 2^r.
3. Perform modulo-2 binary division of D' by G. The resulting remainder R has degree at most r - 1 (length r bits).
4. Transmit the codeword T = D' XOR R. At the receiver, dividing T by G yields a remainder of exactly 0 if no errors occurred.
3. GATE Worked Numerical: CRC Remainder & Transmitted Codeword
If generator polynomial G(x) = x^3 + x + 1, its degree is 3! That means you MUST append exactly 3 zeros to the data, and the generator binary bit string has 4 bits: 1011.
Problem: Given Data = 110101 and Generator G(x) = x^3 + x + 1. Find the CRC remainder and the transmitted bit frame.
Step 1: Write G(x) as binary: G(x) = 1x^3 + 0x^2 + 1x^1 + 1x^0 -> Generator bits = 1011 (degree r = 3).
Step 2: Append r = 3 zeros to Data: Dividend = 110101 000 (total 9 bits).
Step 3: Modulo-2 division (XOR subtraction):
110101000 divided by 1011:
1101 XOR 1011 = 0110 -> bring down 0 -> 1100
1100 XOR 1011 = 0111 -> bring down 1 -> 1111
1111 XOR 1011 = 0100 -> bring down 0 -> 1000
1000 XOR 1011 = 0011 -> bring down 0 -> 0110
0110 has degree < 3 -> bring down 0 -> 110 (degree 2).
Final Remainder R = 110 (3 bits).
Step 4: Transmitted Codeword T = Data appended with Remainder = 110101 110.
4.Hamming Distance & Error Detection/Correction Bounds
§ 2.4.Hamming Distance d(c1, c2) between two binary codewords of equal length is the number of bit positions in which they differ (the number of 1s in c1 XOR c2).
Minimum Hamming Distance d_min of a code is the smallest Hamming distance between any pair of valid codewords in the code.
Theorem 1 (Error Detection): To detect up to e bit errors in any transmitted codeword, the code must satisfy: d_min >= e + 1.
Theorem 2 (Error Correction): To correct up to t bit errors in any transmitted codeword, the code must satisfy: d_min >= 2t + 1.
To detect 3 errors: d_min >= 3 + 1 = 4. To correct 2 errors: d_min >= 2(2) + 1 = 5. To detect e errors and simultaneously correct t errors (where e > t): d_min >= e + t + 1.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-level numerical drilling and PYQ analysis.
Step-by-step conceptual walkthroughs with worked GATE numericals.
Clear whiteboard lectures for foundational and semester exam coverage.