A class of 1-generator quasi-cyclic codes

If R = F/sub q/[x/spl rceil/]/(x/sup m/ - 1), S = F/sub qn/[x]/(x/sup m/ - 1), we define the mapping a_(x) /spl rarr/ A(x) =/spl sigma//sub 0//sup n-1/a/sub i/(x)/spl alpha//sub i/ from R/sup n/ onto S, where (/spl alpha//sub 0/, /spl alpha//sub i/,..., /spl alpha//sub n-1/) is a basis for F/sub qn/ over F/sub q/. This carries the q-ray 1-generator quasicyclic (QC) code R a_(x) onto the code RA(x) in S whose parity-check polynomial (p.c.p.) is defined as the monic polynomial h(x) over F/sub q/ of least degree such that h(x)A(x) = 0. In the special case, where gcd(q, m) = 1 and where the prime factorizations of x/sub m/ 1 over F/sub q/ and F/sub qn/ are the same we show that there exists a one-to-one correspondence between the q-ary 1-generator quasis-cyclic codes with p.c.p. h(x) and the elements of the factor group J* /I* where J is the ideal in S with p.c.p. h(x) and I the corresponding quantity in R. We then describe an algorithm for generating the elements of J*/I*. Next, we show that if we choose a normal basis for F/sub qn/ over F/sub q/, then we can modify the aforementioned algorithm to eliminate a certain number of equivalent codes, thereby rending the algorithm more attractive from a computational point of view. Finally in Section IV, we show how to modify the above algorithm in order to generate all the binary self-dual 1-generator QC codes.     

Random properties of the highest level sequences of primitive sequences over Z(2/sup e/)

Using the estimates of the exponential sums over Galois rings, we discuss the random properties of the highest level sequences /spl alpha//sub e-1/ of primitive sequences generated by a primitive polynomial of degree n over Z(2/sup e/). First we obtain an estimate of 0, 1 distribution in one period of /spl alpha//sub e-1/. On the other hand, we give an estimate of the absolute value of the autocorrelation function |C/sub N/(h)| of /spl alpha//sub e-1/, which is less than 2/sup e-1/(2/sup e-1/-1)/spl radic/3(2/sup 2e/-1)2/sup n/2/+2/sup e-1/ for h/spl ne/0. Both results show that the larger n is, the more random /spl alpha//sub e-1/ will be.     

Cyclic codes over GR(4/sup m/) which are also cyclic over /spl Zopf//sub 4/

Let GR(4/sup m/) be the Galois ring of characteristic 4 and cardinality 4/sup m/, and /spl alpha/_={/spl alpha//sub 0/,/spl alpha//sub 1/,...,/spl alpha//sub m-1/} be a basis of GR(4/sup m/) over /spl Zopf//sub 4/ when we regard GR(4/sup m/) as a free /spl Zopf//sub 4/-module of rank m. Define the map d/sub /spl alpha/_/ from GR(4/sup m/)[z]/(z/sup n/-1) into /spl Zopf//sub 4/[z]/(z/sup mn/-1) by d/spl alpha/_(a(z))=/spl Sigma//sub i=0//sup m-1//spl Sigma//sub j=0//sup n-1/a/sub ij/z/sup mj+i/ where a(z)=/spl Sigma//sub j=0//sup n-1/a/sub j/z/sup j/ and a/sub j/=/spl Sigma//sub i=0//sup m-1/a/sub ij//spl alpha//sub i/, a/sub ij//spl isin//spl Zopf//sub 4/. Then, for any linear code C of length n over GR(4/sup m/), its image d/sub /spl alpha/_/(C) is a /spl Zopf//sub 4/-linear code of length mn. In this article, for n and m being odd integers, it is determined all pairs (/spl alpha/_,C) such that d/sub /spl alpha/_/(C) is /spl Zopf//sub 4/-cyclic, where /spl alpha/_ is a basis of GR(4/sup m/) over /spl Zopf//sub 4/, and C is a cyclic code of length n over GR(4/sup m/).     

Deconvolving multivariate kernel density estimates from contaminated associated observations

We consider the estimation of the multivariate probability density function f(x/sub 1/,...,x/sub p/) of X/sub 1/,...,X/sub p/ of a stationary positively or negatively associated (PA or NA) random process {X/sub i/}/sub i=1//sup /spl infin// from noisy observations. Both ordinary smooth and super smooth noise are considered. Quadratic mean and asymptotic normality results are established.     

Time-frequency localisation of Shannon wavelet packets

It is well known that the 2/spl pi/ minimally supported frequency scaling function /spl phi//sup /spl alpha//(x) satisfying /spl phi//spl circ//sup /spl alpha//(/spl omega/)=/spl chi//sub (-/spl alpha/,2/spl pi/-/spl alpha/)/(/spl omega/), 0相似文献   

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.     

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相似文献   

Characterization of accumulation layer capacitance for extracting data on high-/spl kappa/ gate dielectrics

A new parameter extraction technique has been outlined for high-/spl kappa/ gate dielectrics that directly yields values of the dielectric capacitance C/sub di/, the accumulation layer surface potential quotient, /spl beta//sub acc/, the flat-band voltage, the surface potential /spl phi//sub s/, the dielectric voltage, the channel doping density and the interface charge density at flat-band. The parallel capacitance, C/sub p/(=C/sub sc/+C/sub it/), was found to be an exponential function of /spl phi//sub s/ in the strong accumulation regime, for seven different high-/spl kappa/ gate dielectrics. The slope of the experimental lnC/sub p/(/spl phi//sub s/) plot, i.e., |/spl beta//sub acc/|, was found to depend strongly on the physical properties of the high-/spl kappa/ dielectric, i.e., was inversely proportional to [(/spl phi//sub b/m/sup *//m)/sup 1/2/K/C/sub di/], where /spl phi//sub b/ is the band offset, and m/sup */ is the effective tunneling mass. Extraction of /spl beta//sub acc/ represented an experimental carrier confinement index for the accumulation layer and an experimental gate-dielectric direct-tunneling current index. /spl beta//sub acc/ may also be an effective tool for monitoring the effects of post-deposition annealing/processing.     

Entropy and the law of small numbers

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.     

On The General Relation Between /spl alpha/ and Q (Correspondence)

The relation between the quality factor Q and the attenuation constant /spl alpha/ of a transmission line has been known as follows: /spl alpha/ = /spl beta/ / /2Q where /spl beta/ is the phase constant. Recently from the following relation of propagation constant at resonance /spl Gamma/(/spl omega//sub 0/) + /spl part//spl Gamma/ / /spl part//spl omega/ /spl Delta//spl omega//spl cong/ i/spl beta/(/spl omega//sub 0/), where /spl Gamma/(/spl omega//sub 0/) = /spl alpha/(/spl omega//sub 0/) + i/spl beta/(/spl omega//sub 0/). Yeh derived a general relation between Q and /spl alpha/, namely, /spl alpha/ = /spl upsi//sub p/ / /spl upsi//sub g/ /spl beta/ / /2Q where /spl upsi//sub p/, and /spl upsi//sub g/ are the phase velocity and group velocity of the wave respectively. This general relation can be derived very simply from the generally accepted definition of /spl alpha/ and Q.     

A critical analysis on global convergence of Hopfield-type neural networks

This paper deals with the global convergence and stability of the Hopfield-type neural networks under the critical condition that M/sub 1/(/spl Gamma/)=L/sup -1/D/spl Gamma/-(/spl Gamma/W+W/sup T//spl Gamma/)/(2) is nonnegative for any diagonal matrix /spl Gamma/, where W is the weight matrix of the network, L=diag{L/sub 1/,L/sub 2/,...,L/sub N/} with L/sub i/ being the Lipschitz constant of g/sub i/ and G(u)=(g/sub 1/(u/sub 1/),g/sub 2/(u/sub 2/),...,g/sub N/(u/sub N/))/sup T/ is the activation mapping of the network. Many stability results have been obtained for the Hopfield-type neural networks in the noncritical case that M/sub 1/(/spl Gamma/) is positive definite for some positive definite diagonal matrix /spl Gamma/. However, very few results are available on the global convergence and stability of the networks in the critical case. In this paper, by exploring two intrinsic features of the activation mapping, two generic global convergence results are established in the critical case for the Hopfield-type neural networks, which extend most of the previously known globally asymptotic stability criteria to the critical case. The results obtained discriminate the critical dynamics of the networks, and can be applied directly to a group of Hopfield-type neural network models. An example has also been presented to demonstrate both theoretical importance and practical significance of the critical results obtained.     

Order statistics from a logistic distribution and applications to survival and reliability analysis

Joint moments involving arbitrary powers of order statistics are the main concern. Consider order statistics u/sub 1/ /spl les/ u/sub 2/ /spl les/ /spl middot//spl middot//spl middot/ /spl les/ u/sub k/ coming from a simple random sample of size n from a real continuous population where u/sub 1/ = x/sub r(1):n/ is order-statistic #r/sub 1/, u/sub 2/ = x/sub r(1)+r(2):n/ is order statistic #(r/sub 1/ + r/sub 2/), et al., and u/sub k/ = x/sub r(1)+/spl middot//spl middot//spl middot/+r(k):n/ is order statistic #(r/sub 1/ +/spl middot//spl middot//spl middot/+ r/sub k/). Product moments are examined of the type E[u/sub 1//sup /spl alpha/(1)/ /spl middot/ u/sub 2//sup /spl alpha/(2)//sub /spl middot/ /spl middot//spl middot//spl middot//spl middot//u/sub k//sup /spl alpha/(k)/] where /spl alpha//sub 1/, ..., /spl alpha//sub k/ are arbitrary quantities that might be complex numbers, and E[/spl middot/] denotes the s-expected value. Some explicit evaluations are considered for a logistic population. Detailed evaluations of all integer moments of u/sub 1/ and recurrence relations, recurring only on the order of the moments, are given. Connections to survival functions in survival analysis, hazard functions in reliability situations, real type-1, type-2 /spl beta/ and Dirichlet distributions are also examined. Arbitrary product moments for the survival functions are evaluated. Very general results are obtained which can be used in many problems in various areas.     

The empirical distribution of rate-constrained source codes

Let X = (X/sub 1/,...) be a stationary ergodic finite-alphabet source, X/sup n/ denote its first n symbols, and Y/sup n/ be the codeword assigned to X/sup n/ by a lossy source code. The empirical kth-order joint distribution Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rceil/(x/sup k/,y/sup k/) is defined as the frequency of appearances of pairs of k-strings (x/sup k/,y/sup k/) along the pair (X/sup n/,Y/sup n/). Our main interest is in the sample behavior of this (random) distribution. Letting I(Q/sup k/) denote the mutual information I(X/sup k/;Y/sup k/) when (X/sup k/,Y/sup k/)/spl sim/Q/sup k/ we show that for any (sequence of) lossy source code(s) of rate /spl les/R lim sup/sub n/spl rarr//spl infin//(1/k)I(Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor/) /spl les/R+(1/k)H (X/sub 1//sup k/)-H~(X) a.s. where H~(X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d.). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor//spl rArr//sup d/P(X/sup k/,Y~/sup k/) a.s. whenever P(/sub X//sup k//sub ,Y//sup k/) is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers.     

A note on density model size testing

Let (F/sub k/)/sub k/spl ges/1/ be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to F/sub k//sup */, where k/sup */ is the unknown smallest integer such that f/spl isin/F/sub k/. Given a random sample X/sub 1/,...,X/sub n/ drawn from f, an integer k/sub 0//spl ges/1 and a real number /spl alpha//spl isin/(0,1), we introduce a new, simple, explicit /spl alpha/-level consistent testing procedure of the hypothesis {H/sub 0/:k/sup */=k/sub 0/} versus the alternative {H/sub 1/:k/sup *//spl ne/k/sub 0/}. Our method is inspired by the combinatorial tools developed in Devroye and Lugosi and it includes a wide range of density models, such as mixture models, neural networks, or exponential families.     

Grammar-based lossless universal refinement source coding

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).     

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.     

Near-ellipsoidal Voronoi coding

We consider a special case of Voronoi coding, where a lattice /spl Lambda/ in /spl Ropf//sup n/ is shaped (or truncated) using a lattice /spl Lambda/'={(m/sub 1/x/sub 1/,...,m/sub n/x/sub n/)|(x/sub 1/,...,x/sub n/)/spl isin//spl Lambda/} for a fixed m_=(m/sub 1/,...,m/sub n/)/spl isin/(/spl Nopf//spl bsol/{0,1})/sup n/. Using this technique, the shaping boundary is near-ellipsoidal. It is shown that the resulting codes can be indexed by standard Voronoi indexing algorithms plus a conditional modification step, as far as /spl Lambda/' is a sublattice of /spl Lambda/. We derive the underlying conditions on m_ and present generic near-ellipsoidal Voronoi indexing algorithms. Examples of constraints on m_ and conditional modification are provided for the lattices A/sub 2/, D/sub n/ (n/spl ges/2) and 2D/sub n//sup +/ (n even /spl ges/4).     

Prime-length real-valued polynomial residue division algorithms

One class of efficient algorithms for computing a discrete Fourier transform (DFT) is based on a recursive polynomial factorization of the polynomial 1-z/sup -N/. The Bruun algorithm is a typical example of such algorithms. Previously, the Bruun algorithm, which is applicable only when system lengths are powers of two in its original form, is generalized and modified to be applicable to the case when the length is other than a power of two. This generalized algorithm consists of transforms T/sub d,f/ with prime d and real f in the range 0/spl les/f<0.5. T/sub d,0/ computes residues X(z)mod(1-z/sup -2/) and X(z)mod(1-2 cos(/spl pi/k/d)z/sup -1/+z/sup -2/), k=1, 2, ..., d-1, and T/sub d,f/ (f /spl ne/0) computes residues X(z)mod(1-2cos(2/spl pi/(f+k)/d)z/sup -1/+z/sup -2/), k=0, 1, ..., d-1 for a given real signal X(z) of length 2d. The purpose of this paper is to find efficient algorithms for T/sub d,f/. First, polynomial factorization algorithms are derived for T/sub d,0/ and T/sub d,1/4/. When f is neither 0 nor 1/4, it is not feasible to derive a polynomial factorization algorithm. Two different implementations of T/sub d,f/ for such f are derived. One implementation realizes T/sub d,f/ via a d-point DFT, for which a variety of fast algorithms exist. The other implementation realizes T/sub d,f/ via T/sub d, 1/4/, for which the polynomial factorization algorithm exists. Comparisons show that for d/spl ges/5, these implementations achieve better performance than computing each output of T/sub d,f/ separately.