if $job = 1$ , the discrete convolution of $x$ and $y$ , defined by
$z_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k - j} = \sum_{j = 0}^{n - 1} x_{k - j} y_{j};$
if $job = 2$ , the discrete correlation of $x$ and $y$ defined by
$w_{k} = \sum_{j = 0}^{n - 1} {\bar{x}}_{j} y_{k + j} .$

Here

x

and

y

are complex vectors, assumed to be periodic, with period

n

, i.e.,

x_{j} = x_{j \pm n} = x_{j \pm 2 n} = \dots

;

z

and

w

are then also periodic with period

n

Note: this usage of the terms ‘convolution’ and ‘correlation’ is taken from Brigham (1974). The term ‘convolution’ is sometimes used to denote both these computations.

\hat{x}

\hat{y}

\hat{z}

and

\hat{w}

are the discrete Fourier transforms of these sequences, and

\tilde{x}

is the inverse discrete Fourier transform of the sequence

x_{j}

, i.e.,

{\hat{x}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j} \times \exp (- i \frac{2 π j k}{n}), etc.,

and

{\tilde{x}}_{k} = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} x_{j} \times \exp (i \frac{2 π j k}{n}),

then

{\hat{z}}_{k} = \sqrt{n} . {\hat{x}}_{k} {\hat{y}}_{k}

and

{\hat{w}}_{k} = \sqrt{n} . {\bar{\hat{x}}}_{k} {\hat{y}}_{k}

(the bar denoting complex conjugate).

References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall

Parameters

Compulsory Input Parameters

1: $job$ – int64int32nag_int scalar

The computation to be performed:

$job = 1$: $z_{k} = \sum_{j = 0}^{n - 1} x_{j} y_{k - j}$ (convolution);
$job = 2$: $w_{k} = \sum_{j = 0}^{n - 1} {\bar{x}}_{j} y_{k + j}$ (correlation).

Constraint:

job = 1

2

2: $x (n)$ – complex array

The elements of one period of the vector

x

. If x is declared with bounds

(0 : n - 1)

in the function from which nag_sum_convcorr_complex (c06pk) is called, then

x (j)

must contain

x_{j}

, for

j = 0, 1, \dots, n - 1

3: $y (n)$ – complex array

The elements of one period of the vector

y

. If y is declared with bounds

(0 : n - 1)

in the function from which nag_sum_convcorr_complex (c06pk) is called, then

y (j)

must contain

y_{j}

, for

j = 0, 1, \dots, n - 1

Optional Input Parameters

1: $n$ – int64int32nag_int scalar: Default: the dimension of the arrays x, y. (An error is raised if these dimensions are not equal.)
$n$ , the number of values in one period of the vectors x and y. The total number of prime factors of n, counting repetitions, must not exceed $30$ .

Constraint: $n \geq 1$ .

Output Parameters

1: $x (n)$ – complex array: The corresponding elements of the discrete convolution or correlation.
2: $y (n)$ – complex array: The discrete Fourier transform of the convolution or correlation returned in the array x.
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$

On entry,

n < 1

$ifail = 2$

On entry,

job \neq 1

2

$ifail = 3$: An unexpected error has occurred in an internal call. Check all function calls and array dimensions. Seek expert help.

$ifail = 4$

On entry,

n has more than

30

prime factors.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

The results should be accurate to within a small multiple of the machine precision.

Further Comments

The time taken is approximately proportional to

n \times \log (n)

, but also depends on the factorization of

n

. nag_sum_convcorr_complex (c06pk) is faster if the only prime factors of

n

are

2

3

5

; and fastest of all if

n

is a power of

2

Example

This example reads in the elements of one period of two complex vectors

x

and

y

, and prints their discrete convolution and correlation (as computed by nag_sum_convcorr_complex (c06pk)). In realistic computations the number of data values would be much larger.

Open in the MATLAB editor: c06pk_example

function c06pk_example


fprintf('c06pk example results\n\n');

a = 1 - 0.5i;
b =   - 0.5i;
x(1:5) = a;
x(6:9) = b;
y(1:4) = a/2;
y(5:9) = b/2;

job = int64(1);
[conv, tconv, ifail] = c06pk(job, x, y);
job = int64(2);
[corr, tcorr, ifail] = c06pk(job, x, y);

result = [transpose(conv) transpose(corr)];
disp('      Convolution        Correlation');
disp(result);

c06pk example results

      Convolution        Correlation
  -0.6250 - 2.2500i   3.1250 - 0.2500i
  -0.1250 - 2.2500i   2.6250 - 0.2500i
   0.3750 - 2.2500i   2.1250 - 0.2500i
   0.8750 - 2.2500i   1.6250 - 0.2500i
   0.8750 - 2.2500i   1.1250 - 0.2500i
   0.3750 - 2.2500i   1.6250 - 0.2500i
  -0.1250 - 2.2500i   2.1250 - 0.2500i
  -0.6250 - 2.2500i   2.6250 - 0.2500i
  -1.1250 - 2.2500i   3.1250 - 0.2500i

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox