セレクタ論理に帰着させたバタフライ演算器のFPGA実装評価

摘要

高速フーリエ変換（FFT）は信号処理など様々なアプリケーションで利用されるが，特に，秘匿計算で利用される準同型暗号を用いた演算ではFFTが多用され，高速なFFT処理が求められる．高速フーリエ変換の基本演算はバタフライ演算であるが，これはビットレベルで式変形を行いセレクタ論理に帰着させることで，桁上げ伝搬遅延を削減できることが知られている．本稿では，FPGAを対象にバタフライ演算器を実装し，遅延とスライス数の評価を行う．ビットレベル式変形によりセレクタ論理に帰着して積項を生成したバタフライ演算回路を論理合成したところ，セレクタ論理を用いずに積項を生成した回路と比べて，クリティカルパス遅延を最大9.4，スライス数を最大22.3削減できることを確認した．