[發明專利]一種快速樹圖分解方法

有效

• 申請號: 200810038756.X
• 申請日: 2008-06-10
• 公開（公告）號: CN101299612A
• 公開（公告）日: 2008-11-05
• 發明（設計）人: 周秦英;李明齊;楊曾;徐其
• 申請（專利權）人: 上海瀚訊無線技術有限公司
• 主分類號: H03M13/11
• 分類號: H03M13/11
• 代理公司: 上海思微知識產權代理事務所
• 代理人: 屈蘅

技術領域

本發明涉及信道編碼理論、圖論以及有限域理論，具體的說，是涉及一 種快速樹圖分解方法。

背景技術

洪水信息傳遞策略是迭代譯碼算法中常用的信息傳遞方法，在一次迭代 中，所有的變量節點傳遞初始信息給相鄰的校驗節點，然后所有的校驗節點 傳遞信息給其相鄰的變量節點，在每次迭代中，變量節點根據上一次迭代得 到的新信息和信道信息，對相鄰的校驗節點進行信息更新；校驗節點則是利 用當前迭代得到的新信息進行信息更新。

近年來，為了提高信息傳遞的收斂速度，現有技術在洪水信息傳遞策略 的基礎上，發展出多種快速收斂的信息傳遞策略。請參閱文獻[1]“A?new schedule?for?decoding?low-density?parity-check?codes”，Proc.IEEE?GlobeCom， Texas，2001(Y.Mao?and?A.H.Banihashemi)，其中根據圖的結構特性，搜索得 到每個變量節點的最小環長，因為采用洪水信息傳遞策略時，每次迭代會使 該變量節點的信息傳遞延伸一個節點，為了保證每個變量節點傳遞出的信息 沒有通過環路反饋回來，需要針對不同變量節點的最小環長來限定每個變量 節點在不同環路的譯碼迭代次數，消除正反饋，這種方法可以降低誤比特率 和不可檢錯誤概率。

文獻[2]“Parallel?versus?sequential?updating?for?belief?propagation decoding”Physica?A?330(2003)259-270(Haggai?Kfir，Ido?Kanter)以及文獻[3] “Shuffled?belief?propagation?decod-ing”，The?Proceedings?36^th?Asilomar Conferenceon?Signals，Systemsand?Computers，PacificGrove，USA，November 2002(J.Zhang?and?M.Fossorier)中還給出了一種串行信息更新算法，與洪水信 息傳遞算法不同的是，在一次迭代中，它不是先對所有的變量節點進行信息 更新，再對所有的校驗節點進行信息更新，而是在一次迭代中，交替更新變 量節點和校驗節點的信息，更新某個變量節點傳遞給校驗節點信息時，同時 將與該變量節點相連的所有校驗節點給這個變量節點的信息都先進行更新， 然后再利用這些新信息更新該變量節點對每個校驗節點的信息，然后更新下 一個變量節點的信息。當所有變量節點信息更新結束后，一次迭代完成，進 入下一次迭代。

此外，請參閱文獻[4]“An?Efficient?Message-Passing?Schedule?for?LDPC decoding”，IEEE?Communication?Letters，NO.4，pp：223-226，2004(Eran?Sharon， Simon?Litsyn?and?Jacob?Goldberger)以及文獻[5]“Convergence?Analysis?of Serial?Message-Passing?Schedules?for?LDPC?Decoding”，proceeding?of?the?fourth international?symposium?on?TURBO?codes，2006(Eran?Sharon，Simon?Litsyn?and Jacob?Goldberger)，其給出了文獻[2]以及[3]中的串行信息傳遞策略的密度進 化理論公式。

文獻[5]“Replica?Shuffled?Belief?Propagation?Decoding?of?LDPC?Codes”， MITSUBISHI?ELECTRIC?RESEARCH?LABORATORIES?http://www.merl.com (Juntan?Zhang，Yige?Wang，Marc?Fossorier，and?Jonathan?S.Yedidia)是在文獻[2] 的基礎上，對變量節點的度數進行分類，與文獻[2]不同的是串行更新變量節 點的信息時，更新的順序有了限定，將變量節點按照度數大小進行排序，先 更新度數大的變量節點，當更新其它與此變量節點相連的節點的信息時，該 變量節點作為先驗信息更為準確，提高了譯碼收斂速度。