CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE
| 外国特許コード | F150008330 |
|---|---|
| 掲載日 | 2015年4月22日 |
| 出願国 | 世界知的所有権機関（ＷＩＰＯ） |
| 国際出願番号 | 2014JP070000 |
| 国際公開番号 | WO 2015019907 |
| 国際出願日 | 平成26年7月30日(2014.7.30) |
| 国際公開日 | 平成27年2月12日(2015.2.12) |
| 優先権データ |
|
| 発明の名称 （英語） |
CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE
|
| 発明の概要（英語） | The present application solves the problem that with regards to technology for generating a code of a maximum-length linearly recurring sequence, conventionally, it was not indicated that a complement reverse (CR) sequence is present when n is an ordinary odd number, and so only by means of an extremely inefficient method was it possible to generate a CR sequence having a long sequence length. In the present application, a code generating device (100) that generates a CR sequence contained in a de Bruijn sequence having a length of 2(2p+1) is such that first, a directed Eulerian graph (Gn0) is generated using a de Bruijn graph (Gn) in which a plurality of vertices are respectively joined by edges, and then a CR graph archetype and CR graph are generated, and finally a CR sequence is generated. By means of this algorithm, it is possible to uniquely convert an Eulerian circuit on a CR graph to a CR graph. Here, when generating CR graph, each of a plurality of vertices including at least one neutral vertex contained in the CR graph archetype are split into two vertices to perform the generation. |
|
|
|
|
| 国際特許分類(IPC) |
|
| 指定国 |
National States: AE AG AL AM AO AT AU AZ BA BB BG BH BN BR BW BY BZ CA CH CL CN CO CR CU CZ DE DK DM DO DZ EC EE EG ES FI GB GD GE GH GM GT HN HR HU ID IL IN IR IS JP KE KG KN KP KR KZ LA LC LK LR LS LT LU LY MA MD ME MG MK MN MW MX MY MZ NA NG NI NO NZ OM PA PE PG PH PL PT QA RO RS RU RW SA SC SD SE SG SK SL SM ST SV SY TH TJ TM TN TR TT TZ UA UG US UZ VC VN ZA ZM ZW ARIPO: BW GH GM KE LR LS MW MZ NA RW SD SL SZ TZ UG ZM ZW EAPO: AM AZ BY KG KZ RU TJ TM EPO: AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR OAPI: BF BJ CF CG CI CM GA GN GQ GW KM ML MR NE SN TD TG |
日本語項目の表示
| 発明の名称 |
符号生成装置、符号生成方法、通信装置、解析装置
|
|---|---|
| 発明の概要 | 本願は最大周期列の符号の生成技術に関し、従来は、ｎが一般の奇数の場合にＣＲ系列が存在することまでは示せなかったため、極めて非効率な方法でしか、長い系列長を有するＣＲ系列が生成できなかったという課題を解決する。本願では、長さ2(2p+1)のde Bruijn 系列に含まれるCR 系列を生成する符号生成装置１００において、まず、複数の頂点のそれぞれが辺で結ばれたde Bruijn グラフGn を用いて、有向オイラーグラフGn0 を生成し、次いで、ＣＲグラフの原型、ＣＲグラフを生成し、最後に、ＣＲ系列を生成する。このアルゴリズムによると、ＣＲグラフ上のオイラー回路をＣＲグラフに一意に変換できる。ここで、ＣＲグラフの生成においては、ＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって生成する。 |
| 特許請求の範囲 |
[請求項1] 長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置であって、 複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、 ｐを取得する取得部と、 前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、 前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、 前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、 を備えることを特徴とする符号生成装置。 [請求項2] 前記オイラーグラフ生成部は、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有するように、有向オイラーグラフGn0を生成し、 前記第１ＣＲグラフ生成部は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、ＣＲグラフの原型を生成する ことを特徴とする請求項１に記載の符号生成装置。 [請求項3] 前記第２ＣＲグラフ生成部は、前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する ことを特徴とする請求項１に記載の符号生成装置。 [請求項4] 前記ＣＲ系列生成部は、前記ｐが素数でない場合、前記第２ＣＲグラフ生成部によって生成されたＣＲグラフから得られるオイラー回路のうち、正規括弧構造もしくは平衡括弧構造で表されるオイラー回路を選別してＣＲ系列を生成する ことを特徴とする請求項１に記載の符号生成装置。 [請求項5] 長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成方法であって、 複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するステップと、 ｐを決定するステップと、 生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、決定されたｐに対するCRグラフの原型を生成するステップと、 生成されたCRグラフの原型を用いて、CRグラフを生成するステップと、 生成されたCRグラフからCR系列を生成するステップと、 を含むことを特徴とする符号生成方法。 [請求項6] 長さ2(2p+1)のde Bruijn系列に含まれるＣＲ系列を用いて通信を実行する通信装置であって、 複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、 ｐを取得する取得部と、 前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、 前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、 前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからＣＲ系列を生成するＣＲ系列生成部と、 前記ＣＲ系列生成部によって生成されたＣＲ系列を用いて、送信すべき信号に対して符号化処理を実施する符号化部と、 前記符号化部によって符号化された信号を送信する送信部と、 を備えることを特徴とする通信装置。 [請求項7] 長さ2(2p+1)のde Bruijn系列に含まれるＣＲ系列を用いて塩基配列を解析する解析装置であって、 複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、 ｐを取得する取得部と、 前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、 前記第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、 前記第２ＣＲグラフ生成部によって生成されたＣＲグラフからＣＲ系列を生成するＣＲ系列生成部と、 前記ＣＲ系列生成部によって生成されたＣＲ系列を用いて、塩基配列を分析する分析部と、 を備えることを特徴とする解析装置。 |
| 明細書 |
明 細 書 発明の名称 : 符号生成装置、符号生成方法、通信装置、解析装置 技術分野 [0001] 本発明は、符号生成技術に関する。 背景技術 [0002] 近年、電子計算機をインフラ基盤とする産業社会において、最大周期列の応用範囲は拡大しつつある。特に、遺伝子解析系、暗号系、通信系、計算機科学系、経済・ファイナンス系など、さまざまな分野に応用されている。 [0003] 従来、最大周期列を生成するために、線形フィードバックシフトレジスタ（linear feedback shift register）が通常用いられていた。線形フィードバックシフトレジスタから生成される最大周期系列はＭ系列と呼ばれ、擬似乱数系列として最も良く知られている。また、非線形フィードバックシフトレジスタから生成される最大周期系列の典型例であるde Bruijn系列は、Ｍ系列よりも遥かに多くの最大周期系列が存在する。 [0004] 非特許文献１では、長さ２nのde Bruijn系列に対するＣＲ（complement reverse）系列を定義し、nが偶数のときにはそれが存在しないことを指摘した。さらに、n＝3、5の場合にその存在例を示した。 先行技術文献 非特許文献 [0005] 非特許文献1 : H. Fredricksen、 “A Survey of Full Length Nonlinear Shift Register Cycle Algorithm”、 SIAM Review、 vol.24、 pp. 195～221、 1982。 発明の概要 発明が解決しようとする課題 [0006] しかしながら、従来の技術では、n＝3、5の場合について例示しているものの、ｎが一般の奇数の場合にまで拡張してＣＲ系列が存在することまでは示せなかった。そのため、ｎが７以上の奇数となるような、比較的長い系列長を有するＣＲ系列を生成するためのアルゴリズムが確立できず、極めて非効率な方法でしか、長い系列長を有するＣＲ系列が生成できなかった。このような状況であったため、ＲＮＡのde novoシーケンス解析やＤＮＡリシーケンシング、あるいは、通信技術への応用には限界があった。 [0007] 本発明はかかる課題に鑑みてなされたものであり、その目的は、長い系列長を有するＣＲ系列を効率的に生成する符号生成装置、符号生成方法、通信装置、解析装置を提供することにある。 課題を解決するための手段 [0008] 本発明のある態様は、符号生成装置に関する。この符号生成装置は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置である。また、この符号生成装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、を備える。また、この符号生成装置において、第２ＣＲグラフ生成部は、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成してもよい。また、この符号生成装置において、ＣＲ系列生成部は、ｐが素数でない場合、第２ＣＲグラフ生成部によって生成されたＣＲグラフから得られるオイラー回路のうち、正規括弧構造もしくは平衡括弧構造で表されるオイラー回路を選別してＣＲ系列を生成することができる。 [0009] このような態様によると、ｐを自由に選択した上で、それぞれ特性の異なる３つのグラフを段階的に生成することによって、効率的に、長い系列長を有するＣＲ系列を生成できる。このアルゴリズムによると、ＣＲグラフ上のオイラー回路をＣＲグラフに一意に変換できる。 [0010] 本発明の別の態様は、符号生成方法である。この符号生成方法は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成方法であって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するステップと、ｐを決定するステップと、生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、決定されたｐに対するCRグラフの原型を生成するステップと、生成されたCRグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、CRグラフを生成するステップと、生成されたCRグラフからCR系列を生成するステップと、を含む。 [0011] 本発明の別の態様は、通信装置である。この通信装置は、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する。また、この通信装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、ＣＲ系列生成部によって生成されたＣＲ系列を用いて、送信すべき信号に対して符号化処理を実施する符号化部と、符号化部によって符号化された信号を送信する送信部と、を備える。 [0012] 本発明の別の態様は、解析装置である。この解析装置は、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含む複数の頂点を有する有向オイラーグラフGn0を生成するオイラーグラフ生成部と、ｐを取得する取得部と、オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む複数の頂点を有するように、取得部によって取得されたｐに対するＣＲグラフの原型を生成する第１ＣＲグラフ生成部と、第１ＣＲグラフ生成部によって生成されたＣＲグラフの原型を用いて、ＣＲグラフを生成する第２ＣＲグラフ生成部と、第２ＣＲグラフ生成部によって生成されたＣＲグラフからCR系列を生成するＣＲ系列生成部と、ＣＲ系列生成部によって生成されたＣＲ系列を用いて、塩基配列を分析する分析部とを備える。 [0013] なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。 発明の効果 [0014] 本発明によると、長い系列長を有するＣＲ系列を効率的に生成できる。 発明を実施するための形態 [0015] 以下においては、まず本発明の理論を説明した上で、実施例を用いて説明していくものとする。 [0016] ＜理論＞ １．de Bruijn 系列 本発明においては、離散化マルコフ変換に基づく最大周期列の典型例である、de Bruijn 系列に注目している。de Bruijn系列は、離散化マルコフ変換に関して定義することができる（参考文献１参照）。 しかしながら、ここでは、次の様に、離散化マルコフ変換に無関係に定義するものとする。 [0017] ここで、二進語は有限二値系列である。また、長さ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}と略記する。 [0018] 二つの列X = (Xi){i=0,1,…,N-1}とY = (Yi) {i=0,1,…,N-1}が同値であると言われるのは、X とY が同じサイクルであるときであり、これを記号 ＜式Ａ＞ で表す。長さ2n の二進完全サイクルは二進2n-語のサイクルであって、二進n-語の、 2n 個の可能な順序列が全て異なるものとなる。なお、任意の二進n-語は、完全サイクルに丁度一回現れる。 [0019] 例１ 長さ2n の完全サイクルの例を与える。 n = 1、 01、 n = 2、 0011、 n = 3、 00010111、 00011101。 [0020] なお、次の定理のために、完全サイクルは、de Bruijn 系列とも呼ばれる。 定理１(参考文献２、３参照) 各正の整数n に対して、長さ2n の完全サイクルは、丁度22^(n-1)-n 個存在する。なお、ｘ＾ｎは、ｘのｎ乗を表すものとする。 [0021] ２．既知の結果 本発明の理論を検討するまえに、まず、既知の結果について以下に述べる。 [0022] まず、N = 2n (n ≧ 1) と置く。また、a ∈ {0、 1} に対して、~a を用いて、a の補数を表す、即ち、~0 = 1 および~1 = 0となる。ここで、X = (Xi){i=0,1,…,N-1}は長さN = 2n のde Bruijn 系列であるとする。 [0023] ここで、系列の時間反転を扱うために、次を導入する。 定義１：{0、 1}上の系列X = (Xi){i=0,1,…,N-1}に対して、X の反転rX はrX = (Xi) {i=N-1,…,0}で定義される。 [0024] 観察1 (参考文献４参照) X は完全サイクルであるので、~X = (~Xi){i=0,1,…,N-1}もまた完全サイクル、すなわち、de Bruijn 系列である。同様に、rX もまたde Bruijn 系列である。 [0025] 補題1 (参考文献５参照) n≧3 に対して、 ＜式Ｂ＞ となる。補題2 (参考文献６参照) n≧3 に対して、 ＜式Ｃ＞ となる。 [0026] 定義により、r(rX) = X、~(~X) = X、およびr~X =~（rX）。 ＜式Ｄ＞ 、または、 ＜式Ｅ＞ ならば、X はCR (complement reverse) 系列と呼ばれる。定義により、 X がCR 系列であれば、~X とrX もCR 系列であることとなる。 [0027] 補題3 (参考文献４参照) 偶数n≧4 に対して、 ＜式Ｆ＞ となる。 [0028] 一方、参考文献４において、 n = 5 に対して、 ＜式Ｇ＞ が起こると指摘された。実際、 n = 5 に対して、32 対のCR 系列が存在する。その様なCR 系列の一例が与えられた: 例2 (参考文献４参照) X = 11111001000101011101100000110100 は ＜式Ｈ＞ を満たす。 [0029] 参考文献４において、次の問題がFredricksen により与えられた。 「 n (≧3) が偶数であるとき常にCR 系列が存在することを示せ。」 この問題はしばしば議論され、特に、参考文献６において、 CR 系列の特徴付けが与えられた。 [0030] 補題4 (参考文献６) Y = (~Yi){i=0,1,…,N-1}は、必ずしもde Bruijn 系列でない、 {0、 1} 上の系列であるとする。系列Y がCR 系列であるのは、 N が偶数、かつ、あるN/2-語w に対して ＜式Ｉ＞ のとき、またそのときに限る。 なお、語u とv に対して、uvはuとvの連接を表す。しかしながら、残念であるが、発明者の知る限り、上記Fredricksen の問題は未解決である。本発明では、この問題を解決する。 [0031] ３．準備: 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 系列を提供する。 [0032] さらに、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-語と言う。 [0033] また、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 系列の構成において、決定的に重要な役割を果たす。 [0034] 補題5 ＜式Ｊ＞ は、長さ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 に一度だけ現れる。 [0035] CR グラフの構成を進めるために、次を導入する。 定義2 {0、 1} 上の系列Y = (Yi){i=0,1,…,N-1} の重みW(Y ) は、N 個のYi の間の非零記数の数であると定義される。 すなわち、 ＜式Ｋ＞ となる。 [0036] これを用いて、Vn を互いに素な三つの部分集合 Vn-= {v ∈ Vn : W(v) < m}、 Vn0= {v ∈ Vn : W(v) = m}、 および Vn+= {v ∈ Vn : W(v) > m} に分割する。 [0037] 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) はグラフ同型であることが理解される。 [0038] ステップ1 有向グラフGn0の構成 まず初めに、 de Bruijn グラフGn に同伴する有向グラフGn0を次のように構成する。 [0039] まず、Wn = {λ} ∪ Vn＼Vn+と置く。Wn に属する形式u = a1a2・・・an-1 とv = a2a3・・・an の二つの頂点に対して、二進n-語a1a2・・・anは、u からv への有向辺として定義できる。結果として得られるGn の部分グラフはオイラー・グラフでない。その理由は、 Gn における次の二つの型の有向辺が与えられていないからである。 [0040] u1：ここでu ∈ Vn0はu = 0v の形式である; および 1u： ここでu ∈ Vn0はu = v0 の形式である。 これら二つの型以外、 w ∈ W ＼ {λ} に対して、Gn における全ての有向辺0w、 1w、 w0、 およびw1 は、結果として得られる部分グラフに備わっている。部分グラフをオイラー・グラフにするために、これら二つの型の不在の有向辺に対応して、λ から出る、またはλへ向かう有向辺を次の様に加える。 [0041] Gn における全てのその様な有向辺: u1 （ここでu = 0v ∈ Vn0）、および1u （ここでu = v0 ∈ Vn0）に対応して、 全てのu = 0v ∈ Vn0に対してu からλ への有向辺uλ を加える; および 全てのu = v0 ∈ Vn0に対してλ からu への有向辺λu を加える。 [0042] これにより、連結グラフを得ることができ、それをGn0で表す。上記構成により、λ は等しい入次数と出次数、 ＜式ＡＢ＞ を持つこととなる。一方、 Vn ＼ Vn+ に属するすべての頂点は等しい入次数と出次数、2 を持つ。ここで、頂点の入次数はそれに隣接する頂点の数であり、および頂点の出次数はそれが隣接する頂点の数である。ゆえに、結果として得られる有向グラフGn0はオイラー・グラフとなる。 [0043] ステップ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)} に分割する。 [0044] m = 1 の場合、 w ∈ {0、 1}0 はw =εを意味し、語u とv に対してuεv = uv と約束する。ここでεは、空語を表す。VnCR⊂ Vn01∪ Vn10であるのに再度注意する。特に、 m = 1 に対して、VnCR = Vn01∪ Vn10となり、およびVn00と Vn11は空集合となる。 [0045] 構成を進めるために、初等整数論のいくつかの概念を用いることとする。まず、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)。 [0046] 定義3 m(≧2) に対して、VnCRに属する形式v(i(k)) = (1k0k)m/k および~v(i(k)) の2(d(m)-1) 個の頂点は中立頂点と呼ばれる。ここでk≧2、 k|m および ＜式Ｌ＞ である。 [0047] VnCR,vを用いて、VnCRに属する中立頂点全体の集合を表す。各j = 1、 2、・・・、 k-1 に対して、 Sj(v(i(k))) はVn11に属する。Vn11に属するその様な頂点もまた中立と呼ばれる。Vn11,vを用いて、Vn11に属する中立頂点全体の集合を表す。Vn00に属する中立頂点全体の集合Vn00,vが相補的に定義される． [0048] 構成に戻る。VnCR∪ Vn11に属する中立頂点を除いたすべての頂点v ∈ Vn0を二つの頂点、 有向辺0v とv0 を有するvと、 および有向辺1v+ とv+0 を有するv+ とに分裂する。これを図式で示すと図４、図５に図示した様になる。図４は、頂点vに対して、0vと1vが入力され、v0とv1が出力されることを示している。図５は、図４のvを２つの頂点vとv+に分裂した場合を示している。 [0049] このとき、中立頂点以外、すべてのv ∈ Vn0に対して、複製された頂点v+ は単一のループλ1iv+1jλ に現れる。ここで0 ≦ i+j ≦ mである。その様な単一ループは全て削除できる。 [0050] 一方、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))λ とラベル付けする。 [0051] 以上により、頂点集合{λ} ∪ (Vn0＼Vn00,v)∪ Vn- を有する連結グラフを得る。これをGn- で表す。上記構成により、λ は等しい入次数と出次数、 d(m)-1 を持つ。また、 VnCR,v∪ Vn11,v∪ Vn-に属するすべての頂点は等しい入次数と出次数、2 を持つ。さらに、Vn0＼ (VnCR,v∪ Vn11,v∪ Vn00,v) に属するすべての頂点は等しい入次数と出次数、1 を持つ。ゆえに、結果として得られる有向グラフGn-はオイラー・グラフである。それをCR グラフの原型と呼ぶ。 [0052] ステップ3 CR グラフの構成 ここで、有向グラフGn- を変形することによって、CR グラフを構成する段階にある。以下、 m(≧2) は素数であると仮定する。この仮定を表示するために、本実施例の残りに渡ってm をp で置き換える。ここで、この仮定の下で VnCR,v = {v(i(p)) = 1p0p、 ~v(i(p)) = 0p1p} を得ることに注意する。 [0053] まず初めに、頂点λ および、λv(i(p)) または~v(i(p))λ （ここでv(i(p)) ∈ VnCR,v） 、とラベル付けされた、その全部で四つの有向辺を~v(i(p)) からv(i(p)) への二つの有向辺で置き換え、各々~v(i(p))λv(i(p)) と同じラベルを付ける。 [0054] 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) へ向かう。 [0055] ケースi) v(i) ∈ VnCR＼ VnCR,v ならば、VnCR,v に属する中立頂点v(i(p)) と~v(i(p)) の両方を、図４、図５で図示したのと同様に、各々二つの頂点に分裂すると、図６のように図示される。なお、図６および図７においては、アッパーバーを用いて補数を表現している。 [0056] ケースii) v(i) が中立頂点、すなわち、v(i) = v(i(p)) またはv(i) = ~v(i(p)) であるならば、VnCR,vに属する中立頂点v(i(p)) と~v(i(p)) の両方を、図７に図示されるように、各々二つの頂点に分裂する: [0057] 結局、各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) ) と書く。 [0058] この段階において、 2p 個のCR グラフを得る。Hv(i) とH~v(i) がグラフ同型であることに注意するのは有益である。これを記号で、 ＜式Ｍ＞ と書く。実際、次の様に、写像の対∂Φ : WnCR→ WnCRとΦ : Bv(i) → B~v(i)から成るグラフ同型写像(∂Φ、 Φ) : Hv(i) → H~v(i) を得る。なお、写像∂Φ を、 v ∈ WnCRに対して∂Φ(v) = rv で定義する。 [0059] また、写像Φ を次の様に定義する。 頂点v ∈ WnCRから出る有向辺va に対してΦ(va) = r(va) = a rv と定める。これは頂点rv に入る有向辺である; および 頂点v ∈ WnCR に入る有向辺av に対してΦ(av) = r(av) = rvaと定める。これは頂点rv から出る有向辺である。ここでa ∈ {0、 1}。 [0060] 特に、 v(i) はCR 語であることを思い出して、∂Φ(v(i)) = ~v(i) を得る。∂Φ とΦ は一対一かつ上への写像であるので、(∂Φ、 Φ) : Hv(i) → H~v(i) はグラフ同型写像である。 [0061] ４． 全てのCR 系列の生成 本発明者は、参考文献７また特開２０１１－２２７６３２において、離散化された区分的単調増加マルコフ変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えている。最大周期列の総数を計算することなく、全ての最大周期列を生成するという意味において、提案されたアルゴリズムは効率的である。提案されたアルゴリズムは全てのde Bruijn 系列を生成するのに応用することができる。しかしながら、残念であるが、CR グラフに基づいてCR 系列を全て生成するために、有界単調真理値表アルゴリズムを応用することはできないであろう。というのは、 CR グラフにおいて、提案されたアルゴリズムにおいて不可欠な役割を果たすための参考文献７で定義された拡大的サイクルを見つけることができないようであるからである。現状ではCR 系列の総数を計算する必要がある。 [0062] 準備: 既知のアルゴリズムによる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 へのこれらの有向辺に沿う有向路が存在するものである。次の定理は行列木定理としてよく知られている。 [0063] 定理2 (参考文献８参照) 根vi を有するG を張る有向木の総数はアドミタンス行列C = (cij) {i=1,…,M, j=1,…,M}におけるcii の余因子で与えられる。 上で与えられた有向グラフがオイラー・グラフであるならば、次の定理により、その様なG におけるオイラー回路の総数は、任意の頂点vi に対するcii の余因子で与えられることが示される。 [0064] 定理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) によって続けられないときにだけ終了する。 [0065] 各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 のアルゴリズムはよく知られたアルゴリズムである。これは、重み付き連結グラフを張る最小木を見付けるための貪欲アルゴリズムである（参考文献１０参照）。 [0066] ステップ４ 全CR 系列生成 以下、 CR グラフHv(i) が与えられれば、直ちにΔ(v(i)) 個のHv(i) におけるオイラー回路を全て得ると仮定してよい。Y はHv(i) におけるオイラー回路であるとする。オイラー回路Y を{λ、 0、 1} 上の系列と同一視する。Y によって生成される周期列Y∞ を考える。 [0067] ケース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) であるとする。 [0068] 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 を得る。 [0069] 構成により、語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 系列に含まれる。 [0070] ケースii) v(i) が中立頂点、すなわち、v(i) = v(i(p)) またはv(i) = ~v(i(p)) である場合を考える。これら両方の場合を考えなければならないが、v(i) = v(i(p)) の場合だけを考える。というのは、Y からCR 系列を構成する手続きはいずれの場合についても全く同じであるからである。 [0071] このとき、循環順序に関する同値関係を考慮して、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} 上の語である。 [0072] 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 を得る。 [0073] 逆に、長さ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) を尽くす。 [0074] 補題1 と共に、オイラー回路とCR 系列の間のこの対応を用いて、長さ22p+1 のde Bruijn 系列に含まれるCR 系列の総数は ＜式Ｎ＞ で与えられる。これは、3 の最後で述べたHv(i) とH~v(i) の間のグラフ同型から、 ＜式Ｏ＞ に等しい。したがって、次を得る。 [0075] 系1 任意の素数p に対して、長さ22p+1 のde Bruijn 系列に含まれるCR 系列の総数は ＜式Ｐ＞ となる。ここでv(i) ∈ V2p+1CR、である。次の簡単な下界を直ちに得る。 注1 ＜式Ｑ＞ [0076] 最後に、長さ22p+1 (p≧1) のde Bruijn 系列に含まれるCR 系列の存在に関して、参考文献４でFredricksen によって提起された基本的な問題を部分的に解決する: [0077] 定理4 p が素数であるとき常に、長さ22p+1 のde Bruijn 系列に ＜式Ｒ＞ 個のCR 系列が存在する。ここでv(i) ∈ V2p+1CRである。 [0078] 次の例において、記法を簡明にするために、 v(i(p))+ から右肩の添記号+ を省略した。 例3 図８にp = 2 に対するCR グラフの原型を示す。図９と図１０にそれぞれ1100 および1010 に同伴するCRグラフを示す。これら二つのCR グラフに対して、簡単な計算によりΔ(1100) = 12 およびΔ(1010) = 4 を得る。 [0079] したがって、長さ25 のde Bruijn 系列に含まれるCR 系列の総数は64 である。これにより参考文献４で観察された実験結果が理論的に確認される。 [0080] 次に、mが素数でない場合における長さ22m+1のde Bruijn系列に含まれるCR系列の特徴付けを行う。以下に示すDyck言語を利用することにより、上記Fredricksenの問題を完全に解決する。 [0081] ５． 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(太字)を有し、それらの関係は次のようである: ＜式Ｓ＞ [0082] 元のu = u1u2・・uk∈Σkを長さk(k ≧ 1)のΣ上の語またはブロックと呼ぶ。長さkの語を単にk-語と呼ぶ。Σ上の全ての語と空語εの集合を表すのにΣ＊を用いる。Σ＊から逆モノイドDnへの写像を表すのにred()を用いて、γ = γ1γ2・・γk∈Σ＊(k ≧ 1)に対して、red(γ) = γ1・γ2・・γkおよびred(ε)= 1(太字)と定める。 [0083] Dyck言語L(Dn)は L(Dn) = {u ∈ Σ＊ :red(u) ≠ 0} で定義される。 u ∈ Σ＊に対してred(u)= 1(太字)ならば、uは平衡であると言われる。空語εは平衡である。なお、参考文献１３においては，n個の型の平衡括弧を有する言語がDyck言語と呼ばれている。 [0084] L(D1)に属する平衡語の集合は全ての正規括弧構造から成る。実際、n=1のとき、α1 = (およびβ1 = )と表すと、次の様に、三つの括弧対までの正規括弧構造を得ることができる: (),(()),()(),((())),(()()),(())(),()(()),()()(). (3) 注2：n個の括弧対はCatalan数で数え上げられることは良く知られている: ＜式Ｔ＞ [0085] ステップ3’ CRグラフの構成 上記ステップ２で提案されたアルゴリズムにより、CRグラフの原型Gn－ は既に構成されているとする。今、有向グラフGn－ を変形することによって、CRグラフを構成する段階にある。pが素数であるような場合に対しては、上記ステップ３において、長さ22p+1のde Bruijn系列に属する全てのCR系列を既に構成した。ゆえに、以下、m(≧2)は素数でないとする。これによりm ≧ 4である。 [0086] 準備：まず初めに、頂点λおよび、λ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))を付ける。 [0087] 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)へ向かう。 [0088] ケースi) v(i)∈VnCR＼VnCR,νならば、VnCR,νに属する中立頂点v(i(k))と~v(i(k))の全ての対を、pが素数である場合に図６、図７で図示したのと同様に、各々二つの頂点に分裂すると、図１５のように図示される。図１５および図１６においては、アッパーバーを用いて補数を表現している。 [0089] ケース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)の各々を上記図１５と同じ方法で二つの頂点に分裂する。 [0090] 結局、各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)がグラフ同型であることに注意するのは有益である。 [0091] ステップ4’ 全てのCR系列の生成 上記pが素数の場合において、CR頂点の概念を用いることにより、EtzionとLempelによるCR系列の特徴付けの精密化を次の様に得た。m(≧4)が素数でない場合にも、CR系列の構成において、これは決定的に重要な役割を果たすので再記する。 補題5 ＜式Ｕ＞ は、長さ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に一度だけ現れる。 [0092] ステップ3’と同様、m(≧4)は素数でないとする。固定したv(i) ∈ VnCRに対して、Hv(i)はオイラー・グラフであるので、Hv(i)におけるオイラー回路を得る。回路は、VnCR,νに属する元の(2(d(m)－1)－1)!個の円順列の一つを表す。pが素数であるような、m = pの場合と異なり、mが素数でないならば、全ての回路がCRを生成するとは限らない。新たな概念を導入するのに用いるため、上記で述べた定義を再記する。 [0093] 語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)。 [0094] 定義3 m(≧2)に対して、VnCRに属する形式v(i(k)) = (1k0k)m/kおよび~v(i(k))の2(d(m)－1)個の頂点は中立頂点と呼ばれる。ここでk≧2，k|mおよび ＜式Ｖ＞ である。VnCR,vを用いて、VnCRに属する中立頂点全体の集合を表す。各j = 1,2,・・,k－1に対して、Sj(v(i(k)))はVn11に属する。Vn11に属するその様な頂点もまた中立と呼ばれる。Vn11,νを用いて、Vn11に属する中立頂点全体の集合を表す。Vn00に属する中立頂点全体の集合Vn00,νが相補的に定義される。 [0095] 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(は平衡であると言われる。 [0096] Hv(i)におけるすべてのオイラー回路にはd(m)－1個の平衡対が存在することがわかる。その様な平衡対の集合をDyck言語L(Dd(m)－1)に対するアルファベットΣとみなす。 [0097] ケース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) を満たす。 [0098] ケース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)で与えられる。 [0099] ケースi)またはii)のいずれの場合においても、平衡対の集合とΣの間に、2d(m)－1個の一対一対応を得る。 準備：(3)で示した様に、d(m)－1対の括弧を有する全ての正規括弧構造を考える。注意2により、その総数は ＜式Ｗ＞ で与えられる。 [0100] その様な長さ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で述べた平衡対の集合に属する元の ＜式Ｘ＞ 個の円順列を得る。定義4の平衡対の集合に属する元のその様な円順列は、d(m)－1個の型の括弧対を有する長さ2(d(m)－1)の正規括弧構造であると言われる。その様な円順列として表されるような、CRグラフにおけるオイラー回路だけがCR系列を生成することができることを以下に示す。 [0101] 各CRグラフにおけるその様なオイラー回路の存在は次により保証される。 補題6 各v(i)∈VnCRに対して、d(m)－1個の型の括弧対を有する長さ2(d(m)－1)の正規括弧構造で表されるような、Hv(i)におけるあるオイラー回路が存在する。 以下、CRグラフHv(i)が一度与えられれば、上で述べた正規括弧構造で表されるようなHv(i)における全てのオイラー回路を得るとしてよい。実際、Hv(i)における全てのオイラー回路を実現して、それら各々に対して正規括弧構造で表されるかどうかを調べ、正規括弧構造で表されるようなオイラー回路だけを全て予め選別すればよい。 [0102] Yは、正規括弧構造で表されるような、Hv(i)におけるオイラー回路であるとする。回路Yを{λ,0,1}上の系列と同一視する。ここで~λ = λと定義する。 Yによって生成される周期列Y∞を考える。Φ:Σ→Φ(Σ)を用いて、Yに対する、上で述べた2d(m)－1個の一対一対応の一つを表す。次の観察は、CR系列の構成において重要な役割を果たす。 注3：各対応Φ(γ)=a~vλvbに対して、 ＜式Ｙ＞ と定義する。ここでγ∈Σ, a,b∈{0,1},およびv∈VnCR,νである。このとき、1≦j≦d(m)－1に対して、 ＜式Ｚ＞ を得る。ここでw∈{0,1,λ}＊である。 [0103] ケース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系列を構成する手続きはいずれについても全く同じであるからである。 [0104] 開始ステップ：まず初めに、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)で表す。 [0105] 2から(d(m)－1)までの繰り返しステップ： 次に、Z(1)は、(5)において、Φ(αj2)とΦ(βj2)がgまたはhに現れることに依存して、それぞれ ＜式ＡＣ＞ の形式で書かれる。ここでαj2は対応する平衡Dyck語における最左から第二の負の記号である。Yは平衡括弧構造を有するので、(5)において、Φ(αj2)とΦ(βj2)は共にgまたhのいずれかに現れるが、別々にgとhに現れない。もしもΦ(αj2)とΦ(βj2)が別々にgとhに現れたとすると、それらは平衡括弧構造を壊すことになるであろう。両者が共にgに現れるときでさえ、注意3により、gからr~gへの上記変換は、Yにおける平衡括弧構造に影響しない。 平衡括弧構造を変更することなく、上の変換を繰り返すことにより、帰納的にZ(d(m)－1)を得る。 [0106] 最終ステップ： 再び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系列に属することを確認するのは容易である。 [0107] ケースii) v(i)が中立頂点、すなわち、v(i) = v(i(k0))またはv(i) = ~v(i(k0))である場合を考える。これら両方の場合を考えなければならないが、v(i) = v(i(k0))の場合だけを考える。というのは、 ＜式ＡＤ＞ であるからである。 このとき、循環順序に関する同値関係を考慮して、Y∞は次の形式で書かれる： Φ(αj1)fΦ(βj1)gΦ(αj1)f・・。 [0108] ここでα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・・。 [0109] 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を得る。 [0110] 逆に、長さ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に対して、 ＜式ＡＡ＞ であるので（参照文献５参照）、CR系列Xに対して、~Xは相異なるCR系列を与える。ゆえに、v(i)∈V2m+1CRに対する上の手続きは、全体として、長さ22m+1のde Bruijn系列に含まれるCR系列の全ての対(X,~X)を尽くす。 結局、次の定理を得る。 [0111] 定理5 m(≧4)が素数でない場合、長さ22m+1のde Bruijn系列に含まれるCR系列が少なくとも2m+1個存在する。 したがって、上記定理4と合わせて、長さ22m+1(m≧1)のde Bruijn系列に含まれるCR系列の存在に関して、参考文献４においてFredricksenにより提唱された基本的問題を完全に解決した。 [0112] 以下に、参考文献を列挙する。 [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. 実施例 1 [0113] ここで、実施例１を用いて、本発明の実施の形態について説明する。図１１は、本発明の実施例１にかかる符号生成装置１００を示す図である。符号生成装置１００は、メモリ１０と、オイラーグラフ生成部１２と、取得部１４と、第１ＣＲグラフ生成部１６とを、第２ＣＲグラフ生成部１８と、ＣＲ系列生成部２０とを含む。 [0114] この符号生成装置１００においては、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する。メモリ１０は、オイラーグラフ生成部１２と、第１ＣＲグラフ生成部１６とを、第２ＣＲグラフ生成部１８と、ＣＲ系列生成部２０と接続され、それぞれのブロックにおいて生成されたグラフを記憶し、必要に応じてアクセスされて、記憶している情報を出力する。 [0115] オイラーグラフ生成部１２は、上記ステップ１において説明したように、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成して、メモリ１０に記憶する。 [0116] 具体的には、オイラーグラフ生成部１２は、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は、生成したい符号の長さを考慮して、所定の従来技術を用いて生成されてもよく、このような態様であっても、本発明の実施になんら影響を与えるものでないことは、当業者において自明であると言える。 [0117] なお、メモリ１０に記憶されるグラフの態様は、通常の技術が用いられてもよい。なお、複数の頂点は、入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含んでもよい。 [0118] 取得部１４は、素数ｐを取得して、第１ＣＲグラフ生成部１６に出力する。ｐは、生成したい符号の長さを22p+1として求めればよく、ｐの代わりに符号長自体を入力して、ｐを計算により導出してもよい。 [0119] 第１ＣＲグラフ生成部１６は、上記ステップ２において説明したように、オイラーグラフ生成部１２によって生成された有向オイラーグラフGn0をメモリ１０から読み出して、取得部１４によって取得されたｐに対するＣＲグラフの原型に変形し、メモリ１０に記憶する。 [0120] 具体的には、第１ＣＲグラフ生成部１６は、有向オイラーグラフGn0において、中立頂点を除いたすべての頂点v ∈ Vn0を二つの頂点、すなわち、有向辺0v とv0 を有するvと、有向辺1v+ とv+0 を有するv+ とに分裂する。さらに、第１ＣＲグラフ生成部１６は、分裂後の部分グラフから、単一のループλ1iv+1jλを削除する。 [0121] ついで、第１ＣＲグラフ生成部１６は、中立頂点の各対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))λ とラベル付けする。 [0122] 以上により、ＣＲグラフの原型は、それぞれの頂点における入次数と出次数が等しくなる。ここで、ＣＲグラフの原型における複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含む。 [0123] 第２ＣＲグラフ生成部１８は、上記ステップ３において説明したように、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型をメモリ１０から読み出して、ＣＲグラフを生成し、メモリ１０に記憶する。 [0124] 具体的には、第２ＣＲグラフ生成部１８は、頂点λ および、λ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) へ向かう。 [0125] ここで、ＣＲグラフは、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、生成される。 [0126] ＣＲ系列生成部２０は、上記ステップ４において説明したように、第２ＣＲグラフ生成部１８によって生成されたＣＲグラフからCR系列を生成する。 [0127] つぎに、動作例について説明する。図１２は、図１１の符号生成装置１００の処理例を示すフローチャートである。このフローチャートは、生成すべき符号の長さが決定されたことを契機として開始されてもよい。 [0128] まず、生成すべき符号の長さからＰを取得する（Ｓ１０）。ここで、Ｐが素数でない場合（Ｓ１２のＮｏ）、後述する処理Ａを実行する。一方、Ｐが素数であった場合（Ｓ１２のＹｅｓ）、上記ステップ１にしたがって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点が入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含むように、有向オイラーグラフGn0を生成する（Ｓ１４）。 [0129] ついで、上記ステップ２にしたがって、生成された有向オイラーグラフGn0をメモリ１０を変形して、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含むように、取得されたｐに対するＣＲグラフの原型に変形する（Ｓ１６）。 [0130] さらに、上記ステップ３にしたがって、生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する（Ｓ１８）。ここで、上記ステップ４にしたがって、生成されたＣＲグラフからCR系列を生成する。 [0131] 一方、図１２において、符号生成装置１００は、取得部１４において生成すべき符号の長さN=2nからＰを取得し（Ｓ１０）、Ｐが素数でないm(≧4)の場合（Ｓ１２のＮｏ）、図１７に示す処理Ａを実行する。図１７のフローチャートにおいて、Ｓ１４、Ｓ１６の処理は、上記図１２のＳ１４、１６の処理と同様である。すなわち、オイラーグラフ生成部１２は、上記ステップ1にしたがって、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点が入次数と出次数が共に第１所定値となる第１頂点と、入次数と出次数が共に２となる第２頂点とを含むように、、有向オイラーグラフGn0を生成する（Ｓ１４）。 [0132] ついで、上記ステップ2にしたがって、第１ＣＲグラフ生成部１６は、上記生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなり、かつ、複数の頂点は、入次数と出次数が共に第２所定値となる第３頂点と、入次数と出次数が共に２となる複数の第４頂点と、入次数と出次数が共に１となる第５頂点とを含むように、取得されたｐに対するＣＲグラフの原型に変形する（Ｓ１６）。 [0133] さらに、第２ＣＲグラフ生成部１８は、上記ステップ3’にしたがって、第１ＣＲグラフ生成部１６によって生成されたＣＲグラフの原型に含まれる少なくとも１つの中立頂点を含む複数の頂点のそれぞれを２つの頂点に分裂させることによって、ＣＲグラフを生成する（Ｓ２０）。ここで、ＣＲ系列生成部２０は、上記ステップ4’において説明したように、Dyck言語を利用することにより、第２ＣＲグラフ生成部１８によって生成されたＣＲグラフから正規括弧構造を持つオイラー回路を選別し（Ｓ２２）、選別したオイラー回路を用いてCR系列を生成する（Ｓ２４）。 [0134] 第２ＣＲグラフ生成部１８で生成される各頂点v(i)∈VnCRに対するCRグラフに含まれるオイラー回路は、VnCR,νに属する元の(2(d(m)－1)－1)!個の円順列の一つを表すが、mが素数でないならば、全ての回路がCRを生成するとは限らない。そこで、ＣＲ系列生成部２０は、d(m)－1個の型の括弧対を有する長さ2(d(m)－1)の正規括弧構造を持つ円順列として表されるような、CRグラフにおけるオイラー回路だけがCR系列を生成することができる、という概念を導入する。 [0135] したがって、上記実施例１によれば、任意の奇数n (≧3)に対する、全てのＣＲ系列を生成可能な符号生成装置を提供することができる。これにより、ｎが７以上の奇数となるような、比較的長い系列長を有するＣＲ系列を効率的に生成することが可能になる。 [0136] ここで変形例について説明する。第１の変形例は、解析装置である。図１３は、第１の変形例にかかる解析装置２００の構成例を示す図である。この解析装置２００は、ＲＮＡのde novoシーケンス解析やリシーケンシングを用いる次世代ＤＮＡシーケンス解析に好適である。 [0137] 解析装置２００は、符号生成装置１００と、分析部３０とを含む。符号生成装置１００は、図４に図示した符号生成装置１００である。ここで、分析部３０は、符号生成装置１００によって生成された符号を用いて、分析対象となる塩基配列について分析を行い、結果を出力する。 [0138] 第２の変形例は、通信装置である。第２の変形例は、通信装置である。図１４は、第２の変形例にかかる通信装置３００の構成例を示す図である。 [0139] 通信装置３００は、符号生成装置１００と、符号化部４０と、送信部４２とを含む。符号生成装置１００は、図４に図示した符号生成装置１００である。ここで、符号化部３０は、符号生成装置１００によって生成された符号を用いて、送信すべき信号に対して符号化処理を実施する。ここで、符号化処理は、誤り訂正符号化処理であってもよいし、暗号化処理であってもよい。また、ＣＤＭなどの符号を用いた符号化処理であってもよい。送信部４２は、符号化部４０によって符号化処理された信号を送信処理する。 [0140] 以上、本発明を実施の形態をもとに説明した。本発明は上述した実施例並びに各実施例の内容に限定されるものではなく、本発明の要旨の範囲内において種々に変形して実施をすることが可能である。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。 産業上の利用可能性 [0141] 長い系列長を有するＣＲ系列を効率的に生成できる。 図面の簡単な説明 [0142] [図1] 本発明にかかる第１のde Bruijnグラフの構成例を示す図である。 [図2] 本発明にかかる第２のde Bruijnグラフの構成例を示す図である。 [図3] 本発明にかかる語ｗの態様を示す図である。 [図4] 本発明にかかる第１のグラフの構成例を示す図である。 [図5] 本発明にかかる第２のグラフの構成例を示す図である。 [図6] 本発明にかかる第３のグラフの構成例を示す図である。 [図7] 本発明にかかる第４のグラフの構成例を示す図である。 [図8] 本発明にかかる第５のグラフの構成例を示す図である。 [図9] 本発明にかかる第６のグラフの構成例を示す図である。 [図10] 本発明にかかる第７のグラフの構成例を示す図である。 [図11] 本発明の実施例１にかかる符号生成装置の構成例を示す図である。 [図12] 図１１の符号生成装置の処理例を示すフローチャートである。 [図13] 第１の変形例にかかる解析装置の構成例を示す図である。 [図14] 第２の変形例にかかる通信装置の構成例を示す図である。 [図15] 本発明にかかる第７のグラフの構成例を示す図である。 [図16] 本発明にかかる第８のグラフの構成例を示す図である。 [図17] 図１２の処理Ａを示すフローチャートである。 符号の説明 [0143] １０ メモリ、 １２ オイラーグラフ生成部、 １４ 取得部、 １６ 第１ＣＲグラフ生成部、 １８ 第２ＣＲグラフ生成部、 ２０ ＣＲ系列生成部、 １００ 符号生成装置、 ２００ 解析装置、 ３００ 通信装置。 |
『 CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE 』に関するお問合せ
- 国立大学法人金沢大学 研究推進部産学連携課知的財産係
- URL: https://www.kanazawa-u.ac.jp/
-
E-mail:
- Address: 〒920-1192 石川県金沢市角間町ヌ７番地
- TEL: 076-264-6176
- FAX: 076-234-4012
※ 同じキーワードでJ-STORE内を検索することが出来ます。→ J-STORE内を検索
