加载中…
个人资料
pooran
pooran
  • 博客等级:
  • 博客积分:0
  • 博客访问:22,935
  • 关注人气:5
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

DataMatrix编码2——伽罗华域运算

(2012-03-29 20:11:44)
标签:

杂谈

分类: DataMatrix
    伽罗华域即有限域,RS编码在此域中进行运算,故不得不对其有所了解。DataMatrix的数据码字、及纠正码字等均是属于GF(2^8)中的符号,其空间大小为256。有限域的一个特征是,其符号(元素)运算的结果,仍属于该域。除了0、1外,另外254个符号,均由本原多项式P(x)生成,DataMatrix规则中,P(x)=x^8+x^5+x^3+x^2+1,设α为P(x)的根,α^8+α^5+α^3+α^2+1=0,由于伽罗华域的加法为异或算法,故α^8=α^5+α^3+α^2+1。
    GF(2^8)符号的表示形式如下:

 

多项式

D7D6D5D4 D3D2D1D0

数值表示

0

0

0000 0000

0

α^0

α^0

0000 0001

1

α^1

α^1

0000 0010

2

α^2

α^2

0000 0100

4

α^3

α^3

0000 1000

8

α^4

α^4

0001 0000

16

α^5

α^5

0010 0000

32

α^6

α^6

0100 0000

64

α^7

α^7

1000 0000

128

α^8

α^5+α^3+α^2+1

0010 1101

45

α^9

α^6+α^4+α^3+α

0101 1010

90

α^10

α^7+α^5+α^4+α^2

1011 0100

180

α^11

α^6+α^2+1

0100 0101

69

α^12

α^7+α^3+α

1000 1010

138

α^13

α^5+α^4+α^3+1

0011 1001

57

α^14

α^6+α^5+α^4+α

0111 0010

114

…… ……

     计算机运算时,需要用相关算法将整个GF的所有符号的数值表示列表出来,结果如下:
alphaTo=
    1,   2,   4,   8,  16,  32,  64, 128,  45,  90, 180,  69, 138,  57, 114, 228,
     229, 231, 227, 235, 251, 219, 155,  27,  54, 108, 216, 157,  23,  46,  92, 184,
      93, 186,  89, 178,  73, 146,   9,  18,  36,  72, 144,  13,  26,  52, 104, 208,
     141,  55, 110, 220, 149,   7,  14,  28,  56, 112, 224, 237, 247, 195, 171, 123,
     246, 193, 175, 115, 230, 225, 239, 243, 203, 187,  91, 182,  65, 130,  41,  82,
     164, 101, 202, 185,  95, 190,  81, 162, 105, 210, 137,  63, 126, 252, 213, 135,
      35,  70, 140,  53, 106, 212, 133,  39,  78, 156,  21,  42,  84, 168, 125, 250,
     217, 159,  19,  38,  76, 152,  29,  58, 116, 232, 253, 215, 131,  43,  86, 172,
     117, 234, 249, 223, 147,  11,  22,  44,  88, 176,  77, 154,  25,  50, 100, 200,
     189,  87, 174, 113, 226, 233, 255, 211, 139,  59, 118, 236, 245, 199, 163, 107,
     214, 129,  47,  94, 188,  85, 170, 121, 242, 201, 191,  83, 166,  97, 194, 169,
     127, 254, 209, 143,  51, 102, 204, 181,  71, 142,  49,  98, 196, 165, 103, 206,
     177,  79, 158,  17,  34,  68, 136,  61, 122, 244, 197, 167,  99, 198, 161, 111,
     222, 145,  15,  30,  60, 120, 240, 205, 183,  67, 134,  33,  66, 132,  37,  74,
     148,   5,  10,  20,  40,  80, 160, 109, 218, 153,  31,  62, 124, 248, 221, 151,
       3,   6,  12,  24,  48,  96, 192, 173, 119, 238, 241, 207, 179,  75, 150,   0 }
同时,将各符号的指数也列表出来:
expOf=
   { 255,   0,   1, 240,   2, 225, 241,  53,   3,  38, 226, 133, 242,  43,  54, 210,
       4, 195,  39, 114, 227, 106, 134,  28, 243, 140,  44,  23,  55, 118, 211, 234,
       5, 219, 196,  96,  40, 222, 115, 103, 228,  78, 107, 125, 135,   8,  29, 162,
     244, 186, 141, 180,  45,  99,  24,  49,  56,  13, 119, 153, 212, 199, 235,  91,
       6,  76, 220, 217, 197,  11,  97, 184,  41,  36, 223, 253, 116, 138, 104, 193,
     229,  86,  79, 171, 108, 165, 126, 145, 136,  34,   9,  74,  30,  32, 163,  84,
     245, 173, 187, 204, 142,  81, 181, 190,  46,  88, 100, 159,  25, 231,  50, 207,
      57, 147,  14,  67, 120, 128, 154, 248, 213, 167, 200,  63, 236, 110,  92, 176,
       7, 161,  77, 124, 221, 102, 218,  95, 198,  90,  12, 152,  98,  48, 185, 179,
      42, 209,  37, 132, 224,  52, 254, 239, 117, 233, 139,  22, 105,  27, 194, 113,
     230, 206,  87, 158,  80, 189, 172, 203, 109, 175, 166,  62, 127, 247, 146,  66,
     137, 192,  35, 252,  10, 183,  75, 216,  31,  83,  33,  73, 164, 144,  85, 170,
     246,  65, 174,  61, 188, 202, 205, 157, 143, 169,  82,  72, 182, 215, 191, 251,
      47, 178,  89, 151, 101,  94, 160, 123,  26, 112, 232,  21,  51, 238, 208, 131,
      58,  69, 148,  18,  15,  16,  68,  17, 121, 149, 129,  19, 155,  59, 249,  70,
     214, 250, 168,  71, 201, 156,  64,  60, 237, 130, 111,  20,  93, 122, 177, 150 }
符号的运算:
a+b:=a^b,例如66+67=66^67=1
a*b:1、两指数相加,2、Mod(255),3、求新指数对应的符号,例如66*67,指数分别为expOf(66)=220、expOf(67)=217,新指数为182,对应符号alphaTo(182)=204,即66*67=204。

     GF(2^8)空间的生成算法如下:

int MM = 8;
int NN = 255;
int alphaToMM = 45;//α^8=α^5+α^3+α^2+1
int* alphaTo = new int[NN+1];
int* expOf = new int[NN+1];

alphaTo[MM] = alphaToMM;
expOf[alphaToMM] = MM;
alphaTo[NN] = 0;
expOf[0] = NN;

int i, shift;
shift = 1;
for(i=0; i<MM; i++){
    alphaTo[i] = shift;//2^i
    expOf[alphaTo[i]] = i;
    shift <<= 1;
}
shift = 128;
for(i=MM+1; i<NN; i++){
    if(alphaTo[i-1] >= shift){
        alphaTo[i] = alphaTo[MM] ^ ((alphaTo[i-1]^shift)<<1);//alphaTo[i-1]*alpha+alpha^8
    }else{
        alphaTo[i] = alphaTo[i-1]<<1;
    }
    expOf[alphaTo[i]] = i;
}


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有