Search

In this paper, we provide the left and right Parseval relations over the quaternions. Moreover, we construct a new infinite family of sequences almost over $Q_{8} $ with period $p$ by a generalization of Legendre mapping, where $p\equiv 1 \pmod {8}$ is prime and the sequences have ideal autocorrelation. The sequences are symmetric when $p\equiv 1 \pmod {16}$ , and antisymmetric when $p\equiv 9 \pmod {16} $. [ABSTRACT FROM AUTHOR]

For a function $f$ from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{n}$ , the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an “intermediate” concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it conveys a detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges. [ABSTRACT FROM AUTHOR]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

Bazzi and Mitter showed that binary dihedral group codes are asymptotically good. In this paper we prove that the dihedral group codes over any finite field with strong duality property are asymptotically good. If the characteristic of the field is even, self-dual dihedral group codes are asymptotically good. If the characteristic of the field is odd, maximal self-orthogonal dihedral group codes and LCD dihedral group codes are asymptotically good. [ABSTRACT FROM AUTHOR]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

Hermitian functional and differential codes are AG-codes defined on a Hermitian curve. To ensure good performance, the divisors defining such AG-codes have to be carefully chosen, exploiting the rich combinatorial and algebraic properties of the Hermitian curves. In this paper, the case of differential codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ on the Hermitian curve $\mathscr {H}_{q^{3}}$ defined over $\mathbb {F}_{q^{6}}$ is worked out where $\mathop {\mathrm {supp}}\nolimits (\mathtt {T}):= \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{2}})$ , the set of all $\mathbb {F}_{q^{2}}$ -rational points of $\mathscr {H}_{q^{3}}$ , while $\mathtt {D}$ is taken, as usual, to be the sum of the points in the complementary set $D = \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{6}})\setminus \mathscr {H} _{q^{3}}(\mathbb {F}_{q^{2}})$. For certain values of $m$ , such codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ have better minimum distance compared with true values of 1-point Hermitian codes. The automorphism group of $C_{L}(\mathtt {D},m\mathtt {T})$ , $m\leq q^{3}-2$ , is isomorphic to $PGU(3,q)$. [ABSTRACT FROM AUTHOR]

Let $m$ be an arbitrary positive integer and $D_{8m}$ be the dihedral group of order $8m$ , i.e., $D_{8m}=\langle x,y\mid x^{4m}=1, y^{2}=1, yxy=x^{-1}\rangle $. Left ideals of the dihedral group algebra $\mathbb {F}_{2}[D_{8m}]$ are called binary left dihedral codes of length $8m$ , and abbreviated as binary left $D_{8m}$ -codes. In this paper, we give an explicit representation and enumeration for all distinct self-dual binary left $D_{8m}$ -codes. These codes make up an important class of self-dual binary $[8m,4m]$ -codes such that the dihedral group $D_{8m}$ is necessarily a subgroup of the automorphism group of each code. In particular, we provide recursive algorithms to solve congruence equations over finite chain rings for constructing all distinct self-dual binary left $D_{8m}$ -codes and obtain a Mass formula to count the number of all these self-dual codes. As a preliminary application, we obtain the extremal self-dual binary $[{48,24,12}]$ -code and an extremal self-dual binary $[{56,28,12}]$ -code from self-dual binary left $D_{48}$ -codes and left $D_{56}$ -codes respectively. [ABSTRACT FROM AUTHOR]

Let $\Bbb F_{q}$ be a finite field with $q$ elements and $p$ be a prime with $\gcd (p,q)=1$. Let $G$ be a finite abelian $p$ -group and $\Bbb F_{q}(G)$ be a group algebra. In this paper, we find all primitive idempotents and minimal abelian group codes in the group algebra $\Bbb F_{q}(G)$. Furthermore, we give all LCD abelian codes (linear code with complementary dual) and self-orthogonal abelian codes of $\Bbb F_{q}(G)$. [ABSTRACT FROM AUTHOR]

This paper addresses the question of achieving capacity with lattice codes in multi-antenna block fading channels when the number of fading blocks tends to infinity. A design criterion based on the normalized minimum determinant is proposed for division algebra multi-block space-time codes over fading channels; this plays a similar role to the Hermite invariant for Gaussian channels. Under maximum likelihood decoding, it is shown that this criterion is sufficient to guarantee transmission rates within a constant gap from capacity both for deterministic channels and ergodic fading channels. Moreover, if the number of receive antennas is greater than or equal to the number of transmit antennas, the same constant gap is achieved under naive lattice decoding as well. In the case of independent identically distributed Rayleigh fading, the error probability vanishes exponentially fast. In contrast to the standard approach in the literature, which employs random lattice ensembles, the existence results in this paper are derived from the number theory. First, the gap to capacity is shown to depend on the discriminant of the chosen division algebra; then, class field theory is applied to build families of algebras with small discriminants. The key element in the construction is the choice of a sequence of division algebras whose centers are number fields with small root discriminants. [ABSTRACT FROM AUTHOR]

Let $G$ be a finite abelian group. If $f: G\rightarrow {\mathbf{C}} $ is a nonzero function with Fourier transform $\hat {f}$ , the Donoho-Stark uncertainty principle states that $| {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G|$. The purpose of this paper is twofold. First, we present the shift bound for abelian codes with a streamlined proof. Second, we use the shifting technique to prove a generalization and a sharpening of the Donoho-Stark uncertainty principle. In particular, if $f: G\rightarrow {\mathbf{F}} $ is a non-zero function from $G$ to a field ${\mathbf{F}}$ , and if $f$ has a Fourier transform $\hat {f}$ , the sharpened uncertainty principle states that $| {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G|+| {\mathrm{ supp}}(f)|-|H({\mathrm{ supp}}(f))|$ , where $H({\mathrm{ supp}}(f))$ is the stabilizer of ${\mathrm{ supp}}(f)$ in $G$. [ABSTRACT FROM AUTHOR]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

This paper considers space-time coding over several independently Rayleigh faded blocks. In particular, we will concentrate on giving upper bounds for the coding gain of lattice space-time codes as the number of blocks grow. This problem was previously considered in the single antenna case by Bayer-Fluckiger et al. in 2006. Crucial to their work was Odlyzko’s bound on the discriminant of an algebraic number field, as this provides an upper bound for the normalized coding gain of number field codes. In the MIMO context natural codes are constructed from division algebras defined over number fields and the coding gain is measured by the discriminant of the corresponding (noncommutative) algebra. In this paper, we will develop analogues of the Odlyzko bounds in this context and show how these bounds limit the normalized coding gain of a very general family of division algebra based space-time codes. These bounds can also be used as benchmarks in practical code design and as tools to analyze asymptotic bounds of performance as the number of independently faded blocks increases. [ABSTRACT FROM AUTHOR]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kind of dual conditions. The hyperlogarithmic growth of maximal repetition has been experimentally observed for texts in natural language, whereas the power-law growth of topological entropy implies a vanishing Shannon entropy rate and thus probably does not hold for natural language. In this paper, we provide a constructive example of regular Hilberg processes, which we call random hierarchical association (RHA) processes. Our construction does not apply the standard cutting and stacking method. For the constructed RHA processes, we demonstrate that the expected length of any uniquely decodable code is the orders of magnitude larger than the Shannon block entropy of the ergodic component of the RHA process. Our proposition supplements the classical result by Shields concerning nonexistence of universal redundancy rates. [ABSTRACT FROM PUBLISHER]

Let p be an odd prime number, e an integer greater than 1, and \bf Z/(p^e) the integer residue ring modulo p^e. In this paper, we obtain an improved result of the previous paper (IEEE Trans. Inf. Theory, 56(1) (2010) 555–563) on distribution properties of compressing sequences derived from primitive sequences over \bf Z/(p^e). It is shown that two primitive sequences \underlinea and \underlineb generated by a strongly primitive polynomial f\left(x\right) over \bf Z/(p^e) are the same, if there exist s\in\bf Z/(p) and k\in\bf Z/(p)^\ast such that the distribution of s in their compressing sequences \underlineae-1+\eta (\underlinea0,\ldots,\underlineae-2) and \underlinebe-1+\eta (\underlineb0,\ldots,\underlinebe-2) is coincident at the positions t with \alpha (t)=k, where \eta\left(x0,\ldots,xe-2\right) is an (e-1)-variable polynomial over \bf Z/(p) with the coefficient of xe-2^{p-1}\cdots x1^{p-1}x0^{p-1} not equal to \left(-1\right)^e\cdot\left(p+1\right)/2 and \underline\alpha is an m-sequence over \bf Z/(p) determined by f(x) and \underlinea. Compared with the previous result, this gives a more precise characterization on the positions of a compressing sequence, i.e., of the form \underlineae-1+\eta (\underlinea0,\ldots,\underlineae-2), derived from a primitive sequence \underlinea over \bf Z/(p^e) that completely determines \underlinea. In particular, the result is also true for the highest level sequence \underlineae-1 by taking \eta (x0,\ldots,xe-2)=0. [ABSTRACT FROM AUTHOR]

In this paper, a new construction of zero-difference balanced functions defined on \BBZv is given, where v is an odd positive integer. Based on the generic constructions proposed by Ding, optimal constant composition codes and perfect difference systems of sets with new parameters can be generated from the zero-difference balanced functions constructed in this paper. [ABSTRACT FROM AUTHOR]

In this paper, an application of the theoretical algebraic notion of a separable ring extension in the realm of cyclic convolutional codes or, more generally, ideal codes, is investigated. It is worked under very mild conditions that cover all previously known as well as new non-trivial examples. It is proved that ideal codes are direct summands, as left ideals, of the underlying non-commutative algebra, in analogy with cyclic block codes. This implies, in particular, that they are generated by a non-commutative idempotent polynomial. Hence, by using a suitable separability element, an efficient algorithm for computing one of such idempotents is designed. We show that such an idempotent generator polynomial can be used to get information on the free distance of the convolutional code. [ABSTRACT FROM AUTHOR]

In a system that performs both encryption and lossy compression, the conventional way is to compress first and then encrypt the compressed data. This separation approach has been proved to be optimal. In certain applications where sensitive information should be protected as early as possible, it is preferable to perform the encryption first and then compress the encrypted data, which leads to the concept of the reversed system. Johnson et al. proposed an achievable scheme for the reversed system, where a modulo-sum encryption is followed by a compression using the Wyner–Ziv distributed source coding with side information. However, in general, this reversed system performs worse than the conventional system in the sense that it requires more compression rate and secrecy key rate. In this paper, we propose a new achievable scheme for the reversed system, where the encryption is conducted by a permutation cipher, and then, the encrypted data is compressed using the optimal rate-distortion code. The proposed scheme can achieve the optimal compression rate and secret key rate. As a result, we show that reversing the order of the encryption and compression does not necessarily compromise the performance of an encryption-compression system. We show that the proposed system attains strong secrecy, and the information leakage vanishes exponentially. [ABSTRACT FROM PUBLISHER]

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 classical Blahut--Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs. [ABSTRACT FROM AUTHOR]

The design requirements for space-time coding typically involves achieving the goals of good performance, high rates, and low decoding complexity. In this paper, we introduce a further constraint on space-time code design In that the code should also lead to low values of the peak-to-mean envelope power ratio (PMEPR) for each antenna. Towards that end, we propose a new class of space-time codes called the "low PMEPR space-time" (LPST) codes. The LPST codes are obtained using the properties of certain cyclotomic number fields. The LPST codes achieve a performance identical to that of the threaded algebraic space-time (TAST) codes but at a much smaller PMEPR. With M antennas and a rate of one symbol per channel use, the LPST codes lead to a decrease in PMEPR by at least a factor of M relative to a Hadamard spread version of the TAST code. For rates beyond one symbol per channel use and up to a guaranteed amount, the LPST codes have provably smaller PMEPR than the corresponding TAST codes. Additionally, with the concept of punctured LPST codes proposed in this paper, significant performance Improvement Is obtained over the full diversity TAST schemes of comparable complexity. Numerical examples are provided to illustrate the advantage of the proposed codes in terms of PMEPR reduction and performance improvement for very high rate wireless communications. [ABSTRACT FROM AUTHOR]

In this correspondence, we consider the problem of. maximizing sum rate of a multiple-antenna Gaussian broadcast channel (BC). It was recently found that dirty-paper coding is capacity achieving for this channel. In order to achieve capacity, the optimal transmission policy (i.e., the optimal transmit covariance structure) given the channel conditions and power constraint must be found. However, obtaining the optimal transmission policy when employing dirty-paper coding is a computationally complex nonconvex problem. We use duality to transform this problem into a well-structured convex multiple-access channel (MAC) problem. We exploit the structure of this problem and derive simple and fast iterative algorithms that provide the optimum transmission policies for the MAC, which can easily be mapped to the optimal BC policies. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new way of providing cyclic structures to convolutional codes. We define the skew cyclic convolutional codes as left ideals of a quotient ring of a suitable non-commutative polynomial ring. In contrast to the previous approaches to cyclicity for convolutional codes, we use Ore polynomials with coefficients in a field (the rational function field over a finite field), so their arithmetic is very well known and we may proceed similarly to cyclic block codes. In particular, we show how to obtain easily skew cyclic convolutional codes of a given dimension, and we compute an idempotent generator of the code and its dual. [ABSTRACT FROM AUTHOR]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography, and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction gives ZDB functions defined on the abelian groups (GF(q1)\times,\cdots,\timesGF(qk),+) with new and flexible parameters. The other two constructions are based on 2-cyclotomic cosets and yield ZDB functions on \BBZn with new parameters. The parameters of optimal constant composition codes, optimal, and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized. [ABSTRACT FROM PUBLISHER]

Let G be a finite Abelian group and \BBF a field such that \mathop char(\BBF ) does not divide \vert G\vert . Denote by \BBF G the group algebra of G over \BBF . A (semisimple) Abelian code is an ideal of \BBF G. Two codes \cal I1 and \cal I2 of \BBF G are G-equivalent if there exists an automorphism \psi of G whose linear extension to \BBF G maps \cal I1 onto \cal I2. In this paper, we give a necessary and sufficient condition for minimal Abelian codes to be G-equivalent and show how to correct some results in the literature. [ABSTRACT FROM PUBLISHER]

In this paper, the minimum weight and the dimension of all cyclic codes of length p^n over a field \BBFq, are computed, when p is an odd prime and \BBFq a finite field with q elements, assuming that \overlineq generates the group of invertible elements of \BBZp^{n}. Furthermore, the minimum weight and dimension of codes which are sum of two minimal codes in \BBFq(Cp\times Cp) are also computed. Finally, the efficiency of cyclic codes and noncyclic abelian codes of length p^2 are compared. [ABSTRACT FROM AUTHOR]

Network calculus (NC) is a set of rules and results for computing bounds for performance parameters of communication systems, such as end-to-end delay, maximum backlog, and service curves. Previous works show that the problem of determining performance bounds of communication networks is simplified if modeled using the dioid algebra. In this paper, we propose a methodology that allows the treatment of NC problems in a modular basis in a time-varying context, i.e., when curves vary with time. From the proposed methodology, we extend some results of the literature and derive new results on NC. Among the obtained results, we introduce an alternative representation of service guarantees that better explore the available knowledge of systems. We also define variable delay functions that lead to less conservative delay bounds than those in the literature. Finally, we analyze a FIFO multiplexer with M input flows. [ABSTRACT FROM AUTHOR]

In this paper, we study generalized Reed–Solomon codes (GRS codes) over commutative and noncommutative rings, we show that the classical Welch–Berlekamp and Guruswami–Sudan decoding algorithms still hold in this context, and we investigate their complexities. Under some hypothesis, the study of noncommutative GRS codes over finite rings leads to the fact that GRS codes over commutative rings have better parameters than their noncommutative counterparts. Also, GRS codes over finite fields have better parameters than their commutative rings counterparts. But we also show that given a unique decoding algorithm for a GRS code over a finite field, there exists a unique decoding algorithm for a GRS code over a truncated power series ring with a better asymptotic complexity. Moreover, we generalize a lifting decoding scheme to obtain new unique and list decoding algorithms designed to work when the base ring is, for example, a Galois ring or a truncated power series ring or the ring of square matrices over the latter ring. [ABSTRACT FROM AUTHOR]

This paper deals with the multiplicative finite-field matrix channel, a discrete memoryless channel whose input and output are matrices (over a finite field) related by a multiplicative transfer matrix. The model considered here assumes that all transfer matrices with the same rank are equiprobable, so that the channel is completely characterized by the rank distribution of the transfer matrix. This model is seen to be more flexible than previously proposed ones in describing random linear network coding systems subject to link erasures, while still being sufficiently simple to allow tractability. The model is also conservative in the sense that its capacity provides a lower bound on the capacity of any channel with the same rank distribution. A main contribution is to express the channel capacity as the solution of a convex optimization problem which can be easily solved by numerical computation. For the special case of constant-rank input, a closed-form expression for the capacity is obtained. The behavior of the channel for asymptotically large field size or packet length is studied, and it is shown that constant-rank input suffices in this case. Finally, it is proved that the well-known approach of treating inputs and outputs as subspaces is information-lossless even in this more general model. [ABSTRACT FROM AUTHOR]

Given the noiseless superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, the goal of this paper is to establish deterministic conditions under which exact recovery of the low-rank and sparse components becomes possible. This fundamental identifiability issue arises with traffic anomaly detection in backbone networks, and subsumes compressed sensing as well as the timely low-rank plus sparse matrix recovery tasks encountered in matrix decomposition problems. Leveraging the ability of \ell 1 and nuclear norms to recover sparse and low-rank matrices, a convex program is formulated to estimate the unknowns. Analysis and simulations confirm that the said convex program can recover the unknowns for sufficiently low-rank and sparse enough components, along with a compression matrix possessing an isometry property when restricted to operate on sparse vectors. When the low-rank, sparse, and compression matrices are drawn from certain random ensembles, it is established that exact recovery is possible with high probability. First-order algorithms are developed to solve the nonsmooth convex optimization problem with provable iteration complexity guarantees. Insightful tests with synthetic and real network data corroborate the effectiveness of the novel approach in unveiling traffic anomalies across flows and time, and its ability to outperform existing alternatives. [ABSTRACT FROM AUTHOR]

Multiple-input double-output (MIDO) codes are important in the near-future wireless communications, where the portable end-user device is physically small and will typically contain at most two receive antennas. Especially tempting is the 4\,\times\,2 channel due to its immediate applicability in the digital video broadcasting (DVB). Such channels optimally employ rate-two space-time (ST) codes consisting of (4\times 4) matrices. Unfortunately, such codes are in general very complex to decode, hence setting forth a call for constructions with reduced complexity. Recently, some reduced complexity constructions have been proposed, but they have mainly been based on different ad hoc methods and have resulted in isolated examples rather than in a more general class of codes. In this paper, it will be shown that a family of division algebra based MIDO codes will always result in at least 37.5% worst-case complexity reduction, while maintaining full diversity and, for the first time, the nonvanishing determinant (NVD) property. The reduction follows from the fact that, similarly to the Alamouti code, the codes will be subsets of matrix rings of the Hamiltonian quaternions, hence allowing simplified decoding. At the moment, such reductions are among the best known for rate-two MIDO codes refid="ref5"/, refid="ref6"/. Several explicit constructions are presented and shown to have excellent performance through computer simulations. [ABSTRACT FROM AUTHOR]

The known families of binary sequences having asymptotic merit factor 6.0 are modifications to the families of Legendre sequences and Jacobi sequences. In this paper, we show that at N=pq, there are many suitable modifications other than the Jacobi or modified Jacobi sequences. Furthermore, we will give three new modifications to the character sequences of length N=pq. Based on these new modifications, for any pair of large p and q, we can construct a binary sequence of length 2pq so that such families of sequences have asymptotic merit factor 6.0 without cyclic shifting of the base sequences. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with Hadamard matrices with a certain noncyclic property. First we show that when the first column of a Sylvester Hadamard matrix of order 2m, m≥ 2, a positive integer, is removed, the number of shift distinct row vectors in the matrix is given by 2m - m. Then, for m ≥ 4, we construct an infinite family of Hadamard matrices with a property that when the first column of the Hadamard matrix is removed, all the row vectors of the matrix are shift distinct. These Hadamard matrices are useful in constructing low correlation zone sequences. [ABSTRACT FROM AUTHOR]

In the past few years, algebraic attacks against stream ciphers with linear feedback function have been significantly improved. As a response to the new attacks, the notion of algebraic immunity of a Boolean function ƒ was introduced, defined as the minimum degree of the annihilators of ƒ and ƒ + 1. An annihilator of ƒ is a nonzero Boolean function g, such that ƒ · g = 0. While several constructions of Boolean functions with optimal algebraic immunity have been proposed, there is no significant progress concerning the resistance against the so-called fast algebraic attacks. In this paper, we provide a framework to assess the resistance of Boolean functions against the new algebraic attacks, including fast algebraic attacks. The analysis is based on the univariate polynomial representation of Boolean functions and necessary and sufficient conditions are presented for a Boolean function to have optimal behavior against all the new algebraic attacks. Finally, we introduce a new infinite family of balanced Boolean functions described by their univariate polynomial representation. By applying the new framework, we prove that all the members of the family have optimal algebraic immunity and we efficiently evaluate their behavior against fast algebraic attacks. [ABSTRACT FROM AUTHOR]

Hoffstein and Silverman suggested the use of low Hamming weight product (LHWP) exponents to accelerate group exponentiation while maintaining the security level. With LHWP exponents, the computation costs on GF(2n) or Koblitz elliptic curves can be reduced significantly, where the cost of squaring and elliptic curve doubling is much lower than that of multiplication and elliptic curve addition, respectively. In this paper, we present a parameterized splitting system with an additional property, which is a refinement version of the system introduced in PKC'08. We show that it yields an algorithm for the discrete logarithm problem (DLP) with LHWP exponents with lower complexity than that of any previously known algorithms. To demonstrate its application, we attack the GPS identification scheme modified by Coron, Lefranc, and Poupard in CHES'05 and the DLP with Hoffstein and Silverman's (2,2,11)-exponent. The time complexity of our key recovery attack against the GPS scheme is 261.82, which was expected to be 278. Hoffstein and Silverman's (2,2,11)-exponent can be recovered with a time complexity of 253.02, which is the lowest among the known attacks. [ABSTRACT FROM AUTHOR]

Various measures of security of stream ciphers have been studied that are based on the problem of finding a minimum size generator for the keystream in some special class of generators. These include linear and p-adic spans, as well as π-adic span, which is based on a choice of an element π in a finite extension of the integers. The corresponding sequence generators are known as linear feedback shift registers, feedback with carry shift registers, and the more general algebraic feedback shift registers, respectively. In this paper, the average behavior of such security measures when πd = p > 0 or π² = -p < 0 is studied. In these cases, if ℤ[π] is the ring of integers in its fraction field and is a UFD, it is shown that the average π-adic span is n - O(log(n)) for sequences with period n. [ABSTRACT FROM AUTHOR]

In this paper we construct new classes of optimal frequency-hopping sequences (FHSs) with respect to the Lempel-Greenberger bound and the Peng-Fan bound by interleaving techniques which are used to construct a sequence length kN from k sequences of length N. We first give two generic constructions for optimal FHS sets from some known optimal FHS sets by interleaving techniques and present some examples new optimal FHS sets. We then design new optimal FHSs whose parameters include those of the known optimal constructions with length kN and frequency set size N for some positive integers k and N. We also construct optimal FHS sets of length kp from power-residue sequences for any odd prime p and 2 ≤ k < In particular, our constructions give several new parameters not covered in the literature, which are summarized in Tables I and II. [ABSTRACT FROM AUTHOR]

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]

Traditional sampling theories consider the problem of reconstructing an unknown signal x from a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is that x lies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in which x lies in a union of subspaces. In this paper, we develop a general framework for robust and efficient recovery of such signals from a given set of samples. More specifically, we treat the case in which x lies in a sum of k subspaces, chosen from a larger set of m possibilities. The samples are modeled as inner products with an arbitrary set of sampling functions. To derive an efficient and robust recovery algorithm, we show that our problem can be formulated as that of recovering a block-sparse vector whose nonzero elements appear in fixed blocks. We then propose a mixed l2/l1 program for block sparse recovery. Our main result is an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal. This result relies on the notion of block restricted isometry property (RIP), which is a generalization of the standard RIP used extensively in the context of compressed sensing. Based on RIP, we also prove stability of our approach in the presence of noise and modeling errors. A special case of our framework is that of recovering multiple measurement vectors (MMV) that share a joint sparsity pattern. Adapting our results to this context leads to new MMV recovery methods as well as equivalence conditions under which the entire set can be determined efficiently. [ABSTRACT FROM AUTHOR]

In the present paper, by making use of some special properties of the Hermitian function fields, we construct multisequences with both large linear complexity and k-error linear complexity. Moreover, these sequences can be explicitly constructed. [ABSTRACT FROM AUTHOR]

In this paper, the complexity of applying a guess and determine attack to so-called Linear Feedback Shift register (LFSR)-based stream ciphers is analyzed. This family of stream ciphers uses a single or several LFSR and a filtering function F : GF(2)n → GF(2)m to generate the blocks of m ≥ 1 keystream bits at the time. In difference to a classical guess and determine attack, a method based on guessing certain bits in order to determine the remaining secret key/state bits, our approach efficiently takes advantage of the reduced preimage space for relatively large m and at the same time employing the design structure of the cipher. Several variations of the algorithm are derived to circumvent the sensitivity of attack to the input data, n, m and the key length. In certain cases, our attack outperforms classical algebraic attacks [10]; these being considered as one of the most efficient cryptanalyst tools for this type of ciphers. A superior performance of our attack over algebraic attacks is demonstrated in case the filtering function belongs to the extended Maiorana-McFarland class. [ABSTRACT FROM AUTHOR]

We consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets follows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences. [ABSTRACT FROM AUTHOR]

Frequency hopping spread spectrum and direct sequence spread spectrum are two main spread coding technologies in communication systems. Frequency hopping sequences :are needed in frequency hopping code-division multiple-access (FH-CDMA) systems, in this paper, four algebraic and a combinatorial constructions of optimal sets of frequency hopping sequences with new parameters are presented, and a number of bounds on sets of frequency hopping sequences are described. [ABSTRACT FROM AUTHOR]

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with nt transmit and nr receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an L-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number L of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity-multiplexing-delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback. In this paper, a set of sufficient conditions under which a space-time (ST) code will achieve the DMD tradeoff is presented. This is followed by two classes of explicit constructions of ST codes which meet these conditions. Constructions belonging to the first class achieve minimum delay and apply to a broad class of fading channels whenever nr ≥ nt and either L|nt or nt|L. The second class of constructions do not achieve minimum delay, hut do achieve the DMD tradeoff of the fading channel for all statistical descriptions of the channel and for all values of the parameters nr, nt, L. [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]

Frequency hopping (FH) sequences play a key role in frequency hopping spread spectrum communication systems. In order to evaluate the performance of FH sequences, Lempel and Greenberger (1974) and Peng and Fan (2004) derived lower bounds on their Hamming auto- and cross-correlations. In this paper, we construct families of FH sequences with Hamming correlations meeting those bounds by combinatorial and algebraic techniques. We first construct optimal families consisting of a single FH sequence with maximum Hamming correlation equal to 2 from a combinatorial approach. Then we investigate families consisting of multiple FH sequences. We provide a combinatorial characterization for such families, and present a recursive method to construct them by means of this characterization. We also describe two algebraic constructions for such families of FH sequences, gerteralizing those of Ding, Moisio, and Yuan (2007). As a consequence, many new optimal families of FH sequences are obtained. [ABSTRACT FROM AUTHOR]