Tóm tắt Luận án Xây dựng phương pháp giải mã theo chuẩn syndrome trên cơ sở nhận dạng lỗi

Bé gi¸o dôc vµ ®µo t¹o Bé Quèc phßng 
ViÖn khoa häc vµ c«ng nghÖ qu©n sù 
-------------------------- 
VŨ SƠN HÀ 
XÂY DỰNG PHƢƠNG PHÁP GIẢI MÃ THEO 
CHUẨN SYNDROME TRÊN CƠ SỞ NHẬN DẠNG LỖI 
Chuyên ngành: Kỹ thuật điện tử 
Mã số: 62 52 02 03 
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT 
HÀ NỘI - 2016 
Công trình đƣợc hoàn thành tại: 
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÒNG 
Ngƣời hƣớng dẫn khoa học: 
1. TS PHẠM VIỆT TRUNG 
2. TS PHẠM KHẮC HOAN 
Phản biện 1: PGS.TS Lê Mỹ Tú 
Học viện Kỹ thuật Mật mã 
Phản biện 2: PGS.TS Hoàng Mạnh Thắng 
Đại học Bách khoa Hà Nội 
Phản biện 3: TS Nguyễn Đông Hƣng 
Cục Cơ yếu – Bộ Tổng tham mưu 
Luận án đƣợc bảo vệ trƣớc Hội đồng chấm luận án Tiến 
sĩ cấp Viện, họp tại Viện Khoa học và Công nghệ quân sự vào 
hồi: ...... giờ ...... ngày ...... tháng ...... năm 2016. 
Có thể tìm hiểu luận án tại: 
- Thư viện Viện Khoa học và Công nghệ quân sự. 
- Thư viện Quốc gia Việt Nam. 
1 
MỞ ĐẦU 
1. Tình hình nghiên cứu trong nƣớc và ngoài nƣớc 
Tại Việt Nam các giáo sư Nguyễn Xuân Quỳnh, Nguyễn Bình đã 
nghiên cứu về mã cyclic cục bộ từ những năm 80 của thế kỷ XX. Mã 
cyclic cục bộ tiếp tục phát triển và có nhiều thành tựu đáng kể. Tuy 
nhiên các công trình này chưa đi sâu vào việc nghiên cứu phương pháp 
giải mã, thiết kế bộ giải mã, đặc biệt khi khoảng cách mã lớn, hay mã có 
khả năng sửa đồng thời lỗi ngẫu nhiên và lỗi chùm. 
Các thiết bị giải mã mã BCH, Reed-Solomon hiện nay thường sử 
dụng các thuật toán Berlekamp-Massey, Euclid. Thuật toán Berlekamp-
Massey (BMA) là một phương pháp tính để giải phương trình khóa rất 
hiệu quả về số lượng của phép tính trong trường hữu hạn và là lựa chọn 
phổ biến để mô phỏng hoặc thực hiện giải mã BCH và Reed-Solomon 
bằng phần mềm. Thuật toán Euclid (EA) là phương pháp để giải phương 
trình khóa dựa trên việc tìm ước số chung lớn nhất của hai đa thức. Đặc 
điểm cơ bản của các thuật toán này là chúng ở dạng lặp, dễ thực hiện ở 
dạng phần mềm, nhưng khó thực hiện khi thiết kế phần cứng, tốc độ giải 
mã không cao. 
2. Tính cấp thiết 
Các phương pháp đại số giải mã BCH yêu cầu phải giải phương 
trình khóa bậc cao trên trường Galoa. Các thuật toán lặp BMA, EA và 
thủ tục tìm kiếm Chien có độ trễ xử lý lớn khi n và t tăng, điều đó hạn 
chế việc ứng dụng mã BCH vào các hệ thống thông tin thời gian thực. 
Mặt khác trong các hệ thống truyền tin, các hệ thống xử lý, lưu trữ thông 
tin thường xảy ra lỗi ở cả dạng lỗi ngẫu nhiên và lỗi chùm. Một số mã 
khối tuyến tính có khả năng đồng thời sửa được cả lỗi ngẫu nhiên và lỗi 
chùm như mã tầng, mã Fire biến thể, mã có xáo trộn tuy nhiên việc 
giải mã chúng thường khá phức tạp, tốc độ mã hóa thấp hoặc khả năng 
sửa lỗi không lớn. 
Trên cơ sở nghiên cứu cấu trúc của mã BCH và các biến thể của 
nó, xây dựng một tham số mới là chuẩn syndrome. Chuẩn syndrome là 
bất biến với tác động của nhóm phép thế dịch vòng và chuẩn syndrome 
của các nhóm khác nhau thì khác nhau. Khi sử dụng chuẩn syndrome, 
các lỗi ngẫu nhiên và lỗi chùm có thể được sửa đồng thời do chuẩn 
syndrome của các vector lỗi ngẫu nhiên và một số cấu hình lỗi chùm độ 
dài nhỏ, lỗi chùm đồng pha không trùng nhau khi chọn đa thức sinh của 
trường một cách thích hợp. Trên cơ sở chuẩn syndrome, quá trình nhận 
2 
dạng lỗi có thể thực hiện khá thuận tiện làm giảm độ phức tạp xử lý lỗi 
đồng thời tăng hiệu quả giải mã. 
Do đó đề tài “Xây dựng phƣơng pháp giải mã theo chuẩn 
syndrome trên cơ sở nhận dạng lỗi’’ có tính cấp thiết và tính ứng dụng 
thực tiễn cao. 
3. Đối tƣợng nghiên cứu: 
- Nhóm các phép thế dịch vòng, phép thế cyclotomic. 
- Các mã BCH, Reed-Solomon và các biến thể. 
4. Mục đích nghiên cứu: 
- Nghiên cứu đặc điểm cấu trúc của mã BCH. 
- Nghiên cứu xây dựng thuật toán, thiết bị giải mã dựa trên chuẩn 
syndrome. 
- Nghiên cứu xây dựng phương pháp nhận dạng vector lỗi dựa trên 
chuẩn syndrome để nâng cao hiệu quả sửa lỗi của mã. 
5. Nhiệm vụ nghiên cứu: 
- Nghiên cứu về mã BCH, Reed-Solomon. 
- Nghiên cứu nhóm các phép thế dịch vòng và tính chuẩn 
syndrome cho các mã BCH, Reed-Solomon và các biến thể. 
- Nghiên cứu phương pháp nhận dạng vector lỗi theo chuẩn syndrome. 
- Nghiên cứu thiết bị giải mã mã BCH và các biến thể, mã Reed-
Solomon trên cơ sở nhận dạng lỗi theo chuẩn syndrome. 
- Nghiên cứu phương pháp nén chuẩn syndrome và nhận dạng lỗi 
khi sửa lỗi bội cao. 
6. Phƣơng pháp nghiên cứu: 
Phương pháp nghiên cứu cơ bản là kết hợp phương pháp giải tích 
và phương pháp mô phỏng Monte-Carlo trên Matlab có sử dụng các 
công cụ toán học của lý thuyết xác suất thống kê, lý thuyết nhóm... đồng 
thời sử dụng các công nghệ thiết kế, chế tạo phần cứng như công nghệ 
FPGA để thiết kế thiết bị giải mã. 
7. Ý nghĩa khoa học và thực tiễn: 
Ý nghĩa khoa học: Xây dựng phương pháp thế giải mã mã BCH và 
các biến thể dựa trên chuẩn syndrome, phương pháp giải mã dựa trên 
việc kết hợp phép thế cyclotomic và phép thế dịch vòng khi sửa lỗi bội 
cao. Xây dựng phương pháp nhận dạng vector lỗi theo chuẩn syndrome 
với các dạng lỗi khác nhau, cho phép mở rộng khả năng sửa lỗi của mã. 
Ý nghĩa thực tiễn: Đề xuất sơ đồ cấu trúc thiết bị giải mã mã BCH 
và các biến thể, mã Reed-Solomon trên cơ sở nhận dạng lỗi theo chuẩn 
syndrome. Thiết bị mã hóa, giải mã thực hiện trên thiết bị logic lập trình 
3 
được có mức tác động nhanh cao và độ phức tạp thấp hơn các bộ giải mã 
đại số thông thường. 
8. Bố cục luận án: 
 Luận án chia thành 03 chương. Chương 1: Tổng quan về mã BCH. 
Chương 2: Phương pháp chuẩn syndrome giải mã mã BCH. Chương 3: Mở 
rộng khả năng sửa lỗi của mã BCH sử dụng phương pháp chuẩn syndrome. 
Ngoài ra luận án gồm có phần mở đầu, kết luận, danh mục các công trình 
nghiên cứu đã công bố của tác giả, tài liệu tham khảo và phụ lục. 
CHƢƠNG 1: TỔNG QUAN VỀ MÃ BCH 
1.1. Tổng quan về mã khối tuyến tính 
Một mã khối có chiều dài n gồm qk từ mã được gọi là mã tuyến tính 
(n,k) khi và chỉ khi qk từ mã hình thành một không gian vector con k chiều 
của không gian vector gồm tất cả các vector n thành phần trên GF(q). 
Đối với xác suất lỗi bit có thể sử dụng giới hạn sau: 
Pb 
n
ti
ini
n
i
pp
n
ti
1
1 (1.14) 
Với mã tuyến tính nhị phân hệ thống truyền qua kênh AWGN, xác 
suất bit lỗi có giới hạn trên như sau: 
Pb 
 n
dw o
bw
N
E
wRQ
n
wA
2 (1.20) 
1.2. Mã BCH 
1.2.1. Một số khái niệm cơ bản 
1.2.2. Mã BCH nhị phân 
Mã BCH nhị phân là mã vòng được xây dựng bởi các không 
điểm của đa thức sinh. Một mã BCH nhị phân có khoảng cách cấu 
trúc δ 2t + 1 là một mã vòng mà đa thức sinh g(x) có 2t lũy thừa 
liên tiếp của α là nghiệm b , 1 b , ..., tb 2 . 
1.2.3. Mã BCH không nhị phân và mã Reed–Solomon 
Mã BCH nhị phân có thể được tổng quát thành mã không nhị phân. 
Đa thức sinh g(x) của mã BCH q - phân sửa t lỗi là một đa thức bậc thấp 
nhất với hệ số thuộc trường GF(q) và có các phần tử b , 1 b , ..., tb 2 là 
nghiệm. Nếu q 2 thì nhận được mã BCH nhị phân. 
Lớp con đặc biệt của mã BCH q phân với s 1 là lớp con quan 
trọng nhất. Mã của lớp con này được gọi là mã Reed–Solomon (mã RS). 
Mã RS sửa t lỗi dùng các ký hiệu thuộc trường Galoa GF(q) có những tham 
số sau: độ dài khối: n q – 1; số symbol kiểm tra: n – k 2t; khoảng 
cách tối thiểu: d 2t + 1 
4 
1.3. Các phƣơng pháp giải mã mã BCH 
+ Thuật toán Berlekamp–Massey (BMA); 
+ Thuật toán Euclid (EA); 
+ Phương pháp bẫy lỗi; 
+ Phương pháp thế. 
1.4. Đặt vấn đề nghiên cứu 
1.4.1. Nghiên cứu xây dựng phƣơng pháp chuẩn syndrome giải mã 
mã BCH và các biến thể trên cơ sở nhận dạng lỗi 
Vấn đề nghiên cứu thứ nhất của luận án là xây dựng phương pháp 
giải mã mã BCH và biến thể dựa trên chuẩn syndrome cho phép xác định 
vector lỗi theo chuẩn syndrome, không cần giải phương trình khóa. 
Vấn đề nghiên cứu thứ hai của luận án là xây dựng phương pháp 
kết hợp phép thế cyclotomic và phép thế dịch vòng để giải mã mã BCH 
cho phép rút gọn các tập vector lỗi cần xử lý. 
1.4.2. Nghiên cứu mở rộng khả năng sửa lỗi của mã BCH và các biến 
thể sử dụng phƣơng pháp chuẩn syndrome trên cơ sở nhận dạng lỗi 
Vấn đề nghiên cứu thứ ba của luận án là mở rộng khả năng sửa lỗi 
của mã BCH, Reed-Solomon và các biến thể, cho phép đồng thời sửa lỗi 
ngẫu nhiên và lỗi chùm trên cơ sở nhận dạng lỗi theo chuẩn syndrome. 
1.5. Kết luận chƣơng 1 
Các kết quả chương 1 bao gồm: 
(1) Nghiên cứu tổng quan mã khối tuyến tính, mã BCH và các phương 
pháp giải mã mã BCH nhị phân và không nhị phân, mã Reed-Solomon 
dựa trên thuật toán Berlekamp–Massey, thuật toán Euclid. 
(2) Nghiên cứu phương pháp bẫy lỗi và phương pháp thế giải mã mã 
BCH nhị phân. 
CHƢƠNG 2: PHƢƠNG PHÁP CHUẨN SYNDROME 
GIẢI MÃ MÃ BCH 
2.1. Phân loại dịch vòng vector lỗi 
Ký hiệu σ là phép thế dịch vòng, vector lỗi e (e1, e2, , en) dịch 
vòng phải đi một vị trí σ(e) (en, e1, e2, e3, , en-1). Tập hợp tất cả các 
vector khác nhau đôi một σm(e) với 0 ≤ m ≤ n – 1 của vector lỗi e tùy ý 
gọi là σ-orbit của nó, mỗi σ-orbit có một vector sinh. 
Với một số λ tự nhiên nhỏ nhất nào đó, 1 < λ < n, σ-orbit chứa λ 
phần tử, với λ n hoặc λ là ước của nó, σ-orbit có cấu trúc sau: 
5 
 )(),...,(,)( 1 eeeee  (2.2) 
Tất cả các vector của σ-orbit có cùng đường kính, với hai vector lỗi tùy ý 
e và e’ thì các σ-orbit , hoặc là trùng nhau hoặc không giao nhau. Khi 
n 15, có 105 vector lỗi trọng số 2 chia thành 7 lớp với đường kính lỗi 
từ 2 đến 8 như minh họa trong bảng 2-1. 
Bảng 2-1. Các σ-orbit, đường kính, tọa độ vector lỗi bội 2 
với chiều dài n=15 
Các lớp σ-orbit Đường kính lỗi D Tọa độ vector sinh lỗi e 
I2 2 1,2 (110000000000000) 
I3 3 1,3 (101000000000000) 
I4 4 1,4 (100100000000000) 
I5 5 1,5 (100010000000000) 
I6 6 1,6 (100001000000000) 
I7 7 1,7 (100000100000000) 
I8 8 1,8 (100000010000000) 
2.2. Xây dựng phƣơng pháp chuẩn syndrome cho mã BCH và các biến thể 
2.2.1. Phƣơng pháp chuẩn syndrome giải mã mã BCH 
Ma trận kiểm tra của mã BCH với khoảng cách cấu trúc δ có dạng: 
 Tibibbi
bnbb
bnbb
bnbb
H
H
)2()1(
)2)(1()2(22
)1)(1()1(21
)1(2
....,,
...1
...............
...1
...1






 5
 (2.3) 
với 0 ≤ i ≤ n – 1,  là căn bậc n của 1. 
Cho mã BCH có ma trận kiểm tra như biểu thức (2.3), với 
syndrome S(e) (s1, s2, , sδ-1), khi đó: 
).,...,,())(( 1
2
2
1
1 
 
 ssseS bbb (2.4) 
Tổng quát khi sử dụng (2.4) λ lần ta có: 
)5.2(.10),,...,,())(( 1
)2(
2
)1(
1 
 nssseS bbb  
 
Đối với mã BCH có ma trận kiểm tra như biểu thức (2.3) phổ 
syndrome của σ-orbit J bao gồm các vector khác nhau đôi một 
của không gian S(En) dạng: 
6 
.10),,...,,( 1
)2(
2
)1(
1 
 nsss bbb  
 (2.6) 
Định nghĩa 2.1. Chuẩn syndrome của vector lỗi e với mã C (có ma 
trận kiểm tra (2.3)) là vector: 
 N(S(e)) (N12, N13, , N 1(δ-1), N23, ..., N (δ-2)(δ-1)) có 
2
1 C 
tọa độ 
Nij, 1≤ i < j ≤ δ - 1 tính theo công thức: 
( 1)/ ( 1)// , ( 1, 1)b i hij b j hijij j i ijN s s h USCLN b i b j
 Trong đó: 
 Nij = ∞ nếu sj ≠ 0, si = 0. 
 Nij = - (không xác định) khi sj = si = 0. 
 Đối với mã nhị phân q 2, ma trận kiểm tra của mã BCH nhị phân 
theo nghĩa hẹp (b = 1) với δ 2t + 1 có dạng: 
  .10,....,, )12(3 niH Titii  (2.8) 
 Khi đó syndrome của vector lỗi tùy ý gồm t thành phần thuộc 
trường GF(2m) S(e) (s1, s2, , st). 
Đối với BCH mã nhị phân với ma trận kiểm tra (2.8) ta có; 
).,...,,())(( 122
3
1 t
t ssseS  (2.9) 
Với mã BCH nhị phân nguyên thủy theo nghĩa hẹp, b 1, 
  phần tử nguyên thủy của trường GF(2
m
) và ma trận kiểm tra có dạng: 
   .12,10,....,,
)12(3 m
Titii nniH (2.10) 
Trường hợp mã BCH nhị phân nguyên thủy theo nghĩa hẹp có ma 
trận kiểm tra (2.10) đối với vector lỗi e, syndrome S(e) (s1, s2, , st) 
phổ syndrome S() gồm tất cả các vector khác nhau đôi một dạng: 
.220),,...,,( )12(2
3
1 
 m
t
tiii sss  (2.11) 
Định nghĩa 2.2. Gọi chuẩn (norm) của syndrome S(e) (s1, s2, , st) 
với mã nguyên thủy theo nghĩa hẹp là vector N(S) có 
2
tC tọa độ Nij, 
1≤ i < j ≤ t tính theo công thức: 
)12,12(,/
/)12(/)12(
jiUSCLNhssN ij
hj
i
hi
jij
ijij . (2.12) 
 Nij = ∞ nếu sj ≠ 0, si = 0; Nij = - (không xác định) khi sj = si = 0. 
Ví dụ với mã BCH nhị phân có d 7, chuẩn syndrome gồm 3 
thành phần: 
(2.7) 
7 
5
2
3
33
5
132
3
121 /,/,/ ssNssNssN . 
Tính chất cơ bản của chuẩn syndrome là tính bất biến của nó với 
phép thế dịch vòng. 
))(()))((( eSNeSN  . (2.13) 
Định nghĩa 2.3. Norm của σ-orbit J là chuẩn syndrome của một vector 
tùy ý trong J và ký hiệu là N(J). 
Định lý 2.1. Cho K là tập σ-orbit tùy ý các vector lỗi nhị phân có 
phổ syndrome đầy đủ với mã BCH có khoảng cách mã 2t + 1 trên trường 
GF(2
m
) và có chuẩn syndrome khác nhau đôi một. Nếu biết rằng từ mã 
nhận được chứa vector lỗi thuộc tập K thì mã đã cho sửa được lỗi này. 
Để thực hiện giải mã dựa trên chuẩn syndrome cần ba bộ nhớ 
ROM lưu trữ các thông tin sau: 
- P1 = {N(I1), N(I2), ..., N(It)}– tập chuẩn syndrome của các σ-
orbit I1, I2, ..., It của tập cần giải mã K (ROM 1). 
- P2 = {e01, e02, ..., e0t} – tập các vector sinh của các vector lỗi cho 
mỗi lớp I1, I2, ..., It (ROM 2). 
- P3 = {S11
-1
, S12
-1
, ..., S1t
-1
} – tập các phần tử của trường Galoa 
(ROM 3), trong đó s1j – thành phần syndrome đầu tiên của vector lỗi ei 
trong P2 (nếu s1(t) = 0, N(It) = ∞, thì thay cho s1t
-1
 ghi s2t
-1
 cho thành 
phần thứ 2 là s2t của S(et)). 
Thuật toán giải cho giải mã theo phương pháp chuẩn syndrome 
thực hiện tính toán qua các bước như sau: 
+ Tính syndrome S(e) (s1, s2, , st) với si là phần tử của trường 
Galoa GF(2
m
). 
+ Tính bậc của chuẩn syndrome N. 
Tính degsj, degsi là bậc thành phần si, sj của syndrome 
S(e) (s1, s2, , si, ..., sj, ..., st) với 1≤ i < j ≤ t. 
Chuẩn syndrome của syndrome S(e) tính theo công thức (2.12): 
)12,12(,/
/)12(/)12(
jiUSCLNhssN ij
hj
i
hi
jij
ijij . 
DegNij {degsj.(2i – 1)/hij – degsi.(2j – 1)/hij } mod n. 
+ Theo degNij xác định vector sinh và bậc i0 của thành phần 
syndrome đầu tiên s1
0
 ứng với vector sinh. 
+ Tính số thứ tự bit lỗi đầu tiên bằng Li (degsi – degs1
0
) mod n. 
+ Tìm vector lỗi e bằng cách dịch vòng vector sinh đi Li nhịp. 
+ Sửa tín hiệu nhận được bằng cách tổng tín hiệu nhận được với 
vector lỗi tìm được. 
8 
2.2.2. Phƣơng pháp chuẩn syndrome giải mã mã thuận nghịch 
Cho mã thuận nghịch C5 có ma trận kiểm tra dạng 
 TzzH , , chuẩn syndrome S (s1, s2) ( i, j) là tích các 
thành phần của syndrome trong trường GF(2m). 
N s1.s2 = 
i+j
  (2.15) 
Với  T {– , 0, 1, 2, , n – 1}. Bậc  được gọi là 
bậc của chuẩn syndrome N và được ký hiệu degN : 
njiN mod)(deg . (2.16) 
Khi phân hoạch theo các σ-orbit, chuẩn syndrome tương ứng với 
các lỗi ngẫu nhiên và một số dạng lỗi phụ thuộc không trùng nhau. Ví dụ 
mã thuận nghịch có độ dài 31, d 5, với phần tử nguyên thủy α là 
nghiệm của đa thức x5 + x2 + 1 ngoài các lỗi bội 1, 2 còn sửa được các 
vector lỗi bội 3 với các vị trí lỗi thỏa mãn i2 – i1 i3 – i2 ... 2 3 (1,6,11) (0, α
0
, 0) 0
Ф3 
4 (1,2,3,11) (0, α2, α5) α5 
5 (1,3,5,6) (0, α4, α10) α10 
6 (1,5,9,11) (0, α8, α5) α5 
7 (1,2,6,9) (0, α1, α10) α10 
Ф4 
8 (1,3,10,13) (0, α11, α5) α5 
9 (1,4,5,10) (0, α7, α10) α10 
Ф5 10 (1,2,4,8) (0, α
12
, 0) 0
Giả sử với vector lỗi e tùy ý, syndrome S(e) = (s1, s2, ..., st) có thành 
phần đầu tiên s1 = α
h
 ≠ 0, sau khi dịch vòng n – h nhịp sẽ nhận được s1
*
 = 1. 
Xét vector g là tổng của vector f nhận được sau khi dịch vòng vector e và 
vector (1, 0, ...,0), g = τ(f) = f + 1, rõ ràng syndrome của g có thành phần 
thứ nhất bằng 0. Vector g tạo thành tập M10,w trong M0,w. Trên hình 2-11 
biểu diễn tác động của biến đổi τσn-h với các vector lỗi bội 2 trong không 
gian E15, khi đó 105 vector lỗi bội 2 (7 σ-orbit) được nén thành 7 vector 
bội 3 thuộc 3 σ-orbit có thành phần s1 = 0. 
17 
Hình 2-11 Tác động của các phép thế τσn-h với các 
vector lỗi bội 2 trong không gian E15 
Như vậy nếu xác định được vector g sẽ tìm được vector e = σh(τ(g)). 
Việc xác định g đơn giản hơn việc xác định e bởi vì số lượng vector g ít 
hơn số lượng vector e đúng n lần; số lượng σ-orbit của g ít hơn của e 
khoảng w + 1 lần; số lượng thành phần chuẩn syndrome cũng giảm đi. 
Tuy nhiên cần tính đến khả năng các vector g có trọng số khác nhau có 
cùng chuẩn syndrome và syndrome. Khi đó cần đánh giá trọng số của g 
theo syndrome và trước tiên xác định các vector có trọng số w ≤ t, sau 
đó mới xét vector trọng số t+1. Chú ý rằng trong mỗi σ-orbit của các 
vector thuộc tập M0,w chỉ có w vector thuộc tập M
1
0,w, vì vậy có thể xác 
định đơn trị vector g. Quy tắc giải mã theo phương pháp nén chuẩn 
syndrome như sau. 
1. Tính syndrome S = (s1, s2, ..., st), nếu S = 0, không xảy ra lỗi, với 
S ≠ 0, giải mã theo các bước sau. 
)10,14,4(
)2,1(
f
14
5
8
)13,12,1(
13
9
)5,13,8(
)3,1(
),14,13(
)7,1(
 )5,,10(
)6,1(
 )10,13,9(
)8,1(
),7,14(
)4,1(
 )10,11,1(
)5,1(
)5,8,0(
)15,4(
)5,2,0(
)12,13(
),10,0(
)5,2(
11 
)10,1,0(
)14,7(
)10,4,0(
)10,8(
),5,0(
)9,3(
 )0,,0(
)11,6(
6 7
2 5
)5,2,1()15,4,1(
12 4
14
)10,8,1(
)14,7,1( )9,3,1(
)11,6,1(
18 
2. Nếu s1 = 0, tính chuẩn syndrome, xác định vector lỗi theo phương 
pháp chuẩn syndrome. 
3. Nếu s1 = α
h
 ≠ 0, sử dụng biến đổi g = τσn-h(e), khảo sát giá trị 
S(g) = (0, N12 + 1, ..., N1t +1), nếu S(g) = 0, xảy ra lỗi đơn tại vị trí h. 
4. Với S(g) ≠ 0, chuyển về bước 2 và giải mã theo phương pháp 
chuẩn syndrome để xác định g. 
5. Biến đổi vector g để xác định vector lỗi e = σh(τ(g)). 
Mã BCH (31, 16) số lượng vector lỗi bội 1, bội 3 cần phân tích là 
4991. Khi sử dụng phương pháp chuẩn syndrome yêu cầu phân tích 161 
chuẩn syndrome. Với phương pháp nén chuẩn syndrome yêu cầu phân 
tích 5 σ-orbit của tập M0,3 (gồm một G-orbit) hoặc phân tích 31 vector 
thuộc tập M10,3, M
1
0,4 do đó nếu tính đến cả phép dịch vòng thì chỉ cần 
5 + 31 + 1 + 31 = 68 phép phân tích. Độ phức tạp giải mã giảm khoảng 
73 lần so với phương pháp syndrome thông thường, giảm 3 lần so với 
phương pháp chuẩn syndrome. 
2.4. Kết luận chƣơng 2 
Các kết quả chương 2 bao gồm: 
(1) Nghiên cứu phương pháp giải mã thế mã BCH và các biến thể dựa 
trên chuẩn syndrome: 
 - Phân loại các vector lỗi theo chuẩn syndrome, tham số đặc trưng 
bởi cấu trúc của mã BCH. 
- Nghiên cứu các thuật toán giải mã mã BCH và biến thể dựa trên 
chuẩn syndrome. 
(2) Đề xuất sơ đồ cấu trúc thiết bị giải mã theo phương pháp chuẩn 
syndrome cho mã BCH và các biến thể: 
 - Sơ đồ cấu trúc thiết bị giải mã mã BCH sử dụng các bộ cộng 
modul và các bộ nhớ ROM, thiết bị giải mã mã BCH, Reed-Solomon 
trên thiết bị logic khả trình có mức tác động nhanh cao, độ phức tạp thấp. 
(3) Đề xuất kết hợp phép thế cyclotomic và phương pháp chuẩn 
syndrome để giải mã mã BCH: 
 - Phương pháp giải mã dựa trên phép thế cyclotomic cho phép rút 
gọn số tổ hợp cần chọn lọc đến 5, 7, 11 lần với mã C5 có độ dài n = 31, 
127, 1047 tương ứng. 
 - Nghiên cứu phương pháp nén chuẩn syndrome giải mã mã BCH. 
Với mã BCH (31,16) phương pháp đề xuất cho phép giảm độ phức tạp 3 
lần so với phương pháp chuẩn syndrome thông thường. 
Nội dung của chương này đã được công bố trong các công trình 
CT1, CT2, CT5. 
19 
CHƢƠNG 3: MỞ RỘNG KHẢ NĂNG SỬA LỖI CỦA MÃ BCH 
SỬ DỤNG PHƢƠNG PHÁP CHUẨN SYNDROME 
3.1. Nghiên cứu mở rộng khả năng sửa lỗi của mã BCH và các biến thể 
3.1.1. Mở rộng khả năng sửa lỗi của mã BCH 
Trước hết xét mã BCH C5 có chiều dài n = 2
m
 - 1, m ≥ 4. Chú ý 
rằng với mã này chuẩn syndrome có n + 2 giá trị phân biệt, tương ứng 
n.(n+2) vetor lỗi khác 0. Lùa chän ®a thøc sinh cña tr-êng mét c¸ch hîp 
lý, m· BCH nguyªn thñy C5 söa ®-îc ®ång thêi lçi béi 2 vµ mäi lçi chïm 
dµi 4. 
Định lý 3.1. Nếu phần tử nguyên thủy không là nghiệm của đa 
thức 1;1 456256 xxxxxxxx và vết của các 
phần tử sau bằng 1 
323
52
4
33
224
3
33
24
232
4
1
)1(
)1()1(
;
)1(
)1()1(
;
)1(
)1()1(
;
)1(
)1(




 (3.1) 
thì mã BCH nguyên thủy C5 sửa được đồng thời lỗi bội 2 và mọi 
lỗi chùm dài 4. 
Trong trường hợp các điều kiện của định lý 3.1 thỏa mãn trừ điều 
kiện 04 Tr , mã BCH C5 có thể sửa được cùng với lỗi bội 2 là các lỗi 
chùm dài 4 trừ lỗi đặc. 
Mã BCH C7 có chiều dài n = 2
m
 – 1, m ≥ 4 sẽ có C1n, C
2
n, C
3
n
vector lỗi tương ứng trọng lượng 1, 2, 3. Tổng số syndrome chiếm một 
nửa tập hợp tất cả các giá trị syndrome, giải mã được (n+2)2 + (n+2) J- 
σ-orbit, tương ứng với n.((n+2)2 + (n+2)) = (n+1)3 – 1 vector lỗi khác 0. 
Vì vậy có thể mở rộng khả năng sửa lỗi của mã C7. 
Xét mã C7 (15,5) trên GF(2
4
) với đa thức sinh 14 xx . Ký 
hiệu K – tập hợp các lỗi bội 1, bội 2, bội 3, chứa 39 σ-orbit (1 σ-orbit lỗi 
đơn, 7 σ-orbit lỗi bội 2, 31 σ-orbit lỗi bội 3). Tập K chứa 38.15 + 5 = 
576 vector lỗi. Bổ sung vào tập K các σ-orbit của các lỗi chùm có vector 
sinh dạng = với i = 4, 5, 6, 7 và cho phép tăng khả 
năng sửa lỗi của mã lên hơn 10%. 
20 
Bảng 3-3. Vector sinh, σ-orbit, syndrome, chuẩn syndrome của các lỗi chùm. 
TT Đường kính σ-orbit Vector sinh e Syndrome S(e) Norm(S(e)) 
1 4 I1 (1,2,3,4) (α
12, α12, 1) (α6, 1, 1) 
2 5 I2 (1,2,3,4,5) (α
6
 ,0, α10) (0, α10, ∞) 
3 6 I3 (1,2,3,4,5,6) (α
9
, 1, 0) (α3, 0, 0) 
4 7 I4 (1,2,3,4,5,6,7) (α
5, α14, 1) (α14, α5, α3) 
Tập K mở rộng gồm tất cả các σ-orbit của các lỗi bội 1, 2, 3 và các 
σ-orbit I1, I2, I3, I4 gồm 43 σ-orbit chứa tổng cộng 635 vector lỗi thỏa 
mãn điều kiện định lý 2.1. Do đó mã C7 (15,5) sửa được các lỗi nói trên. 
ThuËt to¸n gi¶i m· gồm các bước: 
- Tính syndrome: S = r . HT = (S1, S2, S3) 
- Tính chuẩn syndrome: 
 N = (N1, N2, N3) = 
5
2
3
3
5
1
3
3
1
2 ,,
S
S
S
S
S
S
- Tập hợp (N1, N2, N3) chỉ ra dạng vector lỗi và kết hợp với giá trị 
S1 để tìm lượng dịch vòng x để xác định vector lỗi hiện thời e. 
- Đầu ra từ mã đúng v: v = r + e. 
3.1.2. Mở rộng khả năng sửa lỗi của các mã BCH biến thể 
Bổ sung thêm bit kiểm tra chẵn lẻ, nhận được mã BCH mở rộng 
Cˆ có ma trận kiểm tra Hˆ nhận được từ H bằng cách bổ sung thêm một 
hàng toàn các bit 1. Mở rộng thêm một bit kiểm tra chẵn lẻ cho mã C5 
nhận được mã Cˆ có khoảng cách Hamming lúc này d = 6, bit kiểm 
tra chẵn (parity) của lỗi bội 2 bằng 0, của các lỗi đặc bội lẻ bằng 1, 
nhờ đó phân biệt được 2 cấu hình lỗi trên. Mã BCH có khoảng cách 
d = 6 cho phép sửa đồng thời lỗi bội 2 cùng với các lỗi chùm đặc bội lẻ 
và phần lớn các lỗi chùm đặc độ dài chẵn, vì vậy có thể mở rộng miền 
ứng dụng của nó. 
Với mã thuận nghịch C có ma trận kiểm tra 
,),,( Tii IH với 220 mi , đây là biến thể của mã thuận 
nghịch C5 loại bỏ tất cả các từ mã trọng lượng lẻ. Vì vậy mã C cùng với 
lỗi bội 2 sửa được tất cả các lỗi chùm đặc độ dài lẻ và các lỗi đặc độ dài l 
chẵn (l ≥ 4) nếu Trc = 1, với )1)(1( 221 llc . 
Trường hợp trên, trong phần thứ nhất H1 của ma trận kiểm tra của 
mã thuận nghịch mở rộng tham số i được sắp xếp theo thứ tự tăng dần. 
Giả sử sắp xếp các cột của H1 theo một thứ tự khác và thay thế đồng bộ 
21 
với các cột của H2. Cột thứ i của H1 là biểu diễn m bit của số nguyên i 
-1, 1 ≤ i ≤ n = 2m với m lẻ nhận được mã C
~
 có ma trận kiểm tra 
TIHHH ),
~
,
~
(
~
21
 , khoảng cách mã d = 6. Các cột của nó được chia 
thành các modul dài 4 ký hiệu là Mj với 0 ≤ j ≤ n/4 -1. Khảo sát khả 
năng sửa đồng thời lỗi bội 1, bội 2 và các lỗi modul dài 4 của mã C
~
. 
 Định lý 3.2. Mã C
~
với m lẻ cho phép đồng thời sửa lỗi ngẫu nhiên 
bội 1,2 và các lỗi modul dài 4 nếu vết của phần tử sau bằng 1. 
12 )1( c (3.13) 
Tương tự như mã C5, với mã C7, mở rộng 1 bit kiểm tra chẵn lẻ, 
mã BCH C8 đồng thời sửa lỗi bội 3 trở xuống và các lỗi chùm độ dài đến 5. 
3.2. Nghiên cứu mở rộng khả năng sửa lỗi của mã Reed-Solomon 
3.2.1. Đồng thời sửa và nhận dạng lỗi modul nhờ mã Reed-Solomon 
Xét mã RS(15,12) với d = 4, với thành phần nguyên thủy là 
nghiệm của đa thức x4 x 1, có khả năng sửa 1 lỗi modul và nhận 
dạng được lỗi 2 modul ma trận kiểm tra dạng: 
28642
14321
hhhhI
hhhhI
IIIII
H



, 321 iiiiih (3.17) 
với I là các ma trận đơn vị 4 x 4.
Chuẩn syndrome 
2
3
1
2
21 ,),(
S
S
S
S
NNN (3.18) 
Với lỗi trong 1 modul thì S = (S1, S2, S3), N1 = N2 = 
l (lỗi modul 
thứ l, với l = 0, 1, 2,...., 14), vector lỗi e = S1 .Với N1 ≠ N2 nhận dạng 
được đây là lỗi modul bội 2, có thể xử lý riêng biệt. 
3.2.2. Đồng thời sửa lỗi modul và lỗi chùm nhờ mã Reed-Solomon 
Xét mã RS(15,12) với d = 4, với thành phần nguyên thủy là 
nghiệm của đa thức x4 x 1, mỗi modul có độ dài 4 bit, ma trận kiểm 
tra có dạng (3.17). Đối với các cấu hình vector lỗi độ dài 2, 3, 4, 5, 6 xảy 
ra tại 2 modul liền kề nhau chuẩn syndrome không trùng với lỗi modul. 
Quy tắc giải mã như sau: 
- Tính syndrome: S = r . H
T
 = (S1, S2, S3) 
- Tính chuẩn syndrome: N = (N1, N2) = (S2/S1, S3/S2) 
- Từ giá trị N, kết hợp với giá trị S1 (hoặc S2) để tìm lượng dịch 
vòng x và chỉ ra được vector lỗi e. 
- Đầu ra từ mã đúng v: v = r + e 
22 
3.3. Khảo sát hiệu quả mã BCH có mở rộng khả năng sửa lỗi 
Mã được khảo sát BCH C7 (31,16) với đa thức sinh của trường 
tương ứng là x5 + x4 + x2 + x + 1 (067), x5 + x4 + x3 + x2 + 1 (075) sử 
dụng điều chế BPSK. 
3.3.1. Khảo sát trên kênh Gauss 
Hình 3-6 Hiệu quả của mã BCH trên kênh Gauss với đa thức sinh 075. 
Độ lợi mã hóa theo phương pháp chuẩn syndrome so với phương 
pháp Berlekamp-Massey khi sử dụng mã BCH với đa thức sinh 067, 075 
trên kênh Gauss tương ứng là 2,8dB; 2,7dB tại BER = 10-4. 
Hình 3-5 Hiệu quả của mã BCH trên kênh Gauss với đa thức sinh 067. 
23 
3.3.2. Khảo sát trên kênh Rayleigh 
Trên hình 3-8, 3-10 trình bày kết quả mô phỏng hiệu quả của mã 
BCH trên kênh pha đinh Rayleigh phẳng. Trong mô hình mô phỏng sử 
dụng thêm khối ghép xen với độ sâu L = 5 
Độ lợi mã hóa theo phương pháp chuẩn syndrome so với phương 
pháp Berlekamp-Massey khi sử dụng mã BCH với đa thức sinh 067, 075 
trên kênh pha đinh Rayleigh phẳng tương ứng 5,1dB; 5,8dB tại BER = 10-4. 
3.4. Kết luận chƣơng 3 
Các kết quả chương 3 đạt được bao gồm: 
(1) Nghiên cứu vấn đề mở rộng khả năng sửa lỗi của mã BCH sử 
dụng phương pháp chuẩn syndrome bao gồm: 
- Đồng thời sửa lỗi ngẫu nhiên và lỗi chùm nhờ mã BCH. 
- Đồng thời sửa lỗi ngẫu nhiên và lỗi chùm nhờ các mã BCH mở 
rộng, mã thuận nghịch mở rộng. 
- Kết quả mô phỏng trên cho thấy phương pháp chuẩn syndrome 
so với phương pháp Berlekamp – Massey khi sử dụng mã BCH(31,16) 
trên kênh Gauss và kênh pha đinh Rayleigh phẳng cải thiện khoảng 
2,7dB; 5,1dB tương ứng tại BER = 10-4. 
(2) Nghiên cứu vấn đề mở rộng khả năng sửa lỗi của mã Reed-
Solomon nhờ phương pháp chuẩn syndrome bao gồm: 
Hình 3-8 Hiệu quả của mã BCH 
trên kênh Rayleigh phẳng với đa 
thức sinh 067, L = 5. 
Hình 3-10 Hiệu quả của mã BCH 
trên kênh Rayleigh phẳng với đa 
thức sinh 075, L = 5. 
24 
- Nhận dạng và sửa lỗi modul nhờ mã Reed-Solomon theo phương 
pháp chuẩn syndrome. 
- Đồng thời sửa lỗi modul và lỗi chùm sử dụng mã Reed-Solomon. 
Nội dung của chương 3 đã được công bố trong các công trình CT3, 
CT4, CT6. 
KẾT LUẬN 
Dựa trên việc nghiên cứu tác động của phép thế dịch vòng và phép 
thế cyclotomic lên không gian vector lỗi, luận án xây dựng phương pháp 
thế giải mã mã BCH và các biến thể dựa trên chuẩn syndrome. Luận án 
đã đề xuất thuật toán và sơ đồ cấu trúc của thiết bị giải mã mã BCH và 
các biến thể theo phương pháp chuẩn syndrome, nghiên cứu vấn đề mở 
rộng khả năng sửa lỗi của mã BCH và Reed-Solomon. Trên cơ sở đó 
luận án đã phát triển và đạt được một số kết quả. 
A. Những đóng góp mới của luận án 
(1). Xây dựng phương pháp giải mã dựa trên chuẩn syndrome, kết hợp 
phép thế dịch vòng và phép thế cyclotomic cho mã BCH và các biến thể 
như mã thuận nghịch, mã BCH mở rộng, mã Reed-Solomon. Phương 
pháp được đề xuất cho phép tăng tốc độ xử lý và có thể thiết kế bộ giải 
mã trên các thiết bị logic khả trình. 
 (2). Nghiên cứu vấn đề mở rộng khả năng sửa lỗi của mã BCH dựa trên 
chuẩn syndrome, đồng thời sửa lỗi ngẫu nhiên và lỗi chùm. Với mã 
BCH(31,16) kết quả mô phỏng trên kênh AWGN và kênh pha đinh 
Rayleigh phẳng đạt độ lợi tương ứng khoảng 2,7dB; 5,1dB tại BER = 10-4 
so với phương pháp Berlekamp-Massey. 
(3). Nghiên cứu khả năng đồng thời sửa lỗi modul và lỗi chùm nhờ mã 
Reed-Solomon dựa trên chuẩn syndrome. 
B. Hƣớng phát triển của luận án 
- Tiếp tục nghiên cứu khả năng nén chuẩn syndrome khi sửa lỗi bội 
cao hơn. 
- Nghiên cứu khả năng ứng dụng trên các kênh pha đinh và một số 
hệ thống thông tin thực tế. 
25 
DANH MỤC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ 
CT1. Phạm Khắc Hoan, Vũ Sơn Hà, Phạm Việt Trung, (2012) “Phương 
pháp thế giải mã hiệu quả mã BCH”, Tạp chí Nghiên cứu Khoa học 
và Công nghệ Quân sự, ISSN 1859 – 1043, số đặc san, 05-2012, tr.3-9. 
CT2. Phạm Khắc Hoan, Vũ Sơn Hà, Phạm Việt Trung, Lê Văn Thái 
(2013), “Sơ đồ chữ ký số sử dụng chuỗi mã BCH dựa trên chuẩn 
syndrome”, Tạp chí Nghiên cứu Khoa học và Công nghệ Quân sự, 
ISSN 1859 – 1043, số đặc san, 05-2013, tr. 47-56. 
CT3. Pham Khac Hoan, Le Van Thai, Vu Son Ha (2013), “Simultaneous 
correction of random and burst errors using norm syndrome for BCH 
codes”, REV 2013 - Kỷ yếu Hội nghị Quốc gia về Điện tử - Truyền 
thông, Hội Vô tuyến Điện tử Việt nam, 12/2013, tr. 154-158. 
CT4. Phạm Khắc Hoan, Vũ Sơn Hà, Lê Văn Thái (2014), “Mở rộng 
khả năng sửa lỗi của mã BCH sử dụng giải mã theo chuẩn 
syndrome”, Tạp chí Nghiên cứu Khoa học và Công nghệ Quân 
sự, ISSN 1859 – 1043, đặc san CNTT, 04-2014, tr. 16-22. 
CT5. Phạm Khắc Hoan, Vũ Sơn Hà, Bùi Ngọc Mỹ (2014), “Phương 
pháp nén chuẩn Syndrome giải mã mã BCH”, Tạp chí Nghiên cứu 
Khoa học và Công nghệ Quân sự, ISSN 1859 – 1043, số 32, 08-
2014, tr. 91-96. 
CT6. Phạm Khắc Hoan, Vũ Sơn Hà, Nguyễn Thị Thu Nga (2015), 
“Mở rộng khả năng sửa lỗi của mã Reed-Solomon sử dụng chuẩn 
syndrome”, Tạp chí Nghiên cứu Khoa học và Công nghệ Quân sự, 
ISSN 1859 – 1043, số 36, 04-2015, tr. 103-109.