The search functionality is under construction.

IEICE TRANSACTIONS on Fundamentals

  • Impact Factor

    0.48

  • Eigenfactor

    0.003

  • article influence

    0.1

  • Cite Score

    1.1

Advance publication (published online immediately after acceptance)

Volume E89-A No.4  (Publication Date:2006/04/01)

    Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa
  • FOREWORD

    Yoshifumi NISHIO  

     
    FOREWORD

      Page(s):
    839-839
  • Modeling the Influence of Input-to-Output Coupling Capacitance on CMOS Inverter Delay

    Zhangcai HUANG  Atsushi KUROKAWA  Yun YANG  Hong YU  Yasuaki INOUE  

     
    PAPER

      Page(s):
    840-846

    The modeling of gate delays has always been one of the most difficult and market-sensitive works. In submicron designs, the second-order effects such as the input-to-output coupling capacitance have a significant influence on gate delay as shown in this paper. However, the accurate analysis of the input-to-output coupling capacitance effect has not been presented in previous research. In this paper, an analytical model for the influence of the input-to-output coupling capacitance on CMOS inverter delay is proposed, in which a novel algorithm for computing overshooting time is given. Experimental results show good agreement with Spice simulations.

  • Formula-Based Method for Capacitance Extraction of Interconnects with Dummy Fills

    Atsushi KUROKAWA  Akira KASEBE  Toshiki KANAMOTO  Yun YANG  Zhangcai HUANG  Yasuaki INOUE  Hiroo MASUDA  

     
    PAPER

      Page(s):
    847-855

    In advanced ASIC/SoC physical designs, interconnect parasitic extraction is one of the important factors to determine the accuracy of timing analysis. We present a formula-based method to efficiently extract interconnect capacitances of interconnects with dummy fills for VLSI designs. The whole flow is as follows: 1) in each process, obtain capacitances per unit length using a 3-D field solver and then create formulas, and 2) in the actual design phase, execute a well-known 2.5-D capacitance extraction. Our results indicated that accuracies of the proposed formulas were almost within 3% error. The proposed formula-based method can extract interconnect capacitances with high accuracy for VLSI circuits. Moreover, we present formulas to evaluate the effect of dummy fills on interconnect capacitances. These can be useful for determining design guidelines, such as metal density before the actual design, and for analyzing the effect of each structural parameter during the design phase.

  • Determination of Interconnect Structural Parameters for Best- and Worst-Case Delays

    Atsushi KUROKAWA  Hiroo MASUDA  Junko FUJII  Toshinori INOSHITA  Akira KASEBE  Zhangcai HUANG  Yasuaki INOUE  

     
    PAPER

      Page(s):
    856-864

    In general, a corner model with best- and worst-case delay conditions is used in static timing analysis (STA). The best- and worst-case delays of a stage are defined as the fastest and slowest delays from a cell input to the next cell input. In this paper, we present a methodology for determining the parameters that yield the best- and worst-case delays when interconnect structural parameters have the minimum and maximum values with process variations. We also present analysis results of our circuit model using the methodology. The min and max conditions for the time constant are found to be (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh), respectively. Here, +Δ or -Δ means the max or min corner value of each parameter variation, where w is the width, t is the interconnect thickness, and h is the height. Best and worst conditions for delay time are as follows: 1) given a circuit with an optimum driver, dense interconnects, and small branch capacitance, the best and worst conditions are respectively (-Δw, +Δt, +Δh) & (+Δw, +Δt, -Δh), 2) given driver and/or via resistances that are higher than the interconnect resistance, dense interconnects, and small branch capacitance, they are (-Δw, -Δt, +Δh) & (+Δw, +Δt, -Δh), and 3) for other conditions, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh). Moreover, if there must be only one condition each for the best- and worst-case delays, they are (+Δw, +Δt, +Δh) & (-Δw, -Δt, -Δh).

  • A Method to Derive SSO Design Rule Considering Jitter Constraint

    Koutaro HACHIYA  Hiroyuki KOBAYASHI  Takaaki OKUMURA  Takashi SATO  Hiroki OKA  

     
    PAPER

      Page(s):
    865-872

    A method to derive design rules for SSO (Simultaneous Switching Outputs) considering jitter constraint on LSI outputs is proposed. Since conventional design rules do not consider delay change caused by SSO, timing errors have sometimes occurred in output signals especially for a high-speed memory interface which allows very small jitter. A design rule derived by the proposed method includes delay change characteristics of output buffers to consider the jitter constraint. The rule also gives mapping from the jitter constraint to constraint on design parameters such as effective power/ground inductance, number of SSO and drivability of buffers.

  • Investigation of Class E Amplifier with Nonlinear Capacitance for Any Output Q and Finite DC-Feed Inductance

    Hiroo SEKIYA  Yoji ARIFUKU  Hiroyuki HASE  Jianming LU  Takashi YAHAGI  

     
    PAPER

      Page(s):
    873-881

    This paper investigates the design curves of class E amplifier with nonlinear capacitance for any output Q and finite dc-feed inductance. The important results are; 1) the capacitance nonlinearity strongly affects the design parameters for low Q, 2) the value of dc-feed inductance is hardly affected by the capacitance nonlinearity, and 3) the input voltage is an important parameter to design class E amplifier with nonlinear capacitance. By carrying out PSpice simulations, we show that the simulated results agree with the desired ones quantitatively. It is expected that the design curves in this paper are useful guidelines for the design of class E amplifier with nonlinear capacitance.

  • A Chaotic Burst in a Modified Discrete-Time Neuron Model

    Hiroto TANAKA  

     
    PAPER

      Page(s):
    882-886

    In this paper, we propose a modified bursting neuron model, which is a natural extension of an original one proposed by the author et al. We will show that chaotic bursts appear in the modified model though there exhibit quasi-periodic bursts in the original one. Moreover, we will show that such chaotic bursts appear by breaking down a pair of invariant closed curves, which is generated by a Hopf bifurcation for a pair of two-periodic points.

  • Dead Problem of Program Nets

    Shingo YAMAGUCHI  Kousuke YAMADA  Qi-Wei GE  Minoru TANAKA  

     
    PAPER

      Page(s):
    887-894

    In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.

  • Entropy Based Associative Memory

    Masahiro NAKAGAWA  

     
    PAPER

      Page(s):
    895-901

    In this paper, an entropy based associative memory model will be proposed and applied to memory retrievals with an orthogonal learning model to compare with the conventional model based on the quadratic Lyapunov functional to be minimized. In the present approach, the updating dynamics will be constructed on the basis of the entropy minimization strategy which may be reduced asymptotically to the above-mentioned autocorrelation dynamics as a special case. From numerical results, it will be found that the presently proposed novel approach realizes twice of the memory capacity in comparison with the autocorrelation based dynamics such as associatron.

  • A CMOS Watchdog Sensor for Certifying the Quality of Various Perishables with a Wider Activation Energy

    Ken UENO  Tetsuya HIROSE  Tetsuya ASAI  Yoshihito AMEMIYA  

     
    PAPER

      Page(s):
    902-907

    We developed a CMOS watchdog sensor that simulates the changes in quality of perishables such as farm and marine products. The sensor can imitate a chemical reaction that causes the changes in the quality of perishables, with a wide range of activation energy from 0.1 eV to 0.7 eV. Attached to perishable goods, the sensor simulates the deterioration of the goods caused by surrounding temperatures. By reading the output of the sensor, consumers can determine whether the goods are fresh or not. This sensor consists of subthreshold CMOS circuits with a low-power consumption of 5 µW or less.

  • Complex Bandpass ΔΣAD Modulator Architecture without I, Q-Path Crossing Layout

    Hao SAN  Akira HAYAKAWA  Yoshitaka JINGU  Hiroki WADA  Hiroyuki HAGIWARA  Kazuyuki KOBAYASHI  Haruo KOBAYASHI  Tatsuji MATSUURA  Kouichi YAHAGI  Junya KUDOH  Hideo NAKANE  Masao HOTTA  Toshiro TSUKADA  Koichiro MASHIKO  Atsushi WADA  

     
    PAPER

      Page(s):
    908-915

    This paper proposes a new architecture for multibit complex bandpass ΔΣAD modulators with built-in Switched-Capacitor (SC) circuits for application to Low-IF receivers such as used for Bluetooth and WLAN. In the realization of complex bandpass ΔΣAD modulators, we face the following problems: (i) SNR of AD converter is deteriorated by mismatches between internal analog I and Q paths. (ii) Layout design becomes complicated because of signal lines crossing by complex filter and feedback from DAC for I and Q paths in the complex modulator, and this increases required chip area. We propose a new structure for a complex bandpass ΔΣAD modulator which can be completely divided into two paths without layout crossing, and solves the problems mentioned above. The two parts of signal paths and circuits in the modulator are changed for I and Q while CLK is changed for High/Low by adding multiplexers. Symmetric circuits are used for I and Q paths at a certain timing, and they are switched by multiplexers to those used for Q and I paths at another timing. Therefore the influence from mismatches between I and Q paths is reduced by dynamic matching. As a result, the modulator is divided into two separate parts without crossing signal lines between I and Q paths and its layout design can be greatly simplified compared with conventional modulators. We have conducted MATLAB simulations to confirm the effectiveness of the proposed structure.

  • High-Speed Continuous-Time Subsampling Bandpass ΔΣ AD Modulator Architecture Employing Radio Frequency DAC

    Masafumi UEMORI  Haruo KOBAYASHI  Tomonari ICHIKAWA  Atsushi WADA  Koichiro MASHIKO  Toshiro TSUKADA  Masao HOTTA  

     
    PAPER

      Page(s):
    916-923

    This paper proposes a continuous-time bandpass ΔΣAD modulator architecture which performs high-accuracy AD conversion of high frequency analog signals and can be used for next-generation radio systems. We use an RF DAC inside the modulator to enable subsampling and also to make the SNDR of the continuous-time modulator insensitive to DAC sampling clock jitter. We have confirmed that this is the case by MATLAB simulation. We have also extended our modulator to multi-bit structures and show that this alleviates excess loop delay problems.

  • Nonlinear Blind Source Separation Method for X-Ray Image Separation

    Nuo ZHANG  Jianming LU  Takashi YAHAGI  

     
    PAPER

      Page(s):
    924-931

    In this study, we propose a robust approach for blind source separation (BSS) by using radial basis function networks (RBFNs) and higher-order statistics (HOS). The RBFN is employed to estimate the inverse of a hypothetical complicated mixing procedure. It transforms the observed signals into high-dimensional space, in which one can simply separate the transformed signals by using a cost function. Recently, Tan et al. proposed a nonlinear BSS method, in which higher-order moments between source signals and observations are matched in the cost function. However, it has a strict restriction that it requires the higher-order statistics of sources to be known. We propose a cost function that consists of higher-order cumulants and the second-order moment of signals to remove the constraint. The proposed approach has the capacity of not only recovering the complicated mixed signals, but also reducing noise from observed signals. Simulation results demonstrate the validity of the proposed approach. Moreover, a result of application to X-ray image separation also shows its practical applicability.

  • A Hardware Implementation of a Content-Based Motion Estimation Algorithm for Real-Time MPEG-4 Video Coding

    Shen LI  Takeshi IKENAGA  Hideki TAKEDA  Masataka MATSUI  Satoshi GOTO  

     
    PAPER

      Page(s):
    932-940

    Power efficiency and real-time processing capability are two major issues in today's mobile video applications. We proposed a novel Motion Estimation (ME) engine for power-efficient real-time MPEG-4 video coding based on our previously proposed content-based ME algorithm [8],[13]. By adopting Full Search (FS) and Three Step Search (TSS) alternatively according to the nature of video contents, this algorithm keeps the visual quality very close to that of FS with only 3% of its computational power. We designed a flexible Block Matching (BM) Unit with 16-PE SIMD data path so that the adaptive ME can be performed at a much lower clock frequency and hardware cost as compared with previous FS based work. To reduce the energy cost caused by excessive external memory access, on-chip SRAM is also utilized and optimized for parallel processing in the BM Unit. The ME engine is fabricated with TSMC 0.18 µm technology. When processing QCIF (15 fps) video, the estimated power is 2.88 mW@4.16 MHz (supply voltage: 1.62 V). It is believed to be a favorable contribution to the video encoder LSI design for mobile applications.

  • Real-Time Human Object Extraction Method for Mobile Systems Based on Color Space Segmentation

    Gen FUJITA  Takaaki IMANAKA  Hyunh Van NHAT  Takao ONOYE  Isao SHIRAKAWA  

     
    PAPER

      Page(s):
    941-949

    Since a human object is an important element of the moving pictures being processed by mobile terminals, establishing a human object extraction method encourages dissemination of new applications. In accordance with the requirement of mobile applications, this paper proposes a low-cost human object extraction method, which consists of a face object and a hair object extraction based on their color information and a simple body extraction utilizing the position information of the face object. In the proposed method, skin color and hair color are estimated through color space segmentation, and a human object is effectively extracted by using a radial active contour model. Simulation results of the human object extraction with the use of XScale processor claims that QCIF 15 fps video sequences can be processed in real time.

  • Speech Noise Reduction System Based on Frequency Domain ALE Using Windowed Modified DFT Pair

    Isao NAKANISHI  Yuudai NAGATA  Takenori ASAKURA  Yoshio ITOH  Yutaka FUKUI  

     
    PAPER

      Page(s):
    950-959

    The speech noise reduction system based on the frequency domain adaptive line enhancer using a windowed modified DFT (MDFT) pair is presented. The adaptive line enhancer (ALE) is effective for extracting sinusoidal signals blurred by a broadband noise. In addition, it utilizes only one microphone. Therefore, it is suitable for the realization of speech noise reduction in portable electronic devices. In the ALE, an input signal is generated by delaying a desired signal using the decorrelation parameter, which makes the noise in the input signal decorrelated with that in the desired one. In the present paper, we propose to set decorrelation parameters in the frequency domain and adjust them to optimal values according to the relationship between speech and noise. Such frequency domain decorrelation parameters enable the reduction of the computational complexity of the proposed system. Also, we introduce the window function into MDFT for suppressing spectral leakage. The performance of the proposed noise reduction system is examined through computer simulations.

  • An Active Noise Control System Based on Simultaneous Equations Method without Auxiliary Filters

    Mitsuji MUNEYASU  Osamu HISAYASU  Kensaku FUJII  Takao HINAMOTO  

     
    PAPER

      Page(s):
    960-968

    A simultaneous equations method is one of active noise control algorithms without estimating an error path. This algorithm requires identification of a transfer function from a reference microphone to an error microphone containing the effect of a noise control filter. It is achieved by system identification of an auxiliary filter. However, the introduction of the auxiliary filter requires more number of samples to obtain the noise control filter and brings a requirement of some undesirable assumption in the multiple channel case. In this paper, a new simultaneous equations method without the identification of the auxiliary filter is proposed. By storing a small number of input signals and error signals, we avoid this identification. Therefore, we can reduce the number of samples to obtain the noise control filters and can avoid the undesirable assumption. From simulation examples, it is verified that the merits of the ordinary method is also retained in the proposed method.

  • Partially-Parallel LDPC Decoder Achieving High-Efficiency Message-Passing Schedule

    Kazunori SHIMIZU  Tatsuyuki ISHIKAWA  Nozomu TOGAWA  Takeshi IKENAGA  Satoshi GOTO  

     
    PAPER

      Page(s):
    969-978

    In this paper, we propose a partially-parallel LDPC decoder which achieves a high-efficiency message-passing schedule. The proposed LDPC decoder is characterized as follows: (i) The column operations follow the row operations in a pipelined architecture to ensure that the row and column operations are performed concurrently. (ii) The proposed parallel pipelined bit functional unit enables the column operation module to compute every message in each bit node which is updated by the row operations. These column operations can be performed without extending the single iterative decoding delay when the row and column operations are performed concurrently. Therefore, the proposed decoder performs the column operations more frequently in a single iterative decoding, and achieves a high-efficiency message-passing schedule within the limited decoding delay time. Hardware implementation on an FPGA and simulation results show that the proposed partially-parallel LDPC decoder improves the decoding throughput and bit error performance with a small hardware overhead.

  • Scalable VLSI Architecture for Variable Block Size Integer Motion Estimation in H.264/AVC

    Yang SONG  Zhenyu LIU  Satoshi GOTO  Takeshi IKENAGA  

     
    PAPER

      Page(s):
    979-988

    Because of the data correlation in the motion estimation (ME) algorithm of H.264/AVC reference software, it is difficult to implement an efficient ME hardware architecture. In order to make parallel processing feasible, four modified hardware friendly ME workflows are proposed in this paper. Based on these workflows, a scalable full search ME architecture is presented, which has following characteristics: (1) The sum of absolute differences (SAD) results of 44 sub-blocks is accumulated and reused to calculate SADs of bigger sub-blocks. (2) The number of PE groups is configurable. For a search range of MN pixels, where M is width and N is height, up to M PE groups can be configured to work in parallel with a peak processing speed of N16 clock cycles to fulfill a full search variable block size ME (VBSME). (3) Only conventional single port SRAM is required, which makes this architecture suitable for standard-cell-based implementation. A design with 8 PE groups has been realized with TSMC 0.18 µm CMOS technology. The core area is 2.13 mm1.60 mm and clock frequency is 228 MHz in typical condition (1.8 V, 25).

  • Thermal-Aware Placement Based on FM Partition Scheme and Force-Directed Heuristic

    Jing LI  Hiroshi MIYASHITA  

     
    PAPER

      Page(s):
    989-995

    Temperature-tracking is becoming of paramount importance in modern electronic design automation tools. In this paper, we present a deterministic thermal placement algorithm for standard cell based layout which can lead to a smooth temperature distribution over the die. It is mainly based on Fiduccia-Mattheyses partition scheme and a former substrate thermal model that can convert the known temperature constraints into the corresponding power distribution constraints. Moreover, a kind of force-directed heuristic based on cells' power consumption is introduced in the above process. Experimental results demonstrate a comparatively uniform temperature distribution and show a reduction of the maximal temperature on the die.

  • Selective Low-Care Coding: A Means for Test Data Compression in Circuits with Multiple Scan Chains

    Youhua SHI  Nozomu TOGAWA  Shinji KIMURA  Masao YANAGISAWA  Tatsuo OHTSUKI  

     
    PAPER

      Page(s):
    996-1004

    This paper presents a test input data compression technique, Selective Low-Care Coding (SLC), which can be used to significantly reduce input test data volume as well as the external test channel requirement for multiscan-based designs. In the proposed SLC scheme, we explored the linear dependencies of the internal scan chains, and instead of encoding all the specified bits in test cubes, only a smaller amount of specified bits are selected for encoding, thus greater compression can be expected. Experiments on the larger benchmark circuits show drastic reduction in test data volume with corresponding savings on test application time can be indeed achieved even for the well-compacted test set.

  • Practical Fast Clock-Schedule Design Algorithms

    Atsushi TAKAHASHI  

     
    PAPER

      Page(s):
    1005-1011

    In this paper, a practical clock-scheduling engine is introduced. The minimum feasible clock-period is obtained by using a modified Bellman-Ford shortest path algorithm. Then an optimum cost clock-schedule is obtained by using a bipartite matching algorithm. It also provides useful information to circuit synthesis tools. The experiment to a circuit with about 10000 registers and 100000 signal paths shows that a result is obtained within a few minutes. The computation time is almost linear to the circuit size in practice.

  • Hardware Design Verification Using Signal Transitions and Transactions

    Nobuyuki OHBA  Kohji TAKANO  

     
    PAPER

      Page(s):
    1012-1017

    Hardware prototyping has been widely used for ASIC/SoC verification. This paper proposes a new hardware design verification method, Transition and Transaction Tracer (TTT), which probes and records the signals of interest for a long time, hours, days, or even weeks, without a break. It compresses the captured data in real time and stores it in a state transition format in memory. Since it records all the transitions, it is effective in finding and fixing errors, even ones that occur rarely or intermittently. It can also be programmed to generate a trigger for a logic analyzer when it detects certain transitions. This is useful for debugging situations where the engineer has trouble finding an appropriate trigger condition to pinpoint the source of errors. We have been using the method in hardware prototyping for ASIC/SoC development for two years and found it useful for system level tests, and in particular for long running tests.

  • Synchronization Mechanism for Timed/Untimed Mixed-Signal System Level Design Environment

    Yu LIU  Satoshi KOMATSU  Masahiro FUJITA  

     
    PAPER

      Page(s):
    1018-1026

    Recently, system level design languages (SLDL), which can describe both hardware and software aspects of the design, are receiving attention. Mixed-signal extensions of SLDL enable current discrete-oriented SLDLs to describe and simulate not only digital systems but also digital-analog mixed-signal systems. The synchronization between discrete and continuous behaviors is widely regarded as a critical part in the extensions. In this paper, we present an event-driven synchronization mechanism for both timed and untimed system level designs through which discrete and continuous behaviors are synchronized via AD events and DA events. We also demonstrate how the synchronization mechanism can be incorporated into the kernel of SLDL, such as SpecC. In the extended kernel, a new simulation cycle, the AMS cycle, is introduced. Three case studies show that the extended SpecC-based system level design environment using our synchronization mechanism works well with timed/untimed mixed-signal system level description.

  • Analysis of Automation Surprises in Human-Machine Systems with Time Information

    Masakazu ADACHI  Toshimitsu USHIO  

     
    PAPER

      Page(s):
    1027-1034

    This paper analyzes automation surprises in human-machine systems with time information. Automation surprises are phenomena such that the underlying machine's behavior diverges from user's intention and may lead to critical situations. Thus, designing human-machine systems without automation surprises is one of fundamental issues to achieve reliable user interaction with the machines. In this paper, we focus on timed human-machine interaction and address their formal aspects. The presented framework is essentially an extension of untimed human-machine interaction and will cover the previously proposed methodologies. We employ timed automata as a model of human-machine systems with time information. Modeling the human-machine systems as timed automata enables one to deal with not only discrete behavior but also time constraints. Then, by introducing the concept of timed simulation of the machine model and the user model, conditions which guarantee the nonexistence of automation surprises are derived. Finally, we construct a composite model in which a machine model and a user model evolve concurrently and show that automation surprises can be detected by solving a reachability problem in the composite model.

  • Label Size Maximization for Rectangular Node Labels

    Shigeki TORIUMI  Hisao ENDO  Keiko IMAI  

     
    PAPER

      Page(s):
    1035-1041

    The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing, and graphical interface design. In this paper, we considered the label size maximization problem for points with axes-parallel rectangular labels that correspond to character strings and have different widths based on the number of characters. We propose an algorithm for computing the optimum size for the label size maximization problem in the 2-position model and a polynomial time algorithm for the problem in the 4-position model. Our algorithm cannot obtain the maximum value in the 4-position model because the label size maximization problem in the 4-position model is NP-hard. However, our algorithm is efficient in practice, as shown by computational experiments. Further, computational results for JR trains, subways and major private railroads in Tokyo are presented.

  • On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree

    Toshiya MASHIMA  Satoshi TAOKA  Toshimasa WATANABE  

     
    PAPER

      Page(s):
    1042-1048

    The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices SV and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,EE') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any vV, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

  • Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs

    Satoshi TAOKA  Kazuya WATANABE  Toshimasa WATANABE  

     
    PAPER

      Page(s):
    1049-1057

    Let G = (DS,E) be an undirected graph with a vertex set DS and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set D and a supply vertex set S. We assume that D and S in this paper. Each demand or supply vertex v has a positive real number d(v) or s(v), called the demand or supply of v, respectively. For any subset V' ⊆ DS, the demand of V' is defined by d(V') = ΣvV'∩Dd(v) if V' ∩ D or d(V') = 0 if V' ∩ D = . Let s(S) = ΣvS s(v). Any partition π = {V1,..., Vr} (|S| r |DS|) of DS is called a feasible partition of G if and only if π satisfies the following (1) and (2) for any k = 1,..., r: (1) |VkS|1, and (2) if VkS = {uk} then the induced subgraph G[Vk] of G is connected and d(Vk)s(uk). The demand d(π) of π is defined by d(π)=d(Vk). The "Maximum-Supply Partitioning Problem (MSPP)" is to find a feasible partition π of G such that d(π) is maximum among all feasible partitions of G. We implemented not only existing algorithms for obtainity heuristic or optimum solutions to MSPP but also those that are corrected or improved from existing ones. In this paper we show comparison of their capability based on computational experiments.

  • Regular Section
  • A Two-Stage Method for Single-Channel Speech Enhancement

    Mohammad E. HAMID  Takeshi FUKABAYASHI  

     
    PAPER-Speech and Hearing

      Page(s):
    1058-1068

    A time domain (TD) speech enhancement technique to improve SNR in noise-contaminated speech is proposed. Additional supplementary scheme is applied to estimate the degree of noise of noisy speech. This is estimated from a function, which is previously prepared as the function of the parameter of the degree of noise. The function is obtained by least square (LS) method using the given degree of noise and the estimated parameter of the degree of noise. This parameter is obtained from the autocorrelation function (ACF) on frame-by-frame basis. This estimator almost accurately estimates the degree of noise and it is useful to reduce noise. The proposed method is based on two-stage processing. In the first stage, subtraction in time domain (STD), which is equivalent to ordinary spectral subtraction (SS), is carried out. In the result, the noise is reduced to a certain level. Further reduction of noise and by-product noise residual is carried out in the second stage, where blind source separation (BSS) technique is applied in time domain. Because the method is a single-channel speech enhancement, the other signal is generated by taking the noise characteristics into consideration in order to apply BSS. The generated signal plays a very important role in BSS. This paper presents an adaptive algorithm for separating sources in convolutive mixtures modeled by finite impulse response (FIR) filters. The coefficients of the FIR filter are estimated from the decorrelation of two mixtures. Here we are recovering only one signal of interest, in particular the voice of primary speaker free from interfering noises. In the experiment, the different levels of noise are added to the clean speech signal and the improvement of SNR at each stage is investigated. The noise types considered initially in this study consist of the synthesized white and color noise with SNR set from 0 to 30 dB. The proposed method is also tested with other real-world noises. The results show that the satisfactory SNR improvement is attained in the two-stage processing.

  • A Novel Wavelet-Based Notch Filter with Controlled Null Width

    Yung-Yi WANG  Ying LU  Liang-Cheng LEE  

     
    PAPER-Digital Signal Processing

      Page(s):
    1069-1075

    This paper presents a wavelet-based approach for the design of the finite impulse response (FIR) notch filter with controlled null width. The M-band P-regular wavelet filters are employed to constitute the null space of the derivative constraint matrix. Taking advantage of the vanishing moment property of the wavelet filters, the proposed method controls the null width of the notch filter by adjusting the regularity of the employed wavelet filters. Besides, the selection of large number of bands of the wavelet filters can effectively reduce the minimum mean square error and thus improve the performance of the notch filter. Computer simulations show that, in addition to possessing lower computational complexity, the proposed reduced-rank method has similar frequency response compared to those of the full-rank-based techniques.

  • Low-Voltage Analog Switch in Deep Submicron CMOS: Design Technique and Experimental Measurements

    Christian Jesus B. FAYOMI  Mohamad SAWAN  Gordon W. ROBERTS  

     
    PAPER-Analog Signal Processing

      Page(s):
    1076-1087

    This paper concerns the design, implementation and subsequent experimental validation of a low-voltage analog CMOS switch based on a gate-bootstrapped method. The main part of the proposed circuit is a new low-voltage and low-stress CMOS clock voltage doubler. Through the use of a dummy switch, the charge injection induced by the bootstrapped switch is greatly reduced resulting in improved sample-and-hold accuracy. An important attribute of the design is that the ON-resistance is nearly constant. A test chip has been designed and fabricated using a TSMC 0.18 µm CMOS process (single poly, n-well) to confirm the operation of the circuit for a supply voltage of down to 0.65 V.

  • Chaotification of the Van der Pol System Using Jerk Architecture

    Sinuhe BENITEZ  Leonardo ACHO  Ricardo J.R. GUERRA  

     
    PAPER-Systems and Control

      Page(s):
    1088-1091

    In this brief, a chaotic Jerk system is presented. This was obtained by converting the Van der Pol architecture into a third order differential equation, and, after the state-space representation was obtained, adding one innovation term and modifying some proportional parameters. Using Lyapunov exponents, Poincare maps, Fourier spectrum analysis and numerical experiments, we confirm the chaotic nature of the proposed Jerk system. Experimental results are also included.

  • Robust Chaotic Message Masking Communication over Noisy Channels: The Modified Chaos Approach

    Chian-Song CHIU  Tung-Sheng CHIANG  Peter LIU  

     
    PAPER-Systems and Control

      Page(s):
    1092-1099

    This paper studies the robustness of message masking communication over noisy channels using modified chaotic systems. First, the modified chaotic systems are introduced with a higher capability of transmitting messages than typical chaotic systems. Then, assuming an ideal channel, the chaotic message masking scheme is derived which achieves asymptotic convergence or dead-beat performance for recovering messages. Next, considering the case of noisy channels, an H performance and an L2-gain optimal noise rejection are achieved by solving linear matrix inequality (LMI) problems. Furthermore, the ultimate bound of synchronization error and recovered message error can be adjusted by both design gains and the system parameter of the modified chaos. Using the proposed method, the bit-error-ratio and noise tolerance are improved. Finally, numerical simulations and DSP experiments are carried out to verify the theoretical derivations.

  • Robust Fuzzy Integral Regulator Design for a Class of Affine Nonlinear Systems

    Tung-Sheng CHIANG  Chian-Song CHIU  Peter LIU  

     
    PAPER-Systems and Control

      Page(s):
    1100-1107

    This paper proposes a robust fuzzy integral controller for output regulating a class of affine nonlinear systems subject to a bias reference to the origin. First, a common biased fuzzy model is introduced for a class of continuous/discrete-time affine nonlinear systems, such as dc-dc converters, robotic systems. Then, combining an integrator and parallel distributed compensators, the fuzzy integral regulator achieves an asymptotic regulation. Moreover, when considering disturbances or unstructured certainties, a virtual reference model is presented and provides a robust gain design via LMI techniques. In this case, H performances is guaranteed. Note that the information regarding the operational point and bias terms are not required during the controller implementation. Thus, the controller can be applied to a multi-task regulation. Finally, three numerical simulations show the expected results.

  • Fingerprinting Protocol for On-Line Trade Using Information Gap between Buyer and Merchant

    Minoru KURIBAYASHI  Hatsukazu TANAKA  

     
    PAPER-Information Security

      Page(s):
    1108-1115

    The homomorphic property of the public key cryptosystem has been exploited in order to achieve asymmetric fingerprinting such that only a buyer can obtain fingerprinted content. However, this requires many computations and a wide-band network channel because the entire uncompressed content must be encrypted based on the public key cryptosystem. In this paper, instead of the homomorphic property, we introduce the management of the enciphering keys for the symmetric cryptosystem. Based on a buyer's identity, a trusted center issues the buyer a partial sequence which is one of the two elements in the entire sequence. Although a merchant shares the entire sequence with the center, he cannot extract the buyer's key sequence from it. Such an information gap enables our protocol to be asymmetric and efficient. For each packet of content, the merchant produces two marked packets that contains a "0" or "1" information bit, and they are enciphered using the two elements from the entire sequence. Subsequently, the buyer obtains the two ciphertexts (the encrypted marked packets) containing the information bits of his identity. Since the merchant does not know the ciphertext decrypted by the buyer, an asymmetric property is achieved. In our protocol, before trade between a buyer and a merchant, the merchant can produce and compress the marked packets; this enables the reduction of both the computational costs for the encryption and the amount of data for transmission. Since only the enciphering operation is performed by a merchant in the on-line protocol, real-time operation may be possible.

  • Design of IIR Digital Filters with Discrete Coefficients Based on MLS Criterion

    Masayoshi NAKAMOTO  Takao HINAMOTO  

     
    LETTER-Digital Signal Processing

      Page(s):
    1116-1121

    In this paper, we treat a design problem for IIR digital filters described by rational transfer function in discrete space. First, we form the filter design problem using the modified least-squares (MLS) criterion and express it as the quadratic form with respect to the numerator and denominator coefficients. Next, we show the relaxation method using the Lagrange multiplier method in order to search for the good solution efficiently. Additionally we can check the filter stability when designing the denominator coefficients. Finally, we show the effectiveness of the proposed method using a numerical example.

  • Robustness Bounds for Receding Horizon Controls of Continuous-Time Systems with Uncertainties

    ChoonKi AHN  SooHee HAN  WookHyun KWON  

     
    LETTER-Systems and Control

      Page(s):
    1122-1125

    This letter presents robustness bounds (RBs) for receding horizon controls (RHCs) of uncertain systems. The proposed RBs are obtained easily by solving convex problems represented by linear matrix inequalities (LMIs). We show, by numerical examples, that the RHCs can guarantee robust stabilization for a larger class of uncertain systems than conventional linear quadratic regulators (LQRs).

  • Connectivity-Based Image Watermarking

    Jian LUO  Hongxia WANG  

     
    LETTER-Information Security

      Page(s):
    1126-1128

    A novel robust watermarking scheme based on image connectivity is proposed. Having obtained the connected objects according to the selected connectivity pattern, the gravity centers are calculated in several larger objects as the reference points for watermark embedding. Based on these reference points and the center of the whole image, several sectors are formed, and the same version watermarks are embedded into these sectors. Thanks to the very stable gravity center of the connected objects, watermark detection is synchronized successfully. Simulation results show that our scheme can survive under both local and global geometrical distortions.

  • DWT Domain On-Line Signature Verification Using the Pen-Movement Vector

    Isao NAKANISHI  Hiroyuki SAKAMOTO  Naoto NISHIGUCHI  Yoshio ITOH  Yutaka FUKUI  

     
    LETTER-Information Security

      Page(s):
    1129-1131

    In order to reduce the computational complexity of the DWT domain on-line signature verification, the authors propose to utilize the pen-movement vector as an input parameter. Experimental results indicate that the verification rate obtained using the pen-movement vector parameter is equivalent to that obtained by the conventional method, although the computational complexity of the proposed method is approximately half that of the conventional method.

  • A Code Whose Codeword Length is Shorter than n in Almost All of Sufficiently Large Positive Integers

    Hirofumi NAKAMURA  Sadayuki MURASHIMA  

     
    LETTER-Information Theory

      Page(s):
    1132-1139

    A recursive-type positive integer code is proposed. It prefixes the information about the length of the component of the codeword recursively. It is an asymptotically optimal code. The codeword length for a positive integer n is shorter than n bits in almost all of sufficiently large positive integers, where n is the log-star function.

  • Lower Bounds on Two-Dimensional Generalized Orthogonal Sequences

    Fanxin ZENG  Zhenyu ZHANG  Lijia GE  

     
    LETTER-Information Theory

      Page(s):
    1140-1144

    For various applications in image, communications and signal processing, two-dimensional (2-D) generalized orthogonal (GO) sequences, that is, 2-D sequences with zero correlation zone (ZCZ) and 2-D complementary orthogonal (CO) sequences with ZCZ, are widely investigated. New lower bounds for 2-D GO sequences, based on matrix theory on rank, are derived and presented, some examples that attain these lower bounds are given. As a direct application to our results, upper bound on family size of 2-D mutually complementary orthogonal (MCO) codes defined by Luke [9] is proposed.

  • Bootstrapped Modified Weighted Bit Flipping Decoding of Low Density Parity Check Codes

    Yoichi INABA  Tomoaki OHTSUKI  

     
    LETTER-Coding Theory

      Page(s):
    1145-1149

    Recently, various decoding algorithms with Low Density Parity Check (LDPC) codes have been proposed. Most algorithms can be divided into a hard decision algorithm and a soft decision algorithm. The Weighted Bit Flipping (WBF) algorithm that is between a hard decision and a soft decision algorithms has been proposed. The Bootstrapped WBF and Modified WBF algorithms have been proposed to improve the error rate performance and decoding complexity of the WBF algorithm. In this letter, we apply the Bootstrap step to the Modified WBF algorithm. We show that the Bootstrapped modified WBF algorithm outperforms the WBF, Bootstrapped WBF, and Modified WBF algorithms. Moreover, we show that the Bootstrapped modified WBF algorithm has the lowest decoding complexity.

  • Diversity Combining for Soft/Softer Hand-Over in DS-CDMA

    Jungwoo LEE  

     
    LETTER-Spread Spectrum Technologies and Applications

      Page(s):
    1150-1153

    In soft/softer hand-over of a wideband CDMA system, the RAKE receiver combines signals from different base stations by assigning separate fingers. A generalized maximal ratio combining technique for soft/softer hand-over is derived. Two correction schemes to optimize the MRC are proposed and compared against a conventional MRC.

  • Per-User Automatic Gain Control for an Uplink CDMA Receiver

    Jungwoo LEE  

     
    LETTER-Spread Spectrum Technologies and Applications

      Page(s):
    1154-1157

    A per-user AGC technique is proposed to combat the signal level variation of an individual user in a DS-CDMA receiver. A simple signal model for a Rake receiver is derived, and the potential cause of the signal variation in the Rake receiver output is discussed. The adaptive scheme is also compared with a conventional fixed quantization scheme in simulations.