This paper proposes a circular bit-vector-mismatches (CBVM) algorithm for approximate circular string matching with k-mismatches. We develop the proposed CBVM algorithm based on the rotation feature of the circular pattern. By reusing the matching information of the previous substring, the next substring of the input string can be processed in parallel.

Left-weight sequences (LW-sequences for short) are in common currency for encoding binary trees. In [16], Wu et al. proposed an algorithm associated with tree rotations for listing all binary trees in diverse representations including LW-sequences. In particular, such a list of LW-sequences is generated in Gray-code order. In this paper, based on this ordering, we present efficient ranking and unranking algorithms. For binary trees with n internal nodes, the time complexity and the space requirement in each of our ranking and unranking algorithms are O(n2) and O(n), respectively.

The numerical error of a sample Mahalanobis distance (T2=y'S-1y) with sample covariance matrix S is investigated. It is found that in order to suppress the numerical error of T2, the following conditions need to be satisfied. First, the reciprocal square root of the condition number of S should be larger than the relative error of calculating floating-point real-number variables. The second proposed condition is based on the relative error of the observed sample vector y in T2. If the relative error of y is larger than the relative error of the real-number variables, the former governs the numerical error of T2. Numerical experiments are conducted to show that the numerical error of T2 can be suppressed if the two above-mentioned conditions are satisfied.

Electroencephalography (EEG) and magnetoencephalography (MEG) measure the brain signal from spatially-distributed electrodes. In order to detect event-related synchronization and desynchronization (ERS/ERD), which are utilized for brain-computer/machine interfaces (BCI/BMI), spatial filtering techniques are often used. Common spatial potential (CSP) filtering and its extensions which are the spatial filtering methods have been widely used for BCIs. CSP transforms brain signals that have a spatial and temporal index into vectors via a covariance representation. However, the variance-covariance structure is essentially different from the vector space, and not all the information can be transformed into an element of the vector structure. Grassmannian embedding methods, therefore, have been proposed to utilize the variance-covariance structure of variational patterns. In this paper, we propose a metric learning method to classify the brain signal utilizing the covariance structure. We embed the brain signal in the extended Grassmann manifold, and classify it on the manifold using the proposed metric. Due to this embedding, the pattern structure is fully utilized for the classification. We conducted an experiment using an open benchmark dataset and found that the proposed method exhibited a better performance than CSP and its extensions.

The rapid development of a global navigation satellite system (GNSS) has raised the demand for spacecraft navigation, particularly for lunar spacecraft (LS). First, instead of the traditional approach of combining the united X-band system (UXB) with very-long-baseline interferometry (VLBI) by a terrestrial-based observing station in Chinese deep-space exploration, the spacecraft navigation based on inter-satellite link (ISL) is proposed because the spatial coverage of the GNSS downstream signals is too narrow to be used for LS navigation. Second, the feasibility of LS navigation by using ISL wide beam signals has been analyzed with the following receiving parameters: the geometrical dilution of precision (GDOP) and the carrier-to-noise ratio (C/N0) for satellites autonomously navigation of ISL and LS respectively; the weighting distance root-mean-square (wdrms) for the combination of both navigation modes. Third, to be different from all existing spacecraft ISL and GNSS navigation methods, an ISL annular beam transmitting antenna has been simulated to minimize the wdrms (1.138m) to obtain the optimal beam coverage: 16°-47° on elevation angle. Theoretical calculations and simulations have demonstrated that both ISL autonomous navigation and LS navigation can be satisfied at the same time. Furthermore, an onboard annular wide beam ISL antenna with optimized parameters has been designed to provide a larger channel capacity with a simpler structure than that of the existing GPS ISL spot beam antenna, a better anti-jamming performance than that of the former GPS ISL UHF-band wide band antenna, and a wider effectively operating area than the traditional terrestrial-based measurement. Lastly, the possibility and availability of applying an ISL receiver with an annular wide beam antenna on the Chinese Chang'E-5T (CE-5T) reentry experiment for autonomous navigation are analyzed and verified by simulating and comparing the ISL receiver with the practiced GNSS receiver.

Many methods have been proposed for measuring the structural similarity between two protein folds. However, it is difficult to select one best method from them for the classification task, as each method has its own strength and weakness. Intuitively, combining multiple methods is one solution to get the optimal classification results. In this paper, by generalizing the concept of the large margin nearest neighbor (LMNN), a method for combining multiple distance metrics from different types of protein structure comparison methods for protein fold classification task is proposed. While LMNN is limited to Mahalanobis-based distance metric learning from a set of feature vectors of training data, the proposed method learns an optimal combination of metrics from a set of distance metrics by minimizing the distances between intra-class data and enlarging the distances of different classes' data. The main advantage of the proposed method is the capability in finding an optimal weight coefficient for combination of many metrics, possibly including poor metrics, avoiding the difficulties in selecting which metrics to be included for the combination. The effectiveness of the proposed method is demonstrated on classification experiments using two public protein datasets, namely, Ding Dubchak dataset and ENZYMES dataset.

Efficient detection schemes for an overloaded multiple-input multiple-output (MIMO) system have been investigated recently. The literature shows that trellis coded modulation (TCM) is able to enhance a system's capability to separate signal streams in the detection process of MIMO systems. However, the computational complexity remains high as a maximum likelihood detection (MLD) algorithm is used in the scheme. Thus, a sphere decoding (SD) algorithm with a pseudo distance (PD) is proposed in this paper. The PD maintains the coding gain advantage of the TCM by keeping some potential paths connected unlike conventional SD which truncates them. It is shown that the proposed scheme can reduce the number of distance calculations by about 98% for the transmission of 3 signal streams. In addition, the proposed scheme improves the performance by about 2dB at the bit error rate of 10-2.

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.

This paper proposes a novel technology to detect the orientation of an image relying on its contour which is noised to varying degrees. For the image orientation detection, most methods regard to the landscape image and the image taken of a single object. In these cases, the contours of these images are supposed to be immune to the noise. This paper focuses on the the contour noised after image segmentation. A polar orientation descriptor Orientation Context is viewed as a feature to describe the coarse distribution of the contour points. This descriptor is verified to be independent of translation, isotropic scaling, and rotation transformation by theory and experiment. The relative orientation depends on the minimum distance Roulette Distance between the descriptor of a template image and that of a test image. The proposed method is capable of detecting the direction on the interval from 0 to 359 degrees which is wider than the former contour-based means (Distance Phase [1], from 0 to 179 degrees). What's more, the results of experiments show that not only the normal binary image (Noise-0, Accuracy-1: 84.8%) (defined later) achieves more accurate orientation but also the binary image with slight contour noise (Noise-1, Accuracy-1: 73.5%) could obtain more precise orientation compared to Distance Phase (Noise-0, Accuracy-1: 56.3%; Noise-1, Accuracy-1: 27.5%). Although the proposed method (O(op2)) takes more time to detect the orientation than Distance Phase (O(st)), it could be realized including the preprocessing in real time test with a frame rate of 30.

In this letter, a new method is presented to suppress fractional pseudocodewords by eliminating small instantons of irregular low-density parity-check (LDPC) codes under the linear programming (LP) decoding over the binary symmetric channel (BSC). By appending several new rows found by the integer linear programming formulation to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes under the LP decoding at the cost of a slightly loss of the original code rate.

In many real-world classification problems, the class balance often changes between training and test datasets, due to sample selection bias or the non-stationarity of the environment. Naive classifier training under such changes of class balance systematically yields a biased solution. It is known that such a systematic bias can be corrected by weighted training according to the test class balance. However, the test class balance is often unknown in practice. In this paper, we consider a semi-supervised learning setup where labeled training samples and unlabeled test samples are available and propose a class balance estimator based on the energy distance. Through experiments, we demonstrate that the proposed method is computationally much more efficient than existing approaches, with comparable accuracy.

In this letter, we propose a new distance estimation method based on statistical models of a Received Signal Strength (RSS) at the receiver. The conventional distance estimator estimates the distance between the transmitter and the receiver based on the statistical average of the RSS when the receiver obtains instantaneous RSS and an estimate of the hyperparameters which consists of the path loss exponent and so on. However, it is well-known that instantaneous RSS does not always correspond to the average RSS because the RSS varies in accordance with a statistical model. Although the statistical model has been introduced for the hyperparameters estimation and the localization system, the conventional distance estimator has not yet utilized it. We introduce the statistical model to the distance estimator whose expected value of the estimate corresponds to true distance. Our theoretical analysis establishes that the proposed distance estimator is preferable to the conventional one in order to improve accuracy in the expected value of the distance estimate. Moreover, we evaluate the Mean Square Error (MSE) between true distance and the estimate. We provide evidence that the MSE is always proportional to the square of the distance if the estimate of the hyperparameters is ideally obtained.

The authors proposed an algorithm for calculation of new lower bound (rank bounded distance) using the discrete Fourier transform in 2010. Afterward, we considered some algorithms to improve the original algorithm with moving the row or column. In this paper, we discuss the calculation method of the rank bounded distance by conjugate elements for cyclic codes.

Cassuto and Blaum proposed new error correcting codes which are called symbol-pair codes. They presented a coding framework for channels whose outputs are overlapping pairs of symbols in storage applications. Such channels are called symbol-pair read channels. The pair distance and pair error are used in symbol-pair read channels. Cassuto et al. and Yaakobi et al. presented decoding algorithms for symbol-pair codes. However, their decoding algorithms cannot always correct errors whose number is not more than half the minimum pair distance. In this paper, we propose a new decoding algorithm using syndromes of symbol-pair codes. In addition, we show that the proposed algorithm can correct all pair errors within the pair error correcting capability.

Most P2PTV systems select a neighbor peer in an overlay network using RTT or a random method without considering the underlying network. Streaming traffic is shared over a network without localization awareness, which is a serious problem for Internet Service Providers. In this paper, we present a novel scheme to achieve P2PTV traffic localization by inserting delay into P2P streaming packets, so that the length of the inserted delay depends on the AS hop distance between a peer and its neighbor peer. Experiments conducted on a real network show that our proposed scheme can perform efficient traffic localization.

An appropriate similarity measure between images is one of the key techniques in search-based image annotation models. In order to capture the nonlinear relationships between visual features and image semantics, many kernel distance metric learning(KML) algorithms have been developed. However, when challenged with large-scale image annotation, their metrics can't explicitly represent the similarity between image semantics, and their algorithms suffer from high computation cost. Therefore, they always lose their efficiency. In this paper, we propose a manifold kernel metric learning (M_KML) algorithm. Our M_KML algorithm will simultaneously learn the manifold structure and the image annotation metrics. The main merit of our M_KML algorithm is that the distance metrics are builded on image feature's interior manifold structure, and the dimensionality reduction on manifold structure can handle the high dimensionality challenge faced by KML. Final experiments verify our method's efficiency and effectiveness by comparing it with state-of-the-art image annotation approaches.

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.

In this paper, we propose an error-correction low-pass filter (EC-LPF) algorithm for estimating the wireless distance between devices. To measure this distance, the received signal strength indication (RSSI) is a popularly used method because the RSSI of a wireless signal, such as Wi-Fi and Bluetooth, can be measured easily without the need for additional hardware. However, estimating the wireless distance using an RSSI is known to be difficult owing to the occurrence of inaccuracies. To examine the inaccuracy characteristics of Bluetooth RSSI, we conduct a preliminary test to discover the relationship between the actual distance and Bluetooth RSSI under several different environments. The test results verify that the main reason for inaccuracy is the existence of measurement errors in the raw Bluetooth RSSI data. In this paper, the EC-LPF algorithm is proposed to reduce measurement errors by alleviating fluctuations in a Bluetooth signal with responsiveness for real-time applications. To evaluate the effectiveness of the EC-LPF algorithm, distance accuracies of different filtering algorithms are compared, namely, a low-pass filer (LPF), a Kalman filter, a particle filter, and the EC-LPF algorithm under two different environments: an electromagnetic compatibility (EMC) chamber and an indoor hall. The EC-LPF algorithm achieves the best performance in both environments in terms of the coefficient of determination, standard deviation, measurement range, and response time. In addition, we also implemented a meeting room application to verify the feasibility of the EC-LPF algorithm. The results prove that the EC-LPF algorithm distinguishes the inside and outside areas of a meeting room without error.

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.

We measure neutron-induced Single Event Upsets (SEUs) and Multiple Cell Upsets (MCUs) on Flip-Flops (FFs) in a 65-nm bulk CMOS process in order to evaluate dependence of MCUs on cell distance and well-contact density using four different shift registers. Measurement results by accelerated tests show that MCU/SEU is up to 23.4% and it is exponentially decreased by the distance between latches on FFs. MCU rates can be drastically reduced by inserting well-contact arrays between FFs. The number of MCUs is reduced from 110 to 1 by inserting well-contact arrays under power and ground rails.