Устройство для детектирования перекрывающихся шаблонов бит в двоичной последовательности

Изобретение относится к области вычислительной техники. Технический результат заключается в детектировании IК-разрядных групп во входном N-разрядном двоичном числе, соответствующие IК разрядному заданному шаблону групп IS, который содержит заданную последовательность единичных и нулевых бит. Устройство содержит внешний вход данных ID, группу внешних входов шаблона IS, содержащую К разрядов, группу внешних входов IK задания разрядности входного шаблона IS, содержащую m разрядов, группу внешних выходов данных QB, группу внешних выходов количества шаблонов QS, а также содержит RS-триггер пуска-останова TSS 1, первый счетчик бит СТВ 2, выходной буфер ОВ 3, второй вычитающий счетчик разрядов шаблона СТК 4, элемент И 5, регистр сдвига входных данных RD 6, дешифратор DC 7, группу из (К-1) элементов ИЛИ 81, 82, 8(К-1), первую группу из К элементов И, вторую группу из К элементов И, компаратор СОМР 11 и третий счетчик количества шаблонов CTS 12, а также введены внешние входы тактового сигнала IC, пуска устройства START, остановки устройства STOP и внутренние шина дешифрации разрядов BDC. 3 ил.

 

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

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

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

Известно устройство последовательного типа для детектирования групп нулевых и единичных бит и определение их количества (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=[log₂N]+1 (меньшее целое), а N - размерность длина входной последовательности данных, причем первый счетчик групп CG 9, второй счетчик бит СВ 10, выходной буфер ОВ 11, третий счетчик нулей CZ 15 и четвертый счетчик единиц CU 16 имеют разрядность М, а пятый реверсивный счетчик нулей-единиц CZU 17 имеет разрядность (М+1), а также введены внешние флаги готовности результата FE, «Буфер заполнен» FF, «Буфер пуст» FZ и флаг «нулей больше единиц» F01. При этом в выходном буфере ОВ 11 в четных адресах, начиная с нулевого адреса, указывается количество нулевых бит в группах, а в нечетных адресах, начиная с первого адреса, указывается количество единичных бит в группах.

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

Известно устройство для детектирования групп в бинарной последовательности (RU №2728957, МПК G06F 7/74, Н03К 21/00 заявлено 15.01.2020, опубликовано 03.08.2020, Бюл. №22), содержащее внешний вход данных DI, группу внешних выходов данных QO, группу внешних выходов количества групп QG, группу внешних выходов количества нулей QZ, группу внешних выходов количества единиц QU, группу внешних выходов «разность единиц и нулей» QZU, группы внешних выходов количества единиц в максимальной группе MU, количества нулей в максимальной группе MZ, номера группы максимальной группы единиц NGMU, номера группы максимальной группы нулей NGMZ, номера начала максимальной группы единичных бит NMU и номера начала максимальной группы нулевых бит NMZ, первый RS-триггер пуска-останова TSS 1, блок детектора единиц и нулей 2, третий D-триггер разрешения счета групп ТСЕ 7, третий элемент И 8, первый сумматор SMG 9, второй счетчик бит СВ 10, выходной буфер ОВ 11, четвертый 12, пятый 13 и шестой 14 элементы И, третий счетчик нулей CZ 15, четвертый счетчик единиц CU 16, пятый реверсивный счетчик нулей-единиц CZU 17 и блок преобразователя кода разности 18, первый счетчик CNB 22, первый регистр RNM 23, второй сумматор SNM 24, второй 25, третий 26, четвертый 27, пятый 28, шестой 29, седьмой 32 и восьмой 35 регистры, первый компаратор 30 сравнения количества единичных бит, седьмой элемент И 31, второй компаратор 33 сравнения количества нулевых бит, восьмой элемент И с одним инверсным входом 34, а также введены внешние флаги готовности результата FE, «Буфер заполнен» FF, «Буфер пуст» FZ и флаг «нулей больше единиц» F01.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для детектирования единичных групп бит в бинарной последовательности RU №2763859 МПК G06F 7/74, Н03К 21/00 заявлено 29.04.2021, опубликовано 11.01.2022, Бюл. №2) содержащее внешний вход данных DI, группу внешних выходов данных QB, группу внешних выходов количества групп QG, первый RS-триггер пуска-останова TSS 1, первый счетчик бит СТВ 2, регистр номера первого бита группы RGB 3, первый элемент И 4, первый элемент ИЛИ 5 с одним инверсным входом, второй триггер единичных бит TR1 6, второй элемент И 7 с одним инверсным входом, второй счетчик единиц CTU 8, блок равенства нижней границе 9, блок равенства верхней границе 10, третий триггер нижней границы TRL 11, четвертый триггер верхней границы TRM 12, третий 13 и четвертый 14 элементы И с двумя инверсными входами, второй элемент ИЛИ 15, выходной буфер ОВ 16 и третий счетчик количества групп CTG 17, а также введены внешние входы асинхронной установки в нулевое состояние CLR, пуска устройства START, остановки устройства STOP и тактовый С, внешние входные шины нижней границы GL и верхней границы GM диапазона единичных бит, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ

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

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

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

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что устройство для детектирования перекрывающихся шаблонов бит в двоичной последовательности содержит внешний вход данных ID, группу внешних входов шаблона IS, содержащую К разрядов, группу внешних входов IК задания разрядности входного шаблона IS, содержащую m разрядов (где m=]log₂(К+1)[большее целое), группу внешних выходов данных QB, группу внешних выходов количества шаблонов QS,

а также содержит RS-триггер пуска-останова TSS 1, первый счетчик бит СТВ 2, выходной буфер ОВ 3, второй вычитающий счетчик разрядов шаблона СТК 4, элемент И 5, регистр сдвига входных данных RD 6, дешифратор DC 7, группу из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(К-1), первую группу из К элементов И 9₁, 9₂, …, 9_к, вторую группу из К элементов И 10₁, 10₂, …, 10_к, компаратор СОМР 11 и третий счетчик количества шаблонов CTS 12,

а также введены внешние входы тактового сигнала IC, пуска устройства START, остановки устройства STOP и внутренние шина дешифрации разрядов BDC, шина первого операнда сравнения ВА, шина второго операнда сравнения ВВ, внутренний флаг равенства FEQ и внутренний флаг записи FW, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ,

причем внешний тактовый вход устройства IC соединен с входами синхронизации С RS-триггера пуска-останова TSS 1, первого счетчика бит СТВ 2, выходного буфера ОВ 3, второго вычитающего счетчика разрядов шаблона СТК 4, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12,

внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние RS-триггера пуска-останова TSS 1, с входом L разрешения записи второго вычитающего счетчика разрядов шаблона СТК 4, с входами R синхронной установки в нулевое состояние первого счетчика бит СТВ 2, выходного буфера ОВ 3, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12,

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

причем прямой выход RS-триггера пуска-останова TSS 1 соединен с входами СЕ разрешения работы первого счетчика бит СТВ 2 и регистра сдвига входных данных RD 6,

внешний вход данных ID соединен с входом SI последовательного ввода регистра сдвига входных данных RD 6, группа К выходов которого соединена с первыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к, выходы которых являются соответствующими одноименными разрядами внутренней шины первого операнда сравнения ВА, которая соединена с первой группой входов компаратора СОМР 11,

К разрядов группы внешних входов шаблона IS соединены с первыми входами соответствующих одноименных элементов второй группы из К элементов И 10₁, 10₂, …, 10_к, выходы которых являются соответствующими одноименными разрядами внутренней шины второго операнда сравнения ВВ, которая соединена со второй группой входов компаратора СОМР 11, выход которого является внутренним флагом равенства FEQ и соединен со вторым входом элемента И 5,

причем группа внешних входов IK задания разрядности входного шаблона IS соединена с соответствующей группой D-входов второго счетчика разрядов шаблона СТК 4 и адресными входами дешифратора DC 7, у которого выходы, с первого выхода до (К-1)-го выхода, соединены с первыми входами соответствующих одноименных элементов группы из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(К-1), выходы которых являются соответствующими одноименными разрядами, с первого разряда до (К-1)-го разряда, внутренней шины дешифрации разрядов BDC, у которой К-й разряд соединен с К-м выходом дешифратора DC 7, а К разрядов внутренней шины дешифрации разрядов BDC соединены со вторыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к и второй группы из К элементов И 10₁, 10₂, …, 10_к, а также выходы элементов группы 8₁, 8₂, …, 8_(К-1) из (К-1) элементов ИЛИ, начиная с выхода (К-1)-го элемента 8_(К-1) до второго элемента 8₂, соединены со вторыми входами соответствующих предыдущих элементов ИЛИ группы 8₁, 8₂, …, 8_(К-1), начиная с (К-2)-го элемента 8_(К-2) до первого элемента 8₁, а второй вход (К-1)-го элемента 8_(К-1) соединен с К-м выходом дешифратора DC 7,

кроме того прямой выход заема ВО вычитающего счетчика разрядов шаблона СТК 4 соединен с инверсным входом разрешения работы СЕ счетчика разрядов шаблона СТК 4 и с первым входом элемента И 5, выход которого является внутренним флагом записи FW и соединен с входами СЕ разрешения работы выходного буфера ОВ 3 и третьего счетчика количества шаблонов CTS 12,

причем группа выходов первого счетчика бит СТВ 2 соединена с группой информационных D-входов выходного буфера ОВ 3, который также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 3 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ, а группа выходов счетчика количества шаблонов CTS 12 является группой внешних выходов количества шаблонов QS.

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

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

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

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

ВА - внутренняя шина первого операнда сравнения,

ВВ - внутренняя шина второго операнда сравнения,

ВО - выход заема счетчика,

BDC - внутренняя шина дешифрации разрядов,

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

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

СОМР - схема сравнения (компаратор),

СТ - счетчик,

СТВ - счетчик бит (разрядов),

СТК - вычитающий счетчик разрядов шаблона,

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

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

DC - дешифратор,

IC - внешний тактовый вход,

ID - внешний вход данных,

IК - группа внешних входов задания разрядности входного шаблона IS, содержащая m разрядов (где m=]log₂(К+1)[большее целое),

IS - группа внешних входов шаблона, содержащая К разрядов,

ЕО - внешняя шина управления обменом с выходным буфером ОВ,

FEQ - внутренний флаг равенства,

FW - внутренний флаг записи,

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

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

К - разрядность шаблона,

L - вход разрешения записи,

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

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

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

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

RD - регистр сдвига входных данных,

RG - регистр,

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

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

SI - вход последовательного ввода регистра RD,

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

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

Т - триггер,

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

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

2 - первый счетчик бит СТВ,

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

4 - второй вычитающий счетчик разрядов шаблона СТК,

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

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

7 - дешифратор DC,

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

9₁, 9₂, …, 9_к - первая группа из К элементов И (AND),

10₁, 10₂, …, 10_к - вторая группа из К элементов И (AND),

11 - компаратор (СОМР),

12 - третий счетчик количества шаблонов CTS.

Предлагаемое устройство содержит внешний вход данных ID, группу внешних входов шаблона IS, содержащую К разрядов, группу внешних входов IК задания разрядности входного шаблона IS, содержащую m разрядов (где m=]log₂(К+1)[большее целое), группу внешних выходов данных QB, группу внешних выходов количества шаблонов QS, а также содержит RS-триггер пуска-останова TSS 1, первый счетчик бит СТВ 2, выходной буфер ОВ 3, второй вычитающий счетчик разрядов шаблона СТК 4, элемент И 5, регистр сдвига входных данных RD 6, дешифратор DC 7, группу из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(К-1), первую группу из К элементов И 9₁, 9₂, …, 9_к, вторую группу из К элементов И 10₁, 10₂, …, 10_к, компаратор СОМР 11 и третий счетчик количества шаблонов CTS 12.

В предлагаемое устройство также введены внешние входы тактового сигнала IC, пуска устройства START, остановки устройства STOP и внутренние шина дешифрации разрядов BDC, шина первого операнда сравнения ВА, шина второго операнда сравнения ВВ, внутренний флаг равенства FEQ и внутренний флаг записи FW, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ.

Первый счетчик бит СТВ 2 предназначен для определения номера текущего бита (разряда) входной последовательности данных ID размерности N. Второй вычитающий счетчик СТК 4 предназначен для подсчета первых IК бит (разрядов) входной последовательности данных ID и запрета в этот период (при ВО(СТК)=0) формирования единичного значения внутреннего флага записи FW. Регистр сдвига входных данных RD 6 предназначен для преобразования входной последовательности данных ID в параллельные К-разрядные группы. Выходной буфер ОВ 3 предназначен для накопления номеров старших бит (разрядов) выявленных групп соответствующих заданному шаблону IS из входной последовательности данных ID.

Внешний тактовый вход устройства IC соединен с входами синхронизации С RS-триггера пуска-останова TSS 1, первого счетчика бит СТВ 2, выходного буфера ОВ 3, второго вычитающего счетчика разрядов шаблона СТК 4, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12.

Внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние RS-триггера пуска-останова TSS 1, с входом L разрешения записи второго вычитающего счетчика разрядов шаблона СТК 4, с входами R синхронной установки в нулевое состояние первого счетчика бит СТВ 2, выходного буфера ОВ 3, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12.

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

RS-триггер пуска-останова TSS 1 предназначен для выделения цикла работы предлагаемого устройства, между сигналами START и STOP, для входной последовательности данных ID размерности N. Причем прямой выход RS-триггера пуска-останова TSS 1 соединен с входами СЕ разрешения работы первого счетчика бит СТВ 2 и регистра сдвига входных данных RD 6.

Внешний вход данных ID соединен с входом SI последовательного ввода регистра сдвига входных данных RD 6, группа К выходов которого соединена с первыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к, выходы которых являются соответствующими одноименными разрядами внутренней шины первого операнда сравнения ВА, которая соединена с первой группой входов компаратора СОМР 11.

К разрядов группы внешних входов шаблона IS соединены с первыми входами соответствующих одноименных элементов второй группы из К элементов И 10₁, 10₂, …, 10_к, выходы которых являются соответствующими одноименными разрядами внутренней шины второго операнда сравнения ВВ, которая соединена со второй группой входов компаратора СОМР 11, выход которого является внутренним флагом равенства FEQ и соединен со вторым входом элемента И 5.

Группа внешних входов IK задания разрядности входного шаблона IS соединена с соответствующей группой D-входов второго счетчика разрядов шаблона СТК 4 и адресными входами дешифратора DC 7, у которого выходы, с первого выхода до (К-1)-го выхода, соединены с первыми входами соответствующих одноименных элементов группы из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(К-1), выходы которых являются соответствующими одноименными разрядами, с первого разряда до (К-1)-го разряда, внутренней шины дешифрации разрядов BDC, у которой К-й разряд соединен с К-м выходом дешифратора DC 7.

К разрядов внутренней шины дешифрации разрядов BDC соединены со вторыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к и второй группы из К элементов И 10₁, 10₂, …, 10_к. Выходы элементов группы 8₁, 8₂, …, 8_(К-1) из (К-1) элементов ИЛИ, начиная с выхода (К-1)-го элемента 8(к-1) до второго элемента 8₂, соединены со вторыми входами соответствующих предыдущих элементов ИЛИ группы 8₁, 8₂, …, 8_(К-1), начиная с (К-2)-го элемента 8_(к-2) до первого элемента 8₁, а второй вход (К-1)-го элемента 8_(к-1) соединен с К-м выходом дешифратора DC 7.

Прямой выход заема ВО вычитающего счетчика разрядов шаблона СТК 4 соединен с инверсным входом разрешения работы СЕ счетчика разрядов шаблона СТК 4 и с первым входом элемента И 5, выход которого является внутренним флагом записи FW и соединен с входами СЕ разрешения работы выходного буфера ОВ 3 и третьего счетчика количества шаблонов CTS 12.

Группа выходов первого счетчика бит СТВ 2 соединена с группой информационных D-входов выходного буфера ОВ 3, который также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 3 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ. Группа выходов счетчика количества шаблонов CTS 12 является группой внешних выходов количества шаблонов QS.

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

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

Предлагаемое устройство позволяет детектировать IK-разрядные группы во входном N-разрядном двоичном числе, соответствующие IK разрядному заданному шаблону групп IS, который содержит заданную последовательность единичных и нулевых бит. Устройство позволяет оперативно изменять (задавать) разрядность IK≤K и значения разрядов шаблона IS. В устройстве подсчитывается количество групп соответствующих заданному коду шаблону IS и определяются номера старших разрядов выявленных входных групп во входном N-разрядном двоичном числе, которые записываются в выходной буфер ОВ 3. При этом разряды выявленных соседних входных групп, совпадающих с заданным шаблоном IS, могут перекрываться.

На внешний вход данных ID последовательно разряд за разрядом поступают биты входной последовательности данных размерностью N, которые далее передаются на вход последовательного ввода SI сдвига К разрядного регистра RD 6. На регистре сдвига RD 6 осуществляется сдвиг на один разряд в сторону старших разрядов от 1-го разряда к К-му разряду. При этом разряды кода входной двоичной последовательности ID преобразуются в параллельные К-разрядные коды на выходах регистра RD 6.

На внешний вход данных ID биты начинают поступать в следующем такте после сигнала START=1 и далее поступают в каждом такте IC. После ввода последнего N-го разряда входного двоичного числа задается единичный сигнал остановки STOP=l.

Устройство начинает работать после подачи единичного сигнала START=1, при котором по фронту тактового сигнала IC в вычитающий счетчик разрядов шаблона СТК 4 загружается код «IK» текущей разрядности заданного шаблона IS, значение которого устанавливается на внешней входной К разрядной шине IS. На следующих IK тактовых сигналах IC осуществляется сдвиг в регистре RD 6, подсчет бит (разрядов) входной последовательности ID в счетчике бит СТВ и вычитание в счетчике разрядов шаблона СТК 4, пока не установится единичное значение на выходе заема ВО=1 счетчика СТК 4.

Одновременно код «IK» текущей разрядности заданного шаблона IS передается на входы дешифратора DC 7. На выходах дешифратора 7 формируются унитарные коды «1 из К», которые передаются на соответствующие входы группы 8₁, 8₂, …, 8_(К-1) из (К-1) элементов ИЛИ. Единичное значение, установленное на выходе дешифратора DC 7 соответствующем коду IK, далее последовательно передается по цепочке элементов ИЛИ 8₁, 8₂, …, 8_(К-1) в сторону младших разрядов. При этом на внутренней шине дешифрации разрядов BDC устанавливается упорядоченная последовательность единичных значений, начиная с первого разряда до IK-го разряда (при IK≤K) и нулевые значения с (IK+1)-го разряда до старшего К-го разряда (унитарный позиционный ряд 00…011…1). Далее значения разрядов с внутренней шины BDC поступают на вторые входы соответствующих одноименных элементов И первой группы 9₁, 9₂, …, 9_к и второй группы 10₁, 10₂, …, 10_к. При этом при единичных значениях разрядов в первой группе элементов И 9₁, 9₂, …, 9_к на внутреннюю шину первого операнда сравнения ВА передаются IK разрядов входной последовательности данных ID с выходов регистра RD 6, а во второй группе элементов И 10₁, 10₂, …, 10_к на внутреннюю шину второго операнда сравнения ВВ передаются IK разрядов заданного шаблона IS. При этом на шинах ВА и ВВ с (IK+1)-го разряда до старшего К-го разряда формируются нулевые значения.

Далее на компараторе СОМР 11 осуществляется сравнение кодов с внутренних шин первого ВА и второго ВВ операндов и при совпадении формируется единичное значение внутреннего флага равенства FEQ=1. Далее, при единичном значении на выходе заема ВО=1 второго вычитающего счетчика разрядов шаблона СТК 4, формируется единичное значение внутреннего флага записи FW=1 на выходе элемента И 5, по которому осуществляется запись номера старшего бита выявленной группы из входной последовательности данных ID, соответствующей заданному шаблону IS, с выходов первого счетчика бит СТВ 2 в выходной буфер ОВ 3 и увеличение счетчика количества выявленных шаблонов CTS 12.

Так как в предлагаемом устройстве детектирование выполняется для перекрывающихся шаблонов, то по следующим тактовым сигналам IC в регистр данных RD 6 при сдвиге записывается один следующий разряд входной последовательности данных ID и далее вновь осуществляется сравнение с шаблоном IS на компараторе СОМР 11 и формирование единичных или нулевых значений внутреннего флага равенства FEQ и внутреннего флага записи FW.

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

На фиг. 2 и фиг. 3 приведены временные диаграммы работы устройства для поиска групп во входном N=12 разрядном двоичном числе соответствующих К=4 разрядным шаблонам IS и кодом m=]log₂(4+1)[=3 для разрядности шаблона IK. На фиг. 2 заданный шаблон содержит IK=3 (011) разрядов и значения разрядов IS=0101. На фиг. 3 заданный шаблон содержит IK=4 (100) разрядов и значения разрядов IS=0101.

Перед началом работы соответствующие заданные значения для шаблонов задаются на группе внешних входов шаблона IS, содержащей К=4 разряда, и на группе внешних входов задания разрядности входного шаблона IS, содержащей m разрядов, которые сохраняются на внешних входах в течении всего времени работы устройства - задания входного N=12 разрядного двоичного числа.

Работа устройства для каждой входной последовательности начинается после подачи единичного сигнала START=1. При этом по фронту тактового сигнала IC (такт 2 на фиг. 2-3) в единичное состояние устанавливается RS-триггер 1 пуска-останова TSS=1, в нулевое состояние устанавливаются первый счетчик бит СТВ 2 и третий счетчик количества шаблонов CTS 12, устанавливается начальный нулевой адрес в выходном буфере ОВ 3 и записывается разрядность IK шаблона IS (на фиг. 2 IK=3 (011), на фиг. 3 IK=4 (100)) в вычитающий второй счетчик разрядов шаблона СТК 4, на выходе заема ВО которого устанавливается нулевое значение ВО(СТК)=0.

Одновременно код IK=011 (фиг. 2) текущей разрядности заданного шаблона IS передается на входы дешифратора DC 7. На выходах дешифратора 7 формируются унитарные коды «1 из К=4», которые передаются на соответствующие вторые входы группы 8₁, 8₂, …, 8_(К-1) из (К-1) элементов ИЛИ и далее сформированный код передается на внутреннюю шину дешифрации разрядов BDC. Для кода IK=011 на шине BDC будет установлено значение унитарного позиционного ряда BDC=0111, по которому на следующих тактах разрешается передача только трех младших разрядов на внутреннюю шину первого операнда сравнения ВА с выходов регистра RD 6 и на внутреннюю шину второго операнда сравнения ВВ с внешних входов заданного шаблона IS. При этом на шине второго операнда сравнения ВВ устанавливается код ВВ=0101.

Единичное значение с выхода RS-триггера 1 пуска-останова TSS=1 поступает на входы разрешения работы СЕ первого счетчика бит СТВ 2 и регистра данных RD 6, в которых далее на следующих тактах осуществляется подсчет бит в первом счетчике бит СТВ 2 и прием входных данных ID в регистр сдвига входных данных RD 6.

В такте 3 единичное значение ID=1 с входа данных, заданное в такте 2, записывается в регистр сдвига входных данных RD 6 и на выходах устанавливается код RD=0001, который далее передается на внутреннюю шину первого операнда сравнения ВА=0001, сравнивается с кодом на внутренней шине второго операнда ВВ и устанавливается нулевое значение внутреннего флага равенства FEQ=0 на выходе компаратора СОМР 11. Одновременно увеличивается на единицу значение первого 2 счетчика бит СТВ=1 и уменьшается на единицу значение счетчика 4 разрядов шаблона СТК=2, при этом сохраняется нулевое значение на выходе заема ВО(СТК)=0. Также в такте 3 задается нулевое значение следующего второго бита на входе данных ID=0.

В такте 4 аналогично работают элементы устройства и устанавливаются следующие коды: первого 2 счетчика бит СТВ=2, второго счетчика разрядов шаблона СТК=1, внутренней шины первого операнда сравнения ВА=0010, внутреннего флага равенства FEQ=0 и на выходе заема ВО(СТК)=0. Также в такте 4 задается единичное значение следующего третьего бита на входе данных ID=1.

В такте 5 аналогично работают элементы устройства и устанавливаются следующие коды: первого 2 счетчика бит СТВ=3, второго счетчика разрядов шаблона СТК=0, внутренней шины первого операнда сравнения ВА=0101. При этом так как значение счетчика разрядов шаблона СТК=0, то единичное значение устанавливается на выходе заема ВО(СТК)=1, которое передается на инверсный вход СЕ разрешения работы счетчика разрядов шаблона СТК и запрещает счет на следующих тактах. Кроме того так как совпадают значения кода первого операнда сравнения ВА=0101 и второго операнда ВВ=0101, т.е. выявлена первая группа во входной последовательности соответствующая заданному шаблону IS=0101, то формируется единичное значение внутреннего флага равенства FEQ=1 на выходе компаратора СОМР 11. Далее, при единичном значении на выходе заема ВО=1 второго счетчика разрядов шаблона СТК 4, формируется единичное значение внутреннего флага записи FW=1 на выходе элемента И 5, по которому в такте 6 разрешается работа выходного буфера ОВ 3, в который по нулевому адресу записывается код ОВ(0)=3 с выхода счетчика бит СТВ=3, который соответствует номеру третьего бита входной последовательности, а также разрешается счет (увеличение на единицу) в третьем счетчике 12 количества шаблонов CTS=1.

В тактах 5, 6 и 7 следующие три бита входной последовательности поступают на вход данных ID=101, который также совпадает с заданным шаблоном IS=0101. Поэтому в такте 8 формируются единичные значения внутреннего флага равенства FEQ=1 на выходе компаратора СОМР 11 и внутреннего флага записи FW=1 на выходе элемента И 5, по которому в такте 9 разрешается работа выходного буфера ОВ 3, в который по первому адресу записывается код ОВ(1)=6 с выхода счетчика бит СТВ=6, который соответствует номеру шестого бита входной последовательности (старшего разряда второй выявленной группы), а также разрешается счет в третьем счетчике 12 количества шаблонов CTS=2.

В тактах 8 и 9 следующие два бита (седьмой и восьмой биты) входной последовательности поступают на вход данных ID=01. Так как в устройстве детектируются группы бит соответствующие заданному шаблону с перекрытием разрядов из соседних групп, то при единичном значении шестого бита формируется код трехразрядной группы 101 в трех младших разрядах регистра данных RD 6 соответствующие заданному шаблону IS=101. Поэтому в такте 10 формируются единичные значения внутреннего флага равенства FEQ=1 на выходе компаратора СОМР 11 и внутреннего флага записи FW=1 на выходе элемента И 5, по которому в такте 11 осуществляется запись по второму адресу выходного буфера ОВ(2)=8 и увеличение третьего счетчика 12 количества шаблонов CTS=3.

Аналогично осуществляется поиск групп на тактах 10-12, на такте 13 формирование единичных значений внутреннего флага равенства FEQ=1 и внутреннего флага записи FW=1 и далее на такте 14 запись по третьему адресу выходного буфера ОВ(3)=11, соответствующее старшему одиннадцатому биту для четвертой выявленной группы, и увеличение третьего счетчика 12 количества шаблонов CTS=4.

Таким образом, для входного N=12 разрядного двоичного числа приведенного на фиг. 2 выявлено четыре группы соответствующие заданному трехразрядному IK=3 шаблону IS=101, для которых в выходной буфер ОВ 3 записаны по четырем адресам ОВ(0), ОВ(3) номера (3, 6, 8, 11) старших бит выявленных групп во входной последовательности и на группе внешних выходов количества шаблонов QS установлен код с выхода третьего счетчика 12 количества шаблонов CTS=4.

Для последовательности входных данных ID приведенных на фиг. 3 осуществляется поиск групп для IK=100 разрядов заданного шаблона IS=0101. При этом в такте 2 в счетчик 4 разрядов шаблона СТК записывается код СТК=4, для которого единичное значение выхода заема устанавливается в такте 6 ВО(СТК)=1. Одновременно для кода IK=100 на шине BDC будет установлено значение унитарного позиционного ряда BDC=1111, по которому на следующих тактах разрешается передача четырех младших разрядов на внутреннюю шину первого операнда сравнения ВА с выходов регистра RD 6 и на внутреннюю шину второго операнда сравнения ВВ с внешних входов заданного шаблона IS. При этом на шине второго операнда сравнения ВВ устанавливается код ВВ=0101.

Первое единичное значение внутреннего флага равенства FEQ=1 на выходе компаратора СОМР 11 формируется на такте 5, так как после передачи трех первых бит входной последовательности на шине первого операнда сравнения ВА с выходов регистра RD 6 установлен код ВА=0101 соответствующий разрядам заданного шаблона IS=0101. Но при этом на выходе заема ВО вычитающего второго счетчика разрядов шаблона СТК 4 установлено нулевое значение ВО(СТК)=0. Поэтому формируется нулевое значение внутреннего флага записи FW=0 на выходе элемента И 5 и запрещена запись в выходной буфер ОВ 12 и счет групп в третьем счетчике 12 количества шаблонов CTS.

В тактах 5 и 6 на вход данных ID=01 поступают значении четвертого (0) и пятого (1) бит для которых с учетом значений предыдущих второго (0) и третьего бит (1) формируется четырехразрядной код группы на шине первого операнда сравнения ВА=0101 с выходов регистра RD 6 соответствующий заданному шаблону IS=0101. При этом формируются единичные значения внутреннего флага равенства FEQ=1 и внутреннего флага записи FW=1, так как на выходе заема ВО вычитающего счетчика разрядов шаблона СТК 4 установлено единичное значение ВО(СТК)=1. Поэтому в такте 8 осуществляется запись кода по нулевому адресу выходного буфера кода ОВ(0)=5 с выхода второго счетчика бит СТВ=5, который соответствует номеру старшего пятого бита выявленной группы входной последовательности, а также разрешается счет в третьем счетчике 12 количества шаблонов CTS=1.

Следующая группа, соответствующая заданному шаблону IS=0101, выявлена для 7-10 разрядов входной последовательности, для которой в такте 12 формируется единичное значение внутреннего флага записи FW=1 и далее в такте 13 осуществляется запись кода по первому адресу выходного буфера кода ОВ(1)=10 с выхода счетчика бит СТВ=10, который соответствует номеру десятого бита входной последовательности, а также разрешается счет в третьем счетчике 12 количества шаблонов CTS=2.

При поиске следующей группы во входных данных учитывается перекрытие разрядов из соседних групп - нулевое значение девятого бита и единичное значение десятого бита, которые поступили на вход ID=01 в тактах 10 и 11. Поэтому, после поступления следующего кода ID=01 в тактах 12 и 13, в такте 14 формируется единичное значение внутреннего флага записи FW=1 и далее в такте 15 осуществляется запись кода по второму адресу выходного буфера кода ОВ(2)=12 с выхода счетчика бит СТВ=12, который соответствует номеру двенадцатого бита (старшего разряда третьей группы) входной последовательности, а также разрешается счет в третьем счетчике 12 количества шаблонов CTS=3.

Одновременно в такте 14 поступает единичный сигнал STOP=1, по которому в нулевое состояние переключается RS-триггер 1 пуска-останова TSS=0.

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

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

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

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

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

Устройство для детектирования перекрывающихся шаблонов бит в двоичной последовательности содержит внешний вход данных ID, группу внешних входов шаблона IS, содержащую К разрядов, группу внешних входов IК задания разрядности входного шаблона IS, содержащую m разрядов (где m=]log₂(К+1)[ большее целое), группу внешних выходов данных QB, группу внешних выходов количества шаблонов QS,

а также содержит RS-триггер пуска-останова TSS 1, первый счетчик бит СТВ 2, выходной буфер ОВ 3, второй вычитающий счетчик разрядов шаблона СТК 4, элемент И 5, регистр сдвига входных данных RD 6, дешифратор DC 7, группу из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(к-1), первую группу из К элементов И 9₁, 9₂, …, 9_к, вторую группу из К элементов И 10₁, 10₂, …, 10_к, компаратор СОМР 11 и третий счетчик количества шаблонов CTS 12,

а также введены внешние входы тактового сигнала IC, пуска устройства START, остановки устройства STOP и внутренние шина дешифрации разрядов BDC, шина первого операнда сравнения ВА, шина второго операнда сравнения ВВ, внутренний флаг равенства FEQ и внутренний флаг записи FW, внешняя шина управления обменом ЕО, внешние флаг «Буфер заполнен» FF и флаг «Буфер пуст» FZ,

причем внешний тактовый вход устройства IC соединен с входами синхронизации С RS-триггера пуска-останова TSS 1, первого счетчика бит СТВ 2, выходного буфера ОВ 3, второго вычитающего счетчика разрядов шаблона СТК 4, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12,

внешний вход пуска устройства START соединен с входом S синхронной установки в единичное состояние RS-триггера пуска-останова TSS 1, с входом L разрешения записи второго вычитающего счетчика разрядов шаблона СТК 4, с входами R синхронной установки в нулевое состояние первого счетчика бит СТВ 2, выходного буфера ОВ 3, регистра сдвига входных данных RD 6 и третьего счетчика количества шаблонов CTS 12,

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

причем прямой выход RS-триггера пуска-останова TSS 1 соединен с входами СЕ разрешения работы первого счетчика бит СТВ 2 и регистра сдвига входных данных RD 6,

внешний вход данных ID соединен с входом SI последовательного ввода регистра сдвига входных данных RD 6, группа К выходов которого соединена с первыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к, выходы которых являются соответствующими одноименными разрядами внутренней шины первого операнда сравнения ВА, которая соединена с первой группой входов компаратора СОМР 11,

К разрядов группы внешних входов шаблона IS соединены с первыми входами соответствующих одноименных элементов второй группы из К элементов И 10₁, 10₂, …, 10_к, выходы которых являются соответствующими одноименными разрядами внутренней шины второго операнда сравнения ВВ, которая соединена со второй группой входов компаратора СОМР 11, выход которого является внутренним флагом равенства FEQ и соединен со вторым входом элемента И 5,

причем группа внешних входов IK задания разрядности входного шаблона IS соединена с соответствующей группой D-входов второго счетчика разрядов шаблона СТК 4 и адресными входами дешифратора DC 7, у которого выходы, с первого выхода до (К-1)-го выхода, соединены с первыми входами соответствующих одноименных элементов группы из (К-1) элементов ИЛИ 8₁, 8₂, …, 8_(к-1), выходы которых являются соответствующими одноименными разрядами, с первого разряда до (К-1)-го разряда, внутренней шины дешифрации разрядов BDC, у которой К-й разряд соединен с К-м выходом дешифратора DC 7, а К разрядов внутренней шины дешифрации разрядов BDC соединены со вторыми входами соответствующих одноименных элементов первой группы из К элементов И 9₁, 9₂, …, 9_к и второй группы из К элементов И 10₁, 10₂, …, 10_к, а также выходы элементов группы 8₁, 8₂, …, 8_(к-1) из (К-1) элементов ИЛИ, начиная с выхода (К-1)-го элемента 8_(к-1) до второго элемента 8₂, соединены со вторыми входами соответствующих предыдущих элементов ИЛИ группы 8₁, 8₂, …, 8_(к-1), начиная с (К-2)-го элемента 8_(к-2) до первого элемента 8₁, а второй вход (К-1)-го элемента 8_(к-1) соединен с К-м выходом дешифратора DC 7,

кроме того, прямой выход заема ВО вычитающего счетчика разрядов шаблона СТК 4 соединен с инверсным входом разрешения работы СЕ счетчика разрядов шаблона СТК 4 и с первым входом элемента И 5, выход которого является внутренним флагом записи FW и соединен с входами СЕ разрешения работы выходного буфера ОВ 3 и третьего счетчика количества шаблонов CTS 12,

причем группа выходов первого счетчика бит СТВ 2 соединена с группой информационных D-входов выходного буфера ОВ 3, который также подключен к внешней шине ЕО управления обменом, а соответствующие выходы выходного буфера ОВ 3 являются группой внешних выходов данных QB и внешними флагами «Буфер заполнен» FF и «Буфер пуст» FZ, а группа выходов счетчика количества шаблонов CTS 12 является группой внешних выходов количества шаблонов QS.