Устройство для построения гистограммы

 

Устройство относится к автоматике и вычислительной технике, в частности к устройствам статистической обработки информации . Цель изобретения - повышение быстродействия. Устройство содержит блоки 1,2 ассоциативной памяти, элемент ИЛИ 3, шифраторы 4, 12, мультиплексоры 5. 13, счетчики 6, 10, элемент ИЛИ 11, блок 15 памяти, регистр 17, блок 18 элементов И, индексный регистр 19. регистр 20 маски, блок 21 управления. 4 ил.

союз советских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (яцек G 06 F 15/36

ГосудАРственный кОмитет

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

ПРИ ГКНТ СССР

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

° °

V) фь . о бд

СО

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4622465/24 (22) 20.12.88 (46) 07.07.92. Бюл. hL 25 . (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической.революции (72) B.È,Êàðíåé÷óê, А.П,Марковский, Е.АМаслянчук и А.Н.Скильсара (53) 681.3(088.8) (56) Авторское свидетельство СССР

hb 1388901, кл. G 06 F 15/36, 1988 (прототип).

l,» SU 1746387A1 (54) УСТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ.ГИСТОГРАММЫ (57) Устройство относится к автоматике и вычислительной технике. в частности к устройствам статистической обработки информации. Цель изобретения — повЬ|шение быстродействия. Устройство содержит блоки 1, 2 ассоциативной памяти, элемент ИЛИ

3, шифраторы 4, 12, мультиплексоры 5, 13, счетчики 6, 10, элемент ИЛИ 11, блок 15 памяти, регистр 17, блок 18 элементов И, :индексный регистр 19. регистр 20 маски, блок 21 управления. 4 ил.

1746387

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

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

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

Устройство для построения гистограммы содержит два блока 1, 2 ассоциативной. памяти, элемент ИЛИ 3, шифратор 4, мультиплексор 5, счетчик 6, адресный вход 7, блок 8 памяти, информационный выход 9 устройства, счетчик 10, элемент ИЛИ 11, шифратор 12, мультиплексор 13, счетчик 14, блок 15 памяти. информационный вход 16 устройства, регистр 17, блок 18 элементов

И, индексный регистр 19, регистр 20 маски, блок 21 управления, вход сброса устройства

22, тактовый вход устройства 23, входы задания режима работы блока управления 24—

26, выходы блока управления 27 — 41.

Выход блока 1 ассоциативной памяти подключен к входам многовходового элемента ИЛИ 3 и шифратора 4, выходами связанного с первыми входами . мультиплексора 5, выходы которого соединены с входами установки счетчика 6 адреса, выходы которого являются выходами номера интервала гистограммы устройства, а, кроме того, подключены к адресным входам блока 8 памяти, информационный выход которого является информационным выходом 9 устройства и подсоединен к входам установки счетчика 10, информационными выходами связанного . с информационными входами блока 8 памяти, шины поиска. блока 2 ассоциативной памяти соединены с входами многовходового элемента ИЛИ 11 и входами шифратора 12, выходы которого связаны с вторыми входами мультиплексора 13, первые входы которого, как и адресные входы блока 2 ассоциативной памяти соединеныс выходами счетчика 14 адреса, выход которого подключен к адресным входам блока 15 памяти,, информационные входы которого связаны с выходами приоритетного шифратора 4, а выходы подсоединены к вторым входам мультиплексора 5, информационные входы

16 устройства связаны с входами установки регистра 17 приема кода. выходы которого соединены с информационными входами и входами признака опроса блока 2 ассоциативной памяти, первыми входами блока 18 элементов И, вторые входы которого являются выходами индексного регистра 19, выходы которого соединены с входами признака опроса блока 1 ассоциативной памяти, входы маскирования которого подключены к выходам регистра 20 маски, Кроме того. устройство содержит. блок 21 управления, вход 22 которого является командным входом начальной установки устройства, а вход 23 является запускающим входом устройства, третий вход 24 подсоединен к выходу многовходового элемента

ИЛИ 3, вход 25 связан с выходом многовходового элемента ИЛИ 11. а вход 26 подключен к выходу переполнения счетчика 6 адреса, выход 27 блока 21 управления подсоединен к входу управления приемом кода регистра 17 приема кода, входу установки в нуль регистра 20 маски, входу установки в единицу всех разрядов индексного регистра

19, выход 28 блока 21 управления связан с входами установки в нуль всех разрядов регистра 17 приема кода,, счетчика 10, первого

6 и второго 2 счетчиков адреса, входами маскирования блока 2 ассоциативной памяти, выход 29 блока 21 управления подключен к входу управления сдвигом регистра 20 управления соединен с входом управления записью по адресу блока 2 ассоциативной памяти, входом управления записью блока

15 памяти, выход 32 связан с входом управ30 ления приемом кода счетчика 6 адреса, выход 33 блока 21 управления подключен к входу управления ассоциативным опросом блока 2 ассоциативной памяти, входу управления считыванием блока 15 памяти. входу управления мультиплексорами 5 и 13, выход

34 является входом управления сдвигом индексного регистра 19, выход 35 подсоединен к счетному входу счетчика 10, выход 36 связан с входом управления записью блока

8 памяти. выход 37 блока 21 управления подключен к входу управления ассоциативной записью блока 2 ассоциативной памяти, а входы 38 и 39 являются счетными входами соответственно счетчиков 6 и 14 адреса, выход 40 блока 21 управления соединен с входом управления .считыванием блока 8 памяти и входом управления приемом кода

50 .счетчика.10, а выход 41 является сигнальным выходом устройства, Блок управления в устройстве выполнен в виде микропрограммного управляю щего устройства.

Перед построением гистограммы яркостей полутонового йзображения, по сигна55 лу, подаваемому на вход 22 устройства производится начальная установка устройства, Алгоритм, в соответствии с которым блок 21 управления осуществляет выдачу

25 маски, а выход 30 является входом управления ассоциативным опросом. блока 1 ассоциативной памяти, выход 31 блока 21

1746387 управляющих сигналов, представлен на устанавливаются в единицу, Соответственфиг,2.Блок21управленияформируетсигна- но, код с регистра 17 подается на входы лы единичного уровня на выходах 28. 33 по признака опроса блоков 1, 2 ассоциативной которым все разряды регистра 17 устанав- памяти, В следующем такте сигналом с выливаются в нуль, равно как и все разряды 5 ходов 30, 39 блока 21 управления инициирусчетчиков 6, 10, 13 на все разряды маскиро- ется ассоциативный опрос блоков вания блока 2 подаются единичные потен- ассоциативной памяти содержимым регистциалы (соответствует замаскированному ра 17(на входы маскирования блока 2 подасостоянию всех разрядов признака опроса), ется нулевой потенциал с выхода 28 блока

Одновременно выполняется ассоциатив- 10 21 управления, что соответствует отсутстный опрос блока 2 ассоциативной памяти, вию маскирования). В случае, если в блоке 2

Поскольку все разряды замаскированы, то ассоциативной памяти содержатся слова, сигнал совпадения формируется на всех совпадающие с поступившим на вход16 кошинах поиска. В следующем тактесигналом дом, то будет сформирован единичный сигс выхода 37.блок 21 управления инициирует 15 нал на соответствующей шине поиска, и ассоциативную запись нулевого кода из ре- соответственно, на выходе многовходового гистра 17 в.ячейки, на которых зафиксиро- элемента ИЛИ 11. Упомянутый сигнал пованы совпадения в предшествующем такте ступает на вход 25 блока 21 управления. ассоциативного опроса. Если код с регистра 17 совпадает с одним из

Таким образом обнуляется содержимое 20 слов. хранящихся в блоке 1 ассоциативной всех ячеек блока ассоциативной памяти. Од- памяти, то единичный сигнал будет сформиновременно, сигналом с выхода 36 блока 21 рован на входе 24 блока 21 управления. управления обнуляется (кодом со счетчика Суть реализуемой в последующих так10) содержимое нулевой ячейки(на счетчике тах процедуры состоит в следующем. В бло6 зафиксирован нулевой код) блока 8 памя- 25 ке 1 ассоциативной памяти множество X ти. Затем сигналом с выхода 38 блока 21 чисел, составляющих границы интервалов управления содержимое первого счетчика 6 гистограммы, а в соответствующих ячейках адреса увеличивается на единицу, если при блока 8 памяти значения количества кодов, этом, последний не формирует сигнала пе- попадающих в соответствующий интервал, реполнения, который поступает на вход 26 30 в блоке 2 ассоциативной памяти xpBHNTGA блока 21 управления, то обнуляется содер- множество У, которое совпадает или являжимое очередной ячейки блока 8 памяти ется подмножеством множества R, обрабо(содержимое ячеек блока 2 ассоциативной танных к текущему моменту кодов памяти при этом остается обнуленным), По- измерений (точек изображений), т.е, Y R, сле обнуления всех ячеек блока 8 памяти 35 а в одноименных ячейках второго блока 15 счетчик 6 адреса формирует сигнал пере- памяти хранится ссылка на номер (адрес в полнения, который поступает на вход 26 блоке 8 памяти) интервала, в который попаблока 21 управления, который под действи- дает соответствующий код из множества Y. ем укаэанного сигнала формирует на выхо- Если считанный на регистре 17 код очередде 41 сигнал готовности устройства к 40 ного измерения (точки изобретения) совпаприему кода яркости первой точки изобра- дает с одним из кодов множества У, то номер интервала, в который попадает код

В режиме построения гистрограммы на регистре17 определяется кодом на выхокод очередного числа поступает на инфор- де блока 15 памяти, который в этом случае, мационные входы 16 устройства одновре- 45 адресуется номером шины поиска блока 2, менно с подачей сигнала на вход 23 на которой сформировался сигнал совпадеустройства, по последнему, блоком 21 уп- ния. Если код на регистре 17 не совпадает равления формируется последовательность ни с одним элементом множества У, выполвыдачи управляющих сигналов в соответст- няется цикл огределения интервала, заклю-вии с алгоритмом. представленным на чающего код Z на регистре 17. В указанном

50 цикле отыскивается среди множества граОбработка кода очередного числа (ярко- ниц интервалов подмножество Q J QCX) чиссти) начинается выдачей блоком 21 управле- ла таких, что каждое из них q О меньше ния единичного сигнала на выходе 27, под (qCZ), причем множество Q обязательно управлением которого поступающий код с включает число, ближайшее меньшее к Z, входов 16 записывается на регистр 17 при- 55 среди чисел, составляющих множество. Поема кода, все разряды регистра 20 маски сколькумножество0, выделяемое из шин устанавливаются в нуль (соответствует не- поиска блока 1 ассоциативной памяти, упозамаскированному состоянию всех разря- рядочено (в силу тсго, что упорядочено при дов) все разряды индексного регистра 19

1746387 записи в блок 1 множество Х}, то первым на множестве (т.е. в ячейке с минимальным адресом) выделяется приоритетным шифратором 4, число. ближайшее к Z, Код на выходе приоритетного шифратора 5 определяет номер интервала, заключающего код Z, Код

Z и соответствующий ему номер интервала записываются соответственно в блок 2 ассоциативной памяти в блок 15 памяти. Если

YC R, Уф Я, то возможна ситуация, когда код

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

Описание операции осуществляется следующим образом. Если после опроса обоих блоков 1, 2 ассоциативной памяти (блок 2 алгоритма на фиг.3) сигнал на входе

25 блока 21 соответствует единице, то блоком 21 управления формируется единичный потенциал на выходах 33 и 32, по первому из которых осуществляется опрос блока 2 ассоциативной памяти, на одной из шин которого формируется сигнал совпадения, который преобразуется шифратором 12 в код адреса, который поступает, через открытый единичным сигналом с выхода 33 мультиплексор 13, на адресные входы блока 15 памяти, на выходах которого под действием сигнала считывания с выхода 33формируется код номера интервала, заключающий код с регистра 17 и идентичный ему код, среди хранящихся в блоке 2 ассоциативной памяти. Упомянутый код с выходов блока 15 памяти через открытый единичным сигналом с выхода 33 мультиплексор 5 поступает на входы счетчика 6 адреса и фиксируется под действием. сигнала с выхода 32 блока 21 управления. В следующем такте (блок 11 алгоритма на фиг.2) сигналом с выхода 40 блок 21 управления инициирует считывание на счетчик 10 кода количества измерений, попавших в интервал, номер которого зафиксирован на счетчике 6. В дальнейшем, сигналом с выхода 35 производится увеличение на единицу содержимого счетчика 10.

В заключительном такте (блок 9 алгоритма на фиг.3) выполняется, по сигналу с выхода

36, занесение скорректированного описанным способом числа попаданий в интервал в блок 8 памяти. Одновременно блок 21 управления формирует на выходе 41 устройства сигнал готовности к приему очередного кода.

Если после опроса блоков 1 и 2 ассоциативной памяти на вход 25 блока 21 управления поступит нулевой сигнал, то анализируется сигнал на входе 24: если он соответствует единичному потенциалу (т.е на регистре 17 совпадает с одной иэ границ пределов гистограммы), то сигналом с выхода 30 блока 21 управления повторяется опрос блока 1 ассоциативной памяти, при этом на выходе приоритетного шифратора 4 формируется номер интервала, в котором заключена упомянутая граница. Код номера интервала через открытый нулевым потен10 циалом с выхода 33 мультиплексор 5 поступает на входы счетчика 6, на котором фиксируется под действием сигнала с выхода 32 блока 21 управления (блок 12 алгоритма на фиг.3). В дальнейшем осуществляется

15 описанная последовательность коррекции содержимого блока 8 памяти.

Если после опроса блоков 1 и 2 ассоциативной,памяти на входы 24, 25 блока 21 управления поступят нулевые сигналы, то

20 последним выдается сигнал с выхода 34, которым инициируется сдвиг содержимого индексного регистра 19 на один разряд влево (в сторону старших разрядов) с заполнением освободившегося разряда нулем. В

25 следующем такте (блок 3 алгоритма на фиг.3) сигналом с выхода 30 блока 21 управления осуществляется опрос блока 1 ассоциативной памяти немаскируемым числом с регистра 17 с нулевым младшим разрядом, 30 т.е. выявляется наличие в множестве Х числа, совпадающего с Z в (и-1) старших разрядов и меньшего Z (n — разрядность обрабатываемых кодов), Если такое число не найдено, то на входе 24 блока 21 управ35 ления присутствует нулевой сигнал, по которому блок 21 управления формирует сигналы на выходах 29.и.30, которыми инициируется сдвиг влево соответственно содержимого регистра 20 маски (с

40 заполнением освободившегося разряда единицей) и.индексного регистра 19 (с заполнением освободившегося разряда нулем). Вновь производится опрос блока 1 ассоциативной памяти на предмет наличия

45 слов, совпадающих (n-2) старшими разрядами с кодом на регистре 17 и меньших указанного кода (n-2) старших разряда признака опроса совпадают с соответствующими разрядами кода на регистре 17, (n50 1)-й разряд признака опроса равен нулю, так как нуль хранится после двух сдвигов в (n-1)-м разряде регистра 19, и-й (младший разряд признака опроса маскируется единицей в соответствующем разряде регистра

55 20 маски). Если таких чисел нет, то.описанная йроцедура модификации признака onроса повторяется до тех пор, пока в результате опроса блока 1 ассоциативной памяти не будет выявлено наличие совпадений, отмечающих множество Q, и, соответ1746387

10 ственно, не будет сформирован единичный сигнал на входе 24 блока 21 управления, который инициирует выдачу последним сигналом на выходах 30 — 32 (блок 6 алгоритма на фиг,3), под управлением первого из которых производится повторный опрос блока 1 ассоциативной памяти, при этом на шинах поиска блока 1 формируется сигнал, отличающий множество Q. Приоритетным шифра. тором 4 выделяется элемент множества Q c минимальным номером, код которого через открытый нулевым потенциалом с выхода 33 мультиплексора 5 поступает на вход счетчика 6 адреса, на котором фиксируется под действием сигнала с выхода 32. Кроме того, код номера интервала, включающего код на регистре 17, поступает на информационные входы второго блока 15 памяти, адресуемого, как и блок 2 ассоциативной памяти кодом, зафиксированным на счетчике 4 адреса, В этом же такте под действием сигнала с выхода 31 производится запись кода регистра 17 в одну из ячеек блока 2 ассоциативной памяти и запись соответствующего номера интервала в одноименную ячейку блока памяти. В следующем такте сигналом с выхода 39 блок 21 управления инициирует прибавление единицы к содержимому счетчика 14 адреса, а также сигналом выхода 40 — считывание содержимого ячейки блока 8 памяти, адресуемой содержимым счетчика

6 адреса, в счетчик 10. Далее производится описанный цикл коррекции содержимого блока 8 памяти.

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

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

ИЛИ, выход. первого счетчика соединен с адресным входом первого блока памяти, выход которого соединен с информационным входом второго счетчика, выход которого соединен с информационным входом первого блока памяти, первый выход блока микропрограммного управления соединен с тактовым входом регистра, второй выход блока микропрограммного управления соединен с входом сдвига индексного регистра.

5 третий выход блока микропрограммного управления соединен. с входом сброса первого счетчика, четвертый выход блока микропрограммного управления соединен с тактовым входом первого счетчика, пятый

10 выход блока микропрограммного управления соединен со счетным входом первого счетчика, шестой выход блока микропрограммного управления соединен со счетным входом первого счетчика, шестой выход бло15 ка микропрограммного управления соединен со счетным входом второго счетчика, седьмой выход блока микропрограммного управления соединен с тактовым входом второго счетчика и входом считывания пср-.

20 ваго блока памяти, восьмой выход блока микропрограммного управления соединен с входом записи первого блока памяти, девятый выход блока микропрограммного управления соединен с входом опроса первого

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

45 тора соединен с первым информационным входом второго мультиплексора, выход которого соединен с адресным входом второго блока памяти, информацион«ый вход которого соединен с выходом первого шиф50 ратора. второй информационный вход BTQрого мультиплексора соединен с информационным выходом второго счетчика и адресным входом второго блока ассоциативной памяти, информационный выход

55 регистра соединен с информационным Вхо дом и входом опроса второго блока ассоциативной памяти, первый выход блока микропрограммного управления соединен с входом сброса регистра маски и входом установки индексного регистра, третий выход

1746387

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

10 входом логических условий блока микропрограммного устройства.

1746387

Редактор H.Õèì÷óê

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

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

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

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

Составитель Д.Ухтверов

Техред М.Моргентал

Корректор А.Осауленко