Lý thuyết mã hóa. Các loại mã hóa. Sự ra đời của lý thuyết mã hóa Phân loại các phương pháp mã hóa

"Mục đích của khóa học này là giúp bạn chuẩn bị cho tương lai kỹ thuật của mình."

Chào, Habr. Bạn còn nhớ bài viết tuyệt vời "Bạn và công việc của bạn" (+219, 2442 dấu trang, 394k lượt đọc)?

Vì vậy, Hamming (vâng, vâng, tự kiểm tra và tự sửa mã Hamming) có cả một cuốn sách dựa trên các bài giảng của anh ấy. Chúng tôi dịch nó, bởi vì người đàn ông nói vấn đề.

Cuốn sách này không chỉ nói về CNTT, đây là cuốn sách nói về phong cách tư duy của những con người vô cùng tuyệt vời. “Nó không chỉ là trách nhiệm của suy nghĩ tích cực; nó mô tả các điều kiện làm tăng cơ hội làm được việc lớn. "

Chúng tôi đã dịch 28 (trong số 30) chương. Và chúng tôi đang tiến hành xuất bản "trên giấy".

Lý thuyết mã hóa - I

Sau khi xem xét máy tính và cách chúng hoạt động, bây giờ chúng ta sẽ xem xét vấn đề trình bày thông tin: cách máy tính biểu diễn thông tin mà chúng ta muốn xử lý. Ý nghĩa của bất kỳ ký tự nào có thể phụ thuộc vào cách nó được xử lý, máy móc không có ý nghĩa cụ thể cho bit được sử dụng. Khi thảo luận về lịch sử của phần mềm trong Chương 4, chúng tôi đã xem xét một số ngôn ngữ lập trình tổng hợp, trong đó mã của lệnh dừng trùng với mã của các lệnh khác. Tình huống này là điển hình cho hầu hết các ngôn ngữ, ý nghĩa của lệnh được xác định bởi chương trình tương ứng.

Để đơn giản hóa vấn đề trình bày thông tin, chúng ta hãy xem xét vấn đề chuyển thông tin từ điểm này sang điểm khác. Câu hỏi này liên quan đến vấn đề bảo quản thông tin. Vấn đề truyền thông tin trong thời gian và không gian là giống hệt nhau. Hình 10.1 mô tả một mô hình truyền thông điển hình.

Hình 10.1

Bên trái trong Hình 10.1 là nguồn thông tin. Khi xem xét một mô hình, chúng tôi không quan tâm đến bản chất của nguồn. Nó có thể là một tập hợp các ký hiệu bảng chữ cái, con số, công thức toán học, nốt nhạc, ký hiệu mà chúng ta có thể biểu diễn các chuyển động khiêu vũ - bản chất của nguồn và ý nghĩa của các ký hiệu được lưu trữ trong đó không phải là một phần của mô hình truyền tải. Chúng tôi chỉ coi là nguồn thông tin, với hạn chế này, một lý thuyết tổng quát, mạnh mẽ thu được có thể được mở rộng cho nhiều lĩnh vực. Nó là một sự trừu tượng từ nhiều ứng dụng.

Khi Shannon tạo ra lý thuyết thông tin vào cuối những năm 1940, người ta tin rằng nó nên được gọi là lý thuyết truyền thông, nhưng ông nhấn mạnh vào thuật ngữ thông tin. Thuật ngữ này đã trở thành một nguồn liên tục của cả sự quan tâm gia tăng và sự thất vọng liên tục về mặt lý thuyết. Các nhà điều tra muốn xây dựng toàn bộ "lý thuyết thông tin", họ đã biến chất thành một lý thuyết về tập hợp các ký hiệu. Quay trở lại mô hình truyền, chúng ta có một nguồn dữ liệu cần được mã hóa để truyền.

Bộ mã hóa bao gồm hai phần, phần đầu tiên được gọi là bộ mã hóa nguồn, tên chính xác tùy thuộc vào loại nguồn. Các nguồn của các kiểu dữ liệu khác nhau tương ứng với các loại bộ mã hóa khác nhau.

Phần thứ hai của quá trình mã hóa được gọi là mã hóa kênh và phụ thuộc vào loại kênh truyền dữ liệu. Do đó, phần thứ hai của quá trình mã hóa được khớp với loại kênh truyền. Do đó, khi sử dụng các giao diện chuẩn, dữ liệu từ nguồn đầu tiên được mã hóa theo yêu cầu của giao diện, sau đó theo yêu cầu của kênh truyền dữ liệu được sử dụng.

Theo mô hình trong Hình 10.1, liên kết dữ liệu bị “nhiễu ngẫu nhiên thêm”. Tất cả tiếng ồn trong hệ thống được kết hợp tại điểm này. Giả định rằng bộ mã hóa nhận được tất cả các ký hiệu mà không bị biến dạng và bộ giải mã thực hiện chức năng của nó mà không có lỗi. Đây là một số lý tưởng hóa, nhưng đối với nhiều mục đích thực tế, nó gần với thực tế.

Giai đoạn giải mã cũng gồm hai giai đoạn: kênh - chuẩn, chuẩn - máy thu dữ liệu. Khi kết thúc quá trình chuyển giao, dữ liệu được chuyển đến người tiêu dùng. Một lần nữa, chúng tôi không xem xét câu hỏi về cách người tiêu dùng giải thích dữ liệu này.

Như đã đề cập trước đó, một hệ thống truyền dữ liệu, ví dụ, tin nhắn điện thoại, radio, chương trình TV, trình bày dữ liệu dưới dạng một tập hợp các số trong sổ đăng ký của máy tính. Một lần nữa, truyền trong không gian không khác gì truyền trong thời gian hoặc lưu trữ thông tin. Bạn có thông tin sẽ được yêu cầu sau một thời gian, sau đó nó phải được mã hóa và lưu trữ tại nguồn lưu trữ dữ liệu. Thông tin được giải mã nếu cần thiết. Nếu hệ thống mã hóa và giải mã giống nhau, chúng ta truyền dữ liệu qua kênh truyền không thay đổi.

Sự khác biệt cơ bản giữa lý thuyết đã trình bày và lý thuyết thông thường trong vật lý là giả định rằng không có nhiễu ở nguồn và máy thu. Trên thực tế, lỗi xảy ra trong bất kỳ phần cứng nào. Trong cơ học lượng tử, tiếng ồn xảy ra ở bất kỳ giai đoạn nào theo nguyên lý bất định, và không phải là điều kiện ban đầu; trong mọi trường hợp, khái niệm nhiễu trong lý thuyết thông tin không tương đương với khái niệm trong cơ học lượng tử.
Để xác định rõ ràng, chúng ta sẽ xem xét thêm về dạng biểu diễn dữ liệu nhị phân trong hệ thống. Các biểu mẫu khác được xử lý theo cách tương tự, vì lý do đơn giản, chúng tôi sẽ không xem xét chúng.

Hãy bắt đầu bằng cách xem xét các hệ thống có các ký tự được mã hóa có độ dài thay đổi, như trong mã Morse cổ điển gồm các dấu chấm và dấu gạch ngang, trong đó các ký tự phổ biến là ngắn và các ký tự hiếm là dài. Cách tiếp cận này cho phép bạn đạt được hiệu quả mã cao, nhưng cần lưu ý rằng mã Morse là mã bậc ba, không phải mã nhị phân, vì nó chứa ký tự khoảng trắng giữa dấu chấm và dấu gạch ngang. Nếu tất cả các ký tự trong mã có cùng độ dài, thì mã như vậy được gọi là mã khối.

Thuộc tính cần thiết rõ ràng đầu tiên của mã là khả năng giải mã một cách rõ ràng một thông điệp trong trường hợp không có nhiễu, ít nhất đây có vẻ là một thuộc tính mong muốn, mặc dù trong một số trường hợp, yêu cầu này có thể bị bỏ qua. Dữ liệu từ kênh truyền có dạng như một luồng gồm các kênh truyền dữ liệu và số không đến máy thu.

Hãy gọi hai ký hiệu liền kề là mở rộng kép, ba ký hiệu liền kề là mở rộng gấp ba, và nói chung, nếu chúng ta gửi N ký hiệu, bộ nhận sẽ thấy các bổ sung vào mã cơ sở của N ký hiệu. Máy thu, không biết giá trị của N, phải chia luồng thành các khối được dịch. Hay nói cách khác, người nhận phải có khả năng phân tách luồng theo một cách duy nhất để khôi phục lại thông điệp ban đầu.

Hãy xem xét một bảng chữ cái có số lượng ký tự nhỏ, thường là các bảng chữ cái lớn hơn nhiều. Bảng chữ cái của các ngôn ngữ bắt đầu từ 16 đến 36 ký tự, bao gồm chữ hoa và chữ thường, dấu số, dấu câu. Ví dụ, trong bảng ASCII, 128 = 2 ^ 7 ký tự.
Hãy xem xét một đoạn mã đặc biệt gồm 4 ký tự s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Cách người nhận sẽ diễn giải biểu thức nhận được tiếp theo

Thế nào s1s1s4 hoặc thế nào s2s4?

Bạn không thể đưa ra câu trả lời rõ ràng cho câu hỏi này, mã này chắc chắn không được giải mã, do đó, nó không đạt yêu cầu. Mặt khác, mã

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Giải mã tin nhắn theo một cách độc đáo. Chúng ta hãy lấy một chuỗi tùy ý và xem máy thu sẽ giải mã nó như thế nào. Bạn cần xây dựng một cây giải mã Theo mẫu trong hình 10.II. Hàng

1101000010011011100010100110 …

Có thể được chia thành các khối ký tự

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Theo quy tắc sau để xây dựng cây giải mã:

Nếu bạn đang ở trên ngọn cây, bạn đọc ký tự tiếp theo. Khi bạn đến lá cây, bạn chuyển đổi chuỗi thành một ký tự và quay lại phần bắt đầu.

Lý do cây như vậy tồn tại là không có ký tự nào là tiền tố của cây khác, vì vậy bạn luôn biết khi nào quay lại phần đầu của cây giải mã.

Cần chú ý những điều sau. Đầu tiên, giải mã là một quá trình phân luồng nghiêm ngặt, trong đó mỗi bit chỉ được kiểm tra một lần. Thứ hai, các giao thức thường bao gồm các ký tự đánh dấu sự kết thúc của quá trình giải mã và cần thiết để chỉ ra sự kết thúc của thông điệp.

Tránh sử dụng ký tự theo sau là một lỗi phổ biến trong thiết kế mã. Tất nhiên, một chế độ giải mã không đổi có thể được cung cấp, trong trường hợp đó không cần ký hiệu dấu.

Hình 10.II

Câu hỏi tiếp theo là mã để giải mã trực tuyến (tức thì). Xem xét mã lấy được từ mã trước đó bằng cách hiển thị các ký tự

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Giả sử chúng ta có chuỗi 011111...111 ... Cách duy nhất bạn có thể giải mã văn bản của tin nhắn là nhóm các bit từ cuối thành 3 trong nhóm và chọn các nhóm có số 0 đứng đầu trước các bit, sau đó bạn có thể giải mã. Một đoạn mã như vậy có thể được giải mã theo một cách duy nhất, nhưng không phải ngay lập tức! Để giải mã, bạn phải đợi đến khi kết thúc đường truyền! Trong thực tế, cách tiếp cận này phủ định tốc độ giải mã (định lý McMillan), do đó, cần phải tìm cách giải mã tức thời.

Hãy xem xét hai cách để mã hóa cùng một ký tự, Si:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Cây giải mã cho phương pháp này được thể hiện trong Hình 10.III.

Hình 10.III

Cách thứ hai

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,

Cây giải mã của sự ra đi này được thể hiện trong Hình 10.IV.

Cách rõ ràng nhất để đo chất lượng mã là độ dài trung bình cho một tập hợp các thông báo. Để làm được điều này, cần phải tính độ dài của mã của mỗi ký tự nhân với xác suất xuất hiện của số pi tương ứng. Điều này sẽ cung cấp độ dài của toàn bộ mã. Công thức cho độ dài mã trung bình L cho một bảng chữ cái gồm q ký tự như sau

Trong đó pi là xác suất xuất hiện của ký tự si, li là độ dài tương ứng của ký tự được mã hóa. Để có một mã hiệu quả, giá trị của L phải càng nhỏ càng tốt. Nếu P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 và p5 = 1/16, thì đối với mã số 1, chúng ta nhận được giá trị của độ dài mã

Và đối với mã số 2

Các giá trị thu được cho biết mức độ ưu tiên của mã đầu tiên.
Nếu tất cả các từ trong bảng chữ cái có cùng xác suất xuất hiện, thì mã thứ hai sẽ được ưu tiên hơn. Ví dụ: với pi = 1/5 độ dài của mã # 1

Và độ dài của mã # 2

Kết quả này cho thấy ưu tiên của 2 mã. Vì vậy, khi thiết kế mã "tốt", khả năng xảy ra các ký hiệu phải được xem xét.

Hình 10.IV

Hình 10.V

Hãy xem xét bất đẳng thức Kraft, xác định giá trị giới hạn của độ dài mã ký tự li. Dựa trên cơ sở 2, bất đẳng thức được biểu diễn dưới dạng

Sự bất bình đẳng này có nghĩa là không thể có quá nhiều ký hiệu ngắn trong bảng chữ cái, nếu không tổng sẽ khá lớn.

Để chứng minh bất đẳng thức Kraft cho bất kỳ mã giải mã nhanh duy nhất nào, chúng tôi xây dựng một cây giải mã và áp dụng phương pháp quy nạp toán học. Nếu một cây có một hoặc hai lá, như trong Hình 10.V, thì chắc chắn điều bất đẳng thức là đúng. Hơn nữa, nếu cây có nhiều hơn hai lá, thì ta tách cây dài m thành hai cây con. Theo nguyên lý quy nạp, chúng ta giả sử rằng bất đẳng thức đúng với mỗi nhánh có chiều cao từ m -1 trở xuống. Theo nguyên lý quy nạp, áp dụng bất đẳng thức cho từng nhánh. Hãy biểu thị độ dài của mã của các nhánh K "và K" ". Khi hai nhánh của cây được kết hợp với nhau, độ dài của mỗi mã tăng lên 1, do đó, độ dài của mã bao gồm tổng K '/ 2 và K '' / 2,

Định lý được chứng minh.

Hãy xem xét chứng minh của định lý Macmillan. Chúng tôi áp dụng bất đẳng thức Kraft cho các mã giải mã không được sắp xếp hợp lý. Chứng minh dựa trên thực tế rằng với bất kỳ số nào K> 1 thì lũy thừa bậc n của số đó chắc chắn lớn hơn một hàm tuyến tính của n, trong đó n là một số khá lớn. Chúng tôi nâng bất đẳng thức Kraft lên lũy thừa thứ n và biểu diễn biểu thức dưới dạng tổng

Trong đó Nk là số ký tự có độ dài k, phép tính tổng bắt đầu với độ dài tối thiểu của biểu diễn ký tự thứ n và kết thúc bằng độ dài tối đa nl, trong đó l là độ dài tối đa của ký tự được mã hóa. Nó tuân theo yêu cầu giải mã duy nhất đó. Số tiền được trình bày dưới dạng

Nếu K> 1 thì cần đặt n đủ lớn để bất đẳng thức trở thành sai. Do đó, k<= 1; теорема Макмиллана доказана.

Hãy xem xét một số ví dụ về ứng dụng của bất đẳng thức Kraft. Có thể có một mã được giải mã duy nhất với độ dài 1, 3, 3, 3 không? Có, kể từ khi

Còn độ dài 1, 2, 2, 3 thì sao? Tính theo công thức

Bất bình đẳng bị vi phạm! Có quá nhiều ký tự ngắn trong mã này.

Mã dấu chấm (mã dấu phẩy) là mã bao gồm 1 ký tự, kết thúc bằng ký tự 0, ngoại trừ ký tự cuối cùng bao gồm tất cả các ký tự. Một trong những trường hợp đặc biệt là mã

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5 = 11111.

Đối với mã này, chúng tôi nhận được biểu thức cho bất đẳng thức Kraft

Trong trường hợp này, chúng tôi đạt được sự bình đẳng. Dễ dàng nhận thấy rằng đối với mã điểm, bất bình đẳng Kraft biến thành bình đẳng.

Khi xây dựng mã, bạn cần chú ý đến số lượng Kraft. Nếu tổng Kraft bắt đầu vượt quá 1, thì đây là tín hiệu về sự cần thiết phải bao gồm một ký tự có độ dài khác để giảm độ dài mã trung bình.

Cần lưu ý rằng sự bất bình đẳng của Kraft không có nghĩa là mã này được giải mã duy nhất, mà là mã có các ký tự có độ dài như vậy được giải mã duy nhất. Để tạo một mã được giải mã duy nhất, bạn có thể gán một số nhị phân với độ dài tương ứng tính bằng bit li. Ví dụ, với độ dài 2, 2, 3, 3, 4, 4, 4, 4, chúng ta thu được bất đẳng thức Kraft

Do đó, một mã phát trực tuyến được giải mã duy nhất như vậy có thể tồn tại.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Tôi muốn thu hút sự chú ý của bạn đến những gì thực sự xảy ra khi chúng ta trao đổi ý kiến. Ví dụ, tại thời điểm này, tôi muốn chuyển một ý tưởng từ đầu của tôi sang ý tưởng của bạn. Tôi đang phát âm một số từ mà qua đó tôi tin rằng bạn sẽ có thể hiểu (hiểu) ý tưởng này.

Nhưng sau này khi bạn muốn truyền đạt ý tưởng này cho bạn của mình, bạn gần như chắc chắn sẽ nói những lời hoàn toàn khác. Trong thực tế, ý nghĩa hay ý nghĩa không bị giới hạn trong bất kỳ từ cụ thể nào. Tôi đã sử dụng một số từ, nhưng bạn có thể sử dụng các từ hoàn toàn khác nhau để truyền đạt cùng một ý tưởng. Do đó, các từ khác nhau có thể chuyển tải cùng một thông tin. Tuy nhiên, ngay sau khi bạn nói với người đối thoại rằng bạn không hiểu thông điệp, thì theo quy luật, để truyền đạt ý nghĩa, người đối thoại sẽ chọn một bộ từ khác, một phần hai hoặc thậm chí một phần ba. Do đó, thông tin không được chứa trong một tập hợp các từ cụ thể. Một khi bạn đã nhận được những từ này hoặc những từ đó, thì hãy thực hiện tốt việc chuyển từ ngữ thành ý tưởng mà người đối thoại muốn truyền đạt cho bạn.

Chúng ta học cách chọn từ để thích ứng với người đối thoại. Theo một nghĩa nào đó, chúng tôi chọn từ bằng cách phù hợp với suy nghĩ của chúng tôi và mức độ nhiễu trong kênh, mặc dù so sánh này không phản ánh chính xác mô hình mà tôi sử dụng để biểu thị nhiễu trong quá trình giải mã. Trong các tổ chức lớn, không có khả năng nghe những gì người kia đang nói là một vấn đề lớn. Ở các vị trí cấp cao, nhân viên nghe “những gì họ muốn nghe”. Trong một số trường hợp, bạn cần ghi nhớ điều này khi tiến lên nấc thang sự nghiệp. Việc trình bày thông tin dưới dạng chính thức là sự phản ánh một phần các quá trình trong cuộc sống của chúng ta và đã được ứng dụng rộng rãi vượt xa ranh giới của các quy tắc chính thức trong các ứng dụng máy tính.

Còn tiếp...

Ai muốn trợ giúp về dịch thuật, bố cục và xuất bản cuốn sách - hãy viết thư cá nhân hoặc email [email được bảo vệ]

Nhân tiện, chúng tôi cũng đã ra mắt bản dịch của một cuốn sách hay nhất khác -

Mã hóa. Các khái niệm cơ bản.

Các phương pháp mã hóa khác nhau đã được sử dụng rộng rãi trong thực tế của con người từ thời xa xưa. Ví dụ, ký hiệu vị trí thập phân là một cách mã hóa các số tự nhiên. Một cách khác để mã hóa các số tự nhiên là chữ số La Mã, và phương pháp này thực tế là trực quan và tự nhiên hơn, ngón tay - I, năm - V, hai năm - X. Tuy nhiên, với phương pháp mã hóa này, việc thực hiện các phép tính số học sẽ khó hơn. trên số lượng lớn, vì vậy nó đã được thay thế bằng phương pháp mã hóa dựa trên ký hiệu thập phân vị trí. Từ ví dụ này, chúng ta có thể kết luận rằng các phương pháp mã hóa khác nhau có các tính năng cụ thể chỉ dành riêng cho chúng, tùy thuộc vào mục tiêu mã hóa, có thể là ưu điểm của một phương pháp mã hóa cụ thể hoặc là nhược điểm của nó.

Các phương pháp mã hóa số của các đối tượng hình học và vị trí của chúng trong không gian được biết đến rộng rãi: Tọa độ Descartes và tọa độ cực. Và các phương pháp mã hóa này khác nhau về các tính năng cụ thể vốn có của chúng.

Cho đến thế kỷ 20, các phương pháp và công cụ mã hóa đóng vai trò phụ trợ, nhưng với sự ra đời của máy tính, tình hình đã thay đổi hoàn toàn. Mã hóa được sử dụng rộng rãi trong công nghệ thông tin và thường là vấn đề trọng tâm trong việc giải quyết nhiều vấn đề như:

- trình bày dữ liệu có tính chất tùy ý (số, văn bản, đồ họa) trong bộ nhớ máy tính;

- truyền dữ liệu tối ưu qua các kênh truyền thông;

- bảo vệ thông tin (tin nhắn) khỏi bị truy cập trái phép;

- đảm bảo khả năng chống nhiễu trong quá trình truyền dữ liệu qua các kênh truyền thông;

- nén thông tin.

Theo quan điểm của lý thuyết thông tin, mã hóa là một quá trình so sánh rõ ràng bảng chữ cái của một nguồn thông điệp và một tập hợp các ký hiệu điều kiện nhất định, được thực hiện theo một quy tắc nhất định, và một mã (bảng chữ cái) là một tập hợp hoàn chỉnh. (tập hợp) các ký hiệu có điều kiện khác nhau (ký hiệu mã) có thể được sử dụng để mã hóa thông điệp gốc và có thể thực hiện được với quy tắc mã hóa đã cho. Số lượng các ký hiệu mã khác nhau tạo nên bảng chữ cái mã được gọi là khối lượng của mã hoặc khối lượng của bảng chữ cái mã. Rõ ràng, khối lượng của bảng chữ cái mã không thể nhỏ hơn khối lượng của bảng chữ cái của thông điệp gốc đang được mã hóa. Như vậy, mã hóa là sự biến đổi thông điệp gốc thành một tập hợp hoặc một chuỗi các ký hiệu mã đại diện cho thông điệp được truyền qua kênh truyền thông.

Mã hóa có thể là số (kỹ thuật số) và không phải số, tùy thuộc vào loại mà các ký hiệu mã được biểu diễn: các số trong bất kỳ hệ thống số nào hoặc một số đối tượng hoặc dấu hiệu khác, tương ứng.

Trong hầu hết các trường hợp, ký hiệu mã là tập hợp hoặc chuỗi của một số thành phần đơn giản nhất, ví dụ, một dãy số trong các ký hiệu mã của mã số, được gọi là các phần tử của ký hiệu mã. Vị trí hoặc số sê-ri của một phần tử trong từ mã được xác định bởi vị trí của nó.

Số phần tử của ký tự mã được sử dụng để đại diện cho một ký tự trong bảng chữ cái của nguồn gốc của thông báo được gọi là giá trị mã. Nếu giá trị của mã giống nhau đối với tất cả các ký hiệu trong bảng chữ cái của thông điệp gốc, thì mã đó được gọi là đồng nhất, ngược lại - không đồng đều. Số phần tử có trong ký hiệu mã đôi khi được gọi là độ dài của ký hiệu mã.

Theo quan điểm của dự phòng, tất cả các mã có thể được chia thành mã không dự phòng và mã dự phòng. Trong mã dự phòng, số lượng phần tử của ký hiệu mã có thể giảm do sử dụng hiệu quả hơn các phần tử còn lại, trong mã không dư thừa, việc giảm số lượng phần tử trong ký hiệu mã là không thể.

Các vấn đề về mã hóa khi không có sự can thiệp và sự hiện diện của chúng là khác nhau đáng kể. Do đó, có sự phân biệt giữa mã hóa hiệu quả (entropy) và mã hóa sửa chữa (sửa lỗi). Với mã hóa hiệu quả, nhiệm vụ là đạt được sự biểu diễn của các ký tự trong bảng chữ cái của nguồn thông báo với số lượng phần tử ký hiệu mã tối thiểu trung bình trên một ký tự của bảng chữ cái của nguồn thông báo bằng cách giảm sự dư thừa của mã, dẫn đến tăng tốc độ truyền tin nhắn. Và với mã hóa sửa chữa (sửa lỗi), nhiệm vụ là giảm xác suất sai sót trong việc truyền các ký hiệu của bảng chữ cái gốc bằng cách phát hiện và sửa lỗi bằng cách đưa vào mã dự phòng bổ sung.

Một nhiệm vụ riêng của mã hóa là bảo vệ các thông điệp khỏi bị truy cập trái phép, bóp méo và phá hủy. Với kiểu mã hóa này, các thông điệp được mã hóa theo cách mà ngay cả khi nhận được chúng, kẻ tấn công sẽ không thể giải mã chúng. Quá trình của loại mã hóa thông điệp này được gọi là mã hóa (hoặc mã hóa), và quá trình giải mã được gọi là giải mã (hoặc giải mã). Bản thân thông điệp được mã hóa được gọi là mã hóa (hay đơn giản là mã hóa) và phương pháp mã hóa được sử dụng được gọi là mật mã.

Thông thường, các phương pháp mã hóa được phân biệt thành một lớp riêng biệt, cho phép xây dựng (không làm mất thông tin) mã thông báo có độ dài ngắn hơn so với thông báo gốc. Các kỹ thuật mã hóa như vậy được gọi là kỹ thuật nén hoặc đóng gói dữ liệu. Chất lượng nén được xác định bằng tỷ lệ nén, tỷ lệ này thường được đo bằng phần trăm và cho biết thông điệp được mã hóa ngắn hơn bao nhiêu phần trăm so với thông báo gốc.

Trong quá trình xử lý tự động thông tin bằng máy tính, theo quy luật, mã hóa số (kỹ thuật số) được sử dụng, và theo lẽ tự nhiên, câu hỏi đặt ra về việc biện minh cho hệ thống số đã sử dụng. Thật vậy, với việc giảm cơ số của hệ thống số, bảng chữ cái của các phần tử của các ký hiệu mã được đơn giản hóa, nhưng các ký hiệu mã được kéo dài ra. Mặt khác, cơ số của hệ thống số càng lớn thì số chữ số cần thiết để biểu thị một ký hiệu mã càng nhỏ, và do đó, thời gian truyền nó càng ít, nhưng với sự phát triển của cơ số của hệ thống số, các yêu cầu đối với các kênh liên lạc và các phương tiện kỹ thuật để nhận biết các tín hiệu sơ cấp tăng lên đáng kể tương ứng với các yếu tố khác nhau của các ký hiệu mã. Đặc biệt, mã của một số được viết trong hệ nhị phân dài hơn trung bình khoảng 3,5 lần so với mã thập phân. Vì trong tất cả các hệ thống xử lý thông tin, cần phải lưu trữ các mảng thông tin lớn dưới dạng thông tin số, một trong những tiêu chí thiết yếu để lựa chọn bảng chữ cái của các phần tử của các ký hiệu của mã số (tức là cơ sở của hệ thống số được sử dụng ) là giảm thiểu số lượng phần tử điện tử trong các thiết bị lưu trữ, cũng như tính đơn giản và độ tin cậy của chúng.

Khi xác định số lượng phần tử điện tử cần thiết để cố định từng phần tử của các ký hiệu mã, cần phải tiến hành từ giả định thực tế đã được chứng minh rằng điều này đòi hỏi số lượng phần tử điện tử đơn giản nhất (ví dụ, bóng bán dẫn) bằng với cơ sở của hệ thống số Một... Sau đó để lưu trữ trong một số thiết bị n các phần tử ký tự mã sẽ được yêu cầu NS phần tử điện tử:

M = a n. (2.1)

Số lượng lớn nhất các số riêng biệt có thể được ghi lại trong thiết bị này n:

N = a n.

Lấy logarit của biểu thức này và biểu diễn từ nó n chúng tôi nhận được:

n= ln n/ ln Một.

Chuyển đổi biểu thức (2.1) sang dạng

NS= một ∙ ln n/ ln Một(2.2)

có thể xác định được ở cơ sở nào của logarit Một số lượng nguyên tố NS sẽ là tối thiểu cho một n... Phân biệt bằng Một hàm số M = f (a) và cân bằng đạo hàm của nó bằng 0, chúng ta nhận được:

Rõ ràng, đối với bất kỳ Một

ln n/ ln 2 a ≠ 0

và do đó

ln Một - 1 = 0,

ở đâu a = e ≈ 2,7.

Vì cơ số chỉ có thể là một số nguyên, nên Mộtđược chọn bằng 2 hoặc 3. Ví dụ: chúng ta hãy đặt dung lượng tối đa của thiết bị lưu trữ n= 10 6 số. Sau đó, đối với các cơ sở khác nhau của hệ thống số ( Một) lượng phần tử ( NS) trong một thiết bị lưu trữ như vậy, theo biểu thức (2.2), như sau (Bảng 2.1):

Bảng 2.1.

Một
NS	39,2	38,2	39,2	42,9		91,2

Vì vậy, nếu chúng ta tiến hành từ việc giảm thiểu số lượng thiết bị, thì lợi thế nhất sẽ là hệ thống số nhị phân, bậc ba và bậc bốn, gần với tham số này. Nhưng do việc triển khai kỹ thuật của các thiết bị hoạt động trong hệ thống số nhị phân đơn giản hơn nhiều, nên phổ biến nhất trong mã hóa số là các mã dựa trên hệ thống số cơ sở 2.

Là một nhánh của lý thuyết thông tin nghiên cứu các cách xác định thông điệp bằng các tín hiệu phản ánh chúng. Nhiệm vụ của lý thuyết mã hóa là khớp nguồn thông tin với kênh truyền thông.

Đối tượng của mã hóa là thông tin rời rạc và liên tục đến với người tiêu dùng thông qua nguồn thông tin. Khái niệm mã hóa có nghĩa là chuyển đổi thông tin thành một dạng thuận tiện cho việc truyền tải qua một kênh truyền thông cụ thể.

Hoạt động ngược lại - giải mã - bao gồm việc khôi phục thông điệp đã nhận từ biểu mẫu mã hóa thành thông báo được chấp nhận chung có sẵn cho người tiêu dùng.

Có một số hướng trong lý thuyết mã hóa:

• mã hóa tĩnh hoặc hiệu quả;
• mã hóa chống nhiễu;
• mã hiệu chỉnh;
• mã tuần hoàn;
• mã số học.

Với sự ra đời của các hệ thống điều khiển, đặc biệt là máy tính, vai trò của mã hóa đã tăng lên và thay đổi đáng kể, vì việc truyền thông tin là không thể nếu không có mã hóa. Gần đây, cùng với sự phát triển của hệ thống viễn thông và việc sử dụng rộng rãi công nghệ máy tính để xử lý và lưu trữ thông tin, một lĩnh vực kiến ​​thức mới đã hình thành - an toàn thông tin.

Mã hóa là một cách phổ biến để hiển thị thông tin trong quá trình lưu trữ, xử lý và truyền dưới dạng một hệ thống tương ứng giữa các tín hiệu và các phần tử thông báo, với sự trợ giúp của các phần tử này có thể được sửa chữa.

Mã là một quy tắc để chuyển đổi một cách rõ ràng một thông điệp từ một dạng biểu tượng của một thông điệp sang một thông điệp khác, thường mà không làm mất thông tin.

Nếu tất cả các từ mã có cùng độ dài, thì mã đó được gọi là thống nhất, hoặc khối.

Theo một bảng chữ cái trừu tượng, chúng tôi muốn nói đến một tập hợp các ký hiệu rời rạc có trật tự.

Mã hóa bảng chữ cái. Bảng chữ cái, tức là từng chữ cái, bảng mã có thể được thiết lập bởi bảng mã. Trong thực tế, mã chuyển đổi là một số loại thay thế.

Trong đó bảng chữ cái A, tập hợp các từ được cấu tạo trong bảng chữ cái B. Tập hợp các mã chữ cái được gọi là tập hợp các mã sơ cấp. Mã hóa bảng chữ cái có thể được sử dụng cho bất kỳ bộ thông điệp nào.

Xử lý dữ liệu máy tính dựa trên việc sử dụng mã nhị phân. Phương pháp mã hóa phổ quát này phù hợp với mọi dữ liệu, bất kể nguồn gốc và nội dung của nó.

Mã hóa văn bản

Văn bản là chuỗi các ký tự có trong một bảng chữ cái nhất định. Mã hóa văn bản được rút gọn thành mã hóa nhị phân của bảng chữ cái trên cơ sở nó được xây dựng. Mã hóa byte được sử dụng phổ biến nhất của bảng chữ cái. Trong trường hợp này, số lượng tối đa của bảng chữ cái là 256 ký tự. Một bảng chữ cái như vậy có thể chứa hai bộ ký tự chữ cái (ví dụ: tiếng Nga và tiếng Latinh), số, dấu câu và dấu hiệu toán học, một khoảng trắng và một số nhỏ các ký tự bổ sung. Một ví dụ về bảng chữ cái như vậy là mã ASCII.

Tuy nhiên, bộ mã hạn chế gồm 256 ký tự không còn đáp ứng được nhu cầu liên lạc quốc tế ngày càng cao. Hệ thống mã hóa ký tự 16 bit phổ quát UNICODE đang trở nên phổ biến hơn.

Sức mạnh của bảng chữ cái trong hệ thống mã hóa UNICODE là 216 = 65 536 mã khác nhau, trong đó 63 484 mã tương ứng với các ký tự của hầu hết các bảng chữ cái, và 2048 mã còn lại được chia đôi và tạo thành một bảng 1024 cột x 1024 dòng . Có hơn một triệu ô trong bảng này, có thể chứa hơn một triệu ký tự khác nhau. Đây là những biểu tượng của ngôn ngữ "chết", cũng như những biểu tượng không có nội dung từ vựng, con trỏ, dấu hiệu, v.v. Các ký tự bổ sung này yêu cầu một cặp từ 16 bit (16 bit cho số dòng và 16 bit cho số cột).

Do đó, hệ thống UNICODE là một hệ thống mã hóa chung cho tất cả các ký hiệu của hệ thống chữ viết quốc gia và có khả năng mở rộng đáng kể.

Mã hóa hình ảnh

Bản vẽ, tranh, ảnh được mã hóa ở định dạng raster... Theo quan điểm này, mỗi hình ảnh là một bảng hình chữ nhật gồm các chấm màu. Màu sắc và độ sáng của từng điểm riêng biệt được thể hiện dưới dạng số, cho phép mã nhị phân được sử dụng để biểu diễn dữ liệu đồ họa.

Thông thường, thể hiện hình ảnh đen trắng trong thang độ xám; đối với điều này, mô hình GreyScale được sử dụng. Nếu độ chói của một chấm được mã hóa trong một byte, có thể sử dụng 256 tông màu xám khác nhau. Độ chính xác này phù hợp với độ nhạy của mắt người và khả năng của công nghệ in.

Khi mã hóa hình ảnh màu, nguyên tắc phân hủy màu sắc thành các thành phần được sử dụng; đối với điều này, mô hình RGB được sử dụng. Hình ảnh màu trên màn hình thu được bằng cách trộn ba màu cơ bản: đỏ (Red, R), xanh lam (Blue, B) và xanh lục (Green, G).

Mỗi pixel trên màn hình được tạo thành từ ba phần tử gần nhau phát sáng với những màu này.

Màn hình màu sử dụng nguyên tắc này được gọi là màn hình RGB.

Mã màu pixel chứa thông tin về tỷ lệ của mỗi màu cơ bản.

sơ đồ hình thành màu sắc

Nếu cả ba thành phần có cùng cường độ (độ sáng), thì có thể thu được 8 màu khác nhau từ sự kết hợp của chúng (23):

			màu nâu

Sự hình thành màu sắc ở độ sâu màu 24 bit:

Độ sâu màu càng lớn, phạm vi màu có sẵn càng rộng và sự thể hiện của chúng trong hình ảnh số hóa càng chính xác. Một pixel có độ sâu bit bằng một chỉ có 2 (ở mức đầu tiên) trạng thái có thể có - hai màu: đen hoặc trắng. Một pixel có độ sâu bit là 8 có 28 hoặc 256 giá trị màu có thể. Một pixel có độ sâu bit 24 đơn vị có 224 độ) hoặc 16,7 triệu giá trị có thể. Người ta tin rằng hình ảnh 24-bit, chứa 16,7 triệu màu, tái tạo chính xác màu sắc của thế giới xung quanh chúng ta. Thông thường, độ phân giải bit được chỉ định trong phạm vi từ 1 đến 48 bit / pixel.

Khi in trên giấy, một mô hình màu hơi khác được sử dụng: nếu màn hình phát ra ánh sáng, màu sắc thu được là kết quả của việc cộng các màu sắc, thì sơn hấp thụ ánh sáng, màu sắc bị trừ đi. Do đó, các loại sơn màu lục lam (Cyan, C), đỏ tươi (Magenta, M) và màu vàng (Yellow, Y) được sử dụng làm chủ đạo. Ngoài ra, do sự không hoàn hảo của thuốc nhuộm, một phần tư thường được thêm vào chúng - màu đen (đen, K). Để lưu trữ thông tin về mỗi lớp sơn, và trong trường hợp này, 1 byte thường được sử dụng nhất. Hệ thống mã hóa này được gọi là CMYK.

Biểu diễn màu thô hơn sử dụng ít bit hơn. Ví dụ, mã hóa đồ họa màu với số 16 bit được gọi là Màu cao. Trong trường hợp này, năm chữ số được gán cho mỗi màu.

Mã hóa âm thanh và video

Kỹ thuật làm việc với thông tin âm thanh mới nhất đã đến với công nghệ máy tính. Một phương pháp mã hóa phân tích áp dụng cho bất kỳ tín hiệu âm thanh nào dựa trên chuyển đổi tương tự sang kỹ thuật số. Tín hiệu tương tự gốc được biểu diễn dưới dạng một chuỗi các tín hiệu kỹ thuật số được ghi lại dưới dạng mã nhị phân. Bit chuyển đổi xác định lượng dữ liệu tương ứng với một tín hiệu kỹ thuật số duy nhất. Khi phát âm thanh, hãy thực hiện chuyển đổi ngược từ kỹ thuật số sang tương tự.

Phương pháp mã hóa này có một lỗi, do đó tín hiệu được tái tạo hơi khác so với bản gốc.

Phương pháp mã hóa tổng hợp dạng bảng chỉ có thể áp dụng cho một bản nhạc. Các mẫu (sample) âm thanh của nhiều loại nhạc cụ khác nhau được lưu trữ trong các bảng đã chuẩn bị sẵn. Các mã số xác định nhạc cụ, nốt nhạc và thời lượng.

Khi mã hóa tín hiệu video, bạn cần ghi lại một chuỗi hình ảnh (khung hình) và âm thanh (nhạc phim). Định dạng ghi video cho phép cả hai luồng dữ liệu được đưa vào một chuỗi kỹ thuật số.

04.04.2006 Leonid Chernyak Thể loại: Công nghệ

"Hệ thống mở" Việc tạo ra máy tính sẽ không thể thực hiện được nếu lý thuyết mã hóa tín hiệu không được tạo ra đồng thời với "sự xuất hiện của chúng. Lý thuyết mã hóa" là một trong những lĩnh vực toán học có ảnh hưởng đáng kể đến sự phát triển của máy tính.

"Hệ thống mở"

Việc tạo ra máy tính sẽ không thể thực hiện được nếu lý thuyết về mã hóa tín hiệu không được tạo ra đồng thời với sự xuất hiện của chúng.

Lý thuyết mã hóa là một trong những lĩnh vực toán học có ảnh hưởng rõ rệt đến sự phát triển của máy tính. Phạm vi của nó mở rộng đến việc truyền dữ liệu qua các kênh thực (hoặc nhiễu) và chủ đề là đảm bảo tính đúng đắn của thông tin được truyền. Nói cách khác, nó học cách tốt nhất để đóng gói dữ liệu để sau khi một tín hiệu đã được truyền đi, thông tin hữu ích có thể được trích xuất một cách đáng tin cậy và đơn giản từ dữ liệu. Đôi khi lý thuyết về mã hóa bị nhầm lẫn với mã hóa, nhưng điều này không đúng: mật mã giải quyết vấn đề ngược lại, mục đích của nó là gây khó khăn cho việc lấy thông tin từ dữ liệu.

Nhu cầu mã hóa dữ liệu lần đầu tiên xuất hiện cách đây hơn 150 năm, ngay sau khi phát minh ra máy điện báo. Các kênh này đắt tiền và không đáng tin cậy, khiến nhiệm vụ giảm thiểu chi phí và tăng độ tin cậy của việc truyền tải điện tín trở nên cấp thiết. Vấn đề càng trở nên trầm trọng hơn do việc đặt các dây cáp xuyên Đại Tây Dương. Kể từ năm 1845, những cuốn sách mật mã đặc biệt đã được đưa vào sử dụng; chúng được sử dụng bởi các nhà khai thác điện báo để "nén" các thông điệp theo cách thủ công, thay thế các chuỗi từ thông thường bằng các mã ngắn hơn. Đồng thời, để kiểm tra tính đúng đắn của đường truyền, họ bắt đầu sử dụng điều khiển chẵn lẻ, một phương pháp được sử dụng để kiểm tra tính đúng đắn của việc nhập thẻ đục lỗ cũng có trong máy tính thế hệ thứ nhất và thứ hai. Để làm điều này, một thẻ được chuẩn bị đặc biệt với tổng kiểm tra được đưa vào bộ bài đang được đưa vào. Nếu thiết bị đầu vào không đáng tin cậy lắm (hoặc bộ bài quá lớn) thì có thể xảy ra lỗi. Để sửa nó, quy trình nhập đã được lặp lại cho đến khi tổng kiểm tra được tính toán khớp với tổng kiểm tra được lưu trữ trên thẻ. Đề án này không chỉ khó xử, mà còn mắc lỗi kép. Với sự phát triển của các kênh truyền thông, cần phải có một cơ chế kiểm soát hiệu quả hơn.

Giải pháp lý thuyết đầu tiên cho vấn đề truyền dữ liệu qua các kênh nhiễu được đề xuất bởi Claude Shannon, người sáng lập lý thuyết thống kê về thông tin. Shannon là ngôi sao trong thời đại của ông, ông là một trong những học giả ưu tú của Hoa Kỳ. Là một nghiên cứu sinh của Vannevar Bush, năm 1940, ông đã nhận được giải Nobel (đừng nhầm lẫn với giải Nobel!), Được trao cho các nhà khoa học dưới 30 tuổi. Khi làm việc tại Bell Labs, Shannon đã viết Lý thuyết toán học về truyền thông điệp (1948), nơi ông chỉ ra rằng nếu băng thông của kênh cao hơn entropy của nguồn thông điệp, thì thông điệp có thể được mã hóa để nó được truyền đi. không thể trì hoãn quá mức. Kết luận này nằm trong một trong những định lý được Shannon chứng minh, ý nghĩa của nó rút ra từ thực tế là nếu có một kênh có đủ băng thông, một thông điệp có thể được truyền với một số thời gian trễ. Ngoài ra, ông đã chỉ ra khả năng lý thuyết của việc truyền đáng tin cậy khi có nhiễu trong kênh. Công thức C = W log ((P + N) / N), được khắc trên một tượng đài khiêm tốn của Shannon, được dựng lên ở quê hương của ông ở Michigan, được so sánh về giá trị với công thức E = mc 2 của Albert Einstein.

Các công trình của Shannon đã mang lại nguồn gốc cho rất nhiều nghiên cứu sâu hơn trong lĩnh vực lý thuyết thông tin, nhưng chúng không có ứng dụng kỹ thuật thực tế. Sự chuyển đổi từ lý thuyết sang thực hành được thực hiện nhờ nỗ lực của Richard Hamming, một đồng nghiệp của Shannon tại Bell Labs, người đã trở nên nổi tiếng với việc khám phá ra một loại mã được gọi là "mã Hamming." Có một truyền thuyết cho rằng việc phát minh ra mã Hamming của họ được thúc đẩy bởi sự bất tiện khi làm việc với các thẻ đục lỗ trên máy tính chuyển tiếp Bell Model V vào giữa những năm 40. Anh được giao thời gian làm việc trên máy vào cuối tuần khi không có người điều khiển, còn bản thân anh thì phải loay hoay nhập liệu. Có thể như vậy, nhưng Hamming đề xuất các mã có thể sửa lỗi trong các kênh giao tiếp, bao gồm cả đường truyền dữ liệu trong máy tính, chủ yếu giữa bộ xử lý và bộ nhớ. Các mã Hamming cung cấp bằng chứng về cách các khả năng được chỉ ra bởi các định lý của Shannon có thể được thực hiện trên thực tế.

Hamming xuất bản bài báo của mình vào năm 1950, mặc dù lý thuyết mã hóa của ông có từ năm 1947 trong các báo cáo nội bộ. Do đó, một số người tin rằng Hamming nên được coi là cha đẻ của lý thuyết mã hóa, chứ không phải Shannon. Tuy nhiên, thật vô ích nếu tìm kiếm cái cũ trong lịch sử công nghệ.

Điều chắc chắn là Hamming là người đầu tiên đề xuất Mã sửa lỗi (ECC). Các sửa đổi hiện đại của các mã này được sử dụng trong tất cả các hệ thống lưu trữ dữ liệu và để trao đổi giữa bộ xử lý và bộ nhớ chính. Một trong những biến thể của chúng, mã Reed-Solomon được sử dụng trong đĩa CD, cho phép bạn phát các bản ghi mà không có tiếng kêu và tiếng ồn có thể gây trầy xước và các hạt bụi. Có nhiều phiên bản mã dựa trên Hamming, chúng khác nhau về thuật toán mã hóa và số lượng bit kiểm tra. Những mã như vậy có tầm quan trọng đặc biệt liên quan đến sự phát triển của liên lạc không gian đường dài với các trạm liên hành tinh, ví dụ, có mã Reed-Muller, trong đó có 32 bit điều khiển cho bảy bit thông tin hoặc 26 cho sáu.

Trong số các mã ECC mới nhất là mã LDPC (Mã kiểm tra tính chẵn lẻ mật độ thấp). Trên thực tế, chúng đã được biết đến trong ba mươi năm, nhưng sự quan tâm đặc biệt đối với chúng đã được bộc lộ chính xác trong những năm gần đây, khi truyền hình độ nét cao bắt đầu phát triển. Mã LDPC không chính xác 100%, nhưng tỷ lệ lỗi có thể được điều chỉnh đến mức mong muốn và băng thông được sử dụng nhiều nhất có thể. Gần với chúng là "Mã Turbo", chúng hiệu quả khi làm việc với các đối tượng trong không gian sâu và băng thông hạn chế.

Tên của Vladimir Aleksandrovich Kotelnikov đã được khắc sâu trong lịch sử lý thuyết mã hóa. Năm 1933, trong "Tài liệu về liên lạc vô tuyến cho Đại hội Liên minh lần thứ nhất về việc tái thiết kỹ thuật thông tin liên lạc", ông đã xuất bản tác phẩm "Trên băng thông của không khí?" và? dây? " Tên của Kotelnikov, như một bình đẳng, được đưa vào tiêu đề của một trong những định lý quan trọng nhất của lý thuyết mã hóa. Định lý này xác định các điều kiện mà tín hiệu đã truyền có thể được khôi phục mà không bị mất thông tin.

Định lý này được gọi bằng nhiều tên khác nhau, bao gồm cả "định lý WKS" (từ viết tắt WKS được lấy từ Whittaker, Kotelnikov, Shannon). Một số nguồn sử dụng cả định lý lấy mẫu Nyquist-Shannon và định lý lấy mẫu Whittaker-Shannon, và trong các sách giáo khoa của trường đại học Nga, phổ biến nhất chỉ đơn giản là “định lý Kotelnikov”. Trên thực tế, định lý này có lịch sử lâu đời hơn. Phần đầu tiên của nó đã được chứng minh vào năm 1897 bởi nhà toán học người Pháp Emile Borel. Edmund Whittaker đã đóng góp vào năm 1915. Năm 1920, Kinnosuki Ogura của Nhật đã công bố các sửa đổi cho nghiên cứu của Whittaker, và vào năm 1928, Harry Nyquist người Mỹ đã làm rõ các nguyên tắc số hóa và khôi phục tín hiệu tương tự.

Claude Shannon(1916 - 2001) từ những năm đi học đã thể hiện sự quan tâm như nhau đối với toán học và kỹ thuật điện. Năm 1932, ông vào Đại học Michigan, năm 1936 - tại Viện Công nghệ Massachusetts, từ đó ông tốt nghiệp năm 1940, nhận hai bằng - thạc sĩ kỹ thuật điện và tiến sĩ toán học. Năm 1941, Shannon gia nhập Phòng thí nghiệm Bell. Tại đây, ông bắt đầu phát triển những ý tưởng mà sau này là lý thuyết thông tin. Năm 1948, Shannon xuất bản một bài báo "Lý thuyết toán học về giao tiếp", nơi các ý tưởng cơ bản của nhà khoa học được hình thành, đặc biệt là việc xác định lượng thông tin thông qua entropy, và cũng đề xuất một đơn vị thông tin xác định sự lựa chọn của hai các tùy chọn có khả năng xảy ra như nhau, nghĩa là sau này được gọi là ... Năm 1957-1961, Shannon công bố các công trình mà ông đã chứng minh định lý về dung lượng của các kênh liên lạc ồn ào, hiện mang tên ông. Năm 1957, Shannon trở thành giáo sư tại Viện Công nghệ Massachusetts, nơi ông nghỉ hưu 21 năm sau đó. Vào ngày "nghỉ hưu xứng đáng", Shannon đã hoàn toàn đầu hàng với niềm đam mê tung hứng lâu đời của mình. Ông đã chế tạo một số máy tung hứng và thậm chí còn phát triển một lý thuyết chung về trò tung hứng.

Richard Hamming(1915 - 1998) bắt đầu học tại Đại học Chicago, nơi ông nhận bằng cử nhân vào năm 1937. Năm 1939, ông nhận bằng thạc sĩ tại Đại học Nebraska và bằng Tiến sĩ toán học tại Đại học Illinois. Năm 1945, Hamming bắt đầu làm việc như một phần của Dự án Manhattan, một dự án nghiên cứu quy mô lớn của chính phủ nhằm tạo ra bom nguyên tử. Năm 1946, Hamming đến làm việc tại Phòng thí nghiệm Điện thoại Bell, nơi ông làm việc với Claude Shannon. Năm 1976, Hamming nhận một ghế tại Trường Cao học Hải quân ở Monterey, California.

Công trình khiến ông trở nên nổi tiếng, nghiên cứu cơ bản về mã phát hiện và sửa lỗi, được xuất bản bởi Hamming vào năm 1950. Năm 1956, ông làm việc trên một trong những máy tính lớn đầu tiên của IBM 650. Công việc của ông đã đặt nền móng cho một ngôn ngữ lập trình sau này phát triển thành các ngôn ngữ lập trình cấp cao. Để ghi nhận những thành tựu của Hamming trong khoa học máy tính, IEEE đã lập Huy chương Dịch vụ Xuất sắc cho Tin học và Lý thuyết Hệ thống, được đặt theo tên của ông.

Vladimir Kotelnikov(1908 - 2005) năm 1926 vào Khoa Kỹ thuật Điện của Trường Kỹ thuật Cao cấp Matxcova mang tên N.E.Bauman (MVTU), nhưng đã tốt nghiệp Học viện Kỹ thuật Điện Matxcova (MEI), tách khỏi MVTU như một viện độc lập. Trong quá trình học sau đại học của mình (1931-1933) Kotelnikov đã lập công thức toán học và chứng minh "định lý đếm", sau này được đặt theo tên của ông. Sau khi tốt nghiệp cao học năm 1933, Kotelnikov, trong khi vẫn giảng dạy tại MPEI, đã đến làm việc tại Viện Nghiên cứu Khoa học Trung ương về Truyền thông (TsNIIS). Năm 1941, V.A.Kotelnikov đã đưa ra một tuyên bố rõ ràng về những yêu cầu mà một hệ thống không thể giải mã được về mặt toán học cần phải đáp ứng, và một bằng chứng về tính không thể giải mã của nó đã được đưa ra. Năm 1944, Kotelnikov nhận chức giáo sư, trưởng khoa kỹ thuật vô tuyến của MPEI, nơi ông làm việc cho đến năm 1980. Năm 1953, ở tuổi 45, Kotelnikov ngay lập tức được bầu làm thành viên chính thức của Viện Hàn lâm Khoa học Liên Xô. Từ năm 1968 đến 1990, V.A.Kotelnikov đồng thời là giáo sư, trưởng phòng của Viện Vật lý và Công nghệ Mátxcơva.

Sự ra đời của lý thuyết mã hóa

Lý thuyết mã hóa. Các loại mã hóa Các khái niệm cơ bản của lý thuyết mã hóa Trước đây, các công cụ mã hóa đóng vai trò bổ trợ và không được coi là một môn học riêng biệt của nghiên cứu toán học, nhưng với sự ra đời của máy tính, tình hình đã thay đổi hoàn toàn. Mã hóa thực sự tràn ngập công nghệ thông tin và là một vấn đề trọng tâm trong việc giải quyết nhiều (hầu như tất cả) các vấn đề lập trình: ۞ trình bày dữ liệu có tính chất tùy ý (ví dụ, số, văn bản, đồ họa) trong bộ nhớ máy tính; ۞ bảo vệ thông tin khỏi truy cập trái phép; ۞ đảm bảo khả năng chống nhiễu trong quá trình truyền dữ liệu qua các kênh truyền thông; ۞ nén thông tin trong cơ sở dữ liệu. Lý thuyết mã hóa là một nhánh của lý thuyết thông tin nghiên cứu các cách xác định thông điệp với các tín hiệu đại diện cho chúng. Mục tiêu: Phối hợp nguồn thông tin với kênh truyền thông. Đối tượng: Thông tin rời rạc hoặc liên tục đến với người tiêu dùng thông qua một nguồn thông tin. Mã hóa là sự biến đổi thông tin thành một công thức thuận tiện cho việc truyền tải qua một kênh truyền thông cụ thể. Một ví dụ về mã hóa trong toán học là phương pháp tọa độ được giới thiệu bởi Descartes, cho phép nghiên cứu các đối tượng hình học thông qua biểu thức phân tích của chúng dưới dạng số, chữ cái và tổ hợp - công thức của chúng. Khái niệm mã hóa có nghĩa là chuyển đổi thông tin thành một dạng thuận tiện cho việc truyền tải qua một kênh truyền thông cụ thể. Giải mã - khôi phục một tin nhắn đã nhận từ một biểu mẫu đã được mã hóa thành một biểu mẫu có sẵn cho người tiêu dùng.

Chủ đề 5.2. Mã hóa bảng chữ cái Nhìn chung, vấn đề mã hóa có thể được biểu diễn như sau. Giả sử có hai bảng chữ cái A và B, bao gồm một số hữu hạn các ký hiệu: và. Các yếu tố của bảng chữ cái được gọi là các chữ cái. Một tập hợp có thứ tự trong bảng chữ cái A sẽ được gọi là một từ, trong đó nó được ký hiệu là n = l () = | | , số n thể hiện số lượng chữ cái trong từ và được gọi là độ dài của từ, Một từ rỗng được ký hiệu: Đối với một từ, chữ a1 được gọi là đầu, hoặc tiền tố của từ, chữ an là phần cuối hoặc hậu tố của từ. , và Các từ có thể được kết nối. Để làm được điều này, tiền tố của từ thứ hai phải ngay sau tiền tố của từ đầu tiên, trong khi ở từ mới, chúng tự nhiên bị mất trạng thái, trừ khi một trong các từ trống. Sự kết nối của các từ và được chỉ ra, sự kết nối của n từ giống nhau được chỉ ra, hơn thế nữa. Tập hợp tất cả các từ không rỗng của bảng chữ cái A sẽ được ký hiệu là A *: Tập hợp A được gọi là bảng chữ cái của thông điệp, và tập hợp B được gọi là bảng chữ cái mã hóa. Tập hợp các từ được cấu tạo trong bảng chữ cái B sẽ được ký hiệu là B *.

Chúng ta ký hiệu F là ánh xạ của các từ từ bảng chữ cái A sang bảng chữ cái B. Khi đó từ đó được gọi là mã của từ. Mã hóa là một cách phổ biến để hiển thị thông tin trong quá trình lưu trữ, truyền và xử lý thông tin dưới dạng một hệ thống tương ứng giữa các phần tử thông điệp và tín hiệu, với sự trợ giúp của các phần tử này có thể được cố định. Do đó, mã là một quy tắc để chuyển đổi rõ ràng (tức là một chức năng) của một thông điệp từ một dạng biểu diễn tượng trưng (bảng chữ cái gốc A) sang một dạng khác (bảng chữ cái đối tượng B), thường mà không làm mất thông tin. Quá trình chuyển đổi F: A * B * → các từ của bảng chữ cái gốc A thành bảng chữ cái B được gọi là mã hóa thông tin. Quá trình chuyển đổi một từ trở lại được gọi là giải mã. Do đó, giải mã là hàm nghịch đảo của F, tức là F1. to word Vì đối với bất kỳ mã hóa nào, hoạt động giải mã phải được thực hiện, nên ánh xạ phải có thể đảo ngược (bijection). Nếu | B | = m, thì F được gọi là mã hóa thứ m, trường hợp phổ biến nhất là mã hóa nhị phân B = (0, 1). Đó là trường hợp này được xem xét trong những gì sau đây. Nếu tất cả các từ mã có cùng độ dài, thì mã đó được gọi là thống nhất, hoặc khối. Có thể chỉ định mã hóa theo bảng chữ cái (hoặc từng chữ cái) bằng một bảng mã. Một số loại thay thế sẽ đóng vai trò như một mã hoặc chức năng mã hóa. Sau đo ở đâu,. Việc mã hóa từng chữ cái như vậy được ký hiệu là một tập hợp các mã cơ bản. Mã hóa bảng chữ cái có thể được sử dụng cho bất kỳ bộ thông điệp nào. Do đó, mã hóa bảng chữ cái là đơn giản nhất và luôn có thể được nhập trên các bảng chữ cái không trống. ... Nhiều mã chữ cái

VÍ DỤ Cho các bảng chữ cái A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) B = (0, 1) được cho. Sau đó, bảng mã hóa có thể là một thay thế:. Đây là một mã hóa thập phân nhị phân, nó là một-một và do đó có thể được giải mã. Tuy nhiên, kế hoạch này không phải là 1-1. Ví dụ: một tập hợp sáu từ 111111 có thể khớp với từ 333 hoặc 77, hoặc 111111, 137, 3311 hoặc 7111 cộng với bất kỳ hoán vị nào. Sơ đồ mã hóa theo bảng chữ cái được gọi là tiền tố nếu mã cơ bản của một chữ cái không phải là tiền tố của mã cơ bản của chữ cái khác. Một lược đồ mã hóa theo bảng chữ cái được gọi là có thể phân tách được nếu bất kỳ từ nào bao gồm các mã cơ bản có thể được phân tách duy nhất thành các mã cơ bản. Việc mã hóa bảng chữ cái với một lược đồ có thể phân tách cho phép giải mã. Có thể chứng minh rằng lược đồ tiền tố có thể phân tách được. Để một sơ đồ mã hóa chữ cái có thể phân tách được, độ dài của các mã cơ bản phải thỏa mãn một quan hệ được gọi là bất đẳng thức Macmillan. Bất đẳng thức Macmillan nếu Lược đồ mã hóa theo bảng chữ cái

có thể phân tách được, thì bất đẳng thức là đúng VÍ DỤ Lược đồ mã hóa theo thứ tự chữ cái A = (a, b) và B = (0, 1), có thể phân tách được, vì, và do đó, bất đẳng thức Macmillan là đúng. mã cơ bản của chữ a là tiền tố của mã cơ bản của chữ b. Chủ đề 5.3. Mã dự phòng tối thiểu Trong thực tế, điều quan trọng là mã thông báo càng ngắn càng tốt. Mã hóa bảng chữ cái phù hợp với bất kỳ thông điệp nào, nhưng nếu không biết gì về tập hợp tất cả các từ của bảng chữ cái A, thì rất khó để hình thành bài toán tối ưu hóa một cách chính xác. Tuy nhiên, trong thực tế, thông tin bổ sung thường có sẵn. Ví dụ, đối với các thông báo được trình bày bằng ngôn ngữ tự nhiên, thông tin bổ sung đó có thể là phân phối xác suất của các chữ cái xuất hiện trong thông báo. Sau đó, vấn đề xây dựng một mã tối ưu thu được một công thức toán học chính xác và một giải pháp nghiêm ngặt.

Hãy cho một số sơ đồ mã hóa theo thứ tự bảng chữ cái có thể phân tách được. Khi đó, bất kỳ lược đồ nào trong đó tập hợp có thứ tự là một hoán vị của tập hợp có thứ tự cũng sẽ có thể phân tách được. Trong trường hợp này, nếu độ dài của bộ mã cơ bản bằng nhau, thì hoán vị của chúng trong lược đồ không ảnh hưởng đến độ dài của thông điệp được mã hóa. Trong trường hợp độ dài của các mã cơ bản khác nhau, thì độ dài của mã tin nhắn trực tiếp phụ thuộc vào các mã cơ bản được gán cho các chữ cái nào và vào thành phần của các chữ cái trong tin nhắn. Nếu một thông điệp cụ thể và một sơ đồ mã hóa cụ thể được chỉ định, thì một hoán vị của các mã như vậy có thể được chọn, trong đó độ dài của mã thông báo sẽ là nhỏ nhất. Thuật toán gán mã cơ bản, trong đó độ dài của mã của một thông điệp cố định S sẽ nhỏ nhất đối với một lược đồ cố định: ۞ sắp xếp các chữ cái theo thứ tự giảm dần của số lần xuất hiện; ۞ sắp xếp các mã cơ bản theo thứ tự độ dài tăng dần; ۞ đặt các mã phù hợp với các chữ cái theo cách quy định. Giả sử bảng chữ cái và xác suất của các chữ cái xuất hiện trong tin nhắn được đưa ra:

Trong đó pi là xác suất xuất hiện của chữ cái ai, và các chữ cái có xác suất xuất hiện bằng 0 trong thông báo bị loại trừ và các chữ cái được sắp xếp theo thứ tự giảm dần xác suất xuất hiện của chúng. Thông báo, được chỉ định và định nghĩa là VÍ DỤ. Đối với lược đồ mã hóa theo thứ tự bảng chữ cái có thể phân tách A = (a, b), B = (0,1), với phân phối xác suất, chi phí mã hóa là và với phân phối xác suất, chi phí mã hóa là

Chủ đề 5.4. Mã hóa Huffman Thuật toán này được phát minh vào năm 1952 bởi David Huffman. Chủ đề 5.5. Mã số học Cũng giống như thuật toán Huffman, tất cả đều bắt đầu với một bảng các phần tử và các xác suất tương ứng. Giả sử bảng chữ cái đầu vào chỉ bao gồm ba phần tử: a1, a2 và a3, đồng thời P (a1) = 1/2 P (a2) = 1/3 P (a3) ​​= 1/6 Giả sử rằng chúng ta cần mã hóa dãy a1, a1, a2, a3. Chúng tôi chia khoảng thời gian, trong đó p là một số cố định, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

một ca và một yếu tố chính và sửa một lỗi có thứ tự (so sánh với (2)). Như một toán học. Mô hình bộ mã hóa và bộ giải mã thường được xem xét từ sơ đồ của các phần tử chức năng và độ phức tạp được hiểu là số lượng phần tử trong mạch. Đối với các lớp mã đã biết có sửa lỗi, một nghiên cứu về các thuật toán có thể có cho các thuật toán và thuật toán được thực hiện và thu được các giới hạn trên cho độ phức tạp của bộ mã hóa và bộ giải mã. Một số mối quan hệ cũng đã được tìm thấy giữa tốc độ truyền mã hóa, khả năng chống nhiễu mã hóa và độ phức tạp của bộ giải mã (xem). Một hướng nghiên cứu khác trong lý thuyết mã hóa có liên quan đến thực tế là nhiều kết quả (ví dụ, định lý Shannon và giới hạn (3)) không mang tính "xây dựng", mà đại diện cho các định lý về sự tồn tại của chuỗi vô hạn mã (Kn) để chứng minh những kết quả này dẫn đến lớp các chuỗi mã như vậy (K n), trong đó có một máy Turing nhận ra rằng một từ tùy ý có độ dài l thuộc một tập hợp tại một thời điểm và có thứ tự phát triển chậm hơn đối với l ( ví dụ: llog l). Một số cấu trúc và phương pháp mới để đạt được giới hạn, được phát triển trong lý thuyết mã hóa, đã dẫn đến tiến bộ đáng kể trong các câu hỏi mà thoạt nhìn, rất xa so với các vấn đề truyền thống của lý thuyết mã hóa. Ở đây, cần chỉ ra việc sử dụng mã cực đại với việc sửa một lỗi trong một phương pháp tiệm cận tối ưu để thực hiện các chức năng của đại số logic bằng các mạch tiếp xúc; về nguyên tắc, cải thiện giới hạn trên đối với mật độ đóng gói của một re -không gian Euclide có chiều bởi các viên bi bằng nhau; về việc sử dụng bất đẳng thức (1) khi ước tính độ phức tạp của việc thực hiện bằng các công thức của một lớp hàm của đại số logic. Các ý tưởng và kết quả của lý thuyết mã hóa tìm thấy sự phát triển hơn nữa của chúng trong các vấn đề tổng hợp các mạch tự sửa chữa và các mạch đáng tin cậy từ các phần tử không đáng tin cậy. Lít .: Shannon K., Làm việc về lý thuyết thông tin và điều khiển học, trans. từ tiếng Anh., M., 1963; Berlekamp E., Lý thuyết mã hóa đại số, trans. từ tiếng Anh, M., 1971; Peterson, W., Weldon, E., Mã sửa lỗi, trans. từ tiếng Anh, xuất bản lần thứ 2, M., 1976; Toán học rời rạc và các vấn đề toán học của điều khiển học, v.1, Moscow, 1974, phần 5; Bassalygo L. A., Zyablov V. V., Pinsker M. S, "Probl. Truyền thông tin", 1977, câu 13, số 3, tr. 517; [V] Sidelnikov VM, "Mat. Sb.", 1974, tập 95, v. 1, tr. 148 58. V. I. Levenshtein.

Bách khoa toàn thư về Toán học. - M .: Bách khoa toàn thư Liên Xô. I. M. Vinogradov. Năm 1977-1985.  KÍCH THÍCH THUẬT TOÁN  COEUCLIDE SPACE Xem thêm trong các từ điển khác:  DECODING - xem Mã hóa và giải mã ... Encyclopedia of Mathematics  Mã hóa thông tin âm thanh - Bài viết này nên được wiki hóa. Vui lòng điền vào nó theo các quy tắc định dạng bài viết. Mã hóa âm thanh bằng PC dựa trên quá trình chuyển đổi dao động không khí thành dao động điện ... Ảnh mã Wikipedia), cam kết theo định nghĩa. quy tắc, tổng hợp thành rykh được gọi. mật mã K., ... ... Từ điển Bách khoa Triết học  GIẢI MÃ THÔNG TIN - thiết lập sự tương ứng giữa các phần tử thông điệp và tín hiệu, với sự trợ giúp của các phần tử này có thể được sửa chữa. Gọi B, tập hợp các phần tử của thông điệp, A là bảng chữ cái với các ký hiệu, Gọi dãy hữu hạn các ký hiệu. word in ... ... Bách khoa toàn thư vật lý  MÃ TỐI ƯU - (trong tâm lý học kỹ thuật) (mã hóa tối ưu tiếng Anh) tạo ra các mã đảm bảo tốc độ tối đa và độ tin cậy của việc nhận và xử lý thông tin về một đối tượng điều khiển bởi người vận hành (xem Tiếp nhận thông tin, giải mã). Bài toán của K. o. ... ... Bách khoa toàn thư tâm lý lớn  DECODING (trong tâm lý học kỹ thuật) - (xem Coding ... ... Từ điển bách khoa tâm lý lớn

 Giải mã - khôi phục một thông điệp được mã hóa bởi các tín hiệu truyền và nhận (xem phần Mã hóa) ... Từ điển Kinh tế và Toán học  KÍCH THƯỞNG - ENCODING. Một trong những giai đoạn tạo ra lời nói, trong khi “giải mã” là tiếp nhận và diễn giải, là quá trình hiểu một thông điệp lời nói. Xem ngôn ngữ học tâm lý ... Từ điển mới về các thuật ngữ và khái niệm phương pháp luận (lý thuyết và thực hành giảng dạy ngôn ngữ)  CODING - (Mã hóa tiếng Anh). 1. Chuyển đổi tín hiệu từ dạng năng lượng này sang dạng năng lượng khác 2. Chuyển đổi hệ thống tín hiệu hoặc dấu hiệu này sang hệ thống tín hiệu hoặc dấu hiệu khác, thường còn được gọi là "chuyển mã", "thay đổi mã" (đối với lời nói, "dịch"). 3. K. (mnemonic) ... ... Big Encyclopedia of Psychology  Giải mã - Bài viết này nói về mã trong lý thuyết thông tin, để biết các nghĩa khác của từ này, hãy xem mã (nghĩa). Mã là một quy tắc (thuật toán) để đối sánh từng thông điệp cụ thể với sự kết hợp được xác định chặt chẽ của các ký hiệu (dấu hiệu) (hoặc tín hiệu). Còn được gọi là mã ... ... Mã hóa tối ưu Cùng một thông điệp có thể được mã hóa theo nhiều cách khác nhau. Được mã hóa tối ưu sẽ được coi là mã trong đó thời gian tối thiểu dành cho việc truyền thông điệp. Nếu việc truyền mỗi ký hiệu cơ bản (0 hoặc 1) mất cùng thời gian, thì mã tối ưu sẽ là mã có độ dài tối thiểu có thể. Ví dụ 1. Cho một biến ngẫu nhiên X (x1, x2, x3, x4, x5, x6, x7, x8), có tám trạng thái với phân phối xác suất. 000, 001, 010, 011, 100, 101, 110 , 111 Để trả lời mã này có tốt hay không, bạn cần so sánh nó với giá trị tối ưu, nghĩa là xác định entropy

Sau khi xác định độ dư thừa L theo công thức L = 1H / H0 = 12,75 / 3 = 0,084, ta thấy rằng có thể giảm độ dài mã đi 8,4%. Câu hỏi đặt ra: liệu có thể soạn một đoạn mã mà trung bình một chữ cái sẽ có ít ký tự cơ bản hơn. Mã như vậy tồn tại. Đây là mã ShannonFano và Huffman. Nguyên tắc xây dựng mã tối ưu: 1. Mỗi ký hiệu sơ cấp phải mang lượng thông tin tối đa, vì vậy, các ký hiệu sơ cấp (0 và 1) trong văn bản được mã hóa xảy ra bình thường như nhau. Entropy trong trường hợp này sẽ là cực đại. 2. Cần gán các từ mã ngắn hơn của bảng chữ cái phụ cho các chữ cái của bảng chữ cái chính, các từ này có xác suất cao.