【举例子详细分析】BCH码(BCH code) - 知乎首发于数学瞎想录切换模式写文章登录/注册【举例子详细分析】BCH码(BCH code)胡虎护弧呼规则就是用来被打破的。流体模拟交流群1001290801。在信息论中,BCH codes 是指 Bose–Chaudhuri–Hocquenghem codes,可以用来纠错。BCH码利用了多项式一些很好的性质。本文将从0开始,用详细的例子解释二进制域中的BCH码。二进制域与多项式首先考虑二进制域,即所有每个位的取值只能是0或1。我们可以尝试把二进制数表示为多项式,二进制数中的从左往右第j位,是多项式x^j的系数。例如11011,可以表示成为 1 + x + x^3 + x^4。二进制域的四则运算与我们常见的十进制差不多,但由于在二进制1 + 1 = 2 = 0,所以我们每次计算后相当于模上2。例如计算11*11,在多项式表示就是 (1 + x)*(1 + x) = 1 + 2*x + x^2 = 1 + x^2 。这儿的x的系数2在二进制中等于0。另外很重要的概念就是二进制域中,加等于减,例如 x^2 + 1 = 0 相当于 x^2 = 1 。寻找新的编码方式我们先回顾简单的奇偶校验码和hamming码。简单的奇偶校验码只能检查出错误而不知道具体是哪里出错,而hamming码只能纠正一位错误。因此我们想能不能有一种方法可以纠正多位错误呢?此时,多项式的威力就发挥了出来。假如我们的真正的消息是m(x),然后乘上一个编码多项式p(x),得到m(x)p(x)再将其发送过去。发送过程中会会受到很多干扰,于是多项式被加上错误多项式e(x),而接收者接收者的消息为c(x),就有c(x) = m(x)p(x) + e(x) 接收者怎么知道消息有没错呢?接收者事先就会和发送者商量好p(x),然后就很简单,只要让c(x)除以p(x),如果余项是0,即没有e(x),没有受到干扰,那么商就是m(x),就是正确的消息。如果余项不是零,我们的商就变成了m(x) + e(x)/p(x),无法将真正的消息分离出来。上述方法有个前提,在m(x) + e(x)/p(x),p(x)必须是不可约的本原多项式(primitive polynomials),这样才能让e(x)不被除尽,我们才能意识到有干扰的存在。至于如何寻找素多项式,将在之后说明。纠单个错的例子下面来看个例子。例如我们要发送的消息m(x)是1001,而编码多项式p(x)是1101,于是我们要发送出去的消息就是1100101。假如接收者也接收到了这个消息,用p(x)除后余项是0,没有错误存在,商是1001,就是发送者发送的消息,自然皆大欢喜。但如果发送过程中,有一个位被某种不可抗拒的神秘力量改变了,变成了1100111,接收者同样用p(x)去除,得到了余项1110000,这下不好了,接收者知道出错了。但现在怎么去找出错误多项式e(x)呢?我们知道,这个余项1110000,就是e(x)/p(x)的余项。为了找出e(x),我们可以反过来推。于是制作一张表格表格右侧就是如果出现一位错误,r(x)/p(x)后,e(x)/p(x)的余项。通过寻找余项结果,我们可以快速定位究竟是哪里出错了。当然如果e(x)为0,那么e(x)/p(x)的余项也为0。上面这个方法之所以能奏效,对于所有的可能的错误。是因为右边的每一个余项都不相同,我们才不至于混淆。如果我们把p(x)换成10001会发生什么呢?这里10001不是本原多项式,因为10001可以分解成101乘101。我们可以看到,右侧重复了!假如我们得到余项1000000,我们无法知道e(x)究竟是第一行的1000000还是第五行的0000100。而本原多项式就好在,在所有错误余项e(x)出现前前,e(x)/p(x)的余项不会重复。之后将开始重复,这就是被称为循环(cyclic)码的原因。寻找本原多项式本原多项式是个神器,但哪些是本原多项式呢?首先有一些原则:r次多项式,最高次项x^r的系数必须是1。多项式如果不包含常数项1,就会被x整除。多项式项数不能是偶数的,比如 1 + x + x^2 + x^4 有四项,很容易将其分解为 (1 + x)(1 + x^2) 。每一项的次数也不能都是偶数,否则将每一项次数减半就能得到因子。例如 1 + x^2 + x^4 = (1 + x + x^2)^2 。于是我们很容易找到:按照上述方法还可以继续寻找更多的本原多项式。次数越高数量越多。BCH码但如果想要纠正多个错误呢?此时仅一个编码多项式p(x)就不够了,我们还需要更多的编码多项式来让我们能找出多个错误。这时就轮到BCH码出场了,其编码多项式标准形式是:其中p(x)是本原多项式,而 p_3(x^3),p_5(x^5)… 都是可以被p(x)除余0的多项式。即如果我们要设计一个可以纠正两个错误的编码多项式,就让 Q(x) = p(x)p_3(x) 。要设计一个可以纠正三个错误的编码多项式,就让 Q(x) = p(x)p_3(x)p_5(x) 。现在我们先说如何寻找 p_3(x) 。例如 p(x) = 1 + x + x^4 。我们发现 (x^6 + x^9 + x^12) = 1 + x^3 (mod \space p(x)) ,所以 (1 + x^3 + x^6 + x^9 + x^12) = 0 (mod \space p (x)) 。我们用 x 代替 x^3 ,就得到 p_3(x) = 1 + x + x^2 + x^3 + x^4 。纠正多个错误的例子注:以下计算均是模上了 p(x) = 1 + x + x^4 的在二进制域内的计算。还是和原来一样,假如我们要发生的消息m(x)是11010,选择的本原多项式是 1 + x + x^4 ,那么 p_3(x) = 1+x + x^2 + x^3 + x^4 , p_5(x) = 1 + x + x^2 。编码多项式就是 Q(x) = p(x)p_3(x)p_5(x) = ( 1 + x + x^4 )( 1+x + x^2 + x^3 + x^4 )(1 + x + x^2) = 1 + x^2 + x^3 + x^4 + x^5 + x^8 + x^{10} ,表示成二进制是11101100101,再乘上消息m(x)就是100001110110010,就是我们发送的出去的。但现在接收者受到的r(x)却是 101000110110010。然后接收者开始计算:前两项余项不为0,而第三项为0说明接到的只有两处错误。但如何把它们的位置找出来?我们就要用到错误定位多项式( error locator polynomial )了。即:不过这时 e_3 可以认为是无穷小,这样 x^{e_3} 就是0。如果我们能找到这个函数的两个根,我们也就找到了e1和e2。为了解决这个问题,我们得先定义两个函数。两个函数初等对称函数(Elementary symmetric polynomial)s,即满足下列的形式的多项式另定义幂和对称函数( power sum symmetric functions)t,在我们的例子中,可能有三个错误,于是可表示成:重点来了。我们有s与t的关系:计算此时上面的错误定位不等式就可以用s函数来描述:我们知道一些t的结果:再用s和t的关系计算即第一个错误在第三个位,第二个错误在第六个位,没有第三个错误。于是将 101000110110010 修改回来得 100001110110010 ,再除Q(x)就得到了真正的消息m(x) = 11010 。结语BCH码被用于卫星通信,固态硬盘等领域。例如BCH(31,16)码,每组有31个位,其中有效的信息位为16个,汉明距离为7,可以纠正3个位的错误。此时应该使用的本原多项式的最高项次数应该是5,因为 2^5 = 31 + 1 。有时候我们使用可以用BCH纠正k个错误的码,但如果错误不止k个,我们就无法恢复正确的消息。但我们仍然可以恢复一些可能是正确的消息,再逐一排查。参考:http://math.mit.edu/~shor/18.310/BCH.pdfhttp://www-math.mit.edu/~djk/18.310/18.310F04/bch_codes.html编辑于 2020-01-28 23:27信息论编码通信赞同 21158 条评论分享喜欢收藏申请转载文章被以下专栏收录数学瞎想录用好玩有趣的文字介绍迷人
BCH码(BCH Code) - 知乎切换模式写文章登录/注册BCH码(BCH Code)小鱼儿学习笔记1.BCH码的基本概念和性质BCH码(BCH codes、Bose–Chaudhuri–Hocquenghem codes),是一种在编码理论和纠错码领域广泛研究的编码方法。它属于多级、循环、错误校正、变长数字编码,旨在纠正多个随机错误模式。BCH码是循环码的一种,其定义基于生成多项式 g(x)。在特定的 n 和 k 下,通常从BCH生成多项式表中选择 g(x) 的值。系统编码方式与CRC和循环码相同,并且可以使用相似的通用编码器电路结构。原始狭义BCH码中当m ≥ 3为任意正整数时,存在一个二进制BCH(n,k)码,其具有以下参数:定义在伽罗华域 GF(2^{m}) 上码长:n = 2m - 1(原始BCH码)可纠正的最大错误数: t < (2^{m} -1 )/2 一个码字中的信息比特数:k ≥ n - m*t最小距离:dmin ≥ 2t +1 • 当t=1时得到循环Hamming码 t个错误可纠正的原始BCH码的生成多项式 g(x) 是GF(2)上具有 \alpha, \alpha^2, …...\alpha^{2t} 为其根的最低次多项式(即对于 i= 1,2,…,2t,满足 g( \alpha^{i} ) = 0) 在GF(2)中,根的平方也是根。 对于特定的n、k和t值,通常从现有的BCH生成多项式表中选择g(x)的值。如表1所示(不完整)。Table 1广义的BCH码自行Google2. BCH码的定义相关示例示例1对于(7,4)的BCH码,其生成多项式为: g(x) = (13)_{Octal} = 001011 = x³ + x + 1 。这个码的码长为n=7,即2³ - 1,是在GF(2³)上定义(m=3)根据条件k ≥ n - m*t,4 ≥ 7 - 3t,所以t ≤ (7-4)/3 = 1最小距离满足dmin ≥ 2t + 1 = 3容易地检查出 \alpha 和 \alpha^{2} 是g (x) 的根,即带入g(x) = 0,计算在伽罗华拓展域上,由其原根多项式约束p(x) = 0示例2对于(31,21)的BCH码,其生成多项式为 : g(x) = (3551)_{Octal}= 011101101001 = = x^{10} +x^{9} +x^{8} +x^{6} +x^{5} +x^{3} + 1 这个码的码长为 n= 31 = 2^{5}-1 ,因此 m =5 k ≥ n - m*t , 21≥ 31-5*t , t ≤ (31-21)/5 = 2 dmin≥ 2t+1 = 5\alpha ,\alpha^{2} ,\alpha^{3} ,\alpha^{4} 是g(x)的根3. BCH编码(BCH Encoding)3.1 非系统编码:消息作为一个因素找到作为生成器倍数的多项式的最直接方法是计算某个任意多项式与生成器的乘积。在这种情况下,可以使用消息的符号作为系数来选择任意多项式。c(x) = I(x) * g(x) 作为一个例子,考虑生成多项式 g(x) = (3551)_{Octal}= 011101101001 = x^{10} +x^{9} +x^{8} +x^{6} +x^{5} +x^{3} + 1 选择用于POCSAG等使用的 (31, 21) 二进制 BCH 代码。为了对 21 位消息 {101101110111101111101} 进行编码,我们首先将其表示为多项式 I(x)。然后,计算c(x) = I(x)*g(x)因此,传输的码字是{1100111010010111101011101110101}。所以在纠错以确保码字有效之后,可以重新计算I(x) = c(x)/g(x)。[1]3.2 系统编码:消息作为前缀BCH和CRC有相同方式的系统编码。系统编码是通过以下步骤进行的,以使BCH码字成为码的生成多项式g(x)的倍数:通过将消息I(x)预乘以 x^{n-k} 将 I(x) * x^{n-k} 除以 g(x)(modulo-2),得到余数将余数附加到I(x) * x^{n-k}以形成BCH码字c(x)示例一个 7 位的消息块 I(x) = 0000101 = x^2 + 1 要使用定义在 GF(2^4) 上的 BCH(15,7) 编码,并使用生成多项式 p(x) = x^4 + x + 1 进行编码,找到对应的码字g(x) =(721)x_{Octal}=111010001 = x^{8} +x^{7} +x^{6}+x^{4}+1 • I(x) * x^{n-k} = x^{10}+x^{8} • I(x) * x^{n-k}/g(x)= x^{2}+x +1 余数 x^{5}+x^{4}+x^{2}+x+1 • c(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1= 000010100110111 (15 bits) 可以验证 c(\alpha ) =0; c(\alpha^{2}) =0; c(\alpha^{3}) =0; c(\alpha^{4}) =0; 比如 c(\alpha ) =\alpha^{10}+ \alpha^{8}+ \alpha^{5}+ \alpha^{4} + \alpha^{2}+ \alpha+ 1 = (\alpha^{2} +\alpha +1)+(\alpha^{2}+1)+ (\alpha^{2} +\alpha)+ (\alpha+1)+ \alpha^{2} +\alpha+1 =0 4. BCH解码(BCH Decoding)对于代数解码BCH码,通常包括以下一般步骤计算综合值(syndrome)确定误差定位多项式,其根提供了错误位置的指示。有不同的方法来找到定位多项式。这些方法包括 BCH 码的 Peterson 算法、BCH 码的 Berlekamp-Massey 算法,欧几里得算法等。寻找错误定位多项式的根。通常使用 Chien 搜索(Chien search)进行,这是对域中所有元素进行穷举搜索的一种方法。以Peterson 算法为例解码过程中的第一步是检查接收到的码字(按设计为 g(x) 的倍数)是否仍具有 \alpha,\alpha^{2},...,\alpha^{2t} 作为根假设 r(x)= c(x) + e(x) 是接收到的码字(多项式), e(x) 是错误多项式首先检查 r(\alpha^{i})=0 ,对于\alpha,\alpha^{2},...,\alpha^{2t}r(\alpha^{i})=c(\alpha^{i})+e(\alpha^{i})=e(\alpha^{i})=S_{i} 所以计算 S_{i}=r(\alpha^{i}) , i=1,2,...,2t 对BCH二进制码 S_{2i}=(S_{i})^{2} ,对任意i因此只需要计算 S_{i} 对任何奇数的i与 Meggit 解码不同,代数解码间接使用综合值定位错误,通过定义一个错误定位多项式 \sigma(x),其根 X_{k} (或倒数根)给出了错误的位置。其中 X_{k} 是第k个错误定位器, X_{k}=\alpha^{j} , \alpha^{j} = GF(2^{m}) , k=1,2,...,t ,表示接收到的n位字的 r(x) 中第 j 位的比特错误 ( j=0,1,2,…..n-1) 。使用 \sigma(x) 允许 (*) 被转换成一组线性方程。Fig.1Fig. 2示例一个在 GF(2^{4}) 上定义的 BCH(15,7),使用 p(x)=x^{4}+x+1 ,编码后的码字接收为 r(x)=x+x^{8}+x^{11}+x^{12} 。假设 c(x)=x+x^{7}+x^{8}+x^{11}+x^{12}+x^{13} 计算过程如下代入 \sigma(x)=x^{2}+\alpha^{5}x+\alpha^{5} ,逐个检查(Chien search)它的根(roots),所以当检查到 j=7:\sigma(\alpha^{7})=\alpha^{2}+\alpha^{5}\alpha^{7}+\alpha^{5}=\alpha^{3}+1+\alpha^{3}+\alpha^{2}+\alpha+1+\alpha^{2}+\alpha=0 类似的 j=13:\sigma(\alpha^{13})=0 所以这里就是接收错误所在。那么这个例子中可以在r(x)中的 j=7,j=13处进行纠正。........ [1]‘BCH code’, 维基百科. Sep. 22, 2023. Accessed: Nov. 30, 2023. [Online]. Available: https://en.wikipedia.org/w/index.php?title=BCH_code&oldid=1176614924 [2] G. Wade, ‘Coding Techniques: An Introduction to Compression and Error Control’, 2000. Accessed: Nov. 30, 2023. [Online]. Available: [3]W. W. Peterson and E. J. Weldon, Error-correcting Codes. MIT Press, 1972. 编辑于 2023-12-01 03:00・IP 属地英国编码理论纠错码BCH码赞同 31 条评论分享喜欢收藏申请
3046 0 obj <> endobj
3057 0 obj <>/Filter/FlateDecode/ID[<531D2BC45BE35A498620DC17DA799DD9>]/Index[3046 23]/Info 3045 0 R/Length 67/Prev 377637/Root 3047 0 R/Size 3069/Type/XRef/W[1 2 1]>>stream
h�bbd``b`���A�'Q$�/�X� BH� �L a�
$2-���@b�D����` I\
endstream endobj startxref
0
%%EOF
3068 0 obj <>stream
h�b```�Zf� ��
�,o�$�L��w�� �EL>0�j�a``|���ɔь�c S7�V�0���+�~�K�1Z1�3���f������I�i7�$�\7&%�z�� �,�X�h�?J�Y-���lY��4e!�ץEͬ������5�k<���uz��n��Ŋ��X�F�ܧ"�a)tuf�ʅ"��bW�3��j�v<п�[���Q>k�����O����-r��^�y�CoS���)�o9~�,zˮdwu��->��U�[d�ba�L����O�V/�)��˚��uo�ԅ��@�0�]se�fMK��z��ek�/���g=g���ȿk�|����N���u>���Tn����Y�be�/����u�`�DGGG������ �d �8�L����X I \��C�BRϜ��@��%��20�������Z��%B`Ob`V:�9�X��<�f�X0X�042X2�\�� -����'C�ęj*<�,q1�O�0���_ ��h�)g`�� ��@����u�/��a`X},��HMc`_Q�h` �v%l
endstream endobj 3047 0 obj <>/Metadata 148 0 R/Outlines 210 0 R/PageLayout/SinglePage/Pages 3036 0 R/StructTreeRoot 301 0 R/Type/Catalog>> endobj 3048 0 obj <>/Font<>>>/Rotate 0/StructParents 0/Type/Page>> endobj 3049 0 obj <>stream
H��P_K�0ϧ���a�]nM(�M�0��1��M&��VQ������7 �]~ˠ�ձ��ꦃ�0e�~�z���z�Md��v��z{�>_�`�۶����wW?�u�o0���
��V� Pg����2! ��B�� �;�
ʑ���q�AxQ��"�IG����(݄[���@��|U��q�Xp?�\�5�Eʬ��(����BL�������������@e�
Jx�$q8!���V��S�Y�̞�p*�JQq��L�Nʔ�J�o�=ӌ�l��3�_��yP_ �Nx�
endstream endobj 3050 0 obj <>stream
h���n�0�_�?A�c�N�*$cDbt*�lE��K!A��Ƌ�Q�x�|nA���w(:�s.>��#�G1��[�Qx;�9��Â!W���Â#߱A9ĵar(���AЉ
��Ԥx����<��J��0��VzWǏr�
��j�8��:m7�D���V�Ĵ�|�����;�vtaGD��T˕F�wqW�� J=�K�e��e��t��ӆo �P��f3k�Ek��j������K�J$�b���Fk�����n�F[��\��
�|%V5)�q ����h��D"�GZ��x��H�
��j�����r�6c�JFh}W�m��%+y� ��q�9�~�6�0Sܝ�.M �<%\m��0��5�Sex2eSN�l�jM�A�ûZW9�82s3��<0��S��b��XV�L�g�Re�$�#lб�s�Mនf�D��i�=��Y�9�.��
������6���>��������
�"�q����B�{*/t���C�U���D{��o���2{�:{�.֫bJ)@���|���;dv����<�8���s��xk0� �VX�G(��"Kd�į4����|��rF���9�A��Ux��+�.Q s�or����b~� 0��
endstream endobj 3051 0 obj <>stream
H�\��j� ��}��ܽX�a�e�B.z�i ��Vh��"o�]���ә_�_yn�k�w?��j��t�
�ǫ�"/@�8��sB��]�cc�IT�J��/�z�S�k!Fo�V_�v ��9��#� �5h袗νv#���M�)o²!�_������S3j�8�N���E�Q�P](j�V���C���w�EUpq��B|ILªL�%��y✹H\0��K�m�-�.�y�x�|H|`>&>2��b��θur����dI����`,>~�MH�C�
0 ��
endstream endobj 3052 0 obj <>stream
H�b``������$����WR����~�������|@���T��#���2S/`M.(*���(%�8H����8c�-�� f�ԉd�9�@6_IjH��9���(3=�D����R�1%?)U!���$5�X�3/9�� �(�$5�j�%V*�'��&*���r" (,!��!�0b;�C��Ң2(��ɘ� � I�8/
endstream endobj 3053 0 obj <>stream
H�Ԕ{\UU�����Qι.> t�iұ4� �曇�B�����L ��|"f��iڌo+�-#�G�LY
>��bf�/`��3��������k�u�oセ @ ~@B����W#ߨ795;%wԜ�W���L��g�\{�4��Acs�e��ƺ-�.�㲦�]��$���~�HOI��m�%�C���d��l�I:�(;,#;oڠ��+���<+'5��?�S���i����v`�$oNH�NϾ3����bjn���E9��{.����;�:e�Q� �*���\-;(!��(�|
��<��i�����a[�����&�&�u��:��-�mp��^���7�c��?e���\ј����C*Zk�i��O�L!��7�^�E�$V��"_�E��b��$��,qC���mqG� jď⮸'������zO+�B�7|�AG+D�:��A�D�b8F i��d�a:f`�(�b�X.f�M�ȓ�(�B�5��M��E9�"M�Y�*-��TLkh7���(�2Q(&��b�Z����A<�I'A���ɕ��$��JI�H�4���lʧ*�9����>: ��Mb��&����2Z%JE��H5�������{��>b�>H��� �"=���>�,4_ĉ��>������"Cd����m�