Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка процесора ШПФ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2003
Тип роботи:
Курсова робота
Предмет:
Проектування алгоритмів і засобів цифрової обробки сигналів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
кафедра ЕОМ
Курсовий проект
з курсу: „Проектування алгоритмів і засобів цифрової обробки сигналів”
Тема: “Розробка процесора ШПФ”
Львів – 2003 р.
Завдання до курсового проекту.
Варіант № 49
Тип процесора: TMS320C25
Кількість точок: 1024
Основа ШПФ: 4
Прорідження в часовій області.
Розрядність вхідних даних: 16
Такт поступлення вхідних даних: 50ns
Час обробки: 1,8ms
Анотація.
Зміст.
Вступ _________________________________________
Теоритичний розділ ______________________________
2.1. Алгоритм ШПФ з основою 4__________________
2.2. Опис процесора TMS320C25__________________
Аналіз блок-схеми виконання заданої
функції обробки сигналів та зображень
на заданому типі процесора ____________________
Розрахунковий розділ _________________________
Розробка функціональної схеми ________________
Розробка програми виконання заданої функції ___
Висновки ____________________________________
Список використаної літератури _______________
1.Вступ.
При обробці сигналів у багатьох випадках доводиться виміряти спектри. Так, в задачах розпізнавання мови спектральний аналіз, як правило, передує подальшій спеціальній обробці. В системах стиснення смуги мовних сигналів спектральний аналіз є звичайно основною операцією. В гідроакустичних системах для виявлення надводних кораблів і підводних човнів вимагається проводити складний спектральний аналіз. В системах радіолокацій для отримання інформації про швидкість мети також доводиться виміряти спектр.
Слід мати на увазі, що поняття «спектральний аналіз» включає велике число різних вимірювань. В широкому значенні його можна визначити як вимірювання, яке дає точні або наближені значення z-перетворення дискретного сигналу для заданих значень z». Створення адекватної теорії спектрального аналізу утруднено тією обставиною, що на практиці всі спектральні вимірювання проводяться на кінцевих тимчасових інтервалах, довжина яких звичайно визначається інтуїтивно або на основі накопиченого досвіду. Наприклад, «спектр» мовного сигналу дуже сильно залежить від часу, змінюючись приблизно із швидкістю зміни параметрів мовного тракту (біля 10раз за секунду). Не дивлячись на це, в багатьох прикладних задачах короткочасний спектр мовного сигналу є однією з найважливіших характеристик.
Набір алгоритмів, званих алгоритмами швидкого перетворення Фурьє (ШПФ), включає різноманітні методи зменшення часу обчислення дискретного перетворення Фурьє (ДПФ). Оскільки обчислення ДПФ є основною операцією в більшості задач спектрального аналізу, то використовування ШПФ в деяких що зустрічаються на практиці випадках, дозволяє прискорити обчислення ДПФ в 100 і більш раз в порівнянні з методом прямого обчислення ДПФ, має надзвичайно важливе значення і повинне розглядатися як невід'ємна частина застосування методів цифрової обробки сигналів для спектрального аналізу.
Той факт, що одновимірний масив чисел можна виразити через двовимірний масив більш ніж одним способом, пояснює різноманіття алгоритмів ШПФ. Звідси витікає, що математична операція переходу з одновимірного простору в двовимірний є основою всіх алгоритмів ШПФ. При такому єдиному підході до алгоритму ШПФ його різні варіанти можуть бути отриманий порівняно простим способом.
2.Теоретичний розділ.
2.1. Алгоритм ШПФ з основою 4
Якщо число N є степенем 4, то його можна записати як (N/4) х 4; аналогічно N/4 = (M/16) X 4 і т.д. В результаті елементи початкового одновимірного масиву можна розположити таким чином, щоб елементарними операціями були чотирьохточкові ШПФ. Простий приклад для N = 16 показаний на рис.2.1.
EMBED PBrush
Рис.2.1. 16-точкове ШПФ з основою 4.
Рис. 2.2. 16-точкове ШПФ з основою 4 з проріджуванням по частоті, прямим порядком на вході і четвірково-інверсним на виході.
Для цього випадку достатньо одного проріджування, здійснюваного шляхом представлення одновимірного масиву матрицею розміром (4 X 4). Виконувані операції можна представити схемою рис.2.2.
Рис. 2.3. 16-точкове БПФ з основою 4 з проріджуванням за часом і із заміщенням, нормальним порядком на вході і четвірково-інверсним на виході.
Таким чином, на рис.2.2 ці кружки представляють чотирьохточкові ШПФ, а множення на повертаючі множники зображені, як і на схемах ШПФ з основою 2, стрілками. Елементи пам'яті також представлені крапками і пронумеровані зверху вниз, причому номери регістрів не приводяться.
По аналогії з ШПФ з основою 2 можливі варіанти ШПФ з основою 4 з проріджуванням по частоті і за часом. Перший варіант представлений на рис. 2, а другий — на рис. 2.3.
Цікаво порівняти кількість арифметичних операцій, виконуваних в схемах рис. 2 і 3 і в будь-якій з 16-точкових структур з основою 2. В другому випадку використовуються 10 нетривіальних комплексних множень (тривіальними є множення на ±1 або на ±J). Аналогічний підрахунок для ШПФ з основою 4 дає вісім таких множень. Таким чином, вже звідси видно, що ефективність різних структур ШПФ з однаковими кінцевими результатами неоднакова. Але рішення питання про те, чи вигідне застосування алгоритму ШПФ з основою 4, залежить у кожному конкретному випадку від великого числа чинників і тут не розглядається.
На рис.2.4 зображена схема алгоритму ШПФ з основою 4 для масиву з 64 відліків. Щоб зрозуміти, яким чином в цьому алгоритмі здійснюється проріджування, вважатимемо, що перші 16 відліків утворюють перший рядок матриці з 16 стовпців і 4 рядків, наступні 16 відліків складають другий рядок і т.д.
Рис. 2.4. 64-точкове БПФ з основою 4 з проріджуванням по частоті, нормальним порядком на вході і четвірково-інверсним на виході.
На першому етапі алгоритму рис.2.4 виконуються 16 чотирьохточкові ДПФ від елементів кожного стовпця. Потім проводяться повороти, причому показники експонент повертаючих множників вказані перед позначенням елементів пам'яті другого етапу. Потім всі чотири рядки проріджуються шляхом формування з них матриць розміром (4 X 4) і перетворяться по схемі 16-точкового БПФ з основою 4, але з іншими повертаючими множниками.
Алгоритм рис. 2.4 можна розглядати як варіант ШПФ з проріджуванням по частоті, оскільки повороти проводяться після ДПФ. Можна побудувати і алгоритм з проріджуванням за часом, але для цього доведеться переходити від матриць меншого розміру до більших матриць.
Алгоритм базової операції ШПФ з основою 4 і проріджуванням за часом можна представити у вигляді :
де А’1 А’2, А’3, А’4 — результати базової операції; А1, А2, А3, А4— вхідні відліки; W1, W2, W3 — комплексні коефіцієнти; J— уявна одиниця, верхній знак перед j відповідає прямому, нижній — зворотному ШПФ. Виділяючи дійсні і уявні частини відліків, одержуємо
2.2. Опис процесора TMS320C25
Діапазон Температури –55°C до 125°C. Цикл інструкції 100-ns або 80-ns. 544 програмованих слова даних.
ОПЕРАТИВНА ПАМ'ЯТЬ
_ 4K Слів ROM програм
_ 128K слова простору даних
_ 16 вхідні і 16 Вихідні канали
_ 16-розрядний Паралельний Інтерфейс
_ Безпосередньо доступна зовнішня пам'ять даних
Простір
– Глобальний інтерфейс пам'яті даних
_ 16-розрядна інструкція і слова даних
_ 32-біт ALU і акумулятор
_ Єдиний цикл множення
Інструкції
_ 0 до Shifter 16-розрядного Масштабування
_ Порозрядна операція і лгічні інструкції
_ Підтримка системи команди з плаваючою комою
Дії, адаптивна фільтрація, і розширять-точна арифметика
Управління
_ Інструкції циклу для ефективного використовування
Простір Програми
_ Вісім допоміжних записів і арифметичний пристрій для непрямої адресації
_ Серійний Порт з абсолютними адресами інтерфейсу рограми
_ Введення синхронізації для конфігурації мультипроцесора
_ Три зовнішні масковані переривання призначені для користувача
_ Технологія 1.6-µm CMOS
Зовнішні Пристрої
_ Напруга 5-V
_ Генератор тактових імпульсів включеного в кристал
Упаковка:
– 68-шпильковий Leaded керамічний корпус
3.Аналіз блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора.
Метелик 1024 розрядного ШПФ
EMBED PBrush
Рис. 3.1
EMBED PBrush
Рис 3.2
Оскільки згідно завдання нам потрібно виконати 1024 розрядне ШПФ з
проріджуванням у часі, то ми на вході метелика ставимо схему інверсії, яка нам
дає з прямого коду четвірково-інверсний. Схема інверсії використовується для того, щоб на виході метелика ми мали послідовні дані тому, що аналіз іде в часовій області.
Оскільки 1024 розрядний метелик намалювати важко, то ми його намалювали за два підходи. Тобто рис.3.2 повинен бути під‘єднаний до кожного блоку “64 точкового комплексного ШПФ з 265 розрядного метелика” на рис.3.1.
В нас ШПФ відбувається за 5 кроків згідно формули 4к = N, де к- кількість кроків ШПФ, а N- розрядність ШПФ.
4.Розрахунковий розділ.
Для виконання базової операції вимагається виконати 12 операцій множення і 22 додавання. Для чисел з фіксованою комою до основних операцій алгоритму базової операції ШПФ з основою 4 додаються 12 операцій округлення дійсних операндів і 8 операцій округления результатів виконання базової операції.
Оскільки внас є 1024 точки і ШПФ виконується за 5 кроків, то на одному кроці виконується 256 базових операцій. А на 5 кроках виконується 1280 базових операцій. В загальному в нас виконується 1280*(12+22)=43520 операцій.
В зв‘язку з синхронізацією і іншими процесами ми даємо запас домножаючи загальну кількість операцій на 1,1. Тобто загальна кількість операцій в нас буде рівна 47872 .
Тзаг=N*Твик ,
де N – загальна кількість операцій, а Твик=1/f , де f – частота процесора.
Твик=1\50=20ns
Тзаг=47872*20*10-9 =
5.Розробка функціональної схеми.
EMBED PBrush
6.Розробка програми виконання заданої функції.
Програма на мові С++
#define Q12_SCALE 8
extern int r4_fft(short, short*, short*);
short x[32]={ 0, 0, // input samples
4617/Q12_SCALE, 0, // Scale the data from Q15 to Q12
9118/Q12_SCALE, 0,
13389/Q12_SCALE, 0,
17324/Q12_SCALE, 0,
20825/Q12_SCALE, 0,
23804/Q12_SCALE, 0,
26187/Q12_SCALE, 0,
27914/Q12_SCALE, 0,
28941/Q12_SCALE, 0,
29242/Q12_SCALE, 0,
28811/Q12_SCALE, 0,
27658/Q12_SCALE, 0,
25811/Q12_SCALE, 0,
23318/Q12_SCALE, 0,
20241/Q12_SCALE, 0 };
short w[32]={ 0, 32767, // Twiddle Factors
12540, 30274, // 32768*sin(2PI*n/N), 32768*cos(2PI*n/N)
23170, 23170,
30274, 12540,
32767, 0,
30274, -12540,
23170, -23170,
12540, -30274,
0, -32767,
-12540, -30274,
-23170, -23170,
-30274, -12540,
-32767, 0,
-30274, 12540,
-23170, 23170,
-12540, 30274 };
short index[16]={ 0, 4, 8, 12, // index for 16-points digit reverse
1, 5, 9, 13,
2, 6, 10, 14,
3, 7, 11, 15 };
short y[32]; // outputs
main()
{
int n=16;
int i;
int scale;
scale = r4_fft(n,x,w);
for(i=0; i<n; i++) {
y[2*i] = x[index[i]*2];
y[2*i+1] = x[index[i]*2+1];
}
}
int r4_fft(short n, int x[], const int w[])
{
int n1, n2, ie, ia1, ia2, ia3, i0, i1, i2, i3, j, k;
int t0, t1, t2;
int xtmph, xtmpl;
int shift, exp=19, scale=0;
n2 = n;
ie = 1;
for ( k=n; k>1; k>>=2 ) {
n1 = n2;
n2 >>= 2;
ia1 = 0;
for ( j=0; j<n2; j++ ) {
ia2 = ia1 + ia1;
ia3 = ia2 + ia1;
for ( i0=j; i0<n; i0+=n1) {
i1 = i0 + n2;
i2 = i1 + n2;
i3 = i2 + n2;
t0 = _add2(x[i1],x[i3]);
t1 = _add2(x[i0],x[i2]);
t2 = _sub2(x[i0],x[i2]);
x[i0] = _add2(t0,t1);
t1 = _sub2(t1,t0);
xtmph = (_smpyh(t1,w[ia2]) - _smpy(t1,w[ia2])) & 0xffff0000;
xtmpl = ((_smpylh(t1,w[ia2]) + _smpyhl(t1,w[ia2])) >> 16) & 0x0000ffff;
x[i2] = xtmph | xtmpl;
t0 = _sub2(x[i1],x[i3]);
t1 = -(t0 << 16);
t0 = t1 | ((t0 >> 16) & 0x0000ffff);
t1 = _add2(t2,t0);
t2 = _sub2(t2,t0);
xtmph = (_smpyh(t1,w[ia1]) - _smpy(t1,w[ia1])) & 0xffff0000;
xtmpl = ((_smpylh(t1,w[ia1]) + _smpyhl(t1,w[ia1])) >> 16) & 0x0000ffff;
x[i1] = xtmph | xtmpl;
xtmph = (_smpyh(t2,w[ia3]) - _smpy(t2,w[ia3])) & 0xffff0000;
xtmpl = ((_smpylh(t2,w[ia3]) + _smpyhl(t2,w[ia3])) >> 16) & 0x0000ffff;
x[i3] = xtmph | xtmpl;
}
ia1 = ia1 + ie;
}
if ( k > 4 ) {
ie <<= 2;
j=0;
while ( (exp > 16) && (j < n) ) {
xtmph = _norm(x[j] >> 16);
xtmpl = _norm(x[j] << 16 >> 16);
if ( xtmph < exp ) exp=xtmph;
if ( xtmpl < exp ) exp=xtmpl;
j++;
}
if ( exp < 19 ) {
shift = 19-exp;
exp = 19;
scale += shift;
_nassert(j>15);
for ( j=0; j<n; j++ ) {
xtmph = (x[j] >> shift) & 0xffff0000;
xtmpl = ((x[j] << 16) >> (16+shift)) & 0x0000ffff;
x[j] = xtmph | xtmpl;
}
}
}
}
return scale;
}
Програма на асемвлері TMS320C25
.title ”r4_fft.sa”
.def _r4_fft
.text_r4_fft .cproc n, p_x, p_w
.reg n1, n2, ie, ia1, ia2, ia3, i0, i1, i2, i3, j, k;
.reg t0, t1, t2, w, x0, x1, x2, x3;
.reg tmp, mskh, xtmph, xtmpl;
.reg exp, scale;
add n, 0, n2
mvk 1, ie
zero mskh
mvkh 0xffff0000, mskh
zero scale
add n, 0, k
stage_loop:
add n2, 0, n1
shr n2, 2, n2
zero ia1
zero j
group_loop:
SPRA654
add ia1, ia1, ia2
add ia2, ia1, ia3
add j, 0, i0
butterfly_loop:
add i0, n2, i1
add i1, n2, i2
add i2, n2, i3
ldw *+p_x[i0], x0
ldw *+p_x[i1], x1
ldw *+p_x[i2], x2
ldw *+p_x[i3], x3
add2 x1, x3, t0
add2 x0, x2, t1
sub2 x0, x2, t2
add2 t0, t1, x0 ; x0
sub2 t1, t0, t1
ldw *+p_w[ia2], w ; load twiddle factor w2
smpyh t1, w, tmp
smpy t1, w, xtmph
sub tmp, xtmph, xtmph
and xtmph, mskh, xtmph
smpylh t1, w, tmp
smpyhl t1, w, xtmpl
add tmp, xtmpl, xtmpl
shru xtmpl, 16, xtmpl
or xtmph, xtmpl, x2 ; x2
sub2 x1, x3, t0
shl t0, 16, t1
neg t1, t1
extu t0, 0 ,16, t0
or t1, t0, t0
add2 t2, t0, t1
sub2 t2, t0, t2
ldw *+p_w[ia1], w ; load twiddle factor w1
smpyh t1, w, tmp
smpy t1, w, xtmph
sub tmp, xtmph, xtmph
and xtmph, mskh, xtmph
smpylh t1, w, tmp
smpyhl t1, w, xtmpl
add tmp, xtmpl, xtmpl
shru xtmpl, 16, xtmpl
or xtmph, xtmpl, x1 ; x1
ldw *+p_w[ia3], w ; load twiddle factor w2
smpyh t2, w, tmp
smpy t2, w, xtmph
sub tmp, xtmph, xtmph
and xtmph, mskh, xtmph
smpylh t2, w, tmp
smpyhl t2, w, xtmpl
add tmp, xtmpl, xtmpl
SPRA654
shru xtmpl, 16, xtmpl
or xtmph, xtmpl, x3 ; x3
stw x0, *+p_x[i0]
stw x1, *+p_x[i1]
stw x2, *+p_x[i2]
stw x3, *+p_x[i3]
add i0, n1, i0
cmplt i0, n, tmp
[tmp]b butterfly_loop ; branch to butterfly loop
add ia1, ie, ia1
add j, 1, j
cmplt j, n2, tmp
[tmp]b group_loop ; branch to group loop
cmpeq k, 4, tmp ; test if last stage
[tmp]b end ; if true, branch to end
mvk 2, exp ; initialize exponent
zero j ; initialize index
mvkl 0x0000ffff, t2 ; mask for masking xtmpl
mvkh 0x0000ffff, t2
test_bit_growth: .trip 16
ldw *+p_x[j], tmp
norm tmp, xtmph ; test for redundant sign bit of HI half
shl tmp, 16, xtmpl
norm xtmpl, xtmpl ; test for redundant sign bit of LO half
cmplt xtmph, exp, tmp ; test if bit grow
[tmp]add xtmph, 0, exp
cmplt xtmpl, exp, tmp ; test if bit grow
[tmp]add xtmpl, 0, exp
cmpgt exp, 2, tmp ; if exp>2 than no scaling
[tmp]b no_scale
cmpeq exp, 0, tmp ; compare if bit grow 3 bits
[tmp]sub 3, exp, t0 ; calculate shift
[tmp]mvk 0x0213, t1 ; csta & cstb to ext xtmpl
[tmp]add scale, t0, scale ; accumulate scale
[tmp]b scaling
cmpeq exp, 1, tmp ; compare if bit grow 2 bit
[tmp]sub 3, exp, t0
[tmp]mvk 0x0212, t1 ; csta & cstb to ext xtmpl
[tmp]add scale, t0, scale ; accumulate scale
[tmp]b scaling
sub 3, exp, t0 ; grows 1 bit
mvk 0x0211, t1 ; csta & cstb to ext xtmpl
add scale, t0, scale ; accumulate scale
b scaling
no_scale:
add j, 1, j
cmplt j, n, tmp ; compare if test all output
[tmp]b test_bit_growth ; if not, test next output
b next_stage ; else go to next stage
scaling:
zero j
scaling_loop: .trip 16
ldw *+p_x[j], tmp
shr tmp, t0, xtmph ; scaling HI half
and xtmph, mskh, xtmph ; mask HI half
ext tmp, t1, xtmpl ; scaling LO half
and xtmpl, t2, xtmpl ; mask LO half by 0x0000ffff
or xtmph, xtmpl, tmp ; x[j]=[xtmph | xtmpl]
stw tmp, *+p_x[j]
add j, 1, j
cmplt j, n, tmp
[tmp]b scaling_loop
next_stage:
shl ie, 2, ie
shr k, 2, k
b stage_loop ; end of stage loop
end:
.return scale
.endproc
7.Висновки.
8.Список використаної літератури.
Основна
Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов /Пер. с англ. А.Л.Зайцева, Э.Г.Назаренко, Н.Н.Тетекина; Под ред. Ю.Н.Александрова. - М.:Мир, 1978. - 848 с.
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Куприянов М. С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. – Спб. : Политехника, 1998.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Цифровой процессор обработки сигналов TMS32010 и его применение/Под ред. А.А.Ланнэ.-Л.:ВАС,1990.-296 с.
http://www.analog.com.
http://www.ti.com.
Допоміжна:
Бабак В.П., Хандецький А.І., Шрюфер Е. Обробка сигналів: підручник для вузів., К., Либідь, 1996.- 390с.
Мельник А.А. Проектирование поточного процессора БПФ на специализированных БИС.- Львов, 1990.- 43с.
Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма.- М. Мир, 1980.- 552с.
Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ.- М.: Радио и связь, 1989.- 472с.
Справочник по устройствам цифровой обработки информации/ Н.А.Виноградов, В.Н.Яковлев, В.В.Воскресенский и др.- К:Тэхника, 1988.- 455с.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Гольденберг А. Ш., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов. Справочник. –М.: Радио и связь, 1985-312с.
Цифровая обработка сигналов/ А.Б.Сергиенко – СПб.:Питер, 2002.-608с.
Шрюфер Е. Обробка сигналів. Цифрова обробка дискретизованих сигналів.- К.: Либідь, 1992.- 226с.
Яцимірський М. М. Швидкі алгоритми ортогональних тригонометричних перетворень. - Львів: Академічни
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора