極化碼編碼器的硬件實現

舒長青，沙 金

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

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

1 極化碼基礎

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

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

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

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

2 極化碼編碼

2.1 生成矩陣

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

這里稱GN為生成矩陣。可以得到

式中:BN是比特反轉矩陣，?是兩個矩陣的Kronecker積。

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

2.2 信息位的選取

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

3 編碼器設計

3.1 基本模塊

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

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

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

圖3 基本處理模塊

3.2 讀取和存儲機制

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

1)在每個時鐘周期內，按順序讀入32位信息比特。假設原始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的數據輸入圖3模塊，同時將處理后的1，5，…，61存入RAM 3的地址1;第35周期，讀出RAM 1和RAM 2地址3的數據，將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。需要注意的是，每次應該同時讀取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)重復步驟2)和步驟3)進行迭代處理，以下要設置讀存儲器的地址順序依次為:第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個周期，故經過6次迭代共198個周期后，此時信息比特已經完成R5的變換，可化簡為64個W4信道的編碼，而基于W4信道的編碼模塊比較簡單，用簡單的異或門即可實現，可以對存儲器中各地址的信息比特進行并行操作，此處不作贅述。至此，編碼完成。

4 結語

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

:

［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］李斌，王學東.極化碼原理及應用［J］.通信技術，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設計與實現［J］.電視技術，2011，35(7):49－51.