Jin-Hyuk YANG In-Cheol PARK Chong-Min KYUNG
In this paper, an instruction-cache scheme called Multi-Path Tracing is proposed to enhance the trace cache. Paths are classified to improve the trace cache hit ratio by reducing the path conflict and basic blocks are joined to reduce the hardware cost needed to implement the trace cache. Simulation results for various SPEC integer benchmarks show that the proposed scheme increases the hit ratio by more than 25% and the effective fetch size by 10%.
Xiaomin MA Xian Yang YI Zhaozhi ZHANG
Some novel learning strategies based on set covering in Hamming geometrical space are presented and proved, which are related to the three-layer Boolean neural network (BNN) for implementing an arbitrary Boolean function with low-complexity. Each hidden neuron memorizes a set of learning patterns, then the output layer combines these hidden neurons for explicit output as a Boolean function. The network structure is simple, reliable and can be easily implemented by hardware.
Masahide NAKAMURA Tohru KIKUNO
Feature interaction detection determines whether interactions occur or not between the new and existing telecommunication services. Most of conventional detection methods on state transition model utilize an exhaustive search. The exhaustive search is fundamentally very powerful in the sense that all interactions are exactly detected. However, it may suffer from the state explosion problem due to the exponential growth of the number of states in the model when the number of users and the number of features increase. In order to cope with this problem, we propose a new detection method using a state reduction technique. By means of a symmetric relation, called permutation symmetry, we succeed in reducing the size of the model while preserving the necessary information for the interaction detection. Experimental evaluation shows that, for practical interaction detection with three users, the proposed method achieves about 80% reduction in space and time, and is more scalable than the conventional ones especially for the increase of the number of users in the service.
In order to improve the efficiency of the feature extraction of backpropagation (BP) learning in layered neural networks, model switching for changing the function model without altering the map is proposed. Model switching involves map preserving reduction of units by channel fusion, or addition of units by channel installation. For reducing the model size by channel fusion, two criteria for detection of the redundant channels are addressed, and the local link weight compensations for map preservation are formulated. The upper limits of the discrepancies between the maps of the switched models are derived for use as the unified criterion in selecting the switching model candidate. In the experiments, model switching is used during the BP training of a layered network model for image texture classification, to aid its inefficiency of feature extraction. The results showed that fusion and re-installation of redundant channels, weight compensations on channel fusion for map preservation, and the use of the unified criterion for model selection are all effective for improved generalization ability and quick learning. Further, the possibility of using model switching for concurrent optimization of the model and the map will be discussed.
This paper demonstrates the necessity of special handling mechanisms for type (or sort) information when learning logic programs on the basis of background knowledge that includes type hierarchy. We have developed a novel relational learner RHB, which incorporates special operations to handle the computing of the least general generalization (lgg) of examples and the code length of logic programs with types. It is possible for previous learners, such as FOIL, GOLEM and Progol, to generate logic programs that include type information represented as is_a relations. However, this expedient has two problems: one in the computation of the code length and the other in the performance. We will illustrate that simply adding is_a relations to background knowledge as ordinary literals causes a problem in computing the code length of logic programs with is_a literals. Experimental results on artificial data show that the learning speed of FOIL exponentially slows as the number of types in the background knowledge increases. The hypotheses generated by GOLEM are about 30% less accurate than those of RHB. Furthermore, Progol is two times slower than RHB. Compared to the three learners, RHB can efficiently handle about 3000 is_a relations while still achieving a high accuracy. This indicates that type information should be specially handled when learning logic programs with types.
Gang ZHAO Shoji TATSUMI Ruoying SUN
Reinforcement learning is an efficient method for solving Markov Decision Processes that an agent improves its performance by using scalar reward values with higher capability of reactive and adaptive behaviors. Q-learning is a representative reinforcement learning method which is guaranteed to obtain an optimal policy but needs numerous trials to achieve it. k-Certainty Exploration Learning System realizes active exploration to an environment, but, the learning process is separated into two phases and estimate values are not derived during the process of identifying the environment. Dyna-Q architecture makes fuller use of a limited amount of experiences and achieves a better policy with fewer environment interactions during identifying an environment by learning and planning with constrained time, however, the exploration is not active. This paper proposes a RTP-Q reinforcement learning system which varies an efficient method for exploring an environment into time constraints exploration planning and compounds it into an integrated system of learning, planning and reacting for aiming for the best of both methods. Based on improving the performance of exploring an environment, refining the model of the environment, the RTP-Q learning system accelerates the learning rate for obtaining an optimal policy. The results of experiment on navigation tasks demonstrate that the RTP-Q learning system is efficient.
Shoichiro YAMASAKI Hirokazu TANAKA Atsushi ASANO
Multimedia communications over mobile networks suffer from fluctuating channel degradation. Conventional error handling schemes consist of the first stage error correction decoding in wireless interface and the second stage error correction decoding in multimedia demultiplexer, where the second stage decoding result is not used to improve the first stage decoding performance. To meet the requirements of more powerful error protection, we propose iterative soft-input/soft-output error correction decoding in multimedia communications, where the likelihood output generated by the error correction decoding in multimedia demultiplexer is fed back to the decoding in wireless interface and the decoding procedure is iterated. The performances were evaluated by MPEG-4 video transmission simulation over mobile channels.
Yasuhiro MATSUMOTO Toru FUJIWARA
A recursive maximum likelihood decoding (RMLD) algorithm is more efficient than the Viterbi algorithm. The decoding complexity of the RMLD algorithm depends on the recursive sectionalization. The recursive sectionalization which minimizes the decoding complexity is called the optimum sectionalization. In this paper, for a class of non-linear codes, called rectangular codes, it is shown that a near optimum sectionalization can be obtained with a dynamic programming approach. Furthermore, for a subclass of rectangular codes, called C-rectangular codes, it is shown that the exactly optimum sectionalization can be obtained with the same approach. Following these results, an efficient algorithm to obtain the optimum sectionalization is proposed. The optimum sectionalizations for the minimum weight subcode of some Reed-Muller codes and of a BCH code are obtained with the proposed algorithm.
Motivated by intention to evaluate asymptotically multiple-burst-error-correcting codes on channels with memory, we will derive the following fact. Let {Zi } be a hidden Markov process, i. e. , a functional of a Markov chain with a finite state space, and Wb(Z1Z2Zn) denote the number of burst errors that appear in Z1Z2Zn, where the number of burst errors is counted using Gabidulin's burst metric , 1971. As the main result, we will prove the almost sure convergence of relative burst weight Wb(Z1Z2Zn)/n, i. e. , the relative frequency of occurrence of burst errors, for a broad class of functionals { Zi } of finite Markov chains. Functionals of Markov chains are often adopted as models of the noises on channels, especially on burst-noise channels, the most famous model of which is probably the Gilbert channel proposed in 1960. Those channel models described with Markov chains are called channels with memory (including channels with zero-memory, i. e. , memoryless ones). This work's achievement enables us to extend Gilbert's code performance evaluation in 1952, a landmark that offered the well-known Gilbert bound, discussed its relationship to the (memoryless) binary symmetric channel, and has been serving as a guide for the-Hamming-metric-based design of error-correcting codes, to the case of the-burst-metric-based codes (burst-error-correcting codes) and discrete channels with or without memory.
Seong Ill PARK So Ryoung PARK Iickho SONG Jooshik LEE Young-Sup JOO Dae Jin KIM
In this paper, we investigate an inherent noise reduction characteristic of a modulated orthogonal sequence. The modulated orthogonal sequence generates length N2 sequences from N information symbols. Using the amplitudes of received sequences, we first estimate the smallest amplitude noise. Then the noise is reduced by the proposed scheme. The noise reduction scheme is shown to have an excellent performance in non-Gaussian noise environment.
Kunio YOSHIDA Heiju UCHIIKE Masahiro SAWA
The relationships between lattice orientation of the electron-beam evaporated MgO layer used as protecting layer for ac plasma displays (ac-PDPs) and the discharge characteristics of color ac-PDPs were investigated by the measurements of ion-induced secondary electron emission. It is proved that values of γi for MgO are large in the order of (220) orientation, (200) orientation, and (111) orientation, that is, γi(220) > γi(200) > γi(111). The values of φ for different lattice orientation are obtained by the measurements of thermionic emission and photo emission. The aging measurements for testing panels with the different lattice orientation of MgO layer revealed that performance of those panels are excellent in the order of (220), (200), and (111). In particular, luminance and luminous efficiency become larger in the order of (220), (200), and (111). It is pointed out that the degree of longevity, sustaining voltage, and memory margin for ac-PDPs with protecting materials as MgO are estimated by the measurements of γi.
Akira SHIOZAKI Yasushi NOGAWA Tomokazu SATO
We proposed a soft-decision decoding algorithm for cyclic codes based on energy minimization principle. This letter presents the algorithm which improves decoding performance and decoding complexity of the previous method by giving more initial positions and introducing a new criterion for terminating the decoding procedure. Computer simulation results show that both the decoded block error rate and the decoding complexity decrease by this method more than by the previous method.
A new UEP technique for image transmission using trellis code based on Hamming distance criterion has been proposed. The simulation results comparing the image quality and bit-rate for UEP and EEP have been provided. The results show that UEP performs better than EEP in terms of bit-rate without any significant depreciation in image quality.
Hiroshi NAGAMOCHI Toshimasa ISHII Toshihide IBARAKI
For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.
Mohd ABDUR RASHID Masao KODAMA
The method solving Bessel's differential equation for calculating numerical values of the Bessel function Jν(x) is not usually used, but it is made clear here that the differential equation method can give very precise numerical values of Jν(x), and is very effective if we do not mind computing time. Here we improved the differential equation method by using a new transformation of Jν(x). This letter also shows a method of evaluating the errors of Jν(x) calculated by this method. The recurrence method is used for calculating the Bessel function Jν(x) numerically. The convergence of the solutions in this method, however, is not yet examined for all of the values of the complex ν and the real x. By using the differential equation method, this letter will numerically ascertain the convergence of the solutions and the precision of Jν(x) calculated by the recurrence method.
Takamitsu KUDO Tsuyoshi Sasaki USUDA Ichi TAKUMI Masayasu HATA
In this paper, we show that the principle of quantum cryptography can be applied not only to a key distribution scheme but also to a data transmission scheme. We propose a secure data transmission scheme in which an eavesdropping can be detected based on sharing the bases Alice (the sender) and Bob (the receiver) have. We also show properties of this scheme.
Toshiaki SUGIHARA Tsutomu MIYASATO Ryohei NAKATSU
In this paper, we describe an experimental evaluation of visual fatigue in a binocular disparity type 3-D display system. To evaluate this fatigue, we use a subjective assessment method and focus on mismatching between convergence and accommodation, which is a major weakness of binocular disparity 3-D displays. For this subjective assessment, we use a newly-developed binocular disparity 3-D display system with a compensation function for accommodation. Because this equipment only allowed us to compare the terms of the mismatching itself, the evaluation is more accurate than similar previous works.
Takashi NOSE Naoyasu IKEDA Hiroshi KANOH Hidenori IKENO Hiroshi HAYAMA Setsuo KANEKO
We proposed a new method to evaluate display legibility as a function of resolution. This method was able to evaluated display legibility without being restricted to the display resolution. Using this method, subjective psychological experiments were carried out to investigate display resolution, which provides legibility, in observing small characters. Samples viewed by subjects were images displayed on a high-resolution TFT-LCD that we developed, CRT images and printed documents for comparison. We have found that TFT-LCD legibility was much better than that of CRT, and that minimum resolution of about 175 dpi was needed for use in legible document viewers.
Noboru TAKAGI Kyoichi NAKASHIMA
In this paper, we focus on regularity and set-valued functions. Regularity was first introduced by S. C. Kleene in the propositional operations of his ternary logic. Then, M. Mukaidono investigated some properties of ternary functions, which can be represented by regular operations. He called such ternary functions "regular ternary logic functions". Regular ternary logic functions are useful for representing and analyzing ambiguities such as transient states or initial states in binary logic circuits that Boolean functions cannot cope with. Furthermore, they are also applied to studies of fail-safe systems for binary logic circuits. In this paper, we will discuss an extension of regular ternary logic functions into r-valued set-valued functions, which are defined as mappings on a set of nonempty subsets of the r-valued set {0, 1, . . . , r-1}. First, the paper will show a method by which operations on the r-valued set {0, 1, . . . , r-1} can be expanded into operations on the set of nonempty subsets of {0, 1, . . . , r-1}. These operations will be called regular since this method is identical with the way that Kleene expanded operations of binary logic into his ternary logic. Finally, explicit expressions of set-valued functions monotonic in subset will be presented.
This paper gives a detailed presentation of a "vision chip" for a very fast detection of motion vectors. The chip's design consists of a parallel pixel array and column parallel block-matching processors. Each pixel of the pixel array contains a photo detector, an edge detector and 4 bits of memory. In the detection of motion vectors, first, the gray level image is binarized by the edge detector and subsequently the binary edge data is used in the block matching processor. The block-matching takes place locally in pixel and globally in column. The chip can create a dense field of motion where a vector is assigned to each pixel by overlapping 2 2 target blocks. A prototype with 16 16 pixels and four block-matching processors has been designed and implemented. Preliminary results obtained by the prototype are shown.