BCH（63，56）性能分析及仿真

詹亞鋒，解得準(zhǔn)

（清華大學(xué) 宇航技術(shù)研究中心，北京 100084）

BCH（63，56）性能分析及仿真

詹亞鋒，解得準(zhǔn)

（清華大學(xué) 宇航技術(shù)研究中心，北京 100084）

作為一種實(shí)現(xiàn)復(fù)雜度低的信道編碼方式，BCH（63，56）碼被廣泛應(yīng)用在空間遙控鏈路中，具有檢測2 bit錯(cuò)誤及糾正1 bit錯(cuò)誤的性能。從理論分析和計(jì)算機(jī)仿真兩個(gè)方面研究了BCH（63，56）碼的編碼性能。在介紹BCH（63，56）碼編譯碼原理的基礎(chǔ)上，對其誤碼率性能進(jìn)行了理論計(jì)算和蒙特卡洛仿真。結(jié)果表明：當(dāng)譯碼后的誤碼率為1×10-5時(shí)，BCH（63，56）碼的編碼增益可達(dá)2.1 dB。

BCH（63，56）；空間通信；蒙特卡洛仿真

0 引 言

在衛(wèi)星測控通信中，可靠的測控信息傳輸至關(guān)重要。通常在地面站發(fā)射功率足夠的情況下，為了降低航天器實(shí)現(xiàn)的復(fù)雜度，上行遙控鏈路不采用信道編碼。但是在特殊場景，如深空通信中，超遠(yuǎn)的傳輸距離使得上行鏈路增加信道編碼變得十分必要。

空間數(shù)據(jù)系統(tǒng)咨詢委員會(huì)（Consultative Committee for Space Data Systems，CCSDS）在其發(fā)布的建議書[1-2]中對上述問題進(jìn)行了說明，建議在空間通信遙控鏈路中采用BCH（63，56）作為信道編碼。該編碼可以糾正1 bit的錯(cuò)誤，辨識2 bit的錯(cuò)誤。

多篇文獻(xiàn)對BCH（63，56）的在軌實(shí)現(xiàn)方式進(jìn)行了研究[3,6-7]，但是尚未發(fā)現(xiàn)有文獻(xiàn)對BCH（63，56）的編碼增益進(jìn)行討論，這給工程設(shè)計(jì)人員帶來了困惑。為此，本文通過理論分析和計(jì)算機(jī)仿真兩個(gè)方面，對BCH（63，56）的編碼性能進(jìn)行分析和討論。論文結(jié)構(gòu)如下：第1節(jié)對BCH的編碼原理進(jìn)行介紹；第2節(jié)基于BCH（63，56）的糾錯(cuò)能力，對其編碼增益進(jìn)行理論分析；第3節(jié)對其編碼增益進(jìn)行蒙特卡洛仿真，并和理論性能進(jìn)行對比；第4節(jié)對全文進(jìn)行小結(jié)。

1 BCH編碼原理簡介

1.1 BCH碼編碼原理

BCH碼是循環(huán)碼的一種，循環(huán)碼是被廣泛使用的線性分組碼[8-9]。它是漢明碼的一種推廣形式，可以糾正多個(gè)錯(cuò)誤。在給定糾錯(cuò)能力的前提下，可以設(shè)計(jì)不同碼長的BCH碼來實(shí)現(xiàn)要求的糾錯(cuò)功能[10]。

不失一般性，假設(shè)研究的BCH碼為BCH（n，k），其中：n為編碼之后數(shù)據(jù)幀的長度（單位是bit）；k為要傳送的消息長度（單位是bit）。設(shè)要傳送的消息矢量為

編碼之后的數(shù)據(jù)幀為

編碼器實(shí)現(xiàn)的功能為將長度為kbit的消息矢量線性映射為長度為nbit的碼字，這兩者之間的關(guān)系為

其中：G為生成矩陣，可以表示為

其中：每一行都是一個(gè)n維的行向量。

編碼的過程也可以寫成多項(xiàng)式的形式，已知消息矢量，可以得到消息多項(xiàng)式為了將該消息多項(xiàng)式生成碼字多項(xiàng)式，需要在該消息多項(xiàng)式的基礎(chǔ)上乘以（n-k）次生成多項(xiàng)式。

如果按照式（6）生成碼字矩陣，則有用的信息并不是集中在已編碼矩陣的右側(cè)，因此，需要首先對消息矩陣進(jìn)行移位

將移位之后的消息多項(xiàng)式除以生成多項(xiàng)式

其中：a(x)和b(x)分別為商式和余式。其中余式為

實(shí)際用來發(fā)送的碼字多項(xiàng)式為消息多項(xiàng)式和余式的和

因此，BCH（63，56）編碼的步驟可以概括為[3]：

1）用xn-k乘以消息多項(xiàng)式m(x)；

2）用相乘之后得到的多項(xiàng)式除以生成多項(xiàng)式g(x)，得到余式為b(x)（余式即為校驗(yàn)多項(xiàng)式）；

3）碼字多項(xiàng)式為消息多項(xiàng)式和校驗(yàn)位多項(xiàng)式之和c(x)=xn-km(x)+b(x)。

對于BCH（63，56）碼來說，已知其生成碼多項(xiàng)式為g(x)= 1 +x2+x6+x7。因此，具體的編碼過程為[11]：

1）將56位消息序列轉(zhuǎn)化成消息多項(xiàng)式；

2）在消息多項(xiàng)式的基礎(chǔ)上乘以x7；

3）將得到的多項(xiàng)式除以生成多項(xiàng)式，得到余式，最后與得到的余式相加，得到碼字多項(xiàng)式；

4）將生成的碼字多項(xiàng)式轉(zhuǎn)化為矢量的形式。

1.2 BCH碼編譯碼原理

采用伴隨式譯碼[5]的方法對BCH（n，k）碼進(jìn)行譯碼。伴隨式譯碼的主要思想是：為了判斷接收到的信息有沒有發(fā)生錯(cuò)誤，需要根據(jù)生成多項(xiàng)式判斷該序列對應(yīng)的伴隨式。如果伴隨式為零，則說明接收到的序列沒有發(fā)生錯(cuò)誤或者發(fā)生了錯(cuò)誤但是變成了另外一個(gè)有效碼字（這種錯(cuò)誤不可檢測），如果伴隨式不為零，需要根據(jù)錯(cuò)誤圖樣和伴隨式的關(guān)系判斷發(fā)生錯(cuò)誤的位置并進(jìn)行力所能及的糾錯(cuò)。錯(cuò)誤圖樣實(shí)際上是一個(gè)和碼字有相同長度的矩陣。對于只能糾正1位錯(cuò)誤的BCH（63，56）碼來說，其對應(yīng)的錯(cuò)誤圖樣矩陣中只有1個(gè)“1”，其他元素全部為“0”。如果對接收到的碼字求解伴隨式，該伴隨式和某一個(gè)錯(cuò)誤圖樣恰好匹配，則該錯(cuò)誤圖樣矩陣中的“1”的位置即為接收碼字中發(fā)生錯(cuò)誤的位置。對該位置上的碼元取反（碼字“1”糾正為“0”，碼字“0”糾正為“1”），即可對該碼字進(jìn)行糾正。同理，如果研究的BCH(n,k)碼具有糾正多位錯(cuò)誤的能力，則其對應(yīng)的錯(cuò)誤圖樣矩陣中的非零元素應(yīng)為多個(gè)（數(shù)目和糾正錯(cuò)誤的位數(shù)相等）。糾正接收碼字的過程實(shí)際上是將接收碼字矩陣與相匹配的錯(cuò)誤圖樣矩陣求異或運(yùn)算的過程。

對于BCH（n，k）碼來說，每一個(gè)接收信號的伴隨式都是一個(gè)r=n-k位的矢量，若接收信號矢量定義為v，則伴隨式矢量為

其中：H表示校驗(yàn)矩陣。校驗(yàn)矩陣可以由生成矩陣得到[5]，若生成矩陣可以寫成

則校驗(yàn)矩陣可以寫成

兩者之間的關(guān)系為

伴隨式矢量s的性質(zhì)為：當(dāng)v是一個(gè)有效的碼字時(shí)，生成的伴隨式矢量s為零，伴隨式為零意味著接收的序列對應(yīng)的多項(xiàng)式能夠被生成多項(xiàng)式整除。因此，伴隨式為零不能保證沒有錯(cuò)誤的出現(xiàn)，接收的序列可能是另外一個(gè)有效的碼字。假設(shè)錯(cuò)誤圖樣為e，則接收矢量可以表示為：v=c+e，則伴隨式和錯(cuò)誤圖樣的關(guān)系為

從式（15）可以看出，只要知道錯(cuò)誤圖樣和伴隨式的對應(yīng)關(guān)系，就可以根據(jù)接收信號矢量生成的伴隨式求出錯(cuò)誤的位置并且進(jìn)行糾正。對于BCH（63，56）碼來說，其糾錯(cuò)能力為1 bit，因此，只要求出每一位出錯(cuò)時(shí)對應(yīng)的錯(cuò)誤圖樣，并且根據(jù)所有可能的錯(cuò)誤圖樣得到所有可能的伴隨式，就可以根據(jù)接收信號矢量的伴隨式得到發(fā)生錯(cuò)誤的位置并且進(jìn)行糾正。圖1是BCH（63，56）碼的譯碼器原理框圖[4,12]。

按照圖1，BCH（63，56）碼的譯碼步驟可以概括為：

1）利用伴隨式計(jì)算電路計(jì)算[6-7]接收信號序列的伴隨式；

2）因?yàn)锽CH（63，56）碼只能糾正1 bit錯(cuò)誤，生成所有發(fā)生1 bit錯(cuò)誤的錯(cuò)誤圖樣。由所有錯(cuò)誤圖樣生成所有可能的伴隨式；

3）將接收信號序列生成的伴隨式與所有錯(cuò)誤圖樣對應(yīng)的伴隨式進(jìn)行比對，發(fā)現(xiàn)錯(cuò)誤的位置并且對錯(cuò)誤進(jìn)行糾正。

圖1 BCH（63，56）譯碼器原理框圖Fig.1 Flowchart of decoding of BCH（63，56）

2 BCH碼性能估算

本節(jié)對BCH（63，56）的編碼性能進(jìn)行估算。因?yàn)锽CH（63，56）碼是糾錯(cuò)碼，其可以糾正編碼后數(shù)據(jù)在信道傳輸?shù)倪^程中發(fā)生的1 bit錯(cuò)誤。因此，在相同的Eb/N0水平下，經(jīng)過BCH（63，56）編碼后再傳輸?shù)姆桨竸荼乇戎苯觽鬏斢杏脭?shù)據(jù)的方案得到的誤碼率小。為精確計(jì)算誤碼率，需要首先知道在給定Eb/N0條件下每一幀發(fā)生不同數(shù)量比特錯(cuò)誤的概率。這里主要考慮如下4種錯(cuò)誤類型：沒有錯(cuò)誤、有1 bit錯(cuò)誤、有2 bit錯(cuò)誤以及有3 bit及以上錯(cuò)誤。設(shè)其發(fā)生的概率分別為P(0)、P(1)、P(2)及P(3)。

以Eb/N0= 6.8 dB為例，未編碼的BPSK信號對應(yīng)的誤碼率為PBPSK= 1×10-3，則可以計(jì)算P(0)、P(1)、P(2)及P(3)為

其中：N為總的幀數(shù)目。因?yàn)榘l(fā)生3 bit以上錯(cuò)誤的幀較少，所以錯(cuò)誤3 bit及以上的幀均按照錯(cuò)誤3 bit來計(jì)算。

若進(jìn)行BCH（63，56）編碼，則譯碼后系統(tǒng)的誤碼率為

因?yàn)锽CH（63，56）碼可以糾正1 bit的錯(cuò)誤，所以不再計(jì)算錯(cuò)誤1 bit導(dǎo)致的誤碼率。按照上面的方法，對BCH（63，56）碼的誤碼率性能進(jìn)行估算，結(jié)果如表1所示。

表1 理論計(jì)算得到的采用BCH編碼的系統(tǒng)的誤碼率Table 1 Error rate of BCH coded system by theoretical calculation

表1中給出的結(jié)果是用概率方法估計(jì)的BCH（63，56）碼在不同的Eb/N0水平下，誤碼率的理論計(jì)算結(jié)果。從前面的計(jì)算過程中可以看出，BCH（63，56）碼對于誤率的減小主要是因?yàn)槠淇梢詫π诺纻鬏斶^程中發(fā)生的1 bit錯(cuò)誤進(jìn)行糾正。從而在相同的Eb/N0水平下，比未經(jīng)過BCH（63，56）碼編碼的方案在誤碼率上有所減小。為了驗(yàn)證理論計(jì)算的正確性，在第3節(jié)中，將會(huì)利用MATLAB軟件實(shí)際仿真得到BCH（63，56）碼的性能。同時(shí)為了直觀比較經(jīng)過BCH（63，56）碼編碼后的方案和未經(jīng)編碼方案的誤碼率，將會(huì)在同一坐標(biāo)尺度下進(jìn)行比較。

3 BCH（63，56）碼性能仿真

本節(jié)用MATLAB軟件對BCH（63，56）碼的編譯碼過程進(jìn)行蒙特卡洛仿真，以得到在不同的Eb/N0條件下BCH（63，56）碼的誤碼率性能。仿真程序的流程圖如圖2所示。

如圖2所示，對BCH（63，56）碼仿真的步驟[13-14]主要為：首先在MATLAB中產(chǎn)生隨機(jī)信源，即要發(fā)送的有用碼字信息。然后根據(jù)第1節(jié)介紹的編碼方法，把每56位信息碼字在生成多項(xiàng)式已知的條件下映射成為63位碼字。仿真中，采用的調(diào)制方式為二進(jìn)制相移鍵控（Binary Phase Shift Keying，BPSK）。生成的碼字經(jīng)過BPSK調(diào)制之后成為基帶調(diào)制信號，根據(jù)不同的Eb/N0可對基帶調(diào)制信號添加不同大小的高斯白噪聲，從而模擬信號在信道中傳輸?shù)倪^程[15]。對于接收端，首先對經(jīng)過信道傳輸?shù)男盘栠M(jìn)行基帶BPSK解調(diào)，恢復(fù)出63位碼字。隨后，利用伴隨式計(jì)算該63位碼字的伴隨式并與本地存儲(chǔ)的錯(cuò)誤圖樣進(jìn)行對比，從而可糾正信道傳輸過程中引起的錯(cuò)誤。

圖2 計(jì)算機(jī)仿真流程圖Fig.2 Flowchart of computer simulation

根據(jù)仿真框圖，通過在MATLAB中進(jìn)行仿真，可以得到BCH(63,56)碼在不同Eb/N0下的性能。

圖3為仿真得到的BCH（63，56）碼的誤碼率和誤幀率，同時(shí)，也畫出了理論計(jì)算得到的BCH（63，56）碼的性能以及BPSK未編碼系統(tǒng)的誤碼率性能。

從圖3中可以看出，當(dāng)信噪比較小時(shí)，經(jīng)過BCH（63，56）碼編碼與未編碼系統(tǒng)的誤碼率性能相仿，而比理論計(jì)算部分得到的誤碼率性能要差。這是因?yàn)椋诘托旁氡鹊那闆r下，消息在傳輸過程中可能會(huì)發(fā)生多位的錯(cuò)誤，而BCH（63，56）碼只能糾正1 bit的錯(cuò)誤，并且只能檢測出2 bit的錯(cuò)誤。如果接收端發(fā)生了2 bit錯(cuò)誤，則接收端能夠檢測出該碼字發(fā)生了錯(cuò)誤，但是不能對其進(jìn)行糾正。當(dāng)接收端發(fā)生了3 bit或者大于3 bit的錯(cuò)誤時(shí)，接收端不能檢測出該碼字發(fā)生的3 bit錯(cuò)誤，更嚴(yán)重的是，因?yàn)槎啾忍劐e(cuò)誤圖樣對應(yīng)的所有可能的伴隨式，與1 bit錯(cuò)誤圖樣對應(yīng)的伴隨式有交集，因此此時(shí)接收端可能會(huì)對接收序列按照發(fā)生了1 bit錯(cuò)誤進(jìn)行“糾錯(cuò)”，當(dāng)然這個(gè)“糾錯(cuò)”的過程勢必會(huì)導(dǎo)致接收序列在錯(cuò)誤的基礎(chǔ)上再多錯(cuò)一位。而對誤碼率進(jìn)行理論計(jì)算的過程中，并沒有考慮BCH（63，56）幀錯(cuò)3 bit以上情況導(dǎo)致的負(fù)作用。從而導(dǎo)致在信噪比很低的情況下仿真誤碼率劣于理論計(jì)算的誤碼率性能。

圖3 BCH（63，56）誤碼率性能和未編碼系統(tǒng)性能比較Fig.3 The comparison of BCH（63，56）and un-coded system

當(dāng)信噪比大于4 dB時(shí)，BCH（63，56）碼的誤碼率性能開始明顯好于未編碼系統(tǒng)的誤碼率性能，并且隨著信噪比增大兩者之間的差距越來越大。這是因?yàn)樵谛旁氡容^大的情況下，每一幀接收信息中發(fā)生錯(cuò)誤的比特?cái)?shù)都在1 bit左右，當(dāng)發(fā)生1 bit的錯(cuò)誤時(shí)，BCH（63，56）碼能夠發(fā)揮出其糾錯(cuò)的功能。對于所有發(fā)生不同比特錯(cuò)誤的幀來說，發(fā)生1 bit錯(cuò)誤的幀在所有發(fā)生錯(cuò)誤的幀中所占的比例越來越大，因此兩者之間誤碼率性能的差距越來越大。因此，當(dāng)信噪比逐步提高時(shí)，BCH（63，56）碼的誤碼率性能的優(yōu)越性逐步就顯現(xiàn)出來了。

同時(shí)，在高信噪比的情況下，仿真性能與理論計(jì)算的性能相仿，這是因?yàn)榇藭r(shí)在系統(tǒng)中出現(xiàn)3 bit錯(cuò)誤的幀的概率很小。從圖3還可以看出，在1×10-5的誤碼率條件下，BCH（63，56）的編碼增益約為2.1 dB。

4 結(jié) 論

BCH（63，56）碼可以糾正1 bit錯(cuò)誤并且檢測出2 bit錯(cuò)誤，該種編碼方式適合于用在深空通信遙控鏈路中。通過理論分析和計(jì)算機(jī)仿真，表明在1×10-5的誤碼率條件下，BCH（63，56）的編碼增益約為2.1 dB。上述結(jié)論可以為深空通信系統(tǒng)的工程人員進(jìn)行系統(tǒng)設(shè)計(jì)時(shí)提供參考。

[1]CCSDS.TC synchronization and channel coding[Z].[S.l.]：CCSDS，2010.

[2]CCSDS.TC synchronization and channel coding - summary of concept and rationale[Z].[S.l.]：CCSDS，2006.

[3]Arunkumar S，Kalaivani T.FPGA implementation of CCSDS BCH（63，56）for satellite communication[C]//IEEE International Conference on Electronics Design.[S.l.]：IEEE，2013.

[4]賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.He H Y.Principle and application of LDPC[M].Beijing:Posts ＆Telecom Press,2009.

[5]王育民，李暉.信息論與編碼理論[M].北京：高等教育出版社，2013.Wang Y M,Li H.The theory of information and coding[M].Beijing:Higher Education Press,2013.

[6]Lonescu L M，Anton C，Tutanescu I，et al.Hardware implementation of BCH Error-correcting codes on a FPGA[J].International Journal of Intelligent Computing Research（IJICR），2010，1（3）：148-153.

[7]Kusumawardani S S，Sutopo B.Designing 1 bit error correcting circuit on FPGA using BCH codes[C]//Proceedings of International Conference on Electrical，Communication，and Information，CECI.[S.l.]：CECI，2001.

[8]王新梅，肖國鎮(zhèn).糾錯(cuò)碼--原理與方法[M].西安：西安電子科技大學(xué)出版社,2001.Wang X M,Xiao G Z.Principles and methods of error correcting codes[M].Xi’an: Xidian University Press,2001.

[9]楊曉琳.循環(huán)碼理論及其譯碼算法研究--設(shè)計(jì)距離為11的二元BCH碼構(gòu)造及其B-M迭代譯碼算法實(shí)現(xiàn)[D].成都：成都理工大學(xué),2008.Yang X L.Research on cyclic codes and its decoding algorithmsconstruction of binary BCH codes with design distance 11 and complementation of its B-M iterative decoding algorithm[D].Chengdu:Chengdu University of Technology,2008.

[10]王永波.BCH譯碼算法的研究及硬件實(shí)現(xiàn)[D].廈門：廈門大學(xué),2011.Wang Y B.BCH decoding algorithm and hardware implementation[D].Xiamen: Xiamen University,2011.

[11]江建國.BCH編譯碼器的設(shè)計(jì)及驗(yàn)證[D].上海：上海交通大學(xué),2010.Jiang J G.Design and verification of BCH encoder and decoder[D].Shanghai: Shanghai Jiao Tong University,2010.

[12]張宗橙.糾錯(cuò)碼原理和應(yīng)用[M].電子工業(yè)出版社,2003.Zhang Z C.Principle and application of error correcting codes[M].Publishing House of Electronics Industry,2003.

[13]李志國,張偉功.BCH碼迭代譯碼算法及軟件實(shí)現(xiàn)方法[J].計(jì)算機(jī)技術(shù)及發(fā)展,2007,17(4):171-174.Li Z G,Zhang W G.Binary BCH code BM decoding Algorithm and soft ware realization[J].Computer Technology and Development,2007,17(4):171-174.

[14]王立寧.MATLAB與通信仿真[M].人民郵電出版社,2000.Wang L N.MATLAB and communication simulation[M].Posts ＆Telecom Press,2000.

[15]樊昌信,曹麗娜.通信原理[M].北京：國防工業(yè)出版社,2012.Fan C X,Cao L N.Principles of communications[M].Beijing：National Defense Industry Press，2012.

Performance Analysis and Simulation of BCH（63，56）

ZHAN Yafeng，XIE Dezhun
（Space Center of Tsinghua University，Beijing 100084，China）

BCH（63，56）is widely used in uplink channel of deep space communication for low-complexity implementing，which can check 2 bits error and correct 1 bit error.The performance of BCH（63，56）is studied by theoretical analysis and computer simulation in this paper.On the basis of introducing the basic principle of BCH（63，56），the performance of bits error rate is calculated and the Monte Carlo simulation is carried out.The results show that the coding gain of BCH（63，56）can be up to 2.1 dB when the bit error rate is 1e-5.

BCH（63，56）；deep space communication；Monte Carlo simulation

V11

A

2095-7777（2017）04-0385-05

10.15982/j.issn.2095-7777.2017.04.012

詹亞鋒，解得準(zhǔn).BCH（63，56）性能分析及仿真[J].深空探測學(xué)報(bào)，2017，4（4）：385-389.

Reference format：Zhan Y F，Xie D Z.Performance analysis and simulation of BCH（63，56）[J].Journal of Deep Space Exploration，2017，4（4）：385-389.

2016-11-03

2017-07-09

國家自然科學(xué)基金資助項(xiàng)目（61671263，61271265）；清華大學(xué)自主科研項(xiàng)目（20161080057，20131089244）

詹亞鋒（1976- ），男，副研究員，博士生導(dǎo)師，主要研究方向：深空通信、通信信號處理。

通信地址：清華大學(xué)中央主樓12層（100084）

電話：（010）62773218

E-mail：zhanyf@tsinghua.edu.cn

[責(zé)任編輯：楊曉燕，英文審校：朱恬]