The OFDM technique has recently received considerable attention in the fields of wireless LAN communication systems. It is accompanied with many practical issues and one major issue is synchronization. In this letter, we propose a frequency offset estimation technique for OFDM system. The proposed frequency offset estimator employing interpolation technique in the frequency domain has a simple structure and good performance.
Shin NATORI Katsuhiko GONDOW Takashi IMAIZUMI Takeshi HAGIWARA Takuya KATAYAMA
Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.
Hiroyuki TANAKA Zhangjian LI Shin-ichi NAKANO
A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n3) time per triangulation without duplications.
Seiichiro TANI Toshiaki MIYAZAKI
Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2log ^* k) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2log ^* k is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.
This paper presents a dynamic node decaying method (DNDM) for layered artificial neural networks that is suitable for classification problems. Our purpose is not to minimize the total output error but to obtain high generalization ability with minimal structure. Users of the conventional back propagation (BP) learning algorithm can convert their program to the DNDM by simply inserting a few lines. This method is an extension of a previously proposed method to more general classification problems, and its validity is tested with recent standard benchmark problems. In addition, we analyzed the training process and the effects of various parameters. In the method, nodes in a layer compete for survival in an automatic process that uses a criterion. Relatively less important nodes are decayed gradually during BP learning while more important ones play larger roles until the best performance under given conditions is achieved. The criterion evaluates each node by its total influence on progress toward the upper layer, and it is used as the index for dynamic competitive decaying. Two additional criteria are used: Generalization Loss to measure over-fitting and Learning Progress to stop training. Determination of these criteria requires a few human interventions. We have applied this algorithm to several standard benchmark problems such as cancer, diabetes, heart disease, glass, and iris problems. The results show the effectiveness of the method. The classification error and size of the generated networks are comparable to those obtained by other methods that generally require larger modification, or complete rewriting, of the program from the conventional BP algorithm.
We present an efficient stream authentication scheme using authentication stars. The computation overhead of the proposed scheme on the sender is almost the same as that of the scheme with the smallest overhead. On the receiver's side, the verification probability of the proposed scheme is much higher than that of any other scheme. To show this, we first conducted a mathematical analysis on the verification probability of our scheme and then performed simulation to compare the verification probability of our scheme with those of the previous schemes. Simulation results shows that when the packet loss rate is 50%, the verification probability of our scheme is 73% whereas those of the previous schemes are below 41%.
Zhang-Jian LI Shin-ichi NAKANO
A plane quadrangulation is a plane graph such that each inner face has exactly four edges on its contour. This is a planar dual of a plane graph such that all inner vertices have degree exactly four. A based plane quadrangulation is a plane quadrangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane quadrangulations with at most f faces. The algorithm uses O(f) space and generates such quadrangulations in O(1) time per quadrangulation without duplications. By modifying the algorithm we can generate all biconnected (non-based) plane quadrangulations with at most f faces in O(f3) time per quadrangulation.
Shinfeng D. LIN Shih-Chieh SHIE Kuo-Yuan LEE
A wavelet-based vector quantization scheme for image compression is introduced here. The proposed scheme obtains a better compression efficiency by the following three methods. (1) Utilizing the correlation among wavelet coefficients. (2) Placing different emphasis on wavelet coefficients at different levels. (3) Preserving the most important information of the image. In our experiments, simulation results show that this technique outperforms the recent SMVQ-ABC [1] and WTC-NIVQ [2] techniques.
Dongliang HUANG Naoyuki FUJIYAMA Sueo SUGIMOTO
This paper presents a maximum likelihood (ML) identification and restoration method for noisy blurred images. The unitary discrete sine transform (DST) is employed to decouple the large order spatial state-space representation of the noisy blurred image into a bank of one-dimensional real state-space scalar subsystems. By assuming that the noises are Gaussian distributed processes, the maximum likelihood estimation technique using the expectation-maximization (EM) algorithm is developed to jointly identify the blurring functions, the image model parameters and the noise variances. In order to improve the computational efficiency, the conventional Kalman smoother is incorporated to give the estimates. The identification process also yields the estimates of transformed image data, from which the original image is restored by the inverse DST. The experimental results show the effectiveness of the proposed method and its superiority over the recently proposed spatial domain DFT-based methods.
Seung-Chan HEO Young-Chan JANG Sang-Hune PARK Hong-June PARK
An 8-bit 200 MS/s CMOS 2-stage cascaded folding/interpolating ADC chip was implemented by applying a resistor averaging/interpolating scheme at the preamplifier outputs and the differential circuits for the encoder logic block, with a 0.35-µm double-poly CMOS process. The number of preamplifiers was reduced to half by using an averaging technique with a resistor array at the preamplifier outputs. The delay time of digital encoder block was reduced from 2.2 ns to 1.3 ns by replacing the standard CMOS logic with DCVSPG and CPL differential circuits. The measured SFDR was 42.5 dB at the sampling rate of 200 MS/s for the 10.072 MHz sinusoidal input signal.
Ji Hoon KIM Joon Hyung KIM Youn Sub NOH Song Gang KIM Chul Soon PARK
A high efficient HBT MMIC power amplifier with a new on-chip bias control circuit was proposed for PCS applications. By adjusting the quiescent current in accordance with the output power levels, the average power usage efficiency of the power amplifier is improved by a factor of 1.4. The bias controlled power amplifier, depending on low (high) output power levels, shows 62(103) mA of quiescent current, 16(28) dBm output power with 7.5(35.4)% of power-added efficiency(PAE), -46(-45) dBc of adjacent-channel power ratio (ACPR), and 23.7(26.9) dB of gain
Dong-Muk CHOI Che-Young KIM Kwang-Hee KWON
This letter presents a Monte-Carlo FDTD technique to determine the scattered field from a perfectly conducting fractal surface from which the useful information on the incoherent pattern tendency could be observed. A one-dimensional fractal surface was generated by the bandlimited Weierstrass function. In order to verify the numerical results by this technique, these results are compared with those of Kirchhoff approximations, which show a good match between them. To investigate the incoherent pattern tendency involved, the dependence of the fitting curve slope on the different D and is discussed for the bistatic and back scattering case, respectively.
Peilin LIU Li JIANG Hiroshi NAKAYAMA Toshiyuki YOSHITAKE Hiroshi KOMAZAKI Yasuhiro WATANABE Hisakatsu ARAKI Kiyonori MORIOKA Shinhaeng LEE Hajime KUBOSAWA Yukio OTOBE
We have developed a low-power, high-performance MPEG-4 codec LSI for mobile video applications. This codec LSI is capable of up to CIF 30-fps encoding, making it suitable for various visual applications. The measured power consumption of the codec core was 9 mW for QCIF 15-fps codec operation and 38 mW for CIF 30-fps encoding. To provide an error-robust MPEG-4 codec, we implemented an error-resilience function in the LSI. We describe the techniques that have enabled low power consumption and high performance and discuss our test results.
An accurate, fast delay calculation method suitable for high-performance, low-power LSI design is proposed. The delay calculation is composed of two steps: (1) the gate delay is calculated by using an effective capacitance obtained from a simple model we propose; and (2) the interconnect delay is also calculated from the effective capacitance and modified by using the gate-output transition time. The proposed delay calculation halves the error of a conventional rough calculation, achieving a computational error within 10% per gate stage. The mathematical models are simple enough that the method is suitable for quick delay calculation and logic circuit optimization in the early stages of LSI design. A delay optimization tool using this delay calculation method reduced the worst path delay of a multiply-add module by 11.2% and decreased the sizes of 58.1% of the gates.
Masayuki MIYAMA Osamu TOOYAMA Naoki TAKAMATSU Tsuyoshi KODAKE Kazuo NAKAMURA Ai KATO Junichi MIYAKOSHI Kousuke IMAMURA Hideo HASHIMOTO Satoshi KOMATSU Mikio YAGI Masao MORIMOTO Kazuo TAKI Masahiko YOSHIMOTO
This paper describes an ultra low power, motion estimation (ME) processor for MPEG2 HDTV resolution video. It adopts a Gradient Descent Search (GDS) algorithm that drastically reduces required computational power to 6 GOPS. A SIMD datapath architecture optimized for the GDS algorithm decreases the clock frequency and operating voltage. A low power 3-port SRAM with a write-disturb-free cell array arrangement is newly designed for image data caches of the processor. The proposed ME processor contains 7-M transistors, integrated in 4.50 mm 3.35 mm area using 0.13 µm CMOS technology. Estimated power consumption is less than 100 mW at 81 MHz@1.0 V. The processor is applicable to a portable HDTV system.
In this paper, two low power hardware structures essential for MPEG-4 video codec are proposed for portable applications. First, an adaptive bit resolution control (ABRC) scheme is proposed for a processing element (PE) in a systolic-array type motion estimator (ME). By appropriately modifying the datapath of PE to exploit the correlations in pixel values, its structure is optimized in terms of both hardware cost and low power consumption. As a result, power is saved up to 29% compared with a conventional PE while the computation accuracy is preserved and the overhead is kept negligible. Second, a low power motion compensation (MC) accelerator is proposed. By embedding DRAM whose structure is optimized for low power consumption, the power consumption for external data I/Os is dramatically reduced. In addition, distributed nine-tiled block mapping (DNTBM) with partial activation scheme in the frame buffer reduces the power for accessing frame buffer up to 31% compared to a conventional 1-bank tiled mapping. With the proposed MC accelerator, MPEG-4 SP@L1 decoding system is fabricated using 0.18 µm embedded memory logic (EML) technology.
Tadayoshi ENOMOTO Akira KOTABE
A fast-motion-estimation (ME) algorithm called a "breaking-off-search (BOS)" was developed. It can improve processing speed of the full-search (FS) method by a factor of 3.4. The BOS algorithm can not only sometimes achieve better visual quality than FS, but can also solve visual degradation problems associated with conventional fast-ME algorithms whenever picture patterns change (i. e. , presence of scene changes). The power dissipation of a 0.6-µ m CMOS parallel Wallace-tree motion estimator using BOS was reduced to about 281 mW which was 1/28.7 that of the 0.6-µ m CMOS binary-tree motion estimator using FS.
Tomoharu SHIBUYA Kohichi SAKANIWA
A parity check matrix for a binary linear code defines a bipartite graph (Tanner graph) which is isomorphic to a subgraph of a factor graph which explains a mechanism of the iterative decoding based on the sum-product algorithm. It is known that this decoding algorithm well approximates MAP decoding, but degradation of the approximation becomes serious when there exist cycles of short length, especially length 4, in Tanner graph. In this paper, based on the generating idempotents, we propose some methods to design parity check matrices for cyclic codes which define Tanner graphs with no cycles of length 4. We also show numerically error performance of cyclic codes by the iterative decoding implemented on factor graphs derived from the proposed parity check matrices.
A new pilot-aided channel estimation technique is proposed and applied to wideband CDMA (WCDMA) systems. This technique is based on conventional pilot-aided decision directed (PADD) algorithms. In this letter, conventional PADD algorithms are studied extensively and a modified PADD algorithm is presented. The performance of the proposed algorithm is compared with that of conventional PADD algorithms through computer simulations in Rayleigh fading environments.
Naoya WATANABE Fukashi MORISHITA Yasuhiko TAITO Akira YAMAZAKI Tetsushi TANIZAKI Katsumi DOSAKA Yoshikazu MOROOKA Futoshi IGAUE Katsuya FURUE Yoshihiro NAGURA Tatsunori KOMOIKE Toshinori MORIHARA Atsushi HACHISUKA Kazutami ARIMOTO Hideyuki OZAKI
This paper describes an Embedded DRAM Hybrid Macro, which supports various memory specifications. The eDRAM module generator with Hybrid Macro provides more than 120,000 eDRAM configurations. This eDRAM includes a new architecture called Auto Signal Management (ASM) architecture, which automatically adjusts the timing of the control signals for various eDRAM configurations, and reduces the design Turn Around Time. An Enhanced-on-chip Tester performs the maximum 512b I/O pass/fail simultaneous judgments and the real time repair analysis. The eDRAM testing time is reduced to about 1/64 of the time required using the conventional technique. A test chip is fabricated using a 0.18 µm 4-metal embedded DRAM technology, which utilizes the triple-well, dual-Tox, and Co salicide process technologies. This chip achieves a wide voltage range operation of 1.2 V at 100 MHz to 1.8 V at 200 MHz.