Skema Koreksi Kesalahan 'Ajaib' Terbukti Tidak Efisien | Majalah Kuanta

Jika Anda pernah mengirim pesan teks, memutar CD, atau menyimpan file di cloud, Anda mendapat manfaat dari koreksi kesalahan. Ide revolusioner ini dimulai pada tahun 1940-an, ketika para peneliti pertama kali menyadari bahwa pesan apa pun dapat ditulis ulang dalam bentuk yang memungkinkan korupsi di kemudian hari dapat dengan mudah dibalik.

Selama bertahun-tahun, para peneliti telah mengembangkan banyak skema cerdik, yang disebut kode koreksi kesalahan, yang menyandikan data dengan cara berbeda dan menggunakan prosedur berbeda untuk memperbaiki kesalahan. Namun bagi para ilmuwan komputer teoretis, hanya sedikit kode yang bisa dikoreksi secara lokal. Kode-kode ini memiliki dua sifat simultan yang terdengar hampir bertentangan: Setiap kesalahan dapat diperbaiki dengan membaca data yang dikodekan hanya di beberapa tempat, namun tidak ada penyerang yang dapat menggagalkan prosedur koreksi ini dengan mengutak-atik kode secara selektif. Seolah-olah Anda dapat memulihkan halaman mana pun yang terkoyak dari sebuah buku hanya dengan melihat sekilas beberapa halaman lainnya.

“Ini fenomena yang sangat ajaib,” katanya Tom Gur, seorang ilmuwan komputer di Universitas Cambridge. “Secara apriori, tidak jelas apakah objek matematika seperti itu bisa ada.”

Namun keajaiban ini harus dibayar mahal. Satu-satunya contoh kode yang dapat diperbaiki secara lokal sangatlah tidak efisien — pengkodean pesan apa pun juga membuatnya jauh lebih lama. Seluruh buku yang dikodekan dengan cara ini akan terlalu berat.

Para ilmuwan komputer telah lama bertanya-tanya apakah mungkin kode yang lebih baik dan dapat diperbaiki secara lokal. Mereka berfokus terutama pada kode yang hanya menggunakan tiga kueri untuk memperbaiki kesalahan apa pun, dengan harapan bahwa pembatasan ketat ini dapat membuat kode ini lebih mudah dipahami. Namun kasus sederhana ini pun telah membingungkan para peneliti selama lebih dari 20 tahun.

Sekarang ilmuwan komputer Pravesh Kothari dari Universitas Carnegie Mellon dan mahasiswa pascasarjananya Peter Manohar akhirnya terbukti bahwa tidak mungkin membuat kode tiga kueri yang dapat diperbaiki secara lokal yang menghindari biaya eksponensial tersebut. Ini mungkin merupakan hasil yang negatif, tetapi apa pun yang memperjelas batas-batas koreksi kesalahan adalah hal yang menarik bagi para peneliti, terutama karena matematika kode-kode yang dapat diperbaiki secara lokal muncul di daerah-daerah yang jauh dari komunikasi.

“Hasil ini luar biasa,” kata Shubhangi Saraf, seorang ilmuwan komputer di Universitas Toronto. “Ini merupakan terobosan besar.”

Kekuatan dalam Angka

Untuk memahami koreksi kesalahan, bayangkan data yang ingin Anda lindungi sebagai rangkaian bit, atau 0 dan 1. Kesalahan, dalam model ini, dapat berupa perubahan angka 0 menjadi 1 yang tidak diinginkan atau sebaliknya, baik karena fluktuasi acak atau gangguan yang disengaja.

Misalkan Anda ingin mengirim pesan ke teman, namun Anda khawatir kesalahan dapat mengubah artinya. Salah satu strategi sederhananya adalah mengganti setiap angka 0 dalam pesan Anda dengan 000 dan setiap angka 1 dengan 111. Jika teman Anda melihat bagian pesan yang tidak berisi tiga bit identik berturut-turut, mereka akan mengetahui bahwa telah terjadi kesalahan. Dan jika kesalahan terjadi secara acak dan relatif jarang, maka string apa pun yang terdiri dari 110 kemungkinan besar adalah 111 yang rusak dibandingkan 000 yang rusak. Suara mayoritas dalam setiap triplet sudah cukup untuk memperbaiki sebagian besar kesalahan.

Skema ini, yang disebut kode pengulangan, memiliki keunggulan kesederhanaan, namun tidak banyak yang merekomendasikannya. Salah satu alasannya adalah diperlukan tiga kali lipat panjang setiap pesan hanya untuk menangani kesalahan yang relatif jarang terjadi, dan jika ada kemungkinan besar terjadi dua kesalahan yang berdekatan, kita memerlukan lebih banyak redundansi. Yang lebih buruk lagi, kode tersebut dengan cepat menjadi tidak berguna jika kesalahan tidak terjadi secara acak, seperti ketika penyerang secara aktif mencoba menyabotase kode. Dalam kode pengulangan, semua informasi yang diperlukan untuk memperbaiki bit tertentu disimpan hanya dalam beberapa bit lainnya, sehingga rentan terhadap serangan yang ditargetkan.

Untungnya, banyak kode koreksi kesalahan yang memberikan hasil lebih baik. Salah satu contoh terkenal, disebut Kode Reed-Solomon, bekerja dengan mengubah pesan menjadi polinomial — seperti ekspresi matematika x² + 3x + 2 yang terdiri dari suku-suku berbeda yang dijumlahkan, masing-masing dengan variabel (misalnya x) dinaikkan ke kekuatan yang berbeda. Pengkodean pesan menggunakan kode Reed-Solomon melibatkan pembuatan polinomial dengan satu suku untuk setiap karakter dalam pesan, kemudian memplot polinomial tersebut sebagai kurva pada grafik dan menyimpan koordinat titik-titik yang terletak pada kurva tersebut (mengambil setidaknya satu lagi poin daripada jumlah karakter). Kesalahan mungkin akan mendorong beberapa titik tersebut keluar dari kurva, namun jika kesalahan tidak terlalu banyak, hanya satu kurva polinomial yang akan melewati sebagian besar titik tersebut. Kurva tersebut hampir pasti sesuai dengan pesan sebenarnya.

Kode Reed-Solomon sangat efisien — Anda hanya perlu menyimpan beberapa poin tambahan untuk memperbaiki kesalahan, sehingga setiap pesan yang disandikan hanya sedikit lebih panjang dari aslinya. Mereka juga kurang rentan terhadap gangguan yang ditargetkan yang dapat menyebabkan bencana bagi kode pengulangan, karena informasi yang digunakan untuk memperbaiki kesalahan di mana pun didistribusikan ke seluruh pesan yang disandikan.

Berpikir Global, Bertindak Lokal

Kekuatan kode Reed-Solomon berasal dari keterhubungan. Namun justru karena keterhubungan tersebut, tidak ada cara untuk memperbaiki satu kesalahan pun dalam pesan yang disandikan tanpa membaca keseluruhannya. Hal ini mungkin tidak terdengar seperti masalah dalam konteks komunikasi: Jika Anda mengirim pesan, Anda mungkin ingin penerimanya membaca semuanya. Namun hal ini dapat menjadi beban dalam penyimpanan data — penerapan besar lainnya dari koreksi kesalahan.

Pertimbangkan sebuah perusahaan yang menyimpan email pengguna di cloud — yaitu, di beragam server. Anda dapat menganggap seluruh kumpulan email sebagai satu pesan panjang. Sekarang anggaplah satu server mogok. Dengan kode Reed-Solomon, Anda perlu melakukan perhitungan besar-besaran yang melibatkan semua data yang disandikan untuk memulihkan email Anda dari satu server yang hilang. “Anda harus melihat semuanya,” kata Zeev Dvir, seorang ilmuwan komputer di Universitas Princeton. “Itu bisa berupa miliaran email – ini bisa memakan waktu yang sangat lama.”

Para peneliti menggunakan istilah “lokal” untuk menggambarkan kode yang hanya menggunakan sebagian kecil dari pesan yang dikodekan kesalahan titik atau memperbaikinya. Kode pengulangan sederhana memiliki karakter lokal, namun justru itulah yang membuatnya sangat rentan terhadap gangguan. Sebaliknya, kode yang dapat diperbaiki secara lokal mendapatkan manfaat terbaik dari keduanya — kode tersebut dapat memperbaiki kesalahan dalam bit apa pun hanya dengan beberapa kueri, semuanya tanpa kehilangan keterhubungan yang membuat kode Reed-Solomon begitu tangguh.

“Ini adalah gagasan yang sangat ketat,” kata Kothari.

Contoh paling terkenal dari kode yang dapat diperbaiki secara lokal adalah versi kode koreksi kesalahan yang ditemukan pada tahun 1954 oleh para ahli matematika. David Müller dan Irving Reed (yang juga membantu mengembangkan kode Reed-Solomon). Seperti kode Reed-Solomon, kode Reed-Muller menggunakan polinomial dengan banyak istilah yang dijumlahkan untuk mengkodekan pesan yang panjang.

Polinomial yang digunakan dalam kode Reed-Solomon melibatkan satu variabel, x, jadi satu-satunya cara untuk menambahkan lebih banyak istilah adalah dengan menggunakan pangkat yang lebih tinggi x. Hal ini menghasilkan kurva dengan banyak goyangan yang hanya dapat ditentukan dengan melihat banyak titik. Kode Reed-Muller menggunakan polinomial di mana setiap suku dapat berisi beberapa variabel yang dikalikan bersama. Semakin banyak variabel berarti semakin banyak cara untuk menggabungkannya, yang pada gilirannya menawarkan cara untuk meningkatkan jumlah suku polinomial tanpa menaikkan variabel individual ke pangkat yang tinggi.

Kode Reed-Muller sangat fleksibel. Anda dapat menyandikan pesan yang lebih panjang dengan meningkatkan pangkat tertinggi yang muncul dalam polinomial, menambah jumlah variabel, atau keduanya. Untuk membuat kode Reed-Muller dapat diperbaiki secara lokal, Anda cukup membatasi daya maksimum setiap variabel pada nilai konstan yang kecil, dan menangani pesan yang lebih panjang dengan hanya menambah jumlah variabel.

Khusus untuk kode tiga kueri yang dapat diperbaiki secara lokal, daya maksimum ditetapkan pada 2. Kemudian, sejauh menyangkut setiap variabel individual, polinomial yang mengkode pesan tersebut menelusuri parabola sederhana. Untuk menentukan bentuk pasti parabola tersebut, Anda hanya perlu memeriksa kurva di tiga titik. Terlebih lagi, dengan banyak variabel, terdapat banyak parabola, yang mana pun dapat digunakan untuk memperbaiki kesalahan. Itulah yang membuat kode Reed-Muller begitu tangguh.

Sayangnya, kode Reed-Muller memiliki kelemahan serius: Jumlah bit yang diperlukan untuk mengkodekan pesan meningkat secara eksponensial seiring dengan jumlah variabel. Jika Anda menginginkan kode yang sangat lokal yang memperbaiki kesalahan hanya dengan beberapa kueri, Anda memerlukan banyak variabel untuk pesan yang panjang, dan kode Reed-Muller akan dengan cepat menjadi tidak berguna dalam praktiknya.

“Eksponensial dalam hal ini sangat buruk,” kata Dvir. Namun apakah hal ini tidak bisa dihindari?

Dapat Diperbaiki atau Dapat Didekodekan?

Ketika para ilmuwan komputer mencoba dan gagal menemukan kode yang lebih efisien dan dapat diperbaiki secara lokal, mereka mulai curiga bahwa kode tersebut tidak mungkin dilakukan sama sekali. Pada tahun 2003, dua peneliti terbukti bahwa tidak ada cara untuk mengalahkan kode Reed-Muller hanya dengan menggunakan dua kueri. Tapi sejauh itulah yang bisa diketahui siapa pun.

“Setelah kita masuk ke tahap ketiga, pengetahuan kita menjadi sangat samar,” kata Kothari.

Terobosan berikutnya justru semakin memperumit masalah. Dalam dua makalah yang diterbitkan di 2008 dan 2009, ilmuwan komputer Sergey Yekhanin dan Klim Efremenko menunjukkan cara membuat kode tiga kueri yang lebih efisien daripada kode Reed-Muller, namun kode ini tidak dapat diperbaiki secara lokal. Sebaliknya, mereka memiliki properti yang sedikit berbeda yang disebut dekodebilitas lokal.

Untuk memahami perbedaannya, mari kita bayangkan lagi penyedia penyimpanan cloud yang menggabungkan data pengguna ke dalam satu pesan panjang dan melindunginya menggunakan kode koreksi kesalahan. Baik kode yang dapat diperbaiki secara lokal maupun kode yang dapat didekodekan secara lokal dapat memperbaiki kesalahan pada bagian mana pun dari pesan asli hanya dengan beberapa pertanyaan.

Namun setiap kode koreksi kesalahan juga memerlukan bit tambahan yang tidak ada dalam pesan aslinya — itulah sebabnya pengkodean pesan membuatnya lebih lama. Kedua jenis kode ini berbeda dalam cara mereka memperlakukan bit tambahan ini. Kode yang dapat didekode secara lokal tidak menjanjikan jumlah kueri yang diperlukan untuk memperbaiki kesalahan dalam bit ini. Namun dalam kode yang dapat diperbaiki secara lokal, kesalahan pada bit tambahan mana pun dapat diperbaiki dengan cara yang persis sama seperti kesalahan pada bit mana pun pada pesan asli.

“Segala sesuatu yang Anda simpan, apakah itu data asli pengguna atau redundansi dan informasi pemeriksaan – semua ini dapat diperbaiki secara lokal,” kata Madhu Sudan, seorang ilmuwan komputer di Universitas Harvard.

Meskipun pada prinsipnya berbeda, kemampuan koreksi lokal dan kemampuan dekode lokal selalu tampak dapat dipertukarkan dalam praktiknya sebelum tahun 2008 - setiap kode yang diketahui dapat didekode secara lokal juga dapat diperbaiki secara lokal. Penemuan Yekhanin dan Efremenko memunculkan kemungkinan adanya perbedaan mendasar antara kedua kondisi tersebut. Atau mungkin kode Yekhanin dan Efremenko dapat diubah agar dapat diperbaiki secara lokal. Hal ini sekali lagi akan menempatkan kedua kondisi tersebut pada posisi yang sama, namun hal ini juga berarti bahwa para peneliti telah salah dalam menilai seberapa efisien kode tiga kueri yang dapat diperbaiki secara lokal. Apa pun yang terjadi, kebijakan konvensional harus diubah.

Logika Peminjaman

Kothari dan Manohar akhirnya menyelesaikan ketegangan tersebut dengan mengadaptasi teknik dari bidang ilmu komputer yang berbeda: studi tentang apa yang disebut masalah kepuasan kendala. Mencoba mengoordinasikan rencana makan malam dengan sekelompok teman adalah semacam kendala kepuasan. Setiap orang mempunyai pilihan yang akan mereka terima dan pilihan yang akan mereka veto. Tugas Anda adalah menemukan rencana yang memuaskan semua orang, atau, jika tidak ada rencana seperti itu, buatlah rencana tersebut sesegera mungkin.

Ada asimetri yang melekat antara dua kemungkinan hasil tersebut. Solusi yang dapat diterima mungkin tidak mudah ditemukan, namun begitu Anda memilikinya, mudah untuk meyakinkan orang lain bahwa solusi tersebut akan berhasil. Namun meskipun Anda mengetahui bahwa masalahnya benar-benar “tidak memuaskan”, mungkin tidak ada contoh yang dapat memberikan bukti.

Pada tahun 2021, Kothari dan Manohar, bersama dengan Venkatesan Guruswami dari University of California, Berkeley, membuat terobosan besar dalam studi masalah kepuasan kendala menggunakan teknik teoretis baru untuk mengidentifikasi kasus-kasus rumit yang tidak dapat memuaskan tersebut. Mereka menduga bahwa metode baru ini akan menjadi alat yang ampuh untuk memecahkan masalah lain juga, dan mahasiswa pascasarjana Guruswami, Omar Alrabiah, menyarankan agar mereka melihat kode tiga kueri yang dapat didekode secara lokal.

“Bisa dikatakan, ini adalah paku dengan palu di tangan kami,” kata Kothari.

Hasil mengejutkan Yekhanin dan Efremenko menunjukkan bahwa kode tiga kueri yang dapat didekodekan secara lokal bisa lebih efisien daripada kode Reed-Muller. Namun apakah kode mereka adalah yang terbaik, atau bisakah kode tiga kueri yang dapat didekode secara lokal menjadi lebih efisien? Kothari, Manohar, Guruswami, dan Alrabiah berpikir bahwa teknik baru mereka mungkin dapat membuktikan batasan seberapa efisien kode tersebut dapat diperoleh. Rencana mereka adalah membangun rumus logis yang mencakup struktur semua kemungkinan kode tiga kueri yang dapat didekodekan secara lokal dengan ukuran tertentu, dan membuktikannya tidak memuaskan, sehingga menunjukkan bahwa kode seperti itu tidak ada.

Keempat peneliti tersebut mengambil langkah pertama ke arah tersebut pada tahun 2022, dengan menetapkan a batas baru pada efisiensi maksimum kode tiga kueri yang dapat didekodekan secara lokal. Hasilnya jauh melampaui apa yang dapat dicapai para peneliti dengan teknik lain, namun tidak menutup kemungkinan bahwa semua kode lebih efisien daripada kode Yekhanin dan Efremenko.

Kothari dan Manohar menduga mereka bisa melangkah lebih jauh. Namun kemajuan terhenti sampai Manohar mencatat perhitungan cepat yang menunjukkan bahwa teknik ini mungkin bekerja lebih baik untuk kode yang dapat diperbaiki secara lokal dibandingkan dengan kode yang dapat didekode secara lokal.

Beberapa bulan kemudian, setelah banyak kesalahan awal yang membuat mereka takut terlalu optimis, teknik ini akhirnya memenuhi janjinya. Kothari dan Manohar membuktikan bahwa seperti dugaan para peneliti, tidak mungkin kode tiga kueri yang dapat diperbaiki secara lokal bekerja lebih baik daripada kode Reed-Muller. Penskalaan eksponensial adalah batasan mendasar. Hasil dari penelitian ini juga merupakan demonstrasi dramatis bahwa kemampuan koreksi lokal dan kemampuan dekode lokal, meskipun secara dangkal serupa, sebenarnya berbeda pada tingkat mendasar: Yang terakhir ini jelas lebih mudah untuk direalisasikan dibandingkan yang pertama.

Kothari dan Manohar sekarang berharap untuk memperluas teknik mereka untuk mempelajari kode yang diperbolehkan untuk membuat lebih dari tiga pertanyaan, karena saat ini sangat sedikit yang diketahui tentang kode tersebut. Dan kemajuan dalam teori koreksi kesalahan seringkali mempunyai implikasi pada bidang lain yang tampaknya tidak berhubungan. Secara khusus, kode-kode yang dapat diperbaiki secara lokal membuat kemunculan yang mengejutkan di mana-mana dari masalah pencarian database pribadi dalam kriptografi untuk pembuktian teorema dalam kombinatorik. Masih terlalu dini untuk mengatakan bagaimana teknik Kothari dan Manohar akan berdampak pada berbagai bidang ini, namun para peneliti merasa optimis.

“Ada ide baru yang sangat bagus di sini,” kata Dvir. “Saya pikir ada banyak potensi.”