Bit reversal on uniprocessors
Bit reversal on uniprocessors
复制标题
DOI：
10.1137/1038001
复制
发表时间：
1996-03-01
期刊：
影响因子：
10.2
通讯作者：
Karp, AH
中科院分区：
文献类型：
--
作者：
Karp, AH
许多版本的快速傅里叶变换都需要对输入或输出数据进行重新排序，这与数组索引中位的顺序颠倒相对应。在最近的文献中，关于这个主题的论文数量惊人地多。本文收集了30种阵列的位反转方法。每种方法在Fortran中被重新编码成统一的样式，并在几台不同的机器上测量其性能，每台机器都有不同的内存系统。这篇论文描述了机器的记忆是如何运作的，以激发两种比其他算法表现得更好的新算法。
Many versions of the fast Fourier transform require a reordering of either the input or the output data that corresponds to reversing the order of the bits in the array index. There has been a surprisingly large number of papers on this subject in the recent literature.This paper collects 30 methods for bit reversing an array. Each method was recoded into a uniform style in Fortran and its performance measured on several different machines, each with a different memory system. This paper includes a description of how the memories of the machines operate to motivate two new algorithms that perform substantially better than the others.