BAB II KAJIAN TEORI A. Lapangan Berhingga Himpunan merupakan suatu kumpulan obyek-obyek yang didefinisikan dengan jelas pada suatu batasan-batasan tertentu. Contoh himpunan hewan berkaki empat H4 ={sapi, kambing, kuda, badak, harimau, unta}. Contoh lain himpunan bilangan prima kurang dari 12 yaitu A = {2,3,5,7,11}. Definisi 2.1 (Sukirman, 2010: 68). Himpunan tak kosong G yang memiliki operasi biner ⦁
disebut suatu grup
apabila memenuhi aksioma-aksioma berikut ini: i.
Operasi ⦁ pada G bersifat asosiatif berlaku ( ⦁ )⦁
⦁( ⦁ ).
ii. G memuat elemen identitas, yaitu . berlaku ⦁
⦁
.
iii. Setiap unsur G memiliki invers di dalam G juga. ⦁
sedemikian sehingga
⦁
. Maka
disebut invers dari . Suatu grup G dengan operasi biner ⦁ ditulis (G, ⦁). Jika (G, ⦁) suatu grup yang bersifat komutatif yaitu
berlaku
komutatif atau grup abelian. Apabila terdapat kompleks dari
⦁
⦁ maka (G, ⦁) disebut grup dan
(Sukirman, 2010:97). Misalkan terdapat (
, maka
) suatu grup dan
kompleks dari , dan apabila (
) suatu grup, maka dikatakan
dari . Operasi pada grup
harus sama (Sukirman, 2010:99).
dan
6
disebut
adalah subgrup
Definisi 2.2 (Sukirman, 2010:174). Diberikan
suatu subgrup dari grup
(diberi simbol
, sehingga
) jika dan hanya jika
disebut subgrup normal dari berlaku
.
Contoh 2.1. i.
(B,+) dengan B adalah himpunan bilangan bulat, merupakan suatu grup dengan elemen identitas 0 dan setiap elemen mempunyai invers terhadap penjumlahan.
ii.
Diberikan B9 = {0,1,2,3,4,5,6,7,8}, yaitu himpunan bilangan bulat tak negatif kurang dari 9. (B9,+), operasi + pada B9 bersifat asosiatif, memiliki elemen identitas 0 tetapi inversnya tidak termuat di B9 sehngga B9 tidak tertutup terhadap operasi +. Dengan demikian (B9,+) bukan merupakan grup. Sedangkan, (B9, ⦁) dengan B9 merupakan himpunan bilangan bulat tak negatif kurang dari 9 dan operasi ⦁ adalah operasi perkalian yang bersifat asosiatif tetapi hasil perkalian elemen-elemennya tidak termuat di B9 sehingga B9 tidak tertutup. Jadi, (B9, ⦁) juga bukan suatu grup.
Definisi 2.3 (Fraleigh, 1989: 167). Suatu ring (
⦁) adalah himpunan tak kosong R yang dilengkapi dengan dua
operasi biner yang ditunjukkan dengan tanda (
) untuk penjumlahan dan
( ⦁ ) untuk perkalian serta memenuhi aksioma-aksioma sebagai berikut: i.
(
ii. (
) merupakan grup komutatif atau grup abelian ⦁) memenuhi sifat asosiatif
iii. Memenuhi sifat distributif kiri dan distributif kanan, untuk setiap berlaku (
)
dan (
)
.
7
Suatu ring (
⦁) dikatakan ring komutatif apabila operasi perkalian ( ⦁ ) berlaku ⦁
pada R bersifat komutatif yaitu untuk setiap
⦁ .
Contoh 2.2. Perhatikan himpunan-himpunan berikut. B9 = {0,1,2,3,4,5,6,7,8}, yaitu himpunan bilangan bulat tak negatif kurang dari 9. = {[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]}, yaitu himpunan semua kelas bilangan bulat modulo 10. = {[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]}, yaitu himpunan semua kelas bilangan bulat modulo 11. Pada himpunan-himpunan tersebut didefinisikan operasi + dan ⦁ sehingga dapat dijelaskan sebagai berikut. i.
(
⦁) merupakan suatu ring karena himpunan
syarat aksioma suatu ring yaitu (
memenuhi semua
) merupakan grup abelian, (
⦁)
bersifat asosiatif, dan memenuhi sifat distribusi kanan dan kiri. ii. (
⦁) merupakan suatu ring karena himpunan
syarat aksioma suatu ring yaitu (
memenuhi semua
) merupakan grup abelian, (
⦁)
bersifat asosiatif, dan memenuhi sifat distribusi kanan dan kiri. iii. (
⦁) bukan suatu ring karena (B9,+) maupun (B9,⦁) bukan suatu grup
seperti yang telah dijelaskan pada Contoh 2.1. Definisi 2.4 (Sukirman, 2006: 35) Diberikan (
⦁) suatu ring. Apabila
ring, maka dikatakan bahwa
,
dan (
⦁) adalah suatu
adalah subring dari .
8
Contoh 2.3. Misalkan
adalah ring bilangan bulat terhadap penjumlahan dan perkalian
aritmetik.
adalah himpunan semua bilangan genap dan
penjumlahan dan perkalian aritmetik adalah ring dan karena bagian dari , maka
terhadap
adalah himpunan
adalah subring dari .
Suatu subring yang memiliki sifat khusus disebut dengan ideal. Berikut diberikan definisi ideal. Definisi 2.5 (Sukirman, 2006: 50). Diberikan
suatu ring dan
subring dari , maka:
i.
disebut ideal kanan dari , jika
ii.
disebut ideal kiri dari , jika
iii.
disebut ideal dua sisi dari
,
berlaku
, , jika
berlaku ,
. .
berlaku
dan
. Teorema 2.1 (Sukirman, 2006: 51). Diberikan
adalah ring,
,
. S adalah ideal dari
jika dan hanya
jika: i.
;
ii.
,
dan
.
Bukti: ( ) Diketahui
suatu ideal dari
yang memenuhi
,
maka menurut definisi, dan
,
adalah dubring dari berlaku
dan
.
9
( ) Apabila
dan menurut ketentuan
adalah subring dari maka
. Selanjutnya, karena
dan ,
, maka
, berlaku
dan
adalah ideal dari .
Contoh 2.4. {[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [
Misalkan
himpunan semua kelas bilangan bulat modulo 12. (
][
adalah
⦁) merupakan ring {[ ] [ ] [ ]}
dengan operasi penjumlahan dan perkalian modulo 12 maka adalah ideal dari
]}
yang tidak memuat pembagi nol.
Definisi 2.6 (Hartley & Howkes, 1970: 59). Suatu ideal
atas daerah integral
oleh elemen tunggal
disebut ideal utama atas
, sedemikian sehingga
jika
dibangun
.
Contoh 2.5. Jika
adalah daerah integral, maka ideal { } dan
adalah ideal utama yang
dibangun oleh masing-masing 0 dan 1. Definisi 2.7 (Herstein, 1996:148). Suatu ideal dari
atas ring
adalah ideal maksimal dari
jika dan hanya jika ideal
memuat yaitu itu sendiri dan .
Definisi 2.8 (Vanstone dan Oorschot, 1989: 21). Sebuah lapangan F merupakan himpunan elemen-elemen tertutup yang memuat dua operasi biner yaitu penjumlahan dan perkalian dinotasikan dengan “+” dan “⦁” sehingga aksioma-aksioma di bawah ini terpenuhi untuk semua i.
(
)
(
.
)
ii.
10
iii.
ada elemen
iv.
ada elemen
v.
⦁( ⦁ )
vi.
⦁
ada elemen
viii.
untuk setiap ⦁(
(
sedemikian sehingga
)
( ⦁ )⦁
⦁
vii.
ix.
sedemikian sehingga
)
sedemikian sehingga ⦁ sedemikian sehingga ⦁
, ada elemen ⦁
⦁ .
Berikut diberikan contoh lapangan. Contoh 2.6. Diberikan
{[ ] [ ] [ ] [ ] [ ] [ ] [ ]},
himpunan
yang
merupakan
himpunan semua kelas bilangan bulat modulo 7 dengan penjumlahan modulo 7 dan perkalian modulo 7 yaitu (
⦁), maka (
⦁) yang merupakan suatu
lapangan. Berikut diberikan bukti dengan menggunakan Tabel Cayley
Tabel 2.1. Tabel Cayley
[0] [1] [2] [3] [4] [5] [6]
[0] [0] [1] [2] [3] [4] [5] [6]
[1] [1] [2] [3] [4] [5] [6] [0]
:
Hasil Penjumlahan Modulo 7 [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] diagonal utama
11
Tabel 2.2. Tabel Cayley
[0] [1] [2] [3] [4] [5] [6]
[0] [0] [0] [0] [0] [0] [0] [0]
[1] [0] [1] [2] [3] [4] [5] [6]
[2] [0] [2] [4] [6] [1] [3] [5]
Hasil Perkalian Modulo 7 [3] [0] [3] [6] [2] [5] [1] [4]
[4] [0] [4] [1] [5] [2] [6] [3]
[5] [0] [5] [3] [1] [6] [4] [2]
[6] [0] [6] [5] [4] [3] [2] [1] diagonal utama
Memperhatikan tabel Cayley
untuk penjumlahan modulo 7 memenuhi sifat
tertutup, elemen nolnya adalah [0], invers terhadap penjumlahan modulo 7, yaitu [ ]
[ ],
[ ]
[ ]
[ ]. Tabel simetris terhadap diagonal utama, sehingga penjumlahan
[ ],
[ ]
[ ],
[ ]
[ ],
[ ]
[ ]
[ ],
modulo 7 maupun perkalian modulo 7 bersifat komutatif. Himpunan
[ ],
terhadap
perkalian modulo 7 bersifat tertutup, memiliki elemen kesatuan yaitu [1], invers terhadap perkalian modulo 7, yaitu [ ] [ ]
[ ],[ ]
[ ],[ ]
[ ] , [ ]
[ ] . Jadi setiap elemen
perkalian dan penjumlahan memiliki invers. Terbukti bahwa (
[ ] , [ ]
[ ] ,
terhadap operasi ⦁) merupakan
suatu lapangan. Suatu lapangan yang memuat sebanyak elemen berhingga disebut dengan lapangan berhingga. Himpunan kelas bilangan bulat modulo dengan
yang dinotasikan
atas operasi standar penjumlahan dan perkalian modulo
disebut
lapangan. Teorema 2.2 (Vanstone & Oorschot , 1989 : 22). Himpunan Zn merupakan lapangan berhingga jika dan hanya jika
bilangan
prima.
12
Bukti: ( ) Ak n ditunjukk n himpunan Zn merupakan lapangan berhingga jika bilangan prima. Diketahui
bukan bilangan prima, maka . Karena
dengan
merupakan lapangan, maka setiap elemen tak
nolnya pasti memiliki invers. Misalkan (
) dan
akibatnya
( (
bilangan prima,
adalah invers dari
). Karena
) yang berarti
kontradiksi dengan pengandaian bahwa
, berarti (
maka sehingga
),
prima. Hal ini
bukan bilangan prima. Jadi
bilangan
prima. ( )Akan ditunjukkan jika
bilangan prima maka himpunan Zn merupakan
lapangan berhingga. Diketahui
bilangan prima. Untuk dapat membuktikan
merupakan lapangan,
maka akan dibuktikan bahwa setiap elemen tak nol mempunyai invers. Karena adalah bilangan prima, maka terdapat bilangan bulat (
dan
), diperoleh
(
)
, untuk
sedemikian sehingga (
. Akibatnya yang berarti
). Jadi terbukti bahwa setiap elemen
tak nolnya mempunyai invers. Jadi Zn adalah lapangan jika
prima. Karena Zn
memiliki elemen bilangan berhingga maka Zn adalah lapangan berhingga. Berikut diberikan contoh lapangan berhingga. Contoh 2.7. dan
merupakan lapangan berhingga, tetapi
dan
bukan lapangan berhingga karena pada operasi perkalian untuk elemen [3]
13
di
tidak mempunyai invers. Selain itu
serta elemen [3] dan [5] di
juga bukan lapangan berhingga karena pada operasi perkalian untuk elemen [2] dan [5] tidak mempunyai invers. Diberikan ring
atas ring
dan ideal
. Karena
adalah grup atas
penjumlahan dan adalah subgrup normal dari , dapat dibentuk suatu grup {
faktor
}. Dengan menganalogikan grup atas koset-koset,
didefinisikan hasil kali dua koset (
).(
)=
.
Teorema 2.3 (Gallian, 2006:269) Suatu ring komutatif
dengan elemen kesatuan dan adalah ideal dari . Suatu
adalah lapangan jika dan hanya jika adalah ideal maksimal. Bukti: ( ) Akan ditunjukkan suatu Diketahui
adalah lapangan jika
lapangan dan ideal dari
yang memuat . Diketahui
komutatif dengan elemen kesatuan dan tetapi
. Suatu
perkalian dari Sehingga,
karena (
adalah ideal dari
adalah elemen tak nol dari
sedemikian hingga (
)
adalah ideal maksimal.
)(
suatu ring
. Diberikan
, jika terdapat elemen
)
, yaitu identitas
maka terdapat
dan
. Oleh karena itu
.
, terbukti
ideal
maksimal. ( ) Akan ditunjukkan jika Diketahui maksimal dan
lapangan dan tetapi
invers perkalian. Memandang
adalah ideal maksimal.maka ideal dari
adalah lapangan
yang memuat .Diketahui
. Hal ini menunjukkan bahwa {
ideal
memiliki
}. Ini adalah ideal dari
14
yang memuat . Karena , dengan
adalah ideal maksimal maka
. Sehingga,
,
, maka (
)(
).
Teorema 2.4 (Gallian, 2006: 311). Diberikan lapangan
dan ( )
[ ], ideal 〈 ( )〉 adalah ideal maksimal di
[ ] jika dan hanya jika ( ) polinomial tak tereduksi atas lapangan . Bukti: ( ) Diketahui 〈 ( )〉 ideal maksimal di
[ ]. Polinomial
( ) juga bukan
polinomial nol maupun elemen identitas di ( ), karena { } maupun [ ] adalah ideal maksimal di lapangan [ ]
[ ]. Jika
, maka 〈 ( )〉
( )
〈 ( )〉
( ) ( ) adalah faktor dari [ ]. Sedemikian, 〈 ( )〉
( ) atas
〈 ( )〉 atau
〈 ( )〉.
( ) Diketahui ( ) polinomial tak tereduksi atas [ ] sedemikian sehingga 〈 ( )〉 ideal utama , maka 〈 ( )〉 maka ( )
. Diberikan
[ ]. Karena
〈 ( )〉 untuk suatu ( ) di ( ) ( ), dengan ( )
suatu ideal di
[ ] adalah daerah asal
[ ]. Jadi, untuk 〈 ( )〉
[ ]. Karena ( ) polinomial tak
tereduksi atas , maka ( ) adalah konstan atau ( ) konstan. Polinomial tak tereduksi adalah polinomial yang tidak dapat dinyatakan sebagai hasil perkalian dari dua polinomial dengan derajat yag lebih kecil dari derajat ( ) dalam atas lapangan
[ ]. Himpunan
[ ] adalah semua polinomial dalam
( prima) dengan setiap polinomial berderajat hingga.
15
Akibat 2.1 (Gallian, 2006: 311). Jika
adalah lapangan dan ( ) polinomial tak tereduksi atas
[ ]
maka
〈 ( )〉 adalah lapangan. Contoh 2.8. Diberikan 〈
〉 adalah ideal maksimal di
( ) sehingga
( ) 〈
〉 adalah lapangan. Lapangan berhingga
yang memuat
Galois) yang dinotasikan dengan
elemen disebut Galois field (lapangan
( ).
Definisi 2.9 (Vanstone & Oorschot, 1989 : 28). Jika F suatu lapangan berhingga dengan bilangan prima dan
bilangan asli, maka
elemen, dan dilambangkan dengan
Perhatikan bahwa q mempunyai bentuk
( ).
, yaitu q merupakan suatu
bilangan prima p atau hasil pemangkatan dari p. Notasi GF ( lapangan dengan karakteristik p. Lapangan
dengan p
) adalah suatu
dapat dinotasikan dengan
( ).
Definisi 2.10. Untuk suatu polinomial
( )
( ), kelas ekuivalensi yang memuat
( )
( ) adalah [ ( )]
{ ( )
( )
( )
( )(
( ))},
yaitu himpunan semua polinomial yang apabila dibagi dengan
( )
menghasilkan sisa yang sama dengan ( ). Operasi penjumlahan dan perkalian dalam kelas-kelas ekuivalensi tersebut didefinisikan sebagai berikut. Untuk ( ) ( )
[ ],
[g(x)]+[ f (x)] = [g(x) + f (x)] dan [g(x)].[ f (x)] = [g(x). f (x)].
16
Diberikan
[ ]
( ) yaitu himpunan semua kelas-kelas ekuivalensi dalam
[ ] yang kongruen modulo ( ), dengan ( ) adalah polinomial tak tereduksi. Contoh 2.9. ( ) 〈
Mengikuti contoh 2.6,
〉 adalah suatu lapangan yang
(
)
)
{[ ] [ ]} dan memiliki 4 elemen.
dengan koefisien elemen-elemennya atas Elemen-elemen dari
(
( ) 〈
〉
{[ ] [ ] [ ] [
]}.
Definisi 2.11 (Vlcek, 2004). Polinomial tak tereduksi ( ) dengan derajat jika
adalah bilangan bulat positif terkecil, untuk
berlaku
( ) dikatakan primitif
atas
( ) faktor dari
,
.
Berikut diberikan contoh lapangan Galois yang dikonstruksi dari polinomial primitif. Contoh 2.10. Pada
(
), polinomial primitif berderajat 3 yang membangun semua elemen
lapangan adalah ( )
. Polinomial primitif ( ) atas
koefisien variabel adalah elemen
( )
Diberikan
adalah akar primitif atas
{ (
}.
) maka
( dihasilkan elemen dari
(
dan )
) seperti pada Tabel 2.3.
Tabel 2.3. Elemen-Elemen Bentuk Pangkat
( ) dengan
Bentuk Polinomial
(
) Bentuk Biner 000 001
17
010 100 011 110 111 101 001
Berdasarkan
Tabel
2.3
dapat
dinyatakan
elemen
GF(
)
=
{000,001,010,011,100,101,110,111}. B. Kode Linear 1.
Ruang Vektor atas Lapangan Berhingga
Definisi 2.12 (Ling dan Xing, 2004: 17). Diberikan
suatu lapangan berhingga dengan elemen sebanyak q.
Himpunan tak kosong V, dengan operasi penjumlahan vektor dan perkalian skalar terhadap elemen-elemen
adalah ruang vektor atas
dan untuk setiap
untuk setiap
berlaku aksioma berikut:
i. ii. (
)
iii. ada elemen iv. ada elemen
(
)
yang berlaku yang berlaku
untuk setiap (
)
(
)
untuk
setiap v. vi.
18
(
vii.
)
viii. ( ix. ( x.
) )
(
)
apabila 1 adalah elemen identitas terhadap perkalian dari
maka
memenuhi Himpunan semua vektor dengan panjang
atas lapangan
ditulis
.
Contoh 2.11. Ruang vektor atas
yaitu {
}.
C. Codeword Definisi 2.13 (Ling & Xing, 2004 : 5). Diberikan
{
} adalah suatu himpunan yang berukuran
, yang
dapat disebut alfabet kode dan elemen-elemennya disebut simbol kode. i.
Suatu word
panjang n yaitu barisan
dengan
untuk setiap i. ii. Kode blok
dengan panjang
kosong C pada word
atas
merupakan himpunan tak
mempunyai panjang
yang sama.
iii. Elemen dari C disebut dengan codeword. iv. Kode dengan panjang
dan berukuran
disebut dengan kode-(
).
Berikut diberikan contoh kode. Contoh 2.12. Suatu himpunan yang beranggotakan warna yaitu B={merah, kuning, hijau, biru, ungu} akan dikodekan menjadi suatu pesan rahasia yang terdiri dari angka biner 0 dan 1 dengan panjang 3 yaitu :
19
Tabel 2.4. Pesan Warna dalam Bentuk Kode Warna Kode Merah 001 Kuning 010 Hijau 011 Biru 100 Ungu 101 Jadi himpunan B dapat ditulis dalam bentuk kode yaitu B={001, 010, 011, 100,101}. Contoh 2.13. {
(i)
} adalah kode-(
) yang artinya kode dengan panjang 2
berukuran 4. {
(ii)
} adalah kode-(
) yang artinya kode dengan
panjang 3 berukuran 4. {
(iii)
} adalah kode-(
) yang artinya
kode dengan panjang 4 berukuran 6. Kode atas alfabet kode {
alfabet kode {
alfabet kode
{
} disebut dengan kode biner. Kode atas
} disebut dengan kode terner. Sedangkan, kode atas } disebut dengan kode quarterner.
D. Kode Blok Definisi 2.14 (Vanstone dan Oorschot, 1989). Kode Blok C dengan panjang himpunan
berisi M elemen atas lapangan A adalah
tupel yang berjumlah M dengan masing-masing koordinat dari
tupel yang diambil dari simbol pada lapangan A dan dinotasikan dengan kode [
] atas lapangan A.
20
[
Elemen-elemen dari kode elemen-elemen [
] disebut dengan codeword. Sedangkan
tupel (blok dengan panjang n) yang tidak berada dalam blok
] disebut dengan word.
Berikut diberikan contoh kode blok. Contoh 2.14. C[2,4] = {00,01,10,11} atas
.
C[3,8] = {000,001,010,011,100,101,110,111} atas
.
C[3,27] = {000,001,002,010,020,011,012,021,022,100,200,101,102,201, 202,110,210,220,120,111,112,121,122,211,212,221,222} atas
.
C[5,12]0=0{00001,00010,00100,01000,00011,00101,00110,01001,01010,01100, 00111,01111} atas
.
A. Jarak Hamming dan Bobot Hamming Jarak hamming digunakan untuk menghitung banyaknya perbedaan posisi dua codeword. Misalkan, jarak hamming antara dua codeword banyaknya posisi yang berbeda antara dua codeword dinotasikan (
dan
dan
artinya
. Jarak hamming
). Berikut diberikan definisi jarak hamming.
Definisi 2.15 (Ling & Xing, 2004: 9). Diberikan x dan y adalah word dengan panjang n atas lapangan A, jarak hamming dari x dan y dinotasikan dan
(
) dengan x dan y berbeda. Jika
, maka (
)
(
)
(
).
21
Berikut diberikan contoh menghitung jarak hamming. Contoh 2.15. Diberikan codeword
sebagai berikut: ,
Jarak hamming (
)
, (
)
, (
)
.
Definisi 2.116 (Vanstone dan Oorschot, 1989 : 7). Diberikan C suatu kode [
] maka jarak hamming d dari kode C adalah
sebagai berikut: { (
)
}
Artinya, jarak hamming dari suatu kode adalah jarak minimum antara dua codeword yang berbeda, atas semua pasang codeword. Berikut diberikan contoh menghitung jarak hamming suatu kode blok. Contoh 2.16. Diberikan kode [
]
{
}:
(
)
(
)
(
)
(
)
dihasilkan jarak hamming dari kode C sebagai berikut: (
)
(
)
(
)
(
)
(
)
(
)
sehingga disimpulkan bahwa kode C mempunyai jarak
.
Definisi 2.17 (Ling & Xing, 2004 : 48). Jika C suatu kode maka bobot hamming minimum dari C dilambangkan dengan ( ) yang berarti bobot terkecil dari codeword yang bernilai tak nol dari C.
22
Berikut diberikan contoh menghitung bobot hamming. Contoh 2.17. Diketahui codeword
,
bobot hamming untuk codeword (
, dan
maka
adalah :
)
(
)
(
)
.
Definisi 2.18 (Ling & Xing, 2004 : 46). Suatu kode C (C tidak harus linear), bobot hamming minimum dari C dinotasikan dengan w(C) yang merupakan bobot terkecil dari codeword tak nol dari C, didefinisikan w(C)=
in
{ ( )}.
Berikut diberikan contoh bobot hamming suatu kode blok. Contoh 2.18. Diberikan kode [
]
{
}:
(
)
(
)
(
)
(
)
dihasilkan bobot hamming dari kode C sebagai berikut: ( )
( )
sehingga disimpulkan bahwa bobot hamming kode C adalah
( ) ( )
.
B. Pengertian Kode Linear Pengkodean yang baik adalah proses encoding dan decoding apabila timbul kesalahan dapat dideteksi dan dapat diperbaiki. Alfabet pada kode dalam kode
23
linear merupakan elemen lapangan berhingga
. Kode yang terbentuk oleh ruang
vektor atas lapangan berhingga disebut kode linear. Berikut diberikan definisi kode linear. Definisi 2.19 (Ling & Xing, 2004 : 45). Kode linear C dengan panjang n atas
merupakan subruang vektor atas
dengan
adalah himpunan semua vektor dengan panjang n yang entri-entrinya
adalah
elemen
{(
Bentuk
)
Kode ( lapangan
.
adalah
sebagai
berikut
:
}.
) adalah kode linear
dengan panjang
dan berdimensi
atas
(Ling & Xing, 2004: 46).
Berikut diberikan contoh kode linear. Contoh 2.19. ={0000, 1000, 0100, 1100} ={0000, 1100, 0011, 1111} {
}.
dan atas
merupakan kode linear atas
, sedangkan
merupakan kode linear
.
C. Kode Siklik Definisi 2.20 (Ling & Xing, 2004:133). Himpunan S atas
adalah kode siklik apabila terdapat (
maka juga terdapat (
)
)
.
Berikut diberikan contoh kode siklik.
24
Contoh 2.20. (i)
Kode C-(
) yaitu kode
= {
} merupakan kode siklik
karena perputaran dari setiap codeword pada
merupakan codeword pada
C juga. (ii)
Diberikan kode C-(
) yaitu
{1101000, 0110100, 0011010, 0001101}
merupakan kode siklik karena perputaran dari setiap codeword pada merupakan codeword pada C juga. (iii)
Diberikan kode
{
} merupakan kode siklik
karena perputaran dari setiap codeword pada
merupakan codeword pada S
juga. D. Polinomial Generator { } dengan panjang
Polinomial generator merupakan kode siklik C , yang terdapat polinomial monik unik
( )
atas
berderajat minimal
(Stichtenoth, 2009 : 317). Polinomial monik adalah polinomial dengan koefisien tak nol pada pangkat tertinggi dari . Polinomial monik
( ) membagi
yaitu
dan membangun C sehingga
polinomial generator juga membagi
. Bentuk umum dari polinomial
generator ( ) adalah sebagai berikut. ( )
dengan
∏(
adalah unsur primitif dalam
) ( ) dan
adalah banyaknya -error
yang dapat dikoreksi. Berikut diberikan contoh polinomial generator.
25
Contoh 2.21 (Vanstone & Oorschot, 1989:29). Polinomial generator atas GF(9) yang terbentuk atas fungsi ireduksibel ( ) [ ]. Untuk mencari elemen primitif perlu dicoba dan jika
dari dimisalkan
ternyata bukan elemen primitif. Tetapi, jika diambil
maka hasilnya sebagai berikut: (
)
(
)
(
)
(
)
Jadi
. . . .
(
)
(
)
(
)
(
)
. . . .
merupakan polinomial generator dari GF(9)*. Notasi GF(9)*
menerangkan polinomial generator
yang tidak menghasilkan
polinomial 0. E. Matriks Generator dan Matriks Parity-Cek Matriks generator digunakan untuk membentuk suatu kode linear. Setelah matriks generator terbentuk, kode akan dikirimkan yang nantinya akan diterima oleh pengguna. Apabila kode yang diterima tidak sesuai dengan yang dikirimkan maka perlu penambahan redudansi ke dalam informasi yang mengalami error agar dapat mendeteksi maupun mengoreksi informasi yang salah seperti aslinya. Redundansi yang dimaksud adalah bit-bit untuk mengecek terjadinya error yang dikenal dengan nama matriks parity-cek. Definisi 2.21 (Ling & Xing, 2004 : 52). i.
Matriks generator untuk kode linear C adalah matriks G dimana baris-baris membentuk basis untuk C. Bentuk standar matriks generator adalah (
).
26
ii. Matriks parity-cek H dari kode linear C adalah matriks generator untuk kode dual
. Bentuk standar matriks parity-cek adalah (
Jika C merupakan kode linear-( matriks berukuran
).
) maka matriks generator untuk C adalah
dan matrisk parity-cek untuk C berukuran (
)
. Berikut diberikan contoh bentuk matriks generator dan matriks parity-cek. Contoh 2.22. Diberikan matriks ̃ yang membangun kode-( ̃
) atas
[
( ), yaitu
].
Operasi baris elementer yang sesuai terhadap ̃ untuk menghasilkan matriks G yang membangun kode yang sama sebagai berikut:
[
]
[
]
[
]
[
]
[
]
[
]
sehingga dihasilkan matriks G adalah
27
[
[
] yang mempunya bentuk
[
diperoleh matriks
].
Matriks generator untuk kode dual [
berbentuk [
], sehingga
atau disebut dengan matriks parity-cek H
], yaitu ]
[
[
]
]
[
[
][
] ].
Contoh 2.23. Diketahui kode C-(6,3) biner atas
dengan matriks generator H untuk
sebagai
berikut: [ Matriks H di atas berbentuk
]. [
] sehingga didapatkan matriks [
Matriks generator
untuk kode
dihasilkan matriks generator [
]. [
[
]
] sehingga
yaitu
]
[
berbentuk
]
[
[
]
].
28
F. Syndrome Definisi 2.22 (Ling S. & Xing C, 2004 : 59). Diberikan
suatu
(
kode )
linear
dengan
panjang
atas
dan
. Coset dari C yang ditentukan oleh u adalah himpunan {
}
{
}
.
Definisi 2.23 (Ling S. & Xing C, 2004 : 60). Suatu word dengan bobot hamming terkecil dalam suatu koset disebut coset leader. Contoh 2.24. Diberikan suatu kode - (
) C dengan matriks generator dan matriks parity-cek
yaitu [
],
[
] serta kode
{
yaitu }.
Berikut diberikan tabel standar array untuk kode-(5,3) C. Tabel 2.5 Standar Array kode-(5,3) C Coset Leader 00000
00000 10011 01001 00110 11010 10101 01111 11100
00001
00001 10010 01000 00111 11011 10100 01110 11101
00010
00010 10001 01011 00100 11000 10111 01101 11110
10000
10000 00011 11001 10110 01010 00101 11111 01100
Berdasarkan Definisi 2.21, coset leader dipilih dari word yang berbobot terkecil yaitu 1. vektor-vektor kolom pertama pada Tabel 2.5 merupakan coset
29
leader dari koset-koset pada kolom selanjutnya. Selain vektor 00010, koset 00010+C juga memiliki coset leader lain yaitu 00100. Selain itu, vektor 00001 pada koset 00001+C juga memiliki coset leader lain yaitu 01000. Berikut diberikan definisi yang berkaitan dengan syndrome. Definisi 2.24 (Ling & Xing, 2004 : 62). Diberikan C adalah [
] kode linear atas
matriks parity-cek untuk C. Untuk setiap word ( )
dan diberikan H adalah
, maka syndrome oleh u adalah
.
Berikut diberikan contoh menghitung syndrome. Contoh 2.25. Diketahui suatu matriks generator dan matriks parity-cek serta kode C seperti pada Contoh 2.24. Berdasarkan Tabel 2.5 diketahui coset leader digunakan untuk menghitung syndrome dengan rumus
yang
( )
sebagai
berikut.
(
)
[
]
[ [
(
)
[
(
)
[
]
]
]
[
[ [
]
]
]
(
)
[
]
[
]
]
] [
[
]
Hasil perhitungan pada Contoh 2.24 dan Contoh 2.25 dinyatakan pada Tabel 2.6 berikut.
30
Tabel 2.6 Coset Leader dan Syndrome kode-( Coset Leader
Syndrome
00000
00
00001
01
00010
10
10000
11
)C
G. Encoding dan Decoding (Vanstone & Oorschot, 1989:1) Teori kode pengoreksi error merupakan salah satu cabang matematika yang bergerak dibidang transmisi dan penyimpanan data. Media informasi tidak selalu memberikan keakuratan dalam menerima informasi, adakalanya terjadi suatu gangguan saat pengiriman pesan/informasi. Apabila terjadi suatu error pada saat pengiriman pesan/informasi, kesalahan tetap dapat terdeteksi bahkan diperbaiki dengan menambahkan suatu redundansi ke dalam pesan/informasi yang telah diubah dalam bentuk kode. Sumber Informasi
Sumber Encoder
Saluran (Channel)
Sumber Decoder
Penerima
Gambar 2.1. Diagram Proses Pengiriman Pesan/Informasi
1.
Proses Encoding Suatu pesan/informasi diubah ke dalam bentuk kode untuk memudahkan
proses pengiriman data (pesan/informasi). Proses mengubah pesan/informasi ke dalam bentuk kode disebut dengan proses encoding. Misalkan suatu himpunan
31
simbol {A,B,C,D} akan ditransmisikan ke dalam bentuk kode biner dengan panjang 2, yaitu: A = 00 B = 10 C = 01 D = 11 Apabila pengirim mengirimkan sebuah kode 00, maka penerima akan membaca kode 00 sebagai A. Contoh 2.26. Diberikan matriks generator adalah
{
}, maka
Jadi pesan yang dikirimkan adalah
[
] dan pesan yang akan dikirim
dikodekan menjadi [
]
[
]
[
]
[
]
{
}.
Sumber informasi mengirimkan simbol dari himpunan informasi {A,B,C,D}. Kemudian, sumber encoder memasangkan atau memetakan setiap informasi dengan urutan biner (0,1) dan ditransmisikan. Selanjutnya sumber decoder menerima urutan biner dari channel atau saluran, lalu dikonversi kembali ke huruf alfabet untuk dapat diterima oleh pengguna (penerima).
32
2.
Proses Decoding Proses mengembalikan kode menjadi suatu pesan/informasi seperti yang
dikirimikan disebut dengan proses decoding. Pada saat proses decoding akan terjadi suatu proses deteksi error dan pengoreksian error jika terjadi error. Artinya, jika sumber decoder membaca informasi seperti yang dikirimkan oleh sumber encoder maka tidak perlu ada proses pengoreksian error. Sebaliknya, jika sumber decoder membaca pesan atau informasi yang salah maka perlu dilakukan suatu proses pengoreksian error. Pada Contoh 2.26, jika sumber encoder mengirimkan 00 dan sumber decoder menerima 01, maka telah terjadi satu kesalahan. Sumber decoder tidak bisa mengetahui terjadinya error karena pesan 01 juga merupakan informasi valid dari C Jika penerima membaca 1100 akan diketahui bahwa telah terjadi kesalahan karena urutan ini bukan salah satu input dari sumber encoder. Apabila kesalahan acak maka decoder akan mentransmisikan pesan ke 1110 karena urutan kode yang diterima hanya terjadi satu error. Definisi 2.25. Suatu kode C dapat mendeteksi sebanyak codeword (
)
kesalahan (
) jika untuk setiap
yang dikirim kemudian diterima codeword sehingga
dengan
.
Selanjutnya diberikan teorema mengenai kemampuan deteksi kesalahan kode.
33
Teorema 2.5. Suatu kode C dikatakan mendeteksi
kesalahan jika dan hanya jika ( )
(
). Dengan kata lain, kode dengan jarak d dapat mendeteksi dengan tepat (d-1) kesalahan. Bukti: ( ) Diketahui (
)
( )
( )
, maka terdapat . Jika codeword
maka terjadi kesalahan sebanyak
sedemikian sehingga
yang dikirim dan diterima codeword ( ) dengan
kesalahan tersebut tidak terdeteksi karena
( )
.Akan tetapi
. Jadi, C bukan mendeteksi u
kesalahan. ( ) Diketahui berakibat jika
( ) dan
. Menurut definisi jarak dari suatu kode, hal ini sedemikian sehingga
(
)
( ), maka
. Artinya jika terjadi kesalahan hingga sebanyak u, maka kesalahan tersebut selalu terdeteksi. Setelah kode yang mengalami kesalahan terdeteksi maka langkah selanjutnya adalah pengoreksian. Ada beberapa macam kode pengoreksi error. Diantaranya yaitu kode Reed Solomon yang merupakan subkelas dari kode BCH. 3.
Kode BCH Kode BCH adalah suatu kelas kode yang ditemukan oleh R.C. Bose dan D.
Ray Chaudhuri pada tahun 1960 dan juga ditemukan secara independen oleh A. Hocquenghem pada tahun 1959. Nama BCH diambil dari penemu-penemu tersebut Bose Chaudhuri Hocquenghem.
34
Definisi 2.26 (Vanstone & Oorschot, 1989 : 205). ( ) dengan panjang blok
Kode BCH atas (designed distance) ( )
dan jarak yang ditentukan
adalah suatu kode yang dibentuk oleh suatu polinomial
{ ( )
}
[ ] dengan KPK adalah kelipatan
persekutuan terkecil. Himpunan akar dari polinomial ( ) memuat yang berbeda
, dengan
elemen kesatuan dan
elemen
adalah suatu akar primitif ke-n dari
adalah suatu bilangan bulat.
Definisi 2.27 (Vanstone & Oorschot, 1989 : 205). Jika
untuk bilangan bulat positif untuk bilangan bulat positif m,
maka kode tersebut adalah suatu kode primitif, dan jika
maka kode
tersebut disebut narrow-sense. Elemen
adalah suatu akar ke- dari elemen kesatuan, sehingga
merupakan suatu akar ke(
) membagi (
dari elemen kesatuan untuk semua
) dan ( ) juga membagi (
juga
sehingga
).
Contoh 2.27. Misal
suatu elemen primitif dari
Polinomial minimal dari ( )
dan
(
) sedemikian sehingga
.
adalah berturut-turut
,
( )
,
( )
,
Kode BCH yang mengoreksi dua error dengan panjang dibentuk )
oleh
( )
{
( )
( )}
. Didapatkan
(
)( sehingga kode tersebut
35
adalah suatu kode (
). Bobot dari polinomial generatornya adalah 5,
sehingga kode tersebut adalah suatu kode (
).
H. Pengantar Kode Reed Solomon pada Aplikasi Steganography 1.
Sejarah Kode Reed Solomon Gustave Solomon lahir di Brooklyn, New York pada tanggal 27 Oktober
1930, dan meninggal pada tanggal 31 Januari 1996 di Beverly Hills, CA. Dia adalah seorang ahli matematika dan insinyur yang merupakan salah satu penemu dari teori aljabar tentang error-correction. Solomon
bersama-sama
dengan
Irving
S.
Reed
dikenal
telah
mengembangkan sebuah teori aljabar tentang error-detecting dan errorcorrecting codes yang dikenal sebagai Reed Solomon error correction. Kode ini digunakan untuk melindungi kerahasiaan informasi digital, dan telah digunakan secara luas di bidang komunikasi dan media penyimpanan digital modern. Kasus yang paling umum misalnya digunakan kode RS-(255, 223) dimana pesan 223 simbol (masing-masing delapan bit ) di encode menjadi 255 simbol. Standar RS-(255, 223) kode Reed Solomon mampu memperbaiki hingga 16 simbol kesalahan dalam setiap codeword. Kode Reed Solomon ditemukan oleh Irving S. Reed dan Gustave Solomon pada tahun 1960. Mereka membawakan jurnal yang berjudul “Polynomial Codes over Certain Finite Fields" dalam seminarnya kala itu. Pada saat artikel tersebut ditulis, teknologi digital saat itu tidak cukup maju untuk menerapkan konsep tersebut. Aplikasi dari kode tersebut baru
36
bisa digunakan pertama kali pada tahun 1982, yang diproduksi secara masal yaitu berupa cakram padat / compact disc, di mana dua kode interleaver Reed-Solomon digunakan. Algoritma decoding yang efisien untuk kode Reed Solomon dengan jarak yang besar telah dikembangkan Elwyn Berlekamp dan James Massey pada 1969. Sekarang ini kode Reed Solomon telah dimanfaatkan untuk banyak aplikasi antara lain aplikasi komputer dan media panyimpanan seperti sistem RAID (Redundant Array of Independent Disks) pada hard disk drive, CD (compact disk), DVD (Digital Versatile Disk), dan blue-ray disk, telekomunikasi dan data teknologi seperti DSL (Digital Subscribe Line) & WiMAX (Worldwide Interoperability for Microwave Acces), dalam siaran televisi digital seperti sistem ATSC (Advanced Television Systems Committee) di Amerika, dan sistem DVB (Digital Video Broadcasting) di Eropa. Selain itu, aplikasi kode Reed Solomon untuk sarana bertukar informasi/pesan
yang
mengutamakan
tingkat
keamanan
adalah
steganography. 2.
Sejarah Steganography Steganography merupakan suatu cara penyembunyian pesan ke dalam
pean lainnya sedemikian rupa sehingga orang lain tidak menyadari adanya perubahan
di
dalam
pesan
yang
terkirim.
Kata
steganography
(steganography) berasal dari bahasa Yunani yaitu steganos yang artinya tersembunyi atau terselubung dan graphein yang artinya menulis sehingga steganography berarti “menulis tulisan yang tersembunyi atau terselubung”
37
(Sellars, 1996). Teknik ini biasa digunakan untuk menyembunyikan pesan rahasia pada media komunikasi. Catatan pertama tentang steganography ditulis oleh sejarawan Yunani Herodotus yaitu ketika Histaeus seorang raja kejam Yunani dipenjarakan oleh Raja Darius di Susa pada abad 5 Sebelum Masehi. Histaeus harus mengirim pesan rahasia kepada anak laki-lakinya Aristagoras di Militus. Histaeus menulis pesan dengan cara mentato pesan pada kulit kepala seorang budak dan ketika rambut budak itu mulai tumbuh, Histaeus mengutus budak itu pergi ke Militus untuk mengirim pesan di kulit kepalanya tersebut kepada Aristagoras. Teknik steganography yang lain adalah tinta yang tak terlihat. Teknik ini pertama kali digunakan pada zaman Romawi kuno dengan menggunakan air sari buah jeruk, urine, atau susu sebagai tinta untuk menulis pean. Cara membacanya adalah dengan dipanaskan di atas nyala lilin, tinta yang sebelumnya tidak terlihat setelah terkena panas akan berangsur-angsur menjadi gelap dan pesan dapat dibaca. Dari contoh steganography konvensional tersebut pada intinya adalah teknik steganography konvensional berusaha merahasiakan pesan komunikasi dengan cara menyembunyikan pesan atau mengkamuflase pesan. Maka, prinsip
dasar
dalam
steganography
dikonsentrasikan
kerahasiaan
komunikasinya bukan pada datanya (Johnson, 1998). Pada abad 20, steganography telah mengalami perkembangan. Steganography telah merambah juga ke media digital.
38
Sebagai contohnya, misalkan akan mengirimkan pesan tersembunyi yang berisi MERAH. Kalimat yang akan dikirimkan adalah Memang Enak Rasa Asam Harumanis. cover text/cover media
: emang nak asa sam arumanis
pesan tersembunyi
: MERAH
stego text (stegogramme) : Memang Enak Rasa Asam Harumanis.
39
