Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Порождающий многочлен циклического кода






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

    Многочлен хn-1 можно разложить на множители

     

    xn-1=(х-1) ∙ (хn-1n-2+…+1),

     

    следовательно, циклические коды существуют при любом n.

    Число циклических n-разрядных кодов равно числу делителей многочлена xn-1. Для построения циклических кодов разработана таблица разложения многочленов xn-1 на неприводимые многочлены, т.е. такие, которые делятся только на единицу и на самого себя. Неприводимые многочлены дают наибольшее число остатков при делении. Это свойство используется для обнаружения ошибки при депозировании.

    Рассмотрим, например, какие коды можно построить на основе многочлена х7+1 над полем GF(2).

     

    x7+1=(х+1)(х32+1)(х3+х+1).

     

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

    Код (n, k) определяется значениями n и k, где k=n- , а – степень многочлена g(x) – делителя х4-1, определяющего код.

    g1(x)=x+1, =1, k=6, код (7, 6)(1 разряд проверочный на четность)

    g2(x)=x3+x2+1, =3, k=4, код (7, 4)

    g3(x)=x3+x+1, =3, k=4, код (7, 4)

    g4(x)=(x+1)(x3+x2+1), =4, k=3, код (7, 3)

    g5(x)=(x+1)(x3+x+1), =4, k=3, код (7, 3)

    g6(x)=(x3+x2+1)(x3+x+1), =6, k=1, код (7, 1)

    При осуществлении операции циклической перестановки мы принимаем хn-1. Учитывая, что кодовые комбинации складываются по mod2, то хn+1=0 и хn-1=0, т.е. х 1=0 или хn+1=хn-1. С другой стороны, с учетом того, что порождающий полином делит полином хn-1, получим

     

    x4+1=g(x) ∙ h(x), и, соответственно

    g(x) ∙ h(x)=0.

     

    Полином h(x) называется проверочным полиномом. Произведение проверочного и порождающего полиномов равно h(x) ∙ g(x)=0. Это соотношение положено в основу декодирования циклических кодов.

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.