PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Distance Approach to Window Decoding
M. Handlery, R. Johannesson, and V. V. Zyablov
pp. 169–181

Abstract—In convolutional coding, code sequences have infinite length; thus, a maximum-likelihood decoder implies an infinite delay. Due to memory and delay constraints in practical coding schemes, convolutional codes often are either terminated or decoded by a window decoder. When a window decoder is used, the convolutional code sequence is not terminated; instead, the window decoder estimates information digits after receiving a finite number of noise-corrupted code symbols, thereby keeping the decoding delay short. An exact characterization of the error-correcting capability of window decoded convolutional codes is given by using active distances of convolutional codes.

A Posteriory Probability Decoding of Nonsystematically Encoded Block Codes
H. Griesser and V. R. Sidorenko
pp. 182–193

Abstract—We consider the problem of symbol-by-symbol a posteriori probability (APP) decoding for information symbols of nonsystematically encoded block codes. This problem arises at soft concatenated decoding of generalized concatenated block codes. The well-known BCJR algorithm for efficient APP decoding is not able to solve the problem if it runs on the minimal code trellis of a block code. We introduce an extended trellis representation for block codes, which includes encoding information and thus makes it possible to apply the BCJR algorithm as well as trellis-based decoding in the dual code space. Complexity properties of the extended trellis are investigated.

Quantum Codes and Abelian Subgroups of the Extra-Special Group
V. M. Sidelnikov
pp. 194–202

Abstract—A method for constructing a new class of quantum codes is proposed. In the method, properties of the extra-special matrix group are exploited. This class of codes is wider than that considered in [1–4] (CSS-codes). In particular, this class includes the one-error-correcting quantum “Hamming code” (which is not a CSS-code) of length $n=2^m$, the number of elements in it being close to the maximum possible. The latter result is one of the main results of the paper.

Adaptive Detection of a Stochastic Signal under Parametric a priori Uncertainty
A. P. Trifonov, A. V. Zakharov, and E. V. Pronyaev
pp. 203–217

Abstract—We obtain a maximum likelihood algorithm for detecting a Gaussian stochastic signal with unknown appearance (disappearance) time and average power. Asymptotic expressions for the probabilities of the 1st- and 2nd-kind detection errors are found. Applicability limits for the derived expressions are found by statistical computer simulation.

Solving Automaton Equations with Distortions in the Automaton Transition Function
A. V. Babash
pp. 218–226

Abstract—Probabilities of correct determination of an initial state of an automaton under a random distortion of its transition function are estimated.

Multiplicativity of Markov Chains with Multiaddress Routing
M. Yu. Tyurikov
pp. 227–236

Abstract—A broad class of network Markov processes (including open queueing networks) with multiaddress routing and one type of calls is considered. Under such routing, the same call can simultaneously arrive at several nodes. For these processes, we found necessary and sufficient conditions of multiplicativity, that is, conditions of representability of a stationary distribution as a product of factors characterizing separate nodes.

New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications
A. V. Ourivski and T. Johansson
pp. 237–246

Abstract—We present two new algorithms for decoding an arbitrary $(n,k)$ linear rank distance code over $\operatorname{\it GF}(q^N)$. These algorithms correct errors of rank $r$ in $O\left((Nr)^3q^{(r-1)(k+1)}\right)$ and $O\left((k+r)^3r^3q^{(r-1)(N-r)}\right)$ operations in $\operatorname{\it GF}(q)$ respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.

On the 100th Anniversary since the Birth of Andrei Nikolaevich Kolmogorov
pp. 247–248