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} x_{j} y_{k + j} .$

Here

x

and

y

are real 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, 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.,

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

This function calls the same auxiliary functions as nag_sum_fft_realherm_1d (c06pa) to compute discrete Fourier transforms.

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} x_{j} y_{k + j}$ (correlation).

Constraint:

job = 1

2

2: $x (n)$ – double 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_real (c06fk) is called, then

x (j)

must contain

x_{j}

, for

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

3: $y (n)$ – double 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_real (c06fk) 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.

Constraint: $n > 1$ .

Output Parameters

1: $x (n)$ – double array: The corresponding elements of the discrete convolution or correlation.
2: $y (n)$ – double array: The discrete Fourier transform of the convolution or correlation returned in the array x; the transform is stored in Hermitian form; if the components of the transform $z_{k}$ are written as $a_{k} + i b_{k}$ , then for $0 \leq k \leq n / 2$ , $a_{k}$ is contained in $y (k)$ , and for $1 \leq k \leq n / 2 - 1$ , $b_{k}$ is contained in $y (n - k)$ . (See also Real transforms in the C06 Chapter Introduction.)
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 = 3$

On entry,

n \leq 1

$ifail = 4$

On entry,

job \neq 1

2

$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_real (c06fk) 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 real vectors

x

and

y

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

Open in the MATLAB editor: c06fk_example

function c06fk_example


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

x = [1;    1;    1;    1;    1;    0;    0;    0;    0];
y = [0.5;  0.5;  0.5;  0.5;  0;    0;    0;    0;    0];

job = int64(1);
[conv, tconv, ifail] = c06fk(job, x, y);

job = int64(2);
[corr, tcorr, ifail] = c06fk(job, x, y);

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

c06fk example results

Convolution  Correlation
    0.5000    2.0000
    1.0000    1.5000
    1.5000    1.0000
    2.0000    0.5000
    2.0000    0.0000
    1.5000    0.5000
    1.0000    1.0000
    0.5000    1.5000
    0.0000    2.0000

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

Chapter Contents

Chapter Introduction

NAG Toolbox