Запоминающее устройство с коррекцией ошибок
Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции. Цель изобретения - повышение надежности. Устройство содержит блок памяти блок кодирования и декодирования, блок сумматоров, блоки анализа и преобразования синдрома, блок элементов И, дешифратор, элементы ИЛИ-НЕ, И и ИЛИ. В устройстве используется обобщенный код Хэмминга. Входное двоичное слово, поступающее на вход блока кодирования, разбивается на группы по U разрядов, каждая иэ которых рассматривается как один символ . Блок анализа синдрома определяет величину ошибки (первый ненулевой символ синдрома). Блок преобразования синдрома осуществляет деление синдрома на величину ошибки. С помощью блоков сумматоров, элементов И и дешифратора осуществляется исправление однобитовых ошибок, а также пакетных (и-разрядньгх) ошибок в двоичном слове. Возможно также обнаружение двукратных пакетов ошибок. Сигнал об этом формируется на входе элемента И. 2 з.п. ф-лы, 4 ил. i (Л ГчЭ СП О)
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51) 4 G 11 С 29/00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1;
H А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3870350/24-24 (22) 16.01.85 (46) 07.09.86. Бюл. № 33 (71) Киевский ордена Ленина политех нический институт им. 50-летия Великой Октябрьской социалистической революции (72) А.К.Антонюженко, Н,И.Величко, И.А.Дичка и В,И.Корнейчук (53) 681.327 (088.8) (56) Авторское свидетельство СССР № 470866, кл. G 11 С 29/00, 1968.
Electronic engineerinp. V. 51, ¹ 617, 1979, р.р. 49, 52, 53. (54) ЗАПОИИНАЮЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ОШИБОК (57) Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции. Цель изобретения — повышение надежности.
„„SU„„1256100 A 1 Устройство содержит блок памяти, блок кодирования .и декодирования, блок сумматоров, блоки анализа и преобразования синдрома, блок элементов И, дешифратор, элементы ИЛИ-НЕ, И и ИЛИ. В устройстве используется обобщенный код Хэмминга. Входное двоичное слово, поступающее на вход блока кодирования, разбивается на группы no u разрядов, каждая из которых рассматривается как один символ. Блок анализа синдрома определяет величину ошибки (первый ненулевой символ синдрома) . Блок преобразования синдрома осуществляет деление синдрома на величину ошибки. С помоФ щью блоков сумматоров, элементов И и дешифратора осуществляется исправление однобитовых ошибок, а также С:: пакетных (u-разрядных) ошибок в двоичном слове. Возможно также обнару- ф жение двукратных пакетов ошибок. Сигнал об этом формируется на входе элемента И. 2 з.п. ф-лы, 4 ил.
1 1
Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повы- . шенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции, Цель изобретения — повышение надежности устройства.
На фиг.1 изображена структурная схема запоминающего устройства с кор. рекцией ошибок; на фиг.2 — структурная схема блока кодирования и декодирования; на фиг.3 — структурная ,схема блока анализа синдрома и блока преобразования синдрома; на фиг.4 структурная схема дешифратора.
Запоминающее устройство содержит (фиг. 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 (фиг.3) содержит блоки
59-6 1 элементов И с первого по третий, блок 62 элементов ИЛИ, элементы ИЛИ 63-65 с первого по третий, первый 66 и второй 67 элементы НЕ.
Блок 9 (фиг.3) содержит дешифраторы
68-70 и преобразователи 71-73 кодов.
Дешифратор 13 (фиг.4) содержит блок 74 дешифрации и элементы И 75-85.
В устройстве используется обобщенный код Хемминга (КХ). Каждый симМ
Кс — — --m
1 д (находят минимальное m), количество столбцов матрицы равно K+m.
Столбцами матрицы Н являются все возможные наборы длины, содержащие 1 в качестве первой ненулевой компойенты.
Пусть на вход ЗУ поступают 16-разрядные двоичные числа, а слова разбиваются на группы по 2 разряда и таким образом 16-разрядное двоичное слово преобразуется в 8-разрядное
4-ичное слово. Проверочная матрица 11 для такого случая имеет вид
0 0 О О О 1 1 1 1 1 1
H = 0 1 1 1 1 0 0 0 0 1 1
10123012301
Если в качестве проверочных символов выбрать символы, соответствующие столбцам с единственным ненуле43 вым элементом, то матрицу Н можно преобразовать к виду
9 10 11
К К
1 О О
0 1 0
О 0 1
5 6 7 8
6 8
1 1 1 1
О 0 1 1
2 3 О 1
2 3 4 и ь
О J 1
1 1 О
2 3 1
U„,Н= 0
50 1
1 соответствующему разделимому коду: первые 8 символов слова (Ui-U8)
Ы информационные, три последних символа (К1 — КЗ) — контрольные
При записи формируются значения контрольных разрядов
256100 2 вол кода может принимать q значений, О где q = 2 (u = 1,2,3...) . Входное двоичное слово, поступающее на вход 3 блока 2, разбивается на группы по U разрядов, и -раз рядная двоичная группа рассматривается как один q-й символ, Таким образом двоичному слову однозначно ставится в соответствие
q-ичное слово, которое кодируется в соответствии с порождающей матрицей обобщенного КХ. Если при записи на вход ЗУ поступает двоичное L-разрядное слово, то оно разбиением íà u— разрядные группы преобразуется в
L н разрядное (K = — -) q-ичное (q=2 ) и слово, Размерность проверочной матрицы Н кода определяется следующим образом. Количество строк матрицы находят из неравенства
1 256100
-К1=Ц4+П5+Пб+И7+Б8
K2=U1+U2+U3+U7+U8
K3=U1+2 U2+3 U3+U4+2 05+3 Цб+П8
= (U1+U4+U8) +2 (U2+U5) +3 (ПЗ+Пб) . 5
Значение К1 формируется на сумматорах 19 (младший разряд) и 20 (старший разряд), значение К2 — на сумматорах 21 и 22 соответственно, КЗ на сумматорах 31 и 32. При записи информации значение входа 57 равно нулю, а значение входа 58 равно едини-.,це. На вход блока 1 поступают информационные разряды слова с выходов 15
4.1.1-4.8.2 блока 2, а также контрольные разряды (выходы элементов
U 46, 48; 50, 52; 54, 56).
При чтении (K+m) -разрядное q-ичное слово или U(K+m)-разрядное двоичное слово поступает в блок 2, где вычисляется m-разрядный q-ичный синдром, поступающий с выхода 7 в бло ки 8и 9.
Двоичное значение синдрома формируется на выходах сумматоров 39-44, где к сумме соответствующих информационных разрядов прибавляются значения контрольных разрядов. Прохождение содержимого контрольных разрядов на сумматоры 39-44 осуществляется через элементы И 33-38 под действием управляющего сигнала "Чтение" (выход 57).
Блок 8 анализирует разряды синд- 35 рома и определяет величину ошибки, которая представляет собой значение первого ненулевого символа синдрома, т.е, блок 8 пропускает на выход 10 первый (при рассмотрении синдрома 40 слева направо) ненулевой символ синдрома.
Блок 9 осуществляет деление синдрома на его первый ненулевой символ (на величину ошибки) в соответствии 4> с таблицей деления. Деление символа синдрома на величину ошибки реализует преобразователь, выполненный, например, в виде ПЗУ.
Разделенный на величину ошибки 50 синдром представляет собой локатор ошибки, т.е. один из столбцов матрицы Н. Для определения позиции искаженного разряда в принятом q-ичном слове необходимо сравнить вычисленный 55 локатор с каждым из столбцов матрицы Н. Столбец, равный локатору, указывает местоположение ошибки.
Разделенный на величину ошибки синдром представляет собой локатор ошибки, т.е. один из столбцов матрицы Н. Для определения позиции искаженного разряда в принятом q-ичном слове необходимо сравнить вычисленный локатор с каждым из столбцов матрицы Н. Столбец, равный локатору, указывает местоположение ошибки, Операцию сравнения локатора со столбцами матрицы Н выполняет дешифратор 13, На вход дешифратора 13 поступает
m-разрядный q-ичный локатор. При наличии ошибки в одном из символов ичного считанного слова на соответствующем выходе дешифратора 13 появляется сигнал, номер этого выхода равен номеру ошибочного разряда слова.
Величина ошибки с выхода 10 блока 8 поступает в блок 11. Коррекция считанной информации производится в блоке 5 сумматоров, исправлению под, вергается разряд, определенный в дешифраторе 13, к содержимому которого прибавляется величина ошибки.
Если синдром считанного слова от личен от нуля, а на всех выходах дешифратора 13 имеют место нулевые
;сигналы (т.е. вычисленный локатор не совпадает ни с одним столбцом матрицы Н), то на выходе 18 элемента ИЛИ 16 индицируется сигнал "Ошибка".
Формула изобретения
1. Запоминающее устройство с коррекцией ошибок, содержащее блок памяти, блок сумматоров, дешифратор, элемент И, элемент ИЛИ и блок кодирования и декодирования, вход которого соединен с выходом блока памяти, а первый выход подключен к первому входу блока сумматоров и вход; блока памяти, выход элемента ИЛИ соединен с первым входом элемента И, выход которого является управляющим выходом устройства, информационным выходом которого является выход блока сумматоров, о т л и ч а ю щ е е с я тем, что, с целью повьппения надежности устройства, в него введены блок анализа синдрома, блок преобразования синдрома, блок элементов И и элемент ИЛИ-НЕ, причем второй выход блока кодирования и декодирования подключен к входу блока анализа син-. дрома и первому входу блока преобра12 зования синдрома, второй вход которого соединен с выходом блока анализа синдрома и первым входом блока элементов И, а выход подключен к входам элемента ИЛИ и дешифратора, выход которого соединен с вторым входом блока элементов И, выход которого соединен с вторым входом блока сумматоров, выход дешифратора подключен через элемент ИЛИ-НЕ к второму входу элемента И.
2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок анализа синдрома содержит блоки элементов И, элементы ИЛИ, элементы НЕ и блок элементов ИЛИ, выходы которого являются выходами блока анализа сии\ дрома, а входы подключены к выходам блоков элементов И, выход первого элемента ИЛИ подключен к одному из
56100 б входов первого бл .- а элементов И и входу первого элемента НЕ, одни из входов второго блока элементов И соедйнены соответственно с выходом второго элемента ИЛИ, входом второго элемента НЕ и выходом первого элемента НЕ, одни нз входов третьего блока элементов И подключены соответственно к выходам третьего элемента ИЛИ и элементов НЕ, причем входы элементов ИЛИ и другие входы блоков элементов И являются входами блока анализа синдрома.
3. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок преобразования синдрома содержит дешифраторы и преобразователи кодов, выходы которых являются выходами блока, а входы подключены к выходам дешифраторов, входы которых являются входами блока.
125б100
125б100
Составитель В. Рудаков
Техред А. Кравчук
Корректор Л.Пилипенко
Редактор А.Сабо
Заказ 4830/52 Тираж 543 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д, 4/5
Производственно-полиграфическое предприятие, r.ужгород, ул, Проектная, 4
