2445678 - Устройство сортировки двоичных чисел

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

Иллюстрации

Показать все

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом является расширение функциональных возможностей за счет правильного распознавания переменной x₁=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-разрядных двоичных чисел, задаваемых двоичными сигналами, а также распознавание сортируемых чисел (многозначных переменных) по принципу «дубликат - не дубликат».

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, не позволяющие правильно распознать переменную 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
V₁₁=x₁	V₁₂=x₁∨x₂	V₁₃=x₁∨x₂∨x₃	V₁₄=x₁∨x₂∨x₃∨x₄
W₁₁=0	W₁₂=x₁x₂	W₁₃=x₁x₃∨x₂x₃	W₁₄=x₁x₄∨x₂x₄∨x₃x₄
V₂₁=0	V₂₂=x₁x₂	V₂₃=x₁x₂∨x₁x₃∨x₂x₃	V₂₄=x₁x₂∨x₁x₃∨x₁x₄∨x₂x₃∨x₂x₄∨x₃x₄
W₂₁=0	W₂₂=0	W₂₃=x₁x₂x₃	W₂₄=x₁x₂x₄∨x₁x₃x₄∨x₂x₃x₄
V₃₁=0	V₃₂=0	V₃₃=x₁x₂x₃	V₃₄=x₁x₂x₃∨x₁x₂x₄∨x₁x₃x₄∨x₂x₃x₄
W₃₁=0	W₃₂=0	W₃₃=0	W₃₄=x₁x₂x₃x₄

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

Таблица 2
j	W_0j	V_1j	v_1j	W_1j	w_1j	V_2j	v_2j	W_2j	w_2j	V_3j	v_3j	W_3j	w_3j
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, задаваемых двоичными сигналами, по принципу «дубликат - не дубликат».

Устройство сортировки двоичных чисел, содержащее 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-м маркерным выходом устройства сортировки двоичных чисел.

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

Патент 2445678