Информатика · объяснение и практика
Из таблицы истинности в XOR-многочлен: сначала закрепите порядок переменных
Построить единственную алгебраическую нормальную форму булевой функции преобразованием Мёбиуса и подтвердить её подстановкой на всех наборах.

В теме Логика и логические схемы · Учебная карта
Главная мысль
Алгебраическая нормальная форма записывает булеву функцию как XOR-сумму квадратсвободных мономов. Коэффициенты находятся над GF(2) по таблице значений. Подстановка во все исходные наборы проверяет и коэффициенты, и принятую нумерацию переменных.
Метод и постановка
Начните с порядка строк, потому что одна и та же последовательность значений при разных соглашениях описывает разные функции. В инструменте номер строки является двоичной маской, а x₁ соответствует младшему биту. Для двух переменных порядок наборов поэтому равен (0,0), (1,0), (0,1), (1,1), если координаты записывать как (x₁,x₂).
В каждой маске хранится сначала значение функции. Проход по переменной добавляет по модулю два коэффициент маски без этой переменной к маске с ней. После всех проходов получается преобразование Мёбиуса на решётке подмножеств. Коэффициент пустого монома — свободная константа; остальные коэффициенты показывают, какие произведения различных переменных входят в XOR-сумму. Квадраты не нужны: на булевых значениях x²=x.
Проверка и границы вывода
Обычная ДНФ соединяет слагаемые операцией ИЛИ. Здесь сложение исключающее, поэтому два одинаковых монома сокращаются. Подмена XOR на ИЛИ может оставить несколько отдельных наборов правильными и всё же изменить функцию. Алгебраическая степень определяется максимальным числом переменных в ненулевом мономе, а не длиной напечатанной строки.
Проверяйте результат полной подстановкой, пока число переменных мало. Для каждой маски суммируются коэффициенты всех её подмножеств по модулю два. Полученная таблица должна совпасть с исходной во всех позициях. Нулевой многочлен не имеет обычной конечной степени; инструмент отмечает это отдельно. Степень константы один равна нулю. Вывод не обещает минимальную схему логических элементов: число мономов и сложность произвольной схемы относятся к разным критериям.
Пример
Таблица 0,1,1,0 в принятом порядке задаёт XOR двух переменных. Полученные коэффициенты равны 0,1,1,0, поэтому форма записывается x₁⊕x₂ и имеет степень один.
На наборе (1,1) оба линейных слагаемых дают единицу, их XOR равен нулю. Если ошибочно заменить сложение на ИЛИ, получится единица и проверка последней строки сразу обнаружит подмену.
От чтения к действию
А теперь — вы
Частые вопросы
Это ДНФ с операцией ИЛИ?
Нет. Сумма здесь исключающая: одинаковые мономы сокращаются по модулю два.
Как читать порядок строк?
Маска 1 означает x₁=1 при остальных нулях; x₁ является младшим битом.
Углублённый разбор
Булева производная по XOR
Булева производная сравнивает выходы функции на двух соседних вершинах куба. Она показывает, при каких значениях остальных переменных изменение одного входного бита действительно изменит результат.
Перед началом: XOR и поле F₂; Алгебраическая нормальная форма.
Разность определяется сложением по модулю два
Для вектора eᵢ с единственной единицей положим Dᵢf(x)=f(x)⊕f(x⊕eᵢ). Производная равна единице ровно на тех входах, где переключение бита i меняет ответ. Деления на малое приращение здесь нет: область конечна, а соседняя точка определяется направлением. Поэтому обычные правила вещественного дифференцирования нельзя переносить без проверки.
Переключив тот же бит ещё раз, получим исходную точку. Следовательно, Dᵢf(x⊕eᵢ)=Dᵢf(x), и результат не зависит от xᵢ. Кроме того, DᵢDᵢf=0: два одинаковых слагаемых сокращаются по XOR. Производные по разным координатам коммутируют, поскольку обе разворачиваются в сумму значений на четырёх вершинах одной грани куба.
Что происходит с мономами АНФ
Каждый моном АНФ содержит переменную не более одного раза. Если xᵢ отсутствует, переключение ничего не меняет, и моном сокращается. Если моном имеет вид xᵢm, то xᵢm⊕(xᵢ⊕1)m=m. Значит, нужно удалить xᵢ из каждого содержащего её монома и сложить результаты по модулю два. Линейный член xᵢ даёт постоянную единицу, а не нуль.
Полученная формула сразу задаёт условие чувствительности. Например, производная x₂⊕1 означает изменение выхода только при x₂=0. Это сильнее одного среднего числа: видно, какие контексты входа опасны. Для схемы с ограничениями на допустимые входы производную следует исследовать именно на разрешённом подмножестве куба, а не усреднять по невозможным состояниям.
От функции чувствительности к влиянию координаты
При равномерном распределении входов влияние i определяется как доля единиц в Dᵢf. Если входы зависимы или имеют смещённые вероятности, та же производная сохраняется, но её математическое ожидание меняется. Поэтому численное влияние всегда относится к заданной вероятностной модели. Нулевая производная означает полную независимость от координаты на всём кубе.
Для проверки вычислите исходную функцию дважды на каждой паре соседей и сравните с символической производной. Такой перебор независимо проверяет сокращение мономов и порядок переменных. Проверять только число единиц недостаточно: две разные производные могут иметь одинаковое влияние, но менять результат на совершенно разных наборах входов.
Три разных условия одинаковой средней силы
Условие. Пусть f=x₁x₂⊕x₂x₃⊕x₁. Найдите три координатные производные и влияния при равномерном трёхбитовом входе.
- Для первой координаты остаются x₂ от произведения x₁x₂ и единица от x₁. Поэтому D₁f=x₂⊕1.
- Для второй координаты два произведения дают x₁ и x₃; линейный член не меняется. Получаем D₂f=x₁⊕x₃.
- Для третьей координаты единственный содержащий её моном даёт D₃f=x₂. Условия чувствительности первой и третьей координат противоположны.
- Каждая из трёх производных равна единице на четырёх из восьми входов. Все влияния равны 1/2, хотя сами множества чувствительных входов различаются.
Ответ. D₁f=x₂⊕1, D₂f=x₁⊕x₃, D₃f=x₂; все три влияния равны 1/2.
Проверка. Проверка всех восьми входов сравнивает три формулы с прямым переключением каждого бита; повторная производная по той же координате всюду нулевая.
Где легко ошибиться. Одинаковое влияние не означает одинаковое поведение на конкретном входе. Сначала найдите всю функцию Dᵢf, затем усредняйте по нужному распределению.
Проверьте понимание
Вопросы к этой главе
Производная уменьшает степень ровно на один?
Не всегда: старшие мономы могут не содержать выбранную переменную. Степень ненулевого результата не превосходит исходную степень минус один, но может оказаться ещё меньше.
Что означает постоянная производная один?
Переключение выбранного бита меняет результат на каждом входе. Это точное тождество на кубе; оно не требует статистического предположения о частотах входных наборов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- SageMath: Boolean functions
Прочитаны derivative(u) и точная ненормированная формула walsh_hadamard_transform. Собственные трёхбитовые функции, чувствительности и спектральные проверки вычислены отдельно; примеры документации не воспроизводятся.
Баланс булевой функции в преобразовании Уолша
Нулевой коэффициент Уолша проверяет баланс нулей и единиц. Остальные коэффициенты отвечают на другой вопрос: насколько функция совпадает с каждым линейным паритетом и его дополнением.
Перед началом: Булев куб; Ортогональность знаковых функций.
Знак превращает XOR в произведение
Зафиксируем W_f(a)=Σₓ(−1)^{f(x)⊕a·x}, где скалярное произведение вычисляется по модулю два. Нормирующий множитель не используется. При a=0 сумма равна количеству нулей функции минус количество единиц. Поэтому функция сбалансирована тогда и только тогда, когда W_f(0)=0. Максимальный модуль коэффициента равен N=2ⁿ.
Для ненулевого a положительные слагаемые соответствуют совпадению f(x) с паритетом a·x, отрицательные — несовпадению. Число совпадений равно (N+W_f(a))/2. Дополнение паритета меняет знак коэффициента. Лучшее аффинное приближение поэтому определяется максимальным модулем спектра, а не только коэффициентом при нулевом векторе.
Баланс не исключает заметной связи с паритетом
Равное число выходных нулей и единиц устраняет смещение относительно константы. Но функция может хорошо совпадать с некоторой комбинацией входных битов. Например, сам ненулевой паритет сбалансирован, хотя один его спектральный коэффициент имеет модуль N. Использовать баланс как единственную проверку нелинейности поэтому недостаточно.
Ортогональность характеров даёт ΣₐW_f(a)²=N². Чтобы увидеть это, раскройте квадрат и поменяйте порядок конечных сумм. Внутренняя сумма по a равна N при одинаковых входах и нулю при разных. Это удобная проверка масштаба преобразования: нормированная версия имеет другую сумму квадратов, и смешивать соглашения нельзя.
Спектр нужно привязывать к порядку координат
Запись вектора 001 здесь означает коэффициенты при x₁,x₂,x₃ именно в таком порядке. Многие библиотеки индексируют таблицы младшим битом первой переменной, поэтому готовый массив может выглядеть переставленным. Надёжная проверка одного коэффициента вычисляет знаки непосредственно для выбранного вектора, не полагаясь на положение числа в массиве.
Полный перебор малой функции одновременно проверяет баланс, спектр и число совпадений. Если известна только часть таблицы, оценка спектра этой части не является точным спектром всей функции. Пропущенные входы способны изменить знак коэффициента и выбор лучшего паритета; здесь нет автоматического продолжения по нескольким наблюдениям.
Баланс при четырёх ненулевых коэффициентах
Условие. Рассмотрите f=x₁x₂⊕x₂x₃⊕x₁⊕x₂ на F₂³. Найдите баланс и качество лучшего аффинного приближения.
- Вычисление таблицы на восьми входах даёт четыре нуля и четыре единицы. Следовательно, W_f(000)=0.
- Прямые знаковые суммы дают W_f(001)=−4, W_f(011)=4, W_f(100)=4, W_f(110)=4. Остальные четыре коэффициента нулевые.
- Проверка энергии даёт четыре слагаемых по 16, то есть 64=8². Максимальный модуль спектра равен 4.
- Лучшее аффинное приближение совпадает на (8+4)/2=6 входах. Например, паритет x₁ имеет шесть совпадений, а дополнение x₃ использует отрицательный коэффициент.
Ответ. Функция сбалансирована; максимальное аффинное согласие равно 6/8.
Проверка. Независимый перебор всех шестнадцати аффинных функций подтверждает максимум шесть совпадений и минимальное расстояние два.
Где легко ошибиться. W_f(0)=0 проверяет только баланс относительно константы. Для аффинных приближений нужны все коэффициенты и явно выбранная нормировка.
Проверьте понимание
Вопросы к этой главе
Отрицательный коэффициент хуже положительного?
Он означает связь с дополнением соответствующего паритета. При поиске аффинного приближения обе константы разрешены, поэтому важен модуль коэффициента.
Почему сумма квадратов не равна единице?
Использована ненормированная сумма N знаков. При делении каждого коэффициента на N сумма квадратов станет единицей; смешение двух соглашений меняет численные выводы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- SageMath: Boolean functions
Прочитаны derivative(u) и точная ненормированная формула walsh_hadamard_transform. Собственные трёхбитовые функции, чувствительности и спектральные проверки вычислены отдельно; примеры документации не воспроизводятся.
Алгебраическая иммунность: найти низкостепенной аннигилятор
Высокая степень булевой функции ещё не описывает все её низкостепенные зависимости. Аннигилятор обращается в нуль на одном из двух уровней функции. Найдём его для трёхбитного большинства и отдельно докажем, что аннигиляторов меньшей степени нет.
Перед началом: Алгебраическая нормальная форма над GF(2); Решение линейной системы по модулю 2.
Произведение функций проверяется по значениям
Работаем в булевом кольце: сложение является XOR, умножение — AND, а x²=x. Ненулевая функция g называется аннигилятором f, если fg=0 на каждом входе. Это означает, что g обязательно равна 0 во всех точках, где f=1. Нулевой g исключается, иначе любая задача имела бы бессодержательный ответ степени, не характеризующей f.
Алгебраическая иммунность AI(f) — наименьшая степень ненулевого g, для которого fg=0 или(1+f)g=0. Проверяют оба уровня f: нули и единицы. Это отличается от вычисления степени самой f или расстояния до линейной функции. Один найденный аннигилятор даёт верхнюю границу AI, но ещё не доказывает её точное значение.
Низкая степень превращает поиск в линейную систему
Для степени не выше 1 запишем g=a0+a1x+a2y+a3z. Коэффициенты неизвестны, а значения мономов на каждом фиксированном входе известны. Требование нулевого g на выбранном уровне f образует однородную линейную систему над GF(2). Нетривиальное ядро означает существование нужного аннигилятора. Затем можно добавить квадратичные мономы и повторить проверку.
У функции большинства f=xy+xz+yz единичный уровень состоит из 110,101,011,111. Подстановка линейного g даёт четыре уравнения. Сравнение строки 111 со строками 110,101,011 последовательно обнуляет a3, a2, a1, затем a0. Для нулевого уровня 000,100,010,001 сначала обнуляется a0, а затем три остальных коэффициента. Поэтому ни у f, ни у 1+f ненулевого линейного аннигилятора нет.
Точное значение требует верхней и нижней границы
Функция g=(1+x)(1+y)=1+x+y+xy имеет степень 2 и ненулевая. Она равна 1 только при x=y=0, где большинство f всегда 0. Следовательно, fg=0 на всех восьми входах. С учётом предыдущего исключения степеней 0 и 1 получаем AI(f)=2. Проверка степени 0 уже включена в линейную систему: единственная ненулевая константа 1 не исчезает ни на одном непустом уровне.
Такой конечный пример показывает способ построить проверяемое свидетельство: предъявить коэффициенты g и доказать невозможность меньшей степени. Он не является общей оценкой безопасности шифра. Даже точная AI описывает один конкретный критерий; другие зависимости и свойства генератора оцениваются отдельно. Здесь проверяется булева алгебраическая задача, а не стойкость реальной системы.
Иммунность трёхбитного большинства
Условие. Для f(x, y, z)=xy+xz+yz над GF(2) найдите AI(f). Разрешено использовать все восемь булевых входов; g=0 не допускается.
- Единичный уровень f:110,101,011,111. Линейный g на нём вынуждает a0=a1=a2=a3=0.
- Нулевой уровень f:000,100,010,001. Здесь требование g=0 также обнуляет все четыре коэффициента.
- Квадратичный g=(1+x)(1+y) ненулевой и поддерживается только при x=y=0, где f=0. Поэтому fg=0.
- Нижняя граница AI≥2 и найденный аннигилятор степени 2 дают точное AI=2.
Ответ. AI(f)=2; один минимальный аннигилятор —1+x+y+xy.
Проверка. Перебор всех 15 ненулевых аффинных g не находит аннигилятора ни у f, ни у 1+f. Таблица восьми значений выбранного квадратичного g даёт тождественно нулевое произведение fg.
Где легко ошибиться. Не объявляйте найденную степень минимальной без исключения меньших степеней на обоих уровнях функции.
Проверьте понимание
Вопросы к этой главе
Почему g=0 запрещена?
Она уничтожает произведение с любой функцией и потому не несёт информации о низкостепенной зависимости.
Достаточно искать только аннигиляторы f?
Нет. В определении AI сравниваются f и её дополнение 1+f. Низкая степень может обнаружиться только на одной из этих двух сторон.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Claude Carlet: Boolean Functions for Cryptography and Coding Theory, определение AI
Определение аннигилятора и минимум по двум уровням булевой функции. Линейные системы и полный конечный сертификат для большинства разобраны самостоятельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Ближайшее кодовое слово и гарантированное исправление — разные утверждения
Перечислить малый двоичный линейный код, установить минимальное расстояние и показать все ближайшие к принятому слову варианты без скрытого выбора.
Открыть темуСообщение как вложенный интервал: что именно передают биты арифметического кода
Построить точный интервал арифметического кодирования короткого сообщения и найти целиком содержащийся в нём двоичный цилиндр.
Открыть темуКороткая рекурсия объясняет префикс, но не доказывает неизвестное продолжение
Найти минимальную линейную рекурсию конечной последовательности над малым простым полем, проверить знаки коэффициентов и границу прогноза.
Открыть тему