Принцип обнаружения и исправления ошибок корректирующими кодами

 

2.1 Коды с обнаружением и исправлением ошибок

Прежде, чем начать рассмотрение специальных корректирующих кодов, следует отметить, что любой код способен обнаруживать и исправлять ошибки, если не все кодовые слова (кодовые комбинации) этого кода используются для передачи сообщений. Нагляднее рассмотреть это на примере блочных кодов, у которых последовательность символов на выходе источника разбивается на блоки (кодовые слова, кодовые комбинации), содержащие одинаковое число символов k. При этом для двоичного кода ансамбль сообщений будет иметь объем N _р = 2 ^k. При помехоустойчивом кодировании это множество из N _р сообщений отображается на множество N = 2 ⁿ возможных кодовых слов, такая процедура и называется помехоустойчивым кодированием дискретных сообщений (число n – число символов в кодовом слове после кодирования,иногда его называют длиной кодовых слов или значностью кода).

В общем случае для блочного равномерного кода с основанием  код имеет  возможных кодовых слов. Используемые для передачи сообщений кодовые слова из множества  называют разрешенными, остальные кодовые слова измножества  не используются и называются запрещенными (неразрешенными для передачи).

Сущность обнаружения ошибок схематично поясняется на Рисунок 48а. Если в результате искажений в канале связи переданное (разрешенное) кодовое слово A_i (i = 1,2, … N _р)превращается в одно из запрещённых B_j (j = 1,2, … N _з), то ошибка обнаруживается, так как такое слово не могло быть передано. Ошибка не обнаруживается только в том случае, когда очередное передаваемое кодовое слово превращается в другое разрешенное, например A_j, которое также могло быть передано.

 

 

Рисунок  89 - Обнаружение и исправление ошибок

 

Исправление ошибок представляет собой более сложную операцию, так как кроме обнаружения наличия ошибки в принятом кодовом слове необходимо определить и местоположение искаженного кодового символа (а если , то и характер искажения). Для того чтобы рассматриваемый код исправлял ошибки, необходимо часть или всё множество  запрещённых кодовых слов разбить на N _р непересекающихся подмножеств ^{( i )} (i = 1,2, … N _р) по количеству разрешенных кодовых слов. Каждое из подмножеств ^{( i )} в декодере приемника приписывается одному из разрешенных кодовых слов (Рисунок 48б).

Способ приема заключается в том, что если принятое кодовое слово принадлежит подмножеству ^{( i )}, считается переданным -е разрешенное кодовое слово. Ошибка не может быть исправлена (исправляется неверно), если переданное кодовое слово в результате искажений превращается в кодовое слово любого другого подмножества ^{( j )},(j ¹ i). На Рисунок  48б ошибка в запрещенном кодовом слове B _{1 j} будет исправлена, так как это слово принадлежит подмножеству ⁽¹⁾, приписанному к переданному разрешенному слову A ₁; ошибка в кодовых словах 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 приведены кривые распределения кратностей ошибок P_n (t) для двух случаев: для двоичного канала с независимыми ошибками в кодовых символах p – кривая 1 (биномиальное распределение)

P_n (t) = C_n^tp^t (1- p) ^n-t                                                          (1.5)

и кривая 2 для канала, в котором передаваемое кодовое слово с одинаковой вероятностью может превратиться в другое кодовое слово данного кода (из множества N)

                   P_n (t) = C_n^t / mⁿ.                                                                             (1.6)

Графики соответствуют длине кодового слова .

Рисунок 90 - Распределение кратностей ошибок

 

Для приведенных на Рисунок  48 распределений кратностей ошибок определим  величины коэффициентов исправления для корректирующего кода с параметрами: ,  (), , исправляющего одиночные ошибки: .

Вероятность ошибки в передаваемом кодовом слове в канале с распределением кратностей ошибок P_n (t), соответствующим кривой 1(Рисунок  49), и вероятностью искажения символа кода p = 0,1 равна

Вероятность исправления ошибки (вероятность ошибки с кратностью t =1):

.

Тогда

 

В канале связи с распределением кратностей ошибок P_n (t), соответствующим кривой 2 (Рисунок  49), вероятность исправления ошибки (вероятность ошибки с кратностью t =1) равна

где  - доля ошибок, кратность которых _ис из общего числа возможных ошибок mⁿ. Тогда коэффициент исправления равен

Таким образом, один и тот же код в первом случае исправляет примерно в четыре раза больше ошибок, чем во втором. Это объясняется тем, что в первом случае наибольшее количество ошибок имееткратность t =1 и исправляется данным кодом, у которого каждому разрешенному кодовому слову приписывается подмножество ближайших неразрешенных слов, а во втором случае наибольшее количество ошибок имееткратность t >1, которые не исправляются данным кодом.

Очевидно, что, если в канале связи преобладают ошибки большой кратности, целесообразно к разрешенным кодовым словам приписывать подмножество таких неразрешенных слов, которые удалены от данного разрешенного на расстояние, соответствующее этим ошибкам.

 

2.2 Кодовое расстояние, избыточность кода

Обнаруживающая и исправляющая способность корректирующих кодов тесно связана с расстояниями между разрешенными кодовыми словами. Расстояние между любой парой кодовых слов  и  выражает различие между ними

,                                                            (1.7)

где ,  - координаты кодовых слов ,  в -мерном неевклидовом пространстве L_n.

Если код является двоичным, под расстоянием между парой кодовых слов понимается количество символов, в которых они отличаются между собой. Оно определяется сложением двух этих слов по модулю 2 и равно числу единиц в этой сумме. Например:

Знак  означает сумму по модулю 2 (сложение по модулю два выполняется по правилу: , , , ).

Напомним, что геометрической моделью -значного двоичного кода является -мерный куб с ребром, равным единице, каждая вершина которого представляет одно из возможных кодовых слов. Расстояние между словами d_ij равно числу ребер куба, отделяющих одну вершину от другой. Наименьшее расстояние между любой парой разрешенных слов данного кода называется кодовым расстоянием d = min d_ij. (1.8)

Так как кратность ошибки  в геометрическом представлении является расстоянием между переданной комбинацией и искаженной, то для обнаружения ошибок кратности t _об требуется кодовое расстояние, равное

.                                                                   (1.9)

Для исправления ошибок кратности t _ис требуется кодовое расстояние

.                                                                             (1.10)

Это означает, что для исправления ошибок искаженное кодовое слово должно располагаться ближе всего к соответствующему правильному слову.

Для исправления стираний кратности t _ст требуется кодовое расстояние

,                                                                   (1.11)

то есть для исправления стираний требуется такое же кодовое расстояние, как и для обнаружения ошибок.

Способность корректирующих кодов обнаруживать и исправлять ошибки (или стирания) определяется передачей дополнительной (избыточной) информации по каналу связи. Коэффициент избыточности в соответствии с теорией информации, как известно, равен

                (1.12)

где - число избыточных кодовых символов в слове ( + = ).

Для каналов с независимыми ошибками вероятность приёма кодового слова с ошибками определяется очевидным выражением вида

,                                                       (1.13)

а вероятность обнаружения ошибки в принятом кодовом слове при декодировании равна

 = .                    (1.14)

Тогда вероятность необнаружения ошибки при декодировании соответственно равна = - , то есть

= .                        (1.15)

Тогда коэффициент обнаружения можно определить следующим образом

.                                                   (1.16)

В настоящее время известно большое число корректирующих кодов, отличающихся по помехоустойчивости и способам построения. Применение некоторых из них ограничивается сложностью технической реализации кодирующих и декодирующих устройств.

На Рисунок  50 приведена классификация наиболее часто используемых корректирующих кодов, в которой отмечаются только семейства кодов без подробной детализации.

Применение корректирующих (помехоустойчивых) кодов является эффективным средством борьбы с ошибками в каналах связи с помехами. Такие коды используются либо только для обнаружения ошибок, либо для обнаружения и исправления ошибок (или ошибок и стираний в каналах со стиранием).

 

 

2.3 Энергетический выигрыш

В заключение рассмотрим энергетический выигрыш от помехоустойчивого кодирования для случая известных (заданных) параметров канала связи и кода. Вероятность ошибки на выходе дискретного канала связи p _вых (или вероятность ошибки декодирования p _д) является функцией отношения сигнал/шум и качества используемого корректирующего кода. “Выигрыш от кодирования” или “энергетический выигрыш” (ЭВК в дБ), который указывает на улучшение качества системы связи от использования данного способа кодирования или метода защиты от ошибок, определяется выражением

                     .       (1.17)

где h ₁², h ₂² - отношения сигнал/шум в первой и второй сравниваемых системах связи при одинаковой вероятности ошибок на выходе;

a - коэффициент, выравнивающий скорость передачи информации в сравниваемых системах.

Например, если первая система является системой без помехоустойчивого кодирования, а вторая система - с обнаружением ошибок и переспросом, то а = (n/k) T _ср /T; здесь Т _ср- средняя длительность передачи кодового слова (или символа длительности T) в системе с переспросом. Для системы c кодом, исправляющим ошибки без переспроса, a = n / k.

Если снять ограничения на длину кодового слова и полосу частот, занимаемую системой связи, то предельный выигрыш от помехоустойчивого кодирования при данной вероятности ошибки в канале связи с гауссовским шумом будет равен

                         (1.18)

На Рисунок  51 приведены, для примера, кривые предельных значений ЭВК от кодирования при когерентном и некогерентном приеме сигналов дискретной частотной модуляции (ЧМ) в зависимости от вероятности ошибки в дискретном канале связи.

Рисунок  92 - Предельные значения ЭВК от кодирования при ЧМ

 

В реальных системах связи длина кода и занимаемая полоса частот ограничены, для этих условий может быть определен асимптотический выигрыш для данного кода. Он зависит только от скорости кода k / n и кодового расстояния.

Для каналов с жёстким решением (на выходе демодулятора двоичныесимволы 1 и 0)

                                   (1.19)

для каналов с мягким решением (на выходе демодулятора многоуровневый сигнал)

                                            (1.20)

Такой выигрыш достигается, когда E/N o. Из этих соотношений видно, что мягкие решения обеспечивают дополнительный выигрыш не более 3 дБ (при E/N o) и существенно меньше при реальных значениях отношения сигнал/шум.