Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка процесора ШПФ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2004
Тип роботи:
Курсовий проект
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Група:
СКС-5
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
НУ “ Львівська політехніка “
ІКТА
Кафедра ЕОМ
з дисципліни „Методи, алгоритми, засоби цифрової обробки
сигналів та зображень”
на тему:
“ Розробка процесора ШПФ”
Варіант 21
Варіант № 21
Розробити процесор ШПФ з наступними вихідними даними:
Тип процесора: ADSP-21060
Кількість точок: 256
Основа – 4
Прорідження – частотне
Вагова функція – Гауса
Розрядність вхідних даних – 32
Такт поступлення вхідних даних, нс – 20
Час обробки (мс) - 1,0
Анотація
Метою даного курсового проекту є розробка процесора швидкого перетворення Фур’є на основі високо продуктивного 32-розрядного цифрового сигнального мікропроцесора ADSP-21060. У записці детально описано алгоритм ШПФ за основою 4 з частотним прорідженням , основні характеристики мікропроцесора ADSP-21060, а також функціональна схема процесора ШПФ та програма виконання заданої функції.
Зміст
Вступ 5
1. Теоретичний розділ 6
1.1 Застосування дискретного перетворення Фур’є 6
1.2 Швидке перетворення Фур'є 6
1.3 Призначення ADSP-21060 9
1.4 Властивості ADSP-21060. 10
1.5 Опис виводів 11
2. Аналіз блок-схеми виконання ШПФ 15
3. Розрахунковий розділ 19
4. Розробка функціональної схеми 21
5. Розробка програми виконання алгоритму ШПФ 26
5.1 Основний модуль 27
5.2 Модуль ШПФ 28
5.2.1 Цикл метелика (bfly_loop) 31
5.2.2 Цикл групи (group_loop) 32
5.2.3 Цикл рівня (stage_loop) 32
Висновки 35
Література 36
Вступ
Значна частина задач аналізу тимчасових рядів пов'язана з перетворенням Фур'є і методами його ефективного обчислення. У цих задачах перетворення Фур'є відіграє важливу роль як необхідний проміжний крок у визначенні густини спектра потужності, крос-спектральної густини, передаточних функцій, згорток, кореляційних функцій, а також у задачах інтерполяції значень.
На практиці широке поширення одержали алгоритми ШПФ за основою 2 , де кожен функціональний вузол виконує базову операцію - двовходового "метелика". Ці алгоритми орієнтовані, насамперед , на зведення до мінімуму числа операцій множення. Виникає питання про реалізацію алгоритмів ШПФ із більш високими основами і їхніми можливими комбінаціями.
Послідовність обчислень будь-якого БПФ можна описати у виді графа, вузли якого виконують фактично звичайне дискретне перетворення, але з меншою розмірністю вхідних векторів (меншою основою). У залежності від вибору основи міняється як загальне число арифметичних операцій, так і кількість ярусів графа.
В алгоритмах ШПФ за основою 2 кількість таких шарів максимальна , тому при поетапному надходженні результатів обчислень від ярусу до ярусу відбувається більше нагромадження помилок округлення, ніж в алгоритмах з більш високою основою. І чим вище розмірність вектора вхідних даних, тим більша буде кількість шарів і в наслідок значніша помилка. Це особливо критично у випадках, коли обчислення проводяться в цілочисленній арифметиці (з фіксованою крапкою) чи при недостатньо широкій розрядності даних. Слід також зазначити, що в цьому випадку для запобігання переповнення проміжні результати після кожного чи після групи етапів множення (ярусів графа) необхідно додатково нормалізувати, застосовуючи операцію зсуву вправо. Нормалізація крім зсуву може містити в собі процедуру округлення, що також вносить додаткові обчислювальні витрати.
Можливим компромісним рішенням може виступати підхід, заснований на збільшенні основи в алгоритмах ШПФ. Далі розглядається варіант ШПФ-256 за основою 4. Вибір такої основи дозволяє знизити кількість ярусів графа .
1. Теоретичний розділ
1.1 Застосування дискретного перетворення Фур’є
Цифровий спектральний аналіз
Аналізатори спектра
Обробка мови
Обробка зображень
Розпізнавання образів
Проектування фільтрів
Обчислення імпульсної характеристики по частотній
Обчислення частотної характеристики по імпульсній
Швидке перетворення Фур'є (БПФ) - це простий алгоритм для ефективного обчислення дискретного перетворення Фур'є (ДПФ)
Аналіз Фур'є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур'є дозволяє зіставити сигналу, заданому в тимчасовій області, його еквівалентне представлення в частотній області. І навпаки, якщо відома частотна характеристика сигналу, то зворотнє перетворення Фур'є дозволяє визначити відповідний сигнал у тимчасовій області. На додаток до частотного аналізу, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур'є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур'є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою ідентичні дискретній імпульсній реакції фільтра.
1.2 Швидке перетворення Фур'є
Вихідними даними для ШПФ є елементи обмеженої послідовності x(n), де n=0,1,.. N-1. Відповідно дискретне перетворення Фур'є має вид:
(1)
(2)
де - повертаючий множник , причому є періодичною послідовністю з періодом N, оскільки , де m - ціле. Безпосереднє обчислення ДПФ (1) для визначення комплексних значень F(k) вимагає для кожного значення k (N-1) множень і (N-1) додавань комплексних чисел чи 4(N-1) множень і 2(N-1) додавань дійсних чисел, а для всіх N значень k=0, 1, ..., N-1 потрібно приблизно N2 множень і N2 додавань комплексних чисел. Таким чином, для великих значень N (порядку декількох сотень) пряме обчислення ДПФ вимагає дуже великого числа арифметичних операцій множення і додавання, що утрудняє реалізацію обчислень у реальному часі.
Швидким перетворенням Фур'є (ШПФ) називають набір алгоритмів, реалізація яких приводить до істотного зменшення обчислювальної складності ДПФ (1).
Алгоритм ШПФ за основою 4 із проріджуванням по частоті полягає в розбивці вихідної послідовності x(n), де n=0,1,.. N-1 на чотири послідовності, кожна з яких містить відповідно перші, другі, треті та останні N/4 відліків. При цьому ДПФ можна записати у вигляді:
Оскільки
то
Замість k підставимо наступні значення k = 4r, k = 4r + 1, k = 4r + 2, k = 4r + 3. Отже отримаємо
Рис.1.1 Операція „метелик” в алгоритмі ШПФ з прорідженням по частоті
Для дійсної та уявної частини маємо наступні вирази.
Рис.1.2 Операція „метелик” в алгоритмі ШПФ з прорідженням
по частоті (комплексні числа)
1.3 Призначення ADSP-21060
ADSP-21060 SHARC – комп’ютер із супер гарвардською архітектурою , що є високо продуктивним 32-розрядним цифровим сигнальним процесором для обробки прикладних програм мови, звуку, графіки і растрових зображень. SHARC є системою на кристалі, оскільки базується на ядрі сімейства ADSP-21000, додаючи двопортову пам’ять на кристалі SRAM, інтегровані зовнішні пристрої вводу-виводу з підтримкою розподілених шин вводу-виводу. Завдяки кешу інструкцій процесор може виконувати майже кожну команду в одному циклі. Чотири незалежних шини для даних, команд та шин вводу-виводу плюс перехресні переключення між зв’язками пам'яті – все це включає супер гарвардська архітектура ADSP-21060.
ADSP-21060 SHARC представляє собою новий стандарт інтегрування для цифрових сигнальних процесорів, комбінуючи високо ефективне з плаваючою крапкою ядро DSP з вбудованим інтерфейсом хост-процесора ,контролером прямого доступу до пам’яті, послідовними портами,link- портами, та із загальнодоступними шинами в багатопроцесорному режимі.
1.4 Властивості ADSP-21060.
Чотири незалежних шини для вибірки даних, інструкції, і шини вводу-виводу
32 бітні з рухомою комою обчислювальні блоки стандарту ІЕЕЕ -- вузол множення, ALU, та зсувач
Двопортова SRAM на кристалі та вбудований процесор вводу – виводу для периферії – складають System-оn-а-сhіp
Вбудовані засоби мультиобробки
40 MІPS, 25 ns цикл виконання інструкцій, кожна інструкція виконується за один цикл
80 MFLOPS – постійна продуктивність двох генераторів адреси та даних з частково-зворотнім адресуванням
Ефективний програмований засіб Sequencіng з нульовим-переповнюючим циклом
ІEEE JTAG Стандарт 1149.1 тестових портів доступу та емуляції на кристалі
32-бітний з фіксованою точністю та 40-бітний з розширюваною точністю ІEEE формати даних з рухомою комою,і 32 розрядний формат даних з фіксованою крапкою
Одноциклові операції множення і арифметико-логічні виконуються паралельно із вибіркою даних чи інструкцій з пам’яті
Двопортова 4Мbit SRAM є доступною як ядра процесора, так і для DMA
4 Gіgawords зовнішня пам’ять підтримує сторінковий режим доступу
ADSP-21060 – процесор з модифікованою гарвардською архітектурою, що містить 4Мбітну SRAM на кристалі, яка складається з двох блоків по 2 Mбіти кожен, і яка може бути сконфігурована для зберігання різних комбінацій інструкцій і даних. Подвійний доступ (тобто в один момент часу може відбуватися операція запису і читання) до кожного блоку пам'яті відбувається в єдиному циклі ядром процесора, процесором вводу/виводу чи контролером DMA.
В ADSP-21060 пам'ять може бути сконфігурована максимум з 128Кслів по 32-біти , з 256Кслів по 16-бітів для даних, та 80Кслів по 48-біт для інструкцій (чи 40-бітові дані), чи з різних комбінацій довжин слів, які поміщаються у 4Мбіти. Але до пам'яті можна звертатися лише по 16-, 32-, чи 48бітних шинах.
У режимі multiprocessing дозволяється підключення шістьох процесорів ADSP-21060 і паралельне їх функціонування. Єдиний адресний простір дозволяє прямі міжпроцесорні доступи до внутрішньої пам'яті кожного ADSP-21060. Розподілена логіка арбітражу шини керує даним режимом і розподіляє ресурси процесорів між собою. Арбітраж надає шині вибраний чи встановлений пріоритет. Максимальна швидкодія при міжпроцесорній передачі даних складає 240 Mbytes/s по link-портах чи по зовнішньому порту.
1.5 Опис виводів
Сигнал може бути:
A -- асинхронний
G – земля
І -- вхід
O -- вихід
P -- електроживлення
S -- синхронний
(A/D) – активний управляючий
(O/D) -- з відкритим стоком (open drain)
T -- з третім станом
Таблиця 1. 1 Опис виводів
Назва сигналу
Тип
Призначення
ADDR 31-0
І/O/T
Зовнішня шина адрес(Extrenal Bus Address).Вихідна шина, що використовується для адресування зовнішньої пам'яті і периферійних пристроїв. В мультипроцесорній системі для одного процесора використовується при адресуванні в операціях читання/запису до внутрішньої пам'яті чи регістра ІOP іншого ADSP-21060.
DATA 47-0
І/O/T
Зовнішня шина даних(Extrenal Bus Data). Двонаправлена шина даних та інструкцій. 32-бітні дані одинарної точності з рухомою комою і 32-бітові дані з фіксованою крапкою передаються лише по частині (47 - 16 ) шини, 40-бітові дані з розширюваною точністю з рухомою комою – 47 - 8, короткі 16 бітні дані – 31 – 16, в режимі ЕPROM завантаження 8-бітові дані – 23 - 16. Використання навантажуючого резистора на вході не обов’язкове.
MS 3-0
O/T
Лінії вибору пам’яті(Memory Select Lines). Сигнал на цих лініях виставляється(низький рівень) для вибору кристала для необхідного банку зовнішньої пам’яті. Розмір банку пам'яті повинен бути визначений у регістрі контролю системи (SYSCON). Це є лінії декодованої адреси пам’яті, стан яких змінюється у той самий час, як і на інших лініях адреси. Коли доступ до зовнішньої пам'яті не використовується, MS 3-0 - лінії перебувають у третьому стані; вони є активними, коли виконується умовна інструкція доступу до пам'яті ,незалежно від результату. MS 0 може використовуватися із сигналом PAGE для реалізації банку DRAM (банк 0). У багатопроцесорних системах сигнал встановлюється ведучим процесором.
RD
І/O/T
Строб читання пам’яті(Memory Read Strobe). Виставляється (низький рівень) , коли процесор читає із зовнішньої пам’яті або внутрішньої пам’яті іншого процесора (багатопроцесорний режим) та при звертанні зовнішніх пристроїв до внутрішньої пам’яті процесора в режимі читання. У багатопроцесорних системах сигнал встановлюється ведучим процесором.
WR
І/O/T
Строб запису до пам’яті(Memory Wrte Strobe). Встановлюється (низький рівень) , коли процесор виконує запис у зовнішню пам’ять або внутрішню пам’ять іншого процесора (багатопроцесорний режим) та при звертанні зовнішніх пристроїв до внутрішньої пам’яті процесора в режимі запису. У багатопроцесорних системах сигнал встановлюється ведучим процесором.
PAGE
O/T
Межа сторінки DRAM(DRAM Page Boundarу). Встановлюється при перетині межі сторінки у зовнішній динамічній пам’яті. Розмір цієї сторінки має бути визначений у контрольному регістрі WAIT. DRAM може бути реалізована лише у банку 0 зовнішньої пам’яті, тому даний сигнал використовується лише до цього банку. У багатопроцесорних системах сигнал встановлюється ведучим процесором.
ADRCLK
O/T
Вихід опорного сигналу тактової синхронізації(Clock Output Referense). У багатопроцесорних системах сигнал встановлюється ведучим процесором.
SW
І/O/T
Вибір синхронізованого запису(Sуnchronous Write Select). Використовується для синхронної взаємодії ADSP-21060 з пристроями пам’яті. Процесор встановлює сигнал(низький рівень), щоб забезпечити попереднє вказання того, що незабаром буде виконаний запис, який може і не відбутися, якщо пізніше не буде встановлений сигнал. Має бути стверджений у той самий момент часу, що і вихідна адреса. У багатопроцесорних системах сигнал встановлюється ведучим процесором. Цей сигнал вказує на тип звертання в простір зовнішньої пам’яті в багатопроцесорній системі. Виставляється, коли виводиться адреса.
ACK
І/O/S
Підтвердження доступу до пам’яті(Memory Acknowledge). Скидається зовнішніми пристроями у низький рівень, що забезпечує додавання додаткових циклів очікування при доступі до зовнішньої пам’яті. Використовується пристроями вводу/виводу, контролерами пам’яті та іншою периферією для продовження доступу до зовнішньої пам’яті.
SBTS
І/S
Перевід шини у третій стан(Suspent Bus Three-State). Зовнішні пристрої можуть встановити даний сигнал у низький рівень для переводу зовнішніх шин адреси і даних, ліній вибору пам’яті і стробів у стан з високим опором на час наступного циклу. Якщо процесор звертається до зовнішньої пам’яті доки цей сигнал встановлений (низький рівень), то таке звертання не буде закінчене до того часу, доки сигнал не буде перетверджений. Може використовуватися лише для виходу із стану взаємного блокування хост процесора і ADSP-21060 або при використанні контролера DRAM.
IRQ2-0
І/A
Лінії запиту переривань(Interrupt Request Lines). Можуть спрацьовувати по фронту чи по рівню.
FLAG3-0
І/O/A
Виводи прапорців(Flag Pins). Двонаправлені лінії: як вхідні сигнали використовуються як умова виконання певної операції, як вихідні – сигнали, що поступають на периферійні пристрої.
TIMEXP
O
Лічильник таймера пустий(Timer Expired). Рівний „1” напротязі чотирьох циклів після зменшення вмістимого регістру TCOUNT до 0 при включеному таймері.
HBR
І/A
Запит шини хост-процесором (Host Bus Request). Встановлюється хост процесором для захоплення зовнішньої шини.
HBG
І/O
Передача шини хост-процесору (Host Bus Grant). Відповідь на попередній запит, яка дозволяю захоплення хост процесором зовнішньої шини.
CS
І/A
Вибір кристалу(Chip Select). Стверджується хост процесором для вибору ADSP-21060.
REDY(O/D)
O
Підтвердження управління шиною хост-процесору (Host Bus Acknowledge). ADSP-21060 скидає даний сигнал (низький рівень) для додавання циклів очікування при асинхронному доступі хост процесором до внутрішньої пам’яті чи розміщених у пам’яті регістрів вводу/виводу. По замовчуванню використовується як вихід з відкритим стоком; стан активного управляючого виходу програмується бітом ADREDY в регістрі SYSCON.
DMAR1
І/A
DMA Request 1. Запит 1 DMA контролера, що використовується каналом 7.
DMAR2
І/A
DMA Request 2. Запит 2 DMA контролера, що використовується каналом 8.
DMAG1
O/T
DMA Grant 1. Сигнал підтвердження на DMAR1.
DMAG2
O/T
DMA Grant 2. Сигнал підтвердження на DMAR2.
BR6-1
І/O/S
Запит шини в багатопроцесорній системі(Multiprcessing Bus Request). Використовується при багатопроцесорному режимі для арбітражу зовнішньої шини.
ID2-0
І
Багатопроцесорний ідентифікатор(Multiprocessing ID). Визначає, який сигнал запиту шини BR1-6 використовується конкретним ADSP. Ці лінії визначають конфігурацію системи, тому апаратно управляються чи змінюються лише при скиді.
RPBA
І/S
Rotating Priority Bus Arbitration Select. Встановлює кругову пріоритетність при арбітражі зовнішньої шини для багатопроцесорного режиму. Коли RPBA рівний 0 – фіксовану пріоритетність.
CPA(O/D)
І/O
Пріоритетний доступ ядра(Core Priority Access). Дозволяє ядру ведучого просесора перервати фонові передачі DMA та отримати доступ до зовнішньо шини. Використовується при багатопроцесорному режимі.
DTx
O
Передача даних(Data Transmit). Використовується послідовними портами для передачі даних.
RDx
І
Приймання даних(Data Receive). Використовується послідовними портами для приймання даних.
TCLKx
І/O
Тактова синхронізація передачі(Transmit Clock). Тактова частота передачі даних послідовними портами.
RCLKx
І/O
Тактова синхронізація приймання(Receive Clock). Тактова частота приймання даних послідовними портами.
TFSx
І/O
Кадрова синхронізація передачі(Transmit Frame Sync). Використовується послідовними портами.
RFSx
І/O
Кадрова синхронізація приймання(Receive Frame Sync). Використовується послідовними портами.
LxDTA3-0
І/O
Дані link-порта(Link Port Data). Використовується link-портами.
LxCLK
І/O
Тактова синхронізація link-порта(Link Port Clock). Використовується link-портами.
LxACK
І/O
Підтвердження зв’язку через link-порти(Link Port Acknowledge). Використовується link-портами.
EBOOT
І
Вибір початкового завантаження з EPROM(EPROM Boot Select). Дозвіл режиму EPROM при початковій ініціалізації.
LBOOT
І
Вибір початкового завантаження через link-порт(Link Boot). Дозвіл режиму link при початковій ініціалізації.
BMS
І/O/T
Вибір пам’яті для початкового завантаження (Boot Memory Select). Вихід – як сигнал chip select пристрою EPROM. Вхід – при низькому рівні, визначає, що не відбувається жодного режиму початкового завантаження (“no booting”) і вибираються інструкції із зовнішньої пам’яті. Цей сигнал визначає конфігурацію системи, тому апаратно управляється чи змінюється лише при скиді.
CLKIN
І
Вхід тактової синхронізації(Clock In). Вхідний тактовий сигнал від зовнішнього тактового генератора. Цикл виконання інструкції рівний даному сигналу. Сигнал на вході CLKIN не може зупинятися чи змінюватися, а його частота не може бути нижчою за встановлене мінімальне значення.
RESET
І/A
Скид процесора(Processor Reset). Сигнал початкового установки. Після подачі даного сигналу на ядро процесора починається вибір першого слова команди із заданої комірки пам’яті по певній адресі.
TCK
І
Вхід сигналу тактової синхронізації операцій тестової логіки(Test Clock). Асинхронні такти для сканування границь JTAG.
TMS
І/S
Вибір тестового режиму(Test Mode Select). Використовується для контролю тестовим кінцевим автоматом.
TDI
І/S
Вхід тестових даних(Test Data Input). Забезпечує послідовні дані на пристрій JTAG сканування.
TDO
O
Вихід тестових даних(Test Data Output). Забезпечує видачу послідовних даних при скануванні JTAG.
TRST
І/A
Тестовий скид(Test Reset). Сигнал початкової установки вузла сканування.
EMU(O/D)
O
Стан емуляції(Emulation Status). Задає стан процесу емуляції.
ICSA
O
Зарезервований.
VDD
P
Power Supply. Джерело живлення.
GND
G
Power Supply Return. Земля.
NC
Не під’єднано.
2. Аналіз блок-схеми виконання ШПФ
Для реалізації ШПФ з прорідженням по частоті 256-точкове ШПФ розділяють на чотири 64-точкові ШПФ, далі на шістнадцять 16-точкових ШПФ, і врешті на 32 4 – точкових ШПФ (див. Рис.3). Для обрахунку 4 – точкового ШПФ використовуються формули „метелика”.
Отже, в результаті для виконання 256-точкове ШПФ необхідно чотири ітерації. При чому, після того, як закінчується обчислення першої ітерації, немає необхідності зберігати які-небудь попередні результати. Результати обчислення першої ітерації можуть бути збережені в тих же регістрах чи комірках пам'яті, що спочатку зберігалися вхідні дані. Так само, коли закінчується обчислення другого каскаду, результати обчислення першого каскаду можуть бути вилучені. У такий же спосіб здійснюється обчислення останнього каскаду, заміняючи в пам'яті проміжний результат обчислення попереднього каскаду.
Слід зауважити, що результат виконання ШПФ отримуємо у біт-інверсному порядку. Тому для адресів вихідних відліків необхідно застосувати біт-інверсний алгоритм. Суть даного алгоритму полягає у наступному: десятковий індекс n перетворюють в його двійковий еквівалент. Потім двійкові розряди розташовуються у зворотньому порядку і перетворюються назад у десяткове число. Приклад наведений у табл..2.1
Таблиця 2.1 Біт-інверсне прорідження
Десяткове
число
Двійковий
еквівалент
Двійкове число
з інверсією
Десятковий
еквівалент
0
000
000
0
1
001
100
4
2
010
010
2
3
011
110
6
4
100
001
1
5
101
101
5
6
110
011
3
7
111
111
7
Далі на Рис.2.1 наведена блок-схема 256-точкового ШПФ, а також на Рис.2.2 граф 64-точкового ШПФ, який деталізує виконання ШПФ.
Рис.2.1 Блок-схема 256-точкового ШПФ
Рис.2.2 Граф 64-точкового ШПФ
У табл.2.2 наведені групи відліків, що беруть участь в базових операціях при виконанні алгоритму ШПФ з N=256 та основою 4. Номери відліків представляються десятковими кодами Порядок виконання базових операцій на кожній ітерації може бути довільним.
Таблиця 2.2 Групи відліків, що беруть участь в базовій операції
при виконанні алгоритму ШПФ з N=256 і основою 4
Номер базової операції
Номер ітерації
1
2
3
4
1
0
0
0
0
64
16
4
1
128
32
8
2
192
48
12
3
2
1
1
1
4
65
17
5
5
129
33
9
6
193
49
13
7
3
2
2
2
8
66
18
6
9
130
34
10
10
194
50
14
11
4
3
3
3
12
67
19
7
13
131
35
11
14
195
51
15
15
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
61
60
204
240
240
124
220
244
241
188
236
248
242
252
252
252
243
62
61
205
241
244
125
221
245
245
189
237
249
246
253
253
253
247
63
62
206
242
248
126
222
246
249
190
238
250
250
254
254
254
251
64
63
207
243
252
127
223
247
253
191
239
251
254
255
255
255
255
3. Розрахунковий розділ
Кількість ярусів для виконання ШПФ ( N = 256) за основою r = 4 визначається наступною формулою:
Кількість метеликів на одному ярусі:
Загальна кількість метеликів для виконання ШПФ:
Для виконання 1 метелика необхідно 30 операцій додавань. Отже загальна кількість додавань становить:
Для виконання 1 метелика необхідно 12 операцій множення. Отже загальна кількість множень становить:
Для виконання 1 метелика необхідно 4 операції читання дійсної частини, 4 операції читання уявної частини, 6 операції читання вагових коефіцієнтів, 4 операції запису дійсної частини, 4 операції запису уявної частини. Отже для виконання усього ШПФ необхідна кількість операцій запису/читання становить:
Сумарна кількість операцій становить:
Час виконання 1 операції становить:
Час виконання ШПФ :
Час поступлення вхідних даних становить 20нс, із зовнішньої ОЗП необхідно зчитати 256 значень дійсної частини та 256 значень уявної частини. Отже час читання із ОЗП становить:
Оскільки час Топ + Тозп = 419840 нс є менший аніж Тдоп (Тдоп = 1 мс), то для виконання 256-точкового ШПФ достатньо одного процесора.
Рис. 3.1 Розподіл процесорного часу
Кількість вхідних даних становить 256 точок, а саме 256 значень дійсної частини та 256 значень уявної частини. Отже, для обробки вхідної послідовності необхідно ОЗП об’ємом 256 32-розрядних комірок, або ж 512 16-розрядних комірок. Процесор ADSP-21060 містить 4 Мбітну SRAM на кристалі, яка складається з двох блоків по 2 Mбіти кожен, і яка може бути сконфігурована як 256 Кслова по 16-бітів, чого буде більше ніж достатньо для обробки вхідної послідовності. Крім того необхідно зовнішнє ОЗП об’ємом 512х16 комірок, оскільки власне із зовнішньої пам’яті вхідні дані будуть зчитуватися у SRAM на кристалі.
Оскільки для реалізації 256-точкового ШПФ потрібно обчислити 256 метеликів, для кожного з яких використовується 3 вагових коефіцієнта (власне 3 значення дійсної частини та 3 значення уявної частини), то для зберігання вагових коефіцієнтів необхідно ПЗП об’ємом 256 * (3 + 3) = 1536 комірок по 16 біт.
Програма реалізації ШПФ містить приблизно 170 команд, кожна з яких 48 - розрядна, тому для зберігання програми необхідна завантажувальна пам’ять об’ємом 170 * (48/8) = 1020 комірок (8 - розрядних).
4. Розробка функціональної схеми
Функціональна схема процесора ШПФ включає наступні функціональні вузли:
Мікропроцесор ADSP-21060
Мікропроцесор згідно з програмою роботи обчислює швидке перетворення Фур’є над вхідними даними, які попередньо зчитуються із зовнішньої ОЗП. На ядро процесора поступає сигнал синхронізації (Fвх = 40 МГц), а також сигнал початкового скиду, після подачі якого починається вибір першого слова команди із заданої комірки пам’яті по певній адресі.
Завантажувальна пам’ять - 1020х8 комірок
Дана пам’ять призначена для зберігання програми роботи мікропроцесора.
Після ввімкнення живлення чи програмному скиді (встановлення у початковий стан) програма автоматично завантажується до внутрішньої пам’яті. Цей процес називається початковим завантаженням.
ADSP-21060 підтримує три режими початкового завантаження: від EPROM, хост процесора та link-портів. У даному випадку використовується EPROM-режим, при цьому використовуються 48-розрядні інструкції та канал DMA для передачі цих інструкцій до внутрішньої пам’яті. При EPROM-режимі ADSP-21060 читає дані з 8-розрядної зовнішньої EPROM.
Режим початкового завантаження вибирається відповідно до сигналів LBOOT, EBOOT, BMS:
EBOOT LBOOT BMS Booting Mode
1 0 як вихідний EPROM-режим
При EPROM-завантаженні (EBOOT=1) сигнал BMS використовується як вихідний і з’єднуючись з ЕВООТ, утворює сигнал вибору кристалу.
Зовнішня ПЗП (ROM) - 1536х16 комірок
Пам’ять призначена для зберігання вагових коефіцієнтів, які використовуються при обчисленні ШПФ.
Зовнішня ОЗП (RAM) - 512х16 комірок
Пам’ять використовується для запису вхідних даних, які поступають на обробку із зовні, і відповідно в подальшому зчитуються мікропроцесором для виконання над ними швидкого перетворення Фур’є.
Керуючий пристрій
Даний вузол призначений для управління доступом до ОЗП.
Сигнали, які надходять на пристрій керування наступні:
Із зовні
- шина даних, яка надходить із зовні
- адресна шина, яка надходить із зовні
- сигнал запису даних в ОЗП із зовні
- сигнал скиду лічильника в початкове положення
З мікропроцесора
- шина даних, яка надходить з мікропроцесора
- адресна шина, яка надходить з мікропроцесора
- сигнал читання даних з ОЗП до внутрішньої пам’яті мікропроцесора
- сигнал запису даних в ОЗП чи в регістр статусу керуючого пристрою з мікропроцесора
- сигнал вибору кристалу пам’яті
- сигнал, який задає режим роботи керуючого пристрою.
Вихідними сигналами керуючого пристрою є наступні:
- шина даних, яка надходить на ОЗП
- адресна шина, яка надходить на ОЗП
- сигнал читання даних з ОЗП
- сигнал запису даних в ОЗП
- сигнал вибору кристалу
- переривання, яке надходить на мікропроцесор
Режим роботи керуючого пристрою встановлює мікропроцесор шляхом запису необхідної інформації у регістр статусу. Структурна схема подана на Рис.4.1
Рис.4.1 Встановлення регістра статусу
Формування вихідних сигналів пристрою керування буде залежати від значень сигналів (задає напрямок передачі) та (вказує операцію : запис або читання). Далі наведені структурні схеми ля формування кожного з вихідних сигналів (шин).
Формування вихідної шини даних
Рис.4.2 Формування шини даних
Дана схема функціонує згідно з табл.4.1
Таблиця 4.1
DD
RW
Напрямок
передачі
Режим роботи
х
0
Читання з ОЗП
0
1
Запис в ОЗП із МП
1
1
Запис в ОЗП із зовні
Формування вихідної шини адрес
Рис.4.3 Формування шини адрес
Дана схема функціонує згідно з табл.4.2
Таблиця 4.2
DD
RW
Напрямок
передачі
Режим роботи
х
0
Читання з ОЗП
0
1
Запис в ОЗП із МП
1
1
Запис в ОЗП із зовні
Формування сигналів , ,
Рис.4.4 Формування сигналів , ,
Сигнал формується згідно із табл.4.3
Таблиця 4.3
DD
Режим роботи
0
Запис в ОЗП із МП
1
Запис в ОЗП із зовні
Сигнал → , а сигнал = & .
Формування сигналу
Рис.4.5 Формування сигналу
Для формування сигналу використовується лічильник, який виконує лічбу до N (де N – це кількість точок ШПФ) і генерує переривання для мікропроцесора. Власне сигнал на переривання формується коли завершено запис даних в ОЗП із зовні, тоді ADSP змінює режим роботи пристою керування і починає читати інформацію з ОЗП у внутрішню пам’ять. Після завершення розпочинається обробка вхідної послідовності.
5. Розробка програми виконання алгоритму ШПФ
Програма ШПФ включає три підетапи : перший обраховує ШПФ, другий виконує корекцію даних з плаваючою крапкою, і третій впорядковує результат ШПФ. Усі підетапи показані на блок-схемі програми реалізації ШПФ.
Рис.5.1 Блок-схема програми реалізації ШПФ
5.1 Основний модуль
В основній процедурі (rad4_main) оголошуються та ініціалізуються буфери та змінні завантажені у зовнішній пам’яті. А також викликаються процедура ШПФ та процедура інверсної перестановки.
Модуль rad4_main має наступний вигляд:
.MODULE/ABS=4 rad4_main;
.CONST N=256,N_x_2=512, {Define constants for N-point FFT}
N_div_4=64,N_div_2=128;
.VAR/DM/RAM/ABS=0 inplacedata[N_x_2], padding[4];
{Pad end of inplacedata so memory}
.VAR/DM/RAM twids[N_x_2]; {accesses can exceed end of buffer}
.VAR/DM/RAM outputdata[N_x_2];
.VAR/DM/RAM input_data[N_x_2];
.VAR/DM/RAM groups,bflys_per_group,
node_space,blk_exponent;
.INIT inplacedata: <inplacedata.dat>;
.INIT input_data: <inplacedata.dat>;
.INIT twids: <twids.dat>;
.INIT groups: 1;
.INIT bflys_per_group: N_div_4;
.INIT node_space: N_div_2;
.INIT blk_exponent: 0;
.INIT padding: 0,0,0,0;
.GLOBAL inplacedata,twids, outputdata;
.GLOBAL groups,bflys_per_group,node_space,blk_exponent;
.EXTERNAL rad4_fft,digit_rev;
CALL rad4_fft;
CALL digit_rev;
TRAP; {Stop program execution}
.ENDMOD;
Константи N, N_x_2, N_div_4, N_div_2 використовуються у даному модулі і визначають довжину буфера, як початкове значення для деяких змінних.
Буфер inplacedata використовується для обчислення ШПФ, а менший буфер padding, який розташований вкінці буфера inplacedata, дозволяє доступатися до переповнення буфера.
Буфер input_data містить початкові дані для ШПФ. Даний буфер дозволяє переглянути оригінальні вхідні дані після виконання програми.
Процедура digit_rev виконує інверсну перестановку ШПФ і записує результат. Змінні groups, bflys_per_group, node_space, blk_exponent використовуються для завантаження характеристик рівнів ШПФ.
Буфери inplacedata, twids та input_data ініціалізуються даними із зовнішнього файла.
Змінна groups ініціалізується ‘1’, а bflys_per_group - N_div_4 , оскільки маємо одну групу на першому рівні ШПФ і N/4 метелики на групу. Відстань між вузлами на першому рівні становить N/4. Крім того, буфер inplacedata організований із вкладенням дійсної та уявної частини даних, тому відстань між вузлами подвоюється і стає рівною N/2 . Тому змінна node_space ініціалізується значенням N_div_2 .
Процедура rad4_fft обчислює ШПФ. Інструкція TRAP зупиняє роботу мікропроцесора, коли ШПФ виконано.
5.2 Модуль ШПФ
Модуль rad4_fft має наступний вигляд:
.MODULE radix_4_dif_fft; {Declare and name module}
.CONST log2N_div_2=5; {Initial stage count}
.ENTRY rad4_fft;
.EXTERNAL groups,node_space,bflys_per_group;
.EXTERNAL inplacedata,twids,bfp_adjust;
rad4_fft: CNTR=log2N_div_2; {Initialize stage counter}
M0=0; {Set constant modifiers, length registers}
M1=1;
M3=-1;
M4=1;
L0=0;
L1=0;
L2=0;
L3=0;
L4=0;
L5=0;
L6=0;
L7=0;
DO stage_loop UNTIL CE; {Compute all stages}
SB=-4; {Detects bit growth into 4 MSBs}
SI=DM(groups); {SI=groups}
SR=ASHIFT SI BY 1(HI); {SR1=groups 2}
AY1=SR1; {AY1=groups 2}
AR=AY1-1; {AR=groups 2 - 1}
M5=AR; {M5=groups 2 - 1}
SR=ASHIFT SR1 BY 1(HI); {SR1=groups 4}
AY1=SR1; {AY1=groups 4}
AR=AY1-1; {AR=groups 4 - 1}
M6=AR; {M6=groups 4 - 1}
AY0=SI; {AY0=groups}
AR=AR+AY0; {AR=groups 5 - 1}
AR=AR+AY0; {AR=groups 6 - 1}
M7=AR; {M7=groups 6 - 1}
M2=DM(node_space); {M2=node_space}
I0=^inplacedata; {I0 -->xa}
I1=I0;
MODIFY(I1,M2); {I1 -->xb}
I2=I1;
MODIFY(I2,M2); {I2 -->xc}
I3=I2;
MODIFY(I3,M2); {I3 -->xd}
CNTR=SI; {Initialize group counter}
AY0=DM(node_space);
M2=I3; {M2=node_space 3}
DO group_loop UNTIL CE; {Compute all groups in stage}
I4=^twids; {I4 -->Cb}
I5=I4; {I5 -->Cc}
I6=I5; {I6 -->Cd}
CNTR=DM(bflys_per_group); {Initialize butterfly counter}
AX0=DM(I0,M0); {AX0=xa, I0 -->xa}
AY0=DM(I2,M1); {AY0=xc, I2 -->yc}
MY0=DM(I5,M4); {MY0=Cc, I5 -->(-Sc)}
DO bfly_loop UNTIL CE; {Compute all butterflies in grp}
AF=AX0+AY0,AX1=DM(I1,M1);
AR=AF-AX1,AY1=DM(I3,M1);
AR=AR-AY1,SR1=DM(I1,M3);
MR=AR*MY0(SS),SR0=DM(I3,M3);
MX0=AR,AR=AX1+AF;
AR=AR+AY1;
SB=EXPADJ AR,DM(I0,M1)=AR; {xa´=xa+xb+xc+xd}
AF=AX0+AY0,AX0=DM(I0,M0);
AR=SR1+AF,AY0=SR0;
AF=AF-SR1;
AR=AR-AY0,AY0=DM(I2,M3);
MX1=AR,AR=SR0+AF;
AF=AX0+AY0,DM(I3,M1)=AR;
AY0=DM(I3,M3),AR=SR1+AF;
AR=AR+AY0,MY1=DM(I5,M6);
SB=EXPADJ AR,DM(I0,M1)=AR; {ya´=ya+yb+yc+yd}
AF=AF-SR1;
AR=AF-SR0;
MR=MR-AR*MY1(SS);
SB=EXPADJ MR1,DM(I2,M1)=MR1; {xc´=(xa-xb+xc-xd)Cc}
MR=AR*MY0(SS); {-(ya-yb+yc-yd)(-Sc)}
MR=MR+MX0*MY1(SS),AY0=DM(I2,M0);
SB=EXPADJ MR1,DM(I2,M1)=MR1; {yc´=(ya-yb+yc-yd)Cc}
AF=AX0-AY0,MY1=DM(I4,M4); {+ (xa-xb+xc-xd)(-Sc)}
AR=AF-AX1,AX0=DM(I0,M0);
AR=AR+AY1,AY0=DM(I2,M1);
MR=MX1*MY1(SS),MY0=DM(I4,M5);
MR=MR-AR*MY0(SS);
SB=EXPADJ MR1,DM(I1,M1)=MR1; {xb´=(xa+yb-xc-yd)Cb}
MR=AR*MY1(SS); {-(ya-xb-yc+yd)(-Sb)}
MR=MR+MX1*MY0(SS),MX1=DM(I3,M0);
SB=EXPADJ MR1,DM(I1,M1)=MR1; {yb´=(ya-xb-yc+xd)Cb}
AR=AX1+AF,MY0=DM(I6,M4); {+ (xa+yb-xc-yd)(-Sb)}
AR=AR-AY1,MY1=DM(I6,M7);
MR=MX1*MY0(SS);
MR=MR-AR*MY1(SS);
SB=EXPADJ MR1,DM(I3,M1)=MR1; {xd´=(xa-yb-xc+yd)Cd}
MR=AR*MY0(SS),MY0=DM(I5,M4); {- (ya+xb-yc-xd)(-Sd)}
MR=MR+MX1*MY1(SS);
bfly_loop: SB=EXPADJ MR1,DM(I3,M1)=MR1;
{yd´= (ya+xb-yc-xd)Cd}
{+ (xa-yb-xc+yd)(-Sd)}
DO bfly_loop UNTIL CE;
{Compute all butterflies in grp}
AF=AX0+AY0,AX1=DM(I1,M1);
AR=AF-AX1,AY1=DM(I3,M1);
AR=AR-AY1,SR1=DM(I1,M3);
MR=AR*MY0(SS),SR0=DM(I3,M3);
MX0=AR,AR=AX1+AF;
AR=AR+AY1;
SB=EXPADJ AR,DM(I0,M1)=AR; {xa´=xa+xb+xc+xd}
AF=AX0+AY0,AX0=DM(I0,M0);
AR=SR1+AF,AY0=SR0;
AF=AF-SR1;
AR=AR-AY0,AY0=DM(I2,M3);
MX1=AR,AR=SR0+AF;
AF=AX0+AY0,DM(I3,M1)=AR;
AY0=DM(I3,M3),AR=SR1+AF;
AR=AR+AY0,MY1=DM(I5,M6);
SB=EXPADJ AR,DM(I0,M1)=AR; {ya´=ya+yb+yc+yd}
AF=AF-SR1;
AR=AF-SR0;
MR=MR-AR*MY1(SS);
SB=EXPADJ MR1,DM(I2,M1)=MR1;
{xc´=(xa-xb+xc-xd)Cc}
MR=AR*MY0(SS); {-(ya-yb+yc-yd)(-Sc)}
MR=MR+MX0*MY1(SS),AY0=DM(I2,M0);
SB=EXPADJ MR1,DM(I2,M1)=MR1;
{yc´=(ya-yb+yc-yd)Cc}
AF=AX0-AY0,MY1=DM(I4,M4);
{+ (xa-xb+xc-xd)(-Sc)}
AR=AF-AX1,AX0=DM(I0,M0);
AR=AR+AY1,AY0=DM(I2,M1);
MR=MX1*MY1(SS),MY0=DM(I4,M5);
MR=MR-AR*MY0(SS);
SB=EXPADJ MR1,DM(I1,M1)=MR1;
{xb´=(xa+yb-xc-yd)Cb}
MR=AR*MY1(SS); {-(ya-xb-yc+yd)(-Sb)}
MR=MR+MX1*MY0(SS),MX1=DM(I3,M0);
SB=EXPADJ MR1,DM(I1,M1)=MR1;
{yb´=(ya-xb-yc+xd)Cb}
AR=AX1+AF,MY0=DM(I6,M4); {+ (xa+yb-xc-yd)(-Sb)}
AR=AR-AY1,MY1=DM(I6,M7);
MR=MX1*MY0(SS);
MR=MR-AR*MY1(SS);
SB=EXPADJ MR1,DM(I3,M1)=MR1;
{xd´=(xa-yb-xc+yd)Cd}
MR=AR*MY0(SS),MY0=DM(I5,M4);
{- (ya+xb-yc-xd)(-Sd)}
MR=MR+MX1*MY1(SS);
bfly_loop: SB=EXPADJ MR1,DM(I3,M1)=MR1;
{yd´= (ya+xb-yc-xd)Cd}
{+ (xa-yb-xc+yd)(-Sd)}
MODIFY(I0,M2); {I0 -->1st xa of next group}
MODIFY(I1,M2); {I1 -->1st xb of next group}
MODIFY(I2,M3);
MODIFY(I2,M2); {I2 -->1st xc of next group}
group_loop: MODIFY(I3,M2); {I3 -->1st xd of next group}
CALL bfp_adjust; {Check for bit growth}
SI=DM(groups); {SI=groups}
SR=ASHIFT SI BY 2(HI); {SR1=groups 4}
DM(groups)=SR1; {Group count, next stage}
SI=DM(bflys_per_group); {SI=bflys_per_group}
SR=ASHIFT SI BY -1(HI); {SR1=bflys_per_group 2}
DM(node_space)=SR1; {Node spacing, next stage}
SR=ASHIFT SI BY -1(HI); {SR1=node_space 2}
stage_loop: DM(bflys_per_group)=SR1; {Butterfly count, next stage}
RTS;
.ENDMOD;
Даний модуль містить три цикли , а саме stage_loop (розовий колір), group_loop (синій колір), bfly_loop (зелений колір). Далі наведено опис кожного з них.
5.2.1 Цикл метелика (bfly_loop)
Дана частина коду обчислює один метелик за основою 4. Формули для обчислення метелика наступні :
Для кожного з восьми результатів контролюється переповнення за допомогою функції EXPADJ. Додатково на даному кроці встановлюються початкові дані для наступного метелика.
Вхідні та вихідні параметри циклу наступні:
Початкові умови Вихідний результат
I0 --> xa I0 --> next xa
I1 --> xb I1 --> next xb
I2 --> yc I2 --> next yc
I3 --> xd I3 --> next xd
I4 --> Cb I4 --> next Cb
I5 --> Sc I5 --> next Sc
I6 --> Cd I6 --> next Cd
M0 = 0 AX0 = next xa
M1 = 1 AY0 = next xc
M3 = –1 MY0 = next Cc
CNTR = butterfly counter CNTR = butterfly counter – 1
M4 = 1
M5 = groups x 2 – 1
M6 = groups x 4 – 1
M7 = groups x 6 – 1
AX0 = xa
AY0 = xc
MY0 = Cc
5.2.2 Цикл групи (group_loop)
Дана частина коду використовується для обчислення однієї групи метеликів. Оскільки перший метелик у всіх групах має ваговий коефіцієнт W0 , то вказівник вагового коефіцієнта вказує на дійсну частину W0 . Далі відбувається ініціалізація лічильника метеликів та необхідних початкових даних.
Після того як усі метелики в групі пораховані, вказівники, які використовувалися при обчисленні метелика, ініціалізуються відповідними значеннями для обрахунку першого метелика наступної групи.
Цикл групи виконується стільки раз, скільки є груп на одному рівні.
Вхідні та вихідні параметри циклу наступні:
Початкові умови Вихідний результат
I0 --> xa I0 --> first xa of next group
I1 --> xb I1 --> first xb of next group
I2 --> xc I2 --> first xc of next group
I3 --> xd I3 --> first xd of next group
M0 = 0 I4 --> invalid location for twiddle factor
M1 = 1 I5 --> invalid location for twiddle factor
M2 = 3 x node_space I6 --> invalid location for twiddle factor
M3 = –1 CNTR = group count – 1
M4 = 1
CNTR = group count
5.2.3 Цикл рівня (stage_loop)
На даному циклі контролюється кількість груп на одному рівні та кількість метеликів у групі. Дана частина коду обчислює усі групи метеликів на конкретному рівні та оновлює необхідні параметри для наступного рівня.
Потенційно при обчисленні метелика вхідні данні можуть збільшитися на 3 біти, тому кожне вхідне значення ШПФ має 3 додаткові контрольні біти для запобігання переповненню. SB ініціалізується значенням -3. Отже, при настанні переповнення його можна буде компенсувати при виконанні блоку корекції даних з плаваючою крапкою, який виконується після кожного рівня.
Змінна groups завантажується у SI та використовується для встановлення різних параметрів рівня, а саме groupsх2-1 - модифікатор вагового коефіцієнта (b), groupsх4-1 - модифікатор вагового коефіцієнта (c), groupsх6-1 - модифікатор вагового коефіцієнта (d). Встановлюються значення xa, xb, xc, та xd для першого метелика на відповідному рівні. Ін...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора