Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

п = 3х , k = 2' , d = 2х .

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

4-3. КОРРЕКТИРУЮЩИЕ КОДЫ ДЛ Я АСИММЕТРИЧНЫХ КАНАЛОВ

В настоящее время можно выделить два основных направления синтеза корректирующих кодов для обна­ ружения и исправления асимметричных ошибок: 1) ко­ ды с постоянным весом; 2) коды с суммированием.

Исторически раньше были предложены коды с по­ стоянным весом, которые характеризуются тем, что количество единичных символов для любого кодового слова длины п разрядов постоянно и равно т. Такие коды принято обозначать «от из п», количество кодовых

слов не превышает величины ^ ^ j • Например, код «4 из 8» используется в некоторых системах и позволяет закодировать ^4 ^ =70 различных слов (букв). В неко-

торых ЦВМ, оперирующих с .цифрами в двоичио-деся- тичном коде, для помехоустойчивого кодирования деся­ тичных цифр использовался, в частности, код «2 из 5». В этом случае десятичные цифры могут быть закодиро­ ваны, как показано в табл. 4-7. Использование такого кода возможно в трактах хранения и передачи инфор­ мации, но выполнение арифметических операций в этом коде сопряжено с определенными трудностями. Для выполнения арифметических операций более удобным является код «2 из 7», два варианта построения кото­ рого представлены в табл. 4-8.

Коды с постоянным весом позволяют обнаружить любую одиночную ошибку. Их возможность обнаружи­

рии канала. Так, в полностью асимметричном канале обнаруживается ошибка произвольной кратности, но в ДСК возможно, например, возникновение необнаруживаемых ошибок кратности 2 (если в одном из разря­ дов произошел переход 0—И, а в другом 1—ИЗ).

Оценить сверху вероятность пропуска двойной ошиб­ ки можно следующим образом. Пусть передача инфор­ мации производится по ДСК без памяти и появление любого кодового слова равновероятно. Из последнего допущения следует равновероятность появления симво-

114

лов 1 и 0 на любой позиции слова и искомая вероят­ ность

Количество разрядов я, которое необходимо для представления двоичных /г-разрядных слов с помощью

Для исправления одиночных ошибок в кодовых сло­ вах с постоянным весом предложен следующий способ

зом относительно одной из (лг+1) переменных, если т остальных известны. Действительно, если одиночная ошибка возникла в той части слова, вес которой дол­ жен оставаться постоянным, то номер искаженного раз­ ряда определяется из сравнения по модулю п

'm—1

R — ^ <Xj-, если вес слова уменьшился на единицу;

^' т-Ы

J] o.i — R, если вес слова увеличился на единицу.

Если ошибка произошла в контрольных разрядах, то вес соответствующей части слова равен т и значение ошибки вычисляется из сравнения

т

AR = R* — щ по модулю п,

»=1

где R* — искаженный контрольный код.

икодовое слово равно 10110001100. Пусть получено слово

10110000100, тогда номер ошибочного разряда равен:

/ = 4 — 5 = — 1 = 7 по модулю 8,

и поскольку вес слова уменьшился на единицу, то в седьмом раз­ ряде необходимо записать 1.

Рассматриваемые ниже корректирующие коды с сум­ мированием относятся к числу разделимых и конструи­ руются следующим образом [Л. 36, 37].

Пусть Vh — множество ^-разрядных двоичных инфор­ мационных слов. Разобьем Vh на непересекающиеся подмножества W0, Wi, . . . , Wft такие, что элементы каж­

116

r=log2 (/+l) =log2 /V.

рования контрольных разрядов, исключающий возмож­ ность пропуска ошибки. Например, для получения кор­ ректирующего кода, обнаруживающего любую асиммет­ ричную ошибку" кратности 2 или менее, требуется два дополнительных разряда, в которые запишем остаток от деления количества единиц на информационных по­ зициях на N=3. Тогда следующее слово является кодо­ вым: 00...00101. Легко видеть, что возникновение двой­ ной асимметричной ошибки (типа 1—Я)) переводит исходное слово в слово 00 ... 00000, которое также явля­ ется кодовым. Чтобы исключить это нежелательное яв­ ление, кодирование контрольного числа должно выпол­ няться с соблюдением условия: если возникающие асим­

да используется обратный код остатка от деления ко­

контрольного кода используется остаток от деления количества нулей на информационных позициях на мо­ дуль N.

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

117