kトニックな0/1列に対する線形サイズ対数深さの否定数限定インバータ

概要

論文の詳細を見る
0/1列x_1,・・・,x_nは,1≦i≦n-1に対してx_i≠x_i+1であるiの数がたかだかkであるときkトニックであるという.本研究では,サイズO((log k)・n),深さO((log k)・log log n+log n),含まれるNOT素子の数log_2 n+O(log log n)であるkトニック列の0/1を反転する回路の構成法を与える.我々の構成法はすべての点において佐藤らによる構成法(サイズO(kn),深さO(k log^2 n),NOT素子の数O(k log n))を改善している.k=O(1)であるとき,佐藤らによる構成法はO(log^2 n)の深さを必要としたが,我々の構成法はNOT素子の数O(log n)で線形サイズ,対数深さを実現している.BelasらはNOT素子を[log_2(n+1)]使用したサイズO(n log n),深さO(log n)のすべての列に対するインバータの構成法を与えた.k=n^<o(1)>であるとき,我々の構成法は同等の深さとO(log log n)のNOT素子の増加のみでそのサイズをo(n log n)に減少させる.kトニック列に対するインバータの構成における我々の考察はkトニック列をソートする回路に関しても佐藤らによるものを改善する.
社団法人電子情報通信学会の論文
2006-11-27