Let$m \in \mathbb{N}$and$\mathbb{Z}_{m} \stackrel{\text { def }}{=}\{0,1, \ldots, m-1\}$be the$m$ary alphabet.$\mathbf{A} \mathbb{Z}_{m}$linear code of length$n \in \mathbb{N}$is a submodule of the module$\left(\mathbb{Z}_{m}^{n},+\bmod m, \mathbb{Z}_{m}, \cdot \bmod m\right)$. This paper presents a significant lower bound for the minimum Lee distance$d_{\text {Lee }}(\mathcal{C})$, of any$\mathbb{Z}_{m}$linear code$\mathcal{C}$. This bound facilitates, for a given minimum Lee distance, the efficient design of high information rate codes, which are computationally simple to implement using algebraic operations over fields of small cardinality. Two notable examples of such codes are provided, demonstrating the application of this bound. These families of codes generalize the$\mathbb{Z}_{4}$linear Preparata and Goethals codes over the alphabet$\mathbb{Z}_{m}, m=2^{l} \in \mathbb{N}$with$l \geq 2$. Specifically, for any$m=2^{l}>2$and$h \in \mathbb{N}, h$odd, the generalized$\mathbb{Z}_{m}$linear Preparata codes have length$n+1=2^{h}$, minimum Lee distance 6 and cardinality$|\mathcal{C}|=m^{n-h-1}\lceil m / 4\rceil^{h}\lceil m / 8\rceil$. For the same parameters$m, l, n, h \in \mathbb{N}$, the generalized$\mathbb{Z}_{m}$linear Goethals codes have length$n+1=2^{h}$, minimum Lee distance 8 and cardinality$|\mathcal{C}|=m^{n-2 h-1}\lceil m / 2\rceil^{h}\lceil m / 4\rceil^{h}\lceil m / 8\rceil$. Notably, both families of codes are less redundant and less complex than$m$-ary codes with the same minimum Lee distances obtained by applying the Gray mapping to$l$-bit subblocks of codewords from binary linear codes.

In a systematic code (systematic in the strict sense) a check symbol is appended to the data word. Here, the theory and design of systematic binary block codes capable of correcting$t$insertion and/or deletion of the symbol 0 in each and every 0-run is studied. This problem is related to the zero error capacity achieving systematic codes in limited magnitude error channels. Optimal and sub-optimal systematic code designs and the encoding/decoding algorithms are given.

Let ${\mathbb{Z}_m}\mathop = \limits^{{\text{ def }}}$ $\left\{ {0,1, \ldots ,\left( {m - 1} \right)} \right\}$ be the m-ary alphabet, $m \in \mathbb{N}$. This paper gives some new theory and designs of ${\mathbb{Z}_m}$ linear error control codes based on the elementary symmetric functions of m-ary words. Here, a ${\mathbb{Z}_m}$ linear code is a submodule of the module $\left( {\mathbb{Z}_m^n, + {\text{mod}}m,{\mathbb{Z}_m}, \cdot {\text{mod}}m} \right),n \in \mathbb{N}$, and the errors are measured in the ${L_1}$ or Lee metric. Potentially, the alphabet size, m, can be any natural, however, the described code designs and decoding methods are solely based on fields and field operations. In particular, starting from a very general class of Goppa-like ${\mathbb{Z}_m}$ linear codes, given a field, $K$, of characteristic $p = {\text{char}}\left( K \right) \in \mathbb{N}$, we consider a generalization of the ${\mathbf{BCH}}$ codes to the m-ary alphabet for $m = {p^l},l \in \mathbb{N}$. For these BCHlike codes we are able to prove a BCH-like bound with respect to both the ${L_1}$ and Lee distances. This enabled us to design a wide family of remarkable efficient codes. For example, an efficient design is given for ${\mathbb{Z}_m}$ linear codes with $m = {2^l},l \in \mathbb{N}$, length $n = m$, minimum Lee distance ${d_{Lee}} = m = n$ and the number of information m-ary digits $k = m/2 = n/2$.

This paper gives some theory and efficient design of binary block codes capable of controlling the deletions of the symbol “0” (referred to as 0-deletions) and/or the insertions of the symbol “0” (referred to as 0-insertions). This problem of controlling 0-deletions and/or 0-insertions (referred to as 0-errors) is shown to be equivalent to the efficient design of$L_{1}$metric asymmetric error control codes over the natural alphabet,${\mathbf{I}}\!{\mathbf{I}}\!\!{\mathbf{N}}$. In this way, it is shown that the$t 0$-insertion correcting codes are actually capable of controlling much more; namely, they can correct$t 0$-errors, detect$(t+1)\,\,0$-errors and, simultaneously, detect all occurrences of only 0-deletions or only 0-insertions in every received word (briefly, they are$t$-Symmetric 0-Error Correcting/$(t+1)$-Symmetric 0-Error Detecting/All Unidirectional 0-Error Detecting ($t$-Sy0EC/$(t+1)$-Sy0ED/AU0ED) codes). From the relations with the$L_{1}$distance error control codes, new improved bounds are given for the optimal$t 0$-error correcting codes. Optimal non-systematic code designs are given. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).

In this paper the theory and design of codes capable of correcting t insertion/deletion of the symbol 0 in each and every bucket of zeros (i. e., zeros in between two consecutive ones) are studied. It is shown that this problem is related to the zero error capacity achieving codes in limited magnitude error channel. Close to optimal non-systematic code designs and the encoding/decoding algorithms are described.

This paper gives some theory and efficient design of binary block codes capable of controlling the deletions of the symbol "0" (referred to as 0-deletions) and/or the insertions of the symbol "0" (referred to as 0-insertions). This problem of con-trolling 0-deletions and/or 0-insertions (referred to as 0-errors) is shown to be equivalent to the efficient design of L1metric asymmetric error control codes over the natural alphabet,IN. Optimal systematic code designs are given. In particular, for all $t,k \in {\mathbb{I}}\mathbb{N}$, a recursive method is presented to encode k information bits into efficient systematic t Symmetric 0-Error Correcting, (t + 1) Symmetric 0-Error Detecting and All Unidirectional 0-Error Detecting (t-Sy0EC/(t+1)-Sy0ED/AU0ED) codes of length\begin{equation*}n \leq k + t\;{\text{lo}}{{\text{g}}_2}\;k + o(t\;{\text{log}}\;n)\end{equation*}as $n \in {\mathbb{I}}\mathbb{N}$ increases. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).

Salp Swarm Algorithm (SSA) is a novel swarm technique using to optimize design problems. SSA is inspired by the swarming behavior of salp observed in the deep area of sea. In spite of its application versatility, SSA suffers from mediocre convergence rate and limited exploratory capabilities. In this paper, a Fitness Dependent Salp Swarm Algorithm (FDSSA) is proposed. The novelties of the proposed approach are the definition of a fitness coefficient able to enhance the exploration, the introduction of a novel mathematical model to describe the trajectory of salps and a mutation mechanism to increase the convergence speed. The designed algorithm is tested on unimodal and multimodal benchmark functions and then compared with well-known heuristic algorithms. The results show the superiority of FDSSA with respect to the comparison algorithms in terms of optimization and convergence performances according to their computational complexity.

This paper gives some theory and efficient design of binary block codes capable of correcting the deletions of the symbol "0" (referred to as 0-deletions) and/or the insertions of the symbol "0" (referred to as 0-insertions). This problem of correcting 0-deletions and/or 0-insertions (referred to as 0-errors) is shown to be equivalent to the efficient design of some L1metric asymmetric error control codes over the natural alphabet, ℕ. In particular, it is shown that t 0-insertion correcting codes are actually capable of correcting t 0-errors, detecting (t+1) 0-errors and, simultaneously, detecting all occurrences of only 0-deletions or only 0-insertions in every received word (briefly, they are t-Sy0EC/(t + 1)-Sy0ED/AU0ED codes). From the relations with the L1distance error control codes, new improved bounds are given for the optimal t 0-error correcting codes. In addition, some optimal non-systematic code designs are also given. Decoding can be efficiently performed by algebraic means with the Extended Euclidean Algorithm.

Let ℤm=def{0, 1, ... , (m - 1)} be the m-ary alphabet, m ∈ ℕ. This paper gives some new theory and efficient designs of ℤmlinear error control codes based on the elementary symmetric functions of m-ary words. Here, a ℤmlinear code is a sub-module of the module (ℤmn, + mod m, ℤm, · mod m), n ∈ ℕ, and the errors are measured in the L1or Lee metric. In particular, given a field, K, of characteristic p = char(K) = 2, 3, 5, ... prime, and given d, m = vpl, v, l, n ∈ ℕ with d ≤ m/v = pland n ≤ |K|-1, we introduce a new class of (d-1) asymmetric error correcting ℤmlinear codes, Cd, of length n whose redundancy is only ρ(Cd) = n - logm|Cd| ≤ (d - 1) logm|K|. For these codes we give very efficient field based algebraic decoding algorithms to control d - 1 errors actually in the Lee distance. Also for the extended codes, we give new efficient field based decoding algorithms.

Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, C0, of a noisy channel. This is defined as the least upper bound of rates, at which, it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length n=1,2,..., in contrast to the long lengths required for the known regular capacity achieving codes, such as turbo codes, LDPC codes, and polar codes. Both wrap around and non-wrap around limited magnitude error models are considered in this paper. For non-wrap around error model, the exact value of zero error capacities is derived, and optimal non-systematic and systematic codes are designed. The non-systematic codes achieve the zero error capacity with any finite length. The optimal systematic codes achieve the systematic zero error capacity of the channel, which is defined as the zero error capacity with the additional requirements that the communication must be carried out with a systematic code. It is also shown that the rates of the proposed systematic codes are equal to or approximately equal to the zero error capacity of the channel. For the wrap around model bounds are derived for the zero error capacity and in many cases the bounds give the exact value. In addition, optimal wrap around non-systematic and systematic codes are developed which either achieve or are close to achieving the zero error capacity with finite length.

Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, Co, of a noisy channel. This is defined as the least upper bound of rates at which it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length n = 1, 2,..., in contrast to the long lengths required for the known regular capacity achieving codes such as turbo codes, LDPC codes and polar codes. Both non-systematic and systematic codes are described.

A new efficient design of second-order spectralnull (2-OSN) codes is presented. The new codes are obtained by applying the technique used to design parallel decoding balanced (i.e., 1-OSN) codes to the random walk method introduced by some of the authors for designing 2-OSN codes. This gives new non-recursive efficient code designs, which are less redundant than the code designs found in the literature. In particular, if k ∈ IIN is the length of a 1-OSN code then the new 2-OSN coding scheme has length n = k + r ∈ IIN with an extra redundancy of r ≃ 2 log2k + (1/2) log2log2k - 0.174 check bits, with k and r even and n multiple of 4. The whole coding process requires O(k log k) bit operations and O(k) bit memory elements.

An m-ary block code, m = 2, 3, 4,..., of length n ϵ IN is called balanced if, and only if, every codeword is balanced; that is, the real sum of the codeword components, or weight, is equal to ⌊(m - 1)n/2⌋. This paper presents efficient encoding schemes to m-ary balanced codes with parallel (hence, fast) decoding. In fact, the decoding time complexity is O(1) digit operations. These schemes are a generalization to the m-ary alphabet of Knuth's complementation method with parallel decoding. Let (nw)mindicate the number of m-ary words w of length n and weight w ϵ(0,1, ... , (m - 1)n}. For any m ϵ IN, m ≥ 2, a simple implementation of the method is given which uses r ϵ IN check digits to balance k ≤ {(⌊(m-1)r/2⌋)m- (m mod 2 + [(m - 1)k] mod 2}}/(m - 1) information digits with an encoding time complexity of O(mk logmk) digit operations. A refined implementation of the parallel decoding method is also given with r check digits and k ≤ (mr-1)/(m -1) information digits, where the encoding time complexity is O(k√logmk). Thus, the proposed codes are less redundant than the m-ary balanced codes with parallel decoding found in the literature and yet maintain the same complexity.

A new efficient coding scheme is given for second-order spectral-null (2-OSN) codes. The new method applies the Knuth's optimal parallel decoding scheme for balanced (i.e., 1-OSN) codes to the random walk method introduced by Tallini and Bose to design 2-OSN codes. If k ∈ IN is the length of a 1-OSN code then the new 2-OSN coding scheme has length n = k+r ∈ IN with an extra redundancy of r ≳ 2 log2k + (1/2) log2log2k - 0.674 check bits. The whole coding process requires O(n log n) bit operations and 0(n) bit memory elements.

The general theory on partially asymmetric (t, t+)-EC/(d-, d+)-ED m-ary codes for the L1distance is developed. In this metric, such codes are capable of correcting t-or less negative errors, detecting d or less negative errors, correcting t+or less positive errors, and simultaneously detecting d+or less positive errors. Based on the elementary symmetric function, a wide class of these codes with efficient decoding algorithms are given. Let S(m, n, w, D) be the set of all the m-ary words of length n with real sum of their components being equal to w mod D. Any subset of S(m, n, w, D) is called m-ary constrained weight (CW) code of length n and is known to be a (D - 1)-UED code. Given a field, K, of prime characteristic p, some m-ary CW codes of length n ≤ |K| - 1 are defined. Such codes are (t-, t+)-EC/(d-, d+)-ED and have a redundancy of ρ(c) = n - logm|C| ≤ ρ {S(m, n, w, d + 1)) + t logm|K|, with t = min{t_ + d+, d_ + t+}, d = max{t_ + d+, d_ + t+} and w ∈ IN. In particular, for t ≤ p-1, a class of essentially linear and systematic (hence, easy to encode) m-ary (t_, t+)-EC/(d_, d+)-ED CW σ-codes with length nm|K| + ⌈d/(m-1)⌉ check digits are given. Also, some new hybrid partially asymmetric/unidirectional/symmetric error control codes are given and shown to be equivalent to the partially asymmetric (t_, t+)-EC/(d_, d+)-ED m-ary codes.

Based on the elementary symmetric functions, this paper gives a new wide class of Goppa like codes capable of correcting/detecting errors measured under the (symmetric) L1distance defined over the m-ary words, 2 ≤ m ≤ +∞. All these codes can be efficiently decoded by algebraic means with the Extended Euclidean Algorithm (EEA). In particular it is shown that if K is any field with characteristic char(K) ≠ 2, m ϵ IN U {+∞} and n, t ϵ IN then there exist m-ary codes C of length n ≤ (|K|- 1)/2 and cardinality |C| ≥ mn/|K|twhich are capable of, say, correcting t errors (i. e., the minimum L1distance of C is dL1(C) ≥ 2t + 1) with t steps of EEA. Also, if K is a finite field and 2t + 1 ≤ char(K) ≠ 2 then some of these codes are (essentially) linear and, hence, easy to encode.

This paper gives some new theory and design of codes capable of correcting/detecting errors measured under the Lee distance defined over m-ary words, m ∈ IN. Based on the elementary symmetric functions (instead of the power sums), a key equation is derived which can be used to design new symmetric (or, asymmetric) error control algorithms for some new and already known error control codes for the Lee metric. In particular, it is shown that if K is any field with characteristic char(K) = p, p odd, and u, h, n, m = uph, t ∈ IN are such that n ≤ (|K|-1)/2 and t ≤ (ph- 1)/2 then there exist m-ary codes C of length n and cardinality |C| ≥ mn/|K|twhich are capable of, say, correcting t symmetric errors (i. e., the minimum Lee distance of C is dLee(C) ≥ 2t + 1) with t steps of the Extended Euclidean Algorithm. Furthermore, if t ≤ (p - 1)/2 then some of these codes are (essentially) linear and, hence, easy to encode.

In an unordered code, no code word is contained in any other code word. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes withkinformation bits, Berger codes are optimal unordered codes withr=[log2(k+1)] ≅ log2kcheck bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic (instantaneous) unordered codes with variable length check symbols. The average redundancy of the new codes presented here isr≅ (1/2)log2k+c, wherec∈ (1.0470,1.1332) ⊆IRandk∈INis the number of information bits. Whenkis large, it is shown that such redundancy is at most 0.6069 bits off the redundancy of an optimal systematic unordered code design with fixed length information symbols and variable length check symbols; and, at most 2.8075 bits off the redundancy of an optimal variable length unordered code design. The generalization is also given for the nonbinary case and it is shown that similar results hold true.

This paper shows that the first order Reed-Muller codes punctured in one component fall into a class of t-asymmetric error correcting (t-AEC) codes with very fast decoding. Hence, these linear Reed-Muller codes give a nice example of t-AEC codes which are very simple to both encode and decode. Decoding of these codes is much simpler than the usual t-SEC BCH code decoding because the syndromes, which are based on elementary symmetric functions of the received word, directly give the number of errors and the error locator polynomial. The result is based on some interesting properties which are proven in general for geometry codes.

This paper gives some theory and design of efficient codes capable of controlling (i. e., correcting/detecting/correcting erasure) errors measured under the L1distance defined over m-ary words, 2 ≤ m ≤ +∞. We give the combinatorial characterizations of such codes, some general code designs and the efficient decoding algorithms. Then, we give a class of linear and systematic m-ary codes, m = sp with s∈IN and p a prime, which are capable of controlling d ≤ p-1 errors. If n and k∈IN are respectively the length and dimension of a BCH code over GF(p) with minimum Hamming distance d + 1 then the new codes have length n and k' = k + r logms information digits.

An m-ary block code, m = 2, 3, 4, ..., of length n ∈ IN is called balanced if, and only if, every codeword is balanced; that is, the real sum of the codeword components, or weight, is equal to ⌊(m - 1)n/2⌋. This paper presents a tight generalization of Knuth's complementation method with parallel (hence, fast) decoding scheme. Let (wn)mindicate the number of m-ary words of length n and weight w ∈ {0, 1, ..., (m-1)n}. A simple implementation of the scheme uses (m - 1)k + m mod 2 balancing functions to make a k ∈ IN digit information word to be balanced. So, r ∈ IN check digits can be used to balance k ≤ [(⌊(m-1)rr/2⌋)m-m mod 2]/(m - 1) information digits. A refined implementation of the parallel decoding scheme uses r check digits to balance k ≤ (mr-1)/(m-1) information digits.

This paper gives the theory and design of efficient codes capable of correcting errors caused by the insertion and deletion of a repeated symbol in the information sequence. Two efficient methods are described. For any fixed t+, t-∈ IN, one method gives a fixed length scheme to encode k information bits into a systematic code of length n = k + r, with r = (t++ t-) log2k + O(log log k), capable of correcting the insertion of t+repeated symbols and, simultaneously, correcting the deletion of t-repeated symbols in every codeword. The second method is a systematic variable length scheme which on average doubles the number of information bits k compared to the first method. The time complexity of the entire coding process for both schemes is T = O (k + (1+min{t-, t+})t) multiplication operations over a finite field containing k elements. The space complexity is S = O(k+t) field memory elements. The generalization to the m-ary case, m ≥ 2, is also given.

In an unordered code no codeword is contained in any other codeword. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes with k information bits, Berger codes are optimal unordered codes with r = ¿log2(k+1)¿ check bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic unordered codes with variable length check symbols. The average redundancy of these new codes is r ¿ (1/2) log2(¿ek/2) = (1/2) log2k + 1.047, where k¿IN is the number of information bits. It is also shown that such codes are optimal in the class of systematic unordered codes with fixed length information symbols and variable length check symbols. The generalization to the non-binary case is also given.

In this note, we give a correction to the Proof of Theorem 2 in L. G. Tallini, S. Al-Bassam, and B. Bose, ldquoFeedback Codes Achieving the Capacity of the Z-Channel,rdquoIEEETransactionsonInformationTheory, vol. 54, pp. 1357-1362, March 2008.

A general key equation based on elementary symmetric functions is developed for decoding some binary error control codes. Here, the syndrome is obtained by computing the elementary symmetric functions (instead of the power-sums) of the received word. A new class of codes is introduced in this paper which can correct up to t00 rarr 1 errors and, simultaneously, up to t11 rarr 0 errors. The new key equation can be used to decode this new class of codes and some known codes such as some t-asymmetric error correcting (t-AEC) codes, the t-symmetric error correcting (t-SEC) BCH codes and Goppa codes. Some generalizations to the non binary case are also given.

Given the 1 to 0 bit error probability, pisin[0, 1], the capacity of the Z-channel is given by Cz=log2(1+pp/(1-p)-p1/(1-p)). Some new error free feedback coding schemes that achieve the Z-channel capacity are presented.

Forward error control (FEC) and automatic-repeat request (ARQ) is two main techniques used for reliable data transmission in computer and communication systems. In this paper, some simple, low cost error control techniques for ARQ protocols used with binary unidirectional channels are described. The proposed schemes can correct up to [t/2] unidirectional errors using t-unidirectional error detecting codes and code combining with a much smaller number of retransmissions. First, we show how to do code combining for unidirectional errors. To use code combining with unidirectional codes, we need to identify the type of error (0rarr1 or 1rarr0) from the received word. We show how this can be done for various unidirectional codes

Some new classes of systematic t-unidirectional error-detecting codes over Zmare designed. It is shown that the constructed codes can detect two errors using two check digits. Furthermore, the constructed codes can detect up to mr-2+ r-2 errors using r ges 3 check bits. A bound on the maximum number of detectable errors using r check digits is also given.

Forward error control (FEC) and automatic-repeat request (ARQ) are two main techniques used for reliable data transmission in computer and communication systems. In this paper, some simple, low cost error control techniques for ARQ protocols used with binary unidirectional channels, are described. The proposed schemes can correct up to [t/2] unidirectional errors using t-unidirectional error detecting codes and code combining with much less number of retransmissions. First we show how to do code combining for unidirectional errors. To use code combining with unidirectional codes, we need to identify the type of error (0 rarr 1 or 1 rarr 0) from the received word. We show how this can be done for various unidirectional codes

In the ARQ (Automatic Retransmission Request) protocol, the sender keeps retransmitting a codeword until it receives a positive acknowledgment from the receiver sent through the feedback channel. This paper proposes Plain and Diversity Combining ARQ Hybrid protocol communication schemes suitable for the m(≥ 2)-ary asymmetric channel using t-Asymmetric Error Correcting/All Asymmetric Error Detecting (t-AEC/AAED) codes. The analysis shows that error correction definitely improves the throughput of the system compared to the ARQ protocol which uses only error detecting codes. The paper provides simple analytic expressions and bounds for the average number of retransmissions in both Plain and Diversity Combining t-AEC/AAED ARQ (t ≥ 0) protocol systems over the m-ary asymmetric channel, m ≥ 2. These can be applied into the design and analysis of error controlling schemes in practical systems such as VLSI and optical communications.

A symbol permutation invariant balanced (SPI-balanced) code over the alphabet Zopfm= {0, 1, ..., m - 1} is a block code over Zopfmsuch that each alphabet symbol occurs as many times as any other symbol in every codeword. For this reason, every permutation among the symbols of the alphabet changes an SPI-balanced code into an SPI-balanced code. This means that SPI-balanced words are "the most balanced" among all possible m-ary balanced word types and this property makes them very attractive from the application perspective. In particular, they can be used to achieve m-ary DC-free communication, to detect/correct asymmetric/unidirectional errors on the m-ary asymmetric/unidirectional channel, to achieve delay-insensitive communication, to maintain data integrity in digital optical disks, and so on. This paper gives some efficient methods to convert (encode) m-ary information sequences into m-ary SPI-balanced codes whose redundancy is equal to roughly double the minimum possible redundancy rmin. It is proven that rminsime [(m - 1)/2]logmn - (1/2)[1 - (1/log2pim)]m - (1/log2pim) for any code which converts k information digits into an SPI-balanced code of length n = k + r. For example, the first method given in the paper encodes k information digits into an SPI-balanced code of length n = k + r, with r = (m - 1) logmk + O(m logmlogmk). A second method is a recursive method, which uses the first as base code and encodes k digits into an SPI-balanced code of length n = k + r, with r sime (m - 1) logmn - logm[(m - 1)!]

Let /spl Phi//sub m//spl sube/ /spl Copf/ be the set of all mth roots of unity, m/spl isin/ IN. A balanced code over /spl Phi//sub m/ is a block code over the alphabet /spl Phi//sub m/ such that each code word is balanced; that is, the complex sum of its components (or weight) is equal to 0. Let B/sub m/(n) be the set of all balanced words of length n over /spl Phi//sub m/. In this correspondence, it is shown that when m is a prime number, the set B/sub m/(n) is not empty if, and only if, m divides n. In this case, the minimum redundancy for a balanced code over /spl Phi//sub m/ of length n is. On the other hand, it is shown that when m=4, the set B/sub 4/(n) is not empty if, and only if, n is even, and in this case, the minimum redundancy for a balanced code over /spl Phi//sub 4/ of length n is. Further, this correspondence completely solves the problem of designing efficient coding methods for balanced codes over /spl Phi//sub m/, when m=4. In fact, it reduces the problem of designing efficient coding schemes for balanced codes over /spl Phi//sub 4/ to the design of efficient balanced codes over the usual bipolar alphabet /spl Phi//sub 2/={-1,+1}.

In the automatic repeat request (ARQ) protocol, the sender keeps retransmitting a code word until it receives a positive acknowledgment from the receiver sent through the feedback channel. This correspondence proposes plain and diversity combining hybrid ARQ protocol communication schemes suitable for the m(ges2)-ary asymmetric channel using t-asymmetric error correcting/all asymmetric error detecting (t-AEC/AAED) codes. The analysis shows that error correction definitely improves the throughput of the system compared to the ARQ protocol which uses only error detecting codes. The correspondence provides simple analytic expressions for the average number of transmissions of a code word in both plain and diversity combining t-AEC/AAED ARQ (tges0) protocol systems over the m-ary asymmetric channel, mges2. An example is shown on how to get very close to the Z-channel capacity

A symbol permutation invariant balanced (SPI-balanced) code over the alphabet ZZm= {0, 1,....,m - 1} is a block code over ZZmsuch that each alphabet symbol occurs as many times as any other symbol in every codeword. For this reason every permutation among the symbols of the alphabet changes a SPI-balanced code into a SPI-balanced code. This means that SPI-balanced words are "the most balanced" among all possible m-ary balanced word types, and this property makes them very attractive from the application perspective. In particular, they can be used to achieve m-ary DC-free communication, to detect/correct asymmetric/unidirectional errors on the m-ary asymmetric/unidirectional channel, to achieve delay-insensitive communication, to maintain data integrity in digital optical disks, and so on. The paper gives some efficient methods to convert (encode) m-ary information sequences into m-ary SPI-balanced codes whose redundancy is equal to roughly double the minimum possible redundancy rminsime [(m - 1)/2] logmn - (1/2)[1 $(1/log2pim)] m - (1/log2pim) for SPI-balanced code with k information digits and length n = k + r. For example, the first method given in the paper encodes k information digits into a SPI-balanced code of length n = k + r, with r = (m - 1) logmk + O(m logmk). A second method is a recursive method, which uses the first as base code, and encodes k digits into a SPI-balanced code of length n = k + r, with r sime (m - 1) logmn $logm[(m - 1)!]

In the usual binary symmetric channel, both 1/spl rarr/0 and 0/spl rarr/1 types of errors can occur. In the binary asymmetric channel, only 1/spl rarr/0 type of errors can occur, whereas, in the unidirectional channel, both 1/spl rarr/0 and 0/spl rarr/1 types of errors can occur, but, unlike the binary symmetric channel, for any particular transmitted word of length n, all the errors are of the same type. In general, a symmetric/ unidirectional channel is a channel, which shows the behavior of both the symmetric and unidirectional channel. Many practical systems, such as semiconductor memories and circuits, can be modeled as a unidirectional and/or symmetric/unidirectional channels. This paper gives the formal definition of these last two channels and shows some interesting simple bounds on their information capacities.

In asynchronous systems, the sender encodes a data word with a code word from an unordered code and transmits the code word on the parallel bus lines. In this paper, a transmission time analysis for the above parallel asynchronous communication scheme is presented. It is proven that the average transmission time for a code word is a strictly increasing function of the weight of the code word and it approaches the worst transmission time possible when the weight goes to infinity. This implies that fast parallel asynchronous systems can be designed using low weight codes. This paper also analyzes the transmission time performances of the proximity detecting codes and gives some efficient low constant weight code designs.

A balanced code with k information bits and r check bits is a binary code of length n=k+r and cardinality 2/sup k/ such that the number of 1s in each code word is equal to [n/2]. This paper describes the design of efficient balanced codes with parallel encoding and parallel decoding. In this case, since area and delay of such circuits are critical factors, another parameter is introduced in the definition of balanced code: the "number of balancing functions used in the code design", p. Parallel encoding and decoding algorithms independent from the chosen balancing method are given and these can be implemented by a VLSI circuit of size O(pk) and depth O(logp). This paper also presents a new balancing method: the permutation method, which, for infinitely many values of k (such as, k=8, 10, 20, 22, 32, 34, ...) is more efficient than Knuth's complementation method. This new method results in efficient balanced codes with k information bits, k even, r=2[k/12]+2 check bits and p=6 balancing functions. Further, Knuth's complementation method is generalized to obtain efficient code designs for any value of the parameters k, r, and p, provided that k/spl les/2/spl Sigma//sub i=0//sup m/(/sub i//sup r/)+p(r-2m-1)[(kr+k+r) mod 2], where m is such that (/sub m-1//sup r/)

Let S (N,q) be the set of all words of length N over the bipolar alphabet (-1,+1), having a qth order spectral-null at zero frequency. Any subset of S (N,q) is a spectral-null code of length N and order q. This correspondence gives an equivalent formulation of S(N,q) in terms of codes over the binary alphabet (0,1), shows that S(N,2) is equivalent to a well-known class of single-error correcting and all unidirectional-error detecting (SEC-AUED) codes, derives an explicit expression for the redundancy of S(N,2), and presents new efficient recursive design methods for second-order spectral-null codes which are less redundant than the codes found in the literature.

Recently, Matsuzawa and Fujiwara (1988) proposed a novel scheme to mask line faults of bus line circuits (such as address buses) due to short circuit defects between adjacent lines. In this paper, first we propose the fundamental theory and then present some efficient designs of these codes. Some lower and upper bounds for the optimal codes are also given.

A constant weight, w, code with k information bits and r check bits is a binary code of length n=k+r and cardinality 2/sup k/ such that the number of 1s in each code word is equal to w. When w=[n/2], the code is called balanced. This paper describes the design of balanced and constant weight codes with parallel encoding and parallel decoding. Infinite families of efficient constant weight codes are given with the parameters k, r, and the "number of balancing functions used in the code design," /spl rho/. The larger /spl rho/ grows, the smaller r will be; and the codes can be encoded and decoded with VLSI circuits whose sizes and depths are proportional to pk and log/sub 2/ p, respectively. For example, a design is given for a constant weight w=33 code with k=64 information bits, r=10 check bits, and p=8 balancing functions. This code can be implemented by a VLSI circuit using less than 4,054 transistors with a depth of less than 30 transistors.

A balanced code with r check bits and k information bits is a binary code of length k+r and cardinality 2/sup k/ such that each codeword is balanced; that is, it has [(k+r)/2] 1's and [(k+r)/2] 0's. This paper contains new methods to construct efficient balanced codes. To design a balanced code, an information word with a low number of 1's or 0's is compressed and then balanced using the saved space. On the other hand, an information word having almost the same number of 1's and 0's is encoded using the single maps defined by Knuth's (1986) complementation method. Three different constructions are presented. Balanced codes with r check bits and k information bits with k/spl les/2/sup r+1/-2, k/spl les/3/spl times/2/sup r/-8, and k/spl les/5/spl times/2/sup r/-10r+c(r), c(r)/spl isin/{-15, -10, -5, 0, +5}, are given, improving the constructions found in the literature. In some cases, the first two constructions have a parallel coding scheme.