RU2763903C1 - Устройство групповой структуры для детектирования границ диапазона единичных бит - Google Patents

Abstract

Изобретение относится к области вычислительной техники. Технический результат - возможность выявления границ диапазона единичных бит, оценка ширины диапазона. Устройство содержит: М разрядов D0, …, D(M-l) группы входных данных из N разрядного двоичного числа, выходные (n+1) и n разрядные шины ширины диапазона QD, номера младшего единичного разряда QL и количества единичных бит QU соответственно, выходной флаг единичных бит QF1, триггеры пуска-останова TSS и единичных бит TU, два элемент И, счетчик групп, элемент ИЛИ, приоритетные шифраторы старшего и младшего единичных разрядов, модуль счета единиц, выходные регистры номера старшего единичного бита RGM и номера младшего единичного бита RGL, сумматоры разности SMS и единичных бит SMU, инкрементор INC, выходной регистр количества единичных бит, внешние входы остановки STOP и начала работы START, тактовых сигналов С и асинхронной установки в нулевое состояние CLR, внутренний флаг единичных бит в группе FU, внутренние m разрядные шины номера старшего и младшего единичного бита в М-разрядной группе, внутренние (n-m) и (m+1) разрядные шины номера группы BD и количества единичных бит в группе AU соответственно. 3 ил.

Description

ОБЛАСТЬ ТЕХНИКИ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Известно устройство для определения количества единиц (нулей) в двоичном числе (RU №2446442, МПК G06F 7/50, Н03К 21/00, заявлено 11.04.2011, опубликовано 27.03.2012, Бюл. №9), содержащее блок управляемой инверсии, состоящий из n-элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» (n - количество разрядов входного числа), элементы ИЛИ и модули, состоящие из элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, которые объединены в группы, состоящие из ярусов, и объединены в k-каскадов (k=]log₂n[), так, что каждый i-й каскад содержит g(i)=n/2ⁱ групп (i=1, …, k), каждая группа i-гo каскада разделена на j ярусов (j=l, i), при этом первый ярус каждой группы i-гo каскада содержит i модулей, а каждый j-й ярус каждой группы i-гo каскада (j=2, …, i,) содержит (i-j) модулей и элемент «ИЛИ».

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

Известно каскадное включение приоритетных шифраторов (Джон Ф. Уэйкерли. Проектирование цифровых устройств. /пер. с англ. Том 1. М.: Постмаркет, 2002, - 544 с., рис. 5.51, с. 440-445) в котором параллельно определяются приоритетные разряды в группах входного числа, между группами последовательно передается выходной сигнал разрешения работы, а выходы групповых шифраторов объединяются группой элементов ИЛИ-НЕ.

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

Известно устройство для детектирования диапазона единичных бит (RU №2717631 С1, МПК G06F 7/74, заявлено 07.11.2019, опубликовано 24.03.2020, Бюл. №9), содержащее N разрядов входной шины D - D1, D2, …, DN, N разрядов выходной шины Q - Q1, Q2, …, QN, первую группу из (N-2) элементов ИЛИ 1₁, 1₂, 1_(n-2), вторую группу из (N-2) элементов ИЛИ 2₁, 2₂, 2_(n-2) и группу из (N-2) элементов И 3₁, 3₂, …, 3_(n-2). Причем первая группа элементов ИЛИ 1₁, 1₂, …, 1_(n-2), объединенных в цепочку, формирует упорядоченную группу подряд идущих единиц в младших разрядах, вторая группа элементов ИЛИ 2₁, 2₂, …, 2_(n-2) формирует упорядоченную группу единиц в старших разрядах, а в группе элементов И 3₁, 3₂, …, 3_(n-2) осуществляется проверка единичных значений в одноименных разрядах упорядоченных групп единиц.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для детектирования границ диапазона единичных бит (RU №2717934 С1, МПК G06F 7/74, Н03К 21/00 заявлено 19.12.2019, опубликовано 27.03.2020, Бюл. №9), содержащее N разрядную входную шину D, выходную шину QR номера младшего разряда и выходную шину QL номера старшего разряда содержащие по М разрядов, где M=]log₂ (N+1)[(большее целое), группу из (N-1) элементов ИЛИ 1₁, 1₂, …, 1_(N-1), группу из (N-1) элементов ИЛИ-НЕ 2₁, 2₂, …, 2_(n-1), первый 3₁ и второй 3₂ блоки счета младших упорядоченных единиц, а также внутреннюю шину SR сдвига вправо и внутреннюю шину SL сдвига влево, которые содержат по N разрядов.

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

ЗАДАЧА ИЗОБРЕТЕНИЯ

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

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

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

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Указанный технический результат при осуществлении изобретения достигается тем, что устройство групповой структуры для детектирования границ диапазона единичных бит содержит М разрядов D0, …, D(M-1) группы входных данных из N разрядного двоичного числа, состоящего из L наборов по М разрядов в группе, где N=L*M, выходную n разрядную шину 20 номера старшего единичного разряда QM, где n=log₂N и N=2ⁿ, выходную (n+1) разрядную шину 21 ширины диапазона QD, выходную n разрядную шину 22 номера младшего единичного разряда QL, выходную (n+1) разрядную шину 23 количества единичных бит QU, выходной флаг 24 единичных бит QF1, первый триггер 1 пуска-останова TSS, второй триггер 2 единичных бит TU, первый элемент И 3, второй элемент И 4, счетчик групп 5, элемент ИЛИ 6, приоритетный шифратор старшего единичного разряда 7, приоритетный шифратор младшего единичного разряда 8, модуль счета единиц 9, первый выходной регистр 10 номера старшего единичного бита RGM, второй выходной регистр 11 номера младшего единичного бита RGL, первый сумматор 12 разности SMS, инкрементор INC 13, второй сумматор 14 единичных бит SMU, третий выходной регистр количества единичных бит 15, а также содержит внешний вход 16 остановки STOP, внешний вход 17 начала работы START, внешний вход 18 тактовых сигналов С, внешний вход 19 асинхронной установки в нулевое состояние CLR, внутренний флаг единичных бит в группе FU, внутреннюю m разрядную шину номера старшего единичного бита UM в М-разрядной группе, где m=log₂M, М=2^m, внутреннюю m разрядную шину номера младшего единичного бита UL в М-разрядной группе, внутреннюю (n-m) разрядную шину номера группы BD, внутреннюю (m+1) разрядную шину количества единичных бит в М-разрядной группе AU,

причем внешний вход С тактовых сигналов 18 и внешний вход CLR асинхронной установки в нулевое состояние 19 соединены с соответствующими входами С тактовых сигналов и входами CLR асинхронной установки в нулевое состояние первого триггера 1 пуска-останова TSS, второго триггера 2 единичных бит TU, счетчика групп 5, первого выходного регистра 10 номера старшего единичного бита RGM, второго выходного регистра 11 номера младшего единичного бита RGL и третьего выходного регистра количества единичных бит 15,

внешний вход 17 начала работы START соединен с входом S синхронной установки в единичное состояние первого триггера 1 пуска-останова TSS,

внешний вход 16 остановки STOP соединен с входом R синхронной установки в нулевое состояние триггера TSS пуска-останова 1,

причем М разрядов D0, …, D(M-1) группы входных данных соединены с соответствующими входами элемента ИЛИ 6, приоритетного шифратора старшего единичного разряда 7, приоритетного шифратора младшего единичного разряда 8 и модуля счета единиц 9,

при этом выход элемента ИЛИ 6 является внутренним флагом единичных бит FU и соединен со вторыми входами первого 3 и второго 4 элементов И и соединен с входом S синхронной установки в единичное состояние второго триггера 2 единичных бит TU, инверсный выход которого соединен с первым входом второго элемента И 4, выход которого соединен с входом разрешения работы СЕ второго выходного регистра 11 номера младшего единичного бита RGL, а прямой выход второго триггера 2 единичных бит TU соединен с первым входом увеличения инкрементора INC 13 и является выходным флагом единичных бит QF1,

причем выход триггера 1 пуска-останова TSS соединен с входом разрешения работы СЕ счетчика групп 5, с входом разрешения работы СЕ третьего выходного регистра 15 и с первым входом первого элемента И 3, выход которого соединен с входом разрешения работы СЕ первого выходного регистр 10 номера старшего единичного бита RGM,

кроме того выходы счетчика групп 5 являются разрядами внутренней шины номера группы BD, которая соединена с группами D-входов старших разрядов первого 10 выходного регистра RGM и второго 11 выходного регистра RGL, при этом выходы приоритетного шифратора старшего единичного разряда 7 являются разрядами внутренней шины номера старшего единичного бита UM в группе, которая соединена с группой D-входов младших разрядов первого 10 выходного регистра RGM, а выходы приоритетного шифратора младшего единичного разряда 8 являются разрядами внутренней шины номера младшего единичного бита UL в группе, которая соединена с группой D-входов младших разрядов второго 11 выходного регистра RGL,

причем выходы модуля счета единиц 9 являются разрядами внутренней шины количества единичных бит в группе AU, которая соединена с группой входов первого слагаемого второго сумматора 14 единичных бит SMU, у которого выход соединен с группой D-входов третьего выходного регистра количества единичных бит 15, выход которого соединен с группой входов второго слагаемого второго сумматора 14 единичных бит SMU,

кроме того выход первого 10 выходного регистра RGM соединен с группой прямых входов первого слагаемого первого сумматора 12 разности SMS, у которого инверсная группа входов второго слагаемого соединена с выходами второго 11 выходного регистра RGL, а на вход переноса CI подано значение логической единицы «1», выход первого сумматора 12 разности SMS соединен со второй группой входов слагаемого инкрементора INC 13,

причем разряды выходов первого выходного регистра 10 являются n разрядами выходной шины 20 номера старшего единичного разряда QM, разряды выходов инкрементора INC 13 и выход переноса СО инкрементора INC 13 являются соответствующими (n+1) разрядами выходной шины 21 ширины диапазона QD, разряды выходов второго выходного регистра 11 являются п разрядами выходной шины 22 номера младшего единичного разряда QL, разряды выходов третьего выходного регистра 15 являются (n+1) разрядами выходной шины 23 количества единичных бит QU.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

На фиг. 1 представлена функциональная схема предлагаемого устройства групповой структуры для детектирования границ диапазона единичных бит. На фиг. 2 и фиг. 3 приведены потактовые временные диаграммы работы для тестовых примеров при количестве разрядов входного двоичного числа N=16, количестве разрядов в группе входных данных М=4 и количестве групп L=4.

На фиг. 1-3 и в тексте введены следующие обозначения:

N - количество разрядов входного двоичного числа,

М - количество разрядов в группе входных данных,

L - количество групп во входном двоичном числе, где N=M*L,

D - входная шина;

D0, …, D3 (D(M-l) - двоичные разряды М-разрядной группы входной шины;

QM - n разрядная выходная шина номера старшего единичного разряда N разрядного двоичного числа, где N=2ⁿ, n=log₂N;

QL - n разрядная выходная шина номера младшего единичного разряда N разрядного двоичного числа;

QD - (n+1) разрядная выходная шина ширины диапазона N разрядного двоичного числа;

QU - (n+1) разрядная выходная шина количества (суммы) единичных бит в N разрядном двоичном числе;

QF1 - выходной флаг единичных бит;

UM - внутренняя m разрядная шина номера старшего единичного бита в М-разрядной группе, где M=2^m, m=log₂M;

UL - внутренняя m разрядная шина номера младшего единичного бита в М-разрядной группе;

BD - внутренняя (n-m) разрядная шина номера группы;

FU - внутренний флаг единичных бит в группе;

AU - внутренняя (m+1) разрядная шина количества единичных бит в М-разрядной группе;

С - тактовый вход;

СЕ - вход разрешения работы;

CLR - вход асинхронной установки в нулевое состояние;

R - вход синхронной установки в нулевое состояние;

S - вход синхронной установки в единичное состояние;

START - внешний вход начала работы;

STOP - внешний вход остановки;

AND - элемент И;

OR - элемент ИЛИ;

INC - инкрементор диапазона;

SM - сумматор;

CI - входной перенос сумматора;

СО - выходной перенос сумматора;

СТ - счетчик;

RG - регистр;

RGM - регистр старшего номера единичных бит;

RGL - регистр младшего номера единичных бит;

SMS - сумматор разности старшего и младшего номеров;

SMU - сумматор единичных бит;

Т - триггер;

TSS - триггер пуска-останова;

TU - триггер единичных бит.

1 - первый триггер пуска-останова TSS;

2 - второй триггер единичных бит TU;

3 - первый элемент И (AND);

4 - второй элемент И (AND);

5 - счетчик групп;

6 - элемент ИЛИ (OR);

7 - приоритетный шифратор старшего единичного разряда;

8 - приоритетный шифратор младшего единичного разряда;

9 - модуль счета единиц,

10 - первый выходной регистр номера старшего единичного бита RGM;

11 - второй выходной регистр номера младшего единичного бита RGL;

12 - первый сумматор разности старшего и младшего номеров SMS;

13 - инкрементор увеличения ширины диапазона INC;

14 - второй сумматор единичных бит SMU;

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

16 - внешний вход остановки STOP;

17 - внешний вход начала работы START;

18 - внешний вход тактовых сигналов С;

19 - внешний вход асинхронной установки в нулевое состояние CLR;

20 - n разрядная выходная шина номера старшего единичного разряда QM;

21 - (n+1) разрядная выходная шина ширины диапазона QD;

22 - n разрядная выходная шина номера младшего единичного разряда QL.

23 - (n+1) разрядная выходная шина количества (суммы) единичных бит QU;

24 - внешний флаг единичных бит QF1.

Предлагаемое устройство групповой структуры для детектирования границ диапазона единичных бит содержит М разрядов D0, …, D(M-1) группы входных данных из N разрядного двоичного числа, состоящего из L наборов по М разрядов в группе, где N=L*M, выходную n разрядную шину 20 номера старшего единичного разряда QM, где n=log₂N и N=2ⁿ, выходную (n+1) разрядную шину 21 ширины диапазона QD, выходную n разрядную шину 22 номера младшего единичного разряда QL, выходную (n+1) разрядную шину 23 количества единичных бит QU, выходной флаг 24 единичных бит QF1, первый триггер 1 пуска-останова TSS, второй триггер 2 единичных бит TU, первый элемент И 3, второй элемент И 4, счетчик групп 5, элемент ИЛИ 6, приоритетный шифратор старшего единичного разряда 7, приоритетный шифратор младшего единичного разряда 8, модуль счета единиц 9, первый выходной регистр 10 номера старшего единичного бита RGM, второй выходной регистр 11 номера младшего единичного бита RGL, первый 12 сумматор разности SMS, инкрементор INC 13, второй сумматор 14 единичных бит SMU, третий выходной регистр количества единичных бит 15, а также содержит внешний вход 16 остановки STOP, внешний вход 17 начала работы START, внешний вход 18 тактовых сигналов С, внешний вход 19 асинхронной установки в нулевое состояние CLR, внутренний флаг единичных бит в группе FU, внутреннюю m разрядную шину номера старшего единичного бита UM в М-разрядной группе, где m=log₂M, M=2^m, внутреннюю m разрядную шину номера младшего единичного бита UL в М-разрядной группе, внутреннюю (n-m) разрядную шину номера группы BD, внутреннюю (m+1) разрядную шину количества единичных бит в М-разрядной группе AU.

Первый триггер пуска-останова TSS 6 принимает единичное значение по фронту синхросигнала С между сигналами внешними сигналами начала работы START и остановки STOP. Флаг единичных бит FU принимает единичное значение при наличии единичных бит в М-разрядной группе входной шины D0, D2, …, D(M-l).

На первом сумматоре 12 разности SMS осуществляется вычитание номера разряда младшего единичного бита, передаваемого со второго 11 выходного регистра RGL, из номера разряда старшего единичного, передаваемого с первого 10 выходного регистра RGM. Инкрементор INC 13 увеличивает значение второго слагаемого на единицу при единичном значении на входе инкремента от второго триггера 2 единичных бит TU для учета в разности разрядов границ диапазона. Второй сумматор 14 единичных бит SMU и третий выходной регистр 15 количества единичных бит образуют накапливающий сумматор и осуществляют счет единиц по группам.

Внешний вход С тактовых сигналов 18 и внешний вход CLR асинхронной установки в нулевое состояние 19 соединены с соответствующими входами С тактовых сигналов и входами CLR асинхронной установки в нулевое состояние первого триггера 1 пуска-останова TSS, второго триггера 2 единичных бит TU, счетчика групп 5, первого выходного регистра 10 номера старшего единичного бита RGM, второго выходного регистра 11 номера младшего единичного бита RGL и третьего выходного регистра количества единичных бит 15.

Внешний вход 17 начала работы START соединен с входом S синхронной установки в единичное состояние первого триггера 1 пуска-останова TSS.

Внешний вход 16 остановки STOP соединен с входом R синхронной установки в нулевое состояние триггера TSS пуска-останова 1.

Причем М разрядов D0, …, D(M-1) группы входных данных соединены с соответствующими входами элемента ИЛИ 6, приоритетного шифратора старшего единичного разряда 7, приоритетного шифратора младшего единичного разряда 8 и модуля счета единиц 9.

Выход элемента ИЛИ 6 является внутренним флагом единичных бит FU и соединен со вторыми входами первого 3 и второго 4 элементов И и соединен с входом S синхронной установки в единичное состояние второго триггера 2 единичных бит TU. Инверсный выход второго триггера 2 единичных бит TU соединен с первым входом второго элемента И 4, выход которого соединен с входом разрешения работы СЕ второго выходного регистра 11 номера младшего единичного бита RGL. Прямой выход второго триггера 2 единичных бит TU соединен с первым входом увеличения инкрементора INC 13 и является выходным флагом единичных бит QF1.

Причем выход триггера 1 пуска-останова TSS соединен с входом разрешения работы СЕ счетчика групп 5, с входом разрешения работы СЕ третьего выходного регистра 15 и с первым входом первого элемента И 3, выход которого соединен с входом разрешения работы СЕ первого выходного регистр 10 номера старшего единичного бита RGM.

Выходы счетчика групп 5 являются разрядами внутренней шины номера группы BD, которая соединена с группами D-входов старших разрядов первого 10 выходного регистра RGM и второго 11 выходного регистра RGL. Выходы приоритетного шифратора старшего единичного разряда 7 являются разрядами внутренней шины номера старшего единичного бита UM в группе, которая соединена с группой D-входов младших разрядов первого 10 выходного регистра RGM. Выходы приоритетного шифратора младшего единичного разряда 8 являются разрядами внутренней шины номера младшего единичного бита UL в группе, которая соединена с группой D-входов младших разрядов второго 11 выходного регистра RGL.

Выходы модуля счета единиц 9 являются разрядами внутренней шины количества единичных бит в группе AU, которая соединена с группой входов первого слагаемого второго сумматора 14 единичных бит SMU, у которого выход соединен с группой D-входов третьего выходного регистра количества единичных бит 15, выход которого соединен с группой входов второго слагаемого второго сумматора 14 единичных бит SMU.

Выход первого 10 выходного регистра RGM соединен с группой прямых входов первого слагаемого первого сумматора 12 разности SMS, у которого инверсная группа входов второго слагаемого соединена с выходами второго 11 выходного регистра RGL, а на вход переноса CI подано значение логической единицы «1». Выход первого сумматора 12 разности SMS соединен со второй группой входов слагаемого инкрементора INC 13.

Разряды выходов первого выходного регистра 10 являются п разрядами выходной шины 20 номера старшего единичного разряда QM. Разряды выходов инкрементора INC 13 и выход переноса СО инкрементора INC 13 являются соответствующими (n+1) разрядами выходной шины 21 ширины диапазона QD. Разряды выходов второго выходного регистра 11 являются n разрядами выходной шины 22 номера младшего единичного разряда QL. Разряды выходов третьего выходного регистра 15 являются (n+1) разрядами выходной шины 23 количества единичных бит QU.

ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Принцип работы предлагаемого устройства состоит в следующем.

Предлагаемое устройство позволяет детектировать правый (младший) разряд и левый (старший) разряд входного N-разрядного двоичного числа, которые имеют единичное значение, и сформировать на выходах устройства номера младшего QL и старшего QM единичных разрядов, ширину диапазона единичных бит QD, количество (сумму) единичных бит QU, включая границы, и при наличии единичных бит установить внешний флаг единичных бит QF1=1. При отсутствии единичных значений в разрядах входного N-разрядного двоичного числа на выходах номеров QL и QM границ диапазона, ширины диапазона QD, суммы единичных бит QU устанавливаются нулевые значения, а также нулевое значение принимает внешний флаг наличия единичных бит QF1=0.

Входное N разрядное двоичное число без знака разбивается на L=N/M групп по М разрядов в каждой группе, где N=2ⁿ, n=log₂N, M=2^m, m=log₂M. Группы входных данных последовательно поступают на входы устройства, при этом М двоичных разрядов каждой из L групп параллельно поступают на соответствующие входы D0, …, D(M-1) устройства (D0 - младший разряд).

Работа устройства начинается по единичному сигналу START=1 и завершается по единичному сигналу остановки STOP=1, который поступает одновременно с кодом последней L-ой группы. Группы входных данных поступают в каждом такте по фронту синхросигнала С.

На каждом такте осуществляется поиск единичных бит в М-разрядной группе и формируются текущие номера старшего и младшего единичных разрядов, которые являются младшими разрядами текущих номеров. Одновременно осуществляется счет групп на счетчике 5, выходы которого являются старшими разрядами текущих номеров. Таким образом, полные текущие номера выявленных единичных разрядов в группе формируются объединением двух частей: старшая - двоичный номер группы со счтечика групп 5, младшая - номер разряда в группе. Одновременно в модуле счета единиц 9 проводится подсчет единичных разрядов в М-разрядной группе и счет текущего общего количества единичных бит во втором сумматоре 14 единичных бит SMU и третьем выходном регистре 15.

Приоритетный шифратор 7 осуществляет поиск старшей единицы во входной М-разрядной группе и формирует на выходе UM двоичный m-разрядный номер этого единичного разряда. Приоритетный шифратор 8 осуществляет поиск младшей единицы во входной М-разрядной группе и формирует на выходе UL двоичный m-разрядный номер этого единичного разряда. Коды на внутренних шинах UM и UL являются младшими m разрядами текущих номеров разрядов соответственно старшей и младшей единицы, которые поступают на младшие разряды D-входов соответственно первого 10 выходного регистра старшего номера RGM и второго 11 выходного регистра младшего номера RGL.

Счетчик групп 5 осуществляет счет групп и формирует на выходе двоичный код номера текущей группы, который передается на внутреннюю шину BD и далее на старшие разряды D-входы первого 10 выходного регистра старшего номера RGM и второго 11 выходного регистра младшего номера RGL.

Подсчет количества единичных разрядов во входной М-разрядной группе осуществляется модуль счета единиц 9 и на выходе AU формируется двоичный код количества (суммы) единичных бит в группе. Текущее количество (сумма) единичных бит во входном числе формируется на накопительном сумматоре, реализованном на втором 14 комбинационном сумматоре единичных бит SMU, и третьем выходном регистре 15.

Ширина диапазона единичных бит формируется на первом 12 сумматоре SMS, как разность между текущими номерами старшего и младшего единичных бит фиксируемых соответственно на первом 10 и втором 11 выходных регистрах. Ширина диапазона единичных бит с выхода первого 12 сумматора SMS далее увеличивается на единицу на инкременторе 13 INC, для коррекции в разности разрядов границ диапазона, и передается на (n+1) разрядную выходную шину ширины диапазона QD. При этом старшим разрядом шины QD является выход переноса СО инкрементора 13 INC.

На выходе элемента ИЛИ 6 формируется единичное значение при детектировании единичных значений во входной М-разрядной группе и устанавливается внутренний единичный флаг FU=1. Выход элемента ИЛИ 6 соединен со вторыми входами первого 3 и второго 4 элементов И и соединен с входом S синхронной установки в единичное состояние второго триггера 2 единичных бит TU, инверсный выход которого соединен с первым входом второго элемента И 4, выход которого соединен с входом разрешения работы СЕ второго выходного регистра 11. Прямой выход второго триггера 2 единичных бит TU является выходным флагом единичных бит QF1 и также соединен с входом увеличения на «1» инкрементора 13 INC. Выход первого 1 триггера пуска-останова TSS соединен с первым входом первого элемента И 3, который соединен с входом разрешения работы СЕ первого выходного регистра 10. Единичные значения на выходах первого элемента И 3 и второго элемента И 4 разрешают запись текущих полных значений номеров старшей и младшей единицы (границ диапазона) соответственно в первый 10 выходной регистр RGM и второй 11 выходной регистр RGL, на основании значений которых формируется текущее значение кода ширины диапазона QD на первом 12 сумматоре SMS и инкременторе 13 INC.

Выходы первого 10 выходного регистра RGM, второго 11 выходного регистра RGL, инкрементора INC 13 и третьего выходного регистра 15 являются выходами соответствующих выходных шин.

Таким образом, в предлагаемом устройстве на выходных шинах в каждом такте устанавливаются текущие значения номера старшего единичного разряда QM, номера младшего единичного разряда QL, ширины диапазона QD, количества (суммы) единичных бит QU и выходного флага единичных бит QF1. По единичному сигналу остановки STOP на соответствующих выходных шинах QM, QL, QD, QU и QF1 будут зафиксированы итоговые значения для входного N разрядного двоичного числа.

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

Перед началом работы подается сигнал на внешнем входе 19 асинхронной установки в нулевое состояние CLR, по которому в нулевые состояния устанавливаются первый триггер 1 пуска-останова TSS=0, второй триггер 2 единичных бит TU=0, счетчик групп 5 BD=0, выходные первый 10, второй 11 и третий 15 регистры.

Далее при единичном значении сигнала начала работы на внешнем 17 входе START=1 (такты 1 на фиг. 2 и фиг. 3 при N=16, М=4, L=4) на такте 2 по фронту тактового сигнала С на внешнем входе 18 в единичное состояние устанавливается первый 1 триггер пуска-останова TSS=1.

Далее в каждом такте 2-5, начиная с такта 2, на внешние входы устройства D0, …, D3(DM-1) параллельно поступают по М=4 разряда последовательных L=N/M=4 групп входного N=16 разрядного двоичного числа без знака (при этом n=log₂N=4, m=log₂M=2). При этом младший разряд D0 является первым (правым) разрядом каждой входной группы (на фиг. 2 и фиг. 3 младшие разряды показаны слева, старшие справа). Значения с входной шины D поступают на соответствующие входы приоритетного шифратора старшего единичного разряда 7, приоритетного шифратора младшего единичного разряда 8, элемента ИЛИ 6 и модуля счета единиц 9.

На каждом такте осуществляется поиск единичных бит в М-разрядной группе и при выявлении единичных значений приоритетный шифратор 7 формирует на выходе UM двоичный m-разрядный номер текущего старшего единичного разряда, приоритетный шифратор 8 формирует на выходе UL двоичный m-разрядный номер текущего младшего единичного разряда, на выходе элемента ИЛИ 6 при детектировании единичных значений во входной М-разрядной группе формируется единичное значение внутреннего единичного флага FU=1, модуль счета единиц 9 осуществляет подсчет единичных бит и на выходе AU формируется двоичный код количества (суммы) единичных бит в группе.

На фиг. 2 приведены два тестовых примера - тест №1 и тест №2, на фиг. 3 приведены также два тестовых примера - тест №3 и тест №4. На фиг. 2 в скобках указано представление значений в двоичном коде (2) или десятичном коде (10), а выходы триггеров TSS и TU, флагов единичных бит FU и QF1 и логических элементов 3 и 4 приведены в виде временных диаграмм.

В тесте №1 в такте 2 на входы D0, …, D3 поступает код нулевой группы 0001, содержащий только одну единицу (D3=1), поэтому на выходах приоритетного шифратора 7 формируется двоичный двухразрядный номер UM текущего старшего единичного разряда UM=3 и на выходах приоритетного шифратора 8 формируется двоичный двухразрядный номер UL текущего младшего единичного разряда UL=3, которые передаются на два младшие D-входа соответственно первого 10 выходного регистра старшего номера RGM и второго 11 выходного регистра младшего номера RGL. При этом на два старших D-входа первого 10 и второго 11 регистров передается код с внутренней шины групп BD=00, так как на счетчике групп 5 установлен код нулевой группы. При этом на D-входах первого 10 и второго 11 регистров устанавливаются коды: D-RGM=00 11 и D-RGL=00 11.

Кроме того на выходе модуля счета единиц 9 формируется двоичный код AU₍₁₀₎=1, который суммируется на втором 14 сумматоре единичных бит SMU с нулевым кодом на выходе третьего регистра 15 и на выходе сумматора устанавливается код SMU₍₁₀₎=l, который передается на D-входы третьего регистра 15, запись в который выполняется на каждом такте по фронту синхросигнала С при единичном значении первого 1 триггера пуска-останова TSS=1.

Одновременно на выходе элемента ИЛИ 6 формируется единичное значение внутреннего единичного флага FU=1. Поэтому далее единичные значения устанавливаются на выходах первого 3 и второго 4 элементов И.

В такте 3 теста №1 по фронту синхросигнала С, при единичных значениях на выходах первого элемента И 3 и второго элемента И 4, установленных в такте 2, осуществляется запись соответствующих текущих значений номеров старшего и младшего единичных разрядов и количество (сумма) единиц в выходные первый 10, второй 11 и третий 15 регистры соответственно, и передача этих значений на выходные шины: QM=3, QL=3, QU=1. Также в такте 3 по фронту синхросигнала в единичное состояние переключается второй триггер 2 единичных бит TU=1, на инверсном выходе которого формируется нулевое значение, и формируется единичное значение выходного флага единичных бит QF1=1. Далее по текущим значениям номеров старшего и младшего единичных разрядов на первом 12 сумматоре SMS=0000 и инкременторе 13 формируется код ширины диапазона INC₍₂₎=0001, который передается на выходную шину QD₍₁₀₎=l. Кроме того в такте 3 теста №1 по фронту синхросигнала С счетчик групп 5 переходит в следующее состояние и на внутренней шины групп устанавливается код BD₍₂₎=01, разряды которой являются двумя старшими разрядами текущего номера для первой группы, что соответствует коду со сдвигом на 2 разряда в сторону старших разрядов BD*2^+m ₍₁₀₎=4.

Одновременно в такте 3 теста №1 на входы D0, …, D3 поступает код следующей первой группы 1100, содержащий две младшие единицы (D0=1, D1=1), для которого аналогично такту 2 формируются двухразрядные коды номеров единичных разрядов UM=1 и UL=0, количество (сумма) единиц AU=2 и на выходе элемента ИЛИ 6 формируется единичное значение внутреннего единичного флага FU=1. При этом на D-входах первого 10 и второго 11 регистров устанавливаются коды: D-RGM=01 01 и D-RGL=01 00, а на выходе второго 14 сумматора единичных бит SMU=3.

В такте 4 теста №1 по фронту синхросигнала С, при единичном значении выходе первого элемента И 3, установленного в такте 3, осуществляется запись соответствующих текущих значений номера старшего единичного разряда и количество (сумма) единиц в выходные первый 10 и третий 15 регистры соответственно, и передача этих значений на выходные шины: QM=5, QU=3. Но так как нулевое значение установлено на выходе второго элемента И 4, то запись во второй 11 регистр не проводится и сохраняется код младшего разряда RGL=0011 (QL=3), установленный на такте 3. На следующих тактах запись во второй регистр 11 также не проводится, так как на инверсном выходе второго 2 триггера TU установлено (сохраняется) нулевое значение. Далее по текущим значениям номеров старшего и младшего единичных разрядов формируется код ширины диапазона INC(₂)=0011 (QD₍₁₀₎=3).

Кроме того в такте 4 теста №1 по фронту синхросигнала С счетчик групп 5 переходит в следующее состояние и на внутренней шины групп устанавливается код BD₍₂₎=10, разряды которой являются старшими разрядами текущего номера для второй группы, что соответствует коду со сдвигом на 2 разряда в сторону старших разрядов BD*2^+m ₍₁₀₎=8.

Одновременно в такте 4 теста №1 на входы D0, …, D3 поступает код второй группы 0111, содержащий три старшие единицы, для которого аналогично такту 3 формируются коды: UM=3, UL=1, AU=3, D-RGM=10 11, D-RGL=10 01 и SMU=6.

В такте 5 теста №1 по фронту синхросигнала С, при единичном значении на выходе первого элемента И 3, установленного в такте 4, осуществляется запись соответствующих текущих значений номера старшего единичного разряда и количество (сумма) единиц записываются выходные первый 10 и третий 15 регистры соответственно, и передача этих значений на выходные шины: QM=11, QU=6. Далее по текущим значениям номеров старшего и младшего единичных разрядов формируется код ширины диапазона INC₍₂₎=1001 (QD₍₁₀₎=9).

Одновременно в такте 5 теста №1 на входы D0, …, D3 поступает код третьей группы 0010, содержащий одну единицу (D2=1), для которого аналогично такту 3 формируются коды: UM=2, UL=2, AU=1, D-RGM=11 10, D-RGL=11 10 и SMU=7. Кроме того единичное значение установлено на внешнем 16 входе остановки STOP=1.

В такте 6 теста №1 по фронту синхросигнала С соответствующие коды записываются выходные регистры и формируется код ширины диапазона INC₍₂₎=1100 (QD₍₁₀₎=12). Одновременно по сигналу STOP=1 в нулевое состояние переключается первый 1 триггер пуска-останова TSS=0.

Таким образом, для теста №1 на выходных шинах устройства будут установлены коды границ единичных разрядов, ширины диапазона, количества единиц: QM=14, QL=3, QD=12, QU=7 и установлен внешний флаг единичных бит QF1=1.

Для теста №2 (фиг. 2), аналогично как в тесте №1, в такте 1 перед началом работы подают сигналы CLR и START=1.

В тесте №2 для кода нулевой группы D0, …, D3=0011 и кода первой группы D0, D3=0110 в тактах 2 и 3 формируются соответствующие коды аналогично как в тесте №1.

В такте 4 теста №2 на входы D0, D3 поступает код второй группы 0000 содержащий только нулевые значения. Поэтому нулевое значение устанавливается на выходе элемента ИЛИ 6, так как нет единичных бит во входной группе, и внутреннего флага FU=0, и далее нулевые значения формируются на выходе первого элемента И 3 и на выходе второго элемента И 4. Поэтому в такте 5 по фронту синхросигнала С не выполняется запись в выходные первый 10 и второй 11 регистры и сохраняются значения на соответствующих выходных шинах. Запись в третий регистр 15 выполняется, но значение тоже сохраняется, так как во второй входной группе нет единиц AU=0.

В тактах 5 и 6 теста №2 аналогично тесту №1 формируются соответствующие коды, и осуществляется запись в выходные регистры.

В результате для теста №2 на выходных шинах устройства будут установлены коды границ единичных разрядов, ширины диапазона, количества единиц: QM=12, QL=2, QD=11, QU=5, и установлен внешний флаг единичных бит QF1=1.

В тесте №3 (фиг. 3) в тактах 2 и 3 на входы D0, D3 для нулевой и первой групп поступает код 0000 содержащий только нулевые значения. Поэтому нулевое значение устанавливается на выходе элемента ИЛИ 6, так как нет единичных бит во входной группе, и внутреннего флага FU=0, и далее нулевые значения формируются на выходе первого элемента И 3 и на выходе второго элемента И 4. Поэтому в тактах 3 и 4 по фронту синхросигнала С не выполняется запись в выходные первый 10 и второй 11 регистры и сохраняются нулевые значения на соответствующих выходных шинах. Запись в третий регистр 15 выполняется, но нулевое значение тоже сохраняется, так как во входных группах нет единиц AU=0.

В тактах 4-6 теста №3 аналогично тесту №1 формируются соответствующие коды для второй т третьей входных групп на входах D0, …, D3, и осуществляется запись в выходные регистры.

В результате для теста №3 на выходных шинах устройства будут установлены коды границ единичных разрядов, ширины диапазона и количества единиц: QМ=13, QL=9, QD=5, QU=4, и установлен внешний флаг единичных бит QF1=1.

В такте 2 теста №4 (фиг. 3) на входы D0, …, D3 поступает код нулевой группы 1000 содержащий только одну единицу в младшем нулевом разряде D0=1. Поэтому формируются нулевые коды номеров старшего и младшего единичных разрядов UM=0 и UL=0. При этом одновременно на выходе элемента ИЛИ 6 формируется единичное значение внутреннего единичного флага FU=1. Поэтому далее единичные значения устанавливаются на выходах первого 3 и второго 4 элементов И.

В такте 3 теста №4 осуществляется запись соответствующих кодов в выходные регистры. Также в такте 3 по фронту синхросигнала в единичное состояние переключается второй триггер 2 единичных бит TU=1, на инверсном выходе которого формируется нулевое значение, и формируется единичное значение выходного флага единичных бит QF1.

В такте 3 теста №4 на входы D0, …, D3 поступает код первой группы 0000 содержащий только нулевые значения, для которого аналогично такту 4 теста №2 формируется флаг FU=0, не выполняется запись в выходные регистры и сохраняются их значения.

В тактах 4 и 5 теста №4 на входы D0, D3 поступают коды второй группы D0, D3=0100 и кода третьей группы D0, …, D3=0001. При этом в третьей группе единичный разряд старший третий D3=l (старший пятнадцатый разряд для входного N=16 разрядного двоичного числа). В тактах 4 и 5 формируются соответствующие коды аналогично как тесте №1 и осуществляется запись в выходные регистры. При этом в выходных регистрах будут установлены следующие коды: QM=15, QL=0, QU=3. Далее по текущим значениям номеров старшего и младшего единичных разрядов на первом 12 сумматоре формируется код SMS=1111 и на инкременторе 13 формируется код ширины диапазона INC(2)=0000. Но при этом формируется единичное значение на выходе переноса СО=1, который передается на старший (n+1) разряд выходной шины QD и устанавливается код QD₍₁₀₎=16, соответствующий диапазону между нулевым и пятнадцатым разрядами для входного N=16 разрядного двоичного числа.

В результате для теста №4 на выходных шинах устройства будут установлены коды границ единичных разрядов, ширины диапазона, количества единиц: QM=15, QL=0, QD=16, QU=3 и установлен внешний флаг единичных бит QF1=1.

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

Claims (11)

1. Устройство групповой структуры для детектирования границ диапазона единичных бит содержит М разрядов D0, …, D(M-1) группы входных данных из N разрядного двоичного числа, состоящего из L наборов по М разрядов в группе, где N=L*M, выходную n разрядную шину 20 номера старшего единичного разряда QM, где n=log₂N и N=2ⁿ, выходную (n+1) разрядную шину 21 ширины диапазона QD, выходную n разрядную шину 22 номера младшего единичного разряда QL, выходную (n+1) разрядную шину 23 количества единичных бит QU, выходной флаг 24 единичных бит QF1, первый триггер 1 пуска-останова TSS, второй триггер 2 единичных бит TU, первый элемент И 3, второй элемент И 4, счетчик групп 5, элемент ИЛИ 6, приоритетный шифратор старшего единичного разряда 7, приоритетный шифратор младшего единичного разряда 8, модуль счета единиц 9, первый выходной регистр 10 номера старшего единичного бита RGM, второй выходной регистр 11 номера младшего единичного бита RGL, первый сумматор 12 разности SMS, инкрементор INC 13, второй сумматор 14 единичных бит SMU, третий выходной регистр количества единичных бит 15, а также содержит внешний вход 16 остановки STOP, внешний вход 17 начала работы START, внешний вход 18 тактовых сигналов С, внешний вход 19 асинхронной установки в нулевое состояние CLR, внутренний флаг единичных бит в группе FU, внутреннюю m разрядную шину номера старшего единичного бита UM в М-разрядной группе, где m=log₂M, M=2^m, внутреннюю m разрядную шину номера младшего единичного бита UL в М-разрядной группе, внутреннюю (n-m) разрядную шину номера группы BD, внутреннюю (m+1) разрядную шину количества единичных бит в М-разрядной группе AU,
2. причем внешний вход С тактовых сигналов 18 и внешний вход CLR асинхронной установки в нулевое состояние 19 соединены с соответствующими входами С тактовых сигналов и входами CLR асинхронной установки в нулевое состояние первого триггера 1 пуска-останова TSS, второго триггера 2 единичных бит TU, счетчика групп 5, первого выходного регистра 10 номера старшего единичного бита RGM, второго выходного регистра 11 номера младшего единичного бита RGL и третьего выходного регистра количества единичных бит 15,
3. внешний вход 17 начала работы START соединен с входом S синхронной установки в единичное состояние первого триггера 1 пуска-останова TSS,
4. внешний вход 16 остановки STOP соединен с входом R синхронной установки в нулевое состояние триггера TSS пуска-останова 1,
5. причем М разрядов D0, …, D(M-1) группы входных данных соединены с соответствующими входами элемента ИЛИ 6, приоритетного шифратора старшего единичного разряда 7, приоритетного шифратора младшего единичного разряда 8 и модуля счета единиц 9,
6. при этом выход элемента ИЛИ 6 является внутренним флагом единичных бит FU и соединен со вторыми входами первого 3 и второго 4 элементов И и соединен с входом S синхронной установки в единичное состояние второго триггера 2 единичных бит TU, инверсный выход которого соединен с первым входом второго элемента И 4, выход которого соединен с входом разрешения работы СЕ второго выходного регистра 11 номера младшего единичного бита RGL, а прямой выход второго триггера 2 единичных бит TU соединен с первым входом увеличения инкрементора INC 13 и является выходным флагом единичных бит QF1,
7. причем выход триггера 1 пуска-останова TSS соединен с входом разрешения работы СЕ счетчика групп 5, с входом разрешения работы СЕ третьего выходного регистра 15 и с первым входом первого элемента И 3, выход которого соединен с входом разрешения работы СЕ первого выходного регистра 10 номера старшего единичного бита RGM,
8. кроме того, выходы счетчика групп 5 являются разрядами внутренней шины номера группы BD, которая соединена с группами D-входов старших разрядов первого 10 выходного регистра RGM и второго 11 выходного регистра RGL, при этом выходы приоритетного шифратора старшего единичного разряда 7 являются разрядами внутренней шины номера старшего единичного бита UM в группе, которая соединена с группой D-входов младших разрядов первого 10 выходного регистра RGM, а выходы приоритетного шифратора младшего единичного разряда 8 являются разрядами внутренней шины номера младшего единичного бита UL в группе, которая соединена с группой D-входов младших разрядов второго 11 выходного регистра RGL,
9. причем выходы модуля счета единиц 9 являются разрядами внутренней шины количества единичных бит в группе AU, которая соединена с группой входов первого слагаемого второго сумматора 14 единичных бит SMU, у которого выход соединен с группой D-входов третьего выходного регистра количества единичных бит 15, выход которого соединен с группой входов второго слагаемого второго сумматора 14 единичных бит SMU,
10. кроме того, выход первого 10 выходного регистра RGM соединен с группой прямых входов первого слагаемого первого сумматора 12 разности SMS, у которого инверсная группа входов второго слагаемого соединена с выходами второго 11 выходного регистра RGL, а на вход переноса CI подано значение логической единицы «1», выход первого сумматора 12 разности SMS соединен со второй группой входов слагаемого инкрементора INC 13,
11. причем разряды выходов первого выходного регистра 10 являются n разрядами выходной шины 20 номера старшего единичного разряда QМ, разряды выходов инкрементора INC 13 и выход переноса СО инкрементора INC 13 являются соответствующими (n+1) разрядами выходной шины 21 ширины диапазона QD, разряды выходов второго выходного регистра 11 являются n разрядами выходной шины 22 номера младшего единичного разряда QL, разряды выходов третьего выходного регистра 15 являются (n+1) разрядами выходной шины 23 количества единичных бит QU.

Images