Bit Reversal through direct Fourier permutation method and Vectorial Digit Reversal generalization

zbMATH Open1265.65284arXiv1106.3635MaRDI QIDQ2919787FDOQ2919787

Authors: Nicolaie Popescu-Bodorin 

Publication date: 22 October 2012

Published in: ROMAI Journal (Search for Journal in Brave)

Abstract: This paper describes the Direct Fourier Permuation Algorithm, an efficient method of computing Bit Reversal of natural indices [1, 2, 3, ..., 2^k] in a vectorial manner (k iterations) and also proposes the Vectorial Digit Reversal Algorithm, a natural generalization of Direct Fourier Permutation Algorithm that is enabled to compute the r-digit reversal of natural indices [1, 2, 3, ..., r^k] where r is an arbitrary radix. Matlab functions implementing these two algo- rithms and various test and comparative results are presented in this paper to support the idea of inclusion of these two algorithms in the next Matlab Signal Processing Toolbox official distribution package as much faster alternatives to current Matlab functions bitrevorder and digitrevorder.

Full work available at URL: https://arxiv.org/abs/1106.3635

Recommendations

• A new bit reversal algorithm
• An improved digit-reversal permutation algorithm
• A new superfast bit reversal algorithm
• A recursive algorithm for quick and efficient bit reversing
• Novel algorithm for complex bit reversal: Employing vector permutation and branch reduction methods

zbMATH Keywords

Additive Constants MethodBit ReversalbitrevorderDanielson-Lanczos LemmadigitrevorderDirect Fourier Permutation MethodFast/Discrete Fourier TransformVectorial Digit Reversal

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

Cited In (4)

• bitrevorder
• Novel algorithm for complex bit reversal: Employing vector permutation and branch reduction methods
• A recursive algorithm for quick and efficient bit reversing
• An improved FFT digit-reversal algorithm

Uses Software

• Matlab
• Signal Processing Toolbox
• digitrevorder

This page was built for publication: Bit Reversal through direct Fourier permutation method and Vectorial Digit Reversal generalization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2919787)