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

 

.Изобретение относится к запоминающим устройствам и может быть использовано в системах с произвольным доступом к двумерным данным, например в .процессорах коррекции геометричесг кик искажений изображения. Цель изобретения - увеличение производительности буферного запоминающего устройства при обработке двумерных данных. Буферное запо.минающее устройство содержит блок 1 памяти адреса,блок 2 v управления флагами сравнения, блок 3 преобразования адреса, коммутатор 4 адреса, блок 5 памяти данных, регистр 6 входных данных, блок 7 управления. Устройство позволяет существенно сокi (Л

4 84 А1

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

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

РЕСПУБЛИК (19) (11) (50 4 G 06 F 12/00

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

H ABTOPCH0MY СВИДЕТЕЛЬСТВУ

ГОСУДАРСтаЕНКЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (Zi) 4006155/24-24 (22) 08.01.86 (46) 15.12.88. Бюл. № 46 (7 1) Институт автоматики и электрометрии СО АН СССР (72) В.А, Слуев (53) 681. 325 (088. 8) (56) Престон К. и др. Основы клеточной логики с приложениями к обработке изображений в медицине. " ТИИЭР, 1979э т.67ь № 5 °

Гиммельфарб Г,П. Автоматизированная межотраслевая обработка снимков земной поверхности, получаемых в НС3 серии LANDSAT. — Зарубежная радиоэлектроника, 1983,¹ 8.

ЭВМ "Электроника 79" 15ВМ-16-011.

Эксплуатационная документация. Книга 9. (54) БУФЕРНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

С ПРОИЗВОЛЬНОЙ ВЫБОРКОЙ ДВУМЕРНОГО

ФРАГМЕНТА (57).Изобретение относится к запоминающим устройствам и может быть использовано в системах с произвольным доступом к двумерным данным, например в .процессорах коррекции геометричес-. ких искажений изображения, Цель изобретения - увеличение производительности буферного запоминающего устройства при обработке двумерных данных.

Буферное запоминающее устройство содержит блок 1 памяти адреса, блок 2 -. управления флагами сравнения, блок 3 преобразования адреса, коммутатор 4 g адреса, блок 5 памяти данных, регистр

6 входных данных, блок 7 управления.

Устройство позволяет существенно сок1444784 ратить количество повторно извлекаемых иэ памяти двумерных данных, обеспечивает параллельность выборки элементов двумерного фрагмента, одновременный контроль данных в четырех соседних сегментах иэображения. В предлагаемом устройстве данные в блоках 1 и 5 распределены по модулям памяти в соответствии со специальной

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

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

10 На фиг.1 изображена функциональная схема буферного запоминающего устройства с „произвольной выборкой двумерного фрагмента; на фиг.2— функциональная схема блока памяти адреса; на фиг,3 — блок управления флагами сравнения; на фиг.4 - блок маскирования и циклического сдвига флагов сравнения; на фиг.5 — блок преобразования адреса; на фиг.бблок памяти данных, на фиг.7 - блок циклического сдвигателя выходных данных; на фиг.8 . — конфигурация окрестностей двумерного фрагмента данных; на фиг.9 — нумерация элементов двумерного фрагмента.

Буферное запоминающее устройство содержит блок 1 памяти адреса, блок 2 управления флагами сравнения, блок 3 преобразования адреса, коммутатор 4 30 адреса, блок 5 памяти данных, регистр

6 входных данных, 5лок 7 управления, вход 8 полного адреса фрагмента, вход 9 готовности адреса фрагмента, ВыхОД 10 ГотОВности BbIxopHbIx Данныху 35 информационный выход 11 устройства, адресный выход 1? устройства, выход . 13 готовности адреса сегмента, выход

14 готовности входных данных, информационный вход .15, вход 16 стробиро- <0 вания регистра 6, вход 17 записи в функцией. За счет этого элементы двумерного фрагмента всегда расположены в .разных модулях памяти. Схема управления флагами сравнения обеспечивает выборку из системной памяти только недостающих данных, что. обеспечивается применением специальных функций маскирования флагов сравнения. 5 з.п, ф-лы, 9 ил., 4 табл.

2 блок 1,. вход 18 записи в блок 2 управления флагами сравнения, вход 19 стробирования дешифратора блока 2 управления флагами сравнения, выход

20 статуса блока 2 управления флагами сравнения, вход 21 записи в модули памяти блока 5 памяти данных, информационный вход 22 блока 5, вход

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

25 блока 1, вход 26 разрешения записи блока 1, выход 27 адреса сегмента, адресный вход 28 блока 5, второй и третий выходы 29; 30 блока 2, второй информационный вход 31 коммутатора

4, вход 32 управления коммутатором 4, вход 33 чтения блока 5 памяти данных.

Блок 1 памяти адреса содержит четыре группы сумматоров 34 адреса, четыре модуля 35 памяти, четыре схемы 36 сравнения адреса и данных в модулях 35 памяти, Блок 2 управления флагами сравнения содержит узел 37. маскирования и циклического сдвига флагов сравнения, четырехраэрядный регистр 38 флагов, приоритетный шифратор 39, дешифратор 40, выходы 41 маскированных флагов сравнения.

Узел 37 маскирования и циклического сдвига флагов сравнения содержит первый и второй входные схемы 42 и 43 сдвига первого каскада, входную схему 44 сдвига второго каскада, выходную схему 45 сдвига первого каскада, первый. и второй выходные схемы

46 и 47 сдвига второго каскада, элементы И 48,...,51, элементы НЕ 52 и 53, элементы ИЛИ 54 и 55.

3 14447

Блок 3 преобразования адреса содержит первый и второй сумматоры 56 и 57 адреса, сумматор 58 приращений адреса, коммутатор 59, регистр 60 адреса, регистр 61 длины строки. .5

Блок 5 памяти данных содержит шестнадцать групп сумматоров 62 адреса, шестнадцать модулей 63 памяти, узел 64 циклического сдвига выходных данных.

Узел 64 циклического сдвига выходных данных содержит четыре схемы

65 сдвига первого каскада и групповую схему 66 сдвига второго каскада.

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

На вход 8 поступают Р разрядов, где P=log

1 первой координаты, где i=1 lîg М-1, и разряды. и; второй координаты, 25 где i 1,...,lag

=0,..., l og L-1, . и младшие разряды и; второй координаты, где i =О,...,log

Перед началом работы по сигналу 35 начальной установки осуществляется обнуление всех ячеек памяти .блока 1 памяти адреса. После этого буферное запоминающее устройство готово к работе. Внешнее задающее устройство устанавливает адрес двумерного фрагмента на входе 8 и генерирует сигнал готовности адреса по входу 9. На сумматоры 34 (фиг;2) каждого из четырех модулей 35 памяти поступают млад- 45 шие разряды, а также разряды m;, и . полного адреса памяти, на сумматоры

62 каждого из шестнадцати модулей 63 памяти блока 5 через коммутатор 4 поступают младшие разряды, а также раэ- 50 ряды me, m „.и» п„полного адреса.

На выходах сумматоров 34 блока 1 устанавливаются полные адреса четырех сегментов 1-4 (фиг.8), в которых-могут располагаться элементы фрагмента на выходах адресных сумматоров 62 блока 5 собственно адреса элементов фрагмента. Выборка данных иэ модулей памяти блоков 1 и 5 осуществляется

84 4 параллельно, В схемах 36 сравнения блока 1 старшие разряды полного адреса с данными в соответствующем модуле памяти, адресуемом младшими разрядами полного адреса сегмента. Разряды четырехразрядного выхода 25 блока 1 (флаги сравнения) для восстановления порядка расположения флагов искаженного использованием функций (8) поступают на первый и второй входные схемы 42 и 43 сдвига первого каскада блока 2 и затем на выходную схему 44 сдвига первого каскада. В схемах 42 и 43, управляемых разрядом т полного адреса памяти, осуществляется циклический сдвиг внутри групп флагов по два в каждой группе, во втором каскаде (схема 44) управляет мом разрядом п z полного адреса памяти, циклический сдвиг групп. Как следует из фиг.8 для организации произвольной выборки фрагмента из блока 5 может .потребоваться загрузка.от одного до четырех сегментов, что определяется положением элемента а „ внутри сегмента. Поэтому четырехразрядный код признаков сравнения после корректировки положения данных поступает на выход узла 37. На базе элементов

И 48,...,51, НЕ 52 и 53, ИЛИ 54 реализуются функции 1.0. Элементы И 48, 49,50 осуществляют собственно маскирование соответствующих флагов сравнения, запрещая выборку ненужных сегментов из памяти исходного изображения. Маскирование флагов сравнения осуществляется разрядами m, m <, и„, и,. полного адреса памяти, Выходами узла 37 маскирования и циклического сдвига флагов сравнения являются два четырехразрядных выхода: сигналы разрешения записи в модули памяти блока 1 (выход 26) и флаги сравнения, модифицированные схемой маскирования (выходы 41). Для корректной записи в модули памяти блока 1 старших разрядов полных адресов сегментов в схемах 45,...,47 сдвига (фиг.4) осуществляется обратная корректировка положения разрядов кода флагов сравнения. В схеме 45, "управляемой разрядом m полного адреса памяти, меняется положение двух групп по два разряда кода флагов, в схемах 46, 47, управляемых разрядом и <, изменяется положение разрядов внутри групп.

Через промежуток времени t, необходимый для установки сигналов разрешения записи (на входе 26) в модули памяти блока 1, установки кода флагов на входах регистра 38, установки данных на выходах данных блока 5, блок 7 управления генерирует сигнал записи по входу 17 в модули памяти блока 1 и сигнал записи по входу 18 в регистр 38 флагов. В состав приоритетного шифратора 39 (фиг.3) кроме собственно шифратора входит схема ИЛИ, входы которой подключены к выходам регистра флагов.

Блок 7 управления анализирует состояние входа 20, являющегося выходом указанного элемента ИЛИ, и, если запросов на загрузку сегментов нет, устанавливает сигнал на выходе 10 готовности данных на выходе 11. Если необходима загрузка сегментов, блок

7 управления снимает сигнал чтения данных из блока 5 по входу 33,переключает коммутатор 4 адреса сигналом на входе 32 в положение, обеспечиваю" щее прохождение на адресные сумматоры блока 5 разрядов с линии 31, переключает коммутатор 59 адреса сигналом с входа 23 так, чтобы выходы сумматоров 56 и 57 быпи подключены к входам регистра 60, стробирует адрес первого загружаемого сегмента в выходной регистр 60 адреса сигналом с входа 24 и генерирует запрос к памяти исходного изображения на линии 13, Адрес загружаемого сегмента, содержащийся в регистре 60, формируется из. адреса базового сегмента Ь|,-, генерируемого адресными сумматорами первого модуля памятй блока 1. Полный адрес базового сегмента на линии 27, разделенный на адреса по первой координате и адреса по второй координате, подключен к первым входам соответственно сумматоров 56 и 57. Полный адрес сегмента с выхода сумматоров через коммутатор

59 поступает на вход регистра 60. Выходы регистра 38 флагов подключены к входам приоритетного шифратора в следующем порядке убывания приоритета: флаг сегмента Ь;, „ „, флаг cer1 мента Ь;,, флаг сегмента b;1

I 6 флаг сегмента b; . Соответственно

1 коды, генерируемые приоритетным шифратором для каждого флага, являющегося старшим в какой-то момент времени, следующие: 11, 10,01 00. Старший разряд выходного кода приоритетного шифратора поступает на вход вычитания единицы сумматора 56, а младший - на

1444784 6 вход вычитания единицы сумматора 57.

Применение такой схемы позволяет параллельно, беэ перебора анализировать 5 состояние регистра 38 флагов и формировать на сумматорах 56 и 57 адреса только тех сегментов, загрузка которых необходима.

После установки адреса сегмента. в регистре 60 и запроса к памяти исходного изображения на линии 13 блок 7 управления анализирует состояние линии 14 готовности данных. Когда на входе 15 устанавливаются истинные

15. данные, что сопровождается изменением состояния линии 14, блок 7 управления генерирует строб записи данных на линии 21 в модули памяти блока 1.

Данные с выхода 15 через регистр 6

2р поступают на вход 22 блока 5. На адресные сумматоры блока 5 по входу 28 поступают младшие разряды полного адреса сегмента, причем разряды адреса соответствующие разрядам m „, m,.

25 и, n „ полного адреса устанавливаются в состояние "О". Данные в блок 5 записываются сегментами, т,е. порядок расположения элементов фрагмента не нарушается. Это дает возможность

gp отказаться от корректировки положе-. ния данных на входе блока 5 памяти данных.

Одновременно со стробом записи в блок 5 блок 7 управления стробирует выходы дешифратора 40 (фиг,3) сигналом на линии 19. По заднему фронту этого импульса осуществляется сброс флага в регистре 38, соответствующего загруженному сегменту. После этого устройство управления анализирует состояние линии 20, Если в регистре

38 флагов имеются установленные s

/ единицу разряды, то процесс считывания сегментов продолжается до обнуления регистра 38 флагов, что будет зафиксировано изменением состояния линии 20. Когда все необходимые сегменты загружены, устройство управления переключает коммутатор 4 в поло50 жение, обеспечивающее прохождение на адресный вход 28 сигналов с входа

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

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

1444784 объясняется физическим устройством средств ввода/вывода изображений.Для работы с линейной организацией данных в состав блока 3 преобразования адре5 са введены сумматор 58 приращений адреса и регистр 61 длины строки, предполагается также использование 32разрядной шины данных. В этом случае адрес сегмента, генерируемый на ли- 10 нии 27, является адресом первых четырех элементов сегмента, лежащих в одной строке. Адреса элементов сегмента, расположенных в других строках, можно получить последовательным суммированием длины строки и составляющей адреса сегмента по второй координате. При этом составляющая адреса по первой координате зафиксирована. Полученные данные последовательно записываются в регистры 6 входных данных и затем параллельно перегружаются в модули памяти блока 5. с!редлагаемое устройство буферной 25 памяти с произвольной выборкой двумерного фрагмента ориентировано на последовательную обработку потока фрагментов размером 4х4 элемента.

Данные извлекаются из памяти исходно- З0 го изображения,в устройство буферной памяти и записываются в память выход" ного изображения, генерируемого обрабатывающим процессором. При использовании буферной памяти в процессорах исправления геометрических искажений входным генератором адреса является процессор полиномиального преобразования координат, а выходным процессором — устройство взвешенного суммиро- 40 вания элементов извлекаемого фрагмента, т.е. устройство интерполяции по методу кубической свертки (2), Данные, получаемые процессором свертки, линейно, строка за строкой записыва- 45 ются в выходную память. Для записи одного элемента, данных изображения необходимо считать шестнадцать элементов данных из памяти исходного изображения. При достаточно высоком быстродействии входного и выходного процессоров скорость извлечения данных ограничивает производительность системы в целом. Предлагаемое устрой" ство буферной памяти позволяет пони55 зить частоту обращений к памяти исходного изображения, а также повысить скорость обработки за счет эффектив-. ной буферизации данных.

Память исходнбго изображения емкостью M

4 4 го изображения содержится

Ь P буферной памяти — х - сегментов. Сег4 4 мент является единицей данных при загрузке данных в буферное запоминающее устройство. Блок 1 памяти адреса

1п- 1, h-q М-!, а >re-1, h+ т-3,h+1 а„,„а „„а,„„, A(m,n) =

+tAtg A- + W(Р+ fll41< h+g + Illif,„ где m,n — индексы, определяющие адрес фрагмента, причем 0 4m

В блоке 1 осуществляется параллельньй контроль за данными, содержащимися в блоке памяти данных (БД) в четырех соседних сегментах. При отсутствии данных требуемый сегмент загружается из памяти исходного изображения, после чего возможна выборка по произвольному адресу. В зависимости от адреса возможна загрузка от одного до четырех сегментов. Их количество определяется функциями маскирования флагов сравнения старших разрядов полного адреса памяти и данных в БА.

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

В БД с помощью шестнадцати пар сумматоров и блока циклического сдвига данных на выходе шестнадцати модулей памяти реализована произвольная выборка фрагмента 4х4 элемента вида

1444784

P m n+1

А (mn) = — — + — -

4 4 4 (5) P m n+2

А (mn) = — -+ — - т 4 4 4

P ш+1 п, А (m и) = — — — + -

4 4 4

9 образующих квадратную матрицу (1), можно представить следующим образом

A(m+i,п+))*Р(m+i)+(п+)), (2) где i u j — целые числа, изменяющие5 ся в пределах: -1 8 i <2

-1 j <2;

P — - длина строки;

m u n — координаты центрального элемента. 10

В предлагаемом буферном запоминающем устройстве элементы двумерного массива распределены по шестнадцати модулям памяти в соответствии с функцией распределения 15

P m+1 п-1, А (mn) = — — -+

4 4 4

P в+1 и+1.

А (m n) = — — — + ю

4 4 4

Р m+1 и+2, A(mn) =-- — +- —

4 4. 4

m n

Ы(ш п) = 4 4 + (3) где " = " — символ, обозначающий операцию взятия остатка от деления; .с-(man) — номер модуля памяти (О «С (15), Адреса элементов массива в модулях памяти определяются формулой

P m+2 п-1

А,(m n) = — — -+

4 4 4

P m+2 п, А (mn) = — — —.+

1э 4 4 4

Р m+2 и+1

А (mn) =- — — + — -

4 4 4

P m+2 n+2

А (m n)= — — -+ — -

1 4 4 4

А „ — номера модулей памяти.

a .

Пример распределения двумерного массива по модулям представлен в табл. 1. Здесь показано расположение фрагмента в памяти для m=4 пб и

P =255.

Использование функции (3) приводит к нарушению естественного расположения элементов фрагмента, извлекаемого из памяти. Обозначим элементы фрагмен- та цифрами от 0 до 15 в соответствии с фиг;9. Тогда функцию перестановки данных можно описать, как в табл.2.

Блок, реализующий описанную в табл.2 функцию перестановки, показан на фиг. 7. Первый каскад осуществляет циклический сдвиг внутри четырех групп данных и управляется разрядами и и:.:и полного адреса памяти (функцйя Ф 1 в табл.2), второй каскад осуществляет циклический сдвиг самих групп данных и управляется разрядами ш и m „ полного адреса памяти (функция ф 2 в табл.2).

Пусть Я х N — размерность массива данных, хранящегося в памяти исходного изображения, L x P — размерность массива данных, хранящегося в БД бу-, ферного запоминающего устройства.

Разрядность шины полного адреса памяти двумерного фрагмента (1) можно представить выражением

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

P m-1 и-1

А (mn) *.— --- Ф

4 4 4

P m-1 тя и

+ °

A, (m,n)

А (ш,n)

А з(ш,п) 60 и+1

+ и+2, 4

Р

4 и-1

Aj(m n) — - +

P m

4 4

А (а,п) — — +

P m

4 4

Р m n

A(m n) = — — + — . (4)

44 4

tl lf где — — символ, обозначающий операцию взятия целой части деления. 30

Таким образом, положение элемента массива в памяти определяется номером модуля памяти и адресом внутри модуля, вычисляемым по формулам (3) и (4). Для распределения элементов массива, определяемого формулой (3), 35 элементы фрагмента (1) при любых

m и и таких, что 04m (L и 06лп<Р, будут находиться в разных модулях памяти, 40

М N L Р где Ар — разрядность шины адреса.

Выражение в первых круглых скобках представляет старшие разряды полного адреса памяти, во вторых — разряды адреса сегмента в БД, содержащего центральный элемент а „ матрицы (1), Цифрой 4 представлены разряды m O,,m 1, и, IIÄ, адресующие элемент а „ внутри сегмента. Старшие разряды полного адреса памяти запоминаются в БА, длина слова которого равна

М И

D=1og — + log — +Т, Ь Р. где Т вЂ” добавочный двоичный разряд истинности данных.

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

L адресная шина БА содержит log - +

B(i 3)= t- 1-1 1-lii (7) где д,) — индексы, определяющие адрес фрагмента, причем

0 i. — О-" - ,L P

4 4 — центральный элемент фрагмента °

Ъ;

1J Элементы ма с сива размерностью

L „P

4 " 4 Распределены по четыРем модулям

Р

+ log — двоичных разрядов. Ввиду того, что в БД осуществляется выборка фрагмента с переходом через границы сегмента, в состав адресной шины БД входят также разряды m, m,, и„, и<Элементы фрагмента (1) могут нахо,", .диться в одном, двух или четырех сегментах. С целью параллельной проверки на предмет наличия или отсутствия требуемых сегментов в БД, в БА организована двумерная выборка фрагмента

2х2 элемента вида (8) модуля О - массива в модулях формулой.5 о((i,j) = 2 = +

2 где а((i, j ) — номер

Адреса элементов памяти определяются

10 p(i j) = + .1

P i

8 2 2

Адресные функции для параллельного доступа к фрагменту имеют вид

Р— 1

А (i j) -=-. -- — +

1 в ° 8 2 29

P i -1 °

20 1 8 2 2

Р i

А (i j) = — — +

8 2 2 где А,А,А и A э — номера модулей о

25 памяти блока БА.

В модуле памяти А g БА хранятся старшие разряды адресов сегментов, 3 удовлетвОряющие условию 2 О, = О, З0 в модуле А, - удовлетворяющие условию

1 3

1 " = = 1 B модуле А g - удовлет2 2

1 1 воряющие условию = = О 2 1 в мо дуле А - удовлетворяющие условию

5.

i 1

1=0.

2 2

Пример распределения элементов

40 двумерного массива данных по четырем модулям памяти представлен в табл.З °

Здесь также показано расположение фрагмента в памяти для i=2, j2

L и -=64 ° Так же, как и в памяти дан45 4 ных, использование функции (8) при" водит к зависимости порядка расположения выходных данных модулей памяти

А,А „А и А э от адреса извлекаемых сегментОв ° Однако В Отличие OT схемы перестановки данных, используемой в

БД, корректировке подвергается порядок сяедования флагов сравнения данных в модулях памяти и старших разря" дов адресов сегментов, генерируемых

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

44784 l2 памяти в соответствии с функцией распределения

l3

144478 сдвигатель ° Первый каскад осуществляет циклический сдвиг внутри двух групп флагов сравнения (по два в каждой группе) и управляется разрядом п полного адреса памяти, второй каскад осуществляет циклический сдвиг самих групп флагов и управляется разt рядом m полного адреса памяти.

На фиг.8 изображены девять сегментов, обозначенных цифрами 1...9, в которых могут располагаться элементы фрагмента (1), если элемент а,„„ находится в центральном сегменте 5, Hs Рисунка видно, что при m,=0 и и, О элементы фрагмента (1) могут находиться в сегментах 1,2,4,5, при m., i, n,= @ - в сегментах 4 5 7 8, при

m 1, и 1 — в сегментах 5,6,8,9.

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

P i — 1+m1 1-1+n

А (i „ ) + .1 ° о 3 8 2

P i-1+m 1+и 1

А (i j) = — — — - +

1 э 8 (9)

P i+m, -1+n i

А (i j) = — — -- +

8 2 2

P i+m, 1+и

A (i j) = — — — +

8 2 2 где А,А „,А и А — номера модулей 35 памяти.

На фиг.8 Б изображены четыре сегмента двумерной матрицы данных, обозначенные цифрами 1 — 4, в которых могут находиться элементы фрагмента 40 (i) с учетом модифицированных адресных функций (9). Внутренний квадрат ограничивает местоположение центрального элемента а „, внешний †.границы фрагмента (1) при изменении положения а в заданных пределах. В завиМп симости от положения центрального элемента а„„ требуется загрузка разного количества сегментов, что определяется табл.4, ь табл.4 для каждой Б0 кодовой комбинации разрядов m,m „, и,, п определяется, какие из сегментов с номерами 1 — 4 необходимо загрузить..Единица в соответствующей графе означает, что сегмент должен быть загружен. Из табл,4 можно получить функции

F1=(mð m,) i (й, ч n, );

14

F2 = m vm,;

F3 й,чп,, F4 = 1, которые определяют необходимость загрузки в БД соответствующих сегментов. формула и з о б р е т е н и я

1,. Буферное запоминающее устройство с произвольной выборкой двумерного фрагмента, содержащее блок управления, блок памяти .адреса, блок памяти дйнных, блок преобразования адреса, регистр входных данных, первый выход блока управления соединен с входом записи блока памяти адреса, второй и третий выходы блока управления соединены с входами чтения и записи блока памяти данных соответственно, четвертый выход блока управления соединен с входом стробирования регистра входных данных, пятый и шестой выходы блока управления соединены с первым и вторым входами стробирования блока преобразования адреса, адресный вход блока памяти адресов соединен со cTBpHIHMH разрядами первой и второй координат входа полного адреса фраг-. мента устройства, информационный вход регистра входных данных является информационным входом устройства, вы" ход регистра входных данных соединен с информационным входом блока памяти данных„ выход которого является информационным выходом устройства, седьмой и восьмой выходы блока управления являются выходами готовности выходных данных и адреса сегмента устройства, первый и второй входы ветвления блока управления являются входами готовности адреса фрагмента и входных данных устройства, первый выход блока преобразования адреса является адресным выходом устройства, первый выход блока памяти адреса соединен с первым информационным входом блока преобразования адреса, о т л и ч а ю щ е е с я тем, что, с целью увеличения производительности при обработке двумерных данных, в него введены блок управления флагами сравнения, коммутатор адреса, причем первый информационный вход коммутатора адреса соединен с входом младших разрядов первой и второй координат входа полного адреса фрагмента

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

2. Устройство по п.1, о т л и — ЗО ч а ю щ е е с я тем, что, блок памяти адреса содержит четыре модуля памяти, четыре схемы сравнения и восемь сумматоров адреса, образующих четыре группы по два, причем вход записи блока соединен с входами записи всех модулей памяти, старшие разряды первой и второй координат адресного входа блока соединены с входами первого слагаемого первого и второго суммато- 40 ров адреса всех групп соответственно, младший разряд первой и второй координат адресного входа соединен с входами переноса первого и второго сумматоров адреса всех групп соответст- 45 венно, старшие разряды первого и второго сумматоров адреса р-й группы соединены с информационным входом р-го модуля памяти, младшие разряды выходы первого и второго сумматоров адреса р-й группы соединены с адресным входом р-го модуля памяти, где р = 1,...,4, выходы первого и второго сумматоров адреса первой группы являются первым и вторым составляющими

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

84 схемы сравнения, входы вторых сла гаемых первых сумматоров адреса с первой по четвертую групп подключены к входам .уровней сигналов "0", -1, "0", "-1" блока соответственно, информационный вход р-го модуля памяти соединен с вторым входом р-й схемы сравнения, выходы. всех схем сравнения образуют второй выход блока, входы второго слагаемого вторых сумматоров адреса с первой по четвертую груп подключены к входам уровней сигналов "0", "0", "-1" и "-1" соответственно.3. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок управления флагами сравнения содержит узел маскирования и циклического сдвига флагов сравнения, регистр флагов, шифратор и дешифратор, причем вход записи блока соединен с входом записи регистра флагов, выход которого соединен с входом шифратора, первый выход которого соединен с четвертым выходом блока, второй и третий выходы шифратора являются вторым и третьим выходами блока соответственно и соединены с информационным входом дешифратора, вход стробирования блока соединен с входом стробирования дешифратора, управляющий и информационный входы блока соединены с управляющим и информационными входами узла маскирования и циклического сдвига флагов сравнения, первый выход которого является первым выходом блока, второй выход узла маскирования и циклического сдвига флагов сравнения соединен с информационным входом регистра флагов, выход дешифратора соединен с входом маскирования информационного входа регистра флагов.

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

1444784 регистра длины строки соединен с входом первого слагаемого сумматора приращений адреса, выход которого соединен с вторым информационным входом

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

5 ° Устроиство по II ° 1 о T л и 15 ч а ю щ е е с я тем, что блок памяти данных содержит тридцать два сумматора адреса, образующих шестнадцать групп по два, шестнадцать модулей памяти и узел циклического сдвига, вхо- 20 ды чтения и записи блока соединены ,с входами чтения и записи всех модулей памяти соответственно, информационные входы всех модулей памяти соединены с информационным входом 25 блока, выход р-ro модуля памяти соединен с р-м информационным входом узла циклического сдвига, где р=1, ..., 16 выходы которого соединены с выходами блока, выход р-й группы сум- Зо маторов соединен с адресным входом р-го модуля памяти, младшие разряды по первой и второй координатам адресного входа блока соединены с входами управления сдвигом узла циклического сдвига, входы первого слагаемого первого и второго сумматоров адреса . всех групп соединены со старшими разрядами по первой и второй координатам адресного входа блока соответ- 40 ственно, входы второго слагаемого первых сумматоров адреса а-й группы и вторых сумматоров адреса б-й группы подключены к входу логического

Уровня сигнала -1 блока, где а 45

1,5,9,13 и б=1,...,4, входы второго слагаемого первых сумматоров адресов

s-й группы и вторых сумматоров адреса r-й группы подключены к входу логического уровня -.чгнала "0" блока, где в=2,6, 10, 14 и r=5,...,8, входы второго слагаемо го первых сумматоров адреса д-й группы и вторых сумматоров адреса е-й группы подключены к входу логического уровня сигнала "+ 1" блока, где д=З, 7, 1 1, 15 и. е=9, ..., 12, входы второro слагаемого первых сумматоров адреса ж-й группы и вторых сумматоров адреса з-й группы папклю" чены к входу логического уровня сигнала "+2" блока, где ж=4,8, 12, 6 и э=13, ° . °, 16.

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

И соответственно, выход четвертого элемента И соединен с вторым входом третьего элемента И, первые входы

19 !44 первого и второго элементов ИЛИ соединены с вторыми разрядами первой и второй координат адреса управляющего входа узла соответственно, вторые входы первого и второго элементов ИЛИ соединены через первый и второй элементы НЕ с первыми разрядами первой и второй координат адреса управляющего входа узла соответственно, третий разряд первой координаты адреса уп-!

4784 20 равляюшего входа узла соединен с входами управления сдвигом первого и второго входных схем сдвига первого

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

Таблица!

22

1444784

Т а б л и ц а 2

Описание

ДЩЧКЦМC( иере сван, Е Ффвrly аgлицаЗ 7ладыуе ,0(7Д,В9 Ф6/

ПАЛ

О/д

/ о/ /в

О&О

О r 0, gy

0 /

j r О

/ / / /

Рисвре Юлеке элеменюо6 фра2мен а ло одул м

ЛД "7Я М в r gg Фз 678ую44zr3Ьа

О r g,5 5 6 yg ggyeQrsrr, Д;/ Z уф 5 БЦ89/О/5ЖЛЙ (Р / б 7 4 сия.д /ф(5 г(ъ

723 О5б 7 f5 /ОЦЯ У1М

rz а ц î х г з ф 5 б 7 4 9 о Н

N vs ц д 3 О / 2 7 4 5 6 rr 4 9 r

gyqgrzggz s О r 67 ф5 /068 у

rg gg л я r g 3 з 5 6 7 4 У /О Н Г

9 /Онrzr5rgr$0 1 2 3 фх 6 7

Ц J g 0 y2 rg r g o 7 2 7 ф Х 6

roke/ 9rôrs23ü2,З< / б 7Ф

ЯЮЦlygфб12 УZ 50Х6 7

5 б 7 Р 9 ЮИr2.ВЦ(БО 1 2.5

7 ф . 6 rr я 9 r rxyz я rq5 О 2

6 74- » и У 34r

561 ф9roВ/ЯИбОу2 ge

О

2

5 (Р о

О

/

/

2

2.

1444784

Фиг.8 а блица 4

1444784

14лч73ч

1444784

1444784

ТЩ1

ТВ

11

ИУ

ВТ

/ТТ 11

Ю

07

78

11

88

Ю7

l8

Составитель В.Бородин

Редактор О.Спесивых Техред А.Кравчук Корректор М.Шароши

Заказ 6507/49 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ушгород, ул. Проектная, 4

Ф