夏閣淞，葛萬成

（同濟(jì)大學(xué)中德學(xué)院，上海 200092）

0 引 言

自從香農(nóng)在1948年發(fā)表了一篇代表著現(xiàn)代信息論開篇的文章后，通信技術(shù)就在不斷快速發(fā)展。近幾年，極化碼在編解碼領(lǐng)域中取得了突破性進(jìn)展，從而激起了極化碼理論研究的快速發(fā)展。Arikan Erdal于2008年提出極化碼，并在對(duì)稱的二進(jìn)制無記憶信道及任意的連續(xù)無記憶信道中證明了極化碼相較于Turbo碼和LDPC碼更能達(dá)到香農(nóng)極限，且用極化碼實(shí)現(xiàn)的通信系統(tǒng)能達(dá)到更高的通信帶寬。所以，極化碼是目前公認(rèn)的“最好”的碼。目前，極化碼的譯碼實(shí)現(xiàn)方式主要有軟件和硬件兩種方式。軟件的實(shí)現(xiàn)方式因CPU串行工作模式限制了譯碼速度的提升，而FPGA因其具有快速并行計(jì)算的能力能彌補(bǔ)這一缺陷。此外，極化碼的遞歸結(jié)構(gòu)能夠?qū)崿F(xiàn)資源共享并簡化計(jì)算過程，這一特點(diǎn)表明極化碼易于FPGA實(shí)現(xiàn)。

目前，關(guān)于極化碼的譯碼算法主要有置信度傳播（Brief Propagation，BP）算法、最大似然比（Maximum Likelyhood，ML）算法和連續(xù)刪除（Successive Cancellation，SC）算法。這3種算法中，BP和ML算法由于在運(yùn)算過程中涉及較多的乘除法運(yùn)算，因此不利于FPGA實(shí)現(xiàn)；而SC算法在譯碼過程中主要通過加減和位運(yùn)算實(shí)現(xiàn)，所以適于FPGA實(shí)現(xiàn)[1]。

1 極化碼解碼算法的改進(jìn)

Arikan Erdal給出了極化碼的一種解碼算法，即最經(jīng)典的連續(xù)刪除譯碼算法。而極化碼的建立過程即對(duì)極化信道的選擇過程，實(shí)際上這種選擇是以SC譯碼算法的性能為標(biāo)準(zhǔn)的。這是由于從極化信道轉(zhuǎn)移概率式中可知，極化后的信道不是相互獨(dú)立的：后面的信號(hào)信道的譯碼取決于前面序號(hào)的信道信息。這意味著必須保障前面的結(jié)果全部正確，極化碼才能達(dá)到信道容量。但是，這要求碼長必須足夠長。

由于信道的極化過程，實(shí)際上是按照最優(yōu)的SC譯碼算法執(zhí)行的，因此對(duì)于極化碼來說，只有這一類譯碼算法才能充分利用極化碼的性能。隨后誕生了簡化的SC算法，即SSC譯碼算法。這幾種方法將極化碼的性能在延遲和正確性兩個(gè)方面得到了提高。

SC譯碼算法的輸出取決于兩部分，分別是信道現(xiàn)在的接收信號(hào)和之前所有的判決。轉(zhuǎn)移概率如下：

通過這兩個(gè)信息可以計(jì)算目前正在判決的這一位的結(jié)果。判決時(shí)，如果解碼器發(fā)現(xiàn)這一位是凍結(jié)比特，那么將直接判決為之前約定好的0或者1。如果解碼器發(fā)現(xiàn)這一位是信息比特，需要通過計(jì)算u^i=0時(shí)和u^i=1的轉(zhuǎn)移概率后得到對(duì)數(shù)似然比，最終得到判定結(jié)果。所以，從延遲上講，該算法在一個(gè)時(shí)鐘周期最多得出一位結(jié)果，解碼速度較慢。

對(duì)數(shù)似然比在通信系統(tǒng)中的作用，一般是用做軟解碼。對(duì)數(shù)似然比的定義為：

判決函數(shù)用L可以表示為：

LLR的遞歸計(jì)算可以表示為：

到了最底端即N=1時(shí)，是遞歸函數(shù)的出口，從而最終完成譯碼任務(wù)。

2 解碼器的FPGA實(shí)現(xiàn)

2.1 FFT結(jié)構(gòu)的SC解碼器

FFT結(jié)構(gòu)的SC解碼器結(jié)構(gòu)，如圖1所示。該方案具有以下優(yōu)點(diǎn)：由于這個(gè)結(jié)構(gòu)并沒有對(duì)硬件進(jìn)行復(fù)用，而是使用了較多硬件，所以簡化了控制結(jié)構(gòu)，使得實(shí)現(xiàn)相對(duì)容易；不妨假設(shè)該方案不使用時(shí)鐘信號(hào)，那么可以做到在一幀的情況下，相比于使用時(shí)鐘信號(hào)控制的結(jié)構(gòu)速度更快。但是，該結(jié)構(gòu)也存在一些缺陷：由于該結(jié)構(gòu)的硬件數(shù)量多且多數(shù)硬件是重復(fù)的，所以對(duì)硬件的利用率較低，帶來了功率上的浪費(fèi)（如果采用這個(gè)結(jié)構(gòu)，那么可以每一個(gè)模塊都會(huì)一直消耗功率消耗，且有相當(dāng)多的功率是完全浪費(fèi)的）；由于沒有時(shí)鐘信號(hào)的控制，該結(jié)構(gòu)對(duì)于外界的噪聲，抗干擾能力會(huì)大幅下降。如果采用D觸發(fā)器這樣的寄存器，那么只有在時(shí)鐘信號(hào)有效的時(shí)候電路才真正工作，其他時(shí)候即便有噪聲，也不會(huì)對(duì)電路結(jié)果造成影響；由于缺少控制信號(hào)，所以很難對(duì)電路的工作進(jìn)度進(jìn)行把控，且極化碼的工作流程是按照步驟一步一步進(jìn)行的，所以更加需要控制信號(hào)的加入，如果輸入信號(hào)速度過快，超過了電路的處理速度，就會(huì)導(dǎo)致輸出的信號(hào)產(chǎn)生錯(cuò)誤。針對(duì)這些缺陷，需要大幅優(yōu)化該結(jié)構(gòu)。

圖1 FFT結(jié)構(gòu)的SC解碼器結(jié)構(gòu)

2.2 流水線的樹結(jié)構(gòu)SC解碼器

流水線的樹結(jié)構(gòu)SC解碼器，如圖2所示。相比于FFT結(jié)構(gòu)，它進(jìn)行了一定優(yōu)化：加入了時(shí)間控制模塊。加入這個(gè)模塊后，該編碼器的過程可以實(shí)現(xiàn)控制。

圖2 流水線的樹結(jié)構(gòu)SC解碼器

每經(jīng)過一個(gè)時(shí)鐘周期，該結(jié)構(gòu)都會(huì)計(jì)算出一個(gè)值，這個(gè)值可能是F也可能是G。計(jì)算出來后，這個(gè)值會(huì)被保存到寄存器，以便后續(xù)計(jì)算時(shí)被使用。所以，該結(jié)構(gòu)使用7個(gè)寄存器來存放。因?yàn)榧僭O(shè)碼長為1 024，那么按照這樣的結(jié)構(gòu)，需要1 024個(gè)寄存器保存之前計(jì)算的結(jié)果，顯然非常浪費(fèi)。為了優(yōu)化空間，本文提出的結(jié)構(gòu)中復(fù)用了存儲(chǔ)LLR的寄存器來存儲(chǔ)結(jié)果，可節(jié)省空間。

使用該結(jié)構(gòu)另一個(gè)優(yōu)點(diǎn)是，由于該結(jié)構(gòu)的設(shè)計(jì)并不是針對(duì)某一種信道或一種凍結(jié)比特序列，而是對(duì)信道的類型不做限制，使得該結(jié)構(gòu)具有了靈活的特性。事實(shí)上，這樣的靈活帶來的結(jié)果是對(duì)硬件的使用率不高，是該結(jié)構(gòu)的兩大缺點(diǎn)之一。本文提出的結(jié)構(gòu)將針對(duì)某種特定的信道做出優(yōu)化，大幅提高了硬件使用率。

該結(jié)構(gòu)的第二個(gè)缺點(diǎn)是延遲高。從圖2可以看出，每經(jīng)過一個(gè)時(shí)鐘周期，該結(jié)構(gòu)只計(jì)算一步，且有很多不需要計(jì)算的部分。在本文提出的結(jié)構(gòu)中，硬件電路會(huì)自動(dòng)略過不需要計(jì)算的部分，減少了延遲。

2.3 F模塊和G模塊的改進(jìn)設(shè)計(jì)

F模塊和G模塊的輸入輸出量，分別如圖3和圖4所示。

圖3 F模塊的輸入輸出量

圖4 G模塊的輸入輸出量

F模塊有2個(gè)輸入，分別是LLR1和LLR2，也就是對(duì)數(shù)似然比，輸出是一個(gè)值，把2個(gè)輸入的符號(hào)相乘后取絕對(duì)值更小的：

G模塊則相對(duì)比較復(fù)雜，有3個(gè)輸入量，除了2個(gè)LLR之外，還需要1個(gè)之前計(jì)算的u^。計(jì)算過程也更加復(fù)雜，涉及到乘法和加法。需注意，做乘法運(yùn)算時(shí)，只是和-1乘，帶來了優(yōu)化的空間。

F模塊和G模塊一一對(duì)應(yīng)，然后利用多路選擇器選擇當(dāng)前工作是哪一個(gè)模塊。傳統(tǒng)設(shè)計(jì)的弊端在于F和G的數(shù)量永遠(yuǎn)相等，但是這并不是必須的。在某些特殊電路中，很有可能不需要那么多G，可能需要很多F。所以，本文提出的結(jié)構(gòu)會(huì)把F和G模塊完全獨(dú)立。它們不相互影響，只在需要對(duì)方提供數(shù)據(jù)的時(shí)候才有交互[2]。

本文改進(jìn)的F模塊中，對(duì)于正負(fù)符號(hào)的判斷，只提取了最高位。這是因?yàn)檩斎胧橇炕蟮?位信息，其中最高位是符號(hào)位，不需要在和0去比較，提高了運(yùn)算速度[3]。同時(shí)，兩個(gè)提取的符號(hào)位的乘法通過異或XOR實(shí)現(xiàn)，這在電路中的復(fù)雜度會(huì)遠(yuǎn)遠(yuǎn)小于一個(gè)乘法器。再將異或運(yùn)算的結(jié)果即符號(hào)位去和更小的絕對(duì)值做最后的運(yùn)算，得到F模塊的輸出。

在G模塊中，論文采用的方法是多路選擇器。將第一個(gè)輸入信號(hào)的正負(fù)值輸入到多路選擇器中，根據(jù)第三個(gè)信號(hào)決定正負(fù)號(hào)后，將其與第二個(gè)信號(hào)求和。

F模塊和G模塊的設(shè)計(jì)思路，分別如圖5和圖6所示。

圖5 matlab中F模塊的設(shè)計(jì)思路

圖6 matlab中G模塊的設(shè)計(jì)思路

3 算法仿真與實(shí)驗(yàn)結(jié)果

函數(shù)f和g的計(jì)算涉及了乘法和除法，在FPGA中實(shí)現(xiàn)比較復(fù)雜。因此改進(jìn)最小和算法，在對(duì)數(shù)域中用等價(jià)函數(shù)來代替，等價(jià)式為：

信道的輸出和運(yùn)算過程中的值都是浮點(diǎn)數(shù)，不利于在FPGA中實(shí)現(xiàn)，所以最后輸出前需要進(jìn)行硬裁決。

本文對(duì)該結(jié)構(gòu)進(jìn)行了實(shí)現(xiàn)，下面對(duì)碼長為4的結(jié)果做出詳細(xì)說明，如圖7所示。

圖7來自于testbench腳本，規(guī)定0時(shí)刻把輸入給到電路，目的是首先測試電路是否需要一個(gè)上電準(zhǔn)備過程，其次可以第一時(shí)間得到電路的輸出。由圖7可以得知，雖然在第一時(shí)間把輸入的信號(hào)給了電路，但是電路并不能在第一時(shí)間把這個(gè)信號(hào)用來處理。這是由于在硬件內(nèi)部，需要對(duì)該電壓進(jìn)行保持，其次需要經(jīng)過緩沖器才可以把該信號(hào)交給電路內(nèi)部處理，最后得到輸出。經(jīng)過測量得到，電路在第32 ns的時(shí)候準(zhǔn)備完畢，然后進(jìn)行下一步工作。

從圖8可以看出，電路的輸出信號(hào)正是符合預(yù)期地一個(gè)個(gè)相繼輸出，且結(jié)果通過和軟件仿真的對(duì)比確保了正確性。

經(jīng)過測量，直到最后一個(gè)輸出結(jié)果顯示完畢，也就是電路工作完畢的時(shí)間，是45.548 ns。這意味著從電路開始工作到結(jié)束，共花費(fèi)了13.548 ns。

本文提出的譯碼器結(jié)構(gòu)可以根據(jù)不同的凍結(jié)比特為自動(dòng)生成對(duì)應(yīng)電路，具有非常好的適應(yīng)性和可拓展性。在硬件使用方面，相比于傳統(tǒng)的譯碼器，硬件各個(gè)部分的使用大幅減小，包括LUT和FF。這其中的原因是該譯碼器減少了無用的F和G模塊，同時(shí)復(fù)用了寄存器[4]。

此處對(duì)于碼長為128的情況做出具體說明，如表1和表2所示。

表1 N=128時(shí)傳統(tǒng)SC譯碼器的硬件消耗

表2 N=128時(shí)本文提出的SSC譯碼器的硬件消耗，R=0.25

對(duì)比表1和表2可以看出，在核心指標(biāo)LUT和FF上，SSC結(jié)構(gòu)具有明顯優(yōu)勢，分別減少了63.9%和65.7%的硬件消耗，提高了性能。

本文提出的譯碼器的第二個(gè)優(yōu)點(diǎn)是減少了譯碼器的延遲，可以大幅改善傳統(tǒng)SC譯碼器延遲高的缺點(diǎn)，大大提高極化碼的競爭力。

可以看出，隨著凍結(jié)比特的比例不斷增加，SSC譯碼器的性能不斷提高。在25%的比特是凍結(jié)比特的時(shí)候，平均減小延遲55%；在50%的比特是凍結(jié)比特的時(shí)候，平均減小延遲53%；在75%的比特是凍結(jié)比特的時(shí)候，平均減小延遲62%，總平均提高57%。從圖9可以看出，在實(shí)際的FPGA上運(yùn)行結(jié)果符合預(yù)期。

圖7 輸入信號(hào)的實(shí)現(xiàn)后仿真結(jié)果

圖8 輸出端的信號(hào)變化情況

圖9 在FPGA上的運(yùn)行結(jié)果符合預(yù)期

本文實(shí)現(xiàn)的結(jié)構(gòu)在對(duì)應(yīng)的FPGA上，最短可以在時(shí)鐘周期為7.968 ns的情況下工作。下面直接對(duì)吞吐量進(jìn)行計(jì)算，結(jié)果如表3所示[5]。

表3 不同碼長情況下的吞吐量

4 結(jié) 語

本文提出的譯碼器結(jié)構(gòu)可以根據(jù)不同的凍結(jié)比特自動(dòng)生成對(duì)應(yīng)電路，具有非常好的適應(yīng)性和可拓展性。在硬件使用方面，相比于傳統(tǒng)的譯碼器，對(duì)減小了各個(gè)部分的硬件使用，包括LUT和FF。究其原因，該譯碼器減少了無用的F和G模塊，復(fù)用了寄存器。此外，這種結(jié)構(gòu)能夠減少譯碼器的延遲，可以大幅改善傳統(tǒng)SC譯碼器延遲高的缺點(diǎn)，大大提高了極化碼的競爭力。隨著凍結(jié)比特的比例不斷增加，譯碼器的性能不斷提高，而本文采用的Matlab腳本可以針對(duì)不同凍結(jié)比特的特點(diǎn)，自動(dòng)生成任意碼長的對(duì)應(yīng)結(jié)構(gòu)，具有更高的靈活性。