馬林華，劉士平，胡星，黃天宇，徐彬

?

系統(tǒng)極化碼低復雜度編碼優(yōu)化方案

馬林華1,2，劉士平1，胡星1，黃天宇1，徐彬3

（1. 空軍工程大學航空工程學院，陜西 西安 710038；2. 西安電子科技大學綜合業(yè)務網國家重點實驗室，陜西 西安 710071；3.空軍航空大學初級訓練基地，黑龍江 哈爾濱 150100）

為解決系統(tǒng)極化碼在編碼過程中因分步計算造成的時延和由循環(huán)迭代“異或”計算造成的計算復雜度，提出并定義了降維裂解策略，并由此提出了基于降維裂解策略的系統(tǒng)極化碼并行編碼算法，然后在AWGN信道下進行了仿真驗證和計算復雜度分析。結果表明，與傳統(tǒng)算法相比，所提算法編碼增益略優(yōu)或基本保持一致，但計算復雜度優(yōu)化率最高可達80.92%，更適合于硬件實現(xiàn)與工程應用，具有一定的實用價值。

極化碼；系統(tǒng)極化碼；并行編碼；復雜度；裂解；誤碼率

1 引言

信道糾錯編碼技術是提高數(shù)字通信系統(tǒng)抗干擾能力的關鍵技術之一。香農在有噪信道編碼理論中指出，存在可以達到香農限的碼字[1]。自2008年土耳其教授Arican基于信道極化定理提出極化碼（polar code）以來，極化碼憑借低復雜度編譯碼以及信道容量可達的優(yōu)勢在信道編碼領域占據(jù)重要地位，逐漸受到重視并開始應用于各個領域，擁有良好的發(fā)展前景[2-4]。

在編碼理論中，系統(tǒng)碼是輸出碼字包含輸入信息序列的一類編碼，即其信息比特會作為碼字的一部分直接顯現(xiàn)出來，而非系統(tǒng)碼的輸出碼字中不包含輸入信息序列。極化碼的標準形式是非系統(tǒng)碼，鑒于任意線性碼都可以轉換成系統(tǒng)碼，因此，極化碼也可被系統(tǒng)地編碼[5]。研究表明，由于在譯碼時系統(tǒng)碼的信息比特可以通過信道被直接觀察，系統(tǒng)極化碼相比于傳統(tǒng)的非系統(tǒng)極化碼具有更好的誤比特率性能[5]，且信息位可直接在系統(tǒng)碼碼字中表現(xiàn)出來，即不需要通過冗長的譯碼過程就能得到合理的準確估計，可快速確定所接收源符號的正確性[6-7]。因此，系統(tǒng)極化碼逐漸成為工程應用上的首選。

Arican[5]在首次提出系統(tǒng)極化碼的同時也給出了該系統(tǒng)極化碼的串行編碼算法，文獻[8]針對此算法進行了補充和復雜度分析。該算法將碼字拆分成2個部分并按序依次進行嵌套運算，由于該運算機制隨著碼長的增加，會提高2個計算步驟之間的錯誤傳播概率，并在2個計算步驟之間因等待造成系統(tǒng)時延。針對此問題，文獻[9-10]提出一種并行計算的編碼算法，利用雙極化結構取代串行編碼算法中分步計算的過程，可以實現(xiàn)任意碼長、碼率下對編碼碼字的一步直接計算。雖然此算法可以實現(xiàn)高度并行計算，降低因分步計算等待造成的時延及錯誤傳播，但是由于增加了一個額外的極化結構導致“異或”運算的次數(shù)隨著碼長增加而呈指數(shù)級增長，提高了系統(tǒng)的計算復雜度，降低了編碼效率，因此并沒有從根本上解決系統(tǒng)運算時延問題[11]?；谏鲜鰡栴}，本文提出基于降維裂解策略的系統(tǒng)極化碼并行編碼算法，基于“分治法”的思想將整段碼字裂解計算再合并，在保證可實時并行計算且不增加額外存儲空間的同時，降低了計算復雜度及錯誤傳播概率，更適用于硬件實現(xiàn)及實際應用。

2 系統(tǒng)極化碼及背景算法描述

2.1 極化碼與系統(tǒng)極化碼

2.2 系統(tǒng)極化碼并行編碼

針對上述問題，文獻[9]對此進行改進并提出了一種新型系統(tǒng)編碼器，該編碼器可以實現(xiàn)編碼的并行計算，并可直接經過編碼得到最終碼字，避免中間步驟的等待時延。

綜合式(8)~式(11)，可以整合出生成碼字計算式，即

該并行編碼算法的編碼器結構如圖1所示。由式(12)及圖1可以看出，該編碼算法將輸入碼字看作一個整體對編碼過程完成“一步計算”，解決了系統(tǒng)極化碼串行編碼因分段計算造成的時延及錯誤傳播問題。

3 降維裂解并行編碼算法

3.1 降維裂解策略

其中，元素表示碼樹第層第個子向量，,。可理解為類似于C語言中碼字向量子向量的指針。定義偏移向量，與分別表示圖2所示循環(huán)遞歸編碼碼樹的層數(shù)及各層中向量的序號。根據(jù)裂解策略及編碼碼樹觀察可得出，第層的個向量長度均為，且每層的向量按順序連接起來均為長度相同的碼字向量，這也驗證了上述定義的裂解算法的正確性。

圖3 循環(huán)迭代單元結構

第三次（③）：第三次也是最后一次返回該節(jié)點，此時已經遍歷了整個子樹并得到了式(17)的結果，最終返回父節(jié)點。

3.2 基于降維裂解策略的系統(tǒng)極化碼并行編碼

利用上述定義的降維裂解編碼策略，在保留文獻[8]中并行編碼算法優(yōu)點的基礎上，對式(12)進一步做低復雜度優(yōu)化，提出了系統(tǒng)極化碼的降維裂解并行編碼，具體算法描述如下。

式(22)所表示的優(yōu)化并行編碼算法可具體闡述如下。

上述2個步驟（即式(23)和式(24)）是依次進行的，利用所提降維裂解策略對傳統(tǒng)并行編碼算法進行低復雜度優(yōu)化，充分保留了傳統(tǒng)并行算法“一步計算”降低錯誤傳播的特點，最終得到基于降維裂解策略的并行編碼。

4 仿真驗證及復雜度分析

圖4 （256,128）系統(tǒng)極化碼不同編碼算法性能對比

圖5 （1 024,512）系統(tǒng)極化碼不同編碼算法性能對比

表1 系統(tǒng)極化碼編碼復雜度對比

表2 不同碼長下本文算法與傳統(tǒng)編碼算法計算復雜度優(yōu)化率對比

圖6 不同編碼算法復雜度變化趨勢

上述仿真驗證及復雜度分析表明，當碼長128時，降維裂解算法的編碼增益與并行系統(tǒng)編碼基本一致，但是計算復雜度明顯降低。相比于串行編碼，無論是計算復雜度還是編碼增益，都起到了優(yōu)化的效果。當碼長<128時，編碼增益與上述類似，但計算復雜略高于串行系統(tǒng)編碼。由于碼長較短使計算復雜度提升并不明顯，且編碼增益優(yōu)于串行編碼，因此本文算法在任意碼長下都可以發(fā)揮作用。

5 結束語

[1] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948, 19(4): 271-285.

[2] ARICAN E. Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051-3073.

[3] ARICAN E. A performance comparison of polar codes and reed- muller codes[J]. IEEE Communications Letters, 2008, 12(6): 447-449.

[4] ARICAN E. Channel combining and splitting for cutoff rate improvement[J]. IEEE Transactions on Information Theory, 2006, 52(2): 628-639.

[5] ARICAN E. Systematic polar coding[J]. IEEE Communications Letters, 2011, 8(15): 860-862.

[6] FENG B, ZHANG Q, JIAO J. An efficient rateless scheme based on the extendibility of systematic polar codes[J]. IEEE Access, 2017, PP(99): 1.

[7] YOO H, PARK I C. Partially parallel encoder architecture for long polar codes[J]. IEEE Transactions on Circuits & Systems II Express Briefs, 2015, 62(3): 306-310.

[8] LI L, ZHANG W. On the encoding complexity of systematic polar codes[C]//IEEE International System-on-Chip Conference. 2015: 415-420.

[9] SARKIS G, TAL I, GIARD P, et al. Flexible and low-complexity encoding and decoding of systematic polar codes[J]. IEEE Transactions on Communications, 2016, 7(65): 2732-2745.

[10] SARKIS G, GIARD P, VARDY A, et al. Fast polar decoders: algorithm and implementation[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(5): 946-957.

[11] TAL I, VARDY A. How to construct polar codes[J]. IEEE Transactions on Information Theory, 2011, 59(10): 6562-6582.

[12] RICHARDSON T J, SHOKROLLAHI M A, URBANKE R. Design of capacity-approaching irregular low-density parity-check codes [J]. IEEE Transaction on Information Theory, 2001, 47(2): 619-637.

[13] CHUNG S Y, RICHARDISON T J, URBANKE R. Analysis of sum-product decoding of low-density parity-check codes using a gaussian approximation[J]. IEEE Transactions on Information Theory, 2001, 47(2): 657-670.

[14] ZHANG Z Y, ZHANG L, WANG X B, et al. A split-reduced successive cancellation list decoder for polar codes[J]. IEEE Journal on Selected Areas in communications, 2016, 34(2): 292-302.

[15] BALATSOUKAS-STIMMING A, RAYMOND A J, GROSS W J, et al. Hardware architecture for list successive cancellation decoding of polar codes[J]. IEEE Transactions on Circuits & Systems II Express Briefs, 2014, 61(8): 609-613.

Optimizing low complexity encoding method for systematic polar code

MA Linhua1,2, LIU Shiping1, HU Xing1, HUANG Tianyu1, XU Bin3

1. Aeronautics and Astronautics Engineering College, Air Force Engineering University, Xi’an 710038, China 2. The State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China 3. Air Force Aviation University Primary Training Base, Harbin 150100, China

In order to solve the delay caused by step-by-step calculation and the computational complexity caused by iterative “exclusive-or” computation during the encoding process, a dimensionality reduction strategy was proposed and defined. Based on this, system polarization code parallel coding algorithm for cracking strategy was proposed. Simulation and computational complexity analysis were carried out on AWGN channel. The results show that the coding gain of the above algorithm is slightly better than the traditional one or almost the same, but the computational complexity is up to 80.92%, which is more suitable for hardware implementation and engineering application. It is more suitable for hardware implementation and has a certain practical value.

polar code, systematic polar code, parallel encoding, complexity, splitting decomposition, bit error rate

TN911.22

A

10.11959/j.issn.1000?436x.2018127

2018?01?11；

2018?05?19

國家自然科學基金資助項目（No.61472442）；陜西省科技攻關基金資助項目（No.2017GY-049）；航空科學基金資助項目（No.20155896025）

The National Natural Science Foundation of China (No.61472442), Shaanxi Province Scientific and Technological Project (No.2017GY-049), Aviation Science Foundation (No.20155896025)

馬林華（1965?），男，陜西漢中人，博士，空軍工程大學教授、博士生導師，主要研究方向為抗干擾通信、信道編碼、無線自組織網絡。

劉士平（1994?），男，黑龍江哈爾濱人，空軍工程大學碩士生，主要研究方向為信道編碼、極化碼、抗干擾通信。

胡星（1990?），男，河南南陽人，空軍工程大學博士生，主要研究方向為模擬量編碼、衛(wèi)星通信。

黃天宇（1993?），男，遼寧營口人，空軍工程大學碩士生，主要研究方向為Massive MIMO下行傳輸技術及信道仿真器設計。

徐彬（1993?），男，吉林吉林人，空軍航空大學工程師，主要研究方向為信道編碼、抗干擾通信。