Общие принципы использования избыточности
Способность кода обнаруживать и исправлять ошибки обусловлена наличием в нем избыточных символов.
Приведенный ниже рисунок иллюстрирует принципы построения помехоустойчивых кодов.
Рисунок иллюстрирует процесс помехоустойчивого кодирования путем увеличения числа выходных кодовых последовательностей, связанных с исходными информационными кодовыми словами.
На вход кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из n двоичных символов, причем n>k.
Всего может быть N=2k различных входных и L=2n различных выходных последовательностей.
Из общего числа 2n, выходных последовательностей только N=2k. последовательностей соответствуют входным. Их называют разрешенными кодовыми комбинациями.
Остальные L-N возможных выходных последовательностей для передачи не используются. Их называют запрещенными кодовыми комбинациями.
Искажения информации в процессе передачи сводятся к тому, что некоторые из передаваемых символов заменяются другими - неверными.
Так как каждая из N=2k разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, то всегда имеется L*N возможных случаев передачи. В это число входят:
1) N=2k случаев безошибочной передачи;
2) N*(N-1)= 2k(2k -1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруженным ошибкам;
3) N*(L-N)=2k(2n - 2k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.
Следовательно, часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи составляет
N(L-N)/(N*L)=(L-N)/L=1-N/L.
Пример: Определить обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (n=k+l).
Решение : 1. Общее число выходных последовательностей составляет 2(k+1) , т.е. вдвое больше общего числа кодируемых входных последовательностей.
2. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество комбинаций, содержащих четное число единиц (или нулей).
3. При кодировании к каждой последовательности из k информационных символов добавляют один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Получение слова с нечетным числом единиц переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть опознанных ошибок составляет
или 0.5 от общего числа возможных кодовых комбинаций.
Любой метод декодирования можно рассматривать как правило разбиения всего множества-запрещенных кодовых комбинаций на N=2k непересекающихся подмножеств Mj, кажде из которых ставится в соответствие одной из разрешенных комбинаций. При получении разрещенной комбинации, принадлежащей подмножеству Мj, принимают решение, что передавалась разрещенная комбинация Аj;. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из Аj, т.е. L-N случаях.
Всего случаев перехода в неразрешенные комбинации
L(L-N)=2k (2n - 2k ).
Таким образом, при наличии избыточности любой код способен исправлять ошибки.
Отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно
(L-N)/N(L-N)=1/N=2k.
Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться конкретным кодом.
Большинство разработанных кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (или пакетов) ошибок.
Взаимно независимыми ошибками называют такие искажения в передаваемом кодовом слове символов, при которых вероятность появления любой комбинации искаженных символов зависит только от числа искаженных символов и вероятности искажения одиночного символа p .
При взаимно независимых ошибках вероятность искажения любых г символов в n- разрядной кодовой комбинации, как уже указывалось для модели двоичного симметричного канала:
Pr=pr*(1-p)(n-r)
где р - вероятность искажения одного символа; r - число искаженных символов; n- число двоичных символов кодового слова.
Если учесть, что р<<1, то в этом случае наиболее вероятны ошибки низшей кратности. Их следует обнаруживать и исправлять в первую очередь.