Area-time complexity for VLSI
Area-time complexity for VLSI
复制标题
VLSI 的面积时间复杂度
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
Clark D. Thomborson
中科院分区：
文献类型：
--
作者：
Clark D. Thomborson
研究了适合VLSI技术的新计算模型，研究了离散傅立叶变换（DFT）的复杂性。面积（a）和时间（t）的下限与DFT中的点（n）数量有关：AT2≥n2/16。当t =θ（n1/2）或t =θ（log n）时，紧密的下限也会得出：atx =ω（n1+x/2），以0≤x≤2。
The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT2≥ N2/16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T = θ(N1/2) or T = θ(log N). A more general lower bound is also derived: ATx = Ω(N1+x/2), for 0≤×≤2.