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

?

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

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

（1. 空軍工程大學(xué)航空工程學(xué)院，陜西 西安 710038；2. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；3.空軍航空大學(xué)初級(jí)訓(xùn)練基地，黑龍江 哈爾濱 150100）

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

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

1 引言

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

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

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

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

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

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

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

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

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

3 降維裂解并行編碼算法

3.1 降維裂解策略

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

圖3 循環(huán)迭代單元結(jié)構(gòu)

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

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

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

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

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

4 仿真驗(yàn)證及復(fù)雜度分析

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

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

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

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

圖6 不同編碼算法復(fù)雜度變化趨勢(shì)

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

5 結(jié)束語(yǔ)

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61472442）；陜西省科技攻關(guān)基金資助項(xiàng)目（No.2017GY-049）；航空科學(xué)基金資助項(xiàng)目（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?），男，陜西漢中人，博士，空軍工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榭垢蓴_通信、信道編碼、無(wú)線自組織網(wǎng)絡(luò)。

劉士平（1994?），男，黑龍江哈爾濱人，空軍工程大學(xué)碩士生，主要研究方向?yàn)樾诺谰幋a、極化碼、抗干擾通信。

胡星（1990?），男，河南南陽(yáng)人，空軍工程大學(xué)博士生，主要研究方向?yàn)槟M量編碼、衛(wèi)星通信。

黃天宇（1993?），男，遼寧營(yíng)口人，空軍工程大學(xué)碩士生，主要研究方向?yàn)镸assive MIMO下行傳輸技術(shù)及信道仿真器設(shè)計(jì)。

徐彬（1993?），男，吉林吉林人，空軍航空大學(xué)工程師，主要研究方向?yàn)樾诺谰幋a、抗干擾通信。