信息论与编码第6章(2)

信道编码1

6.3线性分组码2

线性分组码3G

[gk

1,gk

2

1

0]

,.....g,g

T

线性分组码的码空间C

是由

k

个线性无关的基底

gk-1,，．．．g1

，g0

张成的k维n重子空间，所有码字都可写成k个基底的线性组合，即

c

=

mk-1

gk-1+…+

m1

g1+m0

g0如果gi表示第i个基底，并写成行矩阵的形式

gi

[gi(n

1),gi(n

2),.......gi1,gi0,]k个基底可以排列成k行n列的形式，如下所示：.....

g(k

1)1.....

............

g11.....

g01

g(k

1)(n

1)

.....

g1(n

1)

g0(n

1)g(k

1)0

.......

g10

g00

6.3.1生成矩阵和校验矩阵4

码空间中任何一个码字都可以写成基底的线性组合，即：

C

[cn

1,cn

2,.....,c1,c0]

mk

1gk

1

mk

2gk

2

......

m1g1

m0g0

mG•

当信息元确定后，码字仅由G矩阵决定，因此我们称这

k×n

矩阵G为该(n,k)线性分组码的生成矩阵。•

如果已知线性分组码的生成矩阵，则任何一个k位信息

组对应的码字都可以由mG运算得到。生成矩阵5•

(n,k)线性分组码共有多少个码字?问题答：2k个码字。6

•

想要保证

(n,k)线性分组码能够构成k维n重子空间，G

的 k个行矢量gk-1,…,

g1,

g0必须是线性无关的，只有这样 才符合作为基底的条件。•

由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定 等于k。•

由于基底不是唯一的，所以G也就不是唯一的。•

不同的基底有可能生成同一码集，但因编码涉及码集和 映射两个因素，码集一样而映射方法不同也不能说是同 样的码。生成矩阵G(k×n)的特点7

已知(7,4)线性分组码的生成矩阵为

如果输入的四位信息组为m

[0,1,1,0]时，其对应的码字为：举例8

(n,k)码的任何生成矩阵都可以通过行运算（不改变码集，

只改变映射规则）简化成“系统形式”

。Ik是k×k单位矩阵，P是k×(n-k)矩阵。系统形式的生成矩阵

G

=

[Ik

P

]

=

1

0

0p(k

1)0

p10

p00

p(k

1)(n

k

1)

p1(n

k

1)

p0(n

k

1)0

01

0

0

0

1

p(k

1)1

p11

p019

•

前k位由单位矩阵Ik决定，等于把信息组m原封不

动搬到码字的前k位；•

其余的n-k位叫冗余位或一致校验位，是前k个信

息位的线性组合。•

这样生成的（n,k）码叫做系统码。•

若生成矩阵G不具备系统形式，则生成的码叫做

非系统码。•

系统化不改变码集，只是改变了映射规则。系统码10已知(7,3)线性分组码的生成矩阵为

如果输入的三位信息组为m

[0,1,1]时，其对应的码字为：

特点：

码字的前面k位就是信息组中的k位，而后面的校验

位为信息组的线性组合。系统码11

•

n维n重空间有相互正

交的n个基底•

选择k个基底构成码

空间C•

选择另外的(n-k)个基

底构成空间D•

C和D是对偶的n维n重空间V

k维k重信息组空间m

k维n重

n-k维码空间

n重D

C

H

G空间构成12

•

将D空间的n-k个基底排列起来可构成一个(n-k)×n矩

阵，称为校验矩阵H，也称监督矩阵。用来校验接收

到的码字是否是正确的；

•

即：若c为码空间C中的任意码字，则

若不满足此等式，则c必定不是码空间C中的码字。校验矩阵13

•

G是(n,k)码的生成矩阵，H是它的校验矩阵；

•

H是(n,n-k)对偶码的生成矩阵，它的每一行是

对偶码的一个码字。

G则是它的校验矩阵。

•

GHT=0

，H＝[－

PT

In-k

]，二进制时，负号可

省略。校验矩阵14

校验矩阵与生成矩阵的关系15某线性分组码，其生成矩阵是求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射

关系。(3)计算系统码的校验矩阵H。若收码r

=

[100110],

检

验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。

111010

①G=

110

0

0

1

②

011101

③例6-216码集与映射关系信息000001010011100101110111

码字000000011101110001101100111010100111001011010110系统码字

000000

001011

010110

011101

100111

101100

110001

111010例6-217

二元(6,3)线性分组码编码器输入输出m0

m1

m2

c0

c1

c2例6-218•下面是某线性二元码的全部码字：•••••⑴

求n,

k的值；⑵

构造这码的生成矩阵G；⑶

构成这码的一致校验矩阵H。C1

000000

C2

001111C3

010001C4

011110C5

100011C6

101100C7

1110010C8

111101举例19mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)(n,k)信道定义差错图案E

E＝(en－1,…,e1,e0)＝

R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有E=R

＋

C

及R=C

＋

E6.3.2伴随式与标准阵列译码20因为CHT

=

0所以RHT

＝(C＋E)HT

＝CHT

＋EHT=

EHT如果收码无误：必有R＝C即E＝0，

则EHT=

0

RHT

=

0。如果收码有误：即E

0，

则RHT=

EHT

0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义RHT的运算结果为伴随式S

S

=

(sn-k-1,…,s1,s0)

=

RHT

=

EHT伴随式的定义21?

RHT

=

SR

S

C

=

R＋EE

C只要E正确，译出的码也就是正确的。

•

从物理意义上看，伴随式S并不反映发送的码字是什

么，而只是反映信道对码字造成怎样的干扰。

•

差错图案E是n重矢量，共有2n个可能的组合，而伴随

式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同

的差错图案可能有相同的伴随式。

•

接收端收到R后，因为已知HT，可求出

S＝RHT；如

果能知道对应的E，则通过C

=

R＋E而求得C。伴随式的意义22译码过程框图译码过程23

差错图案E的求解(1)24

•

上述方程组中有n个未知数en－1,…

e1,e0

，却只有n-k

个方程，可知方程组有多解。

•

在有理数或实数域中，少一个方程就可能导致无限多

个解，而在二元域中，少一个方程导致两个解，少两

个方程四个解，以此类推，少n-(

n-k)

=

k个方程导致

每个未知数有2k个解。

•

概率译码：把所有2k个解的重量(差错图案E中1的个

数)作比较，选择其中最轻者作为E的估值。该方法概

念上很简单但计算效率不高。差错图案E的求解(2)25依据：若BSC信道的差错概率是p，则长度n的码中错误概率0个错1个错2个错…n个错概率(1-p)np(1-p)n-1p2(1-p)n-2pn由于p<<

1,

则

(1-p)n>>

p(1-p)n-1

>>

p2(1-p)n-2

>>…>>

pn

出错越少的情况，发生概率越大，E的重量越轻，所以该

译码方法实际上体现了最小距离译码准则，即最大似然译码。

显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果n－k不太大，我们可以预先把不同校正子S情况下的所有方程组都预先解出来，将各种情况下的最大概率译码输出列成一个标准阵列译码表。这样，在实际译码时就不必解方程，只要查译码表就可以了。差错图案E的求解依据26

伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可

以预先把不同S下的方程组解出来，把各种情况下的最大概

率译码输出列成一个码表。这样，在实时译码时就不必再

去解方程，而只要象查字典那样查一下码表就可以了。这

样构造的表格叫做标准阵列译码表。•

表中所列码字是接收到的码字R；•

将没有任何差错时的收码R放在第一行，收码等于发码

R=C(C

Ci,i

=0,1,…2k-1),

差错图案为全零E0=(0,0…0)，伴随

式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。标准阵列译码表的构成27•

在第2到第n+1的n行中差错图案的所有重量为1

(共n个)。•

如果(1+

n)<2n-k，再在下面行写出全部带有2个差错的图

案

(共

n

个)。

2

•

如果总行数(1+n+差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。

n

2)仍然小于2n-k，再列出带有3个

标准阵列译码表的构成28标准阵列译码表29解：(1)构造标准阵列译码表。分别以信息组m=

(00)、(01)

、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2

=

(10111)

、C3

=

(01101)、C4

=

(11010)。

一个(5,2)系统线性码的生成矩阵是

设收码R

=

(10101)，构造标准阵列译码表，译出发码i的估值

cˆ求出校验矩阵：例6-330

列出方程组：

s2

e4h24

e3h23

e2h22

e1h21

e0h20

e4

e3

e2

s1

e4h14

e3h13

e2h12

e1h11

e0h10

e4

e1

s0

e4h04

e3h03

e2h02

e1h01

e0h00

e4

e3

e0

由RHT确定S后，对应的E可以有2k(22=4)个解，究竟取哪一

个作为差错图样E的解?

最简单明了的处理方法是概率译码，即

对所有2k个解的重量(差错图样E中1的个数)进行比较，选择重量

最小的作为E的估值。由于E=R+C，E重量最小，就是R和C的汉

明距离最小。例6-331例6-332S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3

标准阵列译码表33

将接收码R＝10101译码

可选以下三种方法之一译码：

•

直接搜索码表，查得(10101)所在列的子集头是

(10111)，因此译码输出取为(10111)。

•

先求伴随式RHT

=

(10101)

HT

=

(010)

=

S4，确定S4所

在行，再沿着行对码表作一维搜索找到(10101),

最后

顺着所在列向上找出码字(10111)。

•

先求出伴随式RHT

=

(010)

=

S4并确定S4所对应的陪集

首（差错图案）E4=(00010)，再将陪集首与收码相加

得到码字C=R+E4=

(10101)+

(00010)=

(10111)。例6-334对例

6-3的分析

在制定标准阵列译码表的过程中，由S决定差错图案E

时只有前6行真正体现了最大似然译码准则，而第7、8行

的差错图案选择不是唯一的。比如第7行可有(00011)和

(10100)两个选择，如果当时选的不是(00011)而是(10100)，

那么码表第7行就不是现在这样了。那么在译码时最后的

结果也就不一样了。

为什么会出现这种情况呢？

伴随式的个数2n-k与n、k及纠错能力t

有一定的数量关系。例6-335

•

N重码矢c

=

(cn-1,c

n-2,…c1,c0)可与N维矢量空间

XN中的一个点对应，全体码字所对应的点构成

矢量空间里的一个子集

•

发码一定在这个子集里，传输无误时的收码也

一定位于该子集

•

当出现差错时，接收的N重矢量:

–

对应到子集外空间某一点

–

对应到该子集，却对应到该子集的另一点上6.3.3码距、纠错能力、MDC码及重量谱36

dmin=3

t

d=7d=5C1C2C3C4C5•

码集各码字间的距离是

不同的，码距最小者决

定码的特性，称之为最

小距离dmin•

这里dmin=3，纠错能力

是1，检错能力是2码距37dmin

=

min

{w

(C

i)}C

i

C

及C

i

0

•

定理6.1

任何最小距离dmin的线性分组码，其检错能力为

（dmin-1）,

纠错能力t为

•

最小距离dmin表明码集中各码字差异的程度，差异越大越

容易区分，抗干扰能力就越强，是衡量分组码性能的最

重要的指标之一。

•

定理6.2

线性分组码的最小距离等于码集中非零码字的最

小重量纠错能力38于

(n-k+1),

即dmin

(n-k+1)•

定理6.3

(n,k)

线性分组码最小距离等于dmin的充

要条件是：校验矩阵H中有（dmin-1)列线性无关。•

定理6.4

(n,k)

线性分组码的最小距离必定小于等纠错能力39例：

H＝(7，4)线性码

各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k

+1＝4。纠错能力40d0

2t

1

(1)为检测e个错码，要求最小码距

d0

e

1(2)为纠正t个错码，要求最小码距(3)为纠正t个错码，同时检测e个错码，要求最小码距

d0

t

e

1最小码距与检错能力图示41•

（n,k）线性码最小距离dmin的上边界是n-k

我们设计的（n,k）线性码的dmin达到了n-k

达到了设计性能的极点。因此，dmin＝

n-k

为极大最小距离码

(MDC

–

Maximized+1。如果+1，就是+1的码称

minimum

Distance

Code)。(1)

二进制码中，除了将一位信息重复n

次的

（n,1）

码外，不存在其它二进制MDC码；(2)

非二进制码中，MDC码是存在的，如RS码

（reed-solomon)。

MDC码(MaximizedminimumDistanceCode)42•

含义：在码长n的码集里，包含重量为0的码字A0个，

重量为1的码字A1个，-----，重量为n的码字An个。

•

纠错能力t只是说明距离t的差错一定能纠，并非说距

离大于t的差错一定不能纠。（除非完备码）

•

总体的、平均的纠错能力不但与最小距离有关，而且

与其余