Teori kode

Teori kode atau Teori pengkodean adalah studi tentang sifat kode dan kesesuaian untuk aplikasi tertentu. Kode digunakan untuk kompresi data, kriptografi, deteksi dan koreksi kesalahan, transmisi data dan penyimpanan data. Kode dipelajari oleh berbagai disiplin ilmu: seperti teori informasi, teknik listrik, matematika, linguistik, dan ilmu komputer untuk tujuan merancang metode transmisi data yang efisien dan andal. Penghapusan redundansi dan koreksi atau deteksi kesalahan dalam data yang dikirimkan.

Terdapat empat jenis pengkodean:

 Kompresi data (atau pengkodean sumber)
 Kontrol kesalahan (atau pengkodean saluran)
 Pengodean kriptografi
 Pengkodean baris

Kompresi data mencoba menghilangkan redundansi dari data dari sumber untuk mengirimkannya lebih efisien. Misalnya, kompresi data ZIP membuat file data lebih kecil, untuk tujuan seperti untuk mengurangi lalu lintas Internet. Kompresi data dan koreksi kesalahan dapat dipelajari dalam kombinasi.

Koreksi kesalahan menambahkan bit data ekstra untuk membuat transmisi data lebih kuat terhadap gangguan yang ada pada saluran transmisi. Pengguna biasa tidak mengetahui banyak aplikasi yang menggunakan koreksi kesalahan. CD musik (CD) menggunakan kode Reed-Solomon untuk mengoreksi goresan dan debu. Dalam aplikasi ini saluran transmisinya adalah CD. Ponsel juga menggunakan teknik pengkodean untuk mengoreksi fading dan kebisingan transmisi radio frekuensi tinggi. Modem data, transmisi telepon, dan NASA Deep Space Network seluruhnya menggunakan teknik pengkodean saluran untuk mendapatkan bit, misalnya kode turbo dan kode LDPC.

 Sejarah teori pengkodean 
Pada tahun 1948, Claude Shannon menerbitkan "A Mathematical Theory of Communication" sebuah artikel dalam dua bagian dalam edisi Juli dan Oktober dari Bell System Technical Journal. Pekerjaan ini berfokus pada masalah tentang informasi yang dikirim oleh pengirim. Dalam pekerjaan mendasar, ia menggunakan alat dalam teori probabilitas, yang dikembangkan oleh Norbert Wiener, yang sedang dalam tahap awal untuk diterapkan pada teori komunikasi pada saat itu. Shannon mengembangkan entropi informasi sebagai ukuran untuk ketidakpastian dalam pesan sementara pada dasarnya menciptakan bidang teori informasi.

Kode biner Golay ditemukan pada tahun 1949. Kode ini adalah kode koreksi kesalahan yang mengoreksi hingga tiga kesalahan dalam setiap kata 24-bit, dan mendeteksi kesalahan keempat.

Richard Hamming memenangkan Turing Award pada tahun 1968 untuk karyanya di Bell Labs dalam metode numerik, sistem pengkodean otomatis, dan pendeteksi kesalahan dan kode koreksi kesalahan. Dia menemukan konsep yang dikenal sebagai kode Hamming, jendela Hamming, bilangan Hamming, dan jarak Hamming.

Pada tahun 1972, Nasir Ahmed mengusulkan transformasi kosinus diskrit (DCT), yang ia kembangkan bersama T. Natarajan dan K. R. Rao pada tahun 1973. DCT adalah algoritma kompresi Lossy yang paling banyak digunakan, dasar untuk format multimedia seperti JPEG, MPEG dan MP3.

 Sumber kode 

Tujuan sumber pengkodean adalah untuk mengambil data sumber dan membuatnya lebih kecil.

 Definisi 
Data dapat dilihat sebagai variabel acak , di mana  dengan probabilitas .

Data dikodekan oleh string (kata) di atas alfabet .

Kode adalah fungsi

 (atau  jika pita kosong bukan bagian dari alfabet).

 adalah kata kode terkait dengan .

Panjang kata sandi ditulis sebagai

Panjang kode yang diharapkan adalah

Rangkaian kata kode .

Kata kode dari string kosong adalah string kosong:

 Sifat 
  adalah non-singular jika injeksi.
  adalah dapat didekodekan secara unik jika bersifat injeksi.
  adalah awalan jika  bukan awalan dari  (dan sebaliknya).

 Prinsip 
Entropi dari suatu sumber adalah ukuran informasi. Pada dasarnya, kode sumber mencoba mengurangi redundansi yang ada di sumber, dan mewakili sumber dengan bit lebih sedikit yang membawa lebih banyak informasi.

Kompresi data yang secara eksplisit mencoba meminimalkan panjang rata-rata sesuai dengan model probabilitas yang diasumsikan tertentu disebut pengkodean entropi.

Berbagai teknik yang digunakan oleh skema pengkodean sumber mencoba untuk mencapai batas entropi sumber. C(x) ≥ H(x), di mana H(x) adalah entropi sumber (bitrate), dan C(x) adalah bitrate setelah kompresi. Secara khusus, tidak ada skema pengkodean sumber yang lebih baik daripada entropi sumber.

 Contoh 
Faksimili transmisi menggunakan kode panjang proses. Pengkodean sumber menghilangkan semua data yang berlebihan untuk kebutuhan pemancar, mengurangi bandwidth yang diperlukan untuk transmisi.

 Pengkodean saluran 

Tujuan dari teori pengkodean saluran adalah untuk menemukan kode yang mengirimkan dengan cepat, berisi banyak kata kode yang valid dan dapat memperbaiki atau setidaknya mendeteksi banyak kesalahan. Meskipun tidak eksklusif satu sama lain, kinerja di bidang ini merupakan trade off. Jadi, kode yang berbeda optimal untuk aplikasi yang berbeda. Sifat yang diperlukan dari kode ini terutama bergantung pada kemungkinan kesalahan yang terjadi selama transmisi. Pada CD biasa, kerusakan utamanya adalah debu atau goresan.

CD menggunakan penyandian silang Reed-Solomon untuk menyebarkan data ke luar disk.Todd Campbell.
"Answer Geek: Error Correction Rule CDs".

Meskipun bukan kode yang sangat bagus, kode berulang sederhana dapat berfungsi sebagai contoh yang dapat dimengerti. Misalkan kita mengambil satu blok bit data (mewakili suara) dan mengirimkannya tiga kali. Memeriksa tiga pengulangan sedikit demi sedikit dan mengambil suara mayoritas. Hal yang menarik dari hal ini adalah kita tidak hanya mengirim bit secara berurutan. Blok bit data pertama-tama dibagi menjadi 4 blok yang lebih kecil. Kemudian kami menggilir blok dan mengirim satu bit dari yang pertama, lalu yang kedua, dll. Hal ini dilakukan tiga kali untuk menyebarkan data ke seluruh permukaan disk. Dalam konteks kode sederhana, ini mungkin tampak tidak efektif. Namun, kode yang dikenal sangat efektif untuk mengoreksi kesalahan dari goresan atau titik debu saat teknik interleaving ini digunakan.

 Kode linear 

Istilah teori pengkodean aljabar ''' menunjukkan sub-bidang teori pengkodean di mana sifat kode diekspresikan dalam istilah aljabar dan kemudian diteliti lebih lanjut.

Teori pengkodean aljabar pada dasarnya dibagi menjadi dua jenis kode utama:

 Kode blok linear
 Kode konvolusional

Menganalisis tiga properti kode berikut, terutama:

 Panjang kata kode
 Jumlah total kata kode yang valid
 Minimum jarak antara dua kata kode valid, terutama menggunakan jarak Hamming, terkadang juga jarak lain seperti jarak Lee

 Kode blok linear 

Kode blok linear memiliki sifat linieritas, yaitu jumlah dari dua codeword juga merupakan kata kode, dan mereka diterapkan ke bit sumber dalam blok, maka nama kode blok linear.

Kode blok linear diringkas dengan huruf simbolnya (misalnya, biner atau terner) dan parameter (n,m,dmin) where

 n adalah panjang kata sandi, dalam simbol,
 m adalah jumlah simbol sumber yang akan digunakan untuk pengkodean sekaligus,
 dmin adalah jarak hamming minimum untuk kode.

Terdapat banyak jenis kode blok linier, seperti

 Kode siklik (misalnya, kode Hamming)
 Kode pengulangan
 Kode paritas
 Kode polinomial (misalnya, kode BCH)
 Kode Reed–Solomon
 Kode geometris aljabar
 Kode Reed-Muller
 Kode sempurna

Kode blok terkait dengan masalah pengepakan bola, yang telah mendapat perhatian selama bertahun-tahun. Dalam dua dimensi, mudah untuk divisualisasikan. Hasilnya adalah pola segi enam seperti sarang lebah. Namun, kode blok mengandalkan lebih banyak dimensi yang tidak dapat dengan mudah divisualisasikan. [24,12) kode Golay yang kuat yang digunakan dalam komunikasi angkasa menggunakan 24 dimensi. Jika digunakan sebagai kode biner (yang biasanya) dimensi mengacu pada panjang kata sandi seperti yang didefinisikan di atas.

 Catatan 

 Referensi 
 Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), .
 MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. 
 Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., .
 Randy Yates, A Coding Theory Tutorial''.


Kategori:Deteksi dan koreksi kesalahan