Loading...
Teknologi

REED SOLOMON CODE

Kode Reed Solomon adalah sebuah kode yang dirumuskan oleh Irving Reed dan Gus Solomon pada tahun 1960. Kode Reed Solomon mendeskripsikan sebuah cara sistematis untuk membentuk sebuah kode yang mampu mengoreksi error yang muncul secara acak dan tak terduga ( bursty ) pada paket data yang diterima berbasiskan aritmatik Galois Field . Sebuah kode Reed Solomon ditulis dalam bentuk RS ( n,k ) dimana n adalah panjang blok atau panjang kode yang terdiri dari susunan beberapa simbol, sedangkan k adalah panjang informasi atau jumlah simbol data yang akan dikodekan. Panjang block code ini adalah n = 2 m -1, dimana m adalah jumlah bit per simbol. Jumlah simbol parity yang harus ditambahkan untuk mengkoreksi sejumlah error t adalah n – k = 2 t .

Elemen Kode Reed Solomon
Elemen Kode Reed Solomon

Elemen Galois Field

Sebuah elemen galois field terdiri dari sekumpulan elemen primitif, biasanya dinotasikan oleh α, dan bernilai :


capture-8(1)

untuk membentuk sebuah set dari elemen 2m, dimana n = 2m-1. Field ini dikenal sebagai GF (2m). Nilai dari α biasanya dipilih bernilai 2, meskipun nilai lain dapat digunakan. Setelah memilih α, pangkat yang lebih tinggi dapat kemudian diperoleh dengan mengalikan α ditiap langkah.

Tiap elemen field yang ditunjukkan pada persamaan (1) dapat direpresentasikan dalam bentuk polinomial:

capture-9(2)

dimana koefisien dari αm-1 sampai α0 mengambil nilai 1 atau 0. Misalnya untuk m = 8 mempunyai persamaan polinomial elemen galois filed :

capture-10(3)

dengan α7,…, α0 memiliki nilai biner 00000000 – 11111111 atau setara dengan nilai desimal 0 – 256.

Aritmatik dalam elemen galois field memiliki proses penjumlahan, pengurangan, perkalian, dan pembagian yang bebeda dengan operasi pada bilangan integer. Ketika dilakukan penjumlahan antara dua elemen field, berarti dilakukan penjumlahan antara dua buah polinomial :

capture-11(4)

dimana ci = αi + bi untuk 0≤ i ≤ m-1. Koefisien hanya dapat bernilai 0 dan 1 sehingga :

ci = 0 untuk αi = bi dan ci = 1 untuk αi ≠ bi (5)

Berdasarkan persamaan (5) maka diketahui bahwa penjumlahan dua elemen galois field menggunakan penjumlahan modulo 2 atau jika dalam bentuk biner maka disebut penjumlahan EX-OR dimana ketika 2 elemen yang identik dijumlahkan maka hasilnya 0. Untuk pengurangan dua elemen galois field memiliki prinsip pengoperasian yang sama dengan penjumlahan, sehingga tanda minus dapat diganti dengan tanda plus dalam aritmatika elemen field ini.

Misalnya : 13 + 3 = 1101 XOR 0011 = 1110 = 14.

Sedangkan untuk operasi perkalian dan pembagian dalam galois field merupakan operasi perkalian/ pembagian modulo dalam bentuk indeks.

Misalnya : capture-12

13 / 3 = α13 / α4 = α9 = 10

  1. Polynomial Generator Field

Polinomial generator field sering juga disebut polinomial primitif, p(x), dengan pangkat m. Polinomial ini terbentuk dari proses perkalian dua elemen field secara bersamaan. Untuk galois field dengan ukuran tertentu, memiliki bentuk polinomial yang secara umum sudah sering digunakan.

Tabel 1. Bentuk Polinomial Primitif dari Nilai m Tertentu.

Capture-13.JPG

Polinomial primitif yang digunakan untuk GF(256) adalah :

Capture-14.JPG(6)

capture-15(7)

Pembentukan Galois Field (GF)

Tabel 2. Nilai Elemen – Elemen Field Untuk GF(16).

Bentuk index

Bentuk polinomial

Bentuk biner

Bentuk desimal

0

0

0000

0

α0

1

0001

1

α 1

Capture-16.JPG

0010

2

α 2

Capture-17.JPG

0100

4

α 3

Capture-18.JPG

1000

8

α 4

Capture-19.JPG

0011

3

α 5

Capture-20.JPG

0110

6

α 6

Capture-21.JPG

1100

12

α 7

Capture-22.JPG

1011

11

α 8

Capture-23.JPG

0101

5

α 9

Capture-24.JPG

1010

10

α 10

Capture-25.JPG

0111

7

α 11

Capture-26.JPG

1110

14

α 12

Capture-27.JPG

1111

15

α 13

Capture-28.JPG

1101

13

α 14

Capture-29.JPG

1001

9

Tabel 3. Nilai Elemen – Elemen Field Untuk GF(256).

Bentuk indeks

Bentuk polynomial

Bentuk biner

Bentuk desimal

0

0

00000000

0

α0

Capture-30.JPG

00000001

1

α1

Capture-31.JPG

00000010

2

α2

Capture-32.JPG

00000100

4

α3

Capture-33.JPG

00001000

8

α4

Capture-34.JPG

00010000

16

α5

Capture-35.JPG

00100000

32

α6

Capture-36.JPG

01000000

64

α7

Capture-37.JPG

10000000

128

α8

Capture-38.JPG

00011101

29

α9

Capture-39.JPG

00111010

58

α254

Capture-40.JPG

10001110

142

Tabel 2 dan tabel 3 menunjukkan nilai dari elemen field untuk GF(2m) dalam bentuk indeks, polinomial, biner, dan desimal. Berdasarkan tabel 2 dan 3, tiap tahap pembentukan polynomial selalu dikalikan dengan ‘x’, sedangkan untuk pembentukan bilangan biner mewakili nilai-nilai koefisien polynomial. Untuk α8 memiliki bentuk polynomial berdasarkan persamaan (7)

Pembentukan Polynomial Generator Code

Nilai dari simbol pesan dan parity dari sebuah kode Reed Solomon merupakan elemen – elemen dari Galois Field. Sehingga untuk sebuah kode yang didasarkan pada jumlah simbol m-bit, Galois Field memiliki 2m elemen.

Sebuah kode Reed Solomon (n,k) diperoleh dengan membentuk polynomial generator code, g(x), yang mengandung faktor n-k = 2t, akar dari elemen berurutan pada Galois Field. Memilih elemen berurutan memastikan bahwa jarak dari kode dimaksimalkan. Sehingga bentuk umum dari persamaan polynomial generator code adalah:

Capture-41.JPG(8)

Dengan mengacu pada persamaan (8), maka polynomial generator code untuk Reed Solomon (255,239) adalah :

Capture-44.JPG

Ketika dikalikan maka menghasilkan polynomial generator code :

Capture-42.JPG

Dengan cara yang sama, polynomial generator code untuk RS(15,11) adalah :

Capture-43.JPG

Proses Pengkodean Reed Solomon

Hasil dari encoding reed solomon akan memberikan 2t byte yang merupakan sejumlah simbol yang akan diletakkan di belakang data yang telah diencode, disebut dengan codeword, dan di transmisikan oleh transmitter. Di bagian penerima, codeword ini akan memungkinkan decoder untuk melakukan fungsi deteksi dan koreksi error.

Contoh encoding sederhana akan ditunjukkan pada encoding RS(15,11) berikut. Misalkan terdapat 11 byte data yang akan dikodekan dengan menggunakan RS(15,11). Data tersebut setelah diubah dalam bentuk desimal menjadi 1,2,3,4,5,6,7,8,9,10,11. Data tersebut direpresentasikan dalam bentuk polinomial menjadi :

Capture-45.JPG

Data polinomial ini kemudian dikalikan dengan x2t, dimana 2t = 4 sehingga data polinomial dikalikan dengan x4. Hal ini dilakukan untuk menyediakan tempat bagi codeword yang akan diletakkan di belakang data. Hasil perkaliannya adalah :

Capture-46.JPG

Polinomial ini kemudian dibagi dengan polinomial dari kode generator yaitu Capture-47.JPG sehingga menghasilkan 4 codeword.

Pembagian dapat dilakukan dengan metode pipeline, dimana perhitungan data secara pipeline ini biasa dioperasikan pada perangkat keras encoder berupa rangkaian konvensional yang biasa disebut Linear Feedback Shift Register (LFSR). Berikut operasi encoding Reed Solomon dengan perhitungan pipeline :

Capture-48.JPG

Pada metode pipelined data pertama bernilai 1, dijumlahkan pada nilai awal 0 (koefisien x14) digunakan sebagai pengali polinomial field generator. Selanjutnya hasil perkalian dijumlahkan ke 4 keofisien polinomial berurutan lainnya. Demikian seterusnya. Di bagian akhir diperoleh 4 simbol yaitu 3, 3, 12, 12, inilah yang disebut dengan codeword yang nantinya ditempatkan di belakang data yang dikodekan, yaitu menjadi 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 3, 3, 12, 12.

Tinggalkan Balasan