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

I am reading Proakis Digital signal processing using Matlab, 3rd edition I am performing example 5.23 but i am not getting same plot/results as book although i am using almost same code

First i am attaching my code and output and then i will attach snapshot of book containing code and output The issue with book code is that , i get error for "nu" variable and matlab says "NI" is undefined(i have underlined NI in book snapshot with red paint pencil) , so i used "NL" in my code and "NL"=N*L ,but i am not getting output as book

My code is as follows

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/plot snapshot is follow

[![enter image description here][2]][2]

Following is book snapshot [2]: https://i.stack.imgur.com/1wPVM.jpg

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? – engr Jun 18 '20 at 11:48
• Tiny minor comment: log10(N)/log10(2) could become log2(N) – Laurent Duval Jun 19 '20 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 ... – Matt L. Jun 19 '20 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. – Matt L. Jun 20 '20 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. – Matt L. Jun 23 '20 at 9:15