Chương 1. Tổng quan về fountain codes 1. Kênh truyền nhị phân có tính xóa (BEC) Kênh truyền nhị phân có tính xóa (binary erasure channel) là kênh truyền thông dụng được sử dụng trong lý thuyết mã hóa và thông tin. Trong kênh truyền này, bộ phát sẽ truyền các bit nhị phân | hay 0 còn bộ thu sẽ nhận được bit đã phát hoặc nhận được thông tin là bit này đã bị xóa.
Kênh truyền BEC được giới thiệu vào năm 1954 bởi Peter Elias ở đại h c MIT [4]. Kênh truyền tổng quát của BEC được g i là packet erasure channel với đơn vị thông tin được tính là gói thay vì bit có các đặc tính lý thuyết tương tự BEC là kênh truyền được sử dụng phan mô phỏng ở chương 3 của luận văn này. Dung lượng kênh truyền BEC với xác suất xóa p, Một kênh truyền BEC luôn được định nghĩa với một xác suất xóa Pe (erasure probability). Gia sử X là một biến ngẫu nhiên được phát với alphabet {0,1} với xác suất phát 0 và 1 lần lượt là p và q tương ứng.
G i Y là biến nhận được thi alphabet của biến này là {0,1, e}, trong đó e là gói xóa (erasure symbol). Kênh truyền này được đặc tả bởi các hàm xác suất có điều kiện (conditional probability) như trong giản đồ trong Hình 1. | = ory Pe ` = _ >> X‹ wi} ` Pp, 0< ~Ũ |~p.1 : Kênh truyền BEC với xác suất xóa P, HVTH: Đỗ Lê Nam Trang 11 C1. Tông quan về fountain codes GVHD: TS.
Hồ Văn Khương Ngoài cách mô tả bằng một kênh truyền BEC băng giản đồ như Hình 1.1, ta còn thể đặc trưng kênh truyền này bằng các phương trình xác suất có điều kiện như bên dưới [5].(1—pe) Luong thong tin I(X|Y) = H(X) + H(Y) — H(X,Y) = —p X log, p — q X08; q — De X Ì08; De — P X De X (1.3 Ta có I(XỊY) = HX) x (1 — pe) = (—p X log,p — q X log, q ) X (1— De) (14) Dung lượng của kênh truyền (channel capacity) là maximum của /(X|Y) với (1 — ø,) là hằng số thì theo lý thuyết Entropy trong [5], thì H(X) đạt giá trị lớn nhất khi p = q = -. Với giá trị này thi H(X) = 1, dẫn đến I(X|Y) = (1 — p,), chính là dung lượng của kênh truyền xóa (BEC) có xác suất xóa là De- 1. Ma Luby Transform (LT code) 1. Giới thiệu ma LT code Mã Luby Transform (LT code) được phát minh bởi Michael Luby vào năm 1998 và được công bố vào năm 2002, được xem là loại mã hiện thực (practical code) đầu tiên thuộc h HVTH: Đỗ Lê Nam Trang 12 C1.
Tông quan về fountain codes GVHD: TS. Hồ Văn Khương các fountain codes [3]. C ng giống như các loại fountain codes khác, mã LT được xây dựng trên cơ sở các bipartite graph để làm tăng tốc độ giải mã. Đặc trưng cơ bản tạo nên sự đơn giản của mã LT trong h_ fountain codes, là việc sử dụng toán tử XOR trong ca thuật toán mã hóa và giải mã.
Mã hóa LT code Quá trình mã hóa (encoding process) khởi động băng việc chia thông điệp chưa được ma hóa (uncoded message) thành k gói có kích thước bằng nhau. 1 Bậc đ, 1 < d <n, của gói tiếp theo được ch n lựa một cách ngẫu nhiên. =1 Có chính xác đ gói từ các gói thông tin chưa mã hóa được ch_n lựa ngẫu nhiên. El G i M; là gói thứ i của thông điệp cần phát đi thì thành phan dữ liệu của gói mã hóa kế tiếp được tính bởi công thức Mi, 8 M,;@M,;; ---: @ Mig (15) Trong đó, {i,, iz, ., ig} là các chỉ số được ch n lựa ngẫu nhiên cho d gói được ch n lựa cho gói đó.
[1 Giải thuật mã hóa c ng chèn một prefix, vào cuối của phan dữ liệu mã hóa trong gói được phát đi các thông tin về số lượng gói (n) có trong thông điệp, bậc d và các chỉ số {í¡, in, ., ig} liên quan đến gói được mã hóa. El Cuối cùng, gói này được bảo vệ bởi một loại mã sửa lỗi nào đó (error correcting code), chang hạn như mã CRC trước khi được phát di. -] Quá trình mã hóa được lặp lại cho đến khi bộ thu có thể phục hồi được thông điệp phát ban đầu thành công. HVTH: Đỗ Lê Nam Trang 13 C1.
Tông quan về fountain codes GVHD: TS. Hồ Văn Khương Giải ma LT code Quá trình giải mã LT (decoding process) c ng sử dụng toán tử XOR để khôi phục các gói được mã hóa theo thủ tục như sau: H Nếu gói hiện tại không “sạch”, tức là bộ thu không đảm bảo nhận đúng tín hiệu đã phát, hoặc gói này đã được nhận trước đó, thì gói sẽ bi loại bỏ (discarded). H Nếu bậc đ của gói “sạch” hiện tai lớn hơn 1, nó sẽ được xử lý dựa trên tất cả các gói đã được giải mã hoàn toàn (fully decoded packet) trong vùng nhớ lưu trữ dữ liệu (message queuing area) và được lưu vào vùng đệm (buffer) nếu bậc của nó vẫn còn lớn hơn 1 sau khi đã qua xử lý ở vùng nhớ lưu trữ dữ liệu. Khi gói “sạch” mới nhận được có bậc là 1 hoặc sau khi đã qua xử lý ở bước trước đó bậc của gói giảm xuống bang | thì gói đó được lưu vào vùng nhớ lưu trữ dữ liệu (message queuing area) để rồi được xử lý với các gói có bậc lớn hon 1 đang lưu trong vùng buffer.
Khi một gói nào đó có bậc đ > 1 mà trong quá trình mã hóa có bao gồm gói M,, được XOR với gói đã giải mã hoàn toàn M bên phía bộ thu, thì bậc của gói dang được giải mã sẽ giảm di | và các chỉ số d; sẽ được điều chỉnh để phản ánh quá trình này. Khi tat cả n gói đã được chứa trong vùng message queuing area thì bộ thu sẽ phát tín hiệu cho bộ phát về việc thông điệp đã được giải mã thành công. Quá trình giải mã nay đảm bảo thành công bởi A @ A = 0, với bat kì chuỗi bit A. Như vậy sau đ — 1 lần xử lý cho một gói có bậc d thì ta có thé giải mã được gói đó theo công thức (M,, @ M,,@ --: D Miz) @® (Mi, @® Mi, OD Mi,_, O Mi, OD Mig) (1.6) Do M,,,, ® M;,, = 0, nên phương trình (1.6) cho phép giải mã được gói Mj, Khả năng giải mã thành công của mã LT phụ thuộc chủ yêu vào cơ chê sinh ra bậc d của một gói tiếp theo như thế nào.
Trong khi đó, việc ch n các gói thông tin tham gia vào HVTH: Đỗ Lê Nam Trang 14 C1. Tông quan về fountain codes GVHD: TS. Hồ Văn Khương việc tạo thành một gói mã hóa nào đó, đơn thuần chỉ là việc tạo ra một hàm ngẫu nhiên có phân bố đều (normally distribution) trong khoảng từ [1, n]. Các ham sinh bậc d trong mã hóa LT được g ila ham Soliton.
Trước khi đi vào chi tiết các tính toán của các hàm phân bồ bậc trong dùng trong mã hóa LT. Ta xét bài toán đơn giản như sau: giả sử chúng ta ném bóng vào K giỏ, trong đó K là một con số lớn chang han nhu 1000 hay 10000. [1 Tính xác suất dé một giỏ nào đó trong K giỏ không có quả bóng nào được ném vào khi ta đã ném bóng N Ian. 1 Tìm giá trị nhỏ nhất của N dé sau N lần ném bóng thì xác suất có ít nhất một qua bóng trong K giỏ là 1 — 5, với ổ là một con số nhỏ tùy ý.
Xác suất mà một giỏ nào đó trong K giỏ không nhận được bóng trong một lần ném la` (1 — =), 1 Nhu vay, ^ xác z suat k maSA một giỏ T2 nào VÀ đóz trong K giỏ - không A nhận ^ được bóng Z sau N lần ném được cho bởi công thức (1.7) (1-2) ~e# (1 Do đó, khi N = K, tức là số lần ném bóng bằng với số giỏ chứa bóng thì xác suất mà một giỏ nào đó trong K giỏ này không có bóng nào là e1. Tổng quát với N lần ném, kỳ v ng của số giỏ không có quả bóng nào được bởi công thức (1.8) Như vậy, giả sử ký hiệu ổ là con số cho trong công thức (1.8) thì giá trị N nhỏ nhất thỏa mãn xác suất 1 — 6, tat cả các giỏ đều có một quả bóng cho trong công thức (1.9) HVTH: Đỗ Lê Nam Trang 15 C1. Tông quan về fountain codes GVHD: TS. Hồ Văn Khương Vậy để cho việc giải mã thành công điều kiện cần là số lượng gói phát phải thỏa mãn bất phương trình (1.
Van dé đặt ra ở đây là việc thiết kế hàm phân bố như thé nao dé thỏa mãn bất phương trình (1. Hai hàm phân bố bậc được giới thiệu trong [3], nhằm phục vụ cho giải thuật Belief Propagation. Trong đó tại mỗi bước lặp, đòi hỏi ít nhất phải có một gói thu chỉ liên quan đến 1 gói phát, nói cách khác gói thu này băng một gói phát nào đó. Giải thuật sẽ dừng khi không có gói thu nào có bậc 1 hoặc tất cả các ký hiệu phát đã được giải mã hoàn toàn.
Hàm phân bố bậc Ideal Soliton Hàm phân bố bậc (Ideal Soliton Distribution) được giới thiệu trong [3]. Trong tình huống lý tưởng, ta mong muốn trong mỗi lần xử lý thì luôn có một gói thu có bậc 1. Sau khi gói này được xử lý với các gói khác thì bậc trung bình của toàn bộ các gói thu được giảm di 1 và lại làm xuất hiện một gói khác có bậc là 1 dé giải thuật giải mã có thé tiếp tục cho đến khi các gói được giải mã hoàn toàn. Đề thực hiện được điều này, hàm phân bố bậc có hàm phân phối được trình bày trong phương trình (1.K d(d — 1) Trong đó, xác suất để 1 gói phát bằng gói thu là = , rất nhỏ khi K rất lớn, thực tế K được ch n sẽ rất lớn, 1000, 10.
Ngoài ra, đ chính là số gói phát liên kết với gói thu trong 1 lần tạo gói phát bat kì. Bậc kì v ng của hàm phân bố này cho bởi (1.11) K K » d(d—-1) ề =) Zud-1 tw Ink ” (1.11) | d=2 d=2 Ham phan bố bậc Ideal Soliton Distribution mặc dù đơn giản nhưng trong thực tế lại gặp phải nhiêu van đê, chăng han có thê trong một lân lặp nào đó của quá trình giải ma, HVTH: Đỗ Lê Nam Trang 16 C1. Tông quan về fountain codes GVHD: TS. Hồ Văn Khương không có bat kì một gói thu nào có bậc là 1 hoặc có một vài gói phát không có liên kết nào với các gói thu.