Đồ án Nghiên cứu mã sửa sai trong quá trình truyền và lưu trữ dữ liệu số

́ 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 phải 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). Hoặc 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 = pm – 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 pm – 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ạo thành một nhóm giao hoán. Phép cộng và phép nhân có tính chất phân bố tức là: a . (u + v) = a . u + a . v và (a + b) . v = a . v + b . v với mọi a , b F; u , v V . 3. ta có (a . b) = a. (b . v) 4. 1 . v = v với mọi v V, còn 1 là phần tử đồng nhất trong trường F (đối với phép nhân của trường). Ví dụ: Cho V = Rn với n là số tự nhiên tùy ý nhưng cố định. F = R là trường số thực. Dễ dàng kiểm tra được V là không gian vector. Định lý1.3.2 về chiều của không gian vector: Nếu một cơ sở của không gian vector V có k phần tử. Khi đó số k được gọi là số chiều của không gian V hay nói cách khác V là không gian vector con k chiều của không gian vector V hay nói cách khác V là trường không gian vector k chiều. Định lý 1.3.3: Giả sử S là một không gian vector con k chiều của không gian vector V ta ký hiệu: S+ = { u V / (u , v) = 0, với v S }. Khi đó S+ được gọi là không gian đối ngẫu (dual) của không gian vector con S. Định lý 1.3.4: Không gian đối ngẫu S+ của một không gian vector con S V là một không gian vector con của V. Định lý 1.3.4 : Cho V là một không gian vector có chiều là n; S V là một không gian con của V, còn S+ là không gian con đối ngẫu của S. Khi đó số chiều của không gian con S và số chiều của không gian con S+ bằng số chiều của V tức là: dim (S) + dim (S+) = dim (V). Mã khối tuyến tính. 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. Giả sử cho trước bộ mã Hamming (n, k) với k< n. Từ đây ta lập được tập hợp các từ mã khi cho biết đa thức bất khả qui (đa thức sinh) mỗi từ mã có độ dài n. Ta biết rằng tập hợp này gồm có n vector độc lập tuyến tính. Do đó trong tập hợp các từ mã, chọn ra n vector độc lập tuyến tính để lập ma trận sinh G và ma trận kiểm tra H sao cho 2 ma trận này trực giao với nhau. Trong đó G là ma trận cấp k × n còn ma trận H có cấp (n – k)× n, G và H phải thỏa mãn G × HT = 0. Có nhiều khi người ta viết ma trận G và H dưới dạng các vector nhị phân hàng: Với . Và Với Để xây dựng ma trận G và H ta nêu ra một vài bổ đề sau: Bổ đề 1: Tập hợp {1, x, x2,..., xn – 1} là tập hợp gồm n vector độc lập tuyến tính trong không gian tuyến tính các đa thức cấp n. Bổ đề 2: Giả sử f(n) là một đa thức cấp ( n- 1) tùy ý khác không. Ta đặt f0(x) = f(x). f1(x) = x.f(x). f2(x) = x2.f(x). ...................... fn - 1(x) = xn-1.f(x). với xn = 1. Vậy { f0, f1,..., fn- 1} là độc lập tuyến tính. Từ bổ đề trên ta suy ra rằng: để tìm k vector độc lập tuyến tính, ta chỉ việc tìm 1 vector mã f(x) khác không tùy ý. Từ vector này ta suy ra k vector độc lập tuyến tính bằngcách nhân xi với f(x), i = 0, 1,..., k – 1, ta được: Để xây dựng ma trận kiểm tra H cấp (n - k)× n, ta tìm 1 vector đầu tiên khác 0 trực giao với vector đầu tiên (hàng đầu trên của ma trận G). Sau đó áp dụng như thuật toán tìm ma trận G ta sẽ được n – k vector độc lập để tạo nên n – k dòng của ma trận H. Ma trận này sẽ thỏa mãn điều kiện G.HT = 0. Lưu ý: n cột của ma trận H sẽ ứng với n số tự nhiên dầu tiên từ 1 đến n được sắp xếp tùy ý. Thông thường 1 từ mã độ dài n, chẳng hạn cho từ mã a = (a1, a2,..., an) trong đó có k bit đầu là bit thông tin còn n – k bit sau làm bit sửa sai. Vì ma trận sinh G gồm k vector hàng độc lập tuyến tính nên nếu nhân vector a với ma trận G ta sẽ được hệ phương trình tuyến tính n ẩn k phương trình, vậy sẽ có n – k ẩn có thể biểu diễn tuyến tính qua k ẩn (ẩn tự do), n – k ẩn này chính là những bit kiểm tra. Vậy các bit kiểm tra có thể biểu diễn tuyến tính qua các bit thông tin. Như vậy có 2 kết luận quan trọng: Kết luận 1: Các bit trong n – k bit sửa sai đều có thể biểu diễn tuyến tính qua các bit thông tin. Kết luận 2: Mỗi vector mã bất kỳ đều là tổ hợp tuyến tính của các dòng ma trận G. Kết luận 3: Giả sử 1 từ mã tùy ý cho trước mã a = (a1, a2,..., an); . Các bit thông tin a1,..., ak coi như đã biết trước. Vấn đề là cần xác định giá trị các bit kiểm tra ak+1,..., an đó để có thể phát hiện và sửa các bit bị sai. Để giải quyết vấn đề này, ta áp dụng kết quả trong kết luận 1. Kết luận 4: Do G và H trực giao nhau, tức là G.HT = 0 và từ kết luận 2, ta suy ra rằng: mọi từ mã mã a = (a1, a2,..., an) bất kỳ, đều thỏa mãn hệ thức: H . a’ = 0 (a’ là chuyển vị của vector a) tức là trực giao với ma trận H. Từ kết luận 4 ta suy ra nếu ta nhận được 1 từ mã a1 chẳng hạn, thế thì ta có phương pháp kiểm tra như sau: H . a1 = 0 => từ mã a1 là đúng. H . a1 0 => từ mã a1 là sai. Và áp dụng lý thuyết trường hữu hạn các đa thức đồng dư ta có thể tìm được đa thức sai e(x).Vị trí thành phần sai chính là vị trí cột của ma trận H ứng với vector H . a. Kết luận 5: ta có thể áp dụng đa thức đồng dư để kiểm tra và sửa sai như sau: giả sử ta nhận được 1 đa thức d(x) (ứng với từ mã phát đi) . Với g(x) là đa thức sinh cho trước (đa thức sinh có bậc n - k). d(x) là đa thức bậc n – 1. Lúc đó nếu đa thức q(x) sao cho: d(x) = g(x). q(x) => d(x) đúng là đa thức phát ứng với từ mã phát đi. Còn nếu e(x) 0 là đa thức có cấp bé hơn cấp của g(x) sao cho: d(x) = g(x).q(x) + e(x) thì từ mã d(x) nhận được có sai số. Để sửa sai ta xác định đa thức e(x) như sau: e(x) = r(x).g(x). Sau khi xác định được đa thức e(x) ta chỉ việc lấy đa thức nhận được d(x) trừ (hoặc cộng) đi e(x) thì kết quả của phép trừ (cộng) cho ta đa thức phát đúng. 2.2.2. Phát hiện và sửa sai. Trong quá trình truyền tin sẽ xảy ra sai số do nhiều nghuyên nhân. Giả sử ở đầu phát, phát đi mã f(x) nhưng do sai số trên đường truyền mà ở đầu nhận nhận được sẽ là: d(x) = f(x) + e(x). e(x) được gọi là đa thức gây nhiễu (hay là độ sai lệch ). Sau khi nhận được đa thức d(x) ta chia kết quả nhận được cho đa thức sinh g(x). Hai trường hợp sau đây sẽ xảy ra: Nếu phép chia đó có đa thức dư bằng 0 thì đa thức d(x) chính là f(x) và trong trường hợp này không xảy ra sai số. Lúc đó: d(x) f(x). Nếu e(x) 0 thì: d(x) = f(x) + e(x) = g(x).q(x) + e(x). Ta cần xác định đa thức nhiễu e(x), tức là ta sẽ xác định được các bit sai trong từ mã. Ví dụ: Giả sử từ mã (7, 4) phát đi ở phía đầu vào của kênh là: f(x) = x + x3 + x4 = 0101100. Đa thức sinh là: g(x) = x3 + x2 + 1. Còn từ mã nhận được từ đầu ra là: d(x) = x + x4 + x5 = 0100110. So sánh 2 từ mã này ta thấy sai 2 bit: thiếu bit thứ 3 (x3) và thừa bit thứ 5 (x5). Nếu đem cộng 2 từ mã tương ứng cho nhau thưo mod(2) ta thấy 2 vị trí khác 0 là vị trí thứ 4 và vị trí thứ 6 tức là vector sai sẽ là: e(x) = x3 + x5. Bây giờ ta chỉ ra thuật toán xác định e(x). Sau đây là một phương pháp xác định e(x). Lấy d(x) chia cho g(x) sau đó lấy số dư r(x) của phép chia đem nhân với g(x) tiếp theo lấy kết quả của phép nhân trừ cho r(x). Kết quả cuối cùng chính là đa thức ứng với các vị trí sai trong vector nhận được. Trong ví dụ trên d(x) = x5 + x4 + x. Còn g(x) = x3 + x2 + 1 ta có: = = x2 + r(x) ; r(x) = x2 + x. Vì vậy đa thức sai e(x) = r(x).g(x) – r(x) hoặc e(x) = r(x).g(x) + r(x). Sau khi xác định được đa thức sai e(x) ta chỉ cần cộng nó lại với vector nhận được kết quả sẽ cho ta đa thức đúng f(x) = d(x) – r(x). 2.2.3. Mã tuyến tính Hamming. Đặc trưng của bộ mã Hamming là 2 tham số n và K (n, K) trong đó K<n. Lúc đó sẽ có 2n tổ hợp các từ mã khác nhau trong đó 2K từ mã thông tin còn 2n – K từ mã khác nhau dùng cho sửa sai. Ta tạo ra ma trận GK, n và Hn – K, n sao cho các dòng của chúng độc lập tuyến tính. Chẳng hạn với bộ mã (7,4) ta có 27 vector từ mã khác nhau, mỗi từ mã có 7 thành phần, 4 thành phần đầu là các thành phần mang tin, 3 thành phần còn lại là các thành phần dùng để phát hiện và sửa sai. Ma trận G: ma trận sinh. Ma trận H: ma trận kiểm tra. Trường hợp n=7, K=4 thì ma trận G có 4 hàng, 7 cột còn ma trận H có 3 hàng và 7 cột. Chẳng hạn ma trận G có dạng: 1 0 0 0 0 1 1 0 1 0 0 1 0 1 G = 0 0 1 0 1 1 0 = 0 0 0 1 1 1 1 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 = 1 0 1 0 1 0 1 Ta thấy G×H = 0 . Ví dụ: Cho bộ mã Hamming(7, 4) để phát hiện và sửa sai. Giả sử ta có một từ mã dạng: a1, a2......,a7 với ai є {0, 1}; i = 1, 2, 3..,7. Trong đó a1, a2, a3, a4 là các bit thông tin( có 24 = 16 từ mã thông tin) còn a5, a6, a7 là các bit dùng để kiểm tra ai є {0, 1} i = 5, 6, 7 (để ngắn gọn ta gọi là các bit kiểm tra). Các bit thông tin được coi là đã biết ta cần phải xác định giá trị cụ thể của các bít a5, a6,a7 ứng với mỗi từ mã dó sao cho : nếu trong các bít thông tin có bị sai ở thành phần nào đó thì nhờ các bít sửa sai ta có thể phát hiện và sửa sai các bít bị sai đó ,Tức là ta biểu diễn a5, a6,a7 qua tổ hợp tuyến tính a1, a2, a3, a4 . Điều này được thực hiện bằng cách giải hệ ba phương trình tích vô hướng của vector từ mã đó với lần lượt các vector kiểm tra , , và cho bằng 0 để xác định, , . Cụ thể là: a1, a2....,a7. = a1 a2 a3 a4 a5 a6 a7. 0001111 = a4 a5 a6 a7 = 0 (1) a1, a2....,a7. = a1 a2 a3 a4 a5 a6 a7. 0110011 = a2 a3 a6 a7 = 0 (2) a1, a2....,a7. = a1 a2 a3 a4 a5 a6 a7. 1010101 = a1 a3 a5 a7 = 0 (3) Vậy ta có hệ 3 phương trình sau: a4 a5 a6 a7 = 0 (1) a2 a3 a6 a7 = 0 (2) a1 a3 a5 a7 = 0 (3) Cộng phương trình (1) với (2) ta có: a4 a5 a2 a3 = 0 a5 = a2 a3 a4 (4) Cộng phương trình (2) với (3) ta có: a1 a2 a5 a6 = 0 hay: a1 a2 a2 a3 a4 a6 a6 = a1 a3 a4 (5) Thay kết quả ở (4) và (5) vào 1 trong 3 phương trình (1) (2) (3) chẳng hạn vào phương trình (1) ta có: a7 = a4 a5 a6 = a4 a2 a3 a4 a1 a3 a4 = a1 a2 a4 Tức là 3 phần tử a5, a6, a7 biểu diễn dưới dạng tổ hợp của 4 thành phần mang tin Bây giờ để tiếp theo ví dụ trên để đơn giản ta giả thiết các từ mã thông tin là 16 chữ cái đầu tiên (vì 24 = 16 tổ hợp các vector 4 thành phần mang tin là 0000, 000..., 1111) và tương ứng với các mã nhị phân theo thứ tự từ 0000 cho đến 1111. Kết quả mã sửa sai Hamming (7, 4) trong ví dụ này được cho trong bảng 1 sau Kí tự a1 a2 a3 a4 a5 a6 a7 Các vector tương ứng a b c d e f g h i j k l m n o p 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 000 111 110 001 101 010 011 100 011 100 101 010 110 001 000 111 + + + + + + + + + + + + + + + + + + Trong trường hợp có sai. Ví dụ ở đầu phát, phát đi chữ h có mã 0111 100 nhưng ở đầu thu nhận được mã chữ h là: 0111 110. Để kiểm tra ta nhân thử ma trận kiểm tra H với vector nhận được (h’ = 0111 110) 0 1 0 0 0 1 1 1 1 1 1 H.h’= 0 1 1 0 0 1 1 . 1 = 1 0 1 0 1 0 1 0 1 1 0 1 0 Vậy vector nhận có sai và vị trí sai của vector ấy là 110. Vector này là vector cột thứ 6 của ma trận H, vậy vị trí sai của vector nhận là vị trí thứ 6. Do đó ta sửa lại vị trí thứ 6 của vector nhận được là 1 thành 0. Tóm lại vector đúng của nó là 0111 100. 2.2.4. Mã vòng. Mã vòng thực chất là trường hợp đặc biệt của mã tuyến tính. Ở đây ma trận sinh là ma trận vòng( dịch chuyển vòng quanh). Định nghĩa: Một mã tuyến tính C(n, k) được gọi là mã vòng nếu w = a0a1an-2an-1 là một từ mã thì v = an-2a0a1an-2 cũng là một từ mã. Nói cách khác mã vòng là mã có tính vòng, có nghĩa là dịch vòng một từ mã thì kết quả cũng là một từ mã. Ưu điểm: Xét phương diện kinh tế thì mã vòng có nhiều ưu điểm hơn so với mã tuyến tính. Ở mã tuyến tính ma trận sinh G phải được nhớ trong một tập hợp các thanh ghi dịch. Ở mã vòng ma trận sinh chỉ cần được nhớ một dòng là đủ. Do đó việc thiết kế phần cứng cũng không phức tạp lắm. Nhược điểm: Tuy vậy nhưng phương pháp xác định ma trận sinh G và ma trận kiểm tra H tỏ ra phức tạp hơn. Ví dụ: cho bộ mã vòng (n, K) (K<n) Chẳng hạn n= 7, K = 4. Bằng tính toán ta có thể xác định được ma trận sinh G và ma trận kiểm tra H. Một trong những ma trận sinh và ma trận kiểm tra được xác định trong trường hợp cụ thể này là: 0 1 0 1 1 0 0 1 0 1 1 0 0 0 G = 0 1 1 0 0 0 1 = 1 1 0 0 0 1 0 0 1 1 1 0 1 0 H = 1 1 1 0 1 0 0 = 1 1 0 1 0 0 1 Lưu ý: Ma trận G là ma trận gồm K vector dòng (trường hợp này K = 4) độc lập tuyến tính và lập thành một cơ sở trong không gian các từ mã n thành phần (ở ví dụ này n = 7) các dòng của ma trận H cũng tạo thành n – K vector độc lập tuyến tính. Còn n cột (ở đây n = 7 ) của ma trận kiểm tra H tương ứng với n số thập phân từ 1 đến n (không theo thứ tự). Trong mã vòng có thể phát hiện và sửa sai nhiều bit sai trong một từ mã. Các bit kiểm tra a5, a6, a7 được suy ra từ các bit thông tin a1, a2, a3, a4 trong bộ mã (n, K) = (7, 4). Ví dụ: Cho từ mã a1 a2 a3 a4 a5 a6 a7 các bit thông tin là a1 a2 a3 a4, còn các bit kiểm tra là a5 a6 a7 . Bằng cách nhân vô hướng vector từ mã a2 a3 a4 a5 a6 a7 với lần lượt các véctơ của ma trận kiểm tra và cho đồng nhất 0 ta thu được 3 phương trình (trong trường hợp trên) sau đây ): a2 + a3 + a4 + a5 = 0 a1 + a2 + a3 + a5 = 0 (I) a1 + a2 + a3 + a4 + a7 = 0 Đây là hệ 3 phương trình 7 ẩn số và dễ thấy rằng 3 véc tơ hàng của ma trận là độc lập tuyến tính . Do đó số ẩn nhiều hơn số phương trình nên tồn tại a5,a6,a7 biểu diễn tổ hợp tuyến tính của các ẩn còn lại. Dễ thấy : a5 = a1 + a2 +a3 a6 = a2 +a3 + a4 a7 = a3 + a4 + a5 = a3 + a4 + a1 + a2 +a3 = a1 + a2 + a4 Trong các ví dụ này , tập các từ mã tổng quát ( gồm các bít thông tin và cả các bit kiểm tra ) được xác định như sau : ( Số các bít ký tự là 24 = 16 ) Kí tự Các bit thông tin Các bit kiểm tra Các vector tương ứng a b c d e f g h i j k l m n o p 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 000 111 110 101 111 100 001 010 101 110 011 000 010 001 100 111 + + + + + + + + + + + + + + + + + + Bây giờ giả sử ta nhận được một từ mã: a = a6 a5 a4 a3 a2 a1 a0 = 1000011 (giá trị a4 bị sai) Ta thử kiểm tra xem chúng có sai không và sai tại vị trí nào? Để thực hiện điều đó ta nhân vector a với ma trận kiểm tra: 1 + (a, ) = ( 1000011, 0111010 ) = 1. 1 + (a, ) = ( 1000011, 1101001 ) = 1. 1 + (a, ) = ( 1000011, 1101001 ) = 1 + 1 = 0. 1 Vậy vector kết quả là : 1 0 1 1 là một vector cột của ma trận kiểm tra, vector này ở cột thứ 3 của ma trận 0 kiểm tra H thành phần sai ở vị trí 3 tức là a4. Có một vấn đề đặt ra là giả sử cho một bộ mã sửa sai (n, K) với K< n. Như vầy mối quan hệ giữa K và n được thể hiện qua bổ đề sau đây: Bổ đề: quan hệ giữa các bit thông tin (K) và các bit sửa sai (n- K) trong một từ mã phải thoả mãn hệ thức: K 2n- K – (n- K+1) Hoặc tương đương: 2n- K (n +1) 2K  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. Các tính chất cơ bản. Tính chất 1: Một từ mã bất kỳ a0 a1 a2..an- 1 đều có thể biểu diễn một cách duy nhất dưới dạng: an – 1 Xn - 1 + an – 2 Xn – 2 +..+a0. Tính duy nhất được suy ra từ một kết quả trong đại số rằng {1, x, x2,.,xn – i } lập thành một cơ sở trong không gian các đa thức cấp n-1. Ví dụ: cho từ mã 1100110 (n = 7) Lúc đó 1100110 ~ x6 + x5 + x2 + x và biểu diễn này là duy nhất. Tính chất 2: Nếu đem nhân đa thức biểu diễn từ mã với x thì có nghĩa là ta chuyển dịch các phần tử của từ mã đó đi 1 vị trí sang trái. Ví dụ: có 1 đa thức biểu diễn từ mã: x6 + x5 + x2 + x (1) Ta đem nhân đa thức (1) cho x ta có: x( x6 + x5 + x2 + x ) = x6 + x3 + x2 +1. Một cách tổng quát, nếu ta muốn chuyển dịch các thành phần của từ mã đi 1 vị trí, ta chỉ cần nhân đa thức từ ma với xi với i = 1, 2 Điều này gợi ý cho ta ứng dụng tính chất này để tạo ra ma trận G và H của mã dịch vòng, hàng sau là do kết quả của sự chuyển dịch của hàng trước đó tạo nên. Tính chất 3: Trong lý thuyết trường các đa thức đồng dư, một đa thức xn -1 có thể được phân tích ra các đa thức thừa số, tức là 1- xn = (1-x)Q(x). Giả sử P(x) là 1 đa thức ứng với từ mã thông tin.Ta nhân xn- K với P(x) với K= 1, 2, 3,,n-1. Thì có: xn – KP(x). Giả sử g(x) là một đa thức bất khả quy, lúc đó đặt: = q(x) + r’(x) với r’(x)= Bây giờ đặt từ mã f(x) bất kỳ (n, K) đều có dạ