On ternary complementary sequences

A pair of real-valued sequences A=(a₁,a₂,...,a_N) and B=(b₁,b ₂,...,b_N) is called complementary if the sum R(·) of their autocorrelation functions R_A(·) and R_B(·) satisfies R(τ)=R_A(τ)+R _B(τ)=Σ_i=1^N$ -^τa_ia_i+τ+Σ_j=1 ^N-τb_jb_j+τ=0, ∀τ≠0. In this paper we introduce a new family of complementary pairs of sequences over the alphabet α₃=+{1,-1,0}. The inclusion of zero in the alphabet, which may correspond to a pause in transmission, leads both to a better understanding of the conventional binary case, where the alphabet is α₂={+1,-1}, and to new nontrivial constructions over the ternary alphabet α₃. For every length N, we derive restrictions on the location of the zero elements and on the form of the member sequences of the pair. We also derive a bound on the minimum number of zeros necessary for the existence of a complementary pair of length N over α₃. The bound is tight, as it is met by some of the proposed constructions, for infinitely many lengths     

The Kolmogorov complexity, universal distribution, and codingtheorem for generalized length functions

A function h(w) is said to be useful for the coding theorem if the coding theorem remains to be true when the lengths |w| of codewords w in it are replaced with h(w). For a codeword w=a₀a₁...a_m-1 of length m and an infinite sequence Q=(q₀, q₁, q₂, ...) of real numbers such that 0n⩽½, let |w|_Q denote the value Σ_n=0^m-1 (if a_n =0 then -log₂q_n, else -log₂(1-q _n)), that is, -log₂, (the probability that flippings of coins generate x) assuming that the (i+1)th coin generates a tail (or 0) with probability q_i. It is known that if 0n→∞ q_n then |w|_Q is useful for the coding theorem and if lim_n→∞ q _n/(1/(2ⁿ))=0 then |w|_Q is not useful. We introduce several variations of the coding theorem and show sufficient conditions for h(w) not to be useful for these variations. The usefulness is also defined for the expressions that define the Kolmogorov complexity and the universal distribution. We consider the relation among the usefulness for the coding theorem, that for the Kolmogorov complexity, and that for the universal distribution     

Fast evaluation of an integral occurring in digital filteringapplications

A fast evaluation procedure for the integral I_m,n,p=1/2πj∯_|z|=1H_m,n(z)H _m,n(z^-1)z^p-1dz for arbitrary nonnegative integer-valued m, n, and p, is presented, where H_m,n (z)=Σ_k=0^mb_m,kz^-k /Σ_l=0ⁿa_n,lz^-1,a _n,0≠0 is the transfer function of an arbitrary digital filter. Evaluation of this integral frequently appears in control, communication, and digital filtering. A notable result is the one-term recursion on p, for arbitrary but fixed nonnegative integers m and n. The computational complexity is analyzed, and two illustrative examples demonstrate some of the advantages of this approach     

An entropy theorem for computing the capacity of weakly(d,k)-constrained sequences

We find an analytic expression for the maximum of the normalized entropy -Σ_iϵTp_iln p_i/Σ_iϵTip_i where the set T is the disjoint union of sets S_n of positive integers that are assigned probabilities P_n, Σ_nP_n =1. This result is applied to the computation of the capacity of weakly (d,k)-constrained sequences that are allowed to violate the (d,k)-constraint with small probability     

The dynamics of group codes: state spaces, trellis diagrams, andcanonical encoders

A group code C over a group G is a set of sequences of group elements that itself forms a group under a component-wise group operation. A group code has a well-defined state space Σ_k at each time k. Each code sequence passes through a well-defined state sequence. The set of all state sequences is also a group code, the state code of C. The state code defines an essentially unique minimal realization of C. The trellis diagram of C is defined by the state code of C and by labels associated with each state transition. The set of all label sequences forms a group code, the label code of C, which is isomorphic to the state code of C. If C is complete and strongly controllable, then a minimal encoder in controller canonical (feedbackfree) form may be constructed from certain sets of shortest possible code sequences, called granules. The size of the state space Σ_k is equal to the size of the state space of this canonical encoder, which is given by a decomposition of the input groups of C at each time k. If C is time-invariant and ν-controllable, then |Σ_k|=Π_1⩽j⩽v|F_j/F _j-1|^j, where F₀ ⊆···⊆ Fν is a normal series, the input chain of C. A group code C has a well-defined trellis section corresponding to any finite interval, regardless of whether it is complete. For a linear time-invariant convolutional code over a field G, these results reduce to known results; however, they depend only on elementary group properties, not on the multiplicative structure of G. Moreover, time-invariance is not required. These results hold for arbitrary groups, and apply to block codes, lattices, time-varying convolutional codes, trellis codes, geometrically uniform codes and discrete-time linear systems     

Theoretical analysis of word-level switching activity in thepresence of glitching and correlation

This paper presents a novel analytical approach to compute the switching activity in digital circuits at the word level in the presence of glitching and correlation. The proposed approach makes use of signal statistics such as mean, variance, and autocorrelation. It is shown that the switching activity α_f at the output node f of any arbitrary circuit in the presence of glitching and correlation is computed as α_f=Σ_i=1^S-1α(f _i,i+1)=Σ_i=1^{S- 1}p(f_i+1)(1-p(f_i))(1-ρ(f_i,i+1 )) (1) where ρ(f_i,i+1)=ρ(f_i,i+1)=(E[f_i(Sn)f _i+1(Sn)]- p(f_i)p(f_i+1))/(√(p(f _i)-p(f_i)²)(p(f_i+1)- p(f_i+1²))) (2). S number of time slots in a cycle; ρ(f_i,+1) time-slot autocorrelation coefficient; E[x]=expected value of x; p_x=probability of the signal x being “one”. The switching activity analysis of a signal at the word level is computed by summing the activities of all the individual bits constituting the signal. It is also shown that if the correlation coefficient of the higher order bits of a normally distributed signal x is ρ(x_c), then the bit P₀ where the correlation begins and the correlation coefficient is related hy ρ(x_c)=erfc{(2(P₀-1)-1)/(√2σ_x )} where erfc(x)=complementary error function; σ_x=variance of x. The proposed approach can estimate the switching activity in less than a second which is orders of magnitude faster than simulation-based approaches. Simulation results show that the errors using the proposed approach are about 6.1% on an average and that the approach is well suited even for highly correlated speech and music signals     

Three space-economical algorithms for calculatingminimum-redundancy prefix codes

The minimum-redundancy prefix code problem is to determine, for a given list W=[ω₁,..., ω_n] of n positive symbol weights, a list L=[l₁,...,l_n] of n corresponding integer codeword lengths such that Σ_i=1 ⁿ 2^-li⩽1 and Σ_i=1ⁿ ω_il_i is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m₁,..., m_H], where m_l, for l=1,...,H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min(log(1/p₁),n)), where p₁ is the smallest symbol probability, given by ω₁/Σ _i=1ⁿ ω_i. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H², n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during code calculation, a feature that is very useful in some applications     

Inequalities between entropy and index of coincidence derived frominformation diagrams

To any discrete probability distribution P we can associate its entropy H(P)=-Σp_i ln p_i and its index of coincidence IC(P)=Σp_i². The main result of the paper is the determination of the precise range of the map P→(IC(P), H(P)). The range looks much like that of the map P→(P_max, H(P)) where P_max is the maximal point probability, cf. research from 1965 (Kovalevskij (1965)) to 1994 (Feder and Merhav (1994)). The earlier results, which actually focus on the probability of error 1-P_max rather than P_max, can be conceived as limiting cases of results obtained by methods presented here. Ranges of maps as those indicated are called information diagrams. The main result gives rise to precise lower as well as upper bounds for the entropy function. Some of these bounds are essential for the exact solution of certain problems of universal coding and prediction for Bernoulli sources. Other applications concern Shannon theory (relations between various measures of divergence), statistical decision theory, and rate distortion theory. Two methods are developed. One is topological; the other involves convex analysis and is based on a “lemma of replacement” which is of independent interest in relation to problems of optimization of mixed type (concave/convex optimization)     

Constellations matched to the Rayleigh fading channel

We introduce a new technique for designing signal sets matched to the Rayleigh fading channel, In particular, we look for n-dimensional (n⩾2) lattices whose structure provides nth-order diversity. Our approach is based on a geometric formulation of the design problem which in turn can be solved by using a number-geometric approach. Specifically, a suitable upper bound on the pairwise error probability makes the design problem tantamount to the determination of what is called a critical lattice of the body S={x=(x₁, ···, x_n)∈Rⁿ, |Π_i=1ⁿx_i|⩽1}. The lattices among which we search for an optimal solution are the standard embeddings in R ⁿ of the number ring of some totally real number field of degree n over Q. Simulation results confirm that this approach yields lattices with considerable coding gains     

Erasure, list, and detection zero-error capacities for low noiseand a relation to identification

For the discrete memoryless channel (χ, y, W) we give characterizations of the zero-error erasure capacity C_er and the zero-error average list size capacity C_al in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not “single-letterize.” Next we assume that χ⊂y and W(x|x)>0 for all x∈χ, and we associate with W the low-noise channel W_ϵ, where for y ⁺(x)={y:W(y|x)>0} W_ϵ(y|x)={1, if y=x and |y⁺(x)|=1 1-ϵ, if y=x and |y⁺(x)|>1 e/|y ⁺(x)|-1, if y≠x. Our Theorem-2 says that as ε tends to zero the capacities C_er(W_ε) and C_al (W_ε) relate to the zero-error detection capacity C _de(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C_oid for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C_oid equals the zero-error erasure capacity for transmission C_er     

An inequality on guessing and its application to sequentialdecoding

Let (X,Y) be a pair of discrete random variables with X taking one of M possible values, Suppose the value of X is to be determined, given the value of Y, by asking questions of the form “Is X equal to x?” until the answer is “Yes”. Let G(x|y) denote the number of guesses in any such guessing scheme when X=x, Y=y. We prove that E[G(X|Y)^ρ]⩾(1+lnM)^-ρΣ_y [Σ_xP_X,Y(x,y)^1/1+ρ] ^1+ρ for any ρ⩾0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X|Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X|Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets     

Wide-sense and strict-sense nonblocking operation of multicastmulti-log2 n switching networks

Multicast connections are used in broad-band switching networks as well as in parallel processing. We consider wide-sense and strict-sense nonblocking conditions for multi-log₂ N switching networks with multicast connections. We prove that such networks are wide-sense nonblocking if they are designed by vertically stacking at least t · 2^n-t-1 + 2 ^n-2t-1 planes of a log₂ N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2^t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2^n-t-1 + 1 and 2^t + (n - t - 1) · 2^n-t-1 - 2^2t-n-1 + 1, respectively. In the case of strict-sense nonblocking switching networks, the number of planes is at least N/2. The results obtained in this paper show that in many cases number of planes in wide-sense nonblocking switching networks is less than those for t = [n/2] considered by Tscha and Lee (see ibid., vol.47, p.1425-31, Sept. 1999). The number of planes given in the paper is the minimum number of planes needed for wide-sense nonblocking operation provided that Algorithm 1 is used for setting up connections. The minimum number of planes for such operation in general is still open issue     

Theoretical and experimental investigation of rhodamine B-dopedpolymer optical fiber amplifiers

High-power (620 W) and high-gain (28 dB) amplification was achieved by a rhodamine B (RB)-doped GI polymer-optical fiber amplifier (POFA) with a l-m length. A theoretical analysis of the amplification in the RE-doped GI POFA was carried out using the rate equation for the fast three level system. The calculated gain behaviour reasonably fit the experimental data. The possibility of higher power (more than 620 W) and higher gain (more than 28 dB) amplification covering a wide range in the visible region is shown from the calculation. Absorption and emission cross sections of RE in poly(methyl methacrylate) bulk were determined and used in the calculation. The values of the cross sections (σ_{a max}=3.4·10^-20m² ,σ_{e max}=3.4·10^-20 m ²) were approximately 10,000 times larger than those of Er ³⁺ in GeO₂-SiO₂ glass     

Feedback capacity of the first-order moving average Gaussian channel

Despite numerous bounds and partial results, the feedback capacity of the stationary nonwhite Gaussian additive noise channel has been open, even for the simplest cases such as the first-order autoregressive Gaussian channel studied by Butman, Tiernan and Schalkwijk, Wolfowitz, Ozarow, and more recently, Yang, Kavccaronicacute, and Tatikonda. Here we consider another simple special case of the stationary first-order moving average additive Gaussian noise channel and find the feedback capacity in closed form. Specifically, the channel is given by Y_i=X_i+Z_i, i=1,2,..., where the input {X _i} satisfies a power constraint and the noise {Z_i} is a first-order moving average Gaussian process defined by Z_i=alphaU_i-1+U_i, |alpha|les 1, with white Gaussian innovations U_i, i=0,1,.... We show that the feedback capacity of this channel is C_FB=-log x₀ where x₀ is the unique positive root of the equation rhox²=(1-x²)(1-|alpha|x)² and rho is the ratio of the average input power per transmission to the variance of the noise innovation U_i. The optimal coding scheme parallels the simple linear signaling scheme by Schalkwijk and Kailath for the additive white Gaussian noise channel-the transmitter sends a real-valued information-bearing signal at the beginning of communication and subsequently refines the receiver's knowledge by processing the feedback noise signal through a linear stationary first-order autoregressive filter. The resulting error probability of the maximum likelihood decoding decays doubly exponentially in the duration of the communication. Refreshingly, this feedback capacity of the first-order moving average Gaussian channel is very similar in form to the best known achievable rate for the first-order autoregressive Gaussian noise channel given by Butman     

Large purely refractive nonlinear index of single crystal P-toluenesulphonate (PTS) at 1600 nm

Z-scan measurements at 1600 nm on single-crystal PTS (p-toluene sulfonate) with single, 65 ps pulses gave a complex nonlinear refractive index coefficient of n₂=2.2(±0.3)×10^-12 cm²/W at 1 GW/cm² and α₂<0.5 cm/GW. This is the first highly nonlinear, organic material to satisfy the conditions imposed by the figures of merit     

Two-dimensional weight-constrained codes through enumeration bounds

For a rational α∈(0,1), let 𝒜_n×m,α be the set of binary n×m arrays in which each row has Hamming weight αm and each column has Hamming weight αn, where αm and αn are integers. (The special case of two-dimensional balanced arrays corresponds to α=1/2 and even values for n and m.) The redundancy of 𝒜_n×m,α is defined by ρ_n×m,α=nmH(α)-log₂|𝒜 _n×m,α| where H(x)=-xlog₂x-(1-x)log₂(1-x). Bounds on ρ_n×m,α are obtained in terms of the redundancies of the sets 𝒜_ℒ,α of all binary ℒ-vectors with Hamming weight αℒ, ℒ∈{n,m}. Specifically, it is shown that ρ_n×m,α⩽nρ_m,α+mρ _n,α where ρ_ℒ,α=ℒH(α)-log₂|𝒜 _ℒ,α| and that this bound is tight up to an additive term O(n+log m). A polynomial-time coding algorithm is presented that maps unconstrained input sequences into 𝒜_n×m,α at a rate H(α)-(ρ_m,α/m)     

Capacity of the Gaussian arbitrarily varying channel

The Gaussian arbitrarily varying channel with input constraint Γ and state constraint Λ admits input sequences x=(x₁,---,X_n) of real numbers with Σx_i²⩽nΓ and state sequences s=(S₁,---,s_n ) of real numbers with Σs_i²⩽nΛ; the output sequence x+s+V, where V=(V₁,---,V_n) is a sequence of independent and identically distributed Gaussian random variables with mean 0 and variance σ². It is proved that the capacity of this arbitrarily varying channel for deterministic codes and the average probability of error criterion equals 1/2 log (1+Γ/(Λ+σ²)) if Λ<Γ and is 0 otherwise     

Minimum bias multiple taper spectral estimation

Two families of orthonormal tapers are proposed for multitaper spectral analysis: minimum bias tapers, and sinusoidal tapers {υ ^{(k/)}, where υ}sub n//sup (k/)=√(2/(N+1))sin(πkn/N+1), and N is the number of points. The resulting sinusoidal multitaper spectral estimate is Sˆ(f)=(1/2K(N+1))Σ_j=1^K |y(f+j/(2N+2))-y(f-j/(2N+2))|², where y(f) is the Fourier transform of the stationary time series, S(f) is the spectral density, and K is the number of tapers. For fixed j, the sinusoidal tapers converge to the minimum bias tapers like 1/N. Since the sinusoidal tapers have analytic expressions, no numerical eigenvalue decomposition is necessary. Both the minimum bias and sinusoidal tapers have no additional parameter for the spectral bandwidth. The bandwidth of the jth taper is simply 1/N centered about the frequencies (±j)/(2N+2). Thus, the bandwidth of the multitaper spectral estimate can be adjusted locally by simply adding or deleting tapers. The band limited spectral concentration, ∫_-w^w|V(f)|²df of both the minimum bias and sinusoidal tapers is very close to the optimal concentration achieved by the Slepian (1978) tapers. In contrast, the Slepian tapers can have the local bias, ∫_-½^½f ²|V(f)|²df, much larger than of the minimum bias tapers and the sinusoidal tapers     

Tight upper bounds on the redundancy of Huffman codes

Bounds on the redundancy of Huffman codes in terms of the probability p₁ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2^l+1+1)<p₁<1/(2^l-1), l⩾2. It is shown that the new bounds are the tightest possible for these intervals