Циклический код

Тип блочного кода

В теории кодирования циклический код — это блочный код , где циклические сдвиги каждого кодового слова дают другое слово, принадлежащее коду. Это коды с исправлением ошибок , которые обладают алгебраическими свойствами, удобными для эффективного обнаружения и исправления ошибок .

Если 00010111 является допустимым кодовым словом, применение правого циклического сдвига дает строку 10001011. Если код циклический, то 10001011 снова является допустимым кодовым словом. В общем случае применение правого циклического сдвига перемещает младший значащий бит (LSB) в крайнее левое положение, так что он становится старшим значащим битом (MSB); другие позиции сдвигаются на 1 вправо.

Определение

Пусть — линейный код над конечным полем (также называемым полем Галуа ) длины блока . называется циклическим кодом , если для каждого кодового слова из слово в , полученное циклическим правым сдвигом компонентов, снова является кодовым словом. Поскольку один циклический правый сдвиг равен циклическим левым сдвигам, циклический код также может быть определен с помощью циклических левых сдвигов. Следовательно, линейный код является циклическим в точности тогда, когда он инвариантен относительно всех циклических сдвигов. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle c=(c_{1},\ldots ,c_{n})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle (c_{n},c_{1},\ldots ,c_{n-1})}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle n-1}$ ${\displaystyle {\mathcal {C}}}$

Циклические коды имеют некоторые дополнительные структурные ограничения на коды. Они основаны на полях Галуа и из-за своих структурных свойств они очень полезны для контроля ошибок. Их структура тесно связана с полями Галуа, из-за чего алгоритмы кодирования и декодирования для циклических кодов являются вычислительно эффективными.

Алгебраическая структура

Циклические коды могут быть связаны с идеалами в некоторых кольцах. Пусть будет кольцом полиномов над конечным полем . Определим элементы циклического кода с полиномами в таким образом, что отображается в полином : таким образом, умножение на соответствует циклическому сдвигу. Тогда является идеалом в , и, следовательно, главным , так как является кольцом главных идеалов . Идеал порождается единственным моническим элементом в минимальной степени, порождающим полиномом . ^[1] Это должно быть делителем . Отсюда следует, что каждый циклический код является полиномиальным кодом . Если порождающий полином имеет степень, то ранг кода равен . ${\displaystyle R=A[x]/(x^{n}-1)}$ ${\displaystyle A=GF(q)}$ ${\displaystyle C}$ ${\displaystyle R}$ ${\displaystyle (c_{0},\ldots ,c_{n-1})}$ ${\displaystyle c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}}$ ${\displaystyle x}$ ${\displaystyle C}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle C}$ ${\displaystyle g}$ ${\displaystyle x^{n}-1}$ ${\displaystyle g}$ ${\displaystyle d}$ ${\displaystyle C}$ ${\displaystyle n-d}$

Идемпотент — это кодовое слово, такое что (то есть является идемпотентным элементом ) и является тождеством для кода, то есть для каждого кодового слова . Если и взаимно просты, такое слово всегда существует и является уникальным; ^[2] оно является генератором кода. ${\displaystyle C}$ ${\displaystyle e}$ ${\displaystyle e^{2}=e}$ ${\displaystyle e}$ ${\displaystyle C}$ ${\displaystyle e}$ ${\displaystyle e\cdot c=c}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle q}$

Неприводимый код — циклический код, в котором код, как идеал, неприводим, т.е. минимален в , так что его проверочный многочлен является неприводимым многочленом . ${\displaystyle R}$

Примеры

Например, если и , то набор кодовых слов, содержащихся в циклическом коде, сгенерированном с помощью, в точности равен ${\displaystyle A=\mathbb {F} _{2}}$ ${\displaystyle n=3}$ ${\displaystyle (1,1,0)}$

${\displaystyle ((0,0,0),(1,1,0),(0,1,1),(1,0,1))}$.

Он соответствует идеалу, созданному . ${\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}$ ${\displaystyle (1+x)}$

Полином неприводим в кольце полиномов, и, следовательно, код является неприводимым кодом. ${\displaystyle (1+x)}$

Идемпотентом этого кода является многочлен , соответствующий кодовому слову . ${\displaystyle x+x^{2}}$ ${\displaystyle (0,1,1)}$

Тривиальные примеры

Тривиальными примерами циклических кодов являются сам код и код, содержащий только нулевое кодовое слово. Они соответствуют генераторам и соответственно: эти два полинома всегда должны быть множителями . ${\displaystyle A^{n}}$ ${\displaystyle 1}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1}$

Над кодом бита четности , состоящим из всех слов четного веса, соответствует генератор . Опять же над этим всегда должен быть фактор . ${\displaystyle GF(2)}$ ${\displaystyle x+1}$ ${\displaystyle GF(2)}$ ${\displaystyle x^{n}-1}$

Квазициклические коды и укороченные коды

Прежде чем углубляться в детали циклических кодов, обсудим квазициклические и укороченные коды, которые тесно связаны с циклическими кодами, и все они могут быть преобразованы друг в друга.

Определение

Квазициклические коды: ^{[ необходима ссылка ]}

Квазициклический код — это линейный блочный код, такой что для некоторого , взаимно простого с , многочлен является многочленом кодового слова всякий раз, когда является многочленом кодового слова. ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle x^{b}c(x){\pmod {x^{n}-1}}}$ ${\displaystyle c(x)}$

Здесь, кодовый многочлен — это элемент линейного кода, кодовые слова которого являются многочленами, делящимися на многочлен меньшей длины, называемый порождающим многочленом . Каждый кодовый многочлен может быть выражен в виде , где — порождающий многочлен. Любое кодовое слово циклического кода может быть связано с кодовым многочленом, а именно, . Квазициклический код с равным является циклическим кодом. ${\displaystyle c(x)=a(x)g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle (c_{0},..,c_{n-1})}$ ${\displaystyle C}$ ${\displaystyle \sum _{i=0}^{n-1}c_{i}*x^{i}}$ ${\displaystyle b}$ ${\displaystyle 1}$

Определение

Сокращенные коды:

Линейный код называется правильным укороченным циклическим кодом, если его можно получить путем удаления позиций из циклического кода. ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle (n+b,k+b)}$

В укороченных кодах информационные символы удаляются для получения желаемой длины блока, меньшей, чем проектная длина блока. Отсутствующие информационные символы обычно воображаются в начале кодового слова и считаются равными 0. Поэтому − фиксируется, а затем уменьшается, что в конечном итоге уменьшается . Нет необходимости удалять начальные символы. В зависимости от приложения иногда последовательные позиции считаются равными 0 и удаляются. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$

Все символы, которые были отброшены, не нужно передавать, и на приемном конце они могут быть вставлены повторно. Чтобы преобразовать циклический код в укороченный код, установите символы на ноль и отбросьте их из каждого кодового слова. Любой циклический код может быть преобразован в квазициклические коды путем отбрасывания каждого th символа, где является множителем . Если отброшенные символы не являются контрольными символами, то этот циклический код также является укороченным кодом. ${\displaystyle (n,k)}$ ${\displaystyle (n-b,k-b)}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle n}$

Для исправления ошибок

Циклические коды могут использоваться для исправления ошибок , как коды Хэмминга , поскольку циклические коды могут использоваться для исправления одиночных ошибок. Аналогично, они также используются для исправления двойных ошибок и пакетных ошибок. Все типы исправлений ошибок кратко рассматриваются в последующих подразделах.

Код Хэмминга (7,4) имеет порождающий полином . Этот полином имеет ноль в поле расширения Галуа в примитивном элементе , и все кодовые слова удовлетворяют . Циклические коды также могут использоваться для исправления двойных ошибок в поле . Длина блока будет равна и примитивным элементам и как нули в , поскольку мы рассматриваем здесь случай двух ошибок, поэтому каждый будет представлять одну ошибку. ${\displaystyle g(x)=x^{3}+x+1}$ ${\displaystyle GF(8)}$ ${\displaystyle \alpha }$ ${\displaystyle {\mathcal {C}}(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle GF(2^{m})}$

Полученное слово представляет собой многочлен степени, заданной как ${\displaystyle n-1}$ ${\displaystyle v(x)=a(x)g(x)+e(x)}$

где может иметь максимум два ненулевых коэффициента, соответствующих 2 ошибкам. ${\displaystyle e(x)}$

Мы определяем синдромный полином как остаток полинома при делении на порождающий полином , т.е. ${\displaystyle S(x)}$ ${\displaystyle v(x)}$ ${\displaystyle g(x)}$

${\displaystyle S(x)\equiv v(x)\equiv (a(x)g(x)+e(x))\equiv e(x)\mod g(x)}$как . ${\displaystyle (a(x)g(x))\equiv 0\mod g(x)}$

За исправление двух ошибок

Пусть элементы поля и будут двумя номерами местоположений ошибок. Если произошла только одна ошибка, то равно нулю, а если не произошло ни одной, то оба равны нулю. ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{2}}$

Пусть и . ${\displaystyle S_{1}={v}(\alpha )}$ ${\displaystyle S_{3}={v}(\alpha ^{3})}$

Эти элементы поля называются «синдромами». Теперь, поскольку равен нулю в примитивных элементах и ​​, мы можем записать и . Если, скажем, происходят две ошибки, то ${\displaystyle g(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle S_{1}=e(\alpha )}$ ${\displaystyle S_{3}=e(\alpha ^{3})}$

${\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}$и . ${\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}$

И эти два уравнения можно рассматривать как две пары уравнений с двумя неизвестными, и, следовательно, мы можем записать ${\displaystyle GF(2^{m})}$

${\displaystyle S_{1}=X_{1}+X_{2}}$и . ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$

Следовательно, если две пары нелинейных уравнений могут быть решены, циклические коды могут быть использованы для исправления двух ошибок.

Код Хэмминга

Код Хэмминга (7,4) может быть записан как циклический код над GF (2) с генератором . Фактически, любой двоичный код Хэмминга вида Ham (r, 2) эквивалентен циклическому коду, ^[3] и любой код Хэмминга вида Ham (r, q) с r и q-1 взаимно простыми также эквивалентен циклическому коду. ^[4] Учитывая код Хэмминга вида Ham (r, 2) с , набор четных кодовых слов образует циклический -код. ^[5] ${\displaystyle 1+x+x^{3}}$ ${\displaystyle r\geq 3}$ ${\displaystyle [2^{r}-1,2^{r}-r-2,4]}$

Код Хэмминга для исправления одиночных ошибок

Код, минимальное расстояние которого не менее 3, имеет проверочную матрицу, все столбцы которой различны и не равны нулю. Если проверочная матрица для двоичного кода имеет строки, то каждый столбец является -битным двоичным числом. Возможны столбцы. Следовательно, если проверочная матрица двоичного кода с не менее чем 3 имеет строки, то она может иметь только столбцы, не более того. Это определяет код, называемый кодом Хэмминга. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle d_{min}}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle (2^{m}-1,2^{m}-1-m)}$

Легко определить коды Хэмминга для больших алфавитов размера . Нам нужно определить одну матрицу с линейно независимыми столбцами. Для любого слова размера будут столбцы, которые кратны друг другу. Таким образом, для получения линейной независимости все ненулевые -кортежи с единицей в качестве самого верхнего ненулевого элемента будут выбраны в качестве столбцов. Тогда два столбца никогда не будут линейно зависимыми, потому что три столбца могут быть линейно зависимыми с минимальным расстоянием кода, равным 3. ${\displaystyle q}$ ${\displaystyle H}$ ${\displaystyle q}$ ${\displaystyle m}$

Итак, есть ненулевые столбцы с одним в качестве самого верхнего ненулевого элемента. Следовательно, код Хэмминга — это код. ${\displaystyle (q^{m}-1)/(q-1)}$ ${\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}$

Теперь для циклических кодов пусть будет примитивным элементом в , и пусть . Тогда и, таким образом , является нулем многочлена и является порождающим многочленом для циклического кода длины блока . ${\displaystyle \alpha }$ ${\displaystyle GF(q^{m})}$ ${\displaystyle \beta =\alpha ^{q-1}}$ ${\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}$ ${\displaystyle \beta }$ ${\displaystyle x^{(q^{m}-1)/(q-1)}-1}$ ${\displaystyle n=(q^{m}-1)/(q-1)}$

Но для , . И полученное слово является многочленом степени, заданной как ${\displaystyle q=2}$ ${\displaystyle \alpha =\beta }$ ${\displaystyle n-1}$

${\displaystyle v(x)=a(x)g(x)+e(x)}$

где или где представляет собой места ошибок. ${\displaystyle e(x)=0}$ ${\displaystyle x^{i}}$ ${\displaystyle i}$

Но мы также можем использовать как элемент для индекса местоположения ошибки. Поскольку , у нас есть и все степени от до различны. Поэтому мы можем легко определить местоположение ошибки из , если только , что не представляет никакой ошибки. Таким образом, код Хэмминга — это один код исправления ошибок с и . ${\displaystyle \alpha ^{i}}$ ${\displaystyle GF(2^{m})}$ ${\displaystyle g(\alpha )=0}$ ${\displaystyle v(\alpha )=\alpha ^{i}}$ ${\displaystyle \alpha }$ ${\displaystyle 0}$ ${\displaystyle 2^{m}-2}$ ${\displaystyle i}$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle v(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n=2^{m}-1}$ ${\displaystyle k=n-m}$

Для исправления пакетных ошибок

Из концепции расстояния Хэмминга , код с минимальным расстоянием может исправить любые ошибки. Но во многих каналах шаблон ошибки не очень произволен, он возникает в пределах очень короткого сегмента сообщения. Такой тип ошибок называется пакетными ошибками . Таким образом, для исправления таких ошибок мы получим более эффективный код с более высокой скоростью из-за меньших ограничений. Циклические коды используются для исправления пакетных ошибок. Фактически, циклические коды могут также исправлять циклические пакетные ошибки вместе с пакетными ошибками. Циклические пакетные ошибки определяются как ${\displaystyle 2t+1}$ ${\displaystyle t}$

Циклический пакет длины — это вектор, ненулевые компоненты которого находятся среди (циклически) последовательных компонентов, первый и последний из которых ненулевые. ${\displaystyle t}$ ${\displaystyle t}$

В полиномиальной форме циклический всплеск длины можно описать как с как полином степени с ненулевым коэффициентом . Здесь определяет шаблон и определяет начальную точку ошибки. Длина шаблона задается как deg . Синдромный полином уникален для каждого шаблона и задается как ${\displaystyle t}$ ${\displaystyle e(x)=x^{i}b(x)\mod (x^{n}-1)}$ ${\displaystyle b(x)}$ ${\displaystyle t-1}$ ${\displaystyle b_{0}}$ ${\displaystyle b(x)}$ ${\displaystyle x^{i}}$ ${\displaystyle b(x)+1}$

${\displaystyle s(x)=e(x)\mod g(x)}$

Линейный блочный код, исправляющий все пакетные ошибки длины или меньше, должен иметь по крайней мере контрольные символы. Доказательство: Поскольку любой линейный код, который может исправить пакетный шаблон длины или меньше, не может иметь пакет длины или меньше в качестве кодового слова, потому что если бы он это сделал, то пакет длины мог бы изменить кодовое слово на пакетный шаблон длины , что также можно было бы получить, сделав пакетную ошибку длины во всех нулевых кодовых словах. Теперь любые два вектора, которые не равны нулю в первых компонентах, должны быть из разных смежных множеств массива, чтобы их разность не была кодовым словом пакетов длины . Следовательно, количество таких смежных множеств равно количеству таких векторов, которые являются . Следовательно, по крайней мере смежных множеств и, следовательно, по крайней мере контрольного символа. ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle 2t}$ ${\displaystyle q^{2t}}$ ${\displaystyle q^{2t}}$ ${\displaystyle 2t}$

Это свойство также известно как граница Ригера и оно похоже на границу Синглтона для исправления случайных ошибок.

Пожарные коды как циклические границы

В 1959 году Филипп Файр ^[6] представил конструкцию циклических кодов, сгенерированных произведением бинома и примитивного полинома. Бином имеет вид для некоторого положительного нечетного целого числа . ^[7] Код Файра — это циклический пакетный код исправления ошибок с порождающим полиномом ${\displaystyle x^{c}+1}$ ${\displaystyle c}$ ${\displaystyle GF(q)}$

${\displaystyle g(x)=(x^{2t-1}-1)p(x)}$

где — простой многочлен степени не меньше и не делится на . Длина блока кода огня — это наименьшее целое число, такое что делится на . ${\displaystyle p(x)}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle p(x)}$ ${\displaystyle x^{2t-1}-1}$ ${\displaystyle n}$ ${\displaystyle g(x)}$ ${\displaystyle x^{n}-1}$

Код пожара может исправить все пакетные ошибки длины t или меньше, если нет двух пакетов и в одном и том же смежном множестве. Это можно доказать от противного. Предположим, что есть два различных ненулевых пакета и длины или меньше и они находятся в одном и том же смежном множестве кода. Таким образом, их разность является кодовым словом. Поскольку разность кратна , она также кратна . Следовательно, ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle t}$ ${\displaystyle g(x)}$ ${\displaystyle x^{2t-1}-1}$

${\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}$.

Это показывает, что является кратным , поэтому ${\displaystyle j}$ ${\displaystyle 2t-1}$

${\displaystyle b(x)=x^{l(2t-1)}b'(x)}$

для некоторых . Теперь, как меньше чем и меньше чем так и кодовое слово. Поэтому, ${\displaystyle l}$ ${\displaystyle l(2t-1)}$ ${\displaystyle t}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle (x^{l(2t-1)}-1)b(x)}$

${\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}$.

Так как степень меньше степени , не может делить . Если не равно нулю, то также не может делить, так как меньше и по определению делит на не меньшее . Следовательно , и равно нулю. Это означает, что оба всплеска одинаковы, вопреки предположению. ${\displaystyle b(x)}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle b(x)}$ ${\displaystyle l}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle l}$ ${\displaystyle j}$

Коды пожарной безопасности являются лучшими кодами коррекции одиночных пакетов с высокой скоростью, и они построены аналитически. Они имеют очень высокую скорость, и когда и равны, избыточность минимальна и равна . Используя несколько кодов пожарной безопасности, можно также исправить ошибки с более длинными пакетами. ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle 3t-1}$

Для обнаружения ошибок широко используются циклические коды, называемые циклическими избыточными кодами . ${\displaystyle t-1}$

О преобразовании Фурье

Применение преобразования Фурье широко распространено в обработке сигналов. Но их применение не ограничивается только комплексными полями; преобразования Фурье существуют также в поле Галуа . Циклические коды, использующие преобразование Фурье, можно описать в обстановке, более близкой к обработке сигналов. ${\displaystyle GF(q)}$

Преобразование Фурье над конечными полями

Преобразование Фурье над конечными полями

Дискретное преобразование Фурье вектора задается вектором , где, ${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ ${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$

${\displaystyle V_{k}}$= где, ${\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}$

${\displaystyle k=0,.....,n-1}$

где exp( ) - корень th из единицы. Аналогично в конечном поле корень th из единицы является элементом порядка . Поэтому ${\displaystyle -j2\pi /n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$

Если — вектор над , и — элемент порядка , то преобразование Фурье вектора — это вектор , а компоненты задаются выражением ${\displaystyle v=(v_{0},v_{1},....,v_{n-1})}$ ${\displaystyle GF(q)}$ ${\displaystyle \omega }$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}$

${\displaystyle V_{j}}$= где, ${\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}$

${\displaystyle k=0,.....,n-1}$

Здесь — временной индекс, — частота , — спектр . Одно важное различие между преобразованием Фурье в комплексном поле и полем Галуа заключается в том, что комплексное поле существует для каждого значения , тогда как в поле Галуа существует только в том случае, если делит . В случае полей расширения будет преобразование Фурье в поле расширения, если делит для некоторого . В поле Галуа вектор временной области находится над полем , но спектр может находиться над полем расширения . ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle V}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle q-1}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle v}$ ${\displaystyle GF(q)}$ ${\displaystyle V}$ ${\displaystyle GF(q^{m})}$

Спектральное описание

Любое кодовое слово циклического кода длины блока может быть представлено полиномом степени не выше . Его кодер может быть записан как . Следовательно, в частотной области кодер может быть записан как . Здесь спектр кодового слова имеет значение в , но все компоненты во временной области находятся из . Поскольку спектр данных произволен, роль заключается в указании тех, где будет равен нулю. ${\displaystyle n}$ ${\displaystyle c(x)}$ ${\displaystyle n-1}$ ${\displaystyle c(x)=a(x)g(x)}$ ${\displaystyle C_{j}=A_{j}G_{j}}$ ${\displaystyle C_{j}}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$ ${\displaystyle A_{j}}$ ${\displaystyle G_{j}}$ ${\displaystyle j}$ ${\displaystyle C_{j}}$

Таким образом, циклические коды можно также определить как

При наличии набора спектральных индексов, , элементы которого называются контрольными частотами, циклический код представляет собой набор слов, спектр которых равен нулю в компонентах, индексированных . Любой такой спектр будет иметь компоненты вида . ${\displaystyle A=(j_{1},....,j_{n-k})}$ ${\displaystyle C}$ ${\displaystyle GF(q)}$ ${\displaystyle j_{1},...,j_{n-k}}$ ${\displaystyle C}$ ${\displaystyle A_{j}G_{j}}$

Итак, циклические коды являются векторами в поле , а спектр, заданный его обратным преобразованием Фурье, находится над полем и ограничен нулевым значением в определенных компонентах. Но каждый спектр в поле и нулевой в определенных компонентах может не иметь обратных преобразований с компонентами в поле . Такой спектр не может использоваться в качестве циклических кодов. ${\displaystyle GF(q)}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$

Ниже приведены некоторые границы спектра циклических кодов.

BCH связан

Если быть фактором для некоторого . Единственный вектор в весом или меньше, у которого последовательные компоненты его спектра равны нулю, является вектором, состоящим из всех нулей. ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle d-1}$

Связанный Хартманн-Ценг

Если быть множителем для некоторого , и целое число, которое является взаимно простым с . Единственный вектор в веса или меньше, спектральные компоненты которого равны нулю для , где и , является полностью нулевым вектором. ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=\ell _{1}+\ell _{2}b(\mod n)}$ ${\displaystyle \ell _{1}=0,....,d-s-1}$ ${\displaystyle \ell _{2}=0,....,s-1}$

Рус связан

Если быть множителем для некоторых и . Единственный вектор в веса или меньше, спектральные компоненты которого равны нулю для , где и принимает по крайней мере значения в диапазоне , является вектором, состоящим из всех нулей. ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle GCD(n,b)=1}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=l_{1}+l_{2}b(\mod n)}$ ${\displaystyle l_{1}=0,...,d-s-2}$ ${\displaystyle l_{2}}$ ${\displaystyle s+1}$ ${\displaystyle 0,....,d-2}$

Коды квадратичных остатков

Если простое число является квадратичным вычетом по модулю простого числа, то существует код квадратичного вычета , который является циклическим кодом длины , размерности и минимального веса не менее . ${\displaystyle l}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle (p+1)/2}$ ${\displaystyle {\sqrt {p}}}$ ${\displaystyle GF(l)}$

Обобщения

Констациклический код — это линейный код со свойством, что для некоторой константы λ, если ( c ₁ ,c ₂ ,..., c _n ) является кодовым словом, то также является (λ c _n ,c ₁ ,..., c _{n -1} ). Негациклический код — это констациклический код с λ=-1. ^[8] Квазициклический код обладает свойством, что для некоторого s любой циклический сдвиг кодового слова на s позиций снова является кодовым словом. ^[9] Двойной циркулянтный код — это квазициклический код четной длины с s = 2. ^[9] Квазискрученные коды и мультискрученные коды являются дальнейшими обобщениями констациклических кодов. ^{[10] [11]}

Смотрите также

• БЧХ код
• Двоичный код Голея
• Циклическая проверка избыточности
• Юджин Прейндж
• Код Рида-Мюллера
• Троичный код Голея

Примечания

1. Ван Линт 1998, стр. 76
2. Ван Линт 1998, стр. 80
3. Хилл 1988, стр. 159–160.
4. Блахут 2003, Теорема 5.5.1
5. Хилл 1988, стр. 162–163.
6. P. Fire, E, P. (1959). Класс двоичных кодов с множественной коррекцией ошибок для ненезависимых ошибок. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
7. Вэй Чжоу, Шу Линь, Халед Абдель-Гаффар. Исправление пакетных или случайных ошибок на основе кодов Fire и BCH. ITA 2014: 1-5 2013.
8. Ван Линт 1998, стр. 75
9. MacWilliams & Sloane 1977, стр. 506
10. Айдын, Нух; Сиап, Ирфан; К. Рэй-Чаудхури, Дижен (2001). «Структура квазискрученных кодов с 1 генератором и новых линейных кодов». Designs, Codes and Cryptography . 24 (3): 313–326. doi :10.1023/A:1011283523000. S2CID  17376783.
11. Айдын, Нух; Халилович, Айдын (2017). «Обобщение квази-скрученных кодов: многоскрученные коды». Конечные поля и их приложения . 45 : 96–106. arXiv : 1701.01044 . doi : 10.1016/j.ffa.2016.12.002 . S2CID  7694655.

Ссылки

• Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press , ISBN 0-521-55374-1
• Хилл, Рэймонд (1988), Первый курс по теории кодирования , Oxford University Press , ISBN 0-19-853803-0
• MacWilliams, FJ ; Sloane, NJA (1977), Теория кодов, исправляющих ошибки , Нью-Йорк: North-Holland Publishing, ISBN 0-444-85011-2
• Ван Линт, Дж. Х. (1998), Введение в теорию кодирования , Graduate Texts in Mathematics 86 (3-е изд.), Springer Verlag , ISBN 3-540-64133-5

Дальнейшее чтение

• Ранджан Бозе , Теория информации, кодирование и криптография , ISBN 0-07-048297-7 
• Ирвинг С. Рид и Сюэминь Чен, Кодирование с контролем ошибок в сетях передачи данных , Бостон: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4 . 
• Скотт А. Ванстоун , Пол К. Ван Ооршот, Введение в коды исправления ошибок с приложениями , ISBN 0-7923-9017-2 

Внешние ссылки

• Заметки Джона Гилла (Стэнфорд) по занятиям – Заметки № 3, 8 октября, Раздаточный материал № 9. Архивировано 23 октября 2012 г. в Wayback Machine , EE 387.
• Заметки Джонатана Холла (MSU) по занятиям – Глава 8. Циклические коды - стр. 100 - 123
• Дэвид Терр. "Циклический код". MathWorld .

В данной статье использованы материалы из циклического кода PlanetMath , лицензированного по лицензии Creative Commons Attribution/Share-Alike License .