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

 

Изобретение относится к вычислительной технике и может быть использовано в системах сложной логической обработки информации. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения считывания первоначальной формы массива информации, записанного в сжатой форме. Устройство содержит блок 1 памяти, мультиплексор 14 адреса, регистр 15 номера разряда, первый 31, второй 18 и третий 21 счетчики, формирователь 27 адреса, блок 41 приоритета, блок 42 анализа информации о массиве, первый 46 и второй 51 регистры сдвига, блок 50 приоритетных шифраторов, приоритетный шифратор 55, блок 56 управления. Блок 1 памяти содержит блок 2 записи-считывания столбца, входной 5 и выходной 37 регистры слова, блоки усилителей считывания столбца 7 и строки 36, регистр 8 столбца, блок 10 записи-считывания строки, дешифратор 13 адреса, блок 39 поиска групп единиц. 2 ил.

СОЮЗ СОВЕТСКИХ сОцИАлистических

РЕСПУБЛИК (51) 5 6 11 С 15/00

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4256473/24-24 (22) 04.06,87 (46) 23,05,90, Бюл, № 19 (71) Северо-Западный заочный политехнический институт (72) А.Н,Жернак, И.С.Петров, В,A.Ïoáåäíoâ и В.В.Спиридонов (53) 681,327 (088.8) (56) Авторское свидетельство СССР

¹ 996633009999,, кKJл!, G 11 С 15/00, 1981, Авторское свидетельство СССР № 1316047, кл. G 11 С 15/00, 1986.

ÄÄSUÄÄ 1566411 А1 (54) ЛОГИЧЕСКОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в системах сложной логической обработки информации. Цель изобретения — расширение функциональных возможностей устройсва за счет обеспечения считывания первоначальной формы массива информации, записанного в сжатой форме. Устройство содержит блок 1 памяти, мультиплексор

14 адреса, регистр 15 номера разряда, пер1566411

45 вый 31, второй 18 и третий 21 счетчики, формирователь 27 адреса. блок 41 приоритета, блок 42 анализа информации о массиве, первый 46 и второй 51 регистры сдвига, блок

50 приоритетных шифраторов, приоритетный шифратор 55, блок 56 управления. Блок

1 памяти содержит блок 2 записи-считываИзобретение относится к вычислительной технике и может быть использовано в системах сложной логической обработки данных.

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

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

Устройство содержит (фиг.1) блок 1 памяти, включающий блок 2 записи-считывания столбца с входом 3 считывания столбца и входом 4 записи столбца, входной регистр

5 слова с информационным входом 6, блок

7 усилителей считывания столбца, регистр 8 столбца с входом 9 сброса, блок 10 записисчитывания строки с входом 11 считывания строки и входом 12 записи строки, дешифратор 13 адреса. Устройство также содержит мультиплексор 14 адреса, регистр 15 номера разряда с входами сброса 16 и занесения 17, второй счетчик 18 с суммирующим входом 19 и входом 20 начальной установки, третий счетчик 21 с входом 22 разрешения приема информации, суммирующим входом

23 и вычитающим входом 24, блок 25 сравнения с выходом 25 "Окончание анализа слов стека", формирователь 27 адреса с управляющим входом 28, адресный вход 29 устройства и индикаторный выход 30, первый счетчик 31 с суммирующим входом 32, вычитающим входом 33, входом 34 начальной установки и выходом 35 "Граница стека". Блок 1 памяти также содержит блок 36 усилителей считывания строки, выходной регистр 37 слова, накопитель 38, блок 39 поиска групп единиц с выходом 40.

Устройство также содержит блок 41 приоритета, блок 42 анализа информации о массиве с выходами 43 — 45, первый регистр

46 сдвига с входом 47 сброса, входом 48 занесения и входом 49 сдвига, блок 50 приоритетных шифраторов, второй регистр 51 сдвига с входом 52 сброса, входом 53 эане5

35 ния столбца, входной 5 и выходной 37 регистры слова, блоки усилителей считывания столбца 7 и строки 36, регистр 8 столбца, блок 10 записи-считывания строки, дешифратор 13 адреса, блок 39 поиска групп единиц. 2 ил. сения и входом 54 сдвига, приоритетный шифратор 55, блок 56 управления.

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

В процессе функционирования устройства N первых слов (строк) накопителя 38, допускающих считывание и запись по строкам и столбцам, используются для хранения массивов информации, длина которых не превосходит N. Следующие(последние) 0,75 и слов накопителя 38, допускающие считывание и запись информации только по строкам, используются в качестве области стека, причем n — разрядность хранимых в накопителе слов (строк), т.е, число столбцов.

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

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

Соответствующее этому размещение информации в накопителе 38 показано на фиг.2в. Первые N=5 слов накопителя занимает уплотненный массив, причем содержимое столбцов с номерами О, 1 и 2 (нумерация начинается с нуля и идет справа налево) безразлично. Четыре последних слова (0,75 и, где п=б разрядов) накопителя занимает область стека. в которой первые две строки содержат информацию о совпадающих группах, две единицы в первом слове стека расположены в разрядах, соответствующих левому и третьему (слева) 1566411

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

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

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

Выполнение первого этапа сводится к получению в регистре 46 информации стека слова, равного дизьюнкции всех слов стека с обнуленными левыми единичными разрядами, что осуществляется посредством поочередного считывания слов стека на выходной регистр 37 слова с последующей передачей их на регистр 46 через блок 41, гасящий левые единицы (такты 1 — 5, описываемые ниже), Затем поочередным сдвигом содержимого регистра 46 просматриваются, начиная справа, все разряды полученной диэъюнкции, Причем нулевые значения разрядов указывают на несовпадавшие столбцы или опорные столбцы групп. Эти столбцы считываются из уплотненного массива и записываются на свои первоначальные места (та кт ы 6 — 1 1).

Выполнение второго этапа состоит в поочередном считывании слов стека на регистр 51 и сравнении этих слов с ранее полученной их дизьюнкцией, хранимой в регистре 46 (после первого этапа содержимое регистра 46 принимает исходный вид, так как сдвиг в нем циклический). При этом при значениях сравниваемых разрядов 00, 01 и

10. говорящих о том, что соответствующие анализируемому разряду столбцы уже восстановлены, происходит сдвиг вправо содержимого регистров 46 и 51 и переход к анализу следующей пары разрядов. Если пара разрядов имеет значение 11, то опорный столбец группы, записанный по адресу самой левой единицы в слове стека, зане5

50 сенном в регистр 51, восстанавливается перезаписью на первоначальное место, соответствующее анализируемому разряду (такты 12 — 20).

Процедура восстановления первоначального вида массива включает в себя следующие такты.

Первый такт. На вход 33 счетчика 31 от блока 56 подается управляющий сигнал, в результате чего в нем устанавливается код адреса слова, записанного в стек последним (так как после окончания операции уплотнения массива информации в счетчике

31 установлен код адреса. следующего за адресом последнего записанного в стек слова).

Второй такт. Подается сигнал от блока

56 на вход 11 считывания строки, в результате чего в выходной регистр 37 слова заносится слово, считанное по адресу, установленному в счетчик 31 указателя стека, Третий такт. Подается сигнал от блока

56 на вход 48 занесения информации, что приводит к пересылке слова иэ регистра 37 в регистр 46, в процессе выполнения которой блоком 41 обнуляется старшая (левая) единица пересылаемого слова.

Четвертый такт, Подается сигнал от блока 56 на вход сброса, в результате чего производится очистка регистра 37.

Пятый такт, Анализируется блоком 56 сигнал на выходе 35 счетчика 31. Наличие единицы на этом выходе свидетельствует о том, что иэ стека считано последнее слово, В этом случае осуществляется переход к шестому такту, в противном случае — к первому.

Шестой такт. Подается сигнал от блока

56 на вход 34 начальной установки, в результате чего в счетчик 31 устанавливается код адреса слова, записанного в стек последним. Одновременно от блока 56 подаются сигналы на вход 22 разрешения приема информации и вход 20 начальной установки, в результа-е чего счетчик 18 сбрасывается в нуль, а в счетчик 21 иэ формирователя 27 передается адрес нижней (правой) границы уплотненного массива.

Седьмой такт, Анализируется блоком 56 сигнал на выходе 43 блока 42, Единичное значение сигнала на этом выходе, вырабатываемое при поступлении в блок 42 нулевого сигнала из младшего (правого) разряда регистра 46, соответствует несовпадающему ни с одной из групп столбцу исходного массива или опорному (левому) столбцу группы. В этом случае осуществляется переход к восьмому такту, а при нулевом сигнале на выходе 43 — к десятому такту.

1566411

Восьмой такт, Подается сигнал от блока

56 на вход 3, в результате чего на регистр 8 столбца из накопителя 38 считывается столбец, адрес которого установлен на счетчике 21.

Девятый такт. Подается от блока 56 сигнал на вход 4, в результате чего в накопитель 38 записывается содержимое регистра

8 столбца, адрес которого установлен на счетчике 18, Одновременно подается сигнал на вход 23, в результате чего содержимое счетчика 21 увеличивается на единицу.

Десятый такт. Подаются сигналы на вход 49 регистра 46 сдвига и вход 19 счетчика 18, в результате чего содержимое регистра 46 сдвигается (циклически) вправо на один разряд, а содержимое счетчика 18 увеличивается на единицу.

Одиннадцатый такт. Анализируется блоком 56 сигнал на выходе 26. При единичном значении сигнала на этом выходе, вырабатываемом в случае совпадения содержимого счетчика 18 с содержимым счетчика 21, осуществляется переход к двенадцатому такту, в противном случае — к седьмому такту.

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

Двенадцатый такт. Считывается слово из стека на регистр 37, что производится так же, как и во втором такте. Одновременно от блока 56 подаются сигналы на входы 9 сброса и 20 начальной установки, обнуляющие регистр 8 столбца и счетчик 18.

Тринадцатый такт, Подается от блока 56 сигнал на вход 53 занесения информации, в результате чего на регистр 51 передается из регистра 37 слово, считанное в предыдущем такте.

Четырнадцатый такт. Подается от блока

56 сигнал на вход 17 занесения, в результате чего с выхода приоритетного шифратора 55 в регистр 15 заносится номер самого старшего(левого) разряда регистра 51, содержащего единицу. Одновременно от блока 56 подается сигнал на вход сброса, обнуляющий регистр 37 (вход обнуления регистра 37 не показан), Пятнадцатый такт. Анализируется блоком 56 сигнал на выходе 44 блока 42. Единичное значение сигнала на этом выходе, вырабатываемое при поступлении в блок 42 из младших разрядов регистров 46 и 51 любого сочетания значений, кроме двух единиц, соответствует тем случаям, когда в накопителе 38 отсутствуют группы совпада5

55 ющих столбцов, определяемые анализируемым разрядом считанного в двенадцатом такте слова стека, либо уже восстановленным столбцам, При единичном значении сигнала на выходе 44 осуществляется переход к девятнадцатому такту, иначе — к шестнадцатому, Шестнадцатый такт. Анализируется блоком 56 сигнал на выходе 45 блока 42.

Единичное значение сигнала на этом выходе, вырабатываемое при поступлении в блок

42 единичных сигналов иэ младших разрядов регистров 46 и 51, соответствует тому, что в накопителе 38 имеется группа совпадающих столбцов, определяемая единичными разрядами слова стека, считанного на регистр 51. В таком случае осуществляется переход к семнадцатому такту, в противном случае работа устройства завершается по сбою.

Семнадцатый такт, Подается от блока

56 сигнал на вход 3, в результате чего на регистр 8 столбца из накопителя 38 считывается столбец, адрес которого установлен на регистре 15.

Восемнадцатый такт. Подается от блока

56 сигнал на вход 4, в результате чего в накопитель 38 записывается содержимое регистра 8 столбца в столбец, адрес которого установлен на счетчике 18.

Девятнадцатый такт. Подается от блока

56 сигнал на вход 19, увеличивающий содержимое счетчика 18 на единицу, Одновременно от блока 56 подаются сигналы на входы 49 и 54 сдвига, что вызывает сдвиг содержимого регистров 46 и 51 на один разряд вправо, причем сдвиг в регистре 46— циклический, Двадцатый такт. В случае равенства содержимого счетчика 18 числу разрядов слов накопителя 38 осуществляется переход к двадцать первому такту. В противном случае — к пятнадцатому такту, В результате выполнения двенадцатого — двадцатого тактов в накопителе 38 восстановлены на своих местах столбцы первоначального массива совпадающей группы столбцов, определенной единичными разрядами слова, находящегося на регистре 51.

Двадцать первый такт. Анализируется блоком 56 сигнал на выходе 35 счетчика 31.

Наличие единицы на этом выходе говорит о том, что иэ стека считано последнее слово, что свидетельствует о завершении операции восстановления первоначального вида массива в накопителе 38. В противном случае подается сигнал на вход 33 счетчика 31 и осуществляется переход к двенадцатому такту. Далее двенадцатый — двадцать пер1566411

10 вый такты повторяются до завершения процедуры (т.е. до появления единичного сигнала на выходе 35).

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

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

"Наличие группы единиц в слове массива" блока управления подключен к третьему выходу блока памяти, первый и второй выходы блока управления подключены соответственно к первому и второму входам записисчитывания блока памяти, третий, четвертый и пятый выходы блока управления соединены соответственно с управляющим входом формирователя адреса и суммирующим и вычитающим входами первого счетчика, шестой и седьмой выходы блока управления подключены соответственно к входу занесения и сдвига информации первого регистра сдвига, вход "Граница стека" блока управления подключен к второму выходу первого счетчика, о т л и ч э ющ е е с я тем, что, с целью расширения

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

1566411

Номера разрядод(сталбцоЯ

0бласть хранения массиба

Иласть сгпека Искодиое положеиие указателя стена (блок Л) f Абрес нижней границы массида (блок 27) Фиг. 2

Редактор Н.Тупица

Заказ 1225 Тираж 484 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Q1O0f f

010011

111011

101100

Of0

ffO

101

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

Техред M.Ìîðãåíòàë Корректор М.Самборская