Bài tập mã vòng lý thuyết thông tin

Định nghĩa: ma trận kiểm tra chẵn lẻ được thiết kế từ thanh ghi lùi từng bước là ma trận có dạng sau:

A=[x(0)| T x(0)|T2 x(0) |…|Tn-1 x(0)] với n là chu kỳ của thanh ghi (n > m)

Trong đó:

• T là ma trận đặc trưng của thanh ghi.
• x(0) ≠ 0: là giá trị khởi tạo của thanh ghi.
• n : là chiều dài của từ mã và cũng là chu kỳ của thanh ghi.
• m: là số bit kiểm tra hay số bit của thanh ghi.

Ví dụ: xét lại ví dụ tìm chu kỳ thanh ghi, nếu chọn giá trị khởi tạo của thanh ghi là x(0) = 1 thì ta có ma trận kiểm tra với chu kỳ n=6 như sau:

Định nghĩa mã xoay vòng

Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n của thanh ghi lùi từng bước có dạng như:

A=[x(0)| Tx(0)|T2x(0) |…|Tn-1x(0) ]

Ví dụ: xét lại ma trận kiểm tra chẵn lẻ ở trên

Ta có n = 6, m = 3, k = 2 => s = 2k = 22 = 4 từ mã.

Áp dụng Phương pháp sinh mã nhanh bộ mã kiểm tra chẵn lẻ ta có bộ mã kiểm tra chẵn lẻ gồm 4 từ mã sau : w0 = 000000, w­1 = 101010, w­2 = 010101, w­4 = 111111, đây chính là một trong các bộ mã xoay vòng sinh từ thanh ghi lùi từng bước nêu trên (Các bước sinh mã nhanh đề nghị các bạn tự làm)

Phương pháp sinh nhanh bộ mã xoay vòng

Cách sinh nhanh k từ mã độc lập tuyến tính của bộ mã vòng từ a0,a1, a2, …, am-1:

Bước 3: xác định các từ mã còn lại của bộ mã

Các từ mã còn lại gồm (2k – k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, …, k từ mã từ k từ mã độc lập tuyến tính ở trên.

• 1. KHOA HỌC TỰ NHIÊN KHOA TOÁN –TIN HỌC Mã vòng Bài báo cáo môn lý thuyết thông tin Nhóm 2 2009
• 2. dung 1. Giới thiệu ................................................................................................................................3 1.1 Định nghĩa mã vòng ...........................................................................................................3 1.2 Định nghĩa đa thức mã .......................................................................................................3 1.3 Bổ đề 1 ..............................................................................................................................4 2. Các tính chất của mã vòng .......................................................................................................5 2.1 Định lý 1 ............................................................................................................................5 2.2 Định lý 2 ............................................................................................................................5 2.3 Định lý 3 ............................................................................................................................6 2.4 Định lý 4 ............................................................................................................................6 2.5 Định lý 5 ............................................................................................................................7 2.6 Định lý 6 ............................................................................................................................8 3. Mã hóa và giải mã mã vòng ................................................................................................... 10 3.1 Ma trận sinh của mã vòng ................................................................................................ 10 3.2 Ma trận sinh dạng hệ thống và dạng chuẩn ....................................................................... 11 3.3 Mã hóa thành từ mã hệ thống ........................................................................................... 12 3.4 Ma trận kiểm tra của mã vòng .......................................................................................... 13 3.5 Tính toán hội chứng và phát hiện lỗi ................................................................................ 15 3.6 Giải mã theo hội chứng .................................................................................................... 17 4. Tổng kết ................................................................................................................................ 21 Tài liệu tham khảo Toán rời rạc nâng cao-Trần Ngọc Danh-NXB ĐHQG TP HCM-2004 http://www.mth.msu.edu/~jhall/classes/codenotes/Cyclic.pdf http://cwww.ee.nctu.edu.tw/course/channel_coding/chap4.pdf http://www.mcs.vuw.ac.nz/courses/MATH324/2008T2/notes11.pdf 2 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 3. Giới thiệu 1.1 Định nghĩa mã vòng Một mã tuyến tính được gọi là mã vòng (cyclic code) nếu và chỉ nếu dịch chuyển của một từ mã cũng là một từ mã , nghĩa là nếu là một từ mã thì cũng là một từ mã . Mã vòng là mã tuyến tính , do đó được xây dựng trên một trường hữu hạn , trong bài này ta chỉ xét mã vòng trên một trường thông dụng là . Chú ý : Cách dịch từ mã như trong định nghĩa được gọi là dịch phải . Với một từ mã có chiều dài n bit thì ta dịch từ mã này i bit , kết quả cũng là một từ mã (theo qui nạp suy ra ) . Và khi ta dịch theo chiều ngược lại i bit thì kết quả cũng là một từ mã (đồng nghĩa với dịch phải n-i bit ) . 1.2 Định nghĩa đa thức mã Nếu là một từ mã thì là một đa thức mã (code polynomial) tương ứng với từ mã . Vậy chúng ta có một song ánh giữa từ mã và đa thức mã . Do ta xét mã vòng trên trường , nên mỗi đa thức mã là một đa thức trên trường và có bậc ≤ . Sau này ta sẽ dựa vào các đa thức mã này để chứng minh các tính chất của mã vòng . Ví dụ 1 Bảng sau đây trình bày một mã vòng . Thông báo Từ mã Đa thức 0000 0000000 1000 1101000 0100 0110100 1100 1011100 0010 0011010 1010 1110010 0110 0101110 1110 1000110 0001 0001101 1001 1100101 0101 0111001 1101 1010001 0011 0010111 1011 1111111 0111 0100011 1111 1001011 3 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 4. dàng kiểm tra mã trên là một mã tuyến tính có tính chất vòng . Chú ý : vì tổng 2 từ mã là một từ mã ( tính chất của mã tuyến tính ) nên tổng 2 đa thức mã là một đa thức mã . 1.3 Bổ đề 1 là từ mã có được do dịch từ mã bit , và là đa thức mã tương ứng của nó . Ta có Chứng minh Ta có Suy ra Như vậy Hay Có thể hiểu bổ đề này một cách đơn giản qua ví dụ sau Với từ mã 0 1101000 1 0110100 2 0011010 3 0001101 4 1000110 5 0100011 6 1010001 4 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 5. ta thấy tuy nhiên nếu chứa với thì được thay bằng . Trên trường chúng ta có Tương tự hay với . Như vậy ta có thể viết 2. Các tính chất của mã vòng Trong phần này ta sẽ chỉ ra một số tính chất của mã vòng . 2.1 Định lý 1 Với một mã vòng , chỉ tồn tại duy nhất một đa thức mã khác 0 có bậc nhỏ nhất . Hay nói cách khác không tồn tại hai đa thức mã khác 0 , khác nhau và cùng có bậc nhỏ nhất . Chứng minh : Giả sử tồn tại hai đa thức mã khác 0 , và cùng có bậc nhỏ nhất là . Từ đây ta suy ra đa thức có bậc nhỏ hơn , mâu thuẫn . Từ đây suy ra đpcm. Chúng ta ký hiệu đa thức mã có bậc nhỏ nhất của một mã là như sau : 2.2 Định lý 2 Hệ số tự do của phải bằng 1 . Chứng minh : Giả sử , ta suy ra 5 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 6. . Vì từ mã tương ứng với là kết quả của dịch trái 1 bit hay dịch phải (n-1) bit từ mã tương ứng với , do đó cũng là một đa thức mã . Nhưng bậc của là , mâu thuẫn với định nghĩa của . Từ đây suy ra đpcm . 2.3 Định lý 3 Một đa thức trên trường có bậc là đa thức mã nếu và chỉ nếu nó là một bội số của . Tức là có thể viết Chứng minh : Trước hết ta chứng minh nếu và bậc của thì là đa thức mã . Chúng ta có Trong đó p là bậc của và . Do với là đa thức mã tương ứng với từ mã được tạo thành do dịch từ mã bit . Theo tính chất của mã tuyến tính thì cũng là một từ mã vì là tổ hợp tuyến tính của các từ mã . Ngược lại , giả sử là một đa thức mã , ta có Trong đó là đa thức dư có bậc nhỏ hơn bậc của . Mặt khác trên trường , ta có , suy ra Ta có có bậc bậc của , từ chứng minh phần trước ta suy ra là một đa thức mã , mặt khác là một đa thức mã . Suy ra là một đa thức mã có bậc nhỏ hơn bậc của . Do tính chất của , ta suy ra , suy ra đpcm . Từ định lý này , ta gọi là đa thức sinh (generator polynomial), vì từ có thể sinh ra tất cả các đa thức mã khác. 2.4 Định lý 4 Đa thức sinh của một mã vòng có bậc Chứng minh : Gọi là bậc của đa thức sinh Từ định lý 3 , chúng ta có mỗi đa thức mã là một bội số của 6 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 7. vậy có bao nhiêu từ mã thì có bấy nhiêu đa thức . Do bậc của nên bậc của . Suy ra có hệ số thuộc trường , tức là có đa thức . Mặt khác số lượng từ mã là ( do là mã tuyến tính ) . Từ đây suy ra Chứng minh hoàn tất . Từ định lý này ta có thể biểu diễn đa thức sinh như sau Trong đó 2.5 Định lý 5 Đa thức sinh của mã vòng là một ước số của . Chứng minh : Từ bổ đề 1 ta suy ra Hay có thể viết Bây giờ chọn , ta để ý là bậc của bằng ,bậc của . Do đó đa thức ở vế trái có bậc là , để thỏa đẳng thức thì buộc phải có tức là Từ đây , do tính chất của trường ta suy ra Mặt khác do là một đa thức mã nên ta có Như vậy (đpcm) 7 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 8. Định lý 6 Nếu là một đa thức có bậc và là ước số của thì sinh ra mã vòng , hay nói cách khác là đa thức sinh của một mã vòng nào đó . Chứng minh : Với là một đa thức có bậc và là ước của , ta chứng minh sinh ra một mã vòng . Xét k đa thức . Những đa thức có trên bậc lần lượt là Đặt là tổ hợp tuyến tính của đa thức này với các hệ số Ta thấy là đa thức có bậc và là bội số của . Với tất cả bộ , ta có đa thức phân biệt . Ta kiểm tra 2 điều sau Với bất kỳ Ta có Các hệ số Với , ta có Các hệ số Như vậy đa thức này tạo thành một không gian tuyến tính các đa thức mã với là cơ sở .Có thể biểu diễn mỗi phần tử của không gian này như sau Với là đa thức có bậc 8 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 9. vậy ta có một song ánh biến một khối (tương ứng với một đa thức ) thành một khối (tương ứng với một đa thức ) , tức là sinh ra một mã tuyến tính . Bây giờ ta chứng minh mã này có tính chất vòng , nghĩa là nếu là một từ mã thì dịch bit được thì cũng là một từ mã . Điều này tương đương với nếu là một đa thức mã thì cũng là một đa thức mã . Đầu tiên ta biểu diễn thì Theo bổ đề 1 chúng ta có Hay Tương đương với Ta suy ra , nghĩa là Do là bội của (từ cách đặt ) , và là bội của (từ giả thiết) , ta suy ra cũng là bội của . Mặt khác bậc của , suy ra Với là đa thức có bậc . Như vậy cũng là đa thức mã , tức là mã tuyến tính do sinh ra có tính chất vòng . (đpcm) Ví dụ 2 Tìm các đa thức sinh cho các mã vòng có độ dài 7 . Đa thức sinh của một mã vòng có độ dài 7 là ước của . Phân tích đa thức này ra thừa số chúng ta được 9 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 10. 3 thừa số , như vậy có tất cả đa thức sinh ( là ước của ) , tức là có 8 mã vòng có độ dài từ mã là 7 tương ứng với 8 đa thức sinh sau đây : (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) Đa thức sinh sẽ sinh ra mã vòng chính là , còn đa thức sinh sẽ sinh ra mã vòng chỉ có 1 phần tử là {0000000}. 3. Mã hóa và giải mã mã vòng 3.1 Ma trận sinh của mã vòng Từ các định lý trên ta có được những điều sau : Một mã vòng bất kỳ sẽ được sinh từ đa thức sinh của nó , đa thức này là một đa thức có bậc trên trường . Mỗi từ mã sẽ có một đa thức mã tương ứng và ngược lại , tất cả đa thức mã tương ứng với các từ mã của mã vòng này là các đa thức có dạng Như vậy mỗi từ mã là tổ hợp tuyến tính của các từ mã có các đa thức mã tương ứng . Và chú ý là các đa thức mã này độc lập tuyến tính ( vì chúng có bậc hoàn toàn khác nhau ) , do đó ta có thể biểu diễn ma trận sinh (generator matrix) của mã vòng như sau Nhắc lại là , trong đó Đôi khi người ta còn gọi ma trận sinh là ma trận sinh mã vòng (cyclic generator matrix) . 10 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 11. đã có ma trận sinh , thì mã hóa vòng (cyclic encoding) là quá trình mã hóa thông báo thành từ mã . Ví dụ 3 Tìm một mã vòng Từ ví dụ 2 ta thấy có 8 đa thức sinh ứng với 8 mã vòng có độ dài 7 , theo định lý 6 thì đa thức sinh cho mã vòng phải có bậc là 3 . Có 2 đa thức sinh cùng có bậc là 3 , mỗi đa thức này sẽ sinh ra một mã vòng .Chúng ta sẽ chọn một đa thức , chẳng hạn Từ đây ta suy ra ma trận sinh của mã vòng này là Thông báo sẽ được mã hóa thành từ mã . Bộ mã này là bộ mã được trình bày trong ví dụ 1 . 3.2 Ma trận sinh dạng hệ thống và dạng chuẩn Mã hóa dạng hệ thống (synstematic encoding) sẽ mã hóa thông báo thành từ mã dạng hệ thống (systematic form) . Mã hóa dạng chuẩn (standard encoding) sẽ mã hóa thông báo thành từ mã dạng chuẩn (standard form) Để mã hóa dạng hệ thống , ta biến đổi ma trận sinh thành ma trận sinh dạng hệ thống (systematic generator matrix) . Từ cách mã hóa theo dạng hệ thống , ta dễ dàng suy ra ma trận sinh dạng hệ thống phải có dạng Ta chú ý là do hàng trong ma trận sinh luôn độc lập tuyến tính (vì nó tương ứng với k đa thức có bậc từ đến ) nên việc biến đổi này luôn thực hiện được . Ví dụ với ma trận sinh trong ví dụ 3 , ta sẽ đưa về dạng hệ thống bằng cách biến đổi : 11 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 12. được Hoàn toàn tương tự cho trường hợp của mã vòng dạng chuẩn , ta có thể biến đổi ma trận sinh thành ma trận sinh dạng chuẩn (standard generator matrix) . Tuy nhiên do tính vòng của mã vòng , ta có thể biến đổi từ ma trận sinh dạng hệ thống sang dạng chuẩn bằng cách dịch vòng bit . Ma trận sinh dạng chuẩn có dạng sau Với ma trận sinh dạng hệ thống lúc nãy , ta dịch vòng 4 bit để được ma trận sinh dạng chuẩn 3.3 Mã hóa thành từ mã hệ thống Cũng giống như các loại mã tuyến tính khác , ta có thể mã hóa một thông báo thành từ mã hệ thống bằng cách dùng ma trận sinh dạng hệ thống . Với mã vòng chúng ta có thể dùng cách sau để mã hóa thông báo thành từ mã , trong đó bit là các bit kiểm tra . Gọi là đa thức thông báo (message polynomial) tương ứng với thông báo , vì bậc của , chia cho ta được Từ đây suy ra Chú ý là bậc của , do là bội của nên nó là một từ mã . Và để ý mã tương ứng với đa thức mã này có bit sau chính là bit thông báo . Đó chính là từ mã dạng hệ thống tương ứng với thông báo . Do tính chất vòng nên ta có thể tìm từ mã dạng chuẩn tương ứng với thông báo bằng cách dịch vòng k bit từ mã dạng hệ thống tương ứng với . Ví dụ 4 12 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 13. mã vòng trong ví dụ 3 , ta sẽ mã hóa thông báo thành từ mã hệ thống . Đa thức tương ứng với là . Nhân với rồi chia cho chúng ta được Như vậy là đa thức mã và từ mã tương ứng là từ mã hệ thống tương ứng với . Dịch vòng bit , ta thu được từ mã chuẩn tương ứng với là . 3.4 Ma trận kiểm tra của mã vòng Ta có thể tìm ma trận kiểm tra của mã vòng theo cách chung cho các loại mã tuyến tính dựa vào định lý sau Định lý : Nếu ma trận sinh của mã C(n,k) có dạng chuẩn thì là ma trận kiểm tra của C . 1 Ví dụ Với mã vòng có đa thức sinh và ma trận sinh dạng chuẩn Suy ra ma trận kiểm tra là Dựa vào tính chất của mã vòng , ta có thể tìm ma trận kiểm tra (parity check matrix) của mã vòng theo một cách nhanh hơn như sau : Trước hết , do là ước của nên ta có thể biểu diễn Chúng ta gọi là đa thức kiểm tra (parity check polynomial) của mã .Để ý có bậc và được biểu diễn như sau, trong đó 1 Định lý 8.2.8 tr 233 –Toán rời rạc nâng cao-Trần Ngọc Danh-NXB ĐHQG TP.HCM-2004 13 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 14. là đa thức mã tương ứng với từ mã , chúng ta có thể biểu diễn như sau , trong đó có bậc Từ đó Do có bậc nên các hệ số của trong bằng 0 . Ta có thể tính được các hệ số này bằng cách khai triển các đa thức và , từ đó suy ra đằng thức sau Suy ra các tích vector sau bằng 0 Vì thế nếu chúng ta đặt thì chúng ta suy ra . Từ đây suy ra là ma trận kiểm tra của mã vòng . 14 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 15. dụ 5 Cho mã vòng có đa thức sinh là . Từ đây suy ra Và chúng ta có ma trận kiểm tra của mã này như sau 3.5 Tính toán hội chứng và phát hiện lỗi Giả sử là đa thức được gửi đi , còn là đa thức nhận được , chúng ta có thể viết Với là đa thức tương ứng với lỗi xảy ra . Đa thức hội chứng (syndrome polynomial) được định nghĩa bởi . Với là đa thức sinh của mã vòng và có bậc , do đó bậc của , và sẽ tương ứng với 1 từ nhị phân có độ dài . Do là đa thức mã nên Như vậy Hay Như vậy đa thức hội chứng chỉ phụ thuộc vào lỗi . Để tìm đa thức hội chứng , đầu tiên ta định nghĩa ma trận như sau : là ma trận kích thước , trong đó cột thứ , ký hiệu là chính là từ có độ dài tương ứng với . Ta có thể nhận thấy chính là ma trận kiểm tra (parity check matrix ) 2 của mã vì với là một đa thức mã , ta có Bây giờ , nếu là từ nhận được thì 2 Các ma trận kiểm tra H trong 3.4 và 3.5 đều có thể dùng để kiểm tra từ mã và tính toán hội chứng, ma trận kiểm tra khác nhau sẽ cho ra hội chứng s khác nhau với cùng một lỗi, với mã vòng người ta thường dùng ma trận H trong 3.5 để tính hội chứng vì nó tương đương với cách tính bằng đa thức –vốn được dùng nhiều trong thiết kế mạch 15 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 16. vậy nếu và chỉ nếu là đa thức mã . Hơn nữa , nếu thì tương ứng với đa thức . Ví dụ 6 Với mã vòng sinh bởi đa thức . Như vậy , chúng ta tìm như sau Như vậy 16 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 17. từ nhận được , tương ứng với . Ta có và . 3.6 Giải mã theo hội chứng Trước tiên ta giới thiệu một số định nghĩa và định lý. Định nghĩa 3 (i) Với 2 từ và . Khoảng cách giữa và là số vị trí khác nhau của x và y ( nghĩa là số các sao cho ), ký hiệu . (ii) Cho mã có ít nhất 2 từ , khoảng cách của được định nghĩa là (iii) Trọng lượng của , ký hiệu , là số bit khác 0 của . Nói cách khác với 0 là từ zero . (iv) Qui tắc giải mã thích hợp tối đa : trong một kênh liên lạc với các từ trong mã được truyền đi và là một từ nhận được thì được giải mã thành với là từ mã thỏa nhận /truyền ) = nhận /truyền ) (v) Cho là số nguyên dương và là một mã , ta nói hiệu chỉnh được lỗi nếu được truyền đi và là từ nhận được sao cho thì được giải mã thành theo qui tắc thích hợp tối đa . Định lý 4 Mã hiệu chỉnh được lỗi nếu và chỉ nếu , nghĩa là nếu mã có khoảng cách thì hiệu chỉnh đúng lỗi , ký hiệu [.] để chỉ phần nguyên . Định lý sau đây sẽ giúp tính toán các hội chứng nhanh hơn Định lý 7 Với là đa thức nhận được , hội chứng của , nghĩa là là đa thức hội chứng của , nghĩa là 3 ĐN 8.1.6, 8.1.10, 8.2.3, 8.1.5, 8.1.13 Toán rời rạc nâng cao-Trần Ngọc Danh-NXB ĐHQG TP.HCM 4 ĐL 8.1.14 Toán rời rạc nâng cao –Trần Ngọc Danh-NXB ĐHQG TP.HCM 17 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 18. có Chứng minh Với là dịch vòng 1 bit của , Như vậy Để giải mã mã vòng , ta có thể tạo một bảng giải mã chuẩn (standard decoding array – SDA) , sau đó với một chuỗi nhận được , ta tính hội chứng của nó và sửa lỗi theo SDA. Ví dụ 7 Với mã vòng có đa thức sinh là , mã này có khoảng cách nhỏ nhất , do đó có thể hiệu chỉnh 1 đúng 1 lỗi . Tức là nếu lỗi xảy ra có trọng lượng bằng 1 thì mã này có thể sửa được , nếu lỗi xảy ra tại nhiều hơn 1 bit thì không thể sửa được . Như vậy những lỗi có thể sửa được của mã này là và các dịch vòng của nó . Với 18 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 19. mã trên ta được bảng sau Nếu đa thức ta nhận được là , thì hội chứng của nó là Dựa vào SDA được tìm ra như trên là từ mã thích hợp tối đa của . Ta có thể lợi dụng tính chất của mã vòng đề xây dựng một thuật toán giải mã nhanh hơn mà không cần phải tạo SDA . Đầu tiên ta có , do đó ⇔ bậc nhỏ hơn bậc g . Mặt khác ta có Giả sử tồn tại sao cho có bậc nhỏ hơn bậc của , khi đó 19 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 20. mã hiệu chỉnh được lỗi , thì ta chỉ có thể sửa được những lỗi có trọng lượng nhỏ hơn hoặc bằng , có nghĩa điều kiện để sửa lỗi là , hay Từ những phân tích trên ta có một thuật toán để giải mã mã vòng như sau 1. Tính đa thức hội chứng , với là đa thức nhận được 2. Với mỗi , tính ( là hội chứng của dịch vòng thứ của ) , lặp lại cho đến khi tìm được một có trọng lượng của , khi đó đa thức lỗi thích hợp nhất là . Chú ý là trong thuật toán trên , với một lỗi , ta giả sử tồn tại sao cho có bậc nhỏ hơn . Rất có khả năng có một lỗi có trọng lượng nhỏ hơn nhưng không thỏa tính chất này , đây là những lỗi có thể sửa được ( bằng SDA chẳng hạn) nhưng không sửa được bằng thuật toán này , do đó đây là thuật toán không chính xác , nhưng điểm mạnh của thuật toán này , ta có thể thiết kế các mạch giải mã rất dễ dàng và tốc độ thực thi nhanh (do chủ yếu sử dụng các phép dịch bit) . Ví dụ 8 Cho mã vòng có đa thức sinh , mã này có khoảng cách , do đó hiệu chỉnh được 1 lỗi ( . Giả sử đa thức nhận được là , ta tính được hội chứng của nó là , vậy , suy ra Như vậy là từ mã thích hợp tối đa của . Ví dụ 9 Cho mã vòng có đa thức sinh là . Mã này có , như vậy mã này hiệu chỉnh lỗi . Tức là những lỗi có trọng lượng nhỏ hơn hoặc bằng 2 đều có thể sửa được . Giải mã với từ nhận được . Đa thức tương ứng là . 20 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp
• 21. đa thức hội chứng , vậy , suy ra Như vậy 4. Tổng kết Mã vòng là một loại mã tuyến tính đặc biệt , nhờ tính chất vòng của nó , việc sinh ra một mã vòng , mã hóa , kiểm tra , giải mã đều được thực hiện dễ dàng , đặc biệt là việc thiết kế các mạch mã hóa và giải mã cũng rất dễ, do đó nó là loại mã rất quan trọng trong lý thuyết thông tin. Trong bài này , mã vòng được xây dựng trên một trường cụ thể là , tuy nhiên những gì ta xét trong bài cũng hoàn toàn đúng cho mã vòng tổng quát được xây dựng trên trường , thậm chí các phép chứng minh cũng hoàn toàn tương tự như vậy , chỉ có một ít khác biệt về dấu của các đa thức trong một số khái niệm và chứng minh. Có nhiều loại mã vòng đặc biệt được sử dụng rộng rãi trong thực tế, mỗi loại có tính chất và cách xây dựng riêng . Và bài báo cáo này không tìm hiểu một loại mã cụ thể mà chỉ giới thiệu các tính chất chung của mã vòng , cách xây dựng những mã vòng thông thường , cùng với cách mã hóa, kiểm tra , và giải mã chúng. Đây là nền tảng để tìm hiểu những loại mã được sử dụng nhiều như mã CRC , mã BHC , mã Reed-Solomon… Hết ! 21 Lê Đức Bằng – Nguyễn Quốc Cường – Chu Đông Thuyết – Đỗ Trọng Hợp