第8章数字通信中的信道编码 发送滑可以斜正错误的仍技收璃 图8-2-2FEC原理框图 (3)混合纠错方式(HEC) 发送端发送既能自动纠错又能检测的码。接收端收到码流后，检查差错情况，如果错 误在纠错能力范围以内，则自动纠错：如果超过了纠错能力，但能检测出来，则经过反馈 信道请求发送端重发。HEC的性能及优缺点介于ARQ与FEC之间。 能够发现和纠正误的码 发送端 接收端 应答信号 图8-2-3HEC原理框图 8.3分组码 意分组码是将长度为k的数字向量映射为长度为n的数字向量(>k),从而引入元余的 一种编码方法。 。如果映射是线性的，则所产生的码就是线性码，否则为非线性码。通常数字信号处理 的信息是二进制的，因此这种映射一般是针对二进制信号的。 8.3.1有限域FG(q) 编译码的功能体现为对码字进行乘、加算术运算。在有限(q)个元素的集合构成的域中， 进行乘加算术运算服从代数运算的惯例，如：封闭性、结合率、交换率、分配率都成立： 域中存在零元素、每个非零元素都存在对应的逆元素、存在一个单位元素。有限域只有当9 为质数或质数的m次方(q)时才能构成，它们都是基于模运算。 与实数域、复数域和整数域的算术运算相比，FG(q)主要有以下几个不同点： 1)FG(q)是采用模q运算来保证其封闭性：例如：a,b∈FG(q),则c=a+b∈FG(q) 相当于整数域中c=(a+b)modg 2)乘法的逆元素与加法的逆元素相同，b=-b,因此a/b定义为ab=a(-b): 3)多维有限域空间中两个矢量的之间的距离定义为汉明距离，但内积、正交的概念与 多维欧几里德空间的相似。 8.3.2分组码的基本概念 定义：(m,)的分组码是由2个长度都为n的码字构成的集合，用来对k比特信息进行 西安电子科技大学
第 8 章 数字通信中的信道编码 西安电子科技大学 6 图 8-2-2 FEC 原理框图 (3) 混合纠错方式（HEC） 发送端发送既能自动纠错又能检测的码。接收端收到码流后，检查差错情况，如果错 误在纠错能力范围以内，则自动纠错；如果超过了纠错能力，但能检测出来，则经过反馈 信道请求发送端重发。HEC 的性能及优缺点介于 ARQ 与 FEC 之间。 图 8-2-3 HEC 原理框图 8.3 分组码 ) 分组码是将长度为 k 的数字向量映射为长度为 n 的数字向量（n>k），从而引入冗余的 一种编码方法。 ) 如果映射是线性的，则所产生的码就是线性码，否则为非线性码。通常数字信号处理 的信息是二进制的，因此这种映射一般是针对二进制信号的。 8.3.1 有限域 FG( q ) 编译码的功能体现为对码字进行乘、加算术运算。在有限( q )个元素的集合构成的域中， 进行乘加算术运算服从代数运算的惯例，如：封闭性、结合率、交换率、分配率都成立； 域中存在零元素、每个非零元素都存在对应的逆元素、存在一个单位元素。有限域只有当 q 为质数或质数的 m 次方（ q m）时才能构成，它们都是基于模运算。 与实数域、复数域和整数域的算术运算相比，FG( q )主要有以下几个不同点： 1）FG( q )是采用模 q运算来保证其封闭性；例如：a b, ∈FG( q )，则c = a b + ∈FG( q)， 相当于整数域中c = mod ( ) q a b + 。 2）乘法的逆元素与加法的逆元素相同，b-1=-b，因此 ( ) 1 a b ab a b / − 定义为 = − ； 3）多维有限域空间中两个矢量的之间的距离定义为汉明距离，但内积、正交的概念与 多维欧几里德空间的相似。 8.3.2 分组码的基本概念 定义：(, ) n k 的分组码是由 2k 个长度都为 n 的码字构成的集合，用来对 k 比特信息进行
第8章数字通信中的信道编码 编码，每个码字都是一个n维矢量：q进制分组码其码字矢量的元素取值于有限域FG(q): {0,1,q-},即每个码字中的元素都是从{0,1，q-中选取的。 码率：长度n的二进制分组码有2种可能的码字，从中选择M个码字作为可用码， M=2(k<),而其余2”-2*个码为禁用码。这样k比特的一块数据经编码后映射为一个n 比特的数据块，这就是(m,k)的分组码。其码率定义为R=k/n。 码字重量：码字包含的非零元素的个数。如果全部M个码字具有相同的重量，这种码 称为恒重码。 汉明距离：任意两个码字C,和C,对应位置上元素不同的总个数，记为d。如(7,3)分 组码中的两个码字(0111010)与(0011101)的汉明距离为4。汉明距离满足三角不等式， 即若CCCk为同一码组中的不同码字，则d+d2d 线性码：设C,和C,为某(m,k)分组码的两个码字，a和a是码元字符集里任意两个元 素，若α，C+a,C,也是该码的一个码字，则这种分组码称为线性码。线性码必包含全零码： 恒重码是非线性码。 最小码距d：M个码字集合中汉明距离{d,}的最小值称为最小码距，最小码距关系 者该码字的检错与纠错能力。(n,)饯性分组码最小距离等于dm的充要条件是校验矩阵H 中任何dmml列线性无关。 零空间：(m,k)分组码构成k维空间是n维矢量空间的子空间，记为S。,其中任意k个 线性无关的矢量可构成“基底”。如果n维矢量空间S中存在另一组矢量，它们与S的基底” 都正交，则这组矢量构成的子空间称为S的零空间，其维数必定等于(-k)。零空间与(m,k) 分组码的生成矩阵G和监督矩阵H之间存在紧密联系。 检错能力：假如编码码元C通过噪声干扰信道传输，接收码元R在j个位置出现错误， 则dC,Rj。若该分组码的最小汉明距为dmm,这意味着该码组中任意两个码字至少在dmm 个位置上不同，因此dmm1或更少的错误将使R不是该码组中的码字。当接收端发现接收 码字是非法码字（非码组中的码）时，就认为检测到了错误。当错误位置大于等于dm时， 由于至少存在一对合法码字的汉明距满足dmm,因此该分组码不可能检测到所有dmm个错误， 这使得分组码的检错能力为dmml。 纠错能力：令1为满足2+1sdm≥2什2的正整数。其纠错能力为=(dmm1)2。 系统码：系统码是指其编码输出信息块中完全保留输入信息块的编码方法。编码输出 的原始信息位也叫系统位。(，k)分组码中，系统码通常指前k位为原始信息位。 根据信息码元与监督码元的函数关系，分为线性码和非线性码。 根据信息码元和监督码元之间的约束方式，分为分组码和卷积码。在分组码中，监督 西安电子科技大学 7
第 8 章 数字通信中的信道编码 西安电子科技大学 7 编码，每个码字都是一个 n 维矢量；q 进制分组码其码字矢量的元素取值于有限域 FG( q )： {0, 1, ., 1} q − ，即每个码字中的元素都是从{0, 1, ., 1} q − 中选取的。 码率：长度 n 的二进制分组码有 2n 种可能的码字，从中选择 M 个码字作为可用码， M = 2k ( ) k n < ，而其余 2 2 n k − 个码为禁用码。这样 k 比特的一块数据经编码后映射为一个 n 比特的数据块，这就是(, ) n k 的分组码。其码率定义为 / R kn c = 。 码字重量：码字包含的非零元素的个数。如果全部 M 个码字具有相同的重量，这种码 称为恒重码。 汉明距离：任意两个码字Ci 和Cj 对应位置上元素不同的总个数，记为 ij d 。如（7,3）分 组码中的两个码字（0111010）与（0011101）的汉明距离为 4。汉明距离满足三角不等式， 即若 Ci、Cj、Ck 为同一码组中的不同码字，则 dik+djk≥dij。 线性码：设Ci 和Cj 为某 (, ) n k 分组码的两个码字，α1和α 2 是码元字符集里任意两个元 素，若α1 2 C C +α j 也是该码的一个码字，则这种分组码称为线性码。线性码必包含全零码； 恒重码是非线性码。 最小码距 min d ： M 个码字集合中汉明距离{ }ij d 的最小值称为最小码距，最小码距关系 着该码字的检错与纠错能力。(n,k)线性分组码最小距离等于 dmin 的充要条件是校验矩阵 H 中任何 dmin-1 列线性无关。 零空间：(,) n k 分组码构成 k 维空间是 n 维矢量空间 S 的子空间，记为 c S ，其中任意 k 个 线性无关的矢量可构成“基底”。如果 n 维矢量空间 S 中存在另一组矢量，它们与 c S 的“基底” 都正交，则这组矢量构成的子空间称为 c S 的零空间，其维数必定等于( ) n k − 。零空间与 (, ) n k 分组码的生成矩阵 G 和监督矩阵 H 之间存在紧密联系。 检错能力：假如编码码元 C 通过噪声干扰信道传输，接收码元 R 在 j 个位置出现错误， 则 d(C,R)=j。若该分组码的最小汉明距为 dmin，这意味着该码组中任意两个码字至少在 dmin 个位置上不同，因此 dmin-1 或更少的错误将使 R 不是该码组中的码字。当接收端发现接收 码字是非法码字（非码组中的码）时，就认为检测到了错误。当错误位置大于等于 dmin时， 由于至少存在一对合法码字的汉明距满足dmin，因此该分组码不可能检测到所有dmin个错误， 这使得分组码的检错能力为 dmin-1。 纠错能力：令 t 为满足 2t+1≤dmin≥2t+2 的正整数。其纠错能力为 t=（dmin -1）/2。 系统码： 系统码是指其编码输出信息块中完全保留输入信息块的编码方法。编码输出 的原始信息位也叫系统位。（n,k）分组码中，系统码通常指前 k 位为原始信息位。 根据信息码元与监督码元的函数关系，分为线性码和非线性码。 根据信息码元和监督码元之间的约束方式，分为分组码和卷积码。在分组码中，监督
第8章数字通信中的信道编码 码元仅与本码组的信息码元有关，而在卷积码中，监督码元不仅与本组的信息码元有关， 还与前面若干组的信息码元有关。 8.3.3生成矩阵与校验矩阵 设编码器输入为Xn=x1,x,xt小，输出矢量为Cn=c,cn2,C】,对于二进制线 性分组码，编码运算可用n个方程表示： Cw =xmi8+x+j=1.2.n (8-3-8) 改写成矩阵形式：Cn=XG,其中 「81「81812.gm G=8 88.8 (8-3-9) 称为生成矩阵，{g}是(m,k)分组码的基底。 >如：n=8,k=6,即每输入6比特，编码成一个8比特的码字。可以看出，线性分组 码的编码码元为生成矩阵各列向量的线性组合，线性组合的系数为输入的信息序列。 (m,k)分组码的生成矩阵G都可通过初等变换简化成如下的系统码形式： [100.0A1Pa.PA-t ::::ξ： (8-3-10) 000 1 PuPia.p-4J 其中I4是k×k的单位矩阵，P是(n-k)×(n-k)的矩阵，P决定(n-k)个冗余比特。 任何一个(m,k)分组码都存在一个n-k维对偶码，对偶码是由零空间中n-k个线性无关 的码矢量组成，其生成矩阵表示为H。由于(m,k)码中任意一个码字C均与其对偶码的各 码字正交，因此(m,)码的任意码字必正交于矩阵H的每一行，可得 m,CHT=0或GHT=0 (8-3-11) 可见矩阵H可以用来检错，因而称为(m,)码的校验矩阵。 ■线性分组码可以由一个校验矩阵H等效描述，所有码字C=(1,02,c)均满足 HC0。校验矩阵的每一行表示一个校验约束关系，行中不为零的码元变量参与了 该行的校验方程。 若G是系统生成矩阵，则对偶码的生成矩阵： 西安电子科技大学
第 8 章 数字通信中的信道编码 西安电子科技大学 8 码元仅与本码组的信息码元有关，而在卷积码中，监督码元不仅与本组的信息码元有关， 还与前面若干组的信息码元有关。 8.3.3 生成矩阵与校验矩阵 设编码器输入为 1 2 [ , , ., ] X xx x m m m mk = ，输出矢量为 1 2 [ , , ., ] C cc c m m m mn = ，对于二进制线 性分组码，编码运算可用 n 个方程表示： 11 2 2 . 1,2,., mj m j m j mk kj c xg xg xg j n = + ++ = (8-3-8) 改写成矩阵形式：C XG m m = ，其中 1 11 12 1 2 21 22 2 1 2 n n k k k kn g gg g g gg g G g gg g ⎡ ⎤ ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ = = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ " " # ## # " (8-3-9) 称为生成矩阵，{gi} 是(, ) n k 分组码的基底。 ¾ 如： n k = = 8, 6 ，即每输入 6 比特，编码成一个 8 比特的码字。可以看出，线性分组 码的编码码元为生成矩阵各列向量的线性组合，线性组合的系数为输入的信息序列。 (, ) n k 分组码的生成矩阵G 都可通过初等变换简化成如下的系统码形式： 11 12 1 21 22 2 1 2 100 0 010 0 [ ] 000 1 n k n k k k k kn k pp p pp p G IP pp p − − − ⎡ ⎤ ⎢ ⎥ = = ⎣ ⎦ " " " " ## # ## # " " (8-3-10) 其中 Ik 是 k k × 的单位矩阵，P 是( )( ) nk nk −×− 的矩阵，P 决定( ) n k − 个冗余比特。 任何一个(, ) n k 分组码都存在一个 n k − 维对偶码，对偶码是由零空间中 n k − 个线性无关 的码矢量组成，其生成矩阵表示为 H 。由于 (, ) n k 码中任意一个码字Cm 均与其对偶码的各 码字正交，因此(, ) n k 码的任意码字必正交于矩阵 H 的每一行，可得 , T ∀ = mCHm 0或 T GH = 0 (8-3-11) 可见矩阵 H 可以用来检错，因而称为(, ) n k 码的校验矩阵。 线性分组码可以由一个校验矩阵 H 等效描述，所有码字 C=(c1,c2,.,cn)均满足 HCT =0T 。校验矩阵的每一行表示一个校验约束关系，行中不为零的码元变量参与了 该行的校验方程。 若G 是系统生成矩阵，则对偶码的生成矩阵：
第8章数字通信中的信道编码 H=IPT L] (8-3-12) 设C,代表(n,k)码中重量最小的码字，则其重量就是该码的最小距离d。由C,=0, 可知H的秩≤d-1。由零空间的性质可知H的秩为n-k,则得 d≤n-k+l (8-3-13) 【定理】(n,k)线性分组码最小距离等于d的充要条件是H矩阵中任何d-1列线性无关。 【例】(7,4)汉明码编码 (7,4)分组码的形式为Aa6a5a4aa2a1a,其中aa5aa为信息码元，aaa为监 督码元，监督码元与信息码元的关系为： a,+a+a+a=0 a=a。+a+a或者a。+a+a+a-0 (8-3-14) ao as +as +as a+a+a+a。=0 写成矩阵形式： HA=0 (8-3-15) 「1110100 其中矩阵1101010就是校验矩阵，0=0：H=P，P为r×K的矩阵 1011001 0 I为r阶单位阵。如将方程补充完整，则有 a6=a6 [a1f1000] as=ds 0100 a =a, 0010a a3=d3 人 或a 0001 (8-3-16) a. a=a6+a5+a 1110 a=as +as+a /9 1101La do asas ay a 1011 「1000111门 其中矩阵 0100110 就是为生成矩阵G,可表示为GIP]:利用信息序列与生 0010101 0001011 成矩阵就可以产生编码码元。此码共有8个码字，如表8-3-1所示。 西安电子科技大学
第 8 章 数字通信中的信道编码 西安电子科技大学 9 [ ] T H PI = n k − (8-3-12) 设Cj 代表(, ) n k 码中重量最小的码字，则其重量就是该码的最小距离 min d 。由 T C Hj = 0 ， 可知 H 的秩 min ≤ − d 1。由零空间的性质可知 H 的秩为 n k − ，则得 min d nk ≤ − +1 (8-3-13) 【定理】(n,k)线性分组码最小距离等于 min d 的充要条件是 H 矩阵中任何 min d −1列线性无关。 【例】（7,4）汉明码编码 （7,4）分组码的形式为 A=[a6 a5 a4 a3 a2 a1 a0]，其中 a6a5a4a3为信息码元，a2a1a0为监 督码元，监督码元与信息码元的关系为： 2 654 1 653 0 643 a aaa aaaa a aaa ⎧ =++ ⎪ ⎨ =++ ⎪ ⎩ =++ 或者 6542 6531 6430 0 0 0 aaaa aaaa aaaa ⎧ + ++= ⎪ ⎨ + ++= ⎪ ⎩ + ++= (8-3-14) 写成矩阵形式: HA= 0 (8-3-15) 其中矩阵 H= 1110100 1101010 1011001 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 就是校验矩阵，0 = 0 0 0 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ；H =[P I]，P 为 r×K 的矩阵， I 为 r 阶单位阵。如将方程补充完整，则有 6 6 5 5 4 4 3 3 2 654 1 653 0 643 a a a a a a a a a aaa aaaa a aaa ⎧ = ⎪ = ⎪ ⎪ = ⎪ ⎨ = ⎪ =++ ⎪ ⎪ =++ ⎪ ⎩ =++ 或 6 5 6 4 5 3 4 2 3 1 0 1000 0100 0010 0001 1110 1101 1011 a a a a a a a a a a a ⎡ ⎤ ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎡ ⎤ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ (8-3-16) 其中矩阵 1000111 0100110 0010101 0001011 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 就是为生成矩阵 G，可表示为 G=[ I PT ]；利用信息序列与生 成矩阵就可以产生编码码元。此码共有 8 个码字，如表 8-3-1 所示
第8章数字通信中的信道编码 表8-3-1(74)线性分组码 码字 码字 信息元信息元监督元信息元信息元监督元 00000000000 1000 1000111 00110011110 1011 1011001 01000100110 1100 1100001 010001001 0111011100011111111111 8.3.4伴随式译码 ■设发送的码字为C=(cm-1,cm-2.c1,co),信道产生的错误图样为E=(en-1,en-2.e 1,eo),则接收码字为R=C+E=(cn-+en-,cn-2+en-2.c+ebc0+eo),其中c 和e均为二进制数字，加法为模2加。 ■译码器的任务就是从R中恢复C,或者说是从R中估计E,如成功恢复，则译码 成功，否则译码错误。 伴随式定义为接收码字与校验矩阵之乘积，即 S=RHT=(C+E)HT=CHT+EHT (8-3-17) >由(8-1-3)式可知CH=0,因此S=RH=EH。 >如果没有错误传输，即E=0,则S=EH=0,若有错误传输，即E0,则S=EH0。 >对于确定的编码，H是已知的，因此仅S与信道错误图样E有关。如果能从S中得到 E,则可以从接收码字中正确恢复发送码字，即R+E=C+E+E=C。因此将S定义为接 收矢量R的伴随式或矫正子。线性分组码的一个重要性质是伴随式与错误图样是一 对应的。 如何从S中确定E,以便完成正确译码：为了能正确检错与纠错，校验矩阵H需满足： ①H中没有全0列，否则相应码字位置上的错误就无法影响伴随式，因而无法检测。 ②H中所有列都是惟一的；因为假如有两列相同的话，那么二者所对应的错误码发生 位置就无法识别。 我们以可纠正一位错误的线性分组码为例来说明伴随式与错误图样的关系。(，k)码共 有2个有效码字，由于错误图样不能为有效码字（否则无法检错与纠错），因此错误图样属 于2空间，错误图样有2个，这样可以构造出分组码的标准阵列，如表8-3-2所示。 表83-2分组码的标准阵列 西安电子科技大学 10
第 8 章 数字通信中的信道编码 西安电子科技大学 10 表 8-3-1 (7,4)线性分组码 码字 码字 信息元 信息元 监督元 信息元 信息元 监督元 0000 0000 000 1000 1000 111 0001 0001 011 1001 1001 100 0010 0010 101 1010 1010 010 0011 0011 110 1011 1011 001 0100 0100 110 1100 1100 001 0101 0101 101 1101 1101 010 0110 0110 011 1110 1110 100 0111 0111 000 1111 1111 111 8.3.4 伴随式译码 设发送的码字为 C=（cn – 1,cn – 2. c1,c0），信道产生的错误图样为 E=（en – 1,en – 2.e l ,e 0），则接收码字为 R=C+E=（cn – 1+ en – 1, cn – 2 + en – 2. c1+ e l, c0 + e 0），其中 ci 和 ei均为二进制数字，加法为模 2 加。 译码器的任务就是从 R 中恢复 C，或者说是从 R 中估计 E，如成功恢复，则译码 成功，否则译码错误。 伴随式定义为接收码字与校验矩阵之乘积，即 S=RHT =（C+E）HT =CHT +EHT (8-3-17) ¾ 由（8-1-3）式可知 CHT =0，因此 S=RHT =EHT 。 ¾ 如果没有错误传输，即 E=0，则 S = EHT =0，若有错误传输，即 E≠0，则 S =EHT ≠0。 ¾ 对于确定的编码，H 是已知的，因此仅 S 与信道错误图样 E 有关。如果能从 S 中得到 E，则可以从接收码字中正确恢复发送码字，即 R+E=C+E+E=C。因此将 S 定义为接 收矢量 R 的伴随式或矫正子。线性分组码的一个重要性质是伴随式与错误图样是一一 对应的。 如何从 S 中确定 E，以便完成正确译码；为了能正确检错与纠错，校验矩阵 H 需满足： ①H 中没有全 0 列，否则相应码字位置上的错误就无法影响伴随式，因而无法检测。 ② H 中所有列都是惟一的；因为假如有两列相同的话，那么二者所对应的错误码发生 位置就无法识别。 我们以可纠正一位错误的线性分组码为例来说明伴随式与错误图样的关系。（n,k）码共 有 2k 个有效码字，由于错误图样不能为有效码字（否则无法检错与纠错），因此错误图样属 于 2n-k 空间，错误图样有 2n-k个，这样可以构造出分组码的标准阵列，如表 8-3-2 所示。 表 8-3-2 分组码的标准阵列