4概率计算的基本问题与进展

概率计算的基本问题和进展北京理工大学通信技术研究所2011年12月1引言概率计算的基本概念概率计算的适用范围概率计算和器件的进展2概率计算的基本概念概率计算：对概率数值的运算一个概率计算的实例：贝叶斯公式概率计算是数值计算的一种，多数情况为浮点运算。3概率计算在编译码中的应用对数似然比LLR：LDPC中的和积算法对应Bayes网络的置信传播（BP）算法。随着高增益编译码算法的广泛应用，概率计算已经成为通信信号处理中非常密集的运算模式。4概率门的运算定义概率计算存在一些特定的模式，参照数字逻辑中的与、或、非、异或概念定义概率运算的与、或、非、异或运算。1970年JamesN.Cronholm给出了概率门的定义[James1970]：

概率门表示一个固定但可控的转移概率P，P具有数字电路的随时钟变化特性。

Aprobabilitygatepresentsafixedbutcontrollabletransmissionprobabilityptopulsesarrivingatitsinput.[James1970]Probabilitygatesstatistics5概率与、或、非、异或门[BenjaminVigoda2007]AnalogContinuoustimestatisticalprocessing(美国专利US007209867B2)6概率门定义的意义数字逻辑运算的基础是与、或、非门，任何数字系统都是基于逻辑门描述和表达；概率门的定义为概率运算的描述和表达提供了数学基础；FPGA针对查表运算进行了优化，DSP对乘加运算进行了优化，那么对于概率门运算的优化也会提升概率运算的性能。7概率计算的适用领域随着计算机和信息技术的发展，出现了许多与概率计算密切相关的领域和算法：BCJR算法、Kalmanfltering、beliefpropagation等。8早期的工作1998年~1999年瑞士研究人员在瑞士国家科学基金的支持下完成了turbo/LDPC码中的BP算法在模拟VLSI上的实现工作，相关成果发表在IEEEInt.Symp.onInformationTheory上。[Hans-AndreaLoeliger1998]ProbabilityPropagationandDecodinginAnalogVLSI；[Hans-AndreaLoeliger1999]DecodinginAnalogVLSI9早期的工作2003年同一研究小组人员实现了基于“软门”的汉明码译码COMSASIC。[MatthiasFrey2003]ANALOG-DECODEREXPERIMENTSWITHSUBTHRESHOLDCMOSSOFT-GATES用模拟器件实现的译码器10LyricSemiconductor的产品2010年LyricSemiconductor推出了产品化的概率计算芯片；概率计算芯片实现LDPC译码速度是传统芯片的4倍，面积是1/30,耗电是1/12；概率计算芯片的速度、体积和功耗优势使得其具有广泛的应用前景。Lyric的概率计算芯片11Lyric公司Lyric在2006年由BenjaminVigoda和DavidReynolds创立，前者是MIT博士专攻概率计算，后者是芯片设计专家；LyricSemiconductor由MIT和DARPA资助；2011年6月ADI公司收购了Lyric公司；BenjaminVigodaDavidReynolds12BenjaminVigoda1999年在MIT获得硕士学位，论文为ANonlinearDynamicSystemforSpreadSpectrumCodeAcquisition；2003年在MIT获得博士学位，论文为AnalogLogicContinuous-TimeAnalogCircuitsforStatisticalSignalProcessing，初步形成概率计算实现的方向：模拟电路。毕业后进入Mitsubishi电子工作，2006年创业。13BenjaminVigoda的专利和论文BenjaminVigoda及Lyric公司拥有概率计算方面的专利8项；集中于2007年和2010年；在研究论文方面有2篇：[BenjaminVigoda2005]SynchronizationofPseudo-RandomSignalsbyForward-OnlyMessagePassingwithApplicationtoElectronicCircuits，IEEETRANSACTIONSONINFORMATIONTHEORY[BenjaminVigoda2010]LowPowerLogicForStatisticalInference，ISLPED’10,August18–20,2010,14LyricFAQSoisthisanalog,ordigital?是模拟的还是数字的Thisisnottraditionalanalog.Itisnottraditionaldigital.Itisafundamentallynewwayofprocessing.Forprobabilityprocessing,we'veadoptedsomeofthebestideasfrombothanaloganddigital.Werunonaclocklikeadigitalcircuit.Ourcircuitsaremodularandscalable.Ourdesignsaremadeupofmanyinstancesofasmallfamilyofstandardcells.However,wedon'tforceourvariablestobejust0sand1s.Ourvariablestakeonanypossibleprobabilityvalue:anyanalogvaluebetween0and1.带有时钟的模拟电路15LyricFAQSoisitfuzzylogic?是不是模糊逻辑ProbabilityprocessingisBayesian.Theprobabilitiesofdifferentoutcomesmustadduptoone.Infuzzylogic,youareallowedtobe60%surethatacoinisheads,and60%surethatitistails,bothatthesametime.ThatisnotallowedinLyric'sprobabilityprocessingtechnology.Ifweare60%certainthatacoinisheads,theprobabilitythatitistailsmustbe40%--noothervalueisconsistent.

贝叶斯逻辑16LyricFAQSoisthislikeaneuralnet?是不是神经网络AlthoughLyric'stechnologycanbeadaptiveandcanimplementlearningalgorithms,itisfundamentallydifferentfromneuralnets.Neuralnetsmustbetrainedtoexhibitdesiredbehaviors.Oncethey'retrained,neuralnetscanbeveryhardtounderstandandnearlyimpossibletodebug.Lyric'stechnologycanbeprogrammedusingPSBLtoimplementpredictable,understandable,deterministicbehaviors.

可预测、可理解、确定性行为17基于FPGA的实现方案2010年加州大学伯克利分校的MingjieLin基于Virtex-5FPGA实现了一种Bayesiancomputingmachine(BCM)，速度与CPU、GPU相比10倍左右的改善。[MingjieLin2010]High-ThroughputBayesianComputingMachinewithReconfigurableHardware18国内的研究工作北京信息科技大学光电信息与通信工程学院的杨曙辉教授在概率门实现方面有6项专利（2009年），2009年有3篇论文。[杨曙辉2009]具有概率分离计算功能的二级流水线电路设计；[杨曙辉2009]利用CMOS模拟电路设计实现的新型概率译码器；[杨曙辉2009]一种（5,2,3）网格码CMOS