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

Asymptotic Error Probability of the Gallager B Decoder Under Timing Errors

IEEE COMMUNICATIONS LETTERS 2017年第4期21卷 698-701页

作者： Dupraz, Elsa Declercq, David Vasic, Bane CNRS UMR 6285 Lab STICC Telecom Bretagne F-29200 Brest France Univ Cergy Pontoise CNRS UMR 8051 ETIS ENSEA F-95000 Cergy France Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA

In a circuit, timing errors occur when a logic gate output does not switch before the clock rising edge. In this letter, we consider Gallager B decoders under timing errors, following the error model derived by Amaricai et al. from SPICE measurements. For this model, we provide a theoretical analysis of the performance of LDPC decoders. This letter is based on the analysis of the computation trees of the decoder free of logic gate errors and of the decoder with timing errors. As a main result, we show that as the number of iterations goes to infinity, the error probability of the decoder with timing errors converges to the error probability of the logic gate error-free decoder. Monte Carlo simulations confirm this result even for moderate code lengths, which is in accordance with the experimental observations.

关键词： Low-density parity check codes faulty Gallager B decoders timing errors computation trees

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-200

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-200 by published by

关键词： arithmetical arithmetical universe axiom axiom system binary relation computation trees define dynamic logic iff lemma mit-lcs-tr-200 partial correctness program programming language programs proof theorem total correctness universe validity problem weakest precondition

来源：评论

学校读者我要写书评

暂无评论

Multi-Session Function computation and Multicasting in Undirected Graphs

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2013年第4期31卷 702-713页

作者： Kannan, Sreeram Viswanath, Pramod Univ Calif Berkeley Dept EECS Berkeley CA 94720 USA Univ Illinois Dept ECE Urbana IL 61801 USA

In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data;this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph;the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are near optimal for a wide class of function computation requirements even at multiple terminals in undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

关键词： Function computation capacity Steiner packing multiple unicast network coding computation trees multicasting sensor networks

来源：评论

学校读者我要写书评

暂无评论

A Deviation-Based Conditional Upper Bound on the Error Floor Performance for Min-Sum Decoding of Short LDPC Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2012年第12期60卷 3567-3578页

作者： Psota, Eric T. Kowalczuk, Jedrzej Perez, Lance C. Univ Nebraska Dept Elect Engn Lincoln NE 68588 USA

Conditional upper bounds are given for min-sum decoding of low-density parity-check codes in the error floor region. It is generally thought that absorbing sets, i.e., small collections of variable nodes connected to a relatively small number of unsatisfied check nodes, are the primary source of errors in the error floor region. The conditional upper bounds presented here are based on the assumption that all error floor errors are caused by absorbing sets. In order to bound the probability of error associated with each absorbing set, a directed-edge Tanner graph is used to link absorbing sets to low-weight deviations. These low-weight deviations result when a proportionally large number of nodes within a stopping set belong to an absorbing set contained inside the stopping set. A complete collection of the most problematic absorbing sets, and the minimum deviation weights that result from them, are used to derive a conditional upper bound on the probability of error for min-sum decoding of low-density parity-check codes. Simulation results are given to demonstrate the accuracy of the bound.

关键词： LDPC codes iterative message-passing decoding stopping sets absorbing sets computation trees deviations

来源：评论

学校读者我要写书评

暂无评论

Unambiguous computations and locally definable acceptance types

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期194卷 137-161页

作者： Niedermeier, R Rossmanith, P Tech Univ Munich Fak Informat D-80290 Munich Germany Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

Hertrampf's locally definable acceptance types show that many complexity classes can be defined in terms of polynomial-time bounded NTMs with simple local conditions on the nodes of its computation tree, rather than global concepts like number of accepting paths, etc. We introduce a modification of Hertrampf's locally definable acceptance types which allows to get a larger number of characterizable complexity classes. Among others the newly characterizable classes are UP and MODZ(k)P. It is shown how different types of oracle access, e.g., guarded access, can be characterized by this model. This sheds new light on the discussion on how to access unambiguous computation. We present simple functions that describe precisely objects of current research as the unambiguous oracle, alternation, and promise hierarchies. We exhibit the new class UAP which seems to be an unambiguous analogue of Wagner's del P. UAP (and thus del P) contains Few and is currently the smallest class known with this property.

关键词： structural complexity unambiguous computation computation trees

来源：评论

学校读者我要写书评

暂无评论

How can a complex square root be computed in an optimal way?

引用

computationAL COMPLEXITY 1995年第3-4期5卷 222-236页

作者： Lickteig, T Werther, K Institut für Informatik Universität Bonn Bonn Germany

We give an optimality analysis for computations of complex square roots in real arithmetic by certain computation trees that use rear square root operations. Improving standard elementary geometric constructions Schonhage suggests better methods which will be shown to be unimprovable. The iteration of such a procedure for 2(k)-th roots is however ''improvable,'' and an improved Version of it can also be shown to be ''unimprovable.'' In particular, repeated usage of an optimal square root procedure does not yield an optimal one for 2(k)-th roots. To answer this kind of questions about resolution by real radicals we apply methods of real algebra which lead into the theory of real field, ring, and integral ring extensions.

关键词： computation trees straight-line programs complexity real algebra Galois theory and quantitative aspects resolution by real radicals integral extensions elementary geometric constructions

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs

引用

computational Complexity 1991年第3期1卷 257-268页

作者： Hirsch, Michael D. Department of Computer Science Princeton University Princeton 08544 NJ United States

Andrew Yao proved some lower bounds for algebraic computation trees with integer inputs. In his key result he proved bounds on the number of components of the leaf space of a homogeneous decision tree derived from a computation tree. In this paper we present a shorter and more conceptual proof. We introduce the concept of a regulated tree as a generalization of a regular tree which has the advantage of allowing the same lower bounds on the non-linear portion of the complexity. The proof is an application of a result of Ben-Or. © 1991 Birkhäuser Verlag.

关键词： computation trees Lower bounds non-linear complexity real algebraic geometry Subject classifications: 68Q05, 68Q15, 26C10, 26C15

来源：评论

学校读者我要写书评

暂无评论

TAKING RANDOM-WALKS TO GROW trees IN HYPERCUBES

引用

JOURNAL OF THE ACM 1993年第3期40卷 741-764页

作者： BHATT, S CAI, JY BELL COMMUN RES INC MORRISTOWNNJ PRINCETON UNIV DEPT COMP SCIPRINCETONNJ 08544

Many parallel computations are tree structured;as the computation proceeds, new processes are recursively created while others die out. algorithms for maintaining dynamically evolving trees on fine-grain parallel architectures must have minimal overhead and must distribute processes evenly among processors at run-time. A simple randomized strategy for maintaining dynamically evolving binary trees on hypercube networks is presented. The algorithm is distributed and does not require any global information. The algorithm guarantees that every pair of nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube. Furthermore, if M is the number of active nodes in the tree at any instant, then, with overwhelming probability, no hypercube processor is assigned more than O(1 + (M/N)) active nodes. The active nodes in a tree may constitute only leaves of the tree, or all nodes. As a corollary, with high probability, the load is evenly distributed throughout a computation whose running time is polynomial in N, the number of processors. The results can be generalized to bounded-degree trees. Our techniques justify the use of simple algorithms to efficiently parallelize any tree-based computation such as divide-and-conquer, backtrack, functional expression evaluation, and to efficiently maintain dynamic data structures such as quad-trees that arise in scientific applications. A novel technique-tree surgery-is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm.

关键词： ALGORITHMS DESIGN THEORY computation trees HYPERCUBE ARCHITECTURES ONLINE EMBEDDING PROBABILISTIC ANALYSIS RANDOM WALKS

来源：评论

学校读者我要写书评

暂无评论

Some computational problems in linear algebra as hard as matrix multiplication

引用

computational Complexity 1991年第2期1卷 131-155页

作者： Bürgisser, Peter Karpinski, Marek Lickteig, Thomas Institut für Informatik Universität Bonn Bonn 1 D-5300 Germany International Computer Science Institute Berkeley 94704 CA United States Fachbereich Mathematik Universität Tübingen Tübingen D-7400 Germany

We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:KER_n: Compute a basis of the kernel for a given n×n-matrix, OGB_n: Find an invertible matrix that transforms a given symmetric n×n-matrix (quadratic form) into diagonal form, SPR_n: Find a sparse representation of a given n×n-matrix. © 1991 Birkhäuser Verlag.

关键词： computation trees derivations matrix multiplication Ostrowski complexity Problems straight line programs Subject classifications: 68C20, 68C25

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：