Version Alpha of GPS python code

Thanks to one of the comments, I found out that the python code Isaac Carroll was working on is no longer available online. Since it was developed under the gpl license we will now 'fork' it and continue on. Until I get a chance to get the code under sourceForge, here is the current state of the python code.

Discrete Signal and the Stem Plot

I will start using this blog to start researching and documenting the start of the book, "Digital Signal Processing using gnuRadio." After the introduction, the first chapter is on discrete signals. Therefore, let us see what we can do in gnuRadio and python to represent and visualize discrete signals. The gnuRadio data types are as follows:

• Byte: 8 bits per data element
• Short: 2 byte integer
• Int: 4 byte integer
• Float: 4 byte floating point
• Complex: two floats, 8 bytes

A discrete signal is represented by a set of numbers denoted as a sequence

x(n) = {..., x(-1), x(0), x(1), ...}

This is easily done in gnuRadio using a vector block. Since gnuRadio is really about streams of data, it can be a little akward to work outside this framework to demsonstrate some basic DSP principles. First, we will just plot a sequence using gnuRadio and pylab. The discrete nature of the signal can be emphazied through a stem plot. A picture of the discrete signal, x(n) = {-4, -2, 0, 2, 4} for the samples, n = {-2, -1, 0, 1, 2} is given below using pylab, without really using gnuRadio. The code for this example is stem_pylab.py.

Next, we use gnuRadio to add the constant value 2.0 to the above signal. This is accomplished using the add_const_ff(2.0) signal processing block along with the Vector Sink and Source blocks. Note how we set up the gnuRadio graph, Vector Source Block -> Add Constant Block -> Vector Sink Block. We then access the data through dst.data() and plot it using pylab. The code for this example is stem_gnuradio.py.

GPS Acquisition

After a break of almost a year to finish my thesis, I am back to explore GPS using the USRP. The good news is that I was able to 'acquire' (coarse) satellites with the dbsrx daughter board. Unsure of the best gain to use, I collected data for four different gains: 76 dB, 86 dB, 96 dB and 104 dB. Also the active antenna I am using is Gilsson part # SMA-M, which adds 28 dB of gain and can be found here. The gnuRadio commands used to collect the data were

./usrp_rx_cfile.py -g 76 -d 8 -f 1.57542G -N 500M gps76.usrp
./usrp_rx_cfile.py -g 86 -d 8 -f 1.57542G -N 500M gps86.usrp
./usrp_rx_cfile.py -g 96 -d 8 -f 1.57542G -N 500M gps96.usrp
./usrp_rx_cfile.py -g 104 -d 8 -f 1.57542G -N 500M gps104.usrp

Since the decimation is 8, then 500M samples/ 8 Ms/s = 62.5 s, so there is just over 1 minute of data for each gain value. The time the data was taken is around 10:02 AM, May 22, 2007 in Colorado Springs, Lat = N38 52.160', Lon = W104 49.589'. The satellites in view at this time according to my Garmin receiver (which did not track all of these) were

Sats PRN: 03, 06, 07, 09, 14, 16, 18, 21, 22, 24, 26, 29

Of course a bunch were at low elevations and with all the trees in my yard, I was only able to track about half of them. On to the data.

Once again acquisition is achieved using the python code develeped here. Note that you must change some values to correspond to how the data was taken so set these values to

SAMPRATE = 8e6
CENTERFREQ = 0e3
NSIDEFREQ = 50

The number of frequencies to search is increased because of the oscillator on the USRP has a higher error than GPS receivers. One could expect to add at most around +/- 10kHz freqs. to be searched because of doppler and I was getting frequency offsets as high as 24kHz. Results with an 8 sigma acquisition threshold are shown below for the 86 dB gain case

Sat. , Freq. , Code offset, Num. of chunks
-------------------------------------------------------------------------
07 , -17000 , 2648, 6
18 , -2000 , 1988 , 7
21, 20000, 1420, 3
22, 22000, 5464 , 2
24, -18000, 3655 , 5

Plots of the data:

Frequency Steps in Acquisition

In the previous posts, a step size of 500 Hz was used. In the book, "Fundamentals of Global Positioning System Receivers A Software Approach", for 1 ms data blocks, we should use 1000 Hz, not 500 Hz. So let's compare results. For 1 block of data, a second peak really shows itself. Not very encouraging. It is important to note that the carrier was still 3125 and offset was 3107.



Let's try more blocks. We still get a 9-sigma hit, but it takes us 6 blocks, so we lost a little performance going to 1000 Hz steps.



To make it interesting let's attempt 250 Hz steps. It appears to have not really changed from the 1000 Hz example.



And for multiple blocks,



Once again, no real improvement over the 1000 Hz step. Note that just trying this on one SV and one set of data is really not statistically significant, but it is a good check to see which variables might have a hug impact on acquisition.

Playing with acquisition code, coherent time and number of incoherent blocks

After several unsuccessfully attempts at acquisition on data obtained from the dbsrx board, I'm taking a step back to play with the acquisition code to learn more about the problem. A very discouraging post was on the gnuradio mailing list by Matt. Basically, it looks like the current oscillator is going to cause a problem, "The oscillator on the USRP is spec'ed to 50 ppm, so you could be as much
as 79 kHz off plus doppler." With doppler adding +/- 10 kHz, a search of +/- 90 kHz will not be good for a real application. I will have to look into getting a better oscillator (not really a big deal).

Here are a few example plots using the data from the previous post. The first graph shows coherent correlation on 1 ms of data. For a positive hit on acquisition, the best threshold that could be achieved was 5-sigma.



For SV 19, the carrier frequency was found to be off by 3125 kHz and the CA code offset was 3107. Which can be plainly seen in the plot. This amplitude really doesn't 'stand out' and tells us we have a week signal. Getting a better trust on whether or not we have detected the correct signal can be done by noncoherent integration. Basically, we sum together blocks of data. Below is a picture of using 6 blocks of data.



Here we can definitely see a good peak and the threshold was set to 9-sigma. Now it is time to do some variation and see how it affects our acquisition. Let's first due coherent integration over 2ms. Below is the output



Well, a new peak occurs at an offset of 7107. I think since the CA code repeats every 1 ms, if we divide by 2, we get an offset of 3553.5, close to the 3107. Let's see what more blocks show.



Which gives the same offset 7107. Interesting enough, to get 9-sigma it only took 4 blocks of data instead of the 6 blocks needed for 1ms blocks. Finally, lets try 5ms before we move on to other variables. We get more peaks, but nothing overly strong



We can now see 5 peaks, about equally spaced with the strongest at 7107.

GPS Software Correlator for the USRP

Well, thanks to Google's summer of code and student Isaac Carroll at Portland State University, the foundation of a GPS software receiver for the USRP has been laid. For his project he developed a working GPS software correlator that works on captured data from the USRP. A link to the project page is here. Although, there is a lot of work to be done to bring it into the gnuradio framework (i.e. C++ blocks), its great to have some working python code to test feasibility. Speed is really the major roadblock for the python code. After profiling the code, determination of the threshold based on standard deviation of data is a major slowdown. Using the acquire.py code is quite simple and an example for the data found on KD7LMO's website can be downloaded here. After all the python code has been downloaded from the trak page (first link) you can run the example by

python acquire.py gps_4m_complex.dat

GPS C/A code generator

Download the python code which generates a 1023 bit code for each of the GPS satellites. A post will come soon with a detailed description. Hopefully, I'll be able to acquire the code off of sample signals in the the coming weeks. Feel free to download the source CA_code_gen (if this fails get it here . This and the rest of the receiver will be under the GPL.

gnuRadio build for Ubuntu

Instead of using the 2.5 tarballs, I've decided to go off of cvs. Before downloading the files, I need to install the library dependencies

1. SWIG
2. FFTW
3. Boost Library
4. CPP Unit


I had a lot of problems getting it installed, however 4 hours later I successfully ran the USRP tests. Below is the cronological order of my ordeal. The 2 secrets were to follow the instructions on the list here and I had to use swig version 1.2.24, 1.2.25 would not work so beware.

DO NOT FOLLOW THE ORDERS BELOW, it is for information and googling only and may help diagnose your problem. Do the above mentioned steps.


The system I am running is Ubuntu 5.04. Under Applications->system Tools->Add/Remove Programs choose the Advanced options and do a search for SWIG. As you can see the only option is for swig 1.3.22 and the User's guide specifies version 1.3.24 as a minimum. So off to www.swig.org to build from source. Nothing fancy was done, just the normal ./configure, make, make install.

For the FFTW library, we need at least version 3.0.1. In the Synaptic Package Manager we see ubuntu has version 3.0.1-11, yeah! So install from the package manager. Just to be safe I installed all the other fftw3 packages. Hopefully, the binary version is compiled for single precision (usually it has multiple versions). Going to the package properties, we see that the package contains the shared library version of the fftw libraries in single, double and long double precisions. Onward ho!

The package manager has lots of libboost packages, I just need to choose the correct one. I chose to install libboost-dev and libboost-python-dev.

Finally, I install the cppunit, libcppunit-1.10-0 and the libcppunit-dev libraries from the package manager. So it seems Ubuntu makes it fairly easy to install, they just need to get the newer version of SWIG. The future is promising for a gnuRadio package. Actually, after searching I found the libgnuradio package, but I am not sure which version it is so I'll stick to my guns and stay with CVS version. I am now ready to follow the cvs instructions given here.

Well, the first road block is to install the dependencies that show up while trying to install. The errors I got are:

./bootstrap: line 25: aclocal: command not found
./bootstrap: line 26: autoconf: command not found
./bootstrap: line 27: autoheader: command not found
./bootstrap: line 28: libtoolize: command not found
./bootstrap: line 29: automake: command not found

So I'll start with automake. Yikes, a bunch more errors show up after this,

aclocal: macro `AM_PATH_PYTHON' required but not defined
configure.ac:24: error: possibly undefined macro: AM_CONFIG_HEADER
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
configure.ac:26: error: possibly undefined macro: AM_INIT_AUTOMAKE
configure.ac:31: error: possibly undefined macro: AM_CONDITIONAL
configure.ac:51: error: possibly undefined macro: AC_LIBTOOL_WIN32_DLL
configure.ac:53: error: possibly undefined macro: AC_ENABLE_SHARED
configure.ac:54: error: possibly undefined macro: AC_DISABLE_STATIC
configure.ac:55: error: possibly undefined macro: AC_PROG_LIBTOOL
configure.ac:139: error: possibly undefined macro: AM_PATH_CPPUNIT
configure.ac:140: error: possibly undefined macro: AC_MSG_ERROR
autoheader: error: AC_CONFIG_HEADERS not found in configure.ac
./bootstrap: line 28: libtoolize: command not found
automake: configure.ac: installing `./install-sh'
automake: configure.ac: installing `./mkinstalldirs'
automake: configure.ac: installing `./missing'
configure.ac: 55: installing `./ltmain.sh'; cannot run `libtoolize': No such file or directory
configure.ac: 24: required file `./config.h.in' not found
src/lib/Makefile.am:55: variable `CPPUNIT_LIBS' not defined
automake: src/lib/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
src/lib/filter/Makefile.am:173: MD_CPU_generic does not appear in AM_CONDITIONALsrc/lib/filter/Makefile.am:178: MD_CPU_x86 does not appear in AM_CONDITIONAL
automake: src/lib/filter/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
automake: src/lib/general/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
automake: src/lib/io/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
automake: src/lib/missing/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
src/lib/omnithread/Makefile.am:36: OMNITHREAD_POSIX does not appear in AM_CONDITIONAL
src/lib/omnithread/Makefile.am:41: OMNITHREAD_NT does not appear in AM_CONDITIONAL
src/lib/omnithread/Makefile.am:46: variable `PTHREAD_LIBS' not defined
automake: src/lib/omnithread/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
src/lib/runtime/Makefile.am:28: variable `SHM_OPEN_LIBS' not defined
automake: src/lib/runtime/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
src/lib/swig/Makefile.am:64: bad macro name `_gnuradio_swig_python_la_SOURCES'
src/lib/swig/Makefile.am:68: bad macro name `_gnuradio_swig_python_la_LIBADD'
src/lib/swig/Makefile.am:73: bad macro name `_gnuradio_swig_python_la_LDFLAGS'
src/lib/swig/Makefile.am:68: variable `PYTHON_LDFLAGS' not defined
automake: src/lib/swig/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
automake: src/tests/Makefile.am: C++ source seen but `CXX' not defined in `configure.ac'
>>> build FAILED in /home/bloftin/gnuradio/dependencies/gr-build/gnuradio-core

I believe an error occurred when downloading from cvs so I am starting over from the cvs command. Still having problems. After googling the error, I found a similar thread on the gnuradio list and the problem seems to be with the version of automake. Note, I had to completely uninstall automake 1.4 for it to get past these errors. However, I can tell there will be more... From the above thread I try

$ cd gnuradio-core/src/lib/swig
$ make clean
$ make install

no luck, so I install libusb-dev and sdcc packages. Also removed gcc 3.3 and installed gcc 3.4 and libtool 1.5.6-5 and then added g++-3.4, but also kept g++-3.3. Then I got the error

configure: error: cannot find usable Python headers

A clear sign of needing python development, so I added package python2.4-dev. Ugh! Yet another error, but one step further:

configure: error: Failed to locate boost/shared_ptr.hpp.
Try using --with-boost-include-dir=

Installed package libboost-dev. A little further, but now the error

../../../libtool: line 1089: g++: command not found

and sure enough I cannot run g++ from command line so I will reinstall it. I can see /usr/bin/g++-3.3 /usr/bin/g++-3.4, but instead of adding a link, I'll reinstall just in case. Still no gcc so I will make a link.

$ sudo ln -s /usr/bin/g++-3.4 /usr/bin/g++

... recompile, looking good

But the make checks failed for test_all, tried

$ cd gnuradio-core/src/lib/swig
$ make clean
$ make install


Now trying instructions given in list here.

Trying swig 24 instead of 25, we shall see! After installing swig 24 I needed to run
$ cd gnuradio-core/src/lib/swig
$ make clean
$ make install

I've made it to USRP directory. Onward!

Yeah it finally worked! Now trying to test USRP, I've continued on with instructions here.

cp firmware from usrp tarball

next add user to usrp group

I have to run usrp/host/apps/... as sudo
transmitting at 11.62 Mb/s
receiving at 32 Mb/s

So I still have a lingering USB permission issue, but it will have to wait until tomorrow since the above has taken 4 HOURS!