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


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


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 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.


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



TheDesign

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

Selected solution:Combining Parallel processing whit

Pipelines.


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


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


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


Weight vector

Particles propagation

unit

State estimation

unit

Estimated State Vector

[1..18]

xN Extended State Vector

[1..18]

Extended State Vector

[1..18]


[1..18]

Co

ntro

ller

Controller AlgorithmController Algorithm


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”.



Weight vector


unit

State estimation

unit


[1..18]


[1..18]


[1..18]


[1..18]

Co

ntro

ller

Particle propagation unitParticle propagation unit


ParticlePropagation

UnitX(0:439)

INS(0:287)

X_out(0:439)

clockreset

start

finish



PropagationUnit

1

PropagationUnit

2

PropagationUnit

6

6 particles to 1

MUX

Propagationtimingcontrol

Propagation timing controlPropagation timing control


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.



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


Propagationflow

control

Propagation flow controlPropagation flow control




Weight vector


unit

State estimation

unit


[1..18]


[1..18]


[1..18]


[1..18]

Co

ntro

ller

Estimation unitEstimation unit


EstimationUnitX(0:439)

w(0:23)

Estimated_DATA(0:439)

clockreset

New Data In

Estimation Ready

Estimation unitEstimation unit


W*XW

X

ADDER

Timing AnalysisTiming Analysis


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


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


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

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


What’sNext…What’sNext…

Things to doThings to do


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


GANTTGANTT

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

Documents