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

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства сортировки двоичных чисел (см., например, фиг.1 в описании изобретения к патенту РФ 2300136, кл. G06F 7/06, 2007 г.), преобразующие несортированный последовательный набор задаваемых двоичными сигналами n m-разрядных двоичных чисел в сортированный параллельный набор этих чисел.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сортировки двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется преобразование несортированного параллельного набора задаваемых двоичными сигналами n m-разрядных двоичных чисел в их сортированный последовательный набор.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство сортировки двоичных чисел (фиг.1 в описании изобретения к патенту РФ 2264645, кл. G06F 7/06, 2005 г.), которое содержит n-1 логических модулей и преобразует несортированный параллельный набор задаваемых двоичными сигналами n m-разрядных двоичных чисел в сортированный последовательный набор этих чисел.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется преобразование несортированного последовательного набора задаваемых двоичными сигналами n m-разрядных двоичных чисел в их сортированный параллельный набор.
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения преобразования несортированного последовательного набора задаваемых двоичными сигналами n m-разрядных двоичных чисел в их сортированный параллельный набор либо преобразования несортированного параллельного набора указанных чисел в их сортированный последовательный набор.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройство сортировки двоичных чисел, содержащее n-1 логических модулей, каждый из которых содержит m замыкающих, m размыкающих ключей, постоянное запоминающее устройство и регистр, в g-ом  логическом модуле первый управляющий и k-й  входы образованы соответственно входом управления всех имеющихся в нем ключей и входом k-го замыкающего ключа, выход которого соединен с выходом k-го размыкающего ключа и k-ым адресным входом постоянного запоминающего устройства, подсоединенного k-ым выходом к k-му входу регистра, k-й выход и вход записи которого соединены соответственно с входом k-го размыкающего ключа и вторым управляющим входом g-го логического модуля, подсоединенного k-ым выходом к (m+k)-му выходу своего постоянного запоминающего устройства, в каждом логическом модуле, кроме первого, (m+k)-й вход образован (m+k)-ым адресным входом постоянного запоминающего устройства, k-й выход каждого предыдущего логического модуля подключен к (m+k)-му входу последующего логического модуля, а первый и второй управляющие входы g-го логического модуля соединены соответственно с первым и вторым настроечными входами устройства сортировки двоичных чисел, дополнительно введен аналогичный (n-1)-му n-й логический модуль, подключенный первым, вторым управляющими и (m+k)-ым входами соответственно к первому, второму управляющим входам и k-му выходу (n-1)-го логического модуля, в первом логическом модуле (m+k)-й вход образован (m+k)-ым адресным входом постоянного запоминающего устройства, а в i-ом  логическом модуле (m+k)-й выход образован k-ым выходом постоянного запоминающего устройства.
На фиг.1 и фиг.2 представлены соответственно схема предлагаемого устройства сортировки двоичных чисел и временные диаграммы, поясняющие принцип его работы.
1
n
i
1
m
1
m
k
k
k
Устройство сортировки двоичных чисел содержит логические модули 1,…,1. Модуль 1 (i∈{1,…,n}) содержит размыкающие и замыкающие ключи 2,…,2 и 3,…,3, постоянное запоминающее устройство 4, регистр 5, причем выход ключа  соединен с выходом ключа 3 и k-ым адресным входом устройства 4, k-й выход которого соединен с k-ым входом регистра 5, подсоединенного k-ым выходом и входом записи соответственно к входу ключа 2 и второму управляющему входу модуля 1, первый управляющий, k-й, (m+k)-й входы и k-й, (m+k)-й выходы которого образованы соответственно входом управления всех имеющихся в нем ключей, входом ключа 3, (m+k)-ым адресным входом и (m+k)-ым, k-ым выходами устройства 4, k-й выход каждого предыдущего логического модуля соединен с (m+k)-ым входом последующего логического модуля, а объединенные первые и объединенные вторые управляющие входы всех логических модулей подключены соответственно к первому и второму настроечным входам устройства сортировки двоичных чисел.
1
2
1
2
1
1
2
1
2
1
2
1
1
1
n
10
1
n0
n
1
1
1
1
m
1
m
2
m-1
0
m-1
0
m-1
0
m-1
0
m-1
0
m-1
0
m-1
0
m-1
0
Работа предлагаемого устройства сортировки двоичных чисел осуществляется следующим образом. На его первый, второй настроечные входы подаются соответственно импульсные сигналы y,у∈{0,1} (фиг.2), причем длительность Т* высокого уровня сигнала y и период Т сигнала y должны удовлетворять условиям Т*>Δt* и Т>Δt, где Δt*=nτ, Δt=nτ+τ, а τ и τ есть длительности задержек, вносимых соответственно устройством 4 и регистром 5. Подлежащие сортировке m-разрядные двоичные числа x,…,x, задаваемые двоичными сигналами, либо последовательно подаются согласно фиг.2 на модуль 1 (при этом на  входе всех модулей фиксируется логическая «1») либо параллельно подаются в течение времени действия высокого уровня сигнала у соответственно на модули 1,…,1: V=x,…,V=x (при этом на (m+k)-ом входе модуля 1 фиксируется логический «0»). Если у=1 (y=0), то ключи 3,…,3замкнуты (разомкнуты), ключи 2,…,2 разомкнуты (замкнуты). Загрузка данных в регистр 5 происходит по положительному перепаду (из «0» в «1») сигнала на входе записи (сигнала y). В устройстве 4 q-я  ячейка с адресом  содержит 2 m-разрядный двоичный код d*…d* d…d, в котором d*…d*=max(a*…a*, a…a), d…d=min(a*…a*, a…a). Тогда m-разрядные двоичные числа, задаваемые двоичными сигналами на (m+1)-ом - (m+m)-ом и первом - m-ом выходах модуля  будут определяться рекуррентными выражениями
j
i0
i
0j
min
i
i0
max
0j
j
max
i0
i
0j
min
i
0j
max
0j
j
max
nj
in
где символами ∨ и · обозначены операции max и min;  есть номер момента времени t (фиг.2); V=x, W=x≤x либо V=x, W=x≤x. В представленных ниже табл.1 и табл.2 приведены значения выражений (1) при n=4, если соответственно V=x, W=x≤x и V=x, W=x≤x. С учетом данных, приведенных в табл.1 и табл.2, нетрудно вывести непосредственные выражения для соответственно W и V
s1
sn
1
n
s1
sj
si
sn
1
n
(r)
(1)
(n)
где x≠…≠x∈{x,…x};  есть количество неповторяющихся фрагментов x…x (x…x), определяемое как число сочетаний из n по j (по n+1-i). При j=n+1-r выражение (2) и при i=r выражение (3) совпадают с видом поисковой функции (функция (6.7) на стр.117 в книге Левин В.И. Бесконечнозначная логика в задачах кибернетики. М.: Радио и связь, 1982 г.), которая реализует алгоритм выбора из множества {x,…,x} элемента x заданного ранга r∈{1,…,n} (x≤…≤x;
i0
i
0j
min
i
i0
max
0j
j
max
1
n
n
n1
nn
1n
nn
1
n
(n)
(1)
(1)
(n)
Таким образом, при V=x, W=x≤x (при V=x, W=x≤ x) в моменты времени t,…,t (в момент времени t) имеем W=x,…,W=x (V=x,…,V=x), то есть предлагаемое устройство формирует сортированный последовательный (параллельный) набор m-разрядных двоичных чисел x,…,x.
Таблица 1
V<sub>11</sub>=x<sub>min</sub>
V<sub>21</sub>=x<sub>1</sub>x<sub>2</sub>
V<sub>31</sub>=x<sub>1</sub>x<sub>3</sub>∨x<sub>2</sub>x<sub>3</sub>
V<sub>41</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>
W<sub>11</sub>=x<sub>1</sub>
W<sub>21</sub>=x<sub>1</sub>∨x<sub>2</sub>
W<sub>31</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>
W<sub>41</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>∨x<sub>4</sub>
V<sub>12</sub>=x<sub>min</sub>
V<sub>22</sub>=x<sub>min</sub>
V<sub>32</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>
V<sub>42</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>12</sub>=x<sub>min</sub>
W<sub>22</sub>=x<sub>1</sub>x<sub>2</sub>
W<sub>32</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>
W<sub>42</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>
V<sub>13</sub>=x<sub>min</sub>
V<sub>23</sub>=x<sub>min</sub>
V<sub>33</sub>=x<sub>min</sub>
V<sub>43</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>
W<sub>13</sub>=x<sub>min</sub>
W<sub>23</sub>=x<sub>min</sub>
W<sub>33</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>
W<sub>43</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>
V<sub>14</sub>=x<sub>min</sub>
V<sub>24</sub>=x<sub>min</sub>
V<sub>34</sub>=x<sub>min</sub>
V<sub>44</sub>=x<sub>min</sub>
W<sub>14</sub>=x<sub>min</sub>
W<sub>24</sub>=x<sub>min</sub>
W<sub>34</sub>=x<sub>min</sub>
W<sub>44</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>
Таблица 2
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>=x<sub>max</sub>
W<sub>12</sub>=x<sub>1</sub>∨x<sub>2</sub>
W<sub>13</sub>=x<sub>1</sub>x<sub>2</sub>∨x<sub>3</sub>
W<sub>14</sub>=x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>∨x<sub>4</sub>
V<sub>21</sub>=x<sub>max</sub>
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>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>21</sub>=x<sub>max</sub>
W<sub>22</sub>=x<sub>max</sub>
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>1</sub>x<sub>3</sub>∨x<sub>2</sub>x<sub>3</sub>∨x<sub>4</sub>
V<sub>31</sub>=x<sub>max</sub>
V<sub>32</sub>=x<sub>max</sub>
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>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>31</sub>=x<sub>max</sub>
W<sub>32</sub>=x<sub>max</sub>
W<sub>33</sub>=x<sub>max</sub>
W<sub>34</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>∨x<sub>4</sub>
V<sub>41</sub>=x<sub>max</sub>
V<sub>42</sub>=x<sub>max</sub>
V<sub>43</sub>=x<sub>max</sub>
V<sub>44</sub>=x<sub>1</sub>∨x<sub>2</sub>∨x<sub>3</sub>∨x<sub>4</sub>
W<sub>41</sub>=x<sub>max</sub>
W<sub>42</sub>=x<sub>max</sub>
W<sub>43</sub>=x<sub>max</sub>
W<sub>44</sub>=x<sub>max</sub>
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает преобразование несортированного последовательного набора задаваемых двоичными сигналами n m-разрядных двоичных чисел в их сортированный параллельный набор либо преобразование несортированного параллельного набора указанных чисел в их сортированный последовательный набор.