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

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: 
 T
 H  i ,  3i , ....  (2t 1)i  , 0 i n 1. (2.8) 
 Khi đó syndrome của vector lỗi tùy ý gồm t thành phần thuộc 
 m
trường GF(2 ) 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ó; 
 3 2t 1
 S((e)) (s1,  s2 ,...,  st ). (2.9) 
 Với mã BCH nhị phân nguyên thủy theo nghĩa hẹp, b 1, 
 m
 phần tử nguyên thủy của trường GF(2 ) và ma trận kiểm tra có dạng: 
 i 3i (2t 1)i T m (2.10) 
 H  , , ....  , 0 i n 1, n 2 1. 
 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: 
 i 3i i(2t 1) m
 ( s1, s2 ,..., st ), 0  2 2. (2.11) 
 Định nghĩa 2.2. Gọi chuẩn (norm) của syndrome S(e) (s1, s2, , st) 
 2
với mã nguyên thủy theo nghĩa hẹp là vector N(S ) có Ct tọa độ Nij, 
1≤ i < j ≤ t tính theo công thức: 
 N s(2i 1)/ hij / s(2 j 1)/ hij , h USCLN(2i 1,2 j 1) . 
 ij j i ij (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: 
 7 
 3 5 3 5
 N1 s2 / s1 , N2 s3 / s1 , N3 s3 / s2 . 
 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. 
 N(S((e))) N(S(e)) . (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(2m) 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). 
 -1 -1 -1
 - P3 = {S11 , S12 , ..., S1t } – 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 
 -1 -1
trong P2 (nếu s1(t) = 0, N(It) = ∞, thì thay cho s1t ghi s2t 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(2m). 
 + 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): 
 N s(2i 1) / hij / s(2 j 1) / hij , h USCLN(2i 1,2 j 1) . 
 ij j i ij
 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 
 0
syndrome đầu tiên s1 ứng với vector sinh. 
 0
 + Tính số thứ tự bit lỗi đầu tiên bằng Li (degsi – degs1 ) 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 
 z z T i j
H  ,  , chuẩn syndrome S (s1, s2) ( , ) là tích các 
thành phần của syndrome trong trường GF(2m). 
 i+j 
 N s1.s2 = (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: 
 deg N (i j)mod n . (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. 
 Chuẩn syndrome N với mã thuận nghịch C trên GF(2m) chỉ nhận 
các giá trị thuộc GF(2m), bậc chuẩn syndrome degN có giá trị tùy ý 
trong T. Gọi ID là lớp lỗi bội 2, đường kính D chứa lỗi tại vị trí 1 và D. 
Chuẩn syndrome của các lớp lỗi bội 2 và lỗi đơn không giao nhau, nên 
có thể giải mã mã thuận nghịch theo phương pháp chuẩn syndrome. 
 1 2 v 1
 Cho P1 1, ,...,  tập các chuẩn 
syndrome của các lớp tương đương I1, I2, ..., Iv+1 với các lỗi bội 1, 2 
(ROM 1) 
 1 1 1 i 1
 P2 2 ,3 ,...,v 1, i 1 (ROM 2) 
 Thành phần đầu tiên của syndrome của các lỗi bội 2 có vị trí thứ 
nhất tại i. 
 Thuật toán giải mã mã thuận nghịch gồm các bước sau: 
 i j
 + Tính syndrome S = (si, sj) = (α , α ) 
 + Tính chuẩn syndrome N(S) = αi . αj 
 + So sánh N(S) với các phần tử của ROM 1, nếu N(S) = 1 xảy ra 
lỗi đơn tại vị trí i +1. Nếu N(S) thuộc P1 nghĩa là: 
 N S D P với D >1 thì xảy ra lỗi bội 2 có đường 
 1 
kính D. 
 1
 + Với D tìm được và D P2 tính s1. 
 1 
 D - bộ định vị, chỉ ra lỗi ở vị trí thứ  1 
 + Vị trí thứ 2 của lỗi  1 D mod n 
 + Sửa lỗi bằng cách lấy tổng của vector lỗi e và vector nhận 
được r. 
 9 
2.2.3. Phƣơng pháp chuẩn syndrome giải mã mã Reed-Solomon 
 Mã RS có khoảng cách cấu trúc δ, ma trận kiểm tra H: 
 I  b  2b  3b   n 1 b 
 b 1 2 b 1 3 b 1 n 1 b 1 
 I      
 H (2.17) 
       
 b  2 2 b  2 3 b  2 n 1 b  2 
 I      
 Tương tự với mã BCH tổng quát, chuẩn syndrome Nij của các 
thành phần syndrome được tạo thành từ ma trận kiểm tra (2.17) sẽ được 
tính theo công thức: 
 b i 1 / h
 S ij
 N j (2.18) 
 ij b j 1 / hij 
 Si
 Trong đó hij là ước số chung lớn nhất của i và j 
 Các tính chất cơ bản của chuẩn syndrome đối với mã BCH và mã 
Reed-Solomon tương tự nhau 
 Với mã RS sửa 1 lỗi modul, chuẩn syndrome có thể tính như sau: 
 S2
 NM . (2.26) 
 S1 
 Chuẩn syndrome là bất biến với mọi vector lỗi trong modul, dựa 
vào tham số này sẽ xác định được vị trí modul lỗi. Thuật toán giải mã 
như sau: 
 - Tính syndrome S = (S1, S2). 
 - Tính chuẩn syndrome NM theo công thức (2.26). 
 - Theo NM xác định số hiệu modul bị lỗi k. 
 - Vector lỗi e trong modul k được xác định theo giá trị S1 . 
 - Sửa tín hiệu nhận được bằng cách lấy tổng tín hiệu nhận được 
với vector lỗi tìm được: v = r + e. 
 Mã RS có thể ánh xạ sang mã nhị phân, ví dụ mã RS(7,3) với d = 5, 
với thành phần nguyên thủy là nghiệm của đa thức x3 x 1, có 
khả năng sửa 2 lỗi modul ma trận kiểm tra dạng: 
 I I I I  I 
 1 2 3 6 
 I h h h  h i i i 1 i 2
 H , h (2.27) 
 I h2 h4 h6  h12 
 3 6 9 18 
 I h h h  h 
 10 
 Các thành phần chuẩn syndrome được xác định như sau: 
 S S S 
 N 2 3 4 (N N N ) 
 S S S 1 2 3 (2.28)
 1 2 3 
2.2.4. Sơ đồ cấu trúc thiết bị giải mã mã BCH theo phƣơng pháp 
chuẩn syndrome 
 Sơ đồ cấu trúc bộ giải mã theo phương pháp chuẩn syndrome với 
d = 5 trên hình 2-2 gồm 6 khối: KTS – khối tính syndrome; khối tính 
chuẩn syndrome; khối tính số lượng của sự dịch vòng; khối tính toán 
vector sinh trong σ-orbit; khối tính vector lỗi hiện thời; mạch sửa. 
 v
 r Khối tính N Khối tính e0 Khối tính e Mạch 
 KTS norm vector vector lỗi sửa 
 sinh hiện thời 
 Khối tính 
 lượng dịch 
 vòng 
 Hình 2-2 Sơ đồ cấu trúc bộ giải mã dựa trên chuẩn syndrome 
2.2.5. Sơ đồ cấu trúc thiết bị giải mã mã RS theo chuẩn syndrome 
 Xét mã RS nhị phân (21, 15) với ma trận kiểm tra có dạng: 
 I 3 I 3 I 3 I 3 I 3 I 3 I 3 
 H = 
 0 1 2 3 4 5 6 
 h h h h h h h 
 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
H = 
 0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 0 6 0 1 
 Trên hình 2-6 trình bày sơ đồ cấu trúc của thiết bị giải mã mã RS 
theo phương pháp chuẩn syndrome. Thiết bị giải mã bao gồm khối tính 
syndrome (KTS), khối các mạch AND, khối mạch sửa (MS), khối xác 
định số hiệu modul lỗi (KXĐML). Các đầu vào của khối tính syndrome 
và các đầu vào thứ nhất của MS được nối với nhau và là đầu vào của 
 11 
thiết bị giải mã. Các đầu ra thứ nhất của KTS được nối với đầu vào thứ 
nhất của khối các mạch AND và các đầu vào thứ nhất của KXĐML, các 
đầu vào thứ hai của khối được nối với các đầu ra thứ hai của KTS. Các 
đầu ra của KXĐML được nối với đầu vào thứ hai của khối các mạch 
AND, đầu ra của khối các mạch AND được nối với đầu vào thứ hai của 
MS, đầu ra MS là đầu ra của thiết bị giải mã. 
 Khối tính r 
 syndrome 
 S2 S1 
 Mạch “AND” Mạch sửa 
 & М
 Khối xác định số 
 & 2М v 
 hiệu modul lỗi & 2М 
 & 2М 
 & 2М 
 & 2М 
 & 2М 
 2 
 Hình 2-6 Sơ đồ cấu trúc thiết bị giải mã mã Reed-Solomon 
 S1 
 DC 1 
 0 1 2 3 4 5 6 
 LA 
 0 
 1 
 S2 2 
 DC 2 
 3 
 4 
 5 
 6 degN =0 
 degN = 1 
 degN = 2 
 degN = 3 
 degN = 4 
 degN = 5 
 degN = 6 
 Hình 2-7 Sơ đồ chức năng khối xác định modul lỗi 
 12 
 Trên hình 2-7 trình bày một trong các phương án thực hiện khối 
xác định số hiệu modul lỗi thực hiện trên thiết bị logic lập trình được. 
Khối này bao gồm các bộ giải mã DC1, DC2 để xác định i, j và mảng 
logic (LA). Các đầu vào của khối được nối đến khối KTS, trên đầu ra 
của các bộ giải mã DC1, DC2 tạo ra tín hiệu tương ứng với các giá trị i, 
j, chúng được đưa đến mảng logic. Trên đầu ra của mảng logic tạo ra tín 
hiệu logic 1 phụ thuộc vào giá trị degN = (j-i) mod n, do đó tại đầu ra 
của khối sẽ có tín hiệu tương ứng với số hiệu modul lỗi. 
2.3. Kết hợp phƣơng pháp chuẩn syndrome và phép thế cyclotomic 
2.3.1. Tác động của phép thế cyclotomic lên không gian vector lỗi 
 Phép thế cyclotomic theo modul n với trường GF(q) là tập hợp: 
 2 ms 1 ms
 Cs s, sq, sq , ..., sq , sq s mod n (2.29) 
 Định nghĩa 2.4. Trên tập T = {1, 2, ..., n} biến đổi υ thỏa mãn 
υ(i) = 2i-1 mod n khi đánh số tọa độ vector lỗi từ 1 đến n. Với n lẻ, υ 
là song ánh trên tập T. Khi đánh số tọa độ của vector lỗi từ 0 đến (n-1), 
ta có υ(i) = 2i mod n. Tương tự khi áp dụng biến đổi này k lần ta có: 
υk(i)= i2k mod n. Khi đó các số i, 2i, 22i, ...2m-1i tạo thành một lớp cyclotomic 
theo modul n. Các phép thế υ, υ2, .. υm = 1 gọi là nhóm cyclotomic Φ. 
 1 2 3 4 5 6 7
 e : 0 1 1 1 0 0 0
 φ(e): 0 0 1 0 1 0 1
 φ2(e): 0 1 0 0 1 1 0
 3
 e =φ (e): 0 1 1 1 0 0 0
 Hình 2-8 Tác động của phép thế cyclotomic với vector e = 0111000 
2.3.2. Giải mã theo chuẩn syndrome dựa trên phép thế cyclotomic 
 Với n = 31 trong trường GF(2) tồn tại 6 lớp cyclotomic như sau: 
{1, 2, 4, 6, 8, 16}; {3, 6, 12, 24, 17}; {5, 10, 20, 9, 18}; {7, 14, 28, 25, 
19}; {11, 22, 13, 26, 21}; {15, 30, 29, 27, 23}. Trên bảng 2-9 biểu diễn 
giá trị chuẩn syndrome của các lỗi bội 2 (15 lớp vector) với mã có chiều 
dài 31, với đa thức sinh của trường x5 + x3 + x2 + x + 1. 
 13 
 Bảng 2-9. Vector sinh lỗi bội 2 của các lớp dịch vòng và chuẩn syndrome 
 STT N Vector sinh e0 
 1 3 1100000000000000000000000000000 
 2 6 1010000000000000000000000000000 
 3 14 1001000000000000000000000000000 
 4 12 1000100000000000000000000000000 
 5 30 1000010000000000000000000000000 
 6 28 1000001000000000000000000000000 
 7 19 1000000100000000000000000000000 
 8 24 1000000010000000000000000000000 
 9 23 1000000001000000000000000000000 
 10 29 1000000000100000000000000000000 
 11 27 1000000000010000000000000000000 
 12 25 1000000000001000000000000000000 
 13 15 1000000000000100000000000000000 
 14 7 1000000000000010000000000000000 
 15 17 1000000000000001000000000000000 
 Chuẩn syndrome của các vector lỗi bội 2 thuộc 3 lớp cyclotomic 
({3, 6, 12, 24, 17}; {7, 14, 28, 25, 19}; {15, 30, 29, 27, 23}). Với các mã 
C5 có đa thức sinh khác cũng phân phối chuẩn syndrome của các lỗi bội 
2 thành 3 lớp cyclotomic. Số lượng các tổ hợp chọn lọc có thể rút gọn 5 
lần so với mã C5. 
 Ký hiệu chuẩn syndrome của vector sinh của phần tử đầu tiên 
trong các lớp cyclotomic là Nao, Nbo, Nco (trong ví dụ trên Nao = 3, Nbo = 7, 
Nco = 15). Phương pháp giải mã dựa trên phép thế cyclotomic với mã C5 
như sau: 
 + Tính syndrome S và chuẩn syndrome N của tổ hợp nhận được. 
 + So sánh giá trị N với mỗi giá trị Nao, Nbo, Nco, nếu N trùng với một 
trong các giá trị này sẽ xác định lớp cyclotomic mà N thuộc về lớp đó. 
 + Nếu N không trùng với cả ba giá trị Nao, Nbo, Nco, thực hiện phép 
dịch cyclotomic và lặp lại bước 2. 
 + Xác định lớp cyclotomic mà N thuộc về lớp đó, theo số lượng 
phép dịch cyclotomic, xác định giá trị N = Ndịch, vector sinh tương ứng 
e0. 
 + Theo giá trị S, N, e0 tính giá trị vector lỗi tức thời. 
 14 
 Lưu đồ thuật toán giải mã biểu diễn trên hình 2-9, trong đó N0 xác 
định phần tử đầu tiên của các lớp cyclotomic, F1 – hàm tính giá trị N, F2 – 
hàm tính vector sinh e0, F3 – hàm tính vector lỗi tức thời. 
 Begin 
 r 
 Tính S 
 No Yes 
 Nd= No? 
 Tính N 
 Dịch 
 cyclotomic 
 N = F1(Nd,x) 
 SL phép dịch Nd 
 x = 0 
 eo = F2(No) 
 x = x+1 
 Nd = N 
 e = F3(S,N,eo) 
 e 
 End 
 Hình 2-9 Lưu đồ thuật toán giải mã C5, dựa trên phép thế cyclotomic. 
 Để tiếp tục giảm độ phức tạp giải mã có thể sử dụng phương pháp 
xử lý từng bước các lớp cyclotomic. Xét mã C5, n = 31, biểu thức 
N (N ) mod n (N 2 ) mod n, xác định quy tắc chuyển từ 
 co b0 a0
một lớp cyclotomic này sang lớp khác. Vì vậy có thể chọn 1 trong 3 
phần tử của một lớp cyclotomic và ký hiệu là N0. Quy tắc giải mã theo 
các bước sau: 
 + Tính syndrome S và chuẩn syndrome N. 
 + Chọn N N . 
 0 a0
 + So sánh N và N0 (N trùng N0 chỉ ra lớp cyclotomic chứa giá trị N 
tính được). 
 15 
 + Nếu N không trùng với bất kỳ phần tử nào của lớp cyclotomic thì 
 giá trị phần tử sinh của lớp cyclotomic N0 tăng lên ∆ và so sánh N với N0. 
 + Xác định lớp cyclotomic chứa giá trị chuẩn syndrome N, theo số 
 lượng phép dịch đã thực hiện xác định giá trị N0 = Ndịch theo bảng giá trị 
 tìm vector sinh e0 tương ứng với chuẩn syndrome. 
 + Theo giá trị S, N và e0 xác định vector lỗi hiện thời, giá trị ∆ 
 được chọn phụ thuộc vào lớp cyclotomic được sử dụng. 
 Lưu đồ thuật toán giải mã theo quy tắc giải mã nêu trên được minh 
 họa trên hình 2-10. 
 Begin 
 r 
 Tính S 
 No Yes 
 No=Nd 
 Tính N 
 Yes No 
 x < z N = F1(Nd, x) 
Số lượng dịch 
 x = 0 
 Tăng số 
 lượng dịch eo = F2(No) 
 x = x + 1 No = (No + ∆)mod n 
 Nd = N 
 e= F3(S, N, eo) 
 Dịch 
 Quy không bộ đếm e 
 No = Nao cyclotomic N x = 0 
 End 
 Hình 2-10 Lưu đồ thuật toán giải mã dựa trên xử lý từng bước các 
 lớp cyclotomic cho mã C5 với n = 31 
 2.3.3. Giải mã dựa trên nén chuẩn syndrome 
 Khi S1 ≠ 0 theo công thức (2.7) với mã BCH nguyên thủy (b,n) = 1, 
 phổ syndrome của σ-orbit J = chứa n syndrome khác nhau đôi một 
 |S(J)| = |J| = n, nghĩa là thành phần S1 nhận mỗi một giá trị khác 0 trong 
 m
 trường GF(2 ) đúng 1 lần. Nếu với vector e nào đó thuộc σ-orbit J có S1 
 = 0 thì tất cả các vector của σ-orbit đó đều có thành phần syndrome thứ 
 nhất bằng 0. 
 16 
 Mo,w là liên kết của các σ-orbit của các vector lỗi tạo thành G-orbit. 
Trong bảng 2-12 trình bày tập hợp M0,3, M0,4 liên kết thành các lớp 
dịch vòng trong không gian E15 tạo thành bởi các σ-orbit này, vector 
sinh, syndrome của chúng, thành phần N3 của chuẩn syndrome của mã 
 4
C7 với đa thức sinh của trường x + x +1. Tập hợp 35 vector M0,3 chia 
thành 3 σ-orbit, lớp cyclotomic Φ1 có các vector sinh (1, 12, 13) và 
(1, 8, 10) (mỗi vector này sẽ có thêm 14 vector dịch vòng), lớp Φ2 có 
vector sinh (1, 6, 11) (và 4 dịch vòng của nó). Thành phần chuẩn 
syndrome thứ 3 của các vector thuộc M0,3 trùng với chuẩn syndrome của 
các lỗi bội 4 thuộc tập M0,4. Các σ-orbit của tập hợp M0,3; M0,4 có chuẩn 
syndrome N = (∞, ∞, α5) (gồm một σ-orbit của lỗi bội 3 và 3 σ-orbit lỗi 
bội 4) có phổ syndrome như nhau. Ngoài thành phần thứ 3 của chuẩn 
syndrome, khi bổ sung thêm các giá trị degs2 có thể xác định đơn trị 
vector sinh của các σ-orbit này. Chú ý rằng dưới tác động của phép thế 
cyclotomic giá trị degs2 sẽ được nhân đôi. 
 Bảng 2-12. Vector sinh, syndrome S và chuẩn syndrome N3 
 của tập hợp hợp M0,3; M0,4 
 Lớp Số thứ tự 
 Vector sinh Syndrome N
 cyclotomic σ-orbit 3 
 1 (1,12,13) (0, α8, α10) α5 
 Ф
 1 2 (1,8,10) (0, α1, α5) α10 
 0 
 Ф2 3 (1,6,11) (0, α , 0) 0
 4 (1,2,3,11) (0, α2, α5) α5 
 5 (1,3,5,6) (0, α4, α10) α10 
 Ф
 3 6 (1,5,9,11) (0, α8, α5) α5 
 7 (1,2,6,9) (0, α1, α10) α10 
 8 (1,3,10,13) (0, α11, α5) α5 
 Ф
 4 9 (1,4,5,10) (0, α7, α10) α10 
 12 
 Ф5 10 (1,2,4,8) (0, α , 0) 0
 Giả sử với vector lỗi e tùy ý, syndrome S(e) = (s1, s2, ..., st) có thành 
 h *
phần đầu tiên s1 = α ≠ 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 
 1
thứ nhất bằng 0. Vector g tạo thành tập M 0,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 
 (1,2) (1,3)
 (4,14,10) (8,13,5)
 (1,7) (1,6)
 (1,5) (1,4) (1,8 )
 (9,13,10) (13,14, ) (10, ,5)
 (1,11,10) (14,7, )
 2 5
  14  11   6  7  
 (3,9) (6,11)
f (4,15) (13,12) (2,5) (7,14) (8,10)
 (0,8,5) (0,2,5) (0,10, ) (0,1,10) (0,4,10) (0,5, ) (0, ,0)
 12 (1,12,13) 4 (1,8,10) 8
  9 
  (1,6,11)
  5
 13
 (1,4,15) (1,2,5) (1,7 ,14)  (1,3,9)
 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 
 1
vector thuộc tập M0,w chỉ có w vector thuộc tập M 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. 
 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. 
 h n-h
 3. Nếu s1 = α ≠ 0, sử dụng biến đổi g = τσ (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 
 1 1
thuộc tập M 0,3, M 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 c