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

 

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

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

РЕСПУБЛИН

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

К АВто СИому СеиДяткЛьСтау

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЪ9 (21) 3557268/24-24 (22) 28,02.83 (46) 23.11;84. Бюл.Р 43 (72) A.М.Шашин и И.Б.Белов (71) Ленинградский институт авиационного приборостроения (53) 681.327(088 ° 8) (56) 1.Авторское свидетельство СССР

Р 841062, кл. G 11 С 29/00, 1979.

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

9 556501, кл. G 11 С 29/00,1975 (прототип) . (54)(57) 1.ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

С КОРРЕКЦИЕЙ ИНФОРМАЦИИ, содержащее основной накопитель, адресные входы которого подключены к выходам адресного блока, а информационные входы соединены с выходами, входного регистра и одними из входов сумматоров .по модулю два первой группы, выходы которых подключены к.входам буферного накопителя, а другие входы — к выходам выходного регистра, счетные входы которого соединены с выходами блока коррекции информации, и первый блок кодирования,. одни из входов которого соединены с выходами буферного накопителя, а информационные выходы— со счетными входами входного регистра, причем выходы основного накопителя подключены к информационным входам выходного регистра, управляющие входы основного накопителя и блока коррекции информации и установочные входы входного и выходного регистров соединены с одними иэ управляющих выходов первого блока кодирования, выходы синхронизации кото- рого подключены соответственно к входам .синхронизации буферного нако„„su„„ i 125656 A пителя, входного регистра и выходного регистра, а другие входы и другой управляющий выход являются соответственно управляющими входами и управляющим выходом устройства, одними из информационных входов и информационными выходами которого являются соответственно одни иэ информационных входов входного регистра и выходы выходного регистра, о т л и— ч а ю щ е е с я тем, что, с целью увеличения информационной емкости устройства, в него введены селектор и второй блок кодирования, входы которого являются другими информационными входами устройства, а выходы соединены с другими информационными Е

С2 входами входного регистра, причем входы селектора подключены к одним иэ выходов выходного регистра, а выходы — .к входам блока коррекции информации.

2. Устройство по п.l, о т л и — Я ч а ю щ е е с я тем, что селектор содержит вторую группу сумматоров по модулю два и мажоритарный элемент,, входы которого являются входами селек тора и соединены с одними из входов сумматоров по модулю два второй группы, другие входы которых подключены к выходу мажоритарного элемента, а выходы являются выходами селектора.

3. Устройство по пп.l и 2, о т— л и ч а ю щ е е с я тем, что второй блок кодирования содержит третью группу сумматоров по модулю два, входы которых являются входами блока, а выходы - одними из выходов блока.

1125656

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

Недостатком устройства является

era сложность.

Наиболее близким к изобретению является запоминающее устройство с коррекцией информации, содержащее накопитель, одни входы которого подключены к выходам адресного блока, другие входы накопителя соединены с выходами входного регистра, вы- 15 ходы накопителя подключены к входам выходного регистра, счетные входы которого соединены с выходами блока коррекции, выходы входного регистра подключены к одним из входов сумма- 2О тора, другие входы которого соединены с выходами выходного регистра и входами блока коррекции информации, выходы сумматора через буферный накопитель соединены с входами блока кодирования согласующего слова 2 .

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

Цель изобретения — увеличение информационной емкости устройства за счет хранения части информационных разрядов записываемого слова в ячейках памяти накопителя, предназ- 40 наченных для хранения контрольных разрядов записываемого слова.

Поставленная цель достигается тем, что в запоминающее устройство с коррекцией информации содержamee ос 45 новной накопитель, адресные входы которого подключены к выходам адресного блока, а информационные входы соединены с выходами входного регистра и одними из входов сумматоров по модулю два первой группы, выходы которых подключены к входам буферного накопителя, а другие входы — к выходам выходного регистра, счетные входы которого соединены с выходами блока коррекции информации, и первый блок кодирования, одни из входов которого соединены с выходами буферного накопителя, а информационные выхрды — со счетными входами входного регистра, причем выходы основного накопителя подключены к информа-ционным входам выходного регистра, управляющие входы основного накопителя и блока коррекции информации и установочные входы входного и выход- 65 ного регистров соединены с одними из управляющих выходов первого блока кодирования, выходы синхронизации которого подключены соответственно к входам синхронизации буферного накопителя,входного регистра и выходного регистра, а другие входы и другой управляющий выход являются .соответственно управляющими входами и. Управляющим выходом устройства, одними из информационных входов и информационными выходами которого являются соответственно одни иэ информационных входов входного регистра и выходы выходного регистра, введены селектор и второй блок кодирования, входы которого являются другими информационными входами устройства,а выходы соединены с другими информационными входами входного регистра, причем входы селектора подключены к одним из выходов выходного регистра, а выходы — к входам блока коррекции информации.

При этом селектор содержит вторую группу сумматоров по модулю два и мажоритарный элемент, входы которого являются входами селектора и соединены с одними иэ входов сумматоров по модулю два второй группы, другие входы которых подключены к выходу мажоритарного элемента, а выходы являются выходами селектора.

Кроме того, второй блок кодирования содержит третью группы сумматоров по модулю два, входы которых являются входами блока, а выходы— одними иэ выходов блока.

На фиг.1 представлена функциональная схема предложенного устройства; на фиг.2 — 4 — функциональные схемы наиболее предпочтительных вариантов выполнения селектора, второго блока кодирования и первого блока кодирования соответственно для хранения 16-битных сообщений в 20-разрядных ячейках памяти, иэ. которых два разряда или меньше дефектны.

Устройство содержит (фиг.1) основной накопитель 1, адресный блок

2, входной регистр 3„ — 3, выходной регистр 4„- 4, буферный накопитель 5, первый блок 6 кодирования, блок 7 коррекции информации, первую группу сумматоров 8 по модулю два. На фиг.1 обозначены информационные входы 9 входного регистра 3, адресные входы 10 устройства и счетные входы 11 входного регистра 3.

Устройство содержит также второй блок 12 кодирования и селектор 13. На фиг.1 обозначены также вход 14 синхронизации буферного накопителя 5, управляющие входы 15 и

16 основного накопителя 1, входы 17 синхронизации выходного регистра 4,.

1125656 установочные входы 18 входного 3 и выходного 4 регистров, входы 19 синхронизации входного регистра 3, управляющий выход 20 устройства, один из управляющих выходов 21 первого . блока 6 кодирования, управляющие

22-24 и информационные 25 и 26 входы устройства, а также информационные выходы 27 и 28 устройства.

Селектор 13 содержит (фиг.2) мажоритарный элемент 29 и вторую группу сумматоров 30 по модулю два.

Второй блок 12 кодирования содержит (фиг.3) третью группу сумматоров

31 по модулю два.

Первый блок б кодирования содержит (фиг..4) элемент ИЛИ-И 32, гене.Ратор 33 импульсов, счетчик 34, де" шифратор 35, генератор 36 одиночных импульсов, триггер 37, элементы

И 38-42, элементы ИЛИ 43-46, элемент 47 задержки, группу элементов

ИЛИ 48 - 48> и группу элементов

И-ИЛИ 49„- 49

Входы каждого из элементов ИЛИ

48 — 48„ соединены с объединенными по ИЛИ выходами предшествующих элементов ИЛИ 48, i и соответствую" щими входами блока б, подключенными к выходам накопителя 5, Устройство работает; следующим образом.

Для увеличения информационной емкости устройства .записываемое в накопитель 1, и-разрядное слово фор» мируется как сумма по модулю два трех слов:

u=(u„...u,....и„,о),u,å(î; 3,м» к, к< - слово, первые К разрядов которого являются информационными, а последние г разрядов равны нулю (г = и - к ) у

I-

06об=(0... 01 Ох+„ .. 0; ...О, ), (3,6(0 1, К <1 ап слОво, первые К разрядов которого равны нулю, следующие К разрядов (K+1 4 К+К (и ) являются информационными, а .последние (-К) — контрольными и такими, что последние разрядов слова U»$ являются кодовым словом линейного кода (r„K ), исправляющего t -кратные ошибки (r- дли- на кода; К вЂ” число информационных компонентов,B коде), и

c ..c„), c. q(o;z$, fa i< подно из согласующих слов, которыми являются слова (я,п) кода, двойственного линейному коду с минимальным расстоянием Хемминга 5 +1 и у которых последние разрядов, . называемые ключем, различны у всех согласующих слов и содержат не бо лее Ф единиц (Eсr, 4 — целое число, равное допусуимому чйслу дефектных элементов памяти среди элементов, предназначенных для хранения одного слова) . Это слово выбирается таким образом, чтобы под лежащие хранению в дефектных элемен-. тах памяти разряды слова 0 SU pO+< .совпадали с теми двоичными символами, которые хранятся в соответствующих..:

5. дефектных ячейках.

При предлагаемом способе формиро» вания записываемого в накопитель 1 слова, число информационных разрядов в слове íà k больше, чем при

10 известном. При заййси информации первые K n-r разрядов. информационного слова

U=(U„...U„, ); U,.=(O; ), Èiаn+K . помещаются в пеРвые К Разрядов Регистра 3 через входы 25, а последние . разрядов помещаются в блок 12 (фиг.1) . Из блока 12 закодированные кодом (r, к ) последние разряды информационного слова помещаются в последние r разрядов регистра 3 через входы 9 регистра 3. Слово x-=(х„...х„) где х; е(0; i )1 1 g n такое, что

x. =U. 14 i 4 К+к переписывается в

1 i накопитель 1 по адресу, заданному на входах 10. После этого осуществляется контрольное считывание слова из накопителя 1 в регистр 4.

Слово х.=(х .-. х.)1 х ° 5(0,1) 1 i 4п поступающее в регйстр 4, может отлиЗ0 чаться от исходного слова из-за воздействий отказов элементов памяти накопителя 1. На выходах сумматоров 8 формируется первый вектор ошибок

4S

С х9r (х„9+x,... хпО+"„) где знак О+ означает сложение по модулю два.

Вектор 1; поступает через накопи- тель 5, где он запоминается, в блок б. Если Ф;=О, т.е. если слово, х совпадает с x,тб цикл записи заканчивается. Если 3;4 о, то на входы 11 регистра 3 подаются символы 1 с выхода блока 6. В результате этого з регистре 3 оказывается двоичное. слово ч, отличающееся от исходного слова r во всех компонентах (v называется инверсным кодовым словом) .

Слово ч помещается в накопитель

1 на место слова х . Далее осуществляется контрольное считывание слова ч в регистр 4. При этом на выходах сумматоров 8 формируетсз вектор ошибок 1 = з О+ v, где ч — слово, полученное при контрольном считывании.

Вектор ошибок :1 поступает через накопйтель 5 в блок 6, на выходах которого по векторам ошибок

t„. и 6 формируется корректирующее слово ()1=(С„,О1... С„О11,С,. е(В; ) «4 и, 1125656

2 =1(+) сQ+1= хQ+c

К=15 которое подается на входы 11 регистра 3. В результате этого в регистре 3 оказывается слово

00110111010100001001

11011101010000100101

0100101100111100011

0 которое может храниться в рассматриваемой ячейке без ошибок (при наличии в последней не более де-. фек ных запоминающих элементов).

Слово z переписывается иэ регистра

3 в накопитель 1 по заданному ранее адресу, На этом цикл записи за-. канчивается.

При считывании слово из ячейки накопителя 1 с заданным адресом как обычно, считывается в регистр 4. Содержимое последних разрядов выходного регистра 4 поступает в селектор 13, где происходит выделение клю-. .ча согласующего слова. Ключ согласующего слова С с выходов селектора 13 поступает на вход блока 7, на выходе которого по нему формируется согласующее слово с, поступающее на счетные входы регистра 4, в котором в первых К + К разрядах восстанавливается исходное информационное слово 0.

Таким образом, увеличивается информационная емкость накопителя 1, которая для известного устройства рав- ЗО к+ к на, а для предложенного — "+

11100011011101010000 Порождающая

11110001)01110101000 матрица

000110111010000100 кода (20,5) 50

11000110111010100001

00010010110011111000

ll1110001101110101000

0010010110011111001

01i11100011011101010

Более детальное формирование согласующих слов рассмотрим на примере

ЗУ для хранения 16-битных сообщений 35 в ячейках из двадцати элементов памяти каждая. Среди элементов памяти, образующих ячейку, допускаются два или менее дефектных элемента. для этого примера согласующими 40 словами являются слова (20,5), т.е. ,слова укороченного кода, двойственного коду Хемминга (31,26) . Поскольку в качестве согласующих слов ..берутся строчки порождающей матрицы и их комбинации по два, то множество согласующих слов состоит из пятнадцати следующих слов:

0 =20

Кодом для кодирования дополнительной информации может, например, быть код (5,1), состоящий из двух

-слов (lllll; 00000), т.е. для этого примера К =l.

Для выработки согласующего слова используются элементы ИЛИ 48 -48

36 (фиг.4) и элементы И-ИЛИ 49„ - 49

Элементы ИЛИ 48„- 48, служат для выделения первого согласующего слова, например, первого для приведенного примера. Например, на выходе элемента ИЛИ 48; (где 1 4 i 6 15) появляется единичный сигнал только тогда, когда (i + 1) -е слово является первым, согласующим информационное слово с дефектом, присутствующим в ячейке накопителя 1. Это достигается благодаря тому, что на входы каждого t-ro из элементов ИЛИ.48 — 48 подаются соединенные по ИЛИ выходы предшествующих элементов ИЛИ 48 -48

1 14, и те компоненты векторов ошибок В„ и номера которых соответствуют номерам нулевых (для вектора 1„) и соответствечно единичных (для вектора t ) разрядов согласующего (t +1)-го слова. Сигналы на выходах ИЛИ 48

14

48 соответствуют компонентам слова, инверсного согласующему слову.

Это достигается за счет того, что сигналы с выходов каждого иэ элементов ИЛИ 48„- 48„ подаются на входы тех из элементов ИЛИ 48„ - 48д номера которых совпадают с номерами единичных разрядов (0+1) -го согласующего слова.

На выходах элементов И-ИЛИ 49 -49

Формируются информационные сигналы

20 блока 6, поступающие на входы 11 регистра 3. -Таким образом,. в предлагаемом устройстве исправляется заданное количество ошибок типа дефект44 в элементах ячейки накопителя 1, г.е. сохраняется та же корректирующая способность, что и в известном.

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

1125656

27

1125656 вн

Тир

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