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

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

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

Определение

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

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

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

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

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

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

Примеры

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

$((0,0,0),(1,1,0),(0,1,1),(1,0,1))$.

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

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

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

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

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

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

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

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

Определение

Квазициклические коды:

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

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

Определение

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

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

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

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

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

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

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

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

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

Определим синдромный полином , $S(x)$ как остаток полинома $v(x)$ при делении на полином генератора $g(x)$ т.е.

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

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

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

Позволять $S_{1}={v}(\alpha )$ и $S_{3}={v}(\alpha ^{3})$.

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

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

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

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

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

Код Хэмминга

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

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

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

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

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

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

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

$v(x)=a(x)g(x)+e(x)$

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

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

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

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

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

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

$s(x)=e(x)\mod g(x)$

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

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

Коды пожарной безопасности как циклические границы

См. Также: Код исправления пакетов § Коды пожарной безопасности.

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

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

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

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

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

Это показывает, что $j$ кратно $2t-1$, Так

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

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

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

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

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

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

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

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

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

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

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

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

$k=0,.....,n-1$

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

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

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

$k=0,.....,n-1$

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

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

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

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

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

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

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

BCH связан

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

Граница Хартмана-Ценга

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

Роос связан

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

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

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

Обобщения

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

См. также

• Код BCH
• Двоичный код Голея
• Проверка циклическим избыточностью
• Юджин Прейндж
• Код Рида – Мюллера
• Тернарный код Голея

Ссылки

• Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press , ISBN  0-521-55374-1
• Хилл, Рэймонд (1988), Первый курс теории кодирования , Oxford University Press , ISBN  0-19-853803-0
• МакВильямс, ФДж ; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Нью-Йорк: издательство North-Holland Publishing, ISBN  0-444-85011-2
• Ван Линт, Дж. Х. (1998), Введение в теорию кодирования , Тексты для аспирантов по математике 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.
• Конспекты занятий Джонатана Холла (МГУ) – Глава 8. Циклические коды – стр. 100–123.
• Дэвид Терр. «Циклический код» . Математический мир .

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