ітельность (тобто відмінні від нуля лише на кінцевому відрізку). Розглянемо, що відбувається з сигналом кінцевої тривалості, коли його згортають з кінцевим ядром згортки. Нехай сигнал x [n] відмінний від нуля тільки на відрізку від 0 до N - 1 включно («має довжину N»). Нехай ядро ??згортки h [n] відмінно від нуля на відрізку від-m 1 до m 2 включно, що складається з M точок (M=m 1 + m 2 +1). Тоді при підстановці цих сигналів у формулу згортки, ми отримаємо сигнал y [n], який відмінний від нуля на відрізку від-m 1 до N - 1 + m 2 включно. Таким чином, довжина результуючого сигналу дорівнює N + M - 1, тобто сумі довжин вихідного сигналу і ядра згортки мінус один.
Отже, операція згортки розширює сигнал на M - 1 точку, де M - довжина ядра згортки.
. Дискретне перетворення Фур'є
.1 Перетворення Фур'є
Багато сигнали зручно аналізувати, розкладаючи їх на синусоїди (гармоніки). Тому є кілька причин. Наприклад, подібним чином працює людське вухо. Воно розкладає звук на окремі коливання різних частот. Крім того, можна показати, що синусоїди є «власними функціями» лінійних систем (тому вони проходять через лінійні системи, не змінюючи форми, а можуть змінювати лише фазу і амплітуду). Ще одна причина в тому, що теорема Котельникова формулюється в термінах спектру сигналу.
Перетворення Фур'є (Fourier transform) - це розкладання функцій на синусоїди (далі косинусні функції ми теж називаємо синусоїдами, тому що вони відрізняються від «справжніх» синусоїд тільки фазою). Існує кілька видів перетворення Фур'є.
. Неперіодичний безперервний сигнал можна розкласти в інтеграл Фур'є.
. Періодичний безперервний сигнал можна розкласти в нескінченний ряд Фур'є.
. Неперіодичний дискретний сигнал можна розкласти в інтеграл Фур'є.
. Періодичний дискретний сигнал можна розкласти в кінцевий ряд Фур'є.
Комп'ютер здатний працювати тільки з обмеженим обсягом даних, отже, реально він здатний обчислювати тільки останній вид перетворення Фур'є. Розглянемо його докладніше.
2.2 Комплексне ДПФ
До цих пір ми розглядали ДПФ від дійсних сигналів. Узагальнимо тепер ДПФ на випадок комплексних сигналів. Нехай x [n], n=0, ..., N - 1 - вихідний комплексний сигнал, що складається з N комплексних чисел. Позначимо X [k], k=0, ... N - 1 - його комплексний спектр, також складається з N комплексних чисел. Тоді справедливі такі формули прямого і зворотного перетворень Фур'є:
,
.
Якщо за цими формулами розкласти в спектр дійсний сигнал, то перші N / 2 +1 комплексних коефіцієнтів спектра будуть збігатися зі спектром «звичайного» дійсного ДПФ, представленим в «комплексному» вигляді, а інші коефіцієнти будуть їх симетричним відображенням відносно половини частоти дискретизації. Для косинусних коефіцієнтів відображення парне, а для синусних - непарне.
.3 Двовимірне ДПФ
Для зображень, що представляють собою двовимірний сигнал, спектром є також двовимірний сигнал. Базисні функції перетворення Фур'є мають вигляд:
,
...