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



жүктеу 7.09 Mb.
Pdf просмотр
бет20/35
Дата25.12.2016
өлшемі7.09 Mb.
түріСборник
1   ...   16   17   18   19   20   21   22   23   ...   35

ТеоремаДля любого блока замены размером nxm бит: F(x
1
, …, x
n
)→(y
1

…,  y
m
),  и  для  любого  подмножества  T  из  t  всех  возможных  одночленов 
(2
n+m
),если  выполняется  условие  t>2
n
,  то  существует  по  меньшей  мере  t–2
n
 
линейно  независимых  уравнений,  содержащих  одночлены  из  множества  T  и 
выполняющиеся с вероятностью 1. 

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 


3  4 

6  7  8 

10  11  12  13  14  15 
Y  7  12  15  4  6  10  8  2  1  14 


11 


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


Поделитесь с Вашими друзьями:
1   ...   16   17   18   19   20   21   22   23   ...   35


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет