Устройство для исправления пакетных ошибок модульными кодами

 

Изобретение относится к вычислительной технике. Его использование в системах обработки цифровой информации позволяет повысить достоверность работы. Устройство содержит генератор 1 синдрома, буферный регистр 3, счетчик 5 импульсов, дешифратор 6, триггер 7, элементы ИЛИ 8,13 и элементы И 12,14. Благодаря введению переключателя 2, ключевого элемента 4, R сумматоров 9 по модулю два, N мультиплексоров 10, блока 11 контроля и триггера 15 в устройстве обеспечивается исправление всех модульных ошибок для выбранного кода. 5 ил.

„.ЯУ„„1596465

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

А1 (51)5 Н 03 М 13 02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

Н А BTOPGHOMY СВИДЕТЕЛЬСТВУ (21) 44-33717/24-24 (22) 30.05.88 (46) 30.09.90. Бюл. Р 36 (72) H.E Платонов, А.Н. Дядюнов, А.Н. Дятлов, А.В. Кантор и М.Л. Платонова (53) 681.326.7 (088.8) (56) Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. M.: Мир, 1976, с. 400-402, рис. 11.3.

Авторское свидетельство СССР

1Г 1522414, кл. Н 03 М 13/02, 15.02.88, (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ПАКЕТ. НЫХ ОШИБОК МОДУЛЬНЫМИ КОДАМИ

2 (57) Изобретение относится к вычислительной технике. его использование в системах обработки цифровой информа« ции позволяет повысить достоверность рабо1ы. Устройство содержит генератор 1 синдрома, буферный регистр 3 счетчик 5 импульсов, дешифратор 6, триггер 7, элементы ИЛИ 8,. 13 и элементы И 12, 14. Благодаря введению переключателя 2, ключевого элемента 4, r сумматоров 9 по модулю два,,п мультиплексоров 10, блока 11 контроля и триггера 15 в устройстве обеспечивается исправление всех модульных ошибок для выбранного кода. 5 ил.

15 96465

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

Цель изобретения — повышение достоверности работы.

На фиг. 1 приведена функциональная схема устройства; на фиг. 2 — выполнение генератора синдрома; на фиг.3— проверочная матрица кода (24,16); на фиг. 4 — выполнение блока контроля;

»а фиг. 5 — временные диаграммы.

Устройство содержит генератор 1 синдрома, переключатель 2, буферный регистр 3, ключевой элемент 4, счетчик 5 импульсов, дешифратор 6, первый триггер 7, первый элемент 8 ИЛИ, сумматоры 9 по модулю два, мультиплексоры 10, блок контроля 11, первый элемент 12 И, второй элемент 13 ИЛИ, второй элемент 14 И и второй триггер

15. Нефиг. 1 обозначены вход 16 начальной установки, тактовый вход 17., информационный вход 18, информационные выходы 19, контрольный выход 20 и выход 2f готовности.

Генератор 1 синдрома содержит (фиг. 2) ячейки 22 памяти (триггеры) и сумматоры 23 по модулю два, подключение которых определяется порождающим многочленом входного кода (n, n - r). На фиг, 2 показано ко»крет1тое выполнение генератора 1 синдрома для многочлен,а q (х)= х + х +х + 1 при числе отброшенных символов S=36: для кода (24, 16). Проверочнай матрица для этого же кода приведена на фиг. 3 (здесь и = 24).

Блок 11 контроля содержит (фиг.4) г многовходовых сумматоров 24 по мо40 дулю два и элемент 25 ИЛИ-НК (r— количество ттроверочньтх разрядов входного кода). Подключение входов каждого сумматора 24 ко входам

45 блока 11 (к выходам мультиплексоров 10) определяется соответствующей строкой проверочной матрицы (фиг. 3) . Например, для кода (24, 16) к первому сумматору 24 по модулю два надо подключить выходы мультиплексоров 10 с но50 мерами 1, 2, 4, 5, 8, 9, 10, 11, 14 и17итд, На фиг. 5 обозначены следующие сигналы: а — импульсы начальной установки на входе 16; б — тактовые импуль- >5 сы на входе 17; в — входной код на входе 18; г — смена состояний в генераторе 1 синдрома; д — переключение переключателя 2; е — смена состояний н буферном регистре 3; ж — тактовые импульсы на выходе ключевого элемента 4; з — смена состояний счетчика 5 импульсов.; и — импульсы на выходе дешифратора 6; к — переключение триггера 7; л — импульсы на выходе первого элемента 8 ИЛИ; м — смена состояний в сумматорах 9 по модулю дна; н переключение мультиплексоров 10; о сигнал на выходе блока 1f контроля; и — сигнал на контрольном выходе 20; р — сигнал на выходе 21 готовности; с — сигнал на выходе второго элемента 14 И; т — сигнал на выходе второго триггера 15.

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

Выход из строя одной микросхемы вызывает появление модульного пакета ошибок длиной b 4 в определенном модуле слова. Для исправления подобных ошибок применяют так называемые модульные коды, среди которых важное место занимают циклические модульные коды. ../

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

5 159

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

В начальный момент времени на вход

16 начальной установки приходит импульс, который устанавливает в исходное состояние триггеры 7, 15, счетчик

5, буферный регистр 3 и генератор синдрома. Нулевой потенциал присутствует на выходах всех элементов устройства (фиг. 5).

Далее начинается фаза формирования синдрома ошибки. На выход 18 устройст:ва пос..упает последовательно кодовое слово по одному символу за такт. Тактовые импульсы подаются со входа 16 на вход ключевого элемента 4 и проходят через него на блоки 1, 3, 5 и

11, так как на входе управления элемента 4 присутствует разрешающий нулевой потенциал.

По переднему фронту тактовых импульсов информация заносится в генератор 1 синдрома и через переключатель 2 — в буферный регистр 3.

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

Этот же нулевой потенциал, поданный на первый вход первого элемента 12 И, приводит к удержанию нулевого потенциала на контрольном выходе 20 и выходе 21 готовности. Счетчик 5 по заднему фронту импульсов, поступающих на его счетный вход, меняет свое состояние. Дешифратор 6 анализирует двоичный ход на выходе счетчика 5 и после отсчета п импульсов на его выходе появляется импульс, который через первый элемент 8 ИЛИ обнуляет счетчик 5 и переводит первый триггер 7 в единичное состояние ° Переход триггера 7 в единичное состояние означает завершение фазы формирования .синдрома ошибки. Кодовое слово записано в буферный регистр 3, а в генераторе 1 ,синдрома находится синдром ошибки.

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

Х вЂ” слосо принято без ошибок. При этом в генераторе 1 синдрома находится нулевая комбинация, которая, поступая на вторые входы соответствую6465 6 щнх сумматоров 9 по модулю два, не изменяет значения символов кодового слова, поступающих на первые входы этих сумматоров 9 с выходов буферного регистра 3. Мультиплексоры 10 выдают на своих выходах принятое слово без изменений. Блок контроля 11 проверяет это слово и при отсутствии ошибок на его зыходе появляется единичный потенциал, который вместе с единичным потенциалом с выхода первого триггера 7 формируют единичный потенциал на выходе элемента 12 И и на контрольном выходе 20. Единица на этом выходе

20 означает отсутствие ошибок. Единичный потенциал с выхода элемента

12 И поступает на вход второго элемента 13 ИЛИ и вызывает появление на вы20 ходе 21 готовности единичного потенциала, который означает, что обработка слова закончена. Единица с выхода элемента,3 ИЛИ закрывает ключевой элемент 4 и внешние тактовые импуль 25 cb> не проходят черех него, что вызывает неизменное состояние всех элементов устройства до прихода нового импульса чачальной установки. Таким образом, пользователь получает с вы30 хода устройства кодовое слово, признак готовности и признак отсутствия ошибок.

II — слово принято с ошибками, ошибки исправимы данным кодом. В генераторе 1 синдрома формируется ненулевая комбинация, которая поступает на вторые входы сумматоров 9 и из,меняет значения символов кодового слова, поступающих на первые входы этих сумматоров 9 с выходов буферного регистра 3. Мультиплексоры 10, управляемые по адресным входам счетчиком 5, переключаются по заднему фронту тактовых импульсов таким образом, что

45 несмотря на сдвиги информации в герераторе 1 синдрома и буферном регистре 3, порядок расположения символов кодового слова остается неизменным.

Блок контроля 11 стробируемый тактовыми импульсами, проверяет измененное кодовое слово на отсутствие ошибок. Если изменение было сделано неправильно, на выходе блока контроля

11 остается нулевой потенциал, Сле55 дующий тактовый импульс циклически сцвигает инфармацию в буферном регистре 3 и генераторе синдрома 1. Сумматоры 9 по модулю два изменяют другие символы слова в соответствии со сдви1596465 нутым синдромом, а блок контроля 11 проверяет правильность коррекции. До-., пустим, что на некотором К-м такте (K п) комбинация ошибок в слове совпала с синдромом, хранящимся в гене5 раторе 1 синдрома. Тогда сумматоры 9 инвертируют ошибочные символы, а блок контроля 11 выдает единицу на своем выходе. Как и в предыдущем случае, появление единицы на выходе блока контроля 11 вызывает закрытие ключевого элемента 4, что фиксирует относи,тельное положение кодового слова и синдрома ошибки. На выходах мультиплексоров 10 присутствует исправленное слово, а на выходах 20 и 21 — единичные потенциалы, означающие отсутствие оишбок и конец обработки слова.

Описанная ситуация показана левой по- 20 ловиной на фиг. 5.

III — слово принято с ошибками, которые неисправимы данным кодом. Работа устройства аналогична описанной, по блок контроля 11 не выдаст едини- 25 цы при лобом относительном положении ,слова и синдрома. Кгпочевой элемент 4 остается открытым до тех пор, пока в фазе исправления через него не пройдет и тактовых импульсов. Кодовое сло-30 во занимает при этом в буферном регистре 3 первоначальное положение.

Срабатывает дешифратор 6, появление импульса на выходе которого совместно с единицей на выходе первого триг- гера 7 вызывает переход s единичное состояние второго триггера 15, единица с выхода которого проходит через элемент t3 ИЛИ иj закрывает элемент

4, заФиксировав состояние устройства,:, 40

На выходе 21 готовности появляется сигнал конца обработки, а на выходе

20 остается нулевой потенциал, что * означает неисправимость ошибок в сло- : ве (правая половина фиг. 2) .

Для декодирования нового слова надо подать сигнал начальной установки и далее работа устройства повторяется.

ПРогРаммные испытания для модульного кода (24, 16), полученного из кода (60, 52), порождаемого многочленом q(z) = х + х + х + 1, показали, что H,óñòðoéñòâå правильно корректируются все модульные ошибки.

Формула изобретений

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

-yMx ошибок модульными кодами, содержащее генератор синдрома, информационный вход которого является информа ционным входом устройства, буферный рагистр, вход обнуления которого объединен с входами обнуления генератора синдрома и первого триггера и первым входом первого элемента ИЛИ и является входом начальной установки устройства, второй элемент ИЛИ, первый и второи элементы И, выход первого элемента ИЛИ соединен с входом обнуления счетчика импулвсов, выходы которого подключены к входам дешифратора, выход которого подключен к второму входу первого элемента ИЛИ и счетному входу первого триггера, счетные входы счетчика импульсов, буферного регистра и генератора синдрома объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности в работе, в устройство введены с первого по r-й сумматоры по модулю два (r - количество проверочных разрядов входного кода), с первого по п-й мультиплексоры .(n — общее количество разрядов входного кода), блок контроля, второй триггер, переключатель и ключевой элемент, информационный вход которого является тактовым входом устройства, выход первого триггера подключен к первым входам элементов И и управляющему входу переключателя, первый информационный вход которого подключен к информационному входу устройства, выход переключателя соединен с информационным входом буферного регистра, выходы с (и — r + 1)-го по (и — 1)-й разрядов которого подключены к первым входам соответственно с первого по {r-1)-й сумматоров йЬ модулю два, выход n-ro разряда буферного регистра соединен с первым входом r-го сумматора по модулю два и вторым информационным входом переключателя, с первого по r-й-: выходы генератора синдрома подключе« ны к вторым входам соответствующих сумматоров по модулю два, выходы первого — (n — r)-го разрядов буферного регистра и выходы первого — r-го сумматоров по модулю два соединены с

i-ro по (1п + i - -1Imod n)-й инфор- мационными входами i-ro мультиплек сора (i = 1, и), адресные входы всех мультиплексоров соответственно объединены и подключены к выходам счетчика импульсов, выходы в первого по и-й мультиплексоров подключены к со-

1596465

)Р ответствующим Bходам блока контроля и являются информационными выходами устройства, выход блока контроля подключен к второму входу первого эле5 мента И, выход которого соединен с первым входом второго элемента ИЛИ и является контрольным выходом устройства, второй вход второго элемента И подключен к выходу дешифратора, выход о второго элемента И соединен со счетным входом второго триггера, вход обнуления которого подключен к входу начальной установки устройства, выход второго триггера соединен с вторым входом второго элемента ИЛИ, выход которого подключен к управляющему входу ключевого элемента и является выходом готовности устройства, выход ключевого элемента соединен с тактовым входом счетчика импульсов и (п + 1)-м входом блока контроля.

1596465 с

Фаг4

О П-П1 П2."fabri)L-Я Я .П.Я:" ni: Я,Я :с- с:.

-Л:Е:-Л:2С- лС:: С- C- - х:-х асс- :: 1:х":)сс-х::

Di:-iCIL-O Л) Д2";.(лЧ, Р("::.Я i . л ) (.-Я Щ

ГЗ Е С: . и . Я Л Л ю

nial Д д Л Л

-ХЛ -Х:: .3СХ Х

"— ш х хоос- хе:: сх-хххх-хх„ —; — -у и и «3 с П

4Ьа8

Составитель О. Ревинский

Редактор Н. Горват Техред М.Ходанич . Корректор Н. Ревская

Заказ 2917 Тираж 663: Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101