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

Cyclic code

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

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

Определение

Позволять быть линейный код через конечное поле (также называемый Поле Галуа) из длина блока п. называется циклический код если для каждого кодовое слово c=(c1,...,cп) из C, слово (cп,c1,...,cп-1) в полученный циклический сдвиг вправо компонентов снова является кодовым словом. Поскольку один циклический сдвиг вправо равен п - 1 циклический сдвиг влево, циклический код также может быть определен через циклический сдвиг влево. Следовательно, линейный код циклично именно тогда, когда оно инвариантно относительно всех циклических сдвигов.

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

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

Циклические коды могут быть связаны с идеалами в определенных кольцах. Позволять быть кольцо многочленов над конечным полем . Определите элементы циклического кода C с многочленами от р такой, что отображается в полином : умножение на Икс соответствует циклическому сдвигу. потом C является идеальный в р, и поэтому главный, поскольку р это кольцо главных идеалов. Идеал порождается единственным моническим элементом в C минимальной степени, порождающий полином грамм.[1]Это должно быть делителем . Отсюда следует, что каждый циклический код является полиномиальный код.Если образующий полином грамм имеет степень d тогда ранг кода C является .

В идемпотент из C это кодовое слово е такой, что е2 = е (то есть, е является идемпотентный элемент из C) и е является идентификатором кода, то есть е c = c для каждого кодового слова c. Если п и q находятся совмещать такое слово всегда существует и уникально;[2] это генератор кода.

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

Примеры

Например, если А= и п= 3, набор кодовых слов, содержащихся в циклическом коде, порожденном (1,1,0), в точности равен

.

Он соответствует идеалу в создано .

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

Идемпотент этого кода - многочлен , соответствующий кодовому слову (0,1,1).

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

Тривиальные примеры циклических кодов: Ап сам и код, содержащий только нулевое кодовое слово. Они соответствуют генераторам 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 () является й корень единства. Аналогично в конечном поле корень -й единица - это элемент порядка . Следовательно

Если вектор над , и быть элементом порядка , то преобразование Фурье вектора это вектор и компоненты представлены

= куда,

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

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

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

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

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

Итак, циклические коды - это векторы в поле а спектр, задаваемый его обратным преобразованием Фурье, находится над полем и ограничены равными нулю для определенных компонентов. Но каждый спектр в этой области и ноль на некоторых компонентах может не иметь обратных преобразований с компонентами в поле . Такой спектр нельзя использовать в качестве циклических кодов.

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

Привязка BCH

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

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

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

Roos связаны

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

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

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

Обобщения

А констациклический код является линейным кодом, обладающим тем свойством, что для некоторой постоянной λ, если (c1, c2,...,cп) - кодовое слово, то (λcп, c1,...,cп-1). А неациклический код является констациклическим кодом с λ = -1.[8] А квазициклический код обладает тем свойством, что для некоторых s, любой циклический сдвиг кодового слова на s мест снова является кодовым словом.[9] А двойной циркуляционный код является квазициклическим кодом четной длины с s=2.[9]

Смотрите также

Примечания

  1. ^ Ван Линт 1998, п. 76
  2. ^ Ван Линт 1998, п. 80
  3. ^ Хилл 1988, стр. 159-160
  4. ^ Блахут 1983, Теорема 5.5.1
  5. ^ Хилл 1988, стр. 162-163
  6. ^ П. Файер, Э, П. (1959). Класс двоичных кодов с множественными исправлениями ошибок для независимых ошибок. Лаборатория разведывательных систем «Сильвания», Маунтин-Вью, Калифорния, Репт. РГБ-Э-2, 1959.
  7. ^ Вэй Чжоу, Шу Линь, Халед Абдель-Гаффар. Пакетное или случайное исправление ошибок на основе кодов Fire и BCH. ITA 2014: 1–5 2013.
  8. ^ Ван Линт 1998, п. 75
  9. ^ а б МакУильямс и Слоан 1977, п. 506

Рекомендации

  • Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Издательство Кембриджского университета, ISBN 0-521-55374-1
  • Хилл, Раймонд (1988), Первый курс теории кодирования, Oxford University Press, ISBN 0-19-853803-0
  • Мак-Вильямс, Ф. Дж.; Слоан, Н. Дж. А. (1977), Теория кодов, исправляющих ошибки, Нью-Йорк: Издательство Северной Голландии, ISBN 0-444-85011-2
  • Ван Линт, Дж. Х. (1998), Введение в теорию кодирования, Тексты для выпускников по математике 86 (3-е изд.), Springer Verlag, ISBN 3-540-64133-5

дальнейшее чтение

внешняя ссылка

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