v1.0 (2014 Fall) Kangwook Lee **, Kannan Ramchandran **
v1.1 (2015 Fall) Kabir Chandrasekher *, Max Kanwal *, Kangwook Lee **, Kannan Ramchandran **
v1.2 (2016 Spring) Kabir Chandrasekher, Tony Duan, David Marn, Ashvin Nair, Kangwook Lee, Kannan Ramchandran
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!
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?
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).
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.
So what's the secret to this magic? It's a two step process of clever encoding and decoding:
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!
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:
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.
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import json
import random
class Packet:
size_of_packet = 256
def __init__(self, chunks, chunk_indices):
self.data = self.add(chunks)
self.chunk_indices = chunk_indices
def add(self, chunks):
tmp = np.zeros(Packet.size_of_packet, 'uint8')
for each_chunk in chunks:
tmp += each_chunk
return tmp
def num_of_chunks(self):
return len(self.chunk_indices)
You can initiate an encoder with a string! Then, generate_packet() will return a randomly encoded packet.
class Transmitter:
def __init__(self, chunks, channel, degree_distribution):
self.chunks = chunks
self.num_chunks = len(chunks)
self.channel = channel
self.degree_distribution = degree_distribution
def generate_new_packet(self):
if self.degree_distribution == 'single':
#Always give a degree of 1
n_of_chunks = 1
elif self.degree_distribution == 'double':
#Always give a degree of 2
n_of_chunks = 2
elif self.degree_distribution == 'mixed':
#Give a degree of 1 half the time, 2 the other half
if random.random() < 0.5:
n_of_chunks = 1
else:
n_of_chunks = 2
elif self.degree_distribution == 'baseline':
"""
Randomly assign a degree from between 1 and 5.
If num_chunks < 5, randomly assign a degree from
between 1 and num_chunks
"""
n_of_chunks = random.randint(1,min(5, self.num_chunks))
chunk_indices = random.sample(range(self.num_chunks), n_of_chunks)
chunks = [ self.chunks[x] for x in chunk_indices ]
return Packet( chunks, chunk_indices )
def transmit_one_packet(self):
packet = self.generate_new_packet()
self.channel.enqueue( packet )
Channel class takes a packet and erase it with probability eps.
class Channel:
def __init__(self, eps):
self.eps = eps
self.current_packet = None
def enqueue(self, packet):
if random.random() < self.eps:
self.current_packet = None
else:
self.current_packet = packet
def dequeue(self):
return self.current_packet
You can initiate a decoder with the total number of chunks. Then, add_packet() will add a received packet to the decoder.
class Receiver:
def __init__(self, num_chunks, channel):
self.num_chunks = num_chunks
self.received_packets = []
self.chunks = [ ]
for i in range(self.num_chunks):
self.chunks.append( np.zeros(Packet.size_of_packet, 'uint8') )
self.found = [ False for x in range(self.num_chunks) ]
self.channel = channel
def receive_packet(self):
packet = self.channel.dequeue()
if not packet == None:
self.received_packets.append( packet )
if packet.num_of_chunks() == 1:
self.peeling()
def peeling(self):
flag = True
while flag:
flag = False
for each_packet in self.received_packets:
if each_packet.num_of_chunks() == 1: # Found a singleton
flag = True
idx = each_packet.chunk_indices[0]
break
# First, declare the identified chunk
if self.found[ idx ] == False:
self.chunks[ idx ] = np.array(each_packet.data, 'uint8')
self.found[ idx ] = True
# Second, peel it off from others
for each_packet in self.received_packets:
if idx in each_packet.chunk_indices:
each_packet.chunk_indices.remove( idx )
each_packet.data -= self.chunks[ idx ]
def isDone(self):
return self.chunksDone() == self.num_chunks
def chunksDone(self):
return sum(self.found)
from scipy import misc
import matplotlib.cm as cm
import Image
import numpy as np
l = np.asarray(plt.imread("raccoon.jpg"))
#converts the image to grayscale
x = np.zeros((512,512))
for i in xrange(512):
for j in xrange(512):
x[i][j] = l[i][j][0]*0.299+l[i][j][1]*0.587+l[i][j][2]*0.113
plt.imshow(x, cmap = cm.Greys_r)
tt= x.reshape(1,512*512)[0]
size_of_packet = 256
num_of_packets = 1024
assert len(tt) == size_of_packet * num_of_packets
# Your code here
You may find the following function useful:
def visualize( chunks ):
plt.imshow(chunks, cmap = cm.Greys_r)
eps = 0.2
ch = Channel(eps)
tx = Transmitter( chunks, ch, 'single' )
rx = Receiver( len(chunks), ch )
ct = 0
intermediate_data = []
current_sent = []
while not rx.isDone():
tx.transmit_one_packet()
rx.receive_packet()
ct += 1
if ct % 100 == 0:
intermediate_data.append( np.array(rx.chunks, 'uint8').reshape(512,512) )
current_sent.append(sum(rx.found))
received_data = np.array(rx.chunks, 'uint8').reshape(512,512)
print "The number of packets received: {}".format(ct)
### Incrementally show the data received
n_of_figures = int(ct/100)
fig = plt.figure( figsize=(8, 3*n_of_figures) )
for i in range(n_of_figures-1):
fig.add_subplot(n_of_figures,1,i+1)
visualize(intermediate_data[i])
fig.add_subplot(n_of_figures,1,n_of_figures)
visualize(received_data)
#Your plotting code here
Hint: Try out some small examples!
eps = 0.2
ch = Channel(eps)
tx = Transmitter( chunks, ch, 'double' )
rx = Receiver( len(chunks), ch )
ct = 0
while not rx.isDone():
tx.transmit_one_packet()
rx.receive_packet()
ct += 1
received_data = np.array(rx.chunks, 'uint8').reshape(512,512)
print "The number of packets received: {}".format(ct)
eps = 0.2
num_trials = 1
ch = Channel(eps)
tx_baseline = Transmitter( chunks, ch, 'baseline' )
baseline_packets = []
current_baseline = []
for _ in xrange(num_trials):
rx = Receiver( len(chunks), ch )
ct = 0
intermediate_data = []
while not rx.isDone():
tx_baseline.transmit_one_packet()
rx.receive_packet()
ct += 1
if ct % 100 == 0:
current_baseline.append(sum(rx.found))
baseline_packets.append(ct)
#Plotting code here
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.
Good luck!
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!
Besides the top 3 submissions:
#Your code here
Report the average score (averaged over 10 trials):
Answer the following in 1-2 paragraphs (this should be answered individually):
Your Response Here