Устройство для контроля цифровых данных Советский патент 1988 года по МПК H03M13/19 

00

00

оо

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

Цель изобретения - повьппение надежности и достоверности работы устройства.

На фиг. 1 изображена блок-схема устройства для контроля цифррвых данных; на фиг. 2 - таблица модифицированного кода Хэмминга, на основе которого построено предлагаемое устройство; на фиг. 3-8 даны функциональные схемы соответственно блока управления , блока мультиплексирования, вычислителя контрольных разрядов, вычислителя синдрома, блока элементов И и блока обнаружения ошибок; на фиг. 9 показано соединение четырех устройств для контроля данных для наращивания разрядности входного кода у на фиг. 10 представлена таблица расшифровки синдрома ошибки.

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

В устройстве для, контроля цифровых данных используются новая модификация кода Хэмминга, которая представлена таблицей кодирования для информационных слов разрядностью 16, 32 и 64 бит соответственно (фиг. 2). Новая модифшсация крда Хэмминга основана на теории линейных кодов с неравной защитой различных разрядов информационного слова и предназначена обеспечить защиту от двойных ошибок двух старших разрядов информационного слова. Для этого предлагаемое устройство формирует К контрольных разрядов (фиг. 2), число которых определяется по формуле

К 2 + log,j(m+1) ,

где m - разрядность информационного слова.

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

0 дов кодового слова.

Блок 4 управления выполнен (фиг.З) на триггере 18, дешифраторе 19, элементах И 20, элементах ИЛИ 21.

Выполнение блоков 2, 3, 6 и 5 для

5 модифицированного кода Хэмминга приведено на фиг. 4-7.

Блок 7 обнаружения ошибок выполнен (фиг. В) на Дешифраторах 22, элементе 23 равнозначности, элементах

0 ИЛИ 24, элементах И-НЕ 25, элементах И 26 и элементе ИЛИ-НЕ 27.

Для обеспечения работы с кодами большей разрядности (32 и 64) можно включить совместно (фиг. 9) несколь5 ко рассматриваемых устройств 28. При этом их в;-:од1 1 8 образуют информационную шину 29. Входы 9.1 первого из устройств 28 являются входами 30, входы 10 образуют адресную шину 31,

0 а управляющие входы 11-1 3 всех устройств 28 объединяются во входы 32-34. Выходы 14.4-17.4 последнего устройства 28 (для 32-разрядного кода - выходы 14.2-17.2) являются выходами 35-38

5 выборки.

Устройство для контроля цифровых данных работает следующим образом.

Сначала рассмотрим работу устрой- ства при разрядности m 16 бит, а

0 затем при наращивании разрядности (на примере m 16 бит).

Возможны два режима работы устройства:

5 режим кодирования, который задается логическим нулем на входе 13 (режим работы);

- режим декодирования, который задается логической единицей на вхо- де 13 (режим работы).

Б начальный момент времени с информационных входов 8 устройства поступает 16-разрядное слово на регистр 1 данных. С входов 10 (номер БИС) устройства на входы дешифратора 19 блока 4 поступает двухразрядная кодовая комбинация, значения которой приведены в таблице.

Поскольку работу устройства рас- сматриваем сначала при разрядности m 16 бит, то на входы 10 устройства поступает кодовая комбинация 00. На входы 9 (контрольные разряды/синдром) в режиме кодирования на вычис лИтель 6 синдромов поступают логические нули, а в режиме декодирования - контрольные разряды, считанные из памяти вместе с информационными разрядами.

Устройство для контроля запускается в работу импульсным сигналом, приходящим по входу 11 (сигнал начала операции) и поступающим на первый управляющий (синхронизирующий) вход регистра 1 данных, записьшая в него 16-разрядное информационное слово, и на первый управляющий вход блока 4 управления, устанавливая в единичное состояние триггер 18 (фиг. 3). Информационные разряды с выхода регистра 1 данных поступают на вычислитель 3 контрольных разрядов и на бло 2 мультиплексирования, на управляющие входы которого поступают управляющие сигналы с блока Л управления. Блок 2 мультиплексирования посылает на вычислитель 3 те информационные разряды, которые участвуют в формировании контрольного слова или синдроме ошибки для m 16 бит (см. таблицу кодирования для m 16 бит на фиг. 2). В вычислителе 3 происходит формирование разрядных сумм по модулю два ( Rg) тех информационных разрядов, которые помечены знаком X в таблице кодирования на фиг. 2. Указанные разрядные суммы по модулю два (контрольные разряды) поступают

0

0 5

0

5

0

5

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

В режиме кодирования вычислитель 6 формирует семь контрольных разрядов С , - С, которые поступают на выходы 16 (контрольное слово/синдром ошибки) устройства. Формирование сигналов Ошибка, Одиночная ошибка , Многократная ошибка на выходах 17-15 запрещается в данном режиме подачей логического нуля на входе

13 (режим работы) устройства. I

В режиме декодирования вычислитель 6 формирует семь битов синдрома ошибки (S JJ - S,), которые поступают на выходы 14 устройства и на входы блока 7 обнаружен1{я ошибок. Блок 7 формирует по единичному значению сигнала на входе 13 устройства соответственно сигнал Ошибка О, нет ошибки 1 , есть ошибка,

ет на выход 17 (Ошибка) устройства, и сигналы Одиночная ошибка

. и Многократная ошибка 1 , да

О, нет

, , которые ПОСТ;пают соот- 1 да

ветственно на выход 15 (Одиночная ошибка) и выход 16 (Мн(5гократная ошибка) устройства.

После того, как сформированное контрольное слово или синдром ошибки вместе с сигналами ошибки считывается из устройства, нп вход 12 (сброс) приходит импульсный сиг Г(

г

который поступанал, который поступает на второй вход (сброса) регистра 1 данных и на R-вход триггера 18 в блоке 4 управления, устанавливая его в нулевое состояние, А блок 4 управления устанавливает в исходное состояние остальные блоки устройства.

Пример 1. Пусть для формирования контрольного слова в устрой- ство поступило 16-разрядное информационное слово (D - D,) вида 0000000100001000. Тогда на выходе вычислителя 6 будем иметь контрольное слово (GO - С) вида 0001010, которое поступает на входы 15 устройства.

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

а. Предположим,что возникла одиночная ошибка в третьем информационном разряде, т.е. информационное ело во имеет вид 0010000100001000. Тогда на выходе вычислителя 6 будем иметь синдром ошибки tSp- S) вида 1101000, который поступает на выходы 14 устройства и на блок 7 обнаружения ошибок. Тогда на выходе 17 блока 7 обнаружения ошибок будем иметь сигнал Ошибка, равный I, а на выходах 15 и 16 этого блока 7 будем иметь соответственно сигнал Одиночная ошибка, равный 1 .и сигнал Многократная ошибка , равный О.

б.Предположим, что возникла двойная ошибка в первом и третьем инфор- циопиых разрядах, т.е. информационное слово 1шеет вид 1010000100001000. Тогда на выходе вычислителя 6 будем иметь синдром ошибки (S -г S) вида 0011001. Аналогично пункту а на выходе 17 блока 7 обнаружения ошибок будем иметь сигнал Ошибка, равный а на выходах 15 и 16 будем иметь соответственно сигнал Одиночная ошибка, равный О, и сигнал Многократная ошибка, равный Г.

в.Предположим, что возникла трои ная ошибка в третьем, шестом и четырнадцатом информационных разрядах, т.е. информационное слово имеет вид 0010010100001100. Тогда на выходе вычислителя 6 будем иметь синдром (Sp - S,) вида 0011010. В дальнейшем устройство сработает аналогично пункту б. Для примеров 2а, 26, 2в

д

п

5

0 5

30

0

5

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

Теперь рассмотрим работу в режиме наращивания разрядности при m 64 бит, т.е. работу 41т-разрядного устройства для контроля (фиг. 9).

4т-разрядное устройство для контроля данных работает также в двух режимах:

-режим кодирования, который задается логическим нулем по входу 34 (режим раббты);

-режим декодирования, который задается логической единицей по входу 34.

Работа всех устройств 28 аналогична описанной работе устройства при m 16 бит за следующим исключением.

В начальный момент времени на входь 18 устройства 28 поступают со ответственно информационные слова U,-D, D,.-D,i; DJ.-V. ,,c входов 29. На входы 10 устройства 28 поступают соответственно двухразрядные кодовые комбинации 00, 01, 10 и 11, с входов 31 (номер БИС). Устройства 28 запускаются в работу импульсным сигналом, поступающим по входу 32.

1.В режиме кодирования по входам 30 на входы 9.1 устройства 28.1 поступают логические нули, а неполные контрольные разряды с выходов 16.1 устройства 28.1 поступают на входы

9.2устройства 28.2, где произойдет « их сложение по модулю два со сформированными неполными контрольными разрядами устройством 28.2, затем эта сумма по модулю два с выходов 14.2 устройства 28.2 поступает на входы

9.3устройства 28.3 и т.д. Полное контрольное слово будет сформировано в устройстве 28.4 и с выходов 14.4 оно поступает на выходы 35.

Формирование сигналов Ошибка, Одиночная ошибка и Многократная ошибка в данном режиме также запрещается ;

2.В режиме декодирования по входам 30 на входы 9.1 устройства 28.1 поступает контрольное слово, соответствующее полному информационному слову D., - D. Работа устройств 28 аналогична описанной работе по пункту 1, только с выходов 14.4 устрой- зтва 28.4 будет поступать полный син/

дром ошибки на выходы 35, а с выходов 17-15 устройства 28.4 будут поступать соответственно сигналы Ошибка, Одиночная ошибка и Многократная ошибка на выходы 38-36 соответственно. А после приема всей информации из устройств 28 на вход 33 поступает импульсный сигнал сброса, по которому происходит установка в ис- ходное состояние блоков устройст- ва 28.

Пример 3. Пусть для формирования контрольного слова на устройства 28 поступают соответственно ин- формационные разряды (D, - D) вида 0000000100001000, (Dn- D) вида 1000000010000000, (D,,- вида 0001000000010000, (D,- D) вида 0000100000000001. Тогда на выходе 14.1 устройства 28.1 получим неполное контрольное слово (С - С д) , вида 001010000, на выходах 14.2 устройства 28.2 - (С- - С.)

вида

100111000 на выходах 14.3 устройст- на 28.3 - (Со - Св)звида 000101000, а на выходе 14.4 устройства 28.4 получим полное контрольное- слово (GO - Cj) вида 111111000, которое поступает на выходы 35.

Пример 4. Пусть указанное в примере 3 информационное слово (D, - Dj и соответствующее ему полное контрольное слово (С - С) были считаны из ЗУ и поступи;;и для контроля на 4т-разрядное устройство для контроля данных.

а. Предположим, что произошла одиночная ошибка в первом информа- ционном разряде, т.е. (D , - D,) име- ет вид 10000000100001000, а (D,- D( остались без изменений. Тогда на выходах 14.1 устройства 28.1 получим неполный синдром (S - 5),вида 000010100, на выходах 14.2 устройст

ва 28.2 - (Sg - 85,) вида lOOOOOiqO

на выходах 14.3 устройства 28.3 - (Sfl вида 000010100, а на выходах 14.4 устройства 28.4 получим полный синдром ошибки (SP Sj) вида 1110001000, который указывает на данную одиночную ошибку (фиг. 10). На выходах 17, 15 и 16 устройства 28.4 получим соответственно сигналы Ошибка, равный 1, Одиночная ошибка, равный 1 и Многократная ошибка, равный О.

б. Предположим, что произошла двойная ошибка во втором и четвертом

0

5 Q

5

5

5

188

информационных разрядах, т.е. (О, - D,) имеет вид 0101000100001000, а (D D ) остались без изменения. Тогда на выходах 14.1 устройства 28.1 полуним неполный синдром (Sg - S) вида 111101100; на выходах 14.2 устройства 28.2 (S - S), вида 011111100, на выходах 14.3 устройства 28.3 (So - Sg) вида 111101100, на выходах 14.4 устройства 28.4 получим полный синдром ошибки (8д - Sg) вида 000111100, который указывает на данную двойную ошибку (фиг.10). На выходах 17, 15, 16 устройства 28.4 получим соответственно сигналы Ошибка, равный 1, Одиночная ошибка, равный О, Многократная ошибка, равный 1.

в. Предположим, что вовникла пятикратная ошибка в шестом, восьмом, двадцать пятом, сороковом и сорок восьмом информационных разрядах, т.е. информационное слово (D , - D, D

з °4« 1, имеет вид 000001000000010000, 1000000000000, 0001000100010001, 0001000000000001. Тогда на выходах 14.1 устройства 28.1 будем иметь неполный синдром (Sp - Sg), вида 101110000, на вьпсо- дах 14.2 устройства 28.2 получим тогда (Sj - Sg), вида 011110010, на выходах 14.3 устройства 28.3 получим тогда (So - Sj)} 111111010, а на выходах 14.4 устройства 28.4 получим полный синдром ошибки (Sр - S.) вида 000101010, который соответствует данной пятикратной ошибке (фиг. 10). На выходах 17, 15, 16 устройства 28.4 получим соответственно следующие сигналы: Ошибки, равный 1, Одиночная ошибка, равный О и Многократная ошибка, равный 1.

Таким образом, устройство для контроля цифровых данных позволяет повысить достоверность работы за счет обеспечения возможности исправления двойных ошибок любого типа, так как формирование синдрома двойной ошибки не зависит от типа двойной ошибки и исправление двойной ошибки в последующих устройствах происходит только по виду самого синдрома ошибки, в то время как в устройстве-прототипе одна из двух ошибок (постоянная) исправляется путем ее двойного иныер- тирования, затем формируется новый синдром ошибки, который указывает на оставшуюся одиночную ошибку, которая исправляется по виду синдрома ошибки. Кроме того, обеспечивается возможность простого обнаружения многократных ошибок любого типа, В случае возникновения многократной четной ошибки формируется такой синдром ошибки который имеет четный вес (кроме одиночнор ошибки в 1-м информационном разряде) , Для обнаружения многократной нечетной ошибки предлагаемое ycTpopicTBo анализирует два бита синдрома ошибки S,.S. Наличие такой ошибки определяется следующими значениями битов , 01,, - кроме одиночной ошибки в 1-м информационном или С контрольном разрядах 10 - кроме одиночной ошибки в 13 - 16, 32, 48 информационных и С контрольном разрядах, П ,2 - кроме одиноч- ной ошибки во 2-м информационном разряде (фиг, 10),

Кроме того, предлагаемое устройство позволяет повысить надежность и упростить устройство, особенно при наращивании разрядности до 64-х бит путем отказа от дополнительных логических вентилей. Это достигается за счет рационального формирования синдрома ошибки (или контрольных разрядов) с помощью двух вычислителей блока мультиплексирования блока элементов tt и блока управления, обеспечивающих коммутацию информационных разрядов в соответствии с тaбJп- цeй кодирования, использовать устройство для контроля данных для совместно работы с лробым типом памяти (ОЗУ, ПЗУ, ЗУПВ и т,п.) независимо от их организации, так как оно 1-1меет возможность с информационным словом разрядностью 16, 32 или 64 бит; увеличить быстродействие последующих устройств исправления двойных ошибок, так как обнаружен- ная двойная ошибка исправляется - сразу аппарятно по виду синдрома ошибки, который формирует предлагаемое устройство, в то время как в устройстве-прототипе при обнаружении двойной ошибки (при первом считывании информации из ЗУ) производится инвертирование считанной информации и ее запись в ЗУ, затем повторное считывание информации в инверсной форме, в результате чего постоянная ошибка исправляется, затем производится новое формирование синдрома ошибки, который указывает на оставшуюся оди

Q .5 20

8171810

ночную ошибку, вызванную случайным сбоем, В результате этого для исправления двойной ошибки устройством-прототипом необходимо выполнять двойной цикл записи/считывания информации в ЗУ,

Q 5 20

25 зо Q д

35

0

5

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

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

111

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

2. Устройство по п. 1, о т л и- чающееся тем, что блок обнаружения ошибок выполнен на первом - четвертом дешифраторах, первом - десятом элементах И-НЕ, первом - седьмом элементах И, первом и втором элементах ИЛИ, элементе ИЛИ-НЕ и элементе равнозначности, входы которого объединены с одноименными входами первого элемента ИЛИ и соответствующими, входами дешифраторов и яв- ляются информационными входами блока, выход первого разряда первого дешифратора подключен к первым входам первого элемента И и первого и третьего элементов И-НЕ, выход второ го разряда первого дешифратора подключен к первым входам третьего элемента И и четвертого - десятого элементов И-НЕ, выход третьего разряда первого дешифратора подключен к первым входам вторых элементов И и И-НЕ, выход нулевого разряда второго дешифратора соединен с вторыми входами третьего и четвертого элементов И-НЕ, выход третьего разряда второго дешифратора соединен с вторыми входами шестого и восьмого элементов И-НЕ, выход четвертьго разряда второго дешифратора соединен с вторыми входами девятого и десятого элементов И-НЕ, выходы пятого и шестого разрядов второго дешифратора соединены с вторыми входами соответственно пятого и первого элементов И-НЕ, выход седьмого разряда второго дешифратора соединен с вторыми входами второго и седьмого элементов И-НЕ, выход нулевого разряда третьего дешифратора подключен к третьим входам второго - шестого, девятого и десятого элементов И-НЕ, выход второго разряда третьего дешифратора подключен к третьим вхо- дам первого и седьмого элементов И- НЕ, выход третьего разряда третьего дешифратора подключен к третьему входу восьмого элемента И-НЕ, выход нулевого разряда четвертого дешифратора соединен с четвертыми входами первого - восьмого элементов И-НЕ, выходы первого и второго разрядов четвертого дешифратора соединены с четвертыми входами соответственно десятого и девятого элементов И-НЕ,

5

7

0

0

5

0

5

0

5

812

выходы второго и третьего элементов И-НЕ соединены с вторыми входами соответственно первого и второго элементов И, выход первого элемента И-НЕ подключен к третьему входу первого и первому входу четвертого элементов И, выходы четвертого - десятого элементов И-НЕ подключены соответственно к второму - восьмому входам третьего элемента И, выходы первого - третьего элементов И соединены с одноименными входами второго элемента ИЛИ и элемента ИЛИ-НЕ, выход элемента равнозначности соединен с вторым входом четвертого элемента И, выход которого подключен к четвертым входам второго элемента ИЛИ и элемента ИЛИ-НЕ, выходы которых соединены с первыми входами соответственно пятого и шестого элементов И, выход первого элемента ПТИ подключен к первому входу седьмого элемента И и вторым входам пятого и шестого элементов И, третьи входы которых и второй вход седьмого элемента И объединены и являются управлякхцим входом блока, выходы шестого, пятого и седьмого элементов И являются соответственно первым - третьим выходами блока.

3. Устройство по п. 1, о т л и- чающееся тем, что блок управления выполнен на триггере, элементах И, элементах ИШ1 и дешифраторе,первый и второй входы которого являются информационными входами блока, S- и R-входы триггера являются соответственно первым и вторым управляющими входами блока, выход триггера подключен к первым входам первого - четвертого элементов И, выходы дешифратора соединены с вторыми входами соответствующих элементов И, выход первого элемента И соединен с первыми входами первого и второго элементов ИЛИ, выход второго элемента И подключен к второму входу первого и первым входам третьего - пятого элементов ИЛИ, выход третьего элемента И соединен с третьим входом первого, вторым входом четвертого и первым входом шестого элементов ИЛИ, выход четвертого элемента И подключен к третьему входу третьего и вторым входам второго, пятого и шестого элементов ИЛИ, выходы первого и четвертого элементов И и первого - четвертого элементов ИЛИ явля13

ются соответствующими первыми иыхода- mi блока, выходы пятого и шестого

а-

138171814

элементов ИЧИ являются соответствую- П1ими вторыми выходами блока.

. Изобретение относится к вычислительной технике. Его использование в системах хранения, передачи и обработки цифровой информации позволяет повысить надежность и достоверность работы устройства, которое содержит регистр 1 данных, блок 2 мулъ- типлексирования, вычислитель 3 контрольных разрядов, блок 4 управления, вычислитель 6 синдрома и блок 7 обнаружения ошибок. Благодаря введению блока,5 элементов И, а также выполнению блоков 2-7 в соответствии с новым модифицированным кодом Хзмминга, устройство при более простом выполнении обеспечивает выдачу такого синдрома, который позволяет для 16-, 32- и 64-разрядного входного кода исправлять двойные ошибки любого типа и обнаруживать многократные ошибки. 2 з.п. ф-лы, 1-0 нл. 1 табл. (О (Л

Фиг 2

Продо/7жен е

в

fO

J4

X

37

X

3

XXX

4/

X

2

X

43

XXX

и

X

5

XX

46

X

X

8

X

50

X

X

5f

X

52

XXX

53

X

5

X

55

X

56

XX

5в

XX

59

X

X

ВО

XX

X

df

X

От 5лока1

Фиг.5

Нблокуб

Фиг.6

От 5лока 5 К блоку 7

Фиг.7

Фиг. 9

fpazJO