1
$\begingroup$

I'm trying to understand how may I obtain the circular convolution of length L when the sequences I'm trying to convolve are of length greater than L.

For instance this Matlab code using sequences of length 5:

c = cconv([0,0.5,1,1,0.5],[0,0.5,1,1,0.5],4);

yields a 4 point sequence

2.25  2.5  2.25  2.0

and this Matlab code

cconv([0,0.5,1,1,0.5],[0,0.5,1,1,0.5],3)

yields a 3 point sequence

3 3 3

I know that circular convolution may be seen as linear convolution with aliasing and that if I perform the linear convolution and build overlapping periods spaced every N samples I will get the N point circular convolution but is there a way to obtain circular convolution without having to compute first linear convolution? I'm thinking about the classical way of doing convolution, where I flip one of the sequences in time and shift it and for every shift I multiply the 2 sequences and add to obtain the output sample for that shift

$\endgroup$
  • $\begingroup$ very similar if not a possible duplicate of this question $\endgroup$ – Fat32 Oct 9 '17 at 19:54
1
$\begingroup$

Circular convolution is a very close relative to linear one. Both of them are computed based on the same principles. However circular convolution has a periodic result (based on the fact that it's inputs are periodic), hence its computation can be affected by this.

When implementing a circular convolution there is no loss of efficiency if you actually use a linear convolution underhood (vice versa) as their computational efficiencies are very close, except if you are dealing with architecture optimized code.

On the other hand you may be asking for the penalty paid for computing a longer than necessary linear convolution in order to implement an $L$ point circular convolution of $N$ point periodic sequences when $L < N$. In such a case you can improve the efficiency by the following chopping method (borrowed from @DilipSarwate 's a relevant answer ) which I give here a basic MATLAB implementation from which you can see that the linear convolution is performed at the shorter length $L$, instead of the longer one $N$.

Below gives you a way of computing $L$ point circular convolution of $N$ point sequences where $ L < N$.

clc; clear all; close all;

% S0 - Define the Signals
% Note this is meaningful only when L < signal lengths
L = 3;                 % circular convolution length that we want to compute
x = [0 0.5 1 1 0.5];   % signal length is greater than L
h = x;

xL = zeros(1,L);       % these are for short, chopped signals.
hL = zeros(1,L);
for k=1:L              % compute the CHOPPED signals...
    xL(k) = sum( x(k:L:end) );
    hL(k) = sum( h(k:L:end) );
end
yN = conv(xL,hL);     % compute the linear convolution at the chopped length
yL = yN(1:N) + [yN(L+1:end) 0] ; post-process the result.
$\endgroup$
  • $\begingroup$ I have no idea which answer of mine is being deemed relevant here. Could you include a more precise citation? $\endgroup$ – Dilip Sarwate Oct 9 '17 at 17:25
  • $\begingroup$ @DilipSarwate this one...? $\endgroup$ – Fat32 Oct 9 '17 at 19:40
  • 1
    $\begingroup$ +1Thank you very much for your help but I'm not so interested in efficiency now. What I would like to know is can I compute this without having to do linear convolution? $\endgroup$ – VMMF Oct 10 '17 at 1:18
  • $\begingroup$ @VMMF Hmm I though you were afraid of the efficiency loss. Anyway. So why do you hesitate to perform a linear convolution ? $\endgroup$ – Fat32 Oct 10 '17 at 9:00
  • $\begingroup$ @Fat32 It is not that I'm not interested in efficiency, I'm just trying to understand first how circular convolution works and if I can do it without aliasing the linear convolution $\endgroup$ – VMMF Oct 10 '17 at 13:09
1
$\begingroup$

So far I haven't found a way to compute the circular convolution (of size N for sequences greater than N) that doesn't involve applying linear convolution + aliasing. Which is my original question

However, I have found in Sophocles J. Orfanidis' Introduction to signal processing page 518 a clever algorithm that allows me to obtain circular convolution from linear convolution + aliasing in an understandable way.

Here's my explanation:

First we must obtain linear convolution, then we place linear convolution output on time axis at intervals of L samples (sort of a periodic extension). As linear convolution output is greater than L samples, some samples will overlap (actually samples from more than one "period" will overlap on the main "period" from 0 to L-1). In obtaining circular convolution we are only interested in the interval 0 to L-1 (or 1 to L in Matlab)

For instance this example from the book computing 3 points circular convolution:

[1, 3, 3, 5, 3, 7, 4, 3, 3, 0, 1]  main period (direct linear convolution output)
[5, 3, 7, 4, 3, 3, 0, 1, 0, 0, 0]  1 period to the left contribution on main period
[4, 3, 3, 0, 1, 0, 0, 0, 0, 0, 0]  2 periods to the left contribution on main period
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  3 periods to the left contribution on main period

No further periods to the left are considered as they don't generate aliasing in the main period (linear convolution output is smaller than 3 shifts of 3 samples). In the end to form the sequence the first 3 positions (of main period) are summed in order to form the 3 point circular convolution which is (1+5+4+0,3+3+3+1,3+7+3+0) = (10,10,13)

The periods to the right are ignored as they don't contribute to aliasing in the main "period"

Here's my Matlab code (for generic sequences):

modulo = 4;
sequence1  = [0,0.5,1,1,0.5];
sequence2  = [0,0.5,1,1,0.5];
linealConvolution = conv(sequence1,sequence2);

stem(linealConvolution)
hold on

periods = linealConvolution;
times = 1;

while length(linealConvolution) >= times*modulo

    %shift the linealConvolution sequence modulo(amount) samples at a time and add
    %it to the previosly stored sequence (this adds the contribution of time 
    %aliased lineal convolutions on adjacent periods)

    aliasingPeriodToTheLeft = [ linealConvolution(times*modulo + 1: end) zeros(1,times*modulo) ] ;
    stem(aliasingPeriodToTheLeft)

    periods = periods + aliasingPeriodToTheLeft;
    times = times+1;

end

inTheEnd = periods(1:modulo);


figure
stem(inTheEnd)

%checking
isequal(cconv(sequence1,sequence2,modulo),inTheEnd) 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.