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 .

```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.