極化碼編碼器的硬件實現(xiàn)

舒長青，沙 金

(南京大學(xué)微電子所，江蘇南京 210046)

最近，由 Arikan提出的極化碼［1－2］是編碼理論的一個重大突破。極化碼是目前唯一的一種有確定構(gòu)造方式的能在二進制離散無記憶信道下達到香農(nóng)容量的信道編碼方式，同時，它具有較低的編解碼復(fù)雜度O(NlogN)，N是碼長。然而，在實際應(yīng)用中，為了達到理想的糾錯性能，極化碼的碼長一般需要大于210，故編碼器難以對所有信息比特同時編碼，否則硬件實現(xiàn)比較困難，本文提出了一種基于部分并行輸入編碼器的結(jié)構(gòu)設(shè)計。

1 極化碼基礎(chǔ)

對于二元離散無記憶信道W(B－DMC W)，將N個獨立的信道W按照一定的方式進行合并，可以獲得長度為N的矢量信道，即有對于B－DMC W，WN:xN→yN，其中滿足N=2n，n≥0。當(dāng)n=0時，W1=W，n=1時的信道合成如圖1所示。

圖1 兩個W信道的合并示意圖

對于更一般的情況，由N個信道W合成的信道為WN。WN可以遞歸地由兩個WN/2信道構(gòu)成，其中WN/2是由N/2個W信道合并而成［3］。如圖2所示，其中RN是個排列運算，將奇數(shù)比特按順序置于偶數(shù)比特前，即(1，2，3，…，N)→ (1，3，…，N－1，2，4，…，N)。

圖2 基于信道WN/2的信道WN

2 極化碼編碼

2.1 生成矩陣

如圖2所示，從信息比特u1N通過線性變化得到中間參量，再經(jīng)過RN變換，即奇數(shù)比特與偶數(shù)比特分離，然后進入兩個分離信道WN/2，也即轉(zhuǎn)變?yōu)閮蓚€N/2碼長的極化碼，經(jīng)過lbN次迭代之后，可將信息比特編碼為，即可等效地記一個N階矩陣GN［4］，使得

這里稱GN為生成矩陣?？梢缘玫?/p>

式中:BN是比特反轉(zhuǎn)矩陣，?是兩個矩陣的Kronecker積。

式中:GN(Λ)表示GN中與Λ中元素對應(yīng)的那些行所組成的子矩陣，GN(ΛC)為GN(Λ)的陪集。

2.2 信息位的選取

信息位的選取對編碼有著重要的影響，是極化碼編碼的重要內(nèi)容。如果選擇完全好的信道進行信息比特傳輸，當(dāng)編碼塊長度達到一定范圍時，就能實現(xiàn)真正的無失真可靠通信。E.Arikan提出一種信息位選取的方法［5］，針對BEC信道具有較低復(fù)雜度和實用性，但對于其他信道未能找到一個有效的方法去實現(xiàn)這個編碼構(gòu)造。自極化碼被提出以來，很多學(xué)者對其信息位選取方法展開了研究。目前主要有3種選取方法，Monte－Carlo方法、BEC方法及Density evolution方法。

3 編碼器設(shè)計

3.1 基本模塊

極化碼在理論上可以在B－DMC上通信達到香農(nóng)極限，但是需要比較長的碼字，通常N≥210，上文描述了極化碼的生成矩陣和信息位的選取，但由于碼長過大，極化碼的編碼器設(shè)計比較復(fù)雜，本實驗提出了一種基于部分并行輸入的編碼器硬件結(jié)構(gòu)，可以化簡至比較簡單的W4信道的編碼模塊。

編碼器的實現(xiàn)主要是兩個模塊，一個是RN變換，采取一種特定的讀取和存儲機制實現(xiàn)，另一個模塊實現(xiàn)相鄰比特的異或，每次處理32 bit，即16個二進制異或門即可實現(xiàn)。

如圖3所示，1 024 bit每次輸入32位，將奇數(shù)位與相鄰的偶數(shù)位比特異或，將異或后的16位奇數(shù)位和未變的16位偶數(shù)位分別存入兩個RAM中，其中偶數(shù)位用16位寄存器寄存一個周期，實現(xiàn)兩個RAM的“乒乓”存儲。Memory swich為地址選擇器，按特定順序讀取和存儲RAM中各地址的比特實現(xiàn)RN變換。4個RAM皆為單端口RAM，深度為32，每個地址存儲16 bit。用RAM 1和RAM 2分別存儲第一次處理后的奇偶位比特，然后將兩個RAM中的比特分別讀出再通過該模塊，只要在每次迭代的過程中適當(dāng)?shù)馗淖兊刂愤x擇器，將特定地址的比特按順序讀出，經(jīng)過處理更新完畢后再存入另兩個RAM中，進行迭代操作。

圖3 基本處理模塊

3.2 讀取和存儲機制

在信息比特的處理中，采用一種特定的讀取和存儲機制，利用“乒乓存儲”，在讀取數(shù)據(jù)的同時向其他RAM寫入數(shù)據(jù)，可以提高系統(tǒng)的吞吐率和性能，實現(xiàn)數(shù)據(jù)的無縫連接和處理，具體步驟如下:

1)在每個時鐘周期內(nèi)，按順序讀入32位信息比特。假設(shè)原始1 024 bit按順序編號為1，2，3，…，1 024。在第1周期，將處理后的1，3，…，31存入RAM 1的地址1;第2周期，將33，35，…，63存入 RAM 2的地址1，將上次處理后寄存了1個周期的2，4，…，32存入RAM 1的地址2;第3 周期，將65，67，…，95 存入 RAM 1 的地址3，寄存了1 個周期的34，36，…，64存入RAM 2的地址2;依此類推，33個周期后可將信息比特全部存入RAM 1和RAM 2中，此時存儲的比特順序如圖4所示。

圖4 第1次處理后比特順序

2)將RAM 1和RAM 2中的比特讀出，再輸入圖3的計算單元，將處理后的比特存入RAM 3和RAM 4中。具體操作為:在第34周期，讀出RAM 1和RAM 2地址1的數(shù)據(jù)輸入圖3模塊，同時將處理后的1，5，…，61存入RAM 3的地址1;第35周期，讀出RAM 1和RAM 2地址3的數(shù)據(jù)，將65，69，…，125存入RAM 4的地址1，寄存了1個周期的3，7，…，63存入RAM 3的地址2;依此類推，操作方式如步驟1)，此時讀取RAM 1和RAM 2中的地址順序為1，3，5，7，9，11，13，15，17，19，21，23，25，27，29，31，2，4，6，8，10，12，14，16，18，20，22，24，26，28，30，32。需要注意的是，每次應(yīng)該同時讀取2個RAM相同地址的信息比特，33個周期后可將信息比特全部存入RAM 3和RAM 4中，此時RAM 3和RAM 4中存儲的比特順序如圖5所示(依舊為原始編號)。

圖5 第2次迭代后比特順序

3)如步驟2)，將RAM3和RAM4中的比特讀出，再輸入圖3的計算單元，將處理后的比特存入RAM1和RAM2中，操作方式如上，此時讀取RAM3和RAM4的地址順序為1，3，5，7，9，11，13，15，2，4，6，8，10，12，14，16，17，19，21，23，25，27，29，31，18，20，22，24，26，28，30，32。

4)重復(fù)步驟2)和步驟3)進行迭代處理，以下要設(shè)置讀存儲器的地址順序依次為:第4次迭代順序為1，3，5，7，2，4，6，8，9，11，13，15，10，12，14，16，17，19，21，23，18，20，22，24，25，27，29，31，26，28，30，32;第 5 次迭代順序為 1，3，2，4，5，7，6，8，9，11，10，12，13，15，14，16，17，19，18，20，21，23，22，24，25，27，26，28，29，31，30，32;第 6 次迭代順序為1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30，31，32。

5)每次迭代過程需要33個周期，故經(jīng)過6次迭代共198個周期后，此時信息比特已經(jīng)完成R5的變換，可化簡為64個W4信道的編碼，而基于W4信道的編碼模塊比較簡單，用簡單的異或門即可實現(xiàn)，可以對存儲器中各地址的信息比特進行并行操作，此處不作贅述。至此，編碼完成。

4 結(jié)語

極化碼的出現(xiàn)引起了巨大的影響，很多研究者都進行了相關(guān)的研究，本文提出了一種基于部分并行輸入的編碼器硬件結(jié)構(gòu)。類似于LDPC等信道編碼器可用DSP［6］或FPGA實現(xiàn)，本文提出的編碼器也可在硬件平臺上實現(xiàn)。作為一個新出現(xiàn)的技術(shù)，極化碼還有很多的研究需要進行，特別是在譯碼上，找到一個合適可行并且易于硬件實現(xiàn)的譯碼算法十分必要。

:

［1］ARIKAN E.Channel polarization:a method for constru－cting capacityachieving codes for symmetric binary－input me－moryless channels［J］.IEEE Trans.Inform.Theory，2009，55(7):3051－3073.

［2］李斌，王學(xué)東.極化碼原理及應(yīng)用［J］.通信技術(shù)，2012，45(10):21－23.

［3］MARI R，TANAKA T.Performance and construction of polar codes on symmetric binary－input memoryless channels［C］//Proc.ISIT 2009.Seoul，Korea:IEEE Press，2009:1496－1500.

［4］ARIKAN E.Channel combining and splitting for cutoff rate improvement［J］.IEEE Trans.Inform.Theory，2006，52(2):628－639.

［5］ARIKAN E.Source polarization［C］//Proc.2010 IEEE International Symposium on Informantion Theory Proceedings(ISIT).Pasadena，CA，USA:IEEE Press，2010:899－903.

［6］于佳，董淑福，張健.LDPC碼快速編碼器的DSP設(shè)計與實現(xiàn)［J］.電視技術(shù)，2011，35(7):49－51.