5. Содержание работы

1.Ознакомиться с принципами кодирования и декодирования при использовании циклических кодов.

2.Освоить методы полиномиального и матричного построения циклических кодов.

3.Исследовать свойства циклических кодов и образующих полиномов данных кодов.

6. Содержание отчёта

Отчёт должен содержать:

1. Цель работы.

2. Структурную схему системы передачи дискретных сообщений.

3. Результаты выполнения заданий п.п. 4 - 7 раздела "Подготовка к работе".

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

5. Необходимые выводы о корректирующих свойствах циклических кодов.

7. Методические указания по выполнению работы

1. Получить разрешение на выполнение лабораторной работы и на включение компьютера.

2. Запустить файл cyclcodl.exe и зарегистрироваться в компьютере.

3. В появившемся после регистрации меню выбрать раздел "Введение" и ознакомиться с его содержанием. Этот раздел содержит правила и указания по работе с программой CYCLCOD . Затем выйти из меню раздела "Введение", выбрав пункт "Выход из данного меню".

4. Выбрать раздел "Краткая теория" в главном меню. Ознакомиться с его содержанием.

3. Получить допуск к выполнению работы, для чего выбрать раздел "Опросная часть'''' в главном меню и ответить на предложенные компьютером вопросы.

3. После успешного прохождения опросной части войти в экспериментальную часть программы. Пронаблюдать процесс кодирования и декодирования кодовых комбинаций. Пронаблюдать прохождение кодовой комбинации циклического кода по системе ПДС в двух режимах: передача без ошибок и передача с исправлением одиночной ошибки.

При необходимости повторить эксперименты при разных входных данных. Результаты работы записывать по мере её выполнения.

7. После окончания работы с экспериментальной частью выйти в главное меню. Выйти из программы.

8. Оформить отчёт и сделать необходимые выводы.

7. Общие сведения

Рисунок 1 - Структурная схема системы передачи дискретных сообщений

ИПС - источник / получатель сообщений - преобразует информацию пользователя в сообщение, алфавит которого понятен и источнику, и получателю.

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

УЗО - устройство защиты от ошибок - обеспечивает реализацию методов повышения верности передачи. Существует два принципиально различных способа повышения верности:

• верность передачи повышается путём введения избыточности на основе априорных сведений о состоянии дискретного канала (т. е. мы не знаем реального состояния канала в данный момент) - это помехоустойчивое кодирование (наибольшее распространение получили циклический и матричный коды);

• повышение верности обеспечивается введением избыточности на основе сведений о реальном (текущем) состоянии дискретного канала - это алгоритмы систем с решающей обратной связью (обратная связь необходима потому, что избыточность вносится на передаче, а состояние канала можно оценить только на приёме) РОС - ОЖ, РОС - НП, РОС - АП.

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

Вид преобразований полностью определяется видом канала:

♦ для непрерывного канала - модуляция,

♦ для физической пары - специальное кодирование (например, манчестерское).

КС • канал связи.

Принципы построения циклического кода:

Из всех разновидностей систематических кодов циклические коды получили наибольшее распространение в технике ПДС.

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

Название циклических кодов происходит от их основного свойства:

циклический сдвиг элементов разрешённой кодовой комбинации также образует разрешённую кодовую комбинацию.

Таким образом, если кодовая комбинация является разрешённой, то комбинации

и т. д., полученные циклической перестановкой элементов исходной кодовой комбинации, также принадлежат к числу разрешённых.

Такая циклическая перестановка при использовании представления в виде полиномов появляется в результате умножения данного исходного полинома на х.

Если

TO

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

Отсюда

Например, имеем кодовую комбинацию 0110010 х⁵ + х⁴ + х.

Сдвинем её на один разряд. Получим 1100100 х⁶ + х⁵ + х². Очевидно, что х⁶ + х⁵ + х² = .

Теория построения циклических кодов базируется на разделах высшей алгебры, изучающей свойства многочленов, состоящих из дискретных элементов (двоичных многочленов) / 4 /.

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

Такой многочлен делится только на самого себя и на единицу.

Из высшей алгебры известно, что на неприводимый многочлен

делится нацело (т. е. без остатка) двучлен xⁿ +1.

Рассмотрим принцип построения циклических кодов.

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

Таким образом, можно ввести в рассмотрение:

многочлен Q (х) степени к-1, отображающий k-элементную комбинацию первичного кода, и многочлен R (х) степени г-1, отображающий комбинацию проверочных элементов.

Построение разрешённой кодовой комбинации сводится к следующему:

1. Представляем информационную часть кодовой комбинации длиной k разрядов в виде полинома Q (х).

2. Умножаем Q (х) на одночлен х^г и получаем Q (х) х^г. (В двоичной форме записи операция умножения на х^г эквивалентна приписыванию справа r нулей.).

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

3. Делим многочлен Q (х) х^r на образующий полином Р(х), степень которого равна r.

В результате умножения Q (х) на х^r степень каждого одночлена, входящего в Q (х), повышается на r.

При делении произведения Q (х) х^r на образующий полином Р (х) степени r получается частное С (х) такой же степени, что и Q (x). Результаты этих операций можно представить в виде

где R (х) - остаток от деления Q (х) х^r на Р (х).

Поскольку С(х) имеет такую же степень, что и Q(х), то С(х) представляет собой кодовую комбинацию того же k-разрядного кода.

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

Наивысшая степень остатка равна r-1.

Следовательно, наибольшее число разрядов остатка не превышает r.

Умножив обе части (1) на Р (х), получим

или

F(x) = С(х)Р(х) = Q(x)x^r R(x). (2)

Знак вычитания в этом соотношении заменяется знаком сложения по модулю 2, так как вычитание по модулю 2 полностью совпадает со сложением.

Очевидно, что F (х) делится на Р (х) без остатка.

Следовательно, полином F(х) представляет собой разрешённою кодовую комбинацию циклического кода.

Согласно формуле (2) разрешённая кодовая комбинация циклического кода может быть получена двумя способами:

1) умножением кодовой комбинации простого кода С(х) на образующий полином Р (х);

2) умножением кодовой комбинации Q(х) простого (первичного) кода на одночлен х^г и добавлением к этому произведению остатка R(х). получившегося в результате деления произведения Q(х)х^г на образующий полином Р (х).

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

Неразделимость значительно усложняет практическую реализацию процесса декодирования.

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

Этот способ кодирования широко применяется на практике.

Поясним рассмотренные выше способы на примере.

Пусть циклическим кодом кодируются кодовые комбинации

пятиэлементного (к = 5) первичного кода, например, кодовая комбинация 10000= Q (х) = х⁴.

Требуется построить комбинацию циклического кода, исправляющего однократные ошибки (d_Q = 3).

Определим количество проверочных элементов г. Этому условию удовлетворяет г = 4.

Возьмём в качестве образующего многочлен Р (х) = х⁴ + х + 1.

1) Умножаем Q (х) .на х^г (г = 4):

Q (х) х^г = Q (х) х⁴ = х⁴ х⁴ = х⁸ - 100000000;

2 ) Делим Q (х) х^г на Р (х):

Остаток от деления

Знак ге [ ] означает остаток, получающийся от деления, указанного в квадратных скобках.

3) Получаем многочлен комбинации циклического кода

F (х) = Q (х) х^г R (х) = х⁸ + х² + 1.

Этот полином соответствует кодовой комбинации циклического кода

Все указанные операции можно производить и над двоичными числами:

Т о есть 10011

10011=С(х)

00011000 10011

3)

Построим теперь разрешённую кодовую комбинацию первым способом, т.е. используя операцию умножения полинома отображающего кодовую комбинацию первичного кода, на образующий полином Р(х): F(x)=C(x) P(x).

Для рассматриваемого примера

F (x) = x⁴ (x⁴ + x + l) = x⁸ + x⁵ + x⁴ = 100110000. Произведём умножение, представляя полиномы двоичными числами:

_×

00000

00000

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

Обнаружение ошибок при циклическом кодировании

В результате воздействия помех в канале принятая последовательность кодовых элементов может отличаться от переданной, т. е. кодовый многочлен F (х) преобразуется в мчогочлен Н(х):

Н (х) = F (х) Е (х), (3)

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

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

Принадлежность кодовой комбинации к разрешённой или запрещённой определяется по наличию или отсутствию остатка от данного деления.

Если ошибок в принятой кодовой комбинации нет, то в результате деления принятой кодовой комбинации на образующий полином получим нулевой остаток (остаток R(х) = 0).

Если при делении получится остаток (R (х) 0), то это свидетельствует о наличии ошибок в принятой кодовой комбинации.

Следовательно, многочлен R (х) в циклических кодах играет роль синдрома.

Пусть, например, передана следующая кодовая комбинация:

100000101 = F (х) = х⁸ + х² + 1,

а образующий полином Р (х) = х⁴ + х + 1 = 10011.

В информационной части этой комбинации произошла ошибка, и она принята как

101000101 = Н (х) = х⁸ + х⁶ + х² + 1.

Сложив по модулю 2 вектора переданной и принятой кодовой комбинации, получим вектор ошибки и соответствующий ему многочлен ошибки Е (х).

1 0 0 0 0 0 1 0 1 = F (х) = х⁸ + х² + 1 Передано

1 0 1 0 0 0 1 0 1 = Н (х)= х⁸ + х⁶ + х² + 1 П р и н я т о

001000000 = Е(х)= .

Так как F (х) делится на Р (х) без остатка, то, поделив обе части выражения (3) на Р (х), получим

Произведём операцию обнаружения ошибки.

для данного примера получим re =х³ + х² = 1100

или

101000101 10011

10010101

10011

11100

10011

11111

10011

1100

Наличие остатка 1100= х³ + х² свидетельствует об ошибке, т. е. она обнаружена.