Устройство для выбора упорядоченной последовательности данных Советский патент 1984 года по МПК G06F7/06 

n групп элементов И по m элементов в каждой группе, причем в каждом узле формирования сигналов переписи выходы элементов И i-й группы соединены с входами ii-ro элемента ИЛИ узла формирования сигналов переписи, каждый j-и узел преобраэования кодов, где ,3,...,п,содержит m элементов И и m элементов И-НЕ, причем выход j-ro элемента И-НЕ соединен с J-M выходом j-й группы информационных выходов блока анализа и его BTopbiM входом j-го элемента И

(j ll-ro уэла преобразования кодов, выход j-ro элемента И узла преобразования кодов соединен с прямым входом

j-го элемента И-НЕ,с (j + l)-ми инверс иыми входами (j+l )-го, (, т-го элементов И-НЕ и с первым входом j-ro элемента И(j+l)-го узла преобразования кодов, первый узел преобразования кодов содержит m элементов И-НЕ, причем,выход j-ro элемента Н-НЕ соединен с J-M выходом первой группы информационных выходов блока анализа и с вторым выходом j-ro

элемента И второго узла преобразования кодов, выход логической суммы

j-го поразрядного узла анализа соединён с прямым входом j-ro элемента И-НЕ, с (j+l )-ми входами (j+ 1 )-го, ( j +2)-го,..., hi-го элементов И-НЕ первого узла преобразования кодов,

i-й выход j-ro поразрядного узла анализа подключен к i-му входу многовходового элемента ШШ, выход которого является выходом логической су-мы j-ro поразрядного узла анализа, i-й выход j-ro поразрядного .узла анализа блока анализа соединен с управляющими входами j-ro элемента И -й группы каждого i-ro узла формирования сигналов переписи, информационные входы J-X элементов И всех групп 4-гго узла формирования сигналов переписи соединены.с выходом j-ro элемента И-НЕ i-ro узла преобразования кодов блока анализа,выход i-ro элемента Ш1И i-ro узла формирования сигналов переписи соединен с Управляющими входами всех элементов И (ii )-й группы устройства.

УСТРОЙСТВО ДЛЯ BbfBOPA УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ, содержащее п входных регистров, п дешифраторов,и регистров результата, (пп| групп элементов Н, h групп элементов ИЛИ, коммутатор, выходы которого являются выходами устройства, блок анализа, включающий поразрядные узлы анализа, каждый из которых содержит (п-1 )элементов И, (г -1 j элеMiEHTOB № и многовходовый элемент ИЛИ, причем выходы каждого i-го регистра, входы которого являются входами i-го сортируемого числа устройства, где ,2,...,h, п - число сортируемых чисел, соединены с входами i-ro дешифратора и с информационными входами i-x элементов И каждой -й группы, j-и выход каждого -го дешифратора соединен с i-M входом j-ro поразрядного узла анализа, где ,2,...,m , m- число разрядов сортируемых чисел, в каждом J-M поразрядном узле анализа k-й вход, где 1 1 ,2,... ..., (п-1)через k-й элемент НЕ соединен с (k+l)-ми входами k-ro, (k + l)-го,. .., ()-го элементов И, каждый р-й вход поразрядного узла анализа подключен к первому входу (р-1 |-го элементам, где ,3,...,№, первый вход j-ro поразрядного узла подключен к его первому выходу,а выход к-го элемента И поразрядного узла анализа соединен с (К+1)-м выходом поразряднаго узла анализа, выходы элементов И V-й группы устройства подключены к соответствующим входам 1-го элемента ИЛИ т -и группы, выходы элементов ИГЩ -и группы соединены с информационными входами )-го регистра результата, выходы которого соединены с информационными входами i-и группы коммутатора, который содержит h (А групп элементов И, дешифратор и гистр, входы которого соединены с шиной Размер Массива, а выходы -с § соответствующими входами дешифратора, i-и выход которого подключен к первым входам элементов И первой, второй,..., (i-и групп, информационные входы i- группы коммутатора со подключены к вторым входам элементов И л-й группы, входы опроса элемен00 00 тов И всех групп соединены с управляющим входом коммутатора, шина Начальное гашение подключена к входам установки в О входных регистров и регистров результата, шина Опрос подключена к управляющему входу коммутатора, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены п узлов формирования сигналов переписи, а в блок анализа h узлов преобразования кодов, каждый t-fi узел формирования сигналов переписи содержит п элементов ИЛИ и

Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации систем обработки данных и автоматизированных систем управления.

Известно устройство для определе,ния наименьшего из и чисел, содержащее входные регистры, дешифраторы, поразрядные узлы анализа, выполненные на элементах НЕ и И, элементы ИЛИ 1 J.

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

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

управления, коммутатор, группы эле-ментов ИЛИ и И, элемент ИЛИ, группы входных элементов И и ИЛИ, шины Начало операции, Начальное гашение и Размер массива, блок анализа, состоящий из элементов ИЛИ и поразрядных узлов анализа, причем выходы каждого i-ro регистра, где i 1,2,...,h , соединены с входами ,

-го дешифратора и с информационными входами элементов И i-й группы, а выходы i-ro элемента ИЛИ подключены к входам управления элементов И 1гй группы, выходы элементов И

каждой i-й группы соединены с входами элементов 1ШИ группы, выходы которых подключены к входам регистра результата, каждый выход i-ro дешифратора соединен с

t-M входом j-ro поразрядного узла анализа, где j-l,2...,m, m -число разрядов сортируемых чисел, каждый .i-й выход j-ro поразрядного узла анализа подключен к j-му входу -го

элемента ИЛИ, а выход переносов каждого к-го поразрядного узла а.нанза, где ,2,... Дгп-1), соединен входом управлония к+1)-го поразядного узла анализа, каждый j-й оразрядный узел анализа состоит из элементов И,п элементов НЕ и многовходового элемента И, причем каждый 1 -и вход поразрядного узла анализа подключен к первому входу i-ro элемента И, вход управления поразрядного узла анализа соединен с вторыми входами элементов И, каждый т-й вход к-го поразрядного узла анализа подключен i-й элемент НЕ к (i +2)-му ходу (i+l),li+2),...,h -го элементоЕ нк -му входу многовходового элемента И, выход которого подключен к выходу переносов к-го поразрядного узла анализа выход каждого i-ro элемента И соединен с -м выходом к-го поразрядного узла анализа,,ni-и прразрядный узел анализа состоит из элементов И и (n-l)-го элемента НЕ, причем каждый р-й вход узла, где ,... ,(h-I), соединен с первым входом р-го элемента И, вход ереносов ь-го поразрядного узла анализа подключен к вторым входам элементов И, каждый р-й входт-го поразрядного узла анализа через р-й элемент НЕ соединен с(р+2)-м входом (р+Г ),{р+2 ),,.., п-го элементов И, гггй вход №-го поразрядного узла анализа подключен к(т-«-2)-му входу П-го элемента И, выход каждого i-ro элемента И соединен с 1-ым выходом щ-го поразрядного узла анализа, выход блока анализа, соединенный с выходом i-ro элемента ИЛИ блока анализа, подключен к первым управляю щим входам 1-х элементов И в каждой из Ч групп элементов |01И, где 1 ,.,... ,г«, информационные входы которык соединены с выходами Е-го входного регистра, и, к первому входу i-го элемента И группы входных элементов И, вторые входы всех элементов группы входных эл1ементов И соединены с выходом элемента ИЛИ, выход i-го элемента группы входных элементов И с первым входом i-ro элемента группы входных элементов ИЛИ, выход которого подключен к входу установки в ноль i-ro входного регистра, т-й выход блока управления подключен к вторым управляющим входам всех элементов И -н группы и к t-му входу элемента ЫШ, выходы элементов И «-и группы из (8п) групп подключены к соответствующим входам i-ro элемента HIIH (-ОЙ группы, выходы которого

соединены с информационными входами И -го регистра результата, группа информационных выходов i-ro регистра, результата соединена с соответствующими информационными входами J-и группы коммутатора, выходы которого являются информационными выходами устройства, управляющий вход коммутатора подключен к выходу блока управления, шина Начальное гашение соединена с входом установки блока управления, с нулевыми входами выходных регистров и с вторыми входами всех элементов группы входных элементов ИЛИ, шина Размер массива соединена с информационными входами коммутора и блока управления,который содержит триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группуп элементов И, генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с прямым выходом триггера управлеиия и первыми входа5 ми элементов И группы, а выход - с счетным входом счетчика, информационные виходы которого подключены к дешифратору, i-и выход которого соединен с вторым входом i-го элемента И группы, выход которого является i-M выходом блоКсТ управления, выход сигнала переполнения счетчика подключен к первому входу элемента ИЛИ, второй вход которого соединен с шиной Начальное гашение, а выход

5 элемента ИЛИ подключен к нулевому входу триггера управления, единичный вход которого соединен с входом

установки блока управления, а инверсный выход является управляющим вы0 ходом блока управления, информационные входы блока управления подключе ны к установочным входам счетчика, коммутатор содержитh групп элементов И, дешифратор, регистр, входы которо5 го соединены с входами коммутатора, а выходы - с соответствующими входами дешифратора, i-й выход которого подключен к первым входам 1,2,...., -х групп элементов И, информационОные входы i-й группы коммутатора подключены к вторым входам элементов И i-й группы, управляющие входы элементов И всех групп соединены с управляющим входом коммутатора 2..

Недостатком устройства.является низкое быстродействие при формировании упорядоченного выходного массива, так как для его получения требуется соответствующее число циклов работы

устройства. При этом время цикла определяется логической глубиной схе. мы выбора экстремального числа. С увеличением размера выходного массива увеличиваются общие затраты времени на получение упорядоченной последовательности данных,

Целью изобретения является повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для выбора упорядоченной последовательности данных, содержащее входных регистров, .п дешифраторов,п регисторов результата, (nnl групп элементов И,п групп элементов ИЛИ, коммутатор, выходы которого являются выходами устройства, блок анализа, включающий поразрядные узлы анализа, каждый из которых содержит (п-1) элементов И, (гг-1 1 элементов НЕ и многовходовый элемент ИЛИ, причем выходы каждого i-го регистра, входы которого являются входами i-ro сортируемого числа устройства, где 1,2,...,п .h - число сортируемых чисел., соедй,нены с входами i-ro дешифратора и с- . информационными входами i-x элеменТОО И каждой i-и группы, i-й выходкаждого 1- г о дешифратора соединен с Ч- входом j-ro поразрядного узла анализа,где ,2,.,.,т, т- число : разрядов сортируемых чисел, в каждом J-M поразрядном узле анализа к-ый вход , где к 1,2,. . . ,(п-1) через к-й элемент Е соединен с () -ми входами , Ik + l ,.. . ,(л -1) -го элементов И, каждый р-й вход поразрядного узла анализа подключен к первому входу (р-1) -го элемента И,где ,3,...,h, первый вход поразрядного узла анализа подключен к его первому выходу,а выход к-го элемента И поразрядного узла анализа соединен с(К+ 1)-ым выходом поразрядного узла анализа, выходы элементов И i-ой группы устройства подключены к соответствующим входам i-ro элемента ИЛИ i-й группы, . выходы элементов ШШ i-й группы сЪёйинены с информационными входами i -го регистра результата,выходы которого соединены с информационными входами i-й группы коммутатора,который содержит п групп элементов И,дешифратор и регистр,входы которого соединены с шиной Размер массива, а выходы с соответствующимивходами дешифратора, i-й выход которого подключен к первым входам элементов И первой, второй,..., i-й групп, информационные входы i-и группы коммутатора подключены к вторым входам элементов И 1-й группы, входы опроса элементовV И всех групп соединены с управляющим входом коммутатора, шина Начальное гашение подключена к входам установки в О входных регистров и регистров результата, шина Опрос подключена к управляющему входу коммутатора, введены п узлов формирования сигналов переписи, а в блок анализа h узлов преобразования кодов, каждый i .-и узел формирования сигналов переписи содержит п элементов ШШ и h групп элементов И по ТТЛ элементов в каждой группе, причем в каждом узле формирования сигналов переписи выхоДь элементов И i-й группы соединены f входами i-го элемента ИЛИ узла формирования сигналов переписи, каждый J-й узел преобразования кодов, где ,3,...,h , содержитm элементов И и гп.элементов И-НЕ, причем выход j-ro элемента И-ЫЕ соединен с J-M выходом j-й группы информационных выходов блока анализа и его вторым входом j-ro элемента И (j + l)-го узла преобразования, кодов, выход j-ro элемента И узла -Преобразования кодов соединен с прямым входом j-ro элемента -И-НЕ,

с (j+I)-MH инверсными входами ( )- го, (j+2 )-го,...т-го элементов И-НЕ . с первым входом j-ro элемента И (j +1 }-го узла преобразования кодов, первый узел преобразования кодов содержит п элементов И-НЕ, причем вь1ход j-ro элемента И-НЕ соединен с i-M выходом первой группы информационных выходов блока анализа и с вторым входом j-ro элемента И второго узла преобразования кодов, выход логической суммы j-ro поразрядного узла анализа соединен с прямым вхо дом j-ro элемента И-НЕ, с (« 1) -ми входами j-fl )-го, (}н-2)-го,..., т-го элементов И-НЕ первого узла преобразования кодов, ij-й выход J-TO поразрядного узла анализа подключен к I-МУ входу многовходового элемента ИЛИ, выкод которого является выходом логической суммы /-го поразрядного узла анализа, i-и выход j-ro цоразрядного узла анализа блока анализа соединен с управляющими входами j-ro элемента И j-й группы каждого 1-го узла формирования сигналов переписи, информационные входы j-X элементов И всех групп

i-ГО узла формирования сигналов переписи соединены с выходом j-ro элемента И-НЕ i-го узла преобразования кодов блока анализа, выход i-го элемента ИЛИ i-ro узла формирования сигналов переписи соединен с управляющими входами всех элементов И (ii) -и группы устройства.

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

Устройство фиг. I)содержит информационные входные шины J,,- 1, подключенные к входам соответствующих входных регистров 2,, соединены с входами соответствующих дешифраторов 3j, выходные шины i , которых подключены к блоку анализа 5, группы информационных выходов 6 и группа управляющих выходов 7 которого соединены с узлами 8 управления, выходные шины 9,.. ...,9 9 которых соединены с управляющими входами групп элементов и 10,- 10,,..., 10. выходы которых подключены к соответ5твующим элементам ИЛИ I „группНы, выходы которых подключены к информационным входам соответствующих регистров результата 12,, выходы 13 13 регистров подключены к коммутатору 1А, выхрдные шины которого являются информационными выходами устройства, шину 16 Начальное гашение, шину 17 Ра мер массива и шину 18 Опрос.

Блок анализа(фиг. 2)содержит поразрядные узлы I9-,- 19 анализа, узлы 20.- 20 преобразования кодов элемент И-НЕ. 21 и элемент И 22.- узлах преобразования кодов.

Поразрядный узел анализа(фиг. 3) содержит элементы НЕ 23 , . многовходовый элемент ИЛИ 24 и элементы И 25.

. Узел формирования сигналов переписи (фиг. 4)содержите групп элементов И 26,,- 26,.,.. гя элементов в каждой и п элементов

ИЛИ 27 - 27. .

Коммутатор(фиг. 5)содержит.регистр 28, соединенный с дешифраторо 29, выходные сигналы которого подключены к элементам И 30f|.

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

Формирование упорядоченной последовательности чисел из исходных основано на преобразований q помой1ью дешифраторов двоичных кодов чисел в распределительные, а затем сравнение одноименных выходов дешифраторов .

Пусть имеются четыре числа а 101.aj-l10, ,, , размещенные в соответствующих регистрах. Требуется преобразовать-эту последовательность в упорядоченную убываюЩУКЭти числа преобразуются дешифраторами, выходные .сигналы которых nor казаны в табл. 1.

В табл. 1 Q,- OT - сигналы логической суммы, а .- сигналы схем анализа.

Таблица

а 010О 100 00 О q

QI .. 7

Из табл. 1 следует, что наименьшее число Находится в третьем регистре, очередное число в четвертом, далее в первом и наконец во втором. Таким образом, упорядоченная последовательность чисел следующая: aj, а, а,,

Отсюда, в первом выходном регист- ре результата должно быть размещено . число, находящееся в третьемвходном, во втором - число из четвертого входного регистра, в третьем - из второго и в четвертом - из первого входного регистра.

Указанием о том, какое первое наименьшее число,является крайняя левая едингца в колонке табл. 1.

Для данного примера - это сигнал Q-, далее -Q2 , Информация о номере входного регистра, где находится экстремальное число, содержится в индексе сигнала о, (соответственно

.. - т -I . ,.. г .Я1Ч4 Ч1Чг2Гак1 1 образом, если код сигналов Q Qyпреобразовать так, чтобы в нем была однаединица, определяющая иомсгр поразрядного узла анализа, то посредством сигналов |,-с(, данного узла можно передать наименьшее число в соответствующий регистр результата.

Итак, для первого выходного регистра двоичный код 1100110 преобразуется в код 1000000, а для второго выходного регистра из кода 0100110 в код 0100110, /Далее, для третьего выходного регистра из лсода 0000110 в код 0000100 и для четвертого будет код 0000010.

Преобразования кодов для выходных регистров с помощью узлЬв преобразования кодов блока 5 анализа(фиг.2I осуществляют следующим образом.

Предварительно посредством поразрядных узлов анализа(фиг. 3)формируются выходные сигналы - спомощью элементов И сигналы , с помощью элемента ИЛИ 24. Блок анализа 5(фиг. 2)содержит И узлов преобразования. В первом узле преобразования, состоящем -из m элементов И-ИЕ, формируется на выходах 6 -6 | двоичный код сигналов логических сумм Q.

Сигнал логической суммы с выхода 19 закрывает по первым инверсным входам все элементы Й-НЕ 2Ц- in Таким образом, на информационных . выходах первой группы формируется двоичный инверсный код 0111111. Эти же сигналы и соответствующие им сигналы Q.,-Q-, воздействуют на входах элементов И 22 второго узла преобразования. На выхрдах элементов И ,2 формируется двоичный прямой код 0100110.

Таким образом, узлы преобразования формируют коды, в которых номер позиции, где находится нулевое значение сигнала, соответствует номеру поразрядного узла 19 анализа определяющее значение очередного экстремального числа.

В четырех узлах преобразования формируются двоичные коды: 0111111, 1011111, 1111011, 1111101. Это означает , что информация о месте разме,щения минимального числа для первого выходного регистра I2(фиг. 1)находится в первой поразрядном узле 19 анализа У)ИГ. 2), для второго - во втором узле (192), Д- третьего - в

пятом U9;) И ДЛЯ чствертого выходного регистра в шестом поразрядном узле 19(j анализа.

Эти сигналы в качестве информациOHH6IX подаются в соответствующие узлы 8j,управления, которые на основе управляющих сигналов -«v (табл. Побеспечивают формирование управляющего сигнала на выходе 9.)э узла 8, например для первого регистра. По этому сигналу число из регистра 2 передается в выходной регистр

42,.

Аналогичным образом обеспечиваетс передача чисел из остальных входных регистров 2 в выходные 122- 2

Таким образом, за счет преобразования двоичного кода сигналов логических сумм поразрядных узлов анализа обеспечивается определени1е места размещения чисел для получения упорядоченного массива и формирование На этой основе управляющих сигналов для реализации исходных. чисел в регистрах результата.

С помощью коммутатора 14 обеспечивается по сигналу Опрос, поступающему по шину 18, выдача указанного размера выходного массива на информационные выходы 15 устройства.

Пусть необходимо из массива четы.рех чисел на выход устройства выдать два числа. Довичный код этого числа поступает в регистр 28(фиг. 5).

Разрядность pefHCTpa определяется максимальным размером исходного массива чисел h и выбирается по выражению :/ .

- /

в дещифраторе 29 будет возбужден второй выход, разрешающий работу элементов И 30 и 30л. По сигналу Опрос, поступающему по шине 18, выходные сигналы регистров 12, 12 по шинам 13, 132через Элементы И 30 и 30 поступят на выходные шины 13, 132 устройства.

С помощью предложенного устройства можно формировать упорядоченную возрастающую последовательность чисел. При этом исходные числа в регистры 2 - 2,принимаются в обратном коде. Выходная последовательность будет также в обратном коде.

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

Вначале по шине 16 Начальное гашение поступает сигнал, по которому входные регистры 2 и выходны 11I регистры 2 устанавливаются .в нулевые состояния. Затем iio входным шинам 1, - 1 принимаются в регистры 2 исходные числа. Если нужно нолучить убывающую последовательность, то числа поступают в прямом коде, ес;п1 возрастающую - обратн Одновременно по шине 17 Размер массива в регистр 28 принимается двоичный код требуемого массива. . В дальнейшем в каждом узле преобразования- кодов(фиг.2)формируются двоичные коды так, что номер.позици размещения нулевого значения сигнала определяет номер поразрядного узла 19 анализа, выходные сигналы которого используются для передачи экстремального числа из соответствующего входного регистра 2 в выходной регистр 12. Формирование выходных сигналов в. регистрах 12 определяется временем задержки в формировании информационных сигналов Поэтому сигнал Опрос по шине 18 поступает по окончании передачи чисел в выходные регистры. Размер сформированной последоиател1 ности определяется двоичным кодом и Размер массива, по которому в дс1лифраторе 29(фиг. 5)возбуждается ташина, номер которой соответствует размеру заданного выходного массива В соответствии с зтим на выходах устройства 15„устанавливается заданный выходной массив данных Из анализа структурной схемы и принципов функционирования известно го устройства время формирования вы ходной упорядоченной последовательности данных определяется периодом сл дования импульсов генератора блока уп равления и размером выходного массива Период следования импульсов хара теризует время одного цикла работы устройства и зависит от времени задерж ; при выборе экстремального числа. Для формирования массива размеро /в чисел(ч.п1 время работы устройств составляет Т tj,t|., где период следования импульсов генератора бло ка управления. . Минимальный период следования импульсов равен Чи и1и- и „ли Г2 А «Н где , f, - времена -задерж-ек в элементах ИЛИ, И . и триггерах входных регистров соответственно ; R Ьд -- время работы дешиф-. ратора, которое можно принять равным aн нES( ремя анализа блоком анализа, максимальное время задержки которого определяется последн 1м (m-ым)поразрядным узлом анализа. ...Если принять, что .,, 2 %-t33, то VltV M u H V ПЗ. В предлагаемом устройстве время выбора заданного массива определяется от момента подачи/исходных чисел во входные регистры до момента подачи сигнала Опрос. Это время определяется временем задержки в устройстве и определяется как . « :t«H HE u J.-He и и-НЕ/ время работы . блока анализа; - время задержки в элементе И-НЕ; упр ч-не время задержки в блоке управления. Если принять, что t.ng 2Г + Т, то .c.2T.T.,(V,.2in}x j(n-i):4c; n+u; . (i) Выигрыш в быстродействии опрёде лим по выражению Т..-Т, , (3) Подставляя в выражение(3(выражения (1)и(2), получим 17air-(4rn-i:12f) W Л.. .100% . .lZili ±12),oo, причем C|4.hОпределим при Каких соотношениях величин ( и h обеспечивается выигрьш1 в быстродействии. Очевидно, что выигрыш в быстро- . действии будет всегда, когда V((.0.. Отсюда, преобразуя выражение(4 ), ПОЛУЧИМ ..iZ5..ll2):.,. т.е. 17с, -(4п + 12)0. . или 4h + 2 T причем Я , Из выражения(5)видно, что выигрьш в быстродействии обеспечивается для h при л 2, Определим ,при каком состоянии , и п достигается вьшгрьпп в быстродействии. Пусть п « 2, тогда из выражения(5) следует, что 8 + 12 20 17 17 т.е. при п 2, q, должно быть равно 2 Если п 3, то 24 Я,-77- т.е. ,3. Из приведенных расчетов следует. что выигрьш в быстродействии достигается при П7 2 для любых значений , причем t,n . Для случая, когда an, в табл. 2 приведены величины W при различных значениях Таблица2 16 32 64 4 58 67 72 Из табл. 2 видно, что преобразования массивов данных большого размера применение предлагаемого устройства более предпочтительно, чем известного. Прн этом наибольший выигрыш в быстродействии достигается при получении выходного упорядоченного массива такого же размера, как и исходный,

Jt J

рШ;

-

«s

« .

e V.

J

Jlr

Ji

a T

Ш

2

.

.

-.r

.4

4s 7|

. , .

II

г5,

л.

4fr

4 «м

Ъ.П1 7/,л.

«f/HS

2Sn-t

7 i 3 rj Г - in П Г i

J и LJ J L

Д

(

.

п-и

tnJ

Фиг.3 «а U- -КЗ «««