Кафедра теории электрической связи им. А.Г. Зюко

МИНИСТЕРСТВО ТРАНСПОРТА И СВЯЗИ УКРАИНЫ

_______________________________

ОДЕССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ СВЯЗИ им. А.С. ПОПОВА

 

Кафедра теории электрической связи им. А.Г. Зюко

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных работ по дисциплине

“ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ СВЯЗИ”

для модуля № 4

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

 

 

Одесса 2004

 

Содержание

ЛР 4.1,а Изучение кодирования и декодирования кодами Хэмминга

ЛР 4.1,б Изучение кодирования и декодирование циклическими кодами

 

Лабораторная работа 2.6,а
ИЗУЧЕНИЕ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЕ КОДАМИ ХЭММИНГА

Цель работы

1.1 Изучение структуры кодека систематического кода Хэмминга (7, 4).

1.2 Исследование корректирующей способности кода (7, 4).

Ключевые положения

2.1 Систематическими называются корректирующие коды, кодовые комбинации которых содержат k информационных и r = n – k дополнительных символов, являющихся линейной комбинацией информационных. Обозначаются систематические коды как (n, k) либо (n, k, d). В данной работе изучаются коды (7, 4) или (7, 4, 3).

2.2 Корректирующие коды с кодовым расстоянием d = 3, позволяющие при декодировании исправлять однократные ошибки, называют кодами Хэмминга [1, с. 149]. Установим связь между параметрами n и k корректирующего кода. Известно, что для любого натурального числа r существует код Хэмминга длины n = 2 ^r – 1 или k + r = 2 ^r – 1 [1, с. 149]. Естественно, что эти равенства можно использовать и в виде неравенств k £ 2 ^r – r – 1. Последнее соотношение позволяет выбрать n и r при заданном k.

2.3 Матричный способ описания процессов кодирования и декодирования линейных блоковых кодов является наиболее удобным [1, с. 144 …149]. Так, кодирование систематическим кодом (n, k), состоящее во введении в кодовые комбинации дополнительных символов, описываются матричным соотношением

A× G = B, (6,а.1)

где A = (b ₁ b ₂ … b_k) – матрица-строка размером k, соответствующая комбинации простого кода;

B = (b ₁ b ₂ … b _k b _k+1 … b _n) – матрица-строка размером n, соответствующая комбинации корректирующего кода

 

 

 

G = – (6,а.2)

порождающая (производящая) матрица размером k ´ n, элементы которой g_ij принимают значения 1 или 0. Порождающую матрицу можно рассматривать как объединение единичной матрицы порядка k (информационной матрицы) и матрицы-дополнения размером k ´ r.

Требования к отчету

7.1 Название лабораторной работы.

7.2 Цель лабораторной работы.

7.3 Результаты выполнения домашнего задания.

7.4 Структурная схема кодера и декодера, что используется в ЛР.

7.5 Результаты выполнения пп. 5.2...…5.5 лабораторного задания (решетчатые диаграммы, числовые значения кодовых последовательностей и т.п.).

7.6 Выводы по каждому пункту лабораторного задания, в которых дать анализ полученных результатов – совпадение теоретических и экспериментальных данных, корректирующая способность кода (7, 5) и т.п..

7.7 Подпись студента о выполнении ЛР, виза преподавателя о защите ЛР с оценкой по 100-балльной шкале оценивания, дата.

Литература

1. Теория передачи сигналов: Учебник для ВУЗов/ А.Г. Зюко и др. – М.: Радио и связь, 1986.

2. Кузьмин Н.В., Кедрус В.А. Основы теории информации и кодирования. – К.: Вища школа, 1986.

 

Лабораторная работа 2.6,б
ИЗУЧЕНИЕ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЕ ЦИКЛИЧЕСКИМИ КОДАМИ

Цель работы

1.1 Изучение принципов кодирования корректирующим кодом (помехоустойчивого кодирования).

1.2 Экспериментальное исследование работы кодера и декодера циклических кодов.

Ключевые положения

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

2.2 Общий принцип построения корректирующих кодов довольно простой. Из общего числа M = 2 ⁿ возможных кодовых комбинаций длины n используются для передачи не все, а только M ₀ = 2 ^k (M ₀ < M). Используемые кодовые комбинации называются разрешенными. Другие M – M ₀ комбинаций считаются запрещенными, то есть они не могут подаваться в канал связи, их появление на выходе канала свидетельствует о наличии ошибок. Таким образом, благодаря наличию запрещенных кодовых комбинаций возникает возможность обнаружение ошибок, которые возникают во время передачи. Итак, любой корректирующий код является кодом с избыточностью (каналом связи передается r = n – k избыточных символов в каждой кодовой комбинации).

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

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

Кодовое расстояние d _min – это минимальная расстояние Хэмминга для заданного кода. Перебрав все возможные пары разрешенных кодовых комбинаций и вычислив для них расстояния d_ij, необходимо найти среди них минимальную, то есть d _min = min d_ij.

Скорость кода R показывает относительное число информационных символов k в кодовых комбинациях длины n и вычисляется R = k / n.

Корректирующая способность кода определяется кратностью ошибок, которые обнаруживаются q _об, и кратностью ошибок, которые исправляются q _исп..

Кратность ошибок, которые гарантированы обнаруживаются q _об – число ошибок в кодовой комбинации, которая гарантирована обнаруживаются во время декодирования, определяется: q _об < d _min.

Кратность ошибок, которые исправляются q _исп – число ошибок в кодовой комбинации, которые исправляются во время декодирования, определяется: q _вип < d _min /2.

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

 

 

 

Назначение кодера и декодера состоит в следующем. На вход кодера поступает комбинация простого кода А _i длины k, кодер превращает ее в комбинацию корректирующего кода В _i длины n соответственно правилам кодирования, причем, n > k. На вход декодера поступает комбинация длины n из канала связи:

= В _i Å Е, (6,б.1)

где Е – комбинация ошибок. Например, В _i = 101000; пусть ошибка состоялась в втором и третьем символах, тогда Е = 011000, а = 110000.

В зависимости от корректирующей способности кода и цели его применения декодер корректирующего кода может работать в режиме обнаружения или в режиме исправления ошибок. В режиме обнаружения ошибок декодер анализирует: комбинация разрешенная или запрещенная? Если комбинация разрешена, то декодер соответственно правилу декодирования формирует на своем выходе комбинацию А _j длины k. Если комбинация запрещена, то она бракуется декодером, на выходе декодера комбинация отсутствует, а на выходе сигнала ошибки (рис. 6,б.1) появляется определенный сигнал (например, “1”). В режиме исправления ошибок декодер вместо запрещенной комбинации декодирует ближайшую к ней разрешенную кодовую комбинацию соответственно правилу декодирования и выдает комбинацию длины k.

2.5 Наибольшее распространение в системах передачи получили систематические коды, кодовые комбинации которых содержат k информационных символов (это символы комбинации простого кода, что поступила на вход кодера) и r = n – k дополнительных символов, сформированных кодером с информационных символов. В случае линейных кодов дополнительные символы являются линейной комбинацией информационных символов.

Среди систематических блоковых кодов широкое распространение получили циклические коды, благодаря простоте построения кодера и декодера. Для описания циклических кодов оказалось удобным представлять кодовые комбинации полиномами – например, комбинации A _i =10111 отвечает полином a_i (х) = х ⁴ + х ² + х + 1 (символы кодовой комбинации является коэффициентами при соответствующих степенях фиктивной сменной x, причем символ, который записывается первым, отвечает наиболее высокая степень х).

Любой циклический код задается не только числами n и k, но и порождающим полиномом g (x) степени r. Циклическим (n, k) кодом называется код, все комбинации которого представляются полиномами степени n – 1 и меньшее, которые делятся без остатка на порождающий полином. В табл. 6,б.1 приведенные Порождающие полиномы для r = 3, 4 и 5.

Работа кодера циклического кода (n, k) сводится к следующих. Пусть a (x) – полином, который отвечает комбинации простого кода, которая поступила на вход кодера. Полином a (x)× x^r отвечает добавлению к входной комбинации r нулей по правую сторону. Выполняется деление полинома a (x)× x^r на порождающий полином g (x) с целью определения остатка от деления r (x). Остаток от деления r (x) и является дополнительными символами. Полином, который отвечает исходной комбинации кодера, определяется как:

b (x) = a (x)× x^r + r (x), (6,б.2)

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

Легко показать, что полином b (x) делится без остатка на полином g (x):

,

где p (x) – целая часть от деления a (x)× x^r / g (x).

Следует помнить, что сложение полиномов выполняется по правилу сложения по модулю два (mod 2) коэффициентов при одинаковых степенях х.

Рассмотрим пример формирования кодовой комбинации кода (10, 5) с порождающим полиномом g (x) = x ⁵ + x ⁴ + x ² + 1. Пусть А _i = 10110, тогда a_i (x) = x ⁴ + x ² + x, и a_i (x)× x ⁵ = x ⁹ + x ⁷ + x ⁶. Выполним деления с целью определения остатка.

Соответственно (6,б.2)

b_i (x) = x ⁹ + x ⁷ + x ⁶ + x ³ + x ² + 1

B _{i ли} = 1011001101.

В декодере циклического кода выполняется деление принятой комбинации на порождающий полином. Полиномы переданной комбинации b (x), принятой комбинации и ошибки e (x) связанные соотношением, аналогичным (6,б.1): = b (x) Å e (x). Результат деления на порождающий полином можно представить

,

откуда следует, что остаток от деления s (x) зависит только от полинома ошибки и не зависит от переданной комбинации (v (x) – целая часть от деления e (x) на g (x)). Остаток от деления s (x) является синдромом. Ненулевой остаток свидетельствует о том, что принятая комбинация является запрещенной (ошибочной). Если декодер работает в режиме исправления ошибок, то номер ошибочного символа (ли номера ошибочных символов) определяется на основе анализа синдрома. Для кода (10, 5) с порождающим полиномом g (x) = x ⁵ + x ⁴ + x ² + 1 составим таблицу синдромов для всех однократных ошибок, выполняя деления e (x) на g (x) и фиксируя в табл. 6,б.2 только остатки от деления.

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

Рассмотренный код (10, 5) имеет кодовое расстояние d _min = 4 и разрешает исправлять только однократные ошибки.

 

 

3. Ключевые вопросы

3.1 Какие коды называются корректирующими?

3.2 Объяснить назначения кодера и декодера корректирующего кода.

3.3 Что называется чрезмерностью и скоростью кода?

3.4 Что такое расстояние Хэмминга между комбинациями, кодовое расстояние, кратность ошибки?

3.5 Как рассчитать обнаруживающую и испраляющую способность кода?

3.6 Объяснить общий принцип обнаружения и исправление ошибок.

3.7 Какие коды называются циклическими?

3.8 Как выполняется запись кодовых комбинаций в виде полиномов?

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

4. Домашнее задание

4.1 Выучить раздел “Корректирующие коды” по конспекту лекций и литературе [1, с. 137...150; 2, с. 287...297].

4.2 Записать число (N + 8) в двоичной системе счисления, где N – номер Вашей бригады. Считая, что это число – комбинация простого кода длины k = 5, сформировать из нее комбинацию циклического кода (10, 5), используя порождающий полином g (x) = x ⁵ + x ⁴ + x ² + 1.

4.3 Для трех комбинаций ошибок е ₁(х), е ₂(х) и е ₃(х), заданных в табл. 6,б.3, вычислить синдромы, а потом, используя табл. 6,б.2, определить результаты работы декодера. Если вычисленный синдром является в табл. 6,б.2, то декодер инвертирует символ комбинации, которая считается ошибочной. Если же в табл. 6,б.2 отсутствующий вычисленный синдром, то декодер не изменяет символы комбинации, которая декодируется. Комбинация на выходе декодера – это первые k символов принятой комбинации.

Таблица 6,б.3 – Полиномы ошибок для домашнего задания

Номер бригады N	e 1(x) – однократная ошибка	e 2(x) – двукратная ошибка	e 3(x) – трехкратная ошибка
1, 11	x ^9	x ^9 + 1	x ^7 + x ^6 + 1
2, 12	x ^8	x ^6 + x ^8	x ^9 + x ^8 + x ^4
	x ^7	x ^6 + x	x ^9 + x ^8 + x ^2
	x ^6	x ^9 + x	x ^7 + x ^6 + x
	x ^5	x ^7 + x ^6	x ^8 + x ^7 + x ^2
	x ^4	x ^7 + x ^4	x ^8 + x ^7 + x ^3
	x ^3	x ^9 + x ^2	x ^8 + x ^7 + x
	x ^2	x ^6 + x ^3	x ^8 + x ^6 + x
	x ^1	x ^7 + x ^2	x ^9 + x ^6 + x ^4
		x ^8 + x	x ^8 + x ^6 + x ^4

 

4.4 Привести схему включения кодера и декодера корректирующего кода в состав цифрового канала связи.

4.5 Подготовиться к обсуждению по ключевым вопросами.

5. Лабораторное задание

Требования к отчету

7.1 Название лабораторной работы.

7.2 Цель лабораторной работы.

7.3 Результаты выполнения домашнего задания.

7.4 Результаты выполнения пп. 5.2...…5.5 лабораторного задания.

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

7.6 Дата, подпись студента, виза преподавателя с оценкой по 100-балльной шкале.

Литература

1 Теория передачи сигналов. Учебник для вузов / А. Г. Зюко и др. – М.: Радио и связь, 1986.

2 Панфилов И. П., Дирда В. Ю., Капацін А. В. Теорія електричного зв’яСКу: Підручник для студентов вузов 1-го и 2-го рівнів акредитації. – К.: Техніка, 1998.

 

МИНИСТЕРСТВО ТРАНСПОРТА И СВЯЗИ УКРАИНЫ

_______________________________

ОДЕССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ СВЯЗИ им. А.С. ПОПОВА

 

Кафедра теории электрической связи им. А.Г. Зюко

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных работ по дисциплине

“ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ СВЯЗИ”

для модуля № 4