Bases over the field GF(2) generated by the schur - hadamard operation.pdf Рассматривается векторное пространство Fr2, состоящее из всех двоичных векторов длины r. Для любых d таких векторов можно определить их покомпонентное произведение [1]. Пустое произведение (когда в нём нет элементов) равно вектору из всех единиц. ds Пусть s,d G N, s > d > 1, r = , B - базис векторного пространства Fr и i=0 i 2 F С F2 - семейство s двоичных векторов, такое, что все возможные покомпонентные произведения до d векторов из семейства F (включая пустое произведение) образуют базис B [2, 3]. Для векторов a = (a1, ..., an) и b = (b1, ..., bn) из Fqn покоординатное умножение a * b = (aibi,..., anbn) называется произведением Шура или произведением Адамара [4]. В задаче «Bases» [5] для данных s, d и r требуется описать все (или хотя бы некоторые) базисы B, для которых такое семейство F существует, или доказать, что таких базисов нет. Предлагается дать также практическое применение таких базисов. Эту задачу естественно рассматривать на языке бинарных матроидов, элементами которых являются вектор-столбцы (или вектор-строки) некоторых матриц над полем GF(2), их циклов, подпространств, независимых множеств и, наконец, баз этих мат-роидов. В этой работе данная проблематика связывается с кодами Рида - Маллера порядка d, основанных на булевых функциях степени d [6, 7], поскольку покомпонентное произведение векторов можно интерпретировать как конъюнкцию значений соответствующих аргументов булевой функции в полиноме Жегалкина (алгебраической нормальной форме, ANF). В связи с этой интерпретацией становятся естественными предлагаемые применения этих базисов в теории кодирования и схемах разделения секрета. Покомпонентные произведения определённых в условии задачи векторов должны быть, очевидно, ненулевыми и линейно независимыми, в том числе - разными, поэтому можно считать их некоторыми r вектор-строками в таблице некоторой булевой функции f, зависящей от s аргументов t1, . . . , ts и степени не выше d (после некоторой, может быть, перенумерации её аргументов), так что таблица истинности булевой функции f вместе со вспомогательными столбцами (для конъюнкций аргументов по два, три и т. д.) будет выглядеть так (табл. 1): Та б л и ц а 1 1 t2 ts ii t4s t1...td f 1 1 x i xs x1 1s x^ x i fl 1 хГ xs 1s Xr 1 fr Эту таблицу можно рассматривать как расширенную матрицу системы линейных уравнений над GF(2) с некоторой матрицей B и правым столбцом f . Следовательно, базис получается тогда и только тогда, когда существует биекция между всеми булевыми функциями f, зависящими от s аргументов t1, ...,ts степени не выше d, и всем списком значений f1 , . . . , fr на этих булевых векторах значений аргументов x1 , . . . , xs . Рассмотрение булевых функций от s аргументов степени вплоть до d означает рассмотрение кода Рида - Маллера порядка d, список значений всех аргументов можно расположить в естественном порядке их двоичных представлений [2, 8]. Пусть X и Y - некоторые множества, F - некоторое подмножество множества всех функций f : X Y. Естественно назвать подмножество Z С X множеством единственности класса функций F, если для любой функции g : Z Y существует единственная функция f из класса F, такая, что её ограничение на Z совпадает с g, то есть f|Z = g. В нашем случае Y = {0,1}, F - подмножество булевых функций степени d, X = Vs - пространство булевых векторов длины s. Искомые базисы при этом оказываются множествами, однозначно определяющими булеву функцию степени не выше d по любым заданным на этом множестве значениям функции. Если транспонировать табл. 1 (без столбца значений функции), то получим матрицу, которую естественно назвать матрицей Рида - Маллера порядка d. Векторный матроид вектор-столбцов этой матрицы тоже естественно назвать матроидом Рида - Маллера, циклами которого являются минимальные по включению множества линейно зависимых векторов, а базами - искомые базисы как максимальные подматрицы с ненулевым определителем. При этом верхняя строка (имеющая нулевой номер) определителя состоит из одних единиц, а строки с первой по s-ю являются вектор-строками семейства F , определяющего базис B, составленный из всех строк этой подматрицы. Каждый вектор-столбец матрицы Рида - Маллера удобно обозначать номером N двоичного представления набора аргументов t1 ... ts. Например, для s = 3, d = 2 и r = 7 имеем матрицу Рида - Маллера, приведённую в табл. 2. Можно предложить конструкцию для базисов B с таким семейством F для всех s, d, s d > 1, на основе кодов Рида - Маллера порядка d, которая даёт серию искомых базисов для всех параметров s, d, r. Конструкция 1. Определим семейство F как множество столбцов матрицы Рида - Маллера при следующем условии: слово х1... xf значений аргументов t1,... ,ts имеет вес Хэмминга не больше d. Т а б л и ц а 2 N 0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 t1 0 1 0 1 0 1 0 1 t2 0 0 1 1 0 0 1 1 t3 0 0 0 0 1 1 1 1 t1t2 0 0 0 1 0 0 0 1 t1t3 0 0 0 0 0 1 0 1 t2t3 0 0 0 0 0 0 1 1 Для примера в табл. 2 берутся все столбцы, кроме столбца 7, потому что в этой конструкции в базис входят те столбцы, у которых в строках t1, t2, t3 имеется не более двух единиц. Очевидно, что значения коэффициентов соответствующей функции f определяются рекуррентно и однозначно, как и в доказательстве теоремы об ANF [8, теоремы 2.6 и 2.10]: коэффициент перед композицией для подмножества T (мощности не больше d) в множестве {t1, . . . , ts } аргументов определяется как сумма значений f и значений коэффициентов для всех подмножеств R С T, так что это множество T - множество единственности [8] для семейства булевых функций степени не выше d и, следовательно, базис. Обозначим этот базис через B0. Таким образом, трактовка искомого базиса как множества единственности полинома Жегалкина булевой функции степени не выше d равносильна невырожденности некоторой подматрицы в полной матрице кода Рида - Маллера порядка d (в соответствии с теоремой Кронекера - Капелли). Конструкция 2. Поскольку полная аффинная группа является группой автоморфизмов кодов Рида - Маллера, её можно использовать для описания целого класса искомых базисов. Рассмотрим полную аффинную группу, действующую на множестве вектор-столб-цов (t1, . . . , ts)T. Ясно, что преобразования этой группы реализуют перестановки столбцов матрицы Рида - Маллера. В силу того, что эта группа является группой автоморфизмов, она переводит множество единственности в множество единственности, то есть базис в базис. Отсюда следует Утверждение 1. Пусть В0 - построенный в конструкции 1 базис. Тогда для любого аффинного преобразования векторов - значений аргументов (t1,... ,ts)T множество преобразованных вектор-строк базиса B0 также образует базис. Такие базисы можно использовать для построения кода Рида - Маллера, который определяется через порождающую матрицу, содержащую, в том числе, все возможные произведения l строк [8, 9]. Так как количество и длины этих строк определяют параметры кода, то построение базиса определённой размерности регулирует кодирующие способности кода, построенного посредством такого базиса. Однако существуют базисы, не получающиеся из базиса B0 посредством аффинного преобразования, и их описание приводит к задаче аффинной классификации булевых функций, которая решена для квадратичных булевых функций, т. е. для d = 2 [8]. Перечисление искомых базисов может быть произведено при помощи графа баз соответствующего матроида, поскольку он оказывается связным. Пусть M - матроид, B' и B - две его базы: BZ,B G B. Определим, что эти базы соединены ребром в графе Г(В) баз этого матроида, если |BZ ф B| = 2, где ф означает симметрическую разность множеств: B' ф B = (B' \\ B) U (B \\ B') = (B' U B) \\ (B' П B). Поскольку |B ф B| = 0 и B' ф B = B ф B', имеем симметричное антирефлексивное бинарное отношение на множестве B баз матроида M, т. е. действительно получается граф с вершинами - элементами множества B. Каковы свойства этого графа? Ясно, что если M дискретен, т.е. в нем нет циклов, то семейство B баз одноэлементно и ребер нет. Если в M есть единственный цикл C - E - множество всех элементов матроида M, то базами являются все подмножества в E мощности |E| - 1, и граф представляет собой (|E| - 1)-элементную клику. Вне этих крайних случаев имеем |B' ф B| = 2m - чётное число, поскольку |B'| = |B |. Пусть |B' ф B| = 2m, m > 1: B 0... 00 ... 00... о B' По аксиоме замены для каждого b' G B' \\ B существует такой b G B \\ B', что B1 = = (B' \\ {b'}) U {b} является базой. Вычисляем |B1 ф B| = |(B1 U B) \\ (B n B1)| = |B1 U B| - |B1 n B| = = (|B' U B| - 1) - (|B' П B| + 1) = (|B' U B| - |B' П B|) - 2 = 2(m - 1), при этом |Bi ф B'| = |Bi U B'| - |Bi П B'| = (|B'| + 1) - (|B'| - 1) = 2, то есть B1 и B' соединены ребром в графе Г(В). Отсюда индукцией по m получаем Утверждение 2. Граф Г(В) связен. Первоначально этот результат был получен в работе [10] для максимальных совместных подсистем линейных неравенств и применён в алгоритме выделения всех максимальных совместных подсистем несовместной системы линейных неравенств [11].

Скачать электронную версию публикации