Slide bài giảng mã hóa và giải mã LDPC
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.49 MB, 39 trang )
MÃ HÓA VÀ GIẢI MÃ
LDPC
NỘI DUNG
1. KIẾN TRÚC MÃ LDPC
2. ĐỒ HÌNH TANNER
3. 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:
1. Khởi tạo ma trận H tồn 0 sau đó cho giá trị 1 trượt ngẫu nhiên trên các cột
2. Khởi tạo ngẫu nhiên ma trận H có trọng lượng cột bằng
3. 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
4. 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
5. 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
6. 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, In-k ]
- A là ma trận nhị phân (n-k) k
- In-k là ma trận đơn vị.
• Ma trận sinh được xác định:
G = [Ik, AT ]
3.1 Mã hóa sử dụng ma trận sinh G
• Q 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):
Hr =
• Bước tiếp theo đưa ma trận về dạng bậc thang thu gọn (reduced row-echelon):
Hrr =
• 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
ch̉n:
Hstd =
• 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 tồ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 n2 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ử Gauss-Jordan đượ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 Ht
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
= =1010=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 tốn các biến trên đồ thị và có nhiều
tên gọi như:
Thuật tố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ã:
• cn là ký hiệu nút bit thứ n và zm là nút kiểm tra thứ m của đồ hình
tanner.
• Mn là tập các chỉ số của các nút kiểm tra nối tới nút bit cn 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.
• Nm 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.
• Mn/m là tập hợp Mn trừ đi các giá trị bằng m.
• Nm/n là tập hợp Nm 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à qmn(x).
• Xác suất thứ hai ký hiệu là rmn(x)
• Thuật tố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 ci là:
