Циклические коды

ДИСКРЕТНАЯ МАТЕМАТИКА Циклические коды Белоусов Иван Николаевич Институт радиоэлектронники и информационных технологий Уральский федеральный университет 13 апреля 2020 Линейные коды Источник (или отправитель) генерирует сообщение, представляющее собой последовательность из k символов. Кодер переводит это сообщение в кодовое слово, представляющее собой последовательность из n ≥ k символов, которое передается по зашумленному каналу связи. Далее, декодер восставливает с наибольшей вероятностью из полученного "испорченного" кодового слова первоначальное и передает соответствущее сообщение получателю. Источник Кодер Канал Получатель Декодер Рис. 1 Шум Линейное кодирование над полем F = Fq , q = pn состоит в линейном отображении ε : F k → F n , k < n. Сообщение ~a = a1 a2 . . . ak ∈ F k переводится в кодовое слово ~x = x1 . . . xn ∈ F n . Если отображение ε взаимно-однозначно, то подпространство C = ε(F k ) имеет размерность k. Подпространство C называется линейным (n, k)-кодом. Дадим более общее определение. Определение 33. Линейным (n, k)-кодом C, n ≥ k, над полем F называется любое подпространство размерности k линейного пространства F n . Функция ε является кодером. Если n = 2, то код C называют бинарным, а если n = 3, то тернарным кодом. Информационной скоростью кода C называется отношение k/n. Определение 34. Если ~e1 , . . . ,~ek - естественный базис F k , то ε(~ei ) = (xi1 . . . xi1 ) и матрица G = (xij ) размера k × n со строками ε(ei ) называется порождающей матрицей кода C. Вообще, порождающей матрицей кода C называется матрица размера k × n ранга k, строки которой порождают линейное пространство C. Существует k линейно независимых столбцов в матрице G. Отвечающие этим столбцам координаты вектора ~x назывют информационными, а остальные — проверочными. Чаще всего линейно независимыми столбцами будут именно первые k столбцов. Пусть ~a = (a1 , a2 . . . ak ) ∈ Fk — передавемое сообщение. Тогда соответствующее ему кодовое слово в линейном (n, k)-коде C равно ~x = (x1 , x2 , . . . , xn ) = ~aG (1) Определение 35. Матрица вида (Ek | A), где Ek — единичная матрица размера k. называется канонической порождающей матрицей линейного кода C. Для такой матрицы координаты x1 , x2 , . . . , xk — информационные, а координаты xk+1 , xk+2 , . . . , xn — проверочные. Определение 36. В пространстве F n можно задать скалярное произвдение (~x,~y) = x1 y1 + . . . + xn yn для ~x = x1 . . . xn , ~y = y1 . . . yn Тогда коду C отвечает код C∗ = {~y ∈ F n | ∀~x ∈ C (~x,~y) = 0}, являющийся ортогональным дополнение пространства C в пространстве F n . Код C∗ называется дуальным или двойственным к C. Порождающая матрица Hm×n , где m = n − k, кода C∗ называется проверочной матрицей кода C. Из определения вытекает, что C = {~x ∈ F n | H~x T = ~0}. и проверочной матрицей кода C∗ является порождающая матрица G кода C. Определение 37. Если H = (hij ), i ∈ {1, . . . , m}, j ∈ {1, . . . , n}, то H~x T  P n h x  j=1 1j j  n  P  h2j xj =  j=1   n ...  P hmj xj        =       0  . ...  j=1 Уравнения n X j=1 hij xj = 0, i ∈ {1, . . . , m}, называются проверочными. Определение 38. Матрица H = (B | En−k ) называется канонической проверочной матрицей. Ясно, что канонической порождающей матрице G = (Ek | A) кода C отвечает каноническая проверочная матрица H = (−AT | En−k ) этого кода. Напомним, что эквивалентными преобразованиями матрицы над некоторым полем F называется (1) перестановка двух строк; (2) умножение строки на ненулевой элемент поля F; (3) прибавление (вычитание) к одной строке другой, умноженной на элемент из F. Две матрицы A и B называются эквивалентными (обозначается A ∼ B), если одну из другой можно получить эквивалентными преобразованиями. Из определения проверочной H и порождающей G матриц кода C следует, что матрицы H 0 , G0 такие, что H 0 ∼ H, G0 ∼ G, тоже являются соответственно проверочной и порождающей матрицами кода C. Таким образом, порождающую или проверочную матрицы можно эквивалентными преобразованиями привести к каноническому виду. Иногда кроме эквивалентных преобразований проверочной и порождающей матриц линейного кода мы будем использовать еще одно преобразование — перестановку столбцов. Этому преобразованию соответствует перестановка соответствующих символов в кодовых словах данного кода. Определение 39. Расстоянием Хэмминга d(~x,~y) между векторами ~x, ~y ∈ Fnq называется число координат, которым различаются ~x и ~y. Весом Хэмминга w(~x) вектора ~x называется число d(~x, 0), т.е. число ненулевых символов в слове ~x. Минимальным расстоянием кода C называется число dmin (C) = min d(~u,~v). ~ u,~ v∈C u6=v Обозначим через Ai количество кодовых слов веса i. Множество {A0 , A1 , . . . , An } называется весовым спектром данного кода. Ясно, что dmin = min w(~u). ~ u∈C ~ u6=~ Линейный (n, k)-код с минимальным расстоянием d = dmin называют еще (n, k, d)-кодом. Определение 40. Пусть H — проверочная матрица линейного (n, k)-кода C. Тогда вектор S(~y) = H~y T называется синдромом вектора ~y. Определение 41. Если при передаче кодового слова ~x получен вектор ~y, то разность ~e = ~y − ~x = e1 . . . en называется вектором ошибок (ошибкой). В случае линейного кода ~y ∈ C ⇔ ~e ∈ C. Очевидно, что S(~y) = 0 ⇔ ~y ∈ C. Декодер должен преобразовать ~y в некоторое кодовое слово ~x и затем отправить сообщение ε−1 (~x) получателю. Обычно ведется ”декодирование по методу максимального правдоподобия”, т.е. ~y декодируется в такое ~x ∈ C так, что вес w(~e) ошибки ~e = ~y−~x минимален. Мы будем считать, что сообщения передаются по двоичному симметричному каналу, т.е. вероятность правильной передачи каждого символа кодового слова одинакова и равна p, а неправильной передачи равна q = 1 − p. Пусть по двоичному симметричнову каналу было послано кодовое слово ~x ∈ F n , а получено — слово ~y ∈ F n . Тогда вероятность того, что при передаче этого кодового слова t символов были переданы неверно, т.е. w(~e) = t для ~e = ~y − ~x, равна n n n! Qt = pn−t qt , где = . t t (n − t)!t! Вероятность ошибочного декодирования Определение 42. Говорят, что код C обнаруживает s ошибок, если при условии w(~e) ≤ s декодер выдает сообщение об ошибке. Говорят, что код C исправляет s ошибок, если при условии w(~e) ≤ s декодер находит ошибку ~e, т.е. по полученному слову ~y определяет переданное кодовое слово ~x = ~y − ~e. Пусть код C исправляет s ошибок. Тогда для вероятности Q ошибочного декодирования по методу максимального правдоподобия, т.е. для вероятности того, что произошло s + 1 или s + 2 или . . . n P n ошибок, справедливо Q ≤ Qt . А для вероятности правильt=s+1 ного декодирования, т.е. для вероятности того, что не произошло ошибок или произошла одна или две или . . . s ошибок справедливо s P P≥ Qt . t=0 Аналогичные оценки для вероятностей пропуска или обнаружения ошибки можно получить при условии, что код код C обнаруживает s ошибок. Обозначим через [x] целую часть числа x ≥ 0. Теорема 43. Линейный (n, k, d)-код C обнаруживает d − 1 ошибок и исправляет   d−1 ошибок. 2 Декодирование при помощи лидеров Множество F n можно разбить на попарно непересекающиеся смежные классы ~ei + C, где ~e1 ,~e2 , . . . ,~eqm ∈ F n , ~e1 = ~0 и ~ei + C = {~y ∈ F n | ~y = ~e + ~x для некоторого ~x ∈ C}. Итак, F n = C ∪ (~e2 + C) ∪ (~e3 + C) ∪ . . . ∪ (~eqm + C). Известно, что ~y1 + C = ~y2 + C ⇔ ~y1 ∈ ~y2 + C ⇔ ~y1 − ~y2 ∈ C ⇔ S(~y1 ) = S(~y2 ). Вектор ~e ∈ ~ei + C минимального веса называется лидером смежного класса ~ei + C. Декодирование по методу максимального правдоподобия для линейных кодов является "декодированием при помощи лидеров"и заключается следующем. Произвольный вектор ~y ∈ F n декодируется в такое кодовое слово ~x, что слово ~e = ~y − ~x является одним из лидеров смежных классов, т.е. S(~y) = S(~e). Зафиксируем лидеры ~e1 ,~e2 , . . . ,~eqm в смежных классах, ~e1 = ~0. Если лидеров в некотором классе несколько, то фиксируется произвольный из них. Расположим все векторы из Fqn в виде таблицы: ~x1 = ~0 ~e2 ... ~eqm лидеры смежных классов ~x2 ~e2 + ~x2 ... ~eqm + ~x2 ... ... ... ... ~xqk ~e2 + ~xqk ... ~eqm + ~xqk — кодовые слова — отличные от C смежные классы Полученный вектор ~y надо найти в таблице. Пусть ~y = ~ei +~xj . Тогда ошибка ~e совпадает с лидером ~ei и ~y декодируется в кодовое слово ~x = ~y − ~e = ~xj . При этом ~x является верхним словом в столбце таблицы, содержащем ~y. Заметим, что таблица не нужна, а вектор ошибок ~e — это единственный лидер, имеющий тот же синдром, что и ~y. Код Хэмминга Определение 44. Бинарный код C длины n = 2m − 1, m ≥ 2, с проверочной m × (2m − 1) матрицей H, i-м столбцом которой служит двоичная запись числа i длины m, называется бинарным кодом Хэмминга. Удлиненным кодом Хэмминга называется (2m , 2m − 1 − m)-код C, полученный из (2m − 1, 2m − 1 − m)-кода Хэмминга добавлением одного символа x2m к кодовым словам кода Хэмминга и добавление одного проверочного уравнения x1 + x2 + . . . + x2m = 0 (проверкой на четность). Симплексный код — это (2m − 1, m)-код C∗ , дуальный к (2m − 1, 2m − 1 − m)-коду Хэмминга C, а код ∗ Рида-Малера первого порядка — это (2m , m + 1)-код C , дуальный m m к удлиненному (2 , 2 − 1 − m)-коду C Хэмминга. Теорема 45. Минимальное расстояние (2m − 1, 2m − 1 − m)-кода Хэмминга C равно 3, а минимальное расстояние его удлинненого (2m , 2m − 1 − m)-кода C равно 4. Минимальное расстояние симплексного (2m − 1, m)-кода C∗ и (2m , m + 1)-кода Рида-Малера ∗ первого порядка C равно 2m−1 . Задача 4.   1 1 0 0 0 Пусть G =  1 0 1 0 1  — порождающая матрица 1 0 0 1 0 бинарного линейного (5,3)-кода. Найти для этого кода проверочную матрицу, все кодовые слова, а также дуальный код. Найти весовые спектры этих кодов. Выписать все синдромы и лидеры смежных классов и декодировать при помощи лидеров слово 11010. Решение. Для данного кода C длина сообщений k = 3, длина кодовых слов n = 5 и m = n − k = 2. Приведем матрицу G эквивалентными преобразованиями над полем F2 к каноническому виду G0 = (E3 | −AT ), где A ∈ (F2 )2×3 . Тогда H = (A | E2 ) является каноническим видом проверочной матрицы кода C. Под матрицей будем записывать ее эквивалентные преобразования, обозначая строки матрицы римскими цифрами.  1 G= 1 1 1 1  1  ∼ 1     1 1 1 1 II−I, III−I  ∼    1 1 1 1 I−II 1 1 1 1     ∼ III−II 1      ∼ 1 0 0 G0 =  0 1 0 0 0 1 E3 | 0 | 0 | 1  1 1  −AT   1 1  , следовательно,   0 0 1 T T T T A = −(−A ) = (−A ) = , 1 1 0   0 0 1 1 0 H= . 1 1 0 0 1 Таким образом, −AT =  0 1 Пусть ~a = (a1 , a2 , a3 ), где a1 , a2 , a3 ∈ F2 , — сообщение, тогда по формуле (1) соответствующее кодовое слово равно ~x = (x1 , x2 , x3 , x4 , x5 ) = ~aG0 = (a1 , a2 , a3 , a3 , a1 + a2 ). Приведем таблицу всевозможных сообщений и соответствующих кодовых слов. ~a ~x 000 00000 001 00110 010 01001 011 01111 100 10001 101 10111 110 11000 Таким образом, C = {00000, 00110, 01001, 01111, 10001, 10111, 11000, 11110}. 111 11110 Запишем таблицу лидеров ~ei и соответствующих смежных классов ~ei + C. Напомним, что S(~y) = S(~ei ), если y ∈ ~ei + C и S(~ei ) 6= S(~ej ) для i 6= j. Число лидеров (смежных классов) равно 2n /|C| = 2n /2k = 2m = 4. Заполнение таблицы происходит следующим образом: сначала выписываем все кодовые слова ~x1 , ~x2 , ~x3 , ~x4 , ~x5 , ~x6 , ~x7 ~x8 , (первая строка таблицы). Очевидно, S(~xj ) = (0, 0)T . Затем выбираем лидеры ~e1 , ~e2 , ~e3 , ~e4 cмежных классов, так, чтобы их вес был как можно меньше и S(~ei ) 6= S(~ej ) для i 6= j. Векторы из F52 наименьшего веса — суть ~x1 = 00000, w ~ 1 = 00001, w ~ 2 = 00010, ~ 3 = 00100, w ~ 4 = 01000, w ~ 5 = 10000. w Посчитаем их синдромы: S(~x1 ) = (0, 0)T , S(~ w1 ) = S(~ w4 ) = S(~ w5 ) = (0, 1)T , T S(~ w2 ) = S(~ w3 ) = (1, 0) . ~ 1 , ~e3 = w ~ 2 . Оставшийся лидер e4 Возьмем в качестве ~e1 = ~x1 , ~e2 = w ~ 3, w ~ 4, w ~ 5 выбирать нельзя. Теперь рассмотрим вектора из векторов w из F52 веса два и выберем среди них вектор ~e4 такой, что S(~e4 ) 6∈ {S(~e1 ), S(~e2 ), S(e3 )}, т.е. S(~e4 ) = (1, 1)T . В качестве ~e4 можно взять, например, вектор 00011. Итак, имеем следующую таблицу лидеров и их синдромов ~ei S(~ei ) 00000 (0, 0)T 00001 (0, 1)T 00010 (1, 0)T 00011 (1, 1)T Запишем лидеры в первый столбец таблицы лидеров и их смежных классов. Элемент, стоящий в i-й строке и j-м столбце таблицы равен ~yij = ~ei +~xj . Таким образом, i-я строка таблицы представляет собой смежный класс ~ei + C. 00000 00001 00010 00011 00110 00111 00100 00101 01001 01000 01011 01010 01111 01110 01101 01100 10001 10000 10011 10010 10111 10110 10101 10100 11000 11001 11010 11011 11110 11111 11100 11101 Синдром слова ~y = 11010, которое нужно декодировать, равен S(~y) = (1, 0)T = S(~e3 ), т.е. ~y ∈ ~e3 + C, а именно, слово ~y находится в 3-й строке и 7-м столбце. Следовательно, с наибольшей вероятностью передано слово ~x3 = ~y − ~e3 = 11000. Соответствующее сообщение представляет собой слово ~a = 110. Найдем дуальный (5,2)-код C∗ . Порождающей матрицей G∗ для этого кода является матрица H, а проверочной матрицей — матрица G. Как и выше приведем матрицу G∗ элементарными преобразованиями и над F2 к каноническому виду G∗0 = (E2 | − A∗T ). Столбцы матриц будем обозначать арабскими цифрами.     1 1 0 0 1 0 0 1 1 0 ∼ G∗ = ∼ 0 0 1 1 0 1 1 0 0 1 I↔II ∼ G∗0 =  1 (2)↔(3) 1 E2 | 1 | 0 1 −A∗T 1  Если ~a∗ = (a∗1 , a∗2 ) — сообщение, тогда соответсвующее кодовое слово из дуального кода по формуле (1) равно ~x∗ = (x1∗ , x2∗ , x3∗ , x4∗ , x5∗ ) = ~a∗ G0 = (a1 , a2 , a1 , a2 , a1 ). Приведем таблицу всевозможных сообщений и соответствующих кодовых слов для кода C∗ . ~a∗ ~x∗ 00 00000 01 01010 10 10101 11 11111 Таким образом, C∗ = {00000, 01010, 10101, 11111}. Найдем весовые спектры кодов C = {~x1 ,~x2 ,~x3 ,~x4 ,~x5 ,~x6 ,~x7 ,~x8 } и C∗ = {~x1∗ ,~x2∗ ,~x3∗ ,~x4∗ }. Находим веса слов этих кодов: w(~x1 ) = 0, w(~x2 ) = w(~x3 ) = w(~x5 ) = w(~x7 ) = 2, w(~x4 ) = w(~x6 ) = w(~x8 ) = 4, w(~x1∗ ) = 0, w(~x2∗ ) = 2, w(~x3∗ ) = 3, w(~x4∗ ) = 5. Отсюда имеем следующие весовые спектры для кодов C и C∗ : A0 = 1, A2 = 4, A4 = 3, A1 = A3 = A5 = 0; A∗0 = A∗2 = A∗3 = A∗5 = 1, A1 = A4 = 0. Ответ 1. C = {00000, 00110, 01001,   01111, 10001, 10111, 11000, 11110}; 0 0 1 1 0 H= ; C∗ = {00000, 01010, 10101, 11111}; A0 = 1, 1 1 0 0 1 A2 = 4, A4 = 3, A1 = A3 = A5 = 0, A∗0 = A∗2 = A∗3 = A∗5 = 1, A1 = A4 = 0; 11000(110). Задача 5. Найти порождающую матрицу, все кодовые слова и весовой спектр для линейного тернарного (4,2)-кода с проверочной   0 1 1 1 матрицей H = . Выписать все синдромы и лидеры 1 1 2 1 смежных классов и декодировать при помощи лидеров слово 2001. Оценить вероятность правильного декодирования. Решение. Эквивалентными преобразованиями над F3 приведем порождающую матрицу H кода C к каноническому виду H 0 = (A | E2 ), где A ∈ (F3 )2×2 . Напомним, что в поле F3 справедливо следующее: −1 = 2, −2 = 1, 2 + 2 = 1, 2 + 1 = 0, 2 · 2 = 1, 2−1 = 2.  H= 1 | 1 | 2 1 1 1 1   ∼  1 | 2 | 1 1 1 I↔II,  ∼  2 2 1 | 1 | 1 ∼ 2 2 2 1 | 1 | 0 I−2·II   ∼ 2−1 ·I 2 1    ∼  2 1 | 1 | 0 2 2 2 2   ∼ 2−1 ·II II−I  1 1 2 1  ∼ H0 =  1 2 1 A | 1 | 0 E2 1      1 0 1 0 | 2 1 , G = (E2 | −AT ) = . 2 1 0 1 | 0 2 Пусть ~a = (a1 , a2 ), где a1 , a2 ∈ F3 — некоторое сообщение, тогда соответствующее кодовое слово равно ~x = (x1 , x2 , x3 , x4 ) = ~aG = (a1 , a2 , 2a1 , a1 +2a2 ). И мы имеем следующее соответствие сообщений и кодовых слов. Значит, ~a ~x 00 0000 A= 01 0102 02 0201 10 1021 11 1120 12 1222 20 2012 21 2111 22 2210 Выберем, подобно тому как мы это делали в задаче 4, лидеры ~e1 , ~e2 . . ., ~e9 смежных классов. ~ei 0000 0001 0010 1000 0002 0020 2000 0011 1010 S(~ei ) (0, 0)T (0, 1)T (1, 0)T (1, 2)T (0, 2)T (2, 0)T (2, 1)T (1, 1)T (2, 2)T Теперь напишем таблицу лидеров и соответствующих смежных классов. Как и в задаче 4 первая строка — это множество всех кодовых слов, первый столбец — множество всех лидеров, i-я строка представляет собой смежный класс ~ei + C, а элемент, стоящий на пересечении i-й строки и j-го столбца равен ~yij = ~ei + ~xj . 0000 0001 0010 1000 0002 0020 2000 0011 1010 0102 0100 0112 1102 0101 0122 2102 0110 1112 0201 0202 0211 1201 0200 0221 2201 0212 1211 1021 1022 1001 2021 1020 1011 0021 1002 2001 1120 1121 1100 2120 1122 1110 0120 1101 2100 1222 1220 1202 2222 1221 1212 0222 1200 2202 2012 2010 2022 0012 2011 2002 1012 2020 0022 2111 2112 2121 0111 2110 2101 1111 2122 0121 2210 2211 2220 0210 2212 2200 1210 2221 0220 Слово ~y = 2001 лежит в 9-й строке и 4-м столбце, следовательно, с наибольшей вероятностью оно декодируется в кодовое слово ~x4 = ~y − ~e9 = 2001 − 1010 = 1021, которое соответствует сообщению 11. Минимальное расстояние кода dmin (C) = 3. Значит, код C обнаруживает s = dmin (C) − 1 = 2 ошибки и исправляет t = [(dmin (C) − 1)/2] = 1 ошибку (теорема 43). Следовательно, для вероятности P правильного декодирования (вероятности того, что не произошло ошибок или произошла одна ошибка) справедливо P≥ t   X n i=0 i p     5 5 5 q = p + p4 q = p5 + 5p4 q. 1 n−i i Ответ 2. C = {0000, 0101, 0202, 1021,   1122, 1220, 2012, 2110, 2210}; 1 0 | 2 1 G= ; 1021(10); P ≥ p5 + 5p4 q. 0 1 | 0 1 Задача 6. Найти проверочные и порождающие матрицы и информационные скорости для (7,4)-кода Хэминга и удлиненного (8,4)-кода Хэмминга. Сколько ошибок обнаруживают и исправляют эти коды? Декодировать слова 1101011 и 01011011 в коде Хэмминга и его удлиненном коде соответственно. Решение. Обозначим через H и G соответственно проверочную и порождающую матрицы кода Хэмминга C, а через H и G — проверочную и порождающую матрицы удлиненного кода Хэмминга C. Проверочная матрица (7, 4)-кода Хэмминга является бинарная матрица размера 3 × 7, i-й столбец которой есть двоичная запись числа i. Значит,   0 0 0 1 1 1 1 H= 0 1 1 0 0 1 1  1 0 1 0 1 0 1 Удлиненный (8, 4)-код получен добавлением одного символа x8 к кодовым словам кода Хэмминга и добавление одного проверочного уравнения x1 + x2 + . . . + x8 = 0 (проверкой на четность). Следовательно, матрица H может быть получена из H приписывание сверху строки (1, 1, 1, . . . , 1) и справа столбца (1, 0, 0, . . . , 0)T . Следовательно,   1 1 1 1 1 1 1 1  0 0 0 1 1 1 1 0   H=  0 1 1 0 0 1 1 0  1 0 1 0 1 0 1 0 Эквивалентными преобразованиями также, как и в задачах 4, 5, приводим матрицы H и H к каноническому виду H 0 = (A | E3 ), H = (A | E4 ). В результате получаем:   0 1 1 1 | 1 0 0 H0 =  1 0 1 1 | 0 1 0  1 1 0 1 | 0 0 1   0 1 1 1 | 1 0 0 0  1 0 1 1 | 0 1 0 0   H =  1 1 0 1 | 0 0 1 0  1 1 1 0 | 0 0 0 1 Следовательно,  1 0 0 0  0 1 0 0 G=  0 0 1 0 0 0 0 1  1 0 0 0 |  0 1 0 0 | G=  0 0 1 0 | 0 0 0 1 | | | | | 1 1 1 1 1 1 1 1 1 1 1 1  1 1   0  1  1 1 1 1   0 1  1 0 Строки любой порождающей матрицы, записанной в канонической форме, являются базисом пространства кодовых слов. Далее, кодовые слова удлиненного кода получаются из кодовых слов исходного кода добавлением символа проверки на четность. Следовательно, матрицу G можно было получить из G добавлением справа столбца, i-й элемент которого является сумммой всех элементов i-й строки матрицы G (проверкой на четность). Информационная скорость кода Хэмминга C равна k/n = (2m − 1)/(2m − 1 − m) = 7/3, а информационная скорость удлиненного кода Хэмминга C равна k/n = 2m /(2m − m) = 8/4 = 2. Известно, что dmin (C) = 3, dmin (C)=4 (утверждение 45), следовательно, код C обнаруживает dmin (C) − 1 = 2 ошибки и исправляет [(dmin (C) − 1)/2] = 1 ошибку, а код C обнаруживает dmin (C) − 1 = 3 ошибки и исправляет [(dmin (C) − 1)/2] = 1 ошибку (теорема 43). Слово ~y1 = 1101011 имеет синдром S1 (~y1 ) = H~yT2 = (1, 1, 0)T , который является двоичной записью числа 6, и декодер кода Хэмминга решает, что ошибка произошла в 6-й позиции. Следовательно, слову ~y соответствует кодовое слово ~x1 = ~y1 = 1101011 − 0000010 = 1101111, а соответствующее сообщение будет 110. Синдром слова ~y2 = 01011011 равен  8    1 P 1   i=1 yi   T  S2 (~y2 ) = H~y2 =  =  0 , S1 (~y) где ~y2 = y1 y2 . . . y7 y8 = 01011011, ~y = y1 y2 . . . y7 = 0101101. Следовательно, S1 (~y) = (1, 0, 0)T и ошибка в слове ~y произошла в 4-й позиции кодового слова ~x = x1 x2 . . . x7 кода Хэмминга C. Следовательно, ~x = ~y − 0001000 = 0100101. Соответствующее кодовое слово ~x удлиненного (8,4)-кода Хэмминга C равно слову x1 x2 . . . x7 x8 = 7 P 01001011, где x8 = xi = 1 — есть символ проверки на четность. i=1 Кодовому слову 01001011 соответствует сообщение 010. Ответ 3. H, G, H, G; инфомационные скорости кодов C и C равны соответственно 7/3 и 2; код C обнаруживает две ошибки и исправляет одну ошибку, а код C обнаруживает три ошибки и исправляет одну ошибку; 1101111(110), 01001011(010). Задача 7. Найти проверочные и порождающие матрицы для симплексного (7,3)-кода и (8,4)-кода Рида-Малера первого порядка. Содержат ли слова 0101101 и 11001100 в симплексном коде и в коде Рида-Малера обнаруживаемые ошибки? Оценить вероятность обнаружения ошибки для этих кодов. Решение. Обозначим через H ∗ и G∗ соответственно проверочную и ∗ ∗ порождающую матрицы симплексного кода C∗ , а через H и G — ∗ проверочную и порождающую матрицы кода Рида-Малера C (матрицы G, H, G, H, означают то же, что и в задаче 6). Тогда H ∗ = G, ∗ ∗ G∗ = H, H = G, G = H. Выясним, содержат ли слова ~y1 = 0101101, ~y2 = 11001100 обнару∗ живаемые ошибки в кодах C∗ и C : S1 (~y1 ) = H ∗~yT1 = (1, 1, 1, 1)T 6= (0, 0, 0, 0)T ∗ S2 (~y2 ) = H ~yT2 = (1, 1, 1, 1)T 6= (0, 0, 0, 0)T = (0, 0, 0, 0)T . Значит, декодер кода C∗ будет выдавать сообщение об ошибке в ∗ слове ~y1 , а декодер кода C будет считать слово ~y2 кодовым словом. ∗ Известно, что dmin (C∗ ) = dmin (C ) = 2m−1 = 4 (утверждние 45), ∗ следовательно, коды C∗ и C обнаруживают s = dmin (C∗ ) − 1 = 3 ошибки. Это означает, что для вероятностей P1 , P2 пропуска ошибки этими кодами (т.е. для вероятностей того, что произошло не более трех ошибок) справедливо P1 ≥ P2 ≥ 3 P 7 i i=0 3  P i=0
pn−1 qi = p7 + 7p6 q + 21p5 q2 + 35p4 q3  8 n−1 i q = p8 + 8p7 q + 28p6 q2 + 56p5 q3 i p Ответ 4. ∗ ∗ H ∗ = G, G∗ = H, H = G, G = H (матрицы G, H, G, H найдены в задаче 6); в слове 0101101 произошла ошибка с вероятностью P1 ≥ p7 + 7p6 q + 21p5 q2 + 35p4 q3 ; в слове 11001100 не произошла ошибка с вероятностью P2 ≥ p8 + 8p7 q + 28p6 q2 + 56p5 q3 . Циклические коды Множество F(x) всех многочленов над полем F = Fq , q = pn , можно считать как кольцом относительно опрераций умножения и сложения многочленов, так и линейным пространством над полем F = Fq относительно сложения многочленов и умножения их на элементы поля F. Выделим в пространстве F(x) подпространство Vn = {f (x) ∈ F(x) | deg f (x) < n} = = {f (x) = v0 + v1 x + · · · + vn−1 xn−1 | vi ∈ F}. Подпространство Vn имеет базис e1 (x) = 1, e2 (x) = x, . . . , en (x) = xn−1 из n элементов, поэтому его можно отождествить с пространством F n . Каждому многочлену v̄(x) = v0 +v1 x+· · ·+vn−1 xn−1 из Vn при этом отождествлении будет соответствовать вектор ~v = (v0 , v1 , . . . , vn−1 ). Определим операцию умножения ∗ на множестве Vn следующим образом: ū(x) ∗ v̄(x) = rest(ū(x) · v̄(x)/(xn − 1)) для любых ū(x), v̄(x) ∈ Vn . Можно проверить, что относительно этой опрерации и операции сложения множество Vn является ассоциативно коммутативным кольцом. Дадим два эквивалентных определения циклического кода. При этом многочлены v̄(x) из Vn и соответствующие им векторы ~v из F n мы различать не будем. Определение 46. Циклическим кодом называется подространство C пространства Vn над полем F такое, что xk ∗ v̄(x) ∈ C для любого v̄(x) ∈ C и k ∈ {1, . . . , n − 1}. Заметим, что x · v̄(x) = v0 x + v1 x2 + · · · + vn−1 xn и поэтому x ∗ v̄(x) = rest(x · v̄(x)/(xn − 1)) = vn−1 + v0 x + v1 x2 + . . . + vn−2 xn−1 . Аналогично, x2 ∗ v̄(x) = vn−2 + vn−1 x + v0 x2 + . . . + vn−3 xn−1 и т.д. Наконец, xn−1 ∗ v̄(x) = v1 + v2 x + v0 x2 + . . . + vn−1 xn−1 + v0 xn−1 . Циклическим сдвигом называется отображение z из F n в F n , которое каждому вектору ~v = v0 v1 . . . vn−1 ставит в соответствие вектор z(~v) = vn−1 v0 . . . vn−2 . Из выше приведенных вычислений вытекает второе определение. Определение 47. Циклическим кодом называется подространство C пространства F n над полем F, замкнутое относительно циклического сдвига, т.е. для любого вектора ~v из C вектор z(~v) тоже принадлежит C. Для многочлена g(x) ∈ Vn через (g(x)) обозначим множество {g(x) ∗ v̄(x) | v̄(x) ∈ Vn }. Легко понять, что множество (g(x)) замкнуто относительно операций ”+” и ”∗” и поэтому является подкольцом кольца Vn . Кроме того, оно является подпространством пространства Vn над полем F. Теорема 48. Циклическим код равен подпространству (g(x)) пространства Vn для некоторого ненулевого многочлена g(x) из Vn (его можно считать нормированным), делящего многочлен xn − 1. Нормированный многочлен g(x) называется порождающим многочленом кода C. Замечание. Пусть многочлен g(x) = g0 + g1 x + · · · + gm xm делит xn − 1 и deg(g) = m < n. Положим k = n − m. Тогда линейный (n, k) код C = (g(x)) порождается матрицей     g g0 g1 . . . gm 0 ... 0  x∗g   g0 . . . gm−1 gm . . . 0      G= = .. ... ... ... ... ... ... ...    . ... ... ... g0 . . . . . . gm xk−1 ∗ g Определение 49. Многочлен h(x) = кода C. xn − 1 называется проверочным многочленом g(x) Если h(x) = h0 + h1 x + h2 x2 + . . . + hk xk ,  hk hk−1 . . . h0  hk . . . h1  H= ... ... ... ... . . . . . . . . . hk то матрица  0 ... 0 h0 . . . 0   ... ... ...  . . . . . . h0 является проверочной матрицей данного кода. Кодирование Сообщение a = a0 a1 . . . ak−1 в циклическом коде кодер переводит в кодовое слово ~v ∈ C, где v̄(x) = ā(x) ∗ g(x). Декодирование Многочлен ū(x), соответствующий полученному слову ~u нужно разделить с остатком на g(x). Остаток от деления и есть S(~u). Если S(~u) 6= ~0, то при передаче возникла ошибка ~e, которая в циклических кодах общего вида находится при помощи лидеров смежных классов (циклические коды специального вида рассматриваются в следующем пункте). Дуальный код Теорема 50. Пусть C — циклический (n, k)-код с порождающим многочленом g(x). Тогда дуальный код C∗ является циклическим (n, n − k)-кодом с порождающим многочленом g∗ (x) = xk h(1/x) = hk + hk−1 x + . . . + h1 xk−1 + h0 xk . Циклический код и код Хэмминга Теорема 51. Бинарный циклический код длины n = 2m − 1, порождающий многочлен которого является минимальным многочленом над F2 некоторого примитивного элемента из F2m , эквивалентен бинарному (n, n − m)-коду Хэмминга. Задача 8. Найти порождающую и проверочную матрицы, а также проверочный многочлен для бинарного циклического кода порожденного многочленом g(x) = x3 + x + 1, если длина сообщений k = 4. Закодировать сообщение 1001. Содержит ли ошибку полученное по зашумленному каналу слово 1101011? Найти порождающий многочлен для дуального кода. Решение. Данный код C имеет следующие параметры k = 4, m = deg g(x) = 3, n = m + k = 7. Порождающей матрицей этого кода является матрица       1 1 0 1 0 0 0 g(x) 1 + x + x3  0 1 1 0 1 0 0   xg(x)   x + x2 + x4       G=  0 0 1 1 0 1 0  =  x2 g(x)  =  x2 + x3 + x5  0 0 0 1 1 0 1 x3 g(x) x3 + x4 + x6 x7 + 1 xn − 1 = 3 . g(x) x +x+1 Поделим "уголком" многочлен x7 + 1 на многочлен x3 + x + 1: Проверочный многочлен кода C равен h(x) = x7 + 1 x3 + x + 1 7 5 4 x +x +x x4 + x2 + x + 1 5 4 x +x +1 x5 + x3 + x2 x4 + x3 + x2 + 1 x4 + x2 + x x3 + x + 1 x3 + x + 1 Следовательно, h(x) = x4 + x2 + x + 1. Порождающий многочлен g∗ (x) для дуального кода равен (см. теорему 50) xk h(1/x) = x4 ((1/x)4 + (1/x)2 + 1/x + 1) = x4 + x3 + x2 + 1. Теперь можно записать проверочную матрицу кода C.   1 0 1 1 1 0 0 H= 0 1 0 1 1 1 0 =  ∗ 0 0 1 0 4 1 31 12  g (x) x +x +x +1  xg∗ (x)   x5 + x4 + x3 + x     =  x2 g∗ (x)  =  x6 + x5 + x4 + x2  . x3 g∗ (x) x7 + x6 + x5 + x3 Пусть ~a = a0 a1 a2 a3 — некоторое сообщение и пусть ā(x) = a0 + a1 x + a1 x2 + a1 x3 . Тогда соответствующее кодовое слово равно ~v = v0 v1 v2 v3 v4 v5 v6 , где v̄(x) = v0 + v1 x + v2 x2 + v3 x3 + v4 x4 + v5 x5 + v6 x6 , v̄(x) = ā(x) ∗ g(x) = rest (ā(x)g(x)/(xn − 1)). Пусть сообщение равно ~a = 1001, тогда ā(x) = x3 + 1. Поскольку ā(x)g(x) = (x3 + 1)(x3 + x + 1) = x6 + 6 x3 + x4 + 6 x3 + 1 = x6 + x4 + 1, то ā(x) ∗ g(x) = rest (x6 + x4 + 1)/(x7 − 1) = x6 + x4 + 1 и ~v = 1000101. Пусть ~f = 1101011. Слово ~f не содержит ошибки тогда и только тогда, когда ~f ∈ C. Кроме того, ~f ∈ C ⇔ S(~f ) = H~f T = (0, 0, 0)T и ~f ∈ C ⇔ f̄ (x) ∗ h(x) = 0. Второе условие означает, что ~f ∈ C ⇔ f̄ (x)h(x) ≡ 0( mod (x7 − 1)). Посчитаем S(~f ) = (0, 1, 0)T 6= (0, 0, 0)T , f̄ (x)g(x) = (x6 + x5 + x3 + x + 1)(x4 + x2 + x + 1) = = x10 + x9 + x8 + x7 + x5 + 1 ≡ ≡ x3 + x2 + x+ 6 1 + x5 + 6 1 ≡ x5 + x3 + x2 + x 6= 0 Следовательно, слово ~y содержит ошибку. Ответ 5.  1  0 G=  0  1 H= 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  0  , 0  1  0 0 1 0 ; 1 1 1 h(x) = x4 + x2 + x + 1; слово содержит ошибку; g∗ (x) = x4 + x3 + x2 + 1. Задача 9.   1 2 1 0 1 Дана порождающая матрица G =  2 1 0 2 0  линейного 1 0 2 1 2 (5,3)-кода над F3 . Найти проверочную матрицу этого кода. Будет ли код циклическим? Решение. Приведем матрицу G, подобно тому, как мы это делали в задаче 5 эквивалентными преобразованими над F3 к виду G0 = (E3 | −AT ).     1 2 1 0 1 1 2 1 0 1    G= 2 1 0 2 0  ∼   0 0 1 2 1  ∼ 1 0 2 1 2 0 1 1 1 1 II+I, III−I  ∼    1 2 1 1 1 1 II↔III 1 2  1 1 1     ∼    1 2 1 1 1 2 2 1 1     ∼ I+II−III II+2III   | 0 0 | 2 0  | 2 1 1 0 0 ∼ G0 =  0 1 0 0 0 1 −AT E3 Значит, A = −(−AT )T =  1 1 2   , H = (A | E3 ) = 1 1 2 1 1  . Пусть ~a = (a1 , a2 ), где a1 , a2 ∈ F3 — некоторое сообщение, тогда соответствующее кодовое слово равно ~v = (v1 , v2 , v3 , v4 ) = ~aG = (a1 , a2 , a3 , 2a2 + 2a3 , a3 ). И мы имеем следующее соответствие сообщений и кодовых слов. ~a ~v 000 00000 001 00121 002 00212 010 01020 011 01111 012 01202 020 02010 021 02101 ~a ~v 022 02222 100 10000 101 10121 102 10212 110 11020 111 11111 112 11202 120 12010 ~a ~v 121 12101 122 12222 200 20000 201 20121 202 20212 210 21020 211 21111 212 21202 ~a ~v 220 22010 221 22101 222 22222 Таким образом, C = {~v1 ,~v2 , . . . ,~v27 }, где v̄1 (x) = 0, v̄3 (x) = 2x2 + x3 + x4 , v̄5 (x) = x + x2 + x3 + x4 , v̄7 (x) = 2x + x3 , v̄9 (x) = 2x + 2x2 + 2x3 + 2x4 , v̄11 (x) = 1 + x2 + 2x3 + x4 , v̄13 (x) = 1 + x + 2x2 , v̄15 (x) = 1 + x + 2x2 + 2x4 , v̄17 (x) = 1 + 2x + x2 + x4 , v̄19 (x) = 2, v̄21 (x) = 2 + 2x2 + x3 + 2x4 , v̄23 (x) = 2 + x + x2 + x3 + x4 , v̄25 (x) = 2 + 2x + x3 , v̄27 (x) = 2 + 2x + 2x2 + x3 + 2x4 . v̄2 (x) = x2 + 2x3 + x4 , v̄4 (x) = x + 2x3 , v̄6 (x) = x + 2x2 + 2x4 , v̄8 (x) = 2x + x2 + x4 , v̄10 (x) = 1, v̄12 (x) = 1 + 2x2 + x3 + 2x4 , v̄14 (x) = 1 + x + x2 + x3 + x4 , v̄16 (x) = 1 + 2x + x3 , v̄18 (x) = 1 + 2x + 2x2 + 2x3 + 2x4 , v̄20 (x) = 2 + x2 + x3 + x4 , v̄22 (x) = 2 + x + 2x3 , v̄24 (x) = 2 + x + 2x2 + 2x4 , v̄26 (x) = 2 + 2x + x2 + x4 , Линейный код C будет циклическим, тогда и только тогда, когда xk ∗ v̄j (x) ∈ C для любых i ∈ 1, . . . , 27, j ∈ {1, . . . , 2}. Однако x v̄2 (x) = x3 + 2x4 + x5 ≡ 1 + x3 + 2x4 ( mod (x5 − 1)), т.е. x ∗ v̄2 (x) = 1 + x3 + 2x4 6∈ C, следовательно, код C не является циклическим. Ответ  6. H= 1 1 2 1 1  ; код C не является циклическим. Задача 10. Найти порождающий и проверочный многочлен бинарного циклического (7, 4)-кода, эквивалентного (7, 4)-коду Хэмминга. Декодировать слово 1101101 в этом циклическом коде. Решение. (n, n − m)-коду Хэмминга C1 , n = 2m − 1, эквивалентен бинарный циклический код C2 , порождающим многочленом которого является любой примитивный многочлен g(x) степени m (теорема 51). В нашем случае n = 7, m = 3. Из таблицы примитивных бинарных многочленов выберем какой-нибудь примитивный бинарный многочлен степени 3, например, g(x) = x3 + x + 1. Проверочным многочленом кода C2 является многочлен h(x) = (x7 −1)/(x3 +x+1) = x4 + x2 + x + 1, а порождающим многочленом дуального кода — многочлен g∗ (x) = xdeg h(x) h(1/x) = x4 +x3 +x2 +1. Запишем проверочную матрицу кода C2 :    ∗  1 0 1 1 1 0 0 g (x) H2 =  0 1 0 1 1 1 0  =  xg∗ (x)  0 0 1 0 1 1 1 x2 g∗ (x) Проверочной матрицей кода C1 является матрица   0 0 0 1 1 1 1 H1 =  0 1 1 0 0 1 1  . 1 0 1 0 1 0 1 Матрица H2 из матрицы H1 , равно как и матрица H1 из H2 , может быть получена перестановкой столбцов. При этом если H1 = (~b1~b2~b3~b4~b5~b6~b7 ), где ~bi — i-й столбец матрицы H1 , то H2 = (~b4~b2~b5~b6~b7~b3~b1 ), и если H2 = (~c1~c2~c3~c4~c5~c6~c7 ), где ~cj — j-й столбец матрицы H2 , H1 = (~c7~c2~c6~c1~c3~c4~c5 ). Слову ~y = y1 y2 y3 y4 y5 y6 y7 = 1101101, полученному по зашумленному каналу кода C2 соответствует слово ~z = y7 y2 y6 y1 y3 y4 y5 = 1101011. Декодируем его в коде Хэмминга C1 . Синдром S(~z) = H1~zT = (1, 0, 1)T является двоичной записью числа 5, и декодер считает, что ошибка произошла в 5-й позиции, т.е. слову ~z в коде C1 соответствует слово ~x = x1 x2 x3 x4 x5 x6 x7 = 1101111. Следовательно, слову ~y в коде C2 соответствует слово ~v = x4 x2 x5 x6 x7 x3 x1 = 1111101. Ответ 7. g(x) = x3 + x + 1; h(x) = x4 + x2 + x + 1; 1111101. БЧХ-коды Определение 52. Пусть d, n, q ∈ N, где 2 ≤ d ≤ n, q — степень простого числа p. Пусть, далее ξ — примитивный элемент поля Fqm над Fqm , g(x) — минимальный многочлен элемента ξ над Fq и g(x) делит xn − 1. БЧХ-кодом с конструктивным расстоянием d называется циклический код C над Fq , определяемый любым из следующих эквивалентных условий (1) ~v ∈ C ⇔ v̄(ξ i ) = 0 для всех i ∈ {1, 2, . . . , d − 1}. (2) Многочлен g(x) = HOK {Mi (x) | Mi (x) — минимальный многочлен элемента ξ i , i ∈ {1, 2, . . . , d − 1} является порождающим многочленом кода C. Здесь HOK — наименьшее общее кратное. Определение 52. (3) Матрица  1  1 H=  1 ξ ξ2 ξ d−1 ξ2 ξ4 ... ξ 2(d−1) ... ... ξ n−1 ξ 2(n−1) ... ξ (d−1)(n−1)     является проверочной матрицей кода C. Здесь символ ξ i обозначает столбец координат (c0 , c1 , . . . , cm−1 )T вектора ξ i в пространстве Fqm , т.е. ξ i = c0 + c1 ξ + . . . + cm−1 ξ m−1 . Теорема 53. Пусть ξ — примитивный элемент поля Fqn над Fq и минимальный многочлен g(x) для ξ над Fq делит xn − 1, а ξ 1 , ξ 2 , . . . , ξ d−1 - корни g(x). Тогда для БЧХ-кода C, отвечающего этим корням минимальное расстояние dmin не меньше конструктивного расстояния d. Определение 54. Кодом Рида-Соломона называется БЧХ-код над Fq длины n = q − 1. Для кода Рида-Соломона имеем m = 1. Теорема 55. Минимальное расстояние кода Рида-Соломона равно d. Алгоритм декодирования БЧХ-кодов. Допустим, что при использовании БЧХ-кода с конструктивным рас~. стоянием d было передано кодовое слово ~v, а получено — слово w Тогда по теореме 43 при передаче возникло не более t = [(d − 1)/2] ошибок. ~: Шаг 1. Найти синдром слова w S(~ w) = H~ wT = (S1 , S2 , . . . , Sd−1 )T = (w̄(ξ), w̄(ξ 2 ), . . . , w̄(ξ d−1 ))T . Шаг 2. Определить максимальное число  Sr Sr−1 . . .  Sr+2 Sr ...   ... ... ... S2r−1 S2r−1 . . . r ≤ t такое, что матрица  S1 S2   ...  Sr не вырождена. Это будет обозначать, что при передаче произошло r ошибок. Решить систему      Sr Sr−1 . . . S1 τ1 Sr+1  Sr+2     Sr . . . S2     τ2  = −  Sr+2   ...  ...  ... ... ...  ...  S2r−1 S2r−1 . . . Sr τr S2r+1 Решая эту систему относительно τi , образовать многочлен локаторов ошибок r X σ(x) = τi xi , i=0 где τ0 = 1. Шаг 3. Решить уравнение σ(x) = 0 в поле Fq , подставляя вместо x степени ξ. При этом σ(ξ −i ) = 0 ⇔ ( i − ~ ei 6= 0). w ~ произошло более Если многочлен σ(x) не имеет корней, то в слове w ~. t ошибок, и декодер не может распознать слово w Шаг 4. S(~ w) = S(~e) = H~eT = (ē(ξ), ē(ξ 2 ), . . . , ē(ξ d−1 ))T , следовательно, Sj = ē(ξ j ) = n−1 X ei ξ ij , j ∈ {1, 2, . . . , d − 1}. i=0 Из последних (d − 1) соотношений найти вектор ~e = e0 , e1 , . . . , en−1 . ~ соответствует кодовое слово ~v = w ~ − ~e. Шаг 5. Слову w Задача 11. Пусть ξ — примитивный элемент поля F32 , ξ 2 + ξ + 2 = 0. Найти порождающий и проверочный многочлены, а также порождающую и проверочную матрицы тернарного БЧХ-кода длины 8, исправляющего две ошибки. Декодировать слово 12201010. Решение. Опишем сначала поле F32 , полученного из поля F3 при помощи корня ξ примитивного многочлена f (x) = x2 + x + 2 (см. задачу ??): ξ0 ξ1 ξ2 ξ3 ξ4 ξ5 ξ6 ξ7 ξ8 = 1, = ξ, = 2ξ + 1 = ξξ 2 = 2ξ 2 + ξ = 2(2ξ + 1) + ξ = 5ξ + 2 = 2ξ + 2, = ξξ 3 = 2ξ 2 + 2ξ = 2(2ξ + 1) + 2ξ = 6ξ + 2 = 2, = ξξ 4 = 2ξ, = ξξ 5 = 2ξ 2 = 2(2ξ + 1) = 4ξ + 2 = ξ + 2, = ξξ 6 = ξ 2 + 2ξ = (2ξ + 1) + 2ξ = 4ξ + 1 = ξ + 1, = ξξ 7 = ξ 2 + ξ = (2ξ + 1) + ξ = 3ξ + 1 = 1. Напомним, что мультипликативная группа F∗32 поля F32 равна {1, ξ, ξ 2 , ξ 3 , ξ 4 , ξ 5 , ξ 6 , ξ 7 } и ξ j = ξ rest (j/8) для любого j ∈ N ∪ {0}. Проверочная матрица данного БЧХ-кода C имеет вид  1 ξ ξ2 ξ3 . . . ξ (n−1) 2 4 6  1 ξ ξ ξ . . . ξ 2(n−1) H=  ... ... ... ... ... ... 1 ξ d−1 ξ 2(d−1) ξ 3(d−1) . . . ξ (d−1)(n−1)   ,  где d — конструктивное расстояние этого кода, n = 3deg f (x) −1 = 8, и для любого i ∈ N символ ξ i есть сокращенная запись координатного столбца элемента ξ i по базису 1, ξ линейного пространства F32 над F3 . Поскольку код C исправляет t = 2 ошибок, то dmin (C) = 2t + 1 = 5 и значит d ≤ dmin (C), т.е. d ≤ 5. Поэтому достаточно взять d = 5. Следовательно,   1 ξ ξ2 ξ3 ξ4 ξ5 ξ6 ξ7  1 ξ 2 ξ 4 ξ 6 ξ 8 ξ 10 ξ 12 ξ 14   H=  1 ξ 3 ξ 6 ξ 9 ξ 12 ξ 15 ξ 18 ξ 21  1 ξ 4 ξ 8 ξ 12 ξ 16 ξ 20 ξ 24 ξ 32 Порождающим многочленом кода C является многочлен g(x) = HOK{Mi | i ∈ {1, 2, 3, 4}}, где Mi — минимальный многочлен элемента ξ i поля F32 . Ясно, что M1 (x) = f (x) = x2 + x + 2. Далее, M1 (ξ 2 ) = ξ 4 +ξ 2 +2 = 2+(2ξ +1)+2 = 2ξ +2 6= 0, следовательно, M2 (x) 6= M1 (x). Минимальный многочлен элемента ξ 2 можно находить так, как мы это делали в задаче 2 (см. лекции по конечным полям), а можно выбрать его из неприводимых многочленов степеk ни k, где k — наименьшее натуральное, для которого (ξ 2 )3 = ξ 2 . В 2 силу (ξ 2 )3 = ξ 6 6= ξ 2 , (ξ 2 )3 = ξ 18 = ξ 2 , k = deg M2 (x) = 2. Непосредственной проверкой убеждаемся, что M2 (x) = x2 + 1. Для элемента ξ 3 имеем M1 (ξ 3 ) = ξ 6 + ξ 3 + 2 = (ξ + 2) + (2ξ + 2) + 2 = 0, следовательно M3 (x) = M1 (x). Подставляя элемент ξ 4 = 2 в многочлены M1 (x), M2 (x), убеждаемся, что M1 (ξ 4 ) 6= 0, M2 (ξ 4 ) 6= 0, значит M4 (x) 6= M1 (x), M4 (x) 6= M2 (x). Так как (ξ 4 )3 = ξ 12 = ξ 4 , имеем deg M4 (x) = 1. Очевидно, M4 (x) = x − 2 = x + 1. Итак, M1 (x) = M3 (x) = x2 + x + 2, M2 (x) = x2 + 1, M4 (x) = x + 1. Значит, порождающий многочлен кода C равен g(x) = M1 (x)M2 (x)M4 (x) = (x2 + x + 2)(x2 + 1)(x + 1) = = x5 + 2x4 + x3 + x2 + 2. Теперь можно написать  2 0 1 G= 0 2 0 0 0 2  порождающую матрицу кода C:    1 2 1 0 0 g(x) 1 1 2 1 0  =  xg(x)  = 0 1 1 2 1 x2 g(x)  2 + x2 + x3 + 2x4 + x5 =  2x + x3 + x4 + 2x5 + x6  . 2x2 + x4 + x5 + 2x6 + x7 Деля "уголком" многочлен xn − 1 = x8 − 1 на многочлен g(x) над F3 , получаем проверочный многочлен кода C h(x) = x3 + x2 + 1. Для любого слова ~v из F83 справедливо ~v ∈ C ⇔ H~vT = 0 ⇔ (v̄(ξ i ) = 0, i = 1, 2, 3, 4). Кроме того, ввиду минимальности многочленов Mi (x), v̄(ξ i ) = 0 ⇔ Mi (x) | v̄(x). Поскольку M1 (x) = M3 (x), то v̄(ξ) = 0 ⇔ v̄(ξ 3 ) = 0. Таким образом, ~v ∈ C ⇔ H 0~vT = 0 ⇔ (v̄(ξ i ) = 0, i = 1, 2, 4), где матрица H 0 получена из матрицы H вычеркиванием 3-й строки. И матрицу H 0 тоже можно считать проверочной матрицей данного БЧХ-кода. Значит,   1 ξ ξ2 ξ3 ξ4 ξ5 ξ6 ξ7 H 0 =  1 ξ 2 ξ 4 ξ 6 ξ 8 ξ 10 ξ 12 ξ 14  = 1 ξ 4 ξ 8 ξ 12 ξ 16 ξ 20 ξ 24 ξ 28  1 ξ =  1 ξ2 1 ξ4  1  0   1 =  0   1  ξ7 ξ6  = ξ4  0 1 2 2 0 0 2 1 2 2 0 2 2 1   1 2 2 1 1 2 2   2 0 1 0 2 0 1   2 1 2 1 2 1 2  0 0 0 0 0 0 0 ξ2 ξ4 1 ξ3 ξ6 ξ4 ξ4 1 1 ξ5 ξ2 ξ4 ξ6 ξ4 1 Подстановка элемента ξ 5 в многочлены M1 (x) = M3 (x), M2 (x), M4 (x) показывает, что M1 (ξ 5 ) 6= 0, M2 (ξ 5 ) 6= 0, M4 (ξ 5 ) 6= 0. Следовательно, M5 (x) 6∈ {M1 (x), M2 (x), M3 (x), M4 (x)}. Это значит, что в проверочную матрицу H (H 0 ) нельзя добавить строку (1, ξ 5 , ξ 10 , ξ 15 , ξ 20 , ξ 25 , ξ 30 , ξ 35 ), что означает, что dmin (C) ≤ 5 и код C не исправляет более двух ошибок. ~ = 12201011, Осуществим алгоритм декодирования для нашего случая: w d = 5, n = 8, r ≤ 2. Шаг 1.     S1 w̄(ξ)  S2   w̄(ξ 2 )  T  = H~   S(ξ) =  w =  S3   w̄(ξ 3 )  = S4 w̄(ξ 4 )   1 + 2ξ + 2ξ 2 + ξ 4 + ξ 6  1 + 2ξ 2 + 2ξ 4 + ξ 8 + ξ 12   =  1 + 2ξ 3 + 2ξ 6 + ξ 12 + ξ 18  = 1 + 2ξ 4 + 2ξ 8 + ξ 16 + ξ 24     1 + 2ξ + 2ξ 2 + ξ 4 + ξ 6 ξ+1  1 + 2ξ 2 + 2ξ 4 + 1 + ξ 4   ξ + 1    . =  1 + 2ξ 3 + 2ξ 6 + ξ 4 + ξ 2  =  2ξ  4 1 + 2ξ + 2 + 1 + 1 ~ произошла хотя бы одна Поскольку S(~ w) 6= (0, 0, 0, 0)T , то в слове w ошибка, т.е. r > 0. Шаг 2. Найдем решение системы (τ1 , τ2 ) системы      S2 S1 τ1 S3 =− , S3 S2 τ2 S4 т.е. системы  (ξ + 1)τ1 + (ξ + 1)τ2 = −2ξ, 2ξτ1 + (ξ + 1)τ2 = 0. По формулам Крамера ξ+1 2ξ ξ ξ+1 0 ξ+1 , τ1 = ξ+1 ξ+1 2ξ ξ+1 ξ τ2 = . ξ+1 ξ+1 2ξ ξ+1 Значит, ξ2 + ξ 1 = = ξ7, 2 −ξ + 1 ξ −2ξ 2 2ξ + 1 ξ2 τ2 = = = = ξ. = ξ + 2. −ξ 2 + 1 ξ ξ Теперь можно составить многочлен локаторов ошибок τ1 = σ(x) = τ0 + τ1 x + τ2 x2 = 1 + ξ 7 x + ξx2 . Шаг 3. Вычислим σ(ξ i ) для любого i ∈ {0, 1, . . . , 7}: σ(1) = 1 + ξ 7 + ξ = 1 + (ξ + 1) + ξ = 2ξ + 2 6= 0, σ(ξ) = 1 + ξ 8 + ξ 3 = 2 + ξ 3 = 2 + (2ξ + 2) = 2ξ + 1 6= 0, σ(ξ 2 ) = 1 + ξ 9 + ξ 5 = 1 + ξ + ξ 5 = 1 + ξ + 2ξ = 1 6= 0, σ(ξ 3 ) = 1 + ξ 10 + ξ 7 = 1 + ξ 2 + ξ 7 = 1 + (2ξ + 1) + (ξ + 1) = 0, σ(ξ 4 ) = 1 + ξ 11 + ξ 9 = 1 + ξ 3 + ξ = 1 + (2ξ + 2) + ξ = 0, σ(ξ 5 ) = 1 + ξ 12 + ξ 12 = 1 + 2ξ 2 = 1 + ξ + 2 = ξ 6= 0, σ(ξ 6 ) = 1 + ξ 13 + ξ 13 = 1 + 2ξ 5 = 1 + ξ 6= 0, σ(ξ 7 ) = 1 + ξ 14 + ξ 15 = 1 + ξ 6 + ξ 7 = 1 + (ξ + 2) + (ξ + 1) = 2ξ + 1 6= 0, Видно, что x = ξ 3 = ξ −5 , x = ξ 4 = ξ −4 являются корнями уравнения σ(x) = 0. Следовательно, ошибки произошли в 4-й и 5-й позициях (позиции нумеруются с нуля), т.е. вектор ошибок равен ~e = 0000e4 e5 00, где e4 , e5 ∈ {1, 2}. Шаг 4. Найдем e4 , e5 , решая систему  8 P   S1 = ei ξ i ,    i=0   8  P   ei ξ 2i ,  S2 =  e4 ξ 4 + e5 ξ 5 = 2ξ + 2,    e4 ξ 8 + e5 ξ 10 = 2ξ + 2, i=0 ⇔ ⇔ 8 P e4 ξ 12 + e5 ξ 15 = 2ξ + 2,   3i     S = e ξ , 3 i 16 20  e4 ξ + e5 ξ = 2ξ + 2,   i=0   8 P    S1 = ei ξ 4i i=0  2e4 + 2ξe5 = ξ + 1,    e4 + (2ξ + 1)e5 = ξ + 1, ⇔ 2e  4 + (ξ + 1)e5 = 2ξ,   e4 + 2e5 = 0. Уже из первого равенства получаем e4 = e5 = 2. Следовательно, ~e = 00002200. ~ соответствует кодовое слово ~v = w ~ −~e = 12201010 − Шаг 5. Слову w 00002200 = 12202110. Этому кодовому слову соответствует сообщение ~a = a0 a1 a2 , где ā(x) = a0 + a1 x + a2 x2 = x6 + x5 + 2x4 + 2x2 + 2x + 1 v̄(x) = x + 2. = g(x) x5 + 2x4 + x3 + x2 + 2 x6 + x5 + 2x4 + 2x2 + 2x + 1 x6 + 2x5 + x4 + x3 + 2x 2x5 + x4 + 2x3 + 2x2 + 1 2x5 + x4 + 2x3 + 2x2 + 1 Значит, ~a = 210. x5 + 2x4 + x3 + x2 + 2 x+2 Ответ 8. Кодовое слово равно 12202110, ему соответствует сообщение 210. Задача 12. Пусть ξ — примитивный элемент поля F24 , ξ 4 + ξ 3 + 1 = 0, а g(x) = x10 + x9 + x8 + x6 + x5 + x2 + 1 — порождающий многочлен БЧХ-кода длины 15. Найти минимальное расстояние этого кода и посланные кодовое слово и сообщение, если получено слово 001011000101010. Решение. Опишем сначала поле F24 , полученного из поля F2 при помощи примитивного элемента ξ, минимальным многочленом которого является многочлен f (x) = x4 +x3 +1. Напомним, что поле F24 можно еще рассматривать и как линейное пространство над полем F2 с базисом 1, ξ, ξ 2 , ξ 3 . ξ 4 = ξ 3 + 1, ξ 5 = ξξ 4 = ξ 4 + ξ = ξ 3 + ξ + 1, ξ 6 = ξξ 5 = ξ 4 + ξ 2 + ξ = ξ 3 + ξ 2 + ξ + 1, ξ 7 = ξξ 6 = ξ 4 + ξ 3 + ξ 2 + ξ = (ξ 3 + 1) + ξ 3 + ξ 2 + ξ = ξ 2 + ξ + 1, ξ 8 = ξξ 7 = ξ 3 + ξ 2 + ξ, ξ 9 = ξξ 8 = ξ 4 + ξ 3 + ξ 2 = (ξ 3 + 1) + ξ 3 + ξ 2 = ξ 2 + 1, ξ 10 = ξξ 9 = ξ 3 + ξ, ξ 11 = ξξ 10 = ξ 4 + ξ 2 = ξ 3 + ξ 2 + 1, ξ 12 = ξξ 11 = ξ 4 + ξ 3 + ξ = (ξ 3 + 1) + ξ 3 + ξ = ξ + 1, ξ 13 = ξξ 12 = ξ 2 + ξ, ξ 14 = ξξ 13 = ξ 3 + ξ 2 , ξ 15 = ξξ 14 = ξ 4 + ξ 3 = (ξ 3 + 1) + ξ 3 = 1. Будем искать минимальные многочлены Mi (x), i ∈ {1, . . . , d − 1}, элементов ξ i , где d — конструктивное расстояние БЧХ-кода, т.е. g(x) = HOK{Mi (x) | {1, . . . , d − 1}}. Ясно, что M1 (x) = f (x). Поскольку M1 (ξ 2 ) = 0, то M2 (x) = M1 (x). Однако f (ξ 3 ) 6= 0, следовательно, M3 (x) 6= M1 (x). Всилу соотношений (ξ 3 )2 = ξ 6 6= ξ 3 , 2 (ξ 3 )2 = ξ 12 6= ξ 3 , 3 (ξ 3 )2 = ξ 24 = ξ 9 6= ξ 3 , 4 (ξ 3 )2 = ξ 48 = ξ 3 , степень многочлена M3 (x) равна четырем. Из таблицы примитивных многочленов степени 4 над полем F2 простой подстановкой выбираем минимальный многочлен M3 (x) = x4 +x3 +x2 +x+1. Заметим, что deg g(x) = 12, а deg HOK{M1 (x), M2 (x), M3 (x)} = deg M1 (x)M3 (x) = 8, следовательно, d > 4. Для элемента xi4 справедливо M1 (ξ 4 ) = 0 поэтому M4 (x) = M1 (x). А для элемента ξ 5 имеет место M1 (ξ 5 ) 6= 0, M3 (ξ 5 ) 6= 0. Как и выше при помощи таблицы примитивных многочленов находим M5 (x) = x2 + x + 1. Теперь deg HOK{Mi (x) | i ∈ {1, 2, 3, 4, 5}} = deg M1 (x)M3 (x)M5 (x) = 10, а значит g(x) = M1 (x)M3 (x)M5 (x) и d = 6. Значит в качестве проверочной матрицы кода можно взять матрицу   1 ξ ξ 2 . . . ξ 14 H =  1 ξ 3 ξ 6 . . . ξ 28  1 ξ 5 ξ 10 . . . ξ 70 Кроме того, M3 (ξ 6 ) = 0, а Mi (ξ 7 ) 6= 0 для любого i ∈ {1, 2, 3, 4, 5}. Это означает, что в проверочную матрицу можно добавить строку (1, ξ 6 , ξ 12 , . . . , ξ 84 ) а строку (1, ξ 7 , ξ 14 , . . . , ξ 98 ) добавлять уже нельзя. Следовательно, dmin = 7, и значит код исправляет не более трех ошибок. ~ = w0 w1 . . . w14 = 001011000101010. Декодируем слово w Шаг 1.     S1 w̄(ξ)  S2   w̄(ξ 2 )       S3   w̄(ξ 3 )  T  = H~   S(ξ) =  w =  S4   w̄(ξ 4 )  =      S5   w̄(ξ 5 )  S6 w̄(ξ 6 )  2  ξ + ξ 4 + ξ 5 + ξ 9 + ξ 11 + ξ 13  ξ 4 + ξ 8 + ξ 10 + ξ 18 + ξ 22 + ξ 26   6   ξ + ξ 12 + ξ 15 + ξ 27 + ξ 33 + ξ 39    = 8 16 20 36 44 52  =  ξ 10+ ξ 20+ ξ 25+ ξ 45+ ξ 55+ ξ 62   ξ +ξ +ξ +ξ +ξ +ξ  ξ 12 + ξ 24 + ξ 30 + ξ 54 + ξ 66 + ξ 78    3  ξ3 ξ  ξ3 + ξ2 + ξ + 1   ξ6     12     ξ  ξ+1  =  12  . =    ξ  ξ+1    5  3    ξ  ξ +ξ+1 2 ξ +1 ξ9 ~ произошла хотя бы одна ошибка, т.е. r > 0. Ясно, что в слове w Будем считать, что r = 3 Шаг 2. Найдем решение системы (τ1 , τ2 , τ3 ) системы      S3 S2 S1 τ1 S4  S 4 S 3 S 2   τ2  = −  S 5  , S5 S4 S3 τ3 S6 т.е. системы  12  ξ τ1 + ξ 6 τ2 + ξ 3 τ3 = ξ 12 , ξ 12 τ1 + ξ 12 τ2 + ξ 6 τ3 = ξ 5 ,  5 ξ τ1 + ξ 12 τ2 + ξ 12 τ3 = ξ 9 , По формулам Крамера ∆1 , ∆ τ2 = ∆2 , ∆ ∆= ξ 12 ξ 12 ξ5 ξ6 ξ 12 ξ 12 ξ3 ξ6 ξ 12 = ξ + 1 = ξ 12 , ∆1 = ξ 12 ξ5 ξ9 ξ6 ξ 12 ξ 12 ξ3 ξ6 ξ 12 = 1, τ1 = τ1 = ∆3 , ∆ где ∆2 = ξ 12 ξ 12 ξ5 ξ 12 ξ5 ξ9 ξ3 ξ6 ξ 12 = ξ 3 + ξ 2 + 1 = ξ 11 , ∆3 = ξ 12 ξ 12 ξ5 ξ6 ξ 12 ξ 12 ξ 12 ξ5 ξ9 = ξ 2 + ξ = ξ 13 . Поэтому, τ1 = ξ −12 = ξ 3 , τ2 = ξ −1 = ξ 14 , τ3 = ξ. Теперь можно составить многочлен локаторов ошибок σ(x) = τ0 + τ1 x + τ2 x2 = 1 + ξ 3 x + ξ 14 x2 + ξx3 . Шаг 3. Вычислим σ(ξ i ) для любого i ∈ {0, 1, . . . , 7}: σ(1) = ξ 2 + ξ = 1 6= 0, σ(ξ) = ξ + 1 6= 0, σ(ξ 2 ) = ξ 2 + 1 6= 0, σ(ξ 3 ) = ξ 3 + ξ 2 + ξ + 1 6= 0, σ(ξ 4 ) = ξ 2 + ξ + 1 6= 0, σ(ξ 5 ) = ξ 3 6= 0, σ(ξ 6 ) = 0, σ(ξ 7 ) = ξ 3 + ξ 6= 0, σ(ξ 8 ) = ξ 2 + ξ + 1 6= 0, σ(ξ 9 ) = 0, σ(ξ 10 ) = ξ 3 + ξ 2 6= 0, σ(ξ 11 ) = ξ 3 + ξ + 1 6= 0, σ(ξ 12 ) = ξ 3 + 1 6= 0, σ(ξ 13 ) = ξ + 1 6= 0, σ(ξ 14 ) = 0, Корнями уравнения σ(x) = 0 являются x = ξ 6 = ξ −9 , x = ξ 9 = ξ −6 , x = ξ 14 = ξ −1 . Следовательно, ошибки произошли в 1-й, 6-й и 9-й позициях (позиции нумеруются с нуля), т.е. ~e = 010000100100000. ~ соответствует кодовое слово Шаг 5. Слову w ~v = w ~ − ~e = 001011000101010 − 010000100100000 = 011011100001010. Этому кодовому слову соответствует сообщение ~a = a0 a1 a2 a3 , где ā(x) = a0 + a1 x + a2 x2 + a3 x3 = = v̄(x) = g(x) x13 + x11 + x6 + x5 + x4 + x2 + x = x3 + x2 + x. x10 + x9 + x8 + x6 + x5 + x2 + 1 Значит, ~a = 0111. Ответ 9. Кодовое слово равно 011011100001010, соответствующее кодовое сообщение равно 0111.