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_real_1d_nowork (c06ea) and nag_sum_fft_hermitian_1d_nowork (c06eb) to compute discrete Fourier transforms, and there are some restrictions on the value of

n

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_nowork (c06ek) 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_nowork (c06ek) 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 are:

\begin{array}{l} {\hat{Z}}_{k} = a_{k} + i b_{k} \\ {\hat{Z}}_{n - k} = a_{k} - i b_{k} \end{array}\} k = 0, 1, \dots n / 2

where

b_{0}

and

b_{n / 2}

when

n

is even then

x (k + 1)

holds

a_{k}

and

x (n - k + 1)

holds nonzero

b_{k}

(see 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 = 1$: At least one of the prime factors of n is greater than $19$ .

$ifail = 2$: n has more than $20$ prime factors.

$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_nowork (c06ek) is faster if the only prime factors of

n

are

2

3

5

; and fastest of all if

n

is a power of

2

On the other hand, nag_sum_convcorr_real_nowork (c06ek) is particularly slow if

n

has several unpaired prime factors, i.e., if the ‘square-free’ part of

n

has several factors. For such values of

n

, nag_sum_convcorr_real (c06fk) (which requires additional double workspace) is considerably faster.

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_nowork (c06ek)). In realistic computations the number of data values would be much larger.

Open in the MATLAB editor: c06ek_example

function c06ek_example


fprintf('c06ek 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] = c06ek(job, x, y);

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

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

c06ek 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