X
تبلیغات | یک فروم
کانولوشن

برق

کانولوشن

کانولوشن

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری, جستجو
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.

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

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

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

[ویرایش] تاریخچه

عمل

\int_0^t\varphi(s)\psi(t-s)ds,

به ازای

0\le t<\infty,

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

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

[ویرایش] تعریف

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

 

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

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

(f * g )(x) = \int_{\mathbf{R}^d} f(y)g(x-y)\,dy = \int_{\mathbf{R}^d} f(x-y)g(y)\,dy.
شرح تصویری کانولوشن
1.بیان هر تابع بر حسب متغیر زائد \tau.

2. معکوس کردن یکی از توابع: g(\tau)g(-\tau).

3. افزودن فاصله زمانی(t) که g(t-\tau) را در راستای محور \tau جابجا می کند.

4. با شروع t از ∞- تا ∞+. هر زمان که دو تابع با هم برخورد کردند، انتگرال حاصلضرب آن ها را پیدا کنید. به عبارت دیگر، میانگین وزنی تابع متحرک f(\tau) را زمانی که تابع وزنی آن g(-\tau) تعریف شده باشد را بدست آورید.

شکل موج بدست آمده (که در اینجا نمایش داده نشده است) کانولوشن تابع f و g است. اگر (f(t تابع ضربه باشد، نتیجه این عمل همان (g(t خواهد بود، که پاسخ ضربه نامیده می شود.

Convolution3.PNG

[ویرایش] کانولوشن دایره ای

نوشتار اصلی: wiki:Circular convolution


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

(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,\,

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

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

[ویرایش] کانولوشن گسسته

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

(f * g)[n]\ \stackrel{\mathrm{def}}{=}\ \sum_{m=-\infty}^{\infty} f[m]\, g[n - m]
= \sum_{m=-\infty}^{\infty} f[n-m]\, g[m]. (جابجا پذیری)

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

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

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

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

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

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

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

الگو:Repeat/0

(f * g_N)[n] = \sum_{m=0}^{N-1} f[m]\ g_N[n-m]\,

 

 

 

 

 

(الگو:EquationRef)

الگو:Repeat/0

= \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]\,


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

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

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


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

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

[ویرایش] دامنه تعریف

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

(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 هر دو توابع انتگرال پذیر لبسگو ( در L1(Rd)) باشند؛ در این حالت ƒ∗g نیز انتگرال پذیر است (Stein & Weiss 1971, Theorem 1.3). این بیان، یک نتیجه گیری از قضیه تونلی است. به همین صورت، اگر ƒ ∈ L1(Rd) و g ∈ Lp(Rd) که 1 ≤ p ≤ ∞، آنگاه ƒg ∈ Lp(Rd) و

\|{f}*g\|_p\le \|f\|_1\|g\|_p. \,

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

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

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

آنگاه

\|f*g\|_r\le \|f\|_p\|g\|_q,\quad f\in L^p,\ g\in L^q,

در نتیجه، کانولوشن نگاشت دوطرفه پیوسته از Lp×Lq به Lr است.

[ویرایش] توابع با نزل سریع

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

[ویرایش] توزیع ها

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


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

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

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

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).

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

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

\|\mu*\nu\|\le \|\mu\|\|\nu\|

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

[ویرایش] Properties

[ویرایش] خواص جبری

هم‌چنین ببینید: Convolution algebra

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

جابجایی
f * g = g * f  \,
انجمنی
f  * (g  * h) = (f  * g)  * h \,
توزیع پذیری
f  * (g + h) = (f  * g) + (f  * h) \,

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

a (f  * g) = (a f)  * g = f  * (a g) \,

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

خنثی در ضرب

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

+ نوشته شده در ۳۱/۲/۱۳۹۱ساعت ۱۰:۵۵ توسط توحيد جعفري دسته : | نظر(0)