PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 7, Number 3, July–September, 1971
Back to contents page

CONTENTS                   Powered by MathJax

 

Probabilistic Decoding of Majority Codes
V. D. Kolesnik
pp. 193–200

Abstract—The transmission of binary messages over a memoryless channel with a continuous output is considered. For binary codes which allow majority decoding a decision scheme is used which is optimal with respect to the maximum a posteriori probability and uses the a posteriori error probabilities of the received symbols. These probabilities give different weights to the checks, which allows optimal reception as a whole to be approached. A modification of the optimal algorithm which has a simpler realization is likewise described. It is shown that for weak Gaussian noise the use of probabilistic decoding is equivalent to increasing the number of checks for symbol-wise reception by approximately a factor of two.

 

List Decoding in a Gaussian Discrete Memoryless Channel
A. Yu. Sheverdyaev
pp. 201–210

Abstract—Estimates are presented of the probability of list decoding in a Gaussian discrete memory-less channel.

 

Asymptotic Bounds for Probability of Error for Transmission at Zero Velocity in a Gaussian Channel with Full Feedback
A. G. D'yachkov
pp. 211–214

Abstract—The first few terms in the asymptotic expansion of the optimal probability of error for a block transmission exp{τα}  (τ is the block length, and 0 < α < 1) are found. The probability is for equiprobable calls in a stationary, discrete, Gaussian channel, without memory, but with full feedback.

 

One Method of Constructing Quasilinear Codes Providing Synchronization in the Presence of Errors
V. I. Levenshtein
pp. 215–222

Abstract—A method is proposed for the construction of a family of codes of length $n$, these being the cosets of linear codes, providing synchronization in the presence of no more than $t$ errors in $n$ successive symbols. Upper and lower bounds are obtained for the minimal redundancy of the codes of this family. From the bounds obtained follows the asymptotic expression for minimal redundancy under the condition that $t/n\to 0$.

 

A Rational Representation of Codes and $(L,g)$-Codes
V. D. Goppa
pp. 223–229

Abstract—A method of construction of error-correcting codes is described as well as a class of linear $q$-ary codes.

 

A Contribution to the Theory of Multipositional Information Transmission Systems with Compound Signals
N. B. Rezvetsov and I. D. Zaderenko
pp. 230–234

Abstract—The noise immunity of digital information transmission systems with compound signals based on a set of orthonormalized functions is discussed. These systems are compared with the best known communication systems as to the specific amount of energy and frequency bandwidth expended for the transmission of one binary unit of information.

 

Markov Processes with Many Locally Interacting Components — the Reversible Case and Some Generalizations
R. L. Dobrushin
pp. 235–241

Abstract—We continue the investigation of the class of Markov processes introduced in [R.L. Dobrushin, Probl. Peredachi Inf., 1971, vol. 7, no. 2, pp. 70–87]. It is shown that a time reversible stationary process has the Gibbs distribution as its stationary distribution. The possibility of extending the class of processes introduced in the paper cited is mentioned.

 

Conditions for Strong Statistical Equilibrium of Complex Mass Servicing Systems
G. P. Basharin and V. A. Kokotushkin
pp. 242–248

Abstract—The class of single-phase mass servicing systems (MSS) of any structure (single-element, multi-element, etc.) is considered with an arbitrary control algorithm; within this class a subclass is studied for which the final probabilities of states are independent of the form of the distribution function of the servicing time if the first moments are equal. It is shown that for the above the Kovalenko condition established by him for a special kind of MSS is a necessary and sufficient condition (a strong statistical equilibrium). It is also shown that the fulfillment of these conditions does not ensure the independence of the second moment of the lost load of the form of the distribution function of the servicing times.

 

Service Systems with a Hyper-Erlang Source, Exponential Servicing Law, and a Bounded Expectation Space
N. I. Mal'tseva
pp. 249–256

Abstract—The article considers a service system $HE_k|M|c\geq1|r<\infty|d_1$. Obtained are recurrent relations for determining the probability distribution and the characteristics of the system in the steady-state regime.

 

Control of the Conclusion in Formal Grammars
E. D. Stotskii
pp. 257–270

Abstract—This article considers formal generating grammars having different types of control of the conclusion. A classification is made for such grammars and the classes of languages corresponding to them. Special attention is given to classes rigorously intermediate between the class of contextless languages and the class of contextual languages.

 

“Mutual Assistance” in an Aggregate of Radio Stations
V. L. Stefanyuk
pp. 271–274

Abstract—A model of an aggregate of radio stations is considered in which part of the power of each transmitter goes for relaying the signals of the “foreign” transmitters. The necessary and sufficient conditions are written out and the simple necessary conditions obtained to justify such relaying.

 

A Code Ensemble with a Low Density of Ones in the Parity Check Matrix
M. V. Kozlov
pp. 275–277

Abstract—For a code ensemble whose parity check matrices have approximately $\ln n$ in each row we study the minimal code distance and the average ensemble probability of erroneous decoding.

 

A Sorting Problem
A. V. Vasil'ev
pp. 278–280

Abstract—The following problem is considered: each cell of an integer-valued torus contains a particle that belongs to one of two types. At each step one selects at random a pair of neighboring particles of different type which are then exchanged with a probability that depends on the choice of the particles that are neighbors of the pair. The necessary and sufficient conditions are obtained for the existence of a final Gibbs measure on an arbitrary torus with an arbitrary number of particles.