Recovering the GPS Coarse Acquisition Code in Gnu Radio Companion

Gary Schafer, December 19, 2025

This is going to be a lot of information. Frankly, if this makes it as one post, I'll be surprised. It will probably take two. Maybe three.

Let's start with a bit of background: I just finished attending Dan Boschen's Digital Signal Processing for Wireless Communications class. One of the key takeaways from the class is that "correlation is key to understanding a lot of signal processing". (Sidenote: I wholeheartedly agree with this statement. )

ANYWAY, one of the examples he used was the coarse acquisition of the GPS, aka "the C/A code". This is the correlation of a chip stream with the signal from the GPS satellites. I decided to see if I could create a correlator in Gnu Radio Companion (GRC), then correlate it to actual GPS signals. Mr. Boschen even provided a small snippet (20 msec) of a GPS signal.

GPS Overview

GPS is a set of 24 active satellites in orbit around the Earth. Those 24 satellites are constantly transmitting a set of different signals on a few frequencies. The one signal with which we are interested is the C/A code, transmitted on the L1 frequency of 1.57542 GHz. (NOTE: The base clock frequency for GPS is 10.23 MHz. Pretty much everything is derived from this. The L1 frequency is 10.23 MHz x 154. In other words, it is the 154th harmonic of the base clock frequency.) The GPS works on direct sequence spread spectrum. This means that it uses "spreading codes" to spread the energy over a larger amount of spectrum than it would otherwise require. When talking about such things, we don't talk about "bits" but "chips". Just think of a "chip" as "a bit that is being used to spread in frequency another bit sequence".

Receiving the GPS Signal

Look, spread spectrum is an entire field unto itself. We're talking math of an insane order. Euler-phi functions and totients and maximal length and stages and states and primitive polynomials and... you get the idea. What I'm going to cover here are the following:

Generating the C/A spreading codes.
Correlating the spreading code with the GPS signal (the one provided in the class).
Collecting GPS signals using basic SDRs.
Synchronizing the code with the signal in order to recover the data.

Frankly, I think I'll be able to accomplish the first three. The fourth is going to be... iffy.

Let's get started.

Creating the Spreading Code

Let's look at what we need to do. Each satellite transmits its own C/A code. They're all derived from the same circuit, however. The GPS specification provides a nice diagram, shown below. First thing I had to figure out was could I actually create this circuit in Gnu Radio Companion (GRC). Without this, why bother with the rest?

Block diagram showing 10 small boxes set against each other in a horizontal row near the top of the diagram, and a second, similar set near the bottom. Lines connect certain of these boxes to the other boxes. Lines also extend down from the top row of boxes and up from the bottom row of boxes towards the center, followed by arrows that extend towards the right. — Diagram showing the linear feedback shift registers (LFSR) used in the coarse acquisition (C/A) circuit. There are two generators, labeled as G1 and G2 shift registers. These registers are shown as Fibonacci sequence generators. They are used together to create the final C/A code. The two registers of the G2 code are XORed together (determined by the specific satellite being recovered), and the output of that is then XORed with the output of the G1 register. This creates the final code. (Image credit: "Global Positioning System Standard Positioning Service Signal Specification, GPS Civil Performance Standards", Department of Defense, 5 November 1993, Figure 2-4.)

For my circuit, I will need the following:

Two linear feedback shift registers (LFSR).
That are synchronized.
And that I can tap off of two stages from one of them.

Creating the Linear Feedback Shift Register

There are two, general ways to create LFSRs. These are with Fibonacci shift registers or with Galois field shift register. The diagram shown above uses the setup for a Fibonacci-based linear shift register.

A long, horizontal rectangle divided into 10 squares. The squares are numbered 1 - 10 going from left to right. Above the rectangle is a circle with a plus sign in the center. Arrows come out of squares 3 and 10 and point into the circle; an arrow comes out of the circle and points to square 1. An arrow points down from square 1 towards the word \ — 10-stage Fibonacci linear feedback shift register (LFSR). This uses the feedback taps (10,3).

Two horizontal rectangles, one divided into seven squares on the left and the other divided into three squares on the right. All of the squares are numbered from 10 down to 1, starting on the left. Between the two rectangles is a circle with a plus sign in the center. An arrow comes out of the right most square (square 1) and points into the top of the circle. Square 4, which is just to the left of the circle, also has an arrow pointing into the circle. An arrow points out of the circle into square 3. Another arrow comes out of square 1 on the right and points over to square 10 all the way on the left. A final arrow points out of the bottom of square 1 pointing to the word \ — 10-stage Galois LFSR using the same feedback taps as before (10,3). This generator and the Fibonacci before it use the same feedback taps, and therefore will output the same sequence. *However, the sequences will not be synchronized.*

If you've read any of my posts on Gnu Radio, I prefer to create circuits using basic components. A LFSR would use a bunch of "Delay" blocks and one or more "XOR" blocks. It would actually be straightforward. But it would also require using feedback from the last delay block back into at least one of the other blocks (depending on the type of LFSR). Such feedback is not allowed in Gnu Radio flowgraphs. The only option is a GRC block called the "GLFSR", which stands for "Galois Linear Feedback Shift Register".

Synchronizing the LFSRs

This is a "good news / bad news" situation. Let's start with the good news. With the same set of feedback taps, both a Fibonacci LFSR and a Galois LFSR will output the same sequence. Even though we don't have a Fibonacci-based generator, we can still create the necessary sequences with the Galois block in GRC based on the provided feedback taps.

Just to make sure that the sequences were correct, I calculated the first couple of dozen chips for both the G1 and G2 generators. For the G1, I took out a couple of pieces of scrap notebook paper (I keep a large pile under my desk for just such an emergency.) and, by hand, calculated what the first 20-ish chips or so should be.

Notebook page with a horizontal row of 10 squares across the top numbered from 1 - 10 starting on the left. Underneath are roughly 20 rows of ones and zeros. — This is the handwritten running of the G1 LFSR. The top row of 1s is the initialization vector (the initial fill or "seed"). The registers move the chips from left to right. The first register (1) gets its input from the XOR of registers 10 and 3.

Darkened notebook with handwritten notes. The top of the page has a row of 10 squares numbered from 1 - 10 from left to right. Underneath are roughly 20 rows of ones and zeros. The top row, consisting of all ones, is easily seen, as is the first column. The rest of the page is darkened. — This page highlights the first 22 chips output from the G1 LFSR. Because the top row is all 1s, this means it can be the same backwards or forwards. The first 10 chips output are all 1s. After that, we can use the first column to get the output chips. The next 12 chips are 000111000100. Thus, the first 22 chips are 1111111111000111000100. This is the same as the first 22 chips in the time sink above.

I repeated the same thing for the G2 generator. For this, I created a Libreoffice Calc page to do the calculations. (Full disclosure: I did it by hand at first, but due to the number of feedback taps, I made a lot of mistakes. I created the Calc page out of frustration. Turns out it was much easier.)

Spreadsheet consisting of roughly 40 rows and 10 columns. The top row is numbered from 1 - 10, while the remaining rows are numbers of either 1 or 0. — Libreoffice Calc spreadsheet that mimics the output of the G2 generator. Looking at the first column (which shows the output that should come after the run of 10 1s), it matches the output in the zoomed image of the output from the Gnu Radio G2 simulation.

Spreadsheet consisting of roughly 40 rows and 10 columns. The top row is numbered from 1 - 10, while the remaining rows are numbers of either 1 or 0. The top row and left-most column are highlighted in yellow. — This is the same Calc page, but with the top row and left-most column highlighted. Since the initial fill is all 1s, it reads the same either forward or backward. Further, the newest bit comes in at the left end and does not change until it is output on the right. This means we can read the output starting in the top, right corner, going right-to-left on the top row, then down the left-most column to give you the first several chips output from this generator.

Using the same feedback taps ("Mask") as stated for the G1 and G2 generators in the GLFSR block means we should get these sequences.

Now comes the bad news. They will not start at the same point in the sequence. The two generators, G1 and G2, need to be synchronized. Given an initial fill and the fact that they're based on Fibonacci-based generators, the first 10 chip output from each should be 10 1s. A 10-stage Galois-based generator will have an output of the first 10 chips of... who knows? If I can figure out where the 10 1s occur in the Galois-based output, I can use a Delay to shift the sequence to that point. But how do I figure that out? I could look for some math somewhere that might tell me, or I could just create a flowgraph and measure it.

I think I'll do the latter.

I started with the G1 generator. I created a simple flowgraph that takes the output of the GLFSR with the requisite number of taps ("Degree", in the block parameters), the correct feedback taps ("Mask" in the parameters) and initialization vector ("Seed" in the parameters). According to the specification, this LFSR should be maximal length, meaning that it will run for 2¹⁰-1=1023 chips before it starts to repeat. I used a "QT GUI Time Sink" to look at the output. I set the time sink to a length of 1023 and a sample rate of 1. (NOTE: By setting the sample rate to "1" and ignoring the units, any measured values will simply be "chips" or "bit" numbers.) If the chip sequence coming out of the "GLFSR Source" block was, indeed, maximal length, then the chip sequence should appear static in the time sink. The following are the flowgraph and the result when I ran it.

Block diagram consisting of six blocks in two rows. The top row contains two blocks. The bottom row contains four blocks, with these four blocks connected by lines running from left to right. — Gnu Radio flowgraph of a basic test of the "GLFSR Source" block. The block parameters have set it to have 10 registers, feedback at taps 10 and 3, and an initialization of all 1s (2¹⁰ - 1 = 1023). This is what the GPS specification states is for the "G1" shift register for the C/A (coarse acquisition). The "Sample Rate" setting in the time sink has been set to "1" so that the horizontal scale can be read as "chips".

Graph showing the top half with a random-looking chip pattern filling the display from one end ot the other. — Display of the full chip pattern. It doesn't show since this is a still image, but the display appears static. That means that it is not changing as it updates. And *that* means that the chip pattern is a 1023 chips long. This confirms that the output is maximal length.

The time sink display was static when I ran the flowgraph. So this shift register is maximal length (1023 chips). Now I need to get the sequence aligned so that the first 10 chips are all 1s (the same as the initial fill). Zooming in on the time sink, I can see that the sequence in the time sink actually starts within the initial fill, with 7 1s before the beginning (meaning that they show up at the very end of the time sink) and 3 1s at the beginning of the time sink. Adding a "Delay" at the output of the GLFSR will allow me to shift the sequence to the right. Thus, by using a delay of 7 samples, the sequence should start precisely at the beginning of the initial fill just as I need it.

Graph zoomed in on the left end showing a variable chip pattern of roughly 20 chips. — This is the zoomed-in view of the left end (the first chips) of the output of the "GLFSR Source" block from the flowgraph above. The first three chips are 1s. These are the last 3 1s of the initial fill. The remaining 7 occur at the end of the sequence within the time sink.

A set of blocks in two rows. The top row consists of two blocks. The second row consists of five blocks connected by lines. The blocks extend from left to right. — Gnu Radio flowgraph with a delay in the output of the LFSR. This effectively shifts the entire sequence to the right, with the end chips being wrapped around back to the beginning. The "Sample Rate" setting in the time sink has been set to "1" so that the horizontal scale can be read as "chips".

Okay, that worked. I now have the G1 generator creating the code I need and at the correct point in time. On to the second generator, G2. Here's the flowgraph and results using the same method as for the G1.

The G2 sequence is now aligned properly and it matches the sequence as generated in the Calc page.

So that works. Which is nice.

Full GPS C/A Generator

We now have the two chip sequences, G1 and G2, and they are synchronized. Next problem, as stated in the specification:

The effective delay of the G2 sequence to form the G2i sequence is accomplished by combining the output of two stages of the G2 shift register by Modulo-2 addition

In other words, I need to tap off two of the 10 stages from the G2 LFSR. The purpose is to create yet another sequence. Tapping and XORing two registers gives us a certain sequence. Regardless of the pairs selected, the sequence will be identical, only shifted in phase.

But I can't access the G2 generator registers directly. The "GLFSR Source" block does not provide for that. So, Plan B. Run the output through a set of 10 delays and treat these delays as the stages of the G2 LFSR. This should at least give me the access to the correct registers in the correct order to create the XOR of the G2 register pair. Note that this only works since the specification uses a Fibonacci-based generator. It wouldn't work if the original specification said, "Use a Galois-based generator". This is because the Fibonacci-based generator dumps the XORed chips into the first stage. They don't change from there until the output. Therefore, using 10 "Delay" blocks should give me the exact, same sequence as if I'd been able to tap directly off of the linear shift register.

Table consisting of 5 columns. A few footnotes are listed at the bottom. — Code phase assignments table from the GPS specification (November 1993). It shows the G2 register taps for each of 32 satellites, the delay of the S1 + S2 XOR (the two stages tapped off of the G2 generator), as well as the first 10 chips for each, final sequence (last column). Converting these values from octal to binary, they can be used to confirm that the GRC flowgraph is generating the correct code sequence.

Graph showing a line that varies between 1 and 0. — Graph of the output of XORing two stages of the G2 generator. The specific stages here are 2 and 6. According to the "Code Phase Assignments" table, this pair should have a delay of 5. Putting the cursor over the beginning of the sequence (It begins at the start of the run of 10 1s.), the delay is measured as 5.

The delays give me access to the various stages of the G2 generator, as desired. The downside is that this screws up the timing between the G1 and G2. All of these delays effectively shift the G2 sequence to the right 10 chips. Fortunately, the delay directly at the output of the G2 "GLFSR Source" block is pretty high (320). By lowering this number by 10 (to 310), the output from the delays should be aligned with the G1.

Block diagram consisting of three rows. The top row starts with two blocks unconnected to anything. The remaining blocks to the right are connected from left to right. The center and bottom rows also consist of several blocks connected from left to right. — Gnu Radio flowgraph to fully mimic the GPS C/A code. The two primary code generators, G1 and G2, are on the left. The output of the G2 generator passes through 10 "Delay" blocks to mimic the stages of the block itself. To account for this, the "Delay" directly at the output of the G2 generator block is reduced by 10 (from 320 to 310). The "Virtual Sink" blocks marked S1 and S2 act as the taps from the two stages of the G2 generator. They are XORed together, and the output is then XORed with the output of the G1 generator create the final C/A code. The GPS specification provides for 32 codes, which are provided by tapping a specific pair of registers from the G2 generator. This flowgraph taps registers 2 and 6, which is used for satellite ID #1.

Comparing the output from the last "Delay" block with what the output should be for the G2 generator, they are identical. Thus, I now have a working G2 generator and this will allow me to access the stages of the G2 generator, as needed.

I've added two "Virtual Source" blocks to provide for the taps from the stages of the G2 generator. Combining these with an XOR should give me the needed sequence from the G2 generator. Then, I combined this XOR output into another XOR, of which the second input was the G1 generator.

Next step: I need to check that the output is correct. Fortunately, the specification helps with this by providing the first 10 chips of each G2 tap pair. Comparing the output of the XOR of the S1+S2 XOR with the G1 generator, the first 10 chips are correct for each of the first 10 sequences. That's enough for me. I'm confident that the generator works, as desired.

Correlating with a Real GPS Signal

I wanted to test out these codes. One of the benefits of attending Mr. Boschen's class was that he provided a nice, small file of GPS data (two of them, actually!) that he'd collected. I decided to try out my codes against his data set. If it didn't work with that data, then I'd need to relook at my work.

Let me add a little tidbit. There are 32 codes for the original GPS system. Each one requires 1023 chips. Even storing them as one chip per byte (the way that is easiest in Gnu Radio Companion), that's only 32 kB of storage. That's just a rounding error on the storage space most systems have available. You can even lower that by packing 8 chips/byte and the total storage required is 4 kB. That's literally 1 sector on older hard drives. (No idea if sectors are still a thing with .M2s and SSDs.) For now, I recorded each spreading code in a separate file, 32 in all.

Now that I have the spreading codes figured out, time to tackle the next problem. That problem is Doppler shift. GPS satellites are constantly trucking along. They're moving at roughly 3.87 km/sec. Given a person standing on Earth and working through the math, this means a person will see a maximum Doppler shift of roughly +/-4900 Hz.

I created a GRC flowgraph that would account for both the spreading code and the Doppler shift. It would read in the signal samples and one spreading code, cross-correlate them, and provide an output showing if correlation occurred. Further, I added the ability to step through the Doppler offsets most likely to be encountered.

Block diagram showing 5 rows of blocks with arrows connecting the blocks in each row going from left to right. — GRC flowgraph to test the codes using some provided GPS data. The data was captured using an oscilloscope from a signal that has been received using a GPS "puck" antenna, amplified, filtered and frequency shifted down to an intermediate frequency (IF) of 2.5 MHz. The sample rate was 20 MHz, and the data stored as a real signal using 32-bit floating point samples. This flowgraph takes the signal and the desired spreading code, imports them, converts them to the frequency domain via the FFT, multiplies one with the complex conjugate of the other, then reverts them back to the time domain via the inverse FFT. The final time sink displays the cross-correlation between the signal and spreading code.

Mr. Boschen showed a cross-correlation of his signal with the spreading code for SV24. It showed very strong, very clear spikes. So I used my SV24 spreading code against Boschen's data. And it worked.

A display showing a set of vertical lines going from the bottom of the display up about 3/4 of the way to the top. Along the bottom are sliders and the words 'Frequency Shift' and 'Fine Frequency Offset'. — Cross-correlation of Boschen's GPS data with my SV24 spreading code. It achieved a strong correlation at roughly 1080 Hz. This is the offset required due to the Doppler shift.

Compare this with two, other codes, SV01 (no correlation) and SV06 (small correlation).

A display showing a varying, noisy line along the bottom of the display. Along the bottom are sliders and the words 'Frequency Shift' and 'Fine Frequency Offset'. — Correlation display for C/A code SV01 with the Boschen data set. There was no identifiable correlation spikes found.

A display showing a set of vertical lines going from the bottom of the display up about 1/8 of the way to the top. Along the bottom are sliders and the words 'Frequency Shift' and 'Fine Frequency Offset'. — Correlation display for C/A code SV02 with the Boschen data set. There was a small correlation found with this code.

Now that I knew the circuit worked, I added another feature: automatically scanning through all of the Doppler shifts. This was a feature that Dan Boschen put in his circuit. I simply converted the idea to use in a Gnu Radio flowgraph.

Block diagram showing several rows of blocks connected by lines. — Flowgraph to correlate a GPS signal with the SV codes. This flowgraph will automatically scan through all possible Doppler shifts in a stepsize, in Hz, set by the variable "stepSize". The minimum stepsize should be less than 1 kHz. The smaller the stepsize, the better the sensitivity (and the more correlations will be found for a given signal). Another factor is the integration time. The longer the integration time, the better the sensitivity. However, increases in either will slow down the scan time. Due to the manner in which Gnu Radio processes data, the amount of delay between switching SV codes and the display being updated is roughly 5 seconds. (This is with a high-end processor.) This flowgraph displays the data using a Constellation Sink. The horizontal axis is the Doppler shift, in Hz.

Graph of a set of individual vertical lines along the bottom extending from left to right. A few lines extend towards the top with small dots along the line. — Graph showing correlation vs Doppler shift (in Hz). Note that this graph shows a correlation between -1000 and -1200 Hz. The measured Doppler shift for this SV code was found to be roughly -1100 Hz.

This gives me a Gnu Radio flowgraph that I can use to test against GPS signals that I'll try to collect next. I'll stop this post here. As expected, this will require multiple posts.

Random Quote Board