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

.Крупский .Крупский щих устройики, серия роиство; н информаци рольных на дами, обоз - структур фиг.4 - схе ра, один из - схема узл ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(57) Изобретение относится к автоматике ивычислительной технике, в частности к полИзобретение относится к запоминающим устройствам (ЗУ) и в частности - к полупостоянным ЗУ с коррекцией ошибок.Известны ЗУ с исправлением (коррекцией) одиночных и обнаружением двойных ошибок в кодовых. словах, использующие код Хемминга,Недостатком таких устройств является невозможность коррекции более сложных ошибок.Известно также запоминающее устройство принятое эа прототип, способное корректировать более сложные ошибки и в том числе двойную ошибку в одной из строк или в одном из столбцов матрицы, образованной запоминающими элементами накопителя, Более сложные ошибки, например, две двойные ошибки в разных строках матрицы накопителя, данным устройством не коррек.тируются. а тройные ошибки и неисправности аппаратуры коррекции не обнаруживаются и некорректируются.Целью изобретения является повышение надежности путем увеличения коррекупостоянным запоминающим устройствам с коррекцией ошибок. Целью изобретения является повышение надежности устройства, Поставленная цель достигается за счет введения дополнительного накопителя контрольных разрядов кодов Хемминга, коммутаторов, образующих матрицу коммутаторов, дополнительных блоков коррекции, элементов сравнения, первого и второго элементов ИЛИ, инвертора и элемента ИЛИ, В случае возникновения двойных ошибок в строках или столбцах информационной матрицы элементы сравнения отключаются, 5 ил 2 табл.тирующей способности устройства, охвата контролем аппаратуры коррекции ошибок и обнаружение тройных ошибок.Поставленная цель достигается при помощи увеличения информационной избыточности путем введения дополнительного накопителя контрольных разрядов кодов Хемминга, дополнительных блоков коррекции и матрицы выходных коммутаторов, а также двухвходовых элементов сравнения (при помощи которых производится сравнение выходных сигналов основных и дополни 1 ельных блоков коррекции), двух элементов ИЛИ, инвертора и элемента И. г.1 показано предлагаемое уста фиг,2 - условные обозначения онного накопителя и двух конткопителей с ошибочными раэряначенными знаком "Х"; на фиг,3 ная схема блока коррекции; на ма узла синдрома и дешифратовозможных вариантов; на фиг,5 а коррекции, один иэ вариантов.1794261 Составитель . Е,Брикедактор Б,федотов Техред М.Моргентал Коррек Милюкова оизводственно-издательский комбинат "Патент", г. Ужгород ул.Гагарина каз 533 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 133035, Москва, Ж, Раушская наб., 4/5На фиг,1-5 и в тексте приняты следующие обозначенил: 1 - информационный накопитель, 2 - основной накопитель контрольных разрядов кодов Хемминга; 3 - дополнительный накопитель контрольных разрядов кодов Хемминга; 4 - основные блоки коррекции; 5 - дополнительные блоки коррекции; 6 - информационные выходы основных блоков коррекции; 7 - информационные выходы дополнительных блоков коррекции; 8 - сигнал двойной ошибки; 9, - двухвходовые коммутаторы; 10 - управлгиощие входы коммутаторов;11 - выходы коммутаторов, 12 - ДвуххаДО- вые элементь, сравнения:.13 - первый элемент ИЛИ; 14 - второй элемент ИГИ; 15 - ицвертор, 16 - двухвходовой элемент И; 17 - сииал оцибок блоков коррекции или тройной ошибки; 18 - узел синдрома; 19 - дешифратор; 20 - узел коррекции; 21 - сумматоры го модуло двд (свертки) узла синдрома; 22 - свертка полного кода Хеммицга;23 - инверторы;, 4 - четырехвходовые элементы И; 25 - входы элементов И 24; 26 - выходыдешифраторов 19; 27 - сумматоры по модуло двд; 28 - двухвходовые элементы И; 29 - иц Вертор; 30 - четы рехвходавой элемент ИЛИ; 31 - инвертор; 32-двухвходовой элемет И,Предлагаемое запоминаощее устройство состоит из информационного накопителя 1, первого контрольного 2 и;.тораго контрольного 3 накопителей, основных блоков коррекции 4, дополнительцых блоков коррекции 5, коммутаторов 9, элементов сравнения 12, первого элемента И)И 13, Второго элеме; та ИЛИ 14, инвертсра 15 и двухвходавого алел ецта И 16,1 саммутдторы 9 (фиг,1) составллот матрицу коммутаторов (на фиг,1 границь этой матрицы не показаны), содержащую и строк и гп столбцов, т,е, общее количество коммутаторов 9 равцо пгп,В информационном накопителе 1 имеется пп запоминающих элементов (например, одноразрядных микросхем памяти); и строк ип столбцов, Нд фиг, и 8, и =-8(8 ицформациацньх байтов по 8 разрядов в каждом). В основном контроль ом накопителе 2 имеет М контрольных ра.:рядов кода Хеммицга, Нд фиг,1 и -- . 8, К = 5, Г,к, для коррекции одино иЫх о 1 Ибок и абц;.сужения двойной ошибки В Восьми иц:.1 Ормаионных разрядах в коде ХемиП.а т 1 эебуетсл 5 кацтРсльных Рсэз 1 э 5 ДРВ, т,е. В кдж,",Ои 1-и (1 =и) строке ОСНОВНОГО контральн ГО накопителя 2 содсржится па 1 =-5 контрольных Раз)лалаксДс Хеммиц Гз, Отн ОсЯЩихсл к 1-Й строке информационного накопителя 1.А 1 ЭЛОГИспЬМ Обрдэам В ДОПОТИ 1 ЬТ ЛЬ- нсм контрольном накопителе 3 хрдн 5 тс 5 п контрольных разрядов кода Хеммингд: по=- 5 контрольных разрядов в каждом из глстолбцов - длл коррекции сдиночных и обнаружения двойных ошибок в соответству 5 ощем столбце накопителей 1 и 3.Для облегчения объяснения работыпредлагаемого устройства введем такиетермины как одиночные ошибки, двойныегоризонтальные и двойные вертикальные"О ошибки, тройные горизонтальные и тройные вертикальные ошибки. На фиг.2 а показан случай с пятьо одиночными ошибками,ца фиг.26 - одна одиночнал ошибка и однагоризонтальцал тройная ошибки, на фиг,2 В15 - одна одиночнал и одна вертикальная тройная, нд фиг,2 Г - ОДНО ОДиночнал и ОДнэ Двоицал Вертикальная, на фиг.2 д - одна двойналгоризонтальная ошибка и, и наконец, нафиг.2 е показаны две двойные ошибки - вер 20 тикдльнал и горизонтальнал, располокенные "углом",Предлагаемое устройство работает следуощим образом.При отсутствии ошибок, д также при на 25 личии только одиночных ошибок (фиг,2 а) навыходах 6 основных блоков коррекции 4 образуотся пгп (нд фиг,1 - 8 байтов по 8 разрядов) откорректированных информационныхсигналов, т,к, каждый из основных блоков30 коррекции 4, на входах которых имеется одиночндл ошибка, исправят ее.,По этой же причине нд выходах 7 дополнительных блоковкоррекции 5 также образуетсл пгп таких жеоткорректированных выходных сигналов35 (т,е, 64 выхода основных блоков коррекции4 совпадают с 6 Выходами дополнительныхблоков коррекции 5), Упрдвляощие входы10 коммутаторов 9, относящихся к Определецной строке накопителей 1 и 2 и соответ-.40 ствецно к определенному основному блокукоррекции 4, соединены между собой и свыходом 8 двойной ошибки данного основного блокэ коррекции 4, Поэтому при отсутствии двойной ошибки в данной строке45 накопителей 1 и 2 ца выходы 11 коммутаторов 9 данной строки, являющиеся информационньми выходами устройства, пройдутвыходные сигналы данного основного блокакоррекции 4,50 Поскольку для случал, показанного нафиг,2 а, Выходные сигналь 6 и 7 блоков коррекции - и 5 савпдДают, та на ВыхоДах ПГЙэлементов сраВнснил 12, праизВсд 51 щих пс-рязрядное побитнос сравнение информационных выхоДОВ 6 и 7 Обеих Групп блОкОВкоррекции обрдзуотсл си: лалы "0". Следовательно Ыходной с;Гцаг второго элемента ИЛИ 4 также будет равен "0", Выходнойсигнал первого элемецга ИЛИ 13 также равен "О", т,к, двойных олбок нет и выходныесигналы 8 всех и + п блоков коррекции 4 и 5, соединенные со входами первого элемента ИЛИ 13, также будут равны "О",. На выходе инвертора 15 образуется сигнал "1", ана выходе 17 элемента И 16 будет уровень "0", сигнализирующий этим о исправности блоков коррекции 4 и 5, Если при ситуации, показанной на фиг,2 а, произойдет сбой или отказ в каком-нибудь из блоков коррекции 4 и 5. то на выходе одного (или нескольких) элемента сравнения 12 и соответственно на выходе второго элемента ИЛИ 14, образуется сигнал ".1", который пройдет через двухвходовой элемент И 16, что и будет означать неисправность блоков коррекции,Сигнал 17 будет равен "1" еще в двух "случаях - при тройной горизонтальной или тройной вертикальной ошибке (фиг,2 б,в), Тройная ошибка воспринимается соответствующим блоком коррекции как одиночная, в результате чего этот блок коррекции к имеющимся трем ошибкам добавляет четвертую; Следовательно выходные сигналы 6 и 7 основных и дополнительных блоков коррекции в четырех разрядах (из 64) при тройной ошибке будут отличаться друг от друга, Поэтому на выходах четырех элементов 12 (т,е, на четырех входах второго элемент элемента ИЛИ 14) образуются сигналы "1", и на выходах элементов 14 и 16 также. образуются сигналы "1". Сигнал "1".на выходе 17 элемента И 16 таким образом позволяет обнаружить тройную ошибку, сигнализируя при горизонтальной тройной ошибке о неправлльной работе устройства (при вертикальной тройной ошибке устройство работает правильно, т,к. через соответствующие коммутаторы 9 все ошибочные разряды пройдут откорректированными - от основных блоков коррекции 4.Одиночные ошибки в случаях, показанных на фиг.2 б и в, будут откорректированны обычным путем (как при фиг,2 а),Рассмотрим теперь случаи с двойнымиошибками (фиг,2 г,д).При вертикальной двойной ошибке, показанной на фиг.2 г, она вместе с одиночной ошибкой будет откорректирована обычным образом, как при случае. показанном на фиг,2 а,При горизонтальной двойной ошибке (фиг.2 д) эта ошибка не будет откорректирована тем основным блоком коррекции 4, на входах которого имеется эта ошибка (т.к.обычный код Хемминга только обнаруживает, но не корректирует такие ошибки). Однако сигнал 8 двойной ошибки этого блока коррекции переключит все гп коммутаторов 9 этой строки и поэтому через эти коммутаторы данный байт пройдет не с выходов 635 40 45 50 ответствующим дополнительным блоком коррекции 5 (как в случае, показанном на фиг.2 д), Что касается ошибки, лежащей в вершине "угла", то эта ошибка откорректирована не будет, т.к, она входит в состав обеих двойных ошибок - как вертикальной,так и горизонтальной. Несмотря на этот недостаток предложенное устройство обладает значительно более высокой надежностью, чем устройство-прототип, Это происходит как благодаря полному контролю исправности блоков коррекции 4 и 5 (которые являются довольно сложными узлами), так и благодаря обнаружению тройных ошибок.На фиг.З показана структурная схема основного блока коррекции 4, который состоит из узла синдрома 18, дешифратора 19 и узла коррекции 20. Узел синдрома 18 вырабатывает сигнал двойной ошибки 8 и синдром - двоичный код разряда, в котором имеется одиночная ошибка, Дешифратор 19 дешифрирует этот код, а узел коррекции 20 производит инвертирование (т.е, коррекцию) дефектного разряда. Входными сигналами основных блоков коррекции 4, показанных на фиг,1, являются 8 информационных сигналов Р 1 - РЯ данного байта и пять контрольных разрядов К 1 - К 5 данной этого блока коррекции, а с выходов 7 дополнительных блоков коррекции 5 (для которыхдвойная горизонтальная ошибка являетсядвумя простыми одиночными, и поэтомукорректируемыми ошибками).При любой двойной ошибке на выходеэлемента ИЛИ 14 образуется сигнал "1". т.к,на выходах двух элементов сравнения 12образуются сигналы "1", Для того, чтобы"0 этот сигнал не прошел через элемент И 16,в устройстве предусмотрен первый п + евходовой элемент ИЛИ 13. входы которогосоединены с выходами 8 двойных ошибоквсех и + в блоков коррекции. Таким обра 15 зом, при любых двойных ошибках (вертикальных или горизонтальных) на выходепервого элемента ИЛИ 13 образуется сигнал "1", который через инвертор 15 блокирует прохождение через элемент "И" 1620 сигнала "1" с выхода второго элемента ИЛИ14, Другими словами, при двойных ошибкахпредотвращается ложный сигнал тревоги 17(при двойных ошибках этот сигнал тревогибыл бы ложным, т.к, двойные ошибки кор 25 ректируются),При двух двойных ошибках, расположенных "углом", как показано на фиг,2 е,, "нижняя" ошибка будет откорректированасоответствующим основных блоков коррек 30 ции 4 (как в случае, показанном на фиг.2 а)."Левая" ошибка будет откорректирована со1794261 40 строки основной контрольной матрицы 2, Информационными выходами блока коррекции 4 являются восемь откорректированных сигналов 6 данного байта,На фиг.4 показана одна из возможных схем узла синдрома 18 и дешифратора 19 основных блоков коррекции 4. Узел синдрома содержит четыре сумматора 21 по модулю два (свертки) С 1 - С 4, вырабатывающих 4 разряда синдрома в соответствии с табл.1 классического кода Хемминга. В каждом из четырех столбцов табл.1 указаны те разряды Р и К, которые подаются на входы данной свертки С,На входы каждой из сверток 21 подается только один контрольный разряд К, который при исправном устройстве дополняет до четности сумму по модулю два остальных входных сигналов данной свертки, Пятый контрольный разряд К 5 дополняет до четности сумму всех 12-ти разрядов кода Хемминга (Р 1 - Р 8, К 1-Р 4). Все эти 13 разрядов суммируются по модулю два сверткой 22, Поэтому выходной сигнал свертки 22 равен 1 при нечетной ошибке (в том числе при одиночной) и равен 0 при отсутствии ошибок или при четной ошибке (в том числе при двойной). Четыре инвертора 23 и инвертор 31 вырабатывают сигналы, инверсные вы. ходным сигналам сверток 21 и 22.Дешифратор 19 состоит из восьми (по . числу разрядов Р 1 - Р 8) четырехвходовых (по числу кодовых столбцов в табл,1) элементов и 24, На выходе каждого из элементов 24 вырабатывается сигнал 26 ошибки соответствующего информационного разряда Р, т,к. 4 входа 25 каждого из элементов 24 соединены с выходами сверток 21 и инверторов 23 (т,е, с выходами узла синдрома 18) в соответствии с табл,1, Например, входы 25 элемента 24, вырабатывающего сигнал ошибки разряда Рб, соединены с выходами сверток С 2 и СЗ и выходами двух инверторов 23, инвертирующих выходные сигналь 1 сверток С 1 и С 4. Такое соединение определяется строчкой Рб в табл,1 (код 0110). Поэтому, если в разряде Рб произойди ошибка,то на выходах сверток 21 образуется синдром, показанный в табл.2 (напомним, что при отсутствии ошибок, т,е, при четности количества единиц на входах каждой из сверток 21 выходные сигналы всех четырех сверток 21 равны нулю). Поэтому все четыре Формула изобретения Запоминающее устройство, содержащее информационный накопитель, основной. накопитель контрольных разрядов 5 10 15 20 25 30 35 входных сигнала 25 элемента 24 разряда Рб будут равны "1" и на выходе 26 этого элемента образуется сигнал "1", сигнализирующий об ошибке в разряде 6,Четырехвходовой элемент ИЛИ 30 складывает (по ИЛИ) выходные сигналы всех четырех сверток, вырабатываощих синдром. Поэтому при любой ошибке в 13 разрядах Р и К на выходе элемента ИЛИ 30 будет сигнал "1", Если при этом выходной сигнал свертки 22 равен 0(а выходной сигнал инвертора 31 равен 1), то это означает, что имеется двойная (точнее четная) ошибка и выходной сигнал 8 двухвходового элемента И 32 будет равен 1, Таким образом, если выходной сигнал двойной ошибки 8 на выходе узла синдрома 18 равен "1", то это означает наличие двойной ошибки в контролируемом 13-разрядном коде.Аналогичным образом строятся узлы синдрома 18 и дешифраторы 19 дополнительных блоков коррекции 5(при этом номера байтов и разрядов меняются местами).. На фиг,5 показана одна из возможных схем узла коррекции 20 основныхблоков коррекции 4, Схема содержит восемь двухвходовых сумматоров по модулю два 27, восемь двухвходовых элементов И 28 и один инвертор 29, Задачей, выполняемой узлом коррекции 20, является (при условии отсутствия двойной ошибки) инвертирование (коррекция) того выходного информационного сигнала Р информационного накопителя 1, в котором имеется ошибка, (т,е, того разряда Р, для которого соответствующий сигнал 26 "ош Р," на выходе дешифратора 19 данного основного блока 4 коррекции равен единице). В этом случае на обоих входах соответствуюшего элемента И 28 присутствуют два сигнала "1": один из них поступает с выхода инвертора 29 при отсутствиидвойной ошибки, а второй - сигнал 26 "ошР" - с соответствующего выхода дешифратора 19. Выходной сигнал элемента И 28, равный "1", подается на один из входов соответствующего двухвходового сумматора по модулю два 27, который и производит инвертирование (коррекцию) срответствующего информационного сигнала Р информационного накопителя 1.Аналогичнь 1 м образом строятся узлы коррекции 20 дополнительных блоков 5 коррекции. кодов Хемминга, основные блоки коррекции, первые входы каждого из которых соединены с соответствующими выходами информационного накопителя, а вторые1794261 Табл и ца 1 Та хо ные сигналы све ток 21 и и ошибке Р входы - с соответствующими выходами основного накопителя контрольных разрядов кодов Хемминга,отличающееся тем, ято, с целью повышения надежности устройства, ойо содержит дополнительный накопитель контрольных разрядов кодов Хемминга, коммутаторы, образующие матрицу коммутаторов, дополнительные блоки коррекции, элементы сравнения, первый и второй элементы ИЛИ, инвертор и элемент И, выход которого является выходом неисправности устройства, первые входы каждого из дополнительных блоков коррекции соединены с соответствующими выходами информационного накопителя, а вторые входы каждого из дополнительных блоков - коррекции соединены с соответствующими выходами дополнительного накопителя контрольных разрядов кодов Хемминга, информационные выходы каждого из дополнительных блоков коррекции соединены с первыми информационными входами коммутаторов соответствующего столбца матрицы коммутаторов, вторые информационные входы коммутаторов каждой строки матрицы соединены с информационными выходами соответствующего основного блока 5 коррекции, выход обнаружения двойнойошибки каждого основного блока коррекции соединен с управляющими входами коммутаторов соответствующей строки матрицы, выходы коммутаторов являются выходами устройства, 10 выход обнаружения двойной ошибки каждогоосновного и каждого дополнительного блока коррекции соединен с соответствующим водом первого элемента ИЛИ, выход которого соединен с входом инвертора, выход 15 которого соединен с первым входом элемента И, первый и второй входы каждого из элементов сравнения соединены соответственно с первым и вторым информационными входами соответствующего коммутатора, 20 выход каждого из элементов сравнения соединен с соответствующим входом второго элемента ИЛИ. выход которого соединен с вторым входом элемента И.