4概率計算的基本問題與進展

概率計算的基本問題和進展北京理工大學通信技術研究所2011年12月1引言概率計算的基本概念概率計算的適用范圍概率計算和器件的進展2概率計算的基本概念概率計算：對概率數(shù)值的運算一個概率計算的實例：貝葉斯公式概率計算是數(shù)值計算的一種，多數(shù)情況為浮點運算。3概率計算在編譯碼中的應用對數(shù)似然比LLR：LDPC中的和積算法對應Bayes網(wǎng)絡的置信傳播（BP）算法。隨著高增益編譯碼算法的廣泛應用，概率計算已經(jīng)成為通信信號處理中非常密集的運算模式。4概率門的運算定義概率計算存在一些特定的模式，參照數(shù)字邏輯中的與、或、非、異或概念定義概率運算的與、或、非、異或運算。1970年JamesN.Cronholm給出了概率門的定義[James1970]：

概率門表示一個固定但可控的轉移概率P，P具有數(shù)字電路的隨時鐘變化特性。

Aprobabilitygatepresentsafixedbutcontrollabletransmissionprobabilityptopulsesarrivingatitsinput.[James1970]Probabilitygatesstatistics5概率與、或、非、異或門[BenjaminVigoda2007]AnalogContinuoustimestatisticalprocessing(美國專利US007209867B2)6概率門定義的意義數(shù)字邏輯運算的基礎是與、或、非門，任何數(shù)字系統(tǒng)都是基于邏輯門描述和表達；概率門的定義為概率運算的描述和表達提供了數(shù)學基礎；FPGA針對查表運算進行了優(yōu)化，DSP對乘加運算進行了優(yōu)化，那么對于概率門運算的優(yōu)化也會提升概率運算的性能。7概率計算的適用領域隨著計算機和信息技術的發(fā)展，出現(xiàn)了許多與概率計算密切相關的領域和算法：BCJR算法、Kalmanfltering、beliefpropagation等。8早期的工作1998年~1999年瑞士研究人員在瑞士國家科學基金的支持下完成了turbo/LDPC碼中的BP算法在模擬VLSI上的實現(xiàn)工作，相關成果發(fā)表在IEEEInt.Symp.onInformationTheory上。[Hans-AndreaLoeliger1998]ProbabilityPropagationandDecodinginAnalogVLSI；[Hans-AndreaLoeliger1999]DecodinginAnalogVLSI9早期的工作2003年同一研究小組人員實現(xiàn)了基于“軟門”的漢明碼譯碼COMSASIC。[MatthiasFrey2003]ANALOG-DECODEREXPERIMENTSWITHSUBTHRESHOLDCMOSSOFT-GATES用模擬器件實現(xiàn)的譯碼器10LyricSemiconductor的產(chǎn)品2010年LyricSemiconductor推出了產(chǎn)品化的概率計算芯片；概率計算芯片實現(xiàn)LDPC譯碼速度是傳統(tǒng)芯片的4倍，面積是1/30,耗電是1/12；概率計算芯片的速度、體積和功耗優(yōu)勢使得其具有廣泛的應用前景。Lyric的概率計算芯片11Lyric公司Lyric在2006年由BenjaminVigoda和DavidReynolds創(chuàng)立，前者是MIT博士專攻概率計算，后者是芯片設計專家；LyricSemiconductor由MIT和DARPA資助；2011年6月ADI公司收購了Lyric公司；BenjaminVigodaDavidReynolds12BenjaminVigoda1999年在MIT獲得碩士學位，論文為ANonlinearDynamicSystemforSpreadSpectrumCodeAcquisition；2003年在MIT獲得博士學位，論文為AnalogLogicContinuous-TimeAnalogCircuitsforStatisticalSignalProcessing，初步形成概率計算實現(xiàn)的方向：模擬電路。畢業(yè)后進入Mitsubishi電子工作，2006年創(chuàng)業(yè)。13BenjaminVigoda的專利和論文BenjaminVigoda及Lyric公司擁有概率計算方面的專利8項；集中于2007年和2010年；在研究論文方面有2篇：[BenjaminVigoda2005]SynchronizationofPseudo-RandomSignalsbyForward-OnlyMessagePassingwithApplicationtoElectronicCircuits，IEEETRANSACTIONSONINFORMATIONTHEORY[BenjaminVigoda2010]LowPowerLogicForStatisticalInference，ISLPED’10,August18–20,2010,14LyricFAQSoisthisanalog,ordigital?是模擬的還是數(shù)字的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?是不是神經(jīng)網(wǎng)絡AlthoughLyric'stechnologycanbeadaptiveandcanimplementlearningalgorithms,itisfundamentallydifferentfromneuralnets.Neuralnetsmustbetrainedtoexhibitdesiredbehaviors.Oncethey'retrained,neuralnetscanbeveryhardtounderstandandnearlyimpossibletodebug.Lyric'stechnologycanbeprogrammedusingPSBLtoimplementpredictable,understandable,deterministicbehaviors.

可預測、可理解、確定性行為17基于FPGA的實現(xiàn)方案2010年加州大學伯克利分校的MingjieLin基于Virtex-5FPGA實現(xiàn)了一種Bayesiancomputingmachine(BCM)，速度與CPU、GPU相比10倍左右的改善。[MingjieLin2010]High-ThroughputBayesianComputingMachinewithReconfigurableHardware18國內(nèi)的研究工作北京信息科技大學光電信息與通信工程學院的楊曙輝教授在概率門實現(xiàn)方面有6項專利（2009年），2009年有3篇論文。[楊曙輝2009]具有概率分離計算功能的二級流水線電路設計；[楊曙輝2009]利用CMOS模擬電路設計實現(xiàn)的新型概率譯碼器；[楊曙輝2009]一種（5,2,3）網(wǎng)格碼CMOS