A design methodology for the implementation of embedded vehicle navigation systems

Over the years, due to the increasing road density and intensive road traffic, the need for automobile navigation has increased not just for providing location awareness but also for enhancing vehicular control, safety and overall performance. The declining cost of Global Positioning System (GPS) receivers has rendered them attractive for automobile navigation applications. GPS provides position and velocity information to automobile users. As a result, most of the present civilian automobile navigation devices are based on GPS technology. However, in the event of GPS signal loss, blockage by foliage, concrete overpasses, dense urban developments viz. tall buildings or tunnels and attenuation, these devices fail to perform accurately. An alternative to GPS that can be used in automobile navigation is an Inertial Navigation System (INS). INS is a self-contained system that is not affected by external disturbances. It comprises inertial sensors such as three gyroscopes and three accelerometers. Although low-grade, low-cost INS performance deteriorates in the long run as they suffer from accumulated errors, they can provide adequate navigational solution for short periods of time. An integrated GPS/INS system therefore has the potential to provide better positional information over short and long intervals.;The main objective of this research was to implement a real-time navigation system solution on a low cost embedded platform so that it can be used as a design framework and reference for similar embedded applications. An integrated GPS/INS system with closed loop decentralized Kalman filtering technique is designed using trajectory data from low-cost GPS, accelerometer and gyroscope sensors. A data preprocessing technique based on a wavelet de-noising algorithm is implemented. It uses up to five levels of de-composition and reconstruction with non-linear thresholding on each level. The design is described in software which consists of an embedded microprocessor namely MicroBlaze that manages the control process and executes the algorithm.;In order to develop an efficient implementation, floating-point computations are carried out using the floating point unit (FPU) of MicroBlaze soft core processor. The system is implemented on a Xilinx Spartan-3 Field Programmable Gate Array (FPGA) containing 200 thousands gates clocked by an onboard oscillator operating at 50 MHz, with an external asynchronous SRAM memory of 1 MiB. The system also includes the IBM CoreConnect On-Chip Peripheral Bus (OPB). As such the final solution for vehicle navigation system is expected to have features like low power consumption, light weight, real-time processing capability and small chip area. From a development point of view, the combination of the standard C programming language and a soft processor running on an FPGA gives the user a powerful yet flexible platform for any application prototyping.;Results show that a purely software implementation of the decentralized closed loop Kalman filter algorithm embedded platform that uses single precision floating point numbers can produce acceptable results relative to those obtained from a desktop PC platform that uses double precision floating point numbers. At first, the Kalman filter code is executed from a 1 MiB external SRAM supported by 8KiB of data cache and 4KiB of instruction cache. Then, the same code is run from high speed 64KiB on-chip Block RAM. In the two memory configurations, the maximum sampling frequencies at which the code can be executed are 80 Hz (period of 12.5 ms) and 119 Hz (period of 8.4 ms) respectively, while accelerometer and gyroscope sensors provide data at 75 Hz. The same two memory configurations are employed in executing a wavelet de-noising algorithm with 5 levels of de-composition, reconstruction and non linear thresholding on each level. Accelerometer and gyroscope raw data are processed in real-time using non-overlapping windows of 75 samples. The execution latencies in the two cases are found to be 5.47 ms and 1.96 ms respectively. Additionally, from the post synthesis timing analyses, the critical frequencies for the two hardware configurations were 63.3 MHz and 83.2 MHz, an enhancement of 26% and 66% respectively. Since the system operates at 50 MHz, there is thus an interesting processing margin available for further algorithmic enhancements.;Thus, by employing the combination of a low cost embedded platform, a flexible development approach and a real-time solution, the implementation shown in this thesis demonstrates that synthesizing a completely functional low-cost, outage-resilient, real-time navigation solution for automotive applications is feasible.;Keywords: FPGA, MicroBlaze, INS, mechanization, wavelet de-noising, automobile navigation, Kalman filtering.