Исследование процесса декодирование при наличии ошибок.

1. Ввести ошибку поочередно в символы b ₁, b ₂, b ₃, b ₄, b ₅, b ₆, b ₇, убедиться в правильности декодирования и правильности составления таблицы синдромов в домашнем задании.

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

3. Ввести трехкратную ошибку в символы b ₁, b ₂, b ₃. Убедится, что синдром равен нулю (разрешенная комбинация) – это свидетельствует о том, что у кода d = 3. Повторить эксперимент, вводя трехкратную ошибку в символы b ₁, b ₄, b ₅. На основе проверочной матрицы определить, какие еще трехкратные ошибки приводят к разрешенным комбинациям.

Описание лабораторного макета

Лабораторный макет выполнен программно на персональном компьютере. Код (7, 4) описывается порождающей матрицей

G = .

Управление работой макета производится путем перемещения курсора и воздействия левой кнопкой мыши на курсор. Ввод ошибок производится путем установки в «1» разряда (разрядов) комбинации ошибок l ₁ l ₂ l ₃ l ₄ l ₅ l ₆ l ₇, в которых должна возникнуть ошибка. Макет производит преобразование передаваемой комбинации в принимаемую по правилу
= b_i Å l_i, для i = 1, 2, …, 7.

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

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. Лабораторное задание