Особенности реализации систем булевых функций на ПЛИС
Предлагается метод синтеза системы булевых функций на программируемых больших интегральных схемах с архитектурой FPGA. Метод ориентирован на число входов в комбинационных логических блоках. Рассмотрены модификации метода для двух и более входов комбинационных логических блоков. Приведены примеры при...
Збережено в:
| Дата: | 2004 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/6409 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Особенности реализации систем булевых функций на ПЛИС / А.А. Баркалов, А.В. Матвиенко, А.А. Красичков // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 79-86. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859644653235601408 |
|---|---|
| author | Баркалов, А.А. Матвиенко, А.В. Красичков, А.А. |
| author_facet | Баркалов, А.А. Матвиенко, А.В. Красичков, А.А. |
| citation_txt | Особенности реализации систем булевых функций на ПЛИС / А.А. Баркалов, А.В. Матвиенко, А.А. Красичков // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 79-86. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| description | Предлагается метод синтеза системы булевых функций на программируемых больших интегральных схемах с архитектурой FPGA. Метод ориентирован на число входов в комбинационных логических блоках. Рассмотрены модификации метода для двух и более входов комбинационных логических блоков. Приведены примеры применения предложенных методов.
|
| first_indexed | 2025-12-07T13:26:40Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2004, № 3 79
Предлагается метод синтеза си-
стемы булевых функций на прог-
раммируемых больших интеграль-
ных схемах с архитектурой FPGA.
Метод ориентирован на число вхо-
дов в комбинационных логических
блоках. Рассмотрены модифика-
ции метода для двух и более вхо-
дов комбинационных логических
блоков. Приведены примеры при-
менения предложенных методов.
А.А. Баркалов, А.В. Матвиенко,
А.А. Красичков, 2004
ÓÄÊ 681.324
À.À. ÁÀÐÊÀËÎÂ, À.Â. ÌÀÒÂÈÅÍÊÎ,
À.À. ÊÐÀÑÈ×ÊÎÂ
ÎÑÎÁÅÍÍÎÑÒÈ ÐÅÀËÈÇÀÖÈÈ
ÑÈÑÒÅÌ ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ
ÍÀ ÏËÈÑ
В настоящее время требования к характери-
стикам средств вычислительной техники
(ВТ) постоянно растут. Современная вычис-
лительная система должна обладать высоким
быстродействием, малыми габаритами и
приемлемым временем проектирования. Для
удовлетворения этих требований при проек-
тировании цифровых схем ВТ используются
программируемые логические интегральные
схемы (ПЛИС). Наиболее широко применя-
ются две разновидности ПЛИС: CPLD и
FPGA [1]. Синтез цифровых устройств сво-
дится к реализации системы булевых функ-
ций (БФ) в базисе конкретной ПЛИС. Ар-
хитектура CPLD функционально соответ-
ствует широко распространенным микросхе-
мам программируемых логических матриц
(ПЛМ), поэтому методы синтеза в этом бази-
се известны и особых сложностей не пред-
ставляют [2]. Микросхемы FPGA подразуме-
вают принципиально новые методы реализа-
ции систем булевых функций ввиду особен-
ностей своей архитектуры. Алгоритмы фун-
кционального синтеза на FPGA являются
ноу-хау фирм-производителей конкретных
микросхем и встроены в различные САПР
иностранного происхождения, которые не
всегда отвечают требованиям отечественных
разработчиков средств ВТ. Поэтому актуаль-
ной является проблема реализации систем
булевых функций на ПЛИС с архитектурой
FPGA. В настоящей работе предлагаются
методы декомпозиции БФ для реализации их
в базисе FPGA.
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, А.А. КРАСИЧКОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 80
Функциональный базис FPGA представляет собой конечное множество
комбинационных логических блоков (КЛБ), которые могут реализовать любую
булеву функцию от R переменных, либо две независимые функции от (R-1) пе-
ременных, где R − количество входов КЛБ. В производимых в настоящее время
серийно микросхемах FPGA R = 2…5 [1]. Число переменных в БФ проектируе-
мых систем обычно значительно больше и колеблется в широких пределах. По-
этому для реализации системы булевых функций от N переменных необходимо
каждую функцию представить в виде совокупности подфункций от M перемен-
ных, где M≤ R. То есть возникает задача функциональной декомпозиции в базис
с меньшим числом входов, для решения которой можно использовать следую-
щие известные методы:
1. Минимизация c помощью карт Карно или законов алгебры логики. Этот
метод применим, если функция задана в виде совершенной дизъюнктивной
или конъюнктивной нормальной формы (СДНФ или СКНФ соответственно)
и не всегда приводит к реализации функции на КЛБ, так как не ориентирован
на него.
2. Использование законов Де-Моргана. Данный метод всегда приводит к
реализации функции на КЛБ с любым R, однако число КЛБ значительно превы-
шает минимально возможное для реализации заданной функции, так как каждый
блок реализует отдельный терм СДНФ или СКНФ, а остальные блоки исполь-
зуются для объединения групп термов.
3. Разложение Шеннона. Этот метод также приводит к реализации любой
функции на КЛБ, но число подфункций, из которых состоит реализуемая функ-
ция, исчисляется целыми степенями двойки и зависит от числа переменных раз-
ложения. Для реализации функции на КЛБ это самый нерациональный метод с
точки зрения как аппаратурных затрат, так и быстродействия, так как схема
имеет древовидную структуру.
Поскольку КЛБ может реализовать все БФ R переменных, достаточно обес-
печить представление заданной функции в виде минимального числа подфунк-
ций с числом переменных M ≤ R. Функция выражается в виде подфункций та-
ким образом, чтобы пересечение по аргументам в различных подфункциях было
минимальным. В идеальном случае аргументы в подфункциях не пересекаются,
тогда реализация такой функции в базисе КЛБ наиболее рациональна.
Существует множество вариантов соединения КЛБ для реализации функ-
ции, которые могут состоять из фрагментов структур последовательного и па-
раллельного типов, представленных на рис. 1.
Быстродействие при параллельном соединении КЛБ выше, однако, как по-
казали исследования авторов, большинство БФ реализуются в виде последова-
тельного соединения.
Для реализации БФ на ПЛИС FPGA авторы предлагают следующие методы,
отличающиеся параметром R.
1. Метод реализации функций на КЛБ с R = 2.
ОСОБЕННОСТИ РЕАЛИЗАЦИИ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ПЛИС
Комп’ютерні засоби, мережі та системи. 2004, № 3 81
КЛБ
КЛБ
...
x1
x2
xR ...
xR+1
x2R-1 КЛБ...
xi
xN
F
...
КЛБ
КЛБ... F
...
x 1
x 2
x R
КЛБ...
x R+1
x R+2
x 2R
КЛБ...
x i
x i+1
x N
...
РИС. 1. Последовательное и параллельное соединения КЛБ
Пусть функция F является БФ от N переменных: F = F(x1, x2, …, xN) и ее не-
обходимо реализовать на КЛБ с R=2. Поскольку заранее неизвестно, какие ар-
гументы функции могут быть вынесены в подфункции, то возникает необходи-
мость проверки такой возможности для всех возможных групп аргументов. Наи-
более рационально сразу попытаться разбить функцию F на две подфункции с
независимыми аргументами. Это приводит к реализации функции в виде парал-
лельного соединения КЛБ. Такую возможность предлагается проверить с помо-
щью разложения Шеннона и последующего анализа полученных подфункций.
Для проверки возможности отделить от функции группы i аргументов x1, x2,…,
..., xi запишем:
),,...,,(&),...,,(...
),...,,(&),...,,(),...,,(&),...,,(
21
'
21
21
'
221221
'
1211
NiiKiK
NiiiNiii
xxxfxxxf
xxxfxxxfxxxfxxxfF
++
++++
∨∨
∨∨=
где ''
2
'
1 ,...,, Kfff − функции, полученные в результате подстановки в БФ F зна-
чений аргументов ixxx ,...,, 21 , iK 2= , а функции Kfff ,...,, 21 представлены
таблицей истинности (табл. 1).
ТАБЛИЦА 1
ii xxxx 121 ... − KK fffff 1321 ... −
0 0 … 0 0 1 0 0 … 0 0
0 0 … 0 1 0 1 0 … 0 0
0 0 … 1 0 0 0 1 … 0 0
.
.
.
.
.
.
1 1 … 1 0 0 0 0 … 1 0
1 1 … 1 1 0 0 0 … 0 1
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, А.А. КРАСИЧКОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 82
Очевидно, что функции Kfff ,...,, 21 обладают свойством ортогонально-
сти:
1... 1321 =∨∨∨∨∨ − KK fffff , (1)
0&&...&&& 1321 =− KK fffff . (2)
Из формул (1) и (2) следует
KK fffff =∨∨∨∨ −1321 ... ,
……..
KKii ffffff ∨∨∨=∨∨∨ −+ 1121 ...... .
Поскольку дизъюнкция любой группы функций Kfff ,...,, 21 равна инвер-
сии дизъюнкции остальной части системы функций, можно сделать вывод, что
разложение )],...,,(),,...,,([ 2122113 Niii xxxFxxxFFF ++= существует, если мно-
жество функций ''
2
'
1 ,...,, Kfff можно разбить на два подмножества любой раз-
мерности таким образом, что
- в первом подмножестве все элементы равны, во втором – равны нулю;
- в первом подмножестве все элементы равны, во втором – равны единице;
- в первом подмножестве все элементы равны, элементы второго есть инвер-
сия элементов первого множества;
- элементы обоих подмножеств равны.
Разбиение получается после вынесения общих сомножителей за скобки и за-
мены одной из групп функций Kfff ,...,, 21 инверсией другой группы. В ре-
зультате получается функция от двух аргументов-подфункций. При успешном
разбиении каждая подфункция подвергается аналогичному разложению до тех
пор, пока число аргументов в подфункциях не достигнет двух. Более подробно
метод описан в [3].
Если на каком-либо этапе декомпозиции функция или подфункция не мо-
жет быть представлена в виде двух подфункций с независимыми аргументами,
выполняется разбиение на подфункции с общими аргументами. Для этого также
осуществляется разложение Шеннона, причем подфункции ''
2
'
1 ,...,, Kfff пред-
ставляются в виде функций не от N−I, а от N−I+K переменных, где K – число
общих аргументов обеих подфункций.
Рассмотрим пример применения данного метода.
Пусть функция F задана в виде dcbcdacabF ∨∨∨= . Представим ее
в виде [ ])(),( 213 cdfabffF = . Для этого выполним разложение Шеннона по
переменным a и b:
1&&)(&)(& abcbadcbacdbaF ∨∨⊕∨= .
ОСОБЕННОСТИ РЕАЛИЗАЦИИ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ПЛИС
Комп’ютерні засоби, мережі та системи. 2004, № 3 83
То есть cdf ='
1 , dcf ⊕='
2 , cf ='
3 , 1'
4 =f . Эти подфункции нельзя разбить
на два подмножества, удовлетворяющих вышеописанному методу декомпо-
зиции. Согласно методу функцию F можно представить также в виде
[ ])(),( 213 acdfabffF = , т. е. с общим аргументом a. Для этого составим таб-
лицу истинности следующего вида (табл. 2).
ТАБЛИЦА 2
acd cdf ='
1 dcf ⊕='
2 cf ='
3 1'
4 =f
000 0 1 * *
001 0 0 * *
010 0 0 * *
011 1 1 * *
100 * * 0 1
101 * * 0 1
110 * * 1 1
111 * * 1 1
ab 00 01 10 11
Таким образом, из функций '
4
'
1 ff − от двух переменных получаем частично
определенные функции от трех переменных, однако, их также нельзя разбить на
два подмножества для декомпозиции. Представление функции F с общим аргу-
ментом b приведет к такой же таблице.
Далее попробуем представить функцию в виде [ ])(),( 213 adfbcffF = .
Для этого выполним разложение Шеннона по переменным b и c:
)(&)(&)(&0& dabcdacbdacbcbF ∨∨∨∨∨∨= .
То есть, 0'
1 =f , )('
2 daf ∨= , )('
3 daf ∨= , )('
4 daf ∨= . Эти подфункции
тоже нельзя разбить на два подмножества, удовлетворяющих методу. Предста-
вим функцию F в виде [ ])(),( 213 acdfbcffF = (табл. 3).
Из табл. 3 видно, что такое разбиение существует. Это следует из того, что
0'
1 =f , а подфункции '
3
'
2 , ff и '
4f можно склеить в одну, используя неопреде-
ленности )('
4
'
3
'
2 dcafff ⊕∨=== , причем дальнейшая декомпозиция для
функции F не требуется, так как полученная подфункция уже поделена по аргу-
ментам a и c, d. Реализация функции представлена на рис. 2.
2. Метод реализации функций на КЛБ с R>2.
Рассмотрим метод реализации функции на КЛБ с R=3….5 для случая, когда
функция F является БФ от 10 переменных: F = F(x1, x2, …, x10) и R = 4. При реа-
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, А.А. КРАСИЧКОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 84
лизации в виде последовательного соединения КЛБ применяется следующий
метод.
ТАБЛИЦА 3
acd 0'
1 =f )('
2 daf ∨= )('
3 daf ∨= )('
4 daf ∨=
000 0 * 1 *
001 * * 0 *
010 0 0 * 0
011 * 1 * 1
100 0 * 1 *
101 * * 1 *
110 0 1 * 1
111 * 1 * 1
bс 00 01 10 11
a
b
c
& F
d
1
1c
РИС. 2. Реализация функции F на КЛБ
Вначале проверяется возможность разбиения функции на две подфункции –
от трех и семи аргументов, что соответствует ее реализации схемой, показанной
на рис. 3.
РИС. 3. Начальная стадия декомпозиции функции F
Блоком, отмеченным Z, обозначим пока еще неопределенное множество
КЛБ. В дальнейшем будем называть его Z-блок. Выполним разложение Шенно-
FXj
Xj
Xk
КЛБ
Xa
Xb
…
Xg
Z
ОСОБЕННОСТИ РЕАЛИЗАЦИИ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ПЛИС
Комп’ютерні засоби, мережі та системи. 2004, № 3 85
на по переменным xa − xg. Необходимым и достаточным признаком существо-
вания такого разбиения является выполнение условия: полученные подфункции
разбиваются на два подмножества произвольного размера, в каждом из которых
подфункции равны. В данном случае среди 128 подфункций от переменных xi,
xj, xk должно быть два класса одинаковых подфункций. Промежуточная реали-
зация функции ],,),,...,,([ 13 kjigba xxxxxxffF = . Далее поступаем таким же
образом с подфункцией f1, а затем и с ее подфункциями до тех пор, пока на оче-
редном шаге число аргументов не станет меньше либо равным четырем. Если на
каком-либо этапе декомпозиция неосуществима для всех возможных комбина-
ций аргументов, необходимо попытаться выполнить декомпозицию с общими
аргументами. Число таких комбинаций значительно больше, чем при декомпо-
зиции без общих аргументов. Если же и такое разложение невозможно, то дан-
ная функция может быть реализована в виде параллельного соединения КЛБ,
для реализации которой справедлива следующая методика.
Вначале проверяется возможность разбиения функции на две подфункции –
от четырех и шести аргументов, что соответствует ее реализации схемой, пока-
занной на рис. 4.
РИС. 4. Начальное разбиение функции F
Для этого выполняется разложение Шеннона по переменным xa−xd. Чтобы такое
разбиение существовало, как и ранее, необходимо и достаточно, чтобы получен-
ные подфункции разбивались на два однородных подмножества произвольного
размера. В данном случае среди 16 подфункций от 6 переменных xe, xf,,…,xk
должно быть два класса одинаковых подфункций.
Промежуточная реализация функции
],,,,,),,,,([ 13 kjhgfedcba xxxxxxxxxxffF = .
Функция, реализуемая КЛБ по переменным xa - xd, представляет собой буле-
ву переменную для Z-блока. Далее применяется описанная методика декомпо-
зиции для подфункции от семи переменных до тех пор, пока все аргументы не
будут собраны в группы по четыре. Если на каком-либо этапе декомпозиция не-
осуществима для всех возможных комбинаций аргументов, необходимо попы-
таться выполнить декомпозицию с общими аргументами, как было описано вы-
ше. Если и такое разложение невозможно, функцию можно представить в виде
последовательно-параллельного соединения КЛБ со значительным числом об-
щих аргументов в разных КЛБ. Для этого функция разбивается на группы тер-
xa
xb
xc
xd
КЛБ
Fxe
…
xk
Z
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, А.А. КРАСИЧКОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 86
мов СДНФ или СКНФ, каждая из которых реализуется на КЛБ описанными ме-
тодами. Недостатком такого подхода является необходимость перебора всех ва-
риантов разбиения. Авторы разработали методы, позволяющие реализовать та-
кие функции на КЛБ с сужением пространства поиска, однако они выходят за
рамки данной статьи.
Исследования показали, что применение предложенных методов приводит
к более экономичной по числу КЛБ реализации системы булевых функций на
КЛБ, чем в некоторых САПР западного производства [1]. Предлагаемые методы
могут быть использованы при создании отечественных САПР цифровых уст-
ройств на микросхемах программируемой логики с архитектурой FPGA.
1. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах
программируемой логики. – СПб.: БХВ-Петербург, 2002. – 608 с.
2. Баркалов А.А., Палагин А.В. Синтез микропрограммных устройств управления. – Киев:
Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1997. – 136 с.
3. Баркалов А.А., Красичков А.А. Методы декомпозиции булевых функций // Науч. тр.
ДонНТУ. Сер. ИКВТ-2002. – 2002. – Вып. 39. – С. 72 – 80.
Получено 02.03.2004
.
|
| id | nasplib_isofts_kiev_ua-123456789-6409 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T13:26:40Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Матвиенко, А.В. Красичков, А.А. 2010-03-02T11:56:11Z 2010-03-02T11:56:11Z 2004 Особенности реализации систем булевых функций на ПЛИС / А.А. Баркалов, А.В. Матвиенко, А.А. Красичков // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 79-86. — Бібліогр.: 3 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6409 681.324 Предлагается метод синтеза системы булевых функций на программируемых больших интегральных схемах с архитектурой FPGA. Метод ориентирован на число входов в комбинационных логических блоках. Рассмотрены модификации метода для двух и более входов комбинационных логических блоков. Приведены примеры применения предложенных методов. ru Інститут кібернетики ім. В.М. Глушкова НАН України Особенности реализации систем булевых функций на ПЛИС Article published earlier |
| spellingShingle | Особенности реализации систем булевых функций на ПЛИС Баркалов, А.А. Матвиенко, А.В. Красичков, А.А. |
| title | Особенности реализации систем булевых функций на ПЛИС |
| title_full | Особенности реализации систем булевых функций на ПЛИС |
| title_fullStr | Особенности реализации систем булевых функций на ПЛИС |
| title_full_unstemmed | Особенности реализации систем булевых функций на ПЛИС |
| title_short | Особенности реализации систем булевых функций на ПЛИС |
| title_sort | особенности реализации систем булевых функций на плис |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6409 |
| work_keys_str_mv | AT barkalovaa osobennostirealizaciisistembulevyhfunkciinaplis AT matvienkoav osobennostirealizaciisistembulevyhfunkciinaplis AT krasičkovaa osobennostirealizaciisistembulevyhfunkciinaplis |