| 引用本文: | 田泽荣,李晓梅.二维 DFT 和 DCT 的 Systolic 阵列.[J].国防科技大学学报,1993,15(1):82-89.[点击复制] |
| Tian Zerong,Li Xiaomei.Systolic Arrays for Two Dimensional DFT and DCT[J].Journal of National University of Defense Technology,1993,15(1):82-89[点击复制] |
|
| |
|
|
| 本文已被：浏览 6853次 下载 5698次 |
| 二维 DFT 和 DCT 的 Systolic 阵列 |
| 田泽荣, 李晓梅 |
|
(电子计算机系)
|
| 摘要: |
| 超级计算中一个活跃的研究领域是将某些有限和，如离散富里叶变换(DFT)、离散余弦变换（DCT)，映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图，给出了计算二维DFT的二种Systolic 阵列:一种是由N1个处理器组成的线性阵列，所花时间步为O(N1N2) (设二维DFT为N1×N2长的)，与行列分解算法在单处理机上顺序执行所花时间相比，加速比为O(N)(设N1=N2=N)，这一结果无论是在时间消耗，还是在PE数量上都是目前最优的。另一种是由N1×N2个处理器组成的矩形阵列，所需时间为O(N1十N2),与行列算法在单处理机上顺序运行所花时间相比，加速比为O(N2)(这里仍假定N1= N2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。 |
| 关键词: 信号处理，二维DFT，二维DCT，行列分解算法，Systolic 阵列 |
| DOI： |
| 投稿日期：1991-10-10 |
| 基金项目: |
|
| Systolic Arrays for Two Dimensional DFT and DCT |
| Tian Zerong, Li Xiaomei |
|
(Department of Computer Science)
|
| Abstract: |
| An active area of research in supercomputing is concerned with mapping certain sums, such as discrete Fourier transforms (DFT) and discrete cosine transforms (DCT) to multi-processor arrays. This paper presents two kinds of systolic arrays for 2D-DFT using the flow diagram of row-column de composition algorithm. One is a linear array of N1 processors (if the DFT is N1×N2), and it takes O(N1N2)time steps. The speed-up of this array over the sequential implementation of the row-column decomposition algorithm on a single processor is O(N)(IF N1=N2=N). This result is currently optimal not only in PE numbers, but a1so in time cost. The other is a rectagular array of N1×N2 processors and it takes O(N1+N2)steps. The specdup of it over the sequential implementation of the row-cotumn decomposition algorithm on a single processor is O(N2)(IF N= N1=N2). At last, the paper gives two systolic arrays of 2D-DCT,which are similar to that of 2D-DFT. Furthermore, these systolic arrays can be easily generalized to multi-dimensional cases. |
| Keywords: two-dimensional DFT,row-column decomposition algorithm,two-demensional DCT,systolic arrays |
|
|
|
|
|
