Mã hóa kiểm tra chẵn lẻ mật độ thấp

Chia sẻ: Vu Son | Ngày: | Loại File: DOCX | Số trang:13

Thêm vào BST

Báo xấu

61
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm kiếm thông tin là một chủ đề chính đối với thư viện số. Người sử dụng tìm kiếm tài liệu trong các cơ sở dữ liệu (CSDL) của thư viện số dùng bất kỳ thuật ngữ xuất hiện ở bản ghi và không cần thiết am hiểu về cấu trúc bản ghi hoặc các quy tắc tạo lập bản ghi. Gần đây, các nghiên cứu về thư viện số tập trung vào tìm kiếm thông tin được phân tán trên nhiều máy tính qua mạng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mã hóa kiểm tra chẵn lẻ mật độ thấp

Chapter 5 Low Density Parity Check Codes (Mã hóa kiểm tra chẵn lẻ mật độ thấp) Mã hóa kiểm tra chẵn lẻ mật độ thấp (LDPC), đề xuất của Gallager trong 1962 [19],và sau đó được phát hiện bởi MacKay [18] và Neal xuất hiện như là một lớp học của mã có thể mang lại hiệu suất rất tốt trên kênh nhiễu trắng Gaussian (AWGN).Mã hóa LDPC có thể đạt được giới hạn chỉ tiêu lỗi gần Shannon với giải mã thực tế phức tạp trên một kênh AWGN, mã turbo tốt hơn với cùng một kích thước khối và tỷ lệ mã. 5.1 Giới thiệu Mã hóa LDPC là những ví dụ đặc biệt của mã khối tuyến tính. Cấu trúc của một mã khối tuyến tính được mô tả bởi ma trận G hoặc ma trận kiểm tra chẵn lẻ H. Khả năng sửa lỗi kí tự trong một từ mã được xác định bởi khoảng cách tối thiểu dmin. Dmin được định nghĩa là khối lượng ít nhất của các hàng trong ma trận G hoặc nó có thể được định nghĩa là số lượng ít nhất các cột trong H có tổng tới 0. Từ mã của một mã kiểm tra chẵn lẻ được hình thành bằng cách kết hợp một khối các chữ số thông tin nhị phân với một khối các chữ số kiểm tra. Những chữ số kiểm tra này được biểu diễn dưới dạng ma trận được gọi là ma trận kiểm tra chẵn lẻ. Ma trận này đại diện cho một tập hợp các phương trình tuyến tính đồng nhất, và thiết lập các từ mã là bộ các giải pháp của các phương trình Trong ma trận này bốn chữ số đầu tiên là chữ số thông tin và ba chữ số cuối cùng là chữ số kiểm tra. Phương trình kiểm tra chẵn lẻ cho ma trận này có thể được đưa ra như: x5= X1 © x2 © x3 (5.1) x6= X1 © x2 © x4 (5.2) x7= X1 © x3 © x4 (5.3) Những ma trận kiểm tra chẵn lẻ không phải là rất đơn giản để giải mã khi thông tin bên trong là lớn, do đó một kỹ thuật mã hóa khác được đưa ra bởi Gallager được biết đến như là mã hóa LDPC. Mã hóa LDPC là mã xác định bởi một ma trận i.e, nó chứa chủ yếu là 0’s và chỉ có một số nhỏ của 1’s. Mã hóa LDPC có thể được chia thành hai loại • Mã hóa LDPC có quy tắc: Số lượng của 1 mỗi hàng và cột là hằng số. • Mã háo LDPC bất quy tắc: Số lượng của 1 mỗi hàng và cột không cố định. Những mã bất quy tắc cho hiệu suất tốt hơn so với Mã có quy tắc. Giả sử kiểm tra tính chẵn lẻ mật độ thấp ma trận H có N cột và M hàng. Tỷ lệ mã được cho bởi R= 1(M / N), đồ thị hai phía tương ứng bao gồm N bit node, các node kiểm tra M và một số lượng nhất định của các cạnh. Mỗi bit node, được gọi là "left node", đại diện cho một bit của từ mã. Mỗi nút kiểm tra, được gọi là một "right node" đại diện cho kiểm tra chẵn lẻ của mã. Một cạnh tồn tại giữa một bit node và một node kiểm tra khi và chỉ khi có
một 1 trong mục tương ứng trong ma trận kiểm tra chẵn lẻ. Mã hóa LDPC có quy tắc là những ma trận mà tất cả các node cùng loại có cùng một mức độ, nếu mức độ của một node là số cạnh cho một node lân cận. Mã A(n, j, k) mật độ thấp là một mã của chiều dài khối n với số j của 1’s trong mỗi cột của ma trận và số k của 1’s trong mỗi hang của ma trận. Ma trận kiểm tra chẵn lẻ của mã hóa LDPC có quy tắc (3, 4) được hiển thị dưới đây. Hình 5,1 cho thấy đồ thị hai phía liên quan của nó. Hình 5.1 đồ thị đại diện của một mà LDPC có quy tắc (3,6) chiều dài 12. Các left node đại diện cho các variable node trong khi các right node đại diện cho kiểm tra các nút. [20] Các phương trình đại diện bởi những ma trận luôn luôn có thể được giải quyết để cung cấp cho các số kiểm tra là tổng hợp rõ ràng của các số thông tin. Phân tích một mã mật độ thấp chiều dài khối lớn là rất khó khăn vì số lượng bao la của codewords tham gia. Nó là đơn giản để phân tích một quần thể toàn bộ từ mã như vậy bởi vì số liệu thống kê của một quần thể cho phép một mức trung bình trên số lượng mà không phải là dễ xử lý trong mã riêng biệt.Từ các hành vi quần thể ta có thể lập
báo cáo thống kê về các thuộc tính của mã riêng biệt. Cho phân tích một ma trận này được chia thành submatrices j, mỗi submatric có chứa duy nhất 1 trong mỗi cột. 5.2 Mã LDPC trong MIMO Trong các hệ thống MIMO, chuyển tiếp mã hóa sửa lỗi là điều cần thiết cho kết nối chất lượng cao. Các thuật toán VBLAST được sử dụng trong hệ thống MIMO cho phép xử lý tuyến tính thông tin. Các vấn đề gặp phải với một lớp thuật toán là sự hiện diện của lỗi truyền và lớp được phát hiện đầu tiên, mà thường có singnaltonoise ratio (SNR) do mất tín hiệu điện nulling tuyến tính, có nhiều khả năng được giải mã không chính xác. Tối ưu hóa sóng vô tuyến là một giải pháp được thảo luận trong chương trước. Để nâng cao hơn nữa độ tin cậy của liên kết và chống lỗi liên ký tự là vấn đề Forward thực hiện được chương trình sửa lỗi LDPC. Các thủ tục mã hóa cơ bản dữ liệu truyền với một số bit bảo vệ giúp nhận biết xem có lỗi xảy ra trong quá trình truyền. Mã hóa LDPC là rất hiệu quả (đối với mã hóa và giải mã phức tạp) . Sử dụng mã hóa LDPC giúp thực hiện tốt tiềm năng của hệ thống MIMO một cách hiệu quả. 5. 3 mã hóa Mã LDPC là mã tuyến tính. Do đó,nó có thể được thể hiện như không gian của một ma trận chẵn lẻ kiểm tra , ví dụ, là một từ mã khi và chỉ khi H xT= 0T (5.4) Sửa đổi "mật độ thấp" áp dụng cho ma trận nên đơn giản. Ví dụ,nếu có kích thước [(n / 2) x n], trong đó n là chẵn, sau đó nó có thể được yêu cầu cho H có 3 cột và 6 hàng. Chúng ta tham khảo các mã liên kết như là một mã LDPC có quy tắc. Sự đơn giản của H cho phép hiệu quả (tối ưu) giải mã, trong khi tính ngẫu nhiênvđảm bảo (theo nghĩa xác suất) một mã tốt .[20]
Hình 5.2 (a) Một ma trận kiểm trachẵn lẻ tương đương trong hình tam giác thấp hơn. (b)ma trận kiểm tra chắn lẻ tính gần đúng hình tam giác thấp hơn 5.3.1 Mã hóa hiệu quả dựa trên khoảng tam giác thấp hơn Hiệu quả của các bộ mã hóa phát sinh từ các ma trận kiểm tra chẵn lẻ H và thuật toán có thể được áp dụng cho bất kỳ (đơn giản)H. Các hàng của H là độc lập tuyến tính. Chúng ta xem xét một ma trận kiểm tra chẵn lẻ H m x n trên môt lĩnh vực Galva F (GF (2)). Mã liên quan bao gồm các thiết lập của ntuples x hơn F như H xT= 0T (4.5) Đối với các mã để đạt được công suất kênh, và có thời gian xử lý tuyến tính chúng ta đưa ra ma trận kiểm tra chẵn lẻ được đưa ra trong hình tam giác thấp hơn bằng cách sử dụng thuật toán Greedy.Điều này có thể được thực hiện đơn giản với hoán vị hàng và cột. Chúng ta sử dụng thuật toán Greedy A ,đưa ma trận bắt đầu một hình tam giác thấp hơn.
Hình 4.3 Sơ đồ Đại diện của thuật toán Greedy Cốt lõi của thuật toán là bước đường chéo mở rộng. Thuật toán Greedy A bắt đầu với ma trận (1r)l x l; A như hình 4.4 (a). Trong bước khởi tạo, dự kiến phần nhỏ (1 – α) của tất cả các cột được phân loại như được biết đến và phần còn lại được phân loại là xóa. Lần đầu tiên các thuật toán thực hiện một bước này (1 – α )l cột được biết đến được sắp xếp lại để hình thành các cột đầu của ma trận A hiển thị như trong hình 4.4 (b). Giả sử rằng các ma trận còn lại có hàng bậc một, cột kết nối với các hàng bằngmột được xác định trong bước thứ hai. Hãy để các cột này là c1..... ck và cho r1 .... rk có bậc một hàng như vậy mà ci được kết nối với ri. Trong lần thứ hai áp dụng bước một các cột mới này được biết đến và hàng liên quan của nó được sắp xếp dọc theo một đường chéo như trong Hình 4.4 (c). Hơn nữa, trong mỗi lần lặp bổ sung này đường chéo được mở rộng hơn nữa. Nếu thủ tục này không chỉ dừng lại trước sau đó các đường chéo kết quả đã dự kiến chiều dài αl và, do đó, khoảng cách hàng đã dự kiến có kích cỡ (1rα)l và khoảng cách cột kích thước (1 α)l như thể hiện trong hình. 4.4 (d) Hình 5.4. (A) cho ma trận A. (b) Sau khi ứng dụng đầu tiên của bước một, (1 α)l cột được biết đếnđược sắp xếp lại để tạo thành đầu tiên (1 α)l cột của ma trận A. (c) Sau khi ứng dụng thứ hai của bước một, k mới được biết đến cột và các hàng liên quan của họ được sắp xếp lại để tạo thành một đường chéo của chiều dài k. (D) Nếu thủ tục khôngchấm dứt sớm sau đó đường chéo được mở rộng để cóchiều dài αl và, do đó, khoảng cách hàng là bằng (1r α)l và khoảng cách cột bằng (1 α)l. [20]
Nếu, mặt khác, thủ tục chấm dứt trước khi tất cả các cột kết thúc sau đó chúng tôinhận được một tam giác gần đúng bằng cách sắp xếp lại các cột còn lại bên trái.Giả sử rằng các phần còn lại của cột bằng εl sau đó dự kiến kết quảkhoảng cách hàng bằng (1 r α+ε)l và kết quả khoảng cách cột dự kiến sẽ là bằng (1 α +ε)l. Sau khi sử dụng thuật toán greedy và đưa ma trận được đưa ra trong tam giác dưới hình thức, bắt đầu mã hóa.Ma trận kiểm tra chẵn lẻ là H = Trong đó A là (mg) x (nm), B (mg) xg, T là (mg) x (mg), C là gx (nm), D được gxg, và cuối cùng E là gx (mg). Tất cả những ma trận thưa thớt và T là tam giác thấp hơn với những đường dọc theo đường chéo. Nhân ma trận này từ cánh trái (5.7) Tiếp theo ma trận thu được (5.8) X = (s, p1, p2) Nơi s biểu thị phần hệ thống, p1 và p2 kết hợp biểu thị phần chẵn lẻ, p1 có chiều dài g, và p2 có chiều dài (mg). Việc xác định phương trình H xT= 0T chia tách thành hai phương trình, cụ thể là Như AsT + Bp1T + Tp2T = 0 (5.9) (ET1A+C)sT + (ET1A+D)p1T = 0 (5.10) Xác định Ф=(ET1A+D) và giả định cho thời điểm này Ф là nonsingular. Sau đó,từ (5.10) p1T= Ф1[(ET1A + C) sT] (5.11) Sau đó xác định AsT và Bp1T và thêm chúng tới nhân kết quả T1 p2T= T1[AsT+ Bp1T] (5.12) Bước tiền xử lý và thực tế mã hóa
BẢNG II Tóm tắt của thủ tục Encoding đề xuất. Nó đòi hỏi hai bước: Một tiền xử lý Bước Và Bước mã hóa thực tế 5.4 Giải mã: Các thuật toán giải mã được sử dụng cho mã hóa LDPC được gọi là thuật toán qua tin nhắn, và các thuật toán được lặp đi lặp lại. Lý do cho tên của chúng ở mỗi vòng của các thuật toán truyền thông được truyền từ nút truyền thông để kiểm tra các nút, và kiểm tra các nút trở lại các nút truyền thông. Các thong điệp từ các nút truyền thông để kiểm tra các nút được tính dựa trên giá trị quan sát của nút truyền thông và một số các thông điệp truyền từ các nút lân cận để kiểm tra nut tryền thông. Một khía cạnh quan trọng mà thông điệp được gửi đến một nút tryền thông v để kiểm tra node c không phải đưa vào tài khoản truyền thông được gửi ở vòng trước từ c đến v. Điều này cũng đúng đối với thông điệp truyền từ các nút kiểm tra đến các nút truyền thông . Một lớp quan trọng của thuật toán qua truyền thông là thuật toán truyền sự tin cậy. Thuật toán này có mặt trong nghiên cứu của Gallager [19], Các thong điệp thông qua cùng các cạnh trong thuật toán này là xác suất, hay độ tin cậy. Chính xác hơn, các thông điệp qua từ một node thong điệp v để kiểm tra nút c là xác suất mà v có một giá trị nhất định của nút truyền thông, và tất cả các giá trị truyền
đạt v trong vòng trước từ kiểm tra sự cố các nút v khác hơn c. Mặt khác, các thông điệp truyền từ c đến v là xác suất mà v có một giá trị nhất định cho tất cả cácthông điệp truyền cho c trong trước vòng từ các nút thông báo khác hơn v[21]. Đối với một biến ngẫu nhiên nhị phân x để L (x) = Pr [x = 0] / Pr [x = 1] là khả năng của x. Cho một biến y ngẫu nhiên, khả năng điều kiện của x ký hiệu L (x| y) được định nghĩa là Pr [x = 0| y] / Pr [x = 1| y] Tương tự như vậy khả năng đăng nhập của x là ln L(x) và có điều kiện khả năng của x cho y là lnL (x| y). Nếu x là biến ngẫu nhiên có xác suất ngang nhau, sau đó L (x| y) = L (y| x) với quy tắc Bayes. Vì vậy nếu y1 ......... yd là ngẫu nhiên độc lập biến, sau đó chúng ta có lnL(x |y1…………….yd)= (5.13) Bây giờ giả sử rằng x1....... xi là biến nhị phân ngẫu nhiên và y1...... yi là các biến ngẫu nhiên. Ngoài ra ký hiệu F bởi ©. Sau đó tính toán ln L(x1©...© x`| y1; :::; Yl). Nếu p= 2 Pr [x1= 0| y1] 1và q = 2Pr [x2= 0| y2] 1,sau đó 2Pr [x1 ©x2= 0| y1; Y2] 1 = pq.Do đó, 2PR [x1 ©...©x` = 0| y1...... y`] 1 = khi Pr [xi= 0| yi] = L (xi|yi) = (1 + L(xi ‫׀‬yi)), chúng ta có 2Pr[xi= 0‫׀‬yi] 1 = (L 1)=(L + 1) = tanh(l /2), tại L = L(xi‫׀‬yi) và l = lnL. Vì vậy, chúng ta có được Tại li = lnL (xi j yi). Các thuật toán truyền độ tin cậy cho Mã LDPC có thể được bắt nguồn từ hai quan sát. Trong vòng 0, các nút kiểm tra gửi cùng tất cả các đilogkhả năng xảy ra điều kiện trên giá trị quan sát của họ. Ví dụ, nếu các kênh được sử dụng là BSC với xác suất lỗi p, sau đó các tin nhắn đầu tiên được gửi đến tất cả các nút kiểm tra tiếp giáp với một nút thông điệp là ln (1 p) ln p nếu giá trị của nút là số không, và đó là không đúng của giá trị này nếu giá trị của nút là một. Trong tất cả các vòng tiếp theo của các thuật toán một nút kiểm tra c gửi đến một nút tin nhắn liền kề thông qua khả năng theo đến (5.14). Một thông báo nút v gửi đến nút kiểm tra c của nó, điều kiện loglikelihood trên giá trị quan sát của nó và trên đến đăng nhập khả năng xảy ra từ các nút kiểm tra liền kề khác hơn c sử dụng các mối quan hệ (513). Cho m(l)vc là thông điệp thông qua tin nhắn từ nút v để kiểm tra nút c tại vòng thứ lth của thuật toán. Tương tự như vậy, xác định m(l)cv. Tại vòng 0, m(0)vc là khả năng đăng nhập node v tin nhắn có điều kiện về giá trị quan sát của mình, đó là độc lập của c. Chúng tôi biểu thị giá trị này bởi. Sau đó các phương trình cập nhật có thể được mô tả như
trong đó Cv là tập hợp của các nút kiểm tra sự cố để nhắn nút v, và Vc là tập hợp các nút tin nhắn, sự cố để kiểm tra nút c.Việc tính tại các nút kiểm tra có thể được đơn giản hóa hơn nữa bằng cách thực hiệnchúng trong t ông đăng nhập miền. Vì giá trị của tanh (x) có thể bác bỏ, nó là cần thiết để tiếp tục theo dõi các dấu hiệu của nó một cách riêng biệt. Hãy γ là một bản đồ từ các số thực [∞,∞] Để F x [0,∞] được xác định bởi γ(x): = (sgn (x), tanh ( | x| / 2)) (set sgn (x) = 1 nếu x≥1 và sgn (x) = 0 khác.) Rõ ràng là γ ánh xạ, do đó, có tồn tại một chức năng nghịch đảo γ-1.Hơn nữa,γ(xy) =γ(x) +γ(y), trong đó addition là thành phần chính xác trong F và trong [0,∞]. Sau đó, nó là rất dễ dàng để cho thấy rằng(4) tương đương với truyền tin tưởng có thể được thực hiện cho một số lượng tối đa vòng. 5.5 Tỷ lệ LDPC liên tục và biến LDPC: Tỷ lệ mã hoặc tỷ lệ thông tin của một mã sửa lỗi chuyển tiếp (FEC), giống như mã khối tuyến tính, trạng thái của tổng lượng thông tin đó là hữu ích (không dự phòng). Nếu mã tỷ lệ là k / n, cho mỗi k bit thông tin hữu ích, các coder tạo ra n bit dữ liệu chung,trong đó nk là thừa. Nếu R là net bitrate(bitrate hữu ích), gross bitrate ( bitrate raw) là R * n / k. Hằng số tỷ lệ của mã này có nghĩa là tất cả các bộ mã hóa LDPC trong mảng Laser máy phát có một tỷ lệ tương tự của việc gửi dữ liệu. Tỷ lệ mã biến thiên là một trong những tỷ lệ mà tại đó thông tin được gửi tiếp tục thay đổi hình thức một mảng Laser máy phát khác. Để thiết kế tỷ lệ mã biến thiên Puncturing [22] có thể được sử dụng. Các mã bị đánh thủng bằng cách xóa một của những ký tự chẵn lẻ. Một mã (n, k) sẽ trở thành một mã (n1, k). Trong đoạn code tỷ lệ cố định được thiết kế tỷ lệ mã là R = 1/2, thủng 1 bit ra của 18 thay đổi tỷ lệ mã R = 2/3.[22]
5.5.1 Thiết kế của LDPC tỷ lệ khác: Để d là yếu tố thiết kế và W e chiều dài của phần chẵn lẻ của từ mã. [23] Đối với bất kỳ 0
Fig5.6 So sánh BLER và SNR đường cong cho VBLAST uncoded và tốc độ liên tụcLDPC mã hóaVBLAST Và hình 4.6 cho thấy hiệu suất của thuật toán phát hiện VBLAST cải thiện khi mã hóa LDPC được sử dụng. Cho BLER của 1011 có một được mã hóa của 2dB được thực hiện,do đó cải thiện độ tin cậy của thông tin liên lạc, nâng cao sức mạnh hiệu quả của hệ thống cho điều kiện sóng mạnh. Tỷ lệ LDPC được sử dụng là ½. 5.6.1 Simulation Kết quả cho tỷ lệ không đổi LDPC Biểu đồ mô phỏng dưới đây cho thấy việc so sánh các VBLAST không mã hóa với VBLAST để Tối ưu hóa và tỷ lệ không đổi LDPC, với R = ½ Fig5.7 So sánh BLER và SNR đường cong cho VBLAST uncoded, LDPC tốc độ không đổi mãVBLAST và VBLAST uncoded sử dụng Tối ưu hóa đơn đặt hàng Hình 4.7, cho thấy LDPC mã hóa VBLAST cho sự cải thiện của 1dB so với tối ưu hóa để sắp xếp VBLAST QR cho BLERf 1011. Cả hai Mã hóa và trật tự phân loại được sử dụng để chống lại truyền lỗi trong thuật toán VBLAST 5.6.2 Mô phỏng kết quả cho LDPC tốc độ không đổi và tỷ lệ biến LDPC Các LDPC tốc độ không đổi có tỷ lệ ½, mà là tỷ lệ lãi suất thay đổi tiếp tục thay đổi bằng cách sử dụng mã hóa tương tự. Hiệu suất BLER của cả hai được thể hiện trong hình bên dưới,
Fig5.8 So sánh BLER và SNR đường cong cho VBLAST uncoded, LDPC tỷ lệ liên tục mã hóaVBLAST và tỷ lệ biến LDP C mã VBLAST. Trong sung 4,8, có thể thấy rằng mã hóa của 3 dB đạt được so với Uncoded thuật toán VBLAST, và cải thiện 1 dB so với tỷ lệ không đổi Mã LDPC được đạt được bằng cách sử dụng mã LDPC tỷ lệ biến cho BLER của 1011 5.6.3 Mô phỏng kết quả cho LDPC tốc độ không đổi và biến tỷ lệ LDPC mạnh sự hỗn loạn và bất ổn yếu.
Hình 5.9 So sánh các BLER và SNR đường cong, tỷ lệ không đổi LDPC VBLAST mã hóa và biến tỷ lệ LDPC VBLAST mã hóa, cho yếu bất ổn và điều kiện xáo trộn mạnh mẽ Hình 5.9 cho thấy trong điều kiện sóng yếu, mã hóa được cung cấp bởi mã LDPC là tốt hơn nhiều so với các điều kiện sóng mạnh, tốc độ không đổi LDPC một BLER của 1011 tại SNR là 0,75 dB chỉ dưới điều kiện hỗn loạn yếu, mà là ở điều kiện sóng mạnh m SNR của 1,75 dB là cần thiết.