Рейтинг:2

Циклические коды как идеалы факторкольца

флаг jp

Я нахожу алгебру циклических кодов несколько сложной. Отправная точка достаточно проста: $C\subseteq\mathbb F_q^n$ является циклическим, если любой циклический сдвиг кодового слова $c\in\mathbb F_q^n$ все еще в $С$. Потом меня осенило: циклические коды соответствуют идеалам $$\mathbb F_q[x]/(x^n-1). $$ Теперь у меня есть некоторый опыт в абстрактной алгебре, в основном из теории групп. Я могу распознать кольцо и частное, но не вижу эквивалентности. Может ли кто-нибудь объяснить мне это в очень простой термины?

флаг bd
Умножение на $x$ в этом факторкольце представляет собой циклический сдвиг кодового слова. См. мой комментарий под ответом kodlu для более подробной информации.
Рейтинг:2
флаг sa

Идеальное свойство дает эквивалентность многочленов при делении по модулю $(х^n-1).$ $$p(x) \equiv q(x) \text{ тогда и только тогда, когда } p(x) - q(x) = 0 \pmod{(x^n-1)}$$

Думая об умножении на $х$ как оператор сдвига, $$c(x)=c_0+c_1 x+\cdots+ c_{n-1} x^{n-1}$$ это говорит о том, что после $n$ циклические сдвиги, вы получаете тот же полином обратно. Здесь $с(х)$ представляет кодовое слово $$(c_0,c_1,\ldots,c_{n-1})$$

Редактировать: Спасибо за полезный комментарий, @JyrkiLahtonen:

Обратите внимание, что $$ х 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)\ эквивалент $$ $$ \equiv c_{n-1}+c_0 x+ c_1 x^2+\cdots+c_{n-2} x^{n-1} \pmod{x^n-1} $$ объяснить, почему умножение на $х$ в факторкольце $\mathbb{F}_q[x]/(x^nâ1)$ точно соответствует циклическому сдвигу $$ (c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}). $$

флаг bd
Я бы сделал это, возможно, немного более конкретным, добавив наблюдение, что $$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}.$$ Это объясняет, почему умножение на $x$ точно в факторкольце $\Bbb{F}_q[x]/(x^n-1)$ соответствует циклическому сдвигу $$(c_0,c_1,\ldots,c_{n-1})\mapsto (c_{n-1},c_0,c_1,\ldots,c_{n-2}).$$
Рейтинг:1
флаг gb

Напомним, что идеалом кольца называется набор элементов из кольца, таких, что (это не полный список свойств, а только важные для моего ответа):

  1. Мы можем сложить любые два элемента в идеале вместе и получить обратно элемент в идеале (замкнутый при сложении).
  2. Мы можем умножить любой элемент идеала на любой элемент кольца и получить обратно элемент идеала.

Теперь вспомните, что циклический код также является линейным кодом с дополнительным свойством, заключающимся в том, что циклический сдвиг по-прежнему дает кодовое слово (как вы упоминаете в вопросе).

Другой ответ объяснил важность модуля $(х^n-1)$ в ринге для достижения циклической части.Теперь тот факт, что действительный код является идеалом в этом фактор-кольце, соответствует тому, что он является линейным кодом - сложение двух кодовых слов вместе дает другое действительное кодовое слово. Также стоит отметить, что это кольцо главных идеалов, что означает, что каждый идеал может быть порожден одним элементом. Этот элемент в точности является генераторным полиномом $г$ кода. Свойство № 2 выше означает, что каждое кратное генератора $г$ другим полиномом (mod $(х^n-1)$) по-прежнему дает действительное кодовое слово.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.