Codes - Notations: Introduction To Computer Networks

Introduction to Computer Networks
Codes - Notations
Error Detecting & Correcting

Codes
K bits of data encoded into n bits of information.

n-K bits of redundancy
The information data is of length K
The code word is of length n
(n,k) code
n
(7,4)
K =4
redundancy
Parity
Two-Dimensional Bit Parity
Balances the number of 1-s in a code word

Even parity add 1 to achieve an even number of 1s
(p l + p + l +1, p l)
K = p l
n= p l + p + l +1
10101 101011
01010 010100
Odd parity add 1 to achieve an odd number of 1s
10101 101010
01010 010101
Can catch:
All 1-,2-,3- bit errors
Most 4-bit errors
XOR code word by bit to get even parity
10110001 11000010 01101000 00110101 01 001100
Odd parity is NOT of the result
(K+1, K)
Detects all 1-bit errors
10110001
11000010
01101000
00110101
01001100
01100010
0
1
1
0
1
1
Hamming Codes
Hamming Codes
Hamming codes are a family of linear errorcorrecting codes that generalize the Hamming(7,4)code invented by Richard Hamming in 1950.
Hamming codes can detect up to two and
correct up to one bit errors.
Hamming Distance The number of positions in
which 2 words differ.
100101, 101001 distance of 2
Code word of (n,K,d)
Error Detection: d-1
Error Correction: (d-1)/2
Code rate: K/n

Hamming was interested in optimizing two
parameters at once; increasing the distance as
much as possible, while at the same time increasing
the code rate as much as possible.
Hamming codes are special in that they are perfect
codes, that is, they achieve the highest
possible rate for codes with their block
length and minimum distance 3.
Hamming Codes - Construction

2
010
011
100
101
110
111
1
001
Number bits from 1 and upwards

A bit which is a power of 2 is a check bit
1, 2, 4, 8.
All other bits are data bits
3, 5, 6, 7, 9, 10.
Each parity bit covers all bits where the bitwise
AND of the parity position and the bit position is
non-zero.
example : Bit 1 = 001
bit 2 AND bit 1 = 001 & 010 =000
bit 3 AND bit 1 = 001 & 011 = 001
.
bit 1 = bit 3 bit 5 bit 7

Use Generating Matrix (G) and Parity Check
Matrix (H).
G x =y
H y = s
s is a null vector iff y is a code word, i.e. no parity error.
If s is not null, it indicates which bit had an error
1
1
1
G 0
0
1 0 1
0 1 1
0 0 0
1 1 1
1 0 0
0 1 0
0 0 1
1 0 1 0 1 0 1
H 0 1 1 0 0 1 1
0 0 0 1 1 1 1
Hamming Code (7,4)

Example: error in bit 5
x (1 0 1 1)
1 0 1
0

0 1 1
1
1
0 0 0 1
0
1 1 1 0 y
1
1 0 0 0
1
1
0 1 0

0 0 1
1
0
0

0 1 0 1 0 1 0 1 1 1

H y 0 0 1 1 0 0 1 1 0 0
1 0 0 0 1 1 1 1 1 1

1
0

0
1
1
1
G x 0
0
CRC Cyclic Redundancy Check
Data
Codeword
Data
Codeword
0000
0000000
1000
1110000
0001
1101001
1001
0011001
0010
0101010
1010
1011010
0011
1000011
1011
0110011
0100
1001100
1100
0111100
0101
0100101
1101
1010101
0110
1100110
1110
0010110
0111
0001111
1111
1111111
View data bits, D, as a binary number

Choose r+1 bit pattern (generator), G
Goal: choose r CRC bits, R, such that
<D,R> exactly divisible by G (modulo 2)
Receiver knows G, divides <D,R> by G. If

non-zero remainder: error detected!
Can detect all burst errors less than r+1 bits
Polynomial Arithmetic Modulo 2
CRC - Example
B(x) can be divided by a divisor C(x) if B(x) is of

higher degree.
B(x) can be divided once by a divisor C(x) if B(x)
is of the same degree as C(x).
The reminder of B(x)/C(x) is obtained by
subtracting C(x) from B(x).
Subtracting is Simply the XOR operation
G Generator x3+1
D x5+x3+x2+x1 101110
CRC Implementation in Hardware
CRC Implementation in Hardware
CRC algorithm is easily implemented in hardware

using r-bit shift register and XOR gates.
CRC algorithm is easily implemented in hardware

using r-bit shift register and XOR gates.
Put an XOR gate in front of bit n, if there is a
term xn in the generator polynomial.
Below is the hardware that should be used for the
generator x3 + x2 + 1.
The message is shifted from right to left,
beginning with msb and ending with r zeros.
When all the bits have been shifted in and
appropriately XORed, the register contains the
remainder,
i.e. the
CRC.0
2
1
B(x) can be divided once by a divisor C(x) if B(x)

is of the same degree as C(x).
The reminder of B(x)/C(x) is obtained by
subtracting C(x) from B(x).
Subtracting is Simply the XOR operation
. r
R = remainder [ D 2 ]
G
message
16
CRC
CRC
Here's a picture for the start of the division of

(x6 + x2 + 1) divided by (x3 + x2 + 1)

(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0
1000101000
Let's do the steps. I'll list the output bit, the

values in the boxes, and the remaining input
x2
x1
x0
000101000

17
18
CRC
CRC

(x6 + x2 + 1) divided by (x3 + x2 + 1)

(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0
00101000

19
x2
x1
x0
0101000

20
CRC
CRC

(x6 + x2 + 1) divided by (x3 + x2 + 1)

(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0
101000

x2
x1
x0
01000

21
22
CRC
CRC

(x6 + x2 + 1) divided by (x3 + x2 + 1)

(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0
1000

23
x2
x1
x0
000

24
CRC
CRC

(x6 + x2 + 1) divided by (x3 + x2 + 1)

(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0
00

25
CRC
(x6 + x2 + 1) divided by (x3 + x2 + 1)
x2
x1
x0

27
x2
x1
x0

26

Codes - Notations: Introduction To Computer Networks

Uploaded by

Copyright:

Available Formats

Codes - Notations: Introduction To Computer Networks

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Codes - Notations: Introduction To Computer Networks

Uploaded by

Copyright:

Available Formats

Introduction to Computer Networks

Error Detecting & Correcting

K bits of data encoded into n bits of information.

Two-Dimensional Bit Parity

Balances the number of 1-s in a code word

XOR code word by bit to get even parity

10110001 11000010 01101000 00110101 01 001100

Odd parity is NOT of the result

Code rate: K/n

Hamming Codes - Construction

Hamming Codes - Construction

Number bits from 1 and upwards

Hamming Codes - Construction

Hamming Code (7,4)

Hamming Codes - Construction

CRC Cyclic Redundancy Check

View data bits, D, as a binary number

Receiver knows G, divides <D,R> by G. If

Polynomial Arithmetic Modulo 2

B(x) can be divided by a divisor C(x) if B(x) is of

CRC Implementation in Hardware

CRC Implementation in Hardware

CRC algorithm is easily implemented in hardware

CRC algorithm is easily implemented in hardware

B(x) can be divided once by a divisor C(x) if B(x)

Here's a picture for the start of the division of

Here's a picture for the start of the division of

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

Here's a picture for the start of the division of

Here's a picture for the start of the division of

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

Here's a picture for the start of the division of

Here's a picture for the start of the division of

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

Here's a picture for the start of the division of

Here's a picture for the start of the division of

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

Here's a picture for the start of the division of

Here's a picture for the start of the division of

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

Let's do the steps. I'll list the output bit, the

You might also like