Разработка системы кодированиядекодирования циклического кода

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

Кафедра КТРС

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ ПО ДИСЦИПЛИНЕ

«ОСНОВЫ ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ»

ВАРИАНТ № 10

Выполнил:

Проверил:

Студент Иванов И.И.

Преподаватель Синельников А.В.

Группа: РКС10-32

Новосибирск 2009

Общее задание

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

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

Необходимые для решения задачи исходные данные выбираются по таблице 1 в соответствии с полученным вариантом.

Таблица 1

Исходные данные для вариантов расчетно-графической работы.

Этапы выполнения работы

1. Определение числа проверочных элементов избыточного кода.

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

3. Расчёт матрицы синдромов для однократной ошибки.

4. Построение функциональной схемы устройств кодирования-декодирования полученного кода.

5. Построение графика появления необнаруживаемой ошибки при заданном изменении вероятности ошибки в канале связи.

ЗАДАНИЕ ВАРИАНТА

Разработать систему кодирования/декодирования для k = 8-элементного первичного кода, когда код обнаруживает и исправляет t_И = 1-ошибку. Оценить вероятность обнаружения ошибки на выходе системы передачи, если вероятность ошибки в канале связи Р_ОШ меняется от до .

РЕШЕНИЕ

Определение количества поверочных элементов r.

Исходя из того, что k = 8 и t_И = 1, решаем систему уравнений:

Откуда следует:

Составляем таблицу:

Откуда определяем: r = 4, n = k + r = 8 + 4 = 12.

Выбор образующего полинома

После определения проверочных разрядов r, выбираем образующий полином G(x) (многочлен) степени, равной r.

Образующий полином G(x) должен обладать некоторыми свойствами:

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

2) Число остатков у этого полинома должно быть равно количеству ошибок в коде, т.е. такие полиномы примитивные.

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

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

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

A, B, С, D Не примитивный

Е, F, G, Н Примитивный

A, B, Е, F Корни линейно зависимы

С, D, G, Н Корни линейно независимы

A, C, Е, G Корни двойственного многочлена линейно зависимы

B, D, F, Н Корни двойственного многочлена линейно независимы
Выписываем часть таблицы неприводимых полиномов:

Из таблицы выбираем полином (1 23F) и затем переводим из восьмеричного в двоичное представление:

Получили образующий полином:

G(x) = x⁴ + x + 1.

Проверка образующего полинома

1. Определяем необходимое кодовое расстояние:

2. Вычисляем: f(x) = x^k-1 = x⁷ = 10000000

3. Находим: f(x)x^r = x¹¹ = 100000000000

4. Поделим f(x)x^r на G(x):

x¹¹ x⁴ + x + 1

x¹¹ + x⁸ + x⁷ x⁷ + x⁴ + x³ + x

x⁸ + x⁷

x⁸ + x⁵ + x⁴

x⁷ + x⁵ + x⁴

x⁷ + x⁴ + x³

x⁵ + x³

x⁵ + x² + x

x³ + x² + x = r(x) = 1110

Полученный остаток от деления является комбинацией проверочных элементов:

r(x) = 1110

5. Записываем многочлен комбинации:

F(x) = f(z)x^r + r(x) = 100000001110

Определяем вес многочлена (количество единиц в комбинации): V = 4.

6. Сравниваем V с d₀, поскольку выполняется условие: V ³ d₀, то выбранный полином подходит как образующий.

Построение матрицы синдромов для однократной ошибки

Для определения элементов матрицы синдромов будем вносить ошибку в кодовую комбинацию (F(x) = 100000001110) поочерёдно начиная со старшего разряда, затем делить на образующий полином, полученный остаток и будет одной из строк матрицы синдромов. Пусть ошибка произошла в самом старшем разряде, тогда она имеет вид 000000001110, т.е. деление такого числа на образующий полином и есть это число. Следовательно это синдром для ошибки в разряде а1. Определим синдромы для остальных разрядов.

для а2:

x¹⁰ x⁴ + x + 1

x¹⁰ + x⁷ + x⁶ x⁶ + x³ + x² + 1

x⁷ + x⁶

x⁷ + x⁴ + x³

x⁶ + x⁴ + x³

x⁶ + x³ + x²

x⁴ + x²

x⁴ + x + 1

x² + x + 1 = s(x) = 0111

для а3:

x⁹ x⁴ + x + 1

x⁹ + x⁶ + x⁵ x⁵ + x² + x

x⁶ + x⁵

x⁶ + x³ + x²

x⁵ + x³ + x²

x⁵ + x² + x

x³ + x = s(x) = 1010

для а4:

x⁸ x⁴ + x + 1

x⁸ + x⁵ + x⁴ x⁴ + x + 1

x⁵ + x⁴

x⁵ + x² + x

x⁴ + x² + x

x⁴ + x + 1

x² + 1 = s(x) = 0101

для а5:

x⁷ x⁴ + x + 1

x⁷ + x⁴ + x³ x³ + 1

x⁴ + x³

x⁴ + x + 1

x³ + x + 1 = s(x) = 1011

для а6:

x⁶ x⁴ + x + 1

x⁶ + x³ + x² x²

x³ + x² = s(x) = 1100

для а7:

x⁵ x⁴ + x + 1

x⁵ + x² + x x

x² + x = s(x) = 0110

для а8:

x⁴ x⁴ + x + 1

x⁴ + x + 1 1

x + 1 = s(x) = 0011

Таким образом, матрица синдромов имеет вид:

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

Схема кодера циклического кода (12, 8)

Образующий полином G(x) можно представить в виде:

G(x) = g₄x⁴ + g₃x³ + g₂x² + g₁x + g₀, где g₄ = 1, g₃ = 0, g₂ = 0, g₁ = 1, g₀ = 1.

Тогда устройство кодирования имеет вид:

Рис.1. Схема устройства кодирования циклического кода (12, 8).

Принцип работы устройства:

В исходном состоянии ключ находится в положении 1, на вход устройства поступает первичная кодовая комбинация f(x) (начиная со старшего разряда). Через k-тактов вся первичная кодовая комбинация поступит на выход, а в результате деления (благодаря обратной связи) образуется остаток. Ключ переключается в положение 2. Таким образом, через n-тактов на выходе получим F(x).

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

Рис.2. Схема устройства декодирования циклического кода (12, 8).

Принцип работы устройства:

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

Оценка вероятности обнаруживаемой ошибки на выходе системы передачи

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

· Обнаруживаемые или исправляемые кодом.

· Необнаруживаемые ошибки.

Вероятности появления необнаруживаемых ошибок (в режиме исправления):

С помощью программы в среде МАТКАД производим расчеты и получаем графическую зависимость вероятности необнаруживаемых ошибок от вероятности ошибки элемента:

Рис.3. График зависимости вероятности не обнаруживаемой ошибки Р_но на выходе системы передачи от вероятности ошибки в канале связи Р_ош.

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

ЛИТЕРАТУРА

1. Питерсон У., Уэлдон Э. Коды исправляющие ошибки. – М.: Мир, 1976г.

2. Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. – М.: Радио и связь, 1979г.

3. Основы передачи дискретных сообщений: Учебник для вузов / Ю.П. Куликов, В.М. Пушкин, Г.И. Скворцов и др.: Под ред. В.М. Пушкина. – М.: Радио и связь, 1992.- 288 с., ил.