Lý thuyết mã hóa

Nguyên lý

Entrôpi của nguồn là một đo đạc về tin tức. Căn bản mà nói, mã của nguồn được dùng để loại bỏ những phần thừa, không cần thiết còn tồn trong nguồn, để lại phần nguồn với số lượng bit ít hơn, nhưng với nhiều tin tức hơn.
Mỗi loại mã hóa nguồn sử dụng một kỹ thuật khác nhau hòng đạt được giới hạn entrôpi của nguồn. , trong đó  là entrôpi của nguồn (tần số bit), và  là tần số bit sau khi số liệu đã được nén. Cụ thể là, không có phương pháp mã hóa nguồn nào có thể tốt hơn giới hạn entrôpi của ký hiệu (the entropy limit of the symbol).

Ví dụ

Truyền thông bản sao FAX dùng một kỹ thuật đơn giản là trường đạc mã (run-length code).

Mã kết hợp

Mã kết hợp (Convolutional codes) được sử dụng trong các modem dải tần âm (voiceband modems) (V.32, V.17, V.34) và trong các điện thoại di động GSM, cũng như trong các thiết bị truyền thông của quân đội vũ trang và trong các thiết bị truyền thông với vệ tinh.
Ý định ở đây là làm cho tất cả các ký hiệu mã ký (codeword symbol) trở thành tổng trọng số (weighted sum) của nhiều loại ký hiệu thông điệp trong nhập liệu (various input message symbols). Nó tương tự như toán kết hợp được dùng trong các hệ tuyến tính bất biến (linear time invariant systems) để dùng tìm xuất liệu (output) của một hệ thống, khi chúng ta biết nhập liệu (input) và các đáp ứng xung (impulse response).
Nói chung chúng ta tìm xuất liệu của bộ mã hóa kết hợp hệ (system convolutional encoder), tức sự kết hợp của nhập liệu bit, đối chiếu với trạng thái của bộ mã hóa kết hợp (convolution encoder), hoặc trạng thái của các thanh biến (registers).
Về cơ bản mà nói, mã kết hợp không giúp thêm gì trong việc chống nhiễu hơn một mã khối tương ứng. Trong nhiều trường hợp, chúng nói chung cho chúng ta một phương pháp thực thi đơn giản hơn, hơn hẳn một mã khối có hiệu quả tương ứng (a block code of equal power). Bộ mã hóa thường là một mạch điện đơn giản, có một bộ nhớ (state memory), một vài biện pháp truyền thông tin phản hồi báo tình hình (some feedback logic), thường là các cổng loại trừ XOR (XOR gates). Bộ mã hóa có thể được thực thi trong phần mềm hay phần sụn (firmware).
Thuật toán Viterbi (Viterbi algorithm) là một thuật toán ngắn gọn nhất (optimum algorithm) được dùng để giải mã các mã kết hợp. Hiện có những phương pháp giảm ước giúp vào việc giảm khối lượng tính toán phải làm. Những phương pháp này phần lớn dựa vào việc tìm tuyến đường có khả năng xảy ra cao nhất (most likely paths). Tuy không ngắn gọn, song trong môi trường nhiễu thấp hơn, người ta thường thấy chúng cho những kết quả khả quan. Các bộ điều hành vi xử lý hiện đại (Modern microprocessors) có khả năng thực hiện những thuật toán tìm giảm ước nói trên với tỷ lệ trên 4000 mã ký trong một giây.

Các ứng dụng của lý thuyết mã hóa

Một quan tâm khác của lý thuyết mã hóa là việc thiết kế các mã giúp vào việc đồng bộ hóa (synchronization). Một mã có thể được thiết kế để phát hiện dịch pha sóng điện (phase shift) và sửa lỗi, đồng thời cho phép nhiều tín hiệu (multiple signals) được truyền gửi trên cùng một kênh. Có một hạng loại của những mã mà chúng ta hằng ngày thường gặp trong các điện thoại di động của mình. Chúng được gọi là mã Đa truy nhập phân chia theo mã (Code Division Multiple Access - viết tắt là CDMA). Chi tiết về chúng thuộc phạm vi bên ngoài cuộc đàm luận ở đây, song nói một cách ngắn gọn, mỗi cái điện thoại được gắn cho một mã ký (codeword) lấy ra từ một hạng đặc biệt (special class) (ngành Đại Số). Trong khi truyền thông, mã ký được dùng để xáo trộn các bit đại biểu cho thông điệp âm thanh (voice message). Tại máy thu, một quy trình giải xáo trộn ("descrambling") được tiến hành để giải mã (decipher) thông điệp. Đặc tính của hạng mã ký này cho phép nhiều người dùng (với các mã khác nhau) sử dụng cùng một kênh truyền rađiô trong cùng một lúc. Máy thu, dùng chu trình giải xáo trộn, chỉ "nghe" thấy những người gọi khác như "nhiễu âm" ở độ thấp mà thôi.
Một hạng mã nổi tiếng khác nữa là mã Yêu cầu lặp lại tự động (Automatic Repeat reQuest - viết tắt là ARQ). Trong hạng phổ quát (general class) này, máy phát cho thêm các bit chẵn lẻ kiểm tra (parity check bits) vào các thông điệp dài hơn bình thường. Máy thu kiểm tra bit chẵn lẻ của thông điệp thu được và nếu nó phát hiện ra một sự bất đồng, nó sẽ yêu cầu máy phát truyền tin lại thông điệp. Hầu hết các mạng diện rộng (wide area networks) và các giao thức, ngoại trừ những cái hết sức đơn giản, đều sử dụng tái truyền thông ARQ. Những giao thức thông dụng bao gồm SDLC (IBM), TCP (Internet), X.25 (Quốc tế) và nhiều cái khác nữa. Hiện có nhiều nghiên cứu trên phạm vi rộng trong lĩnh vực về đề tài này do khó khăn trong việc so sánh giữa một gói dữ liệu đã bị từ bỏ (rejected packet) với một gói dữ liệu mới. Gói dữ liệu mới đến này là một gói mới hay là một gói cũ được truyền lại? Thường thì các hệ thống đánh số được sử dụng, tuy nhiên trong một số mạng truyền thông, gói dữ liệu có thể có một định danh khác, hoặc vấn đề này được dành lại cho tầng cao hơn (của giao thức) để nó yêu cầu truyền thông lại. TCP/IP là một giao thức điển hình sử dụng cả hai kỹ thuật. Trong bối cảnh đã kết nối, TCP/IP dành việc truyền thông lại cho mạng lưới truyền thông, và vì thế nó sử dụng mã hóa ARQ. Trong mạng lưới vô tuyến (wireless network), người ta không sử dụng ARQ. Thay vào đó, người ta dành trách nhiệm này cho chương trình ứng dụng kiểm nghiệm gói dữ liệu và yêu cầu việc truyền thông lại khi cần. Việc này có thể nâng cao lên đến mức độ đòi hỏi người dùng phải ấn nút "nạp lại" ("refresh" button) trên một trình duyệt web. Song, ngay cả cái này hiện nay vẫn ở trong hạng ARQ đang được nghiên cứu; người dùng bắt buộc phải can thiệp (the user just has to become involved).