Циклический код синдром ошибки - Исправление ошибок и поиск оптимальных решений проблем

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

1. любая
из разрешенных кодовых комбинаций
циклического кода делится по модулю
два без остатка на некоторое, так
называемое «образующее двоичное число»,
определяющее помехоустойчивые свойства
кода, т.е. расстояние d;

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

Например:
01011 и 10110 – две разрешенные кодовые
комбинации некоторого циклического
кода с образующим числом 1011 (d=3).
Поэтому они делятся по модулю два без
остатка на образующее число:

01011
1011 10110 1011

0000
01
1011
10

1011
0000

1011

0000

000
000

При
этом d=4
>d=3.

Кроме
того циклический сдвиг на один разряд
влево элементов первой комбинации
порождают вторую комбинацию.

01011 => 10110

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

Структурная
схема СПДС, содержит кодер и декодер
циклического кода. Структура разрешенных
кодовых комбинаций циклического кода
состоит из двух частей. В начале комбинации
располагается n-проверочных
разрядов, структура которых определяется
кодерами циклического кода из условия
обеспечения делимости без остатка
формируемой разрешенной кодовой
комбинации на образующее число.

Идея
построения циклического кода (n,k)
сводится к тому, что информационную
часть кодовой комбинации G(x)
нужно преобразовать в комбинацию F(x),
которая без остатка делится на порождающий
полином Р(х) степени r=n-k.
Рассмотрим последовательность операций
построения циклического кода:

1.
Представляем информационную часть
кодовой комбинации в виде полинома
G(x).
Например информационная часть 110101.
Тогда
.

2.
Умножаем G(x)
на одночлен
( старшую степень порождающего полинома
Р(х) ) и получаем.

Пусть
у нас порождающий полином 1011,
тогда
.

3. Делим
на
порождающий полином Р(х), при этом
получаем остаток от деленияR(x).

Добавим
полученный остаток R
(x)
к комбинации
и
получим комбинацию,
которая будет передана в линию. Данная
комбинацияF(x)
делится без остатка на образующий
полином и представляет собой разрешенную
кодовую комбинацию циклического (n,k)
кода. На приеме производится деление
полученной кодовой комбинации на
образующий полином. Если ошибок нет, то
деление пройдет без остатка. Если при
делении получен остаток, то комбинация
принята с ошибками.

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

Построение
кодеров, декодеров.

Пример:

Кодер
строится на основе полинома P(x).

=> 1011
–
веса

При
построении устройства число ячеек
регистров сдвига берется по высшей
степени образующего полинома
=>
3 регистра сдвига; число регистров
задержки берется также по высшей степени
образующего полинома; число сумматоров
по модулю два берется по весовой части
образующего полинома минус единица =>
3-1=2m.

Состояния
регистров (1,2,3
– регистры; m
– сумматоры)

На
вход подается
110101000

Декодер
–
правила построения такие же, как у
кодера, но количество регистров задержки
определяется по высшей степени
информационной комбинации плюс 1 
5+1=6

Деление
на образующий полином происходит за 9
тактов. Пока идет деление на образующий
полином К2 разомкнут, а К1 замкнут в
течении 6 тактов пока идет запись
информационных импульсов. После 6 такта
К1 размыкается. После 10 такта К2 замыкается
и формируется сигнал:

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

2. Если во всех
ячейках регистров сдвига будут «0», то
формируется сигнал «0» и информация
будет выдана потребителю.

Состояния
регистров

Если хотя бы в одной
ячейке регистра будет «1», то значит
произошла ошибка.

Информация из
регистров сдвигов будет удаляться. Если
во всех ячейках регистров сдвига будут
«0», то формируется сигнал «0» и информация
будет выдана потребителю.

Выбор образующего
полинома.

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

Кроме
образующего полинома необходимо найти
и количество проверочных разрядов
r.

=1
если n=7,
то

tи.ош
– число ошибок, исправляемых циклическим
кодом.

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

Pr(x)

Двоичная
запись

111

1011

1101

В частности, если
r=3,
t_и.ош=1,
j=2*1-1=1,
образующий полином будет представлять
собой единственный минимальный многочлен
P(x)= x³+x+1
(первая строка, второй столбец таблицы
). Соответственно образующее число равно
1011.

Синдром циклического
кода.

Синдром циклического
кода определяется суммой по модулю 2
принятых проверочных элементов и
элементов проверочной группы,
сформированных из принятых элементов
информационной группы. В циклическом
коде для определения синдрома следует
разделить принятую кодовую комбинацию
на кодовую комбинацию порождающего
полинома. Если все элементы приняты без
ошибок, то остаток от деления R(х)
равен нулю. Если есть ошибки, то остаток
не будет равен нулю. Следовательно,
синдромом циклического кода является
многочлен R(x).
Обнаружение и исправление ошибок
производится только на основе анализа
синдрома. В зависимости от остатка
определяется элемент в котором произошла
ошибка. Для исправления ошибок необходимо
чтобы количество ненулевых остатков
равнялось количеству элементов n
( при исправлении одной ошибки ) или
числу комбинаций из n.

Соседние файлы в папке Будылдина2

#
11.04.20152.54 Mб24ДКР рисунок Mumarev.vsd
#
11.04.20152.49 Mб30ДКР рисунок.vsd
#
#
#
#

Источник

Вычисление
синдрома для циклических кодов является
довольно простой процедурой.

Пусть
U(x)
и r(х)
‑
полиномы, соответствующие переданному
кодовому слову и принятой последовательности.

Разделив
r(x)
на g(x),
получим

r(x)
= q(x)
g(x)
+ s(x),
(1.73)

где
— q(x)
— частное от деления, s(x)
— остаток от деления.

Если
r(x)
является кодовым полиномом, то он делится
на g(x)
без остатка, то есть s(x)
= 0.

Следовательно,
s(x)

0
является условием наличия ошибки в
принятой последовательности, то есть
синдромом принятой последовательности.

Синдром
s(x)
имеет в общем случае вид

S(x)
= S₀
+ S₁
x + … + S_n-

k-1
x^n-k-1
. (1.74)

Очевидно,
что схема вычисления синдрома является
схемой деления, подобной схемам
кодирования рис. 1.10 или 1.11 .

При
наличии в принятой последовательности
r

хотя бы одной ошибки вектор синдрома S
будет иметь, по крайней мере, один
нулевой элемент, при этом факт наличия
ошибки легко обнаружить, объединив по
ИЛИ
выходы всех ячеек регистра синдрома.

Покажем,
что синдромный многочлен S(x)
однозначно связан с многочленом ошибки
e(x),
а
значит, с его помощью можно не только
обнаруживать, но и локализовать ошибку
в принятой последовательности.

Пусть

e(x)
= e₀
+ e₁
x
+ e₂
x²
+ … + e_n_-1
xⁿ^-1
(1.75)

— полином
вектора ошибки.

Тогда
полином принятой последовательности

r(x)
= U(x)
+ e(x).
(1.76)

Прибавим
в этом выражении слева и справа U(x),
а также учтем, что

r(x)
= q(x)
g(x) + S(x), U(x) = m(x)
g(x), (1.77)

тогда

,
(1.78)

то
есть синдромный
полином S(x)
есть
остаток от
деления полинома ошибки e(x)
на порождающий полином g(x).

Отсюда следует, что по синдрому S(x)
можно однозначно определить вектор
ошибки e(x), а следовательно,
исправить эту ошибку.

На рис. 1.14 приведена схема синдромного
декодера с исправлением однократной
ошибки для циклического (7,4)-кода.
По своей структуре она подобна схеме,
приведенной на рис. 1.6, с той лишь разницей,
что вычисление синдрома принятой
последовательности производится здесь
не умножением на проверочную матрицу,
а делением на порождающий полином. При
этом она сохраняет и недостаток, присущий
всем синдромным декодерам: необходимость
иметь запоминающее устройство, ставящее
в соответствие множеству возможных
синдромов S множество векторов
ошибок e. Цикличность структуры
кода в этом случае не учитывается.

Рис.
1.14

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

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

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

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

Одним
из неалгебраических методов является
декодирование с использованием алгоритма
Меггитта,
пригодного для исправления как одиночных,
так и l-кратных
ошибок (на практике l

3).

При
декодировании в соответствии с алгоритмом
Меггитта также вычисляется синдром
принятой последовательности S(x),
однако используется он иначе, нежели в
рассмотренных ранее синдромных декодерах.

Идея,
лежащая в основе декодера Меггитта,
очень проста и основывается на следующих
свойствах циклических кодов:

—
существует взаимно-однозначное
соответствие между множеством всех
исправляемых ошибок и множеством
синдромов;

—
если S(x)
— синдромный многочлен, соответствующий
многочлену ошибок е(x),

то xS(x)
mod
g(x)
— синдромный многочлен, соответствующий
x
e(x) mod (xⁿ
+ 1).

Равенство
а(x)
= b(x) mod p(x)
читается как “а(x),
сравнимо с b(x)
по модулю р(x)”
и означает, что а(x)
и b(x)
имеют одинаковые остатки от деления на
полином p(x).

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

также на одну позицию вправо.

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

Рис.
1.15

Декодер
работает следующим образом. Перед
началом работы содержимое всех разрядов
регистров равно нулю. Принимаемая
последовательность r
в
течение первых n
тактов вводится в буферный регистр и
одновременно с этим в (n—k)-разрядном
сдвиговом регистре с обратными связями
производится ее деление на порождающий
полином g(x).

Через
n
тактов
в буферном регистре оказывается принятое
слово r
,
a в регистре синдрома — остаток от
деления вектора ошибки на порождающий
полином.

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

После
этого синдромный и буферный регистры
один раз циклически сдвигаются. Это
реализует умножение S(x)
на
x
и деление на g(x).
Содержимое ячеек синдромного регистра
теперь равно остатку от деления xS(x)
на g(x)
или синдрому ошибки x
е(x) mod (Хⁿ
+ 1).

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

Рассмотрим
работу декодера Меггитта для циклического
(7,4)-кода,
исправляющего одиночную ошибку. Схема
декодера изображена на рис. 1.16.

Рис.
1.16

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

Полином
ошибки в старшем разряде для (7,4)-кода
Хемминга имеет вид е₆(x)
= x⁶,
соответствующий ему синдромный полином
S₆(x)
= 1 + x³
(
S
= (101)),
детектор ошибки настроен на это значение
синдрома.

Пусть,
например, передана последовательность
U
= (1001011),
ей соответствует кодовый полином U(x)
= 1 + x³
+ x⁵
+ x⁶.
Произошла ошибка в третьей позиции е(x)
= x³,
принятый вектор имеет вид r
= (1000011),
его полином r(x)
= 1 + x⁵
+ x⁶.

Kогда
принятая последовательность полностью
входит в буферный регистр, в регистре
синдрома оказывается синдром,
соответствующий ошибке е(x)
= x³S₃
= (110).
Поскольку он не совпадает с табличным
для е₆,
на выходе детектора ошибок будет 0
и исправления не происходит.

Далее
производятся однократный циклический
сдвиг принятой последовательности в
буферном регистре, однократное деление
синдрома x∙S₃
на порождающий полином в регистре с
обратными связями и проверка на совпадение
синдрома с заданным.

Последовательность
состояний регистров декодера в процессе
декодирования показана на рис. 1.17.

Рис.
1.17

Т
аким
образом, исправление ошибки в декодере
Меггитта осуществляется за 2n
тактов: в течение n
тактов производится ввод принятой
последовательности в буферный регистр,
в течение l
тактов
— исправление ошибки, и еще в течение
n
— l
— восстановление
буферного регистра в исходное состояние
с исправленным словом. Простота декодера
достигается увеличением времени
декодирования.

Следует
отметить, что в связи с успехами в
разработке БИС и устройств памяти в
значительной степени снимается вопрос
о размерах таблиц, связывающих значения
синдрома и вектора ошибки (для синдромных
декодеров) и даже значения кодовых слов
и принятых последовательностей (для
декодера максимального правдоподобия).
Поэтому в перспективе возможно снижение
интереса к кодам, обладающим специальной
структурой, и к методам их декодирования.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
#
#
#
#
#
#
10.06.2015684.82 Кб13P4.pdf
#
#
#
#

Источник

Макеты страниц

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

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

Многочлен ошибок , где — исходный многочлен циклического кода Так, если ошибка произошла в то при коде ошибка в соответствует и т. д. Остаток от деления на для данного -элементного кода всегда одинаков, он не зависит от вида передаваемой комбинации. В рассматриваемом примере Наличие ошибки в других элементах приведет к другим остаткам Остатки зависят только от вида и . Для будет следующее соответствие:

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

На основании приведенного свойства существует следующий метод определения места ошибки. Сначала определяется остаток 1 (0, 1), соответствующий наличию ошибки в старшем разряде. Если ошибка произошла в следующем разряде (более низком), то такой же остаток получится в произведении принятого многочлена и Это служит основанием для следующего приема, суть которого ясна из следующего примера.

Пример 7.10. Предположим, задан код (11,7) в виде кодовой комбинации 10110111100 Здесь последние четыре разряда проверочные и получены на основе использования производящего многочлена . Принята кодовая комбинация 10111111100. Определить ошибочно принятый элемент

Вычисляем как остаток от деления на 10011. Произведя деление, получим 0111. Далее делим принятую комбинацию на (0,1) и получаем остаток Если то ошибка в старшем разряде. Если нет, то дописываем иуль и продолжаем деление. Номер ошибочно принятого разряда (отсчет слева направо) на единицу больше числа приписанных нулей, после которых остаток окажется равным 0111. Проведем процесс деления, отмечая штрихом получаемые остатки дописываемые

(1)

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

Источник

In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.

If 00010111 is a valid codeword, applying a right circular shift gives the string 10001011. If the code is cyclic, then 10001011 is again a valid codeword. In general, applying a right circular shift moves the least significant bit (LSB) to the leftmost position, so that it becomes the most significant bit (MSB); the other positions are shifted by 1 to the right.

Definition[edit]

Let be a linear code over a finite field (also called Galois field) GF(q) of block length . is called a cyclic code if, for every codeword ${displaystyle c=(c_{1},ldots ,c_{n})}$ from , the word ${displaystyle (c_{n},c_{1},ldots ,c_{n-1})}$ in $GF(q)^{n}$ obtained by a cyclic right shift of components is again a codeword. Because one cyclic right shift is equal to n-1 cyclic left shifts, a cyclic code may also be defined via cyclic left shifts. Therefore, the linear code is cyclic precisely when it is invariant under all cyclic shifts.

Cyclic codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properties they are very useful for error controls. Their structure is strongly related to Galois fields because of which the encoding and decoding algorithms for cyclic codes are computationally efficient.

Algebraic structure[edit]

Cyclic codes can be linked to ideals in certain rings. Let $R=A[x]/(x^{n}-1)$ be a polynomial ring over the finite field A=GF(q) . Identify the elements of the cyclic code with polynomials in such that
$(c_{0},ldots ,c_{n-1})$ maps to the polynomial
$c_{0}+c_{1}x+cdots +c_{n-1}x^{n-1}$ : thus multiplication by corresponds to a cyclic shift. Then is an ideal in , and hence principal, since is a principal ideal ring. The ideal is generated by the unique monic element in of minimum degree, the generator polynomial .^[1]
This must be a divisor of $x^{n}-1$ . It follows that every cyclic code is a polynomial code.
If the generator polynomial has degree then the rank of the code is n-d .

The idempotent of is a codeword such that $e^{2}=e$ (that is, is an idempotent element of ) and is an identity for the code, that is for every codeword . If and are coprime such a word always exists and is unique;^[2] it is a generator of the code.

An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in , so that its check polynomial is an irreducible polynomial.

Examples[edit]

For example, if ${displaystyle A=mathbb {F} _{2}}$ and n=3 , the set of codewords contained in cyclic code generated by is precisely

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

It corresponds to the ideal in $mathbb {F} _{2}[x]/(x^{3}-1)$ generated by (1+x) .

The polynomial (1+x) is irreducible in the polynomial ring, and hence the code is an irreducible code.

The idempotent of this code is the polynomial $x+x^{2}$ , corresponding to the codeword .

Trivial examples[edit]

Trivial examples of cyclic codes are $A^{n}$ itself and the code containing only the zero codeword. These correspond to generators and $x^{n}-1$ respectively: these two polynomials must always be factors of $x^{n}-1$ .

Over GF(2) the parity bit code, consisting of all words of even weight, corresponds to generator x+1 . Again over GF(2) this must always be a factor of $x^{n}-1$ .

Quasi-cyclic codes and shortened codes[edit]

Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.

Definition[edit]

Quasi-cyclic codes:^{[citation needed]}

An (n,k) quasi-cyclic code is a linear block code such that, for some which is coprime to , the polynomial ${displaystyle x^{b}c(x){pmod {x^{n}-1}}}$ is a codeword polynomial whenever c(x) is a codeword polynomial.

Here, codeword polynomial is an element of a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called the generator polynomial. Every codeword polynomial can be expressed in the form , where g(x) is the generator polynomial. Any codeword $(c_{0},..,c_{n-1})$ of a cyclic code can be associated with a codeword polynomial, namely, $sum _{i=0}^{n-1}c_{i}*x^{i}$ . A quasi-cyclic code with equal to is a cyclic code.

Definition[edit]

Shortened codes:

An [n,k] linear code is called a proper shortened cyclic code if it can be obtained by deleting positions from an cyclic code.

In shortened codes information symbols are deleted to obtain a desired blocklength smaller than the design blocklength. The missing information symbols are usually imagined to be at the beginning of the codeword and are considered to be 0. Therefore, − is fixed, and then is decreased which eventually decreases . It is not necessary to delete the starting symbols. Depending on the application sometimes consecutive positions are considered as 0 and are deleted.

All the symbols which are dropped need not be transmitted and at the receiving end can be reinserted. To convert (n,k) cyclic code to shortened code, set symbols to zero and drop them from each codeword. Any cyclic code can be converted to quasi-cyclic codes by dropping every th symbol where is a factor of . If the dropped symbols are not check symbols then this cyclic code is also a shortened code.

Cyclic codes for correcting errors[edit]

Now, we will begin the discussion of cyclic codes explicitly with error detection and correction. Cyclic codes can be used to correct errors, like Hamming codes as cyclic codes can be used for correcting single error. Likewise, they are also used to correct double errors and burst errors. All types of error corrections are covered briefly in the further subsections.

The (7,4) Hamming code has a generator polynomial $g(x)=x^{3}+x+1$ . This polynomial has a zero in Galois extension field GF(8) at the primitive element alpha , and all codewords satisfy . Cyclic codes can also be used to correct double errors over the field GF(2) . Blocklength will be equal to $2^{m}-1$ and primitive elements alpha and $alpha ^{3}$ as zeros in the $GF(2^{m})$ because we are considering the case of two errors here, so each will represent one error.

The received word is a polynomial of degree n-1 given as

where e(x) can have at most two nonzero coefficients corresponding to 2 errors.

We define the Syndrome Polynomial, S(x) as the remainder of polynomial v(x) when divided by the generator polynomial g(x) i.e.

as .

For correcting two errors[edit]

Let the field elements $X_{1}$ and $X_{2}$ be the two error location numbers. If only one error occurs then $X_{2}$ is equal to zero and if none occurs both are zero.

Let $S_{1}={v}(alpha )$ and $S_{3}={v}(alpha ^{3})$ .

These field elements are called «syndromes». Now because g(x) is zero at primitive elements alpha and $alpha ^{3}$ , so we can write $S_{1}=e(alpha )$ and $S_{3}=e(alpha ^{3})$ . If say two errors occur, then

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

And these two can be considered as two pair of equations in $GF(2^{m})$ with two unknowns and hence we can write

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

Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.

Hamming code[edit]

The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator $1+x+x^{3}$ . In fact, any binary Hamming code of the form Ham(r, 2) is equivalent to a cyclic code,^[3] and any Hamming code of the form Ham(r,q) with r and q-1 relatively prime is also equivalent to a cyclic code.^[4] Given a Hamming code of the form Ham(r,2) with rgeq 3 , the set of even codewords forms a cyclic $[2^{r}-1,2^{r}-r-2,4]$ -code.^[5]

Hamming code for correcting single errors[edit]

A code whose minimum distance is at least 3, have a check matrix all of whose columns are distinct and non zero. If a check matrix for a binary code has rows, then each column is an -bit binary number. There are $2^{m}-1$ possible columns. Therefore, if a check matrix of a binary code with $d_{min}$ at least 3 has rows, then it can only have $2^{m}-1$ columns, not more than that. This defines a $(2^{m}-1,2^{m}-1-m)$ code, called Hamming code.

It is easy to define Hamming codes for large alphabets of size . We need to define one matrix with linearly independent columns. For any word of size there will be columns who are multiples of each other. So, to get linear independence all non zero -tuples with one as a top most non zero element will be chosen as columns. Then two columns will never be linearly dependent because three columns could be linearly dependent with the minimum distance of the code as 3.

So, there are $(q^{m}-1)/(q-1)$ nonzero columns with one as top most non zero element. Therefore, a Hamming code is a $[(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]$ code.

Now, for cyclic codes, Let alpha be primitive element in $GF(q^{m})$ , and let $beta =alpha ^{q-1}$ . Then $beta ^{(q^{m}-1)/(q-1)}=1$ and thus beta is a zero of the polynomial $x^{(q^{m}-1)/(q-1)}-1$ and is a generator polynomial for the cyclic code of block length $n=(q^{m}-1)/(q-1)$ .

But for q=2 , . And the received word is a polynomial of degree n-1 given as

where, e(x)=0 or $x^{i}$ where represents the error locations.

But we can also use $alpha ^{i}$ as an element of $GF(2^{m})$ to index error location. Because , we have $v(alpha )=alpha ^{i}$ and all powers of alpha from to $2^{m}-2$ are distinct. Therefore, we can easily determine error location from $alpha ^{i}$ unless which represents no error. So, a Hamming code is a single error correcting code over GF(2) with $n=2^{m}-1$ and k=n-m .

Cyclic codes for correcting burst errors[edit]

From Hamming distance concept, a code with minimum distance 2t+1 can correct any errors. But in many channels error pattern is not very arbitrary, it occurs within very short segment of the message. Such kind of errors are called burst errors. So, for correcting such errors we will get a more efficient code of higher rate because of the less constraints. Cyclic codes are used for correcting burst error. In fact, cyclic codes can also correct cyclic burst errors along with burst errors. Cyclic burst errors are defined as

A cyclic burst of length is a vector whose nonzero components are among (cyclically) consecutive components, the first and the last of which are nonzero.

In polynomial form cyclic burst of length can be described as $e(x)=x^{i}b(x)mod (x^{n}-1)$ with b(x) as a polynomial of degree t-1 with nonzero coefficient $b_{0}$ . Here b(x) defines the pattern and $x^{i}$ defines the starting point of error. Length of the pattern is given by deg b(x)+1 . The syndrome polynomial is unique for each pattern and is given by

A linear block code that corrects all burst errors of length or less must have at least check symbols. Proof: Because any linear code that can correct burst pattern of length or less cannot have a burst of length or less as a codeword because if it did then a burst of length could change the codeword to burst pattern of length , which also could be obtained by making a burst error of length in all zero codeword. Now, any two vectors that are non zero in the first components must be from different co-sets of an array to avoid their difference being a codeword of bursts of length . Therefore, number of such co-sets are equal to number of such vectors which are $q^{2t}$ . Hence at least $q^{2t}$ co-sets and hence at least check symbol.

This property is also known as Rieger bound and it is similar to the Singleton bound for random error correcting.

Fire codes as cyclic bounds[edit]

In 1959, Philip Fire^[6] presented a construction of cyclic codes generated by a product of a binomial and a primitive polynomial. The binomial has the form $x^{c}+1$ for some positive odd integer .^[7] Fire code is a cyclic burst error correcting code over GF(q) with the generator polynomial

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

where p(x) is a prime polynomial with degree not smaller than and p(x) does not divide $x^{2t-1}-1$ . Block length of the fire code is the smallest integer such that g(x) divides
$x^{n}-1$ .

A fire code can correct all burst errors of length t or less if no two bursts b(x) and $x^{j}b'(x)$ appear in the same co-set. This can be proved by contradiction. Suppose there are two distinct nonzero bursts b(x) and $x^{j}b'(x)$ of length or less and are in the same co-set of the code. So, their difference is a codeword. As the difference is a multiple of g(x) it is also a multiple of $x^{2t-1}-1$ . Therefore,

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

This shows that is a multiple of 2t-1 , So

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

for some . Now, as l(2t-1) is less than and is less than $q^{m}-1$ so $(x^{l(2t-1)}-1)b(x)$ is a codeword. Therefore,

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

Since b(x) degree is less than degree of p(x) , p(x) cannot divide b(x) . If is not zero, then p(x) also cannot divide $x^{l(2t-1)}-1$ as is less than $q^{m}-1$ and by definition of , p(x) divides $x^{l(2t-1)}-1$ for no smaller than $q^{m}-1$ . Therefore and equals to zero. That means both that both the bursts are same, contrary to assumption.

Fire codes are the best single burst correcting codes with high rate and they are constructed analytically. They are of very high rate and when and are equal, redundancy is least and is equal to 3t-1 . By using multiple fire codes longer burst errors can also be corrected.

For error detection cyclic codes are widely used and are called t-1 cyclic redundancy codes.

Cyclic codes on Fourier transform[edit]

Applications of Fourier transform are widespread in signal processing. But their applications are not limited to the complex fields only; Fourier transforms also exist in the Galois field GF(q) . Cyclic codes using Fourier transform can be described in a setting closer to the signal processing.

Fourier transform over finite fields[edit]

Fourier transform over finite fields

The discrete Fourier transform of vector $v=v_{0},v_{1},....,v_{n-1}$ is given by a vector $V=V_{0},V_{1},.....,V_{n-1}$ where,

$V_{k}$ = $Sigma _{i=0}^{n-1}e^{-j2pi n^{-1}ik}v_{i}$ where,

where exp() is an th root of unity. Similarly in the finite field th root of unity is element omega of order . Therefore

If $v=(v_{0},v_{1},....,v_{n-1})$ is a vector over , and be an element of of order , then Fourier transform of the vector is the vector $V=(V_{0},V_{1},.....,V_{n-1})$ and components are given by

$V_{j}$ = $Sigma _{i=0}^{n-1}omega ^{ij}v_{i}$ where,

Here is time index, is frequency and is the spectrum. One important difference between Fourier transform in complex field and Galois field is that complex field omega exists for every value of while in Galois field omega exists only if divides q-1 . In case of extension fields, there will be a Fourier transform in the extension field $GF(q^{m})$ if divides $q^{m}-1$ for some .
In Galois field time domain vector is over the field GF(q) but the spectrum may be over the extension field $GF(q^{m})$ .

Spectral description of cyclic codes[edit]

Any codeword of cyclic code of blocklength can be represented by a polynomial c(x) of degree at most n-1 . Its encoder can be written as . Therefore, in frequency domain encoder can be written as $C_{j}=A_{j}G_{j}$ . Here codeword spectrum $C_{j}$ has a value in $GF(q^{m})$ but all the components in the time domain are from GF(q) . As the data spectrum $A_{j}$ is arbitrary, the role of $G_{j}$ is to specify those where $C_{j}$ will be zero.

Thus, cyclic codes can also be defined as

Given a set of spectral indices, $A=(j_{1},....,j_{n-k})$ , whose elements are called check frequencies, the cyclic code is the set of words over GF(q) whose spectrum is zero in the components indexed by $j_{1},...,j_{n-k}$ . Any such spectrum will have components of the form $A_{j}G_{j}$ .

So, cyclic codes are vectors in the field GF(q) and the spectrum given by its inverse fourier transform is over the field $GF(q^{m})$ and are constrained to be zero at certain components. But every spectrum in the field $GF(q^{m})$ and zero at certain components may not have inverse transforms with components in the field GF(q) . Such spectrum can not be used as cyclic codes.

Following are the few bounds on the spectrum of cyclic codes.

BCH bound[edit]

If be a factor of $(q^{m}-1)$ for some . The only vector in $GF(q)^{n}$ of weight d-1 or less that has d-1 consecutive components of its spectrum equal to zero is all-zero vector.

Hartmann-Tzeng bound[edit]

If be a factor of $(q^{m}-1)$ for some , and an integer that is coprime with . The only vector in $GF(q)^{n}$ of weight d-1 or less whose spectral
components $V_{j}$ equal zero for $j=ell _{1}+ell _{2}b(mod n)$ , where $ell _{1}=0,....,d-s-1$ and $ell _{2}=0,....,s-1$ , is the all zero vector.

Roos bound[edit]

If be a factor of $q^{m}-1$ for some and . The only vector in
$GF(q)^{n}$ of weight d-1 or less whose spectral components $V_{j}$ equal to zero for $j=l_{1}+l_{2}b(mod n)$ , where $l_{1}=0,...,d-s-2$ and $l_{2}$ takes at least s+1 values in the range , is the all-zero vector.

Quadratic residue codes[edit]

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

Generalizations[edit]

A constacyclic code is a linear code with the property that for some constant λ if (c₁,c₂,…,c_n) is a codeword then so is (λc_n,c₁,…,c_n-1). A negacyclic code is a constacyclic code with λ=-1.^[8] A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.^[9] A double circulant code is a quasi-cyclic code of even length with s=2.^[9] Quasi-twisted codes and multi-twisted codes are further generalizations of constacyclic codes.^[10]^[11]

Notes[edit]

^ Van Lint 1998, p. 76
^ Van Lint 1998, p. 80
^ Hill 1988, pp. 159–160
^ Blahut 2003, Theorem 5.5.1
^ Hill 1988, pp. 162–163
^ P. Fire, E, P. (1959). A class of multiple-error-correcting binary codes for non-independent errors. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
^ Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Burst or random error correction based on Fire and BCH codes. ITA 2014: 1-5 2013.
^ Van Lint 1998, p. 75
^ ^a ^b MacWilliams & Sloane 1977, p. 506
^ Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). «The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes». Designs, Codes and Cryptography. 24 (3): 313–326. doi:10.1023/A:1011283523000. S2CID 17376783.
^ Aydin, Nuh; Halilović, Ajdin (2017). «A generalization of quasi-twisted codes: multi-twisted codes». Finite Fields and Their Applications. 45: 96–106. doi:10.1016/j.ffa.2016.12.002. S2CID 7694655.

References[edit]

Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
Hill, Raymond (1988), A First Course In Coding Theory, Oxford University Press, ISBN 0-19-853803-0
MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York: North-Holland Publishing, ISBN 0-444-85011-2
Van Lint, J. H. (1998), Introduction to Coding Theory, Graduate Texts in Mathematics 86 (3rd ed.), Springer Verlag, ISBN 3-540-64133-5

External links[edit]

John Gill’s (Stanford) class notes – Notes #3, October 8, Handout #9, EE 387.
Jonathan Hall’s (MSU) class notes – Chapter 8. Cyclic codes — pp. 100 — 123
David Terr. «Cyclic Code». MathWorld.

This article incorporates material from cyclic code on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Источник

Definition[edit]

Algebraic structure[edit]

An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in , so that its check polynomial is an irreducible polynomial.

Examples[edit]

For example, if ${displaystyle A=mathbb {F} _{2}}$ and n=3 , the set of codewords contained in cyclic code generated by is precisely

It corresponds to the ideal in $mathbb {F} _{2}[x]/(x^{3}-1)$ generated by (1+x) .

The polynomial (1+x) is irreducible in the polynomial ring, and hence the code is an irreducible code.

The idempotent of this code is the polynomial $x+x^{2}$ , corresponding to the codeword .

Trivial examples[edit]

Over GF(2) the parity bit code, consisting of all words of even weight, corresponds to generator x+1 . Again over GF(2) this must always be a factor of $x^{n}-1$ .

Quasi-cyclic codes and shortened codes[edit]

Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.

Definition[edit]

Quasi-cyclic codes:^{[citation needed]}

Definition[edit]

Shortened codes:

An [n,k] linear code is called a proper shortened cyclic code if it can be obtained by deleting positions from an cyclic code.

Cyclic codes for correcting errors[edit]

The received word is a polynomial of degree n-1 given as

where e(x) can have at most two nonzero coefficients corresponding to 2 errors.

We define the Syndrome Polynomial, S(x) as the remainder of polynomial v(x) when divided by the generator polynomial g(x) i.e.

as .

For correcting two errors[edit]

Let the field elements $X_{1}$ and $X_{2}$ be the two error location numbers. If only one error occurs then $X_{2}$ is equal to zero and if none occurs both are zero.

Let $S_{1}={v}(alpha )$ and $S_{3}={v}(alpha ^{3})$ .

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

And these two can be considered as two pair of equations in $GF(2^{m})$ with two unknowns and hence we can write

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

Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.

Hamming code[edit]

Hamming code for correcting single errors[edit]

So, there are $(q^{m}-1)/(q-1)$ nonzero columns with one as top most non zero element. Therefore, a Hamming code is a $[(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]$ code.

But for q=2 , . And the received word is a polynomial of degree n-1 given as

where, e(x)=0 or $x^{i}$ where represents the error locations.

Cyclic codes for correcting burst errors[edit]

A cyclic burst of length is a vector whose nonzero components are among (cyclically) consecutive components, the first and the last of which are nonzero.

This property is also known as Rieger bound and it is similar to the Singleton bound for random error correcting.

Fire codes as cyclic bounds[edit]

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

where p(x) is a prime polynomial with degree not smaller than and p(x) does not divide $x^{2t-1}-1$ . Block length of the fire code is the smallest integer such that g(x) divides
$x^{n}-1$ .

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

This shows that is a multiple of 2t-1 , So

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

for some . Now, as l(2t-1) is less than and is less than $q^{m}-1$ so $(x^{l(2t-1)}-1)b(x)$ is a codeword. Therefore,

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

For error detection cyclic codes are widely used and are called t-1 cyclic redundancy codes.

Cyclic codes on Fourier transform[edit]

Fourier transform over finite fields[edit]

Fourier transform over finite fields

The discrete Fourier transform of vector $v=v_{0},v_{1},....,v_{n-1}$ is given by a vector $V=V_{0},V_{1},.....,V_{n-1}$ where,

$V_{k}$ = $Sigma _{i=0}^{n-1}e^{-j2pi n^{-1}ik}v_{i}$ where,

where exp() is an th root of unity. Similarly in the finite field th root of unity is element omega of order . Therefore

If $v=(v_{0},v_{1},....,v_{n-1})$ is a vector over , and be an element of of order , then Fourier transform of the vector is the vector $V=(V_{0},V_{1},.....,V_{n-1})$ and components are given by

$V_{j}$ = $Sigma _{i=0}^{n-1}omega ^{ij}v_{i}$ where,

Spectral description of cyclic codes[edit]

Thus, cyclic codes can also be defined as

Following are the few bounds on the spectrum of cyclic codes.

BCH bound[edit]

If be a factor of $(q^{m}-1)$ for some . The only vector in $GF(q)^{n}$ of weight d-1 or less that has d-1 consecutive components of its spectrum equal to zero is all-zero vector.

Hartmann-Tzeng bound[edit]

Roos bound[edit]

Quadratic residue codes[edit]

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

Generalizations[edit]

Notes[edit]

^ Van Lint 1998, p. 76
^ Van Lint 1998, p. 80
^ Hill 1988, pp. 159–160
^ Blahut 2003, Theorem 5.5.1
^ Hill 1988, pp. 162–163
^ P. Fire, E, P. (1959). A class of multiple-error-correcting binary codes for non-independent errors. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
^ Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Burst or random error correction based on Fire and BCH codes. ITA 2014: 1-5 2013.
^ Van Lint 1998, p. 75
^ ^a ^b MacWilliams & Sloane 1977, p. 506
^ Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). «The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes». Designs, Codes and Cryptography. 24 (3): 313–326. doi:10.1023/A:1011283523000. S2CID 17376783.
^ Aydin, Nuh; Halilović, Ajdin (2017). «A generalization of quasi-twisted codes: multi-twisted codes». Finite Fields and Their Applications. 45: 96–106. doi:10.1016/j.ffa.2016.12.002. S2CID 7694655.

References[edit]

Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
Hill, Raymond (1988), A First Course In Coding Theory, Oxford University Press, ISBN 0-19-853803-0
MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York: North-Holland Publishing, ISBN 0-444-85011-2
Van Lint, J. H. (1998), Introduction to Coding Theory, Graduate Texts in Mathematics 86 (3rd ed.), Springer Verlag, ISBN 3-540-64133-5

External links[edit]

John Gill’s (Stanford) class notes – Notes #3, October 8, Handout #9, EE 387.
Jonathan Hall’s (MSU) class notes – Chapter 8. Cyclic codes — pp. 100 — 123
David Terr. «Cyclic Code». MathWorld.

This article incorporates material from cyclic code on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Источник

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

Definition[edit]

Algebraic structure[edit]

Examples[edit]

Trivial examples[edit]

Quasi-cyclic codes and shortened codes[edit]

Definition[edit]

Definition[edit]

Cyclic codes for correcting errors[edit]

For correcting two errors[edit]

Hamming code[edit]

Hamming code for correcting single errors[edit]

Cyclic codes for correcting burst errors[edit]

Fire codes as cyclic bounds[edit]

Cyclic codes on Fourier transform[edit]

Fourier transform over finite fields[edit]

Spectral description of cyclic codes[edit]

BCH bound[edit]

Hartmann-Tzeng bound[edit]

Roos bound[edit]

Quadratic residue codes[edit]

Generalizations[edit]

See also[edit]

Notes[edit]

References[edit]

Further reading[edit]

External links[edit]

Definition[edit]

Algebraic structure[edit]

Examples[edit]

Trivial examples[edit]

Quasi-cyclic codes and shortened codes[edit]

Definition[edit]

Definition[edit]

Cyclic codes for correcting errors[edit]

For correcting two errors[edit]

Hamming code[edit]

Hamming code for correcting single errors[edit]

Cyclic codes for correcting burst errors[edit]

Fire codes as cyclic bounds[edit]

Cyclic codes on Fourier transform[edit]

Fourier transform over finite fields[edit]

Spectral description of cyclic codes[edit]

BCH bound[edit]

Hartmann-Tzeng bound[edit]

Roos bound[edit]

Quadratic residue codes[edit]

Generalizations[edit]

See also[edit]

Notes[edit]

References[edit]

Further reading[edit]

External links[edit]