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

第 19 卷 第 5 期 哈尔滨师范大学自然科学学报 NATURAL SCIENCES JOURNAL OF HARBIN NORMAL UNIVERSITY Vol . 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) 称为循环码的生成多项式 1 BCH 码是一种很好的线性循环码 , 在中 、长 码长中具有很好的纠错能力 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 种 ( q 1 BCH 码及其迭代译码算法 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 + +