У вас вопросы?
У нас ответы:) SamZan.net

Докажем в начале- идеал в алгебре многочленов по mod fx xn1 ~ циклический код

Работа добавлена на сайт samzan.net: 2015-07-10

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 3.4.2025

Циклические коды.

Циклическим кодом называется линейный n,k код, обладающий следующим свойством:

Если - вектор кода, то  – вектор кода.

   (циклический     сдвиг).        Обратите     внимание    на     нумерацию   от     до .

Теорема. Циклический код есть идеал в алгебре многочленов по модулю многочлена f(x)=xn+1.

  1.  Докажем в начале: идеал в алгебре многочленов по

mod f(x)= xn+1 – циклический код.

а) Линейный код – векторное подпространство векторного пространства всех последовательностей длины n.

Идеал так же векторное подпространство векторного пространства всех последовательностей длины n.

Отсюда   Идеал – линейный код.

б) Далее:пусть  принадлежит идеалу J.

Тогда    по определению идеала.

Но .

Откуда , т.е. циклический сдвиг принадлежит идеалу, ч.т.д.

  1.  Докажем обратное утверждение – циклический код – идеал.

Пусть  - вектор кода. Тогда  - вектор кода как его циклический сдвиг.

Следовательно  - вектор кода, i=0,2,…,n-1.

Далее,  пусть в(x)   –   вектор   из   кольца   многочленов  по

mod f(x)= =xn+1.   

Тогда

В правой части – линейная комбинация векторов, т.е. вектор кода. Отсюда . Следовательно, циклический код – идеал.

Задание циклического кода.

f(x)= xn+1;          

                     

                                                степень n-k     степень k

Порождающая матрица несистематического

циклического кода.

      g(x)                   Пример:  

G=  xg(x)       ;          

      ……. g(x) h(x)

      xk-1g(x)

                                                                

                    1   0   1    1   0   0   0      

G=       ;    G=   0   1   0    1   1   0   0   ;  ),

                      0   0   1    0   1   1   0                  

                      0   0   0    1   0   1   1  

                                                                                 

  

Проверочная матрица.

      h(x)                                     Для условий примера:

H=  xh(x)       ;                             

      …….  

      xn-k-1h(x)

                       0   0   1   1   1   0   1

H=      ;     H=  0   1   1    1   0   1  0

                     1   1   1    0   1   0  0 7,4 код

 Хэмминга

c  dmin=3

Задание несистематического

циклического кода многочленом g(x).

Вектор кода V(x);

Выводы:

  1.  Кодер несистематического циклического кода – схема умножения многочленов.
  2.  V(x) принадлежит коду, если делится на g(x) (без остатка). Декодер в режиме обнаружения ошибок – схема деления V(x) на g(x).

Пример:

          a(x)=x

0    1   0   0

                0  1 0  1  1  0 0

Получение порождающей матрицы

систематического циклического n,k кода.

   степень n-k     степень k

                         К равенств

………………………………………………………….

                    i=0,1,…,k-1

       k  векторов.   Степень r(x) меньше n-k.

Поэтому:   вектора

 i=0,1,…,k-1

-  линейно независимые (К векторов)

Так как , т.е. делится на g(x), то

 - вектор кода

 i=0,1,…,k-1.

K линейно независимых векторов кода – его базис. Отсюда порождающая матрица:

                                         Здесь

 G=                             -

          ……………………………..                         остаток от

                                    деления

          …………………………….                           на g(x);

                                            i=0,1,…,k-1.

Пример:    


                      

1

3

                                                    

                                               

   1                        

                                                                  

  

2

4

                                      

                   

   x+1                                                

                                         

   

                

 

         

        

        

        

G=    1   0   1    1   0   0   0   ;

        1   1   1    0   1   0   0

        1   1   0    0   0   1   0

        0   1   1    0   0   0   1

             P                Jk

Получение алгоритма задания систематического

циклического кода.

.

В соответствии с алгоритмом Евклида R(x) – остаток от деления  на g(x);

V(x)=g(x)d(x);

что такое R(x)-???

Степень R(x) меньше степени n-k;              

Алгоритм задания систематического

циклического кода.

  1.  Умножаем a(x) на  и запоминаем.
  2.  Определяем остаток от деления на g(x), т.е. определяем R(x).
  3.  Получаем вектор кода

так как степень R(x) меньше степени g(x) – степень n-k, то это сложение просто приписывается.

Пример:  

0    1   0   1               a(x)=x+x3

2

1

     Делим  на g(x):

    

                            V(x)=a(x)x3+R(x)=x6+x4+1

                     1 = R(x)              
                                                      1   0    0   0   1   0   1

                                                      

                                          проверочные     информационные

  




1. так больно Но ведь и хорошего в уходящем году тоже было немало1
2. Статья 91 Понятие рабочего времени
3. экономического чуда
4. Описати теорію розрахунку числа точок перехрещень.html
5. Введение для изучающих психологию Петер Шульц Католический университет г
6. govu-www-new-html-ukr-min Переклад- Галина Заворітня Загальна редакція- Тарас Качка Літературна редакція- Оль
7. на тему- rdquo;Философия Аристотеля ldquo; Студент Светлана Александровна Конон
8. Сахар
9. Психология риска
10. .Explin the influence of ech of the following events on the quntity of rel GDP supplied nd ggregte supply in Indi nd use grph to illustrte