In this paper, we present an average-case efficient algorithm to resolve the problem of determining whether two Boolean functions in trace representation are identical. Firstly, we introduce a necessary and sufficient condition for null Boolean functions in trace representation, which can be viewed as a generalization of the well-known additive Hilbert-90 theorem. Based on this condition, we propose an algorithmic method with preprocessing to address the original problem. The worst-case complexity of the algorithm is still exponential; its average-case performance, however, can be improved. We prove that the expected complexity of the refined procedure is O(n), if the coefficients of input functions are chosen i.i.d. according to the uniform distribution over F2n; therefore, it performs well in practice.
Trung Hieu BUI Takeshi SAITOH Eitaku NOBUYAMA
This paper proposes a vanishing point-based road detection method. Firstly, a vanishing point is detected using a texture-based method proposed in a recent study. After that, a histogram is generated for detecting two road borders. The road area is defined as the region between the two road borders and below the vanishing point. The experimental results demonstrate that our method performs well in general road images.
Jongwon SEOK Taehwan KIM Keunsung BAE
This letter deals with angular position classification using the synthesized active sonar returns from targets. For the synthesis of active sonar returns, we synthesized active sonar returns based on ray tracing algorithm for 3D highlight models. Then, a fractional Fourier transform (FrFT) was applied to the sonar returns to extract the angular position information depending on the target aspect by utilizing separation capability of the time-delayed combination of linear frequency modulated (LFM) signals in the FrFT domain. With the FrFT-based features, three different target angular positions were classified using neural networks.
Masafumi TAKEMATSU Junichi HONDA Yuki KIMURA Kazunori UCHIDA
This paper is concerned with a method to reduce the computation time of the Discrete Ray Tracing Method (DRTM) which was proposed to numerically analyze electromagnetic fields above Random Rough Surfaces (RRSs). The essence of DRTM is firstly to search rays between source and receiver and secondly to compute electric fields based on the traced rays. In the DRTM, the method discretizes not only RRSs but also ray tracing procedure. In order to reduce computation time for ray searching, the authors propose to modify the conventional algorithm discretizing RRSs with equal intervals to a new one which discretizes them with unequal intervals according to their profiles. The authors also use an approximation of Fresnel function which enables us to reduce field computation time. The authors discuss the reduction rate for computation time of the DRTM from the numerical view points of ray searching and field computation. Finally, this paper shows how much computation time is reduced by the new method.
Osamu TODA Masahiro YUKAWA Shigenobu SASAKI Hisakazu KIKUCHI
We propose a novel adaptive filtering scheme named metric-combining normalized least mean square (MC-NLMS). The proposed scheme is based on iterative metric projections with a metric designed by combining multiple metric-matrices convexly in an adaptive manner, thereby taking advantages of the metrics which rely on multiple pieces of information. We compare the improved PNLMS (IPNLMS) algorithm with the natural proportionate NLMS (NPNLMS) algorithm, which is a special case of MC-NLMS, and it is shown that the performance of NPNLMS is controllable with the combination coefficient as opposed to IPNLMS. We also present an application to an acoustic echo cancellation problem and show the efficacy of the proposed scheme.
Chungsoo LIM Soojeong LEE Jae-Hun CHOI Joon-Hyuk CHANG
In this letter, we propose a simple but effective technique that improves statistical model-based voice activity detection (VAD) by both reducing computational complexity and increasing detection accuracy. The improvements are made by applying Taylor series approximations to the exponential and logarithmic functions in the VAD algorithm based on an in-depth analysis of the algorithm. Experiments performed on a smartphone as well as on a desktop computer with various background noises confirm the effectiveness of the proposed technique.
Compressive sensing is a promising technique in data acquisition field. A central problem in compressive sensing is that for a given sparse signal, we wish to recover it accurately, efficiently and stably from very few measurements. Inspired by mathematical analysis, we introduce a combining scheme between stability and robustness in reconstruction problems using compressive sensing. By choosing appropriate parameters, we are able to construct a condition for reconstruction map to perform properly.
Yusuke MIZUNO Kazunobu KONDO Takanori NISHINO Norihide KITAOKA Kazuya TAKEDA
Blind source separation is a technique that can separate sound sources without such information as source location, the number of sources, and the utterance content. Multi-channel source separation using many microphones separates signals with high accuracy, even if there are many sources. However, these methods have extremely high computational complexity, which must be reduced. In this paper, we propose a computational complexity reduction method for blind source separation based on frequency domain independent component analysis (FDICA) and examine temporal data that are effective for source separation. A frame with many sound sources is effective for FDICA source separation. We assume that a frame with a low kurtosis has many sound sources and preferentially select such frames. In our proposed method, we used the log power spectrum and the kurtosis of the magnitude distribution of the observed data as selection criteria and conducted source separation experiments using speech signals from twelve speakers. We evaluated the separation performances by the signal-to-interference ratio (SIR) improvement score. From our results, the SIR improvement score was 24.3dB when all the frames were used, and 23.3dB when the 300 frames selected by our criteria were used. These results clarified that our proposed selection criteria based on kurtosis and magnitude is effective. Furthermore, we significantly reduced the computational complexity because it is proportional to the number of selected frames.
Shuichi NAGASAWA Kenji HINODE Tetsuro SATOH Mutsuo HIDAKA Hiroyuki AKAIKE Akira FUJIMAKI Nobuyuki YOSHIKAWA Kazuyoshi TAKAGI Naofumi TAKAGI
We describe the recent progress on a Nb nine-layer fabrication process for large-scale single flux quantum (SFQ) circuits. A device fabricated in this process is composed of an active layer including Josephson junctions (JJ) at the top, passive transmission line (PTL) layers in the middle, and a DC power layer at the bottom. We describe the process conditions and the fabrication equipment. We use both diagnostic chips and shift register (SR) chips to improve the fabrication process. The diagnostic chip was designed to evaluate the characteristics of basic elements such as junctions, contacts, resisters, and wiring, in addition to their defect evaluations. The SR chip was designed to evaluate defects depending on the size of the SFQ circuits. The results of a long-term evaluation of the diagnostic and SR chips showed that there was fairly good correlation between the defects of the diagnostic chips and yields of the SRs. We could obtain a yield of 100% for SRs including 70,000JJs. These results show that considerable progress has been made in reducing the number of defects and improving reliability.
Christian Henry Wijaya OEY Sangman MOH
One of the most important requirements for a routing protocol in wireless body area networks (WBANs) is to lower the network's temperature increase. The temperature of a node is closely related to its activities. The proactive routing approach, which is used by existing routing protocols for WBANs, tends to produce a higher temperature increase due to more frequent activities, compared to the on-demand reactive routing approach. In this paper, therefore, we propose a reactive routing protocol for WBANs called priority-based temperature-aware routing (PTR). In addition to lowering the temperature increase, the protocol also recognizes vital nodes and prioritizes them so they are able to achieve higher throughput. Simulation results show that the PTR protocol achieves a 50% lower temperature increase compared to the conventional temperature-aware routing protocol and is able to improve throughput of vital nodes by 35% when the priority mode is enabled.
Mingfu XUE Wei LIU Aiqun HU Youdong WANG
Hardware Trojan (HT) has emerged as an impending security threat to hardware systems. However, conventional functional tests fail to detect HT since Trojans are triggered by rare events. Most of the existing side-channel based HT detection techniques just simply compare and analyze circuit's parameters and offer no signal calibration or error correction properties, so they suffer from the challenge and interference of large process variations (PV) and noises in modern nanotechnology which can completely mask Trojan's contribution to the circuit. This paper presents a novel HT detection method based on subspace technique which can detect tiny HT characteristics under large PV and noises. First, we formulate the HT detection problem as a weak signal detection problem, and then we model it as a feature extraction model. After that, we propose a novel subspace HT detection technique based on time domain constrained estimator. It is proved that we can distinguish the weak HT from variations and noises through particular subspace projections and reconstructed clean signal analysis. The reconstructed clean signal of the proposed algorithm can also be used for accurate parameter estimation of circuits, e.g. power estimation. The proposed technique is a general method for related HT detection schemes to eliminate noises and PV. Both simulations on benchmarks and hardware implementation validations on FPGA boards show the effectiveness and high sensitivity of the new HT detection technique.
Yoichi TOMIOKA Ryota TAKASU Takashi AOKI Eiichi HOSOYA Hitoshi KITAZAWA
Hardware acceleration is an essential technique for extracting and tracking moving objects in real time. It is desirable to design tracking algorithms such that they are applicable for parallel computations on hardware. Exclusive block matching methods are designed for hardware implementation, and they can realize detailed motion extraction as well as robust moving object tracking. In this study, we develop tracking hardware based on an exclusive block matching method on FPGA. This tracking hardware is based on a two-dimensional systolic array architecture, and can realize robust moving object extraction and tracking at more than 100 fps for QVGA images using the high parallelism of an exclusive block matching method, synchronous shift data transfer, and special circuits to accelerate searching the exclusive correspondence of blocks.
Yoshitaka TAKAHASHI Hiroshi SHIMADA Masaaki MAEZAWA Yoshinao MIZUGAKI
We present our design and operation of a 6-bit quasi-triangle voltage waveform generator comprising three circuit blocks; an improved variable Pulse Number Multiplier (variable-PNM), a Code Generator (CG), and a Double-Flux-Quantum Amplifier (DFQA). They are integrated into a single chip using a niobium Josephson junction technology. While the multiplication factor of our previous m-bit variable-PNM was limited between 2m-1 and 2m, that of the improved one is extended between 1 and 2m. Correct operations of the 6-bit variable-PNM are confirmed in low-speed testing with respect to the codes from the CG, whereas generation of a 6-bit, 0.20mVpp quasi-triangle voltage waveform is demonstrated with the 10-fold DFQA in high-speed testing.
Kanshiro KASHIKI I-Te LIN Tomoki SADA Toshihiko KOMINE Shingo WATANABE
This paper describes an analytical study of performance of a proposed signal detection scheme that will allow coexistence of an additional radio communication system (generally, secondary system) in the service area where the existing communication system (primary system) is operated. Its performance characteristics are derived by an analytical method based on stochastic theory, which is subsequently validated by software simulation. The main purpose of the detection scheme is to protect the primary system from the secondary system. In such a situation, the signals of the primary system and secondary system may be simultaneously received in the signal detector. One application of such a scheme is D-to-D (Device-to-Device) communication, whose system concept including the detection scheme is briefly introduced. For improved secondary signal detection, we propose the signal cancellation method of the primary system and the feature detection method of the secondary system signal. We evaluate the performance characteristics of the detection scheme in terms of “probability of correct detection”. We reveal that an undesired random component is produced in the feature detection procedure when two different signals are simultaneously received, which degrades the detection performance. Such undesired component is included in the analytical equations. We also clarify that the cancellation scheme improves the performance, when the power ratio of the primary signal to secondary signal is higher than 20-22dB.
Moving objects or more generally foreground objects are the simplest objects in the field of computer vision after the pixel. Indeed, a moving object can be defined by 4 integers only, either two pairs of coordinates or a pair of coordinates and the size. In fixed camera scenes, moving objects (or blobs) can be extracted quite easily but the methods to produce them are not able to tell if a blob corresponds to remaining background noise, a single target or if there is an occlusion between many target which are too close together thus creating a single blob resulting from the fusion of all targets. In this paper we propose an novel method to refine moving object detection results in order to get as many blobs as targets on the scene by using a tracking system for additional information. Knowing if a blob is at proximity of a tracker allows us to remove noise blobs, keep the rest and handle occlusions when there are more than one tracker on a blob. The results show that the refinement is an efficient tool to sort good blobs from noise blobs and accurate enough to perform a tracking based on moving objects. The tracking process is a resolution free system able to reach speed such as 20 000fps even for UHDTV sequences. The refinement process itself is in real time, running at more than 2000fps in difficult situations. Different tests are presented to show the efficiency of the noise removal and the reality of the independence of the refinement tracking system from the resolution of the videos.
Jianqiao WANG Yuehua LI Jianfei CHEN
Observed samples in wideband radar are always represented as nonlinear points in high dimensional space. In this paper, we consider the feature selection problem in the scenario of wideband radar target clustering. Inspired by manifold learning, we propose a novel feature selection algorithm, called Local Reconstruction Error Alignment (LREA), to select the features that can best preserve the underlying manifold structure. We first select the features that minimize the reconstruction error in every neighborhood. Then, we apply the alignment technique to extend the local optimal feature sequence to a global unique feature sequence. Experiments demonstrate the effectiveness of our proposed method.
A method for efficiently estimating the time-varying spectra of nonstationary autoregressive (AR) signals is derived using an indefinite matrix-based sliding window fast linear prediction (ISWFLP). In the linear prediction, the indefinite matrix plays a very important role in sliding an exponentially weighted finite-length window over the prediction error samples. The resulting ISWFLP algorithm successively estimates the time-varying AR parameters of order N at a computational complexity of O(N) per sample. The performance of the AR parameter estimation is superior to the performances of the conventional techniques, including the Yule-Walker, covariance, and Burg methods. Consequently, the ISWFLP-based AR spectral estimation method is able to rapidly track variations in the frequency components with a high resolution and at a low computational cost. The effectiveness of the proposed method is demonstrated by the spectral analysis results of a sinusoidal signal and a speech signal.
Shun-ichi AZUMA George J. PAPPAS
This paper addresses the discrete abstraction problem for stochastic nonlinear systems with continuous-valued state. The proposed solution is based on a function, called the bisimulation function, which provides a sufficient condition for the existence of a discrete abstraction for a given continuous system. We first introduce the bisimulation function and show how the function solves the problem. Next, a convex optimization based method for constructing a bisimulation function is presented. Finally, the proposed framework is demonstrated by a numerical simulation.
MIL-STD-188-220 standard specifies protocols for narrowband and voice-based tactical communication devices. However, the future tactical communication devices require broadband services for accurate command and control. In this letter, the enhancement for MIL-STD-188-220-based systems is proposed for use over wideband channels. Unlike the operation defined in the standard, transmissions in Bump-Slots uses P-Persistence method and give the higher p to stations experiencing longer delays. The proposed method is extensively evaluated and the performance enhancements are proved.
Lei SUN Zhenyu LIU Takeshi IKENAGA
Scalable Video Coding (SVC) is an extension of H.264/AVC, aiming to provide the ability to adapt to heterogeneous networks or requirements. It offers great flexibility for bitstream adaptation in multi-point applications such as videoconferencing. However, transcoding between SVC and AVC is necessary due to the existence of legacy AVC-based systems. The straightforward re-encoding method requires great computational cost, and delay-sensitive applications like videoconferencing require much faster transcoding scheme. This paper proposes a 3-stage fast SVC-to-AVC transcoder with medium-grain quality scalability (MGS) for videoconferencing applications. Hierarchical-P structured SVC bitstream is transcoded into IPPP structured AVC bitstream with multiple reference frames. In the first stage, mode decision is accelerated by proposed SVC-to-AVC mode mapping scheme. In the second stage, INTER motion estimation is accelerated by an optimized motion vector (MV) conjunction method to predict the MV with a reduced search range. In the last stage, hadamard-based all zero block (AZB) detection is utilized for early termination. Simulation results show that proposed transcoder achieves very similar coding efficiency to the optimal result, but with averagely 89.6% computational time saving.