Nghiên cứu bộ lọc thích nghi

Chương 1. BỘ LỌC SỐ Bộ lọc số là hệ thống tuyến tính bất biến theo thời gian. Thông số vào và ra của hệ thống quan hệ với nhau bằng tổng chập trong phương trình (1.1.5). Y(Z)=H(Z).X(Z) (1.1.1) Chuyển đổi miền Z của đáp ứng xung đơn vị H(Z) được gọi là hàm hệ thống. Biến đổi Fourier của đáp ứng xung đơn vị H(ejw) là một hàm phức của w, biểu diễn theo phần thực và phần ảo là: H(ejw)=Hr(ejw)+jHi(ejw) (1.1.2) Hoặc biểu diễn dưới dạng góc pha: (1.1.3) Một hệ thống tuyến tính bất biến nhân quả là dạng có h(n)=0 với n<0. Một hệ thống ổn định là dạng với tất cả các thông số đưa vào hữu hạn sẽ có thông số ra hữu hạn. Điều kiện cần và đủ cho một hệ thống tuyến tính bất biến ổn định là: (1.1.4) Điều kiện này giống với công thức (1.2.5). Thêm vào đó, tất cả các hệ thống tuyến tính bất biến có các thông số vào và ra như các bộ lọc thoả mãn phương trình sai phân có dạng: (1.1.5) Chuyển đổi sang miền Z cả hai vế của phương trình ta được: (1.1.6) So sánh hai phương trình trên, từ phương trình sai phân (1.1.3) ta có thể đạt được H(Z) trực tiếp bằng cách đồng nhất các hệ số của phần tử vào trễ trong (1.1.5) với các luỹ thừa tương ứng Z-1. Hàm hệ thống H(Z) là một hàm hữu tỉ của Z-1. Nó có thể được biểu diễn bằng dạng điểm cực và điểm không trong mặt phẳng Z. Như vậy H(Z) có thể viết dạng: (1.1.7) Như chúng ta đã xét trong miền Z, hệ thống nhân quả sẽ có miền hội tụ dạng . Nếu hệ thống cũng là ổn định thì R1 phải nhỏ hơn giá trị đơn vị, do đó miền hội tụ bao gồm là vòng tròn đơn vị. Như vậy trong hệ thống bất biến, nhân quả thì tất cả các điểm cực của H(Z) phải nằm trong vòng tròn đơn vị. Để thuận tiện, ta phân thành các lớp hệ thống, những lớp này bao gồm hệ thống đáp ứng xung hữu hạn (Finit duration Impulse Response_FIR), và hệ thống đáp ứng xung vô hạn (Infinit duration Impulse Response_IIR). 1.1. Hệ thống FIR Nếu các hệ số ak trong phương trình (1.1.5) bằng không, khi đó phương trình sai phân sẽ là: (1.1.8) So sánh (1.3.8) với (1.1.5b) chúng ta thấy rằng: (1.1.9) Hệ thống FIR có rất nhiều thuộc tính quan trọng, trước tiên chúng ta chú ý rằng H(Z) chỉ có điểm không là một đa thức của Z-1 và tất cả các điểm cực của H(Z) đều bằng không, tức là H(Z) chỉ có điểm không. Thêm nữa, hệ thống FIR có thể có chính xác pha tuyến tính. Nếu h(n) xác định theo công thức sau: (1.1.10) thì H(ejw) có dạng: (1.1.11) H(ejw) chỉ có phần thực hoặc phần ảo tuỳ thuộc vào phương trình (1.1.10) lấy dấu (+) hay dấu (-). Dạng pha tuyến tính chính xác thường rất hữu ích trong các ứng dụng xử lý âm thanh, khi mà xác định thứ tự thời gian là cần thiết. Các thuộc tính này của bộ lọc FIR cũng có thể đơn giản hoá vấn đề xấp xỉ, nó chỉ xét đến khi đáp ứng độ lớn cần thiết. Khoảng sai số mà được bù để thiết kế các bộ lọc với đáp ứng xung pha tuyến tính chính xác là phần mà một khoảng thời gian tồn tại đáp ứng xung phù hợp được yêu cầu để xấp xỉ phần nhọn bộ lọc bị cắt đi. Dựa trên những thuộc tính chung với bộ lọc FIR pha tuyến tính, người ta đã phát triển ba phương pháp thiết kế xấp xỉ. Những phương pháp này là: - Thiết kế cửa sổ. - Thiết kế mẫu tần số. - Thiết kế tối ưu. Chỉ có phương pháp đầu tiên là phương pháp phân tích, thiết kế khối khép kín tạo bởi các phương trình có thể giải để nhận được các hệ số bộ lọc. Phương pháp thứ hai và phương pháp thứ ba là phương pháp tối ưu hoá, nó sử dụng phương pháp lặp liên tiếp để được thiết kế bộ lọc: Z-1 x(n) + Z-1 x(n-1) + Z-1 x(n-2) + x(n-M) + x(n-M-1) b0 b1 b2 bM-1 bM Hình 1.1. Mạng số cho hệ thống FIR Bộ lọc số thường được biểu diễn dạng biểu đồ khối, như hình (1.3) ta biểu diễn phương trình sai phân (1.1.8). Sơ đồ như vậy thường được gọi là một cấu trúc bộ lọc số. Trên sơ đồ, biểu diễn các toán tử yêu cầu tính giá trị mỗi dãy ra từ giá trị của dãy đưa vào. Những phần tử cơ bản của sơ đồ biểu diễn ý nghĩa phép cộng, nhân các giá trị của dãy với hằng số (các hằng số trên nhánh hàm ý phép nhân), và chứa các giá trị trước của dãy vào. Vì vậy biểu đồ khối đưa ra chỉ dẫn rõ ràng về tính phức tạp của hệ thống. 1.2. Hệ thống IIR Nếu hàm hệ thống của phương trình (1.1.7) có các điểm cực cũng như điểm không, thì phương trình sai phân (1.1.5) có thể viết: (1.1.12) Phương trình này là công thức truy hồi, nó có thể được sử dụng để tính giá trị của dãy ra từ các giá trị trước đó của thông số ra và giá trị hiện tại, trước đó của dãy đầu vào. Nếu M<N trong phương trình (1.1.7), thì H(Z) có thể biến đổi về dạng: (1.1.13) Cho hệ thống nhân quả, ta dễ dàng biểu diễn: (1.1.14) Ta có thể thấy rằng dãy h(n) có chiều dài vô hạn. Tuy nhiên, vì công thức truy hồi (1.1.12) thường dùng để thực hiện bộ lọc IIR, nó sử dụng ít phép tính hơn là đối với bộ lọc FIR. Điều này đặc biệt đúng cho các bộ lọc lựa chọn tần số cắt nhọn. Có nhiều phương pháp thiết kế sẵn có cho bộ lọc IIR. Những phương pháp thiết cho bộ lọc lựa chọn tần số (thông thấp, thông dải, ...) một cách chung nhất là dựa trên những biến đổi của thiết kế tương tự: - Các thiết kế Butterword. - Các thiết kế Bessel. - Các thiết kế Chebyshev. - Các thiết kế Elliptic. Tất cả những phương pháp trên dùng phép phân tích tự nhiên và được ứng dụng rộng rãi để thiết kế các bộ lọc IIR. Thêm vào đó các phương pháp tối ưu hoá IIR đã được phát triển cho thiết kế xấp xỉ liệt kê, điều này không dễ thích nghi với một trong các phương pháp xấp xỉ trên. Sự khác nhau chính giữa FIR và IIR là IIR không thể thiết kế để có pha tuyến tính chính xác, khi mà FIR có những thuộc tính này, còn bộ lọc IIR hiệu quả hơn trong thực hiện lọc cắt nhọn hơn là FIR. Mạng bao hàm phương trình (1.1.12) được biểu diễn trong hình 1.4a cho trường hợp N=M=3, nó thường được gọi là dạng biểu diễn trực tiếp. Phương trình sai phân (1.3.12) có thể được chuyển sang dạng tương đương. Đặc biệt bộ phương trình sau thường được sử dụng: (1.1.15) Bộ phương trình này có thể biểu diễn như trong hình 1.4b, với bộ nhớ để lưu giữ được yêu cầu và chứa các giá trị dãy trễ. Phương trình (1.1.7) chỉ ra rằng H(Z) có thể biểu diễn như một tích các điểm cực. Những điểm cực và điểm không này là các cặp liên hiệp phức, vì các hệ số ak và bk là thực. Bằng những nhóm liên hiệp phức điểm cực và điểm không trong cặp liên hợp phức, nó cũng có thể biểu diễn H(Z) như tích của các hàm hệ thống cơ bản cấp hai dạng: (1.1.16) Z-1 x(n) + Z-1 + Z-1 b0 b1 b2 b3 + + Z-1 + Z-1 + Z-1 a1 a2 a3 + + y(n) K là phần nguyên của (N+1)/2. Hệ thống cấp hai này được biểu diễn như trong hình 1.5a cho trường hợp N=M=4: (a) x(n) + + b0 b1 b2 b3 + + Z-1 + Z-1 + Z-1 a1 a2 a3 + + y(n) w(n) (b) Hình 1.2. (a) Cấu trúc dạng trực tiếp. (b) Cấu trúc dạng trực tiếp tối giản. Tiếp tục, một cấp độ cao hơn được xét đến. Dạng phân số mở rộng của phương trình (1.3.13) cho ta hướng khác để biểu diễn. Bằng cách kết hợp những phần liên quan đến cực liên hợp phức, H(Z) có thể viết dạng: (1.1.17) Điều này gợi ý một dạng sơ đồ song song biểu diễn như hình 1.5b cho N=4: x(n) + + b10 b11 b12 + Z-1 + Z-1 + a11 a12 + y(n) + + b20 b21 b22 + Z-1 + Z-1 + a21 a22 + (a) c10 x(n) + + c11 + Z-1 + Z-1 a11 a12 y(n) + + + c20 c21 + Z-1 + Z-1 a21 a22 (b) Hình 1.3. (a) Dạng tầng (b) Dạng song song Trong những ứng dụng lọc tuyến tính, dạng song song đưa ra những đặc tính cao hơn về phương diện làm tròn giảm tiếng ồn, các sai số hệ số, và tính ổn định. Chương 2. BỘ LỌC THÍCH NGHI 2.1. Bộ lọc FIR thích nghi dạng trực tiếp Từ chuẩn bình phương tối thiểu đưa tới khuôn mẫu chung thiết lập công thức tuyến tính cho hệ số bộ lọc. (2.1.1) Dãy tự tương quan và tương quan chéo nhận được từ dữ liệu, do đó chúng mô tả những ước lượng của dãy tương quan và tự tương quan thực. Hệ số h(k) ở (2.1.1) cũng là những ước lượng của hệ số thực. Độ chính xác của các ước lượng phụ thuộc vào độ dài của bản ghi dữ liệu, đó là 1 vấn đề cần cân nhắc trong hệ thống xử lí của bộ lọc. Vấn đề thứ 2 cần quan tâm đó là quá trình ngẫu nhiên cơ bản x(n) thường xuyên không ổn định. Ví dụ, trong bộ hiệu chỉnh kênh, các thông số đặc trưng cho tần số có thể biến đổi theo thời gian. Như 1 hệ quả, các dãy tương quan và tự tương quan thống kê, và các ước lượng của chúng thay đổi theo thời gian. Điều này làm cho hệ số của bộ lọc thích nghi cũng phải thay đổi theo thời gian để phản ánh được các thông số thay đổi theo thời gian của tín hiệu ở đầu vào bộ lọc. Điều này cũng kéo theo chất lượng của ước lượng không thể tăng bằng cách đơn giản là tăng số mẫu tín hiệu được sử dụng trong ước lượng các dãy tương quan và tự tương quan. Có nhiều cách để hệ số của bộ lọc có thể biến đổi theo thời gian cùng với các thông số thống kê theo thời gian của tín hiệu. Phương pháp phổ biến nhất là đưa vào bộ lọc dựa trên các mẫu liên tiếp một cách đệ quy mỗi khi nhận được một mẫu tín hiệu. Cách thứ 2 là ước lượng và trên cơ sở các khối liên tiếp, và không duy trì sự liên tục của các giá trị của hệ số bộ lọc từ một khối dữ liệu tới một khối khác. Kích thước khối phải tương đối nhỏ, chiếm một khoảng thời gian ngắn khi so sánh với khoảng thời gian mà các đặc trưng thống kê của dữ liệu thay đổi một cách đáng kể. Khi nghiên cứu về các thuật toán của bộ lọc thích nghi, ta chỉ chú ý tới các thuật toán đệ quy thời gian mà nó cập nhật hệ số dựa trên các mẫu liên tiếp. Trong thực tế ta xét tới hai dạng thuật toán: thuật toán LMS (Least Mean Squares), là thuật toán dựa trên kiểu gradient hướng theo sự thay đổi theo thời gian của các thông số đặc trưng của tín hiệu, và loại thật toán bình phương tối thiểu đệ quy, là thuật toán phức tạp hơn so với LMS. 2.1.1. Tiêu chuẩn lỗi trung bình bình phương tối thiểu (MMES) Thuật toán LMS được xác định dễ dàng nhất bằng cách lập công thức tối ưu tính hệ số của bộ lọc FIR như một sự ước lượng dựa trên việc tối thiểu hóa lỗi bình phương trung bình. Ta giả sử có dãy dữ liệu x(n) là các mẫu từ việc xử lí ngẫu nhiên dãy tự tương quan: (2.1.2) Từ những mẫu này ta ước lượng dãy d(n) bằng cách đưa x(n) qua bộ lọc FIR với hệ số bộ lọc h(n), . Đầu ra của bộ lọc là (2.1.3) Với là ước lượng của d(n) với lỗi ước lượng là: (2.1.4) Lỗi trung bình phương như là một hàm của hệ số bộ lọc: (2.1.5)Với và là vector hệ số. là liên hợp của là chuyển vị của Ta thấy rằng MSE là hàm bậc 2 của hệ số bộ lọc. Do đó giá trị nhỏ nhất của dẫn tới việc thiết lập biểu thức tuyến tính M l = 0,1,.. … …, M-1 (2.1.6) Bộ lọc có hệ số nhận được từ (2.1.6) (2.1.6 là công thức Wiener-Hopf) được gọi là bộ lọc Wiener. Khi so sánh (2.1.6) và (2.1.1) ta thấy rằng chúng cùng dạng. Ở 2.1.1 ta dùng sự ước lượng về tự tương quan và tương quan chéo để xác định hệ số bộ lọc, trong khi ở (2.1.6) người ta dùng dãy tự tương quan và tương quan chéo thống kê được, vì thế (2.1.6) cung cấp hệ số bộ lọc tối ưu trong hướng MSE, trong khi (2.1.1) đưa ra sự ước lượng về hệ số tối ưu. Biểu thức 2.1.6 ở dạng ma trận như sau: (2.1.7) Với là ma trận Toeplizt ()với thành phần và bằng vetor tương quan chéo với thành phần . Và ta có hệ số bộ lọc tối ưu là: (2.1.8) Và: (2.1.9) Với H là chuyển vị liên hợp. Việc thiết lập biểu thức tuyến tính (2.1.6) cũng có thể thực hiện bằng cách đưa ra nguyên lí trực giao trong việc ước lượng trung bình bình phương. Theo nguyên lí này, lỗi ước lượng trung bình bình phương được tối thiểu hóa khi e(n) trực giao với ước lượng (2.1.10) l=0,1,… … … ,M-1 Hoặc tương đương với: (2.1.11) Nếu ta thay thế e(n) trong (2.1.11) bằng e(n) trong (2.1.4) và sử dụng phép toán trung bình ta nhận được biểu thức như (2.1.6). Do là trực giao với e(n), lỗi bình phương trung bình nhỏ nhất là: (2.1.12) Hệ số bộ lọc tối ưu như ở (2.1.8) có thể được thực hiện một cách hiệu quả khi dùng thuật toán Levinson-Durbin. Tuy nhiên ta cần chú ý tới việc dùng phương pháp gradient, việc đó dẫn tới thuật toán LMS cho bộ lọc. 2.1.2. Thuật toán Widrow LMS Có nhiều phương pháp để thiết lập biểu thức tuyến tính (2.1.6) hay (2.1.7) cho hệ số bộ lọc tối ưu. Ở đây ta xét tới phương pháp đệ quy, nó cho phép tìm cực tiểu của một hàm nhiều biến, MSE là một hàm bậc 2 của hệ số bộ lọc, do vậy hàm này có duy nhất một giá trị cực tiểu và chúng ta sẽ xác định nó bằng cách lặp nhiều lần. Ta giả thiết ma trận tự tương quan và vector tương quan chéo đã biết trước, do đólà hàm đã biết của hệ số h(n), . Các thuật toán để tính toán một cách đệ quy hệ số bộ lọc và tìm cực tiểu của có dạng: n=0,1,... … … (2.1.13) Với là vector của hệ số bộ lọc tại bước lặp thứ n là độ lớn bước nhảy tại bước lặp thứ n là vector hướng cho bước lặp thứ n Giá trị ban đầu được chọn tùy ý. Phương pháp đơn giản nhất để tìm cực tiểu của một cách đệ quy là dựa vào việc tìm theo sự hạ thấp của đường dốc, ở phương pháp này vector , với g(n) là vector gradient tại bước nhảy thứ n. (2.1.14) Do đó ta sẽ tính vector gradient cho mỗi bước nhảy và thay đổi giá trị của theo gradient chiều ngược, và ta có thuật toán đệ quy dựa trên phương pháp tìm theo sự hạ thấp của đường dốc là: (2.1.15) Tương đương với: (2.1.16) Ta không chứng minh thuật toán dẫn tới việc hộ tụ tới khi , dãy độ lớn bước nhảy hoàn toàn khả tổng và khi . Một số thuật toán khác cho ta sự hội tụ nhanh hơn như thuật toán liên hợp gradient và thuật toán Fletcher-Powel. Trong thuật toán liên hợp gradient: (2.1.17) Với là hàm vô hướng của vector gradient Trong thuật toán Fletcher-Powel: (2.1.18) Với là ma trận dương và nó hội tụ ngược với . Rõ ràng 3 thuật toán có cách xác định hướng vector khác nhau. Ba thuật toán trên là thích hợp khi và đã biết, tuy nhiên đó không phải là trường hợp trong các ứng dụng của bộ lọc thích nghi. Khi không biết và ta có thể thay thế ước lượng cho thực tế. Đầu tiên, chú ý rằng vecter gradient ở (2.1.14) cũng có thể được thể hiện ở điều kiện trực giao như trong (2.1.10), thực tế (2.1.10) tương đương với: (2.1.19) Với là vector với các thành phần, . Do vậy vector gradient là: (2.1.20) Từ (2.1.20) ta có ước lượng khá chính xác về vector gradient: (2.1.21) Với và là bộ mẫu tín hiệu M trong bộ lọc ở bước lặp thứ n, khi thay cho ta có thuật toán: (2.1.22) Và nó gọi là thuật toán hạ bậc gradient ngẫu nhiên, thuật toán này được áp dụng phổ biến trong các bộ lọc thích nghi để sử dụng thuật toán độ lớn bước cố định vì hai lí do. Một là thuật toán độ lớn bước cố định được thực hiện dễ dàng với cả phần cứng và phần mềm. Thứ hai, một bước nhảy đã ấn định kích thước thì thích ứng với dòng tín hiệu thay đổi theo thời gian, trong khi nếu khi , Với và là bộ mẫu tín hiệu M trong bộ lọc ở bước lặp thứ n, khi thay cho g(n) ta có thuật toán: (2.1.22) Và nó gọi là thuật toán hạ bậc gradient ngẫu nhiên, thuật toán này được áp dụng phổ biến trong các bộ lọc thích nghi để sử dụng thuật toán độ lớn bước cố định vì hai lí do. Một là thuật toán độ lớn bước cố định được thực hiện dễ dàng với cả phần cứng và phần mềm. Thứ hai, một bước nhảy đã ấn định kích thước thì thích ứng với dòng tín hiệu thay đổi theo thời gian, trong khi nếu khi , việc thích nghi với sự thay đổi của tín hiệu không thể xảy ra. Vì những lí do đó (2.1.22) có thể được viết: (2.1.23) Với là kích thước bước nhảy đã được ấn định. Thuật toán này được đưa ra đầu tiên bởi Windrow và Hoft (1960), giờ đây nó được biết đến rộng rãi với cái tên thuật toán LMS (Least Mean Square). Rõ ràng, nó là thuật toán gradient ngẫu nhiên. Thuật toán LMS là thuật toán sử dụng dễ dàng, vì thế nó được dùng rộng rãi trong nhiều ứng dụng của bộ lọc thích nghi. Các thuộc tính và giới hạn của nó được nghiên cứu kĩ lưỡng. Trong phần dưới đây, ta sẽ đưa ra bản tóm tắt về các thuộc tính quan trọng của nó liên quan tới sự hội tụ, độ ổn định và nhiễu do việc ước lượng vector gradient. Sau đó ta sẽ so sánh thuộc tính của nó với các thuật toán bình phương tối thiểu đệ quy phức tạp hơn. Nhiều biến dạng của thuật toán LMS cơ bản được đặt ra trên lí thuyết và được thực hiện trong một vài ứng dụng của bộ lọc, một trong số đó là: nếu ta lấy trung bình các vector gradient qua nhiều lần lặp để điều chỉnh hệ số bộ lọc, ví dụ trung bình K vector gradient là: (2.1.24) Và theo công thức đệ quy, việc thiết lập hệ số bộ lọc ở mỗi bước lặp K là: (2.1.25) Việc lấy trung bình như ở (2.1.24) giảm nhiễu trong việc ước lượng vector gradient. Một cách khác là đặt một bộ lọc thông thấp và dùng đầu ra của nó để ước lượng vector gradient. Ví dụ, một bộ lọc thông thấp đơn giản cung cấp vector gradient ở đầu ra: (2.1.26) Với xác định dải thông của bộ lọc thông thấp. Khi , dải thông bộ lọc nhỏ và việc lấy trung bình được thực hiện trên rất nhiều vector gradient. Mặt khác, khi nhỏ bộ lọc có dải thông lớn và do đó ít vector gradient được lấy trung bình hơn. Với g’(n) ở (2.1.26) ta nhận được một phiên bản mới của thuật toán LMS: (2.1.27) 2.1.3. Thuộc tính của thuật toán LMS Trên thực tế ta tập trung vào thuộc tính hộ tụ, tính ổn định và việc xử lí nhiễu phát sinh khi thay thế vector gradient nhiễu cho vector gradient thực. Việc ước lượng nhiễu của vector gradient làm cho hệ số bộ lọc dao động ngẫu nhiên, và do đó việc giải thích thuộc tính của thuật toán được thực hiện bằng cách thống kê. Tính hội tụ và ổn định của thuật toán LMS được nghiên cứu bằng việc xác định cách mà giá trị trung bình của hM(n) hội tụ tới hệ số tối ưu hopt. (2.1.28) Với và I là ma trận đồng nhất. Hệ thức đệ quy (2.1.28) được thể hiện bởi hệ thống điều khiển vòng kín như ở hình 2.1. Tốc độ hội tụ và tính ổn định của hệ thống này được điều khiển bằng cách chọn kích cỡ bước nhảy . Để xác định trạng thái hội tụ thuận tiện nhất là tách rời M phương trình sai phân đồng thời cho ở (2.1.28) bằng cách sử dụng phương pháp biến đổi tuyến tính vector hệ số trung bình . Khi chú ý tới ma trận tự tương quan , ta có biến đổi tương ứng: (2.1.29) Với U là ma trận chuẩn hóa của và A là đường chéo của ma trận với các thành phần , bằng với giá trị riêng của . Thay (2.1.29) vào (2.1.28) ta có:  (2.1.30) Với và + Filter Hình 2.1 hệ thống điều khiển kín Tính hội tụ và ổn định được xác định từ công thức đồng nhất: (2.1.31) Ta có: (2.1.32) Với C là hằng số tùy ý. là dãy bước nhảy đơn vị. Rõ ràng hội tụ tới 0 khi: Tương đương với: 2.1.33) Tốc độ hội tụ cực đại khi: . Điều kiện ở (2.1.33) cho sự hội tụ của phương trình sai phân đồng nhất đối với hệ số bộ lọc thứ k (mô hình thứ k của hệ thống kín) phải thỏa mãn cho mọi k=0, 1, ..., M-1. Do vậy dải giá trị của đảm bảo sự hội tụ của vector hệ số trong thuật toán LMS là: (2.1.34) Với là giá trị riêng lớn nhất của Do là một ma trận tự tương quan, giá trị riêng của nó không âm. Do vậy cận trên của là: (2.1.35) Với là nguồn tín hiệu đầu vào, nó dễ dàng được ước lượng từ tín hiệu nhận được, do vậy cận trên của là . LMS hội tụ nhanh khi nhỏ. Tuy nhiên, ta không thể có điều kiện như mong muốn và vẫn thỏa mãn cận trên khi có một khoảng cách lớn giữa giá trị riêng lớn nhất và nhỏ nhất của . Nói cách khác, nếu ta chọn bằng , tốc độ hội tụ của LMS sẽ được xác định bởi sự suy giảm của mô hình tương ứng tới giá trị nhỏ nhất . Ở mô hình này, thay vào công thức (2.1.32) ta có Tỉ số giới hạn tốc độ hội tụ, nếu sự hội tụ sẽ chậm và ngược lại khi . Một đặc tính quan trọng nữa của LMS là nhiễu do việc sử dụng ước lượng của vector gradient. Nhiễu này làm cho hệ số bộ lọc dao động ngẫu nhiên quanh giá trị tối ưu và điều đó làm tăng giá trị cực tiểu của MSE ở đầu ra của bộ lọc. Do đó tổng MSE là với là lỗi bình phương trung bình dư. Tổng MSE ở đầu ra bộ lọc có thể được viết như sau: (2.1.36) Với hopt là hệ số tối ưu của bộ lọc được xác định bởi (2.1.8). được gọi là đường cong tiếp thu Khi thay như ở (6.2.29) và biến đổi trực giao tuyến tính ta có: (2.1.37) Với được coi là lỗi trong hệ số bộ lọc thứ k (trong hệ thống sắp xếp trực giao). Và lỗi bình phương trung bình dư là: (2.1.38) Ta giả sử giá trị trung bình của hệ số bộ lọc hM(n) hội tụ tới giá trị tối ưu của nó là hopt. Và phần trong (2.1.23) là vector nhiễu trung bình không. Hiệp phương sai của nó là: (2.1.39) Ta giả sử không liên quan tới vector tín hiệu, dù giả thiết này không chặt chẽ lắm nhưng nó rút ngắn dẫn dắt và cho kết quả đầy đủ. Và (2.1.40) Đối với vector hệ số , cộng thêm nhiễu, ta có: (2.1.41) Với là vector nhiễu cộng thêm, nó liên quan tới vector nhiễu qua biến đổi (2.1.42) Có thể thấy ma trận hiệp phương sai của vector nhiễu là: (2.1.43) Do vậy các thành phần M của không liên quan tới nhau và mỗi thành phần có một sai số . Do các thành phần M của không liên quan tới nhau nên ta có thể tách riêng M công thức, mỗi công thức bậc nhất thể hiện một bộ lọc với đáp ứng xung . Khi một bộ lọc bị ảnh hưởng bởi dãy nhiễu , nhiễu ở đầu ra của bộ lọc là (2.1.44) Ta giả thiết là nhiễu trắng, và (2.1.44) được rút gọn: (2.1.45) Thay (2.1.45) vào (2.1.38) ta có: (2.1.46) Khi coi với mọi k, ta được: (2.1.47) Với là công suất tín hiệu vào. Ta thấy lỗi bình phương trung bình dư thì tỉ lệ thuận với bước nhảy . Do đó khi chọn phải đảm bảo hội tụ nhanh và lỗi bình phương trung bình dư nhỏ. Trên thực tế, mong muốn có , ta có Tương đương: (2.1.48) Trong điều kiện ổn định phải thỏa mãn (2.1.48). Nói cách khác, lỗi bình phương trung bình dư cũng làm giảm đáng kể chất lượng bộ lọc thích nghi. Những lí giải về lỗi bình phương trung bình dư ở trên là dựa vào giả thiết giá trị trung bình của hệ số bộ lọc hội tụ tới giá trị tối ưu . Ở điều kiện đó, kích thước bước nhảy phải thỏa mãn (2.1.48). Mặt khác, ta đã xác định để vector hệ số trung bình hội tụ thì điều kiện cần là . Trong khi việc chọn gần với cận trên có thể dẫn tới sự hội tụ ban đầu của thuật toán gradient, khi mở rộng sẽ làm thuật toán gradient LMS ngẫu nhiên mất ổn định. Tính hội tụ ban đầu hay trạng thái nhất thời của LMS được nhiều nhà khoa học nghiên cứu. Họ chỉ ra rằng kích thước bước nhảy tỉ lệ thuận với độ dài bộ lọc thích nghi. Cận trên (2.1.48) là cần thiết để đảm bảo sự hội tụ ban đầu của LMS gradient ngẫu nhiên. Thực tế thường chọn . Trong hoạt động của LMS, việc chọn kích thước bước nhảy quan trọng hơn. Ta có thể giảm lỗi bình phương trung bình dư bằng cách giảm tới điểm mà tại đó tổng của lỗi bình phương trung bình đầu ra giảm. Điều đó xảy ra khi các thành phần gradient được ước lượng, sau phép nhân bởi thông số độ lớn bậc nhỏ (nhỏ hơn một nửa của bit nhỏ nhất trong biểu diễn điểm cố định của hệ số bộ lọc). Do đó điều quan trọng là kích thước bước nhảy phải đủ rộng để hệ số bộ lọc hội tụ tới . Nếu muốn giảm kích thước bước nhảy một cách đáng kể thì điều cần thiết là phải tăng độ chính xác của hệ số bộ lọc. Thông thường, 16 bits được dùng cho các hệ số bộ lọc, với từ 8 đến 12 bits dùng cho xử lí số học trong lọc dữ liệu, từ 4 đến 8 bits cho xử lí thích nghi. Các thành phần gradient ước lượng dùng số bit ít nhất. Cuối cùng, ta cần chỉ ra rằng thuật toán LMS thích ứng với dòng tín hiệu thống kê biến đổi chậm theo thời gian, như trong trường hợp cực tiểu MSE và hệ số tối ưu biến đổi theo thời gian. Nói cách khác, là một hàm theo thời gian. LMS chứa một loại lỗi khác, đó là lỗi trễ, là lỗi giá trị bình phương trung bình giảm cùng với việc tăng kích thước bước nhảy. Tổng lỗi MSE giờ là (2.1.49) Nếu ta vẽ và như một hàm của, ta có hình 2.2. Ta thấy khi tăng thì tăng còn lại giảm, từ đó thấy giá trị mà tại đó tổng lỗi là nhỏ nhất. Khi tín hiệu biến đổi nhanh theo thời gian lỗi trễ sẽ lấn át chất lượng bộ lọc. như trong trường hợp , khi giá trị lớn nhất của được dùng. Khi đó thuật toán LMS không còn thích hợp cho các ứng dụng và cần tới một thuật toán phức tạp hơn, thuật toán bình phương tối thiểu đệ quy, để có được sự hội tụ nhanh hơn và bám sát. 2.1.4. Thuật toán bình phương tối thiểu đệ quy Lợi thế cơ bản của LMS là cách tính toán đơn giản. Tuy nhiên, nó lại hội tụ chậm đặc biệt khi các giá trị riêng của ma trận tự tương quan có khoảng cách lớn. Nhìn theo quan điểm khác, thuật toán LMS chỉ có một thông số để điều khiển tốc độ hội tụ, đó là. Do bị hạn chế bởi cận trên để đảm bảo tính ổn định, các giá trị riêng nhỏ hơn nên hội tụ rất chậm. Để có được sự hội tụ nhanh hơn, cần có một thuật toán hoàn chỉnh hơn cho nhiều thông số hơn. Thực tế, nếu ma trận tự tương quan có các giá trị riêng không bằng nhau , ta phải dùng một thuật toán có M thông số, mỗi thông số cho một giá trị riêng. Để dẫn tới các thuật toán cho sự hội tụ nhanh hơn, ta cần chấp nhận thay thế phép xấp xỉ thống kê dựa trên chuẩn MSE bằng chuẩn bình phương tối thiểu. Ta sẽ quan tâm trực tiếp tới dữ liệu và nhận được ước lượng về tương quan từ dữ liệu. Điều thuận lợi để thể hiện thuật toán bình phương tối thiểu là dạng ma trận, các thuật toán đệ quy trong miền thời gian. Cũng cần phải đưa chỉ số thời gian và vector hệ số bộ lọc dãy lỗi. Vector hệ số bộ lọc ở miền thời gian n là: (2.1.50) Với chỉ số M là độ dài bộ lọc. Tương tự, vector tín hiệu đầu vào của bộ lọc là: (2.1.51) Giả sử với n<0. Điều này được gọi là lấy dữ liệu vào qua cửa sổ. Bình phương tối thiểu đệ quy giờ tính toán như sau: Giả sử ta đã có vector và ta muốn xác định vector hệ số sao cho nó làm giảm tối thiểu độ lớn của lỗi bình phương. (2.1.52) Với lỗi được định nghĩa là khoảng cách giữa dãy mong muốn và dãy ước lượng (2.1.53) Với là chỉ số và . Chỉ số là để xử lí hầu hết các điểm dữ liệu mới và do đó cho phép hệ số bộ lọc đáp ứng được các thông số đặc trưng biến đổi theo thời gian của dữ liệu. điều đó được thực hiện bằng cách sử dụng hệ số trọng số lũy thừa với dữ liệu chuyển qua. Tương tự, ta có thể sử dụng cửa sổ trượt độ dài hữu hạn với trọng số đồng dạng trên toàn kích thước cửa sổ. Ta có: (2.1.54) Với là kích thước cửa sổ trượt. Việc tối thiểu hóa mà vẫn ổn định vector hệ số bộ lọc dẫn tới thiết lập công thức tuyến tính (2.1.55) Với là ma trận tương quan tín hiệu. (2.1.56) là vector tương quan chéo: (2.1.57) Từ (2.1.55) có: (2.1.58) Rõ ràng ma trận giống ma trận tự tương quan trong khi ma trận giống vector tương quan chéo . Tuy nhiên cần nhấn mạnh rằng không phải là ma trận Toeplizt như . Ta cũng cần chú ý tới giá trị nhỏ của n, không tính được đảo của . Như trong trường hợp cộng thêm ma trận vào , với là ma trận đồng nhất và là hằng số dương nhỏ. Giả sử ta có (2.1.58) ở (n-l) (ví dụ ta có ) và ta muốn tính , do đó trong thực tế không thể thiết lập các biểu thức tuyến tính M cho mỗi thành phần tín hiệu mới. Thay vào đó ta có thể tính ma trận và vector một cách đệ quy. Đầu tiên, tính (2.1.59) Ta gọi (2.1.59) là biểu thức cập nhật thời gian cho . Do đảo của là cần thiết, ta dùng bổ đề đảo ma trận: (2.1.60) Ta đặt để thuận tiện cho việc xác định vector khuếch đại Kalman: (2.1.61) Với vô hướng: (2.1.62) Khi đó (2.1.60) trở thành: (2.1.63) Nhân (2.1.63) với ta có: (2.1.64) Do vậy vector khuếch đại Kalman cũng được định nghĩa như . Ta dùng ma trận đảo để lập biểu thức tính hệ số bộ lọc một cách đệ quy. Do: (2.1.65) Và: (2.1.66) Ta có (2.1.67) Ta thấy rằng là đầu ra của bộ lọc thích nghi ở thời điểm n dựa vào hệ số bộ lọc ở thời điểm . Do đó: (2.1.68) Và: (2.1.69) (2.1.70) Tương đương: (2.1.71) Giả sử ta có hệ số bộ lọc tối ưu , ma trận và vector . Khi nhận được một tín hiệu mới ta lập vector bằng cách tách phần từ và cộng thêm phần . Và hệ số bộ lọc được tính một cách đệ quy như sau: 1. Tính đầu ra của bộ lọc: (2.1.72) 2. Tính lỗi: (2.1.73) 3. Tính vector Kalman: (2.1.74) 4. Cập nhật ma trận đảo của ma trận tương quan: (2.1.75) 5. Cập nhật vector hệ số của bộ lọc: (2.1.76) Thuật toán đệ quy được thiết lập bởi (2.1.72) qua (2.1.76) gọi là thuật toán bình phương tối thiểu đệ quy (RLS). Ban đầu đặt và là số dương nhỏ. Phần lỗi bình phương trung bình còn dư do việc tối ưu hóa là: (2.1.77) Từ (2.1.76) ta thấy các hệ số bộ lọc thay đổi theo thời gian một lượng bằng . Do là một vector thứ nguyên, mỗi hệ số bộ lọc sẽ được diều khiển bởi 1 trong những thành phần của . Vì vậy, ta có được sự hội tụ nhanh. Ngược lại, biểu thức thay đổi theo thời gian của các hệ số bộ lọc sử dụng trong thuật toán LMS: (2.1.78) Tìm thừa số LDU và thuật toán căn bậc hai. Thuật toán LMS chỉ có một thông số để điều khiển tốc độ hội tụ. Thuật toán RLS ở trên rất dễ dàng chấp nhận làm tròn nhiễu trong hoạt động của thuật toán với phép toán độ chính xác giới hạn. Vấn đề chính của việc làm tròn xảy ra khi cập nhật . Để khắc phục vấn đề này, ta có thể khai triển hoặc ma trận tương quan hoặc nghịch đảo của nó . Ta hãy xét khai triển LDU của . (2.1.79) Với là ma trận (phần dưới) dạng tam giác với các phần tử là đường chéo ma trận và các phần tử là ma trận (phần trên) tam giác. Các phần tử trên đường chéo của bằng 1. Để thay cho việc tính một cách đệ quy, ta có thể xác định công thức cập nhật và một cách trực tiếp. Từ (2.1.75) và (2.1.79) ta có (2.1.80) Với: (2.1.81) Phần bên trong ngoặc của (2.1.80) là ma trận Hermitian và có thể được viết dưới dạng: (2.1.82) Sau đó thay (2.1.82) vào (2.1.80): (2.1.83) Và: (2.1.84) Kết quả thuật toán nhận được từ (2.1.84) phụ thuộc trực tiếp vào vector dữ liệu và không phụ thuộc vào bình phương dữ liệu. Vì thế thuật toán bình phương bị loại bỏ và ảnh hưởng của lỗi làm tròn được giảm thiểu. Thuật toán RLS nhận được từ việc khai triển hoặc được gọi là thuật toán căn bậc hai RLS. Thuật toán RLS nhanh Thuật toán RLS dạng trực tiếp và dạng căn bậc hai có cách tính toán phức tạp tỉ lệ với . Mặt khác, thuật toán giàn RLS (ở 2.3) lại tỉ lệ với M. các thuật toán giàn loại bỏ việc nhân ma trận xuất hiện khi tính . Bằng cách sử dụng các công thức cho giàn LMS ở trước và sau phần 2.3 ta có thể nhận được các biểu thức theo thời gian của vector khuếch đại Kalman mà hoàn toàn không dùng tới việc nhân ma trận. Các thuật toán phức tạp tỉ lệ với M được gọi là thuật toán RLS nhanh cho bộ lọc FIR dạng trực tiếp. 2.1.5. Các thuộc tính của thuật toán RLS dạng trực tiếp Thuật toán RLS hơn LMS ở chỗ là có sự hội tụ nhanh. Trạng thái đặc trưng này được thể hiện ở 2.2 (diễn tả tốc độ hội tụ của 2 thuật toán đối với kênh cân bằng FIR thích nghi có độ dài M=11. Ma trận tự tương quan dành cho tín hiệu nhận có tỉ lệ giá trị riêng là . Tất cả các hệ số bộ cân bằng ban đầu được đặt bằng 0. Kích thước bước nhảy thuật toán LMS , là giá trị tối ưu đảm bảo cho cả tốc độ hội tụ cả lỗi bình phương trung bình dư. Thuật toán gradient RLS Thuật toán w=0.999 Số lần lặp Lỗi Sự hội tụ nhanh hơn của RLS thể hiện rất rõ. Nó hội tụ trong ít hơn 70 lần lặp (70 mẫu tín hiệu) trong khi thuật toán LMS không hội tụ trong hơn 600 lần lặp. tốc độ hội tụ này của RLS vô cùng quan trọng trong các ứng dụng khi mà tín hiệu thay đổi nhanh theo thời gian. Không kể tới chất lượng tự hiệu chỉnh cao, thuật toán RLS của bộ lọc thích ứng FIR có 2 nhược điểm lớn. Một là cách tính toán phức tạp. Thuật toán căn bậc hai tỉ lệ với , RLS nhanh tỉ lệ với M nhưng hệ số tỉ lệ bằng 4 đến 5 lần so với LMS. Nhược điểm thứ hai là đặc tính nhạy của nó khi làm tròn lỗi tích lũy khi tính toán đệ quy. Trong một vài trường hợp, lỗi làm tròn khiến cho thuật toán không ổn định. Thuộc tính của RLS được nghiên cứu bởi nhiều nhà nghiên cứu. Bảng 2.1 đưa ra kết quả mô phỏng lỗi bình phương trong trạng thái ổn định của thuật toán căn bậc hai RLS, RLS nhanh và LMS với các độ dài từ khác nhau. Việc mô phỏng được thực hiện với bộ cân bằng thích ứng có độ dài M=11. Với chỉ số trọng số lũy thừa đối với RLS là và kích thước bước nhảy đối với LMS. Nhiễu cộng thêm là 0.001, đầu ra MSE với tính toán chính xác là . Ta có thể chỉ ra rằng thuật toán RLS dạng trực tiếp trở nên mất ổn định và do đó không thể làm việc với các phép toán 16 bits. Đối với thuật toán này, cần 24 bits. Mặt khác, thuật toán căn bậc hai làm việc dưới 9 bits, RLS nhanh làm việc khá tốt dưới 11 bits trong thời gian ngắn, với 500 lần lặp, nếu số lần lặp lớn hơn thuât toán sẽ mất ổn định. Điều đó dẫn gây tích lũy lỗi làm tròn. Số bit Thuật toán RLS Square root Fast RLS LMS 16 13 11 10 9 8 2.17 2.33 6.14 17.6 75.3 2.17 2.21 3.34 2.30 2.30 19.0 77.2 311.0 1170.0 Bảng 2.1 Độ chính xác của các thuật toán bộ lọc thíc nghi FIR. 2.2. Bộ lọc thích nghi dạng thang lưới. Bộ lọc FIR có thể được thực hiện với cấu trúc giàn với thông số giàn được gọi là hệ số phản xạ, được liên kết với các hệ số bộ lọc ở dạng trực tiếp. Có phương pháp để chuyển đổi hệ số bộ lọc FIR thành hệ số phản xạ. Trong phần này ta nghiên cứu các thuật toán của bộ lọc thích nghi với cấu trúc giàn hoặc giàn hình thang. Các thuật toán này dựa trên phương pháp bình phương tối thiểu và có nhiều thuộc tính mong muốn, đưa ra cách tính toán hiệu quả và lỗi sai số làm tròn được kiểm soát tốt. 2.2.1. Thuật toán thang lưới bình phương tối thiểu hồi qui Các thuật toán bình phương tối thiểu đệ quy dành cho bộ lọc FIR dạng trực tiếp mô tả trong phần 2.1.4 chỉ đệ quy trong miền thời gian. Độ dài của bộ lọc được cố định. Sự thay đổi độ dài bộ lọc sẽ tạo ra các hệ số bộ lọc mới hoàn toàn khác với các hệ số trước đó. Ngược lại, bộ lọc giàn là hồi quy bậc, vì thế độ dài một số bộ lọc có thể tăng hoặc giảm mà không ảnh hưởng tới hệ số phản xạ của các bộ lọc còn lại. Giả sử ta nhận được tín hiệu và chú ý tới việc ước lượng. Gọi là lỗi ước lượng trước đối với việc ước lượng bậc thứ m (2.2.1) Với vector chứa các hệ số ước lượng trước: (2.2.2) Và vector dữ liệu là: (2.2.3) Các hệ số ước lượng được chọn để tối thiểu hóa lỗi bình phương trọng số thời gian trung bình. (2.2.4) Việc tối thiểu đồng thời chú ý tới dẫn tới biểu thức tuyến tính: (2.2.5) Với là ma trận tương quan tín hiệu: Và được định nghĩa là: (2.2.6) Từ (2.2.5) ta có: (2.2.7) Giá trị nhỏ nhất của được coi như (2.2.8) Với: (2.2.9) (2.2.5) và (2.2.8) có thể ở dạng ma trận: (2.2.10) Khi là vector rỗng thứ nguyên m. Cần chú ý rằng: (2.2.11) Ta cũng tối thiểu hóa lỗi bình phương trọng số thời gian trung bình phía sau: (2.2.12) Với lỗi phía sau là: (2.2.13) Và là vector hệ số ước lượng lùi. Việc tối thiểu hóa dẫn tới biểu thức: (2.2.14) (2.2.15) Với : (2.2.16) Giá trị nhỏ nhất của là (2.2.17) Với là đại lượng vô hướng: (2.2.18) Từ (2.2.14) và (2.2.17) ta có: (2.2.19) Ma trận tự tương quan cũng được ước lượng: (2.2.20) Như vậy ta đã có công thức ước lượng bình phương tối thiểu tiến và lùi của bậc m. Tiếp theo ta sẽ suy ra các biểu thức bậc khác. Ta dùng hai ma trận đảo đồng nhất của ma trận dạng: (2.2.21) (2.2.22) Và: (2.2.23) Với: (2.2.24) Hồi quy nâng bậc: Dùng biểu thức (2.1.22) để tìm ma trận đảo của . Đầu tiên, ta có (2.2.25) Và: (2.2.26) Do vậy: (2.2.27) Tương đương với: Thay n bằng (n-1) vào (2.2.27) và nhân sau kết quả với ta có: (2.2.28) Với là đại lượng vô hướng: (2.2.29) (2.1.28) là sự đệ quy dạng Levinson cho các hệ số bộ lọc ước lượng. Tương tự để nhận được biểu thức cập nhật cho ta dùng ma trận đảo của . Trong trường hợp này ta có: (2.2.30) Và: (2.2.31) Do đó: Hoặc tương đương: (2.2.33) Khi: (2.2.34) Các biểu thức cập nhật cho và cũng có thể tìm được. Từ định nghĩa của ở (2.2.8) ta có: (2.2.35) Thay am+1(n) ở (2.1.8) vào (2.2.35) ta có: (2.2.36) Tương tự ta có: (2.2.37) Bộ lọc giàn đặc trưng bởi cặp biểu thức lỗi tiến và lùi fm(n,n-1) và gm(n,n-1). Ta có (2.2.38) Thay từ (2.2.28) vào (2.2.38) nhận được (2.2.39) Ta định nghĩa: (2.2.40) Vì thế (2.2.39) có thể viết là (2.2.41) Tương tự: (2.2.42) Thay từ (2.2.33) (2.2.43) Tương đương: (2.2.44) Hai biểu thức đệ quy (2.2.41) và (2.2.44) xác định bộ lọc giàn ở hình 2.3. Để thuận tiện ta xác định các hệ số phản xạ cho giàn: (2.2.45) Các điều kiện ban đầu cho việc thay đổi bậc là: (2.2.46) Và (2.2.46) cũng là biểu thức theo thời gian của và . + + Tầng1 Tầng 2 Tầng 3 Tầng M-1 ….. ….. Hình 2.3. Bộ lọc lưới bình phương tối thiểu Hồi quy điều chỉnh theo thời gian Ta cần xác định biểu thức theo thời gian km(n), nó là cần thiết để bộ lọc giàn trở nên thích nghi và đưa ra các biểu thức theo thời gian cho các hệ số bộ lọc. Ta bắt đầu với: (2.2.47) Biểu thức theo thời gian cho Vm+1(n) là: (2.2.48) Biểu thức theo thời gian cho các hệ số ước lượng được xác định như sau. Từ (2.2.6), (2.2.7) và (2.2.8) ta có: (2.2.49) Với Km(n-1) là vector khuếch đại Kalman ở bước lặp thứ n-1. Nhưng từ (2.2.38) ta có: (2.2.50) Bên cạnh đó, dùng (2.2.15), (2.2.16) và (2.2.63) ta được biểu thức theo thời gian cho các hệ số ước lượng lùi ở dạng: (2.2.51) Từ (2.2.48) và (2.2.50) ta có biểu thức theo thời gian của km+1(n) Nhưng: (2.2.53) Và: (2.2.54) Với được định nghĩa ở (2.1.62). (2.2.55) Thay (2.2.53), (2.2.54) và (2.2.55) vào (2.2.52) ta có: (2.2.56) Ta có một biến mới: (2.2.57) có giá trị thực và (2.2.56) giờ được viết: (2.2.58) Điều chỉnh bậc cho : Dù có thể được tính trực tiếp với mỗi giá trị của m và n, nhưng tốt hơn hết là dùng biểu thức theo bậc. Đầu tiên, từ định nghĩa Km(n) ở (2.1.61) ta thấy rằng: (2.2.59) Để có được biểu thức theo thời gian cho , cần có biểu thức theo bậc của vector Kalman Km(n). Nhưng Km+1(n) có thể được viết: (2.2.60) Trong đó: (2.2.61) Do đó biểu thức theo bậc đối với Km(n) ở (2.2.60) được viết: (2.2.62) Từ (2.2.62) và (2.1.59) ta có: (2.2.63) Như vậy ta đã nhận được các biểu thức theo bậc và theo thời gian của giàn bình phương tối thiểu như ở hình 2.3. (2.2.41) và (2.2.44) là các biểu thức cơ bản cho lỗi tiến và lùi, thường được gọi là các phần dư. (2.2.36) và (2.2.37) là lỗi bình phương tối thiểu, (2.2.58) là biểu thức theo thời gian cho Km(n) , (2.2.63) là biểu thức theo bậc cho thông số . Ta có: (2.2.64) Ước lượng quá trình kết hợp: Ta cần tìm ước lượng bình phương tối thiểu cho tín hiệu d(n) từ giàn. Giả sử bộ lọc có m+1 hệ số và các hệ số này được xác định để tối thiểu hóa lỗi bình phương trọng số trung bình: (2.2.65) Khi: (2.2.66) • Ước lượng tuyến tính: (2.2.67) Ước lượng này nhận được từ giàn bằng cách dùng phần dư, và được gọi là ước lượng quá trình kết hợp. Ở (2.1.4) ta đã có các hệ số của bộ lọc thích nghi được tối thiểu hóa bởi biểu thức: (2.2.68) Ta có thỏa mãn biểu thức theo thời gian ở (2.1.76) Từ (2.2.68) và (2.2.27) ta có: (2.2.69) Đại lượng vô hướng: (2.2.70) (2.2.69) có thể viết: (2.2.71) thỏa mãn biểu thức theo thời gian, biểu thức này có được từ biểu thức theo thời gian của và ở (2.2.51) và (2.2. 66). (2.2.72) Nhưng: (2.2.73) Và: (2.2.74) (2.2.75) Thay kết quả ở (2.2.73) qua (2.2.75) vào (2.2.72) ta có: (2.2.76) Như vậy ta đã có biểu thức theo bậc cho . Với , biểu thức theo bậc cho là: (2.2.77) Ước lượng đầu ra d(n) của giàn bình phương tối thiểu là: (2.2.78) Nhưng không được tính toán cụ thể. Bằng cách dùng như ở (2.2.71) ta có: (2.2.79) Nói cách khác, ước lượng đầu ra là tổng trọng số tuyến tính của phần dư tiến . + + + + + + + + + Tầng 1 Tầng 2 Tầng M-1 - - - - - + + + + ... ... Hình 2.4. Bộ lọc thang lưới thích nghi RLS Các thuật toán đệ quy được tổng kết trong bảng 2.5. đó được gọi là dạng ưu tiên của thuật toán giàn hình thang RLS để phân biệt nó với dạng khác của thuật toán, gọi là dạng lùi. Ở dạng lùi này, được thay bởi để ước lượng d(n). Trong bộ cân bằng kênh hoặc khử phản hồi, dạng lùi không sử dụng được vì không thể tính toán để tính d(n). Thuật toán thang lưới RLS cải tiến. Các biểu thức đệ quy ở bảng 2.5 không phải là duy nhất. Có thể xây dựng các biểu thức khác mà không ảnh hưởng tới tính tối ưu của thuật toán. Tuy nhiên, một vài biến thể của thuật toán vượt hẳn về số lượng khi phép toán điểm ấn định được dùng trong thuật toán. Đầu tiên, ta có mối liên hệ giữa phần lỗi dư tiến và lùi. Lỗi tiến: (2.2.80) Lỗi lùi: (2.2.81) Hệ thức giữa (2.2.80) và (2.2.81) là: (2.2.82) Thứ hai, ta tìm được các biểu thức theo thời gian cho lỗi bình phương tối thiểu tiến và lùi. Từ (2.2.8) và (2.2.50) ta có: (2.2.83) Tương tự từ (2.2.17) và (2.2.51) ta có: (2.2.84) Thứ ba, ta có biểu thức theo thời gian cho vector hệ số khuếch đại Kalman, vector này không được dùng trong thuật toán giàn mà sử dụng trong các thuật toán nhanh. Để có được biểu thức này, ta cũng dùng các biểu thức theo thời gian của hệ số ước lượng tiến và lùi cho bởi (2.2.50) và (2.2.51). Ta có: (2.2.85) Khi đặt chứa thành phần đầu tiên của và chứa các thành phần cuối cùng. Từ (2.2.60) ta có biểu thức theo bậc cho là: (2.2.86) Cho (2.2.85) và (2.2.86) bằng nhau ta có: (2.2.87) Và do đó: (2.2.88) Thay (2.2.51) vào (2.2.88) ta có biểu thức theo thời gian cho vector hệ số khuếch đại Kalman: (2.2.89) Đó cũng là biểu thức theo thời gian cho đại lượng vô hướng . Từ (2.2.63) ta có: (2.2.90) Từ (2.2.85) ta có: (2.2.91) Cho (2.2.90) và (2.2.91) bằng nhau ta có biểu thức theo thời gian cho là: (2.2.91) Cuối cùng, ta cần phân biệt giữa những phương pháp khác nhau để cập nhật các hệ số phản xạ cho bộ lọc giàn và hình thang là phương pháp trực tiếp và gián tiếp. Trong phương pháp gián tiếp: 2.2.93) (2.2.94) (2.2.95) Với là theo như (2.2.58), theo như (2.2.76), và theo như (2.2.83) và (2.2.84). Thay từ (2.2.58) vào (2.2.93) và dùng (2.2.84) và biểu thức thứ 8 trong bảng 2.5, ta có Đây là công thức để cập nhật trực tiếp hệ số phản xạ trong giàn. Tương tự, thay (2.2.58) vào (2.2 94) và dùng (2.2.83) và biểu thức thứ 8 trong bảng 2.5 ta có: (2.2.97) Hệ số khuếch đại thang cũng có thể được cập nhật một cách trực tiếp: (2.2.98) Một đặc tính của thuật toán thang lưới là phần dư tiến và lùi sẽ quay trở lại cập nhật các hệ số phản xạ trong tầng giàn và phản hồi lại để cập nhật . Vì vậy, thuật toán giàn hình thang được gọi là dạng phản hồi lỗi. Có thể nhận được dạng tương tự dành cho thuật toán giàn hình thang RLS ưu tiên. Thuật toán RLS nhanh. Có hai phiên bản của RLS nhanh. Thực tế, ta cố định kích thước của giàn và kết hợp ước lượng tiến và lùi ở tầng thứ M-1. Ta nhận được 7 biểu thức đầu. Vấn đề còn lại là xác định biểu thức theo thời gian cho vector hệ số khuếch đại Kalman như ở (2.2.89). Có hai điểm khác biệt cơ bản: thứ nhất, Feast dùng vector hệ số khuếch đại thay thế để thay cho vector hệ số khuếch đại Kalman. Thứ 2, RLS nhanh ước lượng lỗi qua bộ lọc FIR bằng cách dùng vector hệ số , trong khi Feast tính qua cách tính toán vô hướng và chú thích là phần tử cuối cùng của vector hệ số khuếch đại thay thế, , bằng . Chất lượng của RLS nhanh phụ thuộc nhiều vào việc khởi tạo ban đầu. Thuật toán lưới chuẩn hay căn bậc hai. Một dạng khác của thật toán giàn LS được gọi là căn bậc hai hay thuật toán giàn chuẩn hóa. Để có được thuật toán này, đầu tiên ta định nghĩa góc và độ lớn của lỗi LS thông thường. (2.2.99) (2.2.100) Kĩ thuật chuẩn hóa góc xuất phát từ thực tế là là cosine của góc giữa khoảng của vector dữ liệu tại (n-l) và n. Thứ hai, ta xác định hệ số phản xạ chuẩn hóa . (2.2.101) Dễ dàng để chứng minh rằng cả 3 đại lượng đều có giá trị biên độ nhỏ hơn 1. Do thuộc tính này thuật toán giàn LS căn bậc 2 chuẩn hóa là tiện ích đối với việc thực hiện các phép toán điểm ấn định. Thay thế (2.2.99), (2.2.100) và (2.2.101) vào (2.2.58) ta có: (2.2.102) Tương đương: (2.2.103) Từ biểu thức theo thời gian của và ở (2.2.83) và (2.2.84) có thể chỉ ra rằng: (2.2.104) Và: (2.2.105) Sau đó thay (2.2.104), (2.2.105) vào (2.2.103) ta có biểu thức theo thời gian cho . (2.2.106) Để có biểu thức theo bậc cho lỗi chuẩn hóa trước và sau, trước tiên ta viết biểu thức theo bậc cho lỗi tiến: (2.2.107) Và: (2.2.108) Sau đó viết (2.2.107) trong điều kiện của lỗi chuẩn hóa ta có: (2.2.109) Cuối cùng ta có: (2.2.110) Từ biểu thức theo bậc cho ở (2.2.36) có thể chỉ ra rằng (2.2.111) Từ (2.2.63) ta có: (2.2.112) Sau đó bằng cách thay (2.2.111) và (2.2.112) vào (2.2.110) ta có kết quả: (2.2.113) Tương tự ta có biểu thức theo bậc cho lỗi lùi chuẩn hóa là: (2.2.114) Biểu thức (2.2.106), (2.2.113) và (2.2.114) xây dựng nên thuật toán giàn LS chuẩn hóa hay căn bậc 2. Chú ý rằng thuật toán này chỉ chứa 3 biến và chỉ được thực hiện với 3 biểu thức. Do vậy nó có dạng chắc chắn hơn so với các dạng khác của thuật toán giàn LS. Tuy nhiên, nó yêu cầu các phép tính căn bậc 2 các phép tính này mất nhiều thời gian. Vấn đề này thì được giải quyết bằng cách sử dụng bộ xử lí CORDIC, có thể tính căn bậc 2 trong N xung, với N là số bits độ dài từ được tính. 2.2.2. Thuật toán thang lưới Gradient Các thuật toán giàn hình thang được mô tả ở các phần trước thì hoàn phức tạp hơn so với thuật toán LMS nhưng lại có chất lượng tốt hơn. Khi cố gắng đơn giản cách tính toán của dạng này, mà vẫn giữ được tính tối ưu của nó, ta chú ý tới cấu trúc bộ lọc giàn hình thang với số tham số bộ lọc được giảm thiểu. Trong thực tế, cấu trúc bộ lọc giàn hình thang được thể hiện như ở hình 6.4. Mỗi tầng của giàn đặc trưng bởi hệ thức giữa đầu vào và đầu ra. (2.2.115) Với là hệ số phản xạ của tầng thứ m, và là phần dư tiến và lùi. + + + + + + + + + Stage 1 Stage 1 Stage M-1 - - - - - + + + ….. ….. ….. ….. + + ) Hình 2.5 Bộ lọc thang lưới gradient Dạng bộ lọc này thì giống với dạng được suy ra từ thuật toán Levinson-Durbin, trừ việc được phép thay đổi theo thời gian. So sánh với thuật toán giàn RLS, thuật toán này hạn chế hơn trong việc ước lượng hệ số tiến và lùi. Tham số có thể được tối ưu theo chuẩn MSE hoặc theo phương pháp bình phương tối thiểu. Giả sử ta có chuẩn MSE và chọn các tham số để tối thiểu hóa tổng lỗi bình phương trung bình tiến và lùi. Khi ta giảm sự phụ thuộc vào thời gian của : (2.2.116) Chú ý rằng có dạng hệ số tương quan chuẩn hóa. Khi đặc tính thống kê của tín hiệu chưa được biết đến, ta chấp nhận chuẩn bình phương tối thiểu để xác định . Chỉ số đặc trưng được tối thiểu hóa (2.2.117) Ta có: (2.2.118) Trong (2.2.118), tử và mẫu có thể được viết theo thời gian như sau: (2.2.119) Và: (2.2.120) Biểu thức theo thời gian của : (2.2.121) Ta định dạng đầu ra của cấu trúc như ở hình 6.4 như một tổ hợp tuyến tính của các phần dư tiến: (2.2.122) Với là trọng số của phần thang. Giá trị tối ưu của trọng số có thể có được bằng cách tối thiểu MSE giữa tín hiệu mong muốn và ước lượng của nó. Gọi là chênh lệch giữa và ước lượng của nó ở tầng thứ m. Và với ta có: (2.2.123) Lỗi trong (2.2.123) có thể viết ở dạng ma trận: (2.2.124) Với là vector trọng số hình thang và là vector dư tiến. Nếu ta giả thiết việc thống kê tín hiệu là không đổi, ta có thể giảm sự phụ thuộc vào thời gian của vector hệ số và chọn thỏa mãn điều kiện trực giao: (2.2.125) Thay (2.2.124) vào (2.2.125) và dùng phép toán kì vọng ta có: Tương đương: (2.2.126) Một đặc tính quan trọng của phần dư tiến trong bộ lọc giàn được mô tả bởi (2.2.115) ,với k=j ,với k≠j (2.2.127) Do đó ma trận là ma trận chéo và do vậy hệ số khuếch đại thang tối ưu là: (2.2.128) Vấn đề còn lại là điều chỉnh hệ số khuếch đại thang cho thích nghi. Do tối thiểu hóa MSE và , lỗi sẽ trực giao với phần dư trước trong . Điều này đưa ra thuật toán gradient ở dạng: (2.2.129) Với là ước của và có thể tính toán một cách đệ quy. (2.2.130) Tuy nhiên, việc tính toán như ở (2.2.130) có thể không thực hiện được. Do đó phần dư trước và sau có giá trị bình phương trung bình ban đầu, và biến được ước lượng bằng . Và (2.2.129) có thể được viết: (2.2.131) Thuật toán ở (2.2.131) dùng để cập nhật hệ số khuếch đại thang là thuật toán gradient, bộ lọc được gọi là bộ lọc giàn hình thang gradient. Thành phần đóng vai trò như kích thước bước nhảy. 2.2.3. Thuộc tính của thuật toán thang lưới Tốc độ hội tụ: Thuật toán giàn hình thang về cơ bản có tốc độ hội tụ như cấu trúc bội lọc FIR dạng trực tiếp. Tuy thuật toán giàn gradient còn một vài đặc tính của giàn RLS, nhưng lại không tối ưu trong hướng bình phương tối thiểu, do đó nó hội tụ chậm. Yêu cầu tính toán: Thuật toán giàn RLS mô tả trong phần trên có cách tính toán phức tạp tỉ lệ thuận với M. Trái lại, thuật toán RLS căn bậc hai tỉ lệ với . Mặt khác, thuật toán nhanh dạng trực tiếp, thuật toán bắt nguồn từ thuật toán giàn RLS, tỉ lệ với M. Thuộc tính số: Thuật toán giàn RLS và gradient là lớn về số lượng. Đầu tiên, thuật toán giàn là ổn định về số. Ổn định về số có nghĩa là lỗi ước lượng ở đầu ra có được nhờ tính toán thì bị chặn khi tín hiệu lỗi bị chặn được đưa vào đầu vào. Thứ 2, độ chính xác số của phần tối ưu cũng được so sánh trong mối liên hệ với thuật toán FIR dạng trực tiếp và thuật toán LMS. Trong thuật toán giàn gradient, các hệ số phản xạ và hệ số khuếch đại thang cũng được cập nhật trực tiếp. Sự hoạt động: Cấu trúc bộ lọc giàn có tính kết cấu cao và cho phép tính toán nối truyền liên tiếp. Thực tế, thuật toán RLS và giàn gradient thích ứng với sự hoạt động trong VLSI.