image thumbnail

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

by

 

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 'Uploaded January 20, 2012'
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?')

Contact us