Introduction to Computer Networks Codes - Notations

 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
Error Detecting & Correcting  (n,k) code
Codes
n

(7,4)

K =4 redundancy

1 2

Parity Two-Dimensional Bit Parity

 Balances the number of 1-s in a code word  (p l + p + l +1, p l)
 Even parity – add 1 to achieve an even number of 1s  K = p l
10101  101011  n= p l + p + l +1
01010  010100  Can catch:
 Odd parity – add 1 to achieve an odd number of 1s  All 1-,2-,3- bit errors
10101  101010  Most 4-bit errors
01010  010101
 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)
10110001 0
 Detects all 1-bit errors 1
11000010
01101000 1
00110101 0
01001100 1
3 01100010 1 4
Hamming Codes Hamming Codes
 Hamming codes are a family of linear error- Code rate: K/n
correcting codes that generalize the Hamming(7,4)- Hamming was interested in optimizing two
code invented by Richard Hamming in 1950. parameters at once; increasing the distance as
 Hamming codes can detect up to two and much as possible, while at the same time increasing
correct up to one bit errors. the code rate as much as possible.
Hamming Distance – The number of positions in Hamming codes are special in that they are perfect
which 2 words differ. codes, that is, they achieve the highest
 100101, 101001 – distance of 2 possible rate for codes with their block
 Code word of (n,K,d) length and minimum distance 3.
 Error Detection: d-1
 Error Correction: (d-1)/2


5 6

Hamming Codes - Construction Hamming Codes - Construction

 Number bits from 1 and upwards
 A bit which is a power of 2 is a check bit 1 2 3 4 5 6 7
 1, 2, 4, 8….

001
010

100
101
110
111
011
 All other bits are data bits
 3, 5, 6, 7, 9, 10….
 Each parity bit covers all bits where the bitwise 1 2 3 4 5 6 7
AND of the parity position and the bit position is
non-zero. 1 2 3 4 5 6 7
 example : Bit 1 = 001
bit 2 AND bit 1 = 001 & 010 =000 1 2 3 4 5 6 7
bit 3 AND bit 1 = 001 & 011 = 001
….
 bit 1 = bit 3  bit 5  bit 7
7
Hamming Codes - Construction Hamming Codes - Construction
 Use Generating Matrix (G) and Parity Check
 Example: error in bit 5
Matrix (H).
 G x =y x  (1 0 1 1)
 H y = s 1 1 0 1  0
   
 s is a null vector iff y is a code word, i.e. no parity error. 1 0 1 1 1
1  1  
 If s is not null, it indicates which bit had an error 
0 0 0   1
 0  
1 1 0 1 G  x  0 1 1 1     0  y
  0 1 0 0     0 
1
1 0 1 1 
0  1
1 0 1 0 1
0 0 0    
  0 0 0 1 1
G  0 1 1 1
0     0
1 0 0 
0
    
   
0  1
0 0 1 0   0    1 0 1 0 1 0 1  1   1 
          
0 0 0 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 1 0 1 0 1         
   0 1
H   0 1 1 0 0 1 1      
 0 0 0 1 1 1 1   0   1
 

Hamming Code (7,4) CRC – Cyclic Redundancy Check

Data Codeword Data Codeword  View data bits, D, as a binary number
 Choose r+1 bit pattern (generator), G
0000 0000000 1000 1110000  Goal: choose r CRC bits, R, such that
0001 1101001 1001 0011001  <D,R> exactly divisible by G (modulo 2)
 Receiver knows G, divides <D,R> by G. If
0010 0101010 1010 1011010 non-zero remainder: error detected!
 Can detect all burst errors less than r+1 bits
0011 1000011 1011 0110011
0100 1001100 1100 0111100
0101 0100101 1101 1010101
0110 1100110 1110 0010110
0111 0001111 1111 1111111
Polynomial Arithmetic Modulo 2 CRC - Example
 B(x) can be divided by a divisor C(x) if B(x) is of  G – Generator – x3+1
higher degree.  D – x5+x3+x2+x1 – 101110
 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).
R = remainder [ D 2 ]
. r
 Subtracting is Simply the XOR operation G

CRC Implementation in Hardware CRC Implementation in Hardware

 CRC algorithm is easily implemented in hardware  CRC algorithm is easily implemented in hardware
using r-bit shift register and XOR gates. using r-bit shift register and XOR gates.
 Put an XOR gate in front of bit n, if there is a
 B(x) can be divided once by a divisor C(x) if B(x) term xn in the generator polynomial.
is of the same degree as C(x).  Below is the hardware that should be used for the
 The reminder of B(x)/C(x) is obtained by generator x3 + x2 + 1.
subtracting C(x) from B(x).  The message is shifted from right to left,
 Subtracting is Simply the XOR operation 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
x2 x1 x

message
16
CRC CRC
 Here's a picture for the start of the division of  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 x2 x1 x0
0
0 0 0 1000101000 0 0 1 000101000

 Let's do the steps. I'll list the output bit, the  Let's do the steps. I'll list the output bit, the
values in the boxes, and the remaining input values in the boxes, and the remaining input

17 18

CRC CRC
 Here's a picture for the start of the division of  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 x2 x1 x0
0 1
0 1 0 00101000 1 0 0 0101000

 Let's do the steps. I'll list the output bit, the  Let's do the steps. I'll list the output bit, the
values in the boxes, and the remaining input values in the boxes, and the remaining input

19 20
CRC CRC
 Here's a picture for the start of the division of  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 x2 x1 x0
1 1
1 0 1 101000 1 1 0 01000

 Let's do the steps. I'll list the output bit, the  Let's do the steps. I'll list the output bit, the
values in the boxes, and the remaining input values in the boxes, and the remaining input

21 22

CRC CRC
 Here's a picture for the start of the division of  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 x2 x1 x0
0 0
0 0 1 1000 0 1 1 000

 Let's do the steps. I'll list the output bit, the  Let's do the steps. I'll list the output bit, the
values in the boxes, and the remaining input values in the boxes, and the remaining input

23 24
CRC CRC
 Here's a picture for the start of the division of  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 x2 x1 x0
1 0
1 1 0 00 0 0 1 0

 Let's do the steps. I'll list the output bit, the  Let's do the steps. I'll list the output bit, the
values in the boxes, and the remaining input values in the boxes, and the remaining input

25 26

CRC
 Here's a picture for the start of the division of
(x6 + x2 + 1) divided by (x3 + x2 + 1)

x2 x1 x0
0
0 1 0

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

values in the boxes, and the remaining input

27