TOP > 国内特許検索 > 系列生成装置、符号化処理装置、送信装置 > 明細書

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

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2018-072867 (P2018-072867A)
公開日 平成30年5月10日(2018.5.10)
発明の名称または考案の名称 系列生成装置、符号化処理装置、送信装置
国際特許分類 G06F   7/58        (2006.01)
H04J  13/16        (2011.01)
FI G06F 7/58 620
H04J 13/16
請求項の数または発明の数 14
出願形態 OL
全頁数 30
出願番号 特願2016-207576 (P2016-207576)
出願日 平成28年10月24日(2016.10.24)
発明者または考案者 【氏名】藤崎 礼志
出願人 【識別番号】504160781
【氏名又は名称】国立大学法人金沢大学
個別代理人の代理人 【識別番号】100141519、【弁理士】、【氏名又は名称】梶田 邦之
【識別番号】100172199、【弁理士】、【氏名又は名称】松山 浩也
【識別番号】100201374、【弁理士】、【氏名又は名称】福澤 昌俊
審査請求 未請求
要約 【課題】任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成可能な系列生成装置、当該系列を利用する符号化装置、送信装置、及び受信装置を提供する。
【解決手段】系列生成装置100は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第1系列を生成する生成部130と、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、第1系列を第2系列に変換する変換部150と、を備える。
【選択図】図5
特許請求の範囲 【請求項1】
所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第1系列を生成する生成部と、
所定の分布と前記区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、前記第1系列を第2系列に変換する変換部と、
を備える系列生成装置。
【請求項2】
前記所定の分布は、均等分布である、請求項1記載の系列生成装置。
【請求項3】
前記所定の相関特性は、下記式のρである、請求項1又は2記載の系列生成装置。
【数1】
JP2018072867A_000082t.gif
ここで、Zは、前記第1系列の確率変数である。
【請求項4】
前記変換部は、下記式により、前記第1系列を前記第2系列に変換する、請求項1乃至3のうちいずれか1項記載の系列生成装置。
【数2】
JP2018072867A_000083t.gif
ここで、Xは前記第1系列であり、Φは前記変換条件を表すブロック符号であり、Yは前記第2系列であり、Sは、Lブロック全体の集合{0,1,2}上のシフト変換であって、v=v・・・v∈{0,1,2}に対して下記式で表される。
【数3】
JP2018072867A_000084t.gif

【請求項5】
前記変換条件を表すブロック符号は、下記式で定義される、請求項4記載の系列生成装置。
【数4】
JP2018072867A_000085t.gif
【数5】
JP2018072867A_000086t.gif

【請求項6】
前記変換条件を表すブロック符号は、下記式で定義される、請求項4又は5記載の系列生成装置。
【数6】
JP2018072867A_000087t.gif

【請求項7】
前記第2系列は、拡散符号である、請求項1乃至6のうちいずれか1項記載の系列生成装置。
【請求項8】
前記第2系列は、暗号化又は復号のための系列である、請求項1乃至6のうちいずれか1項記載の系列生成装置。
【請求項9】
第1系列から変換された第2系列を、記憶する記憶部と、
前記第2系列に基づいて、信号列の符号化を行う符号化部と、
を備え、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
符号化処理装置。
【請求項10】
前記第2系列は、前記第1系列から変換された拡散符号であり、
前記符号化は、前記信号列の拡散である、
請求項9記載の符号化処理装置。
【請求項11】
前記符号化は、前記信号列の暗号化である、請求項9記載の符号化処理装置。
【請求項12】
第1系列から変換された第2系列に基づいて、信号列の符号化を行う符号化部と、
前記符号化後の前記信号列を、他の装置に送信する送信部と、
を備え、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
送信装置。
【請求項13】
前記第2系列は、前記第1系列から変換された拡散符号であり、
前記符号化は、前記信号列の拡散である、
請求項12記載の送信装置。
【請求項14】
前記符号化は、前記信号列の暗号化である、請求項12記載の送信装置。

発明の詳細な説明 【技術分野】
【0001】
本発明は、系列生成装置、符号化処理装置、送信装置に関する。
【背景技術】
【0002】
擬似乱数が使用される分野は、情報通信系、暗号系、計算機科学、経済学(数理ファイナンス)、地球科学(地球シミュレーション)、気象学、ゲノム・サイエンスと枚挙に暇がない。また、学術分野のみならず、高機能携帯端末(スマートフォン)、通信、金融と情報技術(IT)を融合させたフィンテック(電子決済、クラウド会計)、多元センサーのランダム制御(自動給水装置及び自動給水システム)を証左として、「擬似乱数は我々の社会生活に必要不可欠なインフラ技術の一つである」と言っても過言ではない。
【0003】
例えば、特許文献1には、区分単調増加マルコフ変換を用いて最大周期列を生成するアルゴリズムが開示されている。
【先行技術文献】
【0004】

【特許文献1】特開2011-227632号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
上述した特許文献1に開示されたアルゴリズムを用いることで、効率的に系列を生成することができるが、様々な分野において、相関特性および均等分布性を有する系列を生成することが望まれる。
【0006】
例えば、暗号、計算機科学などの分野では、時間tに関してt=0で1、それ以外で0を取るようなデルタ関数的な規格化自己相関関数が要求される。また、情報通信、数理ファイナンスなどの分野では、短期に指数関数的に減少する自己相関特性、及び長周期に振動する自己相関特性を有する系列が必要とされる。すなわち、自己相関特性と均等分布を有し、しかも互いに無相関な系列(擬似乱数)が大量に必要になる。
【0007】
そこで、本発明の目的は、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量生成可能な系列生成装置、当該系列を用いる符号化処理装置、送信装置を提供することにある。
【課題を解決するための手段】
【0008】
本発明のある態様は、系列生成装置に関する。この系列生成装置は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第1系列を生成する生成部と、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、第1系列を第2系列に変換する変換部と、を備える。
【0009】
このような態様によると、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された第1系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて変換することにより、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することができる。
【0010】
本発明の別の態様は、符号化処理装置である。この符号化処理装置は、第1系列から変換された第2系列を、記憶する記憶部と、第2系列に基づいて、信号列を符号化する符号化部と、を備え、第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものであり、第2系列は、第1系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。
【0011】
本発明の別の態様は、送信装置である。この送信装置は、第1系列から変換された第2系列を、記憶する記憶部と、第2系列に基づいて、信号列を符号化する符号化部と、符号化された信号列を、他の装置に送信する送信部と、を備え、第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものであり、第2系列は、第1系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。
【0012】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として捉えることができる。
【発明の効果】
【0013】
本発明によれば、任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することが可能である。
【図面の簡単な説明】
【0014】
【図1】図1は、傾きβ=1+√3を有するマルコフβ変換Tのグラフを示す図である。
【図2】図2は、X{22}のグラフ表現Gを示す図である。
【図3】図3は、系列長56のときの、ビット誤り生起確率のユーザ数依存性を示す図である。
【図4】図4は、系列長32のときの、ビット誤り生起確率のユーザ数依存性を示す図である。
【図5】図5は、実施例1にかかる系列生成装置100を示す図である。
【図6】図6は、実施例2にかかる符号化装置200を示す図である。
【図7】図7は、実施例3にかかる送信装置300を示す図である。
【図8】図8は、実施例4にかかる受信装置400を示す図である。
【発明を実施するための形態】
【0015】
以下においては、まず本発明が適用される理論を説明した上で、実施例を用いて説明していくものとする。つまり説明は、以下の順序で行われる。
1.理論
1.1.緒言
1.2.有限タイプのシフト
1.3.超離散力学系に基づく最大周期列
1.4.β変換に基づく指定された相関特性を有するマルコフ連鎖の実現
1.5.離散化β変換に基づく所望の相関特性と均等分布を有するマルコフ連鎖の実現
1.6.実験結果
1.7.一般の場合について
2.実施例
2.1.実施例1
2.2.実施例2
2.3.実施例3
2.4.実施例4
3.その他

【0016】
<1.理論>
<1.1.緒言>
擬似乱数が使用される分野は、情報通信系、暗号系、計算機科学、経済学(数理ファイナンス)、地球科学(地球シミュレーション)、気象学、ゲノム・サイエンスと枚挙に暇がない。また、学術分野のみならず、高機能携帯端末(スマートフォン)、通信、金融と情報技術(IT)を融合させたフィンテック(電子決済、クラウド会計)、多元センサーのランダム制御(自動給水装置及び自動給水システム)を証左として、「擬似乱数は我々の社会生活に必要不可欠なインフラ技術の一つである」と言っても過言ではない。

【0017】
要求される性能は、次ビット予測可能性、高次均等分布性、相関特性と、使用する目的に応じて種々挙げられる。本理論では、広い分野に要求される相関特性および均等分布性に注目する。暗号、計算機科学などでは時間tに関してt=0で1、それ以外で0を取るようなデルタ関数的な規格化自己相関関数が要求される。一方、情報通信、数理ファイナンスなどでは、短期に指数関数的に減少する自己相関特性や長周期に振動する自己相関特性が必要とされる。さらに、暗号だけでなく通信システムにおいても均等分布を有するビット列が用いられる。その様な自己相関特性と均等分布を有し、しかも互いに無相関な擬似乱数が大量に必要である。斯様な要求に答えること、すなわち、任意に指定された自己相関特性と均等分布を有する互いに無相関な擬似乱数を大量に実現することが本理論の目的である。実用の一例として、スペクトル拡散多元接続(SSMA)通信システムを考え、実際の携帯通信システムに使用可能な最適スペクトル拡散符号を取り上げる。

【0018】
<1.2.有限タイプのシフト>
集合Σは有限アルファベットであるとする。全Σシフトは、
【数1】
JP2018072867A_000003t.gif
で表される。これには、Σ上の離散位相から生ずる直積位相が付与される。

【0019】
シフト変換σ:
【数2】
JP2018072867A_000004t.gif

は、
【数3】
JP2018072867A_000005t.gif
で定義される。全
【数4】
JP2018072867A_000006t.gif
シフトの閉シフト不変部分集合はサブシフトと呼ばれる。サブシフトXに対して、X上のシフト変換をσXで表す。これは、Σ上のσの、Xへの制限である。簡単のため、σXよりむしろσ:X→Xと書くことにする。

【0020】
元u=u…u∈Σを長さn(n≧1)のΣ上のブロックと呼ぶ、これを単にnブロックとも言う。空ブロックを表すのにεを用いる。サブシフトXに対して、L(X)はXに属する点に現れるnブロック全体の集合を表す。このとき、Xの言語は集合
【数5】
JP2018072867A_000007t.gif
である。
ここで、L(X)={ε}である。

【0021】
(有向)グラフG=(V,A)は頂点の有限集合Vと辺の有限集合Aから成る。各辺e∈Aは、初期状態と呼ばれ、i(e)∈Vで表される頂点を出発し、終状態と呼ばれ、t(e)∈Vで表される頂点に到達する。

【0022】
(定義1)
G=(V,A)はグラフであるとする。頂点u,v∈Vに対して、au,vは、初期状態uと終状態vを有するGの辺の数を表すとする。このとき、Gの隣接行列はA=(au,v)u,v∈Vで定義される。隣接行列AがGから構成されるのをA=A(G)またはA=Aで表す。逆に、k×k非負整数行列
【数6】
JP2018072867A_000008t.gif
は,頂点集合{0,1,…,k-1}と、初期状態iから終状態jへのbi,j個の相異なる辺を有するグラフHを決定する。グラフHがBから構成されるのをH=G(B)またはH=Gで表す。A=A(G)となること、およびGとH=G(A)がグラフ同型であることは注目に値する。

【0023】
与えられた非負整数行列Aに対して、G=(V,A)と置く。
【数7】
JP2018072867A_000009t.gif
とする。このとき、σ:X→Xは、行列Aによって決定される両側位相的マルコフ連鎖と呼ばれる。位相的マルコフ連鎖はまた有限タイプのシフト(SFT)とも呼ばれる。SFTとは禁止語の有限集合によって表現することができるようなサブシフトである。与えられた禁止語の有限集合Fに対して、SFTを表すのにXを用いる。

【0024】
<1.3.超離散力学系に基づく最大周期列>
集合Eの濃度(有限の場合には要素数)を表すのに|E|を用いる。

【0025】
(定義2)
T:[0,1)→[0,1)とする。Pは点0=a<a<…<a|P|=1で与えられる区間[0,1)の分割であるとする。i=1,…,|P|に対して、I=(a-1,a)とし、TのIへの制限をT|Iで表す。T|Iが、Iから、Pの区間の閉包のある連結和集合の内部の上への同相写像であるとき、Tはマルコフであると言われる。このとき、分割
【数8】
JP2018072867A_000010t.gif
は、Tに関するマルコフ分割と呼ばれる。

【0026】
既約かつ非周期的マルコフ変換Tに対して、Tに関するマルコフ分割Pが定まる。このとき、各部分区間I∈Pを一つの辺e(I)に対応させると、辺集合Aを得る。Aに同伴して、頂点集合Vが
【数9】
JP2018072867A_000011t.gif
で与えられる。Pの元の各順序対(I,J)に対して、t(e(I))=i(e(J))が成り立つのは、丁度J⊂T|(I)のときである。斯くして、マルコフ変換を表現するグラフG=(V,A)を得る。一般に、得られたグラフはオイラーグラフではない。

【0027】
H=(V,B)は、最大辺数を有するGの全域オイラー部分グラフであるとする。既約かつ非周期的マルコフ変換を考えているので、頂点集合VはGからHへの変形に対して不変である。上で述べた、PとAの間の一対一対応の下で、Bに対応する部分分割Qを得る。このとき、離散化マルコフ変換
【数10】
JP2018072867A_000012t.gif
は、全てのI∈Qに対して、
【数11】
JP2018072867A_000013t.gif
を満たす置換
【数12】
JP2018072867A_000014t.gif
によって定義される。

【0028】
離散化マルコフ変換に基づく最大周期列は、丁度H上のオイラー回路であり、その長さは|B|で与えられる。Tに関するマルコフ分割Pが与えられるとき、|Q|!個の離散化マルコフ変換を得る。任意の置換は互いに素な巡回置換の積で(順序を除いて)一意に表されることは良く知られている。この事実に鑑み、離散化マルコフ変換
【数13】
JP2018072867A_000015t.gif
が基本変換T:[0,1)→[0,1)を近似すると見做さられるのは、丁度一つの巡回置換として表現されるときに限る。
この場合、離散化マルコフ変換
【数14】
JP2018072867A_000016t.gif
それ自身は最大周期列wとして見ることができる。さらに、最大周期列wに対して、両側無限列w=…www…を考えれば、巡回置換
【数15】
JP2018072867A_000017t.gif

【数16】
JP2018072867A_000018t.gif
上のシフトと見做すことができる。

【0029】
離散化マルコフ変換に基づく最大周期列は
【数17】
JP2018072867A_000019t.gif
に属するブロックに他ならないことが観察される。これは離散化マルコフ変換
【数18】
JP2018072867A_000020t.gif
が単に基本変換T:[0,1)→[0,1)の近似の一段階に過ぎないことを示唆する。より精密な近似を定義するために、記号力学系から高次辺グラフという概念を導入する[参考文献1]。

【0030】
(定義3)
Gはグラフであるとする。n≧2に対して、Gのn次高次辺グラフG[n]は頂点集合
【数19】
JP2018072867A_000021t.gif
を持ち、また、e…en-1=f…fn-2のとき(但しn=2の場合はt(e)=i(f)のとき)には常にe…en-1からf…fn-1へ丁度一つの辺を含むが、それ以外のときには何も無いような、辺集合を持つと定義される。辺はe…en-1n-1=e…fn-1と名付けられる。n=1に対して、G[1]=Gと置く。

【0031】
グラフGはマルコフ変換を表すとする。このとき、Gの高次辺グラフの列
【数20】
JP2018072867A_000022t.gif
を得る。各n≧1に対して、
【数21】
JP2018072867A_000023t.gif
は最大辺数を有するG[n]の全域オイラー部分グラフを表すとする。各々は、離散化マルコフ変換
【数22】
JP2018072867A_000024t.gif
を導く。最大周期列の長さは|B|で与えられることに注意しておく。

【0032】
ここまで,離散化される変換として、一般の既約かつ非周期的マルコフ変換Tを考えてきた。以下、離散化される変換Tに対して、次の単調性を要求する。[0,1]のある分割0=x<x<…<x=1が存在して、各整数i=1,…,kに対して、Tの区間[xi-1,xi)への制限は単調増加関数である。

【0033】
既約かつ非周期的マルコフ変換Tがこの条件を満たすとき、Tを区分的単調増加(PMI)マルコフ変換と呼ぶ。以下、離散化される変換は、その様な単調性を有するとしよう。ここで、区分的単調増加マルコフ変換は実用的に十分広いクラスのマルコフ変換を含むことを強調しておく。実際、PMIマルコフ変換は、本理論で考える黄金平均変換やβ変換だけでなく、Bernoulli変換、Kalmanのマルコフ変換[参考文献2]、および[参考文献3]で定義されたk(≧2)方有尾シフト変換を含む。

【0034】
PMIマルコフ変換に対しては、離散化された変換に基づく最大周期列を全て生成するような、有界単調真理値表アルゴリズムを与えた[参考文献4]。

【0035】
<1.4.β変換に基づく指定された相関特性を有するマルコフ連鎖の実現>
非同期スペクトル拡散多元接続(SSMA)通信システムのおけるビット誤り生起確率に関して、最適M(≧2)相マルコフ連鎖拡散符号が設計された[参考文献5]。最適拡散符号を生成するマルコフ連鎖は、その確率行列の第二固有値が-2+√3を有することでMに無関係に特徴付けられる。簡単のため、以下M=2の場合に制限するが、[参考文献5]の結果を用いることにより、M≧3の場合も同様に得られる。

【0036】
M=2の場合、最適二値マルコフ連鎖拡散符号系列は
【数23】
JP2018072867A_000025t.gif
を有する{1,-1}に値を取る定常マルコフ連鎖系列
【数24】
JP2018072867A_000026t.gif
として特徴付けられる。ここで、確率変数Zに対して、
【数25】
JP2018072867A_000027t.gif
はZの期待値を表す。

【0037】
系列に対する相関関数は、二つの系列の間の類似性または関係性の測度であり、数学的に次の様に定義される。
(定義4)
{-1,1}上の系列
【数26】
JP2018072867A_000028t.gif

【数27】
JP2018072867A_000029t.gif
に対する、遅れ時間
【数28】
JP2018072867A_000030t.gif
の正規化相互相関関数は
【数29】
JP2018072867A_000031t.gif
で定義される。ここで、
【数30】
JP2018072867A_000032t.gif
である。整数aとb(≧1)に対して、a(mod b)は法bに関するaの最小剰余を表す。X=Yのとき
【数31】
JP2018072867A_000033t.gif
を正規化自己相関関数と呼び、単に
【数32】
JP2018072867A_000034t.gif
で表す。
所望の
【数33】
JP2018072867A_000035t.gif
を有する系列Xを構成するために[参考文献6]で定義されたPerron数を導入する。

【0038】
(定義5)
数λがPerron数であるのは、次を満たすときである。i)λは正の代数的整数である。およびii)λ以外の全ての代数的共役μに対して、λ>|μ|が成り立つ。Perron数全体の集合を
【数34】
JP2018072867A_000036t.gif
で表す。

【0039】
行列Aは非負整数行列であるとする。ある整数nに対して、A>0ならば、Aは原始的であると言われる。ここで、行列Bに対して、B>0はBが正行列であることを表す。Aが原始的であるのは、Aが既約かつ非周期的であることと同等である。原始的行列Aに対して、AのPerron-Frobenius固有値をλで表す。斯くして、Perron数は次の定理により特徴付けられる。

【0040】
定理1(Lind [参考文献6])
【数35】
JP2018072867A_000037t.gif
はある原始的Aに対してλ=λのときまたそのときに限る。
所望の相関関数はパラメータを一個(すなわち-2+√3)しか持たないので、次数2を有する
【数36】
JP2018072867A_000038t.gif
を考えれば十分である。一般に、パラメータ数mに対して、次数m+1を考えればよい。次数2を有するλの、Q上最小多項式は
【数37】
JP2018072867A_000039t.gif
で定義される。ここで、
【数38】
JP2018072867A_000040t.gif
である。多項式f(t)のコンパニオン行列は、
【数39】
JP2018072867A_000041t.gif
で与えられる。コンパニオン行列Bの特性多項式と最小多項式はf(t)に等しいことに注意する。

【0041】
β変換は、次のように定義される。すなわち、β>1に対して、β変換T:[0,1]→[0,1]はT(x)=βx(mod 1),x∈[0,1]で定義される。ここでx=y(mod 1)は1を法とする実数上の合同、すなわち、x-yが整数であることを表す。さらに、β変換が(定義2)を満たすとき、マルコフβ変換と呼ばれる。

【0042】
マルコフβ変換に行列Bを同伴するために、0<c≦cとする。このとき、コンパニオン行列Bに同伴するマルコフβ変換の(c+1)×(c+1)隣接行列Aは
【数40】
JP2018072867A_000042t.gif
で与えられる。

【0043】
実数値を二値に符号化する写像Ψ:[0,1)→{1,-1}を
【数41】
JP2018072867A_000043t.gif
で定義する。n=0,1,2,…に対して、変換Tのn回反復T(x)は、T(x)=x及びT(x)=Tn-1(T(x))により帰納的に定義される。このとき、Z=Ψ(T(x))と置くことにより、区間[0,1)に属するほとんど全てのxに対して、{1,-1}に値を取るマルコフ連鎖系列
【数42】
JP2018072867A_000044t.gif
が生成される。斯くして、
【数43】
JP2018072867A_000045t.gif
を得る。ここで、
【数44】
JP2018072867A_000046t.gif
はλの代数的共役である。

【0044】
条件0<c≦cの下、方程式
【数45】
JP2018072867A_000047t.gif
の整数解(c,c)はc=c=2として一意に与えられる。

【0045】
結局、傾きβ=1+√3を有するマルコフβ変換Tを得る。β=1+√3=λはt-2t-2=0の正の解である。図1にTのグラフを示す。

【0046】
相関特性
【数46】
JP2018072867A_000048t.gif
を有するような、{1,-1}に値を取るマルコフ連鎖系列
【数47】
JP2018072867A_000049t.gif
をうまく得た。しかしながら、連鎖の定常分布は
【数48】
JP2018072867A_000050t.gif
で与えられ、一様分布でないため、
【数49】
JP2018072867A_000051t.gif
となり、所望の零でない。

【0047】
次に、得られた最適二値マルコフ連鎖拡散符号の相関特性を変更すること無く、スライディング・ブロック符号を用いて、系列の分布(p,p)を一様分布に変換する。

【0048】
<1.5.離散化β変換に基づく所望の相関特性と均等分布を有するマルコフ連鎖の実現>
基数β=1+√3を用いるとき、区間[0,1)に属する実数xのβ進展開はSFT
【数50】
JP2018072867A_000052t.gif
の右側無限列として与えられる。ここでΣ={0,1,2}及びF={22}である。実数x∈[0,1)のβ進展開から得られる右側無限列は、図1に示したβ変換Tの、初期値をxとする。実数値解軌道の記号力学的表現である。SFT X のグラフ表現Gは、図2に示すように与えられる。同時に、GはTの表現でもある。

【0049】
初期グラフをG=G[2]として、Gの高次辺グラフの列
【数51】
JP2018072867A_000053t.gif
を得る。各n≧2に対して、Hは最大辺数を有するG[n]の全域オイラー部分グラフを表すとする。各オイラー部分グラフHのオイラー回路が、傾きβ=1+√3を有するβ変換Tの超離散化に基づく最大周期列である。図2において、Gはオイラーグラフであることがわかる。この場合、G=G[2]=Hを得る。しかしながら、n(≧3)に対して、G[n]はオイラーグラフであるとは限らない。実際、HはG[3]の真部分グラフである。
これを
【数52】
JP2018072867A_000054t.gif
で表す。任意のn(≧3)に対して、
【数53】
JP2018072867A_000055t.gif
となるのが確認される。

【0050】
図2のオイラー部分グラフHにおいて、例えば、最大周期列001021120を得る。
最大周期列の長さ|B|は
【数54】
JP2018072867A_000056t.gif
で与えられる[参考文献7]。ここで、
【数55】
JP2018072867A_000057t.gif
はβの代数的共役である。

【0051】
以下、傾きβ=1+√3を有するβ変換の超離散化に基づき、最適二値マルコフ連鎖拡散符号を構成する。集合L(X)\{ε}上の全順序関係≦を次で定義する。すなわち、L(X)に属する任意のu=u…u(m≧1)とv=v…v(n≧1)に対して、u≦vは
【数56】
JP2018072867A_000058t.gif
のときまたそのときに限る。
簡単のため、最大周期列の長さ|B|を表すのにLを用いる。Lブロックv=v…v∈{0,1,2}に対して、ブロック符号Φ:{0,1,2}→{1,-1}を
【数57】
JP2018072867A_000059t.gif
で定義する。

【0052】
Lブロック全体の集合{0,1,2}上のシフト変換をSで表す。すなわち、v=v…v∈{0,1,2}に対して、
【数58】
JP2018072867A_000060t.gif
と表す。斯くして、周期Lの周期列に対して、
【数59】
JP2018072867A_000061t.gif
で定義されるスライディング・ブロック符号φを得る。ここで、ブロックuに対して、u=…uuu…である。

【0053】
系列Xは、β=1+√3を有する離散化マルコフβ変換に基づく、長さL=|B|の、Σ={0,1,2}上の最大周期列であるとする。スライディング・ブロック符号φを用いて、最適二値マルコフ連鎖拡散符号系列Yが
【数60】
JP2018072867A_000062t.gif
により実現される。

【0054】
長さ|B|の最適二値マルコフ連鎖拡散符号の例を示す。
(例1) n=3のとき、L=20であり、
【数61】
JP2018072867A_000063t.gif
を得る。ここで、表記を簡単にするため、右辺の0は-1を表す。

【0055】
[参考文献8]の結果を最適二値マルコフ連鎖拡散符号に適用して、次の評価を得る。
(定理2)
【数62】
JP2018072867A_000064t.gif
を得る。
これは
【数63】
JP2018072867A_000065t.gif
を示唆する。ここで、
【数64】
JP2018072867A_000066t.gif
はランダウの記号である。

【0056】
<1.6.実験結果>
最大周期列の長さ|B|、Hにおける{0,1,2}上の最大周期列の総数ν、及び実現された最適二値マルコフ連鎖拡散符号の総数
【数65】
JP2018072867A_000067t.gif
をそれぞれ表1に示す。
【表1】
JP2018072867A_000068t.gif

【0057】
n=4のとき、最大周期列の長さは|B|=56となる。この場合に、離散化β変換に基づいて実現された最適二値マルコフ連鎖拡散符号を用いた非同期SSMA通信システムのおけるビット誤り生起確率の、ユーザ数依存性を図3に示す。現在、実用化されているGold符号の系列長は32である。n=4のとき、長さ|B|=56の最適二値マルコフ連鎖拡散符号に対して、開始点をランダムに選び、そこから長さ32で系列を打ち切ることにより、長さ32の系列が得られる。このようにして、長さ56の最適二値マルコフ連鎖拡散符号から長さ32の系列を抽出した場合の結果を図4に示す。

【0058】
図3及び図4の各々において、曲線は[参考文献9]で与えられる中心極限定理(CLT)に基づく理論評価式を表し、点×は数値実験結果を表す。いずれにおいても両者は良く一致していることが確認される。同様にして、任意の長さの擬似乱数を得ることができる。

【0059】
<1.7.一般の場合について>
これまで、最適二値マルコフ連鎖拡散符号を実現するため、
【数66】
JP2018072867A_000069t.gif
において、ρ=-2+√3の場合を考えた。ρが一般の場合には上記(1)式と同様に、
【数67】
JP2018072867A_000070t.gif
の整数解(c,c)を求めることにより、傾きβが得られる。

【0060】
簡単のためc+1=kとおく。離散化β変換により、{0,1,…,k-1}上の最大周期列を得る。残るはブロック符号Φの定義だけである。

【0061】
貪欲算法による実数x∈[0,1]のβ進展開をdβ(x)で表す。|B|=Lとおく。Lブロックv=v2…∈{0,1,2}に対して、ブロック符号Φ:{0,1,…,k-1}→{1,-1}を次のように定義すればよい。
【数68】
JP2018072867A_000071t.gif
【数69】
JP2018072867A_000072t.gif

【0062】
以下に、参考文献を列挙する。
[参考文献1] D. Lind and B. Marcus, Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995.
[参考文献2] R. E. Kalman, “Nonlinear aspects of sampled-data control systems”, Proc. Symp. Nonlinear Circuit Analysis VI, pp. 273-313, 1956.
[参考文献3] 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.
[参考文献4] 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.
[参考文献5] 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.
[参考文献6] 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.
[参考文献7] H. Fujisaki, “On the topological entropy of the discretized Markov β-transformations,” to appear in IEICE Trans. Fundamentals, vol. E99-A, total 10 pages, 2016.
[参考文献8] 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.
[参考文献9] 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】
<2.実施例>
<2.1.実施例1>
次に、実施例1を用いて、本発明の実施の形態について説明する。図5は、実施例1にかかる系列生成装置100を示す図である。系列生成装置100は、記憶部110、生成部130、及び変換部150を含む。系列生成装置100は、所定の自己相関特性と均等分布を有する互いに無相関な系列を生成する。

【0064】
(記憶部110)
記憶部110は、生成部130と変換部150とそれぞれ接続され、生成部130により生成された系列(第1の系列)を記憶し、記憶している情報を変換部150に出力する。

【0065】
(生成部130)
生成部130は、上述した<理論>に従い、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第1系列を生成する。まず、所定の相関特性は、下記式のρにより与えられる。
【数70】
JP2018072867A_000073t.gif
ここで、Zは第1系列の確率変数である。具体的なρの値は、ユーザが例えば記憶部110に予め記憶しておき、記憶した情報(ρの値)を生成部130に出力することができる。

【0066】
このようにしてρが与えられることで、生成部130は、下記式において整数解(c,c)を求めることにより、区分単調増加マルコフ変換の傾きβを得ことができる。
【数71】
JP2018072867A_000074t.gif
具体例として、ρ=-2+√3の場合には、区分単調増加マルコフ変換の傾きβは、1+√3となる。

【0067】
生成部130は、Z=Ψ(T(x))のTを、区分単調増加マルコフ変換の傾きβとすることで、下記式により表される第1系列を生成する。生成した第1系列は、記憶部110に記憶される。
【数72】
JP2018072867A_000075t.gif

【0068】
具体例で挙げたようにTを傾き1+√3のβ変換とした場合、区間[0,1)に属するほとんど全てのxに対して、所定ρ=-2+√3の相関特性を有し、{1,-1}に値を取る第1系列を生成することができる。

【0069】
(変換部150)
変換部150は、上述した<理論>に従い、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、第1系列を第2系列に変換する。

【0070】
所定の分布は、均等分布、言い換えれば一様分布である。一様分布を満たす限り、
【数73】
JP2018072867A_000076t.gif
となる。

【0071】
一様分布と、区分単調増加マルコフ変換の傾きとに基づいて得られる変換条件は、下記式のブロック符号Φにより表される。
【数74】
JP2018072867A_000077t.gif
【数75】
JP2018072867A_000078t.gif

【0072】
具体例として、区分単調増加マルコフ変換の傾きβが1+√3の場合には、ブロック符号Φは下記式により表される。
【数76】
JP2018072867A_000079t.gif

【0073】
変換部150は、変換条件を表すブロック符号Φに基づいて、下記式により第1系列Xを第2系列Yに変換する。
【数77】
JP2018072867A_000080t.gif

【0074】
ここで、Sは、Lブロック全体の集合{0,1,2}上のシフト変換であって、v=v・・・v∈{0,1,2}に対して下記式で表される。
【数78】
JP2018072867A_000081t.gif

【0075】
以上のような構成からなる系列生成部100は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された第1系列を、所定の分布と区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて変換することにより、任意に指定された自己相関特性と均等分布を有する互いに無相関な第2系列を大量に生成することができる。

【0076】
第2系列は、拡散符号として用いることができる。つまり、CDMA方式などの無線通信の拡散符号として用いることができる。また、第2系列は、暗号化又は復号(decryption)のための系列として用いることができる。

【0077】
<2.2.実施例2>
次に、実施例2を用いて、本発明の実施の形態について説明する。図6は、実施例2にかかる符号化処理装置200を示す図である。符号化処理装置200は、記憶部210、及び符号化部230を含む。符号化処理装置200は、上述した系列生成部100により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第2系列を利用して、任意の信号列の符号化を行う。

【0078】
(記憶部210)
記憶部210は、上述した系列生成装置100により第1系列から変換された第2系列を記憶し、記憶している情報を符号化部230に出力する。ここで、上述したように、第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第2系列は、第1系列を、所定の分布(均等分布)と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。

【0079】
(符号化部230)
符号化部230は、記憶部210から第2系列を読み出し、読み出した第2系列に基づいて信号列の符号化を行って出力する。

【0080】
具体的に、符号化処理装置200が、CDMA方式で通信を行う用途で用いられる場合には、第2の系列は、第1系列から変換された拡散符号であり、符号化部230は、信号列を拡散する。

【0081】
また、符号化処理装置200が、暗号化を行う用途で用いられる場合には、符号化部230は、信号列を暗号化する。

【0082】
以上のような構成からなる符号化処理装置200は、記憶部210が、自己相関特性と均等分布を有する互いに無相関な第2系列を大量に記憶することができる。このため、例えば、CDMA方式の無線通信において同一の周波数帯域内で2つ以上の複数の通信を行う際に、第2系列を用いた拡散を行った信号列を用いて通信することで、ビット誤りを少なくして信頼性を高めることができる。また、符号化処理装置200は、第2系列を用いて信号列を暗号化することで、暗号の信頼性を高めることができる。

【0083】
<2.3.実施例3>
次に、実施例3を用いて、本発明の実施の形態について説明する。図7は、実施例3にかかる送信装置300を示す図である。

【0084】
送信装置300は、記憶部310、符号化部330、及び送信部350を含む。送信装置300は、上述した系列生成部100により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第2系列を利用して、任意の信号列を符号化して、他の装置へ送信する。

【0085】
(記憶部310)
記憶部310は、上述した系列生成装置100により第1系列から変換された第2系列を記憶し、記憶している情報を符号化部330に出力する。ここで、上述したように、第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第2系列は、第1系列を、所定の分布(均等分布)と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。

【0086】
(符号化部330)
符号化部330は、記憶部310から第2系列を読み出し、読み出した第2系列に基づいて信号列の符号化を行って送信部350に出力する。具体的に、第2の系列は第1系列から変換された拡散符号であり、符号化部330は、第2系列を用いて信号列の拡散を行う。なお、拡散に代えて暗号化を行ってもよい。すなわち、符号化部330は、第2系列を用いて信号列の暗号化を行ってもよい。

【0087】
(送信部350)
送信部350は、符号化部330により符号化(拡散)された信号列を無線信号に変換して、他の装置に送信する。

【0088】
以上のような構成からなる送信装置300は、記憶部310が、自己相関特性と均等分布を有する互いに無相関な第2系列を大量に記憶することができ、このような第2系列を用いて信号列を拡散して他の装置に送信することができる。

【0089】
例えばCDMA方式の無線通信では、同一の周波数帯域内で2つ以上の複数の通信を行う際にビット誤りを軽減する観点から、長周期の系列を大量に用いることが必要となる。このため、送信装置300では、上述したように、第2系列を用いて信号列を拡散して他の装置に送信することで、同一の周波数帯域内で2つ以上の複数の通信を行う際に、ビット誤りを少なくして信頼性を高めることができる。

【0090】
<2.4.実施例4>
次に、実施例4を用いて、本発明の実施の形態について説明する。図8は、実施例4にかかる受信装置400を示す図である。

【0091】
受信装置400は、記憶部410、受信部430、及び復号部450を含む。受信装置400は、上述した系列生成部100により生成された系列、すなわち、任意に指定された自己相関特性と均等分布を有する第2系列を利用して、符号化された信号列を復号する。

【0092】
(記憶部410)
記憶部410は、上述した系列生成装置100により第1系列から変換された第2系列を記憶し、記憶している情報を復号部450に出力する。ここで、上述したように、第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成されたものである。また、第2系列は、第1系列を、所定の分布(均等分布)と区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換したものである。

【0093】
(受信部430)
受信部430は、他の装置から、第2系列に基づいて符号化された信号列の無線信号を受信して復号部450に出力する。

【0094】
(復号部450)
復号部450は、記憶部310から第2系列を読み出し、読み出した第2系列に基づいて、受信部430が受信した信号列を復号(decoding)する。具体的に、第2の系列は第1系列から変換された拡散符号であり、復号部450は、第2系列を用いて信号列の逆拡散を行う。なお、逆拡散に限らず、信号列が暗号化されている場合には、復号部450は、第2系列を用いて信号列の復号(decryption)を行ってもよい。

【0095】
以上のような構成からなる受信装置400は、記憶部410が、自己相関特性と均等分布を有する互いに無相関な第2系列を大量に記憶することができ、このような第2系列を利用して信号列を逆拡散することができる。

【0096】
例えばCDMA方式の無線通信では、同一の周波数帯域内で2つ以上の複数の通信を行う際にビット誤りを軽減する観点から、長周期の系列を大量に用いることが必要となる。このため、受信装置400では、上述したように、第2系列を用いて信号列を逆拡散することで、同一の周波数帯域内で2つ以上の複数の通信を行う際に、ビット誤りを少なくして信頼性を高めることができる。

【0097】
<3.その他>
以上、本発明を実施の形態をもとに説明した。本発明は上述した実施例並びに各実施例の内容に限定されるものではなく、本発明の要旨の範囲内において種々に変形して実施をすることが可能である。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。

【0098】
例えば、以下の発明も、本発明の態様として捉えることができる。

【0099】
(発明1)
第1系列から変換された第2系列に基づいて符号化が行われた信号列を、他の装置から受信する受信部と、
前記第2系列に基づいて、前記受信した信号列の復号を行う復号部と、
を備え、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
受信装置。
(発明2)
前記第2系列は、前記第1系列から変換された拡散符号であり、
前記符号化は、拡散であり、
前記復号は、前記受信した信号列の逆拡散である、
(発明1)の受信装置。
(発明3)
前記符号化は、暗号化であり、
前記復号(decoding)は、前記信号列の復号(decryption)である、(発明1)記載の受信装置。
(発明4)
所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて、第1系列を生成することと、
所定の分布と前記区分単調増加マルコフ変換の傾きとに基づいて設定された変換条件に基づいて、前記第1系列を第2系列に変換することと、
を含む系列生成方法。
(発明5)
第1系列から変換された第2系列を取得することと、
前記第2系列に基づいて、信号列の符号化を行うことと、
を含み、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
符号化処理方法。
(発明6)
第1系列から変換された第2系列に基づいて、信号列の符号化を行うことと、
前記符号化後の前記信号列を、他の装置に送信することと、
を含み、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
送信方法。
(発明7)
第1系列から変換された第2系列に基づいて符号化が行われた信号列を、他の装置から受信することと、
前記第2系列に基づいて、前記受信した信号列の復号を行うことと、
を含み、
前記第1系列は、所定の相関特性に基づいて設定された区分単調増加マルコフ変換の傾きに応じて生成された系列であり、
前記第2系列は、前記第1系列を、所定の分布と前記区分単調増加マルコフ変換の傾きとに基づく変換条件に基づいて変換した系列である、
受信方法。
【産業上の利用可能性】
【0100】
任意に指定された自己相関特性と均等分布を有する互いに無相関な系列を大量に生成することが可能である。
【符号の説明】
【0101】
100 系列生成装置
110、210、310、410 記憶部
130 生成部
150 変換部
200 符号化装置
230、330 符号化部
350 送信部
430 受信部
450 復号部

図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7