intTypePromotion=3

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

0
2
lượt xem
0
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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ó 
  2. 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 
  3. 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ó  singnal­to­noise 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] 
  4. Hình 5.2 (a) Một ma trận kiểm tra­chẵ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 n­tuples  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.
  5. 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  (1­r)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ằng­mộ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ỡ (1­r­α)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  (1­r ­α)l và khoảng cách cột bằng (1 ­α)l. [20]
  6. 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 (m­g). 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) (­ET­1A+C)sT + (­ET­1A+D)p1T = 0  (5.10) Xác định Ф=(­ET­1A+D)  và giả định cho thời điểm này Ф là nonsingular. Sau đó,từ  (5.10)  p1T= ­Ф­1[(­ET­1A + C) sT]  (5.11) Sau đó xác định AsT và Bp1T và thêm chúng tới nhân kết quả T­1  p2T= ­T­1[AsT+ Bp1T]  (5.12) Bước tiền xử lý và thực tế mã hóa  
  7. 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 
  8. đạ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 đilog­khả  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 log­likelihood 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ư
  9. 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 đó n­k 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ã (n­1, 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]
  10. 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 
  11. 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 10­11 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 10­11. 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,
  12. 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 10­11 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.
  13. 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 10­11 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.

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản