Логическое запоминающее устройство

 

Союз Соаетсииа

Соцмалмсттетееаюен

Веесяублтек

{11) 61{:)1 74 (61) Дополнительное к авт. сеид-ву (22) Заявлено 14.06.76 (21) 2372588/18-24 с присоединением заявки ¹ (23) Приоритет (51) М. Кл. (- 11 С 15/00

Государственный квинтет

Совете Инннетров СССР не делам нзобретеннй н еткре1тнй (43) Опубликовано 05,06.78.Бюллетень № 21 (531 тДК 681.327 (088.8) {45) Дата опубликования описания 04.05.78

{тт2) Автори изобретения

Е. П, Балашов, Н. Н. Варлинский, В, Н. Волкогонов, Г. А. Петров и В. С. Степанов (71) Заявитель

Ленинградский ордена Ленина электротехнический институт им. Ульянова (Ленина) (54) ЛОГИЧЕСКОЕ ЗАПОМИНАЮШЕЕ УСТРОЙСТВО

Изобретение относится к запоминатещим устройствам.

Известно логическое запоминающее устройство (ЗУ), содержащее блоки памяти, каждый из которых хранит определенное число одноразрядных слов и включает в себя

=xe:1у дедифрации aapeca, perr стр адреса, pc r истр слова, - управляющие элементы И, ИЛИ и триггер анализа содержимого регистра слова (1 1 . то

Недостатком такого ЗУ является низкое быстродействие при реализации операции кодирования и декодирования информации.

Из известныхустройств наиболее близким техническим решением к изобретению являетсят5 логическое ЗУ, содержащее постсянный накопитель, подключенньй через дешифратор адреса к регистру адреса, выходной регистр, счетные входы которого подключены к выходам элементов И, входнь.е, вьтходцые и 2тт информапионнье шины (21 .

К недостатка vl этого устройства относятся Heвозможность вьлтэлнения операции декодирования и большая емкость- постоянного накопите.- я, 25

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

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

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

610174 выходами регистра адреса, а выходы — с соответстнук.шими выходными шинами. Упгзавлякд ие входы дополнительньгх дешифратора и регистра, элементов И, выходного реГис г а KoKIM GTopB приема выдачи и ключе- 5 вого элемента соединены с соответствующими шинами.

Кодирование. в циклическом коде и декодирование циклического кода осуществляются следуняцим образом. I0

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

20 х Ф1 и. (х)—

Р (x) где х +1 — бином степени, и

1 и, (x) — многочлен степени пъ, который назьгвается проверочным 25

Циклический код полностью определяется многочченами Р(Х) и h. (Х). Кодовую последовательность циклического кода можно представить в виде;

f(") = (х)х + I(x)

Коэффициенты многочлена $ (Х ) Х при к членах низшего порядка равны нулю, а при m членах высшего порядка соответст- З5 вуют коэффициентам в информационной последовательности g. (х), достоверность которой необходимо повысить, Многочлен Г(>() степени к-1 называется многочленом проверочньх символов кодового многочлена. Таким образом, KorIoBbIH многочлен f (х) имеет степень YI -1, а число коэффициентов Yl =1Я+ к.

Для того чтобы задать циклический код, т.е. найти все 2 комбинаций, достаточ но найти тп основных комбинаций„которь|е 5 образуют порождае.кую матрицу циклического кода, иукаэатьпорядок образования остальных

2 " m кодовых многочленов. Для систе- . матического циклического кода порождающая матрица Р состоит из единичной матрицы Im: 50 размерности 1п.m и матрицы проверочных символов Я размерности (TI-m) тп. Таким обра зом, и имеет размерность П тп

Матрица Р полностью задает циклический кад. Для получения комбинаций циклического када нужно умножить строки матрицы P па коэффициенты информационного

I многочлена g (Х) и результаты произведений сложить. В результате получают комбинацию циклического кода. Но так как результат сложения произведений строк единичной матрицы 1, на коэффициенты многочлена g (х) дает этот же информационный многочлен g (х), То достаточно брать лишь произведения матрицы К на (х), и результат сложения дает многочлен проверочных символов T (х), Таким образом, записав в постоянный накопитель устройства только матрицу проверочных символов R. порождающей матрицы Р вместо всех 2 комбинаций многочленов

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

Рассмотрим операцию декодирования циклического кода.

Каждая кодовая комбинация циклического кода удовлетворяет условию

Р H = =О, где — последовательность коэффициентов кодового многочлена

Р (х);

Я - транспортированная проверочная матрица циклического кода размерности (т — тп ) т

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

ЗУ, на фиг. 2 представлено распределение области постоянного накопителя.

Логическое ЗУ содержит постоянный накопитель 1, дешифратор адреса 2,. регистр

610174 адреса 3, дополнительный регистр 4, элементы И 5, выходной регистр 6, ключевой элемент 7, коммутатор приема-выдачи S, элемент ИЛИ 9 и дополнительный дешифратор 10, 5

Выходы дешифратора 10 подключены к выходным шинам 11 и 12, на которые поступают сигналы "обработано щ символов и

"обработано tl символов соответственно, Управляющий вход дешифратора 10 соеди- 1й нен с управляющей шиной 13, служащей для опроса дешифратора 10, входы которого подключены к выходам регистра адреса 3.

Адресные шины 14 — 16 служат соответственно для установки адреса 2 ячейки 15 накопителя 1, для увеличения адреса на единицу, для разрешения приема адресов ячеек с 0 по (2 -1 ) в .регистр 3 и установки части разрядов регистра 3 в состояние О, Управляющий вход регистра 4 20 соединен с управляющей шиной. 17, слу- жающей для установки его в нулевое состоя- ние, Устройство содержит также управляющие шины 18 для разрешения перезаписи содержимого регистра 6 в регистр 4,шины

19 для считывания ошибки, шины 20 для сдвига содержимого регистра 6 влево, шины

21 для выбора режима коммутатора 8, выходную шину 22, управляющую шину 23 для разрешения приема информации в регистр ЗО

6 и входную шину 24.

Входы элемента ИЛИ 9 подключены к шине 19 и выходу коммутатора 8, а выходко входу дешифратора 2. Информационные входы коммутатора 8 подключены к шинам

22 и 24, Входы регистра 4 соединены с выходами накопителя 1, а выходы — с ин- формационными входами элементов И 5. Вход регистра 6 через ключевой элемент 7 соединен с шиной 24. Управляющие входы 25 регистра 3 соединены со старшими разрядами регистра 4. Управляющие входы элементов И 5, коммутатора 8 и ключевого .элемента 7 соединены соответственно с ши45 нами 18, 21 и 23.

В ячейках накопителя 1 по адресам с к нулевого по 2 -1 (фиг. 2) записаны многочлены ошибок (область 1 ° 1) . В младших к разрядах ячеек с адресами с 2 по к (2" + ) (область 1.2) записана транспонированная проверочная матрица Н дит клического кода. B старших к разрядах ячеек с адресами с 2" по (2 + п ) (область 1,3) записана матрица проверочных >> символов 8 порождающей матрицы Р, Кодирование осуществляется следующим образом, В исходном состоянии коммутатор 8 находится в положении "выдача, ключевой

% элемент 7 закрь1т, в регистре 3 адреса установлен адрес 2 -Й ячейки накопителя 1, регистр 4 установлен в нулевое состояние, а в регистре 6 записана информапионная последовательность. На шину 20 подается импульс сдвига, содержимое регистра 6 сдвигается влево на один разряд, и .символ информапионной последовательности поступает на шину 22 и одновременно через коммутатор 8 и элемент ИЛИ 9 на вход дешифратора 2, Если символ единичный, то из накопителя 1 считывается один из многочленов проверочных символов порождающей матрицы, который составляет К старших разрядов слова, и многочлен записывается в регистр 4, 1

На шину 13 подается сигнал, ч проверяетгя условне выдачи тп информационных симво лов из регистра 6, о чем свидетельствует сигнал на шине 11, Если выдано меньше re символов, т,е. на шине 11 отсутствует сигнал, то содер— жимое регистра 3 увеличивается на единицу, с этой целью на шину 15 подается сигнал, и продолжается выдача информационных символов из регистра 6 и считывание многочленов проверочных символов из накопителя 1, которые суммируются по модулю два с содержимым регистра 4. Если выдано тп символов, то на шине 11 появляется сигнал, т,е, иэ регистра 6 выдается информационная последовательность, а в регистре 4 записььвается многочлен проверочных символов кодовой последовательности, На шину 18 поступает сигнал,и многочлен проверочных символов переписывается в регистр 6 из регистра 4, Проверочные символы заполняют к старших разрядов регистра 6, причем содержимое младших разрядов не имеет значения, При дальнейшем поступлении импульсов сдвига на шину 20 проверочные символы поступают на шину 22, После каждого такта сдвига содержимого регистра 6 опрашивается дешифратор 10. Для этого на шину 13 подается сигнал, и проверяется условие выдачи т символов кодовой последовательности, о чем свидетельствует сигнал на шине 12, Если условие не выполняется, то продолжается выдача проверочных символов, в противном случае кодирование заканчивается, Декодирование осуществляется следующим образом, В исходном состоянии коммутатор 3 находится в положении прием, ключевой элемент 7 открьгт, в регистре 3 находится к адрес 2 ячейки накопителя 1, регистр 4 установлен в нулевое состояние; содержимое регистра 6 сдвинуто на один разряд влево для освобождения младшего разряда. Символ кодовой по ледовательности поступает на шину 24 и через ключевой элемент 7

610174 записывается в младший разряд регистра 6 и одновременно через коммутатор 8 и элемент ИЛИ 9 поступает на вход дешифратора 2. При этом если символ единичный, то один из многочленов проверочной матрицы считывается из накопителя 1 в младшие разряды регистра 4. На шину 13 подается сигнал и проверяется условие приема тй символов кодовой последовательности в регистр 6, о чем свидетельствует сигнал на 1О шине 11.

Если принятб символов, т.е. íà ши- не 11 появляется сигнал, то ключевой weмент 7 закрывается и прекращается посту- 1s пление импульсов сдвига на шину 20, т,е, прекращается прием кодовой последовательности в регистр 6, но продолжается считывание многочленов транс пэнированной проверочной матрицы из накопителя 1 и суммирование их по модулю 20 два в регистре 4, В противном случае опрашивается дешифратор 10 сигналом, поступающим по шине 13, и проверяется условие приема тг символов кодовой последовательности, о чем свидетельствует сигнал 25 на шине 12. Если принято меньше, чем

zn символов, то содержимое регистра 3 увеличивается на единицу поцачей сигнала на шину 15 и продолжается прием кодовой последоватечьности. В противном случае на шину 16 поступает сигнал разрешения в регистр 3 содержимого к младших разрядов регистра 4. Регистр 4 устанавливается в нулевое состояние подачей сигнала на шину 17.

На шину 19 поступает сигнал разрешения, и многочлен ошибки, имеющийт разрядов, счи-. тывается из накопителя в регистр 4. На шину

18 элементов И 5 подается сигнал, и много,член ошибки суммируется по модулю два с содержимым регистра 6, т.е. производится исправление ошибки.

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

)Я раз, где N = g g /у гтг, - .) - тд

Например, для циклического кода, пмеюшего =15, 1т1 =10 получаем g =1 1.

Формула изобретения

Логическое запоминающее устройство, содержащее постоянный накопитель, подключенньгй через дешифратор адреса к регистру адреса; выходной регистр, счетные входы которого подключены к выходач элементов

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

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

Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР № 524224, М. кл. 6- 11 С 15/00, 1976, 2. Дроздов Е, А. и Пятибратов А, П, Автоматическое преобразоваггие и кодггро вание информации, М., "Советское радио", 1964, с, 501, 610174

16 юэ

2Я

2е

Фиг. 1

4 из. г

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

Редактор Л. Утехина Техред О, Андрейко

Корректор Д, Мельниченко

Заказ 3020/41 Тираж 717 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по дела.,i изобретений и открытий

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

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