基于VC的BCH码迭代译码算法实现.doc

第 19 卷第 5 期哈尔滨师范大学自然科学学报NATURAL SCIENCES JOURNAL OF HARBIN NORMAL UNIVERSITYVol . 19 , No . 5 2003基于 VC 的 BCH 码迭代译码算法实现王建华郑坤张军( 哈尔滨师范大学)【摘要】 在现代通信系统中 ,纠错码技术是实现可靠通信的基本方法 1 本文首先对纠错码技术做一下简介 ,然后以 (63 ,39) 码为例 ,着重讨论用 VC + + 610 对 BCH码迭代译码的进行实现 1关键词 : BCH 码 ;域为素数幂) , 则共有 qk 个码字 1 n 长的数组共有 qk组 , 在二进制的情况下 , 有 2 n 个数组 1 显然 , qk 个n 维数组 ( n 重) 组成一个 GF ( q) ( 表示阶为 q 的 有限域) 上的 n 维线性空间 , 如果 qk 个码字集合构成了一个 k 维线性子空间 , 则称它是一个 ( n , k) 线性分组码 1循环码 :它是最重要的一类线性码 , 我们本文 所要讨论的 BCH 码正是循环码 1 根据代数理论 ,一个循环码是模 ( x n - 1) 多项式剩余类线性结合 代数中的一个理想 1 反之 , 一个理想对应一个循环码 1 从理想的定义可知 , 在理想中至少可以找到一个次数最低的非零首一多项式 g ( x) , 有它的 一切倍式能够生成一个理想 ( 循环码) 1 这个多项式 g ( x) 称为循环码的生成多项式 1BCH 码是一种很好的线性循环码 , 在中 、长码长中具有很好的纠错能力 1 其译码方法也有多 种 ,其中迭代算法因其译码速度快而最常用 1 本 文用最流行的开发工具 Visual C + + ,以软件的方法实现迭代译码算法 ,可供教学 、科研 、工业生产 领域之用 1纠错码简介111纠错码的基本概念线性分组码与循环码 在纠错码中最常用的就是线性分组码 ,它是讨论各种码的基础 1分组码 : 信源输出的信息序列 , 以 k 个码元 划分为一段 , 通过编码器把这段 k 个信息元按一定规则产生 r 个校验元 , 输出长为 n = k + r 的一个码组 1 因此分组码用 ( n , k ) 表示 , n 表示码长 , k 表示信息位 1如果我们把每一个码字看成是一个 n 维数 组或 n 维线性空间中的一个矢量 , 则可以从线性空间的角度 , 比较深入地谈论线性分组码 1线性分组码 :一个 ( n , k) 线性分组码 , 是把信 息化成 k 个码元为一段 ( 称为信息组) , 通过编码器变成长为 n 个码元的一组 , 作为 ( n , k ) 线性分 组码的一个码字 1 若每个码元的取值有 q 种 ( q1BCH 码及其迭代译码算法BCH 码是迄今为止所发现的一类很好的线 性纠错码 , 于 1959 年由 Hocquenghem , 1960 年由Bose 和 Ray - Chaudhuri 分别提出 (BCH 是三位科学家的名字的缩写) 1 它的纠错能力很强 ,而且有 严格的代数结构 ,因此在编码理论中起重要作用.BCH 码的描述BCH 码是可以纠正多个随即错误的循环码 ,可以用生成多项式 g ( x) 的根来描述 , 根集合中含2收稿日期 :2003 - 09 - 14有个连续根 1BCH 码的生成多项式为 :g ( x) = L CM ( m0 ( x ) , m1 ( x ) , m2 ( x ) , ( x) )余式 r ( x) , 然后将 r ( x )“后接”到 M ( x ) 的尾部 ,得到码字 C ( x) . 即 C ( x) = M ( x) + r ( x) .假设输入信息 :M ( x) = m38 x38 + m37 x37 + m1 x + m0 ;生成多项式 :, m一个码的纠错能力 , 完全由它的最小汉明距离 dm 决定 , 而 BCH 码的 dm 则完全由 g ( x ) 的根 决定 1在实际中应用的最多的是码元取自 GF (2) 中 的二进制 B CH 码 1 它有如下性质 :对任何正整数 m 和 t , 一定存在一个二进制 B CH 码 , 它以 1 ,g ( x) = g24 x24 + g23 x23 + g1 x + g0 ;余式 : r ( x) = r23 x23 + r22 x22 + r1 x + r0生成的码字 : C ( x ) = m38 x38 + m37 x37 +m1 x + m0 + r23 x23 + r22 x22 + r1 x + r0 .3 ,2 t - 1为根 , 其码长 n = 2 m - 1 , 能纠正 t 个因此 BCH 码的编码问题就是以 g ( x ) 为模的随即错误 , 校验位数目至多 mt 个 1就 ( 63 , 39) 码而言 , 它的码长为 63 = 26 - 1 , 其 中 dm 为 9 , 可纠正 4 个随机错误 , 因此它的校验元共 24 个 1 而它的生成多项式就是以1 ,3 ,5 ,7 的根最小多项式的乘积 1除法问题 112译码3相对于编码而言 ,BCH 码译码问题一直是编码理论研究中最感兴趣的问题之一 1 一个码是否能在实际中应用 ,往往取决于译码器是否简单 、快速 、经济和译码错误概率小 1BCH 码在短和中等( 63 , 39) 码的编码和译码实现首先 , 为了便于计算机快速的计算有限域多 项式乘法 ,在程序中首先建立一张表 ,来建立 GF (26) 上所有元素同以模 x6 + x + 1 的所有剩余类多项式之间的对应关系 1 由于 GF ( 26 ) 上的所有非零元素对乘法满足阿贝尔群 ,所以计算多项式 乘法只需要查表找到对应多项式的元素 ,然后根据元素的乘积找到对应的多项式 ,即完成乘法计 算 1 在 GF ( 26 ) 上有非零元素 26 - 1 个 ,同 x6 - 1 的所有剩余类多项式一一对应 1 比如当要计算两 个多项式 x3 + x 同 x5 + x3 + x 的乘积时 , 我们只需要查表得到其对应的元素分别为 13 和 53 , 其乘积为元素66 = 3 , 于是再返回查表得到 3 对 应的多项式 , 它就是 x3 + x 同 x5 + x3 + x 的乘积 1 下面是该表的部分内容 ( 其中 是多项式 x6 + x+ 1 的根)3码长下 , 具有很好的纠错性能 , 在实际中应用广泛.BCH 码属于线性循环码 ,其译码步骤如下分为三步 :第一步 :由接收到的 R ( x) 计算出伴随式 S ;第二步 :由伴随式 S 找出错误图样 E ( x) ;第三步 :由 R ( x) - E ( x ) 得到最可能发送的码字 C ( x) , 完成译码 1 其中第二步是关键步 , 可以进一步细分为 :(a) 由伴随式 si 求出错误位置多项式( x) ;(b) 用钱搜索解出 ( x ) 的根 , 得到错误位置数 , 确定出错位置;(c) 由错误位置数求得错误值 ,从而得到错误图样 E ( x) .决定译码器的复杂性和速度的主要因素在于如何求 ( x ) , 如何简化和加快这一步是 BCH 码GF (26) 上的元素0 = 1 2对应的多项式000001000010000100译码的关键 1 求( x ) 有许多方法 , 常用的有 Pe2terson 的直接算法 ( 通常对于 t = 4) .Peterson 算法主要是通过公式的方法 ,通常要解线性方程组 ,它的计算量和系数矩阵阶数的三次方成正比 1 因此当码长较长 ,纠错能力较大时 ,6263311编码100001000001计算量很大 ,要求译码器的运算速度很高 1迭代译码算法由 Berlicamp 提出 ,极大的加快了求( x) 的速度 ,易于用计算机完成译码 ,因此根据循环码的性质 , 其每一个码字必是循环码生成多项式 g ( x) 的倍式 , 那么我们就可以根据 g ( x) 来构造循环码 1 对于 ( 63 , 39) 码 , 具体来讲 就是先用输入信息多项式 M ( x) 去除 g ( x ) , 得到从工程上解决了 BCH 码的译码问题 1在这里首先引用求( x) 的关键方程 :S ( x)( x) ( x)x2 t + 1)(mod其中 S ( x) = 1 + S 1 x + S 2 x2 +41 if dj 051 then 选 j 前的第 i 行满足 i - D ( i) 最大且0( x) = 1 +1 x +2 x2 +t xt应用此方程 , 根据对应项系数 , 可求出( x ) .比如 , 当 t = 1 时 , 根据关键方程 , 可以得到 :1 + ( S 1 +1) x + ( S 11 + S 2 +2) x21 + 1 x + 2 x2 ( mod x3)继而根据对应项系数 , 得到S 1 + 1 - 1 = 0S 11 + S 2 +2 - 2 = 0又因为当 t = 1 时 ,2 = 0 ,2 = 0 , 所以得到 :( x) = 1 + ( - S 2/ S 1) x如果错误个数 t 比较大时 , 用展开关键方程 两边的方法求( x) 会很麻烦 1 所以 , 我们采用迭代的方法来解关键方程 1用迭代算法就是首先选择一组或两组合理的 初值如(0) ( x) 和 (0) ( x ) , 然后开始迭代运算求(1) ( x) 和 (1) ( x ) , 并用 (0) ( x ) 和 (0) ( x ) 来表示它们 1 这样依次进行 , 也就是首先计算出满足 关键方程的( x ) 和 ( x ) 的低次项 , 然后通过迭代逐步得到( x ) 和 ( x ) 的高次项 , 最后解出满 足关键方程的( x) 和 ( x) .用这种方法求解时 , 每一步都不是唯一的 , 为 了使解唯一 , 必须加以条件限制 , 即 :( 1) 50( i) ( x) 50( i) ( x)(2) 50( i) ( x) = min50( i) ( x) .用迭代法求解到第 j 步时 , 求得满足 S ( x )( j) ( x) ( j) ( x) (mod xj + 1) 的解( j) 和( j) . 在通 常情况下 , 第 j + 1 步 , 即 xj + 2 为模时 , 上式的( j)( x) 和 ( j) ( x ) 并不满足上面的关键方程 1 这里有di61( j +1) ( x) = ( j) ( x) - d d xj - i( i) ( x)( i) ( x)i j( j +1) ( x)= ( j) ( x) - d d xj - ii j71el se ( j +1) ( x) = ( j) ( x)( j +1) ( x)= ( j) ( x)81 ( x) = ( j +1) ( x) ; / / 如果 50( x) t , 说明有不可纠的错误 1( x) = ( j +1) ( x) ;用 VC 610 实现的 ( 63 ,39) 码编码4和译码程序(63 ,39) 码的编码很简单 ,方法前面已经介绍 过 ,不再详述 1BCH 码是一种循环码 ,要根据循环码的译码 方法来译码 1 程序首先要计算接收数据 R ( x ) 的 伴随式 S i . ( 63 , 39) 码共有 8 个伴随式 , 但根据伴随式的性质 , 我们只需求 i = 1 , 3 , 5 , 7 这几个伴随式 , 而 i = 2 , 4 , 6 , 8 可由前者计算出来 1求伴随式的方法是进行多项式除法 , 即如果 求 S i , 可用 mi 去除 R ( x ) , 所得的余式 ri 再带入相应的元素即可 1 例如 , 如果想求 S 3 , 先用 m3 去除 R ( x) , 得到余式 r3 , 然后将3 带入到 r3 中 , 最 后便得到 S 31伴随式如果不为 0 , 那就认为数据在传输过 程中受到破坏 , 有错误产生 1 反之 , 我们就认为数 据没有遭到破坏 1程序中需要很多多项式除法和乘法操作 , 于 是对应乘法和除法都各自编写独立的功能程序块 , 其实现方法都是查 GF (26 ) 根与多项式对应关 系表 1接下来便是按照迭代算法来进行迭代 , 根据S ( x)( j) ( x) ( j) ( x) + d xj + 1 ( modxj + 2)j其中 , dj 是第 j + 1 步与第 j 步的差值 1 这样得到公式 :( i) ( x)( i) ( x)( j + 1) ( x) = ( j) ( x) - d d xj - ii j( j + 1) ( x) = ( j) ( x) - d d xj - i伴随式 S 得到错误位置多项式( x ) . 迭代需要i ji这里 i 是 j 前面的某一行 , 它满足最大 , 且 dj 0 , 而D ( j) = 50( j) ( x)i -D ( i )2 t - 1 步 , 在这里 , ( 63 , 39) 码需要 7 步迭代 , 即能迭代出( x) . 程序中每次迭代只保留当前最新的now ( x) 和之前的某次 ( x ) , ( x ) 要满足 i - DiiD ( j + 1) = max ( D ( j) , j -213迭代算法i + D ( i ) )( i ) 是最大的 1 迭代完后用钱搜索来解 ( x ) 1 所谓钱搜索 , 就是在知道错误个灵敏的前提下 , 将 GF (26) 内的所有元素逐个带入到( x ) 中 , 但对应 项的次数应该相同 , 即 i ( x ) 应该带入的是该元 素的第 i 次幂 1 检验每个元素带入到( x ) 的值 , 等于 1 的话就该元素就代表( x) 的根 , 并代表了错误应该发生的位置 111( - 1) ( x)= 0 ; / / 初始化= 1 ; ( - 1) ( x )= 0 ; d - 1 = 1 ; D - 121for j - 1 to 2 t - 150( j) ( x) sj +1 - i( j)i31 do dj = sj + 1 +i = 1最后 , 只需要根据( x) 的