Устройство сортировки чисел Советский патент 1988 года по МПК G06F7/06 

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

Целью изобретения является повышение быстродействия,

На фиг. 1 изображено устройство сортировки чисел, на фиг. 2 - блок управления.

Устройство (фиг. 1) содержит т- разрядные кольцевые регистры 1 сдвига, элементы И 2, элементы ИЛИ 3, элементы 2И-ИЛИ 4, триггеры 5-7, управляющий элемент И-ИЛИ 8, блок 9. управления, вход 10 запуска, выхода 11-17 блока управления, адресный выход 18, выход 19 отсортированного числа, информационные входы.

Блок управления содержит двойной триггер 20, генератор 21 импульсов, счетчик 22, дешифратор 23, элементы И 24 и 25, элемент НЕ 26, э лемент И 27, элемент НЕ 28.

В кольцевые регистры 1,-1п каждого модуля устройства массив сортируемых чисел записьшается любым известным способом. По сигналу, поступающему на вход 10 блока 9 управления с помощью синхроимпульсов сГ, и t поступакяцих из генератора. 21 импульсоб, двойной триггер 20, триггеры 5-7 всех модулей устанавливаются в состояние 1, этими же сигналами управления и синхроимпульсами счетчик 22 устанавливается в состояние О, После этого установившееся состояние 1 двойного триггера 20 с помсяцью очередной серии синхроимпульсов о, и 2 устанавливает счетчик 23 в состояние 000...01 (младшие разряды справа). Это же единичное состояние триггера 20 разрешает прохождение синхроимпульсов &, и Г через элемент И 24 на кольцевые регистры каждого модуля. С помощью этих синхроимпульсов начинает сдвигаться на один двоичный разряд информация в кольцевых регистрах Ij-l. Допустим, что в старшем разряде одного из кольцевых регистров 1,- 1 равна 1, тогда на выходе управляющего элемента И-ИЛИ 8 сигнал будет равен единич ному состоянию, т.е. состоянию, разрешающему прохождение сигналов через схемы И элементов 2И-ИЛИ 4. Другими словами, нулевое состояние, например, . в старшем разряде кольцевого регистра 1 одного из модулей поступает через первый вход элемента

2И-ИЛИ 4 на его выход. С приходом синхроимпульса , с выхода 16 блока 9 управления поступает сигнал, который устанавливает триггер 5 в состояние О. Второй синхроимпульс

0 Tj, поступающий с выхода 17 блока управления, устанавливает триггер 7 в состояние О. Состояние старшего разряда всех кольцевых регистров пе- реписьшается в самый младший их раз5 ряд. На место старшего разряда поступает значение цифры разряда с весом на единицу меньше. Аналогично выход старшего разряда всех кольцевых регистров 1,-lf, в случае единичного

0 состояния на выходе управляющего

элемента И-ИЛИ действует на соответствующие триггеры 5 и 7.

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

цифры кольцевых регистров 1|-1, рассматриваемого разряда равны нулю, вс элементы И-ИЛИ, одним из входов ко- торых являются инверсные выходы коль0 цевых регистров -In, закрыты, и сброс триггеров 5 и 7 устройства в состояние О с приходом синхроимпульсов , и Га не осуществляется. В этом случае инфоруяция в кольцевых

- регистрах сдвинется на один разряд. Сброс триггеров 5 и 7 в состояние О свидетельствует о том, что число (содержимое данного кольцевого регистра) является медьаим пи

О величине, чем числа (других кольце- вых регистров 1 других модулей), соответствующие триггеры 5 и 7 которых находятся в состоянии 1. Управляющий элемент И-ШШ 8 исключает

5 их операции сортировки с помощью сиг нала, поступающего из прямого выхода данного триггера 7. Нулевое состояние этого выхода блокирует.информацию, поступающую из кольцевого ред гистра 1; на соо-йветствующий вход управляющего элемента И-ИЛИ 8. Эта блокировка действув.т в течение очередных сдвигов в кольцевых регистрах Ij-ln до окончания полного цикла сдвига, кото1 1й - измеряется количеством сдвигов, равных т, где m - разрядность чисел. В течение тп-го сдвига, а именно на этапе действия синхроимпульса С помощью сигнала.

5

поступающего с блока 9 управления с выхода 15, i-й триггер 6 сбрасывает- мя в состояние О, если соответствующий триггер 5 в это время находится в состоянии О, С наступлением состояния счетчика 22 блока 9 управления, равного числу т, подача синхроимпульсов с выходов 16 и 17 на входы кольцевых регистров прекращается. Это осуществляется подачей запрещающего сигнала из дешифратора 23 на элемент И 28. В это же время (состояние счетчика 23, равное числу т) происходит перезапись состояния i-ro триггера 6 в триггер 5. Прямые выходы триггеров 7 являются адресными выходами 18 устройств, с них считывается адрес наибольшего числа из чисел, сортируе№1Х в тече- i ние предьщущих m сдвигов. Само же это число считьюается в течение этих m сдвигов поразрядно на выход 19.

После m сдвигов в течение действия очередной посьшки пары синхроимпульсов t, и t j состояния триггеров 5 и 7 приобретают состояние триггера 6 предлагаемого устройства, i-e . триггеры 5 и 7 каждого модуля будут в состоянии О, если в соответствующем i-M кольцевом регистре 1 находится число, ранее отсортированное в ранг больших чисел. Состояние О прямого выхода триггера 7 иск- лючает из дальнейшей сортировки соответствующий кольцевой регистр 1 с помощью управляющего элемента И- ИЖ 8.

Состояние 1 триггеров 5 и 7 говорит о том, что содержимое соответствующего . регистра, исключенное в течение предьщущ ей сортировки (т сдвигой), теперь участвует в copf тировке. Процедура очередного этапа сортировки соответствует ранее описанной процедуре, т.е. в течение очередных сдвигов на выход 19 устройства последовательно поступает разряд за разрядом следующее по величине число из сортируемого массива, а по окончании т-го сдвига на выход 18 поступает этого числа.

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

1. Устройство сортировки чисел, содержащее п т-разрядных кольцевых регистров сдвига, где п - чис-

0

5

0

5

ло сортируемых чисел, информационные входы которых являются информационными входами устройства, управляющий элемент И-ИЛИ, п элементов 2И-ИЛИ два элемента И, элемент ИЛИ, блок управления, причем прямой выход старшего разряда i-ro m-разрядного кольцевого регистра сдвига (i 1, ..., п) соединен с управляющим входом i-ro элемента И управляющего элемен-п та И-ИЛИ, отличающееся тем, что, с целью повьштения быстродействия, в устройство введены три группы триггеров п-2 элементов И, п-1 элементов ИЛИ, причем инверсный выход старшего разряда i-ro m-разрядного .кольцевого регистра сдвига соединен с первым входом первого элемента И i-ro элемента 2И-Ш1И, выход которого соединен с входом установки в О i-ro триггера первой групйы, прямой выход которого подключен к входу установки в О i-ro триггера второй группы и входу установки в единичное состояние i-ro триггера третьей группы, прямой выход которого является 1-м адресным выходом устройства и соединен с информациой- ным входом i-ro элеьйнта И управляю щего элемента И-ИЛИ, выход которого , является выходом отсортированного числа устройства и соединен с вторьш входом второго элемента И i-ro эле- 5 мента 2И-Ш1И, вход запуска устройства подключен к первым входам всех элементов ИЛИ, входам установки в единичное cocJгoяниe всех триггеров второй группы и входу запуска блока управления, первый и второй выходы которого подключены к входам управления сдвигом всех т-разрядных регистров сдвига, а третий выход соединен с первыми входами всех элементов И, всех вторых элементов И, всех элементов 2И-ИЛИ, выход i-ro элемен та И подключен к второму входу i-ro элемента ИЛИ, выход которого соединен с входом установки в единичное , состояние i-ro триггера первой группы, инверсш.1й выход которого подключен к входу установки в О i-ro триггера третьей группы, прямой и инверсный выходы i-ro триггера второй группы соединены с вторыми входами соответственно i-ro элемента И и второго элемента И i-ro элемента 2И-Ш1И, четвертый, пятый и шестой выходы блока управления соединены с синхро

0

0

5

0

5

входами триггеров соответственно первой, второй и третьей групп.

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

413846

элементов И, выходы которых являются соответственно четвертым и пятым выходами блока управления, а выход g второго элемента И через первый элемент НЕ - с шестым выходом блока управления, вход запуска блока управления подключен к входу установки в О счетчика и ииформационному входу 10 двойного триггера, выход которого соединен с управляющим входом счетчика и первым входом третьего элемента И, второй выход которого соединен с первым выходом генератЬра 15 импульсов, а выход является первым выходом блока управления и через .второй элемент НЕ соединен с вторым выходом блока управления.

У/

Изобретение относится к вычислительной технике и может быть использовано для построения устройств сорiO тировки и упорядочивания чисел. Цельн изобретения является повьшение быстродействия. Устройство содержит т- разрядные кольцевые регистры сдвига 1, элементы И 2, элементы ИЛИ 3, эле- ;менты 2И-ИЛИ 4, триггеры 5, 6, 7, управляющий элемент И-ИЛИ 8, блок управления 9. Устройство выполняет анализ разрядов сортируеьвлх чисел, начиная со старших разрядов, выбор . максимального из них, затем исключения максимального числа из последовательности чисел, выбор максимального числа из оставшихся чисел и т.д. до упорядочивания всей последовательности чисел. 1 з.п. ф-лы, 2 ип. (Л 00 00