检索结果-内蒙古大学图书馆

Reducing the Multiplier-complexity of Massively Parallel Polyphase 2D IIR Broadband Beam Filters

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2012年第3期31卷 1229-1243页

作者： Madanayake, Arjuna Gunaratne, Thushara K. Bruton, Leonard T. Univ Akron Akron OH 44325 USA Univ Calgary Calgary AB T2N 1N4 Canada

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

关键词： 2-dimensional (2D) computational-complexity Broadband Beam filters FPGA Hardware IIR digital filter Massively parallel Multirate Polyphase Time-interleaved VLSI

来源：评论

学校读者我要写书评

暂无评论

A Novel Approach for WLAN-based Outdoor Fingerprinting Localization

A Novel Approach for WLAN-based Outdoor Fingerprinting Local...

引用

2011 IEEE 3rd International Conference on Communication Software and Networks(ICCSN 2011)

作者： Qingyuan Zhao Sheng Zhang Jinguo Quan and Xiaokang Lin Modern communication laboratory Graduate School at Shenzhen Tsinghua University Shenzhen 518055 China

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.

关键词： WLAN Fingerprinting-system Common-APs Ac- curacy Robustness computational-complexity

来源：评论

学校读者我要写书评

暂无评论

Classical spin systems and the quantum stabilizer formalism: General mappings and applications

引用

JOURNAL OF MATHEMATICAL PHYSICS 2009年第8期50卷 083303:1-083303:35页

作者： Huebener, R. Van den Nest, M. Duer, W. Briegel, H. J. Univ Innsbruck Inst Theoret Phys A-6020 Innsbruck Austria Max Planck Inst Quantum Opt D-85748 Garching Germany Austrian Acad Sci Inst Quantenopt & Quanteninformat A-6020 Innsbruck Austria

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]

关键词： PARTITION-FUNCTION computational-complexity POTTS-MODEL TREE-WIDTH COMPUTER complexity classes Partition function Computers spin model spin systems quanta Potts model

来源：评论

学校读者我要写书评

暂无评论

The complexity of ferromagnetic ising with local fields

引用

COMBINATORICS PROBABILITY & COMPUTING 2007年第1期16卷 43-61页

作者： Goldberg, Leslie Ann Jerrum, Mark Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Edinburgh Div Informat JCMB Edinburgh EH9 3JZ Midlothian Scotland

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.

关键词： computational-complexity MODEL

来源：评论

学校读者我要写书评

暂无评论

Measurable notions of complexity and their relationship to biological complexity

引用

CHEMISTRY & BIODIVERSITY 2007年第11期4卷 2656-2669页

作者： Brooks, J. Paul Virginia Commonwealth Univ Operat Res & Ctr Study Biol Compplexity Dept Stat Sci Richmond VA 23284 USA

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.

关键词： MINIMUM DESCRIPTION LENGTH computational-complexity PRINCIPLE TREES

来源：评论

学校读者我要写书评

暂无评论

Phase transitions in the coloring of random graphs

引用

Physical Review E 2007年第3期76卷 031131-031131页

作者： Lenka Zdeborová Florent Krząkała LPTMS 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 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.

关键词： RANDOM SATISFIABILITY PROBLEMS STRUCTURAL GLASS-TRANSITION REPLICA-SYMMETRY-BREAKING RANDOM-ENERGY MODEL SPIN-GLASSES GROUND-STATE computational-complexity BETHE LATTICE DYNAMICS LIMIT

来源：评论

学校读者我要写书评

暂无评论

Genetic embedded matching approach to ground states in continuous-spin systems

引用

Physical Review E 2007年第6期76卷 066706-066706页

作者： Martin Weigel []Department of Mathematics and the Maxwell Institute for Mathematical Sciences Heriot-Watt University Edinburgh EH14 4AS United Kingdom and Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada N2L 3G1

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.

关键词： MONTE-CARLO computational-complexity FRUSTRATION MODEL GLASS OPTIMIZATION ENERGY ALGORITHM BEHAVIOR RESTORATION SIMULATIONS

来源：评论

学校读者我要写书评

暂无评论

Adaptation in stochastic tunneling global optimization of complex potential energy landscapes

引用

EUROPHYSICS LETTERS 2006年第6期74卷 944-950页

作者： Hamacher, K. Univ Calif San Diego Ctr Theoret Biol Phys La Jolla CA 92093 USA

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.

关键词： MONTE-CARLO ATOMIC CLUSTERS computational-complexity TEMPERING METHOD MINIMIZATION ALGORITHM PROTEIN MINIMUM CHEMISTRY DOCKING

来源：评论

学校读者我要写书评

暂无评论

Tractable fragments of Presburger Arithmetic

引用

THEORY OF COMPUTING SYSTEMS 2005年第5期38卷 647-668页

作者： Subramani, K W Virginia Univ LDCSEE Morgantown WV 26506 USA

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.

关键词： computational-complexity CONSTRAINT DATABASES DATALOG QUERIES FASTALGORITHMS TIME ALGORITHM 2 VARIABLES PROGRAMS FLOW

来源：评论

学校读者我要写书评

暂无评论

complexity and compilability of diagnosis and recovery of graph-based systems

引用

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS 2005年第10期20卷 1053-1076页

作者： Liberatore, P Univ Roma La Sapienza Dipartimento Informat & Sistemist Rome Italy

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.

关键词： computational-complexity INTRACTABLE PROBLEMS OPERATIVE DIAGNOSIS FAULT-PROPAGATION

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：