郑州网站优化工资,如何建立一个自己的网站?,网络促销的方法有哪些,河南住房和城乡建设厅网站特种下面进一步介绍二维码纠错相关的编码矩阵
1 范德蒙德#xff08;Vandermonde#xff09;矩阵
1.1 定义及特性
法国数学家 Alexandre-Thophile Vandermonde 在十八世纪提出了行列式的概念, 用来解决线性方程组问题, 其中一个关键是范德蒙德(Vandermonde) 矩阵, Vandermonde…下面进一步介绍二维码纠错相关的编码矩阵
1 范德蒙德Vandermonde矩阵
1.1 定义及特性
法国数学家 Alexandre-Théophile Vandermonde 在十八世纪提出了行列式的概念, 用来解决线性方程组问题, 其中一个关键是范德蒙德(Vandermonde) 矩阵, Vandermonde 矩阵具有如下的形式: An[111…1x11x21x31…xn1x12x22x32…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x3n−1…xnn−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⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x31x32⋮x3n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤(1) 它的任意的子方阵均为可逆方阵。一个nnn行nnn列的范德蒙德矩阵定义如下其中xix_ixi 均不相同且不为0。Vandermonde 矩阵有一个很重要的特性: ∣An∣∣AnT∣∏1≤i≤j≤n(xj−xi)(2)|\mathrm{A_n}| |\mathrm{A_n^T}| \prod_{1 \leq i \leq j \leq n}(x_j - x_i) \tag2∣An∣∣AnT∣1≤i≤j≤n∏(xj−xi)(2) 例子1 如下范德蒙矩阵 An[111235223252]\mathrm{A_n} \left[ \begin{matrix} 1 1 1 \\ 2 3 5 \\ 2^2 3^2 5^2 \\ \end{matrix} \right] An⎣⎡122213321552⎦⎤ 那么它的行列式为∣An∣(3−2)∗(5−2)∗(5−3)6\left|A_n\right|(3-2)*(5-2)*(5-3)6∣An∣(3−2)∗(5−2)∗(5−3)6. 例子2 如下范德蒙矩阵 An[111123572232527223335373]\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⎦⎥⎥⎤ 那么它的行列式为∣An∣(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∣(3−2)∗(5−2)∗(7−2)∗(5−3)∗(7−3)∗(7−5)240. 这个特性可以用数学归纳法证明出来。 【证明】 若DnD_nDn为nnn阶Vandermonde行列式(n≥2n \geq 2n≥2)则有 Dn∏1≤i≤j≤n(xj−xi)(xn−xn−1)(xn−xn−2)…(xn−x1)(xn−1−xn−2)(xn−1−xn−3)…(xn−1−x1)…(x3−x2)(x3−x1)(x2−x1).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). Dn1≤i≤j≤n∏(xj−xi)(xn−xn−1)(xn−xn−2)…(xn−x1)(xn−1−xn−2)(xn−1−xn−3)…(xn−1−x1)…(x3−x2)(x3−x1)(x2−x1). (1) 当n2n 2n2时 D2∣11x1x2∣(x2−x1)D_2 \left|\begin{matrix}1 1 \\ x_1 x_2\end{matrix}\right| (x_2 - x_1)D2∣∣∣∣1x11x2∣∣∣∣(x2−x1)结论成立 (2) 假设结论对n−1n - 1n−1阶范德蒙德行列式成立即 Dn−1∣11…1x21x31…xn1x22x32…xn2⋮⋮⋱⋮x2n−2x3n−2…xnn−2∣∏2≤i≤j≤n(xj−xi)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) Dn−1∣∣∣∣∣∣∣∣∣∣∣1x21x22⋮x2n−21x31x32⋮x3n−2………⋱…1xn1xn2⋮xnn−2∣∣∣∣∣∣∣∣∣∣∣2≤i≤j≤n∏(xj−xi) 考虑nnn阶范德蒙行列式的情形: Dn∣111…1x11x21x31…xn1x12x22x32…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x3n−1…xnn−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∣∣∣∣∣∣∣∣∣∣∣1x11x12⋮x1n−11x21x22⋮x2n−11x31x32⋮x3n−1………⋱…1xn1xn2⋮xnn−1∣∣∣∣∣∣∣∣∣∣∣ 从第nnn行开始自下而上依次的由下一行减去它上一行的x1x_1x1倍 有 Dn∣111…10x2−x1x3−x1…xn−x10x22−x2x1x32−x3x1…xn2−xnx1⋮⋮⋮⋱⋮0x2n−1−x2n−2x1x3n−1−x3n−2x1…xnn−1−xnn−2x1∣∣111…10x2−x1x3−x1…xn−x10x2(x2−x1)x3(x3−x1)…xn(xn−x1)⋮⋮⋮⋱⋮0x2n−2(x2−x1)x3n−2(x3−x1)…xnn−2(xn−x1)∣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∣∣∣∣∣∣∣∣∣∣∣100⋮01x2−x1x22−x2x1⋮x2n−1−x2n−2x11x3−x1x32−x3x1⋮x3n−1−x3n−2x1………⋱…1xn−x1xn2−xnx1⋮xnn−1−xnn−2x1∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣100⋮01x2−x1x2(x2−x1)⋮x2n−2(x2−x1)1x3−x1x3(x3−x1)⋮x3n−2(x3−x1)………⋱…1xn−x1xn(xn−x1)⋮xnn−2(xn−x1)∣∣∣∣∣∣∣∣∣∣∣ 按第一列展开后提取公因式得 Dn(x2−x1)(x3−x1)…(xn−x1)∣11…1x2x3…xn⋮⋮⋱⋮x2n−2x3n−2…xnn−2∣(x2−x1)(x3−x1)…(xn−x1)∏2≤i≤j≤n(xj−xi)∏1≤i≤j≤n(xj−xi)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(x2−x1)(x3−x1)…(xn−x1)∣∣∣∣∣∣∣∣∣1x2⋮x2n−21x3⋮x3n−2……⋱…1xn⋮xnn−2∣∣∣∣∣∣∣∣∣(x2−x1)(x3−x1)…(xn−x1)2≤i≤j≤n∏(xj−xi)1≤i≤j≤n∏(xj−xi) 得证。
1.2 Vandermonde矩阵的理解
在差值(interpolation)问题中, 假设在二维空间有 nnn 个点 (x1,y1),(x2,y2),…,(xn,yn)(x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)(x1,y1),(x2,y2),…,(xn,yn), 希望得到一个多项式解: p(x)dnxn−1dn−1xn−2⋯d2xd1(3)p(x) d_{n}x^{n-1} d_{n-1}x^{n-2} \dots d_2x d_1 \tag3p(x)dnxn−1dn−1xn−2⋯d2xd1(3) 这个多项式可以满足我们的当前条件 p(x1)y1dnx1n−1dn−1x1n−2⋯d2x1d1p(x2)y2dnx2n−1dn−1x2n−2⋯d2x2d1…p(xn)yndnxnn−1dn−1xnn−2⋯d2xnd1p(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)y1dnx1n−1dn−1x1n−2⋯d2x1d1p(x2)y2dnx2n−1dn−1x2n−2⋯d2x2d1…p(xn)yndnxnn−1dn−1xnn−2⋯d2xnd1 实际上, 可以推演如下: y[y1y2⋮yn][d1d2x1d3x12⋯dnx1n−1d1d2x2d3x22⋯dnx2n−1⋮d1d2xnd3xn2⋯dnxnn−1][111…1x11x21x21…xn1x12x22x22…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x2n−1…xnn−1]T∗[1d2⋮dn]AT∗[y1y2⋮yn](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⎣⎢⎢⎢⎡y1y2⋮yn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎡d1d2x1d3x12⋯dnx1n−1d1d2x2d3x22⋯dnx2n−1⋮d1d2xnd3xn2⋯dnxnn−1⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x21x22⋮x2n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤T∗⎣⎢⎢⎢⎡1d2⋮dn⎦⎥⎥⎥⎤AT∗⎣⎢⎢⎢⎡y1y2⋮yn⎦⎥⎥⎥⎤(4) 还可以表示如下 [d1d2⋮dn](AT)−1y(5)\left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] (\mathrm{A^T})^{-1} y \tag5 ⎣⎢⎢⎢⎡d1d2⋮dn⎦⎥⎥⎥⎤(AT)−1y(5) 令x11,x22,x33,…,xnnx_1 1, x_2 2, x_3 3, \dots, x_n nx11,x22,x33,…,xnn 则有 A[111…1123…n122232…n2⋮⋮⋮⋱⋮1n−12n−13n−1…nn−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⎣⎢⎢⎢⎢⎢⎡1112⋮1n−11222⋮2n−11332⋮3n−1………⋱…1nn2⋮nn−1⎦⎥⎥⎥⎥⎥⎤(6)
1.3 Vandermonde矩阵在最小二乘拟合中的应用
假设对nnn个采样点进行拟合那么方差可以表示为
R2∑i1n[yi−(d1d2xid3xi2⋯dnxin−1)]2R^2 \sum_{i1}^{n}[y_i - (d_1 d_2x_i d_3x_i^2 \dots d_nx_i^{n - 1})]^2R2i1∑n[yi−(d1d2xid3xi2⋯dnxin−1)]2
为求得方差的最小值对d1,…,dnd_1, \dots, d_nd1,…,dn求偏导 ∂(R2)∂(d1)−2∑i1n[y−(d1d2xd3x2⋯dnxn−1)]0∂(R2)∂(d2)−2∑i1n[y−(d1d2xd3x2⋯dnxn−1)]x0…∂(R2)∂(dn)−2∑i1n[y−(d1d2xd3x2⋯dnxn−1)]xn−10\frac{\partial(R^2)}{\partial(d_1)} -2\sum_{i1}^{n}[y - (d_1 d_2x d_3x^2 \dots d_nx^{n - 1})] 0\\ \frac{\partial(R^2)}{\partial(d_2)} -2\sum_{i1}^{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_{i1}^{n}[y - (d_1 d_2x d_3x^2 \dots d_nx^{n - 1})]x^{n-1} 0 \\ ∂(d1)∂(R2)−2i1∑n[y−(d1d2xd3x2⋯dnxn−1)]0∂(d2)∂(R2)−2i1∑n[y−(d1d2xd3x2⋯dnxn−1)]x0…∂(dn)∂(R2)−2i1∑n[y−(d1d2xd3x2⋯dnxn−1)]xn−10 移项 d1nd2∑i1nxid3∑i1nxi2⋯dn∑i1nxin−1)]∑i1nyid1∑i1nxid2∑i1nxi2d3∑i1nxi3⋯dn∑i1nxin)]∑i1nxiyi…d1∑i1nxin−1d2∑i1nxind3∑i1nxin1⋯dn∑i1nxi2n−2∑i1nxin−1yid_1n d_2\sum_{i1}^{n}x_i d_3\sum_{i1}^{n}x_i^2 \dots d_n\sum_{i1}^{n}x_i^{n - 1})] \sum_{i1}^{n}y_i \\ d_1\sum_{i1}^{n}x_i d_2\sum_{i1}^{n}x_i^2 d_3\sum_{i1}^{n}x_i^3 \dots d_n\sum_{i1}^{n}x_i^{n})] \sum_{i1}^{n}x_iy_i \\ \dots \\ d_1\sum_{i1}^{n}x_i^{n-1} d_2\sum_{i1}^{n}x_i^{n} d_3\sum_{i1}^{n}x_i^{n1} \dots d_n\sum_{i1}^{n}x_i^{2n-2} \sum_{i1}^{n}x_i^{n-1}y_i \\ d1nd2i1∑nxid3i1∑nxi2⋯dni1∑nxin−1)]i1∑nyid1i1∑nxid2i1∑nxi2d3i1∑nxi3⋯dni1∑nxin)]i1∑nxiyi…d1i1∑nxin−1d2i1∑nxind3i1∑nxin1⋯dni1∑nxi2n−2i1∑nxin−1yi 用矩阵表示如下 [n∑i1nxi∑i1nxi2…∑i1nxin−1∑i1nxi∑i1nxi2∑i1nxi3…∑i1nxin⋮⋮⋮⋱⋮∑i1nxin−1∑i1nxin∑i1nxin1…∑i1nxi2n−2]∗[d1d2⋮dn][111…1x11x21x21…xn1x12x22x22…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x2n−1…xnn−1]∗[y1y2⋮yn]\left[ \begin{matrix} n \sum_{i1}^{n}x_i \sum_{i1}^{n}x_i^2 \dots \sum_{i1}^{n}x_i^{n-1} \\ \sum_{i1}^{n}x_i \sum_{i1}^{n}x_i^2 \sum_{i1}^{n}x_i^3 \dots \sum_{i1}^{n}x_i^{n} \\ \vdots \vdots \vdots \ddots \vdots \\ \sum_{i1}^{n}x_i^{n-1} \sum_{i1}^{n}x_i^n \sum_{i1}^{n}x_i^{n1} \dots \sum_{i1}^{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] ⎣⎢⎢⎢⎡n∑i1nxi⋮∑i1nxin−1∑i1nxi∑i1nxi2⋮∑i1nxin∑i1nxi2∑i1nxi3⋮∑i1nxin1……⋱…∑i1nxin−1∑i1nxin⋮∑i1nxi2n−2⎦⎥⎥⎥⎤∗⎣⎢⎢⎢⎡d1d2⋮dn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x21x22⋮x2n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤∗⎣⎢⎢⎢⎡y1y2⋮yn⎦⎥⎥⎥⎤ 对其进行变形得到 [111…1x11x21x21…xn1x12x22x22…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x2n−1…xnn−1][111…1x11x21x21…xn1x12x22x22…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x2n−1…xnn−1]T[d1d2⋮dn][111…1x11x21x21…xn1x12x22x22…xn2⋮⋮⋮⋱⋮x1n−1x2n−1x2n−1…xnn−1][y1y2⋮yn]\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] ⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x21x22⋮x2n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x21x22⋮x2n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤T⎣⎢⎢⎢⎡d1d2⋮dn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡1x11x12⋮x1n−11x21x22⋮x2n−11x21x22⋮x2n−1………⋱…1xn1xn2⋮xnn−1⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎡y1y2⋮yn⎦⎥⎥⎥⎤ 上面的公式可以简写为 AATdAy\mathrm{A}\mathrm{A}^\mathrm{T}d \mathrm{A}yAATdAy A\mathrm{A}A为竖着的范德蒙矩阵。此处向量ddd等于 d(AAT)−1Ayd (\mathrm{A}\mathrm{A}^\mathrm{T})^{-1} \mathrm{A}yd(AAT)−1Ay
1.4 基于Vandermonde的编码
编码矩阵就是单位矩阵和范德蒙德矩阵的组合。输入数据D和编码矩阵的乘积就是编码后的数据。 [100…0010…0⋮⋮⋮⋱⋮000…1111…1123…n122232…n2⋮⋮⋮⋱⋮1n−12n−13n−1…nn−1][d1d2⋮dn][d1d2⋮dnc1c2⋮cm](7)\left[ \begin{matrix} 1 0 0 \dots 0 \\ 0 1 0 \dots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ 0 0 0 \dots 1 \\ 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] \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \\ c_1 \\ c_2 \\ \vdots \\ c_m \\ \end{matrix} \right] \tag7 ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡10⋮01112⋮1n−101⋮01222⋮2n−100⋮01332⋮3n−1……⋱…………⋱…00⋮11nn2⋮nn−1⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎡d1d2⋮dn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡d1d2⋮dnc1c2⋮cm⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤(7) 算法复杂度 采用这种方法的算法复杂度还是比较高的编码复杂度为O(mn)O(mn)O(mn)其中mmm为校验数据个数nnn为输入数据个数。解码复杂度为O(n3)O(n^3)O(n3)。
2 柯西 Cauchy矩阵
柯西矩阵的任意一个子方阵都是奇异矩阵存在逆矩阵。而且柯西矩阵在迦罗华域上的求逆运算可以在O(n2)O(n^2)O(n2)的运算复杂度内完成。 使用柯西矩阵比范德蒙德矩阵的优化主要有两点
降低了矩阵求逆的运算复杂度。范德蒙矩阵求逆运算的复杂度为O(n3)O(n^3)O(n3)而柯西矩阵求逆运算的复杂度仅为O(n2)O(n^2)O(n2)。通过有限域转换将GF(2w2^w2w)域中的元素转换成二进制矩阵将乘法转换为逻辑与降低了乘法运算复杂度。二进制的加法即XOR乘法即AND
2.1 柯西 Cauchy矩阵介绍
柯西矩阵的描述如下 [1x0y01x0y11x0y2…1x0yn1x1y01x1y11x1y2…1x1yn1x2y01x2y11x2y2…1x2yn⋮⋮⋮⋱⋮1xmy01xmy11xmy2…1xmyn](8)\left[ \begin{matrix} \frac{1}{x_0 y_0} \frac{1}{x_0 y_1} \frac{1}{x_0 y_2} \dots \frac{1}{x_0 y_n} \\ \frac{1}{x_1 y_0} \frac{1}{x_1 y_1} \frac{1}{x_1 y_2} \dots \frac{1}{x_1 y_n} \\ \frac{1}{x_2 y_0} \frac{1}{x_2 y_1} \frac{1}{x_2 y_2} \dots \frac{1}{x_2 y_n} \\ \vdots \vdots \vdots \ddots \vdots \\ \frac{1}{x_m y_0} \frac{1}{x_m y_1} \frac{1}{x_m y_2} \dots \frac{1}{x_m y_n} \\ \end{matrix} \right] \tag8 ⎣⎢⎢⎢⎢⎢⎢⎡x0y01x1y01x2y01⋮xmy01x0y11x1y11x2y11⋮xmy11x0y21x1y21x2y21⋮xmy21………⋱…x0yn1x1yn1x2yn1⋮xmyn1⎦⎥⎥⎥⎥⎥⎥⎤(8) xix_ixi 和yiy_iyi 都是迦罗华域GF(2w2^w2w中的元素。 基于柯西矩阵的编码矩阵为 [100…0010…0⋮⋮⋮⋱⋮000…11x0y01x0y11x0y2…1x0yn1x1y01x1y11x1y2…1x1yn1x2y01x2y11x2y2…1x2yn⋮⋮⋮⋱⋮1xmy01xmy11xmy2…1xmyn][d1d2⋮dn][d1d2⋮dnc1c2⋮cm](9)\left[ \begin{matrix} 1 0 0 \dots 0 \\ 0 1 0 \dots 0 \\ \vdots \vdots \vdots \ddots \vdots \\ 0 0 0 \dots 1 \\ \frac{1}{x_0 y_0} \frac{1}{x_0 y_1} \frac{1}{x_0 y_2} \dots \frac{1}{x_0 y_n} \\ \frac{1}{x_1 y_0} \frac{1}{x_1 y_1} \frac{1}{x_1 y_2} \dots \frac{1}{x_1 y_n} \\ \frac{1}{x_2 y_0} \frac{1}{x_2 y_1} \frac{1}{x_2 y_2} \dots \frac{1}{x_2 y_n} \\ \vdots \vdots \vdots \ddots \vdots \\ \frac{1}{x_m y_0} \frac{1}{x_m y_1} \frac{1}{x_m y_2} \dots \frac{1}{x_m y_n} \\ \end{matrix} \right] \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{matrix} \right] \left[ \begin{matrix} d_1 \\ d_2 \\ \vdots \\ d_n \\ c_1 \\ c_2 \\ \vdots \\ c_m \\ \end{matrix} \right] \tag9 ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡10⋮0x0y01x1y01x2y01⋮xmy0101⋮0x0y11x1y11x2y11⋮xmy1100⋮0x0y21x1y21x2y21⋮xmy21……⋱…………⋱…00⋮1x0yn1x1yn1x2yn1⋮xmyn1⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎡d1d2⋮dn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡d1d2⋮dnc1c2⋮cm⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤(9)
2.2 柯西编解码过程优化
在范德蒙编码的时候我们可以采用对数/反对数表的方法将乘法运算转换成了加法运算并且在迦罗华域中加法运算转换成了XOR运算。 柯西编解码为了降低乘法复杂度采用了有限域上的元素都可以使用二进制矩阵表示的原理将乘法运算转换成了迦罗华域“AND运算”和“XOR逻辑运算”提高了编解码效率。 从数学的角度来看在迦罗华有限域中任何一个GF(2w2^w2w)域上的元素都可以映射到GF(2)二进制域并且采用一个二进制矩阵的方式表示GF(2w2^w2w)中的元素。 例如GF(232^323)域中的元素可以表示成GF(2)域中的二进制矩阵 上图中黑色方块表示逻辑1白色方块表示逻辑0。通过这种转换GF(2w2^w2w)域中的阵列就可以转换成GF(2)域中的二进制阵列。生成矩阵的阵列转换表示如下 在GF(2w2^w2w)域中的编码矩阵为k∗(km)k *(km)k∗(km)转换到GF(2)域中使用二进制矩阵表示编码矩阵变成了(w∗k)∗(w∗(km))(w*k)* (w*(km))(w∗k)∗(w∗(km))二进制矩阵。
采用域转换的目的是简化GF(2w2^w2w)域中的乘法运算。在GF(2)域中乘法运算变成了逻辑与运算加法运算变成了XOR运算可以大大降低运算复杂度。 和范德蒙编解码中提到的对数/反对数方法相比这种方法不需要构建对数/反对数表可以支持www为很大的GF域空间。采用这种有限域转换的方法之后柯西编码运算可以表示如下 算法复杂度使用柯西矩阵要优于范德蒙德矩阵的方法柯西矩阵的运算复杂度为O(n∗(n−m))O(n *(n - m))O(n∗(n−m))解码复杂度为O(n2)O(n^2)O(n2)。
2.3 参数www影响
选择GF(2w2^w2w)中的www参数需要满足kn≤2wkn \leq 2^wkn≤2w。 对于柯西矩阵的RS编码还需要满足coding Block size % (www * packet) 0。具体参数设置和意义见 Jerasure实现jerasure开源实现。 关于Erasure Code有一个开源的实现Jerasure是由James S. Plank教授开发。还有一个开源项目FECpp也是关于EC code的。地址为FECpp 开源实现。
3 RS编码升级
RS编码后的数据如果丢失了一块恢复丢失的数据需要最少读取n块数据。在生产环境中硬盘故障经常发生恢复数据对网络IO和CPU都会有较大的消耗。 因此有些公司在EC编码的基础上做了一些改进使用LRC或SEC替换RS编码。
3.1 LRC - Locally Repairable Code 本地副本存储
LRC编码与RS编码方式基本相同同时增加了额外的数据块副本。 LRC编码本质上是RS编码2副本备份。 LRC编码步骤如下
对原始数据使用RS编码例如编码为42编码结果为4个数据块D1、D2、D3、D42个编码块C1、C2原始数据做2副本将4个数据块的前2个数据块和后2个数据块分别生成2个编码块即R1D1D2R2D3D4如果某一个数据块丢失例如D2丢失则只需要R1和D1即可恢复D2
LRC的编码矩阵中增加了步骤2的2副本编码样子如下 LRC增加了副本数量使用了更多的存储空间来减少恢复数据块时读取块的数量节省恢复数据使用的网络IO和CPU。
3.2 SEC - Sparse Erasure Code 稀疏纠删码
LRC编码中只对数据块做了2副本当编码块丢失时仍然需要读取n块数据来重新计算编码块。 SEC编码中对数据块和编码块都做增加了校验块。 SEC编码本质上是RS编码奇偶校验块。 SEC编码步骤如下
对原始数据使用RS编码例如编码为42编码结果为4个数据块D1、D2、D3、D42个编码块C1、C2生成D1D2的校验块X1D3D4的校验块X2C1C2的校验块X3当数据块或编码块中的某一个丢失时例如C2丢失通过C1和校验块X3即可恢复C2
SEC同样通过增加存储块减少了恢复数据是的网络和CPU开销。
4 FEC 介绍
在信息中按照某种规则加上一定的冗余位构成一个码字称为差错控制编码过程。 在接收端接收到码字或从存储设备中读取码字后查看信息位和冗余位并检查他们之间的关系是否正确以确定是否有差错发生称为校验。 Forward Error CorrectionFEC- 前向纠错编码技术通过在传输码列中加入冗余纠错码在一定条件下通过解码可以自动纠正传输误码。这种编码的译码设备较复杂。
除FEC之外还有两种差错控制编码Automatic repeat requestARQ检错重发或自动请求重传Hybrid Error CorrectionHEC混合纠错。
检错重发由发送端送出能够发现错误的码接收端如果发现错误通过反向信道把这一判决结果反馈给发送端。然后发送端把接收端认为错误的信息再次重发。其特点是需要反馈信道译码设备简单。
混合纠错是 ARQ和 FEC方式的混合。发送端同时送出具有检错和纠错能力的码如果接收端收到信码在纠错能力以内则自动进行纠正。如果超出纠错能力则经过反馈信道请求发送端重发。
参考
A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like SystemsOptimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Storage ApplicationsTutorial: Erasure Coding for Storage Applicationshttp://jerasure.org/jerasure/jerasurehttp://jerasure.org/jerasure/gf-completehttp://alanwu.blog.51cto.com/3652632/1406312http://alanwu.blog.51cto.com/3652632/1410132http://blog.163.com/yandong_8212/blog/static/13215391420143281143547/
