The superior broadband performance of 2D IIR frequency-planar beam filters, relative to conventional 2D FIR true-time-delay beamforming, has recently been reported using computational electromagnetics and real-time em...
详细信息
The superior broadband performance of 2D IIR frequency-planar beam filters, relative to conventional 2D FIR true-time-delay beamforming, has recently been reported using computational electromagnetics and real-time emulations on an antenna test range, resulting in significant improvements of bit-error-rates (BERs) in the presence of broadband interference. Further, massively parallel systolic VLSI circuit polyphase architectures have also been reported (Madanayake et al. in Int. J. Circuit Theory Appl. 2010) for the case of the direct-form signal flow graph (SFG) architecture, operating at a maximum throughput of M-(antenna)-frames-per-clock-cycle (MFPCC). The superior broadband performance of 2D IIR frequency-planar beam filters is extended here from the direct-form signal flow graph (SFG) architecture (Madanayake et al. in Int. J. Circuit Theory Appl. 2010) to the novel differential-form SFG architecture in order to reduce overall complexity. The proposed method employs a differential-form polyphase 2D IIR frequency-planar beam SFG, and a corresponding circuit architecture, to implement the required input-output 2D space-time difference equation. The resultant digital hardware has the significant advantage of much-reduced multiplier complexity, relative to the direct-form structure. For example, when look-ahead pipelining is not employed and for polyphase architectures having two, three, and four phases, the corresponding reductions in multiplier complexity are 20%, 28.6% and 33.3%, respectively. A proof-of-concept prototype circuit is designed and implemented on a Xilinx Sx35 FPGA device for the two-phase case, operating at a frame-rate of 132 million linear frames per second on the uniform linear array (ULA), corresponding to 2-frames-per-clock-cycle at a circuit clock frequency of 66 MHz. The circuit is optimized for low critical path delays (CPDs) using look-ahead pipelining of order three. For ultra-wideband (UWB) radio-frequency (RF) implementations, in such
These years, WLAN- based positioning technology developed rapidly due to the limitation of GPS in "city canyon". Some people try to apply the indoor fingerprint positioning technology in the outdoor environm...
详细信息
These years, WLAN- based positioning technology developed rapidly due to the limitation of GPS in "city canyon". Some people try to apply the indoor fingerprint positioning technology in the outdoor environment. Unfortunately, they ig- nore the difference between the indoor and outdoor environment and can’t achieve preferable results. Considering more complex factors in outdoor environment, we propose a new approach called Common-APs(Access points)-Likelihood Algorithm, which uses the overlapping APs to measure the similarity among users and training points instead of the traditional Signal Strength (SS) information. Our experiment shows that our algorithm could improve the accuracy by 48.75% and reduce the time cost significantly. In addition, the proposed algorithm has strong robustness and could work much better in the busy downtown surrounding dense APs.
We present general mappings between classical spin systems and quantum physics. More precisely, we show how to express partition functions and correlation functions of arbitrary classical spin models as inner products...
详细信息
We present general mappings between classical spin systems and quantum physics. More precisely, we show how to express partition functions and correlation functions of arbitrary classical spin models as inner products between quantum stabilizer states and product states, thereby generalizing mappings for some specific models established in our previous work [M. Van den Nest et al., Phys. Rev. Lett. 98, 117207 (2007)]. For Ising- and Potts-type models with and without external magnetic field, we show how the entanglement features of the corresponding stabilizer states are related to the interaction pattern of the classical model, while the choice of product states encodes the details of the interaction. These mappings establish a link between the fields of classical statistical mechanics and quantum information theory, which we utilize to transfer techniques and methods developed in one field to gain insight into the other. For example, we use quantum information techniques to recover well known duality relations and local symmetries of classical models in a simple way and provide new classical simulation methods to simulate certain types of classical spin models. We show that in this way all inhomogeneous models of q-dimensional spins with pairwise interaction pattern specified by a graph of bounded tree width can be simulated efficiently. Finally, we show relations between classical spin models and measurement-based quantum computation. (C) 2009 American Institute of Physics. [DOI: 10.1063/1.3190486]
We consider the complexity of approximating the partition function of the ferromagnetic Ising model with varying interaction energies and local external magnetic fields. Jerrum and Sinclair provided a fully polynomial...
详细信息
We consider the complexity of approximating the partition function of the ferromagnetic Ising model with varying interaction energies and local external magnetic fields. Jerrum and Sinclair provided a fully polynomial randomized approximation scheme for the case in which the system is consistent in the sense that the local external fields all favour the same spin. We characterize the complexity of the general problem by showing that it is equivalent in complexity to the problem of approximately counting independent sets in bipartite graphs, thus it is complete in a logically defined subclass of #P previously studied by Dyer, Goldberg, Greenhill and Jerrum. By contrast, we show that the corresponding computational task for the q-state Potts model with local external magnetic fields and q > 2 is complete for all of #P with respect to approximation-preserving reductions.
complexity is often invoked as a motivation for a systems approach to biology. We review three measurable notions of complexity from the areas of computation and data analysis. These measures have each led to mathemat...
详细信息
complexity is often invoked as a motivation for a systems approach to biology. We review three measurable notions of complexity from the areas of computation and data analysis. These measures have each led to mathematical theory and to further insight on the complexity of objects, demonstrating the benefits of having a well-defined measure of complexity. Each measure is applicable in the study of particular biological systems;however, none is satisfactory to serve as a universal measure of biological complexity. The study of biological systems will likely require numerous measures of complexity, each appropriate for analysis in specific settings.
作者:
Lenka ZdeborováFlorent KrząkałaLPTMS
UMR 8626 CNRS et Université Paris-Sud 91405 Orsay CEDEX France PCT
UMR Gulliver 7083 CNRS-ESPCI 10 rue Vauquelin 75231 Paris France
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and system...
详细信息
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdős-Rényi and regular random graphs and determine their asymptotic values for a large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to...
详细信息
Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.
Global optimization remains one of the great challenges in scientific computing. One particular successful approach is the usage of tunneling functions to cross barriers and transition states more easily thus allowing...
详细信息
Global optimization remains one of the great challenges in scientific computing. One particular successful approach is the usage of tunneling functions to cross barriers and transition states more easily thus allowing for a fast scan of the potential energy surface under investigation. In this paper we develop for the first time a performance measurement procedure for stochastic tunneling approaches and derive an adaptive algorithm that is steered by this performance measure. The proposed algorithm is based on a scale-free measure and thus applicable to general stochastic optimization schemes. We found for a very hard optimization problem the computational effort to be some order of magnitude lower while at the same time increasing the accuracy by a factor of three.
In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitr...
详细信息
In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent two-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. Quantified Integer Programming can be thought of as a restriction of Presburger Arithmetic, in that we allow only conjunctions of linear inequalities. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or quantifier specification or both. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also establish the computational complexities of Oblivious strategy games and Clairvoyant strategy games.
This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from...
详细信息
This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. (c) 2005 Wiley Periodicals, Inc.
暂无评论