company logo mid semester presentation spring 2008/9 performed by: alexander pavlovdavid domb...

Company

LOGO

Mid semester presentationSpring 2008/9

Performed by:Alexander Pavlov David Domb

Supervisor:Mony Orbach

GPS/INS Computing

System

GPS/INS Computing

System

AgendaAgenda

1. General overview1. General overview

2. Our Project2. Our Project

4. What’s Next…4. What’s Next…

GPS/INS Computing System

3. The Design3. The Design

GPS/INS Computing System

General overviewGeneral

overview“Even Noah got no salary for the first six months partly on account of the weather and partly because he was learning navigation.”

Mark Twain

Theoretical Navigation Algorithm Theoretical Navigation Algorithm

0

•Initialization

1

•Particle Propagation

2

•Particle Update & Normalization

3

•State Estimation

4

•Effective N calculation

5

•D computation

6

•Re-sampling

7

•Regularization

8

•Weight Re-computation

GPS/INS Computing System

Developed in the “Technion” and Implements the tightly coupled INS/GPS navigation unit, with the particle filter.

The algorithm stages:

Project GoalsProject Goals

Establishing the efficiency of the particle filter based, tightly coupled INS/GPS navigation unit realization.

Designing an efficient real-time particle filter based, tightly coupled INS/GPS navigation unit.

GPS/INS Computing System

GPS Computing System

Our Project

GeneralGeneral• Project will be performed in 2

stages. First part in this semester.• Project will be performed by

several work groups• Our group will implement Particle

Propagation and State Estimation stages in this first part.

• Both stages need to be performed whit in 0.01 sec, regardless of other stages performance.

GPS Computing System

Group Project Goals – Part 1Group Project Goals – Part 1

Learning GPS/INS navigation using Particle Filter algorithm

Learning VHDL language

Learning FPGA environment

Implementation of Particle Propagation and State Estimation stages of algorithm

GPS/INS Computing System

GPS/INS Computing System

TheDesign

Design guidelinesDesign guidelinesConstrains: large amount of calculations Limited hardware real-time results

Selected solution:Combining Parallel processing whit

Pipelines.

GPS/INS Computing System

X data structureX data structureTrue State Output Record

Field Sign bit Number bits Fraction bitsPosition 0 0 28

0 0 28dummy 0 16 0

1 14 9

Speed 1 13 101 13 101 13 10

Quaternion 1 1 221 1 221 1 221 1 22

Acceleration offset

1 0 231 0 231 0 23

Dreidel offset 1 0 231 0 231 0 23

GPS Receiver offset

1 14 90 24 0

Dummy 0 24 0

GPS Computing System

h

NV

EV

DV

1q

2q

3q

4q

X

Y

Z

X

Y

Z

bb

INS data structureINS data structureTrue State Output Record

Field Sign bit Number bits Fraction bitsAcceleration 1 5 42

1 5 421 5 42

Angular rates 1 2 451 2 451 2 45

GPS Computing System

xV

yV

zV

x

y

z

W data structureW data structureTrue State Output Record

Field Sign bit Number bits Fraction bitsWeight 0 0 24Dummy 0 24 0

0 24 00 24 0

w

Solution – Top designSolution – Top design

GPS/INS Computing System

Weight vector

Particles propagation

unit

State estimation

unit

Estimated State Vector

[1..18]

xN Extended State Vector

[1..18]

Extended State Vector

[1..18]

Extended State Vector

[1..18]

Co

ntro

ller

Controller AlgorithmController Algorithm

GPS/INS Computing System

While “FIFO” is NOT empty:• Every 5 clock cycles, send a new particle

from the “FIFO”, into the “TOP_6_PROP” (asserting the “START” signal to ‘1’).

Keep count of “START” signals given.Keep count of “FINISH” signals from the

“TOP_6_PROP”.For every “FINISH” signal, send the

matching weight vector and new propagated particle to the “TOP_ESTIMATION”.

Solution – Top designSolution – Top design

GPS/INS Computing System

Weight vector

Particles propagation

unit

State estimation

unit

Estimated State Vector

[1..18]

xN Extended State Vector

[1..18]

Extended State Vector

[1..18]

Extended State Vector

[1..18]

Co

ntro

ller

Particle propagation unitParticle propagation unit

GPS/INS Computing System

ParticlePropagation

UnitX(0:439)

INS(0:287)

X_out(0:439)

clockreset

start

finish

Particle propagation unitParticle propagation unit

GPS/INS Computing System

PropagationUnit

1

PropagationUnit

2

PropagationUnit

6

6 particles to 1

MUX

Propagationtimingcontrol

Propagation timing controlPropagation timing control

GPS/INS Computing System

Every “START” = ‘1’ :

counter = counter +1

Propagation unit i starts when:

“START” = ‘1’

AND

counter mod 6 = i.“FINISH” = ‘1’ when:

“finish_i” = ‘1’ for all i.

Particle propagation unitParticle propagation unit

GPS/INS Computing System

PropagationUnit

1

PropagationUnit

2

PropagationUnit

6

6 particles to 1

MUX

Propagationtimingcontrol

Single particle propagation data flowSingle particle propagation data flow

Format inputs to 48 bits

Calculate trigonometric

functions• Latitude sin/cos

Format trigonometric

function output to 48 bits

R_E, R_e, R_N calculation

Denominator calculation

• d_longitude denominator• d_latitude denominator

Dividers• d_longitude• d_lattitude• R_e

Particle

Propagation

GPS Computing System

Propagationflow

control

Propagation flow controlPropagation flow control

GPS Computing System

Solution – Top designSolution – Top design

GPS/INS Computing System

Weight vector

Particles propagation

unit

State estimation

unit

Estimated State Vector

[1..18]

xN Extended State Vector

[1..18]

Extended State Vector

[1..18]

Extended State Vector

[1..18]

Co

ntro

ller

Estimation unitEstimation unit

GPS/INS Computing System

EstimationUnitX(0:439)

w(0:23)

Estimated_DATA(0:439)

clockreset

New Data In

Estimation Ready

Estimation unitEstimation unit

GPS/INS Computing System

W*XW

X

ADDER

Timing AnalysisTiming Analysis

GPS/INS Computing System

1 particle LATENCY – 50 clock cycles (from “start” to “finish”) of propagation and weighting (according to simulation).

Propagation stage LATENCY – 45 clocks. Estimation stage LATENCY – 5 clocks.

With a pipeline (Throughput) of 5 clocks, and 6 parallel propagation units :

30,000 particles in 105,050 clocks =

= 7.5 ms @ 20Mhz.

COMMENTSCOMMENTS

GPS/INS Computing System

NO sin/cos blocks:

the design uses a “DUMMY” block with a latency of 30 clocks and no throughput.

The estimation of the quaternion matrix is left to be resolved by another grope (by software). The matrix is part of the design’s output.

MID-Results   MID-Results  

GPS/INS Computing System

According to the initial timing analysis, we will probably be able

to meet the timing demands - “with time to spare”.

GPS/INS Computing System

What’sNext…What’sNext…

Things to doThings to do

GPS/INS Computing System

Synthesis.Simulations and testing on the board.Final report.

GPS/INS Computing System

GANTTGANTT