BCH碼的定義

BCH碼是由Bose、Chandhari 和 Hocquenhem 分別獨立提出的一種能夠糾正多個隨機錯誤的循環碼。
BCH 碼的定義：給定任一有限域 GF(q)及其擴域 GF(q^m)（其中 q 為素數或素數冪），m 為某一正整數，若碼元取自 GF(q) 循環碼的生成多項式 g(x) 的根集合 R 中有 σ-1 個連續根 α^m0， α^m0+1， α^m0+σ-2，則該循環碼稱為 q 進制 BCH 碼。其中 α∈GF(q^m) 是域中的 n 級元素，α^m0+i∈GF(q^m)(0 ≤ i≤ σ-2)，m0 是任意整數，通常取值為 0 或 1，當 m0=1 時生成的 BCH 碼為狹義 BCH 碼。如果在生成多項式 g(x) 的根中有 GF(q^m) 的本原元，則 BCH 碼的碼長 n=q^m-1，相應的 BCH 稱為本原 BCH 碼。
設 m_i(x) 和 e_i 分別是 α^m0+i(i = 1,2,…,σ-2) 元素的最小多項式和級，則 BCH 碼的生成多項式和碼長分別為：

BCH碼的性質

對于 BCH 碼，有如下性質和結論。
①（BCH 限）BCH 碼的最小距離 d 至少為 σ；若 BCH 碼的生成多項式 g(x) 的根集合為 R = {α^m0， α^m0+c，α^m0+(σ-2)c} 且 (n,c) = 1，則其最小距離 d ≥ σ。
②（HT 限）如果 BCH 碼的生成多項式 g(x) 的根集合 R 中有 s 組 σ-1 個 α 的連續元素（α∈GF(q^m) 是 n 級元素），即 R = {α^m0+σi+j ,i = 0,1,…,s-1; j = 0,1,…,σ-2} 且 (n,α) = 1 ，則 BCH 碼的最小距離 d ≥ σ + s - 1。類似的，（GHT 限）如果 BCH 碼的生成多項式 g(x) 的根集合為 R= {α^m0+σ1i+σ2j ,i = 0,1,…,s-1; j = 0,1,…,σ-2} 且 (n,σ1) < σ，σ ≥ 2 ，則 BCH 碼的最小距離 d ≥ σ + s - 1。
③如果二進制本原 BCH 碼的碼長 n = 2^m-1 ，設計距離為 σ = 2t+1 ，則如果滿足 ：

則，當 t --> 0 時 BCH 碼的實際距離等于設計距離。
④若二進制 BCH 碼的碼長 n = ab 且設計距離為 σ = a ，則碼的實際距離就為 a 。
⑤如果 GF(q) 上 BCH 碼的碼長為 n = q^m-1 ，設計距離 σ = q^h-1 ，則碼的實際距離為 σ 。
⑥ GF(q) 上設計距離為 σ 的本原 BCH 碼的實際最小距離 d ≤ qσ +q-2 。
在我們平時的編碼中，主要討論的是 q = 2 的二進制狹義 BCH 碼。

BCH的構造

對于二進制 BCH 碼，其碼元取自 GF(2) 。根據 BCH 碼的定義，若設 m₀=1， σ=2t+1，α 為 GF(2^m) 上的本原元【0、1】，若碼以 α，α²，…，α^2t 為根，每個根對應的最小多項式為 m_i(x)，i = 1，2，…，2t，則二進制 BCH 碼的生成多項式為：

該 BCH 碼能夠糾正 t 個錯誤。
在特征為 2 的 GF(2^m) 上 （αⁱ）² 和 αⁱ 的最小多項式相同，因此 BCH 碼以 α ，α³，…，α^2t-1 為根，其生成多項式可以寫成：

相應的碼長為：

其中，e_i(i = 1，3，…，2t-1) 為 αⁱ(i = 1，3，…，2t-1) 的級。
根據生成多項式以及循環碼（https://blog.csdn.net/weixin_45115771/article/details/125571083?spm=1001.2014.3001.5501）的循環移位特性可以構造 BCH 碼的生成矩陣 G。若設 C(x) = q(x)g(x) 是 BCH 碼的任一碼字，則 α ，α³，…，α^2t-1 為碼多項式 C(x) 的根，即若碼多項式為：

則有：

根據 CH^T = 0，可知 BCH 碼的校驗矩陣 H 為：

對于二進制 BCH 碼，有如下結論：
對于任意正整數 m 和 t，一定存在一個二進制 BCH 碼，以 α ，α³，…，α^2t-1 為根，碼長為 n = 2^m-1 或 2^m-1 的因子，能夠糾正 t 個錯誤，碼中校驗元的個數為 mt 個（生成多項式 g(x) 的次數）。

例：對于定義在 GF(2⁴) 上的本原 BCH 碼，m = 4，α 為 GF(2⁴) 上的本原元，GF(2⁴) 上的本原多項式 p(x) = x⁴+x+1，則針對不同的 t 值，可以構造不同碼參數的 BCH 碼（假設碼長 n = 2^m-1 = 15）。
①如果 t = 1，則構造的 BCH 碼以 α 為根，同時 α²，α⁴，α⁸ 也是該 BCH 碼的根，α 的最小多項式就是本原多項式，所以生成多項式為 g(x) = x⁴+x+1，校驗元的個數為 mt = 4，得到的是糾錯能力 t=1 的（15，11，4）BCH 碼。
參考下表：

冪次表示二進制表示 十進制表示

0	0000	0
1	0001	1
α1	0010	2
α2	0011	3
α3	0100	4
α4=α+1	0101	5
α5=α2+α	0110	6
α6 =α3+α2	0111	7
α7= α3+α+1	1000	8
α8 = α2+1	1001	9
α9=α3+α	1010	10
α10=α2+α+1	1011	11
α11=α3+α2+α	1100	12
α12 =α3+α2+α+1	1101	13
α13=α3+α2+1	1110	14
α14 =α3+1	1111	15

根據表中 GF(2⁴) 的元素列表及 BCH 碼校驗矩陣的形式，可以寫出該 （15，11，4）BCH 碼的檢驗矩陣 H 為：
![在這里插入圖片描述](https://img-blog.csdnimg.cn/83f409fd6bab41a8afa97db4aec53f5d.png
根據校驗矩陣 H 和生成矩陣 G 的對偶關系或者根據生成多項式 g(x) 及循環碼生成多項式矩陣的構造方法可以寫出該 BCH 碼的生成矩陣 G。

②如果 t = 2，則構造的 BCH 碼以 α ，α³ 為根，α 的最小多項式為 m₁(x) = x⁴+1，α³ 的最小多項式為 m₃(x) = x⁴+ x³+ x²+x+1，所以生成多項式為：g(x) = m₁(x) m₃(x) = x⁸+ x⁷+ x⁶+x⁴+1，校驗元的個數為 mt = 8，得到的是糾錯能力 t = 2 的（15，7，5）BCH 碼。參考上表中 GF(2⁴) 的元素列表及 BCH 碼校驗矩陣的形式，可以寫出該 （15，7，5）BCH 碼的校驗矩陣 H 為：

根據校驗矩陣 H 和生成矩陣 G 的對偶關系或者根據生成多項式 g(x) 及循環碼生成多項式矩陣的構造方法可以寫出該 BCH 碼的生成矩陣 G。
③如果 t = 3，則構造的 BCH 碼以α ，α³， α⁵ 為根，α 的最小多項式為 m₁(x) = x⁴+1，α³ 的最小多項式為 m₃(x) = x⁴+ x³+ x²+x+1，α⁵ 的最小多項式為 m₅(x) = x²+x+1，所以生成多項式為：g(x) = m₁(x) m₃(x)m₅(x) = x¹⁰+ x⁸+ x⁵+x⁴+x²+x+1，校驗元的個數為 mt = 12，得到的是糾錯能力 t = 3 的（15，5，7）BCH 碼。參考上表中 GF(2⁴) 的元素列表及 BCH 碼校驗矩陣的形式，可以寫出該 （15，5，7）BCH 碼的校驗矩陣 H 為：

④如果 t = 4，則構造的 BCH 碼以α ，α³， α⁵ ， α⁷為根，α 的最小多項式為 m₁(x) = x⁴+1，α³ 的最小多項式為 m₃(x) = x⁴+ x³+ x²+x+1，α⁵ 的最小多項式為 m₅(x) = x²+x+1，α⁷ 的最小多項式為 m₇(x) = x⁴+ x³+1，所以生成多項式為：g(x) = m₁(x) m₃(x)m₅(x)m₇(x) = x¹⁴+ x¹³+x¹²+x¹¹+x¹⁰+x⁹+ x⁸+x⁷+x⁶+ x⁵+x⁴+x³+ x²+x+1，得到的是（15，1，15）BCH 碼，也即重復碼。該碼的設計距離為 σ = 2t+1 = 9，可以計算該碼的實際最小距離 d = 15。在此情況下，設計距離不等于實際最小距離，碼設計太過度了，該碼實際可糾 (d-1)/2 = 7個隨機錯誤。
與線性分組碼和循環碼類似，也可以通過增加全校驗位實現擴展 BCH 碼。

BCH碼編碼

BCH 碼編碼的關鍵是生成多項式的選取，或者說生成矩陣 G 和校驗矩陣 H 的構造。對于定義在 GF(q^m) 上分組長度 n = q^m-1、可糾正 t 個錯誤的 BCH 碼，編碼步驟如下：
①選取一個次數為 m 的既約多項式并構造 GF(q^m) 。
②求 αⁱ，i = 1，3，…，2t-1的最小多項式 m_i(x)。
③構造可糾 t 個錯誤的碼生成多項式 g(x) = m₁(x) m₃(x)… m_2t-1(x)。
④按照循環碼的編碼方法和編碼電路及逆行編碼（所有加法運算和乘法運算都在 GF(q^m)。
在MATLAB中提供了 BCH 碼的編碼和譯碼相關函數和 Simulink 仿真模塊，具體說明如下：
—bchgenpoly—：該函數根據碼長 n 和信息組長度 k 計算狹義 BCH 碼的生成多項式。語法結構為：

genpoly = bchgenpoly(n,k) genpoly = bchgenpoly(n,k,prim_poly) [genpoly,t] = bchgenpoly(……)

其中，輸入參數 n 為碼長，k 為信息組長度，碼長 n 必須等于 2^m-1，3 ≤ m ≤ 16，輸入 prim_poly 為按冪次下降順序排列的整數，表示本原多項式的系數。輸出 genpoly 是 GF(2) 上按冪次下降順序排列的生成多項式系數，輸出 t 表示該碼的糾錯能力。
例：生成糾錯能力為 3 的（15，5）BCH 碼的生成多項式。

m = 4; n = 2^m-1; % 碼長 k = 5; % 信息組長度 [genpoly,t] = bchgenpoly(n,k) % 計算生成多項式和糾錯能力 disp(genpoly); % 顯示 genpoly disp(t); % 顯示 t

輸出結果：

genpoly:1×11 gf 數組 - 屬性:x: [1 0 1 0 0 1 1 0 1 1 1]m: 1prim_poly: 3 t:3

有了生成多項式，就可以進行 BCH 碼的編碼和譯碼了。

—bchnumerr—：該函數計算給定參數條件下 BCH 碼的可糾正錯誤數，語法結構為：

T = bchnumerr(N) T = bchnumerr(N,K)

語法結構 1 表示在給定碼長 N 的條件下返回所有可能的信息組長度 K 組成不同 (N,K) BCH 碼時的可糾正錯誤數 T，其返回值 T 為一個包含 3 列元素的矩陣，第 1 列為碼長 N ，第 2 列為可能的信息組長度 K，第３列為糾錯能力T。
例：當N＝15時，輸出結果Ｔ為：

T = bchnumerr(15)； T = 15 11 115 7 215 5 3

也即對于N＝15的情況，可以生成信息組長度K分別為 11 , 7 和 5 的 BCH 碼，其糾錯能力分別為 1、2 和 3。
語法結構 2 要求輸入信息組長度 K，函數執行后返回 (N,K) BCH 碼的糾錯能力 T。

—bchenc—：該函數為 BCH 碼的編碼函數，語法結構為：

code = bchenc(msg,n,k) code = bchenc(……,paritypos)

該函數使用狹義（n，k）BCH 碼的生成多項式對輸入信息組 msg 進行 BCH 碼編碼。其中信息組 msg 定義在 GF(2) 上，可以是矩陣形式，每行包含 k 個元素作為一個信息組。最左邊為最高位符號。在輸出的 GF(2) 域上編碼碼字 code 中檢驗符號位于每個碼字的右端。
語法結構 2 中參數 paritypos 用于指定檢驗符號的位置，值可以是 “end” 或 “beginning”，分別表示校驗符號位于輸出碼字信息組的開始部分和結束部分，默認值為 “end”。
例：假設對（15，5）BCH 碼進行編碼，輸入為：

code = bchenc(msg,n,k) code = bchenc(……,paritypos)

若輸入為：

msg = gf([1 0 1 0 1; 0 1 0 1 0 ]); code = bchenc(msg,15,5);

則輸出為：

code： 2×15 gf 數組 - 屬性:x: [2×15 uint32][1,0,1,0,1,1,0,0,1,0,0,0,1,1,1;0,1,0,1,0,0,1,1,0,1,1,1,0,0,0]m: 1prim_poly: 3

BCH碼譯碼

一、伴隨式譯碼
BCH 碼的伴隨式譯碼分為如下3個步驟：
①根據接收碼多項式 R(x) ，利用公式：

計算伴隨式 S(x)。
②根據伴隨式 S(x)，在碼字糾錯能力范圍內得到錯誤圖樣 E(x) 的估計 E^(x)。
③估計發送碼字 C^(x) = R(X)+E^(x)。

二、迭代譯碼
BCH 碼伴隨式譯碼中最復雜的部分是錯誤位置多項式系數的計算和根的求解。Berlekamp 提出了一種通過迭代方式求解錯誤位置多項式根的方法（BM 算法），結合 Chien搜索電路，可以加快錯誤多項式的求解，簡化譯碼過程。
BCH 碼的迭代譯碼分為如下5個步驟：
①根據接收碼多項式 R(x)，利用公式：

計算伴隨式 S(x)。
②用 BM 算法求解錯誤位置多項式的系數。
③用 Chien 搜索法求錯誤位置多項式的根。
④計算錯誤值（對于二元碼，可以省略該步驟）。
⑤根據錯誤位置（和錯誤值）獲得錯誤圖樣 E(x) 的估計 E^(x)并譯碼， C^(x) = R(X)+E^(x)。

—bchenc—：該函數為 BCH 碼的譯碼函數，使用BM算法進行 BCH 碼的譯碼。語法結構為：

decoded = bchdec(code,n,k) decoded = bchdec(……,paritypos) [decoded,cnumerr] = bchdec(……) [decoded,cnumerr,ccode] = bchdec(……)

其中，輸入參數 n 和 k 分別表示碼長和信息組長度，code 為定義在 GF(2) 上的接受碼符號序列，paritypos 用于指定校驗符號的位置（與 bchenc 中相對應）。
輸出參數中 decoded 表示譯碼輸出碼字，定義在有限域上，可以是矩陣形式，每一行對應輸入 code 中一行碼字的譯碼輸出。如果 bchdec 函數檢測到在 code 的行中出現超過其糾錯能力 t 的錯誤（錯誤數大于 t），則譯碼失敗，這種情況下 bchdec 函數因輸出輸入 code 中每一行的前 k 個符號（默認 paritypos = “end”）。輸出參數中 cnumerr 返回的是列矢量，其中每個元素是對輸入 code 的每行譯碼時糾正的錯誤說，如果某行譯碼失敗，則 cnumerr 列矢量中相應的元素值為 -1。輸出參數中 ccode 返回的是糾正了 code 中的錯誤之后的碼向量（或矩陣），其格式與輸入 code 相同。如果譯碼失敗，則直接輸出 code 中相應的行。
例：對（15，5）BCH 碼進行編譯碼。

n = 15; k = 5; dat = randi([0,1],4,k); msg = gf(dat); code = bchenc(msg,n,k); decode = bchdec(code,n,k); % 檢查譯碼過程是否正確 chk = isequal(decode,msg);

在上述例子中，要求編碼函數 bchenc 和譯碼函數 bchdec 中參數 paritypos 的值必須相同，才能正確譯碼。

總結

以上是生活随笔為你收集整理的BCH编码与译码（MATLAB实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。