Лекции по количественной оценке информации (стр. 9 из 11)

в) производят циклический сдвиг принятой комбинации

влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на . Если в результате этого повторного деления то делимое суммируют с остатком, затем

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

, то

д) повторяют операцию пункта в) до тех пор, пока не будет

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

е) производят циклический сдвиг вправо ровно на столько разрядов,на сколько была сдвинута суммируемая с последним остаткомкомбинация относительно принятой комбинации. В результате получим исправленную комбинацию[18].

II. Коды, обнаруживающие трехкратные ошибки,

.

1. Выбор числа корректирующих разрядов производитсяиз соотношения

или

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

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

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

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

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

5. Обнаружение ошибок производится по остаткам от деления принятой комбинации

на образующий многочлен . Если остатка нет, то контрольные разряды отбрасываются и информационная часть кода используется по назначению. Если в результате деления получается остаток, то комбинация бракуется. Заметим, что такие коды могут обнаруживать 75% любого количества ошибок, так как кроме двойной ошибки обнаруживаются все нечетные ошибки, но гарантированное количество ошибок, которое код никогда не пропустит, равно 3.

Пример: Исходная кодовая комбинация - 0101111000, принятая - 0001011001 (т. е. произошел тройной сбой). Показать процесс обнаружения ошибки, если известно, что комбинации кода были образованы при помощи многочлена 101111.

Решение:

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

III. Циклические коды, исправляющие две и большее количество ошибок,

Методика построения циклических кодов с

отличается от методики построения циклических кодов с только в выборе образующего многочлена. В литературе эти коды известны как коды БЧХ (первые буквы фамилий Боуз, Чоудхури, Хоквинхем - авторов методики построения циклических кодов с ).

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

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

Для исправления числа ошибок

еще не достаточно условия, чтобы между комбинациями кода минимальное кодовое расстояние . необходимо также, чтобы длина кода удовлетворяла условию

(79)

при этом п всегда будет нечетным числом. Величинаh определяет выбор числа контрольных символов

и связана с и s следующим соотношением:

(80)

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

(81)

где

являетсяодним из сомножителей, на которые разлагается число п.

Соотношения между

, С иh могут быть сведены в следующую таблицу

№ п/п	h		C
1 2 3 4 5 6 7 8 9 10	3 4 5 6 7 8 9 10 11 12	7 15 31 63 127 255 511 1023 2047 4095	1 5; 3 1 7; 3; 3 1 17; 5; 3 7; 3; 7 31; 11; 3 89; 23 3; 3; 5; 7; 13

Например, при h = 10 длина кодовой комбинации может быть равна и 1023

и 341 (С = 3), и 33 (С =31), и 31 (С = 33), понятно, что п не может быть меньше Величина С влияет на выбор порядковых номеров минимальных многочленов, так как индексы первоначально выбранных многочленов умножаются на С.

Построение образующего многочлена

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

(82)

Порядок многочлена используется при определении числа сомножителей

. Например, если s = 6, то . Так как для построения используются только нечетные многочлены, то ими будут: старший из них имеет порядок . Как видим, число сомножителей равно 6, т. е. числу исправляемых ошибок. Таким образом, число минимальных многочленов, участвующих в построении образующего многочлена,