Изучение и исследование групповых (циклических) кодов

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра радиотехники и

радиотелекоммуникационных систем

ОТЧЕТ

ПО ЛАБОРАТОРНОЙ РАБОТЕ № 2

по дисциплине

«Системы связи и основы телекоммуникации»

Изучение и исследование групповых (циклических) кодов

Выполнил:

курсант группы Ро-431 Курепина Е.Р.

Принял: руководитель канд. техн. наук,

доцент Л.Ф. Борисова

Мурманск

2017



Введение

Цель работы

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

Задание

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

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

Проанализировать вариант задания (вариант задается преподавателем).

Заданную кодовую комбинацию примитивного кода Q(x) (вариант задается преподавателем) представьте в двоичном коде.

Выберите образующий полином P(x) в соответствии с вариантом задания (вариант задается преподавателем). Сформируйте КК циклического кода, используя полученную ранее 11-ти разрядную комбинацию примитивного кода. Проверьте, является ли найденная КК разрешенной.

Найдите синдром циклического кода для заданной одиночной ошибки (вариант задается преподавателем).

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

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

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

вероятность правильного приема КК для случая приема с исправлением ошибок, Pпр;

вероятность появления не обнаруживаемых ошибок для случая приема с обнаружением ошибок, Pно;

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

Оформите отчет о проделанной работе в соответствии с общими требованиями.

Исходные данные:

Комбинация примитивного кода Q(x)=834

Полином P(x)=x4+x3+1

Номер искаженного разряда N=2

Вероятность ошибки на нулевой элемент P0=3*10-3

декодирование циклический синдром матрица

Пояснительная записка

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

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

Свое название циклические коды получили из-за ряда специфических свойств:

циклический сдвиг разрешенной КК дает также разрешенную КК;

деление разрешенной КК на некоторый полином (многочлен), называемый образующим (порождающим), дает нулевой остаток.

Примитивные коды

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

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

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

Количество кодовых комбинаций для кода равно N=kn, где k-основание кода, а n-длина кодового слова.

Избыточный код

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

Параметры избыточного кода:

Длина кода n - это число символов в кодовой комбинации. кодах длина кодовых комбинаций может быть разной.

Основание кода m - это число различных символов в коде.

Число кодовых комбинаций для равномерного кода равно N=mn.

Число разрешенных кодовых комбинаций Nр - это количество кодовых комбинаций кода, используемых для передачи сообщений. Для помехоустойчивых кодов Nр<N. Оставшиеся кодовые комбинации N-Nр называют запрещенными. Если Nр=N, то код является без избыточным. Для разделимых кодов Nр=2 k.

Избыточность кода Ки показывает, какая доля длины кодовой комбинации используется для повышения помехоустойчивости кода, а не передачи информации. Для разделимых кодов: , где величина k/n называется относительной скоростью кода.

Минимальное кодовое расстояние dmin - это минимальное расстояние между разрешенными кодовыми комбинациями данного кода.

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

Расстояние Хемминга

Расстояние Хемминга - характеризует степень различия кодовых комбинаций и определяется числом несовпадающих в них разрядов.

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d0.

Минимальное расстояние d0 - называется кодовым расстоянием

Кодовое расстояние определяет способность кода обнаруживать и исправлять ошибки.

У простого кода d0=1 - он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

Для того чтобы код обладал корректирующими способностями, его минимальное кодовое расстояние должно быть не менее двух (dmin 2).

Корректирующие свойства кода:

- гарантированное обнаружение ошибок,

- гарантированное исправление ошибок.

Корректирующие коды

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

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

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

На практике количество символов в блоке может быть в пределах от 3 до нескольких сотен. Блоки, содержащие k символов каждый, по определенному закону преобразуются кодером в n-символьные блоки, причем n k. Например, схема блочного кодера Каждый символ выходного блока информации получается как сумма по модулю 2 нескольких символов входного блока, для чего используются n сумматоров по модулю 2. Совокупность всех возможных кодовых комбинаций при блочном способе кодирования, и есть блочный код.

Схема блочного кодера

Классификация корректирующих кодов

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

Наиболее многочисленный класс разделимых кодов составляют линейные коды.

Линейные коды также называют групповыми.

Двоичный блочный код является групповым (линейным) если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

1. Замкнутость gig j= gk G в результате операции с двумя элементами группы получается третий, так же принадлежащий этой группе.

2. Ассоциативность (сочетательность) (gigj) gk = gi (gj gk)

3. Наличие нейтрального элемента gj e = gj

4. Наличие обратного элемента. gi (gi)-1= e

Если выполняется условие gi gj = gj gi, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

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

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

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

Синдром циклического кода

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

Запрещенная комбинация - комбинация, запрещенная для использования.

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

Исправление однократной ошибки может производиться по упрощённому алгоритму: f(x) = F(x)+E(x), где f(x) - принятая КК, F(x) - переданная КК и E(x) - полином ошибок. Таким образом, единицы в многочлене E(x) указывают на разряды, поражённые ошибкой. Синдром не зависит от переданной кодовой комбинации, но в нем сосредоточена вся информация о наличии ошибок. Обнаружение и исправление ошибок в систематических кодах может производиться только на основе анализа синдрома.

Ход работы

Комбинация примитивного кода: Q(x)=834=1101000010,

Образующий полином: P(x)=x4+x3+1=11001

Степень образующего полинома P(x) равна 4. Умножим Q(x) на x4, что равноценно сдвигу КК простого кода на 4 разряда влево. Разделим полученное произведение на P(x):

,

где A(x) - частное, полином степени не более (к-1);

R(x)-остаток от деления, полином степени не более (r-1).



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

Анализ полученного выражения позволяет вывести способ построения разрешённых кодовых комбинаций циклического кода:

Исходная кодовая комбинация первичного кода Q(x) умножается на , и полученное произведение делится на P(x). Остаток от деления - R(x) складывается по модулю 2 с произведением. В этом случае в КК циклического кода к старших разрядов будут информационными (т.е. КК исходного, примитивного кода), а r последующих разрядов - проверочными (остаток R (х) ).

Свойства циклических кодов в полном объёме определяются видом образующего полинома.

При делении получим:

Таким образом, A(x) =100100010, R(x) = 0100.

Тогда кодовая комбинация циклического кода будет следующая:

F(x)=11010000100100

Проверим, является ли полученная КК разрешенной:

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

R(x) = 0, т. е. кодовая комбинация является разрешенной.

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

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

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

1 способ В качестве первой строки берётся образующий полином Р(х), к которому слева приписывается необходимое число нулей так, чтобы длина строки стала равной п. Остальные k-1 строк получаются циклическим сдвигом первой строки.

n=k+r

r - проверочных разрядов в КК (r=4);

к - число информационных разрядов в КК(k=9);

n=9+4=13

Составим образующую матрицу данного циклического кода.

2 способ В качестве информационной части берётся единичная матрица размером 9х9. К каждой строке единичной матрицы приписывается справа 4 нуля. Полученное произведение делится на образующий полином P(x) и остаток от деления складывается по модулю 2 с произведением.

Находим первую строку проверочной части матрицы:

Делим полученную КК на образующий полином и находим остаток от деленияR1(x).



Так же определяются оставшиеся строки, образующие проверочную матрицу:

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

Этот способ дает образующую матрицу в канонической форме.

Анализ строк порождающей матрицы позволяет определить минимальное кодовое расстояние для данного кода. Минимальный вес строки составляет 3, следовательно, d0 = 3.

Имея образующую матрицу в каноническом виде - G13,9 построим проверочную матрицу в каноническом виде

Проверочная матрица Hn,r имеет 13 столбцов и 4 строки. Проверочная матрица получается из порождающей матрицы, записанной в канонической форме - проверочная часть порождающей матрицы транспонируется и к ней справа приписывается единичная матрица 4х4.



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

Найдем необходимые параметры из следующих соотношений:

Кратность гарантированно обнаруживаемых ошибок:

Кратность гарантированно исправляемых ошибок: =>tu=1

3) Относительная избыточность:

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

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

Если , то считается, что КК принята правильно, в противном случае считается, что произошла ошибка.

Обобщённый алгоритм исправления ошибок кратности не более состоит в следующем:

Принятая КК делится на образующий полином. Подсчитывается вес остатка (количество единиц).

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

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

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

Исправленная КК получается в результате сдвига вправо суммы по модулю 2 последней КК и последнего остатка () на столько разрядов, на сколько была сдвинута принятая КК влево.

Исправление однократной ошибки может производиться по упрощенному алгоритму. Можно записать:

,

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

Передается разрешенная КК:

F(x)=11010000100100

Ошибка произошла в 7-м разряде информационной части, тогда принятая КК имеет вид: 11110000100000

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



Остаток R(x)=1101 указывает на ошибку в 2-м разряде.

Исправление ошибки

= F(x)E(x);

где F(x) - принятая КК, F(x) - переданная КК и E(x) - полином ошибок. Таким образом, единицы в многочлене E(x) указывают на разряды, поражённые ошибкой. Следовательно, при однократной ошибке в E(x) будет только одна 1.

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

Вероятность правильного приёма Pпр

Вероятность приёма КК без ошибок Pбо

Вероятность приёма КК с обнаруживаемыми ошибками Pоо

Вероятность приёма КК с ошибками, которые исправляются данным кодом Pио

Вероятность приёма КК с необнаруживаемыми ошибками Pно

Расчет вероятностей с помощи программы МathCAD



Список использованной литературы

1. Шувалов В. П., Захарченко Н. В. Передача дискретных сообщений: учебник для вузов/ Шувалов В. П., Захарченко Н. В. -М.: Радио и связь, 1990. -464 с.:ил.

2. Шинаков Ю. С., Колодяжный Ю. М. Теория передачи сигналов электросвязи: учебник для техникумов.-М.: Радио и связь, 1989. -288 с.:ил.

3. Коды в системах телемеханики. Классификация и характеристики кодов: [Электронный ресурс] // http://vse-lekcii.ru/zheleznodorozhnyj-transport/ats/kody

4. Лекции по Теории передачи сигналов: [Электронный ресурс] // http://siblec.ru/index.php?dn=html&way=bW9kL2h0bWwvY29udGVudC84c2VtLzA4OS83LTEuaHRt

5. Защита от ошибок в системах связи: [Электронный ресурс] // http://siblec.ru/index.php?dn=html&way=bW9kL2h0bWwvY29udGVudC82c2VtL2NvdXJzZTk1L2xlYzUuaHRt

Размещено на Allbest.ru