Các kiến thức cơ bản về âm thanh

ng ở điều kiện bình thường. Tuy nhiên, cũng cuộc trò chuyện đó nằm trong vùng lân cận của những tiếng ồn lớn, như là tiếng ồn do một chiếc phản lực bay ngang bên trên, là hoàn toàn không thể nghe được do lúc này ngưỡng nghe đã bị sai lệch. Khi chiếc phản lục đã đi rồi thì ngưỡng nghe trở lại bình thường. Aâm thanh mà ta không thể nghe được do sự thích nghi động của ngưỡng nghe gọi là bị “che” (masked). c. Che tần số (Frequency Masking) Thí nghiệm: · Phát ra 1 âm có tần số 1 kHz với mức to cố định là 60dB, gọi là “âm che” (masking tone). Phát ra một âm khác (gọi là test tone) ở mức tần số khác (ví dụ 1.1kHz), và tăng mức to của âm này cho đến khi có thể nghe được nó (phân biệt được âm 1.1 kHz và âm che 1kHz). · Làm lại thí nghiệm với các âm thử (test tone) và vẽ ra một ngưỡng mà tại đó các âm thử bắt đầu có thể phân biệt được: Hình 4.3 · Làm thí nghiệm với các “masking tones” có các tần số khác nhau, ta có được hình vẽ: Hình 4.4 d. Che nhất thời. (che thời gian) · Nếu ta nghe một âm thanh lớn, rồi ngưng nó lại, mãi một lúc sau ta mới có thể nghe được một âm lân cận nhỏ hơn . · Thí nghiệm: phát ra một âm che “masking tone” có tần số 1kHz ở mức 60dB, kèm một âm thử (test tone) 1.1kHz ở mức 40dB. Ta không nghe được âm thử này (nó đã bị che). Dừng âm che lại, đợi một lúc (delay time) ta dừng tiếp âm thử (test tone). Điều chỉnh thời gian delay để cho ta vừa có thể nghe được âm chủ (ví dụ khoảng 5ms). Lặp lại thí nghiệm cho các mức to khác nhau của âm thử, ta vẽ được đồ thị sau: Hình 4.5 · Làm thí nghiệm tương tự với các tần số khác nhau cho âm thử. Hiệu qủa che được vẽ như hình. Hình 4.6 5. Hoạt động: · Khi đưa ra phương pháp mã hóa âm thanh, nền tảng vẫn là yếu tố “hệ thống nghe” của con người. Thật không may đó không phải 1 thiết bị hoàn hảo để nhận biết âm thanh nhưng là thiết bị duy nhất chúng ta có được. Nhưng chúng ta có thể chuyển những khuyết điểm của nó thành ưu điểm : đó là đặc tính phi tuyến của ngưỡng nghe và khả năng thích hợp của nó. · MPEG hoạt động dựa trên hệ thống nghe của con người, đó là cảm giác về âm mang đặc tính sinh lý và tâm lý. · Aâm thanh CD ghi lại tất cả tần số, kể cả những tần số bị ‘che’. · Aâm thanh MPEG chỉ ghi lại những tần số mà tai người có thể nghe. · Như vậy, MPEG sẽ bỏ qua những thông tin không quan trọng. Dựa trên nghiên cứu về nhận thức âm thanh của con người, bộ mã hóa sẽ quyết định những thông tin nào là căn bản và những thông tin nào có thể bỏ qua. · Hiệu qủa này là bao quát nhưng đặc biệt quan trọng trong âm nhạc. Nếu trong một dàn nhạc có một nhạc cụ chơi cực mạnh, làm át tiếng của các nhạc cụ khác ta không thể nghe được. Nhưng máy thâu âm vẫn ghi lại đầy đủ tất cả tần số của tất cả nhạc cụ, nghĩa là thiết bị thâu âm hoàn toàn không có khả năng thích nghi động như con người. Nhưng khi phát lại, ta vẫn không nghe được âm thanh của những nhạc cụ bị át. Vì vậy việc lưu trữ/ghi lại những tần số này là thừa, làm chiếm dung lượng khá nhiều. Cách ghi âm tuyến tính trên đĩa CD là hoàn toàn không hiệu qủa về khía cạnh này. Do đó thay vì phải ghi lại thông tin của những âm không nghe được, ta sẽ dành chỗ cho các âm có thể nghe được. Theo cách này, dung lượng của thiết bị ghi âm cần thiết có thể xem như giảm đi mà không làm giảm chất lượng âm thanh. · Trước khi chúng ta nghe được điều gì, thông tin sẽ được phân tích bởi bộ não của chúng ta. Não bộ sẽ dịch âm thanh và lọc bỏ những thông tin không cần thiết. Kỹ thuật âm thanh MPEG làm việc này thay thế cho não bộ. Như vậy, những thông tin lẽ ra phải được lọc bởi não bộ bây giờ không còn cần phải lưu trữ chiếm giữ không gian đĩa nữa. II. CÁC KHÁI NIỆM CƠ BẢN VỀ MPEG. 1. Lược đồ mã hóa Perceptual Subband. Bộ mã hóa âm thanh theo “perceptual subband” phân tích liên tục các tín hiệu vào và xác định ra đường cong che (masking curve), đó là mức ngưỡng mà những âm thanh ở dưới nó không thể nghe được bởi hệ thống nghe của con người. Hình 4.7 Tín hiệu vào được chia thành 1 số dải tần số, gọi là “subband”. Mỗi tín hiệu “subband” được lượng tử hóa theo cách mà sự lượng tử hóa tiếng ồn được bắt đầu bởi việc mã hóa sẽ không vượt qúa đường cong che của subband đó. Sự lượng tử hóa phổ tiếng ồn vì thế thích nghi động với phổ của tín hiệu.Thông tin trên bộ số hóa được dùng trong mỗi subband được truyền dọc theo các mẫu subband được mã hóa. Bộ giải mã sẽ giải mã dòng bit (bitstream) mà không cần phải biết cách mà bộ mã hóa xác định những thông tin này. Điều này cho phép bộ mã hóa hoạt động với những mức độ khác nhau về chất lượng và độ phức tạp, và cũng cho phép sự phát triển trong tương lai của bộ mã hóa. 2. Giải thích về hiệu qủa che (masking effect). a. Nén âm thanh MPEG. MPEG có thể nén 1 dòng bit 32 kbit/s đến 384 kbit/s. Một dòng bit âm thanh PCM thô thì khoảng 705 kbit/s, do đó tỉ số nén tối đa có thể là 22. Tỉ số nén bình thường là 1:6 hay 1:7. 96 kbit/s là xem như trong suốt cho hầu hết các mục đích thực tế. Có nghĩa rằng ta không cần phải lưu tâm đến bất kỳ sự khác biệt nào giữa tín hiệu gốc và tín hiệu nén đối với nhạc pop hay nhạc rock’n roll. Đối với một số ứng dụng khác như là hòa tấu piano, tốc độ bit có thể lên tới 128 kbit/s. Để đạt được tỉ số nén này, đối với âm thanh, về cơ bản ta có hai chọn lựa: hoặc giảm số lần lấy mẫu, hoặc giảm số bit để lượng tử hoá. Con người có thể nghe âm thanh với tần số từ 20 Hz đến 20 kHz. Theo thuyết của Nyquist, ta phải lấy mẫu âm thanh ở tần số tối thiểu là hai lần tần số cao nhất mà ta muốn phát lại. Tần số lấy mẫu 44,1 kHz là thích hợp. Vấn đề còn lại là phải chọn số bit cho một mẫu mã hóa là bao nhiêu. Thông thường là 16 bit. Lý do để chọn con số 16 bit bắt nguồn từ tỉ số tín hiệu và nhiễu (s/n). Nhiễu nói ở đây sinh ra do qúa trình số hóa. Cứ mỗi bit thêm vào, ta có tỉ số s/n tốt hơn 6dB (đối với tai người, 6 dB tương ứng với mức to gấp đôi). Aâm thanh CD đạt tới khoảng 90 dB s/n. Mức này phù hợp với phạm vi động của tai người còn tốt. Nghĩa là ta không thể nghe được bất kỳ nhiễu nào đến từ bản thân hệ thống. Điều gì xảy ra nếu ta lấy mẫu với 8 bit? Ta sẽ nghe thấy rất nhiều tiếng sôi trong bản ghi. Dễ dàng nghe thấy nhiễu trong khoảng nghỉ của bản nhạc hoặc giữa các từ nếu ta ghi âm một giọng nói. b. Hiệu qủa che. Giả sử có một âm mạnh với tần số 1000Hz, và một âm kèm theo có tần số 1100Hz nhưng với cường độ âm nhỏ hơn 18dB. Ta sẽ không thể nghe thấy âm này vì nó đã bị che hoàn toàn bởi âm chủ 1000Hz. Nói một cách khác, một âm thanh yếu gần một âm thanh mạnh sẽ bị che. Nếu có một âm thanh khác tần số 2000Hz cũng có mức to thấp hơn âm 1000Hz là 18dB thì ta sẽ nghe được âm này. Để không nghe được âm này ta phải giảm mức to của âm này xuống còn thấp hơn 45dB so với âm chủ 1000Hz. Hiệu qủa che có ý nghĩa rằng ta có thể gia tăng mức ồn nền xung quanh một âm mạnh mà vẫn không nghe được tiếng ồn vì chúng sẽ bị che hoàn toàn. Tăng mức ồn nền còn có nghĩa là dùng ít bit để số hóa. Và điều này cũng giống như là ta đã nén âm thanh vậy. Bây giờ hãy xem bộ mã hoá âm thanh MPEG hoạt động như thế nào. Bộ mã hóa chia phổ tần số (20Hz đến 20kHz) thành 32 dải nhỏ (sub-band). Mỗi sub-band giữ 1 phần nhỏ của phổ. Trong vùng trên của sub-band 8 ta phát một âm có tần số 1000Hz với mức to 60dB. Bộ mã hóa sẽ tính toán hiệu qủa che của âm này và nhận ra rằng có một ngưỡng che cho toàn bộ sub-band thứ 8 (tất cả những âm có cùng tần số). Ngưỡng che này thấp hơn âm phát ra 35 dB. Tỉ số s/n có thể chấp nhận được là 60 - 35 = 25 dB, tương đương với 4 bit. Ngoài ra nó còn ảnh hưởng trên các sub-band 9-13 và 5-7 với hiệu qủa che giảm dần từ sub-band 8. Hơn nữa, bộ mã hóa cũng xem xét mức độ nhạy cảm của tai đối với các tần số khác nhau. Tai người ít nhạy cảm với các tần số cao và thấp. Nó nhạy cảm nhất đối với tần số 2-4 kHz, cùng dải tần số với tiếng nói con người. Các sub-band nên phù hợp với tai người., nghĩa là mỗi sub-band cần có các tần số có cùng các tính chất âm học tâm lý. Trong MPEG layerII, mỗi sub-band có độ rộng 625Hz, do đó cần phải có những bộ lọc băng thông phức tạp. Để các bộ lọc đỡ phức tạp, người ta thêm FFT (Fast Fourie Transform) vào song song với bộ lọc và sử dụng các thành phần phổ từ FFT như là các thông tin thêm vào bộ mã hóa. Bằng cách này ta sẽ lấy mật độ bit cao hơn đối với các tần số thấp mà tai người nhạy cảm hơn. Còn nhiều vấn đề cần phải bàn tới. Chúng ta chỉ mới giải thích sự che đồng bộ, hiệu qủa che còn xảy ra trước và sau một âm mạnh. 3. Các lớp của âm thanh MPEG. Có nhiều sự nhầm lẫn về lớp âm thanh MPEG. Tất cả các lớp đều dựa trên cùng một lược đồ mã hóa (mã hóa theo nhận thức). Mức độ phức tạp của bộ mã hóa và giảûi mã tuỳ thuộc vào mỗi lớp. Sau đây là hình ảnh cho thấy tỉ số nén mà ta cần phải đạt tới 100% chất lượng CD với các bộ mã hóa và giải mã khác nhau. Hình 4.8 Sau đây là chi tiết về các lớp. a. Lớp I (Layer I): Đây là lớp đơn giản nhất phù hợp cho ứng dụng của người dùng. Mô hình âm học tâm lý của lớp này chỉ sử dụng các tần số che. Điều này có nghĩa rằng nó sẽ bỏ qua các tần số bị khuất sau các tần số khác. Phạm vi tốc độ bit từ 32 kbit/s (mono) đến 448 kbit/s (stereo). Tùy thuộc vào mức độ phức tạp của bộ mã hóa, một âm thanh chất lượng cao (gần với âm thanh CD) yêu cầu tốc độ bit khoảng 256 - 384 kb/s trên một chương trình stereo. Không nên mã hóa với mức nén cao hơn 384 kb/s. Độ phức tạp của bộ giải mã thấp, độ phức tạp của bộ mã hóa cao hơn 1.5 - 3 lần. Lớp I được dùng nhiều trong DDC và Solid State Audio. b. Lớp II (Layer II): Lớp II đề nghị mức độ nén cao hơn lớp I và mức độ lọc sâu hơn. Nó có những ứng dụng số cho cả âm thanh chuyên nghiệp và tài tử, như qua đài phát thanh, TiVi...Phạm vi tốc độ bit từ 32 - 192 kb/s cho âm thanh mono, và từ 64 - 384 kb/s cho âm thanh stereo. Tùy thuộc vào mức độ phức tạp của bộ mã hóa, một âm thanh chất lượng cao (gần với âm thanh CD) yêu cầu tốc độ bit khoảng 256 - 384 kb/s trên một chương trình stereo. Mức độ phức tạp của bộ giải mã 25% cao hơn so với lớp I, và bộ mã hóa có mức phức tạp cao hơn 2 - 4 lần. c. Lớp III (Layer III). Lớp III còn đưa ra mức độ nén và lọc cao hơn cả lớp II và sử dụng một bộ mã hóa Huffman. Layer Complexity Encoder Decoder I 1.5 – 3 1 II 2 – 4 1.25 III > 7.5 2.5 Trong bảng trên, độ phức tạp của bộ giải mã lớp I được dùng để so sánh. III. CÁC THÔNG SỐ DÙNG TRONG MPEG. Chuẩn MPEG cho phép ta chọn lựa các thông số cho việc nén âm thanh tốt nhất phù hợp với ứng dụng mà ta sử dụng. Lược đồ mã hóa cho các loại là tổng quát. Các thông số có thể chọn lựa trong bộ mã hóa MPEG bao gồm: Mode, Sampling frequency, bitrate, và Layer. a. Mode. Chuẩn MPEG có 4 chế độ: · Mono. · Dual channel. · Stereo. · Intensity Stereo (còn gọi là Joint Stereo). Chế độ Mono rõ ràng được dùng cho âm thanh 1 kênh. Để chọn chế độ cho các ứng dụng 2 kênh, đầu tiên ta phải xác định đâu là tín hiệu trái và đâu là tín hiệu phải để chia chúng ra thành 2 files khác nhau, nhằm sau này ta có thể làm việc độc lập trên kênh trái hoặc phải. Lúc đó ta sẽ chọn chế độ Mono. Nếu 2 kênh không cần hoạt động độc lập, ta chọn Stereo, Dual hay Intensity Stereo để tạo một file duy nhất. Chế độ Stereo hay kênh Dual là hoàn toàn đồng nhất khi chúng cùng sinh ra một file duy nhất cho tín hiệu stereo. Tuy nhiên một bit chỉ thị sẽ nhận dạng xem một file là ở chế độ nào và có thể được dùng cho những áp dụng nào... Chế độ Intensity Stereo xem xét sự dư thừa giữa các kênh trái và phải nhằm tối ưu mã. Chất lượng chủ quan của Intensity Stereo thay đổi theo hình ảnh stereo của tín hiệu đã mã hóa. Tuy nhiên nó đặc biệt thích hợp cho tốc độ truyền bit thấp. b. Sampling Frequency (tốc độ lấy mẫu). Một số tốc độ lấy mẫu: 32kHz, 44.1kHzvà 48kHz đối với MPEG1 (Tiêu chuẩn ISO/IEC 11172-3). 16kHz, 22.05kHzvà24kHz đối với MPEG2 (Tiêu chuẩn ISO/IEC13818-3). Khi chọn lựa tốc độ lấy mẫu cần xem xét các vấn đề: · Tần số lấy mẫu càng lớn thì chất lượng âm thanh càng cao(độ dài frame nhỏ hơn). · Băng thông tín hiệu giới hạn ở mức 15 kHz khi lấy mẫu ở tốc độ 32 kHz và 8 kHz ở tốc độ 16 kHz. · Tần số lấy mẫu (kHz) và tốc độ của âm thanh mã hóa (kbps) có thể chọn độc lập. · Tần số lấy mẫu 44.1 kHz hay 22.05 kHz là không thiết thực cho việc chọn lọc vì độ dài frame (byte) là thay đổi. · Những file được lấy mẫu ở những tần số khác nhau thì rất khó khăn khi hòa trộn. · Khi dùng đường nhập số AES/EBU, tần số lấy mẫu bị cố định bởi tín hiệu nhập. Nếu không bắt buộc, Digigram yêu cầu lấy mẫu ở 48 kHz hoặc 44.1 kHz cho phát thanh hay ứng dụng multimedia. Nếu ta phải sử dụng tốc độ bit thấp cho sự truyền có hiệu qủa, tốc độ 24 kHz là thích hợp. c. Bit Rate. Mỗi Layer và chế độ có nhiều cách chọn lựa tốc độ bit (bit rate). Việc chọn tốc độ bit tùy thuộc trước tiên vào chất lượng âm yêu cầu. Băng thông tín hiệu là hẹp hơn nếu tốc độ bit thấp, khiến cho nó không thực tế đối với một số ứng dụng. Tốc độ bit được đo theo kilobits/sec(kbps). Khi chọn lựa tốc độ bit cần xem xét các vấn đề: · Tại 128 kbps trên mỗi kênh (hay 256 kbps stereo), chất lượng âm thanh CD sẽ đạt được với Layer I hay Layer II. · Tại 192 kbps trên mỗi kênh, chất lượng âm thanh là hoàn toàn trong suốt. Tốc độ 128 kbps/kênh được dùng phổ biến nhất trong phát thanh. Nó tương ứng với tỉ số nén 1:6 ở tốc độ lấy mẫu 48 kHz. Tốc độ thấp hơn 128 kbps/kênh được dùng trong các ứng dụng yêu cầu tỉ số nén lớn hơn do giới hạn của băng thông truyền hay thiết bị lưu trữ. Một số tốc độ bit cung cấp bởi chuẩn âm thanh MPEG : MPEG 1: 32 kHz, 44.1 kHz và 48 kHz - Layer I : 32, 64, 96, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448 kbps. Những tốc độ này là có thể ở chế độ Mono hay stereo.. - Layer II : 32, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320, 384 kbps. 32, 48, 56, 80 kbps chỉ có thể ở chế độ Mono; •64, 96, 112, 128, 160, 192 kbps có thể ở cả hai chế độ Mono và Stereo;•224, 256, 320, 384 kbps chỉ có thể ở chế độ Stereo. MPEG 2 : 16 kHz, 22.05 kHz và 24 kHz - Layer I : 32, 48, 56, 64, 80, 96, 112, 128, 144, 160, 176, 192, 224, 256 kbps Những tốc độ này là có thể ở chế độ Mono hay stereo.. - Layer II : 8, 16, 24, 32, 40, 48, 56, 64, 80, 96, 112, 128, 144, 160 kbps. Những tốc độ này là có thể ở chế độ Mono hay stereo. d. Layers. Chuẩn MPEG có ba layer. Khi chọn lựa tốc độ bit cần xem xét các vấn đề: · Ở cùng tốc độ bit, Layer II mang lại chất lượng âm thanh tốt hơn Layer I. Kết luận này là chủ quan, vì sự chênh lệch là rất khó phân biệt ở tốc độ bit 128 kbps và lớn hơn. · Dùng Layer I thì việc chọn lọc chính xác hơn Layer II bởi vì độ phân giải của Layer I gấp ba lần Layer II. Resolution Table Sampling frequency Layer I (384 samples) Layer II (1152 samples) 32 kHz 12 ms 36 ms 44.1 kHz # 8.71 ms # 26.12 ms 48 kHz 8 ms 24 ms 16 kHz 24 ms 72 ms 22.05 kHz # 17.42 ms # 52.24 ms 24 kHz 16 ms 48 ms Các điểm kỹ thuật mấu chốt. Chuẩn mã hóa âm thanh MPEG chỉ định việc ghi một số cố định các mẫu (384 cho Layer I và 1152 cho Layer II) để tạo ra một chuỗi các bytes gọi là “frame”. “Frame” là thực thể nhỏ nhất được điều khiển bởi một ứng dụng. Việc chọn tốc độ bit(kbps) thiết lập nên kích thước của frame đó theo byte. Ví dụ: Ở 48 kHz, 128 kbps, chế độ Mono, Layer II: · 48,000 mẫu, tương ứng 1000 ms hay 1s, 1152 mẫu tương ứng 24 ms. · Ở tốc độ bit 128,000 bits/s, 3072 bits (384 bytes) cần cho 24 ms. · Chiều dài frame vì thế là 384 byte. · Để lưu 1 phút, cần 960,000 byte (hay khoảng 1 Megabyte) đĩa trống. CHƯƠNG 5. CÁC GIẢI THUẬT NÉN ÂM THANH. I. NỀN TẢNG LÝ THUYẾT THÔNG TIN. Theo Shannon, entropy của một nguồn thông tin S được định nghĩa: H(S) = h = Sipilog2(1/pi) Trong đó: - pi là xác suất mà ký hiệu Si xuất hiện trong S. - log2(1/pi) chỉ ra số lượng thông tin chứa đựng trong Si, nghĩa là số bit cần thiết để mã hóa Si. Ví dụ: một hình ảnh được tô đều với cùng một cường độ màu xám, tức là pi=1/256, thì số bit cần thiết để mã hóa cho mỗi mức xám là 8 bits. Entropy của hình này là 8. Giải thuật Shannon - Fano: Ta dùng một ví dụ đơn giản để mô tả giải thuật: Ký hiệu A B C D E --------------------------------------------------- Số lần 15 7 6 6 5 Mã hóa cho giải thuật Shannon - Fano: Dùng cách tiếp cận từ trên xuống. Sắp thứ tự các ký hiệu theo tần số xuất hiện của nó, nghĩa là: ABCDE. Chia thành hai phần, mỗi phần tương đương với cùng số lần đếm. Hình 5.1 Ký hiệu Số lần log(1/p) Mã Cộng(số bit) ---------- -------- ---------- ----- --------------- A 15 1.38 00 30 B 7 2.48 01 14 C 6 2.70 10 12 D 6 2.70 110 18 E 5 2.96 111 15 Tổng cộng(số bit) : 89 II. CÁC GIẢI THUẬT NÉN KHÔNG CÓ TỔN THẤT. 1. Mã hóa Huffman. Khởi tạo: đưa tất cả các node vào danh sách OPEN theo thứ tự tại mọi thời điểm. Ví dụ: ABCDE. Lặp lại cho đến khi danh sách OPEN chỉ còn một node bên trái như sau: - Từ danh sách OPEN, chọn hai node có xác suất thấp nhất, tạo node cha cho chúng. - Gán tổng các xác suất cho node cha và đưa node cha vào danh sách OPEN. - Gán các mã 0, 1 vào các nhánh của cây, xóa các node con khỏi danh sách OPEN. Hình 5.2 Ký hiệu Số lần log(1/p) Mã Cộng(số bit) ---------- --------- ---------- ----- --------------- A 15 1.38 0 30 B 7 2.48 100 14 C 6 2.70 101 12 D 6 2.70 110 18 E 5 2.96 111 15 Tổng cộng (số bit) : 87 Việc giải mã cho cả hai giải thuật trên là tầm thường chừng nào mà bảng mã (thống kê) được gửi trước dữ liệu. Có một bit bên trên công việc truyền này, nhưng không đáng kể nếu file dữ liệu lớn. Tính chất tiền tố duy nhất: không có mã nào là tiền tố cho một mã khác (tất cả các ký hiệu đều là node lá) ® rõ ràng là lớn đối với bộ giải mã. Nếu việc thống kê có thể tiến hành được trước đó và với độ chính xác cao, thì mã Huffman là rất tốt. Trong ví dụ trên:Entropy=(15x1.38+7x2.48+ 6x2.7 + 6x2.7 + 5x2.96)/39 = 85.26 / 39 = 2.19. Số bit cần thiết cho mã hóa Huffman là : 87 / 39 = 2.23 2. Mã Huffman sửa đổi. (a) Các giải thuật trên đây yêu cầu kiến thức về thống kê là điều mà khó có thể thực hiện (ví dụ âm thanh, hình ảnh sống..). (b) Ngay cả khi nếu điều đó là có thể làm được thì chi phí cho nó khá nặng, đặc biệt khi có nhiều bảng phải được truyền mà mô hình non-order() được sử dụng, nghĩa là việc đưa vào tính toán sự ảnh hưởng của các ký hiệu trước đó với xác suất của ký hiệu hiện hành (ví dụ: “qu” thường đi với nhau,..). Bộ mã hóa Initialize_model(); while ((c = getc (input)) != eof) { encode(c, output); update_model(c); } Bộ giải mã Initialize_model(); while ((c = decode (input)) != eof) { putc(c, output); update_model(c); } Giải pháp đưa ra là dùng giải thuật sửa đổi cho thích hợp. Như ví dụ, việc mã hóa Huffman sửa đổi được khảo sát sau đây với ý tưởng là làm thế nào có thể áp dụng vào các giải thuật nén thích hợp khác. Mấu chốt ở đây là cả hai bộ mã hóa và giải mã đều dùng cùng các hàm Initialize_model và update_model . Hàm update_model có hai lưu ý: (a) Tăng biến đếm. (b) Cập nhật cây Huffman. - Trong suốt qúa trình cập nhật, cây Huffman sẽ được duy trì tính kế thừa, các nodes (node trong và lá) được sắp xếp theo thứ tự tăng dần của trọng lượng . - Khi cần thiết trao đổi (swapping), node xa nhất với trọng lượng W được trao đổi với node mà trọng lượng của nó tăng lên 1 đơn vị W+1. Lưu ý: nếu node trọng lượng W có cây con bên dưới nó thì cây con đó cũng phải dời cùng với nó. Cây Huffman có thể nhìn rất khác so với trước khi trao đổi, ví dụ trong cây thứ 3 , node A được trao đổi và trở thành node 5. Bây giờ nó được mã hóa chi bằng 2 bit. 3. Mã hóa số học. Mã hóa Huffman sử dụng một số nguyên k các bit cho mỗi ký hiệu, vì thế k không bao giờ nhỏ hơn 1. Đôi khi, ví dụ phải truyền một hình ảnh 1 bit, thì không thể nén được. Ý tưởng: giả sử mẫu tự là [X,Y] và P(X) = 2/3 P(Y) = 1/3. Nếu ta chỉ quan tâm với chiều dài mã hóa là 2 thông điệp, thì ta có thể ánh xạ tất cả thông điệp có thể có vào những đoạn trong phạm vi [0..1] Để mã hóa thông điệp, chỉ dùng vừa đủ số bit cần thiết cho mỗi đoạn. Tương tự, ta có thể ánh xạ tất cả chiều dài 3 thông điệp vào các đoạn trong [0..1]. Nói chung, số bit được xác định bằng kích thước của đoạn. Ví dụ: Đoạn đầu tiên là 8/27, cần 2 bit® 2/3 bit cho mỗi ký tự. Đoạn cuối là 1/27, cần 5 bit. Tóm lại, cần -[logp] bit để biểu diễn cho đoạn có kích thước p. Vấn đề đặt ra là làm thế nào để xác định được xác suất? Ý tưởng đơn giản là dùng mô phỏng: bắt đầu bằng việc đoán tần số của một ký hiệu. Cập nhật tần số cho mỗi ký hiệu mới. 4. Giải thuật Lempel-Ziv-Welch(LZW). Giả sử chúng ta muốn mã hóa cho một cuốn tự điển Tiếng Anh 159,000 từ. Như vậy mỗi từ cần 18 bit để mã hóa. Nhược: - Dùng qúa nhiều bit. - Chỉ làm việc cho ký tự tiếng Anh. Giải pháp: - Cần phải tìm một cách mã hóa cuốn từ điển cho thích hợp. - Các phương pháp ban đầu được đề xuất bởi Ziv và Lempel vào năm 1978 và 1979. Terry Welch phát triển lược đồ vào năm 1981 và trở thành giải thuật LZW. Giải thuật: w = NIL; while (read a character k) { if wk exists in the dictionary w = wk; else add wk to the dictionary; output the code for w; w = k; } LZW nguyên gốc sử dụng từ điển với 4K mục từ, 256 từ đầu tiên là mã ASCII. Ví dụ: chuỗi ký tự là “^WED^WE^WEE^WEB^WET”. w k output index symbol ------------------------------------------------------------------ NIL ^ ^ W ^ 256 ^W W E W 257 WE E D E 258 ED D ^ D 259 D^ ^ W ^W E 256 260 ^WE E ^ E 261 E^ ^ W ^W E ^WE E 260 262 ^WEE E ^ E^ W 261 263 E^W W E WE B 257 264 WEB B ^ B 265 B^ ^ W ^W E ^WE T 260 266 ^WET T EOF T 19 ký hiệu nhập được giảm xuống 7 ký tự và 5 mã. Mỗi mã/ký hiệu sẽ cần nhiều hơn 8 bit, ta lấy 9 bit. Thông thường, công việc nén chỉ được bắt đầu khi có một số lớn byte được đọc vào (ví dụ >100). Giải thuật giải nén LZW: read a character k; output k; w = k; while ( read a character k ) /* k could be a character or a code. */ { entry = dictionary entry for k; output entry; add w + entry[0] to dictionary; w = entry; } III. CÁC GIẢI THUẬT NÉN CÓ TỔN THẤT. 1. Các phương pháp nén âm thanh đơn giản: Các phương pháp nén khảo sát ở trên không hiệu quả trong việc nén âm thanh. Sau đây là các phương pháp nén có tổn thất: - Nén “silence” : dò các khoảng “yên lặng”, giống như mã hoá run-length. - LPC (Linear Predictive Coding). - CELP (Code Excited Linear Predictor). 2. Nén âm thanh dùng mô hình ââm - tâm lý. a. Hệ thống nghe và phát âm của con người. Phạm vi nghe được từ 20 Hz đến 20 kHz, nhạy cảm ở 2 - 5kHz. Phạm vi phát âm bình thường từ 500 Hz đến 2 kHz. b. Che tần số (Frequency masking) “Ngưỡng che” (Threshold masking): sinh ra từ hiệu ứng che, mỗi âm với một tần số và mức to (dB) xác định sẽ có một “ngưỡng che” (xem hình 4.3 và 4.4) c. Băng giới hạn. Thước đo tần số đồng bộ không tương xứng với độ rộng của đường cong che. Băng giới hạn có độ rộng là 100Hz đối với các tần số che 500Hz. Định nghĩa một đơn vị mới cho tần số là bark ( Barkhausen) 1 Bark = bề rộng của băng giới hạn: - Tần số <500Hz : 1 bark = freq/100. - Tần số >500Hz : 1 bark = 9 + 4log(freq/1000). Ngưỡng che trên thước đo băng giới hạn: Hình 5.3 d. Che nhất thời (Temporal masking): che theo thời gian. Tai người cũng có đặc tính lưu âm. Nếu có một âm thanh lớn, rồi ngưng nó lại, mãi một lúc sau ta mới có thể nghe được một âm lân cận nhỏ hơn (xem hình 4.5 và 4.6). 3. Nén âm thanh MPEG. Vài thông số: MPEG-1 : 1.5Mbits/s cho âm thanh và hình ảnh. Khoảng 1.2 Mbits cho hình ảnh và 0.3Mbits/s cho âm thanh. Aâm thanh CD không nén dùng: (44,100 mẫu/s * 16bit/mẫu * 2 kênh) > 1.4 Mbits/s Aâm thanh MPEG cung cấp các tần số lấy mẫu là 32, 44.1 và 48 kHz. Giải thuật: Dùng bộ lọc thông để chia tín hiệu âm thanh thành các sub-band theo tần số, tương ứng với 32 băng giới hạn ® lọc sub-band. Xác định số lượng che của mỗi band gây bởi các band lân cận bằng các kết qủa bước 1 ® mô hình âm - tâm lý. Nếu mức to của một băng mà nhỏ hơn ngưỡng che thì không mã hóa nó. Ngược lại, xác định số bit cần thiết để mã hóa sao cho nhiễu sinh ra bởi việc lượng tử hóa này thấp hơn đường cong che. 5. Định dạng dòng dữ liệu bit : Hình 5.4 Ví dụ: Sau khi phân tích, 16 band đầu tiên trong số 32 band như sau: _________________________________________________________ Band 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Level(dB) 0 8 12 10 6 2 10 60 35 20 15 2 3 5 3 1 _________________________________________________________ Nếu mức to của âm thứ 8 là 60dB, nó sẽ che band thứ 7 ở mức 12dB và band thứ 9 ở mức 15dB. Mức to ở band 7 là 10dB (<12dB) nên bị bỏ qua, không mã hóa. Mức to band 9 là 35 (> 15dB) nên được tiếp tục xử lý. Layer I: bộ lọc loại DCT với 1 frame và độ rộng tần số như nhau trên mỗi sub-band. Mô hình âm-tâm lý chỉ sử dụng hiệu quả che tần số (Frequency masking). Layer II: sử dụng 3 frame trong bộ lọc (trước, hiện tại và kế tiếp, tổng cộng 1152 mẫu). Mô hình âm-tâm lý có sử dụng hiệu quả che nhất thời (Temporal masking). Layer III: dùng bộ lọc băng giới hạn tốt hơn, mô hình âm-tâm lý có sử dụng hiệu quả ch