2019

多値論理回路・関数・多項式と離散フーリエ変換（On Multiple-Valued Logic Circuits, Functions, and Polynomials and Discrete Fourier Transforms）

多値論理関数とは，入出力が有限体である多変数関数であり，スイッチング回路の構成に応用がある．多値論理多項式とは，有限体係数の多変数多項式であり，多値論理関数は多値論理多項式と全体として等しいという事実がある．誤り訂正符号と多値論理多項式とは互いに双対の関係にあるため，誤り訂正符号の研究成果を多値論理多項式に応用できる．本研究では，「畳込み定理」と呼ばれる，多値論理関数と多値論理多項式の間の離散フーリエ変換を介して成り立つ関係を，有限体の半群と呼ばれる部分集合に対して一般化した．ここで扱う多値論理関数は，有限体内の半群の直積から有限体への関数であり，また多値論理多項式はこれらを多項式に変換したものである．次に，この定理を多値論理多項式どうしの積の高速化に応用し，概算として従来は変数の個数の2乗オーダーであったが，高速化により1乗掛ける対数オーダーにまで計算量を削減することができた．