Устройство для сортировки чисел

Устройство для сортировки чисел

Иллюстрации

Показать все

Реферат

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

Известны следующие устройства: устройство для сортировки чисел - авторское свидетельство СССР №1649533, кл. G 06 F 7/08, 1989, авторское свидетельство СССР №1659998, кл. G 06 F 7/08, 1988.

Прототипом выбрано устройство - авторское свидетельство СССР №1606973, кл. G 06 F 7/08, 1988. Недостатком прототипа является то, что он использует метод линейной организации массива сортируемых чисел, не позволяющий выполнять полную попарную сортировку чисел.

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

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

Схема устройства изображена на чертеже.

Устройство содержит n блоков 1 анализа, каждый из которых включает два элемента И 3, И 8, элемент ИЛИ 6, схему сравнения 7 пары чисел, регистр 2 и две группы элементов И 4, И 5.

Кроме того, устройство содержит триггер 9 коммутации и элемент 10 задержки, элемент ИЛИ-НЕ 11, первый 12 и второй 13 элементы И, генератор 14 импульсов, триггер 15 управления, информационные выходы 16 устройства, выход 17 готовности (ГОТОВ) устройства и вход 18 запуска устройства (ПУСК).

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

Исходное состояние устройства характеризуется тем, что триггеры 9 и 15 установлены в нулевое состояние (цепи установки в "0" аналогичны прототипу).

В соответствующих регистрах 2 блоков анализа 1 размещается массив исходных чисел. Работа устройства начинается по сигналу ПУСК, поступающему по входу 18. Этим сигналом в единичное состояние устанавливается триггер 15. Единичным сигналом с единичного выхода триггера 15 открывается элемент И 12, чем обеспечивается подача импульсов с выхода генератора 14 на элементы схемы устройства.

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

Если в паре сравниваемых чисел большее из них оказалось в левом блоке 1 анализа, то оно передается в правый блок 1 анализа, а число из этого блока переписывается в регистр левого блока 1 анализа. Таким образом, производится обмен числами между регистрами в каждой паре чисел. В противном случае, числа остаются на исходных позициях в паре. По окончании первого этапа цикла триггер 9 устанавливается в единичное состояние, задавая второй этап цикла полного попарного сравнения. При этом сравниваются одновременно пары чисел четных и нечетных блоков анализа с аналогичным выполнением обменов, причем содержимое регистра 2 для n-го (четного) блока 1 анализа сравнивается с содержимым регистра 2 первого (нечетного) блока анализа.

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

Рассмотрим работу устройства при n=4, а в регистрах 2 задан массив чисел: A₁=10, A₂=8, А₃=4, А₄=5.

На входы схемы 7 сравнения блока 1₁ анализа подаются числа A₁ и А₂, на входы схемы 7 блока 1₂ анализа - числа А₂ и А₃, на входы схемы 7 блока 1₃ анализа - числа А₃ и А₄, на входы схемы 7 блока 1₄ анализа - числа A₁ и А₄. При этом на выходах "больше" схем сравнения блоков 1₁ - 1₄ анализа формируется позиционный код сравнения 1101 соответственно, так как A₁>А₂, А₂>А₃, А₃<А₄, A₁>А₄. Нулевое состояние триггера 9 определяет позиционный код коммутации 1010. Элементы И 8 всех блоков анализа выполняют побитовую обработку позиционного кода сравнения со значением 1101, поступающего на вторые входы элементов И 8, с позиционным кодом коммутации со значением 1010, поступающего на первые входы элементов И 8. Таким образом, в блоке 1₁ открыт элемент И 8, единичным сигналом с выхода которого через элементы ИЛИ 6 открыты элементы И 3 в блоках 1₁ и 1₂. Позиционный код сравнения 1101, поступающий на входы элемента ИЛИ-НЕ 11, определяет нулевой сигнал на его выходе. Этим нулевым сигналом закрыт элемент И 13 по первому входу от генератора импульсов 14. Выход элемента И 13 с нулевым сигналом, поступающим на вход сброса триггера 15, не приводит к его переключению и формированию сигнала ГОТОВ на выходе 17 триггера 15.

По сигналу ПУСК по входу 18 триггер 9 устанавливается в единичное состояние, открывая элемент И 12 по второму входу. По первому импульсу генератора, проходящему через элемент И 12 и далее через элементы И 3 в блоках 1₁ и 1₂ на синхровходы регистров 2, производится передача числа A₁ в регистр 2 блока 1₂ анализа через группу элементов И 4, а числа А₂ - регистр 2 блока 1₁ анализа через группу элементов И 5. Затем импульсом, задержанным элементом 10 задержки, устанавливается в единичное состояние триггер 9, чем определяется второй этап первого цикла.

Таким образом, после первого этапа в регистрах 2 блоков 1₁ - 1₄ анализа из последовательности чисел 10, 8, 4, 5 формируется последовательность 8, 10, 4, 5.

При таком расположении чисел схемы 7 сравнения формируют позиционный код сравнения 0101, так как A₁<А₂, А₂>А₃, А₃<А₄, A₁>А₄. Единичное состояние триггера 9 определяет позиционный код коммутации 0101. Элементы И 8 всех блоков анализа выполняют побитовую обработку позиционного кода сравнения со значением 0101, поступающего на вторые входы элементов И 8, с позиционным кодом коммутации со значением 0101, поступающего на первые входы элементов И 8. Единичный сигнал с выхода И 8 блока 1₂ через элементы ИЛИ 6 в блоках 1₂ и 1₃ анализа открывает по первым входам элементы И 3. Единичный сигнал с выхода И 8 блока 1₄ через элементы ИЛИ 6 в блоках 1₁ и 1₄ анализа открывает по первым входам элементы И 3.

Вторым импульсом генератора 14, проходящим через элементы И 12, И 13 в блоках 1₂ и 1₃, 1₁ и 1₄ на синхровходы регистров 2, обеспечивается перезапись кодов чисел через группы элементов И 5 и И 4 соответственно. По окончании переходных процессов в регистрах 2 блоков 1₁-1₄ последовательность чисел 8, 10, 4, 5 преобразуется в последовательность 5, 4, 10, 8.

Через некоторое время импульсом, задержанным элементом 10 задержки, триггер 9 устанавливается в нулевое состояние.

Аналогично рассмотренному, но уже для числовой последовательности 5, 4, 10, 8 на выходах "больше" схем 7 формируется позиционный код сравнения 1010, так как А₁>А₂, А₂<А₃, А₃>А₄, A₁<А₄. Нулевое состояние триггера 9 определяет позиционный код коммутации 1010. Элементы И 8 всех блоков анализа выполняют побитовую обработку позиционного кода сравнения со значением 1010, поступающего на вторые входы элементов И 8, с позиционным кодом коммутации со значением 1010, поступающего на первые входы элементов И 8. Единичный сигнал с выхода элемента И 8 блока 1₁ через элементы ИЛИ 6 в блоках 1₁ и 1₂ открывает по первым входам элементы И 3. Единичный сигнал с выхода элемента И 8 блока 1₃ через элементы ИЛИ 6 в блоках анализа 1₃ и 1₄ открывает по первым входам элементы И 3.

Третьим импульсом генератора 14, проходящим через элементы И 12, И 13 в блоках 1₁ и 1₂, 1₃ и 1₄ на синхровходы регистров 2, обеспечивается перезапись кодов чисел через группы элементов И 5 и И 4 соответственно. По окончании переходных процессов в регистрах 2 блоков 1₁-1₄ последовательность чисел 5, 4, 10, 8 преобразуется в последовательность 4, 5, 8, 10. При этом на входах "больше" схем 7 сравнения всех блоков 1₁-1₄ устанавливаются нулевые сигналы, по которым на выходе элемента ИЛИ-НЕ 11 формируется единичный сигнал, открывающий элемент И 13.

Четвертым импульсом генератора 14 через элементы И 12, И 13 устанавливается триггер 15 в нулевое состояние. Единичный сигнал с нулевого выхода триггера 15, поступающий на вход 17, используется в качестве сигнала готовности устройства к считыванию упорядоченного массива и сортировки очередного массива чисел.

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

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

Устройство для сортировки чисел, содержащее триггер управления, триггер коммутации, элемент задержки, два элемента И, элемент ИЛИ-НЕ, генератор импульсов и n блоков анализа, где n - количество сравниваемых чисел, каждый блок анализа содержит регистр, элемент И и группу элементов И, выходы которых соединены с информационными входами регистра, выходы разрядов которого являются информационными выходами блока анализа, каждый блок анализа, кроме n-го, дополнительно содержит второй элемент И и схему сравнения, блоки анализа со второго по (n-1)-й содержат дополнительно элемент ИЛИ и вторую группу элементов И, выходы которых объединены с выходами соответствующих элементов И первой группы, отличающееся тем, что в первый блок анализа дополнительно введены элемент И второй группы и элемент ИЛИ, в n-й блок анализа дополнительно введены элемент ИЛИ, схема сравнения, второй элемент И и элемент И первой группы, управляющие входы первых групп элементов И нечетных блоков анализа, первые входы вторых элементов И нечетных блоков анализа и управляющие входы вторых групп элементов И четных блоков анализа соединены с инверсным выходом триггера коммутации, управляющие входы второй группы элементов И нечетных блоков анализа, управляющие входы первых групп элементов И четных блоков анализа и первые входы вторых элементов И четных блоков анализа соединены с прямым выходом триггера коммутации, в каждом блоке анализа выход первого элемента И подключен к синхровходу регистра, а к информационным входам регистра подключены выходы элементов И первой и второй групп, выход элемента ИЛИ блока анализа соединен со вторым входом первого элемента И блока анализа, в i-м блоке анализа, где i=1, 2,..., n-1, выход второго элемента И i-го блока анализа соединен со вторым входом элемента ИЛИ i-го блока, с первым входом элемента ИЛИ (i+1)-го блока анализа, выход второго элемента И n-го блока анализа подключен ко второму входу элемента ИЛИ n-го блока анализа и к первому входу элемента ИЛИ первого блока анализа, выход регистра j-го блока анализа, где j=2, 3,..., (n-1), соединен со вторым входом схемы сравнения (j-1)-го блока анализа, вторым входом элемента И первой группы (j-1)-го блока, с первым входом схемы сравнения j-го блока анализа, с первым входом элемента И второй группы (j+1)-го блока анализа, выход регистра n-го блока анализа соединен со вторым входом сравнения (n-1)-го блока анализа, со вторым входом элемента И первой группы (n-1)-го блока анализа, с первым входом схемы сравнения n-го блока и с первым входом элемента И второй группы элементов первого блока анализа, выход регистра первого блока анализа соединен с первым входом схемы сравнения первого блока анализа, с первым входом элемента И второй группы второго блока анализа, со вторым входом схемы сравнения n-го блока анализа и вторым входом элемента И первой группы n-го блока, выход схем сравнения всех блоков анализа подключен ко вторым входам второго элемента И соответствующего блока анализа и ко входам элемента ИЛИ-НЕ, выход которого подключен к первому входу второго элемента И, выход которого соединен с входом установки в нулевое состояние триггера управления, вход установки в единичное состояние которого подключен к входу запуска устройства, прямой выход подключен к первому входу первого элемента И, а инверсный выход триггера управления является выходом готовности устройства, ко второму входу первого элемента И устройства подключен генератор импульсов, выход первого элемента И подключен к первым входам первых элементов И всех блоков анализа, ко второму входу второго элемента И и через элемент задержки подключен к триггеру коммутации, информационные выходы блоков анализа являются выходами соответствующих отсортированных чисел устройства.