Download miễn phí Đồ án Nghiên cứu mã sửa sai trong quá trình truyền và lưu trữ dữ liệu số
Mục lục
Phần I: Mã hóa dùng nguồn. 4
1.1. Entropi 4
1.1.1. Sự bất định, thông tin và Entropi 4
1.1.2. Tính chất cua Entropi 4
1.2. Lý thuyết mã hóa nguồn 4
1.2.1. Mã tiền tố 5
1.2.2. Mã Huffman 6
1.2.3. Mã Lempel 7
Phần II: Mã hoá trên kênh truyền 7
2.1. Một số khái niệm về trường Galois 7
2.1.1 Nhóm, trường, không gian vector 7
2.1.1.1 Định nghĩa nhóm 7
2.1.1.2. Định nghĩa về cấp của 1 phần của một nhóm nhân 8
2.1.1.3. Định nghĩa về một vành (Ring). 8
2.1.1.4. Định nghĩa về Trường (Fields 8
2.1.1.5. Định nghĩa hàm Euler 9
2.1.1.6. Định nghĩa phần tử nguyên thủy 9
2.1.1.7. Định nghĩa đặc số 10
2.1.2.Các đa thức nguyên thủy, các trường Galois có cấp Phần mềm 10
2.1.2.1. Định nghĩa đa thức bất khả quy 10
2.1.2.2. Đa thức nguyên thủy 10
2.1.3. Không gian vector 10
2.2. Mã khối tuyến tính 11
2.2.1. Ứng dụng lý thuyết đa thức đồng dư trên trường GF(2) để xây dựng mà trận sinh G và ma trận kiểm tra H 11
2.2.2. Phát hiện và sửa sai 14
2.2.3. Mã tuyến tính Hamming 15
2.2.4. Mã vòng 19
2.2.5. Ứng dụng lý thuyết trường các đa thức đồng dư để tính toán mã vòng 24
2.3. Chương trình hóa phép chia đa thức được cứng hóa bằng mạch điện 25
http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_nghien_cuu_ma_sua_sai_trong_qua_trinh_truyen_va_luu_tr_jkMX7hJVJA.png /tai-lieu/do-an-nghien-cuu-ma-sua-sai-trong-qua-trinh-truyen-va-luu-tru-du-lieu-so-87390/ Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn. Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn
Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
́ sự bất định nào.
- H(S) = log2K nếu và chỉ nếu pk = 1/K với mọi K. Đây là cận trên của Entropi ứng với trường hợp có sự bất định cực đại của nguồn.
Lý thuyết mã hóa nguồn.
Một vấn đề quan trọng của lý thuyết truyền thông là biểu diễn có hiệu quả tín hiệu phát ra từ nguồn rời rạc. Quá trình này gọi là mã nguồn. Mã nguồn phải thỏa mãn hai điều kiện:
Từ mã ở dạng nhị phân và có chiều dài trung bình ngắn nhất.
Mã nguồn phải được giải mã duy nhất.
Giả sử ký hiệu sk được biểu diễn bởi từ mã dài lk hay:
là độ dài từ mã trung bình. (4)
sẽ được đánh giá là hiệu suất mã nguồn. (5)
Định lý Shannon:
(6)
Mục đích của mã hóa dùng nguồn là lấy dữ liệu nguồn và thu nhỏ chúng lại.
1.2.1. Mã tiền tố.
Giả sử sk được biểu diễn bằng từ mã (m1, m2,..., mn), ở đó mi là các bit 0, 1. Phần đầu m1m2...mk với k < n của một từ mã gọi là tiền tố của mã. Mã tiền tố là mã mà không có từ mã nào lại là tiền tố của từ mã khác.
Mã tiền tố có tính chất quan trọng là luôn giải mã được duy nhất. Nếu mã tiền tố được dùng cho nguồn không nhớ rời rạc (s0, s1,..., sk - 1) với xác suất (p0, p1,..., pk - 1) và từ mã sk có độ dài lk, k = 0, 1, 2....k – 1 thì chúng thỏa mãn bất đẳng thức Mc MiLan:
Đảo lại nếu độ dài các từ mã cho nguồn rời rạc không nhớ, thỏa mãn bất đẳng thức trên, thì có thể xây dựng được mã tiền tố. Mặc dù mã tiền tố có thể được giải mã duy nhất song ngược lại là không đúng.
Mã tiền tố khác với mã khác là nhận biết được vị trí cuối của từ mã nên giải mã sẽ hoàn tất ngay khi dãy nhị phân nhận được đủ nên đôi khi được gọi là mã tức thời.
Ngoài ra từ mã trung bình trong mã tiền tố thỏa mãn bất đẳng thức:
(8)
Biên trái thỏa mãn đẳng thức khi ký hiệu sk được nguồn phát ra với xác suất:
(9)
Ở đó lk là độ dài của từ mã ứng với ký hiệu sk, khi đó:
(10)
Với điều kiện này bất đẳng thức Mc MiLan thỏa mãn nên có thể cấu tạo được mã tiền tố có từ mã trung bình là:
(11)
Entropi tương ứng của nguồn sẽ là:
(12)
Do vậy trong trường hợp đặc biệt này mã tiền tố cho
Song làm sao đối với một nguồn bất kỳ mã tiền tố cũng đạt được điều này ?. Để trả lời ta dùng mã mở rộng. Giả sử ký hiệu độ dài trung bình của mã tiền tố mở rộng. Đối với một mã được giải duy nhất là có thể nhỏ nhất. Dùng phương trình trên ta có:
(13)
Thay vào phương trình cho nguồn mở rộng:
(14)
Hay tương đương là: (15)
Khi n tiến đến vô cùng: (16)
Có thể phát biểu rằng bằng cách tạo bộ mã nguồn tiền tố bậc đủ lớn ta có thể biểu diễn nguồn gần với mong muốn. Nói cách khác độ dài từ mã tiền tố có thể làm ngắn như Entropi, song chi phí rất tốn kém.
1.2.2. Mã Huffman.
Mã Huffman là mã có độ dài trung bình đạt tới giới hạn Entropi của nguồn. Quá trình mã hóa như sau:
1. Ký hiệu nguồn được sắp xếp theo xác suất giảm dần. Hai ký hiệu nguồn với xác suất thấp nhất được gán 0 và 1.
2. Tổng xác suất hai nguồn trên được sắp vào bước thứ 2 cũng theo thứ tự giảm dần.
3. Quá trình được lặp lại cho đến khi chỉ còn hai nguồn tương ứng với 0 và 1 được phân.
4. Mã của mỗi nguồn sẽ được tìm theo chiều đi ngược lại trong bảng.
Mã Lempel – Ziv.
Khi xây dựng mã Huffman cần biết mô hình xác suất nguồn. Tuy nhiên trên
thực tế không phải mô hình này luôn luôn cho biết trước. Thêm nữa mô hình văn bản cho ta thấy yêu cầu về lưu trữ làm cho mã Huffman không bắt được mối liên hệ bậc cao giữa từ và nhóm từ và do vậy giảm hiệu suất mã. Để vượt qua giới hạn này ta dùng thuật toán Lempel – Ziv, chúng thích nghi và dễ dàng thực hiện hơn mã Huffman
Thuật toán này phân chia dòng dữ liệu thành các khúc là các dãy con ngắn nhất không được tính trước đó.
Phần II: Mã hoá trên kênh truyền.
Một số khái niệm về trường Galois.
Nhóm, trường, không gian vector.
2.1.1.1. Định nghĩa nhóm.
Một nhóm (Group) là một tập hợp G 0 cùng với phép toán nhị nguyên trên G
được ký hiệu là “*” thỏa mãn tính chất sau đây:
1. .
2. (a*b)*c = a* (b*c) đối với mọi phần tử a, b, c G
3. Tồn tại một phần tử đơn vị (hay phần tử đồng nhất ) e G sao cho
a*e = e*a đối với mọi a G.
4. sao cho a*b = b*a = e. Nếu toán tử * là phép nhân tức là . Thì ta thường thay phần tử b có tính chất ở 4 bởi a-1 và phần tử e được ký
hiệu là 1 và (G, .) được gọi là nhóm nhân.
Tính chất 1 được gọi là là tính đóng (Closure).
Tính chất 2 được gọi là tính chất kết hợp (Associativity).
Tính chất 3 được gọi là tính đồng nhất (Identity).
Tính chất 4 được gọi là tính nghịch đảo (Inverse).
5. Nếu tính chất 1 có thêm tính chất giao hoán thì nhóm đó được gọi là nhóm Abel (Abelian).
Trường hợp toán tử * + thì nhóm (G, +) được gọi là nhóm cộng.
Chú ý phép nhân hay phép cộng ở đây không chỉ là phép nhân (.) hay cộng (+) thông thường mà có tính tổng quát hơn nhiều.
Cấp (Order) của một nhóm G được định nghĩa là lực lượng (cardinality) của G. Để ứng dụng cho nội dung bản luận văn em chỉ hạn chế xét trong trường hợp G là nhóm hữu hạn, tức là cấp của nó là một số hữu hạn.
2.1.1.2. Định nghĩa về cấp của 1 phần của một nhóm nhân.
Giả sử g là một phần tử của một nhóm nhân G. Để thuận tiện ta viết g . g = g2 ; g. g. g = g3 . Khi đó người ta định nghĩa cấp của phần tử g là một số nguyên dương nhỏ nhất m sao cho gm = 1 (1 là phần tử đơn vị của nhóm G). hay như người ta thường viết
m = ord (g).
2.1.1.3. Định nghĩa về một vành (Ring).
Một vành (Ring) là tập hợp các phần tử của R cùng với 2 phép toán 2 ngôi “+ ” và “.” Sao cho thỏa mãn 3 tính chất sau đây:
Tính chất 1: R tạo thành một nhóm giao hoán đối với phép “+” còn phần tử đồng nhất được ký hiệu là “0”.
Tính chất 2: Phép toán nhân “.” Có tính chất kết hợp, tức là
(a . b) . c = a . (b. c) a , b R.
Tính chất 3: Phép toán nhân “.” Có tính chất phân bố đối với phép cộng nghĩa là: a . (b + c) = (a . b) + (a . c) đối với a , b, c R.
Vành R được gọi là vành giao hoán nếu phép toán nhân (.) có tính chất giao hoán.
Vành R được gọi là vành có đơn vị (và được ký hiệu là 1) tồn tại 1 thuộc R sao cho a . 1 = 1 . a = a a R.
2.1.1.4. Định nghĩa về Trường (Fields).
Một trường F là một vành giao hoán sao cho đối với phép nhân F là một nhóm (ngoài phần tử 0).
Định lý 1.3: Tập hợp các số nguyên { 0, 1, 2. , p – 1} trong đó p là 1 số nguyên tố tạo thành một trường GF(p) đối với phép cộng và phép nhân modulo p. Đó chính là trường Galois.
Các tính chất cơ bản của trường Galois:
Tính chất 1: Gọ a là một phần tử bất kỳ thuộc trường GF(p) còn 1 là phần tử đơn vị đối với phép nhân của trường Galois GF(p).
Ta xét dãy sau đây : 1, a, a2, a3, a4
Vì a GF(p) => a2 GF(p) và a3 GF(p),.Vì trường GF(p) là hữu hạn do đó m (m ≥ 1) bé nhất sao cho am = 1 (theo modulo p) và viết là ordp(a) = m (số m đó được gọi là cấp của phần tử a của trường GF(p)).
Tính chất 2: Cho a GF(p). Khi đó nếu t = ord (a) thì p – 1 chia hết cho t.
Tính chất 3: Gọi a, b là các phần tử trong GF(p) sao cho b = ai. Nếu ord(a) = t khi đó
Với GCD = Great common Divisor hay là ước số chung lớn nhất.
2.1.1.5. Định nghĩa hàm Euler.
Cho trước n là một số nguyên dương tùy ý ta định nghĩa hàm Euler như sau:
và n> 1 ta có:
# { 1 < n: GCD (i, n) = 1} . Dấu # chỉ lực lượng của tập hợp đó.
Tính chất 4:
Nếu t không phải là ước của p – 1, khi đó trong GF(p) không có phần tử nào cấp t.
Nếu t là ước của p – 1, khi đó có phần tử cấp t trong GF(p).
2.1.1.6. Định nghĩa phần tử nguyên thủy.
Phần tử a GF(p) có cấp p – 1 được gọi là phần tử nguyên thủy.
Hệ quả (của tính chất 4) : Với mọi trường GF(p) có cấp p – 1 có đúng phần
tử nguyên thủy.
2.1.1.7. Định nghĩa đặc số.
Đặc số (characteristic) của trường GF(p) là số nguyên dương bé nhất m sao cho m(1) = 0. Trong đó 0 là phần tử đồng nhất đối với phép cộng trong GF(p).
m (1) = 1 + 1 + 1 ++ 1 (m lần).
Tính chất 5: Đặc số m của trường GF(p) luôn luôn là một số nguyên tố.
Tính chất 6: Cấp p của trương GF(p) phải là lũy thừa của một số nguyên tố.
2.1.2.Các đa thức nguyên thủy, các trường Galois có cấp pm.
2.1.2.1. Định nghĩa đa thức bất khả quy.
Đa thức f(x) được gọi là bất khả quy (irreducible) trong trường GF(q) nếu f(x) không thể phân tích thành các đa thức có bậc nhỏ hơn trong GF(q)[x] ký hiệu là trường các đa thức có hệ số trong GF(q).
2.1.2.2. Đa thức nguyên thủy.
Đa thức bất khả quy p(x) GF(p)[x] có cấp m được gọi là đa thức nguyên thủy nếu số nguyên dương bé nhất sao cho xn – 1 chia hết cho p(x) là n = Phần mềm – 1.
Định lý: Tất cả các nghiệm {αj } của đa thức nguyên thủy p(x) GF(p)[x] có cấp Phần mềm – 1.
2.1.3. Không gian vector.
Định lý1.3.1: Cho V là một tập hợp các phần tử được gọi là các vector và F là một trường mà các phần tử của nó được gọi là nhứng vô hướng. Trên V ta xác định 2 phép toán : phép cộng các vector trên V và phép nhân mỗi phẩn tử trong V với một vô hướng trong F sao cho v1 + v2 = v V và với a bất kỳ F, v V ta có a.v V và thỏa mãn các tính chất sau đây:
V cùng với phép cộng t...
