Mã tận (Convolutional code) là một lớp mã sửa lỗi tạo ra các ký hiệu kiểm tra bằng cách trượt một hàm đa thức Boolean trên dòng dữ liệu. Nhờ cấu trúc “dạng lưới” (trellis), mã tận cho phép giải mã tối ưu với độ phức tạp tính toán hợp lý, và vẫn giữ độ chính xác cao ngay cả trên kênh truyền nhiễu mạnh.
Mã tận khác mã khối ở chỗ nào?
Mã tận được đặc trưng bởi tốc độ mã gốc k/n và độ sâu nhớ (constraint length) K, tức đầu ra phụ thuộc vào bit hiện tại và K-1 bit vào trước đó. Trong đó k là số bit dữ liệu đầu vào và n là số bit đầu ra sau mã hóa; luôn có k < n vì bước mã hóa chèn thêm dữ liệu dư thừa.
Độ sâu nhớ cũng có thể biểu diễn bằng số phần tử nhớ v trong đa thức, tương đương với 2^v trạng thái có thể có của bộ mã hóa. Chính số trạng thái này quyết định độ phức tạp của bộ giải mã: bộ giải mã Viterbi phải duyệt toàn bộ lưới trạng thái ở mỗi bước thời gian.
Khác biệt then chốt với mã khối (block code): mã tận dùng lưới bất biến theo thời gian, nhờ đó có thể giải mã quyết định mềm tối ưu với độ phức tạp hợp lý. Ngược lại, mã khối cổ điển có lưới thay đổi theo thời gian và thường chỉ giải mã quyết định cứng. Chính ưu điểm này giúp mã tận phổ biến trong truyền dữ liệu số.
Mã tận thường được mô tả là mã “liên tục”, song trên thực tế hầu hết các hệ thống đều mã hóa theo khối dữ liệu có độ dài bất kỳ và dùng kỹ thuật kết thúc (termination) để đưa bộ mã hóa về trạng thái toàn 0, tránh phát sinh ký hiệu chuyển tiếp ở cuối khối.
Lịch sử phát triển và thuật toán Viterbi
Mã tận được Peter Elias giới thiệu năm 1955. Khi đó người ta cho rằng có thể giải mã mã tận với chất lượng tùy ý chỉ bằng cách tăng độ phức tạp tính toán và độ trễ. Năm 1967, Andrew Viterbi chứng minh có thể giải mã mã tận theo phương pháp khả năng cao nhất với độ phức tạp hợp lý nhờ bộ giải mã dựa trên lưới — thuật toán Viterbi. Sau đó nhiều thuật toán giải mã lưới khác ra đời, tiêu biểu là BCJR.
Đến khoảng năm 1991, Claude Berrou phát minh mã tận hệ thống đệ quy (recursive systematic convolutional code), đặc biệt hiệu quả cho xử lý lặp với các mã nối như turbo code. Về mặt toán học, mã tận kinh điển giống một bộ lọc FIR, còn mã tận đệ quy giống một bộ lọc IIR — đây cũng là lý do phải cẩn trọng khi đánh giá ổn định và khả năng chu kỳ của mã đệ quy.
Bộ mã hóa và cách bộ giải mã Viterbi hoạt động
Quy trình mã hóa khởi đầu với các thanh ghi nhớ mặc định bằng 0, mỗi bước đưa một bit dữ liệu vào và trượt qua toàn bộ thanh ghi. Đầu ra là tổng theo modulo 2 (tức phép XOR) của các thanh ghi theo từng đa thức sinh, mỗi đa thức sinh ứng với một nhánh đầu ra. Vì tín hiệu điện tử qua kênh nhiễu sẽ bị nhiễu, mỗi ký hiệu nhận được có một xác suất sai, và nhiệm vụ của bộ giải mã là tìm chuỗi bit gốc “có khả năng nhất” đã tạo ra chuỗi nhận được đó.
Thuật toán Viterbi duyệt từng trạng thái trong lưới từ trái sang phải, lưu lại đường đi có xác suất cao nhất tới mỗi trạng thái. Khi tới cuối chuỗi, thuật toán truy ngược đường đi tối ưu để khôi phục dữ liệu gốc. Nhờ tính chất quyết định mềm, thuật toán dùng được thông tin độ tin cậy của từng mức điện áp nhận được chứ không chỉ dạng nhị phân cứng, nên hiệu quả hơn hẳn so với quyết định cứng.
Thuật toán Viterbi không chỉ dành riêng cho mã tận: nó là thuật toán quy hoạch động tìm chuỗi trạng thái ẩn khả năng nhất giải thích chuỗi quan sát được, và được dùng rộng rãi trong mô hình Markov ẩn, nhận dạng giọng nói, nhận dạng từ có trọng số và theo dõi mục tiêu.
Puncturing và ứng dụng thực tế
Để điều chỉnh tốc độ mã cho phù hợp băng thông kênh, người ta dùng kỹ thuật puncturing (đục lỗ): mã tận “mẹ” tốc độ 1/2 có thể tăng lên 7/8 chỉ bằng cách không truyền một phần ký hiệu mã. Hiệu năng mã đục lỗ thay đổi theo tỉ lệ ký hiệu kiểm tra còn truyền đi — càng giữ nhiều ký hiệu kiểm tra thì càng bảo mật, nhưng băng thông lại tăng.
Mã tận được dùng rộng rãi trong liên lạc số: truyền hình số, radio, mạng di động (GSM, GPRS, EDGE và 3G đến Release 7), và liên lạc vệ tinh bao gồm cả liên lạc không gian sâu. Nó thường được nối với mã quyết định cứng như Reed–Solomon trước khi turbo code xuất hiện — trước sự xuất hiện của turbo code, tổ hợp này là cấu trúc hiệu quả nhất và đã gần đạt giới hạn Shannon.
Tính linh hoạt về tốc độ mã và độ dài khối, cùng với khả năng giải mã quyết định mềm giá rẻ, đã làm cho mã tận trở thành lựa chọn phổ biến trong truyền thông số. Ngày nay nó vẫn xuất hiện trong các hệ thống truyền dữ liệu không dây, trong chuẩn Wi-Fi, và trong nhiều thiết kế vi mạch số (FPGA) chuyên giải mã tốc độ cao.
Kết luận
Mã tận là công nghệ mã hóa sửa lỗi lâu đời nhưng vẫn hiệu quả nhờ khả năng giải mã tối ưu với lưới bất biến và chi phí tính toán thấp. Hiểu rõ cấu trúc trellis, thuật toán Viterbi và kỹ thuật puncturing giúp bạn nắm được cách truyền dữ liệu đáng tin cậy qua các kênh nhiễu trong thế giới thực.
Nguồn: Wikipedia – Convolutional code, Wikipedia – Viterbi algorithm
