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

3.1 Дайте определение корректирующих кодов.

3.2 Что такое кодовое расстояние?

3.3 Запишите соотношения, определяющие корректирующую способность кода по заданному кодовому расстоянию.

3.4 Дайте определение систематических корректирующих кодов.

3.5 Как определить число дополнительных символов при заданном k, если d = 3?

3.6 Что такое порождающая матрица?

3.7 Как построить порождающую матрицу для систематического кода?

3.8 Что такое проверочная матрица?

3.9 Что такое синдром?

3.10 Поясните принцип построения декодера кода Хэмминга.

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

4.1 Изучить разд. 2 пособия.

4.2 Код (7, 4) задан порождающей матрицей

G = .

Записать номер Вашего стенда N в двоичной системе счисления. Считая, что номер – четырехзначная комбинация на входе кодера, рассчитать комбинацию на выходе кодера. Составить проверочную матрицу заданного кода. Составить таблицу синдромов заданного кода. Ввести однократную ошибку в символ b_N сформированной комбинации, рассчитать синдром для получения комбинации. Убедится, что синдром соответствует ошибочному символу .

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

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

5.1 Ознакомление с виртуальным макетом.

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

5.2 Исследование процесса кодирование.

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

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

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

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

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

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

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

G = .

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

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 Изучение принципов кодирования корректирующим кодом (помехоустойчивого кодирования).

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

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.

Р

Таблиця 6.1 – Порождающие полиноми

r	g(x)
3	x^3 + x^2 + 1
	x^3 + x + 1
4	x^4 + x^3 + 1
	x^4 + x + 1
5	x^5 + x^4 + x^2 + 1

абота кодера циклического кода (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 – Синдроми однократних помилок

Поліном помилки e(x)	Синдром s(x)
x^9	x^4 + x^3 + 1
x^8	x^4 + x^2 + x + 1
x^7	x^3 + x + 1
x^6	x^4 + x^3 + x^2 + x + 1
X^5	x^4 + x^2 + x + 1
x^4	x^4
x^3	x^3
x^2	x^2
x	x
1	1

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

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