Skip to content

Channel Coding: LDPC và Polar

Mã hóa kênh (channel coding), còn gọi là sửa lỗi hướng tới (Forward Error Correction, FEC), là kỹ thuật thêm bit dư thừa vào dữ liệu ở bên phát để bên thu phát hiện và sửa được lỗi bit mà không cần yêu cầu phát lại. Trang này trình bày theo thứ tự: nguyên lý và các khái niệm chung, các họ mã chính, mã hóa kênh trong LTE và NR (LDPC cho kênh dữ liệu, Polar cho kênh điều khiển), rate matching và HARQ, và cuối cùng là tác động tới hiện thực L1. Mã hóa đường truyền (line coding) như NRZ hay 8b/10b là một khái niệm khác, được trình bày ở Line Coding (NRZ, PAM4, 8b/10b).

Nguyên lý mã hóa kênh

Bộ mã hóa (encoder) nhận k bit thông tin và tạo ra một từ mã (codeword) n bit, với n > k. Phần n − k bit thêm vào gọi là parity, được tính từ các bit thông tin theo quy tắc của bộ mã. Vì không phải mọi tổ hợp n bit đều là từ mã hợp lệ, bên thu có thể nhận ra từ mã bị nhiễu làm sai và tìm từ mã hợp lệ gần nhất.

Nguyên lý mã hóa kênh: thêm bit dư thừa ở bên phát để bên thu sửa được lỗi

Hình minh họa dùng mã Hamming (7,4): 4 bit thông tin 1011 được thêm 3 bit parity 010. Trên đường truyền, nhiễu làm bit thứ hai bị hiểu sai, nhưng decoder vẫn khôi phục đúng 4 bit ban đầu.

Các khái niệm cơ bản

Khái niệm Ý nghĩa
Code rate (R) Tỷ lệ k/n giữa bit thông tin và bit của từ mã. R nhỏ nghĩa là nhiều parity: chịu nhiễu tốt hơn nhưng tốc độ hữu ích thấp hơn
Mã hệ thống (systematic) Từ mã chứa nguyên vẹn k bit thông tin, parity nằm riêng. LDPC và Turbo trong LTE/NR đều là mã hệ thống
Quyết định cứng (hard decision) Bên thu quyết định ngay mỗi bit là 0 hay 1 rồi mới đưa vào decoder
Quyết định mềm (soft decision) Bên thu giữ độ tin cậy của từng bit, thường dưới dạng LLR, và decoder dùng thông tin này. Decoder mềm cho hiệu năng tốt hơn decoder cứng
LLR (Log-Likelihood Ratio) Logarit của tỷ số xác suất bit là 0 và bit là 1. Dấu của LLR cho biết bit nghiêng về giá trị nào, độ lớn cho biết mức tin cậy
Coding gain Mức giảm SNR cần thiết để đạt cùng tỷ lệ lỗi so với khi không mã hóa
Giới hạn Shannon Tốc độ tối đa truyền được với xác suất lỗi nhỏ tùy ý trên một kênh có SNR cho trước. Các mã hiện đại như Turbo, LDPC, Polar tiến sát giới hạn này

Trong LTE và NR, khối giải điều chế (demodulator) xuất LLR cho từng bit, không xuất bit. Mỗi LLR được lượng tử hóa thành nhiều bit, nên dữ liệu vào decoder lớn hơn nhiều lần so với dữ liệu ra.

Các họ mã chính

Họ mã Nguyên lý tóm tắt Thường dùng ở
Hamming Mã khối tuyến tính, sửa 1 bit lỗi Bộ nhớ ECC đơn giản, minh họa lý thuyết
BCH, Reed-Solomon Mã khối đại số, sửa nhiều bit hoặc nhiều symbol lỗi ECC của NAND flash, CD/DVD, mã QR, Ethernet tốc độ cao (RS(544,514))
Convolutional Mỗi bit ra phụ thuộc vào vài bit vào gần nhất, giải mã bằng thuật toán Viterbi GSM, kênh điều khiển LTE (tail-biting convolutional code)
Turbo Hai bộ mã convolutional song song nối qua một interleaver, giải mã lặp Kênh dữ liệu 3G và LTE
LDPC Ma trận kiểm tra parity rất thưa, giải mã lặp bằng belief propagation Kênh dữ liệu NR, Wi-Fi 802.11n trở lên, DVB-S2, ECC của SSD
Polar Biến đổi kênh để một phần các kênh con trở nên rất tin cậy, đặt dữ liệu lên các kênh con đó Kênh điều khiển NR

LDPC được Gallager đề xuất năm 1962, Turbo code được công bố năm 1993 và Polar code năm 2009. Các mốc này được dẫn nguồn ở mục Tài liệu tham khảo.

Mã hóa kênh trong LTE

LTE dùng hai bộ mã, quy định trong 3GPP TS 36.212:

  • Kênh dữ liệu (DL-SCH, UL-SCH): Turbo code với mother code rate 1/3 và interleaver dạng QPP (Quadratic Permutation Polynomial). Kích thước code block từ 40 đến 6144 bit; transport block lớn hơn được chia thành nhiều code block.
  • Kênh điều khiển (DCI, PBCH, một phần UCI): tail-biting convolutional code, code rate 1/3.

Giải mã Turbo có tính tuần tự cao trong mỗi vòng lặp, nên khó mở rộng song song khi tốc độ dữ liệu tăng lên hàng Gbit/s. Đây là một trong các lý do NR chuyển sang LDPC.

Mã hóa kênh trong NR

NR dùng LDPC cho kênh dữ liệu và Polar cho kênh điều khiển, quy định trong 3GPP TS 38.212. Hình dưới tóm tắt hai chuỗi xử lý.

Chuỗi mã hóa kênh trong NR cho kênh dữ liệu và kênh điều khiển

LDPC cho kênh dữ liệu

Kênh dữ liệu (DL-SCH trên PDSCH, UL-SCH trên PUSCH) đi qua các bước:

  1. Gắn CRC cho transport block (TB): 24 bit nếu TB lớn hơn 3824 bit, 16 bit nếu nhỏ hơn hoặc bằng.
  2. Chọn base graph: chọn BG1 hoặc BG2 theo kích thước TB và code rate (xem bảng dưới).
  3. Phân đoạn code block: nếu TB kèm CRC vượt kích thước code block tối đa của base graph, TB được chia thành nhiều code block (CB), mỗi CB gắn thêm CRC 24 bit. CRC của từng CB cho phép decoder dừng sớm và cho phép HARQ phản hồi theo nhóm CB.
  4. Mã hóa LDPC: mỗi CB được mã hóa bằng ma trận kiểm tra parity tạo từ base graph.
  5. Rate matching: chọn ra đúng số bit cần truyền từ từ mã (xem mục rate matching).
  6. Ghép code block, scrambling và điều chế.

LDPC của NR là loại quasi-cyclic: ma trận kiểm tra parity được tạo bằng cách thay mỗi phần tử của một base graph nhỏ bằng một ma trận con Zc × Zc (ma trận 0 hoặc ma trận đơn vị bị dịch vòng). Hệ số Zc gọi là lifting size, có 51 giá trị từ 2 đến 384, cho phép một base graph phục vụ nhiều kích thước code block. Cấu trúc này cho phép decoder xử lý song song Zc hàng cùng lúc, phù hợp với phần cứng.

BG1 BG2
Kích thước base graph (hàng × cột) 46 × 68 42 × 52
Số cột thông tin 22 10 (hoặc ít hơn với khối nhỏ)
Kích thước code block tối đa 8448 bit 3840 bit
Mother code rate thấp nhất 1/3 1/5
Dùng cho Khối lớn, code rate cao Khối nhỏ, code rate thấp

Quy tắc chọn base graph: dùng BG2 nếu kích thước TB A ≤ 292 bit, hoặc A ≤ 3824 bit và code rate R ≤ 0,67, hoặc R ≤ 0,25; các trường hợp còn lại dùng BG1.

LDPC thường được giải mã bằng thuật toán truyền thông điệp (belief propagation) hoặc bản xấp xỉ min-sum, lặp giữa các nút biến (bit) và nút kiểm tra (phương trình parity) cho tới khi mọi phương trình parity thỏa mãn hoặc hết số vòng lặp cho phép.

Polar cho kênh điều khiển

Polar code dựa trên hiện tượng phân cực kênh (channel polarization): khi kết hợp đệ quy N bản sao của một kênh truyền, một phần các kênh con tạo thành trở nên gần như không lỗi, phần còn lại gần như vô dụng. Bộ mã đặt bit thông tin lên các kênh con tin cậy nhất và cố định các kênh con còn lại bằng giá trị đã biết (frozen bit). NR định nghĩa sẵn một bảng thứ tự độ tin cậy (reliability sequence) của các kênh con, dùng chung cho mọi kích thước.

Polar được dùng cho:

  • DCI trên PDCCH: gắn CRC 24 bit, trong đó 16 bit cuối được XOR với RNTI. UE giải mã thử với RNTI của mình: CRC đúng nghĩa là DCI dành cho UE đó. Kích thước từ mã mẹ N tối đa 512.
  • PBCH: MIB và các bit thời gian, cũng gắn CRC 24 bit, N = 512.
  • UCI từ 12 bit trở lên trên PUCCH hoặc PUSCH: gắn CRC 6 bit (12 đến 19 bit thông tin) hoặc 11 bit (từ 20 bit trở lên). Ở đường lên, N tối đa 1024.

UCI rất ngắn không dùng Polar: 1 bit dùng mã lặp, 2 bit dùng mã simplex, 3 đến 11 bit dùng mã Reed-Muller.

Polar thường được giải mã bằng successive cancellation list (SCL): decoder giải từng bit theo thứ tự, giữ song song một danh sách gồm vài đường giải mã có khả năng nhất, rồi dùng CRC để chọn đường đúng. Theo các đánh giá trong quá trình chuẩn hóa NR, với khối ngắn như DCI, Polar giải mã bằng SCL có hiệu năng tốt hơn LDPC và Turbo (xem bài tổng quan của Bae và cộng sự).

Lý do chọn hai bộ mã

Tiêu chí LDPC (dữ liệu) Polar (điều khiển)
Kích thước khối Lớn, tới 8448 bit mỗi CB Nhỏ, vài chục tới vài trăm bit
Yêu cầu chính Throughput cao, nhiều Gbit/s Độ tin cậy cao với khối ngắn
Đặc điểm decoder Song song tốt nhờ cấu trúc quasi-cyclic SCL có tính tuần tự, chấp nhận được với khối ngắn
HARQ Hỗ trợ incremental redundancy qua circular buffer Kênh điều khiển không dùng HARQ

3GPP chọn LDPC cho kênh dữ liệu và Polar cho kênh điều khiển của eMBB trong các cuộc họp RAN1 cuối năm 2016.

Rate matching và HARQ

Bộ mã luôn tạo ra từ mã theo mother code rate cố định (1/3 với BG1, 1/5 với BG2), còn số bit thực sự truyền được phụ thuộc vào số resource element được cấp và bậc điều chế. Rate matching là bước chọn ra đúng số bit cần truyền:

  • Với LDPC, từ mã được đặt vào một bộ đệm vòng (circular buffer). Bên phát đọc ra liên tiếp E bit bắt đầu từ một trong bốn vị trí định trước, gọi là redundancy version (RV0 đến RV3). Đọc ít hơn kích thước từ mã là puncture (bỏ bớt bit, tăng code rate), đọc vòng qua đầu bộ đệm là lặp bit (giảm code rate). 2·Zc bit thông tin đầu tiên luôn bị bỏ, không truyền.
  • Với Polar, rate matching dùng puncturing, shortening hoặc lặp tùy theo tỷ lệ giữa số bit cần truyền và N.

HARQ (Hybrid Automatic Repeat Request) kết hợp FEC với phát lại. Khi một lần truyền giải mã thất bại, bên phát gửi lại với RV khác, tức gửi phần khác của từ mã (incremental redundancy). Bên thu cộng dồn LLR của các lần truyền vào bộ đệm mềm (soft buffer) rồi giải mã lại, nên mỗi lần phát lại làm code rate hiệu dụng giảm xuống.

Tác động tới hiện thực L1

Giải mã LDPC là một trong những khối tốn tài nguyên tính toán nhất của L1 phía thu, vì vậy thường được tách ra cho bộ tăng tốc FEC (FPGA, ASIC, hoặc GPU). Một số điểm ảnh hưởng tới thiết kế:

  • Băng thông vào decoder: mỗi bit được truyền tương ứng với một LLR nhiều bit, nên đường dữ liệu giữa CPU và accelerator phải lớn hơn nhiều lần so với tốc độ dữ liệu người dùng.
  • Bộ đệm HARQ: soft buffer phải giữ LLR của mọi HARQ process chưa giải mã xong, cho mọi UE, nên chiếm nhiều bộ nhớ. Bộ đệm này có thể nằm ở accelerator hoặc ở bộ nhớ host.
  • Độ trễ: số vòng lặp của decoder thay đổi theo chất lượng kênh. CRC của từng CB cho phép dừng sớm khi giải mã đã đúng, giúp giảm độ trễ trung bình.

Chi tiết về lookaside và inline accelerator, và giao diện DPDK BBDev cho FEC offload nằm ở L1 & Acceleration.

Liên quan

Tài liệu tham khảo

  • 3GPP TS 38.212: NR; Multiplexing and channel coding (LDPC, Polar, CRC, rate matching, quy tắc chọn base graph). 3GPP Specification 38.212
  • 3GPP TS 36.212: E-UTRA; Multiplexing and channel coding (Turbo code, tail-biting convolutional code). 3GPP Specification 36.212
  • T. Richardson, S. Kudekar, "Design of Low-Density Parity Check Codes for 5G New Radio", IEEE Communications Magazine, vol. 56, no. 3, 2018.
  • J. H. Bae, A. Abotabl, H.-P. Lin, K.-B. Song, J. Lee, "An overview of channel coding for 5G NR cellular communications", APSIPA Transactions on Signal and Information Processing, vol. 8, 2019 (bối cảnh lựa chọn LDPC và Polar trong 3GPP).
  • E. Arıkan, "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels", IEEE Transactions on Information Theory, vol. 55, no. 7, 2009.
  • C. Berrou, A. Glavieux, P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes", IEEE ICC 1993.
  • R. G. Gallager, "Low-Density Parity-Check Codes", IRE Transactions on Information Theory, vol. 8, no. 1, 1962.