In this paper, a generalized Montgomery multiplication algorithm in GF(2m) using the Toeplitz matrix-vector representation is presented. The hardware architectures derived from this algorithm provide low-complexity bit-parallel systolic multipliers with trinomials and pentanomials. The results reveal that our proposed multipliers reduce the space complexity of approximately 15% compared with an existing systolic Montgomery multiplier for trinomials. Moreover, the proposed architectures have the features of regularity, modularity, and local interconnection. Accordingly, they are well suited to VLSI implementation.
Takahiro MATSUDA Nuttapong ATTRAPADUNG Goichiro HANAOKA Kanta MATSUURA Hideki IMAI
Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.
Masashi SUGIYAMA Motoaki KAWANABE Gilles BLANCHARD Klaus-Robert MULLER
Obtaining the best linear unbiased estimator (BLUE) of noisy signals is a traditional but powerful approach to noise reduction. Explicitly computing the BLUE usually requires the prior knowledge of the noise covariance matrix and the subspace to which the true signal belongs. However, such prior knowledge is often unavailable in reality, which prevents us from applying the BLUE to real-world problems. To cope with this problem, we give a practical procedure for approximating the BLUE without such prior knowledge. Our additional assumption is that the true signal follows a non-Gaussian distribution while the noise is Gaussian.
Hochul LEE Youngchang YOON Ickhyun SONG Hyungcheol SHIN
As the gate area decreases to the order of a square micron, individual trapping events can be detected as fluctuations between discrete levels of the drain current, known as random telegraph signal (RTS) noise. Many circuit application areas such as CMOS Image sensor and flash memory are already suffering from RTS noise. Especially, in case of flash memory, FN stress causes threshold voltage shift problems due to generation of additional oxide traps, which degrades circuit performance. In this paper, we investigated how FN stress effects on RTS noise behavior in MOSFET and monitored it in both the time domain and frequency domain.
In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.
In this letter we propose an adaptive beamforming algorithm that efficiently suppresses interferences using a structured interference covariance matrix. The proposed algorithm provides high performance by exploiting angle diversity, especially in cellular mobile environments where the angular spread of a received signal is relatively small. We verify the superiority of the proposed algorithm to the well known linearly constrained minimum variance (LCMV) and reference signal-based algorithms.
Nobuo KARAKI Takashi NANMOTO Satoshi INOUE
This paper presents an asynchronous design technique, an enabler for the emerging technology of flexible microelectronics that feature low-temperature processed polysilicon (LTPS) thin-film transistors (TFT) and surface-free technology by laser annealing/ablation (SUFTLA®). The first design instance chosen is an 8-bit microprocessor. LTPS TFTs are good for realizing displays having integrated VLSI circuit at lower costs. However, LTPS TFTs have drawbacks, including substantial deviations in characteristics and the self-heating phenomenon. To solve these problems, the authors adopted the asynchronous circuit design technique and developed an asynchronous design language called Verilog+, which is based on a subset of Verilog HDL® and includes minimal primitives used for describing the communications between modules, and the dedicated tools including a translator called xlator and a synthesizer called ctrlsyn. The flexible 8-bit microprocessor stably operates at 500 kHz, drawing 180 µA from a 5 V power source. The microprocessor's electromagnetic emissions are 21 dB less than those of the synchronous counterpart.
Chung-Liang CHANG Jyh-Ching JUANG
In air navigation, the rotation of aircraft results in the discontinuous tracking of GNSS signals. As the platform rotates, the GNSS signals are subject to blanking effects. To solve this problem, a ring-type antenna array is used to prevent signal discontinuity and a hypothesis-test based detection scheme is developed so that the correct antenna combination can be formed to provide uninterrupted reception of GNSS signals in the presence of blanking, noise, and interferences. A fixed threshold detection scheme is first developed by assuming that the statistics of the noise are known. It is shown that the scheme is capable of differentiating signal from noise at each antenna element. To account for the interference effect, a multiple hypothesis test scheme, together with an adaptive selection rule, is further developed. Through this detection and selection process, it is shown, through simulations, that the desired GNSS signals can be extracted and successfully tracked in the presence of blanking and co-channel interference.
Taek-Young YOUN Young-Ho PARK Taekyoung KWON Soonhak KWON Jongin LIM
Previously proposed batch signature schemes do not allow a signer to generate a signature immediately for sequentially asked signing queries. In this letter, we propose flexible batch signatures which do not need any waiting period and have very light computational overhead. Therefore our schemes are well suited for low power devices.
Naoya MOCHIKI Tetsuji OGAWA Tetsunori KOBAYASHI
We propose a new type of direction-of-arrival estimation method for robot audition that is free from strict head related transfer function estimation. The proposed method is based on statistical pattern recognition that employs a ratio of power spectrum amplitudes occurring for a microphone pair as a feature vector. It does not require any phase information explicitly, which is frequently used in conventional techniques, because the phase information is unreliable for the case in which strong reflections and diffractions occur around the microphones. The feature vectors we adopted can treat these influences naturally. The effectiveness of the proposed method was shown from direction-of-arrival estimation tests for 19 kinds of directions: 92.4% of errors were reduced compared with the conventional phase-based method.
Masoomeh TORABZADEH Yusheng JI
In multiple-input multiple-output (MIMO) cellular networks, certain schedulers have two independent phases: the first selects a group of users based on the scheduler criterion, and the second assigns the selected users to the transmit antennas by using an assignment scheme taking into consideration capacity maximization. Other schedulers directly select among the available channels between users and the base station in a centralized way. The schedulers of the first category can be implemented with lower complexity compared with the schedulers of the second category. For the first category, we propose three near-optimal assignment schemes with low complexities. We conducted a simulation in which the mobility of users was considered that demonstrated the superior performance of our assignment schemes. Furthermore, we analytically demonstrate their efficiency.
Code acquisition performance in the Direct-Sequence Code-Division Multiple-Access (DS/CDMA) communication system is strongly related to the quality of the communication systems. The performance is assessed by (i) code acquisition time; (ii) precision; and (iii) complexity for implementation. This paper applies the method of maximum likelihood (ML) to estimation of propagation delay in DS/CDMA communications, and proposes a low-complexity method for code acquisition. First, a DS/CDMA system model and properties of outputs with a passive matched-filter receiver are reviewed, and a statistical problem in code acquisition is mentioned. Second, an error-controllable code acquisition method based on the maximum likelihood is discussed. Third, a low-complexity ML code acquisition method is proposed. It is shown that the code acquisition time with the low-complexity method is about 1.5 times longer than that with the original ML method, e.g. 13 data periods under 4.96 dB.
Xu ZHANG Xiaohong JIANG Susumu HORIGUCHI
Three dimensional (3D) integrated circuits (ICs) have the potential to significantly enhance VLSI chip performance, functionality and device packing density. Interconnects delay and signal integrity issues are critical in chip design. In this paper, we extend the idea of redundant via insertion of conventional 2D ICs and propose an approach for vias insertion/placement in 3D ICs to minimize the propagation delay of interconnects with the consideration of signal integrity. The simulation results based on a 65 nm CMOS technology demonstrate that our approach in general can result in a 9% improvement in average delay and a 26% decrease in reflection coefficient. It is also shown that the proposed approach can be more effective for interconnects delay improvement when it is integrated with the buffer insertion in 3D ICs.
Shin-ichi OHKAWA Hiroo MASUDA Yasuaki INOUE
We have proposed a random curved surface model as a new mathematical concept which enables the expression of spatial correlation. The model gives us an appropriate methodology to deal with the systematic components of device variation in an LSI chip. The key idea of the model is the fitting of a polynomial to an array of Gaussian random numbers. The curved surface is expressed by a new extension from the Legendre polynomials to form two-dimensional formulas. The formulas were proven to be suitable to express the spatial correlation with reasonable computational complexity. In this paper, we show that this approach is useful in analyzing characteristics of device variation of actual chips by using experimental data.
Keisuke INOUE Mineo KANEKO Tsuyoshi IWAGAKI
As the feature size of VLSI becomes smaller, delay variations become a serious problem in VLSI. In this paper, we propose a novel class of robustness for a datapath against delay variations, which is named structural robustness against delay variation (SRV), and propose sufficient conditions for a datapath to have SRV. A resultant circuit designed under these conditions has a larger timing margin to delay variations than previous designs without sacrificing effective computation time. In addition, under any degree of delay variations, we can always find an available clock frequency for a datapath having SRV property to operate correctly, which could be a preferable characteristic in IP-based design.
Shinpei HAYASHI Junya KATADA Ryota SAKAMOTO Takashi KOBAYASHI Motoshi SAEKI
One of the approaches to improve program understanding is to extract what kinds of design pattern are used in existing object-oriented software. This paper proposes a technique for efficiently and accurately detecting occurrences of design patterns included in source codes. We use both static and dynamic analyses to achieve the detection with high accuracy. Moreover, to reduce computation and maintenance costs, detection conditions are hierarchically specified based on Pree's meta patterns as common structures of design patterns. The usage of Prolog to represent the detection conditions enables us to easily add and modify them. Finally, we have implemented an automated tool as an Eclipse plug-in and conducted experiments with Java programs. The experimental results show the effectiveness of our approach.
Hoojin LEE Jeffrey G. ANDREWS Edward J. POWERS
Space-time block codes (STBCs) from coordinate interleaved orthogonal designs (CIODs) have attracted a great deal of attention due to their full-diversity and linear maximum likelihood (ML) decodability. In this letter, we propose a simple detection technique, particularly for full-rate STBCs from CIODs to overcome the performance degradation caused by time-selective fading channels. Furthermore, we evaluate the effects of time-selective fading channels and imperfect channel estimation on STBCs from CIODs by using a newly-introduced index, the results of which demonstrate that full-rate STBCs from CIODs are more robust against time-selective fading channels than conventional full-rate STBCs.
The present paper describes a method for the construction of a zero-correlation zone sequence set from a perfect sequence. Both the cross-correlation function and the side-lobe of the auto-correlation function of the proposed sequence sets are zero for phase shifts within the zero-correlation zone. These sets can be generated from an arbitrary perfect sequence, the length of which is the product of a pair of odd integers ((2n+1)(2k+1) for k ≥ 1 and n ≥ 0). The proposed sequence construction method can generate an optimal zero-correlation zone sequence set that achieves the theoretical bounds of the sequence member size given the size of the zero-correlation zone and the sequence period. The peak in the out-of-phase correlation function of the constructed sequences is restricted to be lower than the half of the power of the sequence itself. The proposed sequence sets could successfully provide CDMA communication without co-channel interference, or, in an ultrasonic synthetic aperture imaging system, improve the signal-to-noise ratio of the acquired image.
In this paper, a multiple-valued current-mode (MVCM) circuit based on active-load dual-rail differential logic is proposed for a high-performance arithmetic VLSI system with crosstalk-noise immunity. The use of dual-rail complementary differential-pair circuits (DPCs), whose outputs are summed up by wiring makes it possible to reduce the common-mode noise, and yet enhance the switching speed. By using the diode-connected cross-coupled PMOS active loads, the rapid transition of switching in the DPC is relaxed appropriately, which can also eliminate spiked input noise. It is demonstrated that the noise reduction ratio and the switching delay of the proposed MVCM circuit in a 90 nm CMOS technology is superior to those of the corresponding ordinary implementation.
Sumek WISAYATAKSIN Dongju LI Tsuyoshi ISSHIKI Hiroaki KUNIEDA
We propose a low cost and stand-alone platform-based SoC for H.264/AVC decoder, whose target is practical mobile applications such as a handheld video player. Both low cost and stand-alone solutions are particularly emphasized. The SoC, consisting of RISC core and decoder core, has advantages in terms of flexibility, testability and various I/O interfaces. For decoder core design, the proposed H.264/AVC coprocessor in the SoC employs a new block pipelining scheme instead of a conventional macroblock or a hybrid one, which greatly contribute to reducing drastically the size of the core and its pipelining buffer. In addition, the decoder schedule is optimized to block level which is easy to be programmed. Actually, the core size is reduced to 138 KGate with 3.5 kbyte memory. In our practical development, a single external SDRAM is sufficient for both reference frame buffer and display buffer. Various peripheral interfaces such as a compact flash, a digital broadcast receiver and a LCD driver are also provided on a chip.