わずかにランダム性をもつソースからのランダム性の抽出

山本 博章  丹野 州宣  野口 正一  

誌名
電子情報通信学会論文誌 D   Vol.J71-D   No.11   pp.2242-2249
発行日: 1988/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(669.8KB)
>>論文を購入


あらまし: 
本論文では次のような問題を考える.「A={1,…,k},k≧2とする.いま,Aの各要素を0またはδ(>0なる定数)以上の確率で出力する互いに独立な物理源が複数個存在するとする.そのとき,これらの物理源からの情報をもとにして,A上の各要素を等確率で得る方法が存在するか」.従来,k=2に対し,バリティ関数を用いた方法が得られている.しかし,k≧2を任意にしたとき,バリティ関数の単なる一般化,すなわち,kを法とする加法では物理源の出力に関する確率分布によってはA上の各要素を等確率で得られない場合がある.我々は,これらの物理源にわずかの条件を課し,そのもとで,任意のk≧2に対し,A上の各要素を等確率で得る方法を与える.