Nghiên cứu mã LDPC và mô phỏng đánh giá

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 (3.74 MB, 20 trang )

<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

Aw kw

MO DAU

Ly do chon dé tai:

Mã hóa kênh có vai trị quan trong trong việc truyền dẫn thơng tin số. Mục

<small>đích của mã hóa kênh là nhằm tăng khả năng tái tạo dữ liệu bị cản nhiễu ở phía đầuthu.</small>

<small>Ngày nay, các dịch vụ trên mạng viễn thông gia tăng không ngừng trong khi</small>

nguon tài nguyên của mạng viễn thông là hữu han.Vi vậy việc khai thác nguồn tai

nguyên của mạng viễn thông một cách hiệu quả là yêu cầu tiên quyết trong thiết kế

hệ thống truyền thơng số. Thơng tin đóng vai trị rất quan trọng trong đời sống hiện nay. Tuy nhiên mỗi sự thay đôi của đường truyền dẫn làm cho thông tin phát và bên thu có sự sai lệch. Sự sai lệch này làm thơng tin khơng cịn chính xác và nêu khơng có cách xử lý thì ta phải truyền lại thơng tin gây ra lãng phí thời gian và băng thông. Do vậy, việc sử dụng các loại mã kênh có thể giúp ta sửa sai và tránh được việc truyền lại thông tin. Việc nghiên cứu giải quyết những vấn đề liên quan đến mã hóa kênh không chỉ là đáp ứng yêu cầu thực tiễn cấp thiết trong việc tăng thơng lượng kênh truyền mà cịn có ý nghĩa khoa học khi đưa ra những cơng cụ mơ phỏng và tính tốn hiện đại vào lĩnh vực tạo ra bộ mã hóa kênh tối ưu.

Mã LDPC là một loại mã cho phép có tốc độ truyền tiệm cận tốt nhất, giới hạn tốc độ Shannon và có độ phức tạp tính tốn của bộ mã hóa và giải mã chấp

<small>nhận được với các cơng cụ tính tốn hiện nay cho những bộ mã có độ dài từ mã</small>

lớn.Hiện nay, mã LDPC đang được ứng dụng trong nhiều lĩnh vực truyền thông và

lưu trữ thông tin hiện đại. Vì vậy em chọn đề tài: “NGHIÊN CỨU MÃ LDPC VÀ MO PHONG ĐÁNH GIÁ”

<small>. Tông quan về van đê nghiên cứuMục đích nghiên cứu</small>

Đối tượng và phạm vi nghiên cứu

<small>Phương pháp nghiên cứu</small>

Bồ cục luận văn:

<small>Luận văn tập trung đên một sô nội dung cơ bản sau:</small>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

Chương 1: Tìm hiểu về mã hóa kênh truyền. Chương này đề cập một cách tong quá về mơ kinh mã hóa kênh truyền, về lý thuyết kênh truyền, tìm hiểu những

nguyên lý co bản nhất việc mã hóa kênh truyền.

Chương 2: Tìm hiểu tổng quan về LDPC. Chương này dé cập các khái niệm mã LDPC, cách biểu diễn mã LDPC, tính chất của mã LDPC, các phương pháp tạo

<small>mã và thuật toán giải mã LDPC... Từ những thuật tốn giải mã đưa ra những phân</small>

tích dé có thé thực hiện mơ phỏng đánh giá.

Chương 3: Mơ phỏng đánh giá các thuật toán giải mã LDPC để so sánh các

hiệu năng của chúng qua việc đánh giá khả năng chống nhiễu trên kênh nhị phân có

<small>nhiều.</small>

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

CHƯƠNG 1: TONG QUAN MÃ HOA TREN KENH TRUYEN

1.1 Hệ thống truyền tin

Sơ đồ khối chức năng của một hệ thống truyền tin tổng quát gồm có ba khâu chính: Nguồn tin, kênh tin, nhận tin (hình 1.1)

<small>Hình 1.1 : Sơ đồ khối chức năng hệ thống truyền tin</small>

Trong sơ đồ này:

Nguồn tin là tập hợp các tin mà hệ thống truyền tin dùng dé lập các bản tin

khác nhau dé truyền tin.

Kênh tin là nơi hình thành và truyền tín hiệu mang tin đồng thời ở đấy sinh

<small>ra các tạp nhiễu phá hủy thông tin.</small>

Thu tin là cơ cấu khôi phục thông tin ban dau từ tín hiệu lay ra ở đầu ra của

1.2 Mơ hình truyền kênh

Q trình mã hóa lấy từng khối k bít thơng tin và chun dãy duy nhất n bít

gọi là từ mã. Lượng thơng tin dư thừa trong q trình mã hóa số liệu được đo bằng

tỷ số n/k và k/n gọi là tốc độ mã. Quá trình truyền tin theo mơ hình 1.2

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

<small>Trong đó</small>

Nguồn tin: là nơi tạo ra tin 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.

<small>Mã hóa kênh: Bộ mã hóa kênh ghép thêm thơng tin dư thừa vào</small>

chuỗi dữ liệu đầu vào.

Kênh: Hàm xác suất truyền dẫn của kênh. Trong đó kênh truyền dẫn làkênh

<small>khơng nhớ.</small>

1.3 Kết luận chương

Chương 1 đề cập cách thức truyền tin trên kênh truyền, tổng qt mơ hình <small>mã hóa kênh truyền. Từ đó có thê hiểu được cách truyền tin trên kênh có nhiễu, làmtiên dé đi sâu vào việc nghiên cứu mã LDPC có thê đưa ra những đánh giá nhận xét</small>

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

CHUONG 2:TONG QUAN VE MÃ LDPC

2.1 Tổng quan về mã LDPC

Mã LDPC thuộc họ mã khối [1], quan hê giữa ma trận sinh G và ma trận

kiểm tra H được biểu diễn bằng phương trình sau:

HuxN-GNx& = ŨwxK (21)

Trong đó N là số bít mã, K là số bit thơng tin và M = (N - K) là số bít kiểm

<small>tra trong một từ mã.</small>

Ma trận kiêm tra của mã LDPC có thé được biểu diễn bang các thông số sau

<small>(N, w,,w„), trong đó N là độ dai của từ mã, w,, w„ là các hàm trọng Hamming</small>

trung bình của các cột và hàng tương ứng trong ma trận kiểm tra.

Nếu ma trận kiểm tra của mã LDPC có đầy đủ (khi các hàng của ma trận

<small>nàylà độc lập tuyên tính với nhau), tỉ lệ mã r được xác định như sau:</small>

H„ và phương trình kiểm tra từ mã hợp lệ phải dựa trên hai ma trận mới này.

<small>2.2 Phương pháp tạo mã LDPC</small>

<small>2.2.1 Phuong pháp Gallager</small>

<small>2.2.2 Phương pháp của Mackay — Neal</small>

<small>2.2.3 Phương pháp cua Eleftherious va Olcer</small>

2.3Biéu diễn mã LDPC:

2.3.1 Biểu diễn mã LDPC bằng ma trận kiểm tra chan lẻ

Mã kiểm tra chăn lẻ mật độ thấp (LDPC) là một mã khối tuyến tính khi đó ma trận kiểm tra chin lẻ H có mật độ số 1 là ít.

Ma trận kiểm tra chan lẻ (H) là một ma trận tuyến tính rời rạc:

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

- Có rất ít giá trị 1 tại mỗi hang và cột

<small>- Đảm bảo việc giải mã phức tạp khi mà độ dài mã tuyến tính tăng lên và</small> khoảng cách tối thiêu cũng tăng lên.

- Việc tìm ra ma trận kiểm tra rời rac cho một mã đang tồn tại rất khó

- Gọi ma trận kiểm tra chin lẻ có trọng sỐ hàng i là 1, còn trọng số cột thứ i là h;. Gọi chung v và h là hệ số phân bố của mã.

- W,là số bít 1 tại mỗi cột, Wy số bit 1 tại mỗi hàng.

2.3.2 Biểu diễn mã LDPC bằng đồ thi Tanner

Lúc đầu, mã LDPC được biéu diễn qua ma trận chăn lẻ H. Tuy nhiên, hiện

nay một trong những cách được coi là hiệu quả nhất để biểu diễn mã LDPC đó

<small>chính là thơng qua đồ thị Tanner. Đây là đơ thị 2 phía với hai loại của nút trong một</small>

đồ thi Tanner đó là nútthông tinva nút kiểm tra (chúng ta hay gọi là nút v và nút c). Đồ thị Tanner của một mã được xây dựng thông qua quy tắc: nút kiểm tra j kết nối

được với nút biến số ¡ khi h, trong H bang 1. Chu ky Tanner là một đường khép kin

liên kết từ nút bat kì đi một vịng rồi lai quay lại chính nó.

<small>check fo fi fr f3 fy</small>

2.4 Các tinh chat của mã LDPC

<small>Độ mạnh của mã chính là kha năng sửa lượng lỗi thơng tin lon. Nhung nó</small>

<small>cũng là thuật tốn giải mã dưới mức tơi ưu nhưng cũng có thê được gọi là giải mã</small>

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

tối ưu. Với mỗi một đoạn mã rất dài thì rất ít lượng bit 1 nó sẽ dễ dàng xây dựng được giả ngẫu nhiên một mã có khoảng cách tối thiểu thấp.

Điều quan trọng nhất là chọn được ma trận kiêm tra chan lẻ H phù hợp với

mật độ thấp dé giảm độ phức tap của việc giải mã. Mặt khác với một ma trận có mật độ thấp thì khả năng mở rộng của nó cũng dễ dàng.

Do tính chất phức tạp của mã LDPC, nếu chúng áp dụng cho những trường hợp khả năng mắc lỗi thấp rất lãng phí và khơng phù hợp.

Với mã dài thì một ma trận kiểm tra chan lẻ có cau trúc ngẫu nhiên sẽ tốt

hơn là ma trận có cấu trúc thơng thường. Cịn những mã có độ dài trung

bình và ngắn thì khơng có sự khác biệt nhiều giữa ma trận có quy tắc và bất quy tắc, và việc triển khai bằng phương pháp đồ thị hoặc phương pháp đại số thì ma trận có quy tắc sẽ đễ dàng hơn.

2.5.2 Mã hóa LDPC dùng ma trận kiểm tra chan lẻ H

<small>2.6 Các thuật tốn giải mã LDPC</small>

2.6.1 Thuật tốn trao đổi thơng tin trên kênh loại bo nhị phan a. Đặc điểm của thuật toán:

> Trên kênh truyền loại bỏ nhị phân (BEC) một bít được truyền đi, hoặc sẽ

nhận được chính xác hoặc sẽ bị xóa bỏ với xác suất là e. Nhiệm vụ của bộ giải mã là xác định những bít bị sai và sửa chúng cho đúng hồn tồn dé nhận được thơng tin cần thiết.

> Nếu tơn tại một phương trình kiểm tra chin lẻ mà các bít truyền di bi sai chỉ

một bít thì có thể sửa bằng thuật toán xác định chin lẻ. Theo đồ thị Tanner,

<small>thơng tin được đơn giản như sau: các bít thông tin M gửi thông tin đi dựa vàoma trận H, thông tin này được gọi là M,, đại diện cho bit nút thứ i khai báo</small>

giá trị cua bít là ‘1’, hoặc “0”. Nếu nó kí hiệu là ‘x’ tức là không xác định.

<small>Nếu một nút kiểm tra chỉ nhận một thơng tin là ‘x’, nó vẫn có thé tính được</small>

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

giá trị của bít khơng xác định này bằng cách chọn giá trị sao cho thỏa mãn tính chan lẻ. Mơ tả thuật tốn trao đôi thông tin qua kênh loại bỏ nhị phân:

<small>Su dụng kí hiệu B; dé đại diện cho tập hợp các bit trong phương trình kiểmtra chăn lẻ thứ j của mã.</small>

Algorithm 2 phía dưới phác họa giải mã trao đổi thông tin trong BEC. Dau vào là nhận giá tri từ ma trận y = [y....,yn| cai mà có thé là ‘1’, “0°, ‘x’ và dau ra là

<small>H1: if all messages into check j other than AJ; are known then</small>

<small>12: Kị; = Viren; agi Me mod 2)</small>

<small>19: for ? = Ì :mø da > Step 2: Bit messages i</small>

<small>20: if Ad; = ‘unknown’ then</small>

<small>21: if there exists aj € Ajs.t. Ej; z 'z` then</small>

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

<small>2.6.2 Thuật toán dao ngược bit(Algorithm Bit Flipping)</small>

a. Đặc điểm của thuật tốn đảo ngược bít

> Giải quyết về số nhị phân (khác biệt) của mỗi bit nhận được phát hiện và

truyền tới dé giải mã.

> Thông điệp được truyền đi dọc các cạnh của đồ thị Tanner và cũng dưới dạng

số nhị phân: một nút bit gửi một thông điệp nếu nó là 0 hoặc 1. Nếu đa số

<small>của thơng điệp nhận tại các nút bit là khác giá tri được nhận của nó thi sẽ</small>

thay đối ( đảo ngược) giá trị hiện tại. Tiến trình này được lặp lại trừ khi tất cả

phương trình kiểm tra chan lẻ là đúng hoặc trừ khi số lượng tối da của giải mã tăng lên đã được truyền và từ chối giải mã.

> Giải mã đảo ngược bit có thé ngay lập tức cham dứt khi giá trị từ mã được tìm thấy bởi việc kiểm tra nếu tat cả phương trình kiểm tra chan lẻ đã thỏa

> Thuật tốn đảo ngược bít dựa trên từ mã có liên quan đến một số lượng lớn

các bít kiểm tra và sửa sai chính nó. Ma trận H có mật độ thấp giúp cho việc dan trải các bít kiểm tra bởi vậy mà mỗi phương trình kiểm tra chan lẻ khơng

<small>thê có việc trùng các từ mã.</small>

<small>b. Mơ tả thuật tốn đảo ngược bít</small>

Thuật toán đảo ngược bit là cơ sở quan trọng răng một từ bit từ mã phần lớn liên quan đến của phương trình kiểm tra khơng hợp cách giống chính bản thân nó cũng khơng đúng. Tính rời rạc của H giúp mở rộng các bit vào việc kiểm tra có thể phương trình kiểm tra chan lẻ khơng giống việc bao gồm tập hợp các bit từ mã giống nhau.

Algorithm 3 phía dưới là thuật tốn giải mã đảo ngược bit. Đầu vào vecto

nhận y = [yụ,...,yn| với các bít ‘0’, ‘1’ có bít đã bị dao ngược và đầu ra là M =

[My,....M,] với bít “0°, ‘1’ cần tim.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

<small>15: fori =1:ndo > Step 2: Bit messages</small>

<small>16: if the messages Fj ; disagree with y; then</small>

<small>21: for j =1:mdo & Test: are the parity-check</small>

<small>22: L,= Lien, (My mod 2) > equations satisfied</small>

2.6.3 Thuật toán tong tích

a. Đặc điểm của thuật tốn

> Nó giống nhưthuật tốn đảo ngược bit, nhưng với thơng điệp đại diện cho mỗi quyết đinh (kiểm tra đáp ứng hoặc giá tri bit bằng 1) bang giá trị xác suất.

> Giá trị xác suất bit đầu vào được gọi là xác suất đầu tiên cho bit được nhận

bởi vì chúng được biết trong chuyền tiếp đầu tiên trước khi chạy giải mã

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

LDPC. Xác suất bit được trả về bởi giải mã được gọi là xác suất hậu

b. Thuật tốn tổng tích

Mục tiêu của thuật tốn giải mã tong tích là tinh giá trị tối đa của xác suất

<small>hậu nghiệm (maximuma posteriori probability) MAP cho mỗi bit từ mã, P; = Pƒc; =</small>

Trong giải mã tổng tích ngồi vấn đề thông điệp từ nút kiểm tra j đến nút bit i, Ej là LLR (tỉ lệ logarit hợp lệ) của xác suất đó là bit thứ ¡ dẫn tới thỏa mãn ma

Thuật tốn tổng tích được diễn ra trong Algorithm 4 phía dưới. Với dau vào

<small>là tỉ lệ logarit hợp lệ cho trước xác suất thông điệp.</small>

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

2.6.4 Mức độ đánh giá hiệu năng chống nhiễu:

2.7 Mức độ danh gia hiệu nang chong nhiéu trong BEC

“ Mã theo quy tắc:

Cùng tới T (w„, w„), xem xét tất cả các đồ thị Tanner của LDPC theo quy tắc với nút bit của mức độ w„ và nút kiểm tra của mức độ w,. Chúng ta muốn biết, giải mã trao đôi thông tin sẽ thực hiện như thế nào trong kênh loại bỏ nhị phân.

Từ việc giải mã trao đồi thông điệp trong BEC, thông điệp giữ một trong hai giá trị hiện tại của bit đó là 0 và 1 nếu được biết hoặc x nếu giá trị đó khơng được biết. Chúng ta định nghĩa q, là xác suất mà tại đó lặp | lần một việc kiểm tra đến bit thông điệp là x và q, là xác suất tại đó lặp ! lần một bit dé kiểm tra thông điệp là x.

Kiểm tra đến bit thông điệp trong một cạnh là x nếu một hoặc nhiều thông điệp đến trong cạnh khác (w„ — 1) trong nút kiểm tra là x. Dé tính xác suất q), một

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Ma trận kiểm tra chan lẻ khơng theo quy tắc có số hàng và cột với độ rộng khác nhau. Chúng ta định phần của độ rộng i của cột bởi 0; và định phần độ cao i

của hàng bởi r¡. Dé lay được mức độ đánh giá cho mã LDPC bat quy tắc một thay

thế đặc tính khác của mức độ thuộc tính, từ quan điểm của cạnh đồ thị Tanner được sử dụng. Dinh phần của cạnh mà kết nối đến mức độ i của nút bit được ký hiệu Â¡,

Ở đây A,la xác suất ở đó một cạnh được kết nối từ nút thông điệp i va p; là

xác suất mà ở đó cạnh được kết ni từ nút kiểm tra thứ i

Trước giải mã, giá tri của pp là xác suất của kênh bỏ một bit từ mã:

Po= & Đị= pọÄ(1—p(1—pị~¡)): (2.41)

2.7.2 Mức độ đánh giá hiệu năng chống nhiễu trong kênh có xác suất.

Cho một giải mã trao đơi thơng tin trong kênh nhớ ít chung, thơng điệp từ bit đến kiểm tra là log tỉ lệ khả nghịch (LLRs) của xác suất ở đó đưa bit 0 và 1. Như giá

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

trị LLR là liên tục, xác suất mà một thông điệp là rõ ràng giá tri LLR được mô ta bởi một mức độ xác suất chức nang (pdf)

Cho lai LLR của một giá tri x bat ki là

p(x = 1)j/`

Va L(x) sẽ dương nếu p(x = 0) > p(x = 1) va âm khi ngược lại. Do đó,

L(x) = log (

xác suất tương ứng bit từ mã là 1 là xác suất L(x) âm.

<small>Dé phân tích giá trị của pdfs này trong giải mã trao đôi thông điệp, chúng ta</small>

định nghĩa p(M,) là mức độ xác suất chức năng cho một thông điệp bit đến kiểm tra tại vòng lặp 1 và p(Ƒ,) là mức độ xác suất chức năng cho một thơng điệp kiểm tra đến bít tại vịng lặp 1 và p, là mức độ xác suất chức năng cho LLR của nhận tín

Từ khi thơng điệp đến độc lập, pdf (hàm phân phối xác suất) của giá trị bất kỳ được định dang từ phép cộng này có thé thu được bởi sử dụng xác suattrong pdfs tại thông điệp w„ — 1 từ nút kiểm tra và pdf của thông điệp đến từ kênh:

Pu = Pr pộ he

<small>Trung bình mức độ thuộc tinh khác, a(x):</small>

p(ŒM,) = pữ) ® > Aip(,)0~9 = p(r) ® A®(pŒ,),

Hoạt động cuối cùng có thể được đánh giá bằng việc sử dụng FFTs.

Chức năng của đánh giá tại mỗi nút kiểm tra là:

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

CHƯƠNG 3: MO PHONG ĐÁNH GIA VÀ SO SÁNH CÁC

THUẬT TOÁN GIẢI MÃ LDPC

Chương này dựa và một số thuật tốn cũng như cơng thức của từng thuật toán đã

tim được tại chương 2, tiến hành xây dựng chương trình mơ phỏng một số mã LDPC truyền trên kênh có nhiều AWGN, từ kết quả mơ phỏng này tiến hành đánh

giá so sánh hiệu năng chống nhiễu của chúng. 3.1 Mơ phỏng một số thuật tốn giải mã

3.1.1 Thuật tốn giải mã trao đổi thơng tin thơng qua kênh nhị phân xóa

Hình 3.1: Mơ phỏng hiệu năng của một mã LDPC (3,6) theo quy tắc với

xác suất đầu vào py tương ứng 0,42 và 0,45

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Kết quả mô phỏng cho thấy:

Với xác suất pạ ban đầu đủ lớn thì khi đó chất lượng thuật tốn giải mã trao đổi thơng tin qua kênh xóa càng bị suy giảm. Xác suất tỷ lệ thuận với số vịng lặp của thuật tốn tương ứng với từng giá trị đầu vào.Số vòng lặp càng lớn xác suất sẽ dan tới mức ôn dinh.Dé giảm thiêu độ phức tạp tính tốn, xác suất giải mã tương đối ơn địnhcần tạo ma trận kiểm tra chan lẻ với H có nhiều hàng tương ứng với số vòng lặp tương đối lớn. Với mã LDPC khơng theo quy tắc, thì xác suất ln ln

nhỏ hơn hoặc bằng 0.5, vịng lặp càng lớn, xác suất càng tiến sát tới giá trị có định

<small>0.5 nhanh hơn.</small>

</div>