Search

A simple scheme that achieves the capacity and the reliability function of the wideband Costa dirty-paper channel is proposed. The scheme can be interpreted as an opportunistic version of pulse position modulation (PPM). This interpretation suggests a natural generalization of the scheme which we show to achieve the capacity per unit cost of Gel'fand-Pinsker channels with a zero-cost input letter. [ABSTRACT FROM AUTHOR]

We study the recovery of operators with a bandlimited Kohn–Nirenberg symbol from the action of such operators on a weighted impulse train, a procedure we refer to as sampling of operators. Kailath, Bello, and later Kozek and the authors have shown that the sampling of operators is possible if the symbol of the operator is bandlimited to a set with area less than one. In this paper, we develop the theory of the sampling of operators in analogy with the classical theory of sampling of bandlimited functions. We define the notions of sampling set and sampling rate for operators and give necessary and sufficient conditions on the sampling rate that depend on the size and geometry of the bandlimiting set. We develop explicit reconstruction formulas for operator sampling that generalize reconstruction formulas for bandlimited functions. We give necessary and sufficient conditions on the bandlimiting set under which sampling of operators is possible by their action on a given periodically weighted delta train. We show that under mild geometric conditions on the bandlimiting set, classes of operators are bandlimited to an unknown set of area less than one-half permit sampling and reconstruction. We generalize two results of the Heckel and Bölcskei concerning sampling of operators with area not greater than one-half and less than one, respectively, by finding a larger class of operators to which they apply. Operators with bandlimited symbols have been used to model doubly dispersive communication channels with slowly time-varying impulse response. The results in this paper are rooted in work by Bello and Kailath in the 1960s. [ABSTRACT FROM PUBLISHER]

Assume we have a set of observations (for example, images) of different objects, each undergoing a different geometric deformation, yet all the deformations belong to the same family. As a result of the action of these deformations, the set of different observations on each object is generally a manifold in the ambient space of observations. In this paper we show that in those cases where the set of deformations admits a finite-dimensional representation, there is a mapping from the space of observations to a low-dimensional linear space. The manifold corresponding to each object is mapped to a distinct linear subspace of Euclidean space. The dimension of the subspace is the same as that of the manifold. This mapping, which we call universal manifold embedding, enables the estimation of geometric deformations using the classical linear theory. The universal manifold embedding further enables the representation of the object classification and detection problems in a linear subspace matching framework. The embedding of the space of observations depends on the deformation model, and is independent of the specific observed object; hence, it is universal. We study two cases of this embedding: that of elastic deformations of 1-D signals, and the case of affine deformations of $n$ -dimensional signals. [ABSTRACT FROM AUTHOR]

In this paper, we employ the so-called semi-bent functions to achieve significant improvements over currently known methods, regarding the number of orthogonal sequences per cell that can be assigned to a regular tessellation of hexagonal cells, typical for certain code-division multiple-access systems. Our initial design method generates a large family of orthogonal sets of sequences derived from vectorial semi-bent functions. A modification of the original approach is proposed to avoid a hard combinatorial problem of allocating several such orthogonal sets to a single cell of a regular hexagonal network, while preserving the orthogonality to adjacent cells. This modification increases the number of users per cell by starting from shorter codewords and then extending the length of these codewords to the desired length. The specification and assignment of these orthogonal sets to a regular tessellation of hexagonal cells have been solved, regardless of the parity and size of m (where 2^{m} is the length of the codewords). In particular, when the re-use distance is D=4 , the number of users per cell is 2^m-2 for almost all m , which is twice as many as can be obtained by the best known methods. [ABSTRACT FROM AUTHOR]

A key aspect of many resource allocation problems is the need for the resource controller to compute a function, such as the $\max $ or \mathop {\mathrm {arg\,max\kern 0pt}} , of the competing users’ metrics. Information must be exchanged between the competing users and the resource controller in order for this function to be computed. In many practical resource controllers, the competing users’ metrics are communicated to the resource controller, which then computes the desired extremization function. However, in this paper, it is shown that information rate savings can be obtained by recognizing that the controller only needs to determine the result of this extremization function. If the extremization function is to be computed losslessly, the rate savings are shown in most cases to be at most 2 b independent of the number of competing users. Motivated by the small savings in the lossless case, simple achievable schemes for both the lossy and interactive variants of this problem are considered. It is shown that both of these approaches have the potential to realize large rate savings, especially in the case where the number of competing users is large. For the lossy variant, it is shown that the proposed simple achievable schemes are in fact close to the fundamental limit given by the rate distortion function. [ABSTRACT FROM AUTHOR]

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert–Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets. [ABSTRACT FROM AUTHOR]

It is well known that the entropy $H(X)$ of a discrete random variable $X$ is always greater than or equal to the entropy $H(f(X))$ of a function $f$ of $X$ , with equality if and only if $f$ is one-to-one. In this paper, we give tight bounds on $H(f(X))$ , when the function $f$ is not one-to-one, and we illustrate a few scenarios, where this matters. As an intermediate step toward our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario. [ABSTRACT FROM AUTHOR]

In this comment, we consider a generalization of the Shannon–Khinchin axioms (GSK axioms) and the uniqueness theorem for the entropy determined by GSK axioms proposed in [H. Suyari, IEEE Trans. Inf. Theory, vol. 50, pp. 1783–1787, Aug. 2004]. It is shown that the class of entropy functions determined by the axioms from the mentioned paper is wider than the one proposed in this paper, and a counterexample is given. We also derive a new class of entropies by fixing the incorrectness which occurs in the mentioned paper. [ABSTRACT FROM AUTHOR]

A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most $r$ ) of other symbols of the codeword. In this paper, we introduce a construction of LRC codes on algebraic curves, extending a recent construction of the Reed–Solomon like codes with locality. We treat the following situations: local recovery of a single erasure, local recovery of multiple erasures, and codes with several disjoint recovery sets for every coordinate (the availability problem). For each of these three problems we describe a general construction of codes on curves and construct several families of LRC codes. We also describe a construction of codes with availability that relies on automorphism groups of curves. We also consider the asymptotic problem for the parameters of the LRC codes on curves. We show that the codes obtained from asymptotically maximal curves (for instance, Garcia-Stichtenoth towers) improve upon the asymptotic versions of the Gilbert-Varshamov bound for LRC codes. [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2\sum i=1^{m}wi-2 or $2mw-2w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely. [ABSTRACT FROM AUTHOR]

The Shannon lower bound is one of the few lower bounds on the rate-distortion function that holds for a large class of sources. In this paper, which considers exclusively norm-based difference distortion measures, it is demonstrated that its gap to the rate-distortion function vanishes as the allowed distortion tends to zero for all sources having finite differential entropy and whose integer part has finite entropy. Conversely, it is demonstrated that if the integer part of the source has infinite entropy, then its rate-distortion function is infinite for every finite distortion level. Thus, the Shannon lower bound provides an asymptotically tight bound on the rate-distortion function if, and only if, the integer part of the source has finite entropy. [ABSTRACT FROM PUBLISHER]

In this paper, some new results are presented on the selective discrete Fourier spectra attack introduced first as the Rønjom–Helleseth attack and the modifications due to Rønjom, Gong, and Helleseth. The first part of this paper fills some gaps in the theory of analysis in terms of the discrete Fourier transform (DFT). The second part introduces the new fast selective DFT attacks, which are closely related to the fast algebraic attacks in the literature. However, in contrast to the classical view that successful algebraic cryptanalysis of LFSR-based stream cipher depends on the degree of certain annihilators, the analysis in terms of the DFT spectral properties of the sequences generated by these functions is far more refined. It is shown that the selective DFT attack is more efficient than known methods for the case when the number of observed consecutive bits of a filter generator is less than the linear complexity of the sequence. Thus, by utilizing the natural representation imposed by the underlying LFSRs, in certain cases, the analysis in terms of DFT spectra is more efficient and has more flexibility than classical and fast algebraic attacks. Consequently, the new attack imposes a new criterion for the design of cryptographic strong Boolean functions, which is defined as the spectral immunity of a sequence or a Boolean function. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the conjecture that \sigma2^{t+1l-1,2^t} are the only nonlinear balanced elementary symmetric Boolean functions where t and l are positive integers. We prove if n=2^t+1l-1, l odd and 2^t+1\nmid d, \sigman,d is balanced if and only if d=2^k, 1\leq k\leq t. Our results verify most cases of the conjecture for n\equiv3\ (mod\ 4). [ABSTRACT FROM AUTHOR]

Lower bounds involving f-divergences between the underlying probability measures are proved for the minimax risk in estimation problems. Our proofs just use simple convexity facts. Special cases and straightforward corollaries of our bounds include well known inequalities for establishing minimax lower bounds such as Fano's inequality, Pinsker's inequality and inequalities based on global entropy conditions. Two applications are provided: a new minimax lower bound for the reconstruction of convex bodies from noisy support function measurements and a different proof of a recent minimax lower bound for the estimation of a covariance matrix.ref refid="fn1"/ id="fn1" asterisk="no"paraAfter acceptance of this manuscript, Prof. A. Gushchin pointed out that Theorem II.1 appears in his paper refid="ref14"/. Specifically, in a different notation, inequality (5) appears as Theorem 1 and inequality (4) appears in refid="ref14", Sec. 4.3. The proof of Theorem II.1 presented in Section II is different from that in refid="ref14"/. Also, except for Theorem II.1 and the observation that Fano's inequality is a special case of Theorem II.1 (see Example II.4), there is no other overlap between this paper and refid="ref14"/.para [ABSTRACT FROM AUTHOR]

In this paper, we study the generalized Marcum Q-function Qv(a,b), where a,v > 0 and b ≥ 0. Our aim is to extend the results of Corazza and Ferrari (IEEE Trans. Inf. Theory, vol. 48, pp. 3003-3008, 2002) to the generalized Marcum Q-function in order to deduce some new tight lower and upper bounds. The key tools in our proofs are some monotonicity properties of certain functions involving the modified Bessel function of the first kind and some classical inequalities, i.e., the Cauchy-Buniakowski-Schwarz and Chebyshev integral inequalities. These bounds are shown to be very tight for large b, i.e., the relative errors of our bounds converge to zero as b increases. Both theoretical analysis and numerical results are provided to show the tightness of our bounds. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of hyperbent functions in n variables, i.e., bent functions which are bent up to a change of primitive roots in the finite field GF(2n). Our main purpose is to obtain an explicit trace representation for some classes of hyperbent functions. We first exhibit an infinite class of monomial functions which is not hyperbent. This result indicates that Kloosterman sums on F2m cannot be zero at some points. For functions with multiple trace terms, we express their spectra by means of Dickson polynomials. We then introduce a new tool to describe these hyperbent functions. The effectiveness of this new method can be seen from the characterization of a new class of binomial hyperbent functions. [ABSTRACT FROM AUTHOR]

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and nonadditive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5, 6, 2)) code found by Rains et al. It also extends to operator quantum error correcting codes. [ABSTRACT FROM AUTHOR]

The goal of channel measurement or operator identification is to obtain complete knowledge of a channel operator by observing the image of a finite number of input signals. In this paper, it is shown that the spreading support of the operator (that is, the support of the symplectic Fourier transform of the Kohn-Nirenberg symbol of the operator) has area less than one then the operator is identifiable. If the spreading support is larger than one, then the operator is not identifiable. The shape of the support region is essentially arbitrary thereby proving a conjecture of Bello. The input signal considered is a weighted delta train where the weights are the window function of a finite Gabor system whose elements satisfy a certain robust completeness property. [ABSTRACT FROM AUTHOR]

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov bound by a factor n$ asymptotically for a minimum distance d$ with . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ . [ABSTRACT FROM PUBLISHER]

Rényi's information measures-the Rényi information, mean, capacity, radius, and center-are analyzed relying on the elementary properties of the Rényi divergence and the power means. The van Erven-Harremoës conjecture is proved for any positive order and for any set of probability measures on a given measurable space and a generalization of it is established for the constrained variant of the problem. The finiteness of the order Rényi capacity is shown to imply the continuity of the Rényi capacity on (0, α] and the uniform equicontinuity of the Rényi information, both as a family of functions of the order indexed by the priors and as a family of functions of the prior indexed by the orders. [ABSTRACT FROM AUTHOR]

The asymptotic decorrelation of the discrete wavelet transform for long-memory processes (such as the fractionally differenced (FD) process, the autoregressive fractionally integrated moving average (ARFIMA) process, and the Gegenbauer autoregressive moving average (GARMA) process) as well as the statistical inference techniques based on this property, have received much attention nowadays. In this paper, we investigate the asymptotic decorrelation property of the discrete wavelet packet transform (DWPT) for two classes of discrete-time long-memory processes containing the ARFIMA and the GARMA processes. Especially, we prove theoretically that the covariance across between-packet DWPT coefficients decays hyperbolically or exponentially fast as the width of the underlying Daubechies scaling and wavelet filters to generate the DWPT gets large. Meanwhile, we show that the covariance between within-packet DWPT coefficients converges hyperbolically fast to its corresponding counterpart when the underlying scaling and wavelet filters to generate the DWPT are the Shannon's ideal low- and high-pass filters. [ABSTRACT FROM AUTHOR]

In this paper, we consider the spectra of Boolean functions with respect to the action of unitary transforms obtained by taking tensor products of the Hadamard kernel, denoted by H, and the nega-Hadamard kernel, denoted by N. The set of all such transforms is denoted by \H, N\^n. A Boolean function is said to be bent4 if its spectrum with respect to at least one unitary transform in \H, N\^n is flat. We obtain a relationship between bent, semibent, and bent4 functions, which is a generalization of the relationship between bent and negabent Boolean functions proved by Parker and Pott [cf., LNCS 4893 (2007), 9–23]. As a corollary to this result, we prove that the maximum possible algebraic degree of a bent4 function on n variables is \lceil n \over 2 \rceil and, hence, solve an open problem posed by Riera and Parker [cf., IEEE-TIT 52:9 (2006), 4142–4159]. [ABSTRACT FROM PUBLISHER]

In this paper, two new families of functions in odd characteristic are constructed, and they are proved to be almost perfect nonlinear (APN) functions. Some of the “open cases” which were introduced by Helleseth are answered by these new APN functions. [ABSTRACT FROM AUTHOR]

In this paper, a many-sources large deviations principle (LDP) for the transient workload of a multiqueue single-server system is established where the service rates are chosen from a compact, convex, and coordinate-convex rate region and where the service discipline is the max-weight policy. Under the assumption that the arrival processes satisfy a many-sources LDP, this is accomplished by employing Garcia's extended contraction principle that is applicable to quasi-continuous mappings. For the traditional single-server queue (simplex rate-region), an LDP for the stationary workload is also established under the additional requirements that the scheduling policy be work-conserving and that the arrival processes satisfy certain mixing conditions. The LDP results can be used to calculate asymptotic buffer overflow probabilities accounting for the multiplexing gain, e.g., when the arrival process is an average of i.i.d. processes. The rate function for the stationary workload is expressed in term of the rate functions of the finite-horizon workloads when the arrival processes have i.i.d. increments. [ABSTRACT FROM AUTHOR]

In this paper we report the following computational results on partial spread functions in eight variables: (i) the numbers of equivalence classes of partial spread functions (in eight variables) of all possible orders; (ii) the total number of partial spread bent functions in eight variables; (iii) the distribution of the cardinalities of stabilizers (in GL(8,\BBF 2)) of partial spread bent functions in eight variables. The computational method is also described. [ABSTRACT FROM AUTHOR]

In coding theory, self-dual codes and cyclic codes are important classes of codes which have been extensively studied. The main objects of study in this paper are self-dual cyclic codes over finite fields, i.e., the intersection of these two classes. We show that self-dual cyclic codes of length n over \BBFq exist if and only if n is even and q = 2^m with m a positive integer. The enumeration of such codes is also investigated. When n and q are even, there is always a trivial self-dual cyclic code with generator polynomial x^n\over 2+1. We, therefore, classify the existence of self-dual cyclic codes, for given n and q, into two cases: when only the trivial one exists and when two or more such codes exist. Given n and m, an easy criterion to determine which of these two cases occurs is given in terms of the prime factors of n, for most n. We also show that, over a fixed field, the latter case occurs more frequently as the length grows. [ABSTRACT FROM AUTHOR]

In this paper, a simple but generic method is proposed for transforming any family of quaternary sequences, with low correlation, of any odd period N to another family of quaternary sequences of period 2N with low correlation. As an application of the generic method to sequence Family \cal A, a new optimal quaternary sequence family with length 2(2^n-1), family size 2^n+1, and maximal nontrivial correlation value 2^n+1\over 2+2, where n is an odd integer, is obtained. Most notably, unlike all the known optimal quaternary sequence families, the new family has a unique property that the odd integers 1, 3 and the even integers 0, 2 are allocated alternatively in all the sequences. [ABSTRACT FROM AUTHOR]

A new algorithm of matrix spectral factorization is proposed which can be applied to compute an approximate spectral factor of any positive definite matrix function which satisfies the Paley-Wiener condition. ref refid="fnote1"/ id="fnote1" asterisk="no"paraThis paper includes the detailed proofs for an innovative method for matrix spectral factorization that can be used in numerous applications, including filtering, data compression, and wireless communications. A U.S. patent application has been submitted for this innovation through the Technology Commercialization Center, University of Maryland.para [ABSTRACT FROM AUTHOR]

For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of Kullback–Leibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the rate loss and achievable region of multiple sources codes (also named multiterminal source codes) in the Wyner–Ziv setting (WZ-MSC), in which two stationary memoryless sources (X,Y) are compressed separately from each other at respective rates R1 and R2, and the joint decoder, having access to the side information S which is correlated with sources (X,Y), reconstructs X and Y with distortion D1 and D2, respectively. We define the rate loss L1=R1-RX\vert Y,S(D1), L2=R2-RY\vert X,S(D2), and L0= R1+R2- RX,Y\vert S(D1,D2). For general real-valued stationary memoryless sources and mean squared error distortion measure, we show that the rate loss can be bounded by Li\leq Ki+1, i=1,2, and L0\leq 1, where K1=RX,Y\vert S(D1,D2)-RY\vert S(D2)-RX\vert Y,S(D1) and K2=RX,Y\vert S(D1,D2)-RX\vert S(D1)-RY\vert X,S(D2). When the sources and side information have a jointly Gaussian distribution, we give upper bounds of K1 and K2 by a function of conditional correlation coefficient \rho XY\vert S. For a special case when there is no side information, our result tightens Feng's rate loss bounds. Using our upper bounds of the rate loss, we give good approximations of the achievable region. [ABSTRACT FROM PUBLISHER]

In this paper, a technique on constructing nonlinear resilient Boolean functions is described. By using several sets of disjoint spectra functions on a small number of variables, an almost optimal resilient function on a large even number of variables can be constructed. It is shown that given any m, one can construct infinitely many n-variable (n even), m-resilient functions with nonlinearity > 2n - 1 - 2n-2 A large class of highly nonlinear resilient functions which were not known are obtained. Then one method optimize the degree of the constructed functions is proposed. Last, an improved version of the main construction is given. [ABSTRACT FROM AUTHOR]

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto--Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary. [ABSTRACT FROM AUTHOR]

In this paper, we present two optimal binary families of sequences of length 2n - 1 and 2(2n - 1) for odd integer n. They are obtained as the images of recently proposed optimal quaternary sequences under the most significant bit and the Gray maps. The first family has 2n + 1 sequences of length 2n - 1 and the identical correlation distribution to that of Gold sequences and Gold-like sequences, and the second family of sequences of length 2(2n -1) has 2n sequences and the same correlation values as those of Kerdock sequences. [ABSTRACT FROM AUTHOR]

A constant-amplitude code is a code that reduces the peak-to-average power ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to the favorable value 1. In this paper, quaternary constant-amplitude codes (codes over Z4) of length 2m with error-correction capabilities are studied. These codes exist for every positive integer m, while binary constant-amplitude codes cannot exist if m is odd. Every word of such a code corresponds to a function from the binary m-tuples to Z4 having the bent property, i.e., its Fourier transform has magnitudes 2m/2. Several constructions of such functions are presented, which are exploited in connection with algebraic codes over Z4 (in particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to construct families of quaternary constant-amplitude codes. Mappings from binary to quaternary constant-amplitude codes are presented as well. [ABSTRACT FROM AUTHOR]

The compress-and-forward (CF) strategy achieves the optimal diversity—multiplexing tradeoff (DMT) of a three-node half-duplex relay network in slow fading, under the assumption that the relay has perfect knowledge of all three channel coefficients and that the relay makes use of Wyner—Ziv (WZ) source coding with side information. This paper studies the achievable DMT of the same network when the relay is constrained to make use of standard (non-WZ) source coding. Under a short-term power constraint at the relay, using source coding without side information results in a significant loss in terms of the DMT. For multiplexing gains τ ≤ ⅔,this loss can be fully compensated for by using power control at the relay. On the contrary, for τ ∈ (≤, 1), the loss with respect to WZ coding remains significant. [ABSTRACT FROM AUTHOR]

In this paper, the weight distributions of two classes of linear codes based on all known explicit perfect nonlinear functions from Fqm to itself are determined using a unified approach. All the minimal codewords of these codes are characterized according to their weights, which suggests that their covering structures are determined. Finally, all the minimal access sets of the secret sharing schemes based on their dual codes are obtained. [ABSTRACT FROM AUTHOR]

The problem of computing functions of values at the nodes in a network in a fully distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend, in general, to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the sub-routine yields a complete fully distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme. [ABSTRACT FROM AUTHOR]

A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term "generalized sequential hash functions." We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest. [ABSTRACT FROM AUTHOR]

In a recent paper [1], it is shown that the restrictions of bent functions to subspaces of codimension 1 and 2 are highly nonlinear. Here, we present an extensive study of the restrictions of bent functions to affine subspaces. We propose several methods which are mainly based on properties of the derivatives and of the dual of a given bent function. We solve an open problem due to Hou [2]. We especially describe the connection, for a bent function, between the Fourier spectra of its restrictions and the decompositions of its dual. Most notably, we show that the Fourier spectra of the restrictions of a bent function to the subspaces of codimension 2 can be explicitly derived from the Hamming weights of the second derivatives of the dual function. The last part of the paper is devoted to some infinite classes of bent functions which cannot be decomposed into four bent functions. [ABSTRACT FROM AUTHOR]

This paper considers iterated hash functions. It proposes new constructions of fast and secure compression functions with nl-bit outputs for integers n > 1 based on error-correcting codes and secure compression functions with l-bit outputs. This leads to simply and practical hash functions constructions based on block ciphers such as Data Encryption Standard (DES), where the key size is slightly smaller than the block size; IDEA, where the key size is twice the block size; Advanced Encryption Standard (AES), with a variable key size; and to MD4-like hash functions. Under reasonable assumptions about the underlying compression function and/or block cipher, it is proved that the new hash functions are collision resistant. More precisely, a lower bound is shown on the number of operations to find a collision as a function of the strength of the underlying compression function. Moreover, some new attacks are presented that essentially match the presented lower bounds. The constructions allow for a large degree of internal parallelism. The limits of this approach are studied in relation to bounds derived in coding theory. [ABSTRACT FROM AUTHOR]

Planar functions over finite fields give rise to finite projective planes. They were also used in the constructions of DES-like iterated ciphers, error-correcting codes, and codebooks. They were originally defined only in finite fields with odd characteristic, but recently Zhou introduced pesudo-planar functions in even characteristic, which yields similar applications. All known pesudo-planar functions are quadratic, and hence, they give presemifields. In this paper, a new approach to constructing quadratic pseudo-planar functions is given. Then, five explicit families of pseudo-planar functions are constructed, one of which is a binomial, two of which are trinomials, and the other two are quadrinomials. All known pesudo-planar functions are revisited, some of which are generalized. These functions not only lead to projective planes, relative difference sets, and presemifields, but also give optimal codebooks meeting the Levenstein bound, complete sets of mutually unbiased bases and compressed sensing matrices with low coherence. [ABSTRACT FROM PUBLISHER]

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters. [ABSTRACT FROM PUBLISHER]

In this paper, an amplification of the Cusick-Cheon conjecture on balanced Boolean functions in the cosets of the binary Reed—Muller code R1VI(k, m) of order k and length 2m, in the cases where k = 1 or k ≥ (m - 1)/2, is proved. [ABSTRACT FROM AUTHOR]

In this paper, a large class of universal windows for Gabor frames (Weyl–Heisenberg frames) is constructed. These windows have the fundamental property that every overcritical rectangular lattice generates a Gabor frame. Likewise, every undercritical rectangular lattice generates a Riesz sequence. [ABSTRACT FROM PUBLISHER]

Source coding with a side information “vending machine” is a recently proposed framework in which the statistical relationship between the side information and the source, instead of being given and fixed as in the classical Wyner–Ziv problem, can be controlled by the decoder. This control action is selected by the decoder based on the message encoded by the source node. Unlike conventional settings, the message can thus carry not only information about the source to be reproduced at the decoder, but also control information aimed at improving the quality of the side information. In this paper, the analysis of the tradeoffs between rate, distortion, and cost associated with the control actions is extended from the previously studied point-to-point setup to two basic multiterminal models. First, a distributed source coding model is studied, in which two encoders communicate over rate-limited links to a decoder, whose side information can be controlled. The control actions are selected by the decoder based on the messages encoded by both source nodes. For this setup, inner bounds are derived on the rate-distortion-cost region for both cases in which the side information is available causally and noncausally at the decoder. These bounds are shown to be tight under specific assumptions, including the scenario in which the sequence observed by one of the nodes is a function of the source observed by the other and the side information is available causally at the decoder. Then, a cascade scenario in which three nodes are connected in a cascade and the last node has controllable side information is also investigated. For this model, the rate-distortion-cost region is derived for general distortion requirements and under the assumption of causal availability of side information at the last node. [ABSTRACT FROM AUTHOR]

Carlet and colleagues conjectured that for any almost bent (AB) function F, there exists a linear function L such that F+L is a permutation. Budaghyan and colleagues found a new class of AB functions which is extended affine (EA)-inequivalent to any power functions and can also serve as a counterexample for the conjecture. They checked with the help of a computer that there are no linear functions L on F2^{5} such that x^2^i+1+(x^2^i+x) Tr (x^2^i+1+x)+L(x) is a permutation. In this paper, we prove that there are no permutations EA-equivalent to the AB function x^2^i+1+(x^2^i+x) Tr (x^2^i+1+x) on F2^{2m+1} for any m \geq 2 and there are no permutations EA-equivalent to the APN function x^2^i+1+(x^2^i+x+1) Tr (x^2^i+1) on \BBF2^{2m} for m \geq 2 either. Furthermore, we present some results about characterizations of permutation polynomials of the type L(x^2^i+1)+L^\prime(x) on \BBF2^{2m}, which is essential in the construction of functions Carlet–Charpin–Zinoviev-equivalent to the Gold functions. We obtain all the linear functions L(x) such that x+L(x^2^i+1) is a permutation on \BBF2^{2m} when \vert \ker (L)\vert \geq 2^2m-2. [ABSTRACT FROM AUTHOR]

There is no generally accepted definition of conditional Rényi entropy. The (unconditional) Rényi entropy depends on a parameter \alpha , which for the case of min-entropy takes the value \infty . Even for this particular case, there are several proposals for the definition of conditional entropy. This paper describes three general definitions of conditional Rényi entropy that were found or suggested in the literature. Their properties are studied and their values, as a function of \alpha , are compared. The particular case of min-entropy is widely used in cryptography as a security parameter; this case is studied in some detail. [ABSTRACT FROM PUBLISHER]

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and coding theory. In this paper, we extensively investigate the link between the semibentness property of functions in univariate forms obtained via Dillon and Niho functions and Kloosterman sums. In particular, we show that zeros and the value four of binary Kloosterman sums give rise to semibent functions in even dimension with maximum degree. Moreover, we study the semibentness property of functions in polynomial forms with multiple trace terms and exhibit criteria involving Dickson polynomials. [ABSTRACT FROM AUTHOR]

We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution (f(\cal X)\vert \cal X), for some function f and some distribution \cal X, and we say that such a source has computational min-entropy k if any circuit of size 2^k can only predict f(x) correctly with probability at most 2^-k given input x sampled from \cal X. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multisource extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in computational learning theory: learning linear functions under arbitrary distribution with adversarial noise, and we provide a learning algorithm for this problem. In fact, this problem is a well-recognized one in computational learning theory and variants of this problem have been studied intensively before. Thus, in addition to its application to extractors, our learning algorithm also has independent interest of its own, and it can be considered as the main technical contribution of this paper. [ABSTRACT FROM PUBLISHER]

This paper discusses two classes of symmetric Boolean functions. For each class, a necessary and sufficient condition for having optimum algebraic immunity is proposed. The algebraic degree and nonlinearity of the Boolean functions are also completely determined. And then we prove several of Braeken's conjectures about the algebraic degree and nonlinearity of the Boolean functions with optimum algebraic immunity in the two classes. [ABSTRACT FROM AUTHOR]