Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
+ b 1 g 2 n−m −1 + b 2 · · · g 2 n−m −1 + То, что строк будет 2 n−m следует из теоремы Лагранжа [1], т.к. 2 n−m — это порядок фактор-группы G/B, #(G/B) = #(G)/#(B), #B = Декодирование слова g = b j + g состоит в выборе кодового слова b в качестве переданного и последующем применении операции, обратной умножению на E. Такая схема декодирования сможет исправлять ошибки. Для (3, кода из рассматриваемого примера таблица декодирования будет следующей 100110 010011 110101 001111 101001 011100 111010 100000 000110 110011 010101 101111 001001 111100 011010 010000 110110 000011 100101 011111 011001 001100 101010 001000 101110 011011 111101 000111 100001 010100 110010 000100 100010 010111 110001 001011 101101 011000 111110 000010 100100 010001 110111 001101 101011 011110 111000 000001 100111 010010 110100 001110 101000 011101 111011 000101 100011 010110 110000 001010 101100 011001 111111. 59 Первая строка в ней — это строка кодовых слова первый столбец это лидеры. Чтобы декодировать слово b j + e, следует отыскать его в таблице и выбрать в качестве переданного слово в том же столбце ив первой строке. Например, если принято слово 110011 (я строка, й столбец таблицы, то считается, что было передано слово 010011; аналогично, если принято слово 100101 (я строка, й столбец таблицы, переданным считается слово 110101, и т.д. Групповое кодирование со схемой декодирования посредством лидеров исправляет все ошибки, строки которых совпадают с лидерами. Следовательно, вероятность правильного декодирования переданного по двоичному симметричному каналу кода равна сумме вероятностей всех лидеров, включая нулевой. В рассмотренной схеме вероятность правильной передачи слова будет+ Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца. Пусть переданное слово b i принято как b i + e , d(b i , b i + e) = w(e) , т. е. это расстояние равно весу соответствующего лидера. Расстояние от b i + e до любого другого кодового слова b j равно весу их поразрядной суммы, тет. к лидер смежного класса, к которому принадлежат как b k + e , таки+ Доказано, при схеме декодирования лидерами по полученному слову берется ближайшее к нему кодовое. Упражнение Для кодирующих матриц E 1 = 1 0 1 0 1 0 1 1 1 0 , E 2 = 1 0 0 1 0 1 0 1 0 0 1 0 : 1. Построить соответственно (2, код и (3, код. Найти основные характеристики полученных кодов минимальное расстояние между словами кода вероятность необнаружения ошибки максимальную кратность ошибок, до которой включительно они все исправляются или обнаруживаются. Построить таблицы декодирования. Уточнить характеристики полученных кодов, при использовании их для исправления ошибок, те. найти вероятность правильной передачи и описать ошибки, исправляемые этими кодами. Во что будут декодированы слова 10001, 01110, 10101, 1001, 0110, 1101? 60 24. Совершенные и квазисовершенные коды Групповой (m, код, исправляющий все ошибки веса, не большего k, и никаких других, называется совершенным. Свойства совершенного кода [1]: 1. Для совершенного (m, кода, исправляющего все ошибки веса, не большего k, выполняется соотношение k i=0 C i n = 2 n−m . Верно и обратное утверждение. Совершенный код, исправляющий все ошибки веса, не большего k, в столбцах таблицы декодирования содержит все слова, отстоящие от кодовых на расстоянии, не большем k. Верно и обратное утверждение. Таблица декодирования совершенного кода, исправляющего все ошибки вне более чем k позициях, имеет в качестве лидеров все строки, содержащие не более k единиц. Верно и обратное утверждение. Совершенный код — это лучший код, обеспечивающий максимум минимального расстояния между кодовыми словами при минимуме длины кодовых слов. Совершенный код легко декодировать каждому полученному слову однозначно ставится в соответствие ближайшее кодовое. Чисел m, n и k (1 < k < n−1 2 ), удовлетворяющих условию совершенно- сти кода очень мало. Но и при подобранных m, n и k совершенный код можно построить только в исключительных случаях. Если m, n и k не удовлетворяют условию совершенности, то лучший групповой код, который им соответствует называется квазисовер- шенным, если он исправляет все ошибки кратности, не большей k, и некоторые ошибки кратности k + 1. Квазисовершенных кодов также очень мало. Двоичный блочный (m, код называется оптимальным, если он минимизирует вероятность ошибочного декодирования. Совершенный или квазисовершенный код — оптимален. Общий способ построения оптимальных кодов пока неизвестен. Для любого целого положительного числа r существует совершенный, код, исправляющий одну ошибку, называемый кодом Хэм- минга (Hamming), в котором m = 2 r − r − 1 и n = 2 r − Действительно n = 1 + 2 r − 1 = 2 r = Порядок построения кода Хэмминга следующий. Выбираем целое положительное число r. Сообщения будут словами длины m = 2 r − r − 1, а кодовые слова — длины n = 2 r − 1; 2. В каждом кодовом слове b = b 1 b 2 . . . b n r бит с индексами- степенями двойки (2 0 , 2 1 , . . . , 2 r−1 ) — являются контрольными, остальные в естественном порядке — битами сообщения. Например, если r = 4, то биты b 1 , b 2 , b 4 , b 8 — контрольные, а b 3 , b 5 , b 6 , b 7 , b 9 , b 10 , b 11 , b 12 , b 13 , b 14 , b 15 — из исходного сообщения. Строится матрица M из 2 r − 1 строки столбцов. Вой строке стоят цифры двоичного представления числа i. Матрицы для r = 2, и 4 таковы 10 11 M 7×3 = 001 010 011 100 101 110 111 M 15×4 = 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 ; 4. Записывается система уравнений bM = 0, где M — матрица из предыдущего пункта. Система состоит из r уравнений. Например, для r = 3: b 4 + b 5 + b 6 + b 7 = 0 b 2 + b 3 + b 6 + b 7 = 0 b 1 + b 3 + b 5 + b 7 = 0 ; 5. Чтобы закодировать сообщение a, берутся в качестве b j , j неравно степени двойки, соответствующие биты сообщения и отыскиваются, используя полученную систему уравнений, те b j , для которых j — степень двойки. В каждое уравнение входит только одно b j , j = В выписанной системе входит в е уравнение, b 2 — во второе ив третье. В рассмотренном примере сообщение a = 0111 будет закодировано кодовым словом b = Декодирование кода Хэмминга проходит последующей схеме. Пусть принято слово b + e, где b — переданное кодовое слово, а e строка ошибок. Так как bM = 0, то (b + e)M = bM + eM = eM . Если результат нулевой, как происходит при правильной передаче, считается, что ошибок не было. Если строка ошибок имеет единицу в й позиции, то результатом произведения eM будет я строка матрицы или двоичное представление числа i. В этом случае следует изменить символ в й позиции слова b + e, считая позиции слева, с единицы. Пример. (4, код Хэмминга имеет в качестве одного из кодовых слов b = 0001111. Матрица приведена на шаге 3 хода построения кода Хэмминга. Ясно, что bM = 0. Добавим к b строку ошибок e = 62 0010000. Тогда b + e = 0011111 и (b + e)M = 011 = 3 10 , те. ошибка находится в третьей позиции. Если e = 0000001, то b + e = 0001110 и позиция ошибки — (b+e)M = 111 = 7 и т.п. Если ошибка допущена в более чем водной позиции, то декодирование даст неверный результат. Код Хэмминга — это групповой код. Это следует из того, что, код Хэмминга можно получить матричным кодированием, при помощи m × матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соответствуют уравнениям шага 4 построения кода Хэмминга, тему столбцу соответствует уравнение для вычисления го контрольного разряда, 2-му для го, 4-му — для го и т. д. Такая матрица будет при кодировании копировать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга. Пример. Кодирующая матрица для (4, кода Хэмминга — E = 1110000 1001100 0101010 Ее столбцы с номерами 3, 5, 6 и 7 образуют единичную подматрицу. Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению b 1 = b 3 + b 5 + соответствует столбец 1101, те. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3, 5 и 7 кода. К (m, коду Хэмминга можно добавить проверку четности. Получится+ код с наименьшим весом ненулевого кодового слова, способный исправлять одну и обнаруживать две ошибки. Коды Хэмминга накладывают ограничения на длину слов сообщения эта длина может быть только числами вида 2 r − r − 1: 1, 4, 11, 26, 57, . . . Нов реальных системах информация передается байтам или машинными словами, те. порциями поили бита, что делает использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные коды. Квазисовершенные (m, коды, исправляющие одну ошибку, строятся следующим образом. Выбирается минимальное n так, чтобы n + 1 Каждое кодовое слово такого кода будет содержать k = n−m контрольных разрядов. Из предыдущих соотношений следует, что 2 n−m n + 1 = C 1 n + C 0 n = m + k + 1. 63 Каждому из n разрядов присваивается слева-направо номер от 1 до n. Для заданного слова сообщения составляются k контрольных сумм, . . . , S k по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем для S i (1 i k) выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в м разряде единицу. Для суммы это будут, например, разряды 3, 5, 7 и т.д., для суммы S 2 — 3, 6, 7 и т. д. Таким образом, для слова сообщения a = a 1 . . . a будет построено кодовое слово b = S 1 S 2 a 1 S 3 a 2 a 3 a 4 S 4 a 5 . . . a m . Обозначим S ∗ i сумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме S i и самой этой контрольной суммы. Если S ∗ k . . . S ∗ 1 = то считается, что передача прошла без ошибок. В случае одинарной ошибки S ∗ k . . . будет равно двоичному числу-номеру сбойного бита. В случае ошибки, кратности большей 1, когда S ∗ k . . . S ∗ 1 > n, ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода. Пример построения кодового слова квазисовершенного (9, n)-кода, исправляющего все однократные ошибки, для сообщения 100011010. 2 12 13 = 4096 13 < 2 9 = и 13 14 = 4096 7 > 512, те. n = Искомое кодовое слово имеет вид 2 3 4 5 6 7 8 9 10 11 12 13 S 1 S 2 1 S 3 0 0 0 S 4 1 1 0 1 0 Далее нужно вычислить контрольные суммы 10 = 0001 2 2 10 = 0010 2 3 10 = 0011 2 4 10 = 0100 2 5 10 = 0101 2 6 10 = 0110 2 7 10 = 0111 2 8 10 = 1000 2 9 10 = 1001 2 10 10 = 1010 2 11 10 = 1011 2 12 10 = 1100 2 13 10 = 1101 2 S 1 = b 3 + b 5 + b 7 + b 9 + b 11 + b 13 = 0 S 2 = b 3 + b 6 + b 7 + b 10 + b 11 = 0 S 3 = b 5 + b 6 + b 7 + b 12 + b 13 = 1 S 4 = b 9 + b 10 + b 11 + b 12 + b 13 = Таким образом, искомый код — 0011000111010. Если в процессе передачи этого кода будет испорчен его пятый бит, то приемник получит код 0011100111010. Для его декодирования опять вычисляются контрольные суммы b 1 + b 3 + b 5 + b 7 + b 9 + b 11 + b 13 = 1 S ∗ 2 = b 2 + b 3 + b 6 + b 7 + b 10 + b 11 = 0 S ∗ 3 = b 4 + b 5 + b 6 + b 7 + b 12 + b 13 = 1 S ∗ 4 = b 8 + b 9 + b 10 + b 11 + b 12 + b 13 = 0 S ∗ 4 S ∗ 3 S ∗ 2 S ∗ 1 = 0101 2 = 5 Приемник преобразует изменением пятого бита полученное сообщение в отправленное передатчиком, из которого затем отбрасыванием контрольных разрядов восстанавливает исходное сообщение. Совершенный код Хэмминга также можно строить по рассмотренной схеме, т.к. для него 2 n /(n + 1) = Для исправление одинарной ошибки к разрядному коду достаточно приписать 4 разряда (2 12 /13 > 2 8 ), к разрядному — 5, к 32- разрядному — 6, к разрядному — Упражнение Может ли (6, код, минимальное расстояние между кодовыми словами которого 5, быть совершенным? Упражнение Построить кодовые слова квазисовершенного (9, кода, исправляющего однократные ошибки, для тех сообщений, которые соответствуют числами декодировать слова 1000001000001, 1100010111100, полученные по каналу связи, использующему этот код. Полиномиальные коды При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды — блочные и отличаются от рассмотренных ранее только алгоритмами кодирования и декодирования. Пусть a = a 0 . . . a m−1 — двоичное сообщение. Тогда сопоставим ему многочлен a(x) = a 0 + a 1 x + · · · + a m−1 x m−1 . Все вычисления происходят в поле классов вычетов по модулю 2, те. от результата любой арифметической операции берется остаток от его деления на Например, последовательности 10011 при m = 5 соответствует многочлен 1 + x 3 + Зафиксируем некоторый многочлен степени k, g(x) = g 0 + g 1 x + · · · + g k x k , g 0 = 0, g k = 0. 65 Полиномиальный код с кодирующим многочленом g(x) кодирует слово сообщения a(x) многочленом b(x) = a(x)g(x) = b 0 + b 1 x + · · · + b n−1 x или кодовым словом из коэффициентов этого многочлена b = b 0 . . . b Условия g 0 = 0 и g k = 0 необходимы, потому что в противном случае и b не будут нести никакой информации, т. кони всегда будут нулями. Пример. Рассмотрим кодирующий многочлен g(x) = 1 + x 2 + Сообщение 01011, отвечающее многочлену a(x) = x + x 3 + x 4 , будет закодировано коэффициентами многочлена b(x) = g(x)a(x) = те. b = Полиномиальный код с кодирующим многочленом g(x) степени k является матричным кодом с кодирующей матрицей G размерности m× (m + k): G = g 0 g 1 g 2 · · · g k 0 0 · · · 0 0 g 0 g 1 · · · g k−1 g k 0 · · · 0 0 0 g 0 · · · g k−2 g k−1 g k · · · 0 · · · · · · · · · · · · · · · · · · · · · · · · · · · 0 0 0 · · · · · · · · · · · · · · · g Те. ненулевые элементы в й строке — это последовательность коэффициентов кодирующего многочлена, расположенных с го пой столбцах. Например, (3, код с кодирующим многочленом отвечает матрице = 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 или отображению 000 → 000000; 001 → 001101; 010 → 011010; 011 → 010111; 100 → 110100; 101 → 111001; 110 → 101110; 111 → Полиномиальные коды являются групповыми. Это следует из того, что коды, получаемые матричным кодированием, — групповые. Рассмотрим (m, код с кодирующим многочленом g(x). Строка ошибок e = e 0 . . . e останется необнаруженной в томи только в том случае, если соответствующий ей многочлен e(x) = e 0 + e 1 x + · · · + e n−1 x делится на Действительно) + делится на тогда и только тогда, когда делится на g(x) . Поэтому любая ошибка, многочлен которой не делится на g(x) , будет обнаружена и, соответственно, любая ошибка, многочлен которой делится на g(x) , не может быть обнаружена Таким образом, обнаружение ошибки при использовании полиномиального кода с кодирующим многочленом g(x) может быть реализовано при помощи алгоритма деления многочленов с остатком если остаток ненулевой, то при передаче произошло искажение данных. Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен x 3 + x 2 + 1 определяет совершенный (4, 7)-код, отличный от рассмотренного ранее. Вообще же, если кодирующий многочлен g(x), порождающий соответствующий, код, не является делителем ни одного из многочленов вида x j + 1 при j < n, то минимальное расстояние между кодовыми словами порожденного им кода не меньше Пусть d — минимальное расстояние между кодовыми словами, оно равно минимуму среди весов ненулевых кодовых слов. Предположим d = 2 . Тогда существует такой, что a(x)g(x) = и степень не больше n . Вес равен 2, поэтому b(x) = x m + x и l < m < n . Следовательно) = x l (x m−l + 1) , что означает, что x m−l + должен делиться на g(x) , а это невозможно по условию. Если предположить, что d = 1 , то это приведет к утверждению о том, что x m должен делиться на g(x) , что тоже противоречит условию. Итак, d 3 Кодирующий многочлен x 11 + x 9 + x 7 + x 6 + x 5 + x + 1 определяет совершенный (12, код Голея (Golay) с минимальным расстоянием между кодовыми словами В 1971 году финскими и советскими математиками было доказано, что кроме кодов Хэмминга и Голея других совершенных кодов нет. Наиболее интересными среди полиномиальных кодов являются циклические коды, в которых вместе с любым кодовым словом вида b 0 . . . b n−2 b есть кодовое слово b n−1 b 0 . . . b Упражнение По кодирующему многочлену x |