Міністерство Освіти і Науки України

Міністерство Освіти і Науки України

Національний Університет “Львівська Політехніка”

Кафедра ЕОМ

 

 

 

Цифрове опрацювання сигналів та зображень:

Алгоритми та реалізація

 

Навчальний посібник

 

до лекційного курсу

з дисципліни “Проектування комп’ютерних засобів обробки сигналів та зображень” для студентів спеціальностей

7.091501 і 8.091501 "Комп'ютерні системи та мережі"

7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“

 

 

Львів – 2008

Цифрове опрацювання сигналів та зображень: Алгоритми та реалізація. Навчальний посібник до лекційного курсу з дисципліни “Проектування комп’ютерних засобів ообробки сигналів та зображень” для студентів спеціальностей 7.091501 і 8.091501 "Комп'ютерні системи та мережі", 7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“ / Укладачі: Р. Попович, Є. Ваврук – Львів: Національний університет “Львівська політехніка”, 2008,  147 с.

 

Укладачі:                      Є. Ваврук, к.т.н., доцент

                                          Р. Попович, к.т.н., доцент

                                              

 

 

Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри

 

Рецензенти:                 Ткаченко Р.О., д. т. н, професор

                                          Голембо В.А. В.В., к. т. н, доцент

Анотація

Даний навчальний посібник укладений відповідно до навчальної програми з дисципліни "Проектування комп’ютерних засобів обробки сигналів та зображень". В ньому розглянуті основні питання проектування алгоритмічних, програмних та апаратних засобів опрацювання сигналів та зображень, вивчення яких допоможе студентам спеціальностей 7.091501 і 8.091501 /"Комп'ютерні системи та мережі"/ та 7.091503 і 8.091503 /"Спеціалізовані комп'ютерні системи"/ здобути початкові практичні навички у оптимальному виборі алгоритмів, їх програмній та апаратній реалізації.

 

Зміст

Вступ	5
1. Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень	7
2. Алгоритми швидкого перетворення Фур’є та їх програмна реалізація	13
3. Організація DSP- процесорів для задач опрацювання сигналів та зображень	26
4: Інтерфейси DSP-процесорів	30
5. Проектування процесора ШПФ на ПОС	38
6: Проектування засобів опрацювання сигналів та зображень на ПЛІС	53
7. Реалізація алгоритмів опрацювання сигналів та зображень на нейропроцесорах	62
8. Стиск нерухомих зображень з використанням перетворень різного типу дискретних косинусних перетворень	71
9. Опрацювання мовних сигналів	95
10. Використання вікон для опрацювання сигналів	122
11. Діагностика і контроль процесорів і систем опрацювання сигналів та зображень	135
Висновки	145
Література	146

ВСТУП

В останні роки цифрове опрацювання сигналів та зображень (ЦОСЗ) суттєво впливає на такі ключові технологічні галузі, як телекомунікації, цифрове телебачення і засоби інформації, біомедицина і цифровий звукозапис. Сьогодні ЦОСЗ є основою багатьох новітніх видів цифрових розробок і різних застосувань в інформаційному середовищі (наприклад. цифровий мобільний зв'язок, цифрові відеокамери, телебачення і системи звукозапису). Поряд з тим ЦОСЗ ширше впроваджується і в класичні галузі застосування (радіолокація, геофізика, опрацювання мовних сигналів, сейсмологія, системи зв'язку і передачі даних, медична і технічна діагностика, системи керування). Такому широкому застосуванню сприяли успіхи в розробці швидких алгоритмів і методів ЦОСЗ (наприклад, хвилькові перетворення), досягнення в технології конструювання інтегральних схем (архітектура нових процесорів ЦОСЗ, програмовані логічні інтегральні схеми – ПЛІС, системи на кристалі), використання програмних пакетів (MATLAB, база програм на мові С).

Суть ЦОСЗ як області науки пролягає у розв'язку на обчислювальній машині чотирьох основних задач:

- представлення сигналів та зображень в зручній для сприйняття формі;

- виділення із сигналів та зображень корисної інформації;

- внесення в сигнали та зображення корисної інформації;

- формування сигналів та зображень із заданими параметрами.

Основні переваги ЦОСЗ полягають в: можливості реалізації складних методів та алгоритмів опрацювання сигналів та зображень, недоступних для аналогових пристроїв; забезпеченні високої точності опрацювання; гнучкості і універсальності засобів, розвиненому користувацькому інтерфейсові тощо.

Головна проблема ЦОСЗ полягає у підвищенні швидкодії при реалізації певного набору математичних операцій над сигналами та зображеннями. Цей набір, як правило, визначається проблемною орієнтацією засобів ЦОСЗ. Для розв'язання цієї задачі комплексно застосовуються два напрямки - підвищення ефективності обчислювальних алгоритмів і вдосконалення архітектури комп'ютерних засобів. При цьому виходять з детального аналізу особливостей проблемної області. Власне, незалежно від вибраного напрямку і теми, студенти повинні виконувати курсові роботи з даного курсу виходячи з головної проблеми ЦОСЗ.

Метою вивчення дисципліни є засвоєння основних методів та алгоритмів опрацювання сигналів та зображень, принципів та шляхів проектування апаратних і програмних комп’ютерних засобів опрацювання сигналів та зображень, набуття початкових практичних навиків проектування таких засобів.

В результаті вивчення дисципліни студенти повинні:

знати: типи і особливості алгоритмів опрацювання сигналів та зображень, математичні основи їх реалізації, характеристики елементної бази та основи реалізації алгоритмів на її основі, особливості і етапи розробки цифрових пристроїв на процесорах і вузлах, орієнтованих на задачі опрацювання сигналів та зображень; мови програмування та мови опису апаратних засобів; пакети моделювання, опрацювання і фільтрації сигналів та зображень

вміти: вибирати найефективніший метод і алгоритм, здійснювати математичне формування алгоритму та методу його розв’язання, розробляти блок-схеми алгоритмів, розробляти програмну реалізацію виконання алгоритмів, розраховувати технічні параметри апаратних і програмних засобів, проектувати структурні та функціональні схеми процесорів та вузлів опрацювання сигналів; моделювати і опрацьовувати сигнали різної форми.

Для тих, хто хоче краще орієнтуватися в перспективних напрямках розвитку комп’ютерних засобів опрацювання сигналів та зображень, краще розуміти специфіку і особливості їх проектування радимо, насамперед, скористатись матеріалами Internet-сайтів

1. Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень

Аналіз задач і алгоритмів

До основних галузей, де використовується опрацювання сигналів та зображень відносяться:

1. Радіолокація (РЛ) — виявлення, фільтрація сигналу з режекцією завад та накопичення сигналу.

2. Гідроакустика (ГА) — контроль водяного простору, підводна сейсмологія, гідронавігація.

3. Зв’язок (ЗВ) — підвищення надійності, пропускної здатності, скритності, виділення символів, згортка символьних послідовностей, скорочення надлишковості, підвищення завадостійкості, керування транспортними засобами.

4. Геофізика (ГФ) — пошук нафтоносних (водоносних) шарів.

5. Біомедицина (БМ) — візуалізація органів, діагностика.

6. Системи керування виробничими процесами — керування, знімання даних, передача інформації.

7. Промислова діагностика — неруйнівний контроль, візуалізація стану вузлів, діагностика віддалених об’єктів.

Кількість основних алгоритмів і операцій, що використовуються для їх виконання, як це видно з табл.1.1 є невеликою.

Таблиця 1.1. Перелік основних алгоритмів і застосованих операцій

Алгоритми обробки і	Області застосування
застосовувані операції	РЛ	ГА	ЗВ	ГФ	БМ	СК
Згортка	+		+	+
ШПФ	+	+	+	+	+
Перемноження елементів векторів	+	+			+	+
Додавання елементів векторів	+	+				+
Перетворення координат	+	+	+
Обчислення тригонометричних функцій	+	+	+	+		+
Пошук максимальних значень	+					+
Операції над матрицями	+	+	+		+
Табличне перетворення відліків зображення	+
Сортування	+					+
Отримання квадратного кореня	+	+	+	+		+
Піднесення до степеня	+	+	+	+		+
Статистична обробка	+
Нормування	+	+
Розрахунок нормованих коефіцієнтів кореляції		+
Операції повертання координат			+
Логарифмування				+
Потенціювання				+
Номінальні розкиди координат					+
Інтерполяція даних					+	+

Розглянемо основні типи алгоритмів.

Лінійна фільтрація. Лінійна фільтрація використовується для подавлення шумів, спектр яких не перетинається зі спектром сигналу і дозволяє виділити в чистому вигляді функцію, що описує явище, яке досліджується. На практиці розрізняють два основних типи лінійних фільтрів: з скінченою (СІХ) і нескінченою (НІХ) імпульсними характеристиками. НІХ фільтри мають рекурсивну структуру, що описується різницевими рівняннями згідно з формулою (1.1).

, n ³ 0;                             (1.1)

де x та y - вхідна та вихідна реалізації процесу; a_i і b_i - постійні коефіцієнти, що характеризують властивості фільтра, причому a_м ¹0; M – порядок фільтру.

 СІХ - фільтри реалізуються на основі нерекурсивної структури, яка описується формулою (1.2), і може бути отримана з формули (1.1) якщо a_i прирівняти до нуля, .

, n ³ 0;                                 (1.2)

причому, b_i можна назвати дискретною імпульсною характеристикою системи (фільтра).

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

Дискретне перетворення Фур’є. Дискретне перетворення Фур’є (ДПФ) скінченої періодичної послідовності відліків сигналу { х (n)}, 0< n < N -1, визначається формулою (1.3):

, k =0,1,…, N -1                                  (1.3)

де  - комплексний дискретний ортонормований базис.

Таким чином, ДПФ представляє собою множину спектральних коефіцієнтів Фур’є, що відповідають N рівномірно рознесеним частотам, починаючи від нульової і до (але не включно) частоти 2p/ T. Обернене дискретне перетворення Фур’є (ОДПФ) визначається формулою (1.4):

, n =0,1,…, N -1;                          (1.4)

ОДПФ дозволяє однозначно перейти від Фур’є-образу X (k) до функції х (n).

Швидке перетворення Фур’є (ШПФ) є узагальненою назвою множини алгоритмів, що призначені для виконання ДПФ і ОДПФ. Основна ідея алгоритмів ШПФ полягає в розбитті процедури виконання ДПФ на m =log₂ N етапів, на кожному з яких вхідний дискретний набір розділяється на дві частини. До кожної такої частини вхідного дискретного набору, застосовується операція ДПФ в 2 рази меншої розмірності: в результаті застосувань розбиття m разів на останньому етапі, матимемо тривіальне 2-х точкове ДПФ. Застосування ШПФ можливе лише тоді, коли N є складним числом. Найбільшого розповсюдження набули алгоритми ШПФ для послідовностей довжини N, що є степенем числа 2 (N =2 ^m). Загальне число операцій в алгоритмі ШПФ складає приблизно N log₂ N додавань і 0,5 N log₂ N множень комплексних чисел. Алгоритми ШПФ з проріджуванням в часі і з проріджуванням по частоті принципово мало відрізняються між собою. Тому розглянемо тільки алгоритм ШПФ з проріджуванням в часі. Формула розкладу алгоритму, в результаті застосування якої отримується шуканий дискретний набір X (k), k =0,1,..., N -1, що є зображенням вихідного дискретного набору перетворюваної функції x(n), n =1,2,..., N -1 в Фур’є просторі визначається згідно з формулою (1.5).

, k =0,1,..., N -1;                                 (1.5)

де X ₀(k) та X ₁(k) відповідно N /2 - точкові ДПФ послідовностей x (2 n) та x (2 n +1), n =0, 1,..., (N /2-1). При проріджуванні, N -точкове ДПФ зводиться до обчислення двох N /2-точкових ДПФ. Рекурсивно застосовуючи вказаний спосіб розділення до перетворень меншої розмірності, отримуємо алгоритм ШПФ за основою два з проріджуванням в часі. Аналізуючи формулу (1.5), і беручи до уваги, що послідовності X ₀(k) та X ₁(k), періодичні з періодом N /2, та W_N^N-k = - W_N^k, можна встановити, що при кожному розділенні реалізується однотипна базова операція:

                             A*=A+W_N^kB; B*=A – W_N^k B;                                           (1.6)

причому k О{0, 1,..., (N /2-1)}, а величини A, B, A*, B*, і W_N^k - комплексні числа. Для виконання базової операції (1.6) необхідно виконати одне множення, одне додавання і одне віднімання комплексних величин.

Кореляція. Для визначення подібності між сигналами в різні моменти часу або виділення сигналу на фоні шуму проводять кореляційну обробку, важливе місце в якій займає обчислення функцій взаємної кореляції двох числових послідовностей x і y, кожна з яких містить N відліків, записується у вигляді:

, r = 0,1,…, N -1;                   (1.7)

Тобто, взаємна кореляційна функція двох сигналів обчислюється як сума їх поелементних добутків з відносною затримкою r.

Автокореляційна функція записується у вигляді:

, r = 0,1,…, N -1;                 (1.8)

Обчислення автокореляційної і взаємокореляційної функцій двох сигналів складається з трьох основних операцій: часової затримки, множення і сумування.

Згортка сигналів. При згортці сигналів x (n) та h (m), де n = 0,1,…, N ₁-1, m = 0,1,…, N ₂-1, виконується обробка згідно з формулою (1.9).

;                                               (1.9)

де h (m) і x (n) рівні нулю поза відповідними інтервалами, h (m) - дискретна імпульсна характеристика системи (фільтра).

Нормування сигналів. Одним з прикладів операції нормування сигналів є ділення комплексних чисел, що виконується згідно з формулою (1.10).

(1.10)

Сортування. В основі алгоритмів сортування лежать дві основні операції: порівняння і пересилання даних.

Більшості з названих алгоритмів властиві регулярність, рекурсивність і локальність, що робить їх придатними для реалізації на НВІС. Зокрема, до локально рекурсивних алгоритмів відносяться алгоритми премноження матриць, згортки, НІХ-фільтрація, сортування вибором; до глобально-рекурсивних - алгоритми ШПФ, бітове сортування.

На основі аналізу алгоритмів в табл. 1.2 виділено набір базових операцій для опрацювання сигналів та зображень.

Таблиця 1.2. Базові операції для задач керування та опрацювання інформації

Алгоритм	Базові операції
Реалізація фільтрів, обчислення кореляційної і взаємокореляційної функцій	Додавання, віднімання, множення, обчислення суми парних добутків
Алгоритми перетворення	Множення, додавання комплексних чисел; обчислення операцій ШПФ, ШПХ, множення послідовностей комплексних чисел
Алгоритми обчислення: коефіцієнтів взаємної кореляції, координат, відстаней, виконання вагового множення, тощо	Обчислення тригонометричних функцій, добування квадратного кореня, піднесення до степені, ділення, сортування

Детальніше конкретні алгоритми описані і реалізовані в подальших розділах посібника.

Основні параметри типових операцій. Основні параметри типових операцій наведені в табл. 1.3, де N - розмірність масиву інформації.

Таблиця 1.3. Параметри типових операцій

Тип операції	Складність виконання	Тип обчислюва-льних засобів	Необхідна швидкодія (MOPS)
Лінійні операції: просторова фільтрація, згортка, виявлення контурів, скалярний добуток, КІХ-фільтрація.	N	Скалярний	10^2 - 10^5
Операції другого порядку: лінійні перетворення, перетворення Фур'є, кореляція, перемноження матриці на вектор, сортування, медіанна фільтрація.	N^2	Векторний	10^3 - 10^7
Операції вищих порядків: матричні операції, спектральні обчислення, адаптивні операції, розв’язання задач лінійних алгебраїчних рівнянь	N^3	Матричний	10^4 - 10^8

 

Основні формули

Теореми, що пояснюють суть перетворення Фур’є (наведені без доведення).

Теорема 1. Якщо комплексне число представлене у вигляді e ^j2πN, де N - ціле, то e ^j2πN = 1.

Теорема 2. Величина періодична по k і по n з періодом N. Тобто, для будь-яких цілих l і m виконується рівність:

                                   (2.4)

Теорема 3.

Для величини справедлива формула:

                                                 (2.5)

З наведених теорем визначається основна ідея алгоритму ШПФ:

1. Необхідно розділити суму (1) з N доданків на дві суми по N/2 доданків, і обчислити їх окремо. Для обчислення кожної з підсум, треба їх теж розділити на дві і т.д.

2. Необхідно повторно використовувати вже обчислені доданки.

При обчисленні алгоритму ШПФ застосовують або "проріджування за часом" (в першу суму попадають доданки з парними номерами, а в другу - з непарними), або "проріджування за частотою" (в першу суму попадають перші N/2 доданків, а в другу - інші). Обидва варіанти рівноцінні. В силу специфіки алгоритму доводиться застосовувати тільки N, що є ступенями 2. Розглянемо випадок проріджування за часом.

Теорема 4. Визначимо ще дві послідовності: {x_[even]} і {x_[odd]} через послідовність {x} таким чином:

x_[even]n = x_2n, x_[odd]n = x_2n+1,                                       (2.6)

n = 0, 1,..., N/ 2-1

Нехай до цих послідовностей застосовані ДПФ і отримані результати у вигляді двох нових послідовностей {X_[even]} і {X_[odd]} по N/2 елементів у кожній.

Елементи послідовності {X} можна виразити через елементи послідовностей {X_[even]} і {X_[odd]} за формулою:

            (2.7).

Формула (2.7) дозволяє скоротити число множень удвічі (не враховуючи множень при обчисленні X_{[even] k} і X _[odd]k), якщо обчислювати X_k не послідовно від 0 до N - 1, а попарно: X₀ і X_N/2, X₁ і X_N/2+1,..., X_{N/ 2-1} і X_N. Пари утворяться за принципом: X_k і X_N/2+k.

Теорема 5. ДПФ можна обчислити і за формулою:

(2.8)

З теореми випливає, що можна не зберігати обчислені значення X_[even]k і X_[odd]k після обчислення чергової пари, і одне обчислення можна використовувати для обчислення двох елементів послідовності {X}.

На цьому кроці буде виконане N/2 множень комплексних чисел. Якщо застосувати подібні схеми для обчислення послідовностей {X_[even]} і {X_[odd]}, то кожна з них вимагатиме N/4 множень, разом ще N/2. Продовжуючи аналогічно далі log₂N разів, можна дійти до сум, що містять лише один доданок, так що загальна кількість множень рівна (N/2)log₂N.

Розглянемо ШПФ для різних N. Додамо ще один нижній індекс, який буде вказувати на загальну кількість елементів послідовності, до якої цей елемент належить. Тобто X_{R}k - це k -ий елемент послідовності {X_{R}} з R елементів. X_{R}[even]k - це k -ий елемент послідовності {X_{R}[even]} з R елементів, обчислений по парних елементах послідовності {X_{2R}}. X_{R}[odd]k - це k -ий елемент послідовності {X_{R}[odd]}, обчислений по непарних елементах послідовності {X_{2R}}.

У випадку, коли доданок лише один (N = 1) формула (1) спрощується до:

,                       

Оскільки в цьому випадку k може бути рівне тільки 0, то X_{1}0 = x_{1}0, тобто, ДПФ над одним числом дає це ж саме число.

Для N = 2 за теоремою (2.5) отримаємо:

Для N = 4 за теоремою (2.5) отримаємо:

Звідси виходить, що якщо елементи вихідної послідовності були дійсними, то при збільшенні N елементи ДПФ стають комплексними.

Для N = 8 за теоремою (2.5) отримаємо:

Необхідно звернути увагу, що на попередньому кроці використовувалися ступені W₄, а на цьому - ступені W₈. Зайвих обчислень можна уникнути, якщо врахувати, що

Тоді формули для N =4 будуть використовувати ті ж W-множники, що і формули для N =8:

Висновок:

В основі алгоритму ШПФ лежать такі формули:

                    (2.9)

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-процесорів

Ефективність роботи DSP- процесора в структурі системи залежить від організації каналів вводу-виводу.  До складу сучасних DSP- процесорів (наприклад, ADSP-21ESP202) входять інтегровані АЦП/ЦАП, що знімає проблему організації інтерфейсу між окремими компонентами. А дискретні АЦП і ЦАП оснащуються інтерфейсами, які призначені для зв'язку з DSP, що мінімізує і/чи усуває необхідність зовнішньої підтримки інтерфейсу або застосування інтерфейсної логіки. Високопродуктивні сігма-дельта-АЦП і ЦАП в даний час випускаються в одному корпусі (комбіноване вирішення називається КОДЕК або КОдер/ДЕКодер), наприклад, AD73311, AD73322. Дані пристрої також розроблені з урахуванням мінімальних вимог до інтерфейсної логіки при роботі з найпоширенішими DSP-процесорами.

Ступінь - запис вхідної послідовності у вхідне ОЗП відповідно до двійкової інверсії номерів. 2 ступінь - перша ступінь перетворення. Дані зчитуються з вхідного ОЗП, перетворюються і записуються в буферне ОЗП.

ВЕКТОРНИЙ СПІВПРОЦЕСОР

Векторний співпроцесор - основний функціональний елемент Л1879ВМ1. Структурно він являє собою матрично-векторний операційний пристрій і набір регістрів різного призначення.

Операційний пристрій (ОУ) - регулярна матрична структура 64х64 комірки (рис. 2). Матриця може бути довільно розділена на стовпці і рядки. В утворені після поділу макрокомірки завантажуються вагові коефіцієнти W_іj. На вхід матриці подається вектор вхідних даних , кожному елементу якого відповідає рядок матриці. Ширина рядка (у бітах) - розрядність даного елемента вхідних даних. У макрокомірках відбувається множення елемента вектора вхідних даних на ваговий коефіцієнт і додавання зі значенням верхньої комірки (або значень входів і U). Таким чином, для кожного стовпця обчислюється скалярне вираз . Для зниження розрядності вихідних даних і захисту від арифметичного переповнення використовується програмувальна функція насичення (рис. 7.2).

Рис.7.2.

Операнди і вихідні значення упаковуються в 64-х розрядне слово. Всі операції в матриці ОП робить паралельно, за один такт. Завантаження вагових коефіцієнтів відбувається за 32 такти. У векторному співпроцесорі є "тіньова" матриця, в яку вагові коефіцієнти можна завантажувати у фоновому режимі. Переключення "тіньової" і робочої матриць займає один такт. Найважливіша особливість векторного співпроцесора - робота з операндами довільної довжини (навіть не кратного степеня двійки) у діапазоні 1-64 біт. Цим досягається оптимальне співвідношення між швидкістю і точністю обчислень: при однобітових операндах на тактовій частоті 40 МГЦ продуктивність складе 11 520 MMAC (мільйонів операцій множення з нагромадженням) чи 40 000 MOPS (мільйонів логічних операцій у секунду), при 32-бітових операндах і 64-бітовому результаті вона стане номінальною – 40 MMAC. Вміння динамічно, в процесі обчислень змінювати розрядність операндів дозволяє підвищити продуктивність в тих випадках, коли звичайні процесори працюють "вхолосту", з надлишковою точністю.

Конфігурація матриці може бути змінена динамічно протягом обчислень. Обчислення можуть бути початі з максимальною точністю і мінімальною продуктивністю, але за певних умов можна досягти пікової продуктивності шляхом зниження точності.

Для обчислення продуктивності використовуються наступні вирази:

де:     МСРS - мільйон з'єднань у секунду (еквівалентно ММАС)

64 - ширина слова даних;

Nх- ширина синапсів;

Nw- ширина ваг;

F = 50 МГЦ - тактова частота.

У випадку Nх¹1 і Nw=1, вираз набуває вигляду:

У випадку Nх=1 і Nw¹1, вираз набуває вигляду:

У випадку Nх=Nw=1, вираз набуває вигляду:

У випадку Nх=Nw=32, вираз набуває вигляду:

Опрацювання мовних сигналів

Багато напрямків мовних технологій (опрацювання мовних сигналів з певною метою: стиск мовних сигналів, cинтез мови, зміна темпу мовлення, розпізнавання або визначення емоційного стану людини за голосом, діагностика степені певних захворювань, розпізнавання мови) на сьогодні інтенсивно розвиваються та знаходять усе більше застосування в різноманітних сферах.

Розпізнавання мови є одним з найскладніших напрямків мовних технологій, який можна застосувати в багатьох областях.

Важливим моментом при опрацюванні мовних сигналів у цифровому вигляді є вибір частоти дискретизації та розрядності відліків у бітах при переході за допомогою аналого-цифрового перетворювача від неперервного до дискретного мовного сигналу.

Загалом вважається, що для звукових сигналів (спів людини, музика, мова, інші звукові сигнали, скажімо дзенькіт кришталю) гранична частота не перевищує 22 КГц. Тому для дискретизації звукових сигналів беруть стандартні частоти 44,1 КГц або 48 КГц. Розрядність відліків цифрового звукового сигналу – 16 біт.

Проте мовні сигнали зокрема мають звужений діапазон частот – від 0 до 8 КГц. І при опрацюванні мови досить дискретизувати неперервні сигнали з частотою дискретизації 16 КГц та брати 16-бітові відліки.

У деяких часткових випадках основні спектральні складові сигналів знаходяться в ще вужчому діапазоні, і замість частоти дискретизації 16 КГц можна взяти частоту дискретизації 8КГц.

Мовні технології

Виділяють такі напрямки мовних технологій.

1. Стиск (кодування) мови.

Високого степеня стиску досягаємо використанням дискретних косинусних перетворень.

2. Синтез мови

Завдання полягає в тому, що треба озвучити наявний текст. На сьогодні є два принципово різних підходи до вирішення цієї задачі.

а) компілятивний синтез

Виділяються певні одиниці мови, наприклад звуки мови, після цього з них утворюють слова, речення.

б) формантний синтез

Будують математичну модель голосового тракту людини, щоб мати змогу утворювати різні одиниці мови.

3. Розпізнавання диктора за голосом.

Є два варіанти цієї задачі. Перший варіант, так звана верифікація, полягає в з’ясуванні факту: належить записаний мовний зразок заданій особі чи ні. Інший ускладнений варіант ідентифікації полягає у визначенні якій із наперед заданих осіб належить записаний мовний зразок.

4. Визначення емоційного стану людини за голосом.

5. Визначення стану хворого за голосом (наприклад, при лікуванні мовних розладів).

6. Зміна темпу мовлення.

7. Розпізнавання мови.

Розпізнавання мови є одним з найскладніших напрямків мовних технологій, який можна застосувати в багатьох областях.Задача полягає в тому, що маючи мовний сигнал, треба утворити відповідний текст (так звану транскрипцію).

Підхід до розпізнавання мовних команд вкладається у загальну схему розпізнавання образів (крім мови це можуть бути двовимірні або тривимірні зображення, багатовимірні сигнали різної природи тощо). Згідно з цією схемою слід виконувати такі кроки:

- на фазі навчання попередньо записати певну множину мовних образів-еталонів;

- під час розпізнавання порівнювати невідомий образ (мовний сигнал), який хочемо розпізнати, з кожним із із записаних мовних образів-еталонів;

- найближчий (у сенсі вибраної відстані між образами) до невідомого образу, для якого хочемо здійснити розпізнавання, образ-еталон і буде відповіддю системи розпізнавання.

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

У якому вигляді готувати і тримати мовні сигнали-еталони?

Використовувати часове, спектральне чи якесь комбіноване зображення сигналів?

Якою міркою порівнювати відстань між двома мовними сигналами?

Розглянемо найпростіший алгоритм розпізнавання окремих слів із обмеженого словника з навчанням на одного диктора.

Найпростіший розпізнавач мови

Спочатку опишемо як виконують спрощене попереднє опрацювання мовного сигналу х (n). Пропускаємо його через набір смугопропускних цифрових фільтрів (кількість фільтрів для прикладу взята рівною 16). Тобто частотний діапазон сигналу від 0 до 8 кГц (для мовних сигналів) розбиваємо на 16 рівних смуг. Частотні характеристики фільтрів наведені на рис.9.1.

        

Рис.9.1.

В результаті на виходах цифрових фільтрів ЦФ₁, ЦФ₂,...,ЦФ₁₆ отримуємо 16 цифрових сигналів х ₁(n), х ₂(n),.... х ₁₆(n).

Ділимо число N відліків кожного з цих сигналів на 16 рівних відрізків, доповнюючи сигнал при потребі нульовими відліками, щоб N було кратне 16. Для відліків кожного із шістнадцяти відрізків знаходимо середнє значення. Тобто, перше значення – це середнє відліків сигналу від першого до N /16-го; друге значення – це середнє відліків сигналу від (N /16+1)-го до 2 N /16-го;...; шістнадцяте значення – це середнє відліків сигналу від (15 N /16+1)-го до N -го. Отже, для кожного з шістнадцяти сигналів х ₁(n), х ₂(n),.... х ₁₆(n) отримуємо 16 середніх значень.

У результаті для сигналу х (n) ма