共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(5):769-771
A general product construction for perfect single-error-correcting codes over an arbitrary alphabet is presented. Given perfect single-error-correcting codes of lengthsn, m , andq + 1 over an alphabet of orderq , one can construct perfect single-error-correcting codes of length(q - 1)nm + n + m over the same alphabet. Moreover, if there exists a perfect single-error-correcting code of lengthq + 1 over an alphabet of orderq , then there exist perfect single-error-correcting codes of lengthn ,n = (q^{t} _ 1)/(q - 1) , and(t > 0 , an integer). Finally, connections between projective planes of orderq and perfect codes of lengthq + 1 over an alphabet of orderq are discussed. 相似文献
4.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1983,29(1):136-137
Given a positive integerk and a prime powerq withq leq k , it is proved that the largest value ofn for which there exists an[n,k,n-k+l] maximum distance separable (MDS) code over GF(q) isk+1 . A simple proof for the largest value ofn for which there exists an[n,2,n-1] MDS code over any finite field is also given. 相似文献
5.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1976,22(5):568-573
Modern communication theory and practice are heavily dependent on the representation of continuous parameter signals by linear combinations, involving a denumerable set of random variables. Among the best known and most useful is the cardinal seriesf_{n} (t) = sum^{+n}_{-n} f(k) frac{sin pi (t - k)}{ pi ( t - k )} for deterministic functions and wide-sense stationary stochastic processes bandlimited to(-pi, pi) . When, as invariably occurs in applications, samplesf(k) are available only over a finite period, the resulting finite approximation is subject to a truncation error. For functions which areL_{1} Fourier transforms supported on[-pi + delta, + pi - delta] , uniform trunction error bounds of the formO(n^{-1}) are known. We prove that analogousO(n^{-1}) bounds remain valid without the guard banddelta and for Fourier-Stieltjes transforms; we require only a bounded variation condition in the vicinity of the endpoints- pi and+ pi of the basic interval. Our methods depend on a Dirichlet kernel representation forf_{n}(t) and on properties of functions of bounded variation; this contrasts with earlier approaches involving series or complex variable theory. Other integral kernels (such as the Fejer kernel) yield certain weighted truncated cardinal series whose errors can also be bounded. A mean-square trunction error bound is obtained for bandlimited wide-sense stationary stochastic processes. This error estimate requires a guard band, and leads to a uniformO(n^{-2}) bound. The approach again employs the Dirichlet kernel and draws heavily on the arguments applied to deterministic functions. 相似文献
6.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(3):349-354
An(n, k, d) linear code overF= GF(q) is said to be {em maximum distance separable} (MDS) ifd = n - k + 1 . It is shown that an(n, k, n - k + 1) generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} q is even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withk in the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1 , and that generalized Reed-Solomon codes of lengthq + 1 and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} q is even) do not have MDS extensions. Hence, in cases where the(q + 1, k) MDS code is essentially unique,(n, k) MDS codes withn > q + 1 do not exist. 相似文献
7.
Given p co-prime finite impulse response (FIR) filters hi ∈R (mh), it well known that there exist q i∈R (mq) such that Σihi*qi=δ. Importantly, this enables signal recovery from its convolutions with p⩾2 co-prime FIR filters by FIR filtering. We show that such qi exist almost surely if and only if mq⩾[(mh-1)/(p-1)], where [x] is the smallest integer greater than or equal to x. The results also provide conditions for full rank of certain key matrices arising in the blind multichannel deconvolution problem 相似文献
8.
Guoliang Xue Weiyi Zhang Jian Tang Thulasiraman K. 《Networking, IEEE/ACM Transactions on》2008,16(3):656-669
We study the multi-constrained quality-of-service (QoS) routing problem where one seeks to find a path from a source to a destination in the presence of K ges 2 additive end-to-end QoS constraints. This problem is NP-hard and is commonly modeled using a graph with n vertices and m edges with K additive QoS parameters associated with each edge. For the case of K = 2, the problem has been well studied, with several provably good polynomial time-approximation algorithms reported in the literature, which enforce one constraint while approximating the other. We first focus on an optimization version of the problem where we enforce the first constraint and approximate the other K - 1 constraints. We present an O(mn log log log n + mn/epsi) time (1 + epsi)(K - 1)-approximation algorithm and an O(mn log log log n + m(n/epsi)K-1) time (1 + epsi)-approximation algorithm, for any epsi > 0. When K is reduced to 2, both algorithms produce an (1 + epsi)-approximation with a time complexity better than that of the best-known algorithm designed for this special case. We then study the decision version of the problem and present an O(m(n/epsi)K-1) time algorithm which either finds a feasible solution or confirms that there does not exist a source-destination path whose first weight is bounded by the first constraint and whose every other weight is bounded by (1 - epsi) times the corresponding constraint. If there exists an H-hop source-destination path whose first weight is bounded by the first constraint and whose every other weight is bounded by (1 - epsi) times the corresponding constraint, our algorithm finds a feasible path in O(m(H/epsi)K-1) time. This algorithm improves previous best-known algorithms with O((m + n log n)n/epsi) time for K = 2 and 0(mn(n/epsi)K-1) time for if ges 2. 相似文献
9.
10.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》2009,55(6):2599-2601
11.
Ashley J.J. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1988,34(3):389-399
The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n -ary data into any constrained system Σ with capacity at least log(n ) presented by a graph G with memory m and anticipation a . Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t :t and with window length m +a +2t , where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Σ with finite memory must grow at least linearly with the number of states of the graph G presenting Σ 相似文献
12.
Frequency-hopping code sequence designs having large linear span 总被引:3,自引:0,他引:3
Kumar P.V. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1988,34(1):146-151
In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p 2, p ) and (p n, p n/2+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p , whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method 相似文献
13.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(2):385-388
LetV be an(n, k, d) binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s} , andd geq [(q^{m-r}-1)/(q - 1)] + 1 . This code isr -step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} } , the generator polynomialg(X) , ofV , hasalpha^{nu} as a root if and only ifnu has the formnu = i(q - 1) andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1) , whereW_{q}(x) indicates the weight of the radix-q representation of the numberx . LetS be the set of nonzero numbersnu , such thatalpha^{nu} is a root ofg(X) . LetC_{1}, C_{2}, cdots, C_{nu} be the cyclotomic cosets such thatS is the union of these cosets. It is clear that the process of findingg(X) becomes simpler if we can find a representative from eachC_{i} , since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2 , withs = 2, 3 , andm-r=3 , withs=2 . 相似文献
14.
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-log2 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 · 2n-t-1 + 2 n-2t-1 planes of a log2 N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2n-t-1 + 1 and 2t + (n - t - 1) · 2n-t-1 - 22t-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 相似文献
15.
“特洛伊”消息攻击是Andreeva等针对MD结构杂凑函数提出的一种攻击方法,首次将其应用于不同于MD结构的一类杂凑函数,即联接杂凑。结合联接杂凑的特点,综合利用Joux的多碰撞和深度为n?l的“钻石树”结构多碰撞,构造出了2n-bit联接杂凑函数的长度为 块的“特洛伊”消息,并据此首次提出了对其的固定前缀“特洛伊”消息攻击,其存储复杂性为 块消息,时间复杂性为 次压缩函数运算,远低于理想的时间复杂性 。 相似文献
16.
Finding a Path Subject to Many Additive QoS Constraints 总被引:2,自引:0,他引:2
Guoliang Xue Arunabha Sen Weiyi Zhang Jian Tang Krishnaiya Thulasiraman 《Networking, IEEE/ACM Transactions on》2007,15(1):201-211
A fundamental problem in quality-of-service (QoS) routing is to find a path between a source-destination node pair that satisfies two or more end-to-end QoS constraints. We model this problem using a graph with n vertices and m edges with K additive QoS parameters associated with each edge, for any constant Kges2. This problem is known to be NP-hard. Fully polynomial time approximation schemes (FPTAS) for the case of K=2 have been reported in the literature. We concentrate on the general case and make the following contributions. 1) We present a very simple (Km+nlogn) time K-approximation algorithm that can be used in hop-by-hop routing protocols. 2) We present an FPTAS for one optimization version of the QoS routing problem with a time complexity of O(m(n/epsi)K-1). 3) We present an FPTAS for another optimization version of the QoS routing problem with a time complexity of O(nlogn+m(H/epsi)K-1) when there exists an H-hop path satisfying all QoS constraints. When K is reduced to 2, our results compare favorably with existing algorithms. The results of this paper hold for both directed and undirected graphs. For ease of presentation, undirected graph is used 相似文献
17.
The scattering from an infinite elliptic metallic cylinder coated by a circular dielectric one is considered. The electromagnetic field is expressed in terms of both circular and elliptical cylindrical wave functions, which are connected with one another by well-known expansion formulas. In the special case of small h =ka /2 (a being the interfocal distance of the elliptic conductor and k the wavenumber of the dielectric coating), exact, closed-form expressions of the form S (h )=S (0)[1+g "h 2+O (h 4)] are obtained for the scattered field and the various scattering cross sections of the problem. Both polarizations are considered for normal incidence. Graphical results for various values of the parameters are given 相似文献
18.
Roth R.M. Seroussi G. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1996,42(2):554-565
We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(√(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t∈{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded 相似文献
19.
《Photonics Technology Letters, IEEE》2008,20(23):1929-1931
20.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1970,16(3):303-309
Let{q^(1) (t)} , the signal, be a complex Gaussian process corrupted by additive Gaussian noise{q^(2) (t) } . Observations onp(t)q(t) andp(t) q^(2) (t) are assumed to be available wherep(t) is a smooth weighting function andq = q^(1) + q^(2) . Using the Fourier transform of the samples ofp(t)q(t) andp(t) q^(2) (t) , estimators are derived for estimating the mean frequency and spectral width of the unknown power spectrum of the unweighted signal process. The means and variances of these statistics are computed in general, and explicitly for nontrivial practical examples. Asymptotic formulas for the moment estimators as a function of the number of realizations, frequency resolution, signal-to-noise ratio and spectral width, and consistency of the estimators are some of the results that are discussed in detail. 相似文献