Кодирование и декодирование

Государственное образовательное учреждение высшего профессионального образования

«сибирский государственный университет телекоммуникаций и информатики»

КОНТРОЛЬНАЯ РАБОТА

Предмет: «ТЕЛЕКОММУНИКАЦИИ»

1 Исходные данные и отраБАТЫВАЕМЫЕ вопросы

2 ЛАБОРАТОРНАЯ РАБОТА № 1

3 ЛАБОРАТОРНАЯ РАБОТА № 2

4 ЛАБОРАТОРНАЯ РАБОТА № 3

5 ЛАБОРАТОРНАЯ РАБОТА № 4

ЗАКЛЮЧЕНИЕ

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

1 Исходные данные и отрабатываемые вопросы

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

2 ЛАБОРАТОРНАЯ РАБОТА № 1

Тема: «Исследование методов кодирования и декодирования циклических кодов»

Цель работы

1. Изучение структуры кодеров циклического кода.

2. Анализ процесса формирования проверочных разрядов.

3. Изучение принципов обнаружения и исправления ошибок в декодере циклического кода.

Расчеты:

В данной работе необходимо осуществить кодирование кодовой информации 1101 с помощью образующего полинома Р (Х)=X4+X3+X2+1 (по варианту заданному преподавателем).

По виду образующего полинома Р (Х) можно определить вид образующего числа. В нашем случае образующее число будет иметь вид: Р (Х)=1X4+1X3+1X2+0Х1+1Х0= 11 101. Образующее число представляет собой упорядоченную совокупность двоичных коэффициентов перед степенями образующего полинома.

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

Для обеспечения делимости в качестве проверочных разрядов следует использовать разряды остатка от деления по модулю два информационных разрядов с приписанными к ним справа r нулями на образующее число.

Так как информационные разряды имеют вид 1101, образующий полином Р (Х)=X4+X3+X2+1, образующее число 11 101, то найдем проверочные разряды, причем r=3.

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

где 001 — синдром ошибки (остаток или иначе проверочные разряды).

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

Следовательно, проверочные разряды (синдром) будут иметь вид: 001.

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

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

Таким образом, построим кодер циклического кода для чего воспользуемся правилом: если пронумеровать ячейки регистра возрастающими степенями Х (Х0,Х1,…, Хr+1) — то сумматоры включаются на входах тех ячеек, которые соответствуют ненулевым членам образующего полинома, кроме младшей ячейки Х0. Также добавим, что для ввода разрядов делимого схему устройства деления необходимо дополнить еще одним сумматором по модулю два, включенным в цепь обратной связи таким образом, что один вход подключен к выходу старшей ячейки регистра, на второй вход подаются разряды делимого, а выход подключен к цепи обратной связи. Таким образом, общее количество сумматоров по модулю два получается на единицу меньше веса образующего числа. Схема устройства деления на образующий полином Р (Х)=X4+X3+X2+1 изображена на рис. 2.1:

Рис. 2.1 Устройство формирования проверочных разрядов.

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

Процесс формирования проверочных разрядов иллюстрируется следующей табл. 2.1.

Табл. 2.1 Процесс формирования проверочных разрядов.

После окончания формирования проверочных разрядов их нужно передать в канал вслед за информационными. Поэтому кодер, помимо устройства вычисления проверочных разрядов должен еще содержать ключ 1 (рис. 2.2), который, замыкаясь после окончания формирования проверочных разрядов, пропускает через себя в канал сформированные проверочные разряды. Пока проверочные разряды не сформированы — он разомкнут. Кодер содержит еще ключ 2. Этот ключ отключает цепь обратной связи при выводе проверочных разрядов в канал (на вход модулятора). В противном случае выходящие в канал проверочные разряды, поступая по цепи обратной связи на сумматоры, изменяют уже сформированные разряды.

Схема кодера представлена на рис. 2.2.

Рис. 2.2. Схема кодера.

В качестве декодирующего устройства при обнаружении ошибок может служить схема кодирующего устройства с небольшими изменениями (рис. 2.3). В состав его входят: буферный регистр на k разрядов, декодирующий регистр, схема которого аналогична схеме кодирующего устройства, схемы ИЛИ и ключи К1, К2.

Рис. 2.3 Схема декодирующего устройства.

Принимаемая последовательность записывается в ячейки буферного регистра и поступает в декодирующий регистр. На k-м такте ключ К1 закрывается, благодаря чему в буферном регистре оказываются лишь информационные разряды принимаемой комбинации. Проверочные разряды продолжают поступать в декодирующий регистр. На n-м такта, после приема последнего разряда кодовой комбинации, открывается ключ К2. Если комбинация принята без ошибок, то в ячейках декодирующего регистра будут записаны нули, а сигнал «ошибка» будет отсутствовать. Наличие же в тех или иных ячейках декодирующего регистра единиц свидетельствует об ошибках в принимаемой информации. На выходе схемы ИЛИ в таком случае появляется сигнал «ошибка», который может быть использован для стирания ошибочно принятой информации, накопленной в буферном регистре.

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

Табл.2.2. Процесс формирования проверочных разрядов синдрома в декодирующем устройстве.

Итак, синдром (001) отличен от нуля, что свидетельствует о наличии ошибки. Исправление последней производится следующим образом: ключ К2 отключает декодирующий регистр от входа декодирующего устройства и в буферный и декодирующий регистры подаются тактовые импульсы. Номер такта, при котором в схему И считывается комбинация синдрома 100, совпадает с номером искаженного разряда кодовой комбинации.

3 ЛАБОРАТОРНАЯ РАБОТА № 2

Тема: «Исследование сверточного кода»

Цель работы:

1. Изучить работу кодера и декодера сверточных кодов по алгоритму Витерби.

1. Проанализировать исправляющую способность декодера.

Расчеты:

Сверточные коды можно рассматривать как частный случай блоковых кодов, но наличие сверточной структуры наделяет его дополнительными свойствами, улучшающими его характеристики. Как любой корректирующий код, сверточные коды защищают информацию, добавляя избыточные символы. Кодирующее устройство сверточного кода со скоростью R = k/n (рис. 3.1) обрабатывает входную последовательность, состоящую их k информационных символов, и вычисляет п кодовых (канальных) символов (n > к). Если один (например первый) из n символов текущего блока повторяет текущий информационный бит, код называется систематическим.

Рис. 3.1 Кодирующее устройство сверточного кода со скоростью R = k/n.

Сверточный кодер с кодовым ограничением v представляет собой регистр памяти для хранения т информационных символов и преобразователь информационной последовательности в кодовую последовательность. Процесс кодирования производится непрерывно. Информационные двоичные символы {ai} поступают на вход регистра сдвига с т ячейками, в котором символы кодовой последовательности формируются суммированием по модулю 2 символов с выходов некоторых ячеек. Подключение сумматоров к ячейкам регистра задается генераторными полиномами g1(x) и g2(x).

Будем полагать, что кодирование производится с использованием сверточного (7,5)-кода. Схема сверточного кодера в этом случае будет иметь вид (рис. 3.2)

Рис. 3.2 Схема сверточного кодера для кода (7,5).

Алгоритм функционирования такого кодера поясняется следующей диаграммой (рис. 3.3). Решетчатая диаграмма является разверткой диаграммы состояний во времени (рис. 3.4).

Рис. 3.3 Алгоритм функционирования кодера (7,5).

Рис. 3.4 Диаграмма состояний сверточного кодера указанной структуры.

Сверточный кодер можно рассматривать как постоянный во времени конечный автомат, структура которого является периодической и может быть описана с помощью различных диаграмм. Например, сверточный кодер может быть описан диаграммой состояний. Диаграмма представляет собой направленный граф и описывает все возможные переходы кодера из одного состояния в другое, а также содержит выходные символы кодера, которые сопровождают эти переходы. Пример диаграммы состояний показан на рисунке 3.4. В кружках указаны четыре возможных состояния кодера 00, 10, 01, 11, линиями со стрелками — возможные переходы. Сплошная линия отмечает переходы, совершаемые при поступлении на вход кодирующего устройства информационного символа 0, пунктирная — при поступлении символа 1. Символы около линий обозначают символы на входе и выходе кодера, соответствующие данному переходу.

Принцип функционирования декодера Витерби состоит в следующем: на вход декодера поступает сегмент последовательности r длиной b, превышающей кодовую длину блока n. Назовем b окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной b) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова принимается в качестве оценки информационного кадра декодированного слова. После этого в декодер вводится n0 новых символов, а введенные ранее самые старые n0 символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путем и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путем.

Свободное расстояние кода (7,5) равно минимальному весу пути по диаграмме из состояния 00 в тоже состояние (исключая петлю у состояния 00). Диаграмма свободного расстояния для рисунка 3.4 изображена на рисунке 3.5 и для него df =5.

Рис. 3.5 Диаграмма свободного расстояния кодера (7,5).

Рассмотрим работу декодера Витерби на примере сверточного кода (7,5). Все решетчатые диаграммы процесса декодирования представлены на рис. 3.4.

Пользуясь решетчатой диаграммой кодера, попытаемся, приняв некоторый сегмент r, проследить наиболее вероятный путь кодера. При этом для каждого сечения решетчатой диаграммы будем отмечать меру расходимости пути каждому ее узлу. Предположим, что передана кодовая последовательность U = (0…), а принятая последовательность имеет вид r = (10 001 000…), то есть в первом и в третьем кадрах кодового слова возникли ошибки. Как мы уже убедились, процедура и результат декодирования не зависят от передаваемого кодового слова и определяются только ошибкой, содержащейся в принятой последовательности. Поэтому проще всего считать, что передана нулевая последовательность, то есть U = (0…). Приняв первую пару символов (10), определяется мера расходимости для первого сечения решетки, приняв следующую пару символов (00), — для второго сечения и т. д. При этом из входящих в каждый узел путей оставляем путь с меньшей расходимостью, поскольку путь с большей на данный момент расходимостью уже не сможет стать в дальнейшем короче. Заметим, что для рассматриваемого примера начиная с четвертого уровня метрика (или мера расходимости) нулевого пути меньше любой другой метрики. Поскольку ошибок в канале больше не было, ясно, что в конце концов в качестве ответа будет выбран именно этот путь. Из этого примера также видно, что выжившие пути могут достаточно долго отличаться друг от друга. Однако на шестом-седьмом уровне первые семь ребер всех выживших путей совпадут друг с другом. В этот момент согласно алгоритму Витерби и принимается решение о переданных символах, так как все выжившие пути выходят из одной вершины, т. е. соответствуют одному информационному символу.

Рис. 3.4 Решетчатые диаграммы сверточного декодера Витерби (7,5).

В результате были рассмотрены следующие случаи работы декодера Витерби: 1) Вектор ошибки нулевой (отсутствие ошибок); 2) Одиночная ошибка в начале вектора ошибки; 3) Одиночная ошибка в конце вектора ошибки; 4) Двукратная ошибка; 5) Трехкратная ошибка.

4 ЛАБОРАТОРНАЯ РАБОТА № 3

Тема: «Исследование обнаруживающей и исправляющей способности циклических кодов».

Цель работы

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

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

Расчеты:

На рис. 4.1 приведена схема декодера циклического кода (15,11), а на рис. 4.2 приведена схема декодера циклического кода (23,12).

Рис. 4.1 Схема декодера циклического кода (15,11).

Рис. 4.2 Схема декодера циклического кода (23,12).

Количество ошибок, исправляемых кодами (15,11) и (23,12) соответственно будут равны 1 и 3. Кодовое расстояние определяется для этих кодов как

(4.1)

Следовательно, подставив в (4.1) значение t получим для кода (15,11) d=3 и для кода (23,12) d=7.

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

5 ЛАБОРАТОРНАЯ РАБОТА № 4

Тема: «Исследование методов коммутации»

Цель работы:

1.1 Ознакомление с видами и принципами коммутации.

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

1.3 Приобретение навыков экспериментального исследования одной из основных характеристик функционирования сети — времени доставки сообщения.

1.4 Анализ графических зависимостей на примере зависимости времени доставки сообщений от скорости передачи, длины сообщений.

Предварительный расчёт:

Данные для расчета:

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

А) при коммутации пакетов (КП) и сообщений (КС):

— скорость передачи на всех участках сети одинаковая;

— количество каналов на всех участках сети одинаковое (один канал);

— коэффициент использования (загрузки) канала © на участке узел коммутации (УК) — оконечный пункт (ОП): с = 0,4;

— служебная часть сообщений при КС составляет 70 знаков (560 ед.эл.);

— служебная часть пакета (с учетом проверочных разрядов) — 136 ед.эл.;

— время обработки в узле: при КС — 0,1с, при КП — 0,01с;

Б) при коммутации каналов (КК):

— затраты времени на установление соединения: t_выз — 2с,

время набора одной цифры номера (t_НН): декадный набор — 1,5с;

— число набираемых цифр — 7;

— время коммутации на одном узле (с учетом времени передачи адреса сообщений на следующий узел) — 0,6с;

— время ответа УПС (включая оконечные устройства приема и передачи ОП) — Зс;

— время разъединения (разъед t) — 0,2с.

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

Длина одного запроса и автоответа — 22 комбинации (176 ед.эл.).

Расчеты:

Коммутация каналов:

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

при

t_пер — среднее время передачи сообщения; t_соед — среднее время передачи адреса и установления соединения; t_АО — среднее время обмена автоответами; N_УК — количество узлов КК.

Примем скорость передачи В=100 (Бод).

Следовательно

Таким образом, получим:

при В=100 (Бод).

Коммутация сообщений:

Время доставки сообщения при коммутации сообщений:

t_пер — среднее время передачи служебно-адресной информации и содержимого сообщения на каждом этапе; t_ож — среднее время выбора пути и ожидания освобождения канала передачи; t_обр — среднее время обработки адресной части сообщения в каждом узле КС; N_УК — число узлов КС.

Примем скорость передачи В=100 (Бод).

Следовательно Таким образом, получим:

при В=100 (Бод)

Коммутация пакетов:

Время доставки сообщения при коммутации пакетов:

где

t_пер.с — время передачи сообщения на первом и последнем узлах КП; t_{пер.пак} — среднее время передачи пакета между узлами КП; t_ож.пак — среднее время выбора пути и ожидания освобождения канала передачи; t_обр — среднее время обработки адресной части пакета в каждом узле КП; t_ожУКn — время ожидания последнего пакета в УКn; N_УК — число узлов КП; k — число передаваемых пакетов (к = 3).

Примем скорость передачи В=100 (Бод).

Следовательно Таким образом, получим:

Таблица 5.1

Сведем полученные результаты расчетов в таблицу 5.1 и 5.2.

Таблица 5.2

На основании значений, приведенных в таблицах 5.1 и 5.2 построим графики зависимостей, приведенные на рис. 5.1 и 5.2 для

Рис. 5.1. Зависимость .

Рис. 5.2.Зависимость .

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

При малых значениях В (до 1000 Бод) наименьшее время доставки сообщения будет при коммутации каналов; а при значениях В (свыше 1000 Бод) наименьшее время доставки сообщения будет при коммутации сообщений. Стоит отметить, что при всех рассмотренных значениях В, время доставки сообщения будет иметь большие значения по сравнению с и. Следовательно, для систем коммутации низкоскоростных сообщений целесообразно применять системы с КК (до 1000 Бод) и с КС (свыше 1000 Бод). Системы с КП в этом случае применять одинаково невыгодно.

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

ЗАКЛЮЧЕНИЕ

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

В лабораторной работе № 1 были изучены структуры кодеров циклического кода; проанализирован процесс формирования проверочных разрядов; изучены принципы обнаружения и исправления ошибок в декодере циклического кода (15,11) и (23,12); сравнили параметры кодов. В лабораторной работе № 2 изучен принцип работы кодера и декодера сверточных кодов по алгоритму Витерби; проанализирована исправляющая способность декодера. В лабораторной работе № 3 ознакомились с методами построения корректирующих кодов; экспериментально исследовали обнаруживающую и исправляющую способности циклических кодов. В лабораторной работе № 4 ознакомились с видами и принципами коммутации; овладели методикой расчета времени доставки сообщений при различных методах коммутации; приобрели навыки экспериментального исследования одной из основных характеристик функционирования сети — времени доставки сообщения.

1. Методическое пособие по расчету цифровых систем связи.

2. Кириллов В. И. Многоканальные системы передачи. Минск. Новое издание, 2003 г.

3. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Москва. Вильямс, 2003 г.