ブール関数に対するフィルタのノイズ除去効果について

摘要

理論計算機科学の分野における様々な問題が，ブールドメイン{0,1}{sup}n上の関数のフーリエ変換を通して解析されているが，その手法は，基底関数の正規直交性やフーリエ係数の組み合わせ論的な性質を調べることを主としており，信号処理の分野における従来のフーリエ解析とは，ほぼ独立に発展している．一方，信号処理分野では，フーリエ解析について長い歴史があり，すでに膨大な知識が蓄えられている．我々は，計算機科学の立場からこれらの結果を見直し，類推することによって，計算機科学においても有用な新たな知見が得られる可能性があると考える．そこで，本論文では，信号処理分野で基本的かつ重要な役割を果たしているフィルタを取り上げ，ブール関数に対するフィルタの概念を定式化し，その性質を調べる．特に，ブール関数に対するフィルタのノイズ除去効果の度合を表わす公式を2つ与える．