О несуществовании двоичных кодов при различных условиях равномерной распределенности

• Автор: Ярыкина, Мария Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 77 с. : ил.

Оглавление
Введение
1 Коды малой мощности
§1.1 Определения
§ 1.2 Коды малой мощности
2 Коды средней мощности
§2.1 Вспомогательные результаты
§ 2.2 Неравенство для сумм биномиальных коэффициентов
§ 2.3 Покрытие булева куба
§ 2.4 Основная теорема для случая средних весов
3 Коды большой мощности
§3.1 Первое семейство
§3.2 Второе семейство
4 Оценки для /-упаковок большого радиуса
5 Неравенства для параметров матриц специального вида
Литература

Введение
В настоящей работе рассматриваются некоторые задачи теории кодирования. Изучается вопрос существования двоичных кодов, равномерно распределенных со степенью / по шарам, рассматривается вопрос существования /-упаковок большого радиуса (Д > га/4) и изучается вопрос существования матриц специального вида с особыми значениями параметров.
В работе получены следующие основные результаты:
1. Доказано несуществование кодов, равномерно распределенных со степенью I по шарам для почти всех значений их мощности в булевых кубах достаточно большой размерности п.
2. Для одного поддиапазона мощности кода получена, явная оценка значения размерности га, начиная с которой не существует кодов, равномерно распределенных со степенью / по шарам.
3. Получена явная верхняя оценка мощности /-упаковки большого радиуса (Д > га/4) в зависимости от параметра т = Д/га.
4. Получена явная точная оценка параметра матриц специального вида. С помощью таких матриц в [18] строятся корреляционно-иммунные функции порядка т > 0.5902... га+0(2 га) с максимальной нелинейностью.
История вопроса. К одним из самых важных задач теории кодирования относятся задача построения кодов, исправляющих ошибки и задача построения кодов для шифрования данных.
Теория кодирования начала развиваться в 1940-х годах с работ Хеммин-га, Шеннона и Голея. В этих работах рассматривалась практическая задача построения кодов, исправляющих ошибки.
Пусть у нас есть канал связи, на одном конце которого мы кодируем данные, а на другом конце — декодируем, и при передаче данных иногда случаются ошибки (шум, помехи). Задача состоит в том, чтобы придумать

такой код, чтобы мы могли выявить и исправить ошибки. Такой код называется кодом, исправляющим ошибки. Наиболее известными являются коды Хемминга - это коды, исправляющие одну ошибку. Кроме того, достаточно известны коды Боуза-Чоудхури-Хеквингема (БЧХ-коды), исправляющие 2 и более ошибок.
Вторая основная задача теории кодирования — это задача построения кодов для шифрования данных с целью сохранения секретности информации.
С появлением и ростом производительности компьютеров, а также появлением новых алгоритмов декодирования для обеспечения надежности шифрования требуются все новые и новые алгоритмы шифрования с лучшими параметрами. Для построения эффективных алгоритмов шифрования требуются булевы функции с определенными свойствами: уравновешенность, корреляционная иммунность, нелинейность, алгебраическая степень и т.д.
Для кодирования текста с закрытым ключом часто используется поточное шифрование. Оно устроено следующим образом: к нашему (двоичному) тексту мы прибавляем (сложение но модулю 2) некоторую псевдослучайную последовательность Т = {4П}. Чтобы дешифровать закодированный текст, мы прибавляем к нему ту же самую последовательность Т и получаем исходный текст.
Для получения псевдослучайной последовательности Т можно использовать регистр сдвига с линейной обратной связью (БРЭЯ).
Однако, если длина наименьшего БРЭЯ, порождающего последовательность Т, равна А(Г), то можно узнать всю последовательность Т, зная только 2Л(Т) первых ее значений. Поэтому шифрование с использованием лишь одного БРЭЯ не обеспечивает достаточной секретности шифрования.
Одним из более надёжных является алгоритм, использующий несколько БРЭЯ следующим образом. Выбирается некоторая булева функция / от I переменных, и в качестве входных переменных функции / используются выходы различных БРЭЯ: БРЭЯх, БРБЯг,
Знгенталер в работе [23] предложил алгоритм дешифрования указанной выше комбинации БИБЯ, используя корреляцию выхода функции / и некоторого подмножества ее входных переменных, и ввел понятие корреляционно-иммунной функции. Булева функция / называется корреляционно-иммунной

Глава
Коды большой мощности
В этой главе мы рассмотрим ГРРШ коды, имеющие мощность т в следующем диапазоне:
А— т 2га~х, п5
где 5 — произвольное натуральное число (в > ка(1), см. теорему 4), А — некоторое положительное число.
В случае кодов большой мощности мы выделим два семейства мощностей. Для каждого семейства мощностей у нас будет свой способ доказательства.
Первое семейство (и > 1 — некоторое фиксированное число, 5 — натуральное число):
5 = 1 и12 4 . 2П 71+1 < т{п) 2"-1
в = 2 и12 4 2п 2 / т{п) (4 + с?) 271 2 , Ч
5« а®
со II с/2 и12 4 271 3 , ч т(п) (1 + сз) 2П 3 , Ч
,5« е; г
5 иР л 2п в , т(п) (Д + С,) 2”
4 а® 5 / а®
и второе семейство, состоящее из всех «больших» значений т, не попавших