Xem mã nguồn của Mã khối

{{chú thích trong bài}}
 
Trong [[lý thuyết mã hóa]], '''mã khối''' là một tập hợp bao gồm nhiều [[Mã hóa kênh|mã sửa lỗi]] mã hóa dữ liệu theo từng khối. Có rất nhiều loại mã khối khác nhau, được sử dụng rộng rãi trong nhiều ứng dụng thực tiễn. Một nguyên nhân khiến mã khối hữu ích như vậy là nó cho phép sử dụng một tách thống nhất các phương pháp từ [[lý thuyết mã hóa]], [[toán học]], và [[khoa học máy tính]] để nghiên cứu về các giới hạn của mã khối.
Các giới hạn đó thường ở dạng bất đẳng thức liên hệ các tham số của mã, chẳng hạn như tỉ lệ và khả năng phát hiện và sửa lỗi.

Một vài ví dụ tiêu biểu của mã khối là [[kỹ thuật sửa lỗi Reed–Solomon|mã Reed–Solomon]], [[mã Hamming]], [[mã Hadamard]], [[mã đồ thị giãn nở]], [[mã Golay]], [[mã Reed–Muller]], và [[mã BCH]]. Các ví dụ này đều là các [[mã tuyến tính]], nên chúng thường được gọi là các '''mã khối tuyến tính'''.

== Mã khối và các tham số ==

[[Mã sửa lỗi]] được dùng để truyền [[dữ liệu số]] một cách đáng tin cậy trên một [[kênh liên lạc]] có [[nhiễu]]. Khi cần truyền nhiều dữ liệu bằng mã khối, người gửi chia dữ liệu thành nhiều phần nhỏ. Mỗi phần nhỏ được gọi là một ''thông điệp'' và thuật toán mã hóa khối mã hóa mỗi thông điệp thành một mã tự, còn được gọi là một ''khối'' trong mã hóa khối. Người gửi gửi tất cả các khối cho người nhận, sau đó người nhận sử dụng thuật toán phục hồi lại thông điệp ban đầu từ các khối có lỗi.

Một mã khối là một [[đơn ánh]]
:<math>C:\Sigma^k \to \Sigma^n</math>.
Ở đây, <math>\Sigma</math> là một [[tập hợp]] các ký tự và <math>k</math> và <math>n</math> là các số nguyên dương. Ý nghĩa các tham số này sẽ được mô tả dưới đây.

=== Bảng chữ cái Σ ===
Có thể coi dữ liệu cần được mã hóa là một [[xâu ký tự]] dùng '''bảng chữ cái''' <math>\Sigma</math>. Kích thước <math>|\Sigma|</math> của bảng chữ cái thường được ký hiệu là <math>q</math>. Nếu <math>q=2</math>, thì mã khối được gọi là mã khối ''nhị phân''. Trong nhiều ứng dụng <math>q</math> thường được chọn là lũy thừa [[số nguyên tố]], và <math>\Sigma</math> là [[trường hữu hạn]] <math>\mathbb F_q</math>.

=== [[Chiều dài]] thông điệp k ===
Mỗi thông điệp ''m'' là một phần tử của <math>\Sigma^k</math>, hay nói cách khác, là một xâu ký tự độ dài <math>k</math>.
Tham số <math>k</math> được gọi là '''chiều dài thông điệp''' hay '''chiều''' của mã khối.

=== [[Chiều dài]] khối n ===
'''Chiều dài khối''' <math>n</math> của một mã khối là số ký tự trong một khối. Mỗi xâu <math>c</math> trong <math>\Sigma^n</math> là một xâu ký tự độ dài <math>n</math> và ứng với một khối (có lỗi) mà người nhận nhận được. Chúng được gọi là khối nhận được.
Nếu <math>c=C(m)</math> với một thông điệp <math>m</math> nhất định, thì <math>c</math> được gọi là mã tự của <math>m</math>.

=== Tỉ lệ R ===
'''Tỉ lệ''' của một mã khối được định nghĩa là tỉ lệ giữa [[chiều dài]] thông điệp và [[chiều dài]] khối:
:<math>R=k/n</math>.
Tỉ lệ lớn nghĩa là lượng thông tin gửi đi trong mỗi khối là cao. Nói cách khác, tỉ lệ được dùng để đo tốc độ truyền và đại lượng <math>1-R</math> đo lượng dữ liệu thừa cần dùng để mã hóa. Theo [[lý thuyết thông tin]], tỉ lệ không thể vượt quá <math>1</math> vì không thể nén dữ liệu trong mọi trường hợp. Một cách khác để suy ra nhận xét này là do <math>C</math> là một đơn ánh.

=== Khoảng cách d ===
'''Khoảng cách''' hay '''khoảng cách nhỏ nhất''' <math>d</math> của một mã khối là số ký tự khác nhau nhỏ nhất giữa hai mã tự bất kì, và '''khoảng cách tương đối''' <math>\delta</math> là tỉ lệ <math>d/n</math>.
Một cách cụ thể hơn, với hai mã tự <math>c_1,c_2\in\Sigma^n</math>, đặt <math>\Delta(c_1,c_2)</math> là [[khoảng cách Hamming]] giữa <math>c_1</math> và <math>c_2</math>, nghĩa là số vị trí khác nhau giữa <math>c_1</math> và <math>c_2</math>. Định nghĩa khoảng cách nhỏ nhất <math>d</math> của mã <math>C</math> là
:<math>d:= \min_{m_1,m_2\in\Sigma^k; m_1\neq m_2} \Delta(C(m_1),C(m_2))</math>.
Do mọi mã đều là đơn ánh, khoảng cách nhỏ nhất luôn lớn hơn hoặc bằng <math>1</math>.

Khoảng cách lớn hơn cho phép phát hiện và sửa nhiều lỗi hơn. Chẳng hạn, nếu ta chỉ xét trường hợp lỗi làm thay đổi ký tự trong mã tự gửi đi nhưng không thêm hay xóa bớt ký tự thì số lỗi chính là số vị trí khác nhau giữa khối gửi đi và khối nhận được.
Một mã với khoảng cách <math>d</math> cho phép phát hiện <math>d-1</math> lỗi vì sau khi thay đổi không quá <math>d-1</math> vị trí của một mã tự, ta không thể thu được một mã tự mới. Ngoài ra, nếu chỉ có không quá <math>(d-1)/2</math> lỗi, người nhận có thể sửa lỗi và tìm ra mã tự gửi đi. Đó là vì trong khoảng cách <math>(d-1)/2</math> từ khối tự nhận được chỉ có đúng một mã tự. Nếu có nhiều hơn <math>(d-1)/2</math> lỗi thì người nhận không thể tìm ra chính xác mã tự gửi đi. Một phương thức đối phó với trường hợp này là sử dụng [[giải mã danh sách]], trong đó người nhận liệt kê tất cả các mã tự nằm trong một bán kính nhất định.

=== Ký hiệu phổ biến ===
Mã khối dùng bảng chữ cái <math>\Sigma</math> kích thước <math>q</math>, với [[chiều dài]] khối <math>n</math>, [[chiều dài]] thông điệp/số chiều <math>k</math>, và khoảng cách <math>d</math> thường được ký hiệu là mã <math>(n,k,d)_q</math>.
Nếu mã khối là mã khối tuyến tính thì thường dùng ký hiệu ngoặc vuông <math>[n,k,d]_q</math>.
Khi <math>q=2</math> hay mã là mã nhị phân, thì không nhất thiết phải ghi rõ <math>q</math>.

Với [[mã MDS]], khoảng cách luôn là <math>d=n-k+1</math>. Trong một số trường hợp khác không rõ chính xác khoảng cách của mã là bao nhiêu. Trong những trường hợp đó có thể bỏ qua thành phần <math>d</math>.

Đôi khi, đặc biệt là mã không phải mã khối, ký hiệu <math>(n,M,d)_q</math> được dùng để chỉ mã có <math>M</math> mã tự độ dài <math>n</math>. Với mã khối với số chiều <math>k</math> trên bảng chữ cái <math>q</math>, số mã tự là <math>M=q^k</math>.

==Tham khảo==

{{Tham khảo}}

* {{chú thích sách | author=J.H. van Lint | authorlink=Jack van Lint | title=Introduction to Coding Theory | edition=2 | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | page=31}}
* {{chú thích sách | author=F.J. MacWilliams | authorlink=Jessie MacWilliams |others=[[Neil Sloane|N.J.A. Sloane]] | title=The Theory of Error-Correcting Codes | url=https://archive.org/details/theoryoferrorcor0000macw | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | page=[https://archive.org/details/theoryoferrorcor0000macw/page/35 35]}}
* {{chú thích sách | author=W. Huffman |others=V.Pless | title= Fundamentals of error-correcting codes | url=https://archive.org/details/fundamentalsofer0000huff | publisher=Cambridge University Press | date=2003 | isbn=978-0-521-78280-7}}
* {{chú thích sách | author=S. Lin |others=D. J. Jr. Costello | title= Error Control Coding: Fundamentals and Applications | url=https://archive.org/details/errorcontrolcodi0000lins | publisher=Prentice-Hall | date=1983 | isbn=0-13-283796-X}}

== Liên kết ngoài ==
* [http://www.complextoreal.com/chapters/block.pdf Coding Concepts and Block Coding ] {{Webarchive|url=https://web.archive.org/web/20120324114922/http://www.complextoreal.com/chapters/block.pdf |date = ngày 24 tháng 3 năm 2012}}{{en}}

[[Thể loại:Lý thuyết mã hóa]]