RU2230331C2 - Procedure establishing clock interval of random flow of pulses with discre te time - Google Patents

Abstract

FIELD: computer engineering. SUBSTANCE: procedure can be utilized for establishment of duration of unit elements of reconnoitered multiposition (multifrequency) signals and for determination of parameters of signals with programmed retuning of working frequencies. Time intervals from moment of emergence of first pulse of input flow to moments of appearance of each pulse in observed realization of flow are measured. Possible values of integral multiplicity factors of time interval are sorted out according to clock interval. Estimates of their common divisors in the form of angular coefficients of straight lines of regression passing through origin of coordinates with equal least sums of squares of departures of own points are found. Maximal angular coefficient of forward regression is taken as value of clock interval. EFFECT: enhanced precision of establishment of clock interval of random flow of pulses with a priory uncertainty of clock probability of their appearance. 3 dwg

Description

The invention relates to the field of computer engineering, in particular to methods and devices for processing statistical data, and can be used to determine the duration of elementary parcels of reconnoitered multi-position (multi-frequency) signals, as well as to determine the parameters of signals with software tuning of operating frequencies.

A known method for determining a constant clock interval of pulse flows with discrete time t _n = nT, n = 1, 2, ..., for which the clock probability of the pulse is equal to unity p _n = p = 1, including measuring the time interval τ _0N between the moments of arrival the first (reference) t ₀ and last t _N pulses in the observed stream implementation, counting the number N _И = N + 1 pulses of the input stream and determining the clock interval by the formula

[1. Mirsky G.Ya. Radio-electronic measurements. Ed. 3rd M .: Energy, 1975, p.223-226].

временного интервала

_0N [1]:The variance of the errors in determining the parameter T in a known manner using formula (1) is N ² times less than the variance of the measurement errors

time interval

_0N [1]:

A disadvantage of the known method for determining the clock interval is the limited scope of its application by periodic flows of pulses, for which the clock probability of occurrence of a pulse is equal to one, with a low accuracy in determining the clock interval.

t_k-1,

между моментами t₀<t₁<...<t_N появления импульсов в наблюдаемой реализации потока и определение с привлечением априорных данных о статистической модели наблюдаемых временных интервалов τ _k,

тактового интервала как параметра соответствующего распределения случайных величин [Левин Б.Р. Теоретические основы статистической радиотехники, кн.2. М.: Советское радио, 1968, с. 122].The closest in technical essence to the proposed method for determining a constant clock interval T of a random stream of pulses with discrete time is a statistical method that includes measuring independent time intervals τ _k = t _k -

t _k-1 ,

between the moments t ₀ <t ₁ <... <t _{N the} appearance of pulses in the observed flow realization and the determination using the a priori data on the statistical model of the observed time intervals τ _k ,

the clock interval as a parameter of the corresponding distribution of random variables [B. Levin Theoretical foundations of statistical radio engineering, book 2. M .: Soviet radio, 1968, p. 122].

Consider the possibilities of the well-known statistical method for determining the clock interval T of a random pulse stream with discrete time using a specific example under two conditions facilitating the solution of this problem:

the clock probability of the appearance of pulses is constant p _n = p = const;

errors of observation (measurement) of time intervals are equal to zero (σ _n = 0).

Under these conditions, sampling time intervals (WMI) τ _k are discrete random variables distributed according to a geometric law shifted by one:

with mathematical expectation and dispersion respectively

For a joint assessment of two constant parameters p and T of distribution (3), we will use the maximum likelihood criterion [Levin B.R. Theoretical foundations of statistical radio engineering, book 3. M .: Soviet Radio, 1976, p.16]. For this purpose, we write the likelihood function of a sample of time intervals of size N in the form of a product of N probabilities (3):

- сумма длин (кратностей) N величин τ _k в единицах Т.Where

- the sum of the lengths (multiplicities) of N quantities τ _k in units of T.

We find the equation for estimating the parameter p by differentiating the logarithm from the likelihood function (5):

The equation for estimating the parameter T has a degenerate form:

since T is the scale factor of VVI.

From equation (6) we find

Thus, an estimate of the clock probability exists if the clock interval is known, and vice versa. In those few cases when the parameter p is a priori known, the estimate of T is found from relation (8):

равна τ _0N, то достаточно измерять временной интервал τ _0N и определять параметр Т по формулеSince the amount

equal to τ _0N , it is enough to measure the time interval τ _0N and determine the parameter T by the formula

We find the accuracy of determining the parameter T using statistics (10) in the presence of measurement errors of the interval τ _0N . The dispersion of the total interval τ _0N in comparison with the dispersion (4) of one interval increases N times:

Given the independent measurement errors (σ _n &λτ;&λτ; T), the variance of the measured time interval τ _0N will be

Using the well-known rule of variation of the variance of a random variable τ _0N multiplied by a nonrandom p / N, we find the variance of the errors in determining the clock interval using the known method (10) in the presence of a priori information about the clock probability (0 <p≤ 1):

Note that for p = 1 formulas (9) and (13) coincide with (1) and (2), respectively.

It follows from (13) that for σ _n ≤ T (in practice, in most cases, σ _n &λτ;&λτ; T), the main share of the error in estimating the parameter T, determined by the first term, is due to the random nature of the FIW lengths. So, at p = 0.5 and σ _n = T, the contribution of the first term is 2N times greater than the contribution made by the measurement errors of the FIW. Obviously, for p <0.5 and σ _n <T, the relative influence of the first term in (13) on the accuracy of determining the clock interval T increases. Therefore, with a limited sample size N, it is not possible to achieve a significant increase in the accuracy of determining the parameter T using the well-known statistical method by increasing the accuracy of observation of FIWs.

Given the above, a significant drawback of the known statistical method is its low accuracy in determining the clock interval and the impossibility of its application in the absence of a priori data on the magnitude of the clock probability of the appearance of pulses of the input stream.

The objective of the invention is to increase the accuracy of determining the clock interval of a random stream of pulses with discrete time with an unknown clock probability of the appearance of pulses while expanding the scope of the method.

The problem is solved due to the fact that in the known method, including measuring the time interval between the moments of the appearance of the first and last pulses in the observed implementation of the stream, additionally measure the time intervals from the moment of the first to the moments of each intermediate in time appearance of the pulse in the observed implementation of the stream, moreover, in the totality of the measured time intervals by organized sorting of possible values of integer multiplicities of time intervals t such as are for interval determined evaluation their common divisors in the form of angular coefficients of the regression lines passing through the origin with identical lowest sum of squares of deviations own points, the magnitude of the maximum clock interval taking the slope of the regression line of said.

In the proposed method, improving the accuracy of determining the clock interval of a random pulse stream with discrete time is provided by a more complete extraction of information about the clock interval contained in the set of overlapping (dependent) random time intervals with independent discrete increments modulo by using the selective properties of mutually prime numbers implemented in statistics of the “greatest common divisor” of discrete random variables, and equalizing (with respect to measured th slots) properties of the regression line passing through the origin with continuous values of time intervals measured by the ordinate axis and the integer values multiplicities clock period T on the abscissa.

The essence of the proposed method for determining the clock interval of a random pulse stream with discrete time is as follows.

First, we assume that the errors in measuring time intervals are zero (σ _H = 0). Then, with a constant clock interval T, we have a system of N≥ 2 linear equations

where τ ' _0k is the discrete time interval between the moments of the appearance of the reference (first) and k-th pulse;

m ₀₁ <m ₀₂ <... <m _0N - unknown random multiplicities (integers) of time intervals τ _0k in units of T.

The system of equations (14) is underdetermined (the number of unknowns is N + 1) and, in the absence of restrictions on the range of values of T, has a countable set of solutions. However, the stochasticity factor of integer multiplicities m _0k allows _us to solve system (14) with respect to unknown T with a non-zero probability. It follows from system (14) that the estimated parameter T is a common divisor (OD) of several N≥ 2 discrete quantities τ ' _0k. The countable set of OD includes the largest common divisor (GCD), for the calculation of which we apply, for example, the Euclidean algorithm [Bronstein I.N., Semendyaev K.A. Math reference. Ed. 8, - M .: Fizmatgiz, 1959, p.129]. The whole set of solutions satisfying the system of equations (14), we find as follows:

where d is the serial number of the OD.

Taking into account (15) and the random nature of the sample elements to determine the interval T, there is a countable set of statistics

Наибольшей вероятностью правильного определения Т обладает первая (d=1) статистикаStatistics (16) are characterized by different probabilities of the correct determination of the interval

The first (d = 1) statistic is most likely to correctly determine T

Statistics (17) correctly determines T if among N multiplicities m _0k WWI (14) there is at least one pair of coprime numbers whose GCD is, by definition, equal to one. Obviously, with increasing sample size N, the probability of fulfilling this condition increases. Statistics (16) with parameters d = 2, 3, ... correctly determine the interval T, if GCD {m ₀₁ , m ₀₂ , ..., m _0N } = 2, 3, ..., respectively, with partial probabilities, the total amount of which is a complement to the probability of a correct determination of T according to statistics (17) to unity:

Determining the discrete components of the sum (18) analytically is a rather time-consuming task.

According to the results of an experiment on a computer, the table shows the probabilities of the appearance of at least one pair of coprime numbers in a sample of size N = 2, 3, 4, 5 of multiplicities m _0k formed from multiplicities m _k with a geometric distribution with parameter 0 <p <1.

Based on the data in the table, the lower limit of the probability values for the correct determination of the constant parameter T using statistics (17) as a function of the size N≥ 2 of the sample with practical accuracy accuracy δ _p = 1 ... 3% can be approximated by a discrete exponent for any value of the clock probability (0 <p≤ 1):

Thus, in the absence of observation errors for time intervals τ ' _{0k, the} variance of the conditional (with probability (19)) estimate of the parameter T using statistics (17) is zero. Comparing this result with (13) for σ _H = 0, we conclude that the interfering factor of discrete quantities in (10) is converted in statistics (17) to a factor that provides a new quality of estimates of the parameter T.

Formula (19) determines the potential possibilities of the proposed method for σ _n (ρ) 0 depending on the size N of the sample.

Under real conditions, VVI (14) are endowed with random observation errors Δ _k with parameters: E (Δ _k ) = 0, D (Δ _k ) = σ $\genfrac{}{}{0ex}{}{\text{2}}{\text{n}}$ :

, m=1, 2,... Поэтому при наличии ошибок наблюдения (σ _н≠ 0) поиск оценок НОД в предложенном способе реализован в рамках предписаний метода наименьших квадратов с использованием прямых регрессии вида у=bх, где x - целочисленный аргумент.Obviously, the GCD of several discrete quantities with structure (14) is the maximum angular coefficient of a straight line passing through the origin with zero sum of deviations from the nodal points of a rectangular discrete lattice {m _k Т, m},

, m = 1, 2, ... Therefore, in the presence of observation errors (σ _n ≠ 0), the search for the GCD estimates in the proposed method is implemented within the framework of the least square method requirements using direct regression of the form y = bx, where x is an integer argument.

₀) прямой регрессии по измеренным ВВИ (20) при произвольно заданном (либо известном) N-мерном векторе кратностей

₀ определяется из условия минимальной суммы квадратов уклонений:The angular coefficient b = T (

₀ ) direct regression according to measured VVI (20) with an arbitrarily given (or known) N-dimensional vector of multiplicities

_{0 is} determined from the condition of the minimum sum of squared deviations:

Equating the Derivative to Zero

we find the angular coefficient of direct regression

If the true multiplicities of time intervals (20) are known, then the variance of the estimate (21) of the clock interval T will be [Linnik Yu.V. Least squares method and the basics of observation processing theory. - M .: Fizmatgiz, 1962, p.124, formula (5.2.7), in which weights p _{i are} replaced by weights m $\genfrac{}{}{0ex}{}{\text{2}}{\text{0k}}$ ]

₀ заявленный способ включает процедуру перебора его целочисленных компонент с целью нахождения линии регрессии с наименьшей (нулевой при σ _н=0) суммой квадратов уклонений собственных точек {τ _0k, m_0k,},

To search for an unknown integer multiplicity vector

_{0, the} claimed method involves the procedure of sorting its integer components in order to find the regression line with the smallest (zero for σ _n = 0) sum of squares of the deviations of the eigen points {τ _0k , m _0k ,},

- пробная оценка (21) параметра Т по текущему вектору кратностей при переборе возможных значений его N целочисленных компонент.Where

- a trial estimate (21) of the parameter T according to the current vector of multiplicities when enumerating the possible values of its N integer components.

, d=1, 2,..., то в соответствии со статистикой (17), для которой d=1, максимально правдоподобную оценку НОД "в шумах" находят по формуле (21) при векторе кратностей

, выбранном по правилу (23) с наименьшей суммой его компонент:Since the sums of squared deviations in (23) (including the smallest) are repeated for multiplicity vectors

, d = 1, 2, ..., then, in accordance with statistics (17), for which d = 1, the most plausible estimate of the GCD “in noise” is found by formula (21) with a multiplicity vector

selected by rule (23) with the smallest sum of its components:

In other words, the maximum angular coefficient of the direct regression passing through the origin with the smallest sum of squares of deviations of the eigen-points is taken as the time interval.

For the implementation of procedure (23), organized sorting of the integer components of the N-dimensional vector of multiplicities is advisable. The enumeration tree of their possible values, assigned taking into account the relative values of explosive weapons, is formed as follows.

The possible time values of the multiplicity m ₀₁ = 1, 2, ... are assigned to the first time interval τ _01. For each value of the multiplicity m _01, other time intervals of the sample are assigned according to (2v + 1) possible values of the multiplicities:

where] · [is the integer part of the number;

v is the branching parameter of the search tree, determined empirically and depending on the relative level of observation errors σ _H / Т. In the range of observation error levels 0 <(σ _n / T) ≤ 0.2, the parameter v ≤ 2.

Note that for σ _n = 0, procedure (23, 24) reduces to an algorithm for computing the GCD of several N≥ 2 discrete quantities (numbers).

The proposed method is new, because from generally accepted information there is no known method for determining the clock interval of a random pulse stream in the absence of a priori information on the magnitude of the clock probability, including the measurement of N≥ 2 overlapping time intervals from the moment the first pulse arrives to the moment each subsequent input pulse appears, organized by enumerating the possible values of their multiplicities to the clock interval in order to find estimates of common divisors in the form of angular coefficients ryamyh regression through the origin with identical lowest sum of squares of deviations own points, the magnitude of the maximum clock interval taking the slope of the regression line of said.

The proposed method has an inventive step, since it does not explicitly follow from published scientific data and known technical solutions that the claimed sequence of operations with a pulse signal for generating a sample of overlapping time intervals between the reference (first) and each subsequent pulse of the input stream and opening their discrete structure in due to the sharing of the selective properties of coprime numbers, which are random multiplicities of time intervals to clock int the interval, and the leveling (with respect to the measured time intervals) properties of direct regression will lead to an increase in the accuracy of determining the clock interval in the absence of a priori information about the magnitude of the clock probability.

The proposed method is industrially applicable, as for its technical implementation can be used typical logical and structural elements of discrete and computer technology.

Figure 1 shows an enlarged structural diagram of a possible variant of the technical implementation of the method, figure 2 - the implementation of a random stream of pulses with discrete time, figure 3 - experimental dependencies of the probabilities of the correct determination of the vector of the multiplicities of time intervals of the proposed method on the parameters of the pulse stream and their errors observations for sample size N = 4.

The structural diagram of a possible implementation of the proposed method (figure 1) contains a time interval converter - code 1, frequency divider 2, memory unit 3, microprocessor 4 and delay element 5; the input of the converter 1, combined with the recording input of the memory unit 3 and the input of the frequency divider 2, is the input of a random pulse stream φ (t) with discrete time (Fig. 2), the output of the divider 2 through the delay element 5 is connected to the start input of the microprocessor 4 and the input "reset" of the converter 1, the bit output of which is connected to the bit input of the memory unit 3, the bit output of the latter is connected to the bit input of the microprocessor 4.

из блока памяти 3 в оперативную память микропроцессора 4, который запрограммирован на вычисление тактового интервала T по формулеThe scheme works as follows. In the initial state, the memory elements of blocks 1 and 2 are in the zero state. The first pulse of the input stream φ (t), the implementation of which is shown in FIG. 2, writes the zero code of the initial state of the converter 1 to the memory unit 3 as a marker for starting a series of N values of selected time intervals, simultaneously enables the operation of the converter 1 and increases the state of the frequency divider 2 per unit. By the time the second pulse of the input stream appears at the output of the converter 1, there is a code equivalent of the value of the first time interval τ ₀₁ with a common observation error (including the error of the converter 1), which is written to the memory unit 3 by the same pulse. By the time the third pulse of the input stream arrives at the output of the transducer 1, running cumulatively, there will be a code equivalent of the value of the second time interval τ ₀₂ with observation errors similar to the first interval τ ₀₁ , which the same (third) pulse is recorded in the memory unit 3, etc. Each pulse of the input stream increases the state of the frequency divider 2 by one. By the moment of arrival of the (N + 1) -th pulse of the input stream, the output of converter 1 will contain the code equivalent of the value of the N-th time interval τ _0N , which is entered into the memory block 3 with the same pulse of the input stream. From the output of the frequency divider 2 (N + 1) the pulse delayed by the delay element 5, sets the initial (zero) state of the converter 1, interrupts its operation and at the same time transfers the code equivalents of the values of the time intervals τ _0k ,

from memory block 3 to the RAM of microprocessor 4, which is programmed to calculate the clock interval T according to the formula

- измеренные временные интервалы входного потока импульсов;where τ _0k ,

- measured time intervals of the input pulse stream;

} - оценка вектора кратностей временных интервалов τ _0k,

тактовому интервалу Т, удовлетворяющая системе их двух требований:{

} is an estimate of the vector of multiplicities of time intervals τ _0k ,

the clock interval T, satisfying the system of their two requirements:

- пробная оценка параметра Т для текущего вектора кратностей при переборе его целочисленных компонент: {m₀₁=1, 2,..., m₀₂=2, 3,... m_0N=N, N+1,...} с учетом условия m_0l&λτ; m₀₂<...<m_0N;Where

- a trial estimate of the parameter T for the current vector of multiplicities when enumerating its integer components: {m ₀₁ = 1, 2, ..., m ₀₂ = 2, 3, ... m _0N = N, N + 1, ...} subject to the condition m _0l &λτ; m ₀₂ <... <m _0N ;

The beginning of a new cycle of operation of the circuit (Fig. 1) is preceded by a pause equal to the value of the (N + 1) th time interval, after which a zero code of the initial state of the converter 1 will be entered into the memory block with the 3 (N + 2) th pulse, dividing separate samples from N time intervals. Further, the operation of the circuit is repeated.

четырех временных интервалов N=4 от относительного уровня ошибок наблюдения σ _н/Т для различных величин тактовых вероятностей р, полученные методом статистических испытаний разработанного способа на ЭВМ, приведены на фиг.3. Число испытаний для каждой точки N_исп=1000. Из анализа этих зависимостей следует, что влияние уровня ошибок наблюдения на вероятность правильного определения вектора кратностей снижается с увеличением тактовой вероятности р и тактового интервала Т при постоянном уровне ошибок σ _н=const.Experimental dependences of the probabilities of the correct determination of multiplicity vectors

four time intervals N = 4 of the relative level of observation errors σ _n / T for various values of the clock probabilities p obtained by the method of statistical testing of the developed method on a computer are shown in Fig.3. The number of tests for each point N _isp = 1000. From the analysis of these dependencies it follows that the influence of the level of observation errors on the probability of correctly determining the multiplicity vector decreases with an increase in the clock probability p and the clock interval T at a constant error level σ _n = const.

Improving the accuracy of determining the clock interval of a random pulse stream with discrete time with an unknown clock probability compared to the prototype is achieved in the proposed method due to a more complete use of information on the measured overlapping time intervals N≥ 2 with independent discrete increments modulo, while in the prototype measure only one maximum time interval between the first and (N + 1) -m (last) pulse of the input stream.

с учетом схемы образования ВВИ и геометрического распределения их независимых дискретных приращений по модулю.For cases of the correct determination of the vector of multiplicities, we find the average variance of the errors in determining the clock interval

taking into account the scheme for the formation of explosive weapons and the geometric distribution of their independent discrete increments modulo.

ВВИ в виде начального момента второго порядка:Using (4) at T = 1, we find the mathematical expectation of a square of random multiplicities

VVI in the form of an initial moment of the second order:

математические ожидания и дисперсии их кратностей параметру T равны соответственноIn accordance with the scheme of the formation of time intervals τ _0k = τ ₁ + τ ₂ + ... τ _k ,

the mathematical expectations and variances of their multiplicities are equal to the parameter T, respectively

Substituting (27) into (26), we find the mathematical expectation of the square of the multiplicities of the individual time intervals τ _0k ,

Taking into account (22) and (28) with a correctly defined vector of multiplicities, the average variance of the errors in determining the clock interval T is

and does not depend on the value of T.

Compared with the prototype method with error dispersion (13), the inventive method with error dispersion (29) provides a gain in terms of the mean square error (SKO) of determining the clock interval equal to

subject to the correct opening of the structure (vector of multiplicities) of time intervals.

For example, with a clock probability of p = 0.9, a relative error in the measurement of time intervals σ _n / T = 0.1, and a sample size of N = 4, the proposed method provides a probability of correct opening of the structure of time intervals close to unity (see Fig. 3) , while the magnitude of the gain in standard deviation when determining the clock interval is B _pr ∀ 10 times.

, известны: m₀₁=1, m₀₂=2,..., m_оN=N и в соответствии с формулой (30) безусловный выигрыш по сравнению с аналогом составитIn addition, the proposed method allows to determine the clock interval and the periodic pulse flow (p = 1). In this case, the multiplicity of time intervals τ _0k , k, k =

are known: m ₀₁ = 1, m ₀₂ = 2, ..., m _оN = N and, in accordance with formula (30), the unconditional gain in comparison with the analogue will be

In particular, for the sample sizes: N = 4, 8, 12, the gain (31) is B _en = 1.37; 1.78; 2.13 respectively.

Another, no less important, advantage of the claimed method for determining the clock interval T is the fact that it overcomes the a priori insufficiency of data on the magnitude of the clock probability, which, in comparison with the prototype, expands its scope and solves the estimation problem (using formula (8)) the second determining parameter p of the stationary (p = const) random stream of events with discrete time.

Claims (1)

A method for determining the clock interval of a random stream of pulses with discrete time, including measuring the time interval between the moments of the first and last pulses in the observed flow implementation, characterized in that they additionally measure time intervals from the moment of the first to the moments of the appearance of each time-delayed pulse in the observed the implementation of the flow, moreover, according to the totality of the measured time intervals by organized sorting of possible values of the integer the calculated multiplicities of time intervals to the time interval determine the estimates of their common divisors in the form of angular coefficients of direct regression passing through the origin with the same least sums of squares of deviations of the eigenspaces, while the maximum angular coefficient of direct regression from the number indicated is taken as the time interval.

Images