Báo cáo mã BCH


! "#$%&'()(&*+,'' /./
-! 01&'()(&*+,'' 2/-
2! '3&'()(&*+,'' *
!
• 4567 689:;6<=>?$$@A"BCDE"CF6G8HI
JK(4;""$L M/.N75JO"KKL M*MN
• 4P"$QCR8J8QJ7J7SCT"GJU9
• ,945CDEVW"$J66XBU4YBYYBZC[;B''Y79;
W"

• \L8N867 R"R
U8:L.B B]B8( N
U8^8JU_7`KJJ"6J(8
• Oa8

67R"3
\LON%67$@I$Fb\L8N
• );EHG$\L8N


B.c c 6778d;\L8Ne

f.
• g"

LhN

a 7S1T8?i7id;-C;EHGj3$

\L8N

LhN%67C;E"d
• :"d$\LONkf."F\LONj;9k
O(
a

• );ERT"d; 8:67C;EHGP8P

a 78:Cl67
d;mkLhN
• 45CD>?$\L-

NB3I67\L-N
@C?BHnUF7?UC;EHGj3KJJ"6J(LhNB;o"CD$@
I$F!
YLhNah
-
_h_ 67C;E"d$\L-N!;>?CD\L-
-
Na\LpN
;hah

Bh_ ah
-
B ah
2
-
 
!"#$%&'()*"+,*"+"

HPS-R"37Jj;9≥3 và t<2
m-1
Q;T>?HF945
U1R
! )F79a-q(
-! 'RHST$;(S≤
2! &JUjP≥ -_
"CDHF45JKLBSBN
-./01)
gSgHF945:;;6<B%r678:"d$\L-

N
LhN67C;E945CDCs[;67C;EHGjP$\L-NGrBr
-
]Br
-

67
LhNat4,um
r


LhNB ≤ ≤-v
m
r


LhNa B-Bp]67R;"!;"$;
Gd;m
r



LhNS1DO"U(S≤ 
YLhNa
(S
h
(S
_
(S(
h
(S(
_]_

h_
.
;C;Eb9

LhNa"

LhNLhN
LhN67 C;Eb9Lr

Na. ≤ ≤-!)?l67CW"S7CdCT C;EHGj
3T$I7C;Eb9d;45
>UCsURd;LhN$JHU8?
2
lV45:;;a Ba+BSap 2
w
a .
-

YJCBLhNah
2
_h_
p
2./)301)
Y"LhNa"
S(
h
S(
_"
S(-
h
S(-
_]_"

h_"
.
$JCL"
S(
B"
S(-
B]B"
.
NCJSH;XB-
S
C;E;X
p!,9;LYKJN
 !bHFLBSBN>UCsC;ELhN
-!4JC;E;X"LhN!bKJ$C;E
$LhNaxh

(S
"LhNyJLhN
L>Nah
(S
"LhN_$LhN
2!4"TL>NWKJ$
lVLBSBNaL *B+B-Nz"aL. N
 +-
w
a .
-
LhNah
w
_h
+
_h
/
_h
p
_
-"LhNah
/
_h
*
_h
-
_h
h
w
"LhNah

p
_h
2
_h
.
_h
M
$LhNaLh
p
_h
2
_h
.
_h
M
NJLh
w
_h
+
_h
/
_h
p
_ Nah
2
_
LhNah
w
"LhN_$LhNah
p

_h
2
_h
.
_h
M
_h
2
_

24JK{J$L N
45)6
!789)01"8:
Lr

Na. ≤ i ≤ 2t
Y,;$Ga. cc-
)|;$G5
67b9d;45(6<!5

a.
*
5%67;$GST$;
g"r
i
7 r
j
67-R6D8L B-Bp]N(r
i
Na.S7}SLr

j
) = 0
;GCD;$GST$;"%
-;#(/<=>/<?;@A1) 0
KJ$;KaLK
.
BK

B]BK
(
N
YA6"GCD$a_K
'$JK'a$5

aL_KN5

aK5

aL'

B'
-
B]B'
-
N
 cc-
&1PiZO"UBg~6<;Us$l•

B•
-

B]B•
~
L.€•

ۥ
-
€]€•
~
€

N
;
'Rs$l6<k
6
ar
•6
/

)TU83$$BQ;:VC;Es$l6<
467  cc~
)•P83$$B;
b 7-O"; R8^8HgCZB"CD
+
-
hUCs‚LhN7
27#0BBC
lV
L *B*B2N45$\L /N
);ELhNah
.

_h
w
_h
*
_h
p
_h
-
_h_ eLhNa.
b9GCD$LhNah
2
_h
/
lJU'$JK
~a2
w
~a-
5""Pƒ
REED-SOLOMON CODES
„! Giới thiệu mã Reed-Solomon
• Mã Reed - Solomon đã được NASA (Cục Quản trị Hàng không và Không
gian Quốc gia Hoa Kỳ) sử dụng vào truyền thông trong vũ trụ từ năm
1977.
• Mã Reed - Solomon được Reed và Solomon giới thiệu lần đầu tiên vào
năm 1960, là một mã sửa sai thuộc loại mã tuyến tính. Mã Reed -
Solomon là một lớp con của mã BCH. Mã BCH (mã Bose, Chaudhuri và
Hocquenghem) là một loại mã sửa lỗi vòng ngẫu nhiên quan trọng, có
khả năng sửa được nhiều lỗi và được ứng dụng rộng rãi, có 2 lớp con là
mã BCH nhị phân và mã BCH không nhị phân. Trong số những mã BCH
không nhị phân này, lớp quan trọng nhất là mã Reed - Solomon.

• Mã Reed - Solomon còn là một lớp quan trọng của Mã tách có khoảng
cách cực đại (MDS). Với tư cách là mã MDS, mã Reed - Solomon còn có
vai trò quan trọng trong việc làm tăng độ an toàn của các mã khối chống
lại những tấn công đã biết như tấn công tuyến tính, tấn công lượng sai.
• Mã Reed - Solomon được sử dụng để sửa các lỗi trong nhiều hệ thống
thông tin số và trong lưu trữ, bao gồm: Các thiết bị lưu trữ (băng từ, đĩa
CD, VCD v.v ), thông tin di động hay không dây (điện thoại di động,
các đường truyền Viba), thông tin vệ tinh, truyền hình số DVB, các
modem tốc độ cao như: ADSL, VDSL v.v (xDSL). Mã Reed - Solomon
đặc biệt quan trọng trong việc sửa các burst lỗi (bit lỗi xảy ra gần nhau).
M
Hệ thống truyền tin sử dụng mã Reed-solomon.
„„! Các định nghĩa liên quan
! Vành đa thức
Xét tập hợp các đa thức có bậc không lớn hơn n-1 sau:
f
i
là các hệ số được lấy giá trị trong một trường F nào đó.
Trên tập các đa thức này ta xác định 2 phép toán trong là phép cộng đa thức và
phép nhân
đa thức như sau:
a, Phép cộng đa thức
Xét hai đa thức sau:
Ta có:
.
Ở đây phép cộng các hệ số a
i
và b
i
được thực hiện trên trường F

Nếu ta coi mỗi đa thức có bậc nhỏ hơn hoặc bằng n-1 là một véctơ trong không
gian
tuyến tính n chiều V
n
thì phép cộng đa thức hoàn toàn tương tự như phép cộng
véctơ.
Ví dụ1:Xét n = 7, F = GF(2)
b, Phép nhân đa thức
Để tích của hai đa thức có bậc ≤n−1 vẫn là một đa thức có bậc ≤ n−1 ta phải
thực hiện
phép nhân 2 đa thức theo mođulo X
n
+ 1 (tức là coi X
n
=1)
Ta thấy rằng tích của hai đa thức được thực hiện trên cơ sởtích của hai đơn thức
x
i
và x
j
.

-! Trường <F,+,* >
là một tập hợp các phần tử với hai phép toán trong hai ngôi thỏa mãn:
<F,+> là một nhóm cộng
<F
*
,i> là một nhóm đối với phép nhân.
Trong đó:
F

*
= F\{0}
Ví dụ3: Trường nhị phân Galois GF(2): Trường này chỉ có hai phần tử 0 và 1.
2! Đa thức a(X) được gọi là bất khả quy nếu nó không thể phân tích thành
tích các đa thức có bậc nhỏ hơn
p! Định lý: Với n=2
m
-1, đa thức X
n
+1 được phân tích thành tích của tất cả
các đa thức bất khả quy có bậc m và ước của m.
„„„! Xây dựng trường hữu hạn GF sử dụng cho mã RS
1. Trường hữu hạn cỡ nguyên tố GF(p)
Các phép toán số học cộng và nhân giữa 2 phần tử của trường được thực hiện
theo modulo p. . Trong trường GF(p) người ta đã chứng minh được rằng tồn tại
ít nhất một phần tử mà các lũy thừa của nó là các phần tử khác 0 của trường.
Phần tử này được gọi là phần tử nguyên thủy. Ví dụ trong trường GF(7) số3 là
phần tử nguyên thủy vì:
-! Các trường mở rộng của trường nhị phân. Trường hữu hạn GF(2
m
)
Người ta cũng chứng minh được rằng luôn tồn tại một phần tử nguyên thủy
trong trường và các phép toán số học sẽ được thực hiện theo modulo của một đa
thức nào đó trên GF(p). Ta chỉ quan tâm đến trường hợp p=2.
Giả sử ta cần tạo một trường hữu hạn GF(q) và ký hiệu a là phần tử nguyên
thủy của nó. Các lũy thừa của α(α
0
đến α
q - 2
)gồm q-1 phần tử khác

không của trường. Đối với trường GF(2
m
) ta có:
-
Nhân thức mà ta chọn phải là bất khả quy và không là nhân thức của 
đối với bất kỳ giá trịn
nào nhỏ hơn 2
m
-1. Nhân thức thỏa mãn các tính chất trên chính là đa thức
nguyên thủy có bậc m.
Cảhai đa thức bậc 3 ở trên đều là các đa thức nguyên thủy và ta có thể chọn tùy
ý. Giả sử ta tạo các lũy thừa của α theo điều kiện α
3
+ α +1 = 0. Khi đó các phần
tử khác không của trường là:
2! Biểu diễn đa thức cho trường hữu hạn GF(2
m
)
Ví dụ: Xét GF (2
3
) , biểu diễn cho 8 phần tử của trường này có thể viết nhưsau:
2
Ở đây dãy 3 bít được dùng để mô tả cho biểu diễn đa thức của các phần tử. Phép
cộng được thực hiện bằng cách cộng modulo 2 theo từng bít của dãy
p! Các nghiệm của đa thức của trường hữu hạn
Một đa thức bất khả quy trên trường hữu hạn luôn có thể phân tích được trong
một trường mở rộng nào đó. Nếu f(X) là một đa thức bất khả quy q phân thì
f(X) sẽcó các nghiệm trong một trường mở
rộng nào đó, tức là f(X) có thể biểu diễn bằng tích của một số hạng có dạng
x+β

i
với
β
i
là phần tửcủa GF(q
m
). Hơn nữa nếu β là một nghiệm nào đó thì có thể thấy
rằng các nghiệm khác có dạng
Với đa thức nhị phân bất khảquy có nghiệm β thì các nghiệm liên hợp là
Nếu β là một nghiệm của f(X) thì β
q
cũng là một nghiệm. Đa thức
f(X) được gọi là đa thức tối tiểu của β. Nếu β là phần tử nguyên thủy thì f(X) là
một đa thức nguyên thủy. Nhưvậy có thể sinh ra một trường hữu hạn từ một
phần tử nguyên thủy là một nghiệm của đa thức nguyên thủy.
p
*! Các phần tử của trường hữu hạn xem như các nghiệm của một đa thức
Các nghiệm của nhị thức :
chính là các phần tử khác không của GF(2
m
)
/! Các nghiệm của một đa thức bất khả quy
Tất cả các đa thức bất khả quy bậc m là nguyên thủy nếu 2
m
-1 là số nguyên tố.
Các nhân thức của chứa tất cả các đa thức bất khả quy bậc m.
+! Xác định các mã bằng các nghiệm
Ta có thểxác định một bộmã bằng cách cho rằng các từ mã là các đa thức nhị
phân có các nghiệm xác định trong GF(2
m

). Chẳng hạn nếu nghiệm là α trong
GF(8) thì đa thức tối tiểu là X
3
+ X +1 và tất cả các từ mã phải chia hết được
cho đa thức này. Trong trường hợp này, đa thức tối tiểu đóng vai trò như đa
thức sinh của mã. Một cách tổng quát ta có thểcoi đa thức sinh là BCNN của
các đa thức tối tiểu của các
nghiệm được xác định. Bậc của đa thức (chính là số dấu kiểm tra của mã) là số
các nghiệm phân biệt sao cho tổng số các nghiệm là số dấu kiểm tra .
Nếu đa thức mã v(X) có một nghiệm βthì v(β) = 0
Cho v
n
là hệ số của X
n
, khi đó:
Ở dạng véctơ ta có thể viết như sau:
*
Tương tự, nếu v(X) có j nghiệm từ β
1
đến β
j
thì :
Ta biết rằng:
v.H
T
=0
Như vậy ma trận chuyển vịcủa ma trận ở trên chính là ma trận kiểm tra của mã.
Các nghiệm đều là các đa thức của α (ta cũng xem nhưlà các véctơvà chúng
cũng phải được chuyển
vị), bởi vậy ta có thểviết:

„! Mã RS
Là mã BCH q phân có độ dài q
m
-1. Trong GF(q
m
) đa thức tối thiểu của một phần
tử β đơn giản chỉlà (x−β). Bởi vậy đa thức sinh của mã RS có dạng:
trong đó α là phần tử nguyên thủy của trường. Bậc của g(x) bằng 2t, như vậy
với mã RS n-k=2t, khoảng cách của mã RS:
d
0
= n-k+1
/
tL>N

…$$J$
4J$$KJ$
>
†‡‡

…$$J$
,;"K
\J$Kˆ
;6J$
„‡
$L>N
'$JK
4;6"6;J$
…$$J$
J6J;6

K$6KS;8ˆ
‰6J$
…$$J$
tJ;XJ
4K
K;$
L>N
5 !4P"$QHF9
Các hệ số của g(x) nằm trong GF(8). Đây là mã RS(7,3) có 8
3
từ mã.
IV. Thực hiện giải mã RS.
Hình 1 mô tả năm thành phần chính trong cấu trúc bộ giải mã. Trong đó:
r(x) Từ mã nhận được ( đầu vào bộ giải mã)
s
i
Syndrome
L(x) Đa thức vị trí lỗi
x
i
Vị trí lỗi
y
i
Giá trị lỗi
c(x) Từ mã được gửi đi ( đầu ra bộ giải mã)
Như vậy, thuật toán giải mã gồm 5 bước chính sau đây:
+
Syndrome calculator : Tính các giá trị S
i
= r(α

i
) , 1≤ i ≤ 2t. Những giá trị S
i
này
được gọi là syndrome.
Berlekamp’s algorithm : Tìm đa thức vị trí lỗi L(x), và số lỗi υ. Thuật toán này
liên quan đến việc giải quyết đồng thời các phương trình ƒn s.
Chien search : Đưa ra L(x) và υ, tìm hệ số x
i
của L(x).
Forney’s algorithm : Từ các syndrome và hệ số của L(x), tìm giá trị của symbol
lỗi y
i
. Thuật toán này liên quan đến việc giải quyết đồng thời các phương trình
với s ƒn số.
Error corrector : Kết hợp các kết quả tính toán ở trên và xây dựng lại tin
4.1. Syndrome
Do từ mã từ nguồn tin truyền đến nhận tin luôn có thể bị sai sót, nên đa thức
tin mà bên thu nhận được là r(x) nói chung khác c(x). Khi đó, ta định nghĩa một
đa thức sai e(x) thỏa mãn:
Để đánh giá tính đúng sai của bản tin nhận được, ta sẽ tính giá trị của e(x) tại
các nghiệm của g(x) là .
Các giá trị S
i
này được gọi là các Syndrome. r(x) là từ mã nếu tất cả các
Syndrome bằng 0, ngược lại thì r(x) không phải từ mã, nghĩa là trong bản tin
nhận được có chứa lỗi sai.
Do

Từ (4.1.1), (4.1.2) =>

 Ta có thể tính các Syndrome thông qua r(x)
Nhắc lại rằng: S
i
= 0 khi và chỉ khi bản tin nhận được là từ mã, ngược lại thì
trong đó có sai sót.
w
4.2. Tìm vị trí sai và giá trị sai.
Một tính chất quan trọng của đa thức sai e(x) là nó cho ta biết cả vị trí sai và
giá trị sai trong bản tin. Giả sử các giá trị sai là và các giá trị sai tại các vị trí đó
lần lượt là Ta sẽ có:
Vì số lỗi không được vượt qua s nên
Theo (4.1.3) ta có:
(4.2.
1)
Giải hệ phương trình trên ta sẽ thu được v vị trí sai và v giá trị sai, nghĩa là
xác định hoàn toàn lỗi sai của bản tin nhận được. Nhưng do hệ này là phi tuyến
nên rất khó giải. Vì vậy, ta sẽ tìm các vị trí sai trước, rồi sau đó mới tìm các giá
trị sai. Bởi vì mã RS có thể tối đa s lỗi nên ta coi v = s.
a) Tìm vị trí sai (thuật toán Berlekamp)
Ta sẽ định nghĩa đa thức vị trí sai:
Đa thức này có nghiệm .
Ta có
M
Trong đó S
i
với i= 1, 2t là các Syndrome.
Đặt S=

Ta tìm được các hệ số của đa thức vị trí sai L(x):
Như vậy, đa thức sai L(x) đã được xác định. Với mọi i mà là nghiệm của

L(x) thì i chính là vị trí sai. Để tìm nghiệm của L(x), ta chỉ việc thay lần lượt
các giá trị vào đa thức này.
 Vị trí sai đã được xác định nhờ đa thức vị trí sai L(x).
Mặt khác, cũng là nghiệm của L(x) => bằng các tìm nghiệm của L(x) ta đã
xác định được các tham số trong đa thức sai e(x). (4.2.2)
b) Xác định giá trị sai
Từ (4.2.1) và (4.2.2) ta có:

Từ đây, ta dễ dàng tìm được các giá trị sai e
1
, e
2
, …, e
t
 Đa thức sai e(x) đã được xác định hoàn

toàn.
4.3. Sửa sai
Khi đã tìm được đa thức sai e(x) thì từ mã c(x) hoàn toàn được xác định
theo công thức sau:
c(x) = r(x) – e(x)
-