Устройство для вычисления скользящего среднего

(51)5 С 06 Р 15(3 ИЯМ ЕЛЬСТВ 14 Ахметьян ьство ССС536, 198 тво СССР 5/36, 198 1 ЧИСЛЕНИ С К к авто и хник может ства тр об та И лени в виоб- ретествия мер, и ыстроде ЗОГОСУДАРСТВЕННЫЙ НОМИПО ИЗОБРЕТЕНИЯМ И 07 НРПРИ ГННТ СССР ОПИСАНИЕН АВТОРСКОМУ СВИ(57) Изобретение отнотике и вычислительнойбыть использовано восуществляющих весовуровой инйормации, преде массивов чисел (наработке изображений),ния является повышени устройства для вычисления скользящегосреднего. Печь достигается путем параллельной обработки элементов исходного массива несколькими окнами, Приэтом параллельно вычисляются несколькозначений скользящего среднего с учетомвесовых Аункций. Устройство содержитблок 1 памяти массива, счетчик 2 номера базовой строки массива, счетчик8 номера столбца маски, блок 9 умножения, накапливающий сумматор 10,делитель 11, регистр 12 делителя,блок 13 элементов И, регистр 14 числа столбцов маски, блок 15 умножения, сумматор 16, триггер 17, элементы И 18-23, элемент НЕ 24, элементИЛИ-НЕ 25, блок 26 элементов И, элемент ИЛИ 27, синхронизатор 28, выходИзобретение относится. к вычислительной технике и автоматике и предназначено для определения скользящегосреднего по выбранному скользящемуокну с наложенной на него маской весовой ункции в устройствах обработкицифровой информации, представленнойв виде массивов чисел (например, приобработке изображений)1011 елью изобретения является повышение быстродействия устройства длявычисления скользящего среднего по -средством параллельного вычисленияпо нескольким окнам нескольких значений скользящего среднего с учетомвесовых АункцийНа чертеже представлена функциональная схема устройства для вычисления скользящего среднего. 20Устройство содержит блок 1 памяти(массива размером ш х и), счетчик (помодулю ш - 1 + 1 номера базовой строки массива) 2, счетчик (по модулюи номера столбца) 3, счетчик (по модулю к номера текущей строки 4), сумматор (адреса чтения) 5, блок б хранения маски, счетчик (по модулю 1номера строки маски) 7, счетчик (помодулю 1 номера столбца маски) 8,блок 9 умножения (на весовой коэффициент), накапливающий сумматор 10,делитель 11, регистр (делителя) 12,блок 13 элементов И, регистр (числастолбцов маски) 14, блок 15 умножения, сумматор 16, триггер (разрешениязаписи) 17, элементы И 18-23, элементНГ 24, 1.-входовой элемент ИЛИ-НГ 25,бпок 26 элементов И, элемент ИЛИ 27,синхронизатор 28, выход "Конец ряботы" 29 устройства и тактовый вход30 устройстваЭлементы 6-20 образуют х-й узелвычисления среднего, а элементы 1416 - схему адресации блока хранения 45маски в -м узле вычисления среднего,Устройство работает следующим образом,В исходном состоянии блок 1 содержитмассив размером ш строк на и столбцов, Лля определенности будет считатьш = и = 2, где . - целое число, Тогда содержимое блока 1 расположено,начиная с ячейки с адресом О, построчно, причем начало второй строки изображения расположено в ячейке с адресом 2, начало третьей строки - в11ячейке с адресом 2 и т,д, Содержимое счетчиков 2-4 равно О, На управляющий вход блока 26 элементов И подан разрешающий сигнал, который сформирован на 1-входовом элементе ИЛИ-НЕ25 и соответствует отсутствию сигналов переполнения счетчиков 8 В сумматор 5 на информационные входы подается содержимое счетчиков 2 и 4. Число младших разрядов адреса блока 1 памяти, подключаемых к счетчику 3, соответствует степени числа 2,. Это чис"ло определяет количество столбцовмассива В блоки б узлов вычислениясреднего записаны коды элементовмаски размером 1 с х 1Иаска представляет собой окно,которым сканируется исходный массивСканирование производится путем поочередного наложения 1 окон-масокна массив со сдвигом вдоль строкидруг относительно друга, Просмотрмассива осуществляется в пределахЕ строк изображения по столбцамСчетчикии триггеры 17 в исходном состоянии обцулены, а счетчики 8,начиная с второго узла вычислениясреднего, установлены в состоянии1 - Ь +1, где Ь - номер узла (Ь2. 1.), Счетчик 8 первого узлаобнулен. В регистры 14 записан кодчисла, соответствующего числу столбцов в маске, накапливающий сумматор10 обнулен, а в регистр 12 записанкод числя, на которое должна бытьразделена в дальнейшем сумма взвешенных элементов массива внутри маскиЭто число определяется размерами маски и значениями его элементов Элементы маски могут быть отрицательнымиУправление Аункционированиемустройства осуществляется с помощьюсинхронизатора 28, По тактовым импульсам, поступающим на тактовыйвход 30, осуществляется выдача управляющих импульсов (УИ) в устройство,11 о первому тактовому импульсу осуществляется выдача первого управляющего импульса 1 УИ (второй выход синхронизатора), который через элемент ИЛИ 27 поступает на управляющий вход сумматора 5, в котором осуществляется вычисление кода номера строки массива путем сложения номеров базовой строки из счетчика 2 и текущей строки из счетчика 4. Кроме того, 1 УИ поступает на управляющий вход516 блока 15 умножения, в котором осуществляется перемножение числа столбцов в маске, код которого хранится в регистре 14, с номером строки маски, код которого хранится в счетчике 7, с целью вычисления смещения адреса элемента маски в блоке 6 в соответствии с номером требуемой 42478устройства таким триггером являетсятриггер 17 второго узла вычислениясреднего, во втором цикле - триггертретьего узла вычисления среднегои т,д. Кроме того, установка в "1"триггера 17 приводит к выдаче сигналазапрета на управляюгий вход блока26 элементов И через элемент ИЛИ-НЕ15 2 О 25о30 строки маски.По второму тактовому импульсу выдается 2 УИ (9-й выход синхронизатора), по которому сумматором 16 формируются адреса элементов маски в узлах вычисления среднего.По третьему тактовому импульсу выдается 3 УИ (5-й выход синхронизатора) который поступает в блоки 1 и 6 на входы разрешения чтения. В результате с выходов блоков 1 и 6 передаются значения элемента массива и элементов маски в блоки 9 узлов вычисления среднего,По четвертому тактовому импульсувыдается 4 УИ (9-й выход синхронизатора), который поступает на управляющие входы блоков 9 умножения,в которых осуществляется перемножение выбранного элемента массива с егвесом, определяемым маской,По пятому тактовому импульсу выдается 5 УИ (3-й выход синхронизатора), который поступает на управляющий вход накапливающего сумматора10, В сумматоре происходит накопление результатов умножения в блоке 9,Кроме этого, 5 УИ поступает на входсчетчиков 4 и 7, увеличивая их содержимое на 1.По шестому тактовому импульсу выдается 6 УИ, (7-й выход синхронизатора), который поступает на счетныйвход счетчика 7. В том случае, еслипроизошло его переполнение, и,пульспереполнения проходит на вход счетчика.8, увеличивая его содержимоена 1. Переполнение счетчиков 7 и 4происходит одновременно. В случае,если этого не происходит, последуюгие тактовые импульсы в цикле работыустройства не производят никакихдействий, так как триггеры не изменяют своего состоянияЕсли при увеличении содержимого счетчика 8 нав одном из узлов вычисления среднего произошло переполнение этогосчетчика, сигнал с его выхода установит в "1" триггер 17 соответствуюгего узла. В первом цикле работы 35 40 45 50 55 25 и сигнала разрешения прохождения8 УИ через элемент И 21, а также команды записи в блок 1 через элемент И 22,По седьмому тактовому импульсу выдаетсяУИ (10-й выход синхронизатора), которьп через элемент И 19 по разрешающему сигналу триггера 17 соответствусщего узла вычисления среднего выдает управляющий сигнал в делитель 11. В этом блоке содержимое накапливающего сумматора 10 делится на содержимое регистра 12 иследовательно, вычисляется текугее значение скользящего среднего по данной маске,По восьмому тактовому импульсу выдается 8 УИ (1-й выход синхронизатора), которьп через элемент И 20 по разрешающему сигналу триггера сбрасывает содержимое накапливающегосумматора 10 соответствующего узла вычисления среднего и открывает блок 13 элементов И, через которьп на. вход блока 1 подается код вычисленного по 7 УИ скользягего среднего. Кроме этого, 8 УИ через элементы И 21 и элемент ИЛИ 27 поступает на управляющий вход сумматора 5, которьп передает на адресньп вход блокЫ 1 номер строки для записи полученного в узле вычисления среднего значения.По девятому тактовому импульсу вырабатывается 9 УИ (б-й выход синхронизатора), который через элемент И 22 поступает на вход записи в блок 1. По этой команде в блок 1 записывается значение скользящего среднего, вычисленное в узле вычисления среднего по 7 УИ.По десятому тактовому импульсу вырабатывается 10 УИ (4-й выход синхронизатора), которьп сбрасывает в "0" соответствующий триггер 17 узла вычисления среднего и увеличивает содержимое счетчика 3 на 1, Если переполнения счетчика 3 не произошло, то цикл работы устройства повторяетоя. Если произошло переполнение счетчика 3, выдается счетньп импульс всчетчик 2, увеличивая его содержимое на "1". Если переполнения счетчика 2 не произошло, то цикл работы устройства повторяетоя. Если произошло переполнение счетчика 2, то по выходу "Конец работы" 29 выдается сигнал об окончании работы устройства. Это означает, что в блоке 1 памяти хранится матрица значений скользящего среднего, причем первые 1-1 столбцов и последние 1-1 строк не должны использоваться для дальнейшей работы.Ф о р м у л а изобретенияУстройство для вычисления скользящего среднего, содержащее блок памяти, элемент ИЛИ, три элемента И,первьп счетчик, синхронизатор, первый 2 Овыход которого подключен к первомувходу первого элемента И, о т л и -ч а ю щ е е с я тем, что, с цельюповышения быстродействия, в неговведены элемент ИЛИ-НЕ, два счетчика, сумматор, блок элементов И, узлывычисления среднего, каждьп из которых содержит два счетчика, три элемента И, триггер, два регистра, дваблока умножения, сумматор, накапливающий сумматор, блок хранения маски, делитель и блок элементов И,выход первого элемента И подключенк первому входу первого элементаИЛИ, к второму входу которого подключен второй выход синхронизатора, выход первого элемента ИЛИ подключенк тактовому входу сумматора, входыпервого и второго слагаемых которого.подключены соответственно к выходупервого счетчика и выходу блока элементов И, разрядные входы сумматораподключены к старшим разрядам адресного входа блока памяти, первьп входблока элементов И соединен с выходомвторого счетчика, счетньп вход которого соединен с третьим выходом синхронизатора, выход переполнения второго счетчика соединен с первымвходом второго элемента И, второйвход которого подключен к четвертомувыходу синхронизатора, выход второгоэлемента И соединен со счетным входом третьего счетчика, разрядныевыходы которого подключены к младшимразрядам адресного входа блока памяти,выход переполнения третьего счетчикаподключен к счетному входу первогосчетчика, выход гереполнения которого является выходом "Конец работы" устройства, вход разрешения чтения блокапамяти подключен к пятому выходусинхронизатора, вход разрешения записи блока памяти подключен к выходутретьего элемента И, первый вход которого подключен к шестому выходу синхронизатора, второй вход третьегоэлемента И соединен с вторым входомпервого элемента И, управляющим входом блока элементов И и подключен квыходу элемента ИЛИ-НЕ, каждый извходов которого объединен с первымивходами первого и второго элементовИ соответствующего узла вычислениясреднего и подключен к прямому вьжо.ду триггера одноименного узла вычисления среднего, в каждом узле вычисления среднего инверсньп вход триггера подключен к четвертому выходу синхронизатора, а прямой - к выходу переполнения первого счетчика этогоузла вычисления среднего, счетныйвход первого счетчика данного узлавычисления среднего подключен к выходу третьего элемента И этого узлавычисления среднего, первый входкоторого подключен к седьмому выходусинхронизатора в каждом узле вычисления среднего, а второй вход подключен к выходу переполнения второгосчетчика этого узла вычисления среднего, в каждом узле вычисления среднего счетньп вход второго счетчикаподключен к третьему выходу синхронизатора, выход второго счетчика подключен к входу первого сомножителяпервого блока умножения данного узлавычисления среднего, вход второгосомножителя первого блока умноженияподключен к выходу первого регистраодноименного узла вычисления среднего, тактовый вход первого блокаумножения в каждом узле вычислениясреднего подключен к второму выходусинхронизатора, выход первого блокаумножения данного узла вычислениясреднего подключен к первому информационному входу сумматора данногоузла вычисления среднего, второй информационный вход сумматора подключен к выходу первого счетчика этогоузла вычисления среднего, в каждомузле вычисления среднего тактовыйвход сумматора подключен к восьмомувьжоду синхронизатора, выход сумматора подключен к адресному входу блокахранения маски данного узла вычислеЗаказ 1148 Тираж 414 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб д, 4/5 Производственно в издательск комбинат "Патент", г.ужгород, ул, Гагарина,101 ния среднего, в каждом узле вычислениясреднего вход разрешения чтения подключен к пятому выходу синхронизатора,информационный выход блока хранениямаски каждого узла вычисления среднего подключен к входу первого сомножителя второго блока умножения данного узла вычисления среднего, входвторого сомножителя которого подключен к информационному выходу блокапамяти, тактовый вход второго блокаумножения каждого узла вычислениясреднего подключен к девятому выходусинхронизатора, выход второго блокаумножения подключен к информационномувходу накапливающего сумматора своегоузла вычисления среднего, вход синхронизации которого в каждом узле вычисления среднего подключен к третьему 0выходу синхронизатора, вход установкинуля накапливающего сумматора объединен с управляющим входом блока элементов.И своего узла вычисления среднего и подключен к выходу первого 25элемента И .этого узла вычисления среднего, второй вход первого элемента Ив каждом узле вычисления среднегоподключен к первому выходу синхронизатора, выход накапливающего сумматора подключен к входу делимогоблока деления данного узла, вход делителя блока деления подключен к выходу второго регистра этого узла вычисления среднего; тактовый вход блока деления подключен к выходу второгоэлемента И своего узла вычислениясреднего, второй вход которого вкаждом узле вычисления среднего подключен к десятому выходу синхронизатора, выход блока деления подключенк входу блока элементов И данногоузла вычисления среднего, выходыблоков элементов И всех узлов вычисления среднего через схему МОНТАЖНОЕИЛИ подключены к соответствующимразрядам входа записи информацииблока памяти, тактовый вход синхронизатора является тактовым входомустройства.