Запоминающее устройство Советский патент 1982 года по МПК G11C11/00 

(54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

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

Решение задачи подсчета количества чисел, укладывающихся в заданные диапазоны с помощью известных ЗУ, либо невозможно, либо требует много времени.

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

Известное ЗУ нельзя использовать для подсчета количества чисел, которые указываются в каходом из 2 диапазонов, длиной L, где m и L - це.пые положительные числа, причем .т является степенью числа 2. Значения чисел, подлежащих подсчету, могут 3aKJna4aTbся в интервале от О до 2-1 включительно, где k - некоторое целое положительное число, не превышающее разрядности ячейки блока памяти. Если задано количество диапазонов 2-, то длина определяется из соотношения

L 2 .

Если же задана длина L, то количество диапазонов определяется .

-. . L

Цель изобретения - повышение быстродействия устройства.

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

25 сдвига, другие - с соответствующими выходами регистра адреса, а выходы коммутатора адреса соединены с адресными входами блока памяти, выходы выходного . регистра соединены со в.чо30дами входного регистра. На чертеже представлена блок-схем предлагаемого устройства. Устройство содержит регистр 1 адреса представляющий собой регистрсчетчик }РСА), входной регистр 2, также,представляющий собой регистрсчетчик (ВРС), коммутатор адреса (КА 3, блок памяти (БП) 4, выходной регистр (ВР) 5 и регистр сдвига (PC) Работа устройства в режиме подсче та чисел Основана на простой аналитической зависимости между величиной числа и номером ячейки, соответствукицей данному диапазону значений чил сел. В разрядном 3V обрабатывается массив чисел, максимальное из которых может иметь значение - 1,где k 1, 2п. При этом может быть 2 диапазонов (,12,...k). Перед работой устройства должна быть з.адана разрядность k максимального числа и параметр т, определяющий количество и-дл,ину диапазонов. В ячейках с нулевой по 2 - 1 включительно, вьаделенных для подсчета чисел, распределяемых по диапазонам, должны быть 3c писаны нули. Обрабатываемый массив чисел должен храниться в последних ячейках БП, начальный адрес записывается в РСА. Устройство работает следующим об разом. На. управляющий вхол КА 3 подается управляющий сигнал, обеспечивающий передачу адреса с tCA 1 через КА 3 на адресные входы БП 4, и производится считывание анализируемого числа массива в ВР 5. На выходах PC 6 вырабатывается код, представляющий

Анализируемое число Адрес ячейки диапазона (содержимое ячейки БП) (содержимое ВР)

01101011 00110100 OlOOOOOO 00000111

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

00000110 00000011 OOOOOIOO 00000000

задачи для N исходных чисел можно оценить по формуле

t 3tj. N.

где - время обращения к ЗУ.

При исполнении известных ЗУ для определения.диапазона, к которому относится анализируемое число, необходимо хранить граничные значения

диапазонов и последовательно сравнивать с ними анализируемое число. Если задано q диапазонов, то в среднем потребуется q/2 таких сравнений. Тогда для определения диапазона потребуется (3-f) обращений к ЗУ: чтение собой сдвинутый на k-m разрядов в сторону младших разрядов код, поступающий с ВР 5. этот код является адресом ячейки соответствующего диапазона в БП 4. На управляющий вход КА 3 подается управляющий сигнал, об,еспечивающий передачу годреса с PC 6 че рез КА 3 на адресные входы БП 4.Производится считывание в ВР 5 кода, отражающего текущее количество анализируемых чисел., попадающих в данный диапазон. Код с ВР 5 пересвшается в ВРС. 2 и производится увеличение содержимого ВРС 2 на единицу. Производится запись содержимого ВРС 2 и БП 4 по адресу, находящемуся в PC 6. Содержимое РСА 1 увеличивается на единицу. Таким образом формируется адрес следующего числа массива. Производится проверка на наличие ,единицы переноса из старшего разряда РСА 1. Если перенос отсутствует (проанализированы не все числа массива), то снова выполняется пункт 1. Наличие единицы переноса свидетельствует об окончании работы устройства в данн ом режиме. ЗУ может работать и в обычных режимах. Для этого выходы РСА 1 подключаются через КА 3 к адресным входам БП 4. Тагда РСА 1 служит для задания адреса. Записываемый код подается на ВРС 3, а считываемый снимается с ВР 5. Пример, иллюстрирующий определение адреса ячейки диапазона, исходя из значения числа для случая , k-7, , показан ниже. анализируемого числа, чтение верхнего значения первого диапазона, чтение верхнего значения второго диапазона и т.п., (до тех пор, пока анализируемое число не окажется меньше верхнего значения соответствуклчего диапазона), чтение ячейки соответствующего диапазона, запись увеличенного содержимого яче{1ки диапазона. Среднее время решения задачи с помощью известных ЗУ можно оценить по формуле t Cl3+|) N Тогда сокращение времени решения задачи, достигаемое от применения пред лагаемого ЗУ определяется следующим образом: в Если число диапазонов лежит в пределах от 4 до 32, время решения задачи сократиться в 1,7+6,3 раз. Предлагаемое у 1тройство с наиболь шим эффектом может быть использовано в системах обработки изобретений (для решений задачи распределения точек изобретения по диапазонам яркости) , а также в различных информационно-логических системах. Формула изобретения Запоминающее устройство, содержащее блок памяти, адресные входы которого соединены с выходами регистра адреса, информационные входы - с выходами входного регистра, а информационные выходы - с входами выходного регистра, отличающееся тем, что, с целью по1зышемия быстродействия устройства, оно содержит регистр сдвига, входы которого соединены с выходами выходного регистра, коммутатор адреса, одни входы котоjporo соединены с соответствующими выходами регистра сдвига, другие - с соответствующими выходами регистра адреса, а выходы кок утатора адреса соединены с адресными входами блока памяти, выходы выходного регистра соединены с входами входного регистра, Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СС.СР 650103, кл. G 11 С 11/00, 1974. 2.Авторское свидетельство СССР 691925, кл. G 11 С 11/00, 1976 (прототип).