English · متن اصلی | ترجمهٔ ماشینی فارسی · متن انگلیسی و فرمول‌ها حفظ شده‌اند. برای رفع ابهام، متن اصلی را هم ببینید.
قسمت 7 · فصل 26

تبدیل فوریهٔ گسسته و FFT

هر دگرگونی تاکنون موضوعی برای نوشتن و استدلال بوده است. تبدیل فوریهٔ گسسته، تبدیلی است که یک ماشین واقعاً می تواند آن را ارزیابی کند، و کل این فصل از پرسیدن اینکه چه چیزی را باید رها کرد - یک رکورد محدود و یک مجموعه محدود از فرکانس ها - و این فداکاری چه هزینه ای دارد، دنبال می شود.

سیگنال‌ها و سیستم‌ها پروفسور Mithun Mondal زمان خواندن ≈ 65 دقیقه
چیزی که یاد خواهید گرفت
  • چرا DTFT فصل 16 قابل محاسبه نیست و دو محدودیت - طول محدود و بسامدهای بسیار محدود - که آن را به DFT تبدیل می کند.
  • جفت DFT، فاکتور پیچیدگی \(W_N = e^{-j2\pi/N}\)، و اثبات فرمول وارونگی که بر چیزی جز یک سری هندسی استوار نیست.
  • هم‌پوشانی طیفی در حوزه زمانی: نمونه‌برداری از طیف، سیگنال زمان را مجبور می کند تا متناوب شود، که منشأ هر عجیب و غریب "دایره ای" است که در ادامه می آید.
  • جابجایی دایره‌ای و کانولوشن دایره‌ای، و شرایط دقیق لایه‌بندی صفر \(N \ge L+M-1\) که کانولوشن دایره‌ای را ایجاد می‌کند کانولوشن خطی فصل 7 را بازتولید می‌کند.
  • Overlap-add و overlap-save – چگونه فیلتری روی سیگنالی اجرا می شود که هرگز با استفاده از تبدیلی که بر بلوک های محدود پافشاری می کند، پایان نمی یابد.
  • FFT در زمان قطع ریشه-2 از ابتدا مشتق شده است: تقسیم برابری، پروانه، ترتیب ورودی معکوس بیت، و افت از \(N^2\) به \(\tfrac{N}{2}\log_2 N\) ضرب.
  • آنچه DFT یک سیگنال اندازه‌گیری شده واقعاً به شما می‌گوید: نشتی، پنجره‌ها، وضوح، و چرا لایه‌بندی صفر امتیاز بیشتری می‌دهد اما جزئیات بیشتری را ارائه نمی‌دهد.
بخش 26-1

طیفی که یک ماشین می تواند نگه دارد

فصل 16 تبدیل فوریهٔ گسسته زمان را تعریف کرد و فصل های 23 تا 25 تبدیل z را در بالای آن ساختند. هر دو پاسخ کاملی برای این سوال هستند که "این دنباله از چه فرکانس هایی ساخته شده است". هیچکدام توسط رایانه قابل ارزیابی نیستند، و دلیل آن ارزش بیان دقیق را دارد، زیرا این راه حل به جای اینکه برای راحتی انتخاب شود، به دلیل دشواری به ما تحمیل شده است.

DTFT فصل 16 - صحیح و غیر قابل محاسبه
\[ X(e^{j\Omega}) \;=\; \sum_{n=-\infty}^{\infty} x[n]\,e^{-j\Omega n} \]

دو چیز مانع است. این مجموع بیش از بی‌نهایت نمونه‌ها را شامل می‌شود و هیچ ماشینی رکورد بی‌نهایتی ندارد. و \(\Omega\) یک متغیر پیوسته است، بنابراین \(X(e^{j\Omega})\) تابعی است در یک بازه — اعداد غیرقابل شمارش، و هیچ ماشینی نیز برای آن حافظه ندارد. بنابراین، یک تبدیل قابل محاسبه باید دو بار محدود باشد: نمونه‌های بسیار محدودی که وارد می‌شوند، تعداد محدودی اعداد بیرون می‌آیند.

هر دو محدودیت در عمل طبیعی است. هر اندازه گیری واقعی یک رکورد محدود است: شما ابزار را روشن می کنید، نمونه های \(N\) را جمع آوری می کنید، آن را خاموش می کنید. و هر نمایش واقعی یک طیف یک لیست محدود است: یک تحلیلگر چند صد یا چند هزار نقطه را ترسیم می کند، نه یک پیوستار. بنابراین سؤال این نیست که آیا باید این دو محدودیت ایجاد کرد یا نه، بلکه هزینه آنها چیست، و پاسخ صادقانه - که در بخش 26-4 کار شده و در بخش 26-9 بازگشته است - این است که هزینه آنها بیشتر از چیزی است که یک مبتدی انتظار دارد.

تبدیلی که حاصل می شود تبدیل فوریهٔ گسسته است. این تبدیل پنجمی نیست که در کنار سری فوریه، تبدیل فوریه، DTFT و تبدیل z به خاطر سپرده شود. این DTFT یک دنباله با طول محدود است که در فرکانس‌های محدود خوانده می‌شود و هر یک از ویژگی‌های آن را می‌توان به همان جمله ردیابی کرد.

هشدار نامگذاری DFT یک تبدیل است. FFT یک الگوریتم برای محاسبه تبدیل است. آنها جایگزین نیستند و پاسخ های متفاوتی نمی دهند - یک FFT دقیقاً DFT را به درون گرد کردن برمی گرداند. صحبت از "دریافت FFT از یک سیگنال" کوتاه نویسی جهانی است، اما زمانی که یک نتیجه استخراج می شود، همیشه منظور DFT است.
بخش 26-2

نمونه‌برداری از DTFT: DFT

دنباله ای را در خارج از \(0 \le n \le N-1\) در نظر بگیرید که صفر است. سپس مجموع DTFT آن فقط دارای عبارات غیر صفر \(N\) است و اولین مشکل خود به خود از بین می رود.

DTFT یک دنباله با طول \(N\)
\[ X(e^{j\Omega}) \;=\; \sum_{n=0}^{N-1} x[n]\,e^{-j\Omega n} \]

این یک جمع محدود است، اما همچنان تابعی از یک \(\Omega\) پیوسته است. پس نمونه‌برداری کنید DTFT در \(\Omega\) دوره ای با دوره \(2\pi\) است، بنابراین یک دوره همه چیز را حمل می کند. آن دوره را به قسمت های مساوی \(N\) تقسیم کنید و در آنجا ارزیابی کنید.

چرا دقیقا امتیاز \(N\)؟ از آنجایی که توالی با اعداد \(N\) مشخص می شود، بنابراین اعداد \(N\) طیف دقیقاً برای تعیین مجدد آن کافی است. تعداد کمتری اطلاعات را به طور جبران ناپذیر از دست می دهند. بیشتر زائد خواهد بود، زیرا مقادیر اضافی را می توان از اولین \(N\) بازسازی کرد. شمارش مصالحه نیست - این حسابداری دقیق است که تبدیل را وارونه می کند.

🔑
جفت تبدیل فوریهٔ گسسته
\[ X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-j\frac{2\pi}{N}kn}, \qquad x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{+j\frac{2\pi}{N}kn} \]

هر دو شاخص بیش از \(0,1,\dots,N-1\) اجرا می شوند. تبدیل رو به جلو حامل علامت منفی و بدون ضریب مقیاس است. معکوس حامل علامت مثبت و \(1/N\) است. ضریب \(k\)-امین DTFT است که در \(\Omega_k = 2\pi k/N\) ارزیابی شده است، بنابراین \(X[k] = X(e^{j\Omega})\big|_{\Omega = 2\pi k/N}\).

نمایی آنقدر ظاهر می شود که نامی به آن داده می شود. عامل پیچیدگی است

عامل پیچیدگی و سه هویت مفید آن
\[ W_N \;=\; e^{-j\frac{2\pi}{N}} \qquad\Longrightarrow\qquad W_N^{N} = 1, \qquad W_N^{k+N} = W_N^{k}, \qquad W_N^{k+N/2} = -\,W_N^{k} \]

با آن جفت \(X[k] = \sum_n x[n]W_N^{kn}\) و \(x[n] = \tfrac1N\sum_k X[k]W_N^{-kn}\) را می خواند. از نظر هندسی، \(W_N^{kn}\) در اطراف دایره واحد در مراحل \(2\pi/N\) راه می رود. این سه هویت می گویند که بعد از گام های \(N\) شما در خانه هستید، پیاده روی تکرار می شود و نیم دور یک تغییر علامت است. هویت سوم کوچک، واضح است و دلیل کامل وجود FFT بخش 26-7 است.

دو ضریب را می توان بدون هیچ حسابی نوشت. تنظیم \(k=0\) نمایی را از بین می‌برد، بنابراین \(X[0] = \sum_n x[n]\) مجموع نمونه‌ها است - مقدار DC و یک بررسی رایگان روی هر DFT که محاسبه می‌کنید. اگر \(N\) زوج باشد، تنظیم \(k = N/2\) به \(e^{-j\pi n} = (-1)^n\) می‌دهد، بنابراین \(X[N/2] = \sum_n (-1)^n x[n]\) مجموع متناوب است، ضریب \(\Omega = \pi\)، بالاترین فرکانسی که یک سیگنال نمونه‌برداری می‌تواند حمل کند.

Ω |X(e^jΩ)| 0 1 2 3 4 5 6 7 2π bin index k — spacing 2π/N, here N = 8
DFT همان DTFT است که در نقاط \(N\) با فاصله یکسان خوانده می شود - منحنی خاکستری چیزی است که وجود دارد، ساقه های طلایی همان چیزی است که به دست می آورید.

این رقم ارزش حمل و نقل را دارد. منحنی خاکستری طیف واقعی رکورد محدود است. ساقه های طلا اعداد \(N\) هستند که DFT برمی گرداند. هیچ چیز در ساقه‌های طلا نمی‌گوید که منحنی بین آنها چگونه رفتار می‌کند، و بسیاری از اشتباهات عملی ناشی از فراموشی این است که DFT یک طیف نمونه‌برداری شده را گزارش می‌کند، نه یک طیف پیوسته.

بخش 26-3

چرا معکوس کار می کند

فرمول وارونگی در بالا بیان شد. سزاوار برهان است و دلیل کوتاه است. همه چیز بر یک جمله متعامد در مورد عوامل پیچیدگی استوار است که خود چیزی بیش از مجموع یک سری هندسی نیست.

🔑
متعامد بودن نمایی های DFT
\[ \frac{1}{N}\sum_{k=0}^{N-1} e^{\,j\frac{2\pi}{N}k(n-m)} \;=\; \begin{cases} 1, & n \equiv m \pmod N \\[2pt] 0, & \text{otherwise} \end{cases} \]

نمایی های گسسته \(N\) به طور متقابل در یک دوره متعامد هستند، که دقیقاً ویژگی مورد نیاز سری فوریه در فصل 10 و تبدیل فوریه در فصل 13 است. DFT همان ایده با مبنای محدود است.

برای دیدن آن، \(r = e^{j2\pi(n-m)/N}\) را قرار دهید و جمع را به صورت \(\sum_{k=0}^{N-1} r^{k}\) بخوانید. اگر \(n-m\) مضربی از \(N\) باشد، آنگاه \(r = 1\) و هر جمله 1 است، بنابراین مجموع آن \(N\) و مقدار نرمال شده 1 است. در غیر این صورت \(r \neq 1\): سری های محدود است.

مجموع هندسی که همه کارها را انجام می دهد
\[ \sum_{k=0}^{N-1} r^{k} \;=\; \frac{1-r^{N}}{1-r}, \qquad r^{N} = e^{\,j2\pi(n-m)} = 1 \quad\Longrightarrow\quad \sum_{k=0}^{N-1} r^{k} = 0 \]

صورت ناپدید می شود زیرا \(n-m\) یک عدد صحیح است و مخرج ناپدید نمی شود زیرا \(r \ne 1\). اکنون تبدیل رو به جلو را با معکوس ادعا شده جایگزین کنید و دو مجموع متناهی را مبادله کنید که همیشه قانونی است:

وارونگی، در سه خط
\[ \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{\,j\frac{2\pi}{N}kn} = \frac{1}{N}\sum_{k=0}^{N-1}\sum_{m=0}^{N-1} x[m]\,e^{-j\frac{2\pi}{N}km}\,e^{\,j\frac{2\pi}{N}kn} = \sum_{m=0}^{N-1} x[m]\left[\frac{1}{N}\sum_{k=0}^{N-1} e^{\,j\frac{2\pi}{N}k(n-m)}\right] = x[n] \]

براکت مجموع متعامد است، که برای \(m = n\) 1 و برای هر \(m\) دیگر در محدوده 0 است، بنابراین مجموع بیرونی به عبارت واحد \(x[n]\) جمع می شود. این تمام اثبات است، و توضیح می‌دهد که \(1/N\) از کجا آمده است: نمایی‌ها متعامد هستند اما نرمال‌سازی نشده‌اند و طول هر کدام \(N\) مربع است.

جایی که \(1/N\) زندگی می کند یک قرارداد است. برخی از متون و برخی از کتابخانه های نرم افزاری \(1/\sqrt{N}\) را روی هر دو تبدیل قرار می دهند که باعث می شود DFT یک ماتریس واحد و رابطه پارسوال کاملا متقارن باشد. برخی دیگر \(1/N\) را روی تبدیل رو به جلو قرار می دهند. هیچ چیز فیزیکی تغییر نمی کند، اما ضریب \(N\) تنها رایج ترین اشکال در کد DFT است، بنابراین قبل از اعتماد به دامنه، بررسی کنید که کتابخانه شما از کدام قرارداد استفاده می کند.
بخش 26-4

قیمت: هم‌پوشانی طیفی دامنه زمانی

تا اینجا اشتقاق فرض می‌کرد که توالی خارج از \(0 \le n \le N-1\) واقعاً صفر است. فرض کنید اینطور نیست - فرض کنید \(x[n]\) برای همیشه روشن است و ما DTFT آن را در نقاط \(N\) به هر حال نمونه‌برداری می کنیم. DFT معکوس به چه ترتیبی دست می دهد؟

محاسبه مانند بخش قبل است، اما اکنون مجموع داخلی تمام شده است\(m\)بر روی همه اعداد صحیح اجرا می شود، و رابطه متعامد می گوید هر زمان که براکت 1 است\(m\)و\(n\)با مضرب متفاوت است\(N\)- نه تنها زمانی که برابر باشند.

آنچه DFT معکوس در واقع برمی گرداند
\[ x_p[n] \;=\; \frac{1}{N}\sum_{k=0}^{N-1} X\!\left(e^{\,j\frac{2\pi k}{N}}\right) e^{\,j\frac{2\pi}{N}kn} \;=\; \sum_{m=-\infty}^{\infty} x[m]\!\!\sum_{r=-\infty}^{\infty}\!\!\delta[n-m+rN] \;=\; \sum_{r=-\infty}^{\infty} x[n+rN] \]
🔑
نمونه‌برداری در فراوانی باعث تناوب در زمان می شود
\[ X[k] = X\!\left(e^{\,j2\pi k/N}\right) \quad\Longleftrightarrow\quad x_p[n] = \sum_{r=-\infty}^{\infty} x[n+rN] \]

DFT معکوس نه \(x[n]\) بلکه پسوند دوره‌ای آن را با دوره \(N\) برمی‌گرداند که با جابجایی سیگنال توسط هر مضربی از \(N\) و اضافه کردن آن ایجاد می‌شود. اگر \(x[n]\) کوتاه‌تر از \(N\) باشد، کپی‌های جابجا شده با هم همپوشانی ندارند و چیزی از بین نمی‌رود. اگر طولانی‌تر باشد، دم‌ها به سمت بالای سر جمع می‌شوند و آسیب غیرقابل برگشت است.

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

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

تناوب ضمنی تفسیر نیست، حسابی است. از یک DFT برای \(X[k]\) با \(k = N+3\) بخواهید و \(e^{-j2\pi(N+3)n/N} = e^{-j2\pi 3n/N}\) نمایی \(X[3]\) را به شما می دهد. یک DFT معکوس برای \(x[N+3]\) بخواهید و \(x[3]\) دریافت می کنید. هر دو دنباله با دوره \(N\) دوره ای هستند، خواه این همان چیزی باشد که شما می خواستید یا نه. هر ویژگی "دایره ای" در بخش بعدی نتیجه این است و نه چیز دیگری.
بخش 26-5

شیفت دایره ای و کانولوشن دایره ای

\((n)_N\) را برای مدول کاهش یافته \(n\) \(N\) بنویسید. یک جابجایی دایره ای توسط \(m\) دنباله \(x[(n-m)_N]\) است: نمونه هایی که از انتهای سمت راست رکورد خارج شده اند دوباره در سمت چپ ظاهر می شوند. تصویر کردن نمونه‌های \(N\) در اطراف یک حلقه، همانطور که در شکل نشان داده شده است، این امر را آشکار می‌کند - یک جابجایی دایره‌ای چرخش حلقه است، و هیچ‌وقت هیچ چیز گم یا ایجاد نمی‌شود.

x[0]x[1] x[2]x[3] x[4]x[5] x[6]x[7] original rotate 2 x[6]x[7] x[0]x[1] x[2]x[3] x[4]x[5] x[(n−2)₈] nothing enters, nothing leaves — the record is a closed ring
یک جابجایی دایره ای یک چرخش است - تنها نوع تغییری که یک DFT می تواند نشان دهد

تبدیل یک جابجایی دایره‌ای آسان است، و اثبات نشان می‌دهد که محل قرارگیری از کجا حفظ می‌شود. قرار دادن \(p = (n-m)_N\); همانطور که \(n\) یک بار از طریق \(0,\dots,N-1\) اجرا می شود، \(p\) نیز انجام می شود. سپس \(W_N^{kn} = W_N^{k(p+m)} = W_N^{km}W_N^{kp}\)، جایی که مرحله مشروع است زیرا \(W_N^{kN}=1\) مدول را جذب می کند. از این رو

تغییر زمان دایره ای و دوگانه آن
\[ x[(n-m)_N] \;\stackrel{\text{DFT}}{\longleftrightarrow}\; W_N^{km}X[k] = e^{-j\frac{2\pi}{N}km}X[k], \qquad W_N^{-\ell n}x[n] \;\stackrel{\text{DFT}}{\longleftrightarrow}\; X[(k-\ell)_N] \]

کانولوشن دایره ای از همین الگو پیروی می کند. برای دو دنباله با طول \(N\) تعریف کنید،

کانولوشن دایره ای \(N\) نقطه ای
\[ \big(x_1 \circledast x_2\big)[n] \;=\; \sum_{m=0}^{N-1} x_1[m]\,x_2\big[(n-m)_N\big], \qquad n = 0,1,\dots,N-1 \]

با جایگزینی به DFT و مبادله مجموع قضیه در دو مرحله به دست می آید. با \(p = (n-m)_N\) دوباره،

قضیه کانولوشن دایره ای، مشتق شده است
\[ \sum_{n=0}^{N-1}\sum_{m=0}^{N-1} x_1[m]\,x_2[(n-m)_N]\,W_N^{kn} = \sum_{m=0}^{N-1} x_1[m]W_N^{km}\sum_{p=0}^{N-1} x_2[p]W_N^{kp} = X_1[k]\,X_2[k] \]
🔑
ضرب DFT ها دایره ای است، نه خطی، کانولوشن
\[ x_1[n] \circledast x_2[n] \;\stackrel{\text{DFT}}{\longleftrightarrow}\; X_1[k]\,X_2[k] \]

فصل 7 نشان داد که یک سیستم LTI کانولوشن خطی را انجام می دهد. ضرب دو DFT به جای آن کانولوشن دایره ای را انجام می دهد. بخش 26-6 دقیقاً نشان می‌دهد که چه مقدار لایه صفر تفاوت را حذف می‌کند - و تا زمانی که این لایه‌بندی اعمال نشود، این دو یکسان نیستند و خطا نیز کم نیست.

خواص باقی مانده در زیر جمع آوری شده است. خطی بودن نیازی به اظهار نظر ندارد. ویژگی تقارن نسخه DFT تقارن مزدوج فصل 14 است: برای یک سیگنال حقیقی، نیمه دوم طیف تصویر آینه اول است، بنابراین از اعداد مختلط \(N\) فقط حدود \(N/2\) مستقل هستند - به همین دلیل است که یک ورودی واقعی با هزینه FFT تقریباً نصف است.

اموالدنبالهDFT
خطی بودن\(a\,x_1[n] + b\,x_2[n]\)\(a\,X_1[k] + b\,X_2[k]\)
تغییر زمان دایره ای\(x[(n-m)_N]\)\(W_N^{km}X[k]\)
تغییر فرکانس دایره ای\(W_N^{-\ell n}x[n]\)\(X[(k-\ell)_N]\)
کانولوشن دایره ای\(x_1[n]\circledast x_2[n]\)\(X_1[k]\,X_2[k]\)
ضرب\(x_1[n]\,x_2[n]\)\(\tfrac{1}{N}\,X_1[k]\circledast X_2[k]\)
زمان معکوس دایره ای\(x[(-n)_N]\)\(X[(-k)_N]\)
تقارن مزدوج (\(x\) واقعی)\(x[n]\) واقعی\(X[(N-k)_N] = X^{*}[k]\)
پارسهوال\(\sum_{n=0}^{N-1}|x[n]|^2\)\(\tfrac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2\)
بخش 26-6

کانولوشن خطی توسط DFT

فیلتر کردن کانولوشن است و کانولوشن گران است: یک سیگنال نقطه \(L\) از طریق فیلتر \(M\)-tap تقریباً ضرب \(LM\) به طور مستقیم هزینه دارد. قضیه کانولوشن دایره ای وعده جایگزینی آن را با دو تبدیل رو به جلو، ضرب \(N\) و یک تبدیل معکوس می دهد، که - زمانی که FFT بخش بعدی در دسترس باشد - به طور چشمگیری ارزان تر است. مانع کلمه دایره است .

رفع مستقیماً از بخش 26-4 می آید. کانولوشن دایره ای مدول کانولوشن خطی \(N\) است. اگر نتیجه خطی به اندازه کافی کوتاه باشد تا در نمونه های \(N\) قرار گیرد، چیزی برای بسته بندی وجود ندارد و این دو بر هم منطبق هستند. فصل 7 طول یک کانولوشن خطی را نشان داد: یک دنباله نقطه ای \(L\) که با یک دنباله نقطه ای \(M\) در هم می پیچد، نقاط \(L+M-1\) را تولید می کند. پس شرط خودش را می نویسد.

🔑
وقتی کانولوشن دایره ای برابر با کانولوشن خطی است
\[ N \;\ge\; L + M - 1 \]

هر دو دنباله را با صفر به طول مشترک \(N\) که این نابرابری را برآورده می کند، قرار دهید، DFT های آنها را بگیرید، نقطه به نقطه ضرب کنید و معکوس کنید. اولین نمونه های \(L+M-1\) نتیجه دقیقاً کانولوشن خطی هستند. بقیه صفر هستند اگر \(N\) کوچکتر باشد، آخرین نمونه های \(L+M-1-N\) روی نمونه های اول جمع می شوند و آنها را خراب می کنند.

که یک بلوک را مدیریت می کند. یک مشکل فیلترینگ واقعی سیگنالی دارد که بسیار طولانی تر از فیلتر است یا اصلاً پایانی ندارد - صدا از میکروفون می رسد، نمونه هایی که از ADC می آیند. دگرگونی کل موضوع غیرممکن است و در هر صورت تاخیری غیرقابل قبول را به همراه خواهد داشت. بنابراین سیگنال به بلوک‌ها بریده می‌شود و دو روش استاندارد برای دوختن نتایج مسدود شده به یکدیگر ارزش دانستن نام دارند.

Overlap-add ورودی را به بلوک های غیر همپوشانی به طول \(L\) برش می دهد. هر بلوک با فیلتر \(M\)-tap با استفاده از یک DFT نقطه‌ای \(N\) با \(N \ge L+M-1\) پیچیده می‌شود و یک بلوک خروجی به طول \(L+M-1\) تولید می‌کند. از آنجایی که کانولوشن خطی است و بلوک‌های ورودی به ورودی اضافه می‌شوند، بلوک‌های خروجی باید به خروجی جمع شوند - اما بلوک‌های خروجی متوالی توسط نمونه‌های \(M-1\) همپوشانی دارند و در آن منطقه همپوشانی اضافه می‌شوند. نام یک توصیف تحت اللفظی است.

همپوشانی-ذخیره حسابداری را به روش دیگری ترتیب می دهد. بلوک‌های ورودی با طول \(N\) با همپوشانی نمونه‌های \(M-1\) بین بلوک‌های متوالی گرفته می‌شوند. هر بلوک به صورت دایره‌ای با فیلتر پرشده در هم می‌پیچد و اولین نمونه‌های خروجی \(M-1\) از هر بلوک - دقیقاً نمونه‌هایی که در اثر پیچ‌شدن خراب شده‌اند - دور ریخته می‌شوند. چیزی اضافه نشده است. قطعات باقی مانده به سادگی به هم متصل می شوند. نیازی به بافر خروجی ندارد، به همین دلیل است که انتخاب معمولی در سخت افزار است.

کدام \(N\)؟ بلوک‌های بزرگ‌تر سربار تبدیل را بر روی نمونه‌های خروجی بیشتری مستهلک می‌کنند، بنابراین هزینه هر نمونه کاهش می‌یابد - اما تأخیر افزایش می‌یابد، زیرا تا زمانی که یک بلوک کامل نرسد، خروجی ظاهر نمی‌شود. طرح‌های واقعی \(N\) را به عنوان کوچک‌ترین توان از دو انتخاب می‌کنند که بودجه تأخیر را برآورده می‌کند، معمولاً چهار تا هشت برابر \(M\). فراتر از آن، هزینه هر نمونه صاف می شود و تنها تاخیر رشد می کند.
بخش 26-7

هزینه، و ایده پشت FFT

محاسبات را در DFT به صورت نوشته بشمارید. هر یک از مقادیر \(N\) \(X[k]\) مجموع محصولات \(N\) است، بنابراین محاسبه مستقیم هزینه های \(N^2\) ضرب مختلط و \(N(N-1)\) را دارد. رشد درجه دوم مشکل است. دوبرابر کردن طول رکورد کار را چهار برابر می‌کند و یک تبدیل 4096 نقطه‌ای تقریباً به هفده میلیون ضرب پیچیده نیاز دارد - برای یک پردازنده مدرن یک بار کاملاً قابل احترام است و اگر باید هزار بار در ثانیه انجام شود ناامیدکننده است.

کولی و توکی این فرار را در سال 1965 منتشر کردند، اگرچه گاوس همان ترفند را در سال 1805 پیدا کرد و آن را به لاتین منتشر نکرد. ایده تفرقه کن و غلبه کن، و اهرم سومین هویت پیچیده، \(W_N^{k+N/2} = -W_N^{k}\) است.

بگذارید \(N\) زوج باشد و مجموع را بر برابری شاخص نمونه تقسیم کنیم - نمونه‌های زوج در یک گروه و با اعداد فرد در گروه دیگر. نوشتن \(n = 2r\) برای شرایط زوج و \(n = 2r+1\) برای فرد:

تقسیم DFT بر اساس برابری - کاهش در زمان
\[ X[k] \;=\; \sum_{r=0}^{N/2-1} x[2r]\,W_N^{2rk} \;+\; \sum_{r=0}^{N/2-1} x[2r+1]\,W_N^{(2r+1)k} \;=\; \sum_{r=0}^{N/2-1} x[2r]\,W_N^{2rk} \;+\; W_N^{k}\sum_{r=0}^{N/2-1} x[2r+1]\,W_N^{2rk} \]

اکنون مشاهده حیاتی در مورد توان. از آنجایی که \(W_N^{2} = e^{-j4\pi/N} = e^{-j2\pi/(N/2)} = W_{N/2}\)، هر دو مجموع باقیمانده دقیقاً \(N/2\) نقطه DFT هستند - به ترتیب از دنباله‌های فرعی با نمایه‌سازی زوج و دنباله‌ای با نمایه‌سازی فرد. آنها را \(G[k]\) و \(H[k]\) صدا کنید.

دو تبدیل نیمه طول، دوباره ترکیب شده است
\[ X[k] \;=\; G[k] \;+\; W_N^{k}\,H[k], \qquad G[k]=\!\!\sum_{r=0}^{N/2-1}\!\! x[2r]W_{N/2}^{rk}, \quad H[k]=\!\!\sum_{r=0}^{N/2-1}\!\! x[2r+1]W_{N/2}^{rk} \]

به نظر می‌رسد که فقط \(k = 0,\dots,N/2-1\) را پوشش می‌دهد، زیرا \(G\) و \(H\) تبدیل‌های نقطه‌ای \(N/2\) هستند و فقط تا اینجا تعریف شده‌اند. اما آنها دوره ای با دوره \(N/2\) هستند، بنابراین \(G[k+N/2] = G[k]\) و \(H[k+N/2] = H[k]\). و هویت twiddle به \(W_N^{k+N/2} = -W_N^{k}\) می دهد. بنابراین جایگزینی \(k+N/2\) هزینه جدیدی ندارد:

🔑
پروانه رادیکس-2
\[ X[k] = G[k] + W_N^{k}H[k], \qquad X\!\left[k+\tfrac{N}{2}\right] = G[k] - W_N^{k}H[k], \qquad k = 0,\dots,\tfrac{N}{2}-1 \]

یک ضرب مختلط \(W_N^k H[k]\) دو مقدار خروجی تولید می کند، یکی با جمع و دیگری با تفریق. این دو به یک کل پس انداز است، و هر چیز دیگری در FFT حسابداری در اطراف آن است.

آنچه به دست آمده را بشمارید. محاسبه دو DFT نقطه‌ای \(N/2\) مستقیماً ضرب‌های \(2(N/2)^2 = N^2/2\) را هزینه می‌کند و هزینه نوترکیب \(N/2\) بیشتر است - تقریباً نیمی از \(N^2\) اصلی. اما دو تبدیل نیمه طول را می توان به همین ترتیب تقسیم کرد و نصف آنها بعد از آن. اگر \(N\) توان دو باشد، تقسیم تا زمانی ادامه می‌یابد که تبدیل‌ها به طول 1 شوند و یک DFT 1 نقطه‌ای هویت است: \(X[0] = x[0]\)، اصلاً حسابی وجود ندارد.

بازگشت و راه حل آن
\[ T(N) = 2\,T\!\left(\tfrac{N}{2}\right) + \tfrac{N}{2}, \qquad T(1) = 0 \qquad\Longrightarrow\qquad T(N) = \tfrac{N}{2}\log_2 N \]

سطوح تقسیم \(\log_2 N\) وجود دارد، هر سطح شامل پروانه های \(N/2\) است، هر پروانه یک ضرب مختلط و دو جمع پیچیده هزینه دارد. مجموع ضرب‌های مختلط \(\tfrac{N}{2}\log_2 N\) و جمع‌های مختلط \(N\log_2 N\) است و تبدیل از درجه دوم به تقریباً خطی شده است.

بخش 26-8

پروانه ها، معکوس کردن بیت، و تعداد عملیات

فرمول نوترکیبی به عنوان یک تقاطع دو ورودی، دو خروجی ترسیم می شود که شکل آن نام آن را می دهد. ورودی بالایی مستقیماً از هر دو خروجی عبور می کند. ورودی پایین تر در ضریب پیچیدگی یک بار ضرب می شود و سپس در بالا اضافه می شود و در پایین کم می شود.

× W ᴺ ᵏ G[k] H[k] X[k] X[k+N/2] + −
یک پروانه - یک ضرب مختلط، دو جمع مختلط، دو خروجی

چیدمان پروانه های \(N/2\) در هر مرحله و \(\log_2 N\) نمودار جریان زیر را برای \(N = 8\) ایجاد می کند. آن را از چپ به راست بخوانید: مرحله اول نمونه‌ها را به صورت جفت ترکیب می‌کند، مرحله دوم نتایج جفت را ترکیب می‌کند، مرحله سوم آن‌ها را ترکیب می‌کند. سه مرحله، هر کدام چهار پروانه، در مجموع دوازده پروانه - در مقابل شصت و چهار ضربی که یک DFT 8 نقطه ای مستقیم نیاز دارد.

stage 1 stage 2 stage 3 x[0]x[4] x[2]x[6] x[1]x[5] x[3]x[7] X[0]X[1] X[2]X[3] X[4]X[5] X[6]X[7] W⁰W¹ W²W³ grey = pass through and add · gold = multiply by a twiddle and cross
FFT 8 نقطه‌ای کاهش در زمان - سه مرحله، هر کدام چهار پروانه، ورودی‌ها با بیت معکوس

ترتیب ورودی دلخواه به نظر می رسد و اینطور نیست. اولین تقسیم از شاخص های فرد جدا می شود. دومی هر نیمه را با بیت بعدی شاخص تقسیم می کند. و غیره پس از تقسیم \(\log_2 N\)، نمونه \(n\) به موقعیتی که نمایش باینری آن \(n\) به عقب نوشته شده است، منتقل شده است. برای \(N = 8\): شاخص 1 \(001\) است، \(100 = 4\) معکوس است، بنابراین \(x[1]\) در موقعیت 4 قرار می گیرد - دقیقاً جایی که شکل آن را نشان می دهد.

\(n\) اعشاریباینری \(n\)معکوس شدموقعیت
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117

خواندن ستون "موقعیت" به سمت پایین \(0,4,2,6,1,5,3,7\)، ترتیب ورودی در نمودار جریان را می دهد. جایگشت معکوس خودش است، بنابراین یک گذر در محل از مبادله های زوجی آن را انجام می دهد، و سپس کل تبدیل در همان آرایه بدون ذخیره سازی اضافی انجام می شود. این ویژگی در محل به اندازه سرعت در سخت افزارهای کوچک اهمیت دارد.

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

سود به بهترین وجه از نظر عددی قدردانی می شود.

\(N\)DFT مستقیم: \(N^2\) multsRadix-2 FFT: \(\tfrac{N}{2}\log_2 N\)افزایش سرعت
864125.3 ×
644 09619221.3 ×
25665 5361 02464 ×
1 0241 048 5765 120204.8 ×
4 09616 777 21624 576682.7 ×
65 5364 294 967 296524 2888 192 ×
چرا این الگوریتم مهندسی را تغییر داد؟ قبل از سال 1965، تجزیه و تحلیل طیف به معنای بانک های فیلتر آنالوگ و نوسانگرهای جاروب بود. FFT یک طیف دیجیتال را به اندازه کافی ارزان کرد تا بتوان در زمان واقعی محاسبه کرد، و با آن فیلتر دیجیتال با کانولوشن سریع، مدولاسیون OFDM، کدگذاری MP3 و JPEG، بازسازی MRI و فشرده سازی پالس رادار به وجود آمد. ریاضیات این فصل صد و پنجاه سال قدمت دارد. عمل شصت سال گذشته بر یک مشاهده در مورد علامت \(W_N^{k+N/2}\) استوار است.
بخش 26-9

تجزیه و تحلیل طیفی در عمل

فرض کنید یک سیگنال پیوسته در \(f_s\) هرتز نمونه‌برداری شده است، نمونه های \(N\) جمع آوری شده و DFT آنها گرفته می شود. Bin \(k\) در \(\Omega_k = 2\pi k/N\) رادیان در هر نمونه قرار دارد که با توجه به رابطه فصل 20 \(\Omega = 2\pi f/f_s\) با فرکانس آنالوگ مطابقت دارد.

شاخص bin به هرتز و طول رکورد
\[ f_k = \frac{k\,f_s}{N} \quad\text{hertz}, \qquad \Delta f = \frac{f_s}{N}, \qquad T = \frac{N}{f_s} = \frac{1}{\Delta f} \]

فاصله بین \(\Delta f\) متقابل مدت زمان رکورد \(T\) است و آن رابطه واحد بر هر چیزی که در ادامه می آید حاکم است. یک سیگنال را برای یک دهم ثانیه تماشا کنید و طیف به یک شبکه 10 هرتز می رسد، هر نرخ نمونه‌برداری.

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

یک مورد شانس وجود دارد. اگر فرکانس آهنگ دقیقاً روی یک bin قرار گیرد، تعداد صحیحی از چرخه‌های آن در داخل رکورد قرار می‌گیرد، پسوند دوره‌ای بخش 26-4 یکپارچه به هم می‌پیوندد، و هر لوب جانبی دقیقاً روی یک صفر از هسته قرار می‌گیرد. سپس DFT یک سنبله تمیز را نشان می دهد. تون را نیم سطل به سمت مرکز حرکت دهید و رکورد دیگر به بالا نمی‌پیوندد: ناپیوستگی در درز دارای محتوای پهنای باند است، لوب‌های کناری دیگر روی صفر قرار نمی‌گیرند و انرژی در کل طیف ظاهر می‌شود.

🔑
نشتی ناشی از درز است نه تغییر شکل
\[ f_{\text{tone}} = \frac{k f_s}{N} \ \ \text{(exactly)} \;\Longrightarrow\; \text{no leakage}; \qquad \text{otherwise, leakage into every bin} \]

DFT در هر دو مورد به درستی رفتار می کند. طیف گسترش دوره‌ای آنچه شما به آن داده‌اید را گزارش می‌کند، و زمانی که رکورد به آرامی به هم نمی‌پیوندد، آن فرمت دوره‌ای واقعاً شامل یک ناپیوستگی گام در هر نمونه \(N\) است.

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

پنجرهتعریف در \(0 \le n \le N-1\)عرض لوب اصلیلوب کناری قله
مستطیل شکل\(w[n]=1\)2 خانه\(-13\) دسی بل
هان\(0.5-0.5\cos\!\frac{2\pi n}{N-1}\)4 خانه\(-31\) دسی بل
همینگ\(0.54-0.46\cos\!\frac{2\pi n}{N-1}\)4 خانه\(-43\) دسی بل
بلکمن\(0.42-0.5\cos\!\frac{2\pi n}{N-1}+0.08\cos\!\frac{4\pi n}{N-1}\)6 خانه\(-58\) دسی بل

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

آن تذکر آخر نکته دوم است. صفر کردن یک رکورد به طول تبدیل طولانی‌تر، خانه‌های بیشتری را ایجاد می‌کند، با فاصله ریزتر، و نموداری به‌طور واضح صاف‌تر ایجاد می‌کند. هیچ اطلاعاتی اضافه نمی‌کند: نمونه‌های اضافی صفر هستند، مدت زمان رکورد \(T\) بدون تغییر است، و شبکه ظریف‌تر فقط همان DTFT زیرین را درون‌یابی می‌کند. لایه‌بندی صفر مفید است – اوج را با دقت بیشتری تعیین می‌کند و جلوه حصار حصار را حذف می‌کند، که در آن پیکی که بین خانه‌ها قرار می‌گیرد تا 3.9 دسی‌بل کمتر خوانده می‌شود – اما این ادعا که وضوح را بهبود می‌بخشد به سادگی نادرست است.

دو دستگیره، دو افکت. نرخ نمونه‌برداری \(f_s\) بالاترین فرکانسی را که می توانید بدون هم‌پوشانی طیفی مشاهده کنید تعیین می کند (فصل 20). طول رکورد \(T = N/f_s\) تعیین می کند که چقدر می توانید فرکانس ها را تشخیص دهید. آنها مستقل هستند و گیج کردن آنها رایج ترین خطا در اندازه گیری های طیف آزمایشگاهی است: نمونه‌برداری سریعتر وضوح را بهبود نمی بخشد و تماشای طولانی تر پهنای باند را افزایش نمی دهد.
بخش 26-10

نمونه های کار شده

1 یک DFT 4 نقطه ای با دست، با پارسوال بررسی شده است

مشکل DFT 4 نقطه ای \(x[n] = \{1,\,2,\,3,\,4\}\) را برای \(n = 0,1,2,3\) محاسبه کنید و با استفاده از رابطه پارسوال پاسخ را تأیید کنید.

راه حل. با \(N = 4\) فاکتور پیچیدگی \(W_4 = e^{-j\pi/2} = -j\) است، بنابراین کل محاسبات توان های \(-j\) است و نیازی به مثلثات نیست. از آنجایی که \(X[k] = \sum_{n} x[n](-j)^{kn}\)،

کار کردن - چهار ضریب
\[ \begin{aligned} X[0] &= 1+2+3+4 = 10\\ X[1] &= 1 + 2(-j) + 3(-j)^2 + 4(-j)^3 = 1 - 2j - 3 + 4j = -2 + 2j\\ X[2] &= 1 + 2(-1) + 3(1) + 4(-1) = -2\\ X[3] &= 1 + 2(j) + 3(-1) + 4(-j) = -2 - 2j \end{aligned} \]

دو چک فوری است. \(X[0] = 10\) مجموع نمونه ها است، همانطور که باید باشد. و \(X[2] = X[N/2]\) مجموع متناوب \(1-2+3-4 = -2\) است، همچنین همانطور که باید باشد. سیگنال حقیقی است، بنابراین تقارن مزدوج نیاز به \(X[3] = X^{*}[1]\) دارد و در واقع \(-2-2j\) مزدوج \(-2+2j\) است.

رابطه پارسوال قوی ترین آزمون است، زیرا شامل هر عدد می شود:

کار - بررسی انرژی
\[ \sum_{n=0}^{3}|x[n]|^2 = 1+4+9+16 = 30, \qquad \frac{1}{4}\sum_{k=0}^{3}|X[k]|^2 = \frac{100 + 8 + 4 + 8}{4} = \frac{120}{4} = 30 \]

با استفاده از \(|-2+2j|^2 = 4+4 = 8\). این دو موافق هستند، بنابراین تبدیل درست است.

2 هم‌پوشانی طیفی دامنه زمانی قابل مشاهده است

مشکل دنباله \(x[n] = (0.5)^n u[n]\) بی نهایت طولانی است. DTFT آن در نقاط \(N = 4\) نمونه‌برداری می شود و DFT معکوس گرفته می شود. چه چیزی برمی گردد و چقدر با \(x[n]\) تفاوت دارد؟

راه حل. در نتیجه بخش 26-4 پاسخ پسوند دوره ای مستعار \(x_p[n] = \sum_{r} x[n+rN]\) است. از آنجایی که \(x[n]\) علّی است، فقط \(r \ge 0\) کمک می کند و هر جمله مضرب ثابت عبارت قبلی است:

کار کردن - دم را به عقب تا کنید
\[ x_p[n] = \sum_{r=0}^{\infty} (0.5)^{\,n+4r} = (0.5)^n\sum_{r=0}^{\infty}\big[(0.5)^4\big]^r = \frac{(0.5)^n}{1-(0.5)^4} = \frac{(0.5)^n}{0.9375} \]

به صورت عددی \(x_p = \{1.0667,\ 0.5333,\ 0.2667,\ 0.1333\}\) در برابر \(\{1,\ 0.5,\ 0.25,\ 0.125\}\) واقعی. هر نمونه با همان ضریب \(1/0.9375\) بسیار بزرگ است، یعنی 6.67٪ - دم تا شده به خودی خود یک کپی مقیاس شده از سر است، زیرا یک دنباله هندسی در هنگام جابجایی خود مشابه است.

تأیید کنید که DFT 4 نقطه ای \(x_p\) واقعاً نمونه های DTFT را بازتولید می کند. DTFT \(X(e^{j\Omega}) = 1/(1-0.5e^{-j\Omega})\) است، بنابراین در \(\Omega_0 = 0\) برابر با \(1/0.5 = 2\) است. و مجموع \(x_p\) \(1.0667+0.5333+0.2667+0.1333 = 2.000\) است. در \(\Omega_1 = \pi/2\)، \(X = 1/(1+0.5j) = 0.8 - 0.4j\)؛ و

در حال کار - ضریب \(k=1\)
\[ X_p[1] = 1.0667 - 0.5333j - 0.2667 + 0.1333j = 0.8 - 0.4j \]

دقیقا همانطور که لازم است مقادیر DFT نمونه های صحیحی از DTFT هستند. این توالی است که آنها به آن معکوس می کنند که خراب شده است. افزایش \(N\) خطا را مانند \(0.5^N\) کوچک می کند، به همین دلیل است که اگر رکورد چندین ثابت زمانی را پوشش دهد، سیگنال پوسیده معمولاً ایمن است.

3 دایره در برابر کانولوشن خطی، و درمان

مشکل اجازه دهید \(x[n] = \{1,2,3\}\) و \(h[n] = \{1,1\}\). کانولوشن خطی و سپس کانولوشن دایره ای 3 نقطه را پیدا کنید و نشان دهید که چگونه لایه صفر آنها را با هم تطبیق می دهد.

راه حل. کانولوشن خطی دارای طول \(3+2-1 = 4\) است. لغزش \(h\) در امتداد \(x\) به روش فصل 7 نشان می دهد

کار - کانولوشن خطی
\[ y_{\text{lin}} = \{1,\ 1+2,\ 2+3,\ 3\} = \{1,\ 3,\ 5,\ 3\} \]

اکنون کانولوشن دایره ای 3 نقطه ای. Pad \(h\) به \(\{1,1,0\}\) بنابراین هر دو دنباله دارای طول 3 هستند و \(y[n] = \sum_{m=0}^{2}x[m]h[(n-m)_3]\) را ارزیابی می کنند:

کار - کانولوشن دایره ای 3 نقطه ای
\[ \begin{aligned} y[0] &= x[0]h[0] + x[1]h[2] + x[2]h[1] = 1 + 0 + 3 = 4\\ y[1] &= x[0]h[1] + x[1]h[0] + x[2]h[2] = 1 + 2 + 0 = 3\\ y[2] &= x[0]h[2] + x[1]h[1] + x[2]h[0] = 0 + 2 + 3 = 5 \end{aligned} \]

بنابراین \(y_{\text{circ}} = \{4,3,5\}\). با نتیجه خطی مقایسه کنید: نمونه چهارم، 3، در یک رکورد طول 3 جایی برای رفتن نداشت و به دور اول پیچید و عدد 1 را به \(1+3 = 4\) تبدیل کرد. هیچ چیز دیگری تغییر نکرد. این هم‌پوشانی طیفی دامنه زمانی در عینی ترین شکل آن است.

شرط \(N \ge L+M-1 = 4\) می گوید از تبدیل 4 نقطه ای استفاده کنید. روی \(x = \{1,2,3,0\}\) و \(h = \{1,1,0,0\}\) قرار دهید و تکرار کنید:

کار - کانولوشن دایره ای 4 نقطه ای
\[ y[0]=1,\quad y[1]=1+2=3,\quad y[2]=2+3=5,\quad y[3]=3+0=3 \]

که \(\{1,3,5,3\}\) است، کانولوشن خطی دقیقا. یک صفر اضافی در هر دنباله کل تفاوت بین یک پاسخ اشتباه و یک پاسخ درست بود.

4 یک FFT 8 نقطه ای از میان پروانه هایش ردیابی شد

مشکل DFT 8 نقطه ای \(x[n] = \{1,1,1,1,0,0,0,0\}\) را با استفاده از تجزیه به موقع محاسبه کنید و \(X[1]\) را در برابر ارزیابی مستقیم تأیید کنید.

راه حل. تقسیم بر اساس برابری. نمونه‌های دارای نمایه زوج \(g = \{x[0],x[2],x[4],x[6]\} = \{1,1,0,0\}\) و شاخص‌های فرد \(h = \{x[1],x[3],x[5],x[7]\} = \{1,1,0,0\}\) هستند - یک دنباله یکسان، بنابراین یک DFT 4 نقطه‌ای برای هر دو استفاده می‌شود. با \(W_4 = -j\)،

کار - دو تبدیل 4 نقطه ای
\[ G[k] = H[k] = 1 + (-j)^k \;\Longrightarrow\; G = H = \{\,2,\ 1-j,\ 0,\ 1+j\,\} \]

اکنون با استفاده از \(W_8 = e^{-j\pi/4}\) با پروانه دوباره ترکیب کنید تا \(W_8^0 = 1\)، \(W_8^1 = \tfrac{\sqrt2}{2}(1-j)\)، \(W_8^2 = -j\) و \(W_8^3 = -\tfrac{\sqrt2}{2}(1+j)\). اصطلاحات عجیب و غریب پیچ خورده هستند

کار - محصولات \(W_8^k H[k]\)
\[ W_8^0H[0] = 2, \quad W_8^1H[1] = \tfrac{\sqrt2}{2}(1-j)(1-j) = -j\sqrt2, \quad W_8^2H[2] = 0, \quad W_8^3H[3] = -\tfrac{\sqrt2}{2}(1+j)(1+j) = -j\sqrt2 \]

با استفاده از \((1-j)^2 = -2j\) و \((1+j)^2 = 2j\). با افزودن و تفریق این موارد از \(G[k]\)، هر هشت خروجی به طور همزمان به دست می‌آید:

کارکردن - هشت ضریب
\[ \begin{aligned} X[0] &= 2+2 = 4, &\quad X[4] &= 2-2 = 0\\ X[1] &= (1-j) - j\sqrt2 = 1 - j2.4142, &\quad X[5] &= (1-j) + j\sqrt2 = 1 + j0.4142\\ X[2] &= 0+0 = 0, &\quad X[6] &= 0-0 = 0\\ X[3] &= (1+j) - j\sqrt2 = 1 - j0.4142, &\quad X[7] &= (1+j) + j\sqrt2 = 1 + j2.4142 \end{aligned} \]

سه چک \(X[0] = 4\) مجموع نمونه ها است. تقارن مزدوج \(X[8-k] = X^{*}[k]\) برای هر جفت برقرار است. و ارزیابی مستقیم \(X[1] = \sum_{n=0}^{3}e^{-j\pi n/4}\) یک سری هندسی را با \((1-e^{-j\pi})/(1-e^{-j\pi/4}) = 2/(0.2929+0.7071j) = 1 - 2.4142j\) جمع می‌کند که با نتیجه پروانه مطابقت دارد.

کار را بشمارید: دوازده پروانه، در برابر شصت و چهار ضرب برای تبدیل مستقیم - و نیمی از این پروانه‌ها ضریب چرخشی 1 یا 0 داشتند و اصلاً هزینه‌ای نداشتند.

5 آیا کانولوشن سریع واقعا ارزشش را دارد؟

مشکل یک فیلتر FIR 256 ضربه ای باید روی سیگنال حقیقی طولانی با استفاده از همپوشانی-افزودن با FFT های 1024 نقطه ای اجرا شود. هزینه محاسباتی هر نمونه خروجی را با کانولوشن مستقیم مقایسه کنید.

راه حل. با \(M = 256\) و \(N = 1024\)، هر بلوک می تواند نمونه های ورودی جدید \(L = N - M + 1 = 769\) را حمل کند و همچنان \(N \ge L+M-1\) را برآورده کند. DFT فیلتر یک بار محاسبه می شود و مجدداً مورد استفاده قرار می گیرد، بنابراین هزینه هر بلوک یک FFT رو به جلو، \(N\) ضرب پیچیده در حوزه فرکانس و یک FFT معکوس است:

کار - هزینه یک بلوک
\[ 2 \times \frac{N}{2}\log_2 N \;+\; N \;=\; 2(512)(10) + 1024 \;=\; 10\,240 + 1024 \;=\; 11\,264 \ \text{complex multiplications} \]

تقسیم بر 769 نمونه خروجی که بلوک تولید می کند، ضرب های پیچیده \(11\,264/769 \approx 14.6\) را در هر نمونه خروجی به دست می دهد. یک ضرب مختلط چهار ضرب واقعی است، بنابراین این در حدود 58.6 ضرب واقعی در هر نمونه است.

کانولوشن مستقیم یک ضرب واقعی برای هر ضربه در هر نمونه هزینه دارد، یعنی 256. بنابراین کانولوشن سریع در اینجا حدود \(256/58.6 \approx 4.4\) برابر ارزانتر است. دوبرابر کردن فیلتر به 512 ضربه، هزینه مستقیم را دو برابر می کند در حالی که به سختی هزینه FFT را جابجا می کند، بنابراین مزیت تقریباً دو برابر می شود. از طرف دیگر، برای یک فیلتر ده یا بیست ضربه ای، باتلاق های سربار تبدیل، صرفه جویی و کانولوشن مستقیم برنده می شود.

نقطه سربه سر معمولاً چیزی بین 30 تا 60 ضربه روی یک پردازنده همه منظوره است. در زیر آن، مستقیماً بپیچید. در بالای آن، تبدیل.

6 خواندن صحیح یک طیف آزمایشگاهی

مشکل یک سیگنال در \(f_s = 8\) کیلوهرتز نمونه‌برداری می شود و نمونه های \(N = 1024\) تبدیل می شوند. الف) فاصله بین سطل ها چقدر است؟ (ب) صدای 1000 هرتز کجا ظاهر می شود و آیا نشت می کند؟ ج) آیا دو تن در 1000 هرتز و 1006 هرتز قابل حل هستند؟ (د) آیا صفر کردن تا 4096 امتیاز کمکی می کند؟

راه حل (الف). \(\Delta f = f_s/N = 8000/1024 = 7.8125\) هرتز، و رکورد \(T = 1024/8000 = 0.128\) s طول می کشد. همانطور که وعده داده شده بود، \(1/T = 7.8125\) هرتز.

راه حل (ب).\(k = 1000/7.8125 = 128\)دقیقاً، بنابراین تن دقیقاً روی bin 128 می افتد. تعداد صحیح چرخه - 128 تای آنها - در داخل رکورد قرار می گیرد، پسوند دوره ای بدون درز به هم می پیوندد، و طیف یک خط تمیز را در bin 128 نشان می دهد (با آینه آن در bin).\(1024-128 = 896\)) و اساساً هیچ جای دیگر. صدایی در 1005 هرتز می‌نشیند\(k = 128.64\)، بین خانه ها، و به همه آنها نشت می کرد.

راه حل (ج). تونها 6 هرتز از هم فاصله دارند که کمتر از فاصله بین 7.8125 هرتز است، بنابراین آنها در یک سطل قرار می گیرند و نمی توان آنها را از هم جدا کرد - هیچ مقدار پردازش آنها را بازیابی نمی کند. وضوح نیاز به مشاهده طولانی تری دارد: یک پنجره مستطیلی به \(T \ge 1/6 \approx 0.167\) s نیاز دارد، از این رو \(N \ge 8000/6 \approx 1334\)، تا 2048 نمونه گرد شده است. با پنجره هان که پهنای لوب اصلی آن دو برابر است، \(T \ge 2/6 = 0.333\) s و \(N \ge 2667\) به 4096 گرد شده است.

راه حل (د). نه. صفر کردن همان 1024 نمونه به یک تبدیل 4096 نقطه ای، فاصله سطل را تا 1.95 هرتز یک چهارم می کند و منحنی صاف تری می کشد، اما \(T\) هنوز 0.128 ثانیه است و DTFT زیربنایی بدون تغییر است - این دو رنگ بیشتر در یک نمونه ادغام شده اند. درون یابی صفر بالشتک. حل نمی شود ارزش این را دارد که در مورد 1005 هرتز در قسمت (ب) انجام شود، جایی که یک شبکه ریزتر محل اوج را پین می‌کند و از خوانش پایین حصار تا 3.9 دسی بل جلوگیری می‌کند.

مرور کنید

خلاصه فصل

✓ جفت DFT

\(X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn}\)، \(x[n]=\tfrac1N\sum_k X[k]W_N^{-kn}\)، با \(W_N=e^{-j2\pi/N}\). این DTFT نمونه‌برداری شده در \(\Omega_k = 2\pi k/N\) است.

✓ هم‌پوشانی طیفی دامنه زمانی

نمونه‌برداری از طیف سیگنال را دوره ای می کند: DFT معکوس \(\sum_r x[n+rN]\) را برمی گرداند. همه چیز دایره ای از این نتیجه می گیرد.

✓ کانولوشن دایره ای

\(X_1[k]X_2[k]\) به دایره ای، نه خطی، کانولوشن معکوس می شود. پد به \(N \ge L+M-1\) و این دو موافق هستند.

✓ پروانه

\(X[k]=G[k]+W_N^kH[k]\)، \(X[k+N/2]=G[k]-W_N^kH[k]\). یک ضرب، دو خروجی - کل صرفه جویی در FFT.

✓ تعداد عملیات

\(N^2\) تبدیل به \(\tfrac{N}{2}\log_2 N\) می شود: ضریب 205 در \(N=1024\) و 8192 در \(N=65536\). ورودی ها به صورت بیت معکوس می رسند.

✓ خواندن یک طیف

\(\Delta f = f_s/N = 1/T\). نشت صداهای خارج از بن. پنجره ها لوب های جانبی را برای عرض تجارت می کنند. لایه صفر درون یابی می شود اما هرگز حل نمی شود.

تمرین کنید

مشکلات

مسائل 1 تا 3 تعریف و ویژگی های آن را بیان می کنند. 4 و 5 مربوط به کانولوشن دایره ای است. 6 و 7 ساختار FFT. 8 کاربردهای اندازه گیری قبل از حرکت، هر تبدیل عددی را با \(X[0]\) و با Parseval بررسی کنید.

  1. DFT 4 نقطه ای \(x[n] = \{1,\,0,\,-1,\,0\}\) را محاسبه کنید. \(X[0]\) را تأیید کنید، تقارن مزدوج را تأیید کنید و رابطه پارسوال را بررسی کنید.
  2. DFT 4 نقطه ای برخی از دنباله های واقعی \(X = \{6,\ -2+2j,\ -2,\ -2-2j\}\) است. \(x[n]\) را با استفاده از DFT معکوس بازیابی کنید و بدون محاسبه بیان کنید که DFT \(x[(n-1)_4]\) چقدر خواهد بود.
  3. نشان دهید که اگر \(x[n]\) واقعی است و حتی در مورد \(n = 0\) به معنای دایره ای، یعنی \(x[(-n)_N] = x[n]\)، آنگاه \(X[k]\) برای هر \(k\) واقعی است. آرگومان خود را روی \(x = \{3,\,1,\,2,\,1\}\) با \(N=4\) تست کنید.
  4. اجازه دهید \(x = \{1,\,-1,\,2\}\) و \(h = \{2,\,1\}\). کانولوشن خطی، کانولوشن دایره ای 3 نقطه ای و کوچکترین طول تبدیلی را که نتیجه دایره ای برابر با خطی است، پیدا کنید.
  5. یک فیلتر 64 ضربه ای با همپوشانی-افزودن با استفاده از تبدیل های 512 نقطه ای اعمال می شود. هر بلوک چند نمونه ورودی جدید حمل می‌کند، بلوک‌های خروجی متوالی با چند نمونه همپوشانی دارند و هر نمونه خروجی چند ضرب پیچیده هزینه دارد؟
  6. نمودار جریان 4 نقطه ای کاهش در زمان را رسم کنید. ترتیب ورودی را برچسب گذاری کنید، هر فاکتور پیچیدگی را علامت بزنید و ضرب هایی را که در واقع بی اهمیت هستند بشمارید.
  7. نشان دهید که تعداد کل اضافات پیچیده در یک radix-2 FFT به طول \(N\) \(N\log_2 N\) است. سپس توضیح دهید که چرا صرفه جویی در DFT مستقیم برای جمع کمتر از ضرب است.
  8. یک تون 2 کیلوهرتز و یک تن 2.1 کیلوهرتز با دامنه های بسیار متفاوت در 20 کیلوهرتز نمونه‌برداری می شود. (الف) چه طول رکوردی برای حل آنها با یک پنجره مستطیلی لازم است؟ (ب) چرا ممکن است یک پنجره همینگ ترجیح داده شود حتی اگر به رکورد طولانی تری نیاز دارد؟ (ج) اگر \(N = 1024\)، تون 2 کیلوهرتز روی کدام سطل قرار می گیرد و آیا نشت می کند؟
نکته: در هر سؤال DFT، ابتدا بپرسید دوره ضمنی چیست. اگر سوال شامل جابجایی، کانولوشن یا معکوس باشد، پاسخ دایره ای است مگر اینکه صفرهای کافی برای خطی کردن آن ارائه شده باشد. و در هر سوال اندازه گیری، \(\Delta f = f_s/N\) و \(T = N/f_s\) را قبل از هر چیز دیگری یادداشت کنید - اکثر پاسخ ها معمولاً در آن دو عدد هستند.