Head of Laboratory – Full member of the Russian Academy of Sciences,

Dr.Sc. (Technology), Prof. Nikolai Kuznetsov

Tel.: (095) 209-42-25, (095) 299-83-54; E-mail: director@iitp.ru

The leading researchers of the laboratory include:

• analysis of systems with complex non-linearities (hysteresis, delays, round-off and discretization effects);
• asynchronous systems;
• hybrid systems;
• oscillation theory, Hopf bifurcations, stability;
• network optimization.

It is shown, that for low-density parity-check (3,K)-codes, K>3, both block and convolutional, the error probability decreases with number of iteration not weaker than exponentially, and for (4,K)-codes, K>4, not weaker than on double exponent. Theoretical proofs confirmed by simmulations.

It is proved, that using of our adaptive method of transmission "down" from base station to mobile increase the system capacity at least two times. This was confirmed also by simulations.

The generalized concatenated constructions of perfect codes were considered. For each construction the lower bound for the number of different resulting codes is obtained.

The coset weight distribution of several classes of Z_4-linear Goethals codes are considered. In particular the coset weight distribution is found for Z_4-linear Goethals codes and also for the binary Goethals-like codes obtained from the last codes by the Gray map. The exact expressions for the number of code words of weight four of cosets of weight four are obtained in terms of Kloosterman sums. This gives some results also for possible values of Kloosterman sums, which improve some earlier results of Lachaud and Wolfmann. Studying the coset weight distributions of generalized Z_4-linear Goethals codes, the connection with Dickson polynomials is also found. We can express the number of code words of weight four as the number of solutions of some equations for Dickson polynomials over finite field.

The following results are obtained. The connection between binary cyclic codes and binary sequences with trinomial properties is considered.

The trajectory attractors were constructed for dissipative equations of mathematical physics with rapidly oscillating terms. It was proved that if the oscillating frequency tends to infinity, then these attractors converge to the corresponding trajectory attractors of the averaged equations.

An expicit estimate was derived for the deviation of the global attractor of a reaction-diffusion system from the global attractor of the corresponding averaged reaction-diffusion system.

The attractors were studied for dissipative nonlinear hyperbolic equations and for reaction-diffusion systems in unbounded domains. The upper and lower estimates were found for the Kolmogorov epsilon-entropy of these attractors in any bounded subdomain.

It is shown that the fractal dimension of the global attractor of the two-dimensional Navier-Stokes system admits the same estimate as the Hausdorff dimension, namely, both are bounded from above by the Lyapunov dimension calculated in terms of the global Lyapunov exponents.

Upper bound for reliability function of Gaussian channel was improved. Some method developed by M. Burnashev almost 20 years ago for another problem turned out be very useful in that task as well.

Sufficient conditions when channel identification capacity coincides with Shannon capacity were obtained. Some examples when they are different are also presented.

The main direction of the researches was related to development statistical approach for some inverse problems for partial differential equations. The obtained results are concerned with the principle of empirical risk minimization for choice of the optimal solution from a given family. It was proved that under the right penalization, which is defined by the type of the inverse problem, this principle gives a solution with the almost optimal risk. On the other hand this approach does not use the prior information about the smoothness of boundary or initial conditions.

The system of diagnostics of tree-like processor net is constructed. This system is based on algebraic codes, implementation opposite signature analysis. The method of diagnostics of certain devices is constructed. The devices are, intend for counting in finite fields. The Kerdock code properties as separating system are investigated.

The race of information creation in channels without memory was studied for slowly changiry Markov signals. Under the assumption that the input signal is a stationary Markov chain with a finite number of states and rare transitions, it is proved that the rabe of information creation is asymptotically equivalent to the chain entropy, therefore the main asymptotic term cloes not depend on the noise power in the channel.

The filtration problem was studied for stationary singular stochastic processes with nonstationary perturbations. Sufficient conditions for the error-free filtration were obtained for some models of nonstationary perturbations.

The Non-Prefix Context Tree models of discrete sources let us better approximate the statistical properties of real data (e.g. texts) than the Prefix ones. Since the set of all such models is very large, the methods of multimodel universal coding of some “reasonable” subsets of Non-Prefix Context Tree sources were proposed.

It is known that the Burrows-Wheeler Transformation (BWT) let us essentially decrease the complexity of coding (compression) of data, but the efficiency of coding is less than of many “classical” algorithms. The algorithm of mixed “number-symbol” coding of data at the output of BWT was proposed and it’s efficiency was studied experimentally.

The themes of research were: Statistical parameter and nonparametric estimation, Statistical inverse problems for Partial differential equations, Averaging principle for the processes with null-recurrent fast component.

Within the frame of "Research on noise-immunity of digital methods of speech compression and transmission based on autoregressive speech production model" acoustic noise robustness of pitch estimation procedure of IMBE codec (TIA/EIA-102.BABA standard) was investigated along with the contribution of its variance to overall IMBE coding quality. The original algorithm modifications are offered (in particular look-ahead and look-back tracking procedures and pitch refinement procedure) that enhance its noise-immunity and thus improve "voiced/unvoiced segment" decision quality for each of codec's working frequency band.

A cross-development system (based on Oberon-2 translators to C), developed and implemented in 1998-1999 for standard 32 bit CPU (Intel x86, Motorola 680x0, PPC, etc.) and for modified Harvard architecture DSP (Analog Devices 16 bit integer ADSP-21xx and 32 bit float ADSP-21xxx) was transfered along with libraries to POSIX compliant operating systems (BeOS, Linux, QNX, etc). Unix-dependent modules of OOC project libraries were adapted accordingly. Translators and libraries manuals were prepared.

Various problems on existence of nontrivial self-oscillations in nonlinear autonomous control systems were studied. New a priori existence criteria were presented. They use double-side sector estimates of nonlinearities and simple asymptotic conditions at zero and at infinity. The sector estimates are standard in the stability theory and in various problems on forced oscillations, in problems on self-oscillations they were applied probably for the first time. The efficiency of the theorems presented is determined by the width of the sectors. The algorithms were presented to estimate periods of cycles if the sector is fixed and to find the maximal sector using characteristics of the linear part. For Hamiltonian control systems the method allow to formulate results on the existence of global continuum of cycles with all positive amplitude. The simple criterion for Lurie control systems is obtained to be Hamiltonian.

The resent investigations of new classes of Hopf bifurcations for autonomous systems with parameters were continued. The term Hopf bifurcation defines the situations where periodic cycles appear in a vicinity of the equilibrium or at infinity for values of the parameter close to some bifurcation point. Let us stress the principal difference between bifurcations at zero and at infinity: for these bifurcations different classes of nonlinearities are natural and important (the classes can not be connected with transformations of the inversion type). In classical theorems bifurcation points are determined by the linear part: each bifurcation point is a value of the parameter where the linear part becomes degenerate (the pair of eigenvalues of the corresponding matrix crosses the imaginary axis in the complex plane). The absolutely new situation appears if the linear part does not depend on the parameter at all. To study such situations we presented a new method to construct and to analyze some equivalent topologically nondegenerate operator equations and we obtain simple rules to find bifurcation points using asymptotic behavior of small sublinear terms of nonlinearities at zero or at infinity. First results were obtained about stability of (small or large) cycles, about the type of bifurcation (sub- or supercritical), about the asymptotics of cycles, etc. The method presented is also applicable (and very simple!) for classical bifurcations defined by the linear part. The method is aimed at analyzing problems with nonsmooth nonlinearities. We studied Hopf bifurcations in systems with Prandtl-Ishlinskii hysteresis nonlinearity. In natural situations in such systems there exist one-parametrical continua of large cycles (for functional nonlinearities the uniqueness is the main case).

We studied various resonant (asymptotically linear at infinity) problems with unbounded nonlinearities. The original approach is presented to analyze such problems. The approach uses the convergence to zero of projections of nonlinearity decrements. Applications to boundary value problems, problems on forced oscillations and self-oscillations, bifurcations are studied.

One of the main conditions in Classical Hopf Theorem is the nonresonace condition: when the pair of eigenvalues crosses the imaginary axis, the other eigenvalues must not be their multiples. Some situations were studied when this condition failed.

The resonance 2:1 (strong resonance) in control systems was studied in details. Quadratic terms of nonlinearities determine if cycles of "almost double" period appear. These cycles differ from the usual ones: they exist at the both sides of the bifurcation point (in some cases two cycles at each side), they are generic 4-dimension curves (the classical ones are asymptotically 2-dimensional). Bifurcation diagrams were studied.

The resonance m:n (weak resonance) was studied. In such resonance due to Hopf theorem there are two families of cycles with periods close to n^-1 and with periods close to m^-1. The natural question is if there exist subharmonics with the period close to 1. For the first time, this problem was considered by Mayer in 1939. Further results in this direction became classical and are presented in many monographs and even textbooks in differential equations. Generally speaking the situation is as follows. If the nonlinearities in system are smooth, then generically continuous branches of subharmonics do not appear. More precisely, it is necessary to have an additional equality for such branches to exist. Under this condition in beaks of sinchronization there exist invariant tori in phase space. We studied nonsmooth case with the principal homogeneous part. Here the situation is dramatically different from the classical one: generically branches of subharmonics exist.

A close situation (the dependence of the answer on the smoothness of the main nonlinear part) appear in some other problems on subharmonic bifurcation. In 1970 V. Kozyakin discovered and studied the subfurcation effect (for parameter values close to the bifurcation point there exist sporadic oscillations with unboundedly increasing periods). This effect is generic and it is also defined by the smoothness of the principal parts of nonlinearities. If the principal parts of the nonlinearity is nonpolynomial, then the subfurcation does not exist: we have usual continuous brunches of subharmonics.

New classes of iteration algorithms were presented to solve boundary value problems with nonmonotone continuous nonlinearities, based on the so-called shuttle-iteration method. These algorithms converge to robust stable solutions or to robust stable branches of solutions (e.g. having nonzero topological index) and contain double-side estimates for these solutions (branches).

The recent methods to analyze nonpotential problems by means of classical potential techniques were developed. The methods use averaging of nonlinearities in phase variables. New solvability conditions were obtained for vector boundary value problems for ODE and periodic problems for systems with hysteresis.

The problem of perturbations of attractors of skew-product dynamical systems was investigated. An "inflation" technique was proposed which reduces the problem to the analysis of set-valued autonomous systems. Obtained results demonstrate that the attractor of the original system may be approximated with any desired precision by attractors of "inflated" systems as the "inflating balls" tend to zero. The robustness of attractors with respect to perturbation of the driving component is established in the case when the driving component possesses the shadowing property.

The problem of influence of perturbations on properties of attractors of dynamical systems and the very fact of their existence is now recognized to be of key importance. The problem is especially difficult for nonautonomous systems, a broad subclass of which form the so-called skew-product systems. In skew-product systems the "driven" component describes the dynamics of the original system depending on an external parameter, while the dynamics of this external parameter is not arbitrary but covered by some "driving" dynamical system. It turned out that at the expense of the skew-product structure it is possible to get a variety of conclusions.

Within the bounds of skew-product approach the problem on influence of permanently acting perturbations on limiting properties of a system is treated as one of the most difficult. To analyze it, the idea of "inflation" of dynamical systems was proposed which reduces the problem to that of investigation of dynamics of auxiliary autonomous set-valued systems.

It was shown that generally the attractor of the original system may be approximated with any desired precision by attractors of "inflated" systems as the "inflating balls" tend to zero. Due to this, it was demonstrated that the procedure of inflation of a dynamical system is equivalent, in a sense, to consideration of all possible procedures of numerical modelling of the original system. From this the positive answer to the question about possibility of tracing the properties of attractors of skew-product systems by numerical methods clearly follows.

Systems desynchronized by phase and frequency give us natural and practically important examples of skew-products. Here the driving component is represented by a linear shift mapping on a multidimensional torus while the properties of driven component depend in a piece-wise constant manner on the driving parameter. By using the technique of shift dictionaries developed earlier conditions were obtained under which the existence of a single bounded stable trajectory in a two-component desynchronized system guarantees the existence of the both forward and pullback attractors.

The situation is much more complicated when, in a skew-product system, perturbations affect not the driven component but the driving one. The main reason for this is that even under infinitesimally small perturbations of the driving component their influence on the driven component is accumulated with time. When investigating the limiting behaviour this results in nonlocal perturbations of a system. Here one should distinguish between two cases, the first one is when perturbations are introduced in the system on the stage of their affecting the driven component (weak perturbation), and the second one is when perturbations affect the very dynamics of the driving component (strong perturbations). It turned out that the analysis of the systems with weak perturbations can be fulfilled within the frameworks of inflation ideology. Analysis of systems with strong perturbations was also fulfilled after it was noted that this case may be reduced to the analysis of weak perturbations in the case when the driving component possesses the shadowing property. It worth to remark that shadowing is inherent in a broad variety of systems with chaotic properties.

The research of mathematical hysteresis and related topics was continued. On the basis of the characterization result claiming that, under additional assumptions, each continuous hysteresis nonlinearity with short memory is a Skorokhod problem (SP) up to a nonsingular change of variables, the main attention was paid to SPs and their nonautonomous generalizations - sweeping processes. Here, essential progress has been made.

First, since the continuity properties of polyhedral PS are known to be related to various stability properties of finite sets of oblique projections (discrete linear inclusions), the research of infinite products of matrices was continued, where the properties of left converging products (LCP) and right converging products (RCP) play the key role. An easily verifiable necessary and sufficient condition of LCP=RCP was found (the transversality condition). It was also proved that, for finite sets of matrices that are both LCP and RCP (in particular, for sets of orthogonal projections onto linear subspaces), products of arbitrary linear ordered sets of matrices are well defined and possess the property of bounded variation. This result is a key to directional differentiation of hysteresis processes and, moreover, might have a strong impact in applications (say, computer tomography), where projection methods are widely used.

The transversality condition together with the LCP property of the so-called associated projection system of a polyhedral SP has been proved sufficient for the Lipschitz continuity of the input-output operator of this SP in the spaces of continuous and absolutely continuous functions simultaneously.

Sweeping processes with variable reflection field on the boundary of a convex closed set (also variable) were studied together; a condition of regularity was found ensuring continuity of the resulting input-output operator. Another joint project was concerned with directional derivatives of hysteresis nonlinearities described as sweeping processes. Here the one-dimensional case was completely studied and the results were written in a compact form by means of a new technique involving generalized limits. The same technique proved to be very fruitful in extending definitions of general sweeping processes. Namely, the output of a sweeping process is defined as a generalized limit of finite sequences of projections onto the changing characteristic set as the finite partition of the time interval is infinitely refining (now, all existence results become trivial). New averaging results concerning the behavior of periodic sweeping processes with slowly changing parameters are easily derived. The research of directional derivatives of multidimensional polyhedral sweeping processes is now in its final stage.

A surprising relation between nonsmooth optimization and mathematical hysteresis has been discovered. The condition of D-regularity (named after the Demyanov metric) that was earlier proved to ensure the survival of the continuity property of convex-valued maps under nonempty intersection, has now been found to guarantee the continuity of sweeping processes with normal reflection in the uniform metric. Closely related is also the following new result: The D-regularity assumption makes convergent a wide variety of projection methods that find applications in image reconstruction, nonsmooth optimization, etc.

One of the most important areas of application of SPs and related techniques is the theory of queueing networks. A decisive progress was made in studying convergence and continuity properties of deterministic single-class flows with queues. The main tool used here was the theory of discrete linear inclusions, where previous unpublished results on unique solvability and continuous dependence were successfully used. All existing constraints on the queueing processes in question were lifted; the resulting theorem allows one to draw far-reaching conclusions for stochastic networks, both single- and multiclass ones. In particular, new fluid approximation results with essentially weaker assumptions on the input and serving stochastic processes can be derived.

A new approach on fair bandwidth allocation to competing traffic streams is proposed. Traditional bandwidth allocation methods can lead to unfair quality of service experienced by different flows. Simulations of wireless systems supported the efficiency of the proposed algorithm. A simplified version of the algorithm (of linear complexity) delivering the same asymptotic performance was also proposed.

A comprehensive study of ATM routing algorithms with multiple quality of service requirements in PNNI networks. The study recommends the best quasi-optimal algorithm for the analyzed scope of networks and traffic scenarios.

A novel method of splitting ATM connection with large bandwidth requirements into multiple sub-connections routed individually is proposed and its efficiency is studied. As simulations demonstrated, splitting the connection into two subconnections is the most efficient approach.

Two algorithms for construction of QOS-aware multicast trees are proposed. One algorithm, the benchmark one, is unscalable; another one is a scalable simplified version of the first algorithm. The second algorithm can be implemented in the extended framework of PIM-SM. The paper shows that the difference in performance between the two is not large for realistic networks.

The solution of the optimal filtering problem and parameter estimation problem for the systems with fractional Brownian noises has been obtained. We have proved the asymptotic stability property of optimal linear filter for such type of systems and we have obtained the asymptotic behavior of the bias and mean square error of the parameter estimator. The homogenization problem for the parabolic operators with random coefficients and with large potential has been solved. We have got the limiting behavior of the solutions of such type parabolic equations as a solutions of stochastic partial differential equations with constant coefficients.

Researches were continued in the domain of hybrid and timed systems. In 2000 we explored the effect of small perturbations on the computational power of hybrid systems and of classical transition systems. Several algorithms and semi-algorithms were developed for analysis and synthesis of hybrid systems. In particular, these algorithms were applied to control of under-actuated mechanical systems.

The reliability of computer models of complex nonlinear systems was studied. The following key problems were considered: 1) to establish relationships between different graph theory characteristics of a statistical ensemble of discretizations of a dynamical system; 2) to investigate how these characteristics depend on discretization step size or more generally the type of computer arithmetic; 3) to clarify how combinatorial characteristics of an ensemble of discretizations depend on entropy-related characteristics of the underlying system, and vice versa.

Our approach is based on some phenomenological models of ensembles of discretizations. These models should be qualitatively consistent with the results of computer experiments, and admit rigorous mathematical investigation. Perhaps the simplest analogy to this approach would be thermodynamics where, rather than follow every particle of gas in a room, we use the simpler microscopic mathematical models of statistical physics to estimate the macroscopic characteristics of the gas such as the entropy or temperature. In this sense the random transformations are to be considered as the phenomenological models of discretizations of dynamical systems.

The construction of these phenomenological models falls naturally into two stages. At the first stage, one considers random transformations which are nonequiprobable: each point is assigned a weight reflecting the nature of the original dynamical system. However, only broad features of these weights can be convincingly attributed to the underlying continuous transformation whose discretizations we are considering. We hope to identify these features through a "thermodynamic limit" in which the number of points of the discretization increases to infinity. Thus we need a second stage, in which the nonequiprobable random transformations are replaced by suitable limits in which much of the detail of the distribution of images disappears.

Here with a given transformation on a finite domain, we associate a three-dimensional distribution function describing the component size, cycle length, and trajectory length of each point in the domain. We then consider a random transformation on the domain, in which images of points are independent and identically distributed. The three-dimensional distribution function associated with this random transformation is itself random. We show that, under a simple homogeneity condition on the distribution of images, and with a suitable scaling, this random distribution function has a limit law as the number of points in the domain tends to infinity. The proof is based on a Poisson approximation technique for matches in an urn model. The result helps to explain the behavior of computer implementations of chaotic dynamical systems.

It is crucial to verify that a particular random mapping can be used as a phenomenological model for an ensemble of discretizations of a dynamical system within a given level of accuracy. To this end reliable estimates of some special characteristics of random mappings are necessary. The second principal result of the project is the method mixed moments as a principal tool to verify the pneomenological models.

In some case the limiting behavior of a random transformation may be indistinguishable from that of a completely random transformation or a transformation with an attracting center. Finally, note that for the systems with strong algebraic structure quite different methods should be used.

Many systems arising in physic, mechanic, control theory, environmental modeling etc. include strongly nonlinear links with nonstandard and unpleasant, from the point of view of classical mathematical analysis, properties. For instance, they can demonstrate hysteretic behaviour, include discontinuities, desynchronizations etc. The classical methods of theoretical analysis are often inadequate for investigation of such systems. On the other hand, computer modeling in this area often lead to some dangerous artifacts and pathologies. This requires systematic and careful approaches to qualitative and numerical methods of analysis of systems with strong and non-standard nonlinearities.

In frames of this project a principally new approach to stability analysis of the systems with hysteresis is suggested. In particular, important progress has been made, we present some principally criteria conditions for the asymptotic stability of forced almost-periodic oscillations in nonlinear systems subject to small hysteretic perturbations. The cases of forced periodic or almost oscillations are considered as well as free oscillations. Both local and clobal stability were analised. The methods work especially well in systems with plasticity hysteresis of the classical Mizes model type. Also more general oscillations in nonlinear systems with hysteresis nonlinearities are studied. The results are applicable to the systems with Prandtl, Besseling, Ishlinskii, Mizes, Tresca models of plasticity, Madelung, Presach, Giltay, Mayergoys models of ferro-magnetism and others.

A special attention was paid to methods of analysis of quasi-chaotic behaviour in systems with strong nonlinearities. A new spectral property that is typical for nonlinear dynamical systems exemplifying the chaotic behaviouris considered and studied in detail. A new definition of chaotic behaviour was given that captures key fetures of symbolic dynamics and is applicable to the systems with the Besseling-Ishlinskii and Giltay models of hysteresis. We give new variants of the classical shadowing lemma which work in analysis of non-smooth systems. By the Shadowing Lemma we can shadow any sufficient accurate pseudo-trajectory of a hyperbolic system by a true trajectory of a hyperbolic system. If we are interested in finite trajectories, at least from one side, then a pseudo trajectory usually has many possible shadows. Here we show that we can choose a continuous single-valued selector from the corresponding multi-valued operator "pseudo-trajectory - the totality of possible shadows". We do this in the context of Lipschitz mappings which are semi-hyperbolic on some compact subset, which need not be invariant. We also prove that semi-hyperbolicity implies inverse shadowing with respect to a very broad class of nonsmooth perturbations.

As a test field for some general methods mentioned above we chose the problem of detailed analysis of a class of analog dynamic memory systems. ADDAMS System Inc. (1990-1993) suggested a memory system using a simple feedback loop circuit for an analog signal. The circuit has a time-delay function with no gain, but perturbation order induction which is generally derived from hardware devices in the system (light fibers and charged coupled devices). If the perturbations and noises can be neglected, then this circuit is capable of permanently storing a signal, whose time length is shorter than the time-delay function in this loop. We proceed with the analysis of the signal stability in such system.

Certain dynamical systems with a scalar random parameter were considered. A class of situations in which a decrease in the standard deviation of this random parameter results in a decrease in the mathematical expectation of the trajectory of the dynamical system is described. This research was stimulated by an example in food production and is likely to have wider applicability in the content of industrial quality control.