Ả
Ọ
Ế
BÀI GI NG MÔN H C LÝ THUY T THÔNG TIN
Mã vòng
ớ
ệ i thi u
ấ ủ
ủ
ể
ậ
ậ
13.1 Gi 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
Trang 2
ớ
ệ
Gi
i thi u
n Đ nh nghĩa
ộ
ị n M t mã tuy n tính
c g i là mã vòng n u ế w =
C(n, k) đ ộ ừ ượ ọ mã thì v = an–1a0a1…an–2 cũng
ộ ừ ế a0a1…an–2an–1 là m t t là m t t
ế ả mã thì k t qu
ả ướ ị mã. ị ộ ừ ộ ừ n Nghĩa là d ch vòng (sang trái hay ph i) m t t ả Ở c d ch ph i. cũng là m t t đây qui mã.
ứ
n Đa th c mã
n N u ế w = a0a1…an–2an–1 là m t t
ộ ừ
w(x) = a0 + a1x + ớ ừ ươ ứ ng ng v i t
n Ví dụ ả
mã thì ứ … + an–2xn 2 + an–1xn 1 là đa th c mã t mã w.
n B ng sau đây trình bày m t mã vòng
Trang 3
ộ C(7, 4).
Ví dụ
m w m w w(x) w(x)
0000 0000000 0 0001 0001101 x3 + x4 + x6
1000 1101000 1 + x + x3 1100101 1 + x + x4 + x6 1001
0100 0110100 x + x2 + x4 0111001 x + x2 + x3 + x6 0101
1100 1011100 1 + x2 + x3 + 1101 1010001 1 + x2 + x6
x4
0010 0011010 x2 + x3 + x5 0011
0010111 x2 + x4 + x5 + x6
1010 1110010 1 + x + x2 + 1011
x5
Trang 4
1111111 1 + x + x2 + x3 + x4 + x5 + x6
0110 0101110 x + x3 + x4 + 0111 0100011 x + x5 + x6
x5
1110 1000110 1 + x4 + x5 1111 1001011 1 + x3 + x5 + x6
ớ
Gi
ệ i thi u (tt)
n w(i), w(i)(x) ừ n w(i) là t ươ ứ
ị ừ ứ mã do d ch t w i bit, và w(i)(x) là đa th c mã
t
i mã ủ w(i). w(0) chính là w. w(i)(x) ng ng c a w(i)
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)
Trang 5
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)
n 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 x đ
n M c khác trên tr
ượ ặ p mod n. ườ GF(2) chúng ta có ng
xn + j = xj *
(xn + 1) + xj hay xn + j mod (xn + 1) = xj
ổ ề n B đ 13.1
w(i)(x) = [xi
Trang 6
* w(x)] mod (xn + 1)
ấ ủ Các tính ch t c a mã vòng
n Đ nh lý 13.1
ứ ấ ấ ậ
ị ỏ n Đa th c mã khác 0 có b c nh nh t là duy nh t. Hay nói cách ứ i hai đa th c mã khác 0, khác nhau và cùng
ậ
ỏ n Ch ng minh
ứ ấ ậ ỏ ồ ạ khác không t n t ấ có b c nh nh t. ứ n Gi hai đa th c mã khác nhau, cùng có b c nh nh t là r,
ả ử (cid:0) s 0 < r < n.
g(x) = g0 +
g1x + … + gr–1xr 1 + xr
f(x) = f0 + f1x
+ … + fr–1xr 1 + xr
Trang 7 ứ
ừ ứ ậ ỏ ơ r, mâu
n T đây suy ra đa th c mã thu n. Ch ng minh hoàn t
ẫ g(x) + f(x) có b c nh h n ấ t.
ấ ủ
Các tính ch t c a mã vòng (tt)
n Kí hi u đa th c mã có b c nh nh t là g(x)
ứ ệ ậ ấ ỏ
g(x) = g0 +
g1x + … + gr–1xr 1 + xr
ệ ố ự ả ằ ủ do g0 c a g(x) ph i b ng 1.
ị n Đ nh lý 13.2 n H s t n Ch ng minh
ả ử
ứ n Gi
s g0 = 0. Suy ra
g(x) = x * (g1
+ … + gr–1xr 2 + xr 1)
ặ ộ ượ ị c d ch trái 1
n Đ t f(x) = ứ m t đa th c mã. Vì f(x) t ị bit hay d ch ph i ( Trang 8 ậ ủ
ớ ừ ứ mã ng v i g(x). ả n – 1) bit t
mã đ ớ ớ ị ủ ẫ ằ (g1 + … + gr–1xr 2 + xr 1), suy ra f(x) cũng là ươ ứ ng ng v i t ừ ừ t n 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)
n Đ nh lý 13.3 ộ
ậ ứ v(x) trên tr ườ GF(2) có b c ≤
ị n M t đa th c ế
ỉ ế n – 1 là đa th c ứ ng ể ộ ộ ố ủ g(x). T c là nó có th ứ
t ế v(x) = q(x) * g(x).
mã n u và ch n u nó là m t b i s c a vi ứ n Ch ng minh
ề ậ
n Chi u thu n 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
(cid:0) (cid:0)
i x
i x
v
q
q
q
x )(
x x g )(*)(
x g )(*
x g )(*
i
i
i
i
0
0
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
Trang 9 ứ
v i ớ p là b c ậ i ≤ p là đa th c ứ ủ ế h p tuy n tính c a
c a ủ q(x) và p + r ≤ n – 1. Do xi * g(x) v i 0 ≤ ớ ộ ổ ợ ứ mã, nên v(x) là đa th c mã vì nó là m t t các đa th c mã.
ấ ủ
Các tính ch t c a mã vòng (tt)
ứ ượ ề n Chi u ng c n 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 ườ GF(2) chúng ta có th suy ra ng
r(x) = q(x) *
g(x) + v(x)
Nên r(x) là
ị ủ g(x) suy ra r(x) = 0.
ộ ứ ứ m t đa th c mã. Theo đ nh nghĩa c a Trang 10 ấ Ch ng minh hoàn t t.
n T đ nh lý này chúng ta g i
ừ ị ứ , vì t ừ g(x) có ọ g(x) là đa th c sinh
ể ấ ả ứ th sinh ra t t c các đa th c mã khác.
ấ ủ
Các tính ch t c a mã vòng (tt)
n Đ nh lý 13.4
ứ ộ
ị ủ n Đa th c sinh c a m t mã vòng
C(n, k) có b c ậ r = n – k.
ứ
n Ch ng minh ứ ỗ
n M i đa th c mã
w(x) là m t b i s c a ộ ộ ố ủ g(x)
w(x) = q(x) *
g(x)
n Có 2k t
ừ 2k đa th c ứ q(x). Suy ra b c c a ậ ủ q(x) là (cid:0)
ừ ị ứ ể ượ ể mã nên có ậ ủ k – 1. Suy ra b c c a g(x) là n T đ nh lý này đa th c sinh n – k. g(x) có th đ ư ễ c bi u di n nh
sau
g(x) = g0 + g1x + … + gn – kxn – k
Trang 11
trong đó g0 =
gn – k = 1.
ấ ủ
Các tính ch t c a mã vòng (tt)
n Đ nh lý 13.5
ứ ủ C(n, k) là m t ộ ướ ố ủ xn + 1. c s c a
ị n Đa th c sinh c a mã vòng
ứ
n Ch ng minh
n B đ 13.1 suy ra
ổ ề
g(i)(x) = [xi *
g(x)] mod (xn + 1)
(cid:0) xi * g(x) =
q(x) * (xn + 1) + g(i)(x)
Ch n ọ i = k (cid:0)
q(x) = 1 t cứ
Trang 12
xk * g(x) =
(xn + 1) + g(i)(x)
(cid:0) 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), (cid:0) 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)
n Đ nh lý 13.6
ứ
ị ộ n N u ế g(x) là m t đa th c có b c
ậ (n – k) và là c s c a
ủ ộ C(n, k) nào đó.
n Xét k đa th c ứ g(x), x * g(x), …, xk – 1 * g(x).
ướ ố ủ (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 ứ ứ n Ch ng minh
Các đa th c ứ
ề ậ này đ u có b c ≤ n – 1.
ộ ổ ợ ứ ớ ế h p tuy n tính c a ủ k đa th c này v i các h s G i ọ v(x) là ệ ố ai (cid:0)
m t t GF(2).
Trang 13
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).
ấ ủ
Các tính ch t c a mã vòng (tt)
n Có t
ạ ấ ả 2k t t c v(x) khác nhau và t o nên m t
ộ ớ g(x), x * g(x),
ứ ế ổ ợ h p tuy n tính ủ ế ứ không gian tuy n tính c a các đa th c mã v i ơ ở …, xk – 1 * g(x) là các đa th c làm c s .
Chúng ta
ằ ộ ươ ứ ớ ng ng v i không gian này là mã
ứ ch ng minh r ng b mã t 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
Trang 14 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.
ấ ủ
Các tính ch t c a mã vòng (tt)
n 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à ộ ủ g(x).
Trang 15
ứ ứ ấ (xn + 1) đ u là b i c a Suy ra w(1)(x) cũng là đa th c mã. Hoàn t ộ ủ g(x) nên w(1)(x) cũng là b i c a t ch ng minh.
ậ Ma tr n sinh
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
g
0
kn
1
2
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
k 0 0
kn
kn
1
1
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
G
g g
g
nk
2
1
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
0 0 0
kn g g g g g 0
0 0
1 g g g
kn
kn
kn
1 0 0 0
(cid:0) (cid:0)
(cid:0) (cid:0)
g
g
g
g
0
0
0
kn
0
1
2
(cid:0) (cid:0) (cid:0)
n Ví dụ
(cid:0) (cid:0) (cid:0) (cid:0)
C(7, 4).
Trang 16
ứ ủ
ộ n Tìm m t mã vòng n Theo các tính ch t c a mã vòng suy ra đa th c sinh c a mã có c s c a ộ ướ ố ủ x7 + 1. Phân tích đa th c ứ ấ ủ 3 và là m t ậ ằ b c b ng
ừ ố ượ này ra th a s chúng ta đ c
Ví dụ
x7 + 1 = (1 +
x)(1 + x + x3)(1 + x2 + x3)
ẳ ọ ạ n Ch n ch ng h n
g(x) = (1 + x
0001011
+ x3) (cid:0) (cid:0)
0010110
(cid:0) (cid:0)
74G
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
0101100 1011000
Trang 17
(cid:0) (cid:0)
ệ ố
ạ Mã vòng d ng h th ng
n T d ng h th ng lo i
ể ị k bit đ ể
ừ ạ ế ổ ệ ố ạ bi n đ i sang d ng h th ng lo i ạ 1 chúng ta có th d ch vòng ạ 2 và ng ệ ố ượ ạ c l i.
0001011
(cid:0) (cid:0) (cid:0) (cid:0)
0110001 1100010
(cid:0) (cid:0) (cid:0) (cid:0)
74G
)74(htG
1110100
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0) (cid:0) (cid:0)
0010110 0101100 1011000
1011000
(cid:0) (cid:0) (cid:0) (cid:0)
ừ
n Mã hóa thành t
mã h th ng
ệ ố ừ
n 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) Trang 18
w(x) = xn–k * u(x) + a(x) = q(x) * g(x)
Ví dụ
ậ
g(x) = (1 + x + x3). n Cho mã vòng C(7, 4) có ma tr n sinh là ệ ố ừ 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
n T đây suy ra
ừ
w(x) = x2 +
x3 + x5
Trang 19
w = 0011010
ừ là t ệ mã h
ạ ố ươ ứ th ng d ng 2 t ng ng v i ớ u.
ủ
ể
ậ
Ma tr n ki m tra c a mã vòng
n 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)
n h(x) đ
ượ ọ ứ ố c g i là đa th c đ i ng u c a ẫ ủ g(x). h(x) có b c ậ k
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
kn 0
1
2
ủ
(cid:0) (cid:0) ậ (cid:0) (cid:0)
1
(cid:0) (cid:0) (cid:0)
H
kn
n
)
(
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1 h ể ậ 0 h 1 h 2
h ộ k h k 0
k h k h k h k
0 h 0 h 1
0 h 0
0 0
(cid:0) (cid:0) h(x) = h0 + 1 0 n Ma tr n sau là m t ma tr n ki m tra c a mã vòng h1x + … + hkxk h k 0 0
(cid:0) (cid:0)
0
0
h k
h k
h k
1
2
h 0
0 Trang 20
(cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0) (cid:0) (cid:0)
Ví dụ
n 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)
n Ma tr n ki m tra c a b mã là
(cid:0) (cid:0) ể ậ ủ ộ
0011101 0111010
73H
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1110100
Trang 21
(cid:0) (cid:0) (cid:0) (cid:0)
Ứ
ườ GF(2m)
ng
ể
ụ ng d ng tr ự đ xây d ng mã vòng
n Đ nh lý 13.7
khác
ầ ử ng ể f(x) c a ủ a có b c là
ộ
ầ ử ườ GF(2m) có chu k là ỳ ủ 0 c a tr m. Thì mã có ma tr n ậ ậ C(n, n – m), trong đó ế ằ c thay th b ng
ị ộ n Cho a là m t ph n t ứ ố n, đa th c t i thi u ậ ể sau làm ma tr n ki m tra là m t mã vòng ướ ượ ậ ỗ i đ trong ma tr n bên d m i ph n t ủ ầ ươ ứ ng ng c a nó. vect
ơ m thành ph n t
Hm(cid:0) n = [1 a
a2 … an – 2 an–1]
ơ ữ H n n a mã
n Ví dụ
ứ vòng này có đa th c sinh chính là f(x).
n Xét tr
ứ ố ể i thi u là ườ GF(24) và a có đa th c t ng Trang 22
f(x) = 1 + x +
x4
ng
ụ ng d ng tr ể
ự
ườ GF(2m) Ứ đ xây d ng mã vòng (tt)
ủ ừ ậ ể n T đây suy ra ma tr n ki m tra c a mã vòng (15, 11).
(cid:0) (cid:0) 111010110010001
(cid:0) (cid:0)
154H
001111010110010 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 011110101100100 (cid:0) (cid:0)
(cid:0) (cid:0) 111101011001000
ứ ố ế
n N u đa th c t có chu k là ỳ sau.
ượ ể i thi u c a 5 và các ph n t ể ủ a là f(x) = 1 + x + x2 + x3 + x4 thì a ư ễ c bi u di n nh ầ ử 1, a, ..., a4 đ
1 = (1000) a3 = (0001)
Trang 23
a = (0100) a4 = (1111)
a2 = (0010)
ng
ụ ng d ng tr ể
ự
ườ GF(2m) Ứ đ xây d ng mã vòng (tt)
ủ ừ ậ ể n T đây suy ra ma tr n ki m tra c a mã vòng (5, 1)
(cid:0) (cid:0)
(cid:0) (cid:0)
54H
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
10001 10010 10100 11000
Trang 24
(cid:0) (cid:0)
ị
Mã BCH nh phân
ả c nhi u l ậ i.
n Do Bose, Chaudhuri và Hocquenghem sáng l p ra. ử ượ n Là mã vòng có kh năng s a đ ố ng n Đ i v i các s nguyên d
ẽ
ộ ị
ộ ề ỗ ấ ỳ ươ 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
Trang 25
Hamming: dmin ≥ 2t + 1
ị
Đ nh lý
n Đ nh lý 13.8
ứ ố
ị n Cho a là m t ph n t
ng ườ GF(2m) có đa th c t
ộ ộ ứ ậ ể i thi u ậ m. Thì mã có ma tr n sau làm ma
ậ ể ả
ộ ầ ử ỗ 2t + ế c thay th ướ ượ i đ
ủ ầ ử ủ c a tr ả là m t đa th c căn b n b c tr n ki m tra là m t mã vòng có kho ng cách Hamming ≥ 1, trong đó m i ph n t ằ b ng vect ơ m thành ph n t
n
n
2
1
(cid:0) (cid:0) ậ trong ma tr n bên d ầ ươ ứ ng ng c a nó. 2 (cid:0) (cid:0)
n
n
6
)2
)1
a 3 a
a (3 a
a (3 a
1 1
(cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
n
n
5
a a 10
(5
)2
(5
)1
H
a
a
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1
(cid:0) (cid:0)
(cid:0) (cid:0)
t
n
t
n
a t 12
a t )12(2
)((12(
)2
)((12(
)1
a
a
a
a 1 Trang 26
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
ị
Đ nh lý (tt)
n H n n a đa th c sinh ấ ủ
ứ
ơ ữ ỏ ể ủ ứ ộ ố g(x) c a b mã là đa th c b i s chung ầ ử a, a3, a5, ứ ố ủ ộ i thi u c a các ph n t
y
j
i
j
) ứ
(cid:0) (cid:0) nh nh t c a các đa th c t …, a2t–1. ổ ề n B đ 13.2 n Ma tr n ậ A sau có đ nh th c b ng (cid:0)
y ( ứ ằ i ị {1, 2, …, r}. Đ nh th c này đ
ượ ọ c g i
ứ ị là đ nh th c Vandermonde. (cid:0) (cid:0)
(cid:0) (cid:0)
2 2
r 2
(cid:0) (cid:0)
A
(cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
(cid:0) (cid:0)
1 y y 2 r
1 y y r r
1
1
1
y
y
r
y 1
2
Trang 27
(cid:0) (cid:0) (cid:0) ị v i ớ i, j (cid:0) 1 y 1 2 y 1 r (cid:0) (cid:0) (cid:0) (cid:0)
Ví dụ
n Cho m = 4, t = 2 chúng ta s xây d ng m t mã vòng có chi u
ẽ ộ
ự ả ừ 24 – 1 = 15 và có kho ng cách Hamming ề d ≥ 5.
ườ ng GF(24).
n G i ọ a là ph n t
ứ ố ể ậ ả mã là dài t ẽ ự ự ệ Vi c xây d ng s d a vào tr ầ ử có đa th c t
ứ i thi u là đa th c căn b n b c 4 f1(x) = 1 + x + x4 sau
ụ ở ườ GF(24) trong ví d ng
n Đây chính là tr n a có chu k ỳ n = 2m – 1 = 15. Chúng ta có ma tr n ki m tra c a
4
3
5
6
7
8
9
10
11
12
12
14
slide 250. ể ậ ủ
(cid:0) (cid:0)
H
9
6
30
33
36
39
42
(cid:0) (cid:0) (cid:0)
a 3 a
a 15 a
a 18 a
a 21 a
a 24 a
a 27 a
a a
a a
a a
a a
a a
(cid:0) (cid:0) ư a a ộ b mã nh sau. 2 a a 1 12 a a 1
ằ ầ ươ ứ ầ ử ai b ng vect ơ 4 thành ph n t ng ng ỗ n Thay m i ph n t Trang 28
Ví d (tt)ụ
111010110010001
(cid:0) (cid:0)
001111010110010
(cid:0) (cid:0)
(cid:0) (cid:0)
011110101100100
(cid:0) (cid:0)
111101011001000
(cid:0) (cid:0)
H
100011000110001
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
110001100011000
(cid:0) (cid:0)
101001010010100
(cid:0) (cid:0)
(cid:0) (cid:0)
111101111011110
Trang 29
(cid:0) (cid:0) (cid:0) (cid:0)
Ví d (tt)ụ
n Đ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.
n Theo ví d
ụ ở ứ ố slide 250, đa th c t i thi u c a ể ủ a3 là
f3(x) = 1 + x + x2 + x3 + x4.
n T đây suy ra
ừ
g(x) = f1(x) * f3(x)
= (1 + x + x4) * (1 + x + x2 + x3 + x4)
n Chú ý
= 1 + x4 + x6 + x7 + x8
n Trong tr ứ
i thi u c a
ả ề ượ ể ủ a không ph i là đa n (cid:0) c mã vòng có chi u dài
ườ ng h p đa th c t ả Trang 30 ợ th c căn b n, chúng ta s tìm đ 2m + 1, v i ớ n là chu k c a ứ ố ẽ ỳ ủ a.
