概率计算的基本问题与进展.ppt
概率计算的基本问题和进展,北京理工大学通信技术研究所2011年12月,1,引言,概率计算的基本概念概率计算的适用范围概率计算和器件的进展,2,概率计算的基本概念,概率计算：对概率数值的运算一个概率计算的实例：贝叶斯公式概率计算是数值计算的一种，多数情况为浮点运算。,3,概率计算在编译码中的应用,对数似然比LLR：LDPC中的和积算法对应Bayes网络的置信传播（BP）算法。随着高增益编译码算法的广泛应用，概率计算已经成为通信信号处理中非常密集的运算模式。,4,概率门的运算定义,概率计算存在一些特定的模式，参照数字逻辑中的与、或、非、异或概念定义概率运算的与、或、非、异或运算。1970年James N.Cronholm给出了概率门的定义James 1970：概率门表示一个固定但可控的转移概率P，P具有数字电路的随时钟变化特性。A probability gate presents a fixed but controllable transmission probability p to pulses arriving at its input.,James 1970 Probability gates statistics,5,概率与、或、非、异或门,Benjamin Vigoda 2007 Analog Continuous time statistical processing(美国专利US 007209867B2),6,概率门定义的意义,数字逻辑运算的基础是与、或、非门，任何数字系统都是基于逻辑门描述和表达；概率门的定义为概率运算的描述和表达提供了数学基础；FPGA针对查表运算进行了优化，DSP对乘加运算进行了优化，那么对于概率门运算的优化也会提升概率运算的性能。,7,概率计算的适用领域,随着计算机和信息技术的发展，出现了许多与概率计算密切相关的领域和算法：BCJR算法、Kalman fltering、belief propagation等。,8,早期的工作,1998年1999年瑞士研究人员在瑞士国家科学基金的支持下完成了turbo/LDPC码中的BP算法在模拟VLSI上的实现工作，相关成果发表在IEEE Int.Symp.on Information Theory上。,Hans-Andrea Loeliger 1998 Probability Propagation and Decoding in Analog VLSI；Hans-Andrea Loeliger 1999 Decoding in Analog VLSI,9,早期的工作,2003年同一研究小组人员实现了基于“软门”的汉明码译码COMS ASIC。,Matthias Frey 2003 ANALOG-DECODER EXPERIMENTS WITH SUBTHRESHOLD CMOS SOFT-GATES,用模拟器件实现的译码器,10,Lyric Semiconductor的产品,2010年Lyric Semiconductor推出了产品化的概率计算芯片；概率计算芯片实现LDPC译码速度是传统芯片的4倍，面积是1/30,耗电是1/12；概率计算芯片的速度、体积和功耗优势使得其具有广泛的应用前景。,Lyric的概率计算芯片,11,Lyric公司,Lyric在2006年由Benjamin Vigoda和David Reynolds创立，前者是MIT博士专攻概率计算，后者是芯片设计专家；Lyric Semiconductor由MIT和DARPA资助；2011年6月ADI公司收购了Lyric公司；,Benjamin Vigoda,David Reynolds,12,Benjamin Vigoda,1999年在MIT获得硕士学位，论文为A Nonlinear Dynamic System for Spread Spectrum Code Acquisition；2003年在MIT获得博士学位，论文为Analog Logic Continuous-Time Analog Circuits for Statistical Signal Processing，初步形成概率计算实现的方向：模拟电路。毕业后进入Mitsubishi电子工作，2006年创业。,13,Benjamin Vigoda的专利和论文,Benjamin Vigoda及Lyric公司拥有概率计算方面的专利8项；集中于2007年和2010年；在研究论文方面有2篇：Benjamin Vigoda 2005 Synchronization of Pseudo-Random Signals by Forward-Only Message Passing with Application to Electronic Circuits，IEEE TRANSACTIONS ON INFORMATION THEORYBenjamin Vigoda 2010 Low Power Logic For Statistical Inference，ISLPED10,August 1820,2010,14,Lyric FAQ,So is this analog,or digital?是模拟的还是数字的 This is not traditional analog.It is not traditional digital.It is a fundamentally new way of processing.For probability processing,weve adopted some of the best ideas from both analog and digital.We run on a clock like a digital circuit.Our circuits are modular and scalable.Our designs are made up of many instances of a small family of standard cells.However,we dont force our variables to be just 0s and 1s.Our variables take on any possible probability value:any analog value between 0 and 1.带有时钟的模拟电路,15,Lyric FAQ,So is it fuzzy logic?是不是模糊逻辑 Probability processing is Bayesian.The probabilities of different outcomes must add up to one.In fuzzy logic,you are allowed to be 60%sure that a coin is heads,and 60%sure that it is tails,both at the same time.That is not allowed in Lyrics probability processing technology.If we are 60%certain that a coin is heads,the probability that it is tails must be 40%-no other value is consistent.贝叶斯逻辑,16,Lyric FAQ,So is this like a neural net?是不是神经网络 Although Lyrics technology can be adaptive and can implement learning algorithms,it is fundamentally different from neural nets.Neural nets must be trained to exhibit desired behaviors.Once theyre trained,neural nets can be very hard to understand and nearly impossible to debug.Lyrics technology can be programmed using PSBL to implement predictable,understandable,deterministic behaviors.可预测、可理解、确定性行为,17,基于FPGA的实现方案,2010年加州大学伯克利分校的Mingjie Lin基于Virtex-5 FPGA实现了一种Bayesian computing machine(BCM)，速度与CPU、GPU相比10倍左右的改善。,Mingjie Lin 2010 High-Throughput Bayesian Computing Machine with Reconfigurable Hardware,18,国内的研究工作,北京信息科技大学光电信息与通信工程学院的杨曙辉教授在概率门实现方面有6项专利（2009年），2009年有3篇论文。杨曙辉 2009 具有概率分离计算功能的二级流水线电路设计；杨曙辉 2009 利用CMOS模拟电路设计实现的新型概率译码器；杨曙辉 2009 一种（5,2,3）网格码CMOS电路模拟译码器；,19,小结,概率计算电路提供了针对概率运算密集的一类问题的一种解决方法；概率计算电路的关键问题是概率门的高效率实现。模拟电路是实现概率的一种有效方法，但是也存在晶体管偏差敏感、易受干扰、受温度影响、器件老化的问题。,20,小 结,大量概率运算密集型的算法和应用的出现是概率计算的价值基础；概率门的定义和概率运算的形式化是概率计算的理论基础；基于模拟电路的高速概率运算器件的出现是概率运算的工程基础；,21,谢谢！,22,
