Устройство для коррекции ошибок в блоках памяти Советский патент 1984 года по МПК G11C29/00 

Изобретение относится к цифровой вычиоштельной технике и технике передачи информации и может быть использовано в адаптерах внешней и оперативной памяти ЭШ, а также в аппаратуре передачи дискретной информации по канапш связи.

Известно устройство для коррекции ошибок с самоконтролем,содержав|ее селектор кода Хаг-шинга, селектор информации,генератор паритета, генератор синдромов, регистр онкцромод, элемент сравнения синдаомов, дешифратор ошибок, корректор информации, блок обнаружения ошибок,сумматоры по модулю два, эле «енты ИЛИ tj

Недостатками этого устройства являются низкая достоверность контроля информации и малая исправляпцая способность.

Наиболее близким к изобретению является устройство дпя приема дискретной информации с исправлением овибок,содержащее последовательно соединенш 1е фс в1рователь входного сигнала, блок деления полиномов, к другому входу которого подключен датчик квазислучайной последовательноети,регистр дшкодируемЫ) комбинации, основной коммутатор, первый сумматор,блок анапиза, ключ, к другсжу входу которого подключен выход основного коммутаторд, накопитель лрка)тзованных символов и выходн(

накопитель,причем к выходу накопителя локализованных символов подключены после; вательно соедагненные блок выбора си(«волов, блок выбора лроверочных соотношений и блок памяти,к другому которого подключен GnoK управления, управляемой от блока выбора символов, выходы блока памяти подключены соответственно к основному и дополнительному коммутаторам, вход последнего подключен к выходу накопителя локализованных символов, а выход череэ второй сумматор - к выходному накогштелю 21.

Однако данное устройство обеспечявает недостаточно высокую достоверность информации.

Целью изобретения я &ляется noniiшение надежности устройства за счет повышения достоверности исправления сшибок.

Поставленная цепь достигается тем, что в устройство для коррекции ошибок в блоках памяти,содержащее последовательно соединенные стохастический преобразователь кодов, первый регистр числа, селектор,сумматор, дешифратор нулевого числа, первый ключ, первый и второй накопители информации,блок исправления ошибок, выход которого подключен к одному из входов второго накопителя информации, первый вход соединен с ОД1ШМ из выходов первого накопителя

информации,второй вход - с первым выходом третьего накопителя информации и одним из входов селектора,выход которого соеданен с одним из входов первого ключа, датчик квазис5 лучайных чисел, олход которого под ключён к одному из входов стохастического преобразователя кодов,введешл второй регистр числа,второй ключ и блок оценки достоверности,

0 выход которого подключен к третье-.

му входу блока исправления ошибок, четвертый вход которого сЬединен с вторым выходом третьего накопителя информации, первый вход блока

5 сщенки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход - с другяы входом первого ключа,вход нто0 рого регистра числа подключеи к первому выходу третьего накопителя информации .

Блок оценки достоверности содержит третий и четвертый регистры чи ела, первый и второй счетчики,группу счетчиков,пороговый элемент,блок сравнения, четвертый накопитель информации и элементы ИЛИ, входы которых подключены к одним из выходов третьего и четвертого регистров числа, а выходы - к входам третьего регистра числа, выход которого соединен с входом второго счетчика,входа счетчиков груп1ы соединены с други- мя выходами четвертого регистра числа, а выходы подключены к входам порогового элегюнта, входы блока сравнения Подключены к выходам счетчи,ков, порогового элемента и четвертого накопителя информа1ши,один из выходов блока сравнения соединен с входом четвертого накопителя информации, а другой выход и выход порогового элемента являются выходами блока, входами которого являются управлякжций вход четвертого регистра числа и вход первого счетчика.

На 4иг. изображена структурная схема предложенного устройства; на структурная схема блика оценки достоверности. Устройство (г.1 содержит стохастический преобразова тель I кодов первый регистр 2 числа, первый ключ 3, первый накопитель 4 информации, накопитель 5 информации, датчик б квази случайных чисел селектор 7,сумматор 8,дешифратор 9 нулевого числа, второй регистр 10 числа, второй ключ II, блок 12 оценки достоверности, третий накопитель 13 информации ,блок 14 исп равления ошибок. Блок Г2 оценки достоверности содег жит (({иг. 2) четвертый накопитель 15 информации,первый счетчик 1 блок 17 срайиени, третий регистр 18 числа, вторс 19,элементы НИИ 20, четвертый регистр 21 числа, группу счетчиков 22, пороговый элемент 23. Работа предлагаемого устройства основана на применении стохастических помехоустойчивых кодов,исправляиЖих ошибю. Элементом (или q-ичным а{мволом) кода является отрезок двоичной последовательности длиной (q 2). Для К информационных символов по закону двоичного (п,К)-кода формируется n-k избыточных символов. Например, для (15,1 D-KOfla Хэ1«шнга q-ичные и быточные символы, обозначенные ниж 1,2,3,4, получаются путем cyм вIpoвal&IЯ по модулю два информа- ционных символов, обозначенных буквамн А-Л. . Г-Ач-Б + Г + Д-ьЖ + и + Л 2- А + В 4- Г + Е + Ж + К + Л 3- Б + В + Г 3 + И + К + Л 4- Д + Е + Ж + 3 + И + К.+ Л Затем каяздый из q-ичных символов подвергается стохастическому (квази случайному) преобразованию под воз дейсттем квази случайной кодируищей последовательности. На этом процесс кодирования заканчивается. и обратное стохастическое преобразование - это известные опер ции, реализуемые как умножение и деление полиномов по модулю неприво димого полинома или выполняемые таб лично З и 4.. При декодировании вначале вЫпоАняется обратное стохастическое пре образование каждого q-ичного символа под воздействием той же квазисл (1 604 чайной последовательности,что и при кодировании. В результате,если q-ич ный символ не был искажен до декодирования, то имеет место исходное значение этого символа. Если же этот символ искажен любой помехой в промежуткемежду кодированием и декодированием-,то после обратного стохастического преобразования происходит преобразование вектора ошибки или перемевшвание искажений такого рода что любое из 2 BO3i « v 9 ix значений этого символа fкроме исходного неискаженного) появляется с равной вероятностью. После обратного стохастического преобразования производится выделение (локализация) прагашьно тфинятых q-1Iчныx символов путем проверки I проверочных соотношений, являюагихся линейныт комбинациями соотноше1|Нй, используем 1х при кодировании. Для проверки некоторого соотношения суммируют по модулю два все входяпрсе в эти соотношения q-ичные символы и проверяют резуль- . тат суммирования На нуль (I). Комбинация из нулей после сумш1рования будет в том случае,если все сиг волы не были искажены,или если искажение этих символов совпадает (при двух искаженных символах). Ирн указанных свойствах стохастического преобразования, переме1шваю1цего искажения,достигается условие,что вероятность оонбочной локализации не превышаетвеличины OU После проверки всех соотношений екоторые q-ичные символы оказываются локализованныки, а остальные исправляются как стирания, т.е. путем выражения нелокализованных символов через значения локализованных. При этом выбирается со этношение,куда входит один исправляекий символ и локализованные символы,тогда значение исправляемого символа равно сумме по модулю два известных сим- волов. Описаиные операции выполняются как в прототипе, так и в предложенном устройстве, однако этнх операций недостаточно, так как путем анализа результатов декодирования (локализации) можно повысить помехоустойчивость декодирования. Введем понятие ошибочной локапи зации, когда при искаженных q-ичны символах QJ и Qj проверочное соотношение , в которое входят они вместе, выполняется. Но те соотношения, куда эти символы входят по отдельности, не будут вьтолняться. Тогда,сравнив число формально локал зованных символов, в которыеВХОДЯТ на; и Glj, с числом ВЫПОПНЯЮ1Ф1ХСЯ соотношении, можно выявить случай о бочной локализации. Если дополнительно сосчитать число соотношений, которые вошел каждый из п q-ичных символов, то можно выявить q-ичные символы,локализование ошибочно. Путем стирания этих символов с последующим их исправлением можйо поклеить помехоустойчивость хранения информации. Для каждого конкретного кода можно построить таблицу соответстш1 числа локализованных символов N и числа выполнившихся соотноше1шй N при правильной локализации.Если эти величины друг другу не соответствуют в конкретном случаеj по проверяется число выполняющихся соотношеНИИ, в которые вошел кажлМй символ М,- . Если величина Н( меньше заданн го порогового значения, то символ с номером i стирается Ши выдается потребителю с указанием на пониженную его достоверность. Т1утем анализ а величин N, Ng и М можно выделить несколько градаци достоверности,достигаемой при декодировании:при Н( достигается высша или абсолютная достоверность,так как есть гарантия, что информация в финципе не содержит ошибок; в зависимости от используемого кода достигаются i-грададии достоверности, при каждой из которых вероятность ошибки не превышает величины g в этом случае после декодировани вместе с информаздией выдается признак степени достоверности выдаваемо информации. Устройство с учетом изложенного работает следукщим образом. Считаем,что информация записана в запоминающее устройство (ЗУ) ЭВМ использованием конкретного (n-k)-KO да,проверочные соотношения для которого записаны- в накопитель ,а таблица соответствия величин N. и N. записана в накопитель 15.Ц)и этом каждалй q-ичный символ записывается на одну дорожку носителя,чтобы сбой илн неисправность канала записи-считывания искажали од11Н q-ичный символ кода. Под воздействием квазислучайной последовательности считанная информа1и1Я подвергается преобразованию в преобразователе 1 и записывается в регистр 2. Из накопителя 13 по очереди считываются соотношения используемото ()-кода, которые поступают в селектор 7 и регистр 10. Указанные позиционньш образом-в проверочном соотношении q-}i4Hbie символы поступают через селектор 7 из регистра 2 в сумматор 8, Полученная сумма q-ичных символов проверяется на нуль в дешифраторе 9. Если имеется нулевая сумма, что через ключ 3 данные сз1мводш переписываются в накопитель 4, а сама комбинация проверочного соотношения через ключ 11 записывается в регистр 21. Одновременно в счетчике 16 Добавляется 1 к числу наполнившихся соотношений. Проверочное соотношение имеет вид двоичной комбинации длиной п, где п - длина кода, в котором единицы стоят в тех позициях,которым соответствуют q-ичшле симBojat,входящие в данное соотношение .Например, для первого соотношения, записанного в выражении (1), проверочное соотношение, обрабатываемое в данном устройстве,имеет следукнций вид: Позиция кодового1234АБ1ВГДЕЖЗИКЛ слова. Ввд провероГ1000110110Г010Г но го соотношенияЗна1чит,если данное соотношение выполнилось,то символы ,А,Б,Г,Д,Ж, И и Л локализуются и переписываются в накопитель 4, а комбинация 100011011010101 поступает из регистра 10 через ключ 11 в регистр 21, откуда переписывается через элементы ИДИ 20 в регистр 18, в котором накапливаются номера позиций локализованных символов,для чего логически суммируются комбинации выполнивошхся проверочных соотношений. Одновременно единицы выполнившихся проверочных соотношений из регистра 21 параллельно поступают на п счетчиков 22, где подсчитывается для кфкдого q-ичного символа число выполнившихся соотношений, в которых присутствовал этот символ. в результате после проверки всех 2 соотношений дня кода (15,1) (число этих соотношений равно 2 - ) в peiHCTpe 18 записаны 1 в тех позициях, которым соответствуют локализованные в одном или в нескольких соотношениях q-ичные -символы,а в счетчиках 22 - число этих соотношений для каждого символа. После этого производится подсчет числа локализованны символов в счётчике 19, на вход которого сдвигается комбинация из регистра 23. В блоке 17 проверяется соответствие величин Нд и NJJ, полученных в счетчиках 16 и 19 соответственно в сравнении с таблицей соответствия, считываемой из Накопителя 15. Пороговый эле14ент 23 вырабатывает сигнал стирания тех q-ичных символов, которые приняты ненадежно,т.е число выполнившихся соотношений для которых ниже заданного порога. 60.8 Сигнал стирания представляет собой позиционную запись номеров ненадежно принятых (стертых) q-ичных символов .Блок 17 сравнения может быть выполнен в соответствии с з . Номера позиций нелокализованных и стертых q-ичных символов поступаитг в блок 21 исправления ошибок,куда, поступают также значения локализованшх сиг-гаолов из накопителя 4. В блоке 14 ПРОИЗВОДИТСЯ исправление ошибок.Исправление каждого из подлежащих исправлению q-ичных символов состоит в выборе щ оверочного соотношения , в которое ВХОДИТ неправляе14 1й символ и ранее локалнзированные символы. Тогда значение исправля емого символа равно сумме по модулю два этих локализованных символов, Значения исправленных символов записываются в накопитель 5. Технико-эконо1«1ческий эффект предлагаемого устройства состоит в повышешш достоверности хранения инфор-, мации за счет операций оценки достоверности, стирания и исправления недостоверных q-ичных символов, а также в повышении помехоустой квости и надежности хранения инфорг ации за счет испразаления сбоев и выделения части неискаженных симво-. лов..

аг.2

1. УСТРрЙС1ВО ДНЯ КОРРЕКЦИИ ОШИБОК В БЛОКАХ ПАМЯТИ,содержащее последовательно соединенные стохастический преобразователь кодов,первый регистр числа, селектор,cyMMiaтор,дешифратор нулевого числа,первый ключ, первый и второй накопители информации, блок исправления ошкбок, выход которого подключен к одному из входов второго накопителя информации, первый вход соединен с одним из выходов первого накопителя информации, второй вход - с периом выходом третьего накопителя информации и одним из входов селектора, выход которого соединен с одним из входов первого ключа, датчик квазислучайных чисел,выход которого подключен к одному из входов стохастического преобразователя кодов, отличающееся тем,что, с целью повышения надежности устройства за счет повышения достоверности исправления ошибок, в него введены второй регистр числа, второй ключ и блок оценки достоверности,выход которого подключен к третьему входу блока исправления сжпбок, четвертый вход которого соединен с вторым выходом третьего накопителя информации,первый вход блока е хенки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход с другим входом первого ключа,вход второго регистра числа подключен к первому выходу третьего накопителя информации. 2. Устройство по п. 1, о т л и ,ч а ю щ е е с я тем,что блок оценкн , i (Л достоверности содержит третий ичетвертый регистры числа, первый и второй счетчики, группу счетчиков, пороговый элемент, блок сравнеиия, четвертый накопитель информации и элементы ИЛИ, входы которых подклю чеп г к одним из выходов третьего и четвертого регистров числа, а выходы - к входам третьего регистра чиэо сла, выход которого соединен с вхоЭ) дом второго счетчика, входы счетчиiu ков группы соединены с другнм) выходами четвертого регистра числа, а выходы подключены к входам порогового элемента, входы блока сравнения подключены к выходам счетчиков,порогового элемента и черветого накопителя информации,один из выходов блока сравнения соединен с входом четвертого накопителя информации, а другой выход и выход порогового элемента являются выходами блока, входамн которого являются управляющий вход четвертого регистрачисла и вход первого счетчика.