Chương 1. TỔNG QUAN VỀ MÃ KHỐI TUYẾN TÍNH Mã hóa kênh đóng vai trò vô cùng quan trọng trong kỹ thuật truyền dẫn thông tin số, trong đó mã khối là họ mã có khả năng sửa và phát hiện lỗi khá tốt đảm bảo độ chính xác cho hệ thống truyền tin. Tuy nhiên, phần lớn các họ mã khối trƣớc đây còn tồn tại những mặt hạn chế đáng kể nhƣ đánh đổi chất lƣợng giải mã để giảm lƣợng tính toán và tăng tốc độ mã hóa. Hoặc, để đạt chất lƣợng mong muốn, phải tăng độ phức tạp tính toán cũng nhƣ giảm tốc độ mã hóa.
Việc phân tích tính chất của mã khối cũng nhƣ đánh giá chất lƣợng giải mã của các thuật toán đóng vai trò vô cùng quan trọng trong việc cải thiện, tìm ra các phƣơng pháp kiểm soát lỗi nh m tăng chất lƣợng truyền dẫn.1 Mã khối nhị phân tuyến tính 1.1 Mô hình hệ thống thông tin Xét hệ thống thông tin số theo sơ đồ khối Hình 1. Ta có nguồn tin phát ra chuỗi tin đƣợc mã hóa kênh thành chuỗi , cụ thể là các kí hiệu thuộc tập kí tự của bộ mã kênh. Sau khi đƣa qua bộ điều chế ta có các tín hiệu dạng sóng để truyền trên kênh có nhiễu. Tại máy thu, tín hiệu thu đƣợc giải điều chế cho ta kí hiệu yi thuộc tập kí tự.
Sau bộ giải mã kênh ta phục hồi đƣợc ̂ là ƣớc lƣợng của thông tin ban đầu tại đích. 𝐮 Mã hóa 𝐜 𝐱 Nguồn Điều chế kênh Kênh truyền 𝐮 ̂ Giải mã 𝐜̂ Giải 𝐲 Đích kênh điều chế Hình 1. Hệ thống thông tin số LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Nhƣ vậy ta có kênh liên tục n m giữa hai khối điều chế và giải điều chế. Nếu xét kênh bao gồm cả hai khối này thì ta có mô hình kênh rời rạc.
Phía trƣớc kênh ta gọi là máy phát, phía sau kênh là máy thu. Vì kênh thực tế tồn tại nhiễu ảnh hƣởng đến thông tin truyền trên kênh và gây ra các sai lỗi tin, thể hiện ở sự sai khác của ƣớc lƣợng tin tại đích so với thông tin tại nguồn. Giả sử đầu ra của một nguồn tin là một dãy các bit nhị phân “0” và “1”. Trong trƣờng hợp mã khối thì dãy thông tin đầu ra từ một nguồn tin sẽ đƣợc chia thành các khối có chiều dài cố định và thƣờng đƣợc gọi là các bản tin.
Mỗi bản tin ký hiệu là gồm có bit thông tin. Nhƣ vậy, tổng cộng chúng ta có bản tin khác nhau có thể có và chúng có thể đƣợc thể hiện là các bộ vectơ thành phần, trong đó mỗi thành phần của vectơ là “0” và “1”. Bộ phận mã hóa theo một quy luật nào đó sẽ ánh xạ bản tin thành một vectơ thành phần ( - tuples) với (. Khi đó đƣợc gọi là từ mã hay vectơ mã) của bản tin.
Ứng với bản tin sẽ có từ mã khác nhau. Tập hợp từ mã này đƣợc gọi là một mã khối. Để mã khối có thể giải mã đƣợc, từ mã luôn là các từ mã độc lập tuyến tính. Do đó, sẽ có ánh xạ 1:1 giữa một bản tin và một từ mã.
Đối với một mã khối có từ mã và mỗi từ mã có chiều dài , việc lƣu lại bảng mã để phục vụ cho giải mã khó khăn khi lớn. Tồn tại họ mã có cơ chế hoạt động dễ dàng hơn đó là mã khối tuyến tính [57]. Định nghĩa: Một mã khối có chiều dài gồm từ mã đƣợc gọi là mã tuyến tính khi và chỉ khi từ mã hình thành một không gian vectơ con chiều của không gian vectơ gồm tất cả các vectơ thành phần. Hệ quả: Mã khối nhị phân đƣợc gọi là tuyến tính khi và chỉ khi kết quả cộng modulo 2 của hai từ mã cũng là một từ mã thuộc bộ mã đó.
Tính chất: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 - Tổ hợp tuyến tính của các từ mã bất kỳ cũng là một từ mã, các bộ mã khối tuyến tính luôn có từ mã bao gồm toàn ký hiệu “0”. - Khoảng cách Hamming giữa các từ mã là số các vị trí khác nhau giữa chúng ta có |{ | }|. - Khoảng cách Hamming tối thiểu của một mã khối tuyến tính b ng trọng số của từ mã có trọng số thấp nhất. Khoảng cách tối thiểu đƣợc định nghĩa là hay có thể đƣợc diễn tả b ng , vì từ mã là tuyến tính nên là một từ mã và.
Tính chất này biểu hiện việc xác định khoảng cách tối thiểu (khả năng phát hiện và sửa lỗi) của mã khối tuyến tính. - Điều kiện sửa lỗi của bộ mã:. - Khả năng sửa lỗi của bộ mã: Bộ mã có khả năng sửa tối đa là lỗi, mối quan hệ giữa và khảng cách Hamming tối thiểu đƣợc xác định: ⌊ ⁄ ⌋. - Khả năng phát hiện lỗi của bộ mã: Chức năng phát hiện lỗi của mã sẽ bị sai trong trƣờng hợp lỗi biến một từ mã đƣợc phát thành từ mã khác.
Điều này sẽ không xảy ra nếu có ít hơn hoặc b ng lỗi xuất hiện trong vị trí của từ mã. Vậy, khả năng phát hiện số bit lỗi của bộ mã là .2 Ma trận sinh Mã tuyến tính là một không gian con chiều của một không gian véctơ thành phần. Do vậy có thể tìm đƣợc từ mã độc lập tuyến tính trong , chẳng hạn g1 , g2 , …, g sao cho mỗi từ mã trong là một tổ hợp tuyến tính của từ mã này: c u1 g1 u2 g2 … u g (1.1) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 g1 g2 Với { } và [ ] là ma trận sinh của mã .1 Với mã khối Hamming (7,4), ma trận sinh là : 0 1 1 1 0 0 0 g1 g2 *1 0 1 0 1 0 0+ g3 (1.2) 1 1 0 0 0 1 0 1 1 1 0 0 0 1 g4 Với mã khối Golay (23,12), ma trận sinh có dạng: 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 Golay 23.3) Nếu là thông tin cần đƣợc mã hoá thì từ mã tƣơng ứng với thu đƣợc b ng cách lấy nhân với g1 g2 [ ] (1.4) g Vì các từ mã tƣơng ứng với các thông tin đƣợc sinh ra bởi theo cách nhƣ trên nên đƣợc gọi là ma trận sinh của bộ mã. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Chú ý Bất kỳ từ mã độc lập tuyến tính nào cũng có thể đƣợc dùng để làm ma trận sinh cho bộ mã.
Nói cách khác, các ma trận sinh khác nhau có thể biểu diễn cùng một bộ mã tuyến tính (hay còn gọi là không gian mã , hay ngƣợc lại một bộ mã tuyến tính có thể có nhiều ma trận sinh khác nhau biểu diễn. Tƣơng ứng với mỗi ma trận sinh thì sẽ có một phép mã hoá. Có nghĩa là ứng với hai ma trận sinh khác nhau sẽ có hai phép mã hoá khác nhau. Vì vậy, với cùng một bộ mã tuyến tính việc chọn ma trận sinh nào là rất quan trọng vì nó quyết định việc ánh xạ thông tin nào thành từ mã.3 Ma trận kiểm tra Đối với một ma trận sinh bất kỳ có hàng độc lập tuyến tính, tồn tại một ma trận có hàng độc lập tuyến tính.
Một vectơ bất kỳ trong không gian tạo bởi hàng của là trực giao với các hàng của và một vectơ bất kỳ trực giao với các hàng của sẽ thuộc không gian tạo bởi hàng của. Do đó, một tổ hợp gồm thành phần là một từ mã hợp lệ của mã đƣợc tạo ra bởi ma trận sinh khi và chỉ khi: [ ] (1.5) Với là ma trận chuyển vị của ma trận , ma trận đƣợc gọi là ma trận kiểm tra chẵn lẻ của mã. Khi từ mã truyền trên kênh có nhiễu tác động sẽ xảy ra lỗi ở vị trí các bit trong từ mã và thông tin nhận đƣợc sẽ bị sai lệch. Vì vậy, nguyên lý giải mã cũng đồng thời là cơ chế phát hiện và sửa lỗi của bộ mã bất kỳ dựa trên tính thống kê của kênh.
Tác động của nhiễu đƣợc biểu thị b ng những vectơ gây lỗi có cùng số chiều với không gian mã gọi là vectơ lỗi. Về nguyên tắc, khi giải mã tuyến tính trƣớc tiên phải xác định xem từ mã nhận đƣợc có sai hay không. Nếu sai, phải phân tích để xác định vị trí sai rồi sửa. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Giải mã mã khối Thông thƣờng, các phƣơng pháp giải mã đều dựa trên các giá trị rời rạc.
Các bit tin thu đƣợc b ng cách lƣợng tử hóa đầu ra của bộ giải điều chế thành hai mức “0” và “1”. Tuy nhiên, giá trị thực tế ở đầu ra bộ giải điều chế có thể đƣợc sử dụng thay vì lƣợng tử hóa chúng để xác định độ tin cậy của bit đƣợc quyết định [57].1 Các phương pháp giải mã mã khối a) Giải mã quyết định cứng Phƣơng pháp giải mã đơn giản nhất là giải mã quyết định cứng (HDD: Hard Decision Decoding) [57]. Để thuận tiện, trong Luận án gọi tắt HDD là giải mã cứng. Chuỗi tín hiệu đầu vào bộ giải mã ̂ (sau khi giải điều chế) bắt buộc phải nhận thông tin trực tiếp từ tin bị nhiễu.
Nghĩa là, việc giải mã chỉ sử dụng giá trị các bit nhận đƣợc lƣợng tử) chứ không phải là độ tin cậy của chúng đƣợc gọi là giải mã cứng. b) Giải mã quyết định mềm Thuật toán giải mã tính đến thông tin tin cậy hoặc sử dụng các giá trị xác suất hay giá trị hợp lý (likelihood) thay vì dữ liệu đƣợc lƣợng tử hóa tại đầu vào bộ giải mã đƣợc gọi là giải mã quyết định mềm (SDD: Soft Decision Decoding) - Gọi tắt là giải mã mềm [57].