For GPS on a bladeRF you have to start with Gold-sequences to find signals buried in noise: it is all about correlation

Gold-sequence

GPS-signals is all about correlation. The signals are completely buried in the noise. Only by searching (or knowing) the code-sequences and the Doppler frequencies is it possible to decode the signals. And they are all transmitted at that same frequency!

I did some experiments in python to get aquainted (again) with Gold-sequences and correlation. So, I programmed a class Gold and wrote some test-programs. Very nice experiments!

I had a lot of fun with it. Python is a very simple language. Plotting is a breeze. And with a class that you can import you get nice short programs. The IDLE editor is sufficient to get experiments running.


A very nice article is: “Understanding Spread Spectrum for Communications” at http://www.ni.com/white-paper/4450/en/

A python class "Gold"

In python I programmed the following class:

class Gold:
    
# Gold-sequence   goldutil.py
# Nov-2013 Kees de Groot
# call:
#   myprn1 = Gold(3, 7) for code phase selection = (3,7)
# or
#   myprn2 = Gold(4) for the 4th from the list
#    = satellite ID number = GPS PRN signal number

    # start with (0,0) to start numbering with 1
    # note that PRN 34 and 37 are identical
    prnlist = [ (0,0), (2,6), (3,7), (4,8), (5,9), (1,9),
                (2,10), (1,8), (2,9), (3,10), (2,3),
                (3,4), (5,6), (6,7), (7,8), (8,9),
                (9,10), (1,4), (2,5), (3,6), (4,7),
                (5,8), (6,9), (1,3), (4,6), (5,7),
                (6,8), (7,9), (8,10), (1,6), (2,7),
                (3,8), (4,9), (5,10), (4,10), (1,7),
                (2,8), (4,10)]


    def __init__(self, a, b = 0):
        self.shreg1 = [1]*11         # don't use first bit-position [0]
        self.shreg2 = [1]*11         # so count bit-positions from 1 to 10
        self.prnRegBinary = []       # contains 0 and 1
        self.prnRegAnalogue = []     # contains -1 and +1
        if b == 0:  # a = GPS PRN signal number or satellite ID
            (self.prn1, self.prn2) = self.prnlist[a]
        else:       # direct code phase selection
            (self.prn1, self.prn2) = (a, b)
        for i in range(1024):
            G1 = self.shreg1[10]
            G2 = self.shreg2[self.prn1] ^ self.shreg2[self.prn2]
            out = G1 ^ G2
            self.prnRegBinary.append(out)
            self.prnRegAnalogue.append(2*out-1)
            val1 = self.shreg1[3] ^ self.shreg1[10]
            val2 = (self.shreg2[2] ^ self.shreg2[3] ^ self.shreg2[6] ^
                    self.shreg2[8] ^ self.shreg2[9] ^ self.shreg2[10])
            # shift one position to the left
            for j in range(9):
                k = 10 - j
                self.shreg1[k] = self.shreg1[k-1]
                self.shreg2[k] = self.shreg2[k-1]
            self.shreg1[1] = val1
            self.shreg2[1] = val2

A first test-program:

import goldutil as gl

myGold37 = gl.Gold(3, 7)
prn1 = myGold37.prnRegBinary
prn2 = myGold37.prnRegAnalogue

print "the first 20 points of the binary version of Gold37:"
for i in range(20):
    print prn1[i],
print "\n..."
print "\nthe first 20 points of the analogue version of Gold37:"
for i in range(20):
    print prn2[i],
print "\n..."

with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
the first 20 points of the binary version of Gold37:
1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 
...

the first 20 points of the analogue version of Gold37:
1 1 1 -1 -1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 
...
>>>

With this framework I can write simple programs by importing the class Gold with the command
import goldutil as gl

Autocorrelation

As a first test I calculate autocorrelation.

# Gold02b.py
# autocorrelation
# nov-2013 Kees de Groot

import goldutil as gl
import pylab as pl

myGold37 = gl.Gold(3, 7)
prn2 = myGold37.prnRegAnalogue

# autocorrelation
ac = [0]*1024
for m in range(1024):
    for l in range(1024):
        ac[m] += prn2[l] * prn2[(l + m)%1024]
print "\nthe first 20 points of the autocorrelation of myGold37:"
for i in range(20):
    print ac[i],
print "\n..."
pl.figure(1)
pl.title("autocorrelation, note big peak of 1024 at x = 0")
pl.vlines(range(1024),[0]*1024,ac)
pl.show()

with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 

the first 20 points of the autocorrelation of myGold37:
1024 0 0 0 -68 -4 0 0 60 -8 4 4 -4 0 -4 60 64 60 -8 4 
...

There is nice peak at x=0, indicating positive correlation, the codes overlaps perfectly

Now correlate two different Gold-sequences.

# Gold02c.py
# correlation between different Gold-sequences
# nov-2013 Kees de Groot

import goldutil as gl
import pylab as pl

myGold37 = gl.Gold(3, 7)       # code (3,7)
prn1 = myGold37.prnRegAnalogue
myGold15 = gl.Gold(15)         # satellite 15
prn2 = myGold15.prnRegAnalogue

# correlation

ac = [0]*1024
for m in range(1024):
    for l in range(1024):
        ac[m] += prn1[l] * prn2[(l + m)%1024]
print "\nthe first 20 points of the correlation:"
for i in range(20):
    print ac[i],
print "\n..."
pl.figure(1)
pl.title("correlation between two different Gold-codes")
pl.vlines(range(1024),[0]*1024,ac)
pl.show()

with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 

the first 20 points of the correlation:
0 0 0 -64 0 0 0 0 0 -4 64 0 4 -4 -64 0 -4 -68 0 64 
...

There are some peaks, but not a single strong one, so there is no correlation.

The real thing

Now it is time for the real thing.

• Take a Gold-sequence of sat 18
• Shift it to the right 200 chips
• Add two more Gold-sequences: sat 4 and sat 17
• Now I have a shifted contaminated satellite signal.

First correlate with a Gold-sequence sat=20. Of course there is not any correlation, only noise
Then, the wonder: correlate with a Gold-sequence sat=18. We see an obvious peak at x=200.
So we know we found the satellite and we know the delay of the signal!

import goldutil1 as gl
import pylab as pl

# Gold04.py
# Generate a Gold-sequence, shift it 200 chips
#       and add two more different Gold-sequences
# then, correlate it with an arbitrary Gold-sequence
# and finally correlate it with the same Gold-sequence
# nov 2013 Kees de Groot

sat1 = 18                       # this is the sat we are looking for
myGold1 = gl.Gold(sat1)
pprn1 = myGold1.prnRegAnalogue

sat2 = 20                       # this is our guess1
myGold2a = gl.Gold(sat2)
pprn2a = myGold2a.prnRegAnalogue

sat2 = 18                       # this is our guess2
myGold2b = gl.Gold(sat2)
pprn2b = myGold2b.prnRegAnalogue

# shift pprn1 200 bits to the right
k = 200
for i in range(1024):
    temp = pprn1[(i + k)%1024]
    pprn1[(i + k)%1024] = pprn1[i]
    pprn1[i] = temp

# add two different Gold-sequences to pprn1
myGold3 = gl.Gold(4)
myGold4 = gl.Gold(17)
for i in range(1024):
    pprn1[i] = (pprn1[i] + myGold3.prnRegAnalogue[i] +
                myGold4.prnRegAnalogue[i])

# now pprn1 is contaminated with two other sequences
    
# cross-correlation with wrong Gold-sequence
ac = [0]*1024
for m in range(1024):
    for l in range(1024):
        ac[m] += pprn1[l] * pprn2a[(l + m)%1024]
print "\n 20 points around the peak at 200:"
for i in range(190, 210):
    print ac[i],
print "\n..."
pl.figure(1)
pl.title("correlation with different sequence")
pl.vlines(range(1024),[0]*1024,ac)

# cross-correlation with the right Gold-sequence
ac = [0]*1024
for m in range(1024):
    for l in range(1024):
        ac[m] += pprn1[l] * pprn2b[(l + m)%1024]
print "\n 20 points around the peak at 200:"
for i in range(190, 210):
    print ac[i],
print "\n..."
pl.figure(2)
pl.title("correlation with the right sequence")
pl.vlines(range(1024),[0]*1024,ac)

pl.show()

With output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 

 20 points around the peak at 200:
12 116 112 28 4 -4 -8 12 0 -48 -48 -36 -8 128 8 -4 -88 -20 -24 -28 
...

 20 points around the peak at 200:
48 104 124 184 72 -12 -32 0 60 8 708 -40 -20 -32 -32 80 12 -24 -80 -48 
...

Note there is no peak in the first run, but in the second run there is a peak with a value of 708, indicating strong correlation around delay = 200 chips.

Only noisy correlation, not one obvious peak

And there it is: a peak around x=200. A clear indication of the existence of a signal in the noise.

Conclusion:

I implemented the Gold-sequence as a class Gold in python.
With that class I first demonstrated a working implementation.
Then I did some experiments with (auto)correlation and finally demonstrated that you can find a certain code-sequence in a noisy contaminated signal and even calculate the delay of that signal.