RU2815502C1 - Device for detecting groups of single bits and maximum groups in blocks of binary sequence - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: invention relates to computer engineering, particularly to data processing devices. Technical result is achieved due to the fact that the device for detecting groups of single bits additionally includes external clock inputs, synchronous setting to zero state and operation permits, internal data buses, coincidence, senior group, number of units in the group and priority, internal flag of the beginning of the block and internal flag of maximum, external buses of exchange control, external flags "Buffer full" and "Buffer empty".

EFFECT: possibility of determining the maximum group of single bits in a binary input sequence.

1 cl, 2 dwg

Description

TECHNICAL FIELD

The invention relates to the field of computer technology, in particular to data processing devices, and can be used to construct functional units for analyzing the properties of generators of pseudo-random sequences of binary numbers, filtering events, processing signals, images and the results of physical experiments.

BACKGROUND ART

A serial type device is known for detecting groups of zero and one bits and determining their number (RU No. 2680759 C1, IPC G06F 7/74, declared 02/16/2018, published 02/26/2019, Bulletin No. 6) in which for input data sequences of dimension N , arriving at the external data input DI, binary codes are generated at the corresponding external outputs of the device groups, corresponding to the number of QG groups, the number of zero bits QZ, the number of one bits QU, the difference between the number of one and zero bits QZU, the number of bits in QO groups from the output buffer OB 11, while in even addresses, starting from the zero address, the number of zero bits in groups is indicated, and in odd addresses, starting from the first address, the number of one bits in groups is indicated, and the FE readiness flag is generated, the “zeros are greater than ones” flag » F01, “Buffer full” flag FF and “Buffer empty” flag FZ.

The disadvantages of this device are the definition of groups of zero and one bits of an arbitrary dimension, rather than a given dimension, and the lack of means for identifying maximum groups.

The closest device for the same purpose to the claimed invention in terms of the set of features is, taken as a prototype, a device for detecting groups of bits (RU No. 2780985, IPC G06F 7/74, G06F 7/02, declared 12/01/2021, published 10/04/2022, Bulletin . No. 28), containing an external m-bit data input ID, an external m-bit input of a given pattern IG, a group of external data outputs QB, the first RS start-stop trigger TSS 1, the second D-trigger TR2 delay 2, counter CTG groups 3, output buffer OB 4, first R1 data register 5, second R2 data register 6, group of m comparators 7 ₁ , 7 ₂ , …, 7 _m , group of (m-1) AND elements 8 ₂ , 8 ₃ , …, 8 _m , element OR 9 and element AND 10, as well as external inputs of asynchronous installation in the zero state CLR, device start START, device stop STOP and clock C, internal 2m-bit data bus BD, internal m-bit buffer data bus IOB, internal match flag FE, external exchange control bus EO, external flag “Buffer full” FF and flag “Buffer empty” FZ.

The disadvantage of this device is that at each clock cycle it detects groups of bits corresponding to only one given pattern.

OBJECTIVE OF THE INVENTION

The objective of the invention is to develop hardware of a group structure for studying the properties of generators of pseudo-random sequences of binary numbers, as well as for processing signals and the results of physical experiments.

When analyzing generators of pseudo-random sequences of binary numbers, the device is designed to identify groups (rows) of consecutive one bits and the longest sequence of ones in blocks of input data of a given dimension.

When processing the results of physical experiments, the device is designed to identify events of a given dimension, determine their number and maximum events.

The technical result of the invention is to expand the arsenal of tools for the same purpose, in terms of the ability to detect groups of unit bits, determine the number of specified groups and identify maximum groups in binary blocks, as well as counting unit groups in the input sequence.

BRIEF DESCRIPTION OF THE INVENTION

The specified technical result when implementing the invention is achieved in that the device for detecting groups of single bits and maximum groups in blocks of a binary sequence contains an external data input ID of serial input of K-bit data blocks BB from the input N-bit binary data sequence, a group of external outputs of QB groups , group of external outputs of maximum groups QH, group of external buses of the number of unit groups Q1, Q2, Q(M+1) (where M is the bit depth of detected unit groups, 1≤M≤K), clock counter CTC 1, output buffer of groups OB 2 , data shift register RD 3, group of (M+1) comparators 4 ₁ , 4 ₂ , …, 4 _(M+1) , AND element with inverse input 5, group of M unit group counters 6 ₁ , 6 ₂ , … , 6 _M , group of (M+1) adders 7 ₁ , 7 ₂ , …, 7 _(M+1) , group of (M+1) registers 8 ₁ , 8 ₂ , …, 8 _(M+1) , trigger TR 9, group of M elements OR 10 ₁ , 10 ₂ , …, 10 _M , group of M elements AND with inverse input 11 ₁ , 11 ₂ , …, 11 _M , priority encoder 12, element OR 13, maximum group register RH 14, priority register RPR 15 and maximum group output buffer OH 16,

and also introduced external inputs clock IC, synchronous zeroing IR and operation permission ICE, internal data buses BD, matches BEQ, high group BS, number of units in the HV group and priority BPR, internal block start flag F1 and internal maximum flag FH , external EO exchange control buses, external flags “Buffer full” FF and “Buffer empty” FZ,

Moreover, the external input of the synchronous setting to the zero state IR is connected to the corresponding inputs of the synchronous setting to the zero state R of the clock counter STS 1, the output buffer of groups OB 2, the data shift register RD 3, registers 8 ₁ , 8 ₂ , ..., 8 _{(M+1 )} and the output buffer of the maximum groups OH 16, and the external operation permission input ICE is connected to the operation permission input CE of the clock counter CTC 1,

The external clock input of the 1C device is connected to the synchronization inputs C of the CTC clock counter 1, the output buffer of groups OB 2, the data shift register RD 3, the unit group counters 6 ₁ , 6 ₂ , ..., 6 _M , registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) , trigger TR 9, maximum group register RH 14, priority register RPR 15 and output buffer maximum groups OH 16,

Moreover, the output of the clock counter STS 1 is the internal flag of the beginning of block F1, which is connected to the inputs of synchronous setting to the zero state R of unit group counters 6 ₁ , 6 ₂ , ..., 6 _M , trigger TR 9, maximum group register RH 14 and priority register RPR 15, and is also connected to the operation permission inputs CE of the output buffer of groups OB 2, registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) and the output buffer of maximum groups OH 16,

the external data input ID is connected to the SI input of the serial input of the data shift register RD 3, the outputs of which are bits of the internal data bus BD,

moreover, the bits of the internal data bus BD in groups of (i+2) bits (where i=1, ..., M), each of which starts from the first bit, are connected to the second groups of inputs of the corresponding i-th comparators of group 4 ₁ , 4 ₂ , ..., 4 _M , and for the first groups of comparator inputs of groups 4 ₁ , 4 ₂ , ..., 4 _M , zero values are supplied to the first digits and (i+2)th digits, and unit values are supplied to the second and subsequent digits in the corresponding groups according to (i) digits (where i=1, ..., M), each of which begins with the second digit,

in addition, the (M+1)th comparator 4 _(M+1) has unit values supplied to all W bits of the first group of inputs (where W is the bit capacity of the detected unit groups, K/2≤W≤K), and the second group of inputs is connected with the first W bits of the internal data bus BD, starting from the first bit, and the output of the (M+1)th comparator 4 _(M+1) is connected by the direct input of element AND 5 to the inverse input,

the outputs of the first M comparators 4 ₁ , 4 ₂ , …, 4 _M are connected to the operation permission inputs CE of the corresponding unit group counters of the same name 6 ₁ , 6 ₂ , …, 6 _M , and are also the same first M bits of the internal BEQ coincidence bus, which (M+1) discharge is connected to the output of element AND 5 with an inverse input, in which the inverse input is connected to the output of the trigger TR 9, in which the input S of the synchronous setting to a single state is connected to the output of element AND 5 with an inverse input,

in this case, all (M+1) bits of the internal coincidence bus BEQ are connected to the corresponding inputs of the priority encoder 12, the outputs of which are bits of the internal bus of the number of units in the HV group, which is connected to a group of information D-inputs of the register of the maximum group RH 14, the outputs of which are connected with a group of information D-inputs of the output buffer of maximum groups OH 16,

in addition, the first M bits of the internal coincidence bus BEQ are connected to the first direct inputs of the corresponding elements And with the inverse input of the group 11 ₁ , 11 ₂ , ..., 11 _M , the outputs of which are the first M bits of the internal bus of the senior group BS, which has (M+ The 1)th bit is connected to the (M+1)th bit of the internal BEQ coincidence bus, and all (M+1) bits of the internal bus of the high group BS are connected by a group of information D-inputs of the priority register RPR 15 and connected to the corresponding inputs of the OR element 13, the output of which is the internal maximum flag FH and is connected to the operation permission inputs of the CE register of the maximum group RH 14 and the priority register RPR 15, the outputs of which are bits of the internal priority bus BPR, in which the first M bits are connected to the first inputs of the same M elements OR from groups 10 ₁ , 10 ₂ , …, 10 _M , the outputs of which are connected to the inverse inputs of the same elements AND with the inverse input from the group 11 ₁ , 11 ₂ , …, 11 _M ,

wherein the second inputs of the first (M-1) elements OR of the group 10 ₁ , 10 ₂ , ..., 10 _(M-1) , starting from the first to the (M-1)th elements, are connected to the outputs of the corresponding subsequent (M-1) OR elements of the group 10 ₂ , 10 ₃ , ..., 10 _M , starting from the second to the M-th elements, and the M-th bit of the internal BPR priority bus is connected to the second input of the M-th element 10 _M , in addition, the outputs of the unit group counters 6 ₁ , 6 ₂ , …, 6 _M and trigger TR 9 are connected to the corresponding groups of information D-inputs of the output buffer of groups OB 2, and also connected to the second groups of inputs of the corresponding (M+1) adders 7 ₁ , 7 ₂ , …, 7 _(M+1) , in which the first groups of inputs are connected to the outputs of registers of the same name (M+1) 8 ₁ , 8 ₂ , ..., 8 _(M+1) , the outputs of which are also the corresponding external buses of the same name Q1, Q2, Q (M+1) number of unit groups,

in addition, the output buffer of groups OB 2 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer OB 2 are a group of external outputs of groups QB and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ,

moreover, the output buffer of the maximum groups OH 16 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer of the maximum groups OH 16 are a group of external outputs of the maximum groups QH and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ.

BRIEF DESCRIPTION OF THE DRAWINGS

In fig. Figure 1 shows a diagram of the proposed device for detecting groups containing from 1 to M=3 single bits and W≥4 single bits in successive blocks of input data BB containing K=8 bits each. In fig. Figure 2 shows a time diagram of the device operation.

In fig. 1-2 and the following notations are used in the text:

ADD - adder,

AND - element AND,

OR - OR element,

BB1, BB2, …., BBL - input data blocks containing K bits each,

BD - internal data bus,

BEQ - internal (M+1)-bit coincidence bus,

BS - internal (M+1)-bit bus of the high group,

VN - internal][log ₂ (M+1)[-bit bus of the number of units in the group

(] [- greater integer),

BPR - internal (M+1) priority bit bus,

BUF - buffer with FIFO service discipline,

C - clock input,

CE - work permission input,

COMP - comparator,

ST - counter,

STS - clock counter,

ST1, ST2,..., STM - a group of M unit group counters,

D - information inputs,

EO - external exchange control bus,

F1 - internal block start flag,

FH - internal maximum flag,

FF - external flag “Buffer full”,

FZ - external flag “Buffer empty”,

IC - external clock input,

ICE - external operation permission input,

ID - external data input,

IR - external input of synchronous installation to zero state,

K - bit depth of input data blocks,

L - number of input blocks of explosives, where L=N/K,

N - dimension (length) of the input data sequence,

M - bit depth of detected unit groups, where 1≤M≤K,

OB - output group buffer,

OH - output buffer of maximum groups,

QB - group of external group outputs,

QH - group of external outputs of maximum groups,

Q1, Q2,Q(M+1) - group of external buses of the number of unit groups,

R - synchronous installation input to zero state,

R1, R2, …, R(M+1) - group of (M+1) unit group registers,

RG - register,

RD - data shift register,

RH - maximum group register,

RPR - priority register,

S - synchronous installation input to single state,

SI - serial input,

TR - trigger,

W is the depth of detected unit groups, where K/2≤W≤K,

1 - STS cycle counter,

2 - output buffer of OB groups,

3 - data shift register RD,

4 ₁ , 4 ₂ , …, 4 _(M+1) - group of (M+1) comparators (COMP),

5 - AND element with inverse input (AND),

6 ₁ , 6 ₂ , …, 6 _M - group of M unit group counters,

7 ₁ , 7 ₂ , …, 7 _(M+1) - group of (M+1) adders (ADD),

8 ₁ , 8 ₂ , …, 8 _(M+1) - group of (M+1) registers,

9 - TR trigger,

10 ₁ , 10 ₂ , …, 10 _M - group of M elements OR (OR),

11 ₁ , 11 ₂ , …, 11 _M - group of M elements AND with inverse input (AND),

12 - priority encoder,

13 - OR element,

14 - maximum group register RH,

15 - RPR priority register,

16 - output buffer of maximum OH groups.

The proposed device contains an external contains an external data input ID for serial input of K-bit data blocks BB from the input N-bit binary data sequence, a group of external outputs of QB groups, a group of external outputs of maximum groups QH, a group of external buses of the number of unit groups Q1, Q2, Q (M+1) (where M is the bit depth of the detected unit groups, 1≤M≤K), clock counter STS 1, output buffer of groups OB 2, data shift register RD 3, group of (M+1) comparators 4 ₁ , 4 ₂ , …, 4 _(M+1) , AND element with inverse input 5, group of M unit group counters 6 ₁ , 6 ₂ , …, 6 _M , group of (M+1) adders 7 ₁ , 7 ₂ , … , 7 _(M+1 ), group of (M+1) registers 8 ₁ , 8 ₂ , …, 8 _(M+1) , trigger TR 9, group of M elements OR 10 ₁ , 10 ₂ , …, 10 _M , a group of M AND elements with an inverse input 11 ₁ , 11 ₂ , ..., 11 _M , priority encoder 12, OR element 13, maximum group register RH 14, priority register RPR 15 and output buffer of maximum groups OH 16.

The proposed device also includes external inputs clock IC, synchronous zeroing IR and operation enable ICE, internal data buses BD, matches BEQ, high group BS, number of units in the HV group and priority BPR, internal block start flag F1 and internal flag maximum FH, external exchange control buses EO, external flags “Buffer full” FF and “Buffer empty” FZ.

The external input of the synchronous setting to the zero state IR is connected to the corresponding inputs of the synchronous setting to the zero state R of the clock counter STS 1, the output buffer of groups OB 2, the data shift register RD 3, registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) and the output buffer of the maximum groups OH 16, and the external operation permission input ICE is connected to the operation permission input CE of the clock counter CTC 1.

The external clock input of the 1C device is connected to the synchronization inputs C of the CTC clock counter 1, the output buffer of groups OB 2, the data shift register RD 3, the unit group counters 6 ₁ , 6 ₂ , ..., 6 _M , registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) , trigger TR 9, maximum group register RH 14, priority register RPR 15 and output buffer maximum groups OH 16,

The output of the clock counter CTC 1 is the internal flag of the beginning of block F1, which is connected to the inputs of synchronous setting to the zero state R of counters of unit groups 6 ₁ , 6 ₂ , ..., 6 _M , trigger TR 9, maximum group register RH 14 and priority register RPR 15 , and is also connected to the operation permission inputs CE of the output buffer of groups OB 2, registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) and the output buffer of maximum groups OH 16.

The external data input ID is connected to the serial input input SI of the data shift register RD 3, the outputs of which are bits of the internal data bus BD.

The bits of the internal data bus BD in groups of (i+2) bits (where i=1, ..., M), each of which starts from the first bit, are connected to the second groups of inputs of the corresponding i-th comparators of group 4 ₁ , 4 ₂ , ... _{. ​ ​ ​} i) digits (where i=l, M), each of which begins with the second digit.

In addition, the (M+1)th comparator 4 _(M+1) has unit values supplied to all W bits of the first group of inputs (where W is the bit capacity of the detected unit groups, K/2≤W≤K), and the second group of inputs is connected with the first W bits of the internal data bus BD, starting from the first bit, and the output of the (M+1)th comparator 4 _(M+1) is connected by the direct input of the AND element 5 to the inverse input.

The outputs of the first M comparators 4 ₁ , 4 ₂ , …, 4 _M are connected to the operation enable inputs CE of the corresponding unit group counters of the same name 6 ₁ , 6 ₂ , …, 6 _M , and are also the same first M bits of the internal BEQ coincidence bus, which (M+1) discharge is connected to the output of element AND 5 with an inverse input, in which the inverse input is connected to the output of trigger TR 9, in which the input S of the synchronous setting to a single state is connected to the output of element AND 5 with an inverse input.

In this case, all (M+1) bits of the internal coincidence bus BEQ are connected to the corresponding inputs of the priority encoder 12, the outputs of which are bits of the internal bus of the number of units in the HV group, which is connected to a group of information D-inputs of the register of the maximum group RH 14, the outputs of which are connected with a group of information D-inputs of the output buffer of maximum groups OH 16.

The first M bits of the internal coincidence bus BEQ are connected to the first direct inputs of the corresponding elements And to the inverse input of the group 11 ₁ , 11 ₂ , ..., 11 _M , the outputs of which are the first M bits of the internal bus of the senior group BS, which has (M+1)- th bit is connected to the (M+1) th bit of the internal coincidence bus BEQ, and all (M+1) bits of the internal bus of the high group BS are connected to a group of information D-inputs of the priority register RPR 15 and connected to the corresponding inputs of element OR 13, output which is the internal flag of the maximum FH and is connected to the operation permission inputs of the CE register of the maximum group RH 14 and the priority register RPR 15, the outputs of which are bits of the internal priority bus BPR, in which the first M bits are connected to the first inputs of the same M elements OR from group 10 ₁ , 10 ₂ , …, 10 _M , the outputs of which are connected to the inverse inputs of the same elements AND with the inverse input from the group 11 ₁ , 11 ₂ , …, 11 _M.

The second inputs of the first (M-1) elements of the OR group 10 ₁ , 10 ₂ , ..., 10 _(M-1) , starting from the first to the (M-1) th elements, are connected to the outputs of the corresponding subsequent (M-1) elements OR groups 10 ₂ , 10 ₃ , ..., 10 _M , starting from the second to M-th elements, and the M-th bit of the internal BPR priority bus is connected to the second input of the M-th element 10 _M.

The outputs of the counters of unit groups 6 ₁ , 6 ₂ , ..., 6 _M and the trigger TR 9 are connected to the corresponding groups of information D-inputs of the output buffer of groups OB 2, and are also connected to the second groups of inputs of the corresponding (M+1) adders 7 ₁ , 7 ₂ , …, 7 _(M+1) , in which the first groups of inputs are connected to the outputs of registers of the same name (M+1) 8 ₁ , 8 ₂ , …, 8 _(M+1) , the outputs of which are also the corresponding external buses of the same name Q1 , Q2, Q (M+1) number of unit groups.

The output buffer of groups OB 2 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer OB 2 are a group of external outputs of groups QB and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ

The output buffer of the maximum groups OH 16 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer of the maximum groups OH 16 are a group of external outputs of the maximum groups QH and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ.

DETAILED DESCRIPTION OF THE INVENTION

The operating principle of the proposed device is as follows.

The proposed device makes it possible to detect groups containing from 1 to M unit bits (where M is set from the range 1≤M≤K) and containing W or more W unit bits (where W is set from the range K/2≤W≤K), in K -bit blocks of explosives in the input N-bit binary sequence. In this case, for groups containing ≥W one bits, only one group can be registered in each BB block.

The input N-bit unsigned binary number is divided into L=N/K blocks with K bits in each block. The bits of each block BB1, BB2, BBL of input data sequentially in each 1C cycle are supplied to the external data input ID, and one separating zero bit is transmitted between the blocks. In this case, in the data shift register RD, the input serial K-bit code of the BB block is converted into a parallel K-bit code, which is transmitted to the internal data bus BD.

At each clock cycle, a search (identification, detection, analysis) is carried out on the internal data bus BD for unit groups of a given dimension on (M+1) COMP comparators from the group 4 ₁ , 4 ₂ , ..., 4 _(M+1) . In this case, for the first M comparators 4 ₁ , 4 ₂ , ..., 4 _M, the first groups of inputs receive codes containing, respectively, from 1 to M single bits, supplemented by zero bits before the least significant and after the most significant single bits, and the second groups of comparator inputs receive codes respectively 3, 4, (M+2) bits from the internal BD data bus, starting from the first bit. The first group of inputs (M+1) of the comparator 4 _(M+1) receives a binary code containing W unit bits, and the second group of W bits from the internal data bus BD, starting from the first bit.

At the outputs of the group of comparators 4 ₁ , 4 ₂ , 4 _(M+1) , a unitary code “1 from (M+1)” is generated, containing one unit value if it matches the corresponding group of unit bits, or a code containing zero values in all bits when mismatches, which are transmitted to the internal BEQ match bus. Next, the corresponding identified unit group is counted on counters 6 ₁ , 6 ₂ , ..., 6 _M. When ≥W single bits are detected (a single value in the (M+1)th bit of the internal data bus BD), trigger TR 9 is set to a single state, according to which, in the next clock cycles, for the current block BB on element AND 5 with an inverse input, prohibition of the formation of a single value in the (M+1)th bit of the internal BEQ coincidence bus from the output of the (M+1)th comparator 4 _(M+1) .

At the same time, the unitary code “1 of (M+1)” from the internal coincidence bus BEQ in the priority encoder 12 is converted into a positional binary code, which is transmitted to the internal bus VN of the number of units in the group and then to the input of the maximum group register RH 14. In addition, based on single values from the priority register RPR 15, which, through the internal priority bus BPR, are sent to a group of M elements OR 10 ₁ , 10 ₂ , ..., 10 _M and further along the chain of elements OR a single value from the most significant digit is transmitted sequentially towards the lower digits, and single values are set at the corresponding outputs of OR elements 10 ₁ , 10 ₂ , ..., 10 _M , by which single values of the corresponding bits of the matching or low priority unitary code “1 of (M+1)” from the internal BEQ coincidence bus are prohibited. Therefore, further at the outputs of the AND elements with an inverse input from the group Hi, 112, they generate a unitary code “1 from (M+1)”, which is transmitted to the internal bus of the high-order group BS, if the current identified group of one bits contains a number of ones exceeding the previous value , and then transmitted from the BS bus to the inputs of the priority register RPR 15.

At the same time, the unitary code “1 of (M+1)” from the internal bus of the senior group BS is transmitted to the inputs of OR element 13, the output of which generates a single value, if there is a single value at one of the inputs, which is the internal maximum flag FH. With a single value of the maximum flag FH=1, writing to the maximum group register RH 14 is allowed, from the internal HV bus of the number of units in the group, and writing to the priority register RPR 15, from the internal bus of the high group BS.

Clock counter CTC 1 counts IC clock pulses modulo (K+1). Moreover, when the STS counter is set to the first state STS = 1, a single value of the block start flag F1 = 1 is generated at the output, which allows writing to the output buffer of groups OB 2 the values of the number of identified single groups from counters 6 ₁ , 6 ₂ , ..., 6 _M and trigger TR 9 and writing to the output buffer of the maximum groups OH 16 from the output of the register of the maximum group RH 14 values for the previous input block BB.

Reading of the results to the group of external outputs of the QB groups from the output buffer OB 2 and to the group of external outputs of the maximum groups QH from the output buffer OH 16 is performed under control via the corresponding external control buses EO. When implementing the output buffers OB 2 and OH 16 in the form of a two-port FIFO memory, the exchange can be performed in the process of detecting groups, taking into account the values of the flags “Buffer empty” FZ and “Buffer full” FF.

In addition, the values from the counters of unit groups 6 ₁ , 6 ₂ , ..., 6 _M and the trigger TR 9 are supplied to the groups of inputs of the second summands of the same adders from the group 7 ₁ , 7 ₂ , ..., 7 _(M+1) , on which the summation with the values of the corresponding amounts (quantities) from the outputs of registers from the group 8 ₁ , 8 ₂ , ..., 8 _(M+1) , identified in the previous blocks of input data. At the same time, accumulating adders are implemented on the group of adders 7 ₁ , 7 ₂ , …, 7 _(M+1) and the group of registers 8 ₁ , 8 ₂ , …, 8 _(M+1) . In addition, the values from the outputs of registers 8 ₁ , 8 ₂ , …, 8 _(M+1) are a group of external buses of the number of unit groups Q1, Q2, …, Q(M+1).

The proposed device works as follows.

The proposed device operates by setting a single value at the external input ICE and operating permission ICE=1. When a signal is applied to the input IR of the synchronous installation using the clock signal IC, the clock counter CTC 1, the data shift register RD 3 and registers from group 8 ₁ , 8 ₂ , ..., 8 _(M+1) are set to zero, and the zero addresses in in the output buffer of groups OB 2 and in the output buffer of maximum groups OH 16.

In fig. Figure 1 shows a diagram of the proposed device for detecting groups containing from 1 to M=3 single bits and W≥4 single bits in successive blocks of input data BB containing K=8 bits each.

In fig. Figure 2 shows a timing diagram of the operation of the proposed device for detecting groups containing from 1 to M=3 single bits and W≥4 single bits, in two consecutive blocks of input data BB(Z+1) and BB(Z+2) containing each K= 8 digits. The external ID data input for the input data block BB(Z+1) is supplied with the sequence “10101101”, and for the input data block BB(Z+2) the sequence “11011111” is supplied. Between the blocks in clock 9 and after the second data block BB(Z+2) in clock 18, separating zero bits are applied to the ID data input. To detect single groups containing up to M=3 and W=4 bits, the input data register RD 3 contains five bits.

In cycle 1, according to the clock signal IC, a zero value from the serial input input SI is written to the low-order bit of the data register RD 3, and in other bits the values “xxxx” are shifted from the previous data block BB(Z). In this case, the code “xxxx0” is set in the data register RD 3. Next, in the group of comparators 4 ₁ , 4 ₂ , …, 4 _(M+1), unit groups are identified taking into account the eighth bit of the previous input block BB(Z) and the corresponding unitary code “1 of (M+1)” is generated on the internal BEQ coincidence bus )", for which in cycle 2 the corresponding unit groups Z4, Z3, Z2, Z1 are counted in counters 6 ₁ , 6 ₂ , ..., 6 _M and trigger TR 9, and the value of the maximum group ZH is generated in register RH 14. At the same time in clock 1, the ID data input receives a one value of the first bit of the next data block BB(Z+1).

In clock 2, the zero value of the second bit of the data block BB(Z+1) is received at the ID data input and at the same time the first bit one is written to the low order of the data register RD 3 and the code “xxx01” is set, which is then compared on comparators 4 ₁ , 4 ₂ , ..., 4 _(M+1) and for which a zero code is generated on the internal coincidence bus BEQ=0000. At the same time, on the clock counter CTC 1, the number of the first bit is set, by which a single value of the block start flag F1=1 is formed, according to which, in cycle 3, the values OB(Z)=Z4_Z3_Z2_Z1 are written to Z addresses in the output buffer of OB groups 2 - the number of identified single groups from counters 6 ₁ , 6 ₂ , ..., 6 _M and trigger TR 9 and writing into the output buffer of maximum groups OH 16 the values OH(Z) = ZH from the output of the maximum group register RH 14 - values for the previous input data block BB(Z ). The total number of identified unit groups is also calculated for the first Z blocks of input data, starting from the first BB1 to BB(Z) block, in accumulating adders on the adder group 7 ₁ , 7 ₂ , ..., 7 _(M+1) and register group 8 ₁ , 8 ₂ , …, 8 _(M+1) and writing the calculated values V4, V3, V2, V1 into registers 8 ₁ , 8 ₂ , …, 8 _(M+1) . In addition, in cycle 3, by the single value of the block start flag F1 = 1, the counters of unit groups from group 6 ₁ , 6 ₂ , ..., 6 _M , trigger TR 9, maximum group register RM 14 and priority register RPR 15 are set to zero.

At the same time, in clock 3, the ID data input receives a single value of the third bit of the data block BB(Z+1) and at the same time the code “xx010” is set in the data register RD 3, which is compared on comparators 4 ₁ , 4 ₂ , ..., 4 _{(M+ 1)} , and for which a single value is generated in the least significant bit and the code BEQ = 0001 is set on the internal coincidence bus, since a group containing one single bit “010” is detected. Therefore, in step 4, the first counter of 61 unit groups ST1=1 is counted. In addition, at the output of the priority encoder 12, a code for the number of the first unit group is generated, which is transmitted to the internal HV bus of the number of units in the HV group = 1, and also the code BS = 0001 is generated on the internal bus of the senior group BS, since in the priority register RPR 15 the zero code is set to “0000”. In this case, in cycle 3, at the output of element OR 13, a single value of the maximum flag FH=T is generated, according to which, in cycle 4, the maximum group RH=1 is written to register 14 and the priority register RPR 15 is written and the code BPR=0001 is set on the priority bus , according to which in the next clock cycles on the group of elements OR 10 ₁ , 10 ₂ , ..., 10 _M and the group of elements AND with an inverse input 11 ₁ , 11 ₂ , ..., 11 _M , single values from the first comparator 4i from the coincidence bus BEQ in the first are excluded bit of the unitary code “1 of (M+1)” on the internal bus of the senior group BS.

Also in clock 4, the zero value of the fourth bit of the data block BB(Z+1) is received at the ID data input and at the same time the code “x0101” is set in the data register RD 3, which is compared on comparators 4 ₁ , 4 ₂ , ..., 4 _{(M+ 1)} , and for which a zero code is generated on the internal coincidence bus BEQ=0000, since no new unit groups have been identified.

In cycle 5, the ID data input receives a single value of the fifth bit of the data block BB(Z+1) and at the same time the code “01010” is set in the data register RD 3, which is compared on comparators 4 ₁ , 4 ₂ , ..., 4 _{(M+1 )} , and for which a single value is formed in the low-order bit and the code BEQ = 0001 is set on the internal coincidence bus, since a group containing one single bit “010” is detected, and then in clock 6 the increase in the first counter 6 ₁ single groups ST1 = is carried out 2. In addition, in cycle 5, at the output of the priority encoder 12, a code for the number of the first unit group is generated, which is transmitted to the internal HV bus of the number of units in the HV group = 1, and on the bus of the senior group BS, a zero code BS = 0000 is generated, since on the priority bus The code is set to BPR=0001. In this case, at the output of OR element 13, a zero value of the maximum flag FH=0 is generated, therefore no entry is made into the maximum group register RH 14 and into the priority register RPR 15.

Next, the ID data input receives the single value of the sixth bit in clock 6 and the zero value of the seventh bit of the BB(Z+1) data block in clock 7, for which the code “10110” is set in clock 8 in the data register RD 3. In this case, a single value is formed at the output of the second comparator 4g and the code BEQ = 0010 is set on the internal coincidence bus, since the group “0110” containing two single bits is detected. Therefore, in step 9, 62 unit groups ST2=1 are counted in the second counter. In addition, at the output of the priority encoder 12, a code for the number of the second unit group is generated, which is transmitted to the internal HV bus of the number of units in the HV group = 2, and also a code BS = 0010 is generated on the internal bus of the senior group BS, which exceeds the priority set in the register priority RPR 15 (BPR code “0001” is set on the priority bus). At the same time, in clock 8, at the output of element OR 13, a single value of the maximum flag FH=1 is generated, according to which, in clock 9, the maximum group RH=2 is written to register 14 and the priority register RPR 15 is written and the code BPR=0010 is set on the priority bus, according to which, at the next clock cycles on the group of elements OR 10 ₁ , 10 ₂ , ..., 10 _M and the group of elements AND with an inverse input 11 ₁ , 11 ₂ , ..., 11 _M , single values from the first 4 ₁ and second 4 ₂ comparators from the bus are excluded coincidence BEQ in the first and second bits of the unitary code “1 of (M+1)” on the internal bus of the high group BS, since the code “011” is set at the outputs of the OR elements of group 10 ₁ , 10 ₂ , ..., 10 _M.

The ID data input in clock cycle 8 receives the single value of the eighth (Kth, most significant) bit of the data block BB(Z+1) and then in clock cycle 9 the value of the zero separating bit between the data blocks BB(Z+1) and BB(Z+ 2). Therefore, in cycle 10 in the data register RD 3, the code “11010” is set, for which a single value is generated at the output of the first comparator 4 ₁ and the code BEQ = 0001 is set on the internal coincidence bus, since the group “010” containing one single bit is detected, and then in step 11 the increase in the first counter 6 ₁ of unit groups ST1=3 is carried out. In this case, at the output of OR element 13, a zero value of the maximum flag FH=0 is generated, since the identified group contains fewer one bits than are registered in register 14 of the maximum group RH=2. Therefore, no entries are made to the maximum group register RH 14 and the priority register RPR 15.

At the same time, in each cycle, the IC clock signals are counted on the clock counter STS 1, in which the counting period (module) is set to nine (for K+1=9). Therefore, in cycle 10, the initial zero state of CTC = 0 is set in the counter CTC 1, and at the next 11th cycle, with the value of CTC = 1, a single value of the block start flag F1-1 is formed, by which in cycle 12 recording is carried out at addresses (Z + 1) into the output buffer of groups OB 2 values OB(Z+1)=0_0_1_3 - the number of identified unit groups from counters 6 ₁ , 6 ₂ , ..., 6 _M and trigger TR 9 and writing to the output buffer of maximum groups OH 16 values OH(Z+ 1)=2 from the output of the maximum group register RH 14 - values for the current input block BB(Z+1). The total number of identified unit groups is also calculated for all blocks of input data, starting from the first BB1 to BB(Z+1) block, in accumulating adders on the adder group 7 ₁ , 7 ₂ , ..., 7 _(M+1) and the register group 8 ₁ , 8 ₂ , …, 8 _(M+1) and writing the calculated values V4, V3, (V2+1), (V1+3) into registers 8 ₁ , 8 ₂ , …, 8 _(M+1) . In addition, in cycle 12, by the single value of the block start flag F1 = 1, the unit group counters from group 6 ₁ , 6 ₂ , ..., 6 _M , trigger TR 9, maximum group register RH 14 and priority register RPR 15 are set to zero.

Then, for the next input group BB(Z+2), in clock cycles 10-17, the following bit sequence “11011111” is received at the ID data input. In this case, in accordance with the above algorithm, at cycle 13, the code “10110” is set in the data register RD 3, in which the group “0110” is detected, containing two unit bits, and a single value of the maximum flag FH = 1 is generated. Therefore, in cycle 14, the second counter of 62 unit groups CT2=1 is counted and the maximum group RH=2 is written to register 14 and the priority register RPR 15 is written to and the code BPR=0010 is set on the priority bus.

In clock 17, the code “01111” is set in the data register RD 3, in which the group “1111” containing four unit bits is detected (the output value of the comparator 4 ₄ is set to one), and the maximum flag FH = 1 is also generated. Therefore, in cycle 18, the fourth counter 6 ₄ unit groups СТ4=Т is counted and the maximum group RH=4 is written to register 14 and the priority register RPR 15 is written to and the code BPR=1000 is set on the priority bus. Also, trigger 9 TR=1 is set to the single state.

At the same time, in clock 18, the code “11111” is set in the data register RD 3, in which the group “1111” containing four one bits is also detected, since the output value of comparator 44 is set to one. However, this value is blocked by element AND 5 with an inverse input, so as flip-flop 9 is set to the single state TR=1, and therefore the zero code BEQ=0000 is set on the coincidence bus.

In cycle 20, at the output of the clock counter CTG 1, a single value of the block start flag F1=1 is formed, according to which, in cycle 21, the values OB(Z+2)=1_0_1_0 are written to the addresses (Z+2) in the output buffer of groups OB 2 OB(Z+2)=1_0_1_0 - quantity identified single groups from counters 6 ₁ , 6 ₂ , ..., 6 _M and trigger TR 9 and writing into the output buffer of maximum groups OH 16 values OH(Z+2) = 4 from the output of the maximum group register RH 14 - values for the current input block BB(Z+2). The total number of identified unit groups is also calculated for all blocks of input data, starting from the first BB1 to BB(Z+2) block, in accumulating adders on the adder group 7 ₁ , 7 ₂ , ..., 7 _(M+1) and the register group 8 ₁ , 8 ₂ , …, 8 _(M+1) and writing the calculated values (V4+1), V3, (V2+2), (V1+3) into registers 8 ₁ , 8 ₂ , …, 8 _{(M +1)} .

Thus, at addresses (Z+1) and (Z+2) in the output buffer of groups OB 2 and in the output buffer of maximum groups OH 16 the corresponding values of the identified single groups and maximum groups in each block BB(Z+1) and BB are written (Z+2). In addition, the values from the outputs of registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) are a group of external outputs of the number of unit groups Q1, Q2,..., Q(M+1), on which the values of the total number of corresponding unit groups for the entire N-bit input data sequence.

Reading of the results to the group of external outputs of the QB groups from the output buffer OB 2 and to the group of external outputs of the maximum groups QH from the output buffer OH 16 is performed under control via the corresponding external control buses EO. When implementing the output buffers OB 2 and OH 16 in the form of a two-port FIFO memory, the exchange can be performed in the process of detecting groups, taking into account the values of the flags “Buffer empty” FZ and “Buffer full” FF.

The proposed device can be used for hardware implementation of statistical tests developed by the Information Technology Laboratory of the National Institute of Standards and Technology (NIST, USA), the purpose of which is to determine the measure of randomness of binary sequences generated by random number generators. In particular, the proposed device implements a test for the longest sequence of ones in a block, which determines the longest sequence of ones within a block of a given length, for example, in blocks containing 8 bits or 128 bits. In eight-bit blocks, the longest sequence of units containing 1, 2, 3, ≥4-bit unit groups is identified.

When processing signals and results of physical experiments, the proposed device ensures the identification of events of a given dimension, determination of their number and maximum events.

The above information allows us to conclude that the proposed device solves the problem, has regularity of nodes and connections, and corresponds to the claimed technical result - expanding the arsenal of tools for the same purpose in terms of the ability to detect groups of unit bits, determine the number of specified groups and identify maximum groups in binary blocks , as well as counting unit groups in the input sequence.

Claims (15)

The device for detecting groups of single bits and maximum groups in blocks of a binary sequence contains an external data input ID of serial input of K-bit data blocks BB from the input N-bit binary data sequence, a group of external outputs of groups QB, a group of external outputs of maximum groups QH, a group of external bus number of unit groups Q1, Q2, Q (M+1) (where M is the bit depth of detected unit groups, 1≤M≤K), clock counter CTC 1, output buffer of groups OB 2, data shift register RD 3, group of ( M+1) comparators 4 ₁ , 4 ₂ , …, 4 _(M+1) , element AND with inverse input 5, group of M counters of unit groups 6 ₁ , 6 ₂ , …, 6 _M , group of (M+1 ) adders 7 ₁ , 7 ₂ , …, 7 _(M+1) , a group of (M+1) registers 8 ₁ , 8 ₂ , …, 8 _(M+1) , trigger TR 9, a group of M elements OR 10 ₁ , 10 ₂ , …, 10 _M , group of M elements AND with inverse input 11 ₁ , 11 ₂ , …, 11 _M , priority encoder 12, OR element 13, maximum group register RH 14, priority register RPR 15 and output buffer maximum groups OH 16, and also introduced external inputs clock IC, synchronous setting to the zero state IR and operation permission ICE, internal data buses BD, matches BEQ, high group BS, number of units in the HV group and priority BPR, internal block start flag F1 and internal maximum flag FH , external EO exchange control buses, external flags “Buffer full” FF and “Buffer empty” FZ, Moreover, the external input of the synchronous setting to the zero state IR is connected to the corresponding inputs of the synchronous setting to the zero state R of the clock counter STS 1, the output buffer of groups OB 2, the data shift register RD 3, registers 8 ₁ , 8 ₂ , ..., 8 _{(M+1 )} and the output buffer of the maximum groups OH 16, and the external operation permission input ICE is connected to the operation permission input CE of the clock counter CTC 1, The external clock input of the IC device is connected to the synchronization inputs C of the CTC clock counter 1, the output buffer of groups OB 2, the data shift register RD 3, the unit group counters 6 ₁ , 6 ₂ , ..., 6 _M , registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) , trigger TR 9, maximum group register RH 14, priority register RPR 15 and output buffer maximum groups OH 16, Moreover, the output of the CTC clock counter 1 is the internal flag of the beginning of block F1, which is connected to the inputs of synchronous setting to the zero state R of counters of unit groups 6 ₁ , 6 ₂ , ..., 6 _M , trigger TR 9, maximum group register RH 14 and priority register RPR 15, and is also connected to the operation permission inputs CE of the output buffer of groups OB 2, registers 8 ₁ , 8 ₂ , ..., 8 _(M+1) and the output buffer of maximum groups OH 16, the external data input ID is connected to the SI input of the serial input of the data shift register RD 3, the outputs of which are bits of the internal data bus BD, moreover, the bits of the internal data bus BD in groups of (i+2) bits (where i=1, ..., M), each of which starts from the first bit, are connected to the second groups of inputs of the corresponding i-th comparators of group 4 ₁ , 4 ₂ , ..., 4 _M , and for the first groups of comparator inputs of groups 4 ₁ , 4 ₂ , ..., 4 _M , zero values are supplied to the first digits and (i+2)-e digits, and unit values are supplied to the second and subsequent digits in the corresponding groups according to (i) digits (where i=1, M), each of which begins with the second digit, in addition, the (M+1)th comparator 4 _(M+1) has unit values supplied to all W bits of the first group of inputs (where W is the bit capacity of the detected unit groups, K/2≤W≤K), and the second group of inputs is connected with the first W bits of the internal data bus BD, starting from the first bit, and the output of the (M+1)th comparator 4 _(M+1) is connected by the direct input of element AND 5 to the inverse input, the outputs of the first M comparators 4 ₁ , 4 ₂ , …, 4 _M are connected to the operation permission inputs CE of the corresponding unit group counters of the same name 6 ₁ , 6 ₂ , …, 6 _M , and are also the same first M bits of the internal BEQ coincidence bus, which (M+1) discharge is connected to the output of element AND 5 with an inverse input, in which the inverse input is connected to the output of the trigger TR 9, in which the input S of the synchronous setting to a single state is connected to the output of element AND 5 with an inverse input, in this case, all (M+1) bits of the internal coincidence bus BEQ are connected to the corresponding inputs of the priority encoder 12, the outputs of which are bits of the internal bus of the number of units in the HV group, which is connected to a group of information D-inputs of the register of the maximum group RH 14, the outputs of which are connected with a group of information D-inputs of the output buffer of maximum groups OH 16, in addition, the first M bits of the internal coincidence bus BEQ are connected to the first direct inputs of the corresponding elements And with the inverse input of the group 11 ₁ , 11 ₂ , ..., 11 _M , the outputs of which are the first M bits of the internal bus of the senior group BS, which has (M+ The 1)th bit is connected to the (M+1)th bit of the internal BEQ coincidence bus, and all (M+1) bits of the internal bus of the high group BS are connected by a group of information D-inputs of the priority register RPR 15 and connected to the corresponding inputs of the OR element 13, the output of which is the internal maximum flag FH and is connected to the operation permission inputs of the CE register of the maximum group RH 14 and the priority register RPR 15, the outputs of which are bits of the internal priority bus BPR, in which the first M bits are connected to the first inputs of the same M elements OR from groups 10 ₁ , 10 ₂ , …, 10 _M , the outputs of which are connected to the inverse inputs of the same elements AND with the inverse input from the group 11 ₁ , 11 ₂ , …, 11 _M , wherein the second inputs of the first (M-1) OR elements of the group 10 ₁ , 10 ₂ , 10( _M-1) , starting from the first to the (M-1)th elements, are connected to the outputs of the corresponding subsequent (M-1) OR elements groups 10 ₁ , 10 ₂ , ..., 10 _M , starting from the second to the M-th elements, and the M-th bit of the internal BPR priority bus is connected to the second input of the M-th element 10 _M , in addition, the outputs of the counters of unit groups 6 ₁ , 6 ₂ , ..., 6 _M and the trigger TR 9 are connected to the corresponding groups of information D-inputs of the output buffer of groups OB 2, and are also connected to the second groups of inputs of the corresponding (M+1) adders 7 ₁ , 7 ₂ , …, 7 _(M+1) , in which the first groups of inputs are connected to the outputs of registers of the same name (M+1) 8 ₁ , 8 ₂ , …, 8 _(M+1) , the outputs of which are also the corresponding ones of the same name external buses Q1, Q2, Q(M+1) number of unit groups, in addition, the output buffer of groups OB 2 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer OB 2 are a group of external outputs of groups QB and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ, moreover, the output buffer of the maximum groups OH 16 is also connected to the external corresponding bus EO exchange control, and the corresponding outputs of the output buffer of the maximum groups OH 16 are a group of external outputs of the maximum groups QH and the corresponding external flags “Buffer full” FF and “Buffer empty” FZ.