We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $rac{15}{16}n^2+O(n)$ swaps for k=3.

A novel ROI-based reversible data hiding scheme is proposed for medical images, which is able to hide electronic patient record (EPR) and protect the region of interest (ROI) with tamper localization and recovery. The proposed scheme combines prediction error expansion with the sorting technique for embedding EPR into ROI, and the recovery information is embedded into the region of non-interest (RONI) using histogram shifting (HS) method which hardly leads to the overflow and underflow problems. The experimental results show that the proposed scheme not only can embed a large amount of information with low distortion, but also can localize and recover the tampered area inside ROI.

A removable HDD “iVDR” is an international standardized medium, which has HDD features such as a large capacity and high-speed data transfer, and also is removable and compatible. We discuss the concepts of the hardware-specifications designed by the iVDR Consortium and the history of the international standardization activities for iVDR. We also discuss application expansions through these standardization activities.

We propose a family of algorithms for efficiently merging on contemporary GPUs, so that each algorithm requires O(m log (+1)) element comparisons, where m and n are the sizes of the input sequences with m ≤ n. According to the lower bounds for merging all proposed algorithms are asymptotically optimal regarding the number of necessary comparisons. First we introduce a parallely structured algorithm that splits a merging problem of size 2l into 2i subproblems of size 2l-i, for some arbitrary i with (0 ≤ i ≤ l). This algorithm represents a merger for i=l but it is rather inefficient in this case. The efficiency is boosted by moving to a two stage approach where the splitting process stops at some predetermined level and transfers control to several parallely operating block-mergers. We formally prove the asymptotic optimality of the splitting process and show that for symmetrically sized inputs our approach delivers up to 4 times faster runtimes than the thrust::merge function that is part of the Thrust library. For assessing the value of our merging technique in the context of sorting we construct and evaluate a MergeSort on top of it. In the context of our benchmarking the resulting MergeSort clearly outperforms the MergeSort implementation provided by the Thrust library as well as Cederman's GPU optimized variant of QuickSort.

In this paper, we propose a hardware architecture of high-speed sorted QR decomposition for 44 MIMO wireless communication systems. QR decomposition (QRD) is commonly used in many MIMO detection algorithms. In particular, sorted QR decomposition (SQRD) is the advanced algorithm to improve MIMO detection performance. We design an SQRD hardware architecture by using a modified Gram-Schmidt algorithm with pipelining and recursive processing. In addition, we propose an extended architecture which can decompose an augmented channel matrix for MMSE MIMO detection. These architecture can be applied in high-throughput MIMO-OFDM system such as IEEE802.11n which supports data throughput of up to 600 Mbps. We implement the proposed SQRD architecture and the proposed MMSE-SQRD architecture with 179k and 334k gates in 90 nm CMOS technology. These proposed design can achieve a high performance of up to 40.8 and 50.0 million 44 SQRD operations per second with the maximum operating frequency of 245 and 300 MHz.

In this letter, a post-detection signal to noise ratio (SNR) is considered for transmit antenna selection, when a sorted QR decomposition (SQRD) algorithm is used for signal detection in spatial multiplexing (SM) ultra-wideband (UWB) multiple input multiple output systems. The post-detection SNR expression is obtained using a QR factorization algorithm based on a sorted Gram-Schmidt process. The employed antenna selection criterion is to utilize the largest minimum post-detection SNR value. It is shown via simulations that the antenna selection significantly enhances the BER performance of the SQRD-based SM UWB systems on a log-normal multipath fading channel.

This paper proposes a new semantics that characterizes the time and/or situation dependencies of properties, together with the ontological notion of existential rigidity. For this purpose, we present order-sorted tempo-situational logic (OSTSL) with rigid/anti-rigid sorts and an existential predicate. In this logic, rigid/anti-rigid sorted terms enable the expressions for sortal properties, and temporal and situational operators suitably represent the ontological axioms of existential rigidity and time and/or situation dependencies. A specific semantics of OSTSL adheres to the temporal and situational behaviors of properties based on existential rigidity. As a result, the semantics guarantees that the ontological axioms of properties expressed by sorted tempo-situational formulas are logically valid.

We propose a new multi-objective genetic programming (MOGP) for automatic construction of image feature extraction programs (FEPs). The proposed method was originated from a well known multi-objective evolutionary algorithm (MOEA), i.e., NSGA-II. The key differences are that redundancy-regulation mechanisms are applied in three main processes of the MOGP, i.e., population truncation, sampling, and offspring generation, to improve population diversity as well as convergence rate. Experimental results indicate that the proposed MOGP-based FEP construction system outperforms the two conventional MOEAs (i.e., NSGA-II and SPEA2) for a test problem. Moreover, we compared the programs constructed by the proposed MOGP with four human-designed object recognition programs. The results show that the constructed programs are better than two human-designed methods and are comparable with the other two human-designed methods for the test problem.

In this letter, we propose a low-complexity sparse channel estimation method for orthogonal frequency division multiplexing (OFDM) systems. The proposed method uses a discrete Fourier transform (DFT)-based technique for channel estimation and a novel sorted noise space discrimination technique to estimate the channel length and tap positions. Simulation results demonstrate that the reduction in signal space improves the channel estimation performance.

We exploit a structural knowledge representation scheme called System Entity Structure (SES) methodology to represent and manage wafer failure patterns which can make a significant influence to FABs in the semiconductor industry. It is important for the engineers to simulate various system verification processes by using predefined system entities (e.g., decomposition, taxonomy, and coupling relationships of a system) contained in the SES. For better computational performance, given a certain failure pattern, a Pruned SES (PES) can be extracted by selecting the only relevant system entities from the SES. Therefore, the SES-based simulation system allows the engineers to efficiently evaluate and monitor semiconductor data by i) analyzing failures to find out the corresponding causes and ii) managing historical data related to such failures.

Combining the sphere decoding (SD) algorithm and the sequential detection method, we propose an adaptive group detection (AGD) scheme based on the sort-descending QRD (S-D-QRD) for V-BLAST architectures over an i.i.d. Rayleigh flat fading channel. Simulation results show that the proposed scheme, which encompasses the SD algorithm and the sequential detection method as two extreme cases in a probability sense, can achieve a very flexible tradeoff between the detection performance and computational complexity by adjusting the group parameter.

This paper proposes a new sieving algorithm that employs a bucket sort as a part of a factoring algorithm such as the number field sieve. The sieving step requires an enormous number of memory updates; however, these updates usually cause cache hit misses. The proposed algorithm significantly reduces the number of cache hit misses when the size of the sieving region is roughly less than the square of the cache size, and the memory updates are several times faster than the straightforward implementation according to the PC experiments.

This research considers an efficient method for calculating the transition matrix in an MPL (Max-Plus Linear) state-space representation. This matrix can be generated by applying the Kleene star operator to an adjacency matrix. The proposed method, based on the idea of a topological sort in graph theory and block splitting, is able to calculate the transition matrix efficiently.

This letter proposes an efficient transmit power allocation using partial channel information feedback for the closed-loop sorted QR decomposition (SQRD) based V-BLAST systems. For the feedback information, the positive real-valued diagonal elements of R are forwarded to the transmitter. With the proposed transmit power allocation that is numerically derived by the Lagrange optimization method, the bit error rate performance of the system can be remarkably improved compare to the conventional open-loop SQRD based V-BLAST systems without increasing the receiver complexity.

Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.

This paper presents two hardware-friendly low-power oriented fast motion estimation (ME) algorithms and their VLSI implementations. The basic idea of the proposed partial distortion sorting (PDS) algorithm is to disable the search points which have larger partial distortions during the ME process, and only keep those search points with smaller ones. To further reduce the computation overhead, a simplified local PDS (LPDS) algorithm is also presented. Experiments show that the PDS and LPDS algorithms can provide almost the same image quality as full search only with 36.7% computation complexity. The proposed two algorithms can be integrated into different FSBMA architectures to save power consumption. In this paper, the 1-D inter ME architecture [12] is used as an detailed example. Under the worst working conditions (1.62 V, 125) and 166 MHz clock frequency, the PDS algorithm can reduce 33.3% power consumption with 4.05 K gates extra hardware cost, and the LPDS can reduce 37.8% power consumption with 1.73 K gates overhead.

A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(+log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Ω(+log n) time slots with at least one station being awake for expected Ω(log n) time slots. Therefore, our ranking protocol is optimal.

The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.

To simultaneously support guaranteed real-time services and best-effort service, a Priority-based Scheduling Architecture (PSA) designed for high-speed switches is proposed. PSA divides packet scheduling into high-priority phase and low-priority phase. In the high-priority phase, an improved sorted-priority algorithm is presented. It introduces a new constraint into the scheduling discipline to overcome bandwidth preemption. Meanwhile, the virtual time function with a control factor α is employed. Both computer simulation results and theoretic analysis show that the PSA mechanism has excellent performance in terms of the implementation complexity, fairness and delay properties.