符号生成装置、通信装置、符号生成方法、及びプログラム
【課題】 効率的に符号を生成する符号生成方法を提供する。
【解決手段】 符号生成方法は、有界単調真理値表を参照して、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、有界単調真理値表を参照して、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとを有する。
【解決手段】 符号生成方法は、有界単調真理値表を参照して、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、有界単調真理値表を参照して、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号生成方法に関するものである。
【背景技術】
【０００２】
例えば、特許文献１には、チェビシェフ写像を用いて乱数列を生成する乱数列出力装置bが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−１４０８８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、上述した背景からなされたものであり、効率的に符号を生成する符号生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するために、本発明に係る符号生成装置は、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部とを有する。
【０００６】
好適には、有界単調真理値表を記録する真理値表記録部をさらに有し、前記符号生成部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列を昇順又は降順に生成し、前記限界値設定部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列の上限値又は下限値を設定する。
【０００７】
また、本発明の通信装置は、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と、前記符号生成部により生成された符号列を用いて、通信を行う通信部とを有する。
【０００８】
また、本発明の符号生成方法は、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとを有する。
【０００９】
また、本発明のプログラムは、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとをコンピュータに実行させる。
【発明の効果】
【００１０】
本発明によれば、効率的に符号を生成することができる。
【図面の簡単な説明】
【００１１】
【図１】黄金平均変換に関するマルコフ分割Pを例示する図である。
【図２】黄金平均変換のグラフＧを例示する図である。
【図３】最大辺数を有するＧの全域オイラー部分グラフＨを例示する図である。
【図４】離散化された黄金平均変換を例示する図である。
【図５】通信システム１のシステム構成を例示する図である。
【図６】符号生成プログラム５００の機能構成を例示する図である。
【発明を実施するための形態】
【００１２】
［背景］
電子計算機をインフラ基盤とする現代社会において、最大周期列の応用範囲は広大であり、暗号系、通信系、計算機科学系、経済（ファイナンス）系と多岐にわたる。最大周期列を生成するために、LFSR （線形フィードバックシフトレジスタ（linear feedback shift register））が通常用いられている。一方、一次元エルゴード的変換のカオス力学系におけるランダム性の観点から、離散化されたBernoulli変換に基づく系列が提案された。
後者はファミリーサイズ（系列の総数）という点で非常に優れている。例えば、長さ2nの二値系列に対して、前者の総数は2n/nよりずっと小さいが、de Bruijn系列の総数は2の（2n-1-n）乗であることが知られている。
【００１３】
本願の発明者は、これまでの研究において、離散化されたマルコフ変換を一般的に定義し、離散化されたマルコフ変換に基づく最大周期列の総数を与えるアルゴリズムを考案した。離散化されたマルコフ変換とは、変換から決定されるマルコフ分割に属する部分区間の置換であり、超離散系の例とみなすことができる。この観点から、de Bruijn系列は単に離散化マルコフ変換から得られる最大周期列の特別な例である。実際、それらは、離散化二進変換の部分族に基づく最大周期列である。
マルコフ変換が与えられると、可算個の離散化マルコフ変換を得る。離散化マルコフ変換を固定すれば、本発明者のアルゴリズムにより、離散化変換に基づく最大周期列の総数を計算することができる。
最大周期列の総数がわかれば、それらを全て生成するような、アルゴリズムを与えるという問題を考察するのは自然であろう。この問題は単に数学的問題として興味深いだけでなく、実用的にも重要である。というのは、先に述べたように、最大周期列の応用は広範囲にわたるからである。しかしながら、この問題は難問である。実際、de Bruijn系列の場合、単一の系列もしくはいくつかの系列を生成するアルゴリズムは数多く提案されているものの、系列を全て生成するアルゴリズムは数えられる位しか存在しない。
最近、いくつかの最大周期列が既に与えられたという仮定の下、系列を決定する置換の互換によって、r = 2の場合にde Bruijn 系列を含む、離散化されたr（≧ 2）進変換に基づき、相対的に多くの系列を生成するアルゴリズムが提案された。これは、全てではないものの、相対的に多くの系列を効率的に生成する、興味深いアルゴリズムである。
【００１４】
本発明者は、最大周期列を全て生成するようなアルゴリズムを与えるという問題に取り組んだ。そのために、区分的単調増加マルコフ変換を定義し、離散化された区分的単調増加マルコフ変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与える。
区分的単調増加マルコフ変換は、既約かつ非周期的マルコフ変換の集合の部分集合である。しかしながら、それは、Bernoulli変換だけでなく、黄金平均変換、Kalmanのマルコフ変換、および、r（≧ 2）方有尾シフト変換（r（≧ 2）-way tailed shift transformations）を含むので、実用的に十分広いクラスである。
現在、最大周期列の総数を計算する既知のアルゴリズムの計算量は、指数関数的オーダである。したがって、最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、本発明に係るアルゴリズムは効率的である。
さらに、de Bruijn系列は離散化された区分的単調増加マルコフ変換から得られる最大周期列に含まれるので、本発明に係る有界単調真理値表アルゴリズムを全てのde Bruijn系列の生成に応用することができる。
【００１５】
de Bruijn系列の生成に関して、本発明者は、離散化されたマルコフ変換を定義し、離散化されたマルコフ変換に基づく最大周期列の総数を与えるアルゴリズムを発見した。まず初めに、その概略を述べる。
既約かつ非周期的マルコフ変換Tに対して、Tに関するマルコフ分割Pが与えられる。このとき、各部分区間I∈Pに一つの辺a（I）が対応し、辺a（I）の集合Aを得る。Pの要素の各順序対（I，J）に対して、a（I）からa（J）へ隣接する一つの頂点v（I、 J）が許されるのは丁度J⊂T|I（I）のときである。これより、マルコフ連鎖を表現する有向グラフG = （V，A）を得る。一般に、得られたグラフはオイラーグラフではない。H=（V，B）は、最大辺数を有するGの全域オイラー部分グラフであるとする。既約かつ非周期的マルコフ変換を考えているので、頂点集合VはGからH への変形に対して不変である。
上に述べた、PとAの間の一対一対応の下で、Bに対応する分割Qを得る。このとき、離散化されたマルコフ変換^Tは、全てのI∈Qに対して^T（I）⊂T|I （I）を満たす、置換^T ：Q→Qとして定義される。結局、離散化されたマルコフ変換から生成される最大周期列の総数は、Hのアドミタンス行列Cの余因子C11により与えられる。
この定義により、de Bruijn系列は、離散化されたマルコフ変換から得られる最大周期列の特別な例となる。
【００１６】
次に、離散化された黄金平均変換の例を述べる。図１に黄金平均変換に関するマルコフ分割Pの例を示す。各分割は長さ５のブロックにより表現される。
P=｛00000，00001，00010，00100，00101，01000，01001，01010，10000，10001，10010，10100，10101｝
０と１をそれぞれ区間[0、 1/β）と[1/β、 1]に同一視することにより、各二値ブロックa1a2・・・a5は筒集合｛x∈[0、 1]：Ti-1（x）∈ai、1 ≦ i ≦ 5｝に対応することに注意する。ここで、βは黄金平均数（1 +√5）/2であり、Tは黄金平均変換である。マルコフ分割P が与えられると、黄金平均変換のグラフ表現Gが、図２のように、直ちに得られる。Pに属する各分割はGに属する辺に対応する。図２のGはオイラーグラフでないことに注意されたい。辺10001と10101を消去することにより、図３に描かれた様に、最大辺数を有するGの全域オイラー部分グラフHを得る。Hの辺集合は分割Q = ｛00000、 00001、 00010、 00100、 00101、 01000、 01001、 01010、 10000、 10010、 10100｝を定める。辺の隣接に随伴する、Qの置換により、離散化された黄金平均変換が定義される。ここで、一般に、Qの置換全体の集合に比べると、少ない量だけしか離散化されたマルコフ変換を与えることができないに注意されたい。Hの11×11アドミタンス行列Cの余因子C11を計算することにより、離散化された黄金平均変換から得られる最大周期列は二であることがわかる。ここで行列の大きさ11はQの濃度に由来する。離散化された黄金平均変換の例を図４に示す。図４において陰をつけた四角形がQの置換の一対一対応を定める。この場合、最大周期列00000100101を生成する。
【００１７】
次に、全てのde Bruijn系列を生成する、比較例のアルゴリズムを検討する。
各正の整数nに対して、長さ2nのde Bruijn系列が丁度2の（2n-1-n）乗個存在する。de Bruijn による、この事実の証明の最も重要な部分は、グラフGnとGn+1の間の次の関係に気付いたことにある。
Gn+1 = G*n・・・（1）
ここで、Gn=（Vn，An）（n > 1）はVn=｛0，1｝n-1とAn =｛0，1｝nを有するde Bruijnグラフである。辺a1a2・・・an∈Aはa1a2・・・an-1からa2a3・・・anへ隣接する。G*nはGnの辺有向グラフである。
上記関係（1）を用いた、全てのde Bruijn系列を生成するアルゴリズムが提案されている。しかしながら、このアルゴリズムは、長さ2nの全てのde Bruijn系列を生成するために、2の2n-2乗ビットの初期記憶を常に必要とする。これは、要求される記憶量の観点から非常に高価である。
また、残念ながら、上記のような関係（1）は、一般に成立しないので、このアルゴリズムを一般の離散化されたマルコフ変換から得られる最大周期列の生成に応用することはできない。実際、離散化された黄金平均変換に対して、上記関係（1）が成り立たないことが示されている。
これまでのところ、本発明者が知り得る限り、全てのde Bruijn系列を生成するアルゴリズムはそれ程知られていない。また、それらはde Bruijn系列の性質に強く依存する。したがって、一般の離散化されたマルコフ変換から得られる最大周期列の生成に直接適用することはできない。ゆえに、本願で提案するアルゴリズムは新規であると同時に自明でない。
【００１８】
次に、本発明に係る、離散化されたマルコフ変換の集合における距離関数を説明する。説明の便宜上、k（?2）アルファベットを二値アルファベット｛0，1｝に制限する。この簡単化は、k＞2の場合に対して、k！個の場合を数え上げることを除いて、数学的処理を本質的に変えない。
与えられた離散化マルコフ変換に基づき、全ての最大周期列を生成するためには、最大辺数を有するGの全域オイラー部分グラフH =（V，B）から始めることができる。
Hはオイラーグラフであるので、連結であり、すべての頂点は偶数次数を持つ。これより、二値アルファベットの場合、各頂点の次数は2または4である。V=U∪Wは直和であるとする。ここで、Uは次数2の頂点の集合であり、Wは次数2の頂点の集合である。
U=｛u1，u2，・・・，u♯U｝およびW=｛w1，w2，・・・，w♯W｝とする。ここで、集合Aに対して、♯AはAの濃度を表す。♯V =♯U+♯Wに注意する。
表現を簡明にするために、各頂点は、二値ブロックにより、uj = a1（j）a2（j）・・・a|uj|（j）∈｛0，1｝|uj|、1 ≦ j ≦ ♯Uおよびwi = b1（i）b2（i）・・・b|wi|（i）∈｛0，1｝|wi|、1 ≦ i≦♯Wと表現されるとする。ブロックwに対して、|w|はwの長さを表す。0および1をそれぞれ区間[0，x1）および[x1，1]と同一して、各二値ブロックujまたはwiはそれぞれ筒集合｛x∈[0，1] ：Ti-1（x）∈a m（j）、1≦m ≦|uj|｝または｛x∈[0，1] ：Ti-1（x）∈b m（i）、1 ≦m≦|wi|｝に対応する。ここで、｛[0，x1）、 [x1，1]｝は、離散化される変換T（後述）の分割である。ただし、この仮定が常に成立するわけではないことが知られている。仮定が成立しない場合は表記が煩雑になるだけであり、任意の既約かつ非周期的マルコフ変換に対して、下記のオイラーグラフの真理値表を定義することができる。
各頂点ujは次数2を持つので、ujはBに属する二つの辺a（j）ujとujb（j）を一意に決定する。ここで、a（j），b（j）∈｛0，1｝。
今、Hにおいて、二つの辺0wiと1wiはwiで終端となる。一方、wi0とwi1はwiで開始する。経路が0wi0を許すとき、これはその経路が1wi1を許す（すなわち、その経路が0wi0・・・1wi1を許す）か、または他の経路が1wi1を許す（すなわち、その経路が1wi1を許さない）ときであり、ti =0と置く。一方、経路が0wi1を許すとき、これはその経路が1wi0を許す（すなわち、その経路が0wi1・・・1wi0を許す）か、または他の経路が1wi0を許す（すなわち、その経路が1wi0を許さない）ときであり、ti =1と置く。これより、♯W次ベクトルt=（t1，t2，・・・，t♯W）∈｛0，1｝♯Wを得る。これをHの真理値表（truth table）と呼ぶ。
【００１９】
第１の具体例としては、de BruijnグラフGn =（｛0，1｝n-1，｛0，1｝n）（n >1）の真理値表は（t1，t2，・・・，tn-1）∈｛0，1｝n-1で与えられる。
第２の具体例としては、離散化された黄金平均変換に随伴する図３のグラフHの真理値表は（t1，t2，t3）∈｛0，1｝3で与えられる。
Hの真理値表tにより、置換σt : B → B が
で定義される。これは、離散化マルコフ変換を表現する。a∈｛0，1｝に対して、<a>はaの二値補数を表す。すなわち、<0> =1および<1> = 0。
次に、離散化マルコフ変換の集合における距離関数dを、t，t'∈｛0，1｝]Wに対して、d（σt，σt'）= dH（t，t'）で定義する。ここで、dHはtとtのHamming距離、すなわち、tとtの異なる要素数である。
次の補題により、提案するアルゴリズムにおける次のステップが定まる：
（補題1）σtは、最大周期列を生成する離散化マルコフ変換である、すなわち、σtそれ自身が全巡回置換（full cycle）であるとする。このとき、d（σt，σt'）=1を満たす任意の離散化マルコフ変換σt'は全巡回置換になり得ない。
この補題１は、提案するアルゴリズムのステップ３（Step 3）において、線形オーダの効率的な計算を実行する指針を与える。
【００２０】
次に、本出願において、wiを非負整数に対する底2を用いた位取り表記と見做し、w1 < w2<・・・< w♯Wを仮定する。
これまで、離散化される変換として、一般の既約かつ非周期的マルコフ変換Tを考えてきた。以下の説明においては、離散化される変換Tに対して、次の単調性を要求する。
[0，1]のある分割0 = x0 < x1 <・・・< x k =1が存在して、各整数i = 1，・・・，kに対して、Tの区間[xi-1，xi）への制限は単調増加関数である。
既約かつ非周期的マルコフ変換Tがこの条件を満たすとき、Tを区分的単調増加マルコフ変換（piecewisemonotone-increasing Markov transformation）と呼ぶ。以下、離散化される変換は、その様な単調性を有するとする。ここで、区分的単調増加マルコフ変換は実用的に十分広いクラスのマルコフ変換を含むことを強調しておく。上記で述べたように、それは、Bernoulli変換だけでなく、黄金平均変換、Kalmanのマルコフ変換、および、k（? 2）-方有尾シフト変換を含む。説明の便宜上、分割の数kはアルファベットの大きさkに対応すると仮定する。先の節の様に、簡単のため、k = 2の場合を考える。
なお、主要ステップに進む前に、もう一つの準備が必要である。
ステップ０（Step 0） i =1，2，・・・，♯Wに対して、辺0wiが0wi = wi0を満たすならば、ti =1と置く。また、辺1wiが1wi = wi1を満たすならば、ti = 0と置く。これにより、単一の辺の巡回置換が予め避けられる。離散化される変換は既約かつ非周期的であるので、いずれかが少なくとも一度起こるが、両方は高々一度しか起こらない。
以下、その様なtiを固定する。tからその様な固定されたtiを全て除去し、tiの残りの成分の座標の番号を付け直した後、（♯W−1）次ベクトルまたは（♯W−2）次ベクトルを得る。それを~t =（~t1，・・・，~tW）で表す。~tを縮約真理値表（contracted truth table）と呼ぶ。定義により、一対一対応γ： t→~tおよびγ-1：~t→tを得る。
【００２１】
具体例としては、de BruijnグラフGn=（｛0，1｝n-1，｛0，1｝n）（n >1）の縮約真理値表は、（~t1，~t2，・・・，~tn-3）（∈｛0，1｝n-3）で与えられる。これは、真理値表（1，~t1， ~t2，・・・，~tn-3，0）に対応する。
他の具体例としては、離散化された黄金平均変換に随伴する図３のグラフHの縮約真理値表は、（~t1，~t2）（∈｛0，1｝2）で与えられる。これは、真理値表（1，~t1，~t2）に対応する。
【００２２】
次のサブルーチンは、本実施形態のアルゴリズムにおいて、重要な役割を果たす。
ステップＢ１（Step B1） m（1 < m ≦ ♯U+2♯W=♯B）は、
σtm（0w1）= 0w1
を満たす最小の周期であるとする。各i（1 ≦ i ≦♯W）に対して、n（1 ≦ n ≦ m ≦ ♯B）が存在して、σtn（0w1）=0wi、を満たすならば、ri =1と置く。そうでないならば、ri=0と置く。これより、r =（r1，・・・，r♯W） を得る。全てのi（1 ≦ i ≦♯W）に対してri =1ならば、全巡回置換σtを得、元に戻る。そうでないならば、ステップＢ２（Step B2）へ進む。
ステップＢ２（Step B2） ~r=γ（r）および~r =（~r1，・・・，~rW）と置く。R0 = max｛i：~ri = 0，1 ≦ i ≦W｝およびR1 =max｛i：~ri =1，1≦ i≦W｝とする。n（1 ≦ n ≦ m ≦♯B）が存在して、σtn（0w1）=1w♯Wを満たすならば、t=γ-1（~t1，・・・，~tR0-1，<~tR0>，~tR0+1，・・・，~tW）と置き、ステップＢ１（Step B1）へ進む。そうでないならば、t =γ-1（~t1，・・・，~tR1-1，<~tR1>，~tR1+1，・・・，~tW）と置き、ステップＢ１（Step B1）へ進む。
以下、~tを非負整数に対する底2を用いた位取り表記と見做す。次の補題は提案するアルゴリズムの本質的な構成要素である。
【００２３】
（補題２）~T=｛~t∈｛0，1｝W：σt=σγ-1（~t）は全巡回置換である｝とする。~t=（0，・・・，0｝（0がＷ個）として、tをステップＢ１に入力するならば、その縮約真理値表~tが~Tの下界であるような、全巡回置換σtを得る。一方、~t=（1，・・・，1｝（１がW個）として、tをステップＢ１に入力するならば、その縮約真理値表~tが~Tの上界であるような、全巡回置換σtを得る。
上記した様に、各正の整数nに対して、（2の2n-1-n乗）個の長さ2nのde Bruijn系列が存在する。これより、全てのde Bruijn系列を生成する際、生成された相異なる系列の個数を確認することによって、いつ符号生成アルゴリズムを停止させるかを判定する条件を直ちに得る。一方、離散化されたマルコフ変換から最大周期列を生成する際、それ程単純ではない。同様に、最大周期列の総数を知りたい場合、Hのアドミタンス行列Cの余因子C11を計算する必要がある。
N×N行列に対して、余因子を計算するのは、漸近的にO（（N − 1）2.376）の複雑度であることが知られている。離散化マルコフ変換に対して、N=♯Bは底2の指数関数オーダであることに注意する。
上記（補題2）は、最大周期列の総数を計算することなく、本実施形態の符号生成アルゴリズムが停止することを保証するので、非常に有用である。
【００２４】
以上で、主要ステップに進む準備が整った。本実施形態のアルゴリズムの主要ステップは、以下である。
ステップ１（Step 1）（上限値の計算）
tを~t =（1，・・・・，1｝（W個の１）として、ステップＢ１に進む。ステップＢ１から戻って来た後、σtを出力し、υ=（υ1，・・・，υW）=~tと置く。次に、ステップ２に進む。
【００２５】
ステップ２（Step 2）
tを~t=（0，・・・，0）（W個の０）としてステップＢ１に進む。ステップＢ１から戻って来た後、σtを出力し、~t（1）=（~t1（1），・・・，~t W（1））=~tと置く。i=1と置いてステップ３に進む。
【００２６】
ステップ３（Step 3）
~t W（i）= 0ならば、~t =~t（i）+11 と置く。~tW（i）=1ならば、~t =~t（i）+1と置く。ここで、加法は、~tと~t（i）を非負整数に対する底2を用いた位取り表記と見做した、二進数系における演算である。次に、ステップＢ１に進む。ステップＢ１から戻って来た後、ステップ４に進む。
【００２７】
ステップ４（Step 4）
~t <υならば、σtを出力する。~t（i+1）=（~t1（i+1），・・・，~t W（i+1））=~tと置く。i = i + 1 と置いてステップ３に進む。~t =υならば、符号生成処理を停止させる。
【００２８】
なお、次の性質により、本実施形態のアルゴリズムを有界単調真理値表（bounded monotone truth-table）アルゴリズムと呼ぶ。結果として得られる縮約真理値表の列は有界単調増加である。つまり、~t（1）< ~t（2）<・・・≦ υ（上限値）
【００２９】
次に、全てのDe Bruijn系列生成への応用を説明する。
本実施形態のアルゴリズムが正しく動作することを実証するために、ここでは、アルゴリズムを、長さ2nのDe Bruijn系列を全て、（2の2n-1-n乗）個生成するのに応用する。その前に、離散化マルコフ変換に基づく全ての最大周期列を生成する簡単な例を手短かに述べる。
【００３０】
上記具体例で見たように、離散化された黄金平均変換に随伴する図３のグラフHの縮約真理値表は、（~t1，~t2）（∈｛0，1｝2）で与えられる。これは、真理値表（1，~t1，~t2）に対応する。以下、二値ブロック~t1~t2を二値ベクトル（~t1，~t2）と見做す。
上記サブルーチンのステップＢ１及びステップＢ２を用いて、ベクトル11により、上界υ=10を得る。同様に、初期ベクトル00により、下界~t（1）=01を得る。このとき、本実施形態の符号生成アルゴリズムは、次の様に、縮約真理値表の有界単調増加列を生成する。
~t（1）= 01<10=υ
これは、上で考察した離散化黄金平均変換に基づく、相異なる二つの最大周期列00000100101および00000101001を与える。
【００３１】
次に、全de Bruijn系列の生成を考える。
n = 4の場合、長さ24のde Bruijn系列は全部で16個存在する。単一の辺の巡回置換を予め避けるため、その真理値表を（1，t2，t3，・・・，t7，0）∈｛0，1｝8で定義する。これより、縮約真理値表~t =（~t1，・・・，~t6）を得る。以下、二値ブロック~t1・・・~t6を二値ベクトル（~t1，・・・，~t6）と見做す。
サブルーチンのステップB1及びB2を用いて、ベクトル1・・・１（１が６個）により、上界（上限値）υ=111110を得る。同様に、初期ベクトル０・・・０（０が６個）により、下界（下限値）~t（1）=000111を得る。このとき、本実施形態のアルゴリズムは、次の様に、縮約真理値表の有界単調増加列を生成する。
~t（1）= 000111 < 001110 < 010011 < 010110 < 010101 < 011010 < 011100 < 011111
< 100011 < 101010 < 110001 < 110010 < 110111 < 111000 < 111011 < 111110 = υ
これは、相異なる１６個のde Bruijn系列を与える。
【００３２】
以上説明したように、位相シフトフリーM-相スペクトル拡散符号を実現する区分的線形マルコフ変換を含む、区分的単調増加マルコフ変換を考え、それらが離散化された変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えた。提案したアルゴリズムは、最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、効率的である。また、１優先関数を使用しないので、計算時間と記憶量の観点から、１優先関数を使用するアルゴリズムに比べて経済的である。本実施形態のアルゴリズムを全てのde Bruijn系列の生成に応用できる。
【００３３】
最後に、上記の最大周期列を用いた通信システムを説明する。
図５は、通信システム１のシステム構成を例示する図である。
図５に例示するように、通信システム１は、複数の携帯電話１０Ａ〜１０Ｎと、基地局２０とを含む。通信システム１には、複数の基地局２０が存在し、各基地局２０に、少なくとも１つの携帯電話１０が収容できる。１つの基地局２０が収容できる携帯電話１０の数は、最大周期列の総数による。
携帯電話１０は、符号拡散方式で音声通信及びデータ通信を行う携帯端末である。
基地局２０は、符号拡散方式で、各携帯電話１０と通信し、携帯電話間の通信を中継する。その際、基地局２０は、上記有界単調真理値表アルゴリズムにより生成された符号列を、各携帯電話１０に割り当てる。
【００３４】
図６は、基地局２０のコンピュータにインストールされた符号生成プログラム５００の機能構成を例示する図である。
図６に例示するように、符号生成プログラム５００は、テーブル生成部５０５、テーブル参照部５１０、符号生成部５１５、限界値設定部５２０、終了判定部５２５、符号割当部５３０、及び通信部５３５を有する。
【００３５】
テーブル生成部５０５は、上述した有界単調真理値表を生成し、真理値表格納部１００に格納する。なお、真理値表格納部１００は、メモリ又はＨＤＤなどにより構成された記録装置である。
テーブル参照部５１０は、符号生成部５１５からの指示に応じて、真理値表格納部１００に格納されている有界単調真理値表を参照し、参照結果を符号生成部５１５に返す。
符号生成部５１５は、テーブル参照部５１０から入力された有界単調真理値表の参照結果に基づいて、符号列を昇順または降順に生成する。
【００３６】
限界値設定部５２０は、テーブル参照部５１０に有界単調真理値表を参照させて、最大周期列の上限値及び下限値を設定し、設定された上限値及び下限値の一方を初期値として符号生成部５１５に出力し、上限値及び下限値の他方を終了値として終了判定部５２５に出力する。
終了判定部５２５は、限界値設定部５２０により設定された限界値（上限値又は下限値）と、符号生成部５１５により生成された符号列とに基づいて、符号生成処理を終了すべきか否かを判定する。本例の終了判定部５２５は、符号生成部５１５から入力される符号列が、限界値設定部５２０により設定した限界値と一致する場合に、符号生成処理を終了させ、これ以外の場合には、符号生成部５１５に対して符号生成処理を継続させる。
符号割当部５３０は、携帯電話１０からの要求に応じて、符号生成部５１５により生成された符号列を、携帯電話１０に割り当てる。
通信部５３５は、符号割当部５３０により各携帯電話１０に割り当てられた符号列を用いて、それぞれの携帯電話１０と通信を行う。
【符号の説明】
【００３７】
１・・・通信システム
１０・・・携帯電話
２０・・・基地局
５・・・符号生成プログラム
【技術分野】
【０００１】
本発明は、符号生成方法に関するものである。
【背景技術】
【０００２】
例えば、特許文献１には、チェビシェフ写像を用いて乱数列を生成する乱数列出力装置bが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−１４０８８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、上述した背景からなされたものであり、効率的に符号を生成する符号生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するために、本発明に係る符号生成装置は、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部とを有する。
【０００６】
好適には、有界単調真理値表を記録する真理値表記録部をさらに有し、前記符号生成部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列を昇順又は降順に生成し、前記限界値設定部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列の上限値又は下限値を設定する。
【０００７】
また、本発明の通信装置は、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と、前記符号生成部により生成された符号列を用いて、通信を行う通信部とを有する。
【０００８】
また、本発明の符号生成方法は、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとを有する。
【０００９】
また、本発明のプログラムは、Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップとをコンピュータに実行させる。
【発明の効果】
【００１０】
本発明によれば、効率的に符号を生成することができる。
【図面の簡単な説明】
【００１１】
【図１】黄金平均変換に関するマルコフ分割Pを例示する図である。
【図２】黄金平均変換のグラフＧを例示する図である。
【図３】最大辺数を有するＧの全域オイラー部分グラフＨを例示する図である。
【図４】離散化された黄金平均変換を例示する図である。
【図５】通信システム１のシステム構成を例示する図である。
【図６】符号生成プログラム５００の機能構成を例示する図である。
【発明を実施するための形態】
【００１２】
［背景］
電子計算機をインフラ基盤とする現代社会において、最大周期列の応用範囲は広大であり、暗号系、通信系、計算機科学系、経済（ファイナンス）系と多岐にわたる。最大周期列を生成するために、LFSR （線形フィードバックシフトレジスタ（linear feedback shift register））が通常用いられている。一方、一次元エルゴード的変換のカオス力学系におけるランダム性の観点から、離散化されたBernoulli変換に基づく系列が提案された。
後者はファミリーサイズ（系列の総数）という点で非常に優れている。例えば、長さ2nの二値系列に対して、前者の総数は2n/nよりずっと小さいが、de Bruijn系列の総数は2の（2n-1-n）乗であることが知られている。
【００１３】
本願の発明者は、これまでの研究において、離散化されたマルコフ変換を一般的に定義し、離散化されたマルコフ変換に基づく最大周期列の総数を与えるアルゴリズムを考案した。離散化されたマルコフ変換とは、変換から決定されるマルコフ分割に属する部分区間の置換であり、超離散系の例とみなすことができる。この観点から、de Bruijn系列は単に離散化マルコフ変換から得られる最大周期列の特別な例である。実際、それらは、離散化二進変換の部分族に基づく最大周期列である。
マルコフ変換が与えられると、可算個の離散化マルコフ変換を得る。離散化マルコフ変換を固定すれば、本発明者のアルゴリズムにより、離散化変換に基づく最大周期列の総数を計算することができる。
最大周期列の総数がわかれば、それらを全て生成するような、アルゴリズムを与えるという問題を考察するのは自然であろう。この問題は単に数学的問題として興味深いだけでなく、実用的にも重要である。というのは、先に述べたように、最大周期列の応用は広範囲にわたるからである。しかしながら、この問題は難問である。実際、de Bruijn系列の場合、単一の系列もしくはいくつかの系列を生成するアルゴリズムは数多く提案されているものの、系列を全て生成するアルゴリズムは数えられる位しか存在しない。
最近、いくつかの最大周期列が既に与えられたという仮定の下、系列を決定する置換の互換によって、r = 2の場合にde Bruijn 系列を含む、離散化されたr（≧ 2）進変換に基づき、相対的に多くの系列を生成するアルゴリズムが提案された。これは、全てではないものの、相対的に多くの系列を効率的に生成する、興味深いアルゴリズムである。
【００１４】
本発明者は、最大周期列を全て生成するようなアルゴリズムを与えるという問題に取り組んだ。そのために、区分的単調増加マルコフ変換を定義し、離散化された区分的単調増加マルコフ変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与える。
区分的単調増加マルコフ変換は、既約かつ非周期的マルコフ変換の集合の部分集合である。しかしながら、それは、Bernoulli変換だけでなく、黄金平均変換、Kalmanのマルコフ変換、および、r（≧ 2）方有尾シフト変換（r（≧ 2）-way tailed shift transformations）を含むので、実用的に十分広いクラスである。
現在、最大周期列の総数を計算する既知のアルゴリズムの計算量は、指数関数的オーダである。したがって、最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、本発明に係るアルゴリズムは効率的である。
さらに、de Bruijn系列は離散化された区分的単調増加マルコフ変換から得られる最大周期列に含まれるので、本発明に係る有界単調真理値表アルゴリズムを全てのde Bruijn系列の生成に応用することができる。
【００１５】
de Bruijn系列の生成に関して、本発明者は、離散化されたマルコフ変換を定義し、離散化されたマルコフ変換に基づく最大周期列の総数を与えるアルゴリズムを発見した。まず初めに、その概略を述べる。
既約かつ非周期的マルコフ変換Tに対して、Tに関するマルコフ分割Pが与えられる。このとき、各部分区間I∈Pに一つの辺a（I）が対応し、辺a（I）の集合Aを得る。Pの要素の各順序対（I，J）に対して、a（I）からa（J）へ隣接する一つの頂点v（I、 J）が許されるのは丁度J⊂T|I（I）のときである。これより、マルコフ連鎖を表現する有向グラフG = （V，A）を得る。一般に、得られたグラフはオイラーグラフではない。H=（V，B）は、最大辺数を有するGの全域オイラー部分グラフであるとする。既約かつ非周期的マルコフ変換を考えているので、頂点集合VはGからH への変形に対して不変である。
上に述べた、PとAの間の一対一対応の下で、Bに対応する分割Qを得る。このとき、離散化されたマルコフ変換^Tは、全てのI∈Qに対して^T（I）⊂T|I （I）を満たす、置換^T ：Q→Qとして定義される。結局、離散化されたマルコフ変換から生成される最大周期列の総数は、Hのアドミタンス行列Cの余因子C11により与えられる。
この定義により、de Bruijn系列は、離散化されたマルコフ変換から得られる最大周期列の特別な例となる。
【００１６】
次に、離散化された黄金平均変換の例を述べる。図１に黄金平均変換に関するマルコフ分割Pの例を示す。各分割は長さ５のブロックにより表現される。
P=｛00000，00001，00010，00100，00101，01000，01001，01010，10000，10001，10010，10100，10101｝
０と１をそれぞれ区間[0、 1/β）と[1/β、 1]に同一視することにより、各二値ブロックa1a2・・・a5は筒集合｛x∈[0、 1]：Ti-1（x）∈ai、1 ≦ i ≦ 5｝に対応することに注意する。ここで、βは黄金平均数（1 +√5）/2であり、Tは黄金平均変換である。マルコフ分割P が与えられると、黄金平均変換のグラフ表現Gが、図２のように、直ちに得られる。Pに属する各分割はGに属する辺に対応する。図２のGはオイラーグラフでないことに注意されたい。辺10001と10101を消去することにより、図３に描かれた様に、最大辺数を有するGの全域オイラー部分グラフHを得る。Hの辺集合は分割Q = ｛00000、 00001、 00010、 00100、 00101、 01000、 01001、 01010、 10000、 10010、 10100｝を定める。辺の隣接に随伴する、Qの置換により、離散化された黄金平均変換が定義される。ここで、一般に、Qの置換全体の集合に比べると、少ない量だけしか離散化されたマルコフ変換を与えることができないに注意されたい。Hの11×11アドミタンス行列Cの余因子C11を計算することにより、離散化された黄金平均変換から得られる最大周期列は二であることがわかる。ここで行列の大きさ11はQの濃度に由来する。離散化された黄金平均変換の例を図４に示す。図４において陰をつけた四角形がQの置換の一対一対応を定める。この場合、最大周期列00000100101を生成する。
【００１７】
次に、全てのde Bruijn系列を生成する、比較例のアルゴリズムを検討する。
各正の整数nに対して、長さ2nのde Bruijn系列が丁度2の（2n-1-n）乗個存在する。de Bruijn による、この事実の証明の最も重要な部分は、グラフGnとGn+1の間の次の関係に気付いたことにある。
Gn+1 = G*n・・・（1）
ここで、Gn=（Vn，An）（n > 1）はVn=｛0，1｝n-1とAn =｛0，1｝nを有するde Bruijnグラフである。辺a1a2・・・an∈Aはa1a2・・・an-1からa2a3・・・anへ隣接する。G*nはGnの辺有向グラフである。
上記関係（1）を用いた、全てのde Bruijn系列を生成するアルゴリズムが提案されている。しかしながら、このアルゴリズムは、長さ2nの全てのde Bruijn系列を生成するために、2の2n-2乗ビットの初期記憶を常に必要とする。これは、要求される記憶量の観点から非常に高価である。
また、残念ながら、上記のような関係（1）は、一般に成立しないので、このアルゴリズムを一般の離散化されたマルコフ変換から得られる最大周期列の生成に応用することはできない。実際、離散化された黄金平均変換に対して、上記関係（1）が成り立たないことが示されている。
これまでのところ、本発明者が知り得る限り、全てのde Bruijn系列を生成するアルゴリズムはそれ程知られていない。また、それらはde Bruijn系列の性質に強く依存する。したがって、一般の離散化されたマルコフ変換から得られる最大周期列の生成に直接適用することはできない。ゆえに、本願で提案するアルゴリズムは新規であると同時に自明でない。
【００１８】
次に、本発明に係る、離散化されたマルコフ変換の集合における距離関数を説明する。説明の便宜上、k（?2）アルファベットを二値アルファベット｛0，1｝に制限する。この簡単化は、k＞2の場合に対して、k！個の場合を数え上げることを除いて、数学的処理を本質的に変えない。
与えられた離散化マルコフ変換に基づき、全ての最大周期列を生成するためには、最大辺数を有するGの全域オイラー部分グラフH =（V，B）から始めることができる。
Hはオイラーグラフであるので、連結であり、すべての頂点は偶数次数を持つ。これより、二値アルファベットの場合、各頂点の次数は2または4である。V=U∪Wは直和であるとする。ここで、Uは次数2の頂点の集合であり、Wは次数2の頂点の集合である。
U=｛u1，u2，・・・，u♯U｝およびW=｛w1，w2，・・・，w♯W｝とする。ここで、集合Aに対して、♯AはAの濃度を表す。♯V =♯U+♯Wに注意する。
表現を簡明にするために、各頂点は、二値ブロックにより、uj = a1（j）a2（j）・・・a|uj|（j）∈｛0，1｝|uj|、1 ≦ j ≦ ♯Uおよびwi = b1（i）b2（i）・・・b|wi|（i）∈｛0，1｝|wi|、1 ≦ i≦♯Wと表現されるとする。ブロックwに対して、|w|はwの長さを表す。0および1をそれぞれ区間[0，x1）および[x1，1]と同一して、各二値ブロックujまたはwiはそれぞれ筒集合｛x∈[0，1] ：Ti-1（x）∈a m（j）、1≦m ≦|uj|｝または｛x∈[0，1] ：Ti-1（x）∈b m（i）、1 ≦m≦|wi|｝に対応する。ここで、｛[0，x1）、 [x1，1]｝は、離散化される変換T（後述）の分割である。ただし、この仮定が常に成立するわけではないことが知られている。仮定が成立しない場合は表記が煩雑になるだけであり、任意の既約かつ非周期的マルコフ変換に対して、下記のオイラーグラフの真理値表を定義することができる。
各頂点ujは次数2を持つので、ujはBに属する二つの辺a（j）ujとujb（j）を一意に決定する。ここで、a（j），b（j）∈｛0，1｝。
今、Hにおいて、二つの辺0wiと1wiはwiで終端となる。一方、wi0とwi1はwiで開始する。経路が0wi0を許すとき、これはその経路が1wi1を許す（すなわち、その経路が0wi0・・・1wi1を許す）か、または他の経路が1wi1を許す（すなわち、その経路が1wi1を許さない）ときであり、ti =0と置く。一方、経路が0wi1を許すとき、これはその経路が1wi0を許す（すなわち、その経路が0wi1・・・1wi0を許す）か、または他の経路が1wi0を許す（すなわち、その経路が1wi0を許さない）ときであり、ti =1と置く。これより、♯W次ベクトルt=（t1，t2，・・・，t♯W）∈｛0，1｝♯Wを得る。これをHの真理値表（truth table）と呼ぶ。
【００１９】
第１の具体例としては、de BruijnグラフGn =（｛0，1｝n-1，｛0，1｝n）（n >1）の真理値表は（t1，t2，・・・，tn-1）∈｛0，1｝n-1で与えられる。
第２の具体例としては、離散化された黄金平均変換に随伴する図３のグラフHの真理値表は（t1，t2，t3）∈｛0，1｝3で与えられる。
Hの真理値表tにより、置換σt : B → B が
で定義される。これは、離散化マルコフ変換を表現する。a∈｛0，1｝に対して、<a>はaの二値補数を表す。すなわち、<0> =1および<1> = 0。
次に、離散化マルコフ変換の集合における距離関数dを、t，t'∈｛0，1｝]Wに対して、d（σt，σt'）= dH（t，t'）で定義する。ここで、dHはtとtのHamming距離、すなわち、tとtの異なる要素数である。
次の補題により、提案するアルゴリズムにおける次のステップが定まる：
（補題1）σtは、最大周期列を生成する離散化マルコフ変換である、すなわち、σtそれ自身が全巡回置換（full cycle）であるとする。このとき、d（σt，σt'）=1を満たす任意の離散化マルコフ変換σt'は全巡回置換になり得ない。
この補題１は、提案するアルゴリズムのステップ３（Step 3）において、線形オーダの効率的な計算を実行する指針を与える。
【００２０】
次に、本出願において、wiを非負整数に対する底2を用いた位取り表記と見做し、w1 < w2<・・・< w♯Wを仮定する。
これまで、離散化される変換として、一般の既約かつ非周期的マルコフ変換Tを考えてきた。以下の説明においては、離散化される変換Tに対して、次の単調性を要求する。
[0，1]のある分割0 = x0 < x1 <・・・< x k =1が存在して、各整数i = 1，・・・，kに対して、Tの区間[xi-1，xi）への制限は単調増加関数である。
既約かつ非周期的マルコフ変換Tがこの条件を満たすとき、Tを区分的単調増加マルコフ変換（piecewisemonotone-increasing Markov transformation）と呼ぶ。以下、離散化される変換は、その様な単調性を有するとする。ここで、区分的単調増加マルコフ変換は実用的に十分広いクラスのマルコフ変換を含むことを強調しておく。上記で述べたように、それは、Bernoulli変換だけでなく、黄金平均変換、Kalmanのマルコフ変換、および、k（? 2）-方有尾シフト変換を含む。説明の便宜上、分割の数kはアルファベットの大きさkに対応すると仮定する。先の節の様に、簡単のため、k = 2の場合を考える。
なお、主要ステップに進む前に、もう一つの準備が必要である。
ステップ０（Step 0） i =1，2，・・・，♯Wに対して、辺0wiが0wi = wi0を満たすならば、ti =1と置く。また、辺1wiが1wi = wi1を満たすならば、ti = 0と置く。これにより、単一の辺の巡回置換が予め避けられる。離散化される変換は既約かつ非周期的であるので、いずれかが少なくとも一度起こるが、両方は高々一度しか起こらない。
以下、その様なtiを固定する。tからその様な固定されたtiを全て除去し、tiの残りの成分の座標の番号を付け直した後、（♯W−1）次ベクトルまたは（♯W−2）次ベクトルを得る。それを~t =（~t1，・・・，~tW）で表す。~tを縮約真理値表（contracted truth table）と呼ぶ。定義により、一対一対応γ： t→~tおよびγ-1：~t→tを得る。
【００２１】
具体例としては、de BruijnグラフGn=（｛0，1｝n-1，｛0，1｝n）（n >1）の縮約真理値表は、（~t1，~t2，・・・，~tn-3）（∈｛0，1｝n-3）で与えられる。これは、真理値表（1，~t1， ~t2，・・・，~tn-3，0）に対応する。
他の具体例としては、離散化された黄金平均変換に随伴する図３のグラフHの縮約真理値表は、（~t1，~t2）（∈｛0，1｝2）で与えられる。これは、真理値表（1，~t1，~t2）に対応する。
【００２２】
次のサブルーチンは、本実施形態のアルゴリズムにおいて、重要な役割を果たす。
ステップＢ１（Step B1） m（1 < m ≦ ♯U+2♯W=♯B）は、
σtm（0w1）= 0w1
を満たす最小の周期であるとする。各i（1 ≦ i ≦♯W）に対して、n（1 ≦ n ≦ m ≦ ♯B）が存在して、σtn（0w1）=0wi、を満たすならば、ri =1と置く。そうでないならば、ri=0と置く。これより、r =（r1，・・・，r♯W） を得る。全てのi（1 ≦ i ≦♯W）に対してri =1ならば、全巡回置換σtを得、元に戻る。そうでないならば、ステップＢ２（Step B2）へ進む。
ステップＢ２（Step B2） ~r=γ（r）および~r =（~r1，・・・，~rW）と置く。R0 = max｛i：~ri = 0，1 ≦ i ≦W｝およびR1 =max｛i：~ri =1，1≦ i≦W｝とする。n（1 ≦ n ≦ m ≦♯B）が存在して、σtn（0w1）=1w♯Wを満たすならば、t=γ-1（~t1，・・・，~tR0-1，<~tR0>，~tR0+1，・・・，~tW）と置き、ステップＢ１（Step B1）へ進む。そうでないならば、t =γ-1（~t1，・・・，~tR1-1，<~tR1>，~tR1+1，・・・，~tW）と置き、ステップＢ１（Step B1）へ進む。
以下、~tを非負整数に対する底2を用いた位取り表記と見做す。次の補題は提案するアルゴリズムの本質的な構成要素である。
【００２３】
（補題２）~T=｛~t∈｛0，1｝W：σt=σγ-1（~t）は全巡回置換である｝とする。~t=（0，・・・，0｝（0がＷ個）として、tをステップＢ１に入力するならば、その縮約真理値表~tが~Tの下界であるような、全巡回置換σtを得る。一方、~t=（1，・・・，1｝（１がW個）として、tをステップＢ１に入力するならば、その縮約真理値表~tが~Tの上界であるような、全巡回置換σtを得る。
上記した様に、各正の整数nに対して、（2の2n-1-n乗）個の長さ2nのde Bruijn系列が存在する。これより、全てのde Bruijn系列を生成する際、生成された相異なる系列の個数を確認することによって、いつ符号生成アルゴリズムを停止させるかを判定する条件を直ちに得る。一方、離散化されたマルコフ変換から最大周期列を生成する際、それ程単純ではない。同様に、最大周期列の総数を知りたい場合、Hのアドミタンス行列Cの余因子C11を計算する必要がある。
N×N行列に対して、余因子を計算するのは、漸近的にO（（N − 1）2.376）の複雑度であることが知られている。離散化マルコフ変換に対して、N=♯Bは底2の指数関数オーダであることに注意する。
上記（補題2）は、最大周期列の総数を計算することなく、本実施形態の符号生成アルゴリズムが停止することを保証するので、非常に有用である。
【００２４】
以上で、主要ステップに進む準備が整った。本実施形態のアルゴリズムの主要ステップは、以下である。
ステップ１（Step 1）（上限値の計算）
tを~t =（1，・・・・，1｝（W個の１）として、ステップＢ１に進む。ステップＢ１から戻って来た後、σtを出力し、υ=（υ1，・・・，υW）=~tと置く。次に、ステップ２に進む。
【００２５】
ステップ２（Step 2）
tを~t=（0，・・・，0）（W個の０）としてステップＢ１に進む。ステップＢ１から戻って来た後、σtを出力し、~t（1）=（~t1（1），・・・，~t W（1））=~tと置く。i=1と置いてステップ３に進む。
【００２６】
ステップ３（Step 3）
~t W（i）= 0ならば、~t =~t（i）+11 と置く。~tW（i）=1ならば、~t =~t（i）+1と置く。ここで、加法は、~tと~t（i）を非負整数に対する底2を用いた位取り表記と見做した、二進数系における演算である。次に、ステップＢ１に進む。ステップＢ１から戻って来た後、ステップ４に進む。
【００２７】
ステップ４（Step 4）
~t <υならば、σtを出力する。~t（i+1）=（~t1（i+1），・・・，~t W（i+1））=~tと置く。i = i + 1 と置いてステップ３に進む。~t =υならば、符号生成処理を停止させる。
【００２８】
なお、次の性質により、本実施形態のアルゴリズムを有界単調真理値表（bounded monotone truth-table）アルゴリズムと呼ぶ。結果として得られる縮約真理値表の列は有界単調増加である。つまり、~t（1）< ~t（2）<・・・≦ υ（上限値）
【００２９】
次に、全てのDe Bruijn系列生成への応用を説明する。
本実施形態のアルゴリズムが正しく動作することを実証するために、ここでは、アルゴリズムを、長さ2nのDe Bruijn系列を全て、（2の2n-1-n乗）個生成するのに応用する。その前に、離散化マルコフ変換に基づく全ての最大周期列を生成する簡単な例を手短かに述べる。
【００３０】
上記具体例で見たように、離散化された黄金平均変換に随伴する図３のグラフHの縮約真理値表は、（~t1，~t2）（∈｛0，1｝2）で与えられる。これは、真理値表（1，~t1，~t2）に対応する。以下、二値ブロック~t1~t2を二値ベクトル（~t1，~t2）と見做す。
上記サブルーチンのステップＢ１及びステップＢ２を用いて、ベクトル11により、上界υ=10を得る。同様に、初期ベクトル00により、下界~t（1）=01を得る。このとき、本実施形態の符号生成アルゴリズムは、次の様に、縮約真理値表の有界単調増加列を生成する。
~t（1）= 01<10=υ
これは、上で考察した離散化黄金平均変換に基づく、相異なる二つの最大周期列00000100101および00000101001を与える。
【００３１】
次に、全de Bruijn系列の生成を考える。
n = 4の場合、長さ24のde Bruijn系列は全部で16個存在する。単一の辺の巡回置換を予め避けるため、その真理値表を（1，t2，t3，・・・，t7，0）∈｛0，1｝8で定義する。これより、縮約真理値表~t =（~t1，・・・，~t6）を得る。以下、二値ブロック~t1・・・~t6を二値ベクトル（~t1，・・・，~t6）と見做す。
サブルーチンのステップB1及びB2を用いて、ベクトル1・・・１（１が６個）により、上界（上限値）υ=111110を得る。同様に、初期ベクトル０・・・０（０が６個）により、下界（下限値）~t（1）=000111を得る。このとき、本実施形態のアルゴリズムは、次の様に、縮約真理値表の有界単調増加列を生成する。
~t（1）= 000111 < 001110 < 010011 < 010110 < 010101 < 011010 < 011100 < 011111
< 100011 < 101010 < 110001 < 110010 < 110111 < 111000 < 111011 < 111110 = υ
これは、相異なる１６個のde Bruijn系列を与える。
【００３２】
以上説明したように、位相シフトフリーM-相スペクトル拡散符号を実現する区分的線形マルコフ変換を含む、区分的単調増加マルコフ変換を考え、それらが離散化された変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えた。提案したアルゴリズムは、最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、効率的である。また、１優先関数を使用しないので、計算時間と記憶量の観点から、１優先関数を使用するアルゴリズムに比べて経済的である。本実施形態のアルゴリズムを全てのde Bruijn系列の生成に応用できる。
【００３３】
最後に、上記の最大周期列を用いた通信システムを説明する。
図５は、通信システム１のシステム構成を例示する図である。
図５に例示するように、通信システム１は、複数の携帯電話１０Ａ〜１０Ｎと、基地局２０とを含む。通信システム１には、複数の基地局２０が存在し、各基地局２０に、少なくとも１つの携帯電話１０が収容できる。１つの基地局２０が収容できる携帯電話１０の数は、最大周期列の総数による。
携帯電話１０は、符号拡散方式で音声通信及びデータ通信を行う携帯端末である。
基地局２０は、符号拡散方式で、各携帯電話１０と通信し、携帯電話間の通信を中継する。その際、基地局２０は、上記有界単調真理値表アルゴリズムにより生成された符号列を、各携帯電話１０に割り当てる。
【００３４】
図６は、基地局２０のコンピュータにインストールされた符号生成プログラム５００の機能構成を例示する図である。
図６に例示するように、符号生成プログラム５００は、テーブル生成部５０５、テーブル参照部５１０、符号生成部５１５、限界値設定部５２０、終了判定部５２５、符号割当部５３０、及び通信部５３５を有する。
【００３５】
テーブル生成部５０５は、上述した有界単調真理値表を生成し、真理値表格納部１００に格納する。なお、真理値表格納部１００は、メモリ又はＨＤＤなどにより構成された記録装置である。
テーブル参照部５１０は、符号生成部５１５からの指示に応じて、真理値表格納部１００に格納されている有界単調真理値表を参照し、参照結果を符号生成部５１５に返す。
符号生成部５１５は、テーブル参照部５１０から入力された有界単調真理値表の参照結果に基づいて、符号列を昇順または降順に生成する。
【００３６】
限界値設定部５２０は、テーブル参照部５１０に有界単調真理値表を参照させて、最大周期列の上限値及び下限値を設定し、設定された上限値及び下限値の一方を初期値として符号生成部５１５に出力し、上限値及び下限値の他方を終了値として終了判定部５２５に出力する。
終了判定部５２５は、限界値設定部５２０により設定された限界値（上限値又は下限値）と、符号生成部５１５により生成された符号列とに基づいて、符号生成処理を終了すべきか否かを判定する。本例の終了判定部５２５は、符号生成部５１５から入力される符号列が、限界値設定部５２０により設定した限界値と一致する場合に、符号生成処理を終了させ、これ以外の場合には、符号生成部５１５に対して符号生成処理を継続させる。
符号割当部５３０は、携帯電話１０からの要求に応じて、符号生成部５１５により生成された符号列を、携帯電話１０に割り当てる。
通信部５３５は、符号割当部５３０により各携帯電話１０に割り当てられた符号列を用いて、それぞれの携帯電話１０と通信を行う。
【符号の説明】
【００３７】
１・・・通信システム
１０・・・携帯電話
２０・・・基地局
５・・・符号生成プログラム
【特許請求の範囲】
【請求項１】
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、
前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と
を有する符号生成装置。
【請求項２】
有界単調真理値表を記録する真理値表記録部
をさらに有し、
前記符号生成部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列を昇順又は降順に生成し、
前記限界値設定部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列の上限値又は下限値を設定する
請求項１に記載の符号生成装置。
【請求項３】
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、
前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と、
前記符号生成部により生成された符号列を用いて、通信を行う通信部と
を有する通信装置。
【請求項４】
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、
設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップと
を有する符号生成方法。
【請求項５】
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、
設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップと
をコンピュータに実行させるプログラム。
【請求項１】
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、
前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と
を有する符号生成装置。
【請求項２】
有界単調真理値表を記録する真理値表記録部
をさらに有し、
前記符号生成部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列を昇順又は降順に生成し、
前記限界値設定部は、前記真理値表記録部により記録されている有界単調真理値表を用いて、符号列の上限値又は下限値を設定する
請求項１に記載の符号生成装置。
【請求項３】
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成部と、
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定部と、
前記限界値設定部により設定された上限値又は下限値と、符号生成部により順に生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定部と、
前記符号生成部により生成された符号列を用いて、通信を行う通信部と
を有する通信装置。
【請求項４】
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、
設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップと
を有する符号生成方法。
【請求項５】
Ｍ相符号列をＭ進数表記の数値とみた場合の上限値又は下限値を設定する限界値設定ステップと、
Ｍ相の符号列を、Ｍ進数表記の昇順又は降順で生成する符号生成ステップと、
設定された上限値又は下限値と、昇順又は降順で生成される符号列とを比較して、符号生成処理を終了すべきか否かを判定する終了判定ステップと
をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−２２７６３２（Ｐ２０１１−２２７６３２Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１０−９５５６６（Ｐ２０１０−９５５６６）
【出願日】平成２２年４月１７日（２０１０．４．１７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り
【出願人】（５０４１６０７８１）国立大学法人金沢大学 (282)
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２２年４月１７日（２０１０．４．１７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り
【出願人】（５０４１６０７８１）国立大学法人金沢大学 (282)
[ Back to top ]