均衡弹性函数的结构与弹性阶

弹性函数是相关免疫布尔函数的自然推广。本文讨论均衡弹性函数,得到以下结果:给出了均衡弹性函数的一种结构,并因此得到了由均衡(n,m,2t)弹性函数构造均衡(n+1,m,2t+1)弹性函数的非线性方法;证明了均衡线性函数的弹性阶等于对应线性分组码的码字最小重最减1,且弹性阶上确界常常能由非线性函数所达到。     

(n+1,m,2t)均衡弹性函数的非线性构造方法

基于GF(2)n上(n,m,2t-1)均衡弹性函数,运用其对偶分布性质和各分量函数弹性阶的相关特性,得到了(n 1,m,2t)均衡弹性函数的非线性构造方法。这些方法使得自变量的维数与弹性阶同步增长,且函数的代数次数也相应增加,从而避免了线性构造的缺陷。     

A product construction for perfect codes over arbitrary alphabets (Corresp.)

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 + 1over an alphabet of orderq, one can construct perfect single-error-correcting codes of length(q - 1)nm + n + mover the same alphabet. Moreover, if there exists a perfect single-error-correcting code of lengthq + 1over 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 orderqand perfect codes of lengthq + 1over an alphabet of orderqare discussed.     

A note on maximum distance separable (optimal) codes (Corresp.)

Given a positive integerkand a prime powerqwithq leq k, it is proved that the largest value ofnfor 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 ofnfor which there exists an[n,2,n-1]MDS code over any finite field is also given.     

On the truncation error of the cardinal sampling expansion

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 banddeltaand for Fourier-Stieltjes transforms; we require only a bounded variation condition in the vicinity of the endpoints- piand+ piof 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.     

On MDS extensions of generalized Reed- Solomon codes

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} qis 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 withkin the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} qis 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 + 1do not exist.     

FIR perfect signal reconstruction from multiple convolutions:minimum deconvolver orders

Given p co-prime finite impulse response (FIR) filters h_i ∈R(m_h), it well known that there exist q _i∈R(m_q) such that Σ_ih_i*q_i=δ. Importantly, this enables signal recovery from its convolutions with p⩾2 co-prime FIR filters by FIR filtering. We show that such q_i exist almost surely if and only if m_q⩾[(m_h-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     

基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造

在特征为p的有限域上,基于弹性函数与正交表大集间的等价关系,借助于一个具有最大圈结构的拉丁方,给出了一个构造q元旋转对称弹性函数的新方法.此外,通过一个具体的实例说明了本文的方法能够构造出已有方法不能构造的GF（p）上的q元旋转对称弹性函数.     

Polynomial Time Approximation Algorithms for Multi-Constrained QoS Routing

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.     

On the Values of Kloosterman Sums

Given a prime $p$ and a positive integer $n$ , we show that the shifted Kloosterman sums $$sum _{x in BBF _{p^{n}}} psi (x + ax^{p^{n}-2}) = sum _{xin BBF _{p^{n}}^{ast }} psi(x + ax^{-1}) + 1, quad a inBBF _{p^{n}}^{ast }$$ where $psi$ is a nontrivial additive character of a finite field $BBF _{p^{n}}$ of $p^{n}$ elements, do not vanish if $a$ belongs to a small subfield $BBF_{p^{m}} subseteq BBF _{p^{n}}$. This complements recent results of P. Charpin and G. Gong which in turn were motivated by some applications to bent functions.      

A linear bound for sliding-block decoder window size

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 Σ     

Frequency-hopping code sequence designs having large linear span

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², p) and (p ⁿ, 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     

On certain projective geometry codes (Corresp.)

LetVbe 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 ifnuhas 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-qrepresentation of the numberx. LetSbe 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 thatSis 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.     

Wide-sense and strict-sense nonblocking operation of multicastmulti-log2 n switching networks

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-log₂ 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 · 2^n-t-1 + 2 ^n-2t-1 planes of a log₂ N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2^t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2^n-t-1 + 1 and 2^t + (n - t - 1) · 2^n-t-1 - 2^2t-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     

对联接杂凑函数的“特洛伊”消息攻击

“特洛伊”消息攻击是Andreeva等针对MD结构杂凑函数提出的一种攻击方法,首次将其应用于不同于MD结构的一类杂凑函数,即联接杂凑。结合联接杂凑的特点,综合利用Joux的多碰撞和深度为n?l的“钻石树”结构多碰撞,构造出了2n-bit联接杂凑函数的长度为 块的“特洛伊”消息,并据此首次提出了对其的固定前缀“特洛伊”消息攻击,其存储复杂性为 块消息,时间复杂性为 次压缩函数运算,远低于理想的时间复杂性 。     

Finding a Path Subject to Many Additive QoS Constraints

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     

Electromagnetic scattering from an infinite elliptic metalliccylinder coated by a circular dielectric one

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²+O(h⁴)] 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     

Location-correcting codes

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     

The $(n+1)/2$ Rule for Dealiasing in the Split-Step Fourier Methods for $n$-Wave Interactions

The aim of this letter is to demonstrate that complete removal of spectral aliasing occurring due to finite numerical bandwidth used in the split-step Fourier simulations of nonlinear interactions of optical waves can be achieved by enlarging each dimension of the spectral domain by a factor $(n+1)/2$, where $n$ is the number of interacting waves. Alternatively, when using low-pass filtering for dealiasing this amounts to the need for filtering a $2/(n+1)$ fraction of each spectral dimension.      

On estimating spectral moments in the presence of colored noise

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.