McElieceTalk

Information about McElieceTalk

Published on February 5, 2008

Author: Paola

Source: authorstream.com

Content

Routing in Error-Correcting Networks:  Routing in Error-Correcting Networks Edwin Soedarmadji May 10, 2006 California Institute of Technology Department of Electrical Engineering Pasadena, CA 91125, USA Introduction:  Introduction Start from an unrelated network problem Route planning under fuel capacity and refueling constraints Especially relevant Increasing energy cost Vehicles with alternative fuel Vehicles exploring remote areas The Gas Station Problem:  The Gas Station Problem Shortest Path Problem in Vehicle has limited a fuel capacity Refueling nodes in the network Edge weights expressed in fuel units Vehicle starts at with fuel units  The Gas Station Problem:  The Gas Station Problem Feasible paths are paths where the vehicle always carries a non-negative amount of fuel on the path nodes Is {all feasible paths} an empty set ? If not, what is the path that minimizes the travel distance?  Theorem:  Theorem Example:  Example Remove infeasible edges in E and vertices in V Compute all-pairs shortest path between nodes in V’ Remove infeasible edges in E’ and vertices in V’ Calculate the shortest path from s to t Solution produced in Error-Correcting Network:  Error-Correcting Network Possible Generalization to Communication Networks The Gas-Station algorithm works for transportation networks Is it applicable to communication networks? There are many similarities Vehicle  information packet Gas tank capacity  error budget Gas station  error correction node Gas consumption  packet error Error Budget:  Error Budget  M U R F L E S M A R B L E S Suppose each packet contains seven symbols, and the error-correction scheme employed in the network can correct up to (but not more than) three errors. Then the error budget is three units for a given alphabet size.   Edge model: Symmetric Channel:  Edge model: Symmetric Channel The Cascaded SC:  The Cascaded SC The ary Erasure Channel:  The ary Erasure Channel Generalized Dijkstra Algorithm:  Generalized Dijkstra Algorithm x + min( y , z ) = min ( x + y , x + z ) The Error Distribution:  The Error Distribution Edge Weight: Worst-Case Error:  Edge Weight: Worst-Case Error p = 0.10 p = 0.25 p = 0.98 p = 0.50 Routing in Error-Correcting Networks:  Routing in Error-Correcting Networks WCE x is a non-decreasing function of p The algorithm used in the Gas Station Problem can be used to find the feasible path with minimum WCE from s to t. Questions? 

Related presentations


Other presentations created by Paola

History of Physical Education
24. 04. 2008
0 views

History of Physical Education

Day 1 3a Core Banking
21. 02. 2008
0 views

Day 1 3a Core Banking

Cooper
11. 01. 2008
0 views

Cooper

lecture Mand C3 B2 for printing
11. 01. 2008
0 views

lecture Mand C3 B2 for printing

food supply
12. 01. 2008
0 views

food supply

MEES04
12. 01. 2008
0 views

MEES04

KubataSession6
14. 01. 2008
0 views

KubataSession6

History of Christianity
20. 01. 2008
0 views

History of Christianity

N2 for NEPA 2 08 07
21. 01. 2008
0 views

N2 for NEPA 2 08 07

Cepeda Impact of CAFTA
22. 01. 2008
0 views

Cepeda Impact of CAFTA

istc301space
22. 01. 2008
0 views

istc301space

Italia 2005
17. 01. 2008
0 views

Italia 2005

20051021 Einleitung
22. 01. 2008
0 views

20051021 Einleitung

handout 184756
23. 01. 2008
0 views

handout 184756

B2 Billings Kelly Spritzer
04. 02. 2008
0 views

B2 Billings Kelly Spritzer

Presentation Gujarat Final
04. 02. 2008
0 views

Presentation Gujarat Final

05
25. 01. 2008
0 views

05

mars venus
25. 01. 2008
0 views

mars venus

Instructor Ch 01
28. 01. 2008
0 views

Instructor Ch 01

UK Coaching Certificate
07. 02. 2008
0 views

UK Coaching Certificate

Adrienne Rich
07. 02. 2008
0 views

Adrienne Rich

ppt 41
14. 02. 2008
0 views

ppt 41

Jeopardy Second Review
18. 02. 2008
0 views

Jeopardy Second Review

CES JHCBML
31. 01. 2008
0 views

CES JHCBML

orcas
20. 02. 2008
0 views

orcas

Aircraft Instruments
22. 02. 2008
0 views

Aircraft Instruments

Chapter 44
15. 01. 2008
0 views

Chapter 44

unit 6
28. 02. 2008
0 views

unit 6

ElementaryElaboratio nV2
15. 01. 2008
0 views

ElementaryElaboratio nV2

Paris Travel Study
29. 02. 2008
0 views

Paris Travel Study

uFZcXFc20070911171029
14. 01. 2008
0 views

uFZcXFc20070911171029

ASApresent
16. 03. 2008
0 views

ASApresent

pwe3 9
21. 03. 2008
0 views

pwe3 9

Costikyan
17. 01. 2008
0 views

Costikyan

Chapter 13
16. 04. 2008
0 views

Chapter 13

ProfessorJinYuanpu
16. 04. 2008
0 views

ProfessorJinYuanpu

2 20080121101119
17. 04. 2008
0 views

2 20080121101119

Lecture 7ME
17. 01. 2008
0 views

Lecture 7ME

animalsUK1
18. 01. 2008
0 views

animalsUK1

Why does popcorn pop2
06. 02. 2008
0 views

Why does popcorn pop2

eecpcl
15. 02. 2008
0 views

eecpcl

compassion lifestyle education
24. 03. 2008
0 views

compassion lifestyle education

Urheiluoikeusluennot
21. 04. 2008
0 views

Urheiluoikeusluennot

seeda
13. 02. 2008
0 views

seeda

subs
07. 05. 2008
0 views

subs

chr Friis Bach slides
08. 05. 2008
0 views

chr Friis Bach slides

B08 FDP
30. 04. 2008
0 views

B08 FDP

mammela011120
02. 05. 2008
0 views

mammela011120

MC strategyannexes
07. 02. 2008
0 views

MC strategyannexes

Portugal More ThanYou Imagine
21. 01. 2008
0 views

Portugal More ThanYou Imagine

orientation4
13. 01. 2008
0 views

orientation4

14 caratteri quantitativi
11. 02. 2008
0 views

14 caratteri quantitativi

metadata 2006 first
03. 03. 2008
0 views

metadata 2006 first

TSA2005
05. 02. 2008
0 views

TSA2005

Humanistisk teoriSNE422V07TE
28. 01. 2008
0 views

Humanistisk teoriSNE422V07TE

oulubreakoutCisco
30. 01. 2008
0 views

oulubreakoutCisco

mexico usa Carly Goodwin
15. 03. 2008
0 views

mexico usa Carly Goodwin

Clyde Ogg Learning Obj 2007
15. 01. 2008
0 views

Clyde Ogg Learning Obj 2007

ee247
09. 01. 2008
0 views

ee247

RECFA Boutigny
22. 01. 2008
0 views

RECFA Boutigny