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

(57) Изобрети вычислит Т.В щяЬ СУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ А ВТОРСИОМУ СВИДЕТЕЛЬСТВ(71) Львовский орднический институткомсомола(56) Авторское свидетельство СССРФ 911509, кл. С 06 Р 7/04, 1980.Авторское свидетельство СССРР 771665, кл. С 06 Р 7/04, 1978,ение относится к обласельной техники и предназ начено для использования в специализированных вычислительных устройствах при обработке одномерных массивов данных. Цель изобретениярасширение функциональных возможнос-,тей за счет операции медианной фильтрации одномерных массивов. Указаннаяцель достигается введением в устройство счетчиков, блока памяти,регистров, схемы сравнения, дешифратора, мультиплексора, В-триггера,элементов задержки, элементов НЕ,элементов И, ИЛИ, ИЛИ-НЕ, одновибраторов, группы элементов И. Устройство позволяет наряду с операциейопределения максимального (минимального) числа выполнять операцию медианной фильтрации. 2 ил.9288 125 5 О 5 20 25 30 35 45 50 5 Изобретение относится к вычислительной технике и предназначено дляиспользования в специализированныхвычислительных устройствах при обработке одномерных массивов данных,Цель изобретения - расширениеФункциональных возможностей за счетоперации медианной Фильтрации одномерных массивов,На фиг.1 представлена функциональная схема устройства; на Фиг.2временная диаграмма работы устройства.Устройство содержит второй счетчик 1, первый счетчик 2, третий ичетвертый счетчики 3 и 4, блок 5памяти, первый регистр 6, третийрегистр 7, четвертый регистр 8,второй регистр 9, первая и втораясхемы 10 и 11 сравнения, дешифратор12, мультиплексор 13, Р-триггер 14,генератор 15 тактовых импульсов,второй и первый элементы 16 и 7задержки, элемент НЕ 18, третий,второй и первый элементы И 19, 20и 21, группу элементов И 22, четвертый элемент И 23, элементы ИЛИ 24-26,элемент И-ИЛИ 27, одновибраторы 28и 29, вход 30 выбора режима устройства, вход 31 начальной установкиустройства, группа входов 32 и 33выбора режима устройства, вход 34пуска устройства, вход 35 заданиядлины массива устройства, информационный выход 36 устройства, выход37 синхронизации устройства и выход38 окончания операции устройства. гМедианная Фильтрация осуществляется посредством движения некоторой апертуры вдоль дискретизированной последовательности и замены значения элемента в середине апертуры медианой исходных значений отсчетов внутри апертуры. Медианой является средний .член ряда, получающегося при упорядочении по убыванию исходных значений внутри апертуры. В исходном состоянии в блоке 5 памяти записана исходная последовательность, причем в начале и конце. массива прописаны минимальные зна чения (нулевые), количество которыхК равно , где К в , длина апертуры, нечетко число, Это необходимо для снижения краевых эффектов. 1Рассмотрим пример медианной фильтрации последовательности: 1, 5, 3, 2, 7, 10, 1. Пусть длина апертуры равна 3, Тогда массив чисел, записанный в блоке 5, имеет вид: О, 1, 5, 3, 2, 7, 1 О, 1, О.Упорядочение подмассива, длина которого равна длине апертуры, выполняется методом выбора наибольших значений в каждом цикле с блокировкой их в следующих циклах. В первом цикле среди первых трех чисел определяется максимальное (5), Его мы должны не учитывать во втором цикле. Во втором цикле определяем наибольшее число (1), Количество циклов, необходимых для нахождения медианы,К+1равно в в . В нашем случае при К=З23+- 2. Таким образом число (1) 2 является медианой в окрестности первого элемента массива.Сдвигаем апертуру на один элемент и определяем медиану среди чисел: 1, 5, 3, Медиана будет равна 3. После выполнения семи этапов поиска медианы находим отфильтрованную последовательность: 1, 3, 3, 3, 7, 7, 1Устройство работает следующим образом.На вход 30 выбора режима и на вход 32 поступает уровень логической "1". Единичный уровень по входу 30 поступает на управляющий вход схемы 10 сравнения и устанавливает ее вследующее состояние: на выходе будет единичный сигнал, если число на первой группе входов (выходы блока 5 40, памяти) больше числа на второй группе входов (выходы регистра б),По сигналу 31 начальной установки (фиг.2 а) сбрасываются в "0" счетчики 1-4, в регистр 9 по входам 34 и 35 заносится длина обрабатываемого массива. Кроме того, сигнал с входа 31 проходит через элементы ИЛИ 24 и сбрасывает в "0" регистр 8 (признаков) и через элемент ИЛИ 25 сбра,сывает триггер 14 (пуска), а также проходит через элемент И 20, на второй вход которого поступает разрешение по входу 30 устройства, и через элемент ИЛИ 26 сбрасывает в "0" регистр 6,По входу 34 поступает сигнал "Пуск" (фиг.2 б) на Р-вход триггера 14 и по переднему фронту импульса с(фиг.2 в), который поступает навход синхронизации триггера, триггер устанавливается в единичноесостояние (фиг,2 г) и разрешает прохождение тактовых импульсов черезэлемент И 23 (фиг. 2 д).Если число, считанное иэ блока5 памяти, больше числа, хранящегосяв регистре 6,.то с выхода схемысравнения единичный сигнал разрешения разрешает прохождение тактовогоимпульса через элемент И 21 фиг.2 е)на вход записи регистра 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. За К тактов в регистр6 выбирается наибольшее число в подмассиве из К чисел, а в регистр 7заносится его адрес.На выходе переноса счетчика 3формируется импульс переноса (фиг. 2 ж),который поступает на вход одновибратора 28. Последний формирует короткий импульс (фиг,2 з), который поступает на первые входы группы элементов И, 22 и через элемент 17 задержкии элемент ИЛИ 26 сбрасывает регистр 556, Элемент 17 задержки задерживаетимпульс сброса регистра 6 на время,необходимое для считывания медианы из регистра 6. Адрес наибольшего числа, хранящийся в регистре 7, дешифруется с помощью дешифратора 12, выходы которого соединены с вторыми входами элементов И 22. Импульс с одновибратора проходит через соответствующий наибольшему числу элемент И 22, на второй вход которого поступает разрешение с дешифратора 12 и устанавливает в единицу соответствующий разряд регистра 8. Это необходимо для блокировки в следующем цикле наибольшего числа. В следующемцикле в регистр 6 выбирается второе по величине число в подмассиве из Кчисел и записывается вторая единицав соответствующий разряд регистра 8.Сигнал с одновибратора 28 поступаетна вход прибавления единицы счетчика4. Счетчик 4 является счетчиком сК+1пересчетом -2, где К - апертура,К+1а --- номер элемента посередине2К+1апертуры т.е. медиана. За --2циклов в регистр 6 будет выбрано значение первой медианы. На выходе счетчика 4 появляется сигнал переноса (фиг.2 и), по которому одновибратор 29 формирует короткий импульс (фиг.2 к), который проходит через элемент ИЛИ 24 и сбрасывает в "0" регистр 8, а также проходит через элемент И-ИЛИ 27, на второй вход которого подается разрешение по входу 32 на выход 37 синхронизации устройства, сообщая, что на информационных выходах устройства находится значение медианы, и поступает на вход прибавления единицы счетчика 1 (начального адреса) и на вход элемента 16 задержки. По сигналу с выхода элемента задержки (фиг.2 л) увеличенное на единицу значение начально- го адреса переписывается в счетчик 2 (текущего адреса), Таким образом, обеспечивается сдвиг апертуры.Еще заК+1циклов определяется2К+1 вторая медиана и т.д. За и циклов, где и - длина обрабатываемого массива, определяются и медиан. В последнем цикле содержимое счетчика 1 начального адреса становится ,равным содержимому регистра 9 длины массива и схема 11 сравнения выра 1259288батывает сигнал (фиг,2 м), которыйпроходит через элемент ИЛИ 25 исбрасывает в "0" триггер 14, которыйзапрещает прохождение тактовых импульсов через элемент И 23. 5Сигнал с выхода схемы 11 сравнения (фиг.2 м) поступает также навыход 38 устройства, сообщая о завершении операции, что позволяет системе снять сигнал пуска (фиг.2 б) .10Устройство может также выполнятьоперацию нахождения максимального(минимального) числа в массиве. Вэтом случае в блок 5 памяти заносится исходный массив, а в регистр 9 - 5длина массива, равная единице. Навход 33 поступает сигнал выполненияоперации определения экстремальногочисла.При определении максимального 0числа на вход 30 поступает логическая "1" и по сигналу с входа 31начальной установки регистр б сбрасывается в 0.За К тактов, где К - коэффициент 25пересчета счетчика 3, в регистр бвыбирается наибольшее число, Импульс,формируемый одновибратором 27 посигналу переноса счетчика 3, поступает через элемент И-ИЛИ 27 (на 30третий вход элемента И-ИЛИ 27 поступает логическая "1" по входу 33)на выход 37 синхронизации устройства и на вход прибавления единицысчетчика 1. Содержимое счетчика 1.сравнивается с содержимым регисгра9, и схема 11 сравнения вырабатываетсигнал 38 окончания операции,Операция определения минимальногочисла выполняется аналогично. При 40этом на входе 30 - логический "0",и схема 10 сравнения выдает единичный сигнал, если число на выходеблока 5 памяти меньше числа, хранящегося в регистре 6, а в регистре 6устанавливается максимальное числопо сигналу с входа 31 начальной установки, который поступает,на входрегистра через элемент И 19, на второй вход которого поступает логическая "1" с элемента НЕ 18.формула изобретенияУстройство для анализа случайных 55чисел, содержащее первый регистр,первый счетчик, генератор тактовыхимпульсов, первый элемент И, первую схему сравнения, причем первая группа входов первой схемы сравнения соединена с информационными входами первого регистра, выходы которого подключены к второй группе входов первой схемы сравнения и являются информационными выходами устройства, вход разрешения сравнения первой схемы сравнения соединен с входом выбора режима устройства, выход первой схемы сравнения подключен к первому входу первого элемента И, выход которого соединен с входом записи первого регистра, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет операции медианной фильтрации одномерных массивов, в него введены счетчики, блок памяти, регистры, вторая схема сравнения, дешифратор, мультиплексор, Р-триггер, элементы задержки, элемент НЕ, элементы И, группу элементов И, элементы ИЛИ, элемент И-ИЛИ, одновибраторы, причем первая группа входов первой схемы сравнения соединена с информационными выходами блока памяти, адресные входы которого соединены с выходами первого счетчика, входы параллельной записи которого соединены с первыми входами второй схемы сравнения и выходами второго счетчика, входы сброса первого, второго, третьего и четвертого счетчиков объединены и соединены с входом записи второго регистра, первыми входами первого и второго элементов ИЛИ, первыми входами второго и третьего элементов И и ВхОдОм начальной устаноВки устройства, вход выбора режима устройства подключен к второму входу второго элемента И и входу элемента НЕ, выход которого соединен с вторым входом третьего элемента И, выход кото-. рого подключен к входу установки первого регистра, Вход сброса которого соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с выходом второго элемента И, вход задания длины массива устройства подключен к информационномувходу второго регистра, выходы которого соединены с вторым входом второй схемы сравнения, выход которой подключен к выходу окончания операции устройства и к второму входу второго элемента ИЛИ, выход которого соединен с входом установки в "О"7 125 В-триггера, вход синхронизации которого подключен к выходу генератора тактовых импульсов и первому входу четвертого элемента И, второй вход которого соединен с выходом 0-триггера, выход четвертого элемента И подключен к входу прибавления единицы первого и третьего счетчиков и к второму входу первого элемента И, третий вход которого соединен с выходом, мультиплексора, управляющие входы которого подключены к информационным выходам третьего счетчика и соединены с информационными входами третьего регистра, выходы которого подключены к входам дешифратора, выходы которого соединены с первыми входами элементов И группы, вторые входы которых объединены и соединены с первым входом элемента И-ИЛИ, входом прибавления единицы четвертого счетчика, входом первого элемента задержки и выходом первого одновибратора, вход которого подключен к выходу переноса третьего счет,чика,. выходы элементов И группы сое 9288 8динены с информационными входамичетвертого регистра, выходы которогоподключены к информационным входаммультиплексора, вход сброса четвертого регистра соединен с выходомпервого элемента ИЛИ, второй входкоторого соединен с вторым входомэлемента И-ИЛИ и выходом второгоодновибратора, вход которого соеди О нен с выходом переноса четвертогосчетчика, третий и четвертый входыэлемента И-ИЛИ соединены соответственно с группой входов выбора режима устройства, выход элемента 15 И-ИЛИ соединен с выходом синхронизации устройства, входом прибавленияедийицы второго счетчика и черезвторой элемент задержки подключенк входу записи первого счетчика, 20 выход первого элемента задержки соединен с вторым входом третьего элемента ИЛИ, выход первого элемента Исоединен с входом записи третьегорегистра, вход пуска устройства 25 соединен с 2 - входом Э - триггера,1259288 бининаич , Корректор Т,Кол оставитель И, ехред М.Хода едакт цол Зака Подписн митета СССР открыт роизводствен играическое предприя 124/48 Тираж 671 НИИПИ Государственног по делам изобретений 13035, Москва, Ж,ская наб., д. 4 Ужгород, ул. Проектна