(57)【要約】  本願は最大周期列の符号の生成技術に関し、従来は、ｎが一般の奇数の場合にＣＲ系列が存在することまでは示せなかったため、極めて非効率な方法でしか、長い系列長を有するＣＲ系列が生成できなかったという課題を解決する。  本願では、長さ２（２ｐ＋１）のｄｅ  Ｂｒｕｉｊｎ系列に含まれるＣＲ系列を生成する符号生成装置１００において、まず、複数の頂点のそれぞれが辺で結ばれたｄｅ  ＢｒｕｉｊｎグラフＧｎを用いて、有向オイラーグラフＧｎ０を生成し、次いで、ＣＲグラフの原型、ＣＲグラフを生成し、最後に、ＣＲ系列を生成する。このアルゴリズムによると、ＣＲグラフ上のオイラー回路をＣＲグラフに一意に変換できる。ここで、ＣＲグラフの生成においては、ＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって生成する。
2015019907.tif 000002
【特許請求の範囲】
【請求項１】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
ｐを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、
前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、
前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、
を備えることを特徴とする符号生成装置。
【請求項２】
前記オイラーグラフ生成部は、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有するように、有向オイラーグラフGn0を生成し、
前記第１ＣＲグラフ生成部は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、ＣＲグラフの原型を生成する
ことを特徴とする請求項１に記載の符号生成装置。
【請求項３】
前記第２ＣＲグラフ生成部は、前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する
ことを特徴とする請求項１に記載の符号生成装置。
【請求項４】
前記ＣＲ系列生成部は、前記ｐが素数でない場合、前記第２ＣＲグラフ生成部によって生成されたＣＲグラフから得られるオイラー回路のうち、正規括弧構造もしくは平衡括弧構造で表されるオイラー回路を選別してＣＲ系列を生成する
ことを特徴とする請求項１に記載の符号生成装置。
【請求項５】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成方法であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するステップと、
ｐを決定するステップと、
生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、決定されたｐに対するCRグラフの原型を生成するステップと、
生成されたCRグラフの原型を用いて、CRグラフを生成するステップと、
生成されたCRグラフからCR系列を生成するステップと、
を含むことを特徴とする符号生成方法。
【請求項６】
長さ2(2p+1)のde Bruijn系列に含まれるＣＲ系列を用いて通信を実行する通信装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
ｐを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、
前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、
前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからＣＲ系列を生成するＣＲ系列生成部と、
前記ＣＲ系列生成部によって生成されたＣＲ系列を用いて、送信すべき信号に対して符号化処理を実施する符号化部と、
前記符号化部によって符号化された信号を送信する送信部と、
を備えることを特徴とする通信装置。
【請求項７】
長さ2(2p+1)のde Bruijn系列に含まれるＣＲ系列を用いて塩基配列を解析する解析装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
ｐを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、
前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、
前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからＣＲ系列を生成するＣＲ系列生成部と、
前記ＣＲ系列生成部によって生成されたＣＲ系列を用いて、塩基配列を分析する分析部と、
を備えることを特徴とする解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号生成技術に関する。
【背景技術】
【０００２】
近年、電子計算機をインフラ基盤とする産業社会において、最大周期列の応用範囲は拡大しつつある。特に、遺伝子解析系、暗号系、通信系、計算機科学系、経済・ファイナンス系など、さまざまな分野に応用されている。【０００３】
従来、最大周期列を生成するために、線形フィードバックシフトレジスタ（linear feedback shift register）が通常用いられていた。線形フィードバックシフトレジスタから生成される最大周期系列はＭ系列と呼ばれ、擬似乱数系列として最も良く知られている。また、非線形フィードバックシフトレジスタから生成される最大周期系列の典型例であるde Bruijn系列は、Ｍ系列よりも遥かに多くの最大周期系列が存在する。【０００４】
非特許文献１では、長さ２nのde Bruijn系列に対するＣＲ（complement reverse）系列を定義し、nが偶数のときにはそれが存在しないことを指摘した。さらに、n＝3、5の場合にその存在例を示した。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H. Fredricksen、 “A Survey of Full Length Nonlinear Shift Register Cycle Algorithm”、 SIAM Review、 vol.24、 pp. 195〜221、 1982。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の技術では、n＝3、5の場合について例示しているものの、ｎが一般の奇数の場合にまで拡張してＣＲ系列が存在することまでは示せなかった。そのため、ｎが７以上の奇数となるような、比較的長い系列長を有するＣＲ系列を生成するためのアルゴリズムが確立できず、極めて非効率な方法でしか、長い系列長を有するＣＲ系列が生成できなかった。このような状況であったため、ＲＮＡのde novoシーケンス解析やＤＮＡリシーケンシング、あるいは、通信技術への応用には限界があった。【０００７】
本発明はかかる課題に鑑みてなされたものであり、その目的は、長い系列長を有するＣＲ系列を効率的に生成する符号生成装置、符号生成方法、通信装置、解析装置を提供することにある。
【課題を解決するための手段】
【０００８】
本発明のある態様は、符号生成装置に関する。この符号生成装置は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置である。また、この符号生成装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、を備える。また、この符号生成装置において、第２ＣＲグラフ生成部は、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成してもよい。また、この符号生成装置において、ＣＲ系列生成部は、ｐが素数でない場合、第２ＣＲグラフ生成部によって生成されたＣＲグラフから得られるオイラー回路のうち、正規括弧構造もしくは平衡括弧構造で表されるオイラー回路を選別してＣＲ系列を生成することができる。【０００９】
このような態様によると、ｐを自由に選択した上で、それぞれ特性の異なる３つのグラフを段階的に生成することによって、効率的に、長い系列長を有するＣＲ系列を生成できる。このアルゴリズムによると、ＣＲグラフ上のオイラー回路をＣＲグラフに一意に変換できる。【００１０】
本発明の別の態様は、符号生成方法である。この符号生成方法は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成方法であって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するステップと、ｐを決定するステップと、生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、決定されたｐに対するCRグラフの原型を生成するステップと、生成されたCRグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、CRグラフを生成するステップと、生成されたCRグラフからCR系列を生成するステップと、を含む。【００１１】
本発明の別の態様は、通信装置である。この通信装置は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する。また、この通信装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、ＣＲ系列生成部によって生成されたＣＲ系列を用いて、送信すべき信号に対して符号化処理を実施する符号化部と、符号化部によって符号化された信号を送信する送信部と、を備える。【００１２】
本発明の別の態様は、解析装置である。この解析装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、ＣＲ系列生成部によって生成されたＣＲ系列を用いて、塩基配列を分析する分析部とを備える。【００１３】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
本発明によると、長い系列長を有するＣＲ系列を効率的に生成できる。
【発明を実施するための形態】
【００１５】
以下においては、まず本発明の理論を説明した上で、実施例を用いて説明していくものとする。
【００１６】
＜理論＞
１．de Bruijn 系列
本発明においては、離散化マルコフ変換に基づく最大周期列の典型例である、de Bruijn 系列に注目している。de Bruijn系列は、離散化マルコフ変換に関して定義することができる（参考文献１参照）。 しかしながら、ここでは、次の様に、離散化マルコフ変換に無関係に定義するものとする。
【００１７】
ここで、二進語は有限二値系列である。また、長さk の語はk-語と呼ばれる。長さk の二進サイクルは、循環順序に関する、二進k-語の列a1a2・・・ak の列である。サイクルa1a2・・・ak においては、a1 からはじまり、ak へと続く。ここで、a2・・・aka1、aka1・・・ak-1は全てa1a2・・・akと同じｋ個のサイクルである。
以下、列X=X0X1X2・・・XN-1をX=（Xi）{i=0,1,…,N-1}と略記する。
【００１８】
二つの列X = (Xi){i=0,1,…,N-1}とY = (Yi) {i=0,1,…,N-1}が同値であると言われるのは、X とY が同じサイクルであるときであり、これを記号
＜式Ａ＞
2015019907.tif 000003
で表す。長さ2n の二進完全サイクルは二進2n-語のサイクルであって、二進n-語の、 2n 個の可能な順序列が全て異なるものとなる。なお、任意の二進n-語は、完全サイクルに丁度一回現れる。
【００１９】
例１  長さ2n の完全サイクルの例を与える。
n = 1、 01、
n = 2、 0011、
n = 3、 00010111、 00011101。
【００２０】
なお、次の定理のために、完全サイクルは、de Bruijn 系列とも呼ばれる。
定理１(参考文献２、３参照)
各正の整数n に対して、長さ2n の完全サイクルは、丁度22^(n-1)-n 個存在する。なお、ｘ＾ｎは、ｘのｎ乗を表すものとする。
【００２１】
２．既知の結果
本発明の理論を検討するまえに、まず、既知の結果について以下に述べる。
【００２２】
まず、N = 2n (n ≧ 1) と置く。また、a ∈ {0、 1} に対して、~a を用いて、a の補数を表す、即ち、~0 = 1 および~1 = 0となる。ここで、X = (Xi){i=0,1,…,N-1}は長さN = 2n のde Bruijn 系列であるとする。
【００２３】
ここで、系列の時間反転を扱うために、次を導入する。
定義１：{0、 1}上の系列X = (Xi){i=0,1,…,N-1}に対して、X の反転rX はrX = (Xi) {i=N-1,…,0}で定義される。
【００２４】
観察1 (参考文献４参照) 
X は完全サイクルであるので、~X = (~Xi){i=0,1,…,N-1}もまた完全サイクル、すなわち、de Bruijn 系列である。同様に、rX もまたde Bruijn 系列である。
【００２５】
補題1 (参考文献５参照) n≧3 に対して、
＜式Ｂ＞
2015019907.tif 000004
となる。補題2 (参考文献６参照) n≧3 に対して、
＜式Ｃ＞
2015019907.tif 000005
となる。
【００２６】
定義により、r(rX) = X、~(~X) = X、およびr~X =~（rX）。
＜式Ｄ＞
2015019907.tif 000006
、または、
＜式Ｅ＞
2015019907.tif 000007
ならば、X はCR (complement reverse) 系列と呼ばれる。定義により、 X がCR 系列であれば、~X とrX もCR 系列であることとなる。
【００２７】
補題3 (参考文献４参照) 偶数n≧4 に対して、
＜式Ｆ＞
2015019907.tif 000008
となる。
【００２８】
一方、参考文献４において、 n = 5 に対して、
＜式Ｇ＞
2015019907.tif 000009
が起こると指摘された。実際、 n = 5 に対して、32 対のCR 系列が存在する。その様なCR 系列の一例が与えられた:
例2 (参考文献４参照) X = 11111001000101011101100000110100 は
＜式Ｈ＞
2015019907.tif 000010
を満たす。
【００２９】
参考文献４において、次の問題がFredricksen により与えられた。
「 n (≧3) が偶数であるとき常にCR 系列が存在することを示せ。」
この問題はしばしば議論され、特に、参考文献６において、 CR 系列の特徴付けが与えられた。
【００３０】
補題4 (参考文献６) Y = (~Yi){i=0,1,…,N-1}は、必ずしもde Bruijn 系列でない、 {0、 1} 上の系列であるとする。系列Y がCR 系列であるのは、 N が偶数、かつ、あるN/2-語w に対して
＜式Ｉ＞
2015019907.tif 000011
のとき、またそのときに限る。
なお、語u とv に対して、uvはuとvの連接を表す。しかしながら、残念であるが、発明者の知る限り、上記Fredricksen の問題は未解決である。本発明では、この問題を解決する。
【００３１】
３．準備: CR グラフの構成
まず、Gn = (Vn、An) は、頂点集合Vn = {0、 1}n-1 および（有向）辺集合An = {0、 1}n を有するde Bruijn グラフであるとする。有向辺a1a2・・・an∈Anは、a1a2・・・an-1からa2a3・・・anに向かうと定義すれば、オイラーグラフであるde Bruijn グラフが容易に得られる。図１にnが２の場合のde Bruijn グラフG2、図２にnが３の場合のde Bruijn グラフG３をそれぞれ示す。
ここで、Fredricksen の問題を解決するために、奇数n (≧3) に対して、de Bruijn グラフに随伴するオイラー・グラフを構成する。得られたグラフのオイラー回路は長さ2n のde Bruijn 系列に属するCR 系列を生成するので、結果として得られるオイラー・グラフはCR グラフと呼ばれる。その上、 CR グラフの集合は、 de Bruijn 系列に属する全てのCR 系列を提供する。
【００３２】
さらに、n = 2m+ 1 (m≧1) と置く。n - 1 = 2m は偶数であるので、補題4 により、頂点集合V2m+1 = {0、 1}2m は、2m 個存在する、長さ2m のCR 系列を全て含む。その様な長さ2 m のCR 系列を問題の長さ2 n のCR 系列と区別するために、その様なCR 系列をCR 頂点またはCR 2m-語と言う。
【００３３】
また、VnCR(⊂ Vn) を用いて、CR 頂点全体の集合を表す。CR 2m-語はr~wwである。ここで、w ∈ {0、 1}mである。VnCRに属する任意のr~uu とr~vv に対して、 r~uu≦r~vv となるためには
u12m-1 + u22m-2 +・・・+ um ≦ v12m-1 + v22m-2 +・・・+ vm、
のときであると定めると、VnCRの上に全順序関係≦が与えられ、r~uu とr~vvの順序が一意に定まる。ここで、u = u1u2・・・um とv = v1v2・・・vm は{0、 1}m に属する。これにより、VnCRに属する全ての元に番号を付ける: v(0) < v(1) <  ・・・< v(2m-1)。CR 頂点の概念を用いて、補題4の精密化を次の様に得る。これは、 CR 系列の構成において、決定的に重要な役割を果たす。
【００３４】
補題5 
＜式Ｊ＞
2015019907.tif 000012
は、長さ22m+1 のde Bruijn 系列に属するCR 系列であるとする。
ここでw = w1w2・・・w2^2m ∈{0、 1}2^2m。このとき、一意のCR 頂点v ∈ V2m+1CRが存在して、
v = r~（w1w2・・・wm）w1w2・・・wm 
= w2^2m-m+1・・・w2^2m-1w2^2mr~（w2^2m-m+1・・・w2^2m-1w2^2m） (1)
を満たす。さらに、一意のv は0v1 と1v0 の形式でX に二度現れる。一方、他のCR 頂点u ∈ V2m+1CR は1u1または0u0 の形式でw に一度だけ現れる。
【００３５】
CR グラフの構成を進めるために、次を導入する。
定義2 {0、 1} 上の系列Y = (Yi){i=0,1,…,N-1} の重みW(Y ) は、N 個のYi の間の非零記数の数であると定義される。
すなわち、
＜式Ｋ＞
2015019907.tif 000013
となる。
【００３６】
これを用いて、Vn を互いに素な三つの部分集合
Vn-= {v ∈ Vn : W(v) < m}、 
Vn0= {v ∈ Vn : W(v) = m}、 および
Vn+= {v ∈ Vn : W(v) > m} に分割する。
【００３７】
v ∈ VnCR に対してW(v) = m なので、VnCR⊂ Vn0となるのに留意する。ここで、各v(i) ∈ VnCR(i = 0、 1、・・・2m -1) に対して、de Bruijn グラフGn に同伴するCR グラフHv(i) を次のように構成する。i + j = 2m を満たす、VnCRに属する各対v(i) とv(j) に対して、~v(i) = v(j) が成立するので、i + j = 2m を満たすHv(i) とHv(j) はグラフ同型であることが理解される。
【００３８】
ステップ1 有向グラフGn0の構成
まず初めに、 de Bruijn グラフGn に同伴する有向グラフGn0を次のように構成する。
【００３９】
まず、Wn = {λ} ∪ Vn＼Vn+と置く。Wn に属する形式u = a1a2・・・an-1 とv = a2a3・・・an の二つの頂点に対して、二進n-語a1a2・・・anは、u からv への有向辺として定義できる。結果として得られるGn の部分グラフはオイラー・グラフでない。その理由は、 Gn における次の二つの型の有向辺が与えられていないからである。
【００４０】
u1：ここでu ∈ Vn0はu = 0v の形式である; および
1u： ここでu ∈ Vn0はu = v0 の形式である。
これら二つの型以外、 w ∈ W ＼ {λ} に対して、Gn における全ての有向辺0w、 1w、 w0、 およびw1 は、結果として得られる部分グラフに備わっている。部分グラフをオイラー・グラフにするために、これら二つの型の不在の有向辺に対応して、λ から出る、またはλへ向かう有向辺を次の様に加える。
【００４１】
Gn における全てのその様な有向辺: 
u1 （ここでu = 0v ∈ Vn0）、および1u （ここでu = v0 ∈ Vn0）に対応して、
全てのu = 0v ∈ Vn0に対してu からλ への有向辺uλ を加える; および
全てのu = v0 ∈ Vn0に対してλ からu への有向辺λu を加える。
【００４２】
これにより、連結グラフを得ることができ、それをGn0で表す。上記構成により、λ は等しい入次数と出次数、
＜式ＡＢ＞
2015019907.tif 000014
を持つこととなる。一方、 Vn ＼ Vn+ に属するすべての頂点は等しい入次数と出次数、2 を持つ。ここで、頂点の入次数はそれに隣接する頂点の数であり、および頂点の出次数はそれが隣接する頂点の数である。ゆえに、結果として得られる有向グラフGn0はオイラー・グラフとなる。
【００４３】
ステップ2 CR グラフの原型の構成
次に、有向グラフGn0を変形して、 CR グラフの原型を得る。そのために、 Vn0を互いに素な以下の四つの部分集合
Vn00= {v ∈ Vn0: v = 0w0、 w ∈ {0、 1}2(m-1)}、 
Vn01= {v ∈ Vn0: v = 0w1、 w ∈ {0、 1}2(m-1)}、 
Vn10= {v ∈ Vn0: v = 1w0、 w ∈ {0、 1}2(m-1)}、 および
Vn11= {v ∈ Vn0: v = 1w1、 w ∈ {0、 1}2(m-1)} 
に分割する。
【００４４】
m = 1 の場合、 w ∈ {0、 1}0 はw =εを意味し、語u とv に対してuεv = uv と約束する。ここでεは、空語を表す。VnCR⊂ Vn01∪ Vn10であるのに再度注意する。特に、 m = 1 に対して、VnCR = Vn01∪ Vn10となり、およびVn00と Vn11は空集合となる。
【００４５】
構成を進めるために、初等整数論のいくつかの概念を用いることとする。まず、m≧2 に対して、 ep(m) は、m の素因数のべきの積としての（一意の）表示に現れる素数p が有する指数として定義されるとする。即ち、m =Πpp^ep(m)。d(m) を用いて、 m の約数の数を表すとすると、d(m) =Πp(ep(m) + 1)を得る。各m≧2 に対して、 VnCRに属する次の頂点は、CR 系列の構成において特に本質的な役割を果たす。語wに対して、 wk を用いて、 w のk 個の複製の連接、即ち、図３に示すような態様を表す。
整数a とb に対して、 a がb の約数であるとき、 a|b と書く。[x] を用いて、 x を超えない最大の整数を表す。S を用いて、 {0、 1}2m の上のシフト変換を表す。即ち、
v = v1v2・・・v2m ∈ {0、 1}2m に対して
S(v1、 v2、・・・、 v2m-1、 v2m) = (v2、 v3、・・・、 v2m、 v1)。
【００４６】
定義3 m(≧2) に対して、VnCRに属する形式v(i(k)) = (1k0k)m/k および~v(i(k)) の2(d(m)-1) 個の頂点は中立頂点と呼ばれる。ここでk≧2、 k|m および
＜式Ｌ＞
2015019907.tif 000015
である。
【００４７】
VnCR,vを用いて、VnCRに属する中立頂点全体の集合を表す。各j = 1、 2、・・・、 k-1 に対して、 Sj(v(i(k))) はVn11に属する。Vn11に属するその様な頂点もまた中立と呼ばれる。Vn11,vを用いて、Vn11に属する中立頂点全体の集合を表す。Vn00に属する中立頂点全体の集合Vn00,vが相補的に定義される．
【００４８】
構成に戻る。VnCR∪ Vn11に属する中立頂点を除いたすべての頂点v ∈ Vn0を二つの頂点、 有向辺0v とv0 を有するvと、 および有向辺1v+ とv+0 を有するv+ とに分裂する。これを図式で示すと図４、図５に図示した様になる。図４は、頂点vに対して、0vと1vが入力され、v0とv1が出力されることを示している。図５は、図４のvを２つの頂点vとv+に分裂した場合を示している。
【００４９】
このとき、中立頂点以外、すべてのv ∈ Vn0に対して、複製された頂点v+ は単一のループλ1iv+1jλ に現れる。ここで0 ≦ i+j ≦ mである。その様な単一ループは全て削除できる。
【００５０】
一方、VnCRに属する中立頂点の各対v(i(k)) と~v(i(k)) に対して、~v(i(k)) からv(i(k)) への有向辺~v(i(k))0kv(i(k)) を得る。ここでk|m であり、i(k) は定義3 で用いた。k|m を満たす各k に対して、~v(i(k)) からv(i(k)) への有向辺を削除する。次に、 λ からv(i(k)) への有向辺を加え、それにλv(i(k)) とラベル付けする。一方、~v(i(k)) からλ への有向辺を加え、それに~v(i(k))λ とラベル付けする。
【００５１】
以上により、頂点集合{λ} ∪ (Vn0＼Vn00,v)∪ Vn- を有する連結グラフを得る。これをGn- で表す。上記構成により、λ は等しい入次数と出次数、 d(m)-1 を持つ。また、 VnCR,v∪ Vn11,v∪ Vn-に属するすべての頂点は等しい入次数と出次数、2 を持つ。さらに、Vn0＼ (VnCR,v∪ Vn11,v∪ Vn00,v) に属するすべての頂点は等しい入次数と出次数、1 を持つ。ゆえに、結果として得られる有向グラフGn-はオイラー・グラフである。それをCR グラフの原型と呼ぶ。
【００５２】
ステップ3 CR グラフの構成
ここで、有向グラフGn- を変形することによって、CR グラフを構成する段階にある。以下、 m(≧2) は素数であると仮定する。この仮定を表示するために、本実施例の残りに渡ってm をp で置き換える。ここで、この仮定の下で
VnCR,v = {v(i(p)) = 1p0p、 ~v(i(p)) = 0p1p}
を得ることに注意する。
【００５３】
まず初めに、頂点λ および、λv(i(p)) または~v(i(p))λ （ここでv(i(p)) ∈ VnCR,v） 、とラベル付けされた、その全部で四つの有向辺を~v(i(p)) からv(i(p)) への二つの有向辺で置き換え、各々~v(i(p))λv(i(p)) と同じラベルを付ける。
【００５４】
Gn-におけるv(i) ∈ VnCRを選び、固定する。v(i) が中立頂点でないならば、即ち、v(i) ∈ VnCR＼ VnCR,vならば、ループであるv(i) からv(i) への有向辺を加え、それにv(i)λv(i) とラベル付けする。v(i) が中立頂点であるならば、即ち、v(i) = v(i(p)) またはv(i) = ~v(i(p)) ならば、何もしない。なぜならば、~v(i(k))λv(i(k)) とラベル付けされた二つの有向辺が構成中のグラフに既に備わっているからである。この二つの有向辺は、v(i) = v(i(p)) のとき~v(i) からv(i) へ向かい、またはv(i) = ~v(i(p)) のときv(i) から~v(i) へ向かう。
【００５５】
ケースi)
v(i) ∈ VnCR＼ VnCR,v ならば、VnCR,v に属する中立頂点v(i(p)) と~v(i(p)) の両方を、図４、図５で図示したのと同様に、各々二つの頂点に分裂すると、図６のように図示される。なお、図６および図７においては、アッパーバーを用いて補数を表現している。
【００５６】
ケースii) 
v(i) が中立頂点、すなわち、v(i) = v(i(p)) またはv(i) = ~v(i(p)) であるならば、VnCR,vに属する中立頂点v(i(p)) と~v(i(p)) の両方を、図７に図示されるように、各々二つの頂点に分裂する:
【００５７】
結局、各v(i) ∈ VnCRに対して、頂点集合(Vn0＼Vn00,v)∪ Vn-∪ VnCR,v+を有する連結グラフを得る。これをHv(i)で表す。ここでVnCR,v+ = {v(i(p))+、 ~v(i(p))+}である。全てのv(i) ∈ VnCR に対して頂点集合は同じであることに注意して、WnCR = (Vn0＼Vn00,v)∪ Vn-∪ VnCR,v+と書く。各v(i) ∈ VnCRに対して、Hv(i) に属するすべての頂点は等しい入次数と出次数を持つ。したがって、結果として得られる有向グラフHv(i) はオイラー・グラフである。Hv(i) におけるオイラー回路はCR 系列を生成するので、これをv(i) に同伴するCR グラフと呼ぶ。Bv(i) を用いて、 Hv(i) の有向辺全体の集合を表し、Hv(i) = (WnCR 、 Bv(i) ) と書く。
【００５８】
この段階において、 2p 個のCR グラフを得る。Hv(i) とH~v(i) がグラフ同型であることに注意するのは有益である。これを記号で、 
＜式Ｍ＞
2015019907.tif 000016
と書く。実際、次の様に、写像の対∂Φ : WnCR→ WnCRとΦ : Bv(i) → B~v(i)から成るグラフ同型写像(∂Φ、 Φ) : Hv(i) → H~v(i) を得る。なお、写像∂Φ を、 v ∈ WnCRに対して∂Φ(v) = rv で定義する。
【００５９】
また、写像Φ を次の様に定義する。
頂点v ∈ WnCRから出る有向辺va に対してΦ(va) = r(va) = a rv と定める。これは頂点rv に入る有向辺である; および
頂点v ∈ WnCR に入る有向辺av に対してΦ(av) = r(av) = rvaと定める。これは頂点rv から出る有向辺である。ここでa ∈ {0、 1}。
【００６０】
特に、 v(i) はCR 語であることを思い出して、∂Φ(v(i)) = ~v(i) を得る。∂Φ とΦ は一対一かつ上への写像であるので、(∂Φ、 Φ) : Hv(i) → H~v(i) はグラフ同型写像である。
【００６１】
４． 全てのCR 系列の生成
本発明者は、参考文献７また特開２０１１−２２７６３２において、離散化された区分的単調増加マルコフ変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えている。最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、提案されたアルゴリズムは効率的である。提案されたアルゴリズムは全てのde Bruijn 系列を生成するのに応用することができる。しかしながら、残念であるが、CR グラフに基づいてCR 系列を全て生成するために、有界単調真理値表アルゴリズムを応用することはできないであろう。というのは、 CR グラフにおいて、提案されたアルゴリズムにおいて不可欠な役割を果たすための参考文献７で定義された拡大的サイクルを見つけることができないようであるからである。現状ではCR 系列の総数を計算する必要がある。
【００６２】
準備: 既知のアルゴリズムによるCR グラフにおける全てのオイラー回路の探索
長さ22p+1 のde Bruijn 系列に含まれるCR 系列の総数を計算するために、まず初めに、行列木定理を思い出す。G は頂点v1、 v2、・・・、 vM を有し、かつvi からvj へ導くtij個の有向辺(i、 j = 1、 2、・・・、M) を有するグラフであるとする。行列A = (tij) {i=1,…,M, j=1,…,M}は隣接行列と呼ばれる。対角成分d1、 d2、・・・、 dM を有する対角行列をdiag(d1、 d2、・・・、 dM) と書いて、D = diag(odeg(v1)、 odeg(v2)、・・・、 odeg(vM)) とする。ここでodeg(v) は頂点vの出次数である。後のために、頂点v の入次数をideg(v) で表す。行列C = D-A はアドミタンス行列と呼ばれる。根vi を有するG を張る有向木は、M-1個の有向辺a1、 a2、・・・、 aM-1 の集合であって、j = 1、 2、・・・、Mに対して、 vj からvi へのこれらの有向辺に沿う有向路が存在するものである。次の定理は行列木定理としてよく知られている。
【００６３】
定理2 (参考文献８参照) 
根vi を有するG を張る有向木の総数はアドミタンス行列C = (cij) {i=1,…,M, j=1,…,M}におけるcii の余因子で与えられる。
上で与えられた有向グラフがオイラー・グラフであるならば、次の定理により、その様なG におけるオイラー回路の総数は、任意の頂点vi に対するcii の余因子で与えられることが示される。
【００６４】
定理3 (参考文献９参照)
G = (V、A) は、すべての頂点v ∈ V に対して、odeg(v) =ideg(v) を満たす有向グラフであるとする。またG′はGを張る有向木であるとする。r はG′ の根であるとし、またa(v) は開始頂点v を有するG′ の有向辺であるとする。a1 は開始頂点r を有する任意の有向辺であるとする。このときv0a1v1・・・aNvN、ここでv0 = r、 vi ∈ V およびai = vi-1vi ∈ A(i = 1、 2、・・・、N)、がオイラー回路であるのは、それが次を満たす有向路であるときである。
i) どの有向辺も高々一度用いられる。
ii) 規則i) に一致する唯一の選択でないならば、a(v) はa1、 a2、・・・、 aN で用いられない。
iii) ra1v1・・・aNvN は規則i) によって続けられないときにだけ終了する。
【００６５】
各CR グラフHv(i) (v(i) ∈ VnCR、 i = 0、 1、・・・、 2p-1) に対して、Δ(v(i)) を用いてHv(i) のアドミタンス行列の(1、 1) 成分の余因子を表す。CR グラフはオイラー・グラフであるので、定理3 と行列木定理から、Hv(i) におけるオイラー回路の総数はΔ(v(i)) で与えられる。定理3 と行列木定理により、Hv(i) におけるオイラー回路を得るためにすべきことは、Hv(i) を張る最小木を全て見付けることである。この目的のために、多種多様なアルゴリズムが提案されてきた。例えば、Kruskal のアルゴリズムはよく知られたアルゴリズムである。これは、重み付き連結グラフを張る最小木を見付けるための貪欲アルゴリズムである（参考文献１０参照）。
【００６６】
ステップ４  全CR 系列生成
以下、 CR グラフHv(i) が与えられれば、直ちにΔ(v(i)) 個のHv(i) におけるオイラー回路を全て得ると仮定してよい。Y はHv(i) におけるオイラー回路であるとする。オイラー回路Y を{λ、 0、 1} 上の系列と同一視する。Y によって生成される周期列Y∞ を考える。
【００６７】
ケースi) 
v(i) がVnCR に属する中立頂点でないならば、Y∞ は
v(i)0α0~v(i(p))λv(i(p))0β1~v(i(p))λv(i(p))1γ0v(i)λv(i)0α・・・  (2)
または
v(i)0α1~v(i(p))λv(i(p))1β0~v(i(p))λv(i(p))0γ0v(i)λv(i)0α・・・
の形式で書かれる。ここで、α、 β、 およびγ は、Y∞ の最初の(22p + 4p + 3)-語に現れる{0、 1} 上の語である。これら両方を考えなければならないが、Y∞ が形式(2) である前者だけを考える。というのは、Y からCR 系列を構成する手続きはいずれについても全く同じであるからである。以下、 Y∞ は形式(2) であるとする。
【００６８】
Y∞の最初の(22p + 4p + 3)-語を
v(i)0α0~v(i(p))λr~(v(i(p))0β1~v(i(p)))λv(i(p))1γ0v(i)λ
に変換する。v(i(p)) と~v(i(p)) はCR 語であることに注意して、
v(i)0α0~v(i(p))λ~v(i(p))0 r~β1v(i(p))λv(i(p))1γ0v(i)λ
を得る。 λ を消去した後、~v(i(p)) ~v(i(p)) とv(i(p))v(i(p)) の各々を単一の語~v(i(p)) とv(i(p)) にそれぞれ置き換えて、
v(i)0α0~v(i(p))0 r~β1v(i(p))1γ0v(i)
を得る。これをZ で表す。v(i(p)) と~v(i(p)) がCR 語であることに再び注意して、
Z r~Z = v(i)0α0~v(i(p))0 r~β1v(i(p))1γ0v(i)v(i)1r~γ0v(i(p))0β1~v(i(p))1r~α1v(i)
を得る。循環順序において二度現れる各々の繰り返しv(i)v(i)を単一の語v(i) でそれぞれ置き換えることにより、長さ22p+1 のCR 系列
X = v(i)0α0~v(i(p))0 r~β1v(i(p))1γ0v(i) 1 r~γ0v(i(p))0β1~v(i(p))1 r~α1
を得る。
【００６９】
構成により、語v(i)0α0~v(i(p))0β1v(i(p))1γ0v(i) において、Vn11,v∪ Vn- に属するすべての頂点は丁度2 回現れる。一方、Vn0＼ Vn11,v に属するすべての頂点は丁度1 回現れる。ゆえに、得られたCR 系列X は長さ22p+1 のde Bruijn 系列に含まれる。
【００７０】
ケースii) 
v(i) が中立頂点、すなわち、v(i) = v(i(p)) またはv(i) = ~v(i(p)) である場合を考える。これら両方の場合を考えなければならないが、v(i) = v(i(p)) の場合だけを考える。というのは、Y からCR 系列を構成する手続きはいずれの場合についても全く同じであるからである。
【００７１】
このとき、循環順序に関する同値関係を考慮して、Y∞ は形式
~v(i(p))λv(i(p))0α0~v(i(p))λv(i(p))1β1~v(i(p))λv(i(p))0α・・・
で一意に書かれるとしてよい。ここで、α とβ はY∞ の最初の(22p + 4p + 3)-語に現れる{0、 1} 上の語である。
【００７２】
Y∞ の最初の(22p + 4p + 3)-語を
~v(i(p))λv(i(p))0α0~v(i(p))λr~(v(i(p))1β1~v(i(p)))λ
に変換すれば、上のケースi) と全く同じ手続きを用いることにより、長さ22p+1 のde Bruijn 系列に含まれるCR 系列X を得る。
【００７３】
逆に、長さ22p+1 のde Bruijn 系列に含まれるCR 系列X が与えられるとき、X または~Xにおいて、補題1 から、条件(1) を満たす一意のv(i) ∈ V2m+1CRを見付けることができる。v(i) が中立であるか否かに依存して、ケースi) またはii) の手続きを反転すれば、X または~X からHv(i) に含まれるオイラー回路を得る。この対応は2 対1 かつ上への対応である。補題1 から、 CR 系列X に対して、~X は相異なるCR 系列を与える。ゆえに、 v(i) ∈ V2m+1CRに対する上の手続きは、全体として、長さ22p+1 のde Bruijn 系列に含まれるCR 系列の全ての対(X、~X) を尽くす。
【００７４】
補題1 と共に、オイラー回路とCR 系列の間のこの対応を用いて、長さ22p+1 のde Bruijn 系列に含まれるCR 系列の総数は
＜式Ｎ＞
2015019907.tif 000017
で与えられる。これは、3 の最後で述べたHv(i) とH~v(i) の間のグラフ同型から、
＜式Ｏ＞
2015019907.tif 000018
に等しい。したがって、次を得る。
【００７５】
系1 任意の素数p に対して、長さ22p+1 のde Bruijn 系列に含まれるCR 系列の総数は
＜式Ｐ＞
2015019907.tif 000019
となる。ここでv(i) ∈ V2p+1CR、である。次の簡単な下界を直ちに得る。
注1
＜式Ｑ＞
2015019907.tif 000020
【００７６】
最後に、長さ22p+1 (p≧1) のde Bruijn 系列に含まれるCR 系列の存在に関して、参考文献４でFredricksen によって提起された基本的な問題を部分的に解決する:
【００７７】
定理4 p が素数であるとき常に、長さ22p+1 のde Bruijn 系列に
＜式Ｒ＞
2015019907.tif 000021
個のCR 系列が存在する。ここでv(i) ∈ V2p+1CRである。
【００７８】
次の例において、記法を簡明にするために、 v(i(p))+ から右肩の添記号+ を省略した。
例3 
図８にp = 2 に対するCR グラフの原型を示す。図９と図１０にそれぞれ1100 および1010 に同伴するCRグラフを示す。これら二つのCR グラフに対して、簡単な計算によりΔ(1100) = 12 およびΔ(1010) = 4 を得る。
【００７９】
したがって、長さ25 のde Bruijn 系列に含まれるCR 系列の総数は64 である。これにより参考文献４で観察された実験結果が理論的に確認される。
【００８０】
次に、mが素数でない場合における長さ22m+1のde Bruijn系列に含まれるCR系列の特徴付けを行う。以下に示すDyck言語を利用することにより、上記Fredricksenの問題を完全に解決する。
【００８１】
５． Dyck言語
参考文献１１、１２に従い、記号力学系の観点からDyck言語L(Dn)(n ≧ 1)を定義する。Σ = {αm,βm:1 ≦ m ≦ n}とおく。各m(1 ≦ m ≦ n)について、αmは負の記号と呼ばれ、一方、βmは正の記号と呼ばれる。（零元を有する）逆単位的半群（逆モノイド）Dnを定義する: それは生成元αi,βj(1 ≦ i,j ≦ n)および1(太字)を有し、それらの関係は次のようである: 
＜式Ｓ＞
2015019907.tif 000022
【００８２】
元のu = u1u2・・uk∈Σkを長さk(k ≧ 1)のΣ上の語またはブロックと呼ぶ。長さkの語を単にk-語と呼ぶ。Σ上の全ての語と空語εの集合を表すのにΣ＊を用いる。Σ＊から逆モノイドDnへの写像を表すのにred()を用いて、γ = γ1γ2・・γk∈Σ＊(k ≧ 1)に対して、red(γ) = γ1・γ2・・γkおよびred(ε)= 1(太字)と定める。
【００８３】
Dyck言語L(Dn)は
L(Dn) = {u ∈ Σ＊ :red(u) ≠ 0}
で定義される。 u ∈ Σ＊に対してred(u)= 1(太字)ならば、uは平衡であると言われる。空語εは平衡である。なお、参考文献１３においては，n個の型の平衡括弧を有する言語がDyck言語と呼ばれている。
【００８４】
L(D1)に属する平衡語の集合は全ての正規括弧構造から成る。実際、n=1のとき、α1 = (およびβ1 = )と表すと、次の様に、三つの括弧対までの正規括弧構造を得ることができる:
(),(()),()(),((())),(()()),(())(),()(()),()()().   (3)
注2：n個の括弧対はCatalan数で数え上げられることは良く知られている:
＜式Ｔ＞
2015019907.tif 000023
【００８５】
ステップ3’ CRグラフの構成
上記ステップ２で提案されたアルゴリズムにより、CRグラフの原型Gn− は既に構成されているとする。今、有向グラフGn− を変形することによって、CRグラフを構成する段階にある。pが素数であるような場合に対しては、上記ステップ３において、長さ22p+1のde Bruijn系列に属する全てのCR系列を既に構成した。ゆえに、以下、m(≧2)は素数でないとする。これによりm ≧ 4である。
【００８６】
準備：まず初めに、頂点λおよび、λv(i(k))または~v(i(k))λとラベル付けされた、その全部で4(d(m)−1)個の有向辺を~v(i(k))からv(i(k))への2(d(m)−1)個の有向辺で置き換える。ここでv(i(k))∈VnCR,νであり、k≧2を満たす。各kに対して、結果として得られる~v(i(k))からv(i(k))への二つの有向辺に同じラベル~v(i(k))λv(i(k))を付ける。
【００８７】
Gn− におけるv(i)∈VnCRを選び、固定する。v(i)が中立頂点でないならば、即ち、v(i)∈VnCR＼VnCR,νならば、ループであるv(i)からv(i)への有向辺を加え、それにv(i)λv(i)とラベル付けする。v(i)が中立頂点であるならば、即ち、v(i) = v(i(k)) または v(i) = ~v(i(k))ならば、何もしない。というのは、~v(i(k))λv(i(k))とラベル付けされた二つの有向辺が構成中のグラフに既に備わっているからである。この二つの有向辺は、v(i) = v(i(k))のとき~v(i)からv(i)へ向かい、またはv(i) = ~v(i(k))のときv(i)から~v(i)へ向かう。
【００８８】
ケースi)
v(i)∈VnCR＼VnCR,νならば、VnCR,νに属する中立頂点v(i(k))と~v(i(k))の全ての対を、pが素数である場合に図６、図７で図示したのと同様に、各々二つの頂点に分裂すると、図１５のように図示される。図１５および図１６においては、アッパーバーを用いて補数を表現している。
【００８９】
ケースii)
v(i)が中立頂点、すなわち、∃k0(k0 ≧ 2, k0|m),v(i) = v(i(k0))またはv(i) = ~v(i(k0))であるならば、VnCR,νに属する中立頂点v(i(k0))と~v(i(k0))の両方を、図１６に示す様に、各々二つの頂点に分裂する。
一方、VnCR,νに属する他の中立頂点の対v(i(k))と~v(i(k))(k ≠ k0)の各々を上記図１５と同じ方法で二つの頂点に分裂する。
【００９０】
結局、各v(i) ∈ VnCRに対して、頂点集合(Vn0＼Vn00,ν)∪ Vn−∪ VnCR,ν+を有するオイラー・グラフを得る。これをHv(i)で表す。ここでVnCR,ν+ = {v(i(k))+, ~v(i(k))+ : v(i(k)), ~v(i(k)) ∈ VnCR}である。Hv(i)におけるオイラー回路はCR系列を生成するので、これをv(i)に同伴するCRグラフと呼ぶ。全てのv(i) ∈ VnCRに対して頂点集合は同じであることに注意して、WnCR = (Vn0＼Vn00,ν)∪ Vn−∪ VnCR,ν+と書く。Bv(i)を用いてHv(i)の有向辺全体の集合を表し、Hv(i) = (WnCR, Bv(i))と書く。この段階において、2m個のCRグラフを得る。Hv(i)とH~v(i)がグラフ同型であることに注意するのは有益である。
【００９１】
ステップ4’ 全てのCR系列の生成
上記pが素数の場合において、CR頂点の概念を用いることにより、EtzionとLempelによるCR系列の特徴付けの精密化を次の様に得た。m(≧4)が素数でない場合にも、CR系列の構成において、これは決定的に重要な役割を果たすので再記する。
補題5
＜式Ｕ＞
2015019907.tif 000024
は、長さ22m+1 のde Bruijn系列に属するCR系列であるとする。ここでw = w1w2・・・w22m ∈{0,1}2^2m。このとき、一意のCR頂点v ∈ V2m+1CRが存在して、
v = r~（w1w2・・・wm）w1w2・・・wm 
= w2^2m-m+1・・・w2^2m-1w2^2mr~（w2^2m-m+1・・・w2^2m-1w2^2m） (1)
を満たす。さらに、一意のvは0v1と1v0の形式でXに二度現れる。一方、他のCR頂点u ∈ V 2m+1CRは1u1または0u0の形式でwに一度だけ現れる。
【００９２】
ステップ3’と同様、m(≧4)は素数でないとする。固定したv(i) ∈ VnCRに対して、Hv(i)はオイラー・グラフであるので、Hv(i)におけるオイラー回路を得る。回路は、VnCR,νに属する元の(2(d(m)−1)−1)!個の円順列の一つを表す。pが素数であるような、m = pの場合と異なり、mが素数でないならば、全ての回路がCRを生成するとは限らない。新たな概念を導入するのに用いるため、上記で述べた定義を再記する。
【００９３】
語wに対して、wkを用いて、wのk個の複製の連接、即ち図３に示すような態様を表す。整数aとbに対して、aがbの約数であるとき、a|bと書く。[x]を用いて、xを超えない最大の整数を表す。Sを用いて、{0,1}2mの上のシフト変換を表す。即ち、v=v1v2・・v2m ∈ {0,1}2mに対してS(v1,v2,・・,v2m−1,v2m) = (v2,v3,・・,v2m,v1)。
【００９４】
定義3 m(≧2)に対して、VnCRに属する形式v(i(k)) = (1k0k)m/kおよび~v(i(k))の2(d(m)−1)個の頂点は中立頂点と呼ばれる。ここでk≧2，k|mおよび
＜式Ｖ＞
2015019907.tif 000025
である。VnCR,vを用いて、VnCRに属する中立頂点全体の集合を表す。各j = 1,2,・・,k−1に対して、Sj(v(i(k)))はVn11に属する。Vn11に属するその様な頂点もまた中立と呼ばれる。Vn11,νを用いて、Vn11に属する中立頂点全体の集合を表す。Vn00に属する中立頂点全体の集合Vn00,νが相補的に定義される。
【００９５】
CRグラフにおけるオイラー回路から全てのCR系列を構成するために、次を導入する。
定義4 各中立頂点v(i(k))∈VnCR,νに対して、対0~v(i(k))λv(i(k))0と1~v(i(k))λv(i(k))1は平衡であると言われる。ここでk|m, k≧2であり、またi(k)は定義3で述べたようである。同様に、対0~v(i(k))λv(i(k))1と1~v(i(k))λv(i(k))0(は平衡であると言われる。
【００９６】
Hv(i)におけるすべてのオイラー回路にはd(m)−1個の平衡対が存在することがわかる。その様な平衡対の集合をDyck言語L(Dd(m)−1)に対するアルファベットΣとみなす。
【００９７】
ケースi)
VnCRに属するv(i)が中立頂点でないならば、k|m，k≧2であるような各kに対して、その様なkと1≦j(k)≦d(m)−1なるj(k)の間の一対一対応が存在して、
{0~v(i(k))λv(i(k))0,1~v(i(k))λv(i(k))1} = {αj(k),βj(k)}   (4)
を満たす。
【００９８】
ケースii)
v(i)が中立頂点、すなわち、∃k0(k0≧2, k0|m),v(i) = v(i(k0))またはv(i) = ~v(i(k0))であるならば、
{0~v(i(k0))λv(i(k0))1,1~v(i(k0))λv(i(k0))0} = {αj(k0),βj(k0)}
を得る。他のk≠k0に対して、対応はv(i)が中立頂点でない場合と同じであり、(4)で与えられる。
【００９９】
ケースi)またはii)のいずれの場合においても、平衡対の集合とΣの間に、2d(m)−1個の一対一対応を得る。
準備：(3)で示した様に、d(m)−1対の括弧を有する全ての正規括弧構造を考える。注意2により、その総数は
＜式Ｗ＞
2015019907.tif 000026
で与えられる。
【０１００】
その様な長さ2(d(m)−1)の正規括弧構造は、d(m)−1個の開括弧(を持つ。d(m)−1個の開括弧の位置に、d(m)−1個の負の記号α1,・・,αd(m)−1を自由に配列することができる。その総数は(d(m)−1)!で与えられる。長さ2(d(m)−1)の正規括弧構造から平衡Dyck語を得るために、d(m)−1個の負の記号のその様な順列を一つ選べば、正の記号β1,・・,βd(m)−1の位置は一意に決定される。循環順序に関する同値関係を考慮して、結局、L(Dd(m)−1)に属する長さ2(d(m)−1)の平衡Dyck語に対応するような、定義4で述べた平衡対の集合に属する元の
＜式Ｘ＞
2015019907.tif 000027
個の円順列を得る。定義4の平衡対の集合に属する元のその様な円順列は、d(m)−1個の型の括弧対を有する長さ2(d(m)−1)の正規括弧構造であると言われる。その様な円順列として表されるような、CRグラフにおけるオイラー回路だけがCR系列を生成することができることを以下に示す。
【０１０１】
各CRグラフにおけるその様なオイラー回路の存在は次により保証される。
補題6 各v(i)∈VnCRに対して、d(m)−1個の型の括弧対を有する長さ2(d(m)−1)の正規括弧構造で表されるような、Hv(i)におけるあるオイラー回路が存在する。
以下、CRグラフHv(i)が一度与えられれば、上で述べた正規括弧構造で表されるようなHv(i)における全てのオイラー回路を得るとしてよい。実際、Hv(i)における全てのオイラー回路を実現して、それら各々に対して正規括弧構造で表されるかどうかを調べ、正規括弧構造で表されるようなオイラー回路だけを全て予め選別すればよい。
【０１０２】
Yは、正規括弧構造で表されるような、Hv(i)におけるオイラー回路であるとする。回路Yを{λ,0,1}上の系列と同一視する。ここで~λ = λと定義する。
Yによって生成される周期列Y∞を考える。Φ:Σ→Φ(Σ)を用いて、Yに対する、上で述べた2d(m)−1個の一対一対応の一つを表す。次の観察は、CR系列の構成において重要な役割を果たす。
注3：各対応Φ(γ)=a~vλvbに対して、
＜式Ｙ＞
2015019907.tif 000028
と定義する。ここでγ∈Σ, a,b∈{0,1},およびv∈VnCR,νである。このとき、1≦j≦d(m)−1に対して、
＜式Ｚ＞
2015019907.tif 000029
を得る。ここでw∈{0,1,λ}＊である。
【０１０３】
ケースi)
v(i)がVnCRに属する中立頂点でないならば、循環順序に関する同値関係を考慮して、Y∞は次の形式で一意に書かれる：
v(i)0fΦ(αj1)gΦ(βj1)h0v(i)λv(i)0f・・.    (5)
ここでαj1は対応する平衡Dyck語における最左の負の記号であり、またv(i)は
v(i)0fΦ(αj1)gΦ(βj1)h0v(i)
に丁度二回現れる。二つの場合、即ち、Φ(αj1) = 0~v(i(k1))λv(i(k1))0かつΦ(βj1) = 1~v(i(k1))λv(i(k1))1、またはΦ(αj1)=1~v(i(k1))λv(i(k1))1かつΦ(βj1)=0~v(i(k1))λv(i(k1))0を考えなければならない。しかしながら、前者の場合だけを考える。というのは、YからCR系列を構成する手続きはいずれについても全く同じであるからである。
【０１０４】
開始ステップ：まず初めに、Y∞における
v(i)0f0~v(i(k1))λv(i(k1))0g1~v(i(k1))λv(i(k1))10v(i)λ
を
v(i)0f0~v(i(k1))λr~(v(i(k1))0g1~v(i(k1)))λv(i(k1))1h0v(i)λ
へ変換する。v(i(k1))と~v(i(k1))がCR語であることに注意して、
v(i)0f0~v(i(k1))λ~v(i(k1))0r~g1v(i(k1))λv(i(k1))1h0v(i)λ
を得る。二つのλを消去した後、繰り返し~v(i(k1))~v(i(k1))とv(i(k1))v(i(k1))の各々を単一の語~v(i(k1))とv(i(k1))にそれぞれ置き換えて、
v(i)0f0~v(i(k1))0r~g1v(i(k1))1h0v(i)
を得る。これをZ(1)で表す。
【０１０５】
2から(d(m)−1)までの繰り返しステップ：
次に、Z(1)は、(5)において、Φ(αj2)とΦ(βj2)がgまたはhに現れることに依存して、それぞれ
＜式ＡＣ＞
2015019907.tif 000030
の形式で書かれる。ここでαj2は対応する平衡Dyck語における最左から第二の負の記号である。Yは平衡括弧構造を有するので、(5)において、Φ(αj2)とΦ(βj2)は共にgまたhのいずれかに現れるが、別々にgとhに現れない。もしもΦ(αj2)とΦ(βj2)が別々にgとhに現れたとすると、それらは平衡括弧構造を壊すことになるであろう。両者が共にgに現れるときでさえ、注意3により、gからr~gへの上記変換は、Yにおける平衡括弧構造に影響しない。
平衡括弧構造を変更することなく、上の変換を繰り返すことにより、帰納的にZ(d(m)−1)を得る。
【０１０６】
最終ステップ：
再びv(i(k))と~v(i(k))がCR語であることに注意して、
Z(d(m)−1)r~Z(d(m)−1) = v(i)0f0~v(i(k1))0・・0v(i)v(i)1・・1~v(i(k1))1r~f1v(i)
を得る。循環順序において二度現れる各々の繰り返しv(i)v(i)を単一の語v(i)でそれぞれ置き換えることにより、長さ22m+1のCR系列
X = v(i)0f0~v(i(k1))0・・0v(i)1・・1~v(i(k1))1r~f1
を得る。得られたCR系列が長さ22m+1のde Bruijn系列に属することを確認するのは容易である。
【０１０７】
ケースii)
v(i)が中立頂点、すなわち、v(i) = v(i(k0))またはv(i) = ~v(i(k0))である場合を考える。これら両方の場合を考えなければならないが、v(i) = v(i(k0))の場合だけを考える。というのは、
＜式ＡＤ＞
2015019907.tif 000031
であるからである。
このとき、循環順序に関する同値関係を考慮して、Y∞は次の形式で書かれる：
Φ(αj1)fΦ(βj1)gΦ(αj1)f・・。
【０１０８】
ここでαj1は対応する平衡Dyck語における最左の負の記号であり、また~v(k0)λv(k0)はΦ(αj1)fΦ(βj1)gに丁度二回現れる。二つの場合、即ち、Φ(αj1) = 1~v(i(k0))λv(i(k0))0かつΦ(βj1) = 0~v(i(k0))λv(i(k0))1、またはΦ(αj1) = 0~v(i(k0))λv(i(k0))1かつΦ(βj1) = 1~v(i(k0))λv(i(k0))0を考えなければならない。しかしながら、YからCR系列を構成する手続きはいずれの場合についても全く同じであるので、前者の場合だけを考える。このとき、循環順序に関する同値関係を考慮して、Y∞は次の形式で一意に書かれる：
v(i(k0))0f0~v(i(k0))λv(i(k0))1g1~v(i(k0))λv(i(k0))0f・・。
【０１０９】
Y∞における
v(i(k0))0f0~v(i(k0))λv(i(k0))1g1~v(i(k0))λ
を
v(i(k0))0f0~v(i(k0))λr~(v(i(k0))1g1~v(i(k0)))λ 
= v(i(k0))0f0~v(i(k0))λ~v(i(k0))0r~g0v(i(k0))λ
へ変換する。二つのλを消去した後、繰り返し~v(i(k0))~v(i(k0))を単一の語~v(i(k0))に置き換えて、
v(i(k0))0f0~v(i(k0))0r~g0v(i(k0))
を得る。これをZ(1)で表す。上のケースi)と全く同じ手続きを用いることにより、帰納的にZ(d(m)−1)を得る。上のケースi)と同じ様に、Z(d(m)−1)r~Z(d(m)−1)を変形することにより、長さ22m+1のde Bruijn系列に属するCR系列Xを得る。
【０１１０】
逆に、長さ22m+1のde Bruijn系列に含まれるCR系列Xが与えられるとき、Xまたは~Xにおいて、補題5から、条件(1)を満たす一意のv(i)∈V2m+1CRを見付けることができる。v(i)が中立であるか否かに依存して、ケースi)またはii)の手続きを反転すれば、Xまたは~XからHv(i)に含まれるオイラー回路を得る。この対応は2対1かつ上への対応である。n≧3に対して、
＜式ＡＡ＞
2015019907.tif 000032
であるので（参照文献５参照）、CR系列Xに対して、~Xは相異なるCR系列を与える。ゆえに、v(i)∈V2m+1CRに対する上の手続きは、全体として、長さ22m+1のde Bruijn系列に含まれるCR系列の全ての対(X,~X)を尽くす。
結局、次の定理を得る。
【０１１１】
定理5  m(≧4)が素数でない場合、長さ22m+1のde Bruijn系列に含まれるCR系列が少なくとも2m+1個存在する。
したがって、上記定理4と合わせて、長さ22m+1(m≧1)のde Bruijn系列に含まれるCR系列の存在に関して、参考文献４においてFredricksenにより提唱された基本的問題を完全に解決した。
【０１１２】
以下に、参考文献を列挙する。
[1] H. Fujisaki、 “Discretized Markov Transformations - An Example of Ultradiscrete Dynamical Systems -”、IEICE Trans. Fundamentals、 vol.E88-A、 pp.2684-2691、 2005。
[2] N. G. de Bruijn、 “A Combinatorial Problem、” Nederl. Akad. Wetensch. Proc.、 vol.49、 pp. 758 - 764、 1946。
[3] C. Flye Sainte-Marie、 “Solution to problem number 58、” L'Intermediare des Mathematiciens、 vol. 1、 pp.107 - 110、 1894。
[4] H. Fredricksen、 “A Survey of Full Length Nonlinear Shift Register Cycle Algorithm、” SIAM Review、 vol.24、 pp. 195 - 221、 1982。
[5] A. H. Chan、 R. A. Games、 and E. L. Key、 “On the Complexities of de Bruijn Sequences、” J. Comb. Theory、Ser. A、 vol. 33、 pp. 233 - 246、 1982。
[6] T. Etzion and A. Lempel、 “On the distribution of de Bruijn sequences of given complexity、” IEEE Trans.on Information Theory、 vol. 30、 pp. 611 - 614、 1984。
[7] H. Fujisaki、 “An Algorithm For Generating All Full-Length Sequences Which Are Based On DiscretizedMarkov Transformations、” NOLTA、 IEICE、 vol. 1、 pp. 166 - 175、 2010。
[8] W. T. Tutte、 “The dissection of equilateral triangles into equilateral triangles、” Proc。 Cambridge Phil. Soc.、vol. 44、 pp. 463 - 482、 1948。
[9] T. van Aardenne-Ehrenfest and N. G. de Bruijn、 “Circuits and trees in oriented linear graphs、” SimonStevin、 vol. 28、 pp. 203 - 217、 1951。
[10] J. B. Kruskal、 “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem、”Proceedings of the American Mathematical Society、 vol 7、 pp. 48 - 50、 1956。
[11] T.Hamachi and K. Inoue, “Embedding of Shifts of Finite Type into the Dyck Shift,”Monatsheftef¨ur Mathematik, vol.145, pp. 107−129, 2005.
[12] T.Meyerovitch, “Tail invariant measures of the Dyck shift,” Israel J. of Math., vol.163, pp.61−83, 2008.
[13] J.E.Hopcroft and J.D.Ulman, Introduction to Automata Theory, Languages, and Comuputation, Addison-Wesley, 1979.
【実施例１】
【０１１３】
ここで、実施例１を用いて、本発明の実施の形態について説明する。図１１は、本発明の実施例１にかかる符号生成装置１００を示す図である。符号生成装置１００は、メモリ１０と、オイラーグラフ生成部１２と、取得部１４と、第１ＣＲグラフ生成部１６とを、第２ＣＲグラフ生成部１８と、ＣＲ系列生成部２０とを含む。【０１１４】
この符号生成装置１００においては、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する。メモリ１０は、オイラーグラフ生成部１２と、第１ＣＲグラフ生成部１６とを、第２ＣＲグラフ生成部１８と、ＣＲ系列生成部２０と接続され、それぞれのブロックにおいて生成されたグラフを記憶し、必要に応じてアクセスされて、記憶している情報を出力する。【０１１５】
オイラーグラフ生成部１２は、上記ステップ１において説明したように、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成して、メモリ１０に記憶する。【０１１６】
具体的には、オイラーグラフ生成部１２は、u = a1a2・・・an-1 とv = a2a3・・・an の二つの頂点に対して、二進n-語a1a2・・・anがu からv への有向辺となるde BruijnグラフGnに含まれる部分グラフのうち、u1、1uのいずれかの型の不在の有向辺に対応して、λ から出る、またはλへ向かう有向辺を、全てのu = 0vに対して、u からλ への有向辺uλ を加える、または、全てのu = v0に対してλ からu への有向辺λu を加えることによって、有向オイラーグラフGn0を生成すればよい。なお、二進n-語a1a2・・・anがu からv への有向辺となるde BruijnグラフGnは、生成したい符号の長さを考慮して、所定の従来技術を用いて生成されてもよく、このような態様であっても、本発明の実施になんら影響を与えるものでないことは、当業者において自明であると言える。【０１１７】
なお、メモリ１０に記憶されるグラフの態様は、通常の技術が用いられてもよい。なお、複数の頂点は、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含んでもよい。【０１１８】
取得部１４は、素数ｐを取得して、第１ＣＲグラフ生成部１６に出力する。ｐは、生成したい符号の長さを22p+1として求めればよく、ｐの代わりに符号長自体を入力して、ｐを計算により導出してもよい。【０１１９】
第１ＣＲグラフ生成部１６は、上記ステップ２において説明したように、オイラーグラフ生成部１２によって生成された有向オイラーグラフGn0をメモリ１０から読み出して、取得部１４によって取得されたｐに対するＣＲグラフの原型に変形し、メモリ１０に記憶する。【０１２０】
具体的には、第１ＣＲグラフ生成部１６は、有向オイラーグラフGn0において、中立頂点を除いたすべての頂点v ∈ Vn0を二つの頂点、すなわち、有向辺0v とv0 を有するvと、有向辺1v+ とv+0 を有するv+ とに分裂する。さらに、第１ＣＲグラフ生成部１６は、分裂後の部分グラフから、単一のループλ1iv+1jλを削除する。【０１２１】
ついで、第１ＣＲグラフ生成部１６は、中立頂点の各対v(i(k)) と~v(i(k)) に含まれる~v(i(k)) からv(i(k)) への有向辺~v(i(k))0kv(i(k)) の一部を削除する。さらに、第１ＣＲグラフ生成部１６は、λからv(i(k)) への有向辺を加え、それにλv(i(k)) とラベル付けする。また、~v(i(k)) からλ への有向辺を加え、それに~v(i(k))λ とラベル付けする。【０１２２】
以上により、ＣＲグラフの原型は、それぞれの頂点における入次数と出次数が等しくなる。ここで、ＣＲグラフの原型における複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む。【０１２３】
第２ＣＲグラフ生成部１８は、上記ステップ３において説明したように、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型をメモリ１０から読み出して、ＣＲグラフを生成し、メモリ１０に記憶する。【０１２４】
具体的には、第２ＣＲグラフ生成部１８は、頂点λ および、λv(i(p)) または~v(i(p))λ （ここでv(i(p)) ∈ VnCR,v） 、とラベル付けされた、その全部で四つの有向辺を~v(i(p)) からv(i(p)) への二つの有向辺で置き換え、各々~v(i(p))λv(i(p)) と同じラベルを付ける。ここで、v(i) が中立頂点でないならば、ループであるv(i) からv(i) への有向辺を加え、それに~v(i)λv(i) とラベル付けする。一方、v(i) が中立頂点であるならば、何もしない。この二つの有向辺は、v(i) = v(i(p)) のとき~v(i) からv(i) へ向かい、またはv(i) = ~v(i(p)) のときv(i) から~v(i) へ向かう。【０１２５】
ここで、ＣＲグラフは、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、生成される。【０１２６】
ＣＲ系列生成部２０は、上記ステップ４において説明したように、第２ＣＲグラフ生成部１８によって生成されたＣＲグラフからCR系列を生成する。【０１２７】
つぎに、動作例について説明する。図１２は、図１１の符号生成装置１００の処理例を示すフローチャートである。このフローチャートは、生成すべき符号の長さが決定されたことを契機として開始されてもよい。【０１２８】
まず、生成すべき符号の長さからＰを取得する（Ｓ１０）。ここで、Ｐが素数でない場合（Ｓ１２のＮｏ）、後述する処理Ａを実行する。一方、Ｐが素数であった場合（Ｓ１２のＹｅｓ）、上記ステップ１にしたがって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点が入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含むように、有向オイラーグラフGn0を生成する（Ｓ１４）。【０１２９】
ついで、上記ステップ２にしたがって、生成された有向オイラーグラフGn0をメモリ１０を変形して、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含むように、取得されたｐに対するＣＲグラフの原型に変形する（Ｓ１６）。【０１３０】
さらに、上記ステップ３にしたがって、生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する（Ｓ１８）。ここで、上記ステップ４にしたがって、生成されたＣＲグラフからCR系列を生成する。【０１３１】
一方、図１２において、符号生成装置１００は、取得部１４において生成すべき符号の長さN=2nからＰを取得し（Ｓ１０）、Ｐが素数でないm(≧4)の場合（Ｓ１２のＮｏ）、図１７に示す処理Ａを実行する。図１７のフローチャートにおいて、Ｓ１４、Ｓ１６の処理は、上記図１２のＳ１４、１６の処理と同様である。すなわち、オイラーグラフ生成部１２は、上記ステップ1にしたがって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点が入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含むように、、有向オイラーグラフGn0を生成する（Ｓ１４）。【０１３２】
ついで、上記ステップ2にしたがって、第１ＣＲグラフ生成部１６は、上記生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含むように、取得されたｐに対するＣＲグラフの原型に変形する（Ｓ１６）。【０１３３】
さらに、第２ＣＲグラフ生成部１８は、上記ステップ3’にしたがって、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する（Ｓ２０）。ここで、ＣＲ系列生成部２０は、上記ステップ4’において説明したように、Dyck言語を利用することにより、第２ＣＲグラフ生成部１８によって生成されたＣＲグラフから正規括弧構造を持つオイラー回路を選別し（Ｓ２２）、選別したオイラー回路を用いてCR系列を生成する（Ｓ２４）。【０１３４】
第２ＣＲグラフ生成部１８で生成される各頂点v(i)∈VnCRに対するCRグラフに含まれるオイラー回路は、VnCR,νに属する元の(2(d(m)−1)−1)!個の円順列の一つを表すが、mが素数でないならば、全ての回路がCRを生成するとは限らない。そこで、ＣＲ系列生成部２０は、d(m)−1個の型の括弧対を有する長さ2(d(m)−1)の正規括弧構造を持つ円順列として表されるような、CRグラフにおけるオイラー回路だけがCR系列を生成することができる、という概念を導入する。【０１３５】
したがって、上記実施例１によれば、任意の奇数n (≧3)に対する、全てのＣＲ系列を生成可能な符号生成装置を提供することができる。これにより、ｎが７以上の奇数となるような、比較的長い系列長を有するＣＲ系列を効率的に生成することが可能になる。【０１３６】
ここで変形例について説明する。第１の変形例は、解析装置である。図１３は、第１の変形例にかかる解析装置２００の構成例を示す図である。この解析装置２００は、ＲＮＡのde novoシーケンス解析やリシーケンシングを用いる次世代ＤＮＡシーケンス解析に好適である。【０１３７】
解析装置２００は、符号生成装置１００と、分析部３０とを含む。符号生成装置１００は、図４に図示した符号生成装置１００である。ここで、分析部３０は、符号生成装置１００によって生成された符号を用いて、分析対象となる塩基配列について分析を行い、結果を出力する。【０１３８】
第２の変形例は、通信装置である。第２の変形例は、通信装置である。図１４は、第２の変形例にかかる通信装置３００の構成例を示す図である。【０１３９】
通信装置３００は、符号生成装置１００と、符号化部４０と、送信部４２とを含む。符号生成装置１００は、図４に図示した符号生成装置１００である。ここで、符号化部３０は、符号生成装置１００によって生成された符号を用いて、送信すべき信号に対して符号化処理を実施する。ここで、符号化処理は、誤り訂正符号化処理であってもよいし、暗号化処理であってもよい。また、ＣＤＭなどの符号を用いた符号化処理であってもよい。送信部４２は、符号化部４０によって符号化処理された信号を送信処理する。【０１４０】
以上、本発明を実施の形態をもとに説明した。本発明は上述した実施例並びに各実施例の内容に限定されるものではなく、本発明の要旨の範囲内において種々に変形して実施をすることが可能である。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【産業上の利用可能性】
【０１４１】
長い系列長を有するＣＲ系列を効率的に生成できる。
【図面の簡単な説明】
【０１４２】
【図１】本発明にかかる第１のde Bruijnグラフの構成例を示す図である。
【図２】本発明にかかる第２のde Bruijnグラフの構成例を示す図である。
【図３】本発明にかかる語ｗの態様を示す図である。
【図４】本発明にかかる第１のグラフの構成例を示す図である。
【図５】本発明にかかる第２のグラフの構成例を示す図である。
【図６】本発明にかかる第３のグラフの構成例を示す図である。
【図７】本発明にかかる第４のグラフの構成例を示す図である。
【図８】本発明にかかる第５のグラフの構成例を示す図である。
【図９】本発明にかかる第６のグラフの構成例を示す図である。
【図１０】本発明にかかる第７のグラフの構成例を示す図である。
【図１１】本発明の実施例１にかかる符号生成装置の構成例を示す図である。
【図１２】図１１の符号生成装置の処理例を示すフローチャートである。
【図１３】第１の変形例にかかる解析装置の構成例を示す図である。
【図１４】第２の変形例にかかる通信装置の構成例を示す図である。
【図１５】本発明にかかる第７のグラフの構成例を示す図である。
【図１６】本発明にかかる第８のグラフの構成例を示す図である。
【図１７】図１２の処理Ａを示すフローチャートである。
【符号の説明】
【０１４３】
１０  メモリ、  １２  オイラーグラフ生成部、  １４  取得部、  １６  第１ＣＲグラフ生成部、  １８  第２ＣＲグラフ生成部、  ２０  ＣＲ系列生成部、  １００  符号生成装置、  ２００  解析装置、  ３００  通信装置。
【図１】
2015019907.tif 000033
【図２】
2015019907.tif 000034
【図３】
2015019907.tif 000035
【図４】
2015019907.tif 000036
【図５】
2015019907.tif 000037
【図６】
2015019907.tif 000038
【図７】
2015019907.tif 000039
【図８】
2015019907.tif 000040
【図９】
2015019907.tif 000041
【図１０】
2015019907.tif 000042
【図１１】
2015019907.tif 000043
【図１２】
2015019907.tif 000044
【図１３】
2015019907.tif 000045
【図１４】
2015019907.tif 000046
【図１５】
2015019907.tif 000047
【図１６】
2015019907.tif 000048
【図１７】
2015019907.tif 000049
【国際調査報告】
2015019907.tif 000050
2015019907.tif 000051