GT 5: Sơ lược lý thuyết mã hóa

NQH | 26/01/2010 |

5. Sơ lược lý thuyết mã hóa

Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua”. Nếu câu nói đó được phát biểu lúc này, thì phải thay “vài thập niên qua” bằng “thế kỷ 20″. Bài này duyệt qua một số kiến thức cơ bản về lý thuyết mã hóa cần cho thử nhóm.

5.1. Ý tưởng của Shannon (và Hamming)

Ý tưởng chính của lý thuyết mã hóa là thêm thông tin vào từng thông điệp trước khi gửi đi để bên nhận có thể tự phát hiện lỗi hoặc thậm chí tự sửa lỗi xảy ra trên đường truyền. Hai tham số chính của một mã là tỉ lệ (rate) của thông tin nguyên thủy trên thông tin gửi đi, và khả năng chịu đựng lỗi — số lỗi tối đa mà mã có thể dùng để kiểm tra hoặc sửa lỗi.

Cụ thể hơn, giả sử ta làm việc trên an-pha-bê ${\Sigma}$ . Trong truyền thông số thì thông thường ${\Sigma = \{0,1\}^m}$ với số tự nhiên ${m}$ nào đó vì thường chỉ có 2 bits ${0}$ và ${1}$ . Trong lý thuyết mã hóa thì ${\Sigma}$ có thể tổng quát hơn, là một trường ${\mathbb F_q}$ chẳng hạn. Chuyển từ an-pha-bê ${\mathbb F_q}$ sang an-pha-bê nhị phân không khó khăn gì. Nhưng ta cứ xét một an-pha-bê tổng quát trước đã. Giả sử mỗi thông điệp gửi đi có chiều dài ${k}$ , nghĩa là mỗi thông điệp gửi đi là một vector trong ${\Sigma^k}$ . Thay vì gửi một thông điệp ${{\bf x} \in \Sigma^k}$ , ta gửi ${{\bf y} = E({\bf x})}$ là ảnh của ${{\bf x}}$ dưới ánh xạ mã hóa ${E: \Sigma^k \rightarrow \Sigma^n}$ . Chúng ta cần ${{\bf y}}$ chứa nhiều thông tin hơn ${{\bf x}}$ , để cho bên nhận — dù có nhận một bản bị lỗi của ${{\bf y}}$ — thì vẫn có thể hồi phục lại ${{\bf x}}$ . Do đó ${n > k}$ .

Tập ${C \subset \Sigma^n}$ tất cả các ảnh của ${\Sigma^k}$ được gọi là mã sửa lỗi (error-correcting code, hoặc ECC cho gọn). Tỉ lệ ${R(C) = k/n}$ là tỉ lệ của mã, ${k}$ là số chiều của mã, và ${n}$ là độ dài mã (block length). Mỗi thành viên của ${C}$ được gọi là một mã tự (codeword). Khoảng cách (distance) của mã là khoảng cách Hamming nhỏ nhất giữa hai mã tự. Cụ thể hơn, gọi ${\Delta(c_1,c_2)}$ là khoảng cách Hamming giữa hai vectors trong ${\Sigma^n}$ , thì

$\displaystyle \text{dist}(C) = \min_{c_1 \neq c_2 \in C} \Delta(c_1,c_2).$

Còn khoảng cách tương đối của mã là

$\displaystyle \delta(C) = \frac{\text{dist}(C)}{n}.$

Nếu ${\Sigma = \mathbb F_q}$ thì ta gọi ${C}$ là mã ${(n,k)_q}$ . Và nếu cụ thể hơn ta biết ${\text{dist}(C) \geq d}$ thì ta gọi ${C}$ mã ${(n,k,d)_q}$ .

Mục đích chính của một mã là làm sao cho bên nhận có thể xây dựng lại mã tự đã được gửi, cho dù đường truyền có thay đổi vài vị trí của vector ${{\bf y}}$ . Ví dụ, ${{\bf y} = (y_1, \dots, y_n)}$ , thì mỗi ${y_i}$ là một vị trí của ${{\bf y}}$ .

Yêu cầu cơ bản nhất là giải mã duy nhất (unique decoding): bộ giải mã phải giải mã ra được đúng mã tự đã gửi, hoặc báo rằng không giải mã được. Giả sử có tổng cộng ${\rho_Un}$ vị trí của ${{\bf y}}$ bị lỗi. (Ví dụ, nếu ${{\bf y}}$ là vector nhị phân thì ${\rho_Un}$ là tổng số bits bị lỗi; Và, ${\rho_U}$ là tỉ lệ tổng số bits lỗi trên tổng số bits gửi.) Câu hỏi chính là: mã của chúng ta có thể “chịu đựng” được ${\rho_U}$ lớn cỡ nào? Chặn thông tin (information theoretic bound) dễ dàng cho ta biết ${\rho_Un \leq n-k}$ , do đó

$\displaystyle \rho_U \leq 1 - R. \ \ \ \ \ (1)$

Đến đây ta đã thấy trade-off (tiếng Việt là gì?) chính giữa tỉ lệ của một mã và độ chịu đựng lỗi của nó. Chúng ta muốn tỉ lệ ${R}$ gần với ${1}$ vì như vậy ta tốn ít băng thông thừa; nhưng khi ${R}$ gần với ${1}$ thì độ chịu lỗi tiến đến ${0}$ . Ngoài ra, nếu bên nhận nhận được một vector nằm ngay giữa hai mã tự thì không biết giải mã thành từ nào. Do đó, nếu ta cố chấp yêu cầu mã phải có tính giải mã duy nhất thì độ chịu đựng lỗi còn bị ép xuống nữa:

$\displaystyle \rho_U < \frac{\text{dist}(C)}{2n}.$

Chặn Singleton nói rằng ${\text{dist}(C) \leq n-k+1}$ , do đó ${\frac{\text{dist}(C)}{2n} \leq \frac{1-R}{2} + \frac 1 n}$ . Điều này cho thấy ép buộc tính chất giải mã duy nhất đẩy chúng ta ra rất xa chặn thông tin (1). Nói cách khác, để luôn luôn giải mã duy nhất được thì chúng ta phí rất nhiều băng thông, chí ít là gấp đôi cần thiết.

5.2. Mã giải theo danh sách

Cuối thập niên 1950, Elias và Wozencraft đề xuất một giải pháp gọi là giải mã danh sách (list-decoding) rất đơn giản và thú vị. Ý tưởng chính như sau. Cái chặn ${\frac{\text{dist}(C)}{2n}}$ là do các điểm tiếp xúc giữa các quả cầu Hamming bán kính ${\frac{\text{dist}(C)}{2}}$ với tâm là các mã tự. Nhưng trong toàn bộ không gian ${\Sigma^n}$ thì các điểm tiếp xúc này chiếm một lượng cực kỳ nhỏ. Nếu ta xét các điểm không nằm trong các quả cầu Hamming này, thì đa số chúng đều gần một mã tự nào đó hơn tất cả các mã tự khác, mặc dù khoảng cách từ một điểm đến mã tự gần nhất có thể xa hơn ${\frac{\text{dist}(C)}{2}}$ nhiều.

Vì thế, nếu chúng ta dùng phép giải mã cự ly ngắn nhất (minimum distance decoding) thì chúng ta có thể chịu đựng được tỉ lệ lỗi lớn hơn ${\frac{\text{dist}(C)}{2n}}$ nhiều, miễn là vector nhận được không nằm trong xóm nhà lá gần điểm tiếp xúc giữa hai quả cầu Hamming nào đó. Tiếc rằng giải mã cự ly ngắn nhất là một bài toán không khả thi và thậm chí không xấp xỉ được trong một tỉ lệ tốt.

Elias-Wozencraft đề xuất là, với tỉ lệ lỗi ${\rho}$ cho trước (nghĩa là giả sử có nhiều nhất ${\rho n}$ lỗi), thì thuật toán giải mã đưa ra một danh sách các mã tự trong bán kính ${\rho n}$ của vector nhận. Nếu ${\rho n}$ thật sự là tổng số lỗi lớn nhất có thể có, thì mã tự được gửi chắc chắn nằm trong danh sách này. Ngoài ra, nếu mã giải theo danh sách (list-decodable code) này được thiết kế tốt thì danh sách này thường là chỉ có một mã tự trong đó và vì thế giải mã là duy nhất với đa số các vectors được nhận. Khác với giải mã cự ly ngắn, giải mã danh sách lại là bài toán khả thi về mặt tính toán, và thậm chí chúng ta có thể đạt gần sát chặn thông tin (1). Đây là một nhánh nghiên cứu rất quan trọng trong chục năm đổ lại đây. Ngoài ứng dụng trong lý thuyết mã hóa thì còn ứng dụng trong lý thuyết độ phức tạp, thử thuộc tính (property testing), và các PCP. Xem thêm survey của Madhu Sudan và luận án của Venkat Guruswami (luận án được giải luận án xuất sắc nhất của ACM năm 2002). Hai bài báo của Parvaresh-Vardy và của Guruswami-Rudra là các phát triển (rất mạnh) gần đây nhất về giải mã danh sách.

5.2. Mã hồi phục danh sách

Trong ngữ cảnh của thử nhóm thì chúng ta lại cần một tổng quát hóa của khái niệm mã giải theo danh sách gọi là mã hồi phục danh sách (list-recoverable codes), do Guruswami và Indyk đề xuất ở FOCS 2001.

Định nghĩa 1 (Mã hồi phục danh sách) Cố định ${0 < \alpha \leq 1}$ . Gọi ${l, L}$ là các số nguyên dương. Một mã ${C \subset \Sigma^n}$ được gọi là mã hồi phục danh sách với các tham số ${(\alpha, l, L)}$ nếu nó thỏa tính chất sau đây. Cho ${n}$ tập hợp bất kỳ ${S_1, \dots, S_n}$ các ký tự, nghĩa là ${S_i \subset \Sigma}$ , trong đó ${|S_i| \leq l}$ . Tồn tại nhiều nhất là ${L}$ các mã tự ${{\bf c} = (c_1,\dots, c_n) \in C}$ thỏa mãn ${c_i \in S_i}$ với ít nhất ${\alpha n}$ các vị trí ${i}$ .

Mã giải theo danh sách chính là mã hồi phục danh sách với ${l=1}$ . Khi ${l=1}$ thì bộ ${S_1,\dots, S_n}$ đại diện cho vector mà bên nhận nhận được, ${(1-\alpha)}$ là tỉ lệ các vị trí bị lỗi, và ${L}$ số nhiều nhất các mã tự nằm trong quả cầu Hamming với bán kính ${(1-\alpha)n}$ có tâm là vector nhận.

Để đơn giản hóa thảo luận ở đây, ta sẽ chỉ dùng một trường hợp đặc biệt của kết quả của Parvaresh-Vardy. Trường hợp đặc biệt này đã được chứng minh trong bài báo của Guruswami-Sudan hồi 1999, áp dụng cho bộ mã lừng danh Reed-Solomon. Do đó trước hết hãy định nghĩa bộ mã RS.

Ở trên ta định nghĩa một bộ mã ${C}$ là một tập con của ${\Sigma^n}$ . Một loại mã rất quan trọng trong thực tế là mã tuyến tính, khi đó ${\Sigma = \mathbb F_q}$ là một trường hữu hạn, ${q}$ là một lũy thừa của một số nguyên tố, và ${C}$ là một không gian con tuyến tính của ${\Sigma^n}$ . Sở dĩ ta cần ${C}$ tuyến tính trên thực tế vì ta có thể tận dụng tính tuyến tính của ${C}$ để mã hóa và giải mã nhanh với các phép biến đổi tuyến tính thông thường. Một mã tuyến tính với độ dài ${n}$ , số chiều ${k}$ , trên trường ${\mathbb F_q}$ sẽ được ký hiệu là mã ${[n,k]_q}$ . Nếu khoảng cách Hamming giữa hai mã tự bất kỳ ít nhất là ${d}$ , thì ta gọi mã này là mã ${[n,k,d]_q}$ .

Bộ mã Reed-Solomon (RS) là một bộ mã ${[n,k]_q}$ với ${k\leq n \leq q}$ , định nghĩa như sau. Mỗi một thông điệp ${{\bf m} = ( m_0, \dots, m_{k-1} ) \in \mathbb F_q^k}$ có thể xem như một đa thức bậc ${k-1}$ trên vành ${\mathbb F_q[X]}$ :

$\displaystyle P_{\bf m}(X) = m_0 + m_1X + \cdots + m_{k-1}X^{k-1}.$

Mã RS là một ánh xạ ${RS: \mathbb F_q^k \rightarrow \mathbb F_q^n}$ định nghĩa như sau. Cố định ${n}$ phần tử khác nhau ${\alpha_1, \dots, \alpha_n \in \mathbb F}$ . (Đây là lý do tại sao ta cần ${q \geq n}$ .) Định nghĩa:

$\displaystyle RS({\bf m}) = ( P_{\bf m}(\alpha_1), \dots, P_{\bf m}(\alpha_n) ).$

Một đa thức bậc ${k-1}$ có nhiều nhất ${k-1}$ nghiệm trên trường bất kỳ. Do đó hai đa thức khác nhau chỉ có thể trùng giá trị ở nhiều nhất là ${\leq k-1}$ điểm ${\alpha_i}$ . Vì thế, mã RS có khoảng cách ít nhất là ${d=n-k+1}$ . Vì thế, mã RS là một mã ${[n, k, n-k+1]_q}$ . (Sự tuyến tính của RS là hiển nhiên.) Mã RS đạt đến chặn Singleton, và vì thế còn được gọi là một mã phân ly khoảng cách tối đa (maximum distance separable code). Mã RS có rất nhiều ứng dụng trên thực tế vì có các thuộc tính đại số dễ mến. Các ứng dụng bao gồm các mã trên CDs, DVDs, truyền thông trên cáp, không gian, vân vân.

Điểm thú vị là mã RS cũng là một mã hồi phục danh sách tốt. Chúng ta sẽ chỉ phát biểu định lý sau đây với ${q}$ là một lũy thừa của ${2}$ , mặc dù định lý đúng cho bất kỳ lũy thừa nguyên tố nào. Đại khái, định lý nói rằng RS là một mã hồi phục danh sách với các tham số ${(1,l, O(nl/k))}$ mà thời gian giải mã là poly ${(q,l)}$ .

Định lý 2 (Guruswami-Sudan) Xét ${l}$ là một số nguyên dương bất kỳ, ${q}$ là một lũy thừa tùy ý của ${2}$ thỏa ${1<k\leq n\leq q}$ , và ${kl<n}$ . Thì, tồn tại một thuật toán thỏa tính chất sau đây. Cho ${n}$ tập con bất kỳ ${S_1, \dots, S_n \subset \mathbb F_q}$ với ${|S_i| \leq l, \forall i}$ . Thuật toán sẽ in ra tất cả các mã tự ${{\bf c} = (c_1,\dots,c_n)}$ của mã RS ${[n,k]_q}$ thỏa tính chất ${c_i \in S_i, \forall i}$ . Ngoài ra, luôn luôn có nhiều nhất ${O(nl/k)}$ các mã tự như vậy, và thuật toán chạy trong thời gian poly ${(q,l)}$ .

5.3. Thêm về mã Reed-Solomon

Mã RS có vài tính chất quan trọng mà chúng ta sẽ dùng vào việc thiết kế thuật toán thử nhóm giải mã nhanh. Trong giới hạn bài này, ta sẽ không chứng minh định lý Guruswami-Sudan mà chỉ dùng nó như một “hộp đen”. Đó là phần giải mã. Còn phần mã hóa thì ta cũng cần mã hóa nhanh và sẽ thảo luận một chút về nó.

Nhớ rằng mỗi mã từ của mã RS có thể viết dưới dạng

$\displaystyle RS({\bf m}) = ( P_{\bf m}(\alpha_1), \dots, P_{\bf m}(\alpha_n) ),$

trong đó

$\displaystyle {\bf m} = ( m_0, \dots, m_{k-1} ) \in \mathbb F_q^k$

và

$\displaystyle P_{\bf m}(X) = m_0 + m_1X + \cdots + m_{k-1}X^{k-1}.$

Do đó, nếu ta định nghĩa ma trận sinh ${{\bf G}}$ như sau

$\displaystyle {\bf G} = \begin{bmatrix} 1 & 1 & \cdots & 1\\ \alpha_1^1 & \alpha_2^1 & \cdots & \alpha_n^1\\ \vdots & \vdots & \cdots & \vdots \\ \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1} \end{bmatrix}$

thì ta có

$\displaystyle RS({\bf m}) = {\bf mG}.$

Ma trận ${k \times n}$ ${{\bf G}}$ còn được gọi là ma trận Vandemonde, có nhiều tính chất thú vị và ứng dụng khắp mọi nơi, bao gồm trong biến đổi Fourier. Mỗi mã từ được “đánh chỉ số” bằng một vector ${{\bf m} \in \mathbb F_q^k}$ . Có tổng cộng ${q^k}$ mã từ, và tính mã từ từ một vector chỉ số ${{\bf m}}$ chỉ tốn thời gian poly ${(q,n)}$ . Cũng nhớ rằng mã RS là một mã tuyến tính ${[n,k,n-k+1]_q}$ . Do đó, khoảng cách tương đối của mã là ${1-\frac k n + \frac 1 n}$ .

Chủ đề : Combinatorics, Lý thuyết mã hóa, Thuật Toán and tagged Giải mã, Lý thuyết mã hóa, Mã Reed-Solomon, Thử nhóm. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

3 Comments

Minh Quan

Posted 05/11/2010 at 9:09 am | Permalink

Thanks so much for your information. I already knew how to define the RS code.
But in your sesson not showing the way how RS code can correct data when nose occur during transportation.
Please, send to me some explaination. I need to master this sesson.
Thanks you so much for best support.
P/S: Reply via ngodaoki18@yahoo.com

Reply
Ngô Quang Hưng

Posted 05/11/2010 at 9:35 am | Permalink

Chào Minh Quan, bạn có thể tìm thêm thông tin về các thuật toán giải mã mã RS ở đây. Cái dễ đọc nhất có lẽ là syndrome decoding.

Reply
Phan Dương Hiệu

Posted 05/11/2010 at 5:17 pm | Permalink

Hi Minh Quan,

Thuật toán giải mã có thể được tóm lược như sau:

Theo như phần anh Hưng trình bày phía trên, mỗi bản mã tương ứng với 1 đa thức $P$ bậc $k$ . Do vậy việc giải mã là việc tìm lại đa thức $P$ .

Một bản mã $RS(m)$ cho ta $n$ giá trị của $P$ tại $n$ điểm. Do vậy nếu không có lỗi thì chỉ cần $n > k$ là ta có thể phục hồi lại đa thức $P$ (đa thức bậc $k$ có thể xác định từ $k+1$ giá trị tại $k+1$ điểm), tức là có thể giải mã.

Bây giờ ta biết sẽ có $e$ lỗi trên đường truyền, tức là trong số $n$ điểm sẽ có $e$ điểm không tương ứng với giá trị thực của đa thức $P$ . Nếu ta xác định được vị trí của $e$ lỗi thì ta chỉ cần loại bỏ chúng và như vậy với $n> k+ e$ là sẽ phục hồi được đa thức P. Vấn đề là ta không biết vị trí của $e$ lỗi (có thể ở các vị trí tùy chọn). Câu hỏi đặt ra là $n$ cần lớn bao nhiêu để ta có thể xây dựng lại $P$ .

Có thể chứng minh được với $n > k+ 2e$ thì sẽ giải mã được. Cách khôi phục lại là như sau:

Cho $n (n > k+ 2e)$ giá trị $(v_1,\dots,v_n)$ trong đó có ít nhất $(n-e)$ vị trí $i$ tại đó giá trị $v_i = P(\alpha_i)$ , với $P(x)$ là một đa thức bậc $k$ . Mục đích xác định đa thức $P(x)$ .

Xử dụng kỹ thuật thêm biến để xóa sổ sự mù mờ về vị trí của $e$ lỗi. Gọi $g(x)$ là một đa thức bậc cao nhất là $e$ thỏa mãn tính chất $g(\alpha_j) = 0$ nếu $v_j$ khác $P(\alpha_j)$ (có nhiều nhất $e$ điểm thỏa mãn). Khi đó, với mọi $i$ ta đều có $P(\alpha_i) g(\alpha_i) = g(\alpha_i)v_i$ . Đa thức $Pg$ có bậc cao nhất $k+e$ . Do đó ta có $n$ phương trình tuyến tính với $k+2e +1$ biến (các biến là các hệ số của $Pg$ và của $g$ , hệ số cao nhất của $g$ có thể cho bằng 1). Do vậy ta sẽ giải được phương trình này (do $n > k+ 2e$ ). Tính được $Pg$ và $g$ , ta tìm lại được $P$ , tức là giải mã được.

Reply