Устройство для вычисления порядковых статистик последовательности двоичных чисел

(594 С 06 Р 7 02 ПИСАНИЕ ИЗОБРЕТЕНИ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ ъ(56) Авторское свидетельство СССР1096638 кл.С 06 Р 7/02, 1983.Авторское свидетельство СССР1239708 кл.С 06 Г 7/02, 1984, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПО-, РЯДКОВЫХ СТАТИСТИК ПОСЛЕДОВАТЕЛЬНОСТИ ДВОИЧНЫХ ЧИСЕЛ(57)Изобретение относится к области вычислительной техники и технической кибернетики и может быть использовано в системах цифровой обработки сиг налов, например для ранговой фильтрации сигналов, Цель изобретения -расширение области применения устройства за счет устранения неоднозначности при вычислении равных порядковых статистик входной последовательности чисел. Устройство.содержат блок из и сдвиговых регистров,и элементов И, где и - количествочисел заданной последовательности,и - входовый элемент ИЛИ, и элементов ИСКЛЮЧА 10 ЩЕЕ ИЛИ, и триггеровпервой группы, блок приоритета, итриггеров второй группы, сдвиговыйрегистр, шифратор, регистр номерапорядковой статистики и блок синхронизации, Порядковые статистики последовательно вычисляются путемопределения максимума в каждом циклеработы устройства и исключения егопри анализе чисел в следующем цикле,общее количество которых равно и.Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в устройствах цифровой обработки сигналов, 5Цель изобретения - расширение области применения устройства за счет устранения неоднозначности при вычислении равных порядковых статистик входной последовательности чисел,На фиг, изображена структурнаясхема предлагаемого устройства; нафиг. 2 - структурная схема блокаприоритета.Устройство содержит блок из п сдвиговых регистров 1, и элементов И 2, и-входовый .элемент ИЛИ 3, п элементов ИСКЛ 1 ОЧАОЩЕЕ ИЛИ 4, и .триггеров 5 первой группы, блок 6 приоритета, и триггеров 7 второй группы, сдвиговый регистр 8, шифратор 9, регистр 10 кода номера порядковой статистики, блок 11 синхроцизации, состоящий из генератора 12 тактовых импульсов и счетчика 13, информационный .вход 14 и вход 15 записи устройства.Блок приоритета содержит и элементов И 16, (и) элементов НЕ 7, и входов 18, управляющий вход 19 и п выходов 20.Устройство работает следующим образом.3511 еред началом вычислений выполняется установка в единичное состояние триггеров первой и второй группы. При поступлении импульса записи на вход 15 устройства в блок 1 с информационного входа 14 устройства записываются коды входной последовательности чисел. Блок 1 состоит изп кольцевых сдвиговых регистров, работающих параллельно. Входы управления сдвигом всех кольцевых сдвиговых регистров соединены с входом управления сдвигом блока 1, а выходы первых (старших) разрядов сдвиговых регистров являются соответствующими выходами блока,В данном устройстве все порядковые статистики последовательностии двоичных чисел вычисляются поочередно, начиная с первой, т.е. с максимального числа заданной последовательности чисел, и кончая и-ой порядковой статистикой, т.е. минимумом этой последовательности, Каждая порядковая статистика вычисляет-ся за время одного цикла работы устройства, причем каждый цикл состоитиз ш тактов работы устройства, гдеш - количество разрядов двоичныхчисел из входной последовательности.В 1-м цикле работы устройства вычисляется ш-разрядный код 1-й порядковой статистики, например код медианного значения последовательности вычисляется в цикле с номером(и + 1) /2. где и - нечетное.Значения всех и порядковых статистик вычисляются поразрядно, начиная со старшего разряда, следующим образом,1В первом цикле работы устройствапри поступлении 3-го тактового импульса с первого выхода блока 11,который является выходом генератора12 тактовых импульсов, на вход управления сдвигом блокапроисходитсчитывание 1-х разрядов всех и чиселпоследовательности и затем сдвигкодов в кольцевых сдвиговых регистрах на. один разряд в сторону старшего разряда, С выходов блока 1сигналы, соответствующие 1-м разрядам чисел, поступают ца первый вход соответствующих элементов И 2, С помощью и элементов И 2, п-входового элемента ИЛИ 3, п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4 и п триггеров 5 первой группы поразрядно (начиная со старшего разряда) вычисляется максимумпоследовательности чисел, коды которых поступают ца первые входы элементов И 2. В первом цикле работы устройства на выход и-входового элемента ИЛИ 3 поразрядно поступает код максимума входной последовательности чисел т.е. первая порядковая статистика, таким образом, что в 1-м такте цикла определяется 1-й разряд порядковой статистики. После ш тактов работы в сдвиговом регистре 8 записывается код максимума входной последовательности, который поразрядно поступает на вход его первого разряда с выхода элемента ИЛИ 3. Триггеры 5 первой группы устанавливаются в нулевое состояние за исключением триггера, номер которого является номером максимума входной последовательности, т,е, этот триггер остается в едицичцом состоянии, После окончания первого цикла работы на втором выходе блока 11, т,е, 1290295на выходе счетчика 13 появляется управляющий импульс. Частота импуль-, сов на выходе счетчика 13 в т раз меньше частоты генератора 12 тактовых импульсов. Импульс с второго 5 выхода блока 11 поступает на управляющий вход блока 6. В предлагаемом устройстве блок 6 выполняет следующую функцию. При определении максимума последовательности чисел может 10 оказаться, что в этой последовательности имеется несколько равных максимальных чисел. Следовательно, в этом случае в единичном состоянии будет несколько триггеров 5, которые соот ветствуют этим максимальным числам, и не будет однозначности при определении индекса максимального числа, т.е. в общем случае индекса вычисляемой порядковой статистики. Блок 6 20 за счет использования и элементов И 16 и п) элементов НЕ 17 позволяет однозначно определить номер вычисляемой порядковой статистики путем селекции первого из триггеров 5, находящихся в единичном состоянии. При поступлении импульса на вход 19 блока 6 на одном из и его выходов 20 появляется импульс, ко 30 торый устанавливает соответствующий триггер 7 в нулевое состояние, а состояния остальных триггеров 7 остаются без изменения. Число входной последовательности чисел, которое было определено в первом цикле работы как максимум, во втором цикле исключено из анализа при определении второй порядковой статистики. Таким образом, во втором цикле работы уст 40 ройства определяемый максимум последовательности кодов чисел на выходе элементов И 2 будет второй порядковой статистикой входной последовательности чисел. Выходные сигна- лы блока 6 также поступают на входы45 шифратора 9, который преобразовывает входной код "1 из и" в позиционный двоичный, имеющий 1= 11 оя п 1 разрядов (где знакобозначает округление до ближайшего целого, не меньшего данного числа).После окончания каждого цикла работы устройства управляющий импульс на втором выходе блока 11 устанавливает все и триггеров 5 первойгруппы в единичное состояние, которое является исходным при определении максимума последовательности в следующем цикле работы. Также при поступлении управляющего импульса на вход управления записью регистра 10 происходит запись номера порядковой статистики в регистр 1 О, Таким образом, после окончания 1-го цикла работы устройства в ш разрядном сдвигоном регистре 8 будет записан код -й порядковой статистики входной последовательности чисел, а в регистре 10 - код индекса д-й порядковой статистики. После и циклов работы будут последовательно вычислены все порядковые статистики.Формула изобретенияУстройство для вычисления порядковых статистик последовательности двоичных чисел, содержащее блок из и сдвиговых регистров, и элементов И, где п - число анализируемых чисел, п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, и триггеров первой группы, элемент ИЛИ, регистр кода номера порядковой статистики, регистр и блок синхронизации, причем выходы старших разрядов сдвиговых регистров блока соединены с первыми входами соответствующих элементов И, выходы которых соединены с первыми входами соответствующих элементов ИСКЛ 10 ЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль соответствующих триггеров первои группы, выходы которых подключены к вторым входам соответствующих элементов И, входы установки в единицу триггеров. первой группы объединены, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ объединены, выход элемента ИЛИ подключен к входу регистра, о т -л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет устранения неоднозначности при вычислении равных порядковых статистик, регистр выполнен сдвиговым и в устройство введены блок приоритета, шифратор, и триггеров второй группы, выходы которых соединены с третьими входами соответствующих элементов И, выходы которых дополнительно подключены к входам элемента ИЛИ, выход которого соединен с вторыми входами элементов ИСКЛЮЧА 10 ЩЕЕ ИЛИ, выходы триггеров соединены с информационными входами блока приоритета, управляющий вход которого соединен с входами установки в5 12единицу триггеров первой группы,синхровходом регистра кода номерапорядковой статистики и выходомконца цикла блока синхронизации,тактовый выход которого подключен квходам управления .сдвигом сдвиговыхрегистров, выходы блока приоритетасоединены с входами установки в нольсоответствующих триггеров второйгруппы и входами шифратора, выходыкоторых подключены к информационнымвходам регистра кода номера порядко 90295вой статистики, выходы которогоявляются выходами кода номера порядковой статистики устройства, выходсдвигового регистра является выходомкода числа, входы установки в единицу триггеров второй группы соединены с входом начальной установкиустройства, информационные входы ивход записи устройства являются ф соответственно информационными входами н входами управления записьюсдвиговых регистров блока.1290295 Е.Ивановйник оставитель ехред Л.О дакто рректор М.Демчи аказ 7902/46 одписно ета СССР ткрытииаб., д. 4 оизводственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4 ВНИИПИ Госу по делам 3035, Москва, Тираж 67 3рственного коизобретений и