Let [n,k,d]q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper, seventeen new codes are constructed, which improve the known lower bounds on minimum distance.

We consider a single-line queueing system (QS) with Poisson input flow of varying intensity, which depends on the number of demands in the system. The job size (length) distribution for a demand depends on the number of demands in the system at the arrival moment. The service rate also depends on the number of calls in the QS. If the job size for a new arrival is larger than the remaining job size for the currently processed demand, then the arrival is put at the beginning of the queue with a certain probability, which depends on the total number of demands in the system. Otherwise, it occupies the server and displaces the currently processed demand, which is put at the beginning of the queue. The probability distribution of stationary states of the QS is found and necessary and sufficient conditions for this distribution to be invariant with respect to the job size distribution with a fixed mean are obtained.

A density estimation problem under relative entropy loss criterion is considered. When the densities estimated constitute a d-dimensional smooth parameter family, an exact asymptotics of the minimax risk is established.

The error-correcting capability of tailbiting codes generated by convolutional encoders is described. In order to obtain a description beyond what the minimum distance dmin of the tailbiting code implies, the active tailbiting segment distance is introduced. The description of correctable error patterns via active distances leads to an upper bound on the decoding block error probability of tailbiting codes. The necessary length of a tailbiting code so that its minimum distance is equal to the free distance dfree of the convolutional code encoded by the same encoder is easily obtained from the active tailbiting segment distance. This is useful when designing and analyzing concatenated convolutional codes with component codes that are terminated using the tailbiting method. Lower bounds on the active tailbiting segment distance and an upper bound on the ratio between the tailbiting length and memory of the convolutional generator matrix such that dmin equals dfree are derived. Furthermore, affine lower bounds on the active tailbiting segment distance suggest that good tailbiting codes are generated by convolutional encoders with large active-distance slopes.

Let E be a denumerable state space and X be a homogeneous Markov chain on E with kernel P. Then the chain X verifies a weak Sanov's theorem, i.e., a weak large deviation principle holds for the law of the pair empirical measure. This LDP holds for any discrete state space Markov chain, not necessarily ergodic or irreducible. It is also known that a strong LDP cannot hold in the present framework. The result is obtained by a new method, which allows us to extend the LDP from a finite state space setting to a denumerable one, somehow like the projective limit approach. The analysis presented here offers some by-products, among which there are a contraction principle for the weak LDP, leading directly to a weak Sanov's theorem for the one-dimensional empirical measure. A refined analysis of the ubiquitous entropy function H proves to be useful in other frameworks, e.g., continuous time or stochastic networks, and allows us to improve the sharpness of asymptotics.

Constructions of conflict-avoiding codes are presented. These codes can be used as protocol sequences for successful packet transmission over a collision channel without feedback. We give a relation between codes that avoid conflicts of different numbers of colliding users. Upper bounds on the maximum code size and three particular code constructions are presented.

Partitions {(k1, , k)} of a given set are considered as a partially ordered set (poset) with a natural partial ordering with respect to inclusion. Asymptotics for the size of the largest antichain in this poset is found for fixed.

New families of unimodular sequences of length p = 3f + 1 with zero autocorrelation are described, p being a prime. The construction is based on employing Gauss periods. It is shown that in this case elements of the sequences are algebraic numbers defined by irreducible polynomials over \mathbb{Z} of degree 12 (for the first family) and 6 (for the second family). In turn, these polynomials are factorized in some extension of the field \mathbb{Q} into polynomials of degree, respectively, 4 and 2, which are written explicitly. For p = 13, using the exhaustive search method, full classification of unimodular sequences with zero autocorrelation is given.

We suggest a method for computing the number of dklr-sequences with given number of ones. Based on these results and the well-known method of Babkin and Cover, enumerative encoding and decoding for constant-weight dklr-sequences is obtained.

We enumerate binary extended nonlinear perfect codes of length 16 obtained by the generalized concatenated construction (GC-construction). There are 15 different types of such codes. They are defined by pairs of MDS codes Ai: (4, 2, 64)4. For every pair, we give the number of nonequivalent codes of this type. In total, there are 285 nonequivalent binary extended nonlinear perfect codes of length 16 obtained by the GC-construction, including the Hamming (i.e., linear) code. Thus, we obtain all binary extended perfect codes of length 16 and rank 13. Their total number is equal to 272.

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.

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 = 2m, the number of elements in it being close to the maximum possible. The latter result is one of the main results of the paper.

We present two new algorithms for decoding an arbitrary (n, k) linear rank distance code over GF(qN). These algorithms correct errors of rank r in O((Nr)3q(r-1)(k+1)) and O((k + r)3r3q(r-1)(N-r)) operations in 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.

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.

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.

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.

A new class of models of queueing networks with load-balanced dynamic routing is considered. We propose a sufficient condition for positive recurrence of the arising Markov process and a limiting mean-field approximation where the process becomes deterministic and is described by a system of nonlinear ordinary differential equations.

Using the local method, we prove the large deviation principle for one model distribution, derive an explicit expression for the rate function, and outline ways to further apply the method presented.

The asymptotic behavior of the -entropy of ellipsoids in an n-dimensional Hamming space whose coefficients take only two different values is investigated as n . Explicit expressions for the main terms of the asymptotic expansion of -entropy of such ellipsoids are obtained under various relations between and parameters that define these ellipsoids.