Системы передачи информации

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

Чтобы полученный результат  был понятнее, напомним, что умножению  некоторого двоичного полинома на соответствует сдвиг двоичной последовательности т = (т₀, m₁...m_k-1) на п-к разрядов вправо.

Итак, циклический (п,к)-код k-разрядной информационной последовательности т = (m₀, m₁…m_k-1) получают следующим образом:

-    информационную последовательность т умножают на х^n-k ,то есть сдвигают вправо на п-k разрядов:

-     полином полученной последовательности делят на порождающий полином кода g(x);

-    полученный остаток от деления на g(x) прибавляют к , то есть записывают в младших п-к разрядах кода.

Алгоритм кодирования, основанный на делении полиномов, можно  реализовать, используя схему деления. Она представляет собой регистр  сдвига, в котором цепи обратной связи замкнуты в соответствии с  коэффициентами порождающего полинома g(x) .

Кодирование выполняется следующим образом:

• k символов информационной последовательности т через переключатель , находящийся в верхнем положении, один за другим передаются в канал и одновременно с этим через открытую схему записываются в регистр проверочных символов, в котором благодаря наличию цепей обратной связи g₀... g_n-k-1 формируется остаток от деления на g(x) — проверочные символы;
• начиная с (к+1)-го такта переключатель переводится в нижнее положение, и из сдвигового регистра выводятся (п-к) проверочных символов: цепь обратной связи при этом разомкнута.

Еще одним важным свойством циклического (п,к)-кода, вытекающим из теоремы о существовании циклических кодов, является то, что его порождающий полином делит без остатка двучлен хⁿ +1, то есть

xⁿ+1=g(x) h(x) + 0.

Полином h(x) — частное от деления хⁿ +1 на g(x) - называется проверочным полиномом.

Поскольку h(x) однозначно связан с g(x), он также определяет код. Следовательно, с помощью проверочного полинома h(x) тоже можно производить кодирование.

 

2. Разработка структурной схемы СПИ

 

2.1 Делитель кодера.

 

Для построения кодирующего устройства циклического кода необходимо выполнить две процедуры: умножить многочлен Q(x) на x^r и полученное произведение разделить на образующий полином P(x) по модулю P(x). Для проведения первой операции не требуется специального устройства, так как умножение многочлена на x^r  означает добавление к нему r нулевой со стороны младшего разряда, т.е. после передачи k информационных элементов за ними следуют r проверочных. Реализация процедуры циклического кодирования программными методами требует больших затрат  машинного времени. Так при делении 32-х разрядного слова на 16-ти разрядное центральный процессор серии КР580 затрачивает время около 2.5 мс. В то же время схемотехнические кодеры и декодеры циклических кодов отличаются малыми аппаратурными затратами и способностью работать в реальном времени. Поэтому в современных программируемых УЗО и различных адаптерах связи циклическое кодирование и декодирование реализуется схемно.

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

Ячейка  регистра для старшей степени исключается, но всегда присутствует триггер, соответствующий  нулевой степени x⁰. Число сумматоров по модулю 2 в регистре должно быть на единицу меньше ненулевых членов выражения P(x). Сумматоры располагают перед ячейками регистра, соответствующими ненулевым членам образующего полинома. На первые входы сумматоров подаются сигналы с предыдущих ячеек регистра, а на вторые - с выхода делителя. Очевидно, нет необходимости ставить сумматор перед ячейкой x⁰.

Построим делитель кодера по вышеуказанным правилам для соответствующего варианта:

Полином: 110101001     

Рисунок 1 - Делитель кодера

 

Для дальнейшей проверки  правильности работы делителя кодера нам необходимо получить остаток. Это можно сделать с помощью деления варианта в двоичной системе счисления с добавленными контрольными разрядами на образующий полином:

  111000111100000000  110101001

110101001

   110111010

   110101001

             100110000  

             110101001

              100110010

               110101001

                 100110110

                 110101001

                   100111110

                   110101001

                     10010111

Образующая (порождающая) матрица составляется дописыванием элементов дополнительной матрицы справа от единичной транспонированной матрицы либо умножением элементов единичной матрицы на образующий многочлен. Определение элементов дополнительной матрицы производится по остаткам от деления последней строки транспонированной матрицы (единицы с нулями) на образующий многочлен

Порождающая матрица  С может быть представлена двумя  матрицами И и П (информационная и проверочная). Число столбцов матрицы П равно n_K, число столбцов матрицы И равно n_M(числом информационных разрядов и числом корректирующих разрядов ):

.         (23)

 

      

Теорией и практикой  установлено, что в качестве матрицы удобно брать обратную единичную матрицу в канонической формуле:

                                   .

 

порождающую матрицу  можно привести к следующему виду:

                        …        …    , называемому левой канонической формой порождающей матрицы.

Построим образующую (порождающая) матрицу в соответствии с заданным вариантом и заданием. Для этого произведём деление:

100000000000000000  110101001

110101001

  101010010

  110101001  

    111110110       

    110101001

      0101111100          

        110101001            

          110101010      

          110101001         

            000000110000

                           

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

1. 10101001
2. 11111011
3. 01011111
4. 10111110
5. 11010101
6. 00000011 
7. 00000110
8. 00001100
9. 00011000
10. 00110000 

Имея все необходимые  данные, можем построить образующую матрицу:

 

где правая матрица-столбец – вариант в двоичной системе счисления, записанный снизу вверх.

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

                                                 

 

Проверка показала, что образующая матрица построена  верно. В результате сложения по модулю 2 строк матрицы мы получили заданный вариант и нужный остаток.

По полученной схеме (1) составим уравнения переходов:

 

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

Таблица 1 -  Таблица  переходов кодера.

Такты	xвх	x0	x1	x2	x3	x4	x5	x6	x7	xвых
0	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	1	0	1	0	1	0
2	1	0	1	0	0	1	0	1	0	1
3	1	1	0	1	1	0	0	0	0	0
4	0	0	1	0	1	1	0	0	0	0
5	0	0	0	1	0	1	1	0	0	0
6	0	0	0	0	1	0	1	1	0	0
7	1	1	0	0	1	1	1	1	0	0
8	1	1	1	0	1	1	0	1	0	0
9	1	1	1	1	1	1	0	0	0	0
10	1	1	1	1	0	1	0	0	1	0
11			1	1	1	0	1	0	0	1
12				1	1	1	0	1	0	0
13					1	1	1	0	1	0
14						1	1	1	0	1
15							1	1	1	0
16								1	1	1
17									1	1
18										1

 

Для проверки схемы делителя кодера, мы подключаем к нему светодиоды и генератор. Как видно из рисунка 3.1, схема делителя кодера построена верно, т.е. на светодиодах отражается полученный нами остаток.

На базе построенной схемы делителя кодера, предварительно убедившись в её правильной работе, мы можем построить и саму схему декодирующего устройства.

Данная схема  представлена в приложении А.

 

2.2 Делитель декодера.

Основу декодирующих устройств циклических кодов  также составляют делители многочленов  на образующий полином. Признаком наличия  ошибок принятой последовательности является ненулевой остаток от деления этой последовательности на Р(х). До завершения процесса деления необходимо запомнить поступивший блок в буферном накопителе. После окончания цикла производится опрос делителя, и в случае ошибки принятый блок стирается. При нулевом остатке блок выводится получателю через ключевой элемент КЛ, а на его место записывается следующее. Структурная схема декодера изображена на рисунке 2. 

В процессе приема распределитель УУ вырабатывает управляющие  импульсы таким образом, что в  буферный регистр заносятся только информационные символы, а на делитель подаются все элементы, которые участвовали в процессе деления в кодере, а также проверочная последовательность R(x).

 

 

 

 

 

 

Рисунок 2– Структурная схема декодера циклического кода

 

Для построения самого декодирующего устройства, как  и в первом случае, нам сначала  необходимо построить делитель декодера, а потом на его основе строить  сам декодер.

 

 

На рисунке 3 изображена схема делителя декодера в соответствии с вариантом.

Рисунок 3 - Делитель декодера

 

При установке  в генератор делителя декодера остатка 10010111, делитель должен установиться в ноль. Это можно проверить следующим способом:

111000111110010111     110101001

110101001

   110111011

    110101001

             100100010

            110101001  

               100010111

               110101001

                 101111101

                 110101001

                   110101001

                  110101001

                   000000000

Вышеуказанное деление подтверждает правильность работы делителя декодера. Так же как и  в первом случае по полученной схеме записываем уравнения переходов и строим таблицу переходов для данной схемы:

По таблице 2. видно, что  при установке в генератор делителя декодера остатка 10010111, делитель устанавливается в ноль:

Таблица 2 –  Таблица переходов декодера

Такты	xвх	x0	x1	x2	x3	x4	x5	x6	x7	xвых
0	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0
2	1	1	1	0	0	0	0	0	0	0
3	1	1	1	1	0	0	0	0	0	0
4	0	0	1	1	1	0	0	0	0	0
5	0	0	0	1	1	1	0	0	0	0
6	0	0	0	0	1	1	1	0	0	0
7	1	1	0	0	0	1	1	1	0	0
8	1	1	1	0	0	0	1	1	1	0
9	1	0	1	1	1	0	1	1	0	1
10	1	1	0	1	1	1	0	1	1	0
11	1	0	1	0	0	1	0	0	0	1
12	0	0	0	1	0	0	1	0	0	0
13	0	0	0	0	1	0	0	1	0	0
14	1	1	0	0	0	1	0	0	1	0
15	0	1	1	0	1	0	0	0	1	1
16	1	0	1	1	1	1	1	0	1	1
17	1	0	0	1	0	1	0	1	1	1
18	1	0	0	0	0	0	0	0	0	1