устройство сортировки двоичных чисел

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

Устройство сортировки двоичных чисел, содержащее n-1 постоянных запоминающих устройств и n-1 регистров, причем k-й выход i-го постоянного запоминающего устройства соединен с k-м входом i-го регистра, подключенного входом сброса, входом записи и р-м

выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и р-му адресному входу i-го постоянного запоминающего устройства, (m+k+l)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+l)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход первого постоянного запоминающего устройства подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+l)-м адресным входом первого, первым - m-м выходами i-го и (m+2)-м - (2m+1)-м выходами (n-l)-гo постоянных запоминающих устройств, отличающееся тем, что в него дополнительно введены 2n-2 инверторов, вход и выход i-го инвертора соединены соответственно с (m+1)-м выходом i-го постоянного запоминающего устройства и объединенными (m+1)-м входом i-го регистра, i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход (n+l-1)-го инвертора подключены соответственно к (2m+2)-му выходу l-го и (2m+2)-му адресному входу (l+1)-го постоянных запоминающих устройств, а вход и выход (2n-2)-го инвертора соединены соответственно с (2m+2)-м выходом (n-1)-гo постоянного запоминающего устройства и n-м маркерным выходом устройства сортировки двоичных чисел.

Описание изобретения к патенту

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

Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку n m-разрядных двоичных чисел (см., например, патент РФ 2300136, кл. G06F 7/06, 2007 г.).

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сортировки двоичных чисел (патент РФ 2346321, кл. G06F 7/06, 2009 г.), которое содержит n-1 постоянных запоминающих устройств, n-1 регистров и выполняет сортировку n m-разрядных двоичных чисел, задаваемых двоичными сигналами, а также распознавание сортируемых чисел (многозначных переменных) по принципу «дубликат - не дубликат».

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, не позволяющие правильно распознать переменную x₁=0, поскольку она всегда маркируется как дубликат.

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения правильного распознавания переменной x₁=0 при распознавании сортируемых m-разрядных двоичных чисел x₁, , x_n, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем n-1 постоянных запоминающих устройств и n-1 регистров, k-й выход i-го постоянного запоминающего устройства соединен с k-м входом i-го регистра, подключенного входом сброса, входом записи и p-м выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и p-му адресному входу i-го постоянного запоминающего устройства, (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+1)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход первого постоянного запоминающего устройства подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+1)-м адресным входом первого, первым - m-м выходами i-го и (m+2)-м - (2m+1)-м выходами (n-1)-го постоянных запоминающих устройств, особенность заключается в том, что в него дополнительно введены 2n-2 инверторов, вход и выход i-го инвертора соединены соответственно с (m+1)-м выходом i-го постоянного запоминающего устройства и объединенными (m+1)-м входом i-го регистра, i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход (n+l-1)-гo инвертора подключены соответственно к (2m+2)-му выходу l-го и (2m+2)-му адресному входу (l+1)-го постоянных запоминающих устройств, а вход и выход (2n-2)-го инвертора соединены соответственно с (2m+2)-м выходом (n-1)-го постоянного запоминающего устройства и n-м маркерным выходом устройства сортировки двоичных чисел.

На фиг.1 и фиг.2 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие его работу.

Устройство сортировки двоичных чисел содержит постоянные запоминающие устройства 1 ₁, , 1_n-1, регистры 2₁, , 2_n-1 и инверторы 3₁, , 3_2n-2, причем k-й выход устройства 1_i соединен с k-м входом регистра 2_i, подключенного входом сброса, входом записи и p-м выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и p-му адресному входу устройства 1_i, (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+1)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход устройства 1₁ подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+1)-м адресным входом устройства 1₁ , первым - m-м выходами устройства 1_i и (m+2)-м - (2m+1)-м выходами устройства l_n-1, вход и выход инвертора 3_i соединены соответственно с (m+1)-м выходом устройства 1_i и объединенными (m+1)-м входом регистра 2_i , i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход инвертора подключены соответственно к (2m+2)-му выходу устройства 1_l и (2m+2)-му адресному входу устройства 1_l+1 , а вход и выход инвертора 3_2n-2 соединены соответственно с (2m+2)-м выходом устройства l_n-1 и n-м маркерным выходом устройства сортировки двоичных чисел.

Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y₁, y₂ {0,1} (фиг.2), причем период Т сигнала y₂ должен удовлетворять условию T> t, где t= ₂+(n-1) ₁, a ₁ и ₂ есть длительности задержек, вносимых соответственно устройством 1_i и регистром 2_i (i {1, ,n-1}). Синхронно с передним фронтом импульса сигнала y ₁ и передними фронтами первого, , (n-1)-го импульсов сигнала y₂ на m информационных входов предлагаемого устройства последовательно подаются соответственно первый и второй, , n-й наборы m произвольных двоичных сигналов, задающие m-разрядные двоичные числа х₁ и х₂, , x_n соответственно (фиг.2). Синхронно с передним фронтом импульса сигнала y₁ и передними фронтами первого, , (n-1)-го импульсов сигнала y₂ на маркерный вход предлагаемого устройства последовательно подаются соответственно первый и второй, , n-й двоичные сигналы, задающие нулевые маркерные биты. Обнуление выходных сигналов регистра 2_i и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала y₁) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y₂). В устройстве 1_i q-я ячейка с адресом содержит (2m+2)-разрядный двоичный код в котором , при и или a_m=0 и , d_m=1 при и или a_m=0 и , в остальных случаях и d_m=0. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, , m-м и (m+2)-м, , (2m+1)-м выходах устройства 1_i , маркерные биты на выходах инверторов 3_i и 3_n+i-1 будут определяться соответственно рекуррентными выражениями

где

Здесь символами , · и &, * обозначены операции max, min и И, ИЛИ; есть номер момента времени t_j (фиг.2); V _i0=0; W_0j=х_j 0; v_i0=w_0j=0. В представленной ниже таблице 1 приведены значения выражений (1) при n=4.

Таблица 1
V11=x1	V12=x1 x2	V13=x1 x2 x3	V14=x1 x2 x3 x4
W11=0	W 12=x1x2	W13=x1x3 x2x3	W14=x1x4 x2x4 x3x4
V21=0	V 22=x1x2	V23=x1x2 x1x3 x2x3	V24=x1x2 x1x3 x1x4 x2x3 x2x4 x3x4
W21=0	W 22=0	W23 =x1x2x3	W24=x1x2x4 x1x3x4 x2x3x4
V31=0	V 32=0	V33 =x1x2x3	V34=x1x2x3 x1x2x4 x1x3x4 x2x3x4
W31=0	W 32=0	W33 =0	W34=x 1x2x3x4

В таблице 2 приведены значения выражений (1) и (2), когда x₁=c=0, x₂=b, х₃=а, x₄=b и a>b>c.

Таблица 2
j	W0j	V1j	v1j	W1j	w 1j	V2j	v2j	W2j	w2j	V 3j	v3j	W3j	w3j
1	с	с	0	0	1	0	0	0	1	0	0	0	1
2	b	b	0	с	0	с	0	0	1	0	0	0	1
3	а	а	0	b	0	b	0	с	0	с	0	0	1
4	b	а	0	b	0	b	0	b	1	b	1	с	0

С учетом данных, приведенных в таблице 1, нетрудно вывести непосредственное выражение, определяющее m-разрядное двоичное число, задаваемое двоичными сигналами на g-й группе m выходов предлагаемого устройства при j=n:

где х_s1 х_sg {х₁, , х_n}; есть количество неповторяющихся фрагментов x_s1 x_sg, определяемое как число сочетаний из n по g. При g=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {х₁, , х_n} элемента х^(r) заданного ранга r {1, , x_n} (x⁽¹⁾ x⁽ⁿ⁾; {x⁽¹⁾} {x⁽ⁿ⁾}={x₁, , x_n}). Таким образом, имеем V_1n=x ⁽ⁿ⁾, , V(_n-1)n=x⁽²⁾, W_(n-1)n =x⁽¹⁾ то есть предлагаемое устройство выполняет сортировку m-разрядных двоичных чисел х₁, , х_n. При этом согласно таблице 2 предлагаемое устройство распознает сортируемые числа по принципу «дубликат - не дубликат» (дубликат маркируется единичным маркерным битом).

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает правильное распознавание переменной х₁=0 при распознавании сортируемых m-разрядных двоичных чисел x₁, , x_n, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».