Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций

Предложен алгоритм оптимизации многоуровневых представлений систем ДНФ полностью определенных булевых функций на основе построения диаграмм двоичного выбора. Приведены результаты экспериментального исследования этого алгоритма, используемого в качестве предварительного оптимизационного этапа синтеза...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Бибило, П.Н., Леончик, П.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2009
Schriftenreihe:	Управляющие системы и машины
Schlagworte:	Новые методы в информатике
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/82772
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системы и машины. — 2009. — № 6. — С. 42–49. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-82772
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-827722025-02-05T20:29:44Z Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций Бибило, П.Н. Леончик, П.В. Новые методы в информатике Предложен алгоритм оптимизации многоуровневых представлений систем ДНФ полностью определенных булевых функций на основе построения диаграмм двоичного выбора. Приведены результаты экспериментального исследования этого алгоритма, используемого в качестве предварительного оптимизационного этапа синтеза комбинационных схем в библиотеках проектирования базовых матричных кристаллов и логических схем, реализуемых в составе FPGA. The algorithm of optimization of multilevel representations of DNF systems of the completely defined Boolean functions based on the construction of binary decision diagrams is suggested. The results of the experimental research of this algorithm which is used as a preliminary optimization stage of the synthesis of combinational circuits in the design library of Gate Arrays and logical circuits implemented in the FPGA, are presented. Запропоновано алгоритм оптимізації багаторівневих представлень систем ДНФ повністю визначених бульових функцій на основі побудови діаграм двійкового вибору. Наведено результати експериментального дослідження цього алгоритму, який використано як попередній оптимізаційний етап синтезу комбінаційних схем у бібліотеках проектування базових матричних кристалів та логічних схем, які реалізуються в складі FPGA. 2009 Article Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системы и машины. — 2009. — № 6. — С. 42–49. — Бібліогр.: 8 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82772 519.7 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые методы в информатике Новые методы в информатике
spellingShingle	Новые методы в информатике Новые методы в информатике Бибило, П.Н. Леончик, П.В. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций Управляющие системы и машины
description	Предложен алгоритм оптимизации многоуровневых представлений систем ДНФ полностью определенных булевых функций на основе построения диаграмм двоичного выбора. Приведены результаты экспериментального исследования этого алгоритма, используемого в качестве предварительного оптимизационного этапа синтеза комбинационных схем в библиотеках проектирования базовых матричных кристаллов и логических схем, реализуемых в составе FPGA.
format	Article
author	Бибило, П.Н. Леончик, П.В.
author_facet	Бибило, П.Н. Леончик, П.В.
author_sort	Бибило, П.Н.
title	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
title_short	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
title_full	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
title_fullStr	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
title_full_unstemmed	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
title_sort	алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2009
topic_facet	Новые методы в информатике
url	https://nasplib.isofts.kiev.ua/handle/123456789/82772
citation_txt	Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системы и машины. — 2009. — № 6. — С. 42–49. — Бібліогр.: 8 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT bibilopn algoritmpostroeniâdiagrammydvoičnogovyboradlâsistemypolnostʹûopredelennyhbulevyhfunkcij AT leončikpv algoritmpostroeniâdiagrammydvoičnogovyboradlâsistemypolnostʹûopredelennyhbulevyhfunkcij
first_indexed	2025-11-25T09:37:56Z
last_indexed	2025-11-25T09:37:56Z
_version_	1849754628274520064
fulltext	42 УСиМ, 2009, № 6 УДК 519.7 П.Н. Бибило, П.В. Леончик Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций Предложен алгоритм оптимизации многоуровневых представлений систем ДНФ полностью определенных булевых функций на основе построения диаграмм двоичного выбора. Приведены результаты экспериментального исследования этого алгорит- ма, используемого в качестве предварительного оптимизационного этапа синтеза комбинационных схем в библиотеках проек- тирования базовых матричных кристаллов и логических схем, реализуемых в составе FPGA. The algorithm of optimization of multilevel representations of DNF systems of the completely defined Boolean functions based on the construction of binary decision diagrams is suggested. The results of the experimental research of this algorithm which is used as a pre- liminary optimization stage of the synthesis of combinational circuits in the design library of Gate Arrays and logical circuits imple- mented in the FPGA, are presented. Запропоновано алгоритм оптимізації багаторівневих представлень систем ДНФ повністю визначених бульових функцій на ос- нові побудови діаграм двійкового вибору. Наведено результати експериментального дослідження цього алгоритму, який ви- користано як попередній оптимізаційний етап синтезу комбінаційних схем у бібліотеках проектування базових матричних кристалів та логічних схем, які реалізуються в складі FPGA. Введение. Синтез комбинационных логических схем традиционно разбивается на два больших этапа: глобальную технологически независи- мую оптимизацию и технологическое отобра- жение (technology mapping). В качестве техно- логически независимой оптимизации чаще всего применяется совместная либо раздельная ми- нимизация системы булевых функций в классе дизъюнктивных нормальных форм (ДНФ), по- зволяющая получать оптимизированные двух- уровневые (и/или) представления функций. Оп- тимизированные многоуровневые представле- ния в виде скобочных алгебраических форм функций получаются на основе факторизаци- онных методов оптимизации, а также много- кратного применения разложения Шеннона – такие представления получили названия би- нарных программ [1] или диаграмм двоичного выбора (BDD – Binary Decision Diagram) [2]. BDD оказались эффективной формой представ- ления функций и получили широкое примене- ние [3–6]. Основная проблема при построении BDD – выбор последовательности перемен- ных, по которой ведется разложение Шеннона. В данной статье предлагается алгоритм по- строения BDD для системы полностью опреде- ленных булевых функций. Функции системы за- даются в виде ДНФ, особенности алгоритма – «блоковый» подход к проведению разложений Шеннона при выбранной последовательности переменных разложения и сочетание различ- ных эвристик при выборе такой последователь- ности. Экспериментально исследуется эффек- тивность предложенного алгоритма для синте- за комбинационных схем в базисе элементов отечественных базовых матричных кристаллов (БМК) и структур программируемых логиче- ских интегральных схем типа FPGA (Field-Pro- grammable Gate Arrays). Диаграмма двоичного выбора (BDD) Разложением Шеннона булевой функции ),...,( 1 nxxf по переменной ix называется пред- ставление ),...,( 1 nxxf в виде ).,...,,0,,...,( ),...,,1,,...,(),...,( 111 1111 niii niiin xxxxfx xxxxfxxxf     (1) Функции ),...,1,,...,( 111 nii xxxxf  , 1 1( ,..., ,if x x  10, ,... )i nx x в (1) называются коэффициента- ми разложения. Они получаются из функции ),...,( 1 nxxf подстановкой вместо переменной ix константы 1 и 0 соответственно. Очевидно, что если коэффициенты равны, то ),...,( 1 nxxf = = ),...,,...,( 111 nii xxxxf  . Переменную ix называ- ют в этом случае несущественной или фик- тивной переменной функции ),...,( 1 nxxf . Каж- дый из коэффициентов ),,...,1,,...,( 111 nii xxxxf  ),...,0,,...,( 111 nii xxxxf  может быть разложен по одной из переменных из множества { 1,...,x УСиМ, 2009, № 6 43 1 1, ,...i i nx x x  }. Процесс разложения коэффици- ентов заканчивается, когда все n переменных будут использованы для разложения. На по- следнем шаге разложения коэффициенты вы- рождаются до констант 0, 1. Под диаграммой двоичного выбора, т.е. под BDD, понимается граф, задающий разложение Шеннона булевой функции ),...,( 1 nxxf по всем ее переменным nxx ,...,1 при заданном порядке (перестановке) переменных, по которым про- водится разложение. В статье рассматриваются BDD для системы функций, при этом переста- новки переменных, по которым ведутся разло- жения, одинаковы для всех функций системы. Пример BDD для системы, состоящей из трех функций, приведены на рис. 1. BDD содержит три вида вершин: Рис. 1  функциональные, соответствующие разла- гаемым функциям (из них три корневые вер- шины-функции f 1, f 2, f 3);  вершины–переменные, т.е. вершины, соот- ветствующие переменным разложения;  листовые, соответствующие константным (0, 1) значениям функций. По диаграмме двоичного выбора легко запи- сывается многоуровневое представление буле- вой функции, так как каждой паре <функцио- нальная вершина, вершина-переменная> соот- ветствует разложение (1) Шеннона некоторой функции, при этом различные разлагаемые функции могут иметь одинаковые коэффици- енты разложения. Примечание. При изображении BDD функ- циональные вершины обычно не показывают- ся, так как предполагается, что всем дугам, ве- дущим в вершину-переменную, соответствует одна и та же булева функция, разлагаемая по этой переменной. Под сложностью BDD понимается число функциональных вершин. Вершины-перемен- ные и листовые вершины не учитываются при подсчете сложности BDD. Алгоритм построения BDD для системы функций Постановка задачи Задана система ),...,( 1 nxxF = ( ),...,( 1 1 nxxf ,… , ),...,( 1 n m xxf ) ДНФ полностью определен- ных булевых функций. Требуется построить BDD минимальной сложности для системы F функций. Решение задачи традиционно разбивается на два этапа. Этап 1. Выбор последовательности (пере- становки) переменных nxx ,...,1 , по которой ве- дется разложение Шеннона. Этап 2. Построение BDD по заданной пере- становке переменных разложения. Опишем сначала алгоритм этапа 2 – построе- ние BDD системы ),...,( 1 nxxF = ( ),...,( 1 1 nxxf ,… , ),...,( 1 n m xxf ) при заданной перестановке множества X ={ nxx ,...,1 } переменных. Основная 44 УСиМ, 2009, № 6 идея алгоритма заключается в том, что пере- менные разложения группируются в блоки, раз- ложение ведется по всем переменным очеред- ного блока без сравнения коэффициентов, срав- нение коэффициентов на равенство осуще- ствляется тогда, когда проведено разложение по последней переменной блока. При этом срав- нение коэффициентов сначала проводится «гру- бо» (два коэффициента считаются равными, если они заданы на одном и том же множестве элементарных конъюнкций). Окончательное сравнение коэффициентов на равенство осу- ществляется при «обратном проходе». Алгоритм этапа 2 состоит из следующих шагов: Ш а г 1. Разбиение множества X на попарно непересекающиеся блоки (подмножества) 1,Y 2 ,..., qY Y . 1.1. Если n > 20, то разбиваем X на q блоков qYYY ,...,, 21 , таких, что iY = 3, i = 2, 3, …, q, где iY – мощность блока iY , а iY 5. 1.2. Если же n  20, то разбиение перемен- ных на блоки осуществляется следующим об- разом. Пусть k – число различных элементар- ных конъюнкций, входящих в ДНФ всех функций системы F. Если 3k < n2 , то разбива- ем X на два блока 21,YY , причем 1 3Y n  , 2 3Y  . Если 3k > n2 , то разбиение на блоки осуществляется так же, как и в п.1.1. Ш а г 2 (итерационный). Построение коэф- фициентов разложения Шеннона для функций системы F по переменным блока iY i =1, 2, …, q – 1 и сравнение их на равенство. Сравниваемые коэффициенты разложения функций системы F задаются в виде ДНФ на «остатках» исходных элементарных конъюнк- ций. Из ДНФ, представляющих коэффициен- ты, удаляются поглощаемые конъюнкции. За- тем строится общий список всех конъюнкций (троичных векторов), на которых заданы все коэффициенты, и каждая ДНФ задается мно- жеством номеров из общего списка. Если име- ется троичный вектор, состоящий только из неопределенных элементов «–», то все ДНФ, в которые он попадает, полагаются равными еди- нице. Это приближенная проверка на равенст- во единице рассматриваемой ДНФ, так как оче- видно, что покрыть все булево пространство может не только один вектор (–,…–), такое по- крытие может осуществить несколько троич- ных векторов, состоящих как из неопределен- ных, так и определенных (0,1) компонент. По- сле того, как все ДНФ заданы на общем списке конъюнкций, осуществляется проверка ДНФ на равенство – именно эта процедура позволяет сократить число функциональных вершин BDD. Если множества номеров конъюнкций двух ДНФ имеют неравную мощность, то такие ДНФ не сравниваются. Сравнение ДНФ, заданных на равномощных множествах номеров конъюнк- ций, сводится к проверке равенства множеств номеров: ДНФ считаются равными, если они заданы на одном и том же множестве номеров. Естественно, такой способ сравнения ДНФ при- ближенный, так как некоторые ДНФ могут быть равными, но состоять из различных подмно- жеств элементарных конъюнкций. Как уже го- ворилось, точная проверка коэффициентов на равенство будет сделана позднее. В результате выполнения шага 2 коэффици- енты разложения будут представлять собой функ- ции )( qYf , зависящие от трех переменных, вхо- дящих в блок qY . Ш а г 3. Построение коэффициентов разло- жения Шеннона по переменным блока qY и точ- ное сравнение их на равенство. На этом шаге осуществляется представление функций )( qYf таблицами истинности, после чего восьмиком- понентный вектор-столбец значений функции интерпретируется как число, заданное в дво- ичной системе счисления. Например, вектор 00001001 интерпретируется как число девять. Среди полученных коэффициентов находятся равные (одинаковые) коэффициенты. Так как каждой из 322 = 256 булевых функций, завися- щих от трех аргументов, соответствует един- ственное десятичное число, то сравнение ко- эффициентов f(Yq) сводится к проверке равен- ства чисел, представляющих эти коэффици- енты (функции), и осуществляется быстро. УСиМ, 2009, № 6 45 В результате выполнения шага 3 строится BDD, однако в ней могут быть вершины, соот- ветствующие одинаковым коэффициентам. Ш а г 4 (итерационный). Сокращение числа вершин BDD, соответствующих переменным блоков 1Y , 2Y ,…, 1qY , начиная с переменных блока 1qY . Переменные блоков 1Y , 2Y ,…, 1qY рассматриваются в порядке, обратном по- рядку разложения. Проверка на равенство ко- эффициентов ),...,( 1 1 jxxs , ),...,( 1 2 jxxs , завися- щих от j переменных, сводится к проверке на равенство упорядоченных пар < ),...,( 11 1 0 jxxs , ),...,( 11 1 1 jxxs >, < ),...,( 11 2 0 jxxs , ),...,( 11 2 1 jxxs > ко- эффициентов, зависящих от j – 1 переменной: если в парах равны компоненты с одинаковы- ми номерами, т.е. если ),...,( 11 1 0 jxxs = 2 0 1( ,...s x 1..., )jx  и ),...,( 11 1 1 jxxs = ),...,( 11 2 1 jxxs , то и ко- эффициенты ),...,( 1 1 jxxs , ),...,( 1 2 jxxs равны. Пример. Проиллюстрируем алгоритм на при- мере системы F, состоящей из трех функций 1f , 2f , 3f (табл. 1). Пусть последователь- ность разложения является < 654321 ,,,,, xxxxxx >. Т а б л и ц а 1 Tx Bf x1 x2 x3 x4 x5 x6 f1 f2 f3 1 1 – 0 1 0 0 - - 1 0 1 0 - - 0 1 0 0 – 0 - 1 - 1 1 1 – 1 0 1 0 – 1 0 1 1 0 0 - - 1 1 0 – 1 - 1 1 – 0 1 - 1 0 1 – 0 1 0 1 0 - - 1 - - 1 0 – 1 - 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 Ш а г и 1 – 2. Последовательность перемен- ных разобьется на два блока 1Y = < 321 ,, xxx >, 2Y = < 654 ,, xxx >. Проведем разложение Шен- нона по переменным блока 1Y , ненулевые ко- эффициенты разложения, полученные непо- средственной подстановкой наборов констант вместо переменных разложения, заданы в табл. 2. Коэффициенты разложения зададим на множестве p1, , p6 различных элементарных конъюнкций, всего получается семь коэффи- циентов s1, , s7 (табл. 3), не считая коэффи- циента s0, равного нулю. После задания коэф- фициентов (функций) si, зависящих от трех пе- ременных 4x , 5x 6x , на наборах булева про- странства, выясняется, что s2 = s7, поэтому функция s7 удаляется из рассмотрения. На- чальный вид BDD, полученной после разложе- ния по переменным блока Y1 и сравнения ко- эффициентов, показан на рис. 2. Т а б л и ц а 2 Коэффициент ip 4x 5x 6x i jf is Функция 1p 101 1 000f 1s 1p 101 1 001f 1s 1p , 3p 101 –1– 1 010f 2s 1p 101 1 011f 1s 2p 010 1 110f 4s 2p 010 1 111f 4s 1f 3p –1– 2 000f 3s 2p 010 2 001f 4s 3p –1– 2 010f 3s 2p 010 2 011f 4s 1p 101 2 100f 1s 1p 101 2 101f 1s 6p –10 2 111f 5s 2f 3p –1– 3 010f 3s 2p 010 3 011f 4s 3p , 4p , 5p –1– – –1 1–1 3 100f 6s 3p , 5p –1– 1–1 3 101f 7s 3p , 5p –1– 1–1 3 110f 7s 3f Ш а г 3. Разложения функций 1s ,…, 7s по переменным блока 2Y = < 654 ,, xxx >. Результа- ты разложения проиллюстрированы на рис. 3, а соответствующее многоуровневое представ- ление имеет вид: ;1 4 1  xs ;2 4 3 4 2  xxs ;3 4 3 4 3  xxs ;4 4 4  xs ;4 4 4 4 5  xxs ;2 4 2 4 6  xxs ;1 5 1  x ;5 1 5 2 xx  ;5 3 x ;2 5 4  x ;6 1 x 6 2 x . 46 УСиМ, 2009, № 6 Рис. 2 Рис. 3 Т а б л и ц а 3 4x 5x 6x 0s 1s 2s 3s 4s 5s 6s 7s = 2s 000 0 0 0 0 0 0 0 0 001 0 0 0 0 0 0 1 0 010 0 0 1 1 1 1 1 1 011 0 0 1 1 0 0 1 1 100 0 0 0 0 0 0 0 0 101 0 1 1 0 0 0 1 1 110 0 0 1 1 0 1 1 1 111 0 0 1 1 0 0 1 1 ip 1p 1p , 3p 3p 2p 6p 3p , 4p , 5p 3p , 5p Ш а г 4. Сокращение числа вершин BDD. Процесс рассмотрения вершин осуществляется от листовых вершин вверх по дереву – к кор- невым вершинам, помеченным исходными функциями 1f , 2f , 3f . На рис. 3 показано, что разложение коэффициента (функции) 6s по переменной 4x дает два одинаковых коэффи- циента 2 , следовательно, переменная 4x несу- щественна для 6s и потому 6s = 2 . Переменная 6s исключается из многоуровневого представ- ления функций. Аналогично: 3s = 3 , 5s = 4 , пе- ременные 3s , 5s исключаются из многоуров- невого представления функций. Каждая различ- ная упорядоченная пара коэффициентов, исхо- дящих из вершины-переменной, задает неко- торый коэффициент. Например, пара < 2s , 1s > задает функцию 2, пара < 3s , 4s > – функцию 3 и т.д. На рис. 2 показано, что разложение коэффициента (функции) 1 по переменной 3x дает два одинаковых коэффициента 1s , следо- вательно, переменная 3x является несуществен- ной для 1, т.е. 1= 1s , и переменная 1 также исключается из многоуровневого представле- ния функций системы F. Пройдя вверх до кор- невых вершин и найдя одинаковые коэффици- енты, получаем результирующую BDD (рис. 1), которой соответствует результирующее много- уровневое представление функций системы: ;21 11 1  xxf ;4 1 3 1 2  xxf ;6 1 5 1 3  xxf ;2 22 1 1  xx ;3 2 2  x ;4 2 1 2 4  xsx ;3 2 5  x ;6 2 5 2 6  xx ;1 3 2 3 2 sxsx  ;4 3 3 3 3 sxsx  ;5 3 4 sx ;2 3 6 3 5 sxsx  ;2 3 6 sx ;1 4 1  xs ;2 4 3 4 2  xxs ;4 4 4  xs ;1 5 1  x ;5 1 5 2 xx  ;5 3 x ;2 5 4  x ;6 1 x 6 2 x . Алгоритм этапа 1 выбора перестановки аргументов Данный алгоритм состоит в последователь- ном применении следующих трех эвристик. Каждая эвристика применяется итерационно до тех пор, пока очередная итерация не даст уменьшения сложности BDD. Для каждой из рассматриваемых промежуточных перестано- вок подсчитывается сложность BDD. Эвристика 1 – «перестановка одного аргу- мента ix с правым соседом». Исходной являет- УСиМ, 2009, № 6 47 ся начальная перестановка < nxx ,...,1 >. Аргумен- ты nxx ,...,1 рассматриваются поочередно. Сна- чала аргумент 1x меняется позицией с правым аргументом 2x (осуществляется транспозиция элементов перестановки), затем 1x меняется позицией с правым соседом 3x и так далее, по- ка 1x не окажется на последнем месте. Среди пройденных выбирается лучшая перестановка (лучшей перестановке соответствует BDD меньшей сложности), она является начальной для последующего движения аргумента 2x , при этом 2x помещается на первую позицию и двигается путем перестановки с правым сосе- дом на последнюю позицию, опять выбирается лучшая перестановка, являющаяся начальной для движения аргумента 3x , и так далее, пока не выполнит аналогичное движение аргумент nx . Поочередное движение всех аргументов составляет одну итерацию применения эври- стики 1. Если итерация применения эвристи- ки 1 уменьшает сложность BDD, то выполня- ется следующая итерация. Если же итерация не приводит к уменьшению сложности BDD, то осуществляется переход к применению эв- ристики 2. Эвристика 2 – «попарная перестановка». Бе- рется лучшая перестановка Xbest., полученная в результате применения эвристики 1. Очеред- ная рассматриваемая перестановка отличается от предыдущей переменой мест только двух аргументов, пока не будет найдена новая луч- шая перестановка Xbest1. Если она найдена, то процесс попарной перестановки повторяется уже для новой лучшей перестановки Xbest1. Эври- стика 2 прекращает работу, если после рассмот- рения всех попарных перестановок нет умень- шения сложности BDD. Эвристика 3 – «оконная перестановка». Ис- ходной является лучшая перестановка Xbest2, по- лученная в результате применения эвристи- ки 2. «Окно» представляет собой четыре по- следовательно расположенных аргумента ,ix 1 2 3, ,i i ix x x    , внутри которого проводятся все перестановки четырех аргументов. Затем окно перемещается на один аргумент вправо – по- лучается новое окно   4321 ,,, iiii xxxx , внутри которого опять осуществляются все переста- новки. Сдвиг окна до последней позиции и пе- ребор внутри него всех перестановок свиде- тельствует об окончании одной итерации при- менения эвристики 3. Лучшая перестановка – начало для следующей итерации применения эвристики 3. Если итерация не приводит к уменьшению сложности BDD, то полученная в результате применения эвристики 3 перестановка резуль- тирующая для алгоритма этапа 1. Экспериментальные исследования Алгоритм построения BDD программно реа- лизован: программа OPT_BDD, реализующая ал- горитм, подвергнута обширному эксперимен- тальному исследованию. Эксперимент 1. Предлагаемый на этапе 1 ал- горитм поиска лучшей перестановки сравни- вался с алгоритмом случайного перебора пере- становок на потоке примеров систем F ДНФ – схемы программируемых логических матриц (ПЛМ) из библиотеки Berkeley PLA Test Set и четыре схемы (lal, ttt2, too_large, x1) многоуров- невой логики, преобразованные в ПЛМ. Резуль- таты эксперимента 1 приведены в табл. 4, где (и далее в других таблицах) используются сле- дующие обозначения: n – число переменных; m – число функций; k – число различных эле- ментарных конъюнкций, входящих в ДНФ всех функций системы F; SBDD – сложность BDD;  – число перебранных перестановок, знак + свидетельствует о полном переборе всех пере- становок; t – время в секундах построения BDD (процессор Pentium 4 с тактовой частотой 2,8 ГГц). Лучшие решения в табл. 4 (и других таблицах) выделены жирным шрифтом. Эксперимент 2. Сравнение предложенного алгоритма с алгоритмом из [6]. Результаты эксперимента 2 приведены в табл. 5. Экспери- ментальные данные (сложность BDD и время), характеризующие программу из [6] и приве- денные в табл. 5, взяты из статьи [6]. 48 УСиМ, 2009, № 6 Т а б л и ц а 4 Случайный перебор перестановок OPT_BDD Имя схемы n m k BDDS  t, с BDDS  t, с add6 12 7 1092 59 5000 276,12 45 907 52,09 b2 16 17 110 620 50000 24746,9 538 1227 177,07 b9 16 5 123 90 10000 1720,2 69 719 37,77 br1 12 8 34 83 15000 156,13 76 436 4,13 br2 12 8 35 73 5000 39,02 71 9763 44,33 dc2 8 7 58 59 40320+ 335,78 59 65 0,52 dist 8 5 255 144 40320+ 340,57 144 23 0,17 in0 15 11 135 378 5000 466,12 301 467 9,85 in2 19 10 137 299 5000 2761,23 231 4749 663,64 intb 15 7 664 809 1000 1269,74 629 757 240,29 t3 12 8 148 61 10000 142,21 54 187 1,95 tial 14 8 640 728 35000 36115,6 682 3912 1460,55 xparc 41 73 551 2762* 1000 8670,31 1927 2676 600,42 vtx1 27 6 110 230* 1000 1203,73 196 1256 118,11 x6dn 39 5 121 264* 1000 1468,71 238 1431 337,99 x9dn 27 7 120 260* 1000 1319,32 212 642 83,55 signet 39 8 124 2938* – – 1500 17945 3197,2 shift 19 16 100 57* 10000 1122,01 50 1067 12,84 soar 83 94 529 956* 1000 50737,84 560 9318 1700,2 * Улучшить начальную перестановку с помощью случайной пере- становки аргументов не удалось. Т а б л и ц а 5 Программа [6] Программа OPT_BDD Имя схемы n m k BDDS t, с BDDS t, с alu4 14 8 1028 747 21,65 735 20,06 apex2 39 3 1035 739 38,53 333 843,80 apex3 54 50 280 1129 87,23 997 83,37 e64 65 65 65 865 183,80 128 399,19 misex3 14 14 1848 523 22,88 581 142,62 table3 14 14 175 798 40,21 747 11,01 table5 17 15 158 689 28,15 708 8,98 Целью экспериментов 3–5 было сравнение эффективности применения оптимизации BDD, выступающей в качестве предварительного эта- па синтеза комбинационных схем, реализуе- мых в составе БМК. В каждом из этих экспериментов синтези- ровалась схема в базисе БМК. В качестве сис- темы синтеза использовалась система Leonardo [7]. Целевой библиотекой синтеза была выбра- на библиотека БМК [7, с. 159], состоящая из 35 элементов. Сложность схемы SБМК в библиоте- ке проектирования БМК (далее просто схемы БМК) подсчитывается как сумма площадей, входящих в данную схему элементов. В экспе- риментах 3–8 исходные примеры ПЛМ и оп- тимизированные представления BDD задава- лись на языке VHDL. Эксперимент 3. Синтез схем БМК по ис- ходным VHDL-описаниям схем ПЛМ. Эксперимент 4. Синтез схем БМК по опти- мизированным (с помощью случайного пере- бора перестановок) представлениям BDD. Эксперимент 5. Синтез схем БМК по опти- мизированным с помощью программы OPT_ BDD представлениям BDD. Результаты экспериментов 3–5 приведены в табл. 6. Т а б л и ц а 6 Экспери- мент 3. Синтез схем БМК по исход- ным ПЛМ Эксперимент 4. Синтез схем БМК по BDD, случайный пе- ребор переста- новок Экспери- мент 5. Синтез схем БМК по BDD, OPT_BDD Имя схемы n m k ÁÌÊS ÁÌÊS ÁÌÊS add6 12 7 1092 4935 167 137 addm4 9 8 480 3985 1379 846 b12 15 9 431 192 194 160 b2 16 17 110 2474 2825 1682 in0 15 11 135 2067 1411 1036 in2 19 10 137 1845 1120 711 m181 15 9 430 192 219 177 m3 8 16 128 1385 975 562 mlp4 8 8 225 2564 1069 674 tial 14 8 640 4505 4030 2389 z9sym 9 1 420 920 212 161 intb 15 7 664 5810 5810 2269 alu1 12 8 19 66 66 66 in1 16 17 110 2862 2468 1711 vtx1 27 6 110 175 314 349 x9dn 27 7 120 198 330 370 soar 83 94 529 1705 2228 2043 gary 15 11 442 1119 1287 1046 max1024 10 6 1024 4048 1255 1307 lal 26 19 117 280 448 298 ttt2 24 21 222 466 663 432 too_large 38 3 1027 5868 – 4415 x1 51 35 274 801 – 1245 Цель экспериментов 6–8 – сравнение эф- фективности применения оптимизации BDD, выступающей в качестве предварительного эта- па синтеза комбинационных схем, реализуемых в составе FPGA. В качестве целевой микросхемы FPGA вы- брана микросхема XC2s100 семейства SPAR- TAN2. Сложность (площадь) полученных ло- гических схем FPGA подсчитывалась в числе УСиМ, 2009, № 6 49 программируемых элементов LUT (Look Up Table), имеющих 4 входа. Эксперимент 6. Синтез схем FPGA по ис- ходным VHDL-описаниям схем ПЛМ. Эксперимент 7. Синтез схем FPGA по оп- тимизированным (с помощью случайного пе- ребора перестановок) представлениям BDD. Эксперимент 8. Синтез схем FPGA по оп- тимизированным с помощью программы OPT_ BDD представлениям BDD. Т а б л и ц а 7 Экспери- мент 6. Синтез схем БМК по исход- ным ПЛМ Экспери- мент 7. Синтез схем БМК по BDD, слу- чайный пе- ребор пере- становок Экспери- мент 8. Синтез схем БМК по BDD, OPT_BDD Имя схемы n m k LUT LUT LUT add6 12 7 1092 66 19 14 addm4 9 8 480 95 114 151 b12 15 9 431 25 24 23 b2 16 17 110 476 381 318 in0 15 11 135 141 141 195 in2 19 10 137 186 191 125 m181 15 9 430 25 25 26 m3 8 16 128 69 69 111 mlp4 8 8 225 68 76 123 tial 14 8 640 652 452 478 z9sym 9 1 420 76 18 19 intb 15 7 664 423 423 391 alu1 12 8 19 8 8 8 in1 16 17 110 392 468 297 vtx1 27 6 110 28 53 99 x9dn 27 7 120 31 53 90 soar 83 94 529 312 384 347 gary 15 11 442 197 263 191 max1024 10 6 1024 676 255 254 lal 26 19 117 53 81 55 ttt2 24 21 222 78 103 72 too_large 38 3 1027 1152 – 847 x1 51 35 274 146 – 213 Обсуждение результатов экспериментов Экспериментальные исследования показали, что предложенный алгоритм эффективен, конку- рентоспособен с известным алгоритмом и при- годен для практического использования. При- менение оптимизации многоуровневых пред- ставлений систем полностью определенных бу- левых функций с помощью BDD полезно (при- водит к сокращению сложностей схем) при син- тезе в базисе БМК. Однако применение BDD в качестве предварительного этапа оптимизации схем FPGA оказалось полезным только в поло- вине примеров схем. Случайный поиск пере- становок аргументов оказывается в общем слу- чае неэффективным (в сравнении с предложен- ным алгоритмом поиска порядка переменных разложения) как для оптимизации схем БМК, так и для оптимизации схем FPGA. Заключение. В статье описан алгоритм оп- тимизации многоуровневых представлений сис- тем полностью определенных булевых функ- ций и результаты экспериментального иссле- дования. Эксперименты показали достаточно высокую эффективность предложенного алго- ритма. Программа OPT_BDD, реализующая ал- горитм построения BDD, включена в систему Micel [8] схемной реализации параллельных алгоритмов логического управления. 1. Кузнецов О.П. О программной реализации логиче- ских функций и автоматов //Автоматика и телемеха- ника. – 1977. – № 7. – С. 63 – 74; № 9. – С. 138 – 149. 2. Akers S.B. Binary Decision Diagrams // IEEE Trans. on Computers. – 1978. – C–27, № 6. – P. 509–516. 3. Bryant R.E. Graph-based algorithms for boolean func- tions manipulation. // Ibid. – 1986. – C–35, № 8. – P. 677–691. 4. Bryant R.E., Meinel C. Ordered Binary Decision Dia- grams // Logic synthesis and verification (Ed. by S. Hassoun, T. Sasao, R.K. Brayton). Kluwer Acad. Publ., 2002. – P. 285–307. 5. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Found. and Appl. – Berlin, Heidelberg: Springer-Verlag, 1998. – 267 p. 6. Dynamic variable reordering for BDD minimization / E. Felt, G. York, R. Brayton et al. // Proc. EURO– DAC, 1993, 20–24 Sep. – P. 130–135. 7. Бибило П.Н. Синтез логических схем с использова- нием языка VHDL – М.: Солон–Р, 2002. – 384 с. 8. Программный комплекс Micel высокоуровневого и логического синтеза параллельных алгоритмов ло- гического управления / П.Н. Бибило, С.Н. Кардаш, Н.А. Кириенко и др. // УСиМ. – 2009. – № 5. – С. 81– 88. Поступила 30.04.2009 Тел. для справок: + 375 (17) 284-2084 (Минск) E-mail: bibilo@newman.bas-net.by © П.Н. Бибило, П.В. Леончик, 2009  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций

Institution

Ähnliche Einträge