通信抗幹擾編碼—分組碼概述

目錄：

• 1 相關概念
• 2 線性分組碼
• • 2.1 監督矩陣
  • 2.2 生成矩陣
  • 2.3 校正子
• 3 交織碼
• 4 循環碼
• • 4.1 循環碼的表示
  • 4.2 循環碼的生成多項式和生成矩陣
  • 4.3 循環碼編碼
• 5 截短循環碼
• 6 BCH碼
• 7 RS碼

1 相關概念

• 分組碼結構

    分組碼包括資訊碼元和監督碼元，通常表示為(n,k)，n是總位數，k是資訊碼元的位數，那麼r=n-k就是監督碼元的個數。例如：(7,4)就代表長度為7，其中包括4個資訊位，3個監督位。

• 編碼效率η及編碼備援度E

  η = k n \frac{k}{n} nk​

  E = n − k k \frac{n-k}{k} kn−k​

• 碼重和碼距

    碼組中1的個數成為“碼重”，不同碼組之間對應位上碼元不同的位數稱為碼距。例如：碼組1：00110110，碼組2：10011011，碼組1的碼重為4，碼組2的碼重為5，二者碼距為5。對于某種編碼方式而言，各個碼組距離的最小值稱為最小碼距(dmin)，它直接決定着這種編碼方式的檢錯和糾錯能力。

2 線性分組碼

  線性分組碼就是資訊碼元和監督碼元之間呈現線性關系的分組碼。如果希望用r個監督位構造出r個監督關系式來訓示一位錯碼的n種位置，則要求

2 r − 1 ≥ n 2^r-1≥n 2r−1≥n

2.1 監督矩陣

  監督矩陣是由監督方程關系式構成，每一行都是一個監督方程，每一個監督方程都是碼組中其中一個監督碼元和某些資訊碼元之間滿足的關系式。例如 ( 7,4 ) 碼有三個監督碼元，那麼對應的就是三個監督方程，方程中出現的碼元對應矩陣元素為1，未出現的碼元對應矩陣元素為0。

  假設某 ( 7,4 ) 碼組A=[ a6 a5 a4 a3 a2 a1 a0 ]，其中a6 a5 a4 a3 為資訊碼元，a2 a1 a0為監督碼元，滿足以下關系：

{ a 6 ⊕ a 5 ⊕ a 4 ⊕ a 2 = 0 a 6 ⊕ a 5 ⊕ a 3 ⊕ a 1 = 0 a 6 ⊕ a 4 ⊕ a 3 ⊕ a 0 = 0 (2-1) \left\{\begin{matrix}a6⊕a5⊕a4⊕a2=0\\a6⊕a5⊕a3⊕a1=0\\a6⊕a4⊕a3⊕a0=0\end{matrix}\right. \tag{2-1} ⎩⎨⎧​a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0a6⊕a4⊕a3⊕a0=0​(2-1)

那麼根據監督方程關系式可得到如下行元素，進而構成監督矩陣H：

{ 1110100 1101010 1011001 \left\{\begin{matrix}1110100\\1101010\\1011001\end{matrix}\right. ⎩⎨⎧​111010011010101011001​

  将監督方程組看成監督矩陣H和碼組相乘，可滿足以下線性代數關系：

[ 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 ] ⋅ [ a 6 a 5 a 4 a 3 a 2 a 1 a 0 ] = [ 0 0 0 ] \left[ \begin{matrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{matrix} \right] · \left[ \begin{matrix} a_6\\ a_5\\ a_4\\ a_3\\ a_2\\ a_1\\ a_0\\ \end{matrix} \right]= \left[ \begin{matrix} 0\\ 0\\ 0\\ \end{matrix} \right] ⎣⎡​111​110​101​011​100​010​001​⎦⎤​⋅⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​a6​a5​a4​a3​a2​a1​a0​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎡​000​⎦⎤​

  可以簡記為

H ⋅ A T = 0 T A ⋅ H T = 0 (2-2) H·A^T=0^T\tag{2-2}\\ A·H^T=0 H⋅AT=0TA⋅HT=0(2-2)

2.2 生成矩陣

   式（2-1）可以表示為：

{ a 2 = a 6 ⊕ a 5 ⊕ a 4 a 1 = a 6 ⊕ a 5 ⊕ a 3 a 0 = a 6 ⊕ a 4 ⊕ a 3 (2-3) \left\{\begin{matrix} a2=a6⊕a5⊕a4\\ a1=a6⊕a5⊕a3\\ a0=a6⊕a4⊕a3 \end{matrix}\right. \tag{2-3} ⎩⎨⎧​a2=a6⊕a5⊕a4a1=a6⊕a5⊕a3a0=a6⊕a4⊕a3​(2-3)

  将式（2-2）表示為矩陣形式：

[ a 2 a 1 a 0 ] = [ a 6 a 5 a 4 a 3 ] [ 111 110 101 011 ] = [ a 6 a 5 a 4 a 3 ] Q k × r \left[ \begin{matrix} a_2a_1a_0 \end{matrix}\right] = \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]\left[ \begin{matrix} 111\\ 110\\ 101\\ 011 \end{matrix} \right]= \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]Q_{k×r} [a2​a1​a0​​]=[a6​a5​a4​a3​​]⎣⎢⎢⎡​111110101011​⎦⎥⎥⎤​=[a6​a5​a4​a3​​]Qk×r​

  可見，隻要已知資訊碼元，通過矩陣Q就可以得到監督碼元。此外，資訊碼元通過與機關矩陣的運算仍然可以得到資訊碼元。那麼與資訊碼元同次元的機關矩陣與Q可拼成矩陣G，即通過資訊碼元和矩陣G的運算可以得到整個碼組，這樣的矩陣G稱為生成矩陣。

[ a 6 a 5 a 4 a 3 ] I k = [ a 6 a 5 a 4 a 3 ] \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right]I_{k}= \left[ \begin{matrix} a_6a_5a_4a_3 \end{matrix}\right] [a6​a5​a4​a3​​]Ik​=[a6​a5​a4​a3​​]

G k × r = [ I k Q k × r ] G_{k×r}=[I_{k}Q_{k×r}] Gk×r​=[Ik​Qk×r​]

2.3 校正子

  假設接收端接收到的碼組B，由式（2-2）可知以下關系。當S=0，無錯碼，當S≠0，有錯碼，此時S為校正子，可根據校正子不為0的位訓示誤碼的碼元。

B ⋅ H T = S B·H^T=S B⋅HT=S

3 交織碼

  交織碼是應用于抗突發幹擾的一種編碼方式。交織分為三種：随機交織、矩陣交織(塊交織)、卷積交織。

  随機交織，利用PN碼進行随機排序，使得資料具有随機性，這一特征導緻在傳輸過程中，不僅要傳輸資料序列，還要附帶對應交織器的資訊，多用于保密信道和擴頻。

  矩陣交織，按行讀入按列輸出，或者按列讀入按行輸出。

  卷積交織，通過特定結構的卷積交織器，解交織則與交織器結構相反。

  舉一種交織的例子：交織碼将已編碼的碼字(例如(n,k)分組碼)按行讀入，即每一行都是一個許用碼組，一共有n列，這樣将會構成一個矩陣，經過交織後，矩陣轉置，然後傳輸，最後按列讀取，即再次進行轉置。若某一個碼組在傳輸過程中成串發生p比特錯誤，那麼經過轉置後，這些原本位于某一行的p個誤碼将會變為某一列的p個元素，即有p行發生了1比特錯誤。如此看來，交織可以将成串的突發誤碼轉化為随機誤碼。是以，隻要錯誤的數目在碼組的差錯控制範圍内便可實作檢錯和糾錯。交織碼的交織深度越大，離散度就越大，抗突發差錯能力也越強。

4 循環碼

4.1 循環碼的表示

  循環碼是一類具有循環性的線性分組碼。循環性是指任意碼組循環移位後，仍然為該碼的一個許用碼組。循環碼也可以用多項式表示。

A ( x ) = a n − 1 x n − 1 + a n − 2 x n − 2 + . . . + a 1 x + a 0 A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{1}x+a_0 A(x)=an−1​xn−1+an−2​xn−2+...+a1​x+a0​

  若任意一個多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數小于n的餘式R(x)，那麼F(x)等價于R(x)即：

F ( X ) N ( X ) = Q ( x ) + R ( x ) N ( x ) \frac{F(X)}{N(X)}=Q(x)+\frac{R(x)}{N(x)} N(X)F(X)​=Q(x)+N(x)R(x)​

F ( x ) ≡ R ( x ) F(x)≡R(x) F(x)≡R(x)

  在循環碼中，設A(x)是一個長度為n的碼組，若

x i ⋅ A ( x ) ≡ A ′ ( x ) （ 模 ( x n + 1 ) ） x^i·A(x)≡A'(x) （模(x^n+1)） xi⋅A(x)≡A′(x)（模(xn+1)）

  則 A ′ ( x ) A'(x) A′(x)也是一個許用碼組。例如：一循環碼是1001011，即

A ( x ) = x 6 + x 3 + x + 1 A(x)=x^6+x^3+x+1 A(x)=x6+x3+x+1

  若給定i=3，那麼

x 3 ⋅ A ( x ) = x 9 + x 6 + x 4 + x 3 ≡ x 6 + x 4 + x 3 + x 2 （ 模 x 7 + 1 ） x^3·A(x)=x^9+x^6+x^4+x^3≡x^6+x^4+x^3+x^2（模x^7+1） x3⋅A(x)=x9+x6+x4+x3≡x6+x4+x3+x2（模x7+1）

  由多項式，移位後的循環碼為1011100，正好是1001011左移三位後的結果。是以，長度為n的循環碼必定為模( x n + 1 x^n+1 xn+1)的一個餘式。

4.2 循環碼的生成多項式和生成矩陣

  在2.2節中，我們提到了生成矩陣，通過資訊碼和生成矩陣可以得到整個碼組，而生成矩陣的每一行都是一個許用碼組，由循環碼特點，循環碼組通過移位可以互相轉化，那麼循環碼的生成矩陣G可以表示為

G ( x ) = [ x k − 1 g ( x ) x k − 2 g ( x ) ︙ x g ( x ) g ( x ) ] G(x)=\left[ \begin{matrix} x^{k-1}g(x)\\ x^{k-2}g(x)\\ ︙\\ xg(x)\\ g(x) \end{matrix} \right] G(x)=⎣⎢⎢⎢⎢⎡​xk−1g(x)xk−2g(x)︙xg(x)g(x)​⎦⎥⎥⎥⎥⎤​

  這裡的生成多項式g(x)需要滿足常數項為1，且是（ x n x^n xn+1）的n-k次因子。

4.3 循環碼編碼

  分為如下5個步驟：

1. 首先根據給定的(n,k)值標明生成多項式g(x)，即從 x n x^n xn+1的因式分解中選一個常數項為1的(n-k)次多項式作為g(x)
2. 将資訊碼表示為多項式m(x)，其幂次小于k。
3. 用 x n − k x^{n-k} xn−k乘m(x)，得到的 x n − k x^{n-k} xn−km(x)的幂次必定小于n。
4. 用g(x)除 x n − k x^{n-k} xn−km(x)，得到餘式r(x)，r(x)的幂次必定小于g(x)的幂次，即小于(n-k)。
5. 将此餘式r(x)加于資訊位之後作為監督位，即将r(x)和 x n − k x^{n-k} xn−km(x)相加，得到的多項式即為碼多項式，即編出的碼組A(x)為：A(x)= x n − k x^{n-k} xn−km(x)+r(x)。

5 截短循環碼

  假設循環碼(n,k)，共有2k個許用碼組，現使前i(0＜i＜k)位資訊位全為"0"，于是它變成僅有2{k-i}個許用碼組。然後删去這i位全"0"的資訊位，最終得到一個(n-i,k-i)的線性碼，将這種碼稱為截短循環碼，它與原循環碼具有相同的糾錯能力，并且編解碼方法仍和截短前一樣。

6 BCH碼

  BCH碼可以糾正多個錯碼，也屬于循環碼，是以也可以由循環碼的生成方式生成，隻需要确定g(x)即可，而g(x)根據n、k和糾錯個數t查表得到。即先查g(x)，然後産生生成矩陣G，用資訊碼乘G得到BCH編碼。

7 RS碼

  假如BCH碼的碼元不用二進制的"0"和"1"表示，而取多進制的一個元素，如BCH的每個碼元用 2 m 2^m 2m進制中的一個m位的二進制碼組表示，則這種多進制BCH碼就是RS碼。例如對于資訊位為10101010101的本原(15,11)碼，其碼序列為10101010101011。如果進行RS編碼，取m=2，即每一位将用一個2比特的二進制碼表示(“01"表示"0”，“10"表示"1”)，那麼輸出的RS碼就是1001100110011001100110011010。由此可見，當以2b為一組計算時，一旦出現"00"或者"11"或不符合循環碼的循環關系時，表示序列傳輸出現差錯。是以，RS碼是一類具有很強糾錯能力的多進制BCH碼。

  當然，RS編碼原理并不僅僅是像上述說得輕松，還涉及到伽羅華域的相關概念，在後期學習中，會更一篇RS碼編解碼原理的博文。