Search

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]

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]

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]

A coordinate of a binary code of size M is said to be balanced if the number of zero and ones in the coordinate is either $$\lfloor M/2\rfloor $$ or $$\lceil M/2 \rceil $$ (that is, exactly $$M/2$$ for even M). Since good codes (of various types) tend to be balanced in all coordinates, various conjectures have been made regarding the existence of such codes. It is here shown that there are parameters for which there are no optimal binary error-correcting codes with a balanced coordinate. This is proved by the code attaining $$A(17,8) = 36$$ , which is shown to be unique here; $$A(n,d)$$ denotes the maximum size of a binary code of length n and minimum distance d. It is further shown that $$A(18,8) \le 68$$ . [ABSTRACT FROM AUTHOR]

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]

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]