Bài giảng Dàn lọc và mã hóa băng con

dàn lỌC VÀ MÃ HÓA BĂNG CON 2.1. Mở đầu Kỹ thuật lọc số nhiều nhịp được ứng dụng trong xử lý tín hiệu, dùng để tăng tốc độ tính toán trong các bộ lọc bằng cách giảm số phép nhân thực hiện trong một giây. Thông thường, trong quá trình xử lý số tín hiệu, bề rộng của dải tần số có thể thay đổi. Các bộ lọc sẽ triệt tiêu các thành phần tần số không mong muốn, bề rộng dải tần của tín hiệu xử lý sẽ giảm đi và chúng ta có thể giảm tần số lấy mẫu cho phù hợp với bề rộng phổ của tín hiệu và như vậy ta sẽ giảm số các phép tính toán trong bộ lọc số. Thành tựu của kỹ thuật lọc số nhiều nhịp thể hiện ở các hệ thống số nhiều nhịp như là tổng hợp các bộ lọc phân chia và các bộ lọc nội suy, các dàn lọc phân tích và tổng hợp, và ứng dụng của chúng là mã hoá băng con. 2.2. Thay đổi nhịp tần số 2.2.1. Định nghĩa hệ thống nhiều nhịp Nếu trong một hệ thống xử lý số tín hiệu, tần số (hay nhịp) lấy mẫu được thay đổi trong quá trình xử lý, thì hệ thống số này được gọi là hệ thống nhiều nhịp. 2.2.2. Định nghĩa phép phân chia Việc giảm tần số (hay nhịp) lấy mẫu từ giá trị Fs về một giá trị F’s (F’s < Fs) được định nghĩa là phép phân chia. Nếu F’s = Fs/M (M > 1 và nguyên dương) thì ta gọi là phép phân chia theo hệ số M; M gọi là hệ số phân chia. 2.2.3. Bộ phân chia Hệ thống chỉ làm nhiệm vụ giảm tần số lấy mẫu được gọi là bộ phân chia Tín hiệu ngõ ra có biên độ ở những thời điểm có chu kỳ T’s.=1/F’s. Hình 2.1: Bộ phân chia Trong miền biến số độc lập n, ta có : y¯M(n) = x (nM) (2.1) Trong miền z, ta có : (2.2) Trong miền tần số, ta có : (2.3) Phép phân chia làm x(n) co hẹp trong miền thời gian (nếu n là thời gian) thì sẽ dẫn đến hiện tượng giãn rộng trong miền tần số. 2.2.4. Định nghĩa phép nội suy Việc tăng tần số (hay nhịp) lấy mẫu từ giá trị Fs về một giá trị F’s (F’s>Fs) được định nghĩa là phép nội suy. Nếu F’s = LFs (L > 1 và nguyên dương) thì ta gọi là phép nội suy theo hệ số L; L gọi là hệ số nội suy. 2.2.5. Bộ nội suy Hệ thống chỉ làm nhiệm vụ tăng tần số lấy mẫu được gọi là bộ nội suy Tín hiệu ngõ ra có biên độ của tín hiệu ngõ vào, ngoài ra, nó còn chèn L-1 mẫu có giá trị bằng 0 giữa hai mẫu từ tín hiệu ngõ vào. Hình 2.2: Bộ nội suy Trong miền biến số độc lập n, ta có với n còn lại y­L[n]= với n = 0, ±L, ±2L,... (2.4) Trong miền z, ta có : Y(z) = X(zL) (2.5) Trong miền tần số, ta có : Y(ejw)=X(ejwL) (2.6) Phép nội suy làm tín hiệu x(n) giãn rộng trong miền thời gian (nếu n là thời gian) thì sẽ dẫn đến hiện tượng co hẹp trong miền tần số. Phép nội suy chèn thêm (L-1) mẫu có giá trị bằng 0 giữa hai mẫu x(n) từ tín hiệu ngõ vào thì trong miền tần số sẽ tạo ra (L-1) bản sao chụp phụ phổ cơ bản, tức là (L-1) bản sao chụp này sẽ chèn vào giữa 2 phổ cơ bản. 2.3. Bộ lọc biến đổi nhịp lấy mẫu 2.3.1. Bộ lọc phân chia Tín hiệu x(n) khi đi qua bộ phân chia ¯M, trong miền tần số sẽ tạo ra (M-1) thành phần hư danh (aliasing), các thành phần hư danh này sẽ gây hiện tượng chồng phổ. Nhưng nếu x(n) có băng tần nằm trong, tức là tần số giới hạn dải chắn thì sẽ không gây hiện tượng chồng phổ. Để làm được điều này, ta đặt trước bộ phân chia¯M một bộ lọc thông thấp có để loại bỏ các thành phần tần số , chỉ giữ lại thành phần và sẽ tránh hiện tượng chồng phổ. y[n] M x[n] h(n) bộ lọc thông thấp h(n): đáp ứng xung của bộ lọc Hình 2.3: Bộ lọc phân chia Trong miền biến số độc lập n: yH¯M(n) =¯M[x(n)*h(n)]= (2.7) Trong miền z: (2.8) Trong miền tần số: (2.9) 2.3.2. Bộ lọc nội suy Phép nội suy chèn thêm (L-1) mẫu có giá trị bằng 0 giữa hai mẫu của tín hiệu vào x(n) trong miền biến số n và tương ứng trong miền tần số sẽ tạo ra (L-1) ảnh phụ của phổ cơ bản sau khi đã co hẹp lại L lần để nhường chỗ cho (L-1) ảnh phụ mà không gây hiện tượng chồng phổ. Như vậy, phép nội suy ­L không làm hư thông tin. Nhưng để nội suy ra các mẫu có biên độ 0, ta phải đặt sau bộ nội suy một bộ lọc có . Trong miền biến số n, bộ lọc này làm nhiệm vụ nội suy các mẫu biên độ 0. Còn trong miền tần số, nó làm nhiệm vụ loại bỏ các ảnh phụ của phổ cơ bản. x[n] y[n] y­L(n) y­LH(n) L h(n) bộ lọc thông thấp có h(n): đáp ứng xung của bộ lọc Hình 2.4: Bộ lọc nội suy Trong miền biến số độc lập n: y­LH(n) = với k=0, ±L, ±2L,... (2.10) Trong miền z: (2.11) Trong miền tần số: y­LH(e =X(e.H(ejw) (2.12) 2.4. Dàn lọc số Dàn lọc số là một tập hợp các bộ lọc số hoặc có lối vào chung hoặc có lối ra tổng. Dàn lọc có chung lối vào và nhiều lối ra thì được gọi là dàn lọc phân tích, còn dàn lọc có nhiều lối vào và chung lối ra thì được gọi là dàn lọc tổng hợp. 2.4.1. Dàn lọc số phân tích Dàn lọc số phân tích là tập hợp các bộ lọc số có đáp ứng tần số là Hk(ejw) được nối với nhau theo kiểu một đầu vào và nhiều đầu ra, cấu trúc của dàn lọc phân tích được minh họa như sau: Ta thấy rằng tín hiệu x[n] đưa vào đầu vào và được phân tích thành M tín hiệu ở đầu ra là xk[n] (0 £k £ M-1), như vậy trong miền tần số mỗi tín hiệu xk[n] sẽ chiếm một dải tần số con trong dải tần của x[n] nên M tín hiệu xk[n] được gọi là tín hiệu dải con (Subband). H0(ejw) H1(ejw) xo[n], x1[n], HM-1(ejw) xM-1[n], x[n] Hình 2.5: Dàn lọc số phân tích X(ejw) X0(ejw) X1(ejw) XM-1(ejw) Còn các bộ lọc số, H0(ejw) sẽ là bộ lọc số thông thấp, H1(ejw) đến HM-2(ejw) sẽ là các bộ lọc thông dải, còn HM-1(ejw) sẽ là bộ lọc thông cao, mà các tần số cắt của các bộ lọc số này sẽ kế tiếp nhau. Như vậy các bộ lọc H0(ejw) , H1(ejw) , ...,HM-1(ejw) được gọi là các bộ lọc phân tích, còn tập hợp các bộ lọc hay {H0(ejw), H1(ejw) , . . .,HM-1(ejw)} được gọi là dàn lọc phân tích. 2.4.2. Dàn lọc số tổng hợp Dàn lọc số tổng hợp là tổng hợp các bộ lọc số có đáp ứng tần số là Gk(ejw) được nối với nhau theo kiểu nhiều đầu vào và một đầu ra, cấu trúc của dàn lọc số tổng hợp được thể hiện trên sau : G0(ejw) G1(ejw) xo[n] x1[n] GM-1(ejw) xM-1[n] + + y[n] G1(ejw) Hình 2.6: Dàn lọc số tổng hợp 2.4.3. Dàn lọc số nhiều nhịp hai kênh và dàn lọc gương cầu phương QMF (Quadrature Mirror Filter Bank) Dàn lọc số nhiều nhịp là sự kết hợp của dàn lọc số phân tích, dàn lọc số tổng hợp với bộ phân chia và bộ nội suy. Với số bộ lọc của băng lọc phân tích và tổng hợp bằng 2 thì ta có dàn lọc số nhiều nhịp hai kênh. Hình 2.7: Băng lọc nhiều nhịp gương cầu phương Trong dàn lọc số phân tích như hình trên, H0(ejω)là bộ lọc số thông thấp, H1(ejω) là bộ lọc số thông cao. Khi thiết kế các bộ lọc này sẽ không thể đạt được lý tưởng, tất nhiên đối với cả các bộ lọc số G0(ejω), G1(ejω) ở dàn lọc tổng hợp nên tín hiệu ra x^(n) của dàn lọc số nhiều nhịp này sẽ khác với tín hiệu vào x(n). Nếu |H0(ejω)|=|H1(ejω)| và nếu chọn tần số cắt cho thì 2 bộ lọc là π/2 thì ta thấy |H0(ejω)|là ảnh của |H1(ejω)| qua gương đặt ở vị trí π/2, và theo thang tần số góc chuẩn hóa bởi tần số lấy mẫu Fs thì π/2 chính là một phần tư tần số lấy mẫu. Băng lọc nhiều nhịp hai kênh với đặc tính như vậy gọi là băng lọc gương cầu phương tức QMF. Nếu dạng của tín hiệu ra x^(n ), giống dạng tín hiệu ngõ vào tức x^(n)=cx(n−n0); c là hằng số thì ta gọi dàn lọc QMF là dàn lọc gương cầu phương khôi phục hoàn hảo PRQMF (Perfect Reconstructure QMF). Trên thực tế, các bộ lọc H0(ejω), H1(ejω) không thể đạt lý tưởng. Ở trường hợp (a) là trường hợp lý tưởng thì sẽ không gây ra sai số hư danh tức sẽ không gây ra hiện tượng chồng phổ đối với tín hiệu ra khỏi bộ phân chia ¯2 là V0(ejω), V1(ejω) và bề rộng của dải thông và dải chắn trong trường hợp lý tưởng đúng bằng π/2 và bề rộng của dải quá độ Dω=0. Còn trường hợp (d) là trường hợp các bộ lọc không lý tưởng nhưng cũng không gây ra chồng phổ đối với V0(ejω), V1(ejω), tức là thành phần hư danh không xuất hiện, nhưng bề rộng của dải thông sẽ nhỏ hơn π/2 và bề rộng dải chắn sẽ lớn hơn π/2, trong trường hợp này, nếu ta chọn bề rộng của dải quá độ rất hẹp thì sẽ gần đạt lý tưởng và không gây chồng phổ, nhưng bộ lọc số sẽ rất đắt tiền. H0(ejw) H1(ejw) 0 p/2 p w a) H0(ejw) H1(ejw) 0 p/2 p w b) H0(ejw) H1(ejw) 0 p/2 p w c) H0(ejw) H1(ejw) 0 p/2 p w d) Hình 2.8: Các trường hợp bộ lọc số a): Trường hợp bộ lọc số lý tưởng b), c), d): các trường hợp bộ lọc số không lý tưởng Khi các bộ lọc số ở trường hợp (b), (c) thì sẽ gây ra hiện tượng chồng phổ, tức là có thành phần hư danh xuất hiện với tín hiệu Vo(ejω) và V1(ejω). Nhưng thành phần hư danh có thể được khử nếu ta thiết kế cẩn thận dàn lọc tổng hợp để bù lại thành phần hư danh do dàn lọc phân tích gây ra. Ở dàn lọc số trên, ta có 2 tín hiệu ra khỏi dàn lọc phân tích là: xk(n) với k = 0 và 1. Trong miền n: xk(n) = hk(n)*x(n) Trong miền z: Để khử được thành phần hư danh X(-z) thì T1(z)=0 tức là: H0(-z)G0(z) = - H1(-z)G1(z) (2.13) Để khử được thành phần hư danh tức là phải thiết kế các bộ lọc số lý tưởng, điều này rất khó khăn mà nếu có tạo được các bộ lọc số gần lý tưởng thì rất tốn kém. Vì vậy, trong kỹ thuật dàn lọc số nhiều nhịp QMF, cho phép có thành phần hư danh nhưng trong dàn lọc phân tích thì H0(z) có thể bù cho H1(z) sau đó chọn dàn lọc tổng hợp sao cho thành phần hư danh của nhánh trên bù cho nhánh dưới. Sau đây là dàn lọc số khôi phục hoàn hảo đơn giản QMF 2 kênh: 2 2 x^[n] x[n] z--1 2 2 z--1 + Hình 2.9: Dàn lọc số khôi phục hoàn hảo đơn giản QMF 2 kênh So sánh với dàn lọc số nhiều nhịp QMF 2 kênh thì thấy: H0(z) =G1(z)=1; G0(z)= H1(z)=z-1 (2.14) Và thành phần hư danh: T1(z)==0 (2.15) Và thành phần: T0(z) = = z-1 (2.16) Do đó : X^(z)= T0(z).X(z) = z-1. X(z) (2.17) Vậy x’[n]=x(n-1) (2.18) 2.4.4. Dàn lọc số nhiều nhịp M kênh xM-1(n) y0(n) x(n) x^(n) yM-1(n) y’M-1(n) y’1(n) y’0(n) v0(n) vM-1(n) v1(n) H0(z) ¯M ­M G0(z) H1(z) ¯M G1(z) HM-1(z) ¯M ­M GM-1(z) + + x0(n) x1(n) y1(n) ­M Sơ đồ tổng quát của dàn lọc số nhiều nhịp M kênh ( hay dàn lọc số QMF M kênh): Hình2.10: Dàn lọc số nhiều nhịp M kênh Trong miền n: xk(n)=hk(n)*x(n) (2.19) Trong miền z: Và đây là dàn lọc số khôi phục hoàn hảo đơn giản M kênh : M x[n] M z--1 M M z--1 + z--1 z--1 M + M x^[n] Hình 2.11: Dàn lọc số khôi phục hoàn hảo đơn giản M kênh Các bộ lọc phân tích và tổng hợp sẽ có dạng sau đây: Hk(z) = z-k (2.20) Gk(z) = z-(M-1-k) với 0 £ k £ M-1 (2.21) Và X^(z) = z-(m-1)X(z) (2.22) x(n) = x[n-(M-1)] (2.23) 2.5. Mã hoá băng con Một trong những ứng dụng quan trọng của dàn lọc số nhiều nhịp là dùng mã hoá và giải mã dải con. 2.5.1. Nguyên tắc của mã hoá băng con Nguyên tắc cơ bản trong quá trình mã hoá băng con là phân chia tín hiệu thành nhiều dải tần số thông qua các bộ lọc thông thấp, thông dải và thông cao. Các dải tần này gọi là các băng con. Sau đó, các băng con này sẽ được lượng tử và mã hoá độc lập nhau, tuỳ thuộc vào tính chất thống kê và mật độ năng lượng của từng dải mà số bit mã hoá khác nhau. Yêu cầu của kỹ thuật này là làm thế nào các băng con không bị chồng chéo lên nhau. Để có thể phân ly tín hiệu ở bộ mã hoá (encoder) thành các băng con, ảnh được cho qua một dàn lọc (filter bank) gọi là dàn lọc phân tích và mỗi đầu ra của dàn lọc, băng con được lấy mẫu xuống hệ số 2. Các đầu ra băng con tần số được lẫy mẫu xuống sẽ lần lượt được: lượng tử hoá độc lập bằng các bộ lọc vô hướng khác nhau, mã hoá entropy, lưu trữ và truyền đi. Ở phía bộ giải mã (decoder), quá trình được thực hiện ngược lại: giải lượng tử băng con tần số, lấy mẫu lên với hệ số 2, cho đi qua bank lọc băng con tổng hợp rồi cộng tất cả các đầu ra của bộ lọc để khôi phục lại tín hiệu. Hình 2.12: Sơ đồ khối hệ thống mã hóa băng con Mã hoá băng con rất thuận tiện cho việc nén tín hiệu tiếng nói bởi vì đối với tín hiệu tiếng nói thông thường năng lượng của phổ tín hiệu phân bố không đều, năng lượng phổ tiếng nói chủ yếu tập trung ở miền tần số thấp, còn miền tần số cao năng lượng của phổ tiếng nói rất nhỏ. Còn đối với tín hiệu hình ảnh, mã hoá băng con cũng rất hiệu quả cho việc nén tín hiệu hình ảnh bởi vì phổ năng lượng của tín hiệu hình ảnh cũng phân bố không đều nhau vì vậy mỗi dải phổ sẽ có năng lượng khác nhau, dải nào có năng lượng lớn sẽ được mã hoá với số bit lớn còn dải nào có năng lượng nhỏ sẽ được mã hoá với số bit ít hơn. Nói chung các tín hiệu trong thực tế có phân bố năng lượng là không đều nhau, vì vậy mã hoá băng con là rất thuận lợi cho việc nén tín hiệu. 2.5.1.1. Cấu trúc dạng cây đơn phân giải (uniform resolution) Vì năng lượng của phổ tín hiệu thường phân bố rất không đồng đều trên toàn bộ dải tần số, vậy để mã hoá băng con hiệu quả cao chúng ta sẽ mã hoá làm nhiều tầng, tức là tầng thứ nhất chia thành 2 dải con đều nhau (mỗi dải có bề rộng là p/2) đến tầng thứ 2 ta lại phân 2 dải con của tầng thứ nhất thành các dải con có bề rộng bằng bằng nửa của tầng thứ nhất (mỗi dải có bề rộng là p/4) và cứ tiếp tục như vậy chúng ta sẽ phân dải phổ của tín hiệu vào làm rất nhiều các dải và sau khi ra khỏi dàn lọc phân tích bề rộng phổ của mỗi tín hiệu dải con là bằng nhau nên ta gọi là phân giải. H01(z) 2 2 2 H11(z) 2 2 2 x(n) Tầng 1 Tầng 2 Hình 2.13 : Cấu trúc dạng cây đơn phân giải của dàn lọc phân tích 4 kênh 0 p/4 w 1 H01(ejw) H11(ejw) p/2 3p/2 p Hình 2.14 : Đồ thị đáp ứng tần số của các bộ lọc số có trong dàn lọc số 4 kênh 2.5.1.2. Cấu trúc dạng cây đa phân giải (multiresolution): Cấu trúc này cho ta lượng bit ngõ ra tối ưu và phù thuộc vào sự phân H01(z) 2 2 2 H11(z) 2 x(n) Tầng 1 Tầng 2 Hình 2.15: Cấu trúc dạng cây đa phân giải dàn lọc phân tích 2 tầng bố phổ của tín hiệu. 0 p/4 w 1 H01(ejw) H11(ejw) p/2 p Hình 2.16: Đồ thị đáp ứng tần số của các bộ lọc số có trong dàn lọc dàn lọc phân tích 2 tầng 2.5.2. Lượng tử hóa: 2.5.2.1 Lượng tử hóa vô hướng: Lượng tử hóa là sự rời rạc hóa tín hiệu về mặt biên độ. Lượng tử hóa xung PAM là sự thay thế các mẫu đã được lấy từ tín hiệu tương tự bằng một tập hợp hữu hạn các mức biên độ đã được ấn định bằng bộ lượng tử hóa . Trong bộ lượng tử hóa , có N mức lượng tử khác nhau. Mẫu có biên độ rơi vào vùng nào của mức lượng tử hóa thì sẽ được gán mức và mã hóa theo vùng đó. Sự thay thế đó chính xác đến 1 /2 mức lượng tử. Lượng sai số đó gọi là sai số lượng tử hóa hay tạp âm lượng tử hóa. Giả sử tín hiệu biến thiên từ -xmax đến +xmax, chia đoạn (0, xmax ) ra N khoảng, mỗi khoảng là Dx. Dx :bước lượng tử hóa . Nếu Dx=const Þ lượng tử hóa tuyến tính (đều). Nếu Dx ¹ const Þ lượng tử hóa phi tuyến (không đều ). A. Lượng tử hóa tuyến tính : Đây là quá trình lượng tử hóa mà thỏa mãn điều kiện trên. Lúc này, sai số lượng tử hóa được xét đến như sau : x= x(t) - xq(t) Ở một mức lượng tử K bất kỳ : Hàm mật độ xác xuất sai số lượng tử hóa w (x) với giả sử w (x) là phân bố đều: với với Công suất sai số lượng tử hóa : Công suất sai số lượng tử hóa tỷ lệ với Dx2. Nếu Dx lớn thì Pq lớn. Muốn giảm Pq thì giảm Dx ÞN tăng (số mức lượng tử hóa tăng) Þ n tăng (n: số bit cần thiết để mã hóa 1 mẫu ) Þ thời gian truyền tin tăng Þ giá thành tăng. Quá trình lượng tử hóa được đánh giá thông qua tỷ số S/N : Tỷ số S/N không đồng đều trong toàn bộ dải động của tín hiệu (nếu S/N < 30dB thì không thể tách tín hiệu ra khỏi nhiễu). Để đạt được S/N không đổi thì Dx phải biến thiên và tỷ lệ với x theo công thức : Dx= Cx. B. Lượng tử hóa phi tuyến : Đối với lượng tử hóa phi tuyến thì Dx= Cx. Thực tế, người ta không tiến hành lượng tử hóa phi tuyến trực tiếp đối với tín hiệu x mà người ta tìm cách chuyển đổi xÞy=f(x), với y thì có thể tiến hành lượng tử hóa tuyến tính, tức Dy=const. y* x* DAC tuyến tính Giãn x y Nén ADC tuyến tính Hình 2.17: Mô hình về sự nén -giãn tín hiệu trong lượng tử hóa phi tuyến Tìm đặc tuyến nén - giãn : + Giả sử tin x biến thiên từ -1 đến +1. + Giả sử tin y biến thiên từ -1 đến +1. + Chia (0,1) ra N khoảng bằng nhau . Có 2 luật nén - giãn logarit được ITU-T khuyến nghị sử dụng: luật A dùng ở châu Âu, luật m được dùng ở Bắc Mỹ & Nhật Bản. Luật A (Châu Âu) : với (2.24) với m=100 hay 255 (2.25) Luật m (Mỹ & Nhật): Để tín hiệu sau khi nén giãn được trung thực thì tổng đường nén & đường giãn phải là một 1 đường thẳng. Đường này không thể thực hiện được trong thực tế. Vì vậy, trong thực tế, người ta dùng phương pháp xấp xỉ từng đoạn để thực hiện việc nén -giãn. 1 1/2 1/8 1 y 7/8 6/8 5/8 4/8 3/8 2/8 1/8 x Hình 2.18: Phương pháp xấp xỉ từng đoạn trong việc nén -giãn Luật A (Châu Âu) : Khoảng (-1,+1) được chia làm 13 đoạn : Phần + : 6 đoạn : 2/8 đến +1. Phần - : 6 đoạn : -2/8 đến -1. 1 đoạn giữa từ -2/8 đến +2/8. Luật m (Mỹ &Nhật) : Khoảng (-1,+1) được chia làm 15 đoạn : Phần + : 7 đoạn : +1/8 đến 1. Phần - :7 đoạn : -1/8 đến -1. 1 đoạn giữa từ -1/8 đến +1/8. Trong 1 đoạn thì hệ số góc không đổi; giữa 2 đoạn kế tiếp nhau thì hệ số góc tga thay đổi 2 lần. Vậy sai số tuyệt đối giữa 2 đoạn kề nhau : 20lg2 = 6dB (có thể chấp nhận được). C. Mã hóa : Mã hóa là quá trình các mẫu đã được lượng tử hóa được chuyển đồi thành mã nhị phân. Có 2 loại mã hóa ứng với 2 phương pháp lượng tử hóa: mã hóa tuyến tính và mã hóa phi tuyến. Mã hóa tuyến tính : Khi lượng tử hóa tuyến tính thì ứng với mã hóa tuyến tính. Với số mức lượng tử hóa là N thì số bit cần thiết để mã hóa1 mẫu là n ³log2N. Hai phương pháp thường dùng trong mã hóa tuyến tính là : Phương pháp mã hóa song song : cho n bit ra đồng thời; phương pháp này nhanh nhưng bù lại số bộ so sánh tăng. Phương pháp mã hóa nối tiếp : cho n bit ra lần lượt từ cao đến thấp; phương pháp này cho tốc độ truy xuất chậm tuy nhiên số bộ so sánh giảm. Mã hóa phi tuyến : Mã hóa phi tuyến tín hiệu thoại thường yêu cầu lấy độ dài từ mã là 8 bit và được phân đoạn như sau : B7 B6 B5 B4 B3 B2 B1 B0 Trong đó: B7 là bit dấu; 1 đoạn gồm (B6, B5, B4); 1 đoạn gồm (B3, B2, B1, B0). Xét phần + dạng sóng tín hiệu biến thiên từ 0 đến 1. Chia đoạn (0,1) ra làm 8 đoạn bằng nhau, mỗi đoạn được đặc trưng bằng 1 từ mã 3 bit (B6, B5, B4). Tiếp theo, chia mỗi đoạn 1/8 ra làm 16 đoạn bằng nhau. Mỗi đoạn nhỏ được đặc trưng bằng 1 từ mã 4 bit (B3, B2, B1, B0). Vậy trong phần + của tín hiệu có 8.16 = 128 mức lượng tử hóa. Tương tự, trong phần - của tín hiệu có 128 mức lượng tử. Vậy toàn dạng sóng tín hiệu có 128.2 = 256 mức =28. Do vậy độ dài từ mã là 8 bit. Nếu lượng tử hóa tuyến tính thì: + trong phần + có 2048 mức lượng tử hóa. + trong phần - có 2048 mức lượng tử hóa. Tổng cộng có 4096 mức = 212 >> độ dài từ mã là 12 bit. Tóm lại, mã hóa phi tuyến có 2 ưu điểm : S/N =const; độ dài từ mã giảm Þ giảm thời gian truyền tín hiệu. 2.5.2.2 Lượng tử hóa vector Lượng tử hóa vectơ là lượng tử hóa của một khối các mẫu tín hiệu hay một khối các thông số tín hiệu. Lượng tử hóa vectơ được dùng rộng rãi trong mã hóa tiếng nói cho hệ thống tế bào số. Lượng tử hóa vectơ ít bị méo và cho tốc độ bít thấp hơn lượng tử hóa vô hướng. Nếu ta có một vectơ n chiều X={ x1 x2 .....xn} với xk (1£k£ n) là thành phần có biên độ liên tục và thực được mô tả bởi hàm mật độ xác suất p(x1, x2 ,.....xn). Vectơ X được lượng tử hóa thành vectơ n chiều X’ với thành phần x’k (1£ k £ n). Ta nói X’ là đầu ra của bộ lượng tử hóa vectơ với vectơ đầu vào là X. Lúc đó, sẽ sinh ra nhiễu lượng tử hóa d(X, X’). Méo trung bình trên tập hợp vectơ đầu vào X là: (2.31) Với P(XÎCk) là xác xuất để vectơ X rơi vào tế bào Ck và p(X) là hàm mật độ xác suất của n biến ngẫu nhiên. Trong trường hợp lượng tử hóa vô hướng, ta có thể giảm D bằng cách chọn tế bào {Ck, 1£ k £ L} cho hàm mật độ xác suất p(X). 2.5.3. Mã hóa Entropy 2.5.3.1. Mã hóa tiền tố Mã chiều dài thay đổi là mã được mong muốn cho việc nén dữ liệu vì chúng ta có thể đạt được việc tiết kiệm toàn cục bằng cách gán những từ mã ngắn cho những kí tự xuất hiện thường xuyên và những từ mã dài hơn cho những kí tự xuất hiện ít hơn. Tuy nhiên, một mã chiều dài thay đổi sẽ trở nên vô giá trị nếu như không thể nhận ra một cách duy nhất những từ mã của mã này từ bản tin đã được mã hoá. Ví dụ : Cho mã chiều dài thay đổi (0, 10, 010, 101) của bảng kí tự (A, B, C, D) . Một đoạn tin là ‘0100101010’ có thể được giải mã nhiều hơn một cách. Ví dụ ‘0100101010’ có thể dịch là ‘ 0 10 010 101 0’ là ‘ ABCDA’ hoặc ‘010 0 101 010 ‘ là CADC. Khi đó sẽ không nhận được chính xác dữ liệu nguồn. Một mã được coi là có khả năng giải mã duy nhất nếu có duy nhất một cách có thể để giải mã bản tin mã hoá. Một giải pháp dường như khả quan cho những trường hợp mã không phải là mã có khả năng giải mã duy nhất đó là thêm vào những kí tự phân cách mở rộng trong giai đoạn mã hoá. Ví dụ, chúng ta sử dụng kí tự ‘/’, sau đó mã hoá chuối kí tự ABCDA là ‘0/10/010/101/0’. Tuy nhiên, phương pháp này phải trả giá quá đắt bởi vì kí tự mở rộng ‘/’ phải được chèn vào cho mỗi từ mã. Mã lý tưởng trong trường hợp này là một mã mà không chỉ có chiều dài thay đổi mà còn có đặc tính tự phân cách. Một loại được gọi là mã tiền tố (prefix code) là mã như thế. “Tiền tố” là một vài bit đầu tiên của một từ mã. Khi hai từ mã có chiều dài khác nhau, có thể từ mã ngắn hơn sẽ giống hệt với vài bít đầu tiên của từ mã dài hơn. Một mã tiền tố (prefix code) là mã trong đó không từ mã nào là tiền tố của từ mã nào, hay cũng không thể một từ mã mà xuất phát từ một từ mã khác bằng cách cộng thêm vào sau vài bit từ mã ngắn hơn. Hình 2.19 : A Prefix code Những mã tiền tố chỉ là một tập con của mã khả năng giải mã duy nhất. Nên nếu một mã không phải là mã tiền tố thì chúng ta không thể khẳng định rằng từ mã này không thể giải mã một cách duy nhất. Ví dụ : mã (0, 01, 011, 0111) cho (A, B, C, D). Rõ ràng đây không phải là mã tiền tố vì từ mã này là tiền tố của từ mã kia. Song nếu nhận được một bản tin mã hoá 01011010111, thì chỉ có một cách giải mã duy nhất là 01 011 01 0111 đó là BCBD. Một số mã có khả năng giải mã duy nhất nhưng yêu cầu phải xem xét ngay từ đầu trong suốt quá trình giải mã. Điều này khiến chúng không hiệu quả bằng mã tiền tố (prefix codes). Vấn đề ta quan tâm ở đây là tìm ra các mã có thể giải đoán duy nhất với chiều dài nhỏ nhất (để cho tốc độ lớn nhất trên kênh truyền). 2.5.3.2. Entropy Những bản tin khác nhau được mã hóa thành những từ có chiều dài khác nhau. Khi nó đến chiều dài của một mã, ta phải chỉ ra giá trị trung bình của các từ mã. Giá trị trung bình này được tính bằng cách lấy xác suất của mỗi bản tin. Một định lý căn bản đã tồn tại trong thuyết mã hóa không có nhiễu. Định lý được phát biểu: Đối với các chữ cái được mã hóa bằng số nhị phân, chiều dài từ mã trung bình lờn hơn hoặc bằng với Entropy. Entropy được định nghĩa : H(S) = (2.26) Với pi là xác suất của bản tin thứ i. Log2(1\P(Xi)): là nội dung của thông tin và đơn vị của nó là bit Entropy là lượng tin trung bình của bản tin. Nếu gọi chiều dài từ trung bình là n thì: n ≥ H. 2.5.3.3. Kỹ thuật mã hóa Huffman Mã hoá Entropy sử dụng kỹ thuật mã hoá Huffman với các bảng mã hoá gồm bảng phân loại và bảng Huffman dựa vào đặc tính thống kê của tín hiệu. Đây là mã prefix và là mã tối ưu đối với mô hình đã cho (tập hợp xác suất). Nguyên tắc: Dựa vào mô hình thống kê của dữ liệu gốc, ký tự có xác suất càng cao thì mã hoá với từ mã càng ngắn. Thuật toán: - Tính tần suất xuất hiện trong dữ liệu gốc, sắp xếp theo thứ tự giảm dần. - Xét từ dưới lên trên, ghép hai ký tự có xác suất bé nhất thành 1 (phần tử này có tần suất bằng tổng 2 tần suất thành phần). Quá trình này lặp lại cho đến khi bảng chỉ còn 1 phần tử. Quá trình này gọi là cây Hufman ( các bit dữ liệu/ký tự là nút lá). Sau khi tạo xong cây, tiến hành gán mã cho các nút lá. Mã hóa: + Mỗi lần xuống bên phải, ta thêm 1 bit “1” vào từ mã. + Mỗi lần xuống bên trái, ta thêm 1 bit “0” vào từ mã. Ví dụ: Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29 A B C D E 0.10 0.15 0.30 0.16 0.29 Quá trình xây dựng cây Huffman diễn ra như sau : A B C D E 010 011 11 00 10 èNhư vậy bộ mã tối ưu tương ứng là :