Коды Рида — Соломона
двойственного к К (определение ниже). Первый способ определения кодов является более естественным, но зато второй во многих случаях более удобен для их построения и исследования их свойств. Он преимущественно используется в теории кодирования.
Мы также часто будем пользоваться вторым способом задания линейного кода. Подробно объясним, что это такое.
Скалярное произведение (х,у) векторов х = (.щ----, ж„), у = і;у\----,уп) ? Fg! в поле F,; определя
ется соотношением
П
*,?) = 5И, (з)
і=1
где сложение и умножение в последней сумме выполняется в поле F?.
Код А: над Fg состоит из всех векторов Ь ? Fg!. таких, что (6, а) = 0 для всех а ? к'.. Но другому,
если і.....а/.. базис кода к'.. то базисом кода к', являются векторы Ьі.....Ьп для которых
(bj,as) = 0 для всех s = 1,..., к. Отметим, что сумма размерностей кодов К. и к', равна п.
Матрица В, строками которой являются базисные векторы bs кода К (их число п к) называется проверочной матрицей кода К. а матрица А, строками которой являются базисные векторы кода к'.. называется порождающей матрицей кода к'.. Таким образом, коду К. принадлежат все векторы а, для которых выполнено
/’' =(). а G F. (4)
где значок ' обозначает транспонирование соответствующего объекта, или все векторы а, которые имеют вид
а = йЛ. aeFg, a ? F. (5)
Заметим, что в формуле (4) а1 столбец высоты п. Матрицы /’ и ,4 по определению взаимно ортогональны: А ¦ Вт = О, В ¦ Ат = 0.
Утверждение 1. Код К, имеет кодовое расстояние d, если выполнены два условия
i. Любой комплект из d 1 столбцов матрицы В является линейно-независимым.
ii. Найдется комплект из d столбцов матрицы В, который является линейно-зависимым.
С помощью утверждения 1 все или почти все методы построения кодов К. с кодовым расстоянием d сводятся к построению проверочной матрицы В, у которой любой комплект из d 1 ее столбцов является линейно-независимым.
Наиболее известными матрицами В, для которых выполнено утверждение 1, являются матрицы
| В = Вц = |
|
d 2,
где п ^ g 1 и 21 = {ад, ад,..., ап} комплекта из d 1 столбцов матрицы определитель
/з? at
Pl $2
al at
различные ненулевые элементы поля Fg. Столбцы любого В является линейно-независимыми. Это следует из того, что
аі
Pd-
д2
d-1‘
ad-2 ad-2 Rd-2
Pi P2 ‘ ‘ ‘ Pd-1
с попарно различными fij является отличным от 0 определителем Вандермонда.
Множество 21 часто расширяют, а именно, добавляют к нему элементы 0 ё F, и особый элемент оо. Мы далее будем полагать, что матрица В в (6) определена именно для такого расширенного множества 21. О подробностях такого определения удобно рассказать ниже в разделе 7.4.
Нумерацию столбцов матрицы В будем производить с помощью элементов множества 21. Так, столбец с номером а является j-ым столбцом, если а = otj. Совершенно аналогично поступаем с координатами вектора х = (хаі,ха2,... ,хап) G F, их также индексируем элементами множества 21, которые записаны в определенном порядке.
Коды Рида Соломона.
Мы рассмотрим три вида кодов Рида Соломона длин п = q 1, q, q+1. Все они имеют в качестве проверочной матрицу вида (6), но различные множества 21.
Тип 1. п = q 1. В этом случае множество Л состоит из всех ненулевых элементов поля F,;.
Тип 2. п = q. В этом случае множество Л состоит из всех элементов поля F,;. Следует сказать, что столбец (aj,aj,..., а^-2)т, у которого aj = 0 имеет вид (1,0,...,0)т.
Тип 3. п = q+1, d 3. В этом случае множество Л состоит из всех элементов поля F,; и еще одного элемента оо (бесконечности). Предполагается, что элемент оо обладает естественными свойствами
этого понятия. Например, аоо = оо, а Ф 0. = 0 и т.п. Столбец (а'-.а,-.....aj . у которого
aj = оо по определению имеет вид (0,0,..., 1)т. Более обще, мы считаем, что значение многочлена /(.г) = о fsXS степени не выше d2 в точке оо является коэффициент /,/ В частности, /(оо) = О, если степень f(x) меньше d 2. В этом случае мы говорим, что f(x) имеет корень оо.
Можно сказать, что мы рассматриваем проективное пространство Fg U {оо} и многочлены на нем.
Коды Рида Соломона всех типов будем обозначать одним символом RSq(n,d). Все они имеют параметры [п,п d+l,d\q и являются, так называемым, g-значными МДР-кодами (см. [17]), а именно кодами, которые имеют максимально возможную размерность п d + 1 при заданных п и d.
Одна из модификаций кода типа 3 (длины п = q 1) будет далее использована как основа для построения системы открытого шифрования, которую мы будем подробно изучать. В частности, мы рассмотрим группу автоморфизмов (определение ниже) этого кода. Эта группа имеет наиболее сложное строение по сравнению с группами автоморфизмов кодов типов 1 и 2. Поэтому мы сначала достаточно подробно изучим группу автоморфизмов кодов типа 2, а затем в основном без доказательства приведем нужные свойства группы автоморфизмов кода типа 3.
Надо сказать, что коды типа 3, в некотором смысле, являются наиболее интересными среди определенных ранее трех типов кодов Рида Соломона. В частности, они имеют наиболее мощную группу автоморфизмов и наибольшую длину и размерность при заданном кодовом расстоянии d. Коды типа 1 используются для построения циклических кодов Боуза Чоудхури Хоквингема.
Коды RSg(n,d) всех типов могут быть заданы (определены) и несколькими другими способами.
Код Боуза Чоудхури Хоквингема.
Предположим, что поле F,..r = р1 , где число I' делит I является подполем поля F,;. q = р1. В
этом случае мы будем рассматривать r-значный подкод кода RSg(n,d), п = q 1, который состоит из всех векторов RSg(n,d), координаты которых принадлежат полю F,.. Этот код называют кодом Боуза Чоудхури Хоквингема (обозначение: ВСНг(п, /)).
Он имеет параметры [q \ .d'. k']r, где d' ^ d, к1 ^ q 1 (d 1 [^г]){г- По поводу этих оценок и замечательных свойств кода BCHr(n,d) см. книгу [17].
Следует обратить внимание на то, что размерности кода RSq(n, d) и кода BCHr(n, d) вычисляются над разными полями: размерность первого над F,;. а размерность второго над его подполем Fr.
Группа автоморфизмов кода RSq(n, d), п = q.
Если переставить координаты кодового вектора а кода К. то полученный вектор а' может как принадлежать, так и не принадлежать коду К. Если перестановка координат а такова, что а (а) = a' G К, для всех а € к'., то она называется автоморфизмом кода К,. Очевидно, что если а' другой автоморфизм, то произведение а ¦ а' также является автоморфизмом.
Поэтому все автоморфизмы кода К, образуют группу Л/с, которая называется группой автоморфизмов кода АГ Заметим, что на множестве перестановок координат векторов пространства F можно естественным образом определить операцию по отношению к которой все они образуют группу Sn порядка пі, называемую симметрической группой.
Перестановку а удобно представлять себе в виде перестановочной матрицы IV = Г = Цу^Ц, которая реализует эту перестановку в виде матричного умножения. А именно, элемент матрицы 7ij равен 1 тогда и только тогда, когда координата с номером % переходит посредством действия а в координату с номером j. Во всех остальных случаях 7^ = 0. Таким образом, матрица Г представляет из себя матрицу, у которой в любой строке и в любом столбце имеется ровно одна 1. Перестановочная матрица Г реализует перестановку а координат вектора а в виде матричного умножения следующим образом !т(а) = аГ. Матричная группа автоморфизмов G = Gc образована всеми матрицами IV, у которых а 6 Л/с-
Если Г 6 G?. а матрица В является проверочной матрицей кода к'., то В - Г, очевидно, также является проверочной матрицей этого кода к'.. Поэтому она может быть представлена в виде В ¦ Г = h ¦ В. где невырожденная матрица h размера пкхпк является матрицей перехода от одного базиса пространства строк матрицы В к другому В'. Последнее высказывание на языке матриц записывается как раз в виде В' = h ¦ В.
Интересно отметить, что указанное отображение Г -л h реализует гомоморфизм матричной группы G;c автоморфизмов кода К, (матрицы размера п х п) в матричную группу, образованную матрицами h размера п кхп к. Ядро JQC) этого гомоморфизма образуют элементы Г, которые оставляют на месте все векторы кода АГ Поэтому матрицы Н, на которые отображается группа 6\-посредством соответствия В-Г = h ¦ В. изоморфна факторгруппе 6\-/./(АГ). Так как далее мы ограничимся рассмотрением только кодов, у которых ядро JQC) тривиально (состоит из одного элемента), то мы всегда будем полагать, группа, образованная матрицами Н, изоморфна группе GК таким кодам относятся коды RSq(n, d) и коды BCHq(n, d).
Доказательство этого утверждения в более общей форме см. ниже (Лемма 2).
Рассмотрим ансамбль (множество) В/с кодов, определяемых проверочными матрицами из множества ® = {В ¦ Г|Г 6 Sn}. где В одна, не важно какая, матрица вида (6). Число Чq(n,d) различных (как множеств) кодов к'. = RSg(n,d) в ансамбле /V (по другому, кодов с проверочной матрицей вида (6)), как нетрудно видеть, равно
Т) f
%(n,d) = ~ (8)
|Ьх|
где К, = RSq(n,d) один из фиксированных кодов Рида Соломона с проверочной матрицей (6).
Как мы видим, число различных кодов Рида Соломона полностью определяется порядком его группы автоморфизмов. К настоящему времени группа автоморфизмов G\- кода К, = RSq(n, d) не вычислена.
Можно только утверждать, в Gnsq(n,d) входят подстановочные матрицы, которые реализуют подстановку х ах, а € F,; \ {0} = F*, элементов поля F,; в себя. Эти матрицы образуют группу, которая изоморфна, так называемой, мультипликативной группе поля F?.
Эта группа является циклической, поэтому и коды Рида Соломона также как и коды Боуза Чоудхури Хоквингема при п = q 1 с помощью соответствующей нумерации множества 21 могут быть сделаны циклическими. На этом здесь останавливаться не будем (см. [17]).
Число проверочных матриц кода RSq(n, d)
Если h невырожденная матрица размера d 1 х d 1, то, как нетрудно видеть, проверочные матрицы В и НВ определяют один и тот же код RSq(n, d). Матрицы В и НВ различны, если Нф Е (единичная матрица). Отсюда следует, что число различных проверочных матриц, которые определяют один и тот же код RSq(n,d), равно Nq^-1, где Nq.s число невырожденных квадратных матриц Н размера s х s.
Лемма 1. Число Nq.s равно
Nq,s = (qs - 1 )(?* -?)¦¦ ¦ (qs - q8-1 )- (9)
Обобщенные коды RSq(n, d), n = q + 1, Рида Соломона.
Нам удобно рассмотреть несколько более широкий по сравнению с RSq(n,d) класс кодов, который мы будем называть обобщенные коды Рида Соломона и обозначать их тем же символом RSq(n,d).
Пусть FJ; = F,; U ос поле, к которому добавлен элемент оо. Рассмотрим матрицу
| ( | ZiOti | Z20-2 | Znan | \ | |||
| z±ai | Z2O.2 | ZnOtn | |||||
| с = | ziaf | Z2CX2 | ZnOLn | , d 3, n = q = 1, | (10) | ||
| \ | ziaf-2 | Z20!2_2 ¦ | ¦ znafc2 | / |
Так же, как для обычного кода Рида Соломона, обобщенный код длины п = q + 1 имеет кодовое расстояние равное d и размерность п d + 1.
Матрица С, очевидно, может быть представлена в виде С = В ¦ D, где D = diag(zi, z2, ¦ ¦ ¦, zn), Zj G Fg \ {0}, диагональная матрица и В проверочная матрица кода Рида Соломона типа 3. Преобразованная матрица С будет выступать далее как проверочная матрица системы открытого шифрования. В этой связи значительный интерес представляет строение группы обобщенных автоморфизмов кода Рида Соломона с проверочной матрицей В, к изучению которой мы переходим.
Обобщенный код BCHr(n,d) определяется аналогично тому, как это было сделано в разделе 7.5: BCHr(n,d) = RSq(n,d) П FJ?, т.е. коду BCHr(n,d) принадлежат все векторы кода RSq(n,d), координаты которых принадлежат подполю F,. поля F,;. Обобщенные коды BCHr(n,d) включают в себя и, так называемые, кода Гоппы (см. [17]).
Код можно задать и с помощью своей проверочной матрицы над полем Fr размера пкхп, где к размерность (над Fr) кода BCHr(n,d). Эта матрица также может иметь вид (10). Определить размерность к даже в частных случаях обобщенных кодов BCHr(n, d). в отличие от размерности любого кода RSq(v.d). очень нетривиально.
В общем случае сделать это не представляется возможным.
Группа обобщенных автоморфизмов кода RSq(n, d), п = q + 1, Рида Соломона
. Если в качестве обычных автоморфизмов кода К, выступали перестановочные матрицы Г, то в качестве обобщенных автоморфизмов выступают матрицы вида Л = Г ¦ D, где D невырожденная диагональная матрица, которые носят название мономиальных. Другими словами, Л перестановочная матрица, у которой ненулевыми элементами являются ненулевые элементы поля F,;.
Мономиальные матрицы сохраняют расстояние Хемминга. А именно, d(a,b) = d(aA,bA).
Как будет видно ниже, это свойство позволяет использовать эти матрицы в системе открытого шифрования. Нашей основной целью является получение нетривиальных нижних верхних оценок порядка группы обобщенных автоморфизмов кода RSg(n,d) и затем оценок для числа различных кодов RSg(n,d).
Теперь переформулируем для обобщенных автоморфизмов некоторые из определений раздела 7.6.
Если мономиальная матрица А такова, что а А = a’ G К. для всех а € к'-, то она называется обобщенным автоморфизмом кода К,. Очевидно, что если А' другой автоморфизм, то произведение А ¦ А' также является автоморфизмом.
Поэтому все обобщенные автоморфизмы кода К. образуют группу Б/с, которая называется группой обобщенных автоморфизмов кода К,. Элементами группы Бю являются, так называемые, мономиальные матрицы размера п х п. Также как в разделе 7.6 можно рассмотреть представление Н/с группы обобщенных автоморфизмов Б/с в виде невырожденных матриц над Fg размера п кхп к. А именно, элементу А из Б/с сопоставим матрицу h = ііа, которая определяется соотношением
ііа-В = В-А. (И)
Произведению А ¦ А' двух элементов из Б соответствует произведение д(А ¦ А') = //.у ¦ На двух элементов из Н/с- Заметим, что порядок следования сомножителей в Н^ обратный по сравнению с Б/с- Поэтому рассматриваемое отображение является гомоморфизмом д : А На группы Б а: в группу матриц размера п к х п к над полем F?.
Лемма 2. Для кода К, = RSq(n,d) гомоморфизм g является изоморфизмом, т.е. |Sjc| = |Дс|.
Теорема 1. Порядок группы Бавтоморфизмов кода Рида Соломона К, = RSg(n,d) не превосходит iVgjCi-i, где :?д.5. число невырожденных квадратных матриц Н размера s х s над полем Fg.
Хотя оценка для числа Зк во многих случаях, по-видимому, весьма грубая, ничего лучшего не известно.
Рассмотрим ансамбль (множество) Лк, К. = RSq(n,d), кодов, определяемых проверочными матрицами из множества 'В = {/’Л|Л G }. где В одна, не важно какая, матрица вида (6), а множество всех мономиальных матриц над полем Fg. Заметим, что ансамбль Лк совпадает с множеством кодов, проверочные матрицы которых имеют вид (10).
Кроме того, нетрудно установить, что \Uq,n\ = nl(q 1). Нас будет интересовать число различных кодов в ансамбле Лк-
По тем же соображениям, что приведены в разделе 7.6, для числа Aq(n,d) различных обобщенных кодов Рида Соломона JC = RSq (п, d) в ансамбле Лк имеет место равенство
= (12)
р /с|
К сожалению, группа 3к обобщенных автоморфизмов кода Рида Соломона не известна. Поэтому мы не можем воспользоваться равенством (12) для вычисления числа Aq(n,d).
Из теоремы 1 и соотношений (9) и (12) следует
Следствие 1. Для числа Aq(n,d) различных обобщенных Рида Соломона К, = RSq(n,d) ? ансамбле Лк имеет место оценка
n\(q 1)
n\(q 1)г
(13)
Aq(n,d) ^
(qd х 1 ){qd 1 q) ¦ ¦ ¦ (qd 1 qd 2) ’
= RSq(n,d) и Nqj- число различных невырожденных
где к = п d + 1 размерность кода К, матриц размера к х к.
Далее мы докажем, что группа 3к содержит подгруппу, изоморфную группе дробно-линейных преобразований. Строение последней группы мы изучим в следующем разделе.
Группа дробно-линейных преобразований.
Элементами группы дробно-линейных преобразований Ф,; множества F(; = F,; U {ос} в себя являются дробно-линейные функции ір(х) = , отличные от постоянной, т.е. функции, у которых определи
тель матрицы
отличен от нуля. Очевидно, каждое дробно-линейных преобразование р(х)
взаимно однозначно отображает множество F'q в себя.
Множество Фд действительно является некоммутативной группой. Умножением ® в ней служит суперпозиция функций, т.е. ір ® ір' = рір'іх)). Группа Ф? = PGL(2, q) имеет порядок (q + 1 )q(q 1). Очень интересным свойством группы Фд является ее трижды транзитивность.
Это означает, что для любых двух пар троек (а,. и-,. 3) и (Іц. h-,.h-,). о.;.
Ь-, е F(;. с попарно различными координатами в группе Ф? найдется элемент ір (всегда один), для которого выполнено р{щ) = Ьі, і = 1,2,3.
Теорема 2. Группа 3к обобщенных автоморфизмов кода К, = RSq(n,d), п = q + 1, Рида Соломона с проверочной матрицей В (см. (6)) содержит подгруппу, которая изоморфна группе дробнолинейных преобразований множества Fg.
Этот результат будет использован при анализе стойкости системы открытого шифрования, построенной с помощью кода Рида Соломона.
Группа 3к обобщенных автоморфизмов кода Рида Соломона также является трижды транзитивной в следующем смысле. Для любой пары упорядоченных троек из попарно различных элементов (/3г,/32,/3з) и (7і,72,7з), где {/Зг,/32,/З3}, {71,72,73} G Я = {аь а2,... ,а„} = Fg существует такая мономиальная матрица А? € 3к, которая переводит координаты хрг, хр2, хр3 вектора ж = (хаі, Ха-21 - - - 1 хап) в координаты х1г, х12, хГі вектора хА? с умножением их на соответствующие постоянные, определяемые диагональной матрицей Dv = diag(dai,da2,... ,dan).
Например, с помощью подходящей матрицы А? можно передвинуть на первые три места любые три координаты вектора х. В частности, если {/Зі = 1,/32 = 0,/33 = оо} и 71 = 1,72 = а2,73 = а3. то хА? = (d at %1 j da2XQj da3Xoo,da4xv(a^,.. .,danx^an)) для некоторой подходящей функции ір(х).
Декодирование
Мы приведем ряд утверждений о декодировании кодов, которые будут играть центральную роль при обосновании стойкости рассматриваемых систем открытого шифрования.
Неформально говоря, под термином декодирование понимается алгоритм, который позволяет по искаженному ошибками кодовому вектору а’ восстановить исходный кодовый вектор а. Таким образом, декодирование сводится к решению уравнения
а' = а + е, а ? К, wt(e) ^ t, (14)
где неизвестными являются кодовый вектор а и вектор ошибки е.
Имеется несколько различных типов декодирования.
i. Корреляционное декодирование кода К. Это алгоритм, который по предъявленному вектору ж ? F находит один или несколько кодовых векторов а ? К, ближайших (в метрике Хемминга) к х.
ii. Декодирование кода К, в пределах его кодового расстояния. Это алгоритм, который по вектору ж, который отстоит от одного из кодовых векторов К. на расстояние ^ ; вычисляет этот
ближайший кодовый вектор. Этот вектор обязательно является единственным.
Векторы ж, которые отстоят от всех кодовых точек на расстояние большее, чем половина кодового расстояния, могут быть декодированы как угодно, в частности, алгоритм может вообще отказаться от их декодирования.
iii. Декодирование кода К, за пределами его кодового расстояния. (Алгоритм промежуточного положения между і. и іі.) Это алгоритм, который по вектору ж, находящемуся не очень далеко (іІ(х. а) ^ f) от некоторого кодового вектора а кода К,, вычисляет один или несколько кодовых векторов а', находящихся на расстоянии ^ f от ж, где t' d^K.g-1 некоторая постоянная (параметр алгоритма).
Наиболее сильным и трудным для реализации является алгоритм і. В настоящее время не известно ни одного нетривиального класса кодов, которые имеют алгоритм декодирования этого типа с простой реализацией. Другими словами, этот алгоритм может быть реализован только с помощью перебора.
А именно, можно сравнивать ж со всеми векторами кода и выделять среди них ближайшие кодовые векторы, или осуществлять просмотр векторов из окрестности ж, пытаясь найти в ней кодовый вектор. Какой из этих упомянутых алгоритмов перебора выгодней с вычислительной точки зрения зависит от соотношений между параметрами кода.
Сложность реализации корреляционного декодирования нетривиальных кодов возрастает как экспоненциальная функция от их длины. На практике ни один из таких кодов на современных вычислительных средствах не может быть декодирован, начиная с длины и 100.
Наиболее легким для реализации является алгоритм декодирования типа іі. Для большинства так называемых алгебраических кодов известны алгоритмы декодирования в пределах их кодового расстояния, сложность которых возрастает как полином небольшой степени от длины кода.
К таким кодам относятся и, рассмотренные нами, обобщенные коды Рида Соломона RSq(n,d). Их декодирование в пределах кодового расстояния может быть осуществлено не более, чем за О(іг') операций в поле Fg [17], [15].
Не надо думать, что для каждого кода существует простой алгоритм декодирования в пределах его кодового расстояния. По современным представлениям такие алгоритмы могут существовать только для кодов, которые снабжены определенной алгебраической или комбинаторной структурой.
Вместе с тем у большинства кодов, не очень точно выражаясь, отсутствует в проверочной матрице какая-либо структура, это коды общего положения. Примером первого типа кодов является код Рида Соломона или код Рида Маллера (совершенно разные коды), а примером второго код, у которого проверочная матрица выбрана случайно среди всех матриц определенной размерности.
Декодирование в пределах кодового расстояния (типа іі.) некоторых типов кодов общего положения является NP-полной задачей, т.е. предположительно не может быть осуществлено за полиномиальное время от их длины. Более того, общепринято, что
Тезис А: декодирование последовательности кодов, которые не обладают полезной для декодирования алгебраической или комбинаторной структурой, не может быть осуществлено за полиномиальное время от их длины.
Это достаточно расплывчатое, но очень правдоподобное утверждение строго не доказано и в настоящее время возможность его доказательства весьма проблематична. Вместе с тем на этом утверждении держится обоснование стойкости открытого шифрования на базе кодов, корректирующих ошибки.
Мы далее, специально не указывая на это, будем постоянно его придерживаться.
Обычно при построении кода, корректирующего ошибки, стараются наделять его определенной структурой, которая обеспечивает, с одной стороны, заданное значение его кодового расстояния, и, с другой, позволяет осуществлять его декодирование с малой вычислительной сложностью.
Приведем одно почти очевидное утверждение о сложности декодирования любого кода с помощью алгоритма типа іі.
Утверждение 2. Любой линейный код К, с параметрами [n,k,d\r, d п/2, имеет алгоритм декодирования в пределах его кодового расстояния, сложность которого не выше 0(mm(nrk, п]Г^._0 ()), гдеі = {^]. 3
