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

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

Иллюстрации

Показать все

Реферат

 

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

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

СООИАЛИСТИЧЕСНИХ

РЕСГ1У БЛИН

<б1>, G 06 Е 7/06 ч,,f

4 с ф

/ A.,, l

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ.(2 1) 3998224/24-24 (22) 29.12.85 (46) 07,06.87. Бюл. № 21 (72) В.Н.Заблоцкий, A.À.Ñàìóñåâ и A,В.Яскульдович (53) 68 1.325 (088.8) (56) Авторское свидетельство СССР

¹ 1007099, кл. G 06 F 7/08, 1983.

Авторское свидетельство СССР № 424141, кл, G 06 F 7/06, 1974. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для сортировки массивов данных, поступающих параллельными кодами одно за другим в реальном масштабе времени,. Целью изобретения является расширение функциональных возможностей за счет обеспечения возможности задания диа13 )5967 пазона сортируемых чисел и орг=;r(tr=ации очередей элементов данных, Устройство содержит ячейки 1 анализа„ обьединенные в виде прямоугольной матрицы,,первую и вторую груп((ы эле-ментов ИЛИ 2 и 3,, причем ка>(дь.:"(с ог-бец матрицы содержит И ячеек„, где ((1 7q 2„ а кажцая с":"рока ма (рицы содер>кит 1 ячеек, где 1 — такое. что

1 1 Ъ m 1(. — I(QII! i(ecTBQ Р(1 з3>ЯЦОв одной ячейке; m — 1(олнчес".:.во разрядов в сортируемых числах, Ячейка ана.= лиза содержит узел памяти, схемусравнения, узел формирования управ- ляющих сигналов, включающий элементы И и ИЛИ. Ячейки в матрице и первая и вторая группы элементов ИЛИ связаны между собой ii с внешними пп(Изобретение относится к вьг(исли †. тельной технике и мО;.ет быт(- использовано в специал((зированных у".òðîéствах, пред азначеннь(х для сортировки массивов данных пэступающи>: п»раллельными кодами одно за другим в реальном масштабе времени, Целью изобретения являе. ся рас-. ширение функцио.-(альных воэможностей за счет обеспечения >возможности задания диапазона сортируемых чисел и

ОРГаииэаЦ((И ОчЕ(>ЕЦЕЙ:>ЛЕМЕПТОВ Данных.

На (1>rrr, 1 r1BoGpa;t(eBa с Tpóêòóð Ball схема устройства для сортировки чисел; на фиг. 2 — то же„ ячейки анализа информации; на фиг. 3 — функци-ональная схема узла формирования >п-. равляющих сигналов, Устройство содержит ячейки I ана-лиза, первую группу злемен.оь ИПИ 2., ВтОрую группу элементОв И.(И З.пер вый выход ч устройства. второй выхоц 5 отсортированного числа устройства Bï!IJQp— мационный вход 6., вход 7 сравнпваеМЫХ ЧИСЕЛ, таКтОВЫй: †:ХОд с>., iiepBbt!.". и второй разрядь(yripaB>zato(OJ о кода

9, первый и второй выходы 10 резуль-тата сравнения, первый 1I l вт;>рой

12 входы установки реж((ма устрой(тва, дополнительный вход l3. Ячейка

С>ОРМад((ОННЬ(МИ И УПРаВЛЯЮ(((И(с" ВХОЦаМ:1

Taким образом,,что пр(вводе в уст— ройство Очеред- lогo числа 0".о запи сы13ается в ячейки той . т1>о си;-.(атpilпы,. B я (ейках 1(стоцой уже бь>г о эапи--CаНО ЧИ("IQ .!el!i>(ЦЕО;3ВС(я(11(QГС, По

i-cJt»жай шее к -re J«v, -1:(CJia >сс>(.1 " .(bre я-(ей(сах 11рсцыцущ(=х стро(с матриьь(, (со-. торыс явля(ется рав-(в(ми ит(и большими

:О B>laiJellИю BBQi(rr?(OÃO чИС>(а, COXp2няютс.я без изменен (й, Числ"., хран(-"МЫ,— B ЯЧЕ(1(СBX JIOCãli=-;т (ОЩИХ CтРОК и той строки,, в ячейки которой записьпзается ввоцимое п(сло, которые JIB"ля(отся (еньшими по значению вводимог0, одповреме((но пзрепис .bIBatoTci(в

;П-Ейх(1 СОСЕДПИ.- ПОСЛЕД>;>(Л(>(с: ГРО(С ч

;, 2 "т ITJbt. 0 Ил, анализа содержит у;ел 1 4 пак(яти .. схему 1з сравнепия., узел 16 (рор((ирогa пия управ((я(т(1>с сил алов, котor.ый со(сер>кит элеме.(òI.J И 17 и 18 „ИЛИ 19

Ус.. ойство (фиг. 1) пля сортивов— э ки i(исе ра зотает r .(e тт oi(;J -:, Q >t-,азом

Перец началом фун(с(н(онйрования,С. РОйСТВО 1(ЕРЕВОДИтСЯ 1. ИСХос(.-,-0e

co(1 Ояние, Для это I" О в устpoJ(CTBe

1с (редус>(от >cii режим пачаль(..ой установки (1>н. ) . 1(..->-. о ". режи !» на. входе

0 -7 -1 войс . Ba у; гап:-,вл-..(ae T я кoц 1(а-ч ИЛЬ:.OH ус та:JOB I(rl i -:а:.3СЕХ " Х-ОС(ах ,;с Tа1ьавливае -c(J код 00. на всех Bx(îax, i «c га:1авлила ется логичес ая ецин(1цa а на всех входа>» 1(? — логичес((гй(по —,ь и (:а вход 8 «;ода o r

И((Г(УГ(ЬС (ИНХР О НИЗ 2 ЦИИ ПО!Ц ger(0(ВИ (.м заднет 0 (1>1-ot(T которого В ячейт-и ка:(сцQ;",(C TOO,",.r, и,= Л-ц(BJ буь(е-- 22;i;-.:02 =

Оциц и тот же i(Qä начальнои ус :-а(01з-кт.:.. П->и . сп.-гьз 32н(пи;:(.1">Ой(тва пля

cQ pTppQB.(:i чисел., зна.!e (i. :B (3, 1(ото

1, (", (l2xoc,c(i с B о пв - (сээ> 0 С 1 « .> I в .ачеcTBе кОца «12 : 1ьной у с : Оновки

ИСПОЛЬЗУЕ 3 Ся- 1»УЛСВО 3 ОП (c01.c i(C

1(ользОВ яиц(и i cTð0éñ 1 Ва для совтиоов

-ки чисе.с- з -ra.-(ения ((.),, которых -2.— хоцятся в преде JG". П ь 1. 2 -1. в ка-. пользуетс:. код, з(. ".ение ".OTOpQòо

P 2.B:10 1 .:

15967 4 не, а также вследствие того,что первое число, хранимое в ячейках первой строки матрицы ячеек, имеет значение (А) большее П,, т.е. А> П.

f5

3 13

Кроме режима РНУ в устройстве предусмотрено шесть режимов функционирования: режим сортировки Э(РС); режим чтения (РЧ); режим хранения (РХ); режим организации очередей элементов данных типа LIFO(PL); режим организации очередей элементов данных типа FIFO(PF); режим организации очередей элементов данных типа ПРИОО(РП).

Режим РС. После режима РНУ, при котором в ячейках каждой строки мат- рицы запоминается код со значением

П 2i О, на каждом входе 9, на разрядах соответственно 20 и 21 устанавливается код 10. На всех входах 11 и 12 устанавливается логический ноль, кроме входа верхней строки матрицы, на котором устанавливается один и тот же код первого числа из массива . сортируемых чисел. Если первым числом является число со значением <П, то после действия синхросигнала на входе 8 содержимое ячеек матрицы не изменяется и устройство остается. в исходном состоянии, так как на всех выходах 10 устанавливается код 10 или 01, под действием которого на выходах всех элементов ИЛИ 2 и 3 сформируется логическая единица и на входах установки режимов записи всех ячеек устанавливается код 11, при котором узлы 4 памяти устанавливаются в режим хранения (РХ), Если первым числом является число, значение (Б), которого больше П, т.е, Б ) П, то узлы памяти в ячейках первой строки устанавливаются в режим 1Рз записи со входа 6, а ячеек j-x строк— в режим 2Рз записи с выхода ячеек ()-1)-х строк, где 1 = 2,...,Н.

После действия синхросигнала на входе 8 устройства код первого числа со входа 6 устройства записывается в узлах памяти ячеек первой строки. В ячейки последующих остальных строк переписывается код начальной установки из ячеек предыдущих строк матрицы ячеек.

После записи кода первого числа на входы 6 и 7 устройства устанавливается один и тот же код второго числа из массива оставшихся чисел.

Если значение (Б) второго числа оказывается меньше или равно П, т.е.

Б 4 П, то после действия синхросигнала на входе 8 содержимое ячеек не изменяется по указанной выше причиЕсли значение второго числа больше П, но меньше или равно первому числу со значением А, т,е, П < Б <А то в этом случае на выходе 10 первой строки матрицы ячеек устанавливается код 10 или 01, под действием которого на выходе элемента ИЛИ 2 и элемента ИЛИ 3 этой строки устанавливается логическая единица.Так как на входе 11 первой строки и, следовательно, на выходе элемента 2 этой строки установлена логическая единица, то на входах установки режима записи всех ячеек верхней строки устанавливается код 11, под действием которого в узлах памяти ячеек устанавливается режим РХ, т.е. код информации, записанный в ячейках пер вой строки, сохраняется без изменений. Так как в ячейках остальных строк хранится код начальной установки со значением П Б, то на выходах элементов ИЛИ 2 и 3 устанавливается логический ноль. В результате на входах установки режима записи ячеек второй строки матрицы устанавливается код 01, так как на выходе

10 первой строки устанавливается код

10 или 01, а на выходе элемента ИЛИ, 2 — логическая единица. В узлах памяти ячеек второй строки устанавливается режим 1Рз, т.е. в ячейки второй строки записывается код, установленный на входе 6 устройства. На входах установки режима записи всех, ячеек остальных строк устанавливается код 00, под действием которого в узлах памяти ячеек устанавливается режим 2Рз, т.е. в ячейки каждой последующей оставшейся строки переписаны коды начальной установки из ячеек, хранятся коды чисел, меныпих числа, код которого установлен на входах 6 и 7 устройства, но болыпих

П, то аналогичным образом переписываются числа, коды которых хранятся в ячейках 1-й строки в ячейки (j+.1)-й строки, где 3 1 М. Если значение второго числа больше значения первого, т.е. Б )A то на всех выходах 10 устанавливается код 00. Следовательно, на выходах всех элементов ИЛИ

2 и 3, кроме элемента ИЛИ 2 первой строки, устанавливается логический

1315967 6 ноль, а на его выходе устанавливается логическая единица.:Ha xo a yc/ тановки режимов записи всех ячеек первой строки устанавливается код

01, под действием которого в узлах памяти ячеек первой строки устанавливается режим 1Рз т.е. в ячейки первой строки записывается код, установленный на входе 6 устройства„

На входах установки режима записи ячеек всех остальных строк (2 "j «< N 1 4 1 1) устанавливается код 00, под действием которого в узлах памяти ячеек устанавливается режим 2Рз. Это значит, что в ячейки второй строки переписан код числа, хранимого в ячейках первой строки, В ячейки третьей строки переписан код числа, хранимого в ячейках второй строки, и т.д. в ячейках N-й строки переписан код числа, хранимого в ячейках (N-1)-й строки.

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

Предположим, что отсортировано и хранится в устройстве (n-i) чисел и подается очередное М-е число, где

М >i n. Если это число больше числа, код которого хранится в ячейках первой строки, то код его записан в ячейках первой строки, а коцы чисел, хранимые в ячейках каждой предыдущей строки, переписаны в ячейки последующих соседних строк, как это было описано выше, так как в ячейках остальных строк хранятся коды чисел, значение которых меньше значения числа, код которого хранится в ячейках первой строки. Если М вЂ” е число меньше меньшего отсортированного числа, но больше П, то код его записан в ячейки и-й строки, как это имело место при записи второго числа в ячейки второй строки. Если М-е число меньше или равно П, то оно не записано в устройстве также как и в с случае с первым и вторым числами, Положим, что значение (Е) М-го чис ла меньше или равно числу, код которого хранится в ячейках 1-й строки, но больше числа, код которого хранится в ячейках (j+1)-й строки. В этом случае код М-го числа будет записан в ячейки (j+1) é строки, Коды чисел, хранимые в ячейках строк с

ЗО

55 номерами большими, перепишутся в ячейки соседних строк с большими номерами, а коды чисел, хранимые в ячейках с номерами меньшими 1, останутся без изменений., Укаэанный случай аналогичен случаю записи второго числа в ячейке второй строки с тем отличием, что коды ",0 или 01 на выходе

10, где ((-1, благодаря которым на выходах соответствующих элементов ИЛИ устанавливается логическая единица и на входах установки режимов записи j ячеек ((c j 1 i 41) с номерами

« j устанавливается код 11, задающий режим хранения (РХ) узлов памяти ячеек, формируются как результат того, что значения чисел, хранимых в ячейках указанных строк:, больше значения

М-го числа.

Таким образом, в предлагаемом устройстве в ячейках первой строки матрицы ячеек записывается код наибольшего числа на всех сортируемых чисел массива. В ячейках второй строки записывается код наибольшего числа из всех оставшихся сортируемых чисел и т.д. в ячейках N-й строки записывается код наименьшего числа массива сортируемых чисел, В качестве признака того, что в устройстве хранится М отсортированных чисел является установка на выходах 4 кода со значением отличным от П или формирование на выходе 10 N-й строки матрицы кода 00 при установке на входе 7 устройства кода со значением П, В . противном случае на выходе 10 N-й строки устанавливается код 10 или 01..

Для расположения чисел в обратном порядке, т.е. в ячейках первой строки — минимального числа, а в ячейках

N-й строки — максимального числа достаточно на входы 6 и 7 устройства подавать дополнительные коды чисел,как это делается в известном устройстве.

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

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

Режим РЧ. Возможны два случая задания режима чтения в устройстве. В первом случае для задания режима чте ния на всех входах 9 устанавливается код 00, на всех входах 11 устанавливается логический ноль, а на всех входах 12 — логическая единица. 3атем на вход 8 устройства подают синхросигнал, под действием которого число, хранимое в ячейках j-ой строки, где 2 j N переписывается в ячейки (j-1)-й строки, благодаря свя зи выходов ячеек j-й строки со входа ми ячеек (j-1)-й строки, а также благодаря тому, что на выходах элементов ИЛИ 2 устанавливается логический ноль, а на выходах элементов

ИЛИ 3 устанавливается логическая единица., и, следовательно, на входах установки режима записи всех ячеек устанавливается код 10, под действием которого в узлах памяти всех ячеек устанавливается режим ЗРз. Код числа, хранимый в ячейках первой строки, может быть считан внешней системой с выхода 4 устройства под действием, например, того же синхросигнала, который подается на вход 8 устройства.

15967 8 максимального числа и кончая мини5

- 20

40 симальным.

После окончания действия синхросигнала на входе 8 код числа, хранимого в ячейках первой строки, стирается (удаляется из устройства), а на его место записывается код числа, хранимого в ячейках второй строки, в которые записывается код числа, хранимого в ячейках третьей строки и т.д. В ячейки N-й строки записывается код начальной установки. Установка на выходе 4 устройства после режима РЧ кода начальной установки является признаком того, что все отсортированные числа считаны (удалены) из устройства, устройство находится в исходном состоянии и вновь может быть использовано для сортировки новых чисел без установки режима РНУ. Считывание отсортированных чисел из устройства в рассматриваемом случае осуществляется, начиная с мальным.

Во втором случае для задания режима чтения на всех входах 9 устанавливается код 00, на всех входах

11 и 12 устанавливается логический ноль. На вход 8 подается синхросигнал, поц действием которого число; код которого хранится в ячейках j-й строки, где 1 4 1 < Й, переписывается в ячейки (j+1)-й строк, на входах установки режима записи всех ячеек устанавливается код 00, под действием которого в узлах памяти всех ячеек устанавливается режим 2Рз.Код числа, хранимого в ячейках N-й строки, может быть считан внешней системой с первого выхода устройства с выхода 4 под действием, например, того же синхросигнала, который подается на вход 8 устройсгва в режиме чтения.

После окончания действия синхросигнала на входе 8 код числа, хранимого в ячейках N-й строки, стирается (удаляется) из устройства, а в ячейки

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

4 после режима чтения в устройстве кода начальной установки, при условии, что до задания режима чтения устанавливался код, отличный от кода начальной установки, является признаком, что все отсортированные числа считаны (выведены) из устройства и оно готово для сортировки новых чисел без установки РНУ.

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

1315967

Режим РХ. Для задания режима РХ на всех входах 11 и 12 и, следовательно, на выходах элементов ИЛИ 2 и 3 устанавливается логическая единица. В результате на входах установки режима. записи всех ячеек устанавливается код 11, при котором узлы памяти ячеек устанавливаются в режим хранения и коды, хранимые в ячейках, не изменяются под действи- 10 ем синхросигнала, независимо от состояний, входов 6 и 7 устройства, Режим PL. Возможны несколько способов использования предлагаемого устройства для организации очередей 15 элементов данных типа LIFO, Рассмотрим в качестве примера один способ, когда организация очереди элементов данных типа LIFO осуществляется путем задания соответствующего режима 20 функционирования устройства. Этот режим аналогичен режиму PC с тем отличием, что при записи очередного элемента данных в устройство код его устанавливают на входе 6, а на вхо- 2g де 7 устройства устанавливают (постоянно) код с максимальным значениITl ем, т.е, равный 2 -1, где m — количестно разрядов устройства. В качестве элементов данных могут использоваться числа со значением (1.) (О (L <2 — 1) .

Каждый новый элемент данных воспринимается в устройстве как наиболь- 5 шее число по отношению к числам,хранимым в устройстве, так как оно воспринимается равным 2 -1, а в устройстве хранятся числа со значением меньшим 2 -1. В результате каждый

ftl новый элемент очереди записывается в ячейки первой строки. При этом в качестве кода начальной установки в устройстве используется нулевой код.

Установка на выходе 4 устройства не нулевого кода является признаком того, что очередь заполнена, т.е. в устройстве нет свободных ячеек памяти, Считывание элементов очереди осуществляется через выход 4 устройства в любой момент путем задания режима РЧ.

На выходе 4 всегда устанавливается код элемента данных, записанного в ячейки первой строки последним.Установка на выходе 4 устройства нуле— вого кода является признаком того, что очередь пуста, т,е. все элементы данных считаны из очереди.

l0

Режим PF..Режим PF аналогичен описанному режиму PL с тем отличием,что на входе ? устройства постоянно устанавливается нулевой код. В качестве элементов данных могут использоваться числа со значением (L) 0 < 1. «< 2 -1, где m — - количество разрядов в устройстве. В качестве кода начальной установки устройства используется нулевой код. В результате каждый новый элемент данных воспринимается как минимальное число по отношению к числам, хранимым в устройстве, и записывается в ячейку j-й строки при условии, что в ячейках (j-t)-й строки уже записан не нулевой код, т.е. предыдущий элемент данных. Считывание элементов данных осуществляется через выход 4 устройства путем задания в устройстве режима РЧ.

Режим РП. Режим РП аналогичен режиму РС, с тем отличием, что на К старших разрядах, где К < m, m — количество разрядов устройства, входов

6 и 7 устанавливается код величины приоритета очередного элемента данных очереди. Значение (ПЭ) кода величины приоритета может находиться в пределах 0 (ПЭ 4 2 — 1, код элемен1( та данных очереди для занесения его в очередь устанавливается на (m-k) младших разрядах входа 6 устройства.

На (m-k) младших разрядах входа 7 устройства устанавливается нулевой код, В качестве кода начальной установки в устройстве используется нулевой код. Значение (L) кода элемента данных может быть равным 0(L 2 — 1.

В результате в устройстве осуществляется сортировка чисел, устанавливаемых последовательно на входе 7 устройства с учетом только их к старших разрядов, так каккод k старших разрядов сортируемьгх чисел устанавливается также и на старших разрядах входа 7 устройства, на (m-k) младших разрядах которого устанавливается нулевой код.

Если коды приоритета элемента данных, код которого хранится в устройстве, и элемента данных, код которого устанавливается на входе 7 устройства, равны, то из таких элементов данных внутри приоритетной очереди элементов в устройстве организуется очередь FIFO, так как код элемента данных вместе с кодом прио1315967 12.»

2»

Дсв °

Зз ритета, хранимые в устройстве. образуют двоичное число, которое всегда больше или равно двоичному числу,устансвленноь у на входе 7, при условии. что íà k старших разрядах чисел (-т.е, коды приоритетов) равны. В ре:-ультате элементы данных в устройстве запоминаются в порядке, определлемом значением приоритета элемента на k стар1«1их разрядах устройства, Та« как сортировка двоичных чисел, образова1111ым кодом приоритета и кодом элемента дачных, в устройстве осуществляетсл только с учетом значений приоритета. При этом элемент данных с максимальным приоритетом запоминасг"л в ячейки первой строки, СчитыВя>ие элементов очереди осуществляв

P Tci; с Вы Она 3 стрсйства в порядке

- б дания приогитетов элементов.

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

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

-HaBI43a где А = 1 ° ° "1 1)/ k— количество разрядов в одной ячейке анализа, m — количестIIo разрядов сравниваемых числах, j = 1,...,N, где 11 — количество сортируемых чисел, выход первого элемента И узла формирования управляющих сигналов соединен с первым входом элемента

ИЛИ узла формирования управляющих сигналов, выход которогс является выходом первого результата сравнения 3-и ячейки анализа тя11тсвый

Вход устройства соединен с синхроВхОдОм каждОгс узля памяти ) Й лчейки анализа, информационный выход

1" k Й Ячейки ЯНЯлиза где k=1

N-1, соединен с первым информационлым входом узла памяти 1. (+1)-й ячейки анализа, информационные выходы ° N-й ячейки анализа лвля1отся

i-и группой разрлцов первого выходя отсортированного числа устройства., 1-я группа разрядов входа наращиваl0

20 ния количества сравниваемых ч сел устройства соединена с первым информационным входом узла памяти 1 1-й ячейки анализà, j-й вход первîro разряда управляющего кода устройства соецинен с управляющими входами элементов И узла. формирования управляющих c>II"Haëoâ 1 j é ячейки анализа, управляющие входы элементов И узла формирования управляющих сигналов

q j — и я- ейки ана.-п1за, где q=2.....1,. соединены с выходом второго результата сравнения (q-1) j-й ячейки анализа. выход второго результата сравнения 1 j-й ячейки анализа является

1-м выходом второго результата сравнения устройства, о т л и ч а ю— щ е е с я тем, «То, с целью расширения функциональных возможностей за счет обеспечения возможности задяпил диапазона сортируемых чисел и организации î 1ередей элементов данных в него введены цве группы эле.— ментов ИЛИ, В каждую « " j — 10 лчей11у анализа введена схема сравненил, узел памяти содержит 1с элементов па:1яти.„ причем в i j-й ячейке анализа первь1й и второй выходы схемы сравнения соединены с информационнымн входами первого и второго элементов

И узла формирования управляющих сигналов соответственно, выход второго элемента И узла формирования управляющих сигналов является Выходом второго результата сравнения i.j-й лчейки анализй. Выхоц узла памяти i j-й ячейки анализа является инфогмяционным выходом i-j-й ячейки анализа и соединен с первым информационным входом схемы срав11енпл. Второй информационный вход схемы сравнения > ° 1-и ячейки анализа является 1-й группой разрядов входа сравниваемых чисел устройства, второй вход элемента ИЛИ узла формирования управляющих сигналов 1 )-й ячейки анализа является

j-м входом второго разряда управляющего кода устройства, выхоц первого резс«л«ьтатя сряв:;ен11Я 1 1-1» 1»»1 йк11 анализа является -,-м выходом первого результата сравнения устройства. второй вход элемента ИЛИ узла формирования управляющих сигналов j é ячейки анализа подключен к в«ыходу первого результата сравнения (q-1).j-й ячейки анализа, второй информяц11О111 ь1Й

Вход $ зля пам11TH j и лчейк11 ян 3 л«и"-зЯ coPIII HFH с i . ГP>"ïïÎÉ РЯ зРЯДОВ информационного входя устройства, ВНИИПИ Заказ 2363/50 Тираж 672

Подписное

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4

13 131 третий информационный вход узла памяти р-й ячейки анализа, где 1< р4И-1, соединен с информационным выходом (р+ 1)-j-й ячейки анализа, первый вход

j-ro элемента ИЛИ первой группы соединен с j-м входом первой группы входов установки режима устройства, j-й выход первой группы установки режима записи устройства соединен с первым входом установки режима записи узла памяти i j-x ячеек анализа и с выходом j-ro элемента ИЛИ первой группы, второй и третий входы которого соединены с (j-1)-ми выходами первого и второго результатов сравнения устройства, j-й вход второй группы вхо. дов установки режима устройства соединен с первым входом j-го элемента

5967 14

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

i-ro элемента ИЛИ второй группы, выЮ ходы узла памяти 1-ячейки анализа являются -и группой разрядов второго выхода отсортированного чис ла устройства, дополнительные входы первого и второго результатов сравнения устройства соединены с вторым и третьим входами элемента ИЛИ первой группы.