Bài giảng Lý thuyết thông tin - Chương 6

BÀI GIẢNG MÔN HỌCLÝ THUYẾT THÔNG TINTrang 2Mã vòng13.1 Giới thiệu13.2 Các tính chất của mã vòng13.3 Ma trận sinh và ma trận kiểm tra của mã 13.4 Mã BCHTrang 3Giới thiệuĐịnh nghĩaMộ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–1a0a1an–2 cũng là một từ mã.Nghĩa là dịch vòng (sang trái hay phải) một từ mã thì kết quả cũng là một từ mã. Ở đây qui ước dịch phải.Đa thức mãNếu w = a0a1an–2an–1 là một từ mã thì w(x) = a0 + a1x + + an–2xn - 2 + an–1xn - 1 là đa thức mã tương ứng với từ mã w.Ví dụBảng sau đây trình bày một mã vòng C(7, 4).Trang 4Ví dụmww(x)mww(x)00000000000000010001101x3 + x4 + x6100011010001 + x + x3100111001011 + x + x4 + x601000110100x + x2 + x401010111001x + x2 + x3 + x6110010111001 + x2 + x3 + x4110110100011 + x2 + x600100011010x2 + x3 + x500110010111x2 + x4 + x5 + x6101011100101 + x + x2 + x5101111111111 + x + x2 + x3 + x4 + x5 + x601100101110x + x3 + x4 + x501110100011x + x5 + x6111010001101 + x4 + x5111110010111 + x3 + x5 + x6Trang 5Giới thiệu (tt)w(i), w(i)(x)w(i) là từ mã do dịch từ mã w i bit, và w(i)(x) là đa thức mã tương ứng của w(i). w(0) chính là w.iw(i)w(i)(x)011010001 + x + x310110100x + x2 + x4 = x * (1 + x + x3) = x * w(x)20011010x2 + x3 + x5 = x2 (1 + x + x3) = x2 * w(x)30001101x3 + x4 + x6 = x3 (1 + x + x3) = x3 * w(x)410001101 + x4 + x5 = x4 + x5 + x7 mod 7 50100011x + x5 + x6 = x5 + x6 + x8 mod 7 610100011 + x2 + x6 = x6 + x7 mod 7 + x9 mod 7 Trang 6Giới thiệu (tt)w(i)(x) = xi * w(x) tuy nhiên nếu w(i)(x) có xp với p ≥ n thì xp được thay bằng xp mod n.Mặc khác trên trường GF(2) chúng ta có xn + j = xj * (xn + 1) + xj hay xn + j mod (xn + 1) = xjBổ đề 13.1 w(i)(x) = [xi * w(x)] mod (xn + 1)Trang 7Các tính chất của mã vòngĐịnh lý 13.1Đa thức mã khác 0 có bậc nhỏ nhất là duy nhất. Hay nói cách khác không tồn tại hai đa thức mã khác 0, khác nhau và cùng có bậc nhỏ nhất.Chứng minhGiả sử  hai đa thức mã khác nhau, cùng có bậc nhỏ nhất là r, 0 < r < n. g(x) = g0 + g1x + + gr–1xr - 1 + xr f(x) = f0 + f1x + + fr–1xr - 1 + xrTừ đây suy ra đa thức mã g(x) + f(x) có bậc nhỏ hơn r, mâu thuẫn. Chứng minh hoàn tất.Trang 8Các tính chất của mã vòng (tt)Kí hiệu đa thức mã có bậc nhỏ nhất là g(x) g(x) = g0 + g1x + + gr–1xr - 1 + xrĐịnh lý 13.2Hệ số tự do g0 của g(x) phải bằng 1.Chứng minhGiả sử g0 = 0. Suy ra g(x) = x * (g1 + + gr–1xr - 2 + xr - 1)Đặt f(x) = (g1 + + gr–1xr - 2 + xr - 1), suy ra f(x) cũng là một đa thức mã. Vì f(x) tương ứng với từ mã được dịch trái 1 bit hay dịch phải (n – 1) bit từ từ mã ứng với g(x).Mà bậc của f(x) bằng r – 1 < r mâu thuẫn với định nghĩa của g(x).Trang 9Các tính chất của mã vòng (tt)Định lý 13.3Một đa thức v(x) trên trường GF(2) có bậc ≤ n – 1 là đa thức mã nếu và chỉ nếu nó là một bội số của g(x). Tức là nó có thể viết v(x) = q(x) * g(x).Chứng minhChiều thuậnNếu v(x) = q(x) * g(x) và có bậc ≤ n – 1 thì v(x) là đa thức mã. với p là bậc của q(x) và p + r ≤ n – 1. Do xi * g(x) với 0 ≤ i ≤ p là đa thức mã, nên v(x) là đa thức mã vì nó là một tổ hợp tuyến tính của các đa thức mã.Trang 10Các tính chất của mã vòng (tt)Chiều ngượcNếu v(x) là đa thức mã thì chia v(x) cho g(x) v(x) = q(x) * g(x) + r(x) trong đó r(x) là đa thức dư và có bậc nhỏ hơn bậc của g(x). Đối với các đa thức trên trường GF(2) chúng ta có thể suy ra r(x) = q(x) * g(x) + v(x) Nên r(x) là một đa thức mã. Theo định nghĩa của g(x) suy ra r(x) = 0. Chứng minh hoàn tất.Từ định lý này chúng ta gọi g(x) là đa thức sinh, vì từ g(x) có thể sinh ra tất cả các đa thức mã khác.Trang 11Các tính chất của mã vòng (tt)Định lý 13.4Đa thức sinh của một mã vòng C(n, k) có bậc r = n – k.Chứng minhMỗi đa thức mã w(x) là một bội số của g(x) w(x) = q(x) * g(x)Có 2k từ mã nên có 2k đa thức q(x). Suy ra bậc của q(x) là  k – 1. Suy ra bậc của g(x) là n – k.Từ định lý này đa thức sinh g(x) có thể được biểu diễn như saug(x) = g0 + g1x + + gn – kxn – k trong đó g0 = gn – k = 1.Trang 12Các tính chất của mã vòng (tt)Định lý 13.5Đa thức sinh của mã vòng C(n, k) là một ước số của xn + 1.Chứng minhBổ đề 13.1 suy ra g(i)(x) = [xi * g(x)] mod (xn + 1)  xi * g(x) = q(x) * (xn + 1) + g(i)(x) Chọn i = k  q(x) = 1 tức xk * g(x) = (xn + 1) + g(i)(x)  xn + 1 = xk * g(x) + g(i)(x) Do g(i)(x) là một đa thức mã nên g(i)(x) là một bội của g(x),  xn + 1 là một bội của g(x). Chứng minh hoàn tất.Trang 13Các tính chất của mã vòng (tt)Định lý 13.6Nếu g(x) là một đa thức có bậc (n – k) và là ước số của (xn + 1) thì g(x) sinh ra mã vòng C(n, k), hay nói cách khác g(x) là đa thức sinh của một mã vòng C(n, k) nào đó.Chứng minhXét k đa thức g(x), x * g(x), , xk – 1 * g(x). Các đa thức này đều có bậc ≤ n – 1. Gọi v(x) là một tổ hợp tuyến tính của k đa thức này với các hệ số ai  GF(2). v(x) = a0g(x) + a1x * g(x) + + ak – 1xk – 1 * g(x) v(x) là một đa thức có bậc ≤ n – 1 và là bội số của g(x).Trang 14Các tính chất của mã vòng (tt)Có tất cả 2k tổ hợp tuyến tính v(x) khác nhau và tạo nên một không gian tuyến tính của các đa thức mã với g(x), x * g(x), , xk – 1 * g(x) là các đa thức làm cơ sở. Chúng ta chứng minh rằng bộ mã tương ứng với không gian này là mã vòng. Gọi w(x) = b0 + b1x + + bn – 1xn – 1 là một đa thức của không gian. Chúng ta chứng minh w(1)(x) = bn – 1 + b0x + b1x2 + + bn – 2xn – 1 cũng là một đa thức của không gian.Trang 15Các tính chất của mã vòng (tt)Theo Bổ đề 13.1 chúng ta có w(1)(x) = [x * w(x)] mod (xn + 1) Dựa vào biểu diễn của v(x) và w(1)(x) chúng ta suy ra x * w(x) = bn – 1(xn + 1) + w(1)(x) Do v(x) và (xn + 1) đều là bội của g(x) nên w(1)(x) cũng là bội của g(x). Suy ra w(1)(x) cũng là đa thức mã. Hoàn tất chứng minh.Trang 16Ma trận sinhVí dụTìm một mã vòng C(7, 4).Theo các tính chất của mã vòng suy ra đa thức sinh của mã có bậc bằng 3 và là một ước số của x7 + 1. Phân tích đa thức này ra thừa số chúng ta đượcTrang 17Ví dụ x7 + 1 = (1 + x)(1 + x + x3)(1 + x2 + x3)Chọn chẳng hạn g(x) = (1 + x + x3)Trang 18Mã vòng dạng hệ thốngTừ dạng hệ thống loại 1 chúng ta có thể dịch vòng k bit để biến đổi sang dạng hệ thống loại 2 và ngược lại.Mã hóa thành từ mã hệ thốngu(x) là thông báo, w(x) là từ mã hệ thống loại 2 tương ứng. xn–k * u(x) = q(x) * g(x) + a(x)w(x) = xn–k * u(x) + a(x) = q(x) * g(x)Trang 19Ví dụCho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Hãy mã hoá thông báo u = 1010 thành từ mã hệ thống dạng 2. u(x) = 1 + x2. Nhân u(x) với xn–k = x3 rồi chia cho g(x) chúng ta được. x3 * (1 + x2) = x3 + x5 = x2 * (1 + x + x3) + x2Từ đây suy ra w(x) = x2 + x3 + x5 w = 0011010 là từ mã hệ thống dạng 2 tương ứng với u.Trang 20Ma trận kiểm tra của mã vòngCó một cách khác để tìm ma trận kiểm tra của mã vòng xn + 1 = g(x) * h(x)h(x) được gọi là đa thức đối ngẫu của g(x). h(x) có bậc k h(x) = h0 + h1x + + hkxkMa trận sau là một ma trận kiểm tra của mã vòngTrang 21Ví dụCho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Từ đây suy ra h(x) = (1 + x + x2 + x4)Ma trận kiểm tra của bộ mã làTrang 22Ứng dụng trường GF(2m)để xây dựng mã vòngĐịnh lý 13.7Cho a là một phần tử khác 0 của trường GF(2m) có chu kỳ là n, đa thức tối thiểu f(x) của a có bậc là m. Thì mã có ma trận sau làm ma trận kiểm tra là một mã vòng C(n, n – m), trong đó mỗi phần tử trong ma trận bên dưới được thay thế bằng vectơ m thành phần tương ứng của nó. Hmn = [1 a a2 an – 2 an–1] Hơn nữa mã vòng này có đa thức sinh chính là f(x).Ví dụXét trường GF(24) và a có đa thức tối thiểu là f(x) = 1 + x + x4Trang 23Ứng dụng trường GF(2m)để xây dựng mã vòng (tt)Từ đây suy ra ma trận kiểm tra của mã vòng (15, 11).Nếu đa thức tối thiểu của a là f(x) = 1 + x + x2 + x3 + x4 thì a có chu kỳ là 5 và các phần tử 1, a, ..., a4 được biểu diễn như sau. 1 = (1000) a3 = (0001) a = (0100) a4 = (1111) a2 = (0010)Trang 24Ứng dụng trường GF(2m)để xây dựng mã vòng (tt)Từ đây suy ra ma trận kiểm tra của mã vòng (5, 1) Trang 25Mã BCH nhị phânDo Bose, Chaudhuri và Hocquenghem sáng lập ra.Là mã vòng có khả năng sửa được nhiều lỗi.Đối với các số nguyên dương m và t bất kỳ chúng ta sẽ xây dựng một mã BCH nhị phân có các thông số sau: Độ dài từ mã: n = 2m – 1 Số bit kiểm tra: n – k ≤ mt Khoảng cách Hamming: dmin ≥ 2t + 1Trang 26Định lýĐịnh lý 13.8Cho a là một phần tử của trường GF(2m) có đa thức tối thiểu là một đa thức căn bản bậc m. Thì mã có ma trận sau làm ma trận kiểm tra là một mã vòng có khoảng cách Hamming ≥ 2t + 1, trong đó mỗi phần tử trong ma trận bên dưới được thay thế bằng vectơ m thành phần tương ứng của nó.Trang 27Định lý (tt)Hơn nữa đa thức sinh g(x) của bộ mã là đa thức bội số chung nhỏ nhất của các đa thức tối thiểu của các phần tử a, a3, a5, , a2t–1.Bổ đề 13.2Ma trận A sau có định thức bằng với i, j  {1, 2, , r}. Định thức này được gọi là định thức Vandermonde. Trang 28Ví dụCho m = 4, t = 2 chúng ta sẽ xây dựng một mã vòng có chiều dài từ mã là 24 – 1 = 15 và có khoảng cách Hamming d ≥ 5. Việc xây dựng sẽ dựa vào trường GF(24).Gọi a là phần tử có đa thức tối thiểu là đa thức căn bản bậc 4 sau f1(x) = 1 + x + x4Đây chính là trường GF(24) trong ‎ví dụ ở slide 250.a có chu kỳ n = 2m – 1 = 15. Chúng ta có ma trận kiểm tra của bộ mã như sau.Thay mỗi phần tử ai bằng vectơ 4 thành phần tương ứngTrang 29Ví dụ (tt)Trang 30Ví dụ (tt)Đa thức sinh g(x) là bội số của hai đa thức tối thiểu tương ứng với phần tử a và a3.Theo ví dụ ở slide 250, đa thức tối thiểu của a3 là f3(x) = 1 + x + x2 + x3 + x4.Từ đây suy ra g(x) = f1(x) * f3(x) = (1 + x + x4) * (1 + x + x2 + x3 + x4) = 1 + x4 + x6 + x7 + x8Chú ýTrong trường hợp đa thức tối thiểu của a không phải là đa thức căn bản, chúng ta sẽ tìm được mã vòng có chiều dài n  2m + 1, với n là chu kỳ của a.