來(lái)源

2.2 有限域(Finite Field, 簡(jiǎn)稱(chēng)GF)

一個(gè)有限域包含了一組預(yù)定于的元素. 有限域具有的多維和數(shù)學(xué)的性質(zhì)使它成為編碼和碼位錯(cuò)誤檢測(cè)理想的工具. 域越大, 生成的RS(里所,里德-所羅門(mén))碼字越長(zhǎng), 則信息的傳輸率就越高.

一個(gè)有限域是用質(zhì)數(shù)為基數(shù)(十進(jìn)制的基數(shù)是十,二進(jìn)制的基數(shù)是二...)建立的. 用質(zhì)數(shù)是非常必要的,確保了域里任何一個(gè)元素和域里其他元素相加, 相乘時(shí)都產(chǎn)生一個(gè)唯一的值. 如果用非質(zhì)數(shù)就沒(méi)有這種效果.

GF(2), GF(3), GF(5), GF(7) 等, 都是有效的質(zhì)數(shù)域. 但是, 2ⁿ也是可以做進(jìn)制的基數(shù), 因?yàn)?是一個(gè)素?cái)?shù)的基數(shù),n次方域示了這個(gè)域里元素的數(shù)量.

例如, GF(2³) = GF(8)就是一個(gè)2進(jìn)制域,含8個(gè)元素{0,1,2,3,4,5,6,7}.
GF(2⁸) = GF(256)就是一個(gè)2進(jìn)制域,含256個(gè)元素{0,1,2,3,....256}.

2.2.1 有限域例子

本節(jié)通過(guò)展示一個(gè)GF(7)整數(shù)域的建立和性質(zhì)來(lái)說(shuō)明有限域的概念. GF(7)有限域包含了7個(gè)元素{0,1,2,3,4,5,6}. 因?yàn)檫@是一個(gè)模7的域, 那么6就是最大的元素. 這個(gè)域的原根是3(一個(gè)大坑,沒(méi)法詳 (╯‵□′)╯︵┻━┻), 這個(gè)域里所有值都是從3的冪得到,如下:

3⁰ = 1 且等于3⁶ 模7余1
3¹ = 3 且等于3⁷ 模7余3
3² = 2 且等于3 × 3 = 9 ÷ 7 = 1 余 2
3³ = 2 且等于3 × 3 × 3 = 27 ÷ 7 = 3 余 6
3⁴ = 2 且等于3 × 3 × 3 × 3 = 81 ÷ 7 = 11 余 4
3⁵ = 2 且等于3 × 3 × 3 × 3 × 3 = 243 ÷ 7 = 34 余 5
3⁶ = 2 且等于3 × 3 × 3 × 3 × 3 × 3 = 729 ÷ 7 = 104 余 1 ( ∑(っ °Д °;)っ, 和 3⁰ 一樣?)
3⁷ = 2 且等于3 × 3 × 3 × 3 × 3 × 3 × 3 = 2187 ÷ 7 = 312 余 3 ( ∑(っ°Д °;)っ, 和 3¹ 一樣?)

請(qǐng)注意到,3⁶ = 3⁰ = 1且3⁷ = 3¹ = 3 和3⁸ = 3² = 2 等等. 域的值根據(jù)3的n次冪無(wú)限循環(huán). 任何加減乘除的結(jié)果值都等于3⁰到3⁵之間的值, 無(wú)論計(jì)算的結(jié)果是什么. 這種周期性對(duì)于微處理器用寄存器來(lái)執(zhí)行移位的計(jì)算非常合適.

有限域GF(7)加法表如下,包含了有限域中元素所有相加,相減所產(chǎn)生的可能的結(jié)果. 請(qǐng)注意表的對(duì)稱(chēng)性. 在任何一行或者列中,都沒(méi)有負(fù)數(shù)或者重復(fù)的數(shù)(就某一行或列而言).

GF(7) - {0,1,2,3,4,5,6}
GF(7) - 加法表

如果兩個(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,并沒(méi)有-b,這里的-b是某個(gè)數(shù),它加上b的結(jié)果為0, 這個(gè)數(shù)到底在哪里?

(╯‵□′)╯︵┻━┻ 什么鬼?

注: 好像是廢話, 5 - 2 就是 5 + (-2)
但是在有限域GF(7)中,有2,并沒(méi)有-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
(/= _ =)/~┴┴