KINERJA SISTEM PENGKODEAN DENGAN MENGGUNAKAN KODE INNER DAN KODE OUTER Sihar Parlinggoman Panjaitan
Staf Pengajar Departemen Teknik Elektro, Fakultas Teknik USU Abstrak: Kesalahan merupakan masalah pada sistem komunikasi. Untuk mengatasi masalah ini digunakan sistem pengkodean untuk dapat mengkoreksi kesalahan. Penelitian ini membuat model sistem kode inner dan outer. Tolok ukuran kinerja sistem adalah Bit Error Rate dari kode inner dan outer kode Hamming dan kode Reed Salomon. Kinerja sistem pengkodean dengan menggunakan kode inner dan outer tersebut dibandingkan dengan kinerja sistem pengkodean dengan menggunakan kode tunggal. Kata kunci: Kode Inner dan Outer, Bit Error Rate, Kode Hamming, Kode Reed Salomon, Pengkodean dan Pendekodean, Koding Gain Abstract:The error represents a problem for the communications systems. In order to overcome this problem, systems coding are used to correct this error. This research makes model of the inner and outer code. The performance of the system is measured by Bit Error Rate By inner and outer Hamming code and Reed Salomon. The performance of coding system by using code is compared with the performace of coding system by using code. Keywords: Inner and Outer Code, Bit Error Rate; Hamming Code, Reed Salomon Code, Coding and Decoding, Gain Coding I. PENDAHULUAN Beberapa studi mengatakan, jika menggunakan kode inner dan outer, di mana yang satu sebagai kode inner dan yang lainnya sebagai kode outer, maka dapat diperoleh kemampuan yang sangat andal, jika hanya menggunakan satu jenis pengkodean saja (Christian Thommesen, 1987). Pola penggabungan kode yang dikombinasikan sebagai kode inner dan kode outer sangat luas pemakaiannya pada sistem komunikasi digital, di mana tujuannya memperoleh kemampuan yang sangat andal guna mengoreksi kesalahan (Fazel K & Salembier P., 1989). Kinerja dari suatu sistem pengkodean dengan menggunakan kode inner dan outer diukur dari besarnya kemampuan koreksi kesalahan dari kode tersebut. Di samping itu, tolok ukur kinerja dari suatu sistem pengkodean adalah Bit Error Rate, yaitu banyaknya bit yang salah dibagi dengan banyaknya bit yang dikirimkan dalam jumlah yang besar. Bit Error Rate dari sistem pengkodean dengan menggunakan kode inner dan outer tidak dapat dihitung secara teoretis. Oleh karena itu untuk memperoleh Bit Error Rate dilakukan simulasi. II. MODEL SISTEM Sistem yang diteliti adalah kinerja dari sistem kode inner dan outer dengan menggunakan metode simulasi. Oleh karena itu diperlukan model sistem. Cakupan pemodelan sistem terdiri dari 4 bagian yaitu: 1. Bagian pertama adalah pemodelan sumber data yang berupa bilangan binari 0 dan 1.
2.
Bagian kedua adalah pemodelan pengkodean dari data yang hendak ditransmisikan. 3. Bagian ketiga adalah pemodelan dari medium transmisi yang meliputi pembangkitan sampel noise Gaussian dan pembangkitan salah bit. 4. Bagian keempat adalah pemodelan pengkodean dari stream bit yang diterima di sistem penerima. Blok diagram model sistem diperlihatkan oleh gambar 1. Model sistem sebagaimana diperlihatkan oleh gambar 1 diimplementasikan dalam bentuk program simulasi pada komputer yang terdiri dari program pembangkitan binari 0 dan 1, proses pengkodean, pembangkitan noise Gaussian dan pembangkitan salah bit serta proses pendekodean.
Sumber Data Proses Medium Proses Gambar 1. Blok Diagram Model Sistem II 1 Algoritma Pembangkitan Binari 0 dan 1 Pada penelitian ini sumber diasumsikan sebagai sumber binari yang mempunyai peluang munculnya bit 1 dan peluang munculnya bit 0 adalah sama. Oleh karena itu dipakai satu
21
Jurnal Sistem Teknik Industri Volume 7, No. 4 Oktober 2006
pembangkit yang dapat membangkitkan bit 0 dan bit 1 dengan peluang yang sama. Pembangkitan bilangan acak yang terdistribusi antara 0 dan 1 dimulai dari pembangkitan bilangan acak ke-i yaitu dari 1 sampai dengan bilangan acak ke-n di mana n, sejumlah perkalian antara panjang data dari kode. Bila jumlah bilangan acak yang dibangkitkan belum mencapai n, maka dibangkitkan bilangan acak berikutnya. Bila bilangan acak dibangkitkan lebih besar dari n maka proses pembangkitan bilangan acak berhenti. Bilangan acak yang telah dibangkitkan (u) dibandingkan dengan 0,5. Bila bilangan acak yang dibangkitkan lebih kecil atau sama dengan 0,5 dibangkitkan bit 0 dan lebih besar dari 0.5 dibangkitkan bit 1. 11.2 Algoritma Pembentukan Kode Hamming dan Kode Reed Salomon Bit stream dari sumber data yang masuk ke enkoder dikodekan dengan menggunakan suatu generator. Oleh karena itu dalam proses pengkodean diperlukan suatu generator, baik generator matriks, generator polinomial maupun generator sekuens. Pada penelitian ini kode-kode yang dipergunakan adalah kode Hamming (7,4) dan kode BCH (127,57) sebagai pembanding yang sifatnya sistematik. Kode Hamming. Dapat diperoleh dari hasil perkalian antara bit stream dengan generator matriks kode Hamming Generator matriks dari kode Hamming (Man Young Rhee, 1989):
tegangan lebih kecil dari harga treshold-nya (0 volt). Tegangan akan lebih kecil dari 0 volt jika noise negatif dengan tegangan lebih kecil dari -V. Apabila bit 0 dikirim maka error akan terjadi jika tegangan lebih besar dari harga treshold-nya (0 Volt). Tegangan akan lebih besar dari 0 jika noise positif dengan tegangan lebih besar dari +V. Karena parameter yang dipakai di dalam program adalah Signal to Noise Ratio (SIN) dan yang akan dicari adalah tegangan (V), maka perlu dibuat suatu hubungan antara tegangan dan variansi dengan signal noise. Didefinisikan tegangan kuadrat (V`) sama dengan daya sinyal (S) karena seolaholah. tegangan dc dan σ sama dengan daya noise (N). Dari definisi tersebut dapat dibuat suatu persamaan yaitu: 2
V2
σ
2
Bila
=
S ……………………… ……(3) N
σ 2 = 1 maka persamaan (3) menjadi:
V2 =
S …………………..(4) N
Pada penelitian ini diasumsikan noise adalah
g(x) = g 0 + g1 x + g 2 x 2 + .... + g n - k n -k . . ( 2 )
Gaussian dengan rataan 0 dan variansi σ . Oleh karena asumsi noise adalah Gaussian maka dalam simulasi ini diperlukan pembangkit bilangan, acak Gaussian dengan rataan = 0 dan harga variansi = 1. Proses pembangkitan salah bit dimulai dengan memberikan nilai Signal to Noise Ratio (SNR) yang diinginkan. Dari harga Signal to Noise Ratio dihitung besarnya tegangan (V) dengan menggunakan persamaan (4). Kemudian dibangkitkan sample noise (u) yang berupa bilangan acak berdistribusi Gaussian dengan rataan 0 dan variansi = 1. Setelah itu diambil bit-bit yang keluar dari inner enkoder di mana tiap yang diambil dibandingkan dengan tiap sampel noise yang dibangkitan. Berdasarkan sampel noise dan bit-bit yang keluar dari inner enkoder diputuskan apakah terjadi error atau tidak. Bila yang diambil adalah bit 1, error terjadi jika sampel noise negatif dengan tegangan lebih kecil dari -V. Bila yang diambil adalah bit 0, error terjadi jika noise positif dengan tegangan lebih besar dari +'V. Jika terjadi error, bit tersebut di invert yakni bit 1 menjadi bit 0 dan bit 0 menjadi bit 1.
11.3 Algoritma Pembangkitan Salah Bit Pada penelitian ini didefinisikan transmisi tanpa modulasi dan format sinyal adalah bipolar di mana bit 1 mewakili tegangan V volt dan bit 0 mewakili tegangan -V volt. Bila bit 1 dikirim error terjadi jika noise negatif dengan tegangan lebih kecil dari --V. Bila bit 0 dikirim error terjadi jika noise positif dengan tegangan lebih besar dari V. Bila bit 1 dikirim maka error akan terjadi jika
11.4 Algoritma Pendekodean Kode Hamming Algoritma pendekodean dari bit stream yang diterima oleh sistem penerima dengan menggunakan kode Hamming dimulai dengan menghitung sindrom dari kode yang diterima. Penghitungan sindrom ini untuk mengetahui apakah kode yang diterima benar atau tidak. Jika sindrom yang dihasilkan bemilai nol
⎡1 ⎢0 G= ⎢ ⎢1 ⎢ ⎣1
1 1 1 0
0 1 1 1
1 0 0 0
0 1 0 0
0 0 1 0
0⎤ 0⎥⎥ ………………….(1) 0⎥ ⎥ 1⎦
Algoritma pembentukan kode Reed Salomon (15,11) dimulai dengan mengambil k bit data sebanyak 44 bit. Kemudian 44 bit ini, diubah kedalam bentuk simbol di mana tiap 4 bit menjadi satu simbol. Sehingga dari 44 bit diperoleh 11 simbol. Kemudian simbol tersebut dikalikan dengan generator polinomial. Hasilnya adalah kode Reed Salomon. Bentuk umum generator polinomial dari kode Reed Salomon [Blahut. Rhichard E. 1983].
22
2
Kinerja Sistem Pengkodean dengan Menggunakan Kode Inner dan Kode Outer Sihar Parlinggoman Panjaitan
maka tidak ada error yang terdeteksi. Bila sindrom tidak bemilai nol maka ada error terdeteksi. Langkah selanjutuya adalah mencari posisi error. Setelah posisi error diketahui, dilakukan pengkoreksian terhadap bit-bit yang terkena error. Tahap terakhir dari proses pengdekodean adalah mengeluarkan bit-bit pariti. Proses dimulai dengan membuat inisialisasi pada mark data dan markcode dengan nilai nol. Proses selanjutnya adalah mengambil 7 bit data. Kemudian sindrom dihitung dengan menggunakan persamaan berikut.
Proses dimulai dengan membuat inisialisasi pada mark data dan markcode dengan nilai nol. Proses selanjutnya adalah mengambil sebanyak 60 bit data. Kode yang diterima diubah kedalam bentuk simbol di mana tiap 4 bit menjadi satu simbol. Sehingga dari 60 bit menjadi 15 simbol. Kemampuan koreksi kesalahan dari kode Reed Salomon (15,11) adalah 2. Banyaknya sindrom adalah dua kali kemampuan koreksi kesalahan. Sehingga sindromnya ada sebanyak 4, yang dihitung dengan persamaan berikut:
S = r HT...............................................................(5) di mana: r = kode yang diterima. HT = transposisi dari pariti check matriks.
s2 = r0 + r1 (α 2 )1 + r2 (α 2 ) 2 + ... + r14 (α 2 )14
Jika sindrom sama dengan nol, dekoder tidak melakukan pengkoreksian, kemudian bit-bit pariti dibuang dan bit-bit data disimpan pada array. Jika sindrom tidak sama dengan nol, dicari posisi error dengan membandingkan sindrom yang diperoleh dengan matriks pariti, yang mana posisinya diasumsikan sebagai posisi error. Setelah diperoleh posisi error maka dilakukan pengkoreksian. Untuk mengkoreksinya, bit pada posisi ke-i tersebut di invert yakni bit 1 menjadi bit 0 dan bit 0 menjadi bit 1. Setelah dikoreksi, bit-bit pariti dibuang dan bit-bit data disimpan pada array. 11. 5 Algoritma Salomon
Pendekodean
kode
Reed
Algoritma pendekodean dari bit stream yang diterima oleh sistem penerima dengan menggunakan kode Reed Salomon, dipilih algoritma Peterson Gorenstein Zieler (Wicker. Stephen B, 1995), Langkah-langkah dari algoritma adalah sebagai berikut: 1. Hitung sindrom dari bit stream yang telah melalui saluran transmisi. 2. Susun matriks sindrom P. 3. Hitung determinan matriks sindrom. Jika determinan tidak nol, lakukan langkah 5. 4. Jika determinan nol, susun matriks sindrom yang baru, dengan cara menghapus kolom paling kanan dau baris paling bawah dari matriks sindrom yang lama. 5. Hitung error locator σ dan susun error locator polinominal σ (x). 6. Hitung akar-akar persamaan error locator polinominal. 7. Hitung error magnitude. 8. Susun error polinomial. 9. Jumlahkan error polinomial dengan kode yang diterima. 10. Selesai.
s1 = r0 + r1α + r2α 2 + ... + r14α 14 s3 = r0 + r1 (α 3 )1 + r2 (α 3 ) 2 + ... + r14 (α 3 )14
..(6)
s4 = r0 + r1 (α 4 )1 + r2 (α 4 ) 2 + ... + r14 (α 4 )14 Kemudian sindrom S 1,S 2,S 3,S 4 diuji. Jika semua nol, berarti tidak ada error deteksi. Dekoder tidak melakukan pengkoreksian. Kemudian bit-bit data disimpan pada array. Jika sindrom tidak sama dengan nol, hitung determinasi matriks P, di mana:
⎡S p=⎢ 1 ⎣S 2
S2 ⎤ ………………………..(7) S 3 ⎥⎦
II.5.1 Determinan Sama dengan Nol Jika determinan sama dengan nol, hitung error locator σ dengan menggunakan persamaan:
σ=
S2 …………………………..(8) S1
Selanjutnya hitung error magnitude ei1 , dengan menggunakan persamaan:
ei1 =
S1
σ
……………………………(9)
Kemudian disusun error polynomial e(x)
e( x) = ei1 x
log
an
………………….(10) log
log
a5
Misalkan σ = α maka x a = x a = x Untuk memperoleh kode yang sebenarnya c(x), jumlahkan kode yang diterima r(x) dengan error polinomial e(x). 5
σ
5
c (x) = r ( x ) + e(x)………………(11) setelah kode diperoleh, maka bit-bit pariti dibuang, kemudian bit-bit data disimpan pada array
23
Jurnal Sistem Teknik Industri Volume 7, No. 4 Oktober 2006
II.5.2 Determinan Tidak Sama dengan Nol Bila determinan tidak sama dengan nol maka susun error locator polinomial dengan menggunakan persamaan:
σ ( x) = 1 + σ 1 x + σ 2 x 2 ………..(12) Di mana
σ1
dan
σ 2 diperoleh dari
S 2 ⎤ ⎡σ 2 ⎤ ⎡ S 3 ⎤ ……….(13) = S 3 ⎥⎦ ⎢⎣σ 1 ⎥⎦ ⎢⎣ S 4 ⎥⎦
⎡ S1 ⎢S ⎣ 2
Kemudian dicari akar-akar persamaan (8) yaitu β 1 dan β 2 . Selanjutnya akar-akar persamaan di invers sehingga diperoleh −1
−1
β1 dan
β 2 . Kemudian dihitung error magnitude ei1 dan ei2 dengan menggunakan persamaan.
⎡ β1 ⎢ −12 ⎣ β1
β2 β 2 −1
Setelah
diperoleh
−1
−1 2
⎤ ⎡ ei1 ⎤ ⎡ S1 ⎤ ⎥ ⎢e ⎥ = ⎢ ⎥ ……….(14) ⎦ ⎣ i2 ⎦ ⎣ S 2 ⎦ harga
kesalahan
ei1 dan
ei2 maka disusun error polynomial e (x). e( x) = ei1 x log a
β1−1
+ ei2 x log a
β 2 −1
……….(15)
Untuk memperoleh kode yang sebenarnya c(x), jumlahkan kode yang diterima r(x) dengan error polinomial e(x). c (x) = r ( x ) + e(x)……………………..…(16) setelah kode diperoleh, maka bit-bit parity dibuang, kemudian bit-bit data disimpan pada array III. PELAKSANAAN PENELITIAN Pelaksanaan penelitian ini dilakukan dalam bentuk program simulasi pada komputer yang dibuat sedemikian rupa sehingga dapat mewakili hasil dari sistem yang sesungguhnya. Program komputer yang dibuat ditulis dalam bahasa Pascal versi 7.0. III. I Proses Simulasi Proses simulasi dimulai dengan membuat inisialisasi Jumlah bit (nbits) dan jumlah error (nerror) dengan nilai nol. Kemudian memberikan harga Signal to Noise Ratio (SNR) yang diinginkan. Selanjutnya memberikan jumlah bit yang hendak dikirimkan (Nbit stream) kemudian
24
dibangkitkan bit stream oleh pembangkit bit. Bit stream yang dibangkitkan diambil sebagiansebagian. Kemudian bit-bit tersebut dikodekan oleh outer enkoder. Hasilnya disimpan pada array codeoutouter. Hasil pengkodean outer enkoder ini merupakan bit stream bagi inner enkoder, untuk selanjutnya dikodekan oleh inner enkoder menjadi kode gabungan yang disimpan pada array codeoutinner. Kemudian bit-bit tersebut dikirimkan ke inner dekoder melalui kanal di mana pada kanal dibangkitkan salah bit. Bit-bit yang telah melalui kanal disimpan pada array codechannel. Kemudian bit-bit tersebut didekodekan oleh inner dekoder. Hasil pengdekodean disimpan pada array datoutinner. Selanjutnya bit-bit tersebut didekodekan oleh outer dekoder. Hasil pengdekodean disimpan dalam array data out Kemudian dihitung jumlah bit yang error dengan cara membandingkan bit pada array datain dan bit pada array dataout. 111. 2 Pengujian Algoritma Yang Disusun Pengujian algoritma yang disusun bertujuan untuk menunjukkan bahwa algoritma tersebut dapat diterapkan dan dapat berfungsi sesuai dengan perancangannya. Pengujian dilakukan dengan menerapkan algoritma dalam bentuk program simulasi komputer, kemudian menguji masing-masing prosedur di dalam program tersebut. Setiap prosedur yang dibuat diuji secara terpisah dengan cara memberikan data masukan tertentu, kemudian membandingkan data keluarannya dengan data yang diproses secara manual. Setelah semua prosedur diuji, maka dilakukan pengujian gabungan seluruh prosedur. 111. 3 Hasil-Hasil Penelitian Pada penelitian ini percobaan dilakukan dengan sepuluh kali pengamatan. Data yang diperoleh berdasarkan hasil rata-rata dari kesepuluh pengamatan tersebut. Adanya beberapa angka desimal di belakang koma disebabkan tidak tepatnya jumlah bit masukan dengan datanya. Misalnya untuk jumlah bit masukan sebanyak 100000 bit, datanya menjadi 100100 bit. Untuk bit masukan sebanyak 1000000 bit, datanya menjadi 1000076 bit dan untuk bit masukan sebanyak 10000000 bit, menjadi 10000144 bit.
Kinerja Sistem Pengkodean dengan Menggunakan Kode Inner dan Kode Outer Sihar Parlinggoman Panjaitan
Tabel 1. Kinerja Kode Inner dan Outer Hamming– Reed Solomon Efisiensi: 0,4191 Kemampuan Koreksi Kesalahan: 7 BER masukan
BER keluaran
9.4879 x 10-3
1,9691 x 10-4
7,0121 x 10-3
8,697 x 10-5
5,0484 x 10-3
3,626 x 10-5
3,5320 x 10-3
1,48 x 10-5
2,3948 x 10-3
5 ,65x 10-6
1,5691 x 10-3
2,01 x 10-6
Tabel 2. Kinerja Kode Inner dan Outer Reed Salomon-Hamming. Efesiensi: 0,4191 Kemampuan Koreksi Kesalahan: 7 BER masukan
BER keluaran
S/N tanpa pengkode (dB)
S/N dengan pengkode (dB)
Koding Gain (dB)
7,9800
4,4
3,5800
8,4826
4,8
3,6826
8,9608
5,2
3,7608
9,4038
5,6
3,8038
9,8403
6
3,8403
10,2664
6,4
3,8664
Tabel 5. Koding Gain Kode Inner dan Outer Reed Salomon–Hamming Efisiensi: 0,4191 Kemampuan Koreksi Kesalahan: 7 S/N tanpa pengkode (dB)
S/N dengan pengkode (dB)
Koding Gain (dB)
9,4879 x 10
-3
6,2131 x 10
7,0121 x 10
-3
2,9015 x 10-4
7,1708
4,4
2,7708
5,0484 x 10
-3
-4
3,5320 x 10
-3
2,3948 x 10
-3
1,5691 x 10-3
1,3292 x 10
-4
Tabel 4. Koding Gain Kode Inner dan Outer Hamming-Reed Salomon Efiensi: 0,4191 Kemampuan Koreksi Kesalahan: 7
7,7225
4,8
2,9225
5,765 x 10
-5
8,2272
5,2
3,0272
2,341 x 10
-5
8,7122
5,6
3,1122
9,1836
6
3,1836
9,645 1
6,4
3,2451
8,81 x 10-6
Tabel 3. Kinerja Kode BCH (127,57) Efisiensi: 0,4488 Kemampuan Koreksi Kesalahan: 11 BER masakan
BER keluaran
9,4879 x 10-3
1,2420 x 10-2
7,0121 x 10-3 5,0484 x 10-3
Tabel 6. Koding Gain kode BCH (127,57). Efisiensi: 0,4488 Kemampuan Koreksi Kesalahan: 11
4,7622 x 10-3
S/N tanpa pengkode (dB)
S/N dengan pengkode (dB)
Koding Gain (dB)
1,4873 x 10-3
4,0097
4,4
-0,3903
5,2645
4,8
0,4645
6,4459
5,2
1,2459
7.5515
5,6
1,9515
8,5838
6
2,5838
9,5476
6,4
3,1476
3,5320 x 10
-3
-4
3,71102 x 10
2,3948 x 10
-3
7.2555 x 10
-5
1,5691 x 10
-3
1.0921 x 10
-5
IV. ANALISIS HASIL PENELITIAN Analisis hasil penelitian mencakup pengaruh parameter signal to Noise Ratio terhadap koding gain dari sistem yang diteliti. Besarnya koding gain (marving et. al. 1995): Koding gain = S/N tanpa pengkode-S/N dengan pengkode……….(10)
25
Jurnal Sistem Teknik Industri Volume 7, No. 4 Oktober 2006
3.
4.
Grafik 2. Koding Gain terhadap Signal to Noise Ratio Inner dan Outer Hamming-Reed Salomon, Reed Salomon-Hamming serta Kode BCH (127,57). Pada gambar 2, terlihat bahwa Koding Gain inner dan outer code Hamming-Reed Salomon dan Reed Salomon-Hamming lebih tinggi bila dibandingkan dengan kode BCH (127,57), Koding Gain inner dan outer Hamming Reed Salomon lebih tinggi, bila dibandingkan dengan inner dan outer code Reed Salomon-Hamming. V. KESIMPULAN Dari penelitian yang telah dilakukan, maka dapat diambil kesimpulan antara lain: 1. Kinerja sistem pengkodean dengan menggunakan kode gabungan lebih andal dibanding dengan kinerja sistem pengkodean yang menggunakan kode tunggal pada Bit Error Rate masukan dari 10-2 sampai 10-3. 2. Kenaikan koding gain semakin kecil pada signal to noise ratio yang semakin besar
26
Koding Gain Hamming sebagai inner code dan Reed Salomon sebagai outer code lebih tinggi dibandingkan dengan Reed Salomon sebagai inner code dan Hamming sebagai outer code Hasil pemodelan simulasi ini mendeksi hasil secara teoretis yakni dengan naiknya signal to noise ratio, maka Bit Error Rate cenderung semakin menurun. Dengan demikian model sistem yang dibuat dapat diyakini untuk mewakili sistem yang sebenarnya.
DAFTAR PUSTAKA Blahut, R.E., (1983), Theory and Practice Of Error Control Codes, Addison-Wesley Pubishing Company Inc., New York. Christian, T., (1987) Error Correcting Capabilities of Concatenated Codes With MDS Outer On Memoryless Channels with MaximumLikelihood Decoding, IEEE Transactions on Information Theory, Vol. IT-33, No.5 Fazel, (1989), K., P. Salembier, Application of Error Modeling at The Output Maximum Likelihood Dekoder to Concatenated Coded 16 PSK, Laboratories d’Electronique Philips, 3 Avenue Descartes 94451 LimeilBrevannes Cedex (France), IEEE, pq. 15281533. Man Young Rhee, (1989), Error Correcting Coding Theory, Mc Graw-Hill., New York. Wicker Stephen.B, Error Control Systems for Digital Communication and Storage, Prentice-Hall International Inc.,1995.
