Bài giảng Cơ sở Lý thuyết Truyền tin - Chương 8: Cấu trúc thu tối ưu - Hà Quốc Trung

Cơ sở Lý thuyết Truyền tin-2004
Hà Quốc Trung1
1Khoa Công nghệ thông tin
Đại học Bách khoa Hà nội
Chương 8: Cấu trúc thu tối ưu 0. 1/ 39
Chương 8: Cấu trúc thu tối ưu
1 Thu tối ưu cho kênh có nhiễu công Gaussian
2 Bộ lọc phối hợp tuyến tính
3 Bộ xác định tối ưu
4 Bộ xác định cực đại khả năng
Chương 8: Cấu trúc thu tối ưu 0. 2/ 39
1. Thu tối ưu cho kênh có nhiễu công Gaussian
1 Thu tối ưu cho kênh có nhiễu công Gaussian
Bài toán
Bộ tương quan tuyến tính
Ví dụ
2 Bộ lọc phối hợp tuyến tính
3 Bộ xác định tối ưu
4 Bộ xác định cực đại khả năng
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 3/ 39
1.1.Bài toán
Xét thiết bị truyền tin số M mức (M đơn vị tín hiệu dải hẹp
sm(t),m = 1,2 . . .M), mỗi đơn vị tín hiệu truyền trong thời
gian T 0 ≤ t ≤ T
Tín hiệu khi truyền qua kênh bị nhiễu. Tín hiệu nhận được
sẽ là:
r(t) = sm(t) + n(t),0 ≤ t ≤ T
n(t) là nhiễu sinh ra trên kênh. Giả thiết trên cây chỉ có
nhiễu cộng Gaussian, mật độ công suất/tần số là
1
2N0(W/Hz)
Mục tiêu : Thiết kế bộ thu tối ưu, xác định được tín hiệu
nào trong M tín hiệu ban đầu đã được gửi đi, với xác suất
sai nhầm nhỏ nhất.
Nguyên tắc: chia thiết bị thu làm 2 thành phần:
Giải điều chế: khai triển tín hiệu trong một không gian giống
như không gian của các tín hiệu ban đầu r1r2 . . . rN
Xác định tín hiệu.
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 4/ 39
1.1.Bài toán
Bộ giải điều chế: chuyển đổi các tín hiệu nhận được thành
một tập các số thực là tọa độ của tín hiệu nhận được trong
không gian của các đơn vị tín hiệu. Bộ tương quan tuyến
tính (Correlation Demudulator), bộ lọc phối hợp tuyến tính
(Matched Filter Demodulator).
Bộ quyết định: các tọa độ thu được không luôn luôn trùng
với một đơn vị tín hiệu đã được định nghĩa. Bộ quyết định
khi đó cần phải xác định tín hiệu đã gửi đi một cách gần
đúng, sao cho sai số trung bình nhỏ nhất: Bộ quyết định tối
ưu, bộ xác định cực đại khả năng.
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 5/ 39
1.2.Bộ tương quan tuyến tính
Khai triển tín hiệu thành các tín hiệu trực giao cơ sở của
các tín hiệu truyền đi (xem lại thuật toán khai triển). Đảm
bảo sai số nhỏ nhất theo năng lượng tín hiệu.
Tín hiệu đầu ra bộ tương quan tuyến tính
T∫
0
r(t)fk(t)dt =
T∫
0
[sm(t) + n(t)] fk(t)dt ,1 ≤ k ≤ N
Có thể viết thành
rk = smk + nk
với
Smk =
T∫
0
r(t)fk(t)dt , k = 1,2, ....N
nk =
T∫
0
n(t)fk(t)dt , k = 1,2, ....N
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 6/ 39
1.2.Bộ tương quan tuyến tính (Tiếp)
Tín hiệu truyền đi được biểu diễn chính xác bằng các tín
hiệu trực giao smk . Tín hiệu thu được biểu diễn bằng các
thành phần rk (là các giá trị vô hướng) với sai số là n′(t)
thỏa mãn
r(t) =
N∑
k=1
smk(t)fk(t)+
N∑
k=1
nk fk(t)+n′(t) =
N∑
k=1
rk(t)fk(t)+n′(t)
từ đó
n′(t) = n(t)−
N∑
k=1
nk fk(t)
n′(t) là thành phần nhiễu không khai triển được trong
không gian tín hiệu. Vậy có thể bỏ qua n′(t) trong quá trình
xác định tín hiệu.
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 7/ 39
1.2.Bộ tương quan tuyến tính (Tiếp)
Các thành phần còn lại của nhiễu có phân bố chuẩn
Gaussian. Giá trị trung bình
T∫
0
E [n(t)] fk(t)dt = E(nk) = 0
Hàm tương quan chéo
E(nknm) = 12N0
T∫
0
T∫
0
E[m(t)n(τ)fk(t)fm(τ)dtdτ =
= 12N0
T∫
0
T∫
0
δ(t − τ)fk(t)fm(τ)dtdτ = 12N0
T∫
0
fk(t)fm(t)dt = 12N0δmk
trong đó δmk =
{
1, Nếu m = k
0, Nếu m 6= k
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 8/ 39
1.2.Bộ tương quan tuyến tính (Tiếp)
Vậy các thành phần của nhiễu không tương quan, sai
phương chung σ2n =
1
2N0, là các biến ngẫu nhiên độc lập
thống kê
Các tín hiệu đầu ra thu được cũng là các biến ngẫu nhiên
gaussian độc lập thống kê, với giá trị trung bình smk , sai
phương 12N0
Mật độ phân bố xác suất của tín hiệu đầu ra
p(r |sm) =
N∏
k=1
p(r |smk),m = 1, ...,M
p(r |smk) = 1√N0 exp
[
−
N∑
k=1
(rk−smk )2
N0
]
Hay
p(r |sm) = 1(√
N0
)N/2 exp
[
−
N∑
k=1
(rk − smk)2
N0
]
, m = 1, ...,M
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 9/ 39
1.2.Bộ tương quan tuyến tính (Tiếp)
Có thể kiểm chứng lại khẳng định n′(t) không liên quan
đến các rk
E(n′(t), rk) = E(n′(t), smk) + E(n′(t)nk) = E(n′(t)nk)
E
{[
n(t)−
N∑
j=1
nj fj(t)
]
nk
}
=
T∫
0
E [n(t)n(τ)] fk(τ)dτ −
N∑
j=1
E
(
njnk
)
ff (t)
= 12Nofk(t)− 12Nofk(t) = 0
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 10/ 39
1.2.Bộ tương quan tuyến tính (Tiếp)
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 11/ 39
1.3.Ví dụ
Xét trường hợp đơn giản, khi có M tín hiệu tương ứng với M
xung tín hiệu với M mức khác nhau (PAM băng tần cơ sở m
mức). Mỗi tín hiệu có độ dài T, biên độ a
g(t) =
{
a, 0 ≤ t ≤ T ;
0, t T
Khai triển trực giao các tín hiệu đầu vào
Năng lượng của tín hiệu
ζ =
T∫
0
g2(t)dt = a2T
Chỉ có một hàm cơ sở
f (t) = 1√
a2T
g(t) =
{
1√
T , 0 ≤ t ≤ T
0, nếu không.
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 12/ 39
1.3.Ví dụ (Tiếp)
Đầu ra của bộ giải điều chế là
r =
∫ T
0
r(t)f (t)dt = 1√
T
∫ T
0
r(t)dt =
1√
T
[∫ T
0
sm(t)dt +
∫ T
0
n(t)dt
]
= sm + n
Giá trị trung bình của nhiễu bằng 0, vậy giá trị trung bình
của tín hiệu đầu ra cũng bằng 0. Phương sai của tín hiệu
đầu ra bằng phương sai của nhiễu và bằng N02
Hàm mật độ phân bố xác suất có điều kiện
p(r |sm) = 1√
piN0
exp
[
− (r − sm)
2
N0
]
Chương 8: Cấu trúc thu tối ưu 1. Thu tối ưu cho kênh có nhiễu công Gaussian 13/ 39
2. Bộ lọc phối hợp tuyến tính
1 Thu tối ưu cho kênh có nhiễu công Gaussian
2 Bộ lọc phối hợp tuyến tính
Nguyên tắc
Tính chất của bộ lọc phối hợp
Biểu diễn bộ lọc phối hợp trong miền tần số
3 Bộ xác định tối ưu
4 Bộ xác định cực đại khả năng
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 14/ 39
2.1.Nguyên tắc
Thay các bộ tương quan bằng các bộ lọc tuyến tính với
đáp ứng xung
hk(t) = fk(T − t),0 ≤ t ≤ T
Tín hiệu đầu ra của các bộ lọc sẽ là yk(t) =
t∫
0
r(τ)h(t − τ)dτ =
t∫
0
r(τ)fk(T − t + τ)dτ , k = 1, ...,N
Lấy mẫu tại thời điểm t = T yk(T ) =
T∫
0
r(τ)fk(τ)dτ = rk
Đầu ra thu được giống đầu ra của bộ tương quan.
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 15/ 39
2.1.Nguyên tắc (Tiếp)
Một bộ lọc có đặc tính xung h(t) = s(T − τ) với s(t) xác
định trong khoảng 0 ≤ t ≤ T gọi là bộ lọc phối hợp tuyến
tính. Tín hiệu đầu ra của bộ lọc này sẽ là
y(t) =
t∫
0
s(t)s(T − t + τ)dτ
chính là hàm tự tương quan của s(t)
Trong bộ giải điều chế trên, có N bộ lọc phối hợp với hàm
cơ sở fk(t)
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 16/ 39
2.1.Nguyên tắc (Tiếp)
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 17/ 39
2.2.Tính chất của bộ lọc phối hợp
Trong tất cả các bộ lọc, đây là bộ lọc cực đại hóa tỷ lệ tín
hiệu/nhiễu
Tính chất trên không phụ thuộc vào dạng của tín hiệu s(t)
Xét tín hiệu r(t) gồm tín hiệu s(t) và nhiễu n(t) với hệ số
nhiễu φnn(f ) = 1/2N0, cho qua một hệ thống có đáp ứng
xung h(t). Cần tìm h(t) để tỷ lệ công suất nhiễu/tín hiệu ở
đầu ra nhỏ nhất.
Tín hiệu đầu ra của bộ lọc
y(t) =
t∫
0
r(τ)h(t−τ)dτ =
t∫
0
s(τ)h(t−τ)dτ+
t∫
0
n(τ)h(t−τ)dτ
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 18/ 39
2.2.Tính chất của bộ lọc phối hợp (Tiếp)
Vào thời điểm lấy mẫu
y(T ) =
T∫
0
s(τ)h(t−τ)dτ+
T∫
0
n(τ)h(t−τ)dτ = ys(T )+yn(T )
Tỷ lệ tín hiệu/ nhiễu:
y2s (t)
E[y2n (t)]
Mẫu số
E[y2n (t)] =
T∫
0
T∫
0
E[n(τ)n(t)]h(T − t)h(T − τ)dtdτ =
=
1
2
N0
T∫
0
T∫
0
δ(t−τ)h(T−t)h(T−τ)dtdτ = 1
2
N0
T∫
0
h2(T−t)dt
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 19/ 39
2.2.Tính chất của bộ lọc phối hợp (Tiếp)
Áp dụng bất đẳng thức Cauchy cho tử số
y2s (T ) =
[∫ T
0
s(τ)h(t − τ)dτ
]2
≤[∫ T
0
s2(τ)dτ
][∫ T
0
h2(T − τ)dτ
]
Vậy tỷ lệ tín hiệu/nhiễu bị chặn trên bởi[
T∫
0
s2(τ)dτ
][
T∫
0
h2(T − τ)dτ
]
1
2N0
∫ T
0 h2(T − t)dt
=
2
N0
T∫
0
s2(t)dt = 2CN0
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 20/ 39
2.2.Tính chất của bộ lọc phối hợp (Tiếp)
Dấu bằng xảy ra khi
h(t) = Cs(T − t)
, có nghĩa là h(t) phối hợp với s(t)
Tính chất này của bộ lọc phối hợp không phụ thuộc tính
chất của s(t)
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 21/ 39
2.3.Biểu diễn bộ lọc phối hợp trong miền tần số
Từ h(t) = s(T − t) có thể tính được hàm chuyển đổi theo
tần số
H(f ) =
∫ T
0
s(T − t)e−2jpiftdt = e−2jpifT
∫ T
0
s(τ)ej2pifτdτ =
S∗(f )e−2jpift
Phổ biên độ tần số của bộ lọc giống của tín hiệu, ngược về
pha
Tín hiệu ra trong miền tần số
ys(t) =
∞∫
−∞
Y (f )ej2piftdf =
∞∫
−∞
|S(f )|2e−j2pifTej2pift
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 22/ 39
2.3.Biểu diễn bộ lọc phối hợp trong miền tần số (Tiếp)
Lấy mẫu tại thời điểm T có
ys(T ) =
∞∫
−∞
|S(f )|2df = C
Phổ mật độ công suất nhiễu ở đầu ra của bộ lọc
Φ0(f ) =
1
2
|H(f )|2N0
Công suất nhiễu của đầu ra
Pn =
∞∫
−∞
Φ0(f )df =
1
2
N0
∞∫
−∞
|H(f )|2df = 1
2
N0
∞∫
−∞
|S(f )|2df = CN0
2
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 23/ 39
2.3.Biểu diễn bộ lọc phối hợp trong miền tần số (Tiếp)
Tỷ lệ tín hiệu/nhiễu khi đó sẽ là
y2s (T )
CN0
2
=
2C
N0
Chương 8: Cấu trúc thu tối ưu 2. Bộ lọc phối hợp tuyến tính 24/ 39
3. Bộ xác định tối ưu
1 Thu tối ưu cho kênh có nhiễu công Gaussian
2 Bộ lọc phối hợp tuyến tính
3 Bộ xác định tối ưu
Nguyên tắc
Ví dụ
4 Bộ xác định cực đại khả năng
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 25/ 39
3.1.Nguyên tắc
Căn cứ vào các vecto nhận được r1, r2, . . . rN xác định đầu
vào thích hợp nhất. Nguyên tắc cơ bản là xác định theo xác
suất hậu nghiệm P(sm|r) cực đại. Tiêu chuẩn này sẽ cực
đại xác suất xác định đúng, cực tiểu xác suất xác định sai
Theo công thức Bayes
P(sm|r) = P(r |sm)P(sm)P(r)
có thể viết lại thành
P(sm|r) = P(r |sm)P(sm)M∑
m=1
p(r |sm)P(sm)
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 26/ 39
3.1.Nguyên tắc (Tiếp)
Mẫu số độc lập với tín hiệu truyền đi, do đó với một tín hiệu
cụ thể, bài toán chuyển về tìm tín hiệu đầu vào sao cho
p(r |sm) cực đại. Hàm số này còn được gọi là hàm số khả
năng
Xác định cực đại của hàm khả năng đơn giản hơn so với
xác định cực đại của xác suất hậu nghiệm. Hai kết quả
giống nhau nếu các tín hiệu đầu vào đẳng xác suất
Với kênh có nhiễu Gaussian, xác suất tín hiệu đầu ra có
thể tính được:
p(r |sm) = 1(√
N0
)N/2 exp
[
−
N∑
k=1
(rk − smk)2
N0
]
, m = 1, ...,M
Lấy loga hai vế
lnp(r |sm) = −12N ln(piN0)−
1
N0
N∑
k=1
(rk − smk)2
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 27/ 39
3.1.Nguyên tắc (Tiếp)
Việc tìm cực đại của xác suất tương đương với việc tìm cực
tiểu của
D(r , sm) =
N∑
k=1
(rk − smk)2
Đây là khoảng cách tối thiểu giữa các giá trị thu được và tín
hiệu ban đầu
Tính toán khoảng cách đòi hỏi khối lượng tính toán lớn
(không có hàm khoảng cách, không có mạch tính khoảng
cách)
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 28/ 39
3.1.Nguyên tắc (Tiếp)
Cần tìm một khoảng cách khác dễ tính hơn
D(r , sm) = |r |2 − 2rsm + |sm|2
. Nếu các tín hiệu đầu vào cùng công suất, thì việc tìm min
D chuyển về tìm max của
rsm =
∫ T
0
r(t)sm(t)dt
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 29/ 39
3.1.Nguyên tắc (Tiếp)
Vậy có thể xây dựng được bộ xác định tín hiệu
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 30/ 39
3.2.Ví dụ
Xét tín hiệu PAM s1 = −s2 =
√
ζb có xác suất tiên nghiệm
là p,1− p
Tín hiệu nhân được ở đầu ra sau giải điều chế sẽ là vector
một chiều, với giá trị
r = ±
√
ζb + yn(T )
, với hai hàm mật độ xác suất có thể là
p(r |s1) = 1√
2piσ2n
exp
[
−(r −
√
ζb)
2
2σ2n
]
p(r |s2) = 1√
2piσ2n
exp
[
−(r +
√
ζb)
2
2σ2n
]
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 31/ 39
3.2.Ví dụ (Tiếp)
Xác suất có thể của r nếu tín hiệu truyền đi là s1 hoặc s2
PM(r , s1) = p.p(r |s1) = p√
2piσ2n
exp
[
−(r −
√
ζb)
2
2σ2n
]
PM(r , s2) = (1− p).p(r |s1) = 1− p√
2piσ2n
exp
[
−(r +
√
ζb)
2
2σ2n
]
Nếu PM(r , s1) > PM(r , s2) chọn s1 nếu không chọn s2.
Điều kiện trên tương đương với
PM(r , s1)
PM(r , s2)
> 1
hay
p
1− p exp
[
(r −√ζb)2 − (r −
√
ζb)
2
2σ2n
]
> 1
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 32/ 39
3.2.Ví dụ (Tiếp)
Log hóa hai vế và chuyển vế√
ζbr >
1
2
σ2n ln
1− p
p
r > σ
2
n
2
√
ζb
ln
1− p
p
Bài toán chuyển về so sánh tín hiệu nhận được với một giá
trị trung gian, nếu lớn hơn, chọn tín hiệu dương, nếu không
chọn tín hiệu âm
Đặc biệt khi p = 1− p = 1/2, mốc để so sánh chính là
điểm 0
Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 33/ 39
4. Bộ xác định cực đại khả năng
1 Thu tối ưu cho kênh có nhiễu công Gaussian
2 Bộ lọc phối hợp tuyến tính
3 Bộ xác định tối ưu
4 Bộ xác định cực đại khả năng
Tín hiệu điều chế có nhớ
Nguyên tắc xác định tín hiệu
Thuật toán Viterby
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 34/ 39
4.1.Tín hiệu điều chế có nhớ
Điều chế tín hiệu tại thời điểm hiện tại phụ thuộc vào việc
điều chế tín hiệu tại thời điểm truớc đó
Ví dụ: điều chế vi sai, điều chế NRZI
Biểu diễn tín hiệu điều chế có nhớ: sơ đồ lưới giống Trellis
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 35/ 39
4.2.Nguyên tắc xác định tín hiệu
Xét ví dụ tín hiệu điều chế NRZI. Tín hiệu đầu vào chỉ có
một chiều, vậy tín hiệu đầu ra chỉ có một chiều
Để có thể xác định được chuỗi tín hiệu vào khi đã biết
chuỗi tín hiệu ra, cần xác định chuỗi tín hiệu vào có khả
năng lớn nhất
Đầu ra cho mỗi ký hiệu đầu vào
rk = ±
√
ζb + nk
trong đó nk là biến ngẫu nhiên chuẩn Gaussian, trị trung
bình 0, phương sai
σ2n =
1
2
N0
với phân bố xác suất của tín hiệu đầu ra
p(rk |s1) = 1√2piσn exp
[
− (rk−
√
σb)
2
2σ2n
]
p(rk |s2) = 1√2piσn exp
[
− (rk+
√
σb)
2
2σ2n
]
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 36/ 39
4.2.Nguyên tắc xác định tín hiệu (Tiếp)
Xác suất xuất hiện của một chuỗir1, r2, ....rK sẽ là
p(r1r2...rk |s(m)) =
M∏
k=1
p(rk |s(m)k ) =
K∏
k=1
1√
2piσn
exp
[
−

rk−s(m)k
2
2σ2n
]
=
(
1√
2piσn
)K
exp
[
K∑
k=1
−

rk−s(m)k
2
2σ2n
]
Cần xác định chuỗi đầu vào sao cho giá trị của xác suất
trên là lớn nhất
Vậy cần xác định cực tiểu của
D(r , s(m)) =
K∑
k=1
(rk − s(m)k )2
Đây chính là đường đi ngắn nhât trong lưới từ thời điểm 1
đến thời điểm K
Để xác định đường đi ngắn nhất: dùng thuật toán Viterby
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 37/ 39
4.3.Thuật toán Viterby
Để có thể xác định đường đi ngắn nhất ta xác định đường
đi từng đoạn một. Vì nguồn có bộ nhớ 1, nên ta xét các
đoạn đường có chiều dài 2
Hệ thống xuất phát từ trạng thái S0 ở thời điểm 0
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 38/ 39
4.3.Thuật toán Viterby (Tiếp)
Tại thời điểm 2T, để có trạng thái S1 có hai đường đi có
thể. Lấy đường đi có giá trị nhỏ nhất trong hai đường đi
D0(0,0) = (r1 +
√
ςb)
2 + (r2 +
√
ςb)
2
D0(1,1) = (r1 −√ςb)2 + (r2 +√ςb)2
Tại thời điểm 2T, để có trạng thái S0 có hai đường đi có
thể. Lấy đường đi có giá trị nhỏ nhất trong hai đường đi
D1(0,1) = (r1 +
√
ςb)
2 + (r2 −√ςb)2
D1(1,0) = (r1 −√ςb)2 + (r2 −√ςb)2
Vậy chỉ còn hai đường đi có thể từ trạng thái S0 đi
Tiếp tục làm như vậy ở thời điểm 3T, 4T... cho đến KT
Bài toán tìm đường đi ngắn nhất có thể giải trong thời gian
đa thức
Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 39/ 39