Fingerprints are useful for biometric purposes because of their well known properties of distinctiveness and persistence over time. However, owing to skin conditions or incorrect finger pressure, original fingerprint images always contain noise. Especially, some of them contain useless components, which are often mistaken for the terminations that are an essential minutia of a fingerprint. Mathematical Morphology (MM) is a powerful tool in image processing. In this paper, we propose a linear time algorithm to eliminate impulsive noise and useless components, which employs generalized and ordinary morphological operators based on Euclidean distance transform. There are two contributions. The first is the simple and efficient MM method to eliminate impulsive noise, which can be restricted to a minimum number of pixels. We know the performance of MM is heavily dependent on structuring elements (SEs), but finding an optimal SE is a difficult and nontrivial task. So the second contribution is providing an automatic approach without any experiential parameter for choosing appropriate SEs to eliminate useless components. We have developed a novel algorithm for the binarization of fingerprint images [1]. The information of distance transform values can be obtained directly from the binarization phase. The results show that using this method on fingerprint images with impulsive noise and useless components is faster than existing denoising methods and achieves better quality than earlier methods.
Marcelo E. KAIHARA Naofumi TAKAGI
A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.
Wei-Chi KU Shen-Tien CHANG Min-Hung CHIANG
Recently, Lin, Hwang, and Li proposed an efficient remote authentication scheme using smart cards for multi-server architecture based on the geometric property of the Euclidean plane. Herein, we show that their scheme is vulnerable to two forgery attacks and a password-guessing attack, and is not easily repairable. Furthermore, their scheme lacks a proper user eviction mechanism.
Pierre-Alain FAYOLLE Benjamin SCHMITT Yuichiro GOTO Alexander PASKO
We present an approach and a web-based system implementation for modeling shapes using real distance functions. The system consists of an applet supporting the HyperFun modeling language. The applet is extended with primitives defined by Euclidean distance from a point to the surface of the shape. Set-theoretic operations (union, intersection, difference) that provide an approximation of the Euclidean distance to a shape built in a constructive way are introduced. Such operations have a controllable error of the exact Euclidean distance to the shape and preserve C1 continuity of the overall function, which is an important condition for further operations and applications. The proposed system should help model various shapes, store them in a concise form, and exchange them easily between different entities on a network. The applet offers also the possibility to export the models defined in the HyperFun language to other formats for raytracing or rapid prototyping.
In this letter, we propose a fast modular reduction method over Euclidean rings, which is a generalization of Barrett's reduction algorithm over the ring of integers. As an application, we construct new universal hash function families whose operations are modular arithmetic over a Euclidean ring, which can be any of three rings, the ring of integers, the ring of Gauss integers and the ring of Eisenstein integers. The implementation of these families is efficient by using our method.
In this paper, a novel methodology for designing and analyzing high performance sigma-delta leapfrog modulators for ultra-high resolution analog-to-digital (A/D) converters is presented. The less sensitive topology, the leapfrog topology, in component variations is analyzed by considering the noise transfer function (NTF). By using theoretical analysis, the loop coefficients are constrained to a small, clear and definite range called the stable region (SR). With the output voltage limited within 2 V, an absolutely stable region (ASR) is obtained. A program that analyzes and generates the required coefficients is constructed for easily designing this topology. For a 256 over-sampling ratio (OSR) and the coefficients from ASR, the signal to noise ratio (SNR) and dynamic range (DR) are 105 dB and 100 dB, respectively. In accordance with the behavior simulation results, the system is not only stable and efficient but also suitable for high-resolution applications.
Yuh-Rau WANG Shi-Jinn HORNG Yu-Hua LEE Pei-Zong LEE
Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.
Wataru MATSUMOTO Weigang XU Hideki IMAI
We propose a scheme for the design of irregular low-density parity-check (LDPC) codes based on Euclidian Geometry using Latin square matrices of random sequence. Our scheme is a deterministic method that allows the easy design of good irregular LDPC codes for any code rate and degree distribution. We optimize the LDPC codes using the Gaussian approximation method. A Euclidean Geometry LDPC code (EG-LDPC) is used as the basis for the construction of an irregular LDPC code. The base EG-LDPC code is extended by splitting rows and columns using a table of Latin square matrices of random sequence to determine the edges along which to split. We provide simulation results for codes constructed in this manner evaluated in terms of bit error rate (BER) performance in AWGN channels. We believe that our scheme is superior in terms of computational requirements and resulting BER performance in comparison to creation of irregular LDPC codes by means of random construction using a search algorithm to exclude cycles of length four.
Masaaki HARADA Takaya YAMAZATO Hiraku OKADA Masaaki KATAYAMA Akira OGAWA
In an attempt to improve the performance under frequency selective fading environment, we develop in this paper an orthogonal frequency division multiplex (OFDM) system in which adaptive interleaving is applied. The adaptive interleaving is a method that assigns symbols adaptively to the subcarriers in order to cope with frequency selective fading based on a channel state information (CSI) sent back from the reception end. The concept of adaptive interleaving is to maximize a free Euclidean distance in the limited interleave size. In this paper, we extend the method by an introduction of bit interleaving and multiple trellis coded modulation (MTCM). MTCM assigns two or more symbols to one trellis branch and shows good performance in frequency selective fading. If we could assign those set of symbols with an aid of the adaptive interleaving, the performance improvement can be expected. Another improvement method considered in this paper is the use of bit interleaving. The bit interleaving techniques randomize the effect of channel more efficiently compared to the case of symbols interleaving. Thus the further performance improvement is expected. One draw back is that since the interleaving process is done in bit level, bit interleaving can not be applied to TCM nor MTCM. In this paper, we mainly focus on adaptive bit and symbol interleaving and discuss the performance from the point of interleaving effect, and the error correcting code (convolutional code and MTCM).
Balaji Sundar RAJAN Ganapathy VISWANATH
The asymptotic Elias upper bound of codes designed for Hamming distance is well known. Piret and Ericsson have extended this bound for codes over symmetric PSK signal sets with Euclidean distance and for codes over signal sets that form a group, with general distance function respectively. The tightness of these bounds depend on a choice of a probability distribution, and finding the distribution (optimum distribution) that leads to the tightest bound is difficult in general. In this paper we point out that these bounds are valid for codes over the wider class of distance-uniform signal sets (a signal set is referred to be distance-uniform if the Euclidean distance distribution is same from any point of the signal set). We show that optimum distributions can be found for (i) simplex signal sets, (ii) Hamming spaces and (iii) biorthogonal signal set. The classical Elias bound for arbitrary alphabet size is shown to be obtainable by specializing the extended bound to simplex signal sets with optimum distribution. We also verify Piret's conjecture for codes over 5-PSK signal set.
A new class of least-squares algorithms is presented for adaptive filtering. The idea is to use a fixed set of directions and perform line search with one direction at a time in a cyclic fashion. These algorithms are called Euclidean Direction Search (EDS) algorithms. The fast version of this class is called the Fast-EDS or FEDS algorithm. It is shown to have O(N) computational complexity and a convergence rate comparable to that of the RLS algorithm. Computer simulations are presented to illustrate the performance of the new algorithm.
Abdussalam Ibn AHD Hidehiko TANABE Hiroyuki UMEDA
An important goal in communication theory is to construct good minimum squared Euclidean distance (MSED) codes for transmission over additive white Gaussian noise (AWGN) channels. In this paper, a new construction method for the M-ary phase-shift-keyed (M-PSK) codes over the ring structure ZM, the ring of integers modulo M, with a good minimum Euclidean distance, is proposed. The proposed codes are linear when multiple coset leaders are considered. The characteristics and performance levels of the newly constructed codes are analyzed for code length up to n 8. It is found that the proposed codes compare favorably with Piret's codes and Graeffe's method codes on Gaussian channels in terms of decoding complexity, coding gain, and error performance.
In order to compute gcd of polynomials, the Euclidean algorithm is used. We estimate the complexities of known Euclidean algorithms. Further, we propose a heuristic Euclidean algorithm. This is faster than ordinary methods under some special conditions by the use of the recurrent Karatsuba multiplication.
The goal of this paper is to describe a practical and efficient algorithm for computing in the Jacobian of a large class of algebraic curves over a finite field. For elliptic and hyperelliptic curves, there exists an algorithm for performing Jacobian group arithmetic in O(g2) operations in the base field, where g is the genus of a curve. The main problem in this paper is whether there exists a method to perform the arithmetic in more general curves. Galbraith, Paulus, and Smart proposed an algorithm to complete the arithmetic in O(g2) operations in the base field for the so-called superelliptic curves. We generalize the algorithm to the class of Cab curves, which includes superelliptic curves as a special case. Furthermore, in the case of Cab curves, we show that the proposed algorithm is not just general but more efficient than the previous algorithm as a parameter a in Cab curves grows large.
Kazuhiro SHOUNO Yukio ISHIBASHI
In this paper, a realization of an imaginary resistor using an ideal transformer is proposed. In the same fashion as the conventional method, a signal path is divided into a real signal path and an imaginary path. We name circuits which constitute a real signal path and an imaginary signal path, a real circuit and an imaginary circuit, respectively. An imaginary resistor is converted into an ideal transformer embedded between the imaginary circuit and the real circuit. The imaginary circuit becomes a dual circuit of the real circuit. This filter consists of terminating resistors, inductors, capacitors and ideal transformers. This prototype circuit is simulated by using operational amplifiers. A 3rd-order complex Chebyshev bandpass filter is designed and its frequency response is measured. Finally, the sensitivity property of the proposed filter is evaluated by a computer simulation.
Multi-ary Trellis-Coded Modulation (TCM) schemes have been studied for use with digital radio communication systems. Among these TCM schemes, we have already reported the optimum signal constellation of a rate-3/4 trellis-coded (TC) 16-ary Amplitude and Phase Shift Keying (APSK) scheme and computed the minimum Euclidean distance: dfree. In this paper, we evaluate other performance parameters: Nfree and bit error rate (BER) over an additive white Gaussian noise channel, and further investigate the various signal constellations of rate-4/5 TC 32-APSK schemes. It is found that the BER performances of circular-type signal constellations are superior to that of rectangular-type in the TC 16-APSK, and a (24,8) circular type signal constellation is superior to other constellations in the TC 32-APSK.
Hawkins noise model is modified for HBT application. The non-ideal ideality factor of HBT is included in both dynamic resistance and noise figure equations. Emitter resistance is also included. The extraction method of noise resistance Rn is developed. Based on the method, a simple analytic equation of Rn is derived and experimentally verified. The effects of noise sources on minimum noise figure are analyzed. The dominant noise sources are the shot noises of emitter and collector currents. Generally, when the minimum noise figure is measured at various current levels, there exists an current level at which the slope of minimum noise figure curve is zero. The zero slope current level coincides with the current level at which the noise contribution of the emitter and collector shot noises including the cancellation by correlation of two sources is minimum. Parasitic resistance degrades output noise through the shot noise amplification with a minor effect of the thermal noise of itself.
Tetsutaro KOBAYASHI Hikaru MORITA
Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve -- on the prime finite field in particular goals -- public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dusse and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5. 5 times faster.
Franco CHIARALUCE Ennio GAMBI Marta MAZZONE
Two new algorithms are introduced, respectively called syndrome erasing and double syndrome decoding, which permit to achieve fast error correction with a wide class of cyclic codes.
Hidehiko TANABE Mohammad Abdus SALAM Masayasu MITAMURA Hiroyuki UMEDA
In multilevel block modulation codes for QPSK and 8-PSK modulation, a construction of binary component codes is given. These codes have a good minimum Euclidean distance by using different forms of the dependency properties of the binary component codes. Interdependency among component codes is formed by using the binary component subcodes which are derived by the coset decomposition of the binary component codes. The algebraic structures of the codes are investigated to find out how interdependency among component codes gives a good minimum Euclidean distance. First, it is shown that cyclic codes over ZM for M-PSK (M=4,8), where the coding scheme is given by Piret, can be constructed by forming specific interdependency among binary component codes for proposed multilevel coding method. Furthermore, it is shown that better minimum Euclidean distance than above can be obtained by modifying the composition of interdependency among binary component codes. These proposed multilevel codes have algebraic structure of additive group and cyclic property over GF(M). Finally, error performances are compared with those of some code's reference modulation scheme for transmitting the same number of information bits.