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

(46) 15.02.88. Бюл Вввй ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ АВТОРСКОМУ СОИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР В 433542, кл. 0 11 С 29/00, 1972.Авторское свидетельство СССР У 855730, кл. О 11 С 29/00, 1979. (54) ЗАПОМИНА 1 ОЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕИ ОШИБОК(57) Изобретение относится к вычисл тельной технике и может быть исполь зовано в качестве основного запоминающего устройства в вычислительных системах. Целью изобретения являетс повышение надежности устройства. 8013428 Устройство содержит блок 1 памяти,первый 3 и второй 23 коммутаторы,блок 3 кодирования, блок 7 элементовИ-ИЛИ, первый 10 и второй 21 регистры, блок 11 декодирования, блок 12коррекции, блок 15 обнаружения ошибок, элемент ИЛИ 16, первый 17 и второй 18 дешифраторы и блок 27 управления, В устройстве применяется сочетание кода БЧХ, исправляющего двухкратные и обнаруживающего трехкратныеошибки, и временной избыточности, аименно метода двойного инвертирования, сводящегося к поразрядному инвертированию слова, считанного иэ некоторой ячейки накопителя, записиего в ту же ячейку, считыванию и инвертированию. 2 ил 2 табл, 1374286Изобретение относится к вычислительной технике и может быть использовано в качестве основного запоминающего устройства в вычислительныхсистемах,5Цель изобретения - повышение надежности устройства.На фиг. 1 изображена структурнаясхема запоминающего устройства с коррекцией ошибок; на фиг. 2 - граф-схема алгоритма работы блока управления.Устройство содержит (фиг. 1) блок1 памяти, первый коммутатор 2, блок3 кодирования. Вход блока 3 является 15информационным входом 4 устройства.Первый информационный вход 5 коммутатора 2 соединен с выходом блока 3, авыход 6 - с информационным входомблока 1 памяти. Устройство также содержит блокэлементов И-ИЛИ, имеющий информационный вход 8 и выход 9,первый регистр 10, блок 11 декодирования, блок 12 коррекции. Второй информационный вход 13 блока подключен 25к первому регистру 10. Выход 14 блока11 соединен с входами блока 15 обнаружения ошибок и с входами элементаИЛИ 16. Устройство также содержитпервый 17 и второй 18 дешифраторы, 30одни из выходов которых обозначенына фиг.1 позициями 19 и 20, второйрегистр 21, имеющий выход 22, второйкоммутатор,23, имеющий вход 24 и вьгход 25, соединенный с третьим информационным входом 26 коммутатора 2, иблок 27 управления. Блок 27 имеетвходы 28 - 33 и выходы 34 - 43.Блок 27 управления может быть реализован в виде автомата Мили, графсхема алгоритма работы которого приведена на фиг. 2. На ней принятыследующие обозначения; В, ( = 0,7) -состояние автомата; В - начальноеосостояние автомата; У, (3 = 111) - . 45управляющие сигналы выдаваемые автоматом; Х(К = 1;6) - логическиеусловия (входные сигналы автомата);3 (1 = 1,5) - логические условия,зависящие от кратности и характераошибок и определяемые в соответствиис табл. 1: ц: Х,Х,ХХ, ч Х,Х,Х,Х- ХХХХ П - ХХХХ 11, - ХХХ ч ХХХХ 115 1111.1 1.1 в где,Х - дизъюнкция разрядов 1 - 1 О синдрома Б, Х, = В, ч В, чч В; получаемая на выходе элемента ИЛИ 16; Х. - значение нулевого разряда В, синдрома; Х, - дизъюнкция пяти старших разрядов д 1 кода, считываемого из блока 15, Х = и д, - значение5сигнала на выходе дешифратора 17; Х - дизъюнкция пяти младших разрядов В, кода, считываемого из блока 15,5Г д . - значение сигнала выхода дешифратора 18 (выходы дешифраторов инверсны; на возбужденном выходе дешифратора имеет место нулевой сигнал, на остальных - единичные сигналы).На основании граф-схемы (см.фиг. 2) построена структурная таблица автомата (табл. 2), которая содержит двоичные коды состояний В,. автомата, логические условия Х, 0, выходные сигналы У., При этом условие Х соответствует оигналу "Запуск", поступающему на вход 28 блока 27 из центрального устройства управления, условие Х- режиму работы (РР) запись (О) или чтение (1), поступающему на вход 29 блока 27 из центрального устройства управления (на фиг1 не показано).В устройстве используется модифицированный код БЧХ (с дополнительной проверкой на четность всего слова), исправляющий двукратные ошибки. Порождающая матрица такого кода представляется в видеО = 11 ЕОК 1и имеет размерность К ч и, где К - количество информационных разрядов; и - длина кодового слова (К = и - 2 ш); ш - целое положительное число, определяемое из соотношения 2 = и; Е - единичная матрица размерности К х К; О - подматрица размерности К х (и -1), строки которой представляют собой остатки от деления единицы с (К - 1) нулями на порождающий полином кода; К - столбец, равный поэлементной сумме по модулю два столбцов- и- матрицы ЕО , обеспечивает контроль по четности всего слова.Порождающую матрицу О неполного кода получают из соответствующей матрища полного кода путем вычеркиваниялишних строк и столбцов. Например,для получения порождающей матрицы неполного кода, позволяющей кодировать16" разрядные слова, необходимо в порождающей матрице полного (31, 21)кода БЧХ (и - 1 31, К = 21, ш = 5)вычеркнуть 5 верхних строк и 5 левыхстолбцов, в результате чего получит- О,1-м остатком от деления единицы снулями на полином который является порождающим для рассматриваемого кода.В соответствии с порождающей матрицей строят блоки 3 и 11. Блок 15 . может быть выполнен в виде ПЗУ.Устройство работает следующим образом. 86ся порождающая матрица (26, 16) кодаБЧХ, а затем к полученной матрицеприсоединить справа столбец, элементы которого равны сумме по модулюдва элементов соответствующих строкматрицы (26, 16) - кода БЧХ. Дпя (27, 16) - кода БЧХ порождающая матрица имеет следующий вцц: 111 001111 1 10010 0011 0 1010011101 1 1011111010 О 01011 1101 0 1100001010 1 Для инициализации устройства навход,28 блока 27 подается сигнал "Запуск".устройство функционирует в одном из двух режимов: "Запись" нли "Чтение".Наличие сигнала "Запись" (Х 0) на входе 29 блока 27 определяет режим записи. Подлежащее записи слово с входа 4 поступает в блок 3, где кодируется в соответствии с порождающей матрицей применяемого кода.По сигналу У = 1 (выход 34 блока 27 и по сигналам У, (37) = 1 (" Выборка74286 6 ние информации. Затем по сигналу Х 1 О 20 25 30 ся восстановление содержимого ячейки блока 1 памяти.Если и в первом и во втором циклах чтения слово содержит ошибку кратности три и бопее (1 = 1), то блок 27 выдает на выход 44 сигнал "Ошибка". Кроме того, если в процессе декодирования информации на входы 30-33 блока 27 поступает код Х Х,Х,Хотсутствующий в табл. 1 (при этом выполняется логическое условие У = 1), то независимо от цикла чтения инфор мации (первой или второй) на выход 45блока 27 выдается сигнал "Неисправность декодера". 50 5 3 кристалла") и Х (38) = 9 (" Запись" ) слово записывается в блок 1 памяти.Поступление на вход 29 блока 27 сигнала "Чтение" (Х, 1) определяет режим чтения. Блок 27 выдает с выходов 37 и 38 сигналы Х - 1 и Х - 1, которые поступают на управляющие входы блока 1. При этом на выходе 39 блока 27 сигнал Х, = 9. В соответствии с этими сигналами считываемое из блока 1 слово поступает в регистр 10 и блоки 11 и 12. Результатом работы блока 11 является значение Б синдрома и разряда Б, = В,. Значение В, поступает на вход 30 блока 27, Значение Б поступает на вход блока 15, а также через элемент ИЛИ 16- на вход 31 блока 27. Считанные по адресу Б номера (их двоичные значения) искаженных разрядов из блока 15 поступают на дешифраторы 17 и 18. При этом значения сигналов на нулевых выходах дешнфраторов 17 и 18 поступают на входы 33 и 32 блока 27 соответственно.Если считанное слово не содержит ошибок, то по сигналу Х = 1 с выхода 41 блока 27, поступающему иа управляющий вход коммутатора 23, содержимое блока 12 поступает на выход 25 устройства.Если считанное слово содержит однократную ошибку в разряде С то по сигналу Х = 1 с выхода 42 блока 27 в блоке 12 производится коррекция содержимого разряда С, и информация по сигналу Х, = 1 (выход 41 блока 27 через коммутатор 23 поступает на выход 25. Если Б ф О, то считанный по адресу Б код (из блока 15), ле вая Ь- и нравая Ь половины которого представляют собой коды двух номеров искаженных разрядов, дешифрируется дешифраторами 17 и 18, вследствие чего в блоке 12 производится коррекция двух разрядов считанного слова (или одиого разряда), если один из номеров Ь; или Ъ равен нулю.Если в считанном слове имеется двукратная ошибка или ошибка более высокой кратности, то по сигналу Х = 1 (выход 40 блока 27) содержимое блока 12 запоминается в регистре 21, а содержимое регистра О, поступая в коммутатор 2, по сигналу Х = 1 5 (выход 36 блока 27) инвертируется и записывается в блок 1 по тому же адресу, по которому производилось чте 1 (выход 38 блока 27) производится чтение содержимого той же ячейки накопителя, которое по сигналу Х = 1 (выход 39 блока 27) инвертируется и поступает в регистр 10 и блоки 11 и 12. Вновь считанное слово корректируется по описанному выше алгоритму. Если вновь считанное слово не со держит ошибок или содержит однократную ошибку, то содержимое блока 12выдается на выход 25, а также по сигналу Х = 1 (выход 35 блока 27), поступающему на соответствующий управляющий вход коммутатора 2, записывается в блок 1 памяти с целью восстановления информации в ячейке.При наличии в слове двукратной ошибки на выход 25 выдается содержимое регистра 21, которое поступает через коммутатор 23 по сигналу Х1 с выхода 43 блока 27, Если вновь считанное слово содержит ошибку кратности три и бопее ( = )то в первом цикле чтения информации из нако- пителя оно содержало двукратную ошибку (1 = 1), то информация на вход 25 также выдается из регистра 21.Следует заметить, что во втором цикле чтения при выдаче информации из блока 12 или регистра 21 производится. Формула и з о б р е т е н и я Запоминающее устройство с коррекцией ошибок, содержащее блок памяти, блок кодирования, блок декодирования, первый и второй регистры, блок обнаружения ошибок, блок коррекции, эле-, мент ИЛИ и блок управления, иричем вход блока кодирования является информационным входом устройства, адресным входам которого является ад1374286 Таблица 1 Ошибок н Однократная ошибкаОшибка в контрольном разряде 1 Двукратная ошибкаО Трехкратная ошибка (мая ошибка кратности О обнаруживае,9,) Обнаруживаемая оши4,6,8,кратности би Ос еисправность де ресный вход блока памяти, выходблока коррекции подключен к информационному входу второго регистра, управляющий вход которого соединен спервым выходом блока управления,вход запуска блока управления является входом обращения устройства,вход управления режимом блока управления является входом чтения-записиустройства, вход анализа нулевогоразряда синдрома блока управленияподключен к выходу блока декодирования, вход анализа разрядов синдромас.первого по десятый блока управления соединен, с выходом элемента ИЛИ,выходы элемента ИЛИ и входы блока обнаружения ошибок соединены поразрядно и подключены к группе выходов блока декодирования, второй и третий 2 Овыходы блока управления соединены соответственно с входом выборки и входом чтения-записи блока памяти,о т л и ч а ю щ е е с я тем, что,с целью повышения надежности устройства, в него введены первый и второйкоммутаторы, блок элементов И-ИЛИ,первый и второй дешифраторы ошибок,причем первый, второй и третий информационные входы первого коммутато Ора подключены соответственно к выходу-блока кодирования, выходу первогорегистра и выходу второго коммутатора, выход первого коммутатора подключен к информационному входу блока па- Змяти, информационные входы второгокоммутатора соединены соответственно. с выходом блока коррекции и выходомвторого регистра, выход второго ком мутатора является информационным выходом устройства, информационные входы блока элементов И-ИЛИ подключенык выходам блока памяти, выходы блока элементов И-ИЛИ соединены с входами первого регистра н входами блокадекодирования, выходы блока обнаружения ошибок подключены к входам соответствующих дешифраторов ошибок,первый вход признака ошибки блокауправления подключен к первому выходу первого дешифратора,ошибок, второйвход признака ошибки блока управления соединен с первым выходом второго дешифратора ошибок, информационные входы блока коррекции подключены соответственно к вторым выходамдешифраторов ошибок и выходам блокаэлементов И-ИЛИ, четвертый, пятый ишестой выходы блока управления соединены соответственно с первым, вторым и третьим управляющими входамипервого коммутатора, седьмой выходблока управления подключен к управляющему Входу блока элементов И-ИЛИ,восьмой и девятый выходы блока управления соединены соответственно спервым управляющим входом второгокоммутатора и управляющим входом блока коррекции, десятый выход блока управления подключен к второму управляющему входу второго коммутатора,одиннадцатый и двенадцатый выходыблока управления являются соответственно выходом Неисправимая ошибка"и выходом "Ошибка декодирования" устрой ства.информации нз блокаемого словаданных с блока 12101 манин из блока 1 памятикоммутатора 23; с дааеа регистра 21одарап. Т 1 И в 111) соответствует следующимод 37 блока 27) выборка кристалла