Một Số Thuật Toán Lượng Tử Trong Lý Thuyết Thông Tin

Khám phá luận văn thạc sĩ về toán ứng dụng và các thuật toán lượng tử, mở ra hướng nghiên cứu mới trong lĩnh vực khoa học máy tính.

• Tác giả: Phạm Thị Hồng
• Người hướng dẫn: TS. Đinh Trung Hòa
• Trường học: Đại học Bách Khoa - ĐHQG TP. Hồ Chí Minh
• Chuyên ngành: Toán ứng dụng
• Đề tài: Một Số Thuật Toán Lượng Tử
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Thuật Toán Lượng Tử Trong Lý Thuyết Thông Tin

Lý thuyết thông tin cổ điển, với nền tảng là mã nhị phân, gặp nhiều thách thức trong bối cảnh bùng nổ thông tin hiện nay. Việc lưu trữ và truyền tải lượng lớn thông tin trở nên khó khăn. Định lý Shannon về chặn dưới nén thông tin và giới hạn kênh truyền đặt ra những giới hạn nhất định. Feymann từ những năm 80 đã đưa ra dự đoán về máy lượng tử để giải quyết các bài toán cơ học lượng tử, từ đó hình thành hướng nghiên cứu mới: lý thuyết thông tin lượng tử. Lý thuyết này ứng dụng nguyên lý cơ lượng tử vào lý thuyết thông tin, giúp các nhà nghiên cứu thu thập thông tin từ việc xử lý, phục vụ cho các nghiên cứu trong lĩnh vực lượng tử. Sự khác biệt then chốt nằm ở chỗ trạng thái hệ lượng tử là tổ hợp tuyến tính của các trạng thái cơ bản (qubit), cho phép tính toán song song, vượt trội so với tính toán nối tiếp trong lý thuyết Shannon. Trên lý thuyết, việc lưu trữ thông tin và giải các bài toán NP-khó trở nên hiệu quả hơn. Tuy nhiên, việc mã hóa thông tin cổ điển thành lượng tử, thiết kế thuật toán và máy tính lượng tử vẫn còn nhiều khó khăn.

1.1. Nguồn Gốc và Sự Phát Triển của Lý Thuyết Thông Tin Lượng Tử

Lý thuyết thông tin lượng tử ra đời như một phản ứng trước những hạn chế của lý thuyết thông tin cổ điển. Ý tưởng về một cỗ máy lượng tử có khả năng giải quyết các bài toán phức tạp trong cơ học lượng tử đã thúc đẩy sự phát triển của lĩnh vực này. Nó không chỉ là sự mở rộng của lý thuyết thông tin Shannon mà còn là một cuộc cách mạng trong cách chúng ta nhìn nhận và xử lý thông tin. Sự kết hợp giữa các nguyên lý của cơ học lượng tử và lý thuyết thông tin đã mở ra những khả năng mới, hứa hẹn giải quyết các vấn đề mà lý thuyết cổ điển không thể xử lý được.

1.2. So Sánh Lý Thuyết Thông Tin Cổ Điển và Lý Thuyết Lượng Tử

Điểm khác biệt cơ bản giữa hai lý thuyết nằm ở cách thức biểu diễn và xử lý thông tin. Trong lý thuyết thông tin cổ điển, thông tin được biểu diễn bằng các bit (0 hoặc 1), trong khi lý thuyết lượng tử sử dụng qubit, có thể tồn tại ở trạng thái tổ hợp tuyến tính của 0 và 1. Điều này cho phép máy tính lượng tử thực hiện các phép tính song song, vượt trội so với máy tính cổ điển. Ngoài ra, các khái niệm như vướng víu lượng tử và teleportation lượng tử không tồn tại trong lý thuyết thông tin cổ điển, mở ra những khả năng truyền thông tin hoàn toàn mới.

II. Thách Thức và Vấn Đề Trong Nghiên Cứu Thuật Toán Lượng Tử

Mặc dù lý thuyết thông tin lượng tử hứa hẹn nhiều tiềm năng, nhưng việc hiện thực hóa chúng gặp nhiều khó khăn. Việc mã hóa thông tin cổ điển sang thông tin lượng tử hiệu quả là một thách thức lớn. Thiết kế các thuật toán lượng tử tối ưu, đặc biệt là cho các bài toán thực tế, đòi hỏi sự hiểu biết sâu sắc về cả lý thuyết lượng tử và khoa học máy tính. Quan trọng nhất, việc xây dựng máy tính lượng tử ổn định và có khả năng mở rộng vẫn là một rào cản công nghệ lớn. Các vấn đề liên quan đến sửa lỗi lượng tử và kiểm soát decoherence (mất tính chất lượng tử) cần được giải quyết trước khi có thể xây dựng các quantum computer thực tế. Theo luận văn, việc thiết kế máy tính lượng tử là điều chưa thể thực hiện được trong thời gian hiện nay, và mọi thứ vẫn đang ở giai đoạn phát triển lý thuyết.

2.1. Rào Cản Công Nghệ Trong Xây Dựng Máy Tính Lượng Tử

Một trong những thách thức lớn nhất là duy trì trạng thái qubit ổn định trong một thời gian đủ dài để thực hiện các phép tính. Hiện tượng decoherence, do tương tác với môi trường bên ngoài, có thể làm mất thông tin lượng tử. Việc kiểm soát và giảm thiểu decoherence đòi hỏi công nghệ chế tạo cực kỳ tinh vi. Ngoài ra, việc mở rộng số lượng qubit trong một máy tính lượng tử mà vẫn duy trì được độ chính xác cao cũng là một thách thức kỹ thuật đáng kể. Các nhà khoa học vẫn đang nỗ lực tìm kiếm các vật liệu và phương pháp chế tạo phù hợp để vượt qua những rào cản này.

2.2. Bài Toán Sửa Lỗi Lượng Tử và Tính Ổn Định của Qubit

Qubit rất nhạy cảm với các tác động từ môi trường bên ngoài, dẫn đến sai sót trong quá trình tính toán. Do đó, sửa lỗi lượng tử là một yêu cầu thiết yếu để xây dựng máy tính lượng tử đáng tin cậy. Tuy nhiên, việc sửa lỗi lượng tử phức tạp hơn nhiều so với sửa lỗi trong máy tính cổ điển, vì không thể sao chép qubit một cách tùy ý (định lý no-cloning). Các nhà nghiên cứu đang phát triển các phương pháp sửa lỗi lượng tử dựa trên các mã lượng tử, nhưng việc triển khai chúng trên thực tế vẫn còn nhiều khó khăn.

III. Phương Pháp Giải Quyết Với Thuật Toán Shor Lượng Tử

Thuật toán Shor là một trong những thành tựu đột phá của lý thuyết thông tin lượng tử. Nó cung cấp một phương pháp hiệu quả để phân tích một số thành các thừa số nguyên tố, một bài toán cực kỳ khó đối với máy tính cổ điển. Thuật toán Shor có tiềm năng phá vỡ nhiều hệ thống mật mã hiện tại, dựa trên độ khó của bài toán phân tích thừa số. Theo luận văn, thuật toán Shor có những ưu điểm vượt trội so với các thuật toán cổ điển trong việc giải quyết các bài toán liên quan đến số học và mật mã. Tuy nhiên, việc triển khai thuật toán Shor trên máy tính lượng tử thực tế vẫn còn nhiều thách thức.

3.1. Cơ Sở Lý Thuyết và Nguyên Lý Hoạt Động của Thuật Toán Shor

Thuật toán Shor dựa trên biến đổi Fourier lượng tử (QFT) và thuật toán tìm kiếm chu kỳ. Nó tận dụng khả năng tính toán song song của máy tính lượng tử để tìm ra chu kỳ của một hàm số nhanh hơn nhiều so với các thuật toán cổ điển. Sau khi tìm được chu kỳ, có thể sử dụng nó để phân tích số thành các thừa số nguyên tố. Thuật toán Shor thể hiện sức mạnh tiềm tàng của máy tính lượng tử trong việc giải quyết các bài toán mà máy tính cổ điển gặp khó khăn.

3.2. Các Bước Triển Khai Thuật Toán Shor và Phân Tích Độ Phức Tạp

Việc triển khai thuật toán Shor bao gồm nhiều bước, từ khởi tạo trạng thái qubit đến thực hiện biến đổi Fourier lượng tử và đo đạc kết quả. Độ phức tạp của thuật toán Shor là polynomial theo số lượng bit của số cần phân tích, trong khi độ phức tạp của các thuật toán cổ điển là exponential. Điều này có nghĩa là thuật toán Shor có thể phân tích các số rất lớn trong một thời gian hợp lý, trong khi máy tính cổ điển sẽ mất hàng tỷ năm. Theo luận văn, tác giả cũng trình bày 1 ví dụ cụ thể thứ tự các bước của thuật toán cho việc phân tích số 91 thành thừa số nguyên tố.

IV. Ứng Dụng Thực Tiễn Của Thuật Toán Lượng Tử Và Nghiên Cứu Mật Mã

Mặc dù máy tính lượng tử vẫn đang trong giai đoạn phát triển, thuật toán lượng tử đã có nhiều ứng dụng tiềm năng trong nhiều lĩnh vực. Trong mật mã, quantum key distribution (QKD), hay phân phối khóa lượng tử, cung cấp một phương pháp an toàn để truyền khóa mã hóa, không thể bị xâm phạm bởi các cuộc tấn công của máy tính cổ điển. Quantum machine learning (học máy lượng tử) hứa hẹn cải thiện hiệu suất của các thuật toán học máy, đặc biệt là trong các bài toán có dữ liệu lớn. Theo luận văn, một số ứng dụng của chương trình Wolfam Mathematica trong tính toán lượng tử được trình bày. Trên Wolfam Mathematica, việc xây dựng thuật toán lượng tử được đơn giản tối đa với các cổng lượng tử, các phép biến đổi,…được lập trình sẵn như cổng Hadamard, cổng NOT, cổng biến đổi Fourier lượng tử.

4.1. Phân Phối Khóa Lượng Tử QKD và Bảo Mật Thông Tin Lượng Tử

QKD sử dụng các nguyên lý của cơ học lượng tử để đảm bảo an toàn cho việc truyền khóa mã hóa. Bất kỳ nỗ lực nghe trộm nào cũng sẽ làm thay đổi trạng thái lượng tử của khóa, và người gửi và người nhận có thể phát hiện ra sự can thiệp. QKD cung cấp một mức độ bảo mật cao hơn so với các phương pháp truyền khóa cổ điển, vì nó không dựa trên độ khó của các bài toán toán học mà dựa trên các định luật vật lý. Sự ra đời của mật mã lượng tử đã tạo ra một cuộc cách mạng trong lĩnh vực bảo mật thông tin.

4.2. Học Máy Lượng Tử và Các Thuật Toán Học Máy Tăng Cường

Học máy lượng tử là một lĩnh vực mới nổi, kết hợp các nguyên lý của cơ học lượng tử và học máy để tạo ra các thuật toán mạnh mẽ hơn. Các quantum algorithm có thể tăng tốc các phép tính cần thiết cho học máy, như phân tích dữ liệu, phân loại và dự đoán. Quantum machine learning có tiềm năng cách mạng hóa nhiều lĩnh vực, từ y học đến tài chính và khoa học vật liệu. Các nhà khoa học đang nghiên cứu và phát triển các quantum algorithm mới để giải quyết các bài toán học máy phức tạp.

V. Nghiên Cứu Tiềm Năng Về Tương Lai Của Thuật Toán Lượng Tử

Tương lai của thuật toán lượng tử hứa hẹn nhiều điều thú vị. Với sự phát triển của máy tính lượng tử, chúng ta có thể mong đợi sự xuất hiện của các quantum algorithm mới có khả năng giải quyết các bài toán mà hiện tại là không thể. Các lĩnh vực như khám phá thuốc, thiết kế vật liệu và mô phỏng tài chính sẽ được hưởng lợi rất nhiều từ những tiến bộ này. Quantum simulation (mô phỏng lượng tử) sẽ cho phép chúng ta mô phỏng các hệ thống lượng tử phức tạp, mở ra những hiểu biết mới về thế giới tự nhiên.

5.1. Triển Vọng Ứng Dụng Thuật Toán Lượng Tử Trong Khoa Học và Công Nghệ

Thuật toán lượng tử có tiềm năng cách mạng hóa nhiều lĩnh vực khoa học và công nghệ. Trong hóa học, chúng có thể giúp chúng ta thiết kế các vật liệu mới với các tính chất mong muốn. Trong y học, chúng có thể giúp chúng ta phát triển các loại thuốc hiệu quả hơn. Trong khoa học vật liệu, chúng có thể giúp chúng ta khám phá các vật liệu siêu dẫn mới. Sự phát triển của thuật toán lượng tử sẽ thúc đẩy sự tiến bộ của khoa học và công nghệ nói chung.

5.2. Hướng Phát Triển Các Thuật Toán Lượng Tử Thế Hệ Mới

Các nhà khoa học đang nỗ lực phát triển các quantum algorithm mới để giải quyết các bài toán ngày càng phức tạp. Một trong những hướng phát triển quan trọng là tạo ra các quantum algorithm có khả năng chống lại các cuộc tấn công của máy tính lượng tử. Ngoài ra, việc phát triển các quantum algorithm hiệu quả hơn và dễ triển khai hơn cũng là một ưu tiên hàng đầu. Sự sáng tạo và đổi mới trong lĩnh vực thuật toán lượng tử sẽ tiếp tục mở ra những chân trời mới cho khoa học và công nghệ.

VI. Kết Luận Về Thuật Toán Lượng Tử Trong Lý Thuyết Thông Tin

Lý thuyết thông tin lượng tử và thuật toán lượng tử đại diện cho một bước tiến lớn trong khoa học thông tin và khoa học máy tính. Mặc dù còn nhiều thách thức, tiềm năng của chúng là rất lớn. Với sự phát triển của máy tính lượng tử, chúng ta có thể mong đợi sự xuất hiện của các ứng dụng đột phá trong nhiều lĩnh vực. Nghiên cứu về thuật toán lượng tử cần sự hợp tác giữa các nhà khoa học từ nhiều lĩnh vực khác nhau, bao gồm vật lý, toán học và khoa học máy tính. Theo luận văn, việc nghiên cứu lý thuyết thông tin lượng tử cần các nghiên cứu trong nhiều ngành: khoa học máy tính, vật lý lượng tử và toán học.

6.1. Tổng Kết Các Thành Tựu và Hạn Chế Hiện Tại

Lý thuyết thông tin lượng tử đã đạt được những thành tựu đáng kể trong việc phát triển các quantum algorithm và các giao thức bảo mật. Tuy nhiên, vẫn còn nhiều hạn chế cần vượt qua, bao gồm độ ổn định của qubit, khả năng mở rộng của máy tính lượng tử và chi phí triển khai. Việc giải quyết những hạn chế này sẽ mở đường cho sự phát triển rộng rãi của thuật toán lượng tử và máy tính lượng tử.

6.2. Định Hướng Nghiên Cứu Trong Tương Lai

Nghiên cứu trong tương lai cần tập trung vào việc cải thiện độ ổn định và khả năng mở rộng của qubit, phát triển các quantum algorithm hiệu quả hơn và khám phá các ứng dụng mới của thuật toán lượng tử. Sự hợp tác giữa các nhà khoa học từ nhiều lĩnh vực khác nhau là chìa khóa để thúc đẩy sự tiến bộ trong lĩnh vực này. Với những nỗ lực không ngừng, chúng ta có thể mong đợi một tương lai mà thuật toán lượng tử đóng vai trò quan trọng trong việc giải quyết những thách thức lớn của xã hội.

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

Chương 1 Một số khó khăn của lý thuyết thông tin cổ điển Các kiến thức trong chương này được lấy từ tài liệu [1], [6], [9].1 Nén dữ liệu 1.1 Ví dụ về nén dữ liệu Những khó khăn đầu tiên của lý thuyết thông tin cổ điển là việc bị giới hạn kích thước đầu ra của nguồn tin. Shannon đã chứng minh được rằng việc nén thông tin đầu ra một cách tùy ý là không thể. Chúng ta bắt đầu với một ví dụ đơn giản để minh họa khái niệm của một nguồn tin. Sau đó chúng ta phát triển một chương trình mã hóa nguồn này với đòi hỏi ít bit hơn mà vẫn mã hóa chính xác thông tin.

Một người gửi A muốn gửi bốn ký tự a, b, c, d (có xác suất khác nhau) tới một người nhận B. Giả sử thêm rằng, có một kênh nhiễu truyền thông tin một cách hoàn hảo kết nối A và B. A và B muốn giảm thiểu số lần sử dụng kênh nhiễu này để giảm chi phí. Phân bố xác suất của bốn ký tự a, b, c, d là: Pr(a) = 1/2; Pr(b) = 1/8; Pr(c) = 1/4; Pr(d) = 1/8.

Tuy nhiên, một kênh nhiễu chỉ chấp nhận bit chứ không chấp nhận các kí tự a, b, c, d là đầu vào nên ta phải mã hóa các ký tự bằng biểu diễn nhị 3 phân, mỗi biểu diễn nhị phân là một từ mã và chiều dài của từ mã được dùng để đo lường hiệu suất. Chẳng hạn: A muốn gửi dãy ký tự aabcdaccaac.1) Cách mã hóa thứ nhất: a → 00 ; b → 01 ; c → 10 ; → 11. Cách thứ hai ta dùng mã hóa Huffman. Mã hóa Huffman là một thuật toán mã hóa dùng để nén dữ liệu.

Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. Để đảm bảo điều này thì số bit dùng cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Tuy nhiên, vì độ dài mã thay đổi nên khi giải mã để phân biệt được xâu bít nào là mã hóa của ký hiệu nào ta cần dùng đến mã tiền tố. Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã ấy.

Chẳng hạn: • Nếu mã hóa a → 0; b → 110; c → 01; d → 111, thì bộ từ mã này không là mã tiền tố ví từ mã của "a" là tiền tố của từ mã của "c". Để mã hóa xâu aabcdaccaac phải đặt dấu ngăn cách vào giữa các từ mã 0,0,110,01,111,0,01,01,0,0,01. Như vậy, các dấu nhăn cách chiếm một không gian đáng kể trong bảng mã.2) thì bộ từ mã này là mã tiền tố. Với bộ mã tiền tố này khi mã hóa xâu aabcdaccaac ta thu được 4 Đặc biệt, mã hóa với độ dài từ mã không đổi như cách mã hóa thứ nhất cũng là một mã tiền tố.

Mã hóa Huffma có thể được biểu diễn trên cây nhị phân. Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu vào một lá. Từ mã của mỗi kí hiệu được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1. Hình minh họa cho cây nhị phân bốn lá Hình 1.1: Cây nhị phân bốn lá Như vậy, A sẽ mã hóa aabcdaccaac → 0011010111010100010 và gửi dãy mã hóa này cho B.

B phân tích 0011010111010100010 → aabcdaccaac. Chúng ta có thể tính toán chiều dài của chương trình mã hóa này như sau: 1 1 1 1 1 7. 2 8 4 4 8 4 So sách hai cách mã hóa ta thấy cách mã hóa thứ 2 đòi hỏi ít bit hơn so với cách mã hóa thứ nhất.2 Cách đo thông tin Ở ví dụ 1.1 trình bày một cách để đo lường thông tin theo sự phân bố xác suất của các ký tự. Các nội dung thông tin của một ký tự x ∈ {a, b, c, d}, 5 với p(x) là xác suất của x, 1 i(x) = log2 = − log2 p(x).

p(x) Trong công thức này, ký tự có xác suất càng nhỏ thì chứa một thông tin càng lớn. Độ dài mỗi từ mã trong chương trình mã hóa bằng các nội dung thông tin của các kí tự tương ứng của nó. Các nội dung thông tin có tính chất cộng tính. Giả sử rằng nguồn thông tin sản xuất hai ký hiệu x1 và x2.

Xác suất xuất hiện 2 ký tự này là p(x1 , x2 ), xác suất xuất hiện của x1 là p(x1 ), xác suất xuất hiện của x2 là p(x2 ) và giả sử nguồn tạo ra mỗi kí tự là độc lập. Các nội dung thông tin dự kiến của các nguồn thông tin X X p(x)i(x) = − p(x)log2 (p(x)). x x Đại lượng trên là rất quan trọng trong lý thuyết thông tin, nó được gọi là entropy của các nguồn thông tin. Entropy của các nguồn thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên.

Entropy thường được diễn đạt dưới dạng số lượng bit cần thiết trung bình để lưu trữ hoặc dẫn truyền. Ví dụ, trong chương trình mã hóa ở ví dụ 1.1, chiều dài dự kiến của một từ mã là entropy của nguồn thông tin: 1 1 1 1 1 1 1 1 − log2 − log2 − log2 − log2 2 2 8 8 4 4 8 8 1 1 1 1 =. 4 6 Nếu một biến ngẫu nhiên rời rạc X, có thể nhận các giá trị là 1,2,.,n với các xác suất tương ứng p(1), p(2),. i=1 p (i) i=1 Không phải ngẫu nhiên mà chúng ta lựa chọn các chương trình mã hóa đặc biệt (1.

Việc lựa chọn chương trình mã hóa liên quan đến cấu trúc của các nguồn thông tin, số ký hiệu là một lũy thừa của hai và xác suất của mỗi biểu tượng là nghịch đảo của một lũy thừa của hai.3 Lý thuyết mã hóa nguồn của Shannon Câu hỏi tiếp theo là liệu có chương trình nào khác có thể đạt được một tỷ lệ nén tốt hơn so với các chương trình trong (1. Để trả lời câu hỏi này, chúng ta xem xét một nguồn thông tin tổng quát hơn và giới thiệu một khái niệm của Shannon, ý tưởng về tập hợp có trình tự điển hình. Chúng ta thể hiện một nguồn thông tin tổng quát hơn với một biến ngẫu nhiên X có chứa x là các chữ cái trong bảng chữ cái χ.3) x∈χ Nội dung thông tin i(X) của biến ngẫu nhiên X là i(X) = −log2 (pX (X)), (1.4) và chính nội dung thông tin là một biến ngẫu nhiên. Không có gì sai về mặt toán học khi biến ngẫu nhiên X là đối số cho hàm mật độ pX.

Một lần nữa, kì vọng của nội dung thông tin của X bằng với entropy của X , EX {−log2 (pX (X))} = H(X). Bây giờ, để mã hóa nguồn thông tin trên, phương pháp mã hóa từng ký tự như trên không còn phù hợp. Ý tưởng mang tính đột phá của Shannon là cho các nguồn phát ra một số lượng lớn các phần tử và sau đó mã hóa 7 các dữ liệu phát ra như một khối lớn, thay vì mã hóa mỗi ký tự như ví dụ 1. Kỹ thuật này được gọi là khối mã hóa.

Hiểu sâu vấn đề nên Shannon cho phép có một lỗi nhỏ trong các chương trình nén vì lỗi này sẽ biến mất khi kích thước khối trở nên lớn tùy ý. Để thực hiện các chương trình mã hóa khối một cách rõ ràng hơn, Shannon gợi ý để cho các nguồn phát ra các trình tự như sau xn = x1 x2 .xn , trong đó: • n là một số tự nhiên khá lớn biểu thị kích thước của khối dữ liệu phát ra., n) là biểu tượng phát ra thứ i. Gọi Xn biểu thị các biến ngẫu nhiên gắn liền với xn , và Xi là biến ngẫu nhiên cho các xi. Giả thiết quan trọng nhất đối với nguồn thông tin này là nó độc lập và phân phối giống nhau.

Giả thiết này có nghĩa là, mỗi Xi biến ngẫu nhiên có phân phối giống như biến ngẫu nhiên X. Theo đó, xác suất để xn phát ra là pX n (xn ) =pX1 , X2 ,.5) i=1 Từ công thức (1.5) về xác suất của những biến ngẫu nhiên độc lập, quá trình tính toán đơn giản hơn rất nhiều. Giả sử rằng, chúng ta gọi các chữ cái trong bảng chữ cái χ là a1 , a2 ,. Gọi N (ai |xn ) là số lần xuất hiện của chữ cái ai trong dãy xn (trong đó i = 1,.

Ví dụ, xét chuỗi ký tự (1., xn } như là một khối với một bộ mã ε và truyền từ mã trên kênh bit không nhiễu I. B nhận được nó, B giải mã từ mã nhận được với một bộ giải mã D và thu được theo trình tự ban đầu mà A đã truyền nếu mã có xác suất lỗi rất nhỏ. Theo công thức (1.6) i=1 i=1 Lưu ý rằng, độ dài n của chuỗi phát ra cực kỳ lớn, lớn hơn nhiều lần so với kích thước bảng chữ cái |χ|, n  |χ| .6) đơn giản hơn rất nhiều so với công thức (1. Với xn là một chuỗi dài tổ hợp của các ký tự {x1 , x2 , ., xn } nên ta có thể hoán vị các ký tự trong chuỗi xn vì khi hoán vị xác suất xuất hiện của các kí tự không thay đổi, xn → a.

| 2{z | {z } n n N (a1 |x ) N (a2 |x ) N (a|χ| |xn ) Trên đây chúng ta đang xét nguồn phát ra theo một trình tự cụ thể. Bây giờ, chúng ta nghiên cứu cách thực hiện đối với nguồn phát ra một chuỗi ngẫu nhiên X n. Sự khác biệt giữa cách thực hiện của dãy có thứ tự xn và dãy ngẫu nhiên X n rất quan trọng. Đặc biệt, chúng ta xem xét về trung bình mẫu nội dung thông tin của chuỗi ngẫu nhiên này (chia nội dung thông tin cho n để được trung bình mẫu), 1 − log2 (pX n (X n )).7) n Có thể chúng ta thấy lạ khi cả X n và pX n (X n ) đều là những biến ngẫu nhiên, nhưng cách biểu diễn này thật sự tốt về mặt toán học bởi vì nó sẽ 9 trở nên rất ngắn ngọn.

Cách biểu diễn này giống với công thức (1.4) dùng để tính entropy.