Teori Pengodean Esensial [pdf]

• Buku ini merangkum secara komprehensif konsep inti teori pengodean dan perkembangan modernnya
• Membahas prinsip dasar kode koreksi kesalahan, struktur dan keterbatasan berbagai kode, serta bidang penerapan nyatanya
• Menjelaskan secara mendalam kode-kode yang digunakan luas di dunia nyata, termasuk teori Shannon dan kode Hamming serta Reed-Solomon
• Juga menyajikan secara sistematis contoh penerapan pada sistem TI modern seperti hashing, group testing, dan perlindungan biometrik
• Disusun sebagai referensi yang efektif bagi pembelajar maupun praktisi, lengkap dengan lampiran, soal latihan, dan daftar pustaka

---

Kata Pengantar

• Buku ini didasarkan pada catatan kuliah teori pengodean oleh Venkatesan Guruswami, Atri Rudra, dan Madhu Sudan
• Berdasarkan materi kuliah yang disampaikan di University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT, dan lainnya
• Didukung oleh NSF CAREER grant CCF-0844796
• Pandangan dan hasil para penulis tidak merepresentasikan posisi resmi NSF
• Tersedia di bawah lisensi Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License

Ringkasan Daftar Isi

Bab 1: Pertanyaan Mendasar

• Tujuan teori pengodean, definisi dasar dan kode
• Koreksi kesalahan dan konsep jarak pada kode, kode Hamming, serta batas-batasnya
• Klasifikasi keluarga kode, beserta soal latihan dan referensi

Bagian I: Dasar-Dasar

• Pengenalan struktur matematis seperti kode linear, medan hingga, dan ruang vektor
• Penjelasan tentang decoding efisien untuk kode Hamming dan kode dual
• Termasuk soal latihan dan referensi

Bab 3: Probabilitas dan Fungsi Entropi q-ary

• Dasar-dasar teori probabilitas, metode probabilistik, dan pemahaman fungsi entropi q-ary
• Menyediakan soal latihan dan daftar pustaka terkait

Bagian II: Kombinatorika

• Menjelaskan batas kode dan keterbatasan seperti Hamming, Gilbert-Varshamov, Singleton, Plotkin, dan lainnya
• Kode Reed-Solomon, polinomial, dan penerapan medan hingga
• Model derau Shannon dan batas transmisi informasi, serta perbandingannya dengan Hamming
• Perluasan seperti list decoding, Johnson Bound, dan kapasitas list decoding
• Teori batas baru seperti Elias-Bassalygo dan linear programming bound

Bagian III: Beragam Struktur Kode

• Kode berbasis polinomial dan penerapan pada medan biner, serta struktur kode umum
• Penggabungan kode (concatenation), Zyablov Bound, teknik penggabungan lanjutan, dan ringkasan
• Graf expander dan kode expander, amplifikasi jarak, serta contoh penerapannya

Bagian IV: Algoritme

• Metode decoding efisien untuk Reed-Solomon, Reed-Muller, dan kode gabungan
• Metode untuk mencapai kapasitas kanal BSCp serta struktur kode internal/eksternal
• Kode Polar, prinsip polarization, implementasi encoder/decoder, serta kemampuan list decoding
• Penjelasan tentang pengodean waktu linear dan kode dengan pemulihan lokal

Bagian V: Aplikasi

• Teori hashing dan pencegahan tabrakan, fungsi hash hampir universal, dan proof of data possession
• Konsep Fuzzy Vault untuk melindungi autentikasi biometrik (sidik jari)
• Formalisasi group testing, batas-batasnya, dan penerapan pada algoritme data stream
• Kompleksitas masalah pengodean: nearest codeword problem, decoding berbasis pra-pemrosesan, aproksimasi, minimum distance problem, dan lainnya
• Topik pendukung kompleksitas komputasi seperti communication complexity, randomization, pseudorandomness, hardcore predicates, dan average-case hardness

Lampiran

• Tabel notasi, pertidaksamaan dan persamaan yang berguna, notasi asimtotik, serta latar dasar algoritme dan kompleksitas
• Algoritme aljabar, pengenalan medan hingga, dan operasi polinomial
• Konsep utama teori informasi: entropi, entropi kondisional, mutual information, dan lainnya

Karakteristik dan Nilai Guna

• Memberikan secara komprehensif latar belakang teoretis dan cara penerapan praktis algoritme koreksi kesalahan yang esensial dalam komunikasi informasi modern, penyimpanan data, dan sistem kriptografi
• Merangkum dari konsep dasar hingga tren terbaru dan aplikasi nyata, sehingga menyampaikan pengetahuan yang luas bagi pengembang pemula, peneliti, dan praktisi TI
• Setiap bab dilengkapi soal latihan dan referensi sehingga mendukung pembelajaran dan belajar mandiri
• Dapat dimanfaatkan secara bebas untuk tujuan akademik/nonkomersial sesuai lisensi Creative Commons

[GN⁺]

Komentar Hacker News

• Saya ingin menekankan bahwa "The Mathematical Theory of Communication" karya Claude Shannon adalah dokumen dasar teori informasi yang dijelaskan dengan cukup mudah sehingga bisa dibaca siapa saja meski tidak punya latar belakang matematika yang mendalam tautan

  • Saya juga ingin mengatakan bahwa Shannon adalah sosok yang sangat baik untuk mulai mempelajari cara berpikir matematis. Awalnya ia menurunkan konsep entropi informasi tanpa makna khusus, hanya berdasarkan sifat-sifat yang dibutuhkan. Yang mengejutkan, definisi yang tercipta hampir secara kebetulan ini ternyata sangat selaras dengan entropi termodinamika dalam fisika, dan Von Neumann-lah yang menunjukkannya lalu memberinya nama. Matematika sering berkembang lewat alur logis seperti, "jika harus memenuhi aturan-aturan ini," dan itu salah satu alasan banyak orang merasa bidang ini sulit. Makalah Shannon hanya membangun kerangka teori pengodean, dan implementasi nyatanya tidak ada di dalam makalah tersebut. Saya pernah menjalankan klub buku di startup lama saya untuk membaca versi buku dari makalah ini bersama-sama, dan saya sangat merekomendasikannya sebagai pengalaman yang bagus untuk memahami teori informasi dan matematika secara umum

• Menarik juga kalau ditambahkan lebih banyak tentang hubungan erat antara kompresi lossless dan AI generatif. Saya ingin merekomendasikan disertasi PhD yang memperkenalkan hubungan antara kompresi lossless dan machine learning dengan sangat baik tautan

  • Sebenarnya ini juga tidak perlu dibatasi hanya pada kompresi lossless. Hampir semua machine learning pada dasarnya bisa dipahami sebagai bentuk kompresi tertentu, terutama kompresi lossy. Misalnya, jika hanya embedding semantik yang dikirim lewat suatu kanal, pekerjaan tetap bisa dilakukan tanpa keseluruhan teks asli karena nilai embedding itu sudah memuat informasi yang cukup. Klasifikasi data pada akhirnya juga merupakan proses membuang hal-hal selain representasi laten dari kategori umum data tersebut. Dalam kasus AI generatif, justru karena kita melakukan 'kompresi lossy' sistem ini bekerja dengan baik. Kita sengaja membuang sebagian informasi, dan dengan harus menyimpulkan celah itu, jalur menuju generalisasi pun terbuka. LLM lossless pada praktiknya tidak terlalu menarik dari sisi kegunaan nyata. Namun, makalah yang saya rekomendasikan sangat istimewa karena termasuk langka di bidang machine learning dalam membahas kompresi lossless

• Ada juga materi bagus yang dibuat belakangan ini, yaitu buku ajar <i>Information Theory: From Coding to Learning</i>. Tersedia versi PDF online juga, jadi layak dijadikan referensi tautan

  • Saya juga ingin merekomendasikan <i>Information Theory, Inference, and Learning Algorithms</i> karya David MacKay tautan

• Untuk menjawab pertanyaan tentang arti "coding" di sini, yang dimaksud adalah tindakan encoding/decoding yang mengubah informasi dari satu representasi ke representasi lain. Sistem seperti ini disebut kode, dan dirancang agar tahan terhadap interferensi, modifikasi, atau penyadapan saat informasi dikirim. Jadi, coding dipakai di banyak bidang seperti kompresi data, enkripsi, deteksi dan koreksi kesalahan, transmisi data, dan penyimpanan data tautan

  • Buku yang disebutkan secara khusus berfokus pada error correcting code. Ketika menyampaikan pesan, data tambahan dilampirkan agar bagian yang hilang bisa dipulihkan. Tantangan yang harus dipecahkan adalah merancang data tambahan yang dapat memulihkan cukup banyak kesalahan dengan overhead seminimal mungkin dan waktu komputasi yang wajar. Teknologi seperti ini benar-benar dipakai di sangat banyak tempat, seperti WiFi, hard drive, kode QR, dan RAM. Misalnya, ECC dalam ECC RAM adalah error correcting code. Dalam DDR5, teknologi ini belakangan sebagian diwajibkan

• Karena suasananya sedang berbagi ebook CS gratis, saya juga sangat merekomendasikan buku Algorithms karya Jeff E. Ini bacaan wajib bagi siapa saja yang ingin belajar algoritma atau meninjau kembali kemampuannya tautan

• Saya sudah membaca beberapa bab dari buku ini dan sangat puas. Saya berencana membacanya pelan-pelan selama beberapa minggu, atau mungkin beberapa bulan ke depan

• Jika ingin belajar lebih dalam tentang teori informasi dan teori pengodean, saya juga ingin merekomendasikan bahan berikut. Untuk error correcting code, "Error-Correcting Codes" karya W. Wesley Peterson dan E. J. Weldon, Jr., dan untuk aljabar abstrak, khususnya teori medan, "Commutative Algebra" karya Oscar Zariski dan Pierre Samuel layak dijadikan rujukan

  • Perintah LaTeX tidak berfungsi di sini

• Kalau harus menyebut beberapa buku yang ingin saya rekomendasikan untuk pemula,

  1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> karya John R. Pierce - klasik yang bagus untuk memahami konsep dan membangun intuisi. Buku-buku lain dari penulis yang sama juga luar biasa
  2. <i>Information Theory: A Tutorial Introduction</i> karya James V. Stone - buku pengantar yang mudah dan bagus. Tutorial lain yang ditulis penulis ini juga bermanfaat
  3. <i>A Student's Guide to Coding and Information Theory</i> karya Stefan Moser dan Po-ning chen - panduan yang ringkas dan jelas, dan buku-buku lain dalam seri yang sama juga layak direkomendasikan

• Setiap kali seseorang mengatakan "ini wajib," bagi saya yang di jurusan hanya pernah sedikit bersentuhan dengan topik tersebut, itu selalu terasa agak menakutkan

  • Yang dimaksud dengan 'wajib' pada mata kuliah ini bukanlah bahwa semua mahasiswa ilmu komputer harus mengetahuinya, melainkan bahwa buku ini memuat inti sari teori pengodean. Salah satu penulis bersama buku ini mengajar langsung di kampus kami, dan kuliah ini adalah mata kuliah pilihan tingkat atas dengan porsi matematika yang sangat besar. Dalam program ilmu komputer empat tahun, biasanya hanya segelintir mahasiswa tingkat akhir yang mengambilnya, dan teman-teman saya yang pernah mengambilnya semuanya adalah orang-orang yang menyukai pembuktian matematis. Mereka menikmati mata kuliah ini

  • Jika tertulis "wajib" atau "pengantar," itu pertanda bahwa buku teks yang menunggu adalah buku yang sangat padat