Circular Convolution of Length L of Sequences of Length Greater Than L

Question

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

Answer 1

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.

Answer 2

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) 

Answer 3

It seems simple to me. You are trying to perform a 4pt circular convolution of two 5 pt sequences. That is, you want to treat the 5 pt sequence as a 4 pt sequence which can be obtained by considering a 1-pt aliasing across multiple copies of the 5pt sequence.

So effectively, you are doing the below operation:

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

Note that you get the same result.