Розробка процесора ШПФ. Курсовий проект з Методи, алгоритми та засоби цифрової обробки сигналів та зображень. Робота № 526593

Розробка процесора ШПФ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2014

Тип роботи:

Курсовий проект

Предмет:

Методи, алгоритми та засоби цифрової обробки сигналів та зображень

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ Курсовий проект з курсу: “Методи, алгоритми та засоби цифрової обробки сигналів та зображень ” на тему “Розробка процесора ШПФ” Завдання до курсового проекту Розмірність, N Основа Тип прорідження Вагова функція Час обробки, мс Розрядність вхідних даних, біт (Re + Im) Тип процесора Тип вхідного інтерфейсу, пристрою, часові параметри Тип вихідного інтерфейсу, пристрою 4096 2 T Валле-Пусена 15.0 16 (8+8) TMS320VC5501-300 UART HPI Валле-Пусена 0 ( (n( ( N/4 N/4 ( (n( ( N/2 Анотація У даному курсовому проекті розглянуто реалізацію швидкого перетворення Фур’є на процесорі TMS320VC5501-300, розглянуто особливості реалізації заданого перетворення на цьому процесорі та розраховано основні параметри створеної системи. Зміст Вступ Значна частина задач аналізу тимчасових рядів пов'язана з перетворенням Фур'є і методами його ефективного обчислення. У цих задачах перетворення Фур'є відіграє важливу роль як необхідний проміжний крок у визначенні густини спектра потужності, крос-спектральної густини, передаточних функцій, згорток, кореляційних функцій, а також у задачах інтерполяції значень. На практиці широке поширення одержали алгоритми ШПФ за основою 2 , де кожен функціональний вузол виконує базову операцію - двовходового "метелика". Ці алгоритми орієнтовані, насамперед , на зведення до мінімуму числа операцій множення. Виникає питання про реалізацію алгоритмів ШПФ із більш високими основами і їхніми можливими комбінаціями. Послідовність обчислень будь-якого БПФ можна описати у виді графа, вузли якого виконують фактично звичайне дискретне перетворення, але з меншою розмірністю вхідних векторів (меншою основою). У залежності від вибору основи міняється як загальне число арифметичних операцій, так і кількість ярусів графа. В алгоритмах ШПФ за основою 2 кількість таких шарів максимальна , тому при поетапному надходженні результатів обчислень від ярусу до ярусу відбувається більше нагромадження помилок округлення, ніж в алгоритмах з більш високою основою. І чим вище розмірність вектора вхідних даних, тим більша буде кількість шарів і в наслідок значніша помилка. Це особливо критично у випадках, коли обчислення проводяться в цілочисленній арифметиці (з фіксованою крапкою) чи при недостатньо широкій розрядності даних. Слід також зазначити, що в цьому випадку для запобігання переповнення проміжні результати після кожного чи після групи етапів множення (ярусів графа) необхідно додатково нормалізувати, застосовуючи операцію зсуву вправо. Нормалізація крім зсуву може містити в собі процедуру округлення, що також вносить додаткові обчислювальні витрати. 1. Теоретичний розділ 1. 1. Характеристики процесора TMS320VC5501Відмінні особливості : " Високопродуктивне ядро для операцій з фіксованою точкою з низьким енергоспоживанням TMS320C55 ™ Час циклу 3.3 нс при тактовій частоті 300 МГц Кеш інструкцій 16 Кбайт (I - кеш ) Виконання однієї або двох інструкцій за такт Два помножувачі ( продуктивність до 600 мільйонів множень з накопиченням в секунду ( MMACS )) Два арифметико-логічних пристрої ( АЛП) Три внутрішніх шини читання даних / операндів Дві внутрішніх шини запису даних / операндів Кеш інструкцій ( 16 КБ ) Вбудоване ОЗП (оперативно запам’ятовуючий пристрій) 16К х 16 біт , що складається з 4 блоків по 4K x 16 біт двохпортовим ОЗП ( DARAM ) (всього 32 КБ ) Вбудоване ПЗП (постійний запам’ятовуючий пристрій) 16К х 16 біт ( 32 КБ ) з одним тактом чекання Загальний обсяг адресованої пам'яті 8M х 16 біт (синхронної DRAM) 32 -бітна зовнішня паралельна шина інтерфейсу зовнішньої пам'яті ( EMIF ) з можливістю використання портів введення-виведення загального призначення ( GPIO ) або підключення пам'яті типів: Асинхронне статичне ОЗП ( SRAM ) асинхронне EEPROM Синхронне динамічне ОЗП ( SDRAM ) Синхронне статичне ОЗП з пакетною вибіркою ( SBSRAM ) Емулятор / трасувальник дозволяє зберігати останні 16 переходів програмного лічильника і 32 значення програмного лічильника Програмний контроль енергоспоживання шести функціональних блоків з внутрішніх пристроїв Вбудовані периферійні пристрої: Чотири таймера : 2 64 -бітових таймера загального призначення 64 -бітний сторожовий таймер ( watchdog ) 64 -бітний таймер РТОС DSP / BIOS ™ Шестиканальний контролер прямого доступу до пам'яті ( DMA) Два багатоканальних буферизованих послідовних порти ( McBSP ) Програмований аналоговий тактовий генератор з ФАПЧ ( APLL ) Порти введення-виведення загального призначення ( GPIO ) і вихід загального призначення ( XF ) 8 -бітний паралельний порт керуючого контролера ( HPI ) Інтерфейс Inter- Integrated Circuit ( I2C ) Універсальний асинхронний приймач ( UART ) вбудований емулятор Підтримка периферійного сканування за стандартом JTAG1 варіанти корпусів 176 - вивідних низькопрофільний корпус LQFP (суфікс PGF ) 201 - вивідних корпус MicroStar BGA ™ ( суфікси GZZ і ZZZ ) Живлення ядра 1,26 В Живлення портів введення-виведення 3,3 В /Блок - схема TMS320VC5501 Загальний опис:Цифрові сигнальні процесори (ЦСП) з фіксованою точкою TMS320VC55021 базуються на ядрі TMS320C55x . Дана архітектура має високу продуктивність при низькому енергоспоживанні завдяки підвищенню паралелізму і приділення особливої уваги питанням зниження споживаної потужності. ЦПУ має внутрішньої шинну структуру що складається з програмної шини , трьох шин читання даних , двох шин запису даних і допоміжних шин для периферії і контролера прямого доступу до пам'яті ( DMA) . Це дозволяє виконувати аж до трьох операцій читання даних і двох операцій запису даних за один цикл . Паралельно цьому , контролер DMA може здійснити до двох операцій переміщення даних без задіяння ЦПУ.Ядро ЦСП C55x володіє двома модулями множення - накопичення ( MAC ), кожен з яких здатний виконувати операції типу " множення 17 - біт x 17 - біт " за один цикл. Центральне 40 – бітовий арифметико-логічний пристрій (АЛП ) супроводжується допоміжним 16 - бітним АЛП. Сценарій спільного використання двох АЛП визначається набором інструкцій , забезпечуючи оптимальну паралельну роботу і зниження енергоспоживання . Розподіл ресурсів покладено на адресний пристрій ( АП ) і пристрій даних ( ПД ) ядра ЦСП C55x .Сімейством цифрових сигнальних процесорів C55x підтримуються інструкції з перемінним числом байт , що дозволяє збільшити щільність коду. Модуль інструкцій ( МІ ) здійснює 32 -бітну вибірку інструкцій з внутрішньої чи зовнішньої пам'яті і визначає чергу інструкцій для програмного модуля (ПМ) . У свою чергу , ПМ декодує інструкції , визначає завдання для АП і ПД і управляє захищеним конвеєром . Для запобігання переповнення конвеєра при виконанні умовних переходів використовується передбачення переходів .Набір периферійних пристроїв процесорів 5501 включає в себе інтерфейс зовнішньої пам'яті ( EMIF ) , що забезпечує безпосереднє підключення різних типів асинхронної пам'яті , таких , як EPROM і SRAM , а також високошвидкісних запам'ятовуючих пристроїв високої щільності , таких , як синхронні DRAM і SRAM з пакетною вибіркою. Крім цього , процесори 5501 мають вбудований інтерфейс UART , сторожовий таймер ( watchdog ) і кеш інструкцій (I - кеш ) . Два повнодуплексних багатоканальних буферизованих послідовних портів ( McBSP ) забезпечують безпосереднє підключення великої низки пристроїв зі стандартними послідовними інтерфейсами і багатоканальний обмін ( до 128 каналів з індивідуальним забороною ) . Порт керуючого контролера ( HPI ) являє собою 8 -бітний паралельний інтерфейс, що забезпечує зовнішньому керуючому процесору доступ до 16 кбайт вбудованої пам'яті процесорів 5501 . Порт HPI може бути налаштований як в мультиплексний , так і в немультіплексний режим , що дозволяє використовувати його спільно з самими різними керуючими процесорами. Контролер прямого доступу до пам'яті ( DMA) забезпечує переміщення даних по шести незалежних каналах без втручання ЦПУ , його сумарна пропускна здатність становить до двох 16 - бітних слів за цикл . Крім цього , набір периферійних пристроїв включає в себе 2 таймера загального призначення , вісім виводів загального призначення ( GPIO ) і аналогового генератора з ФАПЧ ( APLL ) . Нове покоління цифрових сигнальних процесорів C55x базується на принципах , закладених в попередньому поколінні потужних і економічних ЦСП сімейства C54x . Процесори C55x володіють новими програмними можливостями , в той же час зберігаючи програмну сумісність з існуючими пристроями сімейства C54x . Широкі можливості нового сімейства цифрових сигнальних процесорів C55x дозволяють використовувати їх в мобільних пристроях для підключення до мережі Internet , високошвидкісний радіозв'язку та багатьох інших. Перелічимо основні особливості ядра ЦСП C55x :Передові технології автоматичного управління режимами енергоспоживанняЯдро цифрових сигнальних процесорів сімейства C55x володіє новими можливостями управління енергоспоживанням будь-яких периферійних модулів , масивів пам'яті і вузлів ЦПУ. Моніторинг здійснюється автоматично , при цьому ті вузли процесора , які в поточний момент не використовуються , вимикаються .Збільшене число відключаються блоків ( Idle Domains )З метою подальшого поліпшення функцій управління енергоспоживанням в процесорах сімейства C55x з 3 до 64 збільшено кількість конфігурованих блоків , в яких відключається живлення в режимі " idle " . Блок може складатися з таких компонентів: ЦПУ кеш периферійні модулі Модуль прямого доступу до пам'яті ( DMA) тактовий генератор Інтерфейс зовнішньої пам'яті ( EMIF )Використання цієї опції дозволяє значно оптимізувати енергоспоживання та знизити загальну вартість системи . Завдяки зниженню енергоспоживання зменшується розсіює ядром процесора C55x потужність , що забезпечує інженеру більшу гнучкість при розробці топології друкованої плати .Одним з істотних нововведень , застосованих в цифрових сигнальних процесорах сімейства C55x , є підтримка інструкцій змінної довжини , що базуються на оновленою схемою адресації : Довжина інструкції 8 , 16 , 24 , 32 , 40 або 48 біт. Вибірка команд збільшена з 16 до 32 біт. Вбудований буфер інструкцій проводить автоматичне розпакування інструкцій для найбільш ефективного їх виконання.Завдяки вище переліченим нововведенням , у ядра C55x знижена активність шини пам'яті ядра , що призвело до зниження енергоспоживання . Збільшення довжини інструкцій дозволило виконувати більше число операцій за один такт , що підвищило продуктивність процесора і дозволило знизити вартість системи .Ядро ЦСП C55x володіє підвищеним паралелізмом , що дозволяє значно поліпшити потактову ефективність , укупі з : Додатковим апаратним забезпеченням - здвоєними модулями 17 x 17 біт MAC , другий 16 - бітним АЛП , чотирма додатковими регістрами даних (використовуваних для простих обчислень) і чотирма 40 - бітними акумуляторами , що дозволяють виконувати більше дій за один такт , істотно знижуючи загальне енергоспоживання . Новими програмними можливостями: Автоматичне запаралелювання інструкцій Вбудованими паралельними інструкціями Паралельними інструкціями , що задаються користувачем Додатковими інструкціями , що підвищують ортогональность Додатковими шинами і розширеною адресацією - для наближення продуктивності ядра до теоретичного максимуму , ядро C55x володіє : Трьома 16 -бітними шинами читання даних Двома 16 -бітними шинами запису даних Однією 32 -бітної програмної шиною Шістьма 24 -бітними адресними шинамиПідвищена щільність коду завдань управлінняНові програмні можливості , оптимізовані для завдань управління та реалізовані в ядрі C55x , дозволяють відмовитися від використання додаткових мікроконтролерів , поклавши усі завдання управління на ЦСП : Новий модуль буфера інструкцій , здатний оперувати з інструкціями із змінною довжиною дозволяє підвищити щільність коду і ефективність роботи , в результаті знижуючи енергоспоживання . Додаткові регістри даних і АЛП прискорюють прості обчислення арифметичних і логічних операцій , підвищуючи типізацію коду завдань управління. Умовне виконання - більшість завдань управління використовують значне число умовних переходів за певними умовами . Для прискорення таких операцій , ядро C55x готує виконання обох варіантів , таким чином , після здійснення вибору ядро готове виконувати наступну дію негайно.Інтерфейс зовнішньої пам'ятіІнтерфейс EMIF зовнішньої пам'яті ядра C55x володіє підвищеною пропускною здатністю , опціями розширеної пам'яті і автоматичного відключення живлення , забезпечуючи 32 - розрядний швидкісний доступ до пам'яті типу : Синхронне статичне ОЗП з пакетною вибіркою ( Synchronous Burst SRAM ) і синхронне динамічне ОЗУ ( synchronous DRAM ) Асинхронні статичні і динамічні ОЗП , ПЗП і флеш - пам'ять ( Asynchronous SRAM , DRAM , ROM & Flash)Кеш інструкцій з пакетним заповненням ( Burst Fill )Ядро цифрових сигнальних процесорів C55x володіємо кешем інструкцій , що дозволяє значно збільшити швидкість виконання інструкцій із зовнішньої пам'яті без значного збільшення енергоспоживання . Завдяки тому , що декілька інструкцій можуть бути завантажені в кеш одночасно , процесору не потрібен доступ до пам'яті по кожній інструкції , при цьому операції виконуються на максимальній частоті ядра.Спрощений процес налагодження кодуПокращене апаратне забезпечення емуляції , наявне в ЦСП C55x , спільно з програмним забезпеченням eXpressDSP ™ та іншими налагоджувальними засобами дозволяє спростити і прискорити процес налагодження коду. Налагодження без втручання : установка точки перегляду ( " watch point ") дозволяє спостерігати зміни в необхідних регістрах під час виконання програми , без зупинки ЦСП . Обмін даними в реальному режимі часу ( RTDX ) дозволяє спостерігати результати роботи програми без зупинки ЦСП . Буфер FIFO трасувальника , що працює з емулятором XDS510 фірми Texas Instruments дозволяє зберігати останні 16 переходів програмного лічильника і 32 значення програмного лічильника.Периферійні пристрої сімейства C55xСімейство 16 - бітних цифрових сигнальних процесорів з фіксованою точкою C5000 володіє найширшим вибором необхідних розробникам вбудованих периферійних пристроїв. Орієнтована на високоефективні портативні пристрої з батарейним харчуванням , платформа процесорів C5000 забезпечує високу гнучкість при розробці , володіючи такими периферійними пристроями , як: Інтерфейс USB 2.0 Full- Speed Апаратний УСАПП ( UART ) Інтерфейс Inter Integrated - Circuit ( I2C ) Аналогово -цифровий перетворювач ( АЦП) Підтримка карт Multimedia Card / Secure Digital ( MMC / SD) Апаратна підтримка відео Багатоканальні буферизованная послідовні порти ( McBSP ) Безпосередній доступ до пам'яті ( DMA) 8/16-бітний інтерфейс Enhanced Host Port Interface ( EHPI )Інтерфейс USB 2.0 Full- Speed ( 12 Мбіт / с) - C5509Сумісність з іншими USB -сумісними пристроями . Сертифікована організацією USB Implementers Forum швидкість передачі даних до 12 Мбіт / с. Апаратний УСАПП ( UART ) - C5404 , C5407 , C5502 Стандартний асинхронний протокол , який здійснює перетворення даних з послідовного в паралельний формат для зв'язку периферійних пристроїв з ЦПУ. Володіє можливостями контролю і схемою переривань , призначеними для мінімізації програмних витрат при управлінні транзакціями . Можливість переведення прийому чи передачі в допоміжний режим FIFO - буферизації , що дозволяє вивільнити ресурси процесора і скоротити програмні витрати за допомогою буферизації прийнятих і переданих даних. Швидкість передачі даних по послідовному порту 11,52 Кб/с.Аналогово -цифровий перетворювач ( АЦП) - C5509 Архітектура аналогово -цифрового перетворення послідовного наближення з розрядністю до 10 біт забезпечує наднизьким споживанням енергії . Максимальна частота вибірки до 21.5 кГц. Призначений для оцифровки аналогових сигналів , таких , як напруга на движку змінного резистора на панелі оператора , напруга елемента живлення і т.д.Підтримка карт Multimedia Card / Secure Digital ( MMC / SD) - C5509 "Прозорий " інтерфейс до двох найбільш популярним типам карт флеш -пам'яті , призначеним для зберігання цифрових даних , таких , як звукові файли , файли зображень , відео і т.д. Підтримка апаратних протоколів MMC / SD і SPI Програмована тактова частота для забезпечення необхідних тимчасових співвідношень між апаратним контролером MMC / SD і картою . Блок MMC / SD забезпечує передачу даних між ЦПУ або контролером прямого доступу до пам'яті ( DMA) і картою пам'яті.Апаратна підтримка відео - C5510 , C5509 Три блоки апаратної підтримки відео , підтримувані сімейством C55x включають : Пряме / зворотне дискретне косинусное перетворення ( DCT ) інтерполяція пікселів Обчислення проміжних точок при русі Забезпечує високу продуктивність видеокодека , при цьому вивільняючи більше половини ресурсів ЦПУ для обробки додаткових завдань , таких , як перетворення колірних схем , завдання для користувача інтерфейсу , стек TCP / IP , обробка звуку і т.д. С- еквівалентні та викликаються з програм мовою З функції з високим ступенем оптимізації є частиною бібліотеки TMS320C55x DSP Image / Video Processing Library ( IMGLIB ) , безкоштовно доступною в TI Foundation Library .Багатоканальні буферизованная послідовні порти ( McBSP ) Високошвидкісні повнодуплексні послідовні порти: Повнодуплексна зв'язок Подвійна буферизація даних для безперервного обміну Безпосередній зв'язок з : Пристроями сімейства C5000 кодеками Фреймерамі T1/E1 MVIP -сумісними пристроями ST- BUS сумісними пристроями IOM- 2 сумісними пристроями AC97 сумісними пристроями IIS сумісними пристроями SPI ™ сумісними пристроями До 32 / 128 каналів прийому / передачі Розмір даних 8 , 12 , 16 , 20 , 24 або 32 біт Програмоване внутрішньо тактирование і формування фреймів Вбудоване апаратне стиснення і розпакування даних у форматах μ - law або A- lawБезпосередній доступ до пам'яті ( DMA) Передача даних між точками в адресному просторі без участі ЦПУ Переміщення даних з / в вбудованої пам'яті , зовнішньої пам'яті і периферійних пристроїв паралельно з роботою ЦПУ Функціонує незалежно від ЦПУ 6/12/24-канальний порт для інтерфейсу EHPI забезпечує безпосередній обмін даними між EHPI і пам'яттю (тільки в сімействі C55x ™ )8/16-бітний інтерфейс Enhanced Host Port Interface ( EHPI ). Послідовний що, здатний передавати інформацію зі швидкістю 16 Мб/с. Паралельний порт, що забезпечує керуючому процесору безпосередній доступ до пам'яті ЦСП Конфігурується режим доступу до пам'яті ЦСП - доступ тільки керуючому процесору ( Host Only Mode ( HOM )) або загальний доступ ( Shared Access Mode ( SAM )) Можливий обмін інформацією з керуючим процесором через вбудовану або зовнішню пам'ять Доступ до всієї вбудованої пам'яті ЦСП ( або доступ до частини зовнішньої пам'яті через інтерфейс DMA)Відмінні особливості : 1.2 Опис виводів І – вхід; О ‒ вихід; Z – Високий опір P ‒ додаткові; Назва сигналу Тип Призначення A15-0 І/O/Z Зовнішня шина адрес (Extrenal Bus Address). Вихідна шина, що використовується для адресування зовнішньої пам'яті і периферійних пристроїв. D15-0 І/O/Z Зовнішня шина даних (Extrenal Bus Data). Двонаправлена шина даних . C15-0 І/O/Z Зовнішня шина керування ECLKOUT1 ECLKOUT2 EMIFCLKS І/O/Z EMIF − Clock Pins. Зовнішні сигнали тактової частоти HD І/O/Z HPI паралельний порт передачі даних HPIENA І/O/Z Сигнал керування HPI HCNTL0 HCNTL0 І/O/Z Сигнал керування доступом до HPI TX O Вивід даних через UART RX I Прийняття даних через UART GPIO 15-0 I/O/Z GPIO (General Purpose Input/Output, Входи/Виходи Загального призначення) XF O/Z Вивід прапорця стану. CLKOUT1 O/Z Cигнал генератора машинного циклу CLKMD1-2 І Cигнал вибору режимів тактування 1і 2 IS O/Z Cигнал вибору пристрою вводу/виводу. ( активний при низькому рівні) RS І Cигнал скиду. ( активний при низькому рівні) XF O Вивід прапорця стану. CLKOUT1 O/Z Cигнал генератора машинного циклу CLKMD1-2 І Cигнал вибору режимів тактування 1і 2 CLKIN2 І Вивід підключення зовнішнього генератора X2/CLKIN І Вивід підключення кварцового резонатора / вхід зовнішньої синхронізації X1 O Вивід підключення кварцового резонатора CLKR І Вхід синхросигналу прийому по послідовному порту CLKX І/O/Z Вивід синхросигналу передачі по послідовному порту DR І Вхід даних послідовного порту DX O/Z Вихід даних послідовного порту FSR І Cигнал cтарт-імпульсу прийому по послідовному порту FSX І/O/Z Cигнал cтарт-імпульсу передачі по послідовному порту TCK І Вхід сигналу тактової синхронізації операцій тестової логіки(Test Clock). Асинхронні такти для сканування границь JTAG. TIM0 I/O/Z Вхідний/вихідний сигнал нульового таймера TIM1 I/O/Z Вхідний/вихідний сигнал першого таймера TMS І Вибір тестового режиму(Test Mode Select). Використовується для контролю тестовим кінцевим автоматом. TDI І Вхід тестових даних(Test Data Input). Забезпечує послідовні дані на пристрій JTAG сканування. TDO O/Z Вихід тестових даних(Test Data Output). Забезпечує видачу послідовних даних при скануванні JTAG. RESET І Тестовий скид(Test Reset). Сигнал початкової установки вузла сканування. EMU0 O Стан емуляції(Emulation Status). Задає стан процесу емуляції. МP/MC I Вибір режиму мікропроцесор/мікрокомп'ютер DVDD P Живлення. VSS P Земля 1.3. Опис алгоритму ШПФ з прорідженням у часі Дискретним перетворенням Фур'є над вихідною послідовністю чисел {x0, x1, …, xn-1} потужністю n є N, n> 1, де xi є Z, i = (0, n-1), наз. таке перетворення, в результаті якого виходить послідовність {x’0, x’1 , ..., xn-1} комплексних чисел xk тієї ж потужності, кожен елемент якої рахується за правилом: / де k = (0, n-1), W = e-j*π/n і де j – уявна частина Існують такі Wik, в яких (ik) рівні. Неважко помітити, що для виконання n-точкового перетворення Фур'є необхідно виконати n (n–1) комплексних додавань та (n–1) (n–1) комплексних множень (з урахуванням, що W0 = 1 ). При цьому множник Wik буде використаний стільки разів, скільки дільників з діапазону (0, n-1) у показника степеня (ik). Маємо: / Оскільки sin α = – sin (α + π), cos α = – cos (α + π), то: / (1) Звідки випливає, що: / (2) Таким чином, діапазон ступенів (ik) за допомогою формули (1) скорочується з (0, (n–1) (n–1) ), до (0, n-1), а за допомогою формули (2) – до (0, n/2–1). Нехай n - довжина вихідної послідовності чисел {x0,x1,…,xn-1} парна, тоді перетворення Фур’є для такої послідовності можна записати у вигляді: / (3) З урахуванням формули (1), а також виразу / формулу (3) часто записують у вигляді: / (4) Розглянемо першу суму формули (3). Поклавши n/2 = m, отримаємо: 1) n = 2m; 2) /; 3) /. Аналогічні міркування можна провести і відносно другої суми формули (3). Таким чином, ДПФ вихідної послідовності розмірністю n=2m зводиться до двох ДПФ послідовностей розмірністю m чисел кожна, складених з парних і не парних елементів вихідної послідовності. 1. 2. 1. Швидке перетворення Фур'є (ШПФ) Формули (3) і (4) є основою для побудови алгоритму швидкого перетворення Фур'є (ШПФ). Цей алгоритм за рахунок рекурсивного застосування формули (3) зводить ДПФ вихідної послідовності розмірності n = 2l , де l є N, до набору 2-точкових перетворень Фур’є. Отже маємо: / Помножимо x-k на Wn-jk і просумуємо по k = 0 ... (n–1) / 1. 2. 2. Двійково-інверсна перестановка Наведемо у вигляді графа алгоритм ШПФ із проріджуванням за часом заснований на розбитті - об'єднанні при N=8. / Рис. 2. Граф алгоритму ШПФ з проріджуванням за часом при N = 8 На першому етапі відліки вхідного сигналу переставляються місцями і вихідна послідовність ділиться на “парну” і “непарну” (позначені червоними і синіми стрілками). Потім “парна” і “непарна” послідовності у свою чергу діляться на «парну» і «непарну» послідовності. При N=2Lтакий розподіл можна робити L-1 разів. У цьому випадку L=3. Дана процедура називається двійково-інверсною перестановкою, так можна виконати перенумерацію відліків переписавши номер відліку в двійковій системі у зворотному напрямку. Наприклад s(4) має індекс у десятковій системі числення 410 = 1002, Якщо ж 1002переписати справа наліво то отримаємо 0012 , Тобто s(4) після розбиття на парні непарні перед першою операцією «Метелик» стане на місце s(1), яка в свою чергу стане на місце s(4). За аналогічним правилом поміняються місцями всі відліки, при цьому деякі залишаться на місці, зокрема s(2), бо якщо 210 = 0102 переписати справа наліво то все одно залишиться 0102, Аналогічно s(0), s(5) і s(7). Дуже важливо зрозуміти, що даний метод перенумерації повинен застосовуватися при запису числа в двійковій системі, яка складається з L розрядів. У наведеному прикладі використовувалися 3 розряди двійкового числа, але якщо ж L =4 ( N=16), то необхідно записати число при використанні 4 розрядів. У цьому випадку 210=00102 і після переписування отримаємо 01002 , Тобто при N=16 s(2) не залишиться на місці, а поміняється місцями з s(4). Можна сказати що безпосередньо двійково-інверсна перестановка зручна коли наперед кількість відліків вхідного сигналу фіксована, проте в універсальних алгоритмах ШПФ на різні розміри /, Двійково-інверсна перестановка не ефективна, простіше і швидше поміняти відліки місцями. Після двійково-інверсної перестановки отримуємо чотири 2-точкових ДПФ: / (5) На основі чотирьох 2-точкових ДПФ формуються два 4-точкових ДПФ: / (6) І на останньому рівні формується повний спектр вхідного сигналу. 1. 2. 2. Обчислювальна ефективність алгоритму ШПФ з проріджуванням за часом Алгоритм з проріджуванням за часом на кожному рівні вимагає N комплексних множень і додавань. При N = 2L кількість рівнів розкладання - об'єднання рівно L, Таким чином загальна кількість операцій множення і додавання дорівнює L*N. Розглянемо у скільки разів алгоритм ШПФ із проріджуванням за часом ефективніше ДПФ. Для цього розглянемо коефіцієнт прискорення K відношення кількості комплексних множень і додавань при використанні ДПФ і БПФ, при цьому врахуємо що L=log2(N): /разів. (9) У таблиці 1 наведено необхідну кількість операцій Mоп для алгоритму ДПФ при різному N=2Lі при використанні ШПФ із проріджуванням за часом. Таблиця 1. Порівняння кількості операцій. L 4 6 8 10 12 N 16 64 256 1024 4096 Mоп ДПФ 256 4096 65536 1048576 16777216 Mоп ШПФ 64 384 2048 10240 49152 K, Раз 4 10,7 32 102,4 341 З таблиці 1 добре видно, що використання ШПФ призводить до суттєвого зменшення необхідної кількості обчислювальних операцій. Так наприклад при N = 1024 ШПФ вимагає в 100 разів менше операцій ніж ДПФ, а при N = 4096 у 341 разів! При цьому дуже важливо, що виграш у продуктивності тим більше, чим більше розмір вибірки N. Так, наприклад при N=216виграш складе 216 /16 = 212 = 4096 разів. 2. Розрахунковий розділ 2. 1. Розрахунок часу виконання Для розрахунку часу виконання алгоритму ШПФ на процесорі TMS320VC5501 потрібно визначити кількість операцій додавання, множення та читання/запису з/до пам’яті однієї операції «метелик». На рис. 5 наведено базову операцію “метелик” ШПФ за основою 2 з прорідженням по часу. Рис. 5. Метелик ШПФ за основою 2 з прорідженням по часу Формули обчислення метелика: X’1 = X1 + X2*W X’2 = X1 – X2*W Розклад формул для обчислення метелика на дійсну та уявну частину: X’1 = ( ReX1 + jImX1 ) + ( ReX2 + jImX2 ) X’2 = ( ReX1 + jImX1 ) – ( ReX2 + jImX2 ) * ( ReW – jImW ) W = e-j(2πnk/N) = cos ( 2

Курсовий проект Методи, алгоритми та засоби цифрової обробки сигналів та зображень

urasik1703

26.10.2014 22:02

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись