Bài giảng Lý thuyết thông tin (Mới)

yền là w, vectơ lỗi là e và vectơ nhận là v thì
 v = w + e
 e = v + w
 w = e + v
 Ví dụ
  w = 1011011, e = 0010100 v = w + e = 1001111.
  w = 0110010, v = 0010011 e = w + v = 0100001.
  v = 1011001, e = 0010010 w = v + e = 1001011.
 96
 12/25/2010
 Tập giải mã - coset
  Cho S là một không gian con các từ mã của không gian V, coset
 của một phần tử z V đối với S được kí hiệu là z + S và được
 định nghĩa như sau
 z + S = {z + w: w S}
 Bổ đề 12.5
  Tập coset z + S có các tính chất sau.
 (1) z z + S.
 (2) Nếu z S thì z + S = S.
 (3) Nếu v z + S thì v + S = z + S.
 (4) Nếu v z + S thì v + S và z + S rời nhau.
 Sơ đồ giải mã
  Với mỗi vectơ nhận v chúng ta sẽ có một tập coset tương ứng là
 v + S.
  Trong tập này chọn phần tử có trọng số nhỏ nhất, chẳng hạn là
 z. Phần tử này thường được gọi là coset leader.
  Thông báo từ mã được truyền chính là w = v + z.
 Bổ đề 12.6
  Các phần tử của một tập coset có cùng một syndrome như nhau.
 Các tập coset khác nhau có các syndrome khác nhau.
  e = (a1, a2, ..., an), các cột của H lần lượt bằng h1, h2, ..., hn thì
 n
 T
 s(e) e H  aihi  aihi
 i 1 ai 0
 Sơ đồ giải mã (tt)
  Nghĩa là s(e) bằng tổng những cột ở những vị trí tương ứng với
 những vị trí bằng 1 của e.
  Nếu vị trí lỗi sai là 3 thì syndrome của vectơ nhận sẽ là cột số 3
 của H.
 1 1 0 1 0 0 0 
 1 0 0 1 0 1 1 
 1 0 1 1 1 0 0 
 G H3 7 0 1 0 1 1 1 0
 4 7 0 1 0 0 0 1 1 
 0 0 1 0 1 1 1 
 1 0 1 0 0 0 1 
  Tìm vị trí lỗi sai của các vectơ nhận sau đây
 v = 0010011 s(v) = ? e = ? w = ?
 v = 0101101 s(v) = ? e = ? w = ?
 97
 12/25/2010
 Mã tuyến tính Hamming
  Mã tuyến tính Hamming là mã có ma trận H có tính chất giá trị của cột hi
 bằng i (i = 1, 2, ...)
 0 0 0 1 1 1 1 
 H3 7 0 1 1 0 0 1 1 
 1 0 1 0 1 0 1 
 Bổ đề 12.7
  Các mã tuyến tính Hamming đều có khoảng cách Hamming d = 3. Vì vậy
 có thể phát hiện sai 2 bit và sửa sai 1 bit.
 Mã Hamming cho phép sửa sai 1 bit một cách đơn giản như sau:
 1. Tính syndrome s(v) của vectơ nhận.
 2. Đổi chuỗi nhị phân tương ứng ra giá trị thập phân, kết quả đổi chính là vị
 trí lỗi sai đã xảy ra.
 3. Sửa sai ở vị trí lỗi sai tương ứng.
 Ma trận sinh của mã tuyến tính Hamming
  Xét mã tuyến tính Hamming C(7, 4) có các bit thông tin nằm ở
 các vị trí 3, 5, 6, 7. Hãy xác định ma trận sinh G của bộ mã.
  Gọi w = (a1, a2, a3, a4, a5, a6, a7) là một từ mã. Chúng ta có hệ
 phương trình sau được dẫn ra từ công thức w HT = 0.
 a4 + a5 + a6 + a7 = 0
 a2 + a3 + a6 + a7 = 0
 a1 + a3 + a5 + a7 = 0
  Từ đây suy ra công thức tính các bit kiểm tra a1, a2, a4 theo các
 bit thông báo a3, a5, a6, a7 như sau
 a1 = a3 + a5 + a7
 a2 = a3 + a6 + a7
 a4 = a5 + a6 + a7
 Ma trận sinh của mã tuyến tính Hamming
 b1 b2 b3 b4 a1 a2 a3 a4 a5 a6 a7
 u = 1 0 1 0 thì w = 1 0 1 1 0 1 0
 1 1 1 0 0 0 0 
 1 0 0 1 1 0 0 
 G 
 4 7 0 1 0 1 0 1 0 
 1 1 0 1 0 0 1 
 Ví dụ
  Xét mã tuyến tính Hamming C(7, 4) có các bit thông tin nằm ở
 các vị trí 1, 2, 3, 4. Hãy xác định ma trận sinh G của bộ mã.
 98
 12/25/2010
 Bài 13 Mã vòng
13.1 Giới thiệu
13.2 Các tính chất của mã vòng
13.3 Ma trận sinh và ma trận kiểm tra của mã
13.4 Mã BCH
 Giới thiệu
 Đị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–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 +  +
 n - 2 n - 1
 an–2x + an–1x 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).
 Ví dụ
 m w w(x) m w w(x)
 0000 0000000 0 0001 0001101 x3 + x4 + x6
 1000 1101000 1 + x + x3 1001 1100101 1 + x + x4 + x6
 0100 0110100 x + x2 + x4 0101 0111001 x + x2 + x3 + x6
 1100 1011100 1 + x2 + x3 + x4 1101 1010001 1 + x2 + x6
 0010 0011010 x2 + x3 + x5 0011 0010111 x2 + x4 + x5 + x6
 1010 1110010 1 + x + x2 + x5 1011 1111111 1 + x + x2 + x3 +
 x4 + x5 + x6
 0110 0101110 x + x3 + x4 + x5 0111 0100011 x + x5 + x6
 1110 1000110 1 + x4 + x5 1111 1001011 1 + x3 + x5 + x6
 99
 12/25/2010
 Giớ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.
 i w(i) w(i)(x)
 0 1101000 1 + x + x3
 1 0110100 x + x2 + x4 = x * (1 + x + x3) = x * w(x)
 2 0011010 x2 + x3 + x5 = x2 (1 + x + x3) = x2 * w(x)
 3 0001101 x3 + x4 + x6 = x3 (1 + x + x3) = x3 * w(x)
 4 1000110 1 + x4 + x5 = x4 + x5 + x7 mod 7
 5 0100011 x + x5 + x6 = x5 + x6 + x8 mod 7
 6 1010001 1 + x2 + x6 = x6 + x7 mod 7 + x9 mod 7
 Giớ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) = xj
 Bổ đề 13.1
 w(i)(x) = [xi * w(x)] mod (xn + 1)
 Cá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 minh
  Giả sử  hai đa thức mã khác nhau, cùng có bậc nhỏ nhất là r, 0
 < r < n.
 r - 1 r
 g(x) = g0 + g1x +  + gr–1x + x
 r - 1 r
 f(x) = f0 + f1x +  + fr–1x + x
  Từ đâ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.
 100
 12/25/2010
 Cá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)
 r - 1 r
 g(x) = g0 + g1x +  + gr–1x + x
 Định lý 13.2
  Hệ số tự do g0 của g(x) phải bằng 1.
 Chứng minh
  Giả sử g0 = 0. Suy ra
 r - 2 r - 1
 g(x) = x * (g1 +  + gr–1x + x )
 r - 2 r - 1
  Đặt f(x) = (g1 +  + gr–1x + x ), 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).
 Các tính chất của mã vòng (tt)
 Định lý 13.3
  Mộ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 minh
  Chiều thuận
  Nếu v(x) = q(x) * g(x) và có bậc ≤ n – 1 thì v(x) là đa thức mã.
 p p
 v(x) q(x) * g(x) q xi * g(x) q xi * g(x)
  i  i 
 i 0 i 0
 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ã.
 Các tính chất của mã vòng (tt)
  Chiều ngược
  Nế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.
 101
 12/25/2010
 Cá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 minh
  Mỗ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ư sau
 n – k
 g(x) = g0 + g1x +  + gn – kx
 trong đó g0 = gn – k = 1.
 Cá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 minh
  Bổ đề 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.
 Các tính chất của mã vòng (tt)
 Định lý 13.6
  Nế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 minh
  Xé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).
 k – 1
 v(x) = a0g(x) + a1x * g(x) +  + ak – 1x * g(x)
 v(x) là một đa thức có bậc ≤ n – 1 và là bội số của g(x).
 102
 12/25/2010
 Cá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
 n – 1
 w(x) = b0 + b1x +  + bn – 1x
 là một đa thức của không gian.
 Chúng ta chứng minh
 (1) 2 n – 1
 w (x) = bn – 1 + b0x + b1x +  + bn – 2x
 cũng là một đa thức của không gian.
 Cá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
 n (1)
 x * w(x) = bn – 1(x + 1) + w (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.
 Ma trận sinh
 n k  1 k 1  
 g g g  g 0 0  0 
 0 1 2 n k 
 0 g 0 g1  g n k 1 g n k 0  0 
   
 Gk n 0 0 g 0 g n k 2 g n k 1 g n k 0 
          
  
 0 0 0 g 0 g1 g 2 g n k 
 Ví 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 được
 103
 12/25/2010
 Ví dụ
 x7 + 1 = (1 + x)(1 + x + x3)(1 + x2 + x3)
  Chọn chẳng hạn
 g(x) = (1 + x + x3)
 1 1 0 1 0 0 0 
 0 1 1 0 1 0 0
 G 
 4 7 0 0 1 1 0 1 0 
 0 0 0 1 1 0 1 
 Mã vòng dạng hệ thống
  Từ 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.
 1 1 0 1 0 0 0 1 0 0 0 1 1 0 
 0 1 1 0 1 0 0 0 1 0 0 0 1 1 
G G 
 4 7 0 0 1 1 0 1 0 ht(4 7) 0 0 1 0 1 1 1 
 0 0 0 1 1 0 1 0 0 0 1 1 0 1 
  Mã hóa thành từ mã hệ thống
  u(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)
 Ví 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) + x2
  Từ đâ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.
 104
 12/25/2010
 Ma trận kiểm tra của mã vòng
  Có 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
 k
 h(x) = h0 + h1x +  + hkx
  Ma trận sau là một ma trận kiểm tra của mã vòng
 k 1 n k  1 
 h h h  h 0 0  0 
 k k 1 k 2 0 
 0 hk hk 1  h1 h0 0  0 
   
 H (n k ) n 0 0 hk h2 h1 h0 0 
          
  
 0 0 0 hk hk 1 hk 2 h0 
 Ví 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à
 1 0 1 1 1 0 0 
 H 3 7 0 1 0 1 1 1 0 
 0 0 1 0 1 1 1 
 Ứng dụng trường GF(2m)
 để xây dựng mã vòng
 Định lý 13.7
  Cho 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ó.
 2 n – 2 n–1
 Hm n = [1 a a  a a ]
 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 + x4
 105
 12/25/2010
 Ứ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).
 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 
 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0
H 
 4 15 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 
 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 
 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)
 Ứ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)
 1 0 0 0 1 
 0 1 0 0 1
 H 
 4 5 0 0 1 0 1 
 0 0 0 1 1 
 Mã BCH nhị phân
 Do 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 + 1
 106
 12/25/2010
 Định lý
 Định lý 13.8
  Cho 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ó.
 1 a a 2  a n 2 a n 1 
 3 6 3(n 2) 3(n 1) 
 1 a a  a a 
 H 1 a 5 a10  a 5(n 2) a 5(n 1) 
       
 2t 1 2(2t 1) (2t 1)((n 2) (2t 1)((n 1) 
 1 a a  a a 
 Đị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.2
  Ma trận A sau có định thức bằng (yi y j )
 i j
 với i, j {1, 2, , r}. Định thức này được gọi là định thức
 Vandermonde. 1 1  1 
  
 y1 y2 yr 
 A y 2 y 2  y 2 
 1 2 r 
     
 r 1 r 1 r 1 
 y1 y2  yr 
 Ví 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
 4
 sau f1(x) = 1 + x + x
  Đâ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.
 1 a a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a12 a14 
 H 3 6 9 12 15 18 21 24 27 30 33 36 39 42 
 1 a a a a a a a a a a a a a a 
  Thay mỗi phần tử ai bằng vectơ 4 thành phần tương ứng
 107
 12/25/2010
 Ví dụ (tt)
 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 
 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 
 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 
 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
 H 
 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 
 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 
 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 
 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 
 Ví 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à
 2 3 4
 f3(x) = 1 + x + x + x + x .
  Từ đây suy ra
 g(x) = f1(x) * f3(x)
 = (1 + x + x4) * (1 + x + x2 + x3 + x4)
 = 1 + x4 + x6 + x7 + x8
 Chú ý
  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.
 108