PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 47, Number 4, October–December, 2011
Back to contents page

CONTENTS                   Powered by MathJax

 

Codes for MIMO Transmission Based on Orthogonal Sequences
A. A. Kreshchuk, A. A. Davydov, and V. V. Zyablov
pp. 305–326

Abstract—We consider MIMO communication systems with Rayleigh fading. We propose a new coded modulation based on orthogonal sequences and state a new decodability condition. We introduce concepts and constructions of permutation free (PF) and permutation and repetition free (PRF) codes. We also propose a construction of PRF codes with sign manipulation, whose code rate can exceed 1. For better analysis and construction of these codes we introduce a one-to-one mapping that transforms signal matrices to vectors over a finite field. We propose construction algorithms for PF and PRF codes. We build PF and PRF codes with large cardinality, which in several case achieve the maximum cardinality. Simulation of the constructed codes and estimation of their performance was done in Simulink environment. Results show high error-correcting capability, which often reaches that of STBC codes with full transmit diversity.

 

Bounds on the Minimum Code Distance for Nonbinary Codes Based on Bipartite Graphs
A. A. Frolov and V. V. Zyablov
pp. 327–341

Abstract—The minimum distance of codes on bipartite graphs (BG codes) over $\operatorname{\it GF}(q)$ is studied. A new upper bound on the minimum distance of BG codes is derived. The bound is shown to lie below the Gilbert–Varshamov bound when $q \ge 32$. Since the codes based on bipartite expander graphs (BEG codes) are a special case of BG codes and the resulting bound is valid for any BG code, it is also valid for BEG codes. Thus, nonbinary ($q \ge 32$) BG codes are worse than the best known linear codes. This is the key result of the work. We also obtain a lower bound on the minimum distance of BG codes with a Reed–Solomon constituent code and a lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed–Solomon constituent code. The bound for LDPC codes is very close to the Gilbert–Varshamov bound and lies above the upper bound for BG codes.

 

On Regular Realizability Problems
M. N. Vyalyi
pp. 342–352

Abstract—We consider the class of regular realizability problems. Any of such problems is specified by some language (filter) and consists in verifying that the intersection of a given regular language and the filter is nonempty. The main question is diversity of the computational complexity of such problems. We show that any regular realizability problem with an infinite filter is hard for a class of problems decidable in logarithmic space with respect to logarithmic reductions. We give examples of NP-complete and PSPACE-complete regular realizability problems.

 

Properties of a Folded Category Constructed from a Category and a Lattice
A. V. Zhozhikashvili and V. L. Stefanuk
pp. 353–363

Abstract—Previously, employing the apparatus of category theory for abstract description of knowledge in production-type systems was shown to be reasonable. Interest towards applying the obtained techniques to so-called dynamic expert systems, which allow for variation of data and knowledge in the course of system functioning, required a certain generalization of previously developed category theory apparatus related to consideration of so-called folded categories. The paper is devoted to the study of some properties of such categories.

 

Call Center Operation Model as a $MAP/PH/N/R-N$ System with Impatient Customers
S. A. Dudin and O. S. Dudina
pp. 364–377

Abstract—We analyze a multiserver queueing system with a finite buffer and impatient customers. The arrival customer flow is assumed to be Markovian. Service times of each server are phase-type distributed. If all servers are busy and a new arrival occurs, it enters the buffer with a probability depending on the total number of customers in the system and waits for service, or leaves the system with the complementary probability. A waiting customer may become impatient and abandon the system. We give an algorithm for finding the stationary distribution of system states and derive formulas for basic performance characteristics. We find Laplace–Stieltjes transforms for sojourn and waiting times. Numeric examples are given.

 

Common Language of All People: The Innate Language of Thought
A. Wierzbicka
pp. 378–397

The International Dobrushin Prize for 2010 was awarded to Anna Wierzbicka. Wierzbicka is affiliated with the Australian National University, Canberra. The prize was presented on July 25, 2011, at the International Mathematical Conference in honor of the 50th anniversary of the Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences.

 

Random Minkowski Theorem
G. A. Margulis
pp. 398–402

The International Dobrushin Prize for 2011 was awarded to Grigorii Aleksandrovich Margulis. Margulis is affiliated with the Kharkevich Institute for Information Transmission Problems, Moscow, and Yale University, New Haven, USA. The prize was presented on July 25, 2011, at the International Mathematical Conference in honor of the 50th anniversary of the Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences.

 

INDEX
pp. 403–406