Полиномиальное соотношение для представления полной реакции одного класса двоичных 4D-модулярных динамических систем

Модулярные динамические системы (МДС) [1–5] являются одним из важных классов дискретных динамических систем (понятие модулярной динамической системы суть синоним – понятия конечные последовательностные машины, двоичные системы, последовательностные схемы и т.д. [6, 7]). Входные, выходные последовательности и последовательности состояния МДС принимают значения из конечного кольца или поля. Если конечное поле является полем GF ( p ) , тогда функция перехода и функция выхода МДС строится с помощью операции сложения и умножения по mod p ( p – простое число).

К настоящему времени исследованы однопараметрические и многопараметриче-

ские классы МДС [1–14]. Однопараметрические МДС находят широкое применение в различных областях (см. монография [3, 4, 6, 9, 15]). Многопараметрические МДС (короче nD -МДС, n >  2 ) суть системы с пространственной структурой и имеют более широкую возможность применения, чем однопараметрическая МДС. Однако к настоящему времени исследованы в основном линейные классы nD -МДС.

Для развития теории и приложения нелинейных МДС (НМДС) прежде всего необходимо найти формулу для их общего представления. К настоящему времени в работах [1, 6, 7, 9, 10, 14, 15] получены формулы в виде двухзначных аналогов полинома Вольтерры для представления одно- и двухпараметрических НМДС. А для нелинейных nD -МДС ( nD -НМДС), где n >  3 , формула общего представления получена лишь для одного класса 3D-НМДС [7].

Из-за отсутствия общей формулы представления классов nD -НМДС при n > 3 они в общем виде не исследовались. Представляют несомненный интерес исследования различных классов 3D - НМДС, 4D - НМДС и т.д.

В данной работе рассматривается вопрос аналитического представления полной реакции одного класса 4 D -НМДС, заданного входно-выходными соотношениями, в виде двухзначного аналога полинома Воль-терры и определения неизвестных коэффициентов этого полинома в случае известных входной и выходной последовательностей рассматриваемых систем.

1.    Постановка задачи

Рассмотрим МДС с фиксированной памятью n и ограниченной связью P = P х Р ₂ х р , которая задается формулой y [ n , c , c₂, c ₃ ] = G { u [ т , c + Pi, c₂ + p ₂, c ₃ + ⁺ P 3 ^]| ^{n - n} 0 <  ^T <  ⁿ , P a ^{e P} a ,              ⁽¹⁾

a = □}, GF (2).

Здесь n суть временной, c1, c2 и c3 соответственно 1-й, 2-й и 3-й клеточный аргумент [5] и n e {0,1,2,...}, ca e {...,-1,0,1,...}, a = 1,3 ; y[n,C1,c2,c3] e GF(2) и  u[n,C1,c2,c3] e e GF(2) являются выходной и входной последовательностями МДС соответственно Pa = {Pa (1),..., Pa (ra )},  Pa (1) < ... < Pa (ra ), pa(j) e {...,-1,0,1...}, j = 1,...,ra , кроме того, Pa (1) и Pa (ra) конечные целые числа, где через Pa (j) обозначен j -й элемент множества Pa (a = 1,3).

Можно записать функциональные соотношения (1) в более компактном виде. Для    этого    введем    обозначения c = (c1,c 2, c3) и P = (P1, P 2, P з), где Pa e р, a = 1,3. Тогда соотношение (1) можно записать в виде

У ^{[ n} , ^{c ]} =

= G { u [ т , c + p ]| n - n ₀<  т <  n , p e P },   (2)

GF (2).

Задача аналитического представления полной реакции 4D -МДС (1) или (2) со- стоит в представлении отображения G{...} в виде двухзначного аналога полинома Вольтерры и определении неизвестных коэффициентов этого полинома при известных входной и выходной последовательностей рассматриваемых систем.

• 2.    Полиномиальное соотношение для представления полной реакции 4D-MДC

Рассмотрим вопрос вывода полиномиального соотношения для представления полной реакции 4 D -МДС, заданной по формуле (2). Для этого через P ( j ) обозначим j -й элемент множества P . Число элементов множества P определяется выражением r = r • r₂ • r . Отображения G {...} можно записать в виде отображений, зависящих от ( n₀ + 1) • r аргументов:

G {...} =

= f ( u [ n - n 0 , c + P (1)], u [ n - n 0 , c + P (2)],...   (3)

• ..., u [ n - n ₀, c + P ( r )],..., u [ n , c + P ( r )]),

где f (...) суть модулярная функция над конечным полем Галуа GF (2). Ясно, что в каждой точке ( n , c ) модулярную функцию f можно представить в виде полинома над конечным полем GF (2) с помощью произведения элементов множества U в разных возможных комбинациях [16], где

U = { u [ n , c + p (1)],..., u [ n , c + p ( r )],..., u [ n - n ₀, c + + p (1)],..., u [ n - n 0 , c + p ( r )]}.

Во всевозможных комбинациях произведений элементов из U количество множителей, т.е. степеней нелинейности может быть от 0 до (n0 +1)r . Каждое такое произведение можно представить как элементарное произведение. Выберем произвольное i e{1,...,(n0 +1)r}  и рассмотрим те произведения элементов из (3) в разных комбинациях которых степень нелинейности равна i . Пусть в произвольно выбранном произведении для каждого a e {1,...,r} из множества  Ua = {u[n - ^, c + p(a)]|^ = 0,1,..., n0} участвуют множители количеством m , где a = 1,..., r.

Таким образом, должно удовлетворяться следующее соотношение: пусть m₁ + ... + m_r = i

Ф( i ) = { m = ( m 1 ,..., m r )| m _t e {0,..., n ₀ +1}, £ = 1, r , m +... + m_r = i },

Q ( i , m ) = { O ma есть компонента m и m _a ^ 0, a = 1, r }.

Ясно, что рассмотренное произведение со степенью нелинейности i в общем виде можно записать следующим образом:

∏ aeQ (i, m)

Фиксируем

Для

m _α

П u [ n - т ( а , П а ), c + P ( a )] .  ⁽⁶⁾

П а = ¹

i e {1,...,(n0 +1)r} и m e Ф(i) . всех  (a, в) e Q(i, m) введем обозначение

^Г 1 ⁽ m a ) = ^{{ T} a = ^{( т ( а ,1),} ... ^{, т ( а} , m a ⁾⁾⁰< ^ <  т ( а ,1) < ... <  т ( а ,m _a ) <  n₀ }.

Для всех a e Q(m, i)  образуем из векторов τ блочный вектор τ . Множе- ство всех блочных векторов (наборов) τ обозначим через Г(i, m) . Очевидно, что каждому Т er(i, m ) соответствует произведение вида (6) и

Г( i, m ) = X   Г1( ma), aeQ (i, m)

где знак Χ есть знак операции Декартового произведения множеств.

Используя обозначения (4), (5), (8) можем записать f (...) в виде:

^{( n} 0 ^{+ 1) r}

(7),

f (...) = K 0 + £ I I K .m, [ Т ] * i =1    m eФ( i ) r er( i , m )

x П  Пu[n -т(а,Па),c + P(a)],GF(2), aeQ(i,m) na =1

где K0, Ki,m [Т], Т <=Г(i, m), m eФ(i) i e {1,...,(n0 +1)r}, есть коэффициенты это- го полинома.

Таким образом, справедлива

Теорема 1. Пусть имеют место соотношения (4)–(5), (7), (8). Тогда полная реакция 4 D -МДС с фиксированной памятью n и ограниченной связью P , характеризующаяся соотношением (2), может быть представлена в виде следующего двузначного аналога полинома Вольтерры:

( ⁿ 0 + 1) r                          _

y[n,c] = K0 + I I I Ki,m[T]x i=1 m eФ (i) геГ( i,m)

mα x П Пu[n - Та Па),c + P(a)], GF(2). (9) aeQ(i,m) na =1

Теперь рассмотрим вопрос вывода полиномиального соотношения для представления полной реакции 4 D -МДС, заданной по формуле (1). В (1) отображения G{...} можно записать в виде отображений, зависящих от ( n ₀ + 1) • r аргументов:

G {...} = f ( u [ n - n 0 , c + P ! (1), c 2 + p 2 (1), c 3 +

+ P з (1)], u [ n - n 0 , c + P ! (1), c 2 + p 2 (1), c 3 +

+ p 3 (2)],..., u [ n - n 0 , c 1 + P 1 (1), c 2 + p 2 (1), c 3 +

+ P3 (r3 )],u[n - n0, c1 + P1 (1),c2 + P2(2),c3 +

+ p 3(1)],..., u [ n - n 0, c1 + P1(1), c 2 + P 2(2),     (10)

, c 3 + p 3 ( r , )],..., u [ n - n 0 , c + P 1 (1), c 2 +

⁺ P 2 ^{( r} 2 ), ^c 3 ⁺ P 3 ^{( r} 3 ^)], ... ^{, u [ n} , ^c 1 ⁺ P 1 ^{( r} 1 ), ^c 2 ⁺

⁺ P 2 ^{( r} 2 ), c 3 ⁺ P 3 ^{( r} 3 ^)]) .

Ясно, что в каждой точке ( n , c , c ₂, c ₃ ) модулярную функцию f можно представить в виде полинома над конечным полем GF (2) с помощью произведения элементов множества U в разных возможных комбинациях, где

U = {u [ n - n 0 , c 1 + p 1 (1), c 2 + p 2 (1), c 3 +

+ P 3 (1)], u [ n - n 0 , c 1 + p 1 (1), c 2 + p 2 (1), c 3 +

+ p 3 (2)],..., u [ n - n 0 , c 1 + P 1 (1), c 2 + p 2 (1), c 3 +

+ P 3 ( r 3 )], u [ n - n 0 , c 1 + p 1 (1), c 2 + p 2 (2), c 3 +

+ p 3 (1)],..., u [ n - n 0 , c 1 + P 1 (1), c 2 + p 2 (2), c 3 +

+ P 3 ( r 3 )],..., u [ n - n 0 , c 1 + P 1 (1), c 2 + p 2 ( r 2 ), c 3 +

⁺ P 3^{( r} з^)], ... ^{, u [ n} , ^c 1 ⁺ P 1^{( г} 1Х ^c 2 ⁺ P 2⁽ r z b ^c 3 ⁺ P 3^{( r} 3^)]} .

Во всевозможных комбинациях произведений элементов из U количество множителей, может быть от 0 до (n0 +1)r . Каждое такое произведение можно представить как элементарное произведение.       Выберем       произвольное i e{1,...,(n0 +1)r} и рассмотрим те произведения элементов из множества (11) в разных комбинациях, степень нелинейности которых равна i . Пусть в произвольно выбранном произведении для каждой пары (а, в, Y) из множества

^U a,в , Y = ^{ u ^[ n - ^ c 1 ⁺ P 1 ^{( a} ), c 2 ⁺ P 2 ^{( в )} c 3 ⁺

+ P 3(Y )# = 0,1,..., n 0} участвуют множители количеством m , где а = 1,..., r, в = 1,..., r2, y = 1,..., r .

Таким образом, должно удовлетво- rl    r2    r3

ряться равенство ∑∑∑ m = i .

a = 1 в = 1 Y = 1

Пусть

Ф(i) = {m = (тш,...,m,,r,mw-.,m^,r,- ri     r2     r3

...’ m l, Г 2 ,Г 3 ’...

,m rl, r2 - r3

) EEE m a =1 p =1 у =1

= i

ma, p, у G {О^.^ n о + 1}, a = 1,r 1, p = 1,r2, у = 1,r3 }, Q(i, m) = {(a, в, у)|m^p^ есть компонента m U ma,p,у * 0, a = 1,Г1, p = 1,Г2,у = 1,Г3}.

(13) Каждое произведение со степенью i в общем виде можно записать следующим образом:

m a , p , ,

П     П u [ n - T ( a , p , у , o^p ), c c +

( a , p , у ) e Q ( i , m ) o_a , p , _r = 1

⁺ P 1^{( a ), C} 2 ⁺ P 2^{( P ), C} 3 ⁺ P 3⁽ у ^)] .   ⁽¹⁴⁾

Фиксируем i e {1,...,( n₀ + 1) r } и m еФ ( i ) . Для всех ( a , p , у ) e Q ( i , m ) введем обозначение

^Г 1 ⁽ m a , p^ ) = ^{{ T} a , p , у = ^{( т ( a , P ,} Y ^,1), ...

..., T ( a , p , у , m a , p , _r ))|0 <  T ( a , p , у ,1)) < ... (15) .... <  ^{т ( a , p ,} у ^{, m} a , p^ ) <  n о ^} .

Для всех ( a , p , у ) e Q ( i , m ) из векторов т _ap_у образуем блочный вектор τ . Множество всех блочных векторов (наборов) τ обозначим через Г ( i , m ).

Очевидно, что

Г(i, m) = f JO( J1(ma,p,у )

( a , p , у ) e Q ( i , m )

и каждому т еГ ( i , m ) соответствует произведение вида (14).

Используя обозначения (12),(13),

(15), (16) можем записать f (...) в виде следующего полинома:

( n о +1) r_

f(...)=ко + ZEE Kim[т]x i=1    mеФ(i) теГ(i,m)

ma, p, у x п     п u[n - т(a, p, у, oa,p,у )A +

( ^a > ^p , У )^{e Q (} i >  m ) ^oa , p , у ^{= 1}

⁺ P 1 ^{( a ), C} 2 ⁺ P 2 ^{( P ), C} 3 ⁺ P 3 ⁽ у Л ^{GF (2)} .

Таким образом,

( ⁿ о ^{+ 1) r}                            _

y[ n, C1, C 2, C 3] = K о + E E E Ki, m [T]x i=1 m еФ (i) теГ( i, m)

ma, pу x П    П u[n - т(a, P, У, °a,p,у ), C1 +

( « ^{, P ,}Г ^{) e Q (} i ^, m ) ^oa , p , _r =

+ P 1 ( a ), c 2 + p 2 ( p ), c 3 + p 3 ( у )], GF (2). (17)

Полиномиальное представление (17) является общим представлением для 4 D -МДС (1). Однако путем упорядочения слагаемых из этого представления можно получить другое, которое удобно при решении задачи синтеза МДС [6, 7, 9, 10, 14]. Рассмотрим упорядочение представления (17).

Пусть i е {1,..., r ( n₀ + 1)} , m e Ф ( i ) и

A ⁽ m ) = ^{{ m} a,p ,_r\a = ^{1, r} 1 ^{, p} = ^{1, r} ₂ ^, у = ^{1, r} 3 ^} .

Множество A(m ) представляет собой трехмерный массив размерностью r × r × r . По (17) индексы α , β и γ соответствуют клеточным аргументам c , c и c . Рассмотрим трехмерное дискретное пространство. Пусть в этом пространстве выбрана прямоугольная система координат и ось абсцисс, ординат и аппликат суть оCj, оc2 и оc3 соответственно. Пусть точка с координатами (a, p, у), a = 1, r,   p = 1, r2, у = 1, r , отмечена числом ma p , a = 1, r, p = 1, r2, у = 1, r . Все эти точки суть геометрическое представление массива A (m ) в трехмерном пространстве.

Рассмотрим матрицы A_a ( m ) , Ap ( m ) и Ay ( m ) размерности соответственно r₂ x r ₃, r × r и r × r , где

A a ⁽ m ) = ⁽ m ap , у ^{), p} = ^{1, r} 2^, у = ¹

A p ⁽ m ) = ⁽ m a , p , у ^{), a} = ^{1, r} 1^, 7 = ^{1 r} 3 ;

A у ⁽ m ) = ⁽ m app , у ^{), a} = ^{1, r} 1^{, p} = ^{1 r} 2 .

Все элементы каждой матрицы A_a ( m ) , Ap ( m ) и Ay ( m ) в отдельности образуют слой в массиве A ( m ) ( a = 1, r 1 , p = 1, r ₂ , у = 1, r j.

Отметим, что слои Aa (m ), Ap (m) и Ay (m) параллельны плоскостям c2 оc3, Cj оc3 и Cj о c2 соответственно. Если в каком-то слое все точки отмечены нулем, то этот слой следует называть нулевым слоем. Ясно, что в зависимости от m е Ф(i) для некоторых а , в и γ некоторые из соответствующих слоев Aa (m ), Ap (m) и Л., (m) могут быть нулевые. Удалим все нулевые слои массива Л (m ), которые параллельны хотя бы одной из плоскостей с2 0c3, q 0c3, q 0c2 и построим массив B(m ) . Обозначим размерность массива  B (m)  через  £ ^ m ) х

£₂ ( m ) х £₃ ( m ) . Ясно, что размерность массива B ( m ) не превышает размерности массива Л ( m ), т.е. £ j( m ) <  r ,   £ ₂( m ) <  r ,

£ ₃( m ) <  r₃ . Таким образом, для всех элементов m множества Ф ( i ) построим соответствующий массив B ( m ).

Из элементов множества Ф ( i ) построим специальные подмножества следующим образом: 1) любой элемент из множества Ф ( i ) входит только и только в одно специальное подмножество; 2) если для элементов m и m₂ из множества Ф ( i ), соответствующие им массивы B ( m ) и B ( m₂ ) , совпадают, тогда оба элемента входят в одно и то же специальное подмножество. Обозначим через λ количество специальных подмножеств множества Ф ( i ) . i -е специальное подмножество обозначим через Ф₁ ( i , i ). Ясно, что

Ф , ( i , j ) п ФЛ i , £ ) = 0 , j * £ ; λ i

U Ф/ i , j ) = Ф ( i ). j = 1

Рассмотрим какое-либо подмножество Ф1(i, i)  множества  Ф(i) . Пусть этому подмножеству соответствует массив B размерностью £ j х £ 2 х £ 3:

B = ( m' a , в , Y ), а = 1, £ 1 , в = 1, £ 2 , Y = 1, £ 3 - Тогда элементы множества Ф₁ ( i , i ) можно представить в следующем виде:

m j a ,а , , P y = m a , в ,Г ,

а = 1Л, в = 1Л, Г = 1Л,

m a , в Г = ⁰ ’ ^{а £ {}Л,-, ^j £, ^} ’ ^в £ { ^ 1 ^, •.. ^, а£_г ^} , Г £ { P 1 ^, ... ^, Р £₃ }■

Ясно, что каждой тройке ( j , а , р ) соответствует элемент из множества Ф₁ ( i , i ) . Здесь ^j = ⁽ Jv", ^j £, ) , ^а = ( ^а 1 >-> ^а £₂ ) и ^P = ⁽ P 1 ’-’ P^ ) являются наборами соответственно в L_} (£₃) , L 2 ^{( £} 2 ) и ^L 3^{( £} 3 ) , где

L 1 ^{( £} 1 ) = ^{( jv; ^j ^l¹ <  ^j 1 <  ••• <  ^j £ 1 <  ^r 1 ^},

^L 2 ^{( £} 2 ) = {( ^a 1 .■■■. ^a 1 ₂)1 <  ^а 1 < -^{, a} 1 ₂ <  r 2 ^}’   ⁽¹⁸⁾

^L 3 ^{( £} 2 ) = ^{( P 1 ’-’ P ^¹ <  P 1 < - <  P t ₃ <  r 2 ^}- Введем следующее обозначение:

F(i) = {(£ 1,£ 2,£ 3, m)| m = (m1,1,1 ’■■■’ m1,1A ’ m1,2,1r", m1,2,l3 ,......, m1,l2,13 ’■”’m£1,£2Л )’

£ £ £ m ., , , = ^£ m aer «0..... n 0 + 1}.

a = 1 в = 1 Г = 1                                                          (19)

a = й, в = й7, г = 1Л;

( V a е {1,--., £ 1 })( 3 в е {1,---, £ ₂})( 3 г е {1,---, £ 3 }) ^

^ ( m a , в , Г * ⁰⁾’

( V , е {1,---, £ ₂})( 3 a е {1,---, £ JX3 г е {1,---, £ 3 }) ^

^ ( m a , в , Г * ⁰⁾’

(V г е {1.■■■. £ 3 })(E a е {1,-, £ Л)(Е в е {1.■■■. £ 3 }) ^

^ ⁽ m a, , Г * ^{0);   £} а ^е {¹’-’ r a ^}’ ^a = ^1,3}

Q 0 ( i , £ 1 , £ ₂, £ 3, m ) =

= {( a , в , Г )| m_ap _г есть компонента m и ⁽²⁰⁾ m a , в , Г * 0, a = й, в = 1Л Г = 1Х}■

Каждому  (£ j, £ 2, £ 3, m ) е F(i)  соответствует подмножество множества Ф(i) . Пусть m = (m1.1.1’■■■’ m1,1,£3, m1,2,1,-", m1,2,£3,---, m £1,£2,£3),

T = (Т1,1,1,---,Т1,1,£3,Т1,2,1,---,Т1,2,£3,---,Т £1,£2,£3),

L (£) = L (£) х L2 (£2) х L (£3).(23)

При     ^T a, , Г ^еГ 1 ⁽ m a , , , Г ) , ^a = 1, ^£ 1 ’     ^в = 1’ ^£ 2 ’

Г = 1, £ 3 , где ( a , в , Г ) е Q₀(i , £ 1 , £ ₂, £ ₃, m ), множество всех блочных векторов (наборов) τ обозначим через Г ( £ , £₂ , £₃ , m ) .

Очевидно, что каждой четверке <  j , a , P,T >  соответствует произведение вида

П       П u ^{[ n} -^{T ( a}’ ^в ’ Г ’ ^ a , в , Г )’ c 1 ⁺

^{( a , e} ’ Г ^{) е} Q 0⁽ i ^{, £} 1^{, £} 2^{, £} 3 ’ m ) £ a , в , Г = 1

+ Р1 (ja )’ c 2 + Р 2(ав )’ c 3 + Р 3 (Pr )]’ т еЩ!,£ 2, £ 3, m), j e L1(£1), a e L г(£ 2), p e L3(£3)-

Таким образом, справедлива теорема:

Теорема 2. Пусть имеют место соотношения (18)–(23). Тогда полная реакция 4D -МДС с фиксированной памятью n0 и ограниченной связью P = P × P × P , ха- рактеризующаяся соотношением (1), может быть представлена в виде следующего двухзначного аналога полинома Вольтерры:

(n 0+i) r y [ n, Cj, c 2, c 3] = h 0 + £     £ i =1  (£,,£ 2/3, m )e F (i)

£      _   £        h i, £ i , £ 2 , £ 3 ,m^{[ j}, ^a , P , ^{T ] x}

( j a , P ) e L ( £ )   т еГ ( £ 1 , £ 2 , £ з , m )

x      П       П u[n — т(a в, £’ ^a,вY ), a,в,r)eQo(i,£1,£2,£з,m) ia,в,, =1

, ^C 1 ⁺ P 1^{( j} a ), ^C 2 ⁺ P 2^{( а} в ), c 3 ⁺ P 3⁽ P ^)] , ^{GF (2)} -

• 3. Определение неизвестных коэффициентов полиномиальных представлений

Пусть при заданных значениях входной последовательности u [ n — т , c + p ], 0 <  т <  n ₀, p e P известны значения выходной последовательности y [ n , c ].

Рассмотрим вопрос определения коэффициентов Ko, K -[f ] в полиноме (9) для всех     т е Г(i, m),     m e Ф(i), i е{1,...,(n0 +1)r} в соответствии с известными входной и выходной последовательностями. Введем следующее обозначение:

x ( a , т ) = u [ n — т, c + p ( a )], т = 0, n ₀, a = 1, r , (25) с помощью которого получим

• У ^[ n , ^{c ]} =

= f ( x (1,0),..., x (1, n 0 ),..., x ( r ,0),..., x ( r , n 0 )).

K 0 = f (0,...,0,...,0,...,0).        (26)

Положим

X = { x( а , т ) \т = 0,..., n ₀; a = 1,..., r }.  (27)

Пусть x ( a , r ) является единственной переменной из множества X , принимающей значение 1, а остальные переменные из X принимают значения 0, где т e {0,..., n ₀}, a e { 1,..., r } .

В этом случае обозначим значение функции f (...) через f (x(a,r) = 1) . Учи- тывая значения переменных множества X , из (9) получаем

K 1,_аа) [(( т ))] = K 0 + f ( x ( a , т ) = 1), GF (2) , (28) где через (1_a) обозначен элемент m e Ф (1), в котором m_a = 1, а остальные компоненты этого элемента суть 0.

Пусть     x(a ,т(v, i)) = 1, i = 1, £ v , v = 1,0, где 0 < r,   £v < n0 +1, т(v,i) e e {0,...,n0}, av e {1,...,r}, а остальные переменные из X принимают значения 0. При этом через f (x (av ,т(v, i))) = 1^ = 1X, v = 10) обозначено значение функции f (...) .

Пусть

S = £ + ... + £,.              (29)

Построим полином, образованный из элементов множества D , где

D = { x a , т ( v , i ))) = 1 i = 1Л, v = 1, 0 } . Ясно, что этот полином имеет степень, равную числу S .

Пусть n e {0,..., S } . Рассмотрим произведения элементов из множества D в различных комбинациях, степень нелинейности которых равна η . Пусть в произвольно выбранном произведении для каждых v e {1,..., 0 } из множества

{ x ( a v , т ( у , i ))) = 1 ^ = 1, 7 ; , } участвуют множители, число которых суть β . Тогда: в + ... + в = П •

Пусть

£ = ( £ 1 ,..., £ 0 ),

F ( n , 0 , £ ) = {( b , в , P )1 <  b <  0 , в = ( в_й ,-, в р ),

• ¹    <  ^в P _a <  ^£ p _a , ^v = ¹ b , ^P = ⁽ P 1 ^,...^, P b ) ^e Nb ^{( 0 )}, в р 1 + ... + в р b = П },

N b ( 0 ) = { P = ( P 1 ,-, P b )1 <  P 1 <  ••• <  P b <  0 } , (30) b

Я b,в , p С) = X я в^ ( ^£ P v ), v = 1 где

^Я в рv ( ^£ P v ) =

= ^{ П = ^{( n} v , 1 ^, ... ^{, П} в l ¹ <  ⁿ v 1 1 <  ... < ^П в <  ^£ P ^} . ,                   ,' Pv                     ,                           ,' Pv               v

Тогда полином, образованный из элементов множества D , можно записать в виде

f (x (a Tv £))) = 1^ = 1, £ V, v = 1,0) =

S

=K.+EX .

n =1    ^{( b} . ^e . P >  F ^{n , £} )

E    K n ,( в ,.^ ) [ ^{(( r (} P 1 ^,(31)

,v rep, , , ^pb’ ep (£)

^{, f (} P 1 ^{, п} 1, e ⁾⁾ ,..., ^{T (} P b ^{, n} b ,1 T,^TP b , ⁿ b , e_pb ^{)))] x} b

ХП П X(aP. ’T(Pv, nv,£ B, GF(2), v=i ^pv =i где через (в ,...,в ) обозначен элемент m е Ф(п), в которой шг  = в , £ = 1,b,

σρξ     σρξ а остальные компоненты этого элемента суть 0.

Ясно, что в правой части формулы (31) слагаемое со степенью S имеет коэф- K u X^ t uv (1, тгг т..ж i_в )))]

Поэтому, учитывая, что x ( a , f ( v , £ )) = 1 , £ = 1, £_v , V = 1, в , из формулы (31) полу-

К_зд    ДОг (1,1),..., г (1, £ ₁)),...,( г ( 0 ,1),„., г ( 0 , 1 в )))] =

=f(x (a,r(v,£))) =

= £ =1д, v =1 0 )+ к о +

5-1

+∑∑ n =1     (b, в, P )е F(n ,в ,£)

_ E    ^K n ,( в   ,..., А , ) [(( ^г (А,^дХ-’ Г С ^P 1 , ^п 1, в , )),

ПеП be, P (О

••• ^{, T} P b , ⁿ b Jv, ^{T (} P b , ⁿ b , A_n ^)))] , GF ⁽²⁾ .

Таким образом, справедлива

Лемма 1. Пусть x( a_v , r ( v , £ )) = 1 , £ = 1, £ v , v = 1, 0 , где 0 <  r ,     4 <  n о + 1,

r(v, £) е{о,...,nо},      av е {1,...,r},      а остальные переменные из X принимают значения 0. При этом через f (x (av ,r(v, £))) = 1£ = 1Д, v = 10) обозначено значение функции f (...).

Пусть имеет место (29), (30). Тогда справедлива формула (32).

Формулы (28), (32) основываются на обозначении (25). Эти формулы можно привести к виду, в котором обозначения (25) не используются. Ясно, что формулу (28) можно записать в виде

^K 1,(1 . ) [(( г ))] = ^K о +

+ f ( u [ n - t, c + p( a )] = 1), GF (2).

Формулу (32) можно записать в виде

K_s«_t ,...,£, ) [(( г (1,1)^ t (1, £ ₁)),...,( г ( 0 ,1),..., г ( 0 , £ в ))] =

= f ( u [ n - T ( v , £ ), c + p (a )] = 1 £ = 1, £ v , v = 1, 0 ) +

5 -1              ______

+K о+E X n=1 (b, в, P >F(n,0,£)

E    ^K n ( в , ,..., p_a ) ^{[(( t (} P i , ^П 1,Д ... Т ⁽ P i , ^п 1 а »,

Пе^.^ -( £ )         ^{P 1       P b}

• b , в , p'

..Т ГP b , ⁿ bi iT TP b , ⁿ b, a. ^)))], ^{GF (2)}.   ⁽³⁴⁾

,                            ^{,r P} b

Для установления общей формулы определения любых коэффициентов в полиноме (9) рассмотрим коэффициент K_i -[ f ], где f еГ ( i , m ) , m е Ф ( i ) и i е {2,...,( n _о + 1) r } .

Пусть:

• 1 ' . m е Ф ( i ) , где i = 2, ( n_Q + 1) r ;

• 2 ‘ . Ненулевые элементы набора m есть m _a , где a е Q ( i , m ) = { a ₁,..., a₀ } и 0 <  r ;

• 3 ' . Множества   Г ( m_a ) , v = 1, 0 , есть

следующие множества

^Г 1^{( m} . ) = ^{{ f} v = ^{( г}О Д..., Ф, ^m a ^))о < ^{г ( v ,1)} <  ...

... <  ^{T ( v} , ^m . ) <  n о^} ;

• ⁴ ' . ^£ v = ^m a_v , ^v = ^{1, 0} ;

• 5 ' . u [ n - t ( v , £ ), c + p .v )] = 1 , £ = 1, £ v , v = 1, 0 , а остальные переменные из множества U принимают значения 0 и в этом случае через f ( u [ n - t ( v , £ ), c + p ( a v )] = 1 £ = 1, £ v , v = 1, 0 ) обозначено значение функции f (...) .

При выполнения условия 1 ^о - 5 ^о ясно, что m = ( £ j,..., £ ₀) = ( m_a ,..., m_a$ ) и множества Г ( i , m ) содержат следующий единственный