共查询到20条相似文献,搜索用时 15 毫秒
1.
Wende Chen Klove T. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1999,45(1):276-281
The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d1,d2,···,dk ) where dr is the smallest support of an r-dimensional subcode of C. An [n,k;q] code is extremal nonchain if, for any r and s, where 1⩽rS(D)=dr, and wS (E)=ds. The possible weight hierarchies of such binary codes of dimension 4 are determined 相似文献
2.
Linder T. Zeger K. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1996,42(2):480-487
The problem of fixed-rate block quantization of an unbounded real memoryless source is studied. It is proved that if the source has a finite sixth moment, then there exists a sequence of quantizers Qn of increasing dimension n and fixed rate R such that the mean squared distortion Δ(Qn) is bounded as Δ(Qn )⩽D(R)+O(√(log n/n)), where D(R) is the distortion-rate function of the source. Applications of this result include the evaluation of the distortion redundancy of fixed-rate universal quantizers, and the generalization to the non-Gaussian case of a result of Wyner on the transmission of a quantized Gaussian source over a memoryless channel 相似文献
3.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1983,29(3):352-353
Lett(n,k) denote the minimum covering radius of a binary linear(n,k) code. We give a nonconstructive upper bound ont(n,k) , which coincides asymptotically with the known lower bound, namelyn^{-1}t(n,nR)=H^{-1}(1-R)+O(n^{-l}log n) , whereR is fixed,0, andH^{-1} is the inverse of the binary entropy function. 相似文献
4.
Xiang-dong Hou 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1997,43(3):1025-1027
Let ρ(1,m) and N(1,m) be the covering radius and norm of the first-order Reed-Muller code R(1,m), respectively. It is known that ρ(1,2k+1)⩽lower bound [22k-2(2k-1/2)] and N(1,2k+1)⩽2 lower bound [22k-2(2k-1/2)] (k>0). We prove that ρ(1,2k+1)⩽2 lower bound [22k-1-2(2k-3/2)] and N(1,2k+1)⩽4 lower bound [22k-1-2(2k-3/2)] (k>0). We also discuss the connections of the two new bounds with other coding theoretic problems 相似文献
5.
A pseudo-Gray code is an assignment of n -bit binary indexes to 2" points in a Euclidean space so that the Hamming distance between two points corresponds closely to the Euclidean distance. Pseudo-Gray coding provides a redundancy-free error protection scheme for vector quantization (VQ) of analog signals when the binary indexes are used as channel symbols on a discrete memoryless channel and the points are signal codevectors. Binary indexes are assigned to codevectors in a way that reduces the average quantization distortion introduced in the reproduced source vectors when a transmitted index is corrupted by channel noise. A globally optimal solution to this problem is generally intractable due to an inherently large computational complexity. A locally optimal solution, the binary switching algorithm, is introduced, based on the objective of minimizing a useful upper bound on the average system distortion. The algorithm yields a significant reduction in average distortion, and converges in reasonable running times. The sue of pseudo-Gray coding is motivated by the increasing need for low-bit-rate VQ-based encoding systems that operate on noisy channels, such as in mobile radio speech communications 相似文献
6.
Bartlett P.L. Linder T. Lugosi G. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1998,44(5):1802-1813
We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independent and identically distributed (i.i.d.) data points using any design algorithm is at least Ω(n-1/2) away from the optimal distortion for some distribution on a bounded subset of ℛ d. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of n-1/2. We also derive a new upper bound for the performance of the empirically optimal quantizer 相似文献
7.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1980,26(2):137-143
For every individual infinite sequenceu we define a distortion-rate functiond(R|u) which is shown to be an asymptotically attainable lower bound on the distortion that can be achieved foru by any finite-state encoder which operates at a fixed output information rateR . This is done by means of a coding theorem and its converse. No probabilistic characterization ofu is assumed. The coding theorem demonstrates the existence of {em universal} encoders which are asymptotically optimal for every infinite sequence over a given finite alphabet. The transmission of individual sequences via a noisy channel with a capacityC is also investigated. It is shown that, for every given sequenceu and any finite-state encoder, the average distortion with respect to the channel statistics is lower bounded byd(C|u) . Furthermored(C|u) is asymptotically attainable. 相似文献
8.
Asymptotically optimal block quantization 总被引:9,自引:0,他引:9
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1979,25(4):373-380
In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formulaD : = : frac{1}{12N^{2}} : int : p(x) [ É(x) ]^{-2} dx for the mean-square quantizing error whereN is the number of levels,p (x) is the probability density of the input, andE prime (x) is the slope of the compressor curve. The formula, an approximation based on the assumption that the number of levels is large and overload distortion is negligible, is a useful tool for analytical studies of quantization. This paper gives a heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized. The approach is again based on the asymptotic situation whereN , the number of quantized output vectors, is very large. Using the resulting heuristic formula, an optimization is performed leading to an expression for the minimum quantizing noise attainable for any block quantizer of a given block sizek . The results are consistent with Zador's results and specialize to known results for the one- and two-dimensional cases and for the case of infinite block length(k rightarrow infty) . The same heuristic approach also gives an alternate derivation of a bound of Elias for multidimensional quantization. Our approach leads to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers. In particular, fork = 3 we give a tight upper bound that may in fact be exact. The idea of representing a block quantizer by a block "compressor" mapping followed with an optimal quantizer for uniformly distributed random vectors is also explored. It is not always possible to represent an optimal quantizer with this block companding model. 相似文献
9.
Chou P.A. Effros M. Gray R.M. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1996,42(4):1109-1138
A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that “quantizes” the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n -1 log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n-1) when the universe of sources is countable, and as O(n-1+ϵ) when the universe of sources is infinite-dimensional, under appropriate conditions 相似文献
10.
Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10-5⩽ϵ⩽ 1/2. They also find the minimum distance of the shortened code of length n for 33 ⩽n ⩽12144 and the double-burst detecting capabilities 相似文献
11.
Linder T. Lugosi G. Zeger K. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1997,43(2):612-623
The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean independent and identically distributed (i.i.d.) training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided 相似文献
12.
《Microwave Theory and Techniques》1998,46(8):1187-1192
By introducing the concept of “virtual relative permittivity,” this paper reports several closed-form dispersion models for a multilayered shielded/unshielded microstrip line over 1<ϵr⩽20, 0.1⩽(w/h)⩽10, (h3/h)⩾2 in the frequency range up to 4 GHz.cm. The maximum deviation of the one model against the results of the spectral-domain analysis (SDA) is limited to 3%, while for the other three models, the maximum deviation is <2% and the root-mean-square (rms) deviation is <0.8%. This paper also reports improvement in the closed-form model of March for the determination of ϵeff(O) of the shielded microstrip line 相似文献
13.
Pawlak M. Stadtmuller U. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1996,42(5):1425-1438
We consider the problem of recovering a band-limited signal f(t) from noisy data yk=f(kτ)+≫epsilon/k, where τ is the sampling rate. Starting from the truncated Whittaker-Shannon cardinal expansion with or without sampling windows (both cases yield inconsistent estimates of f(t)) we propose estimators that are convergent to f(t) in the pointwise and uniform sense. The basic idea is to cut down high frequencies in the data and to use suitable oversampling τ⩽π/Ω, Ω being the bandwidth (maximum frequency) of f(t). The simplest estimator we propose is given by fˆn(t)=τ Σ/|t-kτ|⩽nτ yksin(Ω(t-kτ))/π(t-kτ),|t|⩽nτ. Generalizations of fˆn including sampling windows are also examined. The main aim is to examine the mean squared error (MSE) properties of such estimators in order to determine the optimal choice of the sampling rate τ yielding the fastest possible rate of convergence. The best rate for the MSE we obtain is O(In(n)/n) 相似文献
14.
Seguin G.E. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1995,41(2):387-399
For (n, q)=1 V a qm-ary cyclic code of length n and with generator polynomial g(x), we show that there exists a basis for F(qm) over Fq with respect to which the q-ary image of V is cyclic, if and only if: (i) g(x) is over Fq; or (ii) g(x)=g0(x)(x-γ-q(μ)), g0(x) is over Fq, Fq≠F(qk)=Fq(γ)⊂F(qm ), μ an integer modulo k, and wm-γ has a divisor over F(qk) of degree e=m/k; or (iii) g(x)=g0 (x) Πμϵs(x-γ(-qμ)), g 0(x) is over Fq, Fq≠F(qk)=Fq(γ)⊂F(qm ), S a set of integers module k of cardinality k-1 and wm -μ has a divisor over F(qk) 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 相似文献
15.
16.
17.
A two-channel conjugate vector quantizer is proposed in an attempt to reduce quantization distortion for noisy channels. In this quantization, two different codebooks are used. The encoder selects the channel code pair that generates the smallest distortion between the input and the averaged output vectors. These two codebooks are alternately trained by an iterative algorithm which is based on the generalized Lloyd algorithm. Coding experiments show that the proposed scheme has almost the same SNR as a conventional vector quantizer for an error-free channel. On the other hand, it has a significantly higher SNR than the conventional one for a 1% error rate. This scheme also has merits in computational complexity and storage requirements. The scheme is confirmed to be effective for a medium bit-rate speech waveform coder 相似文献
18.
19.
Constellations matched to the Rayleigh fading channel 总被引:2,自引:0,他引:2
Girand X. Belfiore J.C. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1996,42(1):106-115
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=(x1, ···, xn)∈Rn, |Πi=1nxi|⩽1}. The lattices among which we search for an optimal solution are the standard embeddings in R n 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 相似文献
20.
A dispersion formula ϵ*eff(f )=ϵ* -{ϵ*-ϵ*eff(0)}/{1+( f /f 50)m}, for the effective relative permittivity ϵ*eff(f ) of an open microstrip line is derived for computer-aided design (CAD) use. The 50% dispersion point (the frequency f 50 at which ϵ*eff(f 50)={ϵ *+ϵ*eff(0)}/2}) is used a normalizing frequency in the proposed formula, and an expression for f 50 is derived. To obtain the best fit of ϵ *eff(f ) to the theoretical numerical model, the power m of the normalized frequency in the proposed formula is expressed as a function of width-to-height ratio w / h for w /h ⩾0.7 and as a function of w /h , f 50, and f for w /h ⩽0.7. The present formula has a high degree of accuracy, better than 0.6% in the range 0.1<w /h ⩽10, 1<ϵ*⩽128, and any height-to-wavelength ratio h /λ0 相似文献