第十章线性分组码.ppt

* S’等于H的第二列，说明E=[0 1 0 0 0 0 0] (7,3)码的最小码字重量为3，所以可以纠正1个错误。 * S’=HE’,E=[1 0 0 1 0 0 0]，所以S’是H的第一和第四列之和 * 由于伴随式S=vH’=eH’，根据接收到的矢量v可以求得伴随式S，根据S可以求得所有可能的错误图样e，然后根据最小距离译码（即e的重量最小）原则，可以得到唯一的e，最后c=v-e。 也就是说对于一个伴随式S，有多个可能的错误图样e，对于每个线性方程S=eH’，S为1*(n-k)的矢量，e为1*n的矢量，H‘为n*(n-k)的矢量，求e。所以该线性方程的解有k位可任意取值，对于二进制来说，该方程组有2k个可能的解。要在这2k个可能的解中重量最小的一个作为解。 而伴随式S的个数有2n-k个，也就是说将2n个可能的e根据对应不同的伴随式S分成了2n-k个集合。 每个陪集中2k个矢量。 根据这样的划分，将2n个可能的e排列成标准阵的形式。 标准阵中的第一行为2k个C中的码字。 陪集首对应于2n-k个S=eH’的重量最轻的解。 * 第一行S=e1H’的陪集，以此类推 陪集首就是可纠正错误图样的集合，而各码字所对应的列就是该码字的正确接收区域。 * 见书中186页的表6.5.2 * 只有当错误图样确实为最小重量的错误图样（陪集首）时，才能正确译码。 * V：接收到的码字 * 下面来观察一下采用最小距离译码时的纠错能力。 首先给出这样一个定理。 推论：根据该定理，若矩阵H中任意d-1列线性无关，那么对于d列线性相关，v中对应的分量不为0，这样对应的v的重量是最小的（为d），（其他至少d+1列线性相关，对应v的重量至少为d＋1），所以相应码的最小距离至少为d。 * 向下截取（板书图） * 汉明球在前面提到过，如果两个求相交，相交部分无法正确译码（不知道译为V还是U） 译码错误概率即差错图样中重量大于t出现的概率之和。 * 可以检错但不能纠错的码字是位于两个纠错汉明球之外。（知道错误，但是不能纠正） V可以纠错的边缘和U可以检错的边缘至少相差1，否则V的纠错和U的检错形成的汉明球相重合，重合部分无法知道到底是译作V还是U出错后形成的码字。 * 伴随式译码 举例：(7,3)码接收矢量 R 的伴随式计算. 设发送码矢C=1010011，接收码字R＝1010011，R与C相同。 * 伴随式译码 若接收字中有一位错误,设发送码矢C=1010011，接收码字R＝1110011，伴随式 * 伴随式译码 当码元错误多于1个时,设发送码矢C=1010011，接收码字R＝0011011，伴随式 * 伴随式译码 将2n个可能的向量分为2n-k个集合，集合中每个向量的伴随式相同，这样的集合称为陪集 选择陪集中重量最轻的向量作为陪集代表，称陪集首。 1.s=0的陪集，即码C中的元素排第一行，c=(00…0)排最左边，计e0. 2.从其余的元素中选重量最轻的元素e1,并与码C中的元素相加，得到的元素分别列于相应的码字下面。 3.从剩下的元素中任取一个重量最轻的，按相同方式构成第三行，依此类推… * 伴随式译码 伴随式 陪集首 陪集 * 伴随式译码 (6,3)码的标准阵 陪集首 伴随式 * 伴随式译码 第l个陪集首的重量 重量为i的陪集首的数量 BSC下，二元线性码正确译码的概率： * 伴随式译码 译码步骤： 计算接收矢量的伴随式 由伴随式确定陪集首 将陪集首作为错误图样e 将v译为c=v-e * 最小距离和纠错能力 Th. v属于码字集合的充要条件是v的非零码元与H相应列的乘积之和为0。 推论：若矩阵H中任意d-1列线性无关，相应码的最小距离至少为d。 * 最小距离和纠错能力 1.最小距离与纠错能力：(n,k) 线性码能纠t个错误的充要条件是码的最小距离为 [证明]：设码C的最小距离为dmin,以码字为中心，以t为半径的球应不相交。反证若相交，设V为其中元素，C1,C2为两相交球的码字，有三角不等式。 d(C1,C2)≤d(C1,V)+d(V,C2)2t≤dmin-1 与码的最小距离为dmin矛盾，固能纠正t个错误。 * 最小距离和纠错能力 如图：如果接收字R中错误个数t’≤t，那么接收字R和发送字V间距离≤t，而与其它任何码字间距离都大于t，按最小距离译码把R译为V。此时译码正确，码字中的错误被纠正。 几何意义： 译码错误概率： * 最小距离和纠错能力 2.最小距离与检、纠错能力： (n,k) 线性码能纠 t 个错误，并能发现 l 个错误 (l t) 的充要条件是码的最小距离为 dmin≥t+ l +1 几何意义： * 最小距离和纠错能力 当 (n,k) 线性码的最小距离 dmin 给定后，可按实际需要灵活安排纠