کانولوشن

Convolution of two square pulses: the resulting waveform is a triangular pulse. The integral of their product is the area of the yellow region.

Convolution of a square pulse (as input signal) with the impulse response of an RC circuit in order to obtain the output signal waveform. The integral of their product is the area of the yellow region.

کانولوشن یا همگشت (به انگلیسی: Convolution) در ریاضیات یا به طور دقیق‌تر آنالیز تابعی، یک عملگر ریاضی است که بر روی دو تابع f و g عمل کرده، و تابع سومی را تولید می‌کند که می‌توان به عنوان نسخه تصحیح شده یکی از دو تابع اصلی نگریسته شود. کانولوشن مشابه تابع هم بستگی است. کاربردهای این عملگر شامل آمار، بینایی رایانه‌ای، پردازش تصویر، پردازش سیگنال، مهندسی برق و معادلات دیفرانسیل می‌شود.

کانولوشن (همگشت) را می‌توان برای توابعی از گروه‌های غیر از فضای اقلیدسی تعریف کرد. در حالت خاص، کانولوشن حلقوی را می‌توان برای توابع متناوب (یعنی توابع روی دایره) تعریف کرد، و کانولوشن گسسته را می‌توان برای توابع مجموعه اعداد صحیح تعریف کرد. چنین تعمیم‌هایی از کانولوشن دارای کاربردهایی در زمینه تحلیل عددی، جبر خطی عددی، و در طراحی و اجرای فیلترهای پاسخ ضربه محدود در پردازش سیگنال دارند.

محاسبه معکوس کانولوشن (همگشت)، دکانولوشن نام دارد.

تاریخچه

عمل

$\int _{0}^{t}\varphi (s)\psi (t-s)ds$$\int _{0}^{t}\varphi (s)\psi (t-s)ds$،

به ازای

$0\leq t<\infty$$0\leq t<\infty$،

حالت خاص ضرب ترکیبی است که ریاضیدان ایتالیایی ویتو ولترا آن را مطرح کرده است.

کانولوشن اصولاً به نام "faltung" (که همان folding انگلیسی باشد)، توسط یک ریاضیدان آلمانی به نام گوستاو دوش معرفی شد.

تعریف

کانولوشن (همگشت) ƒ و g به صورت ƒ*g نوشته می‌شود. این تعریف به صورت انتگرال حاصلضرب دو تابع که یکی از آنها برعکس شده و روی یکدیگر می‌لغزند تعریف می‌شود. با این تعریف، کانولوشن یک نوع خاص از تبدیل انتگرالی است

$(f*g)(t)\ \ \,$$(f*g)(t)\ \ \,$	${\stackrel {\mathrm {def} }{=}}\ \int _{-\infty }^{\infty }f(\tau )\,g(t-\tau )\,d\tau$${\stackrel {\mathrm {def} }{=}}\ \int _{-\infty }^{\infty }f(\tau )\,g(t-\tau )\,d\tau$
	$=\int _{-\infty }^{\infty }f(t-\tau )\,g(\tau )\,d\tau .$$=\int _{-\infty }^{\infty }f(t-\tau )\,g(\tau )\,d\tau .$       (commutativity)

با این که t در رابطه بالا مورد استفاده قرار گرفته است، لزومی برای کار در دامنه زمان نداریم؛ ولی در متون علمی، فرمول کانولوشن را می‌توان به عنوان میانگین وزنی تابع (ƒ(τ با مومنتوم t در نظر بگیریم که وزن‌ها توسط (g(−τ به اندازه t جابجا می‌شوند (لغزش می‌کنند). با تغییر t، تابع وزنی قیمت هاب مختلف تابع ورودی را برجسته می‌کند. به طور کلی، اگر f و g بر روی R^d توابع با مقدار مختلط باشند، آنگاه کانولوشن را می‌توان به صورت انتگرای زیر تعریف کرد:

$(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy=\int _{\mathbf {R} ^{d}}f(x-y)g(y)\,dy.$$(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy=\int _{\mathbf {R} ^{d}}f(x-y)g(y)\,dy.$

شرح تصویری کانولوشن

۱. بیان هر تابع بر حسب متغیر زائد $\tau$$\tau$. ۲. معکوس کردن یکی از توابع: $g(-\tau )$$g(-\tau )$→$g(\tau )$$g(\tau )$. ۳. افزودن فاصله زمانی(t) که $g(t-\tau )$$g(t-\tau )$ را در راستای محور $\tau$$\tau$ جابجا می‌کند. ۴. با شروع t از ∞- تا ∞+. هر زمان که دو تابع با هم برخورد کردند، انتگرال حاصلضرب آن‌ها را پیدا کنید. به عبارت دیگر، میانگین وزنی تابع متحرک $f(\tau )$$f(\tau )$ را زمانی که تابع وزنی آن $g(-\tau )$$g(-\tau )$ تعریف شده باشد را بدست آورید. شکل موج بدست آمده (که در اینجا نمایش داده نشده است) کانولوشن تابع f و g است. اگر (f(t تابع ضربه باشد، نتیجه این عمل همان (g(t خواهد بود، که پاسخ ضربه نامیده می‌شود.

کانولوشن (همگشت) دایره‌ای

وقتی یک تابع g_T متناوب باشد (که T دوره تناوب آن است)، آنگاه برای تابع ƒ (به طوری که ƒ∗g_T وجود داشته باشد)، کانولوشن نیز متناوب و یکتا خواهد بود:

$(f*g_{T})(t)\equiv \int _{t_{0}}^{t_{0}+T}\left[\sum _{k=-\infty }^{\infty }f(\tau +kT)\right]g_{T}(t-\tau )\ d\tau ,\,$$(f*g_{T})(t)\equiv \int _{t_{0}}^{t_{0}+T}\left[\sum _{k=-\infty }^{\infty }f(\tau +kT)\right]g_{T}(t-\tau )\ d\tau ,\,$

که t_o یک مقدار انتخاب است. جمع، یک بسط متناوب از تابع ƒ خوانده می‌شود.

اگر g_T بسط متناوب یک تابع دیگر (مثلاً g) باشد، آنگاه رابطه ƒ∗g_T را کانولوشن دایره‌ای ƒ و g می‌نامند.

کانولوشن گسسته

برای توابع دارای مقدار مختلط ƒ، g بر روی مجموعه اعداد صحیح Z تعریف شده است، انتگرال گسسته ƒ و g' با رابطه زیر بدست می‌آید:

$(f*g)[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }f[m]\,g[n-m]$$(f*g)[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }f[m]\,g[n-m]$

$=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].$$=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].$ (جابجا پذیری)

زمانی که دو چندجمله‌ای را ضرب می‌کنیم، ضرایب حاصلضرب توسط کانولوشن توالی ضرایب اصلی بدست می‌آید، که برای جلوگیری از ایجاد جمله‌های تعریف نشده با عدد صفر بسط داده می‌شوند؛ این عمل تحت عنوان حاصلضرب کوشی ضرایب دو چند جمله‌ای شناخته می‌شود.

کانولوشن گسسته دایره‌ای

وقتی یک تابع g_N (با تناوب N) متناوب است، آنگاه برای توابعی مانند ƒ، به طوری که ƒ∗g_N وجود داشته باشد، کانولوشن متناوب و یکتا خواهد بود:

$(f*g_{N})[n]\equiv \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{f}[m+kN]\right)g_{N}[n-m]\,$$(f*g_{N})[n]\equiv \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{f}[m+kN]\right)g_{N}[n-m]\,$

حاصل این مجموع بر روی k را بسط دوره‌ای تابع ƒ می‌نامند.

اگر g_N بسط دوره‌ای یک تابع دیگر باشد، g، آنگاه عبارت ƒ∗g_N را کانولوشن دایره‌ای ƒ و g می‌نامند.

زمانی که طول زمانی غیرصفر هر دو تابع ƒ و g به محدوده [0, N-۱] مقید شود، آنگاه ƒ∗g_N به صورت زیر کاهش خواهد یافت:

$(f*g_{N})[n]=\sum _{m=0}^{N-1}f[m]\ g_{N}[n-m]\,$$(f*g_{N})[n]=\sum _{m=0}^{N-1}f[m]\ g_{N}[n-m]\,$

(Eq.1)

$=\sum _{m=0}^{n}f[m]\ g[n-m]+\sum _{m=n+1}^{N-1}f[m]\ g[N+n-m]\,$$=\sum _{m=0}^{n}f[m]\ g[n-m]+\sum _{m=n+1}^{N-1}f[m]\ g[N+n-m]\,$

$=\sum _{m=0}^{N-1}f[m]\ g[(n-m)_{\mod {N}}]\quad {\stackrel {\mathrm {def} }{=}}\quad (f*_{N}g)[n]\,$$=\sum _{m=0}^{N-1}f[m]\ g[(n-m)_{\mod {N}}]\quad {\stackrel {\mathrm {def} }{=}}\quad (f*_{N}g)[n]\,$

نماد $(f*_{N}g)\,$$(f*_{N}g)\,$ برای کانولوشن دایره‌ای یادآور کانولوشن بر روی گروه دایروی یک integers modulo N است.

الگوریتم‌های کانولوشن سریع

در برخی حالات، کانولوشن گسسته می‌تواند به کانولوشن دایره‌ای تبدیل شود تا بتوان از خواص کانولوشن برای اجرای تبدیل سریع توسط کامپیوتر بهره برد. برای مثال، کانولوشن توالی رقمی یک عمل بسیار مهم ضرب اعداد چندرقمی است، که در نتیجه می‌تواند به صورت بهینه‌ای با تکنیک‌های تبدیل پیاده‌سازی شود(Knuth 1997, §4.3.3.C; von zur Gathen & Gerhard 2003, §۸٫۲).

Eq.1 به ازای هر مقدار خروجی به N عمل محاسباتی نیاز دارد و در نتیجه N² عمل برای N خروجی؛ که این مقدار محاسبات با اشستفاده از هر کدام از الگوریتم‌های سریع به طور چشمگیریمی تواند کاهش یابد. پردازش سیگنال دیجیتال و دیگر کاربردهای مهندسی معمولاً از الگوریتم‌های کانولوشن سریع برای کاهش هزینه محاسبات کانولوشن با پیچیدگی از درجه O(N log N) اسشتفاده می‌کنند.

مرسوم‌ترین الگوریتم کانولوشن سریع، از الگوریتم‌های تبدیل فوریه سریع (FFT) قضیه کانلوشن دایره‌ای استفاده استفاده می‌کنند. در حالت خاص، کانولوشن دایره‌ای دو توالی با طول محدود را می‌توان با اعمال FFT هر کدام، ضرب نقطه به نقطه، و سپس اعمال FFT معکوس بدست آورد. در نتیجه انواع کانولوشن تعریف شده در بالا را به صورت بهینه می‌توان با استفاده از تکنیک‌هایی همراه با افزودن و/یا کاهش صفر خروجی پیاده‌سازی کرد. الگوریتم‌های کانولوشن سریع دیگر، مثل الگورستم شون هاگه- اشتقاسِن، نیز از تبدیل فوریه سریع در حلقه دیگ استفاده می‌کنند.

دامنه تعریف

کانولوشن دو تابع با مقدار مختلط بر روی R^d

$(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy$$(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy$

خوش تعریف است، تنها اگر ƒ و g به اندازه کافی در بینهایت افت سریع خواهد داشت که انتگرال آن وجود داشته باشد. شرایط وجود کانولوشن تا حدودی ما را به اشتباه میندازد، زیرا یک انفجار (blow up) در تابع g در بینهایت به راحتی با افت سریع تابع ƒ در بینهایت جبران می‌شود. در نتیجه مسئله وجود کانولوشن شامل شرایط دیگری بر روی ƒ و g می‌شود.

Compactly supported functions

اگر ƒ و g توابع ریاضی کاملاً پشتیبان شده باشند، آنگاه کانولوشن آنها وجود دارد، و همچنین تابع بدست آمده شکاملا پشتیبانی شده و پیوسته می‌باشد (Hörmander). اصولاً اگر یکی از توابع (مثلاً ƒ) کاملاً پشتیبانی شده و دیگری انتگرال پذیر بومی باشد، آنگاه ƒ∗g خوش تعریف و پیوسته خواهد بود.

توابع انتگرال پذیر

کانولوشن ƒ و g وجود دارد اگر ƒ و g هر دو توابع انتگرال پذیر لبسگو (در L¹(R^d)) باشند؛ در این حالت ƒ∗g نیز انتگرال پذیر است (Stein & Weiss 1971, Theorem 1.3). این بیان، یک نتیجه‌گیری از قضیه تونلی است. به همین صورت، اگر ƒ ∈ L¹(R^d) و g ∈ L^p(R^d) که 1 ≤ p ≤ ∞، آنگاه ƒ∗g ∈ L^p(R^d) و

$\|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}.\,$$\|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}.\,$

در حالت خاص p= ۱، شاین رابطه نشا می‌دهد که L¹ یک جبر باناچ تحت کانولوشن است (و تساوی دو طرف برقرار است اگر f و g در تمام نقاط غیرمنفی باشند).

به طور کلی تر، نامساوی یونگ بیان می‌کند که کانولوشن یک نگاشت دوطرفه پیوسته بین فضاهای L^p مناسب است. به طور خاص، اگر 1 ≤ p,q,r ≤ ∞ رابطه زیر را ارضا کنند

${\frac {1}{p}}+{\frac {1}{q}}={\frac {1}{r}}+1,$${\frac {1}{p}}+{\frac {1}{q}}={\frac {1}{r}}+1,$

آنگاه

$\|f*g\|_{r}\leq \|f\|_{p}\|g\|_{q},\quad f\in L^{p},\ g\in L^{q},$$\|f*g\|_{r}\leq \|f\|_{p}\|g\|_{q},\quad f\in L^{p},\ g\in L^{q},$

در نتیجه، کانولوشن نگاشت دوطرفه پیوسته از L^p×L^q به L^r است.

توابع با نزول سریع

علاوه بر توابع با پشتیبانی کامل و توابع انتگرال پذیر، توابعی که دارای سرعت نزول سریع در بینهایت هستندنیز می‌توانند تحت کانولوشن قرار بگیرند. یکی از ویژگی‌های مهم کانولوشن آن است که اگر ƒ و g هر دو سریعاً نزولی باشند، آنگاه ƒ∗g نیز به سرعت نزول می‌کند. با در نظر گرفتن این واقعیت که کانولوشن معمولاً با دیفرانسیل گیری همراه است (به خصوصیات مراجعه کنید)، باعث می‌شود که کلاس توابع شوارتز تحت کانولوشن بسته باشند.

توزیع‌ها

نوشتار اصلی: توزیع (ریاضیات)

تحت برخی شرایط، می‌توان کانولوشن یک تابع با یک توزیع، یا دو توزیع را تعریف کرد. اگر ƒ یک تابع کاملاً پشتیبانی شده باشد و g یک توزیع باشد، آنگاه ƒ∗g یک تابع نرم است که توسط فرمول توزیعی زیر تعریف می‌شود

$\int _{\mathbf {R} ^{d}}{f}(y)g(x-y)\,dy.$$\int _{\mathbf {R} ^{d}}{f}(y)g(x-y)\,dy.$

در حالت کلی تر، می‌توان تعریف کانولوشن را بسط داد که به طور یکتا، قانون زیر حتی در حالتی که ƒ یک توزیع باشد، و g یک توزیع کاملاً پشتیبانی شده در نظر بگیریم، بر قرار باشد (Hörmander 1983, §۴٫۲):

$f*(g*\varphi )=(f*g)*\varphi \,$$f*(g*\varphi )=(f*g)*\varphi \,$

اندازه‌ها

کانولوشن هر دو اندازه بورل μ و ν از تغییر محدود، اندازه λ است که با رابطه زیر تعریف می‌شود:

$\int _{\mathbf {R} ^{d}}f(x)d\lambda (x)=\int _{\mathbf {R} ^{d}}\int _{\mathbf {R} ^{d}}f(x+y)\,d\mu (x)d\nu (y).$$\int _{\mathbf {R} ^{d}}f(x)d\lambda (x)=\int _{\mathbf {R} ^{d}}\int _{\mathbf {R} ^{d}}f(x+y)\,d\mu (x)d\nu (y).$

این رابطه زمانی که μ و ν را توزیع در نظر بگیریم با کانولوشن‌های تعریف شده در بالا مطابقت دارد؛ همچنین برای کانولوشن توابع L¹ وقتی که μ و ν نسبت به اندازه لبسگو مطلقاً پیوسته باشند.

همچنین، کانولوشن اندازه‌ها نسخه دیگری از نامعادله یونگ که در زیر آمده است را ارضا می‌کنند

$\|\mu *\nu \|\leq \|\mu \|\|\nu \|$$\|\mu *\nu \|\leq \|\mu \|\|\nu \|$

که نُرم، تغییر کلی اندازه است. از آنجا که فضای اندازه تغییر محدود یک فضای باناخ است، با کانولوشن اندازه می‌توان مشابه روش‌های استاندارد تحلیل تابعی که قابل اعمال به توزیع‌ها نیست برخورد کرد.

Properties

خواص جبری

نوشتار(های) وابسته: Convolution algebra

کانولوشن یک ضرب را بر روی فضای برداری توابع انتگرال پذیر است. این حاصلضرب خواص ریاضی زیر را ارضا می‌کند، که به معنی آن است که فضای توابع انتگرال پذیر با حاصل کانولوشن یک جبر جابجا پذیر است بدون عنصر خنثی (Strichartz 1994, §۳٫۳). دیگر فضاهای برداری توابع، مثل فضای توابع پیوسته کاملاً پشتیبانی شده، تحت کانولوشن بسته هستند، و در نتیجه جزء جبرهای جابجاپذیر هستند.

جابجایی

$f*g=g*f\,$$f*g=g*f\,$

انجمنی

$f*(g*h)=(f*g)*h\,$$f*(g*h)=(f*g)*h\,$

توزیع پذیری

$f*(g+h)=(f*g)+(f*h)\,$$f*(g+h)=(f*g)+(f*h)\,$

؛ خاصیت انجمنی با یک عدد اسکالر

$a(f*g)=(af)*g=f*(ag)\,$$a(f*g)=(af)*g=f*(ag)\,$

به ازای هر عدد حقیقی (مختلط)${a}\,$${a}\,$

خنثی در ضرب

هیچ عمل جبری توابع، یک عامل خنثی در ضرب را برای کانولوشن ایجاد نمی‌کنند. کمبود عامل شخنثی در ضرب عملاً مشکل بزرگی به حساب نمی‌آید، زیرا زیرا اکثر توابعی که کانولوشن روی آنها انجام می‌شود را می‌توان با یک توزیع دیراک مورد کانولوشن قرار داد، یا حداقل (مثلاً برای حالت L¹) می‌توان تقریبی از عامل خنثی را برای آ «در نظر گرفت. ولی فضای برداری توزیع‌های کاملاً پشتیبانی شده، اجازه حضور عامل خنثی در ضرب را تحت کانولوشن به ما می‌دهند. به خصوص اینکه

$f*\delta =f\,$$f*\delta =f\,$

که δ توزیع دلتا است.

؛ عنصر معکوس

برخی توزیع‌ها برای کانولوشن یک عنصر معکوس دارند، S⁻¹، که با رابطه زیر تعریف می‌شوند

$S^{(-1)}*S=\delta .\,$$S^{(-1)}*S=\delta .\,$

مجموعه‌ای از توزیع‌های معکوس پذیر یک گروه آبلی را تحت کانولوشن تشکیل می‌دهند.

مزدوج مختلط؛ ${\overline {f*g}}={\overline {f}}*{\overline {g}}\!\$${\overline {f*g}}={\overline {f}}*{\overline {g}}\!\$

انتگرال گیری

اگر ƒ و g توابع انتگرال پذیر باشند، آنگاه انتگرال کانلوشن آنها در تمام فضا، از حاصلضرب انتگرال آنها بدست می‌آید:

$\int _{\mathbf {R} ^{d}}(f*g)(x)dx=\left(\int _{\mathbf {R} ^{d}}f(x)dx\right)\left(\int _{\mathbf {R} ^{d}}g(x)dx\right).$$\int _{\mathbf {R} ^{d}}(f*g)(x)dx=\left(\int _{\mathbf {R} ^{d}}f(x)dx\right)\left(\int _{\mathbf {R} ^{d}}g(x)dx\right).$

این رابطه از قضیه فوبینی بر گرفته شده است. نتیجه مشابهی نیز برقرار است در صورتی که ƒ و g فقط توابع قابل اندازه‌گیری غیرمنفی باشند توسط قضیه تونلی بیان می‌شود.

دیفرانسیل گیری

در حالت یک متغیری داریم

${\frac {d}{dx}}({f}*g)={\frac {df}{dx}}*g={f}*{\frac {dg}{dx}}\,$${\frac {d}{dx}}({f}*g)={\frac {df}{dx}}*g={f}*{\frac {dg}{dx}}\,$

که d/dx همان مشتق است. به طور کلی، در حالتی که توابعی از متغیرهای مختلف داشته باشیم، فرمول مشابهی با استفاده از مشتق پاره‌ای برقرار است

${\frac {\partial }{\partial x_{i}}}({f}*g)(x)={\frac {\partial f}{\partial x_{i}}}*g={f}*{\frac {\partial g}{\partial x_{i}}}.$${\frac {\partial }{\partial x_{i}}}({f}*g)(x)={\frac {\partial f}{\partial x_{i}}}*g={f}*{\frac {\partial g}{\partial x_{i}}}.$

یک نتیجه خاص این رابطه ان است که کانولوشن را می‌توان به شکل یک عمل «هموار کنندگی» نگاه کرد: کانولوشن ƒ و g به تعداد مرتبه‌ای که ƒ و g قابل دبفرانسیل گیری هستند، قابل دیفرانسیل گیری است.

این خاصیت تحت شرایطی برقرار است که ƒ و g مطلقاً انتگرال پذیر باشند و به عنوان یکی از نتایج نامعادله یونگ حداقل یکی از آنها دارای absolutely integrable (L¹) weak derivative. برای مثال، زمانی که ƒ مشتق پذیر پیوسته با پشتیبانی کامل باشد، و g یک تابع دلخواه و انتگرال پذیر محدود باشد، آ

${\frac {d}{dx}}({f}*g)={\frac {df}{dx}}*g.$${\frac {d}{dx}}({f}*g)={\frac {df}{dx}}*g.$

These identities also hold much more broadly in the sense of tempered distributions if one of ƒ or g is a compactly supported distribution or a Schwartz function and the other is a tempered distribution. On the other hand, two positive integrable and infinitely differentiable functions may have a nowhere continuous convolution.

In the discrete case, the روش تفاضلات محدود D ƒ(n) = ƒ(n + 1) − ƒ(n) satisfies an analogous relationship:

$D(f*g)=(Df)*g=f*(Dg).\,$$D(f*g)=(Df)*g=f*(Dg).\,$

قضیه کانولوشن

قضیه کانولوشن می‌کند که

${\mathcal {F}}\{f*g\}=k\cdot {\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$${\mathcal {F}}\{f*g\}=k\cdot {\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$

که ${\mathcal {F}}\{f\}\,$${\mathcal {F}}\{f\}\,$ بیان کننده تبدیل فوریه تابع $f$$f$ است، و $k$$k$ یک عدد ثابت است که وابسته به نرمالیزه تبدیل فوریه است (به ”خوصصیات تبدیل فوریه“ مراجعه کنید). برخی نسخه‌های دیگر این قضیه برای تبدیل لاپلاس، تبدیل لاپلاس دوسویه، تبدیل z و تبدیل ملین برقرار است.

[[همچنین می‌توانید به قضیه کانولوشن تیشمارش که اهمیت کمتری دارد مراجعه کنید.]]

Translation invariance

The convolution commutes with translations, meaning that

$\tau _{x}({f}*g)=(\tau _{x}f)*g={f}*(\tau _{x}g)\,$$\tau _{x}({f}*g)=(\tau _{x}f)*g={f}*(\tau _{x}g)\,$

where τ_xƒ is the translation of the function ƒ by x defined by

$(\tau _{x}f)(y)=f(y-x).\,$$(\tau _{x}f)(y)=f(y-x).\,$

If ƒ is a Schwartz function, then τ_xƒ is the convolution with a translated Dirac delta function τ_xƒ = ƒ∗τ_x δ. So translation invariance of the convolution of Schwartz functions is a consequence of the associativity of convolution.

Furthermore, under certain conditions, convolution is the most general translation invariant operation. Informally speaking, the following holds

• Suppose that S is a نقشه طولی acting on functions which commutes with translations: S(τ_xƒ) = τ_x(Sƒ) for all x. Then S is given as convolution with a function (or distribution) g_S; that is Sƒ = g_S∗ƒ.

Thus any translation invariant operation can be represented as a convolution. Convolutions play an important role in the study of time-invariant systems, and especially نظریه سیستم خطی تغییرناپذیر با زمان. The representing function g_S is the پاسخ ضربه of the transformation S.

A more precise version of the theorem quoted above requires specifying the class of functions on which the convolution is defined, and also requires assuming in addition that S must be a continuous linear operator with respect to the appropriate مکان‌شناسی. It is known, for instance, that every continuous translation invariant continuous linear operator on L¹ is the convolution with a finite Borel measure. More generally, every continuous translation invariant continuous linear operator on L^p for 1 ≤ p < ∞ is the convolution with a tempered distribution whose تبدیل فوریه is bounded. To wit, they are all given by bounded Fourier multipliers.

Convolutions on groups

If G is a suitable group endowed with a measure λ, and if f and g are real or complex valued integrable functions on G, then we can define their convolution by

$(f*g)(x)=\int _{G}f(y)g(y^{-1}x)\,d\lambda (y).\,$$(f*g)(x)=\int _{G}f(y)g(y^{-1}x)\,d\lambda (y).\,$

In typical cases of interest G is a locally compact Hausdorff topological group and λ is a (left-) Haar measure. In that case, unless G is unimodular, the convolution defined in this way is not the same as $\textstyle {\int f(xy^{-1})g(y)d\lambda (y)}$$\textstyle {\int f(xy^{-1})g(y)d\lambda (y)}$. The preference of one over the other is made so that convolution with a fixed function g commutes with left translation in the group:

$L_{h}(f*g)=(L_{h}f)*g=f*(L_{h}g).\,$$L_{h}(f*g)=(L_{h}f)*g=f*(L_{h}g).\,$

Furthermore, the convention is also required for consistency with the definition of the convolution of measures given below. However, with a right instead of a left Haar measure, the latter integral is preferred over the former.

On locally compact abelian groups, a version of the convolution theorem holds: the Fourier transform of a convolution is the pointwise product of the Fourier transforms. The circle group T with the Lebesgue measure is an immediate example. For a fixed g in L¹(T), we have the following familiar operator acting on the فضای هیلبرت L²(T):

$T{f}(x)={\frac {1}{2\pi }}\int _{\mathbb {T} }{f}(y)g(x-y)dy.$$T{f}(x)={\frac {1}{2\pi }}\int _{\mathbb {T} }{f}(y)g(x-y)dy.$

The operator T is compact. A direct calculation shows that its adjoint T* is convolution with

${\bar {g}}(-y).$${\bar {g}}(-y).$

By the commutativity property cited above, T is normal: T*T = TT*. Also, T commutes with the translation operators. Consider the family S of operators consisting of all such convolutions and the translation operators. Then S is a commuting family of normal operators. According to spectral theory, there exists an orthonormal basis {h_k} that simultaneously diagonalizes S. This characterizes convolutions on the circle. Specifically, we have

$h_{k}(x)=e^{ikx},\quad k\in \mathbb {Z} ,\;$$h_{k}(x)=e^{ikx},\quad k\in \mathbb {Z} ,\;$

which are precisely the characters of T. Each convolution is a compact multiplication operator in this basis. This can be viewed as a version of the convolution theorem discussed above.

A discrete example is a finite cyclic group of order n. Convolution operators are here represented by circulant matrices, and can be diagonalized by the discrete Fourier transform.

A similar result holds for compact groups (not necessarily abelian): the matrix coefficients of finite-dimensional unitary representations form an orthonormal basis in L² by the Peter-Weyl theorem, and an analog of the convolution theorem continues to hold, along with many other aspects of harmonic analysis that depend on the Fourier transform.

Convolution of measures

Let G be a topological group. If μ and ν are finite Borel measures on a group G, then their convolution μ∗ν is defined by

$(\mu *\nu )(E)=\int \!\!\!\int 1_{E}(xy)\,d\mu (x)\,d\nu (y)$$(\mu *\nu )(E)=\int \!\!\!\int 1_{E}(xy)\,d\mu (x)\,d\nu (y)$

for each measurable subset E of G. The convolution is also a finite measure, whose total variation satisfies

$\|\mu *\nu \|\leq \|\mu \|\|\nu \|.$$\|\mu *\nu \|\leq \|\mu \|\|\nu \|.$

In the case when G is locally compact with (left-)Haar measure λ, and μ and ν are absolutely continuous with respect to a λ, so that each has a density function, then the convolution μ∗ν is also absolutely continuous, and its density function is just the convolution of the two separate density functions.

If μ and ν are probability measures, then the convolution μ∗ν is the توزیع احتمال of the sum X + Y of two independent random variables X and Y whose respective distributions are μ and ν.

Bialgebras

Let (X, Δ, ∇, ε, η) be a bialgebra with comultiplication Δ, multiplication ∇, unit η, and counit ε. The convolution is a product defined on the endomorphism algebra End(X) as follows. Let φ, ψ ∈ End(X), that is, φ,ψ : X → X are functions that respect all algebraic structure of X, then the convolution φ∗ψ is defined as the composition

$X{\xrightarrow {\Delta }}X\otimes X{\xrightarrow {\phi \otimes \psi }}X\otimes X{\xrightarrow {\nabla }}X.\,$$X{\xrightarrow {\Delta }}X\otimes X{\xrightarrow {\phi \otimes \psi }}X\otimes X{\xrightarrow {\nabla }}X.\,$

The convolution appears notably in the definition of Hopf algebras (Kassel 1995, §III.3). A bialgebra is a Hopf algebra if and only if it has an antipode: an endomorphism S such that

$S*\operatorname {id} _{X}=\operatorname {id} _{X}*S=\eta \circ \varepsilon .$$S*\operatorname {id} _{X}=\operatorname {id} _{X}*S=\eta \circ \varepsilon .$

کاربردها

ردپای کانولوشن و عملیات مربوطه در بسیاری از کاربردهای مهندسی و ریاضی پیداست.

• در مهندسی برق، کانولوشن یک تابع (سیگنال ورودی) با یک تابع دوم (پاسخ ضربه) خروجی یک سیستم خطی تغییرناپذیر با زمان (LTI) را بر می‌گرداند. خروجی سیستم در هر لحظه برابر با اثر جمعی تمام مقادیر پیشین تابع ورودی است، که آخرین مقادیر معمولاً بیشتریت تأثیر را دارند (که با عامل شرب شوندگی بیان می‌شود). تابع پاسخ ضربه این عامل را برای ما مهیا می‌کند که تابعی از اثر مقدار ورودی در زمان‌های گذشته است.
  • در کاربردهای پردازش سیگنال رقمی و پردازش تصویر، تابع ورودی به طور کامل در دسترس است و لذا می‌توان هر قسمت از خروجی را بدست آورد. در این نوع، می‌توان از مزیت این که خروجی تنها به چند ورودی اخیر بستگی دارد بهره برد.
  • کانولوشن هر مولفه فرکانسی را به طور مستقل بدون وابستگی به دیگر فرکانس‌ها تقویت و با تضعیف می‌کند.
• در آمار، همانطور که اخیراً بیان شد، کانولوشن در واقع یک میانگین متحرک وزن دار است.
• در تئوری احتمال، توزیع احتمال مجموع دو متغیر تصادفی مستقل برابر است با کانولوشن توزیع‌های مستقل.
• در نورشناخت، بسیاری از انواع "بلور" را با کانولوسن بیان می‌کنند. یک سایه (مثلاً سایه روی یک میز، زمانی که دست خود را بین میز و نور قرار می‌دهید) را می‌توان کانولوشن یک شکل از منبع نور (که قالب سایه را تشکیل می‌دهد) و یک عنصر (که سایه آن تشکیل می‌شود) دانست. یک عکی خارج از فوکوس، کانولوشن یک عنصر شفاف با لبه‌های تیز با یک نمودار عنبیه مانند است. اصلاح مرسوم برای این حالت را بوکه است.
• به طور مشابه، در پردازش سیگنال رقمی، فیلتر کانولوشنی نقش مهمی را در الگوریتم‌های تشخیص لبه و کابردهای مشابه بازی می‌کند.
• در صداشناسی، یک پژواک کانولوشن صدای اصلی با تابعی است که عناصر بازپس دهنده صدا را توصیف می‌کند.
• در همهمه مصنوعی (پردازش سیگنال رقمی، صدای پس زمینه)، کانولوشن برای نگاشت پاسخ ضربه یک اتاق واقعی بر روی سیگنال صوتی رقمی استفاده می‌شود.
• In time-resolved fluorescence spectroscopy, the excitation signal can be treated as a chain of delta pulses, and the measured fluorescence is a sum of exponential decays from each delta pulse.
• در سیستم‌های برنامه‌ریز درمان رادیویی، قسمت اعظم محاسبات کدها از الگوریتم‌های برهم‌نهی کانولوشن استفاده می‌کنند.
• در فیزیک، هر جا که سیستم خطی با "اصل برهم‌نهی" همراه می‌شود، کانولوشن را نیز خواهیم دید.
• در سامانه اطلاعات مکانی، پاسخ تقریب هسته‌ایِ تابعِ شدتِ یک الگوی نقطه‌ای، کانولوشن ایزوتروپیک هسته گوسی یک انحراف استاندارد با وزن‌های نقطه‌ای (برای هر نقطه داده) است.(Diggle 1995) می‌توانید به documentation of the "Kernel Smoothed Intensity of Point Pattern" of the SDA4PP QGIS plugin مراجعه کنید.

See also

• مارتیس توپلیتس
• LTI system theory#Impulse response and convolution
• ماتریس توپلیتس (convolutions can be considered a Toeplitz matrix operation where each row is a shifted copy of the convolution kernel)
  • Circulant matrix
• Cross-correlation
• دکانولوشن
• ضرب دیریکله
• Titchmarsh convolution theorem
• Convolution power
• پردازش سیگنال پیوسته
• Convolution for optical broad-beam responses in scattering media
• List of convolutions of probability distributions
• Jan Mikusinski

References

• Bracewell, R. (1986), The Fourier Transform and Its Applications (2nd ed.), McGraw–Hill, ISBN 0071160434 .
• Hewitt, Edwin; Ross, Kenneth A. (1979), Abstract harmonic analysis. Vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 115 (2nd ed.), Berlin, New York: Springer Science+Business Media, ISBN 978-3-540-09434-0, MR551496 .
• Hewitt, Edwin; Ross, Kenneth A. (۱۹۷۰), Abstract harmonic analysis. Vol. II: Structure and analysis for compact groups. Analysis on locally compact Abelian groups, Die Grundlehren der mathematischen Wissenschaften, Band 152, Berlin, New York: Springer Science+Business Media, MR0262773 .
• Hörmander, L. (1983), The analysis of linear partial differential operators I, Grundl. Math. Wissenschaft. 256, Springer, ISBN 3-540-12104-8, MR0717035 .
• Kassel, Christian (1995), Quantum groups, Graduate Texts in Mathematics 155, Berlin, New York: Springer Science+Business Media, ISBN 978-0-387-94370-1, MR1321145 .
• Knuth, Donald (1997), Seminumerical Algorithms (3rd. ed.), Reading, Massachusetts: Addison–Wesley, ISBN 0-201-89684-2 .
• Rudin, Walter (1962), Fourier analysis on groups, Interscience Tracts in Pure and Applied Mathematics, No. 12, Interscience Publishers (a division of John Wiley and Sons), New York–London, ISBN 047152364X, MR0152834 .
• Sobolev, V.I. (2001), "Convolution of functions", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Springer, ISBN 978-1556080104 .
• Stein, Elias; Weiss, Guido (1971), Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, ISBN 0-691-08078-X .
• Strichartz, R. (1994), A Guide to Distribution Theory and Fourier Transforms, CRC Press, ISBN 0849382734 .
• Titchmarsh, E (1948), Introduction to the theory of Fourier integrals (2nd ed.), New York, N.Y.: Chelsea Pub. Co. (published 1986), ISBN 978-0828403245 .
• Uludag, A. M. (۱۹۹۸), "On possible deterioration of smoothness under the operation of convolution", J. Math. Anal. Appl. 227 no. 2, 335--358 
• Treves, François (1967), Topological Vector Spaces, Distributions and Kernels, Academic Press, ISBN 0486453529 .
• von zur Gathen, J.; Gerhard, J. (2003), Modern Computer Algebra, Cambridge University Press, ISBN 0-521-82646-2 .
• Diggle, P. J. (۱۹۹۵), "A kernel method for smoothing point process data", Journal of the Royal Statistical Society, Series C) 34 (1985) 138–147 

پیوند به بیرون

• Earliest Uses: The entry on Convolution has some historical information.
• http://www.nitte.ac.in/downloads/Conv-LTI.pdf
• Convolution, on The Data Analysis BriefBook
• http://www.jhu.edu/~signals/convolve/index.html Visual convolution Java Applet.
• http://www.jhu.edu/~signals/discreteconv2/index.html Visual convolution Java Applet for Discrete Time functions.
• Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution., by Alan Peters.
  • http://www.vuse.vanderbilt.edu/~rap2/EECE253/EECE253_01_Intro.pdf
• A collection of 2D convolution kernels
• Convolution Kernel Mask Operation Interactive tutorial
• Convolution at مث‌ورلد
• Freeverb3 Impulse Response Processor: Opensource zero latency impulse response processor with VST plugins