Marc ALBRECHT Andreas KARRENBAUER Tobias JUNG Chihao XU
We consider the backlight calculation of local dimming as an optimization problem. The luminance produced by many LEDs at each pixel considered is calculated which should cover the gray value of each pixel, while the sum of LED currents is to be minimized. For this purpose a specific approach called as "Sorted Sector Covering" (SSC) was developed and is described in this paper. In our pre-processing unit called condenser the source image is reduced to a matrix of much lower resolution so that the computation effort of the SSC algorithm is drastically reduced. During this preprocessing phase, filter functions can be integrated so that a further reduction of the power consumption is achieved. Our processing system allows high power saving and high visual quality at low processor cost. We approach the local dimming problem in the physical viewing direction -- from LED to pixel. The luminance for the pixel is based on the light spread function (LSF) and the PWM values of the LEDs. As the physical viewing direction is chosen, this method is universal and can be applied for any kind of LED arrangement -- direct-lit as well as edge-lit. It is validated on prototypes, e.g., a locally dimmed edge-lit TV.
Recently, Mooij et al. proposed new sufficient conditions for convergence of the sum-product algorithm, and it was also shown that if the factor graph is a tree, Mooij's sufficient condition for convergence is always activated. In this letter, we show that the converse of the above statement is also true under some assumption, and that the assumption holds for the sum-product decoding. These newly obtained fact implies that Mooij's sufficient condition for convergence of the sum-product decoding is activated if and only if the factor graph of the a posteriori probability of the transmitted codeword is a tree.
Let T be a tree with n nodes, in which each edge is associated with a length and a weight. The density-constrained longest (heaviest) path problem is to find a path of T with maximum path length (weight) whose path density is bounded by an upper bound and a lower bound. The path density is the path weight divided by the path length. We show that both problems can be solved in optimal O(n log n) time.
Hsien-Cheng TSENG Jibin HORNG Chieh HU Seth TSAU
We propose a new parameter-extraction approach based on a mixed-mode genetic algorithm (GA), including the efficient search-space separation and local-minima-convergence prevention process. The technique, substantially extended from our previous work, allows the designed figures-of-merit, such as internal quantum efficiency (ηi) as well as transparency current density (Jtr) of lasers and minimum noise figure (NFmin) as well as associated available gain (GA,assoc) of low-noise amplifiers (LNAs), extracted by an analytical equation-based methodology combined with an evolutionary numerical tool. Extraction results, which agree well with actually measured data, for both state-of-the-art InGaAs quantum-well lasers and advanced SiGe LNAs are presented for the first time to demonstrate this multi-parameter analysis and high-accuracy optimization.
In this work, a high performance LDPC decoder architecture is presented. It is a partially-parallel architecture for low-complexity consideration. In order to eliminate the idling time and hardware complexity in conventional partially-parallel decoders, the decoding process, decoder architecture and memory structure are optimized. Particularly, the parity-check matrix is optimally partitioned into four unequal sub-matrices that lead to high efficiency in hardware sharing. As a result, it can handle two different codewords simultaneously with 100% hardware utilization. Furthermore, for minimizing the performance loss due to round-off errors in fixed-point implementations, the well-known modified min-sum decoding algorithm is enhanced by our recently proposed high-performance CMVP decoding algorithm. Overall, the proposed decoder has high throughput, low complexity, and good BER performances. In the circuit implementation example of the (576,288) parity check matrix for IEEE 802.16e standard, the decoder achieves a data rate of 5.5 Gbps assuming 10 decoding iterations and 7 quantization bits, with a small area of 653 K gates, based on UMC 90 nm process technology.
Hiroyuki OKUNO Yoshiko HANADA Mitsuji MUNEYASU Akira ASANO
In this paper we propose an unsupervised method of optimizing structuring elements (SEs) used for impulse noise reduction in texture images through the opening operation which is one of the morphological operations. In this method, a genetic algorithm (GA), which can effectively search wide search spaces, is applied and the size of the shape of the SE is included in the design variables. Through experiments, it is shown that our new approach generally outperforms the conventional method.
Makoto YAMADA Masashi SUGIYAMA Gordon WICHERN Jaak SIMM
Estimating the ratio of two probability density functions (a.k.a. the importance) has recently gathered a great deal of attention since importance estimators can be used for solving various machine learning and data mining problems. In this paper, we propose a new importance estimation method using a mixture of probabilistic principal component analyzers. The proposed method is more flexible than existing approaches, and is expected to work well when the target importance function is correlated and rank-deficient. Through experiments, we illustrate the validity of the proposed approach.
Nazmat SURAJUDEEN-BAKINDE Xu ZHU Jingbo GAO Asoke K. NANDI Hai LIN
In this paper, we propose a genetic algorithm (GA) based equalization approach for direct sequence ultra-wideband (DS-UWB) wireless communication systems, where the GA is combined with a RAKE receiver to combat the inter-symbol interference (ISI) due to the frequency selective nature of UWB channels for high data rate transmission. The proposed GA based equalizer outperforms significantly the RAKE and the RAKE-minimum mean square error (MMSE) receivers according to results obtained from intensive simulation work. The RAKE-GA receiver also provides bit-error-rate (BER) performance very close to that of the optimal RAKE-maximum likelihood detection (MLD) approach, while offering a much lower computational complexity.
For optimization problems with irregular and complex multimodal landscapes, Estimation of Distribution Algorithms (EDAs) suffer from the drawback of premature convergence similar to other evolutionary algorithms. In this paper, we propose an adaptive niching EDA based on Affinity Propagation (AP) clustering analysis. The AP clustering is used to adaptively partition the niches and mine the searching information from the evolution process. The obtained information is successfully utilized to improve the EDA performance by using a balance niching searching strategy. Two different categories of optimization problems are used to evaluate the proposed adaptive niching EDA. The first one is solving three benchmark functional multimodal optimization problems by a continuous EDA based on single Gaussian probabilistic model; the other one is solving a real complicated discrete EDA optimization problem, the HP model protein folding based on k-order Markov probabilistic model. Simulation results show that the proposed adaptive niching EDA is an efficient method.
This paper presents an approach for improving proximity and diversity in multiobjective evolutionary algorithms (MOEAs). The idea is to discover new nondominated solutions in the promising area of search space. It can be achieved by applying mutation only to the most converged and the least crowded individuals. In other words, the proximity and diversity can be improved because new nondominated solutions are found in the vicinity of the individuals highly converged and less crowded. Empirical results on multiobjective knapsack problems (MKPs) demonstrate that the proposed approach discovers a set of nondominated solutions much closer to the global Pareto front while maintaining a better distribution of the solutions.
Chien-Ning CHEN Sung-Ming YEN SangJae MOON
Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an n-bit NAF recoded scalar is n/3, and an exhaustive search among the 2n/3 candidates is required. This paper shows that in a left-to-right NAF recoded or a left-to-right 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2n/3 to 22n/9 and 20.19n respectively for the cases of NAF and sliding window method.
In a ZigBee network, a finite address space is allocated to every potential parent device and a device may disallow a join request once this address space is exhausted. When a new node (child) requests to a coordinator (parent) to join a ZigBee network, the coordinator checks its address space. If it has sufficient address space, the coordinator accepts the new node as its child in the ZigBee network. If the new node has router capability (JoinAsRouter), it becomes a router in the ZigBee network. However, this association procedure makes ZigBee networks inefficient for routing, because the coordinator checks only the maximum and current numbers of child nodes. In the worst case, the network will be arranged so that the router nodes are crowded in the network. Therefore, we propose the KMCD-IME (Keeping the Maximum Communication Distance and Initial Mutual Exclusion among router nodes) algorithm with two additional conditions when a new node joins the ZigBee network. The first condition maintains the maximum communication distance between the new node and the would-be parent node. The second condition is the Initial Mutual Exclusion among router nodes. The router nodes are evenly spread across the network by KMCD-IME and an effective routing topology is formed. Therefore, the KMCD-IME algorithm extends the lifetime of the ZigBee network.
Seongyong AHN Hyejeong HONG HyunJin KIM Jin-Ho AHN Dongmyong BAEK Sungho KANG
This paper proposes a new pattern matching architecture with multi-character processing for deep packet inspection. The proposed pattern matching architecture detects the start point of pattern matching from multi-character input using input text alignment. By eliminating duplicate hardware components using process element tree, hardware cost is greatly reduced in the proposed pattern matching architecture.
Pham Thanh GIANG Kenji NAKAGAWA
The IEEE 802.11 MAC standard for wireless ad hoc networks adopts Binary Exponential Back-off (BEB) mechanism to resolve bandwidth contention between stations. BEB mechanism controls the bandwidth allocation for each station by choosing a back-off value from one to CW according to the uniform random distribution, where CW is the contention window size. However, in asymmetric multi-hop networks, some stations are disadvantaged in opportunity of access to the shared channel and may suffer severe throughput degradation when the traffic load is large. Then, the network performance is degraded in terms of throughput and fairness. In this paper, we propose a new cross-layer scheme aiming to solve the per-flow unfairness problem and achieve good throughput performance in IEEE 802.11 multi-hop ad hoc networks. Our cross-layer scheme collects useful information from the physical, MAC and link layers of own station. This information is used to determine the optimal Contention Window (CW) size for per-station fairness. We also use this information to adjust CW size for each flow in the station in order to achieve per-flow fairness. Performance of our cross-layer scheme is examined on various asymmetric multi-hop network topologies by using Network Simulator (NS-2).
Novel thermopiles based on modulation doped AlGaAs/InGaAs, AlGaN/GaN, and ZnMgO/ZnO heterostructures are proposed and designed for the first time, for uncooled infrared image sensor application. These devices are expected to offer high performances due to both the superior Seebeck coefficient and the excellently high mobility of 2DEG and 2DHG due to high purity channel layers at the heterojunction interface. The AlGaAs/InGaAs thermopile has the figure-of-merit Z of as large as 1.110-2/K (ZT = 3.3 over unity at T = 300 K), and can be realized with a high responsivity R of 15,200 V/W and a high detectivity D* of 1.8109 cmHz1/2/W with uncooled low-cost potentiality. The AlGaN/GaN and the ZnMgO/ZnO thermopiles have the advantages of high sheet carrier concentration due to their large polarization charge effects (spontaneous and piezo polarization charges) as well as of a high Seebeck coefficient due to their strong phonon-drag effect. The high speed response time τ of 0.9 ms with AlGaN/GaN, and also the lower cost with ZnMgO/ZnO thermopiles can be realized. The modulation-doped heterostructure thermopiles presented here are expected to be used for uncooled infrared image sensor applications, and for monolithic integrations with other photon detectors such as InGaAs, GaN, and ZnO PiN photodiodes, as well as HEMT functional integrated circuit devices.
Yusuke IKAWA Yorihide YUASA Cheng-Yu HU Jin-Ping AO Yasuo OHNO
Drain collapse in AlGaN/GaN HFET is analyzed using a two-dimensional device simulator. Two-step saturation is obtained, assuming hole-trap type surface states on the AlGaN surface and a short negative-charge-injected region at the drain side of the gate. Due to the surface electric potential pinning by the surface traps, the negative charge injected region forms a constant potential like in a metal gate region and it acts as an FET with a virtual gate. The electron concentration profile reveals that the first saturation occurs by pinch-off in the virtual gate region and the second saturation occurs by the pinch-off in the metal gate region. Due to the short-channel effect of the virtual gate FET, the saturation current increases until it finally reaches the saturation current of the intrinsic metal gate FET. Current collapses with current degradation at the knee voltage in the I-V characteristics can be explained by the formation of the virtual gate.
Recently, the importance of data sharing structures in autonomous distributed networks has been increasing. A wireless sensor network is used for managing distributed data. This type of distributed network requires effective information exchanging methods for data sharing. To reduce the traffic of broadcasted messages, reduction of the amount of redundant information is indispensable. In order to reduce packet loss in mobile ad-hoc networks, QoS-sensitive routing algorithm have been frequently discussed. The topology of a wireless network is likely to change frequently according to the movement of mobile nodes, radio disturbance, or fading due to the continuous changes in the environment. Therefore, a packet routing algorithm should guarantee QoS by using some quality indicators of the wireless network. In this paper, a novel information exchanging algorithm developed using a hash function and a Boolean operation is proposed. This algorithm achieves efficient information exchanges by reducing the overhead of broadcasting messages, and it can guarantee QoS in a wireless network environment. It can be applied to a routing algorithm in a mobile ad-hoc network. In the proposed routing algorithm, a routing table is constructed by using the received signal strength indicator (RSSI), and the neighborhood information is periodically broadcasted depending on this table. The proposed hash-based routing entry management by using an extended MAC address can eliminate the overhead of message flooding. An analysis of the collision of hash values contributes to the determination of the length of the hash values, which is minimally required. Based on the verification of a mathematical theory, an optimum hash function for determining the length of hash values can be given. Simulations are carried out to evaluate the effectiveness of the proposed algorithm and to validate the theory in a general wireless network routing algorithm.
Cheng-Yu HU Katsutoshi NAKATANI Hiroji KAWAI Jin-Ping AO Yasuo OHNO
To improve the high voltage performance of AlGaN/GaN heterojunction field effect transistors (HFETs), we have fabricated AlGaN/GaN HFETs with p-GaN epi-layer on sapphire substrate with an ohmic contact to the p-GaN (p-sub HFET). Substrate bias dependent threshold voltage variation (VT-VSUB) was used to directly determine the doping concentration profile in the buffer layer. This VT-VSUB method was developed from Si MOSFET. For HFETs, the insulator is formed by epitaxially grown and heterogeneous semiconductor layer while for Si MOSFETs the insulator is amorphous SiO2. Except that HFETs have higher channel mobility due to the epitaxial insulator/semiconductor interface, HFETs and Si MOSFETs are basically the same in the respect of device physics. Based on these considerations, the feasibility of this VT-VSUB method for AlGaN/GaN HFETs was discussed. In the end, the buffer layer doping concentration was measured to be 21017 cm-3, p-type, which is well consistent with the Mg concentration obtained from secondary ion mass spectroscopy (SIMS) measurement.
Takeyuki TAMURA Tatsuya AKUTSU
A reaction cut is a set of chemical reactions whose deletion blocks the operation of given reactions or the production of given chemical compounds. In this paper, we study two problems ReactionCut and MD-ReactionCut for calculating the minimum reaction cut of a metabolic network under a Boolean model. These problems are based on the flux balance model and the minimal damage model respectively. We show that ReactionCut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (Kout) is one. We also present O(1.822n), O(1.959n) and o(2n) time algorithms for MD-ReactionCut with Kout=2, 3, k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for ReactionCut if there is no directed cycle. Furthermore, we present a 2O((log n)) time algorithm, which is faster than O((1+ε)n) for any positive constant ε, for the planar case of MD-ReactionCut under a reasonable constraint utilizing Lipton and Tarjan's separator algorithm.
In this paper, I will show how multi-valued logics are used for model checking. Model checking is an automatic technique to analyze correctness of hardware and software systems. A model checker is based on a temporal logic or a modal fixed point logic. That is to say, a system to be checked is formalized as a Kripke model, a property to be satisfied by the system is formalized as a temporal formula or a modal formula, and the model checker checks that the Kripke model satisfies the formula. Although most existing model checkers are based on 2-valued logics, recently new attempts have been made to extend the underlying logics of model checkers to multi-valued logics. I will summarize these new results.