Data Communication · Lecture 11

Data Link Layer I

Framing and error control: stuffing, parity, Hamming codes, CRC and checksums

Md Mahbub E Noor · Assistant Professor, Department of CSE, University of Barishal

Course: Data Communication · 2nd Year, 2nd Semester

Frames and errors: today's goals

State the services of the data link layer
Frame data with flags, using byte stuffing and bit stuffing
Distinguish single-bit and burst errors; detection and correction
Use Hamming distance: d_min rules for detecting and correcting
Compute parity, Hamming (7,4), CRC and checksum by hand

Lectures 2–10 gave us

a physical layer that moves raw bits, with noise flipping some of them.

Today

package the bits into frames and add redundancy so the receiver can spot, and sometimes fix, errors.

Reading: Forouzan (5th ed.), Chapter 10 and Section 11.1

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

2 / 36

What the data link layer does

Works node to node: one link at a time (hop to hop)
Framing: packs bits into frames with addresses and checks
Flow control: stops a fast sender drowning a slow receiver
Error control: detects (and corrects or resends) damaged frames
Today: framing and error detection/correction; Lecture 12: flow and error control protocols

frame

one link = one data link job

Sublayer	Job
DLC (data link control)	framing, flow and error control, for every link
MAC (media access control)	sharing a broadcast link (Lecture 13)

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

3 / 36

Framing: where does a frame start and end?

The physical layer delivers a bit stream; the receiver must find frame boundaries
Fixed-size frames need no marker
Variable-size frames need a flag at each end
Danger: the flag pattern might appear inside the data
Fix: stuffing, adding something the receiver will remove

Fixed-size framing

No boundaries needed: the size is the delimiter. Example: ATM cells, always 53 bytes.

53 B

Variable-size framing

Mark where each frame starts and ends with a flag:

Flag

Header

Data (variable)

Trailer

Flag

	Character-oriented	Bit-oriented
Data	8-bit characters (text)	any bit pattern
Flag	a special byte	`01111110`
Problem fix	byte stuffing	bit stuffing

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

4 / 36

Byte stuffing (character-oriented)

Add a special escape byte (ESC) before any data byte that looks like a FLAG
An ESC in the data is also escaped (ESC ESC)
Receiver: on ESC, delete it and treat the next byte as plain data
Cost: frame grows by one byte per stuffed byte
Used in PPP (Lecture 12)

Data from upper layer (contains FLAG and ESC)

FLAG

ESC

Frame sent (orange = stuffed ESC)

FLAG

ESC

FLAG

ESC

FLAG

Receiver removes each ESC and keeps the byte after it

FLAG

ESC

Rule: put an ESC before every FLAG or ESC that appears in the data.

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

5 / 36

Bit stuffing (bit-oriented)

Flag = 01111110: six 1s in a row
Sender: after five consecutive 1s in the data, insert a 0
The data can then never contain six 1s, so it never looks like a flag
Receiver: after five 1s, if the next bit is 0, remove it
The 0 is stuffed even if the next data bit is already 0

Data from upper layer

Frame body sent (orange = stuffed 0)

Inside the frame: 01111110 | stuffed data | 01111110

Receiver rule

after 0 1 1 1 1 1 : next bit 0 → delete it

1 1 1 1 1 0 → destuff

Next bit after five 1s is 1? Then it is the flag (or an error).

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

6 / 36

Try it: stuff the flag out of the data

Interactive

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

7 / 36

Checkpoint 1 · 3 minutes

Check your understanding

Q1

Byte-stuff the data: A ESC FLAG B (write the frame body).

Q2

Bit-stuff the data 0111111011111100. How many 0s are added?

Q3

A receiver gets the frame body 0111110110. What was the original data?

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

8 / 36

Types of errors

Single-bit error: only one bit of the data unit changes
Burst error: two or more bits change
Burst length: first corrupted bit to last corrupted bit
Bursts are far more likely: noise lasts longer than one bit
The higher the rate, the more bits one noise spike hits

Single-bit error

sent

received

Burst error of length 8

sent

received

Length = from the first to the last corrupted bit (blue span); bits inside may be correct

Why bursts are common

noise lasting 1/100 s at 1 Mbps

10,000 bits hit

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

9 / 36

Redundancy: detection or correction

To find errors, send redundant bits along with the data
Detection: only ask whether an error happened
Correction: also find the wrong bits and how many (much harder)
Correction needs more redundancy; it suits links where resending is slow (space, broadcast)
Coding arithmetic is modulo 2: addition = subtraction = XOR

Detection

Is there an error? Yes/no. Then discard and ask again (retransmission, ARQ).

Correction

Which bits are wrong? Fix them at the receiver: forward error correction (FEC).

Modulo-2 arithmetic

Add and subtract are the same: XOR. No carries.

⊕	0	1
0	0	1
1	1	0

Example

10110 ⊕ 11010 ───── 01100

Equal bits → 0, different bits → 1

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

10 / 36

Block coding

Split the message into k-bit datawords
Add r redundant bits: n-bit codewords, n = k + r
Only 2^k of the 2ⁿ possible n-bit words are valid
Receiving an invalid codeword reveals an error
An error that turns one valid codeword into another valid one is not detected

k data bits

r redundant

dataword (k bits) → codeword (n = k + r bits)

Datawords

2^k

valid codewords

Possible n-bit words

2ⁿ

2ⁿ − 2^k invalid

If a received word is invalid, an error is detected

Example: 4B/5B (Lecture 6)

k = 4, n = 5: 2⁴ = 16 valid of 2⁵ = 32

16 unused codes

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

11 / 36

Example 10.1: detecting with a 2→3 code

k = 2, n = 3: four valid codewords out of eight
Each codeword is the dataword plus one bit making the count of 1s even
Sender sends 011 (dataword 01)
One error is always caught; two errors can create another valid codeword
This code detects single errors only

Dataword	Codeword
`00`	`000`
`01`	`011`
`10`	`101`
`11`	`110`

Receive 011

valid codeword

accept 01 ✓

Receive 111 (one error)

not in the table

discard ✓

Receive 000 (two errors)

sent 011, valid by bad luck

accept 00 ✗

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

12 / 36

Correcting: pick the closest codeword

Give each dataword 3 redundant bits: k = 2, n = 5
Received 01001 is not a valid codeword: an error
Compare it with every valid codeword
Choose the one it differs from in the fewest bits
Works if only one bit was wrong

Sent 01011 · received

Dataword	Codeword	Distance to 01001
`00`	`00000`	2
`01`	`01011`	1
`10`	`10101`	3
`11`	`11110`	4

Closest valid codeword

01011 differs in only one bit

correct to 01011 → data 01

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

13 / 36

Hamming distance

d(x, y): number of positions where two words differ
Compute it as: XOR the words, count the 1s
Between sent and received word: the number of bit errors
Minimum Hamming distance d_min: smallest distance between any two valid codewords
d_min decides how many errors a code can detect or correct

d(000, 011)

000 ⊕ 011 ─── 011 → two 1s

d = 2

d(10101, 11110)

10101 ⊕ 11110 ───── 01011 → three 1s

d = 3

Code	Pairwise distances	d_min
2→3 (Ex. 10.1)	2, 2, 2, 2, 2, 2	2
2→5 (last slide)	3, 3, 4, 4, 3, 3	3

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

14 / 36

How many errors? The d_min rules

To detect s errors: d_min ≥ s + 1
s errors move a codeword only distance s away: it cannot reach another valid one
To correct t errors: d_min ≥ 2t + 1
Then the received word is still closer to the original than to any other
Ex. 10.1 code: d_min = 2 → detects 1, corrects 0

Detect up to s errors

need

d_min = s + 1

Correct up to t errors

need

d_min = 2t + 1

d_min

received word

Each codeword owns a circle of radius t; if circles do not overlap, the received word belongs to exactly one

d_min 2: detect 1 · d_min 3: detect 2 or correct 1 · d_min 4: detect 3 or correct 1 · d_min 5: detect 4 or correct 2

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

15 / 36

Checkpoint 2 · 3 minutes

Check your understanding

Q1

Sent 0110100110110001, received 0111100110100001. Burst length?

Q2

Find d_min for the codewords 00000, 01101, 10110, 11011.

Q3

A code must correct 2 errors. What is the smallest d_min? How many errors would it then detect?

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

16 / 36

Simple parity check: C(5, 4)

Add one bit so the total number of 1s is even
Receiver recomputes the parity: the syndrome
Syndrome 0: accept; syndrome 1: discard
Detects any odd number of errors
Misses any even number: d_min = 2

r₀ = a₃ ⊕ a₂ ⊕ a₁ ⊕ a₀

s₀ = b₃ ⊕ b₂ ⊕ b₁ ⊕ b₀ ⊕ q₀

Dataword 1011 → codeword 10111 (even parity)

Case	Received	Syndrome	Result
1 · no error	`10111`	0	accept 1011 ✓
2 · a₁ flipped	`10011`	1	discard ✓
3 · r₀ flipped	`10110`	1	discard ✓
4 · r₀, a₃ flipped	`00110`	0	accept 0011 ✗
5 · a₃, a₂, a₁ flipped	`01011`	1	discard ✓

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

17 / 36

Two-dimensional parity

Arrange data in a table; add a parity bit to every row and every column
Sends the extra parity row with the data
Detects all 1-, 2- and 3-bit errors and most bursts
Can even locate and correct a single error (row × column)
Misses 4 errors forming a rectangle

Sent: 4 × 7 data bits

blue = row and column parity

Two errors in row 2

Row 2 parity still OK, but columns 3 and 6 fail → detected

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

18 / 36

Try it: find and fix a flipped bit

Interactive

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

19 / 36

Hamming code (7, 4): encoding

Corrects any single-bit error: d_min = 3
Choose r ≥ 3, then n = 2^r − 1, k = n − r: here n = 7, k = 4
Condition: 2^r ≥ k + r + 1 (every error position plus “no error” needs its own pattern)
Each check bit is the parity of a different set of three data bits
Syllabus topic; in Forouzan 4th ed. (10.3), not in the 5th

r₀ = a₂ ⊕ a₁ ⊕ a₀

r₁ = a₃ ⊕ a₂ ⊕ a₁

r₂ = a₁ ⊕ a₀ ⊕ a₃

Worked: dataword 0111

r₀ = 1⊕1⊕1 = 1 · r₁ = 0⊕1⊕1 = 0 · r₂ = 1⊕1⊕0 = 0

codeword 0111 001

Dataword	Codeword (a₃a₂a₁a₀ r₂r₁r₀)
`0100`	`0100 011`
`0111`	`0111 001`
`1001`	`1001 011`
`1101`	`1101 000`

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

20 / 36

Hamming (7, 4): decoding with the syndrome

Receiver recomputes the three checks over the received bits
The 3-bit syndrome names the wrong bit (table)
Flip it back: single errors are corrected
Two errors give a wrong syndrome: miscorrection ✗
Old-slide fix: row 3 received must be 1101010, not 1101000

s₀ = b₂ ⊕ b₁ ⊕ b₀ ⊕ q₀

s₁ = b₃ ⊕ b₂ ⊕ b₁ ⊕ q₁

s₂ = b₁ ⊕ b₀ ⊕ b₃ ⊕ q₂

Syndrome s₂s₁s₀	000	001	010	011	100	101	110	111
Error in	none	q₀	q₁	b₂	q₂	b₀	b₃	b₁

Sent	Received	s₂s₁s₀	Action
`0100011`	`0100011`	000	accept 0100
`0111001`	`0011001`	011	flip b₂ → 0111
`1101000`	`1101010`	010	q₁ wrong; data 1101 OK
`1101000`	`0001000`	101	flip b₀ → 0000 ✗

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

21 / 36

Try it: Hamming (7, 4) corrects one error

Interactive

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

22 / 36

Cyclic redundancy check: the encoder

Sender and receiver agree on a generator (divisor) of r + 1 bits
Append r zeros to the dataword
Divide using modulo-2 (XOR, no borrows)
Leftmost bit 0? Use 0000 instead of the divisor
Replace the zeros with the remainder: that is the codeword

Sender: 1001 000 ÷ 1011

1010 1011 ) 1001000 1011 ──── 0100 0000 ──── 1000 1011 ──── 0110 0000 ──── 110

Generator

1011: 4 bits → 3 zeros

r = 3

Remainder

from the division

110

Codeword

dataword + remainder

1001 110

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

23 / 36

CRC: the decoder

Receiver divides the whole received codeword by the same generator
No zeros are added
The remainder is the syndrome
Syndrome all 0s: accept, the dataword is the first k bits
Otherwise: discard (an error is detected)

No error: 1001110 ÷ 1011

1010 1011 ) 1001110 1011 ──── 0101 0000 ──── 1011 1011 ──── 0000 0000 ──── 000

Syndrome

000 → accept 1001

Error: 1000110 ÷ 1011

1011 1011 ) 1000110 1011 ──── 0111 0000 ──── 1111 1011 ──── 1000 1011 ──── 011

Syndrome

011 → discard

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

24 / 36

CRC with polynomials

Write a bit pattern as a polynomial with coefficients 0 or 1
Generator 1011 = x³ + x + 1, degree 3 → 3-bit CRC
Codeword c(x) is a multiple of g(x); error e(x) is missed only if g(x) divides e(x)
Standard generators are chosen to catch all common errors
Bursts longer than r: caught with probability ≈ 1 − (1/2)^r

1011 = x³ + x + 1

1001 = x³ + 1

bit i (from the right, starting at 0) = 1 → term xⁱ

Name	Generator	Used in
CRC-8	x⁸ + x² + x + 1	ATM header
CRC-10	x¹⁰ + x⁹ + x⁵ + x⁴ + x² + 1	ATM AAL
CRC-16	x¹⁶ + x¹² + x⁵ + 1	HDLC
CRC-32	x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1	Ethernet, LANs

A good generator…	so that it detects
has more than one term	all single-bit errors
has (x + 1) as a factor	all odd numbers of errors
has degree r	all bursts of length ≤ r

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

25 / 36

Worked CRC: a 10-bit dataword

Dataword 1101011011, generator x⁴ + x + 1
Generator 10011 has 5 bits → append 4 zeros
Shortcut: write the running result, XOR the divisor under each leading 1
Remainder 1110 → frame 11010110111110
Check: the receiver's division leaves 0000

1101011011 0000 ÷ 10011

11010110110000 10011 ───── 01001110110000 10011 ───── 00000010110000 10011 ───── 00000000101000 10011 ───── 00000000001110

Grey bits are already zero; we XOR only under a leading 1

Generator

x⁴ + x + 1

10011 → r = 4

Remainder

1110

Transmitted

1101011011 1110

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

26 / 36

Try it: CRC division and the receiver's check

Interactive

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

27 / 36

Checksum: add instead of divide

Sender adds all data words; sends the complement of the sum
Uses one's-complement arithmetic: carries wrap round and are added back
Receiver adds everything including the checksum and complements
Result 0: accept; anything else: discard
Simple, fast in software; used by IP, TCP and UDP

Step	Sender	Receiver
Data	7, 11, 12, 0, 6	7, 11, 12, 0, 6, 9
Sum	36 = 10 0100	45 = 10 1101
Wrap (4-bit)	0100 + 10 = 0110 = 6	1101 + 10 = 1111 = 15
Complement	1001 = 9 (checksum)	0000 = 0 → accept

Ex. 10.11

plain sum

Ex. 10.12

wrapped sum

Ex. 10.13

complement 15 − 6

One's complement of a 4-bit number = flip every bit = 15 − x

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

28 / 36

The Internet checksum (16-bit)

Data split into 16-bit words (4 hex digits)
Checksum field set to 0, then all words added in one's complement
Carries beyond 16 bits are added back to the sum
Checksum = complement of the sum
Example text “Forouzan”: checksum 7038

“Forouzan” in ASCII, 16-bit words

Fo 466F ro 726F uz 757A an 616E ──── sum 1 8FC6 wrap 8FC6 + 1 8FC7 ¬ → 7038

Checksum sent

FFFF − 8FC7

7038

Receiver

8FC7 + 7038 = FFFF, complement

0000 ✓

Hex complement: subtract each digit from F

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

29 / 36

Try it: the Internet checksum, step by step

Interactive

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

30 / 36

Error-control codes compared

Code	Redundancy	Detects	Corrects	Where used
Simple parity	1 bit	odd numbers of errors	no	serial (UART), memory
2D parity	row + column	1–3 errors, most bursts	1 error	older storage, teaching
Hamming (7,4)	3 per 4 bits	2 errors	1 error	ECC memory, FEC
CRC	r bits (8–32)	all bursts ≤ r, odd errors	no	Ethernet, Wi-Fi, HDLC
Checksum	16 bits	most errors, not reordering	no	IP, TCP, UDP

Rule of thumb: CRC in hardware at the link layer; checksum in software at higher layers; Hamming-type FEC where resending is impossible.

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

31 / 36

Try it yourself: Error-Control Lab

1 · Framing: byte and bit stuffing of any data
2 · Parity: flip bits; when does even parity fail?
3 · Hamming (7,4): flip a bit and watch the syndrome fix it
4 · CRC: long division step by step, any generator
5 · Checksum: 4-bit and Internet checksums

Scan to open the lab on your phone

Open the lab ↗

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

32 / 36

See it in action: catching errors

Watch a flag hidden in the data, and how bit stuffing defeats it
See single-bit and burst errors
Watch parity catch one error and miss two
Follow a Hamming syndrome and a CRC division
When a “Pause & predict” card appears, answer before the video moves on

Click the video to play or pause · Press → for full screen

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

33 / 36

Checkpoint 3 · 3 minutes

Check your understanding

Q1

Find the CRC for dataword 1010 with generator 1011, and the codeword sent.

Q2

Hamming (7,4) from the slides: received 0101011. Syndrome? Corrected dataword?

Q3

4-bit checksum of the words 5, 9, 14, 3. What does the receiver compute if nothing goes wrong?

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

35 / 36

Key takeaways

Frames need boundaries: flags plus byte stuffing (ESC) or bit stuffing (0 after five 1s)
Errors are single-bit or bursts; bursts are common
Detect s errors: d_min = s + 1; correct t: d_min = 2t + 1
Parity detects odd errors; Hamming (7,4) corrects one using the syndrome
CRC: modulo-2 division, remainder appended; checksum: one's-complement sum

Next lecture

Lecture 12 · Data Link Layer II

Flow and error control: Stop-and-Wait, Go-Back-N and Selective Repeat ARQ, piggybacking, and the HDLC and PPP protocols.

Reading: Forouzan, Chapter 11 · Practise in the Error-Control Lab

Md Mahbub E Noor

Lecture 11: Data Link Layer I

University of Barishal

36 / 36

Data Link Layer I

Frames and errors: today's goals

What the data link layer does

Framing: where does a frame start and end?

Fixed-size framing

Variable-size framing

Byte stuffing (character-oriented)

Bit stuffing (bit-oriented)

Try it: stuff the flag out of the data

Check your understanding

Q1

Q2

Q3

Types of errors

Single-bit error

Burst error of length 8

Redundancy: detection or correction

Detection

Correction

Modulo-2 arithmetic

Block coding

Example 10.1: detecting with a 2→3 code

Correcting: pick the closest codeword

Hamming distance

d(000, 011)

d(10101, 11110)

How many errors? The dmin rules

Check your understanding

Q1

Q2

Q3

Simple parity check: C(5, 4)

Two-dimensional parity

Try it: find and fix a flipped bit

Hamming code (7, 4): encoding

Hamming (7, 4): decoding with the syndrome

Try it: Hamming (7, 4) corrects one error

Cyclic redundancy check: the encoder

CRC: the decoder

CRC with polynomials

Worked CRC: a 10-bit dataword

Try it: CRC division and the receiver's check

Checksum: add instead of divide

The Internet checksum (16-bit)

Try it: the Internet checksum, step by step

Error-control codes compared

Try it yourself: Error-Control Lab

See it in action: catching errors

Check your understanding

Q1

Q2

Q3

Key takeaways

Lecture 12 · Data Link Layer II

How many errors? The d_min rules