BCH编解码

概述分组码分组码是一种将信息序列划分为固定长度块进行编码的信道编码方法用于检错和纠错。传输时前后之间的码字无关。将信源的信息序列分成独立的块进行处理和编码称为分组码。编码时将每k个信息位分为一组进行独立处理变换成长度为nnk的二进制码组。(2,1) 码的意思是信息位 k1 位 → 只能表示2 种消息0和1校验位r1 位 → 由信息位通过某种规则计算出来码长 n2 位eg:奇偶校验码是典型的分组码比如长度为3的消息是111那么进行偶校验编码就是1111这里的码长是n4信息位k3,校验(监督)位mm-k1; 对应的检验子是Sa1​⊕a2​⊕a3​⊕a4​。S0无错S1有错。线性分组码线性分组码Linear Block Code是一种分组码其特点是信息码元与校验码元之间满足线性关系。通常记作 [n,k] 线性分组码其中 k 表示信息位长度n 表示码字长度校验位长度为 rn−k即冗余位。生成矩阵负责生成线性分组码监督矩阵负责进行纠错和检错。译码则通过伴随式。线性分组码的一般特性可以概括为它是 GF(2) 上的 kk 维子空间由生成矩阵 G 编码、校验矩阵 H 校验满足 GHT0GHT0最小距离决定纠错能力伴随式用于解码对偶码提供分析工具。纠错码专题——线性分组码1_校验矩阵和生成矩阵的关系-CSDN博客循环码设一个nk线性分组码C如果它的任一码字的每一次循环移位都还是C的一个码字则称C是循环码。以循环汉明码举例%% 列出 (7,4) 汉明码全部 16 个码字 clear; clc; G_POLY [1 0 1 1]; % g(x) x^3 x 1 fprintf( (7,4) 汉明码全部码字 \n); fprintf(信息位 校验位 码字\n); fprintf(--------------------------------\n); for m 0:15 data bitget(m, 4:-1:1); % 4 位信息MSB 在前 msg [data, 0 0 0]; % 左移 3 位 % 多项式除法求余 for i 1:4 if msg(i) 1 msg(i:i3) xor(msg(i:i3), G_POLY); end end parity msg(5:7); cw [data, parity]; fprintf(%s %s %s\n, ... num2str(data), num2str(parity), num2str(cw)); end注重量分布指的是码字中1的数量比如A01就是16个码字中只有1个码字中1的数量为零。对于线性分组码来说码距d最大重量分布-1/2比如这个就是3-1/21这里取3是因为要选择重量最大分布最广的一个。循环码原理与应用-CSDN博客BCH码BCH码由Bose、Ray-Chaudhuri和Hocquenghem于1959-1960年提出是循环码与线性分组码的复合类型基于有限域理论和生成多项式实现多随机错误校正。 其参数体系包括码长n、信息位k和纠错能力t通过多项式除法生成校验位广泛应用于通信如5G、卫星传输、数据存储如SSD、硬盘及深空探测等领域。注素多项式就是不可约多项式。本原多项式就是根数为本原元的素多项式比如伽罗华域2^7他的本原就是7对应的本原多项式就是x^7 x^3 1;BCH编解码BCH编码假设你要编码一个k 位的信息序列目标是生成一个n 位的BCH码字记为 BCH(n, k) 码其纠错能力为t 位。第1步确定生成多项式 g(x)生成多项式是BCH码的核心它是一个次数为的多项式以,,……,为根。构造方法如下确定根根据纠错能力需要以,,……,为根。求极小多项式对于每个根找出它在上的极小多项式。极小多项式是满足的最低次多项式。求最小公倍式生成多项式是所有不同极小多项式的最小公倍式。由于在上就是这些不同多项式的乘积。第2步构造信息多项式将位信息比特……映射为多项式⋯x例如信息11010对应的多项式为第3步计算校验位取模运算这是编码的核心步骤。先将信息多项式左移位相当于乘以然后对生成多项式做模2除法即多项式除法系数在上运算加法等同于异或。余式[⋅]余式的次数小于其系数就是n−k 校验位。第4步拼接码字最终的系统码码字多项式为⋅对应的 n 位码字就是[原始 k 位信息] [n-k 位校验位]。 一个完整示例BCH(15, 5) 编码以 BCH(15, 5) 码、设计距离 d7可纠 3 位错误为例对信息11010进行编码。确定参数n15, k5, n-k10, t3。求生成多项式在 GF(16) 上本原多项式需要以为根。对应的极小多项式为根为)根为根为因此g(x)m1(x)⋅m3(x)⋅m5(x)展开后为。构造信息多项式11010→ u(x)。计算校验位计算。用 g(x)除得到余式。假设余式为。拼接最终码字为。BCH解码BCH 解码的核心是伴随式 → 错误位置多项式 → 错误位置 → 错误值 → 纠错。其中 BM 算法和钱搜索、Forney 算法是三大关键模块。在 GF(16) 等小域中很多运算可以查表硬件实现相对紧凑。对于更大的 BCH 码如 NAND Flash 中的 BCH(720,640,8)解码器会更复杂但基本流程相同。BCH 解码的目标是从接收到的、可能含有错误的码字 r(x) 中找到错误图样 e(x)从而恢复原始码字 c(x)r(x)−e(x)在 GF(2) 上减法即加法。1. 计算伴随式 Si接收码字。因为所以在 GF(16) 中2t6因此需要计算 S1,S2,S3,S4,S5,S6。如果所有 Si0说明没有错误直接输出信息位即可。计算 Si 时将接收到的 15 位码字看作多项式代入 αi在 GF(16) 中做加法和乘法。硬件上通常用 LFSR 或查表法实现。2. 求错误位置多项式 σ(x)σ(x)定义错误位置多项式其中 ν≤t 是实际错误个数xjαij是错误位置的域元素ij 是错误所在的比特位置。用Berlekamp-Massey (BM) 算法或Peterson 算法根据伴随式 S1∼S2t求出 σ(x) 的系数 σ1,…,σν​。BM 算法是一种迭代算法每次用新的伴随式更新 σ(x)和辅助多项式最终得到最小次数的 σ(x)。3. 钱搜索Chien Search找错误位置错误位置是σ(x) 的根的倒数。对于 GF(16) 中的每个可能位置 i0,1,…,14计算 σ(α−i)。如果 σ(α−i)0则第 i 位有错。实际硬件中钱搜索通常并行计算所有 15 个位置每个周期检查一个根。找到根后记录错误位置。4. Forney 算法计算错误值已知错误位置需要求对应的错误值∈GF(16)。定义错误求值多项式其中错误值由 Forney 公式给出在 GF(2) 上负号可忽略。σ′(x)是 σ(x)的形式导数在 GF(2) 上偶数次项导数为 0奇数次项导数为系数本身。计算得到每个错误位置的错误值后将接收码字对应位翻转异或即完成纠错。5. 恢复信息位纠错后得到正确的码字 c(x)。由于 BCH 码是系统码码字的前 k 位或后 k 位取决于编码约定就是原始信息位直接提取即可。