PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

Volume 39, Number 3, July–September, 2003
Back to contents page

CONTENTS

A Method for Fast Computation of the Fourier Transform over a Finite Field
P. V. Trifonov and S. V. Fedorenko
pp. 231–238

Abstract—We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given.

On the Performance of Permutation Codes for Multi-User Communication
V. B. Balakirsky and H. Vinck
pp. 239–254

Abstract—Permutation coding for multi-user communication schemes that originate from the Fast Frequency Hopping/Multiple Frequency Shift Keying modulation is investigated. Each sender is either passive or sends some signal formed as the concatenation of $M$ elementary signals having $M$ different specified frequencies. There is also a jammer, who can introduce disturbances. A single disturbance is either sending the signal that contains all $M$ frequencies at a certain time instant or sending some elementary signal at all time instants. Each receiver receives a vector of $M$ sets, where a set at each time instant contains a fixed frequency if and only if the corresponding elementary signal was sent by either some sender or the jammer. The task of the receiver is to uniquely decode the message of his sender. We present regular constructions of permutation codes for this scheme given the following parameters: the number of frequencies, number of pairs (sender, receiver), number of messages per sender, and maximum number of disturbances of the jammer.

Extended Binomial Moments of a Linear Code and the Undetected Error Probability
R. Dodunekova
pp. 255–265

Abstract—Extended binomial moments of a linear code, introduced in this paper, are synonymously related to the code weight distribution and linearly to its binomial moments. In contrast to the latter, the extended binomial moments are monotone, which makes them appropriate for studying the undetected error probability. We establish some properties of the extended binomial moments and, based on this, derive new lower and upper bounds on the probability of undetected error. Also, we give a simplification of some previously obtained sufficient conditions for proper and good codes, stated in terms of the extended binomial moments.

Stochastic Dynamic Games with Various Types of Information
P. V. Golubtsov and V. A. Lyubetsky
pp. 266–293

Abstract—Dynamic discrete-time games are generalized to a stochastic environment, in order to examine the influence of various types of information structures on the course of a game. It is shown that the information structure of a game, i.e., type and amount of information available to players and, in particular, asymmetry of information, may lead to unexpected and sometimes counter-intuitive effects on the game result, i.e., the players' payoffs. The paper also develops algorithms for obtaining the Nash equilibrium strategies in such games. These involve reducing optimal reaction policies to the corresponding dynamic programming algorithms and generalizing the classical optimal control technique. Results of computer simulations for a variant of fishery harvesting game are presented.

Note on a Computer-Oriented Language
V. P. Maslov
pp. 294–298

Abstract—In this paper, we consider a Russian–Chinese pidgin, a steady simplified language, whose properties can be modeled in creating a computer-oriented language. Word combinations united into descriptors of the pidgin, which corresponds to adapted Russian, obey the Bose–Einstein statistics. Assuming that, under certain conditions, the steady pidgin gives the maximum of the specified information, we formulate a hypothesis about compression of descriptors for a computer-oriented language.

Analysis of Asymptotic Average Characteristics for Non-Markovian Models of Unstable Random Access Networks
P. I. Kotsyuruba and A. A. Nazarov
pp. 299–308

Abstract—A mathematical non-Markovian model of a random access communication network is investigated asymptotically under the condition of a large delay. An ordinary differential equation is obtained, which determines the average number of calls in the source of repeat calls. Various expressions for it are found in the form of implicit functions, depending on relations between network parameters.

The Gated Infinite-Server Queue with Unbounded Service Times and Heavy Traffic
A. V. Lebedev
pp. 309–316

Abstract—A queueing system with infinitely many servers is considered where access of customers to service is controlled by a gate. The gate is open only if all servers are free. Customers are served in stages. We study the asymptotic behavior of the number of customers served in a stage and of the stage duration in the heavy traffic regime in the case where the service time distribution belongs to the attraction domain of a double exponential law.