Разработка системы кодирования/декодирования циклического кода
Разработка системы кодирования/декодирования циклического кода
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра КТРС РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ ПО ДИСЦИПЛИНЕ«ОСНОВЫ ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ»ВАРИАНТ № 10Выполнил:Проверил:Студент Иванов И.И.Преподаватель Синельников А.В.Группа: РКС10-32Новосибирск 2009Общее задание Разработать систему кодирования/декодирования циклического кода для -элементного первичного кода, который обнаруживает и исправляет ошибок. Оценить вероятность получения необнаруживаемой ошибки на выходе системы, если в канале связи меняется от до . Исходные данные Необходимые для решения задачи исходные данные выбираются по таблице 1 в соответствии с полученным вариантом. Таблица 1 Исходные данные для вариантов расчетно-графической работы. |
Вариант № | Количество элементов в коде | Количество исправляемых ошибок | Вариант № | Количество элементов в коде | Количество исправляемых ошибок | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 5 6 7 8 9 10 5 6 7 8 9 10 5 6 7 8 9 10 5 6 | 1 5 3 2 4 1 2 4 6 1 3 2 3 3 5 4 2 3 4 2 | 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | 7 8 9 5 6 7 8 6 7 5 5 6 7 6 9 8 10 5 5 8 | 4 3 1 5 1 2 5 6 1 3 5 2 4 6 3 4 2 4 5 3 | | |
Этапы выполнения работы Определение числа проверочных элементов избыточного кода. Выбор образующего многочлена для построения кода, указанного в задании. Расчёт матрицы синдромов для однократной ошибки. Построение функциональной схемы устройств кодирования-декодирования полученного кода. Построение графика появления необнаруживаемой ошибки при заданном изменении вероятности ошибки в канале связи. ЗАДАНИЕ ВАРИАНТАРазработать систему кодирования/декодирования для 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) = x4 + x + 1.Проверка образующего полинома1. Определяем необходимое кодовое расстояние:2. Вычисляем: f(x) = xk-1 = x7 = 100000003. Находим: f(x)xr = x11 = 1000000000004. Поделим f(x)xr на G(x):x11 x4 + x + 1x11 + x8 + x7 x7 + x4 + x3 + xx8 + x7x8 + x5 + x4x7 + x5 + x4x7 + x4 + x3x5 + x3x5 + x2 + x x3 + x2 + x = r(x) = 1110Полученный остаток от деления является комбинацией проверочных элементов:r(x) = 11105. Записываем многочлен комбинации:F(x) = f(z)xr + r(x) = 100000001110Определяем вес многочлена (количество единиц в комбинации): V = 4.Сравниваем V с d0, поскольку выполняется условие: V d0, то выбранный полином подходит как образующий.Построение матрицы синдромов для однократной ошибкиДля определения элементов матрицы синдромов будем вносить ошибку в кодовую комбинацию (F(x) = 100000001110) поочерёдно начиная со старшего разряда, затем делить на образующий полином, полученный остаток и будет одной из строк матрицы синдромов. Пусть ошибка произошла в самом старшем разряде, тогда она имеет вид 000000001110, т.е. деление такого числа на образующий полином и есть это число. Следовательно это синдром для ошибки в разряде а1. Определим синдромы для остальных разрядов.для а2:x10 x4 + x + 1x10 + x7 + x6 x6 + x3 + x2 + 1x7 + x6x7 + x4 + x3x6 + x4 + x3x6 + x3 + x2x4 + x2x4 + x + 1x2 + x + 1 = s(x) = 0111для а3:x9 x4 + x + 1x9 + x6 + x5 x5 + x2 + xx6 + x5x6 + x3 + x2x5 + x3 + x2x5 + x2 + xx3 + x = s(x) = 1010для а4:x8 x4 + x + 1x8 + x5 + x4 x4 + x + 1x5 + x4x5 + x2 + xx4 + x2 + xx4 + x + 1x2 + 1 = s(x) = 0101для а5:x7 x4 + x + 1x7 + x4 + x3 x3 + 1x4 + x3x4 + x + 1x3 + x + 1 = s(x) = 1011для а6:x6 x4 + x + 1x6 + x3 + x2 x2 x3 + x2 = s(x) = 1100для а7:x5 x4 + x + 1x5 + x2 + x xx2 + x = s(x) = 0110для а8:x4 x4 + x + 1x4 + x + 1 1x + 1 = s(x) = 0011Таким образом, матрица синдромов имеет вид:Полученная матрица синдромов используется для алгоритма построения дешифратора ошибок разрабатываемого далее декодера.Схема кодера циклического кода (12, 8)Образующий полином G(x) можно представить в виде:G(x) = g4x4 + g3x3 + g2x2 + g1x + g0, где g4 = 1, g3 = 0, g2 = 0, g1 = 1, g0 = 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 с., ил.
|
|