Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка процессора ШПФ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Курсовий проект
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
ІКТА
Кафедра ЕОМ
Курсовий проект
з дисципліни
«Методи, алгоритми та засоби цифрової обробки сигналів та зображень»
на тему:
«Розробка процессора ШПФ»
Львів-2007
Завдання
Варіант №
Розробити процесор ШПФ з такими вхідними даними:
Тип процесора
ADSP-21060
Кількість точок
256
Основа ШПФ
4
Прорідження
часове
Розрядність вхідних даних
32
Такт поступлення вхідних даних
20 нс
Час обробки
0.5 мс
Анотація
В даному курсовому проекті розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для сигнального процессора ADSP-21060 для 32-розрядних вхідних даних з часовим прорідженням, детально описано механізми обчислення швидкого перетворення Фур`є за заданною основою, властивості та основні характеристики процесора, на якому планується реалізація, підраховано часові ресурси для виконання обчислення, створена функціональна схема системи та написана програма, що реалізує вказаний алгоритм ШПФ на заданому процесорі.
Зміст
. Вступ
5
1. Теоретичний розділ
6
1.1.Характеристики сигнального процесора ADSP-21060
6
1.2 Опис ШПФ
9
2. Аналіз блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора
21
3. Розрахунковий розділ
23
4. Розробка функціональної схеми
25
5. Розробка програми виконання заданої функції
29
Висновки
32
Література
33
Вступ
Аналіз Фур'є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур'є (фактично існує кілька варіантів таких перетворень) дозволяє співставити сигналу, заданому в часовій області, його еквівалентне представлення в частотній області, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур'є дозволяє визначити відповідний сигнал у часовій області.
Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур'є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур'є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
1.Теоретичний розділ
1.1. Характеристики сигнального процесора ADSP-21060
1.1.1.Призначення ADSP-21060.
ADSP-21060 SHARC – комп’ютер із супергарвардською архітектурою , що є високо продуктивним 32-розрядним цифровим сигнальним процесором для обробки прикладних програм мови, звуку, графіки і растрових зображеннь. SHARC є системою на кристалі, оскільки базується на ядрі сімейства ADSP-21000, додаючи двохпортову пам’ять на чипі SRAM, інтегровані зовнішні пристрої вводу-виводу з підтримкою розподілених шин вводу-виводу. Завдяки кешу інструкцій процесор може виконувати майже кожну команду в одному (окремому) циклі. Чотири незалежних шини для даних, команд та шин вводу-виводу плюс перехресні переключення між зв’язками пам'яті – все це включає супергарвардська архітектура ADSP-21060.
ADSP-21060 SHARC представляє собою новий стандарт інтегрування для цифрових сигнальних процесорів, комбінуючи високо ефективне з плаваючою крапкою ядро DSP з вбудованим інтерфейсом хост-процесора, контролером прямого доступу до пам’яті, послідовними портами, link-портами, та із загальнодоступними шинами в багатопроцесорному режимі.
1.1.2.Властивості ADSP-21060.
Чотири незалежних шини для вибірки даних, інструкції, і шини вводу-виводу.
32 бітні з рухомою комою обчислювальні блоки стандарту ІЕЕЕ, вузол множення, ALU, та зсувач.
Двопортова SRAM на кристалі та вбудований процесор вводу – виводу для периферії – складають System-оn-а-сhіp.
Вбудовані засоби мультиобробки.
40 MІPS, 25 ns цикл виконання інструкцій, кожна інструкція виконується за один цикл.
80 MFLOPS – постійна продуктивність двох генераторів адреси та даних з частково-зворотнім адресуванням.
Ефективний програмований засіб впорядкованого планування з нульовим переповнюючим циклом.
ІEEE JTAG стандарт 1149.1 тестових портів доступу та емуляції на кристалі.
32-бітний з фіксованою точністю та 40-бітний з розширюваною точністю ІEEE формати даних з рухомою комою, і 32 розрядний формат даних з фіксованою крапкою.
Одноциклові операції множення і арифметико-логічні виконуються паралельно із вибіркою даних чи інструкцій з пам’яті.
Двопортова 4Мbit SRAM є доступною як для ядра процесора, так і для DMA.
4 Gіgawords зовнішня пам’ять підтримує сторінковий режим доступу.
На рис.1 зображена блок-діаграма процесора ADSP-21060, на якій показані всі його основні вузли та зв’язки між ними. Основними вузлами є:
32-розрядні з рухомою комою обчислювальні блоки – АЛП, вузол множення, зсувач;
регістровий файл даних;
генератори адреси даних (DAG1,DAG2);
програмний автомат (Program Sequencer) та кеш інструкцій;
періодичний таймер;
двопортова SRAM;
зовнішній порт для зв'язку із зовнішньою пам'яттю та периферійними пристроями;
інтерфейс хост процесора та багатопроцесорний інтерфейс;
контролер DMA;
послідовні порти;
link-порти;
JTAG тест;
ADSP-21060 – процесор з модифікованою гарвардською архітектурою, що містить 4Мбітну SRAM на кристалі, яка складається з двох блоків по 2 Mбіти кожен, і яка може бути сконфігурована для зберігання різних комбінацій інструкцій і даних. Подвійний доступ (тобто в один момент часу може відбуватися операція запису і читання) до кожного блоку пам'яті відбувається в єдиному циклі ядром процесора, процесором вводу/виводу чи контролером DMA.
В ADSP-21060 пам'ять може бути сконфігурована максимум з 128Кслів по 32-біти , з 256Кслів по 16-бітів для даних, та 80Кслів по 48-біт для інструкцій (чи 40-бітові дані), чи з різних комбінацій довжин слів, які поміщаються у 4Мбіти. Але до пам'яті можна звертатися лише по 16-, 32-, чи 48бітних шинах.
У режимі мультиобробки дозволяється підключення шістьох процесорів ADSP-21060 і паралельне їх функціонування. Єдиний адресний простір дозволяють прямі міжпроцесорні доступи до внутрішньої пам'яті кожного ADSP-21060. Розподілена логіка арбітражу шини керує даним режимом і розподіляє ресурси процесорів між собою. Арбітраж надає шині вибраний чи встановлений пріоритет. Максимальна швидкодія при міжпроцесорній передачі даних складає 240 Mbytes/s по link-портах чи по зовнішньому порту.
Рис.1.1: блок – діаграма процесора ADSP-21060
1.1.3.Розширення рівня системи (системні покращення)
Процесори сімейства ADSP-21000 мають декілька особливостей, що спрощують розробку системи. Ці доповнення внесені у три ключові області:
архітектурні особливості, що підтримують мови високого рівня та операційні системи;
ІЕЕЕ 1149.1 JTAG, що забезпечує послідовне сканування і емуляцію на кристалі
підтримка ІЕЕЕ форматів з рухомою крапкою.
Мови високого рівня. Архітектура сімейства ADSP-21000 має кілька особливостей, що безпосередньо підтримують компілятори мов високого рівня та операційні системи:
універсальні дані і адреси регістрів файлу
32-розрядні типи даних
великий адресний простір
пре- і пост - модифікація адресування
розміщення циклічного буфера даних без заборони на його розміщення в пам’яті;
стек лічильника команд, стек циклу і стек стану, що розміщенні на кристалі;
Додатково, архітектура сімейства ADSP-21000 розроблена спеціально для підтримання ANSІ-стандарту Numeric C-розширення – це перша трансльована мова, що підтримує векторні типи даних і оператори для числових і сигнальних процесів обробки сигналів.
Особливості послідовного сканування і емуляції. Процесори сімейства ADSP-21000 підтримують стандарт ІЕЕЕ1149.1 Joint Test Action Group (JTAG) для відлагодження системи. Цей стандарт визначає метод спеціального послідовного сканування стану вводу-виводу кожного компонента в системі. Послідовний порт JTAG також використовується емулятором ADSP-2106XEZ-ІCЕ для отримання можливостей емуляції на кристалі.
Формати ІЕЕЕ. Сімейство ADSP-21000 підтримує ІЕЕЕ формати даних із рухомою крапкою. Це означає, що дане сімейство, можна використовувати з ІEEE-сумісними процесорами без затрат на додаткове обладнання.
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.Опис швидкого перетворення Фур’є з прорідженням в часі
Дискретний матеріальний сигнал у вигляді кінцевої часової послідовності x(nТ) запишемо як x(nТ), де - число відліків, N – число відліків, T - період дискретизації.
N - точкове дискретне перетворення Фур'є (ДПФ) задається формулою:
де X(k) - частотний k-ий відлік чи k-а спектральна складова сигналу (визначає вихідну частотну послідовність, спектр сигналу),
комплексна експонента, W- ядро перетворення.
При зміні значення n*k на величину кратну N ядро не змінюється (у силу періодичності синуса і косинуса). Тобто ядро по верхньому індексу є періодичною функцією з періодом N. Тому замість добутку n*k можна вставити залишок від ділення його на N , тобто (n*k) mod N. Cпектральна функція X(k) також має період N по аргументу k.
Число множень дійсних відліків сигналу на комплексне ядро в (1) дорівнює N2, а число додавань комплексних чисел - (N -1)N. Кількість цих операцій різко зростає із збільшенням N і приводить до занадто великого часу перетворення.
ДПФ стало широко застосовуватися після винаходу швидких алгоритмів, в основі яких лежить принцип зведення багатоточкового перетворення до малоточкового. Один з них (що став уже класичним) називається ШПФ із проріджу-ванням за часом. Цей алгоритм отриманий за умови, якщо N є ступенем числа 2, тобто , де ν - ціле число, ν≥0.
Основні формули перетворення, до яких ми прийдемо, виходять при розбивці суми в (1) на дві суми, що містять відліки з парними і непарними номерами
Власне кажучи ця операція являє собою зміну порядку сумування (перегрупу-вання доданків), від якого сума не міняється.
Можна записати , . З врахуванням цього (2) прийме вигляд:
Зауважимо, що суми в (3) являють собою N/2 - точкові ДПФ часових відліків з парними номерами в першій сумі, і непарними номерами в другій сумі.
Позначимо, згідно з [1],
X(k) = Xν(k) - ДПФ усіх вхідних відліків дискретного сигналу,
вхідних відліків з парними номерами (перше число в нижньому індексі дорівнює ν - 1, а друге - парному числу (нулю)) ,
вхідних відліків з непарними номерами (друге число в нижньому індексі дорівнює непарному числу (одиниці)).
З урахуванням введених позначень одержимо коротку форму запису (3)
Спектри і є періодичними функціями з періодом N/2 (у ядрі перетворення замість N стоїть N/2). Величина називається повертаючим множником і володіє наступною цікавою властивістю
Ця властивість надає при обчисленні з номерами k від N/2 до (N -1) використовувати відповідні значення раніше обчислених з номерами від 0 до (N/2 -1) (потрібно тільки змінити знак).
За звичай формулу (4) розбивають на два співвідношення для зазначених вище номерів і одержують основні формули (базові співвідношення) перетворення Фур'є у вигляді
Базові співвідношення вже можна назвати швидким перетворенням Фур'є (ШПФ), тому що число операцій зменшилося. Число множень матеріальних відліків сигналу на комплексне ядро дорівнює . До цього потрібно додати множень комплексних чисел. Число додавань дорівнює
Процес розбиття за схемою базових співвідношень можна продовжувати до тих пір, доки не прийдемо до перетворень Фур'є одиничних відліків (що збігаються із самими відліками). Необхідне число операцій при цьому буде значно менше. У такому вигляді це ШПФ називають ШПФ із проріджуванням за часом.
Для пояснення процесу розбиття розглянемо більш детально, приклад ШПФ при .
Позначимо оператор ДПФ визначених вхідних відліків через F і запишемо відповідності між символами ДПФ, введеними вище, і цим оператором.
Зв'язок між ДПФ із великим і меншим числом точок відповідно до базових співвідношень записується в такий спосіб:
Роботу ШПФ можна пояснити графічно, якщо базові співвідношення, записані в дуже короткій формі
або зобразити графом
Верхній стрілці відповідає додавання, а нижній - віднімання. Попередньо bm-1 домножається на множник повороту WN.
Використовуючи вищенаведене і розташовуючи символи ДПФ у впорядковано-му вигляді, зобразимо ШПФ геометрично за допомогою графа.
Рис.1.2.1. Граф ШПФ із проріджуванням за часом при N=8
Відзначимо, що відліки вхідної послідовності переходять у відповідні ДПФ нульового рівня відповідно до інверсії їхній двійкових номерів (операція називається перестановкою вхідних відліків). Наприклад, десятковий номер 4|10 у двійковому вигляді запишеться як 100|2. Інверсія числа 100|2 (у прочитанні з права на ліво) запишеться як 001|2 = 1|10. Таким чином, вхідний відлік під номером 4 співпаде з першим ДПФ X0,1(0). Перестановку для всіх відліків можна показати стрілками переходу: 0 → 0, 1 → 4, 2 → 2, 3 → 6, 4 → 1, 5→ 5, 6 → 3, 7 → 7.
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-21060 є 4Мбіта, тобто може бути сконфігурована наступним чином: 218 слів по 16 розрядів (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...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора