УСТРОЙСТВО ДЛЯ РАСЧЕТА ПОРЯДКОВЫХ НОМЕРОВ БИТОВ С ВЫСОКИМ ЛОГИЧЕСКИМ УРОВНЕМ В СТРОКЕ ДАННЫХ Российский патент 2012 года по МПК G06F7/50 G06F7/60 

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

Известен многовходовый одноразрядный сумматор (пат. №2047216 Россия, G06F 7/50. Многовходовый одноразрядный сумматор). Многовходовый одноразрядный сумматор содержит К элементов сложения по модулю два (К [log₂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²).

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная задача достигается тем, что устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, согласно решению содержит n=2^k бинарных входов битов строки данных Db₁, Db₂,.…, Db_n, где k - целое положительное число, n выходов Q₁, Q₂,.…, Q_n значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И₁, И₂…, И_n, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки M_ij, образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log₂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₂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 устройства. У блока М₁₁ вход 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₂n, i=2, 3,.…, 2^k-1, на фиг.3 приведена схема блоков промежуточного уровня М_s,t, где 1<t<k, a 1<s<2^t-1, на фиг.4 приведена схема блоков М_1,m, где 1<m<k, на фиг.5 приведена схема блоков M_pq, где q=2,.…, k-1, p=2^q-1, на фиг.6 приведена схема блока М_1,k, на фиг.7 приведена схема блока M_n/2,k, где

М₁₁ - первый блок первого уровня;

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

M₁₃, М₂₃, M₃₃, M₄₃ - первый, второй, третий и четвертый блоки третьего уровня;

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

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

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

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

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

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

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

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

Q₁, Q₂, Q₃, Q_4, Q₅, Q₆, Q₇, Q₈ - выходы значений порядковых номеров битов с высоким логическим уровнем;

Db₁, Db₂, Db₃, Db₄, Db₅, Db₆, Db₇, Db₈ - бинарные входы битов входной строки данных;

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

ADD - сумматор;

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

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

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

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

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

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

2. Блоки M_i,k последнего уровня преобразования k, где k=log₂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 блоки М₂₃, М₃₃ соответствуют описанию блока M_i,k, схема которого представлена на фиг.2.

3. Блоки M_s,t промежуточного уровня преобразования t, где 1<t<k, a 1<s<2^t-1 состоят из двух сумматоров ADD. Схема блоков M_s,t приведена на фиг.3. Блоки M_s,t имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока M_s,t соединен с первым входом I1 первого сумматора и со первым входом I1 второго сумматора. Вход I_NUM2 блока M_s,t соединен со вторым входом I2 первого сумматора. Вход I_NUM блока M_s,t соединен со вторым входом I2 второго сумматора и с выходом O_NUM1 блока M M_s,t. Выход O_NUM блока M_s,t соединен с выходом OU первого сумматора. Выход O_NUM2 блока M_s,t соединен с выходом OU второго сумматора. На фиг.1 не изображены блоки, которые соответствуют описанию блоков M_s,t, схема которых представлена на фиг.3, так как эти блоки появляются при длине входной строки данных n более восьми бит.

4. Блоки М_1m промежуточного уровня преобразования m, где 1<m<k состоят из одного сумматора ADD. Схема блоков М_1m приведена на фиг.4. Блоки М_1,m, имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, выход O_NUM2 результатов суммирования, передаваемых на нижний уровень, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока М_1,m соединен с первым входом I1 сумматора и с выходом O_NUM2. Вход I_NUM2 блока М_1,m соединен со вторым входом I2 сумматора. Выход O_NUM блока М_1,m соединен с выходом OU сумматора. На фиг.1 блок M_I2 соответствуют описанию блока М_1m, схема которого представлена на фиг.4.

5. Блоки M_p,q промежуточного уровня преобразования q, где 1<q<k, p=2^q-1 состоят из одного сумматора ADD. Схема блоков M_p,q приведена на фиг.5. Блоки M_p,q имеют первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход результатов суммирования с нижнего уровня I_NUM1, вход I_NUM результатов суммирования с верхнего уровня. Вход I_NUM1 блока M_p.q соединен с первым входом I1 сумматора. Вход I_NUM блока M_p,q соединен со вторым входом I2 сумматора и с выходом O_NUM1 блока M_p,q. Выход O_NUM2 блока M_p.q соединен с выходом OU сумматора. На фиг.1 блок М₂₂ соответствуют описанию блока M_p,q, схема которого представлена на фиг.5.

6. Блок M_1,k последнего уровня преобразования k, где k=log₂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₁₃ соответствует описанию блока М_1,k, схема которого представлена на фиг.6.

7. Блок M_n/2,k последнего уровня преобразования k, где k=log₂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 блок М₄₃ соответствует описанию блока 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₂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₂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₁, Db₂,.…, Db_n устройства для расчета порядковых номеров битов с высоким логическим уровнем поступают биты входной строки данных. Через время задержки t₃ на выходах Q₁, Q₂,.…, Q_n, устройства появляются значения порядковых номеров битов с высоким логическим уровнем во входной строке данных. Скорость выполнения операции зависит от типа используемых сумматоров. Если задержка сумматора не зависит от числа суммируемых разрядов и равна τ, задержка t₃ выполнения предлагаемым устройством расчета порядковых номеров битов с высоким логическим уровнем составляет t_з=2τ(log₂(n)-1). Задержка формирования результата на выходе POPCNT также равна t_з.

В блоках M_i,j могут использоваться сумматоры с сохранением переноса, сумматоры со сквозным переносом, сумматоры с ускоренным переносом и другие сумматоры, описанные, например, в книге Жан М. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.: Вильямс, 2007, 912 с. При расчете порядковых номеров битов с высоким логическим уровнем в n разрядной строке данных используются схемы для суммирования входных данных с числом разрядов от 1 до lоg₂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₂(p))+k-m+1, где функция int(log₂(p)) вычисляет ближайшее целое число, большее чем log₂(p), а выходы O_NUM2 и O_NUM имеют число двоичных разрядов, равное int(log₂(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₂(n)-2, где n - число бит входной строки данных. Это значительно меньше количества сумматоров, необходимого для расчета порядковых номеров битов с высоким логическим уровнем с использованием n устройств расчета количества бит с высоким логическим уровнем. Обработка данных в предлагаемом устройстве выполняется параллельно, что обеспечивает высокую скорость выполнения операции.

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

1. Устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, характеризующееся тем, что оно содержит n=2^k бинарных входов битов строки данных Db₁, Db₂, …, Db_n, где k - целое положительное число, n выходов Q₁, Q₂, …, Q_n значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И₁, И₂,…, И_n, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки M_q, образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log₂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₂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, характеризующееся тем, что у блока М₁₁ вход 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 второго сумматора.