营销网站建设前期准备,百度是不是只有在自己的网站发布才会被收录,职友集 一家做公司点评的网站,企业做网站应注意什么概要
本文主要为计算#xff0c;而非对伽罗瓦域等数学内容的深入解析#xff0c;在知道消息多项式以及纠错数量的情况下通过程序生成对应的纠错码。详细的二维码生成原理参考一个详细全面的二维码生成解析
效果
数据码: 长度16的示例数据码#xff08;正常获取的是示例的…概要
本文主要为计算而非对伽罗瓦域等数学内容的深入解析在知道消息多项式以及纠错数量的情况下通过程序生成对应的纠错码。详细的二维码生成原理参考一个详细全面的二维码生成解析
效果
数据码: 长度16的示例数据码正常获取的是示例的逆序,为了方便计算这里颠倒了顺序 [17, 236, 17, 236, 17, 236, 64, 67, 77, 220, 114, 209, 120, 11, 91,32] 生成多项式: 纠错10个数据码的生成表达式生成表达式的javascript 实现在上一篇当然也可以查表获取。
α0x10α251x9α67x8α46x7α61x6α118x5α70x4α64x3α94x2α32x1α45x0α^{0}x^{10}α^{251}x^{9}α^{67}x^{8}α^{46}x^{7}α^{61}x^{6}α^{118}x^{5}α^{70}x^{4}α^{64}x^{3}α^{94}x^{2}α^{32}x^{1}α^{45}x^{0} α0x10α251x9α67x8α46x7α61x6α118x5α70x4α64x3α94x2α32x1α45x0
生成的纠错码(结果) [196, 35, 39, 119, 235, 215, 231, 226, 93, 23] 思路
使用key-value 的形式表示一个多项式的各项以及各项的阶数和其系数。消息多项式和生成多项式的变量指向有所不同
消息多项式首项(如 32x15) key 代表 15 value 代表 32
生成多项式首项(如 α0x10) key 代表 0 value 代表 10
一个完整的消息多项式 32x1591x1411x13120x12209x11114x10220x977x867x7764x6236x517x4236x317x2236x117x032x^{15} 91x^{14}11x^{13} 120x^{12} 209x^{11} 114x^{10} 220x^{9}77x^{8} 67x^{77} 64x^{6} 236x^{5} 17x^{4} 236x^{3} 17x^{2} 236x^{1} 17x^{0} 32x1591x1411x13120x12209x11114x10220x977x867x7764x6236x517x4236x317x2236x117x0 对应数据结构
{15: 32, 14: 91, 13: 11, 12: 120, 11: 209,10: 114, 9: 220, 8: 77,7: 67, 6: 64, 5: 236, 4: 17, 3: 236, 2: 17, 1: 236, 0: 17
}一个完整的生成多项式 α0x10α251x9α67x8α46x7α61x6α118x5α70x4α64x3α94x2α32x1α45x0α^{0}x^{10}α^{251}x^{9}α^{67}x^{8}α^{46}x^{7}α^{61}x^{6}α^{118}x^{5}α^{70}x^{4}α^{64}x^{3}α^{94}x^{2}α^{32}x^{1}α^{45}x^{0} α0x10α251x9α67x8α46x7α61x6α118x5α70x4α64x3α94x2α32x1α45x0 对应数据结构
{
10: 0, 9: 251, 8: 67, 7: 46, 6: 61, 5: 118, 4: 70, 3: 64, 2: 94, 1: 32, 0: 45
}代码
//对数反对数表 (来源 qrcode.js)
let QRMath {glog: function (n) {if (n 1) {throw new Error(glog( n ));}return QRMath.LOG_TABLE[n];},gexp: function (n) {while (n 0) {n 255;}while (n 256) {n - 255;}return QRMath.EXP_TABLE[n];},EXP_TABLE: new Array(256),// 真数LOG_TABLE: new Array(256)// 指数
};
for (let i 0; i 8; i) {QRMath.EXP_TABLE[i] 1 i;// 1 2 4 8 16 32 64 128
}
for (let i 8; i 256; i) {QRMath.EXP_TABLE[i] QRMath.EXP_TABLE[i - 4] ^ QRMath.EXP_TABLE[i - 5] ^ QRMath.EXP_TABLE[i - 6] ^ QRMath.EXP_TABLE[i - 8];//8: 16 ^ 8 ^ 4 ^ 1 29//9: 32 ^ 16 ^ 8 ^ 2 58
}
for (let i 0; i 255; i) {QRMath.LOG_TABLE[QRMath.EXP_TABLE[i]] i;
}//数据码字(消息多项式的系数)
let _msg_coefficients [17, 236, 17, 236, 17, 236, 64, 67, 77, 220, 114, 209, 120, 11, 91, 32];
//生成多项式 α 表达式指数
let _generator_coefficients [45, 32, 94, 64, 70, 118, 61, 46, 67, 251, 0];/*** 根据数据码字生成纠错指定数量的纠错码* param msg_coefficients 数据码字十进制数组* param generator_coefficients 生成多项式 各项α表达式指数数字组*/
function rs(msg_coefficients, generator_coefficients) {//格式化消息多项式 、生成多项式let msgPolynomial {};let generatorPolynomial {};msg_coefficients.forEach((d, i) msgPolynomial[i] d);generator_coefficients.forEach((d, i) generatorPolynomial[i] d);let msg_num msg_coefficients.length;let generator_num generator_coefficients.length - 1;//纠错数量 纠错数量比生成表达式项数少一// a 表示消息多项式 msgPolynomial b 表示生成多项式 generatorPolynomiallet curr_a {};let curr_b {};// msg 升幂Object.keys(msgPolynomial).forEach(d {curr_a[d generator_num] msgPolynomial[d]});// generator 升幂Object.keys(generatorPolynomial).forEach(d {curr_b[d msg_num - 1] generatorPolynomial[d]});for (let i 0; i msg_num; i) {//各项阶数的降序排列let a_keys Object.keys(curr_a).map(d d).sort((m, n) n - m);let b_keys Object.keys(curr_b).map(d d).sort((m, n) n - m);/** 1)* generator 乘以msg最高项系数* 因为 msg的项系数为真数 generator的项系数为指数表达式* 因此 将msg的项系数为真数最高项的系数转成alpha 表达式,然后再乘到generator上*/let a_item_0 QRMath.glog(curr_a[a_keys[0]]);b_keys.forEach(k {curr_b[k] (curr_b[k] a_item_0) % 255;});/**2)* 2-1)a XOR b (系数XOR)将结果的首项去除(首项系数为0) 作为新的消息多项式a,* 2-2)b降幂一次作为新的生成多项式之前的升幂操作就避免* 最低阶项降幂失败因为升幂消息码字数量同样的需要进行消息码字数量次 异或也就是降幂的次数等于异或的次数。*/let xor_result {};let xor_start Math.min(a_keys[a_keys.length - 1], b_keys[b_keys.length - 1]);// 起始阶数let xor_end Math.min(a_keys[0], b_keys[0]);//终止 阶数let a_t, b_t;for (let j xor_start; j xor_end; j) {if (xor_result[j] null) {//异或操作时没有对应阶数的项,取本身a_t curr_a[j] ! null ? curr_a[j] : 0;b_t curr_b[j] ! null ? QRMath.gexp(curr_b[j]) : 0;xor_result[j] a_t ^ b_t}}if (xor_result[xor_end] 0) {delete xor_result[xor_end];//异或结果移除系数为零首项}//新的acurr_a xor_result;//降幂获得新 bcurr_b {};Object.keys(generatorPolynomial).forEach(d {curr_b[d msg_num - 1 - i - 1] generatorPolynomial[d]});}//异或结果let result_desc Object.keys(curr_a).sort((a, b) b - a).map(k curr_a[k]);console.log(数据码字:, msg_coefficients);console.log(纠错码字:, result_desc);console.log(纠错7纠错码字:, [196, 35, 39, 119, 235, 215, 231, 226, 93, 23])
}rs(_msg_coefficients, _generator_coefficients, 16, 10);
