Устройство декодирования для коррекции модулей ошибок Советский патент 1992 года по МПК G11C29/00 

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

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

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

Наиболее близким по технической сложности и схемному решению к предлагаемому является устройство декодирования для коррекции модулей ошибок, содержащее блок вычисления синдрома, первый блок вычисления частных синдромов, первый блок сравнения, первый блок элементов И, блок сумматоров по модулю два, выходы которых являются информационными выходами устройства входы блока вычисления синдрома являются информационными входами устройства и соединены с входами первой группы блока сумматоров по модулю два, выходы первой группы блока вычисления синдрома соединены соответственно с входами первого блока вычисления частных синдромов и с входами первой группы первого блока элементов И, выходы второй группы блока вычисления синдрома соедиXI

СО XI

сл сл

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

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

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

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

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

элемента И является входом задания режима устройства.

В устройстве, использующем модульные коды, возможна наряду с коррекцией модуля ошибок длины Ь, также и коррекция

0 пакета ошибок длины р b -1, что расширяет область применения устройства по коррекции модулей ошибок.

На фиг. 1 представлена блок схема устройства; на фиг. 2 и 3 - конкретная реализа5 ция части блоков элементов И и элементов ИЛИ; на фиг. 4 и 5 - проверочные матрицы Hi и На кодов, используемых для реализации устройства для коррекции модуля ошибок длины Ь 4 и пакета ошибок длины

0 р 3.

Реализация блока вычисления синдрома, блоков вычисления частных синдромов, блоков сравнения хорошо известна, они состоят из сумматоров по модулю два, элемен5 товИ ИЛИ, НЕ.

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

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

5 вычисления частных синдромов, выходы 18 и 19 первого и второго блоков сравнения соединены соответственно с входами второй группы первого блока элементов И, входами элемента ИЛИ-НЕ 20 и с входами

0 второй группы второго блока элементов И, выход 21 элемента ИЛИ-НЕ соединен с вторым входом элемента ИЛИ 22, первым входом 23 соединенного с выходом элемента И и инверсными входами третьей группы

5 первого блока элементов И, выход 24 элемента ИЛИ соединен с входами третьей группы второго блока элемента И, выходы 25 и 26 первого и второго блоков элементов И соединены соответственно с входами первой и второй групп блока элементов ИЛИ 27,

выходы 28 которого соединены с входами второй группы блока сумматоров по модулю два, выходы 29 блока сумматоров по модулю два являются информационными выходами устройства.

В изобретении используется проверочная матрица модульного кода; в качестве конкретного выполнения на фиг. 4 представлена матрица кода (24; 16), позволяющего корректировать модули ошибок длины b 4. Возможности этого кода по коррекции модулей ошибок известны, поэтому доказательства коррекции любых одиночных ошибок или модулей ошибок длины b 4 в обрабатываемых кодовых словах можно не приводить. Также нет необходимости доказывать, что данный модульный код корректирует пакет ошибок длины р 3.

Известно также, что синдромы пакета ошибок отличаются друг от друга при длине пакета р 3. В примерах конкретного исполнения на фиг. 2 и 3 рассматривается реализация части блоков элементов И и ИЛИ для матрицы Hi (фиг. 4) и матрицы Н2 (фиг. 5), полученной из матрицы Hi путем исключения двух крайних столбцов справа и слева.

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

Возможны два режима работы: коррекции модуля ошибок длины b 4 и пакета ошибок длины р информационных разрядах.

При считывании сигналы с информационных разрядов с блока памяти (не показан) поступают на входы 2 блока вычисления синдрома 1. На выходах 4 и 13 блока 1 формируются известным образом разряды синдрома S (Si, 82).

Например, для применяемого кода (фиг. 4) эти разряды вычисляются следующим образом

Ci ai -- as + ад + aia + ai C2 32 + 36 + аю + 314 + ais

Si Сз аз + 37 + an--ais T 319

, CA 34 + 38 + 312 + 318 + 320

Cs at + ai2 f ais + 318 + 821 82) Ce 32 + as + aie + ai9 + 322

С аз + ас + eg + 320 т а23 , Се 34 + а + аю + ai3 + 324 где а (0, 1) - разряды слова, поступающие на входы 2 блока 1, из них as. an, 314, ai. 321-24 - являются контрольными, остэльные информэционными.

В режиме коррекции модуля ошибок длины b 4 на вход 12 зэдания режима подается сигнал лог. О. При этом первый блок элементов И открыт, а второй блок элементов И 8 закрыт (на выходах 26 нулевые сигналы) нулевым сигналом с выхода 24 элемента ИЛИ 22, на выходах 21 и 23 которого также нулевые сигналы. Причем сигнал на выходе 21 нулевой, поскольку при ошибках в первых пяти модулях (разрядах ai - 320) на одном из выходов 18 блока сравнения 14 присутствует единичный сигнал, который указывает какой из пяти модулей является ошибочным. Местоположение ошибочного

0 модуля определяется известным образом путем вычисления по синдрому Si, присутствующем на выходах 4 блока 1, частных синдромов Sr Si AJT в блоке 5 и сравнении в блоке 14 Si (сигналов на выходах 16) с

5 синдромом $2 (сигналов на выходах 13 блока 1). Вектор ошибки ошибочного модуля Ei Si, который выделяется на одних из выходов 25 блока 7 и далее без применения поступает на выходы 28 блока 27. В резуль0 тате в блоке сумматоров 3 происходит исп- рэвление информации в ошибочном модуле и выдэча прэвильной информации на выход 29 устройства.

В режиме коррекции пакета ошибок

5 длины р Ь-1 3 на вход 12 задания режима работы подается сигнал лог. 1. При этом, если на крайних выводах 4 присутствуют сигналы лог. 1, поступающие на входы 9 и 10 элемента И 11, то на выходе 23 п рисутст0 вует единичный сигнэл. Этот сигнэл зэкры- вэет первый блок элементов И 7 (на выходэх 25 нулевые сигнэлы) и открывэет через элемент ИЛИ 22 второй блок элементов И 8. Это указывает на то. что пакет ошибок попал

5 на стыки модулей кода, задаваемых матрицей Hi (фиг. 4) или в модули кода, задзвае- мого матрицей Н2 (фиг. 5), т. е, пакет ошибок длины три поразил разряды модулей (аз, 34,

35, Эб), (37. 38. 39, аю), (an, 312, 313, 314) .... (319,

0 320. 321, 322). Вектор ошибок этого пакета Ei Si, а местоположение пакета определяется с помощью блоков 6 и 15, причем блок вычисления настных синдромов реализует вычисление Si Si Bj1, исходя из матрицы Н2

5 (фиг. 5). Нз одном из выходов 19 появляется единичный сигнзл, который указывэет какой модуль искажен у кода, задаваемого матрицей Н2. Тогдэ на выходы 28 блока 8 выделяется вектор ошибок пакета Ej Si,

0 который выделяется на выходах 28 блока 27 с учетом сдвига начэла отсчетов модулей кода, зэдзвземого мэтрицей Н2 (фиг. 3). В результате в блоке 3 происходит коррекция пакете ошибок, лежащего нэ стыке модулей

5 кодэ, зэдэваемого матрицей Hi.

Если же синдром 51 1010или51 0101 (например, искажены разряды аз, as или 34, ае), то произошло искажение разрядов на стыке модулей кода, задаваемого матрицей Hi. В этом случае, поскольку эти синдромы

ошибок аналогичны Si, но произошедшим внутри модулей кода, задаваемого матрицей Hi (например, искажены разряды at аз или 32 34) и отличэются в $2, т. е. синдромы S (Si, 82) различны, то на выходах 18 блока 14 будут присутствовать нулевые сигналы закрывающие блок 7, а на выходе 21 элемента ИЛИ-НЕ 20 - единичный сигнал. Данный сигнал, проходя через элемент ИЛИ 22 на выход 24, откроет блок элементов И 8. В результате, как и в предыдущем случае, исправление пакета ошибок, будет осуществляться через блоки 6, 15, 8, реализующие матрицу Н2.

Во всех остальных случаях, когда пакет ошибок длины три лежит в модулях кода, задаваемого матрицей Hi, на одном из выходов 18 блока 14 присутствует единичный сигнал, который, проходя через элементы 20, 22, держит закрытым блок элементов И 8 и открытым один из элементов И блока 7 В результате, как и в первом режиме при коррекции модуля ошибок, происходит исправление пакета ошибок через блоки 5 14 7, реализующие матрицу Hi.

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

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

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

Ш ZJ

Шиг,1

26

Изобретение относится к области вычислительной техники, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения надежности запоминающих устройств. Целью изобретения является расширение области применения устройства декодирования модулей ошибок за счет возможности наряду с коррекцией модулей ошибок производить и коррекцию пакета ошибок. Это достигается применением специальных матриц кодирования, введением дополнительных блоков, элементов и связей. Устройство содержит блок 1 вычисления синдрома, блок 3 сумматоров по модулю два, первый 5 и второй 6 блоки вычисления частных синдромов, элемент И 11, первый 14 и второй 15 блоки сравнения, элемент ИЛИ-НЕ 20, элемент ИЛИ 22 и блок элементов ИЛИ 27. Введение дополнительных блоков, элементов и связей позволяет соответствующим образом использовать верхние разряды синдрома модульного кода для определения местоположения пакета ошибок. Это дает возможность корректировать как модуль так и пакет ошибок. 5 ил со с

15

25

Фиа2

Зв

28

25

28

ФыгЗ

1 1 1 1 1

1 у 11 1 1 1 1 1 I I 1

L. У|

114Г лГ.. К -

1У

1 I/ У 7 У I/ 1 I M I У У У

I « I

МП /I / / 1

л /i п ; Л 1

Н 7 | у у j j

П Ц У У У |У |У У У

J |LJ.LJLJU

7/ 17 7

У У |У |У

i М/ i |

i i

I

I

,|/,|J, О -Ч-1-4-4-+ -

I .

1 I

i i

ШгЧ

I

| in

I /

i

ft i з i &, i 55

fl)t/2,5