在信息論中，BCH codes?是指?Bose–Chaudhuri–Hocquenghem codes，可以用來糾錯。BCH碼利用了多項式一些很好的性質(zhì)。本文將從0開始，用詳細(xì)的例子解釋二進(jìn)制域中的BCH碼。

二進(jìn)制域與多項式

首先考慮二進(jìn)制域，即所有每個位的取值只能是0或1。我們可以嘗試把二進(jìn)制數(shù)表示為多項式，二進(jìn)制數(shù)中的從左往右第j位，是多項式x^j的系數(shù)。例如11011，可以表示成為?。

二進(jìn)制域的四則運算與我們常見的十進(jìn)制差不多，但由于在二進(jìn)制1 + 1 = 2 = 0，所以我們每次計算后相當(dāng)于模上2。例如計算11*11，在多項式表示就是??。這兒的x的系數(shù)2在二進(jìn)制中等于0。另外很重要的概念就是二進(jìn)制域中，加等于減，例如??相當(dāng)于??。

尋找新的編碼方式

我們先回顧簡單的奇偶校驗碼和hamming碼。簡單的奇偶校驗碼只能檢查出錯誤而不知道具體是哪里出錯，而hamming碼只能糾正一位錯誤。因此我們想能不能有一種方法可以糾正多位錯誤呢？

此時，多項式的威力就發(fā)揮了出來。假如我們的真正的消息是m(x)，然后乘上一個編碼多項式p(x)，得到m(x)p(x)再將其發(fā)送過去。發(fā)送過程中會會受到很多干擾，于是多項式被加上錯誤多項式e(x)，而接收者接收者的消息為c(x)，就有

接收者怎么知道消息有沒錯呢？接收者事先就會和發(fā)送者商量好p(x)，然后就很簡單，只要讓c(x)除以p(x)，如果余項是0，即沒有e(x)，沒有受到干擾，那么商就是m(x)，就是正確的消息。如果余項不是零，我們的商就變成了m(x) + e(x)/p(x)，無法將真正的消息分離出來。

上述方法有個前提，在m(x) + e(x)/p(x)，p(x)必須是不可約的本原多項式(primitive polynomials)，這樣才能讓e(x)不被除盡，我們才能意識到有干擾的存在。至于如何尋找素多項式，將在之后說明。

糾單個錯的例子

下面來看個例子。例如我們要發(fā)送的消息m(x)是1001，而編碼多項式p(x)是1101，于是我們要發(fā)送出去的消息就是1100101。假如接收者也接收到了這個消息，用p(x)除后余項是0，沒有錯誤存在，商是1001，就是發(fā)送者發(fā)送的消息，自然皆大歡喜。

但如果發(fā)送過程中，有一個位被某種不可抗拒的神秘力量改變了，變成了1100111，接收者同樣用p(x)去除，得到了余項1110000，這下不好了，接收者知道出錯了。但現(xiàn)在怎么去找出錯誤多項式e(x)呢？

我們知道，這個余項1110000，就是e(x)/p(x)的余項。為了找出e(x)，我們可以反過來推。于是制作一張表格

表格右側(cè)就是如果出現(xiàn)一位錯誤，r(x)/p(x)后，e(x)/p(x)的余項。通過尋找余項結(jié)果，我們可以快速定位究竟是哪里出錯了。當(dāng)然如果e(x)為0，那么e(x)/p(x)的余項也為0。

上面這個方法之所以能奏效，對于所有的可能的錯誤。是因為右邊的每一個余項都不相同，我們才不至于混淆。如果我們把p(x)換成10001會發(fā)生什么呢？這里10001不是本原多項式，因為10001可以分解成101乘101。

我們可以看到，右側(cè)重復(fù)了！假如我們得到余項1000000，我們無法知道e(x)究竟是第一行的1000000還是第五行的0000100。

而本原多項式就好在，在所有錯誤余項e(x)出現(xiàn)前前，e(x)/p(x)的余項不會重復(fù)。之后將開始重復(fù)，這就是被稱為循環(huán)（cyclic）碼的原因。

尋找本原多項式

本原多項式是個神器，但哪些是本原多項式呢？首先有一些原則：

• r次多項式，最高次項x^r的系數(shù)必須是1。
• 多項式如果不包含常數(shù)項1，就會被x整除。
• 多項式項數(shù)不能是偶數(shù)的，比如??有四項，很容易將其分解為?。
• 每一項的次數(shù)也不能都是偶數(shù)，否則將每一項次數(shù)減半就能得到因子。例如??。

于是我們很容易找到：

按照上述方法還可以繼續(xù)尋找更多的本原多項式。次數(shù)越高數(shù)量越多。

BCH碼

但如果想要糾正多個錯誤呢？此時僅一個編碼多項式p(x)就不夠了，我們還需要更多的編碼多項式來讓我們能找出多個錯誤。這時就輪到BCH碼出場了，其編碼多項式標(biāo)準(zhǔn)形式是：

其中p(x)是本原多項式，而??都是可以被p(x)除余0的多項式。即

如果我們要設(shè)計一個可以糾正兩個錯誤的編碼多項式，就讓??。要設(shè)計一個可以糾正三個錯誤的編碼多項式，就讓??。現(xiàn)在我們先說如何尋找??。

例如??。我們發(fā)現(xiàn)??，所以??。我們用??代替??，就得到??。

糾正多個錯誤的例子

注：以下計算均是模上了??的在二進(jìn)制域內(nèi)的計算。

還是和原來一樣，假如我們要發(fā)生的消息m(x)是11010，選擇的本原多項式是??，那么??，??。編碼多項式就是???，表示成二進(jìn)制是11101100101，再乘上消息m(x)就是100001110110010，就是我們發(fā)送的出去的。

但現(xiàn)在接收者受到的r(x)卻是 101000110110010。然后接收者開始計算：

前兩項余項不為0，而第三項為0說明接到的只有兩處錯誤。但如何把它們的位置找出來？我們就要用到錯誤定位多項式（ error locator polynomial ）了。即：

不過這時??可以認(rèn)為是無窮小，這樣??就是0。

如果我們能找到這個函數(shù)的兩個根，我們也就找到了e1和e2。為了解決這個問題，我們得先定義兩個函數(shù)。

兩個函數(shù)

初等對稱函數(shù)(Elementary symmetric polynomial)s，即滿足下列的形式的多項式

另定義冪和對稱函數(shù)（ power sum symmetric functions）t，

在我們的例子中，可能有三個錯誤，于是可表示成：

重點來了。我們有s與t的關(guān)系：

計算

此時上面的錯誤定位不等式就可以用s函數(shù)來描述：

我們知道一些t的結(jié)果：

再用s和t的關(guān)系計算

即第一個錯誤在第三個位，第二個錯誤在第六個位，沒有第三個錯誤。于是將 101000110110010 修改回來得 100001110110010 ，再除Q(x)就得到了真正的消息m(x) = 11010 。

結(jié)語

BCH碼被用于衛(wèi)星通信，固態(tài)硬盤等領(lǐng)域。

例如BCH(31,16)碼，每組有31個位，其中有效的信息位為16個，漢明距離為7，可以糾正3個位的錯誤。此時應(yīng)該使用的本原多項式的最高項次數(shù)應(yīng)該是5，因為??。

有時候我們使用可以用BCH糾正k個錯誤的碼，但如果錯誤不止k個，我們就無法恢復(fù)正確的消息。但我們?nèi)匀豢梢曰謴?fù)一些可能是正確的消息，再逐一排查。

延慶川北小區(qū)45號孫老師 東屯 收賣廢品破爛垃圾炒股

whaosoft aiot?http://143ai.com

額很多圖片沒有傳上出哦 見諒

總結(jié)

以上是生活随笔為你收集整理的BCH码(BCH code)详细分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。