Galois Field


Galois Filed (dibaca Medan Galoa) direpresentasikan oleh GF(q). dimana q adalah prime p maupun pangkat dari p. Untuk biner maka p adalah 2.

Misalkan a adalah elemen nonzero pada GF(q), maka akan ada bilangan bulat yang terkecil n sehingga a^n=1. Bilangan bulat n ini disebut orde dari elemen medan a. Di dalam medan terbatas GF(q), elemen nonzero a disebut primitif jika order a adalah q-1. Sehingga, pangkat dari elemen primitif membangkitkan seluruh elemen nonzero GF(q). Setiap medan terbatas memiliki elemen primitif.

Sebagai contoh kita ambil bilangan bulat 3 di dalam GF(7), maka kita dapatkan:

3^1 = 3
3^2 = 9 => 9 - 7 = 2
3^3 = 3\cdot3^2 = 3\cdot2 = 6
3^4 = 3.3^3 = 3.6 = 18 => 18 - 7.2 = 18 -14 = 4
3^5 = 3.3^4 = 3.4 = 12 => 12 - 7 = 5
3^6 = 3.3^5 =3.5 = 15 => 15 - 7.2 = 15 - 14 = 1

Maka bisa kita lihat diatas bahwa n=6=7-1, oleh karena itu orde bilangan bulat 3 adalah 6 yang merupakan q-1 yaitu 7-1=6, sehingga bilang bulat 3 adalah elemen primitif dari GF(7)

Contoh lain kita ambil bilangan bulat 4 di dalam GF(7). Maka bisa kita lihat pangkat 4 di bawah ini:

4^1=4
4^2=16-14=2
4^3=4.4^2=8-7=1

Bisa kita lihat bahwa order dari bilangan bulat 4 adalah 3. Maka 4 bukanlah elemen primitif dari GF(7).

Contoh lain adalah elemen primitif \alpha untuk suatu GF(q) dengan hasil sebagai berikut:

\alpha^0=1
\alpha^1=5
\alpha^2=4=25-21
\alpha^3=6=20-14
\alpha^4=2=30-28
\alpha^5=3=10-7
\alpha^6=15-14=1

maka bisa kita dapatkan bahwa elemen primitif tersebut adalah \alpha adalah 5, q adalah 7. Jadi bilangan bulat 5 adalah elemen primitif dari GF(7).

Satu medan Galois memiliki sekurang-kurangnya satu buah elemen primitif. Setiap elemen nonzero lainnya dapat dituliskan sebagai pangkat dari lemen primitif tersebut.

Kode dari medan biner GF(2) dan perluasannya GF(2^m) merupakan kode yang paling banyak digunakan secara luas di dalam transmisi data digital dan sistem storage dikarenakan informasi sistem ini dikodekan secara universal di dalam bentuk biner untuk alasan praktis.

irreducible polynomial p(X) dengan  derajat m disebut primitif jika n bernilai n=2^m-1 dan juga nilai n tersebut harus merupakan bilangan bulat positif yang terkecil untuk case p(X) membagi X^n+1

Sebagai contoh, p(X)=X^4+X+1 dapat membagi X^{15}+1 dan tidak bisa membagi X^n+1  untuk nilai 1\leq n<15.  Berarti X^4+X+1 merupakan polynomial primitif untuk derajat m bernilai 4.

Contoh lain adalah X^3+X+1 merupakan polynomial primitif untuk derajat m yang bernilai 3.

Sedangkan contoh yang bukan polynomial primitif adalah X^4+X^3+X^2+X+1 karena bisa membagi sampai n bernilai 5 yaitu X^5+1 sedangkan tidak berharga n=2^m-1.

Tidak mudah untuk mengenali primitif polynomial. Tapi sudah ada list yang menunjukkan primitif polynomial jumlah terkecil dengan derajat dari m di bawah ini. Untuk sebuah  m, maka ada kemungkinan lebih dari satu primitif dari derajat m.

Berikut list primitif polynomial

m=3 \longrightarrow 1+X+X^3
m=4 \longrightarrow 1+X+X^4
m=5 \longrightarrow 1+X^2+X^5
m=6 \longrightarrow 1+X+X^6
m=7 \longrightarrow 1+X^3+X^7
m=8 \longrightarrow 1+X^2+X^3+X^4+X^8
m=9 \longrightarrow 1+X^4+X^9
m=10 \longrightarrow 1+X^3+X^{10}
m=11 \longrightarrow 1+X^2+X^{11}
m=12 \longrightarrow 1+X+X^4+X^6+X^{12}
m=13 \longrightarrow 1+X+X^3+X^4+X^{13}
m=14 \longrightarrow 1+X+X^6+X^{10}+X^{14}
m=15 \longrightarrow 1+X+X^{15}
m=16 \longrightarrow 1+X^3+X^{12}+X^{16}
m=17 \longrightarrow 1+X^3X^{17}
m=18 \longrightarrow 1+X^7+X^{18}
m=19 \longrightarrow 1+X+X^2+X^5+X^{19}
m=20 \longrightarrow 1+X^3+X^{20}
m=21 \longrightarrow 1+X^2+X^{21}
m=22 \longrightarrow 1+X+X^{22}
m=23 \longrightarrow 1+X^5+X^{23}
m=24 \longrightarrow 1+X+X^2+X^7+X^{24}

\alpha merupakan elemen primitif dari GF(2^m). Untuk membangun GF(2^m) bisa kita lakukan sebagai contoh berikut

Untuk GF(2^3) dengan derajat m=3 yang mempunyai polynomial primitf yaiut 1+X+X^3, maka kita bisa membangun elemen  dengan cara p(\alpha)=1+\alpha+\alpha^3=0.  Sehingga kita dapatkan bahwa \alpha^3=1+\alpha.

Identitas \alpha^3=1+\alpha = \alpha+1 digunakan untuk membentuk representasi polynomial untuk elemen GF(2^3).

Contoh di bawah ini untuk membentuk dari representasi pangkat = representasi polynomial = representasi biner = representasi desimal.

0 = 0 = 000 = 0
\alpha^0 = 1 = 001 = 1
\alpha^1 = \alpha = 010 = 2
\alpha^2 = \alpha^2 = 100 = 4
\alpha^3=\alpha+1=011 = 3
\alpha^4=\alpha\cdot\alpha^3=\alpha(1+\alpha) =\alpha+\alpha^2 = 110 = 6
\alpha^5 = \alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3 =\alpha^2+1+\alpha=111=7
\alpha^6=\alpha\cdot\alpha^5=\alpha(\alpha^2+\alpha+1) =\alpha^3+\alpha^2+\alpha=1+\alpha+\alpha^2+\alpha
=\alpha^2+1=101=5

Berikut ini adalah konstruksi elemen untuk GF(2^4) dengan derajat m=4 dengan polynomial primitif adalah 1+X+X^4. Sehingga p(\alpha)=1+\alpha+\alpha^4=\alpha^4+\alpha=1=0. Kemudian kita dapatkan identitas \alpha^4=\alpha+1

0=0=0000=0
\alpha^0=1=0001=1
\alpha^1=\alpha^1=0010=2
\alpha^2=\alpha^2=0100=4
\alpha^3=\alpha^3=1000=8
\alpha^4=\alpha+1=0011=3
\alpha^5=\alpha\cdot\alpha^4=\alpha(\alpha+1)=\alpha^2+\alpha =0110=6
\alpha^6=\alpha\cdot\alpha^5=\alpha(\alpha^2+\alpha)=\alpha^3+ \alpha^2=1100=12
\alpha^7=\alpha\cdot\alpha^6=\alpha(\alpha^3+\alpha^2)=\alpha^4+ \alpha^3=\alpha+1+\alpha^3
=\alpha^3+\alpha+1=1011=11

\alpha^8=\alpha\cdot\alpha^7=\alpha(\alpha^3+\alpha+1) = \alpha^4+\alpha^2+\alpha
=\alpha+1+\alpha^2+\alpha=\alpha^2+1=0101=5

\alpha^9=\alpha\cdot\alpha^8=\alpha(\alpha^2+1)=\alpha^3+\alpha = 1010 = 10
\alpha^{10}=\alpha\cdot\alpha^9=\alpha(\alpha^3+\alpha) =\alpha^4+\alpha^2 = \alpha+1+\alpha^2
=\alpha^2+\alpha+1=0111=7

\alpha^{11}=\alpha\cdot\alpha^{10}=\alpha(\alpha^2+\alpha+1)= \alpha^3+\alpha^2+\alpha=1110=14

\alpha^{12}=\alpha\cdot\alpha^{11}=\alpha(\alpha^3+\alpha^2+\alpha) = \alpha^4+\alpha^3+\alpha^2
=\alpha+1+\alpha^3+\alpha^2= \alpha^3+\alpha^2+\alpha+1=1111=15

\alpha^{13}=\alpha\cdot\alpha^{12}=\alpha(\alpha^3+\alpha^2+\alpha+1 =\alpha^4+\alpha^3+\alpha^2+\alpha
=\alpha+1+\alpha^3+\alpha^2+ \alpha=\alpha^3+\alpha^2+1=1101=13

\alpha^{14}=\alpha\cdot\alpha^{13}=\alpha(\alpha^3+\alpha^2+1)= \alpha^4+\alpha^3+\alpha
=\alpha+1+\alpha^3+\alpha=\alpha^3+1= 1001=9

Contoh penjumlahan GF(2^3)

1+1=\alpha^0+\alpha^0=001+001=000=0
7+7=\alpha^5+\alpha^5=\alpha^2+\alpha+1+\alpha^2+\alpha+1
=111+111=000=0
3+6=\alpha^3+\alpha^4=\alpha+1+\alpha^2+\alpha
=011+110=101=5

Contoh perkalian GF(2^3)
3x3=\alpha^3\cdot\alpha^3=\alpha^3(\alpha+1)=\alpha^4+\alpha^3
= \alpha^2+\alpha+\alpha+1= 110+011=101=5

Bibliografi:
1. S. Lin, D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, Inc., Englewood Cliffs, New Jersey: 1983.
2. Sugihartono, Slide Kuliah Pengkodean Kanal, STEI ITB, 2011.

Tinggalkan komentar