Compression mappings on primitive sequences over Z/(p/sup e/)

Let Z/(p/sup e/) be the integer residue ring with odd prime p/spl ges/5 and integer e/spl ges/2. For a sequence a_ over Z/(p/sup e/), there is a unique p-adic expansion a_=a_/sub 0/+a_/spl middot/p+...+a_/sub e-1//spl middot/p/sup e-1/, where each a_/sub i/ is a sequence over {0,1,...,p-1}, and can be regarded as a sequence over the finite field GF(p) naturally. Let f(x) be a primitive polynomial over Z/(p/sup e/), and G'(f(x),p/sup e/) the set of all primitive sequences generated by f(x) over Z/(p/sup e/). Set /spl phi//sub e-1/ (x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,1/(x/sub 0/, x/sub 1/,...,x/sub e-2/) /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,2/(x/sub 0/,x/sub 1/,...,x/sub e-2/) where /spl eta//sub e-2,1/ and /spl eta//sub e-2,2/ are arbitrary functions of e-1 variables over GF(p) and 2/spl les/k/spl les/p-1. Then the compression mapping /spl phi//sub e-1/:{G'(f(x),p/sup e/) /spl rarr/ GF(p)/sup /spl infin// a_ /spl rarr/ /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) is injective, that is, a_ = b_ if and only if /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl phi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/). Furthermore, if f(x) is a strongly primitive polynomial over Z/(p/sup e/), then /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl psi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) if and only if a_ = b_ and /spl phi//sub e-1/(x/sub 0/,...,x/sub e-1/) = /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/).     

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/).     

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.     

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

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.     

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

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.     

A new binary sequence family with low correlation and large size

For odd n=2l+1 and an integer /spl rho/ with 1/spl les//spl rho//spl les/l, a new family S/sub o/(/spl rho/) of binary sequences of period 2/sup n/-1 is constructed. For a given /spl rho/, S/sub o/(/spl rho/) has maximum correlation 1+2/sup n+2/spl rho/-1/2/, family size 2/sup n/spl rho//, and maximum linear span n(n+1)/2. Similarly, a new family of S/sub e/(/spl rho/) of binary sequences of period 2/sup n/-1 is also presented for even n=2l and an integer /spl rho/ with 1/spl les//spl rho/相似文献   

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.     

A nontrivial lower bound on the Shannon capacities of the complements of odd cycles

This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that /spl alpha/(C~/sub 2n+3/(2/sup n/))/spl ges/2(2/sup n/)+1. It follows that for n/spl ges/0 we have /spl Theta/(C~/sub 2n+3/)>2, where /spl Theta/(G) denotes the Shannon (1956) capacity of graph G.     

Dependence of the neodymium random laser threshold on the diameter of the pumped spot

We experimentally studied the dependence of the threshold energy density E/sub th//S in Nd/sub 0.5/La/sub 0.5/Al/sub 3/(BO/sub 3/)/sub 4/ random laser on the diameter of the pumped spot d and found that at d/spl ges/130/spl mu/m, E/sub th//S is proportional to 1/d+const. This functional dependence is different from the one commonly expected in the case of diffusion, /spl prop/1/d/sup 2/+const. However, the obtained experimental dependence does not mean the failure of the diffusion model. Calculating the mean photon's residence time /spl tau//sub res//sup p/ (which photons, making their diffusion-like random walks, spend inside the gain volume) as the function of d and further assuming that E/sub th//S/spl prop/(/spl tau//sup p//sub res/)/sup -1/, we predicted the experimentally obtained functional dependence, /spl prop/1/d+const. The major difference between our model and that of and was in the boundary conditions.     

Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.     

On /spl Zopf//sub 4/-linear Preparata-like and Kerdock-like codes

We say that a binary code of length n is additive if it is isomorphic to a subgroup of /spl Zopf//sub 2//sup /spl alpha// /spl times/ /spl Zopf//sub 4//sup /spl beta//, where the quaternary coordinates are transformed to binary by means of the usual Gray map and hence /spl alpha/ + 2/spl beta/ = n. In this paper, we prove that any additive extended Preparata (1968) -like code always verifies /spl alpha/ = 0, i.e., it is always a /spl Zopf//sub 4/-linear code. Moreover, we compute the rank and the dimension of the kernel of such Preparata-like codes and also the rank and the kernel of the /spl Zopf//sub 4/-dual of these codes, i.e., the /spl Zopf//sub 4/-linear Kerdock-like codes.     

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

List decoding of q-ary Reed-Muller codes

The q-ary Reed-Muller (RM) codes RM/sub q/(u,m) of length n=q/sup m/ are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in and . The algorithm in Sudan et al. (1999) is an improvement of the algorithm in , it is applicable to codes RM/sub q/(u,m) with u相似文献   

Generalization of the /spl Sigma//sub 0/-rank criteria for space-time codes

Recently, Liu et al., developed the /spl Sigma//sub 0/-rank criteria for space-time codes. It provides a sufficient condition on codeword and generator matrices defined over finite rings /spl Zopf//sub 2k/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation. Here, we generalize the /spl Sigma//sub 0/-rank criteria and derive a sufficient condition on the generator matrices defined over finite rings /spl Zopf//sub 2l/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation for any positive integer l/spl les/k. We also show that generator matrices defined over GF(2) satisfying the BPSK stacking construction constraint of Mammons and El Gamal achieve full spatial diversity when used with 2/sup 2k/-QAM modulation.     

Asymptotic capacity of two-dimensional channels with checkerboard constraints

A checkerboard constraint is a bounded measurable set S/spl sub/R/sup 2/, containing the origin. A binary labeling of the Z/sup 2/ lattice satisfies the checkerboard constraint S if whenever t/spl isin/Z/sup 2/ is labeled 1, all of the other Z/sup 2/-lattice points in the translate t+S are labeled 0. Two-dimensional channels that only allow labelings of Z/sup 2/ satisfying checkerboard constraints are studied. Let A(S) be the area of S, and let A(S)/spl rarr//spl infin/ mean that S retains its shape but is inflated in size in the form /spl alpha/S, as /spl alpha//spl rarr//spl infin/. It is shown that for any open checkerboard constraint S, there exist positive reals K/sub 1/ and K/sub 2/ such that as A(S)/spl rarr//spl infin/, the channel capacity C/sub S/ decays to zero at least as fast as (K/sub 1/log/sub 2/A(S))/A(S) and at most as fast as (K/sub 2/log/sub 2/A(S))/A(S). It is also shown that if S is an open convex and symmetric checkerboard constraint, then as A(S)/spl rarr//spl infin/, the capacity decays exactly at the rate 4/spl delta/(S)(log/sub 2/A(S))/A(S), where /spl delta/(S) is the packing density of the set S. An implication is that the capacity of such checkerboard constrained channels is asymptotically determined only by the areas of the constraint and the smallest (possibly degenerate) hexagon that can be circumscribed about the constraint. In particular, this establishes that channels with square, diamond, or hexagonal checkerboard constraints all asymptotically have the same capacity, since /spl delta/(S)=1 for such constraints.     

Semi-empirical model of the ensemble-averaged differential Mueller matrix for microwave backscattering from bare soil surfaces

A semi-empirical model of the ensemble-averaged differential Mueller matrix for microwave backscattering from bare soil surfaces is presented. Based on existing scattering models and data sets measured by polarimetric scatterometers and the JPL AirSAR, the parameters of the co-polarized phase-difference probability density function, namely the degree of correlation /spl alpha/ and the co-polarized phase-difference /spl sigmav/, in addition to the backscattering coefficients /spl sigma//sub /spl nu//spl nu///sup 0/,/spl sigma//sub hh//sup 0/ and /spl sigma//sub /spl nu/h//sup 0/, are modeled empirically in terms of the volumetric soil moisture content m/sub /spl nu// and the surface roughness parameters ks and kl, where k=2/spl pi/f/c, s is the rms height and l is the correlation length. Consequently, the ensemble-averaged differential Mueller matrix (or the differential Stokes scattering operator) is specified completely by /spl sigma//sub /spl nu//spl nu///sup 0/,/spl sigma//sub hh//sup 0/,/spl sigma//sub /spl nu/h//sup 0/,/spl alpha/, and /spl zeta/.     

Theory of Direct-Coupled-Cavity Filters

A new theory is presented for the design of direct-coupled-cavity filters in transmission line or waveguide. It is shown that for a specified range of parameters the insertion-loss characteristic of these filters in the case of Chebyshev equal-ripple characteristic is given very accurately by the formula P/sub 0/ / /P/sub L/ = 1+h/sup 2/T/sub n//sup 2/[/spl omega//sub 0/ / /spl omega/ sin(/spl pi/ /spl omega/ / /spl omega//sub 0/) / sin/spl theta//sub 0/'] where h defines the ripple level, T/sub n/ is the first-kind Chebyshev polynomial of degree n, /spl omega/ / /spl omega//sub 0/ is normalized frequency, and /spl theta//sub 0/' is an angle proportional to the bandwidth of a distributed lowpass prototype filter. The element values of the direct-coupled filter are related directly to the step impedances of the prototype whose values have been tabulated. The theory gives close agreement with computed data over a range of parameters as specified by a very simple formula. The design technique is convenient for practical applications.     

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.