Логическое запоминающее устройство Советский патент 1990 года по МПК G11C15/00 

Т |, r«u I « J § |

|ДмЬлс ptmvn

0uil

0uil

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

Изобретение относится к вычислительной технике и может быть использовано в системах сложной логической обработки информации. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения считывания первоначальной формы массива информации, записанного в сжатой форме. Устройство содержит блок 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 ил.

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

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

На фиг.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 занесения и входом 54 сдвига, приоритетный шифратор 55, блок 56 управления.

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

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

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

причем n-разрядность хранимых в накопителе слов (строк), т.е. число столбцов.

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

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

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

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

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

Соответствующее этому размещение информации в накопителе 38 показано на

фиг.2в. Первые слов накопителя занимает уплотненный массив, причем содержимое столбцов с номерами 0, 1 и 2 (нумерация начинается с нуля и идет справа налево) безразлично. Четыре последних

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

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

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

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

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

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

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

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

0 результате чего в нем устанавливается код адреса слова, записанного в стек последним (так как после окончания операции уплотнения массива информации в счетчике 31 установлен код адреса, следующего за

5 адресом последнего записанного в стек слова).

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

Третий такт. Подается сигнал от блока 56 на вход 48 занесения информации, что

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

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

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

5 том, что из стека считано последнее слово. В этом случае осуществляется переход к шестому такту, в противном случае - к первому.

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

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

0

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

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

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

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

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

В результате выполнения шестого- одиннадцатого тактов в накопителе 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 отсутствуют группы совпадающих столбцов, определяемые анализируемым разрядом считанного в двенадцатом такте слова стека, либо уже восстановленным столбцам. При единичном значении

сигнала на выходе 44 осуществляется переход к девятнадцатому такту, иначе -к шестнадцатому.

Шестнадцатый такт. Анализируется блоком 56 сигнал на выходе 45 блока 42.

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

0 сбою.

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

5 на регистре 15.

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

Девятнадцатый такт. Подается от блока 56 сигнал на вход 19, увеличивающий содержимое счетчика 18 на единицу. Одновременно от блока 56 подаются сигналы на

5 входы 49 и 54 сдвига, что вызывает сдвиг содержимого регистров 46 и 51 на один разряд вправо, причем сдвиг в регистре 46 - циклический.

Двадцатый такт. В случае равенства со0 держимого счетчика 18 числу разрядов слов накопителя 38 осуществляется переход к двадцать первому такту. В противном случае - к пятнадцатому такту.

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

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

5 том, что из стека считано последнее слово, что свидетельствует о завершении операции восстановления первоначального вида массива в накопителе 38. В противном случае подается сигнал на вход 33 счетчика 31 и осуществляется переход к двенадцатому такту. Далее двенадцатый - двадцать первый такты повторяются до завершения процедуры (т.е. до появления единичного сигнала на выходе 35).

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

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

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

Atipec нижней границы массива (блок 27)

100

ою

010 110 101

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

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

Область стека

- Исходное положение указателя стека (блок 31)

Фиг. 2