We explain three random sampling techniques that are simple but widely applicable for various problems involving huge data sets. The first technique is an immediate application of large deviation bounds. The second and the third ones are sequential sampling or adaptive sampling techniques. We fix one simple problem and explain these techniques by demonstrating algorithms for this problem and discussing their correctness and efficiency.
This paper surveys recent progress in the investigation of the underlying discrete proximity structures of geometric clustering with respect to the divergence in information geometry. Geometric clustering with respect to the divergence provides powerful unsupervised learning algorithms, and can be applied to classifying and obtaining generalizations of complex objects represented in the feature space. The proximity relation, defined by the Voronoi diagram by the divergence, plays an important role in the design and analysis of such algorithms.
This letter describes several techniques for optimizing software implementations of E2 on various platforms. We propose optimization techniques for each part of E2; a new inversion algorithm, efficient byte splitting and merging for BP-Function, and an efficient SPN (Substitution-Permutation Network) implementation for 32- or 64-bit processors. As a result, E2 achieves the encryption speeds of 100.5 kb/s, 68.3 Mb/s, 162.3 Mb/s, and 130.8 Mb/s for H8/300 (5 MHz), Pentium Pro (200 MHz), Pentium II (450 MHz), and 21164A (600 MHz).
The applications of reactance-loaded beam tilting dipole antennas have been reported by many researchers. The reactance elements loaded on the applications reported up to date have been used only for the purpose of beam tilting. This paper presents the basic characteristics of the beam tilting dipole antenna element in which one reactance element is used for the impedance matching at the feed point. The radiation pattern is tilted by the properly determined driving point position, and the loading reactance is used to obtain forced resonance without great changes in tilt angle. The numerical results demonstrate that the reactance element should be loaded in the region where the driving point is placed to obtain forced resonance of the antenna with little changes in beam tilt angle. In case the proposed forced resonant beam tilting antenna with 0.8λ length is driven at 0.2λ from the center, the main beam tilt angle of 57.7 degrees, the highest power gain of 8.6 dB, and VSWR=2.2 are obtained.
It is the purpose of this paper to review the generation of quantized voltage steps in Josephson-junctions, and also the recent practical application of these precise measurements. A 10-V Josephson-junction-array-voltage standard system has been established with a Josephson-junction-array, a phase-locked millimeter wave, and a precise null-detection system. Based on these technologies, the AC Josephson effect has been applied to other precise measurements such as DC error voltage of a multi-integrating analog-to-digital converter and for a pulse-width-modulation type precise voltage calibrator.
Zhen WANG Yoshinori UZAWA Akira KAWAKAMI
We report on progress in the development of high current density NbN/AlN/NbN tunnel junctions for application as submillimeter wave SIS mixers. A ultra-high current density up to 120 kA/cm2, roughly two orders of magnitude larger than any reported results for all-NbN tunnel junctions, was achieved in the junctions. The magnetic field dependence and temperature dependence of critical supercurrents were measured to investigate the Josephson tunneling behaviour of critical supercurrents in the high-Jc junctions. We have developed a low-noise quasi-optical SIS mixer with the high-current density NbN/AlN/NbN junctions and two-junction tuning circuits which employ Al/SiO/NbN microstriplines. The tuning characteristics of the mixer were investigated by measuring the response in the direct detection mode by using the Fourier Transform Spectrometer (FTS) and measuring the response in the heterodyne detection mode with the standard Y-factor method at frequencies from 670 to 1082 GHz. An uncorrected double sideband receiver noise temperature of 457 K (12hν/kB) was obtained at 783 GHz.
Shiho MORIAI Takeshi SHIMOYAMA Toshinobu KANEKO
We introduce an efficient interpolation attack which gives the tighter upper bound of the complexity and the number of pairs of plaintexts and ciphertexts required for the attack. In the previously known interpolation attack there is a problem in that the required complexity for the attack can be overestimated. We solve this problem by first, finding the actual number of coefficients in the polynomial used in the attack by using a computer algebra system, and second, by finding the polynomial with fewer coefficients by choosing the plaintexts. We apply this interpolation attack to the block cipher SNAKE and succeeded in attacking many ciphers in the SNAKE family. When we evaluate the resistance of a block cipher to interpolation attack, it is necessary to apply the interpolation attack described in this paper.
Recent progress of high-temperature superconductor Josephson junction technology is reviewed in the light of the future application to digital circuits. Among various types of Josephson junctions so far developed, ramp-edge-type junctions with a barrier layer composed of oxide materials in the vicinity of metal-insulator transition seem to offer a unique opportunity to fulfill all the requirements for digital circuit applications by virtue of their small junction dimensions, overdamped properties and relatively high IcRn product values at the temperature of around 30-40 K. Recently developed interface engineered junctions can be classified as junctions of this type. These junctions also raise an interesting problem in physics concerning the possibility of resonant tunneling of Cooper pairs via localized states in the barrier. From the viewpoint of practical applications, the improvement of the spread of the junction parameters is still a serious challenge to the present fabrication technology. Although interface engineered junctions seem to be most promising in this regard at present, 1σ spread of around 8% in the present fabrication technology is far from satisfactory for the fabrication of large-scale integrated circuits. The detailed understanding of the barrier formation mechanism in the interface engineered junction is indispensable not only for advancing this particular fabrication technology but also for improving other junction technology utilizing ramp-edge structures.
Hyun H. PARK Byung W. KIM Yeon C. CHUNG Joo G. LEE
The coupling between transmission lines on the PCB (printed circuit board) within a rectangular enclosure with an aperture is investigated by using the finite-difference time-domain (FDTD) method.
Pavol ZAVARSKY Takeshi MYOKEN Noriyoshi KAMBAYASHI Shinji FUKUMA Masahiro IWAHASHI
The paper shows some of benefits of multi-unitary decomposition in signal analysis applications. It is emphasized that decompositions of complex discrete-time signals onto a single basis provide an incomplete and in such way potentially misleading image of the signals in signal analysis applications. It is shown that the multi-unitary decimated filter banks which decompose the analyzed signal onto several bases of the given vector space can serve as a tool which provides a more complete information about the signal and at the same time the filter banks can enjoy efficient polyphase component implementation of maximally decimated, i. e. nonredundant, filter banks. An insight into the multi-unitary signal decomposition is provided. It is shown that the multiple-bases representation leads to an efficient computation of frequency domain representations of signals on a dense not necessarily uniform frequency grid. It is also shown that the multiple-bases representation can be useful in the detection of tones in digital implementations of multifrequency signaling, and in receivers of chirp systems. A proof is provided that there are possible benefits of the multiple-bases representations in de-noising applications.
Yasuji MURAKAMI Kimio ANDOU Kouji SHINO Toshiaki KATAGIRI Satomi HATANO
This paper reports the design and characteristics of an aerial optical drop cable incorporating electric power wires, which was developed for a new π-system. The new system is called the power supply HUB π-system, in which commercial AC electric power is received at a central location of several optical network units (ONUs), and is distributed to each ONU by the aerial optical/electric drop cable. We describe the requirements for the cable, which guarantee a 20-year lifetime. We designed the cross-sectional structure of the cable, based on system requirements and operation requirements, and determined the strength wire type and diameter, based on the optical fiber failure prediction theory and a cable strain requirement. We confirmed that the cables, manufactured as a trial, have stable characteristics, which satisfy the above requirements. The optical/electric drop cables will be introduced in autumn 1999.
Noboru KUNIHIRO Hirosuke YAMAMOTO
Power exponentiation is an important operation in modern cryptography. This operation can be efficiently calculated using the concept of the addition chain. In this paper, two new systematic methods, a Run-length method and a Hybrid method, are proposed to generate a short addition chain. The performance of these two methods are theoretically analyzed and it is shown that the Hybrid method is more efficient and practical than known methods. The proposed methods can reduce the addition chain length by 8%, in the best case, compared to the Window method.
Hiroki ARIMURA Akihiro YAMAMOTO
Inductive Logic Programming (ILP) is a study of machine learning systems that use clausal theories in first-order logic as a representation language. In this paper, we survey theoretical foundations of ILP from the viewpoints of Logic of Discovery and Machine Learning, and try to unify these two views with the support of the modern theory of Logic Programming. Firstly, we define several hypothesis construction methods in ILP and give their proof-theoretic foundations by treating them as a procedure which complets incomplete proofs. Next, we discuss the design of individual learning algorithms using these hypothesis construction methods. We review known results on learning logic programs in computational learning theory, and show that these algorithms are instances of a generic learning strategy with proof completion methods.
Jie CHEN Guoliang SHOU Changming ZHOU
High-speed low-power matched filter plays an important role in the fast despreading of spread-signals in wideband code division multiple access (W-CDMA) mobile communications. In this paper, we describe the algorithm and the VLSI-architecture of a complex matched filter chip implemented by our proposed digital-controlled analog parallel operational circuits. The complex matched filter VLSI with variable taps from 4 to 128 is developed for despreading QPSK-modulated spread-signals for W-CDMA communications, which is fabricated by a 2-metal 0.8 µm CMOS technology. The dissipation power of the chip is 225 mW and 130 mW when it operates at the chip-rate of 20 MHz with the supply voltages of 3.0 V and 2.5 V, respectively, and it can be furthermore reduced to 62 mW at chip rate of 10 MHz when the supply voltage is lowered to 2.2 V. The 3-dB cut-off frequency of the fabricated chip is higher than 20 MHz for both 3.0 V and 2.5 V supplies. Comparing to pure digital matched filters, the massive and high-speed despreading operations of the spread-signals are directly carried out in analog domain. As a result, two high-speed analog-to-digital (A/D) converters operating at chip rate are omitted, the inner signal paths and the total dissipation power are greatly reduced.
Shingo MIYAZAKI Kouichi SAKURAI
We propose an untraceable electronic money system. Our system uses the partially blind signature based on the discrete logarithm problem, and applies secret key certificates to the payment protocol.
Hiroshi OGAWA Takao NAKAMURA Atsuki TOMIOKA Youichi TAKASHIMA
A quantization-based watermarking system for motion pictures is proposed. In particular, methods for improving the image quality of watermarked video, the watermarking data tolerance, and the accuracy of watermark data detection are described. A quantitative evaluation of the reliability of watermarked data, which has not generally been discussed up to now, is also performed.
A new efficient two-dimensional warping algorithm is presented, in which sub-optimal warping is attained by iterating DP-based local optimization of warp on partially overlapping subplane sequence. From an experimental comparison with a conventional approximation algorithm based on beam search DP, relative superiority of the proposed algorithm is established.
Saburo TANAKA Ryouji SHIMIZU Yusuke SAITO Koichi SHIN
A portable cryo-system using a high-Tc SQUID for the measurement of the remanant magnetic field of a rock specimen was designed and fabricated. The sensing surface of the SQUID faces upward in our system, although the system for bio-magnetics faces down. The SQUID is cooled by liquid nitrogen via a sapphire heat transfer rod. The total heat transfer of the system was measured by means of a boiling-off method and was found to be 1.65 W. It was demonstrated that the system can be operated for more than 17 hours without any maintenance such as filling with liquid nitrogen. The system was applied to the measurement of the remanent magnetic field distributions of rock samples cored from deep underground. We have successfully measured the distributions.
Mitsuo OHTA Kiminobu NISHIMURA
The noise level distribution owing to only a non-stationary working objective machine has been stochastically expressed by reflecting the temporal change of distribution parameters under a generalized regression model especially with aid of the vibration level observation. The proposed method has been applied to a noise evaluation of non-stationarily operated jigsaw.
Takao MATSUMOTO Kazuo KIMURA Kazuhiro NOGUCHI Masahiko JINNO
Optical time- and wavelength-domain paths in future very-high-speed optical communications networks are discussed taking into account trends in current optical transmission and optical signal processing technologies. It is important to investigate optical STM cross-connect systems for time-domain paths in the earlier research phase to ensure the deployment of optical cross-connect technology. The configuration of an optical cross-connect system and the issues that need to be investigated are presented. We also report, for the first time, a preliminary experiment of an optical STM cross-connect system, using 20 Gbit/s optical signals.