ine@mit software and mathematics

8Oct/130

using python on the command line instead of bash

because the syntax for for loops in bash is silly and I can never remember it:

python -c "import os; [os.system('wget MY_URL' + str(i) + '.html') for i in range(10)]"

Filed under: Uncategorized No Comments
4Oct/130

Non-macports PyQt4 Install on OSX 10.8.5

just some quick notes

$ sudo port install py-pyqt4

isaac@Archimedes ~/D/P/g/g/qtgui (grcqt)» pyuic4-2.7 BlockLibrary.ui > ui_BlockLibrary.py
------------------------------------------------------------
isaac@Archimedes ~/D/P/g/g/qtgui (grcqt)» pyuic4-2.7 MainWindow.ui > ui_MainWindow.py

isaac@Archimedes ~/D/P/gnuradio (grcqt) [127]» bash 127
bash-3.2$ export PYTHONPATH=/Users/isaac/Documents/Programming/gnuradio

downloaded sip-4.15.2.tar.gz
extracted,
$python configure.py
$make
$sudo make install

then use pass the sip location

$ python configure-ng.py --sip /Users/isaac/Downloads/sip-4.15.2/sipgen/sip

but finally...this worked so those middle steps weren't necessary
$ sudo port select --set python python27

then $python
>>> import PyQt4

worked

Filed under: Uncategorized No Comments
7Jun/120

DisplayPort to HDMI adapter breaks wifi on Macbook Pro 2010

I was getting set up in a new location for work when I realized that my wifi had died. Curious, I ran "airport -I" (airport's not a built in, but I aliased it like so: /usr/sbin/airport -> /System/Library/PrivateFrameworks/Apple80211.framework/Versions/Current/Resources/airport) at the shell and observed that I saw a 10db signal strength drop when I plugged in my external monitor. Hmmm. At first I thought it was the placement of my HDMI cable, but further testing revealed that it was independent of the cable position.

Since I don't have direct HDMI output on my Mac, I suspected the non-Apple adapter. I was about to order a new adapter when I ran across this Apple support article: http://support.apple.com/kb/ht1365

> Certain external monitors and LCD displays: Certain displays may emit harmonic interference, especially in the 2.4GHz band between channels 11 and 14. This interference may be at its worst if you have a portable computer with the lid closed and an external monitor connected to it. Try changing your access point to use 5 Ghz or a lower 2.4 GHz channel.

I switched the router (2.4Ghz) to channel 1 from channel 6 and voila, the problem instantly resolved itself!

Filed under: Uncategorized No Comments
24Jun/111

The Rule of 9′s

An accounting professor I know shared an interesting heuristic with me today called "The Rule of 9's." The trick is that if you're adding up a ledger of numbers and the difference between the result and what you expected is a multiple of 9, it's highly likely that you've swapped the digits of two numbers (eg. written 382 as 328). So the claim was that any time you swapped the digits of a number, the difference between it and the original would be divisible by 9.

This sounded like a really interesting proof, and I guessed it was related to our base 10 numbering system. So, let x and y be the two digits which will be swapped, B be the base of the numbering system, n be the exponent of the base at x and n - d be the exponent of the base at y.

The difference between the number and its modified form will be the following:

xBn + yBn-d - (yBn + xBn-d)

Bn-d(Bd(x - y) + (y - x))

Bn-d((Bd) - 1)(x - y)

now the result is clearly divisible by Bd - 1. For our number system, B = 10 and so the result is 10d-1. So a transposition of 1 will be divisible by 10-1 = 9. Hence the rule of nines! A transposition of 2 will be divisible by 99, etc. And in general a transposition of d in base 10 is divisible by 10d-1.

Linearity also means that even if you have a lot of swapped digits, the final result will still be divisible by 9. Of course, there might be no digits swapped and the error difference is still divisible by 9, but it's less likely.

So I thought that was pretty cool, and a really nifty proof.

Filed under: Uncategorized 1 Comment
22May/110

Gaussian Elimination in Python

3x + 2y + z = 12
2x + y + 2z = 36
x + 2y + 4z = 4

Stuck trying to solve a bunch of simultaneous linear equations?

You want to use Gaussian elimination! It's generally easy to solve two or three simultaneous linear equations with a few variables, but as the number of variables grow it's nifty to have a computer solve the problem for you. Here's a cool javascript implementation which supports up to 5x5 that you can use to get an idea on how the process looks.

Here is a gaussian elimination implementation in Python, written by me from scatch for 6.01X (the advanced programming version of 6.01, MIT's intro to EECS course). I originally looked at the Wikipedia pseudocode and tried to essentially rewrite that in Python, but that was more trouble than it was worth so I just redid it from scratch. It's way simpler than a lot of the other python implementations out there (~170 lines or so). This one is roughly 15 logical lines - it's also available on Github.

def myGauss(m):
    #eliminate columns
    for col in range(len(m[0])):
        for row in range(col+1, len(m)):
            r = [(rowValue * (-(m[row][col] / m[col][col]))) for rowValue in m[col]]
            m[row] = [sum(pair) for pair in zip(m[row], r)]
    #now backsolve by substitution
    ans = []
    m.reverse() #makes it easier to backsolve
    for sol in range(len(m)):
            if sol == 0:
                ans.append(m[sol][-1] / m[sol][-2])
            else:
                inner = 0
                #substitute in all known coefficients
                for x in range(sol):
                    inner += (ans[x]*m[sol][-2-x])
                #the equation is now reduced to ax + b = c form
                #solve with (c - b) / a
                ans.append((m[sol][-1]-inner)/m[sol][-sol-2])
    ans.reverse()
    return ans

tests:

print myGauss([[S('x'),2.0,6.0],
               [2.0,6.0,0]])

print myGauss([[S('M') * S('x'),S('b'),S('y')],
               [2.0,6.0,0]])

print myGauss([[-3.0,2.0,-6.0,6.0],
               [5.0,7.0,-5.0,6.0],
               [1.0,4.0,-2.0,8.0]])

print str(myGauss([[2.0,4.0,6.0,8.0,10.0,0.0],
               [1.0,3.0,5.0,8.0,3.0,-1.0],
               [3.0,8.0,9.0,20.0,3.0,5.0],
               [4.0,8.0,9.0,-2.0,3.0,8.0],
               [5.0,-3.0,3.0,-2.0,1.0,0]])) == '[1.8835063437139565, 1.7012687427912341, -1.4160899653979238, -0.050749711649365627, -0.16695501730103807]'

print 'example from the wikipedia'
print myGauss([[2.0,1.0,-1.0,8.0],
               [-3.0,-1.0,2.0,-11.0],
               [-2.0,1.0,2.0,-3.0]])
print myGauss([[1.0,4.0,-2.0,8.0],
               [5.0,7.0,-5.0,6.0],
               [-3.0,2.0,-6.0,6.0]])
15Jan/111

Downloading the xCode and iOS SDK on a slow internet connection

At home, our internet connection tops out around 60KB/sec - which is really hard to readjust to after experiencing the 20+MB/sec awesomeness which the MIT networks deliver. So when I wanted to download the latest iOS SDK, a 3.5Gb file, things weren't as easy as they seemed.

First I tried letting our iMac download the file overnight. It failed at around 1.5Gb. The next night it failed around 2.2Gb. Also, asking Safari or Chrome to restart the download would restart the download from the beginning, clearly not desirable failure. Then I looked into using a download manager (like DownThemAll) for Firefox to run the download (supports chunking the file and multithreading the download) but I got 403 Forbidden errors because Apple runs the download over HTTP and requires cookies. Grrr. I would have switched to a torrent, but our ISP here blocks torrent ports.

Then, inspired by this StackOverflow question, I remembered I had my XVM. I turned it on,  exported my cookies from Firefox , and ran:

wget --cookies=on --load-cookies=cookies.txt --keep-session-cookies --save-cookies=cookies.txt https://developer.apple.com/devcenter/download.action?path=/ios/ios_sdk_4.2__final/xcode_3.2.5_and_ios_sdk_4.2_final.dmg

wget was kind enough to follow the redirect and finish the download in a cool 3 minutes.

...
Moved Temporarily Location: http://adcdownload.apple.com/ios/ios_sdk_4.2__final/xcode_3.2.5_and_ios_sdk_4.2_final.dmg [following] --13:28:40--  http://adcdownload.apple.com/ios/ios_sdk_4.2__final/xcode_3.2.5_and_ios_sdk_4.2_final.dmg            => `download.action?path=%2Fios%2Fios_sdk_4.2__final%2Fxcode_3.2.5_and_ios_sdk_4.2_final.dmg' Resolving adcdownload.apple.com... xx.xx.xx.xx, xx.xx.xx.xx Connecting to adcdownload.apple.com|xx.xx.xx.xx|:80... connected. HTTP request sent, awaiting response... 200 OK Length: 3,782,241,266 (3.5G) [application/octet-stream]  69% [=======================>           ] 2,629,919,501   18.27M/s    ETA 00:56

Then, after installing lighttpd on my server, I was downloading in five segments at a blazing 30Kb/s. Pausing and resuming the download even worked!

Edit: When I md5'd the downloaded file (a day later!) the checksum didn't match the server checksum. So I ran the unix split utility and divided the .dmg into 500MB chunks - incredibly, these chunks also were failing checksum. I ran split again, dividing into 100MB chunks. The md5s started matching, everything downloaded...I checked all the individual md5s, ran cat to stitch the files back together, checksummed the final .dmg...and it was finally there. That night I uploaded the update to my iPhone app to Apple. Yay!

Filed under: Uncategorized 1 Comment
13Nov/101

Deriving the DT Fourier Transform

In 18.03, we learned that any function can be written as a sum of sines and cosines of different frequencies.

where

This is the definition of a continuous time fourier series. The interesting thing is that there is another definition that can be reached for discrete time, and that Euler's formula e = cos θi sin θ can be used to make the math simpler. Using Euler's formula will also result in the possibility of having complex Fourier coefficients (the a's and b's in the formula). So (using Wikipedia's image):

gives the Fourier coefficients as T increases. In discrete time, we write it like this:

Where omega sub k is 2πk/N, and x[n] is the original input. So these expressions are expressing the same thing. This is how the DTFS (discrete time fourier transform) derives from the Fourier series. Read Wikipedia if you want a fuller explanation; I've glossed over some details on the restrictions on the functions and such.

Plotting X[k] gives the spectrum - a frequency sweep that shows how much of each frequency is present in any input function/signal. The original signal itself can also be written in terms of Fourier coefficients:

Nice, huh? Basically this is just the DT equivalent, saying that we can write an input signal as a weighted sum of exponentials, just as in CT we can write any input function as a sum of weighted sines and cosines (Euler's formula provides the relationship between sin/cos and e, of course). So, given this information, let's look at how to plot the spectrum for any input signal using Python (this is from my 6.02 lab 6.1):

1 # Return two numpy arrays, one containing frequencies, one containing
2 # magnitudes of frequency responses.
3 def freq_res_usr(usr, num_freqs):
4     freqs, mags = [], []
5     #we choose arbitrary frequencies and calulate the magnitude of the resp
6     for f in range(num_freqs):
7         freq = 2.0*math.pi * (float(f)/float(num_freqs)) - math.pi
8         sum = complex(0, 0)
9         #for this freq, what is the magnitude of the usr?
10         for m in range(len(usr)):
11            sum += usr[m] * (math.e**(-complex(0, 1)*freq*m))
12        mags.append(abs(sum))
13        freqs.append(freq)
14    return (freqs, mags)

In line 7, we choose what frequency we are going to calculate (omega sub k). In lines 10-11, for all of the items in the input signal, we sum the individual item multiplied by e^(-i * freqency * index). Really simple actually, but a very powerful result. I'll go over why this actually useful in the next post.

Filed under: Uncategorized 1 Comment
7Nov/100

Deconvolving Convolution

An attempt to explain convolution in a straightforward way. This is something we've been studying in 6.02, Digital Network Communications, and I'm still working on understanding it all myself.

Successful deconvolution of an input waveform over a noise-free channel for 6.02 Lab 2

Convolution itself is pretty straightforward. You take a discrete input signal X, which you are about to pass over a channel with unit sample response H (symbolically, Y = H * X.) The unit response is the way the system responds when you input a steady stream of ones. A unit sample response of [0, 1] will delay by one. A unit sample response of [0, 0.5, 1] does this:

$ numpy.convolve([0,1,0,1,0,1], [0,0.5,1])
array([ 0. ,  0. ,  0.5,  1. ,  0.5,  1. ,  0.5,  1. ])

Here's the key to understanding this: imagine 0, 0.5, 1 as a kind of filter or comb that "picks out" values from the input. First a 0 comes in from the input - the 0 gets matched to the 0, and the output is 0. Then a 1 comes in after the 0, the 0 moves on to 0.5. The output is still zero because 1*0 + 0.5*0 = 0. Then the original zero moves over to the 1, the 1 moves over to the 0.5, and another 0 matches up with the first zero from the 0, 0.5, 1 sequence. Now the output is 0.5 because 0*0 + 0.5*1 + 0*1 = 0.5.

USR 0, 0.5, 1
input at*                             ouput at *
========*======================================*=====
Step 1: 0  *0 + nothing * 0.5 + nothing *  1 = 0
Step 2  1  *0 + 0*0.5 + nothing * 1          = 0
Step 3: 0  *0 + 1*0.5 + 0*1                  = 0.5
Step 4: 1  *0 + 0*0.5 + 1*1                  = 1
Step 5: 0  *0 + 1*0.5 + 0*1                  = 0.5
Step 6: 1  *0 + 0*0.5 + 1*1                  = 1
...

If you read the columns, you can see the input coming in and the output streaming out. The main thing to realize is that each signal, each 1 in the input, is vanishing after its unit sample response is complete. If we bunch those signals close together, we can get some higher results for a bit:

$ numpy.convolve([0,1,1,1,1,0], [0,0.5,1])
array([ 0. ,  0. ,  0.5,  1.5,  1.5,  1.5,  1. ,  0. ])

The 0.5 part of the unit sample response is smearing into the other bits, causing peaks when the values are 1+0.5.

So, how does the unit step response relate to the unit sample response? The primary way is that we use the unit sample response to get the unit step response. If we send the unit step response over a channel and then a version of the unit step response delayed by one time-step, we can find the unit sample response by examining the difference between the two. In other words, the unit sample response H is related to the unit step response M by the equation h[n] = m[n] - m[n-1]. So H is the discrete derivative of M, and M is the discrete integral of H. So m[n] = h[0] + h[1] + ... + h[n].

How does this all fit together? Well, if we know the unit step response of a system it turns out we can do marvelous things. We can predict the exact output (in an ideal, noise-free environment) of the early example H = [0, 1], X=[0,1,1] for example. Let's do this manually. The convolution formula is y[n] = summation from 0 to n of (h[i])(x[n-i]).

y[0] = x[0]h[0] = 0, because h[0] is 0

y[1] = x[0]h[1] + x[1]h[0]
y[1] = 0*1 + 1*0 = 0

y[2] = x[0]h[2] + x[1]h[1] + x[0]h[0]
y[2] = 0*undef + 1*1 + 1*0 = 1

Output so far is [0, 0, 1] - it's delayed by one, just as we expected! Basically, the h of n terms "cycle" through our system, snatching the xs at the appropriate delay and scaling. Quite convenient. Notice that we also made the reasonable assumption that H was zero when undefined/out of range.

Somewhat confusingly, convolution is symmetric. So Y = H * X = X * H, and the summation from 0 to n can be of (h[i])(x[n-i]) or (h[n-i])(x[i]). I recall that the same property holds through for the continuous convolution we did in 18.03, in which ease of integration was often a major motivation to try the symmetric form of the convolution.

Deconvolution
A little clever math goes a long way here. So if

y[n] = h[0]x[n] + h[1]x[n-1]+... + y[m]x[n-m]

Then:

x[n] = (1/h[0])(y[n] - h[1]x[n-1] - h[2]x[n-2] - ... - h[m]x[n-m]

Now we have an recursive formula for X, given Y and H. So if we have an input signal Y and the unit sample response of the channel H, we can recover X, the original input, perfectly! Now you can see what's going on in the image at the start of this post. An input signal X is sent through the channel, which has some nasty oscillation going on before it stabilizes out. The exact properties of that oscillation, however, are captured in H, the unit sample response, which is used to recreate the original input signal perfectly (top and bottom graphs match). Anyways, that's where things are at with 6.02. Cool stuff.

Sidenote
In 6.042 today we proved the Euclidian GCD (greatest commond divisor) formula for two integers. Here's a while loop and a recursive version in Javascript.

function gcdr(a, b)
{
    if (a == 0) return b;
    return gcd(b % a, a);
}

function gcde(a, b)
{
    while (a != 0)
    {
        r = b % a;
        b = a;
        a = r;
    }
    return b;
}

x = gcde(105, 224); //7
y = gcde(1071, 462); //21
Filed under: Uncategorized No Comments