On the survival of sequence information in filters (Corresp.)

Given a binary data streamA = {a_i}_{i=o}^inftyand a filterFwhose output at timenisf_n = sum_{i=0}^{n} a_i beta^{n-i}for some complexbeta neq 0, there are at most2^{n +1)distinct values off_n. These values are the sums of the subsets of{1,beta,beta^2,cdots,beta^n}. It is shown that all2^{n+1}sums are distinct unlessbetais a unit in the ring of algebraic integers that satisfies a polynomial equation with coefficients restricted to +1, -1, and 0. Thus the size of the state space{f_n}is2^{n+1}ifbetais transcendental, ifbeta neq pm 1is rational, and ifbetais irrational algebraic but not a unit of the type mentioned. For the exceptional values ofbeta, it appears that the size of the state space{f_n}grows only as a polynomial innifmidbetamid = 1, but as an exponentialalpha^nwith1 < alpha < 2ifmidbetamid neq 1.     

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.     

Some cross correlation properties for distorted signals

For a nondecreasing distortion characteristicphi(cdot)and a given signalx(cdot), the "cross correlation" function defined byR_{phi} (tau) triangleq int_{-infty}^{infty} phi[x(t)]x(t - tau) dtis shown to satisfy the inequalityR_{phi}(tau) leq R_{phi}(0), for alltau, generalizing an earlier result of Richardson that requiredphi(cdot)to be continuous and strictly increasing. The methods of the paper also show that, under weak conditions, begin{equation} R_{phi,psi}(tau) triangleq int_{-infty}^{infty} phi[x(t)]psi[x(t - tau)] dt leq R_{phi,psi}(0) end{equation} whenpsiis strictly increasing andphiis nondecreasing. In the case of hounded signals (e.g., periodic functions), the appropriate cross correlation function is begin{equation} mathcal{R}_{phi,psi}(tau} triangleq lim_{T rightarrow infty} (2T)^{-l} int_{-T}^T phi[x(t)]psi[x(t - tau)] dt. end{equation} For this case it is shown thatmathcal{R}_{phi,psi} (tau) leq mathcal{R}_{phi,psi}(0)for any nondecreasing (or nonincreasing) distortion functionsphiandpsi. The result is then applied to generalize an inequality on correlation functions for periodic signals due to Prosser. Noise signals are treated and inequalities of a similar nature are obtained for ensemble-average cross correlation functions under suitable hypotheses on the statistical properties of the noise. Inequalities of this type are the basis of a well-known method of estimating the unknown time delay of an observed signal. The extension to nondecreasing discontinuous distortion functions allows the use of hard limiting or quantization to facilitate the cross correlation calculation.     

On the distribution of de Bruijn sequences of given complexity

The distributiongamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and fork geq 3, gamma (2^{2k} - 1,2k) equiv 0 pmod{l6}. It is also shown thatgamma (c, n) equiv 0 pmod{4}for allc, andn geq 3such thatcnis even.     

Electromagnetic reflection from an extended turbulent medium: Cumulative forward-scatter single-backscatter approximation

The backscatter cross sectionQfor high-frequency irradiated turbulent dielectric media, many mean free pathsL_{1}wide, is computed. The lengthL_{1}is the distance into the medium over which the mean electric field decreases in amplitude by a factore^{-1}. Previous calculations have always been restricted toL ll L_{1}. It is found thatQincreases from the Born approximationQ = Q_{1}for medium widthL ll L_{1}toQ = 2Q_{1}forL gg L_{1}, and the theory is valid as long asL ll (kL_{0})^{5/3} L_{1}, a significant improvement over the Born approximation, when the macroscaleL_{0}is much larger than the wavelength2_{pi}k^{-1}. The improvement is due to incorporation of the dominant effects of cumulative forward scattering in the local electric field in the medium. A rigorous and a heuristic derivation are given. The transitional behavior is discussed and a simple physical interpretation is given.     

Far-field approximations to the Kirchoff-Helmholtz representations of scattered fields

The standard far-field approximation to the Kirchhoff formula for the field scattered by a flat metallic plateSof arbitrary shape is given by a certain surface (double) integral. This double integral can be reduced to a line integral evaluated around the boundary of S. Moreover, ifSis a polygon, this line integral can be reduced to a closed form expression involving no integrations at all. The use of such line integral representations can easily reduce the costs of numerical calculation by orders of magnitude. If the integrands are to be sampledptimes per wavelength to achieve an acceptable degree of precision, and ifAis the area ofS, then the numerical evaluation of the double integral requiresp^{2}A/lambda^{2}functional evaluations whereas the line integral only requirespsqrt{A/lambda^{2}}. IfSis a polygon withNvertices, then only2Nfunctional evaluations are required to evaluate the closed form expression with no quadrature error at all.     

A new approach to the problem of wave fluctuations in localized smoothly varying turbulence

In the past, smoothly varying turbulence has been studied by changing the structure constant to the functionC_{n}^{2}(bar{r}). The purpose of this paper is to show that this approach is insufficient, and that a random process developed by Silverman can be used to describe the wave fluctuations in localized smoothly varying turbulence. The localized turbulence is characterized by a correlation function which is a product of a function of the average coordinate and a function of the difference coordinate. The corresponding spectrum is also given by a product of a function of the difference wavenumber and a function of the average wavenumber. They are related to each other through two Fourier transform pairs. Making use of the preceding representations, the fluctuations of a wave propagating through such a turbulence can be given either by the integrals with respect to the two wavenumbers or by a convolution integral of the structure constantC_{n}^{2}(bar{r}) and a function involving the outer scale of the turbulenceL_{0}. It is shown that for a plane wave case, if the distanceLis within (L_{0}^{2}/lambda), then the usual formula given by Tatarski is valid. But if the distance is betweenL_{0}^{2}/lambdaand(bL_{0})/lambdawherebis the total transverse size of the turbulence, the variance of the wave is nearly constant, and ifL gg (bL_{0})/lambda, the variance decays asL^{-2}. Similar conclusions are shown for a spherical wave case. Some examples are shown illustrating the effectiveness of this method.     

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

It is shown thatsqrt[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Sincesqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, wheresqrt{2}is inGF(F_{2})=GF(17), is given.     

On single-sample robust detection of known signals with additive unknown-mean amplitude-bounded random interference--II: The randomized decision rule solution (Corresp.)

A randomized decision rule is derived and proved to be the saddlepoint solution of the robust detection problem for known signals in independent unknown-mean amplitude-bounded noise. The saddlepoint solutionphi^{0}uses an equaUy likely mixed strategy to chose one ofNBayesian single-threshold decision rulesphi_{i}^{0}, i = 1,cdots , Nhaving been obtained previously by the author. These decision rules are also all optimal against the maximin (least-favorable) nonrandomized noise probability densityf_{0}, wheref_{0}is a picket fence function withNpickets on its domain. Thee pair(phi^{0}, f_{0})is shown to satisfy the saddlepoint condition for probability of error, i.e.,P_{e}(phi^{0} , f) leq P_{e}(phi^{0} , f_{0}) leq P_{e}(phi, f_{0})holds for allfandphi. The decision rulephi^{0}is also shown to be an eqoaliir rule, i.e.,P_{e}(phi^{0}, f ) = P_{e}(phi^{0},f_{0}), for allf, with4^{-1} leq P_{e}(phi^{0},f_{0})=2^{-1}(1-N^{-1})leq2^{-1} , N geq 2. Thus nature can force the communicator to use an {em optimal} randomized decision rule that generates a large probability of error and does not improve when less pernicious conditions prevail.     

Size Dependence of Surface-Roughness-Limited Mobility in Silicon-Nanowire FETs

Lateral size effects on surface-roughness-limited mobility in silicon-nanowire FETs are analyzed by means of a full-quantum 3-D self-consistent simulation. A statistical analysis is carried out by considering different realizations of the potential roughness at the Si–$hbox{SiO}_{2}$ interfaces. Nanowires with lateral section varying from $hbox{3} times hbox{3}$ to $hbox{7} times hbox{7} hbox{nm}^{2}$ are considered. Effective mobility is computed by evaluating the electron density in a reduced channel region to eliminate parasitic effects from contacts. It is found that transport in wires with the smallest section is dominated by scattering due to potential fluctuations, resulting in a larger standard deviation of the effective mobility, whereas it is dominated by transverse-mode coupling in wires with larger section, resulting in a stronger influence of surface roughness at high gate voltages.      

Complexity-based induction systems: Comparisons and convergence theorems

In 1964 the author proposed as an explication of {em a priori} probability the probability measure induced on output strings by a universal Turing machine with unidirectional output tape and a randomly coded unidirectional input tape. Levin has shown that iftilde{P}'_{M}(x)is an unnormalized form of this measure, andP(x)is any computable probability measure on strings,x, thentilde{P}'_{M}geqCP(x)whereCis a constant independent ofx. The corresponding result for the normalized form of this measure,P'_{M}, is directly derivable from Willis' probability measures on nonuniversal machines. If the conditional probabilities ofP'_{M}are used to approximate those ofP, then the expected value of the total squared error in these conditional probabilities is bounded by-(1/2) ln C. With this error criterion, and when used as the basis of a universal gambling scheme,P'_{M}is superior to Cover's measurebast. WhenHastequiv -log_{2} P'_{M}is used to define the entropy of a rmite sequence, the equationHast(x,y)= Hast(x)+H^{ast}_{x}(y)holds exactly, in contrast to Chaitin's entropy definition, which has a nonvanishing error term in this equation.     

Comments on "A Two-Stage Rearrangeable Broadcast Switching Network"

It is shown that a result achieved in the above paper is not applicable without constraints. The statement thatn_{2} = 13in the case ofM = 3ifsqrt{N_{1}}is, at least, 6 is not always correct. Ifsqrt{N_{1}}is a multiple of 5,n_{2}= 12, and ifsqrt{N_{1}}is a multiple of 4,n_{2} = 11.     

Fast evaluation of logarithms in fields of characteristic two

A method for determining logarithms in GF(2^{n})is presented. Its asymptotic running time isO(exp (cn^{1/3} log^{2/3} n))for a small constantc, while, by comparison, Adleman's scheme runs in timeO(exp (c^{'}n^{1/2} log^{1/2} n )). The ideas give a dramatic improvement even for moderate-sized fields such as GF(2^{127}), and make (barely) possible computations in fields of size around2^{400}. The method is not applicable to GF(q)for a large primeq.     

The geometry of quadrics and correlations of sequences (Corresp.)

Nondegenerate quadrics of PG(2l, 2^{s})have been used to construct ternary sequences of length(2^{2sl+1} - 1)/(2^{s} - 1)with perfect autocorrelation function. The same construction can be used for degenerate quadrics for this case as well as quadrics of PG(N,q), withNarbitrary andq = p^{s}, for any primep. This is possible because it is shown that ifQ subseteq {rm PG} (N, q)is a quadric, possibly degenerate, that has the same size as a hyperplane, then, providedQitself is not a hyperplane, the hyperplanes of PG(N,q)intersectQin three sizes. These sizes depend on whetherNis even or odd and the degeneracy ofQ. Finally, a connection to maximum period linear recursive sequences is made.     

On the inequivalence of generalized Preparata codes

Ifmis odd andsigma /in Aut GF(2^{m})is such thatx rightarrow x^{sigma^{2}-1}is1-1, there is a[2^{m+1}-1,2^{m+l}-2m-2]nonlinear binary codeP(sigma)having minimum distance 5. All the codesP(sigma)have the same distance and weight enumerators as the usual Preparata codes (which rise asP(sigma)whenx^{sigma}=x^{2}). It is shown thatP(sigma)andP(tau)are equivalent if and only iftau=sigma^{pm 1}, andAut P(sigma)is determined.     

Some periodic convolutional codes better than any fixed code (Corresp.)

Some(n_{o}=2; k_{o}=1)noncatastrophic periodic convolutional codes with memoryM=4are given that have the same free distance,d_{infty}, as the best fixed code but have both a smaller number of paths of weightd_{infty}per time instant and a smaller average number of information bit errors per such path for periodsT=2, 3, 4, and5. It is also shown that an(n_{0}, k_{0})code of periodTis equivalent to a fixed code with parameters(Tn_{0}, Tk_{0}).     

The distribution of gains in uniformly multiplying avalanche photodiodes: Theory

Expressions are derived for the probabilityP_{n,m}that a pulse initiated bynelectrons (or holes) in a uniformly multiplying semiconductor diode will result in a total number of electrons (or holes)m, to give a gainm/n, and for the probabilityQ_{n,m}that the gain will bem/nor greater. It is shown that the distributions are far from Gaussian. The gain distributionP_{1,m}for a single photoelectron, for example, is shown to have a maximum value form = 1for any value of the average gainM=m/n. The derivations are valid for any electric field distribution and assume only that the hole ionization coefficientbeta(E) can be approximated by the relationbeta(E) =kalpha(E), wherealpha(E)is the electron ionization coefficient andkis a constant. A method of determining an effective value ofk, for cases wherebeta=kalphais not a good approximation, is presented. The results can be used to calculate the average gain and the mean square deviation from the average, giving results in agreement with previously published relations [1], [2]. The implications of this theory on the use of avalanche diodes for low-level photodetection are discussed. It is shown that in the near infrared, cooled avalanche photodiodes can compare favorably with the best available photomultiplier when used either in a photon-counting mode, or for the reliable detection of low-level laser pulses.     

Sliding-block coding for weakly continuous channels

For a weakly continuous stationary channel with operational sliding-block capacityC_{s}, it is shown that every stationary, ergodic, aperiodic source with entropy less thanC_{s}is sliding-block transmissible over the channel. It had been shown earlier that a stationary and ergodic source is block transmissible over the channel if its entropy is less than the operational block capacityC_{b}. If, in addition, the channel is ergodic, it is shown thatC_{s}=C_{b}. An example of a nonergodic weakly continuous channel is given for which0.     

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.     

Narrow-band systems and Gaussianity

The approach to Gaussianity of the outputy(t)of a narrow-band systemh(t)is investigated. It is assumed that the inputx(t)is ana-dependent process, in the sense that the random variablesx(t)andx(t + u)are independent foru > a. WithF(y)andG(y)the distribution functions ofy(t)and of a suitable normal process, a realistic boundBon the differenceF(y) -- G(y)is determined, and it is shown thatB rightarrow 0as the bandwidthomega_oof the system tends to zero. In the special case of the shot noise process begin{equation} y(t) = sum_i h(t - t_i) end{equation} it is shown that begin{equation} mid F(y) - G(y) mid < (omega_o/lambda) frac{1}{2} end{equation} wherelambda_iis the average density of the Poisson pointst_i.