Bent functions and linear codes for CDMA.pdf Булева функция от четного числа переменных называется бент-функцией, еслиона максимально удалена от класса аффинных булевых функций. Задача построениябент-функций возникает во многих областях, в том числе в теории кодирования,где находит свое применение в системах коллективного доступа, таких, как стандартыцифровой сотовой связи CDMA. Данные стандарты используют бент-функции дляпостроения кодов постоянной амплитуды, что позволяет предельно снизить коэффициентотношения пиковой и средней мощностей сигнала. Такие коды состоят из векторовзначений бент-функций. И как известно, предпочтение отдается линейным кодам, таккак они довольно просты в реализации.Так возникла задача построения максимального линейного кода на основе заданнойбент-функции, такого, что при сдвиге данной бент-функции на любое кодовое словоне нарушалось бы свойство «бент». В [1] предлагается использовать для построениякода конструкцию Мак-Фарланда [2] f(x,y) = (x,n(y)) + g(y), где x,y E En/2; g(y) -булева функция от и/2 переменных; п - подстановка на En/2; En/2 - булев куб размерностии/2. Рассмотрим линейный код длины 2n, состоящий из векторов значенийфункций h(x,y) = g(y) и всех аффинных функций от и переменных. Размерностьданного кода равна k = 2n/2 + и/2, кодовое расстояние равно d = 2n/2. Например, длялюбой бент-функции из класса Мак-Фарланда от 6 переменных имеем линейный кодс параметрами [26, 11, 8], а для 8 переменных - с параметрами [28, 20,16].В [3] было доказано, что две бент-функции находятся на минимальном расстоянии2n/2 друг от друга тогда и только тогда, когда они отличаются на аффинномподпространстве размерности и/2 и обе на нём аффинны. Исходя из этого критерия,предложен следующий алгоритм построения максимального линейного кода.Алгоритм1) Вход: бент-функция f.2) Добавляем f в список функций functionList.3) Строим все аффинные подпространства размерности n/2, на которых даннаябент-функция аффинна (см. [3]), и добавляем их в список list.4) Далее вызываем рекурсивную функцию fin d C o d e (/, list, /unctionList).fin d C o d e (/, list, /unctionList)1) Вход: бент-функция / ; список аффинных подпространств, на которых / аффинна;список бент-функций.2) Для каждого аффинного подпространства из list строим бент-функцию g наминимальном расстоянии от /.3) Если g линейно независима со всеми функциям из /unctionList, то добавляемg в /unctionList.4) Далее формируем список аффинных подпространств newList. Для каждого аффинногоподпространства из list проверяем условие: если функция g аффиннана данном аффинном подпространстве, добавляем это аффинное подпространствов newList.5) Вызываем рекурсивную функцию findCode(g, newList, /unctionList).С помощью данного алгоритма удалось построить линейные коды для бент-функций от 6 переменных и для некоторых бент-функций от 8 переменных. Стоитзаметить, что построенные по предлагаемому алгоритму коды не обязательно являютсяоптимальными.Нетрудно показать, что для аффинно эквивалентных функций размерности такихкодов будут одинаковыми. Далее приведём таблицу с аффинно неэквивалентнымибент-функциями и размерностями кодов, построенных для них.n Бент-функция Размерность кода6 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж1Ж4 ф Ж2Ж6 ф Ж3Ж4ФФЖ3Ж5 ф Ж3Ж6 ф Ж4Ж5 ф Ж4Ж6 156 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж1Ж2 ф Ж1Ж4 ф X2Х ф Ж3Ж5 ф Ж4Ж5 156 Ж1Ж2Ж3 ф Ж1Ж4 ф Х2.5 ф Ж3Ж6 156 Ж1Ж2 ф Ж3Ж4 ф Ж5Ж6 158 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж1Ж4Ж7 ф Ж3^5ффЖ2^7 ф Ж1Ж5 ф Ж1Ж6 ф Ж4Ж8 298 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж3Ж5 ф Ж2^6ффЖ2^5 ф Ж1Ж7 ф Ж4Ж8 288 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж3Ж5 ф Х ^ ффХ 1Ж4 ф Ж2Ж7 ф Ж6Ж8 308 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж3Ж5 ф Ж2^6ффХ2Х5 ф Ж1Ж2 ф Ж1Ж3 ф Ж1Ж4 ф Ж7Ж8 308 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4Ж6 ф Ж3Ж5 ф Ж1Ж6 ф Ж2Ж7 ф Ж4Ж8 288 Ж1Ж2Ж7 ф Ж3Ж4Ж7 ф Ж5Ж6Ж7 ф Ж1Ж4 ф Ж3^6ффХ2Х5 ф Ж4Ж5 ф Ж7Ж8 298 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж3Ж4 ф Ж2Ж6 ф Х1Х7 ф Ж5Ж8 288 Ж1Ж2Ж3 ф Ж2Ж4Ж5 ф Ж1Ж3 ф Ж1Ж5 ф Х2Х6 ф Ж3Ж4 ф Ж7Ж8 308 Ж1Ж2Ж3 ф Ж1Ж4 ф Х2Х5 ф Ж3Ж6 ф Ж7Ж8 298 Ж1Ж2 ф Ж3Ж4 ф Ж5Ж6 ф Ж7Ж8 28Так же как и в кодах, основанных на конструкции Мак-Фарланда, код, полученныйс помощью предложенного алгоритма, имеет то же кодовое расстояние, равноеминимальному расстоянию между бент-функциями 2n/2. Особенностью метода являетсято, что он зависит от конкретного вида бент-функции, в отличие от конструкцииМак-Фарланда.

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