Коды с обнаружением и исправлением ошибок
Принцип обнаружения и исправления ошибок корректирующими кодами
Прежде, чем начать рассмотрение специальных корректирующих кодов, следует отметить, что любой код способен обнаруживать и исправлять ошибки, если не все кодовые слова (кодовые комбинации) этого кода используются для передачи сообщений. Нагляднее рассмотреть это на примере блочных кодов, у которых последовательность символов на выходе источника разбивается на блоки (кодовые слова, кодовые комбинации), содержащие одинаковое число символов k. При этом для двоичного кода ансамбль сообщений будет иметь объем Nр=2k. При помехоустойчивом кодировании это множество изNрсообщений отображается на множество N= 2n возможных кодовых слов, такая процедура и называется помехоустойчивым кодированием дискретных сообщений (числоn – число символов в кодовом слове после кодирования,иногда его называют длиной кодовых слов или значностью кода).
В общем случае для блочного равномерного кода с основанием код имеет возможных кодовых слов. Используемые для передачи сообщений кодовые слова из множества называют разрешенными, остальные кодовые слова измножества не используются и называются запрещенными (неразрешенными для передачи).
Сущность обнаружения ошибок схематично поясняется на Рисунок 48а. Если в результате искажений в канале связи переданное (разрешенное) кодовое слово Ai (i= 1,2, …Nр)превращается в одно из запрещённых Bj (j= 1,2, …Nз), то ошибка обнаруживается, так как такое слово не могло быть передано. Ошибка не обнаруживается только в том случае, когда очередное передаваемое кодовое слово превращается в другое разрешенное, например Aj, которое также могло быть передано.
Рисунок 89 - Обнаружение и исправление ошибок
Исправление ошибок представляет собой более сложную операцию, так как кроме обнаружения наличия ошибки в принятом кодовом слове необходимо определить и местоположение искаженного кодового символа (а если , то и характер искажения). Для того чтобы рассматриваемый код исправлял ошибки, необходимо часть или всё множество запрещённых кодовых слов разбить на Nр непересекающихся подмножеств (i) (i= 1,2, …Nр) по количеству разрешенных кодовых слов. Каждое из подмножеств (i) в декодере приемника приписывается одному из разрешенных кодовых слов (Рисунок 48б).
Способ приема заключается в том, что если принятое кодовое слово принадлежит подмножеству (i), считается переданным -е разрешенное кодовое слово. Ошибка не может быть исправлена (исправляется неверно), если переданное кодовое слово в результате искажений превращается в кодовое слово любого другого подмножества (j),(j¹i). На Рисунок 48б ошибка в запрещенном кодовом слове B1jбудет исправлена, так как это слово принадлежит подмножеству (1), приписанному к переданному разрешенному слову A1; ошибка в кодовых словах B2jили B4jне будет исправлена, так как эти слова относятся к подмножествам, приписанным к другим разрешённым кодовым словам.
Если принятое кодовое слово попадает в подмножество запрещенных слов, не принадлежащих ни к одному из подмножеств (i) (i= 1,2, …Nр), то ошибка только обнаруживается, но не исправляется. Этот признак может быть использован для исправления ошибки другими методами, например, методом переспроса.
Свойства кода по обнаружению и исправлению ошибок характеризуются количественно коэффициентами обнаружения Kоб и исправления ошибок Kис, которые показывают, во сколько раз уменьшается вероятность ошибки после декодирования по сравнению с её величиной на входе приемного устройства (декодера), благодаря обнаружению ошибок или их исправлению соответственно. Ошибки в кодовых словах могут иметь произвольную конфигурацию, что определяется случайным характером помех в канале связи. Число ошибочных символов в принятом кодовом слове называется кратностью ошибки t, при длине кодового слова из nсимволов она изменяется в пределах от 0 до n.
Если это вероятность ошибки кратности t³ 1 в nразрядном кодовом слове на входе декодера, а Pоб - вероятность обнаружения ошибок в декодере, то коэффициент обнаружения определяется следующим выражением
.
Коэффициент исправления ошибок будет определяться выражением
,
где Pис- вероятность исправления ошибок в декодере.
Последняя численно равна вероятности ошибок в кодовом слове, кратность которых не превышает величины кратности гарантированно исправляемых ошибок tис, то есть Pис= Pвх(£tис, n).
Коэффициент исправления кода всегда меньше коэффициента обнаружения, что является общим условием для любых корректирующих кодов.
Для реализации потенциальных возможностей кода, исправляющего ошибки, необходимо учитывать статистический характер ошибок в реальных каналах связи, в которых предполагается применение этого кода. Разбиение неразрешенных комбинаций на подмножества (i) должно выполняться таким образом, чтобы исправлялись ошибки, появление которых наиболее вероятно в данном канале связи.
В общем случае передаваемая кодовая комбинация искажается случайным образом, что определяется случайным характером помех в канале связи. В реальных системах связи при многообразии характера действующих в линии связи помех распределение кратностей ошибок в дискретном канале связи может быть самым различным. Поэтому построению декодера, исправляющего ошибки, должно предшествовать изучение статистических свойств канала связи. В качестве примера, на Рисунок 49 приведены кривые распределения кратностей ошибок Pn(t) для двух случаев: для двоичного канала с независимыми ошибками в кодовых символах p – кривая 1 (биномиальное распределение)
Pn(t) = Cntpt(1- p)n-t (1.5)
и кривая 2 для канала, в котором передаваемое кодовое слово с одинаковой вероятностью может превратиться в другое кодовое слово данного кода (из множества N)
Pn(t) = Cnt /mn. (1.6)
Графики соответствуют длине кодового слова .
Рисунок 90 - Распределение кратностей ошибок
Для приведенных на Рисунок 48 распределений кратностей ошибок определим величины коэффициентов исправления для корректирующего кода с параметрами: , ( ), , исправляющего одиночные ошибки: .
Вероятность ошибки в передаваемом кодовом слове в канале с распределением кратностей ошибок Pn(t), соответствующим кривой 1(Рисунок 49), и вероятностью искажения символа кода p = 0,1 равна
Вероятность исправления ошибки (вероятность ошибки с кратностьюt=1):
.
Тогда
В канале связи с распределением кратностей ошибок Pn(t), соответствующим кривой 2 (Рисунок 49), вероятность исправления ошибки (вероятность ошибки с кратностьюt=1) равна
где - доля ошибок, кратность которых ис из общего числа возможных ошибок mn. Тогда коэффициент исправления равен
Таким образом, один и тот же код в первом случае исправляет примерно в четыре раза больше ошибок, чем во втором. Это объясняется тем, что в первом случае наибольшее количество ошибок имееткратностьt=1 и исправляется данным кодом, у которого каждому разрешенному кодовому слову приписывается подмножество ближайших неразрешенных слов, а во втором случае наибольшее количество ошибок имееткратностьt>1, которые не исправляются данным кодом.
Очевидно, что, если в канале связи преобладают ошибки большой кратности, целесообразно к разрешенным кодовым словам приписывать подмножество таких неразрешенных слов, которые удалены от данного разрешенного на расстояние, соответствующее этим ошибкам.