Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
n − 1, 2n, (n/2) − 1), состоящий из векторов кода A n и их дополнений. Пример 15. Код Адамара B 12 с параметрами (11, 24, 5) со следующими кодовы- ми словами: 0 11 , 1 11 , [(11011100010)], [(00100011101)]. 3. Код C n , (n, 2n, n/2), состоящий из строк матрицы A n и их дополнений. Код A n является симплексным. Это означает, что расстояние между любыми двумя кодовыми словами равно n/2. Если H — матрица Сильвестра, то A n , B n и C n — групповые коды. Если H — матрица Адамара типа Пэйли, то полученные коды нелинейны для любого n > 8. Линейные оболочки этих кодов принадлежат классу так называемых квадратично- вычетных кодов. 9.1.5. Связь кодов Адамара с кодом Хэмминга Рассмотрим связь кодов Адамара A n , n = 2 k − 1 с кодом Хэмминга. Для этого вспомним определение ортогонального кода. 9.1. Матрицы Адамара, коды Адамара 101 Определение. Если C — линейный [n, k]-код над F , то дуальный или ортого- нальный к нему код C ⊥ определяется как множество всех векторов, ортогональных всем кодовым словам кода C: C ⊥ = {u | u · v = 0 для любого v ∈ C}. Если код C имеет проверочную матрицу H и порождающую G, то дуальный код C ⊥ имеет проверочную матрицу G и порождающую H. Теорема 57. Код, дуальный к коду Хэмминга, является кодом Адамара A n , по- строенным из матрицы Сильвестра. Справедливо и обратное. Доказательство будем проводить индукцией по m, где n = 2 m − 1. Пусть m = 2. Рассмотрим код Хэмминга длины 3, заданный следующей прове- рочной матрицей H 3 = · 1 0 1 0 1 1 ¸ . Она является порождающей матрицей ортогонального кода к коду Хэмминга. Кодо- вые слова имеют вид 0 0 0 1 0 1 0 1 1 1 1 0 . Добавляя проверку на четность и заменяя 0 на 1 и 1 на -1, получаем 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0→1 1→−1 −→ H(4) = 1 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 1 , т. е. матрицу Сильвестра (см. пример 10). Пусть для n = 2 m−1 −1 имеем: код, ортогональный коду Хэмминга, является кодом Адамара A 2 m−1 с порождающей матрицей H n , являющейся проверочной матрицей кода Хэмминга длины n. Покажем, что матрица вида H = 0 . . . 0 1 1 . . . 1 0 H n H n 0 является проверочной матрицей кода Хэмминга порядка 2n − 1. Действительно, это так, поскольку число столбцов равно 2n − 1 и все они являются различными векто- рами длины m (в H n все столбцы — различные векторы длины m − 1). Строки матрицы 0 H n H n 0 , 102 Глава 9. Другие коды порождают код с кодовой матрицей 0 A n A n 0 . Добавляя вектор (0 . . . 01 . . . 1), получаем код, порожденный матрицей H, кодовая матрица которого имеет вид 0 A n A n 0 1 A n A n 1 = A 2n+1 . Отсюда, добавив столбец из нулей, имеем матрицу 0 0 A n A n 0 0 0 1 A n A n 0 1 0→1 1→−1 −→ H(2n) = H(n) H(n) H(n) H(n) , где H(n) — матрица Сильвестра порядка n, следовательно, по теореме 54 матрица H(2n) также является матрицей Сильвестра. Доказательство в обратную сторону проводится также по индукции, начиная с кода Адамара. N 000 011 101 110 n=3 Рис. 9. Симплексный код длины 3 Код Адамара A n называется также симплексным, поскольку его вершины об- разуют в E n правильный симплекс — расстояние между любыми двумя кодовыми словами одно и то же и равно n + 1 2 . На рис. 9 приведен пример кода A 3 , вершины которого образуют правильный тетраэдр. 9.2. Коды Рида-Маллера 103 9.2. Коды Рида-Маллера Определение кодов Рида-Маллера (RM-кодов) удобнее всего приводить в терми- нах булевых функций. Рассмотрим произвольную булеву функцию f (x 1 , . . . , x m ) от m переменных, тождественно не равную нулю. В качестве кодовых слов кода Рида- Маллера длины n = 2 m будут выбраны двоичные векторы, являющиеся наборами значений булевых функций специального вида. Но прежде чем задать способ выбо- ра этих функций, приведем некоторые определения и утверждения. Каждой строке таблицы истинности произвольной функции f , для которой значение функции рав- но единице, можно поставить в соответствие элементарную конъюнкцию длины m, равную единице на этом наборе, т. е. произведение всех переменных x 1 , . . . , x m , взя- тых с отрицанием или без. Дизьюнкция этих элементарных коньюнкций называется совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции f . Далее, используя закон де Моргана x ∨ y =q(qx&qy), удалим все дизъюнкции в представлении функции f (x 1 , . . . , x m ), другими словами, функция f (x 1 , . . . , x m ) будет выражена через функции из множества {&, q}. Так как f — произвольная булева функция, тождественно не равная нулю, то отсюда следует, что система функций {&, q} полна. Напомним, что система булевых функций {f 1 , . . . , f s , . . .} называется полной, если любая булева функция может быть записана в виде формулы через функции этой системы. Теорема 58 (Жегалкин). Каждая булева функция может быть однозначно представлена посредством полинома по модулю 2. Этот полином носит название полинома Жегалкина. Доказательство. Рассмотрим произвольную булеву функцию f (x 1 , . . . , x m ), представленную системой функций {&, q}. Выражая всякий раз отрицание через сложение: qx = x + 1 и опуская знаки &: x&y = xy, после раскрытия скобок и при- ведения подобных членов x + x = 0, xx = x, используя дистрибутивность, получим многочлен X 1≤i 1 ,..., i s ≤m a i 1 ...i s x i 1 · . . . · x i s + a, где a i 1 ...i s , a ∈ {0, 1} — константы для различных i 1 , . . . , i s . Полученный многочлен является полиномом Жегалкина. Теперь покажем, что произвольная булева функция однозначно представляется полиномом Жегалкина. Подсчитаем число различных полиномов Жегалкина X 1≤i 1 , ..., i s ≤m a i 1 ...i s x i 1 · . . . · x i s + a. Для фиксированного s, s ≤ m, имеем µ m s ¶ возможностей выбора произведения x i 1 · . . . · x i s . Так как 0 ≤ s ≤ m, то всего возможно m X s=0 µ m s ¶ = 2 m 104 Глава 9. Другие коды различных элементарных конъюнкций от переменных x 1 , . . . , x m , взятых без отри- цания. Далее, так как коэффициенты a i 1 ...i s , a могут принимать два значения 0 или 1, получаем 2 2 m различных полиномов Жегалкина, каждому из которых отвечает единственная булева функция. С другой стороны, число всех булевых функций от m переменных также равно 2 2 m N Из теоремы Жегалкина получаем, что функции 1, x 1 , . . . , x m , x 1 x 2 , . . . , x m−1 x m , . . . , x 1 x 2 . . . x m образуют базу пространства E 2 m всех булевых функций от m переменных. Теперь перейдем к определению кодов Рида-Маллера. Определение. Двоичный код Рида-Маллера RM(r, m) порядка r, 0 ≤ r ≤ m, — это совокупность векторов длины 2 m , отвечающих полиномам от m переменных сте- пени не больше r. Код Рида-Маллера RM(1, m) первого порядка ортогонален расширенному коду Хэмминга и совпадает с кодом Адамара B m . В свою очередь, расширенный код Хэм- минга является кодом Рида-Маллера RM(m − 2, m) порядка m − 2. Из определения кода Рида-Маллера порядка r вытекает, что он состоит из всех линейных комбинаций векторов, соответствующих произведениям 1, x 1 , . . . , x m , x 1 x 2 , . . . , x m−1 x m , . . . , x m−r+1 x m−r+2 . . . x m . Эти произведения задают базис кода Рида-Маллера порядка r. Отсюда следует, что размерность кода равна k = 1 + µ m 1 ¶ + · · · + µ m r ¶ , все кодовые слова имеют четный вес. Код Рида-Маллера RM(r, m) любого порядка r, 0 ≤ r ≤ m, может быть описан с помощью конструкции Плоткина. Теорема 59. Cправедливо RM(r + 1, m + 1) = { (u, u + v) | u ∈ RM(r + 1, m), v ∈ RM(r, m) }. Доказательство. Рассмотрим произвольное кодовое слово f из RM(r+1, m+1). С одной стороны, оно представляет собой двоичный вектор длины 2 m+1 , с другой стороны — многочлен от (m + 1) переменных, степень которого не больше r + 1. Перепишем многочлен f (x 1 , . . . x m+1 ) следующим образом f (x 1 , . . . , x m+1 ) = g(x 1 , . . . , x m ) + x m+1 h(x 1 , . . . , x m ), где степень g(x 1 , . . . , x m ) не больше r + 1, а степень h(x 1 , . . . , x m ) не больше r. Пусть g и h — векторы длины 2 m , отвечающие многочленам g(x 1 , . . . , x m ) и h(x 1 , . . . , x m ) соответственно, иными словами, g и h — это наборы значений булевых функций (от переменных x 1 , . . . , x m ), представленных этими многочленами. Поскольку степень g(x 1 , . . . , x m ) не больше r + 1, то, по определению кода Рида-Маллера, вектор g 9.2. Коды Рида-Маллера 105 принадлежит коду RM(r + 1, m) порядка r + 1. Аналогично, h принадлежит коду RM(r, m). Рассмотрим многочлен g(x 1 , . . . , x m ) как многочлен от переменных x 1 , . . . , x m+1 : g 0 (x 1 , . . . , x m+1 ) = g(x 1 , . . . , x m ). Вектор длины 2 m+1 , отвечающий этому многочлену, равен (g, g). Действительно, из булевой функции g(x 1 , . . . , x m ) от m переменных мы получили булеву функцию g 0 (x 1 , . . . , x m+1 ) от (m + 1) переменных, где переменная x m+1 является фиктивной. Вторая половина таблицы истинности булевой функции g 0 (x 1 , . . . , x m+1 ), отвечаю- щая значению 1 переменной x m+1 , дублирует первую. Рассмотрим также многочлен h 0 (x 1 , . . . , x m+1 ) как многочлен от переменных x 1 , . . . , x m+1 , определенный с помощью многочлена h(x 1 , . . . , x m ) следующим образом h 0 (x 1 , . . . , x m+1 ) = x m+1 h(x 1 , . . . , x m ) = = 0 · h(x 1 , . . . , x m ) + 1 · h(x 1 , . . . , x m ). Нетрудно видеть, что этому многочлену отвечает двоичный вектор длины 2 m+1 вида (0 2 m , h). Таким образом, получили f = (g, g) + (0 2 m , h) = (g, g + h). N Теорема 60. Минимальное расстояние кода Рида-Маллера RM(r, m) порядка r, 0 ≤ r ≤ m, равно d = 2 m−r . Доказательство. Доказательство будем проводить индукцией по m. Пусть m = 1. В этом случае имеем следующие два тривиальных кода Рида- Маллера порядков 0 и 1 соответственно: RM(0, 1) = {(00), (11)} с кодовым расстоянием 2; RM(1, 1) = {(00), (01), (11), (10)} с кодовым расстоянием 1. Пусть для любого (m−1) теорема верна и минимальное расстояние кода RM(r, m−1) порядка r равно 2 m−1−r для любого r, удовлетворяющего условию 0 ≤ r ≤ m − 1. Рассмотрим конструкцию Плоткина для кода RM(r, m), изложенную в предыдущей теореме: RM(r, m) = {(u, u + v)|u ∈ RM(r, m − 1), v ∈ RM(r − 1, m − 1)}. По предположению индукции, кодовое расстояние кода RM(r − 1, m − 1) равно 2 m−1−(r−1) = 2 m−r , а кода RM(r, m − 1) равно 2 m−r−1 . Нетрудно видеть, что d((u, u + v), (u 0 , u 0 + v 0 )) ≥ 2 m−r для произвольных кодовых слов (u, u + v) и (u 0 , u 0 + v 0 ) из RM(r, m) (см. доказа- тельство теоремы Плоткина в гл. 1). Очевидно, что между кодовыми словами кода RM(r, m) достижимо расстояние, равное 2 m−r N 106 Глава 9. Другие коды Таким образом, код Рида-Маллера RM(r, m) порядка r имеет параметры: • длина кода равна n = 2 m ; • мощность кода равна 2 k , где k = 1 + µ m 1 ¶ + · · · + µ m r ¶ ; • кодовое расстояние d = 2 m−r . Коды Рида-Маллера имеют быстрые процедуры кодирования и декодирования и широко используются на практике, в частности, коды Рида-Маллера третьего поряд- ка представляют собой хороший экземпляр кодов, которые могут быть использованы в криптографии для шифрования информации в криптосистемах с открытыми клю- чами, а именно в криптосистеме МакЭлиса. Теорема 61. Для любых r, 0 ≤ r ≤ (m − 1) код Рида-Маллера RM(m − r − 1, m) ортогонален коду Рида-Маллера RM(r, m). Доказательство. Рассмотрим произвольные векторы f и g, где f ∈ RM(m − r − 1, m), g ∈ RM(r, m). По определению кодов Рида-Маллера, степени многочленов f (x 1 , . . . , , x m ) и g(x 1 , . . . , x m ) не превосходят m−r −1 и r соответствен- но. Следовательно, степень многочлена f (x 1 , . . . , x m ) · g(x 1 , . . . , x m ) не превосходит m−1 и отвечающий этому многочлену вектор принадлежит коду RM(m−1, m). По- скольку в коде RM(m−1, m) все вершины имеют четный вес, то есть скалярное про- изведение векторов f и g равно нулю, то получаем RM(m − r − 1, m) ⊆ RM( |