Recently Yamamoto and Ueda proposed multiple object identification (MOID) codes to identify multiple objects via a channel at once, which is an extension of identification (ID) codes. They gave the explicit construction of MOID codes and derived the achievable triplet of coding rate R, the error exponents E1and E2of type I and type II decoding error probabilities. However, they did not treat the converse problem of the coding theorem. In this paper, we consider the coding rate of multiple objects Rkin addition to R, E1, and E2, and derive a condition that (R, Rk, E1, E2) must satisfy for any MOID codes of noiseless channels.

The discrete time channel AWGN(A) with additive white Gaussian noise, strict power constraint and noiseless feedback is considered. The best error decoding exponent is investigated, limiting to the case of non-exponential number of messages (i.e. the rate of transmission R = 0). The new transmission strategy is proposed, showing that for AWGN(A) channel with noiseless feedback at zero rate R = 0 it is possible to achieve the same error exponent as for transmission of two messages. It gives another proof of known result for AWGN(A) channel. The strategy described is applicable to a wider class of channels.

For information transmission a discrete time channel with independent additive Gaussian noise is used. There is also a feedback channel with independent additive Gaussian noise, and the transmitter observes without delay all outputs of the forward channel via that noisy feedback channel. Transmission of nonexponential number of messages is considered and the achievable decoding error exponent for such a combination of channels is investigated. Transmission/decoding method used in the paper generalizes and strengthens the earlier method used by authors for BSC and Gaussian channel. It allows to improve essentially earlier results. In particular, for small feedback noise, it allows to gain 33.3% (instead of 23.6% in earlier papers).

The threshold, or saturation phenomenon of spatially coupled systems is revisited in the light of Lyapunov's theory of dynamical systems. It is shown that an application of Lyapunov's direct method can be used to quantitatively describe the threshold phenomenon, prove convergence, and compute threshold values. This provides a general proof methodology for the various systems recently studied.

For information transmission a discrete time channel with independent additive Gaussian noise is used. There is also feedback channel with independent additive Gaussian noise, and the transmitter observes without delay all outputs of the forward channel via that feedback channel. Transmission of nonexponential number of messages is considered and the achievable decoding error exponent for such a combination of channels is investigated. It is shown that for any finite noise in the feedback channel the achievable error exponent is better than similar error exponent of the no-feedback channel. Method of transmission/decoding used in the paper strengthens the earlier method used by authors for BSC. In particular, for small feedback noise, it allows to get the gain up to 23.6% (instead of 14.3% earlier for BSC).

A Gaussian random walk (or a Wiener process), possibly with drift, is observed in a noisy or delayed fashion. The problem considered in this paper is to estimate the first time$\tau $the random walk reaches a given level. Specifically, the average$p$-moment ($p\geq 1$) optimization problem$\inf _{\eta} {\BBE} \vert \eta -\tau \vert ^{p}$is investigated where the infimum is taken over the set of stopping times that are defined on the observation process. When there is no drift, optimal stopping rules are characterized for both types of observations. When there is a drift, upper and lower bounds on$\inf _{\eta} {\BBE} \vert \eta -\tau \vert ^{p}$are established for both types of observations. The bounds are tight in the large-level regime for noisy observations and in the large-level-large-delay regime for delayed observations. Noteworthy, for noisy observations there exists an asymptotically optimal stopping rule that is a function of a single observation. Simulation results are provided that corroborate the validity of the results for non-asymptotic settings.

Given a Gaussian random walk X with drift, we consider estimating its first-passage time τ, of a given level ℓ, with a stopping time η defined over an observation process Y that is either a noisy version of X, or a delayed version of X. For both cases, we provide lower bounds on average moments E|η - τ|p, p ≥ 1, for any stopping rule η, and exhibit simple stopping rules that achieve these bounds in the large threshold regime and in the large threshold large delay regime, respectively. The results immediately extend to the corresponding continuous time settings where X and Y are standard Wiener processes with drift.

Theoretical limits of performance of error control coding in iterative cancellation systems is explored. Limits of the modulation symbol estimation error attainable by any code are given. Required properties of optimal codes for cancellation are exposed, and the actual performance of several popular code families is discussed.

For the information transmission a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes without delay all the outputs of the forward channel via that feedback channel. The overall transmission time is fixed. The transmission of a exponential number of messages (i.e. the transmission rate is positive) is considered. The achievable decoding error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the best known lower bound for the error exponent of the no-feedback channel.

Error exponents are studied for recursive and majority decoding of general Reed-Muller (RM) codesRM(r,m) used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any codeRM(r,m), we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.

A novel hypothesis-based preamble detection method for uncoordinated, high-density packet-based communication over an additive white Gaussian noise channel is proposed and analyzed. Received samples are observed over a window of length equal to that of the preamble and a metric is computed for each sample shift of the window. A metric exceeding a noise dependent pre-computed threshold flags the presence of a preamble. The preamble sequence consists of concatenated sections of spreading sequences whose length is at most the coherence time of the channel. These sections are then differentially combined. A differential correlation-based detection is employed to locate the boundaries of the preamble. A theoretical framework is developed to provide exact analytical solutions for missing and falsely detecting a preamble using matrix analysis of quadratic Gaussian statistics. Furthermore, the robustness of the proposed methodology in a two path channel is studied. The effects of frequency and timing offsets on the system performance is evaluated. Simulation results are presented to validate the analytical expressions. Additionally, a performance comparison of the proposed differential detection scheme with that of a noncoherent square-law detector is presented.

Error exponents are studied for the recursive and majority decoding algorithms of general Reed-Muller codes RM(r, m) used on the AWGN channels. Both algorithms have low decoding complexity and substantially outperform bounded distance decoding in their error-correcting capabilities. We obtain asymptotically tight upper bounds on the output error rate that hold for both algorithms and can be used for any RM-code.

A binary symmetric channel is considered. A transmitter observes without delay all the outputs of the forward channel via a noisy binary symmetric channel (a feedback). For illustrative purposes, we consider the transmission of only three messages. The best achievable error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than some positive level, then the achievable error exponent is better than the similar error exponent of the no-feedback channel. In particular, it is the case if the crossover probability of the feedback channel is eight (or more) times smaller than the crossover probability of the forward channel. The transmission strategy described in this talk and the corresponding lower bound for the error exponent can be strengthened and extended to the positive transmission rates as well.

A new approach for upper bounding the channel reliability function using the code spectrum is described. It allows both low and high rate cases to be treated in a unified way. In particular, the earlier known upper bounds are improved, and a new derivation of the sphere-packing bound is presented.

Recursive decoding is studied for Reed-Muller (RM) codes used on a binary symmetric channel. Decoding is performed beyond the bounded distance radius d/2 and corrects most error patterns of weight up to (dlnd)/2. In our analysis, decoding is decomposed into consecutive steps, with one information bit derived in each step. Then the error probability of each step is defined by the recursive recalculations of the Bernoulli random variables. We derive the exponential moments of the recalculated random variables. As a result, tight exponential bounds on the output error probability are obtained for the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs plusmn1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code

Iterative interference cancellation of coded code-division multiple access (CDMA) using random spreading with linear cancellation is analyzed. If users are grouped into power classes and Shannon bound approaching codes are used, a geometric power distribution achieves the additive white Gaussian noise (AWGN) channel Shannon bound as the numbers of classes becomes large. The optimal distribution of the size of these classes is shown to be uniform. If users are grouped into different rate classes with equal powers among equal rate users, the Shannon bound for AWGN channels can be achieved with an arbitrary distribution of the classes sizes, provided that the size of the largest rate class obeys the mild condition that its ratio of size to processing gain is much smaller than the inverse of the signal-to-noise ratio (SNR). The case of equal powers and equal rates among all users is addressed as a "worst case" scenario. It is argued that simple repetition codes provide for a larger achievable capacity than stronger codes. It is shown that this capacity monotonically increases as the rate of the code decreases. A density evolution analysis is used to show that the achievable rates exceed those of a minimum-mean square error filter applied to the uncoded signals. This lower bound is tight for small ratios of bit energy to noise power, and otherwise the iterative cancellation receiver provides an appreciably larger capacity. Relating to recent result from the application of statistical mechanics it is shown that the repetition-coded system with iterative cancellation achieves the performance of an equivalent optimal joint detector for uncoded transmission

The problem of determining the bit-error probability in linear multiuser detection analytically is considered. A number of upper and lower bounds are developed, some of which are very tight, and issues of asymptotic behavior, optimality, and Gaussian approximation are explored. Several special cases, including those of equi-energy and equi-correlated signals, are treated in some detail.

The error exponent of the two-user Poisson multiple-access channel under peak and average power constraints, but unlimited in bandwidth, is considered. First, a random coding lower bound on the error exponent is obtained, and an extension of Wyner's (1988) single-user codes is shown to be exponentially optimum for this case as well. Second, the sphere-packing bounding technique suggested by Burnashev and Kutoyants (see Probl. Inform. Transm., vol.35, no.2, p.3-22, 1999) is generalized to the case at hand and an upper bound on the error exponent, which coincides with the lower bound, is derived. Thus, this channel joins its single-user partner as one of very few for which the reliability function is known.

We consider the problem of one-dimensional parameter transmission over a Poisson channel when the input signal (intensity) obeys a peak energy constraint. We show that it is possible to choose input signals and an estimator in such a way that the mean-square error of parameter transmission will decrease exponentially with transmission time T/spl rarr//spl infin/ and we find the best possible exponent. For more general loss functions of the type |x|/spl alpha/ we find the best possible exponent if /spl alpha//spl ges//spl alpha//sub 0/=(1+/spl radic/5)/2/spl ap/1.618. If 0</spl alpha/

Two kinds of channels are considered: (1) discrete-time channel with additive noise, and (2) Poisson and white Gaussian (i.e., continuous-time) channels. For the type (1) channel there are given some sufficient conditions when the Shannon and identification capacities coincide. It is shown that the identification capacity of Poisson and Gaussian channels without bandwidth constraint is infinite. Conversely, for a white Gaussian channel with bandwidth constraint, the identification capacity coincides with the Shannon capacity.

A simple proof of one probabilistic inequality is presented. Let P and Q be two given probability measures on a measurable space (/spl Xscr/, /spl Ascr/). We consider testing of hypotheses P and Q using one observation. For an arbitrary decision rule, let /spl alpha/ and /spl beta/ denote the two kinds of error probabilities. If both error probabilities have equal costs (or we want to minimize the maximum of them) then it is natural to investigate the minimal possible sum inf{/spl alpha/+/spl beta/} for the best decision rule.

A Markovian technique is described to calculate the exact performance of the Viterbi algorithm used as either a channel decoder or a source encoder for a convolutional code. The probability of information bit error and the expected Hamming distortion are computed for codes of various rates and constraint lengths. The concept of tie-breaking rules is introduced and its influence on decoder performance is examined. Computer simulation is used to verify the accuracy of the results. Finally, we discuss the issue of when a coded system outperforms an uncoded system in light of the new results.>

The number of samples required for signal detection is considered as a function of the error probabilities. This problem is treated in the context of detecting a constant signal in additive, independent, and identically distributed noise. Detectors that base their decisions on the comparison with a threshold of accumulated, nonlinearly transformed observations are treated. Asymptotic expressions are derived for the relationship between sample size and error probabilities for this model in two situations: that in which the nonlinearity has a partially absolutely continuous output distribution; and that in which it has a lattice output distribution. Traditional analyses of such problems have involved only the lowest order terms of such relationships (i.e. central limit theorem results), leading to performance indices such as the Pitman asymptotic relative efficiency (ARE). Such indices are known to be of limited accuracy in predicting performance for more moderate sample sizes. Here, the behavior of sample size as a function of error probabilities is considered in more detail, leading to more accurate indices of relative efficiencies for such detection problems. Several specific examples are examined in detail, and numerical results are included to illustrate the significantly improved performance estimation afforded thereby for even small sample sizes.

The performance of trellis codes is determined by their minimum Euclidean distance. Upper bounds on this minimum distance valid for phase-shift-keyed (PSK) signals that improve on previously derived bounds are derived. Although the bound is valid only for PSK signals, the bounding techniques developed here can be extended to other equal-energy configurations and hence could pave the way to obtaining more general results.>

Upper and lower bounds are derived on the exponential behavior of the\alpha-mean error for parameter transmission over the additive white Gaussian noise channel. The method of proving the lower bound may be used in many information theory and mathematical statistics problems.