PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 49, Number 2, April–June, 2013
Back to contents page

CONTENTS                   Powered by MathJax

 

Some Properties of Rényi Entropy over Countably Infinite Alphabets
M. Kovačević, I. Stanojević, and V. Šenk
pp. 99–110

Abstract—We study certain properties of Rényi entropy functionals $H_\alpha(\mathcal{P})$ on the space of probability distributions over $\mathbb{Z}_+$. Primarily, continuity and convergence issues are addressed. Some properties are shown to be parallel to those known in the finite alphabet case, while others illustrate a quite different behavior of the Rényi entropy in the infinite case. In particular, it is shown that for any distribution $\mathcal P$ and any $r\in[0,\infty]$ there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance and such that $\lim\limits_{n\to\infty}\lim\limits_{\alpha\to{1+}} H_\alpha(\mathcal{P}_n)=\lim\limits_{\alpha\to{1+}}\lim\limits_{n\to\infty} H_\alpha(\mathcal{P}_n)+r$.

 

Random Multiple Access in a Vector Disjunctive Channel
E. V. Pustovalov and A. M. Turlikov
pp. 111–126

Abstract—We consider a random multiple access (RMA) procedure in a vector disjunctive channel. We show that exploiting properties of the channel allows one to reduce collision resolution time and thus increase the maximal stable throughput (MST) of RMA algorithms in this channel. We propose an algorithm, belonging to the class of splitting algorithms, which achieves the MST of 0.603.

 

On Interpolation of Smooth Processes and Functions
G. K. Golubev and E. A. Krymova
pp. 127–148

Abstract—We consider interpolation problems for smooth stationary Gaussian processes and functions from Sobolev classes. These problems are shown to be closely related. Much attention is paid to spline-based interpolation methods. In particular, we prove that splines are limiting optimal interpolations of stationary Gaussian processes with special spectral densities. Based on this analogy, we propose a simple method for controlling accuracy of spline interpolation.

 

Determinization of Ordinal Automata
An. A. Muchnik
pp. 149–162

Abstract—It is proved that for each nondeterministic ordinal automaton there exists a deterministic ordinal automaton which is equivalent to the original one for all countable ordinals. An upper bound for the number of states of the deterministic automaton is double exponential in the number of states of the nondeterministic automaton.

 

Finiteness in the Beggar-My-Neighbor Card Game
E. L. Lakshtanov and A. I. Aleksenko
pp. 163–166

Abstract—For card games of the Beggar-My-Neighbor type, we prove finiteness of the mathematical expectation of the game duration under the conditions that a player to play the first card is chosen randomly and that cards in a pile are shuffled before being placed to the deck. The result is also valid for general-type modifications of the game rules. In other words, we show that the graph of the Markov chain for the Beggar-My-Neighbor game is absorbing; i.e., from any vertex there is at least one path leading to the end of the game.

 

Analysis of an Open Non-Markovian $GI-(GI\,|\,\infty)^K$ Queueing Network with High-Rate Renewal Arrival Process
A. A. Nazarov and A. N. Moiseev
pp. 167–178

Abstract—We analyze an open non-Markovian queueing network with high-rate renewal arrival process, Markovian routing, arbitrary service policy, and unlimited number of servers at nodes. We obtain mean values for the number of busy servers at nodes of the queueing network in question. We show that, under an infinitely increasing arrival rate, the multivariate distribution of the number of busy servers at network nodes can be approximated by a multivariate normal distribution; we find parameters of this distribution.

 

Information Security in a Random Network Coding Network
E. M. Gabidulin, N. I. Pilipchuk, B. Honary, and H. Rashwan
pp. 179–191

Abstract—We consider a communication network with random network coding which can be attacked by adversaries of two types. One of them can wiretap original packets outgoing from source to destination. The other can insert its own packets into information flow, which are wrong messages for the receiver. To provide secure communication, we use a scheme based on combining the GPT (Gabidulin–Paramonov–Tretjakov) public key cryptosystem and SKK (Silva–Kschischang–Koetter) codes. Encrypted packets are transmitted to the destination through wired channels. Performance of this system is investigated. The main result is that the proposed scheme is secure against wiretapping and insertion attacks under some conditions which depend on rank code parameters.

 

Remark on “Steiner Triple Systems $S(2^m-1,3,2)$ of Rank $2^m-m+1$ over $\mathbb{F}_2$” Published in Probl. Peredachi Inf., 2012, no. 2
V. A. Zinoviev and D. V. Zinoviev
pp. 192–195

Abstract—In Theorem 4 of our paper “Steiner Triple Systems $S(2^m-1,3,2)$ of Rank $2^m-m+1$ over $\mathbb{F}_2$” (Probl. Peredachi Inf., 2012, vol. 48, no. 2, pp. 102–126) we have made a mistake. Theorem 4 should read as follows:
The total number of different Steiner triple systems $S(v,3,2)$ of order $v=2^m-1=4u+3$ and rank $v-m+2$ is exactly $$ M^{\rm(o)}_v= \frac{v!\,M_{v,2}} {(u(u-1)(u-2) \ldots (u+1)/2) \cdot (4!)^u \cdot 3!}, $$ where $M_{v,2}$ denotes the number of different Steiner triple systems $S(v,3,2)$ of order $v$ and rank $v-m+2$ orthogonal to the code $\mathcal{A}_m$, which is $$ M_{v,2}=6^{u} \left(\bigl(2^6\cdot 3^2\bigr)^{u(u-1)/6}-2^{u-m+2}\cdot 3 \bigl(16^{u(u-1)/6}-2^{u-m+2}\bigr)-2^{2(u-m+2)}\right). $$