On a new cylindrical harmonic representation for spherical waves

An exact series representation is presented for integrals whose integrands are products of cosine and spherical wave functions, where the argument of the cosine term can be any integral multiple n of the azimuth angle φ. This series expansion is shown to have the following form: I(n)=e^-jkR0/R₀ δ_no-jk Σ_m=1^∞ C(m,n)(k ²ρρ0)/m! h_m⁽²⁾(kR₀)/(kR₀)^m . It is demonstrated that in the special cases n=0 and n=1, this series representation corresponds to existing expressions for the cylindrical wire kernel and the uniform current circular loop vector potential, respectively. A new series representation for spherical waves in terms of cylindrical harmonics is then derived using this general series representation. Finally, a closed-form far-field approximation is developed and is shown to reduce to existing expressions for the cylindrical wire kernel and the uniform current loop vector potential as special cases     

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     

Renyi's divergence and entropy rates for finite alphabet Markovsources

In this work, we examine the existence and the computation of the Renyi divergence rate, lim_n→∞ 1/n D_α (p⁽ⁿ⁾∥q⁽ⁿ⁾), between two time-invariant finite-alphabet Markov sources of arbitrary order and arbitrary initial distributions described by the probability distributions p⁽ⁿ⁾ and q⁽ⁿ⁾, respectively. This yields a generalization of a result of Nemetz (1974) where he assumed that the initial probabilities under p⁽ⁿ⁾ and q⁽ⁿ⁾ are strictly positive. The main tools used to obtain the Renyi divergence rate are the theory of nonnegative matrices and Perron-Frobenius theory. We also provide numerical examples and investigate the limits of the Renyi divergence rate as α→1 and as α↓0. Similarly, we provide a formula for the Renyi entropy rate lim_n→∞ 1/n H _α(p⁽ⁿ⁾) of Markov sources and examine its limits as α→1 and as α↓0. Finally, we briefly provide an application to source coding     

The length of a typical Huffman codeword

If p_i(i=1,···, N) is the probability of the ith letter of a memoryless source, the length l_i of the corresponding binary Huffman codeword can be very different from the value -log p_i. For a typical letter, however, l_i≈-logp_i. More precisely, P_m ^-=Σ/sub j∈{i|l<-logpj-m}/p_j<2^-m and P_m ⁺=Σ/sub j∈{i|li>-logpi+m/}p_j<2^-c(m-2)+2, where c≈2.27     

On the capacity of two-dimensional run-length constrained channels

Two-dimensional binary patterns that satisfy one-dimensional (d, k) run-length constraints both horizontally and vertically are considered. For a given d and k, the capacity C_d,k is defined as C_d,k=lim_m,n→∞log₂N_m,n ^d,k/mn, where N_m,n^d,k denotes the number of m×n rectangular patterns that satisfy the two-dimensional (d,k) run-length constraint. Bounds on C_d,k are given and it is proven for every d⩾1 and every k>d that C_d,k=0 if and only if k=d+1. Encoding algorithms are also discussed     

Eigenvalues of (↓2)H and convergence of the cascade algorithm

This paper is about the eigenvalues and eigenvectors of (↓2)H. The ordinary FIR filter H is a convolution with a vector h=(h(O),...,h(N)), which is the impulse response. The operator (↓2) downsamples the output y=h*x, keeping the even-numbered components y(2n). Where H is represented by a constant-diagonal matrix, this is a Toeplitz matrix with h(k) on its kth diagonal, the odd-numbered rows are removed in (↓2)H. The result is a double shift between rows, yielding a block Toeplitz matrix with 1×2 blocks. Iteration of the filter is governed by the eigenvalues. If the transfer function H(z)=Σh(k)z^-k has a zero of order p at z=-1, corresponding to ω=π, then (↓2)H has p special eigenvalues ½,¼...,(½)^p. We show how each additional “zero at π” divides all eigenvalues by 2 and creates a new eigenvector for λ=½. This eigenvector solves the dilation equation φ(t)=2Σh(k)φ(2t-k) at the integers t=n. The left eigenvectors show how 1,t,...,t^p-1 can be produced as combinations of φ(t-k). The dilation equation is solved by the cascade algorithm, which is an infinite iteration of M=(↓2)2H. Convergence in L² is governed by the eigenvalues of T=(↓2)2HH^T corresponding to the response 2H(z)H(z^-1 ). We find a simple proof of the necessary and sufficient condition for convergence     

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     

Evaluation of the quantization error in denominator-separable 2-Drecursive filters

The evaluation of the quantization error in two-dimensional (2-D) digital filters involves the computation of the infinite square sum J=Σ^∞_m=φΣ ^∞_n=φy² (m, n). A simple method is presented for evaluating J based on partial fraction expansion and using the residue method provided the Z-transform Y(Z₁, Z₂) of the sequence y(m, n) having quadrant support is a causal bounded input, bounded output (BIBO) stable denominator-separable rational function. The value of J is expressed as a sum of simple integrals which can easily be evaluated. The simple integrals are tabulated for ready reference. The proposed method is suitable for analytical as well as numerical computation and can easily be programmed     

A Useful Technique for Interference Analysis in Nakagami Fading

This paper presents a unified analytical method for computing the average E[g(x/(Sigma_k=1 ^K y_k + b))] of some arbitrary function g(.) when x is a gamma random variable and independent of the arbitrary random variables y₁, y₂, ..., y_k. This leads to new explicit expressions for the averages of some specific functions including, erfc(radicz), exp(-z), zⁿ, and In(1 + z), in terms of the moment generating functions of y₁, y₂, ..., y_K.     

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 q-ary image of a qm-ary cyclic code

For (n, q)=1 V a q^m-ary cyclic code of length n and with generator polynomial g(x), we show that there exists a basis for F(q^m) over F_q with respect to which the q-ary image of V is cyclic, if and only if: (i) g(x) is over F_q; or (ii) g(x)=g₀(x)(x-γ^-q(μ)), g₀(x) is over F_q, F_q≠F(q^k)=F_q(γ)⊂F(q^m ), μ an integer modulo k, and w^m-γ has a divisor over F(q^k) of degree e=m/k; or (iii) g(x)=g₀ (x) Π_μϵs(x-γ(-q^μ)), g ₀(x) is over F_q, F_q≠F(q^k)=F_q(γ)⊂F(q^m ), S a set of integers module k of cardinality k-1 and w^m -μ has a divisor over F(q^k) of degree e=m/k. In all of the above cases, we determine all of the bases with respect to which the q-ary image of V is cyclic     

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     

The redundancy of source coding with a fidelity criterion .II.Coding at a fixed rate level with unknown statistics

The redundancy problem of universal lossy source coding at a fixed rate level is considered. Under some condition on the single-letter distortion measure, which implies that the cardinality K of the reproduction alphabet is not greater than the cardinality J of the source alphabet, it is shown that the redundancy of universally coding memoryless sources p by nth-order block codes of rate R goes like |(∂/∂R)d(p,R)|Kln n/2n+o(ln n/n) for all memoryless sources p except a set whose volume goes to 0 as the block length n goes to infinity, where d(p,R) denotes the distortion rate function of p. Specifically, for any sequence {C_n}_n=1^∞ of block codes, where C_n is an nth-order block code at the fixed rate R, and any ϵ>0, the redundancy D_n(C _n,p) of C_n for p is greater than or equal to |(∂/∂R)d(p,R)|(K-ϵ)ln n/2n for all p satisfying some regular conditions except a set whose volume goes to 0 as n→∞. On the other hand, there exists a sequence {C_n}_n=1^∞ of block codes at the rate R such that for any p satisfying some regular conditions, the super limit of D_n(C_n,p)|(ln n/n) is less than or equal to |(∂/∂R)d(p,R)|K/2     

The Viterbi optimal runlength-constrained approximation nonlinearfilter

Simple nonlinear filters are often used to enforce “hard” syntactic constraints while remaining close to the observation data, e.g., in the binary case, it is common practice to employ iterations of a suitable median, or a one-pass recursive median, openclose, or closeopen filter to impose a minimum symbol runlength constraint while remaining “faithful” to the observation. Unfortunately, these filters are-in general-suboptimal. Motivated by this observation, we pose the following optimization: given a finite-alphabet sequence of finite extent y={y(n)}_n=0^N-1 , find a sequence x={x(n)}_n=0^N-1 that minimizes d(x,y)=Σ_n=0^N-1d_n(y(n), x(n)) subject to the following: x is piecewise constant of plateau run-length ⩾M. We show how a suitable reformulation of the problem naturally leads to a simple and efficient Viterbi-type optimal algorithmic solution. We call the resulting nonlinear input-output operator the Viterbi optimal runlength-constrained approximation (VORCA) filter. The method can be easily generalized to handle a variety of local syntactic constraints. The VORCA is optimal, computationally efficient, and possesses several desirable properties (e.g., idempotence); we therefore propose it as an attractive alternative to standard median, stack, and morphological filtering. We also discuss some applications     

有限域上最优码的一种新的构造方法

基于域F_p^m上一类特殊的矩阵,定义了环R(_p^m,k)=F_p^m[u]/k>到F_p^p_mj的一个新的Gray映射,其中u^k=0、p为素数、j为正整数且p^j－1+1≤k≤p^j.得到了环R(_p^m,k)上码长为任意长度N的(1+u)常循环码的Gray象是F_p^m上长为p^jN的保距线性循环码,并给出了Gray象的生成多项式,构造了F₃,F₅和F₇上的一些最优线性循环码.     

On Q of cascaded identical resonators

It is pointed out that the Q of n identical cascaded resonators, Qn, is related to that of each resonator Q0, by the exact relation Qn/Q0= (2^1/n- 1)^-1/2, which is no more complicated than the approximations developed by Mitra and Huey.     

A state space approach to the design of globally optimal FIR energycompaction filters

We introduce a new approach for the least squared optimization of a weighted FIR filter of arbitrary order N under the constraint that its magnitude squared response be Nyquist(M). Although the new formulation is general enough to cover a wide variety of applications, the focus of the paper is on optimal energy compaction filters. The optimization of such filters has received considerable attention in the past due to the fact that they are the main building blocks in the design of principal component filter banks (PCFBs). The newly proposed method finds the optimum product filter F_opt(z)=H_opt(Z)H_opt (z^-1) corresponding to the compaction filter H_opt (z). By expressing F(z) in the form D(z)+D(z^-1), we show that the compaction problem can be completely parameterized in terms of the state-space realization of the causal function D(z). For a given input power spectrum, the resulting filter F_opt(z) is guaranteed to be a global optimum solution due to the convexity of the new formulation. The new algorithm is universal in the sense that it works for any M, arbitrary filter length N, and any given input power spectrum. Furthermore, additional linear constraints such as wavelets regularity constraints can be incorporated into the design problem. Finally, obtaining H_opt(z) from F_opt(z) does not require an additional spectral factorization step. The minimum-phase spectral factor H_min(z) can be obtained automatically by relating the state space realization of D_opt(z) to that of H _opt(z)     

Corrective memory by a symmetric sparsely encoded network

A neural network that retrieves stored binary vectors, when probed by possibly corrupted versions of them, is presented. It employs sparse ternary internal coding and autocorrelation (Hebbian) storage. It is symmetrically structured and, consequently, can be folded into a feedback configuration. Bounds on the network parameters are derived from probabilistic considerations. It is shown that when the input dimension is n, the proportional activation radius is ρ and the network size is 2^νn with ν>1-h₂(ρ), the equilibrium capacity is at least 2^αn/8nρ(1-ρ) for any α<1-h₂(ρ), where h₂(·) is the binary entropy. A similar capacity bound is derived for the correction of errors of proportional size ρ or less, when ρ⩽0.3. The performance of a finite-size symmetric network is examined by simulation and found to exceed, at the cost of higher connectivity, that of the Kanerva (1988) model, operating as a content addressable memory