Synthesis multilevel structure with multiple output
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 descr...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/178 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-178 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/27/e8016a8f0309c8c215489d87f3042b27.pdf |
| spelling |
pp_isofts_kiev_ua-article-1782024-04-28T13:09:56Z Synthesis multilevel structure with multiple output Синтез многоуровневых структур со многими выходами Синтез багаторівневих структур з багатьма виходами Opanasenko, V.M. Kryvyi, S.L. Adaptation; Boolean functions; polynomial Zhegalkin UDC 004.272 адаптация; булева функция; полином Жегалкина УДК: 004.272 адаптація; булева функція; поліном Жегалкіна УДК 004.272 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. Problems in programming 2016; 2-3: 48-62 В работе рассматривается метод решения задачи адаптации логической сети со многими выходами с восстановлением входного множества двоичных векторов при заданных только младших значениях этих векторов и значениях на выходах сети. Алгоритм синтеза логической сети основан на описании ее полиномом Жегалкина. Problems in programming 2016; 2-3: 48-62 В роботі розглядається метод розв’язання задачі адаптації логікової мережі з багатьма виходами з відновленням вхідної множини двійкових векторів при заданих тільки молодших значеннях цих векторів і значень на виходах мережі. Алгоритм синтезу логікової мережі грунтується на зображенні її поліномом Жегалкіна. Problems in programming 2016; 2-3: 48-62 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-07-06 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/178 10.15407/pp2016.02-03.048 PROBLEMS IN PROGRAMMING; No 2-3 (2016); 48-62 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2016); 48-62 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2016); 48-62 1727-4907 10.15407/pp2016.02-03 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/178/173 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T13:09:56Z |
| collection |
OJS |
| language |
Russian |
| topic |
Adaptation Boolean functions polynomial Zhegalkin UDC 004.272 |
| spellingShingle |
Adaptation Boolean functions polynomial Zhegalkin UDC 004.272 Opanasenko, V.M. Kryvyi, S.L. Synthesis multilevel structure with multiple output |
| topic_facet |
Adaptation Boolean functions polynomial Zhegalkin UDC 004.272 адаптация булева функция полином Жегалкина УДК: 004.272 адаптація булева функція поліном Жегалкіна УДК 004.272 |
| format |
Article |
| author |
Opanasenko, V.M. Kryvyi, S.L. |
| author_facet |
Opanasenko, V.M. Kryvyi, S.L. |
| author_sort |
Opanasenko, V.M. |
| title |
Synthesis multilevel structure with multiple output |
| title_short |
Synthesis multilevel structure with multiple output |
| title_full |
Synthesis multilevel structure with multiple output |
| title_fullStr |
Synthesis multilevel structure with multiple output |
| title_full_unstemmed |
Synthesis multilevel structure with multiple output |
| title_sort |
synthesis multilevel structure with multiple output |
| title_alt |
Синтез многоуровневых структур со многими выходами Синтез багаторівневих структур з багатьма виходами |
| description |
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. Problems in programming 2016; 2-3: 48-62 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/178 |
| work_keys_str_mv |
AT opanasenkovm synthesismultilevelstructurewithmultipleoutput AT kryvyisl synthesismultilevelstructurewithmultipleoutput AT opanasenkovm sintezmnogourovnevyhstruktursomnogimivyhodami AT kryvyisl sintezmnogourovnevyhstruktursomnogimivyhodami AT opanasenkovm sintezbagatorívnevihstrukturzbagatʹmavihodami AT kryvyisl sintezbagatorívnevihstrukturzbagatʹmavihodami |
| first_indexed |
2025-07-17T10:04:32Z |
| last_indexed |
2025-07-17T10:04:32Z |
| _version_ |
1850412672985595904 |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Н. Опанасенко, С.Л. Крывый, 2016
32 ISSN 1727-4907. Проблеми програмування. 2016. № 2–3. Спеціальний випуск
УДК: 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] рассмотрены вопросы адаптации логических сетей с одним выходом на основе
треугольной матрицы, которые реализуют разбиение множества входных двоичных векторов
Eeeee n ),,...,( 12 в виде двоичных векторов на два подмножества на основе заданной обучающей
выборки ED . При этом считается, что значение выхода Y логической сети определяется следующим
образом:
,если,0
;если,1
De
De
Y
где DED \ – дополнение множества D в множестве E.
Во многих задачах классификации актуальной является задача восстановления информации по
ее части, поскольку в процессе трансмиссии сигналы могут искажаться [4, 5]. Такая задача состоит в том,
чтобы по известной (не искаженной) части входных сигналов и известным выходным значениям
),,...( 12 yyyY l восстановить входную выборку D, которая обеспечивает заданные значения выходных
сигналов.
В данной работе рассматривается метод решения двух задач. Первая задача состоит в синтезе
логической сети по входной выборке с одним выходом, а вторая – в синтезе логической сети с
восстановлением входной выборки по ее известной части, обеспечивающей заданные выходные значения
сети со многими выходами.
Структура связей синтезируемой логической сети является сотовой, а ее архитектура определяется
следующими параметрами:
логическая сеть со многими выходами;
ED – обучающая выборка или ее неискаженная часть, где Deeee m ),,...,( 12 – двоичные
векторы;
h – выходная размерность сети (разрядность выходных двоичных векторов Yyyy h ),...,( 1 ), где
значения iy hi ,...,2,1 , заданы (в частности, h может быть равно 1).
Синтез логической сети выполняется с помощью представления ее логических элементов в виде
полинома Жегалкина. Посредством выбранной структуры сети реализуется отображение YD: . Выходами
сети является двоичный вектор Yy . Логическая сеть с сотовой структурой связи на основе универсальных
логических элементов (ЛЭ) jiL , характеризуется следующими параметрами:
количество уровней m определяется величиной hnm ;
количество ЛЭ на j –ом уровне сети определяется величиной )( jnN j . Общее число ЛЭ в сети
равно 2/)()1( hnhnN .
Теоретичні та методологічні основи програмування
33
Структура такой сети для 5n , 2h на основе ЛЭ показана на рис. 1.
Рис. 1. Сеть с сотовой структурой связи
2. Общая постановка задачи
Дана группа только младших (старших) разрядов входных векторов обучающей выборки ED , т. е.
( ),...,,( 11 eeee ), где n . Аналогично, если задана группа только старших разрядов или любая группа
подряд идущих символов.
Необходимо для заданной структуры сети с h выходами, значения которых известны, и множества
входных векторов De синтезировать логическую сеть и восстановить полноразрядное входное множество
векторов.
2.1. Решение первой задачи
Рассмотрим логическую сеть с одним выходом и обучающей выборкой D с тремя входами (рис. 2).
Как будет видно из метода синтеза, такие значения не ограничивают общности рассмотрения.
Рис. 2. Логическая сеть с тремя входами
13L
12L22L
11L21L31L
1
e
2
e
3
e5
e
32L
41L
23L
4
e
1y
2y
12L
11L21L
1
e
2
e
3
e
Теоретичні та методологічні основи програмування
34
Сеть синтезируется с помощью полинома Жегалкина в виде:
32173263153421322110)3( eeeaeeaeeaeaeeaeaeaaP f
с заданием обучающей выборки )}0,1,1(),1,0,1(),0,1,0(),0,0,0{(D .
Исходя из условия (1), на элементах из D полином )3(fP должен принимать значение 1, а на элементах
из дополнения )}1,1,1(),1,1,0(),1,0,0(),0,0,1{(D его значения должны быть равны 0. Тогда по выборке D
получаем систему (1) линейных неоднородных диофантовых уравнений (СЛНДУ) в поле вычетов 2F по
модулю 2, из которой необходимо найти значения коэффициентов 7,...,1,0, iai .
.0......
,0......
,0......
,011̀111111
,101010101
,100110011
,100000101
,100000001
76543210
76543210
76543210
76543210
76543210
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
S (1)
Решая данную систему TSS-методом [6,7], находим единственное решение )0,1,0,1,0,0,1,1(1 x , которому
соответствует полином Жегалкина:
3212331)3( 1 eeeeeeeP f .
Если выборка D меняется, например, )}1,0,0(),0,1,0(),0,0,0{(D , то матрица системы (2) не меняется, а
меняются только свободные члены:
.0......
,0......
,0......
,011̀111111
,001010101
,100000011
,100000101
,100000001
76543210
76543210
76543210
76543210
76543210
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
S
Эта система имеет единственное решение )1,0,0,1,1,0,0,1(1 x , которому соответствует полином
Жегалкина:
)()1(1 21321321)3( eeeeeeeeP f .
Если выборки D и D меняются местами, т.е. обучающей выборкой становится выборка 1D , то
полином Жегалкина принимает вид принимает вид )3(
1
)3( 1 ff PP .
Рассмотренное решение некоторым образом является определяющим в том смысле, что при добавлении
новой входной переменной система позволяет без вычислений определить новые функции в уздах.
Действительно, если рассматривать сеть с четырьмя входами с той же выборкой для трех переменных, то
полином будет иметь вид:
4321)4( eeeeP f ,
а выборка, на которой он будет принимать значение 1 имеет вид:
Теоретичні та методологічні основи програмування
35
)}1,1,1,1(),1,1,0,1(),1,0,0,1(),0,0,1,1(),0,1,1,0(),1,0,1,0(),0,1,0,0(),0,0,0,0{()1()0(1 DDD .
Это обстоятельство позволяет решить общую задачу синтеза логической сети вышеописанным методом,
который был назван волновым методом [3].
2.2. Синтез логической сети по обучающей выборке и нескольким выходам
Пусть задана сеть с сотовой структурой связи (рис. 3), на выходах которой заданы значения 1,0,1 и
обучающая выборка которой имеет вид на первых трех выходах: )}0,1,1(),1,0,1(),0,1,0(),0,0,0{(3
1 D .
Синтез выполняем волновым методом.
1. По выборке 3
1D синтезируем подсеть на первых трех входах. Логические элементы имеют вид
321 eee .
2. Волновым методом получаем подсеть для первого и второго выхода:
4321 eeee ,
а обучающая выборка, на которой значения будут 0 и 1 соответственно:
)}1,1,0,1(),1,1,1,1(),0,0,1,1(),1,0,0,1(),0,1,1,0(),1,0,1,0(),0,1,0,0(),0,0,0,0{(4
1 D .
3. Волновым методом получаем подсеть и для трех выходов и пяти входов:
54321 eeeee .
Рис. 3. Структура сети ( 3,5 hn )
Однако эта функция будет давать на третьем выходе 0, а нам нужна 1. Для этого преобразуется к виду:
5432154321543211 eeeeeeeeeeeeeee ,
а выборка, на которой будут обеспечены выходы 1,0,1 , будет такой:
),1,1,1,1,1(),0,0,1,1,1(),1,1,0,1,1(),1,0,0,1,1(),0,1,1,0,1(),1,0,1,0,1(),0,1,0,0,1(),0,0,0,0,1{(5
1 D
)}0,1,0,1,0(),1,0,1,1,0(),0,0,1,0,0(),0,0,0,1,0(),0,1,1,1,0(),1,1,0,0,0(),1,0,0,0,0( .
1. Рассмотрим случай той же сети, но выходные значения будут 0,1,0 и обучающая выборка
)}0,1,1(),1,0,1(),0,1,0(),0,0,0{(3
2 D для 432 ,, eee . Поступаем также, как и в предыдущем случае:
1) Синтезируем функцию подсети на 432 ,, eee входах:
12L22L
11L21L31L
1
e
2
e
3
e5
e
32L
41L
4
e
11 0
Теоретичні та методологічні основи програмування
36
432 eee ;
2) Строим волновым методом функции подсети
1432 eeee
и получаем обучающую выборку:
)}1,1,1,0(),1,1,1,1(),1,0,0,1(),1,1,0,0(),0,0,1,1(),0,1,0,1(),0,0,1,0(),0,0,0,0{(4
1 D ;
3) Строим волновым методом и для выхода третьего:
51432 eeeee
и получаем выборку, на которой обеспечиваются требуемые значения:
4
1
5
1 1)}1,1,1,0,0(),1,1,1,1,0(),1,0,0,1,0(),1,1,0,0,0(),0,0,1,1,0(),0,1,0,1,0(,10,0,1,0,0(),0,0,0,0,0{( DD ,
где
4
1D – дополнение до 4
1D .
2. Рассмотрим случай той же сети с теми же выходами, что и в предыдущем случае, но выборка
)}0,1,0(),0,0,0{(3
2 D . Тогда получаем функцию 42ee , а обучающая выборка имеет вид:
)}1,1,1,0(),1,1,1,1(),1,0,0,1(),1,1,0,0(),1,0,1,1(),1,1,0,1(),0,0,1,0(),0,0,0,0{(4
1 D для 142 eee .
3. Аналогично получаем и для третьего выхода:
5142 eeee .
),1,1,1,0,0(),1,1,1,1,0(),1,1,0,0,0(),1,0,0,1,0(),1,0,1,1,0(),1,1,0,1,0(),0,0,1,0,0(),0,0,0,0,0{(5
1 D
)}0,1,1,1,1(),0,1,0,1,1(),0,1,1,0,1(),0,0,1,1,1(),1,0,1,0,1)(0,1,0,0,1(),0,0,0,1,1( .
Выводы
Предложен метод решения задачи синтеза адаптивных структур со многими выходами,
представленных многоуровневыми логическими схемами, описанных логической сетью с сотовой
структурой связи в виде ациклического графа, вершинами которого являются универсальные логические
элементы. Синтез таких структур состоит в определении общей логической функции для каждого из
выходов сети и восстановлении неизвестной (или искаженной) части двоичных разрядов заданной
обучающей выборки, что позволяет использовать эту структуру для задачи восстановления искаженной
информации. В отличие от известных методов синтеза многоуровневых логических схем в данной работе
предложен подход к синтезу таких схем путем описания булевой сети на основе алгоритма решения СЛНДУ
в поле вычетов по модулю 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.
http://www.springerlink.com/content/g423k622109l/?p=2735992f16994e289bbc2f590fd8bdff&pi=0
http://www.springerlink.com/content/g423k622109l/?p=2735992f16994e289bbc2f590fd8bdff&pi=0
Теоретичні та методологічні основи програмування
37
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.
http://www.springerlink.com/content/g423k622109l/?p=2735992f16994e289bbc2f590fd8bdff&pi=0
http://www.springerlink.com/content/g423k622109l/?p=2735992f16994e289bbc2f590fd8bdff&pi=0
mailto:opanasenko@incyb.kiev.ua
|