2014-02-24
2912
Принцип обнаружения и исправления ошибок корректирующими кодами
Прежде, чем начать рассмотрение специальных корректирующих кодов, следует отметить, что любой код способен обнаруживать и исправлять ошибки, если не все кодовые слова (кодовые комбинации) этого кода используются для передачи сообщений. Нагляднее рассмотреть это на примере блочных кодов, у которых последовательность символов на выходе источника разбивается на блоки (кодовые слова, кодовые комбинации), содержащие одинаковое число символов k. При этом для двоичного кода ансамбль сообщений будет иметь объем Nр= 2 k. При помехоустойчивом кодировании это множество из Nр сообщений отображается на множество N = 2 n возможных кодовых слов, такая процедура и называется помехоустойчивым кодированием дискретных сообщений (число 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б ошибка в запрещенном кодовом слове B 1 j будет исправлена, так как это слово принадлежит подмножеству (1), приписанному к переданному разрешенному слову A 1; ошибка в кодовых словах B 2 j или B 4 j не будет исправлена, так как эти слова относятся к подмножествам, приписанным к другим разрешённым кодовым словам.
Если принятое кодовое слово попадает в подмножество запрещенных слов, не принадлежащих ни к одному из подмножеств ( 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, которые не исправляются данным кодом.
Очевидно, что, если в канале связи преобладают ошибки большой кратности, целесообразно к разрешенным кодовым словам приписывать подмножество таких неразрешенных слов, которые удалены от данного разрешенного на расстояние, соответствующее этим ошибкам.
