Kiyoshi MIKAMI Hiroshi TAMURA Masakazu SENGOKU Yoshio YAMAGUCHI
The synchronic distance is a fundamental concept in a Petri net. Marked graphs form a subclass of Petri nets. Given a matrix D, we are interested in the problem of finding a marked graph whose synchronic distance matrix is D. It is wellknown that the synchronic disrance matrix of a marked graph is a distance matrix. In this letter, we give a matrix D such that D is a distance matrix and there does not exist a marked graph whose synchronic distance matrix is D.
Shoichiro YAMADA Shunichi NAKAYAMA
We propose a new multiple folding algorithm for the gate matrix layout, and apply it to generation of rectangular blocks with flexible size. The algorithm consists of two phases, the net partitioning and the gate arangement, and both algorithms are based on the multi-way mini-cut technique. In the first and second phases, the width and height of the multiple folded gate matrix block are directly minimized, resperctively, such that the area is minimized and desired aspect ratio of the block is obtained. The features of the present algorithm are as hollows: (1) Dead space on the gate matrix block can be minimized, (2) the aspect ratio can be controlled finely, (3) since polar graphs are successfully used in the second phase, the efficiency of the algorithm can be much improved. The experimental results show the effectiveness of our algorithm.
This paper proposes new design methods for single b-bit (b2) byte error correcting and double bit error detecting code, called SbEC-DED code, suitable for high-speed memory systems using byte organized RAM chips. This new type of byte error control code is practical from the viewpoint of having less redundancy and stronger error control capability than the existing ones. A code design method using elements from a coset of subfield under addition gives the practical SbEC-DED code with 64 information bits and 4-bit byte length which has the same check-bit length, 12 bits, as that of the Hamming single byte error correcting code. This also has very high error detection capabilities of random double byte errors and of random triple bit errors.
Masayuki OKUNO Akio SUGITA Tohru MATSUNAGA Masao KAWACHI Yasuji OHMORI Katsumi KATOH
A strictly nonblocking 88 matrix switch was designed and fabricated using silica-based planar lightwave circuits (PLC) on a silicon substrate. The average insertion loss was 11 dB in the TE mode and 11.3 dB in the TM mode. The average switch element extinction ratio was 16.7 dB in the TE mode and 17.7 dB in the TM mode. The accumulated crosstalk was estimated to be 7.4 dB in the TE mode and 7.6 dB in the TM mode. The driving power of the phase shifter required for switching was about 0.5 W and the polarization dependence of the switching power was 4%. The switching response time was 1.3 msec. The wavelength range with a switch extinction ratio of over 15 dB was 1.31 µm30 nm.
This paper proposes a compact high-speed ATM switching architecture that employs a novel arbitration method. The NN matrix shaped crosspoint switch is realized with D small switch blocks (SSBs). The number of crosspoints and address comparators is reduced from N2 to (N/D)2. Each block contains N/D input lines and N/D output lines. The association between output lines and output ports is logically changed each cell period. This arrangement permits each input port to be connected to N/D output ports in each cell period. Output-line contention control is realized block-by-block so high-speed operation is realized. The traffic characteristics of the proposed switch architecture are analyzed using computer simulations. According to the simulation results, the cell loss rate of 10-8 is achieved with only 100-cell input and output-buffers under the heavy random load of 0.9 for any size switch. The proposed ATM switching architecture can construct the Gbit/s high-speed ATM switch fabric needed for B-ISDN.
Supoj CHINVEERAPHAN Ken'ichi DOUNIWA Makoto SATO
An efficient technique for expressing document image is required as part of a unified approach to document image processing. This paper presents a new method, Minimum Covering Run (MCR), for expressing binary images. The name being adapted from horizontal or vertical run representation. The proposed technique uses some horizontal and vertical runs together to represent binary images in which the total number of representative runs is minimized. Considering the characteristic of above run types precisely, it is shown that horizontal and vertical runs of any binary image could be thought of as partite sets of a bipartite graph. Consequently, the MCR expression that corresponds to the construction of one of the most interesting problems in graphs; i.e., maximum matching, is analogously found by using an algorithm which solves this problem in a corresponding graph. The most efficient algorithm takes at most O(n5/2) computations for solving the problem where n is the sum of cardinalities of both partite sets. However, some patterns in images like tables or line drowings, generally, have a large number of runs representing them which results in a long processing time. Therefore, we provide the Rectangular Segment Analysis (RSA) as a pre-processing to define runs representing such patterns beforehand. We also show that horizontal and vertical covering parts of the proposed expression are able to represent stroke components of characters in document images. As an implementation, an efficient algorithm including arrangement for run data structure of the MCR expression is presented. The experimental results show the possibility of stroke extraction of characters in document images. As an application, some patterns such as tables can be extracted from document images.
Nobuo MURAKOSHI Eiji WATANABE Akinori NISHIHARA
Low-sensitivity digital filters are required for accurate signal processing. Among many low-sensitivity digital filters, a method using complex allpass circuits is well-known. In this paper, a new synthesis of complex allpass circuits is proposed. The proposed synthesis can be realized more easily either only in the z-domain or in the s-domain than conventional methods. The key concept for the synthesis is based on the factorization of lossless scattering matrices. Complex allpass circuits are interpreted as lossless digital two-port circuits, whose scattering matrices are factored. Furthermore, in the cases of Butterworth, Chebyshev and inverse Chebyshev responses, the explicit formulae for multiplier coefficients are derived, which enable us to synthesize the objective circuits directly from the specifications in the s-domain. Finally design examples verify the effectiveness of the proposed method.
Hiroyuki FUJIWARA Juro UENO Hiromasa KUDO Ikuo OKA Ichiro ENDO
An optical On-Off Keyed (OOK) pulse is often stretched in dispersive channels, thus producing intersymbol interference (ISI) and degrading the performance. In this paper, error probability is presented for a convolutionally encoded optical OOK channels with ISI. Both ISI-matched and ISI-mismatched decoders are taken into account in the error probability analysis. The encoded optical OOK signal is received by Avalanche Photo Diode (APD) and the number of APD output photo-electrons is counted for soft decision Viterbi decoding. Error probability is derived for a 3-bit and an ideal soft decision schemes in ISI-mismatched decoder and for an ideal soft decision scheme in ISI-matched decoder. Numerical results demonstrate the effects of mismatching or 3-bit soft decision scheme. Some computer simulations are carried out to confirm the validity of the analysis.
This is a partly expository paper discussing how point processes with certain "bursty" features can be qualitatively modelled by the Markovian arrival process, a generalization of the Poisson or Bernoulli processes which can be used to obtain algorithmically tractable matrix solutions to a variety of problems in probability models.
This article discusses a synthesis procedure of a discrete-time asynchronous neural network whose information is a limit cycle. The synthesis procedure uses a novel connection matrix and can be reduced into a linear epuation. If all elements of desired limit cycles are independent at each transition step, the equation can be solved and all desired limit cycles can be stored. In some experiments, our procedure exhibits much better storing performance than previous ones.
The F-matrix expressions of inverted-L-type four-terminal networks, each involving an element with the power-law conductivity σ(ω)ωa (0a1) connected to a resistance R, an inductance L or a capacitance C, were derived using the standard procedures of Laplace transformation, indicating that the exponents of the complex angular frequency s, so far limited to the integers for the transmission circuits with finite elements, can be extended to the real numbers. The responses to a step voltage calculated show hysteretic behavior reflecting the resistance-capacitance ambivalent nature of the power-law conductivity.
It has been recognized that there exist some disparities between properties of continuous control systems and those of discrete ones which are obtained from their continuous counterparts by use of a sampler and zero order hold. This still remains true even if the sampling rate becomes fast enough and sometimes causes unfavorable effects in control systems design. To reconcile with this conflict, use of delta operator has been proposed in place of z-operator recently. This note formulates a delta domain Lyapunov matrix equation and shows that the equation actually mediates the discrete Lyapunov equation and its continuous counterpart.