Bài giảng Mã hóa và giải mã LDPC

MÃ HÓA VÀ GIẢI MÃ LDPC 
NỘI DUNG 
KIẾN TRÚC MÃ LDPC 
2. ĐỒ HÌNH TANNER 
MÃ HÓA 
3.1 Mã hóa sử dụng ma trận sinh G 
3.2 Mã hóa sử dụng ma trận chẵn lẻ H 
4. GIẢI MÃ 
1. KIẾN TRÚC MÃ LDPC 
Mã LDPC (Low-Density Parity-Check code – Mã kiểm tra chẵn lẻ mật độ thấp), hay còn gọi là mã Gallager, được đề xuất bởi Gallager vào năm 1962 
Về cơ bản đây là một loại mã khối tuyến tính có đặc điểm là các ma trận kiểm tra chẵn lẻ (H) là các ma trận thưa (sparse matrix), tức là có hầu hết các phần tử là 0, chỉ một số ít là 1. 
1. KIẾN TRÚC MÃ LDPC 
Các phương pháp xây dựng LDPC: 
Khởi tạo ma trận H toàn 0 sau đó cho giá trị 1 trượt ngẫu nhiên trên các cột 
Khởi tạo ngẫu nhiên ma trận H có trọng lượng cột bằng 
Khởi tạo ma trận H ngẫu nhiên có trọng số cột là và trọng lượng hàng xấp xỉ hoặc bằng 
Khởi tạo ma trận H như trên nhưng trong H không có 2 cột nào trùng nhau các vị trí của số 1 
Khởi tạo ma trận H như phương pháp 4 nhưng chiều dài chu kỳ Tanner phải lớn hơn 4 
Khởi tạo ma trận H như phương pháp 5 nhưng H có dạng H =[ , ]trong đó H2 phải là ma trận khá nghịch, tức là tồn tại ma trận nghịch đảo . 
2. ĐỒ HÌNH TANNER 
Đồ hình Tanner chính là một trong những cách được coi là hiệu quả nhất để biểu diễn mã LDPC. 
Đây là một đồ thị 2 phía , bên trái gọi là nút bit còn bên phải gọi là nút kiểm tra. Đối với mã khối tuyến tính thì đồ hình Tanner tỏ ra rất hiệu quả. 
2. ĐỒ HÌNH TANNER 
Trong đồ hình Tanner trên chúng ta có thể thấy rằng : 
+ Các nút bit và các nút kiểm tra được bố trí ở hai bên đối xứng nhau. 
+ Nút kiểm tra nối với bit khi và chỉ khi H (i ,j)=1 
2. ĐỒ HÌNH TANNER 
Chu kì Tanner là một đường khép kín liên kết từ một nút bất kỳ đi một vòng rồi quay lại chính nó. 
Ở ví dụ vừa rồi ta có chu kì Tanner là 
3. MÃ HÓA 
3.1 Mã hóa sử dụng ma trận sinh G 
Ta có : 
H = [A, I n-k ] 
- A là ma trận nhị phân (n-k) k - I n-k là ma trận đơn vị. 
Ma trận sinh được xác định: 
G = [I k , A T ] 
3.1 Mã hóa sử dụng ma trận sinh G 
Quá trình mã hóa đến đây chỉ đơn giản là thực hiện phép nhân giữa ma trận hàng đơn biểu thị chuỗi tin đầu vào với ma trận sinh tìm được: 
3.1 Mã hóa sử dụng ma trận sinh G 
Ví dụ: Chúng ta sẽ mã hóa từ mã có độ dài 10 với tỉ lệ mã LDPC ½ 
H = 
Trước hết ta đưa ma trận H về dạng bậc thang hàng (row-echelon): 
H r = 
Bước tiếp theo đưa ma trận về dạng bậc thang thu gọn (reduced row-echelon): 
H rr = 
Cuối cùng chúng ta sẽ hoán vị các cột để có một ma trận kiểm tra chẵn lẻ dạng chuẩn: 
H std = 
Từ đó ta có ma trận sinh G được tạo ra như sau: 
G = 
3.1 Mã hóa sử dụng ma trận sinh G 
Nếu sau khi thực hiện các bước của phép thử Gauss-Jordan mà cho ta một ma trận bậc thang hàng có một hàng toàn 0 thì ta được phép bỏ hàng đó. 
Khó khăn ở phương pháp này là ma trận G không bảo đảm được tính thưa như ma trận H. Phương trình mã hóa c = uG được thực hiện ở bộ mã hóa có độ phức tạp gần chính xác bằng n 2 phép tính. Đối với các mã có độ dài từ mã lớn thì bộ mã hóa sẽ trở nên cực kì phức tạp 
3.2 Mã hóa sử dụng ma trận chẵn lẻ H 
Ở phương pháp này người ta sử dụng trực tiếp ma trận H. Ý tưởng của phương pháp này là sử dụng trực tiếp hoán vị hàng cột sao cho vẫn dữ được đặc điểm của ma trận H 
Với k là kích thước bản tin, n là độ dài khối mã , m là số bít kiểm tra m=n-k , g gọi là độ phức tạp mã hóa. 
3.2 Mã hóa sử dụng ma trận H 
Trước hết chỉ hoán vị hàng và cột về dạng gần như tam giác dưới 
 Trong đó: 
T là ma trận tam giác dưới, kích thước (m-g)x(m-g)  B là ma trận kích thước (m-g) x g  A là ma trận kích thước (m-g) x k  C có kích thước g x k  D có kích thước g x g  E có kích thước g x (m-g). 
3.2 Mã hóa sử dụng ma trận H 
Ví dụ: Thực hiện mã hóa bản tin U=[11001] với chiều dài từ mã là 10 tỉ lệ ½, với H cho trước: 
3.2 Mã hóa sử dụng ma trận H 
Đưa về dạng tam giác dưới và ta hoán vị hàng 2 và hàng 3, cột 6 và cột 10 , chọn gap = 2 
3.2 Mã hóa sử dụng ma trận H 
phép thử G au s s- J ordan đượ c ứng dụng một lần để lo ại bỏ E tương đư ơng với việc nhân ma trận với ma trận H t 
Với 
3.2 Mã hóa sử dụng ma trận H 
Ta xét 
Và 
3.2 Mã hóa sử dụng ma trận H 
Ta có từ mã có độ dài bằng 10: c = [ ], c = [ u, ] , ở đây =[ ] và =[ ] được t ính như sau : 
3.2 Mã hóa sử dụng ma trận H 
 đượ c tính như sau : 
 =    = 1  1  0  1 =1 
 =   = 0  1  1 = 0 
 =    = 1  0  1  0 = 0 
Vậy từ mã thu được là c=[1 1 0 0 1 1 0 1 0 0 ] 
4. GIẢI MÃ 
Sử dụng phương pháp lặp để tính toán các biến trên đồ thị và có nhiều tên gọi như: 
Thuật toán tổng - tích – SPA (Sum - Product Algorithm). 
Thuật toán lan truyền niềm tin – BPA (Bilief Propagation Algorithm) 
Thuật toán chuyền bản tin -MPA (Massage Passing Algorithm). 
4. GIẢI MÃ 
Một số kí hiệu trọng giải thuật giải mã: 
c n là ký hiệu nút bit thứ n và z m là nút kiểm tra thứ m của đồ hình tanner. 
M n là tập các chỉ số của các nút kiểm tra nối tới nút bit c n trên đồ hình Tanner hay là các tập chỉ số m với H(m, n) = 1 trong ma trận H. 
N m là tập các chỉ số của các nút bit nối tới các nút kiểm tra z m trên đồ hình Tanner hay tập các chỉ số n với H(m,n) = 1 trong ma trận H. 
M n /m là tập hợp M n trừ đi các giá trị bằng m. 
N m /n là tập hợp N m trừ đi các gía trị bằng n. 
4. GIẢI MÃ 
Giải thuật giải mã tổng tích gồm việc tính hai xác suất có điều kiện. Xác suất thứ nhất ký hiệu là q mn (x ). 
Xác suất thứ hai ký hiệu là r mn (x ) 
Thuật toán giải mã LDPC cần phải có đầu vào là xác suất tiên ngiệm (A Priori Probability – APP) cho từng bit trong chuỗi bộ mã phát. Xác suất tiên nghiệm APP của bít c i là: 
4. GIẢI MÃ 
hoặc tỷ lệ ước lượng Likelihood Ratio (LR): 
Trong các tính toán người ta thường dùng tỷ lệ ước lượng theo hàm log (Log – Likelihood Ratio – LLR): 
với hàm log được lấy theo cơ số tự nhiên. 
4. GIẢI MÃ 
Đầu tiên thì xác suất q mn được khởi tạo bằng xác suất tiên nghiệm APP tương ứng. 
Trong một nửa lần lặp, từng nút c xử lý các tin đầu vào và gửi kết quả tới các nút liên quan. 
4. GIẢI MÃ 
Trong nửa lần lặp còn lại, từng nút z xử lý tin đầu vào và gửi kết quả đến các nút c liên quan . 
Sau khi đạt được số lần lặp cực đại cho trước hoặc một chỉ tiêu dừng lặp nào đó, bộ giải mã tính toán APP, LR hoặc LLR cho các bit c i . 
Chỉ tiêu dừng thường được sử dụng là , trong đó là từ mã thăm dò được giải. 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Thuật toán giải mã SPA là một thuật toán giải mã lặp. Gồm ba bước là bước khởi tạo, bước ngang, bước dọc. 
Bước 1 bước khởi tạo 
Các xác suất q mn (x) được khởi tạo bằng xác suất chính là xác suất tiên nghiệm APP của nút bit thứ n. Với y n là symbol thứ n thu được sau khi truyền qua kênh truyền. 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Đối với kênh AWGN điều chế BPSK thì xác suất tiên nghiệm này được tính như sau: 
Như vậy 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Đối với kênh AWGN và điều chế QPSK thì: 
Trong đó: 
 là phương sai của tạp âm Gauss 
 và lần lượt là thành phần cùng pha và vuông pha của symbol thu được. 
Sự hợp lệ của các bit thu sẽ được đặt trong vector f : 
Các xác suất được đặt trong ma trận Q có giá trị khởi tạo từ f như sau: 
Nếu ma trận kiểm tra chẵn lẻ có kích thướn thì ma trận Q có kích thước . 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Bước 2 bước ngang 
Bước ngang của giải thuật sẽ xác định giá trị các xác suất 
Trong đó: 
 - Vector c gồm tất cả các nút nối tới z m trừ nút bit thứ n là c n . 
Độ dài của vector bằng w r -1 có tổ hợp vector c có thể có. Nhưng chỉ có một số tổ hợp thỏa mãn 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Các xác xuất được đặt trong ma trận R: 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Bước dọc 
Bước dọc của thuật toán để xác định các xác suất 
Áp dụng công thức Bayes: 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Trong đó: được tính dựa theo 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Các xác suất được đ ặt trong ma trận Q: 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Xác định xác suất giả hậu nghiệm: 
Trong đó: được xác định dựa theo 
Các xác suất giả hậu nghiệm được đặt trong ma trận Q’: 
Thuật toán giải mã tổng tích trên miền xác suất SPA. 
Từ các xác suất giả hậu nghiệm này sẽ xác định được giá trị từ mã 
Cuối cùng là kiểm tra điều kiện và số vòng lặp. 
Nếu thì là từ mã hợp lệ và giải thuật kết thúc thành công. 
Nếu không: 
+ nếu đạt tối đa lần lặp thì giải thật kết thúc không thành công 
+ nếu chưa đạt tối đa lần lặp thì bắt đầu vòng lặp mới từ bước ngang