Lượt xem: 7968 | Gửi lúc: 29/04/2012 15:02:34
Bookmark and Share

Ứng dụng thực tế mã sửa sai

Khi ứng dụng mã sửa sai, thông báo cần truyền sẽ được mã hóa, nghĩa là chuyển nó thành một “từ mã” bằng cách thêm “độ dư”. Thay cho việc truyền thông báo, người ta truyền từ mã tương ứng của nó trên kênh. Người nhận sẽ giải mã “thông báo” này và nhận được thông tin gần nhất với thông báo gốc. Mức độ chính xác sẽ tùy thuộc vào phương pháp mã trong mối quan hệ với kênh truyền.

Các mã sửa sai đã được phát triển trong những năm 40 của thế kỷ XX, vào thời gian mà Claude Shannon phát biểu định lý rằng: hầu hết các thông tin chính xác đều có thể nhận được khi truyền trên kênh có tiếng ồn. Thông báo cần truyền trước hết được mã hóa, nghĩa là chuyển nó thành một “từ mã” bằng cách thêm độ dư. Thay cho việc truyền thông báo, người ta truyền từ mã tương ứng của nó trên kênh. Người nhận sẽ giải mã “thông báo” này và nhận được thông tin gần nhất với thông báo gốc. Mức độ chính xác sẽ tùy thuộc vào phương pháp mã, trong mối quan hệ với kênh truyền. Cách này làm tăng hiệu quả trong những ứng dụng quan trọng.
     Sơ đồ truyền tin và mã hóa này được mô tả trong hình sau:



Hiện nay, mã sửa sai đang đuợc sử dụng trong thực tế. Bài viết này giới thiệu một số ứng dụng phổ biến nhất.

Ứng dụng mã sửa sai trong bộ nhớ máy tính
Nhìn chung, bộ nhớ của máy tính được xây dựng từ các chip silicon. Mặc dù mỗi chip đều tin cậy nhưng khi tổ hợp lại thành bộ nhớ thì có thể phát sinh lỗi.
Một chip trong bộ nhớ là một mảng vuông 2 chiều, chứa các ô nhớ. Các ô nhớ số 0 hoặc 1 lưu giữ trong chip nhớ được biểu diễn bởi sự hiện diện, hoặc sự vắng mặt của điện tích âm ở những vị trí trong tinh thể silicon. Khi trạng thái 0 cần phải lưu giữ trong ô nhớ thì nguồn điện thế ở vị trí này được làm đầy bởi các điện tích; khi trạng thái 1 cần phải lưu giữ thì nguồn này là rỗng. Ô này được đọc bằng cách đo điện tích âm của nó. Nếu điện tích này cao hơn một giá trị nhất định thì nó được đọc là 0, ngược lại là 1. Nếu nguồn điện mất điện tích của nó thì việc đọc sẽ không đúng và lỗi sẽ xuất hiện như sau: Các lỗi cứng xuất hiện khi chính chip bị hư hỏng; lỗi mềm xuất hiện khi bản thân chip không hư hỏng, nhưng sự “bắn phá alpha” thực tế xuất hiện và làm thay đổi điện tích trong ô nhớ. Lỗi mềm là phổ biến và không thể tránh khỏi.
Mã sửa sai được dùng để sửa những lỗi như thế theo cách sau: Giả sử ta có bộ nhớ 1 megabyte gồm 128 chip dung lượng 64K, các chip được sắp xếp thành 4 dòng, mỗi dòng 32 chip. Dữ liệu được chia thành các từ, mỗi từ 32 bit và nó bao gồm nội dung của 32 ô nhớ, mỗi ô là mỗi một trong 32 chip. Để sửa các lỗi, 7 chip nữa được thêm vào mỗi dòng, tạo nên 156 (156 = 128 + 4 x 7) chip. Lúc này, mỗi dòng có 39 chip, 7 bit phụ là các bit kiểm tra chẵn lẻ và được giữ để sửa sai.
Tác giả của một công trình nghiên cứu [1] cho rằng, mã thực sự được khai thác là mã Hamming mở rộng nhị phân độ dài 64 bit, nghĩa là mã nhị phân [64,57,4] (với mã này, thông báo dài 57 bit được mã thành từ mã dài 64 bit; sửa được 2 lỗi trên một vector dài 64 bit tương ứng với một từ mã) và bình luận rằng, mã như thế thực sự bảo vệ 57 bit dữ liệu, nhưng thực tế thiết kế mã chỉ sử dụng 32 bit.

Truyền ảnh trong không gian
Trong những năm 60, 70 của thế kỷ XX, các bức ảnh sao Hỏa lần đầu tiên được chụp bởi các tàu vũ trụ và mã Reed- Muller bậc 1 với độ dài 32 bit được sử dụng để thu những bức ảnh chất lượng cao. Những bức ảnh đen trắng gốc do những nhà thám hiểm sao Hỏa chụp sẽ được chia thành những phần tử ảnh cỡ 200x200. Mỗi phần tử này được gán một tuple 6 bit nhị phân để biểu diễn một trong 64 bậc sáng có thể từ 000000 (trắng) tới 111111 (đen). Sau này việc phân chia được “làm đẹp” hơn nhờ sử dụng các phần tử ảnh cỡ 700x832 và chất lượng ảnh được tăng thêm nhờ mã hóa các tuple 6 bằng mã  Reed- Muller R(1,5) nhị phân sửa 7 lỗi [32,6,16]. Trong các ảnh chụp của tàu không gian Voyager cuối những năm 70, mã Goley mở rộng nhị phân  c24 , tức là mã [24,12,8], được sử dụng cho ảnh màu.
Sau này, trên các con tàu không gian Voyager, một dạng mã khác đã được sử dụng, đó là mã Reed- Solomon xoắn.

Ứng dụng sửa sai âm thanh được lưu giữ trên đĩa compact
Ứng dụng này thực hiện bằng cách chia âm thanh thành những phần nhỏ và biểu diễn những phần này bởi dữ liệu nhị phân, đúng như cách phân chia ở các bức ảnh đã nói ở phần trên. Đĩa compact được tạo ra bằng cách lấy mẫu các sóng âm thanh 44.100 lần trên một giây, biên độ được đo và được gán một giá trị giữa 1 và 216- 1, được biểu diễn bởi một tuple gồm 16 bit nhị phân. Hai mẫu sẽ được lấy, một cho kênh trái và một cho kênh phải. Mỗi tuple 16 bit này được lấy để biểu diễn 2 phần tử của trường Galois F2­8 có 28 phần tử và như vậy mỗi mẫu sản sinh ra bốn đặc trưng từ F2­8.
Để sửa sai, thông tin này được phá vỡ thành những đoạn gọi là các frame, mỗi frame nắm giữ 24 đặc trưng dữ liệu. Mã được dùng để sửa sai là mã Reed-Solomon chèn chéo (CIRC) nhận được bởi một quá trình “chèn chéo” hai mã Reed - Solomon bị cắt ngắn. 24 đặc trưng của F2­8 lấy từ 6 mẫu được sử dụng như các đặc trưng thông tin trong mã Reed- Solomon (bị cắt ngắn) [28,24,5] C1 trên F2­8. Mã Reed- Solomon bị cắt ngắn khác [32,28,5] C2 cũng trên F2­8 sau đó được sử dụng trong quá trình chèn, nó có 4 đặc trưng kiểm tra chẵn lẻ bổ sung.
Kết quả của quá trình chèn sửa sai là lỗi ở những chỗ phồng rộp trên đĩa, nó sản sinh ra một chuỗi các lỗi thường được gọi là “bùng lỗi”, được sửa đúng.         
Từ những phân tích trên, có thể thấy rằng các thuật toán giải các mã phân tích trên đều đã có sẵn và rất hiệu quả.

Ứng dụng nêu trên chỉ là những vấn đề chính, bên cạnh đó, trong nhiều năm qua Hoa Kỳ đã đầu tư nhiều kinh phí để nghiên cứu không gian, không thể không giữ bí mật các bức ảnh được truyền về trái đất. Mã sửa sai thêm độ dư vào thông báo, nghĩa là làm tăng lượng tin truyền để bảo đảm độ chính xác của thông tin, vì vậy họ không thể không sử dụng các thuật toán nén dữ liệu ban đầu để giảm chi phí.

TS. Nguyễn Ngọc Cương