Сборник трудов III международной научно практической конференции

225 
 
 
Допустим,  рассматривается  вопрос  формирования  системы  уравнений 
для  S-блока  (4x4).  В  соответствии  с  теоремой,  число  линейно  независимых 
уравнений для данного S-блока не меньше чем 21.      
Из формулы (1) следует, что всевозможные одночлены,  встречающиеся в 
этом  уравнении,  следующие:  x
4
,  x
3
,  x
2
,  x
1
,  y
4
,  y
3
,  y
2
,  y
1
,  x
4
x
3
,  x
4
x
2
,  x
4
x
1
,  x
4
y
4
,  x
4
y
3
, 
x
4
y
2
, x
4
y
1
, x
3
x
2
, x
3
x
1
, x
3
y
4
, x
3
y
3
, x
3
y
2
, x
3
y
1
, x
2
x
1
, x
2
y
4
, x
2
y
3
, x
2
y
2
, x
2
y
1
, x
1
y
4
, x
1
y
3
, x
1
y
2
, x
1
y
1
,
 
y
4
y
3
,  y
4
y
2
,  y
4
y
1
,  y
3
y
2
,  y
3
y
1,
  y
2
y
1
.  Из  этого  списка  видно,  что  существуют  26 
выходных  одночленов  (т.е.  y
i
,  y
i
y
j
,  x
i
y
j
),  которые  определяются  входящими 
значениями  S-блока (т.е.  x
4
,  x
3
,  x
2, 
x
1
).  Очевидно,  что  количество  уравнений  со 
степенью  deg≤2,  описывающих    любой  S-блок  (4x4),  не  больше  чем  26. 
Выражая все 26 выходных одночленов в виде булевых функций (т.е.: y
4
–f
1
, y
3
–f
2
, 
y
2
–f
3
, y
1
–f
4
, x
4
y
4
–f
5
, x
4
y
3
–f
6
, x
4
y
2
–f
7
, x
4
y
1
–f
8
, x
3
y
4
–f
9
, x
3
y
3
–f
10
, x
3
y
2
–f
11
, x
3
y
1
–f
12
, x
2
y
4
–f
13
, 
x
2
y
3
–f
14
, x
2
y
2
–f
15
, x
2
y
1
–f
16
, x
1
y
4
–f
17
, x
1
y
3
–f
18
, x
1
y
2
–f
19
, x
1
y
1
–f
20
,
 
y
4
y
3
–f
21
, y
4
y
2
–f
22
, y
4
y
1
–f
23
, 
y
3
y
2
–f
24
, y
3
y
1
–f
25
, y
2
y
1
–f
26
), можно составит уравнения (АНФ) для этих функций, с 
помощью  их  таблиц  истинности.  Для  всех  этих  уравнений  удовлетворяется 
условие  deg≤4.  Используя  эти  уравнения,  можно  сформировать  уравнения, 
удовлетворяющие условию deg≤2. 
Рассмотрим данное преобразование более подробно. 
Известно, что в составе уравнения со степенью deg=4, существует только 
один  одночлен  вида  “x
4
x
3
x
2
x
1
”.  В составе  уравнения со  степенью  deg=3,  могут 
существовать одночлены “x
4
x
3
x
2
”, “x
4
x
3
x
1
”, “x
4
x
2
x
1
” или “x
3
x
2
x
1
”. Допустим, для n 
(n>1)  уравнений  удовлетворяется  deg(f
1,2,…,n
)=4.  Выбрав  любое  одно  из  этих 
уравнений  (назовем  его  образующим),  осуществим  его  сложение  со  всеми 
остальными  по  модулю  два  (
⨁).  В  итоге  образуется  n-1  уравнений, 
удовлетворяющих deg≤3. 
Далее,  используя  комбинации  (f
i
⨁f
j
)  из  оставшихся  уравнений,  можно 
сформировать или выбрать четыре таких уравнений (следующие  образующие), 
в составе которых будут присутствовать по одному одночлену третей степени,  
которые будут отличаться друг от друга. При помощи образующих уравнений 

226 
 
 
третей степени можно сформировать уравнения, удовлетворяющие  deg≤2. Для 
этого, соответствующие оставшиеся уравнения (не образующие) складываются 
по модулю два с образующими, чем достигается сокращение одночленов третей 
степени.   
Следовательно, после этих двух этапов снижения степени уравнений для 
S-блока  (4х4)  можно  составить  по  меньшей  мере  21  линейно  независимое 
уравнение, удовлетворяющее deg≤2. 
Используя  предложенный  метод,  можно  сформировать  системы 
уравнений  с  минимальной  алгебраической  степенью  для  S-блоков 
произвольного размера. 
Ниже приведен пример формирования системы уравнений для S-блока. 
1-таблица. S-блок (4x4).  
X  0 
1 
2 
3  4 
5 
6  7  8 
9 
10  11  12  13  14  15 
Y  7  12  15  4  6  10  8  2  1  14 
3 
0 
11 
5 
9 
13 
2-таблица. Таблица истинности S- блока(4x4).  
Вход 
Вых
од 
f
5
  f
6
  f
7
  f
8
  f
9
  f
10
  f
11
  f
12
  f
13
  f
14
  f
15
  f
16
  f
17
  f
18
  f
19
  f
20
  f
21
  f
22
  f
23
  f
24
  f
25
  f
26
 
x
4
 
x
3
 
x
2
 
x
1
 
f
1
 
f
2
 
f
3
 
f
4
 
x
4
y
4
 
x
4
y
3
 
x
4
y
2
 
x
4
y
1
 
x
3
y
4
 
x
3
y
3
 
x
3
y
2
 
x
3
y
1
 
x
2
y
4
 
x
2
y
3
 
x
2
y
2
 
x
2
y
1
 
x
1
y
4
 
x
1
y
3
 
x
1
y
2
 
x
1
y
1
 
y
4
y
3
 
y
4
y
2
 
y
4
y
1
 
y
3
y
2
 
y
3
y
1
 
y
2
y
1
 
y
4
 
y
3
 
y
2
 
y
1
 
0 0 0 0 0 1 1 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
0 0 0 1 1 1 0 0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  0  1  0  0  0  0  0 
. . .   . . .  . . . 
1 1 1 0 1 0 0 1  1  1  0  1  1  0  0  1  1  0  0  1  0  0  0  0  0  0  1  0  0  0 
1 1 1 1 1 1 0 1  1  1  0  1  1  1  0  1  1  1  0  1  1  1  0  1  1  0  1  0  1  0 
Первоначально составленные уравнения: 
1.
 
f
1
: y
4

x
1

x
2

x
4
x
2

x
4
x
3

x
4
x
2
x
1
=0, 
2.
 
f
2
: y
3

x
3
x
1

x
3
x
2

x
3
x
2
x
1

x
4

x
4
x
1

x
4
x
2
x
1

x
4
x
3
x
1

x
4
x
3
x
2

1=0, 

227 
 
 
3.
 
f
3
: y
2

x
1

x
3
x
1

x
3
x
2

x
3
x
2
x
1

x
4

x
2
x
4

x
4
x
3

x
4
x
3
x
1

x
4
x
3
x
2

1=0, 
4.
 
f
4
: y
1

x
1

x
3

x
3
x
1

x
4
x
3

1=0, 
5.
 
f
5
: x
4
y
4

x
4
x
1

x
4
x
2
x
1

x
4
x
3
=0, 
6.
 
f
6
: x
4
y
3

x
4
x
1

x
4
x
2
x
1

x
4
x
3
x
2
x
1
=0, 
7.
 
f
7
: x
4
y
2

x
4
x
1

x
4
x
2

x
4
x
3

x
4
x
3
x
2
x
1
=0, 
8.
 
f
8
: x
4
y
1

x
4

x
4
x
1

x
4
x
3
x
1
=0, 
9.
 
f
9
: x
3
y
4

x
3
x
1

x
3
x
2

x
4
x
3

x
4
x
3
x
2

x
4
x
3
x
2
x
1
=0, 
10.
 
f
10
: x
3
y
3

x
3

x
3
x
1

x
3
x
2

x
3
x
2
x
1

x
4
x
3

x
4
x
3
x
2

x
4
x
3
x
2
x
1
=0, 
11.
 
f
11
: x
3
y
2

x
3

x
3
x
2

x
3
x
2
x
1

x
4
x
3
x
1
=0, 
12.
 
f
12
: x
3
y
1

x
4
x
3
=0, 
13.
 
f
13
: x
2
y
4

x
2

x
2
x
1

x
4
x
2

x
4
x
2
x
1

x
4
x
3
x
2
=0, 
14.
 
f
14
: x
2
y
3

x
2

x
3
x
2

x
4
x
2

x
4
x
3
x
2

x
4
x
3
x
2
x
1
=0, 
15.
 
f
15
: x
2
y
2

x
2

x
2
x
1

x
3
x
2

x
4
x
3
x
2
x
1
=0, 
16.
 
f
16
: x
2
y
1

x
2

x
2
x
1

x
3
x
2

x
3
x
2
x
1

x
4
x
3
x
2
=0, 
17.
 
f
17
: x
1
y
4

x
1

x
2
x
1

x
4
x
3
x
1
=0, 
18.
 
f
18
: x
1
y
3

x
1

x
3
x
1

x
4
x
2
x
1

x
4
x
3
x
1

x
4
x
3
x
2
x
1
=0, 
19.
 
f
19
: x
1
y
2

x
3
x
1

x
4
x
1

x
4
x
2
x
1

x
4
x
3
x
2
x
1
=0, 
20.
 
f
20
: x
1
y
1

x
4
x
3
x
1
=0, 
21.
 
f
21
: y
4
y
3

x
1

x
2

x
3
x
1

x
3
x
2

x
4
x
2

x
4
x
2
x
1

x
4
x
3
x
2
=0, 
22.
 
f
22
: y
4
y
2

x
2

x
2
x
1

x
3
x
1

x
3
x
2

x
4
x
1

x
4
x
2

x
4
x
3

x
4
x
3
x
1
=0, 
23.
 
f
23
: 
y
4
y
1

x
2

x
2
x
1

x
3
x
2

x
3
x
2
x
1

x
4
x
2

x
4
x
2
x
1

x
4
x
3

x
4
x
3
x
1

 
x
4
x
3
x
2
=0, 
24.
 
f
24
: y
3
y
2

x
1

x
3
x
2

x
3
x
2
x
1

x
4

x
4
x
2
x
1

x
4
x
3
x
1

x
4
x
3
x
2

1=0, 
25.
 
f
25
: y
3
y
1

x
1

x
3

x
3
x
1

x
4

x
4
x
1

x
4
x
3

1=0, 
26.
 
f
26
: y
2
y
1

x
1

x
3

x
3
x
1

x
4

x
4
x
1

x
4
x
2

x
4
x
2
x
1

1=0. 
После этапов снижения степени уравнений: 
Образующие уравнения: g
0
=f
6
; g
1
=f
1
; g
2
=f
8
; g
3
=f
1

f
13
; g
4
=f
8

f
11
. 
1. f
2

g
1

g
2

g
3

g
4
: y
3

x
2
y
4

x
3
y
2

x
3

x
2
x
1

x
2

x
4
x
2

x
3
x
1

x
4

x
4
x
1
 
    1=0, 


228 
 
 
2. f
3

g
2

g
3

g
4
: y
2

y
4

x
2
y
4

x
3
y
2

x
3

x
2
x
1

x
4

x
3
x
1

x
4
x
2

1=0, 
3. f
4
: y
1

x
1

x
3

x
3
x
1

x
4
x
3

1=0, 
4. f
5

g
1
: x
4
y
4

y
4

x
1

x
2

x
4
x
2

x
4
x
1
=0, 
5. f
7

g
0

g
1
: x
4
y
2

x
4
y
3

y
4

x
1

x
2
=0, 
6. f
9

g
0

g
1

g
3
: x
3
y
4

x
4
y
3

x
2
y
4

x
2
x
1

x
2

x
4
x
2

x
4
x
1

x
3
x
1

x
3
x
2
 
    x
4
x
3
=0, 
7. f
10

g
0

g
1

g
3

g
4
: x
3
y
3

x
4
y
3

x
2
y
4

x
4
y
1

x
3
y
2

x
4

x
2
x
1

x
2

x
4
x
2
   
    x
3
x
1

x
4
x
3
=0, 
8. f
12
: x
3
y
1

x
4
x
3
=0, 
9. f
14

g
0

g
1

g
3
: x
2
y
3

x
4
y
3

x
2
y
4

x
2
x
1

x
4
x
1

x
3
x
2
=0, 
10. f
15

g
0

g
1
: x
2
y
2

x
4
y
3

y
4

x
1

x
4
x
2

x
4
x
3

x
4
x
1

x
2
x
1

x
3
x
2
=0, 
11. 
f
16

g
3

g
4
: 
x
2
y

жүктеу/скачать 7,09 Mb.

Достарыңызбен бөлісу: