{
"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",
"