Giáo trình Lý thuyết truyền tin (Phần 2): Chương 4 - Mã hóa nguồn & kênh

Giáo trình về lý thuyết truyền tin phần 2, biên soạn theo chương trình đào tạo chuẩn, hệ thống hóa kiến thức từ cơ bản đến nâng cao.

• Trường học: Trường Đại Học Khoa Học Tự Nhiên
• Chuyên ngành: Lý Thuyết Truyền Tin
• Đề tài: Giáo Trình Lý Thuyết Truyền Tin Phần 2
• Loại tài liệu: Giáo Trình
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Mục lục chi tiết

• 4. CHƯƠNG 4: MÃ HÓA
• 4.1. Mục tiêu
• 4.2. MỞ ĐẦU
• 4.3. Một số khái niệm chung
• 4.3.1. Nguồn rời rạc
• 4.3.2. Nguồn liên tục
• 4.4. Mã hóa nguồn rời rạc không nhớ
• 4.4.1. Mã hóa nguồn rời rạc với từ mã có độ dài cố định
• 4.4.1.1. Với nguồn rời rạc đẳng xác suất
• 4.4.1.2. Với nguồn rời rạc không đẳng xác suất
• 4.4.2. Mã hóa nguồn rời rạc với từ mã có độ dài thay đổi
• 4.4.2.1. Khái niệm mã hóa thống kê tối ưu
• 4.4.2.2. Định lý về giới hạn trên và dưới của chiều dài trung bình từ mã
• 4.4.2.3. Mã thống kê tối ưu Shannon - Fano
• 4.4.2.4. Mã thống kê tối ưu Huffman
• 4.4.2.5. Kết luận
• 4.5. Mã hóa nguồn dừng rời rạc
• 4.6. MÃ HÓA KÊNH
• 4.6.1. Khái niệm
• 4.6.2. Nguyên tắc phát hiện lỗi và sửa lỗi
• 4.6.2.1. Nguyên tắc phát hiện lỗi của mã hiệu
• 4.6.2.2. Nguyên tắc sửa lỗi của mã hiệu
• 4.6.3. Khái niệm

Tóm tắt

I. Tổng quan các phương pháp mã hóa trong lý thuyết truyền tin

Trong hệ thống truyền tin, mã hóa là một quá trình biến đổi thông tin nhằm hai mục đích chính: tăng hiệu quả và độ tin cậy. Hiệu quả được thể hiện qua việc tăng tốc độ truyền tin, trong khi độ tin cậy liên quan đến khả năng chống lại nhiễu trên kênh truyền. Lý thuyết truyền tin phân chia quá trình này thành hai lĩnh vực riêng biệt nhưng bổ trợ cho nhau: mã hóa nguồn và mã hóa kênh. Mã hóa nguồn tập trung vào việc loại bỏ sự dư thừa trong thông tin gốc, nén dữ liệu để sử dụng tài nguyên kênh một cách tối ưu. Ngược lại, mã hóa kênh cố tình thêm vào thông tin một lượng dư thừa có kiểm soát để phía thu có thể phát hiện và sửa các lỗi phát sinh do nhiễu. Việc hiểu rõ bản chất và ứng dụng của từng phương pháp là nền tảng để xây dựng các hệ thống truyền thông hiện đại, từ mạng máy tính đến viễn thông di động. Mỗi phương pháp, từ mã hóa thống kê tối ưu như Huffman đến các mã chống nhiễu như Hamming, đều giải quyết những thách thức cụ thể trong việc truyền tải thông tin một cách nhanh chóng và chính xác.

1.1. Phân biệt mã hóa nguồn và mã hóa kênh trong truyền tin

Mã hóa nguồn và mã hóa kênh là hai phép biến đổi cơ bản trong một hệ thống truyền tin số. Mục tiêu của mã hóa nguồn, hay còn gọi là mã nén dữ liệu, là biểu diễn thông tin với số lượng bit tối thiểu. Phương pháp này khai thác các đặc tính thống kê của nguồn tin, chẳng hạn như xác suất xuất hiện không đồng đều của các ký hiệu, để loại bỏ độ dư thừa. Kết quả là tốc độ lập tin của nguồn được tăng lên, tiệm cận với thông lượng của kênh. Các kỹ thuật tiêu biểu bao gồm mã Huffman và mã Shannon-Fano. Ngược lại, mục tiêu của mã hóa kênh, hay mã chống nhiễu, là cải thiện độ tin cậy. Phép mã hóa này thêm vào chuỗi bit dữ liệu các bit kiểm tra theo một quy tắc nhất định. Lượng thông tin dư thừa này cho phép phía thu có thể phát hiện lỗi hoặc thậm chí sửa lỗi gây ra bởi nhiễu trên đường truyền, đảm bảo tính toàn vẹn của thông tin nhận được. Các loại mã phổ biến là mã Hamming, mã vòng (CRC) và mã tuyến tính.

1.2. Mục tiêu và vai trò của việc mã hóa dữ liệu hiệu quả

Mục tiêu cốt lõi của việc mã hóa là tối ưu hóa hai thông số đối nghịch: tốc độ và độ chính xác. Một hệ thống truyền tin lý tưởng phải truyền được lượng thông tin lớn nhất trong thời gian ngắn nhất với tỷ lệ lỗi thấp nhất có thể. Mã hóa nguồn đóng vai trò then chốt trong việc tăng tốc độ bằng cách giảm số bit trung bình cần thiết để biểu diễn một ký hiệu nguồn, giúp tiết kiệm băng thông và tài nguyên lưu trữ. Hiệu quả của phép mã hóa nguồn được đo bằng tỷ số giữa entropi của nguồn và độ dài trung bình của từ mã. Trong khi đó, mã hóa kênh đảm bảo độ chính xác bằng cách cung cấp một cơ chế bảo vệ dữ liệu trước các tác động của nhiễu. Theo định lý mã hóa kênh có nhiễu của Shannon, "nếu thông lượng kênh lớn hơn tốc độ lập tin của nguồn thì có thể truyền tin với sai số nhỏ tuỳ ý". Định lý này khẳng định vai trò nền tảng của các loại mã chống nhiễu, cho phép truyền tin cậy ngay cả trên các kênh không hoàn hảo.

II. Bí quyết nén dữ liệu hiệu quả với mã hóa nguồn tối ưu

Thách thức chính trong mã hóa nguồn là làm thế nào để biểu diễn một nguồn tin rời rạc với số lượng ký hiệu mã tối thiểu mà không làm mất thông tin. Giải pháp nằm ở các phương pháp mã hóa thống kê tối ưu. Các phương pháp này hoạt động dựa trên nguyên tắc rằng không phải tất cả các ký hiệu trong nguồn tin đều có tần suất xuất hiện như nhau. Bằng cách khai thác đặc tính thống kê này, một bộ mã hiệu quả sẽ được xây dựng. Cụ thể, các ký hiệu có xác suất xuất hiện cao sẽ được gán những từ mã ngắn, trong khi các ký hiệu ít xuất hiện hơn sẽ được gán những từ mã dài hơn. Cách tiếp cận này đảm bảo rằng độ dài trung bình từ mã là nhỏ nhất có thể, tiệm cận với giới hạn lý thuyết do entropi của nguồn đặt ra. Sự khác biệt giữa việc sử dụng từ mã có độ dài cố định và từ mã có độ dài thay đổi chính là chìa khóa để đạt được hiệu suất nén cao, đặc biệt đối với các nguồn tin không đẳng xác suất.

2.1. Nguyên tắc mã hóa thống kê tối ưu cho nguồn rời rạc

Nguyên tắc cơ bản của mã hóa thống kê tối ưu là thiết lập một sự tương ứng nghịch đảo giữa xác suất xuất hiện của một ký hiệu và độ dài của từ mã đại diện cho nó. Đối với một nguồn rời rạc không nhớ, trong đó các ký hiệu xuất hiện độc lập với nhau, mục tiêu là giảm thiểu giá trị n, tức độ dài trung bình từ mã, được tính bằng tổng Σ p(xi) * ni, trong đó p(xi) là xác suất của ký hiệu xi và ni là độ dài từ mã tương ứng. Định lý mã hóa nguồn của Shannon đã chứng minh rằng giới hạn dưới của n chính là entropi của nguồn, H(X). Một bộ mã được coi là tối ưu khi n xấp xỉ H(X). Để đạt được điều này, các thuật toán như mã Huffman và mã Shannon-Fano được sử dụng để xây dựng các bộ mã có tính tiền tố (prefix code), đảm bảo việc giải mã là duy nhất và không nhập nhằng.

2.2. So sánh mã hóa độ dài cố định và độ dài thay đổi

Mã hóa độ dài cố định gán cho mỗi ký hiệu nguồn một từ mã nhị phân có độ dài n không đổi. Phương pháp này đơn giản và hiệu quả đối với các nguồn đẳng xác suất, nơi H(X) đạt giá trị cực đại. Tuy nhiên, khi nguồn không đẳng xác suất, mã hóa độ dài cố định trở nên lãng phí vì nó không tận dụng được thông tin về tần suất xuất hiện của các ký hiệu. Ngược lại, mã hóa độ dài thay đổi là giải pháp tối ưu cho trường hợp này. Bằng cách sử dụng các từ mã ngắn cho ký hiệu thường gặp và từ mã dài cho ký hiệu hiếm gặp, nó làm giảm đáng kể độ dài trung bình từ mã. Ví dụ, trong văn bản tiếng Anh, ký tự 'e' (xuất hiện nhiều) có thể được mã hóa bằng 3 bit, trong khi ký tự 'z' (xuất hiện ít) có thể cần đến 11 bit. Các phương pháp mã hóa thống kê tối ưu như Huffman đều thuộc loại này và mang lại hiệu suất nén vượt trội.

III. Hướng dẫn chi tiết các thuật toán mã hóa thống kê tối ưu

Để hiện thực hóa nguyên tắc mã hóa thống kê tối ưu, nhiều thuật toán đã được phát triển. Trong số đó, mã Shannon-Fano và mã Huffman là hai phương pháp kinh điển dành cho các nguồn tin có phân bố xác suất đã biết. Cả hai đều nhằm mục đích xây dựng một bộ mã tiền tố với độ dài trung bình từ mã nhỏ nhất. Tuy nhiên, chúng khác nhau về cách tiếp cận: Shannon-Fano sử dụng chiến lược chia để trị (top-down), trong khi Huffman áp dụng phương pháp kết hợp từ dưới lên (bottom-up), đảm bảo tính tối ưu tuyệt đối. Bên cạnh đó, đối với các nguồn mà tính chất thống kê không được biết trước hoặc thay đổi theo thời gian, thuật toán Lempel-Ziv cung cấp một giải pháp thích ứng hiệu quả. Thuật toán này không dựa vào xác suất mà xây dựng một từ điển các chuỗi ký hiệu lặp lại ngay trong quá trình mã hóa, trở thành nền tảng cho nhiều công cụ nén dữ liệu phổ biến hiện nay.

3.1. Các bước xây dựng bộ mã Shannon Fano và ưu nhược điểm

Thuật toán mã Shannon-Fano được xây dựng dựa trên nguyên tắc chia đôi. Quy trình thực hiện gồm các bước: (1) Sắp xếp các ký hiệu nguồn theo thứ tự xác suất giảm dần. (2) Chia tập ký hiệu thành hai nhóm sao cho tổng xác suất của mỗi nhóm gần bằng nhau nhất có thể. (3) Gán bit '0' cho nhóm đầu tiên và '1' cho nhóm thứ hai. (4) Lặp lại các bước 2 và 3 cho từng nhóm con cho đến khi mỗi nhóm chỉ còn một ký hiệu. (5) Từ mã của mỗi ký hiệu là chuỗi các bit được gán trong quá trình phân chia. Ưu điểm của phương pháp này là đơn giản và trực quan. Tuy nhiên, nhược điểm lớn là bộ mã tạo ra không phải lúc nào cũng tối ưu và không duy nhất, do việc chia nhóm "gần bằng nhau" có thể có nhiều cách thực hiện khác nhau, dẫn đến các bộ mã có hiệu suất mã khác nhau.

3.2. Kỹ thuật tạo mã Huffman Tối ưu độ dài trung bình từ mã

Mã Huffman là một thuật toán tham lam tạo ra bộ mã tiền tố tối ưu, nghĩa là không có bộ mã tiền tố nào khác có độ dài trung bình từ mã nhỏ hơn. Các bước thực hiện như sau: (1) Liệt kê tất cả các ký hiệu theo xác suất giảm dần. (2) Chọn hai ký hiệu có xác suất nhỏ nhất và kết hợp chúng thành một ký hiệu mới có xác suất bằng tổng hai xác suất. (3) Gán bit '0' và '1' cho hai nhánh nối đến hai ký hiệu này. (4) Lặp lại quá trình trên với danh sách ký hiệu mới cho đến khi chỉ còn một ký hiệu duy nhất (gốc của cây). (5) Đọc từ mã cho mỗi ký hiệu bằng cách đi từ gốc đến lá tương ứng. Mã Huffman luôn đảm bảo tính tối ưu và được chứng minh thỏa mãn bất đẳng thức Kraft. Nhược điểm của nó là yêu cầu phải biết trước toàn bộ phân bố xác suất của nguồn tin và cần phải truyền bảng mã kèm theo dữ liệu nén.

3.3. Thuật toán Lempel Ziv cho mã hóa nguồn dừng rời rạc

Khác với các phương pháp thống kê, thuật toán Lempel-Ziv (LZ) hoạt động mà không cần biết trước xác suất của nguồn. Đây là một phương pháp mã hóa dựa trên từ điển. Nguyên tắc của nó là phân tích chuỗi dữ liệu đầu vào thành các khối (câu) có độ dài thay đổi. Khi một chuỗi ký hiệu mới xuất hiện, nó sẽ được thêm vào từ điển. Để mã hóa một câu mới, thuật toán chỉ cần trỏ đến vị trí của một câu đã có trong từ điển và thêm vào ký hiệu cuối cùng. Ví dụ, chuỗi 101011 có thể được chia thành 1, 0, 10, 11. Câu 10 được tạo từ câu 1 (đã có) cộng thêm 0. Do đó, thay vì mã hóa toàn bộ chuỗi, ta chỉ cần lưu vị trí của 1 và ký hiệu 0. Thuật toán này rất hiệu quả cho việc nén dữ liệu các tệp lớn có nhiều cấu trúc lặp lại và là nền tảng của các định dạng nén phổ biến như GZIP, PNG và các tiện ích compress trong UNIX.

IV. Cách tăng độ tin cậy truyền tin với các loại mã chống nhiễu

Khi thông tin được truyền qua một kênh vật lý, nó không tránh khỏi bị tác động bởi nhiễu, gây ra các lỗi bit. Để đối phó với thách thức này, mã hóa kênh hay mã chống nhiễu được sử dụng. Nguyên lý cốt lõi là thêm vào dữ liệu gốc một lượng thông tin dư thừa có cấu trúc. Lượng dư thừa này không mang thông tin mới mà đóng vai trò như các bit kiểm tra. Tại phía thu, bộ giải mã sẽ sử dụng các bit này để kiểm tra tính toàn vẹn của dữ liệu nhận được. Nếu phát hiện có sự mâu thuẫn, nó có thể thực hiện phát hiện lỗi và yêu cầu truyền lại, hoặc trong các hệ thống phức tạp hơn, nó có thể tự động sửa lỗi. Các loại mã như mã tuyến tính và mã vòng (CRC) cung cấp các phương pháp toán học chặt chẽ để tạo ra và giải mã các từ mã này một cách hiệu quả, giúp giảm đáng kể tỷ lệ lỗi bit và tăng cường độ tin cậy của toàn hệ thống truyền tin.

4.1. Nguyên tắc phát hiện và sửa lỗi trong mã hóa kênh

Nguyên tắc của việc phát hiện lỗi dựa trên việc chỉ sử dụng một tập con các chuỗi bit có thể có. Các chuỗi bit hợp lệ được gọi là "từ mã", còn lại là các "tổ hợp cấm". Khi một từ mã bị nhiễu làm thay đổi và biến thành một tổ hợp cấm, phía thu sẽ biết rằng đã có lỗi xảy ra. Khả năng sửa lỗi phức tạp hơn. Nó đòi hỏi bộ mã phải được thiết kế sao cho mỗi từ mã khi bị sai sẽ chuyển thành các tổ hợp cấm riêng biệt, không trùng lặp với các tổ hợp cấm của từ mã khác. Khi nhận được một tổ hợp cấm, bộ giải mã sẽ quy nó về từ mã "gần nhất" theo một tiêu chuẩn khoảng cách, thường là khoảng cách Hamming (số vị trí bit khác nhau). Một bộ mã có khả năng sửa được t lỗi nếu khoảng cách Hamming tối thiểu giữa hai từ mã bất kỳ ít nhất là 2t + 1.

4.2. Phân tích mã tuyến tính và vai trò của ma trận kiểm tra

Mã tuyến tính là một lớp mã khối quan trọng trong đó tổng (theo modulo 2) của hai từ mã bất kỳ cũng là một từ mã. Tính chất tuyến tính này cho phép biểu diễn và xử lý mã một cách hiệu quả bằng đại số tuyến tính, đặc biệt là ma trận. Quá trình mã hóa được thực hiện bằng phép nhân vector tin i với ma trận sinh G để tạo ra từ mã C = iG. Ở phía thu, việc kiểm tra lỗi được thực hiện bằng ma trận kiểm tra chẵn lẻ H. Một vector x nhận được là một từ mã hợp lệ khi và chỉ khi xH^T = 0. Nếu kết quả khác 0, giá trị này được gọi là hội chứng (syndrome) S(x) = xH^T. Hội chứng không chỉ cho biết có lỗi xảy ra mà còn chứa thông tin về vị trí của lỗi, giúp cho việc sửa lỗi trở nên khả thi.

4.3. Tìm hiểu mã vòng CRC và cơ chế tạo đa thức sinh

Mã vòng (Cyclic Redundancy Check - CRC) là một phân lớp đặc biệt của mã tuyến tính với thêm một tính chất: một dịch chuyển vòng của một từ mã cũng là một từ mã. Đặc tính này cho phép chúng được biểu diễn và thực thi dễ dàng bằng các đa thức và các mạch ghi dịch phần cứng. Mỗi mã vòng được định nghĩa bởi một đa thức sinh g(x). Một chuỗi bit được xem là một từ mã hợp lệ nếu đa thức tương ứng của nó chia hết cho g(x). Quá trình mã hóa bao gồm việc tính toán số dư của phép chia đa thức tin (đã nhân với x^(n-k)) cho g(x). Số dư này chính là các bit kiểm tra CRC được gắn vào cuối bản tin. CRC cực kỳ hiệu quả trong việc phát hiện lỗi chùm (burst errors) và được sử dụng rộng rãi trong các giao thức mạng như Ethernet và các hệ thống lưu trữ.

V. Ứng dụng thực tiễn của mã Hamming và mã kiểm tra chẵn lẻ

Trong các hệ thống số, việc đảm bảo tính toàn vẹn dữ liệu là yêu cầu bắt buộc. Hai trong số các kỹ thuật mã chống nhiễu được ứng dụng sớm và rộng rãi nhất là mã kiểm tra chẵn lẻ (Parity Check) và mã Hamming. Mã Parity là phương pháp đơn giản nhất để phát hiện lỗi, thường được dùng trong truyền dữ liệu không đồng bộ như giao thức RS-232. Mặc dù có hạn chế, nó vẫn là một giải pháp hiệu quả về chi phí cho các ứng dụng cơ bản. Ở một cấp độ cao hơn, mã Hamming không chỉ phát hiện mà còn có khả năng sửa lỗi đơn một cách hiệu quả. Nhờ cấu trúc toán học chặt chẽ và sơ đồ giải mã đơn giản, mã Hamming đã trở thành một lựa chọn phổ biến trong các hệ thống bộ nhớ máy tính (ví dụ: RAM ECC) và các ứng dụng truyền thông yêu cầu độ tin cậy cao mà không cần cơ chế truyền lại phức tạp.

5.1. Cơ chế hoạt động của mã kiểm tra chẵn lẻ Parity Check

Mã kiểm tra chẵn lẻ hoạt động bằng cách thêm một bit duy nhất, gọi là bit Parity, vào cuối mỗi từ dữ liệu (ví dụ, một byte). Giá trị của bit này được chọn để tổng số bit '1' trong từ mã cuối cùng là một số chẵn (Parity chẵn) hoặc một số lẻ (Parity lẻ). Tại phía thu, mạch kiểm tra sẽ đếm lại số bit '1'. Nếu tổng số bit '1' không khớp với quy ước chẵn/lẻ đã định, một lỗi được phát hiện. Ví dụ, trong bộ mã ASCII 7 bit, một bit thứ 8 thường được dùng làm bit Parity. Hạn chế chính của phương pháp này là nó chỉ có thể phát hiện một số lẻ các lỗi bit (1, 3, 5,...). Nếu có một số chẵn lỗi xảy ra, Parity vẫn đúng và lỗi không bị phát hiện. Mặc dù vậy, sự đơn giản của nó làm cho nó hữu ích cho việc kiểm tra lỗi nhanh chóng.

5.2. Khả năng sửa lỗi đơn của mã Hamming trong hệ thống số

Mã Hamming là một loại mã tuyến tính hoàn hảo, được thiết kế để phát hiện tối đa hai lỗi bit và sửa lỗi đơn. Đặc điểm của mã này là số bit kiểm tra r và số bit tin k tuân theo hệ thức k ≤ 2^r - 1 - r. Các bit kiểm tra được đặt vào các vị trí là lũy thừa của 2 (1, 2, 4, 8,...). Mỗi bit kiểm tra sẽ kiểm tra chẵn lẻ cho một tập hợp các bit dữ liệu cụ thể. Khi giải mã, phía thu sẽ tính toán lại các bit kiểm tra. Kết quả tính toán (gọi là hội chứng) sẽ tạo thành một số nhị phân. Nếu hội chứng bằng 0, không có lỗi. Nếu khác 0, giá trị thập phân của hội chứng này chỉ chính xác vị trí của bit bị lỗi. Bằng cách đảo bit tại vị trí đó, lỗi được sửa chữa. Đây là cơ chế sửa lỗi chuyển tiếp (FEC) hiệu quả, được sử dụng rộng rãi trong bộ nhớ ECC (Error-Correcting Code).

Trích đoạn nội dung tài liệu

MỞ ĐẦU Hệ thống truyền tin được sử dụng để truyền thông tin từ nguồn tin đến nơi nhận tin. Nguồn tin có thể có nhiều dạng, trong hệ thống radio, nguồn tin là nguồn âm thanh (tiếng nói hay âm nhạc); trong hệ thống truyền hình, nguồn tin là nguồn video, nó tạo ra các hình ảnh chuyển động. Những nguồn như thế được gọi là nguồn tương tự. Ngược lại, máy tính tạo ra và sử dụng các tín hiệu rời rạc (các số nhị phân hay các chữ cái trong bảng mã ASCH) được gọi là nguồn rời rạc.

Hệ thống truyền tin rời rạc, khi truyền các tín hiệu liên tục thường phải thông qua một số phép biến đổi rời rạc (rời rạc hóa, lượng tử hóa) để đổi thành tín hiệu số (thường là nhị phân) rồi mã hóa. Ở đầu thu tín hiệu phải thông qua một số phép biến đổi ngược lại như giải mã, liên tục hóa, để phục hồi tin tức. Sự mã hóa tin tức nhằm mục đích tăng tính hiệu quả và độ tin cậy của hệ thống truyền tin, nghĩa là tăng tốc độ truyền tin và khả năng chống nhiễu của tín hiệu khi truyền qua kênh. Thông thường tốc độ lập tin của nguồn thường còn rất xa mới đạt được thông lượng của kênh.

Để tăng tốc độ lập tin, người ta 64 dùng phép mã hóa để thay đổi tính chất thống kê, làm giảm độ dư của thông tin không cần thiết của nguồn nhờ đó tiếp cận với thông lượng của kênh. Các phương pháp mã loại này gọi là mã hóa nguồn. Mặt khác, các tin mang các mã hiệu khi truyền trong kênh thường bị nhiễu phá hoại. Vì vậy, mã hiệu phải được xây đựng theo những quy tắc nhất định nhằm đảm bảo cho phía thu phát hiện được các sai nhầm đồng thời sửa được chúng.

Loại mã hóa này được gọi là mã hóa kênh còn được gọi là mã chống nhiễu. Mã hóa kênh nhằm cải tiến kỹ thuật truyền tin, cho phép tín hiệu phát đi có khả năng chống lại ảnh hưởng của nhiễu. Mã hóa kênh làm giảm lỗi bit hoặc giảm tỷ số năng lượng bit trên mật độ nhiễu tại đầu thu. Một số khái niệm chung Mã hóa nguồn là phép biến đổi đầu tiên cho nguồn nguyên thủy, đầu vào của phép biến đổi này có thể là nguồn tin rời rạc hoặc nguồn tin nguyên thủy.

Trong cả hai trường hợp mục đích chính của phép mã hóa nguồn là biểu điễn thông tin với tài nguyên tối thiểu. Các vấn để cần nghiên cứu đối với mã hóa nguồn là: mã hóa nguồn liên tục, mã hóa nguồn rời rạc và nén dữ liệu. Nguồn rời rạc - Nguồn rời rạc tạo ra các tin rời rạc thể hiện là chuỗi các ký hiệu ngẫu nhiên. - Đối với mã hóa nguồn rời rạc, vấn đề cơ bản là thay đổi bảng chữ cái và phân bố xác suất để giảm bớt lượng ký hiệu cần dùng.

Như vậy cần quan tâm: + Entropi của nguồn trước khi mã hóa + Entropi 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 phép mã hóa - Đối với nguồn rời rạc không nhớ: sử dụng từ mã có độ đài cố định hoặc từ mã có độ đài thay đổi. - Đối với nguồn đừng rời rạc: thường sử dụng thuật toán mã hoá nguồn Lempel-Ziv. Nguồn liên tục - Nguồn liên tục tạo ra tín hiệu liên tục thể hiện một quá trình ngẫu nhiên liên tục. Trong các hệ thống truyền thông, nguồn liên tục thường được biến đổi thành nguồn rời rạc, xử lý và truyền rồi ở đầu nhận lại biến đổi 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ương tự: biến đổi nguồn tương tự thành một chuỗi các giá trị ngẫu nhiên liên tục tại các thời điểm lấy mẫu. + Lượng tử hóa nguồn tương tự: mã hóa các giá trị liên tục bằng nguồn rời Tạc. - Tại đích, nguồn rời rạc được tổng hợp thành nguồn tương tự, cụ thể là: + Tái tạo lại các giá trị liên tục của chuỗi giá trị ban đầ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 quá trình lượng tử, đầu ra sai khác so với đầu vào gọi là sai số lượng tử. ~ Người ta thường sử dụng các kỹ thuật: mã hóa miền thời gian, mã hóa miễn tần số, mã hóa mô hình nguồn để mã hóa nguồn liên tục. Trong mục này chúng ta chỉ khảo sát phương pháp mã hóa nguồn rời rạc. Mã hoá nguồn rời rạc không nhớ 2.

Mã hóa nguồn rời rạc với từ mã có độ dài cố định Nguyên tắc: mã hóa một ký hiệu nguồn bằng một chuỗi ký hiệu mã có độ đài n. Để đảm bảo phép mã hóa là một - một thì một ký hiệu nguồn ứng với một chuỗi ký hiệu nhị nhân, số lượng chuỗi ký hiệu nhị phân phải lớn hơn số ký hiệu nguồn. 2'>Lhayn>log;L (4-1) Nếu L là luỹ thừa của 2 thì giá trị nhỏ nhất của R là log;L. Nếu L không phải là luỹ thừa của 2 thì giá trị của n = [log;L]+1.

66 Hiệu quả của phép mã hóa được xác định bằng: k- ZŒU, (4-2) n 2. Với nguồn rời rạc đẳng xác suất - Hiệu quả của mã hóa đạt giá trị cực đại (bằng 1) khi L. là luỹ thừa của 2 - Nếu nguồn tin ban đầu đẳng xác suất nhưng L. không phải là luỹ thừa của 2 thì n sai khác HỢX) tối đa là ! bi/ký hiệu.

Khi logạL >>l thì phương pháp mã hóa này có hiệu quả cao. Ngược lại, khi log; L < 1 thì hiệu quả của phương pháp mã hóa với độ dài cố định có thể nâng lên bằng cách mã hóa từng khối gém J ky hiệu nguồn. Để mã hoá này duy nhất, ta cần L từ mã, nếu gọi N là số ký hiệu mã được sử dụng để mã hóa thì giá trị nguyên nhỏ nhất có thể chấp nhận của N là N = [Jlog;L] +1. Khi đó, số ký hiệu mã trung bình ứng với một ký hiệu nguồn là ø = ` „ độ không tối ưu của mã giảm xuống xấp xỉ 7 SƠ VỚI việc mã hóa riêng từng ký hiệu nguồn.

Khi J đủ lớn, hiệu quả của phương pháp JH(X) được đo bằng tỷ số rất gan tdi 1. N - Các phương pháp trên không bị sai số, mỗi chuỗi ký hiệu nguồn luôn ứng với một từ mã duy nhất. Với nguồn rời rạc không đẳng xác suất - Trong trường hợp nguồn không đẳng xác suất, để có thể tiếp cận với hiệu quả tối đa (bằng 1) bằng cách giảm n, cần chấp nhận một sai số nào đó. Ví dụ chỉ một phần trong LỊ khối ký hiệu được mã hóa một cách duy nhất còn Ì.ƒ — (2N —1) khối ƒ ký hiệu được mã hóa thành một từ mã đuy nhất.

Phương pháp mã hóa này gây ra việc giải mã sai đối với các khối có xác suất xuất hiện thấp, gọi P, là xác suất giải mã sai. - Dựa trên phương pháp mã hóa này Shannon đã chứng minh định lý mã hóa nguồn như sau: “ Gọi Xà một nguồn rời rạc không nhớ có emropi hữu hạn HỊ(X). Các khối J ký hiệu của nguồn được mã hóa thành các từ mã nhị phản có độ dài N. Với moi > 0, xác suất giải mã khối sai P, có thể nhỏ tuỳ § nếu: n=À >H(X)+e J 67 Ngược lại, nếu: n= Z<H0+e thì P, dân tdi1 khiJ tiến tới vô hạn.

” - Từ định lý này ta thấy số lượng nhị phân trung bình để mã hóa cho một nguồn rời rạc không nhớ với xác suất giải mã sai nhỏ tuỳ ý bị chặn dưới bởi entropi H(X). Ngược lại nếu n < H(X) thì xác suất giải sai tiến tới 100% khi J tăng tới vô hạn. Ma hóa nguồn rời rạc với từ mã có độ dài thay đổi Mã hoá nguồn sử dụng với từ mã có độ dài thay đổi thường sử dụng phương pháp mã hóa thống kê tối ưu. Khái niệm mã hoá thống kê tối tu Mục tiêu của mã hoá thống kê tối ưu là mã hóa tin rời rạc với số lượng các ký hiệu mã nhị phân tối thiểu.

Do đó mã hóa thống kê tối ưu thuộc loạì mã nén dữ liệu. Phương pháp mã hóa này khai thác đặc tính: không phải tất cả các ký hiệu trong một frame truyền có cùng tần suất xuất hiện, ví dụ trong cùng một chuỗi ký tự, sẽ có một số ký tự xuất hiện nhiều hơn các ký tự khác. Thay vì đùng một số bit nhất định mã hoá một ký tự, chúng ta dùng các từ mã có độ dài nhỏ để mã hoá các ký tự có xác suất xuất hiện cao và ngược lại. Như vậy, số ký hiệu cần thiết để mã hoá cho chuỗi ký tự sẽ nhỏ hơn và tính kinh tế cũng cao hơn.

Vi du: ky ty a, b xuất hiện nhiều nên dùng 1 bit để mã hoá, ký tự z xuất hiện ít có thể dùng 10 bit để mã hóa. Tiêu chuẩn của mã thống kê tối ưu đạt đến là độ đài trung bình từ mã là nhỏ nhất. Một nguồn tín liên tục sau khi được rời rạc hóa, hoặc một nguồn tin rời rạc hóa đều được mô tả bằng cấu trúc thống kê của chúng. Trường hợp các lớp tin trong nguồn xuất hiện độc lập thống kê với nhau, sự mô tả nguồn tin được đơn giản hóa đi rất nhiêu, lúc đó chỉ cần nêu quy luật phân bố xác suất xuất hiện của các ký hiệu trong bộ mã là đủ.

Thông thường quy luật phân bố xác suất xuất hiện của các ký hiệu không đều, lúc đó nhiệm vụ của phép mã hoá nguồn rời rạc là mã hóa sao cho độ dài trung bình của từ mã là nhỏ nhất. Cụ thể là đùng những từ mã ngắn cho các ký hiệu mã có xác suất xuất hiện lớn và ngược lại mã hóa các ký hiệu ít xuất hiện bằng những từ mã dài. 68 Mã hóa thống kê tối ưu có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng trên các mảng nhỏ hơn 64KB. Nhược điểm của nó là phải chứa cả bảng mã vào tệp tin nén thì phía nhận mới có thể giải mã được, do đó hiệu suất nén chỉ cao khi thực hiện các tệp tin lớn.

Định lý về giới hạn trên và dưới của chiêu dài trung bình từ mã Định lý này phát biểu như sau: Gọi X = {x}, các xác suất xuất hiện tương ứng p(x,) là nguồn rời rạc không nhớ với emropi hữm hạn H(X).