Устройство для сортировки цифровых сигналов

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (51)5 G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4837685/24 (22) 11.06.90 (46) 30.03.93. Бюл. ¹ 12 (71) Московский институт электромеханики и автоматики (72) B.À,ËàòûøåB, В.Э.Петров (56) 1. Авторское свидетельство СССР

¹ 1196849, кл. G 06 F 7/06, 1984.

2, Авторское свидетельство СССР № 1144103, кл. G 06 F 7/06, 1983.

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

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

Устройство для сортировки цифровых сигналов содержит счетчик 1, блок 2 памяти,, 5U„„1805464 А1 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЦИФРОВЫХ СИГНАЛОВ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения— расширение области применения за счет определения координат сортируемой последовательностии. Устройство содержит счетчик, блок памяти, вспомогательный блок памяти, входной блок памяти, регистр, блок синхронизации, элемент И, блок умножения, сумматор, счетчик адресов вспомогательного блока памяти, генератор тактовых импульсов, триггеры. 6 ил, вспомогательный блок 3 памяти, входной блок 4 памяти, счетчик 5 равных чисел, вычитатель 6, сумматор-вычитатель 7, регистр

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

ИЛИ 11, выходы вспомогательного блока 3

1805464 ветственно с выходами счетчика 5 равных сел и блока 19 умножения, выходы суммара 20 соединены с адресными входами ока 2 памяти, выходы которого соединены выходами координат устройства, инфорционные входы элементов И 21 третьей уппы соединены с выходами разрядов етчика 5 равных чисел, а выход — с инфорционными входами вспомогательного ока 3 памяти, выход переполнения счетка 5 соединен с входом конца цикла бло9 синхронизации, выходы элементов

И 22 четвертой группы соединены с инрмационными входами блока 2 памяти, ход вспомогательного блока 3 памяти ляется выходом частоты устройства, инрмационные входы устройства соединес информационными входами счетчика адресов вспомогательного блока памяти, од начальной установки устройства соенен с входами начальной установки бло9 синхронизации и счетчика 18 адресов помогательного блока памяти, выход нхронизации которого является вторым одом синхронизации устройства, выхоми конца сортировки и конца чтения усойства являются выходы переполнения ответственно счетчика 1 и счетчика 18 ресов вспомогательного блока памяти, ход переполнения счетчика 1 соединен с рвым входом переполнения блока 9 синхнизации, второй вход переполнения котого соединен с выходом переполнения етчика 18 адресов вспомогательного блопамяти, восьмой выход блока 9 синхрониции соединен с суммирующим входом етчика 18 адресов вспомогательного лака памяти, информационные выходы торого соединены с вторыми информацинными входами элементов ИЛИ 15 — 17, орой и третьей групп, и выходом конца аписи устройства является выход конца аписи блока 9 синхронизации, выходы разядов счетчика 1 соединены с информацинными входами элементов И 22 четвертой руппы, вход сортировки устройства соедиен с управляющими входами элементов И

3, 14, 21, 22 всех групп и управляющим ходом сумматора-вычитателя 7, второй

ыход синхронизации блока 9 синхронизаии является вторым выходом синхрониации устройства, В качестве возможного варианта реалиации на фиг.2 приведена функциональная хема блока 9 синхронизации, который соержит генератор 23 тактовых импульсов, ервый-третий триггеры 24-26, первый, втоой и третий элементы задержки 27, 28 и 62, лемент НЕ 29, первый-двадцать пятый элеенты И 30 — 53, 63 и первый-восьмой элепамяти соединены с информационными от входами счетчика 5 равных чисел, выходы чи разрядов которого соединены с входами то первого элемента ИЛИ 11, выход знакового бл разряда вычитателя 6 соединен с первым 5 с входом элемента И 10, второй вход которого ма соединен с третьим выходом блока 9 синх- гр ронизации, первый и второй, информацион- сч н ые входы сумматора-вычитателя 7 ма соединены соответственно с выходами 10 бл элементов ИЛИ 17 первой группы и выхо- чи дами разрядов регистра 8, выходы разря- ка дов которого соединены с входами ИЛ уменьшаемого вычитателя 6, выходы сум- фо матора-вычитателя 7 соединены с инфор- "5 вы ма цион ными выходами устройства, яв четвертый выход блока 9 синхронизации со- фо единен с суммирующим входом счетчика 1, ны пятый, шестой и седьмой выходы блока 9 18 синхронизации соединен соответственно с 20 вх входами синхронизации, вычитающим и ди суммирующим входами счетчика 5 равных ка чисел, третий выход блока 9 синхронизации вс соединен с входом записи-чтения входного си блока 4 памяти, выход запроса числа и пер- 5 вх

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

- 30 ми входами элементов ИЛИ 15 и 16 второй пе и третьей групп, первый вход синхрониза- ро ции устройства соединен с первым входом ро второго элемента ИЛИ 12, второй вход кото- сч рого соединен с выходом элемента И 10, 35 ка выход второго элемента ИЛИ 12 соединен за с синхронизирующим входом регистра 8, сч выходы элементов ИЛИ 15 второй группы б соединены с адресными входами вспомога- ко тельного блока 3 памяти, вход начальной 40 о установки устройства соединен с входами вт начальной установки счетчика 1 и счетчика з

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

- 45 ходы которых соединены с первыми входа- г ми элементов ИЛИ 17 первой группы, н выходы сумматора-вычитателя 7 соединены 1 с информационными входами элементов И в

14 первой группы.

В предлагаемое устройство дополни- ц тельно введены блок 19 умножения, сумма- з тор 20, третья и четвертая группы элементов

И 21 и 22, счетчик 18 адресов вспомогатель- з ного блока памяти, причем входы константы с

55 устройства соединен ы с входами первой д группы блока 19 умножения, входы второй и группы которого соединены с выходами эле- р ментов ИЛИ 16 третьей группы, первый и э второй входы сумматора 20 соединены со- м

1805464 менты ИЛИ 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 синхронизации, выход двадцать второго

1805464

25

40

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

И 63 является вторым выходом синхронизации блока 9 синхронизации, Устройство работает следующим образом.

Режим записи. До начала режима внеш- 15 нее устройство подачей сигнала на вход начальной установки устройства обнуляет счетчики 1, 5, 18 и триггеры 24 — 26, выставляет на информационных входах устройства наибольшее сортируемое число или код (S ax), разрядность которого соответствует разрядности регистра 8 и который содержит

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

12 на вход синхронизации регистра 8 записывает наибольшее сортируемое число или указанный код Smax в регистр 8. На входах

"Сортировка", "Чтение", первом и втором входах синхронизации устройства внешнее устройство устанавливает нулевые потенциалы, на входе логической единицы устройства — единичный потенциал, а на входах константы устройства — константу К. Значение константы К устанавливается равным 35 числу сортируемых кодов N, т,е. К = N, При этом число сортируемых кодов N в устройстве постоянно, счетчик 1 должен считать в диапазоне 0 - (К-1), счетчик 5 — в диапазоне

0 — N, а адресное пространство блока 4 памяти должно быть в диапазоне 0 - (N-1), На входе режима записи устройства "3aпись" внешнее устройство устанавливает единичный потенциал (фиг,3a, 4а), который поступает на второй вход блока 9 синхронизации. Нулевой потенциал с входа сортировки устройства поступает на управляющие входы групп элементов И 14, 21, 22 с помощью группы элементов И 14 блокирует поступление информации с выходов сумматора-вычитателя 7 на адресные входы вспомогательного блока 3 памяти и входы второй группы блока 19 умножения и с помощью групп элементов И 21, 22 образует нулевые коды на информационных вхо- 5 дах блоков 2 и 3 памяти.

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

На выходах генератора 23 формируются последовательно не пересекающиеся во времени импульсы ТИ 1 на первом выходе (фиг,Ç,а; 4,в), ТИ 2 на втором выходе (фиг,Ç,г;4,г), ТИ 3 на третьем выходе (фиг.Ç,д;

4,д), ТИ 4 на четвертом выходе (фиг,З,е; 4,е), ТИ 5 на пятом выходе (фиг.З,ж; 4,ж). В такте

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

56 и И 47 — на второй (фиг.З,л; 4,л) выходы блока 9. По сигналу с первого выхода блока

9 синхронизации производится запись в блок 2 памяти нулевого кода по адресу А =

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

Сигнал с выхода запроса числа блока 9 синхронизации поступает на выход запроса числа устройства. По этому сигналу внешнее устройство выставляет на информационных входах устройства сортируемое число (S), с которых оно поступает на входы вычитаемого вычислителя 6 и информационные входы регистра 8 и входного блока 4 памяти, С выхода вычитателя 6 на первый вход элемента И 10 поступает положительный потенциал, если сортируемое число, поступающее на входы вычитаемого вычитателя 6, меньше числа, поступившего на входы уменьшаемого вычитателя 6 из регистра 8. B такте ТИ 2 срабатывает элемент

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

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

1805464

10 суммирующий вход счетчика 5 равных чисел и увеличивает на единицу содержимое счетчика 5. Информация с выходов разрядов счетчика 5 равных чисел поступает на первые входы сумматора 20, на выходах кото- 5 рого в соответствии с выражением (1) формируется адрес А ячейки блока 2 памяти, и на входы элемента ИЛИ 11. Так как содержимое счетчика 5 отлично от нуля, то на выходе элемента ИЛИ 11 появится единый сигнал. Этот сигнал через вход частоты блока 9 синхронизации поступит на вход элемента задержки 27, длительность задержки которого равна длительности такта генератора 23. В такте ТИ 4 срабатывает элемент И 32, так как триггер 24 находится в нулевом состоянии, Сигнал с выхода элемента И 32 через элементы ИЛИ 55, И 46 и первый выход блока 9 синхронизации поступает на вход записи-чтения блока 2 памяти. Ro этому сигналу обнуляется ячейка блока 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 равных

55 чисел нулевой потенциал через элемент

ИЛИ 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 синхронизации (фиг.3, с) на вход синхронизации триггера 25. Триггер 25 переходит в единичное состояние и нулевым потенциалом своего инверсного выхода (фиг.З,м) блокирует вторые входы элементов И 48, 49, 51.

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

18, то сигнал переполнения поступает через второй вход переполнения блока 9 синхронизации (фиг.4,у) на вход синхронизации триггера 26. Триггер 26 переходит в единичное состояние и нулевым потенциалом (фиг,4,ф) со своего инверсного выхода блокирует вторые входы элементов И 46, 47, 50, 52. Это приводит к тому. что при дальнейшей работе устройства блок 9 синхронизации не будет выдавать управляющие сигналы на первом, втором. седьмом и вось1805464

12 мом выходах. Работа блока 9 в этом случае срабатывает элемент И 36, с выхода которопредставлена временной диаграммой на го положительный потенциал поступает чефиг.4. После переполнения обоих счетчиков рез элемент ИЛИ 57 и пятый выход блока 9

1 и 18 на прямых выходах триггеров 25 и 26 синхронизации (фиг.5,з) на синхронизируюустановятся положительные потенциалы, 5 щий вход счетчика 5 равных чисел, По этому которые сформируют с помощью элемента сигналу в счетчик 5 равных чисел из вспомоИ 53 сигнал конца записи на выходе конца гательного блока 3 памяти считывается часзаписи блока 9 (фиг,З,х, 4,х) С выхода конца тота сортируемого кода, соответствующего записи блока 9 синхронизации этот сигнал адресу, сформированному на выходе суммапоступает на выход конца записи устройст- 10 тора-вычитателя 7. В такте ТИ 2 срабатывает ва. По сигналу конца записи внешнее уст- элементИ37. Сигналсвыходаэтогоэлеменройство снижает сигнал "запись" с входа та поступает через элементы ИЛИ 55, И 46 записи устройства. Таким образом, по окон- и первый выход блока 9 синхронизации чании режима обнуляются ячейки блока 2 (фиг,5,и) на вход записи-чтения блока 2 папамяти и вспомогательного блока 3 памяти, 15 мяти, По этому сигналу происходит запись во входной блок 4 памяти записываются координаты сортируемого числа, поступаюсортируемые числа, а в регистр 8 — наимень- щей с выходов разряда счетчика 1, в ячейку шее из сортируемых чисел (Smln). блока 2 памяти с адресом, поступающим с

Режим сортировки. До начала режима выхода сумматора 20 и равным А в соответвнешнее устройство подачей сигнала на 20 ствии с (1), где В =,S-Smin. В такте ТИ 3 вход начальной установки устройства обну- срабатывает элемент И 38. Сигнал с выхода ляет счетчики 1, 5, 18 и триггеры 24 — 26. На этого элемента поступает через элементы входах "Запись", "Чтение", первом и втором ИЛИ 58, И 50 и седьмой выход блока 9 входах синхронизации, входе "логической" (фиг.5к) на суммирующий вход счетчика 5 единицы устройства внешнее устройство 25 равных чисел и увеличивает содержимое устанавливает нулевые потенциалы, а на счетчика 5 на единицу. B такте ТИ 4 срабавходах константы устройства — константу тывает элемент И 39, Сигнал с выхода этого

К = N. На входе режима сортировки устрой- элемента поступает через элементы ИЛИ ства внешнее устройство устанавливает 56, И 47 и второй выход блока 9 синхрониединичный потенциал (фиг.5,а), который по- 30 зации (фиг.5,л) на вход записи-чтения вспоступаетнатретий вход блока 9синхрониза- могательного блока 3 памяти, По этому ции и на управляющие входы групп сигналу производится запись частоты, поэлементов И 13, 14, 21, 22 и сумматора-вычи- ступающей с информационных выходов тателя 7, По этому сигналу группа элементов счетчика 5. в ячейку вспомогательного блоИ 13 разрешает поступление информации с 35 ка 3 памяти с адресом, вырабатываемым выходов входного блока 4 памяти через сумматором-вычитателем 7. В такте ТИ 5 группу элементов ИЛИ 17 на первые входы срабатывает элемент И 40. Сигнал с выхода сумматора-вычитателя 7, группа элементов элемента И 40 поступает через элемент

И 14 разрешает поступление информации с ИЛИ 59 и четвертый выход блока 9 (фиг,5,м) выходов сумматора-вычитателя 7 через 40 на суммирующий вход счетчика 1, а также группу элементов ИЛИ 15 на адресные вхо- через элемент ИЛИ 54 на вход генератора ды вспомогательного блока 3 памяти и через 23. Этот сигнал увеличивает на единицу согруппу элементов ИЛИ 16 на входы второй держимое счетчика 1 и своим срезом перегруппы блока 19 умножения, группы эле- запускает генератор 23. B последующих ментов И 21 и И 22 разрешают поступление 45 тактах ТИ 1 — ТИ 5 работа устройства происинформации с выходов счетчиков 5 и 1 на ходит вышеописанным образом до момента информационные входы блоков памяти 3 и переполнения счетчика 1. При переполне2, асумматор-вычитатель7 переключается в нии счетчика 1 на его выходе переполнережим вычитания. По входу запуска генера- ния появляется сигнал, который поступает на тора устройства поступает сигнал запуска 50 выход конца сортировки устройства (фиг.5,б), который поступает на первый (фиг.5,н). Внешнее устройство снимает вход блока 9 синхронизации и запускает сигнал "сортировка" с выхода сортировки своим задним фронтом генератор 23 так- устройства. Таким образом, по окончании товых импульсов, На выходах генератора 23 режима в блоке 2 памяти будут записаны формируются последовательно не пересе- 55 координаты отсортированных числе по кающиеся во времени импульсы: ТИ 1 на адресам, определяемым выражением(1),а первом выходе (фиг,5,в), ТИ 2 на втором во вспомогательном блоке 3 памяти — частовыходе (фиг.5,г), ТИ 3 на третьем выходе ты отсортированных чисел. (фиг.5,д), ТИ 4 на четвертом выходе (фиг.5,е), Режим чтения. До начала режима внешТИ 5 на пятом выходе (фиг.5.ж), В такте ТИ1 нее устройство подачей сигнала на вход на

1805464

14 единицы устройства внешнее устройство устанавливает нулевые потенциалы, а на выходах константы устройства — константу

К = N. На входе режима чтения устройства внешнее устройство устанавливает единич- 5 ный потенциал (фиг.6,а), который поступает на четвертый вход блока 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 синхронизации (фиг.6,з) поступает на вход синхронизации счетчика

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

18. При этом возможны два варианта; в счетчик 5 записывается код частоты, отличный от нуля, или нулевой. В первом случае с выхода элемента ИЛИ 11 на вход элемента задержки 27 поступает положительный потенциал (фиг.6,и), который этим элементом задерживается до конца такта ТИ 1, а в такте

ТИ 2, пройдя через элемент НЕ 29, закрывает второй вход элемента И 41. Положительный потенциал с выхода элемента ИЛИ 11 поступает также через элемент задержки

62, задержка которого составляет два такта генератора 23 тактовых импульсов, а такте

ТИ 3 — на второй вход элемента И 63. В такте

ТИ 2 при положительном потенциале с выхода элемента ИЛИ 11 срабатывает элемент

И 44, С выхода этого элемента через первый выход синхронизации (фиг.б,к) блока 9 синхронизации на первый выход синхронизации устройства поступает сигнал синхронизации. По сигналу синхронизации внешнее устройство читает с выхода сумматора-вычитателя 7 код отсортированного числа, с выхода частоты — частоту этого кода.

В такте ТИ 3 при положительном потенциа10

55 ле с выхода элемента ИЛИ 11 срабатывает элемент И 42, С выхода этого элемента через седьмой выход блока 9 синхронизации (фиг,б, л) на вычитающий вход счетчика 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 снимается сигнал частоты (фиг,б,и), Тогда в последующем такте ТИ 4 срабатывает элемент И 63, а в такте ТИ 5 срабатывают элементы И 43 и И 45. С выхода элемента И 63 поступает сигнал синхронизации, а с выхода элемента И 43 через элементы ИЛИ 60, И

52 и восьмой выход блока 9 синхронизации (фиг,6,н) на суммирующий вход счетчика 18 поступает положительный потенциал, и содержимое счетчика 18 увеличивается на единицу. С информационных выходов счетчика 18 на адресные входы блоков памяти 2 и 3 поступит новый адрес. Сигналом с выхода элемента И 45 перезапускается генератор 23. Если в последующем такте ТИ 1 код частоты, читаемый из очередной ячейки блока 3 памяти, отличен от нуля, то работа устройства происходит выше описанным образом. Во втором случае. когда код частоты, записываемый в счетчик 5, равен нулю, в тактах ТИ 2, ТИ 3 и ТИ 4 не срабатывают элементы И 42, И 44 и И 63 и на всех выходах блока 9 синхронизации устанавливаются нулевые потенциалы, В такте ТИ 5 срабатывают элементы И 43 и И 45, и поэтому происходит увеличение на единицу содержимого

1805464

16 счетчика 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", а все остальные — в "0". С приходом сигнала запуска на вход 23.13 триггер 23.9 устанавливается в "1", Открывается схема 23.7 и импульсы генератора 23,10 поступают на синхронизирующие выходы триггеров 23.1—

23.6. При этом "1" с выхода триггера 1 последовательно передвигаются по триггерам

23,2 — 23.6, формируя на выходах А, В, С, Д, Е пять управляющих сигналов, По заднему фронту сигнала Е триггер 23,9 устанавли5

55 вается в "0", закрывая схему 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.

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

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

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

18

1805464

20

30

40

50

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

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

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

И четвертой группы, вход сортировки уст20

1805464 ройства соединен с управляющими входами элементов И всех групп и управляющим входом сумматора-вычитателя, второй аЬренюьпьмнью»

Конец

Риг.1

Запись

57 чиМа

Начальная усн анаен

1ЬИх н ьацил

27 29

/&иец

Уаслеп а галуела

Синхронм

Занудах еехерипта 54

Перепою нЕниЕ

Льмч

7Гхм ю

doe+i саввы

Маем

3ollllCV

3олуск с»

apwopaf йагiреюг ьальес ч

omeeuo

Льь

C4llOIQ.

24

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

47

4В Zanppc

1805464

1805464

1805464

Фиг, Ю

Составитель В. Латышев

Техред М.Моргентал Корректор И. Шулла

Редактор

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина. 101

Заказ 943 Тираж Подписное

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

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