=Paper=
{{Paper
|id=Vol-1631/32-37
|storemode=property
|title=Synthesis of multilevel structures with multiple outputs
|pdfUrl=https://ceur-ws.org/Vol-1631/32-37.pdf
|volume=Vol-1631
|authors=Vladimir Opanasenko,Sergyi Kryvyi
|dblpUrl=https://dblp.org/rec/conf/ukrprog/OpanasenkoK16
}}
==Synthesis of multilevel structures with multiple outputs==
https://ceur-ws.org/Vol-1631/32-37.pdf
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
УДК: 004.272
СИНТЕЗ МНОГОУРОВНЕВЫХ СТРУКТУР
СО МНОГИМИ ВЫХОДАМИ
В.Н. Опанасенко, С.Л. Крывый
В работе рассматривается метод решения задачи адаптации логической сети со многими выходами с восстановлением входного
множества двоичных векторов при заданных только младших значениях этих векторов и значениях на выходах сети. Алгоритм
синтеза логической сети основан на описании ее полиномом Жегалкина. Ил.: 3. Библиогр.: 7 назв.
Ключевые слова: адаптация, булева функция, полином Жегалкина.
В роботі розглядається метод розв’язання задачі адаптації логікової мережі з багатьма виходами з відновленням вхідної множини
двійкових векторів при заданих тільки молодших значеннях цих векторів і значень на виходах мережі. Алгоритм синтезу логікової
мережі грунтується на зображенні її поліномом Жегалкіна. Іл.: 3. Бібліогр.: 7 назв.
Ключеві слова: адаптація, булева функція, поліном Жегалкіна.
The method for solution of adaptation problem of the logical network with many outputs for the restoration of the input set of binary vectors
when given only the lower values of this set and the values of the outputs is considered. The algorithm synthesis of the logical network is
based on the description of its polynomial Zhegalkin. Fig.: 3. Ref. 7 titles.
Key words: Adaptation, Boolean functions, polynomial Zhegalkin.
1. Необходимые сведения и определения
В работах [1–3] рассмотрены вопросы адаптации логических сетей с одним выходом на основе
треугольной матрицы, которые реализуют разбиение множества входных двоичных векторов
e = (en ,..., e2 , e1 ) ∈ E в виде двоичных векторов на два подмножества на основе заданной обучающей
выборки D ⊆ E . При этом считается, что значение выхода Y логической сети определяется следующим
образом:
⎧⎪1, если e ∈ D;
Y =⎨
⎪⎩0, если e ∈ D,
где D = E \ D – дополнение множества D в множестве E.
Во многих задачах классификации актуальной является задача восстановления информации по
ее части, поскольку в процессе трансмиссии сигналы могут искажаться [4, 5]. Такая задача состоит в том,
чтобы по известной (не искаженной) части входных сигналов и известным выходным значениям
Y = ( yl ,... y 2 , y1 ) восстановить входную выборку D, которая обеспечивает заданные значения выходных
сигналов.
В данной работе рассматривается метод решения двух задач. Первая задача состоит в синтезе
логической сети по входной выборке с одним выходом, а вторая – в синтезе логической сети с
восстановлением входной выборки по ее известной части, обеспечивающей заданные выходные значения
сети со многими выходами.
Структура связей синтезируемой логической сети является сотовой, а ее архитектура определяется
следующими параметрами:
− логическая сеть со многими выходами;
− D ⊆ E – обучающая выборка или ее неискаженная часть, где e = (em ,..., e2 , e1 ) ∈ D – двоичные
векторы;
− h – выходная размерность сети (разрядность выходных двоичных векторов y = ( y h ,..., y1 ) ∈ Y ), где
значения yi i = 1,2,..., h , заданы (в частности, h может быть равно 1).
Синтез логической сети выполняется с помощью представления ее логических элементов в виде
полинома Жегалкина. Посредством выбранной структуры сети реализуется отображение ℜ: D → Y . Выходами
сети является двоичный вектор y ∈ Y . Логическая сеть с сотовой структурой связи на основе универсальных
логических элементов (ЛЭ) Li , j характеризуется следующими параметрами:
− количество уровней m определяется величиной m = n − h ;
− количество ЛЭ на j –ом уровне сети определяется величиной N j = (n − j ) . Общее число ЛЭ в сети
равно N = ( n + h − 1 ) ( n − h ) / 2 .
32
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Структура такой сети для n = 5 , h = 2 на основе ЛЭ показана на рис. 1.
y2 y1
L23 L13
L32 L22 L12
L41 L31 L21 L11
e5 e4 e3 e2 e1
Рис. 1. Сеть с сотовой структурой связи
2. Общая постановка задачи
Дана группа только младших (старших) разрядов входных векторов обучающей выборки D ⊆ E , т. е.
( e = (eμ , eμ −1 ,..., e1 ) ), где μ < n . Аналогично, если задана группа только старших разрядов или любая группа
подряд идущих символов.
Необходимо для заданной структуры сети с h выходами, значения которых известны, и множества
входных векторов e ∈ D синтезировать логическую сеть и восстановить полноразрядное входное множество
векторов.
2.1. Решение первой задачи
Рассмотрим логическую сеть с одним выходом и обучающей выборкой D с тремя входами (рис. 2).
Как будет видно из метода синтеза, такие значения не ограничивают общности рассмотрения.
L12
L21 L11
e3 e2 e1
Рис. 2. Логическая сеть с тремя входами
33
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Сеть синтезируется с помощью полинома Жегалкина в виде:
P f ( 3) = a 0 + a 1 e 1 + a 2 e 2 + a 3 e 1 e 2 + a 4 e 3 + a 5 e 1 e 3 + a 6 e 2 e 3 + a 7 e 1 e 2 e 3
с заданием обучающей выборки D = {(0,0,0), (0,1,0), (1,0,1), (1,1,0)} .
Исходя из условия (1), на элементах из D полином P f (3) должен принимать значение 1, а на элементах
из дополнения D = {(1,0,0), (0,0,1), (0,1,1), (1,1,1)} его значения должны быть равны 0. Тогда по выборке D
получаем систему (1) линейных неоднородных диофантовых уравнений (СЛНДУ) в поле вычетов F2 по
модулю 2, из которой необходимо найти значения коэффициентов ai , ∀i = 0,1,...,7 .
⎧1a0 ⊕ 0a1 ⊕ 0a2 ⊕ 0a3 ⊕ 0a 4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1,
⎪
⎪1a0 ⊕ 0a1 ⊕ 1a 2 ⊕ 0a3 ⊕ 0a4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1,
⎪1a0 ⊕ 1a1 ⊕ 0a 2 ⊕ 0a3 ⊕ 1a 4 ⊕ 1a5 ⊕ 0a 6 ⊕ 0a 7 = 1,
⎪
⎪1a ⊕ 0a1 ⊕ 1a 2 ⊕ 0a3 ⊕ 1a 4 ⊕ 0a5 ⊕ 1a6 ⊕ 0a7 = 1,
S =⎨ 0 (1)
⎪1a0 ⊕ 1a1 ⊕ 1a2 ⊕ 1a3 ⊕ 1a4 ⊕ 1a5 ⊕ 1`a6 ⊕ 1a7 = 0,
⎪ . . . . . . = 0,
⎪
⎪ . . . . . . = 0,
⎪ . . . . . . = 0.
⎩
Решая данную систему TSS-методом [6,7], находим единственное решение x1 = (1,1,0,0,1,0,1,0) , которому
соответствует полином Жегалкина:
P f (3) = 1 ⊕ e 1 ⊕ e3 ⊕ e3 e2 = e 1 ⊕ e 2 e 3 .
Если выборка D меняется, например, D = {(0,0,0), (0,1,0), (0,0,1)} , то матрица системы (2) не меняется, а
меняются только свободные члены:
⎧1a0 ⊕ 0a1 ⊕ 0a2 ⊕ 0a3 ⊕ 0a4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1,
⎪
⎪1a0 ⊕ 0a1 ⊕ 1a2 ⊕ 0a3 ⊕ 0a4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1,
⎪1a0 ⊕ 1a1 ⊕ 0a2 ⊕ 0a3 ⊕ 0a4 ⊕ 0a5 ⊕ 0a 6 ⊕ 0a 7 = 1,
⎪
⎪1a ⊕ 0a1 ⊕ 1a2 ⊕ 0a3 ⊕ 1a4 ⊕ 0a5 ⊕ 1a6 ⊕ 0a7 = 0,
S =⎨ 0
⎪1a0 ⊕ 1a1 ⊕ 1a2 ⊕ 1a3 ⊕ 1a4 ⊕ 1a5 ⊕ 1`a6 ⊕ 1a7 = 0,
⎪ . . . . . . = 0,
⎪
⎪ . . . . . . = 0,
⎪ . . . . . . = 0.
⎩
Эта система имеет единственное решение x1 = (1,0,0,1,1,0,0,1) , которому соответствует полином
Жегалкина:
P f (3) = 1 ⊕ e1e2 ⊕ e3 (1 ⊕ e1e2 ) = e3 (e1 ∨ e2 ) .
Если выборки D и D меняются местами, т.е. обучающей выборкой становится выборка D1 , то
полином Жегалкина принимает вид принимает вид P 1f (3) = 1 ⊕ Pf (3) .
Рассмотренное решение некоторым образом является определяющим в том смысле, что при добавлении
новой входной переменной система позволяет без вычислений определить новые функции в уздах.
Действительно, если рассматривать сеть с четырьмя входами с той же выборкой для трех переменных, то
полином будет иметь вид:
P f ( 4) = e 1 ⊕ e 2 e 3⊕ e4 ,
а выборка, на которой он будет принимать значение 1 имеет вид:
34
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
D1 = (0 × D) ∨ (1 × D) = {(0,0,0,0), (0,0,1,0), (0,1,0,1), (0,1,1,0), (1,1,0,0), (1,0,0,1), (1,0,1,1), (1,1,1,1)} .
Это обстоятельство позволяет решить общую задачу синтеза логической сети вышеописанным методом,
который был назван волновым методом [3].
2.2. Синтез логической сети по обучающей выборке и нескольким выходам
Пусть задана сеть с сотовой структурой связи (рис. 3), на выходах которой заданы значения 1,0,1 и
обучающая выборка которой имеет вид на первых трех выходах: D13 = {(0,0,0), (0,1,0), (1,0,1), (1,1,0)} .
Синтез выполняем волновым методом.
1. По выборке D13 синтезируем подсеть на первых трех входах. Логические элементы имеют вид
e 1 ⊕ e2 e3 .
2. Волновым методом получаем подсеть для первого и второго выхода:
e 1 ⊕ e2 e3 ⊕ e4 ,
а обучающая выборка, на которой значения будут 0 и 1 соответственно:
D14 = {(0,0,0,0), (0,0,1,0), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,1,0,0), (1,1,1,1), (1,0,1,1)} .
3. Волновым методом получаем подсеть и для трех выходов и пяти входов:
e 1 ⊕ e2 e3 ⊕ e4 ⊕ e5 .
L32 L22 L12
L41 L31 L21 L11
e5 e4 e3 e2 e1
Рис. 3. Структура сети ( n = 5, h = 3 )
Однако эта функция будет давать на третьем выходе 0, а нам нужна 1. Для этого преобразуется к виду:
1 ⊕ e 1 ⊕ e2 e3 ⊕ e4 ⊕ e5 = e 1 ⊕ e2 e3 ⊕ e4 ⊕ e5 = e 1⊕ e2 e3 ⊕ e4 ⊕ e5 ,
а выборка, на которой будут обеспечены выходы 1, 0, 1 , будет такой:
D15 = {(1,0,0,0,0), (1,0,0,1,0), (1,0,1,0,1), (1,0,1,1,0), (1,1,0,0,1), (1,1,0,1,1), (1,1,1,0,0), (1,1,1,1,1),
(0,0,0,0,1), (0,0,0,1,1), (0,1,1,1,0), (0,1,0,0,0), (0,0,1,0,0), (0,1,1,0,1), (0,1,0,1,0)} .
1. Рассмотрим случай той же сети, но выходные значения будут 0, 1, 0 и обучающая выборка
D23 = {(0, 0, 0), (0,1, 0), (1, 0,1), (1,1, 0)} для e2 , e3 , e4 . Поступаем также, как и в предыдущем случае:
1) Синтезируем функцию подсети на e2 , e3 , e4 входах:
35
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
e2 ⊕ e3 e4 ;
2) Строим волновым методом функции подсети
e2 ⊕ e3e4 ⊕ e1
и получаем обучающую выборку:
D14 = {(0,0,0,0), (0,1,0,0), (1,0,1,0), (1,1,0,0), (0,0,1,1), (1,0,0,1), (1,1,1,1), (0,1,1,1)} ;
3) Строим волновым методом и для выхода третьего:
e2 ⊕ e3e4 ⊕ e1 ⊕ e5
и получаем выборку, на которой обеспечиваются требуемые значения:
D15 = {(0,0,0,0,0), (0,0,1,0,10, (0,1,0,1,0), (0,1,1,0,0), (0,0,0,1,1), (0,1,0,0,1), (0,1,1,1,1), (0,0,1,1,1)} ∨ 1 × D14 ,
где D14 – дополнение до D14 .
2. Рассмотрим случай той же сети с теми же выходами, что и в предыдущем случае, но выборка
D23 = {(0,0,0), (0,1,0)} . Тогда получаем функцию e2 e4 , а обучающая выборка имеет вид:
D14 = {(0,0,0,0), (0,1,0,0), (1,0,1,1), (1,1,0,1), (0,0,1,1), (1,0,0,1), (1,1,1,1), (0,1,1,1)} для e2 e4 ⊕ e1 .
3. Аналогично получаем и для третьего выхода:
e2 e4 ⊕ e1 ⊕ e5 .
D15 = {(0,0,0,0,0), (0,0,1,0,0), (0,1,0,1,1), (0,1,1,0,1), (0,1,0,0,1), (0,0,0,1,1), (0,1,1,1,1), (0,0,1,1,1),
(1,1,0,0,0), (1,0,0,1,0)(1,0,1,0,1), (1,1,1,0,0), (1,0,1,1,0), (1,1,0,1,0), (1,1,1,1,0)} .
Выводы
Предложен метод решения задачи синтеза адаптивных структур со многими выходами,
представленных многоуровневыми логическими схемами, описанных логической сетью с сотовой
структурой связи в виде ациклического графа, вершинами которого являются универсальные логические
элементы. Синтез таких структур состоит в определении общей логической функции для каждого из
выходов сети и восстановлении неизвестной (или искаженной) части двоичных разрядов заданной
обучающей выборки, что позволяет использовать эту структуру для задачи восстановления искаженной
информации. В отличие от известных методов синтеза многоуровневых логических схем в данной работе
предложен подход к синтезу таких схем путем описания булевой сети на основе алгоритма решения СЛНДУ
в поле вычетов по модулю 2. Этот метод обобщен для структур общего вида с n входами и h выходами, вне
зависимости от того, часть каких разрядов обучающей выборки определена в постановке задачи (младшие
или старшие).
1. Palagin A.V., Opanasenko V.N. Reconfigurable computing technology // Journal Cybernetics and Systems Analysis. – 2007. – 43 (5). –
P. 675–686.
2. Opanasenko V.N., Kryvyi S.L. Partitioning the full range of boolean functions based on the threshold and threshold relation // Cybernetics and
Systems Analysis. Springer New York. – 2012. – Vol. 48, N.3. – P. 459–468.
3. Opanasenko V.N., Kryvyi S.L. Synthesis of Adaptive Logical Networks on the Basis of Zhegalkin Polynomials // Cybernetics and Systems
Analysis. Springer New York. – November 2015. – Vol. 51, 6. – P. 969–977.
4. Palagin A., Opanasenko V., Kryvyi S. The structure of FPGA-based cyclic-code converters // Journal Optical Memory & Neural Networks
(Information Optics). – 2013. – 22 (4). – P. 207–216.
5. Palagin A.V., Opanasenko V.N. Design and application of the PLD-based reconfigurable devices // In: Design of Digital Systems and Devices,
Springer, Verlag, Berlin, Heidelberg. – 2011. – Vol. 79. – P. 59–91.
6. Kryvyi S.L. Algorithms for solving systems of linear Diophantine equations in integer domains // Journal Cybernetics and Systems Analysis. –
2006. – 42 (2). – P. 163–175.
7. Kryvyi S.L. Algorithms for solving systems of linear Diophantine equations in residue fields // Journal Cybernetics and Systems Analysis. – 2007.
– 43 (2). – P. 171–178.
36
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
References
1. Palagin A.V., Opanasenko V.N. Reconfigurable computing technology // Journal Cybernetics and Systems Analysis. – 2007. – 43 (5). –
P. 675–686.
2. Opanasenko V.N., Kryvyi S.L. Partitioning the full range of boolean functions based on the threshold and threshold relation // Cybernetics and
Systems Analysis. Springer New York. – 2012. – Vol. 48, N.3. – P. 459–468.
3. Opanasenko V.N., Kryvyi S.L. Synthesis of Adaptive Logical Networks on the Basis of Zhegalkin Polynomials // Cybernetics and Systems
Analysis. Springer New York. – November 2015. – Vol. 51, 6. – P. 969–977.
4. Palagin A., Opanasenko V., Kryvyi S. The structure of FPGA-based cyclic-code converters // Journal Optical Memory & Neural Networks
(Information Optics). – 2013. – 22 (4). – P. 207–216.
5. Palagin A.V., Opanasenko V.N. Design and application of the PLD-based reconfigurable devices // In: Design of Digital Systems and Devices,
Springer, Verlag, Berlin, Heidelberg. – 2011. – Vol. 79. – P. 59–91.
6. Kryvyi S.L. Algorithms for solving systems of linear Diophantine equations in integer domains // Journal Cybernetics and Systems Analysis. –
2006. – 42 (2). – P. 163–175.
7. Kryvyi S.L. Algorithms for solving systems of linear Diophantine equations in residue fields // Journal Cybernetics and Systems Analysis. –
2007. – 43 (2). – P. 171–178.
Об авторах:
Опанасенко Владимир Николаевич,
доктор технических наук, профессор, ведущий научный сотрудник.
Количество научных публикаций в украинских изданиях – 100.
Количество научных публикаций в иностранных изданиях – 15.
H-index: Google Scholar – 5; Scopus – 1.
http://orcid.org/0000-0002-5175-9522.
Крывый Сергей Лукьянович,
доктор физико-математических наук, профессор.
Количество научных публикаций в украинских изданиях – 206.
Количество научных публикаций в иностранных изданиях – 43.
H-index: Google Scholar – 15; Scopus – 4.
http://orcid.org/0000-0065-0736-4579.
Место работы авторов:
Институт кибернетики имени В.М. Глушкова НАН Украины.
03187, г. Киев, проспект Академика Глушкова, 40.
Тел.: (044) 526 2598.
Киевский национальный университет имени Т.Г. Шевченко.
03680, г. Киев, проспект Академика Глушкова, 4.
Тел.: (044) 259 0511.
E-mail: opanasenko@incyb.kiev.ua, krivoi@i.com.ua.
37