Convolution (computer science)

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 x1x2... x|x|, y1y2... y|y|, z1z2... 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 wi is #.

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

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Convolution — For the usage in formal language theory, see Convolution (computer science). Convolution of two square pulses: the resulting waveform is a triangular pulse. One of the functions (in this case g) is first reflected about τ = 0 and then offset by t …   Wikipedia

  • Abkürzungen/Computer — Dies ist eine Liste technischer Abkürzungen, die im IT Bereich verwendet werden. A [nach oben] AA Antialiasing AAA authentication, authorization and accounting, siehe Triple A System AAC Advanced Audio Coding AACS …   Deutsch Wikipedia

  • Liste der Abkürzungen (Computer) — Dies ist eine Liste technischer Abkürzungen, die im IT Bereich verwendet werden. A [nach oben] AA Antialiasing AAA authentication, authorization and accounting, siehe Triple A System AAC Advanced Audio Coding AACS …   Deutsch Wikipedia

  • Liste von Abkürzungen (Computer) — Dies ist eine Liste technischer Abkürzungen, die im IT Bereich verwendet werden. Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z siehe auch: Liste von Dateiendu …   Deutsch Wikipedia

  • Convolute — may also refer to: Convolution (mathematics and music) Circular convolution Convolution reverb Convolution sampling Convolution theorem Titchmarsh convolution theorem Dirichlet convolution Infimal convolute Logarithmic convolution Vandermonde… …   Wikipedia

  • Map (higher-order function) — In many programming languages, map is the name of a higher order function that applies a given function to each element of a list, returning a list of results. They are examples of both catamorphisms and anamorphisms. This is often called apply… …   Wikipedia

  • Scale-invariant feature transform — Exemple de résultat de la comparaison de deux images par la méthode SIFT (Fantasia ou Jeu de la poudre, devant la porte d’entrée de la ville de Méquinez, par Eug …   Wikipédia en Français

  • Scale space implementation — Scale space Scale space axioms Scale space implementation Feature detection Edge detection Blob detection Corner detection …   Wikipedia

  • Data compression — Source coding redirects here. For the term in computer programming, see Source code. In computer science and information theory, data compression, source coding or bit rate reduction is the process of encoding information using fewer bits than… …   Wikipedia

  • language — /lang gwij/, n. 1. a body of words and the systems for their use common to a people who are of the same community or nation, the same geographical area, or the same cultural tradition: the two languages of Belgium; a Bantu language; the French… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”