# 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(i1,...,idims)` for `u(p1,...,pN)`

`inputv(j1,...,jdims)` for `v(q1,...,qN)`

`output(k1,...,kdims)` for `w(r1,...,rN).`

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(i1,...,idims)` is defined if `1 ≤ in ≤ xshape(n)` for every `n=1,...,dims`

`inputv(j1,...,jdims)` is defined if `1 ≤ jn ≤ yshape(n)` for every `n=1,...,dims`

`output(k1,...,kdims)` is defined if `1 ≤ kn ≤ 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(i1,...,idims)= u(p1,...,pN)`, where `pn = Pnmin + (in-1)` for every `n`

`inputv(j1,...,jdims)= v(q1,...,qN)`, where `qn=Qnmin + (jn-1)` for every `n`.

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(k1,...,kdims)= w(r1,...,rN)`, where `rn=Rnmin + (kn-1)` for every `n`.

If the parameter start is defined, it must belong to the interval `Rnmin ≤ start(n) ≤ Rnmax`. If defined, the start parameter replaces `Rmin` in the formula:

`output(k1,...,kdims)=w(r1,...,rN)`, where `rn=start(n) + (kn-1)`

If the parameter decimation is defined, it changes the relation according to the following formula:

`output(k1,...,kdims)=w(r1,...,rN)`, where `rn= Rnmin + (kn-1)*decimation(n)`

If both parameters start and decimation are defined, the formula is as follows:

`output(k1,...,kdims)=w(r1,...,rN)`, where `rn=start(n) + (kn-1)*decimation(n)`

The convolution and correlation software checks the values of zshape, start, and decimation during task commitment. If `rn` exceeds `Rnmax` for some `kn,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 ∈ ZN, one-dimensional indices e, f, g ∈ Z are defined such that:

`inputu(i1,...,idims) is allocated at x(e)`

`inputv(j1,...,jdims) is allocated at y(f)`

`output(k1,...,kdims) 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) = in-1 if xstride(n)>0, or dx(n) = in-xshape(n) if xstride(n)<0`

`dy(n) = jn-1 if ystride(n)>0, or dy(n) = jn-yshape(n) if ystride(n)<0`

`dz(n) = kn-1 if zstride(n)>0, or dz(n) = kn-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(k1, k2)` and `output(k1+1, k2)` for every pair of indices `k1, k2`. On the other hand, `zstride(2)` defines the stride between columns, that is, the stride between `output(k1,k2)` and `output(k1,k2+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 (`k1, ...,kdims`) will be stored in different locations `z(g)`.

Parent topic: Convolution and Correlation