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

.3 л Запоминающе (фиг,1) первый ресные входы 2 устроиство имегистр 1 адрепервый выход т ок ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ П 1 НТ СССР. (46) 07,11.89. Бюл. 9 41 (71) Киевский политехнический и тут им. 50-летия Великой Октябр социалистической революции (72) В.И.Корнейчук, А.П.Марковский, А.Ю.Михайлюк, Е.А,Осадчий и Ф.Ф.Галилейский(56) Авторское свидетельство СССР У 1179429, кл. С 11 С 11/00, 1985.Авторское свидетельство СССР 9 1177856, кл. С 11 С 11/00, 1985. (54) ЗАПОМИНА 1001 ЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано при построении устройств Изобретение относится к вычисли" тельной технике и может быть использовано при построении устройств памяти большого объема. Цель изобретения - повышение информационной емкости устройства.На фиг.1 приведена структурнаясхема запоминающего устройства; нфиг.2 - структурная схема одноговариантов блока управления; на фигблок-схема алгоритма работы блокаравления в режиме считывания; нафиг,4 - 6 - блок-схема алгоритмаботы блока, управления в режиме записи,памяти большого объема. Цель изобретения - повышение информационной емкости устройства. Заломинающее устройство содержит два регистра адреса, адресные входы устройства, блокархива его памяти, два блока сравнения, информационные выходы устройстврегистр слов, блок памяти кодов, регистр кодов, входной регистр, информационные входы устройства, четырекоммутатора, вспомогательный регистррегистр свободной ячейки, счетчик,блок элементов И, сумматор, сдвигающий регистр, входы записи,чтения, установки в исходное состояние и сигнальный, выход переполнения, вход синхронизации устройства.1 табл, 6 ил,4 управления, блок 5 архивной памяти, второй 6 и третий 7 выходы блока управления, первый блок 8 сравнения, первый 9 и второй 1 О входы блока управления, информационные выходы 11, регистр 12 слов, четвертый 13 и пятый 14 выходы блока управления, информационные входы 15 блока 6 памяти кодов, регистр 7 кодов, шестой 18 и седьмой 19 выходы блока управ"ения, второй регистр .20 адреса, . восьмой 21, девятый 22, десятый 23 и одиннадцатый 24 выходы блока управления, входной регистр 25, информационные входы 26, первый 27 коммутатор, двенадцатый выход 28 блока управления, выход 29 блока памяти кодов, второй 30 и третий 3 коммута15205 о откр оизводственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101 Составитель Ю.СычевРедактор О,Головач Техред М,ходанич Корректор И.Пожо Заказ 67 б 4/53 Тираж 558 ПодписноВНИИПИ Государственного комитета по изобретениям113035, Москва, Ж, Раушская н( лиям при ГКНТ СССРторы, вспомогательный регистр 32,четвертый коммутатор ЗЗ, регистр 34свободной ячейки, тринадцатый 35и четырнадцатый 36 выходы блока5управления, счетчик 37, пятнадцатый38, шестнадцатый 39, семнадцатый 40и восемнадцатый 41 выходы блока управления, второй блок 42 сравнения,блок элементов И 43, сумматор 44,сдвигающий регистр 45, девятнадцатый 46, двадцатый 47, двадцать первый 48, двадцать второй 49 и двадцать третий 50 выходы блока управления, третий вход 5 блока управления, входы записи 52, чтения 53 иустановки 54 в исходное состояние,сигнальный вход 55, выход 56 переполнения блока управления и двадцатьчетвертый выход 57 блока управления. 20Блок управления (фиг.2) имеетвход синхронизации 58 устройства,блок 59 постоянной памяти микропрограмм, регистр 60 микрокоманды,счетчик 61 адреса и блок 62 мультиплексоров,Работа устройства основана на том,что каждому запоминаемому слову ставится в соответствие его код, имеющий меньшую разрядность по сравнениюс самим словом. По соответствующемуадресу в блоке 5 архивной памяти вместо слова записывается его более короткий код, что позволяет увеличитьинформационную емкость устройства.Все запоминаемые слова и их кодыхранятся в блоке 16 памяти кодов,ячейка которого в первой группе разрядов хранит одно запоминаемое слово, а во второй группе разрядов - 40соответствующий ему код. При загрузке системы слова (и их коды) размещаются в блоке 16 памяти кодов в порядке возрастания, что позволяет вес" .ти бинарный поиск, Адрес первой незанятой ячейки блока 16 памяти кодовзаносится в регистр 34 свободнойячейки, Если некоторое слово запоминается впервые, то оно заноситсяв блок 16 памяти кодов и снабжаетсякодом, равным среднему арифметическому кодов в соседних ячейках.Устройство работает следующим образом.Для подготовки устройства к работе на вход 54 блока 4 управления по 55дается импульс, устанавливающий егов начальное состояние, После этогона вход 53 (52) блока 4 управления поступает сигнал, переводящий его в режим считывания записи информации, а на адресный вход 2 устройства подается код адреса, по которому информация должна быть считана (записана).При работе блока 4 управления в режиме считывания (фиг.З) каждый блок (кроме проверки условия) описывает состояние выходов блока 4 управления в течение одного тактового периода., С - сигнал на соответствующем входе-выходе. На блок-схемах фиг,З - 6 показаны сигналы, имеющие значения логической "1". Не приведенные в блоках сигналы на протяжении соответствующего тактового периода полагаются равными нулюВ первом тактовом периоде (блок 1, фиг.З) .адрес считываемой информации записывается в регистр 1 (С(3)=) и подается на адресный вход блока 5 памяти, который переведен в режим считывания сигналом с выхода 6 блока 4 управления. Вследствие этого с информационного выхода блока 5 памяти на первый вход блока 8 сравнения поступает код считываемого слова. Выход регистра 12 переведен в высокоомное состояние сигналом С(14)=1, Одновременно с этим происходит обнуление регистра 32 (С(40)=1). Кроме того, с выхода регистра 34 через второй вход коммутатора 33 (так как С(36)=0, в счетчик 37 переписывается (С(38)1) число, являющееся адресом первой свободной ячейки блока 16 памяти, поступающее на второй вход сумматора 44, на первый вход которого подан код числа 9. Код числа Я с выхода сумматора 44 подается на информационный вход регистра 45 и записывается в него вследствие С(47) =1. В следующем такте (блок 2,фиг.З) в регистре 45 по сигналу С(48)=1 данный код сдвигается вправо с потерей младшего разряда и заполнением старшего разряда нулем. Таким образом, на информационный вход регистра 20 поступает код числа- , где квадратные скобки означают целую часть заключенного в них выражения, По .сигналу С(19)1 данный код заносится в регистр 20 и подается на адресныйвход блока 16 памяти, переведенного в режим считывания сигналом С(21) =1. Из15 блока 6 памяти считмнается содержимое ячейки с адресом- , причем записанный в ней код,со второй группы 29 разрядов выходной шины 29 через второй вход коммутатора,27 (так как С(28)=9) проходит на второй вход блока 8 сравнения. Если данный код больше кода, поданного на первый вход блока 8 сравнения, то на первом выходе последнего формируется единица, подаваемая на вход 9 блока 4 управления, Это влечет за собой то, что в следующем тактовом периоде (блок 4, фиг.З) иэ регистра 45 через второй вход коммутатора 31 (С(5=)=9) и первый вход коммутатора 33 (С(36)1) в счетчик 37 записывается (так какн 1С(38) 1) код числа- 1 . В резуль тате на выходе сумматора 44 формируя 1ется код- , , который записывается в регистр 45 (С(47)1).Если имеет место обратное соотношение кодов на входах блока 8 сравнения, то сигнал высокого уровня появляется на втором его выходе и поступает на вход 10 блока 4 управления, В этом случае в следующем тактовом периоде (блок 6, фиг.З) код чи" сла-с выхода коммутатора 31 эа 21писывается в регистр 32 (С(41)1)В результате с выхода сумматора 44 на информационный вход регистра 45 поЗНдается код числа -2 После этого устройство работает аналогично описанному.,В последующем (блок 2, фиг.З) такте код, занесенный в регистр 45, сдвигается вправо и записывается в регистр 20, что вызывает считывание содержимого ячейки блока 16 памяти, имеющей адГЮЧ 3Рес(илиХ ),и т.д. Таким образом осуществляется бинарный поиск в блоке 16 памяти ячейки, содержащей во второй группе своих разрядов код, идентичный считанному из блока 5 памяти. В момент ее нахождения на обоих выходах блока 8 сравнения присутствующее извлеченному из блока 5 памяти коду. После этого (блок 8, фиг.З) с выхода регистра 12 слово проходит на информационный выход 1120592 6запоминающего устройства (С(14) =9) .Блок 4 упранления формирует логике ическую 1 на выходе 55; которая поступает на сигнальный выход 55 устройства, сигнализируя об отработкезаданной операции,Если устройству задан режим записи информации, оно работает следующим образом. По сигналу С(52)= работа блока 4 управления организуется всоответствии с блоком-схемой (фиг.4).В первом тактовом периоде (блок 1,фиг.4) с информационного входа 26устройства в регистр 25 заносится(С(13)=1). Одновременно с адресноговхода 2 в регистр 1 заносится адрес,по которому данное слово должно бытьзаписано. В то же время аналогичным режиму считывания образом в регистр 45 записывается код числа. Вследующем тактовом периоде (блок 2,фиг.4) занесенный в регистр 45 кодсдвигается вправо на один разряд(С(48)1) и переписывается в регистр20 (С(19)=1), в результате чего изблока 16 памяти считывается (С(21)щ 1) содержимое ячейки с адресомс1- ,Кроме того, выход регистра 25переводится в высокоомное состояние(С(24)=1), блок 16 памяти переходитв режим считывания (С(21)1), в результате.чего через первый вход коммутатора 27 (так как С(28)1) навторой вход блока 8 сравнения подает ся содержимое первой группы разрядовсчитываемой из блока 16 памяти ячейки, На первый вход блока 8 сравненияс выхода регистра 12 подается записываемое слово информационный выход 45 блока 5 памяти находится в высокоомном состоянии, так как С 6 9. Далее(блоки 3 - 7, фиг.4) осуществляетсябинарный поиск в блоке 16 памяти ячейки, содержащей в первой группе своих 50 разрядов слово, идентичное записываемому. Работа устройства в данномрежиме аналогична работе блоков 3 -6 режима считывания. Момент нахождения данной ячейки идентифицируется поприсутствию логических нулей на выходах блока 8 сравнения, Это влечет вследующем тактовом периоде (блок 20,фиг.4) перевод блока 5 памяти в режимзаписи (С(7)=1). В результате с вто 1520592рой группы разрядов 29 шины 29 всоответствующую ячейку блока 5 памяти записывается код запоминаемого слова,. Далее (блок 21 фиг.4) блок 4 упуиравления формирует логическую "1" навыходе 55, поступающую на сигнальныйвыход 55 устройства, после чего работа устройства заканчивается.Однако возможен случай, когда вблоке 16 памяти не будет найдена ячейка с запоминаемым словом, что свидетельствует о том. что данное словозапоминается впервые. Тогда на неко 1тором и-шаге бинарного поиска, гдеп (1 оВИ+1 , достигается ситуация,когда в регистре 32 и счетчике 37оказываются коды чисел, отличающихсяна единицу (обозначим их соответственно М и М+1), тогда на выходе сум"матора 44 имеют 2 М+1, а на выходе2 М+1 1сдвигающего регистра 45--2=и+ - 1-м 1+ -1- м+Ф- и. врезультате блок 42 сравнения формирует на своем выходе единицу, посту"лающую на вход 51 блока 4 управления. Поступление данного сигнала свидетельствует о необходимости сдвигасодержимого ячеек блока 16 памяти,имеющих адреса от М+1 до Н, на одну ячейку вперед и записи нового запоминаемого слова в ячейку с адресомМ+1 совместно со сформированным длянего кодом, Вследствие этого в следующем тактовом периоде.(блок 8фиг,4) из регистра 34 через второйвход коммутатора 33 (С(36)9) в счетчик 37 записывается (так как С(38) 1) 40код числа Н, поступающий на второйвход сумматора 44, на первый вход которого подается ноль так как С(57)9 С выхода 46 блока 4 управленияна вход переноса сумматора 44 подает" 45ся единица. В результате в регистр45 записывается (С(47) 1)Я+1. В сле"дующем тактовом периоде (блок 9,фиг.4) это число записывается (С(35)) в регистр 34. Далее (блок 10,фиг,4) содержимое счетчика 37 уменьшается на единицу (С(39)щ 1) и безизменений (С(39) 1) и (С(46,48) 9)записывается в регистр 45 (С(47)щ 1),а затем в регистр 20 (С(19)щ в бло 55ке 12 (фиг.4). Данный адрес подается на адресный вход блока 16 памяти,переведенного в режим считывания сигналом С(21)=1. Из блока 6 памяти считывается содержимое ячейки с данным адресом. С второй группы разрядов 29 щины 29 записанный в данную ячейку код через первый вход коммутатора 30 С(49)=1 поступает в регистр 17 и заносится в него по сигналу С(18)1. Хранящееся в извлекае" мой ячейке слово с первой группы разрядов 29 шины 29 переписывается в регистр 12 (С(13) 1, а выход регистра 25 находится в высокоомном состоянии из-за С(24)1. Далее (блок 13, фиг.4) на вход переноса сумматора 44 подается единица (С(46) 1), благодаря чему в регистр 45 записывается (С(47)1) адрес ячейки блока 16 памяти, следующей за той, содержимое ко" торой находится в регистрах 12 и 17.Далее (блок 14, фиг,4) этот адрес записывается в регистр 20 (С(19)"-1), а затем подается на адресный вход блока 16 памяти, переведенного в режим записи сигналом С(22)1. В результате в соответствующую ячейку записывается содержимое регистров 12 и 17.Циклическая работа блока 4 управления по отработке блоков 10 - 14 (фиг.4) позволяет передвигать содержимое ячеек блока 16 памяти на одну ячейку вперед. Этот процесс повторяется до тех пор, пока после очередно" го уменьшения содержимого счетчика 37 в последнем не окажется число М, В результате коды на входах блока 42 сравнения становятся равными и он по" дает логическую "1" на вход 51 блока 4 управления. После получения данного сигнала (блок 15, фиг,4) из блока16 памяти извлечено (С(21) ),содер" жимое ячейки с адресом М. С второй группы разрядов 291 шины 29 записанный в данной ячейке код через второй вход коммутатора 27 (блок 17,фиг,4) С(28)=9 и первый вход коммутатора 31 (С(50) 1) записывается (С(41)1) в регистр 32. Далее (блок 16,фиг.4) наличие С(46) обеспечивает формирование на выходе сумматора 44 кода числа М+1, который запоминается (С(9)= 1) в регистре 20 (блок 17, фиг.4). В результате из блока 16 памяти считывается содержимое ячейки с данным адресом. Записанный в ней код через второй вход коммутатора .27 (С(28)9), первый вход коммутатора 31(С(50)1) и первый вход коммутатора 33 (С(36), 1) переписывается (С(38)щ 1) в счетчик 37 и подается на вто5 20 30 9 152рой вход сумматора 44, на первый входкоторого поступает содержимое регистра 32 (так как С(57)1), В результате в регистр 45 записывается(С(47)=1) сумма кодов, хранящихся вячейках блока 16 памяти с адресами Ми И+1. Далее (блок 18, фиг.4) сигнал(С(48)=1) обеспечивает сдвиг этойсуммы на один разряд вправо. Полученное среднее арифметическое кодовчерез второй вход коммутатора 30С(49)=9 записывается в регистр 17(С(18)1) и с его выхода поступаетна вторую группу разрядов 15 информационного входа 15 блока 16 памяти,находящегося в режиме записи С(22)=1в блоке 21 (фиг.4). На первую группу 15 разрядов информационного входа 15 блока 16 памяти через регистр12 С(13)1, С(14)=9 с выхода регистра 25 подается запоминаемое слово. Врезультате в ячейку блока 16 памятис адресом И+1 записывается запоминаемое слово с его кодом, После этого(блок 20, фиг.4) блок 16 памяти переводится в режим чтения С(21)=1 и устройство работает аналогично описанномуВозможен вариант, когда коды, хранящиеся в ячейках блока 16 памяти садресами И и М+1, различаются всегона единицу. Тогда после вычислениясреднего арифметического данных кодов (блок 19, фиг.4 ) вследствие потери дробной части при сдвиге имеетместо равенство кодов на входах блока 42 сравненияПо формируемому наего выходе сигналу С(51)=1 блок 4управления формирует (блок 25, Фиг.4)на своем выходе 56 единицу, поступа"ющую на выход 56 переполнения устройства, Этот сигнал вызывает переэагрузку системы с перераспределениемкодов для обеспечения необходимыхинтервалов между соседними в блоке16 памяти кодов кодами.Работа запоминающего устройствав режиме записи, Пусть в запоми-.нающем устройстве записываются двоичные 20-разрядные слова из набора,приведенные в таблице,Каждое слово снабжено 6-разрядным кодом. Данная таблица при загрузке заносится в первые 10 ячеек блока 16 памяти кодов. При записи слова 0000000000010011111 в процессе би-нарного поиска выясняется, что дан 0592 Оное слово записано в первой групперазрядов второй ячейки блока 16 памяти кодов. Тогда из второй группы разрядов данной ячейки считывается соответствующий код 00000 и записывается в блок 5 архивной памяти позаданному адресу.Рассмотрим случай, когда слово запоминается впервые, Пусть идет записьслова 00000000010000000001. После окончания поиска выясняется, что такого слова в блоке 16 памяти кодовнет. Поскольку значение данного слова больше значения слова, записанного в четвертой ячейке, и меньше,расположенного в пятой, данное словодолжно быть записано в блок 16 памяти кодов между этими словами. Для этого содержимое 5-1 - 1 О-й ячеек блока 16 передвигается на одну ячейку вперед, а записываемое словЬ заноситсяв 5-ю ячейку. В соответствие ему становится код, равный среднему арифметическому кодов соседних слов, аименно 010010. Данный код запоминается во второй группе разрядов четвертой ячейки, а также в блоке 5 архивной памяти по заданному адресу. Формула изобретения Запоминающее устройство, содер"жащее входной регистр, первый регистрадреса, первый и второй блоки сравнения, счетчик, информационные входывходного регистра являются информационными входами устройства, о т -л и ч а ю щ е е с я тем, что, с 40 целью повышения информационной ем"кости устройства, в него введены сумматор, первый - четвертый коммутато-:ры, блок управления, блок памяти кодов, блок архивной памяти, второйрегистр адреса, регистр свободной ячейки, вспомогательныйрегистр, сдвигающий регистр, регистр кодов, регистр слов и блок элементов И, адресные входы блока ар хивной памяти соединены с выходамипервого регистра адреса, информационные входы которого являются адресными входами устройства; первый и второй выходы первого блока сравнениясоединены с первым и вторым входамизадания режима блока управления, выходы блока архивной памяти соединеныс входами первой группы первого блока сравнения, выходами регистра слов,0592 12 10 20 25 30 35 40 45 50 15152 информационными входами первой группы блока памяти кодов и являются информационными выходами устройства, выходы регистра кодов соединены с информационными входами второй группы блока памяти кодов, адресные входы которого соединены с выходами второго регистра адреса, информационные входы которого соединены с выходами сдвигающего регистра, входами первой группы второго блока сравнения, информационными входами первой группы второго и третьего коммутаторов, информационные входы второй группы которого соединены с выходами первого коммутатора и входами второй группы первого блока сравнения, выходы входного регистра. соединены с соответствующими информационными входами регистра слов, выходами первой группы блоха памяти кодов и информационными входами первой группь 1 первого коммутатора, информационные входы второй группы которого соединены с соответствующими выходами второй группы блока памяти кодов, информационными входами блока архивной памяти и информационными входами второй группы второго коммутатора, выходы которого соединены с входами регистра кодов, информационные входы сдвигающего регистра соединены с выходами сумматора входы первой группы которого соединены с соответствующими выходами счетчика, входы второй группы сумматора соединены с выходами блокаэлементов И, первые входы которого соединены с выходами вспомогательного регистра и входами второй группы второго блока сравнения, выходы третьего коммутатора соединены с информационными входами вспомогательного регистра и регистра свободной ячейки и информационными входами первой группы четвертого коммутатора, информационными входами первой группы четвертого коммутатора, информационные входы второй группы которого соединены с выходами регистра свободной ячейки, выходы четвертого коммутатора соединены с информационными входами счетчика, выход второго блока сравнения соединен с третьим входом задания режима блока управления, входы записи и чтения которого являются соответствующими входами устройства, вход установки в исходное состояние и вход синхронизации блокауправления являются соответствующимивходами устройства, первый выход блока управления соединен с входом синхронизации первого регистра, второйи третий. выходы - соответственно свходами чтения и записи блока архивной памяти, четвертый и пятый выходы - соответственно с входом синхронизации и задания режима регистраслов, шестой выход - с входом синхронизации регистра кодов, седьмой выход - с входом синхронизации второгорегистра адреса, восьмой и девятыйвыходы- соответственно с входамичтения и записи блока кодов, десятыйи одиннадцатый выходы соответственнос входами синхронизации и задания режима входного регистра, двенадцатыйвыход - с входом управления первогокоммутатора, тринадцатый выход - свходом синхронизации регистра сво"бодной зоны, четырнадцатый выход - свходом управления четвертого коммутатора, пятнадцатый и шестнадцатыйвыходы - соответственно,.с входаминачальной установки синхронизациисчетчика, семнадцатый и восемнадцатыйвыходы - соответственно с входом установки в начальное состояние и синхронизации вспомогательного регистра,девятнадцатый выход - с входом сум"матора, двадцатый и двадцать первыйвыходы " соответственно с входамисинхронизации и сдвига сдвигающегорегистра, двадцать второй выход - свходом управления второго коммутато"ра, двадцать третий выход - с входомуправления третьего коммутатора,двадцать четвертый и двадцать пятый выходы являются соответственно первым ивторым выходами контроля работы устройства, двадцать шестой выход блокауправления соединен с вторыми входами блока элементов И.