A workforce scheduling system to manage both static optimization and dynamic re-optimization for field service is proposed. The problem is formally defined as minimizing the total labor cost while satisfying various constraints. A heuristic algorithm for optimizing the initial scheduling and re-scheduling corresponding to unexpected task inputs is proposed. The proposed algorithm effectively determines the organization of work groups by integrating two work groups on the basis of an integration priority indicator. A prototype is implemented as the web system. The proposed algorithm is evaluated by applying it to the operation and maintenance service of IT equipment in a Japanese field service company. The proposed algorithm can reduce the total travel distance by 20.9% and the required total number of workers by 12.9% while observing time constraints compared with the conventional manual scheduling. The results show the proposed algorithm can manage unexpected tasks and establish an efficient work schedule.

An important problem in secret sharing schemes is minimizing the share size. For (k, n)-threshold schemes and (k, L, n)-ramp schemes, constructions that minimize the share size are known. This paper presents optimal constructions for a more general class of access structures in which subsets with the same cardinality have the same amount of information about the secret. We refer to schemes with such uniform access structures as uniform secret sharing. We first derive a tight lower bound for share entropy and then present an optimal construction. Our lower bound exceeds that previously reported. The optimal construction encodes the secret value using one or more ramp schemes.

Wireless sensor networks are often more vulnerable than wired ones. Especially, an adversary can attack the networks by utilizing false route information. A countermeasure against the attack is a secure routing protocol with digital signatures to guarantee the validity of route information. However, existing secure routing protocols are inefficient because the memory size and the computational overhead are heavy. To overcome these problems, we focus on ID-based sequential aggregate signatures (IBSAS) (Boldyreva et al., 2007). IBSAS allow users to aggregate individual signatures into a single signature. Moreover, certificates of public keys are unnecessary for IBSAS. Therefore, IBSAS can drastically decrease the memory size and the computational overhead. Besides, one of the main concerns for practical use is to construct a protocol specification with IBSAS. Moreover, since IBSAS are sometimes weak against compromising secret keys, another concern is to construct its countermeasure. For these purposes, we propose a secure dynamic source routing with ID-based sequential aggregate signatures, called ISDSR for short and discuss the key management to revoke/update compromised keys. We also show that the performance of ISDSR is the best in comparison with the existing protocols.

A new method using an error correcting code to reduce the probability of detection error for a digital watermark is proposed. The performance of the method is evaluated with a digital watermark for a 2D image as an example. In the method, only minimum weight codewords of the code are used as embedded information and two different decoding algorithms are used to reduce the probability of detection error. Analysis and simulation results on the error correcting capability for AWGN channel are shown to ensure the effectiveness of the concept of the method. In the digital watermark, a minimum weight codeword is embedded in the frequency domain of the green plane of the color space of 2D images with a discrete cosine transform as it has a high PSNR with resistance of JPEG compression. Results on an experiment with JPEG compression attack are also shown to ensure the effectiveness of the method.

A new adaptive recursive maximum likelihood decoding algorithm using ordered statistics is proposed. The average computational complexity of the algorithm is considerably small compared with the known algorithms. Preliminary simulation results for the (64,22,16) Reed-Muller code and the (64,24,16) extended BCH code are shown. The average number of additions and comparisons on soft-decision values becomes smaller than that for recursive MLD at SN ratios higher than or equal to Eb/N01[dB].

The error correction capability of binary linear codes with minimum distance decoding, in particular the number of correctable/uncorrectable errors, is investigated for general linear codes and the first-order Reed–Muller codes. For linear codes, a lower bound on the number of uncorrectable errors is derived. The bound for uncorrectable errors with a weight of half the minimum distance asymptotically coincides with the corresponding upper bound for Reed–Muller codes and random linear codes. For the first-order Reed–Muller codes, the number of correctable/uncorrectable errors with a weight of half the minimum distance plus one is determined. This result is equivalent to deriving the number of Boolean functions of$m$variables with nonlinearity$2^{m-2}+1$. Themonotone error structureand its related notionslarger halfandtrial set, which were introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the results.

In 2005, Osaka University, in Japan, started an international educational program called, Pacific Rim International University (PRIUS), on top of the Pacific Rim Application and Grid Middleware Assembly (PRAGMA) research framework. The PRIUS framework is based on and similar to that of the PRIME program at the University of California San Diego. Through the PRIUS program, Osaka University has explored a new structure of higher education for graduate students by combining lectures given by PRAGMA researchers and scientists as well as internship abroad opportunities to PRAGMA member institutions and universities. In this paper, we describe the goals and framework of the PRIUS program and discuss issues for the improvement of PRIUS. We also present two examples of interns' achievements as well as other educational effects brought through collaboration with PRAGMA.

A lower bound on the number of uncorrectable errors of weight half the minimum distance is derived for binary linear codes satisfying some condition. The condition is satisfied by some primitive BCH codes, extended primitive BCH codes, Reed-Muller codes, and random linear codes. The bound asymptotically coincides with the corresponding upper bound for Reed-Muller codes and random linear codes. By generalizing the idea of the lower bound, a lower bound on the number of uncorrectable errors for weights larger than half the minimum distance is also obtained, but the generalized lower bound is weak for large weights. The monotone error structure and its related notion larger half and trial set, which are introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the bounds.

There are two types of threshold ramp secret sharing (TRSS) schemes: Linear function ramp and nonlinear function ramp. A linear (resp. nonlinear) function TRSS scheme reveals information of the secret linearly (resp. nonlinearly). There are many studies on the linear ones and various secure and efficient constructions have been proposed. In contrast, the notion of the nonlinear function scheme was recently introduced, and any previous construction is either insecure or inefficient. This paper first points out defects of the previous insecure construction, and then presents the first secure and efficient construction. The proposed construction can achieves H(Vi) ≪ H(S) while in the previous secure construction H(Vi) = H(S) where H(Vi) and H(S) are the entropies of each share and the secret, respectively.

Some methods to determine the local weight distribution of binary linear codes are presented. Two approaches are studied: A computational approach and a theoretical approach. For the computational approach, an algorithm for computing the local weight distribution of codes using the automorphism group of the codes is devised. In this algorithm, a code is considered the set of cosets of a subcode, and the set of cosets is partitioned into equivalence classes. Thus, only the weight distributions of zero neighbors for each representative coset of equivalence classes are computed. For the theoretical approach, relations between the local weight distribution of a code, its extended code, and its even weight subcode are studied. As a result, the local weight distributions of some of the extended primitive Bose-Chaudhuri-Hocquenghen (BCH) codes, Reed-Muller codes, primitive BCH codes, punctured Reed-Muller codes, and even weight subcodes of primitive BCH codes and punctured Reed-Muller codes are determined

Relations between the local weight distributions of a binary linear code, its extended code, and its even weight subcode are presented. In particular, for a code of which the extended code is transitive invariant and contains only codewords with weight multiples of four, the local weight distribution can be obtained from that of the extended code. Using the relations, the local weight distributions of the (127, k) primitive BCH codes for k les 50, the (127, 64) punctured third-order Reed-Muller, and their even weight subcodes are obtained from the local weight distribution of the (128, k) extended primitive BCH codes for k les 50 and the (128, 64) third-order Reed-Muller code. We also show an approach to improve an algorithm for computing the local weight distribution proposed before

A new soft-input soft-output (SISO) decoding algorithm based on minimum distance search (MDS), called SISO-IMDS, is presented. The bit error rate of the proposed SISO decoding algorithm is almost the same as those of Max-Log-MAP and Log-MAP algorithms. Moreover, the average decoding complexity of the MDS based SISO decoding algorithm is much smaller than those of trellis-based SISO decoding algorithms. Consequently, the proposed SISO-IMDS can be applied in practical iterative decoding algorithms for a product code and a block turbo code.

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.

In this article, constructions of generalized concatenated (GC) codes with good rates and distances are presented. Some of the proposed GC codes have simpler trellis complexity than Euclidean geometry (EG), Reed-Muller (RM), or Bose-Chaudhuri-Hocquenghem (BCH) codes of approximately the same rates and minimum distances, and in addition can be decoded with trellis-based multistage decoding up to their minimum distances. Several codes of the same length, dimension, and minimum distance as the best linear codes known are constructed.

This paper presents an efficient trellis-based maximum-likelihood decoding algorithm for binary linear block codes. This algorithm is recursive in nature and is devised based on the structural properties and optimum sectionalization of a code trellis. The complexity of the proposed decoding algorithm is analyzed. Numerical results show that the proposed decoding algorithm significantly reduces the decoding complexity. A recursive method for finding the optimum sectionalization of a trellis in terms of computational complexity is given.

This paper presents a method for evaluating the bit-error probability of a concatenated coding system for BPSK transmission over the AWGN channel. In the concatenated system, a linear binary block code is used as the inner code and is decoded with the soft-decision maximum likelihood decoding, and a maximum distance separable code (or its interleaved code) is used as the outer code and is decoded with a bounded distance decoding. The method is illustrated through a specific example in which the inner code is a binary (64.40.8) Reed-Muller subcode and the outer code is the NASA standard (255, 223, 33) Reed-Solomon code over GF(2/sup 8/) interleaved to a depth of 5. This specific concatenated system is being considered for NASA's high-speed satellite communications. The bit-error performance is evaluated by a combination of simulation and analysis. The split weight enumerators for the maximum distance separable codes are derived and used for the analysis.

In previous work, a method was presented to compute the weight distribution of a linear block code by using its trellis diagram. In this correspondence, the method is improved by using the trellis structure of linear block codes. Another method with reduced computational complexity is also proposed which uses the invariant property of a code. With these methods, the weight distributions of all extended binary primitive BCH codes of length 128 are computed, except for those for which the formulas of the weight distribution are known. It turns out that (128,64,22) extended binary primitive BCH code is formally self-dual. The probability of an undetectable error for each code is computed and its monotonicity is examined.

A method for computing the weight distribution of the third-order Reed-Muller code of length 512 is presented. Linear block codes are also examined.

The aliasing error performance of a signature register is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measures, we evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large, say 32, it is computationally hard to obtain the exact aliasing probability. But we observe that the numbers of codewords with large weights in the corresponding code dominate the maximum value of the aliasing probabilities. By computing the numbers of codewords of large weights, we find primitive polynomials of degree 32 whose maximum value of the aliasing probabilities is very large for some test lengths. The error performance of an LFSR with any BCH polynomial of degree m for the test length 2/sup m/2/-2 is shown to be very good by deriving the formula for the weight distribution of the corresponding code.>

An upper bound on the effective error coefficient of a two-level code with two-stage decoding is presented. This bound provides a guideline for constructing two-level codes to achieve a good trade-off between the error performance and decoding complexity. Based on this bound, good two-level decompositions of some Reed-Muller codes for two-stage decoding are found. Simulation results on the error performances of some Reed-Muller codes of lengths up to 64 with two-stage soft-decision suboptimum decoding based on their two-level decompositions are given.>

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>

The aliasing error performance of signature registers is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measurements, the authors evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large (e.g. 32), it is computationally hard to obtain the exact value of the aliasing probability. But the authors observe that the numbers of codewords with large weights in the corresponding code determine the maximum value of the aliasing probabilities in the range 0>

It was shown earlier that for a punctured Reed-Muller (RM) code or a primitive BCH code, which contains a punctured RM code of the same minimum distance as a large subcode, the state complexity of the minimal trellis diagrams is much greater than that for an equivalent code obtained by a proper permutation of the bit positions. The problem of finding a permutation of the bit positions for a given code that minimizes the state complexity of its minimal trellis diagram is related to the generalized Hamming weight hierarchy of a code, and it is shown that, for RM codes, the standard binary order of bit positions is optimum at every bit position with respect to the state complexity of a minimal trellis diagram by using a theorem due to V.K. Wei (1991). The state complexity of the trellis diagram for the extended and permuted (64, 24) BCH code is discussed.>

An upper bound on the number of states of a minimal trellis diagram for a linear block code is derived. Using this derivation a cyclic (or shortened cyclic) code or its extended code is shown to be the worst in terms of trellis state complexity among the linear codes of the same length and dimension. The complexity of the minimal trellis diagrams for linear block codes of length 2/sup m/, including the Reed-Muller codes, is analyzed. The construction of minimal trellis diagrams for some extended and permuted primitive BCH codes is presented. It is shown that these codes have considerably simpler trellis structure than the original codes in cyclic form without bit-position permutation.>

A new defect-tolerant design technique for mask ROMs is proposed. In the proposed technique a Reed-Solomon code with distance three is utilized. A built-in circuit can repair a defect or defects within a word. The overhead area of the defect-tolerant circuits is estimated to be about 1% for a 4 M-bit mask ROM with eight outputs.>

The problem of distributing a Cartesian product file on multiple disks to maximize the parallelism for partial match queries is addressed. C. Faloutsos et al. (1989) have proposed an allocation method for Cartesian product files on multiple disks by using linear error-correcting codes. The performance of the allocation method is analyzed. Some conditions under which the allocation method is strictly optimal for queries with a given number of unspecified attributes are presented. A necessary and sufficient condition for a linear code to give a strictly optimal allocation method is discussed. Formulas for the average response time on queries with w unspecified attributes, denoted T/sub w/, in terms of the weight distribution of the code or its dual code, and formulas for the average response time Ton all queries, are given. Several examples whose average response times T/sub w/ or T are close to theoretical lower bounds are presented.>

The monotonic property of the probability of undetected error is considered when a shortened code of a linear code over GF(q) is used for error detection on a q-ary symmetric channel. Some conditions are presented under which the probability of undetected error is (or is not) monotonic with respect to the code length or the symbol error probability. It is shown that the probability of undetected error for a maximum distance separable code is monotonic with respect to the codelength. It is also shown that the probability of undetected error of a shortened code of any binary cyclic Hamming code generated by a trinomial is not monotonic with respect to the bit-error rate if the code length is short.>

Two important structural properties of block M(=2/sup '/)-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S/sub M-PSK/=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S/sub M-PSK/ with respect to modulo-M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2/sup h/180 degrees /M phase rotation, for 1>

The multilevel technique for combining block coding and modulation is investigated. A general formulation is presented for multilevel modulation codes in terms of component codes with appropriate distance measures. A specific method for constructing multilevel block modulation codes with interdependency among component codes is proposed. Given a multilevel block modulation code C with no interdependency among the binary component codes, the proposed method gives a multilevel block modulation code C' that has the same rate as C, a minimum squared Euclidean distance not less than that of C, a trellis diagram with the same number of states as that of C, and a smaller number of nearest neighbor codewords than that of C. Finally, a technique is presented for analyzing the error performance of block modulation codes for an additive white Gaussian noise (AWGN) channel based on soft-decision maximum likelihood decoding. Error probabilities of some specific codes are evaluated by simulation and upper bounds based on their Euclidean weight distributions.>

A concatenated coded modulation scheme is presented for error control in data communications. The scheme is achieved by concatenating a Reed-Solomon outer code and a bandwidth efficient block inner code for M-ary phase-shift keying (PSK) modulation. Error performance of the scheme is analyzed for an additive white Gaussian noise (AWGN) channel. It is shown that extremely high reliability can be attained by using a simple M-ary PSK modulation inner-code and a relatively powerful Reed-Solomon outer code. Furthermore, if an inner code of high effective rate is used, the bandwidth expansion required by the scheme due to coding will be greatly reduced. The scheme is particularly effective for high-speed satellite communications for large file transfer where high reliability is required. A simple method is also presented for constructing block codes for M-ary PSK modulation. Soome short M-ary PSK codes with good minimum squared Euclidean distance are constructed. These codes have trellis structure and hence can be decoded with a soft-decision Viterbi decoding algorithm. Furthermore, some of these codes are phase invariant under multiples of 45 degrees rotation.>

A robust error control coding system is presented. This system is a cascaded FEC (forward error control) scheme supported by parity retransmissions for further error correction in the erroneous data words. The error performance and throughput efficiency of the system are analyzed. Two specific examples of the error control system are studied. The first example does not use an inner code, and the outer code, which is not interleaved, is a shortened code of the NASA standard RS code over GF(2/sup 8/). The second example, as proposed for NASA uses the same shortened RS code as the base outer code C/sub 2/, except that it is interleaved to a depth of 2. It is shown that both examples provide high reliability and throughput efficiency even for high channel bit-error rates in the range of 10/sup -2/.>

Investigates the error detecting capabilities of the shortened hamming codes adopted for error detection in IEEE Standard 802.3. These codes are also used for error detection in the data link layer of the Ethernet, a local area network. The authors compute the weight distributions for various code lengths. From the results, they show the probability of undetectable error and that of detectable error for a binary symmetric channel with bit-error rate 10/sup -5/>

A coding scheme for error control in data communication systems is investigated. The scheme is obtained by cascading two error-correcting codes, called the inner and outer codes. Its error performance is analyzed for a binary symmetric channel with a bit-error rate epsilon>

In this paper, a concatenated coding scheme for error control in data communications is presented and analyzed. In this scheme, the inner code is used for both error correction and detection; however, the outer code is used only for error detection. A retransmission is requested if either the inner code decoder fails to make a successful decoding or the outer code decoder detects the presence of errors after the inner code decoding. Probability of undetected error (or decoding error) of the proposed scheme is derived. An efficient method for computing this probability is presented. Throughput efficiency of the proposed error control scheme incorporated with a selective-repeat ARQ retransmission strategy is also analyzed. Three specific examples are presented. One of the examples is proposed for error control in the NASA Telecommand System.

Recently Kasami {\em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1withm \geq 8and designed distance2t + 1with4 \leq t \leq 5is improved. From these results, the relative deviation of the number of codewords of weightj\leq 2^{m-1}from the binomial distribution2^{-mt} \left( \stackrel{2^{m}-1}{j} \right)is shown to be less than 1 percent for the following cases: (1)t = 4, j \geq 2t + 1andm \geq 16; (2)t = 4, j \geq 2t + 3and10 \leq m \leq 15; (3)t=4, j \geq 2t+5and8 \leq m \leq 9; (4)t=5,j \geq 2t+ 1andm \geq 20; (5)t=5, j \geq 2t+ 3and12 \leq m \leq 19; (6)t=5, j \geq 2t+ 5and10 \leq m \leq 11; (7)t=5, j \geq 2t + 7andm=9; (8)t= 5, j \geq 2t+ 9andm = 8.

Shortened Hamming codes are widely used for error detection in data communications. In this paper, a method for computing the probability of an undetected error for these codes is presented. This method is then used to evaluate the error-detection performance of the shortened codes obtained from the two distance-4 Hamming codes adopted by CCITT X.25 for error control for packet-switched networks. We show that shortening a code does affect its error-detection performance.

Binary primitive BCH codes form a large class of powerful error-correcting codes. The weight distributions of primitive BCH codes are unknown except for some special classes, such as the single, double, triple error-correcting codes and some very low-rate primitive BCH codes. However, asymptotic results for the weight distribution of a large subclass of primitive BCH codes have been derived by Sidel'nikov. These results provide some insight into the weight structure of primitive BCH codes. Sidel'nikov's approach is improved and applied to the weight distribution of any binary linear block code. Then Sidel'nikov's results on the weight distributions of binary primitive BCH codes are improved and it is shown that the weights of a binary primitive code have approximate binomial distribution.