Устройство для анализа случайных чисел

 

Изобретение относится к области вычислительной техники и предназначено для использования в специализированных вычислительных устройствах при обработке одномерных массивов данных. Цель изобретения - расширение функциональных возможнос-г тей за счет операции медианной фильтрации одномерных массивов. Указанная цель достигается введением в устройство счетчиков, блока памяти, регистров, схемы сравнения, дешифратора , м льтиплексора, D-триггера, элементов задержки, элементов НЕ, элементов И, ИЛИ, Р11ТИ-НЕ, одновибраторов, группы элементов И. Устройство позволяет наряду с операцией определения максимального (минимального ) числа вьтолнять операцию медианной фильтрации. 2 ил. СО ю сд о ю 00 00

СОЮЗ СОБЕТСНИХ

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

РЕСПУБЛИК

151) 4 С 06 Р 15/36

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

H A BTGPCHGMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (2)) 3860014/24-24 (22) 20.02.85 (46) 23.09.86. Бюл. № 35 (71) Львовский ордена Ленина политехнический институт им. Ленинского комсомола (72) А.В.Василькевич, В.N.Êðèùèøèí и Н.В.Черкасский (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 911509 кл. С 06 Р 7/04, 1980.

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

¹ 771665, кл. G 06 F 7/04, 1978. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА СЛУЧАЙHbIX ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и предназначено для использования в специализированных вычислительных устройствах при обработке одномерных массивов данных. Цель изобретения расширение функциональных возможнос-, тей за счет операции медианной фильтрации одномерных массивов. Указанная цель достигается введением в устройство счетчиков, блока памяти, регистров, схемы сравнения, дешифратора, мультиплексора, D-триггера, элементов задержки, элементов НЕ, элементов И, ИЛИ, ИЛИ-HE одновибраторов, группы элементов И. Устройство позволяет наряду с операцией определения максимального (минимального) числа выполнять операцию медианной фильтрации. 2 ил.

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

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

На фиг.1 представлена функциональная схема устройства; на фиг.2 временная диаграмма работы устройства.

Устройство содержит второй счетчик l первый счетчик 2, третий и четвертый счетчики 3 и 4, блок 5 памяти, первый регистр 6, третий регистр 7, четвертый регистр 8, второй регистр 9, первая и вторая схемы 10 и 11 сравнения, дешифратор

12, мультиплексор 13, D-триггер 14, генератор 15 тактовых импульсов, второй и первый элементы 16 и !7 задержки, элемент НЕ 18, третий, второй и первый элементы И 19, 20 и ?1, группу элементов И 22, четверI тый элемент И 23, элементы ИЛИ 24-26, элемент И-ИЛИ 27, одновибраторы 28 и 29, вход 30 выбора режима устройства, вход 31 начальной установки устройства, группа входов 3? и 33 выбора режима устройства, вход 34 пуска устройства, вход 35 задания длины массива устройства, информационный выход 36 устройства, выход

37 синхронизации устройства и выход

38 окончания операции устройства.

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

В исходном состоянии в блоке 5 памяти записана исходная последовательность, причем в начале и конце. массива прописаны минимальные зна-чения (нулевые), количество которых

К-1 равно, где К вЂ . длина апертуры, нечетко число. Это необходимо для снижения краевых эффектов.

9288

35!

О; памяти) больше числа на второй группе входов (выходы регистра 6) .

5

fS

2

Рассмотрим пример медианной фильтрации последовательности: 1, 5, 3, 2, 7, 10, 1. Пусть длина апертуры равна 3. Тогда массив чисел, записанный в блоке 5, имеет вид: О, 1, 5, 3, 2, 7, 10, 1, О.

Упорядочение подмассива, длина которого равна длине апертуры, выполняется методом выбора наибольших значений в каждом цикле с блокировкой их в следующих циклах. В первом цикле среди первых трех чисел определяется максимальное (5). Его мы должны не учитывать во втором цикле.

Во втором цикле определяем наибольшее число (1). Количество циклов, необходимых для нахождения медианы, К+1 равно ††. В нашем случае при К=З

Ъ

3+! — 2. Таким образом число (1)

2 является медианой в окрестности первого элемента массива.

Сдвигаем апертуру на один элемент и определяем медиану среди чисел:

1, 5 3. Медиана будет равна 3. После выполнения семи этапов поиска медианы находим отфильтрованную последовательность: 1, 3, 3, 3, 7, 7, 1

Устройство работает следующим образом.

На вход 30 выбора режима и на вход 32 поступает уровень логической

"1". Единичный уровень по входу 30 поступает на управляющий вход схемы

10 сравнения и устанавливает ее в следующее состояние: на выходе будет единичный сигнал, если число на пер вой группе входов (выходы блока 5

TIo сигналу 31 начальной установки (фиг.2 а) сбрасываются в "О" счетчики 1-4, в регистр 9 по входам 34 и

35 заносится длина обрабатываемого массива. Кроме того, сигнал с входа

31 проходит через элементы ИЛИ 24 и сбрасывает в "О" регистр 8 (признаков) и через элемент ИЛИ 25 сбра,сывает триггер 14 (пуска), а также проходит через элемент И 20, на второй вход которого поступает разрешение по входу 30 устройства, и через элемент ИЛИ 26 сбрасывает в "0" регистр 6, По входу 34 поступает сигнал

"Пуск" (фиг.2 б) на Р-вход триггера

14 и по переднему фронту импульса с

1259288 генератора 15 тактовых импульсов (фиг.2 в), который поступает на вход синхронизации триггера, триггер устанавливается в единичное состояние (фиг.2 г) и разрешает про- 5 хождение тактовых импульсов через элемент И 23 (фиг. 2 д).

Если число, считанное иэ блока

5 памяти, больше числа, хранящегося в регистре 6,.то с выхода схемы сравнения единичный сигнал разрешения разрешает прохождение тактового импульса через элемент И 21 !фиг.2 e) на вход записи регистра 6 и большее число заносится в регистр 6. В противном случае тактовый импульс на вход записи регистра 6 не поступает, а в регистре 6 остается прежнее число. На третий вход элемента И 20 поступает разрешение с мультиплексора 13, который подключает соответствующий сравниваемому числу разряд регистра 8 (признаков). Так как разряды регистра 8 сброшены в "0", а мультиплексор имеет инверсию на своем выходе, то в первом цикле на входе элемента И 20 будет логическая "1".

По тактовым импульсам (фиг.2 д) происходит прибавление единицы в 30 счетчиках 2 текущего адреса и в счетчике 3, который управляет мультиплексором, обеспечивая поочередное ,подключение выходов регистра 8 признаков на вход элемента И 21. Счетчик

3 представляет собой счетчик с пересчетом К, где К длина апертуры. Коли.чество разрядов в регистре 8 также равно длине апертуры К.

По сигналу с выхода элемента И 21 .40 (фиг.2 е), когда число в блоке 5 памяти больше числа в регистре 6, происходит запись содержимого счетчика

3 в регистр 7. 3а К тактов в регистр

6 выбирается наибольшее число в под- 45 массиве из .К чисел, а в регистр 7 заносится его адрес.

На выходе переноса счетчика 3 формируется импульс переноса (фиг. 2ж), который поступает на вход одновибра- 50 тора 28. Последний формирует короткий импульс (фиг.2 з), который поступает на первые входы группы элементов И, 22 и через элемент 17 задержки и элемент ИЛИ 26 сбрасывает регистр 55

6. Элемент 17 задержки задерживает импульс сброса регистра 6 на время, необходимое для считывания медианы из регистра 6. Адрес наибольшего числа, хранящийся в регистре 7,,qeшифруется с помощью дешифратора 12, выходы которого соединены с вторыми входами элементов И 22. Импульс с одновибратора проходит через соответствующий наиболыпему числу элемент

И 22, на второй вход которого поступает разрешение с дешифратора 12 и устанавливает в единицу соответствующий разряд регистра 8. Это необходимо для блокировки в следующем цикле наиболыпего числа. В следующем цикле в регистр 6 выбирается второе по величине число в подмассиве из К чисел и записывается вторая единица в соответствующий разряд регистра 8.

Сигнал с одновибратора 28 поступает на вход прибавления единицы счетчика

4. Счетчик 4 является счетчиком с

К+! пересчетом -2--, где К вЂ” апертура, К+1 а — — — номер элемента посередине

K+1 апертуры т.е. медиана. За ——

Э

2 циклов в регистр 6 будет выбрано значение первой медианы. На выходе счетчика 4 появляется сигнал переноса (фиг.2 и), по которому одновибратор 29 формирует короткий импульс (фиг.2 к), который проходит через элемент ИЛИ 24 и сбрасывает в "0" регистр 8, а также проходит через элемент И-ИЛИ 27, на второй вход которого подается разрешение по входу 32 на выход 37 синхронизации устройства, сообщая, что на информационных выходах устройства находится значение медианы, и поступает на вход прибавления единицы счетчика 1 (начального адреса) и на вход элемента

16 задержки. По сигналу с выхода элемента задержки (фиг.2 л) увеличенное на единицу значение начально- го адреса переписывается в счетчик 2 (текущего адреса). Таким образом, обеспечивается. сдвиг апертуры.

Еще за

К+1 циклов определяется

К+1 вторая медиана и т.д. За n ° циклов, где n — длина обрабатываемого массива, определяются и медиан.

В последнем цикле содержимое счетчика 1 начального адреса становится

;равным содержимому регистра 9 длины

f массива и схема 11 сравнения выраi259288 батывает сигнал (фиг.2 м), который проходит через элемент ИЛИ 25 и сбрасывает в "0" триггер 14, который запрещает прохождение тактовых импульсов через элемент И 23. 5

Сигнал с выхода схемы 11 сравнения (фиг.2 м) поступает также на выход 38 устройства, сообщая о завершении операции, что позволяет системе снять сигнал пуска (фиг.2 б) . о

Устройство может также выполнять операцию нахождения максимального (минимального) числа в массиве. В этом случае в блок 5 памяти заносится исходный массив, а в регистр 9 длина массива, равная единице. На вход 33 поступает сигнал выполнения операции определения экстремального числа.

При определении максимального числа на вход 30 поступает логическая "1" и по сигналу с входа 31 начальной установки регистр 6 сбрасывается в "0" .

За К тактов, где К вЂ” коэффициент пересчета счетчика 3, в регистр б выбирается наибольшее число. Импульс, формируемый одновибратором 27 по сигналу переноса счетчика 3, поступает через элемент И-ИЛИ 27 (на ЗО третий вход элемента И-ИЛИ 27 поступает логическая "1" по входу 33) на выход 37 синхронизации устройства и на вход прибавления единицы счетчика 1. Содержимое счетчика 1. сравнивается с содержимым регистра

9, и схема 11 сравнения вырабатывает сигнал 38 окончания операции.

Операция определения минимальногo числа выполняется аналогично. При этом на входе 30 — логический "0", и схема 10 сравнения выдает единичный сигнал, если число на выходе блока 5 памяти меньше числа, хранящегося в регистре 6, а в регистре 6 устанавливается максимальное число по сигналу с входа 31 начальной установки, который поступает .на вход регистра через элемент И 19, на второй вход которого поступает логичес- 50 кая "! с элемента НЕ 18.

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

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

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

И, вход задания длины массива устройства подключен к информационному входу второго регистра, выходы которого соединены с вторым входом второй схемы сравнения, выход которой подключен к выходу окончания операции устройства и к второму входу второго элемента ИЛИ, выход которого соединен с входом установки в "0"

7 135

D-триггера, вход синхронизации которого подключен к выходу генератора тактовых импульсов и первому входу четвертого элемента И, второй вход которого соединен с выходом D-триггера, выход четвертого элемента И подключен к входу прибавления единицы первого и третьего счетчиков и к второму входу первого элемента И, третий вход которого соединен с выходом, мультиплексора, управляющие входы которого подключены к информационным выходам третьего счетчика и соединены с информационными входами третьего регистра, выходы которого подключены к входам дешифратора, выходы которого соединены с первыми входами элементов И группы, вторые входы которых объединены и соединены с первым входом элемента И-ИЛИ, входом прибавления единицы четвертого счетчика, входом первого элемента задержки и выходом первого одновибратора, вход которого подключен к выходу переноса третьего счет. чика, выходы элементов И группы сое9288 8 динены с информационными входами четвертого регистра, выходы которого подключены к информационным входам мультиплексора, вход сброса четвертого регистра соединен с выходом первого элемента ИЛИ, второй вход которого соединен с вторым входом элемента И-ИЛИ и выходом второго одновибратора, вход которого соеди10 нен с выходом переноса четвертого счетчика, третий и четвертый входы элемента И-ИЛИ соединены соответственно с группой входов выбора режима устройства, выход элемента

15 И-ИЛИ соединен с выходом синхрони— зации устройства, входом прибавления едийицы второго счетчика и через второй элемент задержки подключен к входу записи первого счетчика, 20 выход первого элемента задержки соединен с вторым входом третьего элемента ИЛИ, выход первого элемента И соединен с входом записи третьего регистра, вход пуска устройства соединен с 33 — входом Э вЂ” триггера.

l259288

Составитель И.Дубинина

Редактор Н.Яцола Техред М.Ходанич

Корректор Т.Колб

Заказ 5124/48 Тираж 671

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

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

Подписное

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