7.5: Дискретна кругова згортка часу та DTFS
- Page ID
- 34201
Вступ
Цей модуль пов'язує кругову згортку періодичних сигналів в одній області до множення в іншій області.
Ви повинні бути знайомі з дискретним часом згортки (Розділ 4.3), який говорить нам\(x[n]\), що за умови двох дискретних сигналів часу\(h[n]\), вхід системи, і, відповідь системи, ми визначаємо вихід системи як
\ [\ begin {вирівнювання}
y [n] &= x [n] * h [n]\ nonumber\\
&=\ sum_ {k=-\ infty} ^ {\ infty} x [k] h [n-k]
\ end {вирівнювання}\ nonumber\]
Коли нам дано два DFT (послідовності скінченної довжини, як правило, довжини\(N\)), ми не можемо просто помножити їх разом, як ми робимо у наведеній вище формулі згортки, яку часто називають лінійною згорткою. Оскільки DFT є періодичними, вони мають ненульові значення для\(n≥N\) і, таким чином, множення цих двох DFT буде ненульовим для\(n≥N\). Нам потрібно визначити новий тип операції згортки, який призведе до того, що наш згорнутий сигнал буде нульовим поза діапазоном\(n={0,1,…,N−1}\). Ця ідея призвела до розвитку кругової згортки, званої також циклічної або періодичної згорткою.
Сигнальна кругова згортка
З огляду на сигнал\(f[n]\) з коефіцієнтами Фур'є\(c_k\) і сигнал\(g[n]\) з коефіцієнтами Фур'є\(d_k\), можна визначити новий сигнал\(v[n]\), де\(v[n]=f[n] \circledast g[n]\). Ми виявляємо, що представлення серії Фур'є\(v[n]\)\(a_k\), є таким, що\(a_k=c_kd_k\). \(f[n] \circledast g[n]\)- кругова згортка (Розділ 7.5) двох періодичних сигналів і еквівалентна згортці за один інтервал, т\(\displaystyle{f[n] \circledast g[n] = \sum_{n=0}^{N} \sum_{\eta=0}^{N} f[\eta] g[n-\eta]}\).
Примітка
Кругова згортка у часовій області еквівалентна множенню коефіцієнтів Фур'є.
Це доведено наступним чином:
\ [\ почати {вирівняти}
a_ {k} &=\ розрив {1} {N}\ сума_ {n=0} ^ {N} v [n] e^ {-\ лівий (j\ омега_ {0} k n\ праворуч)}\ номер\\
&=\ frac {1} {N^ {2}}\ sum_ {n = 0} ^ {N} сума_ {n = 0} ^ {\ ета} f [\ ета] г [n-\ ета] e^ {-\ ліворуч (j\ омега_ {0} k n\ праворуч)}\ nonumber\\
&=\ frac {1} {N}\ sum_ {\ eta=0} ^ {N} f [\ та]\ ліворуч (\ frac {1} {N}\ sum_ {n=0} ^ {N} g [n-\ eta] e^ {-\ вліво (j\ omega_ {0} k n\ праворуч)}\ nonumber\\
&=\ ліво (\ frac {1} {N}\ sum_ {\ eta=0} ^ {N} та]\ ліворуч (\ frac {1} {N}\ sum_ {\ nu=-\ ета} ^ {N-\ eta} г [\ nu] e^ {-\ ліво (j\ omega_ {0} (\ nu+\ eta)\ праворуч)\ право)\ квад\ nu = n -\ та\ нуномер\\
&=\ розрив {1} {N}\ sum_ {\ eta=0} ^ {N} f [\ eta]\ лівий (\ frac {1} {N}\ sum_ {\ nu=-\ ета} ^ {N-\ eta} g [\ nu] e^ {-\ лівий (j\ omega_ {0} k\ nu\ право)}\ праворуч) e^ {-\ ліво (j\ omega_ {0} k\ nu\ право)}\ праворуч) e^ {- -\ ліворуч (j\ омега_ {0} k\ ета\ вправо)}\ nonnumber\\
&=\ frac {1} {N}\ sum_ {\ eta=0} ^ {N} f [\ eta] d_ {k} e^ {-\\ left (j\ omega_ {0} k\ eta\ праворуч)}\ номер\\
&=d_ {k}\ лівий (\ frac {1} {N}\ sum_ {\ eta=0} ^ {N} f [\ eta] e^ {-\ left (j\ omega_ {0} k\ eta\ праворуч)}\ nonumber\\
&=c_ {k} d_ {k}
\ кінець {вирівнювання}\ nonu бурштиновий\]
Формула кругової згортки
Що відбувається, коли ми множимо два DFT разом, де\(Y[k]\) DFT\(y[n]\)?
\[ Y[k] = F[k]H[k] \nonumber \]
коли\(0≤k≤N−1\)
Використання формули синтезу DFT для\(y[n]\)
\[y[n]=\frac{1}{N} \sum_{k=0}^{N-1} F[k] H[k] e^{j \frac{2 \pi}{N} k n} \nonumber \]
А потім застосовуючи формулу аналізу\(F[k]=\sum_{m=0}^{N-1} f[m] e^{(-j) \frac{2 \pi}{N} k n}\)
\ [\ почати {вирівняти}
y [n] &=\ розрив {1} {N}\ сума_ {k=0} ^ {N-1}\ сума {м = 0} ^ {N-1} f [м] e^ {(-j)\ frac {2\ пі} {N} k n} H [k] e^ {j\ frac {2\ pi} {N} k}\ номер\\
&=\ сума_ {м = 0} ^ {N-1} f [m]\ лівий (\ frac {1} {N}\ сума {k=0} ^ {N-1} H [k] e^ {j\ frac {2\ pi} {N} k (n-м)}\ праворуч)
\ кінець {вирівнювання}\ номер\]
де ми можемо зменшити друге підсумовування, знайдене у вищезгаданому рівнянні\(h\left[((n-m))_{N}\right]=\frac{1}{N} \sum_{k=0}^{N-1} H[k] e^{j \frac{2 \pi}{N} k(n-m)} y[n]=\sum_{m=0}^{N-1} f[m] h\left[((n-m))_{N}\right]\), в яке дорівнює круговій згортці! Коли ми маємо\(0≤n≤N−1\) в вищесказаному, то отримуємо:
\[y[n] \equiv f[n] \circledast h[n] \nonumber \]
Примітка
Позначення\(\circledast\) являє собою циклічну згортку «мод N».
Альтернативна формула згортки
Альтернативний алгоритм кругової згортки
- Крок 1: Обчисліть DFT\(f[n]\), який дає,\(F[k]\) і розрахуйте DFT\(h[n]\), який дає\(H[k]\).
- Крок 2: Точкове множення\(Y[k]=F[k]H[k]\)
- Крок 3: Зворотний DFT\(Y[k]\), який дає\(y[n]\)
Здається, це обхідний спосіб робити речі, але виявляється, що існують надзвичайно швидкі способи обчислити DFT послідовності.
Для кругового згортання 2-х\(N\) точкових послідовностей:\(y[n]=\sum_{m=0}^{N-1} f[m] h\left[((n-m))_{N}\right]\). Для кожного\(n\):\(N\) кратні,\(N−1\) доповнення.
\(N\)бали мають на увазі\(N^2\) множення,\(N(N−1)\) додавання мають на увазі\(O(N^2)\) складність.
Кроки для кругової згортки
Ми можемо уявити періодичні (Розділ 6.1) послідовності як дискретні точки на колі як область
Малюнок\(\PageIndex{1}\)
Зсув на\(m\)\(f(n+m)\), відповідає обертанню\(m\) насічок циліндра ACW (проти годинникової стрілки). Для\(m=−2\), ми отримуємо зсув, рівний тому, що на наступній ілюстрації:
Малюнок\(\PageIndex{3}\)
Для циклічного зсуву виконуємо наступні кроки:
1) Написати\(f(n)\) на циліндрі, ACW
2) Для циклічного зсуву по\(m\), спина циліндра m плями ACW
\[f[n] \rightarrow f\left[((n+m))_{N}\right] \nonumber \]
Примітки щодо кругового зсуву
\(f[((n+N))_N]=f[n]\)\(N\)Плями для спінінгу - це те ж саме, що крутиться по всьому шляху, або зовсім не крутиться.
\(f[((n+N))_N]=f[((n−(N−m)))_N]\)Зсув ACW мм еквівалентний зміщенню CW\(N−m\)
Малюнок\(\PageIndex{6}\)
\(f[((−n))_N]\)Вищевказане вираз, просто записує значення за\(f[n]\) годинниковою стрілкою.
(а)\(f[n]\)
(б)\(f[((−n))_N]\)
Приклад\(\PageIndex{1}\)
Згорнути (n = 4)
(а)
(б)- \(h[((−(m()()_N]\)
Малюнок\(\PageIndex{9}\)
Помножте\(f[m]\) та підсумуйте до прибутку:\(y[0]=3\)
- \(h[((1(−(m()()_N]\)
Малюнок\(\PageIndex{10}\)
Помножте\(f[m]\) та підсумуйте до прибутку:\(y[1]=5\)
- \(h[((2(−(m()()_N]\)
Малюнок\(\PageIndex{11}\)
Помножте\(f[m]\) та підсумуйте до прибутку:\(y[2]=3\)
- \(h[((3(−(m()()_N]\)
Малюнок\(\PageIndex{12}\)
Помножте\(f[m]\) та підсумуйте до прибутку:\(y[3]=1\)
Вправа
Погляньте на квадратний пульс з періодом\(T\).
Для цього сигналу\ (c_ {k} =\ left\ {\ begin {масив} {l}
\ frac {1} {N}\ текст {якщо} k=0\
\ frac {1} {2}\ frac {\ sin\ left (\ frac {\ pi} {2} k\ право)} {\ frac {\ pi} {2} k\ text {інакше}
end {масив}\ право.\)
Погляньте на трикутник імпульсний поїзд з періодом\(T\).
Цей сигнал створюється шляхом кругового згортання квадратного імпульсу з собою. Коефіцієнти Фур'є для цього сигналу\(a_{k}=c_{k}^{2}=\frac{1}{4} \frac{\sin ^{2}}{\left(\frac{x}{2} k\right)}\)
Вправа\(\PageIndex{1}\)
Знайти коефіцієнти Фур'є сигналу, який створюється при згортанні квадратного імпульсу і імпульсу трикутника.
- Відповідь
-
\ (a_ {k} =\ лівий\ {\ begin {масив} {ll}
\ текст {undefined} & k=0\\ frac {1} {8}
\ розрив {\ sin ^ {3}\ лівий [\ frac {\ pi} {2} k\ праворуч]} {\ лівий [\ frac {\ pi} {2} k\ правий]} {\ лівий [\ frac {\ pi} {2} k\ праворуч] текст {інакше}
\ end {масив}\ право.\)
Кругові зрушення та DFT
Теорема\(\PageIndex{1}\): Circular Shifts and DFT
Якщо\(f[n] \stackrel{\mathrm{DFT}}{\longleftrightarrow} F[k]\) тоді\(f\left[((n-m))_{N}\right] \stackrel{\mathrm{DFT}}{\longleftrightarrow} e^{-\left(j \frac{2 \pi}{N} k m\right)} F[k]\) (тобто круговий зсув у часовій області = фазовий зсув у DFT)
Доказ
\[ f[n]=\frac{1}{N} \sum_{k=0}^{N-1} F[k] e^{j \frac{2 \pi}{N} k n} \nonumber \]
так зсув фази DFT
\ begin {вирівнювання}
f [n] &=\ розрив {1} {N}\ sum_ {k=0} ^ {N-1} F [k] e^ {-\ лівий (j\ frac {2\ пі} {N} k n\ праворуч)} e^ {j\ frac {2\ пі} {N} k n}\ nonumber\\
&=\ frac {1} {N}\ сума_ {k=0} ^ {N-1} F [k] e^ {j\ frac {2\ pi} {N} k (n-м)}\ неномер\\
&= f\ лівий [((n-m)) _ {N}\ праворуч]
\ кінець {вирівняти}
Демонстрація кругової згортки
Висновок
Кругова згортка у часовій області еквівалентна множенню коефіцієнтів Фур'є у частотній області.