线性分组码
线性分组码
一、原理：
监督矩阵：
线性分组码(n，k)中许用码组为2k个。定义线性分组码的加法为模二加法，乘法为二进制乘法。即1+1=0、1+0=1、0+1=1、0+0=0；1⨯1=1、1⨯0=0、0⨯0=0、
0⨯1=0。且码组与码组的运算在各个相应比特位上符合上述二进制加法运算规则。
线性分组码具有如下性质(n，k)的性质：
1. 封闭性。任意两个码组的和还是许用的码组。 2. 码的最小距离等于非零码的最小码重。
对于码组长度为n、信息码元为k位、监督码元为r=n-k位的分组码，常记作(n，k)码，如果满足2r-1≥n，则有可能构造出纠正一位或一位以上错误的线性码。
下面我们通过（7，4）分组码的例子来说明如何具体构造这种线性码。设分组码(n，k)中，k=4，为能纠正一位误码，要求r≥3。取r=3，则n=k+r=7。该例子中，信息组为(a6a5a4a3),码字为(a6a5a4a3a2a1a0)。用S1，S2，S3的值与错码位置的对应关系可以规定为如表1所列。
由表中规定可知，当已知信息组时，按以下规则得到三个校验元，即：
⎧S1=a6⊕a ⎪
5⊕a4⊕a2
⎨S2=a6⊕a5⊕a3⊕a1 ⎪⎩S3
=a6⊕a4⊕a3⊕a
0在发送端编码时，信息位a6，a5，a4和a3的值决定于输入信号，因此它们是随机的。监督位a2，a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上三式中S1，S2和S3的值为零（表示编成的码组中应无错码）。由上式经移项运算，解出监督位： ⎧a2=a6⊕a5⊕a
⎪
4
⎨a1=a6⊕a5⊕a3 ⎪⎩a0
=a6⊕a4⊕a
31.1）1.2）（式
（式
给出信息位后，可直接按上式算出监督位，其结果见表2。
接收端收到每个码组后先按式(1.1)计算出S1，S2和S3，再按表1判断错码情况。
表2 （7，4）线性分组码（海明码）
给出（7,4）线性分组码有24即16个许用码字或合法码字，另有27-24个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。
按上述方法构造的码称为海明码。表2所列的(7,4)海明码的最小码距d0=3，因此，这种码能纠正一个错码或检测两个错码。海明码的编码效率等于
k/n=(
2r
-1-r)/(
2r
-1)=r-1/(
2r
-1)
=1-r/n
当n很大时，则编码效率接近1。可见，海明码是一种高效码。
现在再来讨论线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线性方程的码，式(1.1)就是这样一组线性方程的例子。现在将它改写成：
⎧1∙a6⊕1∙a5⊕1∙a4⊕0∙a3⊕1∙a2⊕0∙a ⎪
0=0
⎨1∙a6⊕1∙a5⊕0∙a4⊕1∙a3⊕0∙a2⊕0∙a0=0 ⎪⎩
1∙a6⊕0∙a5⊕1∙a4⊕1∙a3⊕0∙a2⊕1∙a0=0
式（1.4）可以表示成如下矩阵形式：
⎡a6⎤
⎢⎥⎢a5⎥
⎡1110100⎤⎢a4⎥⎡0⎤
⎢⎢1101010⎥⎢⎥⎥⎢a⎢⎥
3⎥=⎢0⎥ （模2） （式1.5） ⎢⎣1
1
1
1⎥⎦⎢⎥⎢a2⎥⎢⎣0⎥⎦⎢a1⎥⎢⎣a0⎥⎦
上式还可以简记为：
1.3）1.4）（式
（式
H∙A
T
=OT
或 A∙H
T
=0 其中
=[a6a5a4a3a2a1a0]
⎡1110100⎤
H=⎢⎢1
101010⎥⎥ ⎢⎣1
1
1
1⎥⎦
O=[0
0]
右上标“T”表示将矩阵转置。
将H称为监督矩阵，编码时只要监督矩阵给定，编码时监督位和信息位的关系就完全确定。由式（1.4）、式（1.5）都可看出，H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中的“1”的位置表示相应码元之间存在的监督关系。式（1.5）中的H矩阵可以分为两部分：
⎡1
110：100⎤
H=⎢⎢1
101：010⎥
⎥=[PIr] ⎢⎣1
1
1
：0
1⎥⎦
式中，P为r⨯k阶矩阵，Ir为r⨯r阶单位方阵，将具有[PIr]形式的H矩阵称为典型监督矩阵。
由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式，从而也得不到r个独立的监督位。若一行矩阵能写成典型的矩阵形式[PIr]，则其各行一定是线性无关的。因为容易验证[Ir]的各行是线性无关的，故[PIr]也是线性无关的。 生成矩阵：
类似于式（1.4）改变成式（1.5）中矩阵形式那样，式（1.5）也可以改写成：
⎡a2⎤⎡1
110⎤⎡a6⎤
⎢⎢a⎥⎢1⎥=⎢1101⎥⎢⎥⎢a⎥5
⎥ ⎢⎣a0⎥⎦⎢⎣1
1
1⎥⎢a⎦⎢4
⎥
⎣a⎥3⎦
或者
⎡111⎤⎢
[aa110
⎥2
a1
a0]=[a6
a5a43]⎢⎥⎢101⎥=[a
6
a5a4
a3]Q
⎢⎣0
1
1⎥⎦
（式1.6）
（式1.7）
（式:1.8）
（式1.9）
式中，Q为一个k⨯r阶矩阵，即它为P的转置，即
Q=PT
式（1.9）表明，信息位给定后，用信息位的行距乘矩阵Q就产生出监督位。 将Q的左边加上一k⨯k阶单位方阵就构成一矩阵G，即
⎡1000111⎤⎢ G=[I0
100110⎥kQ]=⎢
⎥⎢0010101⎥ ⎢⎣0
1
1
1⎥⎦
G称为生成矩阵，因为由它可以产生整个码组，即有
[a6
a5a4a3a2a1
a0]=[a6
a5a4
a3]∙G
或者
A=[a6
a5a4
a3]∙G
因此，如果找到了码的生成矩阵G，则编码的方法就完全确定。具有[IkQ]形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位不变，监督位附加于其后，这种码称为系统码。
与H矩阵相似，也要求G矩阵的各行是线性无关的。因为由式（1.13）可以看出，任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可组合出2k种不同的码组A，它恰是有k为信息位的全部码组；若G的各行有线性相关的，则不可能由G生成2k种不同码组了。实际上，G的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余的码组。 码的距离
两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离dmin定义为dmin=min{d(ci,cj)，i≠j,ci,cj∈(n,k)}，两个码字之间的距离表示了它们
之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。 线性分组码的纠检错能力
对于任一个(n,k)线性分组码，
（1）若要在一个码字内检测出e个错误，则要求码的最小距离d≥e+1； （2）纠正t个错误，则要求码的最小距离d≥2t+1；
（3）纠正t个错误同时检测e(e≥t)个错误，则要求d≥t+e+1。
（式1.10）
（式1.11）
（式1.12）
（式1.13）
伴随式与译码
一般说来，式（1.13）中A为一n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即
B=[bn-1bn-2 b0]
则发送码组和接收码组之差为：
B-A=E（模2）
它就是传输中产生的错码行矩阵，其中 E=[en-1en-2 e0] 其中
e⎧0
当bi=aii=⎨
⎩1
当bi≠ai
因此，若ei=0，表示该位接收码元无错；若ei=1，则表示该位接收码元有错。式（1.15）也可以改写成：
B=A+E
接收端译码时，可将接收码组B代入式（1.6）中计算。若接收码组中无错码，即E=0，则B=A+E=A，把它代入式（1.6）后，该式仍成立，则有
B∙H
T
=0 当接收码组有错时，E≠0，将B代入式（1.15）后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另一许用码组则式（1.18）仍能成立。这样的错码错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于零。假设这时式（1.18）的右端为S，即
B∙H
T
=S 将B=A+E代入式（1.19）中可得
S=(A+E)∙H
T
=A∙H
T
+E∙H
T
由式（1.6）知，A∙H
T
=0，所以
S=E∙H
T
式中，S称为伴随式或校正子。它与式（1.1）中的S相似，有可能利用它来指示错码位置，这一点可以直接从式（1.20）中看出，式中S只与E有关，而与A无关，这就意味
（式1.14）
（式1.15）
（式1.16）
（式1.17）
（式1.18）
（式1.19）
（式1.20）
着S与错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。
二、编解码流程：
由H与G的分块表示的矩阵形式 H=[P In-k] G
=
[Ik
Q
]
P=QT Q=PT
则有
G∙H
T
=0 或 H∙G
T
=0 已知生成矩阵
⎡1000111⎤⎢G=⎢
0100110⎥⎥⎢0010101⎥ ⎢⎣0
1
1
1⎥⎦
根据以上几式可求出监督矩阵
⎡1110100⎤
H=⎢⎢1
101010⎥⎥ ⎢⎣1
1
1
1⎥⎦
最后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵。即
C=mG
所有的编码情况如表1所示。
（式2.1）
（式2.2） （式2.3） （式2.4）
（式2.5）
（式2.6）
三、核心程序块：
（7,4）码编译器整体程序： #include #include void main()
{ /*G：生成矩阵 H：监督矩阵 HT：监督矩阵对应的转置矩阵*/
/*M：输入信息序列 C：编码输出序列 Input：输入接收码序列 B：译码输出序列 int Q,N;/*定义开始*/
int i,j,s,r,k,t,p,u,m;
S：伴随式*/
int G[4][7]={{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}};
int IR[3][3]={{1,0,0,},{0,1,0},{0,0,1}};
int H[3][7], C[10][7],M[10][4],B[20][7],Input[100],HT[7][3],P[10],S[100][3];/*定义结束*/ printf("\n您好！欢迎使用线性分组码编译器！\n");
printf("\n\n本编译器针对（7，4）码，所采用的生成矩阵G=\n"); for(i=0;i
printf("编译码过程都是针对二进制码组，除了系统要求选择功能，其他情况下禁止输入除0，1以外
for(j=0;j
printf(" %d",G[i][j]);
printf("\n");
的数。请在使用的过程中严格按照编译器要求的格式输入数据。\n\n");
printf("现在请输入您所选择的编译器所对应的序号,按回车键继续:\n"); printf("\n1.编码器 2.译码器 3.退出\n"); printf("\n我选择："); scanf("%d",&Q); if(Q==0)
Q+=4;
while(Q) {
if(Q==1||Q==2||Q==3)break; else { } }
while(Q==1||Q==2||Q==3)
{
if(Q==1)/*编码程序*/
printf("对不起，您输入有误，请重新输入"); scanf("%d",&Q);
scanf("%d",&N);
printf("\n\n请输入您需要编码的%d组四位二进制信息组,码组间用空格分开，按回车
键确认。\n",N);/*输入信息码*/
}
else if(Q==2)/*译码程序*/ {
for(i=0;i
for(j=0;j
scanf("%1d%1d%1d%1d",&M[i][3],&M[i][2],&M[i][1],&M[i][0]);/*求监督码*/ for(i=0;i
C[i][2]=M[i][3]^M[i][2]^M[i][1]; C[i][1]=M[i][3]^M[i][2]^M[i][0]; C[i][0]=M[i][3]^M[i][1]^M[i][0]; }
for(j=0;j
for (i=6;i>2;i--)/*输出编码结果*/
C[j][i]=M[j][i-3];
printf("\n您所输入的信息组编码结果c="); for(j=0;j
for(i=6;i>=0;i--) printf("%d",C[j][i]);
printf("\n\n");
printf("\n接下来您想：\n\n");/*选择功能*/ printf("1.用编码器 2.用译码器 3.退出\n\n"); printf("我想："); scanf("%d",&Q);
}
for(j=4;j
H[i][j]=IR[i][j-4];
printf("\n监督矩阵H=\n");/*输出监督矩阵*/ for(i=0;i
while(t!=2)/*输入接收码组*/ {
p=1;
printf("\n请输入总位数为7的倍数的接收码组,每位用空格隔开，每组位数为7for(j=0;j
printf(" %d",H[i][j]);
printf("\n");
的倍数,以十进制2作为结束标志!按回车键确认\n");
while(p) {
for(i=0;;i++) { } k=i%7;
if(k==0){p=0;t=2;} else {
p=1; k=-k+7;
printf("您接收到的码组丢失了%d位,系统不能判断丢失位的具体位scanf("%d",&Input[i]); if(Input[i]==2)break;
置，请重新输入\n",k);
} u=i/7; i=0; for(r=0;r=0;j--,i++) B[r][j]=Input[i]; } } for(i=0;i
} } s=0; printf("\n\n伴随式S=\n");/*输出伴随式*/ for(j=0;j=0;i--) printf(" %1d",S[j][i]); printf("\n");} printf("\n"); for(i=0;i=0;j--) printf("%1d",B[i][j]); printf("请您再次确认！"); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 2: { B[i][0]=1^B[i][0]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--;
} printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 3: { } B[i][1]=1^B[i][1]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 4: { } B[i][3]=1^B[i][3]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 5: { B[i][2]=1^B[i][2];
} i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 6: { } B[i][4]=1^B[i][4]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 7: { } B[i][5]=1^B[i][5]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; case 8:
} } } B[i][6]=1^B[i][6]; printf("\n\n您接收的第%d个码组有错误，正确的码组应为：",++i); i--; for(j=6;j>=0;j--) printf("%1d",B[i][j]); printf("译出的信息序列为："); for(j=6;j>2;j--) printf("%d",B[i][j]);break; printf("\n\n总的译码结果为："); for(i=0;i2;j--) printf("%1d",B[i][j]); printf("\n\n接下来您想：\n\n");/*继续选择功能*/ printf("1.用编码器 2.用译码器 3.退出\n\n"); printf("我想："); scanf("%d",&Q); if(Q==0) Q=Q+4; while(Q) { } if(Q==1||Q==2||Q==3)break; else { } printf("对不起，您输入有误，请重新输入"); scanf("%d",&Q);
} } else if(Q==3)/*退出程序*/ { } printf("\n谢谢您的使用，欢迎再次使用！\n"); Q=0;