Palindromic representation is generally used to reduce space and time complexities in Gaussian normal basis (GNB) multiplier with even type t. However, palindromic representation is inapplicable for a GNB multiplier with odd type t ($t \geq 2$). This study therefore develops a palindromic-like representation for a GNB multiplier with odd type t. The proposed systolic GNB multiplier with odd type t reduces space and time complexities by as much as 50% compared with conventional GNB multiplier with odd type t without palindromic representation.

Fault-tolerant design of a finite field multiplier is an efficient method for resisting fault-based cryptanalysis in Elliptic curve cryptosystems. A novel fault-tolerant bit-parallel Gaussian normal basis (GNB) multiplier with type-t over GF(2m), which can tolerate multiple module failures at one time, is presented. No hardware modification in the proposed GNB multiplier is required to achieve the fault-tolerant function. Hence, the proposed fault-tolerant GNB multiplier has low hardware cost. The reliability of the proposed fault-tolerant GNB multiplier with type-t increases as t increases. However, the behaviour of existing GNB multipliers with concurrent error correction (CEC) resembles triple modular redundancy (TRM) when t>3. In practice, most of suggested m's by NIST use GNB with type-t>3. The proposed fault-tolerant GNB multiplier is an N-modular redundancy (NMR) system with N=t. Thus, the proposed fault-tolerant GNB multiplier with type-t can tolerate at most t/2-1 failed modules simultaneously, while existing GNB multipliers with CEC only can tolerate one failed module. The proposed GNB multiplier requires less extra space and time complexities than similar multipliers. System reliability of the proposed fault-tolerant GNB multiplier is better than that of similar GNB multipliers.

This work develops a novel self-checking alternating logic (SCAL) bit-parallel Gaussian normal basis (GNB) multiplier with type-t over GF(2m). The proposed GNB multiplier is with both concurrent error-detection and off-line testing capabilities. The concurrent error-detection capability can give countermeasure to fault-based cryptanalysis. The off-line testing capability supports the design-for-test property. The proposed SCAL GNB multiplier can detect both permanent and transient faults. The proposed SCAL GNB is the first normal basis multiplier to have both on-line error-detection and off-line testing capabilities.

Many optimal uniprocessor schedulers, such as earliest deadline first (EDF) and rate monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm earliest deadline first until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+\umax-1/2\ for two-processor systems, where umaxis the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

This paper presents a systematic model, two-phase optimization algorithms (TPOA), for Mastermind. TPOA is not only able to efficiently obtain approximate results but also effectively discover results that are getting closer to the optima. This systematic approach could be regarded as a general improver for heuristics. That is, given a constructive heuristic, TPOA has a higher chance to obtain results better than those obtained by the heuristic. Moreover, it sometimes can achieve optimal results that are difficult to find by the given heuristic. Experimental results show that (i) TPOA with parameter setting (k, d) = (1, 1) is able to obtain the optimal result for the game in the worst case, where k is the branching factor and d is the exploration depth of the search space. (ii) Using a simple heuristic, TPOA achieves the optimal result for the game in the expected case with (k, d) = (180, 2). This is the first approximate approach to achieve the optimal result in the expected case.

This paper presents new and systematic methodologies for analyzing deductive games and obtaining optimal algorithms for 2 × n Mastermind games, where n ≥ 2. We have developed a graphic model to represent the game-guessing process. With this novel approach, we find some symmetric and recursive structures in the process. This not only reduces the size of the search space but also helps us to derive the optimum strategies more efficiently. By using this technique, we develop optimal strategies for 2 × n Mastermind games in the expected and worst cases and are able to derive the following new results: ⌊n/2⌋ + 2 guesses are necessary and sufficient for 2 × n Mastermind games in the worst case. The minimum number of guesses required for 2 × n Mastermind games in the expected case is (8n3 + 51n2 − 74n + 48)/24n2 if n is even and (8n3 + 51n2 − 80n + 69)/24n2 if n is odd. The optimization of this problem bears a resemblance to other computational problems such as circuit testing, differential cryptanalysis, on-line models with equivalent queries and additive search problems. Any conclusion of this kind of deductive game may be applied, although probably not directly, to any of these problems as well as to any other combinatorial optimization problem.

this paper, a constant-time algorithm is proposed on this model for finding the cycles in an undirected graph. We can use this algorithm to decide whether a specified edge belongs to the minimum spanning tree of the graph or not. This cycle-finding algorithm is designed on a two-dimensional nn processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Based on this cycle-finding algorithm, the minimum spanning tree problem and the spanning tree problem can be solved in O(1) time by using fewer processors than before, O(n n)andO(n ) processors respectively. This is a substantial improvement over previous known results. Moreover, we also propose two constanttime algorithms for solving the minimum spanning tree verification problem and spanning tree verification problem by using O(n ) processors, respectively

This paper presents detection algorithms for baseline interconnection networks in the presence of multiple faults. We develop a procedure for finding the constraints of test vectors. This reduces the number of distinct test vectors and solves the problems efficiently. Furthermore, we design a new and systematic procedure for generating admissible permutations and reduction rules to find constraints easier. By using this novel approach, we are able to derive the following new results. (1) Four distinct test vectors are necessary and sufficient for detecting multiple faults in an 8*8 baseline network. (2) Six distinct test vectors are sufficient for detecting multiple faults in a 16 * 16 baseline network. (3) Six tests are necessary and sufficient for detecting multiple faults in a 16 * 16 baseline network. This improves the previous result of [1], which needs 8 tests to accomplish the same task. (4) We show that (2log2N) − 2 tests are sufficient for detecting multiple faults in an N * N baseline network for N ≥ 16. This also improves the result of [1], which needs 2 log2N tests.

The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.

In this paper, we present an O(1) time algorithm to solve the minimum coloring problem defined on a set of intervals, which is also called the channel assignment problem. This problem has not been solved in O(1) time before, even on the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware-solutions. Our algorithm is based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first transform the "left-edge" channel assignment algorithm to the parenthesis-matching problem. Based on this novel scheme, we are able to explore constant-time parallel algorithms to solve the minimum coloring problem for n intervals, which is also called the channel assignment problem, on a PARBS with O(n/sup 2/) processors.>