Search

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]

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]

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]

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 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 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]

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]

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]

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]

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]

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]

We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance. [ABSTRACT FROM PUBLISHER]

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]

We study abelian codes in principal ideal group algebras (PIGAs). We first give an algebraic characterization of abelian codes in any group algebra and provide some general results. For abelian codes in a PIGA, which can be viewed as cyclic codes over a semisimple group algebra, it is shown that every abelian code in a PIGA admits generator and check elements. These are analogous to the generator and parity-check polynomials of cyclic codes. A characterization and an enumeration of Euclidean self-dual and Euclidean self-orthogonal abelian codes in a PIGA are given, which generalize recent analogous results for self-dual cyclic codes. In addition, the structures of reversible and complementary dual abelian codes in a PIGA are established, again extending results on reversible and complementary dual cyclic codes. Finally, asymptotic properties of abelian codes in a PIGA are studied. An upper bound for the minimum distance of abelian codes in a non-semisimple PIGA is given in terms of the minimum distance of abelian codes in semisimple group algebras. Abelian codes in a non-semisimple PIGA are then shown to be asymptotically bad, similar to the case of repeated-root cyclic codes. [ABSTRACT FROM PUBLISHER]

Constant-weight codes play an important role in coding theory. The problem of determining the sizes for optimal quaternary constant-weight codes with length n, weight 4, and minimum Hamming distance 5 ((n,5,4)4 codes) has been investigated in several papers. Although some constructions and several infinite families for such codes with length n\equiv 0,1\pmod4 have been given, the problem is still far from complete. In this paper, we determine the size of an optimal (n,5,4)4 code for each integer n\geq 4 leaving 55 lengths unsolved. Especially, for length n\equiv 0,1\pmod 4, the existence problem of the equivalent combinatorial object, namely the generalized Steiner system, is solved leaving only seven values undetermined. [ABSTRACT FROM AUTHOR]

An n-word y=(y1,\dots, yn) over a finite alphabet of cardinality q is called a descendant of a set of t words x^1,\dots, x^t if every coordinate yi,i=1,\dots, n, is contained in the set \x^1i,\dots, x^{ti\}. A code \cal C=\x^1,\dots, x^M\ is said to have the t-IPP property if for any n-word y that is a descendant of at most t parents belonging to the code, it is possible to identify at least one of them. From earlier works, it is known that t-IPP codes of positive rate exist if and only if t\leq q-1. We introduce a robust version of IPP codes which allows error-free identification of parents in the presence of a certain number of mutations, i.e., coordinates in y that can break away from the descent rule, taking arbitrary values from the alphabet or becoming completely unreadable. We show existence of robust t-IPP codes for all t\leq q-1 and some positive proportion of such coordinates. We uncover a relation between the hash distance of codes and the IPP property and use it to find the exact proportion of mutant coordinates that permits identification of pirates with zero probability of error in the case of size-2 coalitions. [ABSTRACT FROM AUTHOR]

Fix-free codes are prefix condition codes which can also be decoded in the reverse direction. They have attracted attention from several communities and are used in video standards. Two variations (with additional constraints) have also been considered for joint source-channel coding: 1) “symmetric” codes, which require the codewords to be palindromes; 2) codes with distance constraints on pairs of codewords. Approaches to determine the existence of a fix-free code with a given set of codeword lengths, for each of the three variations, are proposed. These appear to involve the first use of Boolean satisfiability (SAT) for the existence and design of source codes. Branch-and-bound algorithms to find the collection of optimal codes for asymmetric and symmetric fix-free codes are described. The first bound for the performance of optimal symmetric binary fix-free codes is provided. An earlier conjecture on optimal symmetric binary fix-free codes is proven and related results for asymmetric fix-free codes are presented. A variation of the 3/4 conjecture for fix-free codes is introduced. A key idea in the first conjecture and the new one is a definition of how one sequence of nondecreasing natural numbers dominates another. [ABSTRACT FROM PUBLISHER]

It has been widely observed that there exists a fundamental tradeoff between the minimum (Hamming) distance properties and the iterative decoding convergence behavior of turbo-like codes. While capacity-achieving code ensembles typically are asymptotically bad in the sense that their minimum distance does not grow linearly with block length, and they therefore exhibit an error floor at moderate-to-high signal-to-noise ratios, asymptotically good codes usually converge further away from channel capacity. In this paper, we introduce the concept of tuned turbo codes, a family of asymptotically good hybrid concatenated code ensembles, where asymptotic minimum distance growth rates, convergence thresholds, and code rates can be tradedoff using two tuning parameters: \lambda and \mu . By decreasing \lambda , the asymptotic minimum distance growth rate is reduced in exchange for improved iterative decoding convergence behavior, while increasing \lambda raises the asymptotic minimum distance growth rate at the expense of worse convergence behavior, and thus, the code performance can be tuned to fit the desired application. By decreasing \mu , a similar tuning behavior can be achieved for higher rate code ensembles. [ABSTRACT FROM PUBLISHER]

Constant-weight codes (CWCs) play an important role in coding theory. The problem of determining the sizes for optimal ternary CWCs with length n, weight 4, and minimum Hamming distance 5 ((n,5,4)3 code) has been settled for all positive integers n\leq 10 or n > 10 and n\equiv 1\pmod 3 with n\in \13,52,58\ undetermined. In this paper, we investigate the problem of constructing optimal (n,5,4)3 codes for all lengths n with the tool of group divisible codes. We determine the size of an optimal (n,5,4)3 code for each integer n\geq 4 leaving the lengths n\in \12,13,21,27,33,39,45,52\ unsolved. [ABSTRACT FROM PUBLISHER]

Knuth's celebrated balancing method consists of inverting the first z bits in a binary information sequence, such that the resulting sequence has as many ones as zeroes, and communicating the index z to the receiver through a short balanced prefix. In the proposed method, Knuth's scheme is extended with error-correcting capabilities, where it is allowed to give unequal protection levels to the prefix and the payload. The proposed scheme is very general in the sense that any error-correcting block code may be used for the protection of the payload. Analyses with respect to redundancy and block and bit error probabilities are performed, showing good results while maintaining the simplicity features of the original scheme. It is shown that the Hamming distance of the code is of minor importance with respect to the error probability. [ABSTRACT FROM PUBLISHER]

A new coding framework is established for channels whose outputs are overlapping pairs of symbols. Such channels are motivated by storage applications in which the spatial resolution of the reader may be insufficient to isolate adjacent symbols. Reading symbols as pairs changes the coding-theoretic error model from the standard bounded number of symbol errors to a bounded number of pair errors. Starting from the most basic coding-theoretic questions, the paper studies codes that protect against pair-errors. It provides answers on pair-error correctability conditions, code construction and decoding, and lower and upper bounds on code sizes. Asymptotic analysis of pair-error correction shows that there exist pair-error codes with rates that are strictly higher than the best known codes in the Hamming metric. [ABSTRACT FROM AUTHOR]

A well-known conjecture of Golomb and Welch is that the only nontrivial perfect codes in the Lee and Manhattan metrics have length two or minimum distance three. This problem and related topics were subject for extensive research in the last 40 years. In this paper, two product constructions for perfect Lee codes and diameter perfect Lee codes are presented. These constructions yield a large number of nonlinear perfect codes and nonlinear diameter perfect codes in the Lee and Manhattan metrics. A short survey and other related problems on perfect codes in the Lee and Manhattan metrics are also discussed. [ABSTRACT FROM AUTHOR]

Various kinds of distances of all negacyclic codes of length 2s over are completely determined. Using our structure theorems of negacyclic codes of length 2s over Z2a, we first calculate the Hamming distances of all such negacyclic codes, which particularly lead to the Hamming weight distributions and Hamming weight enumerators of several codes. These Hamming distances are then used to obtain their homogeneous, Lee, and Euclidean distances. Our techniques are extendable to the more general class of constacyclic codes, namely, the λ-constacyclic codes of length 2s over Z2a, where λ is any unit of Z2a with the form 4k - 1. We establish the Hamming, homogeneous, Lee, and Euclidean distances of all such constacyclic codes. [ABSTRACT FROM AUTHOR]

A new lower bound for the distance of cyclic codes is proposed. This bound depends on the defining set of the code, like several other bounds. The proposed bound improves upon the Bose-Chaudhuri-Hocquehghen (BCH) bound and, for some codes, improves upon the Hartmann-Tzeng bound and the Roos bound as well. [ABSTRACT FROM AUTHOR]

Distance-preserving maps (DPMs) from binary vectors to permutations are useful for the construction of permutation arrays. A new construction of DPMs is presented. We study the distance increasing property of the new DPMs that this construction yields. Then we show that new DPMs contain a class of nicely structured DPMs of even length with good distance increasing property. [ABSTRACT FROM AUTHOR]

The rate-distortion function for source coding with side information at the decoder (the "Wyner-Ziv problem") is given in terms of an auxiliary random variable, which forms a Markov chain with the source and the side information. This Markov chain structure, typical to the solution of multiterminal source coding problems, corresponds to a loss in coding rate with respect to the conditional rate-distortion function, i.e., to the case where the encoder is fully informed. We show that for difference (or balanced) distortion measures, this loss is bounded by a universal constant, which is the minimax capacity of a suitable additive-noise channel. Furthermore, in the worst case, this loss is equal to the maximin redundancy over the rate-distortion function of the additive noise "test" channel. For example, the loss in the Wyner-Ziv problem is less than 0.5 bit/sample in the squared-error distortion case, and it is less than 0.22 bit for a binary source with Hamming distance. These results have implications also in universal quantization with side information, and in more general multiterminal source coding problems. [ABSTRACT FROM PUBLISHER]