Fast Fourier Transform (FFT) based Phase Lock Loops (PLLs) are provided for use in navigational signal receivers. In an embodiment, a navigation receiver correlates a received navigational signal with a locally generated signal into correlation samples, e.g., one-millisecond correlation samples. The navigation receiver includes a FFT based PLL that corrects phase shifts in the correlation samples due to the Doppler frequency by considering both the Doppler frequency and its rate of change, which are obtained from a FFT computation with interpolation. The phase corrected correlation samples are then integrated over a length of a navigation data bit, e.g., 20 milliseconds, to determine the sign of the data bit of the received signal. In another embodiment, a soft decision feedback technique involving integration extending over the present data bit and several prior data bits is used to determine the sign of a present data bit of the received signal.