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

 

ЗАПОМИНАЮЩЕЕ. УСТ ОЙСТВО С МНрГОФОРМАШЬМ ДОСТУПОМ К ДАННЫМ, содержащее регистр типа, обращений, регистр , сукматор по модулю дда, блок мультиплексоров данных, регистр данньвс и блок памяти, причем выход регистра типаг:, обращений соединен с рАним из входов, сумматора по ыокугой два, выход которого соедиг. ней с первым адресным входом блока памяти, выход регистра адреса сое . динен с управляющим входом блока мультиплексоров данных, выход оторого соединен с входом регистра данных, о т л и чаю щ е .е ся тем, что, с целью расширения области применения за счет обеспечения . возможности обращения к квадратным фрагментам данных, в него введены элемент И, блок мультиплексоров кода адреса и второй блок мультиплексоров данных, причем вход элемента И соединен с выходом регистра типа обращений, а ее выход - с управляющим входом блока мультиплексоров кода адреса и управляющим входом .второго блока мультиплексоров данHbjx , вход блока мультиплексоров кода адреса подключен к выходу регистра адреса, а его выход соединен с вторым адресным входом б.пока памяти и вторым входом сумматора по С модулю два, вход второго блока мультиплексоров данных подключен к информационному выходу блока пзмяС ти, а его выход - к входу первого, блока мультиплексоров данных. 4 СО 4 41

„„SU„„1043747 А

СОЮЗ СОВЕТСКИХ.

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

РЕСПУБЛИК

: 3Ц0 С 11 С 11/34; G 11 С 7/04. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБР1 .,;ТЕНИЯ " ;,".;.",:, .„, / к Авто1 скому свидетельств

: (21) 3350058/18-24 (.22 ) 14. 07; 81 (46) 23 09. 83 Бюл. В 35. (72) В.В. Каверэнев и E.A..Èåòëèöкий (71) Ленинградский ордена Ленина электротехнический институт им. В.И. Ульянова (Ленина) (53).681.327.66(088.8) (56) 1. Патент Франции 9 .2369650, ., кл. G И С 11/34, 1978, :2. Патент C_#_A 9 3800.289, кл. 340-.1725, 1974 (прототип). (54.)(57),. ЗАПОМИНИОЩЕЕ. YCTQOACTBO С

: ИНОГОФОРМАТНЫМ ДОСТУПОМ К ДАННЫМ, содержащее регистр. типа. обращений, регистр адреса, сумматор по модулю два,. блок мультиплексоров данных, регистр данных и блок памяти., причем.-: выход регистра типа.;., обращенйй сое динен с одним.из входов. сумматора по модулю два, выход которого соеди-. нен с первым адресным входом блока памяти, выход регистра адреса сое» динеи с управляющим входом блока мультиплексоров данных, выход которого соединен с .входом. регистра данных, о т л и ч а ю щ е е с я тем, что, с целью расширения облас- . ти применения за счет обеспечения . воэможности обращения к квадратным фрагментам данных, в него введены элемент И, блок мудьтиплексоров кода адреса и второй блок мультиплексоров данных, причем вход элемента

И соединен с выходом регистра типа обращений, а ее выход — с управляющим входом блока мультиплексоров кода адреса и управляющим входом второго блока мультиплексоров дан.ных, вход блока мультиплексоров кода адреса подключен к выходу регист. Я ра адреса, а его выход соединен с вторым адресным входом блока памяти и вторым входом сумматора по модулю два, вход второго блока мультиплексоров данных подключен к информационному выходу блока памя- a . ти, а его выход - к входу первого, блока мультиплексоров данных.

1043747

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

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

В данном устройстве используются pq+1 интегральных микросхем памяти емкостью pq бит каждая с адрес ным доступом к.одному биту, обеспечивается выборка строки или столбца, содержащих pq элементов, или фрагмента с максимальным размером. сторон р и q. Точка. изображения с координатами Ь и I, где L u I целые числа от нуля,до рс1,; попадает в интегральную микросхему памяти, номер которой N вычисляется по формуле

)о (рЧ,+11

Такая система универсальна, однако для ее реализации необходимо боль шое количество оборудования.

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

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

Блок памяти этого устройства построен на интегральных микросхе-... мах памяти емкостью 2 бит каждая, где К=2К и К=1, 2,3,... Для хранения информации используется М интегральные микросхемы памяти, W=-2, т.е. столько, сколько элеменК тов.матрицы бинарного изображения необходимо выбрать одновременно.

Блок памяти может быть построен на .интегральных микросхемах большей емкости 2" > W, при этом матрица изображения будет составлена из квадратных подматриц со стороной W.

: Для реализации многоформатного (к сторонам и столбцам} доступа эле менты запоминаемой матрицы (бинар- ный массив W.W) размещаются в интегральных микросхемах памяти таким образом,. чтобы все элементы любой строки или столбца попадали в разные микросхемы памяти. Это обеспечивает воэможность одновременной выборки произвольной строки или столбца.

Для описания соответствия между элементами запоминаемой матрицы. номерами интегральных микросхем памяти и адресами в ннх вводятся сле19 дующие обозначения: I, L — номер столбца и строки запоминаемой мат рицы Е = 0-:И вЂ” 1 -1 =0-, W 1, Х вЂ” номер интегральной микросхемы памяти,N = 0 W - 1; А-R — разряд-. ный код адреса, определяющий выбор ку бита в одной микросхеме памяти;

-S - код типа обращения.

Конкретные значения L, I, И, А, S можно рассматривать. как двоичные

20 векторы и обозначить соответственно

L",. I, N, А, S .. В дальнейшем используются .поразрядные операции коньюнкции (A) дизьюнкции (V) сло жения по модулю два (+) и отрицания

25 (-) над двоичными векторами. Напри. мер, С = х. Л у обозначает что

М

С = (С1 1„С .2,..., Со) = (:с ., А УР--1

% хй2Л yR 2, ° ° °, xoË yP) .

Каждый двоичный элемент запомиЗО наемой матрицы с координатами L", I хранится в микросхеме памяти, номер которой определяется из соотношения

35 динения описывается выражением

А - (у л К )v(x ji,й ) 55 (2) Выражение (1), определяющее рас- . пределение элементов строк (столб- цов) по микросхемам памяти, указывает, что для различных строк (столб цов) порядок элементов на шине данных блоха памяти будет различным.

Этот порядок для строки (столбца) с номером L(I), как видно из выра65

Для подачи .адресов на микросхемы памяти используются две шины х+ и у"

По шине х подается код адреса с регистра адреса устройства. По шине

4О у+.поступает код с выхода суммато.-. ра по модулю два,.на вход которого заведены х и S, причем у"= ГЯ S

Код S поступает с регистра типа обращений. Правило соединения.ад45 ресных входов в блоке памяти следующее: адресные входы А+= (а „, а1 2 ....,аp), микррсхемы памяти с номером N = (п R-, nR 2 no)

% соединяются с проводами шины у =

5п. (y<, у 2,...,у;.), если в соответствующих разрядах номера данной микросхемы есть единица, а остальные входы соединяются с соответствующими .проводами шинн х . Схема такого сое"

1043747

A = хмо+М% (4) где И - номер микросхемы памяти, в которую попадает элемент запоминаемой матрицы с ко.ординатами Ь и I.;

w — строка квадратного фрагмента; х — взятие целой части х.

Как видно иэ таблицы, представленной на фиг. 2, при данном распределении возможно обращение к к квадратным фрагментам со стороной

w. На фиг. 2 она выделена жирными линиями. Для реализации данного рас. жения (1), определяется соответствующими диодными (по модулю два) сдвигами. Чтобы обеспечить однозначную упорядоченность при выборке. любой строки (столбца) в устройстве используется блок мультиплексоров данных, состоящий из fog211 ярусов. Каждый ярус реализует. пере-. становку элементов строки (столбца); соответствующую диодному сдвигу, 1: определенного (2 о, 2", 2,2,) 10 порядка. Управление включением яру-. сов блока мультиплексоров данных осуществляется в зависимости от coc" таяния соответствующих разрядов кода адРеса. 15

Из выражения (2) следует, что, если вектор S" полностью нулевой, на адресных входах всех микросхем памяти независимо от номера будет . Код, равный коду на шине х . Один и. тот же адрес на всех микросхемах соответствует в устройстве режиму вйборки строк. . Если S полностью единичный век- . тор, то выражение .(2) преобразуется . к виду„

Из .выражения (3) следует, что при заданном x+ во всех .N микросхемах 30 памяти выбираются биты по разным адресам. Это соответствует режиму обращения к столбцам хранимой матрицы.

При .0 < Я < 2 — 1 получаются "сме- - 35 шанные" способы обращения, при кото рых реализуется выборка различных. . сочетаний частей строк и столбцов матрицы.

Память, построенная по описанным принципам, отличается простотой и большими функциональными возмож" настями (23.

Однако эта память не позволяет реа лизовать выборку за одно обращение . квадратного гч(м ф) фрагмента матри- 45 цы с покрытием этими фрагментами всего . поля бинарного изображения. В тоже вре.-; мя необходимость такой выборки данных часто встречается в системах цифровой обработки изображений и в ассоци- 50, ативных процессорах.

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

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

На фиг. 1 изображена структурная схема предлагаемого устройства, на фиг. 2 — соответствие между элементами запоминаемой матрицы и адреса- ми интегральных микросхем памяти, в которых они .хранятся для W. = 16; на фиг. 3 — схема блока памяти; на фиг. 4 †. перестановки, осуществляемые вторым блоком мультиплексоров данных (a ) и ярусами первого блока мультиплексоров данных (Е 6, z.,31

Структурная схема запоминающе- го устройства содержит элемент И 1 на R входов,. регистр 2 типа обращений, сумматор 3 по модулю два, блок 4 памяти, второй. блок 5 мультиплексоров данных, первый блок 6 . мультиплексоров данных, регистр 7 данных, регистр 8 адреса, блок 9 мультиплексоров када адреса. Такая структурная схема явилась следствием изменения распределения элемен.тов матрицы и интегральных микросхем памяти. Новое распределение описывается выражением

N = (/L w/ìîà÷+(1 /wan?) 104374 i пределення необходимо при всех обращениях, кроме обращения па столбцам, адрес, поступающий с регистра адреса, сдвинуть на R/2 разрядов циклически или, что тоже самое, переставить старшие и младшие разряды на шинах адреса. Новый порядок проводов х> следующий:

V ЪР- Ъ|2-1 о Ъ-1 R-г "Вг

Кроме того, при обращении по столбцам должен быть. включен. второй блок мультиплексоров данных. Входы этого блока подключены к интегральным микросхемам памяти ° При включенном втором блоке мультиплексоров выход микросхемы памяти с но- мером коммутируется на линию N номер которой вычисляется по формуле

N = w/N/ + fN/w)

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

Рассмотрим несколько примеров для W = 16.

Пример 1. Положим S=OOOO, X=0110.. При S=0000 обращенне про- . исходит по строкам, и при данном

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

ХН= 1001 )

Y = sO+x = 00000+1001 =1001.

Из схемы, представленной .на фиг. 3, видно, что при полученных значениях Х и У на всех микросхемах памяти будет адрес 1001. Это соответствует шестой строке распределения, порядок данных в которой следующий:

9,8,11,10,.13,12,, 16,14, 1,0, 3, 2, Это означает, что на нулевой провод шины данных должна попасть информация из девятой микросхемы памяти, на первый провод — информация иэ восьмой микросхемы памяти и т.д.

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

l управляется кодам 1001. В псрьом блоке мультиплексоров данных вклн1чается нулевой и третий ярусы перестановок (на фиг. 4, б и д ) и информация на выходе блока ока5 эывается в нормальном виде: 0,1, 2,...,15.

Пример 2. Положим S=1111, Х=1000. При $=1111 обращение происходит по столбцам, и блок муль)р типлексоров кода адреса не включен.

У = 111Q+)1000 = 0111

При Х=1000, У=0111 на микросхемах

15 памяти будут следующие адреса: на микросхеме Π— 1000, на микросхеме 1 — 1001, на микросхеме 15

0111.

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

8 ° 12 з 0 з 4 в 9 е 13 1 ь 5 10 ю 1 4, 2 р 6 р 11 р

После преобразования первым блоком мультиплексоров данных порядок будет следующий:

2,3,0,1,6,7,4,5,10,11,8,9,14,15, 12,13.

Это означает, что информация с второго провода шины данных должна попасть на нулевой пРовод, с третьего провода — на первый и т.д.

Данное преобразование выполняет второй блок мультиплексоров данных, который управляется кодом 0010 (т.е. сдвинутым ХН).

4P II р и м е р 3. Положим S=1100, X=0001. Должно произойти обращение к фрагменту с номером один.

Хн= 0100, У = 1100О+ 0100 = 1000.

На адресных входах микросхем

45 будут следующие коды адреса: на микросхеме О - 0100, на микросхеме 1 — 0100; на микросхеме 2 — 0100, на микросхеме 3 — 0100, на микросхеме 4 — 0000, на микросхеме 14

5р 1000, на микросхеме 15 — 1000.

Информация по данным адресам соответствует первому фрагменту.

Порядок информации следующий:

4,5,6,7,0,1,2,3,12,13,14,15,8,9, Включается первый блок мультиплексоров данных, который управляется кодом 0100 и преобразет информацию к нужному виду.

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

$04 3 74 7 явные преимущества по сра внению с известным. Применение предлагаемого запоминающего устройства для сис" тем цифровой обработки изображений существенно повышает его зффективность за счет сокращения в ю раз количества обращений к памяти при работе с квадратными фрагментами.

10!

0100

1О01

fNl

g0l0

0ff0

ОИ2

1011 б Я

1043747

9 10

12 15.5 Т2

13 ж

13 lO

12 15

8 11

15 12

И О

7 4 з о

0001

1043747

1043747. Составитель A.. Дерюгин

Редактор .Н. Лазаренко "ТехредТ,фанта: .. Корректор И. Эатрушкйна -::

Ю » » а и » »»э ю ° »» ю °

Заказ .7348/57 тиран 594 . - Подписное

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

113035, Москва, X-35, Раушская наб., д.4/5 ющВ ю ююю ° Феаеее Ь В

Филиал ППП "Патент", r. Уагород, ул. Проектная, 4