Skip to content
Kembali ke hasil pencarian

Kode Polar dengan Dekode Pembatalan Berurutan

Diperkenalkan oleh
Erdal Arikan
Tahun
2009
Jenis
recursive 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 polar, yang diperkenalkan oleh Erdal Arikan pada tahun 2009, adalah keluarga kode konstruktif pertama yang terbukti mencapai kapasitas Shannon dari kanal simetris input-biner tanpa memori.

Kode ini menggunakan konstruksi rekursif dan dekode pembatalan berurutan, sebuah algoritma serakah sederhana dengan jaminan teoretis. Kode polar diadopsi dalam 5G NR untuk pengodean kanal kontrol dan dipelajari untuk sistem 6G di masa depan. Berbeda dengan kode turbo dan LDPC (yang bersifat empiris), kode polar menyediakan landasan teoretis yang ketat.

Intuisi di balik metode

Kode polar didasarkan pada konsep polarisasi kanal: menerapkan transformasi rekursif spesifik pada sekumpulan kanal identik independen menciptakan sekumpulan kanal baru di mana beberapa kanal menjadi efektif tanpa derau (kapasitas 1) dan yang lain efektif tidak berguna (kapasitas 0). Bit informasi ditempatkan pada kanal tanpa derau; bit beku (diketahui penerima) mengisi kanal yang tidak berguna. Dekode menggunakan pembatalan berurutan: dekode bit demi bit secara berurutan, menggunakan bit yang telah didekode sebelumnya untuk memperbaiki estimasi bit yang tersisa. Struktur rekursif memastikan bahwa kompleksitas dekode adalah linier terhadap panjang kode, dan properti polarisasi menjamin kinerja pencapaian kapasitas asimtotik.

Sejarah

Makalah Arikan tahun 2009 tentang polarisasi kanal bersifat transformatif: untuk pertama kalinya, keluarga kode konstruktif terbukti mencapai kapasitas dengan kompleksitas polinomial. Penelitian selanjutnya mengembangkan dekoder praktis (propagasi keyakinan, dekode daftar) untuk mengatasi error floor pada SNR sedang. Kode polar diadopsi dalam 3GPP 5G NR Release 15 untuk kanal kontrol (misalnya, PBCH, DCI), menggantikan kode turbo. Untuk kanal data, LDPC dipilih karena kinerja empiris yang lebih baik pada panjang blok sedang. Arikan memenangkan IEEE Information Theory Society paper award, dan kode polar tetap menjadi penelitian aktif.

Kapan digunakan

Kode polar ideal untuk panjang paket pendek hingga sedang (100-1000 bit) dan persyaratan latensi ketat (tanpa dekode iteratif). Gunakan kode polar untuk kanal kontrol di 5G/6G atau skenario apa pun yang memprioritaskan jaminan pencapaian kapasitas yang dapat dibuktikan. Hindari kode polar untuk kata kode yang sangat panjang (>10k bit) di mana fleksibilitas LDPC lebih disukai. Kode polar unggul di kanal block-fading; di flat fading, tidak ada keuntungan khusus dibandingkan LDPC.

Batasan dan pertimbangan

  • Pembatalan berurutan memiliki propagasi kesalahan eksponensial pada SNR rendah (error floor)
  • Desain bit beku memerlukan pengetahuan SNR kanal di muka; adaptasi diperlukan
  • Kinerja pada panjang blok pendek lebih rendah daripada LDPC/turbo tanpa modifikasi cerdas
  • Propagasi keyakinan atau dekode daftar (untuk mengurangi error floor) menambah kompleksitas, mendekati LDPC
  • Ekosistem implementasi kurang matang dibandingkan kode turbo dan LDPC

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

Kelebihan

  • Keluarga kode pertama dengan bukti konstruktif pencapaian kapasitas Shannon
  • Dekode pembatalan berurutan sederhana; kompleksitas waktu linier O(N log N)
  • Struktur rekursif memungkinkan implementasi yang efisien perangkat keras
  • Tidak ada pemrosesan iteratif; latensi deterministik (penting untuk sistem waktu nyata)
  • Kerangka kerja teoretis untuk menganalisis kinerja dan mengoptimalkan konstruksi kode
  • Adaptasi inheren melalui pemilihan bit beku untuk SNR dan panjang blok yang berbeda

Penerapan

  • Kanal kontrol 5G NR (PBCH, DCI): transmisi paket pendek yang andal dengan batasan latensi ketat
  • Komunikasi satelit: pengodean terstruktur dengan latensi dekode deterministik untuk tautan kritis misi
  • Distribusi kunci kuantum: keamanan teoretis dikombinasikan dengan koreksi kesalahan praktis
  • Telemetri kedirgantaraan: komunikasi pesawat ruang angkasa dengan keandalan ultra-tinggi dan penundaan dekode terbatas
  • Komunikasi optik: jangkauan pendek tetapi tautan berkecepatan tinggi di mana dekode deterministik cepat sangat penting

Cara kerjanya

Cara kerjanya

1

Bit informasi (ditambah bit beku) membentuk kata kode melalui matriks generator yang dibangun secara rekursif (struktur produk Kronecker).

2

Matriks generator G dibangun dengan produk Kronecker berulang dari [[1,0],[1,1]]; ini menciptakan struktur polarisasi rekursif.

3

Bit yang dikodekan ditransmisikan; bit yang diterima adalah nilai lunak (rasio log-kemungkinan dari kanal).

4

Dekoder pembatalan berurutan memproses bit secara berurutan: untuk bit i, ia menghitung rasio log-kemungkinan bersyarat berdasarkan semua bit yang telah didekode sebelumnya dan observasi kanal.

5

Setiap bit didekode dengan mengiris LLR-nya (positif -> 1, negatif -> 0). Jika bit i dibekukan, nilai yang diketahui digunakan. Bit yang didekode dimasukkan ke depan untuk memperbaiki estimasi LLR untuk bit yang tersisa.

Kesalahan umum

  • Menggunakan pembatalan berurutan dasar pada SNR rendah; propagasi keyakinan atau dekode daftar diperlukan untuk BER yang wajar
  • Merancang set bit beku untuk kondisi kanal yang salah; kinerja menurun jika SNR aktual berbeda dari SNR desain
  • Mengasumsikan kompleksitas dekode linier berarti dekode cepat; setiap bit masih memerlukan komputasi LLR, berjumlah total O(N log N)
  • Mengabaikan efek kuantisasi; kuantisasi LLR titik tetap (terutama keputusan percabangan) memengaruhi error floor
  • Tidak memanfaatkan adaptivitas; pemilihan ulang bit beku berdasarkan umpan balik CSI dapat secara signifikan meningkatkan kinerja

Pertanyaan yang sering diajukan

Apa itu polarisasi kanal dan bagaimana hal itu memungkinkan kode pencapaian kapasitas?

Polarisasi kanal mengubah N kanal identik menjadi N kanal dengan kapasitas terpolarisasi: beberapa mendekati 1 (tanpa derau), yang lain mendekati 0 (tidak berguna). Bit informasi pada kanal berkapasitas tinggi dilindungi; kanal berkapasitas rendah dibekukan. Seiring bertambahnya N, fraksi kanal berkapasitas tinggi mendekati kapasitas Shannon. Struktur ini memungkinkan dekode pembatalan berurutan yang sederhana untuk mencapai kapasitas.

Mengapa pembatalan berurutan memiliki error floor pada SNR rendah?

Pembatalan berurutan secara serakah mendekode satu bit pada satu waktu menggunakan estimasi bit sebelumnya. Jika bit awal didekode secara tidak benar, kesalahan akan merambat ke semua bit hilir, menyebabkan serangkaian kesalahan. Error floor ini timbul dari ketergantungan pada keputusan masa lalu. Propagasi keyakinan atau dekode daftar mengurangi hal ini dengan mengeksplorasi alternatif dan menunda keputusan keras.

Bagaimana bit beku dipilih?

Bit beku ditempatkan pada kanal dengan informasi bersama estimasi rendah (kapasitas rendah). Salah satu metode adalah mensimulasikan proses polarisasi untuk SNR dan panjang blok target, memberi peringkat kanal berdasarkan kapasitasnya, kemudian membekukan K kanal berkapasitas terendah. Ini memerlukan pengetahuan SNR di muka. Kode polar adaptif dapat memperbarui set bit beku berdasarkan umpan balik atau estimasi CSI.

Apa itu dekode daftar untuk kode polar?

Alih-alih membuat satu keputusan keras pada setiap langkah, dekode daftar mempertahankan daftar kata kode parsial kandidat dan mengeksplorasi beberapa jalur. Setelah memproses semua bit, jalur terbaik (berdasarkan kemungkinan) dipilih. Ini secara signifikan mengurangi error floor tetapi meningkatkan kompleksitas menjadi O(L N log N) di mana L adalah ukuran daftar. Ukuran daftar 8-32 adalah tipikal; keseimbangan yang baik antara kinerja dan kompleksitas.

Metode terkait

Sumber

  1. Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.

    Buka referensi DOI
    Disalin.
  2. Sasoglu, E., Telatar, I., & Yildirim, E. (2011). Polarization for arbitrary discrete memoryless channels. In Proceedings of the IEEE Information Theory Workshop (ITW), 144-148.

    Buka referensi publikasi
    Disalin.