Wireless Networks

Error Detecting and Correcting Techniques

1
 Coping with Transmission Errors

 Error detection codes

► Detects the presence of an error
 Error correction codes, or forward correction codes
(FEC)
► Designed to detect and correct errors
► Widely used in wireless networks
 Automatic repeat request (ARQ) protocols
► Used in combination with error detection/correction
► Block of data with error is discarded
► Transmitter retransmits that block of data

2
 Error Detection Process

 Transmitter
► For a given frame, an error-detecting code (check bits) is
calculated from data bits
► Check bits are appended to data bits
 Receiver
► Separates incoming frame into data bits and check bits
► Calculates check bits from received data bits
► Compares calculated check bits against received check bits
► Detected error occurs if mismatch

3
 Error Detection
Transmitter Receiver

• Error detection not 100% reliable!

• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction
4
 Parity Checks
Single bit
 Even or Odd parity
 Only single bit error detection
 What about multiple bit errors
 Use when probability of bit errors is small and
independent
 Errors are usually clustered together

The ability of receiver to both detect and correct errors

is known as forward error correction (FEC)

5
 Examples of parity bit check

Adding parity bit

110001011 Odd
110001010 Even
Odd parity errors
110101011 error detected

110100011 error undetected

6
 Two-dimensional parity checks
 Generalization of 1-bit
 D bits are divided into i rows and j columns.

D1,1 D1,2 … D1,j D1,j+1

D2,1 D2,2 … D2,j D2,j+1

. . … . .
. . … . .
. . … . .
Di,1 Di,2 … Di,j Di,j+1

Di+1,1 Di+1,2 … Di+1,j Di+1,j+1

 Receiver can not only detect but correct as well using row, 7
column indices
 Example of 2D Odd parity check

 1110010101111010
 Let i = 4, j = 4

1110 0 1110 0 1110 0

0101 1 0001 1 0011 1
0111 0 0111 0 0111 0
1010 1 1010 1 1010 1
1001 1 1001 1 1001 1
Parity bits Error detection/correction Error detection/ no correction

8
 Cyclic Redundancy Check (CRC)

 Transmitter  Algorithm
► For a k-bit block, ► Generator: Transmitter
transmitter generates an and receiver agree on an
(n-k)-bit frame check
r + 1 bit pattern P.
sequence (FCS)
► Resulting frame of n bits ► Transmitter chooses r
is exactly divisible by additional bits to append
predetermined number with k data bits.
 Receiver ► Which is remainder of d /
► Divides incoming frame P.
by predetermined number ► Receiver: if remainder of
► If no remainder, assumes D / P is 0 , success
no error otherwise error

9
 CRC using Modulo 2 Arithmetic

 Exclusive-OR (XOR) operation

 Parameters:
• T = n-bit frame to be transmitted
• D = k-bit block of data; the first k bits of T
• F = (n – k)-bit FCS; the last (n – k) bits of T
• P = pattern of n–k+1 bits; this is the predetermined divisor
• Q = Quotient
• R = Remainder

10
 CRC using Modulo 2 Arithmetic

 For T/P to have no remainder, start with

nk
T 2 DF
 Divide 2n-kD by P gives quotient and remainder
2nk D R
Q
P P
 Use remainder as FCS

n k
T 2 DR
11
 CRC using Modulo 2 Arithmetic

 Does R cause T/P have no remainder?

T 2nk D  R 2nk D R
  
P P P P
 Substituting,
T R R RR
Q  Q Q
P P P P

► No remainder, so T is exactly divisible by P

12
 CRC Example

Let d = 10111, P=1001 Q

101011
P
1001 101110000
1001
1010
1001
1100 D
1001
`P(X) = X3 + 1 1010
1001
011

R
T = 10111011

13
 CRC using Polynomials

 All values expressed as polynomials

► Dummy variable X with binary coefficients

X n  k D X  R X 
 Q X  
P X  P X 
T  X   X n  k D X   R X 

14
 CRC using Polynomials

 Widely used versions of P(X)

► CRC–12
• X12 + X11 + X3 + X2 + X + 1
► CRC–16
• X16 + X15 + X2 + 1
► CRC – CCITT
• X16 + X12 + X5 + 1
► CRC – 32
• X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2
+X+1

15
 Wireless Transmission Errors

 Error detection requires retransmission

 Detection inadequate for wireless applications
► Error rate on wireless link can be high, results in a
large number of retransmissions
► Long propagation delay compared to transmission
time

16
 Block Error Correction Codes

 Transmitter
► Forward error correction (FEC) encoder maps each
k-bit block into an n-bit block codeword
► Codeword is transmitted; analog for wireless
transmission
 Receiver
► Incoming signal is demodulated
► Block passed through an FEC decoder

17
18
 FEC Decoder Outcomes

 No errors present
► Codeword produced by decoder matches original
codeword
 Decoder detects and corrects bit errors
 Decoder detects but cannot correct bit errors;
reports uncorrectable error
 Decoder detects no bit errors, though errors
are present

19
 Block Code Principles

 Hamming distance – for 2 n-bit binary sequences, the

number of different bits
► E.g., v1=011011; v2=110001;
► 011011 XOR 110001 = 101010
► d(v1, v2)=3
 Redundancy – ratio of redundant bits to data bits
 Code rate – ratio of data bits to total bits
 Coding gain – the reduction in the required Eb/N0 to
achieve a specified BER of an error-correcting coded
system

20
 Block Codes

 The Hamming distance d of a Block code is the

minimum distance between two code words
 Error Detection:
► Upto d-1 errors
 Error Correction:
► Upto
 d  1
 2 

21
 Example of Block code

 Let k = 2, n = 5
Data block Codeword

00 00000
01 00111
10 11001
11 11110

 Suppose we receive 0 0 1 0 0 pattern

 Minimum distance is with codeword 0 0 0 0 0,
so we deduct 0 0 as data bits.

22