cconv

Modulo-n circular convolution

Description

example

c = cconv(a,b) convolves vectors a and b.

example

c = cconv(a,b,n) circularly convolves vectors a and b. n is the length of the resulting vector. You can also use cconv to compute the circular cross-correlation of two sequences.

Examples

collapse all

Generate two signals of different lengths. Compare their circular convolution and their linear convolution. Use the default value for n.

a = [1 2 -1 1];
b = [1 1 2 1 2 2 1 1];

c = cconv(a,b);            % Circular convolution
cref = conv(a,b);          % Linear convolution

dif = norm(c-cref)
dif = 9.7422e-16

The resulting norm is virtually zero, which shows that the two convolutions produce the same result to machine precision.

Generate two vectors and compute their modulo-4 circular convolution.

a = [2 1 2 1];
b = [1 2 3 4];
c = cconv(a,b,4)
c = 1×4

14    16    14    16

Generate two complex sequences. Use cconv to compute their circular cross-correlation. Flip and conjugate the second operand to comply with the definition of cross-correlation. Specify an output vector length of 7.

a = [1 2 2 1]+1i;
b = [1 3 4 1]-2*1i;
c = cconv(a,conj(fliplr(b)),7);

Compare the result to the cross-correlation computed using xcorr.

cref = xcorr(a,b);
dif = norm(c-cref)
dif = 3.3565e-15

Generate two signals: a five-sample triangular waveform and a first-order FIR filter with response $H\left(z\right)=1-{z}^{-1}$.

x1 = conv([1 1 1],[1 1 1])
x1 = 1×5

1     2     3     2     1

x2 = [-1 1]
x2 = 1×2

-1     1

Compute their circular convolution with the default output length. The result is equivalent to the linear convolution of the two signals.

ccnv = cconv(x1,x2)
ccnv = 1×6

-1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000

lcnv = conv(x1,x2)
lcnv = 1×6

-1    -1    -1     1     1     1

The modulo-2 circular convolution is equivalent to splitting the linear convolution into two-element arrays and summing the arrays.

ccn2 = cconv(x1,x2,2)
ccn2 = 1×2

-1     1

nl = numel(lcnv);
mod2 = sum(reshape(lcnv,2,nl/2)')
mod2 = 1×2

-1     1

Compute the modulo-3 circular convolution and compare it to the aliased linear convolution.

ccn3 = cconv(x1,x2,3)
ccn3 = 1×3

0     0     0

mod3 = sum(reshape(lcnv,3,nl/3)')
mod3 = 1×3

0     0     0

If the output length is smaller than the convolution length and does not divide it exactly, pad the convolution with zeros before adding.

c = 5;
z = zeros(c*ceil(nl/c),1);
z(1:nl) = lcnv;

ccnc = cconv(x1,x2,c)
ccnc = 1×5

0.0000   -1.0000   -1.0000    1.0000    1.0000

modc = sum(reshape(z,c,numel(z)/c)')
modc = 1×5

0    -1    -1     1     1

If the output length is equal to or larger than the convolution length, pad the convolution and do not add.

d = 13;
z = zeros(d*ceil(nl/d),1);
z(1:nl) = lcnv;

ccnd = cconv(x1,x2,d)
ccnd = 1×13

-1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000    0.0000   -0.0000    0.0000    0.0000    0.0000   -0.0000   -0.0000

modd = z'
modd = 1×13

-1    -1    -1     1     1     1     0     0     0     0     0     0     0

The following example requires Parallel Computing Toolbox™ software. Refer to GPU Support by Release (Parallel Computing Toolbox) to see what GPUs are supported.

Create two signals consisting of a 1 kHz sine wave in additive white Gaussian noise. The sample rate is 10 kHz

Fs = 1e4;
t = 0:1/Fs:10-(1/Fs);
x = cos(2*pi*1e3*t)+randn(size(t));
y = sin(2*pi*1e3*t)+randn(size(t));

Put x and y on the GPU using gpuArray. Obtain the circular convolution using the GPU.

x = gpuArray(x);
y = gpuArray(y);
cirC = cconv(x,y,length(x)+length(y)-1);

Compare the result to the linear convolution of x and y.

linC = conv(x,y);
norm(linC-cirC,2)
ans =

1.4047e-08

Return the circular convolution, cirC, to the MATLAB® workspace using gather.

cirC = gather(cirC);

Input Arguments

collapse all

Input array, specified as vectors or gpuArray objects. See Run MATLAB Functions on a GPU (Parallel Computing Toolbox) for details on gpuArray objects. Using cconv with gpuArray objects requires Parallel Computing Toolbox™ software. Refer to GPU Support by Release (Parallel Computing Toolbox) to see what GPUs are supported.

Example: sin(2*pi*(0:9)/10) + randn([1 10])/10 specifies a noisy sinusoid as a row vector.

Example: gpuArray(sin(2*pi*(0:9)/10) + randn([1 10])/10) specifies a noisy sinusoid as a gpuArray object.

Data Types: single | double
Complex Number Support: Yes

Convolution length, specified as a positive integer. If you do not specify n, then the convolution has length length(a)+length(b)-1.

Output Arguments

collapse all

Circular convolution of input vectors, returned as a vector or gpuArray.

Tips

For long sequences, circular convolution can be faster than linear convolution.

 Orfanidis, Sophocles J. Introduction to Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1996, pp. 524–529.