CRC Encoding - Recab

Август 23, 2022

Содержание

2. CRC Encoding - Recab Multiply i(x) by n-k; (puts n-k zeros in (n-k) low order positions)
3. An Example – Step-by-Step
4. An Example – Step 1
5. An Example – Step 2
6. An Example – Step 3
7. An Example – Step 4
8. An Example – Step 5
9. An Example – Step 6
10. An Example – Step 7
11. An Example – Step 8
12. An Example – Step 9
13. An Example – Step 10
14. Overall
15. CRC Capability Analysis What kind of errors will be detected? Imagine that a transmission error e(x)
16. Undetectable Error Patterns Receiver divides the received polynomial R(x) by g(x) Blindspot: If e(x) is a
17. Designing Good Polynomial Codes Select generator polynomial so that likely error patterns are not multiples of
18. Designing Good Polynomial codes Detecting Odd Numbers of Errors Suppose all codeword polynomials have an even
19. Standard CRC Generator Polynomials CRC-8: CRC-16: CCITT-16: CCITT-32: HDLC, XMODEM, V.41 IEEE 802, DoD, V.42 Bisync
20. Internet Checksum Internet Protocols (IP, TCP, UDP) use check bits to detect errors, instead of using
21. Let IP header consists of L, 16-bit words, b0, b1, b2, ..., bL-1 The algorithm appends
22. Internet Checksum Example Assume 4-bit words Use mod 24-1 arithmetic b0=1100 = 12 b1=1010 = 10
23. Internet Checksum Example Use Modulo Arithmetic Assume 4-bit words Use mod 24-1 arithmetic b0=1100 = 12
25. Скачать презентацию

Слайд 2

CRC Encoding - Recab
Multiply i(x) by n-k; (puts n-k zeros

in (n-k) low order positions)
Divide xn-k i(x) by g(x), and get a remainder polynomial r(x) of at most degree n-k-1. The remainder is the CRC checkbits;
Add remainder r(x) to xn-k i(x); (put check bits in the n-k lower-order positions). The resulted polynomial will be transmitted codeword

b(x) = xn-k i(x) + r(x)

Слайд 3

An Example – Step-by-Step

Слайд 4

An Example – Step 1

Слайд 5

An Example – Step 2

Слайд 6

An Example – Step 3

Слайд 7

An Example – Step 4

Слайд 8

An Example – Step 5

Слайд 9

An Example – Step 6

Слайд 10

An Example – Step 7

Слайд 11

An Example – Step 8

Слайд 12

An Example – Step 9

Слайд 13

An Example – Step 10

Слайд 14

Overall

Слайд 15

CRC Capability Analysis
What kind of errors will be detected?
Imagine that a

transmission error e(x) occurs, so that instead of b(x) arriving, b(x) + e(x) arrives.
e(x) has 1s in error locations & 0s elsewhere, an additive error model adding bit-by-bit to the input codeword b(x) using modulo 2 arithmetic

Слайд 16

Undetectable Error Patterns
Receiver divides the received polynomial R(x) by g(x)
Blindspot: If

e(x) is a multiple of g(x), that is, e(x) is a nonzero codeword, then
R(x) = b(x) + e(x) = q(x)g(x) + q’(x)g(x)
If e(x) is divisible by g(x), the error will slip by! So, how we select g(x)?

Слайд 17

Designing Good Polynomial Codes
Select generator polynomial so that likely error patterns

are not multiples of g(x)
Detecting Single Errors
e(x) = xi for error in location i + 1
If g(x) has more than 1 term, it cannot divide xi
Detecting Double Errors
e(x) = xi + xj = xi(xj-i+1) where j>i
If g(x) has more than 1 term, it cannot divide xi
If g(x) is a primitive polynomial, it cannot divide xm+1 for all m<2n-k-1 (Need to keep codeword length less than 2n-k-1)
Primitive polynomials can be found by consulting coding theory books

Слайд 18

Designing Good Polynomial codes
Detecting Odd Numbers of Errors
Suppose all codeword polynomials

have an even # of 1s, then all odd numbers of errors can be detected
As well, b(x) evaluated at x = 1 is zero because b(x) has an even number of 1s
This implies x + 1 must be a factor of all b(x)
Pick g(x) = (x + 1) p(x) where p(x) is primitive

Слайд 19

Standard CRC Generator Polynomials
CRC-8:
CRC-16:
CCITT-16:
CCITT-32:
HDLC, XMODEM, V.41
IEEE 802, DoD, V.42
Bisync
ATM
= x8

+ x2 + x + 1

= x16 + x15 + x2 + 1
= (x + 1)(x15 + x + 1)

= x16 + x12 + x5 + 1

= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Слайд 20

Internet Checksum
Internet Protocols (IP, TCP, UDP) use check bits to detect

errors, instead of using CRC polynomial
The rationale is the simplicity: the checksum must be recalculated at every router, the algorithm for the checksum was selected for its ease of implementation, instead of strength of error detection capability

Слайд 21

Let IP header consists of L, 16-bit words, b0, b1, b2,

..., bL-1
The algorithm appends a 16-bit checksum bL to the header. The checksum bL is calculated as follows:
Treating each 16-bit word as an integer, find
x = (b0 + b1 + b2+ ...+ bL-1 ) modulo 216-1
The checksum is then given by: bL = - x
Thus, the headers must satisfy the following pattern:
0 = (b0 + b1 + b2+ ...+ bL-1 + bL ) modulo 216-1
The checksum calculation is carried out in software using one’s complement arithmetic

Internet (IP) Checksum Algorithm

Слайд 22

Internet Checksum Example
Assume 4-bit words
Use mod 24-1 arithmetic
b0=1100 = 12
b1=1010 =

10
Use Modulo Arithmetic
Use Binary Arithmetic

Слайд 23

Internet Checksum Example
Use Modulo Arithmetic
Assume 4-bit words
Use mod 24-1 arithmetic
b0=1100 =

12
b1=1010 = 10
b0+b1=12+10=7 mod15
b2 = -7 = 8 mod15
Therefore
b2=1000

Use Binary Arithmetic
Note 16 mod15 =1
So: 10000 mod15 = 0001
leading bit wraps around

b0 + b1 = 1100+1010
=10110
=10000+0110
=0001+0110
=0111
=7
Take 1s complement b2 = -0111 =1000