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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТ ИЧЕСНИХРЕСПУБЛИК 9) (И) 11 С 29 00 ННЫЙ НОйИТЕТ СССРЖКПЛЕТЕНИЙ И ОТНРЫТИЙ ГОС ИСАНИЕ ИЗОБРЕТЕНИЯ У( 1. Авторское свидетельство СССРВ 796847, кл. С 06 Р 11/10, 1977.2. Авторское свидетельство СССРпо заявке В 2943474/18-24,кл. Н 04 Ь 1/10, 1980 (прототип).3, Авторское свидетельство СССРВ 559417, кл.Н 04 Ь 1/1 О, 1972.4, Авторское свидетельство СССРФ 849515, кл. Н 04 Ь 1/О, 1979.5. Авторское свидетельство СССРУ 745009, кл. Н 04 Ь 1/10, 1976.(54) (57) 1УСТРОЙСТВО ДПЯ КОРРЕКЦИИОПВБОК В БЛОКАХ ПАМЯТИ, содержащеепоследовательно соединенные стохастический преобразователь кодов,пер-,вый регистр числа, селектор, сумма-.тор,дешифратор нулевого числа,первый ключ, первый и второй накопители информации, блок исправления оши"бок, выход которого годключен к од- .ному иэ входов второго накопителяинформации, первый вход соединенс одним иэ выходов первого накопителя информации, второй вход - с первым выходом третьего накопителя информации и одним из входов селектора, выход которого соединен с од-ним из входов первого ключа, датчик квазислучайных чисел, выход кото-.рого подключен к одному из входовстохастического преобразователя кодов, о т л и ч а ю щ е е с ятем,что, с целью повышения надежности устройства за счет повышения, достоверности исправления ошибок, внего введены второй регистр числа, второй ключ и блок оценки достоверности,выход которого подключен к третьему входу блока исправления ошибок, четвертый вход которого соединен с вторым выходом третъега накопителя информации,пернай вход блока оценки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход -Ю с другни входои первого ключа, вход второго регистра числа подключен кервоиу выходу третьего накопителя информации.2. Устройство по и, 1, о т л и -ч а ю щ е е с я тем,что блок оценки достоверности содержит третий и чет- вертый регистры числа, первый и второй счетчики, группу счетчиков, пороговый элемент, блок сравнения, четвертый накопитель информации и элементы ИЛИ, входы которых подклю.чещю к одним иэ выходов третьего и четвертого регистров числа, а выходы - к входам третьего регистра числа, выход которого соединен с входом второго счетчика, входы счетчиков группы соединены с други)в выходами четвертого регистра числа, а выходы подключены к входам порогового элемента, входы блока сравнения подключены к выходам счетчиков,порогового элемента и черветого накопителя информации, один иэ выходов блока сравнения соединен с входом четвертого накопителя информации, а другой выход и выход порогового элемента являются выходами блока, входами которого являются управляющий вход четвертого регистра числа и вход первого счетчика.Изобретение относится к цифровойвычислительной технике и технике передачи информации и может быть использовано в адаптерах внешней иоперативной памяти ЭВИ, а также ваппаратуре передачи дискретной информации по каналам связи.Известно устройство дпя коррекции ошибок с самоконтролем,сбдержащее. селектор кода Хэмминга, селектор информации, генератор паритета,генератор синдромов, регистр синдромов, элемент сравнения синдромов,дешифратор ошибок, корректор ив 4 юрмации,блок обнаружения ошибок, сумматоры по модулю два, элементы ИЛИ ЦНедостатками этого устройства являются низкая достоверность контроля информации н малая исправляющаяспособность,Наиболее близким к изобретению яв-ляется устройство дпя приема дискретной ин 4 юрмации с исправлением ошибок,содержацее последовательно соединенные формирователь входного сигнапа., блок деления полиномов, к другому вжщу которого подключен датчик квазислучайной последовательнос-.ти,регистр дикодируемой комбинации,основной коммутатор, первый сумматор,блок аиапиэа, ключ, к другому. входу которого подключен выход основного коммутатора, накопитель локализованных символов и выходнойнакопитель,причем к выходу накопителя локализованных символов подклю"чаны последовательно соединенные блоквыбора символов, блок выбора прове- ,рочных соотношений н блок памяти,кдругому входу которого подключенблок управления, управляемай от блока выбора символов,нюходы бпокапамяти подключены соответственно косновному и дополнительному коммутаторам, вход последнего подключен квыходу накопителя локапизованныхсимволов, а выход через второй сумматор - к обиходному накопителю 2,Однако данное устройство обеспечевает недостаточно высокую достоверность информации.Целью изобретения яйляется повышение надежности устройства за счетповышения достоверности исправленияошибок.Поставленная цель достигаетсятем 1 что в устройство для коррекции вшибок в блоках памяти, содержащее последовательно соединенные сто ю15. лучайных чисел, выход которого под -55 5 1 О хастический преобразователь кодов,первый регистр числа, селектор, сумматор,дешифратор нулевого числа, первый ключ, первый и второй накопители информацчи,блок исправленияошибок, выход которого подкпючен кодному из входов второго накопителяинформации, первый вход соединен содним иэ выходов первого накопителяин 4 юрмации,второй вход - с первым выходом третьего накопителя ин 4 юрмации и одним из входов селектора,выход которого соединен с одним извходов первого ключа, датчик квазискпючен к одному из входов стохастического преобразователя кодов,введегвю второй регистр числа, второй ключ и блок оценки достоверности,выход которого подключен к третье. му входу блока исправления ошибок, четвертый вход которого соединен с вторым выходом третьего накопителя информации, первый вход блока оценки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход - с другим входом первого ключа, вход второго регистра числа подключен к первому выходу третьего накопителя инФормацииБлок оценки достоверности содержит третий и четвертый регистры числа, первый и второй счетчики, группусчетчиков, пороговый элемент, блоксравнения, четвертый накопитель ин 4 юрмации и элементы ИЛИ, входы которых подключены к одним иэ выходовтретьего и четвертого регистров числа, а выходы - к входам третьего регистре числа, выход которого соединен с входом второго счетчика, входы счетчиков групва соединены с други-ф ми выходами четвертого регистра числа, а выходы подключены к входам порогового элемента, входы блока сравнения подключены к выходам счетчиков, порогового элемента и четвертого накопителя информации, один нз выходов блока сравнения соединен с входом четвертого накопителя ин 4 юрмации а другой выход и выход порогового элемента являются выходами блока, входами которого являются управляющий вход четвертого регистра числа и вход первого счетчика.На 4 иг. изображена структурная схема предложенного устройства; ва1086 1 О 20 3фнг,2 - структурная схема блокаоцейки достоверности.Устройство (4 иг.1) содержит стохастический преобразователь 1 кодов,первый регистр 2 числа, первый ключ3, первый накопитель 4 информации,второй накопитель 5 информации,датчик 6 квазислучайных чисел,;,селектор 7,сумматор 8,дешифратор 9нулевого числа, второй регистр Очисла, второй ключ 11, блок 12оценки достоверности, третий накопитель 13 информации ,блок 14 исправления ошибок.Влок 2 оценки достоверности содержит (4 иг.21 четвертый накопи-.тель 15 информации,первый счетчик 6,блок 17 сравнения, третий регистр18 числа, второй счетчик 19,элементы ИПИ 20, четвертый регистр 21числа, группу счетчиков 2, пороговый элемент 23.Работа предлагаемого устройстваоснована на применении стохастических помехоустойчивых ходов,исправ" 25лялях ошибки. Элементом (илии-ичнци символом) кода являетсяотрезок двоична последовательностидлиной Я (с2 ). Для К информационных фичных символов по законудвоичного (п,1 с)-кода форвируетсяп"с избыточкцх символов. Например,для (15,11)-хода Хэичинга 1-ичные из-.быточные символы, обозначеннЫе нижецифрамн 1,2,3,4, получаются путем35сущщровакня по модулю два информа .циоинцх символов, обозначенных бук-.вами А-Л.1 А+ Б+ Г+Д+Ж+И+Д2 фА+ В+.Г+Е+Ж+ К+Д (1) 403 Б+ В+ Г+ 3+И+.К+В4Д+ Е + Ж+ 3 + И+ К+ ЛЗатем каждый иэ цичных символовподвергается стохастичесхому (квазислучайкому) преобразованию код воэдействиеи кваэислучайной кодирующейпоследовательности, На .этом процесскодирования заканчивается.Прямое и обраткое стохастическоепреобразование - этоизвестные опера ции, реализуемюе как умножение иделение полиномов по модулю иепрнводкмого полинома или выполняемые таб-лично 3 и 4,.При декодировании вначале вылняется обратное стохастическое пре-образование каждого ц-ичного символа под воздействием той же кваэислу 460 4 чайной последовательности,что и при кодировании, В результате, если ц-ич кый символ ке был искажей до декодирования, то имеет место исходное значение этого символа. Если же этот символ искажен любой помехой в проиежуткемежду кодированием и декодированием;то после обратного стохастического преобразования происходит преобразование вектора ошибки или "неремещнвание" искажений такого рода что любое из,2-1 возможных значений этого символа ( кроме исходного неискаженного появляется с равной вероятностью.После обратного стохастического преобразования производится выделе" ние (локализация) правильно принятых и-ичных символов путем проверки 2" - 1 проверочных соотношений,являацихсялинейныж коьйинацняьк соотношений, используемас при кодировании. Для проверки некоторого соотношения суювруют по модулю два все входящие в эти соотношения и-ичные символы и проверяют результат суммирования на нуль , Комбинация из Й нулей после суммирования будет в том случае,если все символы ке были искажены,или если искажение этих символов совпадает (при двух искаженных символах), Прн указанных свойствах стохастического преобразования, "перемешивакщего" искажения,достигается условие, что вероятность ошибочной локализации не превышает величиныОЬ 3-3После проверки всех соотношений некоторые ц-ичные символы оказываются локалиэованныж, а остальные исправляются как "стирания", т.е. путем выражения нелокализованных символовчерез значения локализованных. Приэтом выбирается соотношение, кудавходит один исправляемый символ к локализованные символы, тогда значение исправляемого символа равносумме по модулю два известных символов. Описанные операции выполняются как в прототипе, так и в предложенном устройстве, однако этих операций недостаточно, так как путем анализа результатов декоДирования (локализации) можно повысить помехоустойчивость декодирования.торого записаны в накопитель З,а таблица соответствия величин И и Б 4 записана в накопитель 5. При этом каждый и-ичный символ записывается на одну дорожку носителя,чтобы сбой или неисправность канала записи-считывания искажали один и-ичный символ кода. кПод воздействием квази случайной последовательности считанная информация поднергается преобразованию в преобразователеи записывается в регистр 2. Из накопителя 13 по очереди считываются соотношения используемого (п,Е) -кода, которые поступают в селектор 7 и регистр 10. Указанные позиционным образом в проверочном соотношении ц "ичные символы поступают через селектор 7 иэ регистра 2 в сумматор 8. Полученная сумма и-ичных символов проверяется на нуль в дешифраторе 9. Если имеется нулевая сумма, что через ключ 3 данные. символы переписываются в накопитель 4, а сама комбинация проверочного соотношения через ключ 11 записывается в регистр 21. Одновременно в счетчике 16 Добавляется "1" к числу ныполнившихся соотношений.Проверочное соотношение имеет нид двоичной комбинации длиной и, где и - длина кода, в котором единицы стоят в тех позициях, которым соответствуют ц-ичные символы, входящие в данное соотношение .Например, дпя первого соотношения, записанного в ныражении (1), проверочное соотношение, обрабатываемое в данном устройстве.,имеет следующий вид: Позициякодового1234 АБВГДЕЖЗИКЛ словаВид про- верочного 10001101101010соотнощенияГЗначит,если данное соотношение выполиилось,то символы 1,А,Б, Г,Д,Ж, И и Л локализуются н переписываются в накопитель 4, а комбинация 10001011010101 поступает из регистра 10 через ключ 1 в регистр 21, откуда переписывается через элементы ИЛИ 20 в регистр 8, в котором накапливаются номера позиций локализованных символов,для чего логически суммируются комби 5 10864 б 0Введем понятие "ошибочной локализации", когда при искаженных г 1-ичныхсимволах Ци й проверочное соотношение, в которое входят онивместе, ныполняется. Но те соотнощения, куда эти символы входят поотдельности, не будут выполняться.Тогда, сравнив число формально локализованных символов, в которыевходят.и О; н О", с числом ныполняющихсясоотношений, можно выявить случай ошибочной локализации, Если дополнительно сосчитать число соотношений,вкоторые вошел каждЫй из п ц-ичныхсимволов, то можно выявить 1-очные 5символы,локализованные ошибочно,Путем стирания этих символов с поспедующим их исправлением можгго повысить помехоустойчивость храненияинформации. 20Дпя каждого конкретного кодаможно построить таблицу соответствиячисла локализованных символов Я ичиспа выполниншихся соотношений Нпри правильной локализации, Если эти 25величины друг другу не соответствуют в конкретном случае, по проверяется число вынолнякщнхся соотноше- .ний, в которые вошел каждый символИ . Если величина Именьше заданно- зого порогового значения, то символс номером х стирается.йлн ныдаетсяпотребителю с указанием на пониженную его .достоверность.Путем анапнэа величин Я,1, й и. И можно выделить несколько градаций(достоверности, достигаемой при декодировании:при 8 2 - достигается нысщаяСили пабсолютная достоверность,так 4 Окак есть гарантия, что информацияф, в принципе не содержит ошибок",в эависиг 4 ости от используемогокода достигаются ь-градации достовериостиу при каждой иэ которых 45вероятность ошибки ие пренавает величины ;ЕЮВ этогг спучае после декодированиявместе с информацией выдается признак степени достоверности выдаваемойинформации,Устройство с учетом изложенногоработает следующим образом.Считаем,что информация записана 55в запоминающее устройство (ЗУ) ЭВИ сиспользованием конкретного (и-с)-ко"да,проверочные соотношения дпя ко1086460 8Сигнал стирания представляет собой позиционную запись номеров ненадежно принятых (стертых) г 1-ичных символов .Блок 17 сравнения может5 быть выполнен В соответствии с ЯНомера позиций нелокализованныхи стертых и-ичных символов поступают в блок 21 исправления ошибок, куда поступают также значения локалнзо 0 вангшгх символов иэ накопителя 4. Вблоке 4 производится исправлениеошибок.йсправленйе каждого иэ подлежащих исправлению г 1-ичных символов состоит в выборе проверочного соотношения , в котоРое входит исправ-" ляемай символ и ранее локалиэированные символы. Тогда значение исправля.емого символа равно сугее. по гюдулю два этих локализованных символов Значения исправленных и"мчных символов записываются в накопитель 5. нации выполнившихся проверочных"соотношений. Одновременно "единицы" выполнившихся проверочных соотношений из регистра 21 параллельно поступают на п счетчиков 22, где подсчитывается для каждого ц-ичного символа число выполнившихся соотно шений, в которых присутствовал этот символ.В результате после проверкивсвсех 2 -1 соотношений для ко-да (15, ) (число этих соотношений равно 2 ф - 1 15) в регистре 18 записаны "1" в тех позициях, которым соответствуют локализованные в одном или в нескольких соотношениях ц-ичные:символы,а в счетчиках 22 - число этих соотношений дпя каждого символа. После этого производится подсчет числа локализованных символов в счетчике 19, на вход которого сдвигается комбинация нз регистра 23..В блоке 17 проверяется соответ.ствие величин Н, и Яс, полученных в счетчиках 16 и 19 соответственно, в еравнении с таблицей соответствия, считываемой из накопителя 15. Пороговый элемент 23 вырабатывает сигнал стирания тех и-ичных символов, которые приняты ненадежно,т.е. число выполнившихся соотношений дпя которых ниже заданного порога. Технико-экономщеский эффект предлагаемого устройства состоит в повы 25 веник достоверности хранения инфор-,мации за счет операций оценки достоверности, стирания и исправлениянедостоверных ц-ичных символов, а также в поигшенни помехоустойчивостиЗа и надежности хранения информацииза счет исправления сбоев и выделения части неискаженных и-ичюх симво-.1086460 Составитель В.РудаковРедактор И.Петрова Техред Л.Иикеш Корректор А.Зимоко нт", г. Уагород, ул. Проектная, 4 ППП и фил Заказ 2257/47 Ти ВНИИПИ Государственно по делам изобретений 113035, Москва, 3-35, аа 575о комети открРаущская ПодписноСССРб., д. 4/5