Обобщенные спектры некоторых линейных кодов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА Факультет вычислительной математики и кибернетики кафедра математической кибернетики

на правах рукописи

ЧЖАН Ичун

ОБОБЩЕННЫЕ СПЕКТРЫ НЕКОТОРЫХ ЛИНЕЙНЫХ КОДОВ

Специальность 01.01.09 - математическая кибернетика

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук профессор В.М. Сидельников

Москва - 1999

Содержание

Введение 3

Глава 1 Обобщенные спектры линейных двоичных кодов 12

§ 1. Основные понятия.....................12

§ 2. Обобщенное соотношение Мак-Вильямс.........15

§ 3. Обобщенные спектры двоичного кода Хэмминга .... 20

Глава 2 Обобщенные спектры кодов БЧХ 22

§ 1. Общее определение кодов БЧХ..............22

§ 2. 1-спектр одного класса троичного примитивного кода

БЧХ.............................23

п.1. Формула для веса произвольного слова дуального кода......................24

п.2. Вычисление 1-спектра кода, исправляющего

две ошибки.....................26

п.З. Асимптотические выражения для элементов 1-

спектра кода....................35

§ 3. 2-спектр двоичного примитивного кода БЧХ (в узком

смысле), исправляющего две ошибки..........40

п.1. Вычисление 2-спектра при нечетных т.....42

п.2. Случай, когда т четно..............47

§ 4. Асимптотические выражения для элементов г-спектра двоичного примитивного кода БЧХ (в узком смысле), исправляющего £ ошибок.................48

п. 1. Свойство сосредоточенности распределения весов ¿¡-наборов слов дуального кода........49

п.2. Оценки для многочлена Кравчука........51

п.З. Асимптотические выражения для элементов г-

спектра кода....................55

Глава 3 Обобщенные спектры кодов Рида-Маллера

первого и второго порядков 57

§ 1. г-спектр кода Рида-Маллера первого порядка.....58

§ 2. 2-спектр кода Рида-Маллера второго порядка.....59

п.1. Весовой спектр кода 11(2, т)...........59

п.2. Свойства симметрии ...............60

п.З. Одно свойство кода Е(2, т)............63

п.4. Вычисление чисел Е818283 ..........................66

п.5. О нахождении чисел ............74

Заключение 76

Литература 77

Введение

Математическая теория кодирования является наукой, результаты которой находят широкие приложения во многих разделах математики и в криптографии. В частности, многие проблемы, возникшие в криптографии в последние годы, естественно рассматривать как проблемы теории кодирования. К таким проблемам относятся: задачи разделения секрета, кодовые проблемы аутентификации, хэш-функции, система открытого шифрования по Мак-Элайсу, канал с подслушиванием типа II, и т.д.

Проиллюстрируем связь между обобщенным кодовым расстоянием линейного кода, изучаемой в диссертации, и проблемой передачи сообщений по каналу с подслушиванием типа II, которую изучали Озаров и Вайнер [1].

Рассмотрим бесшумный канал связи, по которому передаются п-мерные двоичные векторы. Канал подслушивает злоумышленник, который по своему выбору может выбрать любые я координат и получить их значения в переданном векторе. Созданный таким образом злоумышленником побочный канал обычно называют подслушивающим каналом, а бесшумный канал в этой ситуации — каналом с подслушиванием типа II [1]. Отправитель стремится закодировать сообщения так, чтобы минимизировать количество информации о передаваемом сообщении в подслушивающем канале. Злоумышленник в свою очередь стремится к противоположной цели: выбрать 8 координат так, чтобы получить наибольшую информацию о передаваемом векторе.

Мы рассматриваем только один естественный класс кодировок

сообщений, а именно, мы полагаем, что сообщения кодируются с помощью множества, которые представляют собой смежные классы по некоторому fc-мерному линейному подпространству С гг-мерного пространства F2n над конечным полем F2 ([п, fcj-коду С). Для того, чтобы передать сообщение, закодированное смежным классом х + С, х Е Fg, отправитель выбирает в нем случайный элемент v + х, v Er С, и посылает его получателю по бесшумному каналу связи.

В этом случае, как легко видеть [1], злоумышленник не получит о сообщении никакой информации, если s < d(С-1), где d(U) — кодовое расстояние линейного кода U и С1 — код, дуальный к С. Это следует из того, что при любом х в множестве векторов х + С (смежном классе) на любых s позициях одинаково часто появляются все s-ки, ибо любые s столбиков порождающей матрицы кода С линейно независимы.

Говоря более точно, злоумышленник получит s — dim Cg бит информации о сообщении из наблюдаемого множества позиций S = {zi,... ,г3}, где Cs — проекция кода С на множество позиций S. Пусть dim Cs = s — j. Как легко понять, в этом случае в пространстве С найдется j линейно независимых векторов, у которых на позициях из множества S стоят нули. Другими словами, в пространстве С есть j-мерное подпространство, у векторов которого позиции из S тождественно равны нулю.

Верно и обратное. Если у некоторого j-мерного подпространства пространства С позиции из S тождественно равны нулю, то злоумышленник может выбрать их для наблюдения и получить j бит информации.

Таким образом, одна из задач отправителя состоит в построении линейных кодов, у которых для любого 5, |5| = 5, размерность dim C\s была бы возможно большей. Более комбинаторный подход к решению этой и других подобных задач был предложен Вэем в работе [2]. Это вызвало новый интерес к понятию минимальных весов носителя, введенному ранее в работе [3] в другом контексте и с другой целью. Подход Вэя опирается на понятия носителя кода и

обобщенного веса Хэмминга. К их определению мы и переходим.

Пусть С — линейный [п, к]-код. Носителем x(D) подкода D называется множество координат, не тождественно равных нулю на D. Мощность w(D) носителя x(D) называется весом подкода D (или его эффективной длиной), r-м обобщенным весом Хэмминга линейного [п, /г]-кода С называется следующее число:

dr = dr(C) = mm{w(D)\D — [п, г]-подкод кода С} .

Набор чисел {d\, (¿2,..., ¿4} называется весовой иерархией кода С.

Озаров и Вайнер в [1] предложили следующую схему решения. Рассматриваются смежные классы по С1", в соответствии с к информационными символами выбирается один из смежных классов (их всего qk); в этом смежном классе случайным образом выбирается слово, которое и передается по каналу. Другими словами, рассматривается произвольное дополнение С' кода С1 такое, что С±фС' = F™. Здесь dim С' = к, и кодирование состоит в том, что к слову из С' прибавляется случайный элемент из CL. Злоумышленник имеет полную информацию о кодах С1 и С', но не знает процедуру случайного выбора.

Рассмотрим координатное пространство F^ и проекцию F™ —» Fq; при подслушивании передаваемого слова злоумышленник знает его образ при этой проекции. Пусть и C's — образы соответственно С-1 и С' при этой проекции. Информацией Inf^), полученной при подслушивании символов на позициях S, естественно считать размерность факторпространства C's/(C'sf)Cg)] тогда

Inf(5) = dimCg/(C'sПCg) = dimC's - dim(Qn^).

Назовем неопределенностью при подслушивании s символов величину

As = min{& — Inf(5) ||5| = s}. Оказывается, что ¿4-д8 < s < dk-Aa+i- Другими словами,

As = к — г при dr < s < dr+\.

Поскольку скачок неопределенности при передаче сообщений как элементов смежных классов по С1 происходит в точности в точках s = dr(C), то весовая иерархия кода С полностью определяет его поведение при использовании его как криптографического в канале с подслушиванием типа II.

Значительное число работ посвящено нахождению весовых иерархий известных кодов. В [2] вычислены весовые иерархии двоичных кода Хэмминга, кода Голея и кодов Рида-Маллера всех порядков. В [4] вычислены первые и последние несколько обобщенных весов Хэмминга для двоичного примитивного кода БЧХ с минимальным расстоянием 2т~г — 1. В [5] вычислена иерархия весов для кодов на многомерных квадриках. В [6] вычислена весовая иерархия для алгебро-геометрических кодов по поверхностям Дель Пеццо. В [7] даются некоторые эффективные алгоритмы вычисления весовой иерархии для циклических кодов. В [8] и [9] обсуждаются обобщенные веса Хэмминга g-ичных кодов Рида-Маллера. В [10], [11] и [12] даются некоторые границы и соотношения для обобщенных весов Хэмминга линейного кода. В [13] вычислен £¿2 = 8 для двоичного кода БЧХ длины 2т — 1, исправляющего две ошибки.

Близким к понятию весовой иерархии является понятие обобщенного спектра. По сравнению с традиционным весовым спектром обобщенный спектр дает намного больше информации о структуре кода. Кроме того, он содержит в себе весовую иерархию.

Исследование обобщенных спектров некоторых линейных кодов и составляет цель данной диссертации.

Пусть

Nj(r, С) = {D\D — [п, rj-подкод кода С такой, что w(D) — j}, j = l,...,n.

Назовем набор чисел N(r, С) = (Ni(r, С),..., Nn(r, С)) r-ым обобщенным спектром кода С, или, кратко, r-спектром кода С, где г = l,...,dimC. Отметим, что 1-спектр совпадает с традицион-

ным спектром весов Хэмминга (без элемента с индексом 0) кода С. г-й обобщенный вес Хэмминга ¿г является индексом первого отличного от нуля элемента г-спектра. В работе [14] принято несколько отличное определение обобщенного спектра. Некоторые коды имеют предельно простую весовую структуру. К таким кодам относятся код, дуальный к коду Хэмминга, и код Рида-Маллера первого порядка. Обобщенные спектры перечисленных кодов находятся прямым образом. Но для большинства линейных кодов вычислить элементы обобщенного спектра очень сложно. Даже для тех кодов, весовые спектры которых имеют относительно простую структуру, например, кода, дуального к коду БЧХ, исправляющему две ошибки, или кода Рида-Маллера второго порядка, вычисление элементов 2-спектра уже сводится к сложной алгебраической задаче. В работе [5] вычислены г-спектры кодов, ассоциированных с неособой квадрикой.

Мощным инструментом для вычисления обобщенного спектра тех кодов, дуальный код которых имеет простую весовую структуру, оказался несколько неожиданный факт, что элементы г-спектра любого двоичного линейного кода выражаются линейным преобразованием элементов г-спектра дуального кода.

Полученные в диссертации результаты (вычисление обобщенных спектров кодов) также могут быть представлены и как расчет числа различных множеств позиций 5, |5| = в, которые позволяют злоумышленнику в канале с подслушиванием типа II получить 3 битов информации в передаваемом сообщении при использовании отправителем некоторых классических линейных кодов, в том числе кодов БЧХ и кодов Рида-Маллера.

Диссертация состоит из введения, трех глав, заключения и литературы.

В первой главе центральным результатом является теорема 1, утверждающая, что совместная весовая функция кодов С^-, С^,..., С^ однозначно определяется совместной весовой функцией кодов Сь С2, ..., С}.. Другими словами, элементы спектра ^-наборов

двоичного линейного кода С выражаются через линейное преобразование спектра /¿-наборов дуального кода СЭта теорема является обобщением известной теоремы Мак-Вильямс для весового спектра линейного кода [16]. Подобное соотношение существует и между весовыми иерархиями с?2(С),..., ¿п{С)} и {^(С-1), <12(С±),..., ^(С1)} линейного кода [2].

Данную теорему удобно применять, когда известен (или не сложно вычислить) обобщенный спектр дуального кода. Это хорошо иллюстрируется в §3 на примере кода Хэмминга, поскольку код, дуальный к коду Хэмминга, является равновесным.

Вторая глава диссертации посвящена изучению обобщенного спектра кодов БЧХ. Весовой спектр кода, дуального к двоичному коду БЧХ длины 2т — 1, исправляющему две ошибки, был вычислен в явном виде в 1971 году В.М. Сидельниковым [15]. Он имеет 4 и 6 ненулевых элементов при нечетных и четных т соответственно. На основании данного весового спектра в §3 получена схема вычисления элементов 2-спектра кода БЧХ длины 2т — 1, исправляющего две ошибки, когда т нечетно. §2 посвящен исследованию 1-спектров троичных кодов БЧХ. В частности вычислен 1-спектр кода, дуального к троичному коду БЧХ длины п = Зт — 1, исправляющего две ошибки, для которого 1,а,а2 являются корнями порождающего многочлена, где а — примитивный элемент поля Р%т и первообразный корень степени п из единицы. 1-спектр дуального кода вычислен с помощью тригонометрических сумм, он имеет 8 и 12 ненулевых элементов при нечетных и четных т соответственно. По-видимому, вычисление 2-спектра кода, дуального к данному коду БЧХ, представляет трудную задачу.

Большое внимание во второй главе уделено асимптотическому поведению элементов обобщенного спектра кодов БЧХ, поскольку коды БЧХ представляют собой большой практической интерес с точки зрения исправления ошибок, особенно когда ожидаемое число ошибок мало по сравнению с блоковой длиной. Кроме того, двоичные коды БЧХ имеют одно замечательное свойство: если кон-

структивное расстояние кода БЧХ не превосходит примерно у/п, то все значения весов дуального кода расположены около п/2 [16]. Это свойство опирается на теорему Карлица-Ушиямы [17], в доказательстве которой использован глубокий результат Вейля из теории чисел [18]. Данное свойство существенно использовано для получения асимптотических выражений. Во второй главе показано, что 1-спектр троичного кода БЧХ и г-ж обобщенный спектр двоичного кода БЧХ обладают аналогичным свойством.

Асимптотические формулы для элементов 1-спектра двоичного кода БЧХ длины п — 2т — 1, исправляющего I ошибки, при п —> оо, были получены В.М. Сидельниковым в 1971 г. [19]. Развивая технику получения асимптотики для элементов 1-спектра линейного троичного квазисовершенного кода, исправляющего две ошибки, предложенный В.М. Сидельниковым и И.Б. Гашковым в [20], в §2 получены асимптотические выражения (при п оо) для элементов 1-спектра троичного кода БЧХ длины п = Зт — 1 с конструктивным расстоянием <5, корнями порождающего многочлена которого являются 1, а1,..., где а — примитивный элемент поля Р^т и первообразный корень степени п из единицы. В §4, найдя более тонкую оценку для многочлена Кравчука, аналогичным способом получены асимптотические выражения для элементов г-спектра двоичного кода БЧХ (в узком смысле) длины п — 2т — 1, исправляющего £ ошибок, когда п оо.

В третьей главе изучаются обобщенные спектры кодов Рида-Маллера первого и второго порядков. Код Рида-Маллера первого порядка получается удлинением кода, дуального к коду Хэмминга. Поэтому его г-ж обобщенный спектр вычисляется напрямую, где г — 1,..., т + 1.

Что касается кода Рида-Маллера второго порядка, мы ограничимся рассмотрением лишь его 2-спектра. Известно [2], что первые (|п — 1) элементов из спектра N(2, Я(2,т)) являются нулевыми. Типичное кодовое слово кода Я(2,т) задается булевой функцией = у(^уг + + е, у € где — верхняя треугольная

двоичная матрица, Ь — вектор из пространства .Р™, £ = 0 или 1. Если фиксирована, а линейная функция Ъхт+е пробегает по коду Рида-Маллера первого порядка Д(1,т), то (5(у),у е Р™) пробегает по смежному классу кода /2(2, га) по коду Е(1, га). Этот смежный класс полностью характеризуется симплектической матрицей В = <3 + . 1-спектр смежного класса ранга 2К (Д = 0,..., [у]) кода Я(2, т) по коду га) имеет всего три ненулевых элементов, их индексы равны: ^ = 2т~1 - г™-*-1, ^ == 2т~1 + г™"71"1, $ = 2т~1.

В третьей главе каждый элемент спектра 2-наборов представляется в виде суммы из 27([у] + I)3 чисел где — число пар слов (и1, и2) таких, что и1 принадлежит (какому-нибудь) смежному классу ранга йх и и; (и1) = ^, и2 принадлежит (какому-нибудь) смежному классу ранга и к; (и2) = а их сумма и1 + и2 принадлежит (какому-нибудь) смежному классу ранга вз и и^и1 + и2) = Как доказано в данной главе, вес слова кода ./2(2, га) отличен от 2Ш~1 тогда и только тогда, когда существует вектор с € Р™ такой, что Ь = сВ, где Ь и В — соответственно двоичный вектор и симплектическая матрица, соответствующие булевой функции, которая задает данное слово кода. С помощью данного свойства и благодаря различным симметричным соотношениям между числами -Е^1^ можно вычислить те значения |, у которых хотя бы один индекс из {¿1,62, ¿з, 5х, б'2, б'з} равен нулю, а также значение -\-E~~~). Данная задача сведена к вычислению чисел Н™^ пар симплектических т х га-матриц (В^Вг) таких, что: гапкВ! = 2г, гапкВ2 = 2«, гапк(В1 + В2) = 2г, гапк(^) = г. В §2 получена рекуррентная формула для вычисления Н™^. После этого можно получить сумму каждой пары элементов спектра 2-наборов кода Д(2,т), индексы которых симметрично расположенны относительно точки |п:

5Т1 (2) + 5Т2 (2) - Е (Яёй +

8\ . 6о . _4 _л

где п = §п + |(А- + А. + |з_), Т2 = |п _ + А. + ибо в эту

сумму входят либо числа Е^^з, у которых хотя бы один индекс из {¿1, 62, ¿3, 51, йз} равен нулю, либо значения типа Теперь легко найти значения тех элементов спектра 2-наборов кода Я(2, т), индексы которых находятся в диапазоне [|п, поскольку они не имеют "симметричных" элементов относительно |п.

В заключении приведены основные результаты диссертации.

Основные результаты опубликованы в работах [24] [25] [26] и доложены на семинарах по теории кодирования в ИППИ РАН, на механико-математическом факультете МГУ, на 3-ей всекитайской конференции молодых ученых (Пекин, август, 1998), и на 6-ом международном симпозиуме по алгебраической и комбинаторной теории кодирования (Псков, сентябрь, 1998).

Авто