An upper bound for codes for the noisy two-access binary adder channel (Corresp.)

Using earlier methods a combinatorial upper bound is derived for|C|. cdot |D|, where(C,D)is adelta-decodable code pair for the noisy two-access binary adder channel. Asymptotically, this bound reduces toR_{1}=R_{2} leq frac{3}{2} + elog_{2} e - (frac{1}{2} + e) log_{2} (1 + 2e)= frac{1}{2} - e + H(frac{1}{2} - e) - frac{1}{2}H(2e),wheree = lfloor (delta - 1)/2 rfloor /n, n rightarrow inftyandR_{1}resp.R_{2}is the rate of the codeCresp.D.     

Asymptotic properties of delay-time-weighted probability of error (Corresp.)

Asymptotic properties of expected distortion are studied for the delay-time-weighted probability of error distortion measured_n(x,tilde{x}) = n^{-1} sum_{t=0}^{n-1} f(t + n)[l - delta(x_t,tilde{x}_t)],, wherex = (x_0,x_1,cdots,x_{n-1})andtilde{x} = (tilde{x}_0,tilde{x}_1,cdots,tilde{x}_{n-1})are source and reproducing vectors, respectively, anddelta (cdot, cdot)is the Kronecker delta. With reasonable block coding and transmission constraintsx_tis reproduced astilde{x}_twith a delay oft + ntime units. It is shown that if the channel capacity is greater than the source entropyC > H(X), then there exists a sequence of block lengthncodes such thatE[d_n(X,tilde{X})] rigjhtarrow 0asn rightarrow inftyeven iff(t) rightarrow inftyat an exponential rate. However, iff(t)grows at too fast an exponential rate, thenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow infty. Also, ifC < H(X)andf(t) rightarrow inftythenE[d_n(X,tilde{X})] rightarrow inftyasn rightarrow inftyno matter how slowlyf(t)grows.     

On theepsilon-entropy and the rate-distortion function of certain non-Gaussian processes

Letxi = {xi(t), 0 leq t leq T}be a process with covariance functionK(s,t)andE int_0^T xi^2(t) dt < infty. It is proved that for everyvarepsilon > 0thevarepsilon-entropyH_{varepsilon}(xi)satisfies begin{equation} H_{varepsilon}(xi_g) - mathcal{H}_{xi_g} (xi) leq H_{varepsilon}(xi) leq H_{varepsilon}(xi_g) end{equation} wherexi_gis a Gaussian process with the covarianeeK(s,t)andmathcal{H}_{xi_g}(xi)is the entropy of the measure induced byxi(in function space) with respect to that induced byxi_g. It is also shown that ifmathcal{H}_{xi_g}(xi) < inftythen, asvarepsilon rightarrow 0begin{equation} H_{varepsilon}(xi) = H_{varepsilon}(xi_g) - mathcal{H}_{xi_g}(xi) + o(1). end{equation} Furthermore, ff there exists a Gaussian processg = { g(t); 0 leq t leq T }such thatmathcal{H}_g(xi) < infty, then the ratio betweenH_{varepsilon}(xi)andH_{varepsilon}(g)goes to one asvarepsilongoes to zero. Similar results are given for the rate-distortion function, and some particular examples are worked out in detail. Some cases for whichmathcal_{xi_g}(xi) = inftyare discussed, and asymptotic bounds onH_{varepsilon}(xi), expressed in terms ofH_{varepsilon}(xi_g), are derived.     

Improvements of Winograd's result on computation in the presence of noise (Corresp.)

Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a codevarphi: {0,1}^{k} rightarrow {0,1}^{n}is min-preserving(varphi (a wedge b) = varphi (a) wedge varphi (b)fora,b in {0,1}^{k})andepsilon n-error correcting, then the ratek/n rightarrow 0ask rightarrow infty. This result is improved and extended in two directions. begin{enumerate} item For min-preserving codes with {em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n rightarrow 0ask rightarrow infty(strong converses). item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( varphi (a) leq varphi (b)fora leq b)the results in direction 1) hold for maximal errors. end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory.     

A theorem on the entropy of certain binary sequences and applications--I

In this, the first part of a two-part paper, we establish a theorem concerning the entropy of a certain sequence of binary random variables. In the sequel we will apply this result to the solution of three problems in multi-user communication, two of which have been open for some time. Specifically we show the following. LetXandYbe binary randomn-vectors, which are the input and output, respectively, of a binary symmetric channel with "crossover" probabilityp_0. LetH{X}andH{ Y}be the entropies ofXandY, respectively. Then begin{equation} begin{split} frac{1}{n} H{X} geq h(alpha_0), qquad 0 leq alpha_0 &leq 1, Rightarrow \ qquad qquad &qquad frac{1}{n}H{Y} geq h(alpha_0(1 - p_0) + (1 - alpha_0)p_0) end{split} end{equation} whereh(lambda) = -lambda log lambda - (1 - lambda) log(l - lambda), 0 leq lambda leq 1.     

A fundamental inequality between the probabilities of binary subgroups and cosets

The probability of a set of binaryn-tuples is defined to be the sum of the probabilities of the individualn-tuples when each digit is chosen independently with the same probabilitypof being a "one." It is shown that, under such a definition, the ratio between the probability of a subgroup of order2^{k}and any of its proper cosets is always greater than or equal to a functionF_{k}(p), whereF_{k}(p) geq 1forp leq frac{1}{2}with equality when and only whenp = frac{1}{2}. It is further shown thatF_{k}(p)is the greatest lower bound on this ratio, since a subgroup and proper coset of order2^{k}can always be found such that the ratio between their probabilities is exactlyF_{k}(p). It is then demonstrated that for a linear code on a binary symmetric channel the "tall-zero" syndrome is more probable than any other syndrome. This result is applied to the problem of error propagation in convolutional codes.     

Equipartition laws of thermal noise

Classically, the thermal noise in electricalRCcircuits andLCRseries circuits is governed by the equipartition lawfrac{1}{2}overline{CV^{2}} = frac{1}{2}kT, whereV(t)is the noise voltage developed acrossC. When quantum effects are taken into account, the equipartition law no longer holds forRCcircuits, although an equipartition law can be deemed for the measured mean square noise voltage under certain conditions. InLCRseries circuits the equipartition lawfrac{1}{2}overline{CV^{2}} = frac{1}{2}kT, changes intofrac{1}{2}overline{CV^{2}} = frac{1}{2}bar{E}(f_{0})for high-Qtuned circuits, wherebar{E}(f_{0})is the average energy of a harmonic oscillator tuned at the tuning frequency of the tuned circuit.     

An upper bound to the capacity of the band-limited Gaussian autoregressive channel with noiseless feedback

Upper bounds to the capacity of band-limited Gaussianmth-order autoregressive channels with feedback and average energy constraintEare derived. These are the only known hounds on one- and two-way autoregressive channels of order greater than one. They are the tightest known for the first-order case. In this case letalpha_1be the regression coefficient,sigma^2the innovation variance,Nthe number of channel iterations per source symbol, ande = E/N; then the first-order capacityC^1is bounded by begin{equation} C^1 leq begin{cases} frac{1}{2} ln [frac{e}{sigma^2}(1+ mid alpha_1 mid ) ^ 2 +1], & frac{e}{sigma^2} leq frac{1}{1- alpha_1^2} \ frac{1}{2} ln [frac{e}{sigma^2} + frac{2mid alpha_1 mid}{sqrt{1-alpha_1^2}} sqrt{frac{e}{simga^2}} + frac{1}{1-alpha_1^2}], & text{elsewhere}.\ end{cases} end{equation} This is equal to capacity without feedback for very low and very highe/sigma^2and is less than twice this one-way capacity everywhere.     

Writing on dirty paper (Corresp.)

A channel with outputY = X + S + Zis examined, The stateS sim N(0, QI)and the noiseZ sim N(0, NI)are multivariate Gaussian random variables (Iis the identity matrix.). The inputX in R^{n}satisfies the power constraint(l/n) sum_{i=1}^{n}X_{i}^{2} leq P. IfSis unknown to both transmitter and receiver then the capacity isfrac{1}{2} ln (1 + P/( N + Q))nats per channel use. However, if the stateSis known to the encoder, the capacity is shown to beC^{ast} =frac{1}{2} ln (1 + P/N), independent ofQ. This is also the capacity of a standard Gaussian channel with signal-to-noise power ratioP/N. Therefore, the stateSdoes not affect the capacity of the channel, even thoughSis unknown to the receiver. It is shown that the optimal transmitter adapts its signal to the stateSrather than attempting to cancel it.     

On mean-square aliasing error in the cardinal series expansion of random processes (Corresp.)

An upper bound is derived for the mean-square error involved when a non-band-limited, wide-sense stationary random processx(t)(possessing an integrable power spectral density) is approximated by a cardinal series expansion of the formsum^{infty}_{-infty}x(n/2W)sinc2W(t-n/2W), a sampling expansion based on the choice of some nominal bandwidthW > 0. It is proved thatlim_{N rightarrow infty} E {|x(t) - x_{N}(t)|^{2}} leq frac{2}{pi}int_{| omega | > 2 pi W}S_{x}( omega) d omega,wherex_{N}(t) = sum_{-N}^{N}x(n/2W)sinc2W(t-n/2W), andS_{x}(omega)is the power spectral density forx(t). Further, the constant2/ piis shown to be the best possible one if a bound of this type (involving the power contained in the frequency region lying outside the arbitrarily chosen band) is to hold uniformly int. Possible reductions of the multiplicative constant as a function oftare also discussed, and a formula is given for the optimal value of this constant.     

Multiplication noise in uniform avalanche diodes

A general expression is derived from which the spectral density of the noise generated in a uniformly multiplying p-n junction can be calculated for any distribution of injected carriers. The analysis is limited to the white noise part of the noise spectrum only, and to diodes having large potential drops across the multiplying region of the depletion layer. It is shown for the special case in whichbeta = kalpha, wherekis a constant and α and β are the ionization coefficients of electrons and holes, respectively, that the noise spectral density is given by2eI_{in}M^{3}[1 + (frac{1 - k}{k})(frac{M - 1}{M})^{2}]where M is the current multiplication factor and Iinthe injected current, if the only carriers injected into the depletion layer are holes, and by2eI_{in}M^{3}[1 - (1 - k)(frac{M - 1}{M})^{2}]if the only injected carriers are electrons. An expression is also derived for the noise power which will be delivered to an external load for the limitM rightarrow infin.     

Optimum waveform signal sets with amplitude and energy constraints

It is desirable to choose the waveforms making up a signaling alphabet so that they are maximally separated one from another. This problem is considered, in the space of square-integrable functions, for signals which have finite duration, and are constrained in the ranges of their values as well as in energy. Corresponding to each of the following cases, we establish sharp bounds for the minimum distance and for the average distance between elements of a fixed size signal set, and construct sets of signals that attain both bounds simultaneously. begin{list} item {em Case A (Energy Constraint Only):} The average energy of the waveforms in the signal set is at mostsigma, where0 leq sigma < infty. item {em Case B (Energy and Peak Amplitude Constraints):} The average energy of the waveforms in the signal set isleq sigma (0 leq sigma < 1), and the absolute value of each waveform is at most1. item {em Case C (Energy and Value Constraints):} The average energy of the waveforms in the signal set is at mostb^{2}sigma + a^{2}(1 - sigma), and each waveform takes values in the set[a, b], where0 leq a < b < infty, and0 leq sigma leq 1. end{list} Cases A and B are applicable to signal design for communication in channels with additive noise (say Gaussian), and Case C is applicable to signal design for optical channels, where the signal represents the intensity of a photon stream. The general character of the results is that the minimum distance behaves likegamma sigmain Cases A and B, and likegamma sigma (1 - sigma)in Case C, withgammaa suitable constant.     

An improved error bound for equal-strength diversity channels (Corresp.)

An upper bound on the minimum probability of error for an equal-strength diversity channel is simply derived that improves a previously known bound by the factor[4(1 - p)]^(-1),0 leq p leq frac{1}{2}.     

Asymptotics and Error Rate Bounds for M-ary DPSK

The symbol error probabilityP_{E}(M)forM-ary DPSK is shown to be bounded in terms of a recent asymptotic approximationP_{asym}(M)by the inequalitiesP_{asym}(M) < P_{E}(M) < 1.03P_{asym}(M);M geq 4, E_{b}/N_{0} geq 1whereE_{b}/N_{0}is the bit energy-to-noise spectral density ratio. Aside from the wide range of validity and the closeness of the lower and upper bounds, this result is striking in light of the often held view that such asymptotic approximations are primarily of value only in the limitE_{b}/N_{0} rightarrow infty; thus, one of the goals of this note is to demonstrate that asymptotic methods can lead to extremely good error rate approximations in lieu of the more traditional and more widely used bounding techniques. The results are also noted to be applicable in other similar situations which commonly occur.     

A Gaussian channel with slow fading (Corresp.)

An interleaved fading channel whose state is known to the receiver is analyzed. The reliability functionE(R)is obtained for ratesRin the rangeR_c leq R leq C. The capacity is shown to beC = E_A { frac{1}{2} ln (1 + A^2 n)}whereAis a factor describing the fading mechanism anduis the signal-to-noise ratio per dimension.     

Hypothesis testing with multiterminal data compression

The multiterminal hypothesis testingH: XYagainstH̄: X̄Ȳis considered whereX^{n} (X̄^{n})andY^{n} (Ȳ^{n})are separately encoded at ratesR_{1}andR_{2}, respectively. The problem is to determine the minimumbeta_{n}of the second kind of error probability, under the condition that the first kind of error probabilityalpha_{n} leq epsilonfor a prescribed0 < epsilon < 1. A good lower boundtheta_{L}(R_{1}, R_{2})on the power exponenttheta (R_{1}, R_{2},epsilon)= lim inf_{n rightarrow infty}(-1/n log beta_{n})is given and several interesting properties are revealed. The lower bound is tighter than that of Ahlswede and Csiszár. Furthermore, in the special case of testing against independence, this bound turns out to coincide with that given by them. The main arguments are devoted to the special case withR_{2} = inftycorresponding to full side information forY^{n}(Ȳ^{n}). In particular, the compact solution is established to the complete data compression cases, which are useful in statistics from the practical point of view.     

Bounds for truncation error in sampling expansions of band-limited signals

Forf(t)a real-valued signal band-limited to- pi r leq omega leq pi r (0 < r < 1)and represented by its Fourier integral, upper bounds are established for the magnitude of the truncation error whenf(t)is approximated at a generic timetby an appropriate selection ofN_{1} + N_{2} + 1terms from its Shannon sampling series expansion, the latter expansion being associated with the full band[-pi, pi]and thus involving samples offtaken at the integer points. Results are presented for two cases: 1) the Fourier transformF(omega)is such that|F(omega)|^{2}is integrable on[-pi, pi r](finite energy case), and 2)|F(omega)|is integrable on[-pi r, pi r]. In case 1) it is shown that the truncation error magnitude is bounded above byg(r, t) cdot sqrt{E} cdot left( frac{1}{N_{1}} + frac{1}{N_{2}} right)whereEdenotes the signal energy andgis independent ofN_{1}, N_{2}and the particular band-limited signal being approximated. Correspondingly, in case 2) the error is bounded above byh(r, t) cdot M cdot left( frac{1}{N_{1}} + frac{1}{N_{2}} right)whereMis the maximum signal amplitude andhis independent ofN_{1}, N_{2}and the signal. These estimates possess the same asymptotic behavior as those exhibited earlier by Yao and Thomas [2], but are derived here using only real variable methods in conjunction with the signal representation. In case 1), the estimate obtained represents a sharpening of the Yao-Thomas bound for values ofrdose to unity.     

A bound on lightweight sequences with application to definite decoding (Corresp.)

It is shown that the numberMof binary-valuedn-tuples having fractional weightdeltaor less,0 < delta leq frac{1}{3}, such that no twon-tuples agree in anyLconsecutive positions, is bounded by2^{2LH(delta)+1}. A set ofn-tuples is constructed to show that this bound is not likely to be improved upon by any significant factor. This bound is used to show that the ratiod_{DD}/n_{DD}of definite-decoding minimum distance to definite-decoding constraint length is lower bounded byH^{-l}[frac{1}{6} cdot (1 - R)/ (1+R)]asn_{DD}grows without bound.     

A First-Order Markov Model for Understanding Delta Modulation Noise Spectra

A first-order Markov process is used to model the sequence of quantization noise samples in delta modulation. An autocorrelation parameterCin the Markov model controls the shape of the noise spectrum, and asCdecreases from 1 to 0 and then to -1, the spectrum changes from a low-pass to a flat, and then to a high-pass characteristic. One can also use the Markov model to predict the so-called out-of-band noise rejection that is obtained when delta modulation is performed with an oversampled input, and the resulting quantization noise is lowpass filtered to the input band. The noise rejectionGis a function ofCas well as an oversampling factorFand an interesting asymptotic result is thatG=frac{1-C}{1+C} dot FifF gg frac{1+C}{1-C} dot frac{pi}{2}. Delta modulation literature has noted the importance of the specialGvalues,Fand2F. These correspond to autocorrelation values of 0 and -1/3.     

An estimate of the variation of a band-limited process

Upper and lower bounds are established for the mean-square variation of a stationary processX(t)whose power spectrum is bounded byomega_{c}, in terms of its average powerP_{0}and the average powerP_{1}of its derivative. It is shown thatleft( frac{2}{pi} right)^{2} P_{1} tau^{2} leq E {|X(t+tau )-X(t)|^{2}} leq P_{1} tau^{2} leq omega_{c}^{2}P_{0}tau^{2}where the upper bounds are valid for anytauand the lower bound fortau < pi / omega_{c}. These estimates are applied to the mean-square variation of the envelope of a quasi-monochromatic process.