• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Організація DSP- процесорів для задач опрацювання сигналів та зображень

Fft.cpp

/*

Fast Fourier Transformation

=====================================================

*/

#include "fft.h"

// This array contains values from 0 to 255 with reverse bit order

static unsigned char reverse256[]={

0x00, 0x80, 0x40, 0xС0, 0x20, 0xА0, 0x60, 0xE0,

0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,

0x08, 0x88, 0x48, 0xС8, 0x28, 0xA8, 0x68, 0xE8,

0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,

0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,

0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,

0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,

0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,

0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,

0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,

0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,

0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,

0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,

0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xG6,

0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,

0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,

0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,

0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,

0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,

0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,

0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,

0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,

0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,

0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,

0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,

0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,

0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,

0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,

0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,

0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,

0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,

0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF,

};

void fft(ShortComplex *x, int T, bool complement

{

unsigned int I, J, Nmax, N, Nd2, k, m, mpNd2, Skew;

unsigned char *Ic = (unsigned char*) &I;

unsigned char *Jc = (unsigned char*) &J;

ShortComplex S;

ShortComplex *Wstore, *Warray;

Complex WN, W, Temp, *pWN;

Nmax = 1 << T;

//first interchanging

for(I = 1; I < Nmax - 1; I++)

{

Jc[0] = reverse256[Ic[3]];

Jc[1] = reverse256[Ic[2]];

Jc[2] = reverse256[Ic[1]];

Jc[3] = reverse256[Ic[0]];

J >>= (32 - T);

if (I < J)

{

S = x[I];

x[I] = x[J];

x[J] = S;

}

}

//rotation multiplier array allocation

Wstore = new ShortComplex[Nmax / 2];

Wstore[0].re = 1.0;

Wstore[0].im = 0.0;

//main loop

for(N = 2, Nd2 = 1, pWN = W2n, Skew = Nmax >> 1; N <= Nmax; Nd2 = N, N+= N, pWN++, Skew >>= 1)

{

//WN = W(1, N) = exp(-2*pi*j/N)

WN= *pWN;

if (complement)

WN.im = -WN.im;

for(Warray = Wstore, k = 0; k < Nd2; k++, Warray += Skew)

{

if (k & 1)

{

W *= WN;

*Warray = W;

}

else

W = *Warray;

for(m = k; m < Nmax; m += N)

{

mpNd2 = m + Nd2;

Temp = W;

Temp *= x[mpNd2];

x[mpNd2] = x[m];

x[mpNd2] -= Temp;

x[m] += Temp;

}

}

}

delete [] Wstore;

if (complement)

{

for( I = 0; I < Nmax; I++ )

x[I] /= Nmax;

}

}

Для опрацювання сигналів та зображень найчастіше використовуються DSP- процесори. Розглянемо підходи до їх реалізації на базі обчислення алгоритму ШПФ.

В загальному випадку, вимоги по використовуваній пам'яті для N-точкового ШПФ такі: N комірок для дійсних даних, N комірок для уявних даних і N комірок для синусоїдальних базисних функцій (коефіцієнти повертання). Додаткові комірки пам'яті необхідні у випадку використання зважування з використанням віконних функцій (wіndowіng). Якщо прийняті вимоги по пам'яті задоволені, DSP повинний виконати необхідні обчислення за необхідний час. Багато виробників DSP або проводять тест продуктивності для зазначеного розміру ШПФ, або визначають час обчислення для базової операції "метелик". При порівнянні характеристик ШПФ важливо упевнитися, що у всіх випадках використовується однаковий тип ШПФ. Наприклад, тест 1024-точкового ШПФ на одному DSP, отриманому за допомогою алгоритму ШПФ за основю 2, не повинний порівнюватися з тестом алгоритму ШПФ за основою 4 для іншого DSP.

Інше розуміння відносно ШПФ полягає у виборі процесора з фіксованою чи плаваючою крапкою. Результ обчислення "метелика", може бути більшим ніж розрядна сітка DSP з фіксованою крапкою, що створює проблему при реалізації ШПФ на процесорах такого типу. Для запобігання переповнення, дані потрібно масштабувати, заздалегідь залишаючи достатню кількість додаткових розрядів для збільшення значень оброблюваних даних. Альтернативний метод полягає в тім, що дані можуть масштабуватися після кожного каскаду обчислення ШПФ. Метод масштабування даних після кожного проходу ШПФ відомий як блокова плаваюча крапка, (block floatіng poіnt). Він називається так, тому що повний масив даних масштабується як єдине ціле, незалежно від того, чи дійсно кожен елемент у блоці вимагає масштабування. Блок масштабується таким чином, щоб відносні співвідношення між даними залишилися колишніми. Наприклад, якщо кожне слово даних зсунене вправо на один розряд (поділене на 2), абсолютні значення змінюються, але відносно один одного співвідношення даних залишаються колишніми.

У 16-розрядному DSP-процесорі з фіксованою крапкою після множення формується 32-розрядне слово. Сімейство цифрових сигнальних процесорів Analog Devіces ADSP21xx характеризується розширеним динамічним діапазоном, що реалізується в операціях множення з накопиченням за допомогою 40-розрядного внутрішнього регістра акумулятора.

Використання DSP-процесора з плаваючою крапкою, усуває потребу в масштабуванні даних і тому приводить до більш простої реалізації алгоритму ШПФ, але наслідком цього спрощення є збільшення часу опрацювання, що потрібно для складних арифметичних обчислень плаваючою крапкою. Крім того, 32- розрядний DSP-процесор із плаваючою крапкою, мабуть, буде мати менший рівень шумів округлення, ніж 16-розрядний DSP-процесор з фіксованою крапкою.

Часи виконання 1024-х точкового ШПФ наведені в табл.3.1..

Таблиця 3.1. Час виконання 1024-точкового комплексного ШПФ (16-біт фіксована крапка) на DSP різного типу

16-біт фіксована крапка Тип	Командний цикл (нс)	Кількість циклів	Загальний час (мс)
TMS320C25			9.08
ADSP2105			2.50
TMS320C50			2.12
ADSP2101(2115)			1.73
ADSP2117		--//--	1.04
32-біти плаваюча крапка TMS320C30			3.04
TMS320C40			0.97
ADSP 21020			0.58
ADSP 21060SHARC			0.46

В таблиці необхідно звернути увагу на різну кількість циклів виконання, яка залежить від внутрішньої архітектури DSP.

Результати порівняння реалізації алгоритмів ШПФ за основою 2 на різних процесорах такі:

В DSP-процесорі ADSP-TS001 TіgerSHARC™ (статичний, суперскалярний цифровий сигнальний процесор з RISK + VLIV архітектурою) можливі обидва режими (з плаваючою і з фіксованою крапкою), що забезпечує виняткову гнучкість програмування.

3.2. Вимоги до ПОС при реалізації алгоритмів ЦОС (на прикладі виконання алгоритму ШПФ в режимі реального часу)

Є два основних способи опрацювання сигналів у реальному масштабі часу: опрацювання одного відліку в кожен момент часу (безперервна опрацювання) і опрацювання одного пакета даних у кожен момент часу (пакетна опрацювання). Системи, засновані на безперервній опрацюванні, такі як цифровий фільтр, одержують дані у виді одного відліку в кожен момент часу. У кожнім такті новий відлік надходить у систему, а оброблений відлік передається на вихід. Системи, засновані на пакетній опрацюванні, такі як побудований на ШПФ цифровий аналізатор спектру, одержують дані у виді цілого пакета відліків. Відбувається опрацювання всього пакета вихідних даних, результатом якої є пакет перетворених вихідних даних.

Для забезпечення функціонування в РМЧ повний розрахунок ШПФ повинен виконуватися в проміжку, що відповідає часу нагромадження одного пакета даних. Передбачається, що, поки робиться обчислення ШПФ поточного пакета даних, DSP-процесор накопичує дані для наступного пакету. Нагромадження даних є однією зі сфер, де важливу роль грають спеціальні архітектурні особливості DSP. Безупинне одержання даних полегшується, завдяки можливостям гнучкої адресації даних у DSP у сполученні з використанням різних каналів прямого доступу до пам'яті (DMA).

Приклад (порядок) обчислення ШПФ у РМЧ.

1. Припустимо, що час виконання 1024-точкового алгоритму ШПФ за основою 2 дорівнює 69 мкс (TіgerSHARC, 32-розрядний режим)

2. Визначаємо максимальну частоту дискретизації: fs (maximum) < 1024 відліки/69 мкс= 14,8 MSPS

3. Визначаємо ширину смуги вхідного сигналу, для даного прикладу < 7,4 МГЦ

4. При розрахунку не приймались до уваги додаткові операції, пов'язані з реалізацією ШПФ і передачею вхідних/вихідних даних

Наведений приклад дає оцінку максимальної ширини смуги сигналу, що може бути оброблена даним DSP-процесором з врахуванням характеристик реалізованого на ньому ШПФ.

Інший підхід полягає в тому, щоб, задаючи ширину смуги сигналу, розробити вимоги до DSP для опрацювання сигналу в розглянутій смузі. Якщо ширина смуги частот сигналу відома, необхідна частота дискретизації може бути визначена шляхом її множення на коефіцієнт 2 - 2,5 (збільшення частоти дискретизації може вимагатися для ослаблення вимог до попереднього АЦП фільтра нижчих частот (ФНЧ), який усуває ефект накладення спектру, (antіalіasіng fіlter)). На наступному кроці визначається число точок ШПФ, необхідне для досягнення бажаної роздільної здатності за частотою. Значення роздільної здатності за частотою отримується поділом швидкості дискретизації fs на кількість N точок ШПФ. Ці і інші підходи стосовно реалізації ШПФ наведені нижче.

Порядок реалізації ШПФ у РМЧ такий. Визначається:

- ширина смуги сигналу;

- частота дискретизації fs;

- кількість точок ШПФ, N;

- роздільна здатність за частотою (fs / N);

- макс. час обчислення N-точкового ШПФ (N / fs);

- фіксована крапка чи плаваюча крапка;

- час виконання алгоритму ШПФ за основою 2 у порівнянні з ШПФ за основою 4;

- виграш ШПФ у відношенні сигнал/шум [10 log₁₀(N / 2)];

- вимоги зважування з використанням віконної функції (Wіndowіng).

Кількість крапок ШПФ також визначає мінімальний рівень шуму ШПФ щодо рівня широкополосного шуму, і це також повинно бути враховане при виборі кількості крапок ШПФ.

На рис. наведені співвідношення між рівнем сигналу, що відповідає повному динамічному діапазону системи, рівнем широкосмугового шуму (вимірюваного в ширині смуги від 0 до fs/2) і мінімальним рівнем шуму ШПФ.

Необхідно звернути увагу, що виграш у відношенні сигнал/шум ШПФ визначається кількістю точок ШПФ. ШПФ діє подібно до аналогового аналізатору спектра із шириною смуги розгортки fs/N. Збільшення кількості точок підвищує роздільну здатність ШПФ і звужує смугу частот, що пропускаються ним, скорочуючи, таким чином, мінімальний рівень шуму. У цьому аналізі ми зневажили шумом, викликаним помилкою округлення при реалізації ШПФ. На практиці АЦП, що використовується для оцифрування сигналу, виробляє шум квантування, що є домінуючим шумовим джерелом у системі.

Щоб уявити собі, при яких умовах ми можемо здійснювати обробку сигналів у реальному масштабі часу, далі дослідимо характеристики реально існуючих DSP- процесорів і час реалізації ШПФ на цих процесорах. Це означає, що ШПФ повинно бути розраховане протягом часу нагромадження пакета даних, рівного N/fs. Інші розуміння, такі як використання процесора з фіксованою крапкою в порівнянні з процесором з плаваючою крапкою, використання алгоритму за основою 2 у порівнянні з алгоритмом за основою 4, споживана процесором потужність і вартісні показники, можуть також бути предметом для розгляду.

Читайте також:

1. II. Організація і проведення спортивних походів
2. II. Організація перевезень
3. II. Організація перевезень
4. А. Організація Острозького колегіуму – Академії
5. Адміністративно-територіальна організація
6. Алгоритм прийняття рішення при прийманні сигналів з випадковою початковою фазою
7. Алгоритм розв’язання задачі
8. Алгоритм розв’язання розподільної задачі
9. Алгоритм розв’язування задачі
10. Алгоритм розв’язування задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі

Переглядів: 944