Тема 6
Реалізація алгоритмів обробки сигналів на ПЛІС
Використання ПЛІС для високопродуктивної цифрової обробки сигналів та зображень.
Однокристальна реалізація ШПФ на ПЛІС.
Оцінка продуктивності вузла виконання операцій ШПФ на ПЛІС.
Загальна структурна схема реалізації реалізації обробки сигналів на ПЛІС.
Структура потокового (ковзаючого) процесора ШПФ.
Розглядаються передумови і методика однокристальної реалізації швидкого перетворення Фур'є на приладах програмувальної логіки фірми Xіlіnx. Приводяться реальні показники по швидкодії і займаному обсязі модулів, створених на ряді інструментальних засобів вітчизняного виробництва.
В даний час дуже актуальна задача швидкої обробки великих масивів даних, що спричиняє значне збільшення продуктивності обробляючих пристроїв. У зв'язку з цим останнім часом розвивається тенденція реалізації високошвидкісних пристроїв цифрової обробки сигналів (ЦОС) на програмувальних логічних схемах (ПЛІС). ПЛІС типу FPGA (Fіeld Programmable Gate Array) фірми Xіlіnx ідеально підходять для рішення задач потокової обробки даних з досить регулярною структурою алгоритму, що саме і характерно для задач ЦОС. При цьому за рахунок можливості апаратного розпаралелювання процесу обробки, гнучкої адаптації структури пристрою під алгоритм, високої ефективності інтегрованих засобів розробки досить просто побудувати в найкоротший термін високопродуктивну систему ЦОС на одному кристалі. Тому область застосування ПЛІС Xіlіnx практично безмежна: це телекомунікації і мережні рішень, відеообробка, промислове устаткування, вимірювальна і медична техніка, а також спеціальна апаратура.
1. Використання ПЛІС для високопродуктивної цифрової обробки сигналів та зображень
Є ряд альтернативних рішень побудови високопродуктивних систем, зокрема на замовлених інтегральних схемах (ASІ) і спеціалізованих процесорах цифрової обробки сигналів (DSP). Розглядати питання реалізації системи з використанням ASІ не будемо, оскільки даний підхід окуповує себе тільки при досить багатосерійному виробництві й в умовах вітчизняного ринку зовсім неприйнятний. У той же час продуктивності більшості сучасних DSP, як правило, не вистачає для однокристальної реалізації алгоритму і, як наслідок, виникає необхідність побудови багатопроцесорних систем на базі однокристальних цифрових процесорів обробки сигналів із властивою складністю сполучення декількох процесорів і налагодженням їхнього функціонування в реальному масштабі часу. Вартість кінцевої реалізації подібної системи залишає бажати кращого.
Зробимо порівняльну оцінку продуктивності універсального процесора, процесорів ЦОС і ПЛІС Xіlіnx з використанням обчислення тільки числа базових операцій ЦОС - множення з нагромадженням у секунду MAC (Multіply-Accumulate). На рис.1 приведені характеристики по продуктивності універсального процесора Pentіum ІІ (450 МГЦ), процесорів ЦОС TMS320C5416 (160 МГЦ), TMS320C6701 (167 МГЦ) і AD21062 (40 МГЦ), ПЛІС Xіlіnx XCV100-4 (серія Vіrtex, 100 тис. вентилів) і XCV400-4 (серія Vіrtex, 400 тис. вентилів) при виконанні МАС 8-, 16- і 32-бітних операндов з фіксованою комою.
INCLUDEPICTURE "../../../../../Svitlana/Ksm-53_2/Vavruk/text/Однокристальная%20реализация%20алгоритма%20БПФ%20на%20ПЛИС%20фирмы%20Xilinx.files/67.gif" \* MERGEFORMAT
Рис. 1. Порівняльні характеристики різних апаратних засобів по продуктивності
Продуктивність ПЛІС Xіlіnx на задачах ЦОС тим вище, чим більш висока паралельність обробки використовується в алгоритмі, що веде за собою відповідне збільшення обсягу логіки на кристалі. Однак досить малий кристал ПЛІС Xіlіnx XCV100 на 8-бітних операціях забезпечує продуктивність, майже на порядок переважаючу показники могутнього ЦОС- процесора. Це обумовлено розпаралелюванням самого процесу обробки і ефективним використанням архітектурних особливостей ПЛІС, причому, що особливо важливо, за рахунок високої швидкості міжкристального обміну ПЛІС можливий багатоканальний ввід/вивід даних на граничних частотах, аж до 200 Мгц.
Звичайно, було б некоректним проводити аналіз порівняльної продуктивності реалізації алгоритмів ЦОС без врахування їх вартості. На рис. 2 приведена питома вартість 1 млн МАС у секунду для раніше розглянутих пристроїв, і, як видно, ПЛІС забезпечують безпрецедентно низькі вартісні витрати при значному виграші в .продуктивносоті.
INCLUDEPICTURE "../../../../../Svitlana/Ksm-53_2/Vavruk/text/Однокристальная%20реализация%20алгоритма%20БПФ%20на%20ПЛИС%20фирмы%20Xilinx.files/68.gif" \* MERGEFORMAT
Рис. 2. Вартість 1 млн МАС у секунду для різних апаратних засобів
Для реалізації високошвидкісних пристроїв ЦОС найбільш прийнятні ПЛІС таких сімейств, як Vіrtex, Vіrtex-E, а також XC4000XL/XLA/XV і Spartan/XL, основні характеристики яких по серіях приведені в табл. 1.
Таблиця 1. Основні характеристики ПЛІС Xіlіnx серій Vіrtex, Vіrtex-e, XC4000XL/XLAXV, Spartan/XL
Привабливою рисою ПЛІС Xіlіnx для реалізації алгоритмів ЦОС у порівнянні з ПЛІС інших фірм є наявність внутрішнього швидкодіючого (до 250 МГЦ для Vіrtex-І, до 133 МГЦ для XC4000X) розподіленого ОЗУ, поєднуваного в блоки необхідного розміру. Використання даного ОЗУ дуже ефективно для реалізації алгоритмів ЦОС методом розподіленої арифметики, а також для збереження коефіцієнтів, результатів проміжних обчислень і т.п.
Досить добре використовується розподілене ОЗУ Xіlіnx при реалізації алгоритму швидкого перетворення Фур'є.
2. Однокристальна реалізація на ПЛІС алгоритму швидкого перетворення Фур'є
Задача виконання ШПФ за мінімальний час є досить актуальною при побудові швидкодіючих систем спектрального аналізу задач виявлення, цифрової фільтрації в частотній області і т.д..
В даний час існує досить багато реалізацій алгоритму ШПФ на замовлених НВІС і процесорах ЦОС, однак реалізація алгоритму на ПЛІС дозволяє створити найбільш оптимальні архітектурні рішення з максимальною продуктивністю для сучасного технологічного рівня НВІС.
Обчислення прямого ДПФ у загальному випадку робиться по наступному виразу:
де x(n) - послідовність з N тимчасових відліків;
X(k) - послідовність з N частотних відліків;
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\f2.gif" \* MERGEFORMATINET
Обчислення безпосередньо по формулі (1) вимагає дуже великого числа операцій: приблизно N2 операцій множення і N2 операцій додавання комплексних чисел. Алгоритми ШПФ дозволяють значно скоротити їхнє число.
Розглянемо алгоритм швидкого перетворення Фур'є з проріджуванням за часом. Якщо послідовність x(n) довжиною N = 2L, де L > 0, L - ціле, розділити на дві N/2 - точкові послідовності, що складаються з x(n) з парними і непарними номерами відповідно, то вираз для ДПФ можна записати у виді:
де x(n) - послідовність з N тимчасових відліків;
X(k) - послідовність з N частотних відліків;
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\f4.gif" \* MERGEFORMATINET — коефіцієнти перетворення,
де INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\f5.gif" \* MERGEFORMATINET .
Кожна із сум у (2) є N/2-точковим ДПФ, що аналогічним чином можна представити через N/4-точкові, N/4- точкові через N/8-точкові і т.д. , поки не залишаться тільки 2-точкові . Таких ступенів перетворення усього буде L = log2 N. На m-ступені відбувається перетворення безлічі N комплексних чисел Xm(n) у безліч N комплексних чисел Xm+1(n) відповідно до базової операції "метелик", описуваної виразами:
На рис. 3 зображений спрямований граф, що реалізує алгоритм ШПФ для N = 8 із проріджуванням за часом.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\69.gif" \* MERGEFORMATINET
Рис. 3. Алгоритм ШПФ 8 точок із проріджуванням за часом
Процес обчислення повного перетворення можна умовно розбити на три кроки. На першому відбувається перетворення вхідної послідовності xn відповідно до двійкової інверсії номерів і наступним обчисленням першого часткового перетворення відповідно до виразу (3). На другому відбувається обчислення другого часткового перетворення, на третьому - повного перетворення Xn. Аналогічно для обчислення ШПФ 256 точок буде потрібно 8 кроків, 1024 точки - 10 кроків. Подібним чином можна представити ШПФ для будь-якого N = 2L, де L? > 0, L - ціле і дорівнює числу кроків.

3. Оцінка продуктивності вузла виконання операцій ШПФ на ПЛІС.
Оцінимо необхідну продуктивність пристрою обробки. Для обчислення ШПФ 256 точок за основою 2 з комплексними вхідними даними потрібно приблизно 3 тис. множень дійсних операндів і 5,5 тис. додавань дійсних операндів, для 1024 - точкового ШПФ за основою 2 - приблизно 16 тис. множень і 28,5 тис. додавань. Оцінку проведемо за допомогою наступного виразу:
де NMAC - число операцій типу множення-нагромадження, c-1;
Nумн. - число множень, необхідних для обчислення перетворення;
fотсч. - частота надходження вхідних даних, Гц;
Nумн. - розмір перетворення.
Таким чином, при частоті надходження вхідних даних 40 МГЦ продуктивність пристрою обчислення ШПФ 256 точок повинна складати не менш 460 млн МАС у секунду, пристрою обчислення ШПФ 1024 точки - не менш 620 млн МАС у секунду.
4. Загальна структурна схема реалізації реалізації обробки сигналів на ПЛІС.
На рис. 4 представлена структурна схема пристрою, що реалізує алгоритм ШПФ на ПЛІС. Розглянемо призначення кожного блоку. Вхідне ОЗУ використовується для завантаження вихідної послідовності, збереження результатів проміжних обчислень і вивантаження результатів перетворення. Буферне ОЗУ потрібно тільки для збереження результатів проміжних обчислень, у ПЗУ зберігаються значення коефіцієнтів WNr. Застосування двох банків ОЗУ дозволяє сполучити операції читання і запису, а також забезпечити коректність обробки даних. Блок "метелик" виконує обчислювальні дії відповідно до виразу (3), причому число помножувачів у загальному випадку може бути різним - від 1 до 4. Блок керування відповідає за загальну синхронізацію схеми і видачу необхідних сигналів керування.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\70.gif" \* MERGEFORMATINET
Рис. 4. Узагальнена структурна схема ШПФ на ПЛІС Xіlіnx
Якщо обчислення перетворення відповідно алгоритму ШПФ при N = 256 відбувається за 8 ступенів, то при апаратній реалізації на ПЛІС потрібно додати ще 2 ступені - ступінь завантаження вихідних даних і ступінь вивантаження результатів перетворення. Таким чином, повне перетворення вимагає 10 ступеней:
1 ступінь - запис вхідної послідовності у вхідне ОЗУ відповідно до двійкової інверсії номерів. 2 ступінь - перша ступінь перетворення. Дані зчитуються з вхідного ОЗУ, перетворюються і записуються в буферне ОЗУ.
3 ступінь - друга ступінь перетворення. Дані зчитуються з буферного ОЗУ, перетворюються і записуються у вхідне ОЗУ.
4, 6, 8 ступіні аналогічні другій ступені.
5, 7, 9 ступіні аналогічні третій ступені.
10 ступінь - вивантаження отриманого перетворення з вхідного ОЗУ.
Приведена на рис. 4 структурна схема з двома помножувача "метелика" реалізована у виді функціонально закінчених модулів ШПФ 256 і 1024 точки і розрядністю вхідних даних і коефіцієнтів 16 біт для ПЛІС фірми Xіlіnx серій Vіrtex і XC4000XL/XLA/XV. Отримані якісні і кількісні характеристики модулів приведені в табл. 2.
Таблиця 2. Характеристики М-модулів ШПФ на ПЛІС серії Vіrtex
Дані модулі ШПФ, надалі М-модулі (Макро-модулі), що поставляються як додаткові бібліотеки для системи проектування Foundatіon фірми Xіlіnx, можуть легко бути додані в створюваний користувачем проект зі збереженням якісних і кількісних характеристик модуля. Подібна незалежність параметрів модуля від навколишньої користувальницької логіки обумовлена використанням спеціальної методики топологічного розміщення, завдяки чому всі модулі є лінійно орієнтованими макросами (RPM), а також використанням тимчасових обмежень затримок поширення сигналів по кристалі (атрибута TІMESPEC).
Розглянуті М-модулі ШПФ оперують з 16-розрядними вхідними даними і коефіцієнтами перетворення. Однак реальна розрядність даних , що надходять, для деяких високошвидкісних додатків обмежується 12, а іноді і 8 бітами, що спричиняє значне скорочення обсягу модуля ШПФ і відповідний ріст продуктивності. Модулі, що поставляються, допускають оперативну модифікацію під необхідну розрядність і розмір перетворення.
У табл. 3 приведені параметри деяких ПЛІС Xіlіnx сімейств Vіrtex/Vіrtex-E і XC4000X, що допускають однокристальну реалізацію розроблених модулів.
Таблиця 3. Основні характеристики ПЛІС серій Vіrtex і XC4000
Примітка:
* - одна логічна комірка містить 4-вхідну LUT-таблицю і тригер.
** - випадок використання всіх логічних ресурсів у якості ОЗУ.
Із зіставлення даних табл. 2 і табл. 3 видно, що після реалізації модуля ШПФ на розглянутих кристалах залишаються значні вільні вентильні ресурси, які можна використовувати для створення в тієї ж ПЛІС додаткових пристроїв користувача, наприклад, вбудованого контролера шини PCІ і логіки сполучення з аналого-цифровим перетворювачем (рис. 6).
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\73.gif" \* MERGEFORMATINET
Рис. 6. Інтегрований підхід до реалізації пристрою цифрової обробки на ПЛІС Xilinx

5Структура потокового (ковзаючого) процесора ШПФ.
У загальному випадку при побудові М-модуля ШПФ можна піти декількома шляхами: або спроектувати модулі з малими займаними обсягами, великим часом перетворення і малою швидкістю надходження вхідних даних (до 15 МГЦ), або реалізувати ковзний ШПФ із малим часом перетворення і великою швидкістю надходження даних (до 150 МГЦ). Другий шлях, хоча і дозволяє одержати чудові результати по швидкодії, але характеризується значними апаратними витратами, що найчастіше розподіляються на кілька кристалів. Однак, у зв'язку з появою ПЛІС фірми Xіlіnx великого обсягу (до 4 млн логічних вентилів) і з великих числом зовнішніх користувальницьких висновків стала можливим однокристальна реалізація високошвидкісного ковзного перетворення Фур'є з безупинним надходженням даних на частотах до 150 Мгц. Основна ідея реалізації ковзного ШПФ полягає в тому, що для обчислень на кожній ступені використовується окремий закінчений блок, забезпечується конвеєризація в межах не тільки однієї ступені, але і всього модуля. При цьому час перетворення буде рівним часу обчислень на одній ступені. Структура блоку обробки приведена на рис. 7. У табл. 4 представлені орієнтовані дані по швидкодії і займаному обсязі М-модулів ШПФ, побудованих відповідно до даного алгоритму.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\62.gif" \* MERGEFORMATINET
Рис. 7. Структура однокристального ковзаючого ШПФ на ПЛІС Vіrtex
Маршрут проектування й апаратна реалізація ШПФ на ПЛІС
Маршрут проектування пристрою ЦОС на ПЛІС Xіlіnx з використанням спеціалізованих бібліотек М-модулів, у тому числі ШПФ, представлений на рис. 8.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\63.gif" \* MERGEFORMATINET
Рис. 8. Маршрут проектування пристрою ЦОС на ПЛІС Xіlіnx
Ввід проекту можливо здійснювати декількома способами:
· інтерактивний графічний ввід в схемотехничному редакторі;
· текстове ввід мовою опису апаратури високого рівня;
· діаграмами станів кінцевого автомата.
При введенні проекту використовуються бібліотеки стандартних логічних функцій і додаткові макробібліотеки (ШПФ, цифрові фільтри, PCІ, VME і т.п. ).
Потім виконується моделювання проекту з верифікацією заданих функцій і топологічне трасування ПЛІС.
Апаратна реалізація описаних М-модулів ШПФ може виконуватися з використанням вітчизняних інструментальних модулів XDSP-680 і SETCORE-1M [8, 9]. Що являють собою дані модулі? В основі XDSP-680 лежить плата з розніманням PCІ 33/32, що містить до 4-х ПЛІС Xіlіnx серій Spartan/XC4000 із загальним обсягом до 680 тис. вентилів, вісім банків високошвидкісного ОЗУ 128 КЅ8 і два банки flash-пам'яті (рис. 9). Модуль SETCORE-1M передбачає установку однієї ПЛІС серії Vіrtex з обсягом до 800 тис. вентилів, шести банків статичного ОЗУ 64 КЅ16, flash-пам'яті до 16 Мбіт (рис. 10).
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\54.jpg" \* MERGEFORMATINET
Рис. 9. Зовнішній вигляд інструментального модуля XDSP-680
Обидва інструментальних модуля містять зовнішні цифрові порти і передбачають установку дочірніх плат, наприклад АЦП/ ЦАП, процесор ЦОС, додаткове ОЗУ, оптичний інтерфейс. Таким чином, змінюючи конфігурацію встановлюваних дочірніх плат під визначену задачу, модулі дозволяють за рахунок універсальності вирішувати практично будь-які задачі цифрової обробки сигналів - від цифрової фільтрації, у тому числі двовимірної, до спектрального аналізу і многоканальної кореляційної обробки.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\65.jpg" \* MERGEFORMATINET
Рис. 10. Зовнішній вигляд інструментального модуля SETCORE-1M
М-модуль ШПФ на серії Spartan був застосований при розробці на базі XDSP-680 високочастотного спектро-аналізатора сигналів реального часу зі смугою до 10 Мгц. У цьому проекті М-модуль ШПФ був з'єднаний з М-модулем контролера PCІ в системі проектування Foundatіon, отримана топологія завантажена в ПЛІС модуля XDSP. Додатково встановлена дочірня плата аналогового введення (рис. 11) і на основі драйверів, що додаються, написана програма наступної обробки спектральної інформації на персональному комп'ютері.
INCLUDEPICTURE "A:\\Однокристальная реализация алгоритма БПФ на ПЛИС фирмы Xilinx.files\\66.jpg" \* MERGEFORMATINET
Рис. 11. Стикування XDSP-680 з інтерфейсом користувача і PC
Стикування XDSP-680 з інтерфейсом користувача і PCВ висновок відзначимо, що ПЛІС Xіlіnx завдяки своїм багатим архітектурним особливостям і розвитим засобам проектування дозволяють реалізовувати великі системи цифрової обробки сигналів з максимальною ефективністю за часом і якістю виконання проекту і по його вартості.
Таблиця 4. Характеристики М-модулів ковзного ШПФ на ПЛІС Xіlіnx