M1 gp

May 10, 2013Download as ODP, PDF1 like502 views

亮介小林

Faster?GPS?
via?the?Sparse?Fourier?Transform
Haitham?Hassanieh?Fadel?Adib?Dina?Katabi?Piotr?Indyk:?MobiCom2012
浅見?川原研究室
B4?小林亮介

目次
●
背景(GPS ?の同期について）
●
QuickSync
??従来方式
??IFFT部分
??FFT部分
●
実験
●
結論

背景
●
衛星との距離を測定（４衛星）
?　　　　　距離 =? ?到達時間 ×?光速
●
CDMA?code?の同期
CDMA?codeの遅れから到達時間を見積もる.
同期計算での電力消費が大きい

背景（GPS同期）
畳み込み積分
　　O(n^2)
フーリエ変換
　　O(nlogn)

QuickSync
●
現時点で最も速いGPS信号同期アルゴリズム
●
理論上の計算量
　(さらに、SNR ?によっては O(n)?まで可能)
●
実験結果：
実際のGPS信号で実験
従来の2.2倍の速度
O n logn

FFT?based(従来方式)
nサンプルとしたとき、
①それぞれにFFT　???　O(nlogn)
②（乗算　???　O(n)）
③IFFT　???　O(nlogn)
FFT ?と IFFT?をどちらも改良する必要がある

信号処理の基礎
時間領域でのサンプリング周波数：小
→ 周波数領域での波形周期：小
　　　??　エイリアシング発生
逆も同様

QuickSync
後半（逆フーリエ変換）部分
結果がsparse
→ 多小のエイリアシングに耐え得る
→ 入力のサンプリング数を下げてもよい
n

蚕耻颈肠办厂测苍肠(后半部分)
bucket化したのちどうする？
spike中に一つだけ解が含まれる.
→ そこだけ調べれば良い！！
●
bucketize
nコをn/pコのbucketにまとめる
●
サンプル数n/pでIFFT???? O(n/plog(n/p))
●
estimate
spike中のpコと、CDMA?code(n/pコ)
　　　　　の畳み込み積分 ??? O(n)

QuickSync
前半（フーリエ変換）部分
Input（n×p ? ?サンプル）を n/pコにbucketize
???? O(np)??
　　↓FFT
n/pコの周波数データ
↓
後半部分へ
?
n

QuickSync
bucketize & FFT → (muitiply) →　sparseIFFT
O(np?+?(n/p)log(n/p))
p = √logn のとき、O(n√logn)

実験
●
異なる2種類GPS記録を使用
??Europe?and?US
??urban?and?suburban
??clear?and?cloudy
●
2つの尺度で評価
??hardware?implementation
??software?implementation
??
MultiplicationGain =
Multiplications o f baseline
Multiplications o f QuickSync
FLOPsGain =
FLOPs o f baseline
FLOPs o f QuickSync

実験結果
QuickSync
　どの場合においても、
　　　　　QuickSyncが 2倍超の利得を得た.

結論
●
最速の同期アルゴリズム「QuickSync」
　
●
実験の結果、従来の1/2以下の計算量
●
GPSのみならず、同期作業全般にアプライ可
能
O n logn

La computación móvil se basa en los principios de los sistemas distribuidos y permite que las computadoras portátiles sean reemplazadas por medios inalámbricos y se puedan transportar a todas partes. La computación ubicua no es visible, detecta el estado de un individuo y sus necesidades, permite la escalabilidad local y oculta los desniveles de acondicionamiento, y permanece en todas partes.

Apresenta??o avalia??opedrojoao35

More Related Content

What's hot (20)

搁で颈蝉辞尘补辫（多様体学习のはなし）Kohta Ishikawa

200611material ozakiRCCSRENKEI

200730material fujitaRCCSRENKEI

120414 foss4g nagoya_presentation2Takayuki Nuimura

CMSI計算科学技術特論A (2015) 第14回量子化学計算の大規模化１Computational Materials Science Initiative

論文紹介: Fast R-CNN&Faster R-CNNTakashi Abe

Scalable Partial Least Squares Regression on Grammar-Compressed Data MatricesYasuo Tabei

DVB recording command on gstreamer.裕士常田

PARI/GPの話 @ Ph/shh/bin CTF勉強会LT__ytoku

CMSI計算科学技術特論C (2015) feram と強誘電体②Computational Materials Science Initiative

CMSI計算科学技術特論B(11) 大規模MD並列化の技術2Computational Materials Science Initiative

狠狠撸 distMITSUNARI Shigeo

LT@Chainer MeetupShunta Saito

Sortoupc

CMSI計算科学技術特論C (2015) feram と強誘電体①Computational Materials Science Initiative

Lisp meetup #29 cl-online-learningの紹介Satoshi imai

20130626 kawasaki.rb NKT77nkt77

20180427 arXivtimes 勉強会: Cascade R-CNN: Delving into High Quality Object Det...grafi_tt

20120810 eiscat yogawa_v2Iugo Net

搁で颈蝉辞尘补辫（多様体学习のはなし）Kohta Ishikawa

200611material ozakiRCCSRENKEI

200730material fujitaRCCSRENKEI

120414 foss4g nagoya_presentation2Takayuki Nuimura

CMSI計算科学技術特論A (2015) 第14回量子化学計算の大規模化１Computational Materials Science Initiative

論文紹介: Fast R-CNN&Faster R-CNNTakashi Abe

Scalable Partial Least Squares Regression on Grammar-Compressed Data MatricesYasuo Tabei

DVB recording command on gstreamer.裕士常田

PARI/GPの話 @ Ph/shh/bin CTF勉強会LT__ytoku

CMSI計算科学技術特論C (2015) feram と強誘電体②Computational Materials Science Initiative

CMSI計算科学技術特論B(11) 大規模MD並列化の技術2Computational Materials Science Initiative

狠狠撸 distMITSUNARI Shigeo

LT@Chainer MeetupShunta Saito

Sortoupc

CMSI計算科学技術特論C (2015) feram と強誘電体①Computational Materials Science Initiative

Lisp meetup #29 cl-online-learningの紹介Satoshi imai

20130626 kawasaki.rb NKT77nkt77

20180427 arXivtimes 勉強会: Cascade R-CNN: Delving into High Quality Object Det...grafi_tt

20120810 eiscat yogawa_v2Iugo Net

Viewers also liked (20)

Computacion Movil InalambricaKaterine Santander

Apresenta??o avalia??opedrojoao35

Programas de simulacionDiego Moises Tene

Telexfree: Apresenta??o do Negóciomrezende01

Apresenta??o nnexNnex Rio de Janeiro

People. nature and portraits picsHira Farooq

Faidanielalucho

2013 5-9 nuevas profesiones en internetGerardo Salvador

La jornada CEEI Elche trata sobre nuevos perfiles profesionales relacionados con Internet, como técnico de marketing y ventas todo en uno, emprendedor digital, responsable de SEO/SEM, gestor de redes sociales y comunicación, redactores SEO y bloggers, desarrollador web, experto en arquitectura, análisis web y usabilidad, experto legal en Internet y responsable de ecommerce. Gerardo Salvador fue el responsable de desarrollo de negocio en la jornada.

Cr?nicaDani Brandao

Methodology i content centered language learningLUPE AMELIA RIVERA GONZALES

Powerpointgrup11m4c2l11

Hecho en México, hecho en gf k méxico bicentenario-2010Walkiria Calva

Este documento presenta los resultados de una encuesta realizada en México sobre la difusión del Bicentenario de la Independencia por parte de empresas y marcas. Los principales hallazgos son: 1) El 40% de los mexicanos ha visto empresas hablar del Bicentenario, siendo abril y agosto los meses con mayor difusión. 2) Televisa, TV Azteca y el Gobierno Federal fueron las tres entidades con mayor difusión sobre el tema. 3) Televisa se mantuvo como la empresa que más habló del Bicentenario a lo largo de los 6 meses

Presentacion PlanificacióNguestab8516b9

Este documento describe un programa de capacitación virtual para docentes tradicionales sobre el uso de la tecnología en la ense?anza. El programa consta de cursos de 40 horas sobre temas como metodologías de ense?anza virtual, uso de recursos multimedia e internet, y entornos virtuales de aprendizaje. Los cursos serán impartidos por instructores certificados en e-learning y tendrán evaluaciones cuantitativas y cualitativas. El modelo de estudio será totalmente virtual a través de una plataforma que brindará foros, chat y videoconfer

Res0012013sepConselhos

Qumicaindustrial2 090910071755-phpapp01Daniel Arazari

La industria química transforma las materias primas en productos que mejoran la calidad de vida de las personas. Se divide en industrias de base, que elaboran productos intermedios, e industrias de transformación, que producen bienes de consumo. El proceso productivo incluye tratamientos físicos y químicos, y control de calidad. La industria química contribuye al desarrollo económico a través de la exportación de productos como celulosa, refinados de petróleo y metanol.

Aprender y ense?ar en colaboraciónTeresita Sachez Nava

Este documento describe los beneficios y procesos del aprendizaje colaborativo en entornos virtuales. Explica que el aprendizaje colaborativo crea interdependencia positiva entre estudiantes al generar debates y permitir el intercambio de información para construir conocimiento de forma conjunta. También detalla que el aprendizaje colaborativo en línea depende de la situación de aprendizaje, las características del grupo y la tecnología utilizada, y que el dise?o de actividades colaborativas debe considerar aspectos como la

Fraternidade, institui??es e democraciaAna Luiza Santana

Este artigo discute como a democracia, institui??es e fraternidade est?o ligadas e como seu funcionamento em harmonia pode gerar um sistema mais igualitário. A democracia ideal protege liberdades individuais e coletivas, mas no Brasil nem sempre é assim. Institui??es devem servir aos objetivos da sociedade, n?o só o desenvolvimento econ?mico. A fraternidade equilibra as liberdades e ajuda a formar cidad?os conscientes dos direitos de todos.

plantillaEdwin Garcia Martin

operacionalizacion de las hipotesismiguel angel

El documento explica el proceso de operacionalización de hipótesis, el cual consiste en traducir conceptos abstractos (variables) en conceptos concretos (indicadores) a través de tres niveles: 1) Las variables son propiedades abstractas de personas u objetos. 2) Las dimensiones son más específicas que las variables. 3) Los indicadores son los más específicos y permiten medir conceptos en la realidad social. El proceso facilita la elaboración de un bosquejo de trabajo e índices compuestos por varios indicadores cuantificados.

Cuestionario quinto cursocasa

Este documento contiene preguntas y respuestas sobre conceptos básicos de bases de datos, como tablas, registros, campos, claves primarias, formularios, vistas, consultas, informes y macros. Explica que una base de datos permite almacenar y manipular datos de forma ordenada, y que una tabla se compone de registros formados por campos. También describe las funciones de los diferentes tipos de vistas y asistentes para crear y modificar elementos de una base de datos.

Computacion Movil InalambricaKaterine Santander

Apresenta??o avalia??opedrojoao35

Programas de simulacionDiego Moises Tene

Telexfree: Apresenta??o do Negóciomrezende01

Apresenta??o nnexNnex Rio de Janeiro

People. nature and portraits picsHira Farooq

Faidanielalucho

2013 5-9 nuevas profesiones en internetGerardo Salvador

Cr?nicaDani Brandao

Methodology i content centered language learningLUPE AMELIA RIVERA GONZALES

Powerpointgrup11m4c2l11

Hecho en México, hecho en gf k méxico bicentenario-2010Walkiria Calva