JP2004212631A - 地図データ処理システム - Google Patents

Abstract

【課題】受信側が非常に多く存在し、かつ常に通信ネットワークに接続できる環境にあるとは限らないという状況に適した、データ配信を行う枠組みを提供する。
【解決手段】地図データベースに記憶される地図データより、群連鎖反応符号化方式に基づきＰ個以上の符号化データを生成し、該符号化データごとに生成したパケットを放送波により放送する地図データ配信手段と、前記地図データ配信手段から放送されたパケット中の任意の異なるＰ個のパケットを受信し、群連鎖反応符号化方式に基づき該Ｐ個のパケットから前記地図データを復元する情報処理手段と、を備える。
【選択図】 図１

Description

【０００１】
【発明の属する技術分野】
本発明は、自動車等に地図データを配信する場合に適した地図データ処理技術に関する。
【０００２】
【従来の技術】
データの損失を考慮したデータ配信方式としては、例えばＴＣＰのように送信側と受信側との間に１対１のコネクションを形成してデータの受信を確認する確認応答方式、対象データを複数のパケットに分割し、かかる複数のパケットを連続的にサイクリックに繰り返して送信するカルーセル方式などが知られている。
【０００３】
更に、特許文献１には、配信されるファイルに対して高度な数学的理論に基づく所定の関数を用いた演算を行うことにより所定のパケットを生成し、配信されるファイルを構成している一部のパケットが欠落した場合であっても、所定の数のパケットを受信していればファイルを復元することができる方式（以下、群連鎖反応符号化方式と呼ぶ。）が開示されている。
【０００４】
【特許文献１】特開２００１−１８９６６５号公報
【発明が解決しようとする課題】
従来のナビゲーションシステム等の地図データ利用システムでは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体により地図データが提供されるのが一般的であるが、このような構成では地図データを新たに配布したり、更新する場合に、記録媒体の購入、差し替え等の必要があり煩雑であるため、通信ネットワークを介して地図データをデータ配信する構成が検討されている。
【０００５】
しかし、確認応答方式でデータ配信を行おうとすると、受信側である自動車等の台数が非常に多いことから、送信側のサーバの負荷が大きくなり、十分に処理しきれないという問題が生じる。これに対し、カルーセル方式では、上記のようなサーバ負荷の問題は生じない一方、１つのパケットが受信できなかった場合に再びそのパケットを受信するためには全体サイクルが一巡するのを待たなければならないという問題が生じる。特に、エンジンオフやトンネル等による遮蔽の影響など、自動車等は常に通信ネットワークに接続できる環境にあるとは限らないため、１サイクルにわたって受信が継続できることを前提とするカルーセル方式によるデータ配信は、自動車等に対するデータ配信に必ずしも適しているとは言えない。
【０００６】
ここで、群連鎖反応符号化方式は、特許文献１に記載されているように、生成された複数のパケットのうちの任意の組み合せのパケットに基づいてデータを復元できるため、カルーセル方式のような問題は生じない。しかし、特許文献１は、群連鎖反応符号化方式については詳細に開示するものの、かかる方式を利用した具体的なアプリケーションについては何ら開示していない。
【０００７】
本願の発明者は、受信側が非常に多く存在し、かつ常に通信ネットワークに接続できる環境にあるとは限らないという、自動車等にデータ配信する場合に特有の状況を考察し、かかる状況に適したデータ配信方式を検討した結果、群連鎖反応符号化方式に基づくデータ配信がより好ましいと考えるに至った。
【０００８】
そこで、本発明は、群連鎖反応符号化方式を利用して自動車に対してデータ配信を行う枠組みを提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明の地図データ処理システムは、地図データベースに記憶される地図データより、群連鎖反応符号化方式に基づきＰ個以上の符号化データを生成し、該符号化データごとに生成したパケットを放送波により放送する地図データ配信手段と、前記地図データ配信手段から放送されたパケット中の任意の異なるＰ個のパケットを受信し、群連鎖反応符号化方式に基づき該Ｐ個のパケットから前記地図データを復元する情報処理手段と、を備えることを特徴とする。
【００１０】
好適には、前記情報処理手段は、前記地図データを利用してナビゲーション機能を提供することを特徴とする。
【００１１】
また好適には、前記情報処理手段は、走行体に実装された状態で動作することを特徴とする。
【００１２】
また好適には、更に、前記符号化データごとに生成したパケットの一部又は全部を所定の通信方式により送信する通信手段を備え、前記情報端末は、前記放送に基づきＳ個（Ｐ＞Ｓ）のパケットを受信し、前記通信手段からの送信に基づき前記Ｓ個のパケットと異なるＴ個（Ｓ＋Ｔ＝Ｐ）のパケットを受信し、前記Ｓ個のパケット及び前記Ｔ個のパケットから前記地図データを復元することを特徴とする。
【００１３】
本発明の地図データ処理システムは、地図データ配信手段から放送波により放送される符号化データを受信し、該符号化データに基づき地図データを復元する地図データ処理システムであって、前記符号化データは、地図データを対象として群連鎖反応符号化方式に基づき生成された符号化データであり、地図データ処理システムは、前記地図データ配信手段から放送されたＰ個以上の符号化データのうち任意の異なるＰ個の符号化データから、群連鎖反応符号化方式に基づき前記地図データを復元することを特徴とする。
【００１４】
本発明の地図データ処理方法は、地図データベースに記憶される地図データより、群連鎖反応符号化方式に基づきＰ個以上の符号化データを生成して、該符号化データごとにパケットを生成するパケット生成工程と、前記パケットを放送波により放送する放送工程と、放送された前記パケット中の任意の異なるＰ個のパケットを受信する工程と、受信した前記Ｐ個のパケットから群連鎖反応符号化方式に基づき前記地図データを復元する工程と、を備えることを特徴とする。
【００１５】
本明細書において、物の発明は方法の発明として把握することができ、方法の発明は物の発明として把握することができる。また、上記発明は、コンピュータに所定の機能を実現させるプログラムを記録した記録媒体またはプログラムそのものとしても成立する。なお、記録媒体は、例えば、光ディスク、磁気ディスク、半導体メモリなどの各種の記憶媒体を含む。また、プログラムは、前記記録媒体を通じて又はネットワークを介して、コンピュータにインストールまたはロードすることができる。
【００１６】
また、本明細書において、手段とは、単に物理的手段を意味するものではなく、その手段が有する機能をソフトウェアによって実現する場合やハードウェア回路によって実現する場合も含む。また、１つの手段が有する機能が２つ以上の物理的手段により実現されても、２つ以上の手段の機能が１つの物理的手段により実現されても良い。
【００１７】
さらにまた、本明細書における手段は、ハードウェア、ソフトウェアまたはハードウェアおよびソフトウェアの組み合わせにより実現可能である。ハードウェアおよびソフトウェアの組み合わせによる実行は、例えば、所定のプログラムを有するコンピュータ・システムにおける実行が該当する。そして、１つの手段が有する機能が２つ以上のハードウェア、ソフトウェアまたはハードウェアおよびソフトウェアの組み合わせにより実現されても、２つ以上の手段の機能が１つのハードウェア、ソフトウェアまたはハードウェアおよびソフトウェアの組み合わせにより実現されても良い。
【００１８】
【発明の実施の形態】
（群連鎖反応符号化方式の説明）
最初に、群連鎖反応符号化方式について説明する。
【００１９】
群連鎖反応符号化方式は、入力ファイルのデータを表す入力記号に基づき、出力記号（群連鎖反応符号化方式に基づく符号化データ）を生成する符号化方式である。概念的には、符号部において、入力記号をパラメータとする冗長な連立方程式（パラメータ数Ｋよりも式の数の方が多い連立方程式）を作り、該連立方程式を出力記号として出力すると考えることができる。この場合、復号部では、原則として任意のＰ個（Ｐ≧Ｋ）の方程式があれば解（入力記号）を求める、すなわち入力ファイルのデータを復元することが可能となる。
【００２０】
以下、特許文献１を部分的に引用して、更に説明する。
【００２１】
群連鎖反応符号化を用いて、出力記号の群が必要に応じて入力ファイルから送信者によって生成される。出力記号の各群は、出力記号の他の群がどのように生成されるかにかかわらず生成され得る。どの時点においても、送信者は、出力記号の群生成工程を停止し得る。送信者が出力記号の群生成工程をいつ停止または再開するかについては、制約を必要としない。一旦生成された後、出力記号のこれらの群は、パケット内に配置され、送信先へ送信される。この場合、各パケットは、出力記号の群を１つ以上含む。群連鎖反応符号化の具体的な例では、各群は、１つの出力記号を含む。
【００２２】
用語「ファイル」は、１つ以上のソースに格納され、１つ以上の送信先へ１単位として送達される任意のデータのことである。したがって、ファイルサーバまたはコンピュータ記憶装置からのドキュメント、イメージ、およびファイルはすべて、送達され得る「ファイル」の例である。ファイルは、既知のサイズを有するか（ハードディスク上に格納された１メガバイトのイメージなど）、または未知のサイズを有する（ストリーミングソースの出力から取り出されるファイルなど）。いずれの場合も、ファイルは入力記号のシーケンスであり、各入力記号はファイル内の位置および値を有する。
【００２３】
送信は、ファイルを送達するためにデータを１以上の送信者から１以上の受信者にチャネルを介して送信する処理のことである。１送信者が完全なチャネルによって任意数の受信者に接続される場合、すべてのデータが正しく受信されるので受信されたデータが入力ファイルの正確なコピーであり得る。ここで、大半の現実のチャネルの場合のようにチャネルが完全でないと仮定するか、またはいくつかシステムの場合のように１より多い送信者からデータが送信されると仮定するか、またはいくつかシステムの場合のように送信されるデータの一部が途中で故意に脱落されると仮定する。多くのチャネルの欠点のうち、ここで関心のある２つの欠点は、データイレーズおよびデータ不完全性（データイレーズの特殊な場合として処理され得る）である。データイレーズが生じるのは、チャネルがデータを損失または脱落させる場合である。データ不完全性が生じるのは、データをうちのいくつかが受信者を通り過ぎてしまうまで受信者がデータの受信を開始しないか、受信者が送信終了前にデータの受信を停止するか、または受信者がデータ受信の停止および再開を断続的に行う場合である。
【００２４】
データ不完全性の例として、移動衛星送信者が、入力ファイルを表すデータを送信し、受信者が範囲に入る前に送信を開始する。受信者が一旦範囲に入ると、衛星が範囲を出るまでデータが受信され得る。この場合、受信者は、衛星放送受信アンテナの向きを変更して（この間はデータを受信しない）、範囲内に入った別の衛星によって送信されている同じ入力ファイルについてのデータの受信を開始し得る。この記載を読むことにより明らかなように、データ不完全性は、データイレーズの特殊な場合である。なぜなら、受信者は、あたかも受信者が常に範囲内に存在しているが、チャネルは受信者がデータ受信を開始する時点までのすべてのデータを損失するかのように、データ不完全性を処理し得る（および受信者は同じ問題を有する）。また、通信システム設計において周知のように、検出可能な誤りは、単に検出可能な誤りを有するデータブロックまたは記号のすべてを脱落させることによってイレーズと等価になり得る。
【００２５】
別の例としては、ルータは、そのバッファがフルまたはフルに近い（混雑状態）場合に故意にパケットを脱落させ、かつ競合するパケットに対して公平であるようにおよび／または強制的に速度制限をするように故意にパケットを脱落させる。
【００２６】
いくつかの通信システムにおいて、受信者は、複数の送信者または複数の接続を有する１送信者によって生成されるデータを受信する。例えば、ダウンロードの速度を上げるために、受信者は、同時に１より多い送信者に接続して同じファイルに関するデータを送信する。別の例として、マルチキャスト送信において、複数のマルチキャストデータストリームは、受信者がこれらデータストリームのその１つ以上に接続できるよう送信され、そのストリームが送信者に接続されるチャネルの帯域に総送信速度を整合させる。すべてのそのような場合において重要なのは、たとえ送信速度が異なるストリーム間で大きく異なる場合であっても、かつ任意の損失パターンがある場合でも、すべての送信データが受信者に対して独立に使用されること、すなわち、複数のソースデータがストリーム間で冗長でないことである。
【００２７】
一般に、送信とは、送信者から受信者へ送信者と受信者とを接続するチャネルを介してデータを移動する行為である。そのチャネルは、チャネルがデータを取得した際にチャネルがそのデータを送信者から受信者へ移動させる実時間チャネルであり得る。あるいは、チャネルは、送信者から受信者への送信中にデータの一部またはすべてを格納する記憶チャネルでもよい。後者の例は、ディスク記憶装置または他の記憶装置である。この例では、データを生成するプログラムまたはデバイスは、データを記憶装置に送信する送信者として考えられ得る。受信者は、記憶装置からデータを読み出すプログラムまたはデバイスである。送信者がデータを記憶装置へ書き込むために使用する機構、記憶装置自体、および受信者が記憶装置からデータを読み出すための機構が、集合的にチャネルを形成する。これらの機構または記憶装置がデータを損失する可能性がある場合、そのような損失をチャネル中のデータイレーズとして処理し得る。
【００２８】
送信者および受信者がデータイレーズチャネルによって分離される場合、入力ファイルの正確なコピーを送信するのではなくて、その代わりにイレーズの回復を補助する入力ファイルから生成されたデータを送信するのが好ましい。エンコーダとは、そのようなタスクを処理する回路、デバイス、モジュール、または符号セグメントである。エンコーダの動作の見る１つの方法は、エンコーダが入力記号から出力記号の群を生成することであり、ここで入力記号値のシーケンスが入力ファイルを表す。したがって、各入力記号は、入力ファイル内の位置、および値を有する。デコーダとは、受信者によって受信された出力記号の群から入力記号を再構築する回路、デバイス、モジュール、または符号セグメントである。
【００２９】
群連鎖反応符号化は、任意の特定のタイプの入力記号に限定されないが、入力記号のタイプはアプリケーションによって決定されることが多い。一般に、入力記号に対する値は、２^Ｍ個の記号（ここでＭは正の整数）のアルファベットから選択される。そのような場合、入力記号は、入力ファイルからのＭビットのデータシーケンスによって表現され得る。Ｍの値は、アプリケーションの使用、チャネル、および群の最大サイズに基づいて決定されることが多い。例えば、パケットベースインターネットチャネルに対しては、１０２４バイトのサイズのペイロードを有するパケットが適切であり得る（１バイトは８ビット）。この例において、各パケットが出力記号の１群および８バイトの補助情報を含むと仮定し、かつすべての群が４個の出力記号を含むと仮定すると、入力記号サイズのＭは、（１０２４−８）／４、すなわち２５４バイトが適切であり得る。別の例として、ＭＰＥＧパケット規格を使用するいくつかの衛星システムがある。この場合、各パケットのペイロードは１８８バイトを含む。この例において、各パケットは出力記号の１群および４バイトの補助情報を含むと仮定し、かつすべての群が２個の出力記号を有すると仮定すると、記号サイズのＭは、（１８８−４）／２、すなわち９７バイトが適切であり得る。群連鎖反応符号化を使用する汎用通信システムにおいて、入力記号サイズ（すなわち、Ｍ、入力記号によって符号化されたビット数）などのアプリケーション特定パラメータは、アプリケーションによって設定された変数である。
【００３０】
出力記号の各群は、その群における出力記号の各々に対する値を有する。以下を考慮する１つの好ましい実施形態において、出力記号の各群は、「キー」と呼ばれる識別子を有する。好ましくは、出力記号の各群のキーは、受信者によって容易に決定され、受信者が出力記号のある群を出力記号の別の群と区別できるようにする。好ましくは、出力記号の群のキーは、出力記号の他のすべての群のキーと異なる。また好ましくは、受信者が受信された出力記号の群のキーを決定するためには、送信中に含まれるデータは可能な限り少ない方がよい。
【００３１】
キーイングの簡単な形態では、エンコーダによって生成された出力記号の連続した群に対するキーのシーケンスは、連続した整数のシーケンスである。この場合、各キーは、「シーケンス番号」と呼ばれる。各送信パケット中の出力記号値の１群がある場合、シーケンス番号がパケット中に含まれ得る。一般にシーケンス番号が少数のバイト（例えば、４バイト）に収まるので、いくつかのシステムにおいては、出力記号値の群とともにシーケンス番号を含むことは経済的である。例えば、各１０２４バイトのＵＤＰインターネットパケットを使用して、シーケンス番号用に各パケット内に４バイトを割当ててもわずかに０．４％の負担がかかるだけである。
【００３２】
他のシステムでは、１より多くのデータからキーを生成するのが好ましい。例えば、１以上の送信者からの同じ入力ファイルに基づいて生成された１より多くのデータストリームを受信する受信者を含むシステムを考える。ここで、送信データはパケットのストリームであり、各パケットは、出力記号の１群を含む。すべてのそのようなストリームが、キーと同じシーケンス番号のセットを使用する場合、受信者は、同じシーケンス番号を有する出力記号の群を受信する可能性がある。同じキーを有するか、または同じシーケンス番号を有する場合の出力記号の群は、入力ファイルについて同一の情報を含むので、受信者は、無駄な重複データを受信する。したがって、そのような場合、キーがシーケンス番号と対になった固有のストリーム識別子を含むことが好ましい。
【００３３】
例えば、ＵＤＰインターネットパケットの１ストリームに対して、データストリームの固有の識別子は、送信者のＩＰアドレス、および送信者がパケットを送信するために使用しているポート数を含み得る。送信者のＩＰアドレスおよびストリームのポート数は、各ＵＤＰパケットのヘッダの一部であるので、キーのこれらの部分が受信者に確実に利用され得るように各パケット中に必要なさらなるスペースはない。送信者は、単にシーケンス番号を各パケットに対応の出力記号の群とともに挿入することのみを必要とし、受信者は、シーケンス番号およびパケットヘッダから受信された出力記号の１群のキー全体を再生成し得る。別の例として、ＩＰマルチキャストパケットの１ストリームに対して、データストリームの固有の識別子は、ＩＰマルチキャストアドレスを含み得る。ＩＰマルチキャストアドレスは各ＩＰマルチキャストパケットのヘッダの一部であるので、ＵＤＰパケットについての上記説明は、この場合についても同様に適用される。
【００３４】
出力記号の群の位置によるキーイングは、それが可能な場合は好ましい。位置キーイングは、ＣＤ−ＲＯＭ（コンパクトディスク読み取り専用メモリ）などの記憶装置から出力記号の群を読み出すために十分機能し得る。ここで、出力記号の１群のキーは、ＣＤ−ＲＯＭ上の位置（すなわち、トラック、プラスセクタ、セクタ内のプラス位置など）である。位置キーイングはまた、ＡＴＭ（非同期転送モード）システムなどの回路ベース送信システムのために十分機能し得る。ここで、整列したデータセルは、厳しいタイミング制約下で送信される。この形態のキーイングを使用すると、受信者は、出力記号の１群のキーを、そのキーを明確に送信するのに必要なスペースを有することなく、再生成し得る。当然、位置キーイングは、そのような位置情報が利用でき確実であることを必要とする。
【００３５】
位置によるキーイングはまた、他のキーイング方法と組み合わせ得る。例えば、各パケットが出力記号の１より多くの群を含むパケット送信システムを考える。この場合、出力記号の群のキーは、固有のストリーム識別子、シーケンス番号、および出力記号の群のパケット内の位置から構築され得る。データイレーズは一般に全パケットの損失を生じるので、受信者は一般にパケットを全部受信する。この場合、受信者は、パケットのヘッダ（固有のストリーム識別子を含む）、パケット中のシーケンス番号、および出力記号の群のパケット内の位置を再生成し得る。
【００３６】
いくつかのシステムにおいて好ましいキーイングの別の形態は、ランダムキーイングである。これらのシステムにおいては、乱数（疑似乱数）が、生成され、出力記号の各群に対するキーの少なくとも１部として使用され、および出力記号の群とともに明確に送信される。異なる物理的位置で異なる送信者によって生成されるキーに対してさえ（可能なキーの範囲が十分大きいと仮定する）、ランダムキーイングの１つの性質は、同じ値を有するキーの割合が小さい可能性がある。この形態のキーイングは、インプリメンテーションが簡単であるため、いくつかのシステムにおいては他の形態よりも利点を有し得る。
【００３７】
上記のように、群連鎖反応符号化が有用であるのは、データイレーズの可能性があるか、または受信者が、送信が開始および終了するちょうどその時点で受信を開始および終了しない場合である。後者の条件は、本明細書中で「データ不完全性」と呼ばれる。これらの条件は、群連鎖反応符号化が使用される場合、通信プロセスに悪影響を与えない。なぜなら、受信される群連鎖反応符号化が、情報追加型であるように、極めて独立しているからである。出力記号の群のほとんどの任意集合が十分に独立しているので、大部分が情報追加型である（これは、本明細書中に記載の群連鎖反応符号化システムに対する場合である）ならば、任意の適切な数のパケットを使用して、入力ファイルを回復し得る。１００パケットがデータイレーズを起こすノイズの発生によって損失する場合、その発生の後でさらに１００パケットを取り上げてイレーズされたパケットの損失を置き換え得る。送信器が送信を開始した際に受信器が送信器に同調できず何千のパケットが損失した場合、受信器は、他の送信期間から（あるいは、別の送信器からの場合もある）その何千のパケットを取り上げる。群連鎖反応符号化を使用すると、受信者は、任意の特定のパケットのセットを取り上げることに制約されず、従って１送信器からいくつかのパケット受信し、別の送信器に切り換え、いくつかのパケットを損失し、所定の送信の開始または終了を逸しても、なお入力ファイルを回復し得る。受信器−送信器調整のない送信に接続および切断する機能は、通信プロセスを大きく簡略化する。
【００３８】
群連鎖反応符号化を使用してファイルを送信するステップは、入力ファイルから入力記号を生成、形成、または抽出し、その入力記号を１以上の出力記号の群に符号化するステップ（ここで、出力記号の各群は、出力記号のすべての他の群とは独立なキーに基づいて生成される）、および出力記号の群を１以上の受信者にチャネルを介して送信するステップを含む。群連鎖反応符号化を使用する入力ファイルの１コピーを受信（および再構築）するステップは、１以上のデータストリームから出力記号の群のあるセットまたはサブセットを受信するステップ、および受信された出力記号の群の値およびキーから入力記号を復号化するステップを含む。
【００３９】
エンコーダは、入力ファイルのデータおよびキーを使用して、出力記号の１群を生成する。ここで、入力ファイルは、入力アルファベットからそれぞれ選択される順列の複数の入力記号であり、キーは、キーアルファベットから選択され、群サイズは、正の整数として選択され、各出力記号は、出力アルファベットから選択される。キーＩを有する出力記号の１群は、生成されるべき出力記号の群の群サイズＧ（Ｉ）を決定するステップ（ここで、群サイズＧは、複数のキー上の少なくとも２つの値の間で変化し得る正の整数である）、生成されるべき出力記号の群の重みＷ（Ｉ）を決定するステップ（ここで、重みＷは、複数のキー上の少なくとも２つの値の間で変化する正の整数である）、Ｉの関数にしたがって、出力記号の群に関連付けられるＷ（Ｉ）個の入力記号を選択するステップ、および選択されたＷ（Ｉ）個の入力記号の所定の値関数Ｆ（Ｉ）からＧ（Ｉ）個の出力記号値の群Ｂ（Ｉ）＝Ｂ＿１（Ｉ），．．．，Ｂ＿Ｇ（Ｉ）（Ｉ）を生成するステップによって生成される。エンコーダは、１回以上呼び出され得、各回別のキーを用い、各回出力記号の１群を生成する。出力記号の群は、一般に互いに独立であり、無限の数（Ｉの解像度に従う）が、必要ならば生成され得る。
【００４０】
デコーダは、出力記号の１以上の群の値および可能ならすでに回復された他の入力記号の値についての情報から入力記号を回復し得る。したがって、デコーダは、出力記号のいくつかの群からいくつかの入力記号を回復し得る。これにより、デコーダは、その復号された入力記号およびすでに受信された出力記号の群などからの他の入力記号を復号し得、したがってこれにより、ファイルの入力記号の回復の「連鎖反応」が受信者側で再構築される。
【００４１】
（第１実施形態）
次に、本発明の実施の一形態を説明する。図１はこの発明の実施の形態１による地図データ処理システムを示す構成図である。図に示すように、地図データ処理システムは、地図データ配信システム１０と、複数の情報処理装置２０とを含んで構成される。
【００４２】
地図データ配信システム１０は、地図データを記憶する地図データベース１１、地図データより群連鎖反応符号化方式に基づき複数のパケットを生成するパケット生成手段１２、各パケットを放送波（衛星放送波、地上放送波のいずれであってもよい）により放送する放送手段１３を含んで構成されている。
【００４３】
情報処理装置２０は、地図データ配信システム１０から放送されたパケットを受信し、該パケットから群連鎖反応符号化方式に基づき地図データを復元する受信／復元手段２１、地図データ（復元された地図データ又は／及び記憶媒体等により提供される地図データ）を記憶する地図データ記憶手段２２、地図データを利用してナビゲーション機能を提供するナビゲーション手段２３を含んで構成されている。情報処理装置２０は、図に示すように原則として自動車等の走行体に実装されて使用される。
【００４４】
地図データベース１１及び地図データ記憶手段２２は、例えば所定エリアごとに、該エリアの識別番号、該エリアに該当する部分地図データ（地図画像データ、道路等のネットワーク（トポロジー）情報、ＰＯＩ（ポイントオブインタレスト）情報など）、該部分地図データのバージョン番号などを対応づけて記憶している。地図データベース１１及び地図データ記憶手段２２は、通常のハードディスクを用いて構成できるほか、地図データが記録される記録媒体及びその読み出し／書き込み部等を備える構成、又はそれらの組み合わせとしてもよい。
【００４５】
ナビゲーション手段２３は、ユーザからの操作を受け付ける入力ＩＦ部、地図データを表示するためのディスプレイ、ユーザ操作に基づいて経路検索等を実行し、地図データ記憶手段２２を参照して必要な地図データを読み出し、所定の形態でディスプレイに表示する制御部など、通常のナビゲーションシステムと同様の構成・機能を備えている。
【００４６】
パケット生成手段１２、放送手段１３、受信／復元手段２１については、以下の動作説明において併せて説明する。なお、各ステップは処理内容に矛盾を生じない範囲で任意に順番を変更して又は並列に実行することができる。
【００４７】
（地図データ配信システム１０の動作：図２、図３）
パケット生成手段１２は、放送対象とするエリアを選択し、地図データベース１１を参照して前記選択したエリアに対応する地図データを読み出す（Ｓ１００）。エリアの選択方法としては、例えば地図データが更新されたエリアを選択する、地図データ配信システム１０の所在地に関連したエリアを選択する、所定の順番でエリアを選択する、などが考えられる。
【００４８】
パケット生成手段１２は、前記読み出した地図データについて、群連鎖反応符号化方式に基づいて復元する場合に必要な符号化データの数Ｐ（以下、「復元必要データ数Ｐ」と呼ぶ。）を決定する（Ｓ１０１）。復元必要データ数Ｐは、例えば次のようにして決定することができる。１）入力記号数Ｋを求める（地図データサイズをＸ、符号化データのサイズをＹとした場合、Ｋ＝Ｘ／Ｙ）。２）入力記号数ＫをＫ以上の素数値Ｋ’に変更する。３）Ｋ’に所定量の冗長量を付加した値をＰとする。この冗長性は出コードを確実に行うために必要なものであり、例えばＰ＝Ｋ’＋５×ＳＱＲ（Ｋ’）とすることができる。ここで、冗長率をＰ／Ｋ’と定義すると、Ｋ（Ｋ’）が大きいほど冗長率は小さくて済むことになる。例えばＫ’＝１００００の場合、Ｐ＝１．０５×Ｋ’と同等である。
【００４９】
次に、パケット生成手段１２は、前記読み出した地図データについて、群連鎖反応符号化方式に基づき符号化データを生成する（Ｓ１０２）（図４参照）。このとき、前記読み出した地図データについて既に生成した符号化データがある場合、かかる生成済みの符号化データとは異なるように、符号化データを生成する必要がある。
【００５０】
次に、パケット生成手段１２は、前記生成した符号化データについてパケットを生成する（Ｓ１０３）。パケットは、例えば図４に示すように、符号化データにエリア識別情報、地図データのバージョン情報、地図データサイズＸ（又は、復元必要データ数Ｐ）を付加して構成することが考えられる。
【００５１】
次に、放送手段１３は、パケット生成手段１２が生成したパケットについて、放送波により放送する（Ｓ１０４）。放送手段１３の構成は原則として従来の放送装置と同様に構成することができる。
【００５２】
ここで、群連鎖反応符号化方式によれば、Ｐ個以上のパケット中の任意の異なるＰ個のパケットに基づき地図データを復元することが可能であるため、パケット生成手段１２において生成すべきパケット数Ｎ（符号化データ数Ｎ）は、Ｎ≧Ｐの関係を満たしてさえいれば、どのように定めてもよい。
【００５３】
図２はＮを不定値とした場合のフローチャートの例であり、図３はＮとして具体的な値を定めた場合のフローチャートの例である。
【００５４】
図２に示すフローチャートの場合、パケット生成手段１２は、前記読み出した地図データについて生成したパケット数（符号化データの数）がＰ個以上となっているかどうかを判断し（Ｓ１０５）、Ｐ個以上となっていない場合はＳ１０２に戻る。一方、Ｐ個以上となっている場合でも、前記読み出した地図データについて処理を続ける間は、Ｓ１０２に戻り符号化データを生成する（Ｓ１０６）。
【００５５】
図３に示すフローチャートの場合、パケット生成手段１２は、パケットをＮ個生成した時点で前記読み出した地図データについてパケット生成を中止する（Ｓ１０５’）。そして、放送手段１３は、前記読み出した地図データについて処理を続ける間、パケット生成手段１２が生成したＮ個のパケットを繰り返し放送する（Ｓ１０６’、Ｓ１０７’）。
【００５６】
なお、Ｎ個のパケットを繰り返し放送する場合、各パケットの取り扱いが同等である必要は必ずしもなく、例えば各パケットの放送割合（単位時間あたりの放送回数）が異なっていてもよい。ただし、受信側において異なるＰ個のパケットを効率よく受信できるように、Ｎ個のパケットを１セットとして、該セットを周期的に放送することが望ましい。
【００５７】
（受信／復元手段２１の動作：図５）
受信／復元手段２１は、地図データ配信システム１０の放送手段１３により放送されたパケットを受信する（Ｓ２００）。
【００５８】
受信／復元手段２１は、受信したパケットから、エリア識別情報、地図データバージョン情報を抽出し、これらの情報に基づき、受信したパケットに含まれる符号化データが当該情報処理装置２０において取得すべき地図データのものであるかどうかを判断する（Ｓ２０１）。判断方法としては、例えば、地図データ記憶手段２２に記憶されていないエリアの地図データに関するものであった場合に取得すべきと判断する、地図データ記憶手段２２に記憶されている地図データより新しいバージョンの地図データに関するものであった場合に取得すべきと判断する、などが考えられる。
【００５９】
受信／復元手段２１は、取得すべきでないと判断した場合は受信したパケットを破棄し（Ｓ２０２）、次のパケットの処理に移る（Ｓ２１０）。
【００６０】
一方、取得すべきと判断した場合、エリア識別情報及び地図データバージョン情報に対応づけて、受信したパケットに含まれる符号化データを記憶する（Ｓ２０３）。
【００６１】
このとき、受信／復元手段２１は、該符号化データがエリア識別情報及び地図データバージョン情報に関して記憶した１つめの符号化データであるかどうかを判断し（Ｓ２０４）、１つめの場合は、エリア識別情報及び地図データバージョン情報に対応する受信パケット数に１をセットするとともに、受信したパケットより地図データサイズＸ（又は、復元必要データ数Ｐ）を抽出し、これをエリア識別情報及び地図データバージョン情報に対応づけて記憶する（Ｓ２０５）。一方、１つめでない場合は、対応する受信パケット数に１を加算する（Ｓ２０６）。
【００６２】
次に、受信／復元手段２２は、エリア識別情報及び地図データバージョン情報ごとに、受信パケット数が復元必要データ数Ｐに達したかどうかを判断する（Ｓ２０７）。なお、Ｓ２０５において地図データサイズＸを抽出し記憶している場合は、Ｓ１０１において説明した方法と同様の方法により地図データサイズＸに基づき復元必要データ数Ｐを決定し、これに基づき判断すればよい。
【００６３】
受信／復元手段２２は、達していないと判断した場合、次のパケットの処理に移る（Ｓ２１０）。
【００６４】
一方、達していると判断した場合は、群連鎖反応符号化方式に基づいてＰ個のパケットに含まれる符号化データから地図データを復元する（Ｓ２０８）。なお、群連鎖反応符号化方式に基づく復元方法は特許文献１に詳細に開示されているため、当業者であれば該文献を参照することにより受信／復元手段２１における復元処理を構成することが可能である。したがって、ここでは群連鎖反応符号化方式に基づく復元方法についての詳しい説明は避ける。
【００６５】
この場合、受信／復元手段２１は、地図データ記憶手段２２を参照し、エリア識別情報及び地図データバージョン情報に対応づけて、復元した地図データを登録又は更新し（Ｓ２０９）、次のパケットの処理に移る（Ｓ２１０）。
【００６６】
図６に示す例を用いて情報処理装置２０の動作を説明する。この例では、Ｐ＝４であり、図に示す番号順にパケットが放送されているものとする。そして、受信／復元手段２１は、番号１、２のパケットについては受信できたが（図６（ａ）、（ｂ））、番号３のパケットについては電波状態が悪く受信することができなかったものとする（図６（ｃ））。この場合、次の番号４のパケットに続いて（図６（ｄ））、番号５のパケットを受信した段階で（図６（ｅ））、異なる４個のパケット（番号１、２、４、５）が揃うため、受信／復元手段２１は、受信できなかった番号３のパケットが再び放送されるのを待つことなく、番号１、２、４、５のパケットに基づいて地図データの復元処理を実行することができる。
【００６７】
このように本実施形態では、地図データ配信システム１０（放送手段１３）において放送波により地図データに関する符号化データを放送し、自動車等に実装される情報処理装置２０（受信／復元手段２１）において放送された符号化データを受信して地図データを復元し、これを記憶してナビゲーション機能に利用する構成としたので、記録媒体を介して地図データを配布する従来方法に比べて、効率よく新たな地図データや更新された地図データを配布することが可能となる。また、放送波に基づいて放送／受信する構成としているため、確認応答方式のように受信側の台数に依存して配信側システムの負荷が増大してしまうことを回避することができる。
【００６８】
更に、群連鎖反応符号化方式に基づき、生成されたＰ個以上のパケット中の任意の異なるＰ個のパケットに基づいて地図データを復元することができるため、受信／復元手段２１が所定のパケットを受信できなかった場合でも、カルーセル方式のように受信できなかったパケットが再び放送されるまで待つ必要はなく、タイムリーに地図データを復元して利用することが可能となる。そのため、例えばエンジンオフの状態や、トンネルの内部など放送波が届かない環境にある場合など、自動車等に特有の状況、すなわち受信／復元手段２１が常に継続的にパケットを受信できるとは限らないという状況においても、効率よく地図データを配信する枠組みを提供することができる。
【００６９】
（変形例）
本発明は、上記実施形態に限定されることなく種々に変形して適用することが可能である。例えば、生成されたＰ個以上のパケット中の任意の異なるＰ個のパケットに基づいて地図データを復元することができる方式であれば、群連鎖反応符号化方式以外の方式、例えばリードソロモン符号化方式やトルネード符号化方式など、他の符号化方式を採用する構成としてもよい。
【００７０】
また例えば、地図データ配信システム１０が、地図データベース１１、パケット生成手段１２、放送手段１３のうち、少なくともいずれかについて複数備える構成としてもよい。この場合、放送手段１３によって放送する地図データを変える構成としてもよく、例えば放送手段１３等が設置されているエリア又はその近隣エリアの地図データを放送する構成などを考えることができる。
【００７１】
また例えば、放送手段１３において複数の周波数（チャンネル）を使用し、チャンネルごとに異なる地図データを放送する構成としてもよい。この場合、情報処理装置２０において、必要に応じて受信チャンネルを自動的に切り替えることで、自動車が所在するエリアの地図データや、ナビゲーション手段２３により設定された目的地までの経路上の地図データなどを自動的に選択して受信する構成とすることができる。
【００７２】
また例えば、情報処理装置２０において、ユーザからの入力に基づいて、放送を受信してパケットを取得するかどうか、地図データを復元するかどうか（地図データ記憶手段２２の記憶内容を更新するかどうか）などを判断する構成としてもよい。
【００７３】
また例えば、上記実施形態では、放送波により放送する構成のみ説明しているが、本発明は必ずしもこのような構成に限られず、放送波による放送と、放送波による放送とは異なる通信方式（例えば、ＩＥＥＥ ８０２．１１ｂの無線ＬＡＮ方式など）とを組み合せて、地図データを配信する構成とすることもできる。例えば、図７に示すように、ガソリンスタンド等に所定の無線ＬＡＮ方式に基づく通信手段を設置し、該通信手段より、パケット生成手段１２（放送手段１３にパケットを供給するパケット生成手段と必ずしも同一である必要はない）が生成したＮ個のパケットの一部又は全部を送信するように構成する。また、情報処理装置２０に前記通信手段と通信可能な構成を設けておく。この場合、情報処理装置２０では、走行中に放送手段１３からの放送を受信してＳ個のパケットを取得する一方、ガソリンスタンド等に停車中に前記通信手段より前記Ｓ個のパケットと異なる残りのＴ個（Ｔ＝Ｐ−Ｓ）のパケットについて高速に受信することが可能となり、放送波と無線ＬＡＮ方式とを組み合せて効率よくパケットを取得することが可能となる。
【００７４】
また例えば、上記実施形態では、図５に示すフローチャートに基づきシーケンシャルな処理として受信／復元手段２１の動作を説明しているが、本発明は必ずしもこのような構成に限られず、受信工程（Ｓ２００）、記憶工程（Ｓ２０１〜Ｓ２０６）、復元工程（Ｓ２０７〜Ｓ２０９）についてそれぞれ並列に実行する構成とすることもできる。
【００７５】
また例えば、上記実施形態では、復元必要データ数Ｐと符号化データを１つのパケットに含めて放送する構成について説明しているが、本発明は必ずしもこのような構成に限られず、符号化データとは別のパケットを用いて復元必要データ数Ｐを放送する構成としてもよい。この場合、復元必要データ数Ｐを含むパケットの放送チャンネルは、符号化データを含むパケットの放送チャンネルと必ずしも同一である必要はない。更に、復元必要データ数Ｐを予め定めることができる場合は、情報処理装置２０にデフォルトとして復元必要データ数Ｐを記憶させておく構成や、復元必要データ数Ｐを記憶する記憶媒体等を配布して情報処理装置２０の使用者に通知する構成などを考えることもできる。
【００７６】
また例えば、上記実施形態では、自動車に情報端末を実装する構成を例として説明しているが、受信側が非常に多く存在し、かつ常に通信ネットワークに接続できる環境にあるとは限らないという状況であれば、自動車以外のもの（例えば、電車や航空機等の走行体、携帯電話やＰＤＡ等の携帯端末、学校等の固定施設など）に情報端末を実装又は設置して使用したり、情報端末単体で使用する場合においても、本発明の効果を得ることができる。
【００７７】
【発明の効果】
本発明によれば、群連鎖反応符号化方式を利用してパケットを生成／復元するとともに、放送波を利用して自動車にパケットを配信する構成を採用しているため、自動車等にデータ配信する場合に適した枠組みを提供することができる。
【００７８】
【図面の簡単な説明】
【図１】本発明の第１の実施形態である地図データ処理システムの全体構成を示すブロック図である。
【図２】地図データ配信システム１０の動作例を示すフローチャートである。
【図３】地図データ配信システム１０の動作例を示すフローチャートである。
【図４】地図データ配信システム１０における符号化データ及びパケットの生成工程を説明するための図である。
【図５】受信／復元手段２１の動作を示すフローチャートである。
【図６】受信／復元手段２１の動作を説明するための図である。
【図７】第１の実施形態の変形例を説明するための図である。
【符号の説明】
１０ 地図データ配信システム
１１ 地図データベース
１２ パケット生成手段
１３ 放送手段
２０ 情報処理装置
２１ 受信／復元手段
２２ 地図データ記憶手段
２３ ナビゲーション手段

Claims (6)

1. 地図データベースに記憶される地図データより、群連鎖反応符号化方式に基づきＰ個以上の符号化データを生成し、該符号化データごとに生成したパケットを放送波により放送する地図データ配信手段と、
   前記地図データ配信手段から放送されたパケット中の任意の異なるＰ個のパケットを受信し、群連鎖反応符号化方式に基づき該Ｐ個のパケットから前記地図データを復元する情報処理手段と、を備えることを特徴とする地図データ処理システム。
2. 前記情報処理手段は、前記地図データを利用してナビゲーション機能を提供することを特徴とする請求項１記載の地図データ処理システム。
3. 前記情報処理手段は、走行体に実装された状態で動作することを特徴とする請求項１又は２記載の地図データ処理システム。
4. 更に、前記符号化データごとに生成したパケットの一部又は全部を所定の通信方式により送信する通信手段を備え、
   前記情報処理手段は、前記放送に基づきＳ個（Ｐ＞Ｓ）のパケットを受信し、前記通信手段からの送信に基づき前記Ｓ個のパケットと異なるＴ個（Ｓ＋Ｔ＝Ｐ）のパケットを受信し、前記Ｓ個のパケット及び前記Ｔ個のパケットから前記地図データを復元することを特徴とする請求項１乃至３のいずれか１項に記載の地図データ処理システム。
5. 地図データ配信手段から放送波により放送される符号化データを受信し、該符号化データに基づき地図データを復元する地図データ処理システムであって、
   前記符号化データは、地図データを対象として群連鎖反応符号化方式に基づき生成された符号化データであり、
   地図データ処理システムは、前記地図データ配信手段から放送されたＰ個以上の符号化データのうち任意の異なるＰ個の符号化データから、群連鎖反応符号化方式に基づき前記地図データを復元することを特徴とする地図データ処理システム。
6. 地図データベースに記憶される地図データより、群連鎖反応符号化方式に基づきＰ個以上の符号化データを生成して、該符号化データごとにパケットを生成するパケット生成工程と、
   前記パケットを放送波により放送する放送工程と、
   放送された前記パケット中の任意の異なるＰ個のパケットを受信する工程と、
   受信した前記Ｐ個のパケットから群連鎖反応符号化方式に基づき前記地図データを復元する工程と、を備えることを特徴とする地図データ処理方法。

Images