Запоминающее устройство с коррекцией ошибок

(9) 01) А 51) 4 С 11 ПИСАНИЕ ИЗОБРЕТЕН ИДЕТЕЛЬСТВ К АВТОРСКОМ итех- Велии 51,ОИИНАЮЩЕЕ УСТРОИСОШИБОКбретение относитейтехнике и можетно в запоминающих ВО С КО(54) 3 РЕКЦИЕ (57) И к вычисыть исистемах лительн пользов повышен а функ р едней зобрет степе СЬ ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский ордена Ленина понический институт им, 50-летиякой Октябрьской социалистическреволюции(56) Авторское свидетельство СФ 40866, кл. С 11 С 29/00, 19Е 1 есСгопс еп 1 пеегп. Ч.У 617, 1979, р.р. 49, 52, 53. ои надежности, выполненных циональных узлах с большой нью интеграции. Цель ния - повышение надежностиУстройство содержит блок памяти,блок кодирования и декодирования,блок сумматоров, блоки анализа ипреобразования синдрома, блок элементов И, дешифратор, элементы ИЛИИ и ИЛИ, В устройстве используетсяобобщенный код Хэмминга, Входноедвоичное слово, поступающее на входблока кодирования, разбивается нагруппы по ц разрядов, каждая из которых рассматривается как один символ. Блок анализа синдрома определяет величину ошибки (первый ненулевойсимвол синдрома), Блок преобразования синдрома осуществляет делениесиндрома на величину ошибки, С помощью блоков сумматоров, элементов Ии дешифратора осуществляется исправление однобитовых ошибок, а такжепакетных (и-разрядных) ошибок в двоичном слове, Возможно также обнаружение двукратных пакетов ошибок. Синал об этом формируется на входеэлемента И, 2 з.п. ф-лы, 4 ил.1 1Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повы- .шенной надежности, выполненных нафункциональных узлах с большой исредней степенью интеграции,Цель изобретения - повышение надежности устройства.На фиг,1 изображена структурнаясхема запоминающего устройства с коррекцией ошибок; на фиг,2 - структурная схема блока кодирования и декодирования; на фиг.З - структурная,схема блока анализа синдрома и блокапреобразования синдрома; на фиг.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 (фиг.З) содержит блоки59-6 1 элементов И с первого по третий, блок 62 элементов ИЛИ, элементы ИЛИ 63-65 с первого по третий,первый 66 и второй 67 элементы НЕ.Блок 9 (фиг.З) содержит дешифраторы68-70 и преобразователи 71-73 кодов.Дешифратор 13 (фиг.4) содержитблок 74 дешифрации и элементы И 75-85,В устройстве используется обобщенный код Хемминга (КХ), Каждый сим К с --- -ш1 д (находят минимальное ш), количествостолбцов матрицы равно К+ш.Столбцами матрицы Н являются всевозможные наборы длины, содержащие 1в качестве первой ненулевой компойенты,Пусть на вход ЗУ поступают 16-разрядные двоичные числа, а слова разбиваются на группы по 2 разряда итаким образом 16-разрядное двоичноеслово преобразуется в 8-разрядное 354-ичное слово. Проверочная матрица 11для такого случая имеет вид О О О О О 1 1 1 1 1 1Н = О 1 1 1 1 О О О О 1 1 101 23 01 23 01 Если в качестве проверочных символов выбрать символы, соответствующие столбцам с единственным ненулевым элементом, то матрицу Н можнопреобразовать к виду 9 10 11 К К К 1 0 0 0 1 О 0 0 1 2 3 4 2 З 0 О 1 1 1 0 2 3 1соответствующему разделимому коду:первые 8 символов слова (П 1-Ц 8) 55 информационные, три последних символа (К 1-КЗ) - контрольныеПри записи формируются значенияконтрольных разрядов 256100 1вол кода может принимать о значений,Огде с = 2 (ы = 1,2,3), Входноедвоичное слово, поступающее на вход 3блока 2, разбивается на группы по Оразрядов, ц -разрядная двоичная группа рассматривается как один и-й символ, Таким образом двоичному словуоднозначно ставится в соответствиео-ичное слово, которое кодируется всоответствии с порождающей матрицейобобщенного КХ, Если при записи навход ЗУ поступает двоичное Ь-разрядное слово, то оно разбиением на ивразрядные группы преобразуется вЬ цразрядное (К = - -) и-ичное (Ч=2 ),слово, Размерность проверочной матрицы Н кода определяется следующим об"разом. Количество строк матрицы находят из неравенства1 256100 зК 1=Ц 4+П 5+06+И 7+и 8 К 2 =и 1+П 2+ и 3+Н 7+П 8 20 КЗ=П 1+2 02+3 03+04+205+3 06+08 =М 1+П 4+П 8)+2 (02+05) +3 АЗ+06) . Значение К 1 формируется на сумматорах 19 (младший разряд) и 20 (старший разряд), значение К 2 - на сумматорах 21 и 22 соответственно, КЗ на сумматорах 31 и 32. При записи информации значение входа 57 равно нулю, а значение входа 58 равно едини-., це. На вход блока 1 поступают информационные разряды слова с выходов 15 4.1.1-4.8.2 блока 2, а также контрольные разряды (выходы элементов П 46, 48; 50, 52; 54, 56). При чтении (К+ш) -разрядное Ч-ичное слово или П(К+ш)-разрядное двоичное слово поступает в блок 2, гдевычисляется в-разрядный Ч-ичный синдром, поступающий с выхода 7 в блоки Зи 9.25Двоичное значение синдрома формируется на выходах сумматоров 39-44,где к сумме соответствующих информационных разрядов прибавляются значенияконтрольных разрядов, Прохождение содержимого контрольных разрядов на сумматоры 39-44 осуществляется через элементы И 33-38 под действием управляющего сигнала "Чтение" (выход 57),Блок 8 анализирует разряды синдрома и определяет величину ошибки,которая представляет собой значениепервого ненулевого символа синдрома,т.е, блок 8 пропускает на выход 10первый (при рассмотрении синдрома40слева направо) ненулевой символ синдрома.Блок 9 осуществляет деление синдрома на его первый ненулевой символ(на величину ошибки) в соответствии 45с таблицей деления. Деление символасиндрома на величину ошибки реализует преобразователь, выполненный, например, в виде ПЗУ.Разделенный на величину ошибки 50синдром представляет собой локаторошибки, т.е, один из столбцов матрицы Н. Для определения позиции искаженного разряда в принятом Ч-ичномслове необходимо сравнить вычисленный 55локатор с каждым из столбцов матрицы Н. Столбец, равный локатору, указывает местоположение ошибки. Разделенный на величину ошибкисиндром представляет собой локаторошибки, т.е. один из столбцов матрицы Н. Для определения позиции искаженного разряда в принятом и-ичномслове необходимо сравнить вычисленный локатор с каждым из столбцовматрицы Н, Столбец, равный локатору,указывает местоположение ошибки, Операцию сравнения локатора со столбцами матрицы Н выполняет дешифратор 13,На вход дешифратора 13 поступаетш-разрядный и-ичный локатор, При наличии ошибки в одном из символовичного считанного слова на соответствующем выходе дешифратора 13 появляется сигнал, номер этого выходаравен номеру ошибочного разряда слова.Величина ошибки с выхода 10 блока 8 поступает в блок 11. Коррекциясчитанной информации производится вблоке 5 сумматоров, исправлению под,вергается разряд, определенный в дешифраторе 13, к содержимому которогоприбавляется величина ошибки,Если синдром считанного слова отличен от нуля, а на всех выходахдешифратора 13 имеют место нулевые;сигналы (т,е, вычисленный локаторне совпадает ни с одним столбцомматрицы Н), то на выходе 18 элемента ИЛИ 16 индицируется сигнал "Ошибка". Формула изобретения 1, Запоминающее устройство с коррекцией ошибок, содержащее блок памяти, блок сумматоров, дешифратор, элемент И, элемент ИЛИ и блок кодирования и декодирования, вход которого соединен с выходом блока памяти, а первый выход подключен к первому входу блока сумматоров и вход; блока памяти, выход элемента ИЛИ соединен с первым входом элемента И, выход которого является управляющим выходом устройства, информационным выходом которого является выход блока сумматоров, о т л и ч а ю щ е е с ятем, что, с целью повьппения надежности устройства, в него введены блоканализа синдрома, блок преобразования синдрома, блок элементов И и элемент ИЛИ-НЕ, причем второй выход блока кодирования и декодированияподключен к входу блока анализа син-. дрома и первому входу блока преобра12зования синдрома, второй вход которого соединен с выходом блока анализа синдрома и первым входом блокаэлементов И, а выход подключен квходам элемента ИЛИ и дешифратора,выход которого соединен с вторымвходом блока элементов И, выход которого соединен с вторым входом блока сумматоров, выход дешифратора подключен через элемент ИЛИ-НЕ к второму входу элемента И,2, Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок анализа синдрома содержит блоки элементов И, элементы ИЛИ, элементы НЕ иблок элементов ИЛИ, выходы которогоявляются выходами блока анализа сиидрома, а входы подключены к выходамблоков элементов И, выход первогоэлемента ИЛИ подключен к одному из 56100 бвходов первого бл "а элементов И ивходу первого элемента НЕ, одни извходов второго блока элементов И соединены соответственно с выходом второго элемента ИЛИ, входом второгоэлемента НЕ и выходом первого элемента НЕ, одни нз входов третьегоблока элементов И подключены соответственно к выходам третьего элемента ИЛИ и элементов НЕ, причем входы элементов ИЛИ и другие входы блоков элементов И являются входами блока анализа синдрома,3, Устройство по п,1, о т л и ч аю щ е е с я тем, что блок преобразования синдрома содержит дешифраторыи преобразователи кодов, выходы которых являются выходами блока, а входы подключены к выходам дешифраторов,входы которых являются входами блока.125 б 100 оставитель В.Рудакоехред А. Кравчук Редакто ректор Л.Пилипенк о Заказ 4830 ВНИИ по035,аушская наб,оизводственно-полиграфическое предприятие, г,ужгород, ул, Проектная, 4 Тираж 543Государственелам изобретсква, Ж,Подписного комитета СССРий и открытий