Устройство для сортировки цифровых сигналов Советский патент 1993 года по МПК G06F7/06 

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

Цель изобретения - расширение области применения устройства за счет определения координат сигналов сортируемой последовательности,

На фиг.1 приведена функциональная схема устройства; на фиг.2 - функциональная схема блока синхронизации; на фиг.З, 4 - временная диаграмма работы блока синхронизации в режиме запись ; на фиг.5 - временная диаграмма работы блока синхронизации в режиме сортировка ; на фиг.6 - временная диаграмма работы блока синхронизации в режиме чтение.

Устройство для сортировки цифровых сигналов содержит счетчик 1. блок 2 памяти,

вспомогательный блок 3 памяти, входной блок 4 памяти, счетчик 5 равных чисел, вы- читатель 6, сумматор-вычитатель 7, регистр 8, блок 9 синхронизации, элемент И 10, первый и второй элементы ИЛИ 11, 12, две группы элементов И 13 и 14, три группы элементов ИЛИ 15-17, причем информационные входы устройства соединены с входами вычитаемого вычитателя 6 и информационными входами регистра 8 и входного блока 4 памяти, адресные входы которого соединены с выходами разрядов счетчика 1. входы запуска устройства, записи, сортировки, чтения и логической единицы устройства соединены соответственно с входами с первого по пятый блоков 9 синхронизации, первый вход которого соединен с входом записи-чтения блока 2 памяти, вход записи-чтения вспомогательного блока 3 памяти соединен с вторым выходом блока 9 синхронизации, вход частоты которого соединен с выходом первого элемента ИЛИ 11, выходы вспомогательного блока 3

ел

с

оо

О

ел

Јь

о

памяти соединены с информационными входами счетчика 5 равных чисел, выходы разрядов которого соединены с входами первого элемента ИЛИ 11, выход знакового разряда вычитателя б соединен с первым входом элемента И 10, второй вход которого соединен с третьим выходом блока 9 синхронизации, первый и второй: информационные входы сумматора-вычитателя 7 соединены соответственно с выходами элементов ИЛИ 17 первой группы и выходами разрядов регистра 8, выходы разрядов которого соединены с входами уменьшаемого вычитателя б, выходы сумматора-вычитателя 7 соединены с инфор- мационными выходами устройства, четвертый выход блока 9 синхронизации соединен с суммирующим входом счетчика 1, пятый, шестой и седьмой выходы блока 9 синхронизации соединен соответственно с входами синхронизации, вычитающим и суммирующим входами счетчика 5 равных чисел, третий выход блока 9 синхронизации соединен с входом записи-чтения входного блока 4 памяти, выход запроса числа и пер- вый выход синхронизации блока 9 синхронизации соединены соответственно с выходом запроса числа и первым выходом синхронизации устройства, выходы элементов И 14 первой группы соединены с нервы- ми входами элементов ИЛИ 15 и 16 второй и третьей групп, первый вход синхронизации устройства соединен с первым входом второго элемента ИЛИ 12, второй вход которого соединен с выходом элемента И 10, выход второго элемента ИЛИ 12 соединен с синхронизирующим входом регистра 8, выходы элементов ИЛИ 15 второй группы соединены с адресными входами вспомогательного блока 3 памяти, вход начальной установки устройства соединен с входами начальной установки счетчика 1 и счетчика 5 равных чисел, выходы входного блока 4 памяти соединены с информационными входами элементов И 13 второй группы, вы- ходы которых соединены с первыми входами элементов ИЛИ 17 первой группы, выходы сумматора-вычитателя 7 соединены с информационными входами элементов И 14 первой группы.

В предлагаемое устройство дополнительно введены блок 19 умножения, сумматор 20, третья и четвертая группы элементов И 21 и 22, счетчик 18 адресов вспомогательного блока памяти, причем входы константы устройства соединены с входами первой группы блока 19 умножения, входы второй группы которого соединены с выходами элементов ИЛИ 16 третьей группы, первый и второй входы сумматора 20 соединены соответственно с выходами счетчика 5 равных чисел и блока 19 умножения, выходы сумматора 20 соединены с адресными входами блока 2 памяти, выходы которого соединены с выходами координат устройства, информационные входы элементов И 21 третьей группы соединены с выходами разрядов счетчика 5 равных чисел, а выход - с информационными входами вспомогательного блока 3 памяти, выход переполнения счетчика 5 соединен с входом конца цикла блока 9 синхронизации, выходы элементов ИЛИ 22 четвертой группы соединены с информационными входами блока 2 памяти, выход вспомогательного блока 3 памяти является выходом частоты устройства, информационные входы устройства соединены с информационными входами счетчика 18 адресов вспомогательного блока памяти, вход начальной установки устройства соединен с входами начальной установки блока 9 синхронизации и счетчика 18 адресов вспомогательного блока памяти, выход синхронизации которого является вторым входом синхронизации устройства, выходами конца сортировки и конца чтения устройства являются выходы переполнения соответственно счетчика 1 и счетчика 18 адресов вспомогательного блока памяти, выход переполнения счетчика 1 соединен с первым входом переполнения блока 9 синхронизации, второй вход переполнения которого соединен с выходом переполнения счетчика 18 адресов вспомогательного блока памяти, восьмой выход блока 9 синхронизации соединен с суммирующим входом счетчика 18 адресов вспомогательного блока памяти, информационные выходы которого соединены с вторыми информационными входами элементов ИЛИ 15-17, второй и третьей групп, п выходом конца записи устройства является выход конца записи блока 9 синхронизации, выходы разрядов счетчика 1 соединены с информационными входами элементов И 22 четвертой группы, вход сортировки устройства соединен с управляющими входами элементов И 13, 14, 21, 22 всех групп и управляющим входом сумматора-вычитателя 7, второй выход синхронизации блока 9 синхронизации является вторым выходом синхронизации устройства,

В качестве возможного варианта реализации на фиг.2 приведена функциональная схема блока 9 синхронизации, который содержит генератор 23 тактовых импульсов, первый-третий триггеры 24-26, первый, второй и третий элементы задержки 27,28 и 62, элемент НЕ 29, первый-двадцать пятый элементы И 30-53, 63 и первый-восьмой элементы ИЛИ 54-61, причем первый вход блока 9 синхронизации соединен с первым входом первого элемента ИЛИ 54, выход которого соединен с входом генератора 23 тактовых импульсов, второй вход блока 9 синхронизации соединен с первыми входами первого-шестого элементов И 30-35, выходы которых соединены соответственно с первым входом второго элемента ИЛИ 55, первым входом двадцатого элемента И 49, вторым входом третьего элемента ИЛИ 55, первым входом двадцать второго элемента И 51, первым входом пятого элемента ИЛИ 58 и вторым входом первого элемента ИЛИ 54, третий вход блока 9 синхронизации соединен с первыми входами седьмого- одиннадцатого элементов И 36-40, выходы которых соединены соответственно с первым входом четвертого элемента ИЛИ 57, третьим входом второго элемента ИЛИ 55, вторым входом пятого элемента ИЛИ 58, первым входом третьего элемента ИЛИ 56 и вторым входом шестого элемента ИЛИ 59, четвертый вход блока 9 синхронизации соединен с первыми входами двенадцатого- шестнадцатого элементов И 41-45, выходы которых соединены соответственно с вторым входом четвертого элемента ИЛИ 57, седьмым выходом блока 9 синхронизации, первым входом седьмого элемента ИЛИ 60, первым выходом синхронизации блока 9 синхронизации и четвертым входом первого элемента ИЛИ 54, вход конца цикла блока 9 синхронизации соединен с входом синхронизации первого триггера 24, прямой и инверсный выходы которого, соединены соответственно с вторыми входами четвертого и третьего элементов И 33 и 32, вход частоты блока 9 синхронизации соединен с вторыми входами тринадцатого и пятнадца- того элементов И 42 и 44 и с входом первого элемента задержки 27, выход которого соединен с входом элемента НЕ 29, вход логической единицы блока 9 синхронизации соединен с информационными входами первого-третьего триггеров 24-26, входы сброса которых соединены соответственно с выходом восьмого элемента ИЛИ 61 и входом начальной установки блока 9 синхронизации, выход элемента НЕ 29 соединен с вторыми входами первого, второго, двенадцатого и четырнадцатого элементов И 30, 31,41 и 43, третьи входы которых соединены соответственно с первым, вторым, первым и пятым выходами генератора 23 тактовых импульсов, первый выход генератора 23 тактовых импульсов соединен с вторым входом седьмого элемента И 36, второй выход генератора 23 тактовых импульсов соединен с вторым входом восьмого элемента И

37 и третьим входом пятнадцатого элемента И 44, третий выход генератора 23 тактовых импульсов соединен с вторыми входами пятого и девятого элементов И 34, 38 и третьим входом тринадцатого элемента И 42, четвертый выход генератора 23 тактовых импульсов соединен с третьими входами третьего и четвертого элементов И 32, 33 и вторым входом десятого элемента И 39, пятый выход генератора 23 тактовых импульсов сое- динен с вторыми входами шестого, одиннадцатого и шестнадцатого элементов И 35, 40, 45, вход второго элемента задержки 28 соединен с выходом четвертого элемента И 33, выход первого элемента И 30 соединен с первым входом девятнадцатого элемента И 48 и вторым входом третьего элемента ИЛИ 56, выход которого соединен с первым входом восемнадцатого элемента И 47, выход одиннадцатого элемента И 40 соединен с третьим входом первого элемента ИЛИ 54, выходы второго, четвертого и пятого элементов ИЛИ 55, 57, 58 соединены соответственно с первым входом семнадцатого элемента И 46, пятым выходом блока 9 синхронизации и первым входом двадцать первого элемента И 50, выход которого является седьмым выходом блока 9 синхронизации, вход начальной установки блока 9 синхронизации соединен с входом начальной установки генератора 23 тактовых импульсов и с первым входом восьмого элемента ИЛИ 61, второй вход которого соединен с выходом второго элемента задержки 28. первой и второй входы переполнения блока 9 синхронизации соединены соответственно с входами синхронизации второго и третьего триггеров 25 и 26, инверсные выходы которых соединены соответственно с вторыми входами девятнадцатого, двадцатого и двадцать второго элементов И 48, 49 и 51 и с вторыми входами семнадцатого, восемнадцатого, двадцать первого и двадцать третьего элементов И 46, 47, 50 и 52, выходы семнадцатого-двадцатого элементов И 46-И 49, шестого элемента ИЛИ 59 и двадцать третьего элемента И 52 является соответственно первым, вторым, запроса числа, третьим, четвертым и восьмым выходами блока 9 синхронизации, выход четвертого элемента И 33 соединен с вторым входом седьмого элемента ИЛИ 60, первый вход двадцать третьего элемента И 52 соединен с выходом седьмого элемента ИЛИ 60, прямые выходы второго и третьего триггеров 25 и 26 соединены соответственно с первым и вторым входами двадцать четвертого элемента И 53, выход которого является выходом конца записи блока 9 синхронизации, выход двадцать второго

элемента И 51 соединен с первым входом шестого элемента ИЛИ 59, вход третьего элемента задержки 62 соединен с входом частоты блока 9 синхронизации, первый, второй и третий входы двадцать пятого элемента И 53 соединены соответственно с четвертым входом блока 9 синхронизации, выходом третьего элемента задержки 62 и четвертым выходом генератора 23 тактовых импульсов, выход двадцать пятого элемента И 63 является вторым выходом синхронизации блока 9 синхронизации.

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

Режим записи. До начала режима внешнее устройство подачей сигнала на вход начальной установки устройства обнуляет счетчики 1, 5, 18 и триггеры 24-26, выставляет на информационных входах устройства наибольшее сортируемое число или код (Smax), разрядность которого соответствует разрядности регистра 8 и который содержит 1 во всех разрядах, кроме знакового, и подачей синхросигнала через первый вход синхронизации устройства и элемент ИЛИ 12 на вход синхронизации регистра 8 записывает наибольшее сортируемое число или указанный код Smax в регистр 8. На входах Сортировка, Чтение, первом и втором входах синхронизации устройства внешнее устройство устанавливает нулевые потенциалы, на входе логической единицы устройства - единичный потенциал, а на входах константы устройства - константу К. Значение константы К устанавливается равным числу сортируемых кодов N, т.е. К N. При этом число сортируемых кодов N в устройстве постоянно, счетчик 1 должен считать в диапазоне 0 - (N-1), счетчик 5 - в диапазоне О - N, а адресное пространство блока 4 памяти должно быть в диапазоне 0 - (N-1). На входе режима записи устройства Запись внешнее устройство устанавливает единичный потенциал (фиг.За, 4а), который поступает на второй вход блока 9 синхронизации. Нулевой потенциал с входа сортировки устройства поступает на управляющие входы групп элементов И 14, 21, 22 с помощью группы элементов И 14 блокирует поступление информации с выходов сумматора-вычитателя 7 на адресные входы вспомогательного блока 3 памяти и входы второй группы блока 19 умножения и с помощью групп элементов И 21, 22 образует нулевые коды на информационных входах блоков 2 и 3 памяти.

По входу запуска генератора устройства поступает сигнал запуска (фиг.3,6; 4,6), который поступает на первый вход блока 9 синхронизации и запускает своим задним

фронтом генератор 23 тактовых импульсов. На выходах генератора 23 формируются последовательно не пересекающиеся во времени импульсы ТИ 1 на первом выходе

(фиг,3,а; 4,в). ТИ 2 на втором выходе (фиг.3,г;4,г), ТИЗ на третьем выходе (фиг.З.д; 4,д), ТИ 4 на четвертом выходе (фиг.3,е; 4,е), ТИ 5 на пятом выходе (фиг.З.ж; 4,ж). В такте ТИ 1 срабатывает элемент ИЗО, так как счет0 чик 5 равных чисел обнулен и с выходом элемента ИЛИ 11 на вход частоты блока 9 синхронизации поступает нулевой сигнал (фиг.З.з; 4,з), который, проходя через элемент НЕ 29, инвертируется и открывает эле5 мент И 30. Сигнал с выхода элемента И 30 через элемент И 18 поступает на выход запроса числа блока 9 синхронизации (фиг.Зи, 4и), через элементы ИЛИ 55 и И 46 - на первый (фиг.З.к; 4,к), а через элементы ИЛИ

0 56 и И 47 - на второй (фиг.З.л; 4,л) выходы блока 9. По сигналу с первого выхода блока 9 синхронизации производится запись в блок 2 памяти нулевого кода по адресу А ВхК+ (содержимое счетчика 5 равных чисел)

5 (1), где В (содержимое счетчика 18). Так как счетчики 18 и 5 обнулены, то А 0. По сигналу с второго выхода блока 9 синхронизации производится запись в вспомогательный блок 3 памяти нулевого кода (на выходах

0 группы элементов И 21 нулевой потенциал) по нулевому адресу (счетчик 18 обнулен). Сигнал с выхода запроса числа блока 9 синхронизации поступает на выход запроса числа устройства. По этому сигналу внеш5 нее устройство выставляет на информационных входах устройства сортируемое число (S), с которых оно поступает на входы вычитаемого вычислителя 6 и информационные входы регистра 8 и входного блока 4

0 памяти. С выхода вычитателя 6 на первый вход элемента И 10 поступает положительный потенциал, если сортируемое число, поступающее на входы вычитаемого вычитателя 6, меньше числа, поступившего

5 на входы уменьшаемого вычитателя 6 из регистра 8. В такте ТИ 2 срабатывает элемент И 31, с выхода которого положительный потенциал через элемент И 49 и третий выход блока 9 синхронизации (фиг.Зм, 4м) поступа0 ет на второй вход элемента И 10 и вход записи-чтения входного блока 4 памяти. По этому сигналу происходит запись сортируемого числа, если оно меньше Smax, в регистр 8 и во входной блок 4 памяти по адресу,

5 задаваемому счетчиком 1. В такте ТИ 3 срабатывает элемент И 34. Положительный потенциал с его выхода поступает через элементы ИЛИ 58 и И 50 на седьмой выход блока 9 синхронизации (фиг.Зи, 4и). Сигнал с седьмого выхода блока 9 поступает на

суммирующий вход счетчика 5 равных чисел и увеличивает на единицу содержимое счетчика 5. Информация с выходов разрядов счетчика 5 равных чисел поступает на первые входы сумматора 20, на выходах кото- рого в соответствии с выражением (1) формируется адрес А ячейки блока 2 памяти, и на входы элемента ИЛИ 11. Так как содержимое счетчика 5 отлично от нуля, то на выходе элемента ИЛИ 11 появится еди- ный сигнал. Этот сигнал через вход частоты блока 9 синхронизации поступит на вход элемента задержки 27, длительность задержки которого равна длительности такта генератора 23. В такте ТИ 4 срабатывает элемент И 32, так как триггер 24 находится в нулевом состоянии. Сигнал с выхода элемента И 32 через элементы ИЛИ 55, И 46 и первый выход блока 9 синхронизации поступает на вход записи-чтения блока 2 памя- ти. По этому сигналу обнуляется ячейка блока 2 памяти по адресу, равному А. На выходе элемента задержки 27 появится положительный потенциал, который инвертируется элементом НЕ 29. Инвертированный сигнал поступит на вторые входы элементов И 30, 31 и заблокирует их. В такте ТИ 5 срабатывает элемент И 35 и положительный потенциал с выхода этого элемента поступает через элемент ИЛИ 54 на вход генератора 23 тактовых импульсов. По срезу этого сигнала происходит перезапуск генератора 23, на выходах которого снова формируются тактовые импульсы ТИ 1, ТИ 2, ТИ 3, ТИ 4, ТИ 5. В тактах ТИ 1 и ТИ 2 на выходах блока 9 синхронизации управляющие сигналы отсутствуют. В такте ТИ 3 увеличивается на единицу содержимое счетчика 5 равных чисел и сформируется новый адрес А на адрес- ных входах блока 2 памяти. В такте ТИ 4 по этому адресу запишется нуль в блок 2 памяти, а в такте ТИ 5 снова перезапустится генератор 23. Указанная последовательность операций будет выполняться до тех пор, пока в очередном такте ТИ 3 не произойдет переполнения счетчика 5 равных чисел. При переполнении счетчика 5 на его выходе переполнения появится положительный потенциал, а на информационных - нулевой. Сигнал переполнения с выхода переполнения счетчика 5 через вход конца цикла блока 9 синхронизации (фиг.Зе, 4е) поступает на синхронизирующий вход триггера 24 и переводит триггер 24 в единичное состояние. Сигнал с прямого выхода триггера 24 разблокирует второй вход элемента И 23, а сигнал с его инверсного выхода заблокирует второй вход элемента И 32. С инфор- мационных выходов счетчика 5 равных

чисел нулевой потенциал через элемент ИЛИ 11 и вход частоты блока 9 синхронизации поступит на вход элемента задержки 27.

В такте ТИ 4 сработает элемент И 33, с выхода которого положительный сигнал поступит на вход элемента задержки 28, длительность задержки которого равна длительности такта генератора 23, и на первый вход элемента И 51. Сигнал с выхода элемента И 51 через элемент ИЛИ 59 и четвертый выход блока 9 синхронизации (фиг.Зп, 4п) поступит на суммирующий вход счетчика 1 и увеличит содержимое счетчика 1 на единицу, а через элементы ИЛИ 60, И 52 и восьмой выход блока 9 синхронизации (фиг.Зр, 4р) - на суммирующий вход счетчика 18 и увеличит содержимое счетчика 18 на единицу. С информационных выходов счетчика 1 и 18 поступит новое значение адреса на адресные входы блоков памяти 3 и 4 и на входы второй группы умножителя 19. С выхода элемента задержки 27 нулевой потенциал поступит на вход элемента НЕ 29. С выхода элемента НЕ 29 инвертированный сигнал разблокирует вторые входы элементов И 30 и 31. В такте ТИ 5 перезапускается генератор 23 и сигналом с выхода элемента задержки 28 устанавливается в нулевое состояние триггер 24. В последующих тактах генератора 23 тактовых импульсов работа устройства происходит описанным образом до момента переполнения счетчика 1. При переполнении, например, счетчика 1 на его выходе переполнения появляется сигнал, который поступает через первый вход переполнения блока 9 синхронизации (фиг.З, с) на вход синхронизации триггера 25. Триггер 25 переходит в единичное состояние и нулевым потенциалом своего инверсного выхода (фиг.З,м) блокирует вторые входы элементов И 48, 49, 51. Это приводит в тому, что при дальнейшей работе устройства блок 9 синхронизации не будет выдавать управляющие сигналы на четвертом и третьем выходах и выходе запроса числа, работа блока 9 в этом случае представлена временной диаграммой на фиг.З. Если первым переполняется счетчик 18, то сигнал переполнения поступает через второй вход переполнения блока 9 синхронизации (фиг.4,у) на вход синхронизации триггера 26. Триггер 26 переходит в единичное состояние и нулевым потенциалом (фиг.4,ф) со своего инверсного выхода блокирует вторые входы элементов И 46, 47, 50, 52. Это приводит к тому, что при дальнейшей работе устройства блок 9 синхронизации не будет выдавать управляющие сигналы на первом, втором, седьмом и восьмом выходах. Работа блока 9 в этом случае представлена временной диаграммой на фиг.4. После переполнения обоих счетчиков 1 и 18 на прямых выходах триггеров 25 и 26 установятся положительные потенциалы, которые сформируют с помощью элемента И 53 сигнал конца записи на выходе конца записи блока 9 (фиг.З.х, 4,х) С выхода конца записи блока 9 синхронизации этот сигнал поступает на выход конца записи устройст- ва. По сигналу конца записи внешнее устройство снижает сигнал запись с входа записи устройства. Таким образом, по окончании режима обнуляются ячейки блока 2 памяти и вспомогательного блока 3 памяти, во входной блок 4 памяти записываются сортируемые числа, а в регистр 8 - наименьшее из сортируемых чисел (Smin).

Режим сортировки. До начала режима внешнее устройство подачей сигнала на вход начальной установки устройства обнуляет счетчики 1, 5, 18 и триггеры 24-26. На входах Запись, Чтение, первом и втором входах синхронизации, входе логической единицы устройства внешнее устройство устанавливает нулевые потенциалы, а на входах константы устройства - константу К N. На входе режима сортировки устройства внешнее устройство устанавливает единичный потенциал (фиг.5,а), который по- ступает на третий вход блока 9 синхронизации и на управляющие входы групп элементов И 13, 14, 21, 22 и сумматора-вычи- тателя 7. По этому сигналу группа элементов И 13 разрешает поступление информации с выходов входного блока 4 памяти через группу элементов ИЛИ 17 на первые входы сумматора-вычитателя 7, группа элементов И 14 разрешает поступление информации с выходов сумматора-вычитателя 7 через группу элементов ИЛИ 15 на адресные входы вспомогательного блока 3 памяти и через группу элементов ИЛИ 16 на входы второй группы блока 19 умножения, группы элементов И 21 и И 22 разрешают поступление информации с выходов счетчиков 5 и 1 на информационные входы блоков памяти 3 и 2, а сумматор-вычитатель 7 переключается в режим вычитания. По входу запуска генератора устройства поступает сигнал запуска (фиг.5,б), который поступает на первый вход блока 9 синхронизации и запускает своим задним фронтом генератор 23 тактовых импульсов. На выходах генератора 23 формируются последовательно не пересе- кающиеся во времени импульсы: ТИ 1 на первом выходе (фиг.5,в), ТИ 2 на втором выходе (фиг.5,г), ТИ 3 на третьем выходе (фиг.5,д), ТИ 4 на четвертом выходе (фиг.5,е), ТИ 5 на пятом выходе (фиг.5,ж). В такте ТИ1

срабатывает элемент И 36, с выхода которого положительный потенциал поступает через элемент ИЛИ 57 и пятый выход блока 9 синхронизации (фиг.5,з) на синхронизирующий вход счетчика 5 равных чисел. По этому сигналу в счетчик 5 равных чисел из вспомогательного блока 3 памяти считывается частота сортируемого кода, соответствующего адресу, сформированному на выходе сумматора-вычитателя 7. В такте ТИ 2 срабатывает элемент И 37. Сигнал с выхода этого элемента поступает через элементы ИЛИ 55, И 46 и первый выход блока 9 синхронизации (фиг.5,и) на вход записи-чтения блока 2 памяти, По этому сигналу происходит запись координаты сортируемого числа, поступающей с выходов разряда счетчика 1, в ячейку блока 2 памяти с адресом, поступающим с выхода сумматора 20 и равным А в соответствии с (1), где В .S-Smin. В такте ТИ 3 срабатывает элемент И 38. Сигнал с выхода этого элемента поступает через элементы ИЛИ 58, И 50 и седьмой выход блока 9 (фиг.5к) на суммирующий вход счетчика 5 равных чисел и увеличивает содержимое счетчика 5 на единицу. В такте ТИ 4 срабатывает элемент И 39. Сигнал с выхода этого элемента поступает через элементы ИЛИ 56, И 47 и второй выход блока 9 синхронизации (фиг.5,л) на вход записи-чтения вспомогательного блока 3 памяти. По этому сигналу производится запись частоты, поступающей с информационных выходов счетчика 5. в ячейку вспомогательного блока 3 памяти с адресом, вырабатываемым сумматором-вычитателем 7. В такте ТИ 5 срабатывает элемент И 40. Сигнал с выхода элемента И 40 поступает через элемент ИЛИ 59 и четвертый выход блока 9 (фиг.5,м) на суммирующий вход счетчика 1, а также через элемент ИЛИ 54 на вход генератора 23. Этот сигнал увеличивает на единицу содержимое счетчика 1 и своим срезом перезапускает генератор 23. В последующих тактах ТИ 1-ТИ 5 работа устройства происходит вышеописанным образом до момента переполнения счетчика 1. При переполнении счетчика 1 на его выходе переполнения появляется сигнал, который поступает на выход конца сортировки устройства (фиг.5,н). Внешнее устройство снимает сигнал сортировка с выхода сортировки устройства. Таким образом, по окончании режима в блоке 2 памяти будут записаны координаты отсортированных числе по адресам, определяемым выражением (1), а во вспомогательном блоке 3 памяти - частоты отсортированных чисел.

Режим чтения. До начала режима внешнее устройство подачей сигнала на вход на

единицы устройства внешнее устройство устанавливает нулевые потенциалы, а на выходах константы устройства - константу К N. На входе режима чтения устройства внешнее устройство устанавливает единиц- ный потенциал (фиг.б.а), который поступает на четвертый вход блока 9 синхронизации. Нулевой потенциал с входа сортировки устройства поступает на управляющие входы групп элементов И 13,14,21,22. Этот сигнал с помощью группы элементов И 13 блокирует поступление информации с выходов входного блока 4 памяти на первые входы группы элементов ИЛИ 17, с помощью группы элементов И 14 блокирует поступление информации с выходов сумматора-вычита- теля 7 на первые входы групп элементов ИЛИ 15, 16 и устанавливает сумматор-вычи- татель 7 в режим сложения.

По входу запуска генератора устройства поступает сигнал запуска (фиг.6,6), который поступает на первый вход блока 9 синхронизации и запускает своим задним фронтом генератор 23. На выходах генератора формируются импульсы ТИ 1-ТИ 5 (фиг.б,в-6,ж). В такте ТИ 1 срабатывает элемент И 41, так как на входе частоты блока 9 нулевой сигнал (счетчик 5 обнулен). Сигнал с выхода элемента И 41 через элемент ИЛИ 57 и пятый выход блока 5 синхронизации (фиг.б.з) поступает на вход синхронизации счетчика 5 равных чисел. По этому сигналу происходит запись в счетчик 5 частоты из ячейки вспомогательного блока 3 памяти, адрес которой определяется содержимым счетчика 18. При этом возможны два варианта: в счетчик 5 записывается код частоты, отличный от нуля, или нулевой. В первом случае с выхода элемента ИЛИ 11 на вход элемента задержки 27 поступает положительный по- тенциал (фиг.6,и), который этим элементом задерживается до конца такта ТИ 1, а в такте ТИ 2, пройдя через элемент НЕ 29, закрывает второй вход элемента И 41. Положительный потенциал с выхода элемента ИЛИ 11 поступает также через элемент задержки 62, задержка которого составляет два такта генератора 23 тактовых импульсов, а такте ТИ 3 - на второй вход элемента И 63. В такте ТИ 2 при положительном потенциале с вы- хода элемента ИЛ И 11 срабатывает элемент И 44. С выхода этого элемента через первый выход синхронизации (фиг.6,к) блока 9 синхронизации на первый выход синхронизации устройства поступает сигнал синхронизации. По сигналу синхронизации внешнее устройство читает с выхода сумма- тора-вычитателя 7 код отсортированного числа, с выхода частоты - частоту этого кода. В такте ТИ 3 при положительном потенциале с выхода элемента ИЛИ 11 срабатывает элемент И 42. С выхода этого элемента через седьмой выход блока 9 синхронизации (фиг.6, л) на вычитающий вход счетчика 5 поступает сигнал, по которому содержимое счетчика 5 уменьшается на единицу. В такте ТИ 4 срабатывает элемент И 63. С выхода этого элемента через второй выход синхронизации блока 9 синхронизации (фиг.6,м) на второй выход синхронизации устройства поступает сигнал синхронизации. По сигналу синхронизации внешнее устройство читает с выхода координат устройства координату отсортированного кода. В такте ТИ 5, если содержимое счетчика 5 отлично от нуля, срабатывает только элемент И 45, так как сигнал частоты, проходящий через элемент НЕ 29, устанавливает на втором входе элемента И 43 нулевой потенциал. Сигнал с выхода элемента И 45 перезапускает генератор 23. В следующем такте ТИ 1 на всех выходах блока 9 управляющие сигналы нулевые, так как ненулевой сигнал частоты блокирует по второму входу элемент И 41. В такте ТИ 2 внешнее устройство читает код отсортированного числа и его частоту. В такте ТИ 3 уменьшается содержимое счетчика 5, в такте ТИ 4 внеш нее устройство читает координату отсортированного числа, а в такте ТИ 5 перезапускается генератор 23. Устройство работает таким образом, пока содержимое счетчика 5 отлично от нуля. Если в одном из тактов ТИ 3 счетчик 5 обнуляется, то с выхода элемента ИЛИ 11 снимается сигнал частоты (фиг.6,и). Тогда в последующем такте ТИ 4 срабатывает элемент И 63, а в такте ТИ 5 срабатывают элементы И 43 и И 45. С выхода элемента И 63 поступает сигнал синхронизации, а с выхода элемента И 43 через элементы ИЛИ 60, И 52 и восьмой выход блока 9 синхронизации (фиг.б.н) на суммирующий вход счетчика 18 поступает положительный потенциал, и содержимое счетчика 18 увеличивается на единицу. С информационных выходов счетчика 18 на адресные входы блоков памяти 2 и 3 поступит новый адрес. Сигналом с выхода элемента И 45 перезапускается генератор 23. Если в последующем такте ТИ 1 код частоты, читаемый из очередной ячейки блока 3 памяти, отличен от нуля, то работа устройства происходит выше описанным образом. Во втором случае, когда код частоты, записываемый в счетчик 5, равен нулю, в тактах ТИ 2, ТИ 3 и ТИ 4 не срабатывают элементы И 42, И 44 и И 63 и на всех выходах блока 9 синхронизации устанавливаются нулевые потенциалы. В такте ТИ 5 срабатывают элементы И 43 и И 45, и поэтому происходит увеличение на единицу содержимого

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

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

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

В дополнении к вышеописанному на фиг,7 приведен пример схемы блока 23 (фиг.2), где:

23.1-23.6, 23-9 - триггеры;

23.7 - схема выделения целых импульсов;

23.8, 23.11 -элементы задержки;

23.10 - генератор импульсов;

23.12 - вход начальной установки;

23.13 - вход запуска;

А, В. С, Д, Е - выходы.

Перед началом работы в блоке 23 все Д-триггеры устанавливаются в исходные состояния сигналом по входу 23.12. При этом триггер 23.1 устанавливается в 1, а все остальные- в О. С приходом сигнала запуска на вход 23.13 триггер 23.9 устанавливается в 1. Открывается схема 23.7 и импульсы генератора 23.10 поступают на синхронизирующие выходы триггеров 23.1- 23.6. При этом 1 с выхода триггера 1 последовательно передвигаются по триггерам 23.2-23.6, формируя на выходах А, В, С, Д, Е пять управляющих сигналов. По заднему фронту сигнала Е триггер 23.9 устанавливается в О, закрывая схему 23.7, а 1 записывается в триггер 23.1. Таким образом, после выдачи пяти управляющих сигналов блок 23 принимает исходное состояние и находится в ждущем режиме.

Элемент задержки 23.8 обеспечивает запирание схемы 23.7 после переключения Д-триггеров 23.1-23.6. Элемент задержки 23.11 служит для смещения пятого управля- ющего сигнала в случае, когда он используется для повторного запуска генератора 23. Схема 23.7 обеспечивает прохождение на синхронизирующие входы Д-триггеров 23,1-23.6 только целых импульсов генерато- ра 23.10 и тем самым исключает вероятность срыва переключения.

На фиг.8 в качестве примера представлена схема выделения целых импульсов:

23.7.1-23.7.4 - элементы 2И-НЕ; 23.7.5 - информационный вход;

23.7.6 - управляющий вход;

23.7.7 - выход.

На вход 23.7.5 поступают импульсы с генератора импульсов. Когда на вход 23.7.6

приходит сигнал разрешения, то начиная с первого целого импульса, частота с входа 23.7.5 проходит на выход 23.7.7.

Преимуществом предлагаемого устройства является возможность определения координат сигналов сортируемой последовательности. Знание координат сигналов сортируемой последовательности позволяет связать такие характеристики сигналов сортируемой последовательности, какамплитуда и частота, с их положением в исходной последовательности. Это расширяет область применения предлагаемого устройства. Так, в устройствах для анализа статических данных это дает возможность

оперативного определения условных распределений вероятностей. Применение предлагаемого устройства в устройствах для разпознавания образов, сжатия информации и анализа изображений позволяет в

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

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

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

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

0 третья и четвертая группа элементов И, счетчик адресов вспомогательного блока памяти, причем входы константы устройства соединены с входами первой группы блока умножения, входы второй группы

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

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

0 входами блока памяти, выход вспомогательного блока памяти является выходом частоты устройства, информационные входы устройства соединены с информационными входами счетчика адресов вспомогательно5 го блока памяти, вход начальной установки устройства - с входами начальной установки блока синхронизации и счетчика адресов вспомогательного блока памяти, вход синхронизации которого является вторым

0 входом синхронизации устройства, выходами конца сортировки и конца чтения устройства являются выходы переполнения соответственно счетчика и счетчика адресов вспомогательного блока памяти, выход пе5 реполнения счетчика соединен с первым входом переполнения блока синхронизации, второй вход переполнения которого соединен с выходом переполнения счетчика адресов вспомогательного блока памяти,

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

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

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

В/, записи 5С9

Вх. записка гене ратЪра БС9

1-й Выл. ГТИ 23

2-й8ых.ГТИ23

3-йбЫХ.ГТИ23

4-Ц 8ЫХ. ГТИ23

5-Ц8ЫХ.ГТИ23

Вх.частоты БС9 Зых. запроса числа вс9

1-й 8ых. БС9

2-йЖых БСЗ

3-йбых.ВС9

7-йдЫХ.БС9 Входконца циклабСЗ

4-и Вых. 5СЭ

8-цВых.БС9

1-й дх.пеоелял„ нения $С9 Инзерсныа 8ых . ,rnpus.2S

2-й Зх.леоелолненияБСЗИнвдоснь/а Вых n mo us. 26 Вых.нонцалу- nucuSCd

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

Фиг.З