We study task-oriented lossy compression through the lens of rate-distortion-classification (RDC) representations. The source is Bernoulli, the distortion measure is Hamming, and the binary classification variable is coupled to the source via a binary symmetric model. Building on the one-shot common-randomness formulation, we first derive closed-form characterizations of the one-shot RDC and the dual distortion-rate-classification (DRC) tradeoffs. We then use a representation-based viewpoint and characterize the achievable distortion-classification (DC) region induced by a fixed representation by deriving its lower boundary via a linear program. Finally, we study universal encoders that must support a family of DC operating points and derive computable lower and upper bounds on the minimum asymptotic rate required for universality, thereby yielding bounds on the corresponding rate penalty. Numerical examples are provided to illustrate the achievable regions and the resulting universal RDC/DRC curves.

We study the problem of estimating a parametric discrete memoryless channel \( p(y \mid x; \boldsymbolθ) \) when the transmitter selects its input distribution \( π\) to maximize mutual information under the true parameter \( \boldsymbolθ^* \). Using only i.i.d.\ observations of the channel output, we aim to jointly estimate the capacity-achieving input distribution \( \boldsymbolπ^* \) and the true channel parameter \( \boldsymbolθ^* \). In general, recovery of \( \boldsymbolπ^* \) and \( \boldsymbolθ^* \) can be challenging. To that end, we propose two efficient algorithms based on the Blahut--Arimoto (BA) optimality conditions: (i) a bilevel fixed-point method and (ii) an augmented Lagrangian method. Empirical results demonstrate that both proposed algorithms successfully recover the true \( \boldsymbolθ^* \) and \( \boldsymbolπ^* \), whereas a naive maximum-likelihood approach that ignores the mutual-information maximization constraint fails to do so.

Quantization plays a central role in digital communication by mapping continuous-valued signals to a finite set of levels with minimal distortion. Beyond mean-square error, mutual information between the channel input and the quantizer output provides a powerful metric for signal recovery. However, finding the quantizer that maximizes the mutual information is NP-complete for non-binary inputs. To that end, while not optimal, thresholding schemes, whether single-threshold or multi-threshold, are widely adopted. In this work, we study the parallel stochastic single-threshold quantizer architecture, provide some information-theoretic insights, and introduce a momentum-accelerated gradient ascent algorithm that efficiently tunes a single decision threshold to maximize the mutual information. We demonstrate convergence improvements over exhaustive search and quantify mutual information gains across binary and non-binary input distributions. We also validate our theoretical framework with simulations on the MNIST dataset, demonstrating that increasing the number of parallel quantization branches, i.e., mutual information, significantly improves classification accuracy, especially when quantization thresholds are learned and training data is limited.

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 lossy compression, Wang et al. [1] recently introduced the rate-distortion-perception-classification function, which supports multi-task learning by jointly optimizing perceptual quality, classification accuracy, and reconstruction fidelity. Building on the concept of a universal encoder introduced in [2], we investigate the universal representations that enable a broad range of distortion-classification tradeoffs through a single shared encoder coupled with multiple task-specific decoders. We establish, through both theoretical analysis and numerical experiment, that for a Gaussian source under mean-squared error (MSE) distortion, the distortion-classification tradeoff region can be achieved using a single universal encoder. For general sources, we characterize the achievable region and identify conditions under which a universal encoder can produce a small distortion penalty. The experimental result on the MNIST dataset further supports our theoretical findings. We show that universal encoders can obtain distortion performance comparable to task-specific encoders. These results demonstrate the practicality and effectiveness of the proposed universal framework in multi-task compression scenarios.

This paper presents the approach to design the inverter based CTLE at the minimum power consumption point and at minimum noise power product point while meeting the desired specification target. Lagrangian function for constrained optimization is formed. Mathematical close form expressions of the CTLE parameters are derived. Using the proposed design approach, an inverter based CTLE architecture with four different design constraints was designed and simulated in 16nm FinFET and in 65nm CMOS technology to validate existence of minimum power point design.

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).

We study the problem of virtual machine (VM) placement and migration in a data center. In the current approaches, VMs are assigned to physical servers using on-demand provisioning. Such an approach is simple but it often results in a poor performance due to resource fragmentation. Additionally, sub-optimal VM placement usually generates unneeded VM migration and unnecessary cross network traffic. The efficiency of a datacenter therefore significantly depends on how VMs are provisioned and where they are placed. A good placement scheme will not only improve the quality of service but also reduce the operation cost of the data center. In this paper, we study the problem of optimal VM placement and migration to minimize resource usage and power consumption in a data center. We formulate the optimization problem as a joint multiple objective function and solve it by leveraging the framework of convex optimization. Due to the intractable nature of the combinatorial optimization, we then propose Multi-level Join VM Placement and Migration (MJPM) algorithms based on the relaxed convex optimization framework to approximate the optimal solution. The theoretical analysis demonstrates the effectiveness of our proposed algorithms that substantially increases data center efficiency. In addition, our extensive simulation results on different practical topologies show significant performance improvement over the existing approaches.

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.

Traditional bus-based interconnects are simple and easy to implement, but the scalability is greatly limited. While router-based networks-on-chip (NoCs) offer superior scalability, they also incur significant power and area overhead due to complex router structures. In this paper, we explore a new class of on-chip networks, referred to as Routerless NoCs, where routers are completely eliminated. We propose a novel design that utilizes on-chip wiring resources smartly to achieve comparable hop count and scalability as router-based NoCs. Several effective techniques are also proposed that significantly reduce the resource requirement to avoid new network abnormalities in routerless NoC designs. Evaluation results show that, compared with a conventional mesh, the proposed routerless NoC achieves 9.5X reduction in power, 7.2X reduction in area, 2.5X reduction in zero-load packet latency, and 1.7X increase in throughput. Compared with a state-of-the-art low-cost NoC design, the proposed approach achieves 7.7X reduction in power, 3.3X reduction in area, 1.3X reduction in zero-load packet latency, and 1.6X increase in throughput.

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.

Gaussian networks are degree four symmetric networks and these are designed based on the concept of Gaussian integers. The Gaussian network can be described in terms of a generator α = α + bi, where a and bare integers and i = √-1 . When gcd(a,b) = 1, how to find edge disjoint Hamiltonian cycles has been shown before. In this paper for any generator α = α + bi, even when gcd(a,b) = d > 1, how to obtain two edge disjoint Hamiltonian cycles in these networks is 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.

Gaussian interconnection networks have been introduced as a useful alternative to the classical toroidal networks, and in this paper this concept is generalized to higher dimensions. We also explore many important properties of this new topology, including distance distribution and the decomposition of higher dimensional Gaussian networks into edge-disjoint tori and Hamiltonian cycles. In addition, an optimal shortest path routing algorithm and a one-to-all broadcast algorithm for higher dimensional Gaussian networks are given. Simulation results show that the routing algorithm proposed for higher dimensional Gaussian networks outperforms the routing algorithm of the corresponding torus network of the same node-degree and the same number of nodes.

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.

Efficiently managing virtual machines (VMs) plays a key role in improving the resource usage and power consumption of datacenters. However, most of the existing techniques have been optimized for each system criterion separately (e.g., either platform layer or virtualization layer). Such approaches are simple to implement, but they usually result in poor system performance or under-utilization of the resources. In this paper, we investigate the problem of optimal VM management (i.e., placement and migration) in datacenters via a multi-objective function. We show that optimizing the proposed multi-objective function reduces not only the energy consumption, but also the cross network traffic among platforms. Due to the high complexity of the combinatorial optimization problem, we propose an efficient heuristic algorithm to find a near optimal solution based on the relaxed convex optimization framework. We provide both theoretical analysis and simulations to show the effectiveness of the proposed approach over the existing approaches.

Some new classes of Hamming metric Gray codes over Zpn, where p is a prime and n is an integer power of 2, are described; then, how these Gray codes can be used to generate the maximum number of edge-disjoint Hamiltonian cycles in an n-dimensional generalized hypercube (GHC), Qpn, is shown. For Qpn, the number of edge-disjoint Hamiltonian cycles generated using these methods is n(p -1)/2 which is the maximum possible since the degree of each node in Qpnis n(p - 1). In addition, for any integers p and n, p not necessarily a prime and n not necessarily a power of 2, how to generate the maximum number of edge-disjoint Hamiltonian cycles in Qnp is also described.

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.

The error detecting problem for limited magnitude errors over high radix channels is studied. In this error model, the error magnitude does not exceed a certain limited value and it is known beforehand. For asymmetric, unidirectional, and symmetric channels, both all and t error detecting codes are studied. In all these cases, close-to-optimal codes are proposed.

In a multiprocessor system, a limited number of resources need to be uniformly distributed so that all processor nodes can have equal access to these resources. This is referred to as the resource placement problem. In a perfect t--placement each nonresource node is at a distance of t or less from exactly one resource node. Here, we first find all perfect t-placements in the infinite square and triangular grids. That information is then used to show that translates of earlier sets are the only perfect t-placements in Gaussian and EJ interconnection networks.

In multilevel flash memories, leakage of charges results in errors, and the errors are asymmetric, of increasing type and of limited magnitude. On the other hand, low data retention may result in asymmetric errors of decreasing type and usually of smaller magnitude. Therefore, we have unbalanced error types. In this paper, some codes for correcting such errors are presented.

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.

In this paper, we show that the hexagonal mesh networks developed in the early 1990s are a special case of the EJ networks that have been considered more recently. Using a node addressing scheme based on the EJ number system, we give a shortest path routing algorithm for hexagonal mesh networks. We also extend the known efficient one-to-all broadcasting algorithm on hexagonal mesh networks to algorithms for one-to-one personalized broadcasting, all-to-all broadcasting, and all-to-all personalized broadcasting algorithms. Their time complexity and optimality are analyzed.

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.

A relatively new model of error correction is the limited magnitude error model. That is, it is assumed that the absolute difference between the sent and received symbols is bounded above by a certain value$l$. In this paper, we propose systematic codes for asymmetric limited magnitude channels that are able to correct a single error. We also show how this construction can be slightly modified to design codes that can correct a single symmetric error of limited magnitude. The designed codes achieve higher code rates than single error correcting codes previously given in the literature.

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.

Systematic q-ary (q> 2) codes capable of correcting all asymmetric errors of maximum magnitudel, where l ¿ q - 2, are given. These codes are shown to be optimal. Further, simple encoding/decoding algorithms are described. The proposed code can be modified to design codes correcting all symmetric errors of maximum magnitudel, wherel¿ (q-2)/2.

Earlier authors have used quotient rings of Gaussian and Eisenstein-Jacobi integers to construct interconnection networks with good topological properties. In this paper, we present a unified study of these two types of networks. Our results include decomposing the edges into disjoint Hamiltonian cycles, a simplification of the calculation of the Eisenstein-Jacobi distance, a distribution of the distances between Eisenstein-Jacobi nodes, and shortest path routing algorithms. In particular, the known Gaussian routing algorithm is simplified.

Systematic q-ary (q > 2) codes capable of correcting all asymmetric errors of maximum magnitude l, where l ¿ q-2, are given. These codes are shown to be optimal. Further, simple encoding/decoding algorithms are described.

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 paper, we investigate a hybrid network coding technique to be used at a wireless base station (BS) or access point (AP) to increase the throughput efficiency of single-hop wireless networks. Traditionally, to provide reliability, lost packets from different flows (applications) are retransmitted separately, leading to inefficient use of wireless bandwidth. Using the proposed hybrid network coding approach, the BS encodes these lost packets, possibly from different flows together before broadcasting them to all wireless users. In this way, multiple wireless receivers can recover their lost packets simultaneously with a single transmission from the BS. Furthermore, simulations and theoretical analysis showed that when used in conjunction with an appropriate channel coding technique under typical channel conditions, this approach can increase the throughput efficiency up to 3.5 times over the automatic repeat request (ARQ), and up to 1.5 times over the HARQ techniques.

In diversity combining automatic repeat request (ARQ), erroneous packets are combined together forming a single, more reliable, packet. In this paper, we give a diversity combining scheme for the m-ary unidirectional channel. A system using the given scheme with a t-unidirectional error detecting code is able to correct up to Emax= [t/2] unidirectional errors. Simulation results show that the underlined diversity combining protocol significantly increases the channel throughput over plain ARQ. To use the given scheme, the decoder should be able to decide the error type (increasing or decreasing). Hence, we give simple techniques to make this decision for various unidirectional error detecting codes.

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.

Gray codes, where two consecutive codewords differ in exactly one position by plusmn1, are given. In a single radix code, all dimensions have the same base, sayk, whereas in a mixed radix code the base in one dimension can be different from the base in another dimension. Constructions of new classes of mixed radix Gray codes are presented. It is shown how acyclicmixedradixGraycodecorresponds to a Hamiltonian cycle in a mixed radix toroidal graph. It is then shown how these codes can be used as a basis for constructing edge disjoint Hamiltonian cycles in mixed radix toroidal networks when the number of dimensions, n = 2rfor some r ges 0.

Gray codes, where two consecutive codewords differ in exactly one position by plusmn1, are given. In a single-radix code, all dimensions have the same base, say, kappa, whereas, in a mixed-radix code, the base in one dimension can be different from the base in another dimension. Constructions of new classes of mixed-radix Gray codes are presented. It is shown how these codes can be used as a basis for constructing edge-disjoint Hamiltonian cycles in mixed-radix toroidal networks when the number of dimensions n = 2rfor some r ges 0. Efficient algorithms for the generation of these codes are then shown.

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.

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

This paper introduces a type-I hybrid ARQ scheme for the Z-channel, based on a class of codes which can correct t asymmetric errors and further detect d (d > t) more. The specific parameters of the ARQ schemes are considered and an upper bound on the probability of undetected error is derived. We give a couple of detailed examples based on classic inner error correcting codes. They show good behavior of this scheme in terms of error rate and throughput

Corrupted packets that cause retransmission requests in automatic retransmission request (ARQ) systems can be reused. They can be combined with additional stored copies of the transmitted packet in order to obtain a single packet which is more reliable than any of the constituents. A scheme which suits the Z-channel is proposed here and the performance is analyzed under different coding assumptions.

Bose and Lin introduced a class of systematic codes for the detection of asymmetric errors (or equivalently, unidirectional errors). The determination of the probability of undetected error for these codes has been an open problem for many years. In this correspondence, the undetectable errors are characterized and the probability of undetected error is determined. Some detailed examples are given.

In this paper, the code that capable of correcting t-errors and detecting unidirectional errors (t-EC-AUED code) is presented. The t-EC AUED code is studied with the maximal size by using Sperner's theorem. The theorem says that the balanced code is an optimal all unidirectional error detecting code with the maximum number of code words.

Bose and Lin introduced a class of systematics codes for the detection of unidirectional errors (or equivalently, asymmetric errors). The codes are described, the undetectable errors are characterized, and the probability of undetected error for these codes is determined.

Solutions for decomposing a higher dimensional torus to edge disjoint lower dimensional tori, in particular, edge disjoint Hamiltonian cycles are obtained based on the coding theory approach. First, Lee distance Gray codes in Z/sub k//sup n/ are presented and then it is shown how these codes can directly be used to generate edge disjoint Hamiltonian cycles in k-ary n-cubes. Further, some new classes of binary Gray codes are designed from these Lee distance Gray codes and, using these new classes of binary Gray codes, edge disjoint Hamiltonian cycles in hypercubes are generated.

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.

In this paper, we introduce two encoding and decoding methods for balanced codes. The proposed methods are more efficient in terms of computational complexity. The first one complements several appropriate bits at a time instead of complementing one bit at a time as done in Knuth's method. The second one is a parallel implementation of Knuth's method.

A construction of perfect/quasiperfect Lee distance codes in Z/sub K//sup 2/ is introduced. For this class of codes, a constant time encoding scheme is defined, the minimum code distance is derived, and the maximum covering radius is calculated. Efficient decoding schemes are investigated and developed. In general, a code of this class can be decoded in O(t/sub 1/), where t/sub 1/ is the number of errors that can be corrected. Special cases, however, can be decoded in constant time.

In ARQ systems packets that cause retransmission requests can be reused. A diversity combining scheme for the Z-channel is proposed here, which significantly improves the throughput and the accepted packet error rate of a pure ARQ protocol using asymmetric error detection.

In this paper, based on coding theory concepts, a new time scheduling algorithm for multihop packet radio networks is described. Each mobile host is assigned a word from an appropriate constant weight code of length n, distance d and weight w. The host can send a message at the j/sup th/ slot provided the assigned code has a 1 in this j/sup th/ bit. The proposed algorithm is better than the previously known algorithms in terms of minimum system throughput. The algorithm also preserves other desired properties, such as topology independence, guaranteed minimum throughput, bounded maximum delay, and fair transmission policy.

Mobile hosts typically have scarce energy due to short battery lifetimes. We propose a scheduling algorithm which is suitable for battery-constrained multihop packet radio networks. The proposed algorithm, called ECTS (energy conserving transmission scheduling), focuses on conserving battery power while preserving topology transparency, guaranteed minimum throughput, bounded maximum delay, and fair transmission policy. The ECTS algorithm conserves the power using strategies that allow the network interface to use the low power sleep mode instead of the idle mode, and eliminates data collisions using RTS (request-to-send) and CTS (clear-to-send) control slots. As observed in previous experiments, the cost of mode transition is quite expensive. To relieve this unnecessary power consumption, the ECTS algorithm significantly reduces the number of mode transitions. For low-power hosts, the ECTS protocol reduces the number of mode transitions further. We have simulated and compared the energy efficiency of our protocol with the IEEE 802.11 and GRAND (Galois radio network design) algorithms. Simulation results show our protocol is very efficient in terms of power conservation.

The errors in optical communication are of the asymmetric type. Using the Z-channel model, the Bose-Lin asymmetric error detecting codes are analyzed as part of a feedback communication system. The probabilities of detectable and undetectable errors are derived from the code construction using certain properties of the information and check sequences. This is done for two check bits initially, then generalized for any number of check bits. Based on these probabilities, the accepted packet error rate and the throughput can be calculated for pure ARQ protocols. The results obtained show very good performance, in terms of error rate and throughput efficiency, for optical networks.

Lee distance Gray codes for k-ary n-cubes and torus networks are presented. Using these Lee distance Gray codes, it is further shown how to directly generate edge disjoint Hamiltonian cycles for a class of k-ary n-cubes, 2-D tori, and hypercubes.

A fault ring is a connection of only nonfaulty adjacent nodes and links such that the interior of the ring contains only faulty components. This paper proposes two wormhole routing algorithms that deal with more relaxed shapes of fault rings than previously known algorithms in the mesh networks. As a result, the number of components to be made disabled would be reduced considerably in some cases. First algorithm, called F4, uses four virtual channels and allows all four sides of fault rings to contain concave shapes. Second algorithm, F3, permits up to three sides to contain concave shapes using only three virtual channels. Both F3 and F4 are free of deadlock and livelock and guarantee the delivery of messages between any pair of nonfaulty and connected nodes in the network.

A binary code of length n is called a balanced code if each codeword contains exactly [n/2] (or [n/2]) ones and [n/2] (or [n/2]) zeros. In this paper, we give two improved methods for encoding and decoding balanced codes. The first one, called improved single map, improves the computation complexity of Knuth's single map function. This method, instead of complementing one bit at a time as done in Knuth's method, complements several appropriate bits at a time. Some simulation results show the improvement of this scheme over the previously known methods. The second one is a parallel implementation of this method.

It is proved that for all values of code length n, except when n=2, 4, and 8 and possibly when n=2/sup r/ and n=2/sup r/+1, where r/spl ges/1, the Hamming codes are also optimal systematic single asymmetric error-correcting codes. For the cases n=2/sup r/ and n=2/sup r/+1, r/spl ges/4, when not all information words are used, two efficient systematic 1-asymmetric codes are described.

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.

Fault-tolerant communication algorithms for k-ary n-cubes are introduced. These include: One-to-all broadcasting, all-to-all broadcasting, one-to-all personalized communication, and all-to-all personalized communication. Each of these algorithms can tolerate up to (2n-2) node failures provided that k>(2n-2) and k>3. Extensions of these algorithms with up to 2n-1 node failures are also described. The communication complexities of the proposed algorithms are derived when wormhole or store and forward packet routing is used.

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.

This paper investigates methods to locate system resources, such as expensive hardware or software modules, to provide the most effective cost/performance trade-offs in a torus parallel machine. This paper contains some solutions to perfect distance-t and perfectiquasi-perfect j-adjacency placement in a k-ary n-cube and a torus using Lee distance error-correcting codes. It also presents generalized resource placement (j-adjacency with distance-t placement) methods based on the concept of covering radius of Lee distance codes.

A new fault-tolerant all-to-all broadcasting algorithm in an n-dimensional hypercube with up to [n/2] faulty links is given. An extension of this algorithm that can tolerate up to [n/2] faulty nodes is also described. These algorithms assume a multiport I/O model, meaning each node can send and receive messages from all its adjacent nodes simultaneously. The total time steps taken by the proposed algorithms are near optimal, and they produce a factor of n less traffic than previously known algorithms.

We present a distributed network-level algorithm that constructs a cycle in a d-ary De Bruijn multiprocessor network in the presence of an arbitrary number of node failures. When the number of faults f does not exceed d-1 a cycle of length at least d/sup n/-nf-1 can always be found in O(n) steps in a network of size d/sup n/.

Recently, a self-testing ALU design has been proposed that uses Berger codes and compares the check value of the ALU output to a predicted check value that is calculated based on the input operand check values. Berger codes have the property of being able to detect all unidirectional errors. More efficient codes exist for detecting up to t unidirectional errors. This paper examines applying these codes to self-testing ALU designs and shows that the potential savings in check circuitry over Berger codes is up to 61%, depending on the code and the information word length.

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.

In this paper, we consider various topological properties of a k-ary n-cube (Q/sub n//sup k/) using Lee distance. We feel that Lee distance is a natural metric for defining and studying a Q/sub n//sup k/. After defining a Q/sub n//sup k/ graph using Lee distance, we show how to find all disjoint paths between any two nodes. Given a sequence of radix k numbers, a function mapping the sequence to a Gray code sequence is presented, and this function is used to generate a Hamiltonian cycle. Embedding the graph of a mesh and the graph of a binary hypercube into the graph of a Q/sub n//sup k/ is considered. Using a k-ary Gray code, we show the embedding of a k(n/sub 1/)/spl times/k(n/sub 2/)/spl times/.../spl times/k(n/sub m/)-dimensional mesh into a Q/sub n//sup k/ where n=/spl Sigma//sub i=l//sup m/n/sub i/. Then using a single digit, 4-ary reflective Gray code, we demonstrate embedding a Q/sub n/ into Q/sub [n/2]//sup 4/. We look at how Lee distance may be applied to the problem of resource placement in a Q/sub n//sup k/ by using a Lee distance error-correcting code. Although the results in this paper are only preliminary, Lee distance error-correcting codes have not been applied previously to this problem. Finally, we consider how Lee distance can be applied to message routing and single-node broadcasting in a Q/sub n//sup k/. In this section we present two single-node broadcasting algorithms that are optimal when single-port and multi-port I/O is used.>

All words in a balanced code have equal number of ones and zeros. Denote by DC(n,k) a balanced (or dc-free) code of length n, and 2/sup k/ code words. We design an efficient DC(k+r, k) code with k=2/sup r+1//spl minus/0.8/spl radic/(r/spl minus/2). These codes are optimal up to the construction method, introduced by D.E. Knuth (1986).>

Introduces the theory and design of codes that correct t asymmetric errors and simultaneously detect d(d>t) asymmetric errors (t-AEC/d-AED). These codes have a much higher information rate than symmetric error correcting/detecting codes and yet maintain the same encoding and decoding complexity as existing error correcting codes. They are suited for asymmetric channels such as digital transmission over optical fiber or metallic cable and recording of data on optical disks. The authors also improve the design of the best-known t-EC/AUED (t symmetric error correcting and all unidirectional error detecting) codes and t-EC/d-UED (t symmetric error correcting and d unidirectional error detecting) codes.>

New constructions of t-error correcting balanced codes, for 1>

A method of embedding a ring in a d-ary de Bruijn multiprocessor network in the event of multiple node (processor) failures is presented. In particular, the algorithm guarantees that a (2/sup n/-n-1)-node ring will be found in a binary de Bruijn network with a single faulty node, where 2/sup n/ is the total number of nodes in the network. It is also shown that a (d/sup n/-1)-node ring can always be found in the presence of d-1 link failures, when d is a prime power and the network contains d/sup n/ nodes. The latter is accomplished by constructing d-1 edge-disjoint cycles each of length d/sup n/-1. A modification of the graph that allows it to admit a Hamiltonian cycle in the event of d-1 edge failures is also discussed.>

Efficient byte unidirectional error correcting codes that are better than byte symmetric error correcting codes are presented. The encoding and decoding algorithms are discussed. A lower bound on the number of check bits for byte unidirectional error correcting codes is derived. It is then shown that these codes are close to optimal. Capability of these codes for asymmetric error correction is also described. Codes capable of detecting double byte unidirectional errors are also given.>

By extending the results obtained by D. E. Knuth (1986), a parallel unordered coding scheme with 2/sup r/ information bits is described. Balanced codes in which each codeword contains equal amounts of zeros and ones, with r check bits and up to 2/sup r+1/-(r+2) information bits, are constructed. Unordered codes with r check bits and up to 2/sup r/+2/sup r-1/-1 information bits are designed. Codes capable of detecting 2/sup r-1/+(2/sup r//2)-1 unidirectional errors using r check bits are also described. A review of previous work is presented.>

In a balanced code each codeword contains equally many 1's and 0's. Parallel decoding balanced codes with 2/sup r/ (or 2/sup r/-1) information bits are presented, where r is the number of check bits. The 2/sup 2/-r-1 construction given by D.E. Knuth (ibid., vol.32, no.1, p.51-3, 1986) is improved. The new codes are shown to be optimal when Knuth's complementation method is used.>

Two constructions for double-asymmetric-error-correcting codes are given. These codes offer some desirable properties for optical communication, where it is important that most codewords have small weights. The first construction gives a subset of a double-error-correcting BCH code. The code offers considerable improvement in the weight distribution at the expense of one extra bit of redundancy (in almost all cases) over the BCH code. The code is semisystematic and has the same degree of encoding/decoding complexity as the BCH code. The second construction is completely systematic and has twice the information rate as the BCH code in several cases. This code is easy to encode and decode and has fewer 1s than 0s.>

The fundamental theory of t-error correcting and d(d>

Systematic codes capable of detecting burst unidrectional errors of length up to 2r−1using r check bits where r ≥ 3 are presented. Moreover, b-adjacent unidirectional error-detecting codes using [log2(b + 1)] check bits are also described. These codes are shown to be optimal or near optimal. The encoding/decoding and the totally self- checking checker design methods for these codes are also given.

The theory and design of systematic t-unidirectional error-detecting codes are developed. Optimal systematic codes capable of detecting 2, 3, and 6 unidirectional errors using 2, 3, and 4 check bits, respectively, are given. For r ≥5 where r is the number of check bits, the systematic codes described here can detect up to 5· 2r-4 + r -4 unidirectional errors. Encoding/ decoding methods for these codes are also investigated.

Unidirectional error protecting codes for VLSI memories are described. After developing the theory of unidirectional error detection and correction, optimal systematic codes capable of detecting unidirectional errors are presented. Efficient single error correcting and d(d≥2)-unidirectional error detecting codes are also discussed.

PLA implementations of totally self-checking (TSC) checkers for k-out-of-n codes, where 2 ≤k ≤ n -2, are presented. For k-out-of-2k, k-out-of-2k + 1, k + 1-out-of-2k + 1, and k ± 1-out-of-2k codes, TSC checkers are designed using only one PLA. TSC checkers for all other codes are designed using 2 PLA's, and in fact the second PLA is very small for most of the codes.

In this correspondence we give an efficient error control technique for mass memories such as magnetic bubble memories, magnetic tapes, etc. The code discussed here is a modification of the cyclic redundancy check (CRC) used in magnetic tape units. An arithmetic redundancy check (ARC) with respect to an appropriate modulus (or check base) replaces the CRC, and the result is a systematic code which provides correction of multiple unidirectional errors in any one track of a large block of characters. The information rate of this code is much higher than that of the CRC code.

In this correspondence a class of t-error correcting and multiple unidirectional error detecting systematic codes is presented. These codes are significantly more efficient than the earlier codes. The efficiency of these codes approaches the efficiency of the BCH codes, asymptotically. Furthermore, it is shown that these codes can be easily decoded. Also in this correspondence we have presented a generalization of Berger codes over Zq; these new codes are also shown to be optimal.

In this paper we present some basic theory on unidirectional error correcting/detecting codes. We define symmetric, asymmetric, and unidirectional error classes and proceed to derive the necessary and sufficient conditions for a binary code to be unidirectional error correcting/detecting.

In this correspondence, we present some more properties of separating systems (SS) and completely separating systems (CSS) from coding theory framework. First we derive the necessary and sufficient conditions for a set of vectors to be a SS or CSS. Then we show that in the case of linear codes, the necessary and sufficient conditions required for (1, 1) CSS are similar to that of (2, 1) SS and by deleting the 0 vector from a binary code that forms a (2, 1) SS, the set of remaining code words forms a (1, 1) CSS. Even though some linear codes form (2, 1) and (2, 2) SS, we prove here that no linear code forms a(2, 1) or a(2, 2) CSS.

In the above paper,1the authors have defined complete test, closed fault set, fault set graph, and undetected fault set as follows.