›

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

pdf 39 trang huongle 3930
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở Lý thuyết Truyền tin-2004 - Chương 8: Cấu trúc thu tối ưu - Hà Quốc Trung", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_ly_thuyet_truyen_tin_2004_chuong_8_cau_truc_thu_toi_uu.pdf

Nội dung text: Cơ sở Lý thuyết Truyền tin-2004 - Chương 8: Cấu trúc thu tối ưu - Hà Quốc Trung

  1. 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
  2. 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
  3. 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
  4. 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 2 N0(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
  5. 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
  6. 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 T Z Z r(t)fk (t)dt = [sm(t) + n(t)] fk (t)dt, 1 ≤ k ≤ N 0 0 Có thể viết thành rk = smk + nk với T R Smk = r(t)fk (t)dt, k = 1, 2, N 0 T R nk = n(t)fk (t)dt, k = 1, 2, N 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 6/ 39
  7. 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 0 thành phần rk (là các giá trị vô hướng) với sai số là n (t) thỏa mãn N N N X X 0 X 0 r(t) = smk (t)fk (t)+ nk fk (t)+n (t) = rk (t)fk (t)+n (t) k=1 k=1 k=1 từ đó N 0 X n (t) = n(t) − nk fk (t) k=1 n0(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 n0(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
  8. 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 Z E [n(t)] fk (t)dt = E(nk ) = 0 0 Hàm tương quan chéo T T 1 R R E(nk nm) = 2 N0 E[m(t)n(τ)fk (t)fm(τ)dtdτ = 0 0 T T T 1 R R 1 R 1 = 2 N0 δ(t − τ)fk (t)fm(τ)dtdτ = 2 N0 fk (t)fm(t)dt = 2 N0δmk 0 0 0  1, Nếu m = k trong đó δ = mk 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
  9. 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 2 1 phương chung σn = 2 N0, 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 1 phương 2 N0 Mật độ phân bố xác suất của tín hiệu đầu ra N Q p(r|sm) = p(r|smk ), m = 1, , M k=1  N  (r −s )2 p(r|s ) = √1 exp − P k mk mk N0 N0 k=1 Hay " N 2 # 1 X (r − smk ) p(r|s ) = exp − k , m = 1, , M m √ N/2  N0 N0 k=1 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
  10. 1.2.Bộ tương quan tuyến tính (Tiếp) Có thể kiểm chứng lại khẳng định n0(t) không liên quan đến các rk 0 0 0 0 E(n (t), rk ) = E(n (t), smk ) + E(n (t)nk ) = E(n (t)nk ) (" N # ) P E n(t) − nj fj (t) nk = j=1 T N R P  E [n(t)n(τ)] fk (τ)dτ − E nj nk ff (t) 0 j=1 1 1 = 2 Nofk (t) − 2 Nofk (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
  11. 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
  12. 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  a, 0 ≤ t ≤ T ; g(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 ZT ζ = g2(t)dt = a2T 0 Chỉ có một hàm cơ sở ( 1 √1 , 0 ≤ t ≤ T f (t) = √ g(t) = T a2T 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
  13. 1.3.Ví dụ (Tiếp) Đầu ra của bộ giải điều chế là Z T 1 Z T r = r(t)f (t)dt = √ r(t)dt = 0 T 0 " # 1 Z T Z T √ sm(t)dt + n(t)dt = sm + n T 0 0 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 N0 đầu ra bằng phương sai của nhiễu và bằng 2 Hàm mật độ phân bố xác suất có điều kiện  2  1 (r − sm) p(r|sm) = √ exp − πN0 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
  14. 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
  15. 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 t R R r(τ)h(t − τ)dτ = r(τ)fk (T − t + τ)dτ, k = 1, , N 0 0 T R Lấy mẫu tại thời điểm t = T yk (T ) = r(τ)fk (τ)dτ = rk 0 Đầ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
  16. 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à t Z y(t) = s(t)s(T − t + τ)dτ 0 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
  17. 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
  18. 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 t t t Z Z Z y(t) = r(τ)h(t−τ)dτ = s(τ)h(t−τ)dτ+ n(τ)h(t−τ)dτ 0 0 0 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
  19. 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 T T Z Z y(T ) = s(τ)h(t−τ)dτ + n(τ)h(t−τ)dτ = ys(T )+yn(T ) 0 0 Tỷ lệ tín hiệu/ nhiễu: 2 ys (t) 2 E[yn (t)] Mẫu số T T Z Z 2 E[yn (t)] = E[n(τ)n(t)]h(T − t)h(T − τ)dtdτ = 0 0 T T T 1 Z Z 1 Z = N δ(t−τ)h(T −t)h(T −τ)dtdτ = N h2(T −t)dt 2 0 2 0 0 0 0 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
  20. 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ố 2 "Z T # 2 ys (T ) = s(τ)h(t − τ)dτ 0 ≤ "Z T #"Z T # s2(τ)dτ h2(T − τ)dτ 0 0 Vậy tỷ lệ tín hiệu/nhiễu bị chặn trên bởi " T #" T # R 2 R 2 s (τ)dτ h (T − τ)dτ T 0 0 2 Z 2 = s2(t)dt = C 1 R T 2 N0 h (T − t)dt N0 N0 2 0 0 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
  21. 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
  22. 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ố Z T Z T H(f ) = s(T − t)e−2jπft dt = e−2jπfT s(τ)ej2πf τ dτ = 0 0 S∗(f )e−2jπft 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ố ∞ ∞ Z Z j2πft 2 −j2πfT j2πft ys(t) = Y (f )e df = |S(f )| e e −∞ −∞ 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
  23. 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ó ∞ Z 2 ys(T ) = |S(f )| df = C −∞ Phổ mật độ công suất nhiễu ở đầu ra của bộ lọc 1 Φ (f ) = |H(f )|2N 0 2 0 Công suất nhiễu của đầu ra ∞ ∞ ∞ Z 1 Z 1 Z N P = Φ (f )df = N |H(f )|2df = N |S(f )|2df = C 0 n 0 2 0 2 0 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
  24. 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à y2(T ) 2 s = C CN0 N 2 0 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
  25. 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
  26. 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(r|s )P(s ) P(s |r) = m m m P(r) có thể viết lại thành P(r|s )P(s ) P(s |r) = m m m M P p(r|sm)P(sm) m=1 Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 26/ 39
  27. 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: " N 2 # 1 X (r − smk ) p(r|s ) = exp − k , m = 1, , M m √ N/2  N0 N0 k=1 Lấy loga hai vế N 1 1 X 2 ln p(r|sm) = − N ln(πN0) − (rk − smk ) 2 N0 k=1 Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 27/ 39
  28. 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 N X 2 D(r, sm) = (rk − smk ) k=1 Đâ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
  29. 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 2 2 D(r, sm) = |r| − 2rsm + |sm| . 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 Z T rsm = r(t)sm(t)dt 0 Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 29/ 39
  30. 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
  31. 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ị p r = ± ζb + yn(T ) , với hai hàm mật độ xác suất có thể là √ 1  (r − ζ )2  p(r|s ) = √ exp − b 1 2 2 2πσn 2σn √ 1  (r + ζ )2  p(r|s ) = √ exp − b 2 2 2 2πσn 2σn Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 31/ 39
  32. 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 √ p  (r − ζ )2  PM(r, s ) = p.p(r|s ) = √ exp − b 1 1 2 2 2πσn 2σn √ 1 − p  (r + ζ )2  PM(r, s ) = (1 − p).p(r|s ) = √ exp − b 2 1 2 2 2πσn 2σn 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, s ) 1 > 1 PM(r, s2) hay √ √ p (r − ζ )2 − (r − ζ )2  b b > exp 2 1 1 − p 2σn Chương 8: Cấu trúc thu tối ưu 3. Bộ xác định tối ưu 32/ 39
  33. 3.2.Ví dụ (Tiếp) Log hóa hai vế và chuyển vế p 1 1 − p ζ r > σ2 ln b 2 n p σ2 1 − p r > √n ln 2 ζb 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
  34. 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
  35. 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
  36. 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 p rk = ± ζb + nk trong đó nk là biến ngẫu nhiên chuẩn Gaussian, trị trung bình 0, phương sai 1 σ2 = N n 2 0 với phân bố xác suất của tín hiệu đầu ra √ h (r − σ )2 i p(r |s ) = √ 1 exp − k b k 1 2σ2 2πσn √n h (r + σ )2 i √ 1 k b p(rk |s2) = exp − 2 2πσn 2σn Chương 8: Cấu trúc thu tối ưu 4. Bộ xác định cực đại khả năng 36/ 39
  37. 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à   2 M K " (m) # (m) rk−sk p(r r r |s(m)) = Q p(r |s ) = Q √ 1 exp − 1 2 k k k 2πσ 2σ2 = = n n k 1   k 1 " (m) 2 #  K K rk−s = √ 1 exp P − k 2πσ 2σ2 n k=1 n 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 K (m) X (m) 2 D(r, s ) = (rk − sk ) k=1 Đâ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
  38. 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
  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 √ 2 √ 2 D0(0, 0) = (r1 + ςb) + (r2 + ςb) √ 2 √ 2 D0(1, 1) = (r1 − ςb) + (r2 + ςb) 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 √ 2 √ 2 D1(0, 1) = (r1 + ςb) + (r2 − ςb) √ 2 √ 2 D1(1, 0) = (r1 − ςb) + (r2 − ςb) 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