Upload
leo-lindsey
View
215
Download
0
Embed Size (px)
Citation preview
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