2.2 有限域(Finite Field, 簡(jiǎn)稱GF)
一個(gè)有限域包含了一組預(yù)定于的元素. 有限域具有的多維和數(shù)學(xué)的性質(zhì)使它成為編碼和碼位錯(cuò)誤檢測(cè)理想的工具. 域越大, 生成的RS(里所,里德-所羅門)碼字越長, 則信息的傳輸率就越高.
一個(gè)有限域是用質(zhì)數(shù)為基數(shù)(十進(jìn)制的基數(shù)是十,二進(jìn)制的基數(shù)是二...)建立的. 用質(zhì)數(shù)是非常必要的,確保了域里任何一個(gè)元素和域里其他元素相加, 相乘時(shí)都產(chǎn)生一個(gè)唯一的值. 如果用非質(zhì)數(shù)就沒有這種效果.
GF(2), GF(3), GF(5), GF(7) 等, 都是有效的質(zhì)數(shù)域. 但是, 2n也是可以做進(jìn)制的基數(shù), 因?yàn)?是一個(gè)素?cái)?shù)的基數(shù),n次方域示了這個(gè)域里元素的數(shù)量.
例如, GF(23) = GF(8)就是一個(gè)2進(jìn)制域,含8個(gè)元素{0,1,2,3,4,5,6,7}.
GF(28) = GF(256)就是一個(gè)2進(jìn)制域,含256個(gè)元素{0,1,2,3,....256}.
2.2.1 有限域例子
本節(jié)通過展示一個(gè)GF(7)整數(shù)域的建立和性質(zhì)來說明有限域的概念. GF(7)有限域包含了7個(gè)元素{0,1,2,3,4,5,6}. 因?yàn)檫@是一個(gè)模7的域, 那么6就是最大的元素. 這個(gè)域的原根是3(一個(gè)大坑,沒法詳 (╯‵□′)╯︵┻━┻), 這個(gè)域里所有值都是從3的冪得到,如下:
30 = 1 且等于36 模7余1
31 = 3 且等于37 模7余3
32 = 2 且等于3 × 3 = 9 ÷ 7 = 1 余 2
33 = 2 且等于3 × 3 × 3 = 27 ÷ 7 = 3 余 6
34 = 2 且等于3 × 3 × 3 × 3 = 81 ÷ 7 = 11 余 4
35 = 2 且等于3 × 3 × 3 × 3 × 3 = 243 ÷ 7 = 34 余 5
36 = 2 且等于3 × 3 × 3 × 3 × 3 × 3 = 729 ÷ 7 = 104 余 1 ( ∑(っ °Д °;)っ, 和 30 一樣?)
37 = 2 且等于3 × 3 × 3 × 3 × 3 × 3 × 3 = 2187 ÷ 7 = 312 余 3 ( ∑(っ°Д °;)っ, 和 31 一樣?)
請(qǐng)注意到,36 = 30 = 1且37 = 31 = 3 和38 = 32 = 2 等等. 域的值根據(jù)3的n次冪無限循環(huán). 任何加減乘除的結(jié)果值都等于30到35之間的值, 無論計(jì)算的結(jié)果是什么. 這種周期性對(duì)于微處理器用寄存器來執(zhí)行移位的計(jì)算非常合適.
有限域GF(7)加法表如下,包含了有限域中元素所有相加,相減所產(chǎn)生的可能的結(jié)果. 請(qǐng)注意表的對(duì)稱性. 在任何一行或者列中,都沒有負(fù)數(shù)或者重復(fù)的數(shù)(就某一行或列而言).
GF(7) - {0,1,2,3,4,5,6}
GF(7) - 加法表
| + | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 0 | 1 | 2 | 3 | 4 | 5 |
如果兩個(gè)元素的和小于7,那按正常方式相加,例如:
1 + 5 = 6
2 + 4 = 6
3 + 3 = 6
4 + 2 = 6
5 + 1 = 6
加法服從交換(commutative)律, 例如
1 + 5 = 5 +１
2 + 4 = 4 + 2
3 + 3 = 3 + 3
對(duì)于和大于7的兩個(gè)元素相加, 忽略整數(shù)結(jié)果只取模7的余數(shù),例如
1 + 6 = 7 % 7 = 0
2 + 6 = 8 % 7 = 1
3 + 6 = 9 % 7 = 2
5 + 3 = 8 % 7 = 1
減法等于加上這個(gè)元素的加法逆元, 一個(gè)元素的加法逆元就是當(dāng)逆元和該元素相加時(shí),得到的和為0. [a + (-a) = 0]
注: 好像是廢話, a - b 就是 a + (-b)
但是在有限域中,有b,并沒有-b,這里的-b是某個(gè)數(shù),它加上b的結(jié)果為0, 這個(gè)數(shù)到底在哪里?
(╯‵□′)╯︵┻━┻ 什么鬼?
注: 好像是廢話, 5 - 2 就是 5 + (-2)
但是在有限域GF(7)中,有2,并沒有-2,這里的-2是某個(gè)數(shù),它加上2的結(jié)果為0, 這個(gè)數(shù)到底在哪里?
答: 因?yàn)檫@個(gè)有限域中加法的特殊性質(zhì), 和為7的時(shí)候,取模7,余數(shù)為0. 因?yàn)? + 2 = 7, 模7余0, 那么5就是2的加法逆元
5 - 2 = 5 + 5 = 10 % 7 = 3
5 - 2 = 3
(/= _ =)/~┴┴
