 Популярные статьи | |
| Сейчас на сайте |  Гостей: 7
На сайте нет зарегистрированных пользователей
Пользователей: 9,955
новичок: Logyattella
|
|
| 2.4.3 Блоковые коды |
Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На вход кодирующего устройства поступает последовательность из k информационных символов. На выходе ей соответствует последовательность из n двоичных символов, причём n>k. Всего может быть 2k различных входных и 2n различных выходных кодовых комбинаций. Из общего числа 2n выходных последовательностей только2k соответствуют входным. Эти комбинации называют разрешимыми.
Остальные 2n - 2k возможных выходных последовательностей для передачи не используются. Искажение информации в процессе передачи сводится к тому, что некоторые из передаваемых символов заменяются другими – неверными. Так как каждая из 2k разрешённых комбинаций в результате действия помех может трансформироваться в любую другую, то всего имеется 2k *2n возможных случаев передачи. В это число входят:
- 2k случаев безошибочной передачи;
- 2k (2k –1) случаев перехода в другие разрешённые комбинации, что соответствует необнаруживаемым ошибкам;
- 2k (2n -2k )случаев перехода в неразрешённые комбинации, которые могут быть обнаружены.
Следовательно, часть обнаруживаемых кодовых комбинаций от общего числа составляет:
. (2.4.1)
Степень отличия любых двух кодовых комбинаций характеризуется расстоянием между ними в смысле Хемминга или просто кодовым расстоянием. Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме двух кодовых комбинаций по модулю 2.
10011101
11000101
01011000 , d=3.
Минимальное расстояние, взятое по всем парам кодовых разрешённых комбинаций, называется минимальным кодовым расстоянием. Декодирование после приёма может производиться таким образом, что принятая кодовая комбинация отождествляется с той разрешённой, которая находится от неё на наименьшем кодовом расстоянии. Такое декодирование называется декодированием по методу максимального правдоподобия.
Очевидно, что при d=1 все кодовые комбинации являются разрешёнными. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешённую комбинацию. Это случай безызбыточного кода, не обладающего корректирующей способностью. Если d=2, то ни одна из разрешённых кодовых комбинаций при одиночной ошибке не переходит в другую разрешённую кодовую комбинацию. Код обнаруживает одиночные ошибки, а также другие ошибки нечётной кратности. В общем случае, при необходимости обнаруживать ошибки кратности до r включительно, минимальное Хеммингово расстояние должно быть, по крайней мере, на единицу больше r
. (2.4.2)
Для исправления одиночной ошибки каждой разрешённой комбинации необходимо сопоставить подмножество запрещённых кодовых комбинаций. Чтобы эти подмножества не пересекались, хеммингово расстояние между разрешёнными кодовыми комбинациями должно быть не менее трёх. При n=3 за разрешённые кодовые комбинации можно принять 000 или 111. тогда разрешенной кодовой комбинации 000 необходимо приписать подмножества запрещённых кодовых комбинаций 001, 010, 100, образующиеся в результате возникновения одиночной ошибки в комбинации 000. Подобным же образом комбинации 111 необходимо приписать подмножества запрещённых кодовых комбинаций: 110, 011, 101. образующиеся в результате одиночной ошибки в комбинации 111.
В общем случае для обеспечения возможности исправления всех ошибок кратности до s включительно при декодировании по методу максимального правдоподобия каждая из ошибок должна приводить к запрещённой комбинации, относящейся к подмножеству исходной разрешённой кодовой комбинации. Поскольку указанные подмножества не должны пересекаться, минимальное хеммингово расстояние между разрешёнными кодовыми комбинациями должно удовлетворять соотношению:
. (2.4.3)
Нетрудно убедиться в том, что для исправления всех ошибок кратности s и одновременно обнаружения всех ошибок кратности r s минимальное хеммингово расстояние нужно выбирать из условия:
. (2.4.4)
Данные формулы справедливы для случая взаимно независимых ошибок и дают завышенные значения для dmin при помехе, коррелированной с сигналом. В реальных каналах связи длительность импульса помехи часто превышает длительность символов. При этом искажаются несколько расположенных рядом символов комбинации. Ошибки такого рода получили название пачек ошибок, или пакетов ошибок. Для пачек ошибок при той же корректирующей способности минимальное хеммингово расстояние может быть меньше. Однако каждый конкретный корректирующий код не гарантирует исправление любой комбинации ошибок.
Если характер и уровень помехи отличаются от предполагаемых, эффективность использования кода резко снижается. Применение корректирующего кода не может гарантировать безошибочного приёма, но даёт возможность повысить вероятность получения на выходе правильного результата.
Одной из основных характеристик корректирующего кода является избыточность кода, указывающая степень удлинения кодовой комбинации для достижения определённой корректирующей способности. Если на каждые n символов выходной последовательности приходится k информационных и n-k проверочных, то относительная избыточность кода:
; (2.4.5)
. (2.4.6)
Коды, обеспечивающие заданную корректирующую способность при минимально возможной избыточности, называются оптимальными. Найдём для оптимального кода величину Q – наибольшее возможное число разрешённых комбинаций n- значного двоичного кода, обладающего способностью исправлять взаимно независимые ошибки кратности до s включительно. Это равносильно отсеканию числа комбинаций, кодовое расстояние между которыми не менее d=2s+1.
Общее число различных исправляемых ошибок для каждой разрешённой комбинации составляет:
. (2.4.7)
Каждая из таких ошибок должна приводить к запрещённой комбинации, относящейся к подмножеству данной разрешённой комбинации. Совместно с этой комбинацией подмножество включает
. (2.4.8)
Однозначное кодирование возможно лишь в том случае, если названные подмножества не пересекаются. Так как общее число различных комбинаций n- значного двоичного кода 2n , число разрешённых комбинаций не должно превышать:
, (2.4.9)
или
. (2.4.10)
Эта верхняя оценка найдена Хеммингом. Коды, для которых в приведённом соотношении достигается равенство, называются плотноупакованными.
|
|
| Комментарии |
| Добавить комментарий |
|
Пожалуйста залогиньтесь для добавления комментария.
|
| Рейтинги |
|
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
|
|
| Гость |
Вы не зарегистрированны? Нажмите здесь для регистрации.
Забыли пароль? Запросите новый здесь.
|
| Мини-чат | Вам необходимо залогиниться.
Нет присланных сообщений.
|
|
