信息论与编码民大09-线性分组码

线性分组码分组码的表示（二元分组码）信息码组由k

个信息码元组成，共有2k

个不同的信息码组；信息位

附加

个校验码元，每个校验码元是该信息码组的某些信息码元模2和；校验位或监督位

编码器输出长度为n的码字码字的数目共有2k

；这2k

个码字的集合称为(n,k)

分组码；分组码的基本概念k个信息位r个监督位Cn-1Cn-2...CrCr-1Cr-2...C0t码长n=k+r分组码的结构二进制(n,k)分组码，可用编码空间的序列数为2n个，许用码字数为2k

，其余2n-2k个码字未被选用，称为禁用码组。任一种2k信息集合到二进制序列集合2n的映射都是一种(n,k)码。因此总共可能的编码方案有

种。译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于n*2k

。几乎是不可能译码。引入线性码发现或构造好码是信道编码研究的主要问题。编码方案太多，以至全局搜索是不可能的。现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优。这种约束即要能包含尽可能好的码，又要便于分析，便于译码。线性分组码是最具实用价值的一类码，比如汉明码、循环码、BCH码、RS码等。目前对线性系统的研究远远比非线性系统要充分。线性码的好处可以简化分析：将距离谱变成重量谱。简化译码：随机分组码译码需要2k次长为n的距离计算及比较。线性分组码译码只需要n-k次长为n的矢量内积和一张大小为长2k宽2n-k的表。说明约束起了作用，但还不够，需要进一步引入其它约束对信道编码的一般要求是：①纠错检错能力强；②信息传输率高；③编码规律简单，实现设备简单且费用合理；④与信道的差错统计特性相匹配。线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由k位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n重(n>k)码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。信息码组长k位，有2k个不同的信息码组，则应该有2k个码字与它们一一对应。

概念线性分组码：通过预定的线性运算将长为k位的信息码组变换成n位的码字(n>k)。由2k个信息码组所编成的2k个码字集合，称为线性分组码。码矢：一个n重的码字可以用矢量来表示C=(Cn－1,Cn－1,…,C1,C0)所以码字又称为码矢。(n,k)线性码：信息位长为k，码长为n的线性码。编码效率/码率：R=k/n。它说明了信道的利用效率，R是衡量编码性能的一个重要参数。注：用编码提高通信系统的可靠性，是以降低有效性为代价换来的。一致监督方程：在k个信息码元之后附加r(r=n－k)个监督码元，使每个监督元是其中某些信息元的模2和。例k=3,r=4构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算一致监督方程和一致监督矩阵信息码组(101)，即C6=1,C5=0,C4=1由线性方程组得：C3=0,C2=0,C1=1,C0=1即信息码组(101)编出的码字为(1010011)。其它7个码字如表。一致监督矩阵：将监督方程写成矩阵形式，得：

H

CT=0T或

C

HT=0CT、HT、0T分别表示C、H、0的转置矩阵。系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定令系数矩阵为H，码字行阵列为C一致监督方程和一致监督矩阵一致监督矩阵特性:对H各行实行初等变换，将后面r列化为单位子阵，于是得到下面矩阵(行变换所得方程组与原方程组同解)。监督矩阵H的标准形式：后面r列是一单位子阵的监督矩阵H。H的标准形式还说明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H阵的第一行为(1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。

H阵的r行代表了r个监督方程，也表示由H所确定的码字有r个监督元。为了得到确定的码，r个监督方程（或H阵的r行）必须是线性独立的，这要求H阵的秩为r。若把H阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H阵本身的秩。线性码的封闭性:线性码的封闭性：线性码任意两个码字之和仍是一个码字。因为：若U和V为线性码的任意两个码字，故有HUT=0T，HVT=0T那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V满足监督方程，所以U+V一定是一个码字。线性分组码的生成矩阵线性分组码的生成矩阵:在由(n,k)线性码构成的线性空间Vn

的k维子空间中，一定存在k个线性独立的码字：g1,g2,…,gk,。码CI中其它任何码字C都可表示为这k个码字的线性组合，即G中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字。生成矩阵：由于矩阵G生成了(n,k)线性码，称矩阵G为(n,k)线性码的生成矩阵。线性系统分组码:

通过行初等变换，将G化为前k列是单位子阵的标准形式

线性系统分组码：用标准生成矩阵Gk×n

编成的码字，前面k位为信息数字，后面r=n－k位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样解决了。例:(7,4)线性码的生成矩阵为生成矩阵与一致监督矩阵的关系:由于生成矩阵G的每一行都是一个码字，所以G的每行都满足Hr×nCTn×1=0Tr×1，则有Hr×nGTn×k=0Tr×k

或Gk×nHTn×r=0k×r线性系统码的监督矩阵H和生成矩阵G之间可以直接互换。例:

已知(7,4)线性系统码的监督矩阵为(n,k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(n>k)的码字。利用监督矩阵构造(7,3)线性分组码的编码电路：设码字矢量为C=(C6C5C4C3C2C1C0)码的监督矩阵为线性分组码的编码实现电路根据方程组可直接画出(7,3)码的并行和串行编码电路。汉明距离：(n,k)线性码中，两个码字U、V之间对应码元位上符号取值不同的个数，称为U、V的汉明距离。例：码字U=0011101,V=0100111之间第2、3、4和6位不同。因此，码字U和V的距离为4。最小距离dmin：(n,k)线性码中，任意两个码字间距离的最小值，叫码的最小距离。最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。最小距离越大，抗干扰能力就越强。汉明球：汉明球是以码字C为中心，半径为t，并与C的汉明距离≤t的全体向量集合。任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin

。线性分组码的最小距离、检错和纠错能力汉明重量W：码字中非0码元符号的个数。在二元线性码中，码字重量就是码字中“1”的个数。最小重量Wmin

：线性分组码中，非0码字重量的最小值。最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。

最小距离与检、纠错能力：一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：一个线性码能检出长度≤l个码元的任何错误图样，称码的检错能力为l。纠错能力：线性码能纠正长度≤t个码元的任意错误图样，称码的纠错能力为t。最小距离与纠错能力：(n,k)线性码能纠t个错误的充要条件是码的最小距离为

最小距离与检错能力：(n,k)线性码能够发现l个错误的充要条件是码的最小距离为

dmin=l+1或l=dmin－1

最小距离与检、纠错能力：(n,k)线性码能纠t个错误，并能发现l个错误(l>t)的充要条件是码的最小距离为

dmin=t+l+1或t+l=dmin－1

伴随式和错误检测：用监督矩阵译码：接收到一个码字R后，检验H

RT=0T是否成立：H

RT=0T是否成立是检验码字出错与否的依据。若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；伴随式：S=R

HT或ST=H

RT。如何检测？设发送码矢C=(Cn－1,Cn－2,…,C0)信道错误图样为E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n－1,n－2,…,0。线性分组码的伴随式接收码字R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收码字的伴随式

ST=H

RT=H

(C+E)T=H

CT+H

ET由于H

CT=0T，所以ST=H

ET设H=(h1,h2,…,hn)，其中hi表示H的列。代入上式得到

总结：伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收码字是一个码字；若S≠0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式S是H阵中与错误码元对应列之和。例：(7,3)码接收矢量R的伴随式计算设发送码矢C=1010011，接收码字R＝1010011，R与C相同。若接收码字中有一位错误当码元错误多于1个时伴随式计算电路：伴随式的计算可用电路来实现。以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为根据上式可画出伴随式计算电路，见下页。

标准阵列译码标准阵列：是对给定的(n,k)线性码，将2n个矢量划分为2k个子集的一种方法。译码方法把2n个矢量划分为2k个互不相交的子集，使得在每个子集中仅含一个可用码字；根据可用码字和子集间一一对应关系，若接收矢量Rl

落在子集Dl中，就把Rl

译为子集Dl含有的码字Cl；当接收矢量R与实际发送码矢在同一子集中时，译码就是正确的。线性分组码的译码标准阵列构造方法先将2k个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

个n重中选取一个重量最轻的n重E2放在全0码矢C1下面，再将E2分别和码矢相加，放在对应码矢下面，构成阵列第二行；在第二次剩下的n重中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码矢上，得到第三行；…，继续这样做下去，直到全部n重用完为止。得到下页表格所示的(n,k)线性码的标准阵列。线性码纠错能力与监督元数目的关系：一个可纠t个错误的线性码必须满足上式中等式成立时的线性码称为完备码。即对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的(n－k)个监督码元得到了充分的利用。从多维矢量空间的角度看完备码：假定围绕每一个码字Ci

放置一个半径为t

的球，每个球内包含了与该码字汉明距离小于等于t的所有接收码字R的集合；这样，在半径为t=[(dmin－1)/2]的球内的接收码字数是：因为有2k个可能发送的码字，也就有2k个不相重叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。于是一个纠t个差错的码必然满足不等式如果上式中等号成立，表示所有的接收码字都落在2k个球内，而球外没有一个码，这就是完备码。例：对纠一个错误的(7,4)汉明码，可见，(7,4)汉明码是一个完备码。所有汉明码都是完备码（满足2n－k=2m=n+1）。标准阵列译码=最小距离译码陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的n重作陪集首；这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码字间的距离（等于陪集首）最小；因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；任意n重的伴随式决定于它在标准阵列中所在陪集的陪集首。标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单得