reed solomon code
TRANSCRIPT
REED SOLOMON CODE
Anditya Arifianto
213110008
Video
Suara
Text
Gambar
INTRODUCTION TO INFORMATION CODING
Bit 0 dan 1
Digital ErrorBit 0 menjadi 1
Bit 1 menjadi 0
teknik encoding informasi: teknik yang mengorganisir bit 0
dan 1 sehingga kesalahan yang mungkin terjadi dapat
dideteksi dan diperbaiki
Oleh Irving Reed dan Gustave Solomon pada tahun
1960
Bekerja dengan menambahkan informasi tambahan
(redundansi data) di dalam data asli
Systematic linear block code
Nonbinary ciclic code
Banyak digunakan untuk coding Compact Disc
REED SOLOMON CODE
Notasi : RS(n,k)
k : jumlah simbol data
n : panjang simbol codeword
2t : panjang simbol parity
Tiap simbol dikodekan sebanyak m-bit, maka
panjang codeword yang dapat dibentuk adalah
n = 2m-1
ARCHITECTURE
ARCHITECTURE
Kemampuan RS-Code
Deteksi dan koreksi hingga sebanyak t error
2t = n-k t = (n-k)/2 simbol error
Misal
m = 8 bit
n = 255, k = 223 simbol
2t = n-k = 32, t = 16
Bilangan prima p GF(p), p elemen
GF(p) pm elemen extension field
of GF(p)
GF(pm), m = bilangan bulat positif > 0
Reed-Solomon Code : GF(2m)
{0,a0,a1,a2,…,a2m+2}
GALOIS FIELD
Mendefinisikan finite field GF(2m)
Polinom f(x) berderajad m yang tidak bisa
direduksi dikatakan primitif jika untuk
bilangan positif terkecil n yang membagi
habis f(x) terhadap xn+1 adalah n = 2m-1
1 + x + x4
1 + x + x2 + x3 + x4
m= 4, n = 2m-1 = 15 x15+1
PRIMITIVE POLYNOMIAL
LIST OF PRIMITIVE POLYNOMIALS
m = 3 GF(23) = GF(8)
f(X) = 1 + X + X3 = 0
X a
f(a) = 01 + a + a3 = 0
a3 = -1-a a3 = 1+ a
a4 = a.a3 = a.(1+a) = a+a2,
a5 = a.a4 = a.(a+a2) = a2+a3 = 1+a+a2
a6 = a.a5 = a.(1+a+a2) = a+a2+a3 = 1+a2
a7 = a.a6 = a.(1+a2) = a+a3 = 1 = a0
GF(23) = {0,a0,a1,a2,a3,a4,a5,a6}
THE EXTENSION FIELD GF(23)
THE EXTENSION FIELD GF(23)
X0 X1 X2
0 0 0 0
a0 1 0 0
a1 0 1 0
a2 0 0 1
a3 1 1 0
a4 0 1 1
a5 1 1 1
a6 1 0 1
a7 1 0 0
THE EXTENSION FIELD GF(23)
a+a = a-a = 0, a.a = a
RS(n,k)
n = 2m-1 dan k = n-2t = 2m-1-2t,
(n,k) = (2m-1,2m-1-2t)
g(X) = (X - a)(X – a2) … (X – a2t)
RS(7,3) n=7,k=3, n-k=4
RSC ENCODING : GENERATOR
Polinon quotient q(x), polinom parity p(x) polinom
pesan (message) m(x)
Secara sistematik
Geser ke kanan m(x) sebanyak n-k hingga ke sisi
paling kanan kodeword, lalu tambahkan p(x) untuk
mengisi sisi paling kiri dari codeword
Xn-k.m(X) = q(X).g(X) + p(X)
p(X) = Xn-k.m(X) mod g(X)
Polinom Codeword
U(X) = p(X) + Xn-k.m(X)
RSC ENCODING : QUOTIENT - PARITY
RS(7,3), GF(23)
Pesan = 010110111
m(X) = a1 + a3X + a5X2
Xn-k = X4
Xn-km(X) = a1X4 + a3X5 + a5x6
g(X) = a3 + a1X + a0X2 + a3X3 + X4
p(X) = Xn-k.m(X) mod g(X)
p(X) = a0 + a2X + a4X2 + a6X3
Codeword
U(X) = a0 + a2X + a4X2 + a6X3 + a1X4 + a3X5 + a5X6
RSC ENCODING : EXAMPLE
a1 a3 a5
RSC ENCODING : EXAMPLE
U(X) = a0 + a2X + a4X2 + a6X3 + a1X4 + a3X5 + a5X6
U(X) = (100) + (001) X + (011)X2 + (101)X3 +
(010)X4 + (110)X5 + (111)X6
Codeword : 100001011101010110111
Error pattern
Received pattern
r(X) = U(X) + e(X)
RSC DECODING : ERROR - RECEIVED
RSC DECODING : ERROR - RECEIVED
Codeword sent : 100001011101010110111
Codeword received : 100001011100101110111
r(X) = (100) + (001) X + (011)X2 + (100)X3 + (101)X4 +
(110)X5 + (111)X6
r(X) = a0 + a2 X + a4X2 + a0X3 + a6X4 + a3X5 + a5X6
Parity check pada r(X) untuk memastikan r(X) valid
r(X) valid syndrome bernilai 0
Terbentuk dari n-k simbol
{ Si }, i = 1..n-k
Si substitusi X dengan ai, i = 1…n-k
RSC DECODING : SYNDROME
RSC DECODING : SYNDROME
r(X) = a0 + a2 X + a4X2 + a0X3 + a6X4 + a3X5 + a5X6
RS(7,3) n = 7, k = 3
{ Si }, i = 1..n-k = 1..4
S1 = r(a) = a0 + a3 + a6 + a3 + a10 + a8 + a11 = a3
S2 = r(a2) = a0 + a4 + a8 + a6 + a14 + a13 + a17 = a5
S3 = r(a3) = a0 + a5 + a10 + a9 + a18 + a18 + a23 = a6
S4 = r(a4) = a0 + a6 + a12 + a12 + a22 + a23 + a29 = 0
∑Si ≠ 0 codeword mengandung error
Misal terdapat sejumlah v error pada posisi
Xj1 Xj2,…Xjv
Maka polinom error :
Bl = ajl , subtitusikan ai pada r(X) untuk i = 1..2t
RSC DECODING : ERROR PATTERN
Polinom Error Locator L(X) atau (X)
L(X) = 1 + L1X + L2X2 + … + LvX
v
L(X) = (1+B1X) (1+B2X) … (1+BvX)
Akar dari L(X) = 1/B1, 1/B2, … 1/Bv
Kebalikan dari akar L(X) adalah nomor lokasi error
dari error pattern e(X), maka menggunakan teknik
autoregresif modeling kita dapatkan
RSC DECODING : ERROR LOCATOR
RSC DECODING : ERROR LOCATOR
Dari contoh
Penyelesaian koefisien L1 dan L2
Inv[A] = cofactor[A]/det[A]
RSC DECODING : ERROR LOCATOR
Sehingga kita dapatkan polinom L(X)
RSC DECODING : ERROR LOCATOR
Akar dari L(X) adalah posisi error pada r(X)
cara paling brute force : coba subtitusi masing2 elemen
GF pada L(X), jika L(X) bernilai 0, maka elemen
tersebut adalah akar dari L(X) lokasi error
RSC DECODING : ERROR LOCATOR
Didapat akar L(X)
1/B1 = a3 B1 = 1/a3 B1 = a4
1/B2 = a4 B2 = 1/a4 B2 = a3
Subtitusi akar L(X) ke Syndrome manapun
Sehingga bisa kita tuliskan matrix persamaan
RSC DECODING : ERROR VALUE
RSC DECODING : ERROR VALUE
Hitung e1 dan e2
Sehingga kita dapat
Hitung
Kemudian kita dapatkan
RSC DECODING : ERROR CORRECTING
RSC DECODING : ERROR CORRECTING
Sehingga untuk
U(X) = (100) + (001) X + (011)X2 + (101)X3 + (010)X4 +
(110)X5 + (111)X6
r(X) = (100) + (001) X + (011)X2 + (100)X3 + (101)X4 +
(110)X5 + (111)X6
ê(X) = (000) + (000) X + (000)X2 + (001)X3 + (111)X4 +
(000)X5 + (000)X6
Kita dapatkan
Û(X) = (100) + (001) X + (011)X2 + (101)X3 + (010)X4 +
(110)X5 + (111)X6
Hasil corrected code
Û(X) = (100) + (001) X + (011)X2 + (101)X3 + (010)X4 +
(110)X5 + (111)X6
Karena symbol pesan mengkonstitusikan rightmost
k=3 simbol,
maka pesan yang didekodekan =
a1 a3 a5 = 010 110 111
RSC DECODING : DECODED SYMBOL
TERIMA KASIH