(57)【要約】【課題】割り当て時の処理時間を短縮するとともに、有限であるコード番号を効率的に割り当て可能とする。【解決手段】コード番号を多段階層の２分岐木構造化したコードツリーを用いる。そして、各コード番号対応のコード番号状態テーブルに、自コード番号と、第一及び第二の子コード番号との使用状況を記録し、各階層対応の割り当て優先テーブル１０１〜１０４に、自コード番号の使用状況が使用不可状態であるコード番号＃ｎを記録する。コードの割り当て時に、割り当て対象階層より１階層上位の割り当て優先テーブルを参照して使用不可状態の親コード番号を取得し、当該コード番号のコード番号状態テーブルを参照して、子コード番号の使用状況が未使用状態のものを検索し、該当する未使用状態の子コード番号があれば、そのコード番号を割り当てる。【選択図】      図２
2005109542.tif 000002
【特許請求の範囲】
【請求項１】
ＣＤＭＡ移動通信システムの移動機に対し無線リソースとしてのコードを割り当てる際、コードに対応したコード番号を伝送レートに対応した多段階層の２分岐木構造化し、割り当て中のコード番号とその直系の上位階層及び下位階層にあるすべてのコード番号との新たな割り当てを不可とするコードツリーを用いて割り当てるコード割り当て方法において、
各コード番号対応のコード番号状態テーブルに、自コード番号の使用状況と、第一の子コード番号の使用状況と、第二の子コード番号の使用状況とを記録しておき、
コードの割り当て要求発生時に、割り当て対象階層より１階層上位の各コード番号に対応する前記各コード番号状態テーブルを参照して、前記自コード番号の使用状況が直系の他のコード番号の割り当てによる使用不可状態で、かつ、前記第一及び第二のいずれか一方の子コード番号の使用状況が未使用状態のものを検索し、該当する未使用状態の子コード番号があれば、そのコード番号を割り当てることを特徴とするコード割り当て方法。
【請求項２】
各階層対応の割り当て優先テーブルに、自コード番号の使用状況が使用不可状態であるコード番号を記録しておき、
前記コードの割り当て要求発生時に、割り当て対象階層より１階層上位の前記割り当て優先テーブルを参照して前記自コード番号の使用状況が使用不可状態のものを優先的に検索可能としたことを特徴とする請求項１記載のコード割り当て方法。
【請求項３】
コード番号を割り当てた後、
当該コード番号を割り当てたことにより新たな割り当てが不可となる直系の上位階層及び下位階層のすべてのコード番号を算出し、
前記割り当てたコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用中状態を、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、
前記直系の下位階層のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、
前記直系の１階層上位のコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用不可状態が記録されていなければ記録し、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用中状態を記録し、
前記直系の２階層以上上位のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用不可状態が記録されていなければ記録し、
前記コード番号状態テーブルの自コード番号の使用状況として新たに使用不可状態を記録したコード番号を、当該コード番号に対応する階層の割り当て優先テーブルに記録し、所定の優先順位にしたがってコード番号の並び替えを行うことを特徴とする請求項２記載のコード割り当て方法。
【請求項４】
ＣＤＭＡ移動通信システムの移動機に対し無線リソースとしてのコードを割り当てるコード割り当てシステムにおいて、
コードに対応したコード番号を伝送レートに対応した多段階層の２分岐木構造化し、割り当て中のコード番号とその直系の上位階層及び下位階層にあるすべてコード番号との新たな割り当てを不可とするコードツリーと、
各コード番号対応に、自コード番号の使用状況と、第一の子コード番号の使用状況と、第二の子コード番号の使用状況とを記録するコード番号状態テーブルと、
コードの割り当て要求を受けると、割り当て対象階層より１階層上位の各コード番号に対応する前記各コード番号状態テーブルを参照して、前記自コード番号の使用状況が直系の他のコード番号の割り当てによる使用不可状態で、かつ、前記第一及び第二のいずれか一方の子コード番号の使用状況が未使用状態のものを検索し、該当する未使用状態の子コード番号があれば、そのコード番号を割り当てる手段とを有することを特徴とするコード割り当てシステム。
【請求項５】
自コード番号の使用状況が使用不可状態であるコード番号を記録する各階層対応の割り当て優先テーブルを有し、
前記コードの割り当て要求発生時に、割り当て対象階層より１階層上位の前記割り当て優先テーブルを参照して前記自コード番号の使用状況が使用不可状態のものを優先的に検索可能としたことを特徴とする請求項４記載のコード割り当てシステム。
【請求項６】
コード番号を割り当てた後、当該コード番号を割り当てたことにより新たな割り当てが不可となる直系の上位階層及び下位階層のすべてのコード番号を算出する手段と、
前記割り当てたコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用中状態を、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の下位階層のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の１階層上位のコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用不可状態が記録されていなければ記録し、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用中状態を記録し、前記直系の２階層以上上位のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用不可状態が記録されていなければ記録する手段と、
前記コード番号状態テーブルの自コード番号の使用状況として新たに使用不可状態を記録したコード番号を、当該コード番号に対応する階層の割り当て優先テーブルに記録し、所定の優先順位にしたがってコード番号の並び替えを行う手段とを有することを特徴とする請求項５記載のコード割り当てシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＣＤＭＡ（Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ：符号分割多元接続）方式の移動通信システムにおいて、移動機から接続要求があった場合、伝送レートに対応した多段階層の２分岐木構造のコードツリーを用いて無線リソースとしてのコードを割り当てる際の割り当て方法及び割り当てシステムに関する。
【背景技術】
【０００２】
従来よりＣＤＭＡ方式の移動通信システムにおいて、移動機から接続要求があった場合に、基地局装置や基地局制御装置等の上位装置では、無線リソース（この場合、ＣＯＤＥ、コード、符号）の割り当てを行うために、装置内にコードに対応したＣＯＤＥ番号（コード番号）を記憶しておくＣＯＤＥ番号記憶エリア（コード番号記憶エリア）を有している。
【０００３】
図４に、ＣＯＤＥ番号記憶エリアの構造例を示す。ＣＯＤＥ番号記憶エリアには、サービス毎に固定値のＣＯＤＥ番号が記憶されている。そのＣＯＤＥ番号記憶エリアに記憶されているＣＯＤＥ番号は、キュー管理されており、格納されているＣＯＤＥ番号を割り当てた場合、割り当てたＣＯＤＥ番号が格納されていたエリアには、使用中が格納されることになる。ＣＯＤＥ番号を割り当てる際は、使用中でないＣＯＤＥ番号のサーチ（検索）を行い、未使用なものが見つかった場合に、そのＣＯＤＥ番号の割り当てを行う。割り当てたＣＯＤＥ番号は、ＣＯＤＥ番号記憶エリアに使用中をメモしておく。また、未使用のＣＯＤＥ番号が存在しなかった場合は、無線リソースの割り当てを不可能としている。
【０００４】
図４に記した状態は、ＣＯＤＥ番号＃０とＣＯＤＥ番号＃１とが、すでに割り当てられたため使用中となっている状態を示している。この場合、次にＣＯＤＥ番号を割り当てる際は、ＣＯＤＥ番号＃０からサーチを行い、未使用となっているＣＯＤＥ番号＃２を探しあてなくてはならない。
【０００５】
この従来の無線リソースの割り当てでは次のような問題点があった。まず第一の問題点は、未使用なＣＯＤＥ番号をサーチするため、ＣＯＤＥ番号記憶エリアに記憶されているＣＯＤＥ番号の数が多く、使用中のＣＯＤＥ番号の数が多いほど、未使用のＣＯＤＥ番号を探しあてるまでのサーチ回数が増える為、処理時間がかかってしまうことである。第二の問題点は、有限であるＣＯＤＥ番号を固定値で管理しているため、数に制限があり、ＣＯＤＥ番号という資源を有効利用できていないことである。
【０００６】
無線リソースとしてのＣＯＤＥ（符号）は、伝送レート（あるいは拡散率）に対応した多段階層の２分岐木構造（コードツリー）を成している。ある階層のＣＯＤＥ番号を割り当てると、そのＣＯＤＥ番号の直系の上位階層及び下位階層の各ＣＯＤＥ番号は新たな割り当てが不可となる。このため、階層ごとの各ＣＯＤＥ番号の割り当て状況（未割り当て状態、割り当て済み状態、直系の上位階層あるいは下位階層で割り当て済み状態）を管理する割り当てテーブルを設け、割り当て要求対象の階層の割り当てテーブルを若番順に検索して未割り当て状態のＣＯＤＥ番号を検出する技術が提案されている（例えば、特許文献１参照）。
【０００７】
【特許文献１】特開２００１−１６６４４号公報（第２−３頁、図２）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述したように、ある階層で、あるＣＯＤＥ番号を割り当てると、その直系の上位階層及び下位階層の各ＣＯＤＥ番号は新たな割り当てが不可となる。このため、特許文献１記載技術のように、割り当て要求対象の階層で、未使用状態のＣＯＤＥ番号を単に若番順に検索して割り当てると、その上位階層のＣＯＤＥ番号は、例え未割り当て状態であっても割り当て不可状態になってしまう。すなわち、リソース（ＣＯＤＥ番号）が無駄に使用される場合がある。
【０００９】
これに対して、割り当て要求対象の階層で未使用状態のＣＯＤＥ番号のうち、その上位階層のＣＯＤＥ番号が既に割り当て不可状態になっているＣＯＤＥ番号を選択すれば、リソース（ＣＯＤＥ番号）が無駄に使用されることはない。
【００１０】
本発明の目的は、ＣＯＤＥ番号割り当てにあたり、上述した従来技術の問題点を解決し、ＣＯＤＥ番号の割り当て時の処理時間を短縮するとともに、有限であるＣＯＤＥ番号を効率的に割り当て可能としたＣＤＭＡ移動通信システムのＣＯＤＥ割り当てシステム、及びその割り当て方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の請求項１に係るコード割り当て方法は、ＣＤＭＡ移動通信システムの移動機に対し無線リソースとしてのコードを割り当てる際、コードに対応したコード番号を伝送レートに対応した多段階層の２分岐木構造化し、割り当て中のコード番号とその直系の上位階層及び下位階層にあるすべてのコード番号との新たな割り当てを不可とするコードツリーを用いて割り当てるコード割り当て方法において、各コード番号対応のコード番号状態テーブルに、自コード番号の使用状況と、第一の子コード番号の使用状況と、第二の子コード番号の使用状況とを記録しておき、コードの割り当て要求発生時に、割り当て対象階層より１階層上位の各コード番号に対応する前記各コード番号状態テーブルを参照して、前記自コード番号の使用状況が直系の他のコード番号の割り当てによる使用不可状態で、かつ、前記第一及び第二のいずれか一方の子コード番号の使用状況が未使用状態のものを検索し、該当する未使用状態の子コード番号があれば、そのコード番号を割り当てる工程を有する。
【００１２】
本発明の請求項２に係るコード割り当て方法は、請求項１に係るコード割り当て方法において、各階層対応の割り当て優先テーブルに、自コード番号の使用状況が使用不可状態であるコード番号を記録しておき、前記コードの割り当て要求発生時に、割り当て対象階層より１階層上位の前記割り当て優先テーブルを参照して前記自コード番号の使用状況が使用不可状態のものを優先的に検索可能とした工程を有する。
【００１３】
本発明の請求項３に係るコード割り当て方法は、請求項２に係るコード割り当て方法において、コード番号を割り当てた後、当該コード番号を割り当てたことにより新たな割り当てが不可となる直系の上位階層及び下位階層のすべてのコード番号を算出し、前記割り当てたコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用中状態を、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の下位階層のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の１階層上位のコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用不可状態が記録されていなければ記録し、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用中状態を記録し、前記直系の２階層以上上位のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用不可状態が記録されていなければ記録し、前記コード番号状態テーブルの自コード番号の使用状況として新たに使用不可状態を記録したコード番号を、当該コード番号に対応する階層の割り当て優先テーブルに記録し、所定の優先順位にしたがってコード番号の並び替えを行う工程を有する。
【００１４】
本発明の請求項４に係るコード割り当てシステムは、ＣＤＭＡ移動通信システムの移動機に対し無線リソースとしてのコードを割り当てるコード割り当てシステムにおいて、コードに対応したコード番号を伝送レートに対応した多段階層の２分岐木構造化し、割り当て中のコード番号とその直系の上位階層及び下位階層にあるすべてコード番号との新たな割り当てを不可とするコードツリーと、各コード番号対応に、自コード番号の使用状況と、第一の子コード番号の使用状況と、第二の子コード番号の使用状況とを記録するコード番号状態テーブルと、コードの割り当て要求を受けると、割り当て対象階層より１階層上位の各コード番号に対応する前記各コード番号状態テーブルを参照して、前記自コード番号の使用状況が直系の他のコード番号の割り当てによる使用不可状態で、かつ、前記第一及び第二のいずれか一方の子コード番号の使用状況が未使用状態のものを検索し、該当する未使用状態の子コード番号があれば、そのコード番号を割り当てる手段とを有する。
【００１５】
本発明の請求項５に係るコード割り当てシステムは、請求項４に係るコード割り当てシステムにおいて、自コード番号の使用状況が使用不可状態であるコード番号を記録する各階層対応の割り当て優先テーブルを有し、前記コードの割り当て要求発生時に、割り当て対象階層より１階層上位の前記割り当て優先テーブルを参照して前記自コード番号の使用状況が使用不可状態のものを優先的に検索可能とした構成を有する。
【００１６】
本発明の請求項６に係るコード割り当てシステムは、請求項５に係るコード割り当てシステムにおいて、コード番号を割り当てた後、当該コード番号を割り当てたことにより新たな割り当てが不可となる直系の上位階層及び下位階層のすべてのコード番号を算出する手段と、前記割り当てたコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用中状態を、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の下位階層のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二の子コード番号の使用状況として使用不可状態を記録し、前記直系の１階層上位のコード番号に対応する前記コード番号状態テーブルに、自コード番号の使用状況として使用不可状態が記録されていなければ記録し、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用中状態を記録し、前記直系の２階層以上上位のコード番号に対応する前記各コード番号状態テーブルに、自コード番号の使用状況と、第一及び第二のいずれか関係する側の子コード番号の使用状況として使用不可状態が記録されていなければ記録する手段と、前記コード番号状態テーブルの自コード番号の使用状況として新たに使用不可状態を記録したコード番号を、当該コード番号に対応する階層の割り当て優先テーブルに記録し、所定の優先順位にしたがってコード番号の並び替えを行う手段とを有する。
【発明の効果】
【００１７】
本発明によれば、各コード番号対応のコード番号状態テーブルに、自コード番号の使用状況と、第一の子コード番号の使用状況と、第二の子コード番号の使用状況とを記録しておくので、親ＣＯＤＥ番号が使用不可状態になっていても自身が未使用状態である子ＣＯＤＥ番号の検索が容易にでき、当該子ＣＯＤＥ番号の割り当てにより新たに使用不可となる親ＣＯＤＥ番号の無駄な増加を防ぎ、無線資源（コード）の有効利用を行うことができる。
【００１８】
また、各階層対応の割り当て優先テーブルに、自コード番号の使用状況が使用不可状態であるコード番号を記録しておくので、親ＣＯＤＥ番号が使用不可状態であるものの検索を優先的に行うことができ、割り当ての時の判定処理時間を短縮することができる。
【発明を実施するための最良の形態】
【００１９】
まず本発明の概要を説明する。本発明では、ＣＤＭＡ方式の移動通信システムにおける基地局装置や基地局制御装置等の上位装置（コード割り当てシステム）において、移動機に対する無線リソース（ＣＯＤＥ、コード、符号）の割り当てを行うために、ＣＯＤＥ番号記憶エリアにＣＯＤＥ番号の固定値を記憶しておくことをやめ、コードに対応したコード番号（ＣＯＤＥ番号）を伝送レートに対応した多段階層の２分岐木構造化し、割り当て中のコード番号とその直系の上位階層及び下位階層にあるすべてコード番号との新たな割り当てを不可とするコードツリーを用いてＣＯＤＥ番号の割り当てを行う。その際、どのＣＯＤＥ番号を一番優先的にかつ資源の効率よく割り当てるかを知るために、ＣＯＤＥ番号を割り当てたことで使用不可となるＣＯＤＥ番号を記憶するための割り当て優先テーブルを新たに設ける。割り当て優先テーブルは、コードツリーの段（階層）毎に設けている。ＣＯＤＥ割り当て時は、割り当て優先テーブルを参照し、どのＣＯＤＥ番号が一番優先的にかつ資源の効率よく割り当てが可能かを判定し、ＣＯＤＥ割り当てを行う。なお、どの段数のＣＯＤＥ番号を割り当て対象とするかは、接続される呼の通信速度等による。
【００２０】
各段（階層）に設けられた割り当て優先テーブルには、次にＣＯＤＥ番号を割り当てる際にどのＣＯＤＥ番号を割り当てるべきかが記憶されている。呼（移動機の発呼、着呼）から接続要求を受けＣＯＤＥ番号を割り当てる際、このテーブルを参照することにより、次にどのＣＯＤＥ番号を割り当てるかが記憶されているため、即座に割り当てるべきＣＯＤＥ番号が判明する。このため、従来の技術のように固定値で管理されたＣＯＤＥ番号記憶エリアを未使用ＣＯＤＥ番号が存在するところまでサーチする処理が省略されるため、処理時間の短縮につながる。また、割り当て優先テーブルでは、すでに使用不可となったＣＯＤＥ番号と、その使用不可となったＣＯＤＥ番号の子（直系の１階層下の２つのＣＯＤＥ番号）に未使用のＣＯＤＥ番号が存在するか否かを記憶している。このため、子の階層のＣＯＤＥ番号の割り当ての際、既に親（直系の１階層上の１つのＣＯＤＥ番号）が使用不可となっているＣＯＤＥ番号を判別し割り当てることにより、新たに使用不可となるＣＯＤＥ番号の数が１つでも少なくなるように管理されている。そのため、ＣＯＤＥ番号という資源の有効利用にも役立つ。
【００２１】
より具体的に説明すると、本発明のＣＯＤＥ番号割り当て処理は、（１）ＣＯＤＥ番号検索処理、（２）ＣＯＤＥ番号割り当て不可算出処理、（３）優先テーブル書き込み処理、の３つの処理から構成されている。ＣＯＤＥ番号検索処理とは、優先テーブルを参照（検索）し、どのＣＯＤＥ番号が一番優先的にかつ資源の有効利用かを判定し、実際にＣＯＤＥ番号を割り当てる処理である。ＣＯＤＥ番号割り当て不可算出処理とは、（１）にてＣＯＤＥ番号を割り当てたことにより、使用不可になるコードツリー上の関連する他のＣＯＤＥ番号を算出し、コードツリー上に書き込む処理である。最後に優先テーブル書き込み処理は、（１）および（２）の処理により、使用不可となるＣＯＤＥ番号が新たに存在するため、その新たに存在したＣＯＤＥ番号を優先テーブルの書き込み内容に反映する処理である。
【００２２】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００２３】
図１は、コードツリーを示す図である。本発明の説明の前に、コードツリーについて説明を行う。最上位段（１段目）には、１つのＣＯＤＥ番号が置かれ、その１つ下の段（２段目）には、１段目のＣＯＤＥ番号を親とする２つの子のＣＯＤＥ番号が置かれる。さらにその１つ下の段（３段目）には、２段目の各ＣＯＤＥ番号（親）ごとに、２つの子のＣＯＤＥ番号が置かれる。このように段数が増えるにしたがって、親ＣＯＤＥ番号１つに対して子ＣＯＤＥ番号２つが置かれていく。
【００２４】
ＣＯＤＥ番号は、若番（コードツリーの左側）から割り当てられ、割り当てられたＣＯＤＥ番号＃Ｘの親（割り当てられたＣＯＤＥ番号＃Ｘが偶数ならば＃（Ｘ／２）、奇数ならば＃（（Ｘ−１）／２）が割り当て不可能となる。また、さらにその親の直系の親ＣＯＤＥ番号の割り当ても不可能となる。割り当てられたＣＯＤＥ番号の子（割り当てられたＣＯＤＥ番号＃Ｘに対する＃（２Ｘ）、＃（２Ｘ＋１）も使用不可能となり、さらにその子の直系の子は割り当て不可能となる。
【００２５】
上記に記したコードツリーの特徴を踏まえて、図１の＃５のＣＯＤＥ番号の割り当てを行ったとする。その時に、使用不可となるのは、その子であるＣＯＤＥ番号＃１０、ＣＯＤＥ番号＃１１、並びにその親であるＣＯＤＥ番号＃２も使用不可となり、更にその親のＣＯＤＥ番号＃１も使用不可となる。また、次に新たに３段目のＣＯＤＥ番号を割り当てる場合、割り当て可能なＣＯＤＥ番号がＣＯＤＥ番号＃４、ＣＯＤＥ番号＃６およびＣＯＤＥ番号＃７となるが、ＣＯＤＥ番号＃６およびＣＯＤＥ番号＃７のどちらかを割り当てた場合、新たに親であるＣＯＤＥ番号＃３が使用不可となってしまう。反対に、ＣＯＤＥ番号＃４を割り当てた場合、前回のＣＯＤＥ番号＃５を割り当てた時点で、ＣＯＤＥ番号＃２は使用不可となっているため、ＣＯＤＥ番号＃４を割り当てても、新たに使用不可となる親のＣＯＤＥ番号は存在しない。このような処理を行うことで、ＣＯＤＥ番号の資源有効利用を実現している。
【００２６】
図２は、本発明で新たに提案する割り当て優先テーブルを示す図である。図１に記しているコードツリーの各段（１段〜４段）にこの割り当て優先テーブル１０１〜１０４を設ける。また、図３は、コードツリーのＣＯＤＥ番号毎にもつＣＯＤＥ番号状態テーブル２００である。
【００２７】
図２に示す割り当て優先テーブル１０１〜１０４に、先にＣＯＤＥ番号が割り当てられたことにより、割り当てが不可能なＣＯＤＥ番号が記憶されている。図２に示す状態は、後に説明する例の時の構成図となっており、ＦＦとは初期状態のままであることを意味する。また、そのＣＯＤＥ番号は、若番から順に並べられる。若番から順に管理することにより、コードツリーの特徴である左側からＣＯＤＥ番号の割り当てを行うという特徴を実現する。また、割り当てが不可能なＣＯＤＥ番号を記憶するのは、割り当てが不可能なＣＯＤＥ番号の子には、割り当てが可能なＣＯＤＥ番号が存在するため、そのサーチを行うことにより資源の有効利用を実現するためである。
【００２８】
図３に示すＣＯＤＥ番号状態テーブル２００は、自使用状況（自ＣＯＤＥ番号の使用状況）、子０使用状況（第一の子ＣＯＤＥ番号（若番）の使用状況）ならびに子１使用状況（第二の子ＣＯＤＥ番号（老番）の使用状況）の３つの情報を記憶しておくテーブルである。各使用状況とは、未使用、使用中および使用不可の状態がある。未使用とは、該当ＣＯＤＥ番号が割り当てられていない状態を示す。使用中とは、該当ＣＯＤＥ番号が割り当てられている状態を示し、使用不可とは他のＣＯＤＥ番号（直系の上位階層及び下位階層のＣＯＤＥ番号）が割り当てられたことにより、使用できない状態を示す。
【００２９】
次に、本発明の動作を説明する。
【００３０】
まず、コード番号検索処理にて、割り当てるべきＣＯＤＥ番号が存在する段数（割り当て対象段数）の一段上位（−１）の段数の割り当て優先テーブルを取得する。ここで、割り当て対象段数−１の段数の割り当て優先テーブルを取得する理由は、段数−１（親の段数）のテーブルで使用不可のＣＯＤＥ番号を取得することで、そのＣＯＤＥ番号の子（すなわち、割り当て対象段数）に未使用のＣＯＤＥ番号がいないかサーチを行うためである。
【００３１】
取得した割り当て優先テーブルの、最初に記憶されているＣＯＤＥ番号（例えば、＃Ａ）を取得する。そして、対応するＣＯＤＥ番号＃ＡのＣＯＤＥ番号状態テーブルを取得し、子の使用状況を判定する。ＣＯＤＥ番号＃Ａの子に、未使用なＣＯＤＥ番号（例えば、＃Ａ０）が存在した場合は、そのＣＯＤＥ番号＃Ａ０の割り当てを行う。さらに、ＣＯＤＥ番号＃Ａ０のＣＯＤＥ番号状態テーブルを取得し、自使用状況に使用中を記憶する。また、未使用のＣＯＤＥ番号が存在しない場合は、取得したＣＯＤＥ番号＃Ａの次に記載されているＣＯＤＥ番号＃Ｂの子の検索を行う。このように、割り当て対象段数−１のＣＯＤＥ番号を参照し、検索することにより、検索回数が割り当て対象段数を検索する場合の１／２に減少することに加え、すでに使用不可となっているＣＯＤＥ番号のみの子のサーチを行えば良いので、処理時間の短縮が見込まれる。
【００３２】
ここで、ＣＯＤＥ番号を取得できたなら、次にＣＯＤＥ番号割り当て不可算出処理にて、新たにＣＯＤＥ番号を取得（割り当て）したことにより、割り当てが不可能となるＣＯＤＥ番号を算出し、コードツリー対応のＣＯＤＥ番号状態テーブルに記憶する。算出方法は、割り当てたＣＯＤＥ番号の複数段の子と親とのＣＯＤＥ番号を上記に示した計算式で算出する。すなわち、直系の上位階層及び下位階層すべてのＣＯＤＥ番号を算出する。
【００３３】
最後に、優先テーブル書き込み処理にて、今回ＣＯＤＥ番号を割り当てたことにより、上記処理で算出された使用不可になったＣＯＤＥ番号を割り当て優先テーブルに反映する。反映は、今回使用不可となったＣＯＤＥ番号とすでに割り当て優先テーブルに記憶されているＣＯＤＥ番号を比較し、若番から順に並べ替えを行う。
【００３４】
仮に、図１のコードツリーにて、３段目のいずれかのＣＯＤＥ番号を割り当てるとする。この時、すでにＣＯＤＥ番号＃５が割り当てられている状態とする。したがって、ＣＯＤＥ番号＃１，＃２，＃１０，＃１１は使用不可となっている。
【００３５】
この時の、コード番号検索処理では、まず２段目の割り当て優先テーブル１０２を取得する。図２に記したように、取得した割り当て優先テーブル１０２には、すでに使用不可となっているＣＯＤＥ番号＃２が記憶されているため、ＣＯＤＥ番号＃２のＣＯＤＥ番号状態テーブル２００を取得する。取得したＣＯＤＥ番号状態テーブルの子０使用状況と子１使用状況（ＣＯＤＥ番号＃４とＣＯＤＥ番号＃５との使用状況）の状態を判定する。ここでは、すでにＣＯＤＥ番号＃５が使用中、ＣＯＤＥ番号＃４が未使用となっているので、ＣＯＤＥ番号＃４の割り当てを行う。そして、ＣＯＤＥ番号＃４のＣＯＤＥ番号状態テーブル２００を取得し、自使用状況を使用中に設定する。
【００３６】
次に、ＣＯＤＥ番号割当不可算出処理にて、ＣＯＤＥ番号＃４を割り当てたことにより、新たに使用不可となったＣＯＤＥ番号を算出する。この場合、ＣＯＤＥ番号＃４の親であるＣＯＤＥ番号＃２と、さらにその親のＣＯＤＥ番号＃１とは既に使用不可となっている。したがって、ＣＯＤＥ番号＃４の子（子０及び子１）であるＣＯＤＥ番号＃８とＣＯＤＥ番号＃９とが、新たに使用不可となる。そこで、ＣＯＤＥ番号＃４のＣＯＤＥ番号状態テーブル２００を取得し、子０使用状況ならびに子１使用状況を使用不可に設定するとともに、ＣＯＤＥ番号＃８及びＣＯＤＥ番号＃９の各ＣＯＤＥ番号状態テーブル２００をそれぞれ取得し、自使用状況を使用不可に設定する。また、ＣＯＤＥ番号＃２のＣＯＤＥ番号状態テーブル２００の子０使用状況を使用中に設定する。
【００３７】
最後に、優先テーブル割り込み処理にて、割り当て優先テーブルに反映を行う。３段目の割り当て優先テーブル１０３には、既にＣＯＤＥ番号＃５が記憶されているが、新たにＣＯＤＥ番号＃４を記憶する。その際、ＣＯＤＥ番号＃４がＣＯＤＥ番号＃５より左（優先度高）になるように並び替える。４段目の割り当て優先テーブル１０４には、既にＣＯＤＥ番号＃１０及びＣＯＤＥ番号＃１１が記憶されているが、新たにＣＯＤＥ番号＃８及びＣＯＤＥ番号＃９を記憶する。その際、ＣＯＤＥ番号＃８，＃９がＣＯＤＥ番号＃１０，１１より左（優先度高）になるように並び替える。図２は、そのときの状態を示している。
【００３８】
この状態で、さらに３段目のいずれかのＣＯＤＥ番号を割り当てるとする。先ほどと同じように、まず２段目の割り当て優先テーブル１０２を取得する。図２に記したように、取得した割り当て優先テーブル１０２には、すでに使用不可となっているＣＯＤＥ番号＃２が記憶されているため、ＣＯＤＥ番号＃２のＣＯＤＥ番号状態テーブル２００を取得する。取得したＣＯＤＥ番号状態テーブルの子０使用状況と子１使用状況（ＣＯＤＥ番号＃４とＣＯＤＥ番号＃５との使用状況）の状態を判定する。このときには、すでにＣＯＤＥ番号＃４及び＃５とも使用中となっており、その他に使用不可となっているＣＯＤＥ番号もないので（このとき、ＣＯＤＥ番号＃３は使用不可となっていない）、割り当て優先テーブル１０２の参照を中止し、コードツリー及び各ＣＯＤＥ番号状態テーブル２００を直接参照した割り当てを行う。この場合は、２段目においてＣＯＤＥ番号＃２の次位であり、使用中や使用不可状態になっていないＣＯＤＥ番号＃３の子であるＣＯＤＥ番号＃６あるいは＃７（通常は若番の＃６）を割り当てる。
【００３９】
なお上述の説明では、各割り当て優先テーブル１０１〜１０４には、使用中を含めて使用不可となっているＣＯＤＥ番号のみを記憶するようにしているが、そのＣＯＤＥ番号の２つの子ＣＯＤＥ番号の使用状況も併せて記憶するようにしてもよい。このようにすることにより、親ＣＯＤＥ番号が使用不可状態であるが自身が未使用状態である子ＣＯＤＥ番号の検索をより高速に行うことができる。
【００４０】
ＣＯＤＥ番号の割り当てを解除するときは、上記に説明した処理と逆の処理を行う。例えば、図２に示す状態のときに、ＣＯＤＥ番号＃４の割り当てを解除するものとする。
【００４１】
まず、ＣＯＤＥ番号＃４のＣＯＤＥ番号状態テーブル２００の自使用状況、子０使用状況、及び子１使用状況を未使用に戻す。さらに、ＣＯＤＥ番号＃８，＃９の各ＣＯＤＥ番号状態テーブル２００の自使用状況を未使用に戻し、ＣＯＤＥ番号＃２のＣＯＤＥ番号状態テーブル２００の子０使用状況を未使用に戻す。また、割り当て優先テーブル１０３からＣＯＤＥ番号＃４を削除し、ＣＯＤＥ番号＃５を左端に移す。さらに、割り当て優先テーブル１０４から、ＣＯＤＥ番号＃８，＃９を削除し、ＣＯＤＥ番号＃１０，１１を左端に移す。
【図面の簡単な説明】
【００４２】
【図１】コードツリーを説明するための図である。
【図２】本発明の割り当て優先テーブルの構成例を示す図である。
【図３】本発明のＣＯＤＥ番号状態テーブルの構成例を示す図である。
【図４】従来技術におけるＣＯＤＥ番号記憶エリアの構成例を示す図である。
【符号の説明】
【００４３】
１０１〜１０４    割り当て優先テーブル
２００    ＣＯＤＥ番号状態テーブル
【図１】
2005109542.tif 000003
【図２】
2005109542.tif 000004
【図３】
2005109542.tif 000005
【図４】
2005109542.tif 000006