Устройство для обнаружения и исправления ошибок в блоках памяти

(,) С 11 ОПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВИ ЕЛЬСТ и.рек ПАМЯТИвычисыть исства двойных Ж 4 Ь 4 Ьа ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИНМПРИ ГКНТ СССР(56) Авторское свидетельство СССФ 1070605, кЛ. С 11 С 29/00, 198Авторское свидетельство СССРйо заявке У 437143424-24,(54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ИИСПРАВЛЕНИЯ ОШИБОК В БЛОКАХ(57) Изобретение относится клительной технике и может бпользовано в качестве устройдляобнаружения и исправления и пакетных ошибок в блоках памят Цель изобретения - повышение кор тирующей способности устройства.Устройство содержит 0 блоков генераторов кода и исправления ошибокгруппу блоков 2 свертки по модулю два по числу,разрядов блоков памяти, группу 3 из И блоков коррекдии 4, ,группу из И индикаторов неисправно 1стей 5, группу из И блоков коммутаторов б, блок обнаружения ошибок 7. Устройство реализует трехмерный ите-. ративный код и позволяет исправлятьдвухбитовые и пакетные ошибки, а также одиночные ошибки, внесенные во входную информацию при записи. 5 ил.(1 ш = йп(вх) + 3,Например, при искажении девятогоразряда информации 1-го блока памяти символа 186 кодовой матрицы(128,64) трехмерного кода (Фиг.З),мажоритарный элемент 249 каждого блока 1 -11 Й реализует Функцию (Фиг,5):9 ЙО Й 9(вх) (Й 9(вх)+ 0(ЗЙИ Й 9(вх)к 69(вх)+ Ъ 1 Ч 69(вх)+ 0 З ха 9(вх) + Р 1,30 35 При возникновении одиночной ошибки в 1-м блоке памяти на выходах 10 и 11 индикатора неисправностей 50 появляется,код "01" (корректируемой ошибки 1-го блока памяти) по Формулам 45 "КО " = ("Зп") (М з. ЧЗ) хР"НКО " = ("Зп") ("КО) ха (О( Ч Ч о и Ч 31 ЧЧп),Эти Формулы означают, что код "01"55 (корректируемой ошибки 1-го блока памяти) Формируется на выходах 15 и 16 при появлении только одного единичного разряда синдрома (,1-(.п или 19 16496 является для устройства корректируемой ошибкой), то код ошибки, полученный на выходах 15 и 16 генератора 199 имеет следующий вид: на контрольных выходах 15(н и 16одновременно появляются единичный" разряд синдрома О и "единичный" разряд синдрома З, а на остальных (2 п) выходах 15 Р и 16 н сохраняются 0 . На выходах сумматора 22 щ и1 1110 23 по модулю два, где ш = п (-1)+1, Формируются два инверсных значения одного искаженного символа входа 8 устройства; йо (вх) +и сш (вх)+ + Я 3, )(оступающие на второй и третии вход мажоритарного элемента, ормируя на выходе 14 блока 1 инверсное (т.е.исправленное) значение ЫО символа с)ш (вх)по Формулам: 15 201 - п, а код "10" (некорректируемой: двойной им пакетной ошибки 1-го блока памяти) Формируется при появлении двух или более "единиц" в разрядах синдрома 0 1 в Мп или ф 1- и , причем в режимеЧтение" код ошибки 1-го блока памяти "0111 или "10" Формируется в парайазном виде в то время, как в режиме "Запись" код ошибки имеет вид "11", т.е. в режиме "Запись" Коу = НКО. Это различие учитывается блоком 7, обнаружения ошибок, который, анализируя 2 Н-разрядный код ошибок (признаков ошибок И блоков памяти), формирует четырехразрядный код на выходе 12 (признаков ошибки устройства) в режиме "Запись" или "Чтение" по разным Формулам.Работа блока 7 в режиме. "Чтение" запрограммирована по Формулам:"нка" = ("нпчш 11) ("ко")Из этих Формул видно, что в режиме "Чтение" на выходах 12 устройства,могут появиться только две разрешенные комбинации: "01 10" (приз.9 .нак корректируемой ошибки устройства) или "1010" (некорректируемой ошибки Устройства). Появление любой: другой "ненулевой" комбинации расценивается как "запрещенная", т,е, свидетельствует о неисправности в самой схеме контроля.тТаким образом, корректируемойошибкой устройства (в режиме "Чте- " ние") является возникновение одиноФ" ных ошибок в И блоках памяти, которые независимо исправляются в блоках 1 - 1/, реализующих мажоритарно-синдромный . алгоритм деко,цирования, или возникновение навходах 8 устройства только одной (двухбитовой или пакетной) некорректируемой ошибки в 1-м блоке памяти, которая исправляется в коммутаторах 6 ЙЧ методом "адаптации": отклю 16496чением от выхода 9 устройствавыходов 14 блока 1 и подключением к выходу 9 устройства выходов 18 блока коррекции ошибок 4. В данном случае возникновение одиночной некор 5 ректируемой ошибки на входах 8 устройства, .на контрольных выходахустройства сохраняются "О", на контрольных выходах 10 устройства появляется унитарный М-разрядньй код некорректируемой ошибки. блоков памяти:"НК 0"НКа,Ч У НК 0, Ч НКОЧ ЧМ Н 0)15 а на выходах 12 устройства формируется код "0110" корректируемой ошибки устройства.Если же на входах 8 устройства появляются две и более некорректиру емые ошибки (например, при отказах двух блоков памяти или отказе одного блока памяти и возникновении одиночной ошибки в другом блоке памяти и т.п.), на контрольных выходах 10 и 11 устройства появляотся две и более "1", а на выходах 12 устройства формируется код "1010" некорректируемой ошибки устройства, и работа устройства прерьвается. 30Рассмотрим работу устройства в режиме "Чтение" в случае полного отказа одного из И блоков памяти при реализации в устройстве трехмерного кода (128,64) с параметрами и = 4, И = 2 п = 8, кодовая матрица которого представлена на фиг.З.При полном отказе пятого блока памяти (и отсутствии ошибок в других блоках памяти) на входе 8 возникает 40 пакет однонаправленных ошибок типа "16 нулей" или "16 единиц":15 22рицы будет содержать четное (запрещенное) число единиц, при этом навыходах 15 и 16 генератора 19;- копяошибок формируется "единичный" восьмиразрядный код синдрома: "1111 1111",соответствующий пакетной ошибке 5-гсблока памяти,Анализируя данную комбинацию синцрома, индикатор, неисправностей 5"сформирует на выходах 10 и 11 коу,некорректируемой ошибки "10" пятогоблока памяти. На контрольных выходах11 устройства сохраняются восемь "0",а на выходах 10 формируется унитарыйвосьмиразрядный кор 00001000, Анализируя 16-разрядный код сшибк наконтрольных выходах 10 и 11 устройства, блок 7 сформирует на выходах 12четырехразрядный код "01.10" к рректируемой ошибки устройства. В блоках .21-28 и в блоке 4 коррекции ошибокГформируется вторая группа скоррек тированных значений входа 8 устрой ства, которая по выхорам 18 (вторыминформационным входам копут;.тора б)поступает на информационный выход9 устройства, Одновреме;:.но на информац онные выход Э. -9 Ф . 9 Г 9 В устройства поступают первье группь скор=ректированных значений вхороь 8 - ц,86- 8- устройства (с выходов 14блоков 1 -1 1-1 ), так как нуправляю 11 е ьходе комутатора б присутствует "1" (контрольный выход 10устройства), а на управляющем входекоммутаторов б,. -б, 6 - и 68 - "0"(контрольные выходы 10-10 10 ь -10устройстьа), Затем скорректированная128-разрядная информация считываетсяс выходов 9-9устройства на выходную магистраль данных.Если, например, г. пятом блоке памяТи было записано кодовое слово01 000 струкдву5 нечет- нтролькодг,- пред" ении а ошидиниц"ой матСогласно модифицированной туре примененных в устройств мерных кодов: с контролем по ности строк и столбцов и с к ным разрядом по нечетности С вая подматрица Нкоторого ставлена на фиг, 3, при появ на входе 8 устройства паке бок типа "16 нулей" или "16 каждая строка и столбец кодо при отказе 5-го блока памяти типа "1 б,единиц" на входы 85. устройства поступит информация с шестью искаженными символами С , а 2, Яб, Ь 1, Ь 2, ЪЗ, в разрядах соответственно Й 1, 68, 69, с 113, 614 и 615 пято го блока памяти, на выходах 17 бло ков свертки по модулю два 2, 2,649615 2, 2 2 14 и 2 сформируются шесть ва): 1 д 1, Яс 11, 9 й 1, 1 Зс 1, 140 1 и 156единичных разрядов синдрома: 41, )8, а на остальных десяти выходах 18 бло(9, 413, 114 и 1 15, а на выходах ка 4 О сохраняются "1" (правильныедесяти других блоков свертки 2 (из значения десяти (из шестнадцати) сим общего числа 16) сохранятся "0".волов входа 8 устройства, Затем в. На выходах шести сумматоров по коммутаторе 6 происходит исправле;Умодулю два бЛока 4 к сформируются ние шести искаженных символов вхсда,"0" (исправленные значения шести ис устройства по формулам:каженных символов входа 8 устройст 5 С (вых) - (НКО ) (1 аО)(НКО ) 1 5 Со (вх) + У 1,5 а 2 (вых) = (НКО) (8 с 10) 7 (НКО) 5 а 2(вх) + )81)5 Б 6 (вых) = (ЙКО) (ЫО) М (НКО) 5 Бб(вх) +9;5 Ь (вых) = (НКО) (1 Зс 10)(НКО ) 5 Ь 1(вх) + 1 13 Д )НЬ 2 (ввх) = (ЙКО ) (14 ЙО) Ч(НКО 1) ) НЬ 2(вх))ф 141,5 ЬЗ (вых) = (йКО) (15 ао)Ч(НКО ) 5 ЬЗ(вх) + У 15,При отсутствии ошибок (если бы символ Бб, поступивший на вход 8 с,бып неискажен) правильно сформированное кодовое слово выглядело следующим образом: оди 30неример а) каолами аЗ для записи в 16-разрядное ого кода подщее уже три ис аЗ и 5 Ь 1 память сфор кодовое сл матрицы Н каженных с (подчеркну мировалось во двумернсодержа мвола 5 Бб,ы):(Пример в) Пример б) На выходах 9 формируется 128-разрядноекодовое слово с шестью исправленными символами входа 8, устройства.Аналогично исправляются все девять информационных разрядов: Со Б 1-Б 8 и контрольный разряд е пятого блока памяти,Рассмотрим случай исправления ночной некорректируемой ошибки, в сенной в кодовое слово при записи (обнулением семи контрольных разрядов пятого блока памяти), Этот случай бып рассмотрен при описании ра боты предлагаемого устройства в режиме "Запись" (пример с и Е ) и заключается в следующем.В режиме записи в память на входы40 8 устройства поступило четное девятиразрядное сообщение с одним ис женным символом 5 Б 6 = "1" (подчеркнут): 100 011 111. На выходах 14 блока 1 сформировались семь контрольных разрядов пятого блока памяти с двумя направильными симв11011 и Ъ 1 = 11", т.е т. е. Бб = "0", аЗ = "1", Ъ 1 = "О".Как было описано выше, данная трехбитовая ошибка двумерного кода является некорректируемой ошибкой устройства (в режиме чтения), так как при считывании кодового слова (пример б) из 5-го блока памяти на выходах 15 и 16 генератора 19 кода ошибок был бы сформирован синдром: 0001 0001, который индикатор .неисправности 5 воспримет за корректируемую одиночную ошибку в разряде е , в результате чего вместо некор- р Уректируемой трехбитовой ошибки в разрядах 5 Бб, 5 аЗ и 5 Ъ 1 будет ложно "исправлена" ошибка в разряде 8 р и на выходы 9 устройства поступит кодовое слово уже с четырьмя ошибочными символами (подчеркнуты):1649615,2,ходе 12 блока 7. Поэтому в устройстве обеспечивается контроль всех цепей коррекции и обнаружения ошибок самого. устройства. При этом неисп 5 равности самого устройства исправляются или обнаруживаются наравне с ошибками в блоках памяти.,формула из о бр ет ения Устройство для обнаружения и исправления ошибок в блоках памяти, содержащее блок генераторов; кода и исправления ошибок, блок обнаружения ошибок, выходы которого являются первой группой кон 3 рольных выходов устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения корректирующей способности устрой ства, в него введены с второго по И-й блоки генераторов кода и исправления ошибок, где Б - число блоков . памяти, группа блоков свертки по модулю /два по числу разрядов блоков памяти, 25 группа из Н блоков коррекции ошибок, группа из И индикаторов неисправностей и группа Из Ю коммутаторов,информационные выходы которых являются информационными выходами устройства, , 30 входы блоков генераторов кода и исправления ошибок являются инйормационными входами устройства и соединены с соответствующими входамисоответствующих блоков свертки помодулю два группы и входами первойгруппы соответствующих блоков кор"рекции ошибок группы, входы второйгруппы которых соединены с выходамиблоков сумматоров по модулю двагруппы, выходы блоков коррекции оши-бок группы соединены с информационными входами первой группы соответ-ствующих блоков коммутаторов группы, информационные входы второйгруппы которых соединены.с информационными выходами соответствующихблоков генераторов кода и исправления ошибок, контрольные. выходы которых соединены с информационными входами соответствующих индикаторовнеисправностей группы, выходы котбрых соединены с входами блока обнаружения ошибок и являются второйгруппой контрольных выходов устройства, управляющие входы индикаторовнеисправностей группы объединены иявляются управляющим входом устройства, управляющий вход каждогоблока коммутаторов группы соединенс выходом некорректируемой ошибкисоответствующего индикатора неисправностей группы164 3615 Составитель М,ЛапушкинТехред М,дидык Корректор С,Шекмар ктор А,Ле а Производственно-издательский комбинат "Патент" Гагарина, 101 Ухгор Заказ 1525 Тираж 352 Подписное ВНИИПИ Государственного комитета по изобретениям и открытия113035, Москва, Ж, Раушская наб., д. 4/5Изобретение относится к вычислительной технике и может быть использовано в качестве устройств для обнаружения и исправления двойных ипакетных ошибок в блоках памяти,Цель изобретения " повышение корректирующей способности устройства.На фиг.1 представлена структурнаясхема устройства для обнаружения иисправления ошибок в М и -разрядныхблоках памяти; на фиг. 2 - функциональная схема логического блока коррекции 1 р (где 1 - номер блока памяти); на фиг. 3 - геометрическая интерпретация кодовой матрицы трехмерного кода (128,64) с параметрами и = 4И = 2 п, составленного из восьми подматриц НДдвумерного итеративного,кода (16,8); на фиг, 4 - схема формирования контрольных разрядов 1 ар1 Ь 1 для 1-го блока памяти в режиме "Запись" (где 1 - номер строки,1, - номер столбца двумерного кодаб2.,иф, (и - 1) ; на фиг. 5 - схема коррекции одного (ш-го) разряда информации Я 6 (хр 3 р 1) 1-го блокапамяти, где 1, 1 р 1 - координатыпозиции символа 86 в кодовой матрицетрехмерного кода, д=и (1-1)+3.Устройство содержит (фиг.1) блоки1 р -1 генераторов кодов и исправле 2ний ошибок, И-входовые блоки 2 б свертки по модулю два, группу 3 изблоков 4-4 коррекции, каждый изй 35которых состоит из и сумматоров помодулю два, блоки 5-5 1 индикаторовнеисправностей , блоки 6 -6коьщутаторов и блок 7 обнаружения ошибок.Устройство имеет информационные81-81 группы входов, информационные9-9 м группы выходов, а также вторую10,-10 и 11- 111 и первую 12 р 12 р12 р 12 группы контрольных выходовустройства, управляющий вход 13 Устройства.Блоки 1 р -11 имеют информационные14 и контрольные 15 и 16 выходы.Блоки 2 р свертки по модулю дваимеют выходы 17, а блоки 41-4 коррекции ошибок имеют выходы 18,Каждый логический блок 1 коррек-.ции (1 = 1"И) содержит (фиг.2) и -входовой генератор 19 кода ошибок,состоящий из и-входовых блоков 20 и21 свертки по модулю два, первый 22.и второй 23 блоки коррекции ошибок,йкаждый из которых состоит из и сумматоров по модулю два, и блок 24 мажо-ритарных элементов, состоящий иэ итрехвходовых мажоритарных элементов, реализующих функцию (Ъ 2), причем информационные входы каждого ло"гического блока коррекции 1 подключены к входам блоков 20 и 21 генератора 19 кода ошибок и входам первой группы блоков 22, 23 и 24 в соответствии.с подматрицей Врвумерногомодифицированного итеративного кода(181, Ы 1, С 1),(18 К, 18 К, СК)обозначены информационные разрядытрехмерного кода (Иир ИК)рпоступающие в режиме "Запись" на информационные входы 8 -8, устройства, где И -число плоскостей кодовой матрицы трехмерного кода(фиг.З);, 1 - номер плоскости кодовой матрицы, и и К - соответственно общее число разрядов ичисло информационных разрядов в каждой плоскости кодовой матрицы (К == и -2 и), символами 1 а 1-1 аи и 1 Ь 11 Ьи - контрольные разряды по нечетности соответственно для и строк и истолбцов каждой подматрицыН двумерного итеративного кода ир (и)формируемые в режиме "Запись" соответственно на первых 15 и вторых 16контрольных выходах логического блока коррекции 1 р,символами я 1 р я 1 рдИ - контрольные разряды общей четности соответственно для И двумерныхитеративных кодов, формируемые врежиме "Запись" (фиг,4) на информационном выходе 14 каждого ЛБК 11 -11причем для каждого (1-го) правильнозакодированного и -разрядного кодового слова, значения контрольных разрядов 1 аи,. 1 Ьи, 81 равны между собойи равны 1": (1 ап = 1 Ьи =81 = " 1"),символами 10(пМ и и 11 -1 иразряды синдрома, формируемые в режиме "Чтение" соответственно на первых 15 и вторых 16 контрольных выходах каждого логического блока коррекции 1 е . На фиг. 3 стрелками (-У), ( ф), (- ) указаны грузны разрядов, входящих в х-ю строку и 1-й столбец подматржцм НбД, а также р ш-е ребро кодовой матрицы трехмерного кода, участвующие в коррекции каждого разряда Й(1 р,1 р 1) трехмерного кода, где 1 р 1 р 1 - координаты каждого символа в кодовой матрице трехмерного кода.5 16На фиг.4 и 5 символами 1 йщ -Ющобозначены одноименные (щ-е) разряды Н блоков памяти, входящие в щ-еребро кодовой матрицы трехмерногокода щ =и (1-1) +1, гдекоординаты каждого символа 1 йщ всоответствующей подматрице Нд дву- мерного кода (фиг.З).Схема обнаружения некорректируемых (НКО) и корректируемых (КО) ошибок устройства состоит из последовательно соединейных блоков свертки201-201 и 21 -21 ЛБК 1-1, формирующйх на контрольных выходах 15 -15 и 161 "1611 (2 Я п)-разрядный кодсиндрома, индикаторов неисправностей 5 1-5 Н, формирующих на контрольных выходах 10- 1011 и 11,-111 устройства 2 Н-разрядный код ошибки(НКСГ-НК 011, КО -КО) и логическогоблока 7 обнаружения ошибок, формирующего на выходах 12-12 устройства четырехразрядный код признака корректируемой (или некорректируемой) для устройства ошибки (НКО, КО,Нп 4 щ, Нп 3 п).При отсутствии неисправностей всамой схеме обнаружения ошибок в .каждом цикле работы устройства (какв режиме записи, так и в режиме чте 1ния очередного (Н и )-разрядного ко-,дового слова, поступившего на входы8 устройства), на выходах 121- 12,устройства может появиться толькоодна из пяти разрешенных комбинаций,каждая из которых является кодомпризнака соответствующей ошибки устройства:1) "ОООО" - признак отсутствияошибок в режиме "Запись" или"Чтение",2) "0101" - признак корректируемой ошибки в режиме "Запись" )3) "1001" - признак некорректиру. емой ошибки в режиме "Запись";4),"0110" - признак корректируе- .мой ошибки в режиме "Чтение",5) "1010" - признак некорректируемой ошибки в режиме "Чтение".Любая другая комбинация (кромепяти перечисленных) является для устройства "запрещенной" и свидетельствует о неисправности в самой схемеконтроля.Каждый индикатор неисправностей5-5 1 настроен на неисправноститолько одного (нсобственного) блокапамяти и служит для выявления коррек 49615.6тируемых (одиночных) или некорректнру)емых (двойных и пакетных) ошибок ви -разрядном кодовом слове двумерного2итеративного кода, поступающем в каждом цикле Запись или 1 Чтение" насоответствующие информационные входы8 устройства ( где 1 - номер блока памяти) .Устройство (фиг.1) для обнаружения и исправления и -разрядных ошибок в Н блоках памяти (где и и Мчетные числа) реализует трехмерныймодифицированный итеративный код15(Ип,ВК), составленный из М двумерных модифицированных кодов и(п) .Кодовая матрица трехмерного кодаимеет две проверочные (Би)-разряд 20 ные плоскости А и В, составленные изконтрольных разрядов по нечеткостистрок (1 а) и столбцов (1 Ь) подматриц Н 1-Ндвумерного кода.Первое (проверочное) ребро кодо 25 вой матрицы трехмерного кода (первые 161-НЙ 1 разряды подматриц Н-Н удвумерного кода) составлено из Иконтрольных разрядов (1 С -С) по неочетности для Н (К)-разрядных сооб 30 щений, поступающих на входы 8-8устройства для кодирования и записив память, а И-я (проверочная) плоскость (информационные разряды подматрицы Н составлена из К контй35рольных разрядов (С 1-СК) по четности для К И-разрядных информационныхребер кодовой матрицы трехмерногокода.Например, информационный разряд40 586 трехмерного кода (128,64), имеющий в кодовой матрице (фиг,З) координаты (3, 1, 5), является соот.ветственно символами 5 Й 8, т.е. зани,мает девятую позицию в подматрице45, Н двумерного кода (16,8) и расположен на девятом (информационном)ребре кодовой матрицы трехмерногокода,Контрольные разряды 1 а, 1 Ь 1 и50 я 1, расположенные в двух проверочнйх плоскостях А и В трехмерногокода и соответственно имеющие в ко"довой матрице координаты (д, п, 1),(п1) и (и, п 1) ЯвлЯютсЯ сим55 волами 1 Й 61, 1 П(+ 1 и 1" (йР)Например, контрольные разряды 5 аЗ,5 Ь 1 и я 5 трехмерного кода (128,64) являются соответственно символами 5414,5 ф)и 5 й, т,е, занимают 12-ю, 13-ю и16-ю позиции в подматрице Н - двумер 5ного кода (1.6,8) и расположены соответственно на 12-м, 13-м и 16-м (проверочных) ребрах кодовой матрицытрехмерного кода.Устройство (Фиг.1) работает следующим образом.В обоих режимах работы (иЗаписьиии 10и Чтение" ) используются все блокиустройства.Кодирование информации в режимезапнси ее в И блоков памяти заключается в Формировании контрольных разрядов 1 а 3. и 1 Ъ,1 (1 = 1-М; х, 1 = 1-и)двух проверочных плоскостей ь и Вкодовой матрицы трехмерного кода(Фиг.3) и происходит в два этапа.В режиме "Запись" на управляющийвход 13 устройства поступает и 1", ана информационные входы 8-8 И устройства с входной магистрали данных од 2новременно поступают К -разрядныхсообщений (где К = п), каждое из 25которых при отсутствии ошибок должно содержать нечетное количествоединиц.На первом этапе цикла "Запись"каждая К -разрядная группа входов28 обрабатывается независимо от другик групп входов: 88 И ,1,8(+,),.. ,8 И соответствующим блоком 1 и индикатором неисправностей5 Р. При этом в каждом блоке 1(фиг,2и 4) в соответстппи с подматрйцейН двумерного кода, Формируютсяконтрольные разряды по нечетностистрок а, - О,и столбцов Ь - Ькоторые по контрольным выходам 15 40и 16 блока 1 поступают для анализана входы индикатора неисправностей5 а по информационным выходам 14блока 1- на первую группу информационных входов коммутатора 6 длядальнейшей обработки. Одновременнона (2 п) выходах 17 соответствующих блоков свертки по модулю два:2, 2 и 12 и 2(п+,1-2(п) Формируются 0 , которыебез измененияи ипроходят на выходы соответствующихш-х сумматоров по модулю два (ш=хп,Кп+1, п) (гдеш = и (1-1)+3 - номерребра кодовой матрицы ) блока 4коррекции ошибок, Формируя на соответствующих (ш-х) выходах 18 "нулевые"значения контрольных разрядов 1 а 1-1 аК1 Ь 1-1 ЬК, я 1, которые поступают навторую группу .информационных входов коммутатора б. Заканчивается первый этап цикла иЗаписьи формированием на выходе 10 каждого индикатора неисправностей 5 управляющего сигнала (иОи или и 1 и), который поступает на управляющий вход коммутатора 6, и Формированием на контрольных выходах 10 и 11 устройства 2 Ы-разрядного кода ошибки записи: (НКО - НКО, КО -КОи), который поступает для анализа на входы блока 7 обнаружения ошибок.На втором этапе цикла иЗаписьи в устройстве работают коммутаторы блоков б,- б 1 и блок 7, Коммутаторы 61- бв зависимости от значений управляющих сигналов (иОи или и 1 и) пропускают на выходы 9 -9 для записи в память значения сформированных контрольных разрядов или иОи, Блок 7 Формирует на выходах 12 соответствующий признак ошибки записи.Работа индикаторов неисправностей 5-5 и в режиме "Запись" начинается при поступлении на управляющий (2 п+1)-й вход каждого из "1 и (высокого убовня напряжения) и запрограммирована по Формуле; НКО= КО = иЗпи (а 1 + а 2 ++ аК Ь 1 + Ь 2 + + ЬК)Ч ап ( Ьп 3.При отсутствии ошибок в (Ы К ) разрядной информации, поступающей в очередном цикле записи на информационные входы 8 -8 и устройства, каждое Кф-разрядное сообщение входа 8 устройства должно содержать нечетное количество "единиц". Поэтому (при отсутствии ошибок в самих генераторах 19 кода ошибок каждого блока 1) контрольные разряды по нечетности а 1 - о.К и Ь 1 - ЬК, сформированные на конт-,"рольных выходах 15 (р(1 - 0(К) и 16 ф 1- рК) каждого блока 1 должны со" держать четное количество "единиц", а контрольные разряды ап и Ьп на выходах 15 (К п)и 16 ( Р и) должны быть равны и 1", причем значения конт рольных разрядов ц 1-цИ общей четности, одновремейно Формируемых на последнем Ип)информационном выходе 14 каждого блока 1, также должны(М а й В этом случае на первом 10 и втором 11 выходах индикаторов неисправностей 5-5 сохраняются и 0", что соответствует отсутствию ошибок в при" нятом для записи (ИК)-разрядном сообщении, Соответственно, на пер9 1 вых (НКО -НКО 1) и вторых (К 01- КОц)- контрольных выходах устройства Формируется 2 Н "0", поступающих на втором этапе цикла "Запись" на входы блока 7 и (по выходам 10 .индикаторов неисправностей 5-51) на управляющие входы коммутаторов 6-61 л пропуская на информационные выходы 91-9 11 устройства (2 п"1) контрольных разрядов сформированного трехмерного,кода, поступивших на первую груп информационных входов коммутаторов , 6611 с информационных выходов 14 блоков, 11-111. Одновременно. на выходах 12-1211 блока 7 Формируются код "0000" (признак отсутствия ошибок на входе 8 устройства), разрешающий запись в память сформированного (Н и )-разрядного кодового слова трехмерного 1 кода, В конце цикла "Запись" сформированное кодовое слово по информационным входам 8 -8 устройства (НвК разрядов входного слова) и по информационным выходам 9-9 я устройства (контрольные разряды 1 Ь 1, Ч 1, 1 ах, сформированные ,для Б, двумерных кодов) записывается в Ю блоков памяти, причем в каждый блок памяти будет записана одна и в .разрядная плоскость кодовой матрицы (Фиг.З).Если же в режиме "Запись" входное,(Н Х )-разрядное сообщение поступает с одной ошибкой т.е. одно из Б (1-е) К -разрядное сообщение, поступающее на информационный вход 8устройства, содержит четное количество "единиц", то сформированные контрольные разряды по нечет- .ности 1 а 1-1 аК и 1 Ь 1-1 Ь 1 на выходах 15 и 16 одного блока 1 будут соответственно содержать нечетное количество "единиц". В данном случает на выходах 10 и 11 индикато.ров неисправностей 5(-5(-51+,1 - 5 р по-прежнему сохраняются "0", а на выходах 10 и 11индикатора неисправностей 5 Р Формируются две "1", что соответствует одиночной трехбитовой ошибке (некорректируемой логическим блоком коррекции 1 в режиме "Запись" ), которая одновременно является корректируемой (на втором этапе цикла "Запись" ) ошибкой устройства.Коррекцйя одиночной ошибки входа 8 Устройства на втором этапе цикла "Запись" заключается в "об 649615 Онулении" всех (2 п) сформированныхконтрольных разрядов подматриць. Нрпоступающих через коммутатор 6на выход 9 устройства для записив 1-й блок памяти, методом "адаптации": отключением от выхода 9 устройства выходов 14 блока 1 и подключением к выходу 9 устройства выходов18 блока 4 коррекции ошибок.Обнаружение двойных ошибок на вхопу дах 8 -8 ц устройства заключается в1обнаружении двух единичных сигналов,сформированных на контрольных выходах10 или 11 устройства, и запрещениизаписи в память двух неправильно сформированных кодовых слов (подматриц1 Н) за счет преобразования 20-разрядного кода ошибки, поступившего навходы блока 7, в четырехразрядный код"1001" некорректируемой ошибки "Записи" на управляющем выходе 12 устройства, и прерывания работы устройства.Необходимость обнуления в режиме25 "Запись" всех (2 п) контрольных разрядов 1-го блока памяти объясняетсятем, что согласно структуре двумерного кода подматрицы Нпри возникновении одиночной ошибки Б (, 1) на30 входе 8 устройства, на выходе 14 блока 1, реализующего синдромно-мажоритарный алгоритм кодирования, неправильно сформируются значения двухконтропьных разрядов 1 а 1 и 1 Ь и,таким образом, на входах 1-го блокапамяти возникнет трехбитовая ошибка;в разрядах 1 Б (, ), 1 а и 1 Ь 1 сФормированного для записи в память 1-гокодового слова, что является для уст 40 ройства некорректируемой ошибкой (необнаруживаемой в режиме "Чтение" ),так.как двумерный код имеет кодовоерасстояние й = 4, т,е, может обнаружить двойную или пакетную ошибку 1-гоблока памяти, а трехбитовую ошибкуданной конфигурации: в разрядах Б(, 3), а, Ь 3 1-ого блока памяти двумерный код обнаружить не может, Более того, .если в режиме кодированияне произвести "обнуление" контрольных,разрядов, в режиме декодирования устройство воспримет такую трехбитовуюошибку как одиночную корректируемуюошибку 1-го блока памяти (в разряде55 4 ф исправит ее и сформирует на выходе 9 устройства кодовое слово .с четырьмя ошибками в разрядах Б(, 1), а, Ь и я, которое поступит на выходную магистраль данныхтарных элементов 24 (к)1 и 24(лги"а на выходе сумматоров 23 и;к1 и;23 " значение контрольного разряда Рп который поступает на третий вход мажоритарных элементов 24;)и 24(дц) . Соответственно на выходах14 каждого ЛБК 1 Аормируются значения контрольных разрядов а 1, Ь 1 ипо формулам:а 1 = р 1Ьп;Ь 3 = (,1 Оп=Ып п,где О и = 3 п = 1.Из данных Формул видно, что значения контрольных разрядов м ЬЗ я,. сформированные на инАормациоНнык выО ходах 14 каждого блока 1совпадаютсо значениями контрольных разрядовМ 1 /3Мп фп) сформированнымина контрольных выходах 15 и 16:а 1 = 3., Ь 1 = /1 я =Ып =/3 п.к 5 В общем виде работу схемы кодирования устройства (Фиг.4) можно описать по Формулам1 а 1 = НКОо Л 1 Б(11)1 Б(11)+зо . +1 Б(1 М)3;".нпЗп" = (нко ко,) ЧЧ (нко К)Ч.140Ч (нкоко),55 как "безошибочное", что для устройства контроля недопустимо. Поэтомупри возникновении в режиме "Запись"одиночной ошибки на входе 8 устройства (трехбитовой ошибки в 1-кодовом слове) на выходе 9 устройства происходит "обнуление" всех контрольных разрядов 1-го блока памяти,,т.е. избавление от тройной (некорректируемой для устройства) ошибкиавтоматически исправляемой в режиме"Чтение".В устройстве возможность "исправления" одиночных ошибок, внесенныхво входную информацию при записи впамять, обеспечивается за счет полного, распараллеливания схемы кодирования (Формирования и коррекции контрольных разрядов) и схемы обнаружения ошибок (Формирования разрядов синдрома), т.е. за счет одновременного Формирования контрольныхразрядов подматрицы НД: на контрольных выходах 15 и 16 блока 1(для анализа в индикаторе неисправностей 5) и на инАормационных выходах 14 блока 1 (для "обнуления"1 в коммутаторе 6),Возможность Формирования в режиме "Запись" контрольных разрядов ахЪ 1, я модифицированного двумерногокода одновременно на контрольных 15,16 и информационных 14 выходах каждо.го блока 1 - 1 проиллюстрированана фиг,4 и объясняется следующим об-,разом.В режиме "Запись" на п-й входблоков 20 и 21, а также на первыйвход блоков 22, 23 и 24 и на всевходы блоков 20 и 211, поступают"0с входов 8 устройства: й(1) вх,1(в+1 вх, 1 р) вх. Соответственно на"П+31инверсных, выходах блоков 20 п и 21Формируются " 1" (п и фп) на выходах блоков (201-20 ) - значенияК,контрольных разрядов а ( Ж 1- МК)на выходах блоков (21-21)- значения контрольных разрядов Ь,1 ( ф 1-3 К)На выходе сумматоров 22(,1 и 23(км)по модулю два Формируются значенияконтрольных разрядови3которые поступают соответственно навторой вход мажоритарных элементов24(,)и третий вход мажоритарных элементов 24( ). На выходе сумматоров22( ) и 22 (р 1 формируется значеф 11ние контрольного разряда Яп который поступает на второй вход мажори 1 ьз: нко1(1 д)1(ц+ + 1 БЬ.1); 35 к 1 = НКО, Работа блока 1 в режиме Запись" запрограммирована по Аормулам:, "НКО" = ("Нпэп") ("КО")Сигнал "НпЗн" - неисправности 50 устройства в режиме "Запись" - Аормируется на выходе 124, сигнал "КО" - на выходе 12 , а сигнал "НКО" - на выходе 12 , Выход 12(Нп 4 ш) в режиме "Запйсьч не используется, поэтому на нем сохраняется "0".Из этих Аормул видно, чтов режиме"Запись" на контрольных выходах 12 12 12 12. устройства могут появиться только две разрешенные комби 1649615 14нации: ".,0101" - признак корректируемой ошибки устройства или "1001"признак некорректируемой ошибки устройства. Появление на выходах 12 любой другой ненулевой комбинации5свидетельствует о неисправностях всамой схеме обнаружения ошибок: вблоках 20, .21, 5 р или блоке 7.Работу устройства в режиме "Запись" в память удобно рассмотретьдля одного конкретного случая егоприменения, например при реализациив нем (128,64) модиАицированного трехмерного кода, кодовая матрица которого представлена на Фиг.З,В данном случае ня входы 8-8устройства поступают для записи впамять восемь девятиразрядных сообщений, например восемь одинаковыхкомбинаций вида (100 011 011), содержащих нечетное (правильное) количествоединиц", а на девятый вход каждого индикатора неисправностей 5- 5поступает с входа 13 устройства "1" 25настраивающая индикаторы неисправностей на работу в режиме "Запись".Одновременно ня восемь входовкаждого блока свертки по модулюдва 242 8 2 2 2, 2 и 2и на два входа каждого щ-го сумматора по модулю два блоков 4- 4коррекции ошибок (ш = 4, 8, 12, 13,14, 15, 16) поступают "0" (Аиг,4),формируя на выходах 18 каждого блока коррекции ошибок группы 3 "нулевые" значения семи контрольных, разрядов: а 1, а 2, яЗ, Ъ 1, Ь 2, ЪЗ,я,поступающие на вторую группу инАормационных входов каждого коммутатора б -б. 4 д 1 861 1261, 13 Н, 1461,15 с 11 и 1661.(Пример я) О Значения информационных разрядовБО-Б 8 и сАормировянных контрольных разрядов я 1-аЗ, Ь 1-ЬЗ и 8 подмятрицы Нрасполагаются для наглядности на соответствующих им позициях в каждой плоскости кодовой матрицы трехмерного кода, контрольные разряды строк и столбцов отделены. Одновременно на управляющем вы 35 ходе 12 устройства Аормируется кодп 0000, разрешающий запись в память,в результяте чего в каждый блок памяти одновременно записываются девять инАормационных разрядов (100,щ 011 011) и семь контрольных разрядов(011 011 1) в виде 16-рязрядного кодового слова 01-о 16: (1000 0111 01110111), причем значения одноименныхконтрольных разрядов 1 а 1, 1 а 2, 1 аЗ,45 1 Ь 1, 1 Ь 2, 1 ЬЗ, ц (подчеркнуты) записываются соответственно в одноименные разряды блоков памяти согласно кодовой матрице трехмерногокода (128,64). На этом цикл "Запись"заканчивается,Рассмотрим конкретный случай"исправления" одиночных ошибок,внесенных в 72-разрядное входное сообщение в режиме "Запись", методомадаптации (обнуленйя) .В данном случае на инАормационныевходы 8 устройства поступают семь без".ошибочных инАормационных сообщений,например семь одинаковых девятиразНа входы каждого индикатора неисправностей 5-5 8 поступает комбинация (0111 0111), свидетельствующая об отсутствии ошибок в каждом девятиразрядном сообщении с входов 8-8 устройства (100 011 011), содержащем информационные разряды Б 1-Б 8 и один контрольный разряд Со по нечетности, воспринимаемый каждым блоком 1-18 кяк инАормационный символ БО, в результате чего 16-разрядное кодовое слово подматрицы ( НД (Аиг.З), сАормированное соответственно на инАормационном входе 8 и информационном выходе 14 каждого блока 1, содержит четное (правильное) количество единиц." и имеет вид При отсутствии ошибок на входах 8устройства на контрольных выходах10 -108 и 11- 11 устройства формируются "0", поступающие на 16 входовблока 7 и на управляющие входы коммутаторов 6 -68, в результате чегона информационные выходы 9 -9 уст 8ройства, связанные с входами восьмиблоков памяти, поступают 56 контрольных разрядов трехмерного коря(128,64), сформированных ня информационных входах первой группы каждого15164 рядных комбинаций (100 011 011), содержащих нечетное количество ууединиц 1 и одно "четное" девятиразрядное сообщение, например, с искаженньм символом 586 = "1" (подчеркнут): 100 011 111 Согласио кОДОВОй подматРИЦе Н р на контрольных ( 03 и 1) выходах 15 и 16, а также на информационных (1200 и 1360) выходах 14 ЛБК 1,. неправильно сформируются два контрольных разряда пятого блока памяти: 5 аЗ = "0" и 5 Ь 1 = "1" по формулам:5 Ь 1 = 5 Со + 583 + 586 + "1" = 1+0+1+1=,1, На входы каждого индикатора неисправностей 5 - 54, 56 - 58 посту- пает комбинация (0111 0111), свидетельствующая об отсутствии ошибок в каждом девятиразрядном сообщении входов 8 -8 у 8-8устройства (100 011 011), а йа входы индикатора неисправностей 5 поступает комбинация (0101.11 11), свидетельствующая об ошибке входа 8 устройства (100 011 111) в результате чего каждое 16-разрядное кодовое слово подматриц Н-Н, Н-Н 8 будет иметь вид а 16-разрядное кодовое слово подматрипы Ндпу сформированйое соответственнона информационном входе 8и информационном выходе 14- ЛБК .1содержит нечетное количество единиц и будет иметь вид (подчеркнутытри искаженных символа 586, 5 аЗ и5 Ъ 1) На контрольных выходах 10 - 10, 106- 108 и 11- 11, 11". 118 устройства Формируются "0", поступающие на управляющие входы коммутатрров бр-б, 66-68, а на контрольных выходах 10 и 11 у устройства 9615 бформируются две "1", в результатечего на информационные выходы 9 -9 р9" 9 б устройства поступают 49 контрольных разрядов трехмерного кода(128,64), а на информационный выход9 устройства поступает семь "О",Одновременно на управляющем выходе12 устройства (Формируется код"0101 ч корректируемой ошибки "Запи 1 О у 1си , разрешающий запись в память, вщррезультате чего в семь (из восьми)блоков памяти записывается 16-разрядное кодовое слово (1000 01110111 0111), а в пятый блок памяти -16-разрядное кодовое слово с нулевыми контрольными разрядами содержащее соответственно шесть ошибочных символов 586, 5 а 2 5 аЗ, 5 Ь 2 р 5 ЬЗи я (подчеркнуты)1000 01101110 0000) .Йа этом цикл "Запись" заканчивается.Надо отметить, что в данных примерах для простоты описания работыустройства был рассмотрен случай записи в память М одинаковых иразрядных кодовых слов,При этом согласно модифицированной структуре поднатрнн нр трех-.мерного кода с контролем по нечетности строк и столбцов в каждой пло-.скости кодовой матрицы (Фиг.З), каждая п-разрядная строка и каящьй иразрядный столбец двумерного кода(где п - четное число, например четыре) содержит минимум одну "единицу" (например, 0001) и минимумодин, ".нуль" (например, 1110). Поэтому каждое и -разрядное слово вумерного модифицированного кода и(и) , Формируемое.в режиме "Запись" для 1-го блока памяти, должносодержать минимум 2 к "единиц" или2 И "нулей" (где К = и). Поэтомув каждый из 0 блоков памяти не может быть записана и, следовательнв режиме "Чтение" не может быть стана комбинация, соостоящая из и2"нулей" или пф. "единиц", так какпри этом каждая и-разрядная строкаи каждый и-разрядный столбец подмарицы Н трехмерного кода будет содержать четное (неправильное) числоединиц, например ОООО или 1111, чтообязательно обнаружится устройствомв режиме "Чтение" (индикатором не"Таким образом, модифицированнаяструктура примененного в устройствекода позволяет обнаружить (и исправить) пакет однонаправленных ошибоктипа "и нулей или "и единиц", воэ1 Йникающий при отказах любого из Иблоков памяти, а также обнаружить(и исправить) в режиме "Чтение" ошибки, внесенные в кодовое слово при записи в память, которые предварительно были исправлены в режиме "Запись"методом "обнуления": внесением в .1-йблок памяти многобитовой (обнаруживаемой) ошибки вместо трехбитовой (необнаруживаемой) ошибки.В режиме "Чтение" в устройствереализуется синдромно-мажоритарныйалгоритм декодирования с адаптацией,что позволяет устройству исправлятьН одиночных ошибок (при независимомих возникновении в каждом иэ М блоков памяти), а также (2-и )-битовыеошибки одного из И блоков памяти.Декодирование информации в режиме "Чтение" происходит в два этапа.На первом этапе на управляющийвход 13 устройства поступает "0",перестраивающий индикаторы неисправностей на работу в режиме "Чтение" ,и разрешающий считывание (11-и)-разрядной информации.из И блоков памятина входы 81-8 1 устройства, На первомэтапе декодирования трехмерногокода используются блоки 1, 2, 4 и5, В блоках 11 -1происходит исправление одиночной (корректируемой)ошибки каждого,из блоков памяти и Формирование (на выходах 14) первойгруппы скорректированных значений1 ДО)1 ДО входа 8 устройства, а в индикаторах неисправностей 51-5 1(происходит обнаружение двойной и пакетной ошибки (некорректируемой) ошибки каждого из Ю блоков памяти и Формирование (на выходах 15 и 16) признаков некорректируемой НК 01-НК 01 и корректируемой К 01-К 011 ошибки блоков памяти, Одновременно в блоках сверткипо модулю два 2, 2 2 й проверкойна четность каждого ребра кодовойматрицы (фиг.3) Формируется (на выходах 17) третья группа разрядов синдрома )1, ш, )и , а в блоках2коррекции ошибок 4 -4 Формируется Г55 (на выходах 18) вторая группа скорректированных значений 1 Д 1-БД 1 входа 8 устройства а 17 (вх) +1, ан (вх)++ Р, аиТ (вх) + У На этом первый этап декодирования заканчивается.На втором этапе используются блоки 6 и 7. В блоке 7 происходит анализ 2 И-разрядного кода ошибки, сформированного на контрольных выходах 10 и 11 устройства, и Формирование на выходах 1 2 1 2 устройства четырехразрядного кода "0110" или "1010" - признаков корректируемой или некорректируемой ошибки устройства в режиме "Чтеиние , а в коммутаторах-корректорах 6-6 происходит "исправление" одиночной некорректируемой ошибки каждого из И блоков памяти (методом адаптации) и Формирование на выходах 9 в -9устройства третьей группы окончательно скорректированных значений 1 Д (вых) - ЫД (вых) по формулам:Д(вых) = (йКО Л 1 ДО) ЧУ(НКО А 1 Д 1)В конце. цикла Чтение" (после формирования на выходе 12 устройства кода "0000" - признака отсутствия ошибок или "0110" - признака корректируемой ошибки устройства в режиме "Чтение" ) скорректированная (Би ) - разрядная информация считывается с выходов 9 устройства на выходную магистраль данных.На этом цикл иЧтениеи заканчивается.На первом этапе декодирования в каждом блоке 1 реализуется синдром- но-мажоритарный алгоритм декодирования (фиг,2), который заключается в следующем. При отсутствии ошибок в2и разрядах информации, считанной из 1-го блока памяти, информация проходит с входа 8 устройства: 1 Д (вх) на выход 14 блока 1: 1 ДО без изменения, так как на выходах генератора 19 Р кода ошибок Формируется нулевой синдром поэтому значения йп (вх) +Шв дв(вх) + )(3 хавхо-,. го сигнала входа 8, сформированные в блоках 22 и 23 блока 1, совпадают на входе каждого мажоритарного элемента 24 с первыми, считанными из памяти значениями аш (вх) информационного входа 8, На выходах индикаторов неисправностей 5 -5 1 сохраняются "0".Если в каждом иэ И блоков памяти возникают только одиночные ошибки (возникновение 1-Н одиночных ошибок