Chương 1 MÃ SỬA SAI CÓ MA TRẬN KIỂM TRA MẬT ĐỘ THẤP LDPC 1. Một số mã sửa sai thông dụng Năm 1948 Claude E. Shannon đã phát hành những công trình nghiên cứu về lý thuyết toán học trong công nghệ truyền thông. Trong các công trình này Shannon phát triển các mô hình thuật toán cho phép giải quyết các vấn đề cơ bản trong truyền dẫn tín hiệu.
Nguồn tin: là nơi tạo ra tin M , với xác suất là fM (M = m).1: Mô hình hệ thống truyền tin số 22 1. Một số mã sửa sai thông dụng 23 của M được xác định như sau: ∑ H(M ) = − fM (m).1) m Mã hóa Nguồn: Bộ mã hóa nguồn loại bỏ những thông tin dư thừa của chuỗi thông tin đầu vào. Mã hóa kênh: Bộ mã hóa kênh ghép thêm thông tin dư thừa vào chuỗi dữ liệu đầu vào. Mục đích của việc ghép thêm thông tin dư thừa vào nhằm tăng khả năng tái tạo lại dữ liệu khi tín hiệu bị can nhiễu ở phía đầu thu.
Kênh: Hàm xác suất truyền dẫn của kênh được định nghĩa là fY /X (Y /X) như trong mô hình thuật toán kênh 1. Trong đó kênh truyền dẫn là kênh không nhớ. Có hai dòng mã sửa sai chính đó là mã chập và mã khối: Hình 1.2: Mô hình toán học kênh truyền dẫn • Mã chập thực hiện trên những dòng bít hoặc dòng symbol có độ dài tùy ý. Mã này thường được giải mã bằng thuật toán Viterbi, đôi khi một số thuật toán khác cũng được sử dụng.
Thuật toán giải mã Viterbi cho phép hiệu quả giải mã tối ưu khi tăng độ dài từ mã, tuy nhiên độ phức tạp giải mã cũng tăng theo độ dài từ mã. Mã chập cũng có thể trở thành mã khối nếu được thiết kế bằng phương pháp "gắn bit đuôi". Một số mã sửa sai thông dụng 24 • Mã khối thực hiện trên gói dữ liệu chứa một khối bít hay symbols có kích thước đã được xác định. Thời gian giải mã khối là hàm đa thức thời gian phụ thuộc vào kích thước khối của nó.
Mã chập đệ quy Mã chập đệ quy là trường hợp mã chập thông thường có một đường hồi tiếp về đầu vào. Mã chập đệ quy (RSC) có các bít thông tin được thể hiện trong từ mã ở đầu ra, vì vậy mã RSC còn được gọi là mã hệ thống. Mặt khác có thể coi bộ mã RSC là một bộ lọc đáp ứng xung vô tận (IIR). Quá trình giải mã chập có thể thực hiện bằng phương pháp giải mã bít cứng và giải mã bít mềm dựa trên thuật toán Viterbi.
Thuật toán giải mã bít mềm giải mã xác suất thông tin hậu nghiệm cực đại (MAP) mục đích là tìm xác suất P [u(t) = 1|y] và xác suất P [u(t) = 0|y] tại mỗi thời điểm t, đối với mỗi bít u(t) nhận được ở phía thu, khi một bít y được truyền qua kênh có nhiễu. Thuật toán MAP Thuật toán này tuần tự thực hiện các bước sau: • Dán nhãn các nhánh của giản đồ lưới bằng xác suất chuyển trạng thái γi,j (t); • Quét toàn bộ theo hướng thuận của giản đồ lưới để tính toán xác suất bắt đầu tại mỗi nút của giản đồ lưới αi (t); • Quét toàn bộ theo hướng ngược lại của giản đồ lưới để tính toán xác suất kết thúc tại mỗi nút của giản đồ lưới βi (t); 1. Một số mã sửa sai thông dụng 25 • Tính toán giá trị logarit tỉ số xác suất LLR của bít thông tin tại mỗi đoạn giản đồ lưới như sau: P [u(t) = 1|y] λ(t) = P [u(t) = 0|y] ∑ S →Sj :u=1 αi (t − 1)γi,j (t)βj (t) = log ∑ i ; (1. Thuật toán MAP có thể được tính toán trong miền logarit bằng cách lấy logarit hai vế ta được: γi,j (t) = log P (Si (t − 1) → Sj (t)|y(t)) (1.5) Mã Turbo Mã Turbo được cấu tạo bởi hai bộ mã hóa chập đệ quy (RSC), tại đầu vào giữa hai bộ mã RSC sử dụng bộ tráo ngẫu nhiên các bít mã đầu vào.
Quá trình giải mã Turbo là quá trình lặp giải mã giữa hai bộ mã hóa RSC, thông tin trích xuất tại đầu ra bộ mã 1 được chuyển đến đầu vào bộ mã hóa 2 sau khi đã đưa qua bộ giải tráo (ngược với qua trình tráo ở phía bộ mã hóa) và ngược lại. Bộ mã hóa Turbo có những ưu, nhược điểm sau: • Bộ mã hóa Turbo có khả năng sửa lỗi tốt với mức tỉ số tín hiệu trên tạp nhiễu S/N rất thấp. Khả năng giải mã của bộ mã Turbo 1. Một số mã sửa sai thông dụng 26 Hình 1.3: Sơ đồ bộ mã Turbo có thể tiến sát đến giới hạn Shannon là do có rất nhiều từ mã đầu ra bộ mã Turbo có hàm trọng nhỏ.
• Tuy nhiên cũng vì có nhiều từ mã hàm trọng nhỏ, mã Turbo có hiện tượng sàn lỗi (tại dải giá trị rất nhỏ BER không tăng khi tăng S/N trong một khoảng nhất định). • Khả năng sửa lỗi của mã Turbo tăng theo độ dài khối bít mã hóa và hiện tượng sàn lỗi sẽ suy giảm khi kích thước khung của bộ tráo tăng lên. Tuy tăng kích thước khối bít mã hóa không gây thêm độ phức tạp của bộ giải mã, nhưng sẽ gây ra hiện tượng trễ trong quá trình giải mã, điều này sẽ đòi hỏi bộ nhớ đệm của bộ giải mã phải tăng theo. • Độ phức tạp của mã Turbo KT C và bộ mã RSC KCC có cùng độ dài ràng buộc L được tính như sau: 1.
Một số mã sửa sai thông dụng 27 LT C ≈ 2 + LCC + log(Số lần lặp giải mã) Quá trình giải mã của bộ mã Turbo được thực hiện theo thuật toán giải mã lặp các giá trị của bít mềm vào ra giữa hai bộ mã RSC (SISO-MAP) như hình dưới đây.4: Thuật toán giải mã SISO-MAP • Đầu vào bộ giải mã là: – Các tỉ số xác suất LLR λu,i của các bít thông tin đến từ bộ giải mã thứ hai. – Các tỉ số xác suất LLR λc,i của các bít mã đến từ kênh truyền. • Đầu ra bộ giải mã là: – Các tỉ số xác suất LLR λu,o của các bít thông tin truyền qua bộ giải mã thứ hai. – Các tỉ số xác suất LLR λc,o của các bít mã không được bộ giải mã thứ 2 sử dụng.
Cấu trúc giải mã Turbo được mô tả trong hình 1. Một số mã sửa sai thông dụng 28 Hình 1.5: Cấu trúc giải mã Turbo Các xác suất đầu vào λu,i bộ mã hóa trên ban đầu được gán giá trị "0". Bộ giải mã trên sẽ thực hiện giải mã trước sau đó bộ giải mã dưới sẽ thực hiện giải mã dựa vào các thông tin từ kênh truyền và từ đầu ra bộ giải mã trên. Các bộ mã hóa Turbo gần đây được sử dụng trong các hệ thống thông tin vệ tinh [14,15], trong hệ thống Wimax [16], hay hệ thống viễn thông phân chia truy cập theo mã CDMA2000 [17].
Mã có ma trận kiểm tra mật độ thấp LDPC Năm 1963, Gallager [6, 18] phát minh họ mã có mật độ ma trận kiểm tra thấp LDPC (Low Density Parity Check) trong quá trình làm 1. Một số mã sửa sai thông dụng 29 luận văn tiến sĩ của mình tại học viện MIT. Tại thời điểm lúc đó, mã LDPC có rất ít ảnh hưởng đến hội đồng nghiên cứu mã kênh truyền dẫn, do khả năng sửa lỗi của họ mã này kém hơn nhiều so với mã Turbo [5], trong khi đó độ phức tạp của mã cao. Vì vậy, trong hơn một thập kỉ tiếp theo họ mã này không được tiếp tục phát triển.
Độ phức tạp của mã LDPC được đánh giá bởi Zyablov và Pinsker năm 1975 [19], trong khi đó Tanner [20] đưa ra phương pháp thiết kế cấu trúc lặp cho ma trận kiểm tra (Parity Check Matrix) và biểu diễn ma trận này dưới dạng đồ thị. Sipser và Spielman [21] giới thiệu ma trận kiểm tra sử dụng các đồ thị mở rộng. Tuy nhiên, trong những năm của thập kỉ 1990, sự quan tâm của hội đồng nghiên cứu mã kênh truyền đối với mã LDPC được khôi phục lại. Như tổng kết trong bảng 1.1, các mã LDPC đã trở thành đề tài nóng bỏng đối với hội đồng nghiên cứu mã kênh truyền dẫn.
Mackay và Neal [22, 23] thực nghiệm với mã LDPC có từ mã lớn và đã chứng minh rằng các mã LDPC có khả năng sửa lỗi cao hơn so với các mã turbo, khi truyền dẫn qua các kênh truyền có phân bố tạp âm trắng kiểu Gauss AWGN (Additive White Gaussian Noise). Bị thu hút bởi khả năng sửa lỗi của mã LDPC, họ đã tiếp tục nghiên cứu nhiều thuộc tính khác của họ mã LDPC. Thuật toán tiến triển hàm mật độ DE (Density Evolution) được phát minh bởi Richardson và các đồng nghiệp cho phép tính toán tiệm cận hiệu quả của các mã LDPC được sử dụng trong sửa lỗi dữ liệu qua kênh truyền AWGN. Sau đó Chung và các đồng nghiệp của mình [30,41] đã đơn giản hóa thuật toán DE.
Thuật toán DE ngày nay được sử dụng rộng rãi để dự đoán tiệm cận hiệu quả sử dụng các mã LDPC trong kênh AWGN và nó được sử dụng bởi nhiều nhà nghiên cứu như Fossorier, Chen và các 1. Một số mã sửa sai thông dụng 30 Bảng 1.1: Các mốc phát triển chính trong nghiên cứu mã LDPC 1948 Giới hạn của Shannon [24]; 1962 Các mã LDPC được phát minh bởi Gallager [18]; 1975 Tính toán độ phức tạp của các mã LDPC bởi Zhang [19] ; 1983 Đồ thị Tanner cho các mã LDPC của Tanner [20]; 1997 Hiệu quả của mã LDPC gần giới hạn Shannon, được thực hiện bởi Mackay [22]; 1998 Mã LDPC bất nhị phân được phát minh bởi Davey [25]; Mã LDPC không đều được thiết kế bởi Luby [26]; Richardson phát minh thuật toán giải mã dựa trên thuật toán FFT nhằm giảm độ tính toán phức tạp của quá trình giải mã LDPC; Thuật toán tiến triển hàm mật độ được phát minh bởi Richardson; 1999 Lentmaier phát minh mã LDPC tổng hợp G-LDPC [27]; 2001 Kou và đồng nghiệp thiết kế ma trận kiểm tra của LDPC có dạng hình học hữu hạn [28]; Giải mã LDPC bằng phương pháp đảo bit được thực hiện bởi Kou ; Ten Brink phát minh đồ thị EXIT [29]; Chung phát minh phương pháp tiến triển mật độ xấp xỉ hàm Gauss [30]; 1.