Thứ Bảy, 14 tháng 3, 2015

Tìm hiểu Mã xoắn (mã chập) và cách hoán vị (interleaving)

Thực ra thì mình không thực sự hiểu thấu đáo vấn đề mã này, tuy nhiên mình có thể chỉ ra ưu điểm của nó so với mã khối và lý do nó được dùng.
Mình sẽ giải thích nó qua một sơ đồ mã xoắn đơn giản nhất :

Một bít được đưa vào bộ mã hoá sẽ xuất hiện trong 5 bit ở đầu ra. Giả sử ta đang quan sát bit c, đầu ra của bộ mã hoá sẽ gồm :

a XOR b XOR c; a XOR c; b XOR c XOR d; b XOR d; c XOR d XOR e; c XOR e; ...

Toán tử XOR ở đây tương tự toán tử cộng nhị phân (do không biết viết ký tự cộng nhị phân như thế nào).
Có thể thấy là bit c không chỉ phụ thuộc vào các bit liền trước (a, b) mà còn phụ thuộc vào các bit liền sau (d, e).

Bỏ qua những cái như khoảng cách Hamming hay khả năng sửa lỗi của bộ mã hóa này là bao nhiêu, ta chỉ cần biết là bộ mã hóa này sẽ sản sinh ra một chuỗi bit có khả năng sửa lỗi nếu kênh truyền bị lỗi.

Giả sử cho các mã sửa lỗi khối hay xoắn có cùng khẳ năng như nhau, cứ 7 bit thì mã này sửa được 1, ta truyền đi ví dụ 14 bit mã xoắn(A ở đây là đại diện cho bit đúng , B cho bit sai).
Nếu là mã khối (mã Haming, Cyclic ..) 7 bit đầu được phép sai 1 lỗi, 7 bit sau được phép sai 1 lỗi, tương tự ta có.
- AAABAAA AAAAABA ABAAAAA ...
Và mã xoắn thì trong 7 bit (3 bit liền trước và 3 bit liền sau) mà đúng thì sẽ sửa lỗi được, ví dụ đây là trường hợp nó sửa được nhiều lỗi nhất :
- AAABAAA BAAABAA ABAAABAAA.. 

Có thể nói là mật độ sửa lỗi của mã xoắn tăng hơn hẳn đối với trường hợp lỗi bị rải đều.

Tuy nhiên nó cũng không phải là không có nhược điểm ví dụ lỗi mà kiểu cụm thì :
AAAAABBAAAAAA... thì mã khối lại sửa được và mã xoắn thì tịt vì mã xoắn đòi hỏi 3 bit trước và 3 bit sau của bit lỗi phải đúng.

Vậy vì sao người ta lại đánh giá mã xoắn tốt hơn mã khối???

Và một thông tin nữa: trong viễn thông thì hầu hết lỗi xảy ra là lỗi cụm -> đáng ra mã khối phải cho kết quả tốt hơn chứ.

Tuy nhiên mã xoắn lại đi kèm với một bộ gọi là bộ hoán vị : Interleaving

nên (trong hầu hết trường hợp) lỗi trong truyền tín hiệu là lỗi cụm (thông tin được xáo trộn trước khi truyền)-> sau khi giải xáo trộn thì các lỗi lại rải ra rất đều -> 5 bit lỗi như ở ví dụ mã xoắn mà là lỗi cụm thì vẫn xử được hết miễn khoảng cách tối thiểu các lỗi là 3 bit đúng với hiệu năng (trong hầu hết trường hợp) tốt hơn mã khối.

Hiện nay có một loại mã còn tốt hơn mã xoắn nữa là mã turbo, cũng dựa trên mã xoắn có điều phức tạp hơn còn cho hiệu năng tốt hơn cả mã xoắn.

Đây là vài nhận xét rút ra khi học, hi vọng nó đúng và hữu ích cho mọi người.

Hoán vị (interleaving) có tác dụng gì ?

Trên các kênh truyền vô tuyến, việc lỗi bit thường xảy ra theo từng cụm (do tác động biến đổi nhất thời nào đó của kênh truyền, ví dụ như một khoảng thời gia bị deep fading) hơn là xảy ra từng bit lỗi riêng lẻ. Nếu một cụm lỗi bit quá nhiều vượt quá khả năng sửa lỗi của mã sửa sai thì dẫn đến giải mã sai--> lỗi bit. Để khắc phục điều này trước khi truyền bên phát interleave data, trên kênh truyền có bị lỗi cụm thì sang bên thu, sau khi deinterleave, các lỗi cũng không nằm cạnh nhau thành một cụm nữa, kết hợp với khả năng sửa lỗi của mã sửa sai, giảm được bit lỗi.

Nói chung có thể hiểu là các mã sửa lỗi chỉ có thể sửa được lỗi nếu lỗi đó ít hơn 1 mức cho phép, nếu nhiều lỗi tập trung vào 1 chỗ thì không sửa được (có khi giải ra còn lỗi nhiều hơn), nên việc xáo trộn để các lỗi cụm rải rác ra nhiều nơi, mỗi chỗ gánh 1 tí thì sẽ có khả năng sửa lỗi cụm đó.

Thực ra thì não người cũng có thể coi là một hệ thống sửa sai, với văn bản nội dung bị sai ta vẫn có thể nhận dạng nếu sai ít và các chỗ sai không phải các ký tự quan trọng, còn sai nhiều thì cũng tịt, ta có thể làm 1 ví dụ như sau:
I have a __arm.
so với
I hav_ a drea_

Thì sẽ thấy nhận dạng câu I have a dream ở ví dụ 2 dễ dàng hơn.

0 nhận xét:

Đăng nhận xét