# Confusion regarding plot of linear convolution vs fast convolution via FFT

## Question

[Example 5.23 of Digital Signal Processing Using MATLAB Third Edition By Vinay K. Ingle and John G. Proakis ]

I am not getting same plot/results as book although I am using almost same code

The issue with book code is that, I get error for NI variable and MATLAB says NI is undefined, (I have red-underlined NI in Snapshot), so I used NL in my code and NL=N*L, but I am not getting output as book

## My Code

clc;clear all;close all;
conv_time = zeros(1,150); fft_time = zeros(1,150);
%
for L = 1:150
tc = 0; tf=0;
N = 2*L-1; nu = ceil(log10(N*L)/log10(2)); N = 2^nu;
for I=1:100
h = randn(1,L); x = rand(1,L);
t0 = clock; y1 = conv(h,x); t1=etime(clock,t0); tc = tc+t1;
t0 = clock; y2 = ifft(fft(h,N).*fft(x,N)); t2=etime(clock,t0);
tf = tf+t2;
end
%
conv_time(L)=tc/100; fft_time(L)=tf/100;
end
%
n = 1:150; subplot(1,1,1);
plot(n(25:150),conv_time(25:150),n(25:150),fft_time(25:150))


## My Output

The variable NI in the book is just a typo, it should be N instead (not N*L as in your code). Apart from that, remember that book was written about $$25$$ years ago, and the code was run on a $$33$$ MHz $$486$$ PC. So in order to see some effects on today's computers, you should crank up the value of L.

I've modified the code a bit (see below). Now the figure illustrates the expected result.

L = 200:500:10000;
K = length(L);
conv_time = zeros(1,K); fft_time = zeros(1,K);
Nav = 10;

for k = 1:K
tc = 0; tf=0;
Lk = L(k);
N = 2*Lk-1; nu = ceil(log10(N)/log10(2)); N = 2^nu;
for I=1:Nav
h = randn(1,Lk); x = rand(1,Lk);
t0 = clock; y1 = conv(h,x); t1=etime(clock,t0); tc = tc+t1;
t0 = clock; y2 = ifft(fft(h,N).*fft(x,N)); t2=etime(clock,t0);
tf = tf+t2;
end
conv_time(k)=tc/Nav; fft_time(k)=tf/Nav;
end

plot(L,conv_time,L,fft_time)


• your code worked awesome. But why you are dividing tc and tf ,both by Nav? Jun 18, 2020 at 11:48
• Tiny minor comment: log10(N)/log10(2) could become log2(N) Jun 19, 2020 at 19:49
• @LaurentDuval: That's right, I just left that part of the original code unchanged. Maybe matlab didn't have log2 back then ... Jun 19, 2020 at 20:44
• @engr: $2L-1$ is the minimum required FFT length to avoid circular convolution artefacts. The actual FFT length $N$ is chosen such that it is the smallest power of $2$ that is greater than or equal to $2L-1$. FFTs lengths that are powers of $2$ result in especially efficient implementations. Jun 20, 2020 at 9:23
• @engr: I actually already did. As I said, $N$ is chosen as the power of $2$ that is greater than or equal to $2L-1$. So you compute the logarithm (with base $2$) of $2L-1$, chose the smallest integer that is greater than or equal to that number (ceil), and then you take $2$ to the power of that number. Jun 23, 2020 at 9:15