Prime Failure 1 Year in the Making

My expression is completely flat right now. I simply cannot believe I’m about to say what I’m preparing to say. I spent nearly a year cracking large prime numbers. In short, I took-on a project I called _The Flowering N’th Prime Project, where I used my SheevaPlug to generate a list of every [every millionth] prime number. The current “golden standard” is this page where one can look-up the N’th prime up to 1 trillion. My goal was to reach over 1 trillion, which I did just this morning! I was planning on being the only source on the web to allow lookups of prime numbers greater than 1 trillion.

However, when I went to look at the logs, I realized that the software had a small, fatal bug in it. Apparently every time the program restarted (which happened a few times over the months), although it resumed at its most recent prime number, it erased the previous entries. As a result, I have no logs below N=95 billion. In other words, although I reached my target this morning, it’s completely irrelevant since I don’t have all the previous data to prove it. I’m completely beside myself, and have no idea what I’m going to do. I can start from the beginning again, but that would take another YEAR. [sigh]

So here’s the screw-up. Apparently I coded everything correctly on paper, but due to my lack of experience I overlooked the potential for multiple appends to occur simultaneously. I can only assume that’s what screwed it up, but I cannot be confident. Honestly, I still don’t know specifically what the problem is. All in all, it looks good to me. Here is the relevant Python code.

def add2log(c,v):
 f=open(logfile,'a')
 f.write("%d,%dn"%(c,v))
 f.close()

def resumeFromLog():
 f=open('log.txt')
 raw=f.readlines()[-1]
 f.close()
 return eval("["+raw+"]")

For what it’s worth, this is what remains of the log file:

953238,28546251136703
953239,28546282140203
953240,28546313129849
...
1000772,30020181524029
1000773,30020212566353
1000774,30020243594723

Converting Numbers to Morse Code with GCC

One of my microcontroller projects requires me to measure values and transmit then in Morse code. There may be code out there to do this already, but I couldn’t find it. I’m sure there are more elegant and efficient ways to handle the conversion, but this works for me. Hopefully someone will find it useful!

#include <stdio.h>

//Morse code numbers from 0 to 9
char *array[10] = {"-----", ".----", "..---", "...--", "....-",
                   ".....", "-....", "--...", "---..", "----."};

void beep(char v)
{
    // beep (or print) Morse code as necessary
    printf("%s ", array[v]);
}

void send(int l)
{
    // convert a number into Morse code
    char d = 0;
    int t = 0;
    int val = 0;
    for (t = 100000; t > 0; t = t / 10)
    { //number of digits here
        if (l > t)
        {
            d = l / t;
            beep(d);
            l -= d * t;
        }
        else
        {
            beep(0);
        }
    }
    printf("n");
}

void main()
{
    // program starts here
    int l = 0b1111111111; //sample number (maximum 10-bit)
    printf("%d ", l);
    send(l);
    l = 0b11010001100101100011; //larger sample number
    printf("%d ", l);
    send(l);
}

vdFSK Modulation

My goal is to create a QRPP (extremely low power) transmitter and modulation method to send QRSS (extremely slow, frequency shifting data) efficiently, able to be decoded visually or with automated image analysis software. This evolving post will document the thought process and development behind AJ4VD's Frequency Shift Keying method, vdFSK.

Briefly, this is what my idea is. Rather than standard 2-frequencies (low for space, high for tone) QRSS3 (3 seconds per dot), I eliminate the need for pauses between dots by using 3 frequencies (low for a space between letters, medium for dot, high for dash). The following images compare my call sign (AJ4VD) being sent with the old method, and the vdFSK method.

Again, both of these images say the same thing: AJ4VD, .- .--- ....- ...- -.. However, note that the above image has greater than a 3 second dot, so it’s unfairly long if you look at the time scale. Until I get a more fairly representative image, just appreciate it graphically. It’s obviously faster to send 3 frequencies rather than two. In my case, it’s over 200% faster.

This is the code to generate audio files converting a string of text into vdFSK audio, saving the output as a WAV file. Spectrographs can be created from these WAV files.

generate_audio.py

# converts a string into vdFSK audio saved as a WAV file

import numpy
import wave
from morse import *


def makeTone(freq, duration=1, samplerate=5000, shape=True):
    signal = numpy.arange(duration*samplerate) / \
        float(samplerate)*float(freq)*3.14*2
    signal = numpy.sin(signal)*16384
    if shape == True:  # soften edges
        for i in range(100):
            signal[i] = signal[i]*(i/100.0)
            signal[-i] = signal[-i]*(i/100.0)
    ssignal = ''
    for i in range(len(signal)):  # make it binary
        ssignal += wave.struct.pack('h', signal[i])
    return ssignal


def text2tone(msg, base=800, sep=5):
    audio = ''
    mult = 3  # secs per beep
    msg = " "+msg+" "
    for char in msg.lower():
        morse = lookup[char]
        print char, morse
        audio += makeTone(base, mult)
        for step in lookup[char]:
            if step[0] == ".":
                audio += makeTone(base+sep, int(step[1])*mult)
            if step[0] == "-":
                audio += makeTone(base+sep*2, int(step[1])*mult)
            if step[0] == "|":
                audio += makeTone(base, 3*mult)
    return audio


msg = "aj4vd"
file = wave.open('test.wav', 'wb')
file.setparams((1, 2, 5000, 5000*4, 'NONE', 'noncompressed'))
file.writeframes(text2tone(msg))
file.close()

print 'file written'

morse.py

# library for converting between text and Morse code
raw_lookup="""
a.- b-... c-.-. d-.. e. f..-. g--. h.... i.. j.--- k-- l.-.. m--
n-. o--- p.--. q--.- r.-. s... t- u.- v...- w.-- x-..- y-.-- z--..
0----- 1.---- 2..--- 3...-- 4....- 5..... 6-.... 7--... 8---.. 9----.
..-.-.- =-...- :---... ,--..-- /-..-. --....-
""".replace("n","").split(" ")

lookup={}
lookup[" "]=["|1"]
for char in raw_lookup:
    """This is a silly way to do it, but it works."""
    char,code=char[0],char[1:]
    code=code.replace("-----","x15 ")
    code=code.replace("----","x14 ")
    code=code.replace("---","x13 ")
    code=code.replace("--","x12 ")
    code=code.replace("-","x11 ")
    code=code.replace(".....","x05 ")
    code=code.replace("....","x04 ")
    code=code.replace("...","x03 ")
    code=code.replace("..","x02 ")
    code=code.replace(".","x01 ")
    code=code.replace("x0",'.')
    code=code.replace("x1",'-')
    code=code.split(" ")[:-1]
    #print char,code
    lookup[char]=code

Automated decoding is trivial. The image above was analyzed, turned into the image below, and the string (AJ4VD) was extracted:

decode.py

# given an image, it finds peaks and pulls data out
from PIL import Image
from PIL import ImageDraw
import pylab
import numpy

pixelSeek = 10
pixelShift = 15


def findPeak(data):
    maxVal = 0
    maxX = 0
    for x in range(len(data)):
        if data[x] > maxVal:
            maxVal, maxX = data[x], x
    return maxX


def peaks2morse(peaks):
    baseFreq = peaks[0]
    lastSignal = peaks[0]
    lastChange = 0
    directions = []
    for i in range(len(peaks)):
        if abs(peaks[i]-baseFreq) < pixelSeek:
            baseFreq = peaks[i]
        if abs(peaks[i]-lastSignal) < pixelSeek and i < len(peaks)-1:
            lastChange += 1
        else:
            if abs(baseFreq-lastSignal) < pixelSeek:
                c = " "
            if abs(baseFreq-lastSignal) < pixelSeek:
                c = " "
            if abs(baseFreq-lastSignal) < pixelSeek:
                c = " "
            directions.append(
                [lastSignal, lastChange, baseFreq, baseFreq-lastSignal])
            lastChange = 0
        lastSignal = peaks[i]
    return directions


def morse2image(directions):
    im = Image.new("L", (300, 100), 0)
    draw = ImageDraw.Draw(im)
    lastx = 0
    for d in directions:
        print d
        draw.line((lastx, d[0], lastx+d[1], d[0]), width=5, fill=255)
        lastx = lastx+d[1]
    im.show()


im = Image.open('raw.png')
pix = im.load()
data = numpy.zeros(im.size)
for x in range(im.size[0]):
    for y in range(im.size[1]):
        data[x][y] = pix[x, y]

peaks = []
for i in range(im.size[0]):
    peaks.append(findPeak(data[i]))

morse = peaks2morse(peaks)
morse2image(morse)
print morse

High Altitude Balloon Transmitter

SUMMARY: A small group of high school students taking an AP class for college credit launched a high-altitude weather balloon with a small payload. In addition to a video transmitter and GPS transmitter, they decided to include a simple transmitter built from scratch. This is the story of the project, with emphasis on the simple transmitter's design, construction, implementation, and reception (which surprised me, being detected ~200 miles away and lasting the entire duration of the flight!) [sample.ogg]

6/16/2010 - TRACKING

__I’m impressed __ how well the transmitter/receiver worked! For only a few milliwatts, I was able to track that thing all the way from takeoff to landing in Gainesville, FL a few hundred miles away.

ANALYSIS: the text on the image describes most if it, but one of the most interesting features is the “multipathing” during the final moments of the descent, where the single carrier signal splits into two. I believe this is due to two Doppler shifts: (1) as the distance between the falling transmitter and the receiver is decreasing, producing a slight in increase in frequency, and (2) a signal reflected off of a layer of the atmosphere above the craft (the ionosphere?) before it gets to the receiver, the distance of which is increasing as the craft falls, producing a decrease in frequency. I’ll bet I can mathematically work backwards and determine how high the craft was, how fast it was falling, and/or how high the layer of the reflecting material is - but that’s more work than this dental student is prepared to do before his morning coffee!

HERE IS SOME AUDIO of some of the strongest signals I received. Pretty good for a few milliwatts a hundred miles away! beeps.ogg

6/16/2010 - THE FLIGHT

The design team:

Walking the balloon to its launch destination at NASA with an awesome rocket (Saturn 1B - identified by Lee, KU4OS) in the background.

The team again, getting ready for launch. I’ve been informed that the reason their hands are up is to prevent the balloon from tilting over too much. I’d imagine that a brush with a grass blade could be bad news for the project!

Last minute checks - you can see the transmitter and battery holders for it taped to the Styrofoam.

The transmitter in its final position:

Note the coil of yellow wire. That serves as a rudimentary “ground” for the antenna’s signal to push off of. I wasn’t very clear on my instructions on how to make it. I meant that it should be a huge coil wrapped around the entire payload (as large as it can be), which would have probably produced a better signal, but since I was able to capture the signal during the whole flight it turned out to be a non-issue.

The antenna can be seen dropping down as a yellow wire beneath the payload. (arrow)

Launch! Look how fast that balloon is rising!

It’s out of our hands now. When I got the text message that it launched, I held my breath. I was skeptical that the transmitter would even work!

One of the students listening to my transmitter with QRSS VD software (score!)

Video capture from an on-board camera was also attempted (900MHz), but from what I hear it didn’t function well for very long.

6/15/2010 - IMPROVED BUILD

Here you can see me (center arrow) showing the students how to receive the Morse code signal sent from the small transmitter (left arrow) using a laptop running QRSS VD analyzing audio from and an Icom706 mkII radio receiver attached to a dipole (right arrow).

I amped-up the output of the oscillator using an octal buffer chip (74HC240) with some decent results. I’m pleased! It’s not perfect (it’s noisy as heck) but it should be functional for a 2 hour flight.

Closeup of the transmitter showing the oscillator at 29.4912 MHz, the Atmel ATTiny44a AVR microcontroller (left chip), octal buffer 74HC240 (right chip), and some status lights which blink as the code is executed.

This is my desk where I work from home. Note the styrofoam box in the background - that’s where my low-power transmitter lives (the one that’s spotted around the world). All I needed to build this device was a soldering iron.

Although I had a radio, it is not capable of receiving 29MHz so I was unable to test the transmitter from home. I had to take it to the university to assess its transmitting capabilities.

I connected the leads to the output of the transmitter, shorted by a 39ohm resistor. By measuring the peak-to-peak voltage of the signal going into a resistor, we can measure its power.

Here’s the test setup. The transmitter is on the blue pad on the right, and the waveform can be seen on the oscilloscope on the upper left.

With the amplifier off, the output power is just that of the oscillator. Although the wave should look like a sine wave, it’s noisy, and simply does not. While this is unacceptable if our goal is a clean radio signal with maximum efficiency, this is good enough to be heard at our target frequency. The PPV (peak-to-peak voltage) as seen on the screen is about 100mV. Since I’m using a x10 probe, this value should be multiplied by 10 = 1V. 1V PPV into 39 ohms is about 3 milliwatts! ((1/(2*2^.5))^2/39*1000=3.2). For the math, see this post

With the amplifier, the output is much more powerful. At 600mV peak-to-peak with a 10x probe (actually 6V peak-to-peak, expected because that’s the voltage of the 4xAAA battery supply we’re using) into 39 ohms we get 115 millivolts! (6/(2*2^.5))^2/39*1000=115.38.

Notes about power: First of all, the actual power output isn’t 115mW. The reason is that the math equations I used work only for pure sine waves. Since our transmitter has multiple waves in it, less than that power is going to produce our primary signal. It’s possible that only 50mW are going to our 29MHz signal, so the power output assessment is somewhat qualitative. Something significant however is the difference between the measured power with and without the amplifier. The 6x increase in peak-to-peak voltage results in a 36x (6^2) increase in power, which is very beneficial. I’m glad I added this amplifier! A 36 times increase in power will certainly help.

6/14/2010 - THE BUILD

Last week I spoke with a student in the UF aerospace engineering department who told me he was working with a group of high school students to add a payload to a high-altitude balloon being launched at (and tracked by) NASA. We tossed around a few ideas about what to put on it, and we decided it was worth a try to add a transmitter. I’ll slowly add to this post as the project unfolds, but with only 2 days to prepare (wow!) I picked a simplistic design which should be extremely easy to understand by everyone. Here’s the schematic:

The code is as simple as it gets. It sends some Morse code (“go gators”), then a long tone (about 15 seconds) which I hope can be measured QRSS style. I commented virtually every line so it should be easy to understand how the program works.

#include <avr/io.h>
#include <util/delay.h>

char call[] = {2, 2, 1, 0, 2, 2, 2, 0, 0, 2, 2, 1, 0, 1, 2, 0, 2, 0, 2, 2, 2, 0, 1, 2, 1, 0, 1, 1, 1, 0, 0};
// 0 for space, 1 for dit, 2 for dah

void sleep()
{
    _delay_ms(100);      // sleep for a while
    PORTA ^= (1 << PA1); // "flip" the state of the TICK light
}

void ON()
{
    PORTB = 255;          // turn on transmitter
    PORTA |= (1 << PA3);  // turn on the ON light
    PORTA &= ~(1 << PA2); // turn off the ON light
}

void OFF()
{
    PORTB = 0;            // turn off transmitter
    PORTA |= (1 << PA2);  // turn on the OFF light
    PORTA &= ~(1 << PA3); // turn off the OFF light
}

void ID()
{
    for (char i = 0; i < sizeof(call); i++)
    {
        if (call[i] == 0)
        {
            OFF();
        } // space
        if (call[i] == 1)
        {
            ON();
        } // dot
        if (call[i] == 2)
        {
            ON();
            sleep();
            sleep();
        } // dash
        sleep();
        OFF();
        sleep();
        sleep(); // between letters
    }
}

void tone()
{
    ON(); // turn on the transmitter
    for (char i = 0; i < 200; i++)
    { // do this a lot of times
        sleep();
    }
    OFF();
    sleep();
    sleep();
    sleep(); // a little pause
}

int main(void) // PROGRAM STARTS HERE
{
    DDRB = 255; // set all of port B to output
    DDRA = 255; // set all of port A to output
    PORTA = 1;  // turn on POWER light

    while (1)
    {           // loop forever
        ID();   // send morse code ID
        tone(); // send a long beep
    }
}

I’m now wondering if I should further amplify this signal’s output power. Perhaps a 74HC240 can handle 9V? … or maybe it would be better to use 4 AAA batteries in series to give me about 6V. [ponders] this is the schematic I’m thinking of building.

UPDATE: This story was featured on Hack-A-Day! Way to go everyone!

Coder's Block

I like the idea of writing a set of tools for scientific frequency analysis (more than just turning audio into images), and I keep starting over re-coding things from scratch. I develop too much, too quickly, and half way in I get overwhelmed and mentally blocked. I do it to myself. I’ve taken about a week off and will continue to take a few more days off to reset my mind. I’m trying to improve my coding by reading books (e-books) about advanced Python programming. Perhaps when it’s time to return, I’ll write gorgeous and functional code. I always seem to have one or the other, but never both [sigh]

The photo above is the signal of my (AJ4VD) little homemade transmitter in Gainesville, Florida, USA (using a 20-ft piece of wire inside my apartment as an antenna) detected by ON5EX in Belgium. It makes me happy. It reminds me that some of the projects I work on succeed, which gives me motivation to continue pursuing the ones which currently challenge me.