Convolution (computer science)

In computer science, specifically formal languages, convolution (sometimes referred to as zip) is a function which maps a tuple of sequences into a sequence of tuples.

Example

The convolution of and, fish, be is

$(a,f,b)(n,i,e)(d,s,\#)(\#,h,\#)$

Definition

Let Σ be an alphabet, # a symbol not in Σ.

Let x₁x₂... x_|x|, y₁y₂... y_|y|, z₁z₂... z_|z|, ... be n words (i.e. finite sequences) of elements of Σ. Let $\ell$ denote the length of the longest word, i.e. the maximum of |x|, |y|, |z|, ... .

The convolution of these words is a finite sequence of n-tuples of elements of (Σ ∪ {#}), i.e. an element of $((\Sigma\cup\{\# \})^n)^*$:

$(x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_\ell,y_\ell,\ldots)$,

where for any index i > |w|, the w_i is #.

The convolution of x, y, z, ... is denoted conv( x, y, z, ...), zip( x, y, z, ...) or x ⋆ y ⋆ z ⋆ ...

The inverse to convolution is sometimes denoted unzip.

A variation of the convolution operation is defined by:

$(x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_{\underline{\ell}},y_{\underline{\ell}},\ldots)$

where $\underline{\ell}$ is the minimum length of the input words. It avoids the use of an adjoined element $\#$, but destroys information about elements of the input sequences beyond $\underline{\ell}$.

This article incorporates material from convolution on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.