bluuebunny/crossref_metadata_2025_split huggingface dataset:
A design of real‐time systolic convolvers
Authors: Umeo Hiroshi 
Published: July 2007

AbstractThis paper discusses the systolic algorithm where the input and output are serial and the processing is performed in parallel (called serial‐I/0, parallel‐processing scheme). This paper considers the following three kinds of parallel algorithms which have been known as the algorithms for different problems: the palindrome recognizer, multiplication of binary sequences, and the pattern‐matching algorithm. Based on these algorithms, a new systolic convolver is proposed which computes the convolution of two infinite sequences in real time. As an application of the systolic convolver, a systolic pattern‐matching algorithm is proposed which is the fastest and the optimum among the presently known algorithms considering the constant coefficients. By the data‐routing proposed in this paper, a clear design principle is formulated for the real‐time systolic convolver, which greatly simplifies the proof for the validity and provides an easy understanding of the real‐time systolic convolution algorithm.
Longitudinal ECT imaging using Y‐ray camera
Authors: Iwata Satoshi , Nakajima Masato , Yuta Shinichi , Ogawa Koichi 
Published: July 2007

AbstractSingle‐photon emission CT is one of the most useful techniques in nuclear medicine, wherein a radioisotope material is injected into the body and by external detection of the radiated y‐ray the RI distribution on an arbitrary layer (slice) is reconstructed from the data, permitting visual representation of physiological information. Longitudinal imaging is one of such techniques. The object is regarded as composed of layered RI distributions. From the y‐ray projection data obtained by y‐ray detectors placed parallel to the layer, the RI distribution at each slice is reconstructed. In longitudinal imaging, however, the projection data are observed only along a particular direction and the working range of the detector is restricted, leading to blur and degradation of the reconstructed image. This paper discusses the quality degradation inherent in longitudinal imaging and proposes a reconstruction algorithm which employs the contour information of the object in the reconstruction computation to make correction for the quality. The result of numerical simulation is also reported.
Distance transformation and reconstructable skeleton of three‐dimensional digital binary images
Authors: Sun Wei‐Dong , Tayama Norio , Otawara Isao 
Published: July 2007

AbstractThis paper considers the filled three‐dimensional image, such as the one obtained by superposing several CT images, and discusses the distance transformation and the skeleton for the three‐dimensional filled object. From the viewpoint that the internal structure of the three‐dimensional object should easily be understood, there has been devised a distance transformation, where the distances from all points inside of the three‐dimensional object to the surface are determined. There has not been presented, however, a method which is applicable to the general situation. From such a viewpoint, this paper introduces a new notion of fundamental neighbor set, and proposes a general parallel and serial algorithms for the distance transformation. As an example, the notion of the reconstruetable skeleton for the three‐dimensional object is proposed, and the parallel and serial algorithms are presented, which can reconstruct accurately the original three‐dimensional object from the skeleton. The reconstructable skeleton will be useful as a means of information compression for the three‐dimensional image, which requires especially a large amount of data for the representation. The validity of the proposed algorithms is verified by computer simulation.
Software testing system supported by a computer architecture
Authors: Baba Takanobu , Suzuki Shinzi , Yamazaki Katsuhiro , Okuda Kenzo , Sano Toshiyuki 
Published: July 2007

AbstractBased on the development of hardware, various computer architectures have been proposed to support software. However, most of them have not been implemented and evaluated. We have realized a software testing system on a machine developed at our laboratory. Utilizing its architectural features, we proved the effect experimentally. The supporting functions include the following: display of memory contents according to the data type, step‐run in the units of statement and procedure, specification of type and range of variables, checking of assign/refer relationship, and measurement of execution frequencies. The user can specify these functions explicitly by interactively using various commands. A tagged architecture and data descriptor have been utilized to implement the functions efficiently. Experimental results show that 86 percent of program errors were detected by the supporting functions, and the overhead was less than 2 percent of the total execution time.
Hardware algorithms for computing exponentials and logarithms using redundant binary representation
Authors: Takagi Naofumi , Yajima Shuzo 
Published: July 2007

AbstractIn this paper, we propose hardware algorithms for computing exponentials and logarithms utilizing the redundant binary representation for internal computation. The algorithms proposed in this paper are improved versions of modified STL methods which were improved by Specker and by Chen and are known as methods suited for the dedicated circuits for computing exponentials and logarithms. The algorithms by Specker and by Chen compute exponentials and logarithms by repeating a simple procedure composed of an additional subtraction, a shift and a table look‐up. In the proposed algorithms, by using the redundant binary representation, each digit at which is an element of {0, 1, ‐1} for the internal computation, we eliminate carry (borrow) propagation from addition (subtraction) and improve the speed of computation. Using the traditional methods, because of carry (borrow) propagation addition (subtraction), combinational circuits for computing n‐bit exponentials and logarithms require at least a computation time proportional to n log n and the number of elements proportional to n2. Using the proposed algorithms, the computation time is improved to be proportional to n, and the number of elements is proportional to n2 using traditional methods.
A tree‐structured parallel processing system for image generation by ray tracing
Authors: Deguchi Hiroshi , Shirakawa Isao , Omura Koichi , Nishida Masato , Nishimura Hitoshi , Kawata Toru 
Published: July 2007

AbstractAn image generation system by ray tracing was implemented on a distributed parallel processing system composed of loosely coupled multimicrocomputers. An improvement was made by extending the architecture from the star structure to the hierarchical tree structure. This improvement makes it possible for an animated image to be generated at high speed with shading which can represent the shape and texture of three‐dimensional objects with high quality. This paper outlines the hierarchical tree‐structured image generation system, discussing the parallel processing mechanisms of the system, such as data transfer and hierarchical load distribution schemes. Experiments were made to evaluate the performance. Problems in the tree‐structured system are pointed out, and remedies are proposed (area redistribution, and area subdivision). Experiments are made to evaluate the effectiveness of these methods. Thus, it is demonstrated that the tree‐structured system is useful in the image generation using ray tracing.
A fast image filtering processor using the fermat number transform
Authors: Yamane Nobumoto , Morikawa Yoshitaka , Hamada Hiroshi 
Published: July 2007

AbstractThis paper discusses a newly developed high‐speed image filtering processor, aiming at high‐accuracy and high‐speed isotropic filtering. The isotropic filtering is made efficient by the following features.(1) The image is sampled over the triangular lattice and processed by the hexagonal finite‐impulse response (FIR) filter. (2) The filter is realized by the Fermat number transform (FNT) with hexagonal sectioning procedure.The high‐speed hardware has the following features: (1) FNT‐butterfly circuit using 3‐input adders; and (2) multiple processing by the memory structure with three‐level hierarchies. By those features, the proposed system executes the filtering in approximately 0.5 s for an image composed of 512 × 512 pixels in triangular lattice (512 × 591 pixels in square lattice) by a hexagonal FIR filter with edge distance of 15 (17 × 17 in square lattice‐square FIR filter). This paper describes the features, architecture and operation of the proposed system. Then the result of correcting the isotropic blur is presented, indicating that a practically sufficient accuracy is obtained.
A module structure real‐time operating system for microcomputers
Authors: Tsuda Junji , Tsutsui Shigeyoshi , Maeda Takao , Yokohata Shizuo , Ishikawa Tomo 
Published: July 2007

AbstractWith the advent of large‐scale and complicated microcomputer application systems, the role of OS is becoming more important. An OS which can cope with various application requirements is strongly desired. This paper aims at the construction of OS which can be made optimum for various real‐time applications. A construction of real‐time modular structure OS using the microcomputer 68000 is proposed. The message‐passing and procedure‐call schemes are combined to connect the modules. A two‐layered hierarchy module structure is proposed, suppressing the increase of the overhead due to modular implementation, and also providing the flexibility for replacing modules. By this scheme, operating systems with capacity from 10 KB to 150 KB can be constructed, covering a wide range of applications from a small‐scale system with hardware built‐in structure to the relatively large‐scale system requiring programming functions, by simply modifying the combination of modules. To utilize commercial softwares or general‐purpose OS in the real‐time environment, a scheme is proposed in which the general‐purpose OS is executed as the secondary OS with the real‐time kernel. As a result of evaluation, when a general‐purpose OS, CP/M‐68K, is executed as the secondary OS, the processing time is increased by 12.7% compared with CP/M‐68K directly implemented on the 68000.
Description and verification of input constraints and input‐output specifications of logic circuits
Authors: Kimura Shinji , Yajima Shuzo 
Published: July 2007

AbstractThe input constraints and the input‐output specifications of the logic circuit are assertions to be satisfied in the operation of the logic circuit. Most of the timing constraints such as the set‐up time of the clocked flip‐flop can be regarded as the input constraint or the input‐output specification. In this paper, the time is considered as discrete with sufficiently small steps, and the input and output of the logic circuit are treated as sequences. The method to describe the set of sequences satisfying the input constraints or the input‐output specifications and the method to verify these assertions are proposed anew; # expression and the first # form are proposed as the description methods. The # expression is obtained by adding the newly proposed # concatenation and # closure to the regular expression. The first # form is a restricted # expression, where the number of states of the deterministic finite automaton accepting the set of sequences represented by the expression does not exceed twice the length of the description. In this paper, the logic circuit is regarded as a converter for the set of sequences and the verification of the input constraint or the input‐output specification is reduced to the examination of the inclusive relation among the sets of sequences. Consequently, when the set of sequences satisfying the input constraint or the input‐output specification is described in the first # form, the verification can be performed efficiently. The proposed method is applied to several actual problems, and is shown to be useful.
A character recognition system with learning dictionary for handwritten drawings
Authors: Ishii Mitsuo , Iwasaki Michiko , Yamada Masahiro 
Published: July 2007

AbstractThis paper discusses the character recognition system used in the automatic input of drawings. The character considered is of small size, 2 to 5 mm, which is sampled with a low resolution such as 5 lines/mm. The recognition is performed by a kind of pattern matching. The input pattern is superposed on the dictionary pattern. The distance distortion measure is introduced which represents the degree of mismatch with the closest pixels as the corresponding pair. To reflect the structural feature of the character, the weighted distortion measure is proposed which considers the environment of the corresponding pixels. By this elaboration, the misrecognition rate was decreased by 45 percent. To cope with the problem arising from representing the two‐dimensional pattern distortion by a single number, dictionary patterns are increased. The generation and the structure of the dictionary are discussed. A hierarchical dictionary with learning pointer is constructed which records the mistakes made in the course of training. The feature of the method is that mistakes made in the past can be utilized and the processing time does not increase so rapidly in proportion to the number of dictionary patterns. Approximately 30,000 characters were learned, and the practical recognition performance was verified through the recognition experiment for the drawings.
A concurrent pattern operation algorithm for VLSI mask data
Authors: Tsukizoe Akira , Kozawa Tokinori , Sakemi Jun'Ya , Miura Chihei , Ishii Tatsuki 
Published: July 2007

AbstractWith the advance of scale and integrity of LSIs, several kinds of CAD systems are being developed and introduced to design verification and mask pattern generation for mask pattern data as a means of shortening the design time. The processings common to these CAD systems are pattern logical operations. This paper proposes effective and fast pattern operation algorithms for large‐scale data containing patterns of any angle: the virtual slit method and limited searching algorithm. The virtual slit method is a logical operation algorithm performing concurrently the three processings, intersection‐point calculation, slit division, and logical processing which have been done independently in old algorithms. The limited searching algorithm is a highspeed intersection‐point calculation algorithm indispensable for diagonal figures. The time complexity of both methods is theoretically O(Nv) log Nv) where Nv is the number of input vectors. For manufactured LSI mask data, we obtained the result for the time complexity based on estimation by program execution which can be approximated by O(Nv).
Matching of distorted central symmetry image—An application to seal impression collation
Authors: Takeda Haruo , Tabata Kuniaki , Hananoi Toshihiro 
Published: July 2007

AbstractThis paper considers the pattern matching of images in which, originally, the boundary has central symmetry which is made incomplete by defects and noises. A detection method for the centroid of symmetry is proposed. In the proposed method, the boundary is rotated by 180° to match itself (self‐matching of the boundary), thereby detecting the centroid by utilizing all position information of the pixels on the boundary. When the defects are assumed, methods such as tracing cannot be applied directly to the extraction of the boundary, and a simple scheme is employed which scans the image in parallel to the coordinate axis. The effect of the spurious information produced by the scanning is eliminated by using the histogram as the measure of the boundary matching. The effect of the missing information is eliminated by superposing the histogram, which is obtained by scanning in the direction perpendicular to the original scanning, to the original histogram. The proposed method is applied to collation of seal impressions. It was verified that the positioning is performed within the error of one pixel for the ordinary defect of the impression frame and the partial defect of the frame due to the noise by background and fibrous padding material. It was also verified that a processing with practically sufficient speed can be realized. The proposed method will also be applied effectively to the positioning of the images with partial central symmetry, such as a circular component with a protrusion.
A method of document‐image segmentation based on projection profiles, stroke densities and circumscribed rectangles
Authors: Akiyama Teruo , Masuda Isao 
Published: July 2007

AbstractA method is proposed wherein printed documents are segmented into the following three areas: headline area, textline area, and attached area. Then the character lines constituting headline and textline are extracted. This paper describes: 1) the combination of the global features of the document such as projection profiles and stroke densities, and the local features of the document such as circumscribed rectangles are used; 2) the basic features of document elements such as character line periodicity in the textline area, so that a single method can be applied to segment document elements in differently formatted documents.An experimental result of this method applied to eight Japanese and English printed documents of both horizontal and vertical lines showed that 98.4 percent of the headlines in headline area, 99.9 percent of the textlines in textline area, and 83.3 percent of diagrams in the attached area were segmented successfully.The result confirms that this method is effective in segmenting document elements, and applicable to a variety of documents. Part of document processing is implemented in the experiment by special hardware for speed.
Properties of personal identification systems using question‐answer technique
Authors: Masuyama Hiroshi 
Published: July 2007

AbstractThis paper considers various personal identification systems based on questions and answers concerning knowledge inherent to the individual, and discusses the personal identification probability. Assume a personal identification system which contains N knowledge items and assume that a solver has forgotten the correct answers for M items after the registration. The behavior of the system is as follows: Q knowledge items for questions are selected randomly from N items. For each of the selected items, R selection keys are presented which include a correct answer and the solver is requested to select one. When the solver forgets the correct answer, the probability of correct answer is 1/R; otherwise it is 1. The following three systems are considered under such conditions. System I decides the solver as correct if all answers to the extracted Q items are correct. System II decides the solver as correct if there are fewer than K incorrect answers. System III decides the solver as correct unless k or more consecutive answers are incorrect. It is seen that the probability of personal identification increases in the order of I, II and III. It is not always true that the probability of excluding an incorrect solver is low if the probability of personal identification is high. Each of the considered systems is suited to particular applications, depending on the environment.
Performance of a simulated dataflow computer DFNDR‐2
Authors: Sowa Masahiro , Kamimura Akitoshi 
Published: July 2007

AbstractAn architecture is proposed for the dataflow computer and an experimental system is constructed. However, since the emphasis has been on the realization of the computer, it has been difficult to estimate the general performance of the dataflow computer from the performance of the experimental system. This paper describes the result of simulation to estimate the general performance.
Principles of algebraic language ASL
Authors: Kasami Tadao , Taniguchi Kenichi , Sugiyama Yuji , Seki Hiroyuki 
Published: July 2007

AbstractThis paper discusses the problems and basic principles in the design of the algebraic language ASL/. A text of ASL/ is composed of a context‐free grammar and a set of (conditional, in general) axioms, and specifies the set of expressions and the congruence relation on the set. The set of expressions and the syntax of each expression are specified by the context‐free grammar. The congruence relation on the set of expressions is defined as the minimal equivalence relation, which satisfies the axioms and is closed under the “operations,” i. e., the substitution into a “subexpression.” The value of an expression and the concept of the realization are defined based on the congruence relation. The “projection” is a special case of the conditional axiom, which is a facility to include only the expressions satisfying the specified syntactical condition. Projection is useful for including primitive functions and procedures with parameter passing of call‐by‐value in a text, and also for description of a specification of a realization in a simple way.
Arithmetic burst error correcting fire‐type cyclic ST‐AN codes
Authors: Shimada Ryosaku , Murakami Ryutaro , Sono Kazuharu , Ohkura Yoshiteru 
Published: July 2007

AbstractThe cyclic ST‐AN code is a cyclic AN code based on a ternary number system using numerals ‐1, 0, 1 (called symmetrical ternary number system). It is suited to the arithmetic operations handling positive and negative numbers in a symmetrical way as well as to the error‐correction. We have already presented some reports on the basic concept of the code and the error‐correcting ability for the random error. This paper proposes the cyclic ST‐AN code which can correct the burst error. The code is generated by the code generator A = (3c ‐ 1) A2, and is an extension of the algebraic Fire code. Because of this property, it has the features that the construction is very simple and the selection of the code is easy. A satisfactory result is also obtained for the code efficiency. This paper describes first the outline of the cyclic ST‐AN code and the concepts of arithmetic burst. Then it discusses the construction of the cyclic ST‐AN Fire‐type code and its error‐correcting ability. Finally, the decoding method is presented which uses the error‐trapping.
A random‐pattern testable design for programmable logic arrays
Authors: Fujiwara Hideo 
Published: July 2007

AbstractAlthough the built‐in self‐test approaches by pseudo‐random patterns using LFSR are common, it is difficult to expect high fault coverage for high fan‐in circuits such as PLA. Thus, for the built‐in test of circuits like PLA we need to generate regular test patterns or to devise some counterplan even in the use of random patterns. This paper proposes a method for constructing random‐pattern‐testable PLAs for which we can achieve high fault coverage even by random patterns by adding mask arrays to conventional PLAs. To see how high fault coverage is achieved, fault detection probability by random patterns is analyzed for equivalent AND‐OR circuits of the form‐like trees for both stuck‐ and cross‐point type faults. Also a method for finding a mask that maximizes the probability of fault detection in the composition of random‐testable PLAs is studied.