{ "metadata": { "name": "recitation14" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# CS1001.py\n", "\n", "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n", "\n", "# Recitation 14 - 17-20.6.2013\n", "\n", "## Last update: 16.6.2013" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Error detection and correction\n", "\n", "When we send data, we send data + error correction information (EC). \n", "Although longer, this transmission will allow detecting and correcting errors in transmission.\n", "\n", "#### Definitions\n", "\n", "- `k` \u2013 len of original message \n", "- `n` \u2013 len of transmitted message (data + EC) \n", "\n", "- The *Hamming distance* between two `n`-bit long messages is the numbers of differences between them.\n", "Example: \n", " \n", "$$HD(01000,11010) = 2$$\n", "\n", "- `d` is the minimal HD between any 2 possible `n`-messages.\n", "\n", "- An `(n,k,d)` code is able to detect `d-1` errors, and fix \u0001$\\frac{d-1}{2}$ errors. \n", "\n", "## Repetition code\n", "\n", "Transmitting each bit `p` times.\n", "\n", "data = 10 \n", "`p` = 4\n", "data + EC = 11110000\n", "`d` = 4\n", "\n", "## Other codes from lecture\n", "\n", "- Parity bit (xor) \n", "- 2D parity bit (card magic) \n", "- Israeli ID control digit \n", "- Hamming (7,4,3) code \n", "\n", "## Index code\n", "We will now introduce another example for a code.\n", "\n", "- $k = 2^m -1$\n", "- EC: XOR over all active indices (containing `1`s) in data. (first index is 1)\n", "\n", "Example:\n", "\n", "- data = 0110110\n", "- $k = 2^3-1=7$\n", "- EC = 010 + 011 + 101 + 110 = 010 (active indices are 2,3,5,6)\n", "- message = 0110110010\n", "\n", "#### Q1: What is the length of the EC? What is `n`?\n", "\n", "$|EC| = \\lfloor\\log_2{2^m-1}\\rfloor + 1$\n", "\n", "$n = 2^m + m - 1$\n", "\n", "#### Q2: What is `d`? How many errors can be detected and fixed?\n", "\n", "- `d` = 2\n", "- detect: 1\n", "- fix: 0\n", "\n", "Example:\n", "0000000 000 \n", "0001000 100\n", "\n", "#### Q3 Improvement A - transmit EC twice. What are `n`,`k`,`d` now?\n", "\n", "- $n = 2^m -1 + 2m$\n", "- $k=2^m-1$\n", "- `d`=3, can fix 1 error\n", "\n", "#### Q4: What's the decoding algorithm, given that we expect *no more than 1 error*? \n", "Remember to treat the cases of 0 or 1 errors.\n", "\n", "**decode(transmitted message)**\n", "\n", "- Compute EC from first `k` bits\n", "- If EC = EC1 or EC = EC2: return first `k` bits\n", "- 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)\n", "\n", "Example:\n", "\n", "1. Encoding: 0110110 -> 0110110 010 010\n", "2. Transmission error: 0110110 010 010 -> 0110**0**10 010 010\n", "3. Decoding: 0110010 010 010\n", " - EC = 2 + 3 + 6 = 010 + 011 + 110 = 111 != 010\n", " - Error bit at 111 + 010 = 101 = 5\n", "4. Correction: 0110010 -> 0110110\n", "\n", "#### Q5: What happens if we have 2 errors?\n", "\n", "In this case we will think there is one error, try to correct, and will insert a third error.\n", "\n", "Example:\n", "\n", "3. Decoding: 0**0**10**0**10 010 010\n", " - EC = 3 + 6 = 011 + 110 = 101 != 010\n", " - Error bit at 101 + 010 = 111 = 7\n", " - Correction: 0010010 -> 0010011 != 0110110\n", "\n", "#### Q6: Improvment B - add *parity* bit at the end\n", "\n", "What is the value of `d` now?\n", "\n", "Before, we had `d`=3. So the closet words were 3 bits apart.\n", "Therefore, they differ in parity, and are now 4 bits apart - `d`=4.\n", "We can now detect 3 and fix 1.\n", "\n", "#### Q7: Can be sitringuish between 0, 1 and 2 errors? How about 3 errors?\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
# errorsEC vs EC1 vs EC2parity
0VV
1X or V (if error in parity)X
2XV
3X or V (example below)X
\n", "\n", "Examle for not detectin 3 bits by EC:\n", "\n", "0**0**10110 0**0**0 0**0**0 1\n", "\n", "#### Q8: What's the decoding algorithm given we expect no more than 2 errors?\n", "\n", "We use the above table.\n", "\n", "- EC and parity are V - no errors, return data\n", "- Parity is X - single error, fix.\n", "- EC is X, parity is V - two errors, don't fix.\n", "\n", "What can we do with the knowledge that we have an error if we cannot fix it?\n", "\n", "\n", "#### Q9: Improvement C: iterated/turbo decoding\n", "\n", "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.\n", "We might even be able to iterate and fix several errors.\n", "\n", "What is a scenario we cannot fix with at most 2 errors in evey row/column?\n", "\n", "A rectangle of 4 errors." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Fin\n", "This notebook is part of the [Extended introduction to computer science](http://tau-cs1001-py.wikidot.com/) course at Tel-Aviv University.\n", "\n", "The notebook was written using Python 3.2 and IPython 0.13.1.\n", "\n", "The code is available at .\n", "\n", "The notebook can be viewed online at .\n", "\n", "This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)." ] } ], "metadata": {} } ] }