Конвейерное буферное запоминающее устройство для систем обработки изображений

 

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

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

РЕСПУБЛИК (51)s G 06 F 12/00

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

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

ПРИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4745732/24 (22) 06.07.89 (46) 30.07.92. Бюл,"йг 28 (71) Институт автоматики и электрометрии

СО АН СССР (72) В.А.Слуев (56) Патент США

N. 5995253, кл. G 06 F 12/00, 1976.

Авторское свидетельство СССР

N. 1444784, кл, G 06 F 12/00, 1988, (54) КОНВЕЙЕРНОЕ БУФЕРНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО ДЛЯ СИСТЕМ ОБРАБОТКИ ИЗОБРАЖЕНИЙ (57) Изобретение относится к запоминающим устройствам и может быть использовано в системах с поточной обработкой двумерных данных. Цель изобретения — поИзобретение относится к запоминающим устройствам и может быть использовано в системах с поточной обработкой двумерных данных. например в процессорах фильтрации, корреляции, коррекции геометрических искажений.

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

Однако в известном буферном запоминающем устройстве невозможна конвейер„„. ЖÄÄ 1751769 А1 вышение быстродействия устройства, Запоминающее устройство содержит блок памяти адреса, блок очереди выходного адреса, блок преобразования адреса, коммутатор адреса, блок памяти данных, блок памяти очереди данных, блок управления, блок памяти адресов фрагментов данных, блок памяти очереди входного адреса, Устройство позволяет существенно сократить количество повторно извлекаемых из памяти двумерных данных, обеспечивает параллельность выборки двумерного фрагмента, одновременный контроль данных в четырех соседних сегментах изображения. В устройстве реализована предварительная выборка данных, эа счет чего существенно уменьшено время ожидания загрузки данных из системной памяти. 1 з.п. ф-лы, 10 фиг, ная обработка данных, что ограничивает его производительность, Цель изобретения — повышение быстродействия буферного запоминающего устройства.

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

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

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

35 информационным выходом блока памяти очереди выходного адреса, входы стробирования записи блока памяти адресов фрагментов данных, блока памяти адреса и

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

15 строки.

30 Блок 5 памяти данных содержит шестнадцать групп сумматоров 81 адреса, шест40

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

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

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

2 памяти выходногo адреса, блок 3 преобра- 2 эования адреса, коммутатор 4 адреса, блок

5 памяти данных, блок 6 памяти очереди данных, устройство 7 управления, блок 8 памяти адресов фрагментов данных, блок 9 памяти очереди входного адреса, линию 10 стробирования адреса фрагмента, шину 11 полного адреса фрагмента, линию 12 запрета записи данных. выходную шину 13 данных, линию 14 готовности выходных данных, выходную шину 15 адреса, линию 3

16 готовности адреса сегмента. линию 17 готовности входных данных. шину 18 входных данных, первый 19 и второй. 20 информационные выходы блока памяти адреса, первый выход 21 управления, второй инфоомационный выход 22. второй 23 и третий

24 выходы управления. первый информационный выход 25 блока памяти очереди выходного адреса. восьмой 26 и девятый 27 управляющие выходы блока управления, четвертый 28 и пятый 29 выходы управления блока памяти очереди выходного адреса, третий 30 и четвертый 31 управляющие выходы блока управления, второй выход 32 блока преобразования адреса, первый 33 и второй 34 информационные выходы, выход

35 управления блока памяти адресов фрагментов данных, седьмой 36, первый 37, второй 38, десятый 39 и одиннадцатый 40 управляющие выходы блока управления, четвертый 41 и пятый 42 входы блока управления, выход 43 коммутатора, выход 44 данных блока памяти очереди данных, двенадцатый 45 и тринадцатый 46 выходы блока управления, выход 47 блока памяти очереди входного адреса, четырнадцатый выход 48 чправления блока управления

Блок памяти очередного выходного сигнала содержит узел 49 памяти очереди, регистр 50 флагов сравнения, приоритетный шифратор 51, дешифратор 52, узел 53 маскирования и циклического сдвига, счетчик

54 единиц, первый выход счетчика 55 единиц, первый выход 56 узла маскирования и циклического сдвига, второй информационный выход 57 узла памяти очереди.

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

Блок памяти адреса содержит четыре группы сумматоров 64 адреса, четыре модуля 65 памяти, четыре схемы 66 сравнения, адреса и данных в модулях 65 памяти.

Узел 53 маскирования и циклического сдвига флагов сравнения содержит первый и второй входные схемы 67 и 6С сдвига первого каскада, входную схему 69 сдвига второго каскада, выходную схему 70 сдвига первого каскада, первый и второй выходные схемы 71 и 72 сдвига второго каскада, элементы И 73-76, элементы HE 77 и 78, элементы ИЛИ 79 и 80, надцать модулей 82 памяти, узел 83 циклического сдвига выходных данных с входами 84, Узел 83 циклического сдвига выходных данных содержит четыре схемы 85 сдвига первого каскада и групповую схему 86 сдвига второго каскада, Конвейерное буферное запоминающее устройство работает следующим образом.

На вход 11 поступают P разрядов, где

Р = logz М + logz N, задающие полный адрес элемента двумерной матрицы данных размерностью MxN, на.адресные входы блока

1 поступают разряды mi первой координаты, где l = 1, ..., logz М вЂ” 1, и разряды ni второй координаты, где i = 1, ..., togz N-1, на первый информационный вход блока 8 поступают младшие разряды пц первой координаты, где i = О, ..., logz — 1, и младшие разряды ni второй координаты, где i = О, ..., logz К-1, причем емкость блока 5 памяти данных составЛяет (LxK) элементов. На первый управляющий вход блока 2 поступают разряды

ГЛ0, m1, mZ И По, п1. П2 ПОЛНОГО ЭДРЕСЭ фРаГ мента.

Перед началом работы по сигналу начальной установки осуществляется обнуление всех ячеек памяти блока 1 адреса, 1751769 стирание содержимого блоков 6, В, g, 4g, Выходы 12, 42 блоков 8 и 6 устанавливаются в единичное состояние — разрешение записи данных. Выходы 35, 28. 41 блоков 8, 49 и

6 принимают нулевое значение, означающее отсутствие загруженных данных. Устройство 7 управления переходит в состояние, соответствующее точке А алгоритмов на фиг.5 и 6. Оператор 1 (фиг,5) осуществляет проверку сигнала на линии 29, являющегося индикатором загрузки данных а блок 49. Оператор 1 (фиг,6) осуществляет проверку сигнала на линии 35 выхода управления блока 8. При отсутствии данных в блоках 8 и 50 устройство управления циклически выполняет операции 1 на фиг,5 и 6.

Алгоритмы на фиг.б и 5 выполняются параллельно и не связаны между собой, Внешнее задающее устройство устанавливает адрес двумерного фрагмента на входе 11 и через промежуток времени t генерирует стробирующий импульс на линии

10, Нэ сумматоры 64 (фиг.7) каждого из четырех модулей 65 памяти поступают младшие разряды, а также разряды п11 и п1 полного адреса памяти, На выходах сумматоров устанавливаются полные адреса четырех сегментов, в которых могут располагаться элементы фрагмента (1), В схемах

66 сравнения старшие разряды полного адреса сегмента сравниваются с данными а соответствующем модуле памяти, адресуемыми младшими разрядами полного адреса сегмента. Разряды четырехразрядного выхода 20 блока 1 (флаги сравнения) для socстановления порядка расположения флагов, искаженного использованием функции раСпределения данных по модулям памяти, поступают на первый и второй входные схемы 67 и 68 сдвига первого каскада блока 53, а затем на выходную схему

69 сдвига первого каскада. В схемах 67 и 68;. управляемых разрядом rr-2 полного адреса памяти, осуществляется циклический сдвиг внутри групп флагов по два в каждой группе, во втором каскаде (схема 69), управляемом разрядом п2 полного адреса памяти, — циклический сдвиг групп. Для организации произвольной выборки фрагмента из блока

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

Поэтому четырехразрядный код признаков сравнения после корректировки положения данных поступает на схему маскирования, которая реализована ца базе элементов 72-80, Схема маскирования запрещает выборку ненужных сегментов из памяти исходного изображения, Маскирование флагов сравнения осуществляется

25

30 решения записи в модули памяти блока

1. Значения сигналов на шине 56 поступа40

50

5

10 разрядами mo, п11, по п1 полного адреса памяти, Выходами узла 53 маскирования и циклического сдвига являются два четырехразрядных выхода: сигналы разрешения записи в модули памяти блока 1 (выход 21) и флаги сравнения, модифицированные схемой маскирования (выход 56). Для корректной записи в модули памяти блока 1 старших разрядов адресов сегментов в схемах 70, 71, 72 сдвига (фиг,8) осуществляется обратная корректировка положения разрядов кода флагов сравнения. В схеме 70, управляемой разрядом m2 полного адреса памяти, меняется положение двух групп по два разряда кода флагов, в схемах 71 и 72, управляемых разрядом п2, изменяется положение рэзрядоа внутри групп, За время t на выходе 19 блока 1 формируется адрес базового сегмента, нэ выходе четырехразрядной шины 20- признаки наличия требуемых сегментов данных в блоке памяти 5. Значения разрядов шины 20 поступают на информационный вход узла 53 маскирования и циклического сдвига флагов сравнения, Под управлением разрядов

mp, П11, пч2 и пр, и), п2 шины 11 полного адреса фрагмента на первом выходе узла

53 формируется четырехразрядный код 56 флагов сравнения и сигналы шины 21 разют на второй информационный вход блока

49 памяти очереди и на входы счетчика 54 единиц, представляющего собой комбинационную логическую схему. На выходах 22 счетчика формируегся двоичный позиционный код, значение которого определяется количеством "единиц" на шине 56. В состав счетчика входит схема ИЛИ. входы которой подключены к разрядам шины 56, а выходом является выход 55 счетчика. Если хотя бы один из разрядов шины 56 установлен в единицу, то выход 55 блока 54 устанавливается а единичное состояние и разрешает загрузку базового сегмента и кода флагов сравнения в блок памяти 49.

После установки всех сигналов внешнее задающее устройство стробирующим импульсом на линии 10 загружает значения старших разрядов адресов затребованных сегментоа в модули памяти блока 1, значение базового сегмента на шине 19 и код флагов сравнения нз шине 56 в блок 49 памяти очереди. значение младших разрядоа первой и второй координат полного адреса фрагмента и выходное значение счетчика единиц на шине 23 в блок 8 памяти адресов фрагментов данных. После этого внешнее задающее устройство проверяет значение выхода 12 блока памяти адресов

1751769

10 фрагментов данных. Если блок памяти не заполнен, то повторяется загрузка нового фрагмента, Если выход 12 переходит в состояние "0", что означает полное заполнение памяти, загрузка прекращается, При загрузка данных в блок памяти 49 нэ выходе 28 устанавливается значение "1", положительный фронт которой загружает выходное значение кода флагов сравнения на выходе блока 49 в регистр флагов 50. В

10 состав приоритетного шифратора 51 входит схема ИЛИ, входы которой подключены к выходам регистра флагов, а выходом является линия 29. На линии 29 устанавливается значение "1". Алгоритм работы устройства управления при загрузке данных в буферную память представлен на фиг.5, После начальной установки устройство управления осуществляет циклическую проверку

15 состояния линии 28 (блок алгоритма 5-1), и

20 если она установлена в единичное состояние, анализирует состояние линии 29 (блок алгоритма 5-2), Если линия 29 установлена в единицу, устройство управления цикличености блока 6 памяти очереди данных принимать данные (блок алгоритма 5 — 3). Если блок 6 не заполнен, линия 42 установлена в единичное состояние. В этом случае уст30 ройство управления переключает коммутатор 61 адреса сигналом 30 так, чтобы выходы сумматоров 59 и 58 были подключены к входам регистра 62 (блок алгоритма

5-4), стробирует адрес nepeor о загружаемого сегмента в выходной регистр 62 адреса

35 сигналом на линии 31 (блок алгоритма 5 — 5), генерирует запрос к памяти исходного изображения на линии 16 (блок алгоритма 5 — 6), загружает младшие разряды адреса сегмента на шине 32 в блок 9 очереди входного

40 адреса сигналом на линии 45 (блок алгоритма 5-7).

Адрес загружаемого сегмента, содержащийся в регистре 62, формируется из адреса базового сегмента Ь ;, генерируемого в бло45 ке 1 памяти адреса, Полный адрес базового сегмента на шине 25, разделенный на адреса по первой координате и адреса по второй координате, подключен к первым входам соответственно сумматоров 58 и 59, Полный адрес сегмента с выхода сумматоров через коммутатор 61 поступает на вход регистра

62. Выходы регистра 50 флагов подключены к входам приоритетного шифратора в следующем порядке убывания приоритета; флаг сегмента b;-1,-1, флаг сегмента b;j-q, флаг сегмента b -i,1, флаг сегмента Ьц, Соответственно коды. генерируемые приоритетным шифратором для каждого флага, являющегося старшим в какой-то момент времени, 50

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

После установки адреса сегмента в регистре 62 и запроса к памяти исходного изображения на линии 16 блок 7 управления анализирует состояние линии 17 готовности данных (блок алгоритма 5-8}. Когда на входе 18 устанавливаются истинные данные, что сопровождается изменением состояния линии 17, блок 7 управления генерирует строб записи данных, на линии

40 в блок 6 памяти очереди данных (блок алгоритма 5-9). Далее устройство управления снимает сигнал истинности данных на линии 16 (блок алгоритма 5 — 10) и стробирует выходы дешифратора 52 сигналом на линии

27 (блок алгоритма 5 — 11). По заднему фронту этого импульса осуществляется сброс флага в регистре 50, соответствующего загруженному сегменту, После этого устройство управления анализирует состояние линии 29 (блок алгоритма 5-12). Если в регистре 50 флагов имеются установленные в единицу разряды, то устройство управления переходит к выполнению блока 5 — 3 алгоритма и процесс считывания сегментов продолжается до обнуления регистра флагов 50, что будет зафиксировано изменением со-, стояния линии 29. В этом случае устройство управления сигналом на линии 26 осуществляет разгрузку памяти очереди 49 (блок алгоритма 5-13) и переходит к выполнению блока 5-1 алгоритма на фиг.1.

Алгоритм работы устройства управления при разгрузке данных из буферной памяти представлен на фиг.6. После начальной установки устрОйство управления циклически анализирует состояние линии 35 готовности данных на выходе блока 8 адреса фрагмента, При загрузке данных в блок 8 значения адреса фрагмента на шине 11 и разрядов шины 22 с некоторой задержкой устанавливаются на выходных шинах 33 и

34 блока 8, выход 35 устанавливается в единичное состояние, Устройство управления анализирует состояние шины 34 (блок алгоритма 6 — 2), и если для выборки фрагмента из памяти данных 5 необходйма подкачка дополнительных сег лентов, т,е. на шине 34 содержится ненулевое значение кода, устройство управления запоминает его значение (блок алгоритма 6 — 3). Далее устройство управления циклически анализирует состояние линии 41 готовности данных на выходе блока 6 (блок алгоритма 6 — 2). Если данные были загружены, то устройство управления сигналом на линии 36 подключает выходную

1751769

5

20

40

50

55 шину блока 9 к адресным входам 43 блока памяти 5 (блок алгоритма 5-6) и загружает требуемый сегмент данных в блок памяти 5 сигналом на линии 38 (блок алгоритма 6 — 6).

После этого устройство управления сигналом на линии 46 и сигналом на линии 39 разгружает блок 9 памяти очереди входного адреса и блок памяти 6 очереди данных (блок алгоритма 6-7), вычитает единицу из внутреннего счетчика числа сегментов (блок алгоритма 6-8) и, если он равен нулю, повторяет блоки алгоритма 6-4, 6 — 5, 6 — 6, 6 — 7, 6 — 8 до обнуления внутреннего счетчика, Когда все требуемые сигналы бу дут загружены, устройство управления сигналом на линии 36 переключает коммутатор 4 в положение, обеспечивающее nро.хождение на выход 43 разрядов шины 33 (блок алгоритма 6-10), запускает цикл чтения блока 5 сигналов на линии 37 (блок алгоритма 6 — 1) и через промежуток времени, необходимый для считывания данных, устанавливает сигнал готовности данных в блоке 14 (блок алгоритма 6 — 12). Далее устройство управления после задержки, необходимой для передачи данных во внешнее приемное устройство (блок алгоритма

6-13), сигналом на линии 38 осуществляет разгрузку блока 8 (блок алгоритма-6-14) и переходит к выполнению блока 6-1 алгоритма на фиг.6, Предлагаемое конвейерное устройство буферной памяти предназначено для поточной обработки фрагментов двумерных данных размеров 4х4 элемента. Данные с произвольным адресом извлекаются из памяти исходных данных в устройство буферной памяти и записываются в память выходных данных выходным обрабатывающим процессором. Память исходных данных емкостью MxN элементов, а также память блока запоминающих устройств

Данных емкостью LxP элементов (M, N, 1, P — степени числа 2) разбиваются на сегменты 4х4 элемента. В памяти исходных данных содержится M/4xN/4, а в буферной памяти L/4xP/4 сегментов. Сегмент является единицей данных при загрузке

:.данных в буферное запоминающее устройство. Блок 1 памяти адреса содержит L/4

Р/4 ячеек памяти (по одной на каждый сегмент), в которых хранятся старшйе разряды адресов сегментов, При генерации адреса фрагмента с произвольным адресом его элеМенты могут лежать в разных сегментах, В блоке 1 осуществляется параллельньгй контроль за данными, содержащимися в блоке памяти данных в четырех соседних сегментах. При отсутствии даннь х требуемый сегмент загружается из памяти исходных данных, после чего возможна выборка по произвольному адресу. В зависимости от адреса возможна загрузка от одного до четырех сегментов, Для организации парал-. лельного контроля данных, а также параллельной выборки фрагмента по произвольному адресу в блоки 1 и 5 введены узлы вычисления адресов, узлы циклического сдвига данных, что обеспечивает параллельность выборки.

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

Bm-1,п-1 ат — 1,п Bm-1,п+1, Bm-1,n+2

A(m,Ï) = B,п 1 à,, à,n+1 Bm,п+г (1) а,.+1,n 1 Bm+1, а„+1,n+1 а„+1n+2

Bm+2, и — 1 Bm+2,п Bm+2,n+1 Bm+2.n+2. где m, и — индексы, определяющие адрес фрагмента, причем 0 < m < L и 0 < n < р;

am,п — центральный элемент фрагмента.

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

А (m+i, n+J) = P (m+i)+ (n+j), (2) где 1 и J — целые числа, изменяющиеся в пределах-1

Р— длина строки; п1 и n — координаты центрального элемента.

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

4 4 где ".=" — символ, обозначающий операцию взятия остатка от деления; и (m,n) — номер модуля памяти (О «<

<à <15).

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

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

44 4 (4) где "-" — символ, обозначающий операцию взятия целой части деления.

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

1751769

Использование функции (3) приводит к нарушению естественного расположения элементов фрагмента, извлекаемо о из памяти, Для восстановления порядка расположения данных используется блок 83 (фиг.10), представляющий собой комбинационную схему, состоящую из двух каскадов, Первый каскад осуществляет циклический сдвиг внутри четырех групп данных и управляется разрядами по и п1 полного адреса памяти, второй каскад осуществляет циклический сдвиг самих групп данных и управляется разрядами m< и m> полного адреса памяти, Пусть MxN — размерность массива данных, хранящегося в памяти исходного изображения, хР— размерность массива данных, хранящегося в БД буферного запоминающего устройства. Разрядность шины полного адреса памяти двумерного фрагмента (1) можно представить выражением

Ар (!ОЯг + logy ) + (!09г — +

М N ! Р 4

+ !оцг — )+4, P

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

M N

0 =-! оцг — + !оцг — + T, ! P где Т вЂ” добавочный двоичный разряд истинности данных.

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

+!о9г — двоичных разрядов. Ввиду того, P

4 что в БД осуществляется выборка фрагмента с переходом через границы сегмен-. та, в состав адресной шины БД (блок 5) входят также разряды mo, m>, no, n<, Элементы фрагмента (1) могут находиться в одном, двух или четырех сегментах, С целью параллельной проверки на предмет наличия или отсутствия требуемых сегментов в БД в

БА организована двумерная выборка фрагмента 2х2 элемента вида

bl-ц-! bl-ц

5 В(Ц) =

Ьц-! !,! где i, j — индексы, определяющие адрес фрагмента, пРичем 0 i Я 4, 0 N j < 4

L Р.

10 bi,! — центральный элемент фрагмента.

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

4

P х — распределены по четырем модулям па4

15 мяти s соответствии с функцией распределения (.)) =2-,+2. () где а (Ц) — номер. модуля памяти, причем

0 а «3, Адреса элементов массива в модулях памяти определяются формулой

Р )

82

А(!, !) = — — +

Так же, как и в памяти данных, использование функции (7) приводит к зависимости порядка расположения выходных данных модулей памяти Ао. А1, Аг, Аз от адреса извлекаемых сегментов. Однако, в отличие от схемы перестановки данных, . используемой в БД, корректировке подвергается порядок расположения флагов сравнения, Во время загрузки данных внешнич задающим устройством подкачка данных иэ памяти исходных данных требуется только для части адресов фрагментов, В блок 8 загружаются младшие разряды всех адресов фрагментов. Каждое загруженное слово сопровождается трехразрядным кодом, содержащим информацию о числе сегментов данных, которые должны быть загружены в буферную память. В блок 49 загружатся ад45 реса базовых сегментов данных и четыре флага, определяющие необходимость загрузки четырех соседних сегментов данных.

Адрес базового сегмента и флаги формируются в блоке 1. Каждое загруженное в блок

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

6, 8, 9, 49 в предлагаемом устройстве буферной памяти осуществляется предвари55 тельная выборка данных и параллельная работа алгоритмов загрузки и разгрузки данных.

Пусть память очереди адресов фрагментов содержит шестнадцать ячеек, внешнее задающее устройство генерирует шестнад1751769

5 с адресам фрагментов. После загрузки в блок

8 первого адреса фрагмента, а в блок 49 10 адреса базового сегмента устройство 7 упзирует состояние линии 41 (алгоритм на фиг,6). Когда данные, необходимые для вы- 15 борки первого фрагмента, загружены и он

35

50 цать полных адресов фрагментов данных на шине 11 и требуется подкачка данных только для первого адреса фрагмента и шестнадцатого. После загрузки шестнадцатого адреса в блок 8 выход 12 устанавливается в состояние "0", запрещая дальнейшую загрузку. В блок 49 будут загружены два слова, соответствующие первому и последнему равления осуществляет загрузку данных (алгоритм на фиг.5) и одновременно аналибудет считэн из блока 5 памяти, устройство управления параллельно выполняет два алгоритма — последовательное считывание фрагментов данных со второго по пятнадцатый, для которых не нужна подкачка данных из блока 5 и загрузка данных в блок 6 из памяти исходных данных, необходимых для считывания шестнадцатого фрагмента. Когда потребуются данные шестнадцатого фрагмента, они уже будут загружены в блок 6.

B предлагаемом буферном запоминающем устройстве в качестве блока 9 памяти очереди входного адреса и блока 6 памяти очереди данных использованы стандартные блоки памяти типа FIFO (FIRST INPUT, FIRSTOUTPUT), аналогичные блокам 8 и 49, изображенным на фиг.4(а) и фиг.4(б).

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

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

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

1751769

18 входом блока памяти данных, двенадцатый и тринадцатый выходы блока управления соединены с входами загрузки и разгрузки данных блока памяти очереди входного адреса, четырнадцатый выход блока управле- 5 ния - с входом разгрузки данных блока памяти адресов фрагментов данных, ïåðвый и второй информационные выходы блока памяти адресов фрагментов данных соединены соответственно с вторым инфор- 10 мационным входом коммутатора и с шестым входом блока управления, седьмой вход которого соединен с выходом готовности выходных данных блока памяти адресов фрагментов данных. "-15

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

1751769

1751769

1751769

1751769

5б

5б

1751769

13

Составитель С, Шустенко

Техред М;Моргентал Корректор Л. Филь

Редактор М. Циткина

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

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

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

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