This paper proposes a novel image integral equation of the first type (IIE-1) for a TE plane wave scattering from periodic rough surfaces with perfect conductivity by means of the method of image Green's function. Since such an IIE-1 is valid for any incident wavenumbers including the critical wavenumbers, the analytical properties of the scattered wavefield can be generally and rigorously discussed. This paper firstly points out that the branch point singularity of the bare propagator inevitably appears on the incident wavenumber characteristics of the scattered wavefield and its related quantities just at the critical wavenumbers. By applying a quadrature method, the IIE-1 becomes a matrix equation to be numerically solved. For a periodic rough surface, several properties of the scattering are shown in figures as functions of the incident wavenumbers. It is then confirmed that the branch point singularity clearly appears in the numerical solution. Moreover, it is shown that the proposed IIE-1 gives a numerical solution satisfying sufficiently the optical theorem even for the critical wavenumbers.
Toru OMURA Tomoaki AKIBA Xiao XIAO Hisashi YAMAMOTO
A connected-(r,s)-out-of-(m,n): F system is a kind of the connected-X-out-of-(m,n): F system defined by Boehme et al. [2]. A connected-(r,s)-out-of-(m,n): F system consists of m×n components arranged in (m,n)-matrix. This system fails if and only if there exists a grid of size r×s in which all components are failed. When m=r, this system can be regarded as a consecutive-s-out-of-n: F system, and then the optimal arrangement of this system satisfies theorem which stated by Malon [9] in the case of s=2. In this study, we proposed a new algorithm for obtaining optimal arrangement of the connected-(r,2)-out-of-(m,n): F system based on the above mentioned idea. We performed numerical experiments in order to compare the proposed algorithm with the algorithm of enumeration method, and calculated the order of the computation time of these two algorithms. The numerical experiments showed that the proposed algorithm was more efficiently than the algorithm of enumeration method.
Katsuyuki YAMAMOTO Tadashi KAWAI Akira ENOKIHARA Tetsuya KAWANISHI
Optical single sideband (SSB) modulation with the Mach-Zehnder (MZ) interferometer was realized by integrating the modulation electrode with the branch-line coupler (BLC) as a 90-degree hybrid onto the modulator substrate. In this paper, BLCs of the microsrtip-line structure were miniaturized on modulator substrates, LiNbO3 (LN), to realize more compact optical SSB modulators. We introduced two techniques of miniaturizing the BLC, one is using periodically installed open-circuited stabs and the other is installing series capacitors. Compared with a conventional pattern of the BLC, an area of the miniaturized BLC by using periodically installed open-circuited stubs was reduced to about 50%, and that by installing series capacitors was done to about 60%. The operation of these miniaturized BLCs was experimentally confirmed as the 90-degree hybrid at around 10GHz. Output ports of each miniaturized BLC were directly connected with the modulation electrode on the modulator substrate. Thereby, we fabricated two types of compact SSB modulators for 1550nm light wavelength. In the experiments, the optical SSB modulation was successfully confirmed by the output light spectra and the sideband suppression ratio of more than 30dB were observed.
Yoshio SHIMOMURA Hiroki YAMAMOTO Hayato USUI Ryotaro KOBAYASHI Hajime SHIMADA
Modern processors use Branch Target Buffer (BTB)[1] to relax control dependence. Unfortunately, the energy consumption of the BTB is high. In order to effectively fetch instructions, it is necessary to perform a branch prediction at the fetch stage, regardless of whether the fetched instruction is a branch or a nonbranch. Therefore, the number of accesses to the BTB is large, and the energy consumption of the BTB is high. However, accesses from nonbranches to the BTB waste energy. In this paper, we focus on accesses from nonbranches to the BTB, which we call useless accesses from a viewpoint of power. For reducing energy consumption without performance loss, we present a method that reduces useless accesses by using information that indicates whether a fetched instruction is a branch or not. To realize the above approach, we propose a branch bit called B-Bit. A B-Bit is associated with an instruction and indicates whether it is a branch or not. A B-Bit is available at the beginning of the fetch stage. If a B-Bit is “1” signifying a branch, the BTB is accessed. If a B-Bit is “0” signifying a nonbranch, the BTB is not accessed. The experimental results show that the total energy consumption can be reduced by 54.3% without performance loss.
Xianshi JING Sheng SUN Lei ZHU
A miniaturized patch hybrid coupler with arbitrary power ratio and impedance transformation is proposed and designed by loading a pair of asymmetric cross slots on a squared patch resonator. To obtain the arbitrary power ratio and impedance transformation, the rectangular size of stepped slot ends should be well designed to be asymmetry and thus to obtain the different inductive loadings along two current paths. Theoretically, the equivalent transmission line model is first developed to understand the physical relationship between the patch and traditional branch-line hybrids. The matching/isolation and power ratio conditions are then derived at center frequency. By following a detailed design guideline, a prototype of the hybrid with 1:2 power ratio and 1:1.3 impedance transformation is designed and fabricated at 4.2 GHz. The measured results show a good agreement with simulated results, where the measured -10 dB impedance bandwidth achieves 18% and the bandwidth of 90°±6° phase difference is about 35% in a frequency range from 3.5 GHz to 5 GHz.
Hiroshi SHIMIZU Hitoshi ASAEDA Masahiro JIBIKI Nozomu NISHINAGA
How to retrieve the closest content from an in-network cache is one of the most important issues in Information-Centric Networking (ICN). This paper proposes a novel content discovery scheme called Local Tree Hunting (LTH). By adding branch-cast functionality to a local tree for content requests to a Content-Centric Network (CCN) response node, the discovery area for caching nodes expands. Since the location of such a branch-casting node moves closer to the request node when the content is more widely cached, the discovery range, i.e. the branch size of the local tree, becomes smaller. Thus, the discovery area is autonomously adjusted depending on the content dissemination. With this feature, LTH is able to find the “almost true closest” caching node without checking all the caching nodes in the in-network cache. The performance analysis employed in Zipf's law content distribution model and which uses the Least Recently Used eviction rule shows the superiority of LTH with respect to identifying the almost exact closest cache.
Ichiro TOYOSHIMA Shota NAKANO Shingo YAMAGUCHI
In this paper, we proposed reduction operators of timed Petri net for efficient model checking. Timed Petri nets are used widely for modeling and analyzing systems which include time concept. Analysis of the system can be done comprehensively with model checking, but there is a state-space explosion problem. Therefore, previous researchers proposed reduction methods and translation methods to timed automata to perform efficient model checking. However, there is no reduction method which consider observability and there is a trade-off between the amount of description and the size of state space. In this paper, first, we have defined a concept of timed behavioral inheritance. Next, we have proposed reduction operators of timed Petri nets based on timed behavioral inheritance. Then, we have applied our proposed operators to an artificial timed Petri net. Moreover, the results show that the reduction operators which consider observability can reduce the size of state space of the original timed Petri nets within the experiment.
This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 235 and 236, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2101 and 2158, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.
Etsuji TOMITA Yoichi SUTANI Takanori HIGASHI Mitsuo WAKATSUKI
Many problems can be formulated as maximum clique problems. Hence, it is highly important to develop algorithms that can find a maximum clique very fast in practice. We propose new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, pp.95–111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Extensive computational experiments confirm the superiority of MCS over MCR and other existing algorithms. It is faster than the other algorithms by orders of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graph. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs. This paper demonstrates in detail the effectiveness of each new techniques in MCS, as well as the overall contribution.
Huiyun JING Qi HAN Xin HE Xiamu NIU
We propose a novel threshold-free salient object detection approach which integrates both saliency density and edge response. The salient object with a well-defined boundary can be automatically detected by our approach. Saliency density and edge response maximization is used as the quality function to direct the salient object discovery. The global optimal window containing a salient object is efficiently located through the proposed saliency density and edge response based branch-and-bound search. To extract the salient object with a well-defined boundary, the GrabCut method is applied, initialized by the located window. Experimental results show that our approach outperforms the methods only using saliency or edge response and achieves a comparable performance with the best state-of-the-art method, while being without any threshold or multiple iterations of GrabCut.
A workflow net (WF-net for short) is a Petri net which represents a workflow. There are two important subclasses of WF-nets: extended free-choice (EFC for short) and well-structured (WS for short). It is known that most actual workflows can be modeled as EFC WF-nets; Acyclic WS is a subclass of acyclic EFC but has more analysis methods. An acyclic EFC WF-net may be transformed to an acyclic WS WF-net without changing the external behavior of the net. We name such a transformation Acyclic EFC WF-net refactoring. We give a formal definition of acyclic EFC WF-net refactoring problem. We also give a necessary condition and a sufficient condition for solving the problem. Those conditions can be checked in polynomial time. These result in the enhancement of the analysis power of acyclic EFC WF-nets.
Chia-Hao KU Hsien-Wen LIU Yu-Shu LIN Kuei-Yi LIN Pao-Jen WANG
A planar miniaturized branch-line coupler with harmonic suppression property for UHF band applications is presented in this paper. By properly synthesizing the LC-tanks that employ artificial transmission lines, two pairs of quarter-wavelength branch-lines to respectively meet characteristic impedances of 35.4 and 50 ohms can be obtained with the coupler. For the operating band, it can achieve good 3 dB power division with a 90° phase difference in the outputs of the through and coupled arms. The coupler also has a small area of 20.5(L)18(W) mm2, corresponding to 0.11 λg0.1 λg at 922 MHz. Compared with conventional couplers, the proposed design not only offers a wide bandwidth of more than 230 MHz within 1° or 1 dB, but also works with additional harmonic suppression for achieving better performance. Therefore, the proposed branch-line coupler with a compact size is well suitable for power division application.
Sinhyung JEON Hyengcheul CHOI Hyeongdong KIM
A planar inverted-E (PIE) antenna that can achieve a wide impedance bandwidth is proposed. The antenna is realized by inserting a branch capacitance between the feed line and the shorting pin of a conventional planar inverted-F antenna (PIFA). Such a modification significantly enhanced the impedance bandwidth while maintaining the antenna size. The proposed antenna possesses a very wide impedance bandwidth of 1250 MHz (1650-2900 MHz) at a voltage standing wave ratio (VSWR) <3. In addition, good radiation patterns were obtained at the desired frequency bands.
Shunsuke HORII Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP). Since it is an NP-hard problem in general, there are many researches about the algorithms to approximately solve the problem. One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al. LP decoding is based on the LP relaxation, which is a method to approximately solve the ILP corresponding to the ML decoding problem. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed by Taghavi et al. and Yang et al., respectively. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-and-bound methods. The branch-and-cut method is widely used to solve ILP, however, it is unobvious that the method works well for the ML decoding problem. In this paper, we show that the branch-and-cut method is certainly effective for the ML decoding problem. Furthermore the branch-and-cut method consists of some technical components and the performance of the algorithm depends on the selection of these components. It is important to consider how to select the technical components in the branch-and-cut method. We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations.
Hiroki NAKAHARA Tsutomu SASAO Munehiro MATSUURA Yoshifumi KAWAMURA
The parallel branching program machine (PBM128) consists of 128 branching program machines (BMs) and a programmable interconnection. To represent logic functions on BMs, we use quaternary decision diagrams. To evaluate functions, we use 3-address quaternary branch instructions. We realized many benchmark functions on the PBM128, and compared its memory size, computation time, and power consumption with the Intel's Core2Duo microprocessor. The PBM128 requires approximately a quarter of the memory for the Core2Duo, and is 21.4-96.1 times faster than the Core2Duo. It dissipates a quarter of the power of the Core2Duo. Also, we realized packet filters such as an access controller and a firewall, and compared their performance with software on the Core2Duo. For these packet filters, the PBM128 requires approximately 17% of the memory for the Core2Duo, and is 21.3-23.7 times faster than the Core2Duo.
Tsutomu SASAO Hiroki NAKAHARA Munehiro MATSUURA Yoshifumi KAWAMURA Jon T. BUTLER
This paper first reviews the trends of VLSI design, focusing on the power dissipation and programmability. Then, we show the advantage of Quarternary Decision Diagrams (QDDs) in representing and evaluating logic functions. That is, we show how QDDs are used to implement QDD machines, which yield high-speed implementations. We compare QDD machines with binary decision diagram (BDD) machines, and show a speed improvement of 1.28-2.02 times when QDDs are chosen. We consider 1-and 2-address BDD machines, and 3- and 4-address QDD machines, and we show a method to minimize the number of instructions.
Tadashi KAWAI Miku NAKAMURA Isao OHTA Akira ENOKIHARA
This paper treats a band-broadening design technique of a dual-band branch-line coupler with matching networks composed of an impedance step and a short-circuited stub based on the equivalent admittance approach. By replacing each right-handed transmission line (RH-TL) with a composite right/left-handed transmission line (CRLH-TL), very flat couplings over a relative bandwidth of about 10% can be obtained at two arbitrary operating frequencies in comparison with previous CRLH-TLs branch-line couplers. Furthermore, by adding periodical open-circuited stubs into RH-TLs of the designed CRLH-TLs branch-line coupler with matching networks, the entire size of the coupler can be reduced to about 50%. Verification of these band-broadening and size-reduction design techniques can be also shown by an electromagnetic simulation and experiment.
Teruyoshi ZENMYO Takashi KOBAYASHI Motoshi SAEKI
One of the critical issue in framework-based software development is a huge introduction cost caused by technical gap between developers and users of frameworks. This paper proposes a technique for deriving framework usages to implement a given requirements specification. By using the derived usages, the users can use the frameworks without understanding the framework in detail. Requirements specifications which describe definite behavioral requirements cannot be related to frameworks in as-is since the frameworks do not have definite control structure so that the users can customize them to suit given requirements specifications. To cope with this issue, a new technique based on satisfiability problems (SAT) is employed to derive the control structures of the framework model. In the proposed technique, requirements specifications and frameworks are modeled based on Labeled Transition Systems (LTSs) with branch conditions represented by predicates. Truth assignments of the branch conditions in the framework models are not given initially for representing the customizable control structure. The derivation of truth assignments of the branch conditions is regarded as the SAT by assuming relations between termination states of the requirements specification model and ones of the framework model. This derivation technique is incorporated into a technique we have proposed previously for relating actions of requirements specifications to ones of frameworks. Furthermore, this paper discuss a case study of typical use cases in e-commerce systems.
This paper presents a numerical approach to the time-domain analysis of N-branch-line couplers. The approach is based on the modified central difference (MCD) method combined with internal boundary treatments, which consist of the time-domain scattering matrix for the three-port junction discontinuity. The behavior of the signal propagation including multiple reflections on the N-branch-line coupler with and without line loss is analyzed and demonstrated in the time domain. Additionally, the S-parameters obtained from Gaussian pulse responses of the N-branch-line directional couplers are shown. The simulated results are in good agreement with those of the commercial simulator.
Teng LIN Jianhua FENG Dunshan YU
A novel application-dependent interconnect testing scheme of Xilinx Field Programmable Gate Arrays (FPGAs) based on line branches partitioning is presented. The targeted line branches of the interconnects in FPGAs' Application Configurations (ACs) are partitioned into multiple subsets, so that they can be tested with compatible Configurable Logic Blocks (CLBs) configurations in multiple Test Configurations (TCs). Experimental results show that for ISCAS89 and ITC99 benchmarks, this scheme can obtain a stuck-at fault coverage higher than 99% in less than 11 TCs.