本专栏包含信息论与编码的核心知识，按知识点组织，可作为教学或学习的参考。markdown版本已归档至【Github仓库：github.com/timerring/i… 】或者公众号【AIShareLab】回复 信息论 获取。
线性分组码
基本概念
线性分组码数学定义: 编码前信息码元空间 U k U^{k} U k f f f C n C^{n} C n f : U k → C n f: U^{k} \rightarrow C^{n} f : U k → C n n > k n>k n > k f f f
f ( α u ⊕ β u ′ ) = α f ( u ) ⊕ β f ( u ′ ) f\left(\alpha \mathbf{u} \oplus \beta \mathbf{u}^{\prime}\right)=\alpha f(\mathbf{u}) \oplus \beta f\left(\mathbf{u}^{\prime}\right) f ( α u ⊕ β u ′ ) = α f ( u ) ⊕ β f ( u ′ ) 其中 α , β ∈ G F ( 2 ) = { 0 , 1 } , u 与 u ′ ∈ U k \alpha, \beta \in G F(2)=\{0,1\}, \mathbf{u} 与 \mathbf{u}^{\prime} \in \mathbf{U}^{k} α , β ∈ GF ( 2 ) = { 0 , 1 } , u 与 u ′ ∈ U k f f f
线性分组码是一类奇偶校验码，它由（n，k ）形式表示。编码器将一个 k 比特信息分组（信息矢量）转变成一个更长的由给定符号集组成的 n 比特编码分组（编码矢量）。当这个符号集包含 2 个元素 (0 and1） 时 , 称为二进制编码。
kbit 信息形成 2 k 2^k 2 k 2 n 2^n 2 n
定义: 如果分组码中任意两个码字的线性组合仍是分组码的一个码字，那么该分组码是线性的 。 对于二进制码，如果 c i c_i c i c j c_j c j c i c_i c i c j c_j c j
例:(7,3)线性分组码
d min = 4 d_{\min }=4 d m i n = 4 c i + c j c_{i}+c_{j} c i + c j
快速计算方法：看除全零码以外，最小的码重就是它的码距。
编码-生成矩阵
编码和生成矩阵
（n，k ）线性分组码的构造——依据给定的 k 个信息码元，设计满足编码条件（最小码距、码率）的 n-k个监督码元 。
例: 二元 (7,3) 线性分组码, n=7, k=3, r=7-3=4 ,
u = ( u 2 , u 1 , u 0 ) → c = ( c 6 , c 5 , c 4 , c 3 , c 2 , c 1 , c 0 ) \mathbf{u}=\left(u_{2}, u_{1}, u_{0}\right) \rightarrow \mathbf{c}=\left(c_{6}, c_{5}, c_{4}, c_{3}, c_{2}, c_{1}, c_{0}\right) u = ( u 2 , u 1 , u 0 ) → c = ( c 6 , c 5 , c 4 , c 3 , c 2 , c 1 , c 0 ) 构造:
编码位高位直接对应信息位 ;
编码位低位由信息位组合而成 。.
c 6 = u 2 c 3 = u 2 ⨁ u 0 = c 6 ⊕ c 4 c 5 = u 1 c 2 = u 2 ⨁ u 1 ⊕ u 0 = c 6 ⊕ c 5 ⊕ c 4 c 4 = u 0 c 1 = u 2 ⨁ u 1 = c 6 ⊕ c 5 c 0 = u 1 ⊕ u 0 = c 5 ⊕ c 4 \begin{array}{ll}
c_{6}=u_{2} & c_{3}=u_{2} \bigoplus u_{0}=c_{6} \oplus c_{4} \\
c_{5}=u_{1} & c_{2}=u_{2} \bigoplus u_{1} \oplus u_{0}=c_{6} \oplus c_{5} \oplus c_{4} \\
c_{4}=u_{0} & c_{1}=u_{2} \bigoplus u_{1}=c_{6} \oplus c_{5} \\
& c_{0}=u_{1} \oplus u_{0}=c_{5} \oplus c_{4}
\end{array} c 6 = u 2 c 5 = u 1 c 4 = u 0 c 3 = u 2 ⨁ u 0 = c 6 ⊕ c 4 c 2 = u 2 ⨁ u 1 ⊕ u 0 = c 6 ⊕ c 5 ⊕ c 4 c 1 = u 2 ⨁ u 1 = c 6 ⊕ c 5 c 0 = u 1 ⊕ u 0 = c 5 ⊕ c 4 写成矩阵形式，为
即 : C = u G \mathbf{C}=\mathbf{u} \mathbf{G} C = uG u \mathbf{u} u C = u G \mathbf{C}=\mathbf{u G} C = uG G \mathbf{G} G
G \mathbf{G} G
G = ( g 1 g 2 ⋮ g k ) = ( g 11 … g 1 n ⋮ ⋮ ⋮ g k 1 … g k n ) k × n 阶 \mathbf{G}=\left(\begin{array}{c}
\mathbf{g}_{1} \\
\mathbf{g}_{2} \\
\vdots \\
\mathbf{g}_{k}
\end{array}\right)=\left(\begin{array}{ccc}
g_{11} & \ldots & g_{1 n} \\
\vdots & \vdots & \vdots \\
g_{k 1} & \ldots & g_{k n}
\end{array}\right) k \times n \text { 阶 } G = ⎝ ⎛ g 1 g 2 ⋮ g k ⎠ ⎞ = ⎝ ⎛ g 11 ⋮ g k 1 … ⋮ … g 1 n ⋮ g kn ⎠ ⎞ k × n 阶 线性分组码的编码: C = u G \mathrm{C}=\mathbf{u G} C = uG
该 (7,3) 码的生成矩阵为
如：若输入的信息为 [011], 由 C = u G \mathrm{C}=\mathrm{uG} C = uG C = [ 0111010 ] \mathrm{C}=[0111010] C = [ 0111010 ]
例 生成矩阵如图矩阵。μ = ( 1 1 1 ) \mu=\left(\begin{array}{lll}1 & 1 & 1\end{array}\right) μ = ( 1 1 1 )
G = [ 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 ] G=\left[\begin{array}{lllllll}
1 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1
\end{array}\right] G = ⎣ ⎡ 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 ⎦ ⎤
系统码与非系统码
若生成矩阵可以分解成两个子块,
G = [ I ⋮ Q ] 或 G = [ Q ⋮ I ] \boldsymbol{G}=[\boldsymbol{I} \vdots \boldsymbol{Q}] \text { 或 } \boldsymbol{G}=[\boldsymbol{Q} \vdots \boldsymbol{I}] G = [ I ⋮ Q ] 或 G = [ Q ⋮ I ] 其中 I \mathrm{I} I k \boldsymbol{k} k Q \mathrm{Q} Q k ∗ ( n − k ) \boldsymbol{k} *(\boldsymbol{n}-\boldsymbol{k}) k ∗ ( n − k )
若信息分组以不变的形式出现在线性分组码的任意k位(一般为前k位，或后k位），则称此码组为系统码，否则称为非系统码。(如果编码器输出的比特流中原样包含了信息比特，叫系统码。编码输出中的这些原始信息位也叫系统位 。)
生成矩阵的特性
a. 生成矩阵 G \mathbf{G} G k \boldsymbol{k} k n \boldsymbol{n} n k × n \boldsymbol{k} \times \boldsymbol{n} k × n G \mathrm{G} G k \boldsymbol{k} k
b. 线性分组码的每个码字是生成矩阵 G \mathbf{G} G
C = u G = ( u k − 1 , … , u 1 , u 0 ) ( g 1 g 2 ⋮ g k ) = u k − 1 g 1 + u k − 2 g 2 + … + u 1 g k − 1 + u 0 g k \begin{array}{r}
\mathbf{C}=\mathbf{u G}=\left(u_{k-1}, \ldots, u_{1}, u_{0}\right)\left(\begin{array}{c}
\boldsymbol{g}_{1} \\
\boldsymbol{g}_{2} \\
\vdots \\
\boldsymbol{g}_{k}
\end{array}\right) \\
=u_{k-1} \boldsymbol{g}_{1}+u_{k-2} \boldsymbol{g}_{2}+\ldots+u_{1} \boldsymbol{g}_{k-1}+u_{0} \boldsymbol{g}_{k}
\end{array} C = uG = ( u k − 1 , … , u 1 , u 0 ) ⎝ ⎛ g 1 g 2 ⋮ g k ⎠ ⎞ = u k − 1 g 1 + u k − 2 g 2 + … + u 1 g k − 1 + u 0 g k c. G的每一行是一个码字。
d. 生成矩阵G的各行线性无关 。思考:已知码字集合，如何构造生成矩阵?
e. 对非系统码的生成矩阵 ，总可以经过初等行变换 及列交换 构造成另一等价的系统码的生成矩阵 并且这两个线性分组码检、纠错性能相同。
求非系统 (7,4) 线性分组码的等价系统码生成矩阵。
G = [ 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 ] \mathrm{G}=\left[\begin{array}{lllllll}
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\end{array}\right] G = ⎣ ⎡ 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 ⎦ ⎤
列的交换和初等行变换不改变矩阵的秩，变换后矩阵的各行矢量仍线性无关 。
任何一个线性分组 (n, k)码都可等价于一个系统码 。（纠错能力、编码结构)
思考:由非系统型生成矩阵变换成系统型生成矩阵，答案唯一吗?
已知某(7，4)分组码的码表如下，请问最小汉明距是多少?请写出该码的典型生成矩阵。
最小汉明距：3
生成矩阵:
G = [ 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 ] G=\left[\begin{array}{lllllll}
1 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 1
\end{array}\right] G = ⎣ ⎡ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 ⎦ ⎤ 检错-监督矩阵
由分组码的生成矩阵可得到其监督矩阵。
H C T = 0 T , [ P : I ] C T = 0 T \mathbf{H C}^{T}=\mathbf{0}^{T},[\mathbf{P}: \mathbf{I}] \mathbf{C}^{T}=\mathbf{0}^{T} HC T = 0 T , [ P : I ] C T = 0 T 一般情况下, 一个 (n, k) 线性分组码的H矩阵中的（n-k）行对应（n-k）个线性监督方程组, 以确定（n-k）个监督码元。
H \mathbf{H} H （ n − k ） × n （n-k） \times \mathbf{n} （ n − k ） × n
若 H=[P ：I], 其中 I 是 ( n-k ）阶方阵, 则 H 为典型监督矩阵。
监督矩阵
H ⋅ C T = H ⋅ G T μ T = 0 T H \cdot C^{T}=H \cdot G^{T} \mu^{T}=0^{T} H ⋅ C T = H ⋅ G T μ T = 0 T 或者 G \mathbf{G} G H ⋅ G T = 0 T ⇒ G ⋅ H T = 0 H \cdot G^{T}=0^{T} \Rightarrow G \cdot H^{T}=0 H ⋅ G T = 0 T ⇒ G ⋅ H T = 0
G ⋅ H T = [ I Q [ P T I ] = P T + Q = 0 ∴ Q = P T 或 P = Q T \begin{array}{c}
G \cdot H^{T}=\left[\begin{array}{ll}
I & Q
\end{array}\left[\begin{array}{c}
P^{T} \\
I
\end{array}\right]=P^{T}+Q=0\right. \\
\therefore Q=P^{T} \text { 或 } P=Q^{T}
\end{array} G ⋅ H T = [ I Q [ P T I ] = P T + Q = 0 ∴ Q = P T 或 P = Q T 请思考：已知 G = [ I : Q ] ⇒ H = [ P : I ] \mathbf{G}=[I: Q] \Rightarrow \mathbf{H}=[\mathrm{P}: I] G = [ I : Q ] ⇒ H = [ P : I ] G = [ Q : I ] G=[Q: I] G = [ Q : I ] H = [ I : P ] H= [I:P] H = [ I : P ]
监督方程
由
H ⋅ C T = H ⋅ G T μ T = 0 T ⇒ C H T = 0 \begin{aligned}
H \cdot C^{T} & =H \cdot G^{T} \mu^{T}=0^{T} \\
& \Rightarrow C H^{T}=0
\end{aligned} H ⋅ C T = H ⋅ G T μ T = 0 T ⇒ C H T = 0 可知，若
C ~ H T ≠ 0 \widetilde{\boldsymbol{C}} \boldsymbol{H}^{T} \neq \mathbf{0} C H T = 0 则 C ~ \widetilde{\boldsymbol{C}} C
C H T = 0 \boldsymbol{C H}^{T}=0 CH T = 0 称为线性分组码的监督方程。
监督矩阵的特性
由H矩阵可以建立线性分组码的线性方程组, H矩阵共有 n-k 行, 其中每行代表一个线性方程的系数, 表示求一个监督位的线性方程;
H矩阵的每行与码集中的一个码字的内积为 0 ;
任何一个 ( n − k ) (\boldsymbol{n}-\boldsymbol{k}) ( n − k ) H \mathrm{H} H ( n − k ) (\boldsymbol{n}-\boldsymbol{k}) ( n − k )
一个 ( n , k , d ) (\boldsymbol{n}, \boldsymbol{k}, d) ( n , k , d )
系统码的典型生成矩阵 G \mathbf{G} G H \mathbf{H} H
已知一 (6,3) 线性分组码的生成矩阵G如下，求其监督矩阵 H \mathbf{H} H
G = [ 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 ] \begin{array}{l}
\boldsymbol{G}=\left[\begin{array}{llllll}
1 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 1
\end{array}\right] \\
\end{array} G = ⎣ ⎡ 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 ⎦ ⎤
参考文献：
Proakis, John G., et al. Communication systems engineering . Vol. 2. New Jersey: Prentice Hall, 1994.
Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering . Vol. 2. New Jersey: Prentice Hall, 1994.
周炯槃. 通信原理（第3版）[M]. 北京：北京邮电大学出版社, 2008.
樊昌信, 曹丽娜. 通信原理（第7版） [M]. 北京：国防工业出版社, 2012.
