Convolution (computer science)
Encyclopedia
In computer science
, specifically formal language
s, convolution (sometimes referred to as zip) is a function which maps a tuple
of sequence
s into a sequence
of tuple
s.
Let x1x2... x|x|, y1y2... y|y|, z1z2... z|z|, ... be n words (i.e. finite sequence
s) of elements of Σ. Let
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
:
,
where for any index i > |w|, the wi 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:
where
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 
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, specifically formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, convolution (sometimes referred to as zip) is a function which maps a tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
of sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
s into a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s.
Example
The convolution of and, fish, be isDefinition
Let Σ be an alphabet, # a symbol not in Σ.Let x1x2... x|x|, y1y2... y|y|, z1z2... z|z|, ... be n words (i.e. finite sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
s) of elements of Σ. Let
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
:,where for any index i > |w|, the wi 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:
where
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 .