Введение
Тип блочного кода
В теории кодирования циклический код — это блочный код, для которого циклические сдвиги каждого кодового слова также являются кодовыми словами. Это коды, исправляющие ошибки, обладающие алгебраическими свойствами, удобными для эффективного обнаружения и исправления ошибок.
Определение
Пусть будет линейный код над конечным полем (также называемым полем Галуа) длины блока. Код называется циклическим, если для каждого кодового слова из , слово, полученное циклическим правым сдвигом компонентов, также является кодовым словом. Поскольку один циклический правый сдвиг эквивалентен циклическим левым сдвигам, циклический код может быть также определен через циклические левые сдвиги. Следовательно, линейный код является циклическим тогда и только тогда, когда он инвариантен относительно всех циклических сдвигов. Циклические коды обладают дополнительными структурными ограничениями. Они основаны на полях Галуа, и благодаря своим структурным свойствам они очень полезны для контроля ошибок. Их структура тесно связана с полями Галуа, что обеспечивает вычислительную эффективность алгоритмов кодирования и декодирования для циклических кодов.
Тривиальные примеры
Тривиальными примерами циклических кодов являются сам код и код, содержащий только нулевое кодовое слово. Они соответствуют генераторам и соответственно: эти два многочлена всегда должны быть делителями . Над полем из двух элементов код четности, состоящий из всех слов четного веса, соответствует генератору . Снова над полем из двух элементов, этот многочлен всегда должен быть делителем .
Over the parity bit code, consisting of all words of even weight, corresponds to generator Again over this must always be a factor of .
Квазициклические коды и сокращенные коды
Прежде чем углубиться в детали циклических кодов, мы обсудим квазициклические и укороченные коды, которые тесно связаны с циклическими кодами, и все они могут быть преобразованы друг в друга.
Код Хамминга
Код Хамминга (7,4) может быть записан как циклический код над GF(2) с образующей матрицей. Фактически, любой двоичный код Хамминга вида Ham(r, 2) эквивалентен циклическому коду, и любой код Хамминга вида Ham(r,q) с r и q взаимно простых также эквивалентен циклическому коду. Для кода Хамминга вида Ham(r,2) с , множество четных кодовых слов образует циклический код.
Код Хамминга для исправления единичных ошибок
Код, минимальное расстояние которого не меньше 3, имеет контрольную матрицу, все столбцы которой различны и ненулевые. Если контрольная матрица для двоичного кода имеет строк, то каждый столбец является двоичным числом из бит. Существует возможных столбцов. Следовательно, если контрольная матрица двоичного кода с минимальным расстоянием не менее 3 имеет строк, то она может иметь только столбцов, не более того. Это определяет код, называемый кодом Хэмминга. Легко определить коды Хэмминга для больших алфавитов размера . Нам нужно определить одну матрицу с линейно независимыми столбцами. Для любого слова длины будут столбцы, кратные друг другу. Чтобы обеспечить линейную независимость, выбираются все ненулевые кортежи с единицей в качестве старшего ненулевого элемента в качестве столбцов. Тогда два столбца никогда не будут линейно зависимы, поскольку три столбца могут быть линейно зависимы при минимальном расстоянии кода, равном 3. Таким образом, существует ненулевых столбцов с единицей в качестве старшего ненулевого элемента. Следовательно, код Хэмминга – это -код. Теперь, для циклических кодов, пусть будет примитивным элементом в , и пусть . Тогда и, следовательно, является корнем полинома и является образующим полиномом для циклического кода длины блока . Но для , и принятое слово является полиномом степени , заданным как , где или , где обозначает местоположения ошибок. Но мы также можем использовать в качестве элемента для индексации местоположения ошибки. Поскольку , у нас есть и все степени от до различны. Поэтому мы можем легко определить местоположение ошибки из , если не , что означает отсутствие ошибки. Таким образом, код Хэмминга – это код с однократным исправлением ошибок над полем с и .
But for , And the received word is a polynomial of degree given as
where, or where represents the error locations. But we can also use as an element of to index error location. Because , we have and all powers of from to are distinct. Therefore, we can easily determine error location from unless which represents no error. So, a Hamming code is a single error correcting code over with and .
Для исправления ошибок в сбое
Из концепции расстояния Хэмминга, код с минимальным расстоянием может исправить любые ошибки. Однако во многих каналах структура ошибок не является полностью случайной, они возникают в пределах очень короткого участка сообщения. Такие ошибки называются импульсными ошибками (или ошибками всплеска). Следовательно, для исправления таких ошибок можно получить более эффективный код с более высокой скоростью за счет меньших ограничений. Циклические коды используются для исправления импульсных ошибок. Фактически, циклические коды могут исправлять как импульсные, так и циклические импульсные ошибки. Циклическая импульсная ошибка длины определяется как вектор, ненулевые компоненты которого находятся среди (циклически) последовательных компонентов, причем первый и последний из них ненулевые. В полиномиальной форме циклическая импульсная ошибка длины может быть описана как , где является полиномом степени с ненулевым коэффициентом. Здесь определяет структуру ошибки, а определяет начальную позицию ошибки. Длина структуры ошибки определяется степенью полинома. Полином синдрома уникален для каждого шаблона и задается следующим образом:
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 with as a polynomial of degree with nonzero coefficient Here defines the pattern and defines the starting point of error. Length of the pattern is given by deg. 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 Hence at least 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.
Линейный блочный код, исправляющий все импульсные ошибки длины или меньше, должен иметь не менее контрольных символов. Доказательство: любой линейный код, способный исправлять импульсные ошибки длины или меньше, не может содержать импульсную ошибку длины или меньше в качестве кодового слова, поскольку в противном случае импульсная ошибка длины могла бы преобразовать кодовое слово в импульсную ошибку длины, которую также можно получить, внеся импульсную ошибку длины в нулевое кодовое слово. Теперь, любые два вектора, ненулевые в первых компонентах, должны принадлежать разным кодовым подпространствам, чтобы их разность не являлась кодовым словом, представляющим импульсную ошибку длины . Следовательно, число таких кодовых подпространств равно числу таких векторов, то есть не менее . Таким образом, требуется не менее кодовых подпространств и, следовательно, не менее контрольных символов. Это свойство также известно как граница Ригера и аналогично границе Синглтона для исправления случайных ошибок.
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 with as a polynomial of degree with nonzero coefficient Here defines the pattern and defines the starting point of error. Length of the pattern is given by deg. 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 Hence at least 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.
На трансформации Фурье
Приложения преобразования Фурье широко распространены в обработке сигналов. Однако их применение не ограничивается только комплексными областями; преобразования Фурье существуют и в полях Галуа. Циклические коды, использующие преобразование Фурье, можно описать в рамках, более близких к обработке сигналов.
BCH связан
Если $a$ является делителем $b$ для некоторого $b$, то единственный вектор в $\mathbb{R}^n$ веса не более $b$, имеющий $a$ последовательных нулевых компонент в своем спектре, является нулевым вектором.
Хартманн-Ценг
Если `a` является делителем `n` для некоторого `n`, и `k` — целое число, взаимно простое с `n`, то единственным вектором `x` в `Z_n^m` веса не более `k`, у которого спектральные компоненты равны нулю для всех `j`, где `1 ≤ j ≤ k`, является нулевой вектор.
components equal zero for , where and , is the all zero vector.
Весьма неплохо.
Если `a` является делителем `b` для некоторого `b`, и единственный вектор в `R^n` весом не более `w`, чьи спектральные компоненты равны нулю для `i = 1, ..., n`, где `n` принимает по крайней мере `m` значений в диапазоне `[1, N]`, является нулевым вектором.
of weight or less whose spectral components equal to zero for , where and takes at least values in the range , is the all zero vector.
Коды квадратных остатков
Когда простое число является квадратичным остатком по модулю простого числа , существует код квадратичных остатков, являющийся циклическим кодом длины , размерности и минимального веса не менее , над .
Обобщения
Констациклический код — это линейный код, обладающий свойством, что для некоторой постоянной λ, если (c1, c2, ..., cn) является кодовым словом, то и (λcn, c1, ..., cn-1) также является кодовым словом. Негациклический код — это констациклический код с λ = -1. Квазициклический код обладает свойством, что для некоторого s любое циклическое сдвигание кодового слова на s позиций также является кодовым словом. Двойной циркулянтный код — это квазициклический код четной длины с s = 2.