無線通信報告ldpc碼的線性規(guī)劃譯碼算法-文庫吧
2025-04-23 09:45 本頁面
【正文】 碼的譯碼 LDPC 碼的譯碼算法可分為硬判決譯碼算法和軟判決譯碼算法。硬判決算法操作簡單，易于硬件實現(xiàn)，但是性能較差 。軟判決算法性能較好，但實現(xiàn)復雜度太高。在軟判決算法方面，以 Gallager 提出的消息傳遞算法 (Message Passing Algorithm, MPA)為主，在因子圖上進行消息迭代地傳播算法，也稱置信傳播(Belief Propagation, BP)算法。推廣和積 (SumProduct, SP)算法和變異算法，如最小和 (Minimum Sum, MS)譯碼算法 。 軟判 決迭代譯碼算法均具有譯碼速度快，譯碼性能優(yōu)良，復雜度較低的優(yōu)點。然而，迭代算法在許多情況下，比如當 Tanner圖中存在環(huán)時，并不能保證算法收斂 。并且，如果算法收斂，收斂點也不一定全是有意義的。也就是說對于迭代譯碼算法來講，盡管在大多數(shù)情況下都能收斂到最大似然碼字，依然缺乏理論根據(jù)，因此采用迭代譯碼時，譯碼性能難以分析。 20xx 年， 等人 ,利用線性規(guī)劃 (Linear Programming, LP)松弛，對LDPC 碼的最大似然 (Maximum Likehood, ML)譯碼進行近似求解，建立 了二進制分組碼的松弛規(guī)劃譯碼模型，從而提出了 LP 譯碼算法。作為 ML譯碼的估計，理論證明該算法具有最大似然保持特性，也就是，一旦最優(yōu)解為整數(shù)解，那么該解一定為最大似然碼字。同時，當 Tanner 圖中存在環(huán)時，可以通過添加限制條件，改進 LP 譯碼的性能。 四 線性規(guī)劃譯碼算法 （一） 線性規(guī)劃以及線性規(guī)劃松弛 線性規(guī)劃是指在一個線性目標函數(shù)下，求解一系列線性約束式集合的問題，即在由一系列線性約束式形成的可行域中尋找線性目標函數(shù)的最優(yōu)值，是較簡單的一種凸優(yōu)化問題。許多簡單的優(yōu)化問題都可以利用線性規(guī)劃求解。 如果一個優(yōu)化問 題的目標函數(shù)是線性的，但當且僅當變量取整數(shù)時才有意義(比如變量代表候車廳的座椅數(shù)目 )，那么采用線性規(guī)劃對此問題無法直接求解。這是因為線性規(guī)劃的可行域是連續(xù)的，求解 LP 問題所得最優(yōu)解可能不是整數(shù)，從而可能導致解無意義。這樣的優(yōu)化問題為整數(shù)線性規(guī)劃 (Integer Linear Programming, ILP)問題，其可行域由離散的整數(shù)點組成。 LP 問題可以通過優(yōu)化算法高效地求解， ILP 卻通常是一個 NPhard 問題。如果我們對 ILP 問題中限制變量為整數(shù)的條件進行修改，使可行域變?yōu)榘锌尚姓麛?shù)點在內(nèi)的連 續(xù)域，那么這個 ILP 問題便被松弛成一個 LP 問題，可以通過高效的優(yōu)化算法來求解。此時 LP 問題的解可能是 ILP 問題的最優(yōu)解，也可能不是，如果不是，可以采用現(xiàn)有方法修正結(jié)果使其有意義。在很多問題中，只需簡單的對每個值進行舍入處理，使其變成整數(shù)，就可以得到 ILP 的最優(yōu)解。 周珍珠 13212895 信息與通信工程專業(yè)（電 A） 4 * ? ?a r g m a x Pr [ | ] a r g m in l n ( Pr [ | ] )yCyCy y y y y??? ? ?這種通過轉(zhuǎn)化成 LP 問題來求解 ILP 問題的方法被稱為線性規(guī)劃松弛。線性規(guī)劃松弛廣泛應用在計算科學和組合優(yōu)化上的近似求解算法中，用以解決各種難以求解的凸優(yōu)化問題。 （二） 等價 ILP 問題 ILP 問題是指在有限個整數(shù)離散點組成的可行域中，找到使線性代價函 數(shù)最小的可行點的問題，常見形式如下： minimize: aTx subject to: x?Zn 其中 x 表示一個 n 維的變量 ,a 表示系數(shù)向量 , aTx 稱為代價函數(shù)， minimize:aTx 稱為目標函數(shù)， Zn 表示 n 維整數(shù)域。 對 ML 譯碼的目標函數(shù)進行如下變換 使得代價函數(shù)符合 ILP 中最小值優(yōu)化的特點。假設信道具有離散無記憶的特性， 那么1? ?Pr [ | ] Pr [ | ]n iiiy y y y???，式（ ）可等價為 *11? ?a r g m in l n ( P r [ | ] ) a r g m in l n ( P r [ | ] )nni i i iy C i y C iy y y y y? ? ? ?? ? ? ? ? ? （ ） 此時 ML譯碼已變?yōu)樽钚』瘑栴}，但仍然是非線性的。對代價函數(shù)整體進行整數(shù)的加減乘除運算并不會改變最優(yōu)解的值，在信道特性已知的情況下，1 ?ln (Pr [ | 0 ])n iii yy???為常數(shù)，將其加入到式（ ）的代價函數(shù)中，有 * 11? ?a r g m in { l n ( P r [ | 0 ] ) l n ( P r [ | ] ) }nni i i iy C i iy y y y y? ? ?? ? ? ? ? : 0 : 1? ?Pr [ | 0 ] Pr [ | 0 ]a r g m in { l n ( ) l n ( ) }? ?Pr [ | 0 ] Pr [ | 1 ]iii i i iyC i y i yi i i iy y y yy y y y? ????? ? ? ? :1?P r [ | 0 ]a r g m in l n ( )?P r [ | 1 ]iiiyC iyiiyyyy? ???? ? 1?Pr [ | 0 ]a r
研究報告相關推薦
鄂ICP備17016276號-1