УСТРОЙСТВО СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ
DEVICE TO SORT BINARY NUMBERS

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку n m-разрядных двоичных чисел (см., например, патент РФ 2300136, кл. G06F 7/06, 2007 г.).
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сортировки двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется распознавание сортируемых чисел по принципу «дубликат - не дубликат».
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сортировки двоичных чисел (патент РФ 2346321, кл. G06F 7/06, 2009 г.), которое содержит n-1 постоянных запоминающих устройств, n-1 регистров и выполняет сортировку n m-разрядных двоичных чисел, задаваемых двоичными сигналами, а также распознавание сортируемых чисел (многозначных переменных) по принципу «дубликат - не дубликат».
1
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, не позволяющие правильно распознать переменную x=0, поскольку она всегда маркируется как дубликат.
1
1
n
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения правильного распознавания переменной x=0 при распознавании сортируемых m-разрядных двоичных чисел x, …, x, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем 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
n-1
1
n-1
1
2n-2
i
i
i
1
1
i
n-1
i
i
i
l
l+1
2n-2
n-1
Устройство сортировки двоичных чисел содержит постоянные запоминающие устройства 1, …, 1, регистры 2, …, 2 и инверторы 3, …, 3, причем k-й  выход устройства 1 соединен с k-м входом регистра 2, подключенного входом сброса, входом записи и p-м  выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и p-му адресному входу устройства 1, (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+1)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход устройства 1 подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+1)-м адресным входом устройства 1, первым - m-м выходами устройства 1 и (m+2)-м - (2m+1)-м выходами устройства l, вход и выход инвертора 3 соединены соответственно с (m+1)-м выходом устройства 1 и объединенными (m+1)-м входом регистра 2, i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход инвертора  подключены соответственно к (2m+2)-му выходу устройства 1 и (2m+2)-му адресному входу устройства 1, а вход и выход инвертора 3 соединены соответственно с (2m+2)-м выходом устройства l и n-м маркерным выходом устройства сортировки двоичных чисел.
1
2
2
2
1
1
2
i
i
1
2
1
2
n
1
2
i
1
2
i
m
m
m
m
i
i
n+i-1
Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y, y∈{0,1} (фиг.2), причем период Т сигнала y должен удовлетворять условию T>Δt, где Δt=τ+(n-1)τ, a τ и τ есть длительности задержек, вносимых соответственно устройством 1 и регистром 2 (i∈{1, …,n-1}). Синхронно с передним фронтом импульса сигнала y и передними фронтами первого, …, (n-1)-го импульсов сигнала y на m информационных входов предлагаемого устройства последовательно подаются соответственно первый и второй, …, n-й наборы m произвольных двоичных сигналов, задающие m-разрядные двоичные числа х и х, …, x соответственно (фиг.2). Синхронно с передним фронтом импульса сигнала y и передними фронтами первого, …, (n-1)-го импульсов сигнала y на маркерный вход предлагаемого устройства последовательно подаются соответственно первый и второй, …, n-й двоичные сигналы, задающие нулевые маркерные биты. Обнуление выходных сигналов регистра 2 и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала y) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y). В устройстве 1 q-я  ячейка с адресом  содержит (2m+2)-разрядный двоичный код  в котором ,  при  и  или a=0 и , d=1 при  и  или a=0 и , в остальных случаях  и d=0. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, …, m-м и (m+2)-м, …, (2m+1)-м выходах устройства 1, маркерные биты на выходах инверторов 3 и 3 будут определяться соответственно рекуррентными выражениями
где
j
i0
0j
j
i0
0j
Здесь символами ∨, · и &, * обозначены операции max, min и И, ИЛИ;  есть номер момента времени t (фиг.2); V=0; W=х≥0; v=w=0. В представленной ниже таблице 1 приведены значения выражений (1) при n=4.
Таблица 1
V<sub>11</sub>=x<sub>1</sub>
V<sub>12</sub>=x<sub>1</sub>∨x<sub>2</sub>
V<sub>13</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>
V<sub>14</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>∨x<sub>4</sub>
W<sub>11</sub>=0
W<sub>12</sub>=x<sub>1</sub>x<sub>2</sub>
W<sub>13</sub>=x<sub>1</sub>x<sub>3</sub>∨x<sub>2</sub>x<sub>3</sub>
W<sub>14</sub>=x<sub>1</sub>x<sub>4</sub>∨x<sub>2</sub>x<sub>4</sub>∨x<sub>3</sub>x<sub>4</sub>
V<sub>21</sub>=0
V<sub>22</sub>=x<sub>1</sub>x<sub>2</sub>
V<sub>23</sub>=x<sub>1</sub>x<sub>2</sub>∨x<sub>1</sub>x<sub>3</sub>∨x<sub>2</sub>x<sub>3</sub>
V<sub>24</sub>=x<sub>1</sub>x<sub>2</sub>∨x<sub>1</sub>x<sub>3</sub>∨x<sub>1</sub>x<sub>4</sub>∨x<sub>2</sub>x<sub>3</sub>∨x<sub>2</sub>x<sub>4</sub>∨x<sub>3</sub>x<sub>4</sub>
W<sub>21</sub>=0
W<sub>22</sub>=0
W<sub>23</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>
W<sub>24</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>4</sub>∨x<sub>1</sub>x<sub>3</sub>x<sub>4</sub>∨x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>
V<sub>31</sub>=0
V<sub>32</sub>=0
V<sub>33</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>
V<sub>34</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>∨x<sub>1</sub>x<sub>2</sub>x<sub>4</sub>∨x<sub>1</sub>x<sub>3</sub>x<sub>4</sub>∨x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>
W<sub>31</sub>=0
W<sub>32</sub>=0
W<sub>33</sub>=0
W<sub>34</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>
1
2
3
4
В таблице 2 приведены значения выражений (1) и (2), когда x=c=0, x=b, х=а, x=b и a>b>c.
Таблица 2
j
W<sub>0j</sub>
V<sub>1j</sub>
v<sub>1j</sub>
W<sub>1j</sub>
w<sub>1j</sub>
V<sub>2j</sub>
v<sub>2j</sub>
W<sub>2j</sub>
w<sub>2j</sub>
V<sub>3j</sub>
v<sub>3j</sub>
W<sub>3j</sub>
w<sub>3j</sub>
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
1
n
s1
sg
1
n
n
1
n
1n
n-1)n
(n-1)n
1
n
(r)
(1)
(n)
(1)
(n)
(n)
(2)
(1)
где х≠…≠х∈{х, …, х};  есть количество неповторяющихся фрагментов x…x, определяемое как число сочетаний из n по g. При g=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {х, …, х} элемента х заданного ранга r∈{1, …, x} (x≤…≤x; {x}∪…∪{x}={x, …, x}). Таким образом, имеем V=x, …, V(=x, W=x то есть предлагаемое устройство выполняет сортировку m-разрядных двоичных чисел х, …, х. При этом согласно таблице 2 предлагаемое устройство распознает сортируемые числа по принципу «дубликат - не дубликат» (дубликат маркируется единичным маркерным битом).
1
1
n
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает правильное распознавание переменной х=0 при распознавании сортируемых m-разрядных двоичных чисел x, …, x, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».