В теории кодирования , циклический код является блок кода , где круговые сдвиги каждого кодового слова , дает еще одно слово , которое принадлежит к коду. Это коды с исправлением ошибок, которые имеют алгебраические свойства, удобные для эффективного обнаружения и исправления ошибок .
Определение
Позволять - линейный код над конечным полем (также называемым полем Галуа )от длины блока п .называется циклическим кодом, если для каждого кодового слова c = ( c 1 , ..., c n ) из C слово ( c n , c 1 , ..., c n-1 ) вполученный циклическим сдвигом компонентов вправо, снова является кодовым словом. Поскольку один циклический сдвиг вправо равен n - 1 циклическому сдвигу влево, циклический код также может быть определен посредством циклических сдвигов влево. Следовательно, линейный код циклично именно тогда, когда оно инвариантно относительно всех циклических сдвигов.
Циклические коды имеют некоторые дополнительные структурные ограничения на коды. Они основаны на полях Галуа и благодаря своим структурным свойствам очень полезны для контроля ошибок. Их структура сильно связана с полями Галуа, из-за которых алгоритмы кодирования и декодирования для циклических кодов являются эффективными с вычислительной точки зрения.
Алгебраическая структура
Циклические коды могут быть связаны с идеалами в определенных кольцах. Позволятьбыть кольцо многочленов над конечным полем. Отождествим элементы циклического кода C с многочленами из R такими, что отображается в полином : таким образом, умножение на x соответствует циклическому сдвигу. Тогда C - идеал в R и, следовательно, главный , поскольку R - кольцо главных идеалов . Идеал порождается единственным моническим элементом в C минимальной степени порождающим многочленом g . [1] Это должно быть делителем. Отсюда следует, что каждый циклический код является полиномиальным кодом . Если порождающий полином g имеет степень d, то ранг кода C равен.
Идемпотентный из C является кодовым словом е таким , что е 2 = е (то есть, е представляет собой идемпотентная элемент из С ) и е представляет собой тождество для кода, то есть е с = с для каждого кодового слова , с . Если п и д являются взаимно простыми такое слово всегда существует и единственно; [2] это генератор кода.
Неприводимый код представляет собой циклический код , в котором код, как идеал неприводит, т.е. минимальна в R , так что проверка его многочлен является неприводимым многочленом .
Примеры
Например, если A =и n = 3, набор кодовых слов, содержащихся в циклическом коде, порожденном (1,1,0), в точности равен
- .
Он соответствует идеалу в создан .
Полином неприводима в кольце многочленов, следовательно, код является неприводимым кодом.
Идемпотент этого кода - многочлен , соответствующий кодовому слову (0,1,1).
Тривиальные примеры
Тривиальными примерами циклических кодов являются сам A n и код, содержащий только нулевое кодовое слово. Они соответствуют генераторам 1 и соответственно: эти два многочлена всегда должны быть множителями .
Над GF (2) битовый код четности , состоящий из всех слов четного веса, соответствует генератору. Снова по GF (2) это всегда должно быть множителем.
Квазициклические коды и сокращенные коды
Прежде чем углубляться в детали циклических кодов, мы сначала обсудим квазициклические и сокращенные коды, которые тесно связаны с циклическими кодами, и все они могут быть преобразованы друг в друга.
Определение
Квазициклические коды: [ необходима цитата ]
An квазициклический код - это линейный блочный код, такой, что для некоторых который взаимно прост с , многочлен является полиномом кодового слова всякий раз, когда является полиномом кодового слова.
Здесь полином кодового слова - это элемент линейного кода, кодовые слова которого являются полиномами, которые делятся на полином меньшей длины, называемый порождающим полиномом . Каждый полином кодового слова может быть выражен в виде, где - порождающий полином. Любое кодовое слово циклического кода можно связать с полиномом кодового слова, а именно, . Квазициклический код с равно - циклический код.
Определение
Сокращенные коды:
An линейный код называется собственным сокращенным циклическим кодом, если он может быть получен путем удаления позиции из циклический код.
В сокращенных кодах информационные символы удаляются, чтобы получить желаемую длину блока, меньшую проектной длины. Отсутствующие информационные символы обычно предполагаются в начале кодового слова и считаются равными 0. Следовательно,- фиксируется, а затем уменьшается, что в конечном итоге уменьшается . Стартовые символы удалять не нужно. В зависимости от приложения иногда последовательные позиции считаются за 0 и удаляются.
Все отброшенные символы не нужно передавать, и на принимающей стороне их можно повторно вставить. Конвертировать циклический код для сокращенный код, набор символы к нулю и отбросьте их из каждого кодового слова. Любой циклический код можно преобразовать в квазициклические коды, отбрасывая каждыйй символ где фактор . Если отброшенные символы не являются проверочными символами, тогда этот циклический код также является сокращенным кодом.
Циклические коды для исправления ошибок
Теперь мы начнем обсуждение циклических кодов явно с обнаружения и исправления ошибок . Циклические коды могут использоваться для исправления ошибок, как коды Хэмминга, поскольку циклические коды могут использоваться для исправления одиночной ошибки. Точно так же они также используются для исправления двойных ошибок и пакетных ошибок. Все типы исправлений ошибок кратко описаны в следующих подразделах.
Код Хэмминга (7,4) имеет порождающий полином . Этот многочлен имеет нуль в поле расширений Галуа у примитивного элемента , и все кодовые слова удовлетворяют . Циклические коды также могут использоваться для исправления двойных ошибок по полю.. Длина блока будет равно и примитивные элементы а также как нули в потому что здесь мы рассматриваем случай двух ошибок, поэтому каждая будет представлять одну ошибку.
Полученное слово - многочлен степени дан как
где может иметь не более двух ненулевых коэффициентов, соответствующих 2 ошибкам.
Мы определяем полином синдрома , как остаток от полинома при делении на порождающий полином т.е.
в виде .
Для исправления двух ошибок
Пусть элементы поля а также - два номера местоположения ошибки. Если возникает только одна ошибка, то равно нулю, и если ничего не встречается, оба равны нулю.
Позволять а также .
Эти элементы поля называются «синдромами». Теперь, потому что равен нулю в примитивных элементах а также , поэтому мы можем написать а также . Если, скажем, возникают две ошибки, то
а также .
И эти два можно рассматривать как две пары уравнений в с двумя неизвестными и, следовательно, мы можем написать
а также .
Следовательно, если две пары нелинейных уравнений могут быть решены, циклические коды могут использоваться для исправления двух ошибок.
Код Хэмминга
Код Хэмминга (7,4) может быть записан как циклический код над GF (2) с генератором. Фактически, любой двоичный код Хэмминга вида Ham (r, 2) эквивалентен циклическому коду [3], и любой код Хэмминга вида Ham (r, q) с взаимно простыми числами r и q-1 также эквивалентен к циклическому коду. [4] Для кода Хэмминга вида Ham (r, 2) с, набор четных кодовых слов образует циклический -код. [5]
Код Хэмминга для исправления одиночных ошибок
Код, минимальное расстояние которого составляет не менее 3, имеет контрольную матрицу, все столбцы которой различны и не равны нулю. Если контрольная матрица для двоичного кода имеет строк, то каждый столбец представляет собой -битовое двоичное число. Естьвозможные столбцы. Следовательно, если проверочная матрица двоичного кода с по крайней мере 3 имеют строк, то он может иметь только столбцы, не более того. Это определяет код, называемый кодом Хэмминга.
Коды Хэмминга легко определить для больших алфавитов размера . Нам нужно определить одинматрица с линейно независимыми столбцами. Для слова любого размерабудут столбцы, которые кратны друг другу. Итак, чтобы получить линейную независимость, все ненулевые-кортежи с одним верхним ненулевым элементом будут выбраны в качестве столбцов. Тогда два столбца никогда не будут линейно зависимыми, потому что три столбца могут быть линейно зависимыми с минимальным расстоянием кода равным 3.
Итак, есть ненулевые столбцы с одним самым верхним ненулевым элементом. Следовательно, код Хэмминга - это код.
Теперь для циклических кодов Пусть быть примитивным элементом в , и разреши . потом и поэтому является нулем многочлена и является порождающим полиномом для циклического кода блочной длины .
Но для , . А полученное слово - многочлен степени дан как
где, или же где представляет собой расположение ошибок.
Но мы также можем использовать как элемент для индексации места ошибки. Так как, у нас есть и все силы из к различны. Таким образом, мы можем легко определить место ошибки. из пока не что не представляет ошибки. Итак, код Хэмминга - это код с исправлением одиночных ошибок, превышающий с участием а также .
Циклические коды для исправления пакетных ошибок
Из концепции расстояния Хэмминга код с минимальным расстоянием может исправить любой ошибки. Но во многих каналах шаблон ошибки не очень произвольный, он возникает в очень коротком сегменте сообщения. Такие ошибки называются пакетными ошибками . Таким образом, для исправления таких ошибок мы получим более эффективный код с более высокой скоростью из-за меньшего количества ограничений. Циклические коды используются для исправления пакетной ошибки. Фактически, циклические коды могут также исправлять циклические пакетные ошибки вместе с пакетными ошибками. Циклические пакетные ошибки определяются как
Циклический всплеск длины - вектор, ненулевые компоненты которого находятся среди (циклически) последовательные компоненты, первая и последняя из которых не равны нулю.
В полиномиальной форме циклический всплеск длины можно описать как с участием как многочлен степени с ненулевым коэффициентом . Здесь определяет шаблон и определяет начальную точку ошибки. Длина рисунка определяется в градусах.. Синдромный полином уникален для каждого паттерна и определяется выражением
Линейный блочный код, который исправляет все пакетные ошибки длины или меньше должен иметь как минимум проверьте символы. Доказательство: потому что любой линейный код, который может исправить последовательность пакетов длины или меньше не может иметь длительную серию или меньше в качестве кодового слова, потому что если это так, то всплеск длины может изменить кодовое слово на пакетную последовательность длины , которое также можно было получить, сделав пакетную ошибку длиной во всех нулевых кодовых словах. Теперь любые два вектора, отличные от нуля в первом компоненты должны быть из разных совокупностей массива, чтобы их различие не являлось кодовым словом пакетов длины . Следовательно, количество таких совокупностей равно количеству таких векторов, которые. Следовательно, по крайней мере co-множеств и, следовательно, по крайней мере проверьте символ.
Это свойство также известно как граница Ригера и похожа на границу Синглтона для исправления случайных ошибок.
Коды пожара как циклические границы
В 1959 году Филип Файр [6] представил конструкцию циклических кодов, порожденных произведением бинома и примитивного полинома. Бином имеет вид для некоторого положительного нечетного целого числа . [7] Пожарный код - это циклический код исправления пакетных ошибок по с образующим полиномом
где является простым многочленом степени не меньше чем а также не делит . Длина блока пожарного кода - наименьшее целое число такой, что разделяет .
Пожарный код может исправить все пакеты ошибок длиной t или меньше, если нет двух пакетов а также появляются в одной совокупности. Это можно доказать от противного. Предположим, что есть два различных ненулевых всплеска а также длины или меньше и находятся в одной совокупности кода. Итак, их отличие - это кодовое слово. Поскольку разница кратна это также кратно . Следовательно,
.
Это показывает, что кратно , Так
для некоторых . Теперь, когда меньше чем а также меньше чем так это кодовое слово. Следовательно,
.
С степень меньше степени , не могу разделить . Если не равно нулю, тогда также не может разделить в виде меньше чем и по определению , разделяет нет меньше чем . Следовательно а также равно нулю. Это означает, что оба всплеска одинаковы, вопреки предположению.
Коды пожара являются лучшими однократными исправляющими кодами с высокой скоростью, и они построены аналитически. Они очень высоки и когда а также равны, избыточность наименьшая и равна . Используя несколько кодов пожара, можно также исправить более длинные пакеты ошибок.
Для обнаружения ошибок широко используются циклические коды, которые называются циклические коды избыточности .
Циклические коды на преобразовании Фурье
Применение преобразования Фурье широко распространено в обработке сигналов. Но их приложения не ограничиваются только сложными областями; Преобразования Фурье также существуют в поле Галуа. Циклические коды, использующие преобразование Фурье, могут быть описаны в настройке, более близкой к обработке сигнала.
Преобразование Фурье над конечными полями
Преобразование Фурье над конечными полями
Дискретное преобразование Фурье вектора задается вектором где,
знак равно где,
где exp () является й корень единства. Аналогично в конечном полекорень 1-й степени из единицы - это элемент порядка . Следовательно
Если вектор над , а также быть элементом порядка , то преобразование Фурье вектора это вектор и компоненты представлены
знак равно где,
Здесь - временной индекс,это частота иэто спектр . Одним из важных различий между преобразованием Фурье в комплексном поле и полем Галуа является то, что комплексное поле существует для каждого значения в то время как в поле Галуа существует только если разделяет . В случае полей расширения в поле расширения будет преобразование Фурье. если разделяет для некоторых . В векторе временной области в поле Галуа над полем но спектр может быть над полем расширения .
Спектральное описание циклических кодов
Любое кодовое слово циклического кода длины блока можно представить полиномом степени не более . Его кодировщик можно записать как. Следовательно, кодировщик частотной области может быть записан как. Здесь спектр кодовых слов имеет ценность в но все компоненты во временной области взяты из . Поскольку спектр данных произвольно, роль состоит в том, чтобы указать те где будет ноль.
Таким образом, циклические коды также можно определить как
Учитывая набор спектральных индексов, , элементы которого называются контрольными частотами, циклический код набор слов закончился спектр которого равен нулю в компонентах, индексированных . Любой такой спектр будет иметь компоненты формы .
Итак, циклические коды - это векторы в поле а спектр, задаваемый его обратным преобразованием Фурье, находится над полем и ограничены равными нулю на определенных компонентах. Но каждый спектр в этой области и нуль на некоторых компонентах может не иметь обратных преобразований с компонентами в поле . Такой спектр нельзя использовать в качестве циклических кодов.
Ниже приведены некоторые оценки спектра циклических кодов.
BCH привязан
Если быть фактором для некоторых . Единственный вектор в веса или меньше, что равные нулю последовательные компоненты его спектра - это все-нулевой вектор.
Граница Хартмана-Ценга
Если быть фактором для некоторых , а также целое число, взаимно простое с . Единственный вектор в веса или менее, чьи спектральные компоненты равен нулю для , где а также , - нулевой вектор.
Roos связаны
Если быть фактором для некоторых а также . Единственный вектор в веса или менее, чьи спектральные компоненты равно нулю для , где а также занимает по крайней мере значения в диапазоне , - вектор с нулевыми значениями.
Квадратичные вычетные коды
Когда премьер является квадратичным вычетом по простому модулю существует код квадратичного остатка, который является циклическим кодом длины, измерение и минимальный вес не менее над .
Обобщения
Констациклические коды представляют собой линейный код с тем свойством , что для некоторых постоянная Л , если ( гр 1 , C 2 , ..., гр п ) является кодовым словом , то так есть (λ с п , с 1 , ..., гр п -1 ). Negacyclic код является кодом с констациклическим λ = -1. [8] квази-циклический код имеет свойство , что для некоторых х , любой циклический сдвиг кодового слова на з местах снова является кодовым словом. [9] двойной циркулянт код является квази-циклическим кодом четной длины с й = 2. [9]
Смотрите также
- Циклическая проверка избыточности
- Код BCH
- Код Рида – Мюллера
- Двоичный код Голея
- Тернарный код Голея
- Юджин Прейндж
Заметки
- ^ Ван Линт 1998 , стр. 76
- ^ Ван Линт 1998 , стр. 80
- ^ Hill 1988 , стр. 159-160
- ^ Blahut 1983 , теорема 5.5.1
- Перейти ↑ Hill 1988 , pp. 162-163
- ↑ P. Fire, E, P. (1959). Класс двоичных кодов с многократным исправлением ошибок для независимых ошибок. Лаборатория разведывательных систем «Сильвания», Маунтин-Вью, Калифорния, Репт. РГБ-Э-2, 1959.
- ↑ Вэй Чжоу, Шу Линь, Халед Абдель-Гаффар. Пакетное или случайное исправление ошибок на основе кодов Fire и BCH. ITA 2014: 1–5 2013.
- ^ Ван Линт 1998 , стр. 75
- ^ a b MacWilliams & Sloane 1977 , стр. 506
Рекомендации
- Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press , ISBN 0-521-55374-1
- Хилл, Раймонд (1988), Первый курс теории кодирования , Oxford University Press , ISBN 0-19-853803-0
- MacWilliams, FJ ; Sloane, NJA (1977), Теория кодов с исправлением ошибок , Нью-Йорк: Издательство Северной Голландии, 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 , EE 387.
- Конспект Джонатана Холла (МГУ) - Глава 8. Циклические коды - стр. 100 - 123
- Дэвид Терр. «Циклический код» . MathWorld .
Эта статья включает материал из циклического кода на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .