Запоминающее устройство с многоформатным доступом к данным

. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ 4 11 С 11/34 Х.,ИЯ ",.": - / Гй - ГУ-:.: Я 13 Г,Ф(72) В.В. Каверэнев и Е.АМетлиц- тем, что, с целью расширения облас- .кий . : , . : ти применения за счет обеспечения,(71) Ленинградский ордена Ленина , воэможности обращения к квадратнымэлектротехнический институт фрагментам данных, в него введеныим, В.н Ульянова (ленина) .элемент и, блок мультиплексоров ко(53).681.327,66(088. 8) .да адреса и второй блок мультиплек(56) 1. Патент Франции В 2369650, .соров данных, причем вход элемента ., кл. С И С 11/34, 1978.И соединен с выходом регистра типа2. Патент СЮА Р 3800.289, . обращений, а ее выход - с управляюкл. 340-.1725, 1974 (прототип). , щим входом блока мультиплексоров54.)(57). ЗАПОМИНАЮЩЕЕ. УСТРОЙСТВО С . кода адреса и управляющим входомИНОГОФОРМАТНЫМ ДОСТУПОМ К ДАННЫМ, второго блока мультиплексоров дан.содержащее регистр. типа. обращений, ных, вход блока мультиплексоров корегистр адреса, сумматор по модулю , да адреса подключен к выходу регистдва,. блок мультиплексоров данных, , .ра адреса, а его выход соединен срегистр данных и блок памяти., причем.:- вторым адресным входом блока памявыход регистра типа обращений сое-ти и вторым входом сумматора подинен с одним иэ входов, сумматорамодулю два, вход второго блока мупо модулю два, выход которогО соеди:, льтиплексоров данных подключен кнен с первым адресным входом блока : : информационному выходу блока папамяти, выход регистра адреса соети, а его выход - к входу перводинеи с управляющим входом блока . блока мультиплексоров данных. мя- С 2го,Изобретение относится к вычислительной технике, а именно к разделу запоминающих устройств, которые могут использоваться в специализированных системах хранения и и цифровой обработки изображений, а также в ассоциативных вычислительных системах.Известно запоминающее устройство для храиения цифровых двумерных массивов данных (изображений), позволя ющеепроизводить обращение к столбцам, строкам и прямоугольным фраг- ментам изображения (1 ).В данном устройстве используются рай+1 интегральных микросхем памяти емкостью рп бит каждая с адрес ным доступом к.одному биту,обеспе" чивается выборка строки или столбца, содержащих рц элементов, или фрагмента с максимальным размером. сторон р и и. Точка изображения с координатами Ь и 1, где Ь и 1 целые числаот нуля,до рц,; попадает в интегральную микросхему памяти, номер которой И вычисляется по формулео(рЧ,+.)Такая система универсальна, однако для ее реализации необходимо большое количество оборудования.Наиболее близким к предлагаемому по технической сущности является ассоциативное запоминающее. устройство, содержащее регистр типаобращений, регистр адреса, сумматор по модулю два, блок мультиплексоров данныхрегистр данных и блокпамяти, причем выход регистра типаобращений соединен с одним из входов сумматора по модулЮ два, выходкоторого соединен,с первым адресным входом блока памяти, выход регистра адреса соединен с управляющим входом блока мультиплексоровданных, выход которого соединен свходом регистра данных,Блок памяти этого устройствапостроен на интегральных микросхе-мах памяти емкостью 2 бит каждая,где к=2 К и К=1, 2,3, Для хранения информации. используется Минтегральные микросхемы памяти,%=2 , т,е. столько, сколько элеменКтов матрицы бинарного изображениянеобходимо выбрать одновременно.Блок памяти может быть построен на.интегральных микросхемах большейемкости 2"М, при этом матрицаизображения будет составлена изквадратных подматриц со стороной М.: Для реализации многоформатного(к сторонам и столбцам) доступа элементы запоминаемой матрицы (бинар-ный массив И Ю) размещаются в интегральных микросхемах памяти такимобразом,.чтобы все элементы любойстроки или столбца попадали в разные микросхемы памяти. Это обеспечивает воэможность одновремейнойвыборки произвольной строки или 5 столбца.Для описания соответствия междуэлементами запоминаемой матрицыномерами интегральных микросхем памяти и адресами в ннх вводятся сле дующие обозначения: 1, Ь - номерстолбца и строки запоминаемой мат рицы Е = О -; И - 1 1 = О -. М - 1,Х - номер интегральной микросхемыпамяти,М = О . И - 1; А-й - разряд-.ный код адреса, определяющий выбор ку бита в одной микросхеме памяти;.8 - код типа обращения. Конкретные значения Ь, 1, И, А,Я можно рассматривать как двоичные 20 векторы и обозначить соответственноЬ",. 1 ф, Х, А , ЯВ дальнейшемиспользуются .поразрядные операцииконьюнкции (Л), дизьюнкции (Ч), сложения по модулю два (+) и отрицания 25 (-) над двоичными векторами. Напри.мер, С = х. Л уфобозначает чтоМС = (С , С С) = (х 4 у .,Юх 2 Луй х,Л уо).Каждый двоичный элемент запомиЗ 0 наемой матрицы с координатами Ь",1 хранится в микросхемепамяти,номер которой определяется из соот- ношения 35 55 динения описывается выражением А (уф.Л К+3 Ч(Х ФЙ )(2) Выражение (1), определяющее рас- .пределение элементов строк (столб-ф цов) по микросхемам памяти, указывает, что для различных строк (столб цов) порядок элементов на Шине данных блоха памяти будет различным.Этот порядок для строки (столбца)с номером Ь(1), как видно из выраДля подачи .адресов на микросхемыпамяти используются две шины хф и уфПо шине хф подается код адреса с регистра адреса устройства. По шине 40 у+ поступает код с выхода суммато-:ра по модулю два, на вход которогозаведены х и Яф, причем у"= РЯ ЯКод Я поступает с регистра типаобращений. Правило соединения ад ресных входов в блоке памяти следующее: адресные входы А= (а ,а 2 . ,ао), микррсхемы памяти сномером Х. = (и я , пй 2 ,пе)%соединяются с проводами шины у = 50 (Уйэ У,ув), если в соответствующих разрядах номера данной микросхемы есть единица, аостальныевходы соединяются с соответствующими(4) где И - номер микросхемы памяти, вкоторую попадает элементзапоминаемой матрицы с ко.ординатами Ь и 1.;ы - строка квадратного фрагмента;х - взятие целой части х.Как видно иэ таблицы, представленной на фиг, 2, при данном распределении возможно, обращение к к квадратным Фрагментам со стороной ы. Нафиг. 2 она выделена жирными линиями. Для реализации данного рас жения (1), определяется соответствующими диодными (по модулю два) сдвигами. Чтобы обеспечить однозначную упорядоченность при выборке.любой строки (столбца) в устройстве используется блок мультиплексоров данных, состоящий из Хо 25 ярусов. Каждый ярус реализует. перестановку элементов строки (столбца); соответствующую диодному сдвигу определенного (2 о, 2", 2 .,2 оф 2 ф 5 . 10 порядка. Управление включением яру-. сов блока мультиплексоров данных осуществляется в зависимости от сос таяния соответствующих разрядов кода адреса. 15Из выражения (2) следует, что, если вектор 5 ф полностью нулевой, на адресных входах всех микросхем памяти независимо от номера будет . Код, равный коду на шине х. Одини. тот же адрес на всех микросхемахф соответствует в устройстве режиму вйборки строк.Если Яф полностью единичный век-. тор, то выражение .(2) преобразуется . к виду. 25 Из .выражения (3) следует, что призаданном хф во всех .Х микросхемах 30памяти выбираются биты по разнымадресам. Это соответствует режиму обращения к столбцам хранимой матрицы,При,О с 52 - 1 получаются "смешанныеф способы обращения, при которых реализуется выборка различных.. сочетаний частей строки столбцов матрицы.Память, построенная по описанным принципам, отличается простотой , .40и большими функциональными возмож"настями 21.Однако эта память не позволяет реа лизовать выборку за одно обращение .квадратного гч(м: 1 Гу) фрагмента матри цы с покрытием этими фрагментами всего поля бинарного изображения. В тоже вре.-; мя необходимость такой выборки данных часто встречается в системах цифровой обработки изображений и в ассоци-50 . ативных процессорах.Целью изобретения является расши," . рение области применения ассоциатив-.ного запоминающего устройства насистемы цифровой обработки иэображений и повышение эффективности егоиспользования за счет введения дополнительных форматов обращения кпамяти для сокращения количестваобращений при работе С квадратными фрагментами изображений. ЖПоставленная цель достигаетсятем, что в схему запоминающего;уст ройства, содержащего регистр типа обращений регистр адреса, сумма- . Ктор по модулю два, блок мультиплек. саров данных, регистр данных и блокпамяти, причем выход регистра типаобращений соединен с одним из входов сумматора по модулю два, выходкоторого соединен с первым адресным.входом блока памяти, выход регистраадреса соединен с управляющим вхо.дом блока мультиплексоров данных,выход которого соединен с входомрегистра данных, введены элемент И,блок мультиплексоров кода адреса ивторой блок мультиплексоров данных,причем вход элемента И соединен свыходом регистра типа обращений, аего выход - с управляющим входомблока мультиплексоров кода адресаи управляющим входом второго блокамультиплексоров даннйх, вход блокамультиплексоров кода адреса подключен к выходу регистра адреса, аего выход соединен с вторым адресным входом блока памяти и вторымвходом сумматора по модулю два,вход второго блока мультиплексоровданных .подключен к информационномувыходу блока памяти, а ега выход квходу первого блока мультиплексоров данных.На фиг. 1 изображена структурнаясхема предлагаемого устройства, нафиг. 2 - соответствиемежду элементами запоминаемой матрицы и адреса-ми интегральных микросхем памяти,в которых они .хранятся для И, = 16;на фиг, 3 - схема блока памяти; нафиг. 4 в . перестановки, осуществляемые вторым блоком мультиплексоровданных (а ) и ярусами первого блокамультиплексоров данных (Е 6, а,З).Структурная схема запоминающе-го устройства содержит элемент И 1на К входов,. регистр 2 типа обращений, сумматор 3 по модулю два,блок 4памяти, второй.блок 5 мульти.плексоров данных, первый блок б .мультиплексоров данных, регистр 7данных, регистр 8 адреса, блок 9мультиплексоров када адреса. Такаяструктурная схема явилась следствием изменения распределения элемен.тов матрицы и интегральных микросхем памяти, Новое распределениеописывается выражением И = (/Ь / Й/3(+)1)пределения необходимо при всех обращениях, кроме обращения по столбцам, адрес, поступающий с регистра адреса, сдвинуть на К/2 разрядов циклически или, что тоже самое, переставить старшие и младшие разряды на шинах адреса. Новый порядок проводов хи следующий:хн- (х ,х 2х, 2хк )Крометого, при обращении постолбцам должен быть. включен второй блок мультиплексоров данных. Входы этого блока подключены к интегральным микросхемам памяти. При включенном втором блоке мультиплексоров выход микросхемы памяти с но-мером коммутируется на линию И номер которой вычисляется по формулеТаким образом, при обращениипо столбцам включается второй блокмультиплексоров данных и выключает"ся блок мультиплексоров кода адреса, а при остальных обращенияхвторой блок мультиплексоров данныхвыключен, а включен блок мультиплексоров кода адреса. На управляющие входы первого блока мультиплексоров данных всегда поступает кодхн фРассмотрим несколько примеровдля И = 16.П р и м е р 1, Положим Я=ОООО,Х=0110 При Я=ОООО обращенне про- .исходит по строкам, и при данномХ обращение должно произойти к шестой строке. Поскольку обращениепроисходит не по столбцам, то включен блок мультиплексоров .кода ад- .ресаи Х сдвигается на два разряда циклическиХН= 1001)У = Бо+Х.= ООООО+1001 = 1001.Из схемы, представленной .нафиг. 3, видно, что при полученных значениях Х и У на всех микросхемах памяти будет адрес 1001. Это соответствует шестой строке распределения, порядок данных в которой следующий:9,8,11,10,13,1216,14,1,0, 3,2,Этоозначает, что на нулевой проводшины данных должна попасть информация из девятой микросхемы памяти, на первый провод - информация иэ восьмой микросхемы памяти и т,д.Дпя данного преобразования служат блокимультиплексоров данных, Второй блок мультиплексоров данных в этомслучае не включен, а первый управляется кодом 1001, Б первомблоке мультиплексоров данных включается нулевой и третий ярусы перестановок 1 на фиг. 4, б и д ) иинформация на выходе блока ока 5 эывается в нормальном виде: 0,1,2. 15.П р и м е р 2. Положим 8=1111,Х=1000. При 5=1111 обращение происходит по столбцам, и блок муль 10 типлексоров кода адреса не включен,У = 111 О+1000 = 0111При Х=1000, У=0111 на микросхемах 15 памяти будут следующие адреса:на микросхеме 0 - 1000, на микросхеме 1 - 1001, на микросхеме 150111.Как видно из таблицы распределения информации (фиг. 2) по даннымадресам обращение соответствуетвосьмому столбцу, где порядок ииформации следующий812 фОф 4 ф 9 ю 1311 ь 5 ф 10,14 р 2 рбр 11 рПосле преобразования первым блоком мультиплексоров данных порядок будет следующий:2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13.Это означает, что информацияс второго провода шины данных должна попасть на нулевой провод, стретьего провода - на первый и т.д.Данное преобразование выполняетвторой блок мультиплексоров данных,который управляется кодом 0010(т,е. сдвинутым ХИ).4 О П р и м е р 3. Положим 5=1100,Х=0001. Должно произойти обращениек фрагменту с номером один,Хн= 0100, У = 1100 О+ 0100 = 1000.На адресных входах микросхем45 будут следующие коды адреса: намикросхеме 0 - 0100, на микросхеме 1 - 0100; на микросхеме 2 - 0100,на микросхеме 3 - 0100, на микросхеме 4 - 0000, на микросхеме 145 О 1000, на микросхеме 15 - 1000.Информация по данным адресам соответствует первому фрагменту.Порядок информации следующий:4,5,6,7,0,1,2,3,12,13,14,15,8,9,Включается первый блок мультиплексоров данных, который управляется кодом 0100 й преобразет информацию к нужному виду.ф Введение в схему запоминающегоустройства блока мультиплексоров кода адреса, второго блока мультиплексоров данных и элемента И незначктельно усложняет схему предла гаемого устройства, но дает эначитеявные преимущества по сравнению сизвестным, Применение предлагаемого запоминающего устройства для сис"тем цифровой обработки изображений существенно повышает его зффективность за счет сокращения в ю разколичества обращений к памяти приработе с квадратными фрагментами,1043747 ль А ДерюгиФанта И. Ватрушинйа юютюююююе юе рректПодписноа ССий 4/5 еююв юе ююе еееюее е в лиал ППП фПатентф, г. Уагород П ная,. Составитеедактор .Н. Лаэарецко "Гехредт,