PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Signaling to Relativistic Observers: An Einstein–Shannon–Riemann Encounter
M. Kovačević
pp. 303–308

Abstract—A communication scenario is described involving a series of events triggered by a transmitter and observed by a receiver experiencing relativistic time dilation. The message selected by the transmitter is assumed to be encoded in the events' timings and is required to be perfectly recovered by the receiver, regardless of the difference in clock rates in the two frames of reference. It is shown that the largest proportion of the space of all $k$-event signals that can be selected as a code ensuring error-free information transfer in this setting equals $\zeta(k)^{-1}$, where $\zeta$ is the Riemann zeta function.

On Bases of BCH Codes with Designed Distance 3 and Their Extensions
I. Yu. Mogilnykh and F. I. Solov'eva
pp. 309–316

Abstract—We consider narrow-sense BCH codes of length $p^m-1$ over $\mathbb{F}_p$, $m\ge 3$. We prove that neither such a code with designed distance $\delta=3$ nor its extension for $p\ge 5$ is generated by the set of its codewords of the minimum nonzero weight. We establish that extended BCH codes with designed distance $\delta=3$ for $p\ge 3$ are generated by the set of codewords of weight 5, where basis vectors can be chosen from affine orbits of some codewords.

Detecting Cycles of Length 10 in the Tanner Graph of a QC-LDPC Code Based on Protograph Analysis
A. V. Kharin, K. N. Zavertkin, and A. A. Ovinnikov
pp. 317–331

Abstract—We complete the description of the procedure of topological expansion of a bipartite graph without parallel branches on the plane of changing the structure of cycles of length up to 10 inclusive. Based on previous papers, we have extended a set of theorems specifying transformation rules for cycles and paths when passing from a protograph to the Tanner graph. We propose a procedure for detecting the existence of a cycle of length 10 in the expanded graph by analyzing the protograph.

A Sufficient Condition for the Existence of Restricted Fractional $(g,f)$-Factors in Graphs
S. Zhou, Z. Sun, and Q. Pan
pp. 332–344

Abstract—In an NFV network, the availability of resource scheduling can be transformed to the existence of the fractional factor in the corresponding NFV network graph. Researching on the existence of special fractional factors in network structure can help to construct the NFV network with efficient application of resources. Let $h\colon E(G)\to[0,1]$ be a function. We write $d_G^{h}(x)=\sum\limits_{e\ni x}h(e)$. We call a graph $F_h$ with vertex set $V(G)$ and edge set $E_h$ a fractional $(g,f)$-factor of $G$ with indicator function $h$ if $g(x)\le d_G^{h}(x)\le f(x)$ holds for any $x\in V(G)$, where $E_h=\{e:\: e\in E(G),\: h(e)>0\}$. We say that $G$ has property $E(m,n)$ with respect to a fractional $(g,f)$-factor if for any two sets of independent edges $M$ and $N$ with $|M|=m$, $|N|=n$, and $M\cap N=\emptyset$, $G$ admits a fractional $(g,f)$-factor $F_h$ with $h(e)=1$ for any $e\in M$ and $h(e)=0$ for any $e\in N$. The concept of property $E(m,n)$ with respect to a fractional $(g,f)$-factor corresponds to the structure of an NFV network where certain channels are occupied or damaged in some period of time. In this paper, we consider the resource scheduling problem in NFV networks using graph theory, and show a neighborhood union condition for a graph to have property $E(1,n)$ with respect to a fractional $(g,f)$-factor. Furthermore, it is shown that the lower bound on the neighborhood union condition in the main result is the best possible in some sense.

On Stability of the Independence Number of a Certain Distance Graph
P. A. Ogarok and A. M. Raigorodskii
pp. 345–357

Abstract—We study the asymptotic behavior of the independence number of a random subgraph of a certain $(r,s)$-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.

Peculiar Properties of the $p$-Linear Decomposition of $p$-Linear Functions in Terms of the Shift-Composition Operation
I. V. Cherednik
pp. 358–372

Abstract—We analyze the shift-composition operation on discrete functions which occurs under homomorphisms of finite shift registers. We prove that for a prime $p$, in the class of all functions that are linear in the extreme variables, the notions of reducibility and $p$-linear reducibility coincide for $p$-linear functions. Furthermore, we show that a linear function irreducible in the class of all linear functions has no $p$-linear divisors that are bijective in the rightmost variable, and in some cases, has no $p$-linear divisors at all.

Polynomial Asymptotically Optimal Coding of Underdetermined Bernoulli Sources of the General Form
L. A. Sholomov
pp. 373–387

Abstract—An underdetermined Bernoulli source generates symbols of a given underdetermined alphabet independently with some probabilities. To each underdetermined symbol there corresponds a set of basic (fully defined) symbols such that it can be substituted (specified) by any of them. An underdetermined source is characterized by its entropy, which is implicitly introduced as a minimum of a certain function and plays a role similar to the Shannon entropy for fully defined sources. Coding of an underdetermined source must ensure, for any sequence generated by the source, recovering some its specification. Coding is asymptotically optimal if the average code length is asymptotically equal to the source entropy. Coding is universal if it does not depend on the probabilities of source symbols. We describe an asymptotically optimal universal coding method for underdetermined Bernoulli sources for which the encoding and decoding procedures can be realized by RAM-programs of almost linear complexity.

Existence and Construction of Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise
E. E. Egorova, M. Fernandez, G. A. Kabatiansky, and Y. Miao
pp. 388–398

Abstract—It was shown very recently in [1] that there are no multimedia digital fingerprinting codes capable of fully recovering a coalition of malicious users under the general linear attack and adversarial noise. We show that such codes exist if the class of attacks is narrowed to the averaging attack. The arising mathematical problem is close to the problem of constructing signature codes for a noisy binary adder channel.

Retraction Note: Note on “Smaller Explicit Superconcentrators” by N. Alon and M. Capalbo
L. A. Bassalygo
p. 399

Abstract—The author has retracted this article [1], since a critical error was found in the proof of the main result after its publication, thus making it invalid.