Teori kode

Visualisasi dua dimensi dari jarak Hamming, ukuran dalam teori pengkodean.

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:^[1]

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.^[2] 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 $X:\Omega \to {\mathcal {X}}$ , dimana $x\in {\mathcal {X}}$ dengan probabilitas $\mathbb {P} [X=x]$ .

Data dikodekan oleh string (kata) di atas alfabet $\Sigma$ .

Kode adalah fungsi

C:{\mathcal {X}}\to \Sigma ^{*}

(atau

\Sigma ^{+}

jika pita kosong bukan bagian dari alfabet).

$C(x)$ adalah kata kode terkait dengan $x$ .

Panjang kata sandi ditulis sebagai

l(C(x)).

Panjang kode yang diharapkan adalah

l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].

Rangkaian kata kode $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$ .

Kata kode dari string kosong adalah string kosong:

C(\epsilon )=\epsilon

Sifat

$C:{\mathcal {X}}\to \Sigma ^{*}$ adalah non-singular jika injeksi.
$C:{\mathcal {X}}^{*}\to \Sigma ^{*}$ adalah dapat didekodekan secara unik jika bersifat injeksi.
$C:{\mathcal {X}}\to \Sigma ^{*}$ adalah awalan jika $C(x_{1})$ bukan awalan dari $C(x_{2})$ (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), dimana 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.^[3]

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.^{[butuh rujukan]}

Kode linear

Istilah teori pengkodean aljabar ' menunjukkan sub-bidang teori pengkodean di mana sifat kode diekspresikan dalam istilah aljabar dan kemudian diteliti lebih lanjut.^{[butuh rujukan]}

Teori pengkodean aljabar pada dasarnya dibagi menjadi dua jenis kode utama:^{[butuh rujukan]}

Kode blok linear
Kode konvolusional

Menganalisis tiga properti kode berikut, terutama:^{[butuh rujukan]}

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.^[4]

Kode blok linear diringkas dengan huruf simbolnya (misalnya, biner atau terner) dan parameter (n,m,d_min)^[5] where

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

Terdapat banyak jenis kode blok linier, seperti

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. Tetapi 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

^ James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. hlm. 18. ISBN 9780471808725. There are four types of coding
^ Nasir Ahmed. "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.
^ Todd Campbell. "Answer Geek: Error Correction Rule CDs".
^ Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama terras
^ Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama blahut

Referensi

Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
Randy Yates, A Coding Theory Tutorial.

[1] James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. hlm. 18. ISBN 9780471808725. There are four types of coding

[Ahmed-2] Nasir Ahmed. "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.

[3] Todd Campbell. "Answer Geek: Error Correction Rule CDs".

[terras-4] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama terras

[blahut-5] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama blahut

[1]

[2]

[3]

[4]

[5]

Pengawasan otoritas
Umum	Integrated Authority File (Jerman)
Perpustakaan nasional	Prancis (data) Amerika Serikat Jepang
Lain-lain	Microsoft Academic