Chương 1: Những vấn đề chung và những khái niệm cơ bản

3

CHƯƠNG I: NHỮNG VẤN ĐỀ CHUNG VÀ NHỮNG KHÁI

NIỆM CƠ BẢN

1.1. VỊ TRÍ, VAI TRÒ VÀ SƠ LƯỢC LỊCH SỬ PHÁT TRIỂN CỦA "LÝ THUYẾT

THÔNG TIN"

1.1.1. Vị trí, vai trò của Lý thuyết thông tin

Do sự phát triển mạnh mẽ của kỹ thuật tính toán và các hệ tự động, một ngành khoa học

mới ra đời và phát triển nhanh chóng, đó là: "Lý thuyết thông tin". Là một ngành khoa học nhưng

nó không ngừng phát triển và thâm nhập vào nhiều ngành khoa học khác như: Toán; triết; hoá;

Xibecnetic; lý thuyết hệ thống; lý thuyết và kỹ thuật thông tin liên lạc... và đã đạt được nhiều kết

quả. Tuy vậy nó cũng còn nhiều vấn đề cần được giải quyết hoặc giải quyết hoàn chỉnh hơn.

Giáo trình " Lý thuyết thông tin" này (còn được gọi là "Cơ sở lý thuyết truyền tin") chỉ là

một bộ phận của lý thuyết thông tin chung - Nó là phần áp dụng của "Lý thuyết thông tin" vào kỹ

thuật thông tin liên lạc.

Trong các quan hệ của Lý thuyết thông tin chung với các ngành khoa học khác nhau, ta phải

đặc biệt kể đến mối quan hệ của nó với ngành Xibecnetic.

Mối quan hệ giữa các hoạt động khoa học của con người và các quảng tính của vật chất

được mô tả trên hình (1.1).

- Năng lượng học: Là một ngành khoa học chuyên nghiên cứu các vấn đề liên quan tới các

khái niệm thuộc về năng lượng. Mục đích của năng lượng học là làm giảm sự nặng nhọc của lao

động chân tay và nâng cao hiệu suất lao động chân tay. Nhiệm vụ trung tâm của nó là tạo, truyền,

thụ, biến đổi, tích luỹ và xử lý năng lượng.

Quảng tính của vật chất

Khối lượng

Công nghệ học

Thông tin

Năng lượng

Năng lượng học

Điều khiển học

(Xibecnetic)

Các lĩnh vực hoạt động khoa học của

con người

Hình 1.1. Quan hệ giữa hoạt động khoa học và quảng tính của vật chất HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

- - - - - - - - - - - - - -

BÀI GIẢNG

LÝ THUYẾT THÔNG TIN

Biên soạn : PGS.Ts. NGUYỄN BÌNH

Lưu hành nội bộ

HÀ NỘI - 2006 LỜI NÓI ĐẦU

Giáo trình Lý thuyết thông tin là một giáo trình cơ sở dùng cho sinh viên chuyên ngành

Điện tử - Viễn thông và Công nghệ thông tin của Học viện Công nghệ Bưu chính Viễn thông.

Đây cũng là một tài liệu tham khảo hữu ích cho các sinh viên chuyên ngành Điện - Điện tử.

Giáo trình này nhằm chuẩn bị tốt kiến thức cơ sở cho sinh viên để học tập và nắm vững các

môn kỹ thuật chuyên ngành, đảm bảo cho sinh viên có thể đánh giá các chỉ tiêu chất lượng cơ bản

của một hệ thống truyền tin một cách có căn cứ khoa học.

Giáo trình gồm 6 chương, ngoài chương I có tính chất giới thiệu chung, các chương còn lại

được chia thành 4 phần chính:

Phần I: Lý thuyết tín hiệu ngẫu nhiên và nhiễu (Chương 2)

Phần II: Lý thuyết thông tin và mã hóa (Chương 3 và Chương 4)

Phần III: Lý thuyết thu tối ưu (Chương 5)

Phần IV: Mật mã (Chương 6)

Phần I: (Chương II). Nhằm cung cấp các công cụ toán học cần thiết cho các chương sau.

Phần II: Gồm hai chương với các nội dungchủ yếu sau:

- Chương III: Cung cấp những khái niệm cơ bản của lý thuyết thông tin Shannon trong hệ

truyền tin rời rạc và mở rộng cho các hệ truyền tin liên tục.

- Chương IV: Trình bày hai hướng kiến thiết cho hai định lý mã hóa của Shannon. Vì

khuôn khổ có hạn của giáo trình, các hướng này (mã nguồn và mã kênh) chỉ được trình bày ở mức

độ các hiểu biết cơ bản. Để có thể tìm hiểu sâu hơn những kết quả mới và các ứng dụng cụ thể

sinh viên cần phải xem thêm trong các tài liệu tham khảo.

Phần III: (Chương V) Trình bày vấn đề xây dựng các hệ thống thu tối ưu đảm bảo tốc độ

truyền tin và độ chính xác đạt được các giá trị giới hạn. Theo truyền thống bao trùm lên toàn bộ

giáo trình là việc trình bày hai bài toán phân tích và tổng hợp. Các ví dụ trong giáo trình được

chọn lọc kỹ nhằm giúp cho sinh viên hiểu được các khái niệm một cách sâu sắc hơn. Các hình vẽ,

bảng biểu nhằm mô tả một cách trực quan nhất các khái niệm và hoạt động của sơ đồ khối chức

năng của các thiết bị cụ thể

Phần VI: (Chương VI) Trình bày cơ sở lý thuyết các hệ mật bao gồm các hệ mật khóa bí

mật và các hệ mật khóa công khai. Do khuôn khổ có hạn của giáo trình, một số vấn đề quan trọng

còn chưa được đề cập tới (như trao đổi và phân phối khóa, xác thực, đảm bảo tính toàn vẹn ...)

Sau mỗi chương đều có các câu hỏi và bài tập nhằm giúp cho sinh viên củng cố được các kỹ

năng tính toán cần thiết và hiểu sâu sắc hơn các khái niệm và các thuật toán quan trọng.

Phần phụ lục cung cấp một số kiến thức bổ xung cần thiết đối với một số khái niệm quan

trọng về một số số liệu cần thiết giúp cho sinh viên làm được các bài tập được ra ở các chương.

Giáo trình được viết dựa trên cơ sở đề cương môn học Lỹ thuyết thông tin do Bộ Giáo dục

và Đào tạo và được đúc kết sau nhiều năm giảng dạy và nghiên cứu của tác giả. Rất mong được

sự đóng góp của bạn đọc.

Các đóng góp ý kiến xin gửi về

KHOA KỸ THUẬT ĐIỆN TỬ 1 - HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

KM 10. ĐƯỜNG NGUYỄN TRÃI - THỊ XÃ HÀ ĐÔNG

Email: [email protected]

Hoặc [email protected]

Cuối cùng tôi xin chân thành cảm ơn GS. Huỳnh Hữu Tuệ đã cho tôi nhiều ý kiến quý báu

trong các trao đổi học thuật có liên quan tới một số nội dung quan trọng trong giáo trình này.

NGƯỜI BIÊN SOẠN Chương 1: Những vấn đề chung và những khái niệm cơ bản

4

- Xibecnetic: Bao gồm các ngành khoa học chuyên nghiên cứu các vấn đề có liên quan đến

khái niệm thông tin và tín hiệu. Mục đích của Xibecnetic là làm giảm sự nặng nhọc của trí óc và

nâng cao hiệu suất lao động trí óc. Ngoài những vấn đề được xét trong Xibecnetic như đối tượng,

mục đích, tối ưu hoá việc điều khiển, liên hệ ngược. Việc nghiên cứu các quá trình thông tin (như

chọn, truyền, xử lý, lưu trữ và hiển thị thông tin) cũng là một vấn đề trung tâm của Xibecnetic.

Chính vì vậy, lý thuyết và kỹ thuật thông tin chiếm vai trò rất quan trọng trong Xibecnetic.

- Công nghệ học: gồm các ngành khoa học tạo, biến đổi và xử lý các vật liệu mới. Công

nghệ học phục vụ đắc lực cho Xibecnetic và năng lượng học. Không có công nghệ học hiện đại

thì không thể có các ngành khoa học kỹ thuật hiện đại.

1.1.2. Sơ lược lịch sử phát triển

Người đặt viên gạch đầu tiên để xây dựng lý thuyết thông tin là Hartley R.V.L. Năm 1928,

ông đã đưa ra số đo lượng thông tin là một khái niệm trung tâm của lý thuyết thông tin. Dựa vào

khái niệm này, ta có thể so sánh định lượng các hệ truyền tin với nhau.

Năm 1933, V.A Kachenhicov chứng minh một loạt những luận điểm quan trọng của lý

thuyết thông tin trong bài báo "Về khả năng thông qua của không trung và dây dẫn trong hệ thống

liên lạc điện".

Năm 1935, D.V Ageev đưa ra công trình "Lý thuyết tách tuyến tính", trong đó ông phát

biểu những nguyên tắc cơ bản về lý thuyết tách các tín hiệu.

Năm 1946, V.A Kachenhicov thông báo công trình "Lý thuyết thế chống nhiễu' đánh dấu

một bước phát triển rất quan trọng của lý thuyết thông tin.

Trong hai năm 1948 - 1949, Shanon C.E công bố một loạt các công trình vĩ đại, đưa sự

phát triển của lý thuyết thông tin lên một bước tiến mới chưa từng có. Trong các công trình này,

nhờ việc đưa vào khái niệm lượng thông tin và tính đến cấu trúc thống kê của tin, ông đã chứng

minh một loạt định lý về khả năng thông qua của kênh truyền tin khi có nhiễu và các định lý mã

hoá. Những công trình này là nền tảng vững chắc của lý thuyết thông tin.

Ngày nay, lý thuyết thông tin phát triển theo hai hướng chủ yếu sau:

Lý thuyết thông tin toán học: Xây dựng những luận điểm thuần tuý toán học và những cơ

sở toán học chặt chẽ của lý thuyết thông tin. Cống hiến chủ yếu trong lĩnh vực này thuộc về các

nhà bác học lỗi lạc như: N.Wiener, A. Feinstain, C.E Shanon, A.N. Kanmôgorov, A.JA Khintrin.

Lý thuyết thông tin ứng dụng: (lý thuyết truyền tin)

Chuyên nghiên cứu các bài toán thực tế quan trọng do kỹ thuật liên lạc đặt ra có liên quan

đến vấn đề chống nhiễu và nâng cao độ tin cậy của việc truyền tin. Các bác học C.E Shanon, S.O

RiCe, D. Midleton, W. Peterson, A.A Khakevich, V. Kachenhicov đã có những công trình quý

báu trong lĩnh vực này. Chương 1: Những vấn đề chung và những khái niệm cơ bản

5

1.2. NHỮNG KHÁI NIỆM CƠ BẢN - SƠ ĐỒ HỆ TRUYỀN TIN VÀ NHIỆM VỤ CỦA NÓ

1.2.1. Các định nghĩa cơ bản

1.2.1.1. Thông tin

Định nghĩa: Thông tin là những tính chất xác định của vật chất mà con người (hoặc hệ

thống kỹ thuật) nhận được từ thế giới vật chất bên ngoài hoặc từ những quá trình xảy ra trong bản

thân nó.

Với định nghĩa này, mọi ngành khoa học là khám phá ra các cấu trúc thông qua việc thu

thập, chế biến, xử lý thông tin. ở đây "thông tin" là một danh từ chứ không phải là động từ để chỉ

một hành vi tác động giữa hai đối tượng (người, máy) liên lạc với nhau.

Theo quan điểm triết học, thông tin là một quảng tính của thế giới vật chất (tương tự như

năng lượng, khối lượng). Thông tin không được tạo ra mà chỉ được sử dụng bởi hệ thụ cảm.

Thông tin tồn tại một cách khách quan, không phụ thuộc vào hệ thụ cảm. Trong nghĩa khái quát

nhất, thông tin là sự đa dạng. Sự đa dạng ở đây có thể hiểu theo nhiều nghĩa khác nhau: Tính ngẫu

nhiên, trình độ tổ chức,...

1.2.1.2. Tin

Tin là dạng vật chất cụ thể để biểu diễn hoặc thể hiện thông tin. Có hai dạng: tin rời rạc và

tin liên tục.

Ví dụ: Tấm ảnh, bản nhạc, bảng số liệu, bài nói,... là các tin.

1.2.1.3. Tín hiệu

Tín hiệu là các đại lượng vật lý biến thiên, phản ánh tin cần truyền.

Chú ý: Không phải bản thân quá trình vật lý là tín hiệu, mà sự biến đổi các tham số riêng

của quá trình vật lý mới là tín hiệu.

Các đặc trưng vật lý có thể là dòng điện, điện áp, ánh sáng, âm thanh, trường điện từ

1.2.2. Sơ đồ khối của hệ thống truyền tin số (Hình 1.2)

Mã bảo

mật

Mã

kênh

Dồn

kênh

Trải

phổ

Giải mã

mật

Giải mã

kênh

Chia

kênh

Ép

phổ

Dòng bit

Hệ thống đồng bộ

( Synchronization ) Dạng sóng số

K

Ê

N

H

Nhiễu

Từ các nguồn khác

Tới các bộ nhận tin khác

Định khuôn

dạng

Định khuôn

dạng

Đầu vào số

Đầu ra số

Điều chế

Máy

Phát

(XMT)

Giải điều

chế

MáY

THU

(RCV)

Khối cơ bản

Khối tuỳ chọn

Hình 1.2. Sơ đồ khối hệ thống truyền tin số.

m1 S1(t)

Nhận

tin

m1

Nguồn

tin

Mã

nguồn

Giải mã

nguồn

Đa truy

nhập

Đa truy

nhập Chương 1: Những vấn đề chung và những khái niệm cơ bản

7

1.2.2.1. Nguồn tin

Nơi sản ra tin:

- Nếu tập tin là hữu hạn thì nguồn sinh ra nó được gọi là nguồn rời rạc.

- Nếu tập tin là vô hạn thì nguồn sinh ra nó được gọi là nguồn liên tục.

Nguồn tin có hai tính chất: Tính thống kê và tính hàm ý.

Với nguồn rời rạc, tính thống kê biểu hiện ở chỗ xác suất xuất hiện các tin là khác nhau.

Tính hàm ý biểu hiện ở chỗ xác suất xuất hiện của một tin nào đó sau một dãy tin khác nhau

nào đó là khác nhau.

Ví dụ: P(y/ta) ≠ P(y/ba)

1.2.2.2. Máy phát

Là thiết bị biến đổi tập tin thành tập tín hiệu tương ứng. Phép biến đổi này phải là đơn trị

hai chiều (thì bên thu mới có thể "sao lại" được đúng tin gửi đi). Trong trường hợp tổng quát, máy

phát gồm hai khối chính.

- Thiết bị mã hoá: Làm ứng mỗi tin với một tổ hợp các ký hiệu đã chọn nhằm tăng mật độ,

tăng khả năng chống nhiễu, tăng tốc độ truyền tin.

- Khối điều chế: Là thiết bị biến tập tin (đã hoặc không mã hoá) thành các tín hiệu để bức xạ

vào không gian dưới dạng sóng điện từ cao tần. Về nguyên tắc, bất kỳ một máy phát nào cũng có

khối này.

1.2.2.3. Đường truyền tin

Là môi trường vật lý, trong đó tín hiệu truyền đi từ máy phát sang máy thu. Trên đường

truyền có những tác động làm mất năng lượng, làm mất thông tin của tín hiệu.

1.2.2.4. Máy thu

Là thiết bị lập lại (sao lại) thông tin từ tín hiệu nhận được. Máy thu thực hiện phép biến đổi

ngược lại với phép biến đổi ở máy phát: Biến tập tín hiệu thu được thành tập tin tương ứng.

Máy thu gồm hai khối:

- Giải điều chế: Biến đổi tín hiệu nhận được thành tin đã mã hoá.

- Giải mã: Biến đổi các tin đã mã hoá thành các tin tương ứng ban đầu (các tin của nguồn

gửi đi).

1.2.2.5. Nhận tin

Có ba chức năng:

- Ghi giữ tin (ví dụ bộ nhớ của máy tính, băng ghi âm, ghi hình,...)

- Biểu thị tin: Làm cho các giác quan của con người hoặc các bộ cảm biến của máy thụ cảm

được để xử lý tin (ví dụ băng âm thanh, chữ số, hình ảnh,...) Chương 1: Những vấn đề chung và những khái niệm cơ bản

8

- Xử lý tin: Biến đổi tin để đưa nó về dạng dễ sử dụng. Chức năng này có thể thực hiện

bằng con người hoặc bằng máy.

1.2.2.6. Kênh truyền tin

Là tập hợp các thiết bị kỹ thuật phục vụ cho việc truyền tin từ nguồn đến nơi nhận tin.

1.2.2.7. Nhiễu

Là mọi yếu tố ngẫu nhiên có ảnh hưởng xấu đến việc thu tin. Những yếu tố này tác động

xấu đến tin truyền đi từ bên phát đến bên thu. Để cho gọn, ta gộp các yếu tố tác động đó vào một

ô trên hình 1.2.

Hình 1.2 là sơ đồ khối tổng quát nhất của một hệ truyền tin số. Nó có thể là: hệ thống vô

tuyến điện thoại, vô tuyến điện báo, rađa, vô tuyến truyền hình, hệ thống thông tin truyền số liệu,

vô tuyến điều khiển từ xa.

1.2.2.8. Các phương pháp biến đổi thông tin số trong các khối chức năng của hệ thống

Chương 1: Những vấn đề chung và những khái niệm cơ bản

9

Định dạng/ Mã nguồn

Mã hoá ký tự

Lấy mẫu

Lượng tử hoá

Điều chế mã xung

(PCM)

- PCM vi phân

- Điều chế Delta (DM)

- DM có tốc độ biến đổi

liên tục (CVSD)

- Mã hoá dự đoán tuyến

tính (LPC)

- Các phương pháp nén:

Mã Huffman, mã số học,

thuật toán Ziv_Lempel

Điều chế

Kết hợp

- PSK: Manip pha

- FSK: Manip tần số

- ASK: Manip biên độ

- Hỗn hợp

- OQPSK: Manip pha

tương đối 4 mức

- MSK

Không kết hợp

- PSK vi phân

- FSK

- ASK

- Hỗn hợp

Mã kênh

Dạng sóng

Tín hiệu M_trị

Tín hiệu trực giao

Tín hiệu song trực

giao

Các dãy có cấu trúc

- Mã khối

- Mã liên tục

Dồn kênh/ Đa truy cập

- Phân chia tần số:

FDM/ FDMA

- Phân chia thời gian:

TDM/ TDMA

- Phân chia mã:

CDM/ CDMA

- Phân chia không gian:

SDMA

- Phân chia cực tính:

PDMA

- OFDM

Trải phổ

Dãy trực tiếp (DS)

Nhảy tần (FH)

Nhảy thời gian (TH)

Các phương pháp hỗn

hợp

Đồng bộ

- Đồng bộ sóng mang

- Đồng bộ dấu

- Đồng bộ khung

- Đồng bộ mạng

- Hoán vị

- Thay thế

- Xử lý bit

- Các phương pháp hỗn hợp

- Thuật toán RSA

- Thuật toán logarit rời rạc

- Thuật toán McElice

- Thuật toán Merkle-Hellman

- Thuật toán sử dụng đường

cong Elliptic

Mã bảo mật

Mã hoá theo khối

Mã hoá dòng số liệu

Mật mã cổ điển

Mật mã khoá công khai Chương 1: Những vấn đề chung và những khái niệm cơ bản

10

1.2.3. Những chỉ tiêu chất lượng cơ bản của một hệ truyền tin

1.2.3.1. Tính hữu hiệu

Thể hiện trên các mặt sau:

- Tốc độ truyền tin cao.

- Truyền được đồng thời nhiều tin khác nhau.

- Chi phí cho một bit thông tin thấp.

1.2.3.2. Độ tin cậy

Đảm bảo độ chính xác của việc thu nhận tin cao, xác suất thu sai (BER) thấp.

Hai chỉ tiêu trên mâu thuẫn nhau. Giải quyết mâu thuẫn trên là nhiệm vụ của lý thuyết thông

tin.

1.2.3.3. An toàn

- Bí mật:

+ Không thể khai thác thông tin trái phép.

+ Chỉ có người nhận hợp lệ mới hiểu được thông tin.

- Xác thực: Gắn trách nhiệm của bên gửi - bên nhận với bản tin (chữ ký số).

- Toàn vẹn:

+ Thông tin không bị bóp méo (cắt xén, xuyên tạc, sửa đổi).

+ Thông tin được nhận phải nguyên vẹn cả về nội dung và hình thức.

- Khả dụng: Mọi tài nguyên và dịch vụ của hệ thống phải được cung cấp đầy đủ cho người

dùng hợp pháp.

1.2.3.4. Đảm bảo chất lượng dịch vụ (QoS)

Đây là một chỉ tiêu rất quan trọng đặc biệt là đối với các dịch vụ thời gian thực, nhậy cảm

với độ trễ (truyền tiếng nói, hình ảnh, ....) Chương 2: Tín hiệu và nhiễu

11

CHƯƠNG II: TÍN HIỆU VÀ NHIỄU

2.1. TÍN HIỆU XÁC ĐỊNH VÀ CÁC ĐẶC TRƯNG VẬT LÝ CỦA CHÚNG

Tín hiệu xác định thường được xem là một hàm xác định của biến thời gian t (s(t)). Hàm

này có thể được mô tả bằng một biểu thức giải tích hoặc được mô tả bằng đồ thị. Một trong các

đặc trưng vật lý quan trọng của tín hiệu là hàm mật độ phổ biên độ phức S( )

•

ω . Với tín hiệu s(t)

khả tích tuyệt đối, ta có cặp biến đổi Fourier sau:

jt

jt

S( ) s(t) e dt (2.1)

1

s(t) S( )e d (2.2)

2

∞ •

−ω

−∞

∞ •

ω

−∞

ω=

=ωω

π

∫

∫

Sau đây là một số đặc trưng vật lý quen thuộc của tín hiệu:

- Thời hạn của tín hiệu (T): Thời hạn của tín hiệu là khoảng thời gian tồn tại của tín hiệu,

trong khoảng này giá trị của tín hiệu không đồng nhất bằng 0.

- Bề rộng phổ của tín hiệu (F): Đây là miền xác định bởi tần số khác không cao nhất của tín

hiệu.

- Năng lượng của tín hiệu (E): Năng lượng của tín hiệu có thể tính theo miền thời gian hay

miền tần số.

2

2 1

Es(t)dt S()d [J](2.3)

2

∞∞ •

−∞ −∞

==ωω

π ∫∫

(Định lý Parseval)

- Công suất của tín hiệu (P):

E

P[W]

T

=

2.2. TÍN HIỆU VÀ NHIỄU LÀ CÁC QUÁ TRÌNH NGẪU NHIÊN

2.2.1. Bản chất ngẫu nhiên của tín hiệu và nhiễu

Như đã xét ở trên, chúng ta coi tín hiệu là biểu hiện vật lý của tin (trong thông tin vô tuyến:

dạng vật lý cuối cùng của tin là sóng điện từ). Quá trình vật lý mang tin diễn ra theo thời gian, do

đó về mặt toán học thì khi có thể được, cách biểu diễn trực tiếp nhất cho tín hiệu là viết biểu thức

của nó theo thời gian hay vẽ đồ thị thời gian của nó. Chương 2: Tín hiệu và nhiễu

12

Trong lý thuyết cổ điển, dù tín hiệu tuần hoàn hoặc không tuần hoàn nhưng ta đều coi là đã

biết trước và biểu diễn nó bằng một hàm tiền định của thời gian. Đó là quan niệm xác định về tín

hiệu (tín hiệu tiền định). Tuy vậy, quan niệm này không phù hợp với thực tế. Thật vậy, tín hiệu

tiền định không thể dùng vào việc truyền tin tức được. Với cách coi tín hiệu là biểu hiện vật lý của

tin, nếu chúng ta hoàn toàn biết trước nó thì về mặt thông tin, việc nhận tín hiệu đó không có ý

nghĩa gì. Nhưng nếu ta hoàn toàn không biết gì về tín hiệu truyền đi, thì ta không thể thực hiện

nhận tin được. Bởi vì khi đó không có cái gì làm căn cứ để phân biệt tín hiệu với những cái không

phải nó, đặc biệt là với các nhiễu. Như vậy, quan niệm hợp lý nhất là phải kể đến các đặc tính

thống kê của tín hiệu, tức là phải coi tín hiệu là một quá trình ngẫu nhiên. Chúng ta sẽ gọi các tín

hiệu xét theo quan điểm thống kê này là các tín hiệu ngẫu nhiên.

2.2.2. Định nghĩa và phân loại nhiễu

Trong quá trình truyền tin, tín hiệu luôn luôn bị nhiều yếu tố ngẫu nhiên tác động vào, làm

mất mát một phần hoặc thậm chí có thể mất toàn bộ thông tin chứa trong nó. Những yếu tố ngẫu

nhiên đó rất đa dạng, chúng có thể là những thay đổi ngẫu nhiên của các hằng số vật lý của môi

trường truyền qua hoặc những loại trường điện từ cảm ứng trong công nghiệp, y học...vv...

Trong vô tuyến điện, người ta gọi tất cả những yếu tố ngẫu nhiên ấy là các can nhiễu (hay nhiễu).

Tóm lại, ta có thể coi nhiễu là tất cả những tín hiệu vô ích (tất nhiên là đối với hệ truyền tin ta xét)

có ảnh hưởng xấu đến việc thu tin. Nguồn nhiễu có thể ở ngoài hoặc trong hệ. Nếu nhiễu xác định

thì việc chống nó không có khó khăn gì về mặt nguyên tắc. Ví dụ như người ta đã có những biện

pháp để chống ồn do dòng xoay chiều gây ra trong các máy khuếch đại âm tần, người ta cũng biết

rõ những cách chống sự nhiễu lẫn nhau giữa các điện đài vô tuyến điện cùng làm việc mà chúng

có phổ tín hiệu trùm nhau...vv... Các loại nhiễu này không đáng ngại.

Chú ý:

Cần phân biệt nhiễu với sự méo gây ra bởi đặc tính tần số và đặc tính thời gian của các thiết

bị, kênh truyền... (méo tuyến tính và méo phi tuyến). Về mặt nguyên tắc, ta có thể khắc phục

được chúng bằng cách hiệu chỉnh.

Nhiễu đáng lo ngại nhất vẫn là các nhiễu ngẫu nhiên. Cho đến nay, việc chống các nhiễu

ngẫu nhiên vẫn gặp những khó khăn lớn cả về mặt lý luận lẫn về mặt thực hiện kỹ thuật. Do đó,

trong giáo trình này ta chỉ đề cập đến một dạng nào đó (sau này sẽ thấy ở đây thường xét nhất là

nhiễu cộng, chuẩn) của nhiễu ngẫu nhiên.

Việc chia thành các loại (dạng) nhiễu khác nhau có thể làm theo các dấu hiệu sau:

1. Theo bề rộng phổ của nhiễu: có nhiễu giải rộng (phổ rộng như phổ của ánh sáng trắng gọi

là tạp âm trắng), nhiễu giải hẹp (gọi là tạp âm màu).

2. Theo quy luật biến thiên thời gian của nhiễu: có nhiễu rời rạc và nhiễu liên tục.

3. Theo phương thức mà nhiễu tác động lên tín hiệu: có nhiễu cộng và nhiễu nhân.

4. Theo cách bức xạ của nhiễu: có nhiễu thụ động và nhiễu tích cực.

Nhiễu thụ động là các tia phản xạ từ các mục tiêu giả hoặc từ địa vật trở về đài ta xét khi

các tia sóng của nó đập vào chúng. Nhiễu tích cực (chủ động) do một nguồn bức xạ năng lượng

(các đài hoặc các hệ thống lân cận) hoặc máy phát nhiễu của đối phương chĩa vào đài hoặc hệ

thống đang xét. Chương 2: Tín hiệu và nhiễu

13

5. Theo nguồn gốc phát sinh: có nhiễu công nghiệp, nhiễu khí quyển, nhiễu vũ trụ...vv...

Trong giáo trình này khi nói về nhiễu, ta chỉ nói theo phương thức tác động của nhiễu lên

tín hiệu, tức là chỉ nói đến nhiễu nhân hoặc nhiễu cộng.

Về mặt toán học, tác động của nhiễu cộng lên tín hiệu được biểu diễn bởi hệ thức sau:

u(t) = s(t) + n(t) (2.4)

s(t) là tín hiệu gửi đi

u(t) là tín hiệu thu được

n(t) là nhiễu cộng

Còn nhiễu nhân được biểu diễn bởi:

u(t) (t).s(t) =μ (2.5)

μ(t): nhiễu nhân, là một quá trình ngẫu nhiên. Hiện tượng gây nên bởi nhiễu nhân gọi là

suy lạc (fading).

Tổng quát, khi tín hiệu chịu tác động đồng thời của cả nhiễu cộng và nhiễu nhân thì:

u(t) (t).s(t) n(t) =μ + (2.6)

Ở đây, ta đã coi hệ số truyền của kênh bằng đơn vị và bỏ qua thời gian giữ chậm tín hiệu

của kênh truyền. Nếu kể đến thời gian giữ chậm τ của kênh truyền thì (2.6) có dạng:

u(t) (t).s(t ) n(t) =μ −τ + (2.7)

2.3. CÁC ĐẶC TRƯNG THỐNG KÊ CỦA TÍN HIỆU NGẪU NHIÊN VÀ NHIỄU

2.3.1. Các đặc trưng thống kê

Theo quan điểm thống kê, tín hiệu và nhiễu được coi là các quá trình ngẫu nhiên. Đặc trưng

cho các quá trình ngẫu nhiên chính là các quy luật thống kê (các hàm phân bố và mật độ phân bố)

và các đặc trưng thống kê (kỳ vọng, phương sai, hàm tự tương quan, hàm tương quan). Các quy

luật thống kê và các đặc trưng thống kê đã được nghiên cứu trong lý thuyết hàm ngẫu nhiên, vì

vậy ở đây ta sẽ không nhắc lại.

Trong lớp các quá trình ngẫu nhiên, đặc biệt quan trọng là các quá trình ngẫu nhiên sau:

- Quá trình ngẫu nhiên dừng (theo nghĩa hẹp và theo nghĩa rộng) và quá trình ngẫu nhiên

chuẩn dừng.

- Quá trình ngẫu nhiên ergodic

Ta minh hoạ chúng theo lược đồ sau:

Chương 2: Tín hiệu và nhiễu

14

Hình 2.1

Trong những đặc trưng thống kê của các quá trình ngẫu nhiên, hàm tự tương quan và hàm

tương quan là những đặc trưng quan trọng nhất. Theo định nghĩa, hàm tự tương quan sẽ bằng:

{ }

[][ ]

x12 1 x1 2 x2

1 x1 2 x2 21212 12

R(t,t) M X(t) m(t).X(t) m(t)

x(t) m(t).x(t ) m(t ).W(x,x,t,t )dxdx

Δ

∞∞

−∞ −∞

⎡⎤⎡ ⎤ =− − ⎣⎦⎣ ⎦

=− − ∫∫

(2.8)

x12 R(t,t) đặc trưng cho sự phụ thuộc thống kê giữa hai giá trị ở hai thời điểm thuộc cùng

một thể hiện của quá trình ngẫu nhiên.

( ) 21212 W x ,x ,t ,t là hàm mật độ phân bố xác suất hai chiều của hai giá trị của quá trình

ngẫu nhiên ở hai thời điểm

1 t và

2 t .

Khi t

1 = t

2 thì (2.8) trở thành:

[] { } 2

x12 x x R (t , t ) M X(t) m (t) D (t) =−= (2.9)

Như vậy, phương sai là trường hợp riêng của hàm tự tương quan khi hai thời điểm xét trùng

nhau.

Đôi khi để tiện tính toán và so sánh, người ta dùng hàm tự tương quan chuẩn hoá được định

nghĩa bởi công thức:

x12 x12

x12

x11 x22 x1 x2

x12

x1 x2

R(t,t) R(t,t)

(t , t )

R (t ,t ).R (t , t ) D (t ).D (t )

R(t,t)

(t ). (t )

Δ

τ= =

=

ττ

(2.10)

Dễ dàng thấy rằng:

x12 (t , t ) 1 τ≤ .

QTNN QTNN

dừng dừng QTNN

rộng hẹp chuẩn

QTNN chuẩn dừng

QTNN

QTNN ergodic Chương 2: Tín hiệu và nhiễu

15

2.3.2. Khoảng tương quan

Khoảng tương quan cũng là một đặc trưng khá quan trọng. Ta thấy rằng hai giá trị của một

quá trình ngẫu nhiên ξ(t) chỉ tương quan với nhau khi khoảng cách τ giữa hai thời điểm xét là

hữu hạn. Khi τ→∞ , thì coi như hai giá trị ấy không tương quan với nhau nữa. Tuy vậy, trong

thực tế, đối với hầu hết các quá trình ngẫu nhiên chỉ cần τ đủ lớn thì sự tương quan giữa hai giá

trị của quá trình đã mất. Do đó, đối với tính toán thực tế người ta định nghĩa khoảng (thời gian)

tương quan như sau:

Định nghĩa 1:

Khoảng tương quan

K τ là khoảng

thời gian trong đó () ξ τ τ không nhỏ hơn

0,05. (hình vẽ 2.2). Như vậy, ∀τ >

K τ thì

xem như hết tương quan.

Nếu cho biểu thức giải tích của () ξ τ τ

thì

K τ được tính như sau:

K

1

()d

2

∞

ξ

−∞

τ= ττ τ ∫ (2.11)

Ý nghĩa hình học:

K τ là nửa cạnh đáy của hình chữ nhật có chiều cao bằng đơn vị K, có diện tích bằng diện

tích của miền giới hạn bởi trục hoành và đường biểu diễn () ξ τ τ .

Trong thực tế, ta thường gặp những quá trình ngẫu nhiên ergodic. Ví dụ: tạp âm của các

máy thu vô tuyến điện,... Đối với các quá trình ngẫu nhiên ergodic, ta có thể xác định các đặc

trưng thống kê của chúng bằng thực nghiệm một cách dễ dàng.

Ta đã biết rằng, nếu X(t) - ergodic và với T đủ lớn thì ta có thể viết:

[] [ ] { }

[][ ]

xxx

T

xx

0

R ( ) M X(t) m . X(t ) m

1

x(t) m . x(t ) m dt

T

τ= − −τ−

≈−+τ− ∫

(2.12)

Trung bình thống kê = trung bình theo thời gian

1 τξ (τ)

0,05

0 τk τ t

Hình 2.2 Chương 2: Tín hiệu và nhiễu

16

2.4. CÁC ĐẶC TRƯNG VẬT LÝ CỦA TÍN HIỆU NGẪU NHIÊN VÀ NHIỄU. BIẾN

ĐỔI WIENER - KHINCHIN

2.4.1. Những khái niệm xây dựng lý thuyết phổ của quá trình ngẫu nhiên - mật độ phổ

công suất

Mục trước ta mới chỉ đưa ra một số đặc trưng thống kê của các quá trình ngẫu nhiên (tín

hiệu, nhiễu) mà chưa đưa ra các đặc trưng vật lý của chúng. Về mặt lý thuyết cũng như thực tế,

các đặc trưng vật lý của tín hiệu ngẫu nhiên (quá trình ngẫu nhiên) đóng một vai trò rất quan trọng

ở những chương sau khi nói đến cơ sở lý thuyết chống nhiễu cũng như xét các biện pháp thực tế

và các thiết bị chống nhiễu ta không thể không dùng đến những đặc trưng vật lý của tín hiệu ngẫu

nhiên và nhiễu. Khi xét các loại tín hiệu xác định trong giáo trình "Lý thuyết mạch", chúng ta đã

làm quen với các đặc trưng vật lý của chúng như: năng lượng, công suất, thời hạn của tín hiệu,

phổ biên độ phức, mật độ phổ, bề rộng phổ, ... Cơ sở để hình thành các đặc trưng vật lý này là

chuỗi và tích phân Fourier.

Đối với các tín hiệu ngẫu nhiên và nhiễu, ta không thể dùng trực tiếp các biến đổi Fourier

để xây dựng các đặc trưng vật lý của chúng được vì những lý do sau:

- Tập các thể hiện { } i

x (t) , i 1,2,..., =∞ của quá trình ngẫu nhiên X(t) cho trên khoảng T

thường là một tập vô hạn (thậm chí nó cũng không phải là một tập đếm được).

- Nếu tín hiệu ngẫu nhiên là dừng chặt thì tập vô hạn các thể hiện theo thời gian của nó

thường sẽ không khả tích tuyệt đối. Tức là:

T2

T

T2

lim x(t) dt

→∞ −

=∞ ∫

Để tránh khỏi những khó khăn trên, ta làm như sau:

Lấy hàm

T x(t) trùng với một thể hiện của quá trình ngẫu nhiên trung tâm X(t) (QTNN trung

tâm là QTNN có kỳ vọng không) ở trong đoạn

TT

,

22

⎡ ⎤

− ⎢ ⎥

⎣ ⎦

và nó bằng không ở ngoài đoạn đó:

T

x(t) t T 2

x(t)

0tT2

⎧≤ ⎪

= ⎨

> ⎪ ⎩

(2.13)

Từ (2.13), ta thấy

T x(t) thoả mãn điều kiện khả tích tuyệt đối nên có thể dùng biến đổi

Fourier cho nó được. Ta đã biết rằng phổ biên độ phức ( ) T S ω của

T x(t) được xác định bởi

tích phân thuận Fourier sau:

() ()

T2

jt

TT

T2

Sxtedt

−ω

−

ω= ∫

(2.14)

Theo định lý Parseval, ta có biểu thức tính năng lượng của

T x(t) như sau: Chương 2: Tín hiệu và nhiễu

17

2

2

T TT

1

Ex(t)dt S()d

2

∞∞ •

−∞ −∞

==ωω

π ∫∫ (2.15)

Công suất của thể hiện

T x(t) sẽ bằng:

2

T 2

T

T T

S( )

E1 1

PS()d d

T2T 2 T

•

∞∞ •

−∞ −∞

ω

= =ωω= ω

ππ ∫∫ (2.16)

Ta thấy vế trái của (2.16) là công suất của thể hiện

T x(t) trong khoảng thời gian tồn tại hữu

hạn T, còn vế phải là một tổng liên tục của các đại lượng

2

T S( ) Td

• ⎧ ⎫ ⎪ ⎪

ω ω ⎨ ⎬

⎪ ⎪ ⎩⎭

. Rõ ràng là để đảm

bảo sự bình đẳng về thứ nguyên giữa hai vế của (2.16) thì lượng

2

T S( )

d

T

•

ω

ω phải biểu thị công

suất trong giải tần vô cùng bé dω. Như vậy,

2

T S( )

T

•

ω

sẽ biểu thị công suất của thể hiện

T x(t)

trong một đơn vị tần số [W/Hz] tức là mật độ phổ công suất của thể hiện

T x(t) . Đến đây ta đặt:

2

T

T

S( )

G()

T

•

ω

= ω (2.17)

và gọi

T G() ω là mật độ phổ công suất của thể hiện

T x(t) trong khoảng T hữu hạn.

T G() ω đặc trưng cho sự phân bố công suất của một thể hiện

T x(t) trên thang tần số. Khi cho

T →∞ ta sẽ tìm được mật độ phổ công suất của một thể hiện duy nhất

T x(t) của quá trình

ngẫu nhiên:

2

T

xT

TT

S( )

G( ) limG( ) lim T

•

→∞ →∞

ω

ω= ω= (2.18)

x G( ) ω cũng có ý nghĩa tương tự như

T G() ω .

Từ (2.18) ta thấy rằng để xác định mật độ phổ công suất của cả quá trình ngẫu nhiên (tức là

tập các thể hiện ngẫu nhiên) thì phải lấy trung bình thống kê đại lượng

x G( ) ω , tức là: Chương 2: Tín hiệu và nhiễu

18

{}

2

T

x

T

S( )

G( ) M G ( ) M lim

T

•

→∞

ω

ω= ω = (2.19)

(2.19) là công thức xác định mật độ phổ công suất của các quá trình ngẫu nhiên.

2.4.2. Cặp biến đổi Wiener - Khinchin

Để thấy được mối quan hệ giữa các đặc trưng thống kê (nói riêng là hàm tự tương quan) và các

đặc trưng vật lý (nói riêng là mật độ phổ công suất) ta viết lại và thực hiện biến đổi (2.19) như sau:

{}

12

12

22

TT

TT

*

TT

T

T2 T2

jt jt

T1 1 T2 2

T

T2 T2

T/2 T/2

j(t t)

T1 T2 12

T

T/2 T/2

S( ) MS( )

G( ) M lim lim TT

1

lim M S ( )S ( ) do (2.14)

T

1

lim M x(t)e dt. x(t)e dt

T

1

lim M x (t ).x (t ) e dt dt

T

••

→∞ →∞

••

→∞

−ω −ω

→∞ −−

−ω −

→∞ −−

ωω

ω= = =

⎧⎫ ⎪⎪

=ωω ⎨⎬

⎪⎪ ⎩⎭

⎧⎫

⎪⎪

== ⎨⎬

⎪⎪ ⎩⎭

=

∫∫

∫∫

Nhưng theo định nghĩa (2.8), ta thấy ngay { } T1 T2 Mx(t).x(t) là hàm tự tương quan của

quá trình ngẫu nhiên trung tâm (có

x m0 = ) nên ta có thể viết:

{ } T1 T2 T12 Mx(t).x(t) R(t,t) =

Nếu

21 tt τ=− + thì đối với những quá trình dừng, ta có:

{ } T1 T2 T Mx(t).x(t) R() = τ

Ta có thể viết lại biểu thức cho ( ) G ω :

2

2

2

2

T t

T/2 2

j

T2

T T T/2 t

2

T t

T/2 2

j

T2

TT T T/2 t

2

1

G( ) lim R ( )e d dt

T

1

lim R ( )e d . lim dt

T

+

−ωτ

→∞ − −−

+

−ωτ

→∞ →∞ − −−

⎧⎫

⎪⎪

ω= τ τ ⎨⎬

⎪⎪

⎩⎭

=ττ

∫∫

∫∫

Chương 2: Tín hiệu và nhiễu

19

j

G( ) R( )e d

∞

− ωτ

−∞

ω =τ τ ∫ (2.20)

Tất nhiên ở đây phải giả sử tích phân ở vế phải của (2.20) tồn tại. Điều này luôn luôn đúng

nếu hàm tự tương quan R( ) τ khả tích tuyệt đối, tức là:

R( )d

∞

−∞

ττ

(2.20) là mật độ phổ công suất của quá trình ngẫu nhiên dừng. Nó biểu diễn một cách trung

bình (thống kê) sự phân bố công suất của quá trình ngẫu nhiên theo tần số của các thành phần dao

động điều hoà nguyên tố (tức là những thành phần dao động điều hoà vô cùng bé).

Như vậy, từ (2.20) ta có thể kết luận rằng phổ công suất G( ) ω của quá trình ngẫu nhiên

dừng là biến đổi thuận Fourier của hàm tự tương quan R( ) τ . Hiển nhiên rằng khi đã tồn tại biến

đổi thuận Fourier thì cũng tồn tại biến đổi ngược Fourier sau:

j 1

R( ) G( )e d

2

∞

ωτ

−∞

τ= ω ω

π ∫ (2.21)

Cặp công thức (2.20) và (2.21) gọi là cặp biến đổi Wiener - Khinchin, đó là sự mở rộng cặp

biến đổi Fourier sang các tín hiệu ngẫu nhiên dừng (ít nhất là theo nghĩa rộng).

Rõ ràng từ định nghĩa (2.17) của mật độ phổ công suất, ta thấy hàm G( ) ω là hàm chẵn

của đối số ω. Do đó sau khi dùng công thức Euler (

j

ecosjsin ±ωτ

= ωτ ± ωτ ) để biến đổi

(2.20) và (2.21), ta được:

0

0

G( ) 2 R( )cos d

1

R( ) G( )cos d

∞

∞

ω= τ ωττ

τ= ω ωτω

π

∫

∫

(2.22)

Chú ý 1: Từ mật độ phổ công suất của tín hiệu ngẫu nhiên, không thể sao lại bất cứ một thể

hiện nào (là hàm của thời gian t) của nó, vì G( ) ω không chứa những thông tin (những hiểu biết)

về pha của các thành phần phổ riêng lẻ. Đối với tín hiệu xác định thì từ mật độ phổ hoàn toàn có

thể sao lại chính tín hiệu đó nhờ tích phân ngược Fourier. Đó là chỗ khác nhau về bản chất giữa

biến đổi Fourier và biến đổi Wiener - Khinchin.

Chú ý 2: Nếu phải xét đồng thời hai quá trình ngẫu nhiên thì người ta cũng đưa ra khái

niệm mật độ phổ chéo. Mật độ phổ chéo và hàm tương quan chéo của hai quá trình ngẫu nhiên có

liên hệ dừng cũng thoả mãn cặp biến đổi Wiener - Khinchi.

2.4.3. Bề rộng phổ công suất Chương 2: Tín hiệu và nhiễu

20

Một đặc trưng vật lý quan trọng khác của

các tín hiệu ngẫu nhiên là bề rộng phổ công suất,

nó được định nghĩa bởi công thức sau:

0

0

G( )d

G( )

∞

Δ

ω ω

Δω =

ω

∫

(2.23)

Trong đó:

G(ω) là mật độ phổ công suất của tín hiệu

ngẫu nhiên.

G( 0 ω ) là giá trị cực đại của G(ω).

Δω là bề rộng phổ công suất (còn gọi là

bề rộng phổ) của quá trình ngẫu nhiên.

Ý nghĩa hình học:

Bề rộng phổ Δω chính là đáy của hình chữ nhật có chiều cao bằng G( 0 ω ) và có diện tích

bằng diện tích của miền giới hạn bởi trục ω và đường cong biểu diễn G(ω). (Hình 2.4).

Ý nghĩa vật lý:

Bề rộng phổ đặc trưng cho sự tập trung công suất (hoặc năng lượng) của tín hiệu ngẫu nhiên

ở quanh một tần số trung tâm, ngoài ra nó cũng đặc trưng cho cả sự bằng phẳng của phổ ở quanh

tần số trung tâm

0 ω .

2.4.4. Mở rộng cặp biến đổi Wiener - Khinchin cho trường hợp R() τ không khả tích

tuyệt đối

Nếu quá trình ngẫu nhiên X(t) chứa các thành phần dao động điều hoà dạng:

KKKK X(t) Acos( t ) =ω−ϕ

trong đó

K A và

K ϕ nói chung có thể là các đại lượng ngẫu nhiên, thì hàm tương quan trung bình:

K

2

* K

XK

A R() cos

2

τ =ωτ không thoả mãn điều kiện khả tích tuyệt đối.

Nếu sử dụng biểu diễn sau của hàm delta:

ixy

edx cos(xy)dx (y)

∞∞

−∞ −∞

==δ ∫∫

và biểu diễn phổ năng lượng của

K X(t) dưới dạng:

0,05

ω0 ω

Δω

G(ω)

Hình 2.3 Chương 2: Tín hiệu và nhiễu

21

[]

2

* K

KKK

A G() ( ) ( )

4

ω= δω−ω +δω+ω

thì định lý Wiener - Khinchin sẽ đúng cả đối với những quá trình ngẫu nhiên có những

thành phần tần số rời rạc, kể cả thành phần một chiều ở tần số

K ω = 0.

2.5. TRUYỀN CÁC TÍN HIỆU NGẪU NHIÊN QUA CÁC MẠCH VÔ TUYẾN ĐIỆN

TUYẾN TÍNH

Đối với các tín hiệu xác định, trong giáo trình "Lý thuyết mạch", ta đã xét bài toán phân

tích sau: Cho một mạch tuyến tính có cấu trúc đã biết (biết hàm truyền đạt K( )

•

ω hoặc biết phản

ứng xung g(t)). Ta phải xét tác động đầu vào theo hưởng ứng đầu ra và ngược lại. Đối với các tín

hiệu ngẫu nhiên nếu số thể hiện là đếm được và hữu hạn thì ta có thể xét hưởng ứng ra đối với

từng tác động đầu vào như bài toán trên. Nhưng khi số thể hiện của tín hiệu ngẫu nhiên là vô hạn

thì ta không thể áp dụng được những kết quả của bài toán phân tích đối với các tín hiệu xác định.

Sau đây ta sẽ xét bài toán này.

2.5.1. Bài toán tối thiểu

2.5.1.1. Bài toán:

Cho một mạch tuyến tính (có tham số không đổi và biết K( )

•

ω của nó. Biết mật độ phổ

công suất

v G( ) ω của quá trình ngẫu nhiên tác động ở đầu vào. Ta phải tìm mật độ phổ công suất

ra G() ω và hàm tự tương quan

ra R() τ của quá trình ngẫu nhiên ở đầu ra.

2.5.1.2. Giải bài toán:

Ở giáo trình "Lý thuyết mạch" ta đã biết hàm phổ biên độ phức của tín hiệu ở đầu ra mạch

vô tuyến điện tuyến tính bằng:

ra v S() K().S()

•••

ω= ω ω (2.24)

K(ω)

GV(ω)

Gra(ω))

Phổ biên độ SK(ω)

AK/2 AK/2

- ωK 0 ωK ω

Phổ năng lượng GK(ω)

δ(ω + ωK) δ(ω - ωK)

- ωK 0 ωK ω Chương 2: Tín hiệu và nhiễu

22

Trong đó: K( )

•

ω là hàm truyền của mạch đã biết.

v S( )

•

ω là phổ biên độ phức của tín hiệu vào

Chú ý: Đối với các quá trình ngẫu nhiên ta không biết được v S( )

•

ω . Không thể tính được

v S( )

•

ω , mặt khác ta đã biết theo (2.19):

2

2

vT

ra T

v

TT

2

ra T

ra 22 T

S()

S() 1

G ( ) M lim M lim TT K( )

S()

11

Mlim .G ( )

T

K( ) K( )

•

•

• →∞ →∞

•

→∞ ••

⎧ ⎫ ω ⎪ ⎪ ω ⎪ ⎪

ω= = ⎨ ⎬

⎪ ⎪ ω ⎪ ⎪ ⎩⎭

ω

= =ω

ωω

Hay:

2

ra v G() K().G()

•

ω= ω ω (2.25)

Người ta đã chứng minh được rằng hưởng ứng ra của hệ thống tuyến tính có tham số không

đổi là một quá trình ngẫu nhiên không dừng ngay cả khi tác động đầu vào là một quá trình ngẫu

nhiên dừng.

Tuy vậy, trong trường hợp hệ thống tuyến tính thụ động có suy giảm thì ở những thời điểm

t >> t

0 = 0 (thời điểm đặt tác động vào) thì quá trình ngẫu nhiên ở đầu ra sẽ được coi là dừng.

Khi đó hàm tự tương quan và mật độ phổ công suất của quá trình ngẫu nhiên ở đầu ra sẽ

liên hệ với nhau theo cặp biến đổi Wiener - Khinchin. Ta có:

j

ra ra

1

R() G()e d

2

∞

ωτ

−∞

τ =ωω

π ∫ (2.26)

Nhận xét:

Từ (2.25) ta thấy mật độ phổ công suất của hưởng ứng ra được quyết định bởi bình phương

môđun hàm truyền của mạch khi đã cho phổ công suất của tác động vào, nó không phụ thuộc gì

vào đặc tính pha tần của mạch.

Công suất của quá trình ngẫu nhiên ở đầu ra (khi quá trình ngẫu nhiên vào là dừng): Chương 2: Tín hiệu và nhiễu

23

2

2

ra ra ra v

11

R (0) G ( )d P K( ) G ( )d

22

∞∞ •

−∞ −∞

=τ= ω ω= = ω ω ω

ππ ∫∫ (2.27)

Nếu phổ công suất của tác động vào không phụ thuộc tần số, tức là

v G( ) ω =

0 N (quá

trình ngẫu nhiên có tính chất này được gọi là tạp âm trắng) thì:

2

ra 0

1

PNK()d

2

∞ •

−∞

=ωω

π ∫ (2.28)

Vì môđun hàm truyền luôn là một hàm chẵn nên:

2

ra 0

0

2

PNK()d

2

∞ •

=ωω

π ∫ (2.29)

Mặt khác, nếu gọi

0 G là phổ công suất thực tế (phần phổ công suất trải từ 0 →∞ ) thì

0 G = 2

0 N và (2.29) có thể viết lại như sau:

2

0

ra

0

G PK()d

2

∞ •

=ωω

π ∫ (2.30)

Hàm tự tương quan của quá trình ngẫu nhiên ở đầu ra trong trường hợp này sẽ bằng:

2

j

ra v

2

j

0

2

j 0

1

R() G()K()e d

2

1

NK()ed

2

N K( ) e d

2

∞ •

ωτ

−∞

∞ •

ωτ

−∞

∞ •

ωτ

−∞

τ= ω ω ω

π

=ωω

π

=ωω

π

∫

∫

∫

2

0

ra

0

G R() K()cos d

2

∞ •

τ= ω ωτω

π ∫ (2.31)

2.5.1.3. Ví dụ 1

Một mạch vô tuyến điện tuyến tính có tham số không đổi và đặc tính truyền đạt dạng chữ

nhật (hình 2.4b) chịu tác động của tạp âm trắng dừng. Tìm hàm tự tương quan của tạp âm ra.

GV(ω)

2N0

ω

0 ω1 ω0 ω2 ω

| K(ω) | Chương 2: Tín hiệu và nhiễu

24

Theo giả thiết:

v0 G( ) 2N ω= và

01 2

12

K

K( )

0(,)

• ω

ω= ⎨

∀ω∉ ω ω ⎩

Theo (2.31), ta có:

2

1

2

2 000

ra 0 2 1

2

00

0

NNK R() Kcos d= (sin sin )

sin NK 2 .cos

2

ω

ω

τ =ωτωωτ−ωτ

ππτ

Δωτ

=Δω ωτ

πτ Δωτ

∫

2

ra ra 0

sin

2 R() cos

2

Δωτ

τ =τ ωτ

Δωτ

(2.32)

Đồ thị ( ) ra R τ như hình 2.5.

(2.32) có thể viết gọn lại như sau:

ra 0ra 0 R() R ()cos τ =τωτ (2.32a)

Trong đó:

2

0ra ra

sin 2

R()

2

Δωτ

τ=σ

Δωτ

(2.32b)

(2.32b) gọi là bao của hàm tự tương quan của hưởng ứng.

12

0

2

ω +ω ω= (2.32c)

gọi là tần số trung bình. Chương 2: Tín hiệu và nhiễu

25

Vậy, bao của hàm tự tương quan của tạp âm ra là một hàm của đối số τ dạng

sin x

x

. Cực

đại của hàm tự tương quan của tạp âm ra đạt tại τ = 0 và bằng

2

ra σ , tức là bằng công suất trung

bình của tạp âm ra.

Bây giờ ta sẽ chuyển sang xét một tham số vật lý nữa để đánh giá mức độ truyền tạp âm qua

mạch tuyến tính.

2.5.1.4. Giải thông tạp âm

Định nghĩa:

Giải thông tạp âm của

mạch tuyến tính (hay bộ lọc

tuyến tính) được xác định theo

biểu thức sau:

2

0

t 2

K( ) d

K( ) m

©

ax

∞ •

Δ

•

ωω

Δω =

ω

∫

(2.33)

2π/Δω

Rra(τ)

σ2

ra

0

τ

ω0 ω

Δωta

| K(ω)|

2

| K(ω)|

2

max

Hình 2.6.

Hình 2.5. Chương 2: Tín hiệu và nhiễu

26

Ý nghĩa hình học:

t© Δω chính là đáy của hình chữ nhật có diện tích bằng diện tích của

miền giới hạn bởi đường cong

2

K( )

•

ω và nửa trục hoành (0, ∞); còn chiều cao của hình chữ

nhật này là

2

K( )

•

ω max.

Ý nghĩa vật lý:

t© Δω đặc trưng cho khả năng làm suy giảm tạp âm của các bộ lọc tuyến tính. Với cùng

0 K( )

•

ω , bộ lọc nào có

t© Δω càng hẹp thì công suất tạp âm đầu ra của bộ lọc ấy càng bé.

2.5.2. Bài toán tối đa

R G() ω và

R B() τ chưa đặc trưng đầy đủ cho quá trình ngẫu nhiên.

Nội dung: Tìm hàm mật độ xác suất của tín hiệu ở đầu ra mạch vô tuyến điện tuyến tính.

2.5.2.1. Mở đầu

Tìm mật độ xác suất n chiều của tín hiệu ngẫu nhiên ở đầu ra mạch tuyến tính là bài toán rất

khó, nó không giải được dưới dạng tổng quát. Dưới đây chỉ xét hai trường hợp đơn giản:

- Tìm mật độ xác suất một chiều của tín hiệu ra bộ lọc tuyến tính khi tác động đầu vào là tín

hiệu ngẫu nhiên chuẩn (có vô hạn thể hiện). Trong trường hợp này người ta đã chứng minh được

tín hiệu ra cũng là một tín hiệu ngẫu nhiên chuẩn.

- Đặt vào bộ lọc tuyến tính một tín hiệu ngẫu nhiên không chuẩn. Nếu

t

1

2F

© Δω

π

(F là

bề rộng phổ của tín hiệu vào) thì tín hiệu ngẫu nhiên ở đầu ra sẽ có phân bố tiệm cận chuẩn.

Người ta bảo đó là sự chuẩn hoá (Gauss hoá) các quá trình ngẫu nhiên không chuẩn bằng bộ lọc

giải hẹp.

2.5.2.2. Ví dụ 2

Cho tạp âm giải hẹp, chuẩn có dạng:

0 n(t) c(t)c t s(t)sin t A(t)c t ) 00 os os( =ω+ω= ω−ϕ (*)

với c(t) và s(t) có phân bố chuẩn cùng công suất trung bình và với

s(t)

arctg

c(t)

ϕ=

22

A(t) c (t) s (t) =+ - đường bao của nhiễu. Chương 2: Tín hiệu và nhiễu

27

Công suất trung bình của cả hai thành phần của nhiễu bằng nhau và bằng hằng số:

222

cs σ=σ=σ . Khi n(t) dừng, người ta coi là hai thành phần của nhiễu không tương quan.

Tác động n(t) lên bộ tách sóng tuyến tính. Hãy tìm mật độ xác suất một chiều của điện áp ra

bộ tách sóng biết rằng bộ tách sóng không gây méo đường bao và không gây thêm một lượng dịch

pha nào. Thực chất của bài toán là phải tìm (A) v 11 WµW() ϕ .

Trong giáo trình "lý thuyết xác suất", ta đã có công thức tìm mật độ xác suất một chiều của

từng đại lượng ngẫu nhiên theo mật độ xác suất đồng thời của chúng, nên ta có:

2

00

(A) (A, )d ; ( ) (A, )dA 12 12 WW WW

π∞

=ϕϕϕ=ϕ ∫∫

Do đó, vấn đề ở đây là phải tìm (A, ) 2 W ϕ .

Vì bộ tách sóng không gây méo đường bao và không gây thêm một lượng dịch pha nào nên

(A, ) 2 W ϕ ở đầu ra cũng chính là (A, ) 2 W ϕ ở đầu vào.

Tìm (A, ) 2 W ϕ : Vì đầu bài chỉ cho (c) v (s) 11 Wµ W nên ta phải tìm (A, ) 2 W ϕ theo

(c,s) 2 W .

Theo giả thiết c(t) và s(t) không tương quan nên:

(c,s) 2 W = (c). (s) 11 WW (2.34)

()

22 22

22

c2 s2

2 22

11 1cs

Wc,s e . e exp

22 22

−δ −δ ⎧⎫ + ⎪⎪

⇒= = − ⎨⎬

πδ πδ πδ δ ⎪⎪ ⎩⎭

()

2

2 22

11

Wc,s exp A

22

⎧ ⎫

=− ⎨ ⎬

πδ δ ⎩⎭

(2.35)

Ta thấy xác suất để một điểm có toạ độ (c,s) trong hệ toạ độ Đêcac rơi vào một yếu tố diện

tích dcds sẽ bằng: (c,s) dcds 2 P W dcds = . Để ý đến (*) ta thấy xác suất này cũng chính là xác

suất để một điểm có toạ độ (A, ) ϕ trong hệ toạ độ cực rơi vào một yếu tố diện tích dAdϕ. Ta có: Chương 2: Tín hiệu và nhiễu

28

(c,s) (A, ) dcds 2 2 P W dcds = W dAd =ϕϕ

(2.36)

Từ đó:

(A, ) (c,s) 22

dcds

WW dAd

ϕ=

ϕ

(**)

Từ H.2.7 ta thấy với dA, dϕ đủ nhỏ ta có: dc ds = Adϕ. DA

Từ (**) ta có:

() ()

2

22 22

1A WA, Wc,s exp

22

⎧ ⎫ ⎪ ⎪

ϕ= = − ⎨ ⎬

πδδ ⎪ ⎪ ⎩⎭

(2.37)

Do đó: () ( )

22 2

12 22

00

AA WA WA, d exp d

22

ππ ⎧⎫ ⎪⎪

=ϕϕ= ϕ ⎨⎬

πδ δ ⎪⎪ ⎩⎭

∫∫

()

2

1 22

AA WA exp

2

⎧⎫ ⎪⎪

=− ⎨⎬

σδ ⎪⎪ ⎩⎭

(2.38)

(2.38) gọi là phân bố Reyleigh (H.2.8).

dϕ

dA

S + dS

S

S

ϕ

0 c c + dc c

A

Hình 2.7. Chương 2: Tín hiệu và nhiễu

29

Vậy nhiễu giải hẹp mà trị tức thời có phân bố chuẩn thì phân bố của đường bao là phân bố

không đối xứng Reyleigh. Sở dĩ như vậy vì giá trị tức thời có cả giá trị âm và giá trị dương nên

phân bố mật độ xác suất sẽ đối xứng qua trục tung (phân bố Gausse). Còn xét đường bao tức là

chỉ xét biên độ (giá trị dương) nên mật độ phân bố xác suất là đường cong không đối xứng và chỉ

tồn tại ở nửa dương trục hoành.

() ( )

2

12 22

00

1A A WWA,dA exp dA

2 2

∞∞ ⎧ ⎫ ⎪ ⎪

ϕ= ϕ = − ⎨ ⎬

π δδ ⎪ ⎪ ⎩⎭

∫∫ () () 11

0

1

WWAdA

2

∞

ϕ=

π ∫ (2.39)

Vậy mật độ phân bố xác suất pha đầu của nhiễu giải hẹp, chuẩn là phân bố đều trong

khoảng (0,2 π ). (H.2.9).

2.5.2.3. Ví dụ 3:

Ở đầu vào bộ tách sóng tuyến tính đặt hỗn hợp tín hiệu và nhiễu:

y(t) = x(t) + n(t)

Với:

0 x(t) U c t 0 os =ω là tín hiệu xác định.

[] n n(t) A (t)c t (t) 0 os =ω−ϕ là nhiễu giải hẹp, chuẩn.

Tìm mật độ phân bố xác suất đường bao và pha của điện áp đầu ra bộ tách sóng tuyến tính.

Ta có:

[]

00

00yy

y(t) U c t c(t)c t s(t)sin t

U c(t) c t s(t)sin t A (t)c t (t)

00

00

os os

os os

=ω+ ω+ω

⎡ ⎤ = + ω+ ω= ω−ϕ ⎣ ⎦

Trong đó: []

2 2

y0 A(t) U c(t) s(t) =++ là bao của hỗn hợp tín hiệu và nhiễu.

y (t)

c(t) 0

s(t)

arctang

U

ϕ=

+

là pha của hỗn hợp tín hiệu và nhiễu.

Làm tương tự như VD2, ta có:

W1(A/σ)

0,6

0,4

0,2

0 1 2 3 A/σ

Hình 2.8.

W1(ϕ)

1/2π

0 2π ϕ

Hình 2.9. Chương 2: Tín hiệu và nhiễu

30

()

() () ()

22

yy0y0

1y 0 22 2

At At U At U

WA exp .I

⎧⎫ ++ ⎧ ⎫ ⎪ ⎪⎪ ⎪

=− ⎨ ⎬⎨ ⎬

δδ δ ⎪ ⎪ ⎩⎭ ⎪⎪ ⎩⎭

(2.40)

(2.40) gọi là phân bố Rice (H.2.10a).

I 0 là hàm Bessel biến dạng loại 1 cấp 0.

2

zc

0

0

1

I(z) e d

2

os

π

θ

= θ

π ∫

I 0 (z) có thể viết dưới dạng chuỗi vô hạn sau:

2n

0 2

n0

1z

I(z)

2 (n!)

∞

=

⎛⎞

= ⎜⎟

⎝⎠

∑

Khi z

2

2

z4

0

z

I(z) 1 ... e

4

=+ + ≈

Nhận xét:

- Khi a = 0 ⇔ không có tín hiệu, chỉ có nhiễu giải hẹp, chuẩn ⇒ phân bố Rice trở về

phân bố Reyleigh.

- a càng lớn, phân bố Rice càng tiến tới phân bố Gausse.

Giải thích:

a >> 1 ⇔ tín hiệu mạnh, nhiễu yếu. Tín hiệu tác dụng với thành phần không trực giao với

nó của nhiễu (khi tín hiệu càng mạnh thì hỗn hợp này càng ít khác tín hiệu), còn thành phần của

nhiễu trực giao với tín hiệu thì không chịu sự "chèn ép" của tín hiệu. Do đó mật độ phân bố xác

suất bao của hỗn hợp sẽ mang đặc điểm của thành phần nhiễu trực giao với tín hiệu.

()

2 2

0y 0y 0 y 0

1y 22 22

Ucos Ucos Usin U 1

W exp 1 exp

2 2 22 2

⎧ ⎫ ⎡⎤ ⎛⎞ ⎧⎫ ϕ ϕϕ ⎪⎪ ⎪ ⎪

ϕ= − + +φ − ⎢⎥ ⎜⎟ ⎨⎬ ⎨ ⎬ ⎜⎟ π δδ ⎪⎪ ⎢ ⎥ πδ δ ⎪ ⎪ ⎩⎭ ⎝⎠ ⎣⎦ ⎩⎭

(2.41)

Trong đó:

2

z

2

0

2

(z) e d

2

−θ

φ= θ

π ∫ là tích phân xác suất.

Đồ thị (2.41) biểu diễn trên hình H.2.10b.

W1(ϕy)

a = 5

a = 2 U0/σ = 0

a = U0/σ = 0

a = 2

a = 4

0,2

0,4

W(Ay/σ) Chương 2: Tín hiệu và nhiễu

31

Nhận xét:

- a = 0 ⇔ chỉ có nhiễu

y () 1 W ϕ chính là () 1 W ϕ đã xét ở VD2.

- a >> 1 ⇒ đường cong

y () 1 W ϕ càng nhọn, hẹp.

Giải thích:

Với a càng lớn thì có thể bỏ qua ảnh hưởng xấu của nhiễu. Do đó đường bao (biên độ tín

hiệu) không có gia số (không thăng giáng) và cũng không có sai pha. Khi đó

y ϕ nhận giá trị "0"

trong khoảng (- π, π) với xác suất lớn.

2.6. BIỂU DIỄN PHỨC CHO THỂ HIỆN CỦA TÍN HIỆU NGẪU NHIÊN - TÍN HIỆU

GIẢI HẸP

2.6.1. Cặp biến đổi Hilbert và tín hiệu giải tích

2.6.1.1. Nhắc lại cách biểu diễn một dao động điều hoà dưới dạng phức

Cho: x(t) = ( ) 00 Ac t A(t)c 0 os os (t) ω+ϕ= θ (2.42)

Trong đó:

0 ω : tần số trung tâm; (t) θ : pha đầy đủ;

0 ϕ : pha đầu.

Trong "Lý thuyết mạch", người ta rất hay

dùng cách biểu diễn x(t) dưới dạng phức sau:

j(t)

x(t) x(t) jx(t) A(t)e

•∧

θ

=+ = (2.43)

Trong đó:

x(t) = Re [ x(t)

•

];

x(t)

∧

= Im [ x(t)

•

] =

0 Asin(t) θ

Im[x(t)]

x(t) M

A

θ(t)

0 x(t) Re[x(t)]

Hình 2.11 Chương 2: Tín hiệu và nhiễu

32

Ta có thể biểu diễn x(t)

•

dưới dạng một vecteur trên mặt phẳng phức.

Khi A(t) = const thì quỹ tích của điểm M sẽ là một vòng tròn tâm O, bán kính OM.

(t) d (t) dt ω=θ là tần số của dao động (H.2.11)

2.6.1.2. Cặp biến đổi Hilbert - Tín hiệu giải tích

a. Cặp biến đổi Hilbert và tín hiệu giải tích:

Để dễ dàng biểu diễn dưới dạng phức những thể hiện phức tạp của các quá trình ngẫu nhiên,

người ta dùng cặp biến đổi Hilbert. Nó cho phép ta tìm x(t)

∧

khi biết x(t) và ngược lại.

Hilbert đã chứng tỏ rằng phần thực và phần ảo của hàm phức (2.43) liên hệ với nhau bởi các

biến đổi tích phân đơn trị hai chiều sau:

x( )

x(t) Im (t) d

t

1

[x ]=

∞ ∧•

−∞

τ

= τ=

π−τ ∫ h [x(t)] (2.44)

x( )

x(t) d Re (t)

t

1

[x ]

∧ ∞ •

−∞

τ

= −τ==

π−τ ∫ h

1 −

[x(t)] (2.45)

Cặp công thức trên được gọi là cặp biến đổi Hilbert. Trong đó (2.44) gọi là biến đổi thuận

Hilbert, còn (2.45) gọi là biến đổi ngược Hilbert.

Chú ý:

Cũng giống như tính chất của các tích phân, biến đổi Hilbert là một phép biến đổi tuyến

tính.

(Một phép biến đổi f được gọi là tuyến tính nếu có:

f(x1 + x 2 ) = f(x1 ) + f(x 2 )

f(kx) = k f(x), k = const)

Các hàm x(t) và x(t)

∧

được gọi là liên hiệp Hilbert đối với nhau. Tín hiệu phức x(t)

•

có

phần thực và phần ảo thoả mãn cặp biến đổi Hilbert gọi là tín hiệu giải tích (tương ứng với tín

hiệu thực x(t)).

b. Biến đổi Hilbert đối với tín hiệu hình sin:

Trong mục này ta sẽ chứng tỏ ct 0 osω và t 0 sinω thoả mãn cặp biến đổi H. Thật vậy: Chương 2: Tín hiệu và nhiễu

33

1c 1c (t) t

x(t) d d

tt

1c (t).c tsin(t).sint

d

t

ctc(t) sintsin(t)

dd

tt

000

0000

00 00

os os[ ]

os os ]

os os

∞∞ ∧

−∞ −∞

∞

−∞

∞∞

−∞ −∞

ωτ ω −τ−ω =τ= τ=

π−τ π −τ

ω−τ ω+ω−τ ω =τ=

π−τ

ωω−τ ωω−τ

=τ+τ

π−τ π−τ

∫∫

∫

∫∫

Chú ý rằng:

c

dz 0

osaz

z

∞

−∞

= ∫ và

sin

dz

az

z

∞

−∞

= π ∫

0 x(t) sin t

∧

⇒=ω

Vậy ( 0 sin t ω ) là liên hợp H của ( 0 ct osω )

Tương tự ( - 0 ct osω ) là liên hợp phức H của ( 0 sin t ω )

c. Biến đổi H đối với các hàm tổng quát hơn:

- Đối với các hàm tuần hoàn x(t):

Trong "Lý thuyết mạch" ta đã biết, chuỗi Fourier của hàm tuần hoàn (thoả mãn điều kiện

Dirichlet) là:

KK0

K0

x(t) (a c K t b sinK t) 0 os

∞

=

=ω+ω ∑ (2.46)

Vì biến đổi H là biến đổi tuyến tính nên biến đổi H của tổng bằng tổng các biến đổi H của

các hàm thành phần, nên:

x(t)

∧

= h [x(t)]

KK0

K0

(a sinK t b c K t) 0 os

∞

=

=ω−ω ∑ (2.47)

(2.46) và (2.47) gọi là chuỗi liên hiệp H.

- x(t) không tuần hoàn:

Nếu hàm không tuần hoàn x(t) khả tích tuyệt đối thì khai triển Fourier của nó là:

0

1

x(t) a( )c t b( )sin t

2

[os ]d

∞

=ωω+ωωω

π ∫ (2.48)

Khi đó: Chương 2: Tín hiệu và nhiễu

34

x(t)

∧

= h [x(t)] =

1

2π

h

0

[a()cost+b()sint]d

∞ ⎧ ⎫ ⎪ ⎪

ω ωωωω= ⎨ ⎬

⎪ ⎪ ⎩⎭

∫

{}

0

1

H[a( ) cos t] + H[b( ) sin t] d

2

∞

= ωω ωωω

π ∫

0

1

[a( )sin t - b( )cos t]d

2

∞

= ωω ωωω

π ∫ (2.49)

(2.48) và (2.49) gọi là các tích phân liên hiệp H.

d. Các yếu tố của tín hiệu giải tích:

Từ (2.46) và (2.47) (hoặc từ (2.48) và (2.49)) ta xây dựng được tín hiệu giải tích ứng với tín

hiệu thực x(t) như sau:

j(t)

x(t) x(t) jx(t) A(t)e

•∧

θ

=+ =

x(t) = Re [ x(t)

•

] = A(t)cos (t) θ (a)

x(t)

∧

= Im [ x(t)

•

] = A(t)sin (t) θ (b)

- Đường bao của tín hiệu giải tích:

Từ (a) và (b) ta thấy:

2

2

A(t) x (t) x (t)

∧

=+ (2.50)

A(t) đặc trưng cho sự biến

thiên (dạng biến thiên) của biên

độ của tín hiệu (H.2.12).

A(t) được gọi là đường bao

của tín hiệu (còn gọi là biên độ

biến thiên hay biên độ tức thời của

tín hiệu).

- Pha tức thời của tín hiệu

giải tích:

Ký hiệu pha tức thời: (t) θ

bằng:

x(t)

(t) arctg

x(t)

∧

θ= (2.51)

t

x(t)

A(t)

Hình 2.12 Chương 2: Tín hiệu và nhiễu

35

- Tần số góc tức thời của tín hiệu giải tích

(t) ω :

d (t) x(t)

(t) arctg

dt x(t)

∧ ′

⎡⎤

θ ⎢⎥ ω= = =

⎢⎥

⎢⎥ ⎣⎦

22

2

2

x(t) x(t)

x(t)x (t) x(t)x (t)

x(t) x(t) x(t)

1

x(t)

∧

∧∧

∧∧

′

⎡⎤

′

⎢⎥

′ − ⎣⎦

=

+

+

(2.52)

- Tính chất của A(t):

+ A(t) ≥ x(t)

+ Khi x(t)

∧

= 0 ⇒ A(t) = x(t)

+ Xét:

2

2

x(t).x (t) x(t).x (t)

A(t)

x(t) x(t)

∧∧

∧

′

′ +

′ =

+

Khi x(t)

∧

= 0 ⇒ A'(t) = x'(t)

Vậy khi x(t)

∧

= 0 thì độ nghiêng của A(t) và x(t) là như nhau.

- Kết luận:

Đối với các tín hiệu ngẫu nhiên thì các yếu tố của tín hiệu là ngẫu nhiên. Nhờ có

khái niệm tín hiệu giải tích nên ta mới nghiên cứu các tính chất thống kê của các yếu

tố của nó được thuận lợi, đặc biệt là trong tính toán.

2.6.2. Tín hiệu giải rộng và giải hẹp

2.6.2.1. Tín hiệu giải rộng

Người ta gọi một tín hiệu là tín hiệu giải rộng

nếu bề rộng phổ của nó thoả mãn bất đẳng thức

sau:

0

1

Δω ≥

ω

(2.53)

Nhìn chung tín hiệu giải rộng là tín hiệu mà

bề rộng phổ của nó có thể so sánh được với

0 ω .

Trong đó

21 Δω=ω −ω và

21

0

2

ω +ω ω= gọi là tần số trung tâm (xem H.2.13).

Δω

0 ω1 ω0 ω2

ω

G(ω)

Hình 2.13 Chương 2: Tín hiệu và nhiễu

36

Ví dụ: Các tín hiệu điều tần, điều xung, điều chế mã xung, manip tần số, manip pha,... là

các tín hiệu giải rộng.

2.6.2.2. Tín hiệu giải hẹp

Nếu tín hiệu có bề rộng phổ thoả mãn:

0

1

Δω ≤

ω

(2.54)

Thì nó được gọi là tín hiệu giải hẹp. (H.2.14).

Ví dụ: tín hiệu giải hẹp là các tín hiệu như:

tín hiệu cao tần hình sin, tín hiệu cao tần điều biên,

tín hiệu đơn biên ....

Nhìn chung tín hiệu giải hẹp là tín hiệu mà bề

rộng phổ của nó khá nhỏ hơn so với tần số

0 ω .

2.6.2.3. Biểu diễn tín hiệu giải hẹp

Nếu một tín hiệu giải hẹp có biểu thức giải tích sau:

0 x(t) A(t)cos[ t (t)] = A(t)cos (t) = ω−ϕ θ (2.55)

Trong đó:

0t ω là thành phần thay đổi tuyến tính của pha chạy (pha tức thời)

(t) ϕ là thành phần thay đổi chậm của pha chạy

A(t) là đường bao của tín hiệu

Thì (2.55) có thể khai triển như sau:

00

00

x(t) A(t)cos tcos (t) A(t)sin tsin (t)

A(t)cos (t)cos t A(t) sin (t) sin t

= ωϕ+ ωϕ

=ϕω+ϕω

= c(t). cos 0t ω + s(t). sin 0t ω (2.56)

c(t). cos 0t ω là tín hiệu điều biên biến đổi chậm

s(t). sin 0t ω là tín hiệu điều biên biến đổi chậm

Vậy một tín hiệu giải hẹp hình sin bao giờ cũng có thể biểu diễn dưới dạng tổng của hai tín

hiệu điều biên biến đổi chậm, với các yếu tố xác định như sau:

0 ω1 ω0 ω2 ω

G(ω) Δω

Hình 2.14 Chương 2: Tín hiệu và nhiễu

37

22

A(t) c (t) s (t)

s(t)

(t) arctg

c(t)

d(t)

(t)

dt

⎧

⎪ =+

⎪

⎪

ϕ= ⎨

⎪

⎪ θ

ω= ⎪

⎩

(2.57)

Rõ ràng là các số hạng ở vế phải (2.56) thoả mãn cặp biến đổi Hilbert.

Việc biểu diễn một tín hiệu giải hẹp thành tổng của hai tín hiệu điều biên biến thiên chậm sẽ

làm cho việc phân tích mạch vô tuyến điện dưới tác động của nó đơn giản đi nhiều. Ta sẽ xét lại

bài toán này ở phần sau.

2.7. BIỂU DIỄN HÌNH HỌC CHO THỂ HIỆN CỦA TÍN HIỆU NGẪU NHIÊN

2.7.1. Khai triển trực giao và biểu diễn vecteur của tín hiệu

2.7.1.1. Năng lượng của chuỗi Kachennhicov

Ta đã biết rất rõ khai triển trực giao Fourier cho các hàm x(t) có phổ vô hạn. ở giáo trình

"Lý thuyết mạch", ta cũng biết rằng một hàm x(t) có phổ không chứa tần số lớn hơn Fc có thể

phân tích thành chuỗi trực giao Kachennhicov sau:

c

c K

sin 2 F (t K t)

x(t) x(K t)

2F(t Kt)

∞

=−∞

π −Δ

=Δ

π−Δ ∑ (2.58)

Trong đó:

c t12F Δ=

Nếu ta chỉ xét tín hiệu có phổ hữu hạn x(t) trong khoảng thời gian T hữu hạn thì ta có biểu

thức gần đúng sau để tính năng lượng của nó:

2 T2 T2 n

2 c

K

c K1 T2 T2

sin (t K t)

Ex(t)dt x dt

(t K t)

= −−

⎡⎤ ω−Δ

=≈ ⎢⎥

ω−Δ ⎢⎥ ⎣⎦

∑ ∫∫ (*)

Trong đó n là số các giá trị rời rạc (còn gọi là các giá trị mẫu) của thể hiện tín hiệu x(t)

trong khoảng quan sát T; còn xK là giá trị mẫu thứ K của x(t) tại thời điểm rời rạc Kt Δ . Để cho

gọn, ta đặt

c (t K t) ω−Δ=λ , khi đó (*) có dạng:

2 T2 T2 2 nn

2

KK 2

cc K1 K1 T2 T2

1 sin 1 sin

Exdxd

== −−

⎡⎤ λλ

≈ λ= λ ⎢⎥

ωλω λ ⎢⎥ ⎣⎦

∑∑ ∫∫

Ta có:

T2 2

2

T2

sin

d

−

λ

λ≈π

λ ∫ (với T khá lớn) Chương 2: Tín hiệu và nhiễu

38

nn

22

KK

cc K1 K1

1

Ex x

2F ==

π

⇒= =

ω ∑∑ (2.59)

(2.59) cho ta tính được năng lượng của chuỗi

2.7.1.2. Biểu diễn x(t) thành vectơ x

→

trong không gian n chiều

Khai triển Kachennhicov (2.58) là một dạng khai triển trực giao. Các hàm

c

K

c

sin (t K t)

(t)

(t K t)

ω−Δ

ψ=

ω−Δ

là các hàm trực giao.

c cc

cc

iK sin (t K t) sin (t i t)

.dt

(t K t) (t i t) 0iK

∞

−∞

⎛⎞ πω = ⎧ ω−Δ ω−Δ

= ⎜⎟ ⎨ ⎜⎟ ω−Δ ω−Δ ≠ ⎩ ⎝⎠

∫

Vì vậy ta có thể coi mỗi hàm là một vecteur đơn vị trên hệ trục toạ độ trực giao. Khi T hữu

hạn thì Kmax = n cũng sẽ hữu hạn. Khi đó ta có thể coi x(t) là một vectơ x

→

trong không gian n

chiều có các thành phần (hình chiếu) trên các trục toạ độ tương ứng là x(K t) Δ , (K = 1, n ).

{ }

{} 12 n

x(t) x(t t),x(t 2 t),...,x(t n t)

x(t) x ,x ,...,x x

→

⇔ −Δ − Δ − Δ

⇔⇔

Theo định nghĩa, độ dài (hay chuẩn) của vecteur x

→

sẽ là:

n

2

K

K1

xx(x,x)

→→→

=

⎛⎞

== ⎜⎟

⎜⎟

⎝⎠

∑ (2.60)

Để ý đến (2.59), ta có:

cc x2FE2FT.PnP

→

== = (2.61)

( c

T

n2FT

t

==

Δ

)

Trong đó P là công suất của thể hiện tín hiệu trong khoảng hữu hạn T. Như vậy, với thời

hạn quan sát và bề rộng phổ của thể hiện cho trước thì độ dài của vecteur biểu diễn tỷ lệ với căn

bậc hai công suất trung bình của nó. Nếu cho trước công suất trung bình P thì độ dài của vecteur

x

→

sẽ tỷ lệ với n (tức là tỷ lệ với căn bậc hai của đáy tín hiệu B =

c

n

FT

2

= )

Nhận xét: Chương 2: Tín hiệu và nhiễu

39

Như vậy, với cùng một công suất trung bình tín hiệu nào có đáy càng lớn (tức là tín hiệu

càng phức tạp) thì độ dài của vecteur biểu diễn nó càng lớn. Khi đáy của tín hiệu càng lớn thì độ

dài của vecteur tín hiệu càng lớn → vecteur tổng của tín hiệu và nhiễu giải hẹp càng ít khác

vecteur tín hiệu → ta sẽ nhận đúng được tín hiệu với xác suất cao. Để tính chống nhiễu của tín

hiệu càng cao thì yêu cầu B càng phải lớn.

Trong trường hợp x(t) không rời rạc hoá:

T

2

x

0

Ex(t)dt = ∫ . Khi đó chuẩn của vecteur sẽ

là:

T

2

cx c

0

x(x,x)2FE x2Fx(t)dt

→→→ →

==⇒= ∫ (2.62)

Người ta còn gọi không gian mà chuẩn của vecteur cho bởi tích vô hướng (2.62) là không

gian Hilbert và ký hiệu là L 2

. Không gian L 2

là sự mở rộng trực tiếp của không gian Euclide hữu

hạn chiều lên số chiều vô hạn.

2.7.2. Mật độ xác suất của vecteur ngẫu nhiên - Khoảng cách giữa hai vecteur tín hiệu

2.7.2.1. Mật độ xác suất của vecteur ngẫu nhiên

a. Vecteur tín hiệu:

Để tiếp tục những vấn đề sau này được thuận tiện, ta đưa vào khái niệm vecteur tín hiệu.

Định nghĩa:

Vecteur tín hiệu

0 x

→

là vecteur sau:

0

x

x

n

→ →Δ

= (2.63)

Trong đó x

→

là vecteur biểu diễn tín hiệu x(t) trong không gian n chiều.

Tính chất:

+

0 x

→

có phương và chiều trùng với x

→

+ Độ lớn (modul):

0

x

xP

n

→ →

==

b. Xác suất phân bố của mút vecteur

0 x

→

và miền xác định của nó

Trong không gian tín hiệu, tín hiệu được biểu diễn bởi vecteur. Do đó xác suất để tồn tại tín

hiệu đó ở một miền (nói riêng: tại một điểm) nào đấy của không gian chính là xác suất để mút

vecteur tín hiệu rơi vào miền ấy (nói riêng: điểm ấy) của không gian. Chương 2: Tín hiệu và nhiễu

40

Nếu x(t) là xác định thì mút của vecteur

0 x

→

chỉ chiếm một điểm trong không gian n chiều.

Còn nếu x(t) là ngẫu nhiên có một tập các thể hiện { } i

x(t) thì mút vecteur

0 x

→

của nó sẽ chiếm

một miền nào đó trong không gian n chiều với thể tích:

12 n V x . x .... x = ΔΔ Δ . Khi ấy, xác suất

để tồn tại tín hiệu ngẫu nhiên trong miền có thể tích dV sẽ là:

{ }

() 12 n 1 2 n 0

Pt/hNN dV P dV

dP x ,x ,...,x dx dx ...dx (x )dV nn

{mót vecteur t/h ®ã } =

WW

→

∈= ∈

== =

(2.64)

Sau đây ta sẽ xét miền xác định của một số dạng tín hiệu ngẫu nhiên:

- Các thể hiện của tín hiệu phát có cùng đáy, cùng công suất:

Khi đó miền các định của vecteur tín hiệu phát sẽ là mặt cầu có bán kính bằng chuẩn của

vecteur tín hiệu phát

0 xP

→

= và có tâm ở gốc toạ độ của vecteur ấy. (Sở dĩ như vậy vì

0 x

→

có chuẩn không đổi nhưng phương và chiều của nó thay đổi ngẫu nhiên).

- Tạp âm trắng:

Ta đã biết rằng các thể hiện

i

n(t) của tạp âm trắng n(t) có cùng công suất P n . Như vậy

miền xác định của tạp âm trắng là mặt cầu có bán kính bằng

n P , có tâm là gốc của vecteur tạp

âm

0 n

→

.

- Tổng của tín hiệu x(t) và tạp âm n(t):

y(t) = x(t) + n(t)

00 0 0 y yx n y P

→→→ →

⇒=+ ⇒ =

Nếu x(t) và n(t) không tương quan thì:

yxn PPP =+ (vì

yxn B (0) B (0) B (0) = + )

2

xn xn 00 yPP yPP

→→

⇒=+⇒ =+

222

000 yxn

→→→

⇒= + (*) Chương 2: Tín hiệu và nhiễu

41

Từ (*) ta thấy

0 x

→

⊥

0 n

→

và

0 y

→

là cạnh huyền của một tam giác vuông có hai cạnh là

0 x

→

và

0 n

→

.

Nếu x(t) xác định thì miền xác định của mút

0 y

→

sẽ là đường tròn đáy của hình nón có đỉnh

ở gốc tọa độ, chiều cao bằng

0 x

→

và bán kính bằng

0 n

→

. (H.2.15a).

Nếu x(t) chỉ là một thể hiện nào đó của quá trình ngẫu nhiên X(t) có các thể hiện cùng công

suất thì lúc đó miền xác định của mút

0 y

→

sẽ là một mặt cầu có bán kính bằng

xn PP + và có

tâm ở gốc toạ độ (H.2.15b).

2.7.2.2. Khoảng cách giữa hai vecteur tín hiệu

Để đánh giá định lượng sự khác nhau giữa hai vecteur tín hiệu, ta đưa ra khái niệm khoảng

cách giữa hai vecteur tín hiệu.

Định nghĩa:

Khoảng cách giữa hai vecteur tín hiệu

0 u

→

và

0 v

→

được xác định theo biểu thức sau:

n0

x0

y0

0

Hình 2.15a

0

Hình 2.15b Chương 2: Tín hiệu và nhiễu

42

00 0 0

n

2

00 K K

K1

1

d(u ,v ) u v u v

n

1

d(u ,v ) (u v )

n

→→Δ → → → →

→→

=

=− = −

⇒= − ∑

Hay:

nnn

222

00 K K KK 22

K1 K1 K1

112

d(u,v) u v u .v

n (n) (n)

→→

===

=+ − ∑∑∑

Ta có:

22 n

2

K00000 2

K1

22 n

2

K00000 2

K1

n

KK 00 0 0 00

K1

11

uuuu.uc(u,u)

n (n)

11

vvvv.vc(v,v)

n (n)

1

u.v (u,v) u .v c (u,v)

n

os

os

os

→→→→→→

=

→→→→→→

=

→→ → → →→

=

⎧

⎪ ===

⎪

⎪

⎪ ⎪

=== ⎨

⎪

⎪

⎪ ==

⎪

⎪ ⎩

∑

∑

∑

22

2

00 0 0 0 0 00

22

2

00 0 0 0 0

d(u,v) u v 2 u . v c (u,v)

d(u,v) u v 2 u . v c

os

os

→→ → → → → →→

→→ → → → →

⇒=+−

=+ − ϕ

Trong đó ϕ là góc hợp bởi

0 u

→

và

0 v

→

trong không gian n chiều.

00

00

u.v

c

u.v

os

→→

→→ ϕ= (2.65)

2

00 u v uv d(u,v) P P 2 PP cos

→→

=+− ϕ (2.66)

Nếu ta không rời rạc hoá tín hiệu thì:

T

00 0 0

0

1

d(u ,v ) u v dt

T

2

[u(t) - v(t)]

→→

=−= ∫ Chương 2: Tín hiệu và nhiễu

43

Hay

TTT

2

00

000

112

d(u,v) dt v dt v dt

TTT

22

u (t) (t) u(t). (t) =+− ∫∫∫

uv uv

uv uv

PP2R(t,t)

PP2R(0)

=+−

=+−

Trong đó

uv R(0) là hàm tương quan chéo của tín hiệu u(t) và v(t).

uv u v uv R (0) D (t).D (t) (0) =ρ

2

00 d(u,v) = uv uvuv PP2P.P (0) +− ρ (2.67)

So sánh (2.66) và (2.67) ta thấy ngay ý nghĩa hình học của hàm tương quan chéo chuẩn hoá:

uv (0) ρ đóng vai trò cosin chỉ phương của hai vecteur tín hiệu.

uv c(0) os = ϕρ (2.68)

Kết luận:

- Với một mức nhiễu xác định, xác suất thu đúng càng cao khi các thể hiện của tín hiệu

càng cách xa nhau.

- Khoảng cách giữa hai mút của hai vecteur tín hiệu càng lớn khi độ dài hai vecteur càng

lớn.

2.7.3. Khái niệm về máy thu tối ưu

2.7.3.1. Máy thu tối ưu

Một cách tổng quát, ta coi một máy thu đặc trưng bởi một toán tử thu ψ (H.2.17). Yêu cầu

của toán tử thu ψ là tác dụng vào y(t) (là tín hiệu vào) phải cho ra tín hiệu đã phát x(t).

Nếu ta phát đi một thể hiện nào đó của một quá trình ngẫu nhiên X(t):

{ } i

X(t) x (t) (i 1,m) ==

Ta coi những thể hiện này có cùng công suất P x , có cùng thời

hạn T và có cùng bề rộng phổ F c .

Giả thiết: trong quá trình truyền từ nơi phát đến nơi thu chỉ có

tạp âm trắng Gausse n(t), các tín hiệu phát là đồng xác suất

Vecteur tín hiệu ta nhận được:

0 yyn

→→

=

ψ

y(t) x(t)

Hình 2.16. Chương 2: Tín hiệu và nhiễu

44

Nếu

0 y

→

này gần với vecteur tín hiệu

j0 x

→

nhất so với các vecteur tín hiệu khác, tức là:

j i

x yyx

nn nn

→ →→→

−≤− Với i: i 1,m vµ i j ∀ =≠

Khi đó máy thu có ψ tác dụng lên y

→

cho ra

j

x

→

:

K [y]=x

→→

ψ , sẽ được gọi là máy thu

tối ưu (theo nghĩa Kachennhicov trong trường hợp các tín hiệu ( ) i

xt là đồng xác suất).

2.7.3.2. Liên hệ giữa máy thu tối ưu K và máy thu theo tiêu chuẩn độ lệch trung bình bình

phương nhỏ nhất

Độ lệch trung bình bình phương (tbbp) giữa tín hiệu thu được và tín hiệu phát thứ j là:

T

0

1

(t) (t) dt

T

22

jj

[y(t) - x ] [y(t) - x ]

−−−−−−−−−−−

= ∫

Máy thu theo tiêu chuẩn độ lệch tbbp nhỏ nhất là máy thu đảm bảo:

j

min (t) j 1,m 2

j

[y(t) - x ]

− −−−−−−−−−−

∀

=

Như vậy, máy thu sẽ cho ra tín hiệu

j

x(t)

→

nếu:

(t) (t) i j, i 1,m 22

ji

[y(t) - x ] [y(t) - x ]

−−−−−−−−−−− −−−−−−−−−−−

≤∀≠=

Hay

TT

00

11

(t) dt (t) dt i j, i 1,m TT

22

ji

[y(t) - x ] [y(t) - x ] ≤∀≠= ∫∫

Nâng lên luỹ thừa 1/2, ta có:

TT

00

11

(t) dt (t) dt i j, i 1,m TT

22

ji

[y(t) - x ] [y(t) - x ] ≤∀≠= ∫∫

Theo định nghĩa của khoảng cách, ta có thể viết lại như sau:

0j0 0i0 d(y ,x ) d(y ,x ) i j, i 1,m

→→ →→

≤∀≠=

Đây chính là hệ thức đảm bảo bởi máy thu tối ưu K. Chương 2: Tín hiệu và nhiễu

45

BÀI TẬP

2.1. Đồ thị giá trị trung bình a(t) và giá trị trung bình bình phương ( ) t σ của các quá trình ngẫu

nhiên X(t), Y(t) và Z(t) vẽ trên hình 1 dưới đây. Hãy chỉ ra trên đồ thị miền các giá trị có thể có

của các quá trình ngẫu nhiên này, biết rằng biên giới của các miền đó được xác định bởi các giá trị

của () t σ .

Hình 1.

2.2. Trên hình 2 vẽ hàm ngẫu nhiên dừng rời rạc X(t), gọi là dãy xung điện báo. Dãy xung có biên

độ không đổi bằng đơn vị, có độ rộng ngẫu nhiên.

Phân bố xác suất các giá trị (0 hoặc 1) của X(t) tuân theo luật Poisson:

ax(t)

0

t

0

ay(t)

t

t

az(t)

0

t t t

( ) y t σ

0 0

( ) z t σ

0

x(t)

1

0

Hình 2. Chương 2: Tín hiệu và nhiễu

46

()

()

n

t

n

t

Pt e t 0

n!

−λ λ

= >

Trong đó λ là số các bước nhảy của hàm X(t) trong một đơn vị thời gian, còn ( ) n Pt là

xác suất để xảy ra n bước nhảy của hàm X(t) trong thời gian t.

Hãy tìm hàm tự tương quan, hàm tương quan chuẩn hoá và thời gian tương quan của quá

trình ngẫu nhiên, biết rằng P(1) = P(0) = 0,5.

2.3. Tìm hàm tự tương quan của quá trình ngẫu nhiên dừng sau:

( ) ( ) 0 Xt Acos2ft =π+ϕ

Trong đó A = const,

0 f = const, ϕ là đại lượng ngẫu nhiên có phân bố đều trong khoảng

() , −π π .

2.4. Tìm hàm tự tương quan và mật độ phổ của tín hiệu điện báo ngẫu nhiên X(t) cho bởi hình

dưới đây. Biết rằng nó nhận các giá trị + a; - a với xác suất như nhau và bằng 1/2. Còn xác suất để

trong khoảng τ có N bước nhảy là:

()

()

N

PN, e 0

N!

−λτ λτ

τ= τ>

(theo phân bố Poisson).

2.5. Hãy chứng tỏ rằng đường bao của tín hiệu giải tích có thể biểu diễn bằng công thức sau:

() () ()

*

aa At S t.S t =

Trong đó: ( )

*

a St là hàm liên hợp phức của ( ) a St :

() () () a St xt jxt

∧

=+ là tín hiệu giải tích.

2.6. Một quá trình ngẫu nhiên dừng có hàm tự tương quan:

a. () 1

2

x R.e

−ατ

τ=σ

b. () 2

2

x0 R.e.cos

−α τ

τ=σ ωτ

Hãy tính toán và vẽ đồ thị mật độ phổ của các quá trình ngẫu nhiên trên. Chương 3: Cơ sở lý thuyết thông tin thống kê

47

CHƯƠNG 3 - CƠ SỞ LÝ THUYẾT THÔNG TIN THỐNG KÊ

3.1. THÔNG TIN - LƯỢNG THÔNG TIN - XÁC SUẤT VÀ THÔNG TIN - ĐƠN VỊ

ĐO THÔNG TIN

3.1.1. Định nghĩa định tính thông tin và lượng thông tin

3.1.1.1. Thông tin

Ở chương trước, ta đã học khái niệm về thông tin. Ở đây ta sẽ xây dựng định nghĩa định

tính của thông tin theo quan điểm thống kê. Để đi tới định nghĩa định tính của thông tin, ta sẽ xét

ví dụ sau:

Ta nhận được một bức điện (thư) từ nhà đến. Khi chưa mở bức điện ra đọc thì ta chỉ có thể dự

đoán hoặc thế này hoặc thế khác về bức điện, mà không dám chắc nội dung của nó là gì. Nói khác

đi, khi chưa mở bức điện ra đọc thì ta không thể xác định được nội dung của nó, tức là ta chưa biết

gia đình báo cho ta thông tin gì. Nhưng khi đã xem xong bức điện thì nội dung của nó đối với ta đã

hoàn toàn rõ ràng, xác định. Lúc đó, nội dung của bức điện không còn bấp bênh nữa. Như vậy, ta nói

rằng: ta đã nhận được một tin về gia đình. Nội dung của bức điện có thể có 3 đặc điểm sau:

- Nội dung đó ta đã thừa biết. (VD: "Các em con được nghỉ hè 3 tháng"). Khi đó bức điện

không cho ta một hiểu biết gì mới về tình hình gia đình. Hay nói theo quan điểm thông tin, thì bức

điện với nội dung ta đã thừa biết không mang đến cho ta một thông tin gì.

- Loại nội dung ta có thể đoán thế này hoặc thế nọ (tức là loại nội dung có độ bấp bênh nào

đấy). VD: "Em An đã đỗ đại học". Vì em An học lực trung bình nên thi vào đại học có thể đỗ, có

thể không. Điện với nội dung ta không biết chắc (nội dung chứa một độ bất định nào đó) thật sự

có mang đến cho ta một thông tin nhất định.

- Loại nội dung mà ta hoàn toàn không ngờ tới, chưa hề nghĩ tới. VD: "Em An trúng giải

nhất trong đợt xổ số". Bức điện như vậy, đứng về mặt thông tin mà nói, đã đưa đến cho ta một

thông tin rất lớn.

Chú ý: Ở đây ta nói tới "những nội dung chưa hề nghĩ tới" phải hiểu theo ý hoàn toàn

khách quan chứ không phải do sự không đầy đủ về tư duy của con người đem lại.

Từ những ví dụ trên, ta rút ra những kết luận sau về khái niệm thông tin:

- Điều gì đã xác định (khẳng định được, đoán chắc được, không bấp bênh,...) thì không có

thông tin và người ta nói rằng lượng thông tin chứa trong điều ấy bằng không.

- Điều gì không xác định (bất định) thì điều đó có thông tin và lượng thông tin chứa trong nó

khác không. Nếu ta càng không thể ngờ tới điều đó thì thông tin mà điều đó mang lại cho ta rất lớn.

Tóm lại, ta thấy khái niệm thông tin gắn liền với sự bất định của đối tượng ta cần xét. Có sự

bất định về một đối tượng nào đó thì những thông báo về đối tượng đó sẽ cho ta thông tin. Khi

không có sự bất định thì sẽ không có thông tin về đối tượng đó. Như vậy, khái niệm thông tin chỉ

là một cách diễn đạt khác đi của khái niệm sự bất định. Chương 3: Cơ sở lý thuyết thông tin thống kê

48

Trước khi nhận tin (được thông báo) về một đối tượng nào đấy thì vẫn còn sự bất định về

đối tượng đó, tức là độ bất định về đối tượng đó khác không (có thể lớn hoặc nhỏ). Sau khi nhận

tin (đã được hiểu rõ hoặc hiểu một phần) về đối tượng thì độ bất định của nó giảm đến mức thấp

nhất, hoặc hoàn toàn mất. Như vậy, rõ ràng "Thông tin là độ bất định đã bị thủ tiêu" hay nói một

cách khác "Làm giảm độ bất định kết quả cho ta thông tin".

3.1.1.2. Lượng thông tin

Trong lý luận ở trên, ta đã từng nói đến lượng thông tin và lượng thông tin lớn, lượng thông

tin nhỏ mà không hề định nghĩa các danh từ đó. Dưới đây ta sẽ trả lời vấn đề đó.

Ở trên ta cũng đã nói: trước khi nhận tin thì độ bất định lớn nhất. Sau khi nhận tin (hiểu rõ

hoặc hiểu một phần về đối tượng thì độ bất định giảm đến mức thấp nhất, có khi triệt hoàn toàn.

Như vậy, có một sự chênh lệch giữa độ bất định trước khi nhận tin và độ bất định sau khi nhận tin.

Sự chênh lệch đó là mức độ thủ tiêu độ bất định. Độ lớn, nhỏ của thông tin mang đến ta phụ thuộc

trực tiếp vào mức chênh đó. Vậy:

"Lượng thông tin là mức độ bị thủ tiêu của độ bất định ⇔ Lượng thông tin = độ chênh của

độ bất định trước và sau khi nhận tin = độ bất định trước khi nhận tin - độ bất định sau khi nhận

tin (độ bất định tiên nghiệm - độ bất định hậu nghiệm)".

3.1.2. Quan hệ giữa độ bất định và xác suất

3.1.2.1. Xét ví dụ sau

Ta phải chọn một phần tử trong một tập nào đó. Phép chọn như thế (hoặc "chọn" hiểu theo

nghĩa rộng: thử, tìm hiểu, điều tra, trinh sát, tình báo,...) bao giờ cũng có độ bất định.

- Nếu tập chỉ có một phần tử thì ta chẳng phải chọn gì cả và như vậy không có độ bất định

trong phép chọn đó.

- Nếu tập có hai phần tử thì ta đã phải chọn. Như vậy, trong trường hợp này phép chọn có

độ bất định. Nếu số phần tử của tập tăng thì độ bất định sẽ tăng.

- Các bước tiếp theo sẽ cho bởi bảng sau:

Số phần tử của tập Độ bất định của phép chọn Xác suất chọn một phần tử trong tập

1

2

3

.

.

.

n

.

.

.

∞

0

≠0

≠0

.

.

.

≠0

.

.

.

∞

1

1/2

1/3

.

.

.

1/n

.

.

.

1/ 0 ∞ =

ơ

Chú ý: Bảng này đưa ra với giả sử việc chọn các phần tử là đồng xác suất.

Tăng

Giảm Chương 3: Cơ sở lý thuyết thông tin thống kê

49

3.1.2.2. Kết luận

- Bảng này cho thấy: độ bất định gắn liền với bản chất ngẫu nhiên của phép chọn, của biến cố.

- Độ bất định (ký hiệu I) là hàm của số phần tử thuộc tập

K I(x ) f (n) = (a)

- Độ bất định có liên quan với xác suất chọn phần tử của tập

KK I(x) E(x) [p ] ⇒= (b)

Để tìm mối quan hệ giữa độ bất định I và xác suất chọn một phần tử

KK x((x)) p trong

tập, ta xuất phát từ các tiêu đề sau:

Theo suy nghĩ thông thường, độ bất định I phải thoả mãn:

+

K I(x ) 0 ≥

+

KKK (x ) 1 I(x ) E (x ) p[p]=E[1]=0 =⇒ = (3.1)

+ Tính cộng được:

Nếu

K x và

i

x độc lập, thì:

Ki K i K i

E(xx)(x)(x)(x)(x) [p ] = E[p p ] = E[p ] + E[p ]

Nếu

K x và

i

x phụ thuộc thì:

Ki K i K K i K E(xx)(x)(xx)(x)(xx) [p ]=E[p p ]=E[p ]+E[p ]

Đặt

K (x ) p p = và

iK (x x ) q p] = , thì khi đó với mọi p, q (0 p 1, 0 q 1)

có:

E[p] + E[q] = E(pq) (3.2)

Từ (3.2) ta có thể tìm được dạng hàm I(p). Lấy vi phân 2 vế của (3.2) theo p, ta có:

E'(p) = q E'(pq)

Nhân cả 2 vế của phương trình này với p và ký hiệu p.q = τ , ta có:

pE'(p) = τE'( τ ) (3.3)

(3.3) đúng ∀p, τ ≠ 0. Nhưng điều này chỉ có thể có khi cả hai vế của (3.3) bằng một

hằng số k nào đó:

pE'(p) = τE'( τ ) = k = const

Từ đó chúng ta có phương trình vi phân pI'(p) = const = k, lấy tích phân phương trình này,

ta tìm được:

E(p) = k.lnp + C (3.4)

Kể đến điều kiện ban đầu (3.1), chúng ta có:

E(p) = k.lnp (3.5)

Như vậy, ta có:

KK I(x) k.ln x) [p( ] = (3.6) Chương 3: Cơ sở lý thuyết thông tin thống kê

50

Hệ số tỷ lệ k trong (3.6) có thể chọn tuỳ ý, nó chỉ xác định hệ đơn vị đo của

K I(x ) . Vì

K ln x ) [p( ] 0 ≤ nên để

K I(x ) 0 ≥ thì k

Nếu lấy k = -1 thì

KK

K

1

I(x) ln x) ln

x)

[p( ] =

p(

⎡ ⎤

=− ⎢ ⎥

⎣ ⎦

(3.7)

Khi đó, đơn vị đo độ bất định sẽ là đơn vị tự nhiên, ký hiệu là nat.

Nếu lấy

1

k

ln 2

=− thì

K

K2K

ln x )

I(x ) log p(x )

ln 2

p(

=− =− (3.8)

Khi đó đơn vị đo độ bất định sẽ là đơn vị nhị phân, ký hiệu là bit (1 nat = 1,433 bit)

Một bit chính là độ bất định chứa trong một phần tử (biến cố của tập xác suất chọn (xuất

hiện) bằng 1/2. Người ta thường sử dụng đơn vị [bit] do trong kỹ thuật tính và kỹ thuật liên lạc

thường dùng các mã nhị phân.

Ngoài ra, người ta còn có thể sử dụng những đơn vị đo khác tuỳ theo cách chọn cơ số của

logarit. Vì vậy trong trường hợp tổng quát, ta có thể viết:

KK I(x ) log x ) p( =− (3.9)

3.1.3. Xác định lượng thông tin

Ở mục 1, ta đã có kết luận sau:

Lượng thông tin = độ bất định tiên nghiệm - độ bất định hậu nghiệm. Vì độ bất định sẽ trở

thành thông tin khi nó bị thủ tiêu nên ta có thể coi độ bất định cũng chính là thông tin. Do đó:

Lượng thông tin = thông tin tiên nghiệm - thông tin hậu nghiệm (*)

Thông tin tiên nghiệm (hay còn gọi là lượng thông tin riêng) được xác định theo (3.9). Còn

thông tin hậu nghiệm xác định như sau:

Gọi

K x là tin gửi đi, yA là tin thu được có chứa những dấu hiệu để hiểu biết về

K x (có

chứa thông tin về

K x ). Khi đó xác suất để rõ về

K x khi đã thu được yA là

K (x y ) p A . Như

vậy độ bất định của tin

K x khi đã rõ yA bằng:

(3.9)

KK xy) (xy) I( - logp = AA (3.10)

(3.10) được gọi là thông tin hậu nghiệm về

K x (thông tin riêng về K x sau khi có yA

).

Thay (3.9) và (3.10) vào (*), ta có: Chương 3: Cơ sở lý thuyết thông tin thống kê

51

K

LI()I(y)

LI()I(y)

11

I( ,y ) log log

p( ) p( y )

KKK

KKK

ý hiÖu

K

KK

−îng th«ng tin vÒ x x x

−îng th«ng tin vÒ x x x

x

xx

⇓

= −

=−

=−

A

A

A

A

K

K

K

p(x y )

I(x ,y ) log

p(x )

⇒= A

A (3.11)

(3.11) gọi là lượng thông tin về

K x khi đã rõ tin yA hay còn gọi là lượng thông tin chéo về

K x do yA mang lại.

Nếu việc truyền tin không bị nhiễu thì

K yx ≡ A . Tức là nếu phát

K x thì chắc chắn nhận

được chính nó. Khi đó:

KKK p(x y ) p(x x ) 1 == A

Từ (3.11) ta có:

KKKK

K

1

I(x ,y ) I(x ,x ) I(x ) log

p(x )

=== A (**)

Như vậy khi không có nhiễu, lượng thông tin nhận được đúng bằng độ bất định của sự kiện

K x , tức là đúng bằng thông tin tiên nghiệm của

K x .

Vậy lượng thông tin tổn hao trong kênh sẽ là:

I( ) I( ,y ) I( y ) KK K xx x −= AA

Đơn vị đo của thông tin (lượng thông tin) cũng chính là đơn vị đo độ bất định.

Nếu cơ số của logarit là 10 thì đơn vị đo thông tin được gọi là Hartley, hay đơn vị thập

phân.

Nếu cơ số của logarit là e = 2,718... thì đơn vị đo thông tin được gọi là nat, hay đơn vị đo

tự nhiên.

Nếu cơ số của logarit là 2 thì đơn vị đo thông tin được gọi là bit, hay đơn vị nhị phân.

1 Harley = 3,322 bit

1 nat = 1,443 bit Chương 3: Cơ sở lý thuyết thông tin thống kê

52

3.2. ENTROPIE VÀ CÁC TÍNH CHẤT CỦA ENTROPIE

3.2.1. Tính chất thống kê của nguồn rời rạc và sự ra đời của khái niệm entropie

Trong mục trước, ta mới chỉ xét đến lượng thông tin về một biến cố (hay một tin) trong một

tập các biến cố (hay tin) xung khắc, đồng xác suất.

Thực tế tồn tại phổ biến loại tập các biến cố (hay nguồn tin, tập tin) xung khắc, không đồng

xác suất. Tức là xác suất xuất hiện các biến cố khác nhau trong tập là khác nhau. Ta gọi sự khác

nhau giữa các xác suất xuất hiện biến cố của tập (hay tin của nguồn rời rạc) là tính chất thống kê

của nó.

Ví dụ 1: Sự xuất hiện các con chữ trong bộ chữ Việt có xác suất khác nhau: p(e) = 0,02843;

p(m) = 0,02395; p(k) = 0,02102,... (Theo số liệu trong đồ án tốt nghiệp "Khảo sát cấu trúc thống

kê chữ Việt" của Đoàn Công Vinh - ĐHBK HN).

Ví dụ 2: Xác suất xuất hiện của 26 chữ cái trong tiếng Anh: (Số liệu theo Beker và Pipe)

Ký tự Xác suất Ký tự Xác suất

A

B

C

D

E

F

G

H

I

J

K

L

M

0,082

0,015

0,028

0,043

0,127

0,022

0,020

0,061

0,070

0,002

0,008

0,040

0,024

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

0,067

0,075

0,019

0,001

0,060

0,063

0,091

0,028

0,010

0,023

0,001

0,020

0,001

Trong một nguồn tin như thế, ngoài thông tin riêng của mỗi tin (hay dấu) của nó, người ta

còn phải quan tâm đến thông tin trung bình của mỗi tin thuộc nguồn. Người ta còn gọi thông tin

trung bình do mỗi dấu của nguồn mang lại là entropie. Dưới đây ta sẽ xét kỹ định nghĩa về

entropie.

3.2.2. Định nghĩa entropie của nguồn rời rạc

3.2.2.1. Đặt vấn đề

Để phép đo được chính xác, trong vật lý, khi đo lường một đại lượng, ta không quan tâm

đến từng trị đo được của đại lượng mà thường xét trị trung bình của chúng. Khi đó ta lấy các trị

đo được cộng với nhau rồi chia cho số lượng của chúng:

n

tb r

r1

iin

=

= ∑ Chương 3: Cơ sở lý thuyết thông tin thống kê

53

Ở đây cũng có điều tương tự: ta không quan tâm đến từng thông tin riêng của mỗi dấu mà

lại chú ý đến giá trị trung bình của các thông tin đó. Chỉ khác ở chỗ mỗi một thông tin riêng đến

tương ứng với một xác suất xuất hiện nào đó, tức là ta có thể xem các thông tin riêng là m đại

lượng ngẫu nhiên I. Do đó giá trị trung bình của các thông tin này (lượng thông tin trung bình hay

entropie) chính là kỳ vọng của đại lượng ngẫu nhiên I. Ta đi tới định nghĩa sau:

3.2.2.2. Định nghĩa

Entropie của nguồn tin rời rạc là trung bình thống kê của lượng thông tin riêng của các dấu

thuộc nguồn A, ký hiệu

1 H(A) :

1 H(A) M ) i

[I(a ]

Δ

= (3.12)

Trong đó

i

a là các dấu của nguồn A (Ta hiểu dấu là các con chữ, hoặc các ký hiệu v.v...

của nguồn). Còn nguồn A là một tập rời rạc các dấu

i

a với các xác suất xuất hiện của chúng. Ta

quy ước viết A như sau:

2s a...a

A

p( ) p( ) ... p( )

1

i

12 s

a

{a } =

aa a

⎛⎞

= ⎜⎟

⎝⎠

(3.13)

Với

i

0p(a)1 ≤≤ và

s

i

i1

p(a ) 1

=

= ∑ (3.14)

A được cho bởi (3.13) và (3.14) còn gọi là trường tin (hay trường biến cố). Từ (3.12) và

(3.13), ta có:

1 H(A) M ) )I )

s

iii

i=1

[I(a ] = p(a (a = ∑

1 H(A) )logp )

s

ii

i=1

= p(a (a ⇒− ∑ (3.15)

1 H(A) còn gọi là entropie một chiều của nguồn rời rạc:

Ví dụ:

1 H (Việt) = 4,5167 bit

1 H (Nga) = 4,35 bit

1 H (Anh) = 4,19 bit

3.2.3. Các tính chất của entropie một chiều của nguồn rời rạc

3.2.3.1. Tính chất 1

Khi

k p(a ) 1 = và

r

p(a ) 0 = với rk ∀ ≠ thì:

11min H(A) H(A ) 0 == (3.16) Chương 3: Cơ sở lý thuyết thông tin thống kê

54

Chứng minh:

Ta đã có:

i

0p(a)1 ≤≤ ⇒

ii

log p(a ) 0 log p(a ) 0 ≤ ⇒− ≥

⇒

11min H(A) 0 H(A ) 0 ≥⇒ =

Bây giờ ta chỉ còn phải chứng tỏ

1min H(A ) 0 = khi

k p(a ) 1 = và

r

p(a ) 0 = ( rk ∀≠ ).

Thật vậy,

r

p(a ) 0 = ⇒

rr

p(a )logp(a ) 0 ( r k) = ∀≠

k p(a ) 1 =⇒

kk p(a )logp(a ) 0 ( r k) = ∀≠

s

1ii

i1

s

kk ii

i1,i k

H(A) p(a)logp(a)

p(a )logp(a ) p(a )logp(a ) 0

=

=≠

⇒=−

=− − =

∑

∑

Ý nghĩa:

Thực ra không cần phải chứng minh như vậy, mà lập luận như sau cũng cho ta công thức

(3.16):

r

p(a ) 0 = ⇒ các r

a không xuất hiện

k p(a ) 1 = ⇒ các k a chắc chắn xuất hiện

⇒ Không có độ bất định nào về các i

a ⇒ lượng thông tin riêng không có ⇒ lượng

thông tin trung bình cũng không có.

3.2.3.2. Tính chất 2

Một nguồn rời rạc gồm s dấu đồng xác suất (và

thoả mãn (3.14)) thì entropie của nó đạt cực đại và cực

đại đó bằng log s.

1m H(A ) logs ax = (3.17)

Chứng minh:

Khi

ij

p(a ) p(a ), i, j (i, j 1,s) =∀∀=

Khi đó

i

1

p(a )

s

= , tức là nguồn gồm các dấu

xung khắc và đồng khả năng.

y

x - 1

lnx

0 1 x

- 1

Hình 3.1. Chương 3: Cơ sở lý thuyết thông tin thống kê

55

s

1

i1

11

H(A') log logs

ss =

⇒=− = ∑

Xét hiệu:

s

1i

i i1

ss

ii

i i1 i1

s

i

i i1

ss

ii

i i1 i1

1

H (A) logs p(a ) log logs

p(a )

1

p(a )log p(a )logs

p(a )

1

p(a ) log logs

p(a )

1

p(a ) log p(a ) log x

p(a )s

=

==

=

==

−= −

=−

⎡⎤

=− ⎢⎥

⎣⎦

==

∑

∑∑

∑

∑∑

Ta có: lnx ≤ x - 1 ∀x (xem hình 3.1)

s

ii

i1

p(a ) l p(a ) (x 1) ogx

=

⇒≤− ∑∑

Mà:

sss

ii

i i1 i1 i1

11

p(a ) 1 p(a ) 0

p(a )s s ===

⎡⎤

−= − = ⎢⎥

⎣⎦

∑∑∑

Vậy:

11 H(A) logs 0 H(A) logs −≤⇒ ≤

Tóm lại, ta thấy

1 0H(A)logs ≤≤ (entropie của nguồn rời rạc)

Entropie là một đại lượng giới nội.

Ký hiệu

m0 H(A) H (A) ax =

Ví dụ:

0 H (Vi 36 5,1713bit 2 Öt) = log =

0 H(Nga 32 5bit 2 )=log =

0 H (Anh 27 4,75489bit 2 )=log =

3.2.4. Entropie của nguồn rời rạc, nhị phân

Nguồn rời rạc nhị phân là nguồn chỉ có hai dấu:

1

2

a"0" v )p

a"1" v )1p

1

2

íi x¸c suÊt p(a

íi x¸c suÊt p(a

⇔= ⎧

⎨

⇔=− ⎩ Chương 3: Cơ sở lý thuyết thông tin thống kê

56

Ta có ngay:

2

1ii

i1

H (A) p(a ) log p(a ) plog p (1 p) f (p)

=

=− =− − − = ∑ (3.18)

Đồ thị f(p) được biểu diễn trên hình 3.2.

Ta thấy

1 H(A) f(p) = chỉ phụ thuộc

vào đặc tính thống kê của các tin.

Nếu đơn vị dùng là bit thì

max 1 H(A) 1 =

Nhận xét:

- 1 H(A)đạt max tại

1

p

2

= . Sở dĩ như

vậy vì tập chỉ có hai phần tử, nên độ bất định của

phép chọn sẽ lớn nhất khi hai dấu có xác suất

xuất hiện như nhau.

- p = 0 ⇒

1min H(A) 0 = . Khi đó 1 - p = 1 là xác suất xuất hiện dấu

2 a . Vậy

2 a là một

biến cố chắc chắn. Phép chọn này không có độ bất định ⇒ lượng thông tin trung bình triệt.

- p = 1 ⇒

1min H(A) 0 = . Giải thích tương tự.

3.2.5. Entropie của trường sự kiện đồng thời

Định nghĩa 1:

Có hai trường sự kiện A và B:

12 s

12 s

aa...a

A

p(a ) p(a ) ... p(a )

⎛⎞

= ⎜⎟

⎝⎠

và

12 t

12 t

bb...b

B

p(b ) p(b ) ... p(b )

⎛⎞

= ⎜⎟

⎝⎠

Các

i

a và

j

b là các sự kiện.

Ta xét một sự kiện tích:

kij

ca.b =

kij

p(c ) p(a .b ) = . Ta xét trường C là giao của hai trường A và B, nếu:

11 12 1 t 2 j s t

11 12 1 t 2 j s t

a b a b ... a b ... a b ... a b

CA.B

p(a b ) p(a b ) ... p(a b ) ... p(a b ) ... p(a b )

⎛⎞

== ⎜⎟

⎜⎟

⎝⎠

Trường C được gọi là trường sự kiện đồng thời (trường giao, tích) của hai trường sự kiện cơ

bản A và B.

Định nghĩa 2:

H1(A)

1

H1(A)max

0 0,5 1 p

Hình 3.2. Chương 3: Cơ sở lý thuyết thông tin thống kê

57

Hai trường sự kiện A và B được gọi là độc lập với nhau nếu:

ij i j

p(a .b ) p(a ).p(b ) =

Chú ý: Tất nhiên nếu

i

p(a ) và

j

p(b ) thoả mãn (3.14) thì ta cũng có:

st

ij ij

i1j1

0p(ab)1; p(ab)1

==

≤ ≤= ∑∑ (*)

Định lý 1:

Entropie của trường sự kiện đồng thời C = A. B sẽ bằng tổng entropie của các trường sự

kiện cơ bản A và B nếu A và B độc lập.

H(A.B) = H(A) + H(B) (3.19)

Chứng minh: Theo định nghĩa:

st

ij ij

i1j1

H(A.B) p(ab)logp(ab)

Δ

==

=− ∑∑

Theo giả thiết A và B độc lập với nhau nên ta có:

st st

ij i ij j

i1j1 i1j1

stt s

iij j ji

i1 j1 j1 i1

H(A.B) p(a )p(b ) logp(a ) p(a )p(b ) logp(b )

p(a )logp(a ) p(b ) p(b )logp(b ) p(a )

== ==

=== =

=− −

=− −

∑∑ ∑∑

∑∑∑∑

Mà:

t

j

j1

p(b ) 1

=

= ∑ ,

s

i

i1

p(a ) 1

=

= ∑

⇒ H(A.B) = H(A) + H(B)

Nhận xét: Tương tự, nếu các nguồn

k X,(k 1,n) = độc lập với nhau thì:

n

12 n k

k1

H(X .X ....X ) H(X )

=

= ∑

3.3. ENTROPIE CÓ ĐIỀU KIỆN. LƯỢNG THÔNG TIN CHÉO TRUNG BÌNH

3.3.1. Entropie có điều kiện về một trường tin này khi đã rõ một tin nhất định của

a1

a2

ak

b1

b2

bl Chương 3: Cơ sở lý thuyết thông tin thống kê

58

trường tin kia

3.3.1.1. Mở đầu

Trong phần trước, ta đã nói nếu truyền tin có nhiễu thì tin phát đi

k a và tin thu được bA là

khác nhau. Và khi đó lượng thông tin riêng về

k a do bA mang lại là:

k

k

1

I(a / b ) log

p(a / b )

= A

A

Vấn đề: ta không quan tâm đến lượng thông tin riêng về một dấu

k a cụ thể nào của nguồn

tin phát { i

a } do bA mang lại mà chỉ quan tâm đến lượng thông tin riêng trung bình về một dấu

nào đó của tập { i

a } do bA mang lại. Ta thấy rằng

k I(a / b ) A là một đại lưọng ngẫu nhiên. Do

đó tương tự như định nghĩa của entropie một chiều, ta đi tới định nghĩa sau.

3.3.1.2.Định nghĩa

Entropie có điều kiện về một trường tin này khi đã rõ một tin của trường tin kia được xác

định bằng kỳ vọng của lượng thông tin riêng có điều kiện về

k a do một bA mang lại:

s

i1

H(A/b) M /b) /b)I /b) iii

[I(a ] = p(a (a

Δ

=

= ∑ AA AA

s

i1

/b )logp /b ) ii

p(a (a

=

=−∑ AA (3.20)

Ý nghĩa:

H(A/b ) A là lượng thông tin tổn hao trung bình của mỗi tin ở đầu phát khi đầu thu đã thu

được

j

b .

Tương tự:

t

iii

j1

H(B/a) /a)logp /a) jj

p(b (b

=

=−∑

Ý nghĩa:

i

H(B/a ) là lượng thông tin riêng trung bình chứa trong mỗi tin ở đầu thu khi đầu phát đã

phát đi một tin

i

a .

3.3.2. Entropie có điều kiện về trường tin này khi đã rõ trường tin kia

Ta thấy rằng do nhiễu ngẫu nhiên nên bên thu không phải chỉ thu được một tin duy nhất mà

là cả tập tin B = { j

b } nào đó, (j 1,t) = . Vậy

j

H(A/b ) cũng là một đại lượng ngẫu nhiên, do Chương 3: Cơ sở lý thuyết thông tin thống kê

59

đó ta phải xét đến lượng thông tin riêng trung bình về mỗi tin ở đầu phát khi đầu thu đã thu được

một dấu nào đó.

Tương tự như trên, ta cũng phải lấy trung bình thống kê của đại lượng ngẫu nhiên này.

Định nghĩa:

Entropie có điều kiện của trường sự kiện A khi đã rõ trường sự kiện B được xác định bởi kỳ

vọng của đại lượng

j

H(A/b ) .

t

jjj

j1

ts

jijij

j1 i1

st

jij ij

i1j1

H(A/B) M H(A/b ) p(b )H(A/b )

p(b ) p(a / b )logp(a / b )

p(b )p(a / b )logp(a / b )

Δ

=

==

==

⎡⎤ == ⎣⎦

⎡ ⎤

=− ⎢ ⎥

⎢ ⎥ ⎣ ⎦

=−

∑

∑∑

∑∑

st

ij i j

i1j1

H(A/B) p(a b )logp(a /b )

==

=−∑∑ (3.21)

Ý nghĩa:

H(A/B) là lượng thông tin tổn hao trung bình của mỗi tin ở đầu phát khi đầu thu đã thu

được một dấu nào đó.

Tương tự:

st

ji j i

i1j1

H(B/A) p(b a )logp(b /a )

==

=−∑∑ (3.22)

Ý nghĩa:

H(B/A) là lượng thông tin riêng trung bình chứa trong mỗi tin ở đầu thu khi đầu phát đã

phát đi một tin nào đó.

Chú ý:

Ta xét một bộ chữ A. Để đặc trưng cho lượng thông tin riêng trung bình chứa trong mỗi con

chữ khi kể đến xác suất xuất hiện các cặp chữ (VD: trong tiếng Việt: p(a/b) ≠ 0, p(b/a) = 0,

p(t/a) ≠ 0, p(a/t) ≠ 0), người ta dùng H(A/A) và ký hiệu là H2 (A).

Ví dụ: H2 (Việt) = 3,2223 bit

H2 (Nga) = 3,52 bit

H2 (Anh) = 3,32 bit Chương 3: Cơ sở lý thuyết thông tin thống kê

60

Việc tính H3, H4 rất phức tạp.

Khakevich tính được đến H5 . Shannon tính được đến H8 .

3.3.3. Hai trạng thái cực đoan của kênh truyền tin

3.3.3.1. Kênh bị đứt (bị nhiễu tuyệt đối)

Trong trường hợp này, các tin thu được hoàn toàn khác các tin phát đi. Nói khác đi vì bị

nhiếu tuyệt đối nên trong mọi tin

j

b B ∈ không chứa dấu hiệu hiểu biết nào về các tin đã phát đi.

Như vậy, A và B là độc lập nhau:

ij i

p(a / b ) p(a ) = ;

ji j

p(b / a ) p(b ) =

ij i j

p(a b ) p(a )p(b ) ⇒=

Khi đó ta có:

s

jii

i1

t

ijj

j1

ts

ji i

j1 i1

st

ij j

i1 j1

H(A/b ) p(a )logp(a ) H(A)

H(B/a ) p(b )logp(b ) H(B)

H(A/B) p(b ) p(a )logp(a ) H(A)

H(B/A) p(a ) p(b )logp(b ) H(B)

=

=

==

==

=− =

=− =

=− =

=− =

∑

∑

∑∑

∑∑

(3.23)

3.3.3.2. Kênh không nhiễu

Khi đó: t = s. Với

ii

i1,sa b ∀ ==

ii

p(a ) p(b ) ⇒= nên H(A) = H(B)

kk kk

ik ik

p(a / b ) p(b / a ) 1

p(a / b ) p(b / a ) 0 víi i k

= =

= =∀≠

kk H(A/b ) 0 H(B/a ) 0

H(A/B) 0 H(B/A) 0

== ⎧

⇒ ⎨

== ⎩

(3.24)

Vì khi không nhiễu, coi A và B phụ thuộc mạnh nhất, có

i

a thì chắc chắn có

i

b , nên độ

bất định về

i

a khi đã thu được

i

b là không có ⇒ độ bất định trung bình cũng không có. Chương 3: Cơ sở lý thuyết thông tin thống kê

61

3.3.4. Các tính chất của entropie có điều kiện

3.3.4.1.Tính chất 1

Nếu A và B là hai trường biến cố bất kỳ (hai nguồn tin bất kỳ) thì entropie của trường biến

cố đồng thời A.B bằng:

H(A.B) = H(A) + H(B/A) = H(B) + H(A/B) (3.25)

Chứng minh:

{}

st

ij ij

i1j1

st

jij jij

i1j1

H(A.B) p(ab)logp(ab)

p(b )p(a / b )log p(b )p(a / b )

==

==

=− =

=− =

∑∑

∑∑

st st

jij j jij ij

i1j1 i1j1

st st

ij j j ij ij

i1 j1 i1j1

H(A.B) p(b )p(a / b ) logp(b ) p(b )p(a / b ) logp(a / b )

p(a /b) p(b)logp(b) p(ab)logp(a/b)

H(B) H(A/B)

== ==

== ==

=− − =

=− −

=+

∑∑ ∑∑

∑∑ ∑∑

Trong đó:

s

ij

i1

p(a / b ) 1

=

= ∑ .

3.3.4.2.Tính chất 2

Entropie có điều kiện nằm trong khoảng:

0H(A/B)H(A) ≤≤ (3.26)

Chứng minh:

+ H(A/B) 0: ≥

ij ij

ij

0 p(a / b ) 1 logp(a / b ) 0

log p(a / b ) 0 H(A/B) 0

≤≤⇒ ≤

⇒− ≥ ⇒ ≥

Nó sẽ nhận dấu bằng khi A và B là đồng nhất (kênh không nhiễu).

+ H(A/B) ≤ H(A):

Xét hiệu: H(A/B) - H(A) = G Chương 3: Cơ sở lý thuyết thông tin thống kê

62

st s

jij ij i i

i1j1 i1

G p(b )p(a / b )logp(a / b ) p(a )logp(a ).1

== =

=− + ∑∑ ∑

Chú ý: ta thay

t

ji

j1

1p(b/a)

=

= ∑

st st

ij i j ij i

i1j1 i1j1

st

ij

ij

i i1j1

st

i

ij

ij i1j1

G p(a b )logp(a / b ) p(a b )logp(a )

p(a / b )

p(a b )log

p(a )

p(a )

p(a b )log

p(a / b )

== ==

==

==

⇒=− +

=−

=

∑∑ ∑∑

∑∑

∑∑

Áp dụng log x x 1 ≤− :

st

i

ij

ij i1j1

st

i

jij

ij i1j1

st st

ij jij

i1 j1 i1j1

p(a )

Gp(ab) 1

p(a / b )

p(a )

Gp(b)p(a/b) 1

p(a / b )

G p(a ) p(b ) p(b )p(a / b )

G1.1 10

==

==

== ==

⎡⎤

⇒≤ − ⎢⎥

⎢⎥ ⎣⎦

⎡ ⎤

≤− ⎢ ⎥

⎢ ⎥ ⎣ ⎦

≤−

≤−=

∑∑

∑∑

∑∑ ∑∑

⇒ H(A/B) ≤ H(A).

H(A/B) = H(A) khi A và B là độc lập (kênh bị đứt).

3.3.4.3. Tính chất 3

Entropie của trường sự kiện đồng thời không lớn hơn tổng entropie của các trường sự kiện

cơ bản.

H(A.B) ≤ H(A) + H(B) (3.27)

Chứng minh:

(3.27) rút ra trực tiếp từ (3.25) và (3.26). Chương 3: Cơ sở lý thuyết thông tin thống kê

63

3.3.5. Lượng thông tin chéo trung bình

Ở phần trước, chúng ta đã biết lượng thông tin chéo về một tin

i

a đã phát đi do một tin

j

b

đã thu được mang lại là:

ij

ij

i

p(a / b )

I(a ,b ) log

p(a )

=

Thông thường, vì bên phát phát đi một tập tin A = { i

a } và bên thu nhận được một tập tin B

= { j

b }. Do đó ta không quan tâm đến lượng thông tin chéo về một tin cụ thể

i

a đã phát do một

tin j

b cụ thể thu được, mà ta chỉ quan tâm đến lượng thông tin chéo trung bình về mỗi tin của tập

phát A do mỗi tin của tập thu B mang lại.

ij

I(a ,b ) là một đại lượng ngẫu nhiên, do đó ta phải lấy

trung bình thống kê của nó.

Định nghĩa:

Lượng thông tin chéo trung bình (ký hiệu là I(A,B)):

ij

I(A,B) M I(a ,b )

Δ

⎡⎤ = ⎣⎦

(3.28)

Xác suất để có thông tin

ij

I(a ,b ) là

ij

p(a b ) , do đó ta có:

st

ij

ij

i i1j1

p(a / b )

I(A,B) p(a b ) log

p(a )

==

=∑∑

st st

ij i j ij i

i1j1 i1j1

I(A,B) p(a b ) logp(a / b ) p(a b )logp(a )

H(A/B) H(A)

== ==

=−

=− +

∑∑ ∑∑

Tóm lại: I(A,B) = H(A) - H(A/B) (3.29a)

Tương tự, ta có: I(A,B) = H(B) - H(B/A) (3.29b)

Hay: I(A,B) = H(A) + H(B) - H(A.B)

I(A,B) còn gọi là lượng thông tin trung bình được truyền theo kênh rời rạc.

3.3.6. Tính chất của I(A,B)

3.3.6.1. Tính chất 1

I(A,B) ≥ 0: (3.30)

Theo tính chất 2 ở mục 3.3.4: H(A/B) ≤ H(A) ⇒ H(A) - H(A/B) ≥ 0.

I(A,B) = 0 khi kênh bị đứt. Chương 3: Cơ sở lý thuyết thông tin thống kê

64

3.3.6.2.Tính chất 2

I(A,B) ≤ H(A): (3.31)

Thật vậy: H(A/B) ≥ 0 ⇒ I(A,B) = H(A) - H(A/B) ≤ H(A)

I(A,B) = H(A) khi kênh không có nhiễu.

Từ (3.31) ta thấy khi truyền tin trong kênh có nhiễu, thông tin sẽ bị tổn hao một phần.

Lượng thông tin tổn hao trung bình chính là H(A/B).

3.3.6.3.Tính chất 3

I(A,A) = H(A)

3.3.6.4. Tính chất 4

I(A,B) = I(B,A)

3.3.7. Mô hình của kênh truyền tin có nhiễu

Dựa vào (3.29a), ta có mô hình kênh truyền khi có nhiễu như sau:

Hình 3.4. Lược đồ Wenn mô tả mối quan hệ giữa các đại lượng.

A B

H(A)

A B

H(A/B)

A B

I(A,B)

A B

H(AB)

A B

H(B/A)

H(A) I(A,B) = I(B,A) H(B)

H(A/B) H(B/A)

Tổn hao Lượng tin tức bù bằng hồi liên

Hình 3.3. Chương 3: Cơ sở lý thuyết thông tin thống kê

65

3.4. TỐC ĐỘ PHÁT. KHẢ NĂNG PHÁT. ĐỘ THỪA. KHẢ NĂNG THÔNG QUA

CỦA KÊNH RỜI RẠC

3.4.1. Tốc độ phát của nguồn rời rạc

Trong thông tin rời rạc, người ta thường phát đi các xung. Nếu gọi

n T là độ rộng trung

bình của mỗi xung thì tốc độ phát của nguồn tin rời rạc được định nghĩa như sau:

n

n

1

T

Δ

υ= (3.32)

(3.32) biểu thị số xung trong một đơn vị thời gian.

Thứ nguyên: [ n υ ] = bốt = số dấu (xung)/ sec

Ví dụ: Điện báo tay:

n υ = 25 bốt.

Điện báo tự động:

n υ = (50 ÷ 300) bốt.

Thông tin truyền số liệu: (500

4

n.10 ÷ ) bốt.

3.4.2. Khả năng phát của nguồn rời rạc

Định nghĩa:

n

n

H(A)

H'(A) H(A)

T

Δ

=υ = (3.33)

Thứ nguyên: [H'(A)] = bit/sec.

n

1

m H'(A) H(A)

T

ax =

(3.33) biểu thị lượng thông tin trung bình do nguồn phát ra trong một đơn vị thời gian.

Ví dụ: Một máy điện báo dùng mã Bôđô đều 5 dấu, cơ số 2, tốc độ phát là 75 bốt thì khả

năng tối đa của máy là:

5

mn1m 2 H'(A) .H (A) 75.log 2 375bit / s ax ax =υ = =

3.4.3. Độ thừa của nguồn rời rạc

Định nghĩa:

Độ thừa của nguồn rời rạc là tỷ số:

m

mm

H(A) H(A) H(A)

D1

H(A) H(A)

ax

ax ax

Δ −

==− (3.34) Chương 3: Cơ sở lý thuyết thông tin thống kê

66

D1 =−μ, trong đó:

m

H(A)

H(A) ax

μ= được gọi là hệ số nén tin.

Đối với nguồn tin có s dấu: H(A)max = H0 (A) = log s.

Ý nghĩa:

Độ thừa đặc trưng cho hiệu suất, khả năng chống nhiễu và độ mật của tin. Nếu D càng lớn

thì hiệu suất càng thấp, độ mật càng thấp nhưng khả năng chống nhiễu càng cao.

Ví dụ:

- Đối với tiếng Việt: H1 (Việt) = 4.5167; H0 (Việt) = 5,1713

1 87 ⇒μ = %

1 D ⇒= 13 %

2

2

H (A) 3,2223

l5,1713 ogs

μ= = = 62%

2 D ⇒=38%

- Đối với tiếng Nga:

1 μ= 87%

1 D ⇒= 13 %

3 μ = 60%

3 D ⇒= 40 %

- Đối với tiếng Anh:

1 μ= 84%

1 D ⇒= 16 %

8 μ = 38%

8 D ⇒= 62 %

3.4.4. Các đặc trưng của kênh rời rạc và các loại kênh rời rạc

Một kênh rời rạc hoàn toàn được đặc trưng bởi ba tham số sau:

- Trường dấu lối vào và trường dấu lối ra của kênh.

- Xác suất chuyển

ji

p(b / a )

- Tốc độ truyền tin của kênh

K υ

Định nghĩa 1:

Nếu một kênh có

ji

p(b / a ) t ∉ thì được gọi là kênh đồng nhất;

ji

p(b / a )∉vào dấu đã

phát trước nó thì được gọi là kênh không nhớ. Ngược lại,

ji

p(b / a ) t ∈ thì kênh được gọi là

không đồng nhất;

ji

p(b / a )∈ vào dấu đã phát trước nó thì kênh được gọi là kênh có nhớ

( i, j ∀ ).

Định nghĩa 2:

Nếu một kênh có xác suất chuyển:

ji

c,j1,t

p(b / a )

pc ij

s

®

p onst víi i j, i=1,s

onst

⎧ =∀≠= ⎪

= ⎨

=∀= ⎪ ⎩

Chương 3: Cơ sở lý thuyết thông tin thống kê

67

thì kênh đó sẽ được gọi là kênh đối xứng.

Ví dụ:

∀xác suất sai bằng nhau, ∀xác suất đúng bằng nhau.

Đối với kênh đối xứng nhị phân (Hình vẽ):

s pp1 ® + = .

3.4.5. Lượng thông tin truyền qua kênh trong một đơn vị thời gian

Định nghĩa:

K

K

I(A,B)

I'(A,B) I(A,B)

T

Δ

==υ [bit/s] (3.35)

Trong đó:

K

K

1

T

υ= ,

K T : thời gian trung bình để truyền một dấu qua kênh.

K υ biểu thị

số dấu mà kênh đã truyền được (được truyền qua kênh) trong một đơn vị thời gian. I'(A,B) là

lượng thông tin đã truyền qua kênh trong một đơn vị thời gian.

Nếu kênh giãn tin:

Kn TT >

Nếu kênh nén tin:

Kn TT

Thông thường:

Kn TT =

3.4.6. Khả năng thông qua của kênh rời rạc

Để đánh giá năng lực tải tin tối đa cuả một kênh truyền, người ta đưa ra khái niệm khả năng

thông qua.

3.4.6.1. Định nghĩa

Khả năng thông qua của kênh rời rạc là giá trị cực đại của lượng thông tin truyền qua kênh

trong một đơn vị thời gian, lấy theo mọi khả năng có thể có của nguồn tin A. (Cực đại này sẽ đạt

được ứng với một phân bố tối ưu của các xác suất tiên nghiệm p( i

a ),

i

aA ∀ ∈ ).

K AA

C'mI'(A,B) mI(A,B) ax ax

Δ

==υ [bit/s] (3.36)

p(b1/a1) = pđ

a1 b1

a2 b2

p(b2/a2) = pđ

p(b2/a1) p(b1/a2) Chương 3: Cơ sở lý thuyết thông tin thống kê

68

K A

C' .C v m I(A,B) íi C = ax =υ

C được gọi là khả năng thông qua của kênh đối với mỗi dấu.

C' là một tham số rất quan trọng của một kênh.

3.4.6.2. Tính chất

- C' ≥ 0, C' = 0 khi và chỉ khi A và B độc lập (kênh bị đứt).

- C' K logs ≤υ , đẳng thức chỉ xảy ra khi kênh không nhiễu. (3.37)

Chứng minh:

KK K

KK

KK

K

I(A,B) H(A)

I(A,B) H(A) ( 0)

mI(A,B))mH(A))

m I(A,B) m H(A)

C' logs

ax( ax(

ax ax

≤

υ ≤υ υ >

υ≤υ

υ≤υ

≤υ

3.4.7. Tính khả năng thông qua của kênh nhị phân đối xứng không nhớ, đồng nhất

3.4.7.1. Đặt bài toán

Ta có một kênh nhị phân như hình 3.4. Trong đó:

Xác suất sai:

21 12 s p(b / a ) p(b / a ) p ==

Xác suất đúng:

22 11 p(b / a ) p(b / a ) p® ==

p(a1) = p; p(a 2 ) = 1 - p;

Các dấu a1 và a 2 có cùng thời hạn T. Vấn đề: tính C'?

3.4.7.2. Giải bài toán

Ta có:

[]

KK

11

C' m I(A,B) m H(B) H(B/A)

TT AA

ax ax ==−

Ta có ngay:

22

iji ji

i1j1

H(B/A) p(a )p(b /a )logp(b /a )

==

=−∑∑

p(b1/a1) = pđ

a1 b1

a2 b2

p(b2/a2) = pđ

p(b1/a2)

= ps Chương 3: Cơ sở lý thuyết thông tin thống kê

69

[]

[]

[]

[]

111 11 21 21

212 12 22 22

ssss

ss s s

H(B/A) p(a ) p(b /a )logp(b /a ) p(b /a )logp(b /a )

p(a ) p(b / a )logp(b / a ) p(b / a )logp(b / a )

p (1 p ) log(1 p ) p log p

(1p)plogp (1p)log(1p)

=− +

−+

=− − − +

−− + − −

[] ss s s H(B/A) p logp (1 p )log(1 p ) =− + − −

Ta thấy H(B/A) chỉ phụ thuộc vào

s p , mà không phụ thuộc vào xác suất tiên nghiệm của

các dấu thuộc nguồn tin A. Do đó:

[]

K

KK

1

C' m H(B) H(B/A)

T

11

mH(B) H(B/A)

TT

A

A

ax

ax

=−

=−

Ở đây H(B/A) không đổi đối với mọi trạng thái (đặc tính thống kê) của nguồn A.

Mà:

m22 m H(B) H(B) log s log 2 1 ax

A

ax ====

Vậy: [] ss s s

K

1

C' 1 p log p (1 p ) log(1 p )

T

=+ +− −

( ) sK C' f p ,T =

ms

K

1

C' p 0

T ax =⇔=⇔ Kênh không nhiễu.

ss s s

m

C'

1 p log p (1 p ) log(1 p )

C'

ax

=+ + − −

(3.38)

Đồ thị (3.38) biểu diễn trên hình 3.5.

3.4.8. Định lý mã hoá thứ hai của Shannon

Định lý: Nếu khả năng phát H'(A) của nguồn tin rời rạc A bé hơn khả năng thông qua của

kênh: (H'(A)

lỗi bé tuỳ ý (nếu H'(A) > C' thì không tồn tại phép mã hoá và giải mã như vậy) khi độ dài từ mã

đủ lớn.

Nhận xét: Đây là một định lý tồn tại vì nó không chỉ cho ta cách thiết lập một mã cụ thể

nào. Lý thuyết mã kênh trong chương 4 chính là hướng dẫn cần thiết cho định lý này.

C'/ C'max

1

0 0,5 1 ps

Hình 3.5. Chương 3: Cơ sở lý thuyết thông tin thống kê

70

3.4.9. Khả năng thông qua của kênh nhị phân đối xứng có xoá

3.4.9.1.Đặt bài toán

Cho kênh truyền, các dấu

1 a và

2 a như hình vẽ. Các dấu

1 a và

2 a có cùng thời hạn T.

Hãy tính khả năng thông qua C' của kênh này với điều kiện:

Xác suất xoá:

3i

p(b / a ) q =

Xác suất thu đúng:

11 2 2 s p(b / a ) p(b / a ) 1 p q ==−−

Xác suất thu sai:

21 12 s p(b / a ) p(b / a ) p ==

3.4.9.2. Giải bài toán

Tương tự bài toán trên, ta có:

[]

1

C' m H(B) H(B/A)

T A

ax =−

Trong đó:

()()

() ()()

()()

23

iji ji

i1j1

ssss

ss s s

ssss

H(B/A) p(a )p(b /a )logp(b /a )

p1pqlog1pqplogpqlogq

1pplogp 1pqlog1pqqlogq

1 p q log 1 p q p log p qlogq

==

=−

⎡⎤ =− −− −−+ + ⎣⎦

⎡⎤ −− +− − − − + ⎣⎦

⎡⎤ =− − − − − + + ⎣⎦

∑∑

Ta thấy H(B/A) ∉ vào tính chất thống kê của nguồn A. Do đó:

[] m H(B) H(B/A) m H(B) H(B/A)

AA

ax ax −= −

() () ()

3

jj

j1

HB pb logpb

=

=−∑

Trong đó:

( ) ( ) ( ) ( ) ( )

()

3131232 pb pa pb/a pa pb/a

pq 1 p q q

=+

=+− =

không phụ thuộc vào tính chất thống kê của nguồn A.

Như vậy, H(B) sẽ đạt max ứng với phân bố của các xác suất p( i

a ) đảm bảo được:

1- ps - q

a1 b1

ps

q

b3

q

ps

a2 b2

1 - ps - q Chương 3: Cơ sở lý thuyết thông tin thống kê

71

() ( ) 12

1q

pb pb

2

−

==

() ( )

( ) 1q

mHB qlogq 1qlog

2 A

ax

−

⇒=−−−

( ) ( ) ( ) ( ) { } ss s s C' F 1 q 1 log 1 q p log p 1 p q log 1 p q ⇒= − − − + +−− −− ⎡⎤ ⎣⎦

Trong đó

1

F

T

=

3.5. ENTROPIE CỦA NGUỒN LIÊN TỤC. LƯỢNG THÔNG TIN CHÉO TRUNG

BÌNH TRUYỀN QUA KÊNH LIÊN TỤC KHÔNG NHỚ

3.5.1. Các dạng tín hiệu liên tục

Đối với các tín hiệu cao tần liên tục s(t) thì giá trị của nó có thể nhận một cách liên tục các

giá trị khác nhau trong một khoảng xác định

min m ss ax ÷ , còn đối số thời gian t lại có thể liên

tục hay rời rạc (hình 3.6)

Vì vậy, ta sẽ phân các tín hiệu liên tục ra 2 loại.

- Tín hiệu liên tục với thời gian rời rạc (hình 3.6a).

- Tín hiệu liên tục với thời gian liên tục (hình 3.6b).

Các tham số đặc trưng của tín hiệu liên tục là:

- Công suất phổ trung bình

- Bề rộng phổ

3.5.2. Các đặc trưng và tham số của kênh liên tục

Ta đã biết rằng các đặc trưng của kênh rời rạc là:

- Trường dấu lối vào trước hay sau bộ mã hoá: A

s(t)

smax

Δt

smin

t

s(t)

smax

smin

t

a. b.

Hình 3.6. Chương 3: Cơ sở lý thuyết thông tin thống kê

72

- Trường dấu lối ra sau bộ giải điều chế hoặc sau bộ giải mã B.

- Xác suất chuyển ( ) ij

pa/b hoặc

( ) ( )

( )

nn

ii

p/ αβ

Đối với kênh liên tục, các đặc trưng của nó là:

- Trường dấu lối vào (sau bộ điều chế): {s(t)}

- Trường dấu lối ra (trước bộ giải điều chế): {U(t)}

- Mật độ phân bố xác suất để xuất hiện ( ) j

Ut khi đã phát hiện ( ) i

st :

( ) ( ) ( ) i

t/s t j

WU

Cũng như đối với kênh rời rạc tham số quan trọng nhất của kênh liên tục là khả năng thông

qua của nó.

Định nghĩa:

Kênh Gausse không đổi là một kênh liên tục có tập tin lối vào và tập tin lối ra liên hệ với

nhau theo công thức:

( ) ( ) ( ) ut .st nt =μ + (3.39)

Trong đó μ = const, ( ) t ∉ , n(t): nhiễu cộng là tạp âm trắng phân bố chuẩn.

3.5.3. Kênh liên tục chứa trong kênh rời rạc

Tính chất:

Khả năng thông qua của kênh liên tục không nhỏ hơn khả năng thông qua của kênh rời rạc

chứa nó:

'

lt r.r ch CC'

øa lt

≥ (3.40)

Chứng minh:

Nếu phép giải điều chế và điều chế là hai phép thuận nghịch lẫn nhau như ta mong muốn thì

khi qua bộ điều chế và giải điều chế lượng thông tin là không đổi (lượng thông tin truyền qua

Mã hoá

Điều chế

Đường tin

Giải điều chế

Giải mã

Nhiễu

Kênh liên tục

Kênh rời rạc (chứa kênh liên tục)

i

a i

α s(t) u(t) i

β i

bChương 3: Cơ sở lý thuyết thông tin thống kê

73

kênh trong một đơn vị thời gian). Như vậy, khả năng thông qua của kênh liên tục đúng bằng khả

năng thông qua của kênh rời rạc. Tuy nhiên phép giải điều chế thường làm tổn hao thông tin, do

đó khả năng thông qua của kênh rời rạc không thể lớn hơn khả năng thông qua của kênh liên tục

nằm trong nó.

3.5.4. Entropie của nguồn tin liên tục (của một quá trình ngẫu nhiên liên tục)

Xét một nguồn tin S ở mỗi một thời điểm có thể phát ra những tin là một đại lượng ngẫu

nhiên s có thể nhận các giá trị liên tục trong khoảng

min m ss ax ÷ với mật độ xác suất ( ) s 1 W .

Vì trong khoảng

min m ss ax ÷ ta có vô số

những giá trị của s nên tập tin của nguồn S là

một tập vô hạn và như vậy S là một nguồn tin

liên tục. Để tính entropie của nguồn này ta

làm như sau:

Ta thực hiện một phép lượng tử hoá

hình thức bằng cách chia khoảng

min m ss ax ÷ ra n phần bằng nhau. Mỗi phần

bằng s Δ và được gọi là bước lượng tử (hình

3.7).

Ta coi rằng s sẽ nhận giá trị

i

s nếu giá

trị của nó nằm trong một phần thứ i nào đó. Như vậy s có thể nhận các giá trị sau: S' = { i

s }, i =

1, n . Xác suất để s nhận giá trị

i

s sẽ là:

( ) ( ) ii

ps s . s 1 W ≈Δ

Entropie của nguồn tin đã rời rạc hoá S' sẽ bằng:

() () ()

n

ii

i1

HS' s . slog s . s 11 WW

=

=Δ Δ ⎡ ⎤ ⎣ ⎦ ∑

Khi cho s Δ→0, ta sẽ được entropie của nguồn tin liên tục.

() () () ()

()

n

ii

s0 s0 i1

n

i

s0 i1

H S lim H S' lim s log s . s

1

lim log s . s

s

11

1

WW

W

Δ→ Δ→ =

Δ→ =

⎛⎞

⎜⎟ ==− Δ+ ⎡⎤ ⎣⎦ ⎜⎟

⎝⎠

⎛⎞

⎜⎟ +Δ

⎜⎟ Δ ⎝⎠

∑

∑

() ()

()

()

s0

1

11

H S s log ds lim s ds

ss

11

1

WW W

∞∞

Δ→ −∞ −∞

=

⎡ ⎤ ⎡⎤

=+ ⎢ ⎥ ⎢⎥

Δ ⎣⎦ ⎢ ⎥ ⎣ ⎦

∫∫

smax

si

smin

t

Hình 3.7. Chương 3: Cơ sở lý thuyết thông tin thống kê

74

() ()

() s0

11

HS slog ds lim ss

1

1

W W

∞

Δ→ −∞

⇒= +

Δ ∫ (3.41)

Từ (3.41) ta thấy entropie một chiều của nguồn tin liên tục lớn vô hạn do

s0

1

lim

s Δ→

=∞

Δ

.

Số hạng thứ hai không phụ thuộc vào bản chất thống kê của nguồn (tín hiệu) mà chỉ có số hạng

thứ nhất phụ thuộc vào bản chất thống kê của nguồn, vì vậy ta có thể lấy nó đặc trưng cho những

quá trình ngẫu nhiên khác nhau. Ta đặt:

() ()

()

1

h S s log ds

s

1

1

W W

∞ Δ

−∞

= ∫ (3.42)

và gọi h(S) là entropie vi phân (hay entropie tương đối) của nguồn S.

Chú ý:

- Khác với entropie của nguồn rời rạc, h(S) có thể nhận các giá trị dương, âm (hữu hạn).

- Khác với entropie của nguồn rời rạc, h(S) phụ thuộc vào thang tỷ lệ của s, tức là phụ thuộc

vào việc chọn đơn vị đo. Nếu tăng s lên υ lần:

*

s.s = υ , khi đó:

( ) () ()

*

*

ds 1

ss s

ds

11 1 WW W ==

υ

() () () ()

****

hS slog sds hS log 11 WW

∞

−∞

⇒=− =+υ ∫

h(S) cũng có tính chất cộng tính.

3.5.5. Mẫu vật lý minh hoạ sự lớn vô hạn của entropie của nguồn liên tục

Giả sử ta truyền tin từ A đến B bằng đường dây lý

tưởng: không tổn hao, không gây nhiễu. ở đầu B ta đặt

một máy thu là một volt kế lý tưởng (có tạp âm nội bộ

bằng không, nên có thể đo với độ chính xác tuỳ ý,

V Z =∞). Tín hiệu phát nằm trong khoảng

( ) 01 ÷ Vol. Như vậy, ở đâu thu ta sẽ nhận được u = s.

Nếu trường { } i

Aa,i1,10 == (có 10 tin) thì

ta có thể mã hoá một cách đơn giản bằng cách đối chứng như sau:

1 a0,1V ↔ ,

2 a0,2V ↔ , ... ,

10 a1V ↔

Giả sử các tin là đồng xác suất thì H(A) = log 10.

Nếu { } i

A a , i 1,100 == thì ta có thể phát đi bằng cách đối chứng:

A B

s u

Hình 3.8. Chương 3: Cơ sở lý thuyết thông tin thống kê

75

1 a0,01V ↔ ,

2 a0,02V ↔ , ... ,

100 a1V ↔

Nếu các tin là đồng xác suất thì H(A) = log100.

Tương tự, nếu

6

i1,10 = thì chỉ cần chọn bước lượng tử

6

s10−

Δ= thì ta có thể đảm bảo

truyền được mọi tin. Nếu các tin là đồng xác suất thì

6

H(A) log10 = .

Vì kênh và thiết bị thu không có nhiễu nên ta có thể chọn s Δ bé tuỳ ý để truyền một số tin

lớn tuỳ ý. Khi đó entropie của nguồn tin có thể lớn tuỳ ý. Nếu s 0 H(A) Δ →⇒ →∞.

Trong thực tế, luôn tồn tại nhiễu n(t) trên đường dây và volt kế luôn có tạp âm nội bộ. Do

đó không thể chọn s Δ nhỏ tuỳ ý được mà phải là một số hữu hạn. Vì vậy entropie của nguồn trên

thực tế là hữu hạn.

3.5.6. Lượng thông tin chéo trung bình truyền theo kênh liên tục không nhớ

Xét một nguồn liên tục S và giả thiết các tin s do nguồn sinh ra là độc lập thống kê với

nhau, nghĩa là xét nguồn liên tục không nhớ. Xét kênh liên tục chỉ có can nhiễu cộng n(t) có các

giá trị cũng độc lập thống kê với nhau. Khi đó ở lối ra của kênh ta nhận được các tin:

u.sn =μ +

Các tin này cũng độc lập thống kê với nhau. Khi đó kênh xét cũng là kênh liên tục không

nhớ. Ta sẽ tính lượng thông tin trung bình truyền theo kênh này: I(S, U).

Ta cũng sẽ lượng tử hoá các tin ở đầu thu và đầu phát. Bước lượng tử ở đầu phát là s Δ ,

bước lượng tử ở đầu thu là u Δ . Khi đó ta có hai nguồn đã rời rạc sau: { } i

S' s , i 1,n == và

{ } j

U' u , j 1,m == . Tương tự như mục 4, ta có:

Xác suất để s nhận giá trị

i

s sẽ là: ( ) ( ) ii

ps s . s 1 W = Δ .

Tương tự, ta có: ( ) ( ) jj

pu u .u 1 W =Δ .

Xác suất để đồng thời s nhận giá trị

i

s và u nhận giá trị

j

u gần đúng bằng:

( ) ( ) ij ij

ps,u s,u . s.u 2 W =ΔΔ

Nếu coi

i

s là tin truyền đi và

j

u là tin nhận được tương ứng thì khi đó kênh sẽ là rời rạc

không nhớ và lượng thông tin chéo trung bình truyền theo kênh rời rạc đó là:

() ()

( )

()

nm ij

ij

i i1j1

ps/u

IS',U' s,u . s. u.log

ps

2 W

==

=ΔΔ ∑∑

Chú ý rằng theo công thức nhân xác suất: Chương 3: Cơ sở lý thuyết thông tin thống kê

76

()

( )

()

( )

()

() ()

()

() ()

ij i j

ij

jj

nm ij

ij

i1j1 jj

ps.u s,u . s.u

ps/u

pu u .u

s,u . s. u

IS',U' s,u . s. u.log

u.u. s.s

2

1

2

2

11

W

W

W W WW ==

ΔΔ

==

Δ

ΔΔ

⇒= ΔΔ

Δ Δ

∑∑

Khi cho s0vµ u 0 Δ→ Δ→ ta sẽ chuyển từ kênh rời rạc sang kênh liên tục và lượng

thông tin trung bình truyền theo kênh liên tục là:

() ( ) ()

( )

() ( ) s0

u0

s,u

I S,U lim I S',U' s,u log ds.du

s. u

2

2

11

W W WW

∞∞

Δ→ −∞ −∞ Δ→

== ∫∫ (3.43a)

hay

()

( )

() ( )

s,u

IS,U Mlog

s. u

2

11

W

WW

⎡⎤

= ⎢⎥

⎣⎦

(3.43b)

3.6. ENTROPIE VI PHÂN CÓ ĐIỀU KIỆN. TÍNH CHẤT CỦA CÁC TÍN HIỆU

GAUSSE

3.6.1. Entropie vi phân có điều kiện

Từ (3.43b), ta có:

()

()

( )

()

s,u 1

IS,U Mlog log

su

2

11

W

WW

⎡⎤

=+ ⎢⎥

⎣⎦

()

()

( )

()

s,u 1

I S,U M log M log

su

2

11

W

WW

⎡ ⎤⎡ ⎤

⇒= + ⎢ ⎥⎢ ⎥

⎣ ⎦⎣ ⎦

()

()

()

( )

()

s,u 1

s log ds s,u log ds.du

su

2

12

11

W WW WW

∞∞∞

−∞ −∞−∞

=+ ∫∫∫ (3.44a)

Ta có thể viết dưới dạng sau:

I(S,U) = h(S) - h(S/U) (3.44b)

Trong đó h(S) chính là entropie vi phân của nguồn.

() ()

()

1

hS slog ds

s

1

1

W W

∞

−∞

= ∫

Chương 3: Cơ sở lý thuyết thông tin thống kê

77

() ()

( )

()

u

hS/U s,ulog ds.du

s,u

1

2

2

W W W

∞∞

−∞−∞

= ∫∫

()

()

1

s,u log ds.du

s/u

2

1

W W

∞∞

−∞ −∞

= ∫∫ (3.45)

Chú ý:

Theo công thức xác suất nhân: ( ) ( ) ( ) s,u u . s / u 211 WWW =

h(S/U) tính theo (3.45) được gọi là entropie vi phân có điều kiện của nguồn S khi đã biết

nguồn U.

Đối với nguồn rời rạc, ta có: I(A,B) = H(A) - H(A/B)

H(A) là lượng thông tin riêng trung bình chứa trong mỗi dấu của A.

H(A/B) là lượng thông tin tổn hao trung bình của mỗi tin do nhiễu trong kênh gây ra.

Về mặt hình thức, ta thấy h(S) đóng vai trò của H(A), còn h(S/U) đóng vai trò của H(A/B).

Về mặt ý nghĩa thì không phải như vậy, bởi vì h(S) và h(S/U) có thể âm và phụ thuộc vào

thang tỷ lệ. Tuy vậy, việc đưa ra h(S) và h(S/U) rất có lợi cho việc tính toán.

Từ (3.44a) và (3.44b) ta có thể suy ra các tính chất sau của I(S,U):

- I(S,U) ≥ 0, I(S,U) = 0 khi kênh bị đứt: W(u/s) = W(u)

- I(S,U) = I(U,S) = h(U) - h(U/S): tính chất đối xứng.

- Nếu kênh là không nhiễu n(t) = 0 thì I(S,U) = ∞.

Hai tính chất đầu tương tự như trong trường hợp kênh rời rạc không nhớ. Tính chất sau suy

ra từ tính chất lớn vô hạn của entropie của nguồn liên tục.

Chú ý:

I(S,U) không phụ thuộc vào thang tỷ lệ.

3.6.2. Entropie vi phân của nhiễu Gausse

Xét nhiễu Gausse n(t) có M[n] = 0 và D[n] =

n P .

Hàm mật độ phân bố xác suất của nó là:

()

n n

1

2P 2P

2

n

Wn exp-

⎧ ⎫ ⎪ ⎪

= ⎨ ⎬

π ⎪ ⎪ ⎩⎭

Ta sẽ tính vi phân entropie vi phân của nhiễu này. Chương 3: Cơ sở lý thuyết thông tin thống kê

78

Ta có: () ()

2

n

n

2P

n hN log 2Pe dn Wn

∞

−∞

⎛⎞

⎜⎟

=π ⎜⎟

⎜⎟

⎝⎠

∫

() () ()

() ()

[]

2

n

n

n

2P

n

2

n

n

1 Dn P

h N . log 2 P .dn . log e .dn

log e

log 2 P .dn n . .dn

2P

Wn Wn

Wn Wn

∞∞

−∞ −∞

∞∞

−∞ −∞ = ==

=π+

=π +

∫∫

∫∫

() n

1

hN log 2P loge

2

⇒= π+

( ) n hN log 2P.e ⇒= π (3.46)

3.6.3. Lượng thông tin chéo trung bình truyền theo kênh Gausse

Ta có:

( ) ( ) ( )

()

()

()

IS,U hU hU/S

1

u log du h U/S

u

1

1

W W

∞

−∞

=−

=− ∫

Ta sẽ tính h(U/S) trong trường hợp nhiễu Gausse. Kênh ta xét sẽ là kênh Gausse:

( ) ( ) ( ) ut .st nt =μ +

() () ()

( ) ()() ()

() ( ) ( )

h U/S s,u .log u / s .du.ds

hU/S s. u/s.log u/s.du.ds

s.ds u/s.log u/s.du

21

11 1

11 1

WW

WW W

WW W

∞∞

−∞ −∞

∞∞

−∞ −∞

∞∞

−∞ −∞

=−

=−

=−

∫∫

∫∫

∫∫

( ) () () hU/S u/s.log u/s.du 11 WW

∞

−∞

=− ∫ (3.47)

Để xác định h(U/S) ta phải tính được ( ) u/s 1 W . Chương 3: Cơ sở lý thuyết thông tin thống kê

79

Vì yếu tố ngẫu nhiên chỉ do nhiễu gây nên, đo đó với bất cứ một giá trị nhất định nào của s

thì xác suất để u rơi vào khoảng du cũng chính bằng xác suất để n rơi vào khoảng dn.

{ } {} du pu pn dn

s

∈=∈

( ) ( ) u/s du n dn 11 WW =

() () () du

dn

dn 1 u/s n n

du

11 1 WW W ⇒= =

Với ()

du d ds dn

sn 1

dn dn dn dn

=+=+= V 0 khi s,n

ds

× ®éc lËp

dn

⎛⎞

= ⎜⎟

⎝⎠

Vậy () ()

n n

1

u/s n

2P 2P

2

11

n

WW exp-

⎧ ⎫ ⎪ ⎪

== ⎨ ⎬

π ⎪ ⎪ ⎩⎭

( ) ( ) n U/S n log 2 eP hh ⇒==π

()

()

n

1

u .log .du log 2 eP

u

1

1 -

I(U,S) = W W

∞

∞

⇒−π ∫ (3.48)

Nếu u cũng có phân bố chuẩn thì:

() u Ulog2eP h =π

Do s(t) và n(t) là độc lập nên:

22

usn u n PPP =+ =σ+σ

Vậy: () () sn Ulog2ePP h =π+

Cuối cùng, ta có: I(S,U) = h(U) - h(S/U)

ss

nn

PP 1

I(S,U) log 1 log 1

P2 P

⎛⎞

=+= + ⎜⎟

⎝⎠

(3.49)

Trong đó

s

P là công suất trung bình của tín hiệu hữu ích (tín hiệu phát).

Nhận xét:

Từ (3.49) ta thấy I(S,U) không phụ thuộc vào hình dạng và cấu trúc của tín hiệu, mà chỉ phụ

thuộc vào tỷ số

sn P/P . Thực ra kết luận này chỉ đúng về hình thức, thực ra sau này ta sẽ thấy nếu

cấu trúc và hình dạng của tín hiệu thay đổi thì

sn P/P cũng sẽ thay đổi, do đó I(S,U) cũng sẽ khác

nhau đối với các tín hiệu có cấu trúc và hình dạng khác nhau. Chương 3: Cơ sở lý thuyết thông tin thống kê

80

3.6.4. Tính chất của các tín hiệu có phân bố chuẩn

Định lý:

Trong số những quá trình (tín hiệu) có cùng công suất trung bình (

2

σ ), tín hiệu có phân bố

Gausse sẽ cho entropie vi phân lớn nhất. Tức là:

() () ()

2

hX x.log x.dx log 2e 11 WW

∞

−∞

= −≤πσ ∫

() ()

2

m h X log 2 e khi x m 1 ax W Ët ®é chuÈn =πσ −

Chứng minh:

Gọi x(t) là tín hiệu không Gausse.

~

x(t) là tín hiệu Gause:

~ ~

2

~

x x

1

x

2P 2P

~

1

x

Wexp-

⎧ ⎫

⎛⎞ ⎪ ⎪

= ⎨ ⎬ ⎜⎟

π ⎝⎠ ⎪ ⎪

⎩⎭

Điều cần chứng minh ở định lý trên trương đương với việc chứng minh bất đẳng thức sau:

( ) x hX log 2eP 0 −π≤ (*)

Trước hết theo giả thiết, ta có:

~ x

x

DDD ==

()

2 ~~~

2

xxdxxxdx 11 WW

∞∞

−∞ −∞

⎛⎞

⇒= ⎜⎟

⎝⎠

∫∫ (a)

Ta có:

()

~~~~

~~

hX xlog xdx

loge

log 2 D x d x x dx

2D

11

2

11

WW

WxW

∞

−∞

∞∞

−∞ −∞

⎛⎞ ⎛⎞ ⎛⎞

=− = ⎜⎟ ⎜⎟ ⎜⎟

⎝⎠ ⎝⎠ ⎝⎠

⎛⎞

=π + ⎜⎟

⎝⎠

∫

∫∫

()

~~

do x d x x dx 1 v 11 WWµ do(a)

∞∞

−∞ −∞

⎛⎞ ⎛⎞

== ⎜⎟ ⎜⎟

⎜⎟

⎝⎠ ⎝⎠

∫∫ Chương 3: Cơ sở lý thuyết thông tin thống kê

81

()

()

2 ~

~

1x

h X log2 D loge x dx

22D

xlog xdx

1

11

W

WW

∞

−∞

∞

−∞

⎡⎤ ⎛⎞

⇒=−−π− ⎢⎥ ⎜⎟

⎢⎥ ⎝⎠ ⎣⎦

⎛⎞

=− ⎜⎟

⎝⎠

∫

∫

Từ (*) ⇒ cần chứng minh: ()

~

hX hX 0

⎛⎞

− ≤ ⎜⎟

⎝⎠

Ta có:

( ) () () ()

~~

hX hX xlog xdx xlog xdx 11 11 WW WW

∞∞

−∞ −∞

⎛⎞ ⎛⎞

−=− + ⎜⎟ ⎜⎟

⎝⎠ ⎝⎠

∫∫

()

()

~

x

xlog dx

x

1

1

1

W

W W

∞

−∞

⎛⎞

⎜⎟

⎝⎠

= ∫ (**)

Với a > 1 bao giờ ta cũng có:

a log x x 1 ≤ − .

Nên:

() ()

()

()

~

~

~

x

hX hX x 1dx

x

xdx xdx

1

1

1

11

W

W W

WW

∞

−∞

∞∞

−∞ −∞

⎡ ⎤ ⎛⎞

⎢ ⎥ ⎜⎟

⎛⎞ ⎝⎠ ⎢ ⎥ −≤ − ⎜⎟

⎢ ⎥ ⎝⎠

⎢ ⎥

⎣ ⎦

⎛⎞

≤− ⎜⎟

⎝⎠

∫

∫∫

Vậy () ()

~~~

hX hX 0 hX hX x x

⎛⎞ ⎛⎞

−≤⇔≤∀≠ ⎜⎟ ⎜⎟

⎝⎠ ⎝⎠

()

~

mhXlog2eD ax h X ⎛⎞

==π ⎜⎟

⎝⎠

Ý nghĩa định lý:

Trong số các quá trình ngẫu nhiên có cùng phương sai thì quá trình có phân bố chuẩn thể

hiện "tính ngẫu nhiên" nhiều hơn cả. Do đó ta thấy rằng trong số những tạp có cùng phương sai

thì tạp phân bố chuẩn có tác hại lớn nhất đối với việc truyền tin. (vì entropie đặc trưng cho độ bất Chương 3: Cơ sở lý thuyết thông tin thống kê

82

định, mà entropie của tạp chuẩn max nên độ bất định của nó lớn nhất). Đó là lý do vì sao trong

các bài toán của vô tuyến điện thống kê người ta thường xét tạp chuẩn.

Bằng phương pháp tương tự, ta có thể chứng minh được:

a. Trong số tất cả các phân bố trong một khoảng hữu hạn (a,b): ()

b

1

a

Wxdx 1 = ∫ . Đại

lượng ngẫu nhiên phân bố đều có entropie lớn nhất. H(X) = log(b - a) = log 2 3 σ l

b. Trong số tất cả các đại lượng ngẫu nhiên liên tục dương có cùng kỳ vọng m:

() 1

0

Wxdx 1

∞

= ∫ và () 1

0

xW x dx m

∞

= ∫ . Đại lượng ngẫu nhiên phân bố theo luật mũ có

entropie lớn nhất.

3.7. KHẢ NĂNG THÔNG QUA CỦA KÊNH GAUSSE

3.7.1. Khả năng thông qua của kênh Gausse với thời gian rời rạc

Định nghĩa:

Kênh Gausse không đổi với thời gian rời rạc là kênh Gausse không đổi có tín hiệu lối vào

s(t) là hàm liên tục của đối số rời rạc.

Ta có thể coi tín hiệu liên tục với thời gian rời rạc (hình 5.1a) là một dãy xung có biên độ là

các giá trị bất kỳ trong khoảng

min m ss ax ÷ và chu kỳ lặp lại (đồng thời cũng là độ rộng xung)

là khoảng thời gian rời rạc t Δ . Đem các xung (tin) đó truyền vào kênh thì tốc độ truyền tin của

kênh (cũng là tốc độ truyền tin của nguồn) với thời gian rời rạc sẽ là:

K 1

t

υ= Δ

Tương tự như đối với kênh rời rạc, khả năng thông qua của kênh Gausse với thời gian rời

rạc sẽ là:

K C' .max I(U,S) =υ (3.50)

I(U,S) là lượng thông tin chéo trung bình truyền trong kênh liên tục. Đối với kênh Gausse

không đổi, ta có:

( ) ( ) ( ) ( )

() ()

n

n

IU,S hU hN hU log 2eP

mIU,SmhU log2eP ax ax

=−=− π

⇒=−π

Theo định lý ở phần 3.6, ta thấy h(U) đạt max khi u có phân bố chuẩn:

( ) u mhU log2eP ax =π Chương 3: Cơ sở lý thuyết thông tin thống kê

83

ở một thời điểm nào đó, ta có: u.sn = μ+

Do s và n độc lập nên:

usn PP P μ =+

Vậy:

() Ksn n C' log 2 e P P log 2 eP μ

⎡⎤ =υ π + − π

⎢⎥ ⎣⎦

sn

K

n

PP

C' log

P

μ +

⇒=υ

s

K

n

P 1

C' log 1

2P

μ ⎛⎞

⇒=υ + ⎜⎟

⎝⎠

(3.51)

Trong đó

sn PP μ là tỷ số tín trên tạp ở đầu ra của kênh liên tục (đầu vào bộ giải điều chế).

Ta khảo sát ( ) sn C' f P P μ = :

Khi

s

n

P

0C'0

P

μ

→⇒ → . Tức là nếu S/N rất bé thì kênh coi như bị đứt.

Khi

s

n

P

P

μ

↑ nhưng còn nhỏ (

Khi

s

n

P

P

μ

↑ nhưng đã khá lớn (> 12) thì C' tăng theo rất chậm.

Do đó ta thấy không nên chạy theo việc tăng công suất của máy phát để tăng khả năng

thông qua của kênh mà nên tăng tốc độ truyền tin của kênh (vì C' ~

K υ ).

3.7.2. Khả năng thông qua của kênh Gausse với thời gian liên tục trong một giải tần hạn

chế

Ta sẽ tính kảh năng thông qua của kênh Gausse trong trường hợp tín hiệu vào s(t) là hàm

liên tục của thời gian liên tục, có phổ hữu hạn F.

Ở đầu vào của bộ giải điều chế ,ta có thể đặt thêm một bộ lọc tần thấp có giải thông F. (Giải

tần công tác của kênh lúc này cũng chính là giải thông tần của bộ lọc này). Như vậy bộ lọc sẽ

không ảnh hưởng đến méo tín hiệu nhưng sẽ hạn chế được tạp âm trắng. Theo định lý

B.A.Kachennhicop ta có thể rời rạc hoá tín hiệu theo trục t mà vẫn không làm mất thông tin nếu

như

1 t

2F Δ= . Như vậy ta đã thay việc truyền tín hiệu liên tục với thời gian liên tục bằng việc

truyền tin liệu liên tục với thời gian rời rạc. Khi đó tốc độ truyền của kênh (số xung truyền trong

một đơn vị thời gian) sẽ là:

K

1

2F

t

υ= =

Δ

. Do đó theo (3.51), ta có:

c'

2

1

PμS/Pn

0 4 8 12

Hình 3.9. Chương 3: Cơ sở lý thuyết thông tin thống kê

84

s

n

P

C' Flog 1

P

μ ⎛⎞

=+ ⎜⎟

⎝⎠

(3.52)

Trong đó: F là bề rộng phổ của tín hiệu

n P là công suất trung bình của nhiễu trong giải F

Với tạp trắng ta có:

n0 PN.F =

0 N là mật độ phổ công suất thực tế của nhiễu

s

0

P

C' Flog 1

N.F

μ ⎛⎞

⇒= + ⎜⎟

⎝⎠

(3.52')

Nhận xét:

Nếu tăng C' bằng cách tăng F thì kéo theo

n P ↑

S

N

⎛⎞

⇒↓ ⎜⎟

⎝⎠

. Như vậy giữa C', F và

(S/N) có sự trả giá, ta được lợi về mặt này thì phải chịu thiệt ở mặt khác.

Ta vẫn có thể thu chính xác được tín hiệu (đảm bảo C' = const) trong trường hợp S/N bé

(công suất của máy phát nhỏ, cự ly liên lạc xa, nhiễu mạnh) bằng cách mở rộng phổ của tín hiệu.

Ví dụ: trong thông tin vũ trụ, S/N rất nhỏ nên tín hiệu liên lạc phải là tín hiệu giải rộng (tín hiệu

điều chế phức tạp, tín hiệu giả tạp,...)

Đó chính là ý nghĩa của (3.52), nó còn được gọi là công thức Shannon.

3.7.3. Khả năng thông qua của kênh Gausse với thời gian liên tục trong giải tần vô hạn

Trong (3.52'), nếu lấy cơ số của log là e thì C' được đo bằng [nat/s]. Nếu đo bằng [bit/s]

thì:

s

0

P 1

C' 1,443Fln 1 .

NF

μ ⎛⎞

=+ ⎜⎟

⎝⎠

[bit/s] (3.53)

Bây giờ ta sẽ xét sự phụ thuộc của C' vào F.

- Khi F0 → thì rõ ràng là C' 0 →

- Khi F ↑ thì C' ↑

Đặc biệt, ta sẽ xét giá trị của C' khi F→∞, tức là khi giải thông của kênh không hạn chế.

Đặt

s

0

P 1

.x

NF

μ

=

s

0

P 1

F.

Nx

μ

⇒=

Khi x0 → thì F→∞. Chương 3: Cơ sở lý thuyết thông tin thống kê

85

Ta ký hiệu: ()

s '

Fx0 0

P 1

C lim C' lim . .ln 1 x .1,443

Nx

μ

∞ →∞ →

⎡⎤

== + ⎢⎥

⎣⎦

()

s '

x0 0

P 1

C 1,443. . lim .ln 1 x

Nx

μ

∞ →

⎡⎤

⇒= + ⎢⎥

⎣⎦

Ta đã có: ()

1/ x

x0

lim 1 x 1

→

+=

s '

0

P

C 1,443.

N

μ

∞ ⇒= (3.54)

Đồ thị C' = f(F) được vẽ ở hình 3.10.

Tại giá trị

s

0

P

F

N

μ

=

s

0

P

CF

N

μ

⇒== .

Từ đồ thị, ta thấy: Khả năng thông qu của kênh Gausse với thời gian liên tục là một đại

lượng giới nội:

'

0C'C∞ ≤≤ . Điều này được giải thích như sau: Trong thực tế, mọi vật đều có

tạp âm nhiệt. Tạp âm nhiệt có phân bố chuẩn và có mật độ công suất

o

0 Nk.T = .

Trong đó: k là hằng số Boltzman, k =

23

1, 38.10−

J/độ.

o

T là nhiệt độ tuyệt đối của vật.

Vì vậy khả năng thông qua của mọi kênh thực tế đều bị giới nội.

3.7.4. Định lý mã hoá thứ hai của Shannon đối với kênh liên tục

Đối với kênh liên tục, định lý mã hoá thứ hai của Shannon được phát biểu như sau:

Định lý:

Các nguồn tin rời rạc có thể mã hoá và truyền theo kênh liên tục với xác suất sai bé tuỳ ý

khi giải mã các tín hiệu nhận được nếu khả năng phát của nguồn nhỏ hơn khả năng thông qua của

kênh. Nếu khả năng phát của nguồn lớn hơn khả năng thông qua của kênh thì không thể thực hiện

được mã hoá và giải mã với xác suất sai bé tuỳ ý được.

3.7.5. Ví dụ: Khả năng thông qua của một số kênh thực tế

- Kênh viễn thông chuyển tiếp:

( )

67

C' n.10 n.10 =÷ Hartley/s

- Điện thoại, điện báo ảnh, viễn thông chuyển tiếp:

c'

c'∞

PμS/N0

0 PμS/N0 F

Hình 3.10. Chương 3: Cơ sở lý thuyết thông tin thống kê

86

( )

34

C' n.10 n.10 =÷ Hartley/s

- Điện báo:

( )

2

C' n.10 n.10 =÷ Hartley/s

- Con người: + Thị giác:

' 6

1 Cn.10 = Hart./s

+ Thính giác:

' 3

2 Cn.10 = Hart./s.

Điều này chứng tỏ "trăm nghe không bằng một thấy"

+ Xúc giác

'

3 C :

'''

231 CCC

Con người chỉ có thể nhận thức được các thông tin đưa ra với tốc độ truyền ≤ 15 Hart./s.

Một quyển sách 100 trang ( ≈ 2000 dấu/trang): I = ( )

37

10 10 ÷ bit.

Trí nhớ ngắn hạn của con người: ( )

25

10 10 ÷ bit.

Trung bình một đời người tiếp nhận

10

10 ≈ bit.

BÀI TẬP

3.1. Thành phố nọ có 1% dân số là sinh viên. Trong số sinh viên có 50% là nam thanh niên. Số

nam thanh niên trong thành phố là 32%. Giả sử ta gặp một nam thanh niên. Hãy tính lượng thông

tin chứa trong tin khi biết rằng đó là một sinh viên.

3.2. Có hai hộp đựng bút chì, mỗi hợp đựng 20 bút chì. Hộp thứ nhất có 10 bút trắng, 5 bút đen và

5 bút đỏ. Hộp thứ hai có 8 bút trắng, 8 bút đen và 4 bút đỏ. Ta lấy hú hoạ một bút chì từ mỗi hộp.

Hỏi rằng phép thử nào trong hai phép thử nói trên có độ bất định lớn.

3.3. Các tín hiệu

1 x ,

2 x với các xác suất tiên nghiệm ( ) 1 px 3/4 = , ( ) 2 px 1/4 = được

truyền theo kênh nhị phân đối xứng có nhiễu như hình vẽ. Do có nhiễu nên xác suất thu đứng mỗi

tín hiệu giảm đi chỉ bằng 7/8. Hãy tìm:

a. Lượng tin tức riêng có điều kiện ( ) 22 Ix / y

b. Lượng tin tức chéo ( ) 22 Ix,y

c. Các lượng tin tức

trung bình ( ) 2 IX,y ,

H(X), H(X/Y), I(X,Y)

1 y

2 y

2 x

1 x

( ) 11 py/x 7/8 =

( ) 22 py /x 7/8 =

( ) 12 py/x 1/8 =

( ) 21 py /x 1/8 =

() 1 px 3/4 =

( ) 2 px 1/4 = Chương 3: Cơ sở lý thuyết thông tin thống kê

87

3.4. Một bảng chữ cái gồm bốn con chữ

1 x ,

2 x ,

3 x ,

4 x . Giá trị xác suất xuất hiện riêng rẽ các

chữ () i

px và xác suất có điều kiện ( ) j i

px/x cho trong các bảng dưới đây.

i

x

1 x

2 x

3 x

4 x

( ) i

p x 0,5 0,25 0,125 0,125

1 x

2 x

3 x

4 x ()

4

j i

j1

px/x

=

∑

1 x

2 x

3 x

4 x

0

0,2

0,25

0,2

0,2

0,2

0

0,4

0,4

0,3

0,25

0,4

0,4

0,3

0,5

0

1

ơ

1

1

1

Hãy tìm độ thừa của nguồn tin trong hai trường hợp:

a. Khi các con chữ độc lập thống kê với nhau.

b. Khi các con chữ phụ thuộc thống kê với nhau.

3.5. Một điện đài vô tuyến điện gồm 16 khối có giá trị như nhau về độ tin cậy và được mắc nối

tiếp và một thiết bị kiểm tra - thông báo sự hỏng hóc của các khối. Hãy tính só lần thử ít nhất tiến

hành bằng thiết bị kiểm tra - thông báo đó để có thể phát hiện bất cứ sự hỏng hóc nào của tất cả

các khối.

3.6. Một điện đài của địch có thể làm việc trên sóng

1 λ (sự kiện

1 A ) hoặc ở trên sóng

2 λ (sự

kiện

2 A ); nó cũng có thể làm việc ở chế độ liên tục (sự kiện

1 B ) cũng như ở chế độ xung (sự

kiện

2 B ). Xác suất các sự kiện đồng thời có giá trị như nhau:

( ) 11 pAB 0,15 = ; ( ) 12 pAB 0,7 = ; ( ) 21 pAB 0,1 = ; ( ) 22 pAB 0,05 = .

j

x

i

x Chương 3: Cơ sở lý thuyết thông tin thống kê

88

Hãy tính lượng tin tức về chế độ công tác của điện đài ấy nếu coi rằng độ dài bước sóng đã

biết.

3.7. Xác định khả năng thông qua của kênh nhị phân đối xứng có xoá (như hình vẽ). Nếu các dấu

i

x và

j

y có thời hạn τ như nhau và

1

F

τ= . F là tần số phát đi các dấu.

Ghi chú: Giải bằng cách tìm cực trị của hàm ( ) ( ) = HB fp

3.8. Ở đầu vào một máy thu nhận được tín hiệu hỗn hợp y(t) = x(t) + n(t). Trong đó tín hiệu x(t)

và can nhiễu n(t) đều là các quá trình ngẫu nhiên chuẩn, độc lập, có kỳ vọng bằng không và

phương sai lần lượt bằng

2

s σ và

2

n σ . Hãy tính:

a. Lượng tin tức I(x,y) về tín hiệu x(t) chứa trong tín hiệu thu được y(t).

b. Lượng tin tức chéo trung bình.

3.9. A chọn một trong các số từ 0 ÷ 7. Hỏi B phải dùng trung bình bao nhiêu câu hỏi để tìm ra số

A nghĩ?

3.10. Tính độ rộng giải thông của một kênh vô tuyến truyền hình truyền hình ảnh đen trắng với

5

5.10 yếu tố, 25 ảnh trong 1s và có 8 mức sáng đồng xác suất, với tỷ số

2

ss

n0

P

15

PN.F

σ

== .

Nếu coi rằng ảnh vô tuyến truyền hình xem như một dạng tạp âm trắng.

3.11. Tìm mật độ phổ tín hiệu S(f) để bảo đảm tốc độ truyền tin cực đại khi cho trước công suất

toàn phần của tín hiệu: ()

2

1

f

s

f

PSfdf = ∫ và mật độ phổ của nhiễu N(f).

3.12. Hãy so sánh khả năng thông qua của hai kênh thông tin nếu kênh thứ nhất chịu một tác động

của một tạp âm trắng, chuẩn trong giải tần F với phương sai

22

1V σ= , còn kênh thứ hai chịu

tác động của một tạp âm trắng, phân bố đều trong khoảng 1, 5 ± với giải tần 2F. Coi rằng công

suất của tín hiệu rất lớn hơn công suất của tạp âm.

1 - ps - q

p(x1) = p x1 y1

ps

q

y3

ps

p(x2) = 1 - p x2 y2

1 - ps - q

Chương 3: Cơ sở lý thuyết thông tin thống kê

89

3.13. Trong 27 đồng xu giống nhau có 1 đồng xu giả nhẹ hơn. Giả sử ta dùng một cân đĩa thăng

bằng (có hai đĩa cân) để xác định đồng xu giả. Hãy tính số lần cân trung bình tối thiểu để xác định

được đồng xu giả. Nêu thuật toán cân.

3.14. Trong bộ tú lơ khơ 52 quân bài (không kể phăng teo), A rút ra một quân bài bất kỳ. Tính số

câu hỏi trung bình tối thiểu mà B cần đặt ra cho A để xác định được quân bài mà A đã rút. Nêu

thuật toán hỏi? Giả sử A đã rút ra 5 rô, hãy nêu các câu hỏi cần thiết.

Chương 4: Cơ sở lý thuyết mã hóa

90

CHƯƠNG IV - CƠ SỞ LÝ THUYẾT MÃ HÓA

4.1. CÁC ĐỊNH NGHĨA VÀ KHÁI NIỆM CƠ BẢN

4.1.1. Các định nghĩa cơ bản

4.1.1.1. Mã hóa

Tập các tin rời rạc rất đa dạng và phong phú. Để hệ thống truyền tin số có thể truyền được

các tin này cần phải có một quá trình biến đổi thích hợp đối với các tin rời rạc, đó chính là quá

trình mã hóa.

Định nghĩa 1: Mã hóa là một ánh xạ 1- 1 từ tập các tin rời rạc

i

a lên tập các từ mã

i

n

i

α

i

n

i i

:a f →α

Để có thể dễ dàng mã hóa và giải mã, từ các từ mã

i

n

i

α thường là các phần tử của một cấu

trúc đại số nào đó. Bởi vậy ta có thể định nghĩa cụ thể hơn cho phép mã hóa.

Định nghĩa 2: Mã hóa là một ánh xạ 1- 1 từ tập các tin rời rạc

i

a lên một tập con có cấu

trúc của một cấu trúc đại số nào đó.

4.1.1.2. Mã

Định nghĩa 3: Mã (hay bộ mã) là sản phẩm của phép mã hóa, hay nói cách khác mã là một

tập các từ mã được lập nên theo một luật đã định.

4.1.1.3. Các yếu tố của từ mã

Định nghĩa 4: Độ dài từ mã

i

n là số các dấu mã cần thiết dùng để mã hóa cho tin

i

a .

Nếu

i

nconst = với mọi i thì mọi từ mã đều có cùng độ dài. Bộ mã tương ứng được gọi là

bộ mã đều.

Nếu

ij

nn ≠ thì bộ mã tương ứng được gọi là bộ mã không đều

Định nghĩa 5: Số các dấu mã khác nhau (về giá trị) được sử dụng trong bộ mã được gọi là

cơ số mã. Ta ký hiệu giá trị này là m.

Nếu m = 2 thì bộ mã tương ứng được gọi là mã nhị phân.

Nếu m = 3 thì bộ mã tương ứng được gọi là mã tam phân

............

Nếu m = p thì bộ mã tương ứng được gọi là mã p phân.

Thông thường các dấu mã được chọn là các phần tử trong một trường F nào đó. Chương 4: Cơ sở lý thuyết mã hóa

91

Ví dụ 1: Từ mã

7

i

α trong bộ mã đều nhị phân có độ dài 7 có thể mô tả như sau:

7

i

0110101 α=

Mỗi một dấu mã trong từ mã này chỉ có thể nhận một trong hai giá trị {} 0,1 , mỗi dấu mã là

một phần tử của trường nhị phân GF(2).

4.1.2. Các khái niệm cơ bản

4.1.2.1. Độ thừa của một bộ mã đều (D)

Cho nguồn rời rạc A gồm s tin: { } i

Aa;1,s = .

Xét phép mã hóa f sau:

nn

iii

:a ; V →α α ∈ f .

Cơ số mã là m, khi đó số các từ mã độ dài n có thể có là:

n

Nm = .

Định nghĩa 6: Độ thừa của một bộ mã đều được xác định theo biểu thức sau:

( ) ( )

()

( )

()

[]

00 0

00

HV HA HA D1% HV HV

Δ −

==− (4.1)

Trong đó : ( ) 0 HA logs =

( ) 0 HV logNnlogm ==

Ví dụ 2: Ta có mã hóa 4 tin A, B, C, D bằng các tin từ mã của một bộ lọc giải mã đều nhị

phân, có độ dài n = 3, khi đó độ thừa của bộ mã này là:

log 4

D 1 33,33% 3log2

=− =

Bộ mã này có 4 từ mã được dùng để mã hóa cho 4 tin rời rạc. Các từ mã còn lại (4 từ mã)

không được dùng để mã hóa được gọi là các từ mã cấm.

Đối với các bộ từ mã đều, để đánh giá định lượng sự khác nhau giữa các từ mã trong bộ mã,

ta sử dụng khái niệm khoảng cách mã sau.

4.1.2.2. Khoảng cách mã (d)

Định nghĩa 7: Khảng cách giữa hai từ mã bất kỳ

n

i

α và

n

j

α là số các dấu mã khác nhau

tính theo cùng một vị trí giữa hai từ mã này, ký hiệu ( )

nn

ij

d, α α

Ví dụ 3:

7

i

0110101 α=

7

j

10 01110 α= Chương 4: Cơ sở lý thuyết mã hóa

92

( )

77

ij

d, 6 αα =

Khoảng cách mã d có đầy đủ các tính chất của khoảng cách trong một không gian metric.

Tính chất 1: ( ) ( )

nn nn

ij ji

d, d, α α=αα

Tính chất 2: ( )

nn

ij

1d , 0 ≥αα≥

Tính chất 3: (Tính chất tam giác): ( ) ( ) ( )

nn nn nn

ij jk ik d, d, d, α α+αα≥αα

Để đánh giá định lượng khả năng khống chế sai (bao gồm khả năng phát hiện sai và khả

năng sửa sai) của một bộ mã ta sử dụng khái niệm khoảng cách mã tối tiểu (haykhoảng cách

Hamming) sau:

Định nghĩa 8: Khoảng cách Hamming

0 d của một bộ mã được xác định theo biểu thức

sau:

( ) nn

ij

nn

0ij

,

dmind,

Δ

∀α α

=αα

Ở đây

n

i

α và

n

j

α không đồng nhất bằng không (Ta coi

n

i

α là từ mã không khi mọi dấu

mã trong từ mã đều nhận giá trị không).

4.1.2.3. Trọng số của một từ mã

Định nghĩa 9: Trọng số của một từ mã ( )

n

i

W α là số các dấu mã khác không trong từ

mã.

Ví dụ:

7

i

0110101 α=

( )

7

i

W4 α=

Nếu ta coi mỗi từ mã

n

i

α là một véctơ n chiều trong một không gian tuyến tính n chiều

n V , khi đó phép cộng được thực hiện giữa hai từ mã tương tưh như phép cộng giữa hai véctơ

tương ứng.

Ví dụ 4: ( )

7

i

0110101 0,1,1,0,1,0,1 α= ↔

( )

7

j

1001110 1,0,0,1,1,1,0 α= ↔

( )

777

ki j

1 1 1 1 0 1 1 1, 1, 1, 1, 0, 1, 1 α=α+α= ↔ Chương 4: Cơ sở lý thuyết mã hóa

93

Ở đây phép cộng trên mỗi thành phần (tọa độ) của véctơ được thực hiện trên trường nhị

phận GF(2). Phép cộng theo modulo 2 này được mô tả như sau:

+ 0 1

0 0 1

1 1 0

Sau đây là các tính chất của trọng số:

- ( )

n

i

0W 1 ≤α≤

- ( ) ( )

nn n n

ij i j

d, W αα = α+α

4.1.3. Khả năng khống chế sai của một bộ mã đều nhị phân

4.1.3.1. Khả năng phát hiện sai

Định lý 1: Một bộ mã đều nhị phân có độ thừa (D > 0) và có

0 d2 ≥ sẽ có khả năng phát

hiện được t sai thỏa mãn điều kiện:

0 td 1 ≤− (4.2)

Chứng minh:

Mọi từ mã trong bộ mã đều cách nhau một khoảng cách ít nhất là

0 d . Khi truyền tin, do có

nhiễu từ mã nhận được có thể bị sai ở t vị trí

0 td 1 ≤ − . Vì vậy từ mã nhận được không thể biến

thành một từ mã được dùng khác. Như vậy ta luôn có thể phát hiện được rằng từ mã đã nhận sai.

4.1.3.2. Khả năng sửa sai

Định lý 2: Một bộ mã đều nhị phân có độ thừa ( ) D0 ≥ và có ( ) 0 d3 ≥ sẽ có khả năng

sửa được e sai thỏa mãn điều kiện:

0 d1

e

2

− ⎡⎤

≤ ⎢⎥

⎣⎦

(4.3)

Ở đây [] x là ký hiệu phần nguyên của số x .

Chứng minh:

Khi truyền tin, do có nhiễu, từ mã nhận được có thể bị sai ở e vị trí

0 d1

e

2

⎛−⎞ ⎡⎤

≤ ⎜⎟ ⎢⎥

⎣⎦ ⎝⎠

. Như

vậy, Khoảng cách giữa từ mã nhận được với từ mã khác tối tiểu là e1 + . Như vậy, ta luôn có thể

xác định đúng được từ mã đã phát. Điều đó có nghĩa là ta đã sửa sai được e sai gặp phải trên được

truyền. Chương 4: Cơ sở lý thuyết mã hóa

94

4.1.4. Mã đều nhị phân không có độ thừa

Mã đều nhị phân không có độ thừa (D = 0) còn được gọi là mã đơn giản. Với mã đơn giản

ta có

n

s=N=2 . Như vậy mỗi một từ mã có thể có đều được sử dụng để mã hóa cho các tin

rời rạc. Với từ mã đơn giản

0 d1 = . Vì vậy ta không thể phát hiện hay sửa được bất cứ một sai

nào.

Giả sử ta truyền từ mã đơn giản qua kênh đối xứng nhị phân không nhớ có xác suất thu sai

một dấu là

0 p . Khi đó xác suất thu đúng một dấu tương ứng là ( ) 0 1p − . Từ mã chỉ nhận đúng

khi mọi dấu mã đều nhận đúng. Như vậy, xác suất thu đúng từ mã p® là:

()

n

0 p1p =− ® (4.4)

Xác suất thu sai của từ mã là:

()

n

s0 p1p11p =− =− − ® (4.5.a)

Với

0 p1 ta có công thức gần đúng sau:

()

n

00 1p 1np −≈−

Ta có:

s0 pnp ≈ (4.5.b)

Giả sử xác suất thu sai cho phép đối với mỗi tin rời rạc là

scp p , khi đó điều kiện sử

dụng mã đơn giản trong kênh đối xứng nhị phân không nhớ là:

sscp pp ≤

Hay

scp

0

p

p

n

(4.6)

4.2. MÃ THỐNG KÊ TỐI ƯU

Ta xét phép mã hóa sau đối với các tin của nguồn rời rạc A:

i

n

i i

:a →α f

Mỗi tin

i

a được mã hóa bằng một tổ hợp mã (từ mã)

i

n

i

α (

i

n

i

α là một tổ hợp mã gồm

i

n

dấu mã).

Ta xét trường hợp mã nhị phân tức là mỗi dấu mã chỉ nhận một trong hai giá trị "0" và "1". Chương 4: Cơ sở lý thuyết mã hóa

95

4.2.1. Độ dài trung bình của từ mã và mã hóa tối ưu

Ta có

() ()

i

n

i i

i1,s

i i

a

AVi1,s

pa pa =

⎛⎞ ⎛⎞ α

=⎯⎯⎯ →= = ⎜⎟ ⎜⎟ ⎜⎟

⎝⎠ ⎝⎠

Định nghĩa 1: Độ dài trung bình của một tổ hợp mã được xác định theo biểu thức sau:

[] ()

s

iii

i1

nMn npa

Δ

=

== ∑

Định nghĩa 2: Một phép mã hóa được gọi là tiết kiệm (hay tối ưu) nếu nó làm cực tiểu giá

trị n .

4.2.2. Yêu cầu của một phép mã hóa tối ưu

- nmin → .

- Có khả năng giải mã tức thì: không một dãy bít nào trong biểu diễn của một tin (ký tự) nào

đó lại là phần đầu (prefix) của một dãy bít dài hơn biểu diễn cho một tin (ký tự) khác.

Ví dụ 1: Mã Moorse không đảm bảo yêu cầu này vì:

Mã số cho E (.) là tiền tố của mã số cho A ( ) .

−

Mã số cho D () ..

− là tiền tố của mã số cho B ( ) ...

−

4.2.3. Định lý mã hóa thứ nhất của Shannon (đối với mã nhị phân)

4.2.3.1. Định lý

Luôn luôn có thể xây dựng được một phép mã hóa các tin rời rạc có hiệu quả mà n có thể

nhỏ tùy ý nhưng không nhỏ hơn entropic H(A) được xác định bởi đặc tính thống kê của nguồn A.

( ) nHA ≥

Chứng minh:

Nếu gọi m là cơ số của bộ mã thì lượng thông tin riêng cực đại chứa trong mỗi dấu mã là

log m.

Gọi

i

n là độ dài của từ mã

i

n

i

α ứng với tin

i

a , khi đó lượng thông tin riêng cực đại chứa

trong từ mã này là

i

n logm.

Lượng thông tin riêng trung bình của mỗi từ mã là:

()

s

ii

i1

p a n logm n logm

=

= ∑ Chương 4: Cơ sở lý thuyết mã hóa

96

Để phép mã hóa không làm tổn hao thông tin thì lượng thông tin riêng trung bình cực đại

chứa trong mỗi từ mã phải không nhỏ hơn lượng thông tin riêng trung bình chứa trong mỗi tin

thuộc nguồn. Tức là:

( ) nlog m H A ≥

hay

( ) HA n

log m

≥ .

Với mã nhị phân (m = 2) ta có: ( ) nHA ≥

4.2.3.2. Nguyên tắc lập mã tiết kiệm

Theo định lý ta có: () () ()

ss

ii i i

i1 i1

pa n pa logpa

==

≥− ∑∑

Bất đẳng thức trên sẽ thỏa mãn nếu i ∀ ta có:

( ) ( ) ( ) ii i i

pa n pa logpa ≥−

hay ( ) ii

nlogpa ≥−

Nguyên tắc: Các từ mã có độ dài càng nhỏ sẽ được dùng để mã hóa cho các tin có xác suất

xuất hiện càng lớn và ngược lại.

4.2.4. Thuật toán Huffman

4.2.4.1. Thuật toán mã hóa

Với phép mã hóa tối ưu ta có: ( ) nHA =

VÀO: Nguồn rời rạc

()

i

i

a

A,i1,s

pa

⎛⎞

== ⎜⎟

⎝⎠

RA: Từ mã

i

n

i

α tương ứng với tin

i

a

Bước 1: Khởi động một danh sách các cây nhị phân một nút chứa các trọng lượng

12 n p,p , ,p ... cho các tin

12 n a, , ,a ... .

Bước 2: Thực hiện các bước sau n1 − lần:

Tìm hai cây T' và T" trong danh sách với các nút gốc có trọng lượng tối thiểu p' và p".

Thay thế hai cây này bằng cây nhị phân với nút gốc có trọng lượng p' + p" và có các cây

con là T' và T".

Đánh dấu các mũi tên chỉ đến các cây con 0 và 1.

p' + p"

T'

1

T"

0 Chương 4: Cơ sở lý thuyết mã hóa

97

Bước 3: Mã số của tin

i

a là dãy các bít được đánh dấu trên đường từ gốc của cây nhị phân

cuối cùng tới nút

i

a .

Ví dụ 1: Xét các ký tự A, B, C, D, E có các xác suất xuất hiện tương ứng là 0,2; 0,1; 0,1;

0,15; 0,45

Bước 1:

Bước 2: Lần 1:

Lần 2:

Lần 3:

0,2

1 0

0,1

B

0,1

C

0,15

D

0,2

A

0,45

E

0,1

B

0,1

C

0,2

1 0

0,15

D

0,2

A

0,45

E

0,35

1

0

0,1

B

0,1

C

0,15

D

0,2

A

0,45

E

0,1

B

0,1

C

0,2

1 0

0,15

D

0,2

A

0,45

E

0,35

1

0

0,55 0

1 Chương 4: Cơ sở lý thuyết mã hóa

98

Lần 4:

Bước 3:

Ký tự A B C D E

Mã tương ứng 01 0000 0001 001 1

i

n

2 4 4 3 1

Đánh giá hiệu quả:

()

s

ii

i1

n n p a 2.0,2 4.0,1 4.0,1 3.0,15 1.0,45

2,1 =

==++++

=

∑

dÊu

() ()

()

s

i

i i1

1 100 100

H A p a log 2.0,1log10 0,15log 0,2log5 0,45log

pa 15 45

0,2.3,3226 0,15.2,7375 0,2.2,3224 0,45.1,1522

0,6645 0,4106 0,4645 0,5185

2,058 bit

=

==+++

=+ ++

=+++

=

∑

Ta thấy ( ) nHA ≥

Nhận xét: Phép mã hóa trên là gần tối ưu.

4.2.4.2. Thuật toán giải mã

VÀO: Xâu bít

RA: Xâu tin (ký tự)

Bước 1: Khởi động con trỏ P chỉ đến gốc của cây Huffman.

Bước 2: While (chưa đạt tới kết thúc thông báo) do:

a. Đặt x là bít tiếp theo trong xâu bít.

0,1

B

0,1

C

0,2

1 0

0,15

D

0,2

A

0,45

E

0,35

1

0

0,55 0

1

1

0

1 Chương 4: Cơ sở lý thuyết mã hóa

99

b. If x = 0 then

Đặt P: = con trỏ chỉ đến cây con trái của nó

else

P: = con trỏ chỉ đến cây con phải của nó

c. If (P chỉ đến nút lá) then

1. Hiển thị ký tự tương ứng với nút lá.

2. Đặt lại P để nó lại chỉ đến gốc của cây Huffman

Ví dụ 2: Thông báo nhận được: 0 1 0 0 0 1 1 0 0 1 1 0 1 ...

Quá trình giải mã:

GGGGGG

G0 1 000 1 1 00 1 1 0 1

P

ACEDEA

↑↓↑ ↓↑↓↑ ↓↑↓↑↓↑

...

RA: A C E D E A ...

4.3. CÁC CẤU TRÚC ĐẠI SỐ VÀ MÃ TUYẾN TÍNH

4.3.1. Một số cấu trúc đại số cơ bản

4.3.1.1. Nhóm:

* G,

Nhóm G là một tập hợp các phần tử với một phép toán trong 2 ngôi thỏa mãn các tính chất

sau:

- a,b G a b c G ∈⇒∗=∈

- Tồn tại phần tử đơn vị e: a e = e a = a ∗∗

- Tồn tại phần tử ngược

1

a

−

:

11

a a = a a = e

−−

∗∗

Nếu ab = b a ∗∗ thì nhóm được gọi là nhóm giao hoán.

Ví dụ 1: Tập các số nguyên Z với phép toán cộng (+) tạo nên một nhóm giao hoán với phần

tử đơn vị là 0.

Nếu số các phần tử trong nhóm G là hữu hạn thì ta có nhóm hữu hạn cấp G .

Nếu HG ∈ và H,∗ tạo nên một nhóm thì H được gọi là nhóm con của G. Cấp của H là

ước của cấp của G.

4.3.1.2. Nhóm xyclic

Xét nhóm hữu hạn G, i . Nếu G có thể mô tả như sau" Chương 4: Cơ sở lý thuyết mã hóa

100

{ } i

G,i = α∀

thì G được gọi là nhóm xyclic sinh bởi α. α được gọi là phần tử sinh (hay phần tử nguyên

thủy) của nhóm.

Ví dụ 2: Xét nhóm nhân: { } 11 Z 1,2,3,4,5,6,7,8,9,10 ∗

=

Ta có:

05

21 210 ==

16

27

38

49

22 29

24 27

28 23

25 26

==

==

==

==

Ta có thể viết { } i

11 Z2mod11 ∗

= .

Phần tử α được gọi là có cấp k nếu n là số nguyên dương nhỏ nhất thỏa mãn

k

1modn α≡ .

Ở ví dụ trên ta có ( ) ( ) ( ) ( ) ord 2 ord 8 ord 7 ord 9 10 ====

4.3.1.3. Vành: R, , + i

Vành R là một tập hợp các phần tử với hai phép toán trong hai ngôi (Phép cộng (+), phép

nhân ( i )) thỏa mãn các tính chất sau:

- R,+ là một nhóm đối với phép cộng

- R, i là một nửa nhóm đối với phép nhân. Điều này có nghĩa là không nhất thiết mọi

phần tử đều có phần tử ngược của phép nhân.

- Tính chất phân phối: ( ) abc = acbc ++

Vành R được gọi là vành giao hoán nếu ta có ab = ba

4.3.1.4. Ideal:

Ideal I là một tập con trong R có các tính chất sau:

- a,b I : a b I ∈+∈ , I,+ là một nhóm đối với phép *.

- cR:c.a I ∈∈ Chương 4: Cơ sở lý thuyết mã hóa

101

4.3.1.5. Trường F, , + i

Trường F là một tập hợp các phần tử với hai phép toán trong hai ngôi thỏa mãn:

- F,+ là một nhóm cộng

-

*

F, i là một nhóm đối với phép nhân.

Trong đó: { } *

FF\0 =

Ví dụ 3: Trường nhị phân GF(2): Trường này chỉ có hai phần tử 0 và 1.

4.3.1.6. Không gian tuyến tính

n V

Các phần tử trong không gian tuyến tính được gọi là các véctơ.

n V ∈ v là các véctơ n chiều. Mỗi véctơ n chiều được mô tả bằng một bộ n tọa độ được sắp

( ) 01 n1 , , ...,

− ↔ vvv v với

i

F ∈ v

Trong không gian

n V ta xác định các phép toán sau:

- Cộng véctơ: () 0n1 ,...,

− = uu u , ( ) 0n1 , ...,

− = vv v

( ) 0n1 , ...,

− = u+v y y với

jjj

F ∈ y=u+v

- Tích vô hướng của hai véctơ: ( ) u,v

()

n1

ii

i0

F

−

=

=∈ ∑ u,v u v

Hai véctơ được gọi là trực giao nếu ( ) 0 = u,v

- Nhân một véctơ với một phần tử vô hướng

Xét phần tử vô hướng F α∈

( ) 1n1 . , ...,

− αα α u= u u

4.3.2. Các dạng tuyến tính và mã tuyến tính

4.3.2.1. Dạng tuyến tính

Định nghĩa 1: Các dạng tuyến tính của k biến độc lập

12 k , , ..., x xx là các biểu thức có

dạng:

()

k

1k ii

i1

,...,

=

= ∑ f xx ax (4.7) Chương 4: Cơ sở lý thuyết mã hóa

102

Trong đó:

i

F ∈ a

Nhận xét: Có sự tương ứng 1 - 1 giữa các dạng tuyến tính, các véctơ và các đa thức trong

vành đa thức.

4.3.2.2. Mã tuyến tính

Định nghĩa 2: Mã tuyến tính độ dài n là mã mà từ mã của nó có các dấu mã là các dạng

tuyến tính

Định nghĩa 3: Mã hệ thống tuyến tính (n,k) là mã tuyến tính độ dài n trong đó ta có thể chỉ

ra được vị trí của k dấu thông tin trong từ mã.

Định nghĩa 4: Mã tuyến tính ngẫu nhiên là mã tuyến tính có các dấu mã được chọn ngẫu

nhiên từ các dạng tuyến tính có thể có.

Nhận xét:

- Shannon đã chứng minh rằng tồn tại các mã đạt được giới hạn Shannon (thỏa mãn định lý

mã hóa thứ hai) trong các mã tuyến tính ngẫu nhiên.

- Khó tìm các mã tốt trên các mã tuyến tính ngẫu nhiên. Hơn nữa việc mã hóa và giải mã

cho các mã này cũng rất phức tạp. Bởi vậy các mã này chỉ có ý nghĩa về mặt lý thuyết.

Ví dụ 4: Số các dạng tuyến tính khác nhau của 4 biến độc lập là:

4

0 N2115 =−=

Số các mã hệ thống tuyến tính ( ) 7,4 là

3

111 NC 165 ==

4.3.2.3. Ma trận sinh và ma trận kiểm tra của mã tuyến tính

Để đơn giản cho việc mô tả mã tuyến tính người ta thường sử dụng ma trận sinh

k.n G . Ma

trận này chứa k véctơ hàng độc lập tuyến tính tạo nên không gian mã

() n,k V−

k

2 các vétơ khác nhau là tất cả các tổ hợp tuyến tính có thể có của k véctơ hàng này.

Trong đại số tuyến tính ta biết rằng với mỗi G sẽ tồn tại ma trận

rn H × thỏa mãn:

T G.H 0 = (4.8)

Trong đó: rnk =−

T H được gọi là ma trận chuyển vị của H

H được gọi là ma trận kiểm tra của mã tuyến tính (n, k)

Ta thấy rằng H chứa r véctơ hàng trực giao với các véctơ hàng của G

Hiển nhiên là nếu a là một véctơ mã

() ( ) n,r

aV− ∈ thì : Chương 4: Cơ sở lý thuyết mã hóa

103

T a.H 0 = (4.9)

Ở đây H cũng là một ma trận sinh của một mã tuyến tính

() n,r

V− và G lại chính là ma trận

kiểm tra của mã này. Ta thấy rằng không gian tuyến tính C sinh bởi G là không gian không của

không gian tuyến tính C⊥ sinh bởi H.

Từ (4.9) ta có thể viết ra r phương trình:

n

jij

j1

ah 0 , i 1,r

=

= = ∑ (4.10)

Các phương trình này còn được gọi là các tổng kiểm tra. Mã C sinh bởi mã G và C⊥ sinh

bởi H được gọi là các mã đối ngẫu.

Nếu CC⊥ ≡ thì C được gọi là mã tự đối ngẫu. Các mã tự đối ngẫu có rnk =− và bởi

vậy có tốc độ

k1

R

n2

== .

Ví dụ 5: Xét mã hệ thống tuyến tính (7, 4) có các dấu mã được chọn từ các dạng tuyến tính

như sau:

Từ mã a gồm các dấu mã

i

a được chọn như sau:

00

11

22

33

a

a

a

a

=

=

=

=

x

x

x

x

4012

5123

a

a

=++

=++

x xx

x xx

6 013 a =++ x xx

Như vậy ma trận sinh G có dạng:

1000001

0100111

G

0010110

0001011

⎛⎞

⎜⎟

⎜⎟ =

⎜⎟

⎜⎟

⎝⎠

Ma trận kiểm tra của mã (7, 4) này là: Chương 4: Cơ sở lý thuyết mã hóa

104

1110100

H0111010

1101001

⎛⎞

⎜⎟

= ⎜⎟

⎜⎟

⎝⎠

H chính là ma trận sinh của mã (7, 3) là mã đối ngẫu với mã (7, 4) sinh bởi G

4.3.3. Các bài toán tối ưu của mã tuyến tính nhị phân

Khi xây dựng một mã tuyến tính ( ) 0 n,k,d người ta mong muốn tìm được các mã có độ

thừa nhỏ nhưng lại có khả năng khống chế sai lớn. Để đơn giản người ta thường xây dựng mã dựa

trên các bài toán tối ưu sau:

4.3.3.1. Bài toán 1

Với k và

0 d xác định, ta phải tìm được mã có độ dài với từ mã là nhỏ nhất.

Tương ứng với bài toán này ta có giới hạn Griesmer sau:

k1

0

i

i0

d

n

2

−

=

⎡⎤

≥ ⎢⎥

⎢⎥

∑ (4.11)

Ở đây ⎡⎤ ⎢⎥ x chỉ số nguyên nhỏ nhất lớn hơn hoặc bằng x.

Ví dụ 6: Cho

0 k4,d 3 ==

n32117 ≥+++=

Vậy mã phải có độ dài tối tiểu là 7. Hay nói một cách khác mã (7, 4, 3) là một mã tối ưu đạt

được giới hạn Griesmer.

4.3.3.2. Bài toán 2

Với n và k xác định, ta phải tìm được mã có khoảng cách tiểu

0 d là lớn nhất.

Tương ứng với bài toán này ta có giới hạn Plotkin sau:

k1

0 k

n.2

d

21

−

≤

−

(4.12)

Ví dụ 7: Cho k = 3, n = 7

2

0 3

7.2

d4

21

≤=

−

Vậy khoảng cách

0 d lớn nhất là 4. Nói một cách khác mã (7, 3, 4) là một mã tối ưu đạt

được giới hạn Plotkin. Chương 4: Cơ sở lý thuyết mã hóa

105

4.3.3.3. Bài toán 3

Với n và số sai khả sửa t xác định, ta phải tìm được mã có số dấu thông tin k là lớn nhất

(hay số dấu thừa rnk =− là nhỏ nhất)

Tương ứng với bài toán này ta có giới hạn Hamming sau:

t

nk i

n

i0

2C −

=

≥ ∑ (4.13)

Ví dụ 8: Cho n = 7 và t = 1

1

ri01

777

i0

2CCC8

=

≥=+= ∑

2 rlog83 ≥=

hay k734 ≤−=

Như vậy mã (7, 4, 3) là mã tối ưu đạt được giới hạn Hamming

Mã đạt được giới hạn Hamming còn được gọi là mã hoàn thiện.

4.4. VÀNH ĐA THỨC VÀ MÃ XYCLIC

4.4.1. Vành đa thức

Ta xét tập hợp các đa thức có bậc không lớn hơn n1 − sau:

()

n1

i

i

i0

−

=

= ∑ f xfx (4.14)

( ) deg n 1 ≤ − fx

i

f là các hệ số được lấy giá trị trong một trường F nào đó.

Trên tập các đa thức này ta xác định 2 phép toán trong là phép cộng đa thức và phép nhân

đa thức như sau:

4.4.1.1. Phép cộng đa thức

Xét hai đa thức sau: ()

n1

i

i

i0

aX

−

=

= ∑ax , ()

n1

i

i

i0

bX

−

=

= ∑bx

Ta có: ( ) ( ) ( ) aX+bX cX =

()

n1

i

i

i0

cX c

−

=

= ∑ x Chương 4: Cơ sở lý thuyết mã hóa

106

iii

+ c=a b

Ở đây phép cộng các hệ số

i

a và

i

b được thực hiện trên trường F

Nếu ta coi mỗi đa thức có bậc nhỏ hơn hoặc bằng n1 − là một véctơ trong không gian

tuyến tính n chiều

n V thì phép cộng đa thức hoàn toàn tương tự như phép cộng véctơ.

Ví dụ 1: Xét n = 7, F = GF(2)

( ) ( )

() ( )

() () ( )

4

2

24

aX 1 x x a 1100100

b X x x b 0110000

a X bX 1 x x a b 1010100

=++ ↔ =

=+ ↔ =

+=++↔+=

4.4.1.2. Phép nhân đa thức

Để tích của hai đa thức có bậc n1 ≤− vẫn là một đa thức có bậc n1 ≤ − ta phải thực hiện

phép nhân 2 đa thức theo mođulo

n

X1 + (tức là coi

n

X1 = ).

()()

n1 n1

iin

ii

i0 i0

aX.bX . b modX 1

−−

==

⎛⎞⎛⎞

=+ ⎜⎟⎜⎟ ⎜⎟⎜⎟

⎝⎠⎝⎠

∑∑ ax x

Ví dụ 2: ( )

4

aX 1 X X =+ + , ( )

2

b XXX =+

()() ( )( )

()() ()

()()

437

25347 7

2345

aX.bX 1 X X X X modX 1

aX.bX 1 X X X X X modX 1

aX.bX 1 X X X X X

=++ + +

=+ + + + + +

=+++++

Ta thấy rằng tích của hai đa thức được thực hiện trên cơ sở tích của hai đơn thức

i

x và

j

x .

( ) ijmodn ij

.

+

= x xx (4.15)

Chú ý: Phép nhân các hệ số

i

a và

j

b là phép nhân trên trường F

4.4.1.3. Phép dịch vòng

Ta xét một trường hợp đặc biệt của phép nhân là nhân một đa thức ( ) aX và một đơn thức

i

x .

() ()

n1

i

i012n1

i0

aX a , , , ,

−

−

=

=↔= ∑ ... ax a a a a

Xét tích sau: Chương 4: Cơ sở lý thuyết mã hóa

107

() () ()

n1

i

in101n2

i0

bX .aX . b , , , ,

−

− −

=

⎛⎞

== ↔= ⎜⎟ ⎜⎟

⎝⎠

∑ ... xxax aaaa

Ta thấy biểu diễn véctơ b được dịch vòng về phía phải một cấp so với biểu diễn véctơ a.

Tương tự ta có:

() () ()

n1

jji

injnj1nj1

i0

cX .aX . c , , ,

−

− −+ −−

=

⎛⎞

== ↔= ⎜⎟ ⎜⎟

⎝⎠

∑ ... xxax aa a

Xét thương sau:

()

( )

()

i

i

12 n10

aX dd,,,,

− == ↔= ∑ ... ax

x aa a a

xx

Ta thấy biểu diễn của véc tơ d dược dịch vòng về phía trái 1 cấp so với biểu diễn của véctơ

a.

Nhận xét:

( ) ( )

()

n

n-1 aX aX aX ==

x

x

xx

Ví dụ 3:

( ) ( )

() () () ()

()

() ()

()

4

425

4

36

aX 1 x x a 1100100

b X xaX x1xx xx x b 0110010

1xx aX dX 1 x x d 1001001

xx

=++↔=

==++=++↔=

++

== =++↔=

.

4.4.1.4. Định nghĩa vành đa thức

Định nghĩa 1: Tập các đa thức xác định theo (3.11) với hai phép toán cộng đa thức và nhân

đa thức theo modulo

n

X1 + tạo nên vành đa thức. Trong trường hợp các hệ số của các đa thức

nằm trong ( ) GF 2 ta ký hiệu vành này là [ ]

n

2 ZxX 1 + .

4.4.2. Ideal của vành đa thức

Định nghĩa 2: Ideal I của vành đa thức gồm tập các đa thức ( ) aX là bội của một đa thức

( ) gX thỏa mãn:

- ( )

n

gXX 1 + ( ( ) gX là ước của

n

X1 + ) Chương 4: Cơ sở lý thuyết mã hóa

108

- ( ) ( ) deg g X r mindeg a X == với ( ) ( ) aX I,aX 0 ∀ ∈≠

Ta ký hiệu Ideal trong vành đa thức là ( ) IgX =

Hiển nhiên là với ()

r

i

i

i0

gX

=

= ∑gx ta có

0r

1 == gg , { } i

0,1 ∈ g với i1,r1 = −

Để có thể tìm được tất cả các Ideal trong vành ta phải thực hiện phân tích nhị thức

n

X1 +

thành tích của các đa thức bất khả quy.

Định nghĩa 3: Đa thức ( ) aX được gọi là bất khả quy nếu nó chỉ chia hết cho 1 và cho

chính nó.

Như vậy đa thức bất khả quy là đa thức không thể phân tích thành tích các đa thức có bậc

nhỏ hơn.

Định lý 4: Với

m n2 1 = − , đa thức

n

X1 + được phân tích thành tích của tất cả các đa

thức bất khả quy có bậc m và ước của m.

Ví dụ 4:

- m = 2, n = 3: chỉ có duy nhất một đa thức bất khả quy bậc 2 là

2

xx1 + + và một đa thức

bất khả quy bậc 1 là ( ) 1x + . Như vậy:

()( )

32

X 1 1x1x x += + + +

- m = 3, n = 7: Trong số 8 đa thức bậc 3 chỉ có 2 đa thức sau là các đa thức bất khả quy, đó

là

3

xx1 ++ và

32

xx1 ++ . Như vậy:

()( )( )

7323

X 1 1x1x x 1x x += + + + + +

- m = 4, n = 15: Trong số 16 đa thức bậc 4 chỉ có 3 đa thức sau là các đa thức bất khả quy:

4

xx1 ++ ,

43

xx1 ++ và

432

xxxx1 ++++ . Như vậy:

()( )( )( )( )

15 2 4 34 234

X 1 1x1xx 1x x 1x x 1xx x x +=+++++++++++

Gọi số các đa thức bất khả quy trong phân tích của

n

X1 + là I, khi đó số các Ideal trong

vành được xác định theo biểu thức sau:

I

I21 = −

Định nghĩa 5: Đa thức ( ) g* X được gọi là đa thức đối ngẫu của đa thức ( ) gX nếu:

()

( )

( )

deg g X 1

g* X X .g X−

= Chương 4: Cơ sở lý thuyết mã hóa

109

Ví dụ 5: Cho () ( )

3

gX 1 X X =++ .

Khi đó đa thức đối ngẫu ( ) g* X của nó là:

()

332

3

11

g* X X . 1 X X 1

X X

⎛⎞

=++=++ ⎜⎟

⎝⎠

Nếu () () g* X g X = thì () gX được gọi là đa thức tự đối ngẫu.

Nhận xét:

- Nếu () aX là bất khả quy thì nó phải chứa một số lẻ các đơn thức.

- Nếu () aX là bất khả quy thì ( ) a* X cũng là một đa thức bất khả quy.

4.4.3. Định nghĩa mã xyclic

Định nghĩa 6: Mã xyclic (n, k) là Ideal ( ) IgX = của vành đa thức []

n

2 ZxX 1 + .

Vì Ideal ( ) gX chứa tất cả các bội của ( ) gX nên nếu ( ) ( ) aX gX ∈ thì

()() aX gX # và hiển nhiên là ( ) ( ) ( ) ( ) x.aX gX x.aX gX ⇒∈ # .

Ta có thể đưa ra một định nghĩa trực quan hơn cho mã xyclic.

Định nghĩa 7: Mã xyclic là một bộ mã tuyến tính có tính chất sau: Nếu () aX là một từ

mã thì dịch vòng của () aX cũng là một từ mã thuộc bộ mã này.

Chú ý: () gX được gọi là đa thức sinh của mã xyclic

Ví dụ 7: Tập tất cả các mã xyclic trên vành [ ]

7

2 ZxX 1 + . Vành này có tất cả 7 ideal

tương ứng với 7 bộ mã xyclic.

o

N

( ) gX

Mã (n, k) 0 d

1 1 (7, 7) 1

2 1 + X (7, 6) 2

3

3

1XX + +

(7, 4) 3

3 23

1X X ++

(7, 4) 3

4 24

1XX X ++ +

(7, 3) 4

4

234

1X X X +++

(7, 3) 4 Chương 4: Cơ sở lý thuyết mã hóa

110

7

6

i

i0 =

∑x (7, 1) 7

4.4.4. Ma trận sinh của mã xyclic

Vì mã xyclic (n, k) là một mã tuyến tính nên ta có thể mô tả nó thông qua ma trận sinh G

nên chứa k véctơ hàng độc lập tuyến tính. Ta có thể thiết lập G như sau:

( )

()

()

k1

gX

x.g X

G

x.gX −

⎛⎞

⎜⎟

⎜⎟

= ⎜⎟

⎜⎟

⎜⎟

⎝⎠

" (4.1.6)

Ví dụ 8: Mã xyclic (7, 4) có đa thức sinh ( )

3

gX 1 X X =+ + . Ma trận sinh của mã này

có thể mô tả như sau:

3

24

235

346

1XX 1101000

X X X 0110100

G

0011010 XXX

0001101

XXX

⎛⎞ ++ ⎛⎞

⎜⎟

⎜⎟

⎜⎟ ++ ⎜⎟ == ⎜⎟

⎜⎟ ++ ⎜⎟

⎜⎟

⎜⎟

⎝⎠ ++ ⎝⎠

4.4.5. Ma trận kiểm tra của mã xyclic

Vì ( )

n

gXX 1 + nên ta có thể viết ( ) ( )

n

x1gX.hX +=

Hay ()

()

n

x1

hX

gX

+

=

( ) hX được gọi là đa thức kiểm tra.

Vì ( ) ( )

n

gX.hX 0modX 1 ≡+ nên các đa thức ( ) hX và ( ) gX được gọi là các đa

thức trực giao.

Ta có: ()

k

j

j

j0

hX

=

= ∑hx với

0k 1 = = hh , { } j

0,1 ∈ h với j2,k1 = −

Do sự khác biệt giữa tích vô hướng của 2 véctơ và tích của hai đa thức tương ứng nên ta có

thể xây dựng ma trận kiểm tra của mã xyclic sinh bởi ( ) gX như sau: Chương 4: Cơ sở lý thuyết mã hóa

111

()

()

()

*

*

r1 *

hX

x.h X H

x.hX −

⎛⎞

⎜⎟

⎜⎟

= ⎜⎟

⎜⎟

⎜⎟

⎝⎠

#

(4.17)

Ví dụ 9: Xây dựng ma trận kiểm tra cho mã xyclic (7, 4) có ( )

3

gX 1 X X =+ +

Ta có: () ()()

7

23 42

3

X1

hX 1x1XX XXX1

XX1

+

==+++=+++

++

( )

* 234

hX 1X X X =+ + +

Ma trận kiểm tra:

234

345

2456

1X X X 10 11100

HXXXX 0101110

0010111 XXXX

⎛⎞ +++ ⎛⎞

⎜⎟

⎜⎟

⎜⎟ =+++ = ⎜⎟

⎜⎟ ⎜⎟

⎜⎟ +++ ⎝⎠

⎝⎠

Ta dễ dàng kiểm tra:

T G.H 0 =

Với ( ) aX là một từ mã ta có: ( )

T aX .H 0 = ⎡⎤ ⎣⎦

4.5. MÃ HÓA CHO CÁC MÃ XYCLIC

4.5.1. Mô tả từ mã của mã xyclic hệ thống

Định nghĩa: Mã xyclic (n, k) được gọi là một mã xyclic hệ thống nếu ta có thể chỉ rõ vị trí

của các dấu thông tin và các dấu kiểm tra trong từ mã.

Thông thường các dấu thông tin được sắp xếp ở k vị trí bậc cao (từ bậc r tới bậc n1 − ) Các

vị trí bậc thấp còn lại là các dấu kiểm tra (từ bậc 0 tới bậc r1 − )

0 f

1 f ...

r1 − f

r

f

r1 + f ...

n1 − f

r dấu kiểm tra

k dấu thông tin

() () ()

n1

ink

i

i0

Xx.aXrX

−

−

=

== + ∑ ffx

Ta có: ( ) ( ) ( ) ( ) ( ) XgX X qX.gX ⇒= # ff (1.18) Chương 4: Cơ sở lý thuyết mã hóa

112

( )

()

( )

()

( )

()

nk

Xx.aXrX

gX gX gX

−

⇒= +

f

( )

()

()

( )

()

( )

()

Xr'XrX qX

gX gX gX

=+ +

f

(1.19)

Từ (1.1) và (1.2) ta thấy: ( ) ( ) r' X r X 0 +=

4.5.2. Thuật toán mã hóa hệ thống

Từ (1.19) ta có thể mô tả thuật toán xây dựng từ mã xyclic theo các bước sau:

VÀO: Tin rời rạc

i

aA ∈

RA: Từ mã ( ) i

x f tương ứng với

i

a .

Bước 1: Mô tả tin

i

a trong tập tin cần mã hóa (gồm

k

2 tin) bằng một đa thức ( ) i

aX với

( ) i

deg a X k 1 ≤− .

Bước 2: Nâng bậc ( ) i

aX bằng cách nhân nó với

nk

x −

.

Bước 3: Chia ( )

nk

i

aX.x −

cho đa thức sinh g(X) để tìm phần dư ( ) i

rX .

Bước 4: Xây dựng từ mã xyclic: ( ) ( ) ( )

nk

ii i

xaX.x rX −

=+ f (1.20)

4.5.3. Thiết bị mã hóa

Phần trung tâm của thiết bị mã hóa là một thiết bị chia cho g(X) để tính dư. Thực chất đây

là một otomat nhớ dạng của g(X).

Giả sử: ()

r1

i

i

i0

gX

−

=

= ∑gx (1.21)

Khi đó thiết bị mã hóa cho mã (n, k) với đa thức sinh dạng (1.21) được mô tả như sau (Hình

4. 1):

i

0

g

1

⎧

= ⎨

⎩

Hë m¹ch

Ng¾n m¹ch

1n ÷

1 V

( )

nk

i

aX.x −

VÀO

r1 g −

3 g

2 g

1 2

1 g

+ +

3

+ +

r +

k1n + ÷

2 V

RA

H

1k ÷

Hình 4.1: Thiết bị mã hóa cho mã xyclic (n, k) có đa thức sinh g(X) Chương 4: Cơ sở lý thuyết mã hóa

113

Hoạt động của thiết bị mã hóa:

- k nhịp đầu: chia và tính phần dư: Mạch và

1 V mở,

2 V đóng, thiết bị hoạt động như một

bộ chia để tính dư. Kết thúc nhịp thứ k toàn bộ phần dư nằm trong r ô nhớ từ 1 đến r. Trong quá

trình này, các dấu thông tin () ( )

nk

i

aX.x −

được đưa ra qua mạch hoặc H.

- r nhịp sau: đưa ra các dấu kiểm tra (phần dư) tới đầu ra. Mạch VÀ

1 V đóng, thiết bị hoạt

động như một thanh ghi dịch nối tiếp. Mạch VÀ

2 V mở, các dấu kiểm tra được lần lượt đưa ra từ

bậc cao tới bậc thấp. Kết thúc nhịp thứ n, toàn bộ từ mã được đưa ra đầu ra.

Ví dụ 1: Thiết bị mã hóa cho mã xyclic (7, 4) có ( )

3

gX 1 X X =+ +

Giả sử đa thức thông tin cần mã: ( )

3

aX X X = +

Quá trình hoạt động của thiết bị được mô tả trên bảng sau:

Trạng thái các ô nhớ Xung

nhịp

Vào

1 2 1

Ra

1 1 1 1 0 1

2 0 0 1 1 0

3 1 0 0 1 1

4 0 1 1 0 0

5 0 0 1 1 0

6 0 0 0 1 1

7 0 0 0 0 1

Bảng 1: Quá trình hoạt động của bộ mã hóa.

Kiểm tra lại: () ( )

nk 3 3 6 4

a X .x x x .x x x −

=+ =+

17 ÷

1 V

( )

nk

i

aX.x −

1 2

+

3 +

57 ÷ 2 V

H

14 ÷

← 1 0 1 0 # 0 0 0 Chương 4: Cơ sở lý thuyết mã hóa

114

()

64 3

643 3

3

3

xx xx1

xxx x1

x

xx1

rX x 1

+ ++

−

+ ++

−

++

=+ D−

Từ mã được thiết lập ()

60

X.....X 64

Xxxx1 1010011 =+++ ↔ f

4.5.4. Tạo các dấu kiểm tra của mã xyclic

Giả sử () XV ∈ f - mã xyclic (n, k) có đa thức sinh g(X).

Khi đó ()() XgX # f hay () ( ) ( ) XgX.qX = f (*)

Trong đó: ( ) deg X n 1 ≤− f

( ) deg g X r n k == −

( ) deg q X n 1 r k 1 ≤−−=−

Với ()

n1

i

i

i0

X

−

=

= ∑ f fx

Gọi ()

()

n

x1

hX

gX

+

= ta có ( ) deg h X k =

Nhân hai vế của (*) với h(X) ta có: ( ) ( ) ( ) ( ) ( ) X.hX gX.qX.hx = f

Vì ( ) ( )

n

gX.hx x 1 =+ nên ( ) ( ) ( ) ( )

n

X.hX gX.x qX =+ f (**)

Vì ( ) deg g X k 1 ≤− nên trong (**) không chứa các thành phần bậc cao của x có mũ

k, k 1, , n 1 +− ... .

Do đó các hệ số tương ứng của các thành phần này trong (**) phải bằng 0. Tức là trong

biểu thức:

()()

n1 k

ij

ij

i0 j0

X.hX .

−

==

⎛⎞ ⎛⎞

⎜⎟ = ⎜⎟ ⎜⎟ ⎜⎟

⎝⎠ ⎝⎠

∑∑ f fx hx Chương 4: Cơ sở lý thuyết mã hóa

115

ta phải có các số hạng có dạng:

i+j

ij

0 = fhx với ij + thỏa mãn: ki jn1 ≤+≤ − hay

kjin1j −≤≤ −− .

Khi j chạy từ 0 đến k thì: nr jin1j −−≤≤ −− .

Như vậy ta có: