Кіріспе
Қателерді түзету коды Кодтау теориясында Бозе–Чаудхури–Хоккенгем кодтары (BCH кодтары) – шекті өріс (Галуа өрісі деп те аталады) арқылы полиномдарды қолдана отырып құрастырылған циклдық қателерді түзету кодтарының класын құрайды. BCH кодтарын 1959 жылы француз математигі Алексис Хоккенгем, ал 1960 жылы тәуелсіз түрде Радж Чандра Бозе және Д. К. Рэй Чаудхури ойлап тапты. Бозе–Чаудхури–Хоккенгем атауы (және BCH аббревиатурасы) өнертапқыштардың тегінің бас әріптерінен шыққан (Рэй Чаудхури жағдайында қателік бар). BCH кодтарының маңызды ерекшеліктерінің бірі – кодты жобалау кезінде кодтың түзетуге қабілетті символ қателерінің санына нақты бақылау мүмкіндігі. Атап айтқанда, бірнеше биттік қателерді түзетуге арналған бинарлық BCH кодтарын жобалауға болады. BCH кодтарының тағы бір артықшылығы – оларды синдромдық декодтау деп аталатын алгебралық әдіс арқылы оңай декодтау мүмкіндігі. Бұл осы кодтарға декодерді жобалауды жеңілдетеді, сондай-ақ кішкентай, аз қуатты электрондық құралдарды пайдалануға мүмкіндік береді. BCH кодтары спутниктік байланыс, компакт-дискі ойнатқыштары, DVD дискілері, дискілік жектер, USB флеш-дискілері, қатты күйдегі дискілер және екі өлшемді штрих-кодтар сияқты қолданыстарда қолданылады.
In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error correcting codes that are constructed using polynomials over a finite field (also called a Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Chandra Bose and D. K. Ray Chaudhuri. The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors' surnames (mistakenly, in the case of Ray Chaudhuri). One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low power electronic hardware. BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, USB flash drives, solid state drives, and two dimensional bar codes.
Бастапқы тар мағыналы BCH кодтары
Q және q^(m) жай сан және d ≤ q^(m) − 1 шарты орындалатын оң бүтін сандар болғанда, GF(q) шекті өрісінде код ұзындығы және қашықтығы кем дегенде d болатын бастапқы тар мағыналы BCH кодын келесі әдіспен құрастыруға болады. α – GF(q^(m)) өрісінің түпнұсқа элементі болсын. Кез келген оң бүтін i үшін, mi(x) – α^(i) түбірі болатын GF(q) коэффициенттерімен ең төменгі дәрежелі көпмүшелік. BCH кодының генераторлық көпмүшелігі – ең кіші ортақ еселік ретінде анықталады. g(x) көпмүшелігі GF(q) коэффициенттерімен берілгендіктен, ол x^(n) − 1-ге бөлінетінін көруге болады. Сондықтан, g(x) арқылы анықталған көпмүшелік код – циклдық код болып табылады.
Кодтау
Өйткені генераторлық полиномға еселі кез келген полином жарамды BCH код сөзі болып табылады, сондықтан BCH кодтау – генераторды түйіндеме ретінде қамтитын полиномды табу процесі ғана. BCH коды полиномның коэффициенттерінің мағынасына қатысты емес; тұжырымдамалық тұрғыдан алғанда, BCH декодилеу алгоритмінің жалғыз мақсаты – алынған код сөзіне ең жақын Хамминг қашықтығындағы жарамды код сөзін табу. Сондықтан, BCH коды жүйелі код түрінде де, сондай-ақ жүйелі емес код түрінде де жүзеге асырылуы мүмкін, бұл еншілеуші кодталған полиномға хабарламаны қалай енгізуге болатындығына байланысты.
Жүйелік кодтау: хабарлама префикс ретінде
Жүйелі код – хабарлама код сөзінің ішінде өзгеріссіз кездесетін код. Сондықтан, жүйелі BCH кодтау алдымен хабарлама полиномын код сөзі полиномына ендіруді, содан кейін қалған (хабарлама емес) мүшелердің коэффициенттерін түзетуді қамтиды, осылайша бөлгішпен бөлінеді. Бұл кодтау әдісі дивидендтен қалдықты шығарудың нәтижесі бөлгіштің еселігіне тең екенін пайдаланады. Сондықтан, егер біз хабарлама полиномын бұрынғыдай алып, оны көбейтіп (хабарламаны қалдықтан "алысқа жылжыту" үшін), онда полиномдарды Евклидтік бөлуді қолданып, мынаны аламыз:
This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial as before and multiply it by (to "shift" the message out of the way of the remainder), we can then use Euclidean division of polynomials to yield:
Мұнда біз жарамды код сөзін көреміз. әрдайым дәрежесінен төмен дәрежелі болғандықтан (ол дәрежесі), біз оны хабарлама коэффициенттерін өзгертпей қауіпсіз түрде шығарып тастай аламыз, сондықтан біздің мынадай болады:
(яғни, бинарлық BCH кодтары үшін) бұл процесс циклдық артық тексеруге қосудан ажыратылмайды, және егер жүйелі бинарлық BCH коды тек қателерді анықтау үшін қолданылса, онда BCH кодтары циклдық артық тексеру математикасының жалпылама түрі екенін көреміз. Жүйелі кодтаудың артықшылығы – қабылдаушы қателерді түзегеннен кейін алғашқы коэффициенттерден кейінгі барлық нәрсені жойып, бастапқы хабарламаны қалпына келтіре алады.
Питерсон-Горенштейн-Зирлер алгоритмі
Питерсон алгоритмі – жалпыланған BCH түсіндіру процедурасының 2-қадамы. Питерсон алгоритмі полиномның қателік локаторының полиномдық коэффициенттерін есептеу үшін қолданылады. Бізде кем дегенде 2t синдром бар деп есептейміз: sc, ..., sc+2t−1. v = t болсын.
Now the procedure of the Peterson–Gorenstein–Zierler algorithm. Expect we have at least 2t syndromes sc, , sc+2t−1. Let v = t.
Фактор қателік локатордың көптік мәні
Енді полиномиал болғандықтан, оның түбірлерін, мысалы, Chien іздеу алгоритмін қолдану арқылы, қара күшпен табуға болады. Бастапқы элементтің экспоненциалдық дәрежелері қабылданған сөзде қателердің орналасқан жерлерін көрсетеді; сондықтан бұл полиномиал "қате анықтағыш" полиномиясы деп аталады. Λ(x) нөлдері α−i1, , α−iv болып табылады.
powers of the primitive element will yield the positions where errors occur in the received word; hence the name 'error locator' polynomial. The zeros of Λ(x) are α−i1, , α−iv.
Қате мәндерін есептеу
Қателердің орналасқан жерлері белгілі болғаннан кейін, келесі қадам - сол жерлердегі қателік шамаларын анықтау. Бұл қателік шамалары бастапқы кодты сөзді қалпына келтіру үшін сол жерлерде алынған мәндерді түзетуге қолданылады. Бинарлық BCH коды үшін (барлық символдар оқылса) бұл өте оңай; алынған сөздің сол позициялардағы биттерін кері ауыстырсаңыз, түзетілген кодты сөзді аласыз. Көбінесе, қателік салмақтарын сызықтық теңдеулер жүйесін шешу арқылы анықтауға болады.
Қателерді түзету
Қателердің мәні мен орналасқан жерін пайдаланып, қателерді түзету үшін қателер орналасқан жерлердегі қателер мәнін кесіп тастап, түзетілген код векторын құрастырыңыз.
Екіншілік көздер
Курстық жазбалар 2012 жылға қарай жаңарып жатыр деген хабар бар: http://www.stanford.edu/class/ee387/