In many cryptographic applications, a large-order finite field is used as a definition field, and accordingly, many researches on a fast implementation of such a large-order extension field are reported. This paper proposes a definition field Fpm with its characteristic p a pseudo Mersenne number, the modular polynomial f(x) an irreducible all-one polynomial (AOP), and using a suitable basis. In this paper, we refer to this extension field as an all-one polynomial field (AOPF) and to its basis as pseudo polynomial basis (PPB). Among basic arithmetic operations in AOPF, a multiplication between non-zero elements and an inversion of a non-zero element are especially time-consuming. As a fast realization of the former, we propose cyclic vector multiplication algorithm (CVMA), which can be used for possible extension degree m and exploit a symmetric structure of multiplicands in order to reduce the number of operations. Accordingly, CVMA attains a 50% reduction of the number of scalar multiplications as compared to the usually adopted vector multiplication procedure. For fast realization of inversion, we use the Itoh-Tsujii algorithm (ITA) accompanied with Frobenius mapping (FM). Since this paper adopts the PPB, FM can be performed without any calculations. In addition to this feature, ITA over AOPF can be composed with self reciprocal vectors, and by using CVMA this fact can also save computation cost for inversion.

Affine arithmetic is a kind of interval arithmetic defined by Stolfi et al. In affine arithmetic, it is difficult to realize the efficient nonlinear binomial operations. The purpose of this letter is to propose a new dividing method which is able to supply more suitable evaluation than the old dividing method. And this letter also shows the efficiency of the new dividing method by numerical examples.

This paper describes how four-wave mixing (FWM) noise within multifiber linear-lightwave WDM ring networks is reduced due to their thin wavelength density. Preliminary numerical analysis for a full-mesh connection pattern shows that a simple wavelength insertion technique can improve FWM noise performance as high as about 10 dB.

A nonlinear circuit described by the forced Duffing's equation is known to display a rich variety of dynamical behavior. Coupling two Duffing's circuits by a linear resistor, we conclude that combinatorial resonances occur on weak coupling condition. In a coupled system, although symmetrical properties are usually observed, breaking of symmetry can lead to much more complex nonlinear resonant phenomena. In this paper, we discuss asymmetry in four cases of perturbation on parameters. Many bifurcation diagrams are presented. Comparing with symmetrical cases, we analyze the combinatorial resonances in coupled Duffing's circuit completely.

This paper describes a method of analyzing musical sound using a self-organizing map. To take compound factors into account, energy spectra whose frequency ranges were based on the psycho-acoustic experiments were used as input data. Results for music compact discs confirmed that our method could effectively display the positioning and relationships among musical sounds on a map.

In this letter, we propose an efficient channel estimation scheme using trigonometric polynomial approximation for OFDM systems with transmit diversity. While the conventional channel estimation scheme has a high computational complexity in given channel delay profiles, the proposed scheme is efficient in the computational complexity. Especially, for channels with smaller rms delay spreads, the proposed scheme has improved BER performance and complexity reduction. In addition, we evaluate the performance of maximum delay spread estimation in unknown channel. The performance of the proposed scheme is evaluated by computer simulation in various multi-path fading environments.

This paper proposes the evaluation methods for measuring retrieval effectiveness of Web search engine systems, attempting to make them suitable for real Web environment. With this objective, we constructed 100-gigabyte and 10-gigabyte document sets that were mainly gathered from the '.jp' domain, and conducted an evaluation workshop at the third NTCIR Workshop from 2001 to 2002, where we assessed the retrieval effectiveness of a certain number of Web search engine systems using the common data set. Conventional evaluation workshops assessed the relevance of the retrieved documents, which were submitted by the workshop participants, by considering the contents of individual pages. On the other hand, we assessed the relevance of the retrieved pages by considering the relationship between the pages referenced by hyperlinks.

A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.

In this paper, a quasi-synchronous code-division multiple-access (QS-CDMA) is investigated for application in the reverse link of a microcellular or indoor mobile communication environment. In a QS-CDMA system, the relative time delay between the signals of different users is normally restricted within a few chips. Generalized orthogonal (GO) codes added with guard chips are employed as the spreading sequences in this paper and the strict timing error restrictions for BPSK and M-QAM modulation schemes are derived based on the correlation properties of GO code set which determines the multiple access interference (MAI). The results reveal that the system employing GO code set with bigger GO zone can tolerate more serious timing error, and higher order modulation schemes require stricter synchronization. Based on the system model presented, the BER performance for BPSK and M-QAM is evaluated by Gaussian Approximation (GA) and Monte Carlo simulation. The system capacity in terms of acquirable total bit rates are also evaluated, revealing that if system synchronization error is limited within the GO zone, M-QAM scheme can be utilized to improve the system capacity.

Optical Character Reader (OCR) incorrect recognition is a serious problem when searching for OCR-scanned documents in databases such as digital libraries. In order to reduce costs, this paper proposes fuzzy retrieval methods for English text containing errors in the recognized text without correcting the errors manually. The proposed methods generate multiple search terms for each input query term based on probabilistic automata which reflect both error-occurrence probabilities and character-connection probabilities. Experimental results of test-set retrieval indicate that one of the proposed methods improves the recall rate from 95.96% to 98.15% at the cost of a decrease in precision from 100.00% to 96.01% with 20 expanded search terms.

In this paper, we propose an answer seeking algorithm for question answering that integrates structural matching and paraphrasing, and report the results of our empirical evaluation conducted with the aim of examining effects of incorporating those two components. According to the results, the contribution of structural matching and paraphrasing was not so large as expected. Based on error analysis, we conclude that structural matching-based approaches to answer seeking require technologies for (a) coreference resolution, (b) processing of parse forests instead of parse trees, and (c) large-scale acquisition of paraphrase patterns.

Automatic text summarization has the goal of reducing the size of a document while preserving its content. Generally, producing a summary as extracts is achieved by including only sentences which are the most topic-related. DOCUSUM is our summarization system based on a new topic keyword identification method. The process of DOCUSUM is as follows. First, DOCUSUM converts the content words of a document into elements of a context vector space. It then constructs lexical clusters from the context vector space and identifies core clusters. Next, it selects topic keywords from the core clusters. Finally, it generates a summary of the document using the topic keywords. In the experiments on various compression ratios (the compression of 30%, the compression of 10%, and the extraction of the fixed number of sentences: 4 or 8 sentences), DOCUSUM showed better performance than other methods.

Retrieval effectiveness depends on both the retrieval model and how terms are extracted and indexed. For Chinese, Japanese and Korea text, there are no spaces to delimit words. Indexing using hybrid terms (i.e. words and bigrams) was found to be effective and efficient using the 2-Poisson model in NTCIR-III open evaluation workshop. Here, we explore another Okapi weight, BM25, based on the 2-Poisson model and compared their performances with bigram and word indexing strategies. Results show that word indexing is the most efficient in terms of indexing time and storage but hybrid term indexing requires the least amount of retrieval time per query. Without pseudo-relevance feedback (PRF), our BM25 appeared to yield better retrieval effectiveness performance for short queries. With PRF, our implementation of the BM11 weights, which are a simplified version of BM25, with hybrid term indexing remains the most effective combination for retrieval in this study.

In light of the increasing number of computer applications that rely heavily on multimedia data, the database community has focused on the management and retrieval of multidimensional data. Nearest Neighbor queries (NN queries) have been widely used to perform content-based retrieval (e.g., similarity search) in multimedia applications. Incremental NN (INN) query is a kind of NN queries and can also be used when the number of the NN objects to be retrieved is not known in advance. This paper points out the weaknesses of the existing INN search algorithms and proposes a new one, called Batch-Incremental Nearest Neighbor search algorithm (denoted B-INN search algorithm), which can be used to process the INN query efficiently. The B-INN search algorithm is different from the existing INN search algorithms in that it does not employ the priority queue that is used in the existing INN search algorithms and is very CPU and memory intensive for large databases in high-dimensional spaces. And it incrementally reports b(b > 1) objects simultaneously (Batch-Incremental), whereas the existing INN search algorithms report the neighbors one by one. In order to implement the B-INN search, a new search (called k-d-NN search) with a new pruning strategy is proposed. Performance tests indicate that the B-INN search algorithm clearly outperforms the existing INN search algorithms in high-dimensional spaces.

Document retrieval is a fundamental but important task for intelligent access to a huge amount of information stored in documents. Although the history of its research is long, it is still a hard task especially in the case that lengthy documents are retrieved with very short queries (a few keywords). For the retrieval of long documents, methods called passage-based document retrieval have proven to be effective. In this paper, we experimentally show that a passage-based method based on window passages is also effective for dealing with short queries on condition that documents are not too short. We employ a method called "density distributions" as a method based on window passages, and compare it with three conventional methods: the simple vector space model, pseudo relevance feedback and latent semantic indexing. We also compare it with a passage-based method based on discourse passages.

This paper proposes a statistical method of acquiring knowledge about the abbreviation possibility of some of multiple adnominal phrases. Our method calculates weight values of multiple adnominal phrases by mutual information based on the strength of relation between the adnominal phrases and modified nouns. Among adnominal phrases, those having relatively low weight values are deleted. The evaluation of our method by experiments shows that precision attains about 84.1% and recall attains about 59.2%, respectively.

The segregation of non-magnetic phases such as borosilicate and Cr was investigated by crystallization behavior during the surface and bulk crystallization of Co-based amorphous alloys. The concentration of metalloids (B and Si) determined the extent of grain boundary segregation of borosilicate glass during surface crystallization. During the bulk crystallization of (Co75Cr25)0.8Si5B15 amorphous alloy, solute rejection of Cr resulted in the nucleation of Cr-deficient ferromagnetic crystals and non-magnetic σ-phase was subsequently precipitated along the grain boundary. These results show that crystallization process, i.e. nucleation and growth can be controlled to optimize the microstructure to reduce media noises in Co-based recording media.