的最小多项式.ppt

State Key Laboratory of Integrated Services Networks 循 环 码 （III） 内容 用生成多项式的根定义循环码 BCH码 RS码 用生成多项式的根定义循环码 研究表明，生成多项式有重根的码一般都要比无重根的码差，因此只考虑无重根的码，或构造无重根的多项式。 循环码的编码问题转化为：如何由给定的根来得到生成多项式g(x)? GF(q)上多项式xn-1无重根的充要条件是n与q互素。因此对GF(2)而言，充要条件即为n为奇数。 用生成多项式的根定义循环码 给定r个根 , 每个根都有级数ei，即 ，则码长为所有级的最小公倍数 每个根都可有一个最小多项式mi(x)，而生成多项式则是所有根的最小多项式的最小公倍式 同一共轭根系的根在设计生成多项式时的效果相同，只需考虑其中一个； 用指定的根求生成多项式 给定必含根 ，求生成多项式g(x)时，要先找出各个根的最小多项式（可计算或查表），然后求它们的公倍式。 由于共轭根系的最小多项式相同，需先要找出必含根中包括哪几个共轭根系 Example 1 求以GF(24)中的?, ?2, ?3, ?4, ?5,为根的二进制循环码。 ?, ?2, ?4, ?8是15级元素，组成一共轭根系，且有 ?3, ?6, ?9 , ?12是5级元素，组成一共轭根系，且有 ?5是3级元素，且有 因此， Example 2 GF(211)中，?为本原元，令?=?89，求以?、?2、?3、?4为根的二进制循环码。 ?的级数为211-1=2047=89?23，?23=(?89)23=1，因此?的级为23，如果以?为根，则它的共轭根系也为根：?、?2、?4、?8、?16、?32=?9、?18、?36=?13、?26=?3、?6、?12。 由于所要求的其它必含根?2、?3、?4都包括在这个共轭根系中，它们有相同的最小多项式 g(x)=?m(x) =(x-?)(x-?2) (x-?4) (x-?8) (x-?16) (x-?9) (x-?18) (x-?13) (x-?3) (x-?6) (x-?12) = x11 + x9 + x6 + x5 + x4 + x2 + 1 这部是著名的Golay码，能纠3个错，是一种完备码。（上面的化简中要用到m(?)=0和?=?89 ） Example 2 (Continued) 由生成多项式根定义的校验矩阵 若g(x)有r个不相等的根，则每个根必为每个码多项式的根，可将所有根代入是否为零来验证是否为码多项式； 也可由此得到循环码的校验矩阵。 （此处的运算是在扩域GF(qm)上的） 由生成多项式根定义的校验矩阵 BCH码 用GF(qm)中的n级元素?的?-1个连续幂次为根的多项式生成的循环码称为q进制BCH码。它的自由距不小于?。如果根集中有本原元,则码长n=qm-1，称为本原BCH码；否则，称为非本原BCH码 对任何正整数m和t，一定存在一个二进制BCH码，它以?, ?3, …, ?2t-1,为根，其码长n＝2m-1或是2m-1的因子，能纠正t个随机错误，校验位数目至多为deg(g(x))=mt个 Example 求码长n=21,纠2个随机错误的BCH码 因为26-1=21×3，所以GF(26)是含有21级元素的最小域 设?∈ GF(26)是本原域元素，且x6+x+1是的根。令?=?3 ，则?的级为21。要求纠正2个错误，则g(x)以?、?3为根， ?=?3的最小多项式 ?3 =(?3)3 =?9的最小多项式 所以 得到一个[21, 12, 5]非本原BCH码 RS码 GF(q)上的码长N=q-1的本原BCH码称RS码 RS码的符号域与根域相同 RS码生成多项式g(x)=(x-?m0) (x-?m0+1)…(x-?m0+?-2)，常取m0=1。其码距为?。即生成的码为(n, k, d)=(q-1, q-?, ?)。因此RS码被称为极大最小距离可分码（MDS）。 RS码的设计距离?和实际距离D是一致的 Example 设码的符号取自 GF(q)= GF(23)中 的元素， ?∈ GF(23) 是本原域元素， 它是x3+x+1的根， 构造D=5的RS码。 GF(23)的元素见右图 Example (Continued) D=5?以?, ?2 , ?3, ?4为根，因此 生成GF(23)上的八进制[7, 3, 5]本原BCH码，也就是[7