Toby Smith

Posts for the ‘Technology’ Category

Goertzel Algorithm

9th September 2013

I’ve always wondered how complicated it would be to write the code that listens to the numbers you dial on your phone, and works out what numbers you pressed.
I often enter my credit card details over the phone, and think: “If someone had a good enough microphone to record the sounds, they could probably get my information!”

The fancy name for this is: Dual-tone multi-frequency signalling. When you press the buttons, two sine waves are generated with different frequencies. The receiver then has to measure these two frequencies and can work out what number you’ve pressed. I do love the similarity of this with formants (the way we create the different vowels sounds).

Whilst an FFT would easily do the trick, after a bit of research, it’s obvious that the most common algorithm to use is the Goertzel algorithm.
My time pocket principals say I should have just done an FFT and been done with it. The point here wasn’t to get a working decoder, but to understand how it is done, and to actually write some code that I can have.

I decided to work in scilab. I was tempted by C/C++, but I fancied learning a bit more about scilab (and not fiddling with audio libraries).

I created a couple of simple functions to generate some pure “tones” to test the algorithm, as well as adding noise, and gaps.

There’s plenty of examples of the Goertzel code out there. I started off doing different overlapping partitions to sample the audio, but in the end took a far simpler approach.
I’m not exactly satisfied with the speed, or with the way I’ve implemented the divisions. Ironically the first time I wrote it was probably a better method, but the second is definitely faster. So I certainly made some mistakes. Creating a matrix for all the frequencies at all the sample points probably was a bit silly… but I ran out of time.

In addition to the Goertzel I looked at dealing with noise, silence and series of numbers. The algorithm will sample the frequencies (by default) every 0.05 seconds, and will adjust to the sample rate of the audio data. If there isn’t a strong signal, then it will assume there’s no number being pressed. If the value is the same as the previous check, no new number is written out.

I tested it by recording my pressing buttons on a phone, and it actually worked out great! I was quite surprised.
All in all a good way to spend a few hours!

SciLab code here:
(I would imagine it would be fairly easy to port to Matlab).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// This creates an array of the goertzel's response.
// Use: data x, at frequency f, sampled at points defined by at.
function [res] = goertzelArr(x, f, sampleRate, at)
    a=0;
    b=0;
    c=0;
 
    val = 2 * cos(2 * %pi * f / sampleRate);
    res = zeros(1,length(at));
 
    nextAt = 1;
    nextTrig = at(1);
 
    for i = 1:length(x),
        a = val * b - c + x(i);
        c = b;
        b = a;
 
        if i == nextTrig then
            res(nextAt) = (b*b + c*c - b*c*val);            
            nextAt = nextAt + 1;
            b = 0;
            c = 0;
            if (nextAt > length(at) ) then
                return;
            end
            nextTrig = at(nextAt);
        end
    end
endfunction
 
// Main decoding function. 
// Call with: evalTone(AUDIO_VECTOR, SAMPLE_RATE_OF_AUDIO [, time between samples])
function [t] = evalToneAt(x,sampleRate,timebetween)
    // Default time between checks is 0.05
    [out, inp] = argn(0);
    if inp < 3 then, timebetween = 0.05, end
 
    // Work out how many samples per check, and build array    
    spaceSamples = timebetween * sampleRate;
    at = [spaceSamples:spaceSamples:length(x)];    
 
    // Relevant frequencies for number
    checkComb = [1209, 1336, 1477, 1633,697, 770, 852, 941];
    chars = ['1','2','3','A','4','5','6','B','7','8','9','C','*','0','#','D']; 
 
    // Create results array
    r = zeros(8,length(at));
 
    // Get results from goertzels
    for i=1:8
        r(i,:) = goertzelArr(x,checkComb(i),sampleRate,at);
    end
 
    lastVal = 0;
    t = '';
    // Loop through measurements
    for i=1:length(at)
        // Find best tone pair
        col = 1;
        row = 1;
        colval = r(1,i);
        rowval = r(5,i);
        for j=2:4
            if (r(j,i) > colval) then
                colval = r(j,i);
                col = j;
            end
            if (r(j+4,i) > rowval) then
                rowval = r(j+4,i);
                row = j;
            end
        end
        // This is the best candidate tone pair
        v = col + (row - 1) * 4;
 
        // If the magnitude doesn't satisfy contraints ignore.
        if (colval < spaceSamples | rowval < spaceSamples) then
            lastVal = 0;
            continue;
        end
 
        // If this is same tone as before. Ignore
        if (v ~= lastVal) then
            t = strcat([t,chars(v)]);
            lastVal = v;
        end
    end
endfunction

These functions create the sample tones:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Assistant function to create the tones
function [x] = soundChar(c, len, sampleRate)
 
    [out, inp] = argn(0);
    if inp < 3 then, sampleRate = 22050, end
    if inp < 2 then, len = 0.5, end    
 
    checkCol = [1209, 1336, 1477, 1633];
    checkRow = [697, 770, 852, 941];
 
    chars = ['1','2','3','A';'4','5','6','B';'7','8','9','C';'*','0','#','D'];
 
    sig1 = 0;
    sig2 = 0;
 
    for i = 1:size(chars,1)
        for j = 1:size(chars,2)
            if (chars(i,j) == c) then
                sig2 = checkRow(i);
                sig1 = checkCol(j);
            end
        end
    end
 
    v1 = len * 2 * %pi;
    v2 = len * sampleRate;
 
    s1 = sin(linspace(0, v1*sig1, v2));
    s2 = sin(linspace(0, v1*sig2, v2));
 
    x = s1 + s2;
 
endfunction
 
// Create a tone sequence eg: genTone('0123456789#*ABCD',0.2,44100,0.05);
// Will return an audio vector with each tone playing for 0.2 seconds, 
// with gaps in between of 0.05 seconds at a sample rate of 44100
function [x] = genTone(s, len, sampleRate, gap) 
    [out, inp] = argn(0);
    if inp < 4 then, gap = 0.2, end
    if inp < 3 then, sampleRate = 22050, end
    if inp < 2 then, len = 0.5, end   
 
    x = [];
    for i = 1:length(s)
        x = [x,soundChar(part(s,i), len, sampleRate),zeros(1,round(gap*sampleRate))];
    end
 
endfunction

New Design

7th September 2013

Welcome to the new and improved THJSmith.com!

This has been something I’ve been wanting to do for a long time, but I finally decided to put a few days aside and do a custom design for this site.
Funnily enough the initial “design point” ended up getting scrapped, and I would like to find a better way to utilise the colour series throughout the body.

I enjoyed getting to to flex my design, CSS and javascript muscles on a smaller project.

Anyway, I hope you find it suitably unsettling?
Whatchu think?

How to bodge an autocue

4th August 2013

Autocues are really quite simple things; consisting of a camera, a screen, and a piece of glass. They allow you to read off your words, whilst looking straight at the camera.

Adhoc Autocue

I cobbled mine together from a PS:Eye, piece of glass from a photo-frame, and an iPad.
The most irritating thing was getting the text to display. I didn’t check for an app that would scroll the text. In the end I just had a static image (just rememeber to flip it about the y-axis).

The construction was just from junk I had on my desk. Sometimes a little mess can be helpful (that’s my excuse).

It worked, but wasn’t great. The text I was reading was very small (no scrolling), so you can see my eyes scanning across. Having bigger, scrolling text would have been a bonus. Being further from the set up with the camera zoomed in more would probably mitigate the “scanning eyes” too.

All in all it was a lot of fun to build but it’s probably easier to just learn your lines!

Javascript Arguments

25th June 2013

It’s always tempting to optimise code before you need to. With Javascript I think it’s basically worth following some best practises as you go along, and then doing the “proper” thing of working out where the big holes are.
The issue I have with NOT considering speed as you go through, is you end up with death by a thousand cuts. Internet users (Netizens?) are incredible fickle about speed.

So I’ve been taking reasonable efforts to make the code work fast. I recently stumbled across an article mentioning that using “arguments” was bad.
Specifically that:

function (a) {
return a;
}

is considerably better than:

function () {
return arguments[0];
}

Now, I only use the arguments variable if I want to work with a variable (and potentially large) number of arguments. Utility functions and what have you. The alternative to the above would be to assume one parameter that was a list. Like so:

function (args) {
return args[0];
}

The cost here is building a list each time you call the function. I wanted to see what’s actually faster here and so I extended a JSPerf to examine:
http://jsperf.com/named-arguments-vs-arguments-array/2

Moral of the story: if you want to use variable number of arguments in utility functions the use of the arguments variable is better than building a list.

The best comment syntax

24th April 2013

I’m not going to talk about heirarchical comments here. I just wanted to write about a little nugget that I’ve found very useful, so that you can use it too!

//*///

This is valid in javascript, and I’m sure you could something similar in C and C++ too.

Why is this cool?

function GetSomeValue() {
//*///
var a = CHUNK OF CALCULATION
return a;
//*///
var b = CHUNK OF CALCULATION
return b;
}

With the deletion of the first character of the first “//*///” you can comment out the first return. (Imagine this was a substantial chunk of early outs).
The second instance will act as the closing comment for it, without having to add one. It’s useful if you know you’re going to be flicking bits of code on/off for a brief while.

This comment syntax also allows you to add inline comments afterwards:

function GetSomeValue() {
/*/// Inline comments are valid here!
var a = CHUNK OF CALCULATION
return a;
//*/// Also valid here!
var b = CHUNK OF CALCULATION
return b;
}

All in all they’re pretty nifty.
Personally I think I’d go for something like:
#{
#}

#{ being equivalent to /*///.
and
#} being equivalent to //*///

You could even extend this so that:
#{{
#}}
Would also be valid comments. And wouldn’t be closed by #}
This would mean that you could plop multi-line comments in various places, and not have to remove them later if you want to comment out chunks of code later!

function GetSomeValue() {
return 4;
#{{ TESTING ASSUMPTION
#{ This code does some calculation
about various things!
#}
var a = CHUNK OF CALCULATION
return a;
#} Might want to block off this code later
var b = CHUNK OF CALCULATION
return b;
#}}
}

I know it’s not the cleverest chunk of code in the world. Or actually does anything…or is really “code”. But, it might save you some time!

Argument against The Singularity

18th April 2013

I know there are a lot of people excited for the singularity. I would be too, if I thought it to be plausible. By all means prove me wrong and achieve it. I’d love to be wrong on this one.

For those that don’t know: The singularity is the point at which we can create AI that is smarter than us, to the extent that it can significantly improve itself faster than we can.
I highly recommend you go read about it. As that paltry explanation doesn’t really do the subject justice.

This is why I think it’s not going to happen:

  1. Humans create an AI
  2. That AI must be able to improve itself somehow
  3. Whilst increased speed is initially sufficient. Ultimately, the AI will need to improve it’s intelligence and thus: improve the amount it can improve itself
  4. All improvements are sufficient to overcome any, and all physical and or technical limitations
  5. This process can continue for sufficient iterations, in a reasonable time frame, for a seemingly infinite technical advance (as t -> infinity)

Let me break this down:

Humans create an AI

Sure. There are no definitions here. There are no problems here.

That AI must be able to improve itself somehow

We do have evolving algorithms and learning algorithms that get better at their jobs. So, again, technically there are no problems here.

Whilst increased speed is initially sufficient. Ultimately, the AI will need to improve it’s intelligence and thus: improve the amount it can improve itself

I think it’s quite conceivable that an algorithm will be able to make itself “faster”. Self optimisations, even designing custom faster hardware are reasonable plausible. However the AI will have to be able to “improve” itself beyond our initial tinkering. Otherwise it will forever be limited to the level of the human designers.
We do not have any significant AI that can spew out another AI (of greater intelligence). The issue here is that it has taken us so many hundreds of years, and we’re not even at the point when we can design something EQUAL to our brains. You’re assuming that the best thing that we can conceive of, could do better than us. And assuming that for (ostensibly) infinity iterations. Which seems unlikely. Even if you assume that the iterations will end at some point. All the steps before are not trivial.

All improvements are sufficient to overcome any, and all physical and or technical limitations

Each necessary improvement may require a tech shift. Like floppy disks to CDs to DVDs. Perhaps the AI needs new hardware and new tech. It needs to have that available, or be able to produce, design and build. There would have to be NO limitations in what it could feasibly DO. Which is not exactly a simple proposition. How can we provide the AI something we know nothing about. It doesn’t seem very “singularity”-y if we have to get involved every now and then. Life has a way of throwing curve balls at us. I see no reason why that shouldn’t happen to an AI too. The unknown here, is an unwieldy beast.

This process can continue for sufficient iterations, in a reasonable time frame, for a seemingly infinite technical advance (as t -> infinity)

Deep thought took 7 and a half million years to deduce the answer for “Life, the Universe and Everything”.
Even if we assume all the above is “possible”. The time it could take for all of this to happen is an unquantifiable value. We have no real reliable way of knowing how long these stages might take. By definition we can’t really predict what’s going to happen, so surely any time estimates are off. It seems more likely to me, that improvement will be slow. It’s taken us hundreds of years to get to where we are now, and we haven’t even got to the first round of automated improvements yet.

None of these are concrete proofs against the occurrence of the singularity (if such thing could exist). But given that most of the real requirements are ridiculously far off, I don’t think we really need to talk about this for another 100 years really. I think technologists are just being hopeful and optimistic that some ultimate AI will come and do all their work for them. It’s not an unattractive proposition. But the inherent belief and circular arguments borders on religious reasoning.
Once a sceptic always a sceptic, I guess.

The other thing that has surprised me about all this, is the reliance on human intelligence. Most ideas seem to be based on simulating human brains at super-speeds as if that will suddenly step up and spawn something wonderful.
I really don’t think human intelligence is really worth replicating. I’d hope we can come up with something a little better than that (remember point 3 from above). Super fast humans will just be even quicker to jump to conclusions.

http://www.thjsmith.com/feed">RSS Feed
  • Terms of use
  • Privacy Policy