МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет "Львівська політехніка"
Кафедра ЕОМ
Курсовий проект
з курсу “ Методи, алгоритми, засоби цифрової обробки сигналів та зображень”
на тему:
"Розробка алгоритму ДКП на процесорі TMS320C50"
Варіант №9
Львів 2005
Анотація
В даному курсовому проекті описується один із алгоритмів ДКП, а саме 8192-х точкове ДКП. Проводиться розрахунок параметрів алгоритму ДКП та на їх основі будується граф обчислення ДКП. Далі виконується синтез проекту на мікропроцесорі TMS320C50 та оцінка отриманих результатів.
Зміст
Вступ 4
Теоретичний розділ 5
Характеристики процесора TMS320C50 5
Дискретне Косинусне Перетворення 8
Швидкі прямі алгоритми дискретного косинусного перетворення з косинусннми множниками 8
Аналітичний огляд 9
Алгоритм ДКП 9
Побудова графу обчислення ДКП 10
Двійково-реверсна перестановка вихідних даних 13
Розрахунковий розділ 13
Розрахунок часових параметрів 13
Часові діаграми вхідних сигналів 14
Розрахунок об’єму мікросхем пам’яті 14
Розробка функціональної схеми 15
Розробка структурної схеми пристрою 15
Розробка пристрою керування 15
Опис роботи функціональної схеми 16
Розробка програми виконання заданої функції 16
Програма Дискретного Косинусного Перетворення 17
Висновки 19
Література 20
Вступ
Для зменшення надлишковості подання цифрових сигналів та зображень використовуються лінійні унітарні ортогональні дискретні перетворення. Відомо, що за критерієм середньоквадратичної похибки серед всіх ортогональних перетворень оптимальним є перетворення Карунена-Лоева, але для нього не існують швидкі алгоритми. Порівняно з іншими дискретними перетвореннями з швидкими алгоритмами ДКП найефективніше концентрує енергію сигналу в невеликій частині його спектральних елементів і тим забезпечує досягнення великого коефіцієнта ущільнення даних. Крім того ДКП може ефективно використовуватись при обчисленні ДПФ та ДКПФ.
На даний час розроблені два методи побудови алгоритмів швидкого косинусного перетворення (ШКП). Перший з них ґрунтується на алгебраїчній структурі матриці ДКП. Основний недолік відомих алгоритмів цього підходу полягає у використанні косекансних множників, які негативно впливають на точність перетворення, і в надлишковості за кількістю операцій переміщення даних. Другий метод - побічний (непрямий), він передбачає використання інших дискретних перетворень та їх швидких алгоритмів. Серед останніх найчастіше вживаються алгоритми ДКП і ШПХ . Тут використовуються косинусні множники, які покращують характеристики точності, але при цьому алгоритми першого підходу мають менші обчислювальні затрати.
У даному розділі синтезовані алгоритми прямого методу ШКП з косинусними множниками, рівноцінні за обчислювальними затратами з відомими алгоритмами з косекансними множниками, і проведена їх структурна оптимізація. Вона дозволяє зменшити кількість операцій переміщення даних і реалізувати основні обчислення за схемою алгоритму ДКП Кулі-Тьюкі за основою два, включаючи його варіант з постійною структурою графа на кожному з етапів перетворення. Одержані також алгоритми побічного методу на основі алгоритмів ШПХ і проведений порівняльний аналіз двох методів.
Завдання до курсового проекту.
Варіант№9
Розробити та синтезувати на процесорі TMS320C50 пристрій для обчислення 8192-ти точкового ДКП. Розрядність вхідних даних складає 16 біт, такт поступлення вхідних даних складає 30 нс, час обробки становить 18,0мс.
Теоретичний розділ
Характеристики процесора TMS320C50
• Високопродуктивна плаваюча крапка цифрового сигнального процесора (DSP)
- TMS320C50
Час циклу інструкції 20-,25-,35- нс при 5 В напруги
Час циклу інструкції 25-,40-,50- нс при 3 В напруги
• 16-розрядний високопродуктивний CPU
• 16*16-біті дії (множення/додавання) над цілим числом і плаваючою крапкою відповідно
• Інтегрований 2K,4К, 8К,16К, 32К х16-розрядний ПЗП з одинарнимним доступом
• Інтегрованй один 1K, 3К, 6К, 9К х16-розрядна ОЗП з одинарнимним доступом (SARAM)
• Інтегрованй один 1K, 3К, 6К, 9К х16-розрядна ОЗП з подвійним доступом (DARAM)
• Повнодуплексний синхронний серійни порт для кодування/декодування
• Мультиплексований в часі серійний порт (TDM)
• Інтегрований Таймер для контролю операцій
• Високопродуктивна технологія CMOS
• 5 видів корпусів :
- 100-вивідний корпус (PJ Suffix)
- 100-вивідний корпус (PZ Suffix)
- 128-вивідний корпус (PBK Suffix)
- 132-вивідний корпус (PQ Suffix)
- 144-вивідний корпус (PGE Suffix)
• Буферезований серійний порт
• Інтерфейс хост порта
• Пересилка блоків для управління Даними/Програмами
• Інтегрований логічний емулятор
• Малоспоживчі режими:
- 47 мА (2.35 мА/MIP) на 5 В, середня частота 40 МГц
- 23 мА (1.15 мА/MIP) на 3 В, середня частота 40 МГц
• IEEE стандарт 1149.1 JTAG
Абсолютны максимальні діапазони роботи процесора
Діапазон вхідної напруги - 0.3 ÷ 7 В
Діапазон напруги виходу - 0.3 ÷ 7 В
Операційний діапазон температури 0° ÷ 85°C
Діапазон температури зберігання - 55 ÷ 150°C
Рис. 1 Функціональна блок-діаграм процесора TMS320C50
Таблиця 1. Опис виводів процесора TMS320C50
Назва виводу
Опис
Інтерфейс головної шини
D15–D0
Дво направлена 16-бітна шина даних
A15–A0
Одно направлена 16-бітна шина адреси
R/W
Вихідний сигнал читання/запис. Читання = «1», запис = «0»
RD, WE
Сигнали стробу запису і читання
STRB
Сигнал стробу
READY
Вхідний сигнал готовності. Вказує про завершення транзакції
PS, DS, IS
Вибірка програмного простору, простору даних і простору В/В
Керуючі сигнали
RS
Вхідний сигнал початкового скиду
INT4–INT1
Вхідні сигнали запиту на переривання
IACK
Вхідний сигнал підтвердження запиту на переривання
NMI
Немасковане зовнішнє переривання
HOLD
Вхідний сигнал запиту на захват шини
HOLDA
Вихідний сигнал підтвердження запиту на захват шини
XF
Зовнішній флаг
Дискретне Косинусне Перетворення
Пряме та обернене ДКП послідовності дійсних чисел х(п), 1=0,1,...,N-1. відповідно описуються виразами:
(1)
(2)
де С =cos(π(2n+l)k/(2N)), n,k=0,l...,N-l,- елементи матриці ДКП; P0=l/N,Pk=2/N для k≠0. Оскільки множення на Рk (у загальному випадку на степінь двійки) в обчислювальному аспекті не має принципового значення, то його можна опустити.
Швидкі прямі алгоритми дискретного косинусного перетворення з косинусннми множниками
Найменшу кількість арифметичних операцій мають алгоритми ШКП, що грунтуються на алгебраїчній структурі його матриці . У них використовуються базова операція (БО) "дійсний метелик", показані на рис.2 де a і b дійсні числа, RnN - косекансні множники, .
Рис.2 Базова операція «Дійсний метелик»
Відомим недоліком алгоритмів з косекансними множниками є їх чутливість до похибки заокруглення тому що при наближенні п до N/2 різко зростає RnN . Тому розглянемо алгоритми прямого та оберненого ШКП з косинусними множниками RnN : RnN = CnN.
Алгоритм 1, ШКП з косинусними множниками. Елементи матриці ДКП мають такі властивості
n=0,l...,N/2-l
(3)
Враховуючи першу з них, для парних k приведемо (1) до вигляду
k=0,l...,N/2-1
(4)
За другою властивістю для непарних елементів L(k) приведемо (1) до вигляду
k=0,l...,N/2-1
(5)
Нехай B(k)= ДКПN/2{b(n)}, b(n)=(x(n)-x(N-l-n))C, C , n=0,1,..,N/2-1. Безпосередньою перевіркою, використавши формулу суми косинусів cosα+cosβ = 2cos[(α+β)/2]соs[(α-β)/2] і (5),
L(l)=B(0), L(2k+l)=2B(k)-L(2k-l), k=l,2.....N/2-1.
(6)
(7)
Аналітичний огляд
Алгоритм ДКП
1.Знаходимо елементи послідовностей a(n) і b(n), a(n)=x(n)+x(N-1-n),
b(n)=(x(n)-x(N-l-n))C , n=0,1,..,N/2-1.
2. Виконуємо N/2-точкові ДКП послідовностей a(n) і b(n) - Знаходимо відповідно L(2k) і В(k), k=0,1,..,N/2-1.
3. За виразами (6) відтворюємо непарні елементи L(k).
4. На основі попередніх кроків повторюємо розбиття одержаних ДКП меншої довжини до двоточкових, які виконуємо згідно рис.3
На рис.3 у вигляді направленого графа відображена структура алгоритму 1 для N=16. В N -точковому блоці сумування обчислення виконується за виразами (6) з врахуванням, що його входи і виходи з'єднані у двійково-інверсному порядку індексів. Крім того, з метою вилучення додаткової перестановки елементів b(n), при синтезі графа використане співвідношення (8),
L(l)=B(0), L(2k+l)=2(-1)kB(k)-L(2k-l), k=l,2.....N/2-1 (8)
де B(k)=ДКПN/2{b(N/2-1-n)} одержане з (6) на основі властивості ДКП:
якщо L(k) і LT(k) відповідно N -точкові ДКП послідовностей x(n) і x(N-l-n), тоді:
LT(k)=(-1)kL(k), k=0,l,..,N-l. (9)
Заміна (6) на (8) дозволяє скоротити N/4 операцій переміщення даних при одному звертанні до N -точкової процедури розбиття алгоритму 1. При реалізації із заміщенням кожна з таких операцій потребує трьох пересилань даних, без заміщення — двох. У загальному випадку в N -точковому алгоритмі сумарно скорочується N/4 (log2 N—1) вказаних операцій. Поступаючи аналогічно, на основі (9) можна скоротити кількість пересилань і у відомому алгоритмі ДКП. Другий шлях такого скорочення полягає в одночасному обчисленні а(n), b(n). a(N/2-n) і b(N/2-n). Проте при реалізації із заміщенням він вимагає чотирьохточкової БО, що складається з двох двоточкових операцій виду (рис.2).
Побудова графу обчислення ДКП
Для побудови графу N-точкового ДКП необхідно провести розрахунки кількості ярусів графу та кількості метеликів в кожному ярусі. Кількість ярусів графа позначимо змінною Kr, вона розраховується за формулою:
(10)
де N в нас кількість вхідних відліків. Згідно з завданням на курсовий проект кількість відліків складає 8192 точки, відповідно до формули (10) . Кількість метеликів Km на одному ярусі можна розрахувати за наступною формулою:
(11)
Для нашого випадку . Відповідно до завдання ми маємо розробити ДКП, це означає про надходження до першого ярусу графа вхідних відліків в прямому порядку, а на виході останнього ярусу ми отримаємо відліки ДКП в реверсивному порядку, тобто щоб отримати вірні значення ДКП відповідним до них вхідним відлікам, вихідну послідовність відліків ДКП необхідно переставити в прямих порядок.
Як аналогія побудови графу ДКП на 8192 точок використаємо граф на 16 точок (рис. 3).
Двійково-реверсна перестановка вихідних даних
Розглянемо двійкове представлення номерів елементів і займаних ними місць при реверсивній перестановці біт. Елемент з номером 0 (двійкове 0000) після всіх перестановок займає позицію 0 (0000), елемент 8 (1000) - позицію 1 (0001), елемент 4 (0100) - позицію 2 (0010), елемент 12 (1100) - позицію 3 (0011). І так далі. Неважко помітити зв'язок між двійковим представленням позиції до перестановок і після всіх перестановок: вони дзеркально симетричні. Двійкове представлення кінцевої позиції виходить із двійкового представлення початкової позиції перестановкою бітів у зворотному порядку. І навпаки.
Цей факт не є випадковістю для конкретного N, а є закономірністю. В асемблері ця операція називається циклічним зсувом вправо (ror), якщо N - це ступінь двійки. Назва операції походить з того факту, що береться двійкове представлення числа n, потім усі біти, крім молодшого (самого правого) переміщаються на 1 позицію вправо. А молодший біт переміщається на місце, що звільнилося, самого старшого (самого лівого) біта.
Розрахунковий розділ
Розрахунок часових параметрів
Для побудови функціональної схеми пристрою, який виконує ДКП на процесорі TMS320C50, необхідно розрахувати час обрахунку мікропроцесором однієї послідовності вхідних відліків. Якщо час виконання процесором даного перетворення, перевищує обмеження на час виконання перетворення відповідно до варіанта tобр= 18мс необхідно розпаралелювати виконання процесу обчислення. Тобто використовувати при побудові схеми більше одного процесора.
Обчислювальні затрати.
В N - точковому блоці сумування необхідно N/2-1 додавань, а при розбитті N-точкового перетворення на два N/2 - точкових використовується N/2 БО "дійсний метелик", що вимагає N/2 множень і N додавань. Отже, кількість дійсних множень μm і додавань αm в N=2m - точкових алгоритмах дорівнює: μm= μm-1+N/2, αm=2αm-1+3 N/2 - 1 або
μm=2m-1 m, αm=2m-1(3m-2)+1
N=8192 ( m=log2N=13
μ13=214*13= 53248 (множень)
α13=212(3*13-2)+1=151 553 (додавань)
μ13 + α13 = 204 801 (операцій)
Загальний час обчислення = 204 801 * 20нс = 4 016 020нс = 4,1мс
Запису/читання пам’яті :1 метелик => 3 читання і 2 записи до пам’яті.
К-ть метеликів =4016*13=53 248 метеликів.
Загальний час 5*53 248*20 нс = 5,33 мс => 9.43 мс < 18мс
Оскільки, даний час менший ніж 18мс для обрахунку ДКП згідно варіанту вистачає одного мікропроцесора.
Часові діаграми вхідних сигналів
До нашого пристрою надходять 5 вхідних сигнали: синхронізуючі імпульси (SYN), сигнал стробу даних (STRB), запис до пам’яті (WE), скид (RESET) та дані (DATA15-0), які поступають в паралельному виді. Часові діаграми даних сигналів зображені на рис. 5.
Рис. 5 – часові діаграми вхідних сигналів
Оскільки в нас згідно варіанту розрядність даних складає 16 біт, відповідна кількість імпульсів надходить з входу DATA протягом тривалості стробу сигналу STRB.
Розрахунок об’єму мікросхем пам’яті
Для зберігання вхідної послідовності необхідно використовувати зовнішній оперативно-запам’ятовуючий пристрій. Так як вхідна послідовність містить 8192 16 бітових елементи, нам необхідно при побудові використовувати мікросхему оперативної пам’яті не менше 8Кслів з розрядністю шини данин 16 біт.
При розрахунку ДКП ми використовуємо вагові коефіцієнти, значення яких, вже попередньо обчисленні, ми запишемо в постійний запам’ятовуючий пристрій, кількість повертаючи множників – 8192 значень.
Розробка функціональної схеми
Розробка структурної схеми пристрою
Для побудови структурної схеми пристрою необхідно проаналізувати стадії проходження сигналу: від вхідної послідовності до кінцевого результату. На першому етапі вже шістнадцять бітове значення ми маємо зберегти в пам’яті для подальшої обробки. На другому етапі, коли всі 8192 числа буде записано - керування отримує процесор, який виконує ДКП та видає результат, також необхідно врахувати, що при обчисленні ДКП необхідно значення вагових коефіцієнтів. Для зменшення обрахунків, а відповідно і часу загального обрахунку процесором, значення вагових коефіцієнтів, вже попередньо-обраховані, будуть знаходитись у постійному запам’ятовуючому пристрої.
Отже проаналізувавши всі етапи ми можемо виділити наступні структурні одиниці: пристрій керування(CU) для формування керуючих сигналів та адреси комірки пам’яті в яку необхідно записати число, оперативний запам’ятовуючий пристрій(RAM), постійний запам’ятовуючий пристрій(ROM), процесор(CPU), схема початкового встановлення пристрою(R) та схема синхронізації(S). Отриману схему зображено на рис. 6.
Рис. 6 – структурна схема пристрою
Розробка пристрою керування
Пристрій керування в нашому проекті має виконувати наступні функції:
формувати адресу комірки пам’яті, в яку необхідно записати число;
формувати сигнал переривання;
Розглянемо реалізацію кожної функції окремо.
В пристрою керування використовується 4 синхронних лічильника, включені каскадно. На вхід (+1) першого лічильника подаються тактові імпульси (SYN). Лічильники дораховують до 8192 і скидаються в «0». Формується сигнал переривання .
На виході лічильників використовуються буфери, які відділяють шину адресу і даних процесора від вхідних даних і сформованих адрес лічильником.
Опис роботи функціональної схеми
Робота схеми починається після того, як сигнал скидання переходить в стан логічного „0”. Зовні подаються сигнали стробу(STRB = «1»), запису даних(WE = «0») і самі дані(DATA). Буфери готові до передачі даних і адрес до пам’яті. Коли лічильник дорахує до 8192 він сформує сигнал переривання і скине лічильники в «0». Буфери по сигналу стробу відєднаються від шини даних і адреси.
Для вибірки потрібної пам’яті (ПЗП чи ОЗУ) використовується виходи з процесора (див табл. 2).
Табл. 2
Вивід
Пам’ять
ПЗП
ОЗП
Процесор отримавши сигнал переривання почне зчитувати дані з ОЗУі виконує Дискретне косинусне перетворення, причому записуючи проміжні дані в тому ж ОЗУ. Після завершення перетворення процесор формує вихіднй сигнал підтвердження про переривання , який оповіщає зовнішній пристрій про початок передачі нових пакетів даних. Після цього починається новий цикл обробки сигналу.
Розробка програми виконання заданої функції
Наведемо блок-схему алгоритму програми виконання обчислення:
Програма Дискретного Косинусного Перетворення
на асемблері для TMS320C50
* Програма ДКП
.global FCT
.global M
.global COS_TAB
.global COEFF
.text
FCTSIZE .word M
_COS .word COS_TAB
_DATA .word COEFF
FCT:
LDI @FCTSIZE, AR0
LDI @FCTSIZE, BK
LDI @_DATA, AR6
LDI @_COS, AR7
LDI AR1, AR0
LDI -1, IR0
LDI AR6, AR1
ADDI3 AR6, AR0, AR2
SUBI 1, AR2
LSH3 IR0, AR0, AR3
LDI 1, AR5
ADDI AR6, AR3
ADDI3 IR0, AR3, AR4
ADDI3 IR0, AR5, RC
RPTB END_CENTER_LOOP
OUTSIDE_LOOP:
MIDDLE_LOOP:
LDF *AR2, R2
|| LDF *AR3, R3
SUBF3 *AR3. *AR4, R1
SUBF3 *AR2. *AR1, R0
MPYF3 R1, *++AR7, R1
|| ADDF3 R3, *AR4, R3
MPYF3 R0, *--AR7, R0
|| ADDF3 R2, *AR1, R2
STF R1, *AR2++(IR1)%
|| STF R3, *AR4++(IR1)%
END_CENTER_LOOP:
STF R0, *AR3++(IR1)%
|| STF R2, *AR1++(IR1)%
ADDI3 IR0, AR5, RC
ADDF3 *AR3++, *AR2--, R0
CMPI AR3, AR2
LDI 2, IR0
LDI AR6, AR1
ADDI 4, AR1
LDI AR1, AR2
LDI 8, IR1
LAST_OUTSIDE_LOOP:
LDI AR2, AR4
LSH -1, AR5
LDI AR5, RC
ADDF3 *AR2++(IR0), *AR4++(IR0), R0
LDI AR1, R4
SUBI 1, RC
NOP *AR4++(IR0)B
LDI AR2, AR3
RPTB END_INSIDE
LAST_INSIDE_LOOP:
ADDF *AR1, *AR2++(IR1)%, R0
ADDF *AR3, *AR4++(IR1)%, R1
STF R0, *AR1++(IR1)%
END_INSIDE:
STF R1, *AR3++(IR1)%
ADDF *AR1++(IR0)B, *AR2++(IR0)%, R0
ADDF *AR3++(IR0)B, *AR4++(IR0)%, R0
ADDF *AR3++(IR0)B, *AR4++(IR0)%, R0
ADDF *AR1++(IR0)B, *AR2++(IR0)%, R0
CMPI R4, AR4
BNED LAST_INSIDE_LOOP
LDI AR5, RC
SUBI 1, RC
OR 0100H, ST
RPTB LAST_BLOCK
ADDF3 *AR1, *AR2++(IR1)%, R0
LAST_BLOCK:
STF R0, *AR1++(IR1)%
LSH 1, IR0
ADDI IR0, R4
CMPI 1, AR5
BGTD LAST_OUTSIDE_LOOP
BGTD MIDDLE_LOOP
ADDF3 *AR1++, *AR4--, R0
ADDI 2, AR7
OR 0100H, ST
LSH -1, IR1
LDI AR6, AR1
ADDI IR0, AR6, AR2
ADDI IR1, AR2
CMPI 2, IR1
BGTD OUTSIDE_LOOP
LSH 1, AR5
SUBI3 IR0, AR4, AR3
ADDI3 IR0, AR5, RC
LDI 4, IR1
ADDI 1, AR3
LSH -1, AR5
ADDI 3, AR4
ADDI3 IR0, AR5, RC
MPYF3 *AR7,*+AR7, R4
RPTB END_2ND_LOOP
SUBF3 *AR2, *AR1, R0
SUBF3 *AR4, *AR3, R1
MPYF3 R0, R4, R0
|| ADDF3 *AR3++(IR1), *AR4++(IR1), R3
MPYF3 R1, R4, R1
|| ADDF3 *AR1++(IR1), *AR2++(IR1), R2
MPYF3 R3, *+AR7, R3
|| STF R0, *-AR2(IR1)
MPYF3 R2, *+AR7, R2
|| STF R1, *-AR4(IR1)
ADDF3 R3, R1, R3
STF R2, *-AR1(IR1)
END_2ND_LOOP:
STF R3, *-AR3(IR1)
LDI R4, AR2
LDI R4, AR1
LSH 1, IR1
LDF *AR6, R0
BEQD DON’T_STORE
LSH 24, AR5
SUBI3 AR5, *AR6, AR1
NOP
STI AR1, *AR6
DON’T_STORE:
RETS
* таблиця косинусів
.global COS_TAB
.global M
M .set 8192
.data
COS_TAB
.float 0.5024193
.float 5.1011487
.float 0.5224986
.float 1.7224471
.float 0.5669440
.float 1.0606777
…..
.end
Висновки
При виконанні даного проекту було проаналізовано алгоритм Дискретне косинус не перетворення та на його основі з використанням мікропроцесора TMS320C50 було розроблено пристрій для виконання дискретного косинусного перетворення на 8192 16-розрядних точки. Було розроблене програмне забезпечення на мові асемблер, яке було перевірене за допомогою симулятора процесора TMS320C50, а отримані результати були перевірені за допомогою тестової програми.
Література
Горбунов В.Л., Панфилов Д.И., Преснухин Д.Л. Микропроцессоры. Основы построения микро-ЭВМ. – М.:Высш.шк., 1984. – 144 ст.
Конспект лекцій з курсу “Мікропроцесорні системи”(
Конспект лекцій з курсу “Цифрова обробка сигналів”
Конспект лекцій з курсу “Вимірювальні обчислювальні системи”(
Якубовсий С.В.Аналоговые и цифровые интегральные микросхемы: Справочное пособие. – М. : Радио и связь, 1985. – 432 ст.
Нефедов А.В. Зарубежные интегральные микросхемы для промышленной электронной аппаратуры: Справочник. – М.: Энергоатомиздат, 1989. – 288 ст.
Тарабрин Б.В. Интегральные микросхемы: Справочник. – М.: Радио и связь, 1984 – 528 ст.
Четверткова И.И., Смирнова В.Ф. Справочник по электрическим конденсаторам – М.: Радио и связь, 1983 – 576 ст.
TMS320C50 User’s manual