Bab II Teori Encoding-Decoding Reed-Solomon Code
Reed-Solomon Code adalah salah satu teknik error and erasure correction yang paling baik dan dijadikan standar dalam banyak bidang diantaranya komunikasi satelit dan mobile, magnetic recording, dan high-definition television [2]. Dalam komunikasi nirkabel, data yang dikirimkan oleh transmitter tentu akan mendapatkan noise dari kanal (channel) yang bisa mengakibatkan kerusakan pada data. Reed-Solomon Decoder mampu mengembalikan data yang rusak tersebut. Salah satu kelebihan Reed-Solomon adalah non-binary code (data diolah dalam word) sehingga kemampuan koreksi data lebih banyak.
Gambar 3 Komuniksi data digital
I.1.
Aritmatika Galois Field
Dalam Reed-Solomon Code, operasi aritmatika—baik penjumlahan, pengurangan, perkalian, maupun pembagian—dilakukan dalam Galois Field arithmetic. Galois Field adalah finite field, yang berarti merupakan himpunan yang memiliki elemen terbatas. Sebagai contoh, GF(24) terdiri dari 16 elemen bilangan. Permasalahan dalam aritmatika GF(24) akan muncul apabila, misalnya, mengalikan bilangan 4 6
dengan 5. Pada aritmatika normal, hasilnya adalah 20. Tapi, dalam GF(24) tidaklah demikian karena angka 20 tidak termasuk elemen dalam GF(24). Untuk menghitung perkalian 4 dengan 5 dalam Galois Field arithmetic digunakan table yang dibentuk dari primitive polinomial yang akan dijabarkan pada bagian selanjutnya.
I.1.1.
Finite Field GF(p)
GF merupakan himpunan elemen terbatas. Untuk setiap bilangan prima p, akan ada finite field GF(p) yang terdiri dari sejumlah p bilangan. Sebagai contoh, binary field simpel GF(2) terdiri dari hanya bilangan 0 dan 1. Pada GF(2) = {0, 1}, penjumlahan dilakukan dengan modulo 2 dan perkalian dilakukan dengan fungsi logika AND. Untuk GF(256) = {0, 1, 2, …, 255} yang merupakan extension filed GF(2), penjumlahan dilakukan dengan modulo 2 dan perkalian dilakukan dengan fungsi logika yang diturunkan dari tabel primitive polinomial.
I.1.2.
Extension Field GF(pm)
Finite Field GF(p) dapat dikembangkan ke field pm elements. Ini disebut sebagai extension field dari GF(p) dan dinotasikan GF(pm) dengan m adalah bilangan integer bukan 0. Sebagai contoh, disamping 0 dan 1, ada tambahan unique element yang disebut sebagai primitive element α. Setiap non-zero elemen dalam GF(2m) dapat direpresentasikan kedalam bilangan pangkat dari α. Yaitu 0, 1, α1, α2, α3, ..., α(2m-2). Perlu dicatat disini bahwa elemen GF(2) yaitu 0 dan 1 juga merupakan elemen pada GF(2m).
I.1.3.
Representasi Galois Field
Himpunan tak hingga suatu bilangan I(2m) dapat direpresentasikan sebagai 0, 1, α1, α2, …, ∞. Tapi, himpunan tersebut tidak merepresentasikan Galois Field. Galois Field direpresentasikan oleh himpunan terbatas suatu bilangan dimana jumlah elemen maksimum adalah 2m. Elemen pada GF(2m) adalah 0, 1, α1, α2, α3, ..., α(n-1) dimana n = 2m -1. Setiap angka yang lebih besar dari α(n-1) tidak diperbolehkan. 7
Operasi perkalian yang menghasilkan bilangan yang lebih besar dari α(n-1) harus dikonversikan ke dalam operasi yang tidak menghasilkan angka yang lebih besar dari α(n-1). Dalam hal ini, dilakukan dengan tabel dari primitive polinomial.
I.1.4.
Polinomial Galois Field
Sebuah polinomial a(x) degree m pada finite field GF(p) dituliskan sebagai a(x) = amxm + … + a1x + a0. Dimana koefisien ai adalah elemen dalam GF(p) dengan am ≠ 0. Derajat (degree) dari polinomial a(x) adalah pangkat tertinggi dari x, yaitu m. Polinomial tersebut dapat dijumlahkan, dikurangi, dikalikan, dan difaktorisasi dengan polinomial pada field yang sama. Misalkan n(x) dan m(x) adalah polinomial pada GF(256), maka n(x)+m(x), n(x)-m(x), n(x) m(x), dan n(x)/m(x) terdefinisi. Primitive element α dapat berupa sembarang angka, tetapi untuk aplikasi RS Code biasanya dipilih angka 2. Elemen bilangan GF 0, 1, α1, α2, α3, ..., α(n-1) dapat direpresentasikan dalam
bentuk polinomial amxm + … + a1x + a0, dimana
koefisien am-1 sampai a0 bernilai 0 atau 1. Oleh karena itu, setiap elemen bilangan GF 0, 1, α1, α2, α3, ..., α(n-1) dapat dituliskan dalam angka m-bit biner, dan representasi biner ini dapat juga dituliskan kedalam bentuk desimal. Contoh perhitungan: Sebagai contoh, GF(32) = GF(2m) dengan m=5. Representasi elemen bilangan GF(32) dalam bentuk polinomial adalah a4x4 + a3x3 + a2x2 + a1x2 + a0x0 dengan a4, a3, a2, a1, a0 berkorespondensi dengan 0000 sampai 11111, atau dalam bentuk desimal 0 sampai 31. Perlu dicatat bahwa x adalah indikator posisi koefisien (indeks). Tabel tabel contoh representasi indeks, polinomial, biner dan desimal elemen bilangan GF(24) terdapat dalam lampiran.
8
I.1.5.
Primitive Polinomial
Dalam Galois Field, dikenal sebuah polinomial f(x) yang disebut primitive polinomial. Polinomial f(x) pada GF(2m) bersifat tidak dapat direduksi dan difaktorisasi ke dalam bentuk polinomial yang lebih kecil pada filed GF yang sama, atau dengan kata lain tidak memiliki faktor. Dan irreducible polinomial f(x) pada degree m dikatakan primitive apabila untuk setiap bilangan positif integer terkecil n, dengan n = 2m - 1, polinomial xn + 1 dapat dibagi oleh polinomial f(x) dengan sisa pembagian (remainder) nol. Untuk setiap irreducible polinomial f(x) merupakan primitive polinomial apabila paling tidak satu dari akarnya adalah primitive elemen. Irreducible polinomial ini akan digunakan pada operasi perkalian dua elemen Galois Field. Dalam Galois Field, mungkin terdapat lebih dari sebuah primitive polinomial, akan tetapi, dalam proses encoding dan decoding, hanya bisa digunakan satu macam saja. Jika xm + xm-1 + … + 1 adalah primitive polinomial, maka x ... juga primitive polinomial. Contoh perhitungan: Untuk GF(216) biasanya digunakan primitive polinomial f(x) = x8 + x4 + x3 + x2 + 1. Tabel beberapa primitive polinomial untuk GF(2m) dapat dilihat pada lampiran.
I.1.6.
Aritmatika pada Galois Field
Dalam finite field, dapat dilakukan operasi penjumlahan, pengurangan, perkalian, dan pembagian, akan tetapi berbeda dengan operasi biasa. Dalam finite field, setiap operasi elemen bilangan selalu akan menghasilkan elemen bilangan lain dalam himpunan terbatas.
I.1.7.
Operasi Penjumlahan dan Pengurangan
Cara melakukan operasi penjumlahan adalah sebagai berikut, (amxm + … + a1x + a0) + (bmxm + … + b1x + b0) = cmxm + … + c1x + c0, dimana ci = ai + bi untuk (m-1) ≥ i ≥ 0. Sama halnya dalam operasi pengurangan dua elemen GF (amxm + … + a1x + a0) - (bmxm + … + b1x + b0) = cmxm + … + c1x + c0, dimana ci = ai + bi untuk (m9
1) ≥ i ≥ 0. Operasi + dan – dilakukan dengan modulo 2, yaitu dengan operasi logika XOR. Sehingga, baik penjumlahan maupun pengurangan akan didapatkan hasil ci = 0 untuk ai = bi dan ci = 1 untuk ai ≠ bi. Dengan kata lain, penjumlahan dan pengurangan adalah identik dalam Galois Field. Contoh perhitungan: Sebagai contoh, pada GF(16) kita dapat mengurangkan x3 + x dengan x3 + x2 + x + 1, sehingga (x3 + x) – (x3 + x2 + x + 1) = (x3 + x) + (x3 + x2 + x + 1) = x2 + 1. Dalam representasi biner, (1010) – (1111) = (1010) + (1111) = 0101. Atau dalam representasi decimal, 10 – 15 = 10 + 15 = 5. Perlu dicatat bahwa hasil perhitungan GF tidak bisa didapatkan pada manipulasi dalam bentuk desimal. Bentuk desimal hanya digunakan sebagai cara yang mudah untuk merepresentasikan bilangan. Operasi Perkalian dan Pembagian
I.1.8.
Dengan primitive polinomial dapat ditentukan bentuk tiap elemen bilangan GF, baik dalam bentuk index, polinomial, binary, ataupun desimal. Dengan mengetahui bentuk elemen bilangan tersebut, dapat dicari hasil operasi perkalian dua
elemen
bilangan
GF.
Pada
GF(2m)
perkalian
dua
elemen
a ( x ) = am x m + am −1 x m −1 + ... + a1 x1 + a0
bilangan
b( x) = b m x m + bm −1 x m −1 + ... + b1 x1 + b0
akan
dan menghasilkan
c( x) = c m x m + cm −1 x m −1 + ... + c1 x1 + c0 , dimana konstanta cm, ..., c0 didapatkan dari
reduksi bilangan berdasarkan primitive polynomial. Contoh perhitungan: Misalkan, operasi perkalian antara bilangan 14 dengan 11 pada GF(24) dapat dilakukan dalam bentuk indeks maupun polinomial. Dalam bentuk indeks, representasikan bilangan tersebut kedalam bentuk seperti yang tertera pada tabel pada lampiran. Representasi hasil perkalian dalam bentuk index adalah α(jumlah kedua index)mod(2m-1)
.
Bilangan
14
merepresentasikan 10
α11
dan
bilangan
11
merepresentasikan α7. Sehingga, α11 × α7 = α18mod(15) = α3 = 8, atau 14 × 11 = 8 pada GF(24). Dengan cara lain, hasil perkalian bisa dicari dalam bentuk polinomial, yaitu (α3 + α2 + α)(α3 + α + α) = α6 + α4 + α3 + α5 + α3 + α2 + α4 + α2 + α = α6 + α5 + α = α3 + α2 + α2 + α + α = α3 = 8. Operasi pembagian 8 dengan 14 pada GF(24) mirip dengan perkalian. Perhitungan dapat dilakukan dalam bentuk indeks maupun polinomial. Representasi hasil pembagian dalam bentuk indeks adalah α(selisih
kedua index)mod(2m-1)
3
. Bilangan 8
11
merepresentasikan α dan bilangan 14 merepresentasikan α . Sehingga, α3/ α11 = α(3-11)mod(15) = α-(8)mod(15) = α7 = 11. Elemen inverse dari GF didefinisikan sebagai nilai elemen bilangan yang jika dikalikan menghasilkan nilai 1. Jika 14 merepresentasikan α11 maka inversenya adalah α-11 = α(-11)mod(15) = α4 = 3. Maka, 8/14 = 8 x 3 = α3 x α4 = α7mod(15) = α7 = 11, atau 8/14 = 11. Teknik ini banyak dipakai dalam implementasi operasi pembagian GF karena lebih cepat komputasinya daripada teknik pembagian berdasarkan polinomial.
I.2. I.2.1.
Encoding Reed-Solomon Code Code Generator Polinomial g(x)
Bentuk konvensional Reed-Solomon Code adalah (n, k) = (n, n-2t) = (2m – 1, 2m – 1- 2t), dengan n = total code length, k = total jumlah parity simbol, t = kemampuan error koreksi, dan m = jumlah bit tiap simbol. Perlu dicatat bahwa pada code berbasis m-bit simbol, Galois Field memiliki 2m elemen. Sebuah Reed-Solomon Code (n, k) dibuat dengan membentuk code generator polinomial. Polinomial tersebut terdiri dari n – k = 2t faktor, yaitu g(x) = g0 + g1x + g2x2 + … + g2t-1x2t-1 + x2t. Derajat dari polinomial tersebut merupakan jumlan parity simbol yaitu 2t. Jumlah akar dari polinomial tersebut sama dengan derajatnya yaitu 2t. Sehingga ada 2t nilai αi 0 ≤ i ≤ 8. Jika akar pertama adalah αp, maka 11
akar dari g(x) adalah αp, αp+1, αp+2, …, αp+2t-1. Sehingga code generator polinomial menjadi g(x) = (x + αp)( x + αp+1)…( x + αp+2t-1). Contoh perhitungan: Misalkan untuk (n, k) = (15, 11), maka panjang blok (block length) adalah 15 simbol, informasi adalah 11 simbol, pariti adalah 2 simbol, dan jumlah bit dalam satu simbol adalah 4. Dalam kasus ini t = 2, yang mengindikasikan bahwa ada dua simbol yang dapat dikoreksi. RS(15, 11) ini berbasis GF(16). Untuk p = 0, maka didapat g(x) = (x + 1)(x + α) (x + α2) (x + α3) = x4 + x3α3 + x3α2 + x2α5 + x3α + x2α4 + 2x2α3 + xα6 + x3 + x2α2 + xα5 + x2α + xα4 + xα3 + α6 = x4 + x3(α3 + α2 + α + 1) + x2(α5 + α4 + 2α3 + α2 + α) + x(α6 + α5 + α4 + α3) + α6. Dengan menggunakan tabel 1 untuk GF(16) dapat diperoleh code generator polinomial g(x) = x4 + α12x3 + α4x2 + α0x + α6 = x4 + 15x3 + 3x2 + x + 12.
I.2.2.
Code Generator Polinomial pada GF (255, 239)
Beberapa standar komunikasi wireless seperti WiMax dan DVB-T menggunakan Reed-Solomon Code (255, 239). Pada kode ini block length adalah 255 simbol, message length adalah 239 simbol, kemampuan koreksi error adalah 8 simbol, dan jumlah bit per simbol adalah 8 bit. Kode tersebut berbasis pada GF(216) = GF(256). Field generator polinomial untuk kode ini adalah f(x) = x8 + x4 + x3 + x2 + 1. Dan karena α merupakan akar dari polinomial tersebut, maka 0 = α8 + α4 + α3 + α2 + 1, dan α8 = α4 + α3 + α2 + 1. Sedangkan code generator polinomial g(x) = (x + α0)(x + α1)…(x + α15) = x16 + 59x15 + 13x14 + 104x13 + 189x12 + 68x11 + 209x10 + 30x9 + 8x8 + 163x7 + 65x6 + 41x5 + 229x4 + 98x3 + 50x2 + 36x + 59.
I.2.3.
Systematic Encoding Reed-Solomon Code
Encoding Reed-Solomon disebut systematic encoding, yaitu blok data pariti tidak mengubah data message. Dalam systematic encoding, dikenal empat polinomial yaitu M(x), T(x), r(x), q(x). M(x) adalah data message, T(x) adalah data yang dikirimkan, q(x) adalah quotient, sedangkan r(x) adalah remainder. 12
K simbol pesan (message) dapat direpresentasikan ke dalam polinomial M(x) orde k-1. Polinomial data yang ditransmisikan T(x), dapat dinyatakan dari polinomial message dan polinomial r(x), atau dari perkalian dari polinomial quotient q(x) dan polinomial codeword generator g(x). Jika pada receiver, data T(x) dibagi dengan g(x) tidak menghasilkan remainder, maka data pada tersebut tidak terdapat error. Saat transmisi, polinomial quotient q(x) tidak dipakai. M(x) direpresentasikan kedalam M(x) = Mk-1xk-1 + … + M1x + M0, dimana tiap koefisien Mk-1, …, M0 adalah m-bit simbol message. Simbol Mk-1 adalah simbol pertama dan merupakan most significant bit (MSB). Dalam transmisi, T(x) adalah M(x) yang di-shift sehingga derajatnya menjadi n-k, lalu r(x) ditambahkan pada LSB. Caranya adalah mengalikan M(x) dengan xn-k sehingga r(x) bisa masuk kedalam posisi degree n-k. T(x) = M(x)xn-k + r(x) = (Mk-1x(k-1)+(n-k) + … + M0) + (rnn-k-1 k-1x
+ … + r0) = (Mk-1xn-1 + … + M0) + (rn-k-1xn-k-1 + … + r0). Untuk
memperoleh polinomial remainder r(x), polinomial message M(x) dibagi dengan polinomial code generator g(x). Pembagian akan menghasilkan polinomial quotient q(x) dan polinomial remainder r(x).
Atau M(x)xn-k = g(x)q(x) + r(x), atau M(x)xn-k + r(x) = g(x)q(x). Polinomial sebelah kiri adalah T(x). Langkah-langkah encoding untuk RS(15, 11) ini adalah: 1. Bentuk polinomial M(x) dengan k = 11 simbol. 2. Kalikan M(x) dengan x4 untuk membuat ruang bagi r(x). 3. Bagi M(x)x4 dengan g(x) untuk menghasilkan r(x). 4. Buang q(x), karena tidak dibutuhkan. 5. Tambahkan 4 simbol r(x) kepada M(x)x4 untuk membentuk simbol T(x) dengan n = 15 simbol.
13
Contoh perhitungan: Misalkan pada contoh di atas, untuk RS(15, 11) ada data message 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7. Message tersebut akan di-encode dengan g(x) = x4 + α12x3 + α4x2 + α0x + α6 = x4 + 15x3 + 3x2 + x + 12, maka: 1. M(x) = 2x10 + 2x9 + 3x8 + 3x7 + 4x6 + 4x5 + 5x4 + 5x3 + 6x2 + 6x + 7. 2. M(x)x4 = 2x14 + 2x13 + 3x12 + 3x11 + 4x10 + 4x9 + 5x8 + 5x7 + 6x6 + 6x5 + 7x4. 3. M(x)x4 / g(x) = (2x14 + 2x13 + 3x12 + 3x11 + 4x10 + 4x9 + 5x8 + 5x7 + 6x6 + 6x5 + 7x4) / (x4 + 15x3 + 3x2 + x + 12). M(x)x4 / g(x) = { (2x14 + 2x13 + 3x12 + 3x11 + 4x10 + 4x9 + 5x8 + 5x7 + 6x6 + 6x5 + 7x4) / 2x10 (x4 + 15x3 + 3x2 + x + 12) } 2x10 M(x)x4 / g(x) = { (2x14 + 2x13 + 3x12 + 3x11 + 4x10 + 4x9 + 5x8 + 5x7 + 6x6 + 6x5 + 7x4) / (2x14 + 13x13 + 6x12 + 2x11 + 11x10) } 2x10. M(x)x4 / g(x) = { (2x10 + 15x9 + 15x8 + 9x7 + 12x6 + 3x5 + x4 + 5x3 + 15x2 + 5x + 10) + ( (5x3 + 3x + 1) / (2x14 + 13x13 + 6x12 + 2x11 + 11x10) ) } 2x10. Lalu menghasilkan r(x) = 5x3 + 3x + 1. 4. q(x) = 2x10 + 15x9 + 15x8 + 9x7 + 12x6 + 3x5 + x4 + 5x3 + 15x2 + 5x + 10. Polinomial ini tidak dipakai. 5. T(x) = M(x)xn-k + r(x) = 2x14 + 2x13 + 3x12 + 3x11 + 4x10 + 4x9 + 5x8 + 5x7 + 6x6 + 6x5 + 7x4 + 5x3 + 3x + 1. Polinomial T(x) dapat direpresentasikan kedalam GF(15, 11) biner yaitu T(x) = (0010) x14 + (0010) x13 + (0011) x12 + (0011) x11 + (0100) x10 + (0100) x9 + (0101) x8 + (0101) x7 + (0110) x6 + (0110) x5 + (0111) x4 + (0101) x3 + (0000) x2 + (0011) x1 + (0001). Atau dalam GF(15, 11) indeks yaitu T(x) = αx14 + αx13 + α4x12 + α4x11 + α2x10 + α2x9 + α8x8 + α8x7 + α5x6 + α5x5 + α10x4 + α8x3 + α4x + α0 .
I.2.4.
Encoding pada RS(255, 239)
Sama halnya dengan langkah encoding pada RS(15, 11), encoding pada RS(255, 239) dilakukan dengan membagi M(x) dengan g(x) untuk mendapatkan r(x), 14
dimana g(x) = x16 + 59x15 + 13x14 + 104x13 + 189x12 + 68x11 + 209x10 + 30x9 + 8x8 + 163x7 + 65x6 + 41x5 + 229x4 + 98x3 + 50x2 + 36x + 59. Lalu diperoleh T(x) = M(x)xn-k + r(x). Implpementasi Encoder RS ini dapat dibuat dengan LFSR modulo untuk menghasilkan remainder. I.2.5.
RS-Shortened Code
Dalam beberapa standard telekomunikasi seperti WiMax dan DVB-T, digunakan RS-Shortened Code, misalnya RS(204, 188). Reed-Solomon Code ini diperoleh dengan menambahkan 51 simbol MSB pada 188 simbol message sehingga ada 239 simbol message M(x), lalu diencode dengan RS(255, 239) dan hasilnya yaitu 255 simbol T(x). Dari 255 simbol ini diambil 204 simbol LSB untuk dikirimkan lewat transmitter. Untuk standard WiMax digunakan shortened Reed-Solomon Code sebagai berikut: Tabel 1 Code-rate RS Code pada WiMax
Modulation Uncoded block Coded block Overall size (bytes)
size (bytes)
RS Code
coding
CC code rate
rates BPSK
12
24
½
(12, 12, 0)
½
QPSK
24
48
½
(32, 24, 4)
2/3
QPSK
36
48
¾
(40, 36, 2)
5/6
16-QAM
48
96
½
(64, 48, 8)
2/3
16-QAM
72
96
¾
(80, 72, 4)
5/6
64-QAM
96
144
2/3
(108,
96, ¾
6) 64-QAM
108
144
¾
(120, 108, 5/6 6)
15
I.3.
Decoding Reed-Solomon Code
Pada decoding reed-Solomon, R(x) adalah polinomial data yang diterima, sedangkan E(x) adalah polinomial error yang menyebabkan data yang diterima berbeda dari data yang dikirimkan. Disinilah proses decoding dijalankan. Ada empat tahap dalam decoding Reed-Solomon Code yaitu: syndrome computation, error locator polinomial, error evaluator polinomial, dan correcting error. Berikut ini block diagram sistemnya: Received Code RAM
a
Syndrome computation
b
Improved Euclidean
c
Chien Search
e
Fast Komo Algorithm
d
Error Correcting
f
Gambar 4 Proses Decoding Reed-Solomon Code
Dimana a = received code, b = syndrome polinomial, c = error locator polinomial, d = error value, e = error location, f = corrected code. Polinomial received code terhadap transmitted code dideskripsikan oleh persamaan berikut: R(x) = T(x) + E(x), dimana E(x) = En-1xn-1 + … + E1x + E0 adalah m-bit nilai error yang direpresentasikan oleh elemen dari GF(2m). Degree dari x pada E(x) mengindikasikan posisi error pada code word. Jumlah error yaitu t, yang bisa dikoreksi adalah (n-k)/2. Jika ada error lebih dari t yang muncul, maka code tersebut tidak dapat dikoreksi. Contoh perhitungan: Misalkan, pada encoding RS(15, 11) diatas, T(x) = αx14 + αx13 + α4x12 + α4x11 + α2x10 + α2x9 + α8x8 + α8x7 + α5x6 + α5x5 + α10x4 + α8x3 + α4x + α0. Dan asumsi ada dua error yang muncul, yaitu E(x) = 0x14 + 0x13 + 0x12 + 0x11 + α5x10 + 0x9 + 0x8 + 0x7 + 0x6 + 0x5 + α0x4 + α12x3 + 0x2 + 0x + 0. Sehingga didapat R(x) = T(x) + E(x) = 16
αx14 + αx13 + α4x12 + α4x11 + αx10 + α2x9 + α8x8 + α8x7 + α5x6 + α5x5 + α10x4 + α9x3 + α4x + α0. Dalam contoh ini ada dua hal ayng tidak diketahui, posisi error dan nilai error. Karena RS code bekerja pada simbol (m-bit word), maka tidak cukup hanya ditentukan lokasi errornya lalu di-flip nilai pada posisi tersebut, akan tetapi perlu nilai errornya juga. Karena ada empat nilai yang tidak diketahui, maka perlu ada empat persamaan untuk mendapatkan nilainya.
I.3.1.
Menghitung Syndrome
Syndrome Si adalah remainder hasil dari pembagian R(x) oleh masing-masing faktor dari code generator polinomial g(x). Syndrome ini adalah bagian utama proses decoding yang dapat menentukan posisi error dan nilai errornya. Jika nilai syndrome ini semuanya nol, maka R(x) adalah code word yang valid/tanpa error. Jika ada salah satu nilai syndrome yang tidak nol, maka ini mengindikasikan adanya error. Untuk RS(n, k) = RS(16, 11), g(x) = (x + 1)(x + α)(x + α2)(x + α3), dan T(x) = q(x)g(x) = q(x)(x + 1)(x + α)(x + α2)(x + α3), dan T(x)/(x + α3) = q(x)(x + 1)(x + α)(x + α2), sehingga T(x) akan selalu bisa dibagi dengan g(x) dengan menghasilkan remainder nol. Langkah pada syndrome computation ini adalah membagi data received R(x) dengan masing-masing faktor (x + αi) untuk menghasilkan quotient dan remainder. Yaitu ditunjukkan oleh persamaan berikut:
Remainder Si pada persamaan diatas disebut syndrome. Untuk p = 0, maka syndrome S0, …, S2t-1. Dari persamaan diatas didapat Si = Qi(x)(x + αi) + R(x) untuk p ≤ i ≤ (p+2t-1). Jika x = αi, maka persamaan akan tereduksi menjadi Si = R(αi), sehingga Si = Rn-1(αi)n-1 + Rn-2(αi)n-2 + … + R1(αi) + R0, dimana setiap koefisien Rn-1, …, R0 adalah simbol data received m-bit. Persamaan tersebut 17
memberikan metode alternative yang lebih cepet untuk mencari syndrome daripada pembagian polinomial R(x) oleh (x + αi). Karena (x - αi) adalah faktor dari T(x), jika x = αi, kita tahu bahwa T(αi) = 0. Dari R(x) = T(x) + E(x), kita tahu bahwa R(αi) = E(αi) = Si. Hal itu menunjukkan bahwa syndrome adalah independen terhadap berapapun nilai T(x), tetapi dependen terhadap nilai error E(x). Contoh perhitungan: Dari contoh sebelumnya, R(x) = αx14 + αx13 + α4x12 + α4x11 + αx10 + α2x9 + α8x8 + α8x7 + α5x6 + α5x5 + α10x4 + α9x3 + α4x + α0. Maka, untuk primitive elemen 1, α, α2, α3, didapat S0 = R(1) = α14, S1 = R(α) = 0, S2 = R(α2) = α12, dan S3 = R(α3) = α9. Karena kita tahu bahwa R(αi) = E(αi) = Si, maka E(x) = 0x14 + 0x13 + 0x12 + 0x11 + α5x10 + 0x9 + 0x8 + 0x7 + 0x6 + 0x5 + α0x4 + α12x3 + 0x2 + 0x + 0 atau E(x) = α5x10 + α12x3 seharusnya juga bisa dibentuk dari Si = E(αi). Yaitu S0 = E(1) = α5 + α12 = 1 + α3 = α14, S1 = E(α) = 0, S2 = E(α12) = α25 + α18 = α10 + α3 = α12, S3 = E(α3) = α35 + α21 = α5 + α6 = α9, yang sama hasilnya dengan memakai R(x). I.3.1.1.
Metode Horner Untuk Menghitung Syndrome
Persamaan syndrome Si = Rn-1(αi)n-1 + Rn-2(αi)n-2 + … + R1(αi) + R0 dapat diubah menjadi Si = ( …(Rn-1αi + Rn-2)αi + … + R1)αi + R0. Dengan bentuk seperti ini implementasi sebuah cell syndrome generator dapat lebih mudah karena hanya memerlukan sebuah multiplier yang dipakai secara simultan atau iterative. I.3.1.2.
Matriks Persamaan Syndrome
Hubungan antara syndrome dan error polinomial, Si = E(αi) dapat juga dipakai untuk membuat bentuk himpunan persamaan simultan yang bisa dipakai untuk menemukan error. Persamaan error E(x) = En-1xn-1 + … + E1x + E0 ditulis ke dalam bentuk E(x) = Y1xe1 + Y2xe2 + … + Yvxev. Koefisien e1, …, ev menunjukkan lokasi error pada code word, dan Y1, …, Yv merepresentasikan m-bit nilai error pada 18
lokasi tersebut. Maka, Si = E(αi) = Y1αie1 + Y2αie2 + … + Yvαiev = Y1Xi1 + Y2Xi2 + … + YvXiv, dimana I = 0, …, 2t – 1 adalah jumlah dari akar g(x). Variabel (X1 = αe1), …, (Xv = αev) disebut sebagai error locator. Jika diekspresikan persamaan syndrome sebagai system persamaan linear 2t dimana syndrome ditulis sebagai S0, …, S2t-1 yang berkorespondensi dengan akar α0, α1, …, α2t-1 adalah pangkat dari x sebagaimana terlihat pada matriks berikut ini:
Contoh perhitungan: Pada contoh sebelumnya, error polinomial adalah E(x) = α5x10 + α12x3, dengan I = 0, …, 3. Karena Si = Y1αie1 + Y2αie2 + … + Yvαiev, maka S0 = E(α0) = Y10 + Y3, sehingga Y10 = α5 dan Y3 = α12. S1 = E(α1) = Y10αe1 + Y3αe2, sehingga e10 = 10 dan e3 = 3. Karena (X1 = αe1), …, (Xv = αev), sehingga X010 = 1, X03 = 1 untuk i = 0, X110 = α10, dan X13 = α3 untuk i = 1. Sehingga matrik syndrome menjadi:
I.3.2.
Menghitung Polinomial Error Locator
Error locator polinomial Λ(x) dengan nilai syndrome Si dipakai untuk menentukan koefisien error locator polinomial. Dengan posisi error Xi diketahui, adalah mungkin dengan menggunakan system persamaan linear 2t, ditentukan nilai errornya Yi. Ada dua bentuk polinomial error location, yaitu Λ(x) dan σ(x). Dimana σ(x) = (x + X1) (x + X2)… (x + Xv) = xv + σ1xv-1 + … + σv-1x + σv. 19
Sedangkan Λ(x) = (1 + X1x) (1 + X2x)… (1 + Xvx) = 1 + Λ1x + … + Λv-1xv-1 + Λvxv. Sehingga diperoleh hubungan:
Sehingga koefisien σ1, …, σ1 adalah sama dengan Λ1, …, Λv. Dari Λ(x) = (1 + X1x) (1 + X2x)… (1 + Xvx), kita dapat melihat ada akar Xj-1 yang berkorespondensi sehingga menghasilkan Λ(x) = 0. Juga, dengan Λ(x) = 1 + Λ1x + … + Λv-1xv-1 + Λvxv, lalu substitusikan Xj-1 untuk x, maka 0 = 1 + Λ1Xj-1 + … + Λv-1Xj1-v + ΛvXj-v. Agar kompatibel dengan persamaan syndrome, maka kalikan YjXji+1 untuk mendapatkan 0 = YjXji+v + Λ1YjXji+v-1 + … + Λv-1YjXji+1 + ΛvYjXji. Dimana Y1, …, Yv adalah nilai error, dan X1, …, Xv adalah lokasi error. Persamaan yang mirip dapat dibuat untuk semua error, yaitu untuk nilai j yang berbeda. Sehingga secara keseluruhan didapat:
Karena,
Sehingga kita dapatkan
, untuk i = 0, …, 2t-1.
Persamaan di atas adalah himpunan 2t-v persamaan simultan dan disebut key equation dengan Λ1, … , Λv adalah bilangan yang belum diketahui yang merupakan lokasi error. Dalam bentuk matriks:
Untuk menyelesaikan key equation yang diberikan pada matriks di atas, dapat dilakukan dengan beberapa algoritma, yaitu: Berlelamp-Messey algorithm, Euclidean Algorithm, Peterson-Gorenstein-Zierler algorithm. 20
I.3.2.1.
Metode Euclidean Algorithm
Metode Euclidean Algorithm digunakan untuk menyelesaikan key equation. Pada dasarnya, tujuan algoritma Euclidean adalah untuk mencari Faktor Pembagi Terbesar (FPB) atau Great Common Divisor (GCD). Algoritma Euclidean dibangun berdasarkan lemma berikut: Jika g = (a, b) maka ada bilangan integer s dan t sehingga g = (a, b) = as + bt. Untuk polynomial, jika ada g(x) = (a(x), b(x)) maka ada polynomial s(x) dan t(x) sehingga g(x) = a(x)s(x) + b(x)t(x). Contoh Perhitungan: Diketahui g = (851, 966), karena 966 = 1×851 + 115, dengan lemma di atas maka didapat g = (851, 966) = (851, 966 - 1×851) = (851, 115) = (115, 851). Sehingga tereduksi menjadi semakin kecil, kemudian 851 = 7×115 + 46, sehinnga dengan lemma tersebut didapat (115, 851) = (115, 851 - 7×115) = (115, 46) = (46, 115). Dilanjutkan kembali, 115 = 2×46 + 23 lalu (46, 115) = (46, 115 - 2×46) = (46, 23) = (23, 46) lalu 46 = 2×23 + 0 lalu (23, 46) = 23, sehingga hasil akhir algoritma Euclidean akan didapatkan (966, 851) = 23. I.3.2.2.
Modified Euclidean Algorithm
Dalam implementasinya, algoritma Euclidean diubah ke dalam bentuk yang lebih efisien dalam hal komputasinya. Misalnya dengan algoritma Modified Euclidean yang diterapkan oleh Hanho-Lee. Untuk mendapatkan nilai ω(x) dan σ(x) dari persamaan S(x) σ(x)
=
ω(x) mod x2t dapat digunakan algoritma Modified
Euclidean [1]. Berikut ini penjabaran algoritmanya: Inisialisasi, R0 = x2t, Q0 = S(x), L0 = 0, U0 = 1. Setelah iterasi ke-i, didapatkan:
21
Dimana
dan dan
adalah koefisien pada pangkat tertinggi dari polynomial . Dan,
Algoritma akan berhenti jika
, dimana
menyatakan
derajat dari polynomial. Jika kondisi stop tersebut terpenuhi, maka didapatkan ω(x) = Ri(x) dan σ(x) = Li(x). I.3.2.3.
Metode Improved Euclidean Algorithm
Implementasi Modified Euclidean memerlukan data swap, yaitu ketika koefisien didapatkan 1 atau 0. Cara lain dikembangkan oleh Xiao-Chun Li dan Jun-Fa Mao, yaitu Improved Euclidean. Algoritma masih dikembangkan dari Modified Euclidean, akan tetapi tanpa data swap, berikut flow-chartnya.
22
Gambar 5 Flow-chart Improved Euclidean
I.3.3.
Mencari Posisi Error
I.3.3.1.
Metode Chien Search
Akar dari Λ(x) yaitu X1, …, Xv adalah perbandingan terbalik dari posisi error. Untuk mencari akar-akar tersebut, dilakukan prosedur trial-and-error sederhana yang disebut Chien Search. Persamaan Λ(x) dapat ditulis kembali menjadi Λ(x) = X1(x + X1-1)X2(x + X2-1)…Xv(x + Xv-1), maka akan jelas bahwa Λ(x) akan bernilai nol jika akar-akarnya adalah x = X1-1, X2-1, .., Xv-1, yaitu ketika akar-akarnya adalah x = α-e1, α-e1, … α-ev, dimana e1, e2, …, ev mengindikasikan lokasi error yang dituliskan sebagai pangkat dari x. Untuk melakukan pencarian akar, semua elemen bilangan tidak nol pada GF(2m) di-generate terlebih dahulu yaitu, x = 1, x = α, x = α2, … , x = αn-1, lalu tiap elemen tersebut secara individu disubstitusikan ke dalam Λ(x). Untuk tiap substitusi, Λ(x) = 0 dites. Jika memenuhi, maka nilai x saat itu merupakan akar dari persamaan Λ(x), dan nilainya disimpan untuk proses selanjutnya. Nilai akar-akarnya, yaitu α-e1, α-e1, … α-ev = x = X1-1, X2-1, ..., Xv-1, merupakan kebalikan dari nilai posisi errornya.
23
Contoh perhitungan: Pada contoh sebelumnya diketahui Λ( x) = 1 + α 12 x + α 13 x 2 sehingga diperoleh: Λ (α 0 ) = 1 + α −3 + α −2 = 1 + 15 + 13 = 3, Λ (α 1 ) = 1 + α 13 + α 15 = α 13 = α −2 = 13, Λ (α 2 ) = 1 + α 14 + α 17 = α 6 = α −9 = 12, Λ (α 3 ) = 1 + α 15 + α 19 = α 4 = α −11 = 3, Λ (α 4 ) = 1 + α 16 + α 21 = 1 + α + α 6 = 15, Λ (α 5 ) = 1 + α 17 + α 23 = 1 + α 2 + α 2 + 1 = 0, Λ (α 6 ) = 1 + α 3 + α 10 = α + α 2 + α 3 = α 11 = 14, Λ (α 7 ) = 1 + α 4 + α 12 = 1 + α 2 + α 3 = 1 + α 6 = 13, Λ (α 8 ) = 1 + α 5 + α 14 = α 3 + α 5 = 14, Λ (α 9 ) = 1 + α 6 + α 16 = α 5 + α 3 + 1 = 15, Λ (α 10 ) = 1 + α 7 + α 18 = α = 2,
Λ (α 11 ) = α 2 + α 9 + α 6 = α = 2, Λ (α 12 ) = 1 + α 9 + α 22 = 0, Λ (α 13 ) = 1 + α 10 + α 24 = 1 + α 13 = α 3 + α 2 = 12, Λ (α 14 ) = 1 + α 11 + α 26 = 1 Dari persamaan di atas diketahui bahwa pada α5 dan α12 nilai Λ ( x ) adalah nol, dan lokasi error adalah inverse dari nilai-nilai akar tersebut, yaitu X1 = αe1 = α3, dan X2 = αe2 = α10. Kaena E(x) = Y1αie1 + Y2αie2 + … + Yvαiev, maka kta dapatkan E(x) = Y1x3 + Y2x10.
I.3.4.
Menghitung Error Value
Untuk menghitung error value Y1, ..., Yv dapat pada lokasi e1, ..., ev, digunakan matriks persamaan syndrome yaitu:
24
Contoh perhitungan: Pada contoh di atas, S0 = α14, S1 = 0, S2 = α12, S0 = α19. Ambil salah satu bentuk matriks,
⎡ S 0 ⎤ ⎡ X 10 ⎢S ⎥ = ⎢ 1 ⎣ 1 ⎦ ⎣ X1
X 20 ⎤ ⎡ Y1 ⎤ ⎥⎢ ⎥ X 21 ⎦ ⎣Y2 ⎦
Kita dapatkan,
1 ⎤ ⎡ Y1 ⎤ ⎡α 14 ⎤ ⎡ 1 ⎢ ⎥=⎢ 3 ⎥ 10 ⎥ ⎢ ⎣ 0 ⎦ ⎣α α ⎦ ⎣Y2 ⎦ Dari persamaan tersebut didapatkan α 14 = Y1 + Y2 dan 0 = α 3Y1 + α 10Y2 . Sehingga didapatkan Y1 = α12 dan Y2 = α5. Sehingga polinomial error value menjadi
E( x) = α 12 x3 + α 5 x10 , tepat sama dengan nilai error yang di-generate di awal. I.3.4.1.
Metode Fast Komo-Joiner Algorithm Untuk Mencari Error value
Sebuah algoritma hasil modifikasi persamaan syndrome diperkenalkan disini. Metode ini dibuat oleh Komo dan Joiner [3]. Matriks persamaan syndrome dapat dituliskan sebagai Ω( x) = [S ( x)Λ( x) mod( x2t )] , dimana S(x) adalah polinomial syndrome dan Λ ( x ) adalah polinomial error locator. Persamaan tersebut dapat dinyatakan kembali dalam:
⎡
⎤ (1 + β j βi−1 ) ⎥ , i = 1, 2,..., v ⎣ j =1, j ≠ i ⎦
γ i = Ω( βi−1 ) ⎢
v
∏
Dimana,
Λ ( x) [1 + S ( x) ] = Ω( x) mod( x 2 v +1 ), S ( x) = S1 x + S 2 x 2 + ... + St xt , Λ ( x) = (1 + β1 x)(1 + β 2 x)...(1 + β v x) = 1 + Λ1 x + ... + Λ v x v Dari persamaan di atas, Ω( x) dapat dituliskan kembali dalam [3]: Ω( x ) = 1 + ( S1 + Λ1 ) x + ( S 2 + ... + ( Sv + Λ1S v −1 + ... + Λ v −1S1 + Λ v ) x v 25
Sehingga, dengan persamaan baru tersebut, dalam implementasinya akan dibutuhkan (5v2-v) adder dan (7v2-5v)/2 multiplier. Jika lokasi error diketahui, maka nilai error dapat dicari dengan matriks berikut:
⎡ β1 ⎢β 2 ⎢ 1 ⎢ . ⎢ ⎢ . ⎢⎣ β1v
β 2 ... β v ⎤ ⎡ γ 1 ⎤ β12 ... β12 ⎥⎥ ⎢⎢γ 2 ⎥⎥
β 2v
⎡ S1 ⎤ ⎢S ⎥ ⎢ 2⎥ . ⎥⎢ . ⎥ = ⎢ . ⎥ ⎥⎢ ⎥ ⎢ ⎥ . ⎥⎢ . ⎥ ⎢ . ⎥ ... β vv ⎥⎦ ⎢⎣γ v ⎥⎦ ⎢⎣ Sv ⎥⎦
Karena matriks β adalah matriks Vandermonde, maka dengan teknik standar matriks tersebut dapat didiagonalisasi. Lalu, dengan memakai persamaan yang telah dibangun di atas dan struktur matriks Vandermonde, dapat dibuat algoritma iterative untuk menghitung nilai error sebagai berikut [3]: Algorithm 1: S v − j = S v − j − β i S v − j −1 , j = 0,..., v − i − 1; i = 1,..., v − 2
Algorithm 2: Sv =
( Sv − β v −1S v −1 ) , j = 1,..., i; i = 1,..., v − 2 ( β v − β v −1 )
Algorithm 3: Sv = Sv − i − Sv − i + j , j = 1,..., i; i = 1,..., v − 2
Algorithm 3: Sv − i =
( Sv −1 ) , j = 1,..., i; i = 1,..., v − 2 ( β v − β v −1 )
Algorithm 4: Sv −i =
( Sv −1 ) , j = 1,..., i; i = 1,..., v − 2 ( β v − i − β v − i −1 )
Algorithm 5:
26
Sv − i + j =
( Sv −1+ j ) ( β v − i + j − β v − i −1 )
, j = 1,..., i; i = 1,..., v − 2
Algorithm 6: S1 = S1 − S j +1 , j = 1,..., v − 1
Algorithm 7:
S1 =
Sj
βj
, j = 1,..., v
Dimana nilai error adalah koefisien-koefisien akhir dalam Sj. Dengan algoritma iterative ini, dalam implementasinya hanya dibutuhkan 3v(v-1)/2 adder dan v2 multiplier.
27
