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

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Кафедра ЕОМ

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

Рік:

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:10-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись