Линейные коды

ДИСКРЕТНАЯ МАТЕМАТИКА Линейные коды Белоусов Иван Николаевич Институт радиоэлектронники и информационных технологий Уральский федеральный университет 06 апреля 2020 Код Хэмминга Определение 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 , — сообщение, тогда по формуле (??) соответствующее кодовое слово равно ~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 ) — сообщение, тогда соответсвующее кодовое слово из дуального кода по формуле (??) равно ~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 ошибку (теорема ??). Следовательно, для вероятности 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 ошибку (теорема ??). Слово ~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 .