Koji KOBAYASHI Shuichi MIYAZAKI Yasuo OKABE
The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. In this paper, we consider one of the most standard models, called multi-queue switches model. In this model, Albers et al. gave a lower bound , and Azar et al. gave an upper bound on the competitive ratio when m, the number of input ports, is large. They are tight, but there still remains a gap for small m. In this paper, we consider the case where m=2, namely, a switch is equipped with two ports, which is called a bicordal buffer model. We propose an online algorithm called Segmental Greedy Algorithm (SG) and show that its competitive ratio is at most ( 1.231), improving the previous upper bound by ( 1.286). This matches the lower bound given by Schmidt.
Kihun CHANG Sang il KWAK Young Joong YOON
In this paper, active frequency selective surfaces (FSS) having a squared aperture with a metal plate loading are described. Active FSS elements using switched PIN diodes are discussed with an equivalent circuit model. A unit cell consists of a square aperture element with metal island loading and one PIN diode placed at the upper gap, considering the vertical polarization. The electromagnetic properties of the active FSS structure are changed by applying dc bias to the substrate, and they can be estimated by the equivalent circuit model of the FSS structure and PIN diode. This active FSS design enables transmission to be switched on or off at 2.3 GHz, providing high transmission when the diodes are in an off state and high isolation when the diodes are on. The equivalent circuit model in the structure is investigated by analyzing transmission and reflection spectra. Measurements on active FSS are compared with numerical calculations. The experimentally observed frequency responses are also scrutinized.
Tatsunari HAMASAKI Taichiro MORIMUNE Hirotake KAJII Yutaka OHMORI
The characteristics of violet-sensitive organic photodetectors (OPDs) utilizing polyalkylfluorene and triplet materials have been studied as a host and a dopant material, respectively. For the photo absorption layer, poly(9,9-dioctylfluorene) [PFO] and a phosphorescent iridium complex (Iridium (III) bis(2-(4,6-difluorophenyl)pyridinato-N,C2) [FIrpic] or Iridium (III) bis(2-(2'-benzothienyl)pyridinato-N,C3')(acetyl-acetonate) [(btp)2Ir(acac)]) were used as a host and a dopant material, respectively. PFO: (btp)2Ir(acac) device showed less photocurrent than PFO device because (btp)2Ir(acac) enhances recombination of the photo generated carriers in the photo absorption layer. On the other hand, PFO : FIrpic device showed larger photocurrent than PFO device due to triplet energy transfer from FIrpic to PFO. A cutoff frequency of 20 MHz was observed using a sinusoidal modulated violet laser light illumination under the reverse bias of 8 V.
Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes L, P and PSPACE in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the L versus P problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log n) reversal complexity while all languages in L are computable within O(log n) reversal complexity.
Bansi Dhar MALHOTRA Nirmal PRABHAKAR Pratima R. SOLANKI
Nucleic acid sensor based on polyaniline has been fabricated by covalently immobilizing double stranded calf thymus (dsCT) DNA onto perchlorate (ClO- 4) doped polyaniline (PANI) film deposited onto indium-tin-oxide (ITO) glass plate using 1-(3-(dimethylamino) propyl)-3-ethylcarbodiimide hydrochloride (EDC)/N-hydroxyl succinimide (NHS) chemistry. These dsCT-DNA-PANI/ITO and PANI/ITO electrodes have been characterized using square wave voltammetry, electrochemical impedance, and Fourier-transform-infra-red (FTIR) measurements. This disposable dsCT-DNA-PANI/ITO bioelectrode is stable for about four months, can be used to detect arsenic trioxide (0.1 ppm) in 30 s.
Chenggao HAN Takeshi HASHIMOTO Naoki SUEHIRO
In approximately synchronous CDMA (AS-CDMA) systems, zero correlation zone (ZCZ) sequences are known as the sequences to eliminate co-channel and multi-path interferences. Therefore, numerous constructions of zero correlation zone (ZCZ) sequences have been introduced e.g. based on perfect sequences and complete complementary codes etc. However, the previous construction method which based on complete complementary code is lacking for merit figures when none of whose elements are zero. In this paper, a new construction method of ZCZ sequences based on complete complementary codes is proposed. By proposed method, non zero elements ZCZ sequences whose merit figure is greater than 1/2 are constructable.
A function F:F2n F2n is almost perfect nonlinear (APN) if, for every a 0, b in F2n, the equation F(x)+F(x+a)=b has at most two solutions in F2n. When used as an S-box in a block cipher, it contributes optimally to the resistance to differential cryptanalysis. The function F is almost bent (AB) if the minimum Hamming distance between all its component functions v F, v∈F2n
Jeong Ki KIM Hyunseuk YOO Moon Ho LEE
The weakness of implementation for LDPC encoder is that conventional binary Matrix Vector Multiplier has many clock cycles which lead to limited throughput. In this letter in order to construct efficient architecture, we target on IEEE 802.16e LDPC encoders. Over the standard H matrices with Circulant Permutation Matrices, we propose semi-parallel architecture by using cyclic right shift registers and exclusive-OR instead of complex Matrix Vector Multipliers. Proposed efficient encoder for IEEE 802.16e LDPC satisfies compact size and high throughput.
Keiichi SUEMITSU Toshiaki ITO Toshiki KANAMOTO Masayuki TERAI Satoshi KOTANI Shigeo SAWADA
This paper proposes a new parallel method of producing the adjacent net pair list from the LSI layouts, which is run on workstations connected with the network. The pair list contains pairs of adjacent nets and the probability of a bridging fault between them, and is used in fault diagnosis of LSIs. The proposed method partitions into regions each mask layer of the LSI layout, produces a pair list corresponding to each region in parallel and merges them into the entire pair list. It yields the accurate results, because it considers the faults between two wires containing different adjacent regions. The experimental results show that the proposed method has greatly reduced the processing time from more than 60 hrs. to 3 hrs. in case of 42M-gate LSIs.
This paper proposes an efficient design algorithm for power/ground (P/G) network synthesis with dynamic signal consideration, which is mainly caused by Ldi/dt noise and Cdv/dt decoupling capacitance (DECAP) current in the distribution network. To deal with the nonlinear global optimization under synthesis constraints directly, the genetic algorithm (GA) is introduced. The proposed GA-based synthesis method can avoid the linear transformation loss and the restraint condition complexity in current SLP, SQP, ICG, and random-walk methods. In the proposed Hybrid Grid Synthesis algorithm, the dynamic signal is simulated in the gene disturbance process, and Trapezoidal Modified Euler (TME) method is introduced to realize the precise dynamic time step process. We also use a hybrid-SLP method to reduce the genetic execute time and increase the network synthesis efficiency. Experimental results on given power distribution network show the reduction on layout area and execution time compared with current P/G network synthesis methods.
Tae Il BAE Jin Wook KIM Young Hwan KIM
As the semiconductor feature size decreases, the crosstalk due to the capacitive coupling of interconnects influences signal propagation delay more seriously. Moreover, the increase of the operating frequency further emphasizes the necessity of more accurate timing analysis. In this paper, we propose new gate models to calculate gate output waveforms under crosstalk effects, which can be used for gate-level delay estimation. We classify the operation modes of metal-oxide-semiconductor (MOS) devices of a gate into 3 regions, and then develop simple linear models for each region. In addition, we present a non-iterative gate modeling method that is more efficient than previous iterative methods. In the experiments, the proposed method exhibits a maximum error of 10.70% and an average error of 2.63% when it computes the 50% delays of two or three complementary MOS (CMOS) inverters driving parallel wires. In comparison, the existing method has a maximum error of 25.94% and an average error of 3.62% under these conditions.
Insoo KIM Jincheol YOO JongSoo KIM Kyusun CHOI
Threshold Inverter Quantization (TIQ) technique has been gaining its importance in high speed flash A/D converters due to its fast data conversion speed. It eliminates the need of resistor ladders for reference voltages generation which requires substantial power consumption. The key to TIQ comparators design is to generate 2n - 1 different sized TIQ comparators for an n-bit A/D converter. This paper presents a highly efficient TIQ comparator design methodology based on an analytical model as well as SPICE simulation experimental model. One can find any sets of TIQ comparators efficiently using the proposed method. A 6-bit TIQ A/D converter has been designed in a 0.18 µm standard CMOS technology using the proposed method, and compared to the previous measured results in order to verify the proposed methodology.
Sung Jun BAN Chang Woo LEE Sang Woo KIM
Recently, a data-selective method has been proposed to achieve low misalignment in affine projection algorithm (APA) by keeping the condition number of an input data matrix small. We present an improved method, and a complexity reduction algorithm for the APA with the data-selective method. Experimental results show that the proposed algorithm has lower misalignment and a lower condition number for an input data matrix than both the conventional APA and the APA with the previous data-selective method.
Kumiko MAEBASHI Nobuo SUEMATSU Akira HAYASHI
The mixture modeling framework is widely used in many applications. In this paper, we propose a component reduction technique, that collapses a Gaussian mixture model into a Gaussian mixture with fewer components. The EM (Expectation-Maximization) algorithm is usually used to fit a mixture model to data. Our algorithm is derived by extending mixture model learning using the EM-algorithm. In this extension, a difficulty arises from the fact that some crucial quantities cannot be evaluated analytically. We overcome this difficulty by introducing an effective approximation. The effectiveness of our algorithm is demonstrated by applying it to a simple synthetic component reduction task and a phoneme clustering problem.
Kenji ARAKI Fengchao XIAO Yoshio KAMI
To evaluate frequency-domain interference between orthogonally intersecting stripline geometries, a lumped mutual capacitance was incorporated into a circuit model, and then a simplified circuit was proposed in the previous paper. The circuit model was approximated from an investigation of the distribution of mutual capacitance but it has remained how the capacitance is approximated. In this paper, a technique using an error function is proposed for the problem. Then, the time-domain response in an analytical expression is studied using the simplified circuit model in a Laplace transformation to make the mechanism clear. Comparing the experimental and the computed results verifies the proposed models.
Won Joon LEE Jaeyoon LEE Dongweon YOON Sang Kyu PARK
In a multi-user orthogonal frequency division multiplexing (OFDM) system, efficient resource allocation is required to provide service to more users. In this letter, we propose an improved subcarrier allocation algorithm that can increase the spectral efficiency and the number of total transmission bits even if the number of users is too large. The proposed algorithm is divided into two stages. In the first stage, a group of users who are eligible for services is determined by using the bit error rate (BER), the users' minimum data rate requirement, and channel information. In the second stage, subcarriers are first allocated to the users on the basis of channel state, and then the reallocation is performed so that resource waste is minimized. We show that the proposed algorithm outperforms the conventional one on the basis of outage probability, spectral efficiency, and the number of total transmission bits through a computer simulation.
Wen JI Yuta ABE Takeshi IKENAGA Satoshi GOTO
In this paper, we propose a partially-parallel irregular LDPC decoder based on IEEE 802.11n standard targeting high throughput and small area applications. The design is based on a novel sum-delta message passing algorithm characterized as follows: (i) Decoding throughput is greatly improved by utilizing the difference value between the updated and the original value to remove redundant computations. (ii) Registers and memory are optimized to store only the frequently used messages to decrease the hardware cost. (iii) Techniques such as binary sorting, parallel column operation, high performance pipelining are used to further speed up the message passing procedure. The synthesis result in TSMC 0.18 CMOS technology demonstrates that for (648,324) irregular LDPC code, our decoder achieves 7.5X improvement in throughput, which reaches 402 Mbps at the frequency of 200 MHz, with 11% area reduction. The synthesis result also demonstrates the competitiveness to the fully-parallel regular LDPC decoders in terms of the tradeoff between throughput, area and power.
Takaaki MANAKA Motoharu NAKAO Eunju LIM Mitsumasa IWAMOTO
Time-resolved microscopic optical second harmonic generation (TRM-SHG) imaging measurement revealed quantitatively the potential drop at the electrode contact of pentacene field effect transistors (FET). An activation of the SH signal at the edge of Ag-source electrode indicates the presence of large potential drop at pentacene-Ag contact during device operation, whereas negligible potential drop was observed at pentacene-Au contact. These findings agree with the injection characteristics of electrodes owing to the relationship between the work function of the metal and the HOMO level of pentacene.
Kai YANG Jianping AN Xiangyuan BU Zhan XU
A novel algorithm for source location by utilizing the time-difference-of-arrival (TDOA) of a signal received at spatially separated sensors is proposed. The algorithm is based on the constrained total least-squares (CTLS) technique and gives an explicit solution. Simulation results demonstrate that the proposed algorithm has high location accuracy and its performance is close to the Cramer-Rao lower bound (CRLB).
Ali OZEN Ismail KAYA Birol SOYSAL
Because of the fact that mobile communication channel changes by time, it is necessary to employ adaptive channel equalizers in order to combat the distorting effects of the channel. Least Mean Squares (LMS) algorithm is one of the most popular channel equalization algorithms and is preferred over other algorithms such as the Recursive Least Squares (RLS) and Maximum Likelihood Sequence Estimation (MLSE) when simplicity is the dominant decision factor. However, LMS algorithm suffers from poor performance and convergence speed within the training period specified by most of the standards. The aim of this study is to improve the convergence speed and performance of the LMS algorithm by adjusting the step size using fuzzy logic. The proposed method is compared with the Channel Matched Filter-Decision Feedback Equalizer (CMF-DFE) [1] which provides multi path propagation diversity by collecting the energy in the channel, Minimum Mean Square Error-Decision Feedback Equalizer (MMSE-DFE) [2] which is one of the most successful equalizers for the data packet transmission, normalized LMS-DFE (N-LMS-DFE) [3] , variable step size (VSS) LMS-DFE [4] , fuzzy LMS-DFE [5],[6] and RLS-DFE [7] . The obtained simulation results using HIPERLAN/1 standards have demonstrated that the proposed LMS-DFE algorithm based on fuzzy logic has considerably better performance than others.