HAMMING CODE KODE INFORMASI DIGITAL STANDART TT& C SATELIT MIKRO PADA ORBIT LEO. Slamet Hadisaputro

Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006

HAMMING CODE KODE INFORMASI DIGITAL STANDART TT& C SATELIT MIKRO PADA ORBIT LEO Slamet Hadisaputro∗

ABSTRAK HAMMING CODE KODE INFORMASI DIGITAL STANDART TT&C SATELIT MIKRO PADA ORBIT LEO. Jenis kode ini, adalah salah satu dari jenis kode dalam spektrum kode digital yang banyak digunakan untuk penyaluran informasi digital untuk pelbagai keperluan diantaranya untuk proses penyampaian data TT&C satelit orbit rendah. Daerah lintasan setinggi s/d : 1000 Km diantariksa termasuk orbit LEO (Low Equatorial Orbit), termasuk di sini juga orbit polar dengan ketinggian yang serupa seperti TUBSAT daerah ketinggian yang banyak dilintasi satelit jenis amatir,maupun satelit–satelit mikro dalam pelbagai misi komunikasi, pengindraan lingkungan, cuaca atau pelbagai misi lainnya. Rencananya kode ini akan digunakan untuk satelit generasi kedua jenis mikrosat Lapan yang akan datang, jenis kode ini kini sedang direncanakan dan dipopulerkan di kalangan para perancang satelit. Penggunaan kode tersebut merupakan salah satu jenis kode digital yang popular dan bersifat linier, relatif, modern, mudah dibuat serta dari segi keamanan cukup andal serta cukup sederhana, kode Hamming ini dapat dikategorikan juga satu keluarga dengan jenis kode linier lainnya. Kata-kata kunci : kode digital bersifat linier, Hamming code, persamaan matematika biner dan penurunannya, beberapa aplikasi.

ABSTRACT HAMMING CODE MICRO SATELLITE TT & C STANDART DIGITAL INFORMATION CODE ON LEO ORBIT. The type of this code, is a code within the wide spectrum of the existing digital code used for many purposes of a wide variation, within the digital spectrum information one among this type is the TT&C (Telemetric Telecommand and Control ) of low orbital space satellite. The Low Orbital Satellite is a satellite which will fly on the sky around about 1000 Km height, is the same as the TUBSAT, including this type are the many other polar or equatorial orbital satellites, the height of this orbit for satellites is usually used for the microsatellite which has a mission i.e, the amateur satellite, communications, remote sensing,wheather satellite or other missions.This code is to be planned for using the second generation of micro satellite which will be developed for next micro satellite by the Lapan. This code now is being developed and is popularized among the micro satellite planner, modern system, this is also as a most popular digital code and has a linear property, a high capability,easy to be developed and has simple properties, this is also as member of the digital code families spectrum. Keywords: linear code digital, binary mathematic equation, some application

∗

Pusat Elektronika Dirgantara - LAPAN

445


PENDAHULUAN Terdapat banyak sinyal digital dibuat dalam bentuk kode, digunakan terutama untuk komunikasi digital diantaranya kode Hamming, digunakan terutama pada saluran TT&C satelit orbit LEO (Low Orbital Satelitte) yang merupakan koda bentuk standart. Pemakaian ini karena diperlukan kerahasiaan dari data digital ini, atau karena frekwensi gelombang radio yang sangat padat, atau karena aliran data digital yang sangat lemah sehingga perlu tenaga frekwensi yang cukup untuk bisa sampai kebumi. Karena disebabkan adanya pengaruh dari atmosfer dan antariksa setiap saat yang berubah-ubah dll, data tersebut jadi sangat lemah . Salah satu jenis kode digital yang diunggulkan tersebut adalah jenis kode ini, karena tidak memerlukan sirkuit elektronika yang sulit serta mudah membuatnya. Bila kode ini telah berhasil diproduksi , maka kode ini dengan mudah disembunyikan pada frekwensi pembawa (carrier frequency) sebelum dipancarkan ke bumi, demikian pula dengan deteksi kode tersebut tidaklah terlalu sulit.

Gambar: 1. Satelit mikro TUBSAT di-rekayasa oleh teknisi Pusat Elektronika Dirgantara-LAPAN berbobot 65 Kg. Bila pada sirkuit penerima telah menemukan kesalahan dengan mudah langsung dikoreksi dan lokasinya dapat ditentukan segera. Biasanya pada sirkuit penerima di stasiun bumi, penggunaan jenis kode ini dilengkapi dengan alat penerima yang dapat mengoreksi kesalahan dinamakan ACC (Automatic Check Control).

446


APLIKASI KODE MATEMATIKA Untuk memahami kode digital, terpaksa harus dimulai dari matematika biner dengan medan Galois: GF(2m), dilengkapi dengana cara penjabarannya dan penggunaannya dalam structure kode digital. Beberapa hal yang digunakan antaranya:

Matematika Biner Kode Digital Sebagai pengantar ke arah pengertian lebih luas tentang kode dalam komunikasi digital bersama ini diuraikan sekilas matematika biner dan menjadi dasar perhitungan dalam menganalisa teori kode. Sebenarnya matematika biner sudah dipakai secara luas dalam pembentukan pulsa digital, terdiri dari 0 dan 1 dengan pelbagai macam variasinya. Secara umum medan Galois disingkat :GF yang biasa-nya berisikan variasai banyaknya kemungkinan notasi yang terjadi sebanyak : m biasa dituliskan dengan: GF (2m), elemen pembentuk dari medan tersebut adalah 0 dan 1 yang dikalikan atau ditambahkan dengan variasi kombinasi dari faktor tertentu yang didefinisikan dengan : α, misalnya bentuk perkalian:

0.α j = α j .0 = 0 dan 1.α j = α j .1 = α j serta α iα j = α i + j

perkalian tersebut

dapat dituliskan dengan himpunan baru berupa deret perkalian sebagai berikut

F = (0,1, α , α 2 , α 3 ,.....α i + j )

(1)

Bila didefinisikan nilai :p(X) merupakan deret primitif (primitive polynoom) dengan derajat:m didalam medan Galois tersebut: GF(2) dengan anggapan bahwa : p (α ) = 0. ,dan bila nilai dari persamaan: p ( X ) dibagi dengan bilangan sembarang: X2n-1 = q (X).p(X)

(2)

didapat persamaan: X2n-1 +1= q (X) p(X)

(3)

atau bila : X ditukar dengan α menjadi:

α 2 n−1 + 1 = q(α ) p (α ) bila p (α ) = 0 diperoleh akhirnya bentuk deret himpunan dari: α :berbentuk 447

(4)


F * = (0,1, α , α 2 , α 3 .........., α 2 n −2 )

(5)

Misalkan nilai: m = 4 ,sedangkan nilai polynom primitif: p(X) = 1 + X + X4 pada medan galois GF(2) maka dapat dibuatkan tabel elemen:GF(4) yang dapat ditimbulkan (generated) oleh: p (X ) = 1 + X + X 4 sbb: Tabel 1. Elemen Gambaran besarnya tenaga: α 0 1 α1 α2 α3 α4 α5 α6 α7 α8 α9 α10 α11 α12 α13 α14

Bentuk deret (polynom) 0 1 -+ α+-+-+-+ α+-+-+-+ α 1+ α+-+-+ α+ α2+-+-+ α2+ α3 1+ α+-+ α3 1+-+ α2+-+ α+-+ α3 1+ α+ α2+-+ α+ α2+ α3 1+ α+ α2+ α3 1+-+ α2+ α3 1+-+-+ α3

Penggambaran (representasi bentuk biner) 0000 1000 0100 0010 0001 1100 0110 0011 1101 1010 0101 1110 0111 1111 1011 1001

tanda: (-) berarti kosong bukan nol (0). Untuk perkalian dua elemen: dijumlahkan;

i

+

j

α i dan α j dan

nilai

exponent-nya

dapat

nilai: α 15 = 1 dan nilai: ,untuk nilai “pembagian” ternyata

α 5 .α 7 = α 12 serta α 12 .α 7 = α 19 = α 4 4 merupakan selisih,misalkan: α = α 4α 3 = α 7 α 12

demikian

pula

dengan

penjumlahan, maka dapat digunakan tabel diatas sebagai jawabnya. Misalnya pada persamaan:

α 5 + α 7 = (α + α 2 ) + (1 + α + α 3 ) = 1 + α 2 + α 3 = α 13 448

(6)


1 + α 2 + α 10 = 1 + (α + α 2 ) + (1 + α + α 2 ) = 0

(7)

Beberapa Istilah Kode Digital Rumus rumus diatas adalah merupakan rumus matematika kode yang biasa dilakukan pada istilah kode biner tanpa besaran vektor, sehingga aplikasi dalam kode praktis hanya sebagai perhitungan dan dipakai terutama dalam perencanaan, atau implementasi selanjutnya, lebih tepatnya hal-hal diatas hanya dapat disebutkan sebagai bentuk softwarenya kode jadi tanpa implementasi sebenarnya. Tetapi sebaliknya bentuk dari realisasinya menggunakan aplikasi turunan matematika tersebut yang direalisasikan dalam beberapa bentuk sirkuit-sirkuit elektronika yang digabungkan jadi satu, hasilnya merupakan implementasi dari hasil rancangan semula dari bentuk matematika yang diturunkan tadi. Untuk memahami istilah-istilah yang berlaku dalam kode, terutama dalam menemukan software suatu sistem kode, diperlukan beberapa istilah. Istilah ini berlaku secara internasional yang dipakai dalam pembentukan kode.

Beberapa Rumus Kode Untuk Aplikasi Rumus yang penting untuk diketahui dalam pembentukan kode ternyata berbeda-beda antara satu kode dengan kode lainnya, sehingga rumus setiap kode tidaklah “unique.”, rumus dari satu kode hanya berlaku untuk kode itu sendiri dan tidak bisa digunakan untuk kode-kode digital yang lain. Pemakaian kode sudah demikian luasnya sehingga memerlukan perbedaan antara kode yang pertama dengan kode berikutnya. Tergantung dari penggunaan kode tersebut dimana dipakainya, lokasinya dan sifat tingkat kerahasiaannya, penggunaan di terrestrial, di daratan bumi, atau permukaan laut tentu berbeda dengan pemakaian pada satelit ke bumi dan sebaliknya. Rumus tersebut biasanya berisikan istilah tertentu yang wajib dimengerti oleh perancang kode, pada penerima kode nanti hanya akan menerjemahkan kode yang dikirim sesuai aslinya. Secara umum sebelum kode tersebut dikirimkan, kode tersebut haruslah dilindungi dengan “menyelimutinya”, biasanya dilindungi dengan frekwensi pembawa dengan kombinasi dari modulasi F.M. Rumus kode ini sangat penting untuk diketahui para perancang kode digital untuk menghasilkan jenis kode yang dimaksudkan. Beberapa istilah dimasukkan disini sebagai pengantar pengetahuan ke-lingkungan kode.

449


Generator Fungsi Istilah dari Generator Fungsi sebenarnya berfungsi sebagai pembangkit tenaga mula-mula, Generator ini setelah dihubungkan dengan sistem pembuat kode dapat menjadikan bentuk kode yang diinginkan. Generator kode dapat dituliskan secara matrik atau secara linier ( matrik berorde tunggal, hanya ada 1. baris saja ), bentuk liner tersebut biasanya digunakan setelah bentuk persamaan matematika dari generator fungsi menjadi berbentuk vektor tenaga. Vektor tenaga ini berupa vektor daya yang siap untuk digunakan kemudian dipancarkan keluar, biasanya bentuk vektor yang dimaksud berupa tenaga medan elektromagnetik yang sudah siap digunakan dan siap untuk dipancarkan. Istilah “generator fungsi” tersebut biasanya digunakan pada perancangan kode, semua bentuk kode-kode digital yang sudah ditemukkan biasanya dengan menggunakan ukuran dari banyak-nya “baris” dan “kolom” dengan dimensi tertentu, misalnya sebanyak : n baris dan: k kolom biasa ditulis dengan kode (n,k). Kode tersebut biasanya berisikan : n buah, “baris” dan:k buah “kolom”. Rumus generator fungsi lebih luas, biasanya berisikan gabungan matrik, matrik : P (pxn) dan matrik Identity : (k x k) misalnya:

 g 1   p 0, 0 g   p  2   1,0  g 3   p 2, 0    G= . = .  .   .     .   . g   p  k −1   k −1, 0 P: matrik

. . . . . .

p0, n− k −1 p1,n −k −1 p 2,n −k −1 . . .

p k −1,1 . . .

p k −1,n − k −1

p0,1 p1,1 p 2,1 . . .

. . . . . .

. . . . . .

! ! ! ! ! !

1 0 0 . . . 0 0 1 0 0 . . 0 0 0 1 0 . . 0  . . 0 1 . . . . . . 0 . . .  . . . 0 . . . ! 0 0 0 0 . . 1

(8)

k x k identity matrik

Bila IK: merupakan matrik berdimensi : k x k merupakan Identity matrix maka terjadi hubungan;

G = [P.I K ]

(9)

Secara umum bentuknya setiap kode sembarang biasanya berupa format yang berbentuk:

450


Cheking part & Redundance

Message Part

Gambar 2. Bentuk umum sembarang kode digital.

Vektor Kode Sinyal “Pemancar & Penerima”.,dan “Vector Error”(kesalahan) Kode yang dipancarkan, adalah kode yang asli, keluar dari rangkaian pembuat kode dan siap untuk dipancarkan dengan besaran vector. Besaran vektor disini adalah vektor elektromagnetika yang dihitung dalam “medan Galois”: GF(2m) tadi, biasa disimbulkan dengan: v. Sedangkan besaran vektor yang diterima, adalah besaran vektor dari: v yang berhasil diterima setelah sinyal pembawanya dideteksi. Karena sinyal ini berada di bumi, maka dia tidak dapat mengetahui asalnya dari mana, tetapi dengan alat yang dipasangkan pada penerima FEC ( Forward Error Control ) atau ARQ (Automatic Repeat Request) dapat ditentukan bahwa sinyal itu tertuju padanya tetapi mengandung kesalahan-kesalahan (error signal). sinyal yang diterima biasa disingkat dengan: r. Setiap kode dari kalimat yang dikirimkan ke arah penerima, sinyal dari kode ini akan dapat diterima tidak selalu ideal. Hal ini mengingat banyaknya kemungkinan terjadinya perubahan dari sinyal yang asli. Selisih vektor sinyal yang asli dan sinyal yang diterima disebut error sinyal. Vektor Error yang diterima ini dapat di-deteksi , besarnya : e = r + v demikian pula nilai code word yang diterima menjadi: r = v + e i

Parity Check Parity Check matrik, dapat berupa besaran vektor atau matrik yang mempunyai hubungan orthogonal dengan matrik : G. matriks tersebut biasa disingkat dengan: H. Untuk setiap matrix G dengan dimensi derajat : k x n, dengan harga:k adalah baris yang bebas, akan terdapat sebanyak: ( n – k ) x n elemen matrik: H dengan baris yang “bergantung liner” sehingga nilai vektor dalam ruang baris dari elemen G selalu terletak orthogonal terhadap baris elemen: H dan demikian pula dengan nilai vektornya, vektor H akan selalu orthogonal terhadap: G. Bila v adalah bentuk code word (kode-kalimat) dari suatu kode yang dibangkitkan oleh matrix: G. terjadi hanya dan jika hanya berlaku hubungan; v.HT = 0. Matrix :H inilah yang dinamakan parity chek matrix dari suatu kode. Bila generator kode: G tersusun secara sistematis seperti pada persamaan diatas maka nilai parity check matrix akan berbentuk: 451


1  0 0  H = I .n−k.PT =  . .  . 0 

[

]

0 1 0 . . . 0

0 0 1 . . . 0

.. .. .. .. .. .. ..

.. .. .. .. .. .. ..

.0 p0,0 .0 p0,1 .0 p0,2 . . . . . . 1 p0,n−k −1

p1,0 p1,1 p1,2 . . . p1,n−k −1

. . . . . . .

. . . . . . .

 . pk −1,0  . pk −1,1   . pk −1,2  . .  (10)  . .  . .  . p k −1,n−k −1 

dimana matrix:PT adalah matrix transpose dari: P sehingga suatu code linear (n,k) akan ditentukan bentuknya oleh parity chek tersebut. Sebagai contoh suatu kode (7,3) , dengan nilai parity-check: H, berbentuk matrik:

1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 , code ini akan terdiri matrik G dengan dimensi:n x k 0 0 1 0 1 1 1 dengan nilai-nya “hanya dan jika hanya” berlaku hubungan : v.H T = 0 . Nilai pada generator fungsi dapat dihitung. Karena matrik parity chek ini terdapat pada bagian penerima data (receiver) maka implementasinya berupa kombinasi dari shift register (flip-flop) adder dan perkalian sinyal “.

Syndrome Kode Bila dianggap terdapat kode (n,k) berupa kode liner dengan generator matrik: G dan parity chek matrik: H, dan bila pula dapat dimisalkan besarnya vektor yang berhasil dipancarkan. pada daerah yang banyak noisenya

v = (v0 , v1, v2 ,.......vn−1 ) dan

kode yang berhasil diterima adalah: r = (r0 , r1 , r2 ,....rn −1 ) , maka besarnya vektor kesalahan disini adalah sebesar: e = r + v . Oleh karena pada sistim penerima tidak diketahui nilai : v atau : e, sehingga pada penerima: r dapat menentukan terjadinya vektor kesalahan tersebut setelah alat deteksi kesalahan bernama FEC atau ARQ memberi tanda-tanda terjadinya adanya kesalahan tersebut. Sinyal kesalahan itu dapat diperbaiki dengan mengirim ulang atau langsung diperbaiki setempat. Besarnya syndrome: ”s “ pada receiver tersebut dapat dihitung dengan rumus matematika biner:

452


s = r .H T

(11)

HT matriks transpose dari : H , s = “vector syndrome” yang diterima. Bila nilai s ≠ 0 maka pada penerima:r bukanlah suatu code yang dimaksud, ada terdapat error pasa transimisi data., sedangkan bila s = r.H T = 0 maka bentuk dari code word akan sama dengan bentuk asli sebesar: 2 k − 1 , kode dapat dianggap serupa dengan bentuk aslinya yang merupakan kode aslinya yang dikirimkan. Syndrome adalah besaran vektor yang dapat mengetahui banyaknya kesalahan dalam satu kode yang asli.

Jarak (distance) Kode Vektor Linier. ` Pada kode liner Hamming dapat dicari vektor jarak antar dua kode yang berdekatan, demikian pula vektor beban kode tersebut. Jarak antara 2 kode Hamming antara kode pertama dengan persamaan vektor : V = (1001011) dan kode vektor kedua W = (0100011) adalah fungsi metric yang memenuhi ketidaksamaan segitiga dari kedua vektor data kode tersebut. Jumlah perbedaan yang dimaksud terletak pada posisi vektor yang ke-nol, ke-satu,dan ketiga, sehingga jarak kode adalah: ada 3 (tanpa satuan).. Secara umum dapat ditulis bahwa besarnya vector distance disini adalah mengikuti rumus misalkan : V dan W dan X mrupakan kombinasinya:maka

d (v, w) + d ( w, x) ≥ d (v, x)

(12)

Demikian pula untuk dua macam kode V dan W jaraknya menjadi

d (V , W ) = W (V + W )

(13)

ISI KODE HAMMING Kode ini merupakan kode yang banyak digunakan pada kode liner yang dapat dilengkapi dengan koreksi kesalahan, ada terdapat bermacam variasi dengan penggunaan deteksi kesalahan pada sistim komunikasi digital. Hamming code dapat dibentuk dengan ketentuan parameternya sbb: n = 2m – 1

453

(14)


k = 2m – m – 1

(15)

m= n-k

(16)

dengan n = panjang kode k = Banyaknya simbol informasi m = Banyaknya parity check symbol Kemampuan untuk koreksi error t = 1 bila jarak dmin = 3 Dalam bentuk yang sistematik, pengaturan dari parity chek berbentuk:

H = [I m .Q ]

(17)

Dimana Im adalah suatu matriks Identity: m x m dan sub-matrik:Q terdiri dari : 2m – m - 1 buah kolom, dengan: m merupakan bilangan bulat, misalnya untuk nilai m = 3 maka parity chek dari Hamming code terdiri dari panjang: 7, dan dapat berbentuk matrik sbb:

1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1

(18)

ini merupakan kode liner dengan ukuran 7x3 Bentuk kolom dari: Q dapat diatur tanpa mengabaikan sifat-sifat distribusi jarak dan beban dari kode. Dalam bentuk yang sistematis generator matrik tersebut:

[

G = Q.T .I 2m −m −1

]

(19)

dengan: QT adalah matrix transpose dari Q dan I2m- m - 1 adalah suatu matrix identity dengan dimensi: ( 2m – m – 1 ) x ( 2m – m – 1 ) Pada suatu saluran komunikasi yang bersifat BSC ( Binary Symatric Channel ) dengan pelbagai bentuk kemungkinan, Hamming code ini dapat digunakan untuk mendeteksi aliran sinyal-sinyal dan dapat menganalisa kesalahannya..Saluran BSC dapat dianggap satu satelit pemancar dengan satu atau beberapa stasiun bumi dengan aliran data digital tersebut. Dalam perhitungan selanjutnya dari BSC dapat dilakukan pada kode liner misalnya kode Hamming ini. Bila suatu kode liner ( n , k ) hanya

454


untuk mendeteksi kesalahan data sepanjang BSC, maka nilai “probability” dari “kesalahan yang tidak bisa ter-deteksi” sesuai dengan rumus empiris : n

Pu ( E ) = ∑ Ai p i (1 − p )

n −1

(20)

i =1

dengan p: adalah transision probability, nilai minimum distance d min ,dan nilai: Ai sampai ke nilai : Admin -1 adalah dianggap semua nol, penggunaan dari code ini bila beban distribusi (weight distribution) dari code tersebut diketahui. Disini dibedakan hubungan antara beban distribusi satu kode dengan dual (dua) kode liner, hubungan ini lebih mudah untuk menghitung distribusi untuk dual kode. Pada suatu dual kode sembarang C yang liner derajat (n,k) dengan menganggp kode pertama: (A1,A2,A3,……An) adalah beban dari kode liner (n , k) dual kode C dan kode: Cd dengan weight :(B1,B2,B3…….Bn) beban yang lainnya., keduanya mempunyai nilai distribusi weight polynomial A(z) = A 0 + A1z1 + A2.z2 + A3.z 3 +…………+ An zn

(21)

B(z) = B0 + B1z1 + B2z2 + B3z3 + ………………+ Bnzn

(22)

A(z) dan B(z) mempunyai hubungan relasi indentity sbb:

A( z ) = 2 −

(n−k )

(1 + z )n B 1 − z 

(23)

1+ z 

Identity ini dikenal dengan identity dari Mac William, dan nilai polynoom A(z) dan B(z) dikenal dengan beban enumerator (enumerator weight) dari kode liner (n,k,) kode liner C dan dual kode; Cd. .Dengan menggunakan identity dari Mac Willam, dapat dihitung dari probability error suatu (n,k) kode liner dengan dual weight distribution. Bila diambil bentuk ekpresi rumus n

P( E ) = ∑ A.i p i (1 − p ) i =1

n−k

= (1 − p )

n

n

∑ i =1

 p   Ai . 1− p 

(24)

Dengan melakukan substitusi “ z = p / (1 - p) pada A(z) dan Ao = 1 didapat l

persamaan

455

identitas

n  p   p   − 1 = ∑ Ai   , : A i =1 1− p  1− p 

dan

dengan


mengkombinasikan rumus atas didapat Probability dari kesalahan yang tidak dapat terdeteksi sebesar:

 P0 ( E ) = (1 − p ) n  A 

 p     − 1 1− p  

(25)

Dengan menggunakan identitas dari Mac William diperoleh

P0 ( E ) = 2 − ( n− k ).B (1 − 2 p ) − 91 − p ) n

(26)

dengan n

B (1 − 2 p ) = ∑ B (1 − p ) l

(27)

i =0

Misalkan bila kode liner (7,4) dengan tabelnya sbb: Liner blok kode tersebut dengan: k = 4 dan n = 7 Tabel 2. Kode Linier

Message (0 0 0 0) (1 0 0 0) (0 1 0 0) (1 1 0 0) (0 0 1 0) (1 0 1 0) (1 1 1 0) (1 1 1 0) (0 0 0 1) (1 0 0 1) (0 1 0 1) (1 1 0 1) (0 0 1 1) (1 0 1 1) (0 1 1 1) (1 1 1 1)

456

Code words (0 0 0 0 0 0 0 ) (1 1 0 1 0 0 0) (0 1 1 0 1 0 0) (1 0 1 1 1 0 0) (1 1 1 0 0 1 0) (0 0 1 1 0 1 0) (1 1 0 0 0 1 0) (0 1 0 1 0 0 1) (1 0 1 1 0 0 1) (0 1 1 1 0 0 1) (1 1 0 0 1 0 1) (0 0 0 1 1 0 1) (0 1 0 0 0 1 1) (1 0 0 1 0 1 1) (0 0 1 0 1 1 1) (1 1 1 1 1 1 1)


Gambar 3. BSC ( Binary Simetric Cannel ) pulsa digital dengan pelbagai macam kemungkinan bentuk kanal dan kemungkinan arah transmisi. Dual kode dari kode ini di timbulkan oleh generator dengan matrik parity chek

1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 dengan membuat kombinasi linier dari baris 0 0 1 0 1 1 1

matrik (row of matrix) didapat delapan buah dual kode liner (7,4) Tabel 3. Dual Kode Linier (0 0 0 0 0 0 0) (1 0 0 1 0 1 1) (0 1 0 1 1 1 0) (0 0 1 0 1 1 1)

(1 1 0 0 1 0 1 ) (1 0 1 1 1 0 0) (0 1 1 1 0 0 1) (1 1 1 0 0 1 0)

Sehingga weight enumerator dari dual kode adalah

B( z ) = 1 + 7 z k

(28)

Dengan menggunakan persamaan diatas dapat dicari kemungkinan tidak terdeteksi dari kesalahan (7,4) kode linier dari Hamming sesuai dengan tabel diatas jadi:

[

]

P0 ( E ) = 2 −3 1 + 7(1 − 2 p ) − (1 − p )

457

4

7

(29)


Suatu Hamming code bisa mempunyai “single-error correcting code” atau’ double error detecting”, bila suatu Hamming code berupa single error, maka bila ada single error yang muncul selama deteksi transmissi sinyal, maka nilai resultante syndrome adalah “bukan nol (non-zero)dan terdiri dari bilangan bulat (odd number) dari 1, bila double error yang terjadi,nilai syndrome juga merupakan nonzero tetapi biasanya angka ganjil (even number) dari 1 Bila Hamming code digunakan untuk deteksi kesalahan pada kanal BSC maka besarnya Probability :Pu(E) dapat dihitung dari rumus kombinasi dari rumus Probability dari kesalahan yang tidak dapat diteksi, biasa disebut dari Probability dari Mac William sebesar:

 Pu ( E ) = (1 − p ).  A 

 p     − 1 1− p  

(30)

dan A dihitung dengan deret polynom:

A( z ) =

[

(

1 (1 + z )n + n(1 − z ) 1 − z 2 n +1

)

( n −1) / 2

]

(31)

dengan Ai merupakan koefisien dari:zi , akhirya diperoleh rumus probabilitas untuk kode yang dapat dideteksi dari suatu kode Hamming tersebut:

[

(

)

P0 ( E ) = 2 − m 1 + 2 m − 1 (1 − 2 p )

2 m −1

]− (1 − p)

2 m −1

(32)

dimana P0(E) untuk Hamming Code adalah nilai probability yang memenuhi daerah

batas atas: 2 − (n − k ) = 2 − m untuk

p ≤ 0,5 misal − nya

[P ( E ).2 ] −m

0

SIRKUIT KODE HAMMING Untuk dapat membayangkan bentuk implementasi dari bentuk hardware rangkaian kode Hamming dapat diperjelas dengan contoh berikut. Bila dianggap suatu linier kode dari bentuk Hamming (7,3) mempunyai matrik parity check sebesar

1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1

458


kode tersebut mempunyai : 2 3 = 8 buah co-set sehingga terdapat delapan buah error patern yang mungkin untuk dikoreksi termasuk semua vektor nolnya, dan kode ini mempunyai jarak: 3 yang mampu mengkoreksi kesalahan vector error-nya berbobot: 1 dan nol. Bentuk tabel yang mungkin dapat dikoreksi disebut tabel koreksi dari kode liner (7,4) ini beserta syndrome-nya adalah sbb: Tabel 4. Koreksi Kode Linier Syndrome (1 0 0) (0 1 0) (0 0 1) (1 1 0) (0 1 1) (1 1 1) (1 0 1)

Coset Leader (1 0 0 0 0 0 0) (0 1 0 0 0 0 0) (0 0 1 0 0 0 0) (0 0 0 1 0 0 0) (0 0 0 0 1 0 0) (0 0 0 0 0 1 0) (0 0 0 0 0 0 1)

Misalkan code word vector yang dikirimkan: v = (1 0 0 1 0 1 1) dan sinyal yang diterima sebesar r = (1 0 0 1 1 1 1) , untuk dapat mendeteksi sinyal:r kita harus menentukan besarnya syndrome

1 0  0  Sebagai berikut: s = (1001111) 1 0  1 1 

0 1 0 1 1 1 0

0 0 1  0 = ( 0 1 1 ) 1  1 1

Diperoleh besarnya sindrome menurut teori sebesar ( 0 1 1) adalah syndrome yang terjadi pada nilai co-set leader pada posisi: e = (0 0 0 0 1 0 0 ), nilai ini dapat dianggap sebagai error patern disebabkan karena kanal komunikasi dengan hasil decode nya men-jadi:r. Nilai r tersebut kemudian di decode kembali pada pengiriman ulang: : v* = r + e= (1 0 0 1 1 1 1 ) + ( 0 0 0 0 1 0 0 ) = (1 0 0 1 0 1 1 ) v* sebenarnya kode actual vector yang ditransmisikan. Sekarang bila ditentukan kode yang dipancar ulang adalah: v = ( 0 0 0 0 0 0 0 ) artinya tidak ada message yang dikirim kembali hanya vektor kosong saja, dan

459


penerima (receiver) menerima kode r = ( 1 0 0 0 1 0 0 ) maka dapat diketahui terdapat 2 (dua) buah error yang terjadi selama pengiriman tersebut, besarnya error tersebut dapat di decode dan dihitung dengan melalui sindrome: s yang besarnya:

s = r.H T = (1 1 1) Pada tabel decoding pada nilai syndrome: s = ( 1 1 1 ) didapat e = (0 0 0 0 0 1) Karena sensor-sensor telemetri satelit mempunyai frekwensi relatif rendah maka kode yang digunakan sesuai dengan kebutuhannya tidak perlu terlalu besar. Kode vektor yang sebenarnya pada contoh diatas dapat dihitung lagi dalam:

Gambar 4. Sirkuit Decode Pada Penerima Code Word ( 7,4 )

v* = r + e = (1000100) + (0000010) = (1 0 0 0 1 1 0) vektor: v* inilah sebenarnya yang dikirimkan, realisasinya dapat di-implementasi pada gambar diatas. Disebabkan alasan terutama menyangkut kesehatan dari satelit, maka sebisa mungkin penerimaan kode tidak dapat di-deteksi oleh orang lain selain pemiliksatelit tersebut.

460


APLIKASI KODE HAMMING Sinyal-sinyal dari sensor telemetri biasanya mempunyai frekwensi yang rendah tersebut kemudian di multiplexing menjadi seri dari tadinya semula berbentuk paralel, biasanya sensor telemetri satelit yang merupakan pengotrolan dari kesehatan satelit tidaklah yang tunggal (satu) tetapi ada beberapa. Pada satelit mikro TUBSAT digunakan sebanyak :12 kanal telemtri satelit secara paralel, kemudian setelah sinyal analog dari sensor dimultiplexing kemudian dijadikan digital lalu dirubah kedalam bentuk kode Hamming digital sebelum dimodulasi dengan frekwensi pembawa.Dipesawat penerima sinyal, sebaliknya kode ini di-rekontruksikan kembali. Bila dalam penerimaan terjadi kesalahan, kesalahan data ini dikoreksi sehingga dapat berbentuk aslinya kembali. Alat koreksi tersebut dinamakan ACK(Automatic Check Control ) yang dapat mengoreksi kesalahan tersebut, koreksi kesalahan tersebut memerlukan waktu beberapa lama.

Gambar 5. Frame TT&C pada satelit mikro, penambahan digit kode dilakukan searah dengan sumbu waktu. Koreksi siyal yang salah (error signals) terjadi karena adanya permohonan atau request dari ACK sebagai receiver di bumi kearah satelit diatas sebagai pemancar aslinya. Jenis kode vektor yang berhasil dideteksi kesalahannya lalu dikembalikan kealamat aslinya lalu diperbaiki. Setelah proses ini berakhir, maka dipancarkan kembali ke arah stasion bumi penerima. Untuk melaksanakannya akan dibutuhkan waktu menunggu yang cukup lama mengingat letak edar satelit yang berjauhan dari station bumi. Peralatan ACK jenis ini biasanya digunakan untuk keperluan pengiriman data dan gambar yang tidak begitu penting dan tidak segera. Untuk pemakaian waktu yang segera biasanya pada stasiun bumi komunikasi digunakan alat FEC yang dapat langsung mengkoreksi kesalahan data. Cara ini biasanya digunakan karena pada

461


pengiriman data suara tidak dibutuhkan kualitas suara yang tepat, yang penting keseluruhan suara yang dikirimkan dapat dimengerti maksudnya. Aplikasi pada BATAN dapat digunakan misalnya memasangkan sirkuit kode Hamming untuk system Radio Telemetri Monitor pada tempat-tempat berbahaya direaktor nuklir atau pusat pusat PLTN dengan daya besar.

KESIMPULAN Dengan kemajuan teknologi digital akan semakin banyak hal-hal yang dapat ditawarkan kepada para pemakai dari sistim komunikasi digital. Bentuk asli dari kode tersebut adalah asli digital dengan level : tegangan sampai dengan: 5 volt DC (arus searah) yang dibuat kode. Kode tersebut lalu dimodulasikan dengan pelbagai variasi dan jenis-jenis modulasi yang dipilih, biasanya FM-FM atau FM-QPSK atau variasi yang lain. Pada pesawat penerima akan didemodulasikan dengan cara yang sebaliknya, sehingga sinyal yang asli dapat terdeteksi. Keunggulan jenis kode ini adalah sulitnya untuk di diteksi oleh penerima lain yang menggunakan peralatan penerima yang berlainan. Hal ini memungkinkan kode tersebut akan sulit di diteksi jika tidak diketahui jenisnya kode. Rumus yang digunakan pada setiap kode adalah bersifat tidak unique sehingga setiap kode mempunyai ketentuan tersendiri dalam mendeteksi kode. Atas dasar hal ini maka sifat kerahiaan kode akan dapat terjamin sehingga sistim pemencaran code tidak akan terdeteksi oleh orang yang tidak menguasai terhadap sistim ini sehingga kerahasiaan akan cukup terjamin.

DAFTAR PUSTAKA 1. E.R.BERLEKAMP., Algebraic Coding Theory, Mc Graw Hill, New-York, 1986. 2. R.W.HAMMING, Error Detecting and Error Correcting Syst.Tech.J,29, New York, USA, pp 147-160.

Codes,

Bell

3. S.K.LEUNG-YAN CHEONG AND M.E.HELLMAN, Concerning a Bound on Undetected Error Probability, IEEE Trans Inf.Theory,IT-22 March, (1978) 235-237

462


4. S.K.LEUNG-YAN-CHEONG,E.R.BARNES and D.U.FRIEDMAN, On Some Properties of The Undetected Error Probability Of Linear Code, I.E.E.E. Trans Inf Theory, IT-25, Jan, (1976)110-112. 5. W.W.PETERSON AND E.J.WELDON..J.R, Error-Correcting Codes,2nd ed.MIT Press, Cambridge, Mass, 1972. 6. FJ.MAC WILLIAMS, The Theory Of Error Correcting Codes, North Holland, Amsterdam, 1977. 7. SHU LIN and D.J.COSTELLO JR, Error Control Coding, Fundamental and Applications”,Prentice Hall, Ing, Englewood Cliffs, New Jersey, USA,1983. 8. S.KLEUNG YAN-CHEONG and M.E HELLMAN, Concerning a Bound On Undetected Error Probability, IEEE Trans Inf Theory, IT-22, March, (1978) 235-237

DISKUSI SULASNO Berapa banyak bit yang bisa diperbaiki jika terdapat kesalahan dengan hamming code SLAMET HADISAPUTRO Bisa dihitung menurut teori Probabilitas dari Mac William (untuk bit yang tidak

bisa dikoreksi) yang bisa dikoreksi tentunya, Prob = 1-U.DB(Undetected Bit) MASKUR Apakah Hamming Code dalam aplikasinya dapat memantau kebocoran radiasi di suatu reaktor nuklir ? SLAMET HADISAPUTRO Sudah diaplikasikan pada TUBSAT generasi I, mungkin bisa kalau jumlah fluks yang bocor dapat dideteksi. 463


DAFTAR RIWAYAT HIDUP

1. Nama

: Slamet Hadisaputro

2. Tempat/Tanggal Lahir

: Pontianak, 2 Desember 1960

3. Instansi

: Pusat Elektronik Dirgantara -LAPAN

4. Pekerjaan / Jabatan

: Staf Peneliti

5. Riwayat Pendidikan

: (setelah SMA sampai sekarang)

•

Fakultas Teknologi Industri Univ. Trisakti Jurusan Elektro Komunikasi

•

Pasca Sarjana Jurusan Informasi Teknik ITB

6. Pengalaman Kerja

464

:

•

LAPAN-Jakarta

•

Staf Peneliti, Tenaga Struktural pada perancangan Satelit Mikro

HAMMING CODE KODE INFORMASI DIGITAL STANDART TT& C SATELIT MIKRO PADA ORBIT LEO. Slamet Hadisaputro

Recommend Documents