講演抄録/キーワード |
講演名 |
2013-05-24 14:45
畳語分解に基づく文字列の複雑度の提案とその乱数検定への応用 ○真矢 滋・山本博資(東大) IT2013-8 |
抄録 |
(和) |
乱数検定法としてNIST SP 800-22 がよく知られている.その中の検定方法の一つとしてLZ-複雑度(LZ-complexity) を用いた検定法が存在していたが,第一種誤り確率が大きいため排除された.LZ-複雑度の問題点を解消するために,T-複雑度(T-complexity) に基づく乱数検定法が提案されているが,真の乱数系列のT-複雑度がT-複雑度の最大値よりかなり小さいという欠点がある.本稿では,それら両方の欠点を改善できる「畳語分解に基づく複雑度(RP-複雑度, RP-complexity)」を新たに提案し,乱数検定に用いた場合の有用性を示す. |
(英) |
A randomness test based on LZ-compelxity was included in the NIST statistical test suite. However, it was removed because it has relatively large probability of type I error. In order to overcome this defect, a randomness test based on T-complexity was proposed. But, T-complexity has another defect such that the T-complexity of random sequences is considerably smaller than the maximum T-complexity. In order to overcome both defects of LZ-complexity and T-complexity, we propose a new complexity measure called RP-complexity, which is defined by reduplication parsing, and we show the validity of RP-complexity by a randomness test based on RP-complexity. |
キーワード |
(和) |
乱数検定 / LZ-複雑度 / T-複雑度 / / / / / |
(英) |
randomness test / LZ-complexity / T-complexity / / / / / |
文献情報 |
信学技報, vol. 113, no. 58, IT2013-8, pp. 35-40, 2013年5月. |
資料番号 |
IT2013-8 |
発行日 |
2013-05-17 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2013-8 |
研究会情報 |
研究会 |
IT |
開催期間 |
2013-05-24 - 2013-05-24 |
開催地(和) |
福井・あわら温泉 まつや千千 |
開催地(英) |
Hotel Matuya Sensen at Awara-onsen, Fukui Pref. |
テーマ(和) |
記録素子用符号化,一般(フラッシュメモリ符号化に関するワークショップ(5/23~5/24)と併催) |
テーマ(英) |
coding for recording systems, general (jointly held with Workshop on Coding for Flash Memory (5/23-5/24)) |
講演論文情報の詳細 |
申込み研究会 |
IT |
会議コード |
2013-05-IT |
本文の言語 |
日本語 |
タイトル(和) |
畳語分解に基づく文字列の複雑度の提案とその乱数検定への応用 |
サブタイトル(和) |
|
タイトル(英) |
String complexity based on reduplicative parsing and its application to randomness testing |
サブタイトル(英) |
|
キーワード(1)(和/英) |
乱数検定 / randomness test |
キーワード(2)(和/英) |
LZ-複雑度 / LZ-complexity |
キーワード(3)(和/英) |
T-複雑度 / T-complexity |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
真矢 滋 / Shigeru Maya / マヤ シゲル |
第1著者 所属(和/英) |
東京大学 (略称: 東大)
The University of Tokyo (略称: Univ. of Tokyo) |
第2著者 氏名(和/英/ヨミ) |
山本 博資 / Hirosuke Yamamoto / ヤマモト ヒロスケ |
第2著者 所属(和/英) |
東京大学 (略称: 東大)
The University of Tokyo (略称: Univ. of Tokyo) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2013-05-24 14:45:00 |
発表時間 |
25分 |
申込先研究会 |
IT |
資料番号 |
IT2013-8 |
巻番号(vol) |
vol.113 |
号番号(no) |
no.58 |
ページ範囲 |
pp.35-40 |
ページ数 |
6 |
発行日 |
2013-05-17 (IT) |