Puncte:2

Codurile ciclice ca idealuri ale unui inel coeficient

drapel jp

Găsesc algebra din spatele codurilor ciclice oarecum complicată. Punctul de plecare este destul de ușor: $C\subseteq \mathbb F_q^n$ este ciclic dacă orice deplasare ciclică a unui cuvânt de cod $c\in \mathbb F_q^n$ este încă în $C$. Apoi m-am lovit cu asta: codurile ciclice corespund idealurilor de $$\mathbb F_q[x]/(x^n-1). $$ Acum, am niște experiențe în algebră abstractă, mai ales din teoria grupurilor. Pot recunoaște un inel și un coeficient, dar am probleme să văd echivalența. Poate cineva să mi-l explice în foarte simplu termeni?

drapel bd
Înmulțirea cu $x$ în acest inel de coeficient înseamnă deplasarea ciclică a cuvântului de cod. Vezi comentariul meu sub răspunsul lui kodlu pentru mai multe detalii.
Puncte:2
drapel sa

Proprietatea ideală oferă o echivalență de polinoame la diviziunea modulo $(x^n-1).$ $$p(x) \equiv q(x) \text{ iff } p(x) - q(x) = 0 \pmod{(x^n-1)}$$

Gândindu-mă la înmulțirea prin $x$ ca operator de schimb, $$c(x)=c_0+c_1 x+\cdots+ c_{n-1} x^{n-1}$$ asta spune ca dupa $n$ deplasările ciclice obțineți același polinom înapoi. Aici $c(x)$ reprezintă cuvântul de cod $$(c_0,c_1,\ldots,c_{n-1})$$

Editați | ×: Mulțumesc pentru comentariul util, @JyrkiLahtonen:

Rețineți că $$ x c(x)=c_{n-1}+c_0 x+ c_1 x^2+\cdots+c_{n-2} x^{n-1} +c_{n-1}(x^n-1)\ echiv $$ $$ \equiv c_{n-1}+c_0 x+ c_1 x^2+\cdots+c_{n-2} x^{n-1} \pmod{x^n-1} $$ explicând de ce înmulțirea cu $x$ în inelul coeficientului $\mathbb{F}_q[x]/(x^nâ1)$ corespunde exact deplasării ciclice $$ (c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}). $$

drapel bd
Aș face acest lucru poate un pic mai concret adăugând observația că $$xc(x)=c_{n-1}+c_0x+c_1x^2+\cdots+c_{n-2}x^{n-1}+c_{n-1}(x^n-1) \equiv c_{n-1}+c_0x+c_1x^2+\cdots+c_{n-2}x^{n-1}\pmod {x^n-1}.$$ Aceasta explică de ce înmulțirea cu $x$ tocmai în inelul coeficient $\Bbb{F}_q[x]/(x^n-1)$ corespunde deplasării ciclice $$(c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}).$$
Puncte:1
drapel gb

Amintiți-vă că un ideal al unui inel este un set de elemente din inel, astfel încât (aceasta nu este o listă completă de proprietăți, doar cele importante pentru răspunsul meu):

  1. Putem adăuga oricare două elemente din ideal împreună și să obținem înapoi un element din ideal (închis sub adăugare).
  2. Putem înmulți orice element al idealului cu orice element al inelului și să recuperăm un element din ideal.

Acum amintiți-vă că un cod ciclic este, de asemenea, un cod liniar, cu proprietatea suplimentară că o schimbare ciclică oferă încă un cuvânt de cod (după cum menționați în întrebare).

Celălalt răspuns a explicat importanța modulului $(x^n-1)$ în inel pentru a realiza partea ciclică.Acum, faptul că un cod valid este un ideal în acest inel de coeficient corespunde că acesta este un cod liniar - adăugarea a două cuvinte de cod împreună dă un alt cuvânt de cod valid. De asemenea, merită remarcat faptul că acesta este un inel ideal principal, ceea ce înseamnă că fiecare ideal poate fi generat de un singur element. Acest element este exact polinomul generator $g$ a codului. Proprietatea #2 de mai sus înseamnă că fiecare multiplu al generatorului $g$ printr-un alt polinom (mod $(x^n-1)$) încă oferă un cuvânt de cod valid.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.