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

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

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

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

Известно устройство последовательного типа для детектирования групп нулевых и единичных бит и определение их количества (RU №2680759 С1, МПК G06F 7/74, заявлено 16.02.2018, опубл. 26.02.2019, Бюл. №6) в котором для входных последовательностей данных размерностью N, поступающих на внешний вход данных DI, на соответствующих внешних выходах групп устройства формируются двоичные коды, соответствующие количеству групп QG, количеству нулевых бит QZ, количеству единичных бит QU, разности между количеством единичных и нулевых бит QZU, количество бит по группам QO с выходного буфера ОВ 11, при этом в четных адресах, начиная с нулевого адреса, указывается количество нулевых бит в группах, а в нечетных адресах, начиная с первого адреса, указывается количество единичных бит в группах, а также формируются флаг готовности FE, флаг «нулей больше единиц» F01, флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ.

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

Известно устройство параллельно-последовательной структуры для детектирования групп нулевых и единичных бит и определение их количества (RU №2711054 С1, МПК G06F 7/74, заявлено 06.08.2019, опубл. 14.01.2020, Бюл. №2), содержащее М разрядов D1, …, DM набора входных данных из N разрядного двоичного числа, состоящего из L наборов по М разрядов в наборе, где N=L*M, N внешних выходов групп бит QG1, …, QGN, группу внешних выходов общего количества групп QK, внешний выход левого (первого) бита QLB, группу внешних выходов количества единичных бит QU, группу внешних выходов количества нулевых бит QZ, модуль FK детектирования групп 1, первый триггер ТЕВ разрешения приема 2, триггер TLB левого (первого) бита 3, элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, элемент И с одним инверсным входом 5, первый модуль SF_1 сдвига групп 6, первый сумматор SMG бит в группе 7, вычитатель SB 8, второй модуль SF_2 сдвига групп 9, второй сумматор SM_K количества групп 10, третий сумматор SM_U количества единичных бит 11, триггер ТРО пуска-останова 12, регистр RG_G групп бит 13, регистр RG_K количества групп 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 и внутренний флаг декрементации FD.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для детектирования групп бит (RU №2780985, МПК G06F 7/74, G06F 7/02, заявлено 01.12.2021, опубликовано 04.10.2022, Бюл. №28), содержащее внешний m разрядный вход данных ID, внешний m разрядный вход заданного шаблона IG, группу внешних выходов данных QB, первый RS-триггер пуска-останова TSS 1, второй D-триггер TR2 задержки 2, счетчик CTG групп 3, выходной буфер ОВ 4, первый R1 регистр данных 5, второй R2 регистр данных 6, группу из m компараторов 7₁, 7₂, …,7_m, группу из (m-1) элементов И 8₂, 8₃, …, 8_m, элемент ИЛИ 9 и элемент И 10, а также введены внешние входы асинхронной установки в нулевое состояние CLR, пуска устройства START, остановки устройства STOP и тактовый С, внутренняя 2m-разрядная шина данных BD, внутренняя m-разрядная шина данных буфера IOB, внутренний флаг совпадения FE, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ.

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

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

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

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что устройство параллельно-последовательной структуры для детектирования неперекрывающихся шаблонов бит содержит внешний m разрядный вход данных ID, внешний m разрядный вход заданного шаблона IG, группу внешних выходов данных QB, группу внешних выходов количества выявленных шаблонов QK, первый RS-триггер пуска-останова TSS 1, второй D-триггер TR2 задержки 2, счетчик CTG групп 3, выходной буфер ОВ 4, первый R1 регистр данных 5, второй R2 регистр данных 6, группу из m компараторов 7₁, 7₂, …,7_m, группу из m элементов И 8₁, 8₂, …, 8_m, группу из (m-1) элементов ИЛИ 9₁, 9₂, …, 9_(m-1), блок счета единиц 10, элемент И 11, элемент ИЛИ-НЕ 12, счетчик шаблонов СТК 13 и регистр маски RM 14,

а также введены внешние входы асинхронной установки в нулевое состояние CLR, пуска устройства START, остановки устройства STOP и тактовый вход С, внутренняя 2m-разрядная шина данных BD, внутренняя шина v разрядного двоичного кода начала шаблона в группе ВВ (где v=]log2 m[(большее целое)), внутренняя m разрядная шина кода единичного позиционного ряда ВС, внутренняя m разрядная шина маски ВМ, внутренний флаг совпадения FE, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ,

причем внешний вход асинхронной установки в нулевое состояние CLR соединен с соответствующими входами асинхронной установки в нулевое состояние CLR первого RS-триггера пуска-останова TSS 1 и второго D-триггера TR2 задержки,

внешний тактовый вход устройства С соединен с входами синхронизации С первого RS-триггера пуска-останова TSS 1, второго D-триггера TR2 задержки 2, счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистра данных 5, второго R2 регистра данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14,

внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние первого RS-триггера пуска-останова TSS 1 и с входами R синхронной установки в нулевое состояние счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистр данных 5, второго R2 регистр данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14,

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

причем прямой выход первого RS-триггера пуска-останова TSS 1 соединен с D-входом второго триггера TR2 задержки 2, с входами СЕ разрешения работы первого R1 регистра данных 5, второго R2 регистра данных 6, регистра маски RM 14 и третьими входами первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1),

выход второго D-триггера TR2 задержки соединен с входом СЕ разрешения работы счетчика CTG групп 3 и первым входом элемента И 11, выход которого соединен с входом СЕ разрешения записи в выходной буфер ОВ 4 и разрешения счета СЕ счетчика шаблонов СТК 13, выходы которого являются группой внешних выходов количества выявленных шаблонов QK,

причем внешний m разрядный вход заданного шаблона IG соединен с первыми группами входов всех m компараторов группы 7₁, 7₂, …,7_m, выходы которых соединены со вторыми входами соответствующих одноименных элементов И группы 8₁, 8₂, …, 8_m,

внешний m разрядный вход данных ID соединен с группой информационных D-входов первого R1 регистра данных 5, выходы которого являются соответствующими разрядами, начиная с первого до m-го разряда, внутренней шины данных BD, а также соединены с группой информационных D-входов второго R2 регистра данных 6, выходы которого являются соответствующими разрядами, начиная с (m+1)-го до 2m-го разряда, внутренней шины данных BD,

причем разряды внутренней шины данных BD группами по m разрядов, каждая из которых начинается с (i+1)-го разряда (i=l,…, m), соединены со вторыми группами входов соответствующих i-ых компараторов группы 7₁, 7₂, …,7_m,

выходы первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1) соединены с первыми входами одноименных элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1), а выход последнего m-го элемента И 8_m соединен со вторым входом последнего элемента 9_(m-1), а также является m-м разрядом внутренней шины кода единичного позиционного ряда ВС, у которой разрядами, начиная с первого до (m-1)-го разряда, являются выходы одноименных (m-1) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1),

кроме того вторые входы первых (m-2) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-2), начиная с первого до (m-2)-го элементов, соединены с выходами соответствующих последующих (m-2) элементов ИЛИ группы 9₂, 9₃, …, 9_(m-1), начиная со второго до (m-1)-го элементов,

причем все m разрядов внутренней шины кода единичного позиционного ряда ВС соединены с соответствующими входами блока счета единиц 10, с группой информационных D-входов регистра маски RM 14 и с входами элемента ИЛИ-НЕ 12, прямой выход которого является внутренним флагом совпадения FE и соединен со вторым входом элемента И 11, а инверсный выход элемент ИЛИ-НЕ 12 соединен с входом S синхронной установки в единичное состояние регистра маски RM 14,

кроме того выходы регистра маски RM 14 являются соответствующими одноименными разрядами внутренней m разрядной шины маски ВМ, которые соединены с первыми входами одноименных m элементов И группы 8₁, 8₂, …, 8_m,

причем выходы блока счета единиц 10 являются соответствующими разрядами внутренней шины двоичного кода начала шаблона в группе ВВ, которая соединена со второй группой информационных D-входов выходного буфера ОВ 4, у которого первая группа информационных D-входов соединена с выходами счетчика CTG групп 3,

кроме того выходной буфер ОВ 4 также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 4 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ.

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

На фиг. 1 представлена схема предлагаемого устройства. На фиг. 2 приведена схема поиска шаблонов. На фиг. 3 приведена временная диаграмма работы устройства.

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

ВВ - внутренняя шина v разрядного двоичного кода начала шаблона в группе,

где v=]log2 m[(большее целое),

ВС - внутренняя m разрядная шина кода единичного позиционного ряда,

BD - внутренняя 2m разрядная шина данных,

ВМ - внутренняя m разрядная шина маски,

BUF - буфер с дисциплиной обслуживания FIFO,

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

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

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

CTG - счетчик групп,

CTK - счетчик шаблонов,

D - информационные входы,

FF - внешний флаг «Буфер заполнен»,

FZ - внешний флаг «Буфер пуст»,

FE - внутренний флаг совпадения,

G1, G2, …, GL - входные группы,

ID - внешний m разрядный вход данных,

IG - внешний m разрядный вход заданного шаблона,

L - количество входных групп L=N/m,

m - разрядность входных данных,

N - размерность (длина) входной последовательности данных,

ОВ - выходной буфер,

QB - группа внешних выходов данных,

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

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

RG - регистр,

RM - регистр маски,

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

START - внешний вход пуска,

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

Т - триггер,

TR2 - триггер задержки,

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

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

2 - второй D-триггер задержки TR2,

3 - счетчик групп CTG,

4 - выходной буфер ОВ,

5 - первый регистр данных R1,

6 - второй регистр данных R2,

7₁, 7₂, …,7_m - группа из m компараторов (COMP),

8₁, 8₂, …, 8_m - группа из m элементов И (AND),

9₁, 9₂, …, 9_(m-1) - группа из (m-1) элементов ИЛИ (OR),

10 - блок счета единиц,

11 - элемент И (AND),

12 - элемент ИЛИ-НЕ (NOR),

13 - счетчик шаблонов СТК,

14 - регистр маски RM.

Предлагаемое устройство содержит внешний содержит внешний m разрядный вход данных ID, внешний m разрядный вход заданного шаблона IG, группу внешних выходов данных QB, группу внешних выходов количества выявленных шаблонов QK, первый RS-триггер пуска-останова TSS 1, второй D-триггер TR2 задержки 2, счетчик CTG групп 3, выходной буфер ОВ 4, первый R1 регистр данных 5, второй R2 регистр данных 6, группу из m компараторов, 7₁, 7₂, …,7_m, группу из m элементов И 8₁, 8₂, …, 8_m, группу из (m-1) элементов ИЛИ 9₁, 9₂, …, 9_(m-1), блок счета единиц 10, элемент И 11, элемент ИЛИ-НЕ 12, счетчик шаблонов СТК 13 и регистр маски RM 14.

В предлагаемое устройство также введены внешние входы асинхронной установки в нулевое состояние CLR, пуска устройства START, остановки устройства STOP и тактовый вход С, внутренняя 2m-разрядная шина данных BD, внутренняя шина v разрядного двоичного кода начала шаблона в группе ВВ (где v=]log2 m[(большее целое)), внутренняя m разрядная шина кода единичного позиционного ряда ВС, внутренняя m разрядная шина маски ВМ, внутренний флаг совпадения FE, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ.

Внешний вход асинхронной установки в нулевое состояние CLR соединен с соответствующими входами асинхронной установки в нулевое состояние CLR первого RS-триггера пуска-останова TSS 1 и второго D-триггера TR2 задержки.

Внешний тактовый вход устройства С соединен с входами синхронизации С первого RS-триггера пуска-останова TSS 1, второго D-триггера TR2 задержки 2, счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистра данных 5, второго R2 регистра данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14.

Внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние первого RS-триггера пуска-останова TSS 1 и с входами R синхронной установки в нулевое состояние счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистр данных 5, второго R2 регистр данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14.

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

Первый RS-триггер пуска-останова TSS 1 предназначен для выделения цикла работы предлагаемого устройства, между сигналами START и STOP, для входной последовательности данных DI размерности N, содержащей L групп размерности т. Причем прямой выход первого RS-триггера пуска-останова TSS 1 соединен с D-входом второго триггера TR2 задержки 2, с входами СЕ разрешения работы первого R1 регистра данных 5, второго R2 регистра данных 6, регистра маски RM 14 и третьими входами первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1)

Выход второго D-триггера TR2 задержки соединен с входом СЕ разрешения работы счетчика CTG групп 3 и первым входом элемента И 11, выход которого соединен с входом СЕ разрешения записи в выходной буфер ОВ 4 и разрешения счета СЕ счетчика шаблонов СТК 13, выходы которого являются группой внешних выходов количества выявленных шаблонов QK.

Счетчик CTG групп 3 предназначен для счета и хранения номера текущей группы входных данных. Второй D-триггер TR2 задержки 2 задерживает на один такт разрешение счета текущих групп в счетчике CTG групп 3 и записи в выходной буфер ОВ 4.

Внешний m разрядный вход заданного шаблона IG соединен с первыми группами входов всех m компараторов группы 7₁, 7₂, …,7_m, выходы которых соединены со вторыми входами соответствующих одноименных элементов И группы 8₁, 8₂, …, 8_m.

Внешний m разрядный вход данных ID соединен с группой информационных D-входов первого R1 регистра данных 5, выходы которого являются соответствующими разрядами, начиная с первого до m-го разряда, внутренней шины данных BD, а также соединены с группой информационных D-входов второго R2 регистра данных 6, выходы которого являются соответствующими разрядами, начиная с (m+1)-го до 2m-го разряда, внутренней шины данных BD.

Разряды внутренней шины данных BD группами по m разрядов, каждая из которых начинается с (i+1)-го разряда (i=1, …, m), соединены со вторыми группами входов соответствующих i-ых компараторов группы 7₁, 7₂, …,7_m.

Выходы первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1) соединены с первыми входами одноименных элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1), а выход последнего m-го элемента И 8_m соединен со вторым входом последнего элемента 9_(m-1), а также является m-м разрядом внутренней шины кода единичного позиционного ряда ВС, у которой разрядами, начиная с первого до (m-1)-го разряда, являются выходы одноименных (m-1) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1).

Кроме того вторые входы первых (v-2) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-2), начиная с первого до (m-2)-го элементов, соединены с выходами соответствующих последующих (m-2) элементов ИЛИ группы 9₂, 9₃, …, 9_(m-1), начиная со второго до (m-1)-го элементов.

Причем все m разрядов внутренней шины кода единичного позиционного ряда ВС соединены с соответствующими входами блока счета единиц 10, с группой информационных D-входов регистра маски RM 14 и с входами элемента ИЛИ-НЕ 12, прямой выход которого является внутренним флагом совпадения FE и соединен со вторым входом элемента И 11. Инверсный выход элемент ИЛИ-НЕ 12 соединен с входом S синхронной установки в единичное состояние регистра маски RM 14.

Кроме того выходы регистра маски RM 14 являются соответствующими одноименными разрядами внутренней m разрядной шины маски ВМ, которые соединены с первыми входами одноименных m элементов И группы 8₁, 8₂, …, 8_m.

Выходы блока счета единиц 10 являются соответствующими разрядами внутренней шины двоичного кода начала шаблона в группе ВВ, которая соединена со второй группой информационных D-входов выходного буфера ОВ 4, у которого первая группа информационных D-входов соединена с выходами счетчика CTG групп 3.

Выходной буфер ОВ 4 предназначен для накопления номеров входных групп и кода расположения разрядов начала выявленных групп соответствующих коду шаблона IG. Выходной буфер ОВ 4 также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 4 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ.

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

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

Предлагаемое устройство позволяет детектировать m-разрядные группы во входном N-разрядном двоичном числе, соответствующие m-разрядному заданному шаблону групп IG, который содержит заданную последовательность единичных и нулевых бит, формировать и записывать в выходной буфер ОВ 4 номера входных групп и двоичный код разряда начала выявленных групп соответствующих коду шаблона. При этом разряды выявленных соседних входных групп, совпадающих с заданным шаблоном IG, не могут перекрываться.

Входное N разрядное двоичное число без знака разбивается на L=N/m групп по m разрядов в каждой группе. Группы входных данных G1, G2, …, GL последовательно поступают на входы устройства. При этом m двоичных разрядов каждой из L групп параллельно поступают на соответствующие входы данных ID. В течение работы устройства на внешних входах шаблона IG должна быть установлена заданная m-разрядная последовательность единичных и нулевых бит.

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

Поиск (выявление, детектирование, анализ) осуществляется для каждых двух последовательных входных групп общей разрядностью 2 т. При этом каждая входная группа G1, G2, …, GL сначала поступает на первый R1 регистр данных 5, а затем на следующем такте переписывается во второй R2 регистр данных 6 с одновременной загрузкой следующей соседней группы в первый R1 регистр данных 5. Второй TR2 триггер 2 осуществляет задержку начала анализа на один такт для загрузки второй группы и удержание на один такт для возможности записи результата в выходной буфер ОВ 4 после сигнала остановки STOP=1.

На каждом такте для двух соседних групп осуществляется поиск заданного шаблона групп IG на m компараторах из группы 7₁, 7₂, …,7_m, на первые группы входов которых поступает m-разрядный код заданного шаблона IG, а на вторые группы входов которых поступают сдвинутые на один разряд соответствующие m-разрядные коды с внутренней 2m-разрядной шины данных BD, разрядами которой являются выходы первого R1 регистра данных 5 и второго R2 регистра данных 6. Одновременно осуществляется счет входных групп G1, G2, …, GL на счетчике CTG групп 3.

На выходах группы компараторов 7₁, 7₂, …,7_m формируются единичные значения при совпадении соответствующих m-разрядных групп с внутренней 2m-разрядной шины данных BD с кодом заданного шаблона групп IG и формируется m-разрядный код расположения разрядов начала выявленных шаблонов (перекрывающихся и неперекрывающихся) в текущей входной группе, номер которой устанавливается в счетчике CTG групп 3.

Далее, на основании нулевых значений разрядов шины маски ВМ с выходов регистра маски RM 14, в группе элементов И 8₁, 8₂, …, 8_m осуществляется исключение выявленных перекрывающихся шаблонов. Далее в группе элементов ИЛИ 9₁, 9₂, …, 9_(m-1) единичное значение, соответствующее выявленным группам, от старшего разряда передается последовательно в сторону младших разрядов по цепочке элементов ИЛИ и единичные значения устанавливаются на соответствующих выходах элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1), которые далее поступают на внутреннюю шину ВС. Таким образом, на внутренней шине ВС устанавливается упорядоченная последовательность единичных значений (унитарный позиционный ряд 00…011..1), начиная с первого разряда, сумма единиц которой соответствует номеру старшего (левого) выявленного шаблона.

Далее значения с внутренней шины ВС кода единичного позиционного ряда поступают на входы блока счета единиц 10, элемент ИЛИ-НЕ 12 и регистр маски RM 14. В блоке счета единиц 10 единичный позиционный ряд преобразуется в двоичный код разряда начала старшего (левого) выявленного шаблона в группе, которое далее передается на вторую группу информационных D-входов, одновременно с номером входной группы со счетчика CTG 3, которые передаются на первую группу информационных D-входов выходного буфера ОВ 4.

При наличии хотя бы одного единичного значения в разрядах на внутренней шине ВС на прямом выходе элемента ИЛИ-НЕ 12 формируется единичное значение флага совпадений FE=1, которое передается на элемент И 11 и по которому далее разрешается запись в выходной буфер ОВ 4 и счет выявленных шаблонов в счетчике СТК 14.

Одновременно значения с внутренней шины ВС кода единичного позиционного ряда записываются в регистр маски RM 14 и далее передаются на внутреннюю шину маски ВМ. При этом нулевые значения разрядов исключают выявленные перекрывающиеся шаблоны в группе элементов И 8₁, 8₂, …, 8_m.

Кроме того, при отсутствии единичных значений на внутренней шине ВС формируется единичное значение на инверсном выходе элемента ИЛИ-НЕ 12, которое передается на вход S синхронной установки регистра маски RM 14, по которому все разряды регистра маски RM 14 устанавливаются в единичное состояние, по которым на следующем такте разрешается передача единичных значений всех выходов группы из m компараторов 7₁, 7₂, …,7_m в группе элементов И 8₁, 8₂, …, 8_m

Кроме того в группе из (m-1)-го элементов И 8₂, 8₃, …, 8_m осуществляется запрет передачи результатов сравнения с (m-1) компараторов 7₂, 7₃, …,7_m, кроме первого компаратора 7₁, на последнем такте работы после сигнала STOP. Элемент И 11 разрешает передачу значения флага совпадений FE на вход СЕ разрешения записи в выходной буфер ОВ 4 и счет шаблонов в счетчике СТК 14.

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

При подаче сигнала на вход CLR асинхронной установки в нулевое состояние устанавливается первый RS-триггер пуска-останова TSS=0 и второй D-триггер задержки TR2=0.

Тактовые сигналы с входа С постоянно поступают на входы синхронизации С первого RS-триггера пуска-останова TSS 1, второго D-триггера TR2 задержки 2, счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистра данных 5, второго R2 регистра данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14, режимы работы которых задаются сигналами на соответствующих входах управления, а исполняются по фронтам тактовых сигналов С.

На фиг. 2 приведена схема поиска заданного m=4 разрядного шаблона IG=1011 в N=32 разрядном двоичном числе, содержащем L=8 четырехразрядных групп G1, G2, …, G8. На фиг. 2 в результате детектирования выявлены восемь шаблонов, из которых в предлагаемом устройстве два исключены как перекрывающиеся (группы G1-G2 и G5-G6, G6-G7). При этом девятая группа G9 устройством не анализируется, так как она поступает одновременно с сигналом STOP. На фиг. 3 приведена временная диаграмма работы предлагаемого устройства для входных данных, приведенных на фиг. 2.

Устройство начинает работать после подачи единичного сигнала START=1 (такт 1 на фиг. 3). При этом синхронно по фронту следующего тактового сигнала С (такт 2) в единичное состояние устанавливается первый RS-триггер 1 пуска-останова TSS=1 и в нулевое состояние устанавливаются счетчик CTG групп 3, первый R1 регистр данных 5, второй R2 регистр данных 6, счетчик шаблонов СТК 13 и регистра маски RM 14 и устанавливается начальный нулевой адрес в выходном буфере ОВ 4.

Единичное значение с выхода первого RS-триггера 1 пуска-останова TSS=1 поступает на информационный D-вход второго триггера задержки TR2 и разрешает на следующих тактах осуществлять прием групп входных данных в первый R1 регистр данных 5 с внешнего входа данных ID и запись данных с первого R1 регистра данных 5 во второй R2 регистр данных. При этом на фиг. 2 и фиг. 3 старшие разряды в группах ID, в шаблоне IG, в первом R1 и втором R2 регистрах, на компараторах СОМР и внутренних шинах показаны слева.

В такте 2 на входе шаблона IG устанавливается код 1011, который далее удерживается во время работы устройства, и на вход данных ID также поступает код 1011 первой группы G1, который записывается в такте 3 в первый R1 регистр данных 5. Одновременно в такте 3 в единичное состояние переключается второй триггер задержки TR2, который разрешает на следующих тактах работать в счетном режиме счетчику CTG групп 3, на котором устанавливается код номера входной текущей группы, и разрешает передачу значения флага совпадений FE через элемент И 11 на вход СЕ разрешения записи в выходной буфер ОВ 4. Одновременно в такте 2 нулевые значения устанавливаются на выходах всех компараторов из группы 7₁, 7₂, …,7_m, по которым далее формируются нулевые значения на внутренних шинах ВС, ВМ и ВВ, а также нулевое значение флага совпадения FE=0.

В такте 3 увеличивается на единицу значение в счетчике 3 групп CTG=1. Кроме того в такте 3, так как установлено нулевое значение флага совпадения FE=0, в единичное состояние устанавливаются все разряды регистра маски RM 14, которые далее передаются на внутреннюю шину маски ВМ=1111 и разрешают работу группы элементов И 8₂, 8₃, …, 8_m.

Одновременно в такте 3 на вход данных ID поступает код 0110 второй группы G2, который записывается в такте 4 в первый R1 регистр данных 5, и одновременно код 1011 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6. При этом на внутренней 2m-разрядной шине данных BD устанавливается 8-разрядный код 1011 0110.

Далее группами по m разрядов, начиная с левого старшего разряда и сдвигом начала групп на один разряд в сторону младших разрядов, коды поступают на вторые группы входов соответствующих компараторов 7₁, 7₂, …,7_m, а на первые группы входов которых поступает m-разрядный код заданной шаблона IG=1011. При этом единичные значения формируются на выходах двух компараторов 7₁, 7₄ и устанавливается код СОМР=1001, что означает совпадение с шаблоном в двух группах (см. фиг. 2 и фиг. 3), начинающихся с старшего четвертого и младшего первого разрядов первой входной группы G1. Далее этот код 1001, при единичном значении первого RS-триггера 1 пуска-останова TSS=1 и единичных значениях на шине маски ВМ=1111, через группу элементов И 8₁, 8₂, …, 8_m передается на группу элементов ИЛИ 9₁, 9₂, …, 9_(m-1) и далее на внутренней шине ВС устанавливается упорядоченный единичный позиционный ряд ВС=1111, так как единичное значение с левого старшего разряда последовательно передается по цепочке группы элементов ИЛИ 9₁, 9₂, …, 9_(m-1). Далее в блоке счета единиц 10 единичный позиционный ряд ВС=1111 преобразуется в двоичный код ВВ=4, соответствующий левому старшему разряду выявленного шаблона. При этом исключается выявленный перекрывающийся шаблон с началом с первого разряда.

Одновременно формируется единичное значение флага совпадений FE=1. Далее единичное значение устанавливается на выходе элемента И 11, так как установлен в единичное состояние второй D-триггер задержки TR2=1, и далее разрешается запись в выходной буфер ОВ 4, в который в такте 5 по нулевому адресу записывается код ОВ(0)=1_4, соответствующий номеру первой группы G1 со счетчика групп 3 CTG=1 и коду четвертого разряда расположения начала старшего (левого) выявленного шаблона в текущей первой группе G1, который поступает с внутренней шины ВВ=4. Также в такте 5 проводится счет выявленных шаблонов на счетчике 14 СТК=1.

Кроме того так как все разряды выявленного шаблона расположены в первой группе G1, то на следующем такте разрешается проверка сравнений начиная с четвертого разряда. Поэтому в регистре маски RM 14 опять устанавливается разрешение для всех разрядов ВМ=1111.

При этом одновременно в такте 4 на вход данных ID поступает код 1100 третьей группы G3, который записывается в такте 5 в первый R1 регистр данных 5, и одновременно код 0110 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6. Одновременно в такте 5 увеличивается на единицу значение в счетчике 3 групп CTG=2. Поэтому на внутренней 2m-разрядной шине данных BD устанавливается код 0110 1100. При этом совпадение с шаблоном IG=1011 будет выявлено только в одной группе на втором компараторе lz и устанавливается код СОМР=0010. Поэтому далее при единичном значении первого RS-триггера 1 пуска-останова TSS=1 и единичных значениях на шине маски ВМ=1111, через группу элементов И 8₁, 8₂, …, 8_m, группу элементов ИЛИ 9₁, 9₂, …, 9_(m-1) и далее на внутренней шине ВС устанавливается упорядоченный единичный позиционный ряд ВС=0011. Далее в блоке счета единиц 10 единичный позиционный ряд ВС=0011 преобразуется в двоичный код ВВ=2, соответствующий второму разряду выявленного шаблона.

Далее при единичном значении флага совпадений FE=1 в такте 6 в выходной буфер ОВ 4 по первому адресу записывается код ОВ(1)=2_2, соответствующий входной второй группе G2 CTG=2 и второму разряду начала группы, соответствующей заданному шаблону IG=1011, который поступает с внутренней шины ВВ=2. Также в такте 6 проводится счет выявленных шаблонов на счетчике 14 СТК=2.

Кроме того так как два разряда выявленного шаблона расположены во второй группе G2, а два разряда в третьей группе G3, то на следующем такте разрешается проверка сравнений начиная со второго разряда. Поэтому в регистре маски RM 14 устанавливается разрешение для двух разрядов ВМ=0011.

Одновременно в такте 5 на вход данных ID поступает код 1101 четвертой группы G4, который записывается в такте 6 в первый R1 регистр данных 5, и одновременно код 1100 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6, а также увеличивается на единицу значение в счетчике 3 групп CTG=3. Поэтому далее на внутренней 2m-разрядной шине данных BD устанавливается код 1100 1101. При этом на выходах всех компараторов 7₁, 7₂, …,7_m устанавливаются нулевые значения, код СОМР=0000, так как не обнаружено совпадений с шаблоном IG=1011. Поэтому формируется также нулевое значение флага совпадений FE=0 и в такте 7 отсутствует запись в выходной буфер ОВ 4.

Одновременно в такте 7 по нулевому значению флага совпадения FE=0 в единичное состояние устанавливаются все разряды регистра маски RM 14, которые далее передаются на внутреннюю шину маски ВМ=1111 и разрешают работу группы элементов И 8₁, 8₂, …, 8_m.

В такте 6 на вход данных ID поступает код 1101 пятой группы G5, который записывается в такте 7 в первый R1 регистр данных 5, и одновременно код 1101 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6, а также увеличивается на единицу значение в счетчике 3 групп CTG=4 и далее на внутренней 2m-разрядной шине данных BD устанавливается код 1101 1101. При этом в группе компараторов 7₁, 7₂, …,7_m совпадение с шаблоном IG=1011 будет выявлено только в одной группе на третьем компараторе 7₃ и устанавливается код СОМР=0100, по которому на внутренней шине ВС устанавливается упорядоченный единичный позиционный ряд ВС=0111. Далее в блоке счета единиц 10 единичный позиционный ряд ВС=0111 преобразуется в двоичный код ВВ=3, соответствующий третьему разряду выявленного шаблона.

Далее при единичном значении флага совпадений FE=1 в такте 8 в выходной буфер ОВ 4 по второму адресу записывается код ОВ(2)=4_3, соответствующий входной четвертой группе G4 CTG=4 и третьему разряду начала группы, соответствующей заданному шаблону IG=1011, который поступает в внутренней шины ВВ=3. Также в такте 8 проводится счет выявленных шаблонов на счетчике 14 СТК=3.

Далее в тактах 9 и 10 аналогично рассмотренному алгоритму при единичных значениях флага совпадений FE=1 осуществляется запись для выявленных входных пятой G5 и шестой G6 группах соответствующих кодов по третьему ОВ(3)=5_3 и четвертому ОВ(4)=6_1 адресам в выходной буфер ОВ 4.

Одновременно в такте 9 на вход данных ID поступает код 1011 восьмой группы G8, который записывается в такте 10 в первый R1 регистр данных 5, и одновременно код 0110 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6, а также увеличивается на единицу значение в счетчике 3 групп CTG=7. Далее на внутренней 2m-разрядной шине данных BD устанавливается код 0110 1011. При этом на выходах всех компараторов 7₁, 7₂, …,7_m устанавливаются нулевые значения, код СОМР=0000, так как не обнаружено совпадений с шаблоном IG=1011. Поэтому формируется также нулевое значение флага совпадений FE=0 и в такте 11 отсутствует запись в выходной буфер ОВ 4. Одновременно в такте 11 в единичное состояние устанавливаются все разряды регистра маски RM 14, которые далее передаются на внутреннюю шину маски ВМ=1111 и разрешают работу группы элементов И 8₁, 8₂, …, 8_m.

Одновременно в такте 10 поступает единичный сигнал STOP=1, по которому по фронту тактового сигнала С в такте 11 в нулевое состояние устанавливается первый RS-триггер 1 пуска-останова TSS=0. При этом код 0110 с входа данных ID для девятой группы G9 записывается в такте 11 в первый R1 регистр данных 5, и одновременно код 1011 для восьмой группы G8 с выходов первого R1 регистра данных 5 записывается во второй R2 регистр данных 6, а также увеличивается на единицу значение в счетчике 3 групп CTG=8. При этом в группе компараторов 7₁, 7₂, …,7_m совпадение с шаблоном IG=1011 будет выявлено в двух группах на первом и четвертом компараторах 7₁ и 7₄ и на выходах компараторов формируется код СОМР=1001. Но так как в такте 11 нулевое состояние установлено в первом RS-триггер 1 пуска-останова TSS=0, то запрещается передача значений в первых (m-1) элементах группы И 8₁, 8₂, …, 8_(m-1), т.е. разрешается детектирование только в четвертом компараторе СОМР 7₄. Далее на внутренней шине ВС устанавливается упорядоченный единичный позиционный ряд ВС=1111, который передается в блок счета единиц 10, в котором единичный позиционный ряд ВС=1111 преобразуется в двоичный код ВВ=4, соответствующий четвертому разряду выявленного шаблона.

Далее при единичном значении флага совпадений FE=1 в такте 12 в выходной буфер ОВ 4 по пятому адресу записывается код ОВ(5)=8_4, соответствующий входной восьмой группе G8 CTG=8 и второму разряду начала группы, соответствующей заданному шаблону IG=1011, который поступает с внутренней шины ВВ=4. Также в такте 12 проводится счет выявленных шаблонов на счетчике 14 СТК=6, которое передается на группу внешних выходов количества выявленных шаблонов QK.

Таким образом, для входного N=32 разрядного двоичного числа приведенного на фиг. 2 в выходной буфер ОВ 4 записаны по шести адресам ОВ(0), …, ОВ(5) номера входных групп и коды номеров разрядов соответствующие расположению начала шаблонов в группах соответствующих заданному шаблону IG=1011.

Считывание результатов на группу внешних выходов данных QB из выходного буфера ВО 4 выполняется под управлением по внешней шине управления ЕО. При реализации выходного буфера ВО 11 в виде двухпортовой памяти FIFO, обмен можно выполнять в процессе детектирования групп с учетом значений флагов «Буфер пуст» FZ и «Буфер заполнен» FF.

Обработка следующего входного N разрядного двоичного числа начинается после подачи единичного сигнала START=1.

Предлагаемое устройство может быть применено для аппаратной реализации статистических тестов разработанных лабораторией информационных технологий Национального института стандартов и технологий (NIST, США), целью которых является определение меры случайности двоичных последовательностей порожденных генераторами случайных чисел. В частности предлагаемое устройство реализует тест на совпадение неперекрывающихся заданных шаблонов размерностью m бит с группами из входных данных также размерностью m бит. При этом если шаблон не обнаружен то соседние анализируемые группы из входных данных сдвигаются на один бит вперед, а если шаблон найден, то соседняя группа перемещается на бит следующий за найденным шаблоном. Цель - выявить генераторы случайных или псевдослучайных чисел, формирующие слишком часто заданные непериодические шаблоны.

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

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

Изобретение относится к области вычислительной техники и может быть использовано для построения функциональных узлов для анализа свойств генераторов псевдослучайных последовательностей двоичных чисел, фильтрации событий, обработки сигналов, изображений и результатов физических экспериментов. Техническим результатом является обеспечение возможности выявления неперекрывающихся шаблонов, содержащих заданные группы (последовательность) из единичных и нулевых бит и их расположение в группах входных данных. Устройство содержит внешние m разрядный вход данных ID и m разрядный вход заданного шаблона IG, группы внешних выходов данных QB и количества выявленных шаблонов QK, первый RS-триггер пуска-останова TSS, второй D-триггер TR2 задержки, счетчик CTG групп, выходной буфер ОВ, первый R1 регистр данных, второй R2 регистр данных, группу из m компараторов, группу из m элементов И, группу из (m-1) элементов ИЛИ, блок счета единиц, элемент И, элемент ИЛИ-НЕ, счетчик шаблонов СТК и регистр маски RM. 3 ил.

Устройство параллельно-последовательной структуры для детектирования неперекрывающихся шаблонов бит содержит внешний m-разрядный вход данных ID, внешний m-разрядный вход заданного шаблона IG, группу внешних выходов данных QB, группу внешних выходов количества выявленных шаблонов QK, первый RS-триггер пуска-останова TSS 1, второй D-триггер TR2 задержки 2, счетчик CTG групп 3, выходной буфер ОВ 4, первый R1 регистр данных 5, второй R2 регистр данных 6, группу из m компараторов 7₁, 7₂, …, 7_m, группу из m элементов И 8₁, 8₂, …, 8_m, группу из (m-1) элементов ИЛИ 9₁, 9₂, …, 9_(m-1), блок счета единиц 10, элемент И 11, элемент ИЛИ-НЕ 12, счетчик шаблонов СТК 13 и регистр маски RM 14,

а также введены внешние входы асинхронной установки в нулевое состояние CLR, пуска устройства START, остановки устройства STOP и тактовый вход С, внутренняя 2m-разрядная шина данных BD, внутренняя шина v-разрядного двоичного кода начала шаблона в группе ВВ (где v=]log2 m[(большее целое)), внутренняя m-разрядная шина кода единичного позиционного ряда ВС, внутренняя m-разрядная шина маски ВМ, внутренний флаг совпадения FE, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ,

причем внешний вход асинхронной установки в нулевое состояние CLR соединен с соответствующими входами асинхронной установки в нулевое состояние CLR первого RS-триггера пуска-останова TSS 1 и второго D-триггера TR2 задержки,

внешний тактовый вход устройства С соединен с входами синхронизации С первого RS-триггера пуска-останова TSS 1, второго D-триггера TR2 задержки 2, счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистра данных 5, второго R2 регистра данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14,

внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние первого RS-триггера пуска-останова TSS 1 и с входами R синхронной установки в нулевое состояние счетчика CTG групп 3, выходного буфера ОВ 4, первого R1 регистра данных 5, второго R2 регистра данных 6, счетчика шаблонов СТК 13 и регистра маски RM 14,

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

причем прямой выход первого RS-триггера пуска-останова TSS 1 соединен с D-входом второго триггера TR2 задержки 2, с входами СЕ разрешения работы первого R1 регистра данных 5, второго R2 регистра данных 6, регистра маски RM 14 и третьими входами первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1),

выход второго D-триггера TR2 задержки соединен с входом СЕ разрешения работы счетчика CTG групп 3 и первым входом элемента И 11, выход которого соединен с входом СЕ разрешения записи в выходной буфер ОВ 4 и разрешения счета СЕ счетчика шаблонов СТК 13, выходы которого являются группой внешних выходов количества выявленных шаблонов QK,

причем внешний m-разрядный вход заданного шаблона IG соединен с первыми группами входов всех m компараторов группы 7₁, 7₂, …, 7_m, выходы которых соединены со вторыми входами соответствующих одноименных элементов И группы 8₁, 8₂, …, 8_m,

внешний m-разрядный вход данных ID соединен с группой информационных D-входов первого R1 регистра данных 5, выходы которого являются соответствующими разрядами, начиная с первого до m-го разряда, внутренней шины данных BD, а также соединены с группой информационных D-входов второго R2 регистра данных 6, выходы которого являются соответствующими разрядами, начиная с (m+1)-го до 2m-го разряда, внутренней шины данных BD,

причем разряды внутренней шины данных BD группами по m разрядов, каждая из которых начинается с (i+1)-го разряда (i=1, …, m), соединены со вторыми группами входов соответствующих i-ых компараторов группы 7₁, 7₂, …, 7_m,

выходы первых (m-1) элементов И группы 8₁, 8₂, …, 8_(m-1) соединены с первыми входами одноименных элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1), а выход последнего m-го элемента И 8_m соединен со вторым входом последнего элемента 9_(m-1), а также является m-м разрядом внутренней шины кода единичного позиционного ряда ВС, у которой разрядами, начиная с первого до (m-1)-го разряда, являются выходы одноименных (m-1) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-1),

кроме того вторые входы первых (m-2) элементов ИЛИ группы 9₁, 9₂, …, 9_(m-2), начиная с первого до (m-2)-го элементов, соединены с выходами соответствующих последующих (m-2) элементов ИЛИ группы 9₂, 9₃, …, 9_(m-1), начиная со второго до (m-1)-го элементов,

причем все m разрядов внутренней шины кода единичного позиционного ряда ВС соединены с соответствующими входами блока счета единиц 10, с группой информационных D-входов регистра маски RM 14 и с входами элемента ИЛИ-НЕ 12, прямой выход которого является внутренним флагом совпадения FE и соединен со вторым входом элемента И 11, а инверсный выход элемент ИЛИ-НЕ 12 соединен с входом S синхронной установки в единичное состояние регистра маски RM 14,

кроме того выходы регистра маски RM 14 являются соответствующими одноименными разрядами внутренней m-разрядной шины маски ВМ, которые соединены с первыми входами одноименных m элементов И группы 8₁, 8₂, …, 8_m,

причем выходы блока счета единиц 10 являются соответствующими разрядами внутренней шины двоичного кода начала шаблона в группе ВВ, которая соединена со второй группой информационных D-входов выходного буфера ОВ 4, у которого первая группа информационных D-входов соединена с выходами счетчика CTG групп 3,

кроме того выходной буфер ОВ 4 также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 4 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ.