This paper presents the average block error rate (BLER) performance of circular 32QAM and 64QAM schemes employing a frequency domain equalizer (FDE) for discrete Fourier transform (DFT)-precoded orthogonal frequency division multiplexing (OFDM) in multipath Rayleigh fading channels. The circular QAM scheme has an advantageous feature in that the fluctuation in the amplitude component is smaller than that for the cross or rectangular QAM scheme. Hence, focusing on the actual received signal-to-noise power ratio (SNR) taking into account a realistic peak-to-average power ratio (PAPR) measure called the cubic metric (CM), we compare the average BLER of the circular 32QAM and 64QAM schemes with those of cross 32QAM and rectangular 64QAM schemes, respectively. We investigate the theoretical throughput of various circular 32QAM and 64QAM schemes based on mutual information from the viewpoint of the minimum Euclidean distance. Link-level simulation results show that the circular 32QAM and 64QAM schemes with independent bit mapping for the phase and amplitude modulations achieves a lower required average received SNR considering the CM than that with the minimum Euclidean distance but with composite mapping of the phase and amplitude modulations. Through extensive link-level simulations, we show the potential benefit of the circular 32QAM and 64QAM schemes in terms of reducing the required average received SNR considering the CM that satisfies the target average BLER compared to the cross 32QAM or rectangular 64QAM scheme.

Continuous phase modulation (CPM) is a very attractive digital modulation scheme, with constant envelope feature and high efficiency in meeting the power and bandwidth requirements. CPM signals with pairs of input sequences that differ in an infinite number of positions and map into pairs of transmitted signals with finite Euclidean distance (ED) are called catastrophic. In the CPM scheme, data sequences that have the catastrophic property are called the catastrophic sequences; they are periodic difference data patterns. The catastrophic sequences are usually with shorter length of the merger. The corresponding minimum normalized squared ED (MNSED) is smaller and below the distance bound. Two important CPM schemes, viz., LREC and LRC schemes, are known to be catastrophic for most cases; they have poor overall power and bandwidth performance. In the literatures, it has been shown that the probability of generating such catastrophic sequences are negligible, therefore, the asymptotic error performance (AEP) of those well-known catastrophic CPM schemes evaluated with the corresponding MNSED, over AWGN channels, might be too negative or pessimistic. To deal with this problem in AWGN channel, this paper presents a new split-merged MNSED and provide criteria to explore which conventional catastrophic CPM scheme could increase the length of mergers with split-merged non-periodic events, effectively. For comparison, we investigate the exact power and bandwidth performance for LREC and LRC CPM for the same bandwidth occupancy. Computer simulation results verify that the AEP evaluating with the split-merged MNSED could achieve up to 3dB gain over the conventional approach.

We consider a physical-layer network coding (PNC) scheme based on M-ary continuous phase frequency shift keying (M-CPFSK) modulation for a bidirectional relay network. In this scheme, the maximum-likelihood sequence detection (MLSD) algorithm for the relay receiver over Rayleigh fading channels is discussed. Moreover, an upper bound on the minimum Euclidean distance for the superimposed signals is analyzed and the corresponding lower bound for the average symbol error rate (SER) at the relay is derived. Numerical results are also sustained by simulations which corroborate the exactness of the theoretical analysis.

Nonnegative Matrix Factorization (NMF) with sparseness and smoothness constraints has attracted increasing attention. When these properties are considered, NMF is usually formulated as an optimization problem in which a linear combination of an approximation error term and some regularization terms must be minimized under the constraint that the factor matrices are nonnegative. In this paper, we focus our attention on the error measure based on the Euclidean distance and propose a new iterative method for solving those optimization problems. The proposed method is based on the Hierarchical Alternating Least Squares (HALS) algorithm developed by Cichocki et al. We first present an example to show that the original HALS algorithm can increase the objective value. We then propose a new algorithm called the Gauss-Seidel HALS algorithm that decreases the objective value monotonically. We also prove that it has the global convergence property in the sense of Zangwill. We finally verify the effectiveness of the proposed algorithm through numerical experiments using synthetic and real data.

In this paper, we propose a similarity searchable encryption in the symmetric key setting for the weighted Euclidean distance, by extending the functional encryption scheme for inner product proposed by Bishop et al. [4]. Our scheme performs predetermined encoding independently of vectors x and y, and it obtains the weighted Euclidean distance between the two vectors while they remain encrypted.

Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.

In bit-patterned media recording (BPMR), the readback signal is severely corrupted by the inter-symbol interference (ISI) and inter-track interference (ITI), especially at high recording densities, due to small bit and track pitches. One way to alleviate the ITI effect is to encode an input data sequence before recording, so as to avoid some data patterns that easily cause an error at the data detection process. This paper proposes an ITI-mitigating 5/6 modulation code for a multi-track multi-head BPMR system to eliminate the data patterns that lead to severe ITI. Specifically, each of the 5 user bits is converted into a 6-bit codeword in the form of a 3-by-2 data array, based on a look-up table. Experimental results indicate that the system with the proposed coding scheme outperforms that without coding, especially when an areal density is high and/or the position jitter is large.

We propose a quasi-linear trellis-coded modulation (TCM) using nonbinary convolutional codes for quadrature amplitude modulation (QAM). First, we study a matched mapping which is able to reduce the computational complexity of the Euclidean distances between signal points of MQAM. As an example, we search for rate R=1/2 convolutional codes for coded 64QAM by this method. The symbol error rates of the proposed codes are estimated by the distance properties theoretically and they are verified by simulation. In addition, we compare the minimum free Euclidean distances of these new codes with their upper bounds. Finally, the bit error probabilitiy of the proposed coded modulation is compared with uncoded signal constellations and a conventional TCM code proposed by Ungerboeck. The result shows the proposed scheme outperform them on the AWGN channels.

Conventional CPM signals employ information sequence with time-unlimited phase shaping pulse (PSP) to achieve power and bandwidth efficient transmission. On the contrary, information sequence using time-limited PSP was believed to produce power-wasting data-independent discrete spectral lines in CPM spectra, and was suggested to be avoided. In this paper, we revisit this problem and adopt the time-limited PSP to replace the one with time-unlimited, it turns out to have an alternative solution to the CPM scheme. We first modify the spectral computing formula for the CPM with time-limited PSP (or CPM-TL) from conventional CPM formula and show that the discrete spectral lines appeared in the power density spectrum of CPM-TL signals can be diminished or become negligible by appropriately choosing PSP. We also show that this class of CPM can use any real number modulation index (h) and the resultant trellis structure of CPM guarantees the maximum constraint length allowed by the number of states in the MLSD receiver. Finally, the energy-bandwidth performance of CPM using time-limited PSP is investigated and compared with conventional CPM with time-unlimited PSP. From numerical results we show that, under the same number of states in the MLSD receiver and bandwidth occupancy, this subclass of CPM could outperform the conventional CPM up to 6dB coding gain, for h<1, in many cases.

In this paper, we propose a hardware solution for overcoming the problem of high computational demands in a nearest neighbor (NN) based multi-prototype learning system. The multiple prototypes are obtained by a high-speed K-means clustering algorithm utilizing a concept of software-hardware cooperation that takes advantage of the flexibility of the software and the efficiency of the hardware. The one nearest neighbor (1-NN) classifier is used to recognize an object by searching for the nearest Euclidean distance among the prototypes. The major deficiency in conventional implementations for both K-means and 1-NN is the high computational demand of the nearest neighbor searching. This deficiency is resolved by an FPGA-implemented coprocessor that is a VLSI circuit for searching the nearest Euclidean distance. The coprocessor requires 12.9% logic elements and 58% block memory bits of an Altera Stratix III E110 FPGA device. The hardware communicates with the software by a PCI Express (4) local-bus-compatible interface. We benchmark our learning system against the popular case of handwritten digit recognition in which abundant previous works for comparison are available. In the case of the MNIST database, we could attain the most efficient accuracy rate of 97.91% with 930 prototypes, the learning speed of 1.310-4 s/sample and the classification speed of 3.9410-8 s/character.

With the wide usage of multispectral images, a fast efficient multidimensional clustering method becomes not only meaningful but also necessary. In general, to speed up the multidimensional images' analysis, a multidimensional feature vector should be transformed into a lower dimensional space. The Hilbert curve is a continuous one-to-one mapping from N-dimensional space to one-dimensional space, and can preserves neighborhood as much as possible. However, because the Hilbert curve is generated by a recurve division process, 'Boundary Effects' will happen, which means data that are close in N-dimensional space may not be close in one-dimensional Hilbert order. In this paper, a new efficient approach based on the space-filling curves is proposed for classifying multispectral satellite images. In order to remove 'Boundary Effects' of the Hilbert curve, multiple Hilbert curves, z curves, and the Pseudo-Hilbert curve are used jointly. The proposed method extracts category clusters from one-dimensional data without computing any distance in N-dimensional space. Furthermore, multispectral images can be analyzed hierarchically from coarse data distribution to fine data distribution in accordance with different application. The experimental results performed on LANDSAT data have demonstrated that the proposed method is efficient to manage the multispectral images and can be applied easily.

The N-dimensional (N-D) Hilbert curve is a one-to-one mapping between N-D space and one-dimensional (1-D) space. It is studied actively in the area of digital image processing as a scan technique (Hilbert scan) because of its property of preserving the spatial relationship of the N-D patterns. Currently there exist several Hilbert scan algorithms. However, these algorithms have two strict restrictions in implementation. First, recursive functions are used to generate a Hilbert curve, which makes the algorithms complex and computationally expensive. Second, all the sides of the scanned region must have the same size and the length must be a power of two, which limits the application of the Hilbert scan greatly. Thus in order to remove these constraints and improve the Hilbert scan for general application, a nonrecursive N-D Pseudo-Hilbert scan algorithm based on two look-up tables is proposed in this paper. The merit of the proposed algorithm is that implementation is much easier than the original one while preserving the original characteristics. The experimental results indicate that the Pseudo-Hilbert scan can preserve point neighborhoods as much as possible and take advantage of the high correlation between neighboring lattice points, and it also shows the competitive performance of the Pseudo-Hilbert scan in comparison with other common scan techniques. We believe that this novel scan technique undoubtedly leads to many new applications in those areas can benefit from reducing the dimensionality of the problem.

This paper considers reduction of the peak-to-average power ratio (PAPR) of M-quadrature amplitude modulation (QAM) signals in orthogonal frequency division multiplexing (OFDM) systems. It is known that a 16-QAM or 64-QAM constellation can be written as the vector sum of two or three QPSK constellations respectively. We can then use the Golay complementary sequences over Z4 to construct 16-QAM or 64-QAM OFDM sequences with low PAPR. In this paper, we further examine the squared Euclidean distance of these M-QAM sequences and their variations. Our goal here is to combine the block coded modulation (BCM) and Golay complementary sequences to trade off the PAPR, the code rate, and the squared Euclidean distance of M-QAM OFDM signals. In particular, some 16-QAM and 64-QAM OFDM sequences with low PAPR and large squared Euclidean distance are presented.

A method for searching minimum Euclidean distances of respective substreams for different modulation orders of M-ary quadrature amplitude modulation signals in multiple-input and multiple-output systems is described. A channel matrix is cyclically-sorted sequentially and QR-decomposed. Using upper triangular matrices obtained by QR decomposition, minimum Euclidean distances are searched over trellis diagrams consisting of symbol-difference lattice points by computationally efficient multiple trellis-search algorithms. The simulation results demonstrate that per-substream minimum Euclidean distances can be detected with a high correct-estimation probability by path-re-searching controls over different modulation orders.

The 2-dimensional (2-D) Hilbert curve is a one-to-one mapping between 2-D space and one-dimensional (1-D) space. It is studied actively in the area of digital image processing as a scan technique (Hilbert scan) because of its property of preserving the spacial relationship of the 2-D patterns. Currently there exist several Hilbert scan algorithms. However, these algorithms have two strict restrictions in implementation. First, recursive functions are used to generate a Hilbert curve, which makes the algorithms complex and computationally expensive. Second, both sides of the scanned rectangle must have same size and each size must be a power of two, which limits the application of the Hilbert scan greatly. In this paper, a Pseudo-Hilbert scan algorithm based on two look-up tables is proposed. The proposed method improves the Hilbert scan to be suitable for real-time processing and general application. The simulation indicates that the Pseudo-Hilbert scan can preserve point neighborhoods as much as possible and take advantage of the high correlation between neighboring lattice points. It also shows competitive performance of the Pseudo-Hilbert scan in comparison with other scan techniques.

The probability associated with population fitness in a Genetic Algorithm (GA) is studied using the concept of average Euclidean distance. Based on the probability derived from population fitness, the GA can effectively terminate its evolution operations to mitigate the total computational load. Simulation results verify the feasibility of the derived probability used for the GA's termination strategy.

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.

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.

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.

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).