This work first investigates two existing check node unit (CNU) architectures for LDPC decoding: self-message-excluded CNU (SME-CNU) and two-minimum CNU (TM-CNU) architectures, and analyzes their area and timing complexities based on various realization approaches. Compared to TM-CNU architecture, SME-CNU architecture is faster in speed but with much higher complexity for comparison operations. To overcome this problem, this work proposes a novel systematic optimization algorithm for comparison operations required by SME-CNU architectures. The algorithm can automatically synthesize an optimized fast comparison operation that guarantees a shortest comparison delay time and a minimized total number of 2-input comparators. High speed is achieved by adopting parallel divide-and-conquer comparison operations, while the required comparators are minimized by developing a novel set construction algorithm that maximizes shareable comparison operations. As a result, the proposed design significantly reduces the required number of comparison operations, compared to conventional SME-CNU architectures, under the condition that both designs have the same speed performance. Besides, our preliminary hardware simulations show that the proposed design has comparable hardware complexity to low-complexity TM-CNU architectures.
Takayuki NOZAKI Kenta KASAI Kohichi SAKANIWA
The fixed points of the belief propagation decoder for non-binary low-density parity-check (LDPC) codes are referred to as stopping constellations. In this paper, we give the stopping constellation distributions for the irregular non-binary LDPC code ensembles defined over the general linear group. Moreover, we derive the exponential growth rate of the average stopping constellation distributions in the limit of large codelength.
Pinhui KE Zheng YANG Jie ZHANG
We determine the autocorrelations of the quaternary sequence over F4 and its modified version introduced by Du et al. [X.N. Du et al., Linear complexity of quaternary sequences generated using generalized cyclotomic classes modulo 2p, IEICE Trans. Fundamentals, vol.E94-A, no.5, pp.1214–1217, 2011]. Furthermore, we reveal a drawback in the paper aforementioned and remark that the proof in the paper by Kim et al. can be simplified.
Many scientific applications require efficient variable-precision floating-point arithmetic. This paper presents a special-purpose Very Large Instruction Word (VLIW) architecture for variable precision floating-point arithmetic (VV-Processor) on FPGA. The proposed processor uses a unified hardware structure, equipped with multiple custom variable-precision arithmetic units, to implement various variable-precision algebraic and transcendental functions. The performance is improved through the explicitly parallel technology of VLIW instruction and by dynamically varying the precision of intermediate computation. We take division and exponential function as examples to illustrate the design of variable-precision elementary algorithms in VV-Processor. Finally, we create a prototype of VV-Processor unit on a Xilinx XC6VLX760-2FF1760 FPGA chip. The experimental results show that one VV-Processor unit, running at 253 MHz, outperforms the approach of a software-based library running on an Intel Core i3 530 CPU at 2.93 GHz by a factor of 5X-37X for basic variable-precision arithmetic operations and elementary functions.
Bin-Shyan JONG Chi-Kang KAO Juin-Ling TSENG Tsong-Wuu LIN
This paper introduces a new dynamic 3D mesh representation that provides 3D animation support of progressive display and drastically reduces the amount of storage space required for 3D animation. The primary purpose of progressive display is to allow viewers to get animation as quickly as possible, rather than having to wait until all data has been downloaded. In other words, this method allows for the simultaneous transmission and playing of 3D animation. Experiments show that coarser 3D animation could be reconstructed with as little as 150 KB of data transferred. Using the sustained transmission of refined operators, viewers feel that resolution approaches that of the original animation. The methods used in this study are based on a compression technique commonly used in 3D animation - clustered principle component analysis, using the linearly independent rules of principle components, so that animation can be stored using smaller amounts of data. This method can be coupled with streaming technology to reconstruct animation through iterative updating. Each principle component is a portion of the streaming data to be stored and transmitted after compression, as well as a refined operator during the animation update process. This paper considers errors and rate-distortion optimization, and introduces weighted progressive transmitting (WPT), using refined sequences from optimized principle components, so that each refinement yields an increase in quality. In other words, with identical data size, this method allows each principle component to reduce allowable error and provide the highest quality 3D animation.
Masami AKAMINE Jitendra AJMERA
This paper proposes likelihood smoothing techniques to improve decision tree-based acoustic models, where decision trees are used as replacements for Gaussian mixture models to compute the observation likelihoods for a given HMM state in a speech recognition system. Decision trees have a number of advantageous properties, such as not imposing restrictions on the number or types of features, and automatically performing feature selection. This paper describes basic configurations of decision tree-based acoustic models and proposes two methods to improve the robustness of the basic model: DT mixture models and soft decisions for continuous features. Experimental results for the Aurora 2 speech database show that a system using decision trees offers state-of-the-art performance, even without taking advantage of its full potential and soft decisions improve the performance of DT-based acoustic models with 16.8% relative error rate reduction over hard decisions.
Tetsunao MATSUTA Tomohiko UYEMATSU
The multiple-access channel (MAC) becomes very popular in various communication systems, because multi-terminal communication systems have been widely used in practical systems, e.g., mobile phones and P2P, etc. For some MACs, it is known that feedback can enlarge the capacity region, where the capacity region is the set of rate pairs such that the error probability can be made arbitrarily small for sufficiently large block length. The capacity region for general MACs, which are not required to satisfy ergodicity and stationarity with perfect feedback was first shown by Tatikonda and Mitter without the proof, where perfect feedback means that the channel output is perfectly fed back to senders. In this paper, we generalize Tatikonda and Mitter's result to the case of deterministic feedback, where the values of deterministic functions of past channel outputs is fed back to senders. We show that the capacity region for general MACs with deterministic feedback can be represented by the information-spectrum formula introduced by Han and Verdu, and directed information introduced by Massey. We also investigate the compound MAC problem, the ε-coding problem, the strong converse property and the cost constraint problem for general MACs with deterministic feedback.
Hwi-Gang KIM Sung-Hak LEE Tae-Wuk BAE Kyu-Ik SOHNG
An image appearance model called iCAM06 was designed for high dynamic range (HDR) image rendering. The dynamic range of an HDR image needs to be mapped on output devices, which is called tone compression or tone mapping. The iCAM06, the representative HDR rendering algorithm, uses tone compression for image reproduction on the low dynamic range of output devices. However, color saturation reduction occurs during its tone compression process. We propose a saturation correction method using the inverse compensation in order to recover the saturation reduction in the iCAM06. Experimental results show that the proposed method has better performance than the iCAM06 from the viewpoint of saturation accuracy and rendering preference.
Tetsuya IZU Yumi SAKEMI Masahiko TAKENAKA
EMV signature is one of specifications for authenticating credit and debit card data, which is based on ISO/IEC 9796-2 signature scheme. At CRYPTO 2009, Coron, Naccache, Tibouchi, and Weinmann proposed a new forgery attack against the signature ISO/IEC 9796-2 (CNTW attack) [2]. They also briefly discussed the possibility when the attack is applied to the EMV signatures. They showed that the forging cost is $45,000 and concluded that the attack could not forge them for operational reason. However their results are derived from not fully analysis under only one condition. The condition they adopt is typical case. For security evaluation, fully analysis and an estimation in worst case are needed. This paper shows cost-estimation of CNTW attack against EMV signature in detail. We constitute an evaluate model and show cost-estimations under all conditions that Coron et al. do not estimate. As results, this paper contribute on two points. One is that our detailed estimation reduced the forgery cost from $45,000 to $35,200 with same condition as [2]. Another is to clarify a fact that EMV signature can be forged with less than $2,000 according to a condition. This fact shows that CNTW attack might be a realistic threat.
In this letter, a two-stage TOA estimation scheme is proposed for positioning in OFDM-based WLAN systems under indoor environments. The estimation scheme consists of coarse estimation and fine estimation. The presented scheme effectively exploits the preamble of the OFDM-based WLAN for accurate estimation. The simulation results exhibit that the performance of the proposed approach is comparable to that of super-resolution estimation even with lower computational complexity.
Hideaki ORII Hideaki KAWANO Hiroshi MAEDA Norikazu IKOMA
We propose a novel background and foreground estimation algorithm in MAP-MRF approach for binarization of degraded document image. In the proposed algorithm, an assumption that background whiteness and foreground blackness is not employed differently from the conventional algorithm, and we employ character's irregularities based on local statistics. This makes the method possible to apply to the image with various colored characters, ex. outlined characters by colored background. The effectiveness and the validity are shown by applying the proposed method to various degraded document images.
Adaptive interference suppression strategies based on the transform domain approach are proposed for a satellite on-board filter bank under tone-type interferences. In the proposed methods, the three kinds of algorithms to compute the threshold level are jointly employed with the notch filter or the clipper. Simulation results show that the proposed schemes significantly improve performance under interfering environments, compared to the no suppression case.
Cheng-Min LIN Shyi-Shiou WU Tse-Yi CHEN
Universal Plug and Play (UPnP) allows devices automatic discovery and control of services available in those devices connected to a Transmission Control Protocol/ Internet Protocol (TCP/IP) network. Although many products are designed using UPnP, little attention has been given to UPnP related to modeling and performance analysis. This paper uses a framework of Generalized Stochastic Petri Net (GSPN) to model and analyze the behavior of UPnP systems. The framework includes modeling UPnP, reachability decomposition, GSPN analysis, and reward assignment. Then, the Platform Independent Petri net Editor 2 (PIPE2) tool is used to model and evaluate the controllers in terms of power consumption, system utilization and network throughput. Through quantitative analysis, the steady states in the operation and notification stage dominate the system performance, and the control point is better than the device in power consumption but the device outperforms the control point in evaluating utilization. The framework and numerical results are useful to improve the quality of services provided in UPnP devices.
Tetsuki TANIGUCHI Yoshio KARASAWA Nobuo NAKAJIMA
In cellular systems, particular in the cell edge, the user terminals (UTs) are suffered from the attenuation of the signal from their target base station (BS) and the relatively strong interferences from BSs of other users. This paper investigates the performance improvement under this bad situation by BS cooperation (BSC) in the downlink scenario using multiantenna transmission assuming the perfect channel state information (CSI), and compares the effectiveness of several strategies based on a three cell model. Through computer simulations, the performance improvement by BSC is verified. Then the result is extended to multiple stream transmission utilizing the feature of multiantenna, and advantage of BSC with data sharing is shown.
Shinichiro MIYAZAKI Shoichiro YAMASAKI Ryuji KOHNO
This paper proposes a single-carrier transmission method based on an overlap frequency-domain equalizing (FDE) and a coherent averaging. FDE is a block-based equalizing technique using discrete Fourier transform. A cyclic prefix is often used to avoid inter-block interference under multipath channel conditions, which reduces transmission efficiency. An overlap FDE is a technique to avoid the cyclic prefix insertion, but the residual interferences often exist after the FDE processing according to the channel conditions. The method proposed in this paper suppresses the residual interferences by applying a coherent averaging to the FDE outputs and improve the equalization performances. Computer simulation shows the effect of the proposed technique over the multipath channels.
Zhaocheng WANG Jintao WANG Linglong DAI
This paper proposes a novel scheme to reduce the complexity of existing transmit diversity solutions to time domain synchronous OFDM (TDS-OFDM). The space shifted constant amplitude zero autocorrelation (CAZAC) sequence based preamble is proposed for channel estimation. Two flexible frame structures are proposed for adaptive system design as well as cyclicity reconstruction of the received inverse discrete Fourier transform (IDFT) block. With regard to channel estimation and cyclicity reconstruction, the complexity of the proposed scheme is only around 7.20% of that of the conventional solutions. Simulation results demonstrate that better bit error rate (BER) performance can be achieved over doubly selective channels.
Fagen LI Jiang DENG Tsuyoshi TAKAGI
Authenticated encryption schemes are very useful for private and authenticated communication. In 2010, Rasslan and Youssef showed that the Hwang et al.'s authenticated encryption scheme is not secure by presenting a message forgery attack. However, Rasslan and Youssef did not give how to solve the security issue. In this letter, we give an improvement of the Hwang et al.'s scheme. The improved scheme not only solves the security issue of the original scheme, but also maintains its efficiency.
A novel grouping approach to segment text lines from handwritten documents is presented. In this text line segmentation algorithm, for each text line, a text string that connects the center points of the characters in this text line is built. The text lines are then segmented using the resulting text strings. Since the characters of the same text line are situated close together and aligned on a smooth curve, 2D tensor voting is used to reduce the conflicts when building these text strings. First, the text lines are represented by separate connected components. The center points of these connected components are then encoded by second order tensors. Finally, a voting process is applied to extract the curve saliency values and normal vectors, which are used to remove outliers and build the text strings. The experimental results obtained from the test dataset of the ICDAR 2009 Handwriting Segmentation Contest show that the proposed method generates high detection rate and recognition accuracy.
Gregory BLANC Youki KADOBAYASHI
Modern web applications incorporate many programmatic frameworks and APIs that are often pushed to the client-side with most of the application logic while contents are the result of mashing up several resources from different origins. Such applications are threatened by attackers that often attempts to inject directly, or by leveraging a stepstone website, script codes that perform malicious operations. Web scripting based malware proliferation is being more and more industrialized with the drawbacks and advantages that characterize such approach: on one hand, we are witnessing a lot of samples that exhibit the same characteristics which make these easy to detect, while on the other hand, professional developers are continuously developing new attack techniques. While obfuscation is still a debated issue within the community, it becomes clear that, with new schemes being designed, this issue cannot be ignored anymore. Because many proposed countermeasures confess that they perform better on unobfuscated contents, we propose a 2-stage technique that first relieve the burden of obfuscation by emulating the deobfuscation stage before performing a static abstraction of the analyzed sample's functionalities in order to reveal its intent. We support our proposal with evidence from applying our technique to real-life examples and provide discussion on performance in terms of time, as well as possible other applications of proposed techniques in the areas of web crawling and script classification. Additionally, we claim that such approach can be generalized to other scripting languages similar to JavaScript.
Fahad QURESHI Oscar GUSTAFSSON
In this work we consider optimized twiddle factor multipliers based on shift-and-add-multiplication. We propose a low-complexity structure for twiddle factors with a resolution of 32 points. Furthermore, we propose a slightly modified version of a previously reported multiplier for a resolution of 16 points with lower round-off noise. For completeness we also include results on optimal coefficients for eight-points resolution. We perform finite word length analysis for both coefficients and round-off errors and derive optimized coefficients with minimum complexity for varying requirements.