Sang-Ho SEO Hae-Wook CHOI Sin-Chong PARK
In this paper, a new implementation of the Viterbi decoder is proposed. The Modified State-Mapping VD algorithm combines the TB algorithm with the RE algorithm. By updating the starting point of the state for each memory bank, and by using Trace Back and Trace Forward information, LIFO (Last Input First Output) operation can be eliminated, which reduces the latency of the TB algorithm and decreases the resource usage of the RE algorithm. When the memory unit is 3, the resource usage is 13184 bits and the latency is 54 clocks. The latency of the proposed algorithm is 25% smaller than the MRE algorithm and 50% smaller than the k-pointer even TB algorithm. In addition, resource usage is 50% smaller than the RE algorithm. The resource usage is a little larger than that of the MRE algorithm for the small value of k, but it becomes smaller after k is larger than 16.
Masahide MIYAZAKI Tomokazu YONEDA Hideo FUJIWARA
With the increasing demand for SoCs to include rich functionality, SoCs are being designed with hundreds of small memories with different sizes and frequencies. If memory BIST logics were individually added to these various memories, the area overhead would be very high. To reduce the overhead, memory BIST logic must therefore be shared. This paper proposes a memory-grouping method for memory BIST logic sharing. A memory-grouping problem is formulated and an algorithm to solve the problem is proposed. Experimental results show that the proposed method reduced the area of the memory BIST wrapper by up to 40.55%. The results also show that the ability to select from two types of connection methods produced a greater reduction in area than using a single connection method.
Chin-Hung TENG Yung-Sheng CHEN Wen-Hsing HSU
Rendering realistic trees is quite important for simulating a 3D natural scene. Separating the trunk from its background is the first step toward the 3D model construction of the tree. In this paper, a three-phase algorithm is developed to extract the trunk structure of the tree and hence segment the trunk from the image. Some experiments were conducted and results confirmed the feasibility of proposed algorithm.
Masafumi UEMORI Haruo KOBAYASHI Tomonari ICHIKAWA Atsushi WADA Koichiro MASHIKO Toshiro TSUKADA Masao HOTTA
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.
Hideki TODE ZhengYu XIE Koso MURAKAMI
At present, a demand to the technology of contents distribution by which each user can request the desired content through network is increasing. There are some merits and demerits respectively with the existing on-demand systems for contents distribution, such as the methods based on broadcast and select transfer or multicast one. In this paper, we propose a hybrid scheduling method which adaptively uses both broadcasting and multicasting in order to improve the system efficiency. Adequate channel boundary to adopt two different transfer mechanisms is found through analytical consideration. Also, performance improvement of our proposal is verified in terms of response time and request blocking rate through computer simulation.
Yoshihide OHGAME Atsuo HAZEYAMA
Software inspection is a widely acknowledged effective quality improvement method in software development by detecting defects involved in software artifacts and removing them. In research on software inspection, constructing computer supported inspection systems is a major topic in the field. A lot of systems have been reported. However few inspection support systems for model diagrams, especially UML diagrams, have been emerged. We identified four key requirements an inspection support system for UML diagrams should have. They are as follows: 1) direct annotations are given to model diagrams, 2) version management is provided so that evolution of artifacts can be managed, 3) the whole inspection process should be supported, 4) horizontal and vertical readings are supported. This paper describes design and implementation of our inspection support system for UML diagrams to realize the four requirements.
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.
Koutaro HACHIYA Hiroyuki KOBAYASHI Takaaki OKUMURA Takashi SATO Hiroki OKA
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.
Byung-Gyu KIM Seon-Tae KIM Seok-Kyu SONG Pyeong-Soo MAH
An improved algorithm for fast motion estimation based on the block matching algorithm (BMA) is presented for use in a block-based video coding system. To achieve enhanced motion estimation performance, we propose an adaptive search pattern length for each iteration for the current macro block (MB). In addition, search points that must be checked are determined by means of directional information from the error surface, thus reducing intermediate searches. The proposed algorithm is tested with several sequences and excellent performance is verified.
Peng YUE Zeng-Ji LIU Bin ZHANG
In this paper, based on Equivalent Active Flow, we propose a novel technique called Approximate Fairness Dropping, which is able to approximate fairness by containing misbehaving flows' access queue opportunity with low time/space complexity. Unlike most of the existing Active Queue Management schemes (e.g., RED, BLUE, CHOKE), Approximate Fairness Dropping does not drop the packets whose arriving rate is within the maximum admitted rate, so it protects the well-behaving flows against misbehaving ones, moreover, improves the throughput and decreases the queuing delay. Our simulations and analyses demonstrate that this new technique outperforms the existing schemes and closely approximates the "ideal" case, where full state information is needed.
Chunshien LI Kuo-Hsiang CHENG Zen-Shan CHANG Jiann-Der LEE
A hybrid evolutionary neuro-fuzzy system (HENFS) is proposed in this paper, where the weighted Gaussian function (WGF) is used as the membership function for improved premise construction. With the WGF, different types of the membership functions (MFs) can be accommodated in the rule base of HENFS. A new hybrid algorithm of random optimization (RO) algorithm incorporated with the least square estimation (LSE) is presented. Based on the hybridization of RO-LSE, the proposed soft-computing approach overcomes the disadvantages of other widely used algorithms. The proposed HENFS is applied to chaos time series identification and industrial process modeling to verify its feasibility. Through the illustrations and comparisons the impressive performances for unknown system identification can be observed.
Jaehak CHUNG Seung Hoon NAM Chan-Soo HWANG
A differential detection Space-Time Block Code (STBC) is proposed with a high transmission rate, allowing a trade-off between diversity and multiplexing gain with low encoding and decoding complexity. The proposed method offers multiplexing gain by doubling the transmission rate for three and four transmission antennas. Computer simulations demonstrate that the proposed STBC can achieve a 5.8 dB Eb/N0 gain at BER = 10-3 compared with a conventional differential detection STBC for four transmission and two receiving antennas.
Youhua SHI Nozomu TOGAWA Shinji KIMURA Masao YANAGISAWA Tatsuo OHTSUKI
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.
Yunjian JIA Quoc Tuan TRAN Shinsuke HARA
We have proposed two space division multiple access (SDMA) approaches for OFDM signals: "Virtual Subcarrier Assignment (VISA)" and "Preamble Subcarrier Assignment (PASA)," both of which can enhance the system capacity without significant change of transmitter/receiver structures for already-existing OFDM-based standards such as IEEE802.11a. In order to investigate the performance of the proposed approaches in real wireless scenarios, we conducted a measurement campaign to obtain real channel state data at 5-GHz band in an indoor environment. Using the measured channel data, we can make the performance evaluation realistic. In this paper, after the brief overview of the two proposed SDMA approaches, we describe our measurement campaign in detail. Furthermore, we evaluate the performance of VISA-based system and PASA-based system by computer simulations using the measured channel state data and present a comparative study on the performance of the two proposed SDMA approaches in the realistic wireless environment.
Masakazu ADACHI Toshimitsu USHIO
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.
Etsuko TOYODA Morihiko MATSUMOTO Tomoyuki FUJITA Kenichi SHIOI Kazuaki YANO Masamitsu WATANABE Toshihiro ICHINO Yoshimori MIYATA Nobuo KUWAKI
We have developed a promising method for suppressing moisture condensation that prevents insulation failures in surge protectors. By analyzing surge protectors retrieved from the field, we found that electrolytic corrosion had occurred due to the encroachment of sea salt, the application of bias voltages, and the condensation of moisture. To suppress moisture condensation, a key factor in insulation failure, we applied a previously developed humidity-control package containing water-absorbent polymer. We experimentally optimized the design and functionality of the polymer package. We found that sealing the feed-through apertures alone was not enough to suppress moisture inflow and that a relatively large amount of water-absorbent polymer was needed to prevent water condensation in environments with extremely high humidity for extended periods of time. Laboratory experiments and field tests demonstrated that our optimized package minimized humidity fluctuation and thus moisture condensation in surge protectors, thereby preventing insulation failure. Application of this method to installed surge protectors greatly reduced the insulation failure rate.
Shingo YAMAGUCHI Kousuke YAMADA Qi-Wei GE Minoru TANAKA
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.
Mitsuji MUNEYASU Osamu HISAYASU Kensaku FUJII Takao HINAMOTO
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.
Masayoshi NABESHIMA Kouji YATA
It is well known that TCP does not fully utilize the available bandwidth in fast long-distance networks. To solve this scalability problem, several high speed transport protocols have been proposed. They include HighSpeed TCP (HS-TCP), Scalable TCP (S-TCP), Binary increase control TCP (BIC-TCP), and H-TCP. These protocols increase (decrease) their window size more aggressively (slowly) compared to standard TCP (STD-TCP). This paper aims at evaluating and comparing these high speed transport protocols through computer simulations. We select six metrics that are important for high speed protocols; scalability, buffer requirement, TCP friendliness, TCP compatibility, RTT fairness, and responsiveness. Simulation scenarios are carefully designed to investigate the performance of these protocols in terms of the metrics. Results clarify that each high speed protocol successfully solves the problem of STD-TCP. In terms of the buffer requirement, S-TCP and BIC-TCP have better performance. For TCP friendliness and compatibility, HS-TCP and H-TCP offer better performance. For RTT fairness, BIC-TCP and H-TCP are superior. For responsiveness, HS-TCP and H-TCP are preferred. However, H-TCP achieves a high degree of fairness at the expense of the link utilization. Thus, we understand that all the proposed high speed transport protocols have their own shortcomings. Thus, much more research is needed on high speed transport protocols.
Yang SONG Zhenyu LIU Satoshi GOTO Takeshi IKENAGA
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).