imported>Dangvantai987: /* growthexperiments-addlink-summary-summary:2|0|0 */

2023-02-27T01:03:25Z

growthexperiments-addlink-summary-summary:2|0|0

Trang mới

Trong [[lý thuyết mã hóa]], '''mã BCH''' là một lớp các [[Phát hiện và sửa lỗi|mã sửa lỗi]] [[mã vòng|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 [[Alexis Hocquenghem|Hocquenghem]], và một cách độc lập năm 1960 bởi [[Raj Chandra Bose|Bose]] và [[D.K. Ray-Chaudhuri|Ray-Chaudhuri]].<ref>{{Harvnb|Reed|Chen|1999|p=189}}</ref> 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,<ref>{{chú thích web|title=Phobos Lander Coding System: Software and Analysis|url=http://ipnpr.jpl.nasa.gov/progress_report/42-94/94V.PDF|accessdate =ngày 25 tháng 2 năm 2012}}</ref> máy nghe [[CD]], [[DVD]], [[ổ đĩa]], [[SSD]]<ref>{{chú thích web|title=Sandforce SF-2500/2600 Product Brief|url=http://www.sandforce.com/index.php?id=133&parentId=2&top=1|accessdate =ngày 25 tháng 2 năm 2012}}</ref> và [[Mã vạch|mã vạch hai chiều]].

== Cách xây dựng ==
=== Mã BCH nghĩa hẹp nguyên thủy ===

Với một số nguyên tố <math>q</math> và hai số nguyên dương <math>m</math> và <math>d</math> thỏa mãn <math>d \leq q^m - 1</math>, một mã BCH nghĩa hẹp nguyên thủy trên trường hữu hạn <math>\mathrm{GF}(q)</math> với [[chiều dài]] mã <math>n = q^m - 1</math> và khoảng cách nhỏ nhất lớn hơn hoặc bằng <math>d</math> được xây dựng như sau.

Đặt <math>\alpha</math> là một [[Phần tử nguyên thủy (trường hữu hạn)|phần tử nguyên thủy]] của <math>\mathrm{GF}(q^m)</math>. Với mọi số nguyên dương <math>i</math>, đặt <math>m_i(x)</math> là [[đa thức nhỏ nhất (lý thuyết trường)|đa thức nhỏ nhất]] của <math>\alpha^i</math>. [[Đa thức]] sinh của mã BCH được định nghĩa là [[bội chung nhỏ nhất]] <math>g(x) = {\rm lcm}(m_1(x),\ldots,m_{d-1}(x))</math>. Có thể thấy <math>g(x)</math> là một đa thức có hệ số trong <math>\mathrm{GF}(q)</math> và chia hết <math>x^n - 1</math>. Do đó mã đa thức định nghĩa bởi <math>g(x)</math> là một mã vòng.

=== Ví dụ ===

Đặt <math>q=2</math> và <math>m=4</math> (nên <math>n=15</math>). Ta sẽ xét các giá trị khác nhau cho <math>d</math>. Tồn tại nghiệm nguyên thủy <math>\alpha\in GF(16)</math> thỏa mãn
:{{NumBlk|:|<math>\alpha^4+\alpha+1=0</math>|{{EquationRef|1}}}}
đa thức nhỏ nhất của nó trên <math>GF(2)</math> là: <math>m_1(x) = x^4+x+1</math>.
Ghi chú là trong <math>GF(2^4)</math>, đẳng thức <math>(a+b)^2 = a^2 + ab + ab + b^2 = a^2 + b^2</math> là đúng, nên
<math>m_1(\alpha^2) = m_1(\alpha)^2 = 0</math>.
Vì vậy <math>\alpha^2</math> là nghiệm của <math>m_1(x)</math>, nên
:<math>m_2(x) = m_1(x) = x^4+x+1</math>.
Để tính <math>m_3(x)</math>, có thể thấy, bằng cách áp dụng ({{EquationNote|1}}) nhiều lần, ta thu được hệ các quan hệ tuyến tính sau:
* <math>1 = 0\alpha^3 + 0\alpha^2 + 0\alpha + 1</math>
* <math>\alpha^3 = 1\alpha^3 + 0\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^6 = 1\alpha^3 + 1\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^9 = 1\alpha^3 + 0\alpha^2 + 1\alpha + 0</math>
* <math>\alpha^{12} = 1\alpha^3 + 1\alpha^2 + 1\alpha + 1</math>
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 <math>\alpha^{12}+\alpha^9+\alpha^6+\alpha^3+1=0</math>.
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 <math>\alpha^3</math> là:<math>m_3(x) = x^4+x^3+x^2+x+1</math>.
Tiếp tục tương tự như vậy, ta tìm được

:<math>m_4(x) = m_2(x) = m_1(x) = x^4+x+1,\,</math>
:<math>m_5(x) = x^2+x+1,\,</math>
:<math>m_6(x) = m_3(x) = x^4+x^3+x^2+x+1,\,</math>
:<math>m_7(x) = x^4+x^3+1.\,</math>

Mã BCH với <math>d=1,2,3</math> có đa thức sinh

:<math>g(x) = m_1(x) = x^4+x+1.\,</math>

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 <math>d=4,5</math> có đa thức sinh

:<math>g(x) = {\rm lcm}(m_1(x),m_3(x)) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1.\,</math>

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 <math>d=6,7</math> có đa thức sinh

:<math>
\begin{align}
g(x) & {} = {\rm lcm}(m_1(x),m_3(x),m_5(x)) \\
& {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) \\
& {} = x^{10}+x^8+x^5+x^4+x^2+x+1.
\end{align}
</math>

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 <math>d=8</math> và lớn hơn có đa thức sinh

:<math>
\begin{align}
g(x) & {} = {\rm lcm}(m_1(x),m_3(x),m_5(x),m_7(x)) \\
& {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)(x^4+x^3+1) \\
& {} = x^{14}+x^{13}+x^{12}+\cdots+x^2+x+1.
\end{align}
</math>

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ú==
{{Tham khảo}}

==Tham khảo==
===Tài liệu nguyên thủy===
* {{chú thích
|first= A.
|last= Hocquenghem
|author-link= Alexis Hocquenghem
|title=Codes correcteurs d'erreurs
|language= fr
|journal= Chiffres
|location= Paris
|volume=2
|pages= 147–156
|date= 9/1959
|issn=
|doi=}}
*{{chú thích
|first= R. C.
|last= Bose
|author-link= R. C. Bose
|first2= D. K.
|last2= Ray-Chaudhuri
|author2-link= D. K. Ray-Chaudhuri
|title= On A Class of Error Correcting Binary Group Codes
|journal= [[Information and Control]]
|volume= 3
|issue=1
|pages= 68–79
|date= 3/1960
|issn= 0890-5401
|doi=}}

===Tài liệu khác===
*{{chú thích
|first= W. J.
|last= Gilbert
|first2= W. K.
|last2= Nicholson
|title= Modern Algebra with Applications
|edition= 2
|publisher= John Wiley
|year= 2004
|url=
|isbn=
|doi=}}
*{{chú thích
|last= Gill
|first= John
|title= EE387 Notes #7, Handout #28
|year= unknown
|accessdate= ngày 21 tháng 4 năm 2010
|pages= 42–45
|publisher= Stanford University
|url= http://www.stanford.edu/class/ee387/handouts/notes7.pdf
|doi=
|access-date= 2012-04-17
|archive-date= 2014-06-30
|archive-url= https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
}}
*{{chú thích
|last= Gorenstein
|first= Daniel
|authorlink= Daniel Gorenstein
|last2= Peterson
|first2= W. Wesley
|authorlink2= W. Wesley Peterson
|last3= Zierler
|first3 = Neal
|authorlink3= Neal Zierler
|title= Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect
|journal= Information and Control
|volume= 3
|issue= 3
|pages= 291–294
|year= 1960
|doi= }}
*{{chú thích
|first= Rudolf
|last= Lidl
|first2= Günter
|last2= Pilz
|title= Applied Abstract Algebra
|edition= 2
|publisher= John Wiley
|year= 1999
|url=
|isbn=
|doi=}}
*{{chú thích
|first= S.
|last= Lin
|first2= D.
|last2= Costello
|title= Error Control Coding: Fundamentals and Applications
|publisher= Prentice-Hall
|location= Englewood Cliffs, NJ
|year= 2004
|isbn=
|doi= }}
*{{chú thích
|first= F. J.
|last=MacWilliams
|first2= N. J. A.
|last2= Sloane
|authorlink2= N. J. A. Sloane
|title= The Theory of Error-Correcting Codes
|location= New York, NY
|publisher= North-Holland Publishing Company
|year= 1977
|isbn=
|doi=}}
*{{chú thích
|first= Irving S.
|last= Reed
|authorlink= Irving S. Reed
|first2= Xuemin
|last2= Chen
|title= Error-Control Coding for Data Networks
|location= Boston, MA
|publisher= [[Kluwer Academic Publishers]]
|year= 1999
|isbn= 0-7923-8528-4
|doi=}}
*{{chú thích
|first= Atri
|last= Rudra
|title= CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications
|publisher= University at Buffalo
|url= http://www.cse.buffalo.edu/~atri/courses/coding-theory/
|accessdate= ngày 21 tháng 4 năm 2010
|doi=
|access-date= 2012-04-17
|archive-date= 2010-07-02
|archive-url= https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
}}

{{DEFAULTSORT:BCH, Mã}}
[[Thể loại:Phát hiện và sửa lỗi]]
[[Thể loại:Trường hữu hạn]]
[[Thể loại:Lý thuyết mã hóa]]

Mã BCH - Lịch sử thay đổi

imported>Dangvantai987: /* growthexperiments-addlink-summary-summary:2|0|0 */