CRS
[toc]
CRS
CRS 即 Cauchy Reed-Solomon coding，基于柯西矩阵的RS编码。
使用柯西矩阵代替范德蒙矩阵可以使求逆矩阵的时间复杂度降低为O(n^2)。并且它可以 采用有限域二进制矩阵的方式来提高运算效率，直接将普通运算转换成XOR逻辑运算，大大降低了运算复杂度。 实际在实现中，加减法都变成异或，乘除用查表（空间换时间）。
伽罗华域
伽罗华域，Galois Field，就是有限域。简单理解，域是一种定义了域中元素两种数学运算的代数系统，域由全体元素的加法集合以及非零元素的乘法集合构成。具有有限个元素的域，称为有限域。
注意到元素有限，所以一般认为域中的计算是带有取模性质的。例如有限域，在该域内的加法与乘法都是在模7的前提下进行的，这样可以发现在这个域里的运算依然满足封闭性以及加法乘法的交换律结合律。我们也称其为“模7加法”“模7乘法”。
注意到这样的域，p是质数，这种有限域在密码学、信息编码中都有很多应用。因为只有当p是质数时，才能保证域里每一个元素都有加法逆元和乘法逆元（除0外）。关于逆元，可简单理解成倒数。即在模运算的除法可转换成对应逆元的乘法（费马小定理），例如
GF(2^8)
GF(2^8) 是一个经常讨论的域。其一原因是在计算机里每个字节 Byte 就是由8位 bit （0或1）组成，对应的就是从0到255。但是对于 2^8 = 256 是不满足之前GF(p = prime)的要求的，因此要换个方法让其满足每个元素都有逆元。
多项式
我们规定如同 形式的式子为多项式，不过在这种讨论下，对多项式有下列要求:
- 多项式的系数只能是0或1。（这是由GF(2^8)中的2决定的）。
- 同类项的合并，系数用异或。（也因此加法减法是一样的）。
例如：
注意到多项式也是有乘除法的。乘法就是简单的多项式乘积并化开即可。除法也是类似，也有对应的商与余数的概念。因此引入素多项式概念，即该多项式无法划分成另两个多项式的乘积。
注意，这里我们可以将“多项式”构成一个域，这个域是对一个“素多项式”进行取模运算。这样这个域里的每个多项式也有对应的逆元，且也可以满足封闭性和各种运算定律。
例如：
其中是一个素多项式，上面的8个式子都有对应的加法乘法逆元（也是多项式且都在这8个多项式其中）。
注意到每个多项式的系数都由0、1构成，这样将系数串联可以变成一个三位的二进制数，恰好从000到111。每个多项式对应一个值（称为多项式值）。例如在 下，
的乘法逆元就是
，可以理解成在 GF(2^3) 下
的逆元是
同理扩展到 GF( 2 ^ 8 )。它的一个经典的素多项式就是，我们可以以此为据，加法减法用异或，乘除逆元用预处理查表即可。
柯西矩阵
柯西矩阵的构造如下：设 都是
中的元素，则柯西矩阵Cauchy Matrix 可表述为如下形式：
CRS 编码
生成矩阵的前k行（0 ~ k - 1行）是 k * k 的单位阵，第 k 到 第 n - 1 行是柯西矩阵。将其与加密块相乘，得到冗余数据。接收方只要接收到n个数据里的k个数据就可以复原全部的数据。具体细节见之前的FEC介绍。
注意到一点，我们对数据包进行操作时，处理单位并不是一个单独的bit，而是一个int（可能4位，可能8位等... 这里我们用8位）。我们记 w = 8 表示一个处理的基本单位。那么生成矩阵可以化成如下形式：
注意到更改后的bitmatrix大概率是一个稀疏矩阵，所以无需做矩阵乘法，转而记录对应信息位的计算式即可。将这个计算式列表称为 schedule. 一个Schedule 是一个五元组
其中，op代表操作码。0 - 复制，1 - 异或。 表示源设备编号和源二进制数位编号。同理
表示目标设备编号和目标二进制数位编号。
使用Schedule 的好处：各种编译码方式都可以统一转换成Schedule的计算方式，无需编写众多的编译码函数
// ./Jerasure/Examples/encoder.c
...
/* Create coding matrix or bitmatrix and schedule */
switch(tech) {
...
case Cauchy_Orig:
matrix = cauchy_original_coding_matrix(k, m, w);
bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
break;
...
}
...
// ./Jerasure/src/cauchy.c
...
int* cauchy_original_coding_matrix(int k, int m, int w)
{
...
int* matrix = talloc(int, k * m);
index = 0;
for (i = 0; i < m; i++) {
for (j = 0; j < k; j++) {
matrix[index] = galois_single_divide(1, (i ^ (m + j)), w);
index++;
}
}
return matrix;
}
...
// ./Jerasure/src/jerasure.c
...
int* jerasure_matrix_to_bitmatrix(int k, int m, int w, int* matrix)
{
int* bitmatrix = talloc(int, k * m * w * w);
rowelts = k * w;
rowindex = 0;
for (i = 0; i < m; i++) {
colindex = rowindex;
for (j = 0; j < k; j++) {
elt = matrix[i * k + j];
for (x = 0; x < w; x++) {
for (l = 0; l < w; l++) {
bitmatrix[colindex + x + l * rowelts] = ((elt & (1 << l)) ? 1 : 0);
}
elt = galois_single_multiply(elt, 2, w);
}
colindex += w;
}
rowindex += rowelts * w;
}
return bitmatrix;
}
...
jerasure_smart_bitmatrix_to_schedule 它写的又臭又长，后面还要再改一下。
注意到上方还没开始编码，是编码前的预处理工作（目标是按k,m,w处理出schedule)。这里我们默认w=8.
// ./Jerasure/Examples/encoder.c
/* Encode according to coding method */
switch(tech) {
...
case Cauchy_Orig:
jerasure_schedule_encode(k, m, w, schedule, data, coding, blocksize, packetsize);
break;
...
}
// ./Jerasure/src/jerasure.c
...
void jerasure_schedule_encode(int k, int m, int w, int** schedule,
char** data_ptrs, char** coding_ptrs, int size, int packetsize)
{
char** ptr_copy;
int i, tdone;
ptr_copy = talloc(char*, (k + m));
for (i = 0; i < k; i++) ptr_copy[i] = data_ptrs[i];
for (i = 0; i < m; i++) ptr_copy[i + k] = coding_ptrs[i];
for (tdone = 0; tdone < size; tdone += packetsize * w) {
// 根据 schedule 里规定的五元组，按操作进行编码
jerasure_do_scheduled_operations(ptr_copy, schedule, packetsize);
for (i = 0; i < k + m; i++) ptr_copy[i] += (packetsize * w);
}
free(ptr_copy);
}
...
处理完之后的data 和 coding 就分别对应编码后的 data块 （原始数据）和 coding块（冗余）。
CRS 译码
// ./Jerasure/Examples/decoder.c
...
int main(int argc, char **argv){
...
/* Choose proper decoding method */
...
if (tech == Cauchy_Orig ||...) {
i = jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, coding, blocksize, packetsize, 1); // line 324
}
...
}
// ./Jerasure/src/jerasure.c
...
int jerasure_schedule_decode_lazy(int k, int m, int w, int* bitmatrix, int* erasures, char** data_ptrs, char** coding_ptrs, int size, int packetsize, int smart)
{
int i, tdone;
char** ptrs;
int** schedule;
ptrs = set_up_ptrs_for_scheduled_decoding(k, m, erasures, data_ptrs, coding_ptrs);
if (ptrs == NULL) return -1;
schedule = jerasure_generate_decoding_schedule(k, m, w, bitmatrix, erasures, smart);
if (schedule == NULL) {
free(ptrs);
return -1;
}
for (tdone = 0; tdone < size; tdone += packetsize * w) {
jerasure_do_scheduled_operations(ptrs, schedule, packetsize);
for (i = 0; i < k + m; i++) ptrs[i] += (packetsize * w);
}
jerasure_free_schedule(schedule);
free(ptrs);
return 0;
}
