如题。。因为看了某针的二维码视频，所以想试试实现自己写个，于是就有了这篇文章。
这里主要研究的是二维码的纠错码。使用语言为Javascript，所有代码均可在浏览器直接运行。

模二除法

因为二维码的编码是在伽罗瓦域中进行的，所以需要大量用到异或和模二乘法。异或很简单，但模二乘法就很复杂了，这里先实现下模二乘法的第二部取余。
模二除法的算法原理参考于模2除法(CRC校验码计算)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
      1 0 1 1     //商
---------------
1 1 1 1 0 0 0     //被除数,注意首位为1
1 1 0 1              //被除数首位为1,除以除数
---------------
  0 1 0 0 0 0     //余数去除首位,作为新的被除数
  0 0 0 0         //被除数首位为0,除以0
---------------
    1 0 0 0 0     //余数去除首位,作为新的被除数
    1 1 0 1       //被除数首位为1,除以除数  
---------------
      1 0 1 0     //余数去除首位,作为新的被除数
      1 1 0 1     //被除数首位为1,除以除数
---------------
        1 1 1     //余数,此时余数位数少于除数,不能继续除了

看计算过程可以得知，模二除法就是看除的时候某一位是不是1，如果是1就用被除数和除数异或，商1，然后看下一位。
我写的算法和上述有些不同，我是看在某一位的时候用被除数和除数做异或运算后被除数是否变小，如果变小则商一。这个算法其实和最简单的竖列除法差不多，都是尽可能的让被除数变小，待会的多项式除法我会用这个思路。光说可能没那么容易理解，上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function mod_div(a,b){
    ori = b;
    while(a > b){
        b <<= 1;
    }

    let ans = 0;
    while(b >= ori){
        ans <<= 1;
        if((a ^ b) < a){
            a ^= b;
            ans += 1;
        }
        b >>= 1;
    }

    return a;
}

在算法中，结果的商也被求出来了，在while结束时的ans即使商，不过由于我们只关心余数，这里就先不管它了。

模二乘法

接下来是模二乘法：

1
2
3
4
5
6
7
8
9
10
11
12
function xor_mul(a,b){
    let ans = 0;
    while(b > 0){
        if(b&1){
            ans ^= a;
        }
        b >>= 1;
        a <<= 1;
        //console.log(ans)
    }
    return ans;
}

算法和快速乘法差不多，这里就不多解释了。

伽罗瓦域中的模二乘法（？）

1
2
3
function mod_mul(a, b, p){
    return mod_div(xor_mul(a, b),p);
}

有了上面的算法，就可以表示出模二乘法了。其中的p是事先设定好的数值，在视频中这个数是0b1011，也就是11 。
接下来验证我们的算法，很简单，我们试着输出一张GF(2^3)的完整乘法表，然后和视频中对照一下就知道算法正确不正确了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mod_div_2 = [];
var i = 0;
for(i=0;i<8;++i){
    mod_div_2[i] = [0,];
}

table = '';
for(i=0;i<8;i++){
    for(j=0;j<8;j++){
        tmp = mod_mul(i, j, 11);
        table += tmp;
        table += ' ';
        mod_div_2[tmp][i] = j;
    }
    table += '\n';
}
console.log('-----table-----');
console.log(table);
console.log('-----table2-----');
console.log(mod_div_2);

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-----table-----
0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 3 1 7 5
0 3 6 5 7 4 1 2
0 4 3 7 6 2 5 1
0 5 1 4 2 7 3 6
0 6 7 1 5 3 2 4
0 7 5 2 1 6 4 3

-----table2-----
[
  [7, 0, 0, 0, 0, 0, 0, 0 ],
  [0, 1, 5, 6, 7, 2, 3, 4 ],
  [0, 2, 1, 7, 5, 4, 6, 3 ],
  [0, 3, 4, 1, 2, 6, 5, 7 ],
  [0, 4, 2, 5, 1, 3, 7, 6 ],
  [0, 5, 7, 3, 6, 1, 4, 2 ],
  [0, 6, 3, 2, 4, 7, 1, 5 ],
  [0, 7, 6, 4, 3, 5, 2, 1 ]
]

你可能会发现这段代码和刚才我说的不太一样，事实上，这里我并不仅输出了一张乘法表，顺便还获取了一张完整除发表（实际上是刚才的逆运算，和上面的模二除法并不一样）。这在后面会用到。通过对比，我们能看到输出的这张乘法表和视频中是一样的，说明了我们算法的正确性。

多项式运算

接下来的运算都是把数据编码成多项式后进行的运算，所以我们需要多项式的运算。
要进行多项式运算，我们首先要定义多项式。
这里我直接使用数组来代表多项式。数组下标为n的元素的值代表多项式fx中x的冥为n的项的系数。
例如：[1,2,3,4] 代表的就是f(x) = 4x^3 + 3x^2 + 2x + 1。

多项式的加法与减法

因为在前面定义过，伽罗瓦域中的加法与减法都是异或运算，所以这里的加减法都一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function polyn_add(a, b){
    // 让a的项数始终比b多。
    if(a.length < b.length){
        let c = a;
        a = b;
        b = c;
    }

    let ans = [];

    for(i=0; i<a.length; i++){
        if(i < b.length){
            ans.push(a[i] ^ b[i]);
        } else {
            ans.push(a[i]);
        }
    }

    return(ans);
}

var polyn_sub = polyn_add;

只需要逐位进行异或运算，注意下两个多项式项数不一样的情况就行了。

多项式的乘法

多项式的乘法就复杂一些了，但也不算太难。两个多项式相乘，结果的最高项一定是两个多项式最高项的和，只要按照排列组合把每一项都加起来就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function polyn_mul(a, b){
    let max_ratio = a.length + b.length - 1;
    console.log('max--',max_ratio)
    //make a longer than b
    if(a.length < b.length){
        let c = a;
        a = b;
        b = c;
    }

    let ans = [];

    for(i=0; i<max_ratio; i++){
        let tmp = 0;
        for(j=0; j<a.length; j++){
            if((i-j >= 0) && (i-j < b.length)){
                tmp = mod_add(tmp, mod_mul(a[j], b[i-j], 11));
            }
        }
        ans.push(tmp);

    }

    return ans;
}

多项式的除法

和乘法相比，除法就复杂多了，不过和上面的模二除法思路差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function polyn_div(a, b, p){
    let aa = a.reverse();
    let bb = b.reverse()

    ori_leng = bb.length;

    while(aa.length > bb.length){
        bb.push(0);
    }

    let ans = [];
    while(aa.length >= ori_leng){
        let tmp = aa[0];
        ans.push(tmp);
        aa = polyn_sub(aa, bb.map(val=>mod_mul(val, mod_div_2[tmp][bb[0]], p)));
        aa.shift();
        bb.pop();
    }

    aa.reverse();
    while(aa[0]===0&&aa.length>1){
        aa.shift();
    }

    return aa;
}

同样，这里的除法虽然计算出了商，但我们只关注余数，不关注商。

编码

有了多项式的除法后，我们就可以比较方便的计算出一段数据的纠错码了。我们只需要把原始数据后加四个零，然后除以预设的数值，所得结果即为我们要的纠错码。
在视频中，预设的多项式为 `(x - 2^0)(x - 2^1)(x - 2^2)(x - 2^3)。可以通过下面的方法算出具体的值：

1
2
3
4
tmpa = polyn_mul([1,1], [2,1]);
tmpb = polyn_mul(tmpa, [4,1]);
gx = polyn_mul(tmpb, [3,1]);
//gx = (x-2^0)*(x-2^1)*(x-2^2)*(x-2^3) = [5, 7, 7, 4, 1]

用下面的方法算出纠错码：

1
2
3
4
5
6
7
8
9
10
function get_eccode(data){
    let mx = [0,0,0,0].concat(data.reverse());
    let gx = [5, 7, 7, 4, 1];
    let px = polyn_div(mx, gx, 11);
    let eccode = data.reverse().concat(px.reverse());
    return eccode;//mx
}

console.log(get_eccode([1,2,3,4]));
//输出： [ 1, 2, 3, 4, 1, 6, 7, 4]

验证数据有没有被篡改也很简单，只要用数据除以预设的多项式，若结果为0，那就是没问题。

1
2
console.log(polyn_div([1,2,3,4,1,6,7,4].reverse(), [5,7,7,4,1], 11));
// 输出： [ 0 ]

这样我们就得到了我们想要的编码了。

数据的恢复

那要是我们的数据被损坏了呢？
按照视频中的思路，我们可以通过解一个四元二次方程组来获得错误的数据的位置和大小，然后就可以计算出正确的数据。但是解一个四元二次方程组对一个中学生而言显然有些过于困难了，好在数据量不大，我们可以通过遍历的方法解出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 求幂算法
function mod_pow(a, b, p){
    let ans = 1;
    for(i=0;i<b;++i){
        ans = mod_mul(ans, a, p);
    }
    return ans;
}
// 快速多项式算法
function compute_polyn(n, a, x){
    p = a[n];
    for(i=n;i>0;--i){
        p = a[i-1] ^ mod_mul(x, p, 11);
    }
    return p;
}

// 这个函数用来计算方程组的右半部分
function compute_offset(y1,y2,e1,e2,pos){
    return mod_mul(y1,mod_pow(2,pos*e1,11),11) ^ mod_mul(y2,mod_pow(2,pos*e2,11),11);
}

// 这个函数用于在已知错误的情况下完成纠错
function correct_data(error, data){
    data[error[0]] ^= error[2];
    data[error[1]] ^= error[3];
    return data;
}

function correct_error(data){
    // 先算出m(2^0) ~ m(2^3)的值
    m20 = compute_polyn(7, data, 1);
    m21 = compute_polyn(7, data, 2);
    m22 = compute_polyn(7, data, 4);
    m23 = compute_polyn(7, data, 3);

    ans=[];//方程组的解可能不止一个

    // 遍历找解
    for(y1=0;y1<8;++y1){
        for(y2=0;y2<8;++y2){
            for(e1=0;e1<8;++e1){
                for(e2=0;e2<8;++e2){
                    if((compute_offset(y1,y2,e1,e2,0) === m20) && (compute_offset(y1,y2,e1,e2,1) === m21) && (compute_offset(y1,y2,e1,e2,2) === m22) && (compute_offset(y1,y2,e1,e2,3) === m23)){
                            ans.push([e1,e2,y1,y2]);
                        }
                }
            }
        }
    }

    //输出所有可能的正确结果
    return ans;
}

然后我们来用视频中的例子验证下它的结果：

1
2
3
4
5
6
err = correct_error([4,7,6,1,4,2,2,6]);
console.log(err);

err.forEach(element => {
    console.log(correct_data(element, [4,7,6,1,4,2,2,6]));
});

输出：

1
2
3
4
5
[ [ 5, 0, 1, 7 ], [ 5, 7, 1, 7 ], [ 0, 5, 7, 1 ], [ 7, 5, 7, 1 ] ]
[ 3, 7, 6, 1, 4, 3, 2, 6 ]
[ 4, 7, 6, 1, 4, 3, 2, 1 ]
[ 3, 7, 6, 1, 4, 3, 2, 6 ]
[ 4, 7, 6, 1, 4, 3, 2, 1 ]

可以注意到，代码一共帮我们找到了4个可能的解，其中第二个和第四个显然是和视频中相同的答案，只是顺序不同而已，但除了这两个答案之外还给出了另外两个答案，而且他们都是可以通过验证的，只不过现在我还不知道为什么（

后记

那笔记就这么多了，原理部分不多但这些代码是可以完成基本功能的。虽然还有些小bug而且还有些地方我还不会写。。现在也还正在学习这些内容。如果谁能给我一些修改建议那就感激不尽了。