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

MaRDI QIDQ2919787zbMATH OpenFDO

Authors Nicolaie Popescu-Bodorin

Publication date 22 October 2012

Published in ROMAI Journal (Search for Journal in Brave)

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

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)

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.

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

Cited in

(4)

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

Describes a project that uses

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)