Устройство для сортировки @ -ичных чисел (его варианты) Советский патент 1986 года по МПК G06F7/08 

ел ел

00 Изобретение относится к вычислительной технике и может быть использовано при сортировке Б-разрядных S-ичньгх; чисел. Цель изобретения - повышение быст родействия и расширение области применения за счет обеспечения сортиров ки чисел, начиная с заданного. На фиг. 1 и 2 представлены функциональные схемы устройства по первому и второму вариантам; на фиг. 3 и 4 функциональные схемы i-ro () и 1-го блоков памяти чисел устройства соответственно по первому и второму вариантам; на фиг. За - функциональная схема блока памяти констант на фиг. 5 S ,6 примеры выполнения i-ro,и f-ro регистров ввода-вывода; на фиг. 5г - пример выполнения ключа на фиг, 6 и 7 - соответственно алгоритм вычисления данных для заполнения блоков памяти констант и пример такого заполнения (где х(у) - текущий номер бита; ACT (Амл) - старшие iS (младшие т) разряды адреса; Rx признак вывода опорного числа; Вх признак наличия числа, больше выводи мого; Ux - код большего числа; А(Д) код адреса и соответствующих ему дан ных; ВТу - значение бита с номером у; и - информационные выходы), Устройство по первому варианту со держит Б блоков 1 памяти чисел, Г блоков 2 памяти констант, (1-1) регистров 3, 2 регистров 4 ввода-вывода, I групп 5 ключей, (41-3) элементов ИЛИ 6, 2 (1-1) элементов И 7, (3Z-2) элементов 8 задержки, инфор. мационные входы-выходы 9, вход 10 разрешения записи опорного числа, вход 11 разрешения вывода, вход 12 разрешения чтения, тактовый вход 13, вход 14 разрешения записи данных вход 15 режима Чтение-запись, вход 16 данных, вход 17 запроса числа, тактовый выход 18, выход 19 конца работы и выход 20 признака вывода опорного числа. Устройство по второму варианту со держит Г блоков 21 памяти чисел, t блоков 22 памяти констант, (1-1) регистров 23, f регистров 24 ввода-вывода, 2 групп 25 ключей, (4Z-3) элементов ИЛИ 26, (31-2) элементов И 27 (31-2) элементов 28 задержки, инфор мационные входы-выходы 29, вход 30 разрешения записи опорного числа, вход 31 разрешения вывода, вход 32 азрешения чтения, тактовый вход 33, ход 34 разрешения записи данных, ход 35 режима Чтение-запись, вход 36 данных, вход 37 запроса числа, тактовый выход 38, выход 39 конца работы и выход 40 признака вывода опорного числа. Блок памяти чисел i-й по первому варианту (фиг. За) содержит S модулей 41 памяти, дешифратор 42 и элементы ИЛИ 43. Блок памяти чисел -й по первому варианту (фиг. 35) содержит S триггеров 44 и дешифратор 45. Блок памяти чисел i-й по второму варианту (фиг. 4а ) содержит S модулей 46 памяти, дешифратор 47, элементы ИЛИ 4В и элемент И 49. Блок памяти чисел Г-й по второму варианту (фиг. 4 &) содержит S триггеров 50, дешифратор 51 и элементы ИЛИ 52. Блок памяти констант (фиг. 5а ) содержит модуль 53 памяти и группу 54 ключей, Регистр ввода-вывода (фиг. 58 , в) содержит регистр 55 и группу 56 ключей. Ключ (фиг. 5 г) содержит транзисторы 57 и резисторы 58. Устройство по первому варианту работает следующим образом. В режиме подготовки устройства производится стирание данных во всех блоках 1 памяти чисел. Для этого на входах 12, 10, 13, 15 и 16 устройства устанавливают уровень логического О, что обеспечивает соответственно запрет чтения блоков 1, отключение выходов регистров 4 от адресных входов бита блоков 1, запрет ввода опорного числа, установку режима -записи и логического уровня данных, равного нулю, на входах блоков 1. Далее, устанавливая на информационных входахвыходах 9 устройства последовательно коды от О до (S -1) и сопровождая их стробирующим сигналом, подаваемым на вход 14 разрешения записи устройства, производят стирание (обнуление) данных во всех блоках 1 памяти чисел устройства. При этом информация с входов-выходов 9 устройства поступает на адресные входы слова и адресные входы бита блоков 1 памяти чисел. Значение адреса бита дешифрируется дешифратором.42 /45), что при наличии сигнала разрешения записи на входах позволяет через соответствующий элемент ИПИ 3 (непосредственно для блока 1р) произвести обращение, а следовательно, в данном случае и запись логического О в соответствующий модуль 41 памяти или триггер 44 По окончании данного режима устройства может быть переведено в режим ввода в него массива сортируемых чисел. В этом режиме, как и в предыдущем на входах 12, 10, 13 и.15 устройства остается уровень логического О, ана выходе 16 данных устройства устанавливается уровень логической 1 Далее, устанавливая на информационных входах-выходах 9 устройства коды сортируемых чисел и подавая сиг нал разрешения записи на вход 14 уст ройства, производят запись в блоки памяти чисел. Таким образом, каждое из введенных в устройство чисел отме чается установкой бита в состояние логической 1, адрес которого равен коду этого числа. Рассмотрим пример работы устройст ва для сортировки трехразрядных вось меричных чисел, т.е. , , . Допустим, что в устройство введе ны последовательно следующие числа: 145, 413, 237 и 235. Тогда в следующих блоках 1 памяти чисел по следующим адресам устанавливается состояние логической в блоке 1 по адресам 1,2 и 4; в блоке 1 по ад адресам 14,23 и 41; в блоке адресам 145, 235, 237 и 413. По окончании ввода в устройство сортируемых чисел оно может быть переведено в режим ввода опорного числа, относительно которого в следующем режиме осуществляется вьщача чисел в упорядоченной последовательности. Код опорного числа, например 235, устанавливается на входах-выходах 9 устройства, так, что на адресных входах слова блоков 1j и 1, памяти Цисел устанавливаются адреса 2 и 23 соответственно. При этом на входах 9-14, 16 и 15 устройства установлены соответственно уровни логических О и 1. Затем на вход 12 устройства Подается сигнал, разрешающий чтение информации из блоков 1 и 1, . Сигнал чтения поступает на входы 12 блоков 1 и 1,, и далее через элементы ИЛИ 4 осуществляется обращение по всем мо584дулям 41 памяти, после чего на их выходах образуются данные, соответствующие указанным адресам, а именно: на выходе блока 1 код 00010000, на выходе регистра 3 код 00000101. Кроме того, сигнал разрешения чтения с входа 12 устройства поступает через элементы ИЛИ 6 и элементы 8 задержки на тактовые входы регистров 3 и входы установки в О регистров 4, тем самым обеспечивая запись информации с выходов блоков Ij и 1 в соответствующие регистры 3. Затем уровнем логической 1 по входу 9 устройства открьгоаются ключи 5, что обеспечивает установку на информационных входах регистров 4 кодов соответствующих разрядов опорного числа 235. Затем на входе 13 устройства формируется сигнал разрешения ввода кода опорного числа, который поступает через элементы ИЛИ 6 на тактовые входы регистров 4и производит запись в них указанной информации: в регистр 4 кода 2, в регистр 4 кода 3, в регистр 4 кода 5. По окончании ввода опорного числа устройство может быть переведено в режим выдачи введенных в него числе в упорядоченной последовательности, начиная с опорного числа. Дпя этого внешний источник данных (кодов адресов и кодов чисел в предыдущих режимах) отключается от входов-выходов 9 устройства. Ключи 5переводом входа 9 устройства в состояние логического О закрываются, а выходы блоков 2 памяти констант и регистров 4 выводятся из третьего i состояния переводом входа 10 устройства в состояние логической 1, на выходах модулей памяти и выходах регистров 34 появляется значимая информация. Входы 13 и 14 устройства установлены в состояние логического О, а вход 15 - в состояние логической 1. Блок 2 памяти констант состоит из последовательно соединенных модуля 53 памяти и группы 54 ключей. В модуле 53 памяти закодированы результаты анализа адресов и значений битов S-разрядного слова, поступающего на адресньм вход блока 2. На другой адресный вход поступает гаазрядный код () адреса бита в этом слове. Сущность анализа состоит в том, что для каждого возможного значения т-разрядцого кода определяется соответствующее ему значение бита в S-разрядном слое и, если оно равно нулю (единице), значение признака R вывода опорного числа равно нулю (единице). Далее анализируются биты, адреса которых больше заданного т-разрядного кода. После нахождения первого бита, установленного в состояние логической 1, его адрес фиксируется в поле данных (И), а значение призна ка В наличия числа, большего выводимого, становится равным единице. Если нет ни одного бита, установленного в состояние логической 1, адрес которого больше заданного т-разрядного кода, то значение признака В становится равным нулю, а значение М становится несущественным. Пример анализа (S-8, ) байта 01100101 показан на фиг. 7. Полньш алгоритм вычисления данных для заполнения модуля 53 памяти показан на фиг. 6. Та КИМ образом, каждый модуль 53 памяти должен вмещать (т+2)-разрядных слов для блоков 2 ламяти констан Устройство в режиме выдачи из него чисел в упорядоченной последова тельности для указанного примера работает следующим образом. После занесения в регистры 4 кода 235 опорного числа этот же код присутствует на входах-выходах 19 устройства, т.е. на адресных входах блоков 1 ,2 и 1 , установлены соответственно адреса слова 2 и 23. Адреса бита, поступающие на входы блоков Ц 1, 1, , на них никакого влияния не оказывают, так как на их входах разрешения записи установлен уровень логического .О. Далее, ключи 5 закрьшаются нулевым логическим уровнем на входе 9 устройства, а выходы модулей 53 памяти и регистров 34 логически соединяются с выходами блоков 2 памяти констант и выходами регистров 4 за счет того, что соответствующие ключи 54 и 56 открываются единичным логическим уровнем на входе 10 устройства, на входах 13,14 и 16 которого установлены уровни логического О . На входе 15 устройства установлен уровень логической 1, разрешающий режим чтения из блоков 1 памяти чисел. Для рассматриваемого примера к данному моменту на адресных входах 1 8 6 блоков 2 памяти констант, входящих в состав блоков , Ц, 1 и 1,, соответственно установлены следующие коды: 01101000 и 010; 00010000 и 011; 00000101 и 101, а следовательно, в соответствии с алгоритмом работы блока 1 памяти констант на их выходах (И, R, В) присутствуют следуюш 1е коды: 100, 1,1; Н, 1,0 и 111,1,1, где й - .незначащий код. При выводе чисел из устройства в упорядоченной последовательности от меньшего к большему, начиная с опорного, первым анализируется выход 20 признака вывода опорного числа. Если этот выход установлен в состояние логической 1, то, последовательно, на входах-выходах 9 устройства находится код числа, равного опорному, т.е. код 235. После приема кода этого числа приемник данных (источник и приемник данных (не показаны) анализирует значение логического уровня на выходе 19, наличие кода большего числа устройства. Если на нем присутствует уровень логической то в устройстве еще имеются не выведенные из него числа. Для рассматриваемого примера этот уровень является единичным, так как выходы В блоков 2 логически объединены эле- ментами РШИ 6. Каждое следующее число выводится из устройства по сигналу, подаваемому на вход 17 запроса числа устройства. Прохождение этого сигнала блокируется единичным уровнем на инверсном входе элемента И 7(). Далее этот сигнал поступает через элемент ИЛИб, элемент И 7 и элемент ИЛИ 6 на тактовый вход регистра 4, и производит в него запись кода 111 (7), т.е. на входах-выходах 19 устройства появляется код следующего числа 237. Через время, достаточное для установления информации, на выходе регистра 4, а следовательно, и на тактовом выходе 18устройства появляется единичный сигнал,.сообщающий приемнику данных о наличии на входах-выходах 9 устройства кода следующего по величине из сортируемых чисел. Так как на выходе 19устройства остается уровень логической 1, приемник данных снова формирует сигнал на входе 17 запроса числа устройства, который блокируется элементом И 7 (так как выход В блока 2 памяти констант установлен уже в состояние логического О), но про пускается элементом И 7 . Далее его прохождение блокируется через элемент И 7 по той же причине, что и для элемента И 7, , но разрешается через элемент И 7, с выхода которог он поступает через элемент ИЛИ 64 на тактовый вход регистра 4 , разреша запись в него кода следующего числа в данном разряде, а именно кода 100 (4). После того, как этот код установится на выходе регистра 4, а следовательно, и на адресных входа блоков 1 и 1,, на выходе элемента 8 задержки появляется сигнал, который поступает на элемент ИЛИ 6. , с выход которого он поступает на вход разрешения чтения блока 1 памяти чисел и вход элемента 8 задержки. После того, как на выходах блока l установятся действительные данные (в данном случае код 01000000), на выходе элемента В задержки появляется сигнал, производящий запись этих дан ных в регистр 3 и обнуление регистра 4. При этом на выходах И, R, В блок памяти констант устанавливаются следующие коды: 010, 0,1. Далее сигнал запроса числа с выхода элемента 8 задержки поступает через элемент ИЛИ 6д, элемент И 7 Ц элемент ИЛИ 6 на тактовый вход регистра 4, производя запись в него кода 010 (2). После установки этого кода на выходе регистра 4 ,а следовательно,и на адресных входах блока 1 сигнал запроса числа появляется на выходе элемента 8 задержки, с которого он поступает на вход блока 1 памяти чисел и вход элемента 8 задержки и одновременно осуществляет чтение слова по адресу 41, которое дарее записьшается в регистр 31, и, кроме того, обнуляет регистр 4,. Таким образом, на адресных входах А р и А блок а 2 памяти « констант установлены коды: 000 и 00010000. Следовательно, на его выздадах И, R, В появляются соответственно коды 011,0,1. Далее аналогично тому, как это описано для блока 1 (и), с выходов блока 2, памяти констант код переписывается в регистр 4. Таким образом, на входах-выходах 9 устройства появляется код числа 413, а на выходах 18 и 19 устройства появляются уровни логических 1 и О, подтверждающие наличие на входах-выходах 19 действительных данных и то, что это число является последним. Устройство для сортировки чисел по второму варианту работает аналогично устройству по первому варианту. Отличие состоит лишь в том, что в этом устройстве для повьшения быстродействия в режиме стирания информации в блоках 1 памяти чисел введены элементы И 27, через которые (в случае, если сигнал на выходе В равен уровню логического О, т.е. анализ слова завершен) сигнал запроса числа с выхода элемента 28 задержки поступает на вход (на входе 36 данных устройства в этом режиме установлен уровень логического блоков 21 памяти чисел, прох6 ;ит через элементы ИЛИ 48 и осуществляет обращение (запись) в модули 46 памяти (триггеры 50). При этом сигнал обращения устанавливает на выходе элемента И 49 блока 21 уровень логического О, что задает на модулях 46 памяти режим записи. В результате стираются данные по текущему адресу в блоке 21. Технико-экономическая эффективность изобретения по сравнению с известным устройством состоит в расширении класса решаемых задач за счет обеспечения возможности вывода чисел в упорядоченной последовательности, начиная с заданного, а также в том, что повышается быстродействие устройства. Время вывода N чисел в упорядоченной последовательности из известного устройства пропорционально величине (I+1), где TS - время j задержки распространения информации через один блок для сортировки чисеЛ. Ввиду сложности получения времени вывода N чисел в упорядоченной последовательности из предлагаемого .устройства для произвольного коэффициента их заполнения числовой шкалы от О до (S -1) проведем сравнение для вух крайних случаев. В первом случае коэффициент заполнения числовой шкалы настолько мал, то информация должна проходить чеез все блоки 2 и 1, т.е. время выода пропорционально величине . Во втором случае коэффициент заолнения числовой шкалы равен единие. Тогда время вывода пропорциональоs (г-к+1)-. Так как Т для известного и предлагаемого устройств примерно равно, коэффициент повышения быстродействия К с находится в следующих пределах: S (f+1) 6К. S s cl-K+D Для рассмотренного при описании работы устройства примера (, ) 1,3 Кс 4 3,1. Для устройства по второму вариант по сравнению с устройством по первому варианту время стирания информаци сокращается на N тактов обращения к блокам памяти чисел, так как это сти рание происходит параллельно с выводом информации из устройства. Применение устройства по второму варианту наиболее эффективно в случае, если после каждого вывода инфо.рмации из устройства в упорядоченной последова тельности в него вводится следующий массив чисел, подлежащий сортировке. Ф о р мула изобрет е н и я . 1 .Устройство для сортировки S-ичны чисел, где S - основание системы счисления, содержащее И блоков памяти чисел, где I - разность сортируемых чисел, (1-1) регистров, Zt элементов задержки и элемент ИЛИ, выход которого является выходом конца работы устройства, вход разрешения записи данных устройства соединен: с входами разрешения записи всех блоков памяти чисел, выходы i-ro бло ка памяти, где ,2,... ,-1, соеди-Ьены с информационными входами i-ro регистра, первый вход управления выборкой i-ro блока памяти чисел соединен с входом разрешения чтения уст ройства, выход i-ro элемента задержки соединен с тактовым входом i-ro регистра, отличающееся тем, что, с целью повышения быстродействия и расширения области применения за счет обеспечения сортировки чисел, начиная с заданного, в него введены блоков памяти констант I регистров ввода-вывода, f групп п m ключей, (т Clo,tSl) , (2-2) эле1ентов задержки, 3 (f-.1) элементов ЛИ и 2 (-1) элементов И, причем вход данных устройства соединен с входами данных всех блоков памяти чисел, выходы i-ro регистра соединены с соответствующими адресными входами первой группы i-ro блока памяти констант, выходы 2-го блока памяти чисел соединены с соответствующими адресными входами первой группы J-го блока памяти констант, информационные входы-выходы К-й т-разрядной группы устройства (,2,..,,1) соединены с соответствукицими адресными входами бита К-го блока памяти чисел, с соответствующими адресными входами второй группы К-го блока памяти, с соответствующими информационными входами ключей К-й группы и выходами Ic-ro регистра ввода-вывода, входы которого соединены с соответствующими выходами k -го блока памяти констант и выходами соответствующих ключей К-й группы, информационные входы-выходы т-разрядной j-й группы устройства, где , k+2,...,J, соединены с соответствуюпщми адресными входами слова (j-k)-й группы К-го блока памяти, вход режима Чтение-запись устройства соединен с входом режима Чтение-запись i-ro блока памяти чисел, второй вход управления выборкой которого соединен с входом i-ro элемента задержки и выходом ()-ro элемента ИЛИ, первый и второй входы которого соединены с входом разрешения чтения устройства и выходом i+Jго элемента задержки соответственно, тактовьА вход устройства соединен с первым входом (k+E-1)-ro элемента ИЛИ, выход которого соединен с тактовым входом К-го регистра ввода-вывода, вход установки в состояние ывода которого и вход разрешения выборки k -го блока памяти констант соединены с входом разрешения вывода устройства, вход разрешения записи заданного числа устройства соединен с управляющими входами ключей k-и группы, выход i-ro элемента задержки соединен с входом установки в О i-ro регистра ввода-вывода и через (i+2J-1)-й элемент задержки соединен С первым входом (i+3f-2)-ro элемента ИЛИ, выход которого соединен с первым входом i-ro элемента И, вход запроса числа устройства соединен с вторым входом (31-1)-го элемента ИЛИ и первым входом Б-го элемента И, выход каждого (i+2-1)-ro элемента И, кроме 2 (2-1)-го, соединен с первым входом (i+I)-ro элемента И и с вторы входом (i-3i-2)-ro элемента ИЛИ, выход 2(1-1)-го элемента И соединен с вторым входом ()-го элемента ИЛИ и с входом (22-1)-го элемента задерж ки, выход признака наличия большего числа i-ro блока памяти констант соединен с инверсным входом i+(I-1)го элемента И, с первьпу входом i-ro элемента ИЛИ и с вторым входом i-ro элемента И, выход которого соединен с вторым входом i+( J-1) элемента ИЛИ и входом i-(J-1)-гго элемента задержки, вьгход признака наличия большего числа -го блока памяти кон стант соединен с вторым входом (J-1) го элемента ИЛИ, второй вход кжадого q-ro элемента ИЛИ, где ,.,.,I-2, соединен с выходом (q+1)-ro элемента ИЛИ, вьгход 1-го элемента задержки является тактовым выходом устройства выход признака вывода опорного числа первого блока памяти констант являет ся одноименным выходом устройства, 2,Устройство по п. 1,отличающееся тем, что 2-ной блок памяти чисел содержит S триггеров и дешифратор, информационный и управляющий входы которого являются соответственно адресными входами бита и входом разрешения записи 5-го блока памяти чисел, вход данных и выходы Б-го блока памяти чисел соединены со ответственно с информационными входами и выходами триггеров, синхровходы которых соединены с соответствующими выходами дешифратора. 3.Устройство по п. 1, отличающееся тем, что i-й блок памяти чисел содержит дешифратор, S элементов ИЛИ, S модулей памяти, каждый из которых содержит S однобитовых ячеек памяти, вход управления выборкой каждого модуля памлти соединен с выходом соответствующего элемента ИЛИ, первый и второй входы которого соединены соответственно с первым и вторым входами управления выборкой i-ro блока памяти чисел, а третий вход - с соответствующим выходом дешифратора, информационные и управляющие входы которого являются соответственно адресными входами бита и входом разрешения записи i-ro блока памяти чисел, входы режима Чтение-запись данных и адресные входы слова i-й группы которого соединены с соответствующими входами режима Чтение-запись данных и адресными входами слова каждого модуля памяти, выходы которых являются выходами 1-го блока памяти чисел. 4, Устройство для сортировки S-ичных чисел, где S - основание системы счисления, содержащее Г блоков памяти чисел, где X - разрядность сортируемых чисел, (-1) регистров, 2 элементов задержки и элемент ИЛИ, выход которого является выходом конца работы :5гстройства, вход разрешения записи данных устройства соединен .с входами разрешения записи всех блоков памяти чисел, выходы i-ro блока памяти чисел, где ,2,.,.,1-1, соединены соответственно с информационными входами i-ro регистра, первьш вход управления выборкой i-ro блока памяти чисел соединен с входом разрешения записи устройства, выход i-ro элемента задержки соединен с тактовым входом i-ro регистра, отличающееся тем, что, с целью повышения быстродействия и расширения области применения за счет обеспечения copTi-фовки чисел, начиная с заданного, в него введены Е блоков памяти констант, S групп по m ключей, где m , I регистров ввода-вывода, (J-2) элементов задержки, 3(-1) элементов ИЖ и (32-2) элементов И, причем вход данных устройства соединен с входами данных всех блоков памяти чисел, выходы i-ro регистра соединены соответственно с адресными входами первой группы i-ro блока па7 мяти констант, выходы -го блока памяти чисел соединены соответственно с адресными входами первой группы J-ro блока памяти констант, информационные входы-выходы К-й т-разрядной группы устройства, где ,2,..,,, соединены соответственно с адресными входами бита К-го блока памятичисел, с адресными входами второй группы К-го блока памяти констант, с информационными входами ключей К-й группы и С выходами К-го регистра ввода-вывода, входы которого соединены соответственно с m выходами К-го блока памяти констант и выходами ключей К-й группы, информационные входы-выводы т-разрядной j-й группы устройства, где , k+2,...,I, соединены COOTветственно с адресными входами слова (j-k)-ft группы К-го блока памяти чисел, вход режима Чтение-запись устройства соединен с входом режима Чтение-запись i-ro блока памяти 1исел, второй вход управления выборкой которого соединен с входом i-ro элемента задержки и выходом i + + (21-1)-го элемента ИЛИ, первый вход которого соединен с входом разрешения чтения устройства, а второй вход соединен с выходом (i+l)-ro элемента задержки и первым входом i+(2I-1)}-го элемента И, выход кото рого соединен с входом разрешения стирания (i+1)-ro блока памяти чисел тактовый вход устройства соединен с первым входом k+(J-1)-ro элемента ИЛИ, выход.которого соединен с такто вым входом К-го регистра ввода-вывода, вход установки в состояние вывод которого и тактовый вход соответству ющего К-го блока памяти констант Сое динены с входом разрешения вьшода устройства, вход разрешения записи заданного числа устройства соединен с управляющими входами ключей К-й группы, выход i-ro элемента задержки соединен с входом установки в О i-ro регистра ввода-вывода и через i-(2|-1)} -и задержки соедине с первым входом i+(3J-2)-ro элемент ИЛИ, выход которого соединен с первы входом i-ro элемента И, вход запрос числа устройства соединен с вторым входом (31-1)-го элемента ИЛИ и пер вым входом S-ro элемента И, вьпсод каждого .i+(l-1 )3-го элемента И, кр ,ме 2 (1-1), соединен с первым входом (i+l)-ro элемента И и с вторым входом i+(3l-2)J-ro элемента ИЛИ, выход 2(1-1)-го элемента И соединен с вторым входом ()-го элемента ИЛИ и входом ()-гоэлемента задержки, выход признака большего числа i-блока памяти констант соединен с инверсными входами i+(i-1)3 го и i+2(I-1)J-го элементов И, с первым входом i-ro элемента ИЛИ и с вторым входом i-ro элемента И, выход которого соединен с вторым входом i+( J-1 ) элемента ИЛИ и с входом i+d-Dj-ro элемента задерж ки, выход признака наличия большего числа -го блока памяти констант со динен с инверсным входом (3f-2)-ro элемента И, с вторым входом ($-1)-г элемента ИЛИ, второй вход каждого i-ro элемента ИЛИ с первого по (Г-2)-й соеди11е;н с , ( )-го элемента ИЛИ, выход Р-го элемента задержки является тактовым выходом устройства, выход признака вывода опорного числа первого блока памяти констант является одноименным выходом устройства. 5, Устройство по п. 4, отличающееся тем, что 1-й памяти содержит 1 триггеров, S элементов И и дешифратор, информационные и управляющий входы которого являются г- ответственно адресными входами бита fe входом разрешения записи 1-го блока памяти чисел, вход данных и выходы памяти чисел соединены соответственно с информационными входами и выходами триггеров, синхровходы которых соединены с выходами соответствующих элементов ИЛИ, первый, вход каждого элемента ИЛИ соединен с соответствующим выходом дешифратора, а второй вход соединен с входом разрешения стирания 1-го блока памяти чисел. 6. Устройство по п. 4, о т л ичающееся тем, что i-й блок памяти чисел содержит дешифратор, S элементов ИЛИ, элемент И и S модулей памяти, каждый из которых содержит S однобитовых ячеек памяти, вход управления выборкой каждого модуля памяти соединен с выходом соответствующего элемента ИЛИ, первый и второй входы которого соединены соответственно с первым и вторым входами управления выборкой i-ro блока памяти чисел, а третий вход соединен с соответствующим выходом дешифратора, информационные и управляющий входы которого являются соответственно адресными и входом разрешения записи i-ro памяти чисел, вход даишых и адресные входы слова i-ro блока памяти чисел соединены соответственно с входом данных и адресными входами слова соответствующего модуля памяти, вход режима Чтение-запись каждого модуля памяти соединен с выходом элемента И, инверсный вход которого соединен с четвертыми входами э;пементов ИЛИ и является входом paSр апения стирания i-ro блока памяти чисел, вход режима Чтение-записв i-ro блока памяти чисел соединен с прямым входом элемента И, выходы модулей памяти являются выходами i-ro блока памяти чисел.

Изобретение относится к области вычислительной техники. Цель изобретения .- повышение быстродействия и расширение области применения за счет обеспечения возможности сортировки чисел, начиная с заданного. Указанный положительный эффект в устройстве по первому и второму вариантам достигается, в частности, введением блоков памяти констант, обеспечивающих ускорение поиска следующего по величине числа на интервале числовой шкалы в S единиц. Устройство по второму варианту, кроме того, имеет более высокое быстродействие по сравнению с устройством по первому варианту за счет сокращения времени сортировки на N тактов, где N - число сортируемых чисел, обеспечиваемого стиранием прежней информации параллельно с ее выводом. Поэтому его с (О применение наиболее эффективно в слу(Л чае часто изменяемого массива сортируемых чисел. 2 с.п. ф.п.,4 з.п. с ф.п., 7 ил.

Om9i

Sml6 Om150fn1t4 OmK ffmSi fSe-t)

a

ОтЩ

(пЪЧ (2e-f) Oml7i(ze-i a am8,l29,lОтШЗП

ОтЗ,(Щ

0m 16 dm 14 g

.3

Om29e

От 38

.4

$5

&rrS/2e)if., Й

4l2f{ e

Фиг.5

Йичало

Ж

1 JE

|j °дr;/iл |

, Ам/1 а,Ш,., Sx

О

z

3

ft

5 6

Фиг. 7