{ "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", "
# errors | EC vs EC1 vs EC2 | parity | \n", "
---|---|---|
0 | V | V | \n", "
1 | X or V (if error in parity) | X | \n", "
2 | X | V | \n", "
3 | X or V (example below) | X | \n", "