扩展码
计算机科学领域术语
长度为q的q进制里德-索罗门码,这样的码叫做扩展码。该码可纠正t=(n-k)/2 个符号错误,且既可以将它看做是对可以纠正t一1个错误、检测t个错误(扩展)的码添加一个奇偶校验,还可以将它看做是对可以纠正t个错误的码加上一个额外的信息符号。
定义
(n,k)分组码都是纠正单个错误的。假设出现两位错,且错误模式为和,则错误伴随式是H的第i列和第j列相应位按模2求和的结果。因为H的各列互不相同,故,所以有错。但是,它可能与第k列相同,即。这时,也就是说,如果错了两位,不仅不能正确译码,而且也发现不了错误,这是人们不希望的。
例如(7,4)码的校验矩阵为
若第5位和第6位有错,则伴随式为
它恰好与第3列相同。这时,就将错误模式0000110误认为0010000,于是,就将实际无错的第3位错纠了。
所以,上述由H矩阵构成的码,只能纠正单个错误,而不能发现两个错误,当然更谈不上纠正两个错误了。为了能纠正一个错误,又能够发现两个错误,可以在纠单错码的基础上加以扩展,使构造的H矩阵保证任意3列线性无关。
构造长度为q的q进制里德-索罗门码,这样的码叫做扩展码。该码可纠正t=(n-k)/2个符号错误,且既可以将它看做是对可以纠正t一1个错误、检测t个错误(扩展)的码添加一个奇偶校验,还可以将它看做是对可以纠正t个错误的码加上一个额外的信息符号。
扩展码不是循环码,但是可以用频域技术对其进行编码和解码。这种码的特性相对来说易于理解,解码方法的逻辑是其属性的有效证明。
分类
单拓展码
示例:要想构造可纠正一个错误、检测两个错误的长度为7、GF(8)上的里德一索罗门码,我们可以使用,信息进行系统编码后,成为。位置3的傅立叶变换为。
所以最后的码字为。
我们在位置7和位置5上生成两个错误,接收序列就变成。序列。的校正子多项式是。
位置4的校正子是0。尝试纠正单个错误,则产生连接多项式,且位置2的校正子分量得到了正确的预测。因此,位置7上的符号就不再需要了。错误值就是的值,即,所以收到的(7,4)码的码字可以被纠正成,前4个符号是信息。
另外,我们也可以在位置5和位置3上制造两个错误,那么接收到的序列就是,的校正子多项式是。
位置3的值是。纠正单个错误的连接多项式是,但是它不能正确地预测下一个匀量。所以我们假设边缘频率是正确的,并将它加到计算出的上去,得到纠正两个错误的码的校正子。双错误纠正的关键方程为:,。
消去,得到,。它的根是和,表明错误在位置5和位置3上。
双拓展码
示例:我们考虑GF(8)_E的(9,5)里德一索罗门码的情形。在这个例子中,我们有一个由5个符号组成的信息序列。将第一个和最后一个符号作为边缘符号对待,在频域中将它们分别置于位置3和位置0。这样,我们便从纠正单个错误的里德一索罗门码的频谱开始:。反向变换将给出(7,5)里德一索罗门码的码字:。
将两个额外的信息符号加到码字的两端,构成(9,5)里德一索罗门码字
下面假设在位置8和位置5上产生了错误,这样便产生接收序列
先将附加的信息从序列中去除,使得变换为。
向下的3阶项并没有作为校正子析出,而附加的符号则加到了合适的点上,得到。校正子中的各项会随着阶数的增加而增的倍数,表明出现了单个错误,且关键方程的解为。因此,错误序列的谱就是。
当它与R(z)相加时得到。
解码得到了正确的实现,且所有的信息都可以直接从c(z)中得到。
参考资料
最新修订时间:2024-06-06 11:50
目录
概述
定义
参考资料