Trong lý thuyết mã hóa, mã BCH là một lớp các mã sửa lỗi vòng xây dựng bằng trường hữu hạn. Mã BCH được phát minh năm 1959 bởi Hocquenghem, và một cách độc lập năm 1960 bởi BoseRay-Chaudhuri.[1] Tên viết tắt BCH gồm chữ cái đầu của tên những người phát minh ra loại mã này.

Một trong những tính năng chính của mã BCH là khi thiết kế, có thể điều chỉnh chính xác số lỗi mã có thể sửa được. Cụ thể hơn, có thể thiết kế mã BCH nhị phân sửa được nhiều lỗi bit. Một lợi thế khác của mã BCH là có thể giải mã dễ dàng bằng một phương pháp đại số gọi là giải mã hội chứng. Điều này giúp đơn giản hóa việc thiết kế bộ giải mã cho mã này bằng phần cứng điện tử sử dụng ít năng lượng.

Mã BCH được dùng trong nhiều ứng dụng như liên lạc vệ tinh,[2] máy nghe CD, DVD, ổ đĩa, SSD[3]mã vạch hai chiều.

Cách xây dựngSửa đổi

Mã BCH nghĩa hẹp nguyên thủySửa đổi

Với một số nguyên tố   và hai số nguyên dương    thỏa mãn  , một mã BCH nghĩa hẹp nguyên thủy trên trường hữu hạn   với chiều dài mã   và khoảng cách nhỏ nhất lớn hơn hoặc bằng   được xây dựng như sau.

Đặt   là một phần tử nguyên thủy của  . Với mọi số nguyên dương  , đặt  đa thức nhỏ nhất của  . Đa thức sinh của mã BCH được định nghĩa là bội chung nhỏ nhất  . Có thể thấy   là một đa thức có hệ số trong   và chia hết  . Do đó mã đa thức định nghĩa bởi   là một mã vòng.

Ví dụSửa đổi

Đặt    (nên  ). Ta sẽ xét các giá trị khác nhau cho  . Tồn tại nghiệm nguyên thủy   thỏa mãn

 

 

 

 

 

(1)

đa thức nhỏ nhất của nó trên   là:  . Ghi chú là trong  , đẳng thức   là đúng, nên  . Vì vậy   là nghiệm của  , nên

 .

Để tính  , có thể thấy, bằng cách áp dụng (1) nhiều lần, ta thu được hệ các quan hệ tuyến tính sau:

  •  
  •  
  •  
  •  
  •  

Năm vế phải là các tổ hợp tuyến tính của 4 lũy thừa giống nhau nên chúng phụ thuộc tuyến tính. Thật vậy, ta có tổ hợp tuyến tính  . Vì không tồn tại quan hệ phụ thuộc tuyến tính bậc nhỏ hơn nên đa thức nhỏ nhất của   là: . Tiếp tục tương tự như vậy, ta tìm được

 
 
 
 

Mã BCH với   có đa thức sinh

 

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 3, và do đó sửa được 1 lỗi. Vì đa thức sinh có bậc 4, mã này có 11 bit dữ liệu và 4 bit kiểm tra.

Mã BCH với   có đa thức sinh

 

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 5 và do đó sửa được 2 lỗi. Vì đa thức có bậc 8, mã này có 7 bit dữ liệu và 8 bit kiểm tra.

Mã BCH với   có đa thức sinh

 

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 7 và do đó sửa được 3 lỗi. Mã này có 5 bit dữ liệu và 10 bit kiểm tra.

Mã BCH với   và lớn hơn có đa thức sinh

 

Mã này có khoảng cách Hamming nhỏ nhất bằng 15 và sửa được 7 lỗi. Nó có 1 bit dữ liệu và 14 bit kiểm tra. Mã này chỉ có đúng hai mã tự: 000000000000000 và 111111111111111.

Ghi chúSửa đổi

  1. ^ Reed & Chen 1999, tr. 189
  2. ^ “Phobos Lander Coding System: Software and Analysis” (PDF). Truy cập ngày 25 tháng 2 năm 2012.
  3. ^ “Sandforce SF-2500/2600 Product Brief”. Truy cập ngày 25 tháng 2 năm 2012.

Tham khảoSửa đổi

Tài liệu nguyên thủySửa đổi

Tài liệu khácSửa đổi