Contents

# Convolution and Correlation Data Allocation

This section explains the relation between:
• mathematical finite functions
u
,
v
,
w
introduced in Mathematical Notation and Definitions;
• multi-dimensional input and output data vectors representing the functions
u
,
v
,
w
;
• arrays
u
,
v
,
w
used to store the input and output data vectors in computer memory
The convolution and correlation routine parameters that determine the allocation of input and output data are the following:
• Data arrays
x
,
y
,
z
• Shape arrays
xshape
,
yshape
,
zshape
• Strides within arrays
xstride
,
ystride
,
zstride
• Parameters
start
,
decimation

## Finite Functions and Data Vectors

The finite functions
u(p)
,
v(q)
, and
w(r)
introduced above are represented as multi-dimensional vectors of input and output data:
inputu(i
1
,...,i
dims
)
for
u
(p
1
,...,p
N
)
inputv(j
1
,...,j
dims
)
for
v
(q
1
,...,q
N
)
output(k
1
,...,k
dims
)
for
w
(r
1
,...,r
N
).
Parameter
dims
represents the number of dimensions and is equal to N.
The parameters
xshape
,
yshape
, and
zshape
define the shapes of input/output vectors:
inputu(i
1
,...,i
dims
)
is defined if
1
i
n
xshape
(
n
)
for every
n=1,...,
dims
inputv(j
1
,...,j
dims
)
is defined if
1
j
n
yshape
(
n
)
for every
n=1,...,
dims
output(k
1
,...,k
dims
)
is defined if
1
k
n
zshape
(
n
)
for every
n=1,...,
dims
.
Relation between the input vectors and the functions
u
and
v
is defined by the following formulas:
inputu(i
1
,...,i
dims
)=
u
(p
1
,...,p
N
)
, where
p
n
= P
n
min
+ (i
n
-1)
for every
n
inputv(j
1
,...,j
dims
)=
v
(q
1
,...,q
N
)
, where
q
n
=Q
n
min
+ (j
n
-1)
for every
n
.
The relation between the output vector and the function
w(r)
is similar (but only in the case when parameters
start
and
decimation
are not defined):
output(k
1
,...,k
dims
)= w(r
1
,...,r
N
)
, where
r
n
=R
n
min
+ (k
n
-1)
for every
n
.
If the parameter
start
is defined, it must belong to the interval
R
n
min
start(n)
R
n
max
. If defined, the
start
parameter replaces
R
min
in the formula:
output(k
1
,...,k
dims
)=w(r
1
,...,r
N
)
, where
r
n
=start(n) + (k
n
-1)
If the parameter
decimation
is defined, it changes the relation according to the following formula:
output(k
1
,...,k
dims
)=w(r
1
,...,r
N
)
, where
r
n
= R
n
min
+ (k
n
-1)*decimation(n)
If both parameters
start
and
decimation
are defined, the formula is as follows:
output(k
1
,...,k
dims
)=w(r
1
,...,r
N
)
, where
r
n
=start(n) + (k
n
-1)*decimation(n)
The convolution and correlation software checks the values of
zshape
,
start
, and
decimation
r
n
exceeds
R
n
max
for some
k
n
,n=1,...,dims
, an error is raised.

## Allocation of Data Vectors

Both parameter arrays
x
and
y
contain input data vectors in memory, while array
z
is intended for storing output data vector. To access the memory, the convolution and correlation software uses only pointers to these arrays and ignores the array shapes.
For parameters
x
,
y
, and
z
, you can provide one-dimensional arrays with the requirement that actual length of these arrays be sufficient to store the data vectors.
The allocation of the input and output data inside the arrays
x
,
y
, and
z
is described below assuming that the arrays are one-dimensional. Given multi-dimensional indices
i
,
j
,
k
Z
N
, one-dimensional indices
e
,
f
,
g
Z
are defined such that:
inputu(i
1
,...,i
dims
) is allocated at
x(e)
inputv(j
1
,...,j
dims
) is allocated at
y(f)
output(k
1
,...,k
dims
) is allocated at
z(g)
.
The indices
e
,
f
, and
g
are defined as follows:
e
= 1 +
xstride
(n)·
dx
(n)
(the sum is for all
n=1,...,dims
)
f
= 1 +
ystride
(n)·
dy
(n)
(the sum is for all
n=1,...,dims
)
g
= 1 +
zstride
(n)·
dz
(n)
(the sum is for all
n=1,...,dims
)
The distances
dx(n)
,
dy(n)
, and
dz(n)
depend on the signum of the stride:
dx(n) = i
n
-1 if xstride(n)>0, or dx(n) = i
n
-xshape(n) if xstride(n)<0
dy(n) = j
n
-1 if ystride(n)>0, or dy(n) = j
n
-yshape(n) if ystride(n)<0
dz(n) = k
n
-1 if zstride(n)>0, or dz(n) = k
n
-zshape(n)
if zstride(n)<0
The definitions of indices
e
,
f
, and
g
assume that indexes for arrays
x
,
y
, and
z
are started from unity:
x(e)
is defined for
e=1,...,length(x)
y(f)
is defined for
f=1,...,length(y)
z(g)
is defined for
g=1,...,length(z)
Below is a detailed explanation about how elements of the multi-dimensional output vector are stored in the array
z
for one-dimensional and two-dimensional cases.
One-dimensional case.
If
dims
=1
, then
zshape
is the number of the output values to be stored in the array
z
. The actual length of array
z
may be greater than
zshape
elements.
If
zstride>1
, output values are stored with the stride:
output(1)
is stored to
z(1)
,
output(2)
is stored to
z(1+zstride)
, and so on. Hence, the actual length of
z
must be at least
1+zstride*(zshape-1)
elements or more.
If
zstride<0
, it still defines the stride between elements of array
z
. However, the order of the used elements is the opposite. For the
k-
th output value, output(
k
) is stored in
z(1+|zstride|*(zshape-k))
, where
|zstride|
is the absolute value of
zstride
. The actual length of the array
z
must be at least
1+|zstride|*(zshape - 1)
elements.
Two-dimensional case.
If
dims
=2
, the output data is a two-dimensional matrix. The value
zstride(1)
defines the stride inside matrix columns, that is, the stride between the
output(k
1
, k
2
)
and
output(k
1
+1, k
2
)
for every pair of indices
k
1
, k
2
. On the other hand,
zstride(2)
defines the stride between columns, that is, the stride between
output(k
1
,k
2
)
and
output(k
1
,k
2
+1)
.
If
zstride(2)
is greater than
zshape(1)
, this causes sparse allocation of columns. If the value of
zstride(2)
is smaller than
zshape(1)
, this may result in the transposition of the output matrix. For example, if
zshape = (2,3)
, you can define
zstride = (3,1)
to allocate output values like transposed matrix of the shape
3x2
.
Whether
zstride
assumes this kind of transformations or not, you need to ensure that different elements output (
k
1
, ...,k
dims
) will be stored in different locations
z(g)
.

#### Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.