УСТРОЙСТВО ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНОЙ СТРУКТУРЫ ДЛЯ ДЕТЕКТИРОВАНИЯ ГРУПП НУЛЕВЫХ И ЕДИНИЧНЫХ БИТ И ОПРЕДЕЛЕНИЕ ИХ КОЛИЧЕСТВА
DEVICE OF PARALLEL-SERIAL STRUCTURE FOR DETECTION OF GROUPS OF ZERO AND SINGLE BITS AND DETERMINATION OF THEIR NUMBER

ОБЛАСТЬ ТЕХНИКИ
Изобретение относится к области вычислительной техники, в частности к устройствам обработки данных, и может быть использовано для построения средств автоматики и функциональных узлов систем управления, для анализа свойств генераторов псевдослучайных последовательностей двоичных чисел, а также для обработки результатов физических экспериментов.
ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ
Известны система и способ подсчета начальных нулевых разрядов и подсчета начальных единичных разрядов в цифровом процессоре сигналов (RU №2409837 С2, МПК G06F 7/74, заявлен 27.07.2006, опубликовано 20.01.2011, Бюл. №2) в котором определяется количество разрядов для различных размеров слов данных. В устройстве проводится расширение входных данных знаком до временного шестидесятичетырехразрядного слова данных. При подсчете нулевых разрядов проводится инвертирование разрядов слова. Для подсчета начальных разрядов используется двоичный счетчик.
Недостатком данного устройства является низкое быстродействие, а также подсчет только начальных нулевых разрядов и начальных единичных разрядов в цифровом
2
Известно устройство последовательного типа для детектирования групп нулевых и единичных бит и определение их количества (RU №2680759, МПК G06F 7/74, заявлено 16.02.2018, опубликовано 26.02.2019, Бюл. №6), содержащее внешний вход данных DI, группу внешних выходов данных QO, группу внешних выходов количества групп QG, группу внешних выходов количества нулей QZ, группу внешних выходов количества единиц QU, группу внешних выходов «разность единиц и нулей» QZU, первый RS-триггер пуска-останова TSS 1, блок детектора единиц и нулей 2, третий D-триггер разрешения счета групп ТСЕ 7, третий элемент И 8, первый счетчик групп CG 9, второй счетчик бит СВ 10, выходной буфер ОВ 11, четвертый 12, пятый 13 и шестой 14 элементы И, третий счетчик нулей CZ 15, четвертый счетчик единиц CU 16, пятый реверсивный счетчик нулей-единиц CZU 17 и блок преобразователя кода разности 18, причем блок детектора единиц и нулей 2 состоит из первого 3 и второго 4 элементов И с одним инверсным входом, элемента ИЛИ 5 и второго D-триггера управления битами TU 6 и содержит три выхода, а блок преобразователя кода разности 18 содержит группу из (М-2) элементов ИЛИ 19, группу из (М-1) элементов И 20 и группу из (М-1) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 21, где M=[logN]+1 (меньшее целое), а N - размерность длины входной последовательности данных, причем первый счетчик групп CG 9, второй счетчик бит СВ 10, выходной буфер OB 11, третий счетчик нулей CZ 15 и четвертый счетчик единиц CU 16 имеют разрядность М, а пятый реверсивный счетчик нулей-единиц CZU 17 имеет разрядность (М+1), а также введены внешние флаги готовности результата FE, «Буфер заполнен» FF, «Буфер пуст» FZ и флаг «нулей больше единиц» F01.
Недостатком данного устройства является линейное увеличение временных затрат при увеличении разрядности входной информации.
2
1
2
L
1
2
L
1
2
(M-1)
v
1
2
(M-v)
1
2
(M-v)
1
2
(M-1)
1
2
M
ij
(i-1)
(i-1)
(i-2)
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство групповой структуры для детектирования групп нулевых и единичных бит и определение их количества (RU №2680762, МПК G06F 7/74, заявлено 13.04.2018, опубликовано 26.02.2019, Бюл. №6), содержащее N разрядов входного двоичного числа D1, D2, …, DN, которые разделены на L групп по М разрядов в группе (N=L*M), Z ступеней блоков элементов, где Z=]logL[+1 (большее целое), причем первая ступень содержит L блоков элементов 1, 1, …, 1 первого типа, а каждая i-ая ступень, содержит по L/2 блоков элементов 2ij второго типа, где i=2, 3, …, Z, j=1, 2, …, L/2, каждый блок элементов 1, 1, …, 1 первого типа первой ступени содержит (М-1) каскадов формирователей упорядоченных двоичных чисел 3, 3, …, 3, которые объединены в пирамидальную структуру, причем каждый v-й каскад 3 (v=1, …, (М-1)) содержит группу из (M-v) элементов ИЛИ 4, 4, …, 4, группу из (M-v) элементов «ИСКЛЮЧАЮЩЕЕ ИЛИ» 5, 5, …, 5, элемент ИЛИ с одним инверсным входом 6, группу из (М-1) модулей счета младших упорядоченных единиц 7, 7, …, 7, первую группу из М сумматоров 8, 8, …, 8, модуль счета единиц 9 и второй многогрупповой сумматор 10, каждый блок элементов 2 второго типа содержит третью группу из (М*2+1) сумматоров 11, четвертый сумматор 12, модуль сдвига групп 13, модуль формирования кода сдвига и кода общего количества групп 14, который содержит первый 15 и второй 16 элементы И с одним инверсным входом, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 17, пятый 18, шестой 19 и седьмой 20 сумматоры.
Недостатками данного устройства являются большие аппаратные затраты на реализацию каскадов формирователя упорядоченных двоичных чисел, модулей счета младших упорядоченных единиц и групп сумматоров, а также линейное увеличение аппаратных средств при увеличении разрядности входной информации.
ЗАДАЧА ИЗОБРЕТЕНИЯ
Задачей изобретения является разработка аппаратных средств для исследования свойств генераторов псевдослучайных последовательностей двоичных чисел, а также для обработки результатов физических экспериментов.
При анализе генераторов псевдослучайных последовательностей двоичных чисел устройство предназначено для выявления групп (рядов) подряд идущих единичных и нулевых бит, определение количества бит в группах, общего количества групп и общего количества единичных и нулевых бит.
При обработке результатов физических экспериментов устройство предназначено для выявления событий (групп единичных бит) и интервалов между событиями (групп нулевых бит), определение их длительности и определение общего количества и длительности событий.
Техническим результатом изобретения является расширение арсенала средств того же назначения, в части возможности выявления групп единичных и нулевых бит в двоичных числах, а также простое увеличение разрядности входной информации при сокращении аппаратных затрат.
КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ
Указанный технический результат при осуществлении изобретения достигается тем, что устройство параллельно-последовательной структуры для детектирования групп нулевых и единичных бит и определение их количества содержит М разрядов D1, …, DM набора входных данных из N разрядного двоичного числа, состоящего из L наборов по М разрядов в наборе, где N=L*M, N внешних выходов групп бит QG1, …, QGN, группу внешних выходов общего количества групп QК, внешний выход левого (первого) бита QLB, группу внешних выходов количества единичных бит QU, группу внешних выходов количества нулевых бит QZ,
модуль FК детектирования групп 1, первый триггер ТЕВ разрешения приема 2, триггер TLB левого (первого) бита 3, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, элемент И с одним инверсным входом 5, первый модуль SF_1 сдвига групп 6, первый сумматор SM_G бит в группе 7, вычитатель SB 8, второй модуль SF_2 сдвига групп 9, второй сумматор SM_К количества групп 10, третий сумматор SM_U количества единичных бит 11, триггер ТРО пуска-останова 12, регистр RG_G групп бит 13, регистр RG_К количества групп 14, регистр RG_U количества единичных бит 15, третий модуль SF_3 сдвига групп 16, четвертый сумматор SM_N дополнения 17, пятый сумматор SM_Z количества нулевых бит 18, второй триггер TEQ разрешения приема 19, первый выходной буферный регистр кодов групп 20, второй выходной буферный регистр общего количества групп 21, выходной триггер левого (первого) бита входных данных 22, третий выходной буферный регистр количества единичных бит 23, четвертый выходной буферный регистр количества нулевых бит 24,
а также введены внешний вход С тактовых сигналов 25, внешний вход R синхронной установки в нулевое состояние 26, внешний вход начала работы START и внешний вход остановки STOP, внутренняя шина общего количества групп KG и внутренний флаг декрементации FD,
причем внешний вход С тактовых сигналов 25 и внешний вход R синхронной установки в нулевое состояние 26 соединены с соответствующими входами С тактовых сигналов и входами R синхронной установки в нулевое состояние первого триггера ТЕВ разрешения приема 2, триггера TLB левого (первого) бита 3, второго триггера TEQ разрешения приема 19, первого выходного буферного регистра кодов групп 20, второго выходного буферного регистра общего количества групп 21, выходного триггера левого (первого) бита входных данных 22, третьего выходного буферного регистра количества единичных бит 23, четвертого выходного буферного регистра количества нулевых бит 24, а внешний вход С тактовых сигналов 25 также соединен с соответствующими входами С тактовых сигналов регистра RG_G групп бит 13, регистра RG_К количества групп 14, регистра RG_U количества единичных бит 15 и триггера ТРО пуска-останова 12, у которого второй вход R синхронной установки в нулевое состояние соединен с внешним входом R синхронной установки в нулевое состояние 26,
внешний вход начала работы START соединен с входом S синхронной установки в единичное состояние триггера ТРО пуска-останова 12, с информационным D-входом первого триггера ТЕВ разрешения приема 2 и входами R синхронной установки в нулевое состояние регистра RG_G групп бит 13, регистра RG_К количества групп 14, регистра RG_U количества единичных бит 15,
внешний вход остановки STOP соединен с первым входом R синхронной установки в нулевое состояние триггера ТРО пуска-останова 12 и с информационным D-входом второго триггера TEQ разрешения приема 19,
кроме того выход триггера ТРО пуска-останова 12 соединен с входами СЕ разрешения работы регистра RG_G групп бит 13, регистра RG_К количества групп 14 и регистра RG_U количества единичных бит 15, а выход второго триггера TEQ разрешения приема 19 соединен с входами СЕ разрешения работы первого выходного буферного регистра кодов групп 20, второго выходного буферного регистра общего количества групп 21, выходного триггера левого (первого) бита входных данных 22, третьего выходного буферного регистра количества единичных бит 23, четвертого выходного буферного регистра количества нулевых бит 24,
причем М разрядов D1, …, DM набора входных данных соединены с соответствующими одноименными входами модуля FК детектирования групп 1, а также левый (первый) бит D1 соединен с информационным D-входом триггера TLB левого (первого) бита 3 и соединен со вторым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, выходы групп G1, …, GM модуля FК детектирования групп 1 соединены с соответствующими одноименными входами групп первого модуля SF_1 сдвига групп 6, выход группы К количества групп бит соединен со второй группой входов уменьшаемого вычитателя SB 8, а выход группы U количества единичных бит соединен с группой входов первого слагаемого третьего сумматора SM_U количества единичных бит 11,
кроме того выход первого триггера ТЕВ разрешения приема 2 соединен с первым инверсным входом элемента И с одним инверсным входом 5 и с входом СЕ разрешения работы триггера TLB левого (первого) бита 3, выход которого соединен с информационным D-входом выходного триггера левого (первого) бита входных данных 22 и третьим входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, выход которого соединен со вторым прямым входом элемента И с одним инверсным входом 5, выход которого является внутренним флагом декрементации FD и соединен с входом управления сдвигом первого модуля SF_1 сдвига групп 6 и входом вычитания единицы «-1» вычитателя SB 8,
причем у первого SF_1 модуля сдвига групп 6 первая группа выходов соединена с группой входов второго слагаемого первого сумматора SM_G бит в группе 7, а группы выходов, начиная со второй до (М+1)-й групп выходов, соединены с соответствующими информационными группами входов второго SF_2 модуля сдвига групп 9, начиная с (N-M+1)-й до N-й групп входов, N групп выходов второго SF_2 модуля сдвига групп 9 соединены с соответствующими одноименными группами входов регистра RG_G групп бит 13, N групп выходов которого соединены с соответствующими одноименными группами входов третьего SF_3 модуля сдвига групп 16, у которого N групп выходов соединены с соответствующими одноименными группами входов первого выходного буферного регистра кодов групп 20, выходы которого являются N внешними выходами групп бит QG1, ..., QGN,
кроме того у регистра RG_G групп бит 13 выходы групп, начиная с (М+1)-й группы до (N-1)-й группы, соединены с группами входов второго SF_2 модуля сдвига групп 9, начиная с первой до (N-M-1)-й групп входов, а N-я группа выходов регистра RG_G групп бит 13 соединена с группой входов первого слагаемого первого сумматора SM_G бит в группе 7, выход которого соединен с (N-M)-й группой входов второго SF_2 модуля сдвига групп 9, у которого группа входов задания кода сдвига соединена с выходом вычитателя SB 8, который также соединен с группой входов первого слагаемого второго сумматора SM_К количества групп 10, выход которого соединен с группой информационных входов регистра RG_K количества групп 14, выход которого является внутренней шиной общего количества групп KG, которая соединена с группой входов второго слагаемого второго сумматора SM_К количества групп 10, с группой инверсных входов второго слагаемого четвертого сумматора SM_N дополнения 17 и с группой информационных входов второго выходного буферного регистра общего количества групп 21, выходы которого являются группой внешних выходов общего количества групп QК, а младший нулевой разряд kg0 внутренней шины KG общего количества групп также соединен также с первым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4,
причем на группу входов первого слагаемого четвертого сумматора SM_N дополнения 17 подано значение кода числа «N», на вход переноса CI подано значение логической единицы «1», а выход соединен с группой входов задания кода сдвига третьего SF_3 модуля сдвига групп 16,
кроме того, выход третьего сумматора SM_U количества единичных бит 11 соединен с группой информационных входов регистра RG_U количества единичных бит 15, выход которого соединен с группой входов второго слагаемого третьего сумматора SM_U количества единичных бит 11, с группой информационных входов третьего выходного буферного регистра общего количества групп 23 и с группой инверсных входов второго слагаемого пятого сумматора SM_Z количества нулевых бит 18, у которого на группу входов первого слагаемого подано значение кода числа «N», на вход переноса CI подано значение логической единицы «1, а выход соединен с группой информационных входов четвертого выходного буферного регистра количества нулевых бит 24,
причем группа выходов третьего выходного буферного регистра общего количества групп 23 является группой внешних выходов количества единичных бит QU, а группа выходов четвертого выходного буферного регистра количества нулевых бит 24 является группой внешних выходов количества нулевых бит QZ.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
На фиг. 1 представлена функциональная схема предлагаемого устройства. На фиг. 2 приведена потактовая временная диаграмма работы при количестве разрядов входного двоичного числа N=16, количестве разрядов в наборе входных данных М=4 и количестве наборов во входном двоичном L=4. В таблице 1 приведены таблицы истинности для формирования значений разрядов соответствующих двоичных кодов групп G1, …, GM, К и U при количестве разрядов в двоичном наборе М=2. В таблице 2 приведены таблицы истинности для формирования значений разрядов соответствующих двоичных кодов групп G1, …, GM, К и U при количестве разрядов в двоичном наборе М=4. В таблице 3 приведены значения функции для флага декрементации FD.
На фиг. 1, фиг. 2, в таблицах и в тексте приняты следующие обозначения:
N - количество разрядов входного двоичного числа,
М - количество разрядов в наборе входных данных,
L - количество наборов во входном двоичном числе, где N=M*L,
D1, …, DM - разряды набора входных данных,
FК - модуль детектирования групп во входном наборе,
G1, ..., GM - группы единичных и нулевых бит во входном наборе D1, …, DM,
0
G - группы нулевых бит,
1
G - группы единичных бит,
K - группа общего количества (суммы) групп единичных и нулевых бит во входном наборе D1, …, DM,
U - группа количества (суммы) единичных бит во входном наборе D1, …, DM,
FD - внутренний флаг декрементации кода суммы К общего количества групп во входном наборе D1, …, DM,
KG - внутренняя шина общего количества (суммы) групп,
kg0 - младший нулевой разряд внутренней шины KG общего количества групп,
SB - вычитатель (декрементор),
SM_G - сумматор бит в группе,
SM_К - сумматор количества (суммы) групп,
SM_N - сумматор дополнения количества групп до N,
SM_U - сумматор количества (суммы) единичных бит,
SM_Z - сумматор количества (суммы) нулевых бит,
CI - вход переноса сумматора,
SF_1 - первый модуль сдвига групп,
O_SF_1 - выход первого модуля сдвига групп SF_1,
SF_2 - второй модуль сдвига групп,
I_SF_2 - вход второго модуля сдвига групп SF_2,
O_SF_2 - выход второго модуля сдвига групп SF_2,
SF_3 - третий модуль сдвига групп,
O_SF_3 - выход третьего модуля сдвига групп SF_3,
С - тактовый вход,
СЕ - вход разрешения работы,
R - вход синхронной установки в нулевое состояние,
S - вход синхронной установки в единичное состояние,
START - внешний вход начала работы,
STOP - внешний вход остановки,
Т - триггер,
ТЕВ - триггер разрешения приема левого (первого) бита D1 входного числа,
TEQ - триггер разрешения приема в выходные буферные регистры,
TLB - триггер левого (первого) бита D1 входного числа,
ТРО - триггер пуска-останова,
RG - выходной буферный регистр,
RG_G - регистр групп бит,
RG_K - регистр количества (суммы) групп,
RG_U - регистр количества (суммы) единичных бит,
QG1, …, QGN - внешние выходы групп бит,
QК - группа внешних выходов общего количества (суммы) групп,
QLB - внешний выход левого (первого) бита D1 входного числа,
QU - группа внешних выходов количества (суммы) единичных бит,
QZ - группа внешних выходов количества (суммы) нулевых бит,
1 - модуль детектирования групп FК,
2 - первый триггер разрешения приема левого (первого) бита ТЕВ,
3 - триггер левого (первого) бита TLB,
4 - элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR),
5 - элемент И с одним инверсным входом,
6 - первый модуль сдвига групп SF_1,
7 - первый сумматор бит в группе SM_G,
8 - вычитатель (декрементор) SB,
9 - второй модуль сдвига групп SF_2,
10 - второй сумматор количества (суммы) групп SM_К,
11 - третий сумматор количества (суммы) единичных бит SM_U,
12 - триггер пуска-останова ТРО,
13 - регистр групп бит RG_G,
14 - регистр количества (суммы) групп RG_К,
15 - регистр количества (суммы) единичных бит RG_ U,
16 - третий модуль сдвига групп SF_3,
17 - четвертый сумматор SM_N дополнения количества групп до N,
18 - пятый сумматор количества (суммы) нулевых бит SM_Z,
19 - второй триггер разрешения приема в выходные буферные регистры TEQ,
20 - первый выходной буферный регистр кодов групп QG1, …, QGN,
21 - второй выходной буферный регистр общего количества групп QК,
22 - выходной триггер левого (первого) бита входных данных QLB,
23 - третий выходной буферный регистр количества (суммы) единичных бит QU,
24 - четвертый выходной буферный регистр количества (суммы) нулевых бит QZ,
25 - внешний вход тактовых сигналов С,
26 - внешний вход синхронной установки в нулевое состояние R.
Предлагаемое устройство параллельно-последовательной структуры для детектирования групп нулевых и единичных бит и определение их количества в N разрядном двоичном числе, которое разделено на L наборов по М разрядов в наборе (N=L*M), содержит М разрядов D1, …, DM набора входных данных, N внешних выходов групп бит QG1, …, QGN, группу внешних выходов общего количества групп QК, внешний выход левого (первого) бита QLB, группу внешних выходов количества единичных бит QU, группу внешних выходов количества нулевых бит QZ. Наборы входных данных поступают последовательно, а М разрядов каждого набора поступают параллельно на соответствующие внешние входы D1, …, DM.
Кроме того, предлагаемое устройство также содержит модуль FК детектирования групп 1, первый триггер ТЕВ разрешения приема левого (первого) бита 2, триггер TLB левого (первого) бита 3, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, элемент И с одним инверсным входом 5, первый модуль SF_1 сдвига групп 6, первый сумматор SM_G бит в группе 7, вычитатель SB 8, второй модуль SF_2 сдвига групп 9, второй сумматор SM_К количества групп 10, третий сумматор SM_U количества единичных бит 11, триггер ТРО пуска-останова 12, регистр RG_G групп бит 13, регистр RG_К количества групп 14, регистр RG_U количества единичных бит 15, третий модуль SF_3 сдвига групп 16, четвертый сумматор SM_N дополнения 17, пятый сумматор SM_Z количества нулевых бит 18, второй триггер TEQ разрешения приема в выходные буферные регистры 19, первый выходной буферный регистр кодов групп 20, второй выходной буферный регистр общего количества групп 21, выходной триггер левого (первого) бита входных данных 22, третий выходной буферный регистр количества единичных бит 23, четвертый выходной буферный регистр количества нулевых бит 24.
В предлагаемое устройство также введены внешний вход С тактовых сигналов 25, внешний вход R синхронной установки в нулевое состояние 26, внешний вход начала работы START и внешний вход остановки STOP, внутренняя шина общего количества групп KG и внутренний флаг декрементации FD.
Внешний вход С тактовых сигналов 25 и внешний вход R синхронной установки в нулевое состояние 26 соединены с соответствующими входами С тактовых сигналов и входами R синхронной установки в нулевое состояние первого триггера ТЕВ разрешения приема левого (первого) бита 2, триггера TLB левого (первого) бита 3, второго триггера TEQ разрешения приема в выходные буферные регистры 19, первого выходного буферного регистра кодов групп 20, второго выходного буферного регистра общего количества групп 21, выходного триггера левого (первого) бита входных данных 22, третьего выходного буферного регистра количества единичных бит 23, четвертого выходного буферного регистра количества нулевых бит 24. Внешний вход С тактовых сигналов 25 также соединен с соответствующими входами С тактовых сигналов регистра RG_G групп бит 13, регистра RG_К количества групп 14, регистра RG_U количества единичных бит 15 и триггера ТРО пуска-останова 12, у которого второй вход R синхронной установки в нулевое состояние соединен с внешним входом R синхронной установки в нулевое состояние 26.
Внешний вход начала работы START соединен с входом S синхронной установки в единичное состояние триггера ТРО пуска-останова 12, с информационным D-входом первого триггера ТЕВ разрешения приема левого (первого) бита 2 и входами R синхронной установки в нулевое состояние регистра RG_G групп бит 13, регистра RG_К количества групп 14, регистра RG_U количества единичных бит 15.
Внешний вход остановки устройства STOP соединен с первым входом R синхронной установки в нулевое состояние триггера ТРО пуска-останова 12 и с информационным D-входом второго триггера TEQ разрешения приема в выходные буферные регистры 19.
Выход триггера ТРО пуска-останова 12 соединен с входами СЕ разрешения работы регистра RG_G групп бит 13, регистра RG_К количества групп 14 и регистра RG_U количества единичных бит 15.
Выход второго триггера TEQ разрешения приема в выходные буферные регистры 19 соединен с входами СЕ разрешения работы первого выходного буферного регистра кодов групп 20, второго выходного буферного регистра общего количества групп 21, выходного триггера левого (первого) бита входных данных 22, третьего выходного буферного регистра количества единичных бит 23, четвертого выходного буферного регистра количества нулевых бит 24.
Разряды D1, …, DM набора входных данных соединены с соответствующими одноименными входами модуля FК детектирования групп 1, а также левый (первый) бит D1 соединен с информационным D-входом триггера TLB левого (первого) бита 3 и соединен со вторым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4. Выходы групп G1, …, GM модуля FК детектирования групп 1 соединены с соответствующими одноименными входами групп первого модуля SF_1 сдвига групп 6, выход группы К количества групп бит соединен со второй группой входов уменьшаемого вычитателя SB 8, а выход группы U количества единичных бит соединен с группой входов первого слагаемого третьего сумматора SM_U количества единичных бит 11.
Выход первого триггера ТЕВ разрешения приема левого (первого) бита 2 соединен с первым инверсным входом элемента И с одним инверсным входом 5 и с входом СЕ разрешения работы триггера TLB левого (первого) бита 3, выход которого соединен с информационным D-входом выходного триггера левого (первого) бита входных данных 22 и третьим входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, выход которого соединен со вторым прямым входом элемента И с одним инверсным входом 5.
Выход элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4 является внутренним флагом декрементации FD и соединен с входом управления сдвигом первого модуля SF_1 сдвига групп 6 и входом вычитания единицы «-1» вычитателя SB.
У первого SF_1 модуля сдвига групп 6 первая группа выходов соединена с группой входов второго слагаемого первого сумматора SM_G бит в группе 7, а группы выходов, начиная со второй до (М+1)-й групп выходов, соединены с соответствующими информационными группами входов второго SF_2 модуля сдвига групп 9, начиная с (N-M+1)-й до N-й групп входов. N групп выходов второго SF_2 модуля сдвига групп 9 соединены с соответствующими одноименными группами входов регистра RG_G групп бит 13, N групп выходов которого соединены с соответствующими одноименными группами входов третьего SF_3 модуля сдвига групп 16, у которого N групп выходов соединены с соответствующими одноименными группами входов первого выходного буферного регистра кодов групп 20, выходы которого являются N внешними выходами групп бит QG1, …, QGN.
У регистра RG_G групп бит 13 выходы групп, начиная с (М+1)-й группы до (N-1)-й группы, соединены с группами входов второго SF_2 модуля сдвига групп 9, начиная с первой до (N-M-1)-й групп входов. N-я группа выходов регистра RG_G групп бит 13 соединена с группой входов первого слагаемого первого сумматора SM_G бит в группе 7, выход которого соединен с (N-M)-й группой входов второго SF_2 модуля сдвига групп 9, у которого группа входов задания кода сдвига соединена с выходом вычитателя SB 8, который также соединен с группой входов первого слагаемого второго сумматора SM_К количества (суммы) групп 10, выход которого соединен с группой информационных входов регистра RG_K количества (суммы) групп 14, выход которого является внутренней шиной общего количества групп KG, которая соединена с группой входов второго слагаемого второго сумматора SM_К количества (суммы) групп 10, с группой инверсных входов второго слагаемого четвертого сумматора SM_N дополнения 17 и с группой информационных входов второго выходного буферного регистра общего количества групп 21, выходы которого являются группой внешних выходов общего количества групп QК. Младший нулевой разряд kg0 внутренней шины KG общего количества групп также соединен также с первым входом элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4.
На группу входов первого слагаемого четвертого сумматора SM_N дополнения 17 подано значение кода числа «N», на вход переноса CI подано значение логической единицы «1», а выход соединен с группой входов задания кода сдвига третьего SF_3 модуля сдвига групп 16.
Выход третьего сумматора SM_U количества единичных бит 11 соединен с группой информационных входов регистра RG_U количества единичных бит 15, выход которого соединен с группой входов второго слагаемого третьего сумматора SM_U количества единичных бит 11, с группой информационных входов третьего выходного буферного регистра общего количества групп 23 и с группой инверсных входов второго слагаемого пятого сумматора SM_Z количества нулевых бит 18, у которого на группу входов первого слагаемого подано значение кода числа «N», на вход переноса CI подано значение логической единицы «1, а выход соединен с группой информационных входов четвертого выходного буферного регистра количества нулевых бит 24.
Группа выходов третьего выходного буферного регистра общего количества групп 23 является группой внешних выходов количества единичных бит QU, а группа выходов четвертого выходного буферного регистра количества нулевых бит 24 является группой внешних выходов количества нулевых бит QZ.
ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ
Принцип работы предлагаемого устройства состоит в следующем.
Работа предлагаемого устройства начинается по сигналу начала работы START на внешнем входе. При этом по тактовому сигналу С в единичное состояние устанавливаются триггер пуска-останова 12 ТРО=1 и первый триггер 2 разрешения приема левого (первого) бита D1 входного двоичного числа ТЕВ=1. Первый триггер ТЕВ разрешения приема 2 осуществляет задержку на один такт сигнала начала работы START.
Входное N разрядное двоичное число без знака разбивается на L=N/M наборов по М разрядов в каждом наборе. Наборы входных данных последовательно поступают на входы устройства, при этом М двоичных разрядов каждого из L наборов параллельно поступают на соответствующие входы D1, …, DM устройства.
0
1
1
0
В модуле FК детектирования групп 1 для каждого входного набора D1, …, DM формируются значения двоичных кодов групп G1, …, GM, соответствующих количеству подряд идущих единичных или нулевых бит во входном наборе, а также формируются двоичный код К общего количества (суммы) групп и двоичный код U общего количества (суммы) единичных бит. Примеры формирования значений разрядов соответствующих двоичных кодов при М=2 и М=4 приведены в таблицах 1 и 2 или могут быть реализованы как в прототипе. Кроме того, значение левого (первого) бита D1 первого набора данных для входного N разрядного двоичного числа принимается на триггер TLB левого (первого) бита 3. При этом если триггер TLB принимает нулевое значение TLB=0, то первая группа бит содержит нулевые биты G1, а если триггер TLB принимает единичное значение TLB=1, то первая группа бит содержит единичные биты G1. При этом последующие группы единичных бит G и нулевых бит G чередуются.
Для выявления групп (рядов) подряд идущих единичных или нулевых бит и объединения однотипных соседних групп в соседних последовательных наборах анализируются значение младшего разряда kg0 на внутренней шине текущего значения общего количества групп KG, который указывает на четность количества групп (при kg0=0) или нечетность количества групп (при kg0=1), а также значение первого (левого) бита D1 текущего набора входных данных D1, …, DM и значение первого (левого) бита входного двоичного числа, установленного на триггере TLB левого (первого) бита 3 для первого набора входных данных, и формируется значение флага декрементации FD в соответствии с таблицей 3 на элементе «ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR) 4 и элементе И с одним инверсным входом 5. При четном значении кода текущего общего количества групп KG групп (при kg0=0) единичный или нулевой тип последней группы текущего набора не совпадает со значением первого (левого) бита входных данных, установленного на триггере TLB левого (первого) бита 3, а при нечетном значении кода текущего общего количества групп KG групп (при kg0=1) тип последней группы текущего набора совпадает со значением первого (левого) бита входных данных, установленного на триггере TLB.
Далее значения кодов по группам G1, …, GM передаются на соответствующие одноименные группы входов первого SF_1 модуля сдвига групп 6, в котором осуществляется передача этих кодов без сдвига, и заполнением выходной старшей первой группы нулевыми значениями, или со сдвигом в сторону старшей группы влево на 1 разряд, и заполнением выходной младшей (М+1)-й группы нулевыми значениями. Сдвиг на 1 разряд осуществляется при единичном значении флага декрементации FD=1, который указывает на однотипность (единичных или нулевых бит) последней группы предыдущего набора и первой группы последующего текущего набора. Для первого набора D1, …, DM входных данных значения кодов по группам G1, …, GM на выходы первого SF_1 модуля сдвига групп 6 передаются без сдвига, при этом на первой группе выходов устанавливается нулевое значение. Значение кода с первой группы выходов первого SF_1 модуля сдвига групп 6 передается на группу входов второго слагаемого первого сумматора SM_G бит в группе 7. Коды с выходов первого SF_1 модуля сдвига групп 6, начиная со второй до (М+1)-й групп выходов, передаются на соответствующие информационные группы входов второго SF_2 модуля сдвига групп 9, начиная с (N-M+1)-й до N-й групп входов.
1
0
Одновременно на вычитателе SB (декременторе) 8, при совпадении в соседних последовательных наборах в младшей группе предыдущего набора и в старшей группе G1 последующего текущего набора подряд идущих единичных G или нулевых G бит, при единичном значении флага декрементации FD=1 проводится вычитание единицы из кода суммы К количества групп текущего набора (K-FD).
Значение с выхода вычитателя SB (декрементора) 8 передается на группу входов задания кода сдвига второго SF_2 модуля сдвига групп 9 и на группу входов первого слагаемого второго сумматора SM_К количества (суммы) групп 10.
Во втором SF_2 модуле сдвига групп 9 осуществляется сдвиг кодов групп в сторону старшей первой группы влево на скорректированное количество групп текущего набора (K-FD) и при этом нулевые значения устанавливаются в разрядах всех групп, начиная с (N+1)-й до (N+M)-й, которые не передаются на входы регистра RG_G групп бит 13. Значения кодов с выходов второго SF_2 модуля сдвига групп 9 передаются на соответствующие одноименные группы входов регистра RG_G групп бит 13, запись в который осуществляется по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера ТРО пуска-останова 12. При этом на выходах N-й группы будет установлено значение кода соответствующее количеству (сумме) бит в выявленной последней (правой) группе бит на текущий момент времени.
Значения кодов групп с выходов регистра RG_G групп бит 13, начиная с (М+1)-го до (N-1)-го выходов, передаются на соответствующие группы входов второго SF_2 модуля сдвига групп 9, начиная с первой до (N-M-1)-й групп входов, а значение кода с N-й группы выходов регистра RG_G групп бит 13 передается на группу входов первого слагаемого первого сумматора SM_G бит в группе 7, значение с выходов которого передается на (N-M)-ю группу входов второго SF_2 модуля сдвига групп 9.
1
0
На первом сумматоре SM_G бит в группе 7 при совпадении в соседних последовательных наборах в младшей группе предыдущего набора и в старшей группе G1 последующего текущего набора подряд идущих единичных G или нулевых G бит осуществляется сложение значений количества бит в данных группах.
Одновременно на вторых сумматорах SM_К количества (суммы) групп 10 осуществляется суммирование скорректированного значения кода группы общего количества (суммы) групп (K-FD) для текущего набора входных данных, с выходов вычитателя SB (декрементора) 8, и значение кода KG с внутренней шины общего количества (суммы) групп единичных и нулевых бит предыдущих наборов и формируется новый код суммы групп, который передается на соответствующую группу входов регистра RG_K количества (суммы) групп 14, запись в который осуществляется по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера ТРО пуска-останова 12, а разряды выходов регистра RG_K количества (суммы) групп 14 являются разрядами внутренней шины общего количества (суммы) групп KG.
Кроме того, на третьих сумматорах SM_U количества (суммы) единичных бит 11 осуществляется суммирование количества (суммы) единичных бит U для текущего и предыдущих наборов входных данных и результат суммы записывается в регистр RG_U количества (суммы) единичных бит 15 по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера ТРО пуска-останова 12.
Кроме того на пятых сумматорах SM_Z количества (суммы) нулевых бит 18 осуществляется сложение кода числа «N» с инверсным значением кода с регистра RG_U количества (суммы) единичных бит 15, при единичном значении на входе переноса сумматора СI=1. Таким образом, на выходе пятого сумматора SM_Z формируется код (N-(RG_U)+1), который соответствует количеству (сумме) нулевых бит в N разрядных входных данных.
Аналогично осуществляется обработка последующих последовательных наборов входных данных D1, …, DM, выявление (детектирование) групп (рядов) подряд идущих единичных и нулевых бит, объединение однотипных групп соседних наборов и формирование соответствующих значений в регистре RG_G групп бит 13, регистре RG_K количества (суммы) групп 14 и регистре RG_U количества (суммы) единичных бит 15.
Кроме того, на каждом такте на четвертом сумматоре SM_N дополнения количества групп 17 осуществляется сложение кода числа «N» с инверсным значением кода KG с внутренней шины общего количества (суммы) групп, при единичном значении на входе переноса сумматора СI=1. На выходе четвертого сумматора SM_N дополнения количества групп 17 формируется код (N-(KG)+1), который соответствует количеству старших нулевых групп и на данное значение в третьем SF_3 модуле сдвига групп 16 осуществляется сдвиг кодов групп в сторону старшей первой группы влево, таким образом, что значение количества бит в первой группе из N разрядных входных данных передается на выходы первой группы выходов. Значения с групп выходов третьего SF_3 модуля сдвига групп 16 передаются на одноименные группы входов выходного буферного регистра 20.
По сигналу останова STOP на внешнем входе, который поступает одновременно с последним L-м входным набором D1, …, DM, по тактовому сигналу С в нулевое состояние устанавливается триггер пуска-останова 12 ТРО=0 и в единичное состояние устанавливается второй триггер разрешения приема в выходные буферные регистры 19 TEQ=1. Второй триггер TEQ разрешения приема 19 осуществляет задержку на один такт сигнала останова STOP. По следующему тактовому сигналу С, при СЕ=1 передаваемого с выхода второго триггера TEQ=1 разрешения приема 19, осуществляется запись в выходной триггер 22 и в выходные буферные регистры 20, 21, 23 и 24 значений кодов, которые с соответствующих выходов передаются на внешний выход QLB значения левого (первого) бита D1 входного числа и на внешние выходы групп бит QG1, …, QGN, общего количества (суммы) групп QК, количества (суммы) единичных бит QU, количества (суммы) нулевых бит QZ. Одновременно по тактовому сигналу С в нулевое состояние устанавливается второй триггер разрешения приема в выходные буферные регистры 19 TEQ=0.
Предлагаемое устройство работает следующим образом.
Перед началом работы на внешнем входе 26 синхронной установки в нулевое состояние R устанавливается единичное значение и по тактовому сигналу С на внешнем входе 25 в нулевые состояния устанавливаются триггер разрешения приема левого (первого) бита D1 входного числа 2 ТЕВ=0, триггер левого (первого) бита D1 входного числа 3 TLB=0, триггер пуска-останова 12 ТРО=0, триггер разрешения приема в выходные буферные регистры 19 TEQ=0, первый выходной буферный регистр RG кодов групп G1, …, GN 20, второй выходной буферный регистр RG_общего количества групп К 21, выходной триггер Т левого (первого) бита входных данных 22, третий выходной буферный регистр RG_количества (суммы) единичных бит 23 и четвертый выходной буферный регистр RG_количества (суммы) нулевых бит 24. Далее при единичном значении сигнала начала работы на внешнем входе START=1 по тактовому сигналу С на внешнем входе 25 в единичное состояние устанавливаются триггер пуска-останова 12 ТРО=1 и первый триггер разрешения приема левого (первого) бита D1 входного числа 2 ТЕВ=1 и в нулевые состояния устанавливаются регистр RG_G групп бит 13, регистр RG_К количества (суммы) групп 14 и регистр RG_U количества (суммы) единичных бит 15 (соответственно такты 1 и 2 в потактовой временной диаграмме работы на фиг. 2 при N=16, М=4, L=4.).
Далее в каждом такте, начиная с такта 2, на внешние входы устройства D1, …, DM параллельно поступают по М разрядов последовательных L=N/M наборов N разрядного двоичного числа без знака. При этом младший разряд D1 является первым левым разрядом каждого входного набора, а младший разряд D1 первого набора также является левым (первым) битом входного N разрядного двоичного числа. Например, на фиг. 2 в такте 2 на входы D1, …, D4 поступает первый 4-х разрядный двоичный набор 1001.
1
0
1
0
1
0
При этом в модуле 1 детектирования групп FК выявляются группы подряд идущих единичных G или нулевых бит G и для первого входного набора 1001 (в соответствии с таблицей 2) формируются значения - G1=1, G2=2, G3=1, G4=0, а также формируются код количества (суммы) групп К=3 и код количества (суммы) единичных бит U=2. Далее значения кодов групп G1, …, G4 с выходов модуля 1 детектирования групп FК, передаются на соответствующие группы входов первого SF_1 модуля сдвига групп 6, в котором осуществляется передача этих кодов без сдвига, так как установлено нулевое значение флага декрементации FD=0. а на первой группе выходов первого SF_1 модуля сдвига групп 6 устанавливается нулевое значение. При этом на выходе первого SF_1 модуля сдвига групп 6 формируется код O_SF_1=0 1210. Нулевое значение кода первой группы выходов первого SF_1 модуля сдвига групп 6 передается на группу входов второго слагаемого первого сумматора SM_G бит в группе 7, на группу входов первого слагаемого которого также поступает нулевое значение с N-го выхода регистра RG_G групп бит 13. Поэтому на выходе первого сумматора SM_G бит в группе 7 устанавливается нулевое значение SM_G=0, которое передается на (N-M)-й вход второго SF_2 модуля сдвига групп 9. Одновременно коды с выходов первого SF_1 модуля сдвига групп 6, начиная со второй до (М+1)-й групп выходов, передаются на соответствующие информационные входы второго SF_2 модуля сдвига групп 9, начиная с (N-M+1)-го до N-го входа (значение на входе I_SF_2=0000 0000 0000 1210).
Одновременно на выход вычитателя SB (декрементора) 8 передается код суммы количества групп К=3 текущего первого набора без изменений, так как установлено нулевое значение флага декрементации FD=0. Далее значение К=3 с выхода вычитателя SB (декрементора) 8 передается на группу входов задания кода сдвига второго SF_2 модуля сдвига групп 9, в котором осуществляется сдвиг кодов групп в сторону старшей первой группы влево на К=3 групп и на группах выходов устанавливаются соответствующие значения кодов групп O_SF_2=0000 0000 0000 0121, которые передаются на соответствующие одноименные группы входов регистра RG_G групп бит 13, запись в который осуществляется по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера пуска-останова 12 ТРО=1. Кроме того значение кода К=3 с выхода вычитателя SB (декрементора) 8 передается на группу входов первого слагаемого второго сумматора SM_К количества (суммы) групп 10, которое суммируется с начальным нулевым кодом KG=0 с выхода регистра RG_K количества (суммы) групп 14 и формируется текущее значение кода количества (суммы) групп (для первого входного набора данных SM_К=3), который передается на соответствующую группу входов регистра RG_K количества (суммы) групп 14, запись в который осуществляется по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера ТРО пуска-останова 12. Разряды выходов регистра RG_K количества (суммы) групп 14 являются разрядами внутренней шины общего количества (суммы) групп KG. Кроме того на третьих сумматорах SM_U количества (суммы) единичных бит 11 осуществляется суммирование количества (суммы) единичных бит U=2 для текущего набора с нулевым кодом с выхода регистра количества (суммы) единичных бит 15 RG_U=0 и формируется текущее значение суммы единичных бит SM_U=2, которое передается на вход регистра RG_U количества (суммы) единичных бит 15, запись в который осуществляется по тактовым сигналам С при единичном значении СЕ=1 передаваемым с выхода триггера ТРО пуска-останова 12.
По следующему тактовому сигналу С на такте 3 значения кодов со второго и третьего сумматоров SM_К=3 и SM_U=2 записываются соответственно в регистр RG_K количества (суммы) групп 14 и регистр RG_U количества (суммы) единичных бит 15. Кроме того единичное значение первого бита D1=1 записывается в триггер TLB левого (первого) бита 3, так как установлено единичное значение на первом триггере разрешения приема левого (первого) бита D1 входного числа 2 ТЕВ=1, который при этом переключится в нулевое состояние ТЕВ=0.
1
0
1
0
1
0
Одновременно на такте 3 на фиг. 2 на входы D1, …, D4 поступает второй 4-х разрядный двоичный набор 1101, для которого в модуле 1 детектирования групп FК выявляются группы подряд идущих единичных G или нулевых бит G и формируются значения - G1=2, G2=1, G3=1, G4=0, а также формируются код количества (суммы) групп К=3 и код количества (суммы) единичных бит U=3. При этом в соответствии с таблицей 3 формируется единичное значение флага декрементации FD=1, так как единичные значения установлены на триггере 3 левого (первого) бита первого набора входных данных TLB=1, на первом (левом) разряде текущего второго набора входных данных D1=1 и на младшем разряде kg0 на внутренней шине KG текущего значения общего количества групп kg0=1. Далее при единичном значении флага декрементации FD=1 в первом SF_1 модуле сдвига групп 6 осуществляется сдвиг на одну группу влево и на выходе формируется код O_SF_1=2 1100. Единичное значение флага декрементации FD=1 указывает на то, что единичные значения бит установлены в первом разряде D1=1 текущего второго набора и в четвертом разряде D4=1 предыдущего первого набора. Поэтому в вычитателе SB (декременторе) 8 значение кода К=3 количества групп для текущего набора уменьшается на единицу SB=2, которое передается на группу входов первого слагаемого второго сумматора SM_К количества (суммы) групп 10, которое суммируется с кодом на шине KG=3, с выхода регистра RG_K количества (суммы) групп 14, и формируется текущее значение кода количества (суммы) групп - для первых двух наборов входных данных SM_К=5, которое на следующем такте 4 будет записано в регистр RG_K количества (суммы) групп 14 и поступит на внутреннюю шину KG.
1
Кроме того, так как установлено единичное значение флага декрементации FD=1, то в первом сумматоре SM_G бит в группе 7 осуществляется суммирование количества единичных бит последней группы для первого набора и первой группы второго набора, и формируется код суммы SM_G=3 единичной группы G, который одновременно с кодами с выходов групп первого F_1 модуля сдвига групп бис выходов регистра RG_G групп бит 13 передаются на соответствующие группы входов второго SF_2 модуля сдвига групп 9 - I_SF_2=0000 0000 0123 1100, которые сдвигаются на SB=2 групп и на выходах групп второго SF_2 модуля сдвига групп 9 формируется код O_SF_2=0000 0000 0001 2311, который на следующем такте 4 будет записан в регистр RG_G групп бит 13.
Кроме того, на такте 3 на третьем сумматоре SM_U количества (суммы) единичных бит 11 осуществляется суммирование количества (суммы) единичных бит U=3 для текущего второго набора входных данных с кодом с выхода регистра количества (суммы) единичных бит 15 RG_U=2 и формируется текущее значение суммы единичных бит SM_U=5, которое на следующем такте 4 будет записано в регистр RG_U количества (суммы) единичных бит 15.
1
0
0
1
0
1
На такте 4 на фиг. 2 на входы D1, …, D4 поступает третий 4-х разрядный двоичный набор 0101, для которого в модуле 1 детектирования групп FК выявляются группы подряд идущих единичных G или нулевых бит G и формируются значения - G1=1, G2=1, G3=1, G4=1, а также формируются код количества (суммы) групп К=4 и код количества (суммы) единичных бит U=2. Далее в соответствии с таблицей 3 формируется нулевое значение флага декрементации FD=0, так как в последнем разряде предыдущего второго входного набора установлено единичное значение D4=1, а в первом разряде текущего третьего набора в первом разряде установлено нулевое значение D1=0. Поэтому в вычитателе SB (декременторе) 8 значение количества групп К=4 для текущего третьего набора не уменьшается SB=4 и далее на втором сумматоре SM_К количества (суммы) групп 10 формируется текущее значение кода количества (суммы) групп - для трех наборов входных данных SM_К=9, которое на следующем такте 5 будет записано в регистр RG_K количества (суммы) групп 14.
Одновременно на такте 4, так как установлено нулевое значение флага декрементации FD=0, в первом SF_1 модуле сдвига групп 6 сдвиг не выполняется и на выходе формируется код O_SF_1=0 1111, соответствующие группы которого совместно с кодами с выходов регистра RG_G групп бит 13 и с выхода первого сумматора SM_G бит в группе 7 передаются на соответствующие группы входов второго SF_2 модуля сдвига групп 9, в котором осуществляется сдвиг на SB=4 групп и на выходах групп второго SF_2 модуля сдвига групп 9 формируется код O_SF_2=0000 0001 2311 1111, который на следующем такте 5 будет записан в регистр RG_G групп бит 13.
Кроме того, на такте 4 на третьем сумматоре SM_U количества (суммы) единичных бит 11 осуществляется суммирование количества (суммы) единичных бит U=2 для текущего третьего набора входных данных с кодом с выхода регистра количества (суммы) единичных бит 15 RG_U=5 и формируется текущее значение суммы единичных бит SM_U=7, которое на следующем такте 5 будет записано в регистр RG_U количества (суммы) единичных бит 15.
1
1
0
1
0
Далее, аналогично выше приведенному алгоритму, на такте 5 на фиг. 2 на входы D1, …, D4 поступает четвертый 4-х разрядный двоичный набор, содержащий только единичные значения 1111, для которого в модуле 1 детектирования групп FК выявляется только одна группа подряд идущих единичных бит G и формируются значения - G1=4, G2=0, G3=0, G4=0, а также формируются код количества (суммы) групп К=1 и код количества (суммы) единичных бит U=4. Далее в соответствии с таблицей 3 формируется единичное значение флага декрементации FD=1, так как единичные значения установлены в последнем разряде D4=1 предыдущего третьего входного набора и в первом разряде D1=1 текущего четвертого набора. Поэтому в первом SF_1 модуле сдвига групп 6 осуществляется сдвиг на одну группу и на выходе формируется код O_SF_1=4 0000, а также в вычитателе SB (декременторе) 8 значение количества групп К=1 уменьшается на единицу, т.е формируется нулевой код SB=0, и далее на выходе второго сумматора SM_К количества (суммы) групп 10 формируется текущее значение кода количества (суммы) групп - для четырех наборов входных данных SM_К=9, которое на следующем такте 6 будет записано в регистр RG_K количества (суммы) групп 14.
1
Одновременно в первом сумматоре SM_G бит в группе 7 осуществляется суммирование количества единичных бит последней группы для третьего набора и первой группы четвертого набора, и формируется код суммы SM_G=5 единичной группы G.
Далее во втором SF_2 модуле сдвига групп 9 сдвиг не проводится, так как SB=0, и на выходе формируется код O_SF_2=0000 0001 2311 1115, который на следующем такте 6 будет записан в регистр RG_G групп бит 13. Кроме того, на такте 5 на третьем сумматоре SM_U количества (суммы) единичных бит 11 формируется значение суммы единичных бит SM_U=11, которое на следующем такте 6 будет записано в регистр RG_U количества (суммы) единичных бит 15.
Кроме того, одновременно на каждом такте на четвертом сумматоре SM_N дополнения количества групп 17 осуществляется сложение кода числа «N» с инверсным значением кода KG с внутренней шины общего количества (суммы) групп, при единичном значении на входе переноса сумматора СI=1. На выходе четвертого сумматора SM_N дополнения количества групп 17 формируется код (N-(KG)+1), который соответствует количеству старших нулевых групп и на данное значение в третьем SF_3 модуле сдвига групп 16 осуществляется сдвиг кодов групп, с выходов регистра RG_G групп бит 13, в сторону старшей первой группы влево, таким образом, что значение количества бит в первой группе из N разрядных входных данных передается на выходы первой группы выходов. Значения с групп выходов третьего SF_3 модуля сдвига групп 16 передаются на одноименные группы входов выходного буферного регистра 20. Например, в третьем SF_3 модуле сдвига групп 16 на фиг. 2 на такте 3 осуществляется сдвиг на 13 групп и формируется код O_SF_3=1210 0000 0000 0000, на такте 4 сдвиг на 11 групп и формируется код O_SF_3=1231 1000 0000 0000, на такте 5 сдвиг на 7 групп и формируется код O_SF_3=1231 1111 1000 0000. На такте 6 также осуществляется сдвиг на 7 разрядов, так как четвертый набор входных данных содержит все единичные значения 1111, которые суммируются с группой единичных бит третьего набора, и поэтому на выходе третьего SF_3 модуля сдвига групп 16 формируется код O_SF_32=1231 1111 5000 0000.
Кроме того, одновременно на каждом такте на пятых сумматорах SM_Z количества (суммы) нулевых бит 18 осуществляется сложение кода числа «N» с инверсным значением кода с регистра RG_U количества (суммы) единичных бит 15, при единичном значении на входе переноса сумматора СI=1. Таким образом, на выходе пятого сумматора SM_Z формируется код (N-(RG_U)+1), который соответствует количеству (сумме) нулевых бит в N разрядных входных данных. Например, на пятых сумматорах SM_Z количества (суммы) нулевых бит 18 на фиг. 2 на такте 3 формируется код SM_Z=14, так как в первом наборе входных данных содержится только два единичных бита, на такте 4 формируется код SM_Z=11, так как в первом и втором наборах содержится пять единичных бит, на такте 5 формируется код SM_Z=9, так как в трех наборах содержится семь единичных бит и на такте 6 формируется код SM_Z=5, так как во всех входных наборах 16-ти разрядного двоичного числа содержится одиннадцать единичных бит и соответственно пять нулевых бит.
На такте 5 одновременно с последним четвертым набором входных данных устанавливается единичное значение на внешнем входе останова STOP=1 и по следующему тактовому сигналу С на внешнем входе 25 (такт 6) в нулевое состояние устанавливается триггер пуска-останова 12 ТРО=0 и в единичное состояние устанавливается второй триггер разрешения TEQ=1 приема в выходные буферные регистры 19, который осуществляет задержку на один такт сигнала останова STOP.
На следующем такте 6, при единичном значении на выходе второго триггера разрешения 19 TEQ=1, которое передается на входы разрешения СЕ триггера 22 и на выходные буферные регистры 20, 21, 23 и 24, осуществляется запись значений соответствующих кодов, которые далее передаются на внешний выход QLB значения левого (первого) бита D1 входного числа и на внешние выходы групп бит QG1, …, QGN, общего количества (суммы) групп QК, количества (суммы) единичных бит QU, количества (суммы) нулевых бит QZ.
Предлагаемое устройство может быть применено для аппаратной реализации статистических тестов, разработанных лабораторией информационных технологий Национального института стандартов и технологий (NIST, США), целью которых является определение меры случайности двоичных последовательностей, порожденных генераторами случайных чисел. В частности, предлагаемое устройство реализует:
- частотный побитовый тест, суть которого определить соотношение между нулями и единицами во всей двоичной последовательности. Цель - выяснить действительно ли число нулей и единиц в последовательности приблизительно одинаковы. Тест оценивает, насколько близка доля единиц к 0,5.
- частотный блочный тест, суть которого определение доли единиц внутри блока длиной К бит. Цель - выяснить действительно ли частота повторения единиц в блоке длиной К бит приблизительно равна К/2.
- тест на последовательность одинаковых бит, суть которого состоит в подсчете полного числа рядов (групп) в исходной последовательности, где под рядом понимается непрерывная подпоследовательность одинаковых бит. Ряд (группа) длиной k бит состоит из k абсолютно идентичных бит, начинается и заканчивается с бита, содержащего противоположное значение. Цель - сделать вывод о том, действительно ли количество рядов (групп), состоящих из единиц и нулей с различными длинами, соответствует их количеству в случайной последовательности. В частности, определяется быстро либо медленно чередуются единицы и нули в исходной последовательности.
При обработке результатов физических экспериментов предлагаемое устройство обеспечивает выявление событий (группы единичных бит) и интервалов между событиями (группы нулевых бит), определение длительности событий и интервалов между ними, а также определение общего количества и длительности событий.
0
1
Таким образом, на выходах предлагаемого устройства формируются значение левого (первого) бита D1 входных данных QLB, указывающий на тип первой выявленной группы бит, двоичные коды QG1, …, QGN, соответствующие количеству нулевых QG и единичных QG бит в группах входного двоичного числа, которые чередуются в зависимости от значения QLB, а также формируются общее количество групп QК, общее количество (сумма) единичных QU и нулевых QZ бит.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство решает поставленную задачу - выявление групп одинаковых бит, определение количества единичных и нулевых бит в группах, определение общего количества групп и определение общего количества единичных и нулевых бит во входном двоичном числе, обладает регулярностью узлов и связей, и соответствует заявляемому техническому результату - расширение арсенала средств того же назначения и упрощение увеличения разрядности входных данных при сокращении аппаратных затрат.