明細書 :系列生成装置、符号化処理装置、送信装置

発行国	日本国特許庁(JP)
公報種別	特許公報(B2)
特許番号	特許第6788167号 (P6788167)
公開番号	特開2018-072867 (P2018-072867A)
登録日	令和2年11月4日(2020.11.4)
発行日	令和2年11月25日(2020.11.25)
公開日	平成30年5月10日(2018.5.10)
発明の名称または考案の名称	系列生成装置、符号化処理装置、送信装置
国際特許分類	G06F   7/58        (2006.01) H04J  13/16        (2011.01)
ＦＩ	G06F 7/58 620 H04J 13/16
請求項の数または発明の数	13
全頁数	30
出願番号	特願2016-207576 (P2016-207576)
出願日	平成28年10月24日(2016.10.24)
審査請求日	令和元年9月24日(2019.9.24)
特許権者または実用新案権者	【識別番号】504160781 【氏名又は名称】国立大学法人金沢大学
発明者または考案者	【氏名】藤崎 礼志
個別代理人の代理人	【識別番号】100141519、【弁理士】、【氏名又は名称】梶田 邦之 【識別番号】100172199、【弁理士】、【氏名又は名称】松山 浩也 【識別番号】100201374、【弁理士】、【氏名又は名称】福澤 昌俊
審査官	【審査官】征矢 崇
参考文献・文献	特開２０１１－２２７６３２（ＪＰ，Ａ） 特開平１０－２４０５００（ＪＰ，Ａ） 特開平０５－２１６６３０（ＪＰ，Ａ） 米国特許出願公開第２０１３／０１０３７３１（ＵＳ，Ａ１）
調査した分野	Ｇ０６Ｆ７／５８ Ｈ０４Ｊ１３／００－１３／２２
特許請求の範囲	【請求項1】 自己相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第１系列を生成する生成部と、 均等分布と前記区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、前記第１系列を第２系列に変換する変換部と、 を備える系列生成装置。 【請求項2】 前記自己相関特性は、下記式のρである、請求項１記載の系列生成装置。 【数1】 ここで、Ｚは、前記第１系列の確率変数である。 【請求項3】 前記変換部は、下記式により、前記第１系列を前記第２系列に変換する、請求項１又は２記載の系列生成装置。 【数2】 ここで、Ｘは前記第１系列であり、Φは前記変換条件を表すブロック符号であり、Ｙは前記第２系列であり、Ｓは、Ｌブロック全体の集合｛０，１，２｝Ｌ上のシフト変換であって、ｖ＝ｖ１ｖ２・・・ｖＬ∈｛０，１，２｝Ｌに対して下記式で表される。 【数3】 【請求項4】 前記変換条件を表すブロック符号は、下記式で定義される、請求項３記載の系列生成装置。 【数4】 【数5】 【請求項5】 前記変換条件を表すブロック符号は、下記式で定義される、請求項３又は４記載の系列生成装置。 【数6】 【請求項6】 前記第２系列は、拡散符号である、請求項１乃至５のうちいずれか１項記載の系列生成装置。 【請求項7】 前記第２系列は、暗号化又は復号のための系列である、請求項１乃至５のうちいずれか１項記載の系列生成装置。 【請求項8】 第１系列から変換された第２系列を、記憶する記憶部と、 前記第２系列に基づいて、信号列の符号化を行う符号化部と、 を備え、 前記第１系列は、自己相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、均等分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 符号化処理装置。 【請求項9】 前記第２系列は、前記第１系列から変換された拡散符号であり、 前記符号化は、前記信号列の拡散である、 請求項８記載の符号化処理装置。 【請求項10】 前記符号化は、前記信号列の暗号化である、請求項８記載の符号化処理装置。 【請求項11】 第１系列から変換された第２系列に基づいて、信号列の符号化を行う符号化部と、 前記符号化後の前記信号列を、他の装置に送信する送信部と、 を備え、 前記第１系列は、自己相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、均等分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 送信装置。 【請求項12】 前記第２系列は、前記第１系列から変換された拡散符号であり、 前記符号化は、前記信号列の拡散である、 請求項１１記載の送信装置。 【請求項13】 前記符号化は、前記信号列の暗号化である、請求項１１記載の送信装置。
発明の詳細な説明	【技術分野】 【0001】 本発明は、系列生成装置、符号化処理装置、送信装置に関する。 【背景技術】 【0002】 擬似乱数が使用される分野は、情報通信系、暗号系、計算機科学、経済学(数理ファイナンス)、地球科学(地球シミュレーション)、気象学、ゲノム・サイエンスと枚挙に暇がない。また、学術分野のみならず、高機能携帯端末(スマートフォン)、通信、金融と情報技術（ＩＴ)を融合させたフィンテック(電子決済、クラウド会計)、多元センサーのランダム制御（自動給水装置及び自動給水システム）を証左として、「擬似乱数は我々の社会生活に必要不可欠なインフラ技術の一つである」と言っても過言ではない。 【0003】 例えば、特許文献１には、区分単調増加マルコフ変換を用いて最大周期列を生成するアルゴリズムが開示されている。 【先行技術文献】 【0004】 【特許文献1】特開２０１１－２２７６３２号公報 【発明の概要】 【発明が解決しようとする課題】 【0005】 上述した特許文献１に開示されたアルゴリズムを用いることで、効率的に系列を生成することができるが、様々な分野において、相関特性および均等分布性を有する系列を生成することが望まれる。 【0006】 例えば、暗号、計算機科学などの分野では、時間ｔに関してｔ＝０で１、それ以外で０を取るようなデルタ関数的な規格化自己相関関数が要求される。また、情報通信、数理ファイナンスなどの分野では、短期に指数関数的に減少する自己相関特性、及び長周期に振動する自己相関特性を有する系列が必要とされる。すなわち、自己相関特性と均等分布を有し、しかも互いに無相関な系列（擬似乱数）が大量に必要になる。 【0007】 そこで、本発明の目的は、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量生成可能な系列生成装置、当該系列を用いる符号化処理装置、送信装置を提供することにある。 【課題を解決するための手段】 【0008】 本発明のある態様は、系列生成装置に関する。この系列生成装置は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第１系列を生成する生成部と、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、第１系列を第２系列に変換する変換部と、を備える。 【0009】 このような態様によると、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された第１系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて変換することにより、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することができる。 【0010】 本発明の別の態様は、符号化処理装置である。この符号化処理装置は、第１系列から変換された第２系列を、記憶する記憶部と、第２系列に基づいて、信号列を符号化する符号化部と、を備え、第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものであり、第２系列は、第１系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。 【0011】 本発明の別の態様は、送信装置である。この送信装置は、第１系列から変換された第２系列を、記憶する記憶部と、第２系列に基づいて、信号列を符号化する符号化部と、符号化された信号列を、他の装置に送信する送信部と、を備え、第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものであり、第２系列は、第１系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。 【0012】 なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として捉えることができる。 【発明の効果】 【0013】 本発明によれば、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することが可能である。 【図面の簡単な説明】 【0014】 【図1】図１は、傾きβ＝１＋√３を有するマルコフβ変換Ｔのグラフを示す図である。 【図2】図２は、Ｘ｛２２｝のグラフ表現Ｇを示す図である。 【図3】図３は、系列長５６のときの、ビット誤り生起確率のユーザ数依存性を示す図である。 【図4】図４は、系列長３２のときの、ビット誤り生起確率のユーザ数依存性を示す図である。 【図5】図５は、実施例１にかかる系列生成装置１００を示す図である。 【図6】図６は、実施例２にかかる符号化装置２００を示す図である。 【図7】図７は、実施例３にかかる送信装置３００を示す図である。 【図8】図８は、実施例４にかかる受信装置４００を示す図である。 【発明を実施するための形態】 【0015】 以下においては、まず本発明が適用される理論を説明した上で、実施例を用いて説明していくものとする。つまり説明は、以下の順序で行われる。 １．理論 １．１．緒言 １．２．有限タイプのシフト １．３．超離散力学系に基づく最大周期列 １．４．β変換に基づく指定された相関特性を有するマルコフ連鎖の実現 １．５．離散化β変換に基づく所望の相関特性と均等分布を有するマルコフ連鎖の実現 １．６．実験結果 １．７．一般の場合について ２．実施例 ２．１．実施例１ ２．２．実施例２ ２．３．実施例３ ２．４．実施例４ ３．その他 【0016】 ＜１．理論＞ ＜１．１．緒言＞ 擬似乱数が使用される分野は、情報通信系、暗号系、計算機科学、経済学(数理ファイナンス)、地球科学(地球シミュレーション)、気象学、ゲノム・サイエンスと枚挙に暇がない。また、学術分野のみならず、高機能携帯端末(スマートフォン)、通信、金融と情報技術（ＩＴ)を融合させたフィンテック(電子決済、クラウド会計)、多元センサーのランダム制御（自動給水装置及び自動給水システム）を証左として、「擬似乱数は我々の社会生活に必要不可欠なインフラ技術の一つである」と言っても過言ではない。 【0017】 要求される性能は、次ビット予測可能性、高次均等分布性、相関特性と、使用する目的に応じて種々挙げられる。本理論では、広い分野に要求される相関特性および均等分布性に注目する。暗号、計算機科学などでは時間ｔに関してｔ＝０で１、それ以外で０を取るようなデルタ関数的な規格化自己相関関数が要求される。一方、情報通信、数理ファイナンスなどでは、短期に指数関数的に減少する自己相関特性や長周期に振動する自己相関特性が必要とされる。さらに、暗号だけでなく通信システムにおいても均等分布を有するビット列が用いられる。その様な自己相関特性と均等分布を有し、しかも互いに無相関な擬似乱数が大量に必要である。斯様な要求に答えること、すなわち、任意に指定された自己相関特性と均等分布を有する互いに無相関な擬似乱数を大量に実現することが本理論の目的である。実用の一例として、スペクトル拡散多元接続（ＳＳＭＡ）通信システムを考え、実際の携帯通信システムに使用可能な最適スペクトル拡散符号を取り上げる。 【0018】 ＜１．２．有限タイプのシフト＞ 集合Σは有限アルファベットであるとする。全Σシフトは、 【数1】 で表される。これには、Σ上の離散位相から生ずる直積位相が付与される。 【0019】 シフト変換σ： 【数2】 は、 【数3】 で定義される。全 【数4】 シフトの閉シフト不変部分集合はサブシフトと呼ばれる。サブシフトＸに対して、Ｘ上のシフト変換をσＸで表す。これは、Σ上のσの、Ｘへの制限である。簡単のため、σＸよりむしろσ：Ｘ→Ｘと書くことにする。 【0020】 元ｕ＝ｕ１ｕ２…ｕｎ∈Σｎを長さｎ（ｎ≧１）のΣ上のブロックと呼ぶ、これを単にｎブロックとも言う。空ブロックを表すのにεを用いる。サブシフトＸに対して、Ｌｎ（Ｘ）はＸに属する点に現れるｎブロック全体の集合を表す。このとき、Ｘの言語は集合 【数5】 である。 ここで、Ｌ０（Ｘ）＝｛ε｝である。 【0021】 （有向）グラフＧ＝（Ｖ，Ａ）は頂点の有限集合Ｖと辺の有限集合Ａから成る。各辺ｅ∈Ａは、初期状態と呼ばれ、ｉ（ｅ）∈Ｖで表される頂点を出発し、終状態と呼ばれ、ｔ（ｅ）∈Ｖで表される頂点に到達する。 【0022】 （定義１） Ｇ＝（Ｖ，Ａ）はグラフであるとする。頂点ｕ，ｖ∈Ｖに対して、ａｕ，ｖは、初期状態ｕと終状態ｖを有するＧの辺の数を表すとする。このとき、Ｇの隣接行列はＡ＝（ａｕ，ｖ)ｕ，ｖ∈Ｖで定義される。隣接行列ＡがＧから構成されるのをＡ＝Ａ（Ｇ）またはＡ＝ＡＧで表す。逆に、ｋ×ｋ非負整数行列 【数6】 は，頂点集合｛０，１，…，ｋ－１｝と、初期状態ｉから終状態ｊへのｂｉ，ｊ個の相異なる辺を有するグラフＨを決定する。グラフＨがＢから構成されるのをＨ=Ｇ（Ｂ）またはＨ＝ＧＢで表す。Ａ＝Ａ（ＧＡ）となること、およびＧとＨ＝Ｇ（ＡＧ）がグラフ同型であることは注目に値する。 【0023】 与えられた非負整数行列Ａに対して、ＧＡ＝（Ｖ，Ａ）と置く。 【数7】 とする。このとき、σ：ＸＡ→ＸＡは、行列Ａによって決定される両側位相的マルコフ連鎖と呼ばれる。位相的マルコフ連鎖はまた有限タイプのシフト（ＳＦＴ）とも呼ばれる。ＳＦＴとは禁止語の有限集合によって表現することができるようなサブシフトである。与えられた禁止語の有限集合Ｆに対して、ＳＦＴを表すのにＸＦを用いる。 【0024】 ＜１．３．超離散力学系に基づく最大周期列＞ 集合Ｅの濃度（有限の場合には要素数）を表すのに｜Ｅ｜を用いる。 【0025】 （定義２） Ｔ：［０，１）→［０，１）とする。Ｐは点０＝ａ０＜ａ１＜…＜ａ｜Ｐ｜＝１で与えられる区間［０，１）の分割であるとする。ｉ＝１，…，｜Ｐ｜に対して、Ｉｉ＝（ａｉ－１，ａｉ）とし、ＴのＩｉへの制限をＴ｜Ｉｉで表す。Ｔ｜Ｉｉが、Ｉｉから、Ｐの区間の閉包のある連結和集合の内部の上への同相写像であるとき、Ｔはマルコフであると言われる。このとき、分割 【数8】 は、Ｔに関するマルコフ分割と呼ばれる。 【0026】 既約かつ非周期的マルコフ変換Ｔに対して、Ｔに関するマルコフ分割Ｐが定まる。このとき、各部分区間Ｉ∈Ｐを一つの辺ｅ（Ｉ）に対応させると、辺集合Ａを得る。Ａに同伴して、頂点集合Ｖが 【数9】 で与えられる。Ｐの元の各順序対（Ｉ，Ｊ）に対して、ｔ（ｅ（Ｉ））＝ｉ（ｅ（Ｊ））が成り立つのは、丁度Ｊ⊂Ｔ｜Ｉ（Ｉ）のときである。斯くして、マルコフ変換を表現するグラフＧ＝（Ｖ，Ａ）を得る。一般に、得られたグラフはオイラーグラフではない。 【0027】 Ｈ＝（Ｖ，Ｂ）は、最大辺数を有するＧの全域オイラー部分グラフであるとする。既約かつ非周期的マルコフ変換を考えているので、頂点集合ＶはＧからＨへの変形に対して不変である。上で述べた、ＰとＡの間の一対一対応の下で、Ｂに対応する部分分割Ｑを得る。このとき、離散化マルコフ変換 【数10】 は、全てのＩ∈Ｑに対して、 【数11】 を満たす置換 【数12】 によって定義される。 【0028】 離散化マルコフ変換に基づく最大周期列は、丁度Ｈ上のオイラー回路であり、その長さは｜Ｂ｜で与えられる。Ｔに関するマルコフ分割Ｐが与えられるとき、｜Ｑ｜！個の離散化マルコフ変換を得る。任意の置換は互いに素な巡回置換の積で（順序を除いて）一意に表されることは良く知られている。この事実に鑑み、離散化マルコフ変換 【数13】 が基本変換Ｔ：［０，１）→［０，１）を近似すると見做さられるのは、丁度一つの巡回置換として表現されるときに限る。 この場合、離散化マルコフ変換 【数14】 それ自身は最大周期列ｗとして見ることができる。さらに、最大周期列ｗに対して、両側無限列ｗ∞＝…ｗｗｗ…を考えれば、巡回置換 【数15】 は 【数16】 上のシフトと見做すことができる。 【0029】 離散化マルコフ変換に基づく最大周期列は 【数17】 に属するブロックに他ならないことが観察される。これは離散化マルコフ変換 【数18】 が単に基本変換Ｔ：［０，１）→［０，１）の近似の一段階に過ぎないことを示唆する。より精密な近似を定義するために、記号力学系から高次辺グラフという概念を導入する［参考文献１］。 【0030】 （定義３） Ｇはグラフであるとする。ｎ≧２に対して、Ｇのｎ次高次辺グラフＧ［ｎ］は頂点集合 【数19】 を持ち、また、ｅ２ｅ３…ｅｎ－１＝ｆ１ｆ２…ｆｎ－２のとき(但しｎ＝２の場合はｔ（ｅ１）＝ｉ（ｆ１）のとき)には常にｅ１ｅ２…ｅｎ－１からｆ１ｆ２…ｆｎ－１へ丁度一つの辺を含むが、それ以外のときには何も無いような、辺集合を持つと定義される。辺はｅ１ｅ２ｅ３…ｅｎ－１ｆｎ－１＝ｅ１ｆ１ｆ２…ｆｎ－１と名付けられる。ｎ＝１に対して、Ｇ［１］＝Ｇと置く。 【0031】 グラフＧはマルコフ変換を表すとする。このとき、Ｇの高次辺グラフの列 【数20】 を得る。各ｎ≧１に対して、 【数21】 は最大辺数を有するＧ［ｎ］の全域オイラー部分グラフを表すとする。各々は、離散化マルコフ変換 【数22】 を導く。最大周期列の長さは｜Ｂｎ｜で与えられることに注意しておく。 【0032】 ここまで，離散化される変換として、一般の既約かつ非周期的マルコフ変換Ｔを考えてきた。以下、離散化される変換Ｔに対して、次の単調性を要求する。［０，１］のある分割０＝ｘ０＜ｘ１＜…＜ｘｋ＝１が存在して、各整数ｉ＝１，…，ｋに対して、Ｔの区間［ｘｉ－１，ｘｉ）への制限は単調増加関数である。 【0033】 既約かつ非周期的マルコフ変換Ｔがこの条件を満たすとき、Ｔを区分的単調増加（ＰＭＩ）マルコフ変換と呼ぶ。以下、離散化される変換は、その様な単調性を有するとしよう。ここで、区分的単調増加マルコフ変換は実用的に十分広いクラスのマルコフ変換を含むことを強調しておく。実際、ＰＭＩマルコフ変換は、本理論で考える黄金平均変換やβ変換だけでなく、Ｂｅｒｎｏｕｌｌｉ変換、Ｋａｌｍａｎのマルコフ変換［参考文献２］、および［参考文献３］で定義されたｋ（≧２）方有尾シフト変換を含む。 【0034】 ＰＭＩマルコフ変換に対しては、離散化された変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えた［参考文献４］。 【0035】 ＜１．４．β変換に基づく指定された相関特性を有するマルコフ連鎖の実現＞ 非同期スペクトル拡散多元接続（ＳＳＭＡ）通信システムのおけるビット誤り生起確率に関して、最適Ｍ（≧２）相マルコフ連鎖拡散符号が設計された［参考文献５］。最適拡散符号を生成するマルコフ連鎖は、その確率行列の第二固有値が－２＋√３を有することでＭに無関係に特徴付けられる。簡単のため、以下Ｍ＝２の場合に制限するが、［参考文献５］の結果を用いることにより、Ｍ≧３の場合も同様に得られる。 【0036】 Ｍ＝２の場合、最適二値マルコフ連鎖拡散符号系列は 【数23】 を有する｛１，－１｝に値を取る定常マルコフ連鎖系列 【数24】 として特徴付けられる。ここで、確率変数Ｚに対して、 【数25】 はＺの期待値を表す。 【0037】 系列に対する相関関数は、二つの系列の間の類似性または関係性の測度であり、数学的に次の様に定義される。 （定義４） ｛－１，１｝上の系列 【数26】 と 【数27】 に対する、遅れ時間 【数28】 の正規化相互相関関数は 【数29】 で定義される。ここで、 【数30】 である。整数ａとｂ（≧１）に対して、ａ（ｍｏｄ ｂ）は法ｂに関するａの最小剰余を表す。Ｘ＝Ｙのとき 【数31】 を正規化自己相関関数と呼び、単に 【数32】 で表す。 所望の 【数33】 を有する系列Ｘを構成するために［参考文献６］で定義されたＰｅｒｒｏｎ数を導入する。 【0038】 （定義５） 数λがＰｅｒｒｏｎ数であるのは、次を満たすときである。ｉ）λは正の代数的整数である。およびｉｉ）λ以外の全ての代数的共役μに対して、λ＞｜μ｜が成り立つ。Ｐｅｒｒｏｎ数全体の集合を 【数34】 で表す。 【0039】 行列Ａは非負整数行列であるとする。ある整数ｎに対して、Ａｎ＞０ならば、Ａは原始的であると言われる。ここで、行列Ｂに対して、Ｂ＞０はＢが正行列であることを表す。Ａが原始的であるのは、Ａが既約かつ非周期的であることと同等である。原始的行列Ａに対して、ＡのＰｅｒｒｏｎ－Ｆｒｏｂｅｎｉｕｓ固有値をλＡで表す。斯くして、Ｐｅｒｒｏｎ数は次の定理により特徴付けられる。 【0040】 定理１（Ｌｉｎｄ ［参考文献６］） 【数35】 はある原始的Ａに対してλ＝λＡのときまたそのときに限る。 所望の相関関数はパラメータを一個（すなわち－２＋√３）しか持たないので、次数２を有する 【数36】 を考えれば十分である。一般に、パラメータ数ｍに対して、次数ｍ＋１を考えればよい。次数２を有するλの、Ｑ上最小多項式は 【数37】 で定義される。ここで、 【数38】 である。多項式ｆ（ｔ）のコンパニオン行列は、 【数39】 で与えられる。コンパニオン行列Ｂの特性多項式と最小多項式はｆ（ｔ）に等しいことに注意する。 【0041】 β変換は、次のように定義される。すなわち、β＞１に対して、β変換Ｔ：［０，１］→［０，１］はＴ（ｘ）＝βｘ（ｍｏｄ １），ｘ∈［０，１］で定義される。ここでｘ＝y（ｍｏｄ １）は１を法とする実数上の合同、すなわち、ｘ－ｙが整数であることを表す。さらに、β変換が（定義２）を満たすとき、マルコフβ変換と呼ばれる。 【0042】 マルコフβ変換に行列Ｂを同伴するために、０＜ｃ２≦ｃ１とする。このとき、コンパニオン行列Ｂに同伴するマルコフβ変換の（ｃ１＋１）×（ｃ１＋１）隣接行列Ａは 【数40】 で与えられる。 【0043】 実数値を二値に符号化する写像Ψ：［０，１）→｛１，－１｝を 【数41】 で定義する。ｎ＝０，１，２，…に対して、変換Ｔのｎ回反復Ｔｎ（ｘ）は、Ｔ０（ｘ）＝ｘ及びＴｎ（ｘ）＝Ｔｎ－１（Ｔ（ｘ））により帰納的に定義される。このとき、Ｚｎ＝Ψ（Ｔｎ（ｘ））と置くことにより、区間［０，１）に属するほとんど全てのｘに対して、｛１，－１｝に値を取るマルコフ連鎖系列 【数42】 が生成される。斯くして、 【数43】 を得る。ここで、 【数44】 はλの代数的共役である。 【0044】 条件０＜ｃ２≦ｃ１の下、方程式 【数45】 の整数解（ｃ１，ｃ２）はｃ１＝ｃ２＝２として一意に与えられる。 【0045】 結局、傾きβ＝１＋√３を有するマルコフβ変換Ｔを得る。β＝１＋√３＝λはｔ２－２ｔ－２＝０の正の解である。図１にＴのグラフを示す。 【0046】 相関特性 【数46】 を有するような、｛１，－１｝に値を取るマルコフ連鎖系列 【数47】 をうまく得た。しかしながら、連鎖の定常分布は 【数48】 で与えられ、一様分布でないため、 【数49】 となり、所望の零でない。 【0047】 次に、得られた最適二値マルコフ連鎖拡散符号の相関特性を変更すること無く、スライディング・ブロック符号を用いて、系列の分布（p１，p２）を一様分布に変換する。 【0048】 ＜１．５．離散化β変換に基づく所望の相関特性と均等分布を有するマルコフ連鎖の実現＞ 基数β＝１＋√３を用いるとき、区間［０，１）に属する実数ｘのβ進展開はＳＦＴ 【数50】 の右側無限列として与えられる。ここでΣ＝｛０，１，２｝及びＦ＝｛２２｝である。実数ｘ∈［０，１）のβ進展開から得られる右側無限列は、図１に示したβ変換Ｔの、初期値をｘとする。実数値解軌道の記号力学的表現である。ＳＦＴ ＸＦ のグラフ表現Ｇは、図２に示すように与えられる。同時に、ＧはＴの表現でもある。 【0049】 初期グラフをＧ＝Ｇ［２］として、Ｇの高次辺グラフの列 【数51】 を得る。各ｎ≧２に対して、Ｈｎは最大辺数を有するＧ［ｎ］の全域オイラー部分グラフを表すとする。各オイラー部分グラフＨｎのオイラー回路が、傾きβ＝１＋√３を有するβ変換Ｔの超離散化に基づく最大周期列である。図２において、Ｇはオイラーグラフであることがわかる。この場合、Ｇ＝Ｇ［２］＝Ｈ２を得る。しかしながら、ｎ（≧３）に対して、Ｇ［ｎ］はオイラーグラフであるとは限らない。実際、Ｈ３はＧ［３］の真部分グラフである。 これを 【数52】 で表す。任意のｎ（≧３）に対して、 【数53】 となるのが確認される。 【0050】 図２のオイラー部分グラフＨ２において、例えば、最大周期列００１０２１１２０を得る。 最大周期列の長さ｜Ｂｎ｜は 【数54】 で与えられる［参考文献７］。ここで、 【数55】 はβの代数的共役である。 【0051】 以下、傾きβ＝１＋√３を有するβ変換の超離散化に基づき、最適二値マルコフ連鎖拡散符号を構成する。集合Ｌ（ＸＦ）＼｛ε｝上の全順序関係≦を次で定義する。すなわち、Ｌ（ＸＦ）に属する任意のｕ＝ｕ１…ｕｍ（ｍ≧１）とｖ＝ｖ１…ｖｎ（ｎ≧１）に対して、ｕ≦ｖは 【数56】 のときまたそのときに限る。 簡単のため、最大周期列の長さ｜Ｂｎ｜を表すのにＬを用いる。Ｌブロックｖ＝ｖ１ｖ２…ｖＬ∈｛０，１，２｝Ｌに対して、ブロック符号Φ：｛０，１，２｝Ｌ→｛１，－１｝を 【数57】 で定義する。 【0052】 Ｌブロック全体の集合｛０，１，２｝Ｌ上のシフト変換をＳで表す。すなわち、ｖ＝ｖ１ｖ２…ｖＬ∈｛０，１，２｝Ｌに対して、 【数58】 と表す。斯くして、周期Ｌの周期列に対して、 【数59】 で定義されるスライディング・ブロック符号φを得る。ここで、ブロックｕに対して、ｕ∞＝…ｕｕｕ…である。 【0053】 系列Ｘは、β＝１＋√３を有する離散化マルコフβ変換に基づく、長さＬ＝｜Ｂｎ｜の、Σ＝｛０，１，２｝上の最大周期列であるとする。スライディング・ブロック符号φを用いて、最適二値マルコフ連鎖拡散符号系列Ｙが 【数60】 により実現される。 【0054】 長さ｜Ｂｎ｜の最適二値マルコフ連鎖拡散符号の例を示す。 （例１） ｎ＝３のとき、Ｌ＝２０であり、 【数61】 を得る。ここで、表記を簡単にするため、右辺の０は－１を表す。 【0055】 ［参考文献８］の結果を最適二値マルコフ連鎖拡散符号に適用して、次の評価を得る。 （定理２） 【数62】 を得る。 これは 【数63】 を示唆する。ここで、 【数64】 はランダウの記号である。 【0056】 ＜１．６．実験結果＞ 最大周期列の長さ｜Ｂｎ｜、Ｈｎにおける｛０，１，２｝上の最大周期列の総数νｎ、及び実現された最適二値マルコフ連鎖拡散符号の総数 【数65】 をそれぞれ表１に示す。 【表1】 【0057】 ｎ＝４のとき、最大周期列の長さは｜Ｂｎ｜＝５６となる。この場合に、離散化β変換に基づいて実現された最適二値マルコフ連鎖拡散符号を用いた非同期ＳＳＭＡ通信システムのおけるビット誤り生起確率の、ユーザ数依存性を図３に示す。現在、実用化されているＧｏｌｄ符号の系列長は３２である。ｎ＝４のとき、長さ｜Ｂｎ｜＝５６の最適二値マルコフ連鎖拡散符号に対して、開始点をランダムに選び、そこから長さ３２で系列を打ち切ることにより、長さ３２の系列が得られる。このようにして、長さ５６の最適二値マルコフ連鎖拡散符号から長さ３２の系列を抽出した場合の結果を図４に示す。 【0058】 図３及び図４の各々において、曲線は［参考文献９］で与えられる中心極限定理（ＣＬＴ）に基づく理論評価式を表し、点×は数値実験結果を表す。いずれにおいても両者は良く一致していることが確認される。同様にして、任意の長さの擬似乱数を得ることができる。 【0059】 ＜１．７．一般の場合について＞ これまで、最適二値マルコフ連鎖拡散符号を実現するため、 【数66】 において、ρ＝－２＋√３の場合を考えた。ρが一般の場合には上記（１）式と同様に、 【数67】 の整数解（ｃ１，ｃ２）を求めることにより、傾きβが得られる。 【0060】 簡単のためｃ１＋１＝ｋとおく。離散化β変換により、｛０，１，…，ｋ－１｝上の最大周期列を得る。残るはブロック符号Φの定義だけである。 【0061】 貪欲算法による実数ｘ∈［０，１］のβ進展開をｄβ（ｘ）で表す。｜Ｂｎ｜＝Ｌとおく。Ｌブロックｖ＝ｖ１ｖ２…ｖＬ∈｛０，１，２｝Ｌに対して、ブロック符号Φ：｛０，１，…，ｋ－１｝Ｌ→｛１，－１｝を次のように定義すればよい。 【数68】 【数69】 【0062】 以下に、参考文献を列挙する。 ［参考文献１］ D. Lind and B. Marcus, Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. ［参考文献２］ R. E. Kalman, “Nonlinear aspects of sampled-data control systems”, Proc. Symp. Nonlinear Circuit Analysis VI, pp. 273-313, 1956. ［参考文献３］ G. Mazzini, G. Setti, and R. Rovatti, “Chaotic Complex Spreading Sequences for Asynchronous DS-CDMA Part I: System Modeling and Results” IEEE Trans. Circuit Syst.-I vol. CAS-44, no.10, pp.937-947, 1997. ［参考文献４］ H. Fujisaki, “An Algorithm For Generating All Full-Length Sequences Which Are Based On Discretized Markov Transformations,” NOLTA, IEICE, vol. 1, pp. 166-175, 2010. ［参考文献５］ H. Fujisaki and H. Sugimori, “Phase-Shift-Free M-Phase Spreading Sequences of Markov Chains,” IEEE Trans. on Circuit and Systems Part I, vol.CAS-55, pp. 876-882, 2008. ［参考文献６］ D. A. Lind, “The entropies of topological Markov shifts and a related class of algebraic integers,” Ergodic Theory and Dynamical Systems, vol. 4, pp. 283 - 300, 1984. ［参考文献７］ H. Fujisaki, “On the topological entropy of the discretized Markov β-transformations,” to appear in IEICE Trans. Fundamentals, vol. E99-A, total 10 pages, 2016. ［参考文献８］ H. Fujisaki, “Correlational Properties of the Full-Length Sequences Based on the Discretized Markov β-transformations,” to appear in NOLTA, IEICE, vol. 7, total 11 pages, 2017. ［参考文献９］ H. Fujisaki and G. Keller, “The central limit theorem for the normalized sums of the MAI for SSMA communication systems using spreading sequences of Markov chains,” IEICE Trans. Fundamentals, vol. E89-A, no.9, pp. 2307-2314, 2006. 【0063】 ＜２．実施例＞ ＜２．１．実施例１＞ 次に、実施例１を用いて、本発明の実施の形態について説明する。図５は、実施例１にかかる系列生成装置１００を示す図である。系列生成装置１００は、記憶部１１０、生成部１３０、及び変換部１５０を含む。系列生成装置１００は、所定の自己相関特性と均等分布を有する互いに無相関な系列を生成する。 【0064】 （記憶部１１０） 記憶部１１０は、生成部１３０と変換部１５０とそれぞれ接続され、生成部１３０により生成された系列（第１の系列）を記憶し、記憶している情報を変換部１５０に出力する。 【0065】 （生成部１３０） 生成部１３０は、上述した＜理論＞に従い、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第１系列を生成する。まず、所定の相関特性は、下記式のρにより与えられる。 【数70】 ここで、Ｚは第１系列の確率変数である。具体的なρの値は、ユーザが例えば記憶部１１０に予め記憶しておき、記憶した情報（ρの値）を生成部１３０に出力することができる。 【0066】 このようにしてρが与えられることで、生成部１３０は、下記式において整数解（ｃ１，ｃ２）を求めることにより、区分単調増加マルコフ変換の傾きβを得ことができる。 【数71】 具体例として、ρ＝－２＋√３の場合には、区分単調増加マルコフ変換の傾きβは、１＋√３となる。 【0067】 生成部１３０は、Ｚｎ＝Ψ（Ｔｎ（ｘ））のＴを、区分単調増加マルコフ変換の傾きβとすることで、下記式により表される第１系列を生成する。生成した第１系列は、記憶部１１０に記憶される。 【数72】 【0068】 具体例で挙げたようにＴを傾き１＋√３のβ変換とした場合、区間［０，１）に属するほとんど全てのｘに対して、所定ρ＝－２＋√３の相関特性を有し、｛１，－１｝に値を取る第１系列を生成することができる。 【0069】 （変換部１５０） 変換部１５０は、上述した＜理論＞に従い、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、第１系列を第２系列に変換する。 【0070】 所定の分布は、均等分布、言い換えれば一様分布である。一様分布を満たす限り、 【数73】 となる。 【0071】 一様分布と、区分単調増加マルコフ変換の傾きとに基づいて得られる変換条件は、下記式のブロック符号Φにより表される。 【数74】 【数75】 【0072】 具体例として、区分単調増加マルコフ変換の傾きβが１＋√３の場合には、ブロック符号Φは下記式により表される。 【数76】 【0073】 変換部１５０は、変換条件を表すブロック符号Φに基づいて、下記式により第１系列Ｘを第２系列Ｙに変換する。 【数77】 【0074】 ここで、Ｓは、Ｌブロック全体の集合｛０，１，２｝Ｌ上のシフト変換であって、ｖ＝ｖ１ｖ２・・・ｖＬ∈｛０，１，２｝Ｌに対して下記式で表される。 【数78】 【0075】 以上のような構成からなる系列生成部１００は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された第１系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて変換することにより、任意に指定された自己相関特性と均等分布を有する互いに無相関な第２系列を大量に生成することができる。 【0076】 第２系列は、拡散符号として用いることができる。つまり、ＣＤＭＡ方式などの無線通信の拡散符号として用いることができる。また、第２系列は、暗号化又は復号（decryption）のための系列として用いることができる。 【0077】 ＜２．２．実施例２＞ 次に、実施例２を用いて、本発明の実施の形態について説明する。図６は、実施例２にかかる符号化処理装置２００を示す図である。符号化処理装置２００は、記憶部２１０、及び符号化部２３０を含む。符号化処理装置２００は、上述した系列生成部１００により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第２系列を利用して、任意の信号列の符号化を行う。 【0078】 （記憶部２１０） 記憶部２１０は、上述した系列生成装置１００により第１系列から変換された第２系列を記憶し、記憶している情報を符号化部２３０に出力する。ここで、上述したように、第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第２系列は、第１系列を、所定の分布（均等分布）と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。 【0079】 （符号化部２３０） 符号化部２３０は、記憶部２１０から第２系列を読み出し、読み出した第２系列に基づいて信号列の符号化を行って出力する。 【0080】 具体的に、符号化処理装置２００が、ＣＤＭＡ方式で通信を行う用途で用いられる場合には、第２の系列は、第１系列から変換された拡散符号であり、符号化部２３０は、信号列を拡散する。 【0081】 また、符号化処理装置２００が、暗号化を行う用途で用いられる場合には、符号化部２３０は、信号列を暗号化する。 【0082】 以上のような構成からなる符号化処理装置２００は、記憶部２１０が、自己相関特性と均等分布を有する互いに無相関な第２系列を大量に記憶することができる。このため、例えば、ＣＤＭＡ方式の無線通信において同一の周波数帯域内で２つ以上の複数の通信を行う際に、第２系列を用いた拡散を行った信号列を用いて通信することで、ビット誤りを少なくして信頼性を高めることができる。また、符号化処理装置２００は、第２系列を用いて信号列を暗号化することで、暗号の信頼性を高めることができる。 【0083】 ＜２．３．実施例３＞ 次に、実施例３を用いて、本発明の実施の形態について説明する。図７は、実施例３にかかる送信装置３００を示す図である。 【0084】 送信装置３００は、記憶部３１０、符号化部３３０、及び送信部３５０を含む。送信装置３００は、上述した系列生成部１００により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第２系列を利用して、任意の信号列を符号化して、他の装置へ送信する。 【0085】 （記憶部３１０） 記憶部３１０は、上述した系列生成装置１００により第１系列から変換された第２系列を記憶し、記憶している情報を符号化部３３０に出力する。ここで、上述したように、第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第２系列は、第１系列を、所定の分布（均等分布）と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。 【0086】 （符号化部３３０） 符号化部３３０は、記憶部３１０から第２系列を読み出し、読み出した第２系列に基づいて信号列の符号化を行って送信部３５０に出力する。具体的に、第２の系列は第１系列から変換された拡散符号であり、符号化部３３０は、第２系列を用いて信号列の拡散を行う。なお、拡散に代えて暗号化を行ってもよい。すなわち、符号化部３３０は、第２系列を用いて信号列の暗号化を行ってもよい。 【0087】 （送信部３５０） 送信部３５０は、符号化部３３０により符号化（拡散）された信号列を無線信号に変換して、他の装置に送信する。 【0088】 以上のような構成からなる送信装置３００は、記憶部３１０が、自己相関特性と均等分布を有する互いに無相関な第２系列を大量に記憶することができ、このような第２系列を用いて信号列を拡散して他の装置に送信することができる。 【0089】 例えばＣＤＭＡ方式の無線通信では、同一の周波数帯域内で２つ以上の複数の通信を行う際にビット誤りを軽減する観点から、長周期の系列を大量に用いることが必要となる。このため、送信装置３００では、上述したように、第２系列を用いて信号列を拡散して他の装置に送信することで、同一の周波数帯域内で２つ以上の複数の通信を行う際に、ビット誤りを少なくして信頼性を高めることができる。 【0090】 ＜２．４．実施例４＞ 次に、実施例４を用いて、本発明の実施の形態について説明する。図８は、実施例４にかかる受信装置４００を示す図である。 【0091】 受信装置４００は、記憶部４１０、受信部４３０、及び復号部４５０を含む。受信装置４００は、上述した系列生成部１００により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第２系列を利用して、符号化された信号列を復号する。 【0092】 （記憶部４１０） 記憶部４１０は、上述した系列生成装置１００により第１系列から変換された第２系列を記憶し、記憶している情報を復号部４５０に出力する。ここで、上述したように、第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第２系列は、第１系列を、所定の分布（均等分布）と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。 【0093】 （受信部４３０） 受信部４３０は、他の装置から、第２系列に基づいて符号化された信号列の無線信号を受信して復号部４５０に出力する。 【0094】 （復号部４５０） 復号部４５０は、記憶部３１０から第２系列を読み出し、読み出した第２系列に基づいて、受信部４３０が受信した信号列を復号（decoding）する。具体的に、第２の系列は第１系列から変換された拡散符号であり、復号部４５０は、第２系列を用いて信号列の逆拡散を行う。なお、逆拡散に限らず、信号列が暗号化されている場合には、復号部４５０は、第２系列を用いて信号列の復号（decryption）を行ってもよい。 【0095】 以上のような構成からなる受信装置４００は、記憶部４１０が、自己相関特性と均等分布を有する互いに無相関な第２系列を大量に記憶することができ、このような第２系列を利用して信号列を逆拡散することができる。 【0096】 例えばＣＤＭＡ方式の無線通信では、同一の周波数帯域内で２つ以上の複数の通信を行う際にビット誤りを軽減する観点から、長周期の系列を大量に用いることが必要となる。このため、受信装置４００では、上述したように、第２系列を用いて信号列を逆拡散することで、同一の周波数帯域内で２つ以上の複数の通信を行う際に、ビット誤りを少なくして信頼性を高めることができる。 【0097】 ＜３．その他＞ 以上、本発明を実施の形態をもとに説明した。本発明は上述した実施例並びに各実施例の内容に限定されるものではなく、本発明の要旨の範囲内において種々に変形して実施をすることが可能である。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。 【0098】 例えば、以下の発明も、本発明の態様として捉えることができる。 【0099】 （発明１） 第１系列から変換された第２系列に基づいて符号化が行われた信号列を、他の装置から受信する受信部と、 前記第２系列に基づいて、前記受信した信号列の復号を行う復号部と、 を備え、 前記第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 受信装置。 （発明２） 前記第２系列は、前記第１系列から変換された拡散符号であり、 前記符号化は、拡散であり、 前記復号は、前記受信した信号列の逆拡散である、 （発明１）の受信装置。 （発明３） 前記符号化は、暗号化であり、 前記復号（decoding）は、前記信号列の復号（decryption）である、（発明１）記載の受信装置。 （発明４） 所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第１系列を生成することと、 所定の分布と前記区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、前記第１系列を第２系列に変換することと、 を含む系列生成方法。 （発明５） 第１系列から変換された第２系列を取得することと、 前記第２系列に基づいて、信号列の符号化を行うことと、 を含み、 前記第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 符号化処理方法。 （発明６） 第１系列から変換された第２系列に基づいて、信号列の符号化を行うことと、 前記符号化後の前記信号列を、他の装置に送信することと、 を含み、 前記第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 送信方法。 （発明７） 第１系列から変換された第２系列に基づいて符号化が行われた信号列を、他の装置から受信することと、 前記第２系列に基づいて、前記受信した信号列の復号を行うことと、 を含み、 前記第１系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、 前記第２系列は、前記第１系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、 受信方法。 【産業上の利用可能性】 【0100】 任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することが可能である。 【符号の説明】 【0101】 １００ 系列生成装置 １１０、２１０、３１０、４１０ 記憶部 １３０ 生成部 １５０ 変換部 ２００ 符号化装置 ２３０、３３０ 符号化部 ３５０ 送信部 ４３０ 受信部 ４５０ 復号部
図面	【図1】 【図2】 【図3】 【図4】 【図5】 【図6】 【図7】 【図8】