基于gOMP算法的循環(huán)碼譯碼研究

姜恩華

(淮北師范大學(xué) 物理與電子信息學(xué)院, 安徽淮北 235000)

基于gOMP算法的循環(huán)碼譯碼研究

姜恩華

(淮北師范大學(xué) 物理與電子信息學(xué)院, 安徽淮北 235000)

在壓縮感知理論中，廣義正交匹配追蹤(gOMP)算法常用于解決l0范數(shù)的最小化問題.借助無噪聲干擾的壓縮感知觀測(cè)模型，提出了循環(huán)碼差錯(cuò)圖案E重構(gòu)的壓縮感知模型，以校驗(yàn)矩陣H作為測(cè)量矩陣，伴隨式S作為測(cè)量信號(hào)，采用gOMP算法重構(gòu)了差錯(cuò)圖案E，其與收碼R進(jìn)行模2加運(yùn)算，求得發(fā)碼C的估值.進(jìn)一步提出了校驗(yàn)矩陣H作為測(cè)量矩陣的構(gòu)成形式及其2個(gè)定理.詳細(xì)論述了gOMP算法重構(gòu)差錯(cuò)圖案E的計(jì)算過程.以(7,1)、(7,3)、(7,4)、(15,7)和(31,21)循環(huán)碼為例，分析了gOMP算法對(duì)循環(huán)碼的糾錯(cuò)能力；以(7,1)循環(huán)碼為例，分析了gOMP算法中原子選取個(gè)數(shù)s與糾錯(cuò)位數(shù)的關(guān)系.通過誤碼率和碼字C重構(gòu)的成功率，比較分析了gOMP算法和最大似然譯碼算法的譯碼效果.仿真實(shí)驗(yàn)表明，采用壓縮感知理論和廣義正交匹配追蹤gOMP算法實(shí)現(xiàn)循環(huán)碼譯碼是可行和有效的.

廣義正交匹配追蹤gOMP算法；循環(huán)碼；校驗(yàn)矩陣H；伴隨式S；差錯(cuò)圖案E

在壓縮感知理論中，廣義正交匹配追蹤(gOMP)算法屬于貪婪算法[1-2]，用于解決l0范數(shù)的最小化問題.在信道編碼中，循環(huán)碼是線性分組碼的一個(gè)子類，屬于多項(xiàng)式編碼，主要用于數(shù)據(jù)存儲(chǔ)和傳輸?shù)韧ㄐ蓬I(lǐng)域[3].

本文借助無噪聲條件下的壓縮感知理論[4-5]，采用校驗(yàn)矩陣H作為測(cè)量矩陣，伴隨式S作為測(cè)量信號(hào)y，建立了循環(huán)碼差錯(cuò)圖案E重構(gòu)的壓縮感知模型.通過gOMP算法，正確重構(gòu)了差錯(cuò)圖案E，然后對(duì)差錯(cuò)圖案E與收碼R進(jìn)行模2加運(yùn)算，計(jì)算碼字C的估值.

通過gOMP算法，對(duì)(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼進(jìn)行仿真實(shí)驗(yàn)，通過誤碼率和碼字C估值的成功率，分析gOMP算法的譯碼效果.實(shí)驗(yàn)結(jié)果表明，采用gOMP算法能夠?qū)崿F(xiàn)對(duì)(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼.

1 差錯(cuò)圖案E的壓縮感知模型

壓縮感知觀測(cè)模型分為無噪聲干擾和有噪聲干擾 2種[4-5].本文借助無噪聲干擾的壓縮感知模型實(shí)現(xiàn)差錯(cuò)圖案E的重構(gòu)，假設(shè)x是稀疏信號(hào)，A為測(cè)量矩陣，y為測(cè)量信號(hào)，則y可以表示為[4-5]:

y=A·x，

(1)假設(shè)已知測(cè)量矩陣A和測(cè)量信號(hào)y，如式(2)所示[4-5]通過求解‖x‖0范數(shù)的最小值求得稀疏信號(hào)x.

(2)

式(2)為無噪聲干擾的壓縮感知模型，可以通過貪婪算法求解‖x‖0的最小值，例如廣義正交匹配追蹤gOMP算法[1-2].

1.1 差錯(cuò)圖案E

差錯(cuò)圖案E等于發(fā)碼C減去收碼R，在二元域內(nèi)，差錯(cuò)圖案E等于發(fā)碼C與收碼R的模2加之和[3]：

E=C⊕R，

(3)

在隨機(jī)差錯(cuò)條件下，通常將差錯(cuò)圖案E看作一維稀疏信號(hào)，由于發(fā)碼C與校驗(yàn)矩陣H正交，其內(nèi)積為0，式(3)右乘以校驗(yàn)矩陣H的轉(zhuǎn)置矩陣HT，由于收碼R和HT的內(nèi)積定義為伴隨式S，所以伴隨式S與差錯(cuò)圖案E的關(guān)系為[3]

ST=H·ET.

(4)由于式(4)為欠定方程，若每次譯碼都求解式(4)，運(yùn)算量大.在最大似然譯碼算法中，通過查找標(biāo)準(zhǔn)陣列譯碼表得到伴隨式S與差錯(cuò)圖案E的對(duì)應(yīng)關(guān)系.

1.2 求解差錯(cuò)圖案E的線性規(guī)劃模型

根據(jù)最佳概率譯碼的準(zhǔn)則，選取概率最大的差錯(cuò)圖案E作為其估值，通過BSC二進(jìn)制對(duì)稱信道可以驗(yàn)證，重量最輕的差錯(cuò)圖案E出現(xiàn)的概率最大[3]，所以選取重量最輕的差錯(cuò)圖案E作為其估值，將式(4)作為求解差錯(cuò)圖案E的約束方程，將求解重量最輕的差錯(cuò)圖案E作為目標(biāo)函數(shù)，得到求解差錯(cuò)圖案E的線性規(guī)劃模型[6-7]:

(5)

1.3 重構(gòu)差錯(cuò)圖案E的壓縮感知模型

在二元域內(nèi)，差錯(cuò)圖案E的元素為0或1，差錯(cuò)圖案E的重量最輕等效為差錯(cuò)圖案E的l0范數(shù)‖E‖0最小，式(5)的目標(biāo)函數(shù)可以用求解‖E‖0范數(shù)最小值代替：

(6)

比較式(6)與式(2)發(fā)現(xiàn)，若將差錯(cuò)圖案E作為一維稀疏信號(hào)，伴隨式S作為測(cè)量信號(hào)，校驗(yàn)矩陣H作為測(cè)量矩陣，可將式(6)定義為重構(gòu)差錯(cuò)圖案E的壓縮感知模型.

與文獻(xiàn)[8-10]提供的方法相比，采用壓縮感知理論和gOMP算法重構(gòu)差錯(cuò)圖案E不需要查找標(biāo)準(zhǔn)陣列譯碼表，運(yùn)算量小，計(jì)算過程簡(jiǎn)單.

2 測(cè)量矩陣

若把校驗(yàn)矩陣H作為測(cè)量矩陣，伴隨式S作為測(cè)量信號(hào)，實(shí)現(xiàn)差錯(cuò)圖案E的重構(gòu).校驗(yàn)矩陣H的稀疏度Spark(H)與差錯(cuò)圖案E的l0范數(shù)‖E‖0之間的關(guān)系為[11]

‖E‖0

(7)

校驗(yàn)矩陣H的構(gòu)成形式如式(8)所示[12-15]:

H=[In-k|P],

(8)

其中，子矩陣P的列向量的最小重量為dmin-1，dmin為碼字C的最小距離.

定理1校驗(yàn)矩陣H的稀疏度Spark為非零碼字的最小重量，即循環(huán)碼碼字的最小距離dmin.

證明在循環(huán)碼中，校驗(yàn)矩陣H的稀疏度Spark表示校驗(yàn)矩陣H中線性相關(guān)的最小列數(shù)，碼字C與校驗(yàn)矩陣H正交，所以碼字C與校驗(yàn)矩陣H的乘積為0，即[15]

C·HT=[cn-1,…,c1,c0][hn-1,…,h1,h0]T=
cn-1·hn-1+…+c1·h1+c0·h0=0.

(9)

線性分組碼非零碼字的最小重量為碼字的最小距離dmin，碼字C的碼元cn-1,…,c1,c0至少有dmin個(gè)非零元素，式(9)至少有dmin個(gè)非零項(xiàng)，所以校驗(yàn)矩陣H至少有dmin個(gè)列線性相關(guān)，dmin為校驗(yàn)矩陣H的稀疏度Spark.

定理2差錯(cuò)圖案E重構(gòu)的必要條件是差錯(cuò)圖案E的l0范數(shù)小于或等于糾錯(cuò)能力t.

證明線性分組碼的糾錯(cuò)能力t為

(10)

由于校驗(yàn)矩陣H的稀疏度Spark(H)與循環(huán)碼碼字的最小距離dmin相等，差錯(cuò)圖案E的l0范數(shù)與校驗(yàn)矩陣H的稀疏度Spark(H)的關(guān)系如式(7)所示，所以有

‖E‖0≤t.

(11)

能使式(11)成立的差錯(cuò)圖案E就是式(6)最稀疏的解.

(12)

當(dāng)循環(huán)碼的校驗(yàn)矩陣H作為測(cè)量矩陣時(shí)，可以求出(7，1)循環(huán)碼的校驗(yàn)矩陣H的稀疏度Spark為7，由式(7)，計(jì)算其差錯(cuò)圖案E的l0范數(shù)最大值為3，根據(jù)定理1，其碼字的最小距離dmin=7，根據(jù)式(10)，(7，1)循環(huán)碼的糾錯(cuò)能力t為3，所以式(11)成立.同理可求得：(7，3)循環(huán)碼的校驗(yàn)矩陣H的稀疏度Spark為4，其差錯(cuò)圖案E的l0范數(shù)最大值為1，(7，3)循環(huán)碼的糾錯(cuò)能力t為1，所以式(11)成立；(7，4)循環(huán)碼的校驗(yàn)矩陣H的稀疏度Spark為3，其差錯(cuò)圖案E的l0范數(shù)最大值為1，(7，4)循環(huán)碼的糾錯(cuò)能力t為1，所以式(11)成立.

3 廣義正交匹配追蹤(gOMP)算法

將廣義正交匹配追蹤(gOMP)算法[1-2]應(yīng)用于差錯(cuò)圖案E的重構(gòu)，根據(jù)差錯(cuò)圖案E的壓縮感知模型，分析gOMP算法在重構(gòu)差錯(cuò)圖案E時(shí)的計(jì)算過程和譯碼效率.

3.1 gOMP算法重構(gòu)差錯(cuò)圖案E的計(jì)算過程

3.1.1 輸入數(shù)據(jù)

校驗(yàn)矩陣H作為測(cè)量矩陣，伴隨式S作為測(cè)量信號(hào)y，差錯(cuò)圖案E的稀疏度為K，最大原子選擇個(gè)數(shù)為s.

3.1.2 計(jì)算過程

1)參數(shù)初始化：求測(cè)量矩陣的行數(shù)和列數(shù)，測(cè)量信號(hào)y作為初始化殘差r0，索引集合Λ0為空集，按照索引集合Λ0選出的矩陣A0為空集，迭代次數(shù)l=1.

2)計(jì)算殘差rl=〈rl-1,aj〉,1≤j≤N，并按降序排列，按從大到小的順序選取s個(gè)殘差，記錄s個(gè)殘差對(duì)應(yīng)的矩陣A的列數(shù)j組成列序號(hào)集合J0.

3)更新索引集合Λl=Λl-1∪J0和索引集合Λl選出的矩陣Al=Al-1∪aj(j∈J0) .

4)計(jì)算y=Al·θl的最小二乘解，計(jì)算稀疏信號(hào)的估值：

6)判斷殘差rl的值是否小于預(yù)設(shè)的條件，若小于則跳出循環(huán)，或判斷迭代次數(shù)l+1后是否大于稀疏度K，若大于則結(jié)束循環(huán).

gOMP算法通過增加原子選擇的個(gè)數(shù)s，提高對(duì)稀疏信號(hào)的重構(gòu)效率，在文獻(xiàn)[1-2]中，對(duì)gOMP、OMP、ROMP、CoSaMP、StOMP算法的重構(gòu)效率進(jìn)行了比較，顯示gOMP算法對(duì)稀疏信號(hào)重構(gòu)具有優(yōu)越性.

3.2 差錯(cuò)圖案E重構(gòu)

以(15，7)循環(huán)碼為例，采用gOMP算法重構(gòu)差錯(cuò)圖案E.(15，7)循環(huán)碼的校驗(yàn)矩陣H如式(13)所示.根據(jù)收碼R和校驗(yàn)矩陣H，計(jì)算伴隨式S=R·HT，把伴隨式S作為測(cè)量信號(hào)，校驗(yàn)矩陣H作為測(cè)量矩陣，通過gOMP算法，重構(gòu)(15，7)循環(huán)碼的差錯(cuò)圖案E，如表1所示.差錯(cuò)圖案E也可以通過求解欠定線性方程組S=E·HT得到，求解(15，7)循環(huán)碼的差錯(cuò)圖案E的線性方程組如式(13)所示，若(15，7)循環(huán)碼的糾錯(cuò)位數(shù)取1，將重量為0或1的差錯(cuò)圖案E代入線性方程組式(13)，求出伴隨式S，列出標(biāo)準(zhǔn)陣列譯碼表，與表1比較，可以驗(yàn)證gOMP算法重構(gòu)的差錯(cuò)圖案E是正確的.同理，也可以采用gOMP算法正確重構(gòu)(7，1)、(7，3)、(7，4)和(31，21)循環(huán)碼的差錯(cuò)圖案E.

(13)

表1 gOMP算法重構(gòu)(15，7)循環(huán)碼的差錯(cuò)圖案E的結(jié)果

4 gOMP算法的循環(huán)碼譯碼效果分析

采用gOMP算法，實(shí)現(xiàn)(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼的糾錯(cuò)，分別采用各自的校驗(yàn)矩陣H作為測(cè)量矩陣，分析gOMP算法對(duì)循環(huán)碼的糾錯(cuò)能力以及gOMP算法中原子選擇的個(gè)數(shù)s對(duì)循環(huán)碼糾錯(cuò)位數(shù)的影響.

4.1 gOMP算法的循環(huán)碼糾錯(cuò)能力

以(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼為例，測(cè)試gOMP算法對(duì)循環(huán)碼的糾錯(cuò)能力，把差錯(cuò)位數(shù)從0逐漸增加，能被100%重構(gòu)的收碼的最大差錯(cuò)位數(shù)為其糾錯(cuò)能力t，因?yàn)闇y(cè)量信號(hào)長(zhǎng)度M=n-k是伴隨式S的長(zhǎng)度，采用校驗(yàn)矩陣H作為測(cè)量矩陣，伴隨式S作為測(cè)量信號(hào)，差錯(cuò)位數(shù)為差錯(cuò)圖案E中1的個(gè)數(shù).實(shí)驗(yàn)結(jié)果如圖1所示，可以看出goMP算法對(duì)差錯(cuò)位數(shù)為3的(7，1)循環(huán)碼的糾錯(cuò)能力為100%，對(duì)差錯(cuò)位數(shù)為1的(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼的糾錯(cuò)能力為100%.同時(shí)可看出gOMP 算法對(duì)(7，3)、(15，7)和(31，21)循環(huán)碼中差錯(cuò)位數(shù)為2和3的收碼也有一定的糾錯(cuò)能力.對(duì)差錯(cuò)位數(shù)為2的(15,7)循環(huán)碼的糾錯(cuò)能力為60%.(7，3)和(31，21)循環(huán)碼的糾錯(cuò)能力近似相同.

4.2 原子選擇個(gè)數(shù)s對(duì)循環(huán)碼糾錯(cuò)的影響

在每次迭代時(shí)，gOMP算法計(jì)算傳感矩陣A各列與殘差的內(nèi)積，并按照降序排列，依次選擇s個(gè)最大的殘差來更新索引集合，提高了gOMP算法的重構(gòu)效率.以(7，1)循環(huán)碼為例，選擇s=2，3，4，測(cè)試gOMP算法對(duì)(7，1)循環(huán)碼的糾錯(cuò)能力，如圖2所示，可以看出s=2時(shí)，能糾正3位錯(cuò)誤，s=3時(shí)，能糾正2位錯(cuò)誤，s=4時(shí)，能糾正1位錯(cuò)誤，所以原子個(gè)數(shù)s=2為最佳選擇，能夠?qū)崿F(xiàn)(7，1)循環(huán)碼的糾錯(cuò)能力為3.同理，可以驗(yàn)證：(7，4)循環(huán)碼在s=3時(shí)，對(duì)差錯(cuò)位數(shù)為1的收碼重構(gòu)的成功率為100%.(7，3)循環(huán)碼在s=1，2，3，4時(shí)，對(duì)差錯(cuò)位數(shù)為1的收碼重構(gòu)的成功率為100%，當(dāng)s=4時(shí)，對(duì)差錯(cuò)位數(shù)為2的收碼的糾錯(cuò)能力為30%.(15，7)循環(huán)碼在s=1，2，3，4時(shí)，對(duì)差錯(cuò)位數(shù)為1的收碼重構(gòu)的成功率為100%，當(dāng)s=3時(shí)，對(duì)差錯(cuò)位數(shù)為2的收碼的糾錯(cuò)能力為80%.(31，21)循環(huán)碼在s=1，2，3，4時(shí)，對(duì)差錯(cuò)位數(shù)為1的收碼重構(gòu)的成功率為100%，當(dāng)s=1時(shí)，對(duì)差錯(cuò)位數(shù)為2的收碼的糾錯(cuò)能力為35%.

圖1 測(cè)量信號(hào)長(zhǎng)度M對(duì)循環(huán)碼糾錯(cuò)能力的影響

圖2 原子選擇個(gè)數(shù)s對(duì)(7，1)循環(huán)碼糾錯(cuò)能力的影響(M=6，N=7)

5 循環(huán)碼譯碼的仿真實(shí)驗(yàn)設(shè)計(jì)

5.1 仿真實(shí)驗(yàn)設(shè)計(jì)

按照如圖3所示的線性分組碼的譯碼步驟設(shè)計(jì)仿真實(shí)驗(yàn)[3]，首先產(chǎn)生N個(gè)信息元組m，信息元組m與生成矩陣G相乘生成碼字C，對(duì)碼字C進(jìn)行2PSK調(diào)制，已調(diào)信號(hào)通過高斯白噪聲信道AWGN，信噪比SNR取值范圍為0～12 dB，在每個(gè)信噪比SNR點(diǎn)，選取N=50 000個(gè)m信息分組.在接收端，對(duì)接收信號(hào)進(jìn)行2PSK解調(diào)，得到收碼R，借助校驗(yàn)矩陣H計(jì)算伴隨式S.將伴隨式S作為測(cè)量信號(hào)，校驗(yàn)矩陣H作為測(cè)量矩陣，通過廣義正交匹配追蹤gOMP算法，重構(gòu)差錯(cuò)圖案E，重構(gòu)的差錯(cuò)圖案E與收碼R進(jìn)行模2加運(yùn)算，計(jì)算碼字C的估值.

圖3 線性分組碼的編譯碼過程

5.2 gOMP算法實(shí)現(xiàn)循環(huán)碼譯碼

借助Matlab軟件編寫程序，實(shí)現(xiàn) gOMP算法和最大似然譯碼算法對(duì)循環(huán)碼譯碼的仿真實(shí)驗(yàn)，本文以(7，4)、(15，7)和(31，21)循環(huán)碼為例，從譯碼的誤碼率和碼字C重構(gòu)的成功率兩方面比較gOMP算法和最大似然譯碼算法的譯碼效果[16]，譯碼的誤碼率如圖4所示，碼字C重構(gòu)的成功率如圖5所示.

圖4 循環(huán)碼譯碼的誤碼率比較

圖5 循環(huán)碼譯碼的碼字C估值成功率比較

從圖4中可以看出，在同一個(gè)譯碼算法中，(15，7)循環(huán)碼譯碼的誤碼率最低.當(dāng)信噪比SNR相同時(shí)，最大似然算法譯(15，7)循環(huán)碼的誤碼率最低，當(dāng)信噪比SNR為5.2 dB時(shí)，其誤碼率低于10-5.gOMP算法譯(31，21)循環(huán)碼的誤碼率最高，當(dāng)信噪比SNR為7.6 dB時(shí)，其誤碼率低于10-5.采用最大似然算法和gOMP算法譯(7，4)循環(huán)碼的誤碼率近似相同，當(dāng)信噪比SNR為6.6 dB時(shí)，其誤碼率低于10-5.gOMP算法譯(15，7)與(7,4)循環(huán)碼的誤碼率近似，當(dāng)信噪比SNR為6.6 dB時(shí)，其誤碼率低于10-5.從圖5中可以看出，最大似然算法譯(15，7)循環(huán)碼的碼字C重構(gòu)的成功率最高，在信噪比SNR為5.8 dB時(shí)，碼字C重構(gòu)的成功率趨于100%.采用最大似然算法和gOMP算法譯(7，4)循環(huán)碼的碼字C重構(gòu)成功率近似，當(dāng)信噪比SNR為7.2 dB時(shí)，碼字C重構(gòu)的成功率趨于100%.gOMP算法譯(15，7)與(7，4)循環(huán)碼碼字C重構(gòu)成功率近似，當(dāng)信噪比SNR為7.2 dB時(shí)，碼字C重構(gòu)的成功率趨于100%.當(dāng)信噪比相同時(shí)，gOMP算法譯(31，21)循環(huán)碼的碼字C重構(gòu)成功率低于最大似然算法；當(dāng)信噪比SNR為6.6 dB時(shí)，最大似然算法重構(gòu)(31，21)循環(huán)碼的成功率趨于100%；當(dāng)信噪比SNR為8 dB時(shí)，gOMP算法重構(gòu)(31，21)循環(huán)碼的成功率趨于100%.gOMP算法和最大似然算法重構(gòu)(7，4)、(15，7)和(31，21)循環(huán)碼的差錯(cuò)率和成功率如表2所示.

表2 循環(huán)碼重構(gòu)的差錯(cuò)率和成功率

*為差錯(cuò)率，**為成功率.

通過分析仿真實(shí)驗(yàn)結(jié)果得到：采用gOMP算法能夠?qū)崿F(xiàn)(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼.與最大似然譯碼算法相比，在循環(huán)碼譯碼的成功率趨于100%的條件下，gOMP算法譯碼時(shí)的信噪比SNR比最大似然算法大1.4 dB.但gOMP算法是根據(jù)伴隨式S和校驗(yàn)矩陣H重構(gòu)差錯(cuò)圖案E的，從而計(jì)算出碼字C的估值，不需要查找標(biāo)準(zhǔn)陣列譯碼表，即可實(shí)現(xiàn)對(duì)(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼.

6 結(jié) 語

借助無噪聲干擾壓縮感知的觀測(cè)模型，提出了求解差錯(cuò)圖案E的線性規(guī)劃模型和壓縮感知模型.采用gOMP算法實(shí)現(xiàn)(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼，提出了校驗(yàn)矩陣H作為測(cè)量矩陣的構(gòu)成形式和2個(gè)定理.采用伴隨式S作為測(cè)量信號(hào)，通過gOMP算法重構(gòu)差錯(cuò)圖案E，對(duì)E與收碼R進(jìn)行模2加運(yùn)算，計(jì)算發(fā)碼C的估值.借助(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼，分析了gOMP算法對(duì)循環(huán)碼的糾錯(cuò)能力及gOMP算法中原子選取個(gè)數(shù)s與糾錯(cuò)位數(shù)的關(guān)系.通過譯碼的誤碼率和碼字C重構(gòu)的成功率，比較分析了gOMP算法和最大似然譯碼算法對(duì)(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼效果.實(shí)驗(yàn)結(jié)果表明：采用gOMP算法能夠?qū)崿F(xiàn)對(duì)(7，1)、(7，3)、(7，4)、(15，7)和(31，21)循環(huán)碼的譯碼.

[1]JIANW,SEOKBEOPK,BYONGHYOS.Generalizedorthogonalmatchingpursuit[J].IEEETransactionsonSignalProcessing,2012,60(12):6202-6216.

[2] WANG J, KWON S, LI P, et al. Recovery of sparse signals via generalized orthogonal matching pursuit: A new analysis[J].IEEETransactionsonSignalProcessing,2016,64(4):1076-1089.

[3] 曹雪虹，張宗橙.信息論與編碼[M].第2版，北京:清華大學(xué)出版社,2009. CAO X H, ZHANG Z C.InformationTheoryandCoding[M]. 2nd ed. Beijing: Tsinghua University Press,2009.

[4] CANDES E J, ROMBERG J, TAO T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[5] DONOHO D L. Compressed sensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[6] DASKALAKIS C, DIMAKIS A G, KARP R M, et al. Probabilistic analysis of linear programming decoding[J].IEEETransactionsonInformationTheory,2008,54(8):3565-3578.

[7] DIMAKIS A G, VONTOBEL P O. LP decoding meets LP decoding: A connection between channel coding and compressed sensing[C]//Forty-SeventhAnnualAllertonConference. Illinois:IEEI,2009:8-15.

[8] 李耀輝,趙海豹,馬春芽.循環(huán)碼譯碼的Dixon結(jié)式 方法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2011,34(4):602-617. LI Y H, ZHAO H B, MA C Y. Decoding cyclic codes by using Dixon resultant method[J].ActaMathematicaeApplicataeSinica,2011,34(4):602-617.

[9] AUGOT D, BARDET M, FAUGRE J C. On the decoding of binary cyclic codes with the Newton identities[J].JournalofSymbolicComputation,2009,44(12):1608-1625.

[10] LOUSTAUNAU P, YORK E V. On the decoding of cyclic codes using Gr?bner bases[J].ApplicableAlgebrainEngineeringCommunication&Computing,1997,8(6):469-483.

[11] ELAD M.SparseandRedundantRepresentations:FromTheorytoApplicationsinSignalandImageProcessing[M]. New York：Springer Publishing Company,2010:26-30.

[12] LIN L, LIU F, JIAO L. Compressed sensing by collaborative reconstruction on over complete dictionary [J].SignalProcessing,2014,103:92-102.

[13] 董小亮,楊良龍,趙生妹,等.用信道編碼構(gòu)造壓縮感知測(cè)量矩陣[J].信號(hào)處理,2013,29(7):809-815. DONG X L, YANG L L, ZHAO S M, et al. Channel coding for compressed sensing measurement matrix[J].JournalofSignalProcessing,2013,29(7):809-815.

[14] 蘆存博,肖嵩,權(quán)磊.基于二進(jìn)制序列族的壓縮感知測(cè)量矩陣構(gòu)造[J].電子與信息學(xué)報(bào),2016,38(7): 1682-1688. LU C B, XIAO S, QUAN L. Construction of compressed sensing measurement matrix based on binary sequence family[J].IntroductionofJournalofElectronics&InformationTechnology,2016,38(7): 1682-1688.

[15] 張景雄,陽柯,郭建中.壓縮感知的信息論解譯[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2014,39(11):1261-1268. ZHANG J X, YANG K, GUO J Z. Information-theoretic interpretations of compressive sampling[J].GeomaticsandInformationScienceofWuhanUniversity,2014,39(11):1261-1268.

[16] 張軼,達(dá)新宇,褚振勇.低密度奇偶校驗(yàn)碼的壓縮感知重構(gòu)[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版,2015,45(3): 985-990. ZHANG Y, DA X Y, CHU Z Y. Compressed sensing reconstruction of LDPC code[J].JournalofJilinUniversity：EngineeringandTechnologyEdition,2015,45(3): 985-990.

JIANG Enhua

(School of Physics and Electronic Information, Huaibei Normal University,Huaibei 235000,Anhui Province,China)

The generalized orthogonal matching pursuit gOMP algorithm has been used in the compressed sensing theory to solve the minimizing problem of thel0norm. According to the compressed sensing model under the no noise condition, the compressed sensing model of the reconstructing error patternEof the cyclic code is built in this paper. With the check matrixHas the measurement matrix, the syndromeSas the measurement signal, the error patternEis reconstructed using the gOMP algorithm, while the value of the code wordCis calculated by the receiving codeRadding the error patternEon modulo 2. Furthermore, we provide the form of the check matrixH, and propose two relevant theorems. The error correction ability of the gOMP algorithm is analyzed through some cyclic code examples, and the relationship between the selecting atom numbersof the gOMP algorithm and the error correction bits is investigated. Finally, based on the bit error rate and the code wordCreconstructing success rate, the decoding effects of the gOMP algorithm and the maximum likelihood algorithm are analyzed and compared. The simulation experiment results prove that the compressed sensing theory and gOMP algorithm are feasible and effective in decoding the cyclic code.

generalized orthogonal matching pursuit(gOMP)algorithm; cyclic code; check matrixH; syndromeS; error patternE

TN 911.7

：A

：1008-9497(2017)05-555-06

2016-06-30.

國(guó)家自然科學(xué)基金資助項(xiàng)目(41475017， 11504121)；安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2016A628，KJ2016A650).

姜恩華(1974-)，ORCID: http:// orcid.org/0000-0002-5944-4541，男，碩士，副教授，主要從事數(shù)字通信技術(shù)與信息處理研究，E-mail：jianghnhb@126.com.

10.3785/j.issn.1008-9497.2017.05.010

ResearchonthecycliccodesdecodingbasedonthegeneralizedorthogonalmatchingpursuitgOMPalgorithm.Journal of Zhejiang University (Science Edition)，2017,44(5):555-560,575