Method of identifying signals. RU patent 2485586.

FIELD: information technology.

SUBSTANCE: method of identifying signals is realised by applying essentially different transformations of digital sequences in form of loops to obtain unique shortcut characteristics of said sequences, use as addresses of which allows to cut the number of successive comparisons with references. Reducing operations for comparing the identified signal segment with a reference will drop, in the extreme case, from j operations for comparison on the number of reference signals to two operations: calculating the binary address B_i and determining the identifier C_j of the value of belonging to the reference class.

EFFECT: shorter duration of the procedure of identifying an analysed signal with references and reducing memory needed to store reference signal samples.

6 dwg, 7 tbl

The invention relates to the technical Cybernetics, is a technique that can be used to identify the signals when solving the problems of defining the conditions of the observed objects when their diagnosis or monitoring of dynamic processes. Functional method is intended to reduce computational operations in the procedure for comparison of the analyzed signal with reference signals of each class of States, and also reduce the amount of memory to store the reference signals.

There is a method of analyzing a signal about the state of the object (Kiselev, NV, V.A. Technical diagnostics methods of nonlinear transformation. - HP, Energy, 1980, 109 S.), including the formation with the subsequent correction of recognition of standards based on the training signals, comparison of recognition standards to the analyzed signal with obtaining a set of estimates on the facilities of the real state of an object to each of the many possible States of an object, comparison of the estimates between themselves and with a given threshold for recognition, in result of which the decision on the alleged condition object. The disadvantage of this method is the inability to assess the validity of the process of learning and pattern recognition, which is critical in terms of noise, resulting in poor visibility of the signals relevant to the different States of the object.

Identified gap eliminates the method of analysis of signals about the state of the object (RF Patent №2090928, cl. G06K 9/00, G06K 9/62, G06K 9/66. A method of analysis of signals about the state of the object), that identifies the object's state by introducing a mechanism to measure the reliability of signals and standards through comparison of signals with the standards on the standard scale. This method has limitations in its application to two basic aspects. The first aspect of the restrictions expressed in the possibility to analyze only the digitized signals and the inability to analyze the signals presented not only in digitized form, and (or) in the form of image on plane. The second aspect of the restriction is necessary a priori knowledge of the finite number of classes of object state that restricts the scope of its application in cases where it is the number of unknown or multiple signal sequences initially not fully. An additional disadvantage of the method is expressed in the absence of a mechanism of prior objective of the separation of signals according to the classes of States, taking into account change of the form of signals in time, in turn, allows the possibility of determining the class false or biased merging of multiple signals in false classes States object, which reduces the reliability of further define the state of the object.

Data problems are eliminated by way of analysis of signals about the state of the object (RF Patent №2355028, cl. G06K 9/00, published 10.05.2009, bul. №13). It allows us to analyze signals, presented in digital form, so and (or) in the form of image on plane, with unknown in advance the number of classes of the object state, which, in turn, increases the accuracy of recognition of the state of the object in the systems of technical Cybernetics. This method lies in the fact that consistently carry out a chain encoding signals presented in digital form and (or) in the form of image on plane, determine the minimum number of state classes application of the hierarchical classification of circuits with the definition of the thresholds of Association in classes, counting the Euclidean distance between the classes of all circuits and medium chain orthogonal space, unite the various classes of circuits in one class at a value threshold Association, not exceeding the minimum Euclidean distance between the classes of circuits and secondary circuits orthogonal space, during the procedure for recognition signals normalized form and correct recognize the standards of the signals on the number of state classes, carry out optimization and a comparison of signals and standards in Euclidean vector space with the subsequent recognition of the state of an object until until the recognition result will not satisfy the specified validity or failure. This method is the closest to the technical nature and is selected as a prototype.

Disadvantages of this method are two significant aspects. The first aspect is the time duration of the procedures of identification, since consecutive comparison of the analyzed signal every reference signal separate class in the worst case is comparable with the number of reference classes. The second aspect is to require a significant amount of memory for storage of reference signals presented for each signal N discrete sampling or (N-1) coded values when representing the signals in the form of chains.

The objective of the invention is to create a method of identification signals, which gives two positive effects: reduction of the temporal duration of the procedure of identification of the analyzed signal with the standards and reduction of memory needed to store benchmark copies of the signals.

This task is solved by the fact that of the prototype method at the stage of recognition of the analyzed signal exclude three consecutive procedures:

1. Correction of the recognized standards of signals on the number of state classes;

2. Optimization of signals and standards in Euclidean vector space;

3. Comparison of signals and standards in Euclidean vector space.

Instead of these procedures during the training phase, when formed the reference signals and write memory to identify current analyzed signals, in addition to the actions of the prototype method:

1) carry out the segmentation of signals that have been converted earlier to mind circuits in accordance with the selected shape of the constellation Tons, equal to m segments of the value multiples of eight codes in the range;

2) in computing device (WOO) each segment of n the circuit elements encode binary sequence B i , consisting of two binary sequences of multiple 1st byte, type:

where - 1-I binary sequence is a multiple of 1 byte, 2 binary sequence is a multiple of 1 byte.

The first binary sequence receive for each from 1 to n-th element segment chain encoding values constellations: the growing areas and zero orientation values constellations (1, 2, 3, 4) units and for decreasing directions - values constellations (5, 6, 7) zeros. In fact, the binary sequence describes the qualitative nature of ascending or descending order segment chain without the indication of the quantitative values. As for the segment of the chain with values constellations equal 12344567, binary sequence =11111000 that in decimal terms is a the number 248; for the segment of the chain with values constellations equal 76544321, binary sequence =00011111 that in decimal calculation is the number of 31.

The second binary sequence receive Association in decimal D i quantitative constellation of values from 1 to n-th item selected segment of the chain, and calculation of a hash with the following expression:

where bin - function of a binary representation of the value of the number of decimal system of calculation;

D - decimal Association constellation of values from 1 to n-th element segment of the chain;

mod - function module base;

K is the greatest decimal Prime number, not greater than a decimal number that is divisible by 2 n (for n=8, G k =251 as 2 n =256; for n=16, G k =65521 as 2 n =65536, for n=24, G k =16777213 as 2 n =16777216, etc).

3) at memory B i write the number of facilities of the address to C j class reference signals. So for two reference the classes are two binary values, 0 and 1; for reference classes in excess of the number 3, you must use the binary entry decimal numbers from 0 to (j-1). Memory address B i has the property of uniqueness for each m i plot segment chain and is the identifier facilities interval circuit to the master class at the given address memory.

In recognition of the signal:

1) identifiable signal transforms to mind chain in accordance with the constellation, selected at the stage of training forms Tons, equal to m segments of the value multiples of eight codes in the segment;

2) each m i segment convert to binary sequence B i determine the value of C j class facilities for this segment memory class ID for this segment;

3) estimated the decision of facilities signal to C j a reference to the class is taken by majority rule indicating the ratio of the number of matching identifiers to a number of non-matching IDs that actually shows the percentage of conformity recognized signal reference Q.

New set of essential features of the claimed process is achieved by using different essence digital transformations of sequences in the form of chains, to obtain the unique characteristics of the reduced data sequences, use whose addresses will reduce the number of consecutive comparisons with the standards. Reduction of operations comparison of the unidentified alarm interval with reference to decline in the extreme case j comparison operations on the number of reference signals up to two operations: the calculation of binary address B i and C j membership value to a reference to the class.

The analysis of the equipment has allowed to establish that the analogues, characterized by the totality of features identical to all signs of the technical solution, no, that indicates compliance of the invention with the condition of patentability «novelty».

Search results known solutions in this and related areas of technology for signs that coincide with the distinctive features of the prototype of the claimed process showed that they are obvious from the prior art. Of the level of technology also found no known impact involves the essential features of the claimed invention transformations to achieve the specified result. Therefore, the proposed method meets the criterion of «inventive step».

The claimed method is illustrated by drawings, showing:

figure 1 - algorithm, and clarifies the method of identification signals;

figure 2 constellation coding difference neighboring normalized counts digital signal sequence;

figure 3 - two-dimensional plane addresses for each segment of 32 classes of signals;

figure 4 - the increased two-dimensional plane addresses for segments with values exceeding in the decimal notation 235;

figure 5 - the increased two-dimensional plane addresses for grades 13 and 15;

figure 6 - increased two-dimensional plane addresses for classes 6 and 15.

For a better understanding of the essence of the proposed method on the figure 1 presents the algorithm of realization of the proposed method of identification signals. Between terminators beginning and end (Modelling of systems: Textbook for call / Б.., .. - 4-e Izd., erased. - M: high school., 2005. - P.93) the algorithm consists of separate procedures. Procedures 3-7 correspond to the stage of study, procedures 9-15 correspond to the stage of recognition of signal identification. Blocks 2, 8 and 14 are blocks of the conditions. Block 1 is a block of data input block 16 - unit output data. Below list of rooms, blocks input and output, procedures and blocks execution of conditions of the algorithm:

1 - Block of input data, taking into account the following variables and constants:

C j classes reference signals defined by the method prototype;

K is the greatest decimal Prime number, not greater than decimal number that is divisible by 2 n for the selected variable n;

m - the number of segments a multiple of the value of the eight codes in the segment of the chain;

T - selected shape of the constellation to encode the signal chain.

2 - Block execution conditions, determines the stage of the training in case of positive result, or recognition stage and the transition to the block 3, with negative outcome or formed at an early stage of learning the address structure B i and the IDs belonging to C j class reference signals recorded according to memory addresses, the transition to block 9.

3 - Block coding signal chain S i (CSC-S i ), representation of the signal of any form as a sequence consisting of n codes obtained conversion of the signal on the selected rule in the value of its changes relative to a reference point.

4 - Block highlighting m (SU m) in the chain S i , implements a consistent segmentation the chains on the m equal segments multiple of the value of the eight codes in the segment.

5 - Block coding m i segment in a binary sequence (KC ).

6 - Block calculation of binary sequence (Calculation ) by the formula 2.

7 - Block record identifier belongs to the class C j at B i carries out record number corresponding to the value of the reference class in memory at the address of B i .

8 - power of the condition that defines the end of the training phase in a positive outcome, and the transition to the unit 2, or continuation phase of training with the negative result and the transition to the unit 3.

9 - Block procedures signal encoding in the chain S i (CSC-S i ), carries out actions similar to the actions of block 3.

10 - Block allocation of segments m (SU m) in the chain S i , carries out actions similar to the actions of unit 4.

11 - Block coding m i segment in a binary sequence (KC ).

12 - Unit calculation binary sequence (Calculation ) by the formula 2.

13 - output Unit of memory at B i ID belonging to a C j a reference class for m i segment of the chain.

14 - Block execution of the conditions defining the last segment of the chain in case of positive result and the transition to a block 15 or when the negative outcome of the transition to the block 11.

15 - Block of evaluation of the quality of identification Q equals the ratio of the total number of matching identifiers to a number of segments of the chain.

16 - Unit output value pairs C j reference class facilities and quality indicator identification Q.

In the way-prototype (Russian Federation Patent №2355028. cl. G06K 9/00, published 10.05.2009, bul. №13) sufficient detail the process of transformation as an arbitrary curve and numerical order in the chain. A sequence of n codes obtained transformation curve for the selected rule in the value of its changes relative to a reference point, is called a chain (theory of recognition and scene analysis: Per. from English. / .., ...; Under. amended ... M: Mir, 1976. - 511 C.). Because the values of the signal level can be different values for the prevention of superiority signs with large numeric values are normalized signals. All the values of signals converts in one-dimensional arrays with mathematical expectation equal to 0, and the value of the variance equal to 1. This conversion for each i-th value of reference of a one-dimensional array of the k-th section of the map attractor to the value shall be in accordance with expression (Statistical analysis in MS Excel: - M: Publishing house «Williams», 2004. P.142):

where µ k - mathematical expectation of a one-dimensional array of samples of the k-th section of the map attractors;

σ k is the standard deviation of one-dimensional array of samples of the k-th section of the map attractors.

This conversion will allow to normalise any signals to sequences of single dimension. The transformation of k-th transformed numerical order in the chain x k is the calculation of the arcsine of the difference between the n neighbouring standardized sampling and , when and i belongs to the interval[1, n], in accordance with the expression

As a result of this transformation is formed a chain x k , elements of which are the angle values for n plots with an interval of angles measurement (-90 to 90 degrees). Within this interval use constellation in the least degree to encode difference neighboring normalized values of signals presented in the figure 2. Taking into account the zero interval for constellation encoding receive seven intervals of the difference of normalized neighboring signal values, which are summarized in table 1. Sequence numbers table 1 shows that the first four serial numbers correspond to the positive dynamics of changes in the circuit or signal phase, 5, 6 and 7 ordinals determined the negative dynamics of the changes. The nature of the positive dynamics circuits (intervals circuits) denote the value of 1, and the decreasing dynamics of the value 0. This condition will describe the qualitative change of the signal in time.

The intervals of the constellation coding for seven intervals of the difference of normalized neighboring the values of the cards attractors

Interval value in degrees

The difference of normalized neighboring values attractors card

[60 to 90 degrees)

[0,433 to 0,5)

[30 to 60°)

[0,25 to 0,433)

(0 to 30°)

(0 to 0.25 in)

(0 to -30 C)

(0 to -0,25)

[-30 to 60 degrees)

[-0,25 to -0,433)

[-60 up to 90o)

[-0,433 to -0,5)

Consideration of the declared method appropriate to carry out the following example. For j=32 different signals from N=33 normalized counts have converted the constellation T=7 (see figure 2), and received 32 value chain for each of the 32 signals. Table 2 summarizes the value chains S i for the first nineteen chains belonging to the thirty-two reference signals, and in table 3 summarizes the thirteen circuits. Sequence numbers in tables 2 and 3 indicate the serial number of the code in the loop and correspond to the ordinal values of table 1. Segmentation of each circuit 8 of its elements will result in 4 segments for each circuit. Data values segments for 32 classes of signals are summarized in table 4. Sequence numbers correspond to the numbers in table 4 classes reference signals. The definition of binary sequences for each from 1 to n-th element segment chain perform encoding values constellations: the growing areas and zero orientation values constellations (1, 2, 3, 4) units and for decreasing directions - values constellations (5, 6, 7) zeros. The result of the coding segments circuits table 4 are summarized in table 5. Binary sequence table 5 describes the qualitative nature of ascending or descending order segment chain without the indication of the quantitative values. To obtain binary sequences for each segment table 4 implemented calculation by formula 2, G (k =251. Joint values in decimal form of calculation for display on all 32 reference classes summarized in tables 6 and 7 on the sixteen classes in each table.

The visual display is presented in the form of a two-dimensional plane addresses for each segment of 32 classes of signals figure 3. On the figure on the abscissa axis decimal values and the ordinate decimal values Location coordinates addresses B i on the two-dimensional plane quantized indicates their isolation in the address space for different classes. Enlarged images of two-dimensional plane addresses for segments with values exceeding in decimal notation 235 figure 4, as well as extended two-dimensional plane addresses for grades 13 and 15 figures 5 and for classes 6 and 15 figure 6 indicate the division of unique addresses for each segment of the chain reference the signal. At B i record identifier facilities segment chain C j a reference to the class. So for the 3rd segment of the 15-th class at decimal address B 15 =[255, 8] (see figure 5) at the stage of training will be written to 15 decimal value or value 001111 in binary notation. For the 1st segment of the 15-th class at decimal address In 15 =[252, 169] (see figure 6) at the stage of training will also be recorded 15 decimal value or value 001111 in binary notation.

Storing in the memory identifiers for signs reference class to be implemented in binary form. The dimension of identity for many signals will be determined by the number of reference classes j. In this example, this number is set to 32 classes, therefore, as an identifier reference class is enough to use 6 bits. Value 000000 in the address field B i will point out that an identifiable segment of the chain does not match any of j reference classes.

To store in the memory of one of the reference signal in the form of a chain of M=(N-1) items will be M memory units. At T=7 requires the total amount of memory to store all j=32 reference signals of equal value V 1 =(3 x 32 x M) . as in our case M=32, so the effective amount of memory will be the value of V 1 =384 bytes. The proposed method of each j-th chain of M=32 (each j-th reference signal) requires 8 bytes of the address field, and 6 bits to record identifier that generalizing the class 32, is the amount of effective memory V 2 =280 bytes that 104 bytes less than V 1 .

In the way the prototype for the assignment of the analyzed signal to one of the j=32 reference signals in the worst case would require 32 calculation procedure measures the Euclidean distances between the chains to determine the minimum threshold classification, in the best case, it will take 1 procedure of calculation of Euclidean distance, when strategies average estimated to grow by 16 procedures. In the proposed method for each identifiable signal chain realize the procedure of segmentation, expect address for each segment and fixed at this address the ID of the reference class, and then calculate indicator of the quality of identification of the Q - ratio of the number of matching identifiers to a number of segments of the chain. Thus, we have two computing operations of the segment and one additional step on the calculation of the facilities to the master class. Characteristically, this value is not critical to the number of reference classes and unlike the prototype method is constant, not dependent strategies. Reduction of the computational procedures direct impact on the reduction of the temporal duration of the procedure of identification of the analyzed signal. Covered both aspects confirm the positive effect of the technical solution proposed method.

Additional calculations method does not require significant computational resources, they can be implemented on the current element base, for example, on any commercially available programmable logic integrated circuits (FPGA).

Described essence of the proposed method is that it provides reduction of the temporal duration of the procedure of identification of the analyzed signal with samples of up to two procedures on each segment of the chain and reduction of memory needed to store benchmark copies of the signals.