Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки УКРАИНЫ

Сумский государственный университет

Кафедра электроники и компьютерной техники

курсовая работа

"основы теории кодирования"

Тема: "Синтез кодирующих устройств системы передачи данных"

Сумы 2006

ЗАДАНИЕ

курсовой работы по дисциплине "Основы теории кодирования" на тему: "Синтез кодирующих устройств системы передачи данных"

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

С этой целью необходимо обеспечить решение следующих задач:

1. Разработать алгоритм, устраняющий избыточность с помощью заданного оптимального неравномерного кода;

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

3. Оценить корректирующие и обнаруживающие способности полученного кода.

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

1 Символы первичного алфавита А: й, х, ц, з, ы, т, в, д, ч, б, а, о.

2 Вид неравномерного кода для сжатия информационного блока: Шеннона - Фано

3 Информационный блок: М слов длиной L двоичных символов в слове: L = 7, К = 12

4 Способ введения избыточности в информационный блок - циклические коды;

5 Допустимое значение вероятности необнаруженной ошибки Р_но доп; 110^-6

6 Вероятность искажения двоичного разряда Р_э; 410^-2

7 Тип канала связи - симметричный;

1. Кодовый метод зашиты информации от ошибок. Основные характеристики

код информационный схема

Кодовая комбинация представляет собой набор знаков (символов, элементов) из некоторого их конечного числа, называемого алфавитом. При кодировании каждому сообщению ставится в соответствие определённая кодовая комбинация. Различают две группы кодов: неизбыточные (некорректирующие, простые, первичные) и избыточные (корректирующие). Первые не позволяют обнаруживать и исправлять искажённые элементы в своих комбинациях, вторые - обеспечивают возможность обнаружения или исправления искажённых в результате действия помех и искажений элементов кодовых комбинаций.

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

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

· число информационных элементов к;

· число проверочных элементов r (для корректирующих кодов);

· длина (разрядность) кода n - число элементов (символов), составляющих кодовую комбинацию, n=к+r;

· основание (алфавит) кода q;

· мощность кода N_р - число разрешённых кодовых комбинаций, используемых для передачи сообщений;

· полное число кодовых комбинаций N - число всех возможных комбинаций, равное qⁿ (для двоичных кодов n=2);

· избыточность кода R_и;

или при N_р=2^k

· относительная скорость кода R, характеризующая степень использования в избыточном коде информационных возможностей его мощности,

или вес кодовой комбинации (кода) для двоичного кода определяется количеством единиц в кодовой комбинации;

· минимальное кодовое расстояние кода, определяемое как минимальное расстояние из всех полученных кодовых расстояний между парами кодовых комбинаций данного кода. Кодовое расстояние d_ij между i -й и j -й комбинациями этого кода определяется в соответствие с правилом

где a_li, а_lj - элементы, стоящие на l-м месте в i-й и j-й комбинациях, т.е. d_i,j определяется числом одноименных разрядов с различными значениями;

· вероятность необнаруживаемой ошибки Р_но - вероятность такого события, при котором принятая кодовая комбинация отличается от переданной, а свойства данного кода не позволяют определить факт наличия ошибки;

· вероятность обнаруженной ошибки Р_оо - вероятность, при которой принятая кодовая комбинация отличается от переданной и благодаря свойствам данного кода устанавливается факт наличия ошибки в кодовой комбинации;

· вероятность исправляемой ошибки Р_АО - вероятность такого события, при котором принятая кодовая комбинация отличается от переданной, и, благодаря свойствам данного кода, исправляется ошибка в кодовой комбинации;

· вероятность возникновения ошибки Р_ош - вероятность такого события, при котором принятая кодовая комбинация отличается от переданной (Р_ош=Р_но+Р_оо=Р_но+Р_оон+Р_и)_о, где Р_оон - вероятность неисправляемой обнаруженной ошибки);

· кратность ошибки н определяется кратностью обнаруживаемых н_о и исправляемых н_и ошибок;

· эффективность кода:

где Р_i - вероятность обнаруживаемой или исправляемой ошибки в зависимости от свойств данного кода.

Степень защиты информации от ошибок определённым методом кодирования зависит, главным образом, от минимального кодового расстояния данного кода.

Различают три вида кодового расстояния: Хемминга, Ли и матричное. Кодовое расстояние Хемминга d между двумя комбинациями одной длины n определяется как число из одноимённых разрядов, содержащих неодинаковые элементы.

Так для двоичных кодов расстояние Хемминга между двумя кодовыми комбинациями можно определить их поразрядным суммированием по mod 2 и последующим подсчётом числа ненулевых элементов, т.е. определением веса w такой суммы.

Общее число комбинаций длины n равно 2ⁿ, а число комбинаций, отстоящих от данной на расстояние d равно числу сочетаний из n по d:

Чтобы определить комбинацию, отстоящую от данной на расстояние d, можно прибавить к данной комбинации любую комбинацию веса d (с d единицами и n-d нулями). Сложение поразрядное по mod 2.

2. Оптимальное кодирование

Код может быть оптимальным только для определённых условий, например, оптимальный код с точки зрения скорости передачи информации, оптимальный код с точки зрения надёжности передачи информации.

Оптимальным кодированием называется процедура преобразования символов первичного алфавита m₁ в кодовые слова во вторичном алфавите m₂, при которой средняя длина сообщений во вторичном алфавите минимальна.

Основные свойства оптимальных кодов:

минимальная средняя длина кодового слова оптимального кода обеспечивается в том0 случае, когда избыточность каждого кодового слова сведена к минимуму (в идеальном случае к нулю);

кодовые слова оптимального кода должны строится из равновероятных и взаимонезависимых символов.

Из свойств оптимальных кодов вытекают принципы их построения.

Первый принцип оптимального кодирования: выбор каждого кодового слова необходимо производить так, чтобы содержащееся в нём количество информации было максимальным.

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

Все существующие методики построения кодов с минимальной средней длиной кодовых слов могут быть сведены к двум универсальным методикам.

Первая методика базируется на работах К.Э. Шеннона и Р. Фано.

Построение оптимального кода по методу Шеннона - Фано для ансамбля из М сообщений сводится к следующей процедуре:

· множество из М сообщений располагают в порядке убывания вероятностей;

· первоначальный ансамбль кодируемых сигналов разбивают на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны;

· первой группе присваивают символ 0, второй - символ 1;

· каждую из подгрупп делят на две группы так, чтобы их суммарные вероятности были по возможности равны;

· первым подгруппам каждой из групп вновь присваивают 0, а вторым - 1, в результате чего получаются вторые цифры кода. И так продолжается до тех пор, пока в каждой из подгрупп останется по одной букве.

Вторая универсальная методика построения оптимального неравномерного кода базируется на известной методике Хаффмана. Для первичных алфавитов с числом качественных признаков m₁ построение оптимального кода во вторичном алфавите с числом качественных признаков m₂ сводится к процедуре построения кодового дерева, для чего выполняются следующие операции. Символы алфавита m₁ упорядочиваются по вероятностям. В случае упорядочивания по убыванию последние n₀ символов объединяются в новый символ с вероятностью равной сумме вероятностей объединяемых символов. Последующие объединения символов в дополнительные символы производятся с соблюдением следующих условий:

· на всех этапах построения кодового дерева (кроме первого и последнего), дополнительные символы объединяют n=m₂ символов. На первом этапе число объединяемых символов равно n₀ , а на последнем значение n может находиться в пределах 1 n m₂

· в дополнительные символы объединяются только символы, имеющие на данном этапе построения кодового дерева наименьшую вероятность с учётом вероятности вновь образованных символов;

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

Процедура объединения в новые символы продолжается до тех пор, пока вероятность очередного вновь образованного символа не будет равна 1.

Ветвям, выходящим из корня и узлов, качественные признаки алфавита m₂ присваиваются всегда в одном и том же порядке.

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

3. Избыточные двоичные коды

Наибольшее распространение среди двоичных избыточных кодов для защиты информации от ошибок получили систематические и несистематические блочные коды, которые, в свою очередь, делятся на линейные и нелинейные. Кроме того, широко используются коды: с одной проверкой на чётность (нечётность); с повторением (с повторением без инверсии); с повторением с инверсией; циклические; итеративные простые (двумерные). Циклические коды широко используются для защиты информации от ошибок. Представление кодовых комбинаций в циклических кодах осуществляют в виде полиномов от формальной переменной x, что позволяет свести действия над кодовыми комбинациями к действиям над многочленами. Так, сложение двоичных многочленов выполняется сложением по mod 2 коэффициентов при равных степенях переменной x.

Например, А=x³+x²+1 сложить по модулю 2 (mod 2) с В=x+1 означает:

Умножение выполняется по обычному правилу умножения степенных функций, но коэффициенты при одинаковых степенях x складываются по mod 2. Деление также осуществляется как обычное деление многочленов, при этом операция вычитания совпадает с операцией сложения по mod 2.

Линейные блочные (n,k) коды, у которых циклический сдвиг a_n-2, a_n-3, a_n-4, …, а₂, а₁, а₀, а_n-1 разрешённой комбинации а_n-1, a_n-2, a_n-3, … , а₁, а₀ также является разрешённой комбинацией, принадлежащей данному коду, называется циклической. Такая циклическая перестановка появляется в результате умножения данного полинома на x.

Если V(x) = а_n-1x^n-1+a_n-2x^n-2+…+а₁x+а₀, то хV(x) = а_n-1xⁿ+a_n-2x^n-1+…+а₁x²+а₀x.

Чтобы степень многочлена не превышала n-1, член а_n-1xⁿ заменяется единицей. Поэтому

xV(x) = F(x) = a_n-2x^n-1+ +…+а₁x²+а₀x+а_n-1.

Особую роль в теории циклических кодов играют так называемые образующие (порождающие) многочлены. Замечено, что комбинации линейного кода обладают свойством цикличности, когда в качестве образующих используются многочлены, являющиеся делителями двучлена xⁿ+1. Обычно каждый двучлен xⁿ+1 может быть разложен на несколько неприводимых многочленов, т.е. таких, которые не могут быть представлены в виде произведения многочленов низших степеней (они делятся сами на себя или на единицу). В качестве образующих многочленов различных циклических кодов могут быть использованы все эти неприводимые многочлены и их произведения, так как они тоже являются делителями двучлена xⁿ+1. Построение разрешённой кодовой комбинации (алгоритм кодирования) сводится к следующему: представить информационную часть из k элементов в виде полинома Q(x) степени k-1 ; умножить Q(x) на x^r (что эквивалентно сдвигу k-разрядной кодовой комбинации на r разрядов); разделить многочлен x^rQ(x) на выбранный образующий полином Р(x), степень которого равна r, и определить остаток от деления R(x), т.е.

,

где С(x) - частное той же степени, что и Q(x), представляющее собой также разрешённую кодовую комбинацию;

R(x) - остаток от деления, который имеет степень не большую r-1 (меньшую, чем степень делителя Р(x), r разрядов остатка представляют собой r проверочных элементов кодовой комбинации

,

где F(x) - кодовая комбинация циклического кода.

Очевидно, что F(x) делится на Р(x) без остатка. На этом и основана проверка кодовой комбинации на наличие ошибок при приёме. Если принятая комбинация делится на Р(x) без остатка, она признаётся безошибочной. алгоритм работы устройства, устраняющего избыточность путем сжатия информации с помощью оптимального неравномерного кода Шеннона - Фано. Заданы сообщения, имеющие условную вероятность, пропорциональную вероятности соответствующих букв русского алфавита.

Буква	Вероятность
Й	0,010
Х	0,009
Ц	0,004
З	0,016
Ы	0,016
Т	0,053
В	0,038
Д	0,025
Ч	0,012
Б	0,014
А	0,062
О	0,090

Сумма вероятностей всех букв равна: 0,349. Вероятность появления заданных сообщений равна 1, поэтому пересчитаем вероятности так, чтобы их суммарная вероятность равнялась 1.

где к - коэффициент пересчета.

Полученные вероятности сообщений сведем в таблицу.

Буква	Вероятность сообщений
Й	0,0287
Х	0,0258
Ц	0,0115
З	0,0458
Ы	0,0458
Т	0,1519
В	0,1089
Д	0,0716
Ч	0,0344
Б	0,0401
А	0,1776
О	0,2579
= 1,0

Составляем таблицу, в первом столбце которой расположим вероятности заданных сообщений в порядке убывания. Далее произведем деление сообщений на группы с присвоением значений 0 и 1 кодовым разрядам (методика описана ранее).

Р(О) = 0,2579	0	0
Р(А) = 0,1776	0	1	0
Р(Т) = 0,1519	0	1	1
Р(В) = 0,1058	1	0	0
Р(Д) = 0,0716	1	0	1	0
Р(Ы) = 0,0458	1	0	1	1
Р(З) = 0,0458	1	1	0	0
Р(Б) = 0,0401	1	1	0	1
Р(Ч) = 0,0344	1	1	1	0	0
Р(Й) = 0,0287	1	1	1	0	1
Р(Х) = 0,0258	1	1	1	1	0
Р(Ц) = 0,0115	1	1	1	1	1

Получим следующие кодовые отображения:

О = 00, А = 010, Т = 011, В = 100, Д = 1010, Ы = 1011, З = 1100,

Б = 1101, Ч = 11100, Й = 11101, Х = 11110, Ц = 11111.

Методика получения кода Хаффмена приведена ранее. Например, получены следующие вероятности сообщений:

Буква	Вероятность к
Ц	0,0083
У	0,0438
В	0,0792
К	0,0583
А	0,1292
Е	0,1500
П	0,0479
Н	0,1104
Р	0,0833
О	0,1875
Ь	0,0292
Л	0,0729
= 1,0

Результаты упорядочения сводим в таблицу

Строим кодовое дерево. Затем производим выбор кодового отображения для каждого сообщения.

Размещено на http://www.allbest.ru/

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

О = 00, Н = 011, А = 100, Е = 101, П = 0100, К = 0101, Л = 1100, В = 1101, Р = 1111, У = 11101, Ц = 111000, Ь = 111001.

4. ВВЕДЕНИЯ ИЗБЫТОЧНОСТИ В ИНФОРМАЦИОННЫЕ ПАКЕТЫ
С ПОМОЩЬЮ ЦИКЛИЧЕСКИХ КОДОВ

Выбор образующего полинома связан с определением числа контрольных (проверочных) разрядов вводимых в K - разрядное информационное сообщение. Число проверочных разрядов r зависит от длины информационной части K и от вероятности необнаруживаемой ошибки . Известно, что для симметричных каналов связи с независимыми ошибками вероятность Р_НО равна:

(1)

Рассмотрим пакет K?L

	L
к
r

Для примера сформируем информационный пакет размером КL:

0110100

1111101

0101101

0111111

0111110

0111100

0111010

1111010

0111101

0000110

1001111

1010100

Пусть допустимое значение вероятности необнаруженной ошибки Р_но доп = 110^-6, вероятность искажения двоичного разряда Р_э = 410^-2

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

1) Пусть d_min = 2, по таблице находим, что при заданном числе информационных разрядов к число проверочных символов равно: r = 1, тогда

.

Полученное значение вероятности необнаруживаемой ошибки больше заданного. Увеличим минимальное кодовое расстояние на 1.

2) Пусть d_min = 3, r = 5, n = 17, тогда ;

3) Пусть d_min = 4, r = 8, n = 20, тогда ;

4) Пусть d_min = 5, r = 11, n = 23, тогда ;

5) Пусть d_min = 6, r = 14, n = 26, тогда ;

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

По заданию ограничена максимальная степень полинома, поэтому выбираем образующий полином 9 степени (r = 9), например,

Найдем проверочные разряды для информационных слов заданного информационного массива, используя приведенный ранее алгоритм:

1) Информационное слово Q₁(1,0) > 010000010011.

Проверочная часть комбинации имеет вид: > 100001100
Кодовое слово - 010000010011 100001100

2)

			111111111000.001111111

Так должны быть получены кодовые комбинации для всех сформированных информационных комбинаций пакета (проверочные разряды к информационным частям)

Для проверки параметров полученной кодировки составим матрицу кодовых расстояний (в столбцах указаны номера кодовых слов для сокращения размеров таблицы). Например:

	1	2	3	4	5	6	7
1	010000010011.100001100	0	15	12	11	12	11	10
2	111111111000.001111111	15	0	7	6	9	12	11
3	110111111001.100100011	12	7	0	7	12	13	14
4	011111111010.101101001	11	6	7	0	9	10	11
5	111111001111.011101100	12	9	12	9	0	9	10
6	000110110110.011100100	11	12	13	10	9	0	11
7	011100001010.010010101	10	11	14	11	10	11	0

По диагонали таблицы будут расположены «0», что соответствует переходу самого кодового слова в себя (правильной передачи). Пользуясь данной таблицей, определим вероятность перехода одного разрешенного слова в другое разрешенное (вероятность необнаруживаемой ошибки для каждого перехода) для каждого кодового расстояния:

d = 6, P = 2,2210^-9;

d = 7, P = 9,2510^-11;

d = 9, P = 1,6110^-13;

d = 10, P = 6,6910^-15;

d = 11, P = 2,7910^-16;

d = 12, P = 1,1610^-17;

d = 13, P = 4,8410^-19;

d = 14, P = 2,0210^-20;

d = 15, P = 8,4010^-22.

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

PHO(a1)	7,2710-15
PHO(a2)	2,3110-9
PHO(a3)	1,8510-10
PHO(a4)	2,3110-9
PHO(a5)	4,910-13
PHO(a6)	1,6810-13
PHO(a7)	1,4210-14

Минимальная вероятность необнаруживаемой ошибки P_HO = 2,3110^-9. Такое значение вероятности необнаруживаемой ошибки удовлетворяет поставленным требованиям.

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

Для обнаружения всех ошибок, кратностью t₀, минимальное кодовое расстояние d_min t₀ + 1, откуда t₀ 5 (при d_min = 6), т.к. будут обнаруживаться все, вплоть до пятикратных ошибок.

Для исправления ошибок определить кратность исправляемых ошибок можно по формуле: d_min 2t_И + 1, откуда t_И 2,5. Таким образом, гарантировано исправляться будут лишь двукратные ошибки.

Опираясь на полученные данные, можно сделать вывод, что разработанный код дает вероятность необнаруживаемой ошибки, которая меньше заданной. Данный код обнаруживает ошибки кратностью до 5 или исправляет двукратную ошибку.

5. Цифровые системы передачи информации

Носителем информации системы передачи информации является сообщение, которое может быть аналоговым или цифровым. Сообщения передаются от объекта к адресату при помощи совокупности технических средств, образующих систему передачи информации.

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

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

На рис. 1 изображена структурная схема системы передачи информации с обратной связью, пакетированием и предварительным сжатием информации оптимальным кодированием. использованы следующие обозначения:

БПИ - блок пакетирования информации;

МБВИ - многоканальный блок введения избыточности (является кодирующим устройством предназначенным для построения циклических кодов);

БП - блок памяти;

УСАП - универсальный синхронно-асинхронный передатчик (приемник);

МБДК - многоканальный блок декодирования;

БДПИ - блок депакетирования информации;

БРАИ - блок разархивации информации;

БФВО - блок формирования вектора ошибок;

БВП - блок векторного переноса;

БПВО - блок памяти вектора ошибок;

ПИ - приемник;

ИИ - источник информации.

СПИСОК ЛИТЕРАТУРЫ

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

2 Цымбал В.П. Теория информации и кодирование. - К.: Вища шк., 1992.

3 Жураковський Ю.П., Полторак В.П, Теорія інформації та кодування: Підручник.- К.: Вища шк, 2001.- 255 с.

4 Васильев и др. Системы связи: Учеб. пособие для втузов / В.И. Васильев, А.П. Буркмн, В.А. Свириденко - М.: Высш. шк., 1987. - 280с.

5 Митюшин К.Г. Телеконтроль и телеуправление в энергосистемах. - М.: Энергоатомиздат, 1990.

Размещено на Allbest.ru