Устройство сортировки двоичных чисел
Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом является расширение функциональных возможностей за счет правильного распознавания переменной x1=0. Устройство содержит n-1 постоянных запоминающих устройств, n-1 регистров и 2n-2 инверторов и выполнено с возможностью сортировки n m-разрядных двоичных чисел, задаваемых двоичными сигналами, а также с возможностью распознавания сортируемых чисел по принципу «дубликат - не дубликат». 2 табл., 2 ил.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства сортировки двоичных чисел, задаваемых двоичными сигналами, выполняющие сортировку n m-разрядных двоичных чисел (см., например, патент РФ 2300136, кл. G06F 7/06, 2007 г.).
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сортировки двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется распознавание сортируемых чисел по принципу «дубликат - не дубликат».
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сортировки двоичных чисел (патент РФ 2346321, кл. G06F 7/06, 2009 г.), которое содержит n-1 постоянных запоминающих устройств, n-1 регистров и выполняет сортировку n m-разрядных двоичных чисел, задаваемых двоичными сигналами, а также распознавание сортируемых чисел (многозначных переменных) по принципу «дубликат - не дубликат».
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, не позволяющие правильно распознать переменную x1=0, поскольку она всегда маркируется как дубликат.
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения правильного распознавания переменной x1=0 при распознавании сортируемых m-разрядных двоичных чисел x1, …, xn, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сортировки двоичных чисел, содержащем 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 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие его работу.
Устройство сортировки двоичных чисел содержит постоянные запоминающие устройства 11, …, 1n-1, регистры 21, …, 2n-1 и инверторы 31, …, 32n-2, причем k-й 
выход устройства 1i 
соединен с k-м входом регистра 2i, подключенного входом сброса, входом записи и p-м 
выходом соответственно к первому, второму настроечным входам устройства сортировки двоичных чисел и p-му адресному входу устройства 1i, (m+k+1)-й выход каждого предыдущего постоянного запоминающего устройства соединен с (m+k+1)-м адресным входом последующего постоянного запоминающего устройства, а (2m+2)-й адресный вход устройства 11 подключен к маркерному входу устройства сортировки двоичных чисел, k-й информационный вход, i-я и n-я группы первого - m-го выходов которого соединены соответственно с (m+k+1)-м адресным входом устройства 11, первым - m-м выходами устройства 1i и (m+2)-м - (2m+1)-м выходами устройства ln-1, вход и выход инвертора 3i соединены соответственно с (m+1)-м выходом устройства 1i и объединенными (m+1)-м входом регистра 2i, i-м маркерным выходом устройства сортировки двоичных чисел, вход и выход инвертора 
подключены соответственно к (2m+2)-му выходу устройства 1l и (2m+2)-му адресному входу устройства 1l+1, а вход и выход инвертора 32n-2 соединены соответственно с (2m+2)-м выходом устройства ln-1 и n-м маркерным выходом устройства сортировки двоичных чисел.
Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y1, y2∈{0,1} (фиг.2), причем период Т сигнала y2 должен удовлетворять условию T>Δt, где Δt=τ2+(n-1)τ1, a τ1 и τ2 есть длительности задержек, вносимых соответственно устройством 1i и регистром 2i (i∈{1, …,n-1}). Синхронно с передним фронтом импульса сигнала y1 и передними фронтами первого, …, (n-1)-го импульсов сигнала y2 на m информационных входов предлагаемого устройства последовательно подаются соответственно первый и второй, …, n-й наборы m произвольных двоичных сигналов, задающие m-разрядные двоичные числа х1 и х2, …, xn соответственно (фиг.2). Синхронно с передним фронтом импульса сигнала y1 и передними фронтами первого, …, (n-1)-го импульсов сигнала y2 на маркерный вход предлагаемого устройства последовательно подаются соответственно первый и второй, …, n-й двоичные сигналы, задающие нулевые маркерные биты. Обнуление выходных сигналов регистра 2i и загрузка в него данных происходят соответственно по высокому уровню сигнала на входе сброса (сигнала y1) и по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y2). В устройстве 1i q-я 
ячейка с адресом 
содержит (2m+2)-разрядный двоичный код 
в котором 
, 
при 
и 
или am=0 и 
, dm=1 при 
и или am=0 и 
, в остальных случаях 
и dm=0. Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на первом, …, m-м и (m+2)-м, …, (2m+1)-м выходах устройства 1i 
, маркерные биты на выходах инверторов 3i и 3n+i-1 будут определяться соответственно рекуррентными выражениями
где
Здесь символами ∨, · и &, * обозначены операции max, min и И, ИЛИ; 
есть номер момента времени tj (фиг.2); Vi0=0; W0j=хj≥0; vi0=w0j=0. В представленной ниже таблице 1 приведены значения выражений (1) при n=4.
| Таблица 1 | |||
| V11=x1 | V12=x1∨x2 | V13=x1∨x2∨x3 | V14=x1∨x2∨x3∨x4 |
| W11=0 | W12=x1x2 | W13=x1x3∨x2x3 | W14=x1x4∨x2x4∨x3x4 |
| V21=0 | V22=x1x2 | V23=x1x2∨x1x3∨x2x3 | V24=x1x2∨x1x3∨x1x4∨x2x3∨x2x4∨x3x4 |
| W21=0 | W22=0 | W23=x1x2x3 | W24=x1x2x4∨x1x3x4∨x2x3x4 |
| V31=0 | V32=0 | V33=x1x2x3 | V34=x1x2x3∨x1x2x4∨x1x3x4∨x2x3x4 |
| W31=0 | W32=0 | W33=0 | W34=x1x2x3x4 |
В таблице 2 приведены значения выражений (1) и (2), когда x1=c=0, x2=b, х3=а, x4=b и a>b>c.
| Таблица 2 | |||||||||||||
| j | W0j | V1j | v1j | W1j | w1j | V2j | v2j | W2j | w2j | V3j | 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∈{х1, …, хn}; 
есть количество неповторяющихся фрагментов xs1…xsg, определяемое как число сочетаний из n по g. При g=n+1-r выражение (3) совпадает с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {х1, …, хn} элемента х(r) заданного ранга r∈{1, …, xn} (x(1)≤…≤x(n); {x(1)}∪…∪{x(n)}={x1, …, xn}). Таким образом, имеем V1n=x(n), …, V(n-1)n=x(2), W(n-1)n=x(1) то есть предлагаемое устройство выполняет сортировку m-разрядных двоичных чисел х1, …, хn. При этом согласно таблице 2 предлагаемое устройство распознает сортируемые числа по принципу «дубликат - не дубликат» (дубликат маркируется единичным маркерным битом).
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сортировки двоичных чисел обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает правильное распознавание переменной х1=0 при распознавании сортируемых m-разрядных двоичных чисел x1, …, xn, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».
Устройство сортировки двоичных чисел, содержащее 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-м маркерным выходом устройства сортировки двоичных чисел.
