RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2016, том 7, выпуск 3, страницы 73–92 (Mi mvk197)

Об одном методе построения булевых функций малого веса, не имеющих имплицент от фиксированного числа переменных

П. В. Ролдугин

Московский государственный университет информационных технологий, радиотехники и электроники, Москва

Аннотация: Задача построения булевых функций без имплицент от $k$ переменных сведена к построению такого множества $M$ булевых функций от $k-1$, что для любых различных векторов $\overline\beta_1,\dots,\overline\beta_k\in V_{k-1}$ и любых $\alpha_1,\dots,\alpha_k\in\{0,1\}$ существует $f\in M\colon f(\overline\beta_1)=\alpha_1,\dots,f(\overline\beta_k)=\alpha_k$. Это позволяет строить функции без имплицент от $k$ переменных, имеющие вес, близкий к минимально возможному значению. Построено несколько семейств таких булевых функций.

Ключевые слова: булевы функции, имплиценты, двоичные матрицы.

УДК: 519.719.2+519.712

Получено 20.IV.2014

DOI: 10.4213/mvk197



Реферативные базы данных:


© МИАН, 2024