Устройство для анализа случайных чисел Советский патент 1986 года по МПК G06F17/18 

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

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

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

Устройство содержит второй счетчик , первый счетчик 2, третий и четвертый счетчики 3 и 4, блок 5 памяти, первый регистр 6, третий регистр 7, четвертый регистр В, второй регистр 9, первая и вторая схемы 10 и 11 сравнения, дешифратор 12, мультиплексор 13, В триггер 14, генератор 15 тактовых импульсов, второй и первый элементы 16 и 17 задержки, элемент НЕ 18, третий, второй и первый элементы И 19, 20 и 21, группу элементов И 22, четвер тьй элемент И 23, элементы ИЛИ 24-26 элемент И-ИЛИ 27, одновибраторы 28 и 29, вход 30 выбора режима устройства, вход 31 начальной установки устройства, группа входов 32 и 33 выбора режима устройства, вход 34 пуска устройства, вход 35 задания длины массива устройства, информационный выход 36 устройства, выход

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

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

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

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

К-1 равно г-, где К - длина апертуры,

нечетно число. Это необходимо для снижения краевых эффектов.

Рассмотрим пример медианной фильт- рации последовательности: 1, 5, 3,

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

3,2, 7, 10, 1, 0.

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

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

К+ 1 равно В нашем случае при ,

--- 2. Таким образом число (1)

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

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

и определяем медиану среди чисел:

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

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

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

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

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

По сигналу 31 начальной установки (фиг.2 а) сбрасываются в О счетчики 1-4, в регистр 9 по входам 34 и 35 заносится длина обрабатываемого массива. Кроме того, сигнал с входа 31 проходит через элементы ИЛИ 24 и сбрасывает в О регистр 8 (признаков) и через элемент ИЛИ 25 сбра- «сывает триггер 14 (пуска) , а. также проходит через элемент И 20, на второй вход которого поступает разрешение по входу 30 устройства, и через элемент ИЛИ 26 сбрасьшает в О регистр 6.

По входу 34 поступает сигнал Пуск (фиг.2 б) на D-БХОД триггера 4 и по переднему фронту импульса с

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

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

5памяти, больше числа, хранящегося

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

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

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

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

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

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

1(+1 пересчетом где К - апертура,

К+1 а -т- - номер элемента посередине

апертуры, т.е. медиана.

За ii За 2

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

V, I

Еще за --- циклов определяется

К+1 вторая медиана и т.д. За п --циклов, где п - длина обрабатываемого массива, определяются п медиан. В последнем цикле содержимое счетчика I начального адреса становится (равным содержимому регистра 9 длины массива и схема П сравнения вьфа5

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

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

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

При определении максимального micjia на вход 30 поступает логическая 1 и по сигналу с входа 31 начальной установки регистр б сбра- сьшается в О.

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

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

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

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

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

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

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

7

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

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

Л 35

Йд./

а 6 6 г

д

е ж

3 и н

/1 ff

Составитель И.Дубинина Редактор Н.Яцола Техред М.Ходанич

Заказ 5124/48 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР , по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

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