Search

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

Boolean functions, coding theory and $t$ -designs have close connections and interesting interplay. A standard approach to constructing $t$ -designs is the use of linear codes with certain regularity. The Assmus-Mattson Theorem and the automorphism groups are two ways for proving that a code has sufficient regularity for supporting $t$ -designs. However, some linear codes hold $t$ -designs, although they do not satisfy the conditions in the Assmus-Mattson Theorem and do not admit a $t$ -transitive or $t$ -homogeneous group as a subgroup of their automorphisms. The major objective of this paper is to develop a theory for explaining such codes and obtaining such new codes and hence new $t$ -designs. To this end, a general theory for punctured and shortened codes of linear codes supporting $t$ -designs is established, a generalized Assmus-Mattson theorem is developed, and a link between 2-designs and differentially $\delta $ -uniform functions and 2-designs is built. With these general results, binary codes with new parameters and explicit weight distributions are obtained, new 2-designs and Steiner system $S(2, 4, 2^{n})$ are produced in this paper. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN 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]

An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$ being involutions over the finite field ${\mathbb F}_{q}$ , where $r\geq 1$ and $s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ from given involutions over some subgroups of ${\mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ are obtained. [ABSTRACT FROM AUTHOR]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert–Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert–Varshamov bound asymptotically by a factor \log (n), when the code length n goes to infinity. [ABSTRACT FROM PUBLISHER]

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity I(W) of any given binary-input discrete memoryless channel (B-DMC) W. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of N independent copies of a given B-DMC W, a second set of N binary-input channels {WN(i) : 1 ≤ i ≤ N} such that, as N becomes large, the fraction of indices i for which I(WN(i) is near 1 approaches I(W) and the fraction for which I(WN(i) is near 0 approaches 1 - I(W). The polarized channels (WN(i) are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC W with I(W) > 0 and any target rate R < I(W), there exists a sequence of polar codes {ℭn; n ≥ 1} such that ℭn has block-length N = 2n, rate ≥ R, and probability of block error under successive cancellation decoding bounded as Pe (N, R) ≥ O(N-1/4) independently of the code rate. This performance is achievable by encoders and decoders with complexity O (N log N) for each. [ABSTRACT FROM AUTHOR]

The notion of tweakable block ciphers was formally introduced by Liskov--Rivest--Wagner at Crypto 2002 (the 2002 Annual International Cryptology Conference). The extension and the first construction, called CMC, of this notion to tweakable enciphering schemes which can handle variable length messages was given by Halevi--Rogaway at Crypto 2003. In this paper, we present HCH, which is a new construction of such a scheme. The construction uses two universal hash computations with a counter mode of encryption in-between. This approach was first proposed by McGrew--Viega to build a scheme called XCB and later used by Wang-Feng-Wu, to obtain a scheme called HCTR. A unique feature of HCH compared to all known tweakable enciphering schemes is that HCH uses a single key, can handle arbitrary length messages, and has a quadratic security bound. An important application of a tweakable enciphering scheme is disk encryption. HCH is well suited for this application. We also describe a variant, which can utilize precomputation and makes one less block cipher call. This compares favorably to other hash-encrypt-hash-type constructions, supports better key agility and requires less key material. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the theorem given by R. M. Wilson about weights modulo pt in linear codes to a divisible code version. Using a similar idea, we give an upper bound for the dimension of a divisible code by some divisibility property of its weight enumerator modulo pe. We also prove that this bound im- plies Ward's bound for divisible codes. Moreover, we see that in some cases, our bound gives better results than Ward's bound. [ABSTRACT FROM AUTHOR]

In this paper, a general space-frequency (SF) block code structure is proposed that can guarantee full-rate (one channel symbol per subcarrier) and full-diversity transmission in multiple-input multiple-output-orthogon frequency-division multiplexing (MIMO-OFDM) systems. The proposed method can be used to construct SF codes for an arbitrary number of transmit antennas, any memoryless modulation and arbitrary power-delay profiles. Moreover, assuming that the power-delay profile is known at the transmitter, we devise an interleaving method to maximize the overall performance of the code. We show that the diversity product can be decomposed as the product of the "intrinsic" diversity product, which depends only on the used signal constellation and the code design, and the "extrinsic" diversity product, which depends only on the applied interleaving method and the power delay profile of the channel. Based on this decomposition, we pro- pose an interleaving strategy to maximize the "extrinsic" diversity product. Extensive simulation results show that the proposed SF codes outperform the previously existing codes by about 3-5 dB, and that the proposed interleaving method results in about 1-3-dR performance improvement compared to random interleaving. [ABSTRACT FROM AUTHOR]

Let p be a prime, and \lambda be a nonzero element of the finite field \mathbb Fp^{m} . The \lambda -constacyclic codes of length p^s over \mathbb Fp^{m} are linearly ordered under set-theoretic inclusion, i.e., they are the ideals \langle (x-\lambda 0)^{i} \rangle , 0 \leq i \leq p^s of the chain ring [(\mathbb Fp^{m[x]})/({\langle x^{p^{s}}-\lambda \rangle })] . This structure is used to establish the symbol-pair distances of all such $\lambda$ -constacyclic codes. Among others, all maximum distance separable symbol-pair constacyclic codes of length p^s are obtained. [ABSTRACT FROM AUTHOR]

We investigate deletion correcting codes and restricted composition codes in particular. Restricted composition codes generalize codes on permutations and multipermutations. We use graph theoretic methods to characterize codes, establish bounds on code size, and describe constructions. The substring partial order has a well-known property. For any string, the number of superstrings of a particular length depends only on the length of the original string. We generalize this property to take compositions into account. For any string, the number of superstrings of a particular composition depends only on the composition of the original string. We present a bijective proof of this fact. We apply this result to obtain a lower bound on the size of restricted composition codes. We obtain an upper bound by analyzing deletion errors when the composition of deleted symbols is restricted to a particular worst case composition. We construct binary restricted composition single-deletion correcting codes and show that they are asymptotically optimal and form an optimal coloring. There is a natural distance on compositions that provides a lower bound on deletion distance. Unrestricted deletion correcting codes can be constructed from the union of restricted composition codes as long as the set of compositions used themselves form a code. The nonbinary single-deletion correcting codes constructed by Tenengolts are a special case of our method. [ABSTRACT FROM PUBLISHER]

A coding scheme for write once memory (WOM) using polar codes is presented. It is shown that the scheme achieves the capacity region of noiseless WOMs when an arbitrary number of multiple writes is permitted. The encoding and decoding complexities scale as O(N \log \; N), where N is the blocklength. For N sufficiently large, the error probability decreases subexponentially in N. The results can be generalized from binary to generalized WOMs, described by an arbitrary directed acyclic graph, using nonbinary polar codes. In the derivation, we also obtain results on the typical distortion of polar codes for lossy source coding. Some simulation results with finite length codes are presented. [ABSTRACT FROM AUTHOR]

We present a general construction of asymmetric quantum codes based on additive codes under the trace Hermitian inner product. Various families of additive codes over \BBF 4 are used in the construction of many asymmetric quantum codes over \BBF 4. [ABSTRACT FROM PUBLISHER]

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention oil a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras. [ABSTRACT FROM AUTHOR]

Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite-alphabet are being compressed into binary sequences by some one-to-one mapping. No a priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that if the universal Lempel--Ziv (LZ) data compression algorithm is successively applied to N-blocks then the best error-free compression, for the particular individual sequence X is achieved as N tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. It is demonstrated that context tree coding essentially achieves it. Next, consider a device called classifier (or discriminator) that observes an individual training sequence X. The classifier's task is to examine individual test sequences of length N and decide whether the test N-sequence has the same features as those that are captured by the training sequence X, or is sufficiently different, according to some appropriate criterion. Here again, it is demonstrated that a particular universal context classifier with a storage-space complexity that is linear in N, is essentially optimal. This may contribute a theoretical "individual sequence" justification for the Probabilistic Suffix Tree (PST) approach in learning theory and in computational biology. [ABSTRACT FROM AUTHOR]

Let p be a prime such that p 1 (mod 8). Let k = (p + 1)/2 and write k = 2mq, q odd. Let S = F2[x]/(1 +-xk) where F2 is the Galois field of two elements. We prove that the binary extended quadratic residue codes of length 2k have a double circulant presentation in the following cases: 1) q = 1, and 2) let X be the class of x in S, and σ the algebra of automorphisms on S that sends Xi to Xi. Factor 1 xq over F2 into irreducible factors. If the class of those factors in S is fixed by σ up to a unit, then the codes have a double circulant presentation. [ABSTRACT FROM AUTHOR]

ln this correspondence, it is shown that some convolutional codes with distinct memory sizes of minimal encoders are equivalent in the sense that the minimal trellises of these codes are the shifted versions of one another. For an (n, k) binary convolutional code, the weight spectrum obtained from the minimal trellis may be slightly different from that obtained from the conventional code trellis with n-bit branches. Code search is conducted to find some good (n, n - 1) binary convolutional codes. Bounds on the trellis complexity, measured by the number of states and the number of branches in the minimal trellis module, of any convolutional code and its equivalent codes are also derived. [ABSTRACT FROM AUTHOR]

In this correspondence, we prove that the probability distribution induced on the leaves of a Tunstall parse tree for a given source is a (unique) lower bound in the partially ordered set of the probability distributions induced by all possible parse trees with a same number of leaves, and ordered according to the majorization partial order. We apply this result to the problem of optimally approximating a uniform distribution with flips of a biased coin. [ABSTRACT FROM AUTHOR]

There exist two important design criteria for unitary space time codes. In the situation where the signal-to-noise ratio (SNR) is large the diversity product (DP) of a constellation should be as large as possible. It is less known that the diversity sum (DS) is a very important design criterion for codes working in a low SNR environment. So far, no general method to design good-performing constellations with large diversity for any number of transmit antennas and any transmission rate exists. In this correspondence, we propose constellations with suitable structures, which allow one to construct codes with excellent diversity using geometrical symmetry and numerical methods. The presented design methods work for any dimensional constellation and for any transmission rate. [ABSTRACT FROM AUTHOR]

Average case universal compression of independent and identically distributed (i.i.d.) sources is investigated, where the source alphabet is large, and may be sublinear in size or even larger than the compressed data sequence length n. In particular, the well-known results, including Rissanen's strongest sense lower bound, for fixed-size alphabets are extended to the case where the alphabet size k is allowed to grow with n. It is shown that as long as k = o(n), instead of the coding cost in the fixed-size alphabet case of 0.5 log n extra code bits for each one of the k - 1 unknown probability parameters, the cost is now 0.5 log(n/k) code bits for each unknown parameter. This result is shown to be the lower bound in the minimax and maximin senses, as well as for almost every source in the class. Achievability of this bound is demonstrated with two-part codes based on quantization of the maximum-likelihood (ML) probability parameters, as well as by using the well-known Krichevsky-Trofimov (KT) low-complexity sequential probability estimates. For very large alphabets, k » n, it is shown that an average minimax and maximin bound on the redundancy is essentially (to first order) log(k/n) bits per symbol. This bound is shown to be achievable both with two-part codes and with a sequential modification of the KT estimates. For k = Θ(n), the redundancy is Θ(1) bits per symbol. Finally, sequential codes are designed for coding sequences in which only m < min{k, n} alphabet symbols occur. [ABSTRACT FROM AUTHOR]

We extend the setting of two-stage lossy source coding with successive refinement structures into a joint source-channel coding setting. In particular, we consider a problem where two descriptions of a memoryless source are to be transmitted across two independent memoryless channels and where the output of the channel corresponding to the first (coarse) description is also available to the decoder of the second (refinement) decoder. Side information (SI), correlated to the source, may also be available to the decoders. In such a case, we confine attention to degraded SI, in the sense that the source, the SI available at the refinement decoder, and the SI available at the coarse decoder form a Markov chain in this order. Our first result is a separation theorem asserting that in the limit of long blocks, no optimality is lost by first applying lossy successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source and the SI. It is also shown that (even noiseless) feedback from the output of the first channel to the input of the second encoder cannot improve performance, but may sometimes significantly facilitate the implementation of optimum codes. We provide two examples where single-letter codes (of unit block length) achieve optimum performance, if feedback from the channel output of the first stage is provided to the encoder of the refinement stage. In one of these examples, it is evident that if feedback is not provided, optimality cannot be achieved with unit length code. Motivated by these examples, we then investigate single-letter codes for this system. Necessary and sufficient conditions are furnished for the optimality of single-letter codes with and without feedback. A corollary of these conditions is that for the quadratic distortion measure, feedback is necessary to achieve optimality in single-letter codes, regardless of the source distribution and the channel statistics. [ABSTRACT FROM AUTHOR]

This correspondence revisits the idea of constructing a binary [m n, mk] code from an [n, k] code over F2m by concatenating the code with a suitable basis representation of F2m over F2. We construct two nonequivalent examples of doubly even self-dual binary codes of length 160 which turn out to be of minimum distance 24. This improves the lower bound for this class of codes, whereas the upper bound Is given by 28. The construction at hand seems to be of interest beyond this particular example. [ABSTRACT FROM AUTHOR]

We show that the list decoding procedure of Guruswami and Sudan may be used to decode generalized Reed-Solomon (RS) codes defined over commutative rings with identity. An algorithm for performing the first of the two phases of this decoding procedure is also given. In particular, we show that for generalized RS codes over chain rings, the probability of picking an incorrect codeword from a given list can be reduced by increasing the size of the code alphabet while keeping the length and minimum (Hamming) distance of the code constant. [ABSTRACT FROM AUTHOR]

A lower bound is derived on the achievable redundancy for universal lessless coding of parametric sources with piecewise stationary, abruptly changing, occasionally repeating statistical parameter vectors (or states) is not too large, for any uniquely decipherable code, for almost every set of states that govern all the different segments in the data sequence, for almost every arrangement of these states in the different segments, and for almost every vector of transition times, the minimum achievable redundancy is composed of 0.5 log d extra code bits for each unknown transition time, and log s extra code bits for each repetition of a state, where d is the average duration of each state in the input string, m is the average length of a segment, and s is the total number of states. If s is essentially large compared to m, it is shown that the minimum redundancy is composed of 0.5 log m bits for each unknown component in each segment and log m bits for each unknown transition time, which is the same lower bound as that of general piecewise stationary sources (PSSs). These results are true also in the minimax and maximin senses. The lower bound is shown to be achievable through construction of mixture and estimation based codes. Different special cases are reviewed, and it is shown that unless s is essentially large compared to m, optimal codes that are designed particularly for sources with repeating statistics. In particular, the bound for general PSSs is shown to be a special case of the new bound. [ABSTRACT FROM AUTHOR]

Given positive integers n and d, let A2 (n, d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A2(n, d) &ges; 2n/V(n, d-1), where V(n, d) = Σi=0d (in) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that [This equation can not be represented in ASCII.TXT] whenever d/n &les; 0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed. [ABSTRACT FROM AUTHOR]

Lower bounds on the state complexity of linear tail-biting trellises are presented. One bound generalizes the total-span bound, while another bound can be regarded as a generalization of the cut-set bound. It is shown by examples that the new bounds may be tighter than any of the existing lower bounds. [ABSTRACT FROM AUTHOR]

We construct error-correcting (nonlinear) binary codes using a construction of Bose and Chowla in additive number theory. Our method extends a construction of Graham and Sloane for constant weight codes. The new codes improve 1028 of the 7168 best known h-error-correcting codes of word length ≤ 512 with 1 ≤ h ≤ 14. We give asymptotical comparisons to shortened Bose-Chaudhuri-Hocquenghem (BCH) codes. [ABSTRACT FROM AUTHOR]

Derives the bounds on the number of errors that can be corrected by list decoding of maximum-distance separable codes using small lists. Upper bound for specific codes; Details on an upper bound for randomly chosen codes; Comments on list decoding.

Presents the greedy and heuristic algorithms used in codes and coloring problems. Review of the partitioning methods for constant weight codes and asymmetric codes; Brief discussion of the main heuristic used; Methods that can be applied to further improve the outcomes of the algorithms.