Brief study of Navigation System



This article is a study and an investigation on navigation systems,used and known worldwide as GPS device.This work is based on GPS signal specification of 1995 and recent additional improvements.The idea of writing this article was sparked a few years ago when i was working on a GPS project in my company.

The goal of this article is to introduce some important aspect of navigation systems to people who are seeking a start point to investigate on the matter, It’s a brief study and susceptible to have some errors slipped inside, so it cannot be considered as a reference or complete document..Some pictures have been taken from Google Images and history is added partly from GPS organisation resources.

  Notice:In this Article we are referring to a Civilian and general purpose GPS .


The Principal of GPS (Global Positioning System ):

GPS is a system providing time and location information. A GPS receiver is a device to use these information in order to guide a Vehicle, an airplane, reach its destination.most people think their device is emitting signals to achieve this purpose, but in reality a GPS receiver device is a passive device and its main purpose is to receive signals from satellite and not to send out. In fact the main job of every GPS receiver device is to calculate its own position from satellite’s position.


The emerging of GPS as we know today is related to General relativity; in fact in 1954 scientists were looking for a set of experiments to investigate on Einstein's general relativity using accurate atomic clocks around orbit.The GPS project started in 1973,initially for a military purpose,In 1983 Korean Air Lines Flight 007, carrying 269 people, was shot down  after straying into the USSR's prohibited airspace, after this accident President Ronald Reagan has ordered by a directive to make GPS available to civilians as well, and this was the birth of GPS in civilian purpose. It has been improved step by step and almost fully operational in 1994.

Initially, the highest quality signal was reserved for military use, and the signal available for civilian use was intentionally degraded ("Selective Availability", SA). This changed with United States President Bill Clinton ordering Selective Availability turned off at midnight May 1, 2000, improving the precision of civilian GPS from 100 meters (about 300 feet) to 20 meters (about 65 feet).AS we'll see later, the most prominent part of a GPS device is its Clock, which accuracy is playing a crucial role in every GPS receiver device.


Maybe better to review a few principal of Geometry which help us to understand better the fundamental of GPS

1) In a 2D geometry the intersection between a circle and a line is represented by two points.

2) In a 2D geometry the intersection between two circles is represented by mostly two points.

3) In 3D Geometry the intersection between a sphere and a plane is a 2D circle (mapped to 2D) (Fig1).

4) In 3D Geometry the intersection between two spheres is a 2D circle (mapped to 2D) (Fig2)

5) In 3D Geometry the intersection between a spheres and a  circle or 3 spheres is two points (Fig3)



By adding 4th sphere the intersection would be a point, and that’s the point we are interesting to,in a GPS study


To Simplify things ,I’m going to give you an Example in  2D geometry
Imagine  two city located on a map as A,B, and we know enough about them  in term of Geographical positions, we have also located a third city (P),and we want to calculate its position knowing we are given A,B position  and distance r1,r2. P will be the point of intersection of two circle of r1,r2 (distances) ,as we see here we have two points of intersection but just one of them is acceptable.


Therefore in order to find the correct position we need an additional point C, as shown here,


it’s also true when you look at the following equations:

(x-α1)² + (y-β1)² = r1²

(x- α2)² + (y- β2)² = r2² 

(x- α3)² + (y- β3)² = r3²

These equation will give us an unique answer, P(x,y)

This example demonstrate what a Navigation system is doing ,in fact it’s computing its position in an arithmetic way given the coordinates of other satellites, a Navigation system is a graphical calculator knowing enough about a few satellites in its line of sight, calculating its own location and track it on its preinstalled map.


Now replace Circles by spheres ,P is located somewhere on the earth,actually P is your receiver location.

In 3D ,Calculation is similar, we have to deal with a similar scenario, except that in this case we need 4 spheres instead of 3 to compute Intersection, and that’s exactly what your navigation system does, to calculate your position,it waits to identify at least 4 satellite in its view, then the process of calculation is starting to resolve 4 equations which results in a point (your position).In the following figure 4 satellite are found by your navigation system device 


By adding 4th sphere the intersection would be a point, and that’s the point we are interesting to,in a GPS study 

The following equations must be resolved by your device in order to find your position

(x-a1)² + (y-b1)² + (z-c1)² - r1² = 0  
2)² + (y-b2)² + (z-c2)² - r2² = 0  
3)² + (y-b3)² + (z-c3)² - r3² = 0  
4)² + (y-b4)² + (z-c4)² - r4² = 0  

x² + y² + z² - 2a1x - 2b1y - 2c1z + a1² + b1² + c1² - r1² = 0 

x² + y² + z² - 2a2x - 2b2y - 2c2z + a2² + b2² + c2² - r2² = 0 

x² + y² + z² - 2a3x - 2b3y - 2c3z + a3² + b3² + c3² - r3² = 0 

x² + y² + z² - 2a4x - 2b4y - 2c4z + a4² + b4² + c4² - r4² = 0

suppose :   

 a1² + b1² + c1² - r1² = 
a2² + b2² + c2² - r2² = 
3² + b3² + c3² - r3² = 
4² + b4² + c4² - r4² = 
 x² + y² + z² - 2a1x - 2b1y - 2c1z  = 0
- x² + y² + z² - 2a
2x - 2b2y - 2c2z  = 0
2x - 2a1x + 2b2y - 2b1y + 2c2z - 2c1z +  –  = 0

x² + y² + z² - 2a1x - 2b1y - 2c1z  = 0
- x² + y² + z² - 2a
3x - 2b3y - 2c3z  = 0
3x - 2a1x + 2b3y - 2b1y + 2c3z - 2c1z +  –  = 0

x² + y² + z² - 2a1x - 2b1y - 2c1z  = 0
- x² + y² + z² - 2a
4x - 2b4y - 2c4z  = 0
4x - 2a1x + 2b4y - 2b1y + 2c4z - 2c1z +  –  = 0

So we get 3 planes:
2x - 2a1x + 2b2y - 2b1y + 2c2z - 2c1z +  –  = 0
2a3x - 2a1x + 2b3y - 2b1y + 2c3z - 2c1z +  –  = 0
2a4x - 2a1x + 2b4y - 2b1y + 2c4z - 2c1z +  –  = 0

Assuming that:  

  –  =Δ1,      –  Δ2,      –  = Δ
2=a ; 2a1=b ; 2a3=g ; 2a4=j 
2=c ; 2b1=d ; 2b3=h ; 2b4=k 
2=e ; 2c1=f ; 2c3=i ; 2c4=l
Now we have three equations

x(a-b) + y(c-d) + z(e-f) + Δ= 0
x(g-b) + y(h-d) + z(i-f) + 
Δ= 0
x(j-b) + y(k-d) + z(l-f) + 
Δ= 0

These equation have only one answer =P(x,y,z) (your location)

Here an example of calculation made by a device Emulator


Distance between satellite and receiver shown as r1,r2,r3,r4……etc are calculated from the time a GPS signal takes to reach us, that means the difference between satellite clocks and  the time we get it In UTC, the data sent by satellite includes clock time and when we receive it ,we can calculate, the distance  by :


Where ri ,ti are respectively distance  and difference of time between satellite i  and our GPS reciever device.

C is the speed of light  or  an electomagnetic signal (approximately), Ti is included in information sent by satellite in Data analyse section (you will see  more in detail). 

The GPS of today as we know it, consists of at least 24 satellites in an orbit of 20000 km around the earth, 

they are transmitting GPS signals at 5 level of frequency L1 to L5 depending on what service is used ,Civilian,military,Nuclear detonation detection, forecasting and ionospheric studies,etc. 

The range of frequency is going from L1=1,1GHZ to L5=1.6GHZ .

The choice of this range is due to a few facts as below:

A)The frequency must be below 2GHZ ,if  f>2GHZ ,receiver has to adopt antenna equipment

B) Minimum influenced in therm of noise and weather conditions



Data Analyse and Programming:

A GPS signal data packet consists of two part C/V code mostly known as Golden code and navigation message , C/V code is generated as a very coplex pettern , but more details about it,is going beyond the scope of this article.The message includes all information a Receiver needs to know ,to compute its position,its frequency is 50Hz and modulated  with Golden code over a BPSK modulator on L1 then transmitted into air Fig8,Fig9.The data is divided into 25 frames (fig9) of 1500 bit (25*1500=37500).As I mentioned data transmission rate is 50HZ ,so to receive the whole message body,Receiver takes :DataSize/f=37500/50=12.5 min, each frame is received every 30sec 12.5 / 25 =30 sec.The frames contain information like position of every satellite including the sender of data .Satellites send constantly these informations,when you turn on your navigation system it must receive all 25 frames in order to identify the most visible satellites so your device takes about 12.5 min to get all frames if Quick fix is not done (see below),each frame is also divided to 5 subframe of 300 bit ,The two last subframes are used to identify a satellite , after identification receiver uses only three first subframes and  so it takes only 30 sec which is the time to get a frame.Every 30 sec it recalculate its position.

Subframe 4 contains information about satellite 25-32

Subframe 5 contains information about satellite 1-24

As we see here, each satellite sends out information about not only itself but also other satellites as well

Notice : GPS Receiver ,after receiving almanac and ephemeris, store them localy in order to be available in future (it uses them later)


A frame is divided into five subframes Fig11


TLM is a data header containing some information like age of Ephemeris data,etc it’s 30 bit in size and fig12 shows the fields structure in detail.HOW is used in a military purpose.The  satellites  broadcast  two  types  of  data,   Almanac   and  Ephemeris.   Almanac  data is course orbital parameters  for  all SVs.  Each SV broadcasts Almanac data for all SVs. This  Almanac data  is  not  very precise and is considered  valid  for  up  to several  months.Ephemeris data by comparison is  very  precise orbital and  clock correction for each SV and is  necessary  for precise  positioning.Eeach SV broadcasts only its own  Ephemeris data. This data is only considered valid for about 30  minutes. The Ephemeris data is broadcast by each SV every 30 seconds.When the GPS is initially turned on after being off for more than 30 minutes,  it "looks" for SVs based on where it is based on the almanac  and current time.With this  information, appropriate SVs can be selected for initial search. 

SV : Satellite in vision.


What is a Quick fix: 

almanac and ephemeris contains date/time information

This date/time is valid for 7 days, in which receiver knows enough about satellite, so during this period it can quickly switch to its position When you update you GPS receiver using you PC, almanac and ephemeris is up to date and receiver doesn’t wait for all 25 frames to be received, because It has already identified the satellite.After analyzing a GPS packet data, we  are able now to put the information into data structures which are much more significant for developers who want to put the concepts  into a system’s firmware. 

typedef Class CGPSData



        long  nCvPRNCode;//1023 bits  2^1023 possibility

        DATAFRAME Data[25];

        ...  ///Some Computation methodes 




typedef Struct DataFrame


        SUBFRAMEDATA SubData[5];//5 subframes 



typedef Struct Subframe //size of structure=300 bit 


        DWORD TLM;//30bit information= 8 preamble +16 bit data+ 6bit parity telemetry word=age of ephemeris data

        DWORD  HOW//17bit time of week+7bit data+6 bit parity Hand over word= time Ticks spent from the previous Sunday 0:00 o’clock (military use)

        DWORD CCD[8];//240 bits information ,satellite clock correction data ,allow synchronization between receiver and satellite


Khosrov Boloorian

March 2011

 © Xosrov 2016