Проектування процесора шпф на пос

Алгоритм ШПФ із проріджуванням за часом

Нехай

Розділимо послідовність x(n) на парні (even) і непарні (odd) складові

Введемо підстановку n=2r для парних n і n=2k+1 для непарних n:

Тому, що

Необхідно зауважити, що і G(k), і H(k) в останній рівності можна трактувати як (N/2)- точкове ШПФ. Отже, N -точкове ШПФ можна обчислити за допомогою комбінування двох N/2 -точкових ШПФ. Продовження рекурсії приводить до 2-точкових ШПФ. які виконуються без використання множень. На рис. 5.1 приведене 8-точкове ШПФ, побудоване за цією схемою. Причому, вхідна послідовність наведена в біт-інверсному виді.

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

і

Рис.5.1.Алгоритм ШПФ з прорідженням за часом (N=8)

Для досягнення високої продуктивності DSP – процесорів застосовуються такі методи і прийоми:

- введення апаратного перемножувача-накопичувача і схеми циклічного зсуву;

- поділ шин адрес і даних (Гарвардська архітектура);

- використання багатомашинних структур;

- розвинені засоби зберігання - блоки регістрів, кеш-пам'ять великого обсягу;

- використання скороченої системи команд;

- розвитий паралелізм на різних рівнях: пристроїв пам'яті, суматорів, перемножувачів, шин, процесорних елементів; на рівні виконання команд;

- побудова багатозв’язаних процесорних структур з використанням конвеєрного і систоличного опрацювання;

- опрацювання множинних потоків команд і даних на масиві процесорів.

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

Тип процесора                               ADSP-21060

Кількість точок                           256

Основа ШПФ                                4

Прорідження                                часове

Розрядність вхідних даних          32

Такт поступлення вхідних даних20 нс

Час опрацювання                          0.5 мс

ADSP-21060 SHARC – 32-х розрядний процесор опрацювання сигналів з супергарвардською архітектурою використовується для високопродуктивного опрацювання прикладних програм мови, звуку, графіки і растрових зображень, є системою на кристалі, оскільки базується на ядрі сімейства ADSP-21000, має двохпортову пам’ять на чипі SRAM, інтегровані зовнішні пристрої вводу-виводу з підтримкою розподілених шин вводу-виводу. Завдяки кеш інструкцій процесор може виконувати практично кожну команду за один цикл. Чотири незалежних шини для даних, команд та шин вводу-виводу плюс перехресні переключення між зв’язками пам'яті, яка може бути сконфігурована максимум з 128Кслів по 32-біти, з 256Кслів по 16-бітів для даних, та 80Кслів по 48-біт для інструкцій (чи 40-бітові дані), чи з різних комбінацій довжин слів, які поміщаються у 4Мбіти. Але до пам'яті можна звертатися лише по 16-, 32-, чи 48бітних шинах.

У режимі мультиопрацюваннядозволяється підключення шістьох процесорів ADSP-21060 і паралельне їх функціонування. Єдиний адресний простір дозволяє прямі міжпроцесорні доступи до внутрішньої пам'яті кожного ADSP-21060. Розподілена логіка арбітражу шини керує даним режимом і розподіляє ресурси процесорів між собою. Арбітраж надає шині вибраний чи встановлений пріоритет. Максимальна швидкодія при міжпроцесорній передачі даних складає 240 Mbytes/s по link-портах чи по зовнішньому порту. Процесори сімейства ADSP-21000 підтримують стандарт ІЕЕЕ1149.1 Joint Test Action Group (JTAG) для відлагодження системи.

Дискретний сигнал у вигляді кінцевої часової послідовності 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.

Кількість множень дійсних відліків сигналу на комплексне ядро в (5.1) дорівнює N², а кількість додавань комплексних чисел - (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 і запишемо відповідності між символами ДПФ, введеними вище, і цим оператором.

 

Використовуючи вищенаведене і розташовуючи символи ДПФ у впорядкованому вигляді, зобразимо ШПФ геометрично за допомогою графа.

Рис.5.2. Граф ШПФ із проріджуванням за часом при N=8

Відзначимо, що відліки вхідної послідовності переходять у відповідні ДПФ нульового рівня відповідно до інверсії їхній двійкових номерів (операція називається перестановкою вхідних відліків). Наприклад, десятковий номер 4|₁₀ у двійковому вигляді запишеться як 100|₂. Інверсія числа 100|₂ (у прочитанні з права на ліво) запишеться як 001|₂ = 1|₁₀. Таким чином, вхідний відлік під номером 4 співпаде з першим ДПФ X_0,1(0). Перестановку для всіх відліків можна показати стрілками переходу: 0 → 0, 1 → 4, 2 → 2, 3 → 6, 4 → 1, 5→ 5, 6 → 3, 7 → 7.

.Алгоритм перетворення

Алгоритм ШПФ можна розробити, спираючись на граф ШПФ при 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 в ).

Змінні зв'язані між собою так:

Ці співвідношення отримані при аналізі графа ШПФ.

Для приведеного графа побудована таблиця, у якій для кожного кроку перетворення занесені індекси і їхні межі зміни, що використані в циклах програми. Нижче наведений алгоритм програми. Його особливість - результат виходить у масиві вхідних даних. Алгоритм побудований для випадку комплексних вхідних даних, як більш загальний випадок.

Алгоритм ШПФ із проріджуванням за часом

Вхідні дані в алгоритмі:

Х(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 2^{step +1}.

6. Якщо іnput = group 2^step+1+2^step: group←group+1, перейти до кроку 4.

7. [Базова операція]

pow ←group_max *<input>₂^step+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. k←0.

2. Якщо k = N, то виконання алгоритму припиняється.

3. n← m← 0 (n←0,m←0).

4. Якщо m = v: перейти до кроку 7.

5. Якщо біт з номером m (0-ої біт - наймолодший) числа k дорівнює 1,

  то n←n + 2^{v - m - 1}.

6. m←m+1, перейти до кроку 4.

7. Якщо k < n: X(k)↔ X(n).

8. k←k+1, перейти до кроку 2.

Приклад виконання для 64-точкового перетворення за основою 4

Порядок розташування відліків

Порядок перед відповідною ітерацією			Номер метелика в ярусі
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

5.2. Аналіз (розробка) блок-схеми виконання алгоритму ШПФ на заданому типі процесора

Алгоритм базової операції ШПФ за основою 4 і проріджування за часом можна представити так:

А'₁ = А₁ + A₂W₁ + A₃W₂ + A₄W₃ = (А₁ + A₃W₂) + (A₂W₁ + A₄W₃),

A'₂ = A₁   jA₂W₁ – A₃W₂ ± jA₄W₃ = (A₁ – A₃W₂)  j(A₂W₁ - A₄W₃ ),

A '₃ = A1 - A₂W₁ + A₃W₂ - A₄W₃ = (A₁ + A₃W₂) - (A₂W₁ + A₄W₃),

A'₄ = A₁ ± jA₂W₁ – A₃W₂   jA₄W₃ = (A₁ - A₃W₂) ± j(A₂W₁ - A₄W₃),

де A'₁, A'₂, А'з, А'₄ - результати базової операції; А₁, А₂, А₃, А₄ - вхідні відліки; W ₁, W ₂, W ₃ - комплексні коефіцієнти; j - уявна одиниця, верхній знак перед j відповідає прямому, нижній - оберненому ШПФ.

ReA'₁ = [ReА₁ + (ReA₂*ReW₂ - ІmA₃*ImW₂)] + [(ReA₂*ReW₁ - ImA₂*ImW₁) + (ReA₄ *ReW₃ – ImA4*ImW3)],

ІмA'₁ = [Іm A₁ + (Re A₃*Im W₂ + ImA₃*Re W₂)] + [(ReA₂*ImW₁ + ІmA₂*ReW₁) + (ReA₄*ImW₃ + ImA₄*Re W₃)],

RеA'₂ = [ReA₁ - (ReA₃*ReW₂ - ImA₃*ImW₂)] ± [(ReA₂*ImW₁ + ImA₂*ReW₁) – (ReA₄*ІmW₃ + ImA₄*ReW₃)],

ImA'₂ = [ImA₁ - (ReA₃*ІmW₂ + ImA₃*ReW₂)]  [(ReA₂*ReW₁ - ImA₂*ImW₁) - (ReA₄*ReW₃ - ImA₄*ImW₃)],

ReA'₃ = [ReA₁ + (ReA₃*ReW₂ - ImA₃*ImW₂)] - [(ReA₂*ReW₁ - ImA₂*ImW₁) + (ReA₄*ReW₃ - ImA₄*ImW₃)],

ІmA'₃ = [ІmA₁ + (ReA₃*ImW₂ + ImA₃*ReW₂)] - [(ReA₂*ImW₁ + ImA₂*ReW₁) + (ReA₄*lmW₃ + ImA₄*ReW₃)],

ReA'₄ = [ReA₁ - (ReA₃*ReW₂ – ImA₃*ImW₂)]  [(ReA₂*ImW₁ + ImА₂*ReW₁) - (ReA4*ReW3 -ImA₄*ReW₃)],

ImA'₄ = [ImA₃ - (ReA₃*ImW₂ + ImA₃*ReW₂)] ± [(ReA₂*ReW₁ - ImA₂*Im W₁) - (ReA4*ReW3 – ImA₄*ImW₃)]

Для виконання базової операції вимагається виконати 12 операцій множення і 22 додавання.

Табл.5. Порядок слідування відліків для кожного ярусу

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
…
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

 

Рис.5.3. Блок-схема 64-точкового перетворення за основою 4