Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка алгоритму ШПФ на ПЛІС.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2005
Тип роботи:
Курсова робота
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
кафедра ЕОМ
Курсовий проект
з курсу:
“Методи алгоритми і засоби цифрової обробки сигналів та зображень”
Тема: “Розробка алгоритму ШПФ на ПЛІС”
Виконав:
студент групи _____
____________
Перевірив:
Львів – 2005
Завдання до курсового проекту.
Розробити та синтезувати на ПЛІС пристрій для обчислення 16-ти точкового ШПФ за основою 2 та прорідженням за частотою. Сформувати набір тестових послідовностей та засобами пакету Active HDL провести функціональну симуляцію пристрою.
Анотація.
В даній роботі описується один із алгоритів ШПФ (FFT), а саме 16-ти точкове ШПФ за основою 2 та прорідженням за частотою. Будується граф обчислення ШПФ та на його основі алгоритм описується мовою VHDL. Далі виконуєьтся синтез проекту на ПЛІС (FPGA) та оцінка отриманих результатів.
Зміст
Вступ ____________________________________5
Аналітичний огляд _________________________6
1.1. Алгоритм ШПФ з основою 2___________________6
1.2. Обчислення повертаючих множників____________7
1.3. Модифікований граф ШПФ____________________9
1.4. Біт інверсний порядок видачі даних____________10
1.5. Проекція графу ШПФ на вертикальну площину__10
Розробка пристрою на VHDL____________________12
2.1. Інтерфейс пристрою__________________________12
2.2. Структурна схема____________________________12
2.3. Формат вхідних та вихідних даних______________12
2.4. Двохточкові ШПФ____________________________14
2.5. Комутаційна мережа__________________________14
2.6. Вибір кількості та об’єму ПЗП__________________15
2.7. Керуючий пристрій___________________________16
Тестування____________________________________ 18
Висновки______________________________________ 34
Література _______________________________________ 35
Вступ
При обробці сигналів у багатьох випадках доводиться виміряти спектри. Так, в задачах розпізнавання мови спектральний аналіз, як правило, передує подальшій спеціальній обробці. В системах стиснення смуги мовних сигналів спектральний аналіз є звичайно основною операцією. В гідроакустичних системах для виявлення надводних кораблів і підводних човнів вимагається проводити складний спектральний аналіз. В системах радіолокацій для отримання інформації про швидкість мети також доводиться виміряти спектр.
Слід мати на увазі, що поняття «спектральний аналіз» включає велике число різних вимірювань. В широкому значенні його можна визначити як вимірювання, яке дає точні або наближені значення z-перетворення дискретного сигналу для заданих значень z». Створення адекватної теорії спектрального аналізу утруднено тією обставиною, що на практиці всі спектральні вимірювання проводяться на кінцевих тимчасових інтервалах, довжина яких звичайно визначається інтуїтивно або на основі накопиченого досвіду. Наприклад, «спектр» мовного сигналу дуже сильно залежить від часу, змінюючись приблизно із швидкістю зміни параметрів мовного тракту (біля 10раз за секунду). Не дивлячись на це, в багатьох прикладних задачах короткочасний спектр мовного сигналу є однією з найважливіших характеристик.
Набір алгоритмів, званих алгоритмами швидкого перетворення Фурьє (ШПФ), включає різноманітні методи зменшення часу обчислення дискретного перетворення Фурьє (ДПФ). Оскільки обчислення ДПФ є основною операцією в більшості задач спектрального аналізу, то використовування ШПФ в деяких що зустрічаються на практиці випадках, дозволяє прискорити обчислення ДПФ в 100 і більш раз в порівнянні з методом прямого обчислення ДПФ, має надзвичайно важливе значення і повинне розглядатися як невід'ємна частина застосування методів цифрової обробки сигналів для спектрального аналізу.
Той факт, що одновимірний масив чисел можна виразити через двовимірний масив більш ніж одним способом, пояснює різноманіття алгоритмів ШПФ. Звідси витікає, що математична операція переходу з одновимірного простору в двовимірний є основою всіх алгоритмів ШПФ. При такому єдиному підході до алгоритму ШПФ його різні варіанти можуть бути отриманий порівняно простим способом.
1.Аналітичний огляд.
1.1. Алгоритм ШПФ з основою 2
Якщо число N є степенем 2, то його можна записати як (N/2) х 2; аналогічно N/2 = (M/4) X2 і т.д. В результаті елементи початкового одновимірного масиву можна розположити таким чином, щоб елементарними операціями були двохточкові ШПФ. Простий приклад для N = 16 показаний на рис.1.1.
Рис.1.1. 16-точкове EMBED Visio.Drawing.6
з основою 2 з проріджуванням по частоті.
При побудові графу N-точкового ШПФ за основою 2 слід виконати ряд обчислень для визначення кількості ярусів графу та кількості метеликів на кожному ярусі.
А саме: кількість ярусів = Log2N, оскільки в нас N=16, то Log216 = 4;
Кількість метеликів = N/2 = 16/2= 8
Після виконання даних розрахунків будуємо граф зображений на рис. 1.1.
Таким чином, на рис.1.1 кружки представляють двохточкові ШПФ, а множення на повертаючі множники зображені стрілками. Елементи пам'яті також представлені крапками і пронумеровані зверху вниз, причому номери регістрів не приводяться. Можливі варіанти ШПФ з основою 2 з проріджуванням по частоті і за часом. Перший варіант представлений на рис. 1.1. Щоб зрозуміти, яким чином в цьому алгоритмі здійснюється проріджування, вважатимемо, що перші 8 відліків утворюють перший рядок матриці з 8 стовпців і 2 рядків, наступні 8 відліків складають другий рядок.
На першому етапі алгоритму рис.1.1 виконуються 8 двохточкові ДПФ від елементів кожного стовпця. Потім проводяться повороти, причому показники експонент повертаючих множників вказані перед позначенням елементів пам'яті другого етапу. Потім всі рядки проріджуються шляхом формування з них матриць розміром (4 X 2) і перетворяться по схемі 8-точкового БПФ з основою 2, але з іншими повертаючими множниками.
Алгоритм рис. 2.1 можна розглядати як варіант ШПФ з проріджуванням по частоті, оскільки повороти проводяться після ДПФ. Можна побудувати і алгоритм з проріджуванням за часом, але для цього доведеться переходити від матриць меншого розміру до більших матриць.
Алгоритм базової операції ШПФ з основою 2 і проріджуванням за частотою можна представити у вигляді :
EMBED Visio.Drawing.6
де X,Y — результати базової операції; А, B — вхідні відліки; WN— комплексні коефіцієнти;
1.2. Обчислення повертаючих множників WN
Для виконання кожної базової операції на метелик необхідно подати поворотний коефіцієнт Wp, де W==e-2jπ/N при прямому БПФ і W=e2jπ/N при зворотному БПФ. Для алгоритму БПФ з прорідженням за часом значення р пов'язані з номерами відліків п, беруть участь у виконанні базової операції на j-й ітерації, наступним співвідношенням:
EMBED Equation.3
де j=1 ..., r-1 - номер поворотного коефіцієнта, що бере участь в базовій операції; ki - розряди r-ого кода номерів операндів.
Наприклад, для N=64 і r=2 на 1-й ітерації значення р(1) для всіх груп відліків рівне 0, на 2-й ітерації р(1}=k524= =k5N/4, т. д.
EMBED Equation.3
На третій ітерації
EMBED Equation.3
і т д.
Використовуючи даний підхід здійснюємо обчислення певертаючих множників для 16-ти точкового ШПФ за основою 2 з прорідженням по частоті. Відмінністю буде лише те, що при прорідженні по частоті змінюється порядок слідування коефіцієнтів на різних ітераціях, тобто на першій ітерації:
EMBED Equation.3
На другій ітерації:
EMBED Equation.3
На третій ітерації:
EMBED Equation.3
На четвертій ітерації
EMBED Equation.3
1.3. Модифікований граф ШПФ
Оскільки при реалізації апаратно графу ШПФ виникають незручності при неспівпадінні адрес комірок з яких потрібно брати елементи на кожному ярусі, то від графу зображеного на рис.1.1. можна перейти до графу зображеного на рис.1.2.
EMBED Visio.Drawing.6
Рис.1.2. Модифікований граф 16-ти точкового ШПФ за основою 2 з прорідженням за частотою.
На рисунку видно, що для кожної базової операції на будь-якому ярусі дані беруться і записуються за тими самими адресами що і на попередньму ярусі.
Точки і метелики пронумеровані у відповідності до графу на рис.2.1 для того щоб простіше було наглядно відслідкувати потік даних і переконатись, що він не перекручений та повністю відповідає алгоритму ШПФ комірки пам’яті пронумеровані у відповідності до нумерації на рис.1.1. Змінюється і порядок слідування повертаючих множників, що зображено на рисунку. При такій побудові графу значно простіше побудувати проекцію графу на вертикальну площину і далі її перевести в схему.
1.4. Біт інверсний порядок видачі даних та проекція графу.
Наступним моментом є те, що на вході графу при прорідженні за частотою ми маємо прямий порядок слідування даних, а на виході отримуємо двійково- інверсний. Отже при видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в таблиці 1.
Таб.1 Двійково-інверсна перестановка даних
Після опису роботи алгоритму можна перейти до його реалізації. На рис. 1.3 зображено проекцію графа ШПФ на вертикальну площину. В результаті його реалізації буде отримано ітераційний пристрій де на кожній ітерації обчислюватиметься один ярус потокового графу ШПФ.
1.5 Проекція потокового графу ШПФ на вертикальну площину.
EMBED Visio.Drawing.6
Рис. 1.3. Спрощена проекція графу на вертикальну площину.
На рисунку використані такі позначення:
Memory array – масив елементів пам'яті для зберігання проміжних результатів обробки
MUX – вхідні мультиплексори для запису вхідних даних на першому циклі роботи пристрою
F1,F2,…,F8 – вузли обробки (двохточкові ШПФ)
На даному рисунку не показано повертаючих множників та виходів пристрою, він ілюструє лише потік даних при обробці.
2. Розробка
Для реалізації пристрою описаного рисунком 1.3. використовуєьтся наступна структура.
EMBED Visio.Drawing.6
2.1 Інтерфейс пристрою
Пристрій має 16 паралельних вхідних портів для прийому даних та два вхідні порти для отримання керуючих сигналів – це сигнали RST (Reset – початковий скид) та CLK(Clock – синхронізація). Результати обробки вхідних даних видаються по 16-х паралельних вихідних портах. Всі порти, крім RST i CLK є 32-х розрядні.
2.2. Спрощена структурна схема пристрою.
Структура пристрою зображена на рис. 2.1. Дані надходять по 16-ти паралельних портах і проходячи через мультиплексори записуються у відповідні регістри. Мультиплексорами управляє керуючий автомат (Control Unit) по лінії SEL. При SEL = 0, в регістри записуються вхідні дані, при SEL = 1 – проміжні дані. Далі дані з регістрів поступають на входи двохточкових ШПФ де обробляються у відповідності до базової операції ШПФ і на наступному циклі знову записуються до відповідних регістрів. На останньому циклі дані записуються в регістри і подаються на вихідні порти відповідно до табл.1 при встановленому сигналі oen, який генерується куруючим пристроєм.
В ПЗП (ROM) зберігаються повертаючі множники, які є константами і подаються на двохточкові ШПФ через комутуючу мережу. Роботою комутуючої мережі (Comunication Network) управляє керуючий пристрій по лініях DC[3:0].
Далі буде детальніше розглянуто кожний з основних вузлів, на базі яких побудована структура пристрою.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора