Тема: Коды с обнаружением и исправлением ошибок.
План лекции.
1..
Правила составления корректирующих кодов
Если кодовые комбинации составлены так, что они отличаются друг от друга на кодовое расстояние d ≥3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности обнаруживать и исправлять ошибки.
Корректирующие коды делятся на систематические и несистематические.
Систематически или линейным, кодом называется код, имеющий постоянную длину и четкое деление всех кодовых элементов на информационные k и контрольные m элементы, занимающие определенные места в комбинациях.
Составление корректирующих кодов производится по следующему правилу. Сначала определяется количество контрольных символов m, которое следует добавить к данной кодовой комбинации, состоящей из k информационных символов. Далее устанавливается место, где эти контрольные символы должны быть расставлены в комбинации, и их состав, то есть является ли данный контрольный символ 1 или 0. На приеме обычно применяется проверка на четность определенной части разрядов.
Эти коды позволяют обнаруживать и исправлять все одиночные ошибки (при d=3), а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки ( при d=4), но не исправлять их.
Рассмотрим код Хэмминга, исправляющий все одиночные ошибки.
В качестве исходного кода берется двоичный код на все сочетания с числом информационных символов k, к которому добавляется m контрольных символов. Таким образом, общая длина закодированной комбинации n=k+m.
|
|
|
Рассмотрим последовательность кодирования и декодирования по методу Хэмминга.
Определение числа контрольных символов
Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с шумами может быть или искажен любой из n символов кода, или слово может быть передано без искажений. Таким образом, может быть n+1 вариантов искажения (включая передачу без искажений).Используя контрольные символы, мы должны различать все n+1 случаев.
С помощью m контрольных символов можно описать 2m событий. Значит, должно быть выполнено условие:
2m ≥ n+1=k+m+1
Задаем m, определим k: 2m ≥ k+m+1
22 ≥ k+2+1, k=1
23 ≥ k+3+1, k=2, 3, 4
Таблица 18.1
| Информационные разряды, k | 1 2 3 4 5 6 7 8 9 10 11 12 13 … 26 |
| Контрольные разряды, m | 2 3 3 3 4 4 4 4 4 4 4 5 5 5 |
Размещение контрольных символов
В принципе местонахождение этих символов значения не имеет: их можно приписывать и перед информационными словами, и после них, и чередуя информационные символы с контрольными. Однако произвольное месторасположение контрольных символов будет затруднять проверку принятого кода. Поэтому для удобства обнаружения искаженного символа целесообразно размещать их на местах кратных степени 2, то есть в позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, для 7-элементной закодированной комбинации можно записать:
|
|
|
23, k =4
m=3, m1, m2, k4, m3, k3, k2, k1 (18.1)
где k4 – старший или четвертый разряд исходной кодовой комбинации двоичного кода, подлежащей кодированию.
Определение состава контрольных символов
Выявление того, какой символ должен стоять на контрольной позиции (1 или 0), производится по коэффициентам при помощи проверки на четность. Рассмотрим определение коэффициентов на примере комбинации (18.1).
Таблица 18.2
Дата добавления: 2018-05-12; просмотров: 299; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!