bluuebunny/crossref_metadata_2025 huggingface dataset:
A bayesian reliability analysis model by a single debugger for discrete‐type software and its application
Authors: Sandoh Hiroaki , Fujii Susumu , Yamawaki Tatsuya
Published: July 2007

A reliability analysis model is proposed for software products at their development stage from the Bayesian viewpoint, with emphasis on such software products as the usual mathematical software used discretely in time. In the proposed model, a single debugger is engaged in conducting software tests and in debugging a software product, where the significations of “single debugger” are as follows: the model does not consider the case where several software engineers conduct software tests and debugging for the same software product independently of each other to collate their respective detected bugs after the tests. On the basis of the proposed model, an optimum release problem for software products is also formulated. The proposed methods are demonstrated by presenting numerical examples to clarify their characteristics.
Design of two‐dimensional IIR digital filters with complex coefficients using spectral transformations
Authors: Sekiguchi Takashi , Takahashi Shin‐Ichi
Published: July 2007

This paper describes a new method for designing two‐dimensional (2‐D) digital filters with complex coefficients having circularly symmetric and fan characteristics by applying variable transformation (spectral variable) to one‐dimensional (1‐D) IIR digital filters with complex coefficients. A 2‐D digital filter with complex coefficients has an advantage in that it can increase greatly the degree of freedom for design, since once it satisfies the design specification partly in the frequency plane, its characteristics can be arbitrary in other regions.

Here, a design method is proposed which makes positive use of this property of the complex coefficient digital filters. Since we have introduced the complex coefficient filters into spectral transformation functions and 1‐D prototype filters, there is no constraint on cutoff frequency (radius) accomplishable in circularly symmetric filters. In fan filters even a characteristic that has been difficult to design unless one uses optimization techniques, has become easy to design by means of variable transformation without using any optimization techniques. Moreover, the stability of the resulting IIR filters is guaranteed in simple conditions.
Reorganization of node connection in chordal‐ring networks with variation of the number of nodes
Authors: Masuyama Hiroshi , Miki Tadayuki
Published: July 2007

In a network operated under a certain system management to make the topological structure invariant for insertion of a newly arising node, accompanied by the increase of the number of users or extension of the system scale, some modifications of the node connection must be required. In a fourth‐degree chordal‐ring network which is known to have a disadvantage with respect to diameter minimization although management software is easy, the forementioned system modification is expected to be required relatively less frequently. This paper presents a new measure for system modification for a chordalring network by formulating modifications of node connection required for the change of the number of nodes.
A realization scheme for the identity‐based cryptosystem
Authors: Tanaka Hatsukazu
Published: July 2007

At Crypto ′84, A. Shamir [1] presented the new concept of identity‐based cryptosystems. Yet no realization scheme has yet been proposed. This paper proposes a scheme for realizing an identity‐based cryptosystem which modifies Shamir's original concept without losing its essential characteristics. The fundamental idea of this realization scheme is based on the well‐known one‐way functions, “the difficulty of calculating a discrete logarithm” and “the difficulty of factoring the composite of two large primes.” As long as all the users in the system keep their own secret keys secure, this cryptosystem is perfectly secure. Even if there is a conspiracy among users in the system, this system remains secure when the number of conspirators is less than a certain number which has been determined during the design phase. In this way, a threshold scheme for a secret information sharing system is realized. This paper presents a detailed analysis of this threshold scheme and shows how to evaluate the secret key of the center when the number of conspiring users is over the threshold. In addition, a scheme which facilitates a reduction in the amount of computation needed to generate a common key is also presented.
Preservation of liveness in hierarchical petri nets
Authors: Kumagai Sadatoshi , Kodama Shinzo , Tsuji Kohkichi , Nakamura Youichi
Published: July 2007

For large‐scale systems for discrete events such as FA, OA and sequence control systems, it is desirable to establish a systematic design methodology. It is expected that a systematic design methodology for systems can be obtained using a Petri net model (a powerful model for discrete event systems) for system specification, analysis and verification. Generally, in the top‐down design of a large‐scale system, we begin with a rough design for the system and apply successive refinements. In the Petri net model, a hierarchical representation is considered such that in a refinement step, one of the elements in the net is replaced by a subnet which represents its behavior in more detail. This paper considers some questions regarding this hierarchical representation of Petri nets, such as whether properties such as liveness and safeness of nets are preserved by the refinement. In particular, we consider simultaneous refinement of parallel transitions to derive several sufficient conditions concerning preservation of properties of the net, and represent these as conditions on subnets which are to replace blocks in the parent net.
A synthesis of low‐sensitivity digital filters using T‐cascade connections. Extraction of wave digital lattice filter sections
Authors: Watanabe Eiji , Minagawa Kenji , Nishihara Akinori
Published: July 2007

Digital filter response is degraded from that desired when the filter is implemented using finite wordlength multipliers. To avoid such degradation, low‐sensitivity filter structures such as wave digital filters (WDF's) often are used. On the other hand, the pipeline processing would be preferable for the high‐speed applications of filters. In general, the pipeline approach is not applicable to WDF's.

This paper proposes new low‐sensitivity filter structures which are also suited for the pipeline processing. The fundamental idea to obtain low‐sensitivity structures is to synthesize digital 2‐port circuits with “structurally induced losslessness,” as done by Vaidyanathan and Mitra. The losslessness of a digital 2‐port circuit is characterized by a para‐unitary scattering matrix. WDF's also have this losslessness when they are modeled after reactance filters.

The proposed structures are synthesized by factoring such scattering matrices, and constructed using T‐cascade connection of new basic sections, in contrast with the II‐cas‐cade connection used in WDF's and Vaidyana‐than‐Mitra structures. Each section, which is also characterized by a paraunitary scattering matrix, is realized as a lattice WDF. The proposed structures can realize any given transfer function, and if the function has a certain symmetry, they reduce to lattice WDF's.
A general method of deriving a discrete normalized system of orthogonal functions and its application to adaptive digital filters
Authors: Kobayashi Shoji , Takahara Mikio , Kubota Hajime
Published: July 2007

The system of orthogonal functions is very useful in science and engineering, and the theory on the orthogonal function system in the continuous time domain has been established. On the other hand, with the advance in digital signal processing, a need for processing the signal in the discrete time domain is acute. With this background, a general derivation of the orthogonal function system in the discrete time domain is desired. This paper proposes a general method for deriving the orthogonal function system in the discrete time domain from the already established orthogonal function system in the continuous time domain. First, the orthogonal function system in the continuous time domain is presented. Next, by the bilinear information of its transfer function, the system is transferred to the discrete time domain. However, in general, the orthogonality in the discrete time domain is destroyed by the bilinear transformation. It is shown that the orthogonality can be maintained in the discrete time domain and the orthonormal function system can be constructed by an appropriate processing. Further, the digital filter using this orthonormal function system is applied to the adaptive digital filter and the number of adaptive parameters is reduced. Finally, by computer simulation, the effectiveness of the adaptive filter configuration by means of the orthonormal function system is proven.
Generalized Minkowski metrics for mixed features
Authors: Ichino Manabu , Yaguchi Hiroyuki
Published: July 2007

This paper presents simple and convenient generalized Minkowski metrics on multidimensional feature space in which each coordinate axis is associated not only with a quantitative feature, but also a qualitative feature. The metrics are defined on a new mathematical model (U(d), +, × constructed by the authors called simply the Cartesian space model. In this model, U(d) is the feature space, + is the Cartesian join operator which abstracts a generalized description from two given descriptions on U(d), and × is the Cartesian meet which extracts a common description from two given descriptions on U(d). In our approach, intervals and finite sets are also permitted as possible feature values. Two simple numerical examples are presented to illustrate the usefulness of our metrics.
Orthonormal discriminant vectors of pattern recognition
Authors: Hamamoto Yoshihiko , Kanaoka Taiho , Tomita Shingo
Published: July 2007

Recently, concerning statistical feature extraction, Okada and Tomita presented an orthonormal discriminant vector method based on the Fisher criterion. The advantage of their method has been discussed experimentally. However, it has not been discussed theoretically in comparison with a well‐known discriminant analysis. For a two‐class problem, it is shown that the method is more powerful than discriminant analysis from the viewpoint of the discriminatory ability between classes. Numerical examples are presented to illustrate the results obtained in this paper.
Image reconstruction from erroneous projections—radon transform as an analog coding
Authors: Kumazawa Itsuo , Ogawa Hidemitsu , Tajima Hiroshi
Published: July 2007

In the image reconstruction problem, projections obtained by scanning X‐rays from many directions around an object are shown to have redundant information for reconstructing a section image of the object. This redundancy means that some relationship or dependency exists among the projections. This paper formalizes the dependency using some linear equations and regards these equations as parity check equations of the analog coding theory. In addition, after an appropriate transformation of the variables, it is shown these equations become equivalent to the parity check equations of the DFT codes, which are well understood and are the most established analog codes. It is shown experimentally that errors or impulsive noises included in about 10 percent of the projections can be detected and corrected automatically by applying the error correcting schema developed from the DFT codes. Also proposed is an error correcting algorithm for the DFT codes, which gives stable results even in the high‐dimensional case similar to those in the practical applications of Computerized Tomography (CT).
Multichannel linear prediction models and their convergence property
Authors: Cheng Fulin , Koga Tosiro
Published: July 2007

This paper considers theoretically the relation between the convergence problem of various algorithms and statistical properties of a signal appearing during construction of a linear prediction system of signals when the time series of the signal is a multiple Gaussian process. Specifically, we consider first the convergence problem of the covariance matrix of a predicted error arising as a linear prediction algorithm applied to the solution of a Yule‐Walker equation.

Next, in comparison with the convergence speed of the correlation coefficient matrix of a multiple signal time series, we obtain an evaluation formula for the convergence speed of a covariance matrix of a linear prediction error. Furthermore, we discuss the convergence of an algorithm for constructing an orthonormalized polynomial matrix which corresponds to a transfer function matrix of a whitening filter from a solution of the Yule‐Walker equation. We present a concrete evaluation formula for the convergence speed of the algorithm.
Overlap resolution problem for block placement in VLSI layout
Authors: Ohmura Michiroh , Miyao Jun'Ichi , Yoshida Noriyoshi , Kikuno Tohru
Published: July 2007

In VLSI layout design by the building block approach, a hierarchical floorplanning method is proposed in which the floorplan and global routing are determined simultaneously to realize low‐congestion switchboxes. In this method, overlap resolution, which preserves relative position and minimizes the obtained chip area, is needed to prevent the increase in the wire length of each net.

In this paper, a fundamental study of this overlap resolution is made, and the following are described.

(1) The formulation of the overlap resolution problem RI is given. In the formulation, (a) preservation of relative position among blocks, and (b) the minimization of obtained chip area are considered; (2) the computational complexity of the problem is analyzed, and then NP‐completeness of the problem RI is proved; and (3) a polynomial heuristic algorithm R for the problem RI is given. In addition, the result of simulation experiments to verify the efficiency of the heuristic algorithm R is also described.
Scheduling methods for a low‐bit‐rate speech coding algorithm (ATC‐VQ) on a multicomputer‐type DSP system
Authors: Sawabe Tomoko , Suzuki Junji , Ohta Naohisa , Ono Sadayasu
Published: July 2007

For parallel implementation of a digital signal processing algorithm, the solution of scheduling problems that consist of task partitioning and task allocation are important. This paper considers an ATC‐VQ (Adaptive Transform Coding using Vector Quantization) algorithm because it is a typically used complex algorithm, and describes the basic study of the scheduling techniques used for implementation of this algorithm on a multicomputer‐type DSP system.

With the ATC‐VQ algorithm the scheduling methods for the LPC residual signal coding has a large effect on the overall performance, because this coding occupies more than 85 percent of the processing time. The LPC residual signals are divided first into multiple vectors and then vector quantized. Three scheduling methods are shown whose partition units quantize the LPC residual signal vectors, and the performance of each method is evaluated. Appropriate scheduling methods suitable to the ATC‐VQ algorithm are discussed.
A bayesian reliability analysis model by two debuggers for discrete‐type software and its applications
Authors: Sandoh Hiroaki , Fujii Susumu , Yamawaki Tatsuya
Published: July 2007

This paper considers the software which is used discretely with regard to time, such as the usual software for numerical computation, and proposes a model for the reliability analysis in the development stage. Also, the case of the software test is considered in which two debuggers attempt to detect the bugs in the software. A discussion is made from the viewpoint of Bayes' theory. The case of two debuggers is as follows. Two software engineers execute the test independently for the same software. The detected bugs are compared later, including their overlaps, to acquire a larger amount of information. Based on the model for analysis proposed in this paper, a formulation is presented for the determination of the release of the software, i.e., the time to terminate the test. Numerical examples are presented, providing discussions on the features of the model considered in this study as well as on its usefulness.
Optimization of system reliability using bicriteria 0‐1 linear programming with GUB constraints
Authors: Ida Kenichi , Sasaki Masato , Gen Mitsuo
Published: July 2007

Generally, problems in the optimization of system reliability such as unit selection and allocation have been formulated as single‐objective nonlinear integer problems and solved by various optimization techniques. The method for solving such problems was based on an implicit enumeration method, which transformed them into 0‐1 linear programming problems. These methods have not considered the GUB constraint, which arises when transforming to 0‐1 linear programming problem, but recently, an efficient method which considers this GUB structure and introduces the AHP (Analytic Hierarchy Process) into the system constraints has been proposed. However, in such system optimization problems, there are many problems that cannot be solved by formulating them as single‐objective programming which optimizes only a single reliability or cost function. Instead, they must be solved by applying MODM methods, which handle multiple objectives that conflict with each other.

In this paper, we propose an efficient algorithm that makes use of the 0‐1 LP (GUB) package, written to solve single‐objective 0‐1 linear‐programming problems, in order to solve large scale 0‐1 linear programming problems that have two conflicting objectives and GUB constraints. To illustrate the effectiveness of the method proposed here, we present two numerical examples, optimal unit selection and optimal redundancy, and compare the results with those of previous methods.
Model reference adaptive control of nonminimum‐phase discrete‐time systems using approximate inverse systems
Authors: Yahagi Takashi , Yokomori Masao
Published: July 2007

The model reference adaptive control is well known in the deterministic system, as a method of adaptive control for the linear discrete‐time system. In the model reference adaptive control, the plant is controlled to follow the output of the given reference model while estimating the unknown parameters of the plant. One of the important problems in this system is the control of the nonminimum‐phase system. Often even if the plant as the continuous‐time system is minimum‐phase, the representation of the plant as the discrete‐time system is nonminimum‐phase.

From such a viewpoint, the control of the nonminimum‐phase system is very important from the practical standpoint. This paper proposes a new method of model reference adaptive control which can effectively control the nonminimum‐phase discrete‐time system using the approximate inverse system by division method. In this method, the approximate inverse system with any accuracy can be constructed by appropriately defining the threshold. The method is very useful in practice since the approximate inverse system of the nonminimum‐phase system can be determined only by iterating simple divisions.

To examine in detail the result of application of the proposed method, various computer simulations were made and the results are discussed.
A theory of estimating the whole from the partial information on the probability distribution of amplitude fluctuation and its application to noise environment
Authors: Ohta Mitsuo , Xiao Yegui , Ikuta Akira
Published: July 2007

Actual environmental noise and vibration exhibit arbitrary probability distribution forms due to the diversified causes of the fluctuation. Furthermore, the objective signal usually is contaminated by background noise or vibration, and often is effected by the dynamical range of the measuring meter. Therefore, it happens that the reliable observation data are only the partial information confined to a finite amplitude interval.

This paper proposes a practical test to estimate the whole probability distribution (connected with the evaluation quantities: Leq and Lx) of the objective signal by using only the partial stochastic information with the influence of the background noise or vibration and of the forementioned dynamical range.

More explicitly, the probability distribution of the objective signal is given first in a generalized series expansion form of probability expression. Next, we estimate the expansion coefficients in this expression by using four methods from different viewpoints. Finally, the effectiveness of the proposed theory is confirmed by applying it to the observed data of actual road traffic noise.
Analysis of frequency characteristics for flexural‐mode tuning‐fork type quartz crystal resonator, taking into account thickness, rotary inertia and shear force
Authors: Kawashima Hirofumi , Sunaga Kenji
Published: July 2007

A study was conducted with a view to finding theoretically and experimentally the relationship between the resonant frequency and its temperature dependence of the thickness of the resonator. As the analytical means, the energy method was used for deriving the equation of motion in which the thickness and rotary inertia and shear force were taken into account.

Since a tuning‐fork type flexural‐mode quartz crystal resonator is considered to have two cantilevers, the equation of motion was solved under the boundary condition of a clamped‐free end. The frequency equation was derived as a function of the thicknesszO' widthxOand lenghtyO.

Next, from this equation, the following relationships are derived: the frequency constant (f·yO) versus the dimensional ratioRxy=xO/yO, the resonant frequency versus the dimensional ratioRzy=zO/yO, the turnover temperature pointTpversus the dimensional ratioRxyand the relationship between the first‐ and second‐order frequency temperature coefficients andTpversus the dimensional ratioRzy. It is shown that the apex temperatureTpchanges significantly for the thickness. Further, these results were compared with the experimental data and good agreement between them is shown. Hence, it is concluded that the present analysis results are useful for the design of new frequency resonators.
Unified analysis of the waves in fluids and solids in time domain by spatial network method
Authors: Sato Masahiro , Yoshida Norinobu , Fukai Ichiro
Published: July 2007

When a fluid and a solid are in contact, complex and characteristic wave propagation phenomena emerge and their engineering applications are being planned in various areas. This paper presents a method which systematically treats the wave propagation in a fluid and a solid by means of the spatial network method which is a numerical time domain analysis of the wave. In the spatial network method (SNM), the wave field is expressed in terms of an equivalent circuit with one‐dimensional transmission lines. Bergeron's method and the circuit theory are applied to the equivalent circuit so that the time domain response is obtained. Here, the flow and viscosity are neglected in the fluid and lossless isotropic solids are treated. Since the waves in a fluid are scalar and those in a solid are vector, their equivalent circuits are different. Their coupling section becomes important. In order that the waves in a solid and a fluid can be treated systematically, a new equivalent circuit for the waves in a fluid is proposed in which particle velocity nodes are added. (SNM) is applied to basic problems so that its characteristics and validity are determined.
A placement method for size‐restricted blocks in VLSI layout design
Authors: Izumoto Hiroshi , Wakabayashi Shin'Ichi , Miyao Jun'Ichi , Yoshida Noriyoshi
Published: July 2007

In VLSI layout design, the placement problem of functional blocks with different sizes and shapes include two NP‐hard problems, that is, the problem of minimizing the chip size and the problem of minimizing the total virtual wire length. Therefore, in general, it is considered that any efficient placement method is very hard to develop.

As a fundamental consideration of the placement problem, this paper discusses a placement problem in which the size of each block to be placed is restricted. First, the placement problem MSL in which the size of each block is restricted to be either 2 × 2, 2 × 1, or 1 × 1 is formulated. Next, a heuristic algorithm for the problem MSL is presented and some theoretical consideration on the proposed algorithm is given.

In the theoretical consideration, the following two results are shown: 1) that the algorithm can find an initial placement with minimum chip area within a linear time on the number of blocks; and 2) that a set of placement change operations used to improve the total virtual wire length is a sufficient set of operations in a sense that any placement can always be transformed into another arbitrary placement by using the set of operations.

Finally, the results of simulation experiment which was performed to evaluate empirically the proposed algorithm are described.
A design of automatically tunable active MOSFET‐RC filters using a single‐ended circuit structure
Authors: Inoue Takahiro , Ueno Fumio , Sonobe Satoru , Kawasaki Mikio
Published: July 2007

Recently, as a new continuous‐time filter, an automatic tuning MOSFET‐C filter was proposed by Banu and Tsividis. It consists of MOSFETs, capacitors and operational amplifiers. It was shown that a highly accurate filter can be realized. In this configuration, only the voltage‐variable MOSFET resistor is used as the resistor and its non‐linearity is eliminated by a circuit configuration such as a fully balanced type.

This paper proposes an active MOSFET‐RC filter in which elimination of the nonlinearity of the MOSFET resistor does not require matching between MOSFETs. The filter consists of MOSFETs, capacitors, linear resistors with identical values and operational amplifiers, and can be made of a single‐ended circuit.

An automatic tuning of the filter characteristics is possible via a control of the resistance value of the MOSFET resistor with a PLL made of a voltage‐controlled all‐pass filter. Based on this configuration, a third‐order elliptic low‐pass filter was constructed with discrete components. With a power supply voltage of ±5 V, the filter characteristics were a total harmonic distortion of less than 0.1 percent, a dynamic range of more than 110 dB, and a passband gain variation of less than ±0.1 dB in the temperature range of −20°C to 80°C for a filter input voltage of less than 5.3 Vp−p.
A design method for coherent optical fiber filters of direct form
Authors: Lee Chae‐Wook , Sakaniwa Kohichi
Published: July 2007

Recently, optical signal processing has attracted considerable attention for highspeed and broadband signal processing such as channel separation filtering for optical FDM signals.

This paper considers coherent optical fiber filters which use coherent light sources and consist of directional couplers and optical fiber delay elements. These optical fiber filters are permitted to have both positive and negative value for filter coefficients, but still differ from the usual digital filters, since in the optical fiber filters, (1) the coupling coefficient a of a directional coupler is restricted to the value between 0 and 1, (2) optical signal E (complex amplitude) is divided into j√a E and √1‐aE at the directional coupler, and (3) for input signal E1 and E2, the output of a directional coupler is given by √1‐aE1 + j√a E2.

Considering these restrictions, we clarify the realizability condition and establish the optimal design method for optical fiber filters of direct form which make best use of optical signal energy.
An estimation method of the pairing and ordering for IIR digital filters with low roundoff noise
Authors: Oguro Yoshinari , Yoshikawa Toshinori
Published: July 2007

This paper considers the IIR cascade digital filter based on the fixed‐point arithmetic, and presents a method for estimation of the optimal pairing and ordering to minimize the output roundoff noise. In the proposed method, the computational complexity required in the estimation is reduced by considering only the pole frequencies of the transfer function in the evaluation. In the scaling of each branch node, the general L2 ‐ and L∞‐norms are assumed.

The proposed method is compared with the methods of Jackson, Lee and Liu‐Peled which are used frequently in practice. The four methods are applied actually to two kinds of filters, and the computational complexities are compared. It is shown as a result that the proposed method requires almost the same computational complexity as those of Jackson and Lee from the lower‐order to higher‐order filters, and realizes the pairing and ordering with smaller output roundoff noise. It is shown also in general that the pairing has a larger effect on the normalized output roundoff noise than the ordering.
Improvement of linearity in switched resistors
Authors: Fukai Sumio , Ishikawa Hirobumi
Published: July 2007

Switched resistor circuits have been proposed as a realization of equivalent resistors suitable for monolithic integrations. Since the linear resistance region of an MOSFET has been used, the dynamic range of the signal handled has been small. This paper presents methods for improving the linearity of the MOSFET suitable for a switched resistor circuit. With a view to configurations with fewer circuit elements, a method is considered for feedback from the drain to the gate and a method in which the nonlinearity is cancelled with two matched MOSFETs. It is confirmed experimentally that a practical dynamic range can be obtained and a high resistance can easily be realized with these methods for improvement.
Mixed D‐A circuit simulation by one‐way subcircuit time‐first analysis approach
Authors: Kage Tetsuro , Shimogori Shintaro
Published: July 2007

This paper considers the mixed digital‐analog (D‐A) circuit which contains both logic gates and analog elements such as bipolar transistors. A mixed D‐A circuit simulator was developed which directly simulates the mixed D‐A circuit. The simulator combines closely the logic simulation and circuit analysis, and provides an accurate and efficient simulation of the mixed D‐A circuit. The management of the simulation time is different for the logic simulation and the circuit analysis. By simply combining those two techniques, it is difficult to provide an efficient simulation for the general mixed D‐A circuit containing a feedback loop.

From such a viewpoint, a simulation method was developed in which the mixed D‐A circuit is decomposed into blocks along the direction of the signal propagation, and each block is simulated by time‐first processing. The block containing a mixed D‐A loop is decomposed hierarchically into blocks until the analog subcircuit is separated. By the proposed method of simulation, an efficient simulation is provided for the general mixed D‐A circuit containing a feedback loop by grouping the processing for the analog subcircuit. However, this is time‐consuming.
RSA security
Authors: Kurosawa Kaoru , Matsu Kazuo , Kasai Hirohumi
Published: July 2007

RSA is a typical public key cryptosystem, but whether or not breaking RSA is as hard as prime factorization is unknown. It is known that if the LSB sequence obtained from iterated cipher texts of RSA is distinguished from the true random sequence in a polynomial time, it is possible to break RSA. Consequently, by testing the quality of this pseudorandom sequence, the security of RSA can be evaluated. It is known also for RSA that guessing the least‐significant bit of the original message from the encrypted message with probability 1/2 + 1/poly(n) is equivalent to finding the whole original message.

In this paper, it is shown first that guessing the value of the original message by mod L with probability 1/L + 1/poly(n) is as difficult as finding the entire original message. Based on the result, a multivalued pseudorandom number generator is given. Those based on the hardness of the quadratic residue property also are shown. Statistical testing of those pseudorandom numbers is attempted, leading to the evaluation of the reliability of RSA.
A global router for standard cell VLSI with feed‐through assignment optimization
Authors: Sugai Yasuo , Hirata Hironori
Published: July 2007

A global routing for a standard cell VLSI poses two important problems: how often we use it with feed‐through and where to install it beside the layout to trunk lines. To minimize the total number of tracks at the level of detailed routings, we avoid local congestions. Thus the layout touting with feed‐through becomes necessary which does not depend on the routing order. For an optimization problem for a large number of combinations of routings, Kirkpatrick et al. have proposed a simulated annealing method. This method is a stochastic sequential improvement method. Its features are an ability to escape from local solutions and the obtained solution depends on the initial conditions and routing order. In this paper we proposed a new method for a global routing for a three‐layer standard cell VLSI with feed‐through based on the simulated annealing method. Features of our method are an enhanced degree of freedom of routings, allowance for changes of directions of feed‐through and an effective acoidance of local congestions. Through experiments on a computer we achieved a drastic reduction of the number of tracks compared with that of the existing method.
Culation algorithms of primary functions on a digital signal processor
Authors: Ebina Tsuyoshi , Ishii Rokuya
Published: July 2007

Recently, many kinds of digital signal processing systems are proposed. In realizing these systems on a digital signal processor (abbreviated as DSP), in most cases primary functions must be computed. When we compute primary functions on DSP, we make tables and use them for these function values for requirements. By using this method, we cannot obtain precise values and thus require a large memory region for tables. If we use DSP for complicated computations, application fields are limited.

This paper presented calculation methods of a division, sin(X), cos(X), tan(X), an arctangent, a square root, a logarithm and an exponential function. Further, execution speeds and execution precision were obtained. We used the digital signal processor MSM6992 made by OKI Electronic Industry Co. On the DSP, the execution program step number is 24 to 77.

The calculation error is less value than 2 to 4 times the value which corresponds to the least significant bit in a DSP with floating point arithmetic. Calculation of primary functions by the proposed methods does not require a large memory region (except for the calculation of a square root of an exponent). Then using proposed methods, we can implement a complex system using primary functions on a one‐chip DSP.
A study on biquad SCF with one operational amplifier
Authors: Komazaki Tomokazu , Gunji Katsuhiko
Published: July 2007

Progress in decreasing the power consumption of communications equipment has created a need for corresponding decreases in the power consumption of switched capacitor filters (SCF). Ishikawa and Laker haver suggested reducing the number of opamps used by means of time sharing. In the present paper a general form of a biquad SCF with a single opamp for time‐sharing use is proposed and a new biquad SCF design is derived. The possibility of designing such SCF's with a small DC offset is demonstrated. Tests with individual components confirm the effectiveness of such devices.
A design of matching network for lumped complex load using hyperbolic‐class nonuniform transmission line
Authors: Endo Isao , Akiyama Michio , Nemoto Yoshiaki , Sato Risaburo
Published: July 2007

This paper presents a new method of matching network design for lumped complex loads using nonuniform transmission lines. An equivalent circuit of a squared trigonometric or squared hyperbolic nonuniform transmission line consists of a cascade connection of a lumped reactive element, a pseudo‐uniform transmission line, an ideal transformer, and a lumped reactive element. The lumped reactive elements in the equivalent circuit may possess positive or negative element values.

Based on the notion of cancellation of the negative element of the equivalent circuit and the positive element of the load impedance, it is possible to design a broadband matching network for a lumped complex load.

This paper discusses mainly the impedance matching for an RC series load. Numerical examples are given and an experimental result demonstrates the validity of the theory.
Saving viterbi decoder states for general rate 1/2, constraint length K, quick look‐in codes
Authors: Tajima Masato , Kobayashi Kenzo , Suzuki Hideo
Published: July 2007

This paper discusses how to reduce the number of states in the main decoder placed in an SST Viterbi decoder for general rate 1/2, constraint length K, and quick look‐in codes. Presented are three different cell configurations for which state elimination is possible if an MAP estimation method is applied for branch metric computation. It is shown that for each of these cell configurations, a considerable portion of decoder states can be eliminated without any accompanying performance degradation. It is clarified also that, by transforming encoder states to syndrome former states (i.e., dual states), these cell configurations can be mapped to those discussed in Schalkwijk's paper.
Linear structure and error performance analysis of block PSK modulation codes
Authors: Takata Toyoo , Fujiwara Toru , Kasami Tadao , Ujita Satoshi , Lin Shu
Published: July 2007

This paper investigates the linear structure and error performance analysis of block PSK modulation codes. The integer group (0, 1, 2, 2l – 1) under the modulo‐2l addition, denoted as Sl, is chosen to represent a 2‐dimensional 2l‐PSK signal set. A necessary and sufficient condition is derived for a block PSK code over Sl to be closed under the component‐wise modulo‐2l addition. Error performance of block PSK codes also are analyzed for an AWGN channel with soft‐decision maximum likelihood decoding. Upper bounds and simulation results on the error probabilities for some specific codes are shown.
A new method for discrete optimization problems
Authors: Nakagawa Yuji
Published: July 2007

A generalized optimization system with a discrete decision space, is described, and on an optimization problem is defined which is associated with the system. A new solution method, which is called modular approach (MA), is presented to solve the optimization problem. This method extends the Morin‐Marsten hybrid idea to solve troublesome problems of dynamic programming. The present method is also an extension of the branch‐and‐bound method using breadth‐first search.
Multiobjective fuzzy linear regression analysis and its application
Authors: Sakawa Masatoshi , Yano Hitoshi
Published: July 2007

This paper tests three formulations of linear programming problems used to derive a fuzzy linear regression model, which are based on three different indices representing the necessity and of sufficiency equivalence relations between fuzzy numbers. It is shown that those formulations are extensions of three traditional formulations for fuzzy data. The trade‐off between “fit” (between the model and the observed data) and the “fuzziness” (of the model) is considered to be a multiobjective decisionmaking problem. This leads to the formulation of a multiobjective programming problem for deriving the fuzzy linear regression model. Corresponding to this situation, an interactive decision‐making procedure is proposed, which is applied to the problem of estimating the pork demand.
Complex chebyshev approximation for IIR digital filters with arbitrary log magnitude and phase functions
Authors: Kobayashi Takao , Imai Satoshi
Published: July 2007

This paper proposes a technique for designing IIR digital filters to have prescribed magnitude and phase responses. The technique is based on an iterative weighted least‐squares approach in the frequency domain.

A weight updating procedure is introduced to minimize the complex logarithmic error in the Chebyshev sense. The real and imaginary parts of the complex logarithmic error represents the log magnitude and phase errors, respectively. Both the log magnitude and phase errors of the resulting filter become nearly equiripple. Filter coefficients at each iteration are computed efficiently using FFT and a fast recursive algorithm for a set of linear equations derived from the weighted least‐squares problem. Several design examples are shown to demonstrate the effectiveness of the proposed technique.
Identification of fuzzy parameters by interval regression models
Authors: Ishibuchi Hisao , Tanaka Hideo
Published: July 2007

Tanaka et al. formulated the problem of determining the linear regression expression with fuzzy parameters as a fuzzy regression analysis problem, using the data for the input‐output relation. This paper discusses such a fuzzy regression analysis, and proposes a method which identifies the fuzzy parameters using the interval regression expression.

First, a method is proposed which identifies the fuzzy parameters with symmetrical triangular form from the interval regression expression. Then a method is proposed which identifies the fuzzy parameters with asymmetrical trapezoid form from two interval regression expressions. Using numerical examples, a method is illustrated which identifies the asymmetrical trapezoid fuzzy parameters from the usual point data and the fuzzy data.

The method proposed herein employs the interval regression expression based on the interval operations, which leads to the merit that the procedure is simple and easy to understand compared with the conventional method employing the operations of fuzzy numbers. The fuzzy regression expression with asymmetrical trapezoid fuzzy parameters is a generalization of the fuzzy regression expression with symmetrical fuzzy parameters obtained by the conventional method.
New IIR‐adaptive algorithms based on orthogonalization method
Authors: Fukumi Minoru , Omatu Sigeru
Published: July 2007

Recently, for signal processing such as echo cancellation and equalization it is required to develop IIR‐adaptive digital filters. This paper proposes a new‐type IIR‐adaptive algorithm based on the orthogonalization method, considers the convergence of the algorithm, and verifies its effectiveness by simulation. White's algorithm is one of IIR‐adaptive algorithms reported thus far and Feintuch's algorithm is known as its approximation algorithm. This paper also derives an IIR‐adaptive algorithm using both Feintuch's algorithm and the orthogonalization method.

First, it can be shown that a generalized algorithm (IIR‐LI) of IIR‐learning identification method based on previous heuristic methods can be derived using the idea of Feintuch's algorithm and the conjugate gradient method. Next, a new IIR‐adaptive algorithm (IIR‐AACG) based on the orthogonalization principle of the conjugate gradient method is presented. Further, by applying the orthogonalization method to a past input vector sequence we derive an IIR‐Affine projection algorithm (IIR‐AP). Finally, these algorithms are compared by computer simulation to verify the effectiveness of the orthogonalization method.
Theory of extended interpolation approximation and upper and lower bounds of error
Authors: Kida Takuro , Yoshioka Leopoldo Hideki
Published: July 2007

Assume that signal f(t) is impressed on N parallel time‐invariant linear networks Hm(w)(m=1∼N), and consider the uniformly sampled values gm(nT)(m = 1∼N; n = 0, ±1, ±2,; T <0) of the output signal gm(t)(m=l∼N). This paper discusses the following problem from a unified viewpoint. The response g(t), when the signal f(t) is passed through the given filter H(w), is to be approximated by an expression y(t) which is the sum of the forementioned sample values multiplied by time functions ψmn(l)(m = 1∼N; n= 0, ±1, ±2, ). It is assumed that the signal f(t) belongs to the set l of the signals for which the weighted square integral of the Fourier spectrum F(w) is not greater than a positive number A. In the foregoing, ψmn(t) is called the interpolation function.

First, it is shown that given Hm(w)(m =1∼N), the time‐limited interpolation function, which minimizes the upper limit emax(t) of the error e(t) = [g{t)‐y(l)] over all f(t) belonging to F, is obtained by shifting the impulse responses ψ(l)(m=1∼N) of certain N linear time‐invariant interpolation filters ψ()w(m=1∼N) along the time axis. The analytic form for this function is given. Assuming that Hm(w) (m=1∼N and ψm(w)(m=1∼N) are optimized so that the measure emax(t) of the error is minimized, the upper and the lower bounds of the optimal emax(t) are shown. Considering an application where N is large, the optimization is discussed in the sense that the equivalent multiplicity is reduced at the sacrifice of the approximation error.
Ring code – code symmetry and uncorrectable errors
Authors: Noda Tadayoshi , Hata Masayasu
Published: July 2007

This paper proposes a ring code as a new burst error‐correcting code, where the check sequence forms a ring on a square code array. The code is a quasi‐cyclic quasi‐optimal code with a symmetrical structure. Because of its cyclic decoding process, it has a feature that the error‐correcting code for a long burst can easily be constructed.

This paper discusses also the properties of the code, as well as the correspondence between the code symmetry and the uncorrectable property. The relation is described clearly from the viewpoints of geometrical structure and the group theory. The computation for the uncorrectable probability is established. Finally, the two‐dimensional ring code is considered, but the theory can be extended to the three‐dimensional and the higher‐dimensional ring code. Due to the symmetry of higher order, the hidden errors are reduced and the error‐correcting power is improved. The exact evaluation of the performance of the code, however, is left to another paper.
A method of designing FIR fan filters based on McClellan transformations
Authors: Tazawa Shiro , Honma Hitoshi , Sagawa Masahiko
Published: July 2007

This paper describes a method of designing the fan filter with a steep cutoff characteristic, using McClellan transformation. The conventional design by McClellan transformation has a problem in that the cutoff region of the fan filter is broad due to the restriction to a lower order of the subfilter employed.

From such a viewpoint, this paper proposes a systematic design method for the subfilter with arbitrary order. First, it is pointed out that the ideal response of the subfilter can be represented in a functional form. Then the error function is defined in regard to the ideal response, and the design is shown for the subfilter where the filter coefficients minimize the error function. Finally, a design example is discussed, and it is shown that a fan filter with a steeper cutoff characteristic than in the conventional method can be designed by the proposed method.
A further result on the construction of asymptotically good convolutional codes for low rates
Authors: Nishijima Toshihisa , Ishii Hiroaki , Inazumi Hiroshige , Hirasawa Shigeichi
Published: July 2007

Justesen presented the asymptotically good block codes, and then the asymptotically good convolutional codes Rj in a constructive way. The latter are the concatenated codes, where the outer code is the convolutional code generated by the generator polynomial of Reed‐Solomon code, and the inner code is Wozencraft's randomly shifted code. The performance of Justesen's convolutional code is not necessarily high for low code rates. Sugiyama, Kasahara, Hirasawa and Namekawa presented new asymptotically good convolutional codes Rc by applying the second order concatenation to Justesen's convolutional codes Rj, which gave an improvement for the low code rates.

This paper presents constructively new asymptotically good convolutional codes R(J), by comgining the second‐order concatenation of the forementioned improved convolutional codes Rc and the generalized concatenated codes. It is shown that the new codes R(J) always have a higher performance than that of the convolutional codes Rc, and have the best performance for the low code rates 0<R<0.25., among the asymptotically good convolutional codes known up to now.