СИНТЕЗ МНОГОУРОВНЕВЫХ СТРУКТУР СО МНОГИМИ ВЫХОДАМИ

Abstract

В работе рассматривается метод решения задачи адаптации логической сети со многими выходами с восстановлением входного множества двоичных векторов при заданных только младших значениях этих векторов и значениях на выходах сети. Алгоритм синтеза логической сети основан на описании ее полиномом Жегалкина. Ил.: 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.

-

− − где D = E \ D – дополнение множества D в множестве E.

Во многих задачах классификации актуальной является задача восстановления информации по ее части, поскольку в процессе трансмиссии сигналы могут искажаться [4, 5]. Такая задача состоит в том, чтобы по известной (не искаженной) части входных сигналов и известным выходным значениям Структура такой сети для n = 5 , h = 2 на основе ЛЭ показана на рис. 1.

e5

L41

L32 e4

L23 L31 y2

L22 e3

y1 L13

L12 e2 L21

L11

e1 Рис. 1. Сеть с сотовой структурой связи 2. Общая постановка задачи

Дана группа только младших (старших) разрядов входных векторов обучающей выборки D ⊆ E , т. е. ( e = (eμ , eμ −1,..., e1) ), где μ < n . Аналогично, если задана группа только старших разрядов или любая группа подряд идущих символов.

Необходимо для заданной структуры сети с h выходами, значения которых известны, и множества входных векторов e ∈ D синтезировать логическую сеть и восстановить полноразрядное входное множество векторов. 2.1. Решение первой задачи

Рассмотрим логическую сеть с одним выходом и обучающей выборкой D с тремя входами (рис. 2). Как будет видно из метода синтеза, такие значения не ограничивают общности рассмотрения.

L12 e2 L21

L11 e3

e1 Рис. 2. Логическая сеть с тремя входами Сеть синтезируется с помощью полинома Жегалкина в виде:

P f ( 3 ) = a 0 + a 1 e1 + a 2 e 2 + a 3 e1 e 2 + a 4 e 3 + a 5 e1 e 3 + a 6 e 2 e 3 + a 7 e1 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 ⊕ 0a4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1, ⎪ ⎪1a0 ⊕ 0a1 ⊕1a2 ⊕ 0a3 ⊕ 0a4 ⊕ 0a5 ⊕ 0a6 ⊕ 0a7 = 1, ⎪⎪1a0 ⊕1a1 ⊕ 0a2 ⊕ 0a3 ⊕1a4 ⊕1a5 ⊕ 0a 6⊕ 0a 7 = 1, S = ⎨⎪1a0 ⊕ 0a1 ⊕1a2 ⊕ 0a3 ⊕1a4 ⊕ 0a5 ⊕1a6 ⊕ 0a7 = 1,   ⎪1a0 ⊕1a1 ⊕1a2 ⊕1a3 ⊕1a4 ⊕1a5 ⊕1`a6 ⊕1a7 = 0, ⎪⎪ . . . . . . = 0, ⎪ . . . . . . = 0, ⎪⎩ . . . . . . = 0.

      ( 1 ) Решая данную систему TSS-методом [6,7], находим единственное решение x1 = ( 1,1,0,0,1,0,1,0 ) , которому соответствует полином Жегалкина:

P f ( 3 ) = 1 ⊕ e1 ⊕ e3 ⊕ e3 e2 = e1 ⊕ e 2e 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, S = ⎨⎪1a0 ⊕ 0a1 ⊕ 1a2 ⊕ 0a3 ⊕ 1a4 ⊕ 0a5 ⊕ 1a6 ⊕ 0a7 = 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 ) = e1 ⊕ e 2e 3⊕ e4 , а выборка, на которой он будет принимать значение 1 имеет вид:

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 )} . Синтез выполняем волновым методом. e1 ⊕ e2e3 .

2. Волновым методом получаем подсеть для первого и второго выхода: а обучающая выборка, на которой значения будут 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. Волновым методом получаем подсеть и для трех выходов и пяти входов:

e1 ⊕ e2e3 ⊕ e4 , e1 ⊕ e2e3 ⊕ e4 ⊕ e5 .

L22 e3

L12 e2 L31

L21

L11 e1 e5

L41

L32 e4 Рис. 3. Структура сети ( n = 5, h = 3 ) Однако эта функция будет давать на третьем выходе 0, а нам нужна 1. Для этого преобразуется к виду: 1 ⊕ e1 ⊕ e2e3 ⊕ e4 ⊕ e5 = e1 ⊕ e2e3 ⊕ e4 ⊕ e5 = e1⊕ e2e3 ⊕ 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 входах: 2) Строим волновым методом функции подсети и получаем обучающую выборку:

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) Строим волновым методом и для выхода третьего: и получаем выборку, на которой обеспечиваются требуемые значения:

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. Аналогично получаем и для третьего выхода:

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 выходами, вне зависимости от того, часть каких разрядов обучающей выборки определена в постановке задачи (младшие или старшие).

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 .

H-index: Google Scholar - 5 ; Scopus - 1.

http://orcid.org/0000-0002-5175-9522.

H-index: Google Scholar - 15 ; Scopus - 4.

http://orcid.org/0000-0065-0736-4579.