Устройство для декодирования кодов с к проверками на четность

 

О П И С А Н И Е (И) 4S1O84

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик (61) ф Зависимое от авт. свид-ва йвударственний комитет

Воввта Министров СССР оо делам иэаоретений и откра1тий

Опубликовано 25.11.7> Бюллетень № 43 (53) УДК 681.326.75 (088.8) Дата опубликования описания 18„О6.75

f (72) Автор . изобретения

А. В. Пастухов (71} Заявитель Институт электронных управляющих машин (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДОВ

С К ПРОВЕРКАМИ НА ЧЕТНОСТЬ ствует вектору ошибки проверочных символов кода. Так как проверочные символы могут не исправляться, то дешифратор не

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

Кроме этого, в известном устройстве дешифратор содержит элементы И по числу информационных символов кода. Каждый из элементов И имеет не меньше,чем К, вхо

I ,,дов, что также представляет известную сложность, Таким образом, известное устройство

4 декодирования повышенной надежности имеИзобретение относится к области вычи-1 сиятельной техники и касается техники передачи и переработки вычислительной иноформациии.

Известно устройство для декодирования 5 кодов с К проверками на четность, позволяющее исправлять ошибки передаваемой информации.

Известное устройство декодирования содержит схему обнаружения ошибок через 1О синдром (ненулевое значение синдрома характерезует наличие определенной ошибки в кодовом векторе), дешифратор, локализируюший место ошибки в кодовом векторе (определяющий вектор ошибки) с помощью сложе-та ния вектора ошибки с передаваемым кодовым вектором.

При независимой реализации К проверок на четность (К блоков) устройство декодирования обладает свойством самокоррек- 2О ции по отношению к одиночным отказам блоков схемы обнаружения ошибок. Это определяется тем, что значение синдрома, 1 формируемое на выходе схемы обнаружения ошибок при одиночном отказе, соответ- ® (22) Заявлено 24.02,72 (21) 1751034/18-24 (51) М. Кл. Q 06 g 11/10 с пписоединением заявки № (32)Приоритет—

451084

3 ет сложную схему обнаружения ошибки и дешифратора.

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

Это достигается тем, что устройство

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

1 в группах, причем вход каждого из трех сумматоров по модулю два группы симвоР лов кода соединен с соответствующими входами,устройства, выход подключен к соответствующему входу схемы обнаруже- 0 ния ошибок в группах, выход которой подключен ко входам дешифратора. !

На чертеже представлено устройство, в состав которого входят входы 1, 2 устройства, схема 3 обнаружения ошибок, сумматоры по модулю два группы симво- . лов кода 4 -4 логические блоки 5 и 5

1 схемы обнаружения ошибок в группах 61и

6, дешифратор 7, вход 8 блока исправ-, ления ошибок 9, вход 10 блока 9, выходы 11 устройства.

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

Любые две иэ К проверок на четность состоят из трех частей t1, Ь и С и име40 ют следующий вид ась=О

СЕ1 =0

Отсюда И= Ь = С

Каждая часть проверки есть сумма по модулю два rpynma символоь, не входящих в другие части, Тогда булева функция определит сигнал об ошибках в символах кода, соответствующих части (1

i,= QbC + 0bC (2)

Аналогично образуются сигналы об ошиб

55 ках в других группах символов.

Схема 6 реализует функции об ошибках вида (2) и функцию отсутствия ошибки в группах, например, вида

4 (3)

Р =аьс+аьс.

Следователь но, число возможных зна чений выходов схемы 6 равно четырем, .т. е, равно числу значений синдрома, определяемых возможными значениями двух проверок на четность. Но так как в схеме

3 имеется К/2 блоков, соответствущщих своим подсистемам проверок вида (1), то число возможных значений выходов схемы

3 как раз равно числу значений синдрома, определяемых возможными значениями всех

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

Устройство работает следующим образом.

На входы 2 параллельным образом поступают информационные символы кодового набора (вектора). Одновременно с ними на входы 1 параллельно поступают К проверочных символов. Далее информационные и, проверочные символы поступают на сумматоры 4 в виде соответствующих групп. При ошибочном символе кодового набора, входящем в некоторую группу, значение вы-, ходов одного из трех сумматоров 4 блока

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

В случае если на блок 5 ошибочный символ не поступает, то значения выходов соответствующих сумматоров 4 одинаковы, а на выходах блока 5 вырабатывается сигнал отсутствия ошибок в соответствующих группах символов. В результате по значению выходов схемы 3, однозначно соотвеу ствующему указанному ошибочному символу, дешифратором 7 определяется позиция ошибочного символа в кодовом наборе, Ври Поступлении сигнала с позиции ошибочного символа на один из входов 8 и

1 соответствующего ошибочного информационного символа на один иэ входов 10 блок

9 инвертирует двоичное значение символа с ошибочного на правильное.

В результате на выходы 11 поступают правильные значения информационных символов.

В случае если на входы 1 и 2 не поступают ошибочные символы (достоверная информация), то в каждом блоке 5 соответствующие сумматоры 4 формируют оди наковые значения выходов. При этом на

451084

6 выходах всех блоков 5 вырабатываются сигналы отсутствия ошибок в группах символов кода. B результате дешифратор не выдает сигнала о позиции ошибочного символа, а блок 9 не инвертирует значе- 5 шгя информационных символов. Следовательно, на входы 11 поступают правильные значения информационных символов.

В случае, если на входы 1 и 2 не поступают ошибочные символы, а один из блоков 5 находится в состоянии отказа, то все блоки 5, кроме одного, формируют сиг-, налы отсутствия ошибок. При этом блок 5, в котором произошел отказ, может сформировать на своем выходе неправильный сигнал, Однако при таких значениях на выходах схемы 4 дешифратор 7 не выдает сиг налы о позиции ошибочного символа, и, сггедовательно, на выходы 11 поступают правильные значения информационных сим20. волов.

Это объясняется следуюшим. Дешифратор

7 реаг ирует только на те значения выходов схемы 3, которые соответствуют ошибкам информационных символов для случая, 25 когда в схеме 3 не было отказа.

Рассмотренный случай с отказом будет определять такое же значение выходов схемы 3, что и в случае без отказа, когда имеется ошибка в информационном сим- во.ге, если ошибочный информаггггонный символ выходит только е те, две проверки на четность, которые соответствуют отказавп ему блоку 5.

Так как отказы могут происходить в

35 любом из блоков, то число информационных символов, при которых не выполняется условие самокоррекции в отношении одиночных отказов, при К четном равно К/2, при К нечетном это число меньше.

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

Подобному свойству удовлетворяют любые коды с исправлением одиночных ошибок, исключая коды Хэмминга, для которых необходимо укорочение длины кода.

Для различных кодов Хэмминга это определяется достаточно малыми значениями, что не накладывает практических ограничений на использование таких кодов.

Предмет изобретения

Устройство для декодирования кодов с

К проверками на четность, содержащее дешифратор и блок исправления ошибок, соединенный с выходами дешифратора и вхс дами и выходами устройства, о т л и ч а ю— ш е е с я тем, что, с целью упрощения устройства, оно содержит К/2 логических блоков, каждый пх которых включает трн сумматора по модулю два группы символов кода и схему обнаружения ошибок в группах, причем вход каждого из трех сумматоров по модулю два группы символов кода соеди, нен с соответствующими входами устройства, выход "- подключен к соответствуюшему входу схемы обнаружения оц.ибгж. в группах, выход которой подключен ко вхо дам дешифратора.

451084

Nsa. jk%0$

Подписное

Тираж

624

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 113035, Раушская наб., 4

Г!редпрнятие «Патент», Москва, Г-59, Бережковская наб., 24

Р О.Степина

Заказ аМ/О

Составитель А Жеренов

Р д Н.Ханеева оРРе Р А.Степанова