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

редактировать

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

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

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

Содержание

1 Определение
2 Алгебраическая структура
3 Примеры
- 3.1 Простые примеры
4 Квазициклические коды и сокращенные коды
- 4.1 Определение
- 4.2 Определение
5 Циклические коды для исправления ошибок
- 5.1 Для исправления двух ошибок
6 Код Хэмминга
- 6.1 Код Хэмминга для исправления одиночных ошибок
7 Циклические коды для исправления пакета ошибки
- 7.1 Коды Файра как циклические границы
8 Циклические коды на преобразовании Фурье
- 8.1 Преобразование Фурье по конечным полям
- 8.2 Спектральное описание циклических кодов
  - 8.2.1 Граница BCH
  - 8.2. 2 Граница Хартмана-Ценга
  - 8.2.3 Граница Рооса
- 8.3 Коды квадратичных остатков
9 Обобщения
10 См. Также
11 Примечания
12 Ссылки
13 Дополнительная литература
14 Внешние ссылки

Определение

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

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

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

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

идемпотент кода C - это кодовое слово e такое, что e = e ( то есть e является идемпотентным элементом в C), а e является идентификатором кода, то есть ec = c для каждого кодового слова c. Если n и q взаимно просты, такое слово всегда существует и уникально; это генератор кода.

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

Примеры

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

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

((0,0,0),(1,1,0),(0,1,1),(1,0,1))

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

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

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

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

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

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

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

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

Определение

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

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

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

Определение

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

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

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

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

Циклические коды для исправления ошибок

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

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

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

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

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

$S (Икс) ≡ v (Икс) ≡ (A (Икс) г (Икс) + е (Икс)) ≡ Е (Икс) по модулю g (x) {\ Displaystyle S (x) \ эквив v (х) \ Equiv (a (x) g (x) + e (x)) \ Equiv e (x) \ mod g (x)}$ $S(x)\equiv v(x)\equiv (a(x)g(x)+e(x))\equiv e(x)\mod g(x)$ as $(a (x) g (x)) ≡ 0 mod g (x) {\ displaystyle (a (x) g (x)) \ Equiv 0 \ mod g (x)}$ $(a(x)g(x))\equiv 0\mod g(x)$ .

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

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

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

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

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

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

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

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

Код Хэмминга

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коды Файра как циклические границы

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

$g (x) = (x 2 t - 1 - 1) п (Икс) {\ Displaystyle г (х) = (х ^ {2t-1} -1) р (х)}$ $g(x)=(x^{2t-1}-1)p(x)$

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

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

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

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

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

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

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

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

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

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

Циклические коды на преобразовании Фурье

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

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

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

$V k {\ displaystyle V_ {k}}$ $V_{k}$ = $Σ я = 0 n - 1 e - j 2 π n - 1 ikvi {\ displaystyle \ Sigma _ {i = 0} ^ {n-1} e ^ {- j2 \ pi n ^ { -1} ik} v_ {i}}$ $\Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}$ где,

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

где exp ( $- j 2 π / n {\ displaystyle -j2 \ pi / n}$ $-j2\pi /n$ ) является корнем $n {\ displaystyle n}$ $n$ -й степени из единицы. Точно так же в конечном поле $n {\ displaystyle n}$ $n$ -й корень из единицы является элементом $ω {\ displaystyle \ omega}$ $\omega$ порядка $n {\ displaystyle n}$ $n$ . Следовательно,

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

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

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

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

Спектральное описание циклических кодов

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

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

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

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

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

Граница BCH

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

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

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

Roos bound

Если $n {\ displaystyle n}$ $n$ быть множителем $qm - 1 {\ displaystyle q ^ {m} -1 }$ $q^{m}-1$ для некоторых $m {\ displaystyle m}$ $m$ и $GCD (n, b) = 1 {\ displaystyle GCD (n, b) = 1}$ $GCD(n,b)=1$ . Единственный вектор в $GF (q) n {\ displaystyle GF (q) ^ {n}}$ $GF(q)^{n}$ веса $d - 1 {\ displaystyle d-1}$ $d-1$ или менее, спектральные компоненты которого $V j {\ displaystyle V_ {j}}$ $V_{j}$ равны нулю для $j = l 1 + l 2 b (mod n) {\ displaystyle j = l_ {1} + l_ {2} b (\ mod n)}$ $j=l_{1}+l_{2}b(\mod n)$ , где $l 1 = 0,..., d − s − 2 {\displaystyle l_{1}=0,...,d-s-2}$ $l_{1}=0,...,d-s-2$ and $l 2 {\displaystyle l_{2}}$ $l_{2}$ takes at least $s + 1 {\displaystyle s+1}$ $s+1$ values in the range $0,...., d − 2 {\displaystyle 0,....,d-2}$ $0,....,d-2$ , is the all-zero vector.

Quadratic residue codes

When the prime $l {\displaystyle l}$ $l$ is a quadratic residue modulo the prime $p {\displaystyle p}$ $p$ there is a quadratic residue code which is a cyclic code of length $p {\displaystyle p}$ $p$ , dimension $( p + 1) / 2 {\displaystyle (p+1)/2}$ $(p+1)/2$ and minimum weight at least $p {\displaystyle {\sqrt {p}}}$ ${\sqrt {p}}$ over $G F ( l) {\displaystyle GF(l)}$ $GF(l)$ .

Generalizations

A constacyclic codeis a linear code with the property that for some constant λ if (c1,c2,...,cn) is a codeword then so is (λcn,c1,...,cn-1). A negacyclic codeis a constacyclic code with λ=-1. A quasi-cyclic codehas the property that for some s, any cyclic shift of a codeword by s places is again a codeword. A double circulant codeis a quasi-cyclic code of even length with s=2.