×
08.03.2019
219.016.d55c

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

Вид РИД

Изобретение

Юридическая информация Свернуть Развернуть
№ охранного документа
0002451988
Дата охранного документа
27.05.2012
Краткое описание РИД Свернуть Развернуть
Аннотация: Изобретение относится к области обработки информации. Техническим результатом является повышение быстродействия расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем в строке данных длиной n, при этом число используемых сумматоров должно быть более O(nlogn), при этом обеспечивается задержка расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем не более tlogn, где t - задержка сумматора с сохранением переноса, при этом число используемых в устройстве сумматоров составляет nlogn. Быстродействующее устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, согласно решению, характеризуется тем, что оно содержит n бинарных входов битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединеный с выходом Q, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2 входов D и 2 выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней L и 2 сумматоров , имеющих первый А и второй В входы и выход С. 5 ил.
Реферат Свернуть Развернуть

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

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

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

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

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

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

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

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

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

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

Техническим результатом является обеспечение задержки расчета порядковых номеров битов и общего числа бит с высоким логическим уровнем не более t3log2n, где t3 - задержка сумматора с сохранением переноса, при этом число используемых в устройстве сумматоров составляет nlog2n.

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

n=2k бит, где k - положительное целое число, согласно изобретению содержит n бинарных входов битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединеный с выходом Qj, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2m входов Di и 2m выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней Lm-1 и 2m-1 сумматоров , имеющих первый А и второй В входы и выход С, каждый вход уровня Lm соединен с входом Di первого вычислительного уровня Lm-1, каждый вход Dq, где q=i+2m-1, уровня Lm соединен с входом Di второго уровня Lm-1, каждый выход Si первого уровня Lm-1 соединен с выходом Si уровня Lm, выход Sp, где p=2m-1, первого уровня Lm-1 дополнительно соединен со вторыми входами В сумматоров , каждый выход Si второго уровня Lm-1 соединен с первым входом А сумматора SMi,m, каждый выход С сумматора SMi,m соединен с выходом Sq, где q=i+2m-1, уровня Lm, a каждый вычислительный уровень L1 состоит из сумматора SM11, имеющего первый А и второй В входы и выход С, причем первый вход А сумматора соединен с входом D1 и выходом S1, второй вход В сумматора соединен с входом D2, выход С сумматора соединен с выходом S2, каждый вход вычислительного уровня Lk соединен с входом устройства DSj, каждый выход уровня Lk соединен с первым входом X1 элемента Иj, выход Sn уровня Lk дополнительно соединен с выходом POPCNT устройства, каждый вход Dj уровня Lk дополнительно соединен со вторым бинарным входом Х2 элемента Иj.

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

SM11-SM43 сумматоры;

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

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

L1, L2, L3, - вычислительные уровни;

D1, D2 - входы вычислительного уровня L1;

D1-D4 - входы вычислительного уровня L2;

D1-D8 - входы вычислительного уровня L3;

D1-D16 - входы вычислительного уровня L4;

S1,S2 - выходы результатов суммирования вычислительного уровня L1;

S1-S4 - выходы результатов суммирования вычислительного уровня L2;

S1-S8 - выходы результатов суммирования вычислительного уровня L3,

S1-S16 - выходы результатов суммирования вычислительного уровня L4;

DS1-DS8 - бинарные входы битов входной строки данных устройства;

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

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

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

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

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

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

В общем случае предлагаемое устройство имеет n бинарных входов DS1-DSn для получения битов входной строки данных, n выходов Q1-Qn результатов расчета порядковых номеров битов с высоким логическим уровнем, выход POPCNT результатов расчета количества бит с высоким логическим уровнем. Устройство содержит сумматоры SMi,j, имеющие первый А и второй В входы для подачи суммируемых величин и выход С результатов суммирования чисел, подаваемых на входы А и В. Сумматоры SMi,j образуют матрицу с k=log2n стадиями суммирования и n линиями (фиг.5), причем индекс i, указывающий номер сумматора, на стадии суммирования, меняется от 1 до 2k-1, а индекс j, указывающий номер стадии суммирования, меняется от 1 до k. На каждой стадии суммирования расположено n/2 сумматоров. Устройство также содержит n элементов логического умножения И1, И2…, Иn, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе XI, если на вход Х2 подается сигнал с высоким логическим уровенем, если на вход Х2 подается сигнал с низким логическим уровнем, то на выходе Y образуется код числа, равного нулю.

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

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

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

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

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

Описанная выше матрица с числом линий n и числом стадий суммирования k=log2n, имеющая входы D1-Dn и выходы S1-Sn представляет собой вычислительный уровень Lk c входами D1-Dn и выходами S1-Sn. Альтернативный способ построения уровня Lk и соединения входов D1-Dn и входов S1-Sn приведен далее.

Согласно второму способу для описания соединений сумматоры SMi,j удобно сгруппировать в вычислительные уровни . Некоторые вычислительные уровни L1, L2, L3 выделены на диаграмме орграфа, представленной на фиг.5. Каждый уровень Lm имеет r=2m входов результатов вычислений D1, D2,…,Dr и r выходов результатов вычислений S1, S2,…,Sr. При этом, как показано на фиг.2, вычислительный уровень L1 состоит из сумматора SM11, первый вход А которого соединен с входом D1 и с выходом S1, второй вход В соединен с входом D2, а выход С соединен с выходом S2.

На фиг.3 представлен вычислительный уровень L2. Он состоит из первого и второго уровней L1 и двух сумматоров SM12 и SM22. Входы D1-D4 уровня L2 образованы входами D1,D2 уровней L1. При этом вход D1 уровня L2 соединен с входом D1 первого уровня L1, вход D2 уровня L2 соединен с входом D2 первого уровня L1, вход D3, уровня L2 соединен с входом D1 второго уровня L1, вход D4 уровня L2 соединен с входом D2 второго уровня L1. Выход S1 уровня L2 соединен с выходом S1 первого уровня L1, выход S2 уровня L2 соединен с выходом S2 первого уровня L1, выход S3 уровня L2 соединен с выходом С первого сумматора SM12, а выход S4 уровня L2 соединен с выходом С второго сумматора SM22. При этом выход S2 первого уровня L1 дополнительно соединен с входом В первого сумматора SM12 и с входом В второго сумматора SM22, выход S1 второго уровня L1 соединен с входом А первого сумматора SM12, выход S2 второго уровня L1 соединен с входом А второго сумматора SM22.

На фиг.1 представлено устройство для расчета порядковых номеров битов с высоким логическим уровнем для случая n=8. Устройство содержит четыре вычислительных уровня L1, два вычислительных уровня L2, один вычислительный уровень L3. Причем уровни L1 находятся внутри уровней L2 и не изображены на фиг.1. Устройство также содержит элементы логического умножения И18. Выходы уровня L3 соединены через элементы логического умножения с выходами устройства. Уровень L3 включает первый и второй уровни L2 и четыре сумматора SM13, SM23, SM33, SM43. Входы D1-D4 уровня L3 образованы входами D1-D4 первого уровня L2. Входы D5-D8 уровня L3 образованы входами D1-D4, второго уровня L2. Выходы S1-S4 первого уровня L2 образуют выходы S1-S4 уровня L3 и соединены с первыми входами X1 элементов логического умножения И14. Выходы С сумматоров SM13, SM23, SM33, SM43 уровня L3 образуют выходы S5-S8 и соединены с первыми входами элементов логического умножения И58. Вторые бинарные входы Х2 элементов логического умножения И18 соединены с входами устройства D1-D8. Выход S4 первого уровня L2, входящего в состав уровня L3, дополнительно соединен с входами В сумматоров SM13, SM23, SM33, SM43. Выход POPCNT устройства соединен с выходом С сумматора SM43.

В общем случае устройство для расчета порядковых номеров битов с высоким логическим уровнем в бинарной строке данных длиной n=2k, где k - положительное целое число, имеет n бинарных входов DS1,DS2,…,DSn битов входной строки данных, n выходов Q1,Q2,…,Qn порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем. Устройство содержит 2k-1 вычислительных уровней L1, 2k-2 вычислительных уровней L2, 2k-3 вычислительных уровней L3, один вычислительный уровень Lk. В общем случае устройство содержит 2k-m вычислительных уровней . Каждый вычислительный уровень состоит из первого и второго вычислительных уровней Lm-1 и 2m-1 сумматоров , имеющих первый А и второй В входы для подачи суммируемых чисел и выход С результатов суммирования чисел на входах А и В. Каждый вход Di уровня Lm образован входом Di первого вычислительного уровня Lm-1, каждый вход Dq, где q=i+2m-1, уровня Lm образован входом Di второго уровня Lm-1. Каждый выход Si первого уровня Lm-1 образует выход Si уровня Lm, выход Sp, где p=2m-1, первого уровня Lm-1 дополнительно соединен со вторыми входами В сумматоров SMi,m. Каждый выход Si второго уровня Lm-1 соединен с первым входом А сумматора SMi,m, каждый выход С сумматора SMi,m образует выход Sq, где q=i+2m-1, уровня Lm. Вычислительный уровень L1 имеет бинарные входы D1,D2, выходы S1,S2 и состоит из сумматора SM11, имеющего первый А и второй В входы для подачи суммируемых чисел и выход С результатов суммировния чисел на входах А и В, причем первый вход А сумматора соединен с входом D1 и выходом S1, второй вход В сумматора соединен с входом D2, выход С сумматора соединен с выходом S2. Уровень Lk имеет n бинарных входов D1,D2,…,Dn, образующих входы устройства DS1,DS2,…,DSn, n выходов S1,S2…,Sn результатов суммирования. Устройство также содержит n элементов логического умножения И12,…,Иn. Каждый элемент логического умножения имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе X1, если на вход Х2 подается высокий логический уровень, если на входе Х2 низкий логический уровень, то число на выходе Y равно нулю. Каждый выход результатов суммирования Si уровня Lk соединен с первым входом X1 элемента логического умножения Иi, где i=1,…,n. Выход результатов суммирования Sn уровня Lk дополнительно соединен с выходом POPCNT устройства. Каждый вход Di уровня Lk соединен со вторым бинарным входом Х2 элемента логического умножения . Каждый выход Y элемента логического умножения Иi образует выход Qi порядкового номера бита с высоким логическим уровнем.

Устройство работает следующим образом. На бинарные входы DS1, DS2,…, DSn устройства для расчета порядковых номеров битов с высоким логическим уровнем поступают биты входной строки данных. Через время задержки t3 на выходах Q1,Q2,…,Qn устройства появляются значения порядковых номеров битов с высоким логическим уровнем во входной строке данных. Скорость выполнения операции зависит от типа используемых сумматоров. Если задержка сумматора не зависит от числа суммируемых разрядов и равна t3, задержка выполнения предлагаемым устройством расчета порядковых номеров битов с высоким логическим уровнем составляет t3log2(n)+tЗИ, где tЗИ - задержка на логическом элементе И, которой обычно можно пренебречь. Задержка формирования результата на выходе POPCNT равна t3log2(n).

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

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

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

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

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

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

Быстродействующее устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n=2 бит, где k - положительное целое число, характеризующееся тем, что оно содержит n бинарных входов битов входной строки данных, n выходов порядковых номеров битов с высоким логическим уровнем, выход POPCNT количества битов с высоким логическим уровнем, n элементов логического умножения , каждый из которых имеет выход Y, соединений с выходом Q, первый вход X1 и второй бинарный вход Х2, иерархические вычислительные уровни , каждый из которых имеет 2 входов D и 2 выходов , причем каждый вычислительный уровень состоит из первого и второго вычислительных уровней L и 2 сумматоров , имеющих первый А и второй В входы и выход С, каждый вход уровня L соединен с входом D первого вычислительного уровня L, каждый вход D, где q=i+2, уровня L соединен с входом D второго уровня L, каждый выход S первого уровня L соединен с выходом S уровня L, выход S, где p=2, первого уровня L дополнительно соединен со вторыми входами В сумматоров , каждый выход S второго уровня L соединен с первым входом А сумматора SM, каждый выход С сумматора SM соединен с выходом S, где q=i+2, уровня L, а каждый вычислительный уровень L состоит из сумматора SМ, имеющего первый А и второй В входы и выход С, причем первый вход А сумматора соединен с входом D и выходом S, второй вход В сумматора соединен с входом D, выход С сумматора соединен с выходом S, каждый вход вычислительного уровня L соединен с входом устройства DS, каждый выход уровня L соединен с первым входом X1 элемента И, выход S уровня L дополнительно соединен с выходом POPCNT устройства, каждый вход D уровня L дополнительно соединен со вторым бинарным входом Х2 элемента И.
Источник поступления информации: Роспатент

Showing 1-10 of 22 items.
10.01.2013
№216.012.1719

Способ оценки прогрессирования стадии первичной открытоугольной глаукомы

Изобретение относится к медицине, в частности к офтальмологии, и может быть использовано для оценки стадии прогрессирования первичной открытоугольной глаукомы. Для конкретного пациента с уже установленным клиническими методами диагнозом первичная открытоугольная глаукома стадии S проводят...
Тип: Изобретение
Номер охранного документа: 0002471405
Дата охранного документа: 10.01.2013
10.01.2013
№216.012.171a

Способ бесконтактного измерения внутриглазного давления

Изобретение относится к области медицины и может быть использовано для измерения внутриглазного давления. Способ заключается в том, что на глаз воздействуют пневмоимпульсом, с одновременным освещением его поверхности лазером, используя калибровочную кривую для модели глаза. Преобразуют...
Тип: Изобретение
Номер охранного документа: 0002471406
Дата охранного документа: 10.01.2013
10.01.2013
№216.012.1a22

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

Изобретение относится к металлоискателям для целей диагностики и дефектоскопии, археологии, входного контроля в системах безопасности и т.п. и может использоваться для обнаружения локальных неоднородностей в виде металлических и металлосодержащих предметов ограниченных размеров, проводных линий...
Тип: Изобретение
Номер охранного документа: 0002472182
Дата охранного документа: 10.01.2013
10.01.2013
№216.012.1a53

Способ экспериментального моделирования стресс-индуцированного развития острого язвенного кровотечения

Изобретение относится к области экспериментальной медицины, в частности к гастроэнтерологии, и касается моделирования развития острого язвенного кровотечения. Для этого обеспечивают индуцированное последовательное воздействие на крыс путем хронического социального и иммобилизационного стрессов....
Тип: Изобретение
Номер охранного документа: 0002472231
Дата охранного документа: 10.01.2013
20.02.2013
№216.012.2801

Способ изготовления зонда для ближнеполевой сверхвысокочастотной микроскопии

Изобретение относится к измерительной технике и может быть использовано в ближнеполевой сканирующей СВЧ и оптической микроскопии. Способ изготовления стеклянного зонда с проводящей сердцевиной включает помещение в стеклянную трубку легкоплавкого металла или металлического сплава, температура...
Тип: Изобретение
Номер охранного документа: 0002475761
Дата охранного документа: 20.02.2013
10.04.2013
№216.012.344d

Способ визуализации аминокислот на целлюлозной матрице, средство для его реализации и способ получения средства

Группа изобретений относится к аналитической химии, а именно к идентификации и экспрессного полуколичественного определения биологически активных соединений в сложных смесях. Способ получения средства для визуализации аминокислот на целлюлозной матрице включает приготовление водного раствора,...
Тип: Изобретение
Номер охранного документа: 0002478932
Дата охранного документа: 10.04.2013
10.06.2013
№216.012.4868

Способ повышения стабильности водного раствора квантовых точек - наночастиц селенида кадмия, покрытых меркаптокислотами

Изобретение относится к аналитической химии. Водный раствор квантовых точек на основе селенида кадмия, покрытых меркаптокислотой, стабилизируют, вводя сульфит натрия до его концентрации в растворе 0,02-0,2 моль/л. Технический результат - повышение стабильности водного раствора квантовых точек...
Тип: Изобретение
Номер охранного документа: 0002484116
Дата охранного документа: 10.06.2013
27.09.2013
№216.012.70cb

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

Изобретение относится к области твердотельной сверхвысокочастотной микроэлектроники, в частности к методам получения электромагнитных колебаний в СВЧ и КВЧ диапазоне, и может использоваться в устройствах для передачи информации. Достигаемый технический результат - расширение диапазона...
Тип: Изобретение
Номер охранного документа: 0002494526
Дата охранного документа: 27.09.2013
20.02.2019
№219.016.becb

Генератор случайных перестановок

Устройство относится к вычислительной, информационно-измерительной радиотехнике и может быть использовано в системах защиты информации от несанкционированного доступа. Технический результат - обеспечение высокой скорости работы устройства, формирующего уникальные случайные числа путем генерации...
Тип: Изобретение
Номер охранного документа: 0002395834
Дата охранного документа: 27.07.2010
20.02.2019
№219.016.c2c3

Генератор импульсов случайной длительности

Изобретение относится к вычислительной технике, информационно-измерительной радиотехнике и может быть использовано в качестве источника подкачки энтропии в систему генерирования случайных чисел для различных устройств информационной безопасности. Техническим результатом является обеспечение...
Тип: Изобретение
Номер охранного документа: 0002408059
Дата охранного документа: 27.12.2010
Showing 1-8 of 8 items.
10.01.2013
№216.012.1a22

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

Изобретение относится к металлоискателям для целей диагностики и дефектоскопии, археологии, входного контроля в системах безопасности и т.п. и может использоваться для обнаружения локальных неоднородностей в виде металлических и металлосодержащих предметов ограниченных размеров, проводных линий...
Тип: Изобретение
Номер охранного документа: 0002472182
Дата охранного документа: 10.01.2013
20.07.2013
№216.012.5819

Устройство перестановок и сдвигов битов данных в микропроцессорах

Изобретение относится к средствам перестановок и сдвигов битов данных в микропроцессорах. Технический результат заключается в увеличении скорости выполнения операций. Устройство содержит n-разрядный вход данных X-X, n-разрядный выход данных Y-Y, n-разрядный вход битов маскирования F-F,...
Тип: Изобретение
Номер охранного документа: 0002488161
Дата охранного документа: 20.07.2013
20.02.2019
№219.016.becb

Генератор случайных перестановок

Устройство относится к вычислительной, информационно-измерительной радиотехнике и может быть использовано в системах защиты информации от несанкционированного доступа. Технический результат - обеспечение высокой скорости работы устройства, формирующего уникальные случайные числа путем генерации...
Тип: Изобретение
Номер охранного документа: 0002395834
Дата охранного документа: 27.07.2010
20.02.2019
№219.016.c2c3

Генератор импульсов случайной длительности

Изобретение относится к вычислительной технике, информационно-измерительной радиотехнике и может быть использовано в качестве источника подкачки энтропии в систему генерирования случайных чисел для различных устройств информационной безопасности. Техническим результатом является обеспечение...
Тип: Изобретение
Номер охранного документа: 0002408059
Дата охранного документа: 27.12.2010
08.03.2019
№219.016.d55a

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

Изобретение относится к области обработки информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является упрощение устройства при сохранении высокой скорости выполнения операции....
Тип: Изобретение
Номер охранного документа: 0002451987
Дата охранного документа: 27.05.2012
10.04.2019
№219.017.0834

Устройство управляемой перестановки информации, хранимой в эвм

Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков...
Тип: Изобретение
Номер охранного документа: 0002405187
Дата охранного документа: 27.11.2010
29.04.2019
№219.017.4518

Устройство кросс-кластерной управляемой перестановки информации, хранимой в персональной эвм

Изобретение относится к области вычислительной техники, в частности к кодированию информации, и может быть использовано в системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является возможность высокоскоростной кросс-кластерной перестановки...
Тип: Изобретение
Номер охранного документа: 0002409842
Дата охранного документа: 20.01.2011
18.05.2019
№219.017.5661

Полосовой ферритовый фильтр сверхвысоких частот

Устройство относится к области использования ферритовых резонаторов, частота которых управляется внешним постоянным магнитным полем. Техническим результатом изобретения является увеличение уровня режекции устройства преобразования индукции магнитного поля (УПИ) до минус 10 - минус 15 дБ, а...
Тип: Изобретение
Номер охранного документа: 0002393594
Дата охранного документа: 27.06.2010
+ добавить свой РИД