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

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

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

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

Известен метод и устройство для подсчета количества бит с высоким логическим уровнем (см. патент на изобретение US 5541865, МПК G06F 7/60, G06F 007/50). Устройство, предназначенное для вычисления числа бит с высоким логическим уровнем элемента данных, включает: первый набор сумматоров с сохранением переноса, состоящий из первого, второго, третьего и четвертого сумматоров, входы которых соединены с входами устройства так, чтобы получить первую, вторую, третью и четвертую битовые части первого элемента данных соответственно, первый и второй сумматоры с сохранением переноса формируют на своих выходах первый многобитовый блок данных, а третий и четвертый сумматоры с сохранением переноса формируют на своих выходах второй многобитовый блок данных; второй набор сумматоров, состоящий из пятого и шестого сумматоров с сохранением переноса, входы которых соединены так, чтобы получить первый и второй многобитовые блоки данных соответственно, пятый и шестой сумматоры с сохранением переноса формируют на своих выходах третий многобитовый блок данных; седьмой сумматор с сохранением переноса, входы которого соединены так, чтобы получить третий многобитовый блок выходных данных, который формирует на своих выходах четвертый многобитовый блок данных; полный сумматор, входы которого соединены так, чтобы получить четвертый многобитовый блок данных, который формирует на своих выходах количество бит с высоким логическим уровнем. Каждый сумматор с сохранением переноса представляет собой 4-2 сумматор с сохранением переноса. Полный сумматор представляет собой четырехбитовый полный сумматор.

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

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

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

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

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

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

Техническим результатом является обеспечение задержки расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем не более t₃log₂n, где t₃ - задержка сумматора с сохранением переноса, при этом число используемых в устройстве сумматоров составляет nlog₂n.

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

n=2^k бит, где k - положительное целое число, согласно изобретению содержит n бинарных входов битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединеный с выходом Q_j, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2^m входов D_i и 2^m выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней L_m-1 и 2^m-1 сумматоров , имеющих первый А и второй В входы и выход С, каждый вход уровня L_m соединен с входом D_i первого вычислительного уровня L_m-1, каждый вход D_q, где q=i+2^m-1, уровня L_m соединен с входом D_i второго уровня L_m-1, каждый выход S_i первого уровня L_m-1 соединен с выходом S_i уровня L_m, выход S_p, где p=2^m-1, первого уровня L_m-1 дополнительно соединен со вторыми входами В сумматоров , каждый выход S_i второго уровня L_m-1 соединен с первым входом А сумматора SM_i,m, каждый выход С сумматора SM_i,m соединен с выходом S_q, где q=i+2^m-1, уровня L_m, a каждый вычислительный уровень L₁ состоит из сумматора SM₁₁, имеющего первый А и второй В входы и выход С, причем первый вход А сумматора соединен с входом D₁ и выходом S₁, второй вход В сумматора соединен с входом D₂, выход С сумматора соединен с выходом S₂, каждый вход вычислительного уровня L_k соединен с входом устройства DS_j, каждый выход уровня L_k соединен с первым входом X1 элемента И_j, выход S_n уровня L_k дополнительно соединен с выходом POPCNT устройства, каждый вход D_j уровня L_k дополнительно соединен со вторым бинарным входом Х2 элемента И_j.

Изобретение поясняется чертежами, где на фиг.1 приведена схема устройства расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n=8, на фиг.2 приведена схема вычислительного уровня L₁, на фиг.3 приведена схема вычислительного уровня L₂, на фиг.4 приведена структурно-функциональная схема вычислительного уровня L₃ устройства, на фиг.5 приведена диаграмма орграфа матрицы сумматоров устройства для случая n=16, где

SM₁₁-SM₄₃ сумматоры;

А, В - первый и второй входы сумматора;

С - выход сумматора;

L₁, L₂, L₃, - вычислительные уровни;

D₁, D₂ - входы вычислительного уровня L₁;

D₁-D₄ - входы вычислительного уровня L₂;

D₁-D₈ - входы вычислительного уровня L₃;

D₁-D₁₆ - входы вычислительного уровня L₄;

S₁,S₂ - выходы результатов суммирования вычислительного уровня L₁;

S₁-S₄ - выходы результатов суммирования вычислительного уровня L₂;

S₁-S₈ - выходы результатов суммирования вычислительного уровня L₃,

S₁-S₁₆ - выходы результатов суммирования вычислительного уровня L₄;

DS₁-DS₈ - бинарные входы битов входной строки данных устройства;

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

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

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

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

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

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

В общем случае предлагаемое устройство имеет n бинарных входов DS₁-DS_n для получения битов входной строки данных, n выходов Q₁-Q_n результатов расчета порядковых номеров битов с высоким логическим уровнем, выход POPCNT результатов расчета количества бит с высоким логическим уровнем. Устройство содержит сумматоры SM_i,j, имеющие первый А и второй В входы для подачи суммируемых величин и выход С результатов суммирования чисел, подаваемых на входы А и В. Сумматоры SM_i,j образуют матрицу с k=log₂n стадиями суммирования и n линиями (фиг.5), причем индекс i, указывающий номер сумматора, на стадии суммирования, меняется от 1 до 2^k-1, а индекс j, указывающий номер стадии суммирования, меняется от 1 до k. На каждой стадии суммирования расположено n/2 сумматоров. Устройство также содержит n элементов логического умножения И₁, И₂…, И_n, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе XI, если на вход Х2 подается сигнал с высоким логическим уровенем, если на вход Х2 подается сигнал с низким логическим уровнем, то на выходе Y образуется код числа, равного нулю.

Ниже приведены два способа описания соединений сумматоров.

Для описания первого способа рассматривается матрица с числом линий n и числом стадий суммирования (столбцов) k=log₂n.

Устройство содержит nk/2 сумматоров, которые располагаются в матрице приведенным ниже способом, при этом на каждой стадии суммирования находится n/2 сумматоров. Расположение сумматоров иллюстрируется диаграммой орграфа для случая n=16, k=4, представленной на фиг.5. Во всех вершинах, кроме висячих, определяющих входы и выходы матрицы, расположены сумматоры. Входы D₁-D₁₆ матрицы соединены с соответстующими входами DS₁-DS₁₆ устройства. Матрица имеет выходы S₁-S₁₆. Каждый выход матрицы соединен с входом X1 элемента логического умножения И_i. На фиг.5 представлены 4 стадии суммирования j=1, j=2, j=3, j=4. Каждая вершина орграфа, в которой расположен сумматор, имеет две входящие дуги и одну или несколько исходящих дуг. Две входящие дуги определяют соединения первого А и второго В входов сумматора. Исходящие дуги определяют соединения выхода сумматора.

Сумматоры первой стадии расположены на четных линиях с номерами 2i, . Сумматоры второй стадии расположены на линиях с номерами 4i и . Сумматоры третьей стадии расположены на линиях с номерами 8i, 8i-1, 8i-2, . В общем случае сумматоры стадии расположены на линиях с номерами Каждый вход соединен с входом A первого, ближайшего к входу DS_i, сумматора, расположенного на линии i, если такого сумматора нет, вход DS_i соединен с выходом S_i. Выход С каждого сумматора, расположенного на линии и стадии соединен с входом А сумматора следующей за j стадии, расположенного на линии i, причем если на линии i нет ни одного сумматора на стадиях с номером, большим j, то выход С соединен с выходом S_i.

Каждый вход матрицы дополнительно соединен с входом В сумматора МS_i,1, расположенного на линии 2i первой стадии. Выход С каждого сумматора MS_i,1, расположенного на линии первой стадии дополнительно соединен с входами В двух сумматоров, расположенных на второй стадии, на линиях с номерами 4i и . Выход С каждого сумматора, расположенного на линии второй стадии дополнительно соединен с входами В четырех сумматоров, расположенных на четырех линиях с номерами 8i, 8i-1, 8i-2, третьей стадии. В общем случае, выход С каждого сумматора стадии расположенного на линии с номером дополнительно соединен с входами В 2^j сумматоров, расположенных на линиях с номерами стадии j+1.

Описанная выше матрица с числом линий n и числом стадий суммирования k=log₂n, имеющая входы D₁-D_n и выходы S₁-S_n представляет собой вычислительный уровень L_k c входами D₁-D_n и выходами S₁-S_n. Альтернативный способ построения уровня L_k и соединения входов D₁-D_n и входов S₁-S_n приведен далее.

Согласно второму способу для описания соединений сумматоры SM_i,j удобно сгруппировать в вычислительные уровни . Некоторые вычислительные уровни L₁, L₂, L₃ выделены на диаграмме орграфа, представленной на фиг.5. Каждый уровень L_m имеет r=2^m входов результатов вычислений D₁, D₂,…,D_r и r выходов результатов вычислений S₁, S₂,…,S_r. При этом, как показано на фиг.2, вычислительный уровень L₁ состоит из сумматора SM₁₁, первый вход А которого соединен с входом D₁ и с выходом S₁, второй вход В соединен с входом D₂, а выход С соединен с выходом S₂.

На фиг.3 представлен вычислительный уровень L₂. Он состоит из первого и второго уровней L₁ и двух сумматоров SM₁₂ и SM₂₂. Входы D₁-D₄ уровня L₂ образованы входами D₁,D₂ уровней L₁. При этом вход D₁ уровня L₂ соединен с входом D₁ первого уровня L₁, вход D₂ уровня L₂ соединен с входом D₂ первого уровня L₁, вход D₃, уровня L₂ соединен с входом D₁ второго уровня L₁, вход D₄ уровня L₂ соединен с входом D₂ второго уровня L₁. Выход S₁ уровня L₂ соединен с выходом S₁ первого уровня L₁, выход S₂ уровня L₂ соединен с выходом S₂ первого уровня L₁, выход S₃ уровня L₂ соединен с выходом С первого сумматора SM₁₂, а выход S₄ уровня L₂ соединен с выходом С второго сумматора SM₂₂. При этом выход S₂ первого уровня L₁ дополнительно соединен с входом В первого сумматора SM₁₂ и с входом В второго сумматора SM₂₂, выход S₁ второго уровня L₁ соединен с входом А первого сумматора SM₁₂, выход S₂ второго уровня L₁ соединен с входом А второго сумматора SM₂₂.

На фиг.1 представлено устройство для расчета порядковых номеров битов с высоким логическим уровнем для случая n=8. Устройство содержит четыре вычислительных уровня L₁, два вычислительных уровня L₂, один вычислительный уровень L₃. Причем уровни L₁ находятся внутри уровней L₂ и не изображены на фиг.1. Устройство также содержит элементы логического умножения И₁-И₈. Выходы уровня L₃ соединены через элементы логического умножения с выходами устройства. Уровень L₃ включает первый и второй уровни L₂ и четыре сумматора SM₁₃, SM₂₃, SM₃₃, SM₄₃. Входы D₁-D₄ уровня L₃ образованы входами D₁-D₄ первого уровня L₂. Входы D₅-D₈ уровня L₃ образованы входами D₁-D₄, второго уровня L₂. Выходы S₁-S₄ первого уровня L₂ образуют выходы S₁-S₄ уровня L₃ и соединены с первыми входами X1 элементов логического умножения И₁-И₄. Выходы С сумматоров SM₁₃, SM₂₃, SM₃₃, SM₄₃ уровня L₃ образуют выходы S₅-S₈ и соединены с первыми входами элементов логического умножения И₅-И₈. Вторые бинарные входы Х2 элементов логического умножения И₁-И₈ соединены с входами устройства D₁-D₈. Выход S₄ первого уровня L₂, входящего в состав уровня L₃, дополнительно соединен с входами В сумматоров SM₁₃, SM₂₃, SM₃₃, SM₄₃. Выход POPCNT устройства соединен с выходом С сумматора SM₄₃.

В общем случае устройство для расчета порядковых номеров битов с высоким логическим уровнем в бинарной строке данных длиной n=2^k, где k - положительное целое число, имеет n бинарных входов DS₁,DS₂,…,DS_n битов входной строки данных, n выходов Q₁,Q₂,…,Q_n порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем. Устройство содержит 2^k-1 вычислительных уровней L₁, 2^k-2 вычислительных уровней L₂, 2^k-3 вычислительных уровней L₃, один вычислительный уровень L_k. В общем случае устройство содержит 2^k-m вычислительных уровней . Каждый вычислительный уровень состоит из первого и второго вычислительных уровней L_m-1 и 2^m-1 сумматоров , имеющих первый А и второй В входы для подачи суммируемых чисел и выход С результатов суммирования чисел на входах А и В. Каждый вход D_i уровня L_m образован входом D_i первого вычислительного уровня L_m-1, каждый вход D_q, где q=i+2^m-1, уровня L_m образован входом D_i второго уровня L_m-1. Каждый выход S_i первого уровня L_m-1 образует выход S_i уровня L_m, выход S_p, где p=2^m-1, первого уровня L_m-1 дополнительно соединен со вторыми входами В сумматоров SM_i,m. Каждый выход S_i второго уровня L_m-1 соединен с первым входом А сумматора SM_i,m, каждый выход С сумматора SM_i,m образует выход S_q, где q=i+2^m-1, уровня L_m. Вычислительный уровень L₁ имеет бинарные входы D₁,D₂, выходы S₁,S₂ и состоит из сумматора SM₁₁, имеющего первый А и второй В входы для подачи суммируемых чисел и выход С результатов суммировния чисел на входах А и В, причем первый вход А сумматора соединен с входом D₁ и выходом S₁, второй вход В сумматора соединен с входом D₂, выход С сумматора соединен с выходом S₂. Уровень L_k имеет n бинарных входов D₁,D₂,…,D_n, образующих входы устройства DS₁,DS₂,…,DS_n, n выходов S₁,S₂…,S_n результатов суммирования. Устройство также содержит n элементов логического умножения И₁,И₂,…,И_n. Каждый элемент логического умножения имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе X1, если на вход Х2 подается высокий логический уровень, если на входе Х2 низкий логический уровень, то число на выходе Y равно нулю. Каждый выход результатов суммирования S_i уровня L_k соединен с первым входом X1 элемента логического умножения И_i, где i=1,…,n. Выход результатов суммирования S_n уровня L_k дополнительно соединен с выходом POPCNT устройства. Каждый вход D_i уровня L_k соединен со вторым бинарным входом Х2 элемента логического умножения . Каждый выход Y элемента логического умножения И_i образует выход Q_i порядкового номера бита с высоким логическим уровнем.

Устройство работает следующим образом. На бинарные входы DS₁, DS₂,…, DS_n устройства для расчета порядковых номеров битов с высоким логическим уровнем поступают биты входной строки данных. Через время задержки t₃ на выходах Q₁,Q₂,…,Q_n устройства появляются значения порядковых номеров битов с высоким логическим уровнем во входной строке данных. Скорость выполнения операции зависит от типа используемых сумматоров. Если задержка сумматора не зависит от числа суммируемых разрядов и равна t₃, задержка выполнения предлагаемым устройством расчета порядковых номеров битов с высоким логическим уровнем составляет t₃log₂(n)+t_ЗИ, где t_ЗИ - задержка на логическом элементе И, которой обычно можно пренебречь. Задержка формирования результата на выходе POPCNT равна t₃log₂(n).

В качестве сумматоров могут использоваться сумматоры с сохранением переноса, сумматоры с последовательным переносом, сумматоры со сквозным переносом, сумматоры с ускоренным переносом и другие сумматоры, описанные, например, в книгах Жан М. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.: Вильямс, 2007. 912 с., или Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. 5-е изд. СПб.: Питер; Киев: Изд. группа BHV, 2003. 848 с. При расчете порядковых номеров битов с высоким логическим уровнем в n разрядной строке данных используются сумматоры входных данных с числом разрядов от 1 до log₂n.

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

Число разрядов суммируемых сумматорами SM_i,j величин различно. У сумматора SM_i,j уровня на первый вход поступает число с количеством двоичных разрядов от 1 до j, а на второй вход поступает число с количеством двоичных разрядов j.

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

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

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

Изобретение относится к области обработки информации. Техническим результатом является повышение быстродействия расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем в строке данных длиной n, при этом число используемых сумматоров должно быть более O(nlog₂n), при этом обеспечивается задержка расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем не более t₃log₂n, где t₃ - задержка сумматора с сохранением переноса, при этом число используемых в устройстве сумматоров составляет nlog₂n. Быстродействующее устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, согласно решению, характеризуется тем, что оно содержит n бинарных входов битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединеный с выходом Q_j, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2^m входов D_i и 2^m выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней L_m-1 и 2^m-1 сумматоров , имеющих первый А и второй В входы и выход С. 5 ил.

Быстродействующее устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n=2^k бит, где k - положительное целое число, характеризующееся тем, что оно содержит n бинарных входов
битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединений с выходом Q_j, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2^m входов D_i и 2^m выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней L_m-1 и 2^m-l сумматоров , имеющих первый А и второй В входы и выход С, каждый вход уровня L_m соединен с входом D_i первого вычислительного уровня L_m-1, каждый вход D_q, где q=i+2^m-1, уровня L_m соединен с входом D_i второго уровня L_m-1, каждый выход S_i первого уровня L_m-1 соединен с выходом S_i уровня L_m, выход S_p, где p=2^m-l, первого уровня L_m-1 дополнительно соединен со вторыми входами В сумматоров , каждый выход S_i второго уровня L_m-1 соединен с первым входом А сумматора SM_i,m, каждый выход С сумматора SM_i,m соединен с выходом S_q, где q=i+2^m-l, уровня L_m, а каждый вычислительный уровень L₁ состоит из сумматора SМ₁₁, имеющего первый А и второй В входы и выход С, причем первый вход А сумматора соединен с входом D₁ и выходом S₁, второй вход В сумматора соединен с входом D₂, выход С сумматора соединен с выходом S₂, каждый вход вычислительного уровня L_k соединен с входом устройства DS_j, каждый выход уровня L_k соединен с первым входом X1 элемента И_j, выход S_n уровня L_k дополнительно соединен с выходом POPCNT устройства, каждый вход D_j уровня L_k дополнительно соединен со вторым бинарным входом Х2 элемента И_j.