Định lý mã hóa nguồn
Mã được tạo ra bởi một nguồn không có bộ nhớ rời rạc, phải được trình bày một cách hiệu quả, đây là một vấn đề quan trọng trong truyền thông. Để điều này xảy ra, có các từ mã, đại diện cho các mã nguồn này.
Ví dụ, trong điện báo, chúng tôi sử dụng mã Morse, trong đó các bảng chữ cái được ký hiệu bằng Marks và Spaces. Nếu lá thưE được coi là được sử dụng chủ yếu, nó được ký hiệu là “.” Trong khi lá thư Q mà hiếm khi được sử dụng, được biểu thị bằng “--.-”
Chúng ta hãy xem sơ đồ khối.
Ở đâu Sk là đầu ra của nguồn không có bộ nhớ rời rạc và bk là đầu ra của bộ mã hóa nguồn được đại diện bởi 0s và 1s.
Trình tự được mã hóa sao cho nó được giải mã thuận tiện tại máy thu.
Giả sử rằng nguồn có bảng chữ cái với k các ký hiệu khác nhau và kth Biểu tượng Sk xảy ra với xác suất Pk, Ở đâu k = 0, 1…k-1.
Để từ mã nhị phân được gán cho ký hiệu Sk, bởi bộ mã hóa có độ dài lk, được đo bằng bit.
Do đó, chúng tôi xác định độ dài từ mã trung bình L của bộ mã hóa nguồn là
$$ \ overline {L} = \ displaystyle \ sum \ limit_ {k = 0} ^ {k-1} p_kl_k $$
L đại diện cho số bit trung bình trên mỗi ký hiệu nguồn
Nếu $ L_ {phút} = \: tối thiểu \: có thể \: giá trị \: của \: \ overline {L} $
Sau đó coding efficiency có thể được định nghĩa là
$$ \ eta = \ frac {L {min}} {\ overline {L}} $$
Với $ \ overline {L} \ geq L_ {min} $, chúng ta sẽ có $ \ eta \ leq 1 $
Tuy nhiên, bộ mã hóa nguồn được coi là hiệu quả khi $ \ eta = 1 $
Đối với điều này, giá trị $ L_ {min} $ phải được xác định.
Chúng ta hãy tham khảo định nghĩa, “Cho một nguồn entropy $ H (\ delta) $ rời rạc, không có bộ nhớ, độ dài từ mã trung bìnhL đối với bất kỳ mã hóa nguồn nào được giới hạn là $ \ overline {L} \ geq H (\ delta) $. "
Nói cách đơn giản hơn, từ mã (ví dụ: mã Morse cho từ QUEUE là -.- ..-. ..-.) Luôn lớn hơn hoặc bằng mã nguồn (ví dụ: QUEUE). Có nghĩa là, các ký hiệu trong từ mã lớn hơn hoặc bằng các bảng chữ cái trong mã nguồn.
Do đó, với $ L_ {min} = H (\ delta) $, hiệu quả của bộ mã hóa nguồn theo Entropy $ H (\ delta) $ có thể được viết là
$$ \ eta = \ frac {H (\ delta)} {\ overline {L}} $$
Định lý mã hóa nguồn này được gọi là noiseless coding theoremvì nó thiết lập một mã hóa không có lỗi. Nó còn được gọi làShannon’s first theorem.