Asymptotic capacity of two-dimensional channels with checkerboard constraints

A checkerboard constraint is a bounded measurable set S/spl sub/R/sup 2/, containing the origin. A binary labeling of the Z/sup 2/ lattice satisfies the checkerboard constraint S if whenever t/spl isin/Z/sup 2/ is labeled 1, all of the other Z/sup 2/-lattice points in the translate t+S are labeled 0. Two-dimensional channels that only allow labelings of Z/sup 2/ satisfying checkerboard constraints are studied. Let A(S) be the area of S, and let A(S)/spl rarr//spl infin/ mean that S retains its shape but is inflated in size in the form /spl alpha/S, as /spl alpha//spl rarr//spl infin/. It is shown that for any open checkerboard constraint S, there exist positive reals K/sub 1/ and K/sub 2/ such that as A(S)/spl rarr//spl infin/, the channel capacity C/sub S/ decays to zero at least as fast as (K/sub 1/log/sub 2/A(S))/A(S) and at most as fast as (K/sub 2/log/sub 2/A(S))/A(S). It is also shown that if S is an open convex and symmetric checkerboard constraint, then as A(S)/spl rarr//spl infin/, the capacity decays exactly at the rate 4/spl delta/(S)(log/sub 2/A(S))/A(S), where /spl delta/(S) is the packing density of the set S. An implication is that the capacity of such checkerboard constrained channels is asymptotically determined only by the areas of the constraint and the smallest (possibly degenerate) hexagon that can be circumscribed about the constraint. In particular, this establishes that channels with square, diamond, or hexagonal checkerboard constraints all asymptotically have the same capacity, since /spl delta/(S)=1 for such constraints.     

Achievable key rates for universal simulation of random data with respect to a set of statistical tests

We consider the problem of universal simulation of an unknown source from a certain parametric family of discrete memoryless sources, given a training vector X from that source and given a limited budget of purely random key bits. The goal is to generate a sequence of random vectors {Y/sub i/}, all of the same dimension and the same probability law as the given training vector X, such that a certain, prescribed set of M statistical tests will be satisfied. In particular, for each statistical test, it is required that for a certain event, /spl epsiv//sub /spl lscr//, 1 /spl les/ /spl lscr/ /spl les/ M, the relative frequency /sup 1///sub N/ /spl Sigma//sub i=1//sup N/ 1/sub /spl epsiv//spl lscr//(Y/sub i/) (1/sub /spl epsiv//(/spl middot/) being the indicator function of an event /spl epsiv/), would converge, as N /spl rarr/ /spl infin/, to a random variable (depending on X), that is typically as close as possible to the expectation of 1/sub /spl epsiv//spl lscr/,/ (X) with respect to the true unknown source, namely, to the probability of the event /spl epsiv//sub /spl lscr//. We characterize the minimum key rate needed for this purpose and demonstrate how this minimum can be approached in principle.     

Asymptotic properties on codeword lengths of an optimal FV code for general sources

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.     

Hit statistics in FH-CDMA unslotted packet networks

This correspondence is concerned with the statistical dependence of hits due to multiple-access interference in the time-unslotted frequency-hopping (FH) packet networks. Relying on the technique of joint probability generating functions (PGFs), we give a formal proof that if the ratio of the number of interfering packets to the number of frequency slots K/q is held constant, hits due to multiple-access interference are asymptotically independent as q/spl rarr//spl infin/. We also derive expressions for the correlation coefficients of hits in the packet.     

Convergence and loss bounds for Bayesian sequence prediction

The probability of observing x/sub t/ at time t, given past observations x/sub 1/...x/sub t-1/ can be computed if the true generating distribution /spl mu/ of the sequences x/sub 1/x/sub 2/x/sub 3/... is known. If /spl mu/ is unknown, but known to belong to a class /spl Mscr/ one can base one's prediction on the Bayes mix /spl xi/ defined as a weighted sum of distributions /spl nu/ /spl isin/ /spl Mscr/. Various convergence results of the mixture posterior /spl xi//sub t/ to the true posterior /spl mu//sub t/ are presented. In particular, a new (elementary) derivation of the convergence /spl xi//sub t///spl mu//sub t/ /spl rarr/ 1 is provided, which additionally gives the rate of convergence. A general sequence predictor is allowed to choose an action y/sub t/ based on x/sub 1/...x/sub t-1/ and receives loss /spl lscr//sub x(t)y(t)/ if x/sub t/ is the next symbol of the sequence. No assumptions are made on the structure of /spl lscr/ (apart from being bounded) and /spl Mscr/. The Bayes-optimal prediction scheme /spl Lambda//sub /spl xi// based on mixture /spl xi/ and the Bayes-optimal informed prediction scheme /spl Lambda//sub /spl mu// are defined and the total loss L/sub /spl xi// of /spl Lambda//sub /spl xi// is bounded in terms of the total loss L/sub /spl mu// of /spl Lambda//sub /spl mu//. It is shown that L/sub /spl xi// is bounded for bounded L/sub /spl mu// and L/sub /spl xi///L/sub /spl mu// /spl rarr/ 1 for L/sub /spl mu// /spl rarr/ /spl infin/. Convergence of the instantaneous losses is also proven.     

Lossless and near-lossless source coding for multiple access networks

A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {X/sub i/}/sub i=1//sup /spl infin// and {Y/sub i/}/sub i=1//sup /spl infin// is drawn independent and identically distributed (i.i.d.) according to joint probability mass function (p.m.f.) p(x,y); the encoder for each source operates without knowledge of the other source; the decoder jointly decodes the encoded bit streams from both sources. The work of Slepian and Wolf describes all rates achievable by MASCs of infinite coding dimension (n/spl rarr//spl infin/) and asymptotically negligible error probabilities (P/sub e//sup (n)//spl rarr/0). In this paper, we consider the properties of optimal instantaneous MASCs with finite coding dimension (n相似文献   

The Kullback-Leibler divergence rate between Markov sources

In this work, we provide a computable expression for the Kullback-Leibler divergence rate lim/sub n/spl rarr//spl infin//1/nD(p/sup (n)//spl par/q/sup (n)/) between two time-invariant finite-alphabet Markov sources of arbitrary order and arbitrary initial distributions described by the probability distributions p/sup (n)/ and q/sup (n)/, respectively. We illustrate it numerically and examine its rate of convergence. The main tools used to obtain the Kullback-Leibler divergence rate and its rate of convergence are the theory of nonnegative matrices and Perron-Frobenius theory. Similarly, we provide a formula for the Shannon entropy rate lim/sub n/spl rarr//spl infin//1/nH(p/sup (n)/) of Markov sources and examine its rate of convergence.     

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.     

Capacity and lattice strategies for canceling known interference

We consider the generalized dirty-paper channel Y=X+S+N,E{X/sup 2/}/spl les/P/sub X/, where N is not necessarily Gaussian, and the interference S is known causally or noncausally to the transmitter. We derive worst case capacity formulas and strategies for "strong" or arbitrarily varying interference. In the causal side information (SI) case, we develop a capacity formula based on minimum noise entropy strategies. We then show that strategies associated with entropy-constrained quantizers provide lower and upper bounds on the capacity. At high signal-to-noise ratio (SNR) conditions, i.e., if N is weak relative to the power constraint P/sub X/, these bounds coincide, the optimum strategies take the form of scalar lattice quantizers, and the capacity loss due to not having S at the receiver is shown to be exactly the "shaping gain" 1/2log(2/spl pi/e/12)/spl ap/ 0.254 bit. We extend the schemes to obtain achievable rates at any SNR and to noncausal SI, by incorporating minimum mean-squared error (MMSE) scaling, and by using k-dimensional lattices. For Gaussian N, the capacity loss of this scheme is upper-bounded by 1/2log2/spl pi/eG(/spl Lambda/), where G(/spl Lambda/) is the normalized second moment of the lattice. With a proper choice of lattice, the loss goes to zero as the dimension k goes to infinity, in agreement with the results of Costa. These results provide an information-theoretic framework for the study of common communication problems such as precoding for intersymbol interference (ISI) channels and broadcast channels.     

Sigma-delta (/spl Sigma//spl Delta/) quantization and finite frames

The K-level Sigma-Delta (/spl Sigma//spl Delta/) scheme with step size /spl delta/ is introduced as a technique for quantizing finite frame expansions for /spl Ropf//sup d/. Error estimates for various quantized frame expansions are derived, and, in particular, it is shown that /spl Sigma//spl Delta/ quantization of a unit-norm finite frame expansion in /spl Ropf//sup d/ achieves approximation error where N is the frame size, and the frame variation /spl sigma/(F,p) is a quantity which reflects the dependence of the /spl Sigma//spl Delta/ scheme on the frame. Here /spl par//spl middot//spl par/ is the d-dimensional Euclidean 2-norm. Lower bounds and refined upper bounds are derived for certain specific cases. As a direct consequence of these error bounds one is able to bound the mean squared error (MSE) by an order of 1/N/sup 2/. When dealing with sufficiently redundant frame expansions, this represents a significant improvement over classical pulse-code modulation (PCM) quantization, which only has MSE of order 1/N under certain nonrigorous statistical assumptions. /spl Sigma//spl Delta/ also achieves the optimal MSE order for PCM with consistent reconstruction.     

Timing-synchronization analysis for IEEE 802.11a wireless LANs in frequency-nonselective Rician fading environments

This paper derives and computes the probability of synchronization failure P/sub fail/ for IEEE 802.11a wireless LANs on frequency-flat Rician fading channels. For a frequency offset within /spl plusmn/232 kHz, it is shown that its effect on the synchronization performance is minor. The E/sub ds//N/sub 0/ ratios required to achieve P/sub fail/=10/sup -3/ and 10/sup -4/ are computed, where E/sub ds/ is the data-symbol energy. We find that E/sub ds//N/sub 0/ ratios over 20 dB are generally required for channels with Rician factors K/spl les/6 dB. In particular, E/sub ds//N/sub 0/ ratios that yield P/sub fail/=10/sup -4/ exceed 30 dB for K/spl les/4 dB.     

Exact error performance of square orthogonal space- time block coding with channel estimation

Consider a wireless communication system in flat fading with N transmit and M receive antennas using space-time block coding, where N/spl times/1 code vectors are transmitted over L symbol intervals, resulting in an N/spl times/L code matrix. A least-squares estimate (LSE) as well as a minimum mean-square estimate (MMSE) of the M/spl times/N channel matrix is obtained from a sequence of pilot code vectors. For the case of linear square (i.e., with N=L) orthogonal codes over constant envelope constellations, we obtain an expression for the exact decoding error probability (DEP) for coherent maximum-likelihood decoding. We also find the coding gain for high average signal-to-noise ratio (SNR) per diversity branch in the case of Rayleigh fading. A comparison between both channel-estimation techniques is done in terms of the average pilot-power-to-signal-power ratio (APPSPR). It is found that MMSE requires lower pilot power than LSE for the same DEP and the same average SNR per diversity branch. In addition, the error performance with LSE approaches that with MMSE, with an increase of average SNR per branch or an increase of APPSPR.     

Discrete Chaos-I: Theory

We propose a definition of the discrete Lyapunov exponent for an arbitrary permutation of a finite lattice. For discrete-time dynamical systems, it measures the local (between neighboring points) average spreading of the system. We justify our definition by proving that, for large classes of chaotic maps, the corresponding discrete Lyapunov exponent approaches the largest Lyapunov exponent of a chaotic map when M/spl rarr//spl infin/, where M is the cardinality of the discrete phase space. In analogy with continuous systems, we say the system has discrete chaos if its discrete Lyapunov exponent tends to a positive number, when M/spl rarr//spl infin/. We present several examples to illustrate the concepts being introduced.     

On the /spl theta/-coverage and connectivity of large random networks

Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for /spl theta/-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its /spl phi//sub n/ nearest neighbors. A network is called /spl theta/-covered if every node, except those near the boundary, can find one of its /spl phi//sub n/ nearest neighbors in any sector of angle /spl theta/. For all /spl theta//spl isin/(0,2/spl pi/), if /spl phi//sub n/=(1+/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, it is shown that the probability of /spl theta/-coverage goes to one as n goes to infinity, for any /spl delta/>0; on the other hand, if /spl phi//sub n/=(1-/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, the probability of /spl theta/-coverage goes to zero. This sharp characterization of /spl theta/-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if /spl phi//sub n/=(1+/spl delta/)log/sub 2/n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.     

Downlink transmission of broadband OFCDM systems-part III: turbo-coded

Orthogonal frequency and code-division multiplexing (OFCDM) systems have been introduced for high-speed data transmission in future wireless mobile communications. In this paper, a hybrid multicode interference cancellation (MCI) and minimum mean-square error (MMSE) detection scheme is presented for the turbo-coded OFCDM systems. Channel estimation based on a code-multiplexed pilot channel is employed. The weights of the hybrid detection are derived theoretically and an effective method to generate the weights in practical applications is proposed. By means of computer simulation, the effects of system parameters on the performance are studied extensively. It is shown that the hybrid detection outperforms pure MMSE detection in various channel conditions, especially for high-level modulation schemes. To carry out interference regeneration for the hybrid detection, the conventional turbo decoding algorithm which only decodes systematic bits should be extended to decode parity bits as well. Moreover, two iterations in turbo decoding are sufficient to provide good performance for the system with the multistage hybrid detection. Finally, given time-domain spreading factor N/sub T/, the system performance improves with frequency-domain spreading factor N/sub F/. However, the frequency diversity gain is saturated when N/sub F/ is large (i.e., N/sub F//spl ges/16).     

Defect-enhanced visible electroluminescence of multi-energy silicon-implanted silicon dioxide film

White-light and blue-green electroluminescence (EL) of a multirecipe Si-ion-implanted SiO/sub 2/ (SiO/sub 2/:Si/sup +/) film on Si substrate are demonstrated. The blue-green photoluminescence (PL) is enhanced by the reaction of O/sub 3//spl equiv/Si-O-Si/spl equiv/O/sub 3//spl rarr/O/sub 3//spl equiv/Si-Si/spl equiv/O/sub 3/+O/sub interstitial/ during Si implantation. After annealing at 1100/spl deg/C for 180 min, the luminescence at both 415 and 455 nm is markedly enhanced by the complete activation of radiative defects, such as weak oxygen bonds, neutral oxygen vacancies (NOVs), and the precursors of nanocrystallite Si (E'/sub /spl delta// centers). Absorption spectroscopy and electron paramagnetic resonance confirm the existence of NOVs and E'/sub /spl delta// centers. The slowly rising E'/sub /spl delta//-related PL intensity reveals that the formation of nanocrystallite Si (nc-Si) requires longer annealing times and suggests that the activation energy for diffusion of excess Si atoms is higher than that of other defects in ion implanted SiO/sub 2/. The EL from the Ag-SiO/sub 2/:Si/sup +//n-Si-Ag metal-oxide-semiconductor diode changes from deep blue to green as the driving current increase from 0.28 to 3 A. The maximum white-light luminescent power is up to 120 nW at a bias current of 1.25 A.     

Downlink transmission of broadband OFCDM Systems-part I: hybrid detection

The broadband orthogonal frequency and code division multiplexing (OFCDM) system with two-dimensional spreading (time and frequency domain spreading) is becoming a very attractive technique for high-rate data transmission in future wireless communication systems. In this paper, a quasianalytical study is presented on the downlink performance of the OFCDM system with hybrid multi-code interference (MCI) cancellation and minimum mean square error (MMSE) detection. The weights of MMSE are derived and updated stage by stage of MCI cancellation. The effects of channel estimation errors and sub-carrier correlation are also studied. It is shown that the hybrid detection scheme performs much better than pure MMSE when good channel estimation is guaranteed. The power ratio between the pilot channel and all data channels should be set to 0.25, which is a near optimum value for the two-dimensional spreading system with time domain spreading factor (N/sub T/) of 4 and 8. On the other hand, in a slow fading channel, a large value of the channel estimation window size /spl gamma/N/sub T/, where /spl gamma/ is an odd integer, is expected. However, /spl gamma/=3 is large enough for the system with N/sub T/=8 while /spl gamma/=5 is more desirable for the system with N/sub T/=4. Although performance of the hybrid detection degrades in the presence of the sub-carrier correlation, the hybrid detection still works well even the correlation coefficient is as high as 0.7. Finally, given N/sub T/, although performance improves when the frequency domain spreading factor (N/sub F/) increases, the frequency diversity gain is almost saturated for a large value of N/sub F/ (i.e., N/sub F/ /spl ges/ 32).     

Coded modulation in the block-fading channel: coding theorems and code construction

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.     

Complex-coupled quantum cascade distributed-feedback laser

Quantum-cascade distributed-feedback lasers (QCDFB) with a grating close to the active region are reported. Feedback is provided by the grating in a refractive index-dominated coupling scheme. Reliable single-mode emission at /spl lambda//sub cm//spl ap/5.4 /spl mu/m with a side-mode suppression ratio (SMSR) /spl ap/30 dB is observed. The laser is continuously tunable over 40 nm with a coefficient of /spl Delta//spl lambda///spl Delta/T/spl ap/0.37 nm/K in the temperature range from 200 K to 300 K. Comparison with Fabry-Perot QC lasers shows an overall improved performance of QC-DFB lasers.     

On the discreteness of capacity-achieving distributions

We consider a scalar additive channel x /spl rarr/ x + N whose input is amplitude constrained. By extending Smith's (1969) argument, we derive a sufficient condition on noise probability density functions (pdf) that guarantee finite support for the associated capacity-achieving distribution(s).