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

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

Согласно выражению (95),

125

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

Для вычисления основных параметров кода задается количество либо информационных символов, либо информационных комбинаций —

N = 2"и. При помощи формул (96) и (98) вычисляют п и пк. Соотно­

проверочный коэффициент аъ втор

126

Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу: в первую проверку входят коэффициенты, которые содержат 1 в младшем разряде, т. е. а1г а3, аъ, а7, а9, аи и т. д.; во вторую проверку — коэффициенты; которые содержат 1 во втором разряде, т. е. а.2, а3, а8, а7, а10, ап и т. д.; в третью проверку — коэф-

42, . . .

фициенты, которые содержат 1 в третьем разряде, и т. д. Номера про­ верочных коэффициентов соответствуют номерам проверочных по­ зиций, что позволяет составить общую таблицу проверок (табл. 22). Рассмотрим конкретный пример.

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

четна. Во второй разряд номера ошибочной позиции записываем 1. Третья проверка:

127

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

Таблица 24

Код, исправляющий одиночную и обнаруживающий двойную ошибки

для всей строки в целом. Чтобы осуществить такую проверку, следует к каждой строке кода добавить контрольные символы, записанные в дополнительной колонке (табл. 24, колонка 8). Тогда в случае одной ошибки проверки по позициям укажут номер ошибочной позиции, а проверка на четность — на наличие ошибки. Если проверки позиций укажут на наличие ошибки, а проверка на четность не фиксирует ошибки, значит в коде две ошибки.

Определением общего выражения для длины кодовой комбинации в кодах, обнаруживающих и исправляющих ошибки, занимались мно­ гие ученые. Однако точного выражения еще не найдено. Установлены лиЩь значения верхней и нижней границ количества добавочных символов, например, [8, 39, 42].

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

В свое время Р. Фанно и К. Шеннон [36, 47] доказали, что су­ ществуют коды, которые обеспечивают в стационарных каналах с ко­

128

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

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

Циклические коды строятся по принципу так называемого неопти­ мального декодирования, согласно которому исправлению подлежат не обязательно все возможные ошибки, а лишь ошибки, принадлежа­ щие некоторому фиксированному множеству. Неоптимальное деко­ дирование, с одной стороны, иногда не полностью использует возмож­ ность кодов, а с другой стороны, значительно упрощает процесс деко­ дирования. Циклические коды благодаря ряду своих свойств часто имеют преимущества перед сопоставимыми неалгебраическими кодами. Так, простейший код с проверкой на четность и циклический код с кодовым расстоянием между двумя любыми, комбинациями не мень­ ше двух казалось бы должны иметь одинаковую корректирующую способность. Однако циклический код обладает большей избыточностью за счет того, что возникает возможность обнаружения, кроме одиноч­ ных ошибок, и части парных ошибок, а это позволяет повысить про­ цент обнаруженных ошибок с 50% до 75% для кода с одним провероч­ ным разрядом [35].

Циклические коды получили свое название благодаря тому, что

Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Например, совокупность комбинаций циклического кода из образующей 000101: 000101, 001010, 010100, 101000, 010001, 100010. Дальше комбинации будут повто­ ряться.

Циклический код можно представить в виде матрицы, причем все ее строки могут быть получены путем циклического сдвига обра­