Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

зующей данного кода. Для нашего примера определяющая матрица

будет иметь вид

000 101

001 010

010 100

101000

010 001

100 010

Часто при анализе циклических кодов кодовые комбинации удоб­ но представлять в виде многочленов, у которых показатели степени х соответствуют номерам разрядов, а коэффициенты при х равны 0 или 1 в зависимости от того, стоит ли 0 или 1 в разряде кодовой комби­ нации, которую представляет данный многочлен. Так, комбинации кода нашего примера могут быть определены в виде многочленов:

Нетрудно заметить, что циклический сдвиг кодовой комбинации ана­ логичен умножению соответствующего многочлена на х:

(х2 4- 1)х — х3 4- х да 001 010; (х3 4- х ) х —'х* 4- х2 да 010 100; (х4 4- х2) х = х5 + х3 да 101 000.

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

Другими словами, существует принципиальная возможность по­ лучения любой кодовой комбинации циклического кода путем умно­ жения соответствующим образом подобранного образующего многочле­ на на некоторый другой многочлен. Однако так как операции умноже­ ния и деления по модулю 2 сводятся, в конце концов, к операции сложения (см. тему 7), то можно сказать, что любой многочлен цикли­

130

Если же при делении комбинации циклического кода на образую­ щий многочлен будет получен остаток, то, значит, либо в коде произо-

Тоблица 25

Основные характеристики циклических кодэв, исправляющих одиночные и обнаруживающих все одиночные и двойные ошибки

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

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

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

1 Н а п о м и н а е м , ч т о д е л и т е л ь п о д п и с ы в а е т с я п о д д е л и м ы м т а к , ч т о б ы с о в п а д а л и с т а р ш и е р а з р я д ы .

пи и контрольных пк символов заданы табл. 25 (сравните с табл. 21 для кода Хэмминга). Там же приведены и образующие многочлены для кодов различной длины.

Вернемся, однако, к процедуре нахождения остатков деления и построения полной образующей матрицы циклического кода. Предпо­ ложим, необходимо передать 10 информационных разрядов так, что­ бы при этом были обнаружены все одиночные и двойные ошибки. По табл. 25 выбираем ближайшее значение пи >- 10. Согласно табл. 25, таким значением будет пя = 11. При этом пк = 4, а п = 15. Там же выбираем образующий многочлен х* + х3 4- 1.

Полную образующую матрицу обычно строят из единичной транс­ понированной матрицы в канонической форме и дополнительной матри­ цы С„и;„к, соответствующей проверочным разрядам. Транспонирован­

ная матрица для пя = 11 имеет вид

0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0 0 0 0

Дополнительная матрица может быть построена по остаткам деления комбинации в виде единицы с нулями (последней строки единичной транспонированной матрицы) на выбранный образующий многочлен:

11001

0001

1 3 2

. f

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

0 0 0 0 0 0 0 0 0 0 1 1 0 0 1

0 0 0 0 0 0 0 0 0 1 0 1 0 1 1

0 0 0 0 0 0 0 0 1 0 0 1 1 1 1

Cl5;ll = 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 I 0

0 0 0 0 0 1 0 0 0 0 0 0 1 0 1

0 0 0 0 1 0 0 0 0 0 0 1 0 1 0

0 0 0 1 0 0 0 0 0 0 0 1 1 0 1

0 0 1 0 0 0 0 0 0 0 0 0 0 1 1

0 1 0 0 0 0 0 0 0 0 0 0 1 1 0

1 0 0 0 0 0 0 0 0 0 0 1 1 0 0

В качестве неприводимого многочлена можно было бы взять, например, и х* + х 1. Тогда мы нашли бы несколько видоизменен­ ную определяющую матрицу, которая отличалась бы от полученной выше не самими остатками, а лишь их порядком:

0 0 0 1 0 0 0 0 0 0 0 1 1 1 0

После того как построены полные образующие матрицы, не пред­ ставляет собой труда выбрать любую из разрешенных комбинаций данного кода. Общее число комбинаций для кода с 11 информацион­ ными разрядами равно 211.

133

В качестве примера выпишем две кодовые комбинации, имеющие единицы, первая в 1, 2, 7, 9, вторая в 3, 5, 6, 10 и 11 информационных разрядах. Для этого достаточно сложить по модулю 2 строки обра­ зующей матрицы с теми же порядковыми номерами, считая снизу вверх:

1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 Q 0 0 0 1 1 0 1-

@ 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1

0 0 1 0 0 0 0 0 0 0 0 1 1 1 1

0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 @ 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0

Код, построенный при помощи матриц С+ц и С\5;ц, может обна­ руживать все одиночные и все двукратные ошибки, а также пачки

ры сдвига с обратной связью через сумматор по модулю 2. На рис. 30 представлена схема такого регистра сдвига, на которой Тг — Тп — ячейки И в случае тиратронного регистра сдвига

регистра. Выход сумматора заведен на вход регистра сдвига. Поэтому в первом каскаде регистра всегда записан результат сложения по модулю 2 (естественно, после-того, как на сумматоре появится первый результат сложения).

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

134