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).

Nội dung chính

TỔNG QUAN HỌC THUẬT VÀ NỘI DUNG GIÁO TRÌNH LÝ THUYẾT TRUYỀN TIN VÀ ĐIỀU CHẾ TÍN HIỆU

---

Tổng quan về giáo trình

Giáo trình thuộc khối kiến thức cơ sở ngành và chuyên ngành trong chương trình đào tạo Cử nhân, Kỹ sư và Học viên Cao học thuộc các lĩnh vực Kỹ thuật Điện tử - Viễn thông, Công nghệ Thông tin, Kỹ thuật Mạng và Truyền thông dữ liệu. Vị trí môn học đóng vai trò cầu nối trung gian giữa khối kiến thức toán học cơ sở (Xác suất thống kê, Đại số tuyến tính) và các môn học ứng dụng chuyên sâu (Hệ thống viễn thông số, Xử lý tín hiệu số, Mạng máy tính).

Mục tiêu học tập (Learning Outcomes) của giáo trình được xác định cụ thể:

• Về kiến thức: Trang bị lý thuyết hoàn chỉnh về hệ thống truyền tin rời rạc và liên tục; cơ chế mã hóa nguồn và mã hóa kênh; các kỹ thuật điều chế cao tần, điều chế xung và điều chế khóa dịch; hiểu rõ các định lý Shannon về giới hạn truyền tin qua kênh có nhiễu.
• Về kỹ năng phân tích: Khả năng tính toán các tham số thống kê (Entropi, hiệu suất mã hóa, tỷ số $E_b/N_0$, xác suất lỗi bit BER); phân tích cấu trúc ma trận sinh và ma trận kiểm tra trong các bộ mã phát hiện/sửa sai.
• Về kỹ năng ứng dụng: Thiết kế thuật toán nén dữ liệu tối ưu; thực hiện quy trình mã hóa và giải mã các hệ thống mã khối, mã vòng CRC, mã Hamming; thiết lập sơ đồ khối chức năng của mạch điều chế và giải điều chế tín hiệu.

Cấu trúc giáo trình tiếp cận theo mô hình phân lớp xử lý thông tin từ đầu phát (Transmitter) đến đầu thu (Receiver), bám sát sơ đồ khối chuẩn của hệ thống truyền dẫn số. Điểm đặc sắc mang tính học thuật của tài liệu là sự kết hợp chặt chẽ giữa mô hình toán học giải tích, lý thuyết đại số tuyến tính với cấu trúc mạch phần cứng thực thi (thanh ghi dịch, cổng logic modulo-2, bộ dao động điều khiển điện áp VCO, vòng khóa pha PLL).

---

Nội dung kiến thức cốt lõi

+-----------------------------------------------------------------------------+
|               MÔ HÌNH HỆ THỐNG TRUYỀN TIN VÀ NỘI DUNG CỐT LÕI              |
+-----------------------------------------------------------------------------+
|                                                                             |
|  [ NGUỒN TIN ] ---> [ MÃ HÓA NGUỒN ] --------> [ MÃ HÓA KÊNH ]             |
|   (Rời rạc/          - Độ dài cố định / thay đổi  - Parity / Khối BCC       |
|    Liên tục)         - Shannon-Fano / Huffman     - Tuyến tính G, H         |
|                      - Nén từ điển Lempel-Ziv     - Mã vòng CRC, Hamming    |
|                                                          |                  |
|                                                          v                  |
|  [ NƠI NHẬN ] <--- [ GIẢI ĐIỀU CHẾ ] <-------- [ ĐIỀU CHẾ TÍN HIỆU ]        |
|                     - Tách hình bao, PLL         - Cao tần: AM, FM, PM      |
|                     - Khôi phục xung             - Xung: PAM, PWM, PPM, PCM |
|                     - Giải khóa dịch             - Khóa dịch: ASK, FSK, PSK |
|                                                                             |
+-----------------------------------------------------------------------------+

Các chương và chủ đề chính

Nội dung giáo trình được tổ chức tuần tự theo chu trình xử lý và bảo toàn thông tin:

• Chương II: Lý thuyết thông tin và Giới hạn kênh truyền: Trình bày định lý Shannon về kênh truyền có nhiễu, xác lập điều kiện biên: nếu thông lượng kênh $C$ lớn hơn tốc độ lập tin của nguồn $R$, hệ thống có thể truyền tin với xác suất sai số nhỏ tùy ý ($P_e \to 0$).
• Chương IV: Mã hóa:
  • Mã hóa nguồn rời rạc không nhớ: Phương pháp dùng từ mã có độ dài cố định $n \ge \log_2 L$ và độ dài thay đổi dựa trên phân bố xác suất; Định lý giới hạn chặn trên và chặn dưới của chiều dài từ mã trung bình: $H(X) \le \bar{n} < H(X) + 1$; Thuật toán mã hóa thống kê tối ưu Shannon - Fano và Huffman; Thử bất đẳng thức Kraft $\sum_{k=1}^L 2^{-n_k} \le 1$ xác định tính chất tiền tố (prefix code).
  • Mã hóa nguồn dừng rời rạc: Thuật toán nén dữ liệu từ điển động Lempel-Ziv, cơ chế tách chuỗi ký hiệu thành các "câu" và biểu diễn bằng địa chỉ từ điển.
  • Mã hóa kênh (Mã chống nhiễu): Khái niệm tổ hợp mã mang tin và tổ hợp cấm; Phương pháp kiểm tra Parity chẵn/lẻ theo ký tự (ASCII 7 bit + 1 bit kiểm tra) và ma trận khối BCC; Mã khối tuyến tính $C(n,k)$ với ma trận sinh $G = [I_k | P]$ và ma trận kiểm tra $H = [P^T | I_{n-k}]$, véc tơ hội chứng (Syndrome) $S(x) = x \cdot H^T$, mối liên hệ giữa khoảng cách mã cực tiểu $d_{min}$ và trọng lượng Hamming; Mã vòng kiểm tra CRC với đa thức sinh $g(x)$ là ước số của $x^n+1$, mạch phần cứng thanh ghi dịch và các chuẩn CRC-12, CRC-16, CRC-CCITT; Mã chống nhiễu Hamming sửa sai 1 bit với điều kiện $k \le 2^r - 1 - r$.
• Chương V: Điều chế tín hiệu:
  • Khái niệm và sự cần thiết của điều chế: Dịch chuyển phổ tần số thấp của tín hiệu mang tin $s(t)$ (tiếng nói 300–3400 Hz, truyền hình 25 Hz–6.5 MHz) lên miền tần số cao của tải tin $u(t)$ để bức xạ qua anten hoặc tương thích với băng thông mạng PSTN.
  • Điều chế cao tần tín hiệu liên tục: Điều biên (AM), điều tần (FM), điều pha (PM); Cơ chế giải điều chế tách hình bao bằng mạch diode-RC với hằng số phóng $\tau = RC$, mạch giải điều tần bằng vòng khóa pha PLL (Phase Locked Loop) và bộ dao động LC điều khiển bằng biến dung (VCO).
  • Điều chế xung: Điều chế biên độ xung (PAM) theo định lý lấy mẫu Shannon ($f_s \ge 2 f_{max}$); Điều chế pha xung (PPM); Điều chế độ rộng xung (PWM); Điều chế tần số xung (PFM); Điều chế xung mã (PCM) gồm 3 giai đoạn: Lấy mẫu $\to$ Lượng tử hóa $\to$ Mã hóa nhị phân.
  • Điều chế khóa dịch truyền số liệu: Khóa dịch biên độ (ASK), khóa dịch tần số (FSK), khóa dịch pha (PSK), và điều chế biên độ cầu phương (QAM) ứng dụng trong Modem máy tính và truyền hình cáp CATV.

Kiến thức nền tảng được xây dựng

Giáo trình xây dựng hệ thống lý thuyết dựa trên 3 trụ cột toán học và kỹ thuật:

1. Lý thuyết xác suất và thống kê: Sử dụng khái niệm Entropi nguồn $H(X) = -\sum p(x_i) \log_2 p(x_i)$, mô hình phân bố xác suất không đều để rút gọn chiều dài từ mã trung bình $\bar{n} = \sum p(x_i) n_i$, và đánh giá hiệu suất mã $K = H(X)/\bar{n}$.
2. Đại số trừu tượng và Đại số tuyến tính: Ứng dụng không gian véc tơ nhị phân, phép toán cộng modulo-2 ($\oplus$), lý thuyết ma trận đối ngẫu ($G \cdot H^T = 0$), và đại số đa thức trường hữu hạn trong mã hóa vòng ($c(x) = b(x) + u(x) \cdot x^{n-k}$).
3. Lý thuyết tín hiệu và hệ thống: Biểu diễn tín hiệu trong miền thời gian và miền tần số; lý thuyết lấy mẫu Nyquist-Shannon; cơ chế phi tuyến và phân tích hình bao tín hiệu.

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Thực hiện tính toán mã hóa và giải mã thủ công hoặc lập trình cho các giải thuật Shannon - Fano, Huffman, Lempel-Ziv; thiết lập bảng mã và sơ đồ cây mã; tính toán tham số phần cứng bộ lọc tách sóng hình bao và mạch tạo mã CRC.
• Kỹ năng phân tích (Analytical skills): Khả năng định vị lỗi thông qua véc tơ sai $e$ và hội chứng Syndrome $S(x)$; phân biệt các loại lỗi độc lập và lỗi chùm; so sánh hiệu suất phổ và khả năng kháng nhiễu giữa các kỹ thuật điều chế tương tự và điều chế số.
• Năng lực thực tiễn (Practical competencies): Đọc hiểu và thiết kế cấu trúc khung truyền dẫn (frame); tích hợp giải thuật kiểm soát lỗi vào các giao thức truyền thông mạng và hệ thống nhúng vi xử lý.

---

Phương pháp giảng dạy và học tập

+-----------------------------------------------------------------------------+
|                  QUY TRÌNH TIẾP CẬN VÀ THỰC HÀNH HỌC TẬP                    |
+-----------------------------------------------------------------------------+
|                                                                             |
|  [ Lý thuyết nền tảng ] ---> Xác lập định lý, mô hình toán, không gian mã   |
|            |                                                                |
|            v                                                                |
|  [ Bài tập mẫu định lượng ] -> Thuật toán Shannon-Fano, Huffman, CRC, PCM   |
|            |                                                                |
|            v                                                                |
|  [ Mô phỏng & Ứng dụng ] --> Thiết kế mạch ghi dịch, ma trận Syndrome       |
|            |                                                                |
|            v                                                                |
|  [ Đánh giá năng lực ] ----> Giải quyết bài toán tối ưu và sửa sai kênh     |
|                                                                             |
+-----------------------------------------------------------------------------+

Phương pháp tiếp cận sư phạm (Pedagogical approach)

Giáo trình áp dụng phương pháp suy diễn kết hợp thực nghiệm: Đi từ việc đặt vấn đề kỹ thuật thực tế (suy hao tín hiệu, giới hạn thông lượng, tạp âm kênh truyền), khái quát hóa thành mô hình toán học giải tích, và cuối cùng hiện thực hóa bằng sơ đồ thuật toán và sơ đồ khối mạch logic.

Bài tập và ví dụ tính toán mẫu (Practical exercises)

Tài liệu cung cấp chuỗi bài tập và ví dụ định lượng chi tiết:

• Ví dụ mẫu mã hóa nguồn: Phân bổ xác suất cho nguồn tin 8 ký hiệu $X = {x_1, \dots, x_8}$, giải thuật chia nhóm mã Shannon - Fano đạt hiệu suất $K = 100%$, giải thuật ghép nút Huffman đạt hiệu suất $K = 97.4%$.
• Ví dụ mẫu mã hóa kênh:
  • Tạo từ mã và ma trận kiểm tra cho mã Hamming $C(7,4)$, xác định vị trí lỗi thông qua giá trị thập phân của hội chứng Syndrome $S(x)$.
  • Thực hiện phép chia đa thức tạo mã vòng $C(7,4)$ với đa thức sinh $g(x) = x^3 + x + 1$ để mã hóa bản tin $u(x) = 1010$ thành từ mã $c(x) = 1010011$.
  • Quy trình giải mã mã vòng bị lỗi tại từ mã nhận $1000011$ qua phép chia đa thức lấy phần dư đối chiếu ma trận sửa sai $M$.
• Hệ thống bài tập tự luyện: 10 bài toán cuối chương bao quát toàn bộ các chủ đề: lập bảng mã Shannon-Fano/Huffman, vẽ đồ hình cây mã, tính bất đẳng thức Kraft, xác định đa thức sinh hợp lệ của mã vòng $C(9,6)$ và $C(8,5)$.

Phương pháp đánh giá (Assessment methods)

• Đánh giá quá trình: Kiểm tra khả năng giải thuật toán nén nguồn, lập ma trận sinh $G$ và ma trận kiểm tra $H$ cho các bộ mã tuyến tính.
• Đánh giá định kỳ: Bài thi tự luận yêu cầu chứng minh các đặc tính toán học của mã khối, mã vòng và tính toán các tham số điều chế cao tần, điều chế xung mã PCM.

Hướng dẫn tự học (Self-study guidelines)

1. Nghiên cứu kỹ định lý mã hóa nguồn và mã hóa kênh của Shannon trước khi thực hiện các bài toán phân bổ xác suất.
2. Tự tay thực hiện lại các bước chia nhóm xác suất và vẽ cây nhị phân trong thuật toán Huffman.
3. Rèn luyện kỹ năng thực hiện các phép toán trên trường hữu hạn $GF(2)$ (cộng/nhân modulo-2, chia đa thức nhị phân).
4. Sử dụng các công cụ mô phỏng toán học (như MATLAB/Python) để kiểm chứng lại các bảng mã và mạch dịch CRC đã tính toán trên lý thuyết.

---

Điểm nổi bật và tính thực tiễn kỹ thuật

+-----------------------------------------------------------------------------+
|               BẢNG TỔNG HỢP CÁC CHUẨN KỸ THUẬT VÀ ỨNG DỤNG                  |
+-------------------+------------------------------+--------------------------+
| Phân loại         | Chuẩn kỹ thuật / Thuật toán  | Phạm vi ứng dụng         |
+-------------------+------------------------------+--------------------------+
| Mã hóa nguồn      | Shannon-Fano, Huffman        | Nén dữ liệu tệp tin      |
|                   | Lempel-Ziv                   | Lệnh compress/uncompress |
+-------------------+------------------------------+--------------------------+
| Mã hóa kênh       | Parity bit (BCC)             | Bộ mã ASCII, truyền UART |
|                   | CRC-12, CRC-16, CRC-CCITT    | Khung dữ liệu mạng, CATV |
|                   | Hamming C(7,4)               | Bộ nhớ, vi xử lý (FEC)   |
+-------------------+------------------------------+--------------------------+
| Điều chế tín hiệu | AM, FM, PM                   | Phát thanh, truyền hình  |
|                   | PAM, PWM, PPM, PCM           | Số hóa âm thanh thoại    |
|                   | ASK, FSK, PSK, QAM           | Thiết bị Modem trên PSTN |
+-------------------+------------------------------+--------------------------+

Điểm nhấn kỹ thuật và cấu trúc hệ thống

Giáo trình không dừng lại ở lý thuyết trừu tượng mà liên kết trực tiếp các mô hình toán với cấu trúc phần cứng và phần mềm tiêu chuẩn:

• Thuật toán nén dữ liệu từ điển Lempel-Ziv: Phân tích chi tiết cấu trúc từ điển động, giải thích cơ chế tiền đề hình thành nên các tiện ích nén dữ liệu kinh điển như compress và uncompress trong các hệ điều hành DOS và UNIX.
• Chuẩn hóa công nghiệp cho mã vòng CRC: Giới thiệu cấu trúc toán học của các đa thức sinh chuẩn quốc tế gồm: $$\text{CRC-12: } g(x) = x^{12} + x^{11} + x^3 + x^2 + x + 1$$ $$\text{CRC-16: } g(x) = x^{16} + x^{15} + x^2 + 1$$ $$\text{CRC-CCITT: } g(x) = x^{16} + x^{12} + x^5 + 1$$
• Thiết kế phần cứng chuyên dụng: Minh họa trực quan sơ đồ nguyên lý mạch tạo mã CRC-16 bằng chuỗi 16 bộ ghi dịch kết hợp các cổng cộng modulo-2; mạch tách sóng hình bao AM dùng điốt bán dẫn $D$ và mạch tích phân $RC$; mạch điều chế xung PWM/PPM dùng tầng so sánh điện áp răng cưa và mạch đa hài đợi.

Ứng dụng thực tế trong mạng và viễn thông (Real-world applications)

• Hạ tầng mạng thoại công cộng (PSTN): Giải thích rõ ràng bài toán thích ứng kênh truyền: do mạng PSTN ban đầu được thiết kế cho tín hiệu thoại tương tự có dải thông giới hạn $300\text{ Hz} - 3400\text{ Hz}$, các thiết bị đầu cuối máy tính (DTE) bắt buộc phải sử dụng thiết bị biến đổi (Modem - Modulator/Demodulator) thông qua các kỹ thuật điều chế khóa dịch ASK, FSK, PSK để truyền số liệu số qua đường dây thoại.
• Hệ thống truyền hình cáp (CATV): Ứng dụng biến đổi tín hiệu số sang miền tần số vô tuyến để ghép kênh trên cáp đồng trục truyền tải đến máy thu hình của thuê bao.
• Bộ mã ký tự tiêu chuẩn ASCII: Minh họa cơ chế kiểm tra chẵn lẻ Parity 1 bit bảo vệ khối dữ liệu 7 bit trước các lỗi lật bit đơn lẻ trong truyền dẫn nối tiếp.

---

Đối tượng sử dụng giáo trình

• Sinh viên đại học: Phù hợp trực tiếp cho sinh viên năm thứ 3 và năm thứ 4 chuyên ngành Kỹ thuật Điện tử - Viễn thông, Kỹ thuật Máy tính, Công nghệ Thông tin và Kỹ thuật Điều khiển - Tự động hóa.
• Học viên cao học và Nghiên cứu sinh: Làm tài liệu tham khảo nền tảng để nghiên cứu sâu hơn về Lý thuyết thông tin nâng cao, Mã hóa kênh hiện đại (Turbocodes, LDPC), và Xử lý tín hiệu trong mạng thông tin di động băng rộng.
• Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành các học phần:
  1. Toán cao cấp và Đại số tuyến tính: Nắm vững không gian véc tơ, ma trận, định thức, và các phép toán ma trận.
  2. Xác suất thống kê: Nắm vững biến ngẫu nhiên, hàm phân bố xác suất, kỳ vọng toán học và các quá trình ngẫu nhiên.
  3. Tín hiệu và Hệ thống: Hiểu rõ biến đổi Fourier, phổ tần số của tín hiệu, và hàm truyền đạt của bộ lọc tuyến tính.
• Giảng viên và Cán bộ nghiên cứu: Giáo trình cung cấp khung đề cương chuẩn, hệ thống bảng biểu thuật toán và ngân hàng bài tập định lượng phục vụ trực tiếp cho việc soạn bài giảng, xây dựng đề thi và hướng dẫn thực hành phòng thí nghiệm.

---

Câu hỏi thường gặp (FAQ)

1. Giáo trình này phục vụ cho môn học cụ thể nào trong chương trình đào tạo?

Giáo trình phục vụ trực tiếp cho các môn học: "Lý thuyết truyền tin", "Lý thuyết thông tin và mã hóa", "Cơ sở truyền số liệu" hoặc "Kỹ thuật truyền thông số" tại các trường đại học khối kỹ thuật và công nghệ.

2. Sinh viên cần chuẩn bị kiến thức toán học nào trước khi học giáo trình này?

Sinh viên cần nắm vững kiến thức về Xác suất thống kê (tính toán xác suất đồng thời, xác suất có điều kiện để tính Entropi), Đại số tuyến tính (phép nhân ma trận, véc tơ chuyển vị), và số học trường hữu hạn nhị phân (phép cộng/nhân modulo-2).

3. Sự khác biệt căn bản giữa mã hóa nguồn và mã hóa kênh trong giáo trình là gì?

• Mã hóa nguồn nhằm giảm độ dư thừa của thông tin, nén dữ liệu để tiếp cận thông lượng kênh với tài nguyên tối thiểu (biểu diễn bởi các giải thuật Shannon-Fano, Huffman, Lempel-Ziv).
• Mã hóa kênh chủ động thêm các bit kiểm tra có quy luật (tăng độ dư) nhằm phát hiện và sửa các lỗi bit do tạp âm kênh truyền gây ra (biểu diễn bởi mã Parity, mã tuyến tính, mã CRC, mã Hamming).

4. Làm thế nào để tự học và làm chủ các thuật toán mã hóa trong sách?

Phương pháp tự học tối ưu là tiến hành giải tay các bảng phân bố xác suất mẫu, tính toán chiều dài từ mã trung bình $\bar{n}$, đối chiếu với bất đẳng thức Kraft $\sum 2^{-n_k} \le 1$, sau đó viết các đoạn mã nguồn ngắn (C/C++ hoặc Python) để tự động hóa thuật toán và kiểm chứng lại kết quả.

5. Giáo trình có đề cập đến cấu trúc phần cứng của các bộ giải điều chế không?

Có. Giáo trình mô tả chi tiết các sơ đồ khối phần cứng như mạch dao động LC điều khiển bằng biến dung (VCO), cấu trúc vòng khóa pha PLL 3 khối chức năng, mạch tách hình bao dùng diode bán dẫn $D$ với tải $RC$, và sơ đồ mạch thanh ghi dịch dùng cho mã vòng CRC.

---

Kết luận

Giáo trình cung cấp một hệ thống tri thức hoàn chỉnh, chuẩn xác và mang tính học thuật cao về lĩnh vực lý thuyết truyền tin và điều chế tín hiệu. Giá trị cốt lõi của tài liệu nằm ở việc kết nối chặt chẽ giữa các định lý giới hạn của Claude Shannon, cấu trúc đại số của các bộ mã kiểm soát lỗi và các giải pháp điều chế vật lý ứng dụng trong hệ thống viễn thông thực tế.

Lộ trình học tập khuyến nghị bắt đầu từ việc nắm vững định lý kênh truyền, tiếp cận các giải thuật mã hóa nguồn tối ưu (Huffman, Lempel-Ziv), phát triển năng lực thiết kế mã hóa kênh chống nhiễu (CRC, Hamming), và hoàn thiện với việc phân tích các cơ chế điều chế cao tần và điều chế xung mã PCM. Tài liệu là nguồn tham khảo tiêu chuẩn cho công tác giảng dạy, học tập và nghiên cứu trong lĩnh vực kỹ thuật truyền thông số.

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).