Skip to content
Kembali ke hasil pencarian

Kode Paritas-Pemeriksaan Kepadatan Rendah (LDPC)

Diperkenalkan oleh
Robert Gallager
Tahun
1962
Jenis
linear error-correcting code
Keluarga
Coding theory

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Kode LDPC, yang ditemukan oleh Robert Gallager pada tahun 1962 dan ditemukan kembali pada tahun 1990-an oleh MacKay, adalah kode linear pengoreksi kesalahan yang didefinisikan oleh matriks paritas-pemeriksaan yang jarang.

Kode ini mencapai kinerja dalam 0,4 dB dari batas Shannon dengan dekode propagasi keyakinan iteratif dan telah menjadi standar untuk nirkabel modern (WiFi-6, 5G NR, Digital Video Broadcasting). Berbeda dengan kode turbo, kode LDPC memiliki struktur teori graf yang lebih elegan dan analisis teoretis yang lebih matang.

Intuisi di balik metode

Kode linear standar menggunakan matriks paritas-pemeriksaan yang padat, membuat dekode menjadi intensif secara komputasi. Kode LDPC membalikkan ini: matriks paritas-pemeriksaan jarang (sebagian besar entri adalah nol), sehingga setiap pemeriksaan paritas hanya melibatkan segelintir bit. Di penerima, graf bipartit dibangun di mana node variabel mewakili bit yang ditransmisikan dan node pemeriksaan mewakili batasan paritas. Dekode menjadi propagasi pesan iteratif pada graf ini: setiap node variabel mengumpulkan informasi dari tetangganya, memperbarui keyakinannya tentang nilai bit, dan mengirimkan perkiraan yang disempurnakan kembali. Ketersebaran memastikan konvergensi cepat dan kinerja mendekati Shannon.

Sejarah

Gallager menemukan kode LDPC pada tahun 1962, tetapi teori tersebut tertinggal dari implementasi praktis. Pada tahun 1995, MacKay menemukan kembali kode tersebut dan menunjukkan kinerja mendekati Shannon melalui simulasi. Penelitian ekstensif pada tahun 2000-an mengembangkan algoritma pengkodean, dekode, dan konstruksi graf yang efisien. Kode LDPC diadopsi dalam WiFi-6 (802.11ax, 2021) dan standar 5G NR (2018). Kode ini menjadi lebih umum daripada kode turbo dalam sistem baru karena kinerja yang lebih baik dan struktur yang lebih bersih.

Kapan digunakan

Kode LDPC lebih disukai daripada kode turbo dalam sistem modern karena kinerja yang lebih baik dan arsitektur yang lebih sederhana. Gunakan LDPC untuk rentang SNR yang luas (tidak ada ambang batas jurang); kode ini bekerja dengan baik dari SNR rendah hingga tinggi. LDPC adalah standar untuk WiFi-6, satelit, dan 5G NR. Hindari LDPC hanya jika kompatibilitas warisan memerlukan kode turbo. LDPC juga cocok untuk paket yang sangat pendek (>30 bit) karena struktur kode dapat dipisahkan.

Batasan dan pertimbangan

  • Konstruksi graf dan penyimpanan matriks menjadi kompleks untuk kode yang sangat panjang (>10k bit)
  • Kinerja sensitif terhadap struktur graf skala kecil (lingkar, himpunan penyerap); memerlukan desain yang cermat
  • Propagasi keyakinan mengasumsikan graf bergelung, tetapi graf memiliki siklus; konvergensi ke solusi optimal tidak dijamin
  • Latensi dekode (iterasi) tumbuh secara logaritmik dengan SNR; bukan latensi nol seperti beberapa kode klasik
  • Kuantisasi pesan (dalam perangkat keras titik tetap) memengaruhi kinerja; alokasi bit yang cermat diperlukan

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Kinerja dalam 0,4 dB dari batas Shannon (sedikit lebih baik dari kode turbo)
  • Struktur teori graf yang lebih sederhana; analisis teoretis yang lebih bersih daripada kode turbo
  • Dekode iteratif menghindari perilaku ambang batas seperti jurang (tidak seperti turbo)
  • Desain kode yang fleksibel melalui konstruksi graf; mudah disesuaikan dengan aplikasi tertentu
  • Perangkat keras dekode paralel yang efisien; propagasi pesan cocok untuk implementasi VLSI/GPU
  • Bekerja dengan baik untuk kata sandi panjang dan cukup pendek

Penerapan

  • WiFi-6 (802.11ax): jaringan area lokal nirkabel throughput tinggi dengan LDPC menyediakan pengiriman data yang andal
  • 5G NR: pengkodean saluran untuk saluran data dan kontrol, menggantikan kode turbo dari 4G
  • Komunikasi satelit: penyiaran video digital (DVB-S2) dan misi luar angkasa jauh menggunakan LDPC kata sandi panjang
  • Komunikasi jalur daya (PLC): transmisi data yang kuat melalui jaringan listrik yang bising
  • Sistem memori flash: koreksi kesalahan untuk penyimpanan flash NAND tanpa penurunan kualitas akibat penyegaran yang sering

Cara kerjanya

Cara kerjanya

1

Bit informasi dikodekan menggunakan matriks paritas-pemeriksaan jarang H; bit yang dikodekan adalah solusi dari H*c = 0 (mod 2), di mana c adalah kata sandi.

2

Matriks paritas-pemeriksaan H disusun agar jarang (misalnya, setiap baris/kolom memiliki bobot konstan rendah 3-5). Struktur ini dieksploitasi untuk pengkodean yang efisien.

3

Bit yang dikodekan ditransmisikan melalui saluran yang bising; bit yang diterima adalah nilai lunak (rasio kemungkinan atau rasio kemungkinan logaritmik).

4

Graf bipartit dibangun: node kiri = node variabel (bit), node kanan = node pemeriksaan (persamaan paritas). Tepi menghubungkan variabel ke pemeriksaan tempat mereka muncul.

5

Propagasi keyakinan iteratif: node variabel mengagregasi pesan dari node pemeriksaan, memperbarui perkiraan bit, dan mengirimkan pesan yang disempurnakan kembali. Setelah iterasi, keputusan keras dibuat; jika pemeriksaan paritas dipenuhi, dekode berhasil.

Kesalahan umum

  • Menggunakan graf jarang yang dirancang buruk dengan siklus pendek; siklus pendek menyebabkan propagasi keyakinan berosilasi
  • Iterasi berlebihan di luar konvergensi; iterasi yang tidak perlu membuang daya tanpa peningkatan
  • Mengasumsikan dekode min-sum sebaik sum-product; aproksimasi memiliki kehilangan kinerja, terutama pada SNR rendah
  • Mengabaikan efek panjang terbatas; graf yang dirancang untuk analisis asimtotik mungkin berkinerja buruk pada paket pendek
  • Tidak memperhitungkan kuantisasi dalam implementasi perangkat keras; simulasi titik mengambang berbeda dari realitas titik tetap

Pertanyaan yang sering diajukan

Apa yang membuat dekode LDPC begitu efisien dibandingkan dengan kode linear umum?

Ketersebaran matriks paritas-pemeriksaan berarti setiap bit berpartisipasi hanya dalam beberapa pemeriksaan paritas. Pada dekode, propagasi pesan pada graf bipartit bersifat linear terhadap jumlah tepi, bukan panjang kode. Untuk kode padat, dekode akan memerlukan inversi matriks, yang bersifat kubik terhadap panjang kode. Ketersebaran membuat dekode quasi-linear dan praktis untuk kode panjang.

Apa itu himpunan penyerap dan mengapa itu penting?

Himpunan penyerap adalah subset kecil dari graf yang dapat menjebak dekode propagasi keyakinan, mencegah konvergensi ke solusi yang benar. Himpunan ini adalah sumber utama lantai kesalahan (penurunan BER yang tidak eksponensial pada SNR rendah). Perancang kode menghindari himpunan penyerap pendek melalui konstruksi graf yang cermat; alat analisis (misalnya, analisis himpunan penghenti) mengidentifikasi struktur yang bermasalah.

Bagaimana perbandingan LDPC dengan kode polar?

Keduanya mencapai kinerja mendekati Shannon. Kode polar memiliki struktur rekursif dan optimalitas yang terbukti di bawah dekode pembatalan berurutan pada panjang kode tak terbatas. Kode LDPC lebih fleksibel dan secara empiris memiliki kinerja panjang terbatas yang lebih baik. 5G NR menggunakan kode polar untuk saluran kontrol (paket pendek) dan LDPC untuk saluran data (paket panjang), memanfaatkan kekuatan masing-masing kode.

Mengapa lingkar graf penting dalam kode LDPC?

Lingkar adalah panjang siklus terpendek dalam graf bipartit. Siklus pendek (lingkar < 6) menyebabkan propagasi keyakinan menggunakan informasi yang berkorelasi (pesan berulang), menurunkan kinerja. Kode lingkar tinggi (lingkar ≥ 6) memutus korelasi dengan lebih baik. Kode sering dirancang untuk memaksimalkan lingkar dengan batasan kelangkaan.

Metode terkait

Sumber

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Buka referensi DOI
    Disalin.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Buka referensi DOI
    Disalin.