Кіріспе

Блок кодтың түрі

Кодтау теориясында, циклді код – әрбір код сөзінің шеңберлік ығысымы осы кодқа жататын басқа сөзді беретін блок код. Олар алгебралық қасиеттері тиімді қателерді анықтау және түзетуге қолайлы қателерді түзету кодтары болып табылады.

Анықтама

Блок ұзындығы шекті өрісте (Галуа өрісі деп те аталады) берілген сызықтық код, егер кез келген код сөзі үшін компоненттердің циклді оңға жылжуынан алынған сөз де код сөзі болса, циклді код деп аталады. Бір циклді оңға жылжу циклді солға жылжуға тең болғандықтан, циклді кодты циклді солға жылжу арқылы да анықтауға болады. Сондықтан сызықтық код, егер ол барлық циклдік жылжулар бойынша өзгермейтін болса, циклді болып табылады. Циклді кодтар кодтардың құрылымына қосымша шектеулер қояды. Олар Галуа өрістеріне негізделген және олардың құрылымдық қасиеттері оларды қателіктерді түзетуге өте пайдалы етеді. Олардың құрылымы Галуа өрістерімен тығыз байланысты, сондықтан циклді кодтарды кодтау және декодтау алгоритмдері есептеу тұрғысынан тиімді.

Қарапайым мысалдар

Циклдік кодтардың қарапайым мысалдары – өзі және тек нөлдік кодты сөзден тұратын код. Олар сәйкесінше генераторларға және сәйкес келеді: бұл екі полином әрқашан бөлігіштері болуы керек. барлық жұп салмақты сөздерден тұратын, паритет біті кодтарында генераторға сәйкес келеді. Қайтадан бойынша, бұл әрқашан бөлігішсі болуы керек.

Квазициклдік кодтар және қысқартылған кодтар

Циклдік кодтардың толық мәліметтерін қарастырудан бұрын, олармен тығыз байланысты және бір-біріне айналдырылатын квазициклдік және қысқартылған кодтарды қарастырамыз.

Хамминг коды

Хамминг (7,4) коды GF(2) үстінде циклдік код ретінде жазылуы мүмкін. Шындығында, Ham(r, 2) түріндегі кез келген екілік Хамминг коды циклдік кодқа эквивалентті, ал r және q 1-ге өте жақын жай сандар болғанда Ham(r,q) түріндегі кез келген Хамминг коды да циклдік кодқа эквивалентті болады. Ham(r,2) түріндегі Хамминг коды берілгенде, жұп код сөздер жиыны циклдік кодты құрайды.

Бір қателерді түзету үшін Хамминг коды

Ең аз қашықтығы 3-тен кем емес кодтың барлық бағандары өзгеше және нөлдік емес тексеру матрицасы болады. Егер бинарлық кодтың тексеру матрицасында қатарлар болса, онда әрбір баған биттік сан болады. Мүмкін бағандар бар. Сондықтан, егер 3-тен кем емес қашықтығы бар бинарлық кодтың тексеру матрицасында қатарлар болса, онда ол тек бағандарға ие бола алады, одан көп емес. Бұл Хамминг коды деп аталатын кодты анықтайды. Үлкен алфавиттер үшін Хамминг кодтарын анықтау оңай. Бізге сызықтық тәуелсіз бағандары бар бір матрицаны анықтауымыз керек. Кез келген өлшемі бар сөз үшін бір-бірінің есесіндегі бағандар болады. Сондықтан, сызықтық тәуелсіздікке қол жеткізу үшін, жоғарғы нөлдік емес элементі 1 болатын барлық нөлдік емес топтар бағандар ретінде таңдалады. Содан кейін екі баған ешқашан сызықтық тәуелді болмайды, өйткені кодтың ең аз қашықтығы 3 болғандықтан үш баған сызықтық тәуелді болуы мүмкін. Сондықтан, жоғарғы нөлдік емес элементі 1 болатын нөлдік емес бағандар бар. Сондықтан, Хамминг коды - бұл код. Енді, циклдық кодтар үшін, мысалы, болсын, және болсын. Онда және осылайша - полиномның түбірі және циклдық кодтың блок ұзындығы үшін генераторлық полином болады. Бірақ және алынған сөз дәрежесі бар полином ретінде берілген:

мұнда немесе , мұнда қателік орындарын көрсетеді. Бірақ біз қателік орынын индекстеу үшін элементін де пайдалана аламыз. Себебі және -нің барлық дәрежелері әртүрлі. Сондықтан, егер болмаса, қателік орнын анықтау оңай. Осылайша, Хамминг коды - бұл және арқылы берілген кеңістікте бір қателікті түзететін код.

Жарылу қателерін түзету үшін

Хамминг қашықтығы тұжырымдамасы бойынша, ең төменгі қашықтығы бар код кез келген қателерді түзете алады. Бірақ көптеген каналдарда қателік үлгісі толығымен кездейсоқ болмайды, ол хабарламаның өте қысқа бөлігінде пайда болады. Мұндай қателер жарылыс қателері деп аталады. Сондықтан, мұндай қателерді түзету үшін біз шектеулердің аздығына байланысты жоғары жылдамдықты, тиімді код аламыз. Жарылыс қателерін түзету үшін циклдық кодтар қолданылады. Шындығында, циклдық кодтар жарылыс қателерімен қатар циклдық жарылыс қателерін де түзете алады. Циклдық жарылыс қателері былай анықталады:

Ұзындығы бар циклдық жарылыс – бұл вектор, оның нөлдік емес компоненттері (циклдік) тізбектелген компоненттердің арасында орналасқан, ал бірінші және соңғы компоненттері нөлдік емес. Полиномдық түрінде ұзындығы бар циклдық жарылыс нөлдік емес коэффициенті бар дәрежелі полином ретінде сипатталады. Мұнда полином үлгіні, ал қателік басталу орнын анықтайды. Үлгінің ұзындығы deg арқылы беріледі. Полиномдық синдром әрбір үлгі үшін бірегей және былай беріледі.

Ұзындығы немесе одан кем жарылыс қателердің барлығын түзететін сызықтық блок коды кемінде тексеру символына ие болуы керек. Дәлел: Ұзындығы немесе одан кем жарылыс үлгісін түзетуге қабілетті кез келген сызықтық кодта, ұзындығы немесе одан кем жарылыс код сөзі болмауы керек, өйткені егер ол болса, онда ұзындығы бар жарылыс код сөзін ұзындығы бар жарылыс үлгісіне өзгерте алады, оны нөлдік код сөзінде ұзындығы бар жарылыс қатесін жасау арқылы да алуға болады. Енді, бірінші компоненттерінде нөлдік емес екі вектор әртүрлі ко-жиынтықта болуы керек, олардың айырмасы ұзындығы бар жарылыс код сөзі болмауы үшін. Сондықтан, мұндай ко-жиынтықтардың саны осындай векторлардың санына тең, демек кемінде ко-жиынтық және кемінде тексеру символы болуы керек. Бұл қасиет Ригер шекарасы деп те аталады және ол кездейсоқ қателерді түзету үшін Синглтон шекарасына ұқсас.

Фурье трансформациясында

Фурье трансформациясы сигналдарды өңдеуде кеңінен қолданылады. Бірақ оның қолданылуы тек күрделі салалармен ғана шектелмейді; Фурье трансформациялары Галуа өрісінде де кездеседі. Фурье трансформациясын қолданатын циклдық кодтарды сигналдарды өңдеуге жақын тұрғыда сипаттауға болады.

BCH-ге байланысты

Егер -ның бір белгісі болса, кейбір үшін, салмағы немесе одан аз болатын векторындағы спектрдің ретті компоненттерінің нөлге тең болуының жалғыз векторы - бұл нөлдік вектор.

Хартман-Ценгке қарай

Егер қандай да бір үшін саны санының бөлгіші болса, және -і санымен өзара жай сандар болса, онда салмағы немесе одан кем векторының спектрлік компоненттері -ге тең болатын жалғыз вектор нөлдік вектор болады, мұнда және .

Қайықталған құстар

Егер a, кейбір b үшін бөлгіш болса және b салмағы 0-ге тең немесе одан кем болса, онда a диапазонында кеміндегі мәнді қабылдайтын, салмағы 0-ге тең немесе одан кем болатын және спектрлік компоненттері i-ге тең болатын жалғыз вектор – нөлдік вектор болады.

Қалдықтардың квадраттық кодтары

Егер жай сан жай санға қатысты квадраттық қалдық болса, онда ұзындығы , өлшемі және ең аз салмағы кем дегенде болатын циклдік код – квадраттық қалдық коді болады.

Жалпылау

Констациклдік код – белгілі бір тұрақты λ үшін, егер (c1, c2, ..., cn) кодты сөз болса, онда (λcn, c1, ..., cn-1) да кодты сөз болып табылады. Негациклдік код – λ=1 констациклдік код. Квазициклдік кодтың қасиеті – кейбір s үшін, кодты сөздің s орынға циклдік ығысуы да кодты сөз болып табылады. Екі реттік циркуляциялық код – жұп ұзындығы бар және s=2 квазициклдік код.