跳转到内容

循环码

维基百科,自由的百科全书

编码理论中,循环码(英语:cyclic code)是一种分组码,每个码字循环移位会得到同样属于该码的另一个码字。它们是拥有便于误差检测与校正的纠错码

若00010111是有效码字,将其右循环移位得到10001011。若该码是循环码,则10001011也会是一个有效的码字。一般来说,在右循环移位会将最低位(LSB)移到最左边的位置,于是变为了最高位(MSB);其他位置会向右移一位。

定义

[编辑]

有限域 上的分组长度n线性码英语linear code。如果对于 C 中的每个码字英语codeword c=(c1,...,cn),由循环移位得到的 中的字 (cn,c1,...,cn-1) 仍是一个码字,则 称为循环码。由于向右循环移一位就相当于向左循环移 n − 1 位,循环码也可以用循环左移来定义。因此如果任何循环移位都不变的线性码 是精确循环码。

循环码对码有一些附加结构约束。它们都是基于伽罗华域,由于其结构性质,循环码对差错控制很有用。它们与伽罗华域密切相关,因此编码和译码算法都方便计算。

例子

[编辑]

举例来说,若 A=n=3,(1,1,0)循环码中包含的码字的集合为

.

它对应于 中由 生成的理想。

注意到 是该多项式环中的不可约多项式,因此该码为不可约码。

该码的幂等为多项式 ,对应于码字 (1,1,0)。

参见

[编辑]

参考文献

[编辑]

延伸阅读

[编辑]

外部链接

[编辑]