循环码

2020/6/27信息与编码1循环码主要内容什么是循环码？循环码的一些性质循环码的构造循环码的编译码循环码的应用2020/6/27信息与编码2什么是循环码？线性分组码的一种，满足线性性。循环性循环码C中的任意码字循环移位k后的码字仍属于C，即若AC，则A(k)C例：{(0000),(1111)}是循环码2020/6/27信息与编码3什么是循环码？图中所示的(7，3)码是循环码。c1=0000000c3=0101110c8=1011100c7=0111001c2=0010111c4=1001011c5=1100101c6=1110010000010111011001100110101UCf:=UC2020/6/27信息与编码4什么是循环码？例如c3=(0101110)循环移一位是c8=(1011100)，再循环移一位是c7=(0111001)。2020/6/27信息与编码5什么是循环码？c2c3c8c7c6c5c4c1(a)(7,3)循环码的码字循环关系2020/6/27信息与编码6什么是循环码？请注意“线性”和“循环”本身是不相干的事情，我们对循环码的定义已经包括了线性特性。在下页表所列的4种(3,2)码中，只有第一种符合我们对循环码的定义。2020/6/27信息与编码7什么是循环码？信息线性，循环线性，不循环非线性，循环非线性，非循环00000000001011010110110101101011011110000111101100000111循环码与非循环码2020/6/27信息与编码8码多项式为了方便分析循环码，我们把n比特组对应为一个多项式。(1001011)对应(0010101)对应120,,,nnaaaa121210nnnnaxaxaxaxa631xxx421xx2020/6/27信息与编码9码多项式代数中有下面这样一个定理：任意给定多项式a(x)、f(x)，存在唯一的多项式q(x)及r(x)，使得可以表示成其中r(x)或者是0，或者是一个次数低于f(x)的非0多项式。称q(x)是a(x)除以f(x)的商式，r(x)是a(x)除以f(x)的余式。axqxfxrx2020/6/27信息与编码10码多项式记a(x)除以f(x)的余式为。如果，则称a(x)能被f(x)整除。modfxaxmod0fxax2020/6/27信息与编码11码多项式下面是一些多项式运算的例子，注意系数运算是上的运算。2GF2211nnxx12111nnnxxxxx73321111xxxxxx2488421111xxxx2020/6/27信息与编码12码多项式码字的码多项式定义为1210...nnCcccc11212100...nnninniicxcxcxcxccx2020/6/27信息与编码13循环性码字的循环左移1位为其码多项式循环左移k位为1210...nnCcccc12101...nnCcccc1101......knknnkCccccc1122101...nnncxcxcxcxc1111101......knkkknknnkcxcxcxcxcxc2020/6/27信息与编码14循环性定理一、证明：用归纳法K=1时，mod1kkncxxcxx11221011212101111101.........1mod1nnnnnnnnnnnnnnncxcxcxcxccxcxcxcxccxxcxcxccxxcxx2020/6/27信息与编码15设k时成立，则显然k+1成立。证毕2020/6/27信息与编码16循环码的性质定理二、（n，k）循环码中存在且仅有一个非零的最低次多项式，该多项式称为生成多项式g(x)，其他所有许用码字均可以表示成c(x)=u(x)g(x)证明：假设（n，k）循环码中存在两个最低次多项式g1(x),g2(x)，则根据循环码的线性性g’(x)=g1(x)+g2(x)是（n，k）中的码多项式。但g’(x)的次数小于g1(x),g2(x)，与假设矛盾。2020/6/27信息与编码17设则根据循环性和线性性也是（n，k）循环码中的许用码组。（n，k）中的任意码字c(x)可写成b(x)是次数小于r-1的多项式，a(x)是次数不大于n-r的多项式121210...rrrrgxgxgxgxg01...nrnrfxffxfxgxcxaxgxbx循环码的性质2020/6/27信息与编码18b(x)=c(x)+a(x)g(x)，由于c(x)，a(x)g(x)都是许用码组，因此b(x)也是许用码组，因此如果b(x)0，则我们找到了一个比g(x)次数低的码字，这与假设g(x)是最低次数矛盾，因此b(x)=0。即循环码中的任意c(x)，有c(x)=a(x)g(x)。循环码的性质2020/6/27信息与编码19定理二告诉一个信息：即（n，k）循环码的构造就是要找到生成多项式g(x)。推论：由于c(x)=a(x)g(x)，且(n,k)循环码的c(x)个数为2^k个，因此a(x)的最高次数为k-1,g(x)的次数为n-k。2020/6/27信息与编码20定理三（生成多项式的构造）（n,k）循环码的生成多项式g(x)是（x^n+1)的次数为n-k的因子。证明：由定理二推论知g(x)的次数为n-k。设则10()...nknkgxgxgxg110...111()()mod1knnknknnxgxxgxgxxcxcxx2020/6/27信息与编码21由定理二，c(x)=a(x)g(x)因此，即g(x)是x^n+1的因子。(())()1knaxxgxx2020/6/27信息与编码22生成多项式例：(7,4)循环码C的生成多项式是，对应码字(0001011)。(7,3)循环码的生成多项式是，对应码字(0010111)。重复码的生成多项式是，对应码字(111…11)。偶校验码的生成多项式是，对应码字是(000…011)。31gxxx421gxxxx121nnxxx1x2020/6/27信息与编码23生成多项式(n,k)循环码的生成多项式g(x)的特性g(x)0次项是1，即其形式是，其中r是g(x)的次数g(x)是唯一的，即C(x)中除0多项式以外次数最低的多项式只有一个。C(x)中的任何一个多项式都能被g(x)整除。任何次数小于n，并能被g(x)整除的多项式都属于C(x)。g(x)的次数是n-kg(x)是的一个因子。1111rrrxgxgx1nx2020/6/27信息与编码24生成多项式推论(n，k)循环码中除了全0码字外，不存在另外一个码字有连续k个0。证明：记C为全部码字的集合，假设存在一个非0码字有连续k个0，则它或者形如即k个连0在最高位，或者形如0120000,,,,,,,innjkcccccc个1200,,,,000,,,nnjikcccccc个2020/6/27信息与编码25生成多项式即k个连0不在最高位。如果是后者，则由于循环码的性质知道形如前者的码字一定存在。而c对应的多项式的次数至多是n-1-k，与生成多项式的次数是n-k最低次数矛盾。2020/6/27信息与编码26生成多项式定理:对任意n，如果g(x)是的一个r次因子，则存在一个(n，n-r)循环码，它的生成多项式是g(x)。构造这样一种(n，k)分组码，需要证明这个码是线性分组码，并满足循环性。证明过程略。1nx2020/6/27信息与编码27生成多项式例：可以分解为，用为生成多项式构成(7，6)偶校验码，用或者作生成多项式构成(7，4)循环码，用构成(7，3)循环码，构成(7，1)重复码。不存在(7，2)或者(7，5)的循环码。71x332111xxxxx1x31xx321xx3432111xxxxxx3242111xxxxxx33265432111xxxxxxxxxx2020/6/27信息与编码28生成多项式与生成矩阵循环码是线性分组码，自然也有生成矩阵。设是某个(n,k)循环码的生成多项式，由于，对应k个码字，且它们线性不相关，所以1111nknknkgxxgxgxxgxi1,,1,0ki2020/6/27信息与编码29生成多项式与生成矩阵一定是生成矩阵。也可以把上式写成多项式形式：011011011000000ggggggggggggGknknknknknkn2020/6/27信息与编码30生成多项式与生成矩阵xgxxgxgxxgxxGkk212020/6/27信息与编码31系统码的生成矩阵对于系统码的循环码，其生成矩阵必然具有下面的形式1,11,21,2,12,22,,1,2,100010001nknkkkknkrrrrrrGrrr2020/6/27信息与编码32系统码的生成矩阵其第i（）行对应的多项式是，其中是次数小于的多项式。作为循环码，必然能被生成多项式整除。因此，。这样，写成多项式形式的系统码的生成矩阵为1,2,,ikniiigxxrx12,1,2,1,nknkiiiinkinkrxrxrxrxrnkigxgxmod0niigxxrxmodniigxrxx2020/6/27信息与编码33系统码的生成矩阵注意其中最后一行是。实际上每一行都是对单1的信息比特组作系统码编码的结果。11mod22modmodnngxnngxninigxxxxxGxxxgxmodnknkgxxxgx2020/6/27信息与编码34系统码的生成矩阵例：某(7，4)循环码的生成多项式是，信息分组(1000)、(0100)、(0010)、(0001)的系统码编码结果分别是(1000101)、(0100111)、(0010110)、(0001011)。这个(7，4)码的生成矩阵是31gxxx1000101010011100101100001011G2020/6/27信息与编码35监督多项式与监督矩阵对应由生成矩阵知0TGH1ngxhxxxgxxgxgxxgxxGkk212020/6/27信息与编码36监督多项式与监督矩阵011011011000000ggggggggggggGknknknknknkn2020/6/27信息与编码37监督多项式与监督矩阵10101()()nnkknkkgxhxxgxgxghxhxhX的n-1次,n-2次…1次幂系数都为0011()0001,2,10iinkinknkkghghghinghgh2020/6/27信息与