CS1001.py

Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013

Recitation 14 - 17-20.6.2013

Last update: 16.6.2013

Error detection and correction

When we send data, we send data + error correction information (EC). Although longer, this transmission will allow detecting and correcting errors in transmission.

Definitions

• k – len of original message

• n – len of transmitted message (data + EC)

• The Hamming distance between two n-bit long messages is the numbers of differences between them. Example:

• d is the minimal HD between any 2 possible n-messages.

• An (n,k,d) code is able to detect d-1 errors, and fix
  $\frac{d-1}{2}$ errors.

Repetition code

Transmitting each bit p times.

data = 10 p = 4 data + EC = 11110000 d = 4

Other codes from lecture

• Parity bit (xor)
• 2D parity bit (card magic)
• Israeli ID control digit
• Hamming (7,4,3) code

Index code

We will now introduce another example for a code.

• $k = 2^m -1$
• EC: XOR over all active indices (containing 1s) in data. (first index is 1)

Example:

• data = 0110110
• $k = 2^3-1=7$
• EC = 010 + 011 + 101 + 110 = 010 (active indices are 2,3,5,6)
• message = 0110110010

Q1: What is the length of the EC? What is n?

$|EC| = \lfloor\log_2{2^m-1}\rfloor + 1$

$n = 2^m + m - 1$

Q2: What is d? How many errors can be detected and fixed?

• d = 2
• detect: 1
• fix: 0

Example: 0000000 000 0001000 100

Q3 Improvement A - transmit EC twice. What are n,k,d now?

• $n = 2^m -1 + 2m$
• $k=2^m-1$
• d=3, can fix 1 error

Q4: What's the decoding algorithm, given that we expect no more than 1 error?

Remember to treat the cases of 0 or 1 errors.

decode(transmitted message)

• Compute EC from first k bits
• If EC = EC1 or EC = EC2: return first k bits
• Else: XOR(EC,ECX) gives the index of the single error (where ECX is either EC1 or EC2, depending on which was not equal to EC)

Example:

1. Encoding: 0110110 -> 0110110 010 010
2. Transmission error: 0110110 010 010 -> 0110010 010 010
3. Decoding: 0110010 010 010
   • EC = 2 + 3 + 6 = 010 + 011 + 110 = 111 != 010
   • Error bit at 111 + 010 = 101 = 5
4. Correction: 0110010 -> 0110110

Q5: What happens if we have 2 errors?

In this case we will think there is one error, try to correct, and will insert a third error.

Example:

1. Decoding: 0010010 010 010
   • EC = 3 + 6 = 011 + 110 = 101 != 010
   • Error bit at 101 + 010 = 111 = 7
   • Correction: 0010010 -> 0010011 != 0110110

Q6: Improvment B - add parity bit at the end

What is the value of d now?

Before, we had d=3. So the closet words were 3 bits apart. Therefore, they differ in parity, and are now 4 bits apart - d=4. We can now detect 3 and fix 1.

Q7: Can be sitringuish between 0, 1 and 2 errors? How about 3 errors?

Examle for not detectin 3 bits by EC:

0010110 000 000 1

Q8: What's the decoding algorithm given we expect no more than 2 errors?

We use the above table.

• EC and parity are V - no errors, return data
• Parity is X - single error, fix.
• EC is X, parity is V - two errors, don't fix.

What can we do with the knowledge that we have an error if we cannot fix it?

Q9: Improvement C: iterated/turbo decoding

Pack several messages into a matrix and add EC for matrix columns. Now, even if we have two errors in a row, we might be able to fix each of them, if they are the sole errors in their columns. We might even be able to iterate and fix several errors.

What is a scenario we cannot fix with at most 2 errors in evey row/column?

A rectangle of 4 errors.

Fin

This notebook is part of the Extended introduction to computer science course at Tel-Aviv University.

The notebook was written using Python 3.2 and IPython 0.13.1.

The code is available at https://raw.github.com/yoavram/CS1001.py/master/recitation14.ipynb.

The notebook can be viewed online at http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation14.ipynb.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.