Here is the code that decoded the strings on a 16F. It's 5 years since I did anything with it, and I don't know if there are any other subroutines that are needed for it, like multiply. I can't find the origianal program that included it.
The code also needs to be called lots of times as it is intended to be used in a PIC where other processes are running so it can't just hog the processor while waiting for more data.
Due to the limitations of the 16F, the programme has to decode the GPS strings as they arrive, rather than store the whole string and decode that. If you use a more powerful processor, you could store the whole string and decode it, which would certainly be easier to test on the MPLAB SIM. I had to change from a 16F to an 18F because I ran out of space, and then had to move onto a 24F.
The 24F pics do have a lot of nice features. To move an indexed array of data to an other indexed array using a loop in a 16F takes about 52 clock periods per byte and the loop is 12 lines of code. In a 24F, the same task takes 1 clock period per byte (16 bits moved every 2 clock periods) and the code is 2 lines long. Multiply and divide are also useful at times.
I have just noticed that I originally programmed it to decode the $GPGLL and $GPVTG strings. Hovwever, if you want MPH you have to scale the speed as it is in kmh or knots. I later decided to use $GPRMC which has all the information from those two, as long as you can handle the speed in knots.
I've since added $GPGGA decoding to get altitude and HDOP. That code is all in 24F pics.