BAB II TEORI KODING DAN TEORI INVARIAN Pada bab 1 ini akan dibahas definisi kode, khususnya kode linier atas dan pencacah bobot Hammingnya. Hammingnya. Di samping itu, akan dijelaskan invarian, ring invarian dan strukturnya.
2.1. Teori Koding Teori koding adalah ilmu yang mempelajari mempelajari metode transmisi data melalui saluran komunikasi yang tidak bebas gangguan secara efisien dan akurat. Teori ini berkembang pesat terutama dalam penerapan sistem telekomunikasi. Perhatikan diagram sistem transmisi informasi pada gambar 1. Gangguan pada saluran informasi dapat menyebabkan pesan yang diterima tidak sama dengan pesan yang dikirim. Akan tetapi, jika digunakan kode yang dapat mendeteksi bahkan mengoreksi kesalahan, pesan dapat terkirim lebih efisien dan akurat.
transmisi informasi secara umum. Gambar 1.. Diagram sistem transmisi
4
Kode atas
Misalkan suatu himpunan hingga. Maka adalah himpunan semua -
pasangan terurut (-tuple) elemen atau himpunan vektor yang setiap
koordinatnya adalah elemen , = , , … , ∈ , = 1, … , .
dikatakan kode atas dengan panjang jika adalah subhimpunan tak
kosong dari . Anggota atau elemen dari kode disebut katakode. Kode linier atas
Misalkan suatu lapangan hingga dengan elemen, = , suatu
bilangan prima dan bilangan bulat positif. suatu kode linier [, ] atas
merupakan subruang berdimensi dari .
Misalkan , ∈ . Hasil kali dalam antara vektor dan (ditulis ∙ )
didefinisikan sebagai ∙ = ∑! di . Jika ∙ = 0 %di &, dan dikatakan (saling) ortogonal. Kode dual (dinotasikan ' ) dari kode didefinisikan
sebagai
' = ( ∈ ( ∙ ) = 0 %di &, untuk setiap ) ∈ .
Kode ini merupakan kode linier [, − ] atas atau subruang berdimensi
− dari .
Jika ' = , maka kode dikatakan kode swa-dual dan merupakan
subruang berdimensi /2 dari . Eksistensi kode swa-dual atas ditentukan lemma berikut.
5
Lemma 2.1.1 (Pless, 1968) Misalkan ≡ 167 4, kode swa-dual atas panjang ada ⟺ genap.
Misalkan ≡ 367 4, kode swa-dual atas panjang ada ⇔ habis dibagi empat.
Bobot, Distribusi Bobot, dan Pencacah Bobot Hamming Misalkan = , , … , ∈ , bobot Hamming dari , <= adalah
banyaknya koordinat yang tak nol pada vektor . Contoh : <=101 = 2, <=102023 = 4.
Distribusi bobot Hamming >? yaitu banyaknya katakode yang memiliki bobot Hamming = atau ditulis |A) ∈ |<=) = =B|.
Pencacah bobot Hamming dari suatu kode adalah sukubanyak CD (, E = F ( I∈D
E
GH?I H?I
= F >? ( G? E ? ?!J
Contoh : kode = A00, 11B memiliki CDK (, E = ( + E .
kode swa-dual linier [8,4] atas dengan bobot terkecil dari setiap katakode tak nol adalah 4, memuat kata-katakode
11000101
00000000
11101000
01110100
00111010
10011100
10100110
11010010
11111111
00010111
10001011
01100011
10110001
01011001
00101101
01001110
6
Kode ini memiliki pencacah bobot Hamming CDM (, E = ( N + 14( O E O + E N . Dari persamaan ini dapat kita ketahui informasi distribusi bobot katakodenya.
Hubungan antara pencacah bobot Hamming kode dual dan pencacah bobot Hamming kodenya disebut identitas MacWilliams, yang ditunjukkan dalam teorema berikut.
Teorema 2.1.2 (MacWilliams, 1963) Jika kode linear atas maka : CD P (, E =
1 C ( + − 1E, ( − E. || D
2.2. Teori Invarian Misalkan R , R , … , RS matriks-matriks kompleks × yang mempunyai invers. Jika dilakukan operasi perkalian matriks-matriks tersebut dalam semua kemungkinan, dapat dibentuk suatu grup U. Maka U memuat V, R , R , … , RS ,
R R , … , R R G , R G RW , … , dan dikatakan AR , R , … , RS B membangun U.
Asumsikan X = 6Y7ZU) yaitu banyaknya elemen U adalah berhingga (jika U tak berhingga maka teori invariant tidak berlaku). Misalkan [( = [( , ( , … , ( suatu sukubanyak dalam variabel dengan koefisien
kompleks,
maka
[(
dapat
ditulis
sebagai
jumlah
dari
\K …] ( K (M … (] . Jika \K …] tidak nol, \K …] ( K (M … (] disebut
7
bagian (term) dengan derajat + + ⋯ + , dan derajat dari sukubanyak
adalah derajat tertinggi dari bagian-bagian pada sukubanyak. Jika [( = 0 atau setiap bagian dari [( mempunyai derajat sama maka [( dikatakan homogen.
ℂ[( , ( , … , ( ]
adalah
himpunan
( , ( , … , ( dengan koefisien kompleks.
semua
sukubanyak
dalam
variabel
Misalkan R suatu matriks kompleks × , aksi matriks R terhadap
[( adalah R ∙ [( = [R ∙ (, fungsi sukubanyak yang variabel-variabelnya
ditransformasikan terhadap matriks R, dengan menganggap ( = ( , ( , … , (
sebagai vektor kolom.
Invarian Jika R ∙ [( = [R ∙ ( = [(, sukubanyak tersebut tidak berubah (invarian) terhadap aksi matriks R. [( invarian terhadap aksi oleh matriks-matriks di U atau cukup dikatakan [( invarian dari U, jika untuk setiap matriks R` ∈ U berlaku R` ∙ [( = [R` ∙ ( = [(.
−1 0 1 0 Contoh : Misalkan ab c, b cd grup matriks, maka ( , E , (E dan 0 −1 0 1
( O + ( W E + 5( + 2(E adalah sukubanyak yang merupakan invarian dari grup matriks tersebut.
Bagaimana cara mencari suatu invarian dari U? Teorema berikut menunjukkan invarian dapat dicari dengan merata-ratakan sebarang sukubanyak atas grup U.
8
Teorema 2.2.1 Misalkan [( sebarang sukubanyak maka g
1 [ f ( = F R` ∙ [( X `!
adalah invarian dari U. Bukti :
Ambil sebarang Rh ∈ U, maka Ri = Rh ∙ R` ∈ U untuk suatu R` ∈ U karena U
g grup. Dengan demikian, jika dilakukan aksi Rh pada [ f ( = g ∑`! R` ∙ [(, g
g
`!
i!
1 1 Rh ∙ [ f ( = F%Rh R` & ∙ [( = F Ri ∙ [( = [ f (. X X
[ f ( tak berubah terhadap aksi oleh matriks-matriks di U.
Jadi [ f ( adalah suatu invarian dari U.
■
Lebih lanjut, sebarang fungsi simetri dari g sukubanyak R ∙ [(, … , Rg ∙ [( adalah suatu invarian dari U.
Ring invarian Jika [, ℎ invarian dari U maka [ + ℎ, [ℎ, )[ () suatu bilangan kompleks), juga
invarian dari U, maka himpunan semua invarian dari U dinotasikan ℂ[(]k = A[(|[> ∙ ( = [(, untuk setiap > ∈ UB membentuk ring.
9
Salah satu masalah dalam bahasan dalam teori invarian adalah bagaimana mendeskripsikan ℂ[(]k = ℂ[( , ( , … , ( ]k . Karena transformasi oleh matriks-
matriks di U tak mengubah derajat dari sukubanyak, maka cukup dipelajari
invarian yang homogen (sebarang invarian adalah jumlah dari invarian-invarian homogen). Contoh : [ ( = ( O + ( W E + 5( + 2(E adalah invarian dari grup matriks
AV, −VB, merupakan jumlah dari invarian homogen berderajat 4 dan 2, [ ( =
( O + ( W E + 5( + 2(E.
Langkah selanjutnya adalah mencari basis untuk invarian, yaitu suatu himpunan invarian dimana sebarang invarian dapat diekpresikan dalam bagian-bagian dari himpunan ini.
Bebas aljabar Suku-sukubanyak [ (, [ (, … , [S (, dikatakan bergantung aljabar jika
terdapat suatu sukubanyak dengan koefisien-koefisien kompleks, yang tak
semuanya nol, sehingga %[ (, [ (, … , [S (& = 0. Jika tidak demikian disebut bebas aljabar.
Teorema 2.2.2 (Jacobson, 1964) + 1 buah sukubanyak dalam variabel bergantung aljabar.
10
Tipe basis pertama yang kita cari adalah himpunan invarian [ , [ , … , [ yang bebas aljabar. Berdasarkan teorema ini, sebarang invarian adalah bergantung
aljabar pada [ , [ , … , [ dan merupakan suatu akar dari persamaan sukubanyak
dalam [ , [ , … , [ . Teorema berikut menjamin adanya basis tersebut. Teorema 2.2.3 (Burnside, 1955) Selalu ada buah invarian [ , [ , … , [ di ℂ[(]k yang bebas aljabar.
Deskripsi yang lebih sesuai mengenai basis yaitu himpunan invarian A[ , [ , … , [l B,
dimana sebarang invarian adalah suatu sukubanyak dalam [ , [ , … , [l . Basis ini
kita sebut basis sukubanyak.
Teorema 2.2.4 (Noether, 1916) Ring invarian dari U, grup berhingga matriks kompleks × , mempunyai basis
sukubanyak yang memuat tak lebih dari m tak melebihi X = 6Y7ZU.
+X n buah invarian dengan derajat
Lebih lanjut basis ini diperoleh dengan merata-ratakan atas U semua suku
( oK ( oM ⋯ ( o] yang total derajatnya ∑ q! pq tak melebihi X. Bukti :
Misalkan U grup berhingga matriks kompleks × dan ( = ( , … , ( r suatu
vektor kolom. Aksi R` ∙ (, untuk setiap matriks R` ∈ U merupakan transformasi linier
11
s ` ∶ (q →
` (q
= F \q, ( ; w = 1, 2, … , .
1
!
Misalkan sebarang invarian di U adalah sukubanyak
[( , ( , … , ( = F )x ( xK ( xM ⋯ ( x] ; x
)x suatu bilangan kompleks (jumlah diperluas untuk semua Z = Z , Z , … , Z , sehingga tidak ada bagian yang nol). Karena [( = [( , ( , … , ( invarian maka tak berubah jika dirata-ratakan
atas grup U, yaitu
[( , ( , … , ( = = =
1 [%( , ( , … , ( & + ⋯ + [%( g , ( g , … , ( g & X
1 xK x] xK x] F )x a%( & ⋯ %( & + ⋯ + %( g & ⋯ %( g & d X x
1 F )x yx ; X x
Dengan demikian setiap invarian merupakan kombinasi linier dari (tak hingga banyaknya) invarian khusus yx = ∑`! %( ` & g
xK
⋯ %( ` &
x]
.
yx (tanpa faktor konstanta) merupakan koefisien dari xK xM ⋯ x] pada
sukubanyak g
x
zx = F% ( ` + ⋯ + ( ` & , `!
12
dimana Z = Z + Z + ⋯ + Z . Dengan kata lain, zx adalah jumlah dari pangkatpangkat ( + ⋯ + ( , … , ( g + ⋯ + ( g .
Sebarang zx dapat ditulis sebagai suatu sukubanyak dengan koefisien-
koefisien rasional dalam X jumlah pangkat z , … , zg . Maka sebarang yx untuk
Z = ∑ q! Zq > X dapat ditulis sebagai suatu sukubanyak dalam invarian khusus yx
dengan Z + Z + ⋯ + Z ≤ X (yang merupakan koefisien-koefisien z , … , zg ).
Kemudian kita dapat menuliskan sebarang invariant adalah suatu sukubanyak dalam bentuk yx dengan ∑ q! Zq ≤ X. Banyaknya yx yang seperti itu, yaitu
sejumlah Z , Z , … , Z yang memenuhi Zq ≥ 0 dan Z + Z + ⋯ + Z ≤ X yaitu
m
+X n. Akhirnya, derajat yx ≤ X dan yx diperoleh dengan merata-ratakan
( xK ( xM ⋯ ( x] atas grup.
■
Teorema 2.2.5 (Miller dkk, 1961) Banyaknya invarian berderajat 1 dari U yang bebas linier adalah g
1 \ = F =Y\)ZR` . X `!
Bukti : Misalkan ~ = g ∑`! R` . Lakukan perubahan variabel-variabel dari ( , ( , … , (
g
ke E , E , … , E , dimana s( , ( , … , ( r = E , E , … , E r , mengakibatkan ~
berubah ke ~’ = s~s G . Dapat kita pilih s sehingga ~’ diagonal. Jika ~ = ~ maka
~’ = ~’ dan entri diagonal dari ~’ adalah 0 atau 1.
13
Maka dengan suatu perubahan variabel, dapat kita asumsikan 1 ~= 0
⋱
1
0
⋱
0
;
0
~ matriks dengan Y entri diagonalnya bernilai 1, maka ~ ∙ Eq = Eq , jika 1 ≤ w ≤ Y dan ~ ∙ Eq = 0, jika Y + 1 ≤ w ≤ .
Sebarang invarian linier (berderajat 1) dari U ditentukan oleh ~, maka \ ≤ Y.
Dengan teorema 2.2.1, ~ ∙ Eq = g ∑`! R` ∙ Eq adalah suatu invarian dari U untuk
sebarang w, dan \ ≥ Y.
g
■
Deret Molien Jika \ menyatakan banyaknya invarian homogen berderajat 7 yang bebas linier maka Φk = ∑ !J \ disebut deret Molien.
Dari teorema 2.2.4, kita ketahui basis untuk invariant dari U selalu ada. Untuk
mengetahui bagaimana menemukannya, kita gunakan teorema Molien. Sebelum ke teorema Molien, perlu didefinisikan matriks terinduksi ke-7 dari R.
Matriks terinduksi ke-7 dari R` , dinotasikan R` , menyatakan bagaimana R` mentransformasikan
hasil
kali
dari
( , ( , … , ( G ( , …
14
(q
[]
sebanyak
7
kali,
yaitu
Contoh : Misalkan R = b
\ )
p c mentransformasikan 7
( ( ( (
Z
\ ( + 2\p( ( + p ( \)( + \7 + p)( ( + p7( ) ( + 2)7( ( + 7 (
Maka matriks terinduksi ke-2 nya adalah R[]
\ = \) )
2\p \7 + p) 2)7
p p7 . 7
Teorema 2.2.6 (Molien, 1897) Untuk U suatu grup hingga matriks bilangan kompleks, deret Moliennya Φk =
1 1 F |U| det V − R ∈k
Bukti : Perhatikan bahwa \ adalah banyaknya invariant berderajat 1 dari U [] = aR` = 1, … , Xd. Berdasarkan teorema 2.2.5, \ = g ∑`! =Y\)ZR` .
[]
g
Cukup dibuktikan =Y\)ZR` sama dengan koefisien di
[]
[]
1 1 = , detV − R` 1 − ⋯ 1 −
2
Dimana , … , adalah nilai-nilai eigen dari R` . Dengan perubahan variabel yang sesuai, dapat dipilih
15
R` = ⋮ 0
⋯ ⋱ ⋯
0 ⋮ ,
R`
[]
=
⋱
G
⋱
dan =Y\)ZR` adalah jumlah dari hasil kali , … , sebanyak 7 dan ini []
merupakan koefisien dari pada persamaan 2.
■
Struktur Ring Invarian Sebelum kita tuliskan ring invariant, kita definisikan operasi
atau jumlah
langsung. Sebagai contoh, ring invarian yang dibentuk grup U ditulis ℂ[(]k =
⊕ ~ berarti tiap invarian dapat dituliskan secara tunggal dalam bentuk Y + , dimana Y ∈ dan ∈ ~.
Secara umum, basis sukubanyak yang “bagus” untuk ℂ[(]k adalah himpunan
invarian homogen A[ , [ , … , [l B ≥ , dimana [ , [ , … , [ bebas aljabar dan berlaku hubungan ℂ[(]k = ℂ[[ , [ , … , [l ], jika = ; atau
ℂ[(]k = ℂ[[ , [ , … , [ ] ⨁[ ℂ[[ , [ , … , [ ]⨁ … ⨁[l ℂ[[ , [ , … , [ ], jika > .
16
