A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a multilevel, cyclic, error-correcting, variable-length digital code used to correct errors up to approximately 25% of the total number of digits. BCH codes are not limited to Binary Code codes, but may be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign numerical digit. BCH codes make use of field theory (mathematics) and polynomials over that field. The way the check polynomial is constructed provides the key to indicating that an error has occurred. If we wish to construct a BCH code to detect and correct 2 errors we use the finite field GF(16) or Z2[''x'']/<''x''4+''x''+1> Now if we have α a root of ''x''4+''x''+1, ''m''1(''x'')=''x''4+''x''+1. Now ''m''1 is minimal for α since :''m''1(''x'')=(''x''-α)(''x''-α2)(''x''-α4)(''x''-α8)=''x''4+''x''+1. If we wish to construct a code to correct 1 error we use ''m''1(''x''). Our codewords will be : ''C''(''x'')≡0 (mod ''m''1(''x'')) which has roots α, α2, α4, α8. This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α3, and then the minimal polynomial for this is :''m''3(''x'')=''x''4+''x''3+''x''2+''x''+1. which has roots α3, α6, α12, α24=α9. We take codewords having all of these as roots, so we form the polynomial :''m''1,3(''x'')=''m''1(''x'')''m''3(''x'')=''x''8+''x''7+''x''6+''x''4+1 and take codewords corresponding to polynomials of degree 14 such that : ''C''(''x'')≡0 (mod ''m''1,3(''x'')) So now ''C''(α)=''C''(α2)=...=''C''(α8)=0. (*) Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*). == Encoding == Construct our information codeword as : (''c''14, ''c''13, ..., ''c''8) so our polynomial will be : ''c''14+''c''13+...+''c''8 Call this ''C''I. We then want to find a ''C''R such that ''C''R=''C''I (mod ''m''1,3(''x''))=''c''7+''c''6+...+''c''0 So we have the following codeword to send ''C''(''x'') = ''C''I+''C''R (mod ''m''1,3(''x'')) = 0 For example, if we are to encode (1,1,0,0,1,1,0) : ''C''I=''x''14+''x''13+''x''10+''x''9 and using polynomial long division of ''m''1,3(''x'') and ''C''I to get ''C''R(''x''), in Z2 we obtain ''C''R to be : ''x''3+1 So then the codeword to send is :(1,1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1) == Decoding == Suppose we receive a codeword vector r (the polynomial ''R''(''x'')). If there is no error R(α)=R(α3)=0 If there is one error, ie r=c+ei where e''i'' represents the ''i''th basis vector for R14 So then :''S''1=''R''(α)=''C''(α)+α''i''=αi :''S''3=''R''(α3)=C(α3)+(α3)i :: =(αi)3=''S''13 so we can recognize one error. A change in the bit position shown by α's power will aid us correct that error. If there are two errors :r=c+e''i''+e''j'' then :''S''1=''R''(α)=''C''(α)+α''i''+α''j'' :''S''3=''R''(α3)=C(α3)+(α3)''i''+(α3)''j'' :: = (α3)''i''+(α3)''j'' which is not the same as ''S''13 so we can recognize ''two'' errors. Further algebra can aid us in correcting these two errors. ''Original source (first two paragraphs) from Federal Standard 1037C'' Error detection and correction
See other meanings of words starting from letter:
Words begining with BCH_code:
BCH_code
BCH code
A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a multilevel, cyclic, error-correcting, variable-length digital code used to correct errors up to approximately 25% of the total number of digits. BCH codes are not limited to Binary Code codes, but may be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign numerical digit. BCH codes make use of field theory (mathematics) and polynomials over that field. The way the check polynomial is constructed provides the key to indicating that an error has occurred. If we wish to construct a BCH code to detect and correct 2 errors we use the finite field GF(16) or Z2[''x'']/<''x''4+''x''+1> Now if we have α a root of ''x''4+''x''+1, ''m''1(''x'')=''x''4+''x''+1. Now ''m''1 is minimal for α since :''m''1(''x'')=(''x''-α)(''x''-α2)(''x''-α4)(''x''-α8)=''x''4+''x''+1. If we wish to construct a code to correct 1 error we use ''m''1(''x''). Our codewords will be : ''C''(''x'')≡0 (mod ''m''1(''x'')) which has roots α, α2, α4, α8. This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α3, and then the minimal polynomial for this is :''m''3(''x'')=''x''4+''x''3+''x''2+''x''+1. which has roots α3, α6, α12, α24=α9. We take codewords having all of these as roots, so we form the polynomial :''m''1,3(''x'')=''m''1(''x'')''m''3(''x'')=''x''8+''x''7+''x''6+''x''4+1 and take codewords corresponding to polynomials of degree 14 such that : ''C''(''x'')≡0 (mod ''m''1,3(''x'')) So now ''C''(α)=''C''(α2)=...=''C''(α8)=0. (*) Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*). == Encoding == Construct our information codeword as : (''c''14, ''c''13, ..., ''c''8) so our polynomial will be : ''c''14+''c''13+...+''c''8 Call this ''C''I. We then want to find a ''C''R such that ''C''R=''C''I (mod ''m''1,3(''x''))=''c''7+''c''6+...+''c''0 So we have the following codeword to send ''C''(''x'') = ''C''I+''C''R (mod ''m''1,3(''x'')) = 0 For example, if we are to encode (1,1,0,0,1,1,0) : ''C''I=''x''14+''x''13+''x''10+''x''9 and using polynomial long division of ''m''1,3(''x'') and ''C''I to get ''C''R(''x''), in Z2 we obtain ''C''R to be : ''x''3+1 So then the codeword to send is :(1,1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1) == Decoding == Suppose we receive a codeword vector r (the polynomial ''R''(''x'')). If there is no error R(α)=R(α3)=0 If there is one error, ie r=c+ei where e''i'' represents the ''i''th basis vector for R14 So then :''S''1=''R''(α)=''C''(α)+α''i''=αi :''S''3=''R''(α3)=C(α3)+(α3)i :: =(αi)3=''S''13 so we can recognize one error. A change in the bit position shown by α's power will aid us correct that error. If there are two errors :r=c+e''i''+e''j'' then :''S''1=''R''(α)=''C''(α)+α''i''+α''j'' :''S''3=''R''(α3)=C(α3)+(α3)''i''+(α3)''j'' :: = (α3)''i''+(α3)''j'' which is not the same as ''S''13 so we can recognize ''two'' errors. Further algebra can aid us in correcting these two errors. ''Original source (first two paragraphs) from Federal Standard 1037C'' Error detection and correction
See other meanings of words starting from letter:
B
BA | BC | BD | BE | BF | BG | BH | BI | BJ | BK | BL | BM | BN | BO | BP | BR | BS | BT | BU | BW | BX | BY | BZ |Words begining with BCH_code:
BCH_code
Sponsored links: praca.
These materials are based on Wikipedia and licensed under the GNU FDL
Untitled Document
| Linki sponsorowane | Tani hosting | Pozycjonowanie |
YouTube.com videos better site than Turbo Tax 2007
