(57)【特許請求の範囲】
【請求項１】
パケット単位で送信される番組情報を含むＦＭ多重放送電波を受信する受信手段と、
前記受信されたＦＭ多重放送電波から前記番組情報を抽出して番組の組立を行う番組組立手段とを備えたＦＭ多重放送受信機において、
前記番組情報を構成する各パケットのデータ、および各パケット相互間の接続関係を示す情報を記憶する第１の番組管理テーブルと、
前記番組情報を複数のパケット単位で分割した各単位を示すデータグループ相互間の接続関係を示す情報、および各データグループに対応する前記第１の番組管理テーブルのアドレス情報を記憶する第２の番組管理テーブルとを備え、
前記第２の番組管理テーブルは、番組情報の種類を表すサービス識別番号および前記データグループの識別番号の双方を検索用のキーデータとして、該キーデータに関連のある前記第１の番組管理テーブルのアドレス情報と、該キーデータの後につながる前記第２の番組管理テーブルのキーデータのアドレス情報と、該キーデータの前につながる前記第２の番組管理テーブルのキーデータのアドレス情報とを含み、
検索された前記第２の番組管理テーブルのアドレス情報におけるキーデータが、組立を行うべき番組のデータグループのキーデータより小さい場合は、前記検索された前記第２の番組管理テーブルのアドレス情報におけるキーデータの後につながるキーデータの前記第２の番組管理テーブルのアドレス情報が検索され、検索された前記第２の番組管理テーブルのアドレス情報におけるキーデータが組立を行うべき番組のデータグループのキーデータより大きい場合は、前記検索された前記第２の番組管理テーブルのアドレス情報におけるキーデータの前につながるキーデータの前記第２の番組管理テーブルのアドレス情報が検索され、前記組立を行うべき番組のデータグループのキーデータと同じ値のキーデータが検索されるまで前記検索を続けることによって組立を行うべき番組のデータグループの前記第２の番組管理テーブルのアドレス情報を検索する第１のテーブル検索手段をさらに備え、
前記番組組立手段は、前記第１のテーブル検索手段の検索結果および前記第１と第２の番組管理テーブルに基づいて番組の組立を行うことを特徴とするＦＭ多重放送受信機。
【請求項２】
前記第１の番組管理テーブルは、パケット番号を検索用のキーデータとして、該キーデータに対応するパケットのデータと、該キーデータの後につながるキーデータのアドレス情報と、該キーデータの前につながるキーデータのアドレス情報とを少なくとも含むことを特徴とする請求項１に記載されたＦＭ多重放送受信機。
【請求項３】
前記組立を行うべき番組を選択する番組選択手段をさらに備え、
前記第１のテーブル検索手段は、前記番組選択手段により選択された番組の前記第２の番組管理テーブルのアドレス情報を検索し、
前記第１のテーブル検索手段によって検索された前記第２の番組管理テーブルのアドレス情報における前記第１の番組テーブルのアドレス情報に基づいて前記第１の番組管理テーブルの検索を行い、前記番組選択手段により選択された番組の先頭パケットに対応するデータの格納位置を検出する第２のテーブル検索手段と、
前記第２のテーブル検索手段による検索結果に基づいて前記第１の番組管理テーブルの検索を行い、前記番組選択手段により選択された番組の先頭パケットから接続順に各パケットのデータを検出する第３のテーブル検索手段とを備え、
前記番組組立手段は、前記第３のテーブル検索手段により検出された各パケットのデータを順につなげて番組の組立を行うことを特徴とする請求項１または２に記載されたＦＭ多重放送受信機。
【請求項４】
前記番組組立手段により組み立てられた番組に異常があるか否かを判断する異常判断手段と、
前記異常判断手段により異常がないと判断されると、前記第２の番組管理テーブルに基づいて、前記組み立てられた番組のパケットに対応する情報を検索する第４のテーブル検索手段と、
前記第４のテーブル検索手段による検索結果に基づいて前記第１の番組管理テーブルの検索を行い、前記組み立てられた番組の先頭パケットに対応するデータの格納位置を検出する第５のテーブル検索手段と、
前記第５のテーブル検索手段による検索結果に基づいて前記第１の番組管理テーブルの検索を行い、前記組み立てられた番組の先頭パケットから接続順に各パケットのデータを検出する第６のテーブル検索手段と、
前記第６のテーブル検索手段により検出された各パケットのデータを前記第１および第２の番組管理テーブルから順に消去する番組消去手段とを備えることを特徴とする請求項１〜３のいずれか１項に記載されたＦＭ多重放送受信機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＦＭ多重放送によりパケット単位で送信される番組情報を受信して番組の組立を行うＦＭ多重放送受信機に関する。
【０００２】
【従来の技術】
渋滞情報や事故情報等の複数の番組情報をＦＭ多重放送により送信する道路交通情報通信システムが知られている。これら番組情報は複数バイトから成るパケット単位で送信され、連続する複数のパケットを１つのデータグループとして各番組情報は複数のデータグループで構成されている。
【０００３】
ＦＭ多重放送受信機は、これら番組情報をパケット単位で受信して番組格納用メモリにいったん格納し、その後、必要に応じて番組格納用メモリから読み出して番組の組立処理を行う。具体的には、図１７に示すように、サービス種別番号Ｓｉと、データグループ番号Ｇｒと、パケット番号と、パケットデータとから成る番組管理テーブルを番組格納メモリ内に生成し、この番組管理テーブルに基づいて番組の組立処理を行うのが一般的である（例えば、特開平８−２３２８８  号）。
【０００４】
【発明が解決しようとする課題】
ところが、同一番組のパケットが必ずしもパケット番号順に受信されるとは限らず、番組を組み立てる際には、番組管理テーブルを順次検索していく必要がある。このため、番組の組立処理に時間がかかり、リアルタイム性が要求される交通情報などの情報提供が遅れ、情報の利用価値が薄れるおそれがある。
【０００５】
本発明の目的は、パケット単位で受信した番組の組立処理を迅速に行うことができるＦＭ多重放送受信機を提供することにある。
【０００６】
【課題を解決するための手段】
以下、発明の一実施の形態を示す図１に対応づけて本発明を説明する。
−請求項１−
請求項１に記載の発明は、パケット単位で送信される番組情報を含むＦＭ多重放送電波を受信する受信手段１ａと、受信されたＦＭ多重放送電波から番組情報を抽出して番組の組立を行う番組組立手段とを備えたＦＭ多重放送受信機に適用され、番組情報を構成する各パケットのデータ、および各パケット相互間の接続関係を示す情報を記憶する第１の番組管理テーブルと、番組情報を複数のパケット単位で分割した各単位を示すデータグループ相互間の接続関係を示す情報、および各データグループに対応する第１の番組管理テーブルのアドレス情報を記憶する第２の番組管理テーブルとを備え、第２の番組管理テーブルは、番組情報の種類を表すサービス識別番号およびデータグループの識別番号の双方を検索用のキーデータとして、該キーデータに関連のある第１の番組管理テーブルのアドレス情報と、該キーデータの後につながる第２の番組管理テーブルのキーデータのアドレス情報と、該キーデータの前につながる第２の番組管理テーブルのキーデータのアドレス情報とを含み、検索された第２の番組管理テーブルのアドレス情報におけるキーデータが、組立を行うべき番組のデータグループのキーデータより小さい場合は、検索された第２の番組管理テーブルのアドレス情報におけるキーデータの後につながるキーデータの第２の番組管理テーブルのアドレス情報が検索され、検索された第２の番組管理テーブルのアドレス情報におけるキーデータが組立を行うべき番組のデータグループのキーデータより大きい場合は、検索された第２の番組管理テーブルのアドレス情報におけるキーデータの前につながるキーデータの第２の番組管理テーブルのアドレス情報が検索され、組立を行うべき番組のデータグループのキーデータと同じ値のキーデータが検索されるまで検索を続けることによって組立を行うべき番組のデータグループの第２の番組管理テーブルのアドレス情報を検索する第１のテーブル検索手段をさらに備え、第１のテーブル検索手段の検索結果および第１と第２の番組管理テーブルに基づいて番組の組立を行うように番組組立手段を構成することにより上記目的は達成される。
請求項１に記載の発明では、各パケットのデータと各パケット相互間の接続関係とを示す情報を記憶する第１の番組管理テーブルを設ける。また、データグループ相互間の接続関係を示す情報と各データグループに対応する第１の番組管理テーブルのアドレス情報とを記憶する第２の番組管理テーブルを設ける。そして、第２の番組管理テーブルに基づいて第１の番組管理テーブルの検索開始位置を検出し、検出された検索開始位置を起点として第１の番組管理テーブルを検索して所望のパケットのデータを検出して番組の組立を行う。また、請求項１に記載の発明では、例えば図２（ａ）の番組管理テーブルＡのように、サービス識別番号およびデータグループの識別番号の双方を検索用のキーデータとし、各キーデータに対応する第２の番組管理テーブルのアドレス情報を第２の番組管理テーブルに格納する。また、第２の番組管理テーブルを二分検索木のデータ構造とし、キーデータの後につながるキーデータのアドレス情報と、キーデータの前につながるキーデータのアドレス情報とを格納する。
−請求項２−
請求項２に記載の発明は、パケット番号を検索用のキーデータとして、該キーデータに対応するパケットのデータと、該キーデータの後につながるキーデータのアドレス情報と、該キーデータの前につながるキーデータのアドレス情報とを少なくとも含むように第１の番組管理テーブルを構成するものである。
請求項２に記載の発明では、例えば図２（ｂ）の番組管理テーブルＢのように、パケット番号を検索用のキーデータとし、キーデータに対応する各パケットのデータを格納する。また、第２の番組管理テーブルを二分検索木のデータ構造とし、キーデータの後につながるキーデータのアドレス情報と、キーデータの前につながるキーデータのアドレス情報とを格納する。
−請求項３−
請求項３に記載の発明は組立を行うべき番組を選択する番組選択手段をさらに備え、
前記第１のテーブル検索手段は、前記番組選択手段により選択された番組の前記第２の番組管理テーブルのアドレス情報を検索し、
前記第１のテーブル検索手段によって検索された第２の番組管理テーブルのアドレス情報における第１の番組テーブルのアドレス情報に基づいて第１の番組管理テーブルの検索を行い、番組選択手段により選択された番組の先頭パケットに対応するデータの格納位置を検出する第２のテーブル検索手段と、第２のテーブル検索手段による検索結果に基づいて第１の番組管理テーブルの検索を行い、番組選択手段により選択された番組の先頭パケットから接続順に各パケットのデータを検出する第３のテーブル検索手段とを備え、第３のテーブル検索手段により検出された各パケットのデータを順につなげて番組の組立を行うように番組組立手段を構成するものである。
請求項３に記載の発明では、選択した番組に関連する情報を第２の番組管理テーブルから検索し、その情報に基づいて第１の番組管理テーブルを検索して番組の先頭パケットに対応するデータの格納位置を検出し、先頭パケットから順々に各パケットのデータを抽出して番組の組立を行う。
−請求項４−
請求項４に記載の発明は、番組組立手段により組み立てられた番組に異常があるか否かを判断する異常判断手段と、異常判断手段により異常がないと判断されると、第２の番組管理テーブルに基づいて、組み立てられた番組のパケットに対応する情報を検索する第４のテーブル検索手段と、第４のテーブル検索手段による検索結果に基づいて第１の番組管理テーブルの検索を行い、組み立てられた番組の先頭パケットに対応するデータの格納位置を検出する第５のテーブル検索手段と、第５のテーブル検索手段による検索結果に基づいて第１の番組管理テーブルの検索を行い、組み立てられた番組の先頭パケットから接続順に各パケットのデータを検出する第６のテーブル検索手段と、第６のテーブル検索手段により検出された各パケットのデータを第１および第２の番組管理テーブルから順に消去する番組消去手段とを備えるものである。
請求項４に記載の発明では、何ら異常なく組立が終了した番組については、組立終了後に、番組組立と同一手順で第１および第２の番組管理テーブルを検索し、組み立てた番組に関する情報を各テーブルから消去する。
【０００７】
なお、本発明の構成を説明する上記課題を解決するための手段の項では、本発明を分かり易くするために本発明の一実施の形態の図を用いたが、これにより本発明が一実施の形態に限定されるものではない。
【０００８】
【発明の実施の形態】
以下、図１〜１６に基づいて本発明の一実施の形態について説明する。図１は本発明に係るＦＭ多重放送受信機の一実施の形態のブロック図である。本実施の形態のＦＭ多重放送受信機は、ＦＭ多重ユニット１と、ＡＶコントロールユニット２と、ディスプレイユニット３とで構成される。ＦＭ多重ユニット１は、アンテナ４で受信された電波のうち所望の周波数のＦＭ信号電波を選局するＦＭチューナ１ａと、ＦＭチューナ１ａで選局されたＦＭ信号電波を復調する復調器１ｂと、復調器１ｂで復調されたデジタル信号の誤り訂正を行う誤り訂正部１ｃと、番組の組立を行うマイコン１ｄと、番組表示のための映像信号を生成する描画部１ｅとで構成される。一方、ディスプレイユニット３は、メニュー選択を行う操作ボタン３ａと、操作ボタン３ａの操作状態を検出するマイコン３ｂと、番組情報を表示する液晶表示器（ＬＣＤ）３ｃとで構成される。また、ＡＶコントロールユニット２の内部には、不図示のアンプやテープデッキ等を制御するマイコン２ａが設けられている。
【０００９】
ＦＭ多重ユニット１内部のマイコン１ｄにはＲＡＭ１ｆが内蔵されており、番組情報を構成するパケット群が受信されると、マイコン１ｄは図２（ａ），（ｂ）に示すような番組管理テーブルＡ，ＢをＲＡＭ１ｆの内部に生成する。ここで、サービス識別番号Ｓｉ、データグループ番号Ｇｒおよびパケット番号はＦＭ多重放送により提供されるが、図２（ａ），（ｂ）に示すａ，ｂ、Ｘ０などのアドレス情報は、マイコン１ｄ内部で演算される。
【００１０】
番組管理テーブルＡは、サービス識別番号Ｓｉとデータグループ番号Ｇｒとの双方をテーブル検索用のキーデータとして、キーデータに対応する番組管理テーブルＢのアドレス情報と、キーデータの後につながるキーデータ（大きいキーデータ）のアドレス情報と、キーデータの前につながるキーデータ（小さいキーデータ）のアドレス情報とで構成される。一方、番組管理テーブルＢはパケット番号をキーデータとして、パケットデータと、キーデータの後につながるキーデータ（大きいキーデータ）のアドレス情報と、キーデータの前につながるキーデータ（小さいキーデータ）のアドレス情報とで構成される。なお、１つのグループは１以上のパケットで構成される。例えば、サービス識別番号Ｓｉ２  およびデータグループ番号Ｇｒ２  を一対とするキーデータを持つグループ、すなわちアドレス情報Ｙ０，Ｙ１，Ｙ２…のグループは、図２（ｂ）に示すようにパケット４，６，７から構成される。
【００１１】
このように、番組管理テーブルＡ，Ｂはそれぞれ図３（ａ），（ｂ）に簡略化して示すように、二分検索木のデータ構造を有する。そして、番組管理テーブルＡには、サービス識別番号Ｓｉおよびデータグループ番号Ｇｒをキーデータとするキーデータ相互間の関係を示すアドレス情報（ａ，ｂなど）と、各キーデータに対応する番組管理テーブルＢのアドレス情報（Ｘ０，Ｙ０，Ｚ０など）とが格納される。一方、番組管理テーブルＢには、パケット番号をキーデータとするキーデータ相互間の関係を示すアドレス情報が格納される。なお、番組管理テーブルＢには、同一パケットのアドレス情報が重複して格納されることはない。
【００１２】
例えば、サービス識別番号Ｓｉ２，データグループ番号Ｇｒ２で表される番組の組立処理は、以下の手順で行われる。
▲１▼まず、Ｓｉ２，Ｇｒ２の番組に対応するパケットデータの番組管理テーブルＢ内の格納位置を検索する処理を行う。具体的には、図２（ａ）の番組管理テーブルＡの先頭行を検索開始位置として検索を開始し、Ｓｉ２，Ｇｒ２が見つかると（図２（ａ）のアドレスａ）、このアドレスａに番組管理テーブルＢのアドレス情報として格納されている検索開始位置Ｙ０を読み出す。
▲２▼次に、上記▲１▼で設定された検索開始位置のアドレスＹ０を起点として番組管理テーブルＢを検索し、番組の先頭パケットデータを読み出す。
▲３▼次に、先頭パケットデータにつながる同一キーデータでグループ分けされたパケットデータを読み出して、先頭パケットデータにつなげる。
▲４▼上記▲３▼の組立処理を、番組の最後尾のパケットデータをつなげるまで続ける。
▲５▼次に、組み立てた番組に対してＣＲＣチェックを行う。
▲６▼次に、上記▲１▼と同様に、番組管理テーブルＢの検索開始位置のアドレスを検索する。
▲７▼次に、番組管理テーブルＢにおける先頭パケットデータの格納位置を検出する。
▲８▼次に、先頭パケットデータをＲＡＭ１ｆから消去する。
▲９▼以下、最後尾のパケットデータまで、同一キーデータでグループ分けされた複数のパケットデータを順々にＲＡＭ１ｆから消去する。
【００１３】
図４，５はＦＭ多重ユニット１内部のマイコン１ｄが行う番組組立処理を示すフローチャートであり、以下このフローチャートに基づいて本実施の形態の動作を説明する。図４に示す処理は１つのパケットを受信し番組管理テーブルＡと番組管理テーブルＢとを作成した後に実行される。図４のステップＳ１では、番組が確立したか否か、すなわちグループ（番組）を構成するパケットの全てが存在するか否かを判定し、番組が確立していなければステップＳ１に留まり、番組が確立するとステップＳ２に進む。ここで、グループを確定するパケットが全て存在しなければ、検索を行う必要がないため、番組が確立したか否かの判定を行うものである。ステップＳ２では、図６に詳細を示すテーブルＡ検索処理を行う。このテーブルＡ検索処理では、後述するように、番組管理テーブルＡの中から、所定のサービス識別番号Ｓｉとグループ番号Ｇｒとで分類された確立した番組を構成するパケット群における番組管理テーブルＢ内の先頭格納位置を検索する。
【００１４】
次にステップＳ３では、図７に詳細を示すテーブルＢ検索処理Ａを行う。このテーブルＢ検索処理Ａでは、後述するように番組管理テーブルＢを検索して、サービス識別番号Ｓｉとグループ番号Ｇｒとで特定された番組を構成するパケット群の先頭パケットの格納位置を検出する処理を行う。次にステップＳ４では、番組組立用の作業領域を初期化する。なお、この作業領域はＲＡＭ１ｆの内部に生成される。
【００１５】
次にステップＳ５では、取得したアドレスのパケットデータを番組管理テーブルＢから読み出し、次にステップＳ６では、読み出したパケットデータを作業領域上で順次つなぎ合わせる。次にステップＳ７では、図８に詳細を示すテーブルＢ検索処理Ｂを行う。テーブルＢ検索処理Ｂでは、後述するように、直前に読み出したパケット番号よりも大きくて、直前に読み出したパケット番号に最も近いパケットデータのアドレスを検索する処理を行う。
【００１６】
次にステップＳ８では、つなぎ合わせるべきパケットがまだ残っているか否かを判定し、残っていればステップＳ５に、残っていなければ図５のステップＳ９に進む。ステップＳ９では、組立の終わった番組に対してＣＲＣチェックを行う。次にステップＳ１０では、ＣＲＣチェックに異常があるか否かを判定し、異常があればステップＳ１に戻り、異常がなければステップＳ１１に進む。
【００１７】
ステップＳ１１では、ステップＳ２と同様にテーブルＡ検索処理を行い、確立した番組を構成する複数のパケットの番組管理テーブルＢ内の先頭格納位置を検出する。次にステップＳ１２では、ステップＳ３と同様に、テーブルＢ検索処理Ａを行い、確立した番組を構成する先頭パケットデータの番組管理テーブルＢ内の格納位置を検出する。次にステップＳ１３では、まだ消去していないパケットデータを番組管理テーブルＢから消去する。次にステップＳ１４では、ステップＳ７と同様にテーブルＢ検索処理Ｂを行い、直前に読み出したパケット番号よりも大きくて、直前に読み出したパケット番号に最も近いパケットデータの、番組管理テーブルＢ内の格納位置を検出する。
【００１８】
次にステップＳ１５では、消去すべきパケットデータがまだ残っているか否かを判定し、まだ残っていればステップＳ１３に戻り、残っていなければステップＳ１６に進む。ステップＳ１６では、図９，１０に詳細を示すテーブルＡデータ消去処理を行う。テーブルＡデータ消去処理では、後述するように、組立の終了した番組に関する情報を番組管理テーブルＡから消去し、キーデータ相互間の接続関係を変更する処理を行う。ここで、テーブルＡ，Ｂのデータの消去を行うのは、１つのパケットは繰り返し送信され、同一のサービス識別番号Ｓｉ、データグループ番号Ｇｒおよびパケット番号であっても、時間の経過とともにパケットデータが異なる場合があり、ＣＲＣチェックが正常であれば、次回のデータを０から受信できるようにするためである。
【００１９】
このように、図４，５の番組組立処理では、番組管理テーブルＡを検索して番組管理テーブルＢの検索場所を特定し（ステップＳ２）、次に番組管理テーブルＢを検索して一つの番組の先頭パケットの格納位置を検出する（ステップＳ３）。次に、先頭パケットから順にパケットデータを読み出して番組の組立を行い（ステップＳ４〜Ｓ８）、番組組立が完了するとＣＲＣチェックを行う（ステップＳ９，Ｓ１０）。ＣＲＣチェックが問題なければ、再度番組管理テーブルＡ，Ｂを検索して番組組立の終了した番組情報を番組管理テーブルＡ，Ｂから削除する（ステップＳ１１〜Ｓ１６）。
【００２０】
図６は図４，５のステップＳ２，Ｓ１１のテーブルＡ検索処理の詳細フローチャートである。図６のステップＳ５１では、検索位置を番組管理テーブルＡの先頭アドレスに設定する。次にステップＳ５２では、検索位置のキーデータが検索目標値と一致するか否かを判定する。ここで、検索目標値とは、確立した番組に対応するキーデータであり、例えばサービス識別番号がＳｉ２でデータグループ番号Ｇｒ２である。図２に示すように、このキーデータはアドレスａに割り付けられている。
【００２１】
検索位置のキーデータが検索目標値よりも小さい場合にはステップＳ５３に進み、現在の検索位置のキーデータよりも大きいキーデータのアドレスを新たな検索位置としてステップＳ５２に戻る。一方、検索位置のキーデータが検索目標値よりも大きい場合にはステップＳ５４に進み、現在の検索位置のキーデータよりも小さいキーデータのアドレスを新たな検索位置としてステップＳ５２に戻る。一方、検索位置のキーデータと検索目標値とが一致する場合にはステップＳ５５に進み、現在の検索位置をアドレスとして番組管理テーブルＡからデータを読み出し、番組管理テーブルＢの格納位置を検出する。ここで、番組管理テーブルＡ，Ｂにおけるキーデータの大小の比較は、キーデータを単純に比較することにより行う。番組管理テーブルＡはＳｉ×２５６＋Ｇｒの演算の結果を比較する。例えば、Ｓｉ１  ＝２、Ｇｒ１  ＝１、Ｓｉ２  ＝３、Ｇｒ２  ＝４とすると、
Ｓｉ１  ×２５６＋Ｇｒ１  ＝１×２５６＋２＝２５８
Ｓｉ２  ×２５６＋Ｇｒ２  ＝３×２５６＋４＝７７２
となり、Ｓｉ２  、Ｇｒ２  の方が大きいと判断される。  なお、番組管理テーブルＢはパケット番号を単純に比較する。
【００２２】
図７は図４，５のステップＳ３，Ｓ１２のテーブルＢ検索処理Ａの詳細フローチャートである。図７のステップＳ１０１では、検索位置のパケット番号よりも小さいパケット番号が存在するか否かを判定する。ここでは、図２（ｂ）に示す番組管理テーブルＢの「小さいキーデータ（パケット番号）のアドレス情報」の欄にアドレス値が登録されていれば、小さいパケット番号が存在すると判断する。なお、テーブルＢ検索処理Ａを開始する時点では、図６のステップＳ５５で検出された位置が検索位置となる。検索位置のパケット番号よりも小さいパケット番号が存在する場合にはステップＳ１０２に進み、現在の検索位置をスタックに退避する。なお、スタックは、ＲＡＭ１ｆの内部に生成される。
【００２３】
次にステップＳ１０３では、現在の検索位置よりも小さいパケット番号のアドレスを新たな検索位置としてステップＳ１０１に戻る。ステップＳ１０１の判定が否定されるとステップＳ１０４に進み、現在の検索位置をパケットデータの読み出し位置に設定する。
【００２４】
図８は図４，５のステップＳ７，Ｓ１４のテーブルＢ検索処理Ｂの詳細フローチャートである。図８のステップＳ１５１では、検索位置のパケット番号よりも大きいパケット番号が存在するか否かを判定し、大きいパケット番号が存在する場合にはステップＳ１５２に進む。ステップＳ１５２では、現在の検索位置のパケット番号よりも大きいパケット番号のアドレスを新たな検索位置とする。次にステップＳ１５３では、検索位置のパケット番号よりも小さいパケット番号が存在するか否かを判定し、存在する場合にはステップＳ１５４に進み、現在の検索位置をスタックに退避する。次にステップＳ１５５では、検索位置のパケット番号よりも小さいパケット番号のアドレスを新たな検索位置としてステップＳ１５３に戻る。一方、ステップＳ１５３の判定が否定されるとステップＳ１５６に進み、現在の検索位置をパケットデータの読み出し位置に設定してリターンする。
【００２５】
一方、ステップＳ１５１において、検索位置のパケット番号よりも大きいパケット番号が存在しないと判定されるとステップＳ１５７に進み、スタックにアドレス情報が退避されているか否かを判定する。スタックにアドレス情報が退避されていない場合にはステップＳ１５８に進み、検索位置にパケットデータが存在しない旨の設定を行う。また、スタックにアドレス情報が退避されている場合にはステップＳ１５９に進み、スタックから取り出したアドレスを番組管理テーブルＢの読み出し位置に設定する。
【００２６】
図９，１０は図５のステップＳ１６のテーブルＡデータ消去処理の詳細フローチャートである。図９のステップＳ２０１では、消去すべきキーデータを検索目標値に設定する。次にステップＳ２０２では、現在の検索位置を処理対象位置とする。次にステップＳ２０３では、現在の検索位置のキーデータが検索目標値と一致するか否かを判定する。現在の検索位置のキーデータが検索目標値よりも小さければステップＳ２０４に進み、現在の検索位置を処理対象位置として記憶する。次にステップＳ２０５では、現在の検索位置のキーデータよりも大きいキーデータのアドレスを新たな検索位置としてステップＳ２０３に戻る。
【００２７】
一方、ステップＳ２０３において、現在の検索位置のキーデータが検索目標値よりも大きいと判定されるとステップＳ２０６に進み、現在の検索位置を処理対象位置として記憶する。次にステップＳ２０７では、現在の検索位置のキーデータよりも小さいキーデータのアドレスを新たな検索位置としてステップＳ２０３に戻る。
【００２８】
一方、ステップＳ２０３において、現在の検索位置のデータと検索目標値とが等しいと判定されるとステップＳ２０８に進み、現在の検索位置をデータの消去位置とする。次にステップＳ２０９では、消去位置のキーデータよりも小さいキーデータが存在するか否かを判定し、小さいキーデータが存在しない場合には図１０のステップＳ２１０に進む。ステップＳ２１０では、消去位置のキーデータよりも大きいキーデータが存在するか否かを判定し、存在しなければステップＳ２１１に進む。ステップＳ２１１では、処理対象位置が持つ大きいキーデータのアドレスが消去位置と一致するか否かを判定し、一致すればステップＳ２１２に進み、消去対象位置は大きいキーデータを持たない旨の設定を行う。一方、一致しなければステップＳ２１３に進み、処理対象位置は小さいキーデータを持たない旨の設定を行う。
【００２９】
図１１（ａ）は図１０のステップＳ２１１の判定が肯定される場合の二分検索木の一例を示す図である。図１１（ａ）の二分検索木は、ステップＳ２１２の処理を行うことで図１１（ｂ）のように整形される。また、図１１（ｃ）は図１０のステップＳ２１１の判定が否定される場合の二分検索木の一例を示す図である。図１１（ｃ）の二分検索木は、ステップＳ２１３の処理を行うことで図１１（ｄ）のように整形される。ここで、二分検索木の整形を行うのは、以下の理由によるものである。例えば、上記図９，１０に示す消去処理によりＳｉ２  およびＧｒ２  のキーデータのグループを削除したとすると、図２（ａ）のＳｉ２  およびＧｒ２  のキーデータグループのアドレスａより先の部分にはデータが存在しなくなり、キーデータの大小関係が破壊されててしまう。したがって、このような不具合を是正してキーデータの大小関係を元の状態に戻すために二分検索木の整形を行うものである。
【００３０】
一方、ステップＳ２１０において、消去位置のキーデータよりも大きいキーデータが存在すると判定されるとステップＳ２１４に進み、処理対象位置のキーデータが持つ大きいキーデータのアドレスが消去位置と一致するか否かを判定する。一致すればステップＳ２１５に進み、処理対象位置が持つ大きいキーデータのアドレスを、消去位置が持つ大きいキーデータのアドレスとする。一方、一致しなければステップＳ２１６に進み、処理対象位置が持つ小さいキーデータのアドレスを、消去位置が持つ大きいキーデータのアドレスとする。
【００３１】
図１１（ｅ）は図１０のステップＳ２１４の判定が肯定される場合の二分検索木の一例を示す図である。図１１（ｅ）の二分検索木は、ステップＳ２１５の処理を行うことで図１１（ｆ）のように整形される。また、図１１（ｇ）は図１０のステップＳ２１４の判定が否定される場合の二分検索木の一例を示す図である。図１１（ｇ）の二分検索木は、ステップＳ２１６の処理を行うことで図１１（ｈ）のように整形される。
【００３２】
一方、図９のステップＳ２０９において、消去位置のキーデータよりも小さいキーデータが存在すると判定されるとステップＳ２１７に進み、消去位置のキーデータよりも大きいキーデータが存在するか否かを判定する。大きいキーデータが存在しない場合には図１０のステップＳ２１８に進み、処理対象位置が持つ大きいキーデータのアドレスが消去位置と一致するか否かを判定する。一致する場合にはステップＳ２１９に進み、処理対象位置が持つ大きいキーデータのアドレスを、消去位置が持つ小さいキーデータのアドレスとする。一方、一致しない場合にはステップＳ２２０に進み、処理対象位置が持つ小さいキーデータのアドレスを、消去位置が持つ小さいキーデータのアドレスとする。
【００３３】
図１１（ｉ）は図１０のステップＳ２１８の判定が肯定される場合の二分検索木の一例を示す図である。図１１（ｉ）の二分検索木は、ステップＳ２１９の処理を行うことで図１１（ｊ）のように整形される。また、図１１（ｋ）は図１０のステップＳ２１８の判定が否定される場合の二分検索木の一例を示す図である。図１１（ｋ）の二分検索木は、ステップＳ２２０の処理を行うことで図１１（ｌ）のように整形される。
【００３４】
一方、図９のステップＳ２１７において、消去位置のキーデータよりも大きいキーデータが存在すると判定されると図１０のステップＳ２２１に進み、図１２に詳細を示す二分検索木つけかえ処理を行う。なお、二分検索木つけかえ処理の詳細については後述する。
【００３５】
図１０のステップＳ２１２，Ｓ２１５，Ｓ２１９，Ｓ２２０または図９のＳ２２１の処理が終了すると図９のステップＳ２２２に進み、消去位置のデータを番組管理テーブルＡから消去してリターンする。
【００３６】
図１２は図９のステップＳ２２１の二分検索木つけかえ処理の詳細フローチャートである。図１２のステップＳ３０１では、消去位置が持つ大きいキーデータのアドレスを検索位置とする。次にステップＳ３０２では、現在の検索位置を切り離し位置としてＲＡＭ１ｆに記憶する。次にステップＳ３０３では、現在の検索位置が小さいキーデータを持っているか否かを判定し、持っている場合にはステップＳ３０４に進む。ステップＳ３０４では、現在の検索位置を切り離し位置としてＲＡＭ１ｆに記憶する。次にステップＳ３０５では、現在の検索位置が持つ小さいキーデータのアドレスを新たな検索位置としてステップＳ３０３に戻る。
【００３７】
一方、ステップＳ３０３において、現在の検索位置が小さいキーデータを持っていないと判定されるとステップＳ３０６に進み、現在の検索位置が消去位置の持つ大きいキーデータのアドレスと一致するか否かを判定する。一致する場合にはステップＳ３０７に進み、処理対象位置が持つ小さいキーデータのアドレスを、消去位置が持つ大きいキーデータのアドレスに置き換える。次にステップＳ３０８では、現在の検索位置が持つ小さいキーデータのアドレスを、消去位置が持つ小さいキーデータのアドレスに置き換える。
【００３８】
一方、ステップＳ３０６の判定が否定されるとステップＳ３０９に進み、処理対象位置が持つ小さいキーデータのアドレスを、切り離し位置が持つ小さいキーデータのアドレスに置き換える。次にステップＳ３１０では、検索位置が持つ小さいキーデータのアドレスを、消去位置が持つ小さいキーデータのアドレスに置き換える。次にステップＳ３１１では、切り離し位置が持つ小さいキーデータのアドレスを、検索位置が持つ大きいキーデータのアドレスに置き換える。次にステップＳ３１２では、検索位置が持つ大きいキーデータのアドレスを消去位置が持つ大きいキーデータのアドレスに置き換える。
【００３９】
図１３，１５は二分検索木つけかえ処理を行う対象となる二分検索木の一例を示す図である。図示のように、消去位置が大きいキーデータ（孫ｂ）と小さいキーデータ（孫ａ）の双方を持っている場合に二分検索木つけかえ処理が行われる。図１３の二分検索木の場合、まず、消去位置のキーデータよりも大きく、かつ消去位置のキーデータに最も近いキーデータ（例えば、子孫Ｙ）を検索する（図１２のステップＳ３０１〜Ｓ３０５）。次に、消去位置の親が持つ大きいキーデータのアドレスを、子孫Ｙのアドレスに置き換える（図１２のステップＳ３０９）。次に、子孫Ｙが持つ小さいキーデータのアドレスを孫ａのアドレスに置き換える（図１２のステップＳ３１０）。次に、子孫Ｘが持つ小さいキーデータのアドレスを子孫Ｚのアドレスに置き換える（図１２のステップＳ３１１）。次に、子孫Ｙが持つ大きいキーデータのアドレスを孫ｂのアドレスに置き換える（図１２のステップＳ３１２）。この結果、図１３の二分検索木は図１４のように整形される。
【００４０】
一方、図１５の二分検索木の場合、消去位置が持つ大きいキーデータ（孫ｂ）が小さいキーデータを持っていないため、図１２のステップＳ３０６の判定が肯定される。そして、親の大きいキーデータのアドレスを孫ｂのアドレスに置き換えた後（図１２のステップＳ３０７）、孫ｂの小さいキーデータのアドレスを孫ａのアドレスに置き換える（図１２のステップＳ３０８）。この結果、図１５の二分検索木は図１６のように整形される。
【００４１】
上記実施の形態では、図２に示すようなデータ構造の番組管理テーブルＡ，ＢをＲＡＭ１ｆの内部に生成したが、各テーブルに含まれるデータ項目の数や種類は図２に限定されない。例えば、サービス識別番号とデータグループ番号のいずれか一方だけを設けてもよい。
【００４２】
このように構成した一実施の形態にあっては、ＦＭチューナ１ａが受信手段に、図４のステップＳ６が番組組立手段に、番組管理テーブルＢが第１の番組管理テーブルに、番組管理テーブルＡが第２の番組管理テーブルに、図４のステップＳ１が番組選択手段に、図４のステップＳ２が第１のテーブル検索手段に、図４のステップＳ３が第２のテーブル検索手段に、図４のステップＳ７が第３のテーブル検索手段に、図５のステップＳ１０が異常判断手段に、図５のステップＳ１１が第４のテーブル検索手段に、図５のステップＳ１４が第６のテーブル検索手段に、図５のステップＳ１６が番組消去手段に、それぞれ対応する。
【００４３】
【発明の効果】
以上詳細に説明したように、本発明によれば、パケット単位で分類された第１の番組管理テーブルと、複数のパケット単位で分類された第２の番組管理テーブルとを用いて番組の組立を行うため、番組組立処理に要する時間が少なくて済み、受信した番組をリアルタイムに提供することができる。また、第１の番組管理テーブルの内部に、サービス識別番号およびデータグループの識別番号の少なくとも一方を検索用のキーデータとして、各キーデータに関連のある第２の番組管理テーブルのアドレス情報を格納するため、サービス識別番号およびデータグループと、パケットデータとの関係を簡易かつ正確に検出できる。また、第１の番組管理テーブルを二分検索木のデータ構造にしたため、各キーデータ間の関係がわかりやすくなる。さらに、第２の番組管理テーブルを二分検索木のデータ構造にしたため、各キーデータ間の関係がわかりやすくなり、番組組立処理を高速化できる。
請求項２に記載の発明によれば、第２の番組管理テーブルの内部に、パケット番号を検索用のキーデータとして、各キーデータに対応するパケットのデータを格納するため、パケット番号と、パケットデータとの関係を簡易かつ正確に検出できる。
請求項３に記載の発明によれば、第１〜第３のテーブル検索手段を設けるため、番組の先頭パケットから順々に滞りなく迅速に選択して番組組立処理を行うことができる。
請求項４に記載の発明によれば、組立の終了した番組に関する各情報を、番組組立処理と同一手順で消去するため、不要になった情報を各テーブルから迅速に消去して新たな番組情報の受信に備えることができる。
【図面の簡単な説明】
【図１】本発明に係るＦＭ多重放送受信機の一実施の形態のブロック図。
【図２】（ａ）は番組管理テーブルＡのデータ構造を示す図、（ｂ）は番組管理テーブルＢのデータ構造を示す図。
【図３】（ａ）は番組管理テーブルＡを模式化した図、（ｂ）は番組管理テーブルＢを模式化した図。
【図４】ＦＭ多重ユニット内部のマイコンが行う番組組立処理を示すフローチャート。
【図５】図４に続くフローチャート。
【図６】図４のステップＳ２のテーブルＡ検索処理の詳細フローチャート。
【図７】図４のステップＳ３のテーブルＢ検索処理Ａの詳細フローチャート。
【図８】図４のステップＳ７のテーブルＢ検索処理Ｂの詳細フローチャート。
【図９】図５のステップＳ１６のテーブルＡデータ消去処理の詳細フローチャート。
【図１０】図９に続くフローチャート。
【図１１】図１０のステップＳ２１０〜Ｓ２２０に関する二分検索木の例を示す図。
【図１２】図９のステップＳ２２１の二分検索木つけかえ処理の詳細フローチャート。
【図１３】二分検索木つけかえ処理を行う対象となる二分検索木の例を示す図。
【図１４】図１３の二分検索木を整形した二分検索木の例を示す図。
【図１５】二分検索木つけかえ処理を行う対象となる二分検索木の例を示す図。
【図１６】図１５の二分検索木を整形した二分検索木の例を示す図。
【図１７】従来の番組管理テーブルのデータ構造を示す図。
【符号の説明】
１  ＦＭ多重ユニット
１ａ  ＦＭチューナ
１ｂ  復調器
１ｃ  誤り訂正部
１ｄ  マイコン
１ｅ  描画部
１ｆ  ＲＡＭ
２  ＡＶコントロールユニット
２ａ  マイコン
３  ディスプレイユニット
３ａ  操作ボタン
３ｂ  マイコン
３ｃ  液晶表示器
４  アンテナ
【図１】
0003630840.tif 000002
【図２】
0003630840.tif 000003
【図３】
0003630840.tif 000004
【図４】
0003630840.tif 000005
【図５】
0003630840.tif 000006
【図６】
0003630840.tif 000007
【図７】
0003630840.tif 000008
【図８】
0003630840.tif 000009
【図９】
0003630840.tif 000010
【図１０】
0003630840.tif 000011
【図１１】
0003630840.tif 000012
【図１２】
0003630840.tif 000013
【図１３】
0003630840.tif 000014
【図１４】
0003630840.tif 000015
【図１５】
0003630840.tif 000016
【図１６】
0003630840.tif 000017
【図１７】
0003630840.tif 000018