BCH码查看源代码讨论查看历史

来自 孔夫子旧书网 的图片

BCH码是全国科学技术名词审定委员会审定、公布的一个科技名词。

语言文字是一个民族文化的结晶。这个民族过去的文化靠着它来流传,未来的文化也仗着它来推进，从大约是在公元前14世纪，殷商后期的“甲骨文”被认为是“汉字”的第一种形式，西周后期，汉字发展演变为大篆，后秦始皇统一中国，中国文字才逐渐走上了发展的道路，直至今天。

名词解释

BCH码是一类重要的纠错码，它把信源待发的信息序列按固定的κ位一组划分成消息组，再将每一消息组独立变换成长为n(n>κ)的二进制数字组，称为码字。如果消息组的数目为M(显然M>=2),由此所获得的M个码字的全体便称为码长为n、信息数目为M的分组码，记为n，M。把消息组变换成码字的过程称为编码，其逆过程称为译码。

分组码就其构成方式可分为线性分组码与非线性分组码。

线性分组码是指[n,M]分组码中的M个码字之间具有一定的线性约束关系,即这些码字总体构成了n维线性空间的一个κ维子空间。称此κ维子空间为(n，κ)线性分组码，n为码长，κ为信息位。此处M=2。

非线性分组码[n，M]是指M个码字之间不存在线性约束关系的分组码。d为M个码字之间的最小距离。非线性分组码常记为[n，M，d]。非线性分组码的优点是：对于给定的最小距离d,可以获得最大可能的码字数目。非线性分组码的编码和译码因码类不同而异。虽然预料非线性分组码会比线性分组码具有更好的特性，但在理论上和实用上尚缺乏深入研究（见非线性码）。

汉明码

这是最早提出的一类线性分组码，已广泛应用于计算机和通信设备。它是由R.W.汉明于1950年提出的。若码的均等校验矩阵H由2-1个、按任一次序排列且彼此相异的二进制r维列矢量构成。这样得到的线性分组码称为汉明码，其分组长为n=2-1，信息位为κ=n-r=2-1-r，即为(2-1，2-1-r)码。例如，以矩阵

为均等校验矩阵的线性分组码便为(7，4)汉明码。汉明码的译码十分简单。例如, 假定=(1001100)为发送的码字,其第3位有错，即接收矢量为r=(1011100)。于是

恰为矩阵H的第 3 列，因而判定原来发送的码字为=(1001100)。这种译码方式是一般性的。如果接收矢量r在第i位有错,则其伴随式Hr刚好为矩阵H的第i列。汉明码是可以纠正单个错误的线性分组码。

循环码

具有某种循环特性的线性分组码，如果(n，κ)线性分组码Vκ具有如下的性质:对于每一个=(ɑ0,ɑ1，…，)∈Vn，只要∈Vκ,其循环移位()亦属于Vκ,则称Vκ为循环码。循环码的优点在于其编码和译码手续比一般线性码简单，因而易于在设备上实现。使Vn中的每一个矢量=(ɑ0，ɑ1，…，),对应于域GF(2)上的多项式ɑ(x)=ɑ0+ɑ1x+…+x。于是Vn中的全体n维矢量便与上述多项式之间建立了一一对应的关系。基于这种对应,使Vn中除了线性运算而外，还建立了矢量之间的乘法运算。A=(ɑ0,ɑ1,…,)与B=(b0,b1,…,)的乘积ab可视为ɑ(x)b(x)[mod(x-1)]所对应的矢量。因此,一个(n,κ)循环码的生成矩阵及均等校验矩阵可分别由生成多项式及均等校验多项式h(x)所代替，从而简化了编码及译码运算。

BCH码

它是一类重要的循环码，能纠正多个错误。假设m是满足模n(modn)的最小正整数,β是域GF(2)的n次单位原根,作循环码的生成多项式g(x),以d0-1个接续的元素为根，其中m0,d0均为正整数，且d0≥2。于是

其中mj(x)代表的最小多项式。由这个g(x)所生成的，分组长为n的循环码称为BCH码。它由R.C.Bose，D.K.Ray-Chaudhuri及A.Hocquenghem三人研究而得名。BCH码的主要数量指标是：码长n，首元指数m0，设计距离d0，信息位数（表示多项式g(x)的次数）。BCH码的重要特性在于：设计距离为d0的BCH码，其最小距离至少为d0，从而可至少纠正(d0-1)/2个独立错误。BCH码译码的第一步是计算伴随式。假设 为发送码矢量,为接收矢量,而E=(E0,E1,…,En-1)为错误矢量,或记为错误多项式。于是伴随矢量之诸S=(S1，S2，…,S2t)分量Sκ由

决定（κ=1,2,…2t；为简便计,设m0=1,d0=2t+1）。假设有e个错误出现(1≤e≤t),则对应于e个错误的Ei厵0。如果E的第j个（从左至右）非零分量是Ei,则称Xj=β为这个错误Ei的错位，而称Yj=Ei为这个错误的错值。称 为错位多项式。BCH码译码的关键是由诸sκ(κ=1,2，…，2t)求出(z)。这可用著名的伯利坎普－梅西迭代算法来完成。这种算法相当于线性移位寄存器（LFDR寄存器）的综合问题。最后一步是求出(z)的全部根，可用钱天闻搜索算法完成,从而可以定出接收矢量r的全部错位。