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

Изобретение относится к вычислительной технике, а именно к разделу запоминающих устройств, которые могут использоваться в специализированных системах хранения и цифровой обработки изображений, а также в ассоциативных вычислительных системах, Известно запоминающее устройст в.о для хранения цифровых двумерных массивов данных (изображений):,позво ющее производить обращение к столб цам, строкам и прямоугольным -фрагментам изображения fl , В данном устройстве используются pq+l интегральных микросхем памяти емкостью pq бит каждая с адре ным доступом к. одному биту, 6бесле чивается выборка строки или столбца, содержащих pq элемен тов, или фрагмента с максимальным размером сторон р и q. Точка изображения с координатами L и Г , где L и I целые числам от нуля .до pq,, попадает в интегральную микросхему памяти, номер которой N вычисляется по формуле М ft + Т1 ,/ N (Lq, Пгпос1(рч,4-г) Такая система универсальна, одн ко для ее реализации необходимо бо шое количество оборудования. Наиболее .близким к предлагаемому по технической сущности является ассоциативное запоминающее, ус ройство, содержащее регистр обращений, регистр адреса, сумматор по модулю два, блок мультиплек соров данных,.регистр данных и бло памяти, причем выход регистра типа обращений соединен с одним из входов сумматора по модули два, выход которого соединен.с первым адресным входом блока-памяти, выход регистра адреса- соединен с управля,ющим входом блока мультиплексоров данных, выход которого соединен с входом регистра данных. Блок памяти этого устройства построен на интегральных микросхем мах памяти емкостью 2 бит каждая, где и , 2,3,... Для хранения информации используется W интегральные микросхемы памяти, , т.е. столько, сколько элемен тов- матрицы бинарного изображения необходимо выбрать одновременно. Блок памяти может, быть построен на интегральных мигсросхемах большей емкости 2 W, при этом матрица изображения будет соста.влена из квадратных подматриц со стороной W Для реализации многоформатного (к сторонам и столбцам) доступа эп менты запоминаемой матрицы (бинарный массив W-W) размещаются в интегральных микросхемах Пс1мятИ таки образом, чтобы все элементы любой строки или столбца попадали в разные микросхемы памяти. Это обес- печивает возможность одновремейной выборки произвольной строки или столбца. . Для описания соответствия меяшу элементами запоминаемой матрицы номерами интегральных микросхем памяти и адресами в них вводятся следующие обозначения: I, t - номер столбца и строки запоминаемой матрицы I 04 W - 1 -1 .0 4 W - 1; N - номер Интегральной микросзсемы , памяти .N ОЧ W - 1 J A-R - разряд-: ный код адреса, определяющий вцборку бита в одной микросхеме памяти; -S- - код типа обращения. Конкретные значения L, I, N, А, S можно рассматривать- как двоичные векторы иобозначить соответственнр L,- I, N, А, S. В дальнейшем используются .поразрядные операции коньюнкции (Л), дизъюнкции (V), сложения по модулю два ) и отрицания (-) над двоичными векторами. Например, С х.Л у обозначает что С- (, , . . , С0) (, х.,.2ЛУрЛ- -. И Уо) . 0 УОаждый двоичный элемент запоминаемой матрицы с координатами L, I хранится в микросхемепамяти, номер которой определяется из соотношения . N Для подачи.адресов на микросхемы памяти используются две шины х и у По шине X подается код адреса с регистра ад.реса устройства. По шине -поступает код с выхода суммато-:. ра по модулю два , на вход которого заведены х и причем у (5. Код S поступает с регистра типа обращений. Правило соединения .адресных входов в блоке памяти следукадее: адресные дходы А (ajj. , а jj.2 о) мйкррсхемы памяти с номером N (п,., ) соединяются с проводами шины (Ук--1 Ун.-2 «УО соответствующих разрядах номера данной микросхемы есть единица, а естальные входы соединяются с соответствующими проводами шины X. Схема такого соединения описывается выражением А - ( N)V() Выражение (1), определяющее распрёделеииё элементов строк (столб-ч цов) по микросхемам памяти, указыэает, что для различных строк (столб цов) порядок элементов на шиие даииых блока памяти будет различным. Этот порядок для отроки (столбца) с номером L(I), как видно из выражения (1), определяется соответствующими диодными (по модулю два) сдвигами. Чтобы обеспечить однозначную упорядоченность при выборке любой строки (столбца) в устройстве используется блок мультиплексоров данных, состоящий из ярусов. Каждый ярус реализует, перестановку элементов строки (столбца); соответотйующую диодному сдвигу. определенного (2 , 2, 2, . . . .,) порядка. Управление включением яру-. сов блока мультиплексоров данных осуществляется в зависимости от состояния соответствующих разрядов & кода адреса1. .

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

Если S полностью единичный век- тор,-то выражение .(2) преобразуется , к виду. .

©N

А X

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

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

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

.Однако эта память неПозволяет реализовать выборку за одно обращение квадратного vw( ) фрагмента матри.- щл с покрытием этими фрагментами всег.6.- поля бинарного изображения.В тоже время необходимость такой выборки данных часто встречается в системах цифровой обработки.изображений и в ассоциативных пpoцeqcopax. . . . . Целью изобретения является расшй,рение области применения ассоциатйвг Кого запомина ющего устройства на системы цифровой обработки изображени.й и повышение эффективности его использования за счет введения дополнительных форматов обращения к памяти для сокращения количества обращений при работе С квадратными фрагментами,изображений.

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

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

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

.вход второго блока мультиплексоров данных .подключен к информационному

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

На фиг. 1 изображена структурная схема предлагаемого устройства на

-фиг. 2 - соответствие между элемен-

0

тами запоминаемой матрицы и адресами интегр альных микросхем памяти, в которых они .хранятся рля W, 16, на -фиг. 3 - схема блока на фиг. 4 -г перестановки, осуществляе/мые вторым блоком мультиплексоров данных («) и ярусами первого блока мультиплексоров данных (Г, в,г,Э).

Структурная схема запоминающего устройства содержит элемент И 1

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

N (/Lw/,,.

(4

где N - номер микросхемы п амяти, в .которую попадает элемент аапоминаемой матрицы с координатами L и I.; строка квадратного фрагменW та; .., взятие целой части х.

X Как видно из таблицы, представленной на фиг. 2, при данном рас- . пределении возможно .обращение к к квадратным фрагментам со стороной W. На фиг. 2 она выделена жирными 5 линиями. Для реализации данного распределення необходимо при всех обращениях, кроме обращения по столбцам, адрес, поступающий с регистра адреса, сдвинуть на R/2 разрядов циклически или, что тоже самое, переставить старшие и младшие разряды на шинах адреса. Новый порядок . проводов Xf, следующий:

ПгЧ 12-2

0VlR-2

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

N -w/N/. N/W . .

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

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

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

XH 1001;

Y S0X 00000

)01 1001.

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

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

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

управляется кодом .tUOl. В первом блоке мультиплексоров дпяных включается нулевой и третий ярусы перестановок (на фиг. 4,5 иЭ ) и . информация на выходе блока оказывается в нормальном виде: 0,1,

2,15.

Пример 2. Положим , . обращение происходит по столбцам, и блок мультиплексоров кода адреса не включен.

У 11101000 0111

При., на микросхемах памяти будут следующие адреса: на микросхеме О - 1000, на микросхеме 1 - 1001, на микросхеме 15 0111.

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

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

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

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

12,13.

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

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

Пример 3. Положим , . Должно йроизойти обращение . к фрагменту с номером один.

Хц 0100, У 110000100 1000. На адресных входах микросхем будут следующие коды адреса: на микросхеме О - 0100, на микросхеме 1,- 0100; нА микросхеме 2 - 0100, на микросхеме 3 - 0100, на микросхеме 4 - 0000, на микросхеме 14 1000, на микросхеме 15 - 1000.

Информация по данным сшресам соответствует первому фрагменту. Порядок информации следующий:

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

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

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

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

.--i-l; 3-: ;

существенно повышает его эффективность за счег сокращения в w раз количества обращений к памяти при работе с квадратными фрагментами.

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