Запоминающее устройство с коррекцией ошибок Советский патент 1986 года по МПК G11C29/00 

1

ts

20

25

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

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

На фиг.1 изображена структурная схема запоминающего устройства с кор- JQ рек1щей ошибок; на фиг.2 - структурная схема блока кодирования и декодирования; на фиг.З - структурная схема блока анализа синдрома и блока преобразования синдрома; на фиг.А - структурная схема дешифратора.

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

Блок 2 кодирования и декодирования (фиг.2) содержит сумматоры 19-28 по модулю два, умножитель 29 (на два), умножитель 30 (на три), сумматоры 31 и 32, элементы И 33-38, сумматоры 39-44 по модулю два, элементы. И 45-56. На фиг.2 обозначены также вход Чтение 57 и вход Запись 58.

Блок 8 (фиг.З) содержит блоки 59-61 элементов И с первого по тре- jj тий, блок 62 элементов ИЛИ, элемен- 50 ты ИЛИ 63-65 с первого по третий, первый 66 и второй 67 элементы НЕ. Блок 9 (фиг.З) содержит дешифраторы 68-70 и преобразователи 71-73 кодов. Дешифратор 13 (фиг.4) содержит 55 блок 74 дешифрации и элементы И 75-85.

В устройстве используется обобщенный код Хемминга (КХ). Каждый символгде дво бло раз па вол одн q-и соо . обо вхо ное раз

раз

(СЛО цы раз ход

30

35

40

45

(на сто

воз в к

ряд бив так сло 4-и для

вол щие вым пре

соо пер инф ла

кон

ts

20

,

JQ

2561002

вол кода может принимать q значений, где q 2 (и 1,2,3...). Входное двоичное слово, поступающее на вход 3 блока 2, разбивается на группы по и разрядов, U-разрядная двоичная группа рассматривается как один q-й символ. Таким образом двоичному слову однозначно ставится в соответствие q-ичное слово, которое кодируется в соответствии с порождающей матрицей . обобщенного КХ. Если при записи на вход ЗУ поступает двоичное L-разряд- ное слово, то оно разбиением наU- разрядные группы преобразуется в К

разрядное (К ) q-ичное ( )

(СЛОВО. Размерность проверочной матрицы Н кода определяется следующим образом. Количество строк матрицы находят из неравенства

(я

к , 2.

q - 1

- m

(находят минимальное т), количество столбцов матрицы равно К+Ш.

Столбцами матрицы Н являются все возможные наборы длины, содержаш;ие 1 в качестве первой ненулевой компоненты.

Пусть на вход ЗУ поступают 16-разрядные двоичные числа, а слова разбиваются на группы по 2 разряда и таким образом 16-разрядное двоичное слово преобразуется в 8-разрядное 4-ичное слово. Проверочная матрица 11 для такого случая имеет вид

110О О 011

111О 1

О о

1 1

2 3

1 1 О О О 1

11 О О

23

1 1 1 1 О 1

Если в качестве проверочных символов выбрать символы, соответствующие столбцам с единственным ненулевым элементом, то матрицу Н можно преобразовать к виду

2345

и, и, и, и и

00

1 1

2 3

7 8

и, и

1 ь ь

1 1

00011 12301

9 10 11

т -а t 1 1 11 00

О 1 о о о 1

jj

соответствукицему разделимому коду: первые 8 символов слова (U1-U8) - информационные, три последних символа (К1-КЗ) - контрольные .

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

.3

K1 U4+U5+U6+U7+U8

K2 U1+U2+U3+U7+U8

K3 UH-2-U2+3-U3+U4+2 U5+3 U6+U8

. (U1+U4+U8)+2-(U2+U5)+3 (U3+U6).

Значение K1 формируется на сумматорах 19 (младший разряд) и 20 (старший разряд), значение К2 - на сумматорах 21 и 22 соответственно, КЗ - на сумматорах 31 и 32. При записи информации значение входа 57 равно нулю, а значение входа 58 равно единит це. На вход блока 1 поступают информационные разряды слова с выходов 4.1.1-4.8.2 блока 2, а также контрольные разряды (выходы элементов и 46, 48; 50, 52; 54, 56).

При чтении (К+т)-разрядное q-ичное слово или U(К+т)-разрядное двоичное слово поступает в блок 2, где вычисляется т-разрядный q-ичный синдром, поступающий с выхода 7 в блоки 8 и 9.

Двоичное значение синдрома формируется на выходах сумматоров 39-44, где к сумме соответствующих информационных разрядов прибавляются значения контрольных разрядов. Прохождение со держимого контрольных разрядов на сумматоры 39-44 осуществляется через элементы И 33-38 под действием управляющего сигнала Чтение (выход 57).

Блок 8 анализирует разряды синд- рома и определяет величину ошибки, которая представляет собой значение первого ненулевого символа синдрома, т.е. блок 8 пропускает на выход 10 первый (при рассмотрении синдрома слева направо) ненулевой символ синдрома .

Блок 9 осуществляет деление синдрома на его первый ненулевой символ (на величину ошибки) в соответствии с таблицей деления. Деление символа синдрома на величину ошибки реализует преобразователь, вьшолненный, например, в виде ПЗУ.

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

,

S

О-5

20 350 455055

30

1004

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

Величина ошибки с выхода 10 блока 8 поступает в блок 11. Коррекция считанной информации производится в блоке 5 сумматоров, исправлению под- , вергается разряд, определенный в дешифраторе 13, к содержимому которого прибавляется величина ошибки.

Если синдром считанного слова от- личен от нуля, а на всех выхо дах дешифратора 13 имеют место нулевые Iсигналы (т.е. вычисленный локатор 1не совпадает ни с одним столбцом матрицы Н), то на выходе 18 элемента ИЛИ 16 индицируется сигнал Ошибка.

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

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

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

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

56100ft

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

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

20 входы которых являются входами, блока.

У

Фа2.2

Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции. Цель изобретения - повышение надежности. Устройство содержит блок памяти блок кодирования и декодирования, блок сумматоров, блоки анализа и преобразования синдрома, блок элементов И, дешифратор, элементы ИЛИ-НЕ, И и ИЛИ. В устройстве используется обобщенный код Хэмминга. Входное двоичное слово, поступающее на вход блока кодирования, разбивается на группы по U разрядов, каждая иэ которых рассматривается как один символ. Блок анализа синдрома определяет величину ошибки (первый ненулевой символ синдрома). Блок преобразования синдрома осуществляет деление синдрома на величину ошибки. С помощью блоков сумматоров, элементов И и дешифратора осуществляется исправление однобитовых ошибок, а также пакетных (и-разрядньгх) ошибок в двоичном слове. Возможно также обнаружение двукратных пакетов ошибок. Сигнал об этом формируется на входе элемента И. 2 з.п. ф-лы, 4 ил. i (Л ГчЭ СП О)

Редактор А.Сабо

Фиг

Составитель Б.Рудаков Техред А. Кравчук

Заказ 4830/52 Тираж 543Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул. Проектная, 4

Корректор Л.Пилипенко