PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

Volume 40, Number 3, July–September, 2004
Back to contents page

CONTENTS

Detecting and Correcting Capabilities of Convolutional Codes
V. V. Zyablov, R. Johannesson, and V. A. Pavlushkov
pp. 187–194

Abstract—A convolutional code can be used to detect or correct infinite sequences of errors or to correct infinite sequences of erasures. First, erasure correction is shown to be related to error detection, as well as error detection to error correction. Next, the active burst distance is exploited, and various bounds on erasure correction, error detection, and error correction are obtained for convolutional codes. These bounds are illustrated by examples.

On the Optimality of Trivial $(w,r)$-Cover-Free Codes
H. K. Kim and V. S. Lebedev
pp. 195–201

Abstract—A $(w,r)$-cover-free code is the incidence matrix of a family of sets where no intersection of $w$ members of the family is covered by the union of $r$ others. We obtain a new condition in view of which $(w,r)$-cover-free codes with a simple structure are optimal. We also introduce $(w,r)$-cover-free codes with a constraint set.

On a Method of Empirical Risk Minimization
G. K. Golubev
pp. 202–211

Abstract—We consider the problem of estimating an unknown vector observed in a simple white Gaussian noise model. For the estimation, a family of projection estimators is used; the problem is to choose, based on observations, the best estimator within this family. The paper studies a method for choosing a projection estimator, based on the principle of penalized empirical risk minimization. For this estimation method, nonasymptotic inequalities controlling its quadratic risk are given.

Point Asymptotics for Probabilities of Large Deviations of the $\omega^2$ Statistics in Verification of the Symmetry Hypothesis
V. R. Fatalov
pp. 212–225

Abstract—We consider the $\omega^2$ statistic, destined for testing the symmetry hypothesis, which has the form $$\omega_n^2=n \int\limits_{-\infty}^\infty [F_n(x)+F_n(-x)-1]^2\,dF_n(x),$$ where $F_n(x)$ is the empirical distribution function. Based on the Laplace method for empirical measures, exact asymptotic (as $n\to\infty$) of the probability $$\Pr \{\omega_n^2\gt n v\}$$ for $0\lt v\lt 1/3$ is found. Constants entering the formula for the exact asymptotic are computed by solving the extreme value problem for the rate function and analyzing the spectrum of the second-order differential equation of the Sturm–Liouville type.

Wavelets and Estimation of Discontinuous Functions
L. L. Boiko
pp. 226–236

Abstract—The paper considers the problem of estimating a signal with finitely many points of discontinuity from observations against white Gaussian noise. It is shown that, with an appropriate choice of a generator polynomial, an estimation method based on wavelets yields asymptotically minimax (up to a constant) estimates for functions sufficiently smooth outside the discontinuity points.

Gated Infinite-Server Queue with Heavy Traffic and Power Tail
A. V. Lebedev
pp. 237–242

Abstract—An infinite-server queueing system is considered where access of customers to service is controlled by a gate. The gate is open only if all servers are free. Otherwise, customers are put on a queue. Asymptotic behavior of the system in heavy traffic is studied under the assumption that the service time distribution has a power tail.

Analysis of a Communication Network Governed by an Adaptive Random Multiple Access Protocol in Critical Load
D. Yu. Kuznetsov and A. A. Nazarov
pp. 243–253

Abstract—A mathematical model of an adaptive random multiple access communication network is investigated. The value of the network critical load is found; in the critical load, asymptotic probability distributions for states of the information transmission channel and for the number of requests in the source of repeated calls are found. It is proved that distributions of the normalized number of requests belong to the class of normal and exponential distributions, and it is shown how conditional normal distributions pass in the limit to the class of exponential ones.

Image Restoration in Optical-Acoustic Tomography
D. A. Popov and D. V. Sushko
pp. 254–278

Abstract—We consider the optical-acoustic tomography problem. In the general case, the problem is to reconstruct a real-valued function with a compact support in the $n$-dimensional Euclidean space via its spherical integrals, i.e., integrals over all $(n-1)$-dimensional spheres centered at points on some $(n-1)$-dimensional hypersurface. We deal with the cases $n=2$ and $n=3$, which are of the most practical interest from the standpoint of possible medical applications. We suggest a new effective method of reconstruction, develop restoration algorithms, and investigate the quality of the algorithms for these cases. The main result of the paper is construction of explicit approximate reconstruction formulas; from the mathematical standpoint, these formulas give the parametrix for the optical-acoustic tomography problem. The formulas constructed is a background for the restoration algorithms. We performed mathematical experiments to investigate the quality of the restoration algorithms using the generally accepted tomography quality criteria. The results obtain lead to the general conclusion: the quality of the restoration algorithms developed for optical-acoustic tomography is only slightly lower then the quality of the convolution and back projection algorithm used in Radon tomography, which is a standard de facto.

Gibbs Field Approaches in Image Processing Problems
X. Descombes and E. A. Zhizhina
pp. 279–295

Abstract—In this paper, we address the problem of image denoising using a stochastic differential equation approach. Proposed stochastic dynamics schemes are based on the property of diffusion dynamics to converge to a distribution on global minima of the energy function of the model, under a special cooling schedule (the annealing procedure). To derive algorithms for computer simulations, we consider discrete-time approximations of the stochastic differential equation. We study convergence of the corresponding Markov chains to the diffusion process. We give conditions for the ergodicity of the Euler approximation scheme. In the conclusion, we compare results of computer simulations using the diffusion dynamics algorithms and the standard Metropolis–Hasting algorithm. Results are shown on synthetic and real data.