IEEE Transactions on Information Theory

We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n, p) of tests for the Bernoulli p-scheme, where ...

In a hidden Markov model (HMM) the underlying finite-state Markov chain cannot be observed directly but only by an additional process. We are interested in estimating the unknown path of the Markov chain. The most widely used estimator is the maximum a ...

The Viterbi algorithm (1967) and conventional serial concatenated codes (CSCC) have been widely applied in digital communication systems over the last 30 years. We show that the Shannon capacity of additive white Gaussian noise (AWGN) channels can be ...

We present a framework for iterative multiuser joint decoding of code-division multiple-access (CDMA) signals, based on the factor-graph representation and on the sum-product algorithm. In this framework, known parallel and serial, hard and soft ...

We study the asymptotic behavior of space-time codes when the number of transmit and receive antennas grows to infinity. Specifically, we determine the behavior of pairwise error probabilities with maximum-likelihood (ML) decoding and with three types ...

Multiple-antenna systems that operate at high rates require simple yet effective space-time transmission schemes to handle the large traffic volume in real time. At rates of tens of bits per second per hertz, Vertical Bell Labs Layered Space-Time (V-...

One well-known method of generating key stream sequences for stream ciphers is to combine the outputs of several linear-feedback shift registers (LFSR) using a combining Boolean function. Here we concentrate on the design of good combining Boolean ...

A recursive linear detection algorithm is proposed for the detection of signals from an asynchronous direct-sequence code-division multiple-access (DS-CDMA) communication system. This algorithm works for short as well as long codes. Under some ...

In blind (or group-blind) linear multiuser detection, the detector is estimated from the received signals, with the prior knowledge of only the signature waveform of the desired user (or the signature waveforms of some but not all users). The ...

For the least mean square (LMS) algorithm, we analyze the correlation matrix of the filter coefficient estimation error and the signal estimation error in the transient phase as well as in steady state. We establish the convergence of the second-order ...

This paper provides a mathematical analysis of transform compression in its relationship to linear and nonlinear approximation theory. Contrasting linear and nonlinear approximation spaces, we show that there are interesting classes of functions/random ...

This paper considers the problem of blind symbol rate estimation of signals linearly modulated by a sequence of unknown symbols. Oversampling the received signal generates cyclostationary statistics that are exploited to devise symbol-rate estimators by ...

This paper presents a unified approach to the problem of blind separation of sources, based on the concept of mutual information. This concept is applied to the whole source sequences as stationary processes and thus provides a universal contrast ...

The problem of optimal sequential decision for individual sequences, relative to a class of competing off-line reference strategies, is studied for general loss functions with memory. This problem is motivated by applications in which actions may have "...

Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his/her predictions a number of steps in advance, with incomplete information. For finite action ...

We study the sample complexity of proper and improper learning problems with respect to different q-loss functions. We improve the known estimates for classes which have relatively small covering numbers in empirical L₂ spaces (e.g. log-covering numbers ...

We establish a one-to-one correspondence between information inequalities and group inequalities. The major implication of our result is that we can prove information inequalities by proving the corresponding group inequalities, and vice versa. By ...

We take the point of view that a Markov random field is a collection of so-called full conditional mutual independencies. Using the theory of I-measure, we have obtained a number of fundamental characterizations related to conditional mutual ...

We study the problem of source coding with multiple descriptions, which is described as follows. Let X be a discrete memoryless source. There are two encoders, Encoders 1 and 2, and three decoders, Decoders 0, 1, and 2. Encoders 1 and 2 describe the ...

In this paper, alphabet extension for Markov sources is studied such that each extension tree is grown by splitting the node with the maximum value for a weight as a generalization of the leaf probability in Tunstall's (1967) algorithm. We show that the ...

Multiple description (MD) coding is a source coding technique for information transmission over unreliable networks. In MD coding, the coder generates several different descriptions of the same signal and the decoder can produce a useful reconstruction ...

The undetected error probabilities of codes when used repeatedly to transmit sequences of messages are studied. It is shown that for any code whose rate is greater than zero but less than one, the coding scheme obtained by the repeated use of the code ...

New extremal self-dual codes of length 62 are constructed with weight enumerators of three different types. Two of these types were not represented by any known code up till now. All these codes possess an automorphism of order 15. Some of them are used ...

Previously, (linear) codes over Z ₄ and quasi-cyclic (QC) codes (over fields) have been shown to yield useful results in coding theory. Combining these two ideas we study Z ₄-QC codes and obtain new binary codes using the usual Gray map. Among the new ...

Using a particular construction of generator matrices of the q-ary image of q^m-ary cyclic codes, it is proved that some of these codes are invariant under the action of particular permutation groups. The equivalence of such codes with some two-...

We evaluate the variance of the union performance bound for a rate-1/3 turbo code over all possible interleavers of length N, under the assumption of a maximum-likelihood (ML) decoder. Theoretical and simulation results for turbo codes with two-memory ...

The linear vector-valued channel x |→ Π_n M_nx + z with z and M_n denoting additive white Gaussian noise and independent random matrices, respectively, is analyzed in the asymptotic regime as the dimensions of the matrices and vectors involved ...

Three new partition problems are proposed. The fact that these problems are NP-complete is shown

Traceability codes are identifiable parent property (IPP) codes with the additional requirement that the Hamming distance can be used to trace a parent of a word. Traceability codes can be used for constructing digital fingerprints in order to deter ...

We consider the problem of estimating the feedback coefficients of a linear feedback shift register based on noisy observations. The problem of determining feedback coefficients in the absence of noise is now classical (Massey's (1969) algorithm). In ...