Устройство для сортировки чисел Советский патент 1991 года по МПК G06F7/08 

о

4ь 4

Ю

00

3-

Изобретение относится к области автоматики и вычислительной техники

Цель изобретения - расширение функциональных возможностей за счет обеспечения сортировки чисел в сколзящей выборке.

На фиг. 1 приведена схема устройства; на фиг. 2 - схема ячейки анализа.

Устройство содержит регистр 1, первую и вторую матрицы ячеек анализа, которые содержат k групп ячеек

,(™+пИнализа (k 2П - апертура выборки, га - количество разрядов анализируемых чисел), генератор 3 импульсов, триггер 4, счетчик 5, коммутаторы 6,-6(/, элементы ИЛИ 7,- 7К, входы 8, выходы 9 -9 разрядов чисел отсортированной выборки. Ячейка 2 анализа содержит триггер 10, элементы И , элементы ИЛИ , коммутаторы 13 и 13, информационные входы 14 и 142, управляющие входы 15 и 152, тактовые входы 16 4 и 16j, вход 17 переноса, вход 18 управления режимом, информационные выходы , выход 20 переноса.

i

Устройство работает следующим образом.

При работе устройства в ячейках 2 (, -2 xtin находятся k га-разрядных чисел, отсортированных в порядке убывания (в ячейке 2 (i( - старший разряд самого большого числа), а в

ячейках 24((W44j- 2k(mtn,- величина , где N - номер числа в порядке поступления.

Очередное анализирующее число поступает на входы 8 и сигналами с выхода а генератора 3 импульсов записывается в регистр 1.Одновременно число, хранящееся в счетчике 5, увеличива40

дое в последующую (у+1)-ю строку (т.е. в ячейки 2,),, -2(р+0,(т + п) а затем по сигналу с выхода в генера тора 3 импульсов в ячейку строки Об записывается текущее число с его номером.

Таким образом, на выходе 9 устрой ства на каждом i-м такте работы устется на единицу, а триггер 4 устанав- j ройства формируется выборка чисел ливается в единичное состояние. Да-i -k+( Aj.kfi J отсоР1 11 0

ванная в порядке убывания. Формула изобретения

лее происходит поиск числа, записанного в триггер ячеек z,

-2

k.m

анализа k тактов назад (т.е. самого старого из хранящихся в устройстве). Это число имеет тот же самый номер (так как емкость счетчика 5 равна k) что и только что поступившее число, и этот номер хранится в триггерах ячеек 21|(т+,,-2ц(т+п) . Поиск номера числа, равного текущему номеру, хранящемуся в счетчике 5, выполняется в ячейках 21|(m,-2k|( с помощью элементов И 1Ц, 11у и элемента

5

0

5

0

0

ИЛИ 124. На выходе 20 переноса ячей- ки 2й,(п+гм (оЈ «оме строки, содержащей искомое число) формируется логическая единица, которая по цепочке из элементов ИЛИ распространяется на управляющие входы 15 соответствующих ячеек 2|{,tm.nj . Кроме того, сформированная на выходе 20 переноса ячейки 2(-4.,,) логическая единица через коммутатор 62 поступает на управляющие входы 15 ячеек 2( - 2 (m4.n) выбранной строки Сб . В результате число, записанное в ячейках 2 -2 (п1н.п1 , теряется; числа с их номерами, записанные в ячейках 2,, (m+n1 ф-(оЈ-И), (tf+2),..., k), переписываются каждое в предыдущую (|5-1) строку (т.е. в ячейке 2 (р.о,, ,( ), а в ячейке 2 , -2 k-й строки записываются нули.

На втором полутакте сигналом с выхода б генератора 3 импульсов триггер 4 устанавливается в нулевое состояние. Происходит поиск чисел, меньших, чем текущее, находящееся в регистре 1. На выходах переноса ячеек 2|.irri строк, содержащих такие числа, формируется логическая единица, которая через коммутаторы поступает на входы 15 всех ячеек

2й.1 2 k (mnl анализа« В результате числа с их номерами, записанные в

ячейках 2у, -2yilnHn, (f-tf, (tf+1), i (),... (k-1)) переписываются каждое в последующую (у+1)-ю строку (т.е. в ячейки 2,),, -2(р+0,(т + п) ), а затем по сигналу с выхода в генератора 3 импульсов в ячейку строки Об записывается текущее число с его номером.

Таким образом, на выходе 9 устройства на каждом i-м такте работы устройства формируется выборка чисел ( Aj.kfi J отсоР1 11 0

ванная в порядке убывания. Формула изобретения

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

третий и четвертый элементы И и первый элемент ИЛИ, а каждая ячейка анализа первой матрицы содержит, кроме того, пятый и шестой элементы И и второй элемент ИЛИ, причем вход 1-го разряда сортируемого числа устройства, где ,2,.,., m, соединен с информационным входом 1-го разряда регистра, выхрд которого соединен с первым информационным входом 1-й ячейки анализа первой группы первой матрицы, первые информационные выходы i-й и J.-U ячеек анализа 1-й группы соответственно первой и второй матриц, где ,2,...,n, ,2,..., (k-1), соединены с первыми информационными входами соответственно 1-й и j-й ячеек анализа (1+1)-й группы той же матрицы, в каждой группе ячеек анализа выход переноса р-й и q-й ячеек анализа соответственно первой л второй матриц, где ,2,..., (m-1), ,2,..., (n-1) соединен с входом переноса соответственно (р+ И )-й и (q+O-й ячейки анализа той же группы той же матрицы, в каждой ячейке анализа первый тактовый вход соединен с первыми входами первого и второго элементов И, первый информационный вход соединен с вторым входом второго и первым входом третьего элементов И, выход третьего элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый и второй входы которого подключены соответственно к прямому выходу триггера и к входу переноса этой ячейки анализа, кроме того, в каждой ячейке анализа первой матрицы ее второй информационный вход соединен с первым входом пятого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, отличающееся тем, что, с целью расширения функциональных возможностей путем обеспечения сортировки чисел в скользящей выборке, в него введены счетчик, триггер, генератор импульсов, К коммутаторов, К элементов ИЛИ, в каждую ячейку анализа второй матрицы введены пятый и шестой элементы И и второй элемент ИЛИ, в каждую ячейку анализа обеих матриц введены седьмой элемент И, третий элемент ИЛИ и два коммутатора, причем выход j-ro разряда счетчика соединен с первым информационным входом

0

5

0

5

0

5

0

5

0

5

j-й ячейки анализа первой группы второй матрицыt вторые информационные входы i-й и j-й ячеек анализа 1-х групп соответственно первой и второй матриц подключены к вторым информационным выходам соответственно i-й и j-й ячеек анализа (1+1)-й группы той же матрицы, входы переноса первых ячеек анализа всех групп обеих матриц подключены к входу логической единицы устройства, выходы переноса m-й и n-й ячеек анализа s-й группы соответственно первой и второй матрицы, где s-1 , 2,..., соединены соответственно с первым информационным входом s-ro коммутатора и с первым входом s-ro элемента ИЛИ, выходы которых соединены соответственно с первыми и вторыми управляющими входами всех ячеек анализа s-й группы обеих матриц, выход переноса n-й ячейки анализа s-й группы второй матрицы соединен с вторым информационным входом s-ro коммутатора, выход 1-го элемента ИЛИ соединен с вторым входом (l-H)-ro элемента ИЛИ, вторые информационные входы всех ячеек анализа k-й группы обеих матриц подключены к входу логического нуля устройства, входы задания режима всех ячеек анализа первой и второй матриц подключены к входам соответственно логической единицы и логического нуля устройства, первый выход генератора импульсов соединен с входом разрешения записи регистра и со счетным входом счетчика, первый и второй выходы генератора импульсов соединены с входами установки триггера соответственно в единичное и нулевое состояния, прямой выход которого соединен с управляющими входами всех коммутаторов, второй и третий выходы генератора импульсов соединены соответственно с первым и вторым тактовыми входами всех ячеек анализа обеих матриц, второй вход первого и третий вход k-x элементов ИЛИ подключены соответственно к входам логического нуля и логической единицы устройства, третий информаци- -онный вход i-й ячейки анализа k-й группы первой матрицы является выходом 1-го разряда k-ro числа отсортированной выборки ус тройств а, в ячейках анализа второй матрицы второй информационный вход соединен с первым входом пятого элемента И, выход которого

соединен с первым входом пятого элеента И, выход которого соединен с первым входом второго элемента ИЛИ, во всех ячейках анализа обеих матриц j первый информационный вход соединен с первым информационным входом первого коммутатора, третьим входом четертого элемента И и с инверсными входами первого и седьмого элементов ю И, второй информационный вход ячейки анализа соединен с первым информационным входом второго коммутатора и с инверсным входом шестого элемента И, выход которого соединен с первым вхо- 15. дом третьего элемента ИЛИ, первый управляющий вход ячейки анализа соединен с управляющим входом первого коммутатора, третьим входом второго и вторым входом первого элементов И, 20 выходы которых соединены с вторыми входами соответственно второго и третьего элементов ИЛИ, выходы которых соединены с входами установки триггера соответственно в единичное 25 и нулевое состояния, прямой выход

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

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения сортировки чисел в скользящей выборке. Устройство содержит регистр 1, k групп ячеек анализа ЯА 2 -З-щщщ ( 8 апертура выборки, m - количество разрядов анализируемых чисел), генератор 3 импульсов, триггер 4, счетчик 5, коммутаторы , элементы ИЛИ 7, -7, входы 8, выходы 9 ,«-9 t разрядов чисел отсортированной выборки. ЯА 2 содержит триггер, элементы И, ИЛИ, два коммутатора, информационные управляющие и тактовые входы, вход перекоса, вход управления режимом, информационные выходы, выход переноса. Устройство обеспечивает сортировку в порядке убывания чисел в скользящей выборке, т.е. сначала - сортировка выборки чисел |А (, А,... Аку, на следующем такте - выборки чисел (А 1лг А« А,.г Т| и т.д. 2 ил. (Л