Code covered by the BSD License

# 3-Part Demo Use of Simple Matlab Commands for Bit Reversal Required in Fast Fourier Transform or FFT

### AMITAVA BISWAS (view profile)

3-Part Demo Uses Simple Matlab Commands for Bit Reversing Required in Fast Fourier Transform or FFT

biswas50.m
```disp 'Simple Demo of Bit Reversal'
disp 'Author: Amitava Biswas, PhD, FIEI, FIETE'
disp 'The University of Texas at El Paso'
disp 'Email:abiswas@utep.edu Phone:(915)747-8307'
disp 'Reference Article by Biswas, IEEE Transaction ASSP 1991'
close all; clear all;

scrsz = get(0,'ScreenSize'); % full screen looks better
figure('Position', scrsz, 'Units', 'normalized');
axes('Position',[0 0 1 1], 'Units','normalized');
axis([0 10 0 4]); % broad enough, change if necessary
axis on; grid on; hold on % looks ok
set(gca,'color',rand(1,3)/2+1/2) % just a light color

% a simple procedure to reverse bits directly
x=round(rand*10^12); % chose a number, big is not a big problem
xbin=dec2bin(x); % binary string, not a number now
xbinrev=fliplr(xbin); % reversed binary string, not a number yet
xrev=bin2dec(xbinrev); % now the number with bits reversed
% show me ...
text(1,3.5, ...
'Demo Part-I of Bit-Reversal by Amitava Biswas', ...
'fontsize',24); pause(1)
text(1,3.0, ...
'Uses Matlab command  bin2dec ( fliplr ( dec2bin ( x ) ) )', ...
'fontsize',24); pause(1)
text(1,2.5, ...
[num2str(x) ...
'    A large random number displayed in decimal notation'], ...
'fontsize',24); pause(1)
text(1,2, ...
[xbin '    Above number in binary'], ...
'fontsize',24); pause(1)
text(1,1.5, ...
[xbinrev '    Bits reversed'], ...
'fontsize',24); pause(1)
text(1,1.0, ...
[num2str(xrev) ...
'     Value in decimal notation after reversing the bits'], ...
'fontsize',24); pause(2)

scrsz = get(0,'ScreenSize'); % full screen looks better
figure('Position', scrsz, 'Units', 'normalized');
axes('Position',[0 0 1 1], 'Units','normalized');
axis([0 10 0 4]); % broad enough, change if necessary
axis on; grid on; hold on % looks ok
set(gca,'color',rand(1,3)/2+1/2) % just a light color
text(1,3.5, ...
'Demo Part-II of Bit-Reversal by Amitava Biswas', ...
'fontsize',24); pause(1)
text(1,3.0, ...
['Uses Matlab command ' ...
' xrev = bitxor (xrev, 2^n / (1 + 1/bitxor(x, x-1)))'], ...
'fontsize',24); pause(1)

n=4; % number of bits, change as necessary
for x=0:2^n-1
if x==0;
xrev=0; % initialize
else
xrev=bitxor(xrev,2^n/(1+1/bitxor(x,x-1)));
end
text(1,2.5-x/8, ...
[num2str(x,'%02d') '   ' dec2bin(x,n) '   ' dec2bin(xrev,n)], ...
'fontsize',16); pause(1/4)
end

scrsz = get(0,'ScreenSize'); % full screen looks better
figure('Position', scrsz, 'Units', 'normalized');
axes('Position',[0 0 1 1], 'Units','normalized');
axis([0 10 0 4]); % broad enough, change if necessary
axis on; grid on; hold on % looks ok
set(gca,'color',rand(1,3)/2+1/2) % just a light color
text(1,3.5, ...
'Demo Part-III of Bit-Reversal by Amitava Biswas', ...
'fontsize',24); pause(1)
text(1,3.0, ...
['Necessary and sufficient swap pairs for FFT'], ...
'fontsize',24); pause(1)

n=4; incr=zeros(1,2^n); % initialize table
incrx=2*4^n; % starting value
for k=0:n-1; % ok
incrx=(incrx-4^n)/2; % increments for mirror image
incr(1+(2^k:2*2^k:2^n))=incrx;
end;

bitrev=0; % initialize
disp('verify mirror image increments')
for k=0:2^n-1
bitrev=bitrev+incr(k+1); % increment mirror image
disp([num2str(k) ' ' dec2bin(k,2*n) ...
' ' dec2bin(bitrev,2*n)]) % show bits
end

for p=0:2^n-2 % traverse UNB matrix, see cited reference above
prima=p+bin2dec(fliplr(dec2bin(p,2*n))); % perfect symmetry
seco=prima; % both are identical
for s=p+1:2^n-1 % traverse UNB matrix columns now
prima=prima+1; % increment regular
seco=seco+incr(s+1); % increment mirror image
text(0.1+p,1/2+s/8, ...
[dec2bin(prima,2*n) '<>' dec2bin(seco,2*n)], ...
'fontsize',8); pause(1/10)
end
end
disp('pretty simple and fun, no?')
```