Algebraic Geometry Codes

Sebagai Perluasan dari Kode Reed Solomon

OUTLINE

• Teori Koding​
• Algebraic Geometry
• Contoh

Teori Koding

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi nec metus justo. Aliquam erat volutpat.

time : 1-2 minutes

Teori Kode

Definisi

Kode $\cal{C}$ adalah subhimpunan dari $F_q^n$.

Definisi

Kode linear adalah subruang dari $F_q^n$.

Definisi

Kode $\cal{C}^{\perp}$ adalah subruang dari $F_q^n$ yang orthogonal dengan $\cal{C}$.

Definisi

Kata kode adalah anggota dari kode.

Matriks

Definisi

Matriks pembangun adalah matriks yang baris-barisnya merupakan basis bagi kode $\cal{C}$.

Definisi

Matriks paritas dari kode $\cal{C}$ adalah matriks pembangun dari kode $\cal{C}^{\perp}$.

Bobot

Definisi

Bobot Hamming dari suatu kata kode adalah banyaknya elemen tak nol dari kata kode tersebut.

Bobot dari kata kode $x$ dilambangkan dengan $w(x)$.

Definisi

Jarak Hamming dari dua kata kode adalah banyaknya posisi dimana kedua kata kode berbeda.

Jarak dua kata kode $x$ dan $y$ dilambangkan dengan $d(x,y)$. Jarak minimum di $\cal{C}$ dinotasikan dengan $d$.

Definisi

Dimensi dari kode $\cal{C}$ adalah dimensi $\cal{C}$ sebagai ruang vektor atas $F_q^n$.

Encoding-Decoding

Definisi

Encoding adalah suatu pemetaan dari pesan ke himpunan kode.

Salah satu encoding adalah pemetaan berikut: $$f:A \rightarrow \cal{C}$$ $$\quad x \mapsto xG$$

dengan $G$ adalah matriks pembangun.

Pengecekan Eror

Suatu vektor $x$ adalah kata kode di $\cal{C}$ jika $Hx = 0$ untuk suatu matriks paritas $H$.

Encoding-Decoding

Encoding-Decoding

Definisi

Decoding adalah suatu algoritma untuk mengubah vektor menjadi pesan

Jika diberikan suatu $a \in F_q^n$ dengan jaminan bahwa $a=c+e$ untuk suatu $c \in \cal{C}$ dan suatu $e \in F_q^n$ dengan $w(e) \le \frac{d-1}2$, maka selalu bisa didapatkan pesan yang sebenarnya.

Batas-batas

Suatu kode $C \in F_q^n$ dengan panjang $n$, berdimensi $k$ dan jarak minimum $d$, disebut kode $[n,k,d]$.

Efektif dan Efisien ​

Bagaimana $d$ terhadap $n$?

Bagaimana $k$ terhadap $n$?

Batas-batas

Teorema Batas Singleton

Untuk semua kode linear $C[n,k,d]$ berlaku $$d+k \leq n+1$$

Bukti

Kode Reed-Solomon

Misalkan $n = q-1$ dan $\mathbb{F}_q^n$ dan $k \leq n$.

Definisikan

$$L_k = \{ f \in \mathbb{F}_q^n \mid deg\left(f\right) \leq q-1\}$$

Definisikan kode Reed-Solomon sebagai

$${\cal{C}_{RS}} = \{ f(x) \mid f \in L_k,x\in \mathbb{F}_q^n \}$$

Klaim

Kode $\cal{C}_{RS}$ adalah kode $[n,k,n-k+1]$.

Kode Reed-Solomon

Bukti

• ​​Fungsi $f : L_k \rightarrow \cal{C}_{RS}$ adalah pemetaan injektif
• Polinom berderajat $k-1$ mempunyai akar tidak lebih dari $k-1$ sehingga $$d \ge n-(k-1)$$
• Dengan batas singleton, bisa disimpukan bahwa $$d \le n-k+1$$