Search

Error-correcting output coding (ECOC) is a method for constructing a multi-valued classifier using a combination of given binary classifiers. ECOC can estimate the correct category by other binary classifiers even if the output of some binary classifiers is incorrect based on the framework of the coding theory. The code word table representing the combination of these binary classifiers is important in ECOC. ECOC is known to perform well experimentally on real data. However, the complexity of the classification problem makes it difficult to analyze the classification performance in detail. For this reason, theoretical analysis of ECOC has not been conducted. In this study, if a binary classifier outputs the estimated posterior probability with errors, then this binary classifier is said to be noisy. In contrast, if a binary classifier outputs the true posterior probability, then this binary classifier is said to be noiseless. For a theoretical analysis of ECOC, we discuss the optimality for the code word table with noiseless binary classifiers and the error rate for one with noisy binary classifiers. This evaluation result shows that the Hamming distance of the code word table is an important indicator. [ABSTRACT FROM AUTHOR]

Let R be a Galois ring, G R (p n , r) , of characteristic p n and of order p n r . In this article, we study cyclic codes of arbitrary length, N, over R. We use discrete Fourier transform (DFT) to determine a unique representation of cyclic codes of length, N, in terms of that of length, p s , where s = v p (N) and v p are the p-adic valuation. As a result, Hamming distance and dual codes are obtained. In addition, we compute the exact number of distinct cyclic codes over R when n = 2 . [ABSTRACT FROM AUTHOR]

A fundamental problem in coding theory is to find the values of A (n , d) , i.e., the A (n , d) is the size of the maximum binary code set of length n and minimum Hamming distance d. And A (n , d) can also be viewed as the size of maximum independent set of d − 1 t h -power of the n -dimensional hypercube Q n. In order to further understand and study this problem, we study the distribution of the maximum clique and the structure of the point of Q n d for d ≤ 5. [ABSTRACT FROM AUTHOR]

For a subset I subseteq Fnq, let Delta (I) be the set of distances determined by the elements of I. The ErdH os--Falconer distance problem in Fnq asks for a threshold on the cardinality | I| so that Delta (I) contains a positive proportion of the whole distance set. In this paper, we consider the analogous question under Hamming distance, which is the most important metric in coding theory. When q geqslant 4 is a fixed prime power and n goes to infinity, our main result shows that, for arbitrary positive proportion alpha, we can find alpha n distinct Hamming distances in Delta (I) if | I| > q(1 beta)cdot n, where beta is a positive number depending on alpha. Unlike using Fourier analytical method as usual, our main tools include the celebrated dependent random choice and some results from additive number theory and coding theory. Hence our bound is much smaller than the previously known bound which was obtained by Fourier analytic machinery. [ABSTRACT FROM AUTHOR]

Due to the wide applications in consumer electronics, data storage systems and communication systems, cyclic codes have been an interesting research topic in coding theory. In this paper, let p be a prime with p ≥ 7. We determine the Hamming distances of all repeated-root cyclic codes of length 5 p s over F q , where q = p m and both s and m are positive integers. Furthermore, we find all MDS cyclic codes of length 5 p s and take quantum synchronizable codes from repeated-root cyclic codes of length 5 p s . By comparing the minimum distances of 5 p s -length repeated-root cyclic codes to BCH codes of close lengths, we illustrated that quantum synchronizable codes constructed from repeated-root cyclic codes have in general better performance in correcting Pauli errors than those from BCH codes. [ABSTRACT FROM AUTHOR]

Orthogonal arrays have many connections to other combinatorial designs and are applied in coding theory, the statistical design of experiments, cryptography, various types of software testing and quality control. In this paper, we present some general methods to find the Hamming distances for saturated asymmetrical orthogonal arrays (SAOAs) with strength 2. As applications of our methods, the Hamming distances of SAOA parents of size less than or equal to 100 are obtained. We also provide the Hamming distances of the SAOAs constructed from difference schemes or by the expansive replacement method. The feasibility of Hamming distances is discussed. [ABSTRACT FROM AUTHOR]

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an $[{\it{ n,k,d}}]_{ {q}}$ linear block code, we are able to prove the existence of a permutation code in the symmetric group of degree n, having minimum distance at least d and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code. [ABSTRACT FROM AUTHOR]

For a subset I ⊆ Fqn, let Δ (I) be the set of distances determined by the elements of I. The Erdös--Falconer distance problem in Fqn asks for a threshold on the cardinality | I| so that Δ (I) contains a positive proportion of the whole distance set. In this paper, we consider the analogous question under Hamming distance, which is the most important metric in coding theory. When q ≥ 4 is a fixed prime power and n goes to infinity, our main result shows that, for arbitrary positive proportion α, we can find αn distinct Hamming distances in Δ (I) if |I| > q(1-β)·n, where β is a positive number depending on α . Unlike using Fourier analytical method as usual, our main tools include the celebrated dependent random choice and some results from additive number theory and coding theory. Hence our bound is much smaller than the previously known bound which was obtained by Fourier analytic machinery. [ABSTRACT FROM AUTHOR]

Cassuto and Blaum recently studied the symbol-pair channel, a model where every two consecutive symbols are read together. This special channel structure is motivated by the limitations of the reading process in high density data storage systems, where it is no longer possible to read individual symbols. In this new paradigm, the errors are not individual symbol errors, but rather symbol-pair errors, where at least one of the symbols is erroneous. In this work, we study bounds and constructions of codes over the symbol-pair channel. We extend the Johnson bound and the linear programming bound for this channel and show that they improve upon existing bounds. We then propose new code constructions that improve upon existing results for pair-distance six, seven, and ten. [ABSTRACT FROM AUTHOR]

Given a ${q}$ -ary frequency hopping sequence set of length ${n}$ and size ${M}$ with Hamming correlation ${H}$ , one can obtain a ${q}$ -ary (nonlinear) cyclic code of length ${n}$ and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool–martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of synchronizing two sets of data where the size of the symmetric difference between the sets is small and, in addition, the elements in the symmetric difference are related through the Hamming distance metric. Upper and lower bounds are derived on the minimum amount of information exchange. Furthermore, explicit encoding and decoding algorithms are provided for many cases. [ABSTRACT FROM AUTHOR]

We investigate the list decodability of symbol-pair codes in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric. [ABSTRACT FROM AUTHOR]

Mutually uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this paper,we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well-known construction of MU codes and study the asymptotic behavior of its cardinality. This task is accomplished by studying a special class of run-length limited codes that impose the longest run of zeros to be at most some function of the codewords length. We also present an efficient algorithm for this class of constrained codes and show how to use this analysis for MU codes. Next, we extend the results on the run-length limited codes in order to study $(d_{h},d_{m})$ -MU codes that impose a minimum Hamming distance of $d_{h}$ between different codewords and $d_{m}$ between prefixes and suffixes. In particular, we show an efficient construction of these codes with nearly optimal redundancy. We also provide similar results for the edit distance and balanced MU codes. Last, we draw connections to the problems of comma-free and prefix synchronized codes. [ABSTRACT FROM AUTHOR]

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs. [ABSTRACT FROM AUTHOR]

We develop refinements of the Levenshtein bound in q-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. We investigate the first relevant cases and present new bounds. In particular, we derive generalizations and q-ary analogs of the MacEliece bound. Furthermore, we provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds. [ABSTRACT FROM AUTHOR]

Codes that can correct up to $t$ symmetric errors and detect all unidirectional errors, known as $t$ -EC-AUED codes, are studied in this paper. Given positive integers $q$ , $a$ , and $t$ , let $n_{q}(a,t+1)$ denote the length of the shortest $q$ -ary $t$ -EC-AUED code of size $a$. We introduce combinatorial constructions for $q$ -ary $t$ -EC-AUED codes via one-factorizations of complete graphs, and concatenation of MDS codes and codes from resolvable set systems. Consequently, we determine the exact values of $n_{q}(a,t+1)$ for several new infinite families of $q,a$ , and $t$. [ABSTRACT FROM AUTHOR]

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords $\mathsf {M}$ , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the $r$ -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized $r$ -wise Plotkin bound. The $r$ -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < $\delta$ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords $\mathsf {M}$ satisfying $\mathsf {M}\le 4$ and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For $\mathsf {M}$ = 5 or $\mathsf {M}$ = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger $\mathsf {M}$ , observations regarding the optimal design are presented, e.g., that good codes have a large $r$ -wise Hamming distance structure for all $r$. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes. [ABSTRACT FROM AUTHOR]

Let F be any field and A 1 , … , A m be finite subsets of F . We determine the maximum number of common zeroes a linearly independent family of r polynomials of degree at most d of F [ x 1 , … , x m ] can have in A 1 × … × A m . In the case when F is a finite field, our results resolve the problem of determining the generalized Hamming weights of affine Cartesian codes. This is a generalization of the work of Heijnen and Pellikaan where these were determined for the generalized Reed–Muller codes. Finally, we determine the duals of affine Cartesian codes and compute their generalized Hamming weights as well. [ABSTRACT FROM AUTHOR]

This paper considers an uplink multiuser multiple-input-multiple-output (MIMO) system with low-resolution analog-to-digital converters (ADCs), in which K users equipped with a single-antenna communicate with one base station (BS) with N_{\mathrm{ r}} antennas. In this system, we present a novel multiuser MIMO detection framework inspired by coding theory. The key idea of the proposed framework is to create a code {\mathcal C} of length 2N\mathrm{ r} over a spatial domain. This code is constructed by an auto-encoding function that is completely described by a channel transformation followed by a quantization function of the ADCs for a fixed input constellation set. Using the proposed framework, we present a novel weighted minimum distance decoding (wMDD) that achieves the optimal detection performance by appropriately exploiting unequal channel reliabilities. In addition, we show that bit error rate exponentially decreases with the minimum distance of the code {\mathcal C} , which plays a similar role with a condition number in conventional MIMO systems. Furthermore, we develop the communication method that uses the wMDD when the explicit channel state information is not available at the BS. Finally, numerical results are provided to verify the superiority of the proposed method. [ABSTRACT FROM PUBLISHER]

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]

Bus-Invert ( BI ) coding schemes have been used in the circuit design to save power usage by minimizing the number of transitions between successive words. With an increased number of bits for bus width, many other coding schemes like Bus-Shift ( BS ) and Shift-Invert ( SINV ) have been proposed for better power saving. In this paper, we are proposing a new Successive Shift-Invert ( SSINV ) coding scheme where the transmitting data will first be inverted. Then both the original and the inverted word will be shifted circularly for each bit and compared with the data just sent for least hamming distance. Thus, the combination having the least hamming distance with the last sent data will be selected and sent. The proposed method exhibits better power saving compared to other reported methods, but needs one extra control bit than BS ; which add to the computation time. Simulation results show a saving margin of 5–15% in average cases in comparison with BI , BS , and SINV for higher bus width. A VerilogA implementation of SSINV using TSMC 65 nm technology is also presented as a proof of concept. [ABSTRACT FROM AUTHOR]

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in the literature, called, respectively, fix-free code and non-overlapping code. In this paper we present constructive algorithms for such codes and some numerical results about their cardinality. [ABSTRACT FROM PUBLISHER]

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over \mathop \mathrm GR\nolimits (2^a,m) of length 2^s have been characterized: the ring \mathcal R2(a,m,-1)= {\mathrm{ GR}}(2^{a},m)[x]/\langle x^{2^{s}}+1\rangle is a chain ring. Furthermore, these results have been generalized to \lambda -constacyclic codes for any unit \lambda of the form 4z-1 , . In this paper, we study more general cases and investigate all cases, where {\mathcal{ R}}_{p}(a,m,\gamma) = {\mathrm{ GR}}(p^{a},m)[x]/\langle x^{p^{s}}-\gamma \rangle is a chain ring. In particular, the necessary and sufficient conditions for the ring {\mathcal{ R}}_{p}(a,m,\gamma) to be a chain ring are obtained. In addition, by using this structure we investigate all \gamma -constacyclic codes over \mathop {\mathrm {GR}}\nolimits (p^{a},m) when {\mathcal{ R}}_{p}(a,m,\gamma)$ is a chain ring. The necessary and sufficient conditions for the existence of self-orthogonal and self-dual \gamma$ -constacyclic codes are also provided. Among others, for any prime p$ , the structure of is used to establish the Hamming and homogeneous distances of $\gamma$ -constacyclic codes. [ABSTRACT FROM PUBLISHER]

We consider the question of interactive communication, in which two remote parties perform a computation, while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties “out of sync,” so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and tolerates noise rates of up to $1/18- \varepsilon $ . To this end, we develop a novel primitive we name edit-distance tree code. The edit-distance tree code is carefully designed to replace the Hamming distance constraints in Schulman’s tree codes (IEEE Trans. Inf. Theory, 1996), with a stronger edit-distance requirement. [ABSTRACT FROM PUBLISHER]

Motivated by applications involving hot data, the notion of (r, t) -availability was introduced, where a symbol is said to have (r, t) -availability if it can be reconstructed, respectively, from t disjoint repair alternatives of other symbols, each of size at most r . The key to constructing a family of locally repairable codes with (r, t) -availability is the design of a membership matrix for dividing global parities into local ones such that each repair group contains only one parity symbol. Although explicit designs of membership matrices are available, it remains unclear whether membership matrices with significantly better parameters can be constructed, which was a question left open. To tackle the open problem, this paper first provides a connection between the design of membership matrices and the design of a combinatorial object in the well-known combinatorial design theory, called resolvable configurations. This paper then proposes several direct designs of membership matrices based on Euclidean geometry, finite fields, circulant permutation matrices, affine permutation matrices, and Reed–Solomon codes. By leveraging the notion of resolvable configurations and the Kronecker product, this paper further proposes a two-step design of membership matrices. The proposed direct and two-step designs of membership matrices are shown to have significantly better parameters than those recently available. [ABSTRACT FROM AUTHOR]

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and \gcd (n, k)=1 , it is known that the Coulter–Matthews bent function f(x)=Tr\left(ax^\frac 3^k+12\right) is weakly regular bent over \mathbb F3^{n} , where a\in \mathbb F3^{n}^{*} , and Tr(\cdot ):\mathbb F3^{n}\rightarrow \mathbb F3 is the trace function. In this paper, we investigate the dual function of $f(x)$ , aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n=3t+1$ and k=2t+1$ with t\geq 2n=3t+2$ and k=2t+1$ with t\geq 2f(x)$ is regular bent. [ABSTRACT FROM PUBLISHER]

An explicit construction of an infinite family of cyclic codes is presented which, over GF(4) (resp., GF(8)), have approximately 8/9 (resp., 48/49) the redundancy of BCH codes of the same minimum distance and length. As such, the new codes are the best codes currently known in a regime where the minimum distance is fixed and the code length goes to infinity. [ABSTRACT FROM PUBLISHER]

In a group testing scheme, a series of tests are designed to identify a small number $t$ of defective items that are present among a large number N$ of items. Each test takes a group of items as input and produces a binary output indicating whether any defective item is present in the group. In a non-adaptive scheme, the tests have to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a disjunct matrix, an M \times N$ binary matrix where the union of supports of any t$ columns does not contain the support of any other column. In principle, one wants to have such a matrix with a minimum possible number M and 2) each t$ -set of items can be defective with uniform probability. In both the cases, our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before, and it is known that \Theta (t \log N)$ tests are necessary as well as sufficient (via random coding) in both the cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with rows that identify any t$ defectives. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. Indeed, we show how distance, a pairwise property of the columns of the matrix, translates to a (t+1)$ -wise property of the columns. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to for both the first and second cases. While only away by a factor of ({\log N}/{\log t}) from the optimal number of tests, this is the best set of parameters that one can obtain from a deterministic construction, and our main contribution lies in relating the group testing properties to the average and minimum distances of constant-weight codes. [ABSTRACT FROM PUBLISHER]

In this paper, we overview three closely related problems: Nelson-Hadwiger problem on coloring spaces with forbidden monochromatics distances; Borsuk's problem on partitioning sets in spaces into parts of smaller diameter; problem of finding codes with forbidden Hamming distances. [ABSTRACT FROM AUTHOR]

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH , the corresponding minimum pair distance is at least dH+3 . In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH , the minimum pair distance is at least dH +\left \lceil{ {dH/{2}}}\right \rceil . We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, $b \geqslant 3$ , of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting. [ABSTRACT FROM AUTHOR]

Distributed arithmetic coding (DAC) is an effective technique for implementing Slepian–Wolf coding (SWC). It has been shown that a DAC code partitions source space into unequal-size codebooks, so that the overall performance of DAC codes depends on the cardinality and structure of these codebooks. The problem of DAC codebook cardinality has been solved by the so-called codebook cardinality spectrum (CCS). This paper extends the previous work on CCS by studying the problem of DAC codebook structure. We define Hamming distance spectrum (HDS) to describe DAC codebook structure and propose a mathematical method to calculate the HDS of DAC codes. The theoretical analyses are verified by experimental results. [ABSTRACT FROM AUTHOR]

The ranks and kernels of generalized Hadamard matrices are studied. It is proved that any generalized Hadamard matrix H(q,\lambda ) over {\mathbb {F}}_{q} , q>3$ , or $q=3$ and $\gcd (3,\lambda )\not =1$ , generates a self-orthogonal code. This result puts a natural upper bound on the rank of the generalized Hadamard matrices. Lower and upper bounds are given for the dimension of the kernel of the corresponding generalized Hadamard codes. For specific ranks and dimensions of the kernel within these bounds, generalized Hadamard codes are constructed. [ABSTRACT FROM AUTHOR]

In this paper, we propose two new generic attacks on the rank syndrome decoding (RSD) problem. Let C be a random [n,k] rank code over GF(q^m) and let y=x+e be a received word, such that x \in C and rank (e)=r . The first attack, the support attack, is combinatorial and permits to recover an error e of rank weight r operations on GF(q) . This new attack improves the exponent for the best generic attack for the RSD problem in the case n > m , by introducing the ratio m/n in the exponential coefficient of the previously best known attacks. The second attack, the annulator polynomial attack, is an algebraic attack based on the theory of q rather than in GF(q) as it is usually the case. We consider two approaches to solve the problem in this new setting. The linearization technique shows that if n \ge (k+1) (r+1)-1 the RSD problem can be solved in polynomial time. More generally, we prove that if , the RSD problem can be solved with an average complexity of O(r^3k^3q^r\lceil (((r+1)(k+1)-(n+1))/r) \rceil ) operations in the base field GF(q) . We also consider solving with Gröbner bases for which we discuss theoretical complexity, we also consider hybrid solving with Gröbner bases on practical parameters. As an example of application, we use our new attacks on all recent cryptosystems parameters, which repair the GPT cryptosystem, we break all examples of published proposed parameters, and some parameters are broken in less than 1 s in certain cases. [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]

Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall $\tau $ , Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results. [ABSTRACT FROM PUBLISHER]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

Recently, symbol-pair codes are proposed to protect against pair errors in symbol-pair read channels. One main task in symbol-pair coding theory is to design codes with large minimum pair distance. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense they attain maximal minimum pair distance. In this paper, based on constacyclic codes, we construct some new MDS symbol-pair codes with minimum pair-distance five and six. Compared with classical $q$ -ary MDS codes, the constructed MDS symbol-pair codes have length up to q^{2}+q+1 . [ABSTRACT FROM PUBLISHER]

We investigate binary orthogonal arrays by making use of the fact that all possible distance distributions of the arrays under investigation and of related arrays can be computed. We apply certain relations for reducing the number of feasible distance distributions. In some cases this leads to nonexistence results. In particular, we prove that there exist no binary orthogonal arrays with parameters (strength, length, cardinality) = (4, 10, 6 · 2), (4, 11, 6 · 2), (4, 12, 7 · 2), (5, 11, 6 · 2), (5, 12, 6 · 2), and (5, 13, 7 · 2). [ABSTRACT FROM AUTHOR]

We put forward an ample framework for coding based on upper probabilities, or more generally on normalized monotone set-measures, and model accordingly noisy transmission channels and decoding errors. Two inverse problems are considered. In the first case, a decoder is given and one looks for channels of a specified family over which that decoder would work properly. In the second and more ambitious case, it is codes which are given, and one looks for channels over which those codes would ensure the required error correction capabilities. Upper probabilities allow for a solution of the two inverse problems in the case of usual codes based on checking Hamming distances between codewords: one can equivalently check suitable upper probabilities of the decoding errors. This soon extends to "odd" codeword distances for DNA strings as used in DNA word design, where instead, as we prove, not even the first unassuming inverse problem admits of a solution if one insists on channel models based on "usual" probabilities. [ABSTRACT FROM AUTHOR]

In this paper, code decompositions (a.k.a. code nestings) are used to design binary polarization kernels. The proposed kernels are in general nonlinear. They provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, nonlinear kernels of dimensions 14, 15, and 16 are constructed and are shown to have optimal asymptotic error-correction performance. The optimality is proved by showing that the exponents of these kernels achieve a new upper bound that is developed in this paper. [ABSTRACT FROM AUTHOR]

We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over \( \mathbb {F}_{2}\) . We also show how to extend the reduction to work over any fixed finite field. Previously, a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes. [ABSTRACT FROM AUTHOR]

We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of \(O(1/\gamma )\) ) and lower bound (of \(\Omega _{p} (\log (1/\gamma ))\) ) for the list size needed to list decode up to error fraction \(p\) with rate \(\gamma \) away from capacity, i.e., \(1- h(p)-\gamma \) [here \(p\in (0, {1}/{2})\) and \(\gamma > 0\) ]. Our main result is that we prove that in any binary code \(C \subseteq \{ 0, 1 \} ^{n}\) of rate \(1- h(p) - \gamma \) , there must exist a set \( \mathcal {L}\subset C\) of \(\Omega _{p} (1/\sqrt {\gamma })\) codewords such that the average distance of the points in \( \mathcal {L}\) from their centroid is at most \(pn\) . In other words, there must exist \(\Omega _{p}(1/\sqrt {\gamma })\) codewords with low average radius. The standard notion of list decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned \(\Omega _{p}(\log (1/\gamma ))\) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one cannot improve the \(\Omega _{p}(\log (1/\gamma ))\) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constant-weight codes [this is a typical approach for negative results in coding theory, including the \(\Omega _{p} (\log (1/\gamma ))\) list-size lower bound]. On a positive note, our \(\Omega _{p}(1/\sqrt {\gamma })\) lower bound for average-radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap \(\gamma \) of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from \(p\) ) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of \(\Omega _{p} (1/\gamma )\) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are \(\Omega _{p} (1/\gamma )\) for errors and \(\exp (\Omega _{p}(1/\gamma ))\) for erasures. [ABSTRACT FROM AUTHOR]

A method for constructing optimal almost equisymbol codes based on difference matrices is proposed. Some of these codes generate previously unknown optimal equidistant codes satisfying the Plotkin bound. As a consequence, they generate new resolvable balanced incomplete block designs. [ABSTRACT FROM AUTHOR]

The distance profiles of linear block codes can be employed to design variational coding scheme for encoding message with variational length and getting lower decoding error probability by large minimum Hamming distance, where one example is in the design of transport format combination indicators (TFCIs) in CDMA. Considering convenience for encoding, we focus on the distance profiles with respect to cyclic subcode chains (DPCs) of cyclic codes over $GF(q)$ with length n$ such that \gcd(n, q)=1$. In this paper, the optimum DPCs and the corresponding optimum cyclic subcode chains are investigated on the punctured second-order Reed–Muller code for increasing message length, where two standards on the optimums are studied according to the rhythm of increase. Ignoring the dimension profile, the device will coincide with that of TFCI. [ABSTRACT FROM AUTHOR]

In this paper we translate in terms of coding theory constraints that are used in designing DNA codes for use in DNA computing. We focus in particular on additive self-dual codes over GF(4), and we propose a new method for constructing DNA codes satisfying the Hamming distance constraint, the reverse-complement constraint and the GC-content constraint. [ABSTRACT FROM AUTHOR]

We present some upper bounds on the size of nonlinear codes and their restriction to systematic codes and linear codes. These bounds are independent of other known theoretical bounds, e.g., the Griesmer bound, the Johnson bound, the Plotkin bound, and of linear programming bounds. One of the new bound is actually an improvement of a bound by Zinoviev, Litsyn, and Laihonen. Our experiments show that in the linear case our bounds provide the best value in a wide range, compared with all other closed-formula upper bounds. In the nonlinear case, we also compare our bound with the linear programming bound and with some improvements on it, show that there are cases where we beat these bounds. In particular, we obtain a new bound in Brouwer's table for A3(16,3). [ABSTRACT FROM AUTHOR]

We revisit the problem of reliable interactive communication over a noisy channel and obtain the first fully (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memoryless noisy channel with constant capacity and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman (1993), our simulation uses a tree-code, yet as opposed to the nonefficient construction of absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an efficient emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore, we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree. [ABSTRACT FROM AUTHOR]

In this paper, we consider the task of target localization using quantized data in wireless sensor networks. We propose a computationally efficient localization scheme by modeling it as an iterative classification problem. We design coding theory based iterative approaches for target localization where at every iteration, the fusion center (FC) solves an M-ary hypothesis testing problem and decides the region of interest for the next iteration. The coding theory based iterative approach works well even in the presence of Byzantine (malicious) sensors in the network. We further consider the effect of non-ideal channels. We suggest the use of soft-decision decoding to compensate for the loss due to the presence of fading channels between the local sensors and FC. We evaluate the performance of the proposed schemes in terms of the Byzantine fault tolerance capability and probability of detection of the target region. We also present performance bounds, which help us in designing the system. We provide asymptotic analysis of the proposed schemes and show that the schemes achieve perfect region detection irrespective of the noise variance when the number of sensors tends to infinity. Our numerical results show that the proposed schemes provide a similar performance in terms of mean square error as compared with the traditional maximum likelihood estimation but are computationally much more efficient and are resilient to errors due to Byzantines and non-ideal channels. [ABSTRACT FROM PUBLISHER]