An improved digit-reversal permutation algorithm
This paper improves the speed of the digit-reversal permutation in the radix-\(B\) fast Fourier or Hartly transform on \(N\) data, where \(N = B^ P\). Its mathematical basis is as follows: Let \(i = (0 0 \dots y_ my_{m-1}\dots y_ 1)_ B\) and \(j = (0 0\dots x_ 1x_ 2\dots x_ m)_ B\). If \(P\) is an even number, then \(B = 2^ m\), and \(0 \leq i,j \leq B^{m-1} = \sqrt{N}-1\). Thus \(k = (x_ mx_{m-1}\dots x_ 1y_ my_{m-1}\dots y_ 1)_ B = i + R[j]\). Hence \(R[k] = R[i]+j\). If \(P\) is odd, \(P = 2m+1\), and \(0 \leq i,j \leq B^ m-1 = \sqrt{N/B}-1\). Then \(k = i + R[j] + zB^ m\) with the middle digit \(z\) where \(0 \leq z \leq B-1\). Thus \(R[k] = R[i] + j + zB^ m\).
- Fast digit-reversal algorithms on a shared-memory machine
- Bit Reversal through direct Fourier permutation method and Vectorial Digit Reversal generalization
- A second improved digit-reversal permutation algorithm for fast transforms
- scientific article; zbMATH DE number 436084 (Why is no real title available?)
- Fast Cell-Structured Algorithm for Digit Reversal of Arbitrary Length
- A new bit reversal algorithm
- An improved FFT digit-reversal algorithm
- scientific article; zbMATH DE number 1151845 (Why is no real title available?)
This page was built for publication: An improved digit-reversal permutation algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687353)
