Mã BCH là gì? Chi tiết về Mã BCH mới nhất 2021

Bách khoa toàn thư mở Wikipedia

Bước tới điều hướng
Bước tới tìm kiếm

Trong lý thuyết mã hóa, mã BCH là một lớp các mã sửa lỗi vòng xây dựng bằng trường hữu hạn. Mã BCH được phát minh năm 1959 bởi Hocquenghem, và một cách độc lập năm 1960 bởi Bose và Ray-Chaudhuri.[1] Tên viết tắt BCH gồm chữ cái đầu của tên những người phát minh ra loại mã này.

Một trong những tính năng chính của mã BCH là khi thiết kế, có thể điều chỉnh chính xác số lỗi mã có thể sửa được. Cụ thể hơn, có thể thiết kế mã BCH nhị phân sửa được nhiều lỗi bit. Một lợi thế khác của mã BCH là có thể giải mã dễ dàng bằng một phương pháp đại số gọi là giải mã hội chứng. Điều này giúp đơn giản hóa việc thiết kế bộ giải mã cho mã này bằng phần cứng điện tử sử dụng ít năng lượng.

Mã BCH được dùng trong nhiều ứng dụng như liên lạc vệ tinh,[2] máy nghe CD, DVD, ổ đĩa, SSD[3] và mã vạch hai chiều.

Cách xây dựng[sửa | sửa mã nguồn]

Mã BCH nghĩa hẹp nguyên thủy[sửa | sửa mã nguồn]

Với một số nguyên tố




q


{displaystyle q}

và hai số nguyên dương




m


{displaystyle m}




d


{displaystyle d}

thỏa mãn




d


q

m



1


{displaystyle dleq q^{m}-1}

, một mã BCH nghĩa hẹp nguyên thủy trên trường hữu hạn





G
F

(
q
)


{displaystyle mathrm {GF} (q)}

với chiều dài mã




n
=

q

m



1


{displaystyle n=q^{m}-1}

và khoảng cách nhỏ nhất lớn hơn hoặc bằng




d


{displaystyle d}

được xây dựng như sau.

Đặt




α


{displaystyle alpha }

là một phần tử nguyên thủy của





G
F

(

q

m


)


{displaystyle mathrm {GF} (q^{m})}

. Với mọi số nguyên dương




i


{displaystyle i}

, đặt





m

i


(
x
)


{displaystyle m_{i}(x)}

là đa thức nhỏ nhất của

Có thể bạn quan tâm  Sao khổng lồ đỏ là gì? Chi tiết về Sao khổng lồ đỏ mới nhất 2021




α

i




{displaystyle alpha ^{i}}

. Đa thức sinh của mã BCH được định nghĩa là bội chung nhỏ nhất




g
(
x
)
=


l
c
m


(

m

1


(
x
)
,

,

m

d

1


(
x
)
)


{displaystyle g(x)={rm {lcm}}(m_{1}(x),ldots ,m_{d-1}(x))}

. Có thể thấy




g
(
x
)


{displaystyle g(x)}

là một đa thức có hệ số trong





G
F

(
q
)


{displaystyle mathrm {GF} (q)}

và chia hết





x

n



1


{displaystyle x^{n}-1}

. Do đó mã đa thức định nghĩa bởi




g
(
x
)


{displaystyle g(x)}

là một mã vòng.

Ví dụ[sửa | sửa mã nguồn]

Đặt




q
=
2


{displaystyle q=2}




m
=
4


{displaystyle m=4}

(nên




n
=
15


{displaystyle n=15}

). Ta sẽ xét các giá trị khác nhau cho




d


{displaystyle d}

. Tồn tại nghiệm nguyên thủy




α

G
F
(
16
)


{displaystyle alpha in GF(16)}

thỏa mãn

 

 

 

 

(1)

đa thức nhỏ nhất của nó trên




G
F
(
2
)


{displaystyle GF(2)}

là:





m

1


(
x
)
=

x

4


+
x
+
1


{displaystyle m_{1}(x)=x^{4}+x+1}

.
Ghi chú là trong




G
F
(

2

4


)


{displaystyle GF(2^{4})}

, đẳng thức




(
a
+
b

)

2


=

a

2


+
a
b
+
a
b
+

b

2


=

a

2


+

b

2




{displaystyle (a+b)^{2}=a^{2}+ab+ab+b^{2}=a^{2}+b^{2}}

là đúng, nên





m

1


(

α

2


)
=

m

1


(
α

)

2


=



{displaystyle m_{1}(alpha ^{2})=m_{1}(alpha )^{2}=0}

.
Vì vậy





α

2




{displaystyle alpha ^{2}}

là nghiệm của





m

1


(
x
)


{displaystyle m_{1}(x)}

, nên

Để tính





m

3


(
x
)


{displaystyle m_{3}(x)}

, có thể thấy, bằng cách áp dụng (1) nhiều lần, ta thu được hệ các quan hệ tuyến tính sau:

Năm vế phải là các tổ hợp tuyến tính của 4 lũy thừa giống nhau nên chúng phụ thuộc tuyến tính. Thật vậy, ta có tổ hợp tuyến tính





α

12


+

α

9


+

α

6


+

α

3


+
1
=



{displaystyle alpha ^{12}+alpha ^{9}+alpha ^{6}+alpha ^{3}+1=0}

.
Vì không tồn tại quan hệ phụ thuộc tuyến tính bậc nhỏ hơn nên đa thức nhỏ nhất của





α

3




{displaystyle alpha ^{3}}

là:





m

3


(
x
)
=

x

4


+

x

3


+

x

2


+
x
+
1


{displaystyle m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1}

.
Tiếp tục tương tự như vậy, ta tìm được

Mã BCH với




d
=
1
,
2
,
3


{displaystyle d=1,2,3}

có đa thức sinh

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 3, và do đó sửa được 1 lỗi. Vì đa thức sinh có bậc 4, mã này có 11 bit dữ liệu và 4 bit kiểm tra.

Mã BCH với




d
=
4
,
5


{displaystyle d=4,5}

có đa thức sinh

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 5 và do đó sửa được 2 lỗi. Vì đa thức có bậc 8, mã này có 7 bit dữ liệu và 8 bit kiểm tra.

Mã BCH với




d
=
6
,
7


{displaystyle d=6,7}

có đa thức sinh

Nó có khoảng cách Hamming nhỏ nhất lớn hơn hoặc bằng 7 và do đó sửa được 3 lỗi. Mã này có 5 bit dữ liệu và 10 bit kiểm tra.

Mã BCH với




d
=
8


{displaystyle d=8}

và lớn hơn có đa thức sinh

Mã này có khoảng cách Hamming nhỏ nhất bằng 15 và sửa được 7 lỗi. Nó có 1 bit dữ liệu và 14 bit kiểm tra. Mã này chỉ có đúng hai mã tự: 000000000000000 và 111111111111111.

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Reed & Chen 1999, tr. 189
  2. ^

    “Phobos Lander Coding System: Software and Analysis” (PDF). Truy cập ngày 25 tháng 2 năm 2012.

  3. ^ “Sandforce SF-2500/2600 Product Brief”. Truy cập ngày 25 tháng 2 năm 2012.

Tham khảo[sửa | sửa mã nguồn]

Tài liệu nguyên thủy[sửa | sửa mã nguồn]

  • Hocquenghem, A. (9/1959), “Codes correcteurs d’erreurs”, Chiffres (bằng tiếng Pháp), Paris, 2: 147–156 Kiểm tra giá trị ngày tháng trong: |date= (trợ giúp)
  • Bose, R. C.; Ray-Chaudhuri, D. K. (3/1960), “On A Class of Error Correcting Binary Group Codes”, Information and Control, 3 (1): 68–79, ISSN 0890-5401 Kiểm tra giá trị ngày tháng trong: |date= (trợ giúp)

Tài liệu khác[sửa | sửa mã nguồn]

  • Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (ấn bản 2), John Wiley
  • Gill, John (unknown), EE387 Notes #7, Handout #28 (PDF), Stanford University, tr. 42–45, truy cập ngày 21 tháng 4 năm 2010 Kiểm tra giá trị ngày tháng trong: |year= (trợ giúp)
  • Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal (1960), “Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect”, Information and Control, 3 (3): 291–294
  • Lidl, Rudolf; Pilz, Günter (1999), Applied Abstract Algebra (ấn bản 2), John Wiley
  • Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall
  • MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
  • Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-8528-4
  • Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, truy cập ngày 21 tháng 4 năm 2010


Lấy từ “https://vi.wikipedia.org/w/index.php?title=Mã_BCH&oldid=64435766”

Từ khóa: Mã BCH, Mã BCH, Mã BCH

LADIGI – Công ty dịch vụ SEO LADIGI giá rẻ, SEO từ khóa, SEO tổng thể cam kết lên Top Google uy tín chuyên nghiệp, an toàn, hiệu quả.

Nguồn: Wikipedia

Scores: 4.7 (166 votes)

100 lần tự tìm hiểu cũng không bằng 1 lần được tư vấn




    Mã giảm giá
    SHOPEE 100K