PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Reliable Communication under the Influence of a State-Constrained Jammer: An Information-Theoretic Perspective on Receive Diversity
C. Arendt, J. Nötzel, and H. Boche
pp. 101–123

Abstract—The impact of diversity on reliable communication over arbitrarily varying channels (AVC) is investigated as follows. First, the concept of an identical state-constrained jammer is motivated. Second, it is proved that symmetrizability of binary symmetric AVCs (AVBSC) caused by identical state-constrained jamming is circumvented when communication takes place over at least three orthogonal channels. Third, it is proved that the deterministic capacity of the identical state-constrained AVBSC is continuous and shows super-activation. This effect was hitherto demonstrated only for quantum communication and for classical communication under secrecy constraints.

Non-split Toric Codes
D. I. Koshelev
pp. 124–144

Abstract—We introduce a new wide class of error-correcting codes, called non-split toric codes. These codes are a natural generalization of toric codes where non-split algebraic tori are taken instead of usual (i.e., split) ones. The main advantage of the new codes is their cyclicity; hence, they can possibly be decoded quite fast. Many classical codes, such as (doubly-extended) Reed–Solomon and (projective) Reed–Muller codes, are contained (up to equivalence) in the new class. Our codes are explicitly described in terms of algebraic and toric geometries over finite fields; therefore, they can easily be constructed in practice. Finally, we obtain new cyclic reversible codes, namely non-split toric codes on the del Pezzo surface of degree 6 and Picard number 1. We also compute their parameters, which prove to attain current lower bounds at least for small finite fields.

On Application of the Modulus Metric to Solving the Minimum Euclidean Distance Decoding Problem
V. A. Davydov
pp. 145–151

Abstract—We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and $Q$-ary output. For such a channel, we give an example of a construction of binary codes correcting $t$ binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with $Q$ quantization errors as $(t+1)(Q-1)-1$ errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.

Geometry of Translations on a Boolean Cube
M. N. Vyalyi and V. K. Leontiev
pp. 152–173

Abstract—The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the two-element field. Subsets of the Boolean cube (or multivariable Boolean functions) form a monoid with respect to this operation. This monoid is of interest in classical discrete analysis as well as in a number of problems related to information theory. We consider several complexity aspects of this monoid, namely structural, algorithmic, and algebraic.

The Geometry of Big Queues
A. A. Puhalskii
pp. 174–200

Abstract—We use Hamilton equations to identify most likely scenarios of long queues being formed in ergodic Jackson networks. Since the associated Hamiltonians are discontinuous and piecewise Lipschitz, one has to invoke methods of nonsmooth analysis. Time reversal of the Hamilton equations yields fluid equations for the dual network. Accordingly, the optimal trajectories are time reversals of the fluid trajectories of the dual network. Those trajectories are shown to belong to domains that satisfy a certain condition of being “essential.” As an illustration, we consider a two-station Jackson network. In addition, we prove certain properties of substochastic matrices, which may be of interest in their own right.