Search

It is well known that sequential decoding methods for burst error control codes use Linear Feedback Shift Registers (LFSR). However, a parallel decoding method employing only combinational logic is preferable in certain applications, such as semiconductor memory systems and holographic memory systems, where a huge amount of data needs to be read or written at ultrahigh speed. This paper proposes a parallel decoding method for linear burst error control codes including the Fire code. In order to obtain the error pattern, this decoding method uses an inverse matrix of a nonsingular matrix which includes a sub-matrix of the parity check matrix. Burst error correction is possible because correct burst error patterns are obtained only from frames that completely include the burst error pattern. Furthermore, this decoding method can also be applied to single byte error correcting codes with less hardware. The implementation of decoding circuits for burst and byte error control codes are illustrated in this paper. And their hardware complexity is also evaluated to show that the proposed method requires less hardware than the existing parallel decoding method. Finally, we will discuss about how the proposed decoding method can be extended to correct multiple burst or byte errors. © 2003 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(1): 38–48, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10094 [ABSTRACT FROM AUTHOR]

In this paper, a new median filter is proposed that has robustness without relying on the noise generation probability. The proposed filter has a configuration with an impulse detector in the prior stage of the filter. Since this detector has a superior signal estimation capability of the directional difference filter, impulse noise can be detected effectively even if generated at a high generating ratio and as a burst. In the median filter in the later stage, inclusion of the output values of the directional filter and successive updating of the signal values (successive process) are introduced. Hence, while the noise elimination capability of the conventional median filter is retained, the signal preservation at the details and edges can be improved. Therefore, the noise elimination filter proposed in this paper is abundant in robustness against variations of the gray scale, the generation probability, and the impulse adding situation. Its restoration results for images with superposed impulse noise at a high generation probability confirm the improvement of performance. In this paper, the effectiveness of the proposed impulse detector is first demonstrated. It is proven through processing examples that a better image processing result can be obtained from its combination with a newly configured median filter. At the same time, the robustness of the proposed procedure under various conditions is demonstrated. The effectiveness of the proposed method in the final restored image is verified. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(3): 22–32, 2002 [ABSTRACT FROM AUTHOR]

When a planar graph is drawn, the drawing plane is divided into several regions, each of which is called a face. A subgraph composing the periphery of a face is called a window. For each window W that exists in the drawing of a planar graph G, the total sum of the weights of the vertices and the edges is called the weight of the window W. Among all windows that can appear in drawings, the window with the maximum weight is called the maximum-weight-window of C. This paper considers the problem of determining the drawing with the maximum-weight-window. The result for this problem is already obtained for the case where the graph is 2-connected, as well as for the case where the graph is not necessarily 2-connected but all weights are nonnegative. This paper considers also the arbitrary planar graph with real-valued weights, and shows that the drawing with the maximum-weight-window can be determined in O(n + e) time. This result can be applied to the layout design for LSI and printed board, as well as to the diagram representation of the network. It can also be applied to the solution of the maximal planarization problem for the graph. [ABSTRACT FROM AUTHOR]

This paper proposes a fast learning algorithm of neural networks and evaluates the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel. The backpropagation (BP) algorithm which is used widely to train neural networks has a slow convergence rate because it is based on the gradient descent method. This paper presents a fast learning algorithm using the recursive least squares (RLS) algorithm which has a fast convergence rate as an adaptive algorithm for adaptive linear filters. In the proposed algorithm, the sum of the squared error between the actual total input and the desired total input is used as the cost function to apply the RLS algorithm. A simulation result on the exclusive-OR problem indicates that the proposed algorithm is about 8.8 times faster than the BP for the number of iterations required to converge. Recently, there has been interest in adaptive equalizers as an application field of neural networks. However, the performance of an adaptive equalizer using a neural network in a frequency-selective fading channel which is observed in land mobile communications has never been evaluated. Therefore, in this paper, the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel are evaluated. Especially, an adaptive equalizer using the selectively unsupervised learning neural network proposed by the authors is considered. The adaptive equalizer can reject the false learning by carrying out learning selectively. It is shown that the adaptive equalizer is superior to the conventional one and the one using the conventional neural network. [ABSTRACT FROM AUTHOR]

The 1/f spectra that appear in electroencephalogram data are among the characteristics that appear in the wide range of self-organizing phenomena encompassing both physical and sociological phenomena. The fact that they appear across the various objects suggests that the underlying cause of the 1/f spectra can be elucidated by using a simplified model that does not depend on the detailed structure of the objects. This paper, treating the electroencephalogram as a macro-quantity of neuron activities, demonstrates the existence of a self-similar solution through the spatial-temporal coarse-graining of a neural network, which is a simplified model of the brain. The self-similar solution in fact leads to the derivation of a 1/f spectrum. © 2003 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(1): 72–81, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10016 [ABSTRACT FROM AUTHOR]

As a hierarchical layout design method that can handle hierarchical designs of large-scale integrated circuits, the BSG method, one of the general structural layout methods, is hierarchical and has evolved as a layout method including interconnections. It is the objective of this paper to construct a design system that will provide feedback as a guideline for circuit design modification in which the layers in the circuit design are faithfully represented and are evaluated from the point of view of layout, and the placement is reconstructed for optimization. Hierarchical BSG is realized by combining smaller BSGs (elemental BSGs) with root trees. The size, number, and hierarchical trees of BSGs can be specified by the designer. An experiment to demonstrate the hierarchical effect is carried out by artificially setting a hierarchical design environment with a combination of several thousands of cells. Performance competitive with that without a hierarchical approach is obtained in the resultant areas and interconnect lengths. As a layout algorithm, the number of rectangles to be treated is increased by one order of magnitude so that several tens of thousands of rectangles can be placed with high quality. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(3): 12–21, 2002 [ABSTRACT FROM AUTHOR]

Users previously had to use transcoding methods in which a coded audio stream was decoded and the decoded audio then reencoded at the desired bit rate. Data processing of coded audio therefore usually involves complex and time-consuming tasks. In this paper, we describe three algorithms for bit rate scaling on coded MPEG data domains. One is a bandwidth limitation method to cut higher frequency components until the target data rate is satisfied. A second method uses a requantization process where a quantization step in each subband is modified, and a third method also utilizes a requantization process with a psychoacoustic model from bit allocation information obtained in the bitstream in order to improve bit rate scaling efficiency. The simulation results show that the requantization process provides very high conversion efficiency and that sound quality nearly equal to that of direct coding can be obtained by utilizing the psychoacoustic model. It was also shown that very fast scaling (factor of six) can be achieved compared with the conventional baseband transcoding method. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(10): 47–56, 2001 [ABSTRACT FROM AUTHOR]

To assess the reliability of software products, the differences between the testing phase and the operational phase must be clearly distinguished. In contrast to the former that makes assessments based only on the statistical properties of the fault detection mechanism observed in the testing process, the latter must be executed by predicting the differences between the environment in the testing phase (effort, test method, and so on) and the software operational environment such as the frequency of use. Previously, many reliability assessment methods for software products in the operational phase have been proposed. However, none have adequately modeled the software operational environments without conflicts. The general methodologies in this field have still not been established. In this paper, we propose a dynamic model to represent the phenomenon of software reliability growth in the operational phase by applying the concept of accelerated life testing of hardware. In addition, we investigate the effectiveness of our model by using both the fault detection time data obtained in the actual software testing process and the error occurrence time data observed in the operational phase. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(8): 25–33, 2001 [ABSTRACT FROM AUTHOR]

If the inverse function x=f1(y) of the system y=f(x) with an input of x and an output of y is multivalued, learning of the inverse system by the neural network is difficult. Hence, in this paper, the mapping of (y,x)→x is learned by the neural network as the inverse system by making use of the extended generalized learning method. Next, the learning of the inverse system (many-valued function) is carried out by solving the obtained inverse system (nonlinear equation) by means of the successive substitution method after the desired output value yd is given so that the desired input value xd is derived. In this case, the learning problem of the neural network that satisfied the convergence condition of the successive substitution method is formulated as a satisfaction optimization problem. This is solved by the nondifferentiable optimization method. As a result of simulation experiment, it is confirmed that an inverse system of a one-to-multivalue correspondence is obtained. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(8): 57–66, 2001 [ABSTRACT FROM AUTHOR]

In this paper, a generalized version of the Hyperbolic Cascaded Reed–Solomon (HCRS) code proposed by K. Saints and C. Heegard is considered. The lower bound of the minimum distance (the design distance) is investigated. This is a linear code that can be expressed as (n, k, d min = d ) on GF(q). Here, n, k, dmin, and d are the code length, dimension, minimum distance, and design distance, respectively. The proposed code has more degrees of freedom in selection of the code length than the HCRS code. Codes with various code length can be constructed easily. However, in the m-dimensional space on GF(q), the selectable code length is less than qm. When the proposed code with a code length less than qm is compared with the shortened code with the same code length obtained by shortening the m-dimensional HCRS code with a code length of qm [or (q-1)m], the design distances are identical, whereas the proposed code has an equal or greater dimension compared with the HCRS code. Also, from the proposed code, it is relatively easy to construct a code of the same code length as the algebraic geometric code (geometric Goppa code) and the improved geometric Goppa code proposed by Feng and Rao. Further, when the performance (parameters) is compared at a high coding rate (k/n), the proposed code sometimes has equal or better performance. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(11): 18–27, 1999 [ABSTRACT FROM AUTHOR]

The graph partitioning problem is an NP hard problem of deriving the partitioning of each vertex such that the total sum of the edge weights among the groups is minimized and the total sum of the vertex weights in each group is less than the upper limit. In this paper, a neural network solution is proposed in which the binary neurons are used for the graph 2-partitioning problem. In the present neural network, an energy function that is applicable to graphs both with and without edge and vertex weights is defined. For improvement of solution accuracy, shaking terms are introduced into the operating equation. To evaluate the solution search capability of the present method, simulations are carried out for random graphs, together with the KL method proposed by Kernighan and Lin, and the FM method proposed by Fiduccia and Mattheyses. From the simulation results, it is shown that the solutions obtained by the present method are the best. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(12): 34–42, 1999 [ABSTRACT FROM AUTHOR]

With the digital representation of various data, such as speech, images, and messages, together with enhanced computer capabilities, it has become indispensable to apply data compression techniques to communication systems and recording systems. Among those, universal codes, including Ziv-Lempel codes, are widely used in computers, since the best compression can be realized asymptotically when the input string length is increased, even if the statistical properties of the input sequence are unknown. A problem arises, however, in connection with random data access or browsing, which are important functions in multimedia systems. In the Ziv-Lempel code, decoding must always be started from the top of the codeword sequence, even if only a part of the input coded sequence is to be decoded. This leads to an excessive load on computer resources. This paper proposes a code based on the Ziv-Lempel code in which partial decoding is possible. The proposed code is theoretically analyzed. The condition for the proposed code to be a universal code is presented. The encoding and decoding algorithms are implemented on a computer, and the result of the analysis is shown to be valid. It is shown that the proposed code has advantages over the Ziv-Lempel code from the viewpoint of applications, because the range of error propagation is restricted when an error is produced in decoding, and the decoding process can be accelerated by parallel processing. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(12): 79–87, 1999 [ABSTRACT FROM AUTHOR]

In order to capture the characteristics of non-Gaussian time series observed in biological signals, it is necessary to study higher-order spectra, such as the bispectrum, in addition to the power spectrum. In order to obtain estimates with little statistical variations in the estimation of higher-order spectra, establishment of a parametric estimation method is desired. Recently, a method has been proposed to numerically derive the higher-order spectra of nonlinear autoregressive models, such as neural net autoregressive models, by means of the repetitive integral transform. However, in efforts to describe the probability density function simply in a discrete manner, there is the problem of an exponentially increasing number of data points to be computed with increasing lag order. In this paper, in order to resolve this problem, a numerical method is proposed for description of the probability density function and integral kernel by means of a tensor product expansion. The tensor product expansion is a representation in terms of the sum of the tensor products of characteristic one-variable functions depending on the given multivariable function. There is a possibility of reducing the memory capacity needed for the calculations. Numerical examples of accurate calculations with fewer data points in the proposed method than in the conventional method are presented. Finally, an example of parametric estimation of the power spectrum and bispectrum of Wolf's sunspot numbers by the proposed method is given. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(11): 47–57, 1999 [ABSTRACT FROM AUTHOR]

A management system for main memory has a great deal of influence on the efficiency of an entire system. In particular, it is important to manage a system with multi-programming that allocates some jobs to main memory and performs their processing at the same time, because the memory space after some operations is not in good order due to additions and deletions of jobs; this is called fragmentation. These problems have not yet been solved fundamentally, but some techniques of solving them have been studied. This paper formulates a stochastic model of a memory-management system with functions of compaction and swapping, which are well-known typical techniques of improving efficiency. Using the theory of reliability, we discuss an optimal policy that reduces waste of memory and time spaces. © 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(10): 9–15, 1998 [ABSTRACT FROM AUTHOR]

Given, a graph G = (V, E), with two vertices s and t specified as the origin and destination, respectively; a positive integer K called the obstruction number; and (positive) weights l (·) on the edges; then, two players P1 and P2 play a game with the following rules. P1 starts from s, and tries to arrive at t by tracing an edge on each move. P2 cuts in his turn, P2 cuts some edges. The maximum total number of edges that P2 can cut is K during the game. It is assumed that both P1 and P2 can see the whole graph. P1 tries to minimize the sum of traveled edge weights (called the path length), and P2 tries to maximize the path length. This paper shows that the path length when the two players do their best can be determined in O(nk-l (m + n log n)) (m = |E| n = (|V|) time. It is also shown that the problem of deciding whether or not the path length when the two players do their best is not greater than a certain positive integer is P-SPACE-complete, even if the weight on each edge is 1. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(2): 13–23, 1998 [ABSTRACT FROM AUTHOR]

In the field of signal processing, some problems that are difficult to process using linear theory can be solved by nonlinear processing. As for estimation problems when an unknown system is nonlinear, real-time processing is difficult because of the huge amount of calculations required to find the optimum solution when conventional nonlinear process methods are used. On the other hand, research on neural networks that have nonlinear input-output relationships has attracted attention. These have been used in various areas such as pattern recognition and nonlinear system estimation. In this paper, a method of designing parallel recurrent neural digital filters by introducing several small, recurrent neural networks is proposed for nonlinear adaptive digital filters, which have many parameters and need real-time processing. The proposed method gives better results than conventional methods based on linear and nonlinear theory. Furthermore, learning efficiency can be improved by the proposed method because parallel learning is performed. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(12): 91–101, 1997 [ABSTRACT FROM AUTHOR]

In this paper, a method for prediction of command lines of the UNIX shell is proposed. Though the method is mainly based on the reuse of command lines, it is able to predict from a similar sequence by means of generalized command lines. A mixture of the frequency and locality of sequences in selecting candidates improves candidate accuracy. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(12): 56–64, 1997 [ABSTRACT FROM AUTHOR]

Model checking is a technique to decide whether a system modeled by a state graph satisfies a temporal logic formula. A serious problem in model checking of practical systems is that the size of the state graphs becomes huge. One solution of this problem is symbolic model checking, in which sets of states and transition relations over states are represented and handled symbolically. This research studies symbolic model checking in which realtime systems are modeled by time Petri nets and specifications are expressed by computation tree logic formulas. As realtime systems potentially have infinite state spaces, techniques to reduce infinite state spaces to finite ones are necessary. This paper discusses a technique based on equivalence classes, called regions, of states as well as a technique to restrict the behavior of time Petri nets so that transitions fire only at integer times. The algorithm in the former approach is presented in detail and then some experimental results are shown. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(4): 11–20, 1997 [ABSTRACT FROM AUTHOR]

In the continuous time model of the Hopfield neural network, which is one of the recurrent-type neural networks, the minimization of a quadratic objective function is carried out by the quasi-steepest descent method with decision variables in the upper and lower limits. This paper describes a quasi-steepest descent method in which arbitrary objective functions are selected. It is shown also that when a quasi-steepest descent method is made discrete under a certain sampling condition, the trajectory becomes chaotic. In addition, a method of applying the chaotic characteristics to the global optimization for a constrained optimization problem with upper and lower limits will be shown. The effectiveness of this method will be demonstrated numerically. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(4): 60–70, 1997 [ABSTRACT FROM AUTHOR]

A very important public-key cryptosystem, the RSA cryptosystem, was proposed by Rivest, Shamir, and Adleman in 1978. As it offers a high level of security and can also be used for digital signature purposes, it has been the subject of active research. Although it has many excellent features, it is well known that the RSA cryptosystem requires excessive encryption and decryption time because both operations require exponentiation and division. This paper presents fast encryption and decryption algorithms appropriate for an RSA cryptosystem using a particular form of the modulus n. The proposed method, designed to perform modular exponentiation, simplifies greatly the processing step of the operation, thereby enhancing speed. Applying this method to the RSA cryptosystem, it becomes possible to implement the cryptosystem with a reduced public-key size. User interface is both simple and secure. It is necessary to consider the tradeoff between a practical cryptosystem and a secure cryptosystem. It is even possible to send cipher text using a small key size, perhaps twice the size of a telephone number, with a higher security level than that of the conventional DES-type cryptosystem, with a key size of 56 bits. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(2): 24–34, 1997 [ABSTRACT FROM AUTHOR]

The word communication in the computer science field is associated with data communication. In the original context, communication is "person-to-persons communication" using some language or the human voice. Nowadays, handicapped people are assisted in communication by informational equipment. The authors have developed several tools as welfare communication tools for handicapped people and related volunteers. The main theme is a support system for the visually impaired and blind. Not only is research level equipment developed, but also commercial products. In this paper, several are described, along with some problems encountered in the development of welfare communication and accessibility to handicapped people. [ABSTRACT FROM AUTHOR]

Recently, sufficient conditions for a time-delay time- varying (TDTV) system have been shown to be non- expansive or bounded real (BR). Using this result, the sufficient conditions for stability of learning control for the TDTV system have been derived [2]. The characterise tic of these sufficient conditions is independent of delay. This paper considers the relation between these obtained conditions and the similarity transformation of a TDTV system, and derives new sufficient conditions of the nonexpansive TDTV system which are invariant under block similarity transformation. New stability conditions also are derived for the leaning control of the TDTV system. The new sufficient conditions include the parameter of delay Length explicitly, and ensure that when the given TDTV System satisfies the new conditions, every TDTV system which is similar to the given systems is nonexpansive. It also is shown that under a certain condition, the new sufficient conditions guarantee the nonexpansivity of TDTV system even when the value of the time-delay length of a real TDTV system deviates from the values in the sufficient condition. Finally, numerical examples are given to show that the obtained stability conditions of learning control are valid. [ABSTRACT FROM AUTHOR]

When genetic algorithms are applied to large-scale optimization problems taking only integer-valued solutions, too often the chromosomes generated faily to satisfy the constraint conditions. In such cases, the selection operator is unable to produce high-quality chromosomes, worsening the search efficiency. As a consequence, many times good solutions cannot be obtained. In this paper, in order to cope with such a problem, a new algorithm with improved chromosome selection mechanism is proposed, taking into account the evaluation function including some information about chromosomes not contained in the feasible region of the nonlinear integer programming problem under consideration. The proposed method considers how far each unfeasible chromosome is from the feasible region. The improved algorithm was applied to a large-scale problem of optimal design of system realibility formulated as a nonlinear integer programming problem and numerical experiments confirmed the effectiveness of the method. [ABSTRACT FROM AUTHOR]

When a database is updated, it is difficult to avoid divided accumulations of data is storage areas by adding and deleting them. Such divided accumulations decrease access efficiency; hence, efficient maintenance is needed to meet the requirement of high-quality service to users. However, maintenance costs must also be kept low. However, if the operating time of a database is specified, economical and planned maintenance to guarantee that high-quality services can be implemented. This paper considers the following stochastic model: A database is updated in accordance with a stochastic process and garbage is generated in the time between updatings, causing fragmentation in storage areas. Maintenance costs increase when accumulated garbage exceeds a threshold level. That is, to remove fragmentation from storage areas, garbage collection is made at time T or at the N-th update. The expected cost rate of this model is obtained and optimal time T* and number N*, which minimize it, are derived. Furthermore, numerical examples are given and some discussions for these examples are presented. [ABSTRACT FROM AUTHOR]

In this papers, we analyze some possible functions of networks where delays of pulse propagation and asynchronous events of pulse occurrence are considered, on the basic of a model asynchronous chaotic neural networks. First, the model is proposed and response characteristics of the single neuron are numerically analyzed, Second, it is shown that the network model with loop structure can select time interval sequence peculiar to the network structure even if random noise is superimposed. [ABSTRACT FROM AUTHOR]

When no function symbols occur in a first-order predicate formula, there exists a procedure to decide the satisfiability of the formula. Examples of such procedures are the method based on Robinson's resolution principle and the method based on the partial instantiation technique by Jeroslow. This paper considers the case where the formula is clausal form and no function symbols occur in it and proposes a satisfiability decision procedure based on the partial instantiation technique applicable to the considered case. The procedure is based on the partial instantiation technique, as in Jeroslow's method, but aims at the following aspects by utilizing the formula being in clausal form: (1) Davis-Putnam's method is used in solving the satisfiability problem in the prepositional logic; (2) the rapid expansion of the formula can be suppressed by expanding the formula with the clause as the unit; and (3) the number of unifications is reduced. The proposed method is compared to Jeroslow's method and the method based on the resolution principle, and then the effectiveness is demonstrated. [ABSTRACT FROM AUTHOR]

One of the methods to perform the high- performance LSI design rule check (DRC) art an engineering work station (EWS), is to employ the dedicated hardware engine. This paper considers the figure operation, which is the fundamental function of DRC, and describes the hardware-oriented algorithm and the design of the hardware system for its implementation. The algorithm is obtained by improving the slit method and the vector method used in the usual software system so that they fit the hardware implementation. The hardware is composed of five functional blocks (VS, OP1- OP-3 and WL), and is implemented on four of 16-bit microprocessors with 1 MByte main memory, together with FIF0 memory. The blocks operate in parallel, realizing a high-speed operation based on the three-stage pipeline. It was verified by a software simulation that the hardware configuration is adequate. [ABSTRACT FROM AUTHOR]