{ "metadata": { "name": "", "signature": "sha256:9ebca578abaeb65d1b0813625499185a6f0a7eabed5b35515db9c06a7b971680" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Viterbi\n", "\n", "Alice and Bob are working together to bake some treats while they are home for winter break.\n", "Alice is in charge of sending Bob the recipe, and Bob is responsible for following directions.\n", "Bob is *extremely* literal- if an error in the recipe says to use 2000 eggs instead of 2, he will use 2000 eggs without a second thought.\n", "Alice is aware of Bob's lack of common sense, but she is also busy.\n", "She already has the recipe open on her phone, so she wants to send it via email (using wifi) to Bob.\n", "Unfortunately, Alice's evil next-door-neighboor Eve has her microwave running continuously at maximum power.\n", "Microwaves emit a lot of radiation around wifi's 2.4GHz channels, causing interference.\n", "This lab will explore different techniques for ensuring that Alice's message will make it to Bob uncorrupted." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Preliminaries\n", "\n", "We assume that Alice's message is $N$ bits long with each bit iid Bernoulli(0.5).\n", "We model the channel as a [binary symmetric channel](http://en.wikipedia.org/wiki/Binary_symmetric_channel), as shown below.\n", "Each bit sent through the channel is flipped (independently) with probability p.\n", "We'll assume p=0.05, which is a fairly typical value for wireless communications.\n", "\n", "![Alt](http://upload.wikimedia.org/wikipedia/commons/8/8e/Binary_symmetric_channel_%28en%29.svg)\n", "\n", "We assume that Alice and Bob use some sort of message integrity check in their message (like a [CRC](http://en.wikipedia.org/wiki/Cyclic_redundancy_check)) - to keep things simple, let's assume Bob can detect any error with probability 1.\n", "\n", "We also assume that Bob sends Alice an ACK or NACK and assume that this message always succeeds.\n", "If Bob sends an ACK, Alice knows Bob got the message.\n", "If Bob sends a NACK, Alice tries to send again." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Repetition Code\n", "We need a way to correct errors introduced by our noisy channel.\n", "One of the simplest error correcting codes is the [repetition code](http://en.wikipedia.org/wiki/Repetition_code).\n", "\n", "Repetition coding works by having Alice send each bit of her message $r$ times.\n", "For each bit, Bob uses majority logic - i.e. for $r=3$ if he gets two 1s and one 0, he will decide 1.\n", "The code below computes the probability that the message is corrupted for various values of $r$." ] }, { "cell_type": "code", "collapsed": false, "input": [ "%pylab\n", "%matplotlib inline\n", "from scipy.stats import binom \n", "r=[2*i+1 for i in range(15)]\n", "def single_bit_error(r, p=0.05):\n", " return 1-binom.cdf(r//2, r, p)\n", "def message_error(r, p=0.05):\n", " return 1-(1-single_bit_error(r,p))**256\n", "message_error(12)\n", "semilogy(r, [message_error(i) for i in r])" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is good! We can get to low probabilities of error if we increase the number of repetitions.\n", "However, increasing the number of repetitions means we are sending a lot more data, lowering Alice's effective datarate.\n", "Alice's phone also has limited battery life, and sending lots of copies of the same data consumes a lot of energy.\n", "Is it possible to correct a lot of errors without having to send so many extra bits?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Shannon says that we should be able to do much better.\n", "Using random coding with infinite block length, we can achieve capacity, which for the BSC is $1-H(p) \\approx 0.71$ bits per channel use for $p=0.05$.\n", "This is way better than the $\\frac{1}{r}$ channel uses per bit given by repetition coding.\n", "\n", "Using random codes sounds great for Alice, but what about Bob?\n", "How is he supposed to decode what Alice is sending him?\n", "It is not clear how much computation it will take for him to do a good job decoding.\n", "He could try syndrome decoding or some other exhaustive search, but this takes exponential time (or space) in the length of the message, which could be really long!\n", "\n", "Is there something better?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Convolutional Coding\n", "Yes! The 802.11 standards for wifi use convolutional codes and LDPC codes to correct errors.\n", "Convolutional codes can be efficiently decoded using the Viterbi algorithm, so they will be the focus of this lab.\n", "\n", "\n", "The above picture is a block diagram for a simple convolutional encoder.\n", "The input message is treated as a stream of bits.\n", "The input is shifted through a series of delays - at time t, the input is in[t], the first delay element (the \"D\" on the left) contains in[t-1], and the last delay elements (the \"D\" on the right) contains in[t-2].\n", "In this example, each input bit produces two output bits - the first output computed by the top \"adder\" and the second output computed by the bottom \"adder\".\n", "These additions are modulo-2, so each output is a 0 or 1 bit.\n", "In this example, the first (top) output at time t is computed as (in[t]+in[t-2]) mod 2.\n", "The second (bottom) output at time t is computed as (in[t]+in[t-1]+in[t-2]) mod 2.\n", "The two outputs are interleaved into one bitstream so the output is (top[0], bottom[0], top[1], bottom[1], top[2], bottom[2], ...).\n", "\n", "The first thing to note is that this is not actually all the different from repetition coding.\n", "Like repetition coding, we are adding redundancy by generating multiple output bits per input bit.\n", "However, unlike repetition coding, convolutional codes have memory.\n", "Each output bit is a function of multiple input bits.\n", "The idea is that if there is an error, you should be able to use the surrounding bit estimates to help you figure out what was actually sent.\n", "\n", "The figure below shows the state transition diagram corresponding to the example encoder above.\n", "Each transition is labelled input/(top, bottom).\n", "Each state represents the contents of the delays, with the most significant bit being the last (right) delay.\n", "Be sure to convince yourself that the encoder above is equivalent to the state transition diagram below.\n", "\n", "\n", "\n", "If we assume that the input bits are iid Bernoulli(0.5), this is a Markov chain with every state equally likely.\n", "We can run the Viterbi algorithm on our output bits (even after going through a noisy channel) to recover a good estimate of the input bits.\n", "\n", "An implementation for a Viterbi decoder can be constructed as follows:\n", "1. A state $s$ has a *path metric* $p_s$ that gives the number of observed bit errors associated with being in $s$ at a given time.\n", "2. A state $s$ and input bit $b$ have *branch metric* $b_{s,b}$ that compares the observed channel output to the expected output given that you were in state $s$ and had input bit $b$. The branch metric is the number of different bits between the observed and expected output (Hamming weight).\n", "3. If input $b$ has transitions from state $s$ to $s'$, we can compute an updated path metric as $p_s + b_{s,b}$.\n", "4. Each state $s'$ will have two incoming transitions, we select the minimum $p_s+b_{s,b}$ and call that our new path metric $p_s'$. This is called Add-Compare-Select.\n", "5. Traceback uses the decisions at each add-compare-select to reconstruct the input bit sequence.\n", "Starting at the ending state with the smallest path metric, traceback finds the predecessor based on the decision made by the add-compare-select unit.\n", "For example, if at the end, state zero has the lowest path metric, and the last add-compare-select for state zero chose the path_metric coming from state 2, we know that the last input bit was zero and the previous state was 2. This continues backwards until it reaches the beginning.\n", "\n", "[This link](http://home.netcom.com/~chip.f/viterbi/algrthms2.html) may be a helpful resource for understanding implementing the Viterbi algorithm for convolutional codes (note that what we are designing is called a hard decoder- soft decoders are a refinement that we won't worry about).\n", "\n", "We assume that we start and end in state 0.\n", "We end in state 0 by appending enough 0s to the end of our input to force us into 0.\n", "Our decoder relies on this by initializing all path metrics to a big number, except for 0 which we initialize to 0.\n", "\n", "## Q1\n", "In the space below, implement a viterbi decoder for our 4-state example code.\n", "\n", "## A1" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy as np\n", "def apply_generator(state, generator):\n", " return reduce(lambda x,y: x^y, map(lambda x: x[0]*x[1], zip(state,generator)), 0)\n", "\n", "example_generators=[[1,0,1], [1,1,1]]\n", "def encode(bits_in, generators=example_generators):\n", " l = max(map(len, generators))\n", " bits_in = list(bits_in) + [0]*(l-1) # end in state 0\n", " state = [0]*l\n", " output = []\n", " for b in bits_in:\n", " state[1:] = state[:-1]\n", " state[0] = b\n", " for g in generators:\n", " output.append(apply_generator(state, g))\n", " return output\n", "\n", "def bsc(bits_in, p=0.05):\n", " out = []\n", " for b in bits_in:\n", " if np.random.uniform() > p:\n", " out.append(b)\n", " else:\n", " out.append(1-b)\n", " return out\n", " \n", "def int2state(i, w):\n", " return [i&(1<0 for k in range(w)]\n", "\n", "def viterbi(bits_in, generators=example_generators):\n", " pass" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "code", "collapsed": false, "input": [ "# Test your code here\n", "a=encode( (1,0,1,1,1,1,1,1))\n", "b=bsc(a,p=0.05)\n", "c=viterbi(b)\n", "print a\n", "print b\n", "print c" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "The above picture shows the convolutional encoder actually used by the wifi standards.\n", "This encoder still puts out two output bits per input bit, but there are a lot more states.\n", "This means it might be able to do a better job correcting errors, but it increases the amount of computation our decoder needs to perform.\n", "\n", "## Q2\n", "After you have your code working for the 4-state example code, run the following code to make sure it works on the more complicated wifi codes.\n", "\n", "## A2" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Test your code here\n", "wifi_generators = [ [1,0,1,1,0,1,1], [1,1,1,1,0,0,1] ]\n", "a = encode( (1,0,1,0,1,0,1,0), generators=wifi_generators)\n", "b=[i for i in bsc(a,p=0.05)]\n", "c=viterbi(b, generators=wifi_generators)\n", "print a\n", "print b\n", "print c" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see how these two codes compare.\n", "We are going to plot the bit error rate = $\\frac{\\textrm{Number of incorrectly decoded bits}}{\\textrm{Total number of bits}}$ for some different channel parameters.\n", "\n", "## Q3\n", "For $0.01\\le p \\le 0.1$ on the x-axis, plot the bit error rate on a log scale on the y-axis. Run 10 trials for 512-bit long inputs at each channel parameter. Plot Both the WiFi and example codes.\n", "\n", "## A3" ] }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bit error rate is a good metric for evaluating how well a code performs in noise.\n", "In addition to BER, the other two main features used to evaluate decoders for error correction are throughput and energy efficieny.\n", "The previous section probably took a long time to run, so our throughput is probably pretty low.\n", "Let's measure throughput more accurately in the next section.\n", "\n", "## Q4\n", "Use the following code block to measure the throughput of your Viterbi decoder.\n", "\n", "## A4" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import timeit\n", "\n", "n_trials = 10\n", "received = []\n", "for i in range(n_trials):\n", " bits_in=np.random.randint(0,1, 512)\n", " received.append(bsc(encode(bits_in, generators=wifi_generators), p=0.05))\n", "\n", "start_time = timeit.default_timer()\n", "for i in range(n_trials):\n", " decoded = viterbi(received[i], generators=wifi_generators)\n", "\n", "elapsed = timeit.default_timer() - start_time\n", "\n", "print str((n_trials * 512) /float(elapsed)) + \" bits per second\"" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Q5\n", "Approximate the number of arithmetic operations needed to decode one bit using the algorithm above.\n", "If you want to watch a youtube video at 10Mbps, we many operations per second does your processor need to do to keep up?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A5 Your Answer Here\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The answers to Q4 and Q5 suggest our python implementation is very inefficient (unless your implementation is *way* better than the solutions).\n", "Still, the answer to Q5 is a lot of operations per second for a low power wifi chip to run on a serial processor.\n", "Fortunately, the computations for each state can be performed in parallel, so specialized hardware can decode with very high throughput without needing multi-gigahertz clocks.\n", "This parallelism, in addition to the simplicity of the arithmetic operations (no floating-point needed), makes convolutional codes and Viterbi decoders very hardware friendly.\n", "\n", "## Q6 \n", "Look at [this decoder](http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=535288&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel3%2F3909%2F11339%2F00535288.pdf%3Farnumber%3D535288) designed at Berkeley in the mid-90s.\n", "Figure 7 shows decode rate and power.\n", "Use the values from figure 7 to find the chip's energy per bit.\n", "Look up the typical power for the processor you have been using to write this lab, and use your answer from Q4 to find Energy / bit = Power / Throughput.\n", "Compare the throughput and energy per bit for the chip from the 90s vs. your computer.\n", "Which is more efficient?\n", "Recall that your computer has an advantage of almost two decades of Moore's law making everything faster and more efficient." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A6" ] }, { "cell_type": "code", "collapsed": false, "input": [ "#thanks http://stackoverflow.com/questions/10237926/convert-string-to-list-of-bits-and-viceversa\n", "def tobits(s):\n", " result = []\n", " for c in s:\n", " bits = bin(ord(c))[2:]\n", " bits = '00000000'[len(bits):] + bits\n", " result.extend([int(b) for b in bits])\n", " return result\n", "\n", "def frombits(bits):\n", " chars = []\n", " for b in range(len(bits) / 8):\n", " byte = bits[b*8:(b+1)*8]\n", " chars.append(chr(int(''.join([str(bit) for bit in byte]), 2)))\n", " return ''.join(chars)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "code", "collapsed": false, "input": [ "fin = open('secret_bits.txt', 'r')\n", "secret_bits = [int(i) for i in fin.read()[1:-1].split(',')]\n", "fin.close()" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Q7\n", "We have included Alice's message for Bob that she encoded with the wifi convolutional codes.\n", "It went through a BSC(0.04) channel.\n", "Can you recover the message?\n", "\n", "## A7" ] }, { "cell_type": "code", "collapsed": false, "input": [ "print viterbi(secret_bits, generators=wifi_generators)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Example encoder and state transition diagram courtesy Bora Nikolic's Spr2013 EE290C Lectures." ] } ], "metadata": {} } ] }