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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТ ИЧЕСНИХ

РЕСПУБЛИК

ИУ (И) Зсю С 11 С2900

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И ASTOPGHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПЮ ДЕЛАМ ИЖК ПЛЕТЕНИЙ И ОТНРЫТИИ (21) 3471247/18-24 (22) 16. 07. 82 . (46} 15.04.84. Бюл. Р 14 (72} С. А.Осмоловский (53) 681.327(008.8) (56) 1. Авторское свидетельство СССР

В 796847, кл. С 06 F 11/10, 1977.

2. Авторское свидетельство СССР по заявке Р 2943474/18-24, кл. Н 04 Т. I/10, 1980 (прототип).

3. Авторское свидетельство СССР

В 559417, кл.Н 04 L 1/10, 1972.

4. Авторское свидетельство СССР

Ф 849515, кл. Н 04 L 1/10, 1979.

5. Авторское свидетельство СССР

У 745009, кл. Н 04 L 1/10, 1976. (543 (57) 1 ° УСТРОЙСТВО ДПЯ КОРРЕКЦИИ

ОПМБОК В БЛОКАХ ПАМЯТИ, содержащее последовательно соединенные стохас тический преобразователь кодов,пер-, вый регистр числа, селектор, сумматор,дешифратор нулевого числа,пермий ключ, первый и второй накопители информации, блок исправления оши» бок, выход которого годключен к одному иэ входов второго накопителя информации, первый вход соединен с одним иэ выходов первого накопителя информации, второй вход — с первым выходом третьего накопителя информации и одним из входов селектора, выход которого соединен с од- ним из входов первого ключа, датчик квазислучайных чисел, выход кото-. рого подключен к одному из входов стохастического преобразователя кодов, о т л и ч а ю щ е е с я тем,что, с целью повышения надежности устройства за счет повышения, достоверности исправления ошибок, в него введены второй регистр числа, второй ключ и блок оценки достоверности,выход которого подключен к третьему входу блока исправления ошибок, четвертый вход которого соединен с вторым выходом третъега накопителя информации,пераий вход блока оценки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход— ю с другим входом первого ключа, вход второго регистра числа подключен к первому выходу третьего накопителя информации.

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем,что блок оценки достоверности содержит третий и чет-! вертый регистры числа, первый и второй счетчики, группу счетчиков, пороговый элемент, блок сравнения, четвертый накопитель информации и

B элементы ИЛИ, входы которых подклю.че аи к одним иэ выходов третьего и четвертого регистров числа, а выходы — к входам третьего регистра числа, выход которого соединен с входом второго счетчика, входы счетчиков группы соединены с другиьы выходами четвертого регистра числа, а выходы подключены к входам порогового элемента, входы блока сравнения подключены к выходам счетчиков,порогового элемента и черветого накопителя информации, один иэ выходов блока сравнения соединен с входом четвертого накопителя информации, а другой выход и выход порогового элемента являются выходами блока, входами которого являются управляющий вход четвертого регистра числа и вход первого счетчика.

1086460

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

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

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

Наиболее близким к изобретению яв- ляется устройство для приема дискретной информации с исправлением oasiбок,содержащее .последовательно соединенные 4юрмирователь входного cursana. блок деления полиномов, к другому вжщу которого подключен датчик квазислучайной последовательнос-. ти,регистр дикодируемой комбинации, основной коммутатор, первый сумматор,блок анализа, ключ, к другому . входу которого подключен выход основного коммутатора, накопитель локализованных символов и выходной накопитель,причем к выходу накопителя локализованных символов подклю™ чаны последовательно соединенные блок выбора символов, блок выбора прове-, рочных соотношений н блок памяти,к другому входу которого подключен блок управления, управляемай от блока выбора символов,жходы блока памяти подключены соответственно к основному и дополнительному коммутаторам, вход последнего подключен к выходу накопителя локализованных символов, а выход через второй сумматор - к шаходному накопителю (2).

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

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

Поставленная цель достигается тем1 что в устройство для коррекции ошибок в блоках памяти, содержащее последовательно соединенные сто1S. лучайных чисел, выход которого под—

55

1О хастический преобразователь кодов, первый регистр числа, селектор, сумматор,дешифратор нулевого числа, первый ключ, первый и второй накопители информацчи,блок исправления ошибок, выход которого подключен к одному as входов второго накопителя ин4юрмации, первый вход соединен с одним иэ выходов первого накопителя информации, второй вход — с первым выходом третьего накопителя ин4юрмации и одним as входов селектора,выход которого соединен с одним из входов первого ключа, датчик квазисключен к одному из входов стохастического преобразователя кодов,введена второй регистр числа, второй ключ и блок оценки достоверности, выход которого подключен к третье». му входу блока исправления ошибок, четвертый вход которого соединен с вторым выходом третьего накопите» ля информации, первый вход блока оценки достоверности соединен с выходом второго ключа, один из входов которого соединен с выходом второго регистра числа, другой вход — с другим входом первого ключа, вход второго регистра числа подключен к первому выходу третьего накопителя информации

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

На фиг.l изображена структурная схема предложенного устройства; на

3086

3 фнг,2 — структурная схема блока оцейки достоверности.

Устройство (4иг.l) содержит стохастический преобразователь 1 кодов, первый регистр 2 числа, первый ключ

3, первый накопитель 4 информации, второй накопитель 5 информации, датчик 6 квазислучайных чисел,;, селектор 7,сумматор 8, дешифратор 9 нулевого числа, второй регистр 10 числа, второй ключ 11, блок 32 оценки достоверности, третий накопитель 13 информации,блок 14 исправления ошибок.

Блок 32 оценки достоверности со- 15 держит (4иг.2) четвертый наколи-. тель 15 информации, первый счетчик !6, блок 17 сравнения, третий регистр

18 числа, второй счетчик 39,элементы ИПИ 20, четвертый регистр Zl що числа, группу счетчиков 2, пороговый элемент 23.

Работа предлагаемого устройства основана на применении стохастических помехоустойчивых кодов,исправ- 25 ляюи3нх ошибки. Элементом (или

q-ичным символом) кода является отрезок двоичной последовательности длиной Я (q .2 ). Дпя К информационных 3-.-ичных символов по закону двоичного (n,k)-кода форвируется п--Зс избыточных символов. Например,: для (15,11)-кода Хэичинга q-ичные избыточные символы, обозначенные ниже цифрамн 1,2,3,4, полУчаются путем сущжровання по модулю два информа» циоиных символов, обозначенных бук-. вами А-Л.

I А+ Б+ Г+Д+333+И+П

2 А+ В+.Г+Е+Ж+ К+Я (1) 40

3 Б+ В+ Г+ 3+И+ К+Д.

4 Д+ Е + Ж+ 3 + И+ К. Д

Затем каждый иэ ц»ичных символов подвергается стохастическому (квазислучайному) преобразованию нод воэ- 45 действием кваэислучайной кодирукщей последовательности, На .этом процесс кодирования заканчивается.

Прямое и обратное стохастическое преобразование — это известные опера-50 ции, реализуемае как умножение и деление полиномов по модулю иепрнводимого полинома или выполняемые таб- лично (3g и (4),.

При декодировании вначале выполняется обратное стохастическое пре- образование каждого q-ичного символа под воздействием той же кваэислу460 4 чайной последовательности,что и при кодировании. В результате, если q-ич. иый символ не был искажей до декодирования, то имеет место исходное значение этого символа. Если же этот символ искажен любой помехой в промежутке между кодированием н декодированием;то после обратного стохастического преобразования происходит преобразование вектора ошибки или "шеремешнвание" искажений такого рода что любое из 2 -1 возмо>3пых значений этого символа (кроме исходного неискаженного) появляется с равной вероятностью.

После обратного стохастического преобразования производится выделение {локализация) правильно принятых ц-ичных символов путем проверки

2" — I проверочных соотношений,яв3 к лякикихся линейныж коЖинацняьк соотношений, используемах при кодировании. Для проверки некоторого соотношения сумяруют по модулю два все входяп3ие в эти соотношения и-ичные символы и проверяют результат суммирования на нуль (3). Комбинация из Й нулей после суммирования будет в том случае,если все символы не были искажены,или если искажение этих символов совпадает (при двух искаженных символах), Прн указанных свойствах стохастического преобразования, "перемешивакщего" искажения,достигается условие, что вероятность оакбочной локализации не превышает величины

Р„с2

-3

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

Описанные операции выполняются как в прототипе, так и в предложенном устройстве, однако этих операций недостаточно, так как путем анализа результатов декодирования (локализации) можно повысить помехоустойчивость декодирования. торого записаны в накопитель 13,а таблица соответствия величин N н

N< записана в накопитель 15.При этом каждый q-ичный символ записывается на одну дорожку носителя,чтобы сбой или неисправность канала записи-считывания искажали один

q-ичный символ кода.

Под воздействием кваэислучайной последовательности считанная информация поднергается преобразованию в преобразователе 1 и записывается в регистр 2. Из накопителя 13 по очереди считываются соотношения используемого (п,k)-кода, которые поступают в селектор 2 и регистр 1О. Указанные позиционным образом. в проверочном соотношении с1-ичные символы поступают через селектор 7 иэ регистра

2 в сумматор 8. Полученная сумма и-ичных символов проверяется на нуль в дешифраторе 9. Если имеется нулевая сумма, что через ключ 3 данные .символы переписываются в накопитель 4, а сама комбинация nposeрочного соотношения через ключ 11 sannwsaevcs в регистр 21. Одновременно в счетчике 16 добавляется "I" к числу ныполнившихся соотношений.

Проверочное соотношение имеет нид двоичной комбинации длиной и, где а — длина кода, в котором единицы стоят в тех позициях, которым соответствуют q-ичные символы, входящие в данное соотношение .Например, дпя первого соотношения, записанного в выражении (1), проверочное соотношение, обрабатываемое в данном устройстве.,имеет следующий вид:

Позиция кодового 1234АБВГДЕЖЗИКЛ слова

Вид проверочного 10001101 1010101 соотношенияя

Г

Значит, если данное соотношение выполнилось,то символы I,А,Б, Г,Д,Ж, И и Л локализуются н переписываются в накопитель 4, а комбинация

100011011010101 поступает из регистра 10 через ключ 11 в регистр

21 откуда переписывается через элементы ИЛИ 20 в регистр !8, в котором накапливаются номера позиций локализованных символов, для чего логически суммируются комбиS 1086 4б0

Введем понятие "ошибочной локализации", когда при искаженных q-ичных символах g! и 0„ проверочное соотношение, в которое входят они вместе, ныполняется. Но те соотно- 5 щения, куда эти символы входят по отдельности, не будут выполняться.

Тогда, сравнив число формально локализованных символов, в которые входят .и 0; н О", с числом ныполнякищихся соотношений, можно ныявить случай ошибочной локализации. Если дополнительно сосчитать число соотношений,в которые вошел каждЫй из n q-ичных символов Г то можно выявить q-a we !5 символы,локализованные ошибочно.

Путем стирания этих символов с последующим их исправлением можно повысить помехоустойчивость хранения информации. 20

Для каждого конкретного кода можно построить таблицу соответствия числа локализованных символов N> и числа выполнившихся соотношений N0 при правильной локализации. Если эти величины друг другу не соответствуют в конкретном случае, по проверяется число вынолнякщнхся соотноше- . ний, в которые вошел каждый символ

И . Если величина И меньше заданно- Зо го порогового значения, то символ с номером i стирается.Или ныдается потребителю с указанием на пониженную его .достоверность.

Путем анализа величин Я4 ° Й и 35 . И можно выделить несколько градаций ( достоверности, достигаемой при декодировании: при и 2 -1 достигается нысшая

C или абсолютная достоверность, так 40

: как есть гарантия, что информация ъ, в принципе не содержит ошибок", в scLBHcHMocTH от используемого кода достигакГгся i-градации достоверности Г при каждой иэ которых 45 вероятность ошибки ие пренлвает ве;е

ФИ

В этом случае после декодирования вместе с информацией выдается признак степени достоверности выдаваемой информации.

Устройство с учетом изложенного работает следующим образом.

Считаем,что информация записана в запоминающее устройство (ЗУ) ЭВИ с использованием конкретного (n-lс)-кода,проверочные соотношения для ко)086460 8

Сигнал стирания представляет собой позиционную запись номеров ненадеино принятых (стертых) q-ичных символов .Блок 17 сравнения может быть выполнен в соответствии с (5) .

Номера позиций нелокализованных и стертых q-ичных символов поступают в блок 21 исправления ошибок, куда поступают также значения локализо)0 ваннах символов иэ накопителя 4. В блоке )4 производится исправление ошибок.йсправленйе каждого as подлекащих исправлению q-ичных символов состоит в выборе проверочного соотношения, в которое входит исправ»" ляемай meson и ранее локалиэированные символы. Тогда значение исправля. емого символа равно сугееь по вюдулю два этих локализованных символов

Значения исправленных ц-мчных символов записываются в накопитель 5. нации выполнившихся проверочных" соотношений. Одновременно "единицы" выполнившихся проверочных соотношений из регистра 21 параллельно поступают íà и счетчиков 22, где подсчитывается дпя какдого q-ичного символа число выполнившихся соотно» шений, в которых присутствовал этот символ.

В результате после проверки в-с всех 2 -1 соотношений для ко- да () 5, I ) ) (число этих соотношений равно 24 — 1)5) в регистре 18 записаны ")" в тех позициях, которым соответствуют локализованные в одном или в нескольких соотношениях q-ичные:символы,à s счетчиках 22 — число этих соотношений дпя какдого символа. После этого производится подсчет числа локализованных символов в счетчике )9, на вход которого сдвигается комбинация нз регистра 23. .В блоке )7 проверяется соответ.ствие величин й,) и N< полученных в счетчиках 16 и 19 соответственно, в еравнении с таблицей соответствия, считываемой из накопителя 15.

Пороговый элемент 23 вырабатывает сигнал стирания тех q-ичных символов, которые приняты ненадежно,т.е. число выполнившихся соотношений дпя которых нике заданного порога.

Технико-эконожческий эффект предлагаемого устройства состоит в повы25 веник достоверности хранения инфор-, мации за счет операций оценки достоверности, стирания и исправления . недостоверных q-ичных символов, а такае в поношении помехоустойчивости щ и надекности хранения информации за счет исправления сбоев и выделения части неискаженных ц-ичюнс симво-. лов., 1086460

Составитель В.Рудаков

Текред Л.Кнкев Корректор А. Зимокосов

Редактор И.Петрова

Филиал ППП "Патент", г. Уагород, ул. Проектная, 4

Заказ 2257/47 Тираа 575 Подписное

ЯППИ Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, Ж-35, Раувская наб., д. 4/5