Составление таблиц опознавателей.

↑

▷ Содержание

⇐ ПредыдущаяСтр 11 из 21Следующая ⇒

Рассмотрим случай обнаружения одиночных ошибок. Допустим Q=15 тогда , с другой стороны:

Из этого выражения можно получить следующую таблицу:

Составим таблицу соответствия вектора ошибки и опознавателей КК n=7:

Определение проверочных равенств.

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

Тогда проверка №1:

.

Проверка №2 – аналогично, во втором разряде опознавателя:

.

Проверка №3 – аналогично в третьем разряде определителя:

.

Теперь нужно определить NN проверочных и информационных разрядов в КК. Нужно чтобы контрольные символы входили во все проверки только один раз. Это обеспечит независимость декодирования, т.е. значения контрольных разрядов может быть определено решением одного из проверочных равенств:

то получим размещение:

Пример. Код Хэмминга d=3, n=7, k=4, m=3 KK = 1011

то выходная КК:

Проверка:

Опознаватель = 101 > ошибка в разряде №5

Вектор ошибки: 0000100

Исправление ошибки: 0110111

0000100

Исправленная КК: 0110011

Коды Хэмминга.

Эти коды являются примером линейных кодов, исправляющих одну единственную ошибку. Длина блока кодов удовлетворяет соотношению n=2^(n-k)-1, где n-k количество проверочных символов. Например, при n-k=3 получаем код (7,4).

Коды Рида-Соломона.

Коды РС относятся к классу недвоичных кодов БЧХ. В кодере сообщение, состоящее из k q-ичных символов, выбираемых из алфавита, содержащего q=2^m символов, преобразуется в кодовое слово РС- кода, содержащее n двоичных символов. Поскольку обычно входные и выходные алфавиты равны степени 2, то входные и выходные символы могут быть представлены m- разрядными двоичными словами. Таким образом, входное сообщение можно рассматривать как km- разрядное слово, а выходное кодовое слово – как nm- разрядное двоичное слово. Длина кода РС равна n=q-1. Если исправляющая способность кода равна t ошибочным символам, то имеет место соотношение n-k=2t. Коды РС существуют при , а их расширение имеют длины блока: n= q и n= q+1.

Код Голея.

Этот код относится к числу наиболее интересных. Он позволяет исправить ошибки высокой кратности (t>1) и является также совершенным кодом. Код Голея (23,12) является циклическим и исправляет все конфигурации ошибок, кратность которых не превышает трех. С кодом Голея (23,12) связан код (24,12), который образуется добавлением к кодовым словам кода дополнительного проверочного символа. Коды (23,12) и (24,12) имеют минимальное кодовое расстояние, равное соответственно 7 и 8. Поэтому код (24,12), кроме исправления ошибок кратности 4 при незначительном изменении кода обнаруживает ошибки выше кратности 4. Код (24,12) относится к числу наиболее распространенных.

Непрерывные коды.

Из непрерывных кодов, исправляющих ошибки, наиболее известны коды Финка-Хагельбаргера, в которых контрольные символы образуются путем линейной операции над двумя или более информационными символами. Принцип построения этих кодов рассмотрим на примере простейшего цепного кода. Контрольные символы в цепном коде формируются путем суммирования символов, расположенных один относительно другого на определенном расстоянии:

e_ik=c_i+c_k; e_i+1, _k+1=c_i+1+c_{k+1; …}

Расстояние между информационными символами l=k-i определяет основные свойства кодов и называется шагом сложения. Число контрольных символов при таком способе кодирования равно числу информационных символов, поэтому избыточность кода æ=0,5. Важное преимущество непрерывных кодов состоит в их способности исправлять не только одиночные ошибки, но и группы ошибок. Если задержка контрольных символов выбрана равной 2l, то можно показать, что максимальная длина исправляемого пакета ошибок также равна 2l при интервале между пакетами 6l+1. Таким образом, возможность исправления длинных пакетов связана с увеличением шага сложения l, а следовательно, и с усложнением кодирующих и декодирующих устройств.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии