MỤC LỤC
DANH MỤC HÌNH VẼ ........................................................................................... ii
THUẬT NGỮ VIẾT TẮT ....................................................................................... iv
MỞ ĐẦU .................................................................................................................. 1
CHƯƠNG 1: TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN SỐ .......................... 2
1.1. Hệ thống thông tin số ................................................................................ 2
1.2. Giới hạn Shannon về chất lượng ............................................................... 6
1.3. Kết luận chương ........................................................................................ 10
CHƯƠNG 2: MÃ LDPC ........................................................................................ 11
2.1. .........................................................................................................
Giới thiệu về bộ mã LDPC ................................................................................. 11
2.2. Mã hóa (encoding) .................................................................................... 13
2.3. Giải mã (decoding) ................................................................................... 14
2.3.1. Giải thuật giải mã truyền belief .......................................................... 15
2.3.2. ...................................................................................................
Giải thuật tổng tích SPA (Sum Product Algorithm) ....................................... 27
2.4. Kết luận chương ........................................................................................ 37
CHƯƠNG 3: MÔ PHỎNG MÃ LDPC ỨNG DỤNG TRONG HỆ THỐNG MIMO
................................................................................................................................ 38
3.1. Tổng quan hệ thống MIMO ...................................................................... 38
3.1.1. Sơ đồ khối tổng quát của thiết bị vô tuyến số ở hệ thống thông tin số. 38
3.1.2. Anten thông minh ............................................................................... 39
3.1.3. ................................................................................................... Hệ
thống đa anten ở đầu phát và đầu thu ............................................................. 40
3.1.4. Sự phân tập ......................................................................................... 48
3.1.5. Mã kênh trong hệ thống MIMO ......................................................... 52
3.2. Mô phỏng mã LDPC ứng dụng trong hệ thống MIMO ............................ 59
3.2.1. Sơ đồ khối hệ thống mô phỏng ........................................................... 59
3.2.2. Lưu đồ thuật toán cho quá trình mô phỏng ........................................ 60
3.2.3. Giao diện mô phỏng ........................................................................... 61
3.2.4. Một số kết quả mô phỏng ................................................................... 62

3.3. Kết luận chương ........................................................................................ 69

1


KẾT LUẬN ............................................................................................................ 70
TÀI LIỆU THAM KHẢO ...................................................................................... 71

2


DANH MỤC HÌNH VẼ
Hình 1.1. Các thành phần cơ bản của một hệ thống thông tin số ............................. 2
Hình 1.2. Sơ đồ kênh kết hợp ................................................................................... 4
Hình 1.3. Sơ đồ phân loại mã kênh .......................................................................... 5
Hình 1.4. Hiệu quả sử dụng phổ của các sơ đồ điều chế và mã hóa khác nhau
được tính toán cho trường hợp BER là 10 5 trên kênh AWGN .............................. 8
Hình 1.5. So sảnh các sơ đồ mã hóa LDPC, TCP, Reed - Solomon ........................ 9
Hình 2.1. Ma trận kiểm tra chẵn lẻ của mã LDPC đều (20, 3, 4) ........................... 11
Hình 2.2. Các trường họp trong đó một đường dẫn từ X sang Y bị chặn, cho
trước tập dấu hiệu E ................................................................................................ 17
Hình 2.3. Bốn kiểu suy diễn trong mạng belief ...................................................... 18
Hình 2.4. Đồ thị của một cây phức ......................................................................... 19
Hình 2.5. (a) Tính Pi(xị) và (b) Ằị(xi) .................................................................... 22
Hình 2.6. (a) Truyền thông báo từ dưới lên; (b) truyền thông báo từ trên xuống 24
Hình 2.7. Mạng belief của mã LDPC ..................................................................... 25
Hình 2.8. Đồ thị thừa số của tích cho ứong phương trình (2.19) ........................... 29
Hình 2.9. Đồ thị thừa số của mã khối tuyến tính cho bởi ma trận kiểm tra chẵn lẻ
của phương ừình (2.20) .......................................................................................... 29
Hình 2.10. Đồ thị thừa số của hiệp xác suất hậu nghiệm của mã khối tuyến tính có ma

trận kiểm tra chẵn lẻ của phương trình (2.20) ........................................................ 31
Hình 2.11. (a) Cây biểu diễn vế phải của phương trình (2.23). (b) Đồ thị thừa số
dưới dạng cây của phương trình (2.23) với x3 là gốc ............................................. 33
Hình 3.1. Sơ đồ khối tổng quát của thiết bị vô tuyến số ở hệ thống thông tin số. 38
Hình 3.2. Hệ thống anten MIMO 4 đầu thu phát.................................................... 40
Hình 3.3. Hệ thống truyền thông số với nhiều anten ở đầu phát và thu ................. 41
Hình 3.4. Chuyển đổi kênh truyền MIMO thành các kênh truyền song song ........ 46
Hình 3.5. Mô hình kênh truyền MIMO khi nT > nR ............................................... 46
Hình 3.6. Mô hình kênh truyền MIMO khi nT < nR ............................................... 47
Hình 3.7. Sự xen kênh ............................................................................................ 49
Hình 3.8. Sự phân tập của anten ............................................................................. 51
Hình 3.9. Ma trận mã STBC ................................................................................... 53
Hình 3.10. Sơ đồ mã lưới ....................................................................................... 57

11


Hình 3.11. Bộ mã lưới k = 1, K = 3 vàn = 2 ...........................................................58
Hình 3.12. Lưới mã và sơ đồ trạng thái với k = l , K = 3 v à n = 2 .......................58
Hình 3.13. Sơ đồ khối hệ thống mô phỏng .............................................................59
Hình 3.14. Lưu đồ thuật toán mô phỏng.................................................................60
Hình 3.15a. Giao diện mô phỏng............................................................................61
Hình 3.15b. Giao diện mô phỏng ...........................................................................61
Hình 3.16. BER của hệ thống Alamouti 2 anten phát 1 anten thu có sử dụng bộ
mã LDPC trong trường hợp sử dụng kiểu điều chế QPSK ....................................62
Hình 3.17. BER của hệ thống Alamouti 2 anten phát 2 anten thu có sử dụng bộ
mã LDPC trong trường hợp sử dụng kiểu điều chế QPSK ....................................62
Hình 3.18. BER của hệ thống Alamouti 2 anten phát 2 anten thu có sử dụng bộ
mã LDPC trong trường hợp sử dụng kiểu điều chế 8PSK .....................................63
Hình 3.19. BER của hệ thống Alamouti 2 anten phát 2 anten thu có sử dụng bộ

mã LDPC trong trường hợp sử dụng kiểu điều chế 16PSK ...................................63
Hình 3.20. BER của hệ thống Alamouti 2 anten phát 2 anten thu có sử dụng bộ
mã LDPC trong trường hợp sử dụng kiểu điều che 8QAM ...................................64
Hình 3.21. So sánh các kiểu điều chế M-PSK trong trường hợp 2 anten phát 2
anten thu .................................................................................................................64
Hình 3.22. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 8PSK.......................................................65
Hình 3.23. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 16PSK.....................................................66
Hình 3.24. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 8QAM.....................................................66
Hình 3.25. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 16QAM...................................................67
Hình 3.26. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 32QAM...................................................67
Hình 3.27. BER của hệ thống 4 anten phát 1 anten thu có sử dụng bộ mã LDPC
trong trường họp sử dụng kiểu điều chế 64QAM...................................................68
Hình 3.28. So sánh các kiểu điều chế M-QAM trong trường hợp 4 anten phát 1 anten
thu ........................................................................................................................... 68

iii


THUẬT NGỮ VIẾT TẮT
APP
ARQ

A Posteriori Probability
Automatic Repeat Request


Xác suât hậu nghiệm
Yêu cầu lặp lại tự động

AWGN Additive White Gaussian Noise

Nhiễu Gauss trắng cộng

BER

Bit Error Rate

Tỷ lệ lỗi bit

CSI

Channel State Information

Thông số trạng thái kênh truyền

ISI

Inter Symbol Interference

Nhiễu liên ký tự

GF

Galois Field

Trường Galois


LDPC

Low Density Parity Check Code

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

MIMO Multiple Input Multiple Output

Nhiều đầu vào nhiều đầu ra

MRC

Maximal Ratio Combining

Kết hợp tỷ số tối đa

PSK
QAM

Phase Shift Keying
Quadrature Amplitude Modulation

Khóa dịch pha
Điều chế biên độ vuông góc

QPSK

Quadrature Phase Shift Keying


Khóa dịch pha cầu phương

SNR

Singal to Noise Ratio

Tỷ số tín hiệu trên tạp âm

SPA

Sum Product Algorithm

Thuật toán tổng - tích

STBC

Space - Time Block Code

Mã khối không gian - thời gian

STTC
SVD

Space - Time Trellis Code
Singular Value Decomposition

Mã lưới không gian - thời gian
Phương pháp phân tích ma trận



MỞ ĐẦU
Thông tin đóng vai trò rất quan trọng trong đời sống hiện nay. Tuy nhiên môi
truờng truyền dẫn thay đổi làm cho thông tin bên 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 đó, việc sử dụng
các loại mã kênh truyền có thể giúp ta sửa sai và tránh được việc truyền lại thông tin.
Các loại mã hiện nay như mã tích chập, mã khối... đặc biệt là mã turbo đã cho thấy
khả năng vượt trội của mình so với các loại mã khác. Tuy nhiên, những nghiên cứu
gần đây về mã LDPC (Low Density Parity Check) đã cho thấy mã này còn tốt hơn
cả mã turbo. Khi Mackay chứng minh nó có khả năng tiệm cận tới hạn Shannon ngay
lập tức đã gây được sự chú ý tới các nhà khoa học.
Yì vậy em chọn đề tài: “Nghiên cứu và đánh giá phương pháp giải mã
LDPC”. Để cải thiện hơn nữa về hiệu suất sửa lỗi, giảm ảnh hưởng của nhiễu và
fading, nâng cao chất lượng tại đầu thu, dựa vào những kỹ thuật được ứng dụng rộng
rãi trong hệ thống thông tin ngày nay, đề xuất một mô hình truyền mới trong đó có
sự kết hợp của mã LDPC vào hệ thống MIMO. Nội dung đồ án gồm 3 chương:
Chương 1: Tổng quan về hệ thống thông tin số
Chương 2: Mã LDPC
Chương 3: Mô phỏng mã LDPC ứng dụng trong hệ thống MIMO.

CHƯƠNG 1
TÔNG QUAN VỀ HỆ THỐNG THÔNG TIN SỐ
1.1. Hệ thống thông tin số
Vào cuối thế kỷ 20 và đầu thế kỷ 21 đã ra đời nhiều loại hệ thống thông tin
số, chúng khác nhau về giải pháp xử lý tín hiệu số nhằm thực hiện việc truyền các
tín hiệu số một cách có hiệu quả về phương diện chiếm dụng băng tần cũng như công
suất tín hiệu. Một trong những giải pháp đó là dùng kỹ thuật mã hoá sửa lỗi (Error
Correction Code). Mục tiêu chính của bộ mã sửa lỗi trong hệ thống thông tin số là
làm cho độ tin cậy của truyền tin đạt cực đại trong phạm vi bị ràng buộc về độ rộng
băng tần, công suất tín hiệu và độ phức tạp của mạch điện trong hệ thống.

Để làm rõ vai trò của việc mã hoá sửa lỗi, ta đưa ra mô hình hệ thống thông

1


tin số tổng quát sau:

Hình 1.1. Các thành phần cơ bản của một hệ thống thông tin số
Trong đó, nguồn tin là nơi tạo ra các bản tin chứa đựng những thông tin cần
phát đi, các bản tin này có thể là các từ, các ký hiệu mã... Đầu ra của nguồn tin là
chuỗi các ký hiệu được biến đổi từ bảng chữ cái nào đó, thông thường là các ký hiệu
nhị phân.
Đầu ra của nguồn tin có nhiều thông tin dư nên bộ mã nguồn được thiết kế để
chuỗi đầu ra của nguồn tin trở thành chuỗi các chữ số nhị phân có độ dư thừa cực
tiểu. Nếu bộ mã nguồn tạo ra rb biưgiây thì rb được gọi là tốc độ dữ liệu.
Kênh truyền là nguyên nhân chủ yếu gây ra lỗi cho tín hiệu thu, nên bộ mã
kênh (giải mã kênh) thực hiện thêm vào các bit kiểm tra vào chuỗi thông tin nhằm
giảm tối thiểu các lỗi xuất hiện trên đường truyền. Bộ mã kênh ấn định bản tin k chữ
số đầu vào thành bản tin mới n chữ số đầu ra dài hơn gọi là từ mã. Một bộ kiểm soát
lỗi được gọi là tốt khi nó tạo ra các từ mã có khoảng cách sai khác nhau (khoảng cách
Hamming lớn). Mỗi bộ mã được mô tả bằng tỷ số R = k/n < 1 được gọi là tốc độ mã,
do đó tốc độ dữ liệu đầu ra bộ mã kênh là rc = rựR bit/giây. Như vậy, bộ mã kênh
làm giảm tốc độ truyền dữ liệu và làm tăng độ rộng băng tần trên kênh.
Đe tín hiệu đầu ra bộ mã kênh phù họp với kênh truyền, bộ điều chế thực hiện
sắp xếp các chuỗi số đầu ra bộ mã kênh thành chuỗi dạng sóng tưomg tự (các ký
hiệu) phù họp với đặc tính kênh truyền. Đe tăng tốc độ truyền, mỗi ký hiệu (symbol)
có thể mang nhiều bit thông tin như các hệ thống điều chế nhiều mức (QPSK, MPSK,
QAM, TCM...). Một bộ điều chế M mức thực hiện sắp xếp khối n chữ số nhị phân
đầu ra bộ mã kênh thành một trong M các dạng sóng có thể, trong đó M = 2“. Quá


2


trình điều chế có thể được thực hiện bằng cách biến đổi giá trị biên độ, pha hoặc tần
số của dạng sóng hình sin còn được gọi là tải tin. Chu kỳ dạng sóng đầu ra bộ điều
chế là T giây và rs = 1/T được gọi là tốc độ ký hiệu. Độ rộng băng tần tín hiệu cực
tiểu là rs Hz và được biểu diễn như sau:

Kênh là phương tiện được sử dụng để truyền tải tin. Ví dụ, kênh hữu tuyến
điện, kênh vô tuyến điện, kênh sợi quang... Hai ảnh hưởng quan trọng nhất của kênh
là tạp nhiễu và độ rộng băng tần. Ngoài ra, trong kênh thông tin di động còn bị hạn
chế bởi truyền lan đa đường, trong cáp sợi quang còn bị tán sắc tín hiệu...
Tuỳ theo yêu cầu đầu vào bộ giải mã kênh, bộ giải điều chế tạo ra chuỗi nhị
phân hay lượng tử. Bộ giải mã kênh thực hiện đánh giá bản tin thu được, với mục
tiêu làm giảm tối thiểu ảnh hưởng tạp nhiễu trên kênh, quá trình giải mã được dựa
trên nguyên tắc mã hoá và đặc tính của kênh. Sau đó, bộ giải mã nguồn biến đổi
chuỗi đầu vào thành chuỗi đầu ra và phân phối tới nơi nhận tin.
Nếu bộ giải điều chế làm việc với quyết định cứng thì đầu ra của nó là chuỗi
nhị phân và giải mã được gọi là giải mã quyết định cứng. Để đơn giản trong quá trình
nghiên cứu về mã kênh, ta có thể kết họp bộ điều chế, khối kênh và bộ giải điều chế
thành sơ đồ kênh kết hợp sau:
Tạp nhiễu

Hình 1.2. Sơ đồ kênh kết hợp
Từ sơ đồ kênh kết họp, nếu giá trị đầu ra kênh kết họp chỉ phụ thuộc vào giá
trị hiện hành đầu vào bộ giải mã mà không phụ thuộc vào một vài giá trị tín hiệu
trước đó thì ta gọi là kênh không nhớ. Nó được miêu tả bằng xác suất truyền P(i[j),
trong đó i là ký hiệu đầu vào nhị phân và j là ký hiệu đầu ra nhị phân. Mô hình kênh
đơn giản nhất là khi xác suất xuất hiện lỗi trong các ký hiệu nhị phân “0” và “1” là
như nhau và kênh là kênh không nhớ. Mô hình kênh loại này được biết đến như kênh


3


đối xứng nhị phân (BSC - Binary Symmetric Channel).
Với giải pháp quyết định cứng tại đầu ra bộ giải điều chế làm cho bộ giải mã
kênh ít cải thiện được tổn hao thông tin. Chỉ khi bộ giải điều chế thực hiện lượng tử
hoá tại đầu ra, với số mức lượng tử lớn hơn hai hoặc đưa ra các mẫu tín hiệu băng
gốc liên tục vào bộ giải mã kênh thì quá trình giải mã như vậy được gọi là giải mã
quyết định mềm và sẽ cải thiện được tổn hao thông tin.
Sơ đồ mã kênh thường được chia làm hai loại, đó là mã dạng sóng
(Waveform) và mã chuỗi có cấu trúc (Structured sequence).
Mã kênh
>f
Mã chuỗi có cấu trúc
-----

>f
Mã dạng sóng 1

Mã khối

—>

Mã đối cực

-->

Mã chập


—>

Mã trực giao

-->

Mã liên kết

-->

Mã lưới

>

—>
Hình 1.3. Sơ đồ phân loại mã kênh

Mã tín hiệu đa mức

Mã khối là bộ mã không nhớ (chuỗi bit được ở đầu ra của bộ mã chỉ phụ thuộc
vào bản tín đầu vào hiện hành mà không phụ thuộc một vài bản tin trước đó). Trái
ngược với mã khối là mã chập, đây là bộ mã có nhớ (chuỗi bit nhận được ở đầu ra
của bộ mã không chỉ phụ thuộc vào bản tin đầu vào hiện hành mà còn phụ thuộc vào
một vài bản tin trước đó). Mã liên kết là sự kết họp của hai bộ mã vòng trong và vòng
ngoài được phân biệt bởi bộ ghép xen (xáo trộn).
Năm 1967, Forney đưa ra sơ đồ mã hoá gồm mã vòng trong là mã chập và
mã vòng ngoài là mã khối Reed - Solomon. Sau đó, năm 1993 Berrou đưa ra bộ mã
Turbo có cấu trúc gồm hai bộ mã chập kết nối song song thông qua ghép xen và năm
1996 Benedetto đưa ra sơ đồ mã gồm hai mã chập liên kết nối tiếp. Các bộ mã này
đều sử dụng thuật toán giải mã lặp và có chất lượng tiến tới giới hạn Shannon. Giờ


4


đây, một hướng phát triển mới cho kỹ thuật mã hoá mới có tên gọi LDPC (Low
Density Parity Check Code) - mã kiểm tra chẵn lẻ mật độ thấp đang nổi lên và có
khả năng sẽ thay thế cho các bộ mã chập và mã liên kết. LDPC là một mã khối tuyến
tính không nhớ sẽ được tìm hiểu kỹ ở chương 2.
1.2. Giới hạn Shannon về chất lượng
Đối với một hệ thống thông tin số có tốc độ rb khi bị giới hạn về độ rộng
băng tần w thì được đánh giá qua hiệu quả sử dụng phổ và được ký hiệu là rị.
7 = ~~ (bit/giây/Hz)

w

(1.2)

Thay (1.1) vào (1.2) ta có:
I = rs^ (biƯgiây/Hz)

T

w

(1.3)

Khi độ rộng băng tần yêu cầu tối thiểu cho tín hiệu sau khi điều chế là rs Hz
thì hiệu quả sử dụng phổ đạt cực đại và được ký hiệu là rimax.
V^=nR


(1.4)

Để đạt được hiệu quả sử dụng công suất thì yêu cầu tỷ số Eb/N0 (Eb là năng
lượng trung bình thu được trên bit thông tin, No là mật độ phổ công suất tạp âm đơn
biên) phải đạt được xác suất lỗi bit theo lý thuyết và có quan hệ với tỷ số tín hiệu trên
tạp âm S/N nhu sau:
— = nR^
N Nữ

(1.5)

Như vậy, giới hạn ừên của tốc độ truyền dữ liệu trên kênh có liên quan tới tỷ
số tín hiệu trên tạp âm và độ rộng băng tàn hệ thống. Theo khái niệm về dung lượng
kênh, ký hiệu là c, được Shannon - Hartley đưa ra năm 1948, đó là tốc độ cực đại
mà thông tin có thể truyền qua trên kênh có tạp âm và được định nghĩa là lượng thông
tin tương hỗ cực đại trên tất cả các phân bố đầu vào kênh có thể xảy ra.

c = max/(X,7)

(1.6)

P(x)

Trong đó I(X,Y) là thông tin tương hỗ giữa X (đầu vào kênh) và Y (đầu ra
kênh) được định nghĩa cho kênh rời rạc là:
(1.7)

5



Trong đó: P(x) và P(y) là hàm mật độ xác suất (pdf) của X và Y, P(x,y) là
hàm mật độ xác suất liên hợp X và Y.

6


Trong kênh truyền, tạp âm quan trọng nhất là tạp âm nhiệt, được quy thành
một nguồn tạp âm cộng tính tại đầu vào máy thu. Tạp âm này được giả định là tạp
âm cộng trắng chuẩn (AWGẩ : Additive White Gaussian ẩ oise), tức là tạp âm có mật
phổ công suất đều trong suốt trục tần số và có biên độ tạp âm tuân theo phân bố Gaoxơ (chuẩn), kỳ vọng bằng không. Khi đó, dung lượng kênh được xác định là:
(
E^\
(1.8)
c = Wlog2 1 + ậ- (biưgiây)
l No)
ẩ ếu áp dụng tiêu chuẩn ẩ yquist và giả thiết rằng,

s = EỊỊ/ÀT (E

S

là năng

lượng tín hiệu trung bình trong khoảng thời gian AT), thì dung lượng kênh được xác
định:
(V
c = Wlog, 1 + — (bit/giây); N = N0W
V N)

(1.9)


Từ (1.9) ta thấy, khi độ rộng băng tần w bị giới hạn thì dung lượng c có thể
tăng lên khi ta tăng công suất tín hiệu truyền qua s. Mặt khác, nếu công suất tín hiệu

s không đổi thì dung lượng c có thể tăng lên khi ta tăng độ rộng băng tần w.
Định lý về mã kênh của Shannon được phát biểu như sau:
" Khỉ xem xét kênh AWGN, tồn tại mã kiểm soát lỗi sao cho có thể truyền
thông tin qua kênh với tốc độ nhỏ hom dung lượng kênh và tỷ số lỗi bit thấp tuỳỷ. ”
ẩ ghĩa là, trong trường hợp có sử dụng bộ mã kênh, khi tốc độ truyền dữ liệu nhỏ hơn
dung lượng kênh (rb < C) thì chất lượng thông tin có thể đạt được xác suất lỗi thấp
tuỳ ý, ngược lại khi tốc độ truyền dữ liệu lớn hơn hoặc bằng dung lượng kênh (r b >
C) thì chất lượng thông tin không thể đạt được xác suất lỗi thấp tuỳ ý. Trường hợp
kênh nhị phân đối xứng, nếu Định lý về mã kênh của Shannon không chỉ ra cách thức
để thiết kế bộ mã nhằm đạt được tốc độ dữ liệu tiệm cận tốc độ cực đại (r b = C) tại
xác suất lỗi thấp tuỳ ý, điều này đã đặt ra thách thức lớn cho nghiên cứu phát triển
về kỹ thuật mã kiểm soát lỗi. Giả thiết, với đường truyền không lỗi tự do (error free), tốc độ dữ liệu đạt cực đại (rb = C) thì hiệu quả sử dụng phổ đạt cực đại r|max =
C/W. Thay (1.5) vào (1.9) ta có:

7


1 + /|R^
\ (biưgiây/Hz)
o2
N,
Thay (1.4) vào (1.10) ta có: ^1 + í?m»T7is ^ (bit/giây/Hz)
^?max

(1.10)


(1.11)

*?*»*= l°g2
Giá trị Eb/No nhỏ nhất ứng với đường truyền không lỗi là khi:
Eb _ 2Vaa -1
Na

(1.12)

Nếu độ rộng băng tần không bị giới hạn thì khi w -> 00 hay TỊmax -> 0 thì
ta có Eb/N0 đạt cực tiểu.
lim — = ln2 = -1.59dB

(1.13)

Nhu vậy, khi đường truyền không lỗi thì tỷ số Efc/No đạt cực tiểu là —1.59
(xem hình 1.4).

Hình 1.4. Hiệu quả sử dụng phổ của các sơ đồ điều chế và mã hóa khác nhau
được tính toán cho trường hợp BER là 10 5 trên kênh AWGN
Kết quả của việc mã hóa đem lại thường được biểu diễn bằng độ tăng ích mã,
tức là hiệu số giữa Eb/N0 trong trường hợp có sử dụng mã và trong trường hợp không
sử dụng mã, khi xem xét tại cùng BER. Ví dụ, với hệ thống điều chế

8


BPSK kfaông mä thi dat dugc Eb/No là 9.6dB tai xâc suât loi bit là 10-5 và ri = 1
b/s/Hz. Trong khi dô giôi han cua Shannon trong truông hop này là OdB. Côn trong
tnrcmg hop su dung mä lien két nôi tiép gôm ma Reed - Solomon và ma châp thi dat

dugc Eb/N0 là 2.2dB tai xâc suât lôi bit là 10 5. Nhu vây, dô täng ich mä là 9.6 - 2.2
= 7.4dB. Vôi dô taug ich này cho phép ta giàm công suât mây phât (giàm trong lugng,
giàm ki ch thuoc và täng tuôi tho) và giâm ki ch thuoc anten.
Nhu vây, theo lÿ thuyét vân côn dé lai 2.2dB không cài thien dugc. Nhièu nô
lue sau näm 1980 và truàc nâm 1990 nhäm tâp trung giài quyét vân dè này, nhung
không tim ra dugc hucmg di moi. Hâu hét nguôi ta tâp trung vào mä châp liên két néi
tiép vài thuât toân giài mä Viterbi vô cùng phuc tap. Song dô täng ich chi them dugc
vài phân much dB, mà ta phâi trâ giâ cho chi phi quâ Ion vè dô phuc tap thiét bi và
thoi gian tinh toân. Tuy nhiên, sau 50 nam khi bài bâo cùa Shannon xuât ban, bàng
giài phâp moi nguoi ta da dat thêm dugc gân 2dB, dô là su ra dài cüa mä Turbo. Mä
Turbo vôi thuât toân giài ma lap (iterative) hâu nhu dâ khai thâc dugc khe ho vè giôi
han giüa dung lugng và chât lugng mä. Chung cô thê dat dugc Eb/N0 = 0.7dB tai
BER = 10 5 và ri = 0.5 bit/giây/Hz.
Tuy nhiên, toi nhung nâm 90 thi Mackay bâng thuât giài tông tich (Sum
Product Agorithm) chüng minh dugc räng câc mä LDPC không dèu trên kênh Gauss
chi each toi han Shannon 0.054dB. Kÿ thuât mä hôa này cô thé thay thé mä hôa
Code rate vs Performance
Eb/N0 ai BER = 1CT8

Turbo.
1.0
- - - ...........

0.9

. -4* „- -

0.8

A


à"'

_* :o

0.7

'& / i
d __

0.6

<
3

. --------

'y*

0.5

■

/

0.4

t

«*


0.3
1.0

2.0

3.0
Eb/N0 (dB)

9

--

Shannon limit (BPSK)
TPC 4K blocks TPC 1
fiK blocks

Reed-Solorn
onyVItsrbi LDPC3ÛK -OLDPC 16K
~Il
4.0
5.0


0.2

0.0
Hinh 1.5. So sânh câc so dô ma hôa LDPC, TCP, Reed - Solomon

10



1.3. Kết luận chương
Chương 1 đã giới thiệu tổng quan về hệ thống thông tin số và giới hạn
Shannon về chất lượng. Trong vài năm trước đây, mã hoá turbo đã được bàn luận và
xem như là kỹ thuật mã sửa lỗi trước FEC (Forward - Error Correction) để cải tiến
hiệu suất kênh. Giờ đây, một hướng phát hiển kỹ thuật mã hoá mới có tên gọi LDPC
- kiểm tra bit chẵn lẻ mật độ thấp (Low-Density Parity Check), đang nổi lên và có
khả năng sẽ thay thế mã hoá turbo trong việc lựa chọn FEC do nó cho phép nhà thiết
kế tiến gần hơn tới giới hạn Shannon.
Chương 2 sẽ tập trung vào cơ sở lý thuyết của các thuật toán giải mã lặp cho
mã LDPC, cụ thể là giải thuật truyền thông báo và giải thuật tổng - tích.

11


CHƯƠNG 2
MÃLDPC
2.1. Giới thiệu về bộ mã LDPC
Mã LDPC (Low Density Parity Check - Mã kiểm tra chẵn lẻ mật độ thấp), hay
còn gọi là mã Gallager, được đề xuất bởỉ Gallager vào năm 1962. về cơ bản mã này
được xem như một loại mã khối tuyến tính. Mã LDPC được xem như là bộ mã sửa lỗi
tốt đạt đến gần gỉởỉ hạn Shannon. Trong thời gian sau này người ta càng khám phá ra
khả năng kiểm soát lỗi rất cao của chúng. Vì thế mã LDPC có thể được sử dụng trong
nhiều ứng dụng thực tế như thông tin vô tuyến và lưu trữ dữ liệu. Điểm đặc biệt của
các mã LDPC là các ma trận kiểm ưa H là các ma ưận thưa, tức là có hầu hết các phần
tử của ma ưận là 0, chỉ một số ít là 1. Theo định nghĩa của Gallager, ma ưận kiểm tra
H của mã LDPC còn có đặc điểm là mỗi một hàng chứa đủng ỉ phần tử 1 và mỗi một
cột chửa đúng j phần tử 1. Một mã LDPC như vậy sẽ được gọi là một mã LDPC đều
(n, j, i), ưong đó n là độ dài khối mã và cũng chính là số cột của ma ưận H.

Tại thời điểm ra đời của mã LDPC, năng lực tính toán của máy tính còn khá
hạn chế nên các kết quả mô phỏng không phản ánh được khả năng kiểm soát lỗi cao
của mã này. Cho đến tận gần đây, đặc tính vượt ưộỉ của mã LDPC mới được chứng
minh và Mackay và Neal là hai người được coi là đã phát minh ra mã LDPC một lần
nữa nhờ sử dụng giải thuật giải mã dựa ưên giải thuật tổng - tích (Sum Procduct
Algorithm).
1
ữ
ữ
ữ
□
Cl

1
0
0
0
ũ
0

1
0
ũ
0
ũ
ũ

0
1
0

□

0
0
0

1

0
0
0

0
ũ

0

1
0

0
0
ũ
ữ

1

1

1

ũ
0
ũ

0

1
0
0
0
0
0
ũ
0
1
0
0
1
0
Ỡ
0

0
1
ũ

ũ

1
ũ


0
1

0
1
□

0
0

0
ũ

0
0

0

1
0
0

1
0
0

1
D


0

0
ũ

0

1
ủ

0
0

0
Q

0
0
0

0

1
0
0

0

0


1

0

0

0

0
0
1
ũ

0
ũ
ũ

0
0
0
0

1
0
0
ữ

0
0
0

1

0
0
1
ũ

0
0
0

0
0

0
1
0

1
a

1

1
0

ũ

1


I
0

0
0

0

0
Ö
0

D

ũ

0
0

1
0
ũ

0
0
0

1
ũ
D


1

0
0

0
0
1

0
0
0

0
□
ũ

0
0

0
0

0
0

1

0

1

ũ

0

0
0

1
0

0
0
ũ

0
0
a

1
ũ

1
a

0

0
ũ


1
0
0
ũ
0
1
0
0
0

0
0

0
0

0
0

0
1
0

0
0
1
ũ

0

0

1

1

1

1

1
ũ

0

0
ũ

ũ

1

ũ

0
ũ

0
0


0
a

1
ũ

0
ũ

0
0

0
ö

0

0

1

0
0

1
0

a

1


0
0
ũ

0
0
0
0

1

ữ

ũ

0
-1

0

0
ữ
□

0
0
0

1


ũ

0
ữ
□
ũ
ũ

0

1

0

D

1
0
G

Hình 2.1. Ma ưận kiểm ưa chẵn lẻ của mã LDPC đều (20, 3,4)
Từ định nghĩa ban đầu của Gallager, Luby dùng các tác giả khác đã đánh dấu
một bước tiến quan trọng của mã LDPC trong việc đưa ra khái niệm mã LDPC không

12


đều. Đặc điểm của mã này là số phần tử 1 trong 1 hàng cũng như số phần tử 1 trong
1 cột không đồng nhất. Các kết quả mô phỏng cho thấy các mã LDPC không đều được

xây dựng phù hợp có đặc tính tốt hom các mã LDPC đều. Tiếp theo đó, Davey và
Mackay khảo sát các mã không đều trên GF(q) với q > 2 (GF: Galois Field - trường
Galois). Theo các tác giả này, khả năng kiểm soát lỗi của loại mã trên GF(q) được cải
thiện đáng kể so với các mã trên GF(2).
Việc biểu diễn mã LDPC bằng đồ hình (graph) đóng vai trò quan trọng trong
việc xây dựng các giải thuật giải mã. Tanner được coi là người đề xuất các mã dựa
trên đồ hình. Nhiều nhà nghiên cứu khác đã phát triển các đồ hình Tanner và các đồ
hình thừa so (factor graph) chính là một dạng tổng quát của đồ hình Tanner.
Đối với quá trình giải mã cho mã LDPC, các giải thuật giải mã xác suất lặp
thường được sử dụng. McEliece cùng các tác giả khác đã chứng minh rằng các giải
thuật giải mã này có thể được xây dựng từ giải thuật truyền Belief Pearl, hay còn gọi
là giải thuật truyền thông báo (message passing algorithm), một giải thuật khá phổ
biến trong ngành trí tuệ nhân tạo. Kschischang cùng các tác giả khác đã tổng quát hóa
giải thuật truyền thông báo để xây dựng giải thuật tổng - tích. Đây là một giải thuật
có thể được áp dụng trong rất nhiều ngành khoa học kĩ thuật như trí tuệ nhân tạo, xử
lí tín hiệu số và thông tin số. Sau đây sẽ đi vào tìm hiểu quá trình mã hóa, giải mã của
bộ mã này.
Như chúng ta đã biết, mã LDPC có thể được coi là một loại mã khối tuyến
tính. Một mã khối tuyến tính c sẽ hoàn toàn được xác định bởi ma trận kiểm tra chẵn
lẻ H. H là một ma trận có kích thước Jxn trong đó n là độ dài từ mã và J > n - k với k
là độ dài từ thông tin (J = n - k khi tất cả các hàng của ma trận H độc lập tuyến tính).
Một ma trận kiểm tra chẵn lẻ được cho trong phương trình (2.1):
1 1 0 0 1 0
H= 0 1 1 0 0 1
.1 0 1 1 0 0.

13


Từ vector thông tin ban đầu U = (ui, . . u k ) , từ mã V = (Vi, . . v n ) sẽ được tạo

ra theo công thức V = U.G, trong đó G là ma trận sinh. Ở đây, c là không gian không
(null space) của H, tức là V.HT = 0, trong đó HT là ma trận chuyển vị của H. Ký hiệu
hi là hàng thứ i của ma trận H, ta có:
v.hT =0, i= 1,2, ..., J

(2.2)

Với hi là vector hàng: hi = (hn, hin). Phương trình (2.2) có thể được viết lại
n

thành:
(2.3)
Đối với một mã trên GF(2), tổng ừên chính là tổng modulo-2 của các bit mã
tương ứng với các hịj khác 0.
Tuy nhiên, tại phía thu, từ mã nhận được r = (rl5 ..., rn) có thể khác với từ mã
tại phía phát V. Tích r.HT được gọi là syndrome s = (Si, ..., Sj) và s có thể khác 0.
Nhiệm vụ của một bộ giải mã kênh truyền (channel decoder) là tìm ra từ mã đã được
phát dựa trên từ mã nhận được r. Một phương pháp giải mã thường được sử dụng cho
mã khối tuyến tính là phương pháp giải mã syndrome. 2“ từ mã có thể nhận được sẽ
được chia thành 2k nhỏm. Mỗi nhỏm có một từ mã đại diện, là một từ mã họp lệ và 2n
" k - 1 từ mã không họp lệ gần với từ mã đại diện này nhất (tính theo khoảng cách
Hamming). Từ mã nhận được thuộc về nhóm nào sẽ được giải mã thành từ thông tin
tương ứng với từ mã đại diện của nhóm đó. Tóm lại, trên cơ sở từ mã thu được, bộ
giải mã sẽ lựa chọn từ mã họp lệ có khả năng đã được gửi đi cao nhất.
2.2. Mã hóa (encoding)
Thông thường chúng ta dùng ma trận sinh G để mã hóa mã khối tuyến tính.
Nếu chúng ta dùng d để biểu diễn dữ liệu nguồn và X để biểu diễn từ mã, chúng ta có
thể sử dụng phương trình G.d = 0 để tạo từ mã. Mặc dù tính toán ma trận G một cách
trực tiếp là rất phức tạp nhưng ta có thể làm giảm độ phức tạp giải mã bằng cách sử
dụng ma trận H. Đầu tiên chúng ta tạo ra ma trận H và sau đó dùng phép thử Gaussian

(Gaussian Elimination) để chuyển đổi H thành H = [IPT]. Sau đó ta có thể tính ma
trận sinh G bằng G = [PI].

14


2.3. Giải mã (decoding)
Trong phần này ta tập trung vào các giải thuật giải mã xác suất lặp cụ thể là
giải thuật truyền belief (là một dạng của giải thuật truyền thông báo) và giải thuật tổng
tích. Trước hết, ta nhắc lại một số khái niệm và định lý về xác suất sử dụng trong giải
mã cho mã LDPC.
•

Xác suất tiên nghiệm
Xác suất tiên nghiệm (a priori probability), hay xác suất không điều kiện, để

mệnh đề A đúng, được ký hiệu là P(A).
Mệnh đề trong dấu ngoặc cũng có thể bao gồm cả đẳng thức, khi đó ta sẽ có
các biến ngẫu nhiên. Lấy ví dụ, khi ta gieo một con xúc xắc, ký hiệu biến ngẫu nhiên
X là giá trị số gieo được, ta có:
P(X = 1) = P(X = 2) = P(X = 3) = P(X = 4) = P(X = 5) = P(X = 6) = 1 / 6
Các giá trị có thể có của biến ngẫu nhiên X được gọi là miền xác định (domain)
của X.
Trong ví dụ trên đây, miền xác định của X là {1, 2, 3, 4, 5, 6}. Một mệnh đề
cũng có thể được coi là một biến ngẫu nhiên với miền xác định dưới dạng:
P(X) = {1/6, 1/6, 1/6, 1/6, 1/6,1/6}
Ta sẽ được phân phối xác suất của biến ngẫu nhiên X.
•

Xác suất hậu nghiệm

Một khi chúng tã đã có một dấu hiệu (thông tin) nào đó liên quan đến biến

ngẫu nhiên X thì xác suất tiên nghiệm không còn được sử dụng nữa. Thay vào đó, ta
sẽ sử dụng xác suất có điều kiện (conditonal probability), hay còn gọi là xác suất hậu
nghiệm (A Posteriori Probability - APP), ký hiệu là P(A|B). Đây là xác suất của sự
kiện A với tất cả các thông tin mà chúng ta đã biết là B.
Xác suất có điều kiện có thể được tính từ xác suất không điều kiện:
với P(B) > 0

P(A|5) =

Trong đó P(A, B) là xác suất để hai sự kiện A, B xảy ra đồng thời.
Phưcmg trình trên cũng có thể được viết lại thành:
P(A,B) = P(A\B)P(B)

15


Đây được gọi là qui tắc nhân (product rule). Qui tắc nhân có thể được mở
rộng cho n biến ngẫu nhiên:
Pi.Xx,...,Xn) = P{X, \x2 ,...,Xn)P{X21*3 ,...,Xn)...P(Xn_x IXn)P(Xn)
•

Phân phối hiệp xác suất
Xác suất để n biến ngẫu nhiên Xi, x 2 , ..x n lần lượt nhận các giá trị Xi, x2,

..x

n


được gọi là hiệp xác suất:
P(Xx = Xj, x 2 = x2, ..x n = Xn)
Phân phối hiệp xác suất P(X], x 2 , ..x n ) xác định hiệp xác suất của tất cả các

tổ hợp giá trị có thể có của x b x 2 , ..x n .
•

Xác suất biên
Xác suất biên P(Xj = Xi) của một phân phối hiệp xác suất P(X], x 2 , . . x n )

được định nghĩa như sau:
P(Xị = Xi) = (Ij=i...n,j*iP(Xi = X 1# x 2 = x2, ...,Xi = Xi, ...,x n = xn)
• Định lý Bayes
Sử dụng quy tắc nhân, ta có thể chứng minh được định lý Bayes:
P(*|7)P(7)
WÕ

PỢ\X) =

Tổng quát hơn, với một dấu hiệu cho trước E (còn gọi là dấu hiệu nền), ta có:
P(X\Y,E)P(Y\E)

P(Y\X,E)

P(X\E)
TV Ạ _

1 __ __ \ 4Ạ _

1


_ ___ r

X

_ 1 I Ạ ____

• ĐỘC lập và độc lập có điêu kiện
Hai biến ngẫu nhiên X và Y được gọi là độc lập nếu: P(X) = P(X|Y). Khi đó,
từ quy tắc nhân, ta có: P(X,Y) = P(X)P(Y).
Neu hai biến ngẫu nhiên X,Y chỉ độc lập khi cho trước z, X và Y được gọi
là độc lập với điều kiện Z: P(X|Z) = P(X|Y, Z).
2.3.1. Giải thuật giải mã truyền belief
2.3.1.1. Mạng belief
Mạng belief hay còn được gọi là mạng Bayes, mạng nhân quả (causal
network), mạng xác suất (probabilistic network), hay bản đồ trí thức (knowledge

16


map), là một khái niệm rất phổ biến trong ngành trí tuệ nhân tạo. Mạng belief là một
cấu trúc dữ liệu mô tả quan hệ giữa các biến ngẫu nhiên và xác định phân bố hiệp xác
suất của chúng. Đây là một mô hình mạng với những đặc điểm sau:
- Mỗi một nút mạng biểu diễn một biến ngẫu nhiên.
- Một mũi tên từ nút X đến nút Y biểu diễn tác động trực tiếp từ X lên Y. Khi
đó, X được gọi là nút cha của Y.
- Tại mỗi nút mạng có một bảng xác suất có điều kiện (conditonal probability
table - CPT) xác định ảnh hưởng của các nút cha lên nút mạng đang xét.
- Sơ đồ mạng là sơ đồ có hướng và không có các vòng kín (directed acyclic
graph - DAG).

Người ta đã nhận thấy có thể dùng mạng belief để biểu diễn quan hệ giữa các
bit trong từ mã ban đầu, từ mã bị tạp âm và syndrome của một mã LDPC. Từ đó, bằng
cách áp dụng các công thức truyền belief của mạng belief, ta có thể xây dựng giải
thuật giải mã lặp dựa trên xác suất cho mã LDPC.
• Phân bố hiệp xác suất trong mạng belief
Mạng belief có thể được sử dụng để biểu diễn các phân bố hiệp xác suất. Hiệp
xác suất được cho bởi phương trình:
P(Xi = xl A... AỊ= xn) = P(x,...,xJ = ŨPÍX' \Parents(X.)) (2.4)
i=l
Trong đó P(xi|Parents(Xj)) là xác suất để biến ngẫu nhiên Xj nhận giá ữị

Xi,

cho trước giá trị của các biến ngẫu nhiên biểu diễn bởi các nút cha của Xi trong mạng
belief.
Mặt khác, áp dụng qui tắc nhân, hiệp xác suất cũng có thể được viết dưới
dạng:
|x_2,...,x,)...P(x2 Ịx,)^*,)

= P(xn |xB_!
.

(2.5)

Ĩ=1
So sánh phương trinh (2.4) và (2.5), ta nhận thấy phương trinh của hiệp xác
suất tương đương với đẳng thức:
P(Xt |x_,,...,x,) = P(X I Parents^))

(2.6)


Với điều kiện các nút cha của Xi cũng thuộc tập các nút {Xi _ X, Xi}. Điều
kiện này có thể được thỏa mãn bằng cách đánh số các biến ngẫu nhiên theo thứ tự phù
17


hợp với cấu hình mạng.
Như vậy mạng belief có thể biểu diễn quan hệ giữa các biến ngẫu nhiên một
cách chính xác chỉ với điều kiện là: Cho trước giá trị các nút cha của một biến ngẫu
nhiên bất kỳ, biến ngẫu nhiên này sẽ độc lập có điều kiện với tất cả các nút tổ tiên của
nó. Vì vậy, khi xây dựng một mạng belief, với một nút mạng Xi, chỉ những nút trong
tập {Xi X, ..., Xi} có ảnh hưởng trực tiếp đến Xi mới được xem là các nút cha của Xi• Quan hệ độc lập có điều kiện của các biến ngẫu nhiên trong mạng belief
Trong phần trên, chúng ta đã khảo sát sự độc lập của một nút mạng với các nút
tổ tiên của nó, cho trước các nút cha. Đe xây dựng các giải thuật suy diễn (inference
algorithm), thông thường chúng ta còn cần phải khảo sát các quan hệ độc lập có điều
kiện tổng quát hom, chẳng hạn, sự độc lập của một tập các nút mạng X với một tập
các nút mạng Y, cho trước tập các dấu hiệu (Evidence) E. Đe biểu diễn quan hệ này
ta dựa vào khái niệm “phân tách theo hướng” (direction-dependent separation) gọi tắt
là “phân tách d” (d - separation). Tập nút mạng E được gọi là phân tách d hai tập nút
mạng X và Y nếu, cho trước E, tất cả các đường dẫn vô hướng từ một nút thuộc X đến
một nút thuộc Y đều bị chặn.

-o— -o
(1) o- —
—o—
—o- —
-o
(2) o- o—
—o ©r
— — -OY

(3)
*© o—
—
yO-

Hình 2.2. Các trường hợp trong đó một đường dẫn từ X sang Y bị chặn, cho
trước tập dấu hiệu E
Một đường dẫn được gọi là bị chặn cho trước tập E, nếu tồn tại một nút z thỏa

mãn một ừong hai điều kiện:

z là một nút mạng kiểu “đối đầu” (head-to-head) và z cũng như các con
cháu của z đều không thuộc tập E (trường họp 3 trong hình 2.2).
- z không phải là một nút mạng kiểu đối đầu và z là một phần tử của tập E
-

18


(trường hợp 1 và 2 trong hình 2.2).
• Suy diễn trong mạng belief
Sử dụng mạng belief, chúng ta có thể tính toán phân phối xác suất có điều kiện
(xác suất hậu nghiệm) của một tập các biến truy vấn (query variable), cho trước giá
trị chính xác của một số biến dấu hiệu (evidence variable). Nghĩa là, chúng ta phải
tính P(Q=q I E=e), trong đó Q và E lần lượt là tập các biến truy vấn và tập các biến
dấu hiệu. Dựa trên quan hệ giữa Q và E, người ta phân ra bốn kiểu suy diễn:
- Suy diễn chẩn đoán (diagnostic inference): Đây là suy diễn đi từ kết quả đến
nguyên nhân.
- Suy diễn nhân quả (causal inference): Suy diễn đi từ nguyên nhân đến kết
quả.

- Suy diễn liên nhân quả (intercausal inferrence): Suy diễn giữa các nguyên
nhân có một kết quả chung.
- Suy diễn hỗn hợp (mixed inference): Hỗn họp của nhiều loại suy diễn ở
trên.
Các kiểu suy diễn được minh họa trong hình 2.3.

Chẩn đoán ẩ hân quả Liên nhân Hỗn họp
quả
Hình 2.3. Bốn kiểu suy diễn trong mạng belief
E: biến dấu hiệu, Q: biến truy vấn
2.3.I.2. Giải thuật truyền belief
Giải thuật giải mã truyền belief là một dạng của giải thuật truyền thông báo
còn được gọi là giải thuật giải mã lật bit thực chất là một loại của giải thuật giải mã
lặp. Trong đồ án sẽ mô tả giải thuật truyền belief Pearl, giải thuật này có thể được sử
dụng để tính các xác suất có điều kiện của một tập các biến, cho trước giá trị của các
biến dấu hiệu. Trên một đồ thị có hướng, không có vòng kín (DAG) G, giải thuật
truyền belief Pearl là một giải thuật truyền thông báo phân tán trong đó các đỉnh của

19


G trao đổi thông tin về xác suất của chúng. Mỗi một nút mạng chỉ có thể nói chuyện
được với các nút cha và nút con của nó.

Hình 2.4. Đồ thị của một cây phức
X là biến truy vấn. E+ và E~~ là xác nhận kiểu nhân quả và xác nhận kiểu bằng
chứng của X. Mạng được chia thành hai phần riêng biệt dựa trên các nút cha và các
nút con của X.
Khái niệm căn bản trong mạng belief chính là Belief. Belief(xi) được định
nghĩa là xác suất có điều kiện, hay xác suất hậu nghiệm, để một biến Xi nhận giá trị

Xi, cho

trước dấu hiệu e.
Bel(xt) = p{xi \e)
Mỗi nút mạng nhận các thông báo từ các nút cha và nút con của nó, sử dụng

các thông báo này để cập nhật belief của bản thân, sau đó gửi các thông báo mới cho
các nút cha và nút con.
Để mô tả quá trình truyền thông báo, người ta đưa ra khái niệm cây (tree) và
cây phức (polytree). Cây là một đồ thị vô hướng trong đó giữa hai nút mạng bất kì chỉ
có một đường dẫn duy nhất. Một cây sẽ được gọi là cây phức nếu mỗi nút mạng có
thể có nhiều nút cha (cây phức còn được gọi là mạng kết nối đơn - singly connected
network). Một ví dụ về cây phức được cho trong hình 2.4. Ở đây, X là biến truy vấn
và E là tập các biến dấu hiệu (X không thuộc E). Giả sử ta phải tính P(X|E). Ký hiệu

u = Ui, ..., Up là tập các nút cha và Y = Yi, ..., Yc là tập các nút con của X. Với mỗi
nút mạng trong hai tập này, ta tách nút đang xét và tất cả các nút cha ông cũng như
con cháu của nó (trừ X) ra khỏi phần còn lại bằng một khung vuông có đường bao đứt

20