Documentation

cconv

Modulo-N circular convolution

Syntax

c = cconv(a,b,n)
c = cconv(gpuArrayA,gpuArrayB,n)

Description

Circular convolution is used to convolve two discrete Fourier transform (DFT) sequences. For long sequences, circular convolution can be faster than linear convolution.

c = cconv(a,b,n) circularly convolves vectors a and b. n is the length of the resulting vector. If you omit n, it defaults to length(a)+length(b)-1. When n = length(a)+length(b)-1, the circular convolution is equivalent to the linear convolution computed with conv. You can also use cconv to compute the circular cross-correlation of two sequences.

c = cconv(gpuArrayA,gpuArrayB,n) returns the circular convolution of the input vectors of class gpuArray. See Establish Arrays on a GPU for details on gpuArray objects. Using cconv with gpuArray objects requires Parallel Computing Toolbox™ software and a CUDA-enabled NVIDIA GPU with compute capability 1.3 or above. See http://www.mathworks.com/products/parallel-computing/requirements.html for details. The output vector, c, is a gpuArray object. See Circular Convolution Using the GPU for an example of using the GPU to compute the circular convolution.

Examples

collapse all

Circular Convolution

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 =

    14    16    14    16

Circular Convolution and Linear Convolution

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.

Circular Cross-Correlation

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

Circular Convolution with Varying Output Length

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

x1 = conv([1 1 1],[1 1 1])
x2 = [-1 1]
x1 =

     1     2     3     2     1


x2 =

    -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)

lcnv = conv(x1,x2)
ccnv =

   -1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000


lcnv =

    -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)

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

    -1     1


mod2 =

    -1     1

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

ccn3 = cconv(x1,x2,3)

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

     0     0     0


mod3 =

     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)

modc = sum(reshape(z,c,numel(z)/c)')
ccnc =

    0.0000   -1.0000   -1.0000    1.0000    1.0000


modc =

     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)

modd = z'
ccnd =

  Columns 1 through 7

   -1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000    0.0000

  Columns 8 through 13

   -0.0000    0.0000    0.0000    0.0000   -0.0000   -0.0000


modd =

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

Circular Convolution Using the GPU

The following example requires Parallel Computing Toolbox software and a CUDA-enabled NVIDIA GPU with compute capability 1.3 or above. See http://www.mathworks.com/products/parallel-computing/requirements.html for details.

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)

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

cirC = gather(cirC);

References

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

See Also

|

Introduced in R2007a

Was this topic helpful?