Тэорыя кадавання, алгебраічнай геаметрыі і базіс Гребнера

Кантэкст

Прыкладання алгебраічнай геаметрыі да тэорыі кадавання пачаліся ў 80-х з працы Гоппе (гл. Тэорыя кадавання і алгебраічнай геаметрыі: Interplay ў гэтай серыі), з крывымі над канчатковымі палямі аказваюцца крыніцай добрых кодаў. У дэкадаваньня гэтых кодаў, паступова стала ясна, што падыход трэба было больш у плане (мнагамерны) паліномны ідэалаў, чым у тэрмінах вектарных прастораў, звязаных з дзельнікаў з алгебраічнай геаметрыі падыход. Сапраўды, галоўная праблема знаходжання памылкі пазіцыі, было пытанне аб знаходжанні розных пунктаў, звязаных з ідэальным прыватнасці, з ідэальным вырабляецца шляхам знаходжання мінімальнага базісу Гребнера адносна прыватнасці TDEG (поўнай ступені) тыпу упарадкавання. Гэта апошнія і захапляльныя даследаванні, з відавочным прымяненнем.

Праблема

Агульная задача дэкадаваньня для любога кода, гэта ўзяць атрымаў слова (гэта значыць, пашкоджаных кодавае слова) і прадукты (эфектыўна) бліжэйшага кодавага слова, каб яго (або, што эквівалентна Найменшая памылка магчыма). Для лінейных кодаў (подпространств), то гэта звычайна робіцца з дапамогай функцыі атрымаў слова, якое залежыць толькі ад памылкі, а не на канкрэтнае слова код перадаецца. Такія функцыі называюцца сіндромамі.

Для кодаў Рыда-Саламона над , У цяперашні час выкарыстоўваюцца ў розных прыкладаннях, такіх як CD-тэхналогіі, сіндромы

з дадзенай атрымаў слова, і primitve элемент .

Адзін затым выкарыстоўвае Берлекэмпа-Месі (або пашыранага алгарытму Эўкліда), каб вырабіць памылка-лакатар паліном (Або памылкі ацэншчыка паліном).

Тады мае выбар вырабляць усе , (На прагляд як рэкурэнтнага суадносіны і гэтага сіндрому ў якасці пачатковых умоў) і выкарыстоўваючы адваротнае пераўтварэнне,

з (Хутчэй за ўсё) памылкі або факторынг , Вырабляючы , І выкарыстоўваючы формулу Форни's:

Алгебра-геаметрычных кодаў

Алгебра-геаметрычныя коды (дваістыя, апісаныя ў `` тэорыі кадавання і алгебраічнай геаметрыі:''Interplay) з'яўляюцца абагульненнямі кодаў Рыда-Саламона вышэй. Такім чынам, павінна быць эфектыўная схема дэкадаваньня, якая па ўзоры алгарытм вышэй. Першы важны алгарытм ў гэтым працэсе стала абагульненне алгарытму Берлекэмпа-Месі на вышэйшыя памернасці, апублікаваная ў канцы 80-х Саката. Гэта прывяло да досыць эфектыўным вектар-касмічныя метады, кожны з якіх некаторыя недахопы, альбо ў лік памылак, лік кропак, або эфектыўнасць. Наступная важная ідэя была апублікаваная ў 93 Фэн і Рао. Гэтая схема большасцю галасоў дазволенае для вытворчасці больш `` синдромы''в той час як шэраг зніжэння сіндрому матрыцы. Толькі нядаўна гэта былі сінтэзаваны ў абагульненні вышэй алгарытму.

Сіндромы

для прасторы аснове вектара праверачнай функцыі /.

Версія Алгарытм Саката з эфектыўным галасавання большасць можа быць выкарыстаны для стварэння ідэальнай У аснову-лакатар ідэал памылкі, разнавіднасць якіх ёсць у дакладнасці мноства памылкі пазіцый. На самай справе мінімальны базіс Гребнера па адносінах да пэўнага тыпу TDEG упарадкавання на пераменных.

Як і раней Ёсць два спосабу, каб зыходзіць з гэтай кропкі.

Па-першае, выкарыстоўваць гэтыя базісныя элементы рэкурэнтнага суадносін, каб вырабляць ўсе сіндромы . Тады можна выкарыстоўваць абагульненыя зваротныя пераўтварэнні, каб вырабляць як памылка пазіцыі і памылкі велічынь.

Па-другое, змена комплексу (чыста лексікаграфічным) тыпу мінімальны базіс Гребнера, з якога параўнальна лёгка счытваць розныя памылкі пазіцыі шляхам знаходжання каранёў паліномаў адной зменнай. Тады можна выкарыстоўваць агульныя функцыі Форни , (Гэта значыць функцыі, якія роўныя нулю на ўсіх пазіцыях, акрамя памылкі P), атрымліваецца як пабочны прадукт аснове змены, каб зрабіць памылкі

як і раней.

Далейшых даследаванняў

Ёсць яшчэ шмат нявырашаных пытанняў у гэтай галіне. Тыя, магчыма справу з базісаў Гребнера б паказаць, што складанасць змены аснове падыходу, як добра ці лепш, чым адваротнае пераўтварэнне падыход, і што ён можа быць ужыты ў крывых, не абавязкова ў асаблівае становішча (як у цяперашні час патрабуецца Фэн -Рао большасцю галасоў). Гэта можа быць таксама, што, прагледзеўшы дэкадаваньня з пункту гледжання ідэалаў і базіс Гребнера, будзе ясна, якія коды будуць працаваць лепш, адносна якіх мноства кропак і прызначаны адлегласці. І гэта можа даць яшчэ больш зваротнай ў дэкадаваньня кодаў БЧХ за МСБ звязана таксама. Там нават можа быць эфектыўным спосабам для атрымання аптымальных функцый Форни.

Для атрымання дадатковай інфармацыі

Большасць літаратуры ў гэтай галіне з'яўляецца ў IEEE Transactions па тэорыі інфармацыі. Гісторыя дэкадаваньня даследаванні ў гэтай галіне пакрыта даволі прыгожа ў ўвядзенне агляднай артыкуле Хо holdt і Pellikaan, які таксама мае шырокую бібліяграфію. Добры сінтэз з згадваннем ідэалы могуць быць знойдзеныя ў IEEE паперы святымі і Heegard, хоць агульны алгарытм вышэй ад працы аўтара будуць апублікаваны ў часопісе IEEE сказаў.

1. Т. Хо holdt і Р. Pellikaan `` Аб дэкадаваньня алгебры-геаметрычныя коды''
2. Д. Леанард `` абагульненая формула Форни для кодаў А. Г.''
3. К. Святыя і С. Heegard `` алгебры-геаметрычныя коды і шматмерных цыклічных кодаў: адзіная тэорыя і алгарытмы дэкадаваньня з выкарыстаннем базісаў Гребнера''<

   Чц Верасень 28 9:58:04 CDT 1995