Chương 1: Tổng quan: Trình bày tổng quan về mã LDPC và nguyên nhân của việc nghiên cứu tối ưu hóa mã LDPC. Chương 2: Cở sở lý thuyết: Trình bày các kiến thức về kỹ thuật sửa lỗi FEC, trình bày về mã LDPC và lý thuyết thuật toán di truyền. Chương 3: Thiết kế và xây dựng hệ thống: Từ yêu cầu đặt ra ở đề tài, trình bày về yêu cầu của hệ thống từ đó có sơ đồ hệ thống. Đi sâu giới thiệu từng khối.
Chương 4: Kết quả thực hiện: Trình bày và phân tích kết quả sau khi thực hiện thiết kế, xây dựng hệ thống và mô phỏng. Chương 5: Kết luận và hướng phát triển: Dựa vào kết quả đánh giá thu được từ Chương 4, rút ra kết luận cũng như hạn chế và sau đó định hướng phát triển của đề tài. 3 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT Để hiểu rõ và thiết kế được mã LPDC dựa trên thuật toán di truyền thì cần có các lý thuyết liên quan. Trong Chương 2 Cơ sở lý thuyết, nhóm thực hiện đề tài trình bài tổng quan về kỹ thuật sửa lỗi FEC, mã LPDC và thuật toán Genetic.
Sau đó đi sâu hơn về kỹ thuật mã hóa và các phương pháp giãi mã LPDC, đồ thị Tanner, cuối cùng là quá trình tối ưu thuật toán Genetic. TỔNG QUAN VỀ KỸ THUẬT SỬA LỖI FEC FEC (Forward Error Correction) là một phương pháp sửa lỗi trong truyền thông dữ liệu, cho phép phát hiện ở đầu thu và tự sửa một số lỗi trong dữ liệu truyền mà không cần gửi lại dữ liệu. Trong kỹ thuật FEC, bên gửi thực hiện mã hóa FEC trên một khối dữ liệu k bits và gửi đi n bits sau khi đã áp dụng FEC. Mã FEC được tính toán dựa trên dữ liệu gốc và được thêm vào trước khi việc truyền tin được thực hiện.
Bên nhận sử dụng mã thừa đã được thêm vào (mã FEC) để kiểm tra dữ liệu nhận được thông qua quá trình giải mã FEC. Nếu dữ liệu nhận được có lỗi, FEC cho phép người nhận phát hiện và sửa chúng mà không cần phải yêu cầu gửi lại dữ liệu. Nếu phía thu nhận thấy dữ liệu không có lỗi nào, thì nó sẽ tiến hành loại bỏ các bit dư thừa trước khi chuyển dữ liệu đến các lớp trên như trên Hình 2.1: Quá trình truyền nhận dữ liệu sử dụng FEC [2] FEC (Forward Error Correction) hiện nay có hai loại chính là mã khối (Block codes) và mã chập (Convolutional codes). Mã khối (Block codes) hoạt động trên các khối bit, trong đó có một nhóm các bits thông tin được mã hóa và một phần được thêm vào để tạo ra một khối dữ liệu lớn hơn, được truyền đi.
Sau đó, bên nhận sẽ kiểm tra và quyết định về tính chính xác của chuỗi nhận được dựa trên khối dữ liệu đó. Mã chập (Convolutional codes), còn được gọi là mã liên tục, hoạt động liên tục trên một luồng bit nhất định. Dữ liệu được phân chia thành các luồng thông tin có độ dài linh hoạt, kèm theo các ký tự kiểm tra chẵn lẻ, sau đó tiến hành mã hóa. Hiện nay, có 4 loại mã sửa lỗi được sử dụng phổ biến và được tạo ra dựa trên 2 loại mã FEC.
- Mã khối: gồm có 3 loại mã sửa lỗi là Hamming codes, LDPC codes, Reed- Solomon codes. - Mã chập: là Binary Convolution codes. TỔNG QUAN VỀ MÃ LPDC Trong những năm gần đây, công nghệ kỹ thuật lưu trữ, lĩnh vực mã hóa phát triển vượt bậc, để đáp ứng giải quyết các bài toán khó có yêu cầu khối lượng tính toán lớn và độ phức tạp cao. Điều đó dẫn đến sự phát triển đáng kể trong các bộ mã hóa, đặc biệt là trong việc chống lỗi và sửa lỗi.
Trong số tất cả các mã hóa khối, mã LDPC đang được sự quan tâm chú ý nhất cho sự trở lại vượt trội sau thời gian dài bị lãng quên. Qua nhiều quá trình thực nghiệm, con người đã chứng minh rằng mã LDPC hơn mã Turbo – một trong những mã hàng đầu hiện nay với kích thước và hiệu suất sửa lỗi cao hơn. Điều đáng chú ý là mã LDPC cũng ít phức tạp hơn các mã tiên tiến khác khi độ dài mã được tăng lên. Những kết luận từ nghiên cứu này đã khẳng định khả năng ứng dụng trong thực tế cũng như tiềm năng phát triển của mã LDPC, nơi mà hiệu suất mã hóa và khả năng sửa lỗi là yếu tố rất quan trọng.
Gallager đã đề xuất mã LDPC, còn được gọi là mã Gallager hoặc mã kiểm tra chẵn lẻ mật độ thấp và năm 1962 [3]. Khi mã này được gửi, các kết quả mô phỏng thời này không thể chứng minh khả năng kiểm soát lỗi cao của máy tính. Những ưu điểm của mã LDPC mới đã được công nhận sau đó.2: Ma trận kiểm tra chẵn lẻ của một mã LDPC (20,3,4) Mã LDPC là một khối tuyến tính (n,k) đặc trưng bởi một ma trận kiểm tra chẵn lẻ chủ yếu gồm bit ‘0’ và rất ít bit ‘1’. Điều này giúp mã LDPC hiệu quả trong việc sửa lỗi cho các khối dữ liệu có độ dài lớn.
Đặc điểm của mã LPDC Mã LDPC được biểu diễn theo dạng (n,j,k) hoặc (n,c,r) trong đó: - n là độ dài mã - j hoặc c là số bit ‘1’ trong mỗi cột của mã - k hoặc r là số bit ‘1’ trong mỗi hàng của mã Ma trận kiểm tra chẵn lẻ (H) trong mã LDPC là ma trận có kích thước m x n. Ma trận H, còn được gọi là mã ký tự, có các hàng biểu thị các phương trình kiểm tra và các cột biểu thị các bit trong từ mã. Ma trận H có mật độ số bit ‘1’ rất thấp và vị trí các bit ‘1’ có thể được chọn ngẫu nhiên tuân theo các ràng buộc j, k. Từ mã c, khi thảo mãn điều kiện sau: 𝑐 × 𝐻𝑇 = 0 (2.1) Ví dụ: Cho mã LDPC (7,3,4).
Ta thấy mã LDPC này có độ dài là n = 7, j = 3, k = 4, điều này có nghĩa là mã này có 4 ký tự mã xuất hiện ở 3 phương trình khác nhau như bên dưới. 1 1 1 0 1 0 0 H = [ 0 1 1 1 0 1 0] 1 0 0 1 1 0 1 Từ ma trận H trên, ta rút ra được các phương trình kiểm tra cho mỗi từ mã. Được biểu diễn như sau: 𝑐1 + 𝑐2 + 𝑐3 + 𝑐5 = 0 𝑐2 + 𝑐3 + 𝑐4 + 𝑐6 = 0 𝑐1 + 𝑐2 + 𝑐4 + 𝑐7 = 0 Dựa trên cách xây dựng ma trận kiểm tra chẵn lẻ (H), mã LDPC có thể được chia thành hai loại: mã LDPC đều và mã LDPC không đều. Mã LDPC đều (Regular LDPC codes): có ma trận H có cấu trúc đều và đơn giản.
Các hàng cũng như các cột trong ma trận H có cùng số lượng bit ‘1’, và mỗi bit trong từ mã tham gia vào cùng số lượng các phương trình kiểm tra chẵn lẻ. Ví dụ, việc xác định mã LDPC thường được xác định bằng cách dùng các khối ma trận đơn giản như ma trận chuẩn hóa hoặc ma trận vòng. 7 Mã LDPC không đều (Irregular LDPC codes): Trong loại này, ma trận H có cấu trúc không đều và phức tạp hơn. Số lượng bit '1' trong mỗi hàng và cột có thể khác nhau, cũng như số lượng bit trong mỗi từ mã có thể khác nhau trong số lượng phương trình kiểm tra chẵn lẻ.
Muốn tạo ra mã này các phương pháp thường được người ta sử dụng như xáo trộn (shuffling), ghép nối (concatenation) hoặc sử dụng ma trận H không đều được thiết kế riêng. Mã LDPC thông thường có dạng (𝑛, 𝑘) hoặc 𝐶(𝑛, 𝑗, 𝑘), trong đó n là độ dài của mã. Tốc độ mã của mã LDPC được tính toán theo công thức: 𝑅 = 1 – 𝑗/𝑘 (2.2) Mã LDPC đều dễ tạo hơn mã LDPC không đều cho hiệu suất lớn hơn ứng với chiều dài mã lớn hơn. Tuy mã LDPC không đều có hiệu quả tốt hơn mã LDPC đều nhưng mã LDPC không đều có tầng lỗi và độ phức tạp mã hóa cao hơn.
Ví dụ: Mã LDPC đều có ma trận H kích thước 3x7: 1 1 0 0 1 0 0 [0 1 1 0 0 1 0] 0 0 1 1 0 0 1 Trong ví dụ này, ma trận H có cấu trúc đều. Mỗi hàng và cột có cùng cố lượng bit ‘1’. Mỗi bit trong từ mã tham gia vào ba phương trình kiểm tra chẵn lẻ. Ma trận trong Ví dụ trên thuận tiện cho quá trình mã hóa dữ liệu cũng như giải mã vì có tính đơn giản.
Ví dụ: Mã LDPC không đều có ma trận H kích thước 3x7: 1 0 1 0 1 0 0 [0 1 1 1 0 1 0] 1 0 0 1 1 0 1 Trong ví dụ này, ma trận H có cấu trúc không đều. Ở mỗi hàng và cột có thể có số lượng bit ‘1’ không giống nhau. Số lượng phương trình kiểm tra phụ thuộc vào số bit trong từ mã. Mặc dù điều này làm việc mã hóa và giải mã tăng độ phức tạp, nhưng nó cũng làm cho cấu trúc linh hoạt và không đều hơn.
8 Ưu điểm [4]: - Hiệu suất gần tiệm cận giới hạn Shannon. - Dễ triển khai và tính toán đơn giản. - Khả năng xử lý lỗi tốt. - Linh hoạt và khả năng điều chỉnh.
- Xử lý lỗi burst. Nhược điểm [4]: - Yêu cầu tài nguyên tính toán cao. - Độ phức tạp trong thiết kế. - Yêu cầu kênh truyền thông rộng.
Ứng dụng của mã LPDC Một trong những lợi ích chính của mã LDPC là khả năng giải mã hiệu quả. Thuật toán giải mã của mã có thế tiếp cận rất gần với giới hạn Shannon, giới hạn tối đa của tốc độ truyền thông trong một kênh tạp âm. Với mức BLER (Block Error Rate) là 10-6. Điều này khiến mã LDPC trở thành một lựa chọn hữu ích trong các ứng dụng hiệu suất truyền thông cao và độ tin cậy cao là điều được yêu cầu.
Nó rất phổ biến trong các hệ thống không dây, mạng cáp quang, mạng di động, viễn thông vệ tinh và hệ thống lưu trữ dữ liệu.1(bảng 2 trang 4 [5]) tổng hợp các ứng dụng mã LPDC. Tiêu chuẩn IEEE 802.16e WiMAX, một tiêu chuẩn mạng không dây khu vực đô thị (WMAN) và tiêu chuẩn IEEE 802.11n WiFi, một tiêu chuẩn mạng không dây cục bộ (WLAN), đều sử dụng mã LDPC trong truyền thông không dây [5]. Cả hai tiêu chuẩn này sử dụng mã LDPC như một sơ đồ mã hóa kênh tùy chọn với nhiều tốc độ mã và độ dài mã khác nhau, giúp cải thiện hiệu suất truyền thông và độ tin cậy trong môi trường không dây. Mã LDPC cũng được sử dụng trong phát sóng video kỹ thuật số thông qua tiêu chuẩn vệ tinh DVB-S2.