Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка процессора ШПФ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Курсовий проект
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
ІКТА
Кафедра ЕОМ
Курсовий проект
з дисципліни
«Методи, алгоритми та засоби цифрової обробки сигналів та зображень»
на тему:
«Розробка процессора ШПФ»
Львів-2007
Завдання
Варіант № 33
Розробити процесор ШПФ з такими вхідними даними:
Тип процесора АDSP- Blackfin 535
Кількість точок N 1024
Основа ШПФ 4
Прорідження Частотне (F)
Вагова функція Пуасона
Час обробки 1,8 мс
Розрядність вхідних даних 24 (12 +12)
Тип зовнішнього інтерфейсу SPORT
Анотація
В даному курсовому проекті розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для сигнального процессора ADSP-BF535 для 24-розрядних вхідних даних з частотним прорідженням, детально описано механізми обчислення швидкого перетворення Фур`є за заданною основою, властивості та основні характеристики процесора, на якому планується реалізація, підраховано часові ресурси для виконання обчислення, створена функціональна схема системи та написана програма, що реалізує вказаний алгоритм ШПФ на заданому процесорі.
Зміст
. Вступ
5
1. Теоретичний розділ
6
1.1.Характеристики сигнального процесора ADSP-BF535
6
1.2 Опис ШПФ
9
2. Аналіз блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора
21
3. Розрахунковий розділ
23
4. Розробка функціональної схеми
25
5. Розробка програми виконання заданої функції
29
Висновки
32
Література
33
Вступ
Аналіз Фур'є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур'є (фактично існує кілька варіантів таких перетворень) дозволяє співставити сигналу, заданому в часовій області, його еквівалентне представлення в частотній області, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур'є дозволяє визначити відповідний сигнал у часовій області.
Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур'є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур'є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
1.Теоретичний розділ
1.1. Характеристики сигнального процесора ADSP-BF535
1.1.1.Призначення ADSP-BF535.
Процесор ADSP-BF535 входить в склад сімейства процесорів Blackfin. Архітектура ядра процесора комбінує механізм подвійної МАС обробки сигналу. Має RISC-подібну систему команд, та одну команду для множення даних (SIMD), підтримує мультимедійні можливості в одному коді команди.
Blackfin процесори підтримують динамічне керування живленням, можуть змінювати як і напругу так і частоту, щоб забезпечити низьке енергоспоживання.
Процесор ADSP-BF535 використовує поняття ядро та система для опису власної архітектури:
• Ядро означає: процесор, пам'ять першого рівня L1, контролер подій, основний таймер, і регістри контролю продуктивності.
• Система означає: периферійну множину,шину PCI, контролер зовнішньої пам’яті (EBIU), контролер прямого доступу до пам’яті (DMA), і інтерфейси між цими компонентами в системі та зовнішні ресурси.
1.1.2. Ключові особливості ADSP-BF535:
високопродуктивне ядро процесора Вlackfin з частотою 350 МГц;
два 16-бітові акумулятори множення (МАС);
два 40-бітові АЛП;
40-бітовий регістр зсуву;
чотири 8-ми бітові відео АЛП;
два 40-бітові акумулятори;
RISC – подібна регістрова пам’ять та система команд, для зручного програмування та компіляції, потужна система відлагодження програм, контроль продуктивності ядра мікропроцесора, 1.0 V – 1.6 V з динамічним енергетичним управлінням;
напруга вводу виводу 3.3 V.
Пам’ять:
Мікропроцесор ADSP-BF535 має 4 Гбайт-ний адресний простір, який охоплює як пам’ять на кристалі так і зовнішню пам’ять, та карту пам’яі ресурсів вводу/виводу. 285 Мбайт пам’яті виділено для внутрішніх ресурсів процесора Рис. 1. У цей внутрішній простір входить декілька типів пам’яті мікропроцесора:
16K Bytes пам’ять команд L1 SRAM/Cache
32K Bytes пам’ять даних L1 SRAM/Cache
4K Bytes резервна пам’ять L1 SRAM
256K Bytes високошвидкісна пам’ять з малим часом доступу L2 SRAM
DMA, контроле[Введите цитату из документа или краткое описание интересного события. Надпись можно поместить в любое место документа. Для изменения форматирования надписи, содержащей броские цитаты, используйте вкладку "Работа с надписями".]
р прямого доступу до пам’яті:
Пристрій керування пам’яттю, призначений для захисту пам’яті, приєднанням зовнішніх контролерів пам’яті, синхронізації SDRAM, підтримка асинхронних SRAM, Flash, ROM.
Рис. 1.
Периферія:
32-Bit, 33 MHz, 3.3 V, PCI 2.2 послідовний шинний інтерфейс з підтримкою режиму Master і Slave.
інтегрований послідовний інтерфейс USB 1.1;
два порти UART, та один порт IrDA®;
два SPI послідовні порти;
два дуплексних, синхронних, паралельних порти (SPORT)
чотири таймери/лічильники, три широтно імпульсних модулятора PWM;
шістнадцять двонаправлених програмованих портів вводу/виводу;
Watchdog Timer;
Real-Time Clock, годинник реального часу;
PLL на кристалі від 1 до 31 фазова автонастройка частоти.
Функціональна схема:
Рис. 2
ADSP-BF535 Периферія
Процесор ADSP-BF535 Blackfin містить широкий набір зовнішніх пристроїв, з’єднаних з ядром мікропроцесора через високошвидкісну шину, забезпечуючи гнучкість в конфігурації системи.
Інтегровані на кристалі:
2 порти UART;
таймери з PWM (широтно-імпульсною модуляцією) і можливість вимірювання тривалості імпульсу;
основні порти вводу/виводу;
годинник реального часу, і watchdog таймер.
Також містить високошвидкісні паралельні порти до інтерфейсів модему та звукових виходів, функції CODEC. Також містить програму для обробки переривань від зовнішніх пристроїв та інших джерел переривань. Контролер використання енергії забезпечує оптимальні енергетичні характеристики процесора та системи для виконання різного роду задач. До мікропроцесора можна легко підключати зовнішні пристрої за рахунок великої кількості інтерфейсів. Включаючи 32-бітну, 33 MHz, V2.2 послідовну PCI шину, паралельний порт SPI та USB порт. Усі інтерфейси і таймери окрім програмованих регістрів працють в режимі реального часу, підтримується гнучка DMA структура з виділеними каналами інтегровані в периферію. Має також виділений окремий канал DMA пам’яті призначений для передачі даних в різні частини пам’яті включаючи зовнішню пам’ять SDRAM і асинхронну пам’ять, внутрішню пам’ять SRAM 1 та 2 рівня та пам’ять шини PCI. Основна 32-розрядна шина працює з частотою 133 МГц, забезпечує широку смугу пропусканя для підтримки ядра процесора в постійній роботі, та повним обміном інформацією з периферією.
Ядро процесора
Як показано на Рис.3 ядро процесора Blackfin складається з двох акумуляторів множення (MAC), двох 40-бітних АЛП, 4 відео АЛП, та регістра зсуву. Обчислювальний блок процесора може приймати 8-ми, 16-ти чи 32-ти розрядні дані з регістрового файлу.
Кожен MAC акумулятор виконує операцію множення 16 бітна 16 кожного такту з накопиченням і видає 40-бітний результат, резервуючи 8-м біт для підвищення точності. АЛП виконують стандартні арифметичні та логічні операції. Два АЛП мають можливість обробляти як 16-ти так і 32-х розрядні дані. Кожен з 32-бітних вхідних регістрів представлений двома 16-ти розрядними, отже кожен АЛП може гнучко виконувати прості 16-ти бітні арифметичні операції. Для відображення 32-х розрядного регістру використовують пару 16-ти розрядних регістрів або один 32-х розрядний, операції можуть виконуватись за один цикл. Одночасно можуть виконуватися чотири 16-ти бітові операції маючи перевагу над звичайним АЛП. Це збільшує продуктивність за один цикл. Потужний 40-ка бітовий регістр зсуву надає великі можливості для виконання зсуву, повороту, нормалізації, витягання та укладання даних.
Дані для обчислень вибираються з багатопортового регістрового файлу з шістнадцяти 16-ти бітних або восьми 32-х бітних портів. Два генератори адрес (DAG) забезпечують вибіркою відразу двох операндів з пам’яті. DAG розділяє регістровий файл на чотири частини 32-х бітний індекс, частина для модифікації, довжина та базовий регістр.
Рис.3
Процесор Blackfin підтримує Гарвардську архітектуру з структурою ієрархії пам’яті. Пам’ять 1 рівня L1, зазвичай оперативна пам’ять, яка працює на частоті процесора і може мати невелику затримку. Пам’ять 2-го рівня L2, це інша пам’ять, може розміщуватися на кристалі і використовує багато циклів процесора для запису чи читання даних. Пам’ять першого рівня використовується тільки як пам’ять команд чи окремо пам’ять даних. Дві пам’яті даних використовують дані і вирішують куди краще записати інформацію. Пам’ять другого рівня використовує єдиний адресний простір для запису команд та даних. В сумі, пам’ять L1 рівня команд та L1 рівня даних може бути зконфігурована як статична RAM (SRAM) або кеш пам’ять. Блок організації пам’яті (MMU) забезпечує захист пам’яті та внутрішніх регітрів процесора від несанкціонованого доступу. Архітектура забезпечує три способи обчислень: корстувацький режим, режим контролю та режим емулювання. Користувацький режим дозволяє реструктурувати доступ до ресурсів центральної системи так забезпечити захист програмних продуктів, поки режим контролю не реструктуризує доступ до системи та ядра процесора.
Система команд процесора оптимізована до 16-ти біт op-коду і дозволяє використовувати максимальну частоту обробки команд, результатом є чудова густина програмного коду. Комплекс DSP команд декодуються в 32-о бітні op-коди, представлені повним описом багатофункціональних команд. Blackfin процесор підтримує обмежену вихідну продуктивність де 32-х бітні команди можуть бути видані паралельно як дві 16-ти бітні, дозволяючи програмі використовувати багато ресурсів ядра процесора за один такт.
Blackfin процесор на мові assembler використовує алгебраїчний синтаксис для зручного кодування та візуального сприйняття. Архітектура оптимізована для роботи з С/С++ компіляторами, результатом є швидке та ефективне програмне забезпечення.
1.1.4.Опис виводів
Рис.1.2. Процесор ADSP-21060
В табл.1.1. використовуються такі позначення:
A – асинхронний;
G – земля;
І – вхід;
О -- вихід;
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
Не під’єднано.
1.2. Опис ШПФ
1.2.1.Опис швидкого перетворення Фур’є з прорідженням по частоті
Основна ідея алгоритму ШПФ з проріджуванням по частоті полягає в поетапному обчислені N-точкового ДПФ на
1.2.2.Алгоритм перетворення
Алгоритм ШПФ можна скласти, спираючи на граф ШПФ при N=8. Зауважимо, що ДПФ з однаковим числом точок на графі розташовані у вигляді стовпців. Пронумеруємо ДПФ у кожнім стовпці цифрами від 0 до 7 (від 0 до N-1 у загальному випадку) зверху вниз. Вихідні значення ДПФ - комплексні числа, які можна зберігати у деякому масиві. Перехід відповідно до базових співвідношень від ДПФ попереднього стовпця до ДПФ із подвоєним числом точок наступного стовпця назвемо кроком перетворення. З огляду на послідовний характер кроків перетворення, вихідні значення ДПФ кожного стовпця можна зберігати в тому самому масиві (це повинен бути масив комплексних чисел). Остаточно масив буде містити результуючі значення ШПФ.
Графи базових співвідношень на кожнім кроці візуально групуються. Групи складаються з окремих графів чи декількох графів, що перетинаються між собою. У прикладі на першому кроці графа є 4 групи, у другому – 2 і на третьому - 1.
Введемо позначення:
- число відліків сигналу, що обробляється, чи число точок перетворення;
v - число кроків перетворення;
step - номер кроку, step = 0,..., v - 1;
group - номер групи графів, group = 0, ..., (group_max - 1), де group_max - число груп (залежить від номера кроку);
іnput - номер ДПФ, вихід якого з'єднаний з верхнім входом графа базового співвідношення;
іnput +add - номер ДПФ, вихід якого з'єднаний з нижнім входом цього графа;
add - різниця відповідних номерів;
pow - ступінь множника повороту (у тексті pow відповідає показнику k в ) .
Змінні зв'язані між собою в такий спосіб:
Ці співвідношення отримані при аналізі графа ШПФ.
Для приведеного графа побудована таблиця, у якій для кожного кроку перетворення занесені індекси і їхні межі зміни, що використані в циклах програми. Нижче приведений алгоритм програми. Його особливість - результат виходить у масиві вхідних даних. Алгоритм побудований для випадку комплексних вхідних даних, як більш загальний випадок.
1.2.3.Алгоритм ШПФ з проріджуванням по частоті
Вхідні дані в алгоритмі:
Х(k), k = 0,..., N -1 - масив комплексних вхідних і вихідних даних.
Для k = 0,..., N -1 встановити:
Встановити:
1. Перестановка елементів масиву Х(k).
2. Якщо step = v, перейти до кроку 9.
3. group←0/
4. Якщо group = group_max: step←step+1, add←add * 2,
group_max←group_max/2, перейти до кроку 2.
5. іnput ← group 2step +1.
6. Якщо іnput = group 2step+1+2step: group←group+1, перейти до кроку 4.
7. [Базова операція]
pow ←group_max *<input>2step+1,
t← X(іnput + add) * W(pow +1),
X(іnput +add) ←X(іnput) - t,
X(іnput) ←X(іnput) + t.
8. input←input+1, перейти до кроку 6.
9. Завершення.
1.2.4.Алгоритм двійково-інверсної перестановки
1. k←0.
2. Якщо k = N, то виконання алгоритму припиняється.
3. n← m← 0 (n←0,m←0 ).
4. Якщо m = v : перейти до кроку 7.
5. Якщо біт з номером m (0-ої біт - наймолодший) числа k дорівнює 1,
то n←n + 2v - m - 1.
6. m←m+1, перейти до кроку 4.
7. Якщо k < n : X(k)↔ X(n).
8. k←k+1, перейти до кроку 2.
1.2.5.Приклад виконання для 64-точкового перетворення за основою 4
Табл.2.2.2. Порядок розташування відліків
Порядок перед відповідною ітерацією
Номер метелика в ярусі
1
2
3
0
0
0
1
16
4
1
32
8
2
48
12
3
1
1
4
2
17
5
5
33
9
6
49
13
7
2
2
8
3
18
6
9
34
10
10
50
14
11
…
15
51
60
16
31
55
61
47
59
62
63
63
63
Блок-схема перетворення виглядає так:
Рис.1.2.2. Блок-схема 64-точкового перетворення за основою 4
Рис.1.2.3. Граф 64-точкового ШПФ за основою 4 з прорідженням по часу
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора
Алгоритм базової операції ШПФ за основою 4 і проріджування за часом можна представити у вигляді
А'1 = А1 + A2W1 + A3W2 + A4W3 = (А1 + A3W2) + (A2W1 + A4W3),
A'2 = A1 jA2W1 – A3W2 ± jA4W3 = (A1 – A3W2 ) j(A2W1 - A4W3 ),
A'3 = A1 - A2W1 + A3W2 - A4W3 = (A1 + A3W2) - (A2W1 + A4W3),
A'4 = A1 ± jA2W1 – A3W2 jA4W3 = (A1 - A3W2) ± j(A2W1 - A4W3),
де A'1, A'2, А'з, А'4 - результати базової операції; А1, А2, А3, А4 - вхідні відліки; W1, W2, W3 - комплексні коефіцієнти; j - уявна одиниця, верхній знак перед j відповідає прямому, нижній - оберненому ШПФ.
ReA'1 = [ReА1 + (ReA2*ReW2 - ІmA3*ImW2)] + [(ReA2*ReW1 - ImA2*ImW1) + (ReA4 *ReW3 – ImA4*ImW3)],
ІмA'1 = [Іm A1 + (Re A3*Im W2 + ImA3*Re W2)] + [(ReA2*ImW1 + ІmA2*ReW1) + (ReA4*ImW3 + ImA4*Re W3)],
RеA'2 = [ReA1 - (ReA3*ReW2 - ImA3*ImW2)] ± [(ReA2*ImW1 + ImA2*ReW1) – (ReA4*ІmW3 + ImA4*ReW3)],
ImA'2 = [ImA1 - (ReA3*ІmW2 + ImA3*ReW2)] [(ReA2*ReW1 - ImA2*ImW1) - (ReA4*ReW3 - ImA4*ImW3)],
ReA'3 = [ReA1 + (ReA3*ReW2 - ImA3*ImW2)] - [(ReA2*ReW1 - ImA2*ImW1) + (ReA4*ReW3 - ImA4*ImW3)],
ІmA'3 = [ІmA1 + (ReA3*ImW2 + ImA3*ReW2)] - [(ReA2*ImW1 + ImA2*ReW1) +(ReA4*lmW3 + ImA4*ReW3)],
ReA'4 = [ReA1 - (ReA3*ReW2 – ImA3*ImW2)] [(ReA2*ImW1 + ImА2*ReW1) - (ReA4*ReW3 -ImA4*ReW3)],
ImA'4 = [ImA3 - (ReA3*ImW2 + ImA3*ReW2)] ± [(ReA2*ReW1 - ImA2*Im W1) - (ReA4*ReW3 – ImA4*ImW3)]
Для виконання базової операції вимагається виконати 12 операцій множення і 22 додавання.
Рис.2.1. «Метелик» алгоритму ШПФ з прорідженням по часу
Табл.2.1. Порядок слідування відліків для кожного ярусу
I
II
III
IV
0
0
0
0
64
16
4
1
128
32
8
2
192
48
12
3
1
1
1
4
65
17
5
5
129
33
9
6
193
49
13
7
2
2
2
8
66
18
6
9
130
34
10
10
194
50
14
11
3
3
3
12
67
19
7
13
131
35
11
14
195
51
15
15
4
4
17
16
68
20
21
17
132
36
25
18
196
52
29
19
…
62
206
242
248
126
222
246
249
190
238
250
250
254
254
254
251
63
207
243
252
127
223
247
253
191
239
251
254
255
255
255
255
Рис.2.2. Блок-схема алгоритму 256-точкового перетворення за основою 4
3.Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – кількість точок вхідного перетворення;
base=4;
N=256;
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
Для виконання базової операції «метелик» необхідно:
12 операцій множення;
22 операцій додавання;
14 операцій читання з пам`яті:
- 4*2=8 (для читання дійсної та уявної частини вхідних відліків);
- 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів);
8 операцій запису:
- 4*2=8 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 56 операцій: Nна 1 мет=56 (оп)
Тривалість виконання обчислення ШПФ:
Тривалість надходження даних у процесор для обробки:
Тнадх=20нс – такт надходження даних;
Тривалість надходження даних у процесор та тривалість обчислення ШПФ:
Ця величина менша за заданий час обробки: , тобто для виконання обчислення достатньо одного процесора.
Рис.3.1. Часова діаграма роботи системи
Внутрішня ОЗП процесора ADSP-BF535 є 285Мбайт, тобто може бути сконфігурована наступним чином: 218 слів по 12 розрядів (4Мб=222 біт).
Для розв`язання поставленої задачі необхідно 512 слів по 16 розрядів. 512х16=29х24=213. Тобто внутрішньої ОЗП цілком вистачає.
Для зберігання повертаючих множників необхідно ПЗП об`ємом: 1536х16,
оскільки на 1 операцію метелик необхідно 3 повертаючих множника, кожен з яких містить дійсну та уявну частину, всього є 256 базових операцій, розрядність операндів є 16. Тому 3*2*256=1536.
Окремо використовуємо завантажувальну пам`ять, де буде зберігатися лістінг програми.
Необхідна зовнішня ОЗП розміром 512х16 для постійного приймання даних, що надходять.
Рис.3.2.Ділянка пам`яті внутрішньої ОЗП, що приймає участь в обробці
4. Розробка функціональної схеми
4.1. Вибір мікропроцесора
Згідно варіанту завдання було вибрано процесор ADSP-21060, тактова частота роботи якого – 40МГц і відповідна тривалість такту – 25нс. На вхід сигнального мікропроцесора надходять такі сигнали:
CLKIN – сигнал синхронізації, що надходить з внутрішнього тактового резонатора;
– глобальний сигнал аппаратного скиду;
– сигнал зовнішнього маскованого переривання;
Вихідними та двонапрямленими сигналами по відношенню до мікропроцесора є:
– сигнал вибору кристалу мікросхеми завантажувальної пам`яті;
ADDR[31:0] – шина адреси;
DATA[47:0] – шина даних;
– строб читання даних з зовнішнього пристрою у мікропроцесор;
– строб запису даних у зовнішній пристрій з мікропроцесора;
– сигнали вибору кристалів відповідно зовнішнього ПЗП(MS1) та зовнішнього ОЗП(MS0);
Інші сигнали або не задіяні, або їх використання не розглядається у данному курсовому проекті. Наприклад, виведення оброблених даних на зовні з мікропроцесора є передбаченим каналами прямого доступу до пам`яті DMA і є відповідний фонд часу для здійснення цієї операції.
4.2. Пам’ять завантаження
Це пам’ять типу EPROM, тобто стирання старої інформації та запис нової є можливим, але лише в результаті спеціального процесу, для здійснення якого запам`ятовуючий пристрій виводиться з робочого режиму (читання даних) та проводиться репрограмування (стирання відбувається за допомогою ультрафіолет-тових променів).
В даному проекті цей блок пам`яті використовується для зберігання програми обчислення алгоритму ШПФ.
Дана пам’ять призначена для зберігання програми роботи мікропроцесора.
Після ввімкнення живлення чи програмному скиді (встановлення у початковий стан) програма автоматично завантажується до внутрішньої пам’яті. Цей процес називається початковим завантаженням.
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 використовується як вихідний і з’єднуючись з ЕВООТ, утворює сигнал вибору кристалу.
Розмір пам`яті умовно беремо 1024х8.
4.3. Зовнішнє ПЗП
Запам`ятовуючий пристрій типу ROM (призначена тільки для читання) зберігає інформацію, що ніколи не змінюється. Інформація записується у нього при виготовленні на промисловому підприємстві з допомогою шаблона (масок) на завершальному етапі технологічного процесу.
В даному курсовому проекті пам’ять цього типу використовується для зберігання повертаючих множників, її розмір обґрунтований у вищенаведеному розділі і складає 1536х16.
4.4. Зовнішнє ОЗП
Запам`ятовуючий пристрій типу SDRAM (Synchronous Dynamic RAM) є швидкодіючою пам`ятю з високою пропускною здатністю. В ній синхросигналу пам’яті тісно пов`язані з тактовою частотою системи, в ній використовується конвеєризація тракта просування інформації, може застосовуватися багатобанкова структура пам`яті.
Вона використовується для зберігання даних, що надходять у систему зовні від давача сигналу. Її розмір 512х16.
Роботою цієї пам`яті керує безпосередньо вузол керування, а не сигнальний процесор, як для вище описаних блоків пам`яті.
Рис.4.1.Часова діаграма запису у зовнішнє ОЗП
4.5. Розробка керуючого пристрою
Призначення даного вузла – арбітраж доступу до зовнішнього ОЗП між обчислювальним процесором та давачем сигналу.
Сигнали, що надходять на керуючий пристрій:
CLK – сигнал синхронізації з давача;
– глобальний сигнал апаратного скиду;
STRD – строб даних, що надходить з давача;
ADDR_IN – шина адреси з обчислювального процесору;
– строб читання зовнішньої пам`яті, надходить з процесору;
– вибір кристалу зовнішньої пам`яті, надходить з процесору;
Сигнали, що виходять з керуючого пристрою:
– дозвіл видачі даних з мікросхеми зовнішньої пам`яті;
– дозвіл запису до мікросхеми зовнішньої пам`яті;
– вибір кристалу зовнішньої пам`яті;
ADDR_OUT – шина адреси, що скеровується на мікросхему зовнішньої пам`яті;
– сигнал маскованого переривання;
Регістр стану зберігає значення сигналів , , , Вихід можна використати як сигнали дозволу у буферній розв`язці для шини даних, оскільки сигнали та взаємовиключаючі і суперечать один одному. Сигнал можна також використати як сигнал ACK, що надходить на процесор і є підтвердженням доступу до зовнішньої пам`яті зовнішнім пристроєм.
Рис.4.2. Структура керуючого пристрою
Рис.4.3. Структура обчислювальної системи
Табл..4.1. Таблиця станів керуючого автомату
Сигнал
Стан очікування
Запис в ОЗП
Читання з ОЗП
RD#
x
X
0
MS0#
x
x
0
STRD
0
1
0
OE#
1
1
0
WE#
1
0
1
CS#
1
0
0
MEM_RD
0
0
1
MEWR
0
1
0
ADDR_OUT
Z
ADDR
ADDR_IN
Сигнал формується лічильником при досягненні межі лічби і направляється на процесор, де обробляється програмою обробки переривань. Лічильник сам скидає сигнал переривання на початку нового циклу лічби. Лічильник сам скидається у початковий стан при надходження стробу даних, а також при подачі апаратного скиду.
Дані надходять із сенсора 16-розрядними і по черзі записуються у зовнішнє ОЗП
5. Розробка програми виконання алгоритму ШПФ
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис.5.1. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент массиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 4*64*3=768 (4 - кількість ярусів, 64 - кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
N=256;
struct complex
{ double re;
double im;
};
complex W[3*N];
complex matrix[N];
int i,imax,j,x1,x2,x3,x4;
int f; //номер етапу
int p; //номер операції в етапі
complex temp1,temp2,temp3,temp4;
f=0;
for(imax = N-1; imax <=0; imax = (imax+1)/4 – 1)
{ p=0;
for(j = 0; j < N; j = j + (imax+1)*4)
{
x1 = j + (imax+1)*0;
x2 = j + (imax+1)*1;
x3 = j + (imax+1)*2;
x4 = j + (imax+1)*3;
for (i = 0; i <= imax; i++)
{
temp1.re=
matrix[x1+i].re + matrix[x3+i].re*W[n*64+p*3+1].re –
- matrix[x3+i].im*W[n*64+p*3+1].im +
+ matrix[x2+i].re*W[n*64+p*3+0].re –
- matrix[x2+i].im*W[n*64+p*3+0].im +
+ matrix[x4+i].re*W[n*64+p*3+2].re –
- matrix[x4+i].im*W[n*64+p*3+2].im;
temp1.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*64+p*3+1].im +
+ matrix[x3+i].im*W[n*64+p*3+1].re +
+ matrix[x2+i].re*W[n*64+p*3+0].im +
+ matrix[x2+i].im*W[n*64+p*3+0].re +
+ matrix[x4+i].re*W[n*64+p*3+2].im +
+ matrix[x4+i].im*W[n*64+p*3+2].re;
temp2.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*64+p*3+1].re +
+ matrix[x3+i].im*W[n*64+p*3+1].im +
+ matrix[x2+i].re*W[n*64+p*3+0].im +
+ matrix[x2+i].im*W[n*64+p*3+0].re -
- matrix[x4+i].re*W[n*64+p*3+2].im –
- matrix[x4+i].im*W[n*64+p*3+2].re;
temp2.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*64+p*3+1].im -
- matrix[x3+i].im*W[n*64+p*3+1].re -
- matrix[x2+i].re*W[n*64+p*3+0].re +
+ matrix[x2+i].im*W[n*64+p*3+0].im -
- matrix[x4+i].re*W[n*64+p*3+2].re +
+ matrix[x4+i].im*W[n*64+p*3+2].im;
temp3.re=
matrix[x1+i].re + matrix[x3+i].re*W[n*64+p*3+1].re –
- matrix[x3+i].im*W[n*64+p*3+1].im -
- matrix[x2+i].re*W[n*64+p*3+0].re +
+ matrix[x2+i].im*W[n*64+p*3+0].im +
+ matrix[x4+i].re*W[n*64+p*3+2].re –
- matrix[x4+i].im*W[n*64+p*3+2].im;
temp3.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*64+p*3+1].im +
+ matrix[x3+i].im*W[n*64+p*3+1].re -
- matrix[x2+i].re*W[n*64+p*3+0].im -
- matrix[x2+i].im*W[n*64+p*3+0].re +
+ matrix[x4+i].re*W[n*64+p*3+2].im +
+ matrix[x4+i].im*W[n*64+p*3+2].re;
temp4.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*64+p*3+1].re +
+ matrix[x3+i].im*W[n*64+p*3+1].im -
- matrix[x2+i].re*W[n*64+p*3+0].im –
- matrix[x2+i].im*W[n*64+p*3+0].re -
- matrix[x4+i].re*W[n*64+p*3+2].re +
+ matrix[x4+i].im*W[n*64+p*3+2].im;
temp4.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*64+p*3+1].im -
- matrix[x3+i].im*W[n*64+p*3+1].re +
+ matrix[x2+i].re*W[n*64+p*3+0].re -
- matrix[x2+i].im*W[n*64+p*3+0].im -
- matrix[x4+i].re*W[n*64+p*3+2].re +
+ matrix[x4+i].im*W[n*64+p*3+2].im;
matrix[x1+i].re = temp1.re;
matrix[x1+i].im = temp1.im;
matrix[x2+i].re = temp2.re;
matrix[x2+i].im = temp2.im;
matrix[x3+i].re = temp3.re;
matrix[x3+i].im = temp3.im;
matrix[x4+i].re = temp4.re;
matrix[x4+i].im = temp5.im;
}
p++;
}
f++;
}
Значення imax+1 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 64, 16, 4, 1. На першому ярусі є 64 групи операцій по 4 відліка кожна, на другому – 16 груп і збірка ведеться по 16 відліків і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2, х3, х4. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляю вже безпосередньо групу.
Змінні temp1, temp2, temp3, temp4 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаю чого множника для даної базової операції.
Висновки
Під час виконання курсового проекту було розглянуто приклад реалізації обчислювальної системи, в основі якої лежить алгоритм швидкого перетворення Фур’є за основою 4. Дана система обробляє вхідний сигнал, що є 32-розрядним і надходить з тактом, який дорівнює 20 нс. Вхідні дані оновлюються кожні 0.5 мс і представляються 256-ма вхідними відліками, що містять дійсну та уявну частину. Роботою сигнального процесора ADSP-21060 керує вузол керування, що є спеціалізо...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора