Chương 5: Mã hóa nguồn – Tài liệu, ebook

Mã hóa nguồn 1 Một số khái niệm chung Mã hóa nguồn Nguồn thông tin 2 Mã hóa nguồn rời rạc không nhớ Mô hình toán học nguồn thông tin Mã hóa với từ mã có độ dài cố định và thắt chặt Mã hóa với từ mã có độ dài đổi khác 3 Mã hóa cho nguồn dừng rời rạc Entropy của nguồn dừng rời rạc Mã hóa Huffman cho nguồn rời rạc Mã hóa độc lập thống kê nguồn Lempel-Ziv 4 Cơ sở kim chỉ nan mã hóa nguồn liên tục Khái niệm cơ bản Hàm vận tốc tạo tin xô lệch Lượng tử hóa vô hướng Lượng tử hóa vector 5 Các kỹ thuật mã hóa nguồn liên tục Mã hóa tín hiệu miền thời hạn

65 trang

Bạn đang đọc: Chương 5: Mã hóa nguồn – Tài liệu, ebook

| Chia sẻ : tlsuongmuoi

| Lượt xem: 8578

Xem thêm: Có 3 giai đoạn phát triển trí não đỉnh cao của trẻ

| Lượt tải : 6

Bạn đang xem trước 20 trang tài liệu Chương 5: Mã hóa nguồn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

Xem thêm: TOP 5 game tư duy trí tuệ cực hấp dẫn để luyện não

Chương 5 : Mã hóa nguồn 1 Một số khái niệm chung Mã hóa nguồn Nguồn thông tin 2 Mã hóa nguồn rời rạc không nhớ Mô hình toán học nguồn thông tin Mã hóa với từ mã có độ dài cố định và thắt chặt Mã hóa với từ mã có độ dài biến hóa 3 Mã hóa cho nguồn dừng rời rạc Entropy của nguồn dừng rời rạc Mã hóa Huffman cho nguồn rời rạc Mã hóa độc lập thống kê nguồn Lempel-Ziv 4 Cơ sở kim chỉ nan mã hóa nguồn liên tục Khái niệm cơ bản Hàm vận tốc tạo tin xô lệch Lượng tử hóa vô hướng Lượng tử hóa vector 5 Các kỹ thuật mã hóa nguồn liên tục Mã hóa tín hiệu miền thời hạn Mã hóa tín hiệu miền tần số Mã hóa quy mô nguồn Cơ sở Lý thuyết Truyền tin Hà Quốc Trung1 1B ộ môn Mạng máy tính và Truyền thông Khoa Công nghệ thông tin Đại học Bách khoa Hà nội 1. Một số khái niệm chung 1 Một số khái niệm chung Mã hóa nguồn Nguồn thông tin 2 Mã hóa nguồn rời rạc không nhớ 3 Mã hóa cho nguồn dừng rời rạc 4 Cơ sở kim chỉ nan mã hóa nguồn liên tục 5 Các kỹ thuật mã hóa nguồn liên tục Khái niệm chung Là phép biến hóa tiên phong cho nguồn tin nguyên thủy Đầu vào của phép biến hóa này hoàn toàn có thể là : nguồn tin rời rạc hoặc nguồn tin liên tục Trong cả hai trường hợp mục tiêu chính của phép mã hóa nguồn là màn biểu diễn thông tin với tài nguyên tối thiểu Các yếu tố cần điều tra và nghiên cứu Mã hóa nguồn rời rạc Mã hóa nguồn liên tục Nén dữ liệu Chương 5 : Mã hóa nguồn 1. Một số khái niệm chung 4 / 65 1.2. Mã hóa nguồn Nguồn thông tin tạo ra các đầu ra một cách ngẫu nhiên Nguồn rời rạc : tạo ra một chuỗi các ký hiệu ngẫu nhiên Nguồn không nhớ : các ký hiệu Open một cách độc lập với nhau Nguồn có nhớ : các ký hiện Open phụ thuộc vào vào các ký hiệu đã Open trước đo Nguồn dừng các mối liên hệ thống kê giữa các thời gian không phụ thuộc vào vào thời hạn Với nguồn rời rạc, yếu tố cơ bản là đổi khác bảng vần âm và phân bổ Phần Trăm để giảm bớt số lượng ký hiệu cần dùng Nguồn liên tục tạo ra một tín hiệu, một bộc lộ của một quy trình ngẫu nhiên Nguồn liên tục hoàn toàn có thể được biến thành một chuỗi các biến ngẫu nhiên ( liên tục ) bằng phép lấy mẫu Lượng tử hóa cho phép biến hóa các biến ngẫu nhiên này thành các biến ngẫu nhiên rời rạc, với sai số nhất định Các kỹ thuật mã hóa nguồn tương tự như Chương 5 : Mã hóa nguồn 1. Một số khái niệm chung 5 / 65 2. Mã hóa nguồn rời rạc không nhớ 1 Một số khái niệm chung 2 Mã hóa nguồn rời rạc không nhớ Mô hình toán học nguồn thông tin Mã hóa với từ mã có độ dài cố định và thắt chặt Mã hóa với từ mã có độ dài biến hóa 3 Mã hóa cho nguồn dừng rời rạc 4 Cơ sở triết lý mã hóa nguồn liên tục 5 Các kỹ thuật mã hóa nguồn liên tục Mô hình toán học nguồn rời rạc Với nguồn rời rạc cần quan tâm Entropy của nguồn tin nguyên thủy Entropy của nguồn sau khi mã hóa Hiệu quả của phép mã hóa Giới hạn của hiệu suất cao mã hóa Xét một nguồn rời rạc không nhớ, sau một thời hạn ts tạo ra ký hiệu xi trong L ký hiệu với các Tỷ Lệ Open là P. ( i ) Để cho đơn thuần, chỉ xét trường hợp mã hiệu nhị phân. Khi đó : lượng tin = lượng bít = số ký hiệu nhị phân Với mã hiệu có cơ số lớn hơn 2, hoàn toàn có thể lan rộng ra các hiệu quả thu được. Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 7 / 65 2.2. Mã hóa với từ mã có độ dài cố định và thắt chặt Nguyên tắc : Mã hóa một ký hiệu nguồn thành một chuỗi ký hiệu mã có độ dài xác lập R Để bảo vệ phép mã hóa là 1-1, một ký hiệu nguồn tương ứng với 1 chuỗi ký hiệu nhị phân. Số lượng chuỗi nhị phân phải lớn hơn số ký hiệu nguồn 2R ≥ L hay R ≥ log2 L Nếu L là lũy thừa của 2 thì giá trị nhỏ nhất của R là log2 L Nếu L không là lũy thừa của 2, giá trị đó là blog2 Lc + 1 Như vậy R ≥ H ( X ). Hiệu suất của phép mã hóa H ( X ) R ≤ 1 Tốc độ lập tin đầu ra sẽ lớn hơn vận tốc lập tin đầu vào Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 8 / 65 Tăng hiệu suất cao mã hóa Hiệu quả mã hóa đạt giá trị cực lớn khi L là lũy thừa của 2 Nguồn tin khởi đầu đẳng Xác Suất Nếu nguồn tin khởi đầu đẳng Phần Trăm, nhưng L không là lũy thừa của 2, số lượng ký hiệu nhỏ nhất sẽ là bH ( X ) c + 1. Hiệu quả của nguồn là H ( X ) bH ( X ) c + 1 ≥ H ( X ) H ( X ) + 1 Để tăng hiệu suất cao, cần tăng lượng tin cho mỗi lần mã hóa : mã hóa cùng một lúc J ký hiệu. Hiệu quả mã hóa JH ( X ) bJH ( X ) c + 1 ≥ JH ( X ) JH ( X ) + 1 Biểu thức trên tiến tới 1 khi J tiến tới vô cùng Kết quả này chỉ đúng cho nguồn đẳng Xác Suất. Phép mã hóa không có sai số, mỗi chuỗi ký hiệu nguồn luôn luôn tương ứng với 1 từ mã duy nhất. Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 9 / 65 Tăng hiệu suất cao bằng mã hóa có sai số Trong trường hợp nguồn không đẳng Tỷ Lệ, để hoàn toàn có thể tiệm cận với hiệu suất cao tối đa ( 1 ), cần gật đầu một sai số nào đó Xét LJ chuỗi ký hiệu nguồn có độ dài J, mã hóa bằng chuỗi các ký hiệu nhị phân có độ dài R, 2R < LJ Như vậy còn LJ − 2R tổng hợp ký hiệu nguồn không có từ mã tương ứng Sử dụng 2R − 1 từ mã mã hóa 2 − 1 chuỗi ký hiệu nguồn Các chuỗi ký hiệu nguồn còn lại ( chọn các chuỗi có Xác Suất nhỏ nhất ), được mã hóa bằng 1 từ mã chung Nếu nguồn phát một chuỗi các ký hiệu trùng với các chuỗi ký hiệu có Phần Trăm thấp, sẽ có sai số. Gọi Xác Suất sai số là Pe Liên quan giữa Pe, R, J ? Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 10 / 65 Định lý mã hóa nguồn 01 Theorem Cho U là một nguồn tin có Entropy hữu hạn. Mã hóa các khối J ký hiệu của nguồn thành các từ mã N ký hiệu nhị phân. là một số dương bất kể Xác suất sai số hoàn toàn có thể nhỏ tùy ý nếu R = N J ≥ H ( U ) + trái lại, nếu R = N J ≤ H ( U ) − thì sai số sẽ tiến tới 1 khi J tiến tới vô hạn Tốc độ lập tin của đầu ra luôn luôn lớn hơn của đầu vào Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 11 / 65 Chứng minh định lý Chứng minh. Phần thuận Coi tập hợp các chuỗi ký hiệu nguồn mà | I ( uJ ) J − H ( U ) | ≥ là các chuỗi ký hiệu nguồn ánh xạ vào cùng một từ mã. Cần chứng tỏ 1 Xác suất Open của các từ mã nói trên hoàn toàn có thể bé tùy ý khi L lớn tùy ý ( hiển nhiên, limJ → ∞ I ( uJ ) J = H ( U ) ) 2 Các chuỗi ký hiệu còn lại hoàn toàn có thể được mã hóa đúng mực ( 1-1 ) với R = NJ ≥ H ( X ) + Phần hòn đảo : Chứng minh xác suất sai số tiến đến 1 ( ? ) Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 12 / 65 Chứng minh phần thuận Gọi tập hợp các ký hiệu còn lại là T. Với mỗi uJ ∈ T có I ( uJ ) J − H ( U ) ≤ H ( U ) − ≤ I ( uJ ) J ≤ H ( U ) + 2 − J ( H ( U ) − ) ≥ P ( uJ ) ≥ 2 − J ( H ( U ) + ) Chú ý 1 ≥ P ( T ) ≥ MTmin ( P. ( uJ ) ) ≥ MT2 − J ( H ( U ) + ) Có MT ≤ 2J ( H ( U ) + ) Vậy nếu chọn chuỗi nhị phân có độ dài tối thiểu là Nmin = log2 2 J ( H ( U ) + ) = J ( H ( U ) + ) sẽ có ánh xạ 1-1 giữa T và tập các từ mã N ký hiệu nhị phân Phép ánh xạ chung sẽ có sai số nhỏ tùy ý Pe = | I ( uJ ) J − H ( U ) | ≥ Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 13 / 65 Chứng minh phần hòn đảo Chọn N ≤ J ( H ( U ) − 2 ). Xét một phép mã hóa bất kể P. ( T ) + P. ( T ) + Pe = 1 Trong đó P. ( T ) là Xác Suất để mỗi một chuỗi ký hiệu trong T có một từ mã P. ( T ) là Tỷ Lệ để một chuỗi ký hiệu ngoài T có một từ mã Xác suất lỗi ( sống sót chuỗi ký hiệu không có từ mã ) Tổng cộng có 2N từ mã, mỗi từ mã sẽ tương ứng với một từ trong T có Tỷ Lệ nhỏ hơn 2 − J ( H ( U ) − ), vậy Phần Trăm để một từ trong T có một từ mã là P. ( T ) = 2 − J ( H ( U ) − ) 2N ≤ 2 − J ( H ( U ) − ) 2 − J ( H ( U ) − 2 ) = 2 − J Chú ý P. ( T ) tiến tới 0 khi j tiến tới vô cùng. Vậy Pe tiến tới 1 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 14 / 65 Ý nghĩa định lý Phép mã hóa với từ mã có độ dài không đổi nói chung bảo toàn độ bất định của nguồn H ( U ) là số ký hiệu nhị phân nhỏ nhất hoàn toàn có thể sử dụng để màn biểu diễn nguồn tin nguyên thủy một cách đúng chuẩn Trong trường hợp tổng quát, số ký hiệu nhỏ nhất đó hoàn toàn có thể đạt được khi mã hóa một khối có chiều dài vô tận các ký hiệu nguồn Định lý hoàn toàn có thể lan rộng ra cho mã hiệu cơ số lớn hơn 2. Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 15 / 65 2.3. Mã hóa với từ mã có độ dài biến hóa Mục tiêu : mã hóa ký hiệu với số lượng ký hiệu nhị phân tối thiểu Xét trường hợp nguồn có phân bổ Tỷ Lệ không đều Các ký hiệu nguồn có Phần Trăm Open lớn cần được mã hóa với các từ mã có độ dài nhỏ và ngược lại. Số ký hiệu trung bình cho mỗi ký hiệu của nguồn : R = L ∑ 1 nkP ( uk ) sẽ có giá trị tối ưu Mã hiệu sử dụng trong trường hợp này cần có tính prefix ( giải thuật được ) được bộc lộ bằng bất đẳng thức Kraft ( McMillan ) Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 16 / 65 2.3. Mã hóa với từ mã có độ dài biến hóa Theorem Điều kiện cần và đủ để sống sót một mã hiệu nhị phân có tính prefix với các từ mã có độ dài n1 ≤ n2 ≤. .. ≤ nL là L ∑ k = 1 2 − nk ≤ 1 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 17 / 65 Chứng minh phần thuận Xây dựng một cây mã nhị phân có 2 n, n = nL nút cuối Chọn một nút bậc n1. Đường dẫn tới nút đó lấy làm từ mã. Toàn bộ cây con trên nút đó coi là đã sử dụng ( gồm 2 n − n1 nút cuối ) Tiếp tục chọn một nút ở mức n2. Loại bỏ hàng loạt cây con của nút đó ( gồm 2 n − n1 nút cuối ). Nếu vẫn còn nút cuối chưa sử dụng, còn hoàn toàn có thể chọn được một nút ở mức bất kể Khi chọn nút nj số lượng các nút đã sử dụng là L ∑ k = 1 2 n − nk = 2 n L ∑ k = 1 2 − nk ≤ 2 n Vậy luôn luôn hoàn toàn có thể chọn được một nút cho đến khi nj > n = nL. Các từ mã tương ứng sẽ tạo ra một mã hiệu có tính prefix. Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 18 / 65 Chứng minh phần hòn đảo Biểu diễn mã hiệu prefix bằng cây nhị phân. Mỗi một từ mã tương ứng với một nút Không có từ mã nào nằm trong cây con của từ mã nào Hai cây con của hai từ mã bất kể rời nhau Tính số lượng các nút cuối thuộc về cây con của mỗi từ mã 2 n − nj Tính tống các nút thuộc về các cây con, có bất đẳng thức Kraft L ∑ k = 1 2 n − nk ≤ 2 n hay L ∑ k = 1 2 − nk ≤ 1 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 19 / 65 Định lý mã hóa nguồn 2 Theorem Cho X là một nguồn rời rạc không nhớ. Có thể mã hóa nguồn X bằng một mã hiệu nhị phân không đều, có tính prefix và có độ dài trung bình R của các từ mã thỏa mãn nhu cầu điều kiện kèm theo H ( X ) ≤ R < H ( X ) + 1 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 20 / 65 Chứng minh cận dưới Có H ( X ) − R = L ∑ k = 1 pk log2 1 pk − L ∑ k = 1 pknk = L ∑ k = 1 pk log2 2 − nk pk Sử dụng bất đẳng thức ln x ≤ x − 1 và bất đẳng thức Kraft H ( X ) − R ≤ ( log2 e ) L ∑ k = 1 pk ( 2 − nk pk − 1 ) ( log2 e ) ( L ∑ k = 1 2 − nk − 1 ) ≤ 0 Dấu bằng xảy ra khi pk = 2 − nk ∀ 1 ≤ k ≤ L Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 21 / 65 Chứng minh cận trên Cần tìm một mã hiệu sao cho R < H ( X ) + 1 Chọn nk sao cho 2 − nk ≤ pk < 2 − nk + 1. Có nk < 1 − log2 pk. Vậy L ∑ k = 1 pknk ≤ L ∑ k = 1 pk ( 1 − log2 pk ) = 1 + H ( X ) Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 22 / 65 Mã hóa Shannon-Fano Nguyên tắc : độ dài từ mã tỷ suất nghịch với Tỷ Lệ Open Cách thức ( Fano ) : 1 Chia các ký hiệu nguồn thành m nhóm ( nếu mã nhị phân : 2 nhóm ), Xác Suất xê dịch như nhau ( làm thế nào để chia ? ) 2 Gán cho mỗi nhóm một ký hiệu 0 hoặc 1 3 Thực hiện 1 cho đến khi mỗi nhóm chỉ còn 1 ký hiệu Cách thức ( Shanon ) 1 Sắp xếp các ký hiệu nguồn theo thứ tự giảm dần của Tỷ Lệ 2 Với mỗi ký hiệu 1 tính tổng các Xác Suất của các ký hiệu đứng trước 2 Biểu diễn tổng thu được theo hệ nhị phân, độ đúng mực là Phần Trăm của ký hiệu 3 Từ mã tương ứng là chuỗi chữ số phần lẻ của trình diễn trên Kết quả : Bộ mã thu được có tính prefix Có thể màn biểu diễn quy trình bằng một cây Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 23 / 65 Ví dụ ( Shanon ) Lập mã cho nguồn có phân bổ Phần Trăm Ký hiệu u1 u2 u3 u4 u5 u6 u7 Xác suất 0.34 0.23 0.19 0.1 0.07 0.06 0.01 Lập bảng ui pi Pi Nhị phân ni Từ mã u1 0.34 0 0.0 2 00 u2 0.23 0.34 0.01 3 010 u3 0.19 0.57 0.1001 3 100 u4 0.1 0.76 0.1100 4 1100 u5 0.07 0.86 0.11011 4 1101 u6 0.06 0.93 0.11101 5 11101 u7 0.01 0.99 0.1111110 7 1111110 Entropy của nguồn 2.3828 Số ký hiệu nhị phân trung bình 2.99 Hiệu quả của nguồn : 0.7969 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 24 / 65 Ví dụ ( Fano ) ui pi Pi Nhị phân ni Từ mã u1 0.34 0 0 - - - 00 u2 0.23 0 1 - - - 01 u3 0.19 1 0 - - - 10 u4 0.1 1 1 0 - - 110 u5 0.07 1 1 1 0 - 1110 u6 0.06 1 1 1 1 0 11110 u7 0.01 1 1 1 1 1 11111 Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 25 / 65 Mã hóa Shannon-Fano Có thể có nhiều mã hiệu thích hợp, nhờ vào vào cách chia nhóm và phụ thuộc vào vào các ký hiệu gán cho mỗi nhóm Nếu sống sót cách chia nhóm ở toàn bộ các mức ( Fano ) hoặc trình diễn nhị phân đúng chuẩn tuyệt đối, khi đó tất cả chúng ta sẽ có mã thống kê tối ưu, R = H ( X ) Nếu H ( X ) < 1, các phép mã hóa sẽ không tối ưu. Giải pháp : gộp các ký hiệu nguồn. Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 26 / 65 Nguyên tắc mã hóa Huffman Nguyên tắc : Từ mã có Xác Suất Open nhỏ có chiều dài lớn Hai từ mã có Phần Trăm gần giống nhau mã hóa bằng hai từ mã gần giống nhau ( trọng số gần nhau ) Hai nhóm từ mã có chung một phần prefix có Phần Trăm gần nhau Giải thuật 1 Liệt kê các ký hiệu theo thứ tự Tỷ Lệ giảm dần 2 Chọn hai ký hiệu có Xác Suất nhỏ nhất, thay bằng một tin mới. Mỗi ký hiệu được gán cho một nhãn 0 hoặc 1 3 Các tin còn lại và tin mới lại được ghi vào cột thứ 2 theo thứ tự giảm dần 4 Bắt đầu từ bước 1 cho đến khi chỉ còn 2 ký hiệu 5 Các từ mã thu được bằng cách khai triển các nhãn tương ứng với ký hiệu và các ký hiệu mới tạo thành từ ký hiệu đó Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 27 / 65 2.3. Mã hóa với từ mã có độ dài đổi khác Tìm code Huffman cho nguồn tin có 8 ký hiệu, cấu trúc thống kê cho trong cột thứ 2 1 2 3 4 5 6 7 A0. 25 A0. 25 A0. 25 A0. 25 CD0. 28 EFGH-B0. 47 CD-A 0.53 ( 1 ) B0. 25 B0. 25 B0. 25 B0. 25 A0. 25 CD0. 28 ( 1 ) EFGH-B 0.47 ( 0 ) C0. 14 C0. 14 C0. 14 EFGH0. 22 B0. 25 ( 1 ) A0. 25 ( 0 ) D0. 14 D0. 14 D0. 14 C0. 14 ( 1 ) EFGH0. 22 ( 0 ) E0. 055 GH0. 11 GH0. 11 ( 1 ) D0. 14 ( 0 ) F0. 055 E0. 55 ( 1 ) EF0. 11 ( 0 ) G0. 055 ( 1 ) F0. 55 ( 0 ) H0. 055 ( 0 ) Vậy các từ mã sẽ là A B C D E F G H 10 01 111 110 0001 0000 0011 1111 Entropy của nguồn : 2.715 Số lượng ký hiệu trung bình : 2.72 Hiệu quả mã hóa : 0.98 Cách thiết lập cây mã : gốc ở bên phải, mỗi lần gộp là một mức Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 28 / 65 Mã hóa nguồn có cấu trúc thống kê đổi khác Trong toàn bộ các quy trình nói trên, mã hiệu phụ thuộc vào vào cấu trúc thống kê của nguồn Có thể tăng hiệu suất cao mã hóa bằng cách mã hóa từng khối ký hiệu. Khi đó độ dài từ trung bình bị số lượng giới hạn bởi JH ( X ) ≤ R < JH ( X ) + 1 Hiệu quả của phép mã hóa sẽ gần 1 hơn. Khi cấu trúc thống kê của nguồn biến hóa, cần biến hóa mã hiệu theo. Bộ giải thuật và bộ mã hóa cần thống nhất với nhau mã hiệu sử dụng Giải pháp Mã hóa động : mỗi khi truyền và nhận một ký hiệu, bộ giải thuật và bộ mã hóa update lại thông tin về các ký hiệu, cấu trúc lại cây mã, lập mã hiệu mới. Ví dụ : Mã Huffman động Mã hóa không nhờ vào cấu trúc thống kê. Ví dụ : mã hóa Lempel-Ziv Chương 5 : Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ 29 / 65 3. Mã hóa cho nguồn dừng rời rạc 1 Một số khái niệm chung 2 Mã hóa nguồn rời rạc không nhớ 3 Mã hóa cho nguồn dừng rời rạc Entropy của nguồn dừng rời rạc Mã hóa Huffman cho nguồn rời rạc Mã hóa độc lập thống kê nguồn Lempel-Ziv 4 Cơ sở kim chỉ nan mã hóa nguồn liên tục 5 Các kỹ thuật mã hóa nguồn liên tục 3.1. Entropy của nguồn dừng rời rạc Xét nguồn có nhớ ( các biến ngẫu nhiên tại các thời gian phụ thuộc vào thống kê ) Entropy của một khối các biến ngẫu nhiên liên tục được tính theo công thức H ( X1X2. .. Xk ) = k ∑ i = 1 H ( Xi | X1X2. .. Xi − 1 ) Có thể tính Entropy trung bình cho từng ký hiệu Hk ( X ) = 1 k H ( X1X2. .. Xk ) Cho k tiến tới vô cùng ∃ ? lim k → ∞ 1 k H ( X1X2. .. Xk ) Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 31 / 65 3.1. Entropy của nguồn dừng rời rạc ( Tiếp ) Mặt khác entropy của từng ký hiệu cũng hoàn toàn có thể được định nghĩa theo ∃ ? lim k → ∞ H ( Xk | X1X2. .. Xk − 1 ) Có thể chứng tỏ hai số lượng giới hạn này sống sót và bằng nhau với nguồn dừng ( Xem [ Proakis ] ) Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 32 / 65 3.2. Mã hóa Huffman cho nguồn rời rạc Mã hóa từng khối J ký hiệu của nguồn dừng với mã Huffman Số lượng ký hiệu nhị phân tối thiểu phải sử dụng thỏa mãn nhu cầu H ( X1X2. .. XJ ) ≤ − → R < H ( X1X2. .. XJ ) HJ ( X ) ≤ R > HJ ( X ) + 1J Cho J tiến tới vô cùng H ( X ) ≤ R < H ( X ) + bé tùy ý Vậy hiệu suất cao của mã hóa Huffman với nguồn dừng có nhớ hoàn toàn có thể tiệm cận 1 Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 33 / 65 Tuy nhiên ..... Cần biết hàm tỷ lệ phân bổ Tỷ Lệ đồng thời của J ký hiệu nguồn liên tục Cần nhìn nhận các Xác Suất Cần tính lại mã hiệu Cần đồng nhất mã hiệu mã hóa và giải thuật Cần .... ? Độ phức tạp thuật toán lớn Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 34 / 65 3.3. Mã hóa độc lập thống kê nguồn Lempel-Ziv Xét nguồn nhị phân Chia đầu ra nguồn nhị phân này thành các câu có tối đa n ký hiệu. Nguyên tắc chia dùng một từ điển như sau Lập một bảng từ điển gồm 3 cột : vị trí, nội dung, từ mã Xuất phát, từ điển rỗng, vị trí trong từ điển là 0000, cột nội dung có giá trị rỗng Nhận ký hiệu tiên phong 1, coi đó là một câu, ghi vào cột nội dung. Cột vị trí ghi giá trị 00001 Nhận ký hiệu 0, coi đó là một câu, ghi vào cột nội dung. Cột vị trí ghi giá trị 00000 Nhận các bộ 2 ký hiệu tiếp theo. Cột vị trí tăng dần các giá trị Nếu là 00, từ mã bằng vị trí của 0 thêm 0 ở cuối Nếu là 01, từ mã bằng vị trí của 0 thêm 1 ở cuối Nếu là 10, từ mã bằng vị trí của 1 thêm 0 ở cuối Nếu là 11, từ mã bằng vị trí của 1 thêm 1 ở cuối Tiếp tục như vậy với các bộ 3,4 ... ký hiệu cho đến khi tràn từ điển Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 35 / 65 Ví dụ Mã hóa dãy ký hiệu 10101101001001110101000011001110101100011011 Chia thành các câu 1,0,10,11,01,00,100,111,010, 1000, 011, 001, 110,101, 10001, 1011 Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 36 / 65 Xây dựng từ điển 1,0,10,11,01,00,100,111,010, 1000, 011, 001, 110,101, 10001, 1011 Vị trí trong từ điển Nội dung Từ mã 0001 1 00001 0010 0 00000 0011 10 00010 0100 11 00011 0101 01 00101 0110 00 00100 0111 100 00110 1000 111 01001 1001 010 01010 1010 1000 01110 1011 011 01011 1100 001 01101 1101 110 01000 1110 101 00111 1111 10001 10101 1011 11101 Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 37 / 65 Đánh giá Quá trình giải thuật : nhận được một từ mã, giải thuật từ trái qua phải để thu được câu cần tìm. Thông thường, từ điển được thiết kế xây dựng ở cả hai phía mã hóa và giải thuật để làm tăng vận tốc giải thuật Giới hạn về size của từ điển Trong ví dụ trên, mã hóa 44 bít dùng 16 từ mã 5 bít : không hiệu suất cao Nếu có 2 n từ mã, mã hóa được 2 n − 1 câu, vậy chiều dài tối đa của câu trong trường hợp xấu nhất là n-1 bít. Khi nào có trường hợp xấu nhất ? Thông thường, khi độ dài các câu đủ lớn, các chuỗi ký hiệu lặp lại nhiều, khi đó hiệu suất cao mã hóa sẽ lớn Chương 5 : Mã hóa nguồn 3. Mã hóa cho nguồn dừng rời rạc 38 / 65 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 1 Một số khái niệm chung 2 Mã hóa nguồn rời rạc không nhớ 3 Mã hóa cho nguồn dừng rời rạc 4 Cơ sở kim chỉ nan mã hóa nguồn liên tục Khái niệm cơ bản Hàm vận tốc tạo tin rơi lệch Lượng tử hóa vô hướng Lượng tử hóa vector 5 Các kỹ thuật mã hóa nguồn liên tục 4.1. Khái niệm cơ bản Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 40 / 65 4.1. Khái niệm cơ bản Nguồn tựa như : quy trình ngẫu nhiên liên tục Trong các mạng lưới hệ thống tiếp thị quảng cáo : nguồn tương tự như được biến thành nguồn tin rời rạc, xử lí rồi lại được đổi khác thành nguồn liên tục Rời rạc hóa nguồn liên tục Lấy mẫu nguồn tựa như : đổi khác nguồn tương tự như thành một chuỗi các giá trị ngẫu nhiên liên tục tại các thời gian thời hạn rời rạc Lượng tử hóa nguồn tương tự như : mã hóa các giá trị liên tục bằng nguồn rời rạc Tại đích, nguồn rời rạc được tổng hợp thành nguồn tương tự như Tái tạo lại giá trị liên tục của chuỗi giá trị khởi đầu từ các ký hiệu của nguồn rời rạc Kết nối các giá trị liên tục thành một tín hiệu ngẫu nhiên đầu ra Do quy trình lượng tử, đầu ra sai khác với nguồn vào : Sai số lượng tử Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 41 / 65 Định luật lấy mẫu X ( t ) = ∞ ∑ n = − ∞ X ( n 2W ) sin [ 2 piW ( t − n2W ) ] 2 piW ( t − n2W ) φ ( τ ) = ∞ ∑ n = − ∞ φ ( n 2W ) sin [ 2 piW ( τ − n2W ) ] 2 piW ( τ − n2W ) Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 42 / 65 Quá trình lượng tử hóa Ví dụ : Biểu diễn một biến ngẫu nhiên liên tục theo phân bổ chuẩn Gaussian Lượng tử hóa dùng 1 bít Luợng tử hóa dùng 2 bít : cần tìm vị trí thích hợp cho bít thứ hai để có sai số nhỏ nhất Mục đích của một thiết bị lượng tử hóa là giảm tối thiểu sai số này với một số ít bít / biến ngẫu nhiên nhỏ nhất ( hoặc ngược lại ) Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 43 / 65 4.2. Hàm vận tốc tạo tin rơi lệch Là vận tốc bít nhỏ nhất bảo vệ một xô lệch xác lập Cho một nguồn tin với phân bổ Phần Trăm nguồn cho trước, các mẫu tín hiệu được lượng tử hóa với sai số d ( x, x ). Sai số nhỏ yên cầu vận tốc truyền tin lớn và ngược lại Hàm vận tốc tạo tin-sai lệch màn biểu diễn liên hệ giữa sai số và vận tốc truyền tin Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 44 / 65 Định nghĩa Xác định sai số Nguồn sau khi lấy mẫu gồm nhiều mẫu Với mỗi mẫu, ký hiệu rơi lệch là d ( xk, xk ) Sai lêch hoàn toàn có thể được định nghĩa theo nhiều cách : phương sai E [ ( X − X ) 2 ], sai lêch lớn nhất E ( max ( | X − X | ) ) Sai số trên tập các biến ngẫu nhiên là kỳ vọng toán học cua d D = E [ d ( Xk, Xk ) ] = 1 n n ∑ k = 1 E [ d ( xk, xk ) ] = E [ d ( xk, xk ) ] Hàm vận tốc tạo tin-sai lệch RI ( D ) = min p ( x / x ) : E [ d ( X, X ) ] ≤ D I ( X, X ) Biểu diễn vận tốc lập tin kim chỉ nan nhỏ nhất để có sai số nhỏ hơn D, lượng tin tối thiếu để màn biểu diễn nguồn với sai số D Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 45 / 65 Định lý mã hóa nguồn với sai số cho trước Theorem Tồn tại một chiêu thức mã hóa nguồn, mã hóa các mẫu, với vận tốc tạo tin tối thiểu là R ( D ) bit / ký hiệu, với sai số sát tùy ý với D, với mọi D. Khẳng định ý nghĩa thực tiễn của khái niệm hàm vận tốc tạo tin-sai lệch Giới hạn kim chỉ nan / trong thực tiễn của quy trình lượng tử hóa Rất khó thống kê giám sát hàm vận tốc lập tin-sai số với các nguồn có nhớ hoặc không phải Gaussian Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 46 / 65 Ví dụ về nguồn chuẩn gaussian, không nhớ, rời rạc theo thời hạn Tốc độ lập tin tối thiểu là Rg ( D ) = { 1 2 log2 ( σ 2 x / D ) ( 0 ≤ D ≤ σ2x ) 0 ( D ≥ σ2x ) Như vậy nếu sai số thiết yếu lớn hơn rơi lệch của nguồn đã cho, không cần truyền tin nữa Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 47 / 65 Hàm sai số-tốc độ lập tin Biểu diễn sai số nhỏ nhất hoàn toàn có thể có khi mã hóa một nguồn tin tựa như D ( R ) = min p ( x / x ) : R ≤ R d ( X, X ) Có thể sử dụng một trong hai hàm để màn biểu diễn liên hệ giữa sai số và vận tốc lập tin Với nguồn Gaussian Dg = 2 − 2R σ2x Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 48 / 65 4.3. Lượng tử hóa vô hướng Xét bài toán lượng tử hóa một biến ngẫu nhiên liên tục ( mẫu của một nguồn liên tục dừng không nhớ ), biết hàm tỷ lệ phân bổ Tỷ Lệ của biến ngẫu nhiên Chia miền giá trị của X thành L khoảng chừng x0 = − ∞ < x1 < x2 < x3 <. .. < xk <. .. < xL = ∞ Mỗi một khoảng chừng xk − 1 < x < xk tương ứng với một mức tín hiệu xk Sai số tổng số sẽ là D = L ∑ k = 1 xk ∫ xk − 1 f ( xk − x ) p ( x ). dx Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 49 / 65 4.3. Lượng tử hóa vô hướng ( Tiếp ) Cần tối thiểu hóa sai số. Lấy đạo hàm theo xk, xk f ( xk − xk ) = f ( xk + 1 − xk ) Và xk ∫ xk − 1 f ′ ( xk − x ) p ( x ). dx = 0 Để màn biểu diễn các mức tín hiệu, cần log2 L bít. Phần Trăm của mổi mức tín hiệu sẽ là pk = xk ∫ xk − 1 p ( x ) dx Entropy của nguồn H ( X ) = − L ∑ k = 1 pk log2 pk Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 50 / 65 4.3. Lượng tử hóa vô hướng ( Tiếp ) Để tối ưu hóa, sau đó nguồn cần được mã hóa bằng mã hóa thống kê ( Fano-Shannon-Huffman ) Có thể chọn các mức sao cho các ký hiệu đầu ra đẳng Phần Trăm : phân các miền giá trị nguồn vào đẳng Xác Suất. Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 51 / 65 Ví dụ : nguồn có phân bổ đều Biên độ nguồn vào giao động trong khoảng chừng − A, A, sai số f = | x − x | Cần giải hệ f ( xk − xk ) = f ( xk + 1 − xk ) và xk ∫ xk − 1 f ′ ( xk − x ) p ( x ). dx = 0 Vậy cần chia đầu vào thành L khoảng chừng đều nhau, trong mỗi khoảng chừng đó lấy giá trị điểm giữa làm mức tín hiệu Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 52 / 65 Ví dụ : nguồn có phân bổ đều ( Tiếp ) Sai số tối ưu là D = L ∑ k = 1 xk ∫ xk − 1 f ( xk − x ) p ( x ). dx = AL Để hoàn toàn có thể mã hóa tối ưu cần chọn L là lũy thừa của 2 Nếu cho trước D vận tốc mã hóa tối thiểu là log2 AD nếu A D là lữy thừa của 2 hoặc1 + blog2 AD c nếu không Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 53 / 65 4.4. Lượng tử hóa vector Trong lượng tử hóa vô hướng miền giá trị của biến ngẫu nhiên đầu vào được chia thành nhiều miền con Tập giá trị trong miền con tương ứng với một mức tín hiệu đầu ra, bảo vệ khoảng cách ngắn nhất tới biên ( TT „ trọng tâm ) Chỉ dùng cho một biến ngẫu nhiên liên tục -> nguồn dừng, không nhớ Có thể tổng quát hóa khái niệm miền giá trị cho khoảng trống n chiều Xét cùng lúc nhiều biến ngẫu nhiên, mỗi biến ngẫu nhiên tương ứng với một chiều Miền con trở thành một ô trong khoảng trống n-chiều Mức tín hiệu đầu ra là một tín hiệu rời rạc ngẫu nhiên nhiều chiều, màn biểu diễn bằng TT của ô. Chương 5 : Mã hóa nguồn 4. Cơ sở kim chỉ nan mã hóa nguồn liên tục 54 / 65 4.4. Lượng tử hóa vector Xét n biến ngẫu nhiên nhiều chiều đặc trưng cho các mẫu của một nguồn liên tục Biểu diễn các biến ngẫu nhiên này trong khoảng trống n chiều Chia khoảng trống n chiều thành L ô Ck Các tín hiệu nguồn vào được lượng tử hóa theo phép mã hóa X = Q ( X ) Xk là giá trị đầu ra tương ứng với tín hiệu nguồn vào trong Ck Ví dụ : Lượn tử hóa vector 2 chiều Không gian hai chiều chia thành các ô có dạng hình lục giác Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 55 / 65 Sai số của phép lượng tử hóa vector D = L ∑ k = 1 P. ( X ∈ Ck ) E [ d ( X, X k ) | X ∈ Ck ] = L ∑ k = 1 P. ( X ∈ Ck ) ∫ X ∈ Ck d ( X, X k ) p ( X ) dX Để tối thiểu D Dạng của các ô phụ thuộc vào vào hàm phân bổ Xác Suất đồng thời Dạng của các ô cũng phụ thuộc vào vào hàm khoảng cách Q. ( X ) = Xk ⇔ D ( X, X k ) ≤ D ( X, X j ), k 6 = j, 1 ≤ j ≤ n Các mức tín hiệu đầu ra tương ứng là TT của các ô Dk = E [ d ( X, X k ) | X ∈ Ck ] = ∫ X ∈ Ck d ( X, X k ) p ( X ) dX Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 56 / 65 Sai số-tốc độ lập tin Hàm sai số d ( X, X ) = 1 n n ∑ k = 1 ( xk − xk ) 2 Tốc độ lập tin R = H ( X ) n trong đó H ( X ) = − L ∑ i = 1 p ( X i ) log 2 p ( X i ) Sai số-tốc độ lập tin Dn ( R ) = min Q. ( X ) E [ d ( X, X ) ] Hàm sai số-tốc độ lập tin D ( R ) = lim n → ∞ Dn ( R ) Chương 5 : Mã hóa nguồn 4. Cơ sở triết lý mã hóa nguồn liên tục 57 / 65 5. Các kỹ thuật mã hóa nguồn liên tục 1 Một số khái niệm chung 2 Mã hóa nguồn rời rạc không nhớ 3 Mã hóa cho nguồn dừng rời rạc 4 Cơ sở triết lý mã hóa nguồn liên tục 5 Các kỹ thuật mã hóa nguồn liên tục Mã hóa tín hiệu miền thời hạn Mã hóa tín hiệu miền tần số Mã hóa quy mô nguồn 5.1. Mã hóa tín hiệu miền thời hạn Biểu diễn tín hiệu theo miền thời hạn Lấy mẫu tín hiệu theo vận tốc Nyquist, tần số fs Các mẫu được lượng tử hóa Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 59 / 65 Điều chế mã xung ( Pulse Code Modulation ) Mỗi một mẫu tín hiệu được mã hóa bằng 2R mức tín hiệu. Tốc độ thông tin của nguồn sau mã hóa là Rfs bps. Giá trị tín hiệu đầu ra xn = xn + qn qn là nhiễu lượng tử ( nhiễu cộng ) Trong trường hợp các mức đều, tỷ lệ phân bổ Phần Trăm đều, sai số lượng tử tối thiểu ( xem ví dụ trên ) : Bộ lượng tử hóa đồng đều Trong trường hợp tỷ lệ phân bổ Tỷ Lệ không đều, cần chọn các mức tương ứng : Bộ lượng tử hóa không đồng đều Trong thực tiễn, với các tín hiệu lời nói, thường sử dụng các mức lượng tử theo loga Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 60 / 65 Mã hóa mã xung vi sai Nếu vận tốc lấy mẫu cao, các mẫu có liên hệ với nhau Dự đoán giá trị các mẫu ? Liên hệ thường thì : hàm số liên tục, đạo hàm hữu hạn. Giá trị mẫu sau sai khác với giá trị mẫu trước một khoảng chừng xác lập Không mã hóa giá trị tín hiệu, chỉ mã hóa sự sai khác so với giá trị của mẫu trước đó Xa hơn nữa, hoàn toàn có thể mã hóa mẫu hiện tại dựa vào p mẫu trước đó Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 61 / 65 Ví dụ về DPCM Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 62 / 65 PCM và DPCM thích nghi PCM và DPCM thích hợp với các nguồn dừng ( phân bổ thống kê của các biến ngẫu nhiên không đổi khác theo thời hạn ) Trong thực tiễn các nguồn tin ít khi dừng tuyệt đối Phân bố thống kê của các nguồn tin trong thực tiễn biến hóa chậm ( nguồn gần dừng ) Có thể cái thiện PCM và DPCM cho tương thích với các nguồn tin đó : đổi khác các thông số kỹ thuật của PCM hoặc DPCM PCM : biến hóa biên độ ( biến hóa khoảng cách giữa các mức ) DPCM : Thay đổi các thông số kỹ thuật của bộ Dự kiến Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 63 / 65 5.2. Mã hóa tín hiệu miền tần số Mã hóa băng con Mã hóa hình ảnh và lời nói Phân tích thông tin đầu vào theo tần số Chia thành nhiều dải con Mã hóa độc lập từng dải Ví dụ : mã hóa tiếng nói Phần tần số thấp chiếm nhiều nguồn năng lượng hơn phần tần số cao Phần tần số thấp được mã hóa bằng số bit ít hơn Mã hóa biến hóa thích nghi Các mẫu được chia thành nhiều khung Các khung này được biến hóa sang miền tần số và truyền đi ( giống giải pháp trên ) Khi nhận được các khung này, đổi khác ngược lại Tùy theo thông số kỹ thuật của phổ, các phổ quan trọng được mã hóa nhiều bít hơn Phép đổi khác thường là phép đổi khác Fourier. Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 64 / 65 5.3. Mã hóa quy mô nguồn Mô hình hóa nguồn tin : sử dụng một số ít tham số ( là các phản ứng của nguồn tin với các tín hiệu nguồn vào nhất định ) Mã hóa các tham số Giải mã để thu được các tham số Phục hồi tín hiệu bắt đầu Mô hình hay dùng là quy mô tuyến tính Chương 5 : Mã hóa nguồn 5. Các kỹ thuật mã hóa nguồn liên tục 65 / 65

Các file đính kèm theo tài liệu này :

• Mã hóa nguồn.pdf

Source: https://thomaygiat.com
Category : Kỹ Thuật Số