Tiểu Luận Khảo sát mã hóa nguồn tin và mã hamming

PHẦN 1 : MÃ HÓA NGUỒN TIN
I. KHÁI QUÁT VỀ MÃ

1. CácThông Số Mã
Cơsố mã : + là số ký hiệu mã trong bộ chữ mã
+ Ký hiệu : m
+ Ví dụ :mã thập phân ( m=10 ) ; mã nhị phân ( m=2 )
Độ dài từ mã :
+ Là số ký tự của một mã
+ Ký hiệu : n
+ Ví dụ :một bộ mã có một từ mã là 001 thì n=3
Tổng số các từ mã của bộ mã ký hiệu là N
2. Các Loại Mã

a. Mã đều và mã không đều
Mã đều : là bộ mã có các từ mã với chiều dài bằng nhau
Mã không đều : là bộ mã có các từ mã với chiều dài không bằng nhau

b. Bộ mã đầy và bộ mã không đầy
Bộ mã đầy : khi N =
Bộ mã không đầy : khi N <

c. Xét Ví Dụ

[TABLE="class: MsoTableGrid"]
[TR]
[TD="width: 72"] Tin
[/TD]
[TD="width: 56"] A
[/TD]
[TD="width: 57"] B
[/TD]
[TD="width: 57"] C
[/TD]
[TD="width: 58"] D
[/TD]
[TD="width: 57"] E
[/TD]
[TD="width: 57"] F
[/TD]
[TD="width: 58"] G
[/TD]
[TD="width: 58"] H
[/TD]
[/TR]
[TR]
[TD="width: 72"] Từ mã
[/TD]
[TD="width: 56"] 000
[/TD]
[TD="width: 57"] 001
[/TD]
[TD="width: 57"] 010
[/TD]
[TD="width: 58"] 011
[/TD]
[TD="width: 57"] 100
[/TD]
[TD="width: 57"] 101
[/TD]
[TD="width: 58"] 110
[/TD]
[TD="width: 58"] 111
[/TD]
[/TR]
[/TABLE]

Ta có : N = 8 ; n=3 ; m=2
Do bộ mã có các từ mã với chiều dài bằng nhau nên đây là bộ mã đều
Và N = ( 8 = ) à đây là bộ mã đầy
è Kết luận : Đây là bộ mã đều và đầy

d. Tính prefix và prefix tối thiểu
Tính prefix : Mã có tính prefix là bộ mã thỏa điều kiện “ bất kỳ từ mã nào cũng đều không phải là prefix của bất cứ từ mã nào khác trong bộ mã .
Tính prefix tối thiểu : Là mã có tính prefix sao cho nếu X là một prefix của một từ mã thì αX phải là một từ mã hay là một prefix của một từ mã trong bộ mã
3. Các Phương Pháp Biểu Diễn Mã

a. Cây mã
Cho U = {00,01,100,1010,1011}

b. Đồ hình kết cấu








c. Hàm cấu trúc của mã hệ thống
Gọi n1,n2, . ,ni là độ dài các tổ hợp sơ đẳng của mã gốc
Gọi λ1, λ2, , λk là độ dài các tổ hợp cuối của mã gốc
g(nj) là số có thể có được các dãy ghép các tổ hợp sơ đẳng với độ dài tổng cộng là nj với qui ước : nj = 0 à g(nj) = g(0) = 1 và nj < 0 à g(nj) = 0
Gọi G(nj) là số có thể có được các từ mã có độ dài bằng nj
G(nj) = g(nj – λ1) + g(nj – λ2) + + g(nj – λk)
Với g(nj) = g(nj – n1) + g(nj – n2) + + g(nj – ni)