{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lab 4 - Codes for Efficient Transmission of Data\n", "\n", "#### Authors:\n", "\n", "v1.0 (2014 Fall) Kangwook Lee \\*\\*, Kannan Ramchandran \\*\\*
\n", "\n", "v1.1 (2015 Fall) Kabir Chandrasekher \\*, Max Kanwal \\*, Kangwook Lee \\*\\*, Kannan Ramchandran \\*\\*
\n", "\n", "v1.2 (2016 Spring) Kabir Chandrasekher, Tony Duan, David Marn, Ashvin Nair, Kangwook Lee, Kannan Ramchandran
\n", "\n", "\n", "In last week's lab, we learned about source coding and then briefly touched upon the channel coding problem. We learned about the simplest and most intuitive code: repetition codes. This week you will explore implementing your own code for transmission of data! \n", "\n", "To see why efficient coding techniques are important, consider an erasure channel in which each packet sent gets dropped with some probability $p$. If we wanted to convey a message, we could consider a feedback channel in which the receiver tells the sender which messages were received and the sender re-sends the dropped packets. This process can be repeated until the receiver gets all of the intended message. While this procedure is indeed optimal in all senses of the word, feedback is simply not possible in many circumstances. What can we do in this situation?\n", "\n", "In this lab, we will be looking at a specific type of code that will apply your knowledge of random bipartite graphs (the balls and bins model)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction \n", "\n", "The coding scheme we will work with in this lab will be a type of erasure code. Under the binary erasure channel (BEC) model, bits that are sent through a noisy channel either make it through unmodified or are tagged as \"corrupt\", in which case the recieved information is dropped in all further information processing steps. \n", "
\n", "A code is considered optimal generally when all $n$ source symbols that need transmitting can be recovered from *any* $n$ encoded symbols. Think of it this way: \n", "You want to stream the new season of House of Cards from Netflix at midnight. But so do 1 million other people! Obviously the server loads are going to be high, so how can Netflix ensure that everyone watches without intermittent lags (which are frustrating and will lose them customers)? Well, one way is to increase the number of servers so that the load on any one server is decreased, but this costs a lot of money. Another important thing for them to consider is in the transmission process. When users are downloading the movie, Netflix servers don't want to have too much overhead to figure out which users need which bits of the video to get smooth playback. If they use near-optimal codes to encode and constantly send out the same random chunks of the video's data to all users, then they can be sure that users get what they need in only a little more than $n$ transmissions *no matter what parts of the show each individual user lost through their specific channel*!\n", "\n", "So what's the secret to this magic? It's a two step process of clever encoding and decoding:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Encoding\n", "1. For $n$ packets you want to transmit in total, pick $d$ such that $1\\leq d \\leq n$ according to some distribution.\n", "2. With $d$ picked, now select $d$ random packets of the $n$ and combine the bits together using the XOR operator.\n", "3. Transmit this combined packet, along with the metadata telling which actual packet indices were XOR'd.\n", "\n", "### Decoding\n", "1. Reconstruct the list of packet indices which were XOR'd (in our case these are just explicitly sent with the data)\n", "2. For each source packet, check if the packet is a singleton, in which case the encoded packet is exactly equal to the actual packet. If not, we can check if any of the packets that have been XOR'd are already known, in which case XOR that packet with the encoded packet and remove it from the list of packet indices that make up the encoded chunk.\n", "3. If there are two or more indices in the list for the encoded packet we cannot figure out any more information! Put it on the side for looking at later.\n", "4. With any newly decoded information, we may be able to decode previously undecodable packets that we had put on the side. Go through all unsolved packets and try to decode more packets until nothing more can be done.\n", "5. Wait for the next encoded packet to come and repeat!\n", "\n", "Now what's left for you to do? Well, remember that number $d$? It needs to be picked according to some distribution, and which distribution is the million dollar question!\n", "\n", "\n", "### Example\n", "
\n", "\n", "Consider the above bipartite graph. Here, $x_i$ represents the encoded incoming packet, $y_i$ represents the actual packet, and the edges represent the actual packets that make up each encoded packet. Consider each $x_i$ coming in chronologically:\n", "1. For incoming packets $x_1, x_2, x_3$ we will not be able to decode anything.\n", "2. As soon as $x_4$ comes, we see that it is a singleton. This means that $y_4$ can be fully recovered from $x_4$. \n", "3. Finally, when $x_5$ comes in, we can suddenly decode everything: $x_5$ is made up of $y_4$ and $y_5$, but we already know $y_4$, so we can then fully decode $y_5$. Similarly, we can then decode $y_3$, then $y_1$, and lastly $y_2$ (in that order specifically).\n", "\n", "As you might be able to tell, by choosing a good degree distribution for $d$, even when random incoming packets were lost (not shown), you were still able to recover all $5$ symbols only from $5$ received packets, despite the sender not knowing what packets you lost through the BEC." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1) Packet Class & Utility functions\n", "\n", "A packet consists of...\n", "\n", "#### ['chunk_indices', 'data' ]\n", "\n", "##### chunk_indices: Which packets are chosen\n", "\n", "##### data: The 'XOR'ed data (we will just add the bits in this lab for simplicity)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%matplotlib inline \n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import json\n", "import random\n", "\n", "class Packet:\n", " size_of_packet = 256\n", " def __init__(self, chunks, chunk_indices):\n", " self.data = self.add(chunks)\n", " self.chunk_indices = chunk_indices\n", "\n", " def add(self, chunks):\n", " tmp = np.zeros(Packet.size_of_packet, 'uint8')\n", " for each_chunk in chunks:\n", " tmp += each_chunk\n", " return tmp\n", " \n", " def num_of_chunks(self):\n", " return len(self.chunk_indices)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Transmitter & Encoder Class\n", "\n", "You can initiate an encoder with a string! Then, generate_packet() will return a randomly encoded packet." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class Transmitter:\n", " def __init__(self, chunks, channel, degree_distribution):\n", " self.chunks = chunks\n", " self.num_chunks = len(chunks)\n", " self.channel = channel\n", " self.degree_distribution = degree_distribution\n", " \n", " def generate_new_packet(self):\n", " if self.degree_distribution == 'single':\n", " #Always give a degree of 1\n", " n_of_chunks = 1\n", " elif self.degree_distribution == 'double':\n", " #Always give a degree of 2\n", " n_of_chunks = 2\n", " elif self.degree_distribution == 'mixed':\n", " #Give a degree of 1 half the time, 2 the other half\n", " if random.random() < 0.5:\n", " n_of_chunks = 1\n", " else:\n", " n_of_chunks = 2\n", " elif self.degree_distribution == 'baseline':\n", " \"\"\"\n", " Randomly assign a degree from between 1 and 5.\n", " If num_chunks < 5, randomly assign a degree from \n", " between 1 and num_chunks\n", " \"\"\"\n", " n_of_chunks = random.randint(1,min(5, self.num_chunks))\n", " chunk_indices = random.sample(range(self.num_chunks), n_of_chunks)\n", " chunks = [ self.chunks[x] for x in chunk_indices ]\n", " return Packet( chunks, chunk_indices )\n", " \n", " def transmit_one_packet(self):\n", " packet = self.generate_new_packet()\n", " self.channel.enqueue( packet )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Channel Class\n", "\n", "Channel class takes a packet and erase it with probability eps." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Channel:\n", " def __init__(self, eps):\n", " self.eps = eps\n", " self.current_packet = None\n", " \n", " def enqueue(self, packet):\n", " if random.random() < self.eps:\n", " self.current_packet = None\n", " else:\n", " self.current_packet = packet\n", " \n", " def dequeue(self):\n", " return self.current_packet" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4) Receiver & Decoder Class\n", "\n", "You can initiate a decoder with the total number of chunks. Then, add_packet() will add a received packet to the decoder." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class Receiver:\n", " def __init__(self, num_chunks, channel):\n", " self.num_chunks = num_chunks\n", " self.received_packets = []\n", " self.chunks = [ ]\n", " for i in range(self.num_chunks):\n", " self.chunks.append( np.zeros(Packet.size_of_packet, 'uint8') )\n", " self.found = [ False for x in range(self.num_chunks) ]\n", " self.channel = channel\n", " \n", " def receive_packet(self):\n", " packet = self.channel.dequeue()\n", " if not packet == None:\n", " self.received_packets.append( packet )\n", " if packet.num_of_chunks() == 1:\n", " self.peeling()\n", " \n", " def peeling(self):\n", " flag = True\n", " while flag:\n", " flag = False\n", " for each_packet in self.received_packets:\n", " if each_packet.num_of_chunks() == 1: # Found a singleton\n", " flag = True\n", " idx = each_packet.chunk_indices[0]\n", " break\n", " \n", " # First, declare the identified chunk\n", " if self.found[ idx ] == False:\n", " self.chunks[ idx ] = np.array(each_packet.data, 'uint8')\n", " self.found[ idx ] = True\n", " # Second, peel it off from others\n", " for each_packet in self.received_packets:\n", " if idx in each_packet.chunk_indices:\n", " each_packet.chunk_indices.remove( idx )\n", " each_packet.data -= self.chunks[ idx ]\n", " \n", " def isDone(self):\n", " return self.chunksDone() == self.num_chunks\n", "\n", " def chunksDone(self):\n", " return sum(self.found)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathcal{Q}$uestion 1. Sending the raccoon\n", "### a. Break up the image shown below into $1024$ packets of size $256$ each." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from scipy import misc\n", "import matplotlib.cm as cm\n", "import Image\n", "import numpy as np\n", "l = np.asarray(plt.imread(\"raccoon.jpg\"))\n", "#converts the image to grayscale\n", "x = np.zeros((512,512))\n", "for i in xrange(512):\n", " for j in xrange(512):\n", " x[i][j] = l[i][j][0]*0.299+l[i][j][1]*0.587+l[i][j][2]*0.113\n", "\n", "plt.imshow(x, cmap = cm.Greys_r)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "tt= x.reshape(1,512*512)[0]\n", "size_of_packet = 256 \n", "num_of_packets = 1024\n", "assert len(tt) == size_of_packet * num_of_packets\n", "\n", "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### b. Using the 'single' degree distribution defined in the Transmitter class, send the raccoon over a channel with erasure probability 0.2. How many packets did you need to send? Display the data you receive every $100$ packets in addition to the data you receive at the end.\n", "\n", "### i. Plot the number of packets decoded as a function of the number of packets you receive. (The current_sent array should be helpful here)\n", "\n", "You may find the following function useful:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def visualize( chunks ):\n", " plt.imshow(chunks, cmap = cm.Greys_r)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [], "source": [ "eps = 0.2\n", "ch = Channel(eps)\n", "tx = Transmitter( chunks, ch, 'single' )\n", "rx = Receiver( len(chunks), ch )\n", "\n", "ct = 0\n", "intermediate_data = []\n", "current_sent = []\n", "while not rx.isDone():\n", " tx.transmit_one_packet()\n", " rx.receive_packet()\n", " ct += 1\n", " if ct % 100 == 0: \n", " intermediate_data.append( np.array(rx.chunks, 'uint8').reshape(512,512) )\n", " current_sent.append(sum(rx.found))\n", "\n", "received_data = np.array(rx.chunks, 'uint8').reshape(512,512)\n", "print \"The number of packets received: {}\".format(ct)\n", "\n", "### Incrementally show the data received\n", "n_of_figures = int(ct/100)\n", "fig = plt.figure( figsize=(8, 3*n_of_figures) )\n", "\n", "for i in range(n_of_figures-1):\n", " fig.add_subplot(n_of_figures,1,i+1)\n", " visualize(intermediate_data[i])\n", "\n", "fig.add_subplot(n_of_figures,1,n_of_figures)\n", "visualize(received_data)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Your plotting code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### b ii. Looking at the graph, we see that it gets harder and harder to find the rest as we decode more and more chunks. Does this remind you of a well known theoretical problem?\n", "Hint: Try out some small examples!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Your answer here." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### c. Using the 'double' degree distribution defined in the Transmitter class, send the raccoon over a channel with erasure probability 0.2. What happens?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "eps = 0.2\n", "ch = Channel(eps)\n", "tx = Transmitter( chunks, ch, 'double' )\n", "rx = Receiver( len(chunks), ch )\n", "\n", "ct = 0\n", "while not rx.isDone():\n", " tx.transmit_one_packet()\n", " rx.receive_packet()\n", " ct += 1\n", "\n", "received_data = np.array(rx.chunks, 'uint8').reshape(512,512)\n", "print \"The number of packets received: {}\".format(ct)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### d. You have seen two degree distributions so far. Both of these have been deterministic, and one worked better than the other. Let's try one final degree distribution. Using the 'baseline' degree distribution, send the raccoon over a channel with erasure probability 0.2. Plot the number of packets decoded against the number of packets transmitted." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "eps = 0.2\n", "num_trials = 1\n", "ch = Channel(eps)\n", "tx_baseline = Transmitter( chunks, ch, 'baseline' )\n", "baseline_packets = []\n", "current_baseline = []\n", "\n", "for _ in xrange(num_trials):\n", " rx = Receiver( len(chunks), ch )\n", " ct = 0\n", " intermediate_data = []\n", " while not rx.isDone():\n", " tx_baseline.transmit_one_packet()\n", " rx.receive_packet()\n", " ct += 1\n", " if ct % 100 == 0: \n", " current_baseline.append(sum(rx.found))\n", " baseline_packets.append(ct)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Plotting code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathcal{C}$ompetition\n", "\n", "Alice has just finished eating dinner, and with her EE 126 homework completed early for once, she plans to sit down for a movie night (she wants to make use of the 30-day free trial of Netflix!). While Alice is surfing Netflix she decides she wants to stream Interstellar. Alice's laptop drops packets with $p=0.25$. You, the Chief Technology Officer of Netflix, know that given the heavy workload of EE 126, this may be your only chance to convert this freeloading customer into a permanent one, but to do so you're going to have to make sure her viewing experience is perfect.\n", "\n", "### Concrete specs:\n", "\n", "- You are given an erasure channel with drop probability $p=0.25$.\n", "- You must define a degree distribution (which can vary as a function of the # of transmissions already sent) to minimize the number of total packets needed to be sent to Alice for her to decode their images. Run your code for 10 trials to get a good estimate of the true number of transmissions needed per image while they watch their movies. Each trial, your score is $\\frac{\\text{# of packets successfully decoded from the first 512 packets}}{512}+\\frac{\\text{# of packets successfully decoded from the first 1024 packets}}{1024}+\\lfloor\\frac{\\text{# of packets successfully decoded from the first 2048 packets}}{1024}\\rfloor+\\lfloor\\frac{\\text{# of packets successfully decoded from the first 4096 packets}}{1024}\\rfloor+\\lfloor\\frac{\\text{# of packets successfully decoded from the first 6144 packets}}{1024}\\rfloor$.\n", "- Note the floor function in the later stages - you can only get the point if you fully decode the file with the alloted number of packets\n", "- **You may work in teams of up to three.**\n", "\n", "Good luck! \n", "\n", "*If you place in the top 3 in the class you will be awarded bonus points and full credit for the homework, as well as get to present your strategy to the entire course staff!* \n", "\n", "Besides the top 3 submissions: \n", "# Everyone who scores above 3 points will receive bonus credit that is proportional to their score!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### $\\mathcal{R}$esults\n", "\n", "Report the average score (averaged over 10 trials):" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\text{Average Score: } \\boxed{}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### $\\mathcal{S}$ummary\n", "\n", "Answer the following in 1-2 paragraphs (this should be answered individually): \n", "- Who were your teammates?\n", "- What did you learn? \n", "- What is the basic inuition behind your final strategy? \n", "- How did your strategy evolve from your first attempt (what worked and what failed)?\n", "- How would your strategy change if the value of $p$ of the BEC was not known?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Your Response Here" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }