This article deals with distributed address determination for mobile Grids, realized by ADENS (address determination via neighboring states), where a new mobile host (MH) determines a conflict-free address for itself efficiently according to state information only from neighboring MHs. With low traffic overhead, ADENS achieves higher address space utilization than the best known approach. The optimal design of basic ADENS has been derived analytically for the first time. Enhanced ADENS can be achieved by designating appropriate MHs (instead of permitting all MHs) to respond to address requests of newly arrived MHs, further improving address space utilization markedly while lowering traffic overhead drastically. Our simulation results reveal that enhanced ADENS enables a mobile Grid to operate practically as long as it needs.

This paper presents a class of binary maximum distance separable (MDS) array codes for tolerating disk failures in redundant arrays of inexpensive disks (RAID) architecture based on circular permutation matrices. The size of the information part is m/spl times/n, the size of the parity-check part is m/spl times/3, and the minimum distance is 4, where n is the number of information disks, the number of parity-check disks is 3, and (m+1) is a prime integer. In practical applications, m can be very large and n is from 20 to 50. The code rate is R=n/(n+3). These codes can be used for tolerating three disk failures. The encoding and decoding of the Reed-Solomon-like codes are very fast. There need to be 3mn XOR operations for encoding and (3mn+9(m+1)) XOR operations for decoding.

For pt.1 see ibid., vol.54, no.9, p.1071-1080 (2005). A new class of binary maximum distance separable (MDS) array codes which are based on circular permutation matrices are introduced in this paper. These array codes are used for tolerating multiple (/spl ges/ 4) disk failures in redundant arrays of inexpensive disks (RAID) architecture. The size of the information part is m /spl times/ n, where n is the number of information disks and (m + 1) is a prime integer; the size of the parity-check part is m /spl times/ r, the minimum distance is r + 1, and the number of parity-check disks is r. In practical applications, m can be very large and n ranges from 20 to 50. The code rate is R = n/(n+r). These codes can be used for tolerating up to r disk failures, with very fast encoding and decoding. The complexities of encoding and decoding algorithms are O(rmn) and O(m/sup 3/r/sup 4/), respectively. When r = 4, there need to be 9mn XOR operations for encoding and (9n + 95)(m + 1) XOR operations for decoding.

In this paper, we attempt to use algebraic-geometric codes to solve the polynomial reconstruction problem, which is the key step for the algebraic IP traceback over the Internet to defend against the DoS attacks. The detailed mathematical expression for the fullpath polynomial is given with analysis showing the deterministic characteristic, the backward compatibility, the low time and storage complexity and the incremental deployment of our scheme. Furthermore, how to reduce the overhead in the IP header is proposed and analyzed with details in this paper. The comparison of our scheme with other related work shows that our scheme can not only be implemented for today's routers (IPv4), but also be extended for future router's usage whenever the router IP address be enlarged (IPv6).

Summary form only given. There are in fact two main parts in this paper. One is a modification to context-tree weighting algorithm known as CTW, and the other is a new algorithm called grouping. In the CTW method, we consider a binary tree as a context-tree T/sub D/, where each node s in this tree has length l(s) with 0/spl ges/l(s)/spl ges/D for a source generating a sequence of binary digits. There are counts a/sub s/, and b/sub s/, for each node s of T/sub D/ denoting the number of zeros and ones respectively. Each internal node s of the tree has two children 0s and 1s. The root of the tree corresponds to memoryless model /spl lambda/ and each node corresponds to a prefix sequence. The second part of the paper, introduces a new algorithm that considers all different binary trees of length /spl ges/D as complete sets of alphabets for a binary source. By using the KT estimator for each of these alphabet models, we find the probability distribution gained by all different complete extended alphabets. By grouping these models, we define the coding distribution as the average of the probabilities for all the models. We have demonstrated a quick algorithm for this idea and call this approach a grouping algorithm. This approach also breaks the extended alphabet model probability distribution into the non-extended one. Note that the result of this algorithm will produce at most log M(D) more code words than the optimal selection of strings of length at most D, as letters of the alphabet.

Double-byte error-correcting codes over GF(q) were constructed by Dumer (1981, 1988, 1992, 1995), which have the parameters n=q/sup m-1/, r/spl les/2m+[m-1/3], m=2, 3, ..., when q is even, and have the parameters n=q/sup m/, r/spl les/2m+[m/3]+1, m=2; 3, ..., when q is odd, respectively. We construct a class of double-byte error-correcting codes over GF(2/sup i/), which have the following parameters: n=q/sup m/, r/spl les/2m+[m/3]+1, m=3, 4, .... So our constructions reduce the code redundancy of Dumer by one symbol, and we eliminate the disparity in code redundancies obtained for even and odd q. A decoding procedure for our codes is also considered.

When multiple copies of a certain resource exist in a cube network system, it is desirable that every nonresource node can reach the resource in a given number of hops. In this paper, we introduce systematic approaches to resource allocation in a cube system so that each nonresource node is connected with a specified number of resource copies and that the allocation performance measure of interest is optimized. The methodology used is based on the covering radius results of known codes. These codes aid in constructing desired linear codes whose codewords address nodes where resource copies are placed. The resource allocation problem is translated to an integer nonlinear program whose best possible solution can be identified quickly by taking advantage of basic properties derived from the known codes, yielding an optimal or near-optimal allocation result. Those basic properties lead to drastic time complexity reduction (up to several orders of magnitude smaller), in particular for large system sizes. Our approaches are applicable to any cube size, often arriving at more efficient allocation outcomes than what are attainable using prior schemes.

In this paper, we present a construction of improved geometric Goppa codes which, for the case of r<2g, are often more efficient than the current geometric Goppa codes derived from some varieties, which include algebraic curves, hyperplanes, surfaces, and other varieties. For the special case of a plane in a three-dimensional projective space, the improved geometric Goppa codes are reduced to linear multilevel codes. For these improved geometric Goppa codes, a designed minimum distance can be easily determined and a decoding procedure which corrects up to half the designed minimum distance is also given.

Algorithm-based fault tolerance is a scheme of low-cost error protection in real-time digital signal processing environments and other computation-intensive tasks. In this paper, a new method for encoding data is proposed and, furthermore, two kinds of error-correcting codes over Z/sub 2(m/), which can be used with fixed-point arithmetic in practical algorithm-based fault tolerant systems, are introduced.>

The current algebraic-geometric (AG) codes are based on the theory of algebraic-geometric curves. In this paper we present a simple approach for the construction of AG codes, which does not require an extensive background in algebraic geometry. Given an affine plane irreducible curve and its set of all rational points, we can find a sequence of monomials x/sup i/y/sup j/ based on the equation of the curve. Using the first r monomials as a basis for the dual code of a linear code, the designed minimum distance d of the linear code, called the AG code, can be easily determined. For these codes, we show a fast decoding procedure with a complexity O(n/sup 7/3/), which can correct errors up to [(d-1/2]. For this approach it is neither necessary to know the genus of curve nor the basis of a differential form. This approach can be easily understood by most engineers.>

The paper presents a new procedure for decoding cyclic and BCH codes up to their actual minimum distance. It generalizes the Peterson decoding procedure and the procedure of Feng and Tzeng (1991) using nonrecurrent syndrome dependence relations. For a code with actual minimum distance d to correct up to t=[(d-1)/2] errors, the procedure requires a (2t+1)/spl times/(2t+1) syndrome matrix with known syndromes above the minor diagonal and unknown syndromes and their conjugates on the minor diagonal. In contrast to previous procedures, this procedure is primarily aimed at solving for the unknown syndromes instead of determining an error-locator polynomial. Decoding is then accomplished by determining the error vector as the inverse Fourier transform of the syndrome vector (S/sub 0/, S/sub 1/, S/sub n-1/). The authors show that with this procedure, all binary cyclic and BCH codes of length>

An efficient decoding algorithm for algebraic-geometric codes is presented. For codes from a large class of irreducible plane curves, including Hermitian curves, it can correct up to [(d*-1)/2] errors, where d* is the designed minimum distance. With it we also obtain a proof of d/sub min//spl ges/d* without directly using the Riemann-Roch theorem. The algorithm consists of Gaussian elimination on a specially arranged syndrome matrix, followed by a novel majority voting scheme. A fast implementation incorporating block Hankel matrix techniques is obtained whose worst-case running time is O(mn/sup 2/), where m is the degree of the curve. Applications of our techniques to decoding other algebraic-geometric codes, to decoding BCH codes to actual minimum distance, and to two-dimensional shift register synthesis are also presented.>

Elias (1991) derived upper and lower bounds on the sizes of error-correcting codes for list decoding. The asymptotic values of his lower bounds for linear codes and for nonlinear codes are separated. The present authors derive improved lower bounds for linear and for nonlinear codes. They conjecture their two bounds are identical. However, they were able to verify this only for small lists.>

We introduce systematic approaches to resource allocation in a cube system so that each non resource node is connected with one resource copy and that the allocation performance measure of interest is optimized.

Totally self-checking (TSC) Berger code checker designs are presented. The generalized Berger check partitioning is derived. It is proven that a TSC Berger code checker can be constructed from a TSC m-out-of-n checker. For a TSC Berger code checker design, no two-output checker exists for information length 2/sup r-1/, for any positive nonzero r. The presented approach solves this open problem.>

A simple decoding procedure for algebraic-geometric codes C/sub Omega /(D,G) is presented. This decoding procedure is a generalization of Peterson's decoding procedure for the BCH codes. It can be used to correct any ((d*-1)/2) or fewer errors with complexity O(n/sup 3/), where d* is the designed minimum distance of the algebraic-geometric code and n is the codelength.>

The generalized Hamming weights of a linear code are fundamental code parameters related to the minimal overlap structures of the subcodes. They were introduced by V.K. Wei (1991) and shown to characterize the performance of the linear code in certain cryptographical applications. Results are presented on the generalized Hamming weights of several classes of binary cyclic codes, including primitive double-error-correcting and triple-error-correcting BCH codes, certain reversible cyclic codes, and some extended binary Goppa codes. In particular, the second generalized Hamming weight of primitive double-error-correcting BCH codes is determined and upper and lower bounds are obtained for the generalized Hamming weights for the codes studied. These bounds are compared to results from other methods.>

A generalization of the Berlekamp-Massey algorithm is presented for synthesizing minimum length linear feedback shift registers for generating prescribed multiple sequences. A more general problem is first considered, that of finding the smallest initial set of linearly dependent columns in a matrix over an arbitrary field, which includes the multisequence problem as a special case. A simple iterative algorithm, the fundamental iterative algorithm (FIA), is presented for solving this problem. The generalized algorithm is then derived through a refinement of the FIA. Application of this generalized algorithm to decoding cyclic codes up to the Hartmann-Tzeng (HT) bound and Roos bound making use of multiple syndrome sequences is considered. Conditions for guaranteeing that the connection polynomial of the shortest linear feedback shift register obtained by the algorithm will be the error-locator polynomial are determined with respect to decoding up to the HT bound and special cases of the Roos bound.>

The decoding capabilities of algebraic algorithms, mainly the Berlekamp-Massey algorithm, the Euclidean algorithm, and the authors' (1989) generalizations of these algorithms, are basically constrained by the minimum distance bounds of the codes. The authors introduce a more general procedure which breaks away from this restriction and which can determine the, error locations from nonrecurrent dependence relations among the syndromes. It can decode many cyclic and BCH codes up to their actual minimum distance and is seen to be a generalization of the procedure introduced by W.W. Peterson and E.J. Weldon (1972).>

A new algorithm for performing fast inversion in GF (2/sup m/) is presented. The algorithm requires O(mlog/sub 2/ m) computation time. Using serial-in-parallel-out multiplication, the design of the algorithm is highly regular, modular, and well suited for VLSI implementation.>

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes.>