Главная страница  |  Описание сайта  |  Контакты
Патент на изобретение №2451987

(19)

RU

(11)

2451987

(13)

C1

(51) МПК G06F7/50 (2006.01)

G06F7/60 (2006.01)

(12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ Статус: по данным на 27.08.2012 - действует Пошлина:

(21), (22) Заявка: 2011115981/08, 25.04.2011

(24) Дата начала отсчета срока действия патента:

25.04.2011

Приоритет(ы):

(22) Дата подачи заявки: 25.04.2011

(45) Опубликовано: 27.05.2012

(56) Список документов, цитированных в отчете о

поиске: US 5717616 А, 10.02.1998. US 5541865 А, 30.07.1996. RU 2047216 C1, 27.10.1995. RU 2030783 C1, 10.03.1995. GB 2365636 A, 20.02.2002.

Адрес для переписки:

410012, г.Саратов, ул. Московская, 155, СГУ, ЦПУ, Н.В. Романовой, рег. 325

(72) Автор(ы):

Сотов Леонид Сергеевич (RU)

(73) Патентообладатель(и):

Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)

(54) УСТРОЙСТВО ДЛЯ РАСЧЕТА ПОРЯДКОВЫХ НОМЕРОВ БИТОВ С ВЫСОКИМ ЛОГИЧЕСКИМ УРОВНЕМ В СТРОКЕ ДАННЫХ

(57) Реферат:

Изобретение относится к области обработки информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является упрощение устройства при сохранении высокой скорости выполнения операции. Устройство содержит n=2 k бинарных входов битов строки данных, где k-целое положительное число, n выходов значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки М ij , содержащие сумматоры и образующие пирамидальную структуру с k уровнями обработки, где индекс j меняется от 1 до k=log 2 n и указывает номер уровня обработки, а индекс i меняется от 1 до 2 j-1 и указывает номер блока на уровне. 6 з.п. ф-лы, 7 ил.

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

Известен многовходовый одноразрядный сумматор (пат. 2047216 Россия, G06F 7/50. Многовходовый одноразрядный сумматор). Многовходовый одноразрядный сумматор содержит К элементов сложения по модулю два (К [log 2 n] n разрядность входного двоичного слова), выход r-го из которых соединен с r-м выходом сумматора, отличающийся тем, что содержит p мажоритарных элементов (p [n/2]), s-й которых имеет порог, равный 2s, i-й вход сумматора соединен с i-м входом первого элемента сложения по модулю два и 1-м входом s-го мажоритарного элемента, t-й вход j-го элемента сложения по модулю два , , соединен с выходом мажоритарного элемента с порогом t 2 j-1 , (k+1)-й выход сумматора соединен с выходом мажоритарного элемента с порогом 2 k .

Данный многовходовый одноразрядный сумматор можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n многовходовых одноразрядных сумматоров, при этом общее число используемых в устройстве сумматоров составляет O(n 2 ).

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

Известен метод и устройство для подсчета количества бит с высоким логическим уровнем (пат. 5541865 США, G06F 7/60, 007/50. Method and apparatus for performing a population count operation). Устройство, предназначенное для вычисления числа бит с высоким логическим уровнем элемента данных, включает: первый набор сумматоров с сохранением переноса, состоящий из первого, второго, третьего и четвертого сумматоров, входы которых соединены с входами устройства так, чтобы получить первую, вторую, третью и четвертую битовые части первого элемента данных соответственно, первый и второй сумматоры с сохранением переноса формируют на своих выходах первый многобитовый блок данных, а третий и четвертый сумматоры с сохранением переноса формируют на своих выходах второй многобитовый блок данных; второй набор сумматоров, состоящий из пятого и шестого сумматоров с сохранением переноса, входы которых соединены так, чтобы получить первый и второй многобитовые блоки данных соответственно, пятый и шестой сумматоры с сохранением переноса формируют на своих выходах третий многобитовый блок данных; седьмой сумматор с сохранением переноса, входы которого соединены так, чтобы получить третий многобитовый блок выходных данных, который формирует на своих выходах четвертый многобитовый блок данных; полный сумматор, входы которого соединены так, чтобы получить четвертый многобитовый блок данных, который формирует на своих выходах количество бит с высоким логическим уровнем. Каждый сумматор с сохранением переноса представляет собой 4-2 сумматор с сохранением переноса. Полный сумматор представляет собой четырехбитовый полный сумматор.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом общее число используемых сумматоров составляет O(n 2 ).

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

Известно устройство для расчета количества бит с высоким логическим уровнем (пат. 6754685 США, G06F 5/01, 7/60, 007/00. Dynamic popcount/shift circuit). Устройство выполняет функцию расчета количества бит с высоким логическим уровнем входной строки данных и функцию сдвига данных. Метод, положенный в основу работы устройства, обеспечивает баланс между нагрузкой счетчиков числа бит с высоким логическим уровнем и схем сдвига данных. Это приводит к увеличению скорости выполнения операции. Устройство имеет входы для битов первого вектора, второго вектора, средства для вычисления числа бит с высоким логическим уровнем первого вектора, средства для осуществления операции сдвига множества бит второго вектора на основе результатов расчета числа бит с высоким логическим уровнем первого вектора, средств для формирования третьего вектора, получающегося на основе операции сдвига. Устройство состоит из множества динамических уровней, за которыми следуют статические уровни. На динамических уровнях используются динамические узлы, которые вычисляют величины, зависящие от отдельных бит указателя и разреженного вектора. Устройство расширяется путем повторения базовой схемы, поэтому оно может быть изменено в соответствии с размером указателя и разреженного вектора.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом аппаратурная сложность устройства составляет O(n 2 ).

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

Известно устройство и метод для расчета количества бит с высоким логическим уровнем (пат. 5717616 США, G06F 7/60, 017/00 Computer hardware instruction and method for computing population counts). Устройство предназначено для вычисления числа бит с высоким логическим уровнем в строках большой длины. При этом вся строка разделяется на более мелкие части и для каждой из частей рассчитывается число бит с высоким логическим уровнем. Для ускорения выполнения операции используются сумматоры с сохранением переноса. Устройство состоит из регистра данных, содержащего строку битов, в которой рассчитывается число битов с высоким логическим уровнем, множества полных сумматоров, каждый из которых имеет выход, и суммирует биты с высоким логическим уровнем из уникального набора битов из регистра данных, множества сумматоров с сохранением переноса, каждый из которых имеет выход, и суммирует биты с высоким логическим уровнем из уникального набора битов из аккумулирующего регистра. Каждый из сумматоров с сохранением переноса формирует уникальный набор выходных данных в регистре назначения, где регистр назначения хранит количество бит с высоким логическим уровнем из подмножества бит регистра данных и группу бит из аккумулирующего регистра в формате суммы с сохранением переноса. Множество полных сумматоров образуют иерархическую структуру так, что первый уровень сумматоров рассчитывает число бит с высоким логическим уровнем, хранящихся в регистре данных. Входы полных сумматоров второго уровня соединены с выходами сумматоров первого уровня так, что каждый из сумматоров второго уровня складывает результаты на выходах двух сумматоров первого уровня, причем каждый из выходов сумматора первого уровня соединен с одним входом сумматора второго уровня. Число полных сумматоров первого уровня составляет половину от числа бит в регистре данных, число полных сумматоров на втором уровне составляет четверть от числа бит в регистре данных. Сумматоры с сохранением переноса суммируют одинаковое количество бит. Роль регистра назначения и аккумулирующего регистра выполняет один и тот же регистр.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом общее число используемых сумматоров составляет O(n 2 ).

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

Задачей настоящего решения является разработка простого устройства с количеством используемых сумматоров не более O(n) для расчета значений порядковых номеров битов и общего числа бит с высоким логическим уровнем в строке данных длиной n бит, обеспечивающего высокое быстродействие за счет параллельной обработки данных.

Техническим результатом является сокращение числа используемых в устройстве сумматоров до 5/2n-2log 2 (n)-2 при сохранении высокой скорости выполнения операции.

Поставленная задача достигается тем, что устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, согласно решению содержит n=2 k бинарных входов битов строки данных Db 1 , Db 2 ,. , Db n , где k - целое положительное число, n выходов Q 1 , Q 2 ,. , Q n значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И 1 , И 2 , И n , каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки M ij , образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log 2 n и указывает номер уровня обработки, а индекс i меняется от 1 до 2 l-1 и указывает номер блока на уровне j, каждый блок M ij имеет вход I_NUM1 результатов суммирования с нижнего уровня и выход O_NUM2 результатов суммирования, каждый блок M ij , где j=2,. , k, i=1, 2, , 2j -1 дополнительно имеет вход I_NUM2 результатов суммирования с нижнего уровня и выход O_NUM результатов суммирования, передаваемых на верхний уровень, каждый блок M ij , где j=2,. , k, i=2, 3, , 2 j-1 дополнительно имеет вход I_NUM результатов суммирования с верхнего уровня и выход O_NUM1 результатов суммирования, блок M l,k дополнительно имеет выход O_NUM1 результатов суммирования, блок M n/2,k дополнительно имеет выход I_NUM2 результатов суммирования, при этом у блока M ij уровня j, где j=1, 2,. , k-1, i=1, 2,. , 2 j-1 , выход O_NUM1 соединен с входом I_NUM блока M 2i-1, j+1 выход O_NUM2 соединен с входом I_NUM блока M 2ij+1 вход I_NUM1 соединен с выходом O_NUM блока M 2ij+1 , вход I_NUM2 соединен с выходом O_NUM блока M 2ij+1 у блоков M i,k последнего уровня k, где k=log 2 n, i=1, 2,. , 2 k-1 выход O_NUM1 соединен с первым входом X1 логического элемента И 2i-1 вход I_NUM1 соединен с входом Db 2i-1 устройства и вторым бинарным входом Х2 логического элемента И 2i-1 , выход логического элемента И 2i-1, соединен с выходом Q 2i-1 устройства, выход O_NUM2 блока М i,k соединен с первым входом X1 логического элемента И 2i , вход I_NUM2 блока М i,k соединен с входом Db 2i устройства и вторым бинарным входом Х2 логического элемента И 2i, выход логического элемента И 2i соединен с выходом Q 2i , устройства, выход O_NUM2 блока M n/2,k дополнительно соединен с выходом POPCNT устройства. У блока М 11 вход I_NUM1 соединен с выходом O_NUM2. Каждый блок промежуточного уровня M i,j , где j=2,. , k-1, i=2 j-l , включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход блока I_NUM1 соединен с первым входом сумматора I1, вход I_NUM соединен со вторым входом сумматора I2 и с выходом O_NUM1, выход O_NUM2 соединен с выходом OU сумматора. Каждый блок M l.j , где j=2,. , k-1 включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход I_NUM1 соединен с первым входом сумматора I1 и с выходом O_NUM2, вход I_NUM2 соединен со вторым входом сумматора I2, выход O_NUM соединен с выходом OU сумматора. Блок М 1,k включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход I_NUM1 соединен с первым входом сумматора I1 и с выходом O_NUM1, вход I_NUM2 соединен со вторым входом сумматора I2, выход O_NUM соединен с выходом OU сумматора и с выходом O_NUM2. Каждый блок М i,k последнего уровня k, где i=2,. , n/2, состоит из трех сумматоров, каждый из которых имеет первый I1 и второй I2 входы, и выход OU, причем вход I_NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I_NUM2 соединен со вторым входом I2 первого сумматора, вход I_NUM соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора, выход OU первого сумматора соединен со вторым входом I2 третьего сумматора и с выходом O_NUM при его наличии, выход O_NUM1 соединен с выходом OU второго сумматора, выход O_NUM2 соединен с выходом OU третьего сумматора. Каждый блок промежуточного уровня M i,j , где j=2,. , k-1, i=2, 3,. , 2 j-1 -1 состоит из двух сумматоров, имеющих первый I1 и второй I2 входы, и выход OU, причем вход I_NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I_NUM2 соединен со вторым входом I2 первого сумматора, вход I_NUM соединен с вторым входом I2 второго сумматора и с выходом O_NUM1, выход O_NUM соединен с выходом OU первого сумматора, выход O_NUM2 соединен с выходом OU второго сумматора.

Изобретение поясняется чертежами, где на фиг.1 приведена структурно-функциональная схема устройства для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n=8, на фиг.2 приведена схема блоков М i,k последнего уровня преобразования k, где k=log 2 n, i=2, 3,. , 2 k-1 , на фиг.3 приведена схема блоков промежуточного уровня М s,t , где 1
М 11 - первый блок первого уровня;

М 12 , М 22 - первый и второй блоки второго уровня;

M 13 , М 23 , M 33 , M 43 - первый, второй, третий и четвертый блоки третьего уровня;

И 1 - И 8 - логические элементы И;

X1 - первый вход логического элемента И;

Х2 - второй бинарный вход логического элемента И;

Y - выход логического элемента И;

O_NUM - выход результатов суммирования, передаваемых на верхний уровень;

O_NUM1, O_NUM2 - первый и второй выходы результатов суммирования, передаваемых на нижний уровень;

I_NUM - вход результатов суммирования с верхнего уровня;

I_NUM1, I_NUM2 - первый и второй входы результатов суммирования с нижнего уровня;

Q 1 , Q 2 , Q 3 , Q 4, Q 5 , Q 6 , Q 7 , Q 8 - выходы значений порядковых номеров битов с высоким логическим уровнем;

Db 1 , Db 2 , Db 3 , Db 4 , Db 5 , Db 6 , Db 7 , Db 8 - бинарные входы битов входной строки данных;

POPCNT - выход суммы битов с высоким логическим уровнем;

ADD - сумматор;

I1, I2 - входы сумматора;

OU - выход сумматора.

В общем случае предлагаемое устройство имеет n бинарных входов для получения битов входной строки данных, n выходов результатов расчета порядковых номеров битов с высоким логическим уровнем, выход результатов расчета количества битов с высоким логическим уровнем. Предлагаемое устройство содержит вычислительные блоки M i,j , образующие пирамидальную структуру с k=log 2 n уровнями обработки, причем индекс i меняется от 1 до 2 j-1 и указывает номер блока на уровне, а индекс j меняется от 1 до k и указывает номер уровня обработки. Таким образом, на первом уровне (j=1) расположен единственный блок М 11 , на втором уровне расположено два блока, на третьем - четыре и так далее до последнего уровня (j=k), содержащего n/2 блоков. Устройство также содержит n элементов логического умножения И 1 , И 2 , И n , каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе Х1, если на входе Х2 высокий логический уровень, если на входе Х2 низкий логический уровень, то число на выходе Y равно нулю.

Блоки M i,j разделяются на семь типов.

1. Блок М 11 имеет вход I_NUM1 и выход J_NUM2, которые соединены между собой.

Остальные блоки состоят из сумматоров ADD, каждый из которых имеет первый I1 и второй I2 входы для подачи суммируемых чисел и выход OU, на котором формируется сумма чисел, подаваемых на входы I1 и I2.

2. Блоки M i,k последнего уровня преобразования k, где k=log 2 n, i=2, 3,. , 2 k-l -1 состоят из трех сумматоров ADD. Схема блоков M i,k приведена на фиг.2. Блоки М i,k имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока M i,k соединен с первым входом I1 первого сумматора и со вторым входом I2 второго сумматора. Вход I_NUM2 блока M i,k соединен со вторым входом I2 первого сумматора. Вход I_NUM блока M i,k соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора. Выход O_NUM блока M i,k соединен с выходом OU первого сумматора и со вторым входом I2 третьего сумматора. Выход O_NUM1 блока M i,k соединен с выходом OU второго сумматора. Выход O_NUM2 блока M i,k соединен с выходом OU третьего сумматора. На фиг.1 блоки М 23 , М 33 соответствуют описанию блока M i,k , схема которого представлена на фиг.2.

3. Блоки M s,t промежуточного уровня преобразования t, где 1
4. Блоки М 1m промежуточного уровня преобразования m, где 1
5. Блоки M p,q промежуточного уровня преобразования q, где 1
6. Блок M 1,k последнего уровня преобразования k, где k=log 2 n, состоит из одного сумматора ADD. Схема блока М 1,k приведена на фиг.6. Блок M 1,k имеет выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока M 1,k соединен с первым входом I1 сумматора блока M 1,k и с выходом O_NUM1 блока M 1,k . Вход I_NUM2 блока M 1,k соединен со вторым входом I2 сумматора блока M 1,k . Выход O_NUM блока M 1,k соединен с выходом OU сумматора блока M 1,k и с выходом O_NUM2 блока M i,k . На фиг.1 блок M 13 соответствует описанию блока М 1,k , схема которого представлена на фиг.6.

7. Блок M n/2,k последнего уровня преобразования k, где k=log 2 n, состоит из трех сумматоров ADD. Схема блока M n/2,k приведена на фиг.7. Блок M n/2,k имеет первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока M n/2,k соединен с первым входом I1 первого сумматора и с первым входом I1 второго сумматора. Вход I_NUM2 блока M n/2,k соединен со вторым входом I2 первого сумматора. Вход I_NUM блока M n/2,k соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора. Выход OU первого сумматора блока M n/2,k соединен со вторым входом I2 третьего сумматора. Выход O_NUM1 блока M n/2,k соединен с выходом OU второго сумматора. Выход O_NUM2 блока M n/2,k соединен с выходом OU третьего сумматора. На фиг.1 блок М 43 соответствует описанию блока M n/2,k , схема которого представлена на фиг.7.

Соединения между блоками устройства следующие.

Если у блока М р,m уровня m, где m=1, 2,. , k-1; р=1, 2,. , 2 m-1 существует выход O_NUM1, то он соединен с входом I_NUM блока M 2p-1, m+1 уровня m+1. Выход O_NUM2 блока М р,m уровня m соединен с входом I_NUM блока М 2р,m+1 уровня m+1. Вход I_NUM1 блока М р,m уровня m соединен с выходом O_NUM блока M 2p-1, m+1 уровня m+1, если у блока М р,m уровня m существует вход I_NUM2, то он соединен с выходом O_NUM блока М 2р,m+1 уровня m+1. Выход O_NUM1 каждого блока M i,k последнего уровня k, где k=lоg 2 n, a i=1, 2,. , 2 k-1 соединен с первым входом X1 логического элемента И 2i-1 , вход I_NUM1 блока М i,k соединен с входом Db 2i-1 устройства и вторым бинарным входом Х2 логического элемента И 2i-1 , выход логического элемента И 2p-1 соединен с выходом Q 2p-1 устройства, выход O_NUM2 блока М i,k последнего уровня k, где k=log 2 n, i=1, 2,. , 2 k-l , соединен с первым входом X1 логического элемента И 2i , вход I_NUM2 блока М i,k соединен с входом Db 2i устройства и вторым бинарным входом Х2 логического элемента И 2i , выход логического элемента И 2i соединен с выходом Q 2i устройства. Выход O_NUM2 блока М n/2,k дополнительно соединен с выходом POPCNT суммы битов с высоким логическим уровнем во входной строке данного устройства.

Устройство работает следующим образом. На бинарные входы Db 1 , Db 2 ,. , Db n устройства для расчета порядковых номеров битов с высоким логическим уровнем поступают биты входной строки данных. Через время задержки t 3 на выходах Q 1 , Q 2 ,. , Q n , устройства появляются значения порядковых номеров битов с высоким логическим уровнем во входной строке данных. Скорость выполнения операции зависит от типа используемых сумматоров. Если задержка сумматора не зависит от числа суммируемых разрядов и равна , задержка t 3 выполнения предлагаемым устройством расчета порядковых номеров битов с высоким логическим уровнем составляет t з =2 (log 2 (n)-1). Задержка формирования результата на выходе POPCNT также равна t з .

В блоках M i,j могут использоваться сумматоры с сохранением переноса, сумматоры со сквозным переносом, сумматоры с ускоренным переносом и другие сумматоры, описанные, например, в книге Жан М. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.: Вильямс, 2007, 912 с. При расчете порядковых номеров битов с высоким логическим уровнем в n разрядной строке данных используются схемы для суммирования входных данных с числом разрядов от 1 до lоg 2 n.

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

Число разрядов суммируемых величин в блоках различно. У блока М р,m уровня m, где m=1, 3,. , k; p=1, 2,. , 2 m-1 выход O_NUM1 имеет число двоичных разрядов, равное int(log 2 (p))+k-m+1, где функция int(log 2 (p)) вычисляет ближайшее целое число, большее чем log 2 (p), а выходы O_NUM2 и O_NUM имеют число двоичных разрядов, равное int(log 2 (p))+k-m+2. Таким образом, последний сумматор последнего уровня, формирующий результат на выходе O_NUM2, имеет k+1 разряд. У блока М р,m уровня m, где m=1, 3,. , k; р=1, 2,. , 2 m-1 входы I_NUM1, I_NUM2 имеют число двоичных разрядов, равное k-m+1. В блоках М р,m можно использовать одинаковые сумматоры с числом разрядов суммируемых чисел, равным k, но при этом часть старших разрядов части сумматоров не будет использоваться.

Заметим, что устройство можно использовать при значениях длины входной строки данных n, отличной от степени числа 2. При этом используется только часть блоков, на которые поступают биты строки входных данных. Неиспользуемые блоки и логические элементы И i можно исключить из устройства.

Таким образом, устройство выполняет расчет порядковых номеров битов с высоким логическим уровнем входной бинарной строки данных. Одновременно с расчетом порядковых номеров битов устройство осуществляет расчет количества битов с высоким логическим уровнем во входной строке данных. Устройство характеризуется небольшим числом используемых сумматоров. Аппаратурная сложность устройства, определяемая количеством используемых сумматоров, составляет 5/2n-2log 2 (n)-2, где n - число бит входной строки данных. Это значительно меньше количества сумматоров, необходимого для расчета порядковых номеров битов с высоким логическим уровнем с использованием n устройств расчета количества бит с высоким логическим уровнем. Обработка данных в предлагаемом устройстве выполняется параллельно, что обеспечивает высокую скорость выполнения операции.

Формула изобретения

1. Устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, характеризующееся тем, что оно содержит n=2 k бинарных входов битов строки данных Db 1 , Db 2 , , Db n , где k - целое положительное число, n выходов Q 1 , Q 2 , , Q n значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И 1 , И 2 , , И n , каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки M q , образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log 2 n и указывает номер уровня обработки, а индекс i меняется от 1 до 2 j-1 и указывает номер блока на уровне j, каждый блок М ij имеет вход I-NUM1 результатов суммирования с нижнего уровня и выход 0-NUM2 результатов суммирования, каждый блок M i,j , где j=2, , k, i=1, 2, , 2 j-i -1 дополнительно имеет вход I-NUM2 результатов суммирования с нижнего уровня и выход O-NUM результатов суммирования, передаваемых на верхний уровень, каждый блок M i,j , где j=2, , k, i=2, 3, , 2 j-1 дополнительно имеет вход I-NUM результатов суммирования с верхнего уровня и выход O-NUM1 результатов суммирования, блок M 1,k дополнительно имеет выход O-NUM1 результатов суммирования, блок M n/2,k дополнительно имеет выход I-NUM2 результатов суммирования, при этом у блока М ij уровня j, где j=1, 2, , k-1, i=1, 2, , 2 j-1 , выход O-NUM1 соединен с входом I-NUM блока М 2i+1 , j+i , выход O-NUM2 соединен с входом I-NUM блока М 2i , j+i , вход I-NUM1 соединен с выходом O-NUM блока M 2i-1, j+i , вход I-NUM2 соединен с выходом O-NUM блока М 2i,j+1 , у блоков М i,k последнего уровня k, где k=log 2 n, i=1, 2, , 2 k-1 , выход O-NUM1 соединен с первым входом X1 логического элемента И 2i-1 , вход I-NUM1 соединен с входом Db 2i-i устройства и вторым бинарным входом Х2 логического элемента И 2i-1 , выход логического элемента И 2i-1 соединен с выходом Q 2i-1 устройства, выход O-NUM2 блока M i,k соединен с первым входом X1 логического элемента И 2i , вход I-NUM2 блока М i;k соединен с входом Db 2i устройства и вторым бинарным входом Х2 логического элемента И 2i , выход логического элемента И 2i соединен с выходом Q 2i устройства, выход O-NUM2 блока M n/2,k дополнительно соединен с выходом POPCNT устройства.

2. Устройство по п.1, характеризующееся тем, что у блока М 11 вход I-NUM1 соединен с выходом O-NUM2.

3. Устройство по п.1, характеризующееся тем, что каждый блок промежуточного уровня M i,j , где j=2, , k-1, i=2 j-1 , включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход блока I-NUM1 соединен с первым входом сумматора I1, вход I-NUM соединен со вторым входом сумматора I2 и с выходом O-NUM1, выход O-NUM2 соединен с выходом OU сумматора.

4. Устройство по п.1, характеризующееся тем, что каждый блок М i,j , где j=2, , k-1 включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход I-NUM1 соединен с первым входом сумматора I1 и с выходом O-NUM2, вход I-NUM2 соединен со вторым входом сумматора I2, выход O-NUM соединен с выходом OU сумматора.

5. Устройство по п.1, характеризующееся тем, что блок M 1,k включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход I-NUM1 соединен с первым входом сумматора I1 и с выходом O-NUM1, вход INUM2 соединен со вторым входом сумматора I2, выход O-NUM соединен с выходом OU сумматора и с выходом O-NUM2.

6. Устройство по п.1, характеризующееся тем, что каждый блок М i,k последнего уровня k, где i=2, , n/2, состоит из трех сумматоров, каждый из которых имеет первый I1 и второй I2 входы, и выход OU, причем вход I-NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I-NUM2 соединен со вторым входом I2 первого сумматора, вход I-NUM соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора, выход OU первого сумматора соединен со вторым входом I2 третьего сумматора и с выходом O-NUM при его наличии, выход O-NUM1 соединен с выходом OU второго сумматора, выход O-NUM2 соединен с выходом OU третьего сумматора.

7. Устройство по п.1, характеризующееся тем, что каждый блок промежуточного уровня M i,j , где j=2, , k-1, i=2, 3, , 2 j-1 -1, состоит из двух сумматоров, имеющих первый I1 и второй I2 входы и выход OU, причем вход I-NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I-NUM2 соединен со вторым входом I2 первого сумматора, вход I-NUM соединен со вторым входом I2 второго сумматора и с выходом O-NUM1, выход O-NUM соединен с выходом OU первого сумматора, выход O-NUM2 соединен с выходом OU второго сумматора.

РИСУНКИ