精华内容
下载资源
问答
  • 直接上例子,“hello world” 利用二维码的编码原理,转换成十进制数字为“32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17”,因此这个语句的消息多项式为: 32x15+91x14+11x13+120x12+209...

    本文将通过例子来说明两个方面的内容:
    (1)如何构建纠错码?
    (2)有了纠错码之后如何纠错?

    1 如何构建纠错码?

    直接上例子,“hello world” 利用二维码的编码原理,转换成十进制数字为“32, 91, 11, 120, 209, 114, 220, 77, 67, 64, 236, 17, 236, 17, 236, 17”,因此这个语句的消息多项式为:
    32 x 15 + 91 x 14 + 11 x 13 + 120 x 12 + 209 x 11 + 114 x 10 + 220 x 9 + 77 x 8 + 67 x 7 + 64 x 6 + 236 x 5 + 17 x 4 + 236 x 3 + 17 x 2 + 236 x 1 + 17 (1) \begin{aligned} &32x^{15} + 91x^{14} + 11x^{13} + 120x^{12} + 209x^{11} + 114x^{10} + 220x^{9} + 77x^{8} + 67x^{7}\\ &+ 64x^{6} + 236x^{5} + 17x^{4} + 236x^{3} + 17x^{2} + 236x^{1} + 17 \end{aligned} \tag1 32x15+91x14+11x13+120x12+209x11+114x10+220x9+77x8+67x7+64x6+236x5+17x4+236x3+17x2+236x1+17(1)

    1.1 生成多项式

    从下面这个网址可以轻松得到 n ≥ 7 n≥7 n7的生成多项式:
    https://www.thonky.com/qr-code-tutorial/generator-polynomial-tool?degree=7

    1.2 多项式除法

    “Hello world”完整的消息多项式见公式(1),为了确保在除法期间引导项的指数不会变得太小,将消息多项式乘以 x n x^n xn n n n是所需的纠错码字的数量。如当纠错码字的数量是10时,式(1)应该变成:

    32 x 25 + 91 x 24 + 11 x 23 + 120 x 22 + 209 x 21 + 114 x 20 + 220 x 19 + 77 x 18 + 67 x 17 + 64 x 16 + 236 x 15 + 17 x 14 + 236 x 13 + 17 x 12 + 236 x 11 + 17 x 10 (2) \begin{aligned} &32x^{25} + 91x^{24} + 11x^{23} + 120x^{22} + 209x^{21} + 114x^{20} + 220x^{19} + 77x^{18} + 67x^{17} \\ &+ 64x^{16} + 236x^{15} + 17x^{14} + 236x^{13} + 17x^{12} + 236x^{11} + 17x^{10} \end{aligned} \tag2 32x25+91x24+11x23+120x22+209x21+114x20+220x19+77x18+67x17+64x16+236x15+17x14+236x13+17x12+236x11+17x10(2)

    生成多项式的前导项也应该具有相同的指数,因此生成多项式也乘 x 15 x^{15} x15得到下式:

    α 0 x 25 + α 251 x 24 + α 67 x 23 + α 46 x 22 + α 61 x 21 + α 118 x 20 + α 70 x 19 + α 64 x 18 + α 94 x 17 + α 32 x 16 + α 45 x 15 (3) \begin{aligned} &α^0x^{25} + α^{251}x^{24} + α^{67}x^{23} + α^{46}x^{22} + α^{61}x^{21} + α^{118}x^{20} + \\ &α^{70}x^{19} + α^{64}x^{18} + α^{94}x^{17} + α^{32}x^{16} + α^{45}x^{15} \end{aligned} \tag3 α0x25+α251x24+α67x23+α46x22+α61x21+α118x20+α70x19+α64x18+α94x17+α32x16+α45x15(3)

    具体除法步骤如下:
    (1)将生成多项式乘以消息多项式的前导项。
    消息多项式的前导项是32,也就是 α 5 α^5 α5,乘上生成多项式后,生成多项式变成:
    α 5 x 25 + α 256 % 255 x 24 + α 72 x 23 + α 51 x 22 + α 66 x 21 + α 123 x 20 + α 75 x 19 + α 69 x 18 + α 99 x 17 + α 37 x 16 + α 50 x 15 = α 5 x 25 + α 1 x 24 + α 72 x 23 + α 51 x 22 + α 66 x 21 + α 123 x 20 + α 75 x 19 + α 69 x 18 + α 99 x 17 + α 37 x 16 + α 50 x 15 = 32 x 25 + 2 x 24 + 101 x 23 + 10 x 22 + 97 x 21 + 197 x 20 + 15 x 19 + 47 x 18 + 134 x 17 + 74 x 16 + 5 x 15 (4) \begin{aligned} &α^5x^{25} + α^{256 \% 255}x^{24} + α^{72}x^{23} + α^{51}x^{22} + α^{66}x^{21} + α^{123}x^{20} + \\ &α^{75}x^{19} + α^{69}x^{18} + α^{99}x^{17} + α^{37}x^{16} + α^{50}x^{15} \\ &= α^5x^{25} + α^{1}x^{24} + α^{72}x^{23} + α^{51}x^{22} + α^{66}x^{21} + α^{123}x^{20} + \\ &α^{75}x^{19} + α^{69}x^{18} + α^{99}x^{17} + α^{37}x^{16} + α^{50}x^{15} \\ &= 32x^{25} + 2x^{24} + 101x^{23} + 10x^{22} + 97x^{21} + 197x^{20} + \\ &15x^{19} + 47x^{18} + 134x^{17} + 74x^{16} + 5x^{15} \end{aligned} \tag4 α5x25+α256%255x24+α72x23+α51x22+α66x21+α123x20+α75x19+α69x18+α99x17+α37x16+α50x15=α5x25+α1x24+α72x23+α51x22+α66x21+α123x20+α75x19+α69x18+α99x17+α37x16+α50x15=32x25+2x24+101x23+10x22+97x21+197x20+15x19+47x18+134x17+74x16+5x15(4)
    (2) 使用消息多项式对结果进行异或。
    从下面这个式子也可以看出来,就是消息多项式和生成多项式中相同次数的项的系数进行了异或操作,经过这个操作之后,消息多项式中最高次数的项已经没有了(因为生成多项式和消息多项式拥有完全相同的第一项,一异或就没了)。
    ( 32 ⊕ 32 ) x 25 + ( 91 ⊕ 2 ) x 24 + ( 11 ⊕ 101 ) x 23 + ( 120 ⊕ 10 ) x 22 + ( 209 ⊕ 97 ) x 21 + ( 114 ⊕ 197 ) x 20 + ( 220 ⊕ 15 ) x 19 + ( 77 ⊕ 47 ) x 18 + ( 67 ⊕ 134 ) x 17 + ( 64 ⊕ 74 ) x 16 + ( 236 ⊕ 5 ) x 15 + ( 17 ⊕ 0 ) x 14 + ( 236 ⊕ 0 ) x 13 + ( 17 ⊕ 0 ) x 12 + ( 236 ⊕ 0 ) x 11 + ( 17 ⊕ 0 ) x 10 = 0 x 25 + 89 x 24 + 110 x 23 + 114 x 22 + 176 x 21 + 183 x 20 + 211 x 19 + 98 x 18 + 197 x 17 + 10 x 16 + 233 x 15 + 17 x 14 + 236 x 13 + 17 x 12 + 236 x 11 + 17 x 10 = 89 x 24 + 110 x 23 + 114 x 22 + 176 x 21 + 183 x 20 + 211 x 19 + 98 x 18 + 197 x 17 + 10 x 16 + 233 x 15 + 17 x 14 + 236 x 13 + 17 x 12 + 236 x 11 + 17 x 10 (5) \begin{aligned} &(32 \oplus 32)x^{25} + (91 \oplus 2)x^{24} + (11 \oplus 101)x^{23} + (120 \oplus 10)x^{22} + (209 \oplus 97)x^{21} \\ &+ (114 \oplus 197)x^{20} + (220 \oplus 15)x^{19} + (77 \oplus 47)x^{18} + (67 \oplus 134)x^{17} + (64 \oplus 74)x^{16} \\ &+ (236 \oplus 5)x^{15} + (17 \oplus 0) x^{14} + (236 \oplus 0)x^{13} + (17 \oplus 0)x^{12} + (236 \oplus 0)x^{11} + (17 \oplus 0)x^{10} \\ &= 0x^{25} + 89x^{24} + 110x^{23} + 114x^{22} + 176x^{21} + 183x^{20} + 211x^{19} + 98x^{18} + 197x^{17} \\ &+ 10x^{16} + 233x^{15} + 17x^{14} + 236x^{13} + 17x^{12} + 236x^{11} + 17x^{10} \\ &= 89x^{24} + 110x^{23} + 114x^{22} + 176x^{21} + 183x^{20} + 211x^{19} + 98x^{18} + 197x^{17} \\ &+ 10x^{16} + 233x^{15} + 17x^{14} + 236x^{13} + 17x^{12} + 236x^{11} + 17x^{10} \end{aligned} \tag5 (3232)x25+(912)x24+(11101)x23+(12010)x22+(20997)x21+(114197)x20+(22015)x19+(7747)x18+(67134)x17+(6474)x16+(2365)x15+(170)x14+(2360)x13+(170)x12+(2360)x11+(170)x10=0x25+89x24+110x23+114x22+176x21+183x20+211x19+98x18+197x17+10x16+233x15+17x14+236x13+17x12+236x11+17x10=89x24+110x23+114x22+176x21+183x20+211x19+98x18+197x17+10x16+233x15+17x14+236x13+17x12+236x11+17x10(5)
    (3) 将生成多项式乘上一步的XOR结果的前导项。注意,这里的生成多项式已经经过了和现在的信息多项式等指数的过程,所以最高次是24。
    在这个例子中,前导项是 89 x 24 89x^{24} 89x24,做乘法的时候,把数字用α表示比较简单,89又等于 α 210 α^{210} α210(这个可以查表得),所以:

    ( α 210 ∗ α 0 ) x 24 + ( α 210 ∗ α 251 ) x 23 + ( α 210 ∗ α 67 ) x 22 + ( α 210 ∗ α 46 ) x 21 + ( α 210 ∗ α 61 ) x 20 + ( α 210 ∗ α 118 ) x 19 + ( α 210 ∗ α 70 ) x 18 + ( α 210 ∗ α 64 ) x 17 + ( α 210 ∗ α 94 ) x 16 + ( α 210 ∗ α 32 ) x 15 + ( α 210 ∗ α 45 ) x 14 = α 210 x 24 + α 206 x 23 + α 22 x 22 + α 1 x 21 + α 16 x 20 + α 73 x 19 + α 25 x 18 + α 19 x 17 + α 49 x 16 + α 242 x 15 + α 0 x 14 = 89 x 24 + 83 x 23 + 234 x 22 + 2 x 21 + 76 x 20 + 202 x 19 + 3 x 18 + 90 x 17 + 140 x 16 + 176 x 15 + 1 x 14 (6) \begin{aligned} & (α^{210} * α^{0})x^{24} + (α^{210} * α^{251})x^{23} + (α^{210} * α^{67})x^{22} + (α^{210} * α^{46})x^{21} \\ &+ (α^{210} * α^{61})x^{20} + (α^{210} * α^{118})x^{19} + (α^{210} * α^{70})x^{18} + (α^{210} * α^{64})x^{17} \\ &+ (α^{210} * α^{94})x^{16} + (α^{210} * α^{32})x^{15} + (α^{210} * α^{45})x^{14} \\ &= α^{210}x^{24} + α^{206}x^{23} + α^{22}x^{22} + α^{1}x^{21} + α^{16}x^{20} \\ &+ α^{73}x^{19} + α^{25}x^{18} + α^{19}x^{17} + α^{49}x^{16} + α^{242}x^{15} + α^{0}x^{14} \\ &= 89x^{24} + 83x^{23} + 234x^{22} + 2x^{21} + 76x^{20} + 202x^{19} + 3x^{18} + 90x^{17} \\ &+ 140x^{16} + 176x^{15} + 1x^{14} \end{aligned} \tag6 (α210α0)x24+(α210α251)x23+(α210α67)x22+(α210α46)x21+(α210α61)x20+(α210α118)x19+(α210α70)x18+(α210α64)x17+(α210α94)x16+(α210α32)x15+(α210α45)x14=α210x24+α206x23+α22x22+α1x21+α16x20+α73x19+α25x18+α19x17+α49x16+α242x15+α0x14=89x24+83x23+234x22+2x21+76x20+202x19+3x18+90x17+140x16+176x15+1x14(6)
    (4) 将上一步得到的式子继续重复类似步骤2的异或操作,这个操作之后,最前面那项(次数为24次的那项)又成功没有了。
    那么重复到什么时候好呢?从上面可以看出来,循环一次,就有一个消息多项式中的一项被消除,所以消息多项式有多少项,就进行多少次循环(这就好像除法进行到了最后一位)。上述例子循环16次后,就得到了下面这个式子(从这个式子中我们就可以看出来,刚开始的时候乘x^10有多明智,为什么是10而不是9或者8也从这里可以看出,因为生成多项式的最高次数是纠错码字的数目,一项项异或之后,最后的余数的位数和生成多项式的位数是相关的)

    196 x 9 + 35 x 8 + 39 x 7 + 119 x 6 + 235 x 5 + 215 x 4 + 231 x 3 + 226 x 2 + 93 x 1 + 23 (7) \begin{aligned} &196x^{9} + 35x^{8} + 39x^{7} \\ &+ 119x^{6} + 235x^{5} + 215x^{4} + 231x^{3} + 226x^{2} + 93x^{1} + 23 \end{aligned} \tag7 196x9+35x8+39x7+119x6+235x5+215x4+231x3+226x2+93x1+23(7)

    现在我们就得到纠错码字了:196 35 39 119 235 215 231 226 93 23
    得到纠错码字之后就是按照规范给填到二维码的格子里面。

    2 如何进行纠错?

    二维码采用Reed-Solomon Codes(简称RS编码)进行纠错。

    2.1 RS编码

    RS编码以word为编码和解码单位,大的数据块拆分到字长为 w w w(取值一般为8或者16位)的word,然后对word进行编解码。 数据块的编码原理与word编码原理相同,后文中以word为例说明,变量 D i \mathrm{D_i} Di, C j \mathrm{C_j} Cj将分别代表第 i i i个数据码和第 j j j个纠错码(以word为单位)。
    输入数据为向量 D = ( D 1 , D 2 , … , D n ) \mathrm{D} =(\mathrm{D_1},\mathrm{D_2},\dots, \mathrm{D_n}) D=(D1D2,Dn),编码后为向量 ( D 1 , D 2 , … , D n , C 1 , C 2 , … , C m ) (\mathrm{D_1},\mathrm{D_2},\dots, \mathrm{D_n}, \mathrm{C_1}, \mathrm{C_2}, \dots, \mathrm{C_m}) (D1D2,Dn,C1,C2,,Cm),RS编码可表示为如下图所示矩阵运算:

    图1 RS编码示意图

    上图最左边是编码矩阵(或称为生成矩阵、分布矩阵,Distribution Matrix),编码矩阵需要满足任意 n × n n \times n n×n子矩阵可逆。

    为方便数据存储,编码矩阵上部是单位阵( n n n n n n列),下部是 m m m n n n列矩阵。下部矩阵可以选择范德蒙德矩阵柯西矩阵。后文说明。

    2.2 RS编码数据恢复原理

    RS最多能容忍 k k k个数据块被删除。 数据恢复的过程如下:
    (1)假设 D 1 \mathrm{D_1} D1 D 4 \mathrm{D_4} D4 C 2 \mathrm{C_2} C2丢失,从编码矩阵中删掉丢失的数据块/编码块对应的行。

    图2 数据缺失情况

    (2)根据图1所示RS编码运算等式,可以得到如下 B ′ \mathrm{B'} B以及等式。

    图3 数据缺失后的编码矩阵

    (3)由于 B ′ \mathrm{B'} B是可逆的,记 B ′ \mathrm{B'} B的逆矩阵为 B ′ − 1 \mathrm{B'}^{-1} B1,则 B ′ × B ′ − 1 = I \mathrm{B'} \times \mathrm{B'}^{-1} = \mathrm{I} B×B1=I 单位矩阵。两边左乘 B ′ \mathrm{B'} B逆矩阵 B ′ − 1 \mathrm{B'}^{-1} B1后如下图:

    图4 左乘逆矩阵的结果

    (4)得到如下原始数据 D \mathrm{D} D的计算公式:

    图5 计算机原始数据

    恢复原始数据 D \mathrm{D} D

    图6 计算机原始数据

    (5)对 D \mathrm{D} D重新编码,可得到丢失的编码。

    3 下一步工作

    下一步将讨论范德蒙德(Vandermonde)矩阵和柯西( Cauchy)矩阵。

    展开全文
  • 二维码纠错率的问题

    2015-09-30 13:21:00
    调高级别,纠错能力也相应提高,但由于数据量会随之增加,编码尺寸也也会变大。  用户应综合考虑使用环境、编码尺寸等因素后选择相应的级别。 在工厂等容易沾染赃物的环境下,可以选择级别Q或H,在不那么脏的环境下...

    纠错功能

    返回 什么是QR码? 首页

    QR码具有“纠错功能”。即使编码变脏或破损,也可自动恢复数据。这一“纠错能力”具备4个级别,用户可根据使用环境选择相应的级别。调高级别,纠错能力也相应提高,但由于数据量会随之增加,编码尺寸也也会变大。 
    用户应综合考虑使用环境、编码尺寸等因素后选择相应的级别。 在工厂等容易沾染赃物的环境下,可以选择级别Q或H,在不那么脏的环境下,且数据量较多的时候,也可以选择级别L。一般情况下用户大多选择级别M(15%)。

    30132134_H3ku.png

    ※相对于全部码字(组成数据的单位,在QR码中,1码字对应于8比特)的恢复率

    纠错功能的机制

    纠错级别的比率,是指全部码字与可以纠错的码字的比率。
    例如,需要编码的码字数据有100个,并且想对其中的一半,也就是50个码字进行纠错,则计算方法如下。纠错需要相当于码字2倍的符号(RS编码※),因此在这种情况下的数量为50个×2=100码字。因此,全部码字数量为200个,其中用作纠错的码字为50个,所以计算得出,相对于全部码字的纠错率就是25%。这一比率相当于QR码纠错级别中的“Q”级别。

    另外,在上述例子当中,也可以认为相对于码字数据的纠错率为50%,但变脏或破损的部位不仅仅局限于码字数据部分,因此,在QR码中,还是用相对于全部码字的比率来描述纠错率。

    ※ RS编码:QR码的纠错功能是通过将RS编码附加到原数据中的方式实现的。RS编码是应用于音乐CD等用途的数学纠错方法。它能以字节为单位进行纠错,适合用于错误位置会集中的突发错误。

    转载于:https://my.oschina.net/u/1788620/blog/512800

    展开全文
  • 假设:原始数据为8位,纠错码为6位,原始信息由原始数据+纠错码。 在传输过程中,由于信息干扰等原因,导致原始信息被污染,被污染后有两位数据被修改。 说明 编码 原始信息 001010011011100 被污染后的...

    1 例子

    假设:原始数据为8位,纠错码为6位,原始信息由原始数据+纠错码。
    在传输过程中,由于信息干扰等原因,导致原始信息被污染,被污染后有两位数据被修改。

    说明编码
    原始信息001010011011100
    被污染后的信息001100011011100

    2 构建码字多项式

    根据接收到被污染后的信息转化为码字多项式:
    R ( x ) = x 12 + x 11 + x 7 + x 6 + x 4 + x 3 + x 2 (1) R(x) = x^{12} +x^{11} + x^{7} + x^{6} + x^{4} + x^{3} + x^{2} \tag1 R(x)=x12+x11+x7+x6+x4+x3+x2(1)

    3 计算特征值

    α \alpha α代入公式(1)得到:
    S 1 = R ( α ) = α 12 + α 11 + α 7 + α 6 + α 4 + α 3 + α 2 = α 214 S_1 = R(\alpha) = \alpha^{12} +\alpha^{11} + \alpha^{7} + \alpha^{6} + \alpha^{4} + \alpha^{3} + \alpha^{2} = \alpha^{214} S1=R(α)=α12+α11+α7+α6+α4+α3+α2=α214
    α 3 \alpha^3 α3代入公式(1)得到:
    S 3 = R ( α 3 ) = α 36 + α 33 + α 21 + α 18 + α 12 + α 9 + α 6 = α 117 S_3 = R(\alpha^3) = \alpha^{36} +\alpha^{33} + \alpha^{21} + \alpha^{18} + \alpha^{12} + \alpha^{9} + \alpha^{6} = \alpha^{117} S3=R(α3)=α36+α33+α21+α18+α12+α9+α6=α117
    α 5 \alpha^5 α5代入公式(1)得到:
    S 5 = R ( α 5 ) = α 60 + α 55 + α 35 + α 30 + α 20 + α 15 + α 10 = α 25 S_5 = R(\alpha^5) = \alpha^{60} +\alpha^{55} + \alpha^{35} + \alpha^{30} + \alpha^{20} + \alpha^{15} + \alpha^{10} = \alpha^{25} S5=R(α5)=α60+α55+α35+α30+α20+α15+α10=α25
    计算 S 2 , S 4 , S 6 S_2,S_4,S_6 S2,S4,S6
    S 2 = S 1 2 = α 173 , S 4 = S 2 2 = α 91 , S 6 = S 3 2 = α 182 S_2 = S_1^2 = \alpha^{173}, S_4 = S_2^2 = \alpha^{91}, S_6 = S_3^2 = \alpha^{182} S2=S12=α173,S4=S22=α91,S6=S32=α182

    4 根据特征值进行纠错

    因为不知道有多少位有错,也不知道错在什么位置,根据纠错码的纠错能力进行穷举。由于纠错码为6位,则纠错能力为 m ≤ ⌊ 6 / 2 ⌋ m \leq \lfloor 6/2 \rfloor m6/2,即 m ≤ 3 m \leq 3 m3,然后从大到小进行穷举,即 m ∈ [ 1 , 3 ] m \in [1, 3] m[1,3]
    先取 m = 3 m = 3 m=3,构建矩阵运算:
    [ S 3 S 2 S 1 S 4 S 3 S 2 S 5 S 4 S 3 ] [ σ 1 σ 2 σ 3 ] = [ S 4 S 5 S 6 ] \left[ \begin{matrix} S_3 &S_2 &S_1 \\ S_4 &S_3 &S_2 \\ S_5 &S_4 &S_3 \\ \end{matrix} \right] \left[ \begin{matrix} \sigma_1 \\ \sigma_2 \\ \sigma_3 \\ \end{matrix} \right] = \left[ \begin{matrix} S_4 \\ S_5 \\ S_6 \\ \end{matrix} \right] S3S4S5S2S3S4S1S2S3σ1σ2σ3=S4S5S6
    代入 S 1 , S 2 , … , S 6 S_1, S_2, \dots, S_6 S1,S2,,S6,并计算行列式:
    ∣ α 117 α 173 α 214 α 91 α 117 α 173 α 25 α 91 α 117 ∣ = 0 \left| \begin{matrix} \alpha^{117} &\alpha^{173} &\alpha^{214} \\ \alpha^{91} &\alpha^{117} &\alpha^{173} \\ \alpha^{25} &\alpha^{91} &\alpha^{117} \\ \end{matrix} \right|= 0 α117α91α25α173α117α91α214α173α117=0
    说明不超过3位,然后取 m = 2 m = 2 m=2,构建矩阵运算:
    [ S 3 S 2 S 4 S 3 ] [ σ 1 σ 2 ] = [ S 4 S 5 ] \left[ \begin{matrix} S_3 &S_2 \\ S_4 &S_3 \\ \end{matrix} \right] \left[ \begin{matrix} \sigma_1 \\ \sigma_2 \\ \end{matrix} \right] = \left[ \begin{matrix} S_4 \\ S_5 \\ \end{matrix} \right] [S3S4S2S3][σ1σ2]=[S4S5]
    代入 S 1 , S 2 , … , S 6 S_1, S_2, \dots, S_6 S1,S2,,S6,并计算行列式:
    ∣ α 117 α 173 α 91 α 117 ∣ = α 45 \left| \begin{matrix} \alpha^{117} &\alpha^{173} \\ \alpha^{91} &\alpha^{117} \\ \end{matrix} \right|= \alpha^{45} α117α91α173α117=α45
    满秩,方程组有解答,经过计算得到:
    σ 1 = α 35 , σ 2 = α 21 \sigma_1 = \alpha^{35}, \sigma_2 = \alpha^{21} σ1=α35σ2=α21
    代入错误多项式得:
    α 21 x 2 + α 35 x + 1 = 0 \alpha^{21}x^2 + \alpha^{35}x + 1 = 0 α21x2+α35x+1=0
    用Chien搜索可得 x 1 = x − 10 , x 2 = x − 11 x_1 = x^{-10}, x_2 = x^{-11} x1=x10,x2=x11,所以错误位置应该是第10位和第11位。

    5 存在问题

    这个例子还有几个核心问题没有解决:
    (1)为什么要计算特征值?(是否会用到范德蒙矩阵或者柯西矩阵的知识?)
    (2)有了特征值又如何进行纠错?

    展开全文
  • 下面进一步介绍二维码纠错相关的编码矩阵 1 范德蒙德(Vandermonde)矩阵 在线性代数中有一种矩阵称为范德蒙德矩阵,它的任意的子方阵均为可逆方阵。一个mmm行nnn列的范德蒙德矩阵定义如下,其中aia_iai​ 均不相同...

    下面进一步介绍二维码纠错相关的编码矩阵

    1 范德蒙德(Vandermonde)矩阵

    1.1 定义及特性

    法国数学家 Alexandre-Théophile Vandermonde 在十八世纪提出了行列式的概念, 用来解决线性方程组问题, 其中一个关键是范德蒙德(Vandermonde) 矩阵, Vandermonde 矩阵具有如下的形式:
    A n = [ 1 1 1 … 1 x 1 1 x 2 1 x 3 1 … x n 1 x 1 2 x 2 2 x 3 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 3 n − 1 … x n n − 1 ] (1) \mathrm{A_n} = \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_3^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_3^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_3^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right] \tag1 An=1x11x12x1n11x21x22x2n11x31x32x3n11xn1xn2xnn1(1)
    它的任意的子方阵均为可逆方阵。一个 n n n n n n列的范德蒙德矩阵定义如下,其中 x i x_i xi 均不相同,且不为0。Vandermonde 矩阵有一个很重要的特性:
    ∣ A n ∣ = ∣ A n T ∣ = ∏ 1 ≤ i ≤ j ≤ n ( x j − x i ) (2) |\mathrm{A_n}| = |\mathrm{A_n^T}| = \prod_{1 \leq i \leq j \leq n}(x_j - x_i) \tag2 An=AnT=1ijn(xjxi)(2)
    例子1:
    如下范德蒙矩阵
    A n = [ 1 1 1 2 3 5 2 2 3 2 5 2 ] \mathrm{A_n} = \left[ \begin{matrix} 1 &1 & 1 \\ 2 & 3 &5 \\ 2^2 & 3^2 &5^2 \\ \end{matrix} \right] An=122213321552
    那么它的行列式为 ∣ A n ∣ = ( 3 − 2 ) ∗ ( 5 − 2 ) ∗ ( 5 − 3 ) = 6 \left|A_n\right|=(3-2)*(5-2)*(5-3)=6 An=(32)(52)(53)=6.
    例子2:
    如下范德蒙矩阵
    A n = [ 1 1 1 1 2 3 5 7 2 2 3 2 5 2 7 2 2 3 3 3 5 3 7 3 ] \mathrm{A_n} = \left[ \begin{matrix} 1 &1 & 1 &1\\ 2 & 3 &5 &7\\ 2^2 & 3^2 &5^2 &7^2\\ 2^3 & 3^3 &5^3 &7^3\\ \end{matrix} \right] An=122223133233155253177273
    那么它的行列式为 ∣ A n ∣ = ( 3 − 2 ) ∗ ( 5 − 2 ) ∗ ( 7 − 2 ) ∗ ( 5 − 3 ) ∗ ( 7 − 3 ) ∗ ( 7 − 5 ) = 240 \left|A_n\right|=(3-2)*(5-2)*(7-2)*(5-3)*(7-3)*(7-5)=240 An=(32)(52)(72)(53)(73)(75)=240.
    这个特性可以用数学归纳法证明出来。
    【证明】
    D n D_n Dn n n n阶Vandermonde行列式( n ≥ 2 n \geq 2 n2),则有
    D n = ∏ 1 ≤ i ≤ j ≤ n ( x j − x i ) = ( x n − x n − 1 ) ( x n − x n − 2 ) … ( x n − x 1 ) ( x n − 1 − x n − 2 ) ( x n − 1 − x n − 3 ) … ( x n − 1 − x 1 ) … ( x 3 − x 2 ) ( x 3 − x 1 ) ( x 2 − x 1 ) . D_n = \prod_{1 \leq i \leq j \leq n}(x_j - x_i) = (x_n - x_{n-1})(x_n - x_{n-2})\dots(x_n - x_1)(x_{n-1} - x_{n-2}) \\ (x_{n-1} - x_{n-3})\dots(x_{n-1} - x_1)\dots(x_3 - x_2)(x_3 - x_1)(x_2 - x_1). Dn=1ijn(xjxi)=(xnxn1)(xnxn2)(xnx1)(xn1xn2)(xn1xn3)(xn1x1)(x3x2)(x3x1)(x2x1).
    (1) 当 n = 2 n = 2 n=2时, D 2 = ∣ 1 1 x 1 x 2 ∣ = ( x 2 − x 1 ) D_2 = \left|\begin{matrix}1 &1 \\ x_1 &x_2\end{matrix}\right| = (x_2 - x_1) D2=1x11x2=(x2x1),结论成立;
    (2) 假设结论对 n − 1 n - 1 n1阶范德蒙德行列式成立,即
    D n − 1 = ∣ 1 1 … 1 x 2 1 x 3 1 … x n 1 x 2 2 x 3 2 … x n 2 ⋮ ⋮ ⋱ ⋮ x 2 n − 2 x 3 n − 2 … x n n − 2 ∣ = ∏ 2 ≤ i ≤ j ≤ n ( x j − x i ) D_{n-1} = \left| \begin{matrix} 1 & 1 &\dots & 1 \\ x_2^1 &x_3^1 & \dots &x_n^1 \\ x_2^2 &x_3^2 & \dots &x_n^2 \\ \vdots &\vdots & \ddots &\vdots \\ x_2^{n-2} &x_3^{n-2} & \dots &x_n^{n-2} \\ \end{matrix} \right| = \prod_{2 \leq i \leq j \leq n}(x_j - x_i) Dn1=1x21x22x2n21x31x32x3n21xn1xn2xnn2=2ijn(xjxi)
    考虑 n n n阶范德蒙行列式的情形:
    D n = ∣ 1 1 1 … 1 x 1 1 x 2 1 x 3 1 … x n 1 x 1 2 x 2 2 x 3 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 3 n − 1 … x n n − 1 ∣ D_{n} = \left| \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_3^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_3^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_3^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right| Dn=1x11x12x1n11x21x22x2n11x31x32x3n11xn1xn2xnn1
    从第 n n n行开始,自下而上依次的由下一行减去它上一行的 x 1 x_1 x1倍 ,有:
    D n = ∣ 1 1 1 … 1 0 x 2 − x 1 x 3 − x 1 … x n − x 1 0 x 2 2 − x 2 x 1 x 3 2 − x 3 x 1 … x n 2 − x n x 1 ⋮ ⋮ ⋮ ⋱ ⋮ 0 x 2 n − 1 − x 2 n − 2 x 1 x 3 n − 1 − x 3 n − 2 x 1 … x n n − 1 − x n n − 2 x 1 ∣ = ∣ 1 1 1 … 1 0 x 2 − x 1 x 3 − x 1 … x n − x 1 0 x 2 ( x 2 − x 1 ) x 3 ( x 3 − x 1 ) … x n ( x n − x 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 0 x 2 n − 2 ( x 2 − x 1 ) x 3 n − 2 ( x 3 − x 1 ) … x n n − 2 ( x n − x 1 ) ∣ D_{n} = \left| \begin{matrix} 1 &1 & 1 &\dots & 1 \\ 0 & x_2- x_1 &x_3 - x_1 & \dots &x_n-x_1 \\ 0 & x_2^2-x_2x_1 &x_3^2-x_3x_1 & \dots &x_n^2-x_nx_1 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ 0 & x_2^{n-1}-x_2^{n-2}x_1 &x_3^{n-1}-x_3^{n-2}x_1 & \dots &x_n^{n-1}-x_n^{n-2}x_1 \\ \end{matrix} \right|\\ =\left| \begin{matrix} 1 &1 & 1 &\dots & 1 \\ 0 & x_2- x_1 &x_3 - x_1 & \dots &x_n-x_1 \\ 0 & x_2(x_2-x_1) &x_3(x_3-x_1) & \dots &x_n(x_n-x_1) \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ 0 & x_2^{n-2}(x_2-x_1) &x_3^{n-2}(x_3-x_1) & \dots &x_n^{n-2}(x_n-x_1) \\ \end{matrix} \right| Dn=10001x2x1x22x2x1x2n1x2n2x11x3x1x32x3x1x3n1x3n2x11xnx1xn2xnx1xnn1xnn2x1=10001x2x1x2(x2x1)x2n2(x2x1)1x3x1x3(x3x1)x3n2(x3x1)1xnx1xn(xnx1)xnn2(xnx1)
    按第一列展开后提取公因式,得
    D n = ( x 2 − x 1 ) ( x 3 − x 1 ) … ( x n − x 1 ) ∣ 1 1 … 1 x 2 x 3 … x n ⋮ ⋮ ⋱ ⋮ x 2 n − 2 x 3 n − 2 … x n n − 2 ∣ = ( x 2 − x 1 ) ( x 3 − x 1 ) … ( x n − x 1 ) ∏ 2 ≤ i ≤ j ≤ n ( x j − x i ) = ∏ 1 ≤ i ≤ j ≤ n ( x j − x i ) D_{n} = (x_2 - x_1)(x_3 - x_1)\dots(x_n - x_1) \left| \begin{matrix} 1 &1 &\dots & 1 \\ x_2 & x_3 & \dots &x_n \\ \vdots & \vdots & \ddots &\vdots \\ x_2^{n-2} & x_3^{n-2} & \dots &x_n^{n-2} \\ \end{matrix} \right| \\ = (x_2 - x_1)(x_3 - x_1)\dots(x_n - x_1)\prod_{2 \leq i \leq j \leq n}(x_j - x_i) =\prod_{1 \leq i \leq j \leq n}(x_j - x_i) Dn=(x2x1)(x3x1)(xnx1)1x2x2n21x3x3n21xnxnn2=(x2x1)(x3x1)(xnx1)2ijn(xjxi)=1ijn(xjxi)
    得证。

    1.2 Vandermonde矩阵的理解

    在差值(interpolation)问题中, 假设在二维空间有 n n n 个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) (x_1,y_1), (x_2,y_2), \dots, (x_n,y_n) (x1,y1),(x2,y2),,(xn,yn), 希望得到一个多项式解:
    p ( x ) = d n x n − 1 + d n − 1 x n − 2 + ⋯ + d 2 x + d 1 (3) p(x) = d_{n}x^{n-1} + d_{n-1}x^{n-2} + \dots + d_2x+ d_1 \tag3 p(x)=dnxn1+dn1xn2++d2x+d1(3)
    这个多项式可以满足我们的当前条件:
    p ( x 1 ) = y 1 = d n x 1 n − 1 + d n − 1 x 1 n − 2 + ⋯ + d 2 x 1 + d 1 p ( x 2 ) = y 2 = d n x 2 n − 1 + d n − 1 x 2 n − 2 + ⋯ + d 2 x 2 + d 1 … p ( x n ) = y n = d n x n n − 1 + d n − 1 x n n − 2 + ⋯ + d 2 x n + d 1 p(x_1) = y_1 = d_{n}x_1^{n-1} + d_{n-1}x_1^{n-2} + \dots + d_2x_1 + d_1 \\ p(x_2) = y_2 = d_{n}x_2^{n-1} + d_{n-1}x_2^{n-2} + \dots + d_2x_2 + d_1 \\ \dots \\ p(x_n) = y_n = d_{n}x_n^{n-1} + d_{n-1}x_n^{n-2} + \dots + d_2x_n + d_1 p(x1)=y1=dnx1n1+dn1x1n2++d2x1+d1p(x2)=y2=dnx2n1+dn1x2n2++d2x2+d1p(xn)=yn=dnxnn1+dn1xnn2++d2xn+d1
    实际上, 可以推演如下:
    y = [ y 1 y 2 ⋮ y n ] = [ d 1 + d 2 x 1 + d 3 x 1 2 ⋯ + d n x 1 n − 1 d 1 + d 2 x 2 + d 3 x 2 2 ⋯ + d n x 2 n − 1 ⋮ d 1 + d 2 x n + d 3 x n 2 ⋯ + d n x n n − 1 ] = [ 1 1 1 … 1 x 1 1 x 2 1 x 2 1 … x n 1 x 1 2 x 2 2 x 2 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 2 n − 1 … x n n − 1 ] T ∗ [ 1 d 2 ⋮ d n ] = A T ∗ [ y 1 y 2 ⋮ y n ] (4) y = \left[ \begin{matrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{matrix} \right] = \left[ \begin{matrix} d_1 + d_2x_1 + d_3x_1^2 \dots + d_nx_1^{n - 1} \\ d_1 + d_2x_2 + d_3x_2^2 \dots + d_nx_2^{n - 1} \\ \vdots \\ d_1 + d_2x_n + d_3x_n^2 \dots + d_nx_n^{n - 1} \\ \end{matrix} \right] \\ = \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_2^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_2^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_2^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right]^\mathrm{T} * \left[ \begin{matrix} _1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] = \mathrm{A^\mathrm{T} } * \left[ \begin{matrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{matrix} \right] \tag4 y=y1y2yn=d1+d2x1+d3x12+dnx1n1d1+d2x2+d3x22+dnx2n1d1+d2xn+d3xn2+dnxnn1=1x11x12x1n11x21x22x2n11x21x22x2n11xn1xn2xnn1T1d2dn=ATy1y2yn(4)
    还可以表示如下:
    [ d 1 d 2 ⋮ d n ] = ( A T ) − 1 y (5) \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] = (\mathrm{A^T})^{-1} y \tag5 d1d2dn=(AT)1y(5)
    x 1 = 1 , x 2 = 2 , x 3 = 3 , … , x n = n x_1 = 1, x_2 = 2, x_3 = 3, \dots, x_n = n x1=1,x2=2,x3=3,,xn=n, 则有:
    A = [ 1 1 1 … 1 1 2 3 … n 1 2 2 2 3 2 … n 2 ⋮ ⋮ ⋮ ⋱ ⋮ 1 n − 1 2 n − 1 3 n − 1 … n n − 1 ] (6) \mathrm{A} = \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ 1 & 2 &3 & \dots &n \\ 1^2 & 2^2 &3^2 & \dots &n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ 1^{n-1} & 2^{n-1} &3^{n-1} & \dots &n^{n-1} \\ \end{matrix} \right] \tag6 A=11121n112222n113323n11nn2nn1(6)

    1.3 Vandermonde矩阵在最小二乘拟合中的应用

    假设对 n n n个采样点进行拟合,那么方差可以表示为:

    R 2 = ∑ i = 1 n [ y i − ( d 1 + d 2 x i + d 3 x i 2 ⋯ + d n x i n − 1 ) ] 2 R^2 = \sum_{i=1}^{n}[y_i - (d_1 + d_2x_i + d_3x_i^2 \dots + d_nx_i^{n - 1})]^2 R2=i=1n[yi(d1+d2xi+d3xi2+dnxin1)]2

    为求得方差的最小值,对 d 1 , … , d n d_1, \dots, d_n d1,,dn求偏导:
    ∂ ( R 2 ) ∂ ( d 1 ) = − 2 ∑ i = 1 n [ y − ( d 1 + d 2 x + d 3 x 2 ⋯ + d n x n − 1 ) ] = 0 ∂ ( R 2 ) ∂ ( d 2 ) = − 2 ∑ i = 1 n [ y − ( d 1 + d 2 x + d 3 x 2 ⋯ + d n x n − 1 ) ] x = 0 … ∂ ( R 2 ) ∂ ( d n ) = − 2 ∑ i = 1 n [ y − ( d 1 + d 2 x + d 3 x 2 ⋯ + d n x n − 1 ) ] x n − 1 = 0 \frac{\partial(R^2)}{\partial(d_1)} = -2\sum_{i=1}^{n}[y - (d_1 + d_2x + d_3x^2 \dots + d_nx^{n - 1})] = 0\\ \frac{\partial(R^2)}{\partial(d_2)} = -2\sum_{i=1}^{n}[y - (d_1 + d_2x + d_3x^2 \dots + d_nx^{n - 1})]x = 0 \\ \dots \\ \frac{\partial(R^2)}{\partial(d_n)} = -2\sum_{i=1}^{n}[y - (d_1 + d_2x + d_3x^2 \dots + d_nx^{n - 1})]x^{n-1} = 0 \\ (d1)(R2)=2i=1n[y(d1+d2x+d3x2+dnxn1)]=0(d2)(R2)=2i=1n[y(d1+d2x+d3x2+dnxn1)]x=0(dn)(R2)=2i=1n[y(d1+d2x+d3x2+dnxn1)]xn1=0
    移项:
    d 1 n + d 2 ∑ i = 1 n x i + d 3 ∑ i = 1 n x i 2 + ⋯ + d n ∑ i = 1 n x i n − 1 ) ] = ∑ i = 1 n y i d 1 ∑ i = 1 n x i + d 2 ∑ i = 1 n x i 2 + d 3 ∑ i = 1 n x i 3 + ⋯ + d n ∑ i = 1 n x i n ) ] = ∑ i = 1 n x i y i … d 1 ∑ i = 1 n x i n − 1 + d 2 ∑ i = 1 n x i n + d 3 ∑ i = 1 n x i n + 1 + ⋯ + d n ∑ i = 1 n x i 2 n − 2 = ∑ i = 1 n x i n − 1 y i d_1n + d_2\sum_{i=1}^{n}x_i + d_3\sum_{i=1}^{n}x_i^2 + \dots + d_n\sum_{i=1}^{n}x_i^{n - 1})] = \sum_{i=1}^{n}y_i \\ d_1\sum_{i=1}^{n}x_i + d_2\sum_{i=1}^{n}x_i^2 + d_3\sum_{i=1}^{n}x_i^3 + \dots + d_n\sum_{i=1}^{n}x_i^{n})] = \sum_{i=1}^{n}x_iy_i \\ \dots \\ d_1\sum_{i=1}^{n}x_i^{n-1} + d_2\sum_{i=1}^{n}x_i^{n} + d_3\sum_{i=1}^{n}x_i^{n+1} + \dots + d_n\sum_{i=1}^{n}x_i^{2n-2} = \sum_{i=1}^{n}x_i^{n-1}y_i \\ d1n+d2i=1nxi+d3i=1nxi2++dni=1nxin1)]=i=1nyid1i=1nxi+d2i=1nxi2+d3i=1nxi3++dni=1nxin)]=i=1nxiyid1i=1nxin1+d2i=1nxin+d3i=1nxin+1++dni=1nxi2n2=i=1nxin1yi
    用矩阵表示如下
    [ n ∑ i = 1 n x i ∑ i = 1 n x i 2 … ∑ i = 1 n x i n − 1 ∑ i = 1 n x i ∑ i = 1 n x i 2 ∑ i = 1 n x i 3 … ∑ i = 1 n x i n ⋮ ⋮ ⋮ ⋱ ⋮ ∑ i = 1 n x i n − 1 ∑ i = 1 n x i n ∑ i = 1 n x i n + 1 … ∑ i = 1 n x i 2 n − 2 ] ∗ [ d 1 d 2 ⋮ d n ] = [ 1 1 1 … 1 x 1 1 x 2 1 x 2 1 … x n 1 x 1 2 x 2 2 x 2 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 2 n − 1 … x n n − 1 ] ∗ [ y 1 y 2 ⋮ y n ] \left[ \begin{matrix} n &\sum_{i=1}^{n}x_i & \sum_{i=1}^{n}x_i^2 &\dots & \sum_{i=1}^{n}x_i^{n-1} \\ \sum_{i=1}^{n}x_i & \sum_{i=1}^{n}x_i^2 & \sum_{i=1}^{n}x_i^3 & \dots & \sum_{i=1}^{n}x_i^{n} \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ \sum_{i=1}^{n}x_i^{n-1} & \sum_{i=1}^{n}x_i^n & \sum_{i=1}^{n}x_i^{n+1} & \dots & \sum_{i=1}^{n}x_i^{2n-2} \\ \end{matrix} \right] * \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] = \\ \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_2^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_2^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_2^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right] * \left[ \begin{matrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{matrix} \right] ni=1nxii=1nxin1i=1nxii=1nxi2i=1nxini=1nxi2i=1nxi3i=1nxin+1i=1nxin1i=1nxini=1nxi2n2d1d2dn=1x11x12x1n11x21x22x2n11x21x22x2n11xn1xn2xnn1y1y2yn
    对其进行变形,得到:
    [ 1 1 1 … 1 x 1 1 x 2 1 x 2 1 … x n 1 x 1 2 x 2 2 x 2 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 2 n − 1 … x n n − 1 ] [ 1 1 1 … 1 x 1 1 x 2 1 x 2 1 … x n 1 x 1 2 x 2 2 x 2 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 2 n − 1 … x n n − 1 ] T [ d 1 d 2 ⋮ d n ] = [ 1 1 1 … 1 x 1 1 x 2 1 x 2 1 … x n 1 x 1 2 x 2 2 x 2 2 … x n 2 ⋮ ⋮ ⋮ ⋱ ⋮ x 1 n − 1 x 2 n − 1 x 2 n − 1 … x n n − 1 ] [ y 1 y 2 ⋮ y n ] \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_2^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_2^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_2^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right] \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_2^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_2^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_2^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right]^{\mathrm{T}} \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right]=\\ \left[ \begin{matrix} 1 &1 & 1 &\dots & 1 \\ x_1^1 & x_2^1 &x_2^1 & \dots &x_n^1 \\ x_1^2 & x_2^2 &x_2^2 & \dots &x_n^2 \\ \vdots & \vdots &\vdots & \ddots &\vdots \\ x_1^{n-1} & x_2^{n-1} &x_2^{n-1} & \dots &x_n^{n-1} \\ \end{matrix} \right] \left[ \begin{matrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{matrix} \right] 1x11x12x1n11x21x22x2n11x21x22x2n11xn1xn2xnn11x11x12x1n11x21x22x2n11x21x22