Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Кольцо многочленов Жегалкина

Читайте также:
  1. Гривы и головы придворных коней покрыты пушистыми страусовымиперьями; кольцо из серебряных колокольчиков вокруг их шеи.
  2. По замыслу великого магистра обладание кольцом связывало его владельца с Вевельсбургом на астральном уровне
  3. Поршневое кольцо
  4. Потерянное кольцо
  5. Что заставило Сталина в последний момент резко изменить свое отношение к Кольцову до сих пор не ясно.

Здесь необходимо за­метить, что система булевых функций, определяющих кольцевые операции (поскольку полиномы Жегалкина образуют коммутативное кольцо с единицей), может определяться по-разному в зависимости от нужд практики. Это достаточно тонкий вопрос, поэтому мы рассмотрим только одноразрядные булевы функции. Обычно на практике используется сложение по модулю 2 (DES, LUCIFER, FEAL, IDEA), поэтому в качестве операции сложения можно использовать сложение по модулю 2 или его инверсию, а в качестве умножения - операцию “И”. Покажем, что других функций, определяющих кольцо, нет (булеву функцию от двух аргументов можно рассматривать как оператор). Полная система одноразрядных булевых функций от двух переменных Y = f(X,Z) имеет вид

Таблица 2.1

X Z f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
                                   
                                   
                                   
                                   

 

Естественно, что операции сложения и умножения не должны быть констан­тами. Результат сложения должен зависеть как от X, так и от Z и удовлетворять не­равенствам f(X,1) ¹ f(X,0), f(1,Z) ¹ f(0,Z), так как в противном случае сложение не будет являться групповой операцией. Этим требованиям удовлетворяет только сложение по модулю 2 и его инверсия. Операция умножения определяется одно­значно по нулевому элементу. Варианты кольцевых операций приведены в таблице.

Таблица 2.2

Сложение Умножение Нуль Единица Примечание
f7 f2     Коммут. кольцо
f10 f8     Коммут. кольцо

 

Очевидно, что эти две системы кольцевых операций определяют изоморфные кольца. Изоморфизм имеет вид (X,Z)® . Поэтому достаточно рассмотреть только полиномы Жегалкина. Полиномы Жегалкина образуют коммутативное кольцо A с единицей 1. Все элементы кольца являются идемпотентными, f2 = f для всех fÎ A. Это кольцо не является целостным, так как из условия f2+f = 0 следует, что f(f+1)=0, то есть каждый отличный от константы элемент кольца является де­лителем нуля.

Рассмотрим нелинейные свойства взаимно однозначных преобразований n‑разрядных блоков. Определим максимальный порядок нелинейности как макси­мальное число сомножителей в каком-либо из слагаемых многочлена Жегалкина, представляющих данное преобразование. Например, группа аффинных операторов имеет порядок нелинейности 1 (то есть не имеет нелинейных слагаемых).

Предложение 2.1. Подстановка n-разрядных слов имеет максималь­ный порядок нелинейности не выше n-1.

Предложение 2.2. При любой поляризации многочленов Жегалкина максимальный порядок нелинейности преобразования не меняется.

 

Дата добавления: 2015-12-01; просмотров: 33 | Нарушение авторских прав

mybiblioteka.su - 2015-2024 год. (0.007 сек.)