ID: 149

Название работы: Основные понятия теории информации

Категория: Лекция

Предметная область: Информатика, кибернетика и программирование

Описание: Понятие информации. Виды и структура информации. Геометрическая, комбинаторная и аддитивная мера Хартли. Статистическая мера информации. Связь энтропии с количеством информации. Количество информации дискретных сообщений. Определение бита и байта.

Язык: Русский

Дата добавления: 2012-11-14

Размер файла: 517 KB

Работу скачали: 258 чел.

Понятие информации. Виды и структура информации. Геометрическая, комбинаторная и аддитивная мера Хартли.

Понятие информации

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

Циклы обращения информации:

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

Основные определения

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

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

Сообщения – конкретные сведения, получаемые об обьекте.

Случайные сообщения – например сообщения о дополнительном экзамене.

Детерминированные сообщения – например сообщения о траектории полета запущенной ракеты.

Сообщения передаются в систему связи в непрерывном (аналоговом) или дискретном (цифровом) виде.

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

Кодирование информации –преобразование формы представления информации с целью адаптации ее передачи по каналам связи.

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

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

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

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

степени истинности или ложности информации;
1. пустой (нулевой), добротной (положительной) и дезинформацией (отрицательной);
2. динамической энтропии - положительной информация уменьшает неопределенность ситуации, отрицательная (дезинформация) – увеличивает;
3. функцией существенности информации для отражения степени ее важности с учетом времени и пространства;
4. тезауруса («запас знаний») для самообучения и восстановления информации в приемнике при передаче в условиях шумов.

Виды структурной меры

Геометрическая мера

Определение количества информации геометрическим методом сводится к измерению длины линии, площади или обьема геометрической модели данного информационного комплекса в количестве дискретных величин – определенных квантов или букв словаря, например метрах, фунтах, пинтах. Если дискретные отчеты осуществляются по осям соответственно через интервалы x; y; z, то непрерывные координаты распадаются на кванты, количество которых составляет: mx = X/x; my = Y/y; mz = Z/z; Тогда количество информации в полном комплексе XYZ, опр. геометрическим методом равно в квантах: M = mx my mz

Комбинаторная мера

Количество информации в комбинаторной мере вычисляется как количество комбинаций элементов.

Сочетания из h элементов по l различаются составом элементов. Их возможное число равно:

Q = Clh = h*(h-1)…(h-l+1)/l!

Например число сочетаний из трехбуквенного алфавита А, Б, В по 2 будет равно 3: АБ, АВ, БВ.

2. Перестановки h элементов различаются их порядком. Число возможных перестановок h эле ментов:

Q = Пh = h!

Например число перестановок букв А, Б, В будет равно 6: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

3. Размещения из h элементов по l различаются составом элементов и их порядком. Возможное число:

Q = Plh = h*(h-1)…(h-l+1)

Например число размещений букв А, Б, В по 2 будет равно 6: АБ, БА, АВ, ВА, БВ, ВБ.

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

Аддитивная мера (Хартли)

Определение аддитивной меры исходит из позиционной системы счисления.

Глубиной h будем называть количество различных элементов (знаков, букв) содержащемся в принятом алфавите. Глубина числа соответствует основанию системы счисления и кодирования.

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

Количество чисел, которое можно представить при глубине h и длине l составит: Q = hl

Например, при глубине h = 3 для трехбуквенного алфавита А, Б, В и длине l = 2 для двухразрядного кода количество чисел будет равно 9: АА, АБ, АВ, БА, ББ, БВ, ВА, ВБ, ВВ.

Вследствие показательного закона зависимости Q от l число Q не является удобной мерой для оценки информационной емкости. Поэтому Хартли ввел аддитивную двоичную логарифмическую меру, позволяющую вычислять количество информации I в двоичных единицах: I = log2 Q = log2hl = l*log2h

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

Составим таблицу, показывающую соотношение h и l при примерно одинаковом обьеме Q = 1000:

l = log2Q / log2 h

h	1000	32	10	4	3	2	1
l	1	2	3	5	6	10	1000

Исследование гиперболической зависимости при минимизации произведения h * l дает в результате h = е = 2.7.. . Таким образом можно констатировать, что оптимальным основанием для системы счисления кодов является h = 3.

Статистическая мера информации. Связь энтропии с количеством информации.

Связь между энтропией и количеством информации.

Ансамблем называется полная группа событий, с известным распределением вероятностей, составляющих в сумме единицу. Р1+Р2+...+Рi+…+Рk=1

Энтропия H характеризует неопределенность априорного состояния ансамбля событий, а количество информации I - мера снятие неопределенности при получении сообщения о событии. Количественно мера информация совпадает с мерой измерения энтропии. Например, ансамбль знаний студента до лекции был: У1, У2,…Ут,…Ук, где Ук – конкретная область научных дисциплин со своими вероятностями познания: Р(У1), Р(У2),… Р(Ут)… Р(Ук) (т – индекс для дисциплины «Теория информации»). Ситуация априорно характеризовалась энтропией Н1. После получения информации на лекции энтропия уменьшилась до Н2, так как вероятность познания Р(Ут) возросла, а значит и уменьшилась неопределенность по отношению к дисциплине «Теория информации», а также в какой-то мере упорядочился ансамбль знаний. Тогда количество информации, полученное студентом I = H1 - H2

Рассмотрим ансамбль случайных дискретных событий Х: Х(х1, х2,.. хi,..хN) , где хi – конкретные случайные события с вероятностями: р(x1), р(x2),.. р(xi),…р(x N)

Очевидно, что чем меньше априорная вероятность i-го события (снег в Африке), тем большую информацию несет сообщение этого события, и наоборот, чем вероятнее событие (лекция закончится до обеда), тем меньше информации в сообщении о событии. В предельном случае, когда вероятность события = 1 (детерминированное событие – «за зимой следует весна»), то количество информации о событии должно быть равно нулю. Поэтому количество информации можно выразить через величину 1/ р(xi). Однако формула I = 1/ p(xi) для граничных значений не подходит, так как I = ∞ при p(xi) = 0 и I = 1 при p(xi) = 1).

Мера измерения количества информации для дискретных случайных сообщений впервые была предложена Шенноном в 1948г, а затем более строго была определена советским ученым Хинчиным А.Я.:

I = loga 1/ p

Количество информации, содержащееся в конкретном сообщении о событии xi:

I(xi) = loga 1/p(xi) = - loga р(хi )

Для того, чтобы мера количества информации не зависела от конкретного события, а характеризовала совокупность сообщений ансамбля Х вводится усредненная статистическая оценка, как математическое ожидание элементов I(xi) по всем xi (1≤ i ≤ N) - среднее количество информации, содержащееся в сообщениях ансамбля Х:

I(Х) = - I(xi) = -p(xi)loga р(хi )

Основания логарифма «а» определяет единицу измерения количества информации. Двоичная единица, соответствующая основанию, равному двум, называется битом. Основанию е = 2,718, соответствует натуральная единица – нит (в математике), 1 нит = 1,44269 бит. Основанию, равному 10, соответствует десятичная единица – дит (в астрономии) или хартли, 1 дит = 3.32193 бит.

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

Структура системы передачи информации. Виды кодирования.

Основные определения

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

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

Сообщения – конкретные сведения, получаемые об обьекте.

Случайные сообщения – например сообщения о дополнительном экзамене.

Детерминированные сообщения – например сообщения о траектории полета запущенной ракеты.

Сообщения передаются в систему связи в непрерывном (аналоговом) или дискретном (цифровом) виде.

Непрерывные каналы связи – радиоканал, звуковой, световой каналы;

Дискретные каналы связи – двоичный последовательный порт типа RS232C, цифровой видео интерфейс FireWire (огненный провод), Compacl PCI$

Количество информации дискретных сообщений. Определение бита и байта.

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

Энтропия H характеризует неопределенность априорного состояния ансамбля событий, а

количество информации I - мера снятие неопределенности при получении сообщения о событии.

Количественно мера информация совпадает с мерой измерения энтропии.

I = loga 1/ p

Количество информации, содержащееся в конкретном сообщении о событии xi:

I(xi) = loga 1/p(xi) = - loga р(хi )

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

Свойства количества информации дискретных сообщений:

1. Количество информации - вещественная, неотрицательная и ограниченная величина 0=< I(Х)<=M

2. Количество информации детерминированных сообщений равно нулю. I(xi) = 0 для p(xi) = 1

3. Количество информации максимально, если сообщения равновероятны.

Imax (X) = - - log2 р(х ) = log2 1/pi = log2N

I=1

Доказательство 1.

I(Х) = -p(xi) log2 р(хi) – вещественная, так как p(xi) – вещественная.
I(Х) = -p(xi) log2 р(хi) – неотрицательная, так как 0 ≤ p(xi) ≤1 и log2 р(хi ) ≤ 0 .
I(Х) = -p(xi) log2 р(хi) – ограниченная, т.к. имеет максимальное ограниченное значение (доказательство 3).

Доказательство 2.

I(Х) = - p(xi) log2 р(хi) = 0 для р(хi) = 1.

Рассмотрим предел p(xi) log2 р(хi) при хi → 0.

Lim p(xi) log2 р(хi) = | y = log2 р(хi), z = 1/p(xi) | = Lim y/z = Lim y'/z' =

= - Lim {1/ р(хi)} /{1/ р(хi)2} = - Lim р(хi) = 0.

Доказательство 3.

Максимально возможное количество информации, содержащееся в N сообщениях, получается для случая равномерного распределения, то есть при p(xi )= 1/N

Imax (X) = - (1/N)* log2 р(х ) = log2 1/p(xi) = log2 N

И совпадает с аддитивной мерой по формуле Хартли, где Q = N. Совпадение оценок количества информации по Шеннону и Хартли свидетельствует о том, что при максимально эффективном статистическом состоянии ансамбля событий, а именно при равновероятности всех событий ансамбля, статистическая информационная емкость полностью использует возможности структурно построения информационной системы для ансамбля событий. В случае неравных вероятностей количество информации по Шеннону меньше информационной емкости ансамбля.

Передача информации по каналу без помех. Основные характеристики.

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

2. Рассмотрим основные характеристики систем передачи данных по каналу связи без ошибок: V(x) и C.

3. V(X).Среднее количество информации, передаваемое по каналу в единицу времени, называется скоростью передачи информации: V(x).

V(x) = lim(I(x)/T)

T

4. Пропускная способность к.с. является важнейшей характеристикой к.с. и формально определяется как максимально возможная скорость передачи информации: C = {V(x)}max

5. Одним из важнейших вопросов проектирования системы передачи данных является согласование V и C:

а) Для эффективного использования канала связи необходимо принять меры к V(x) C;

б) Вместе с тем, для передачи всей информации по каналу связи (отсутствие режима «захлебывания» канала связи): V(x) < C.

6. Впервые эти вопросы были исследованы Шенноном, показавшим, что основным условием динамического согласования источника сообщений и информационного канала является соотношение: V(x)  C

Рассмотрим это соотношение на примере дискретного канала без помех.

Постановка задачи: а) как определить (оценить) V(x) и C?

б) практический вопрос: V  C. Как?

1. Дискретный источник информации создает сообщение из X={X1, X2, … Xn} – символов первичного алфавита, которые подаются на вход канала. В любом реальном канале всегда присутствуют помехи. Однако, если уровень помех так мал, что вероятность искажения приблизительно равно нулю, то можно считать, что: символы передаются без искажений.

а) При этом среднее количество информации, переносимое одним символом: I(x) = H(x),

а максимальное значение среднего количества информации на символ Hmax(Х), получается в случае: P1 = P2 = … = Pn = ½, при этом, Hmax(X) = log2n

б) скорость информации будет определяться: V(X) = 1/ *H(X), где  - длительность передачи символа; H(X) – количество информации переносимое одним символом. V – скорость передачи сообщения = сообщ./с

в) по соотношению: V(x)  C

V(x) = C – для случая, когда V(X) = Vmax (X),

т.е. C = max{1/ * H(X)}= 1/ *max[H(X)] = 1/ * log2n, где 1/ - чистая характеристика канала.

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

Необходимо различать C и V(X).

а) С – зависит только от характеристик канала; V(X) – от H(X) – статистического распределения источника сообщений; ограничена сверху С.

б) по размерности V(X) – для двоичного канала измеряется в бит/сек. С – количество двоичных разрядов (двоичных единиц), проходящих в единицу времени по каналу. С = дв.ед./сек.

в) V(x)  C , т.е. в пределе один двоичный знак может нести информацию не более 1 бита (т.е. двоичный разряд не может содержать более 1 бита информации). 0  I дв. разр.  1 бита

Для каждого источника сообщений соотношение V(X)  C может быть достигнуто специальным выбором способа кодирования сигналов (сообщений).

О степени приближения скорости передачи информации V(X) к пропускной способности канала утверждает теорема Шеннона для дискретного канала без помех.

Первая теорема Шеннона и её следствие.

Первая теорема Шеннона (об эффективности передачи информации по каналу связи)

Пусть источник сообщений характеризуется средним количеством информации I [бит/сообщ.], а канал связи имеет пропускную способность С дв.ед./с. Тогда можно закодировать сообщение на выходе источника таким образом, чтобы передавать сообщения по каналу со средней скоростью V(X) = C -  бит/сек, где   сколь угодно малая величина. V(X) – практический параметр. Передавать сообщение со средней скоростью V(X)  C/I – невозможно.

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

Первая теорема Шеннона утверждает, что существует системное кодирование, обеспечивающее V(X)  C, однако не указывает конкретную процедуру кодирования.

Вместе с тем,

а) V(X)  C осуществляется для I(X) = max,

б) что, в свою очередь, обеспечивается при равномерном распределении передаваемых символов сообщения.

Подобные процедуры кодирования, обеспечивающие V(X)  C, называются эффективными (оптимальными) и, впервые, были предложены Шенноном, Фано, Хаффменом.

Статистическое кодирование.

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

Кодирование, учитывающее статистические особенности источника сообщений называется статистическим (эффективным) кодированием.

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

при заданной статистике сообщений {Pi}формировать кодовые комбинации, допускающие V(X)  C
возможность однозначного декодирования сигналов на приемной стороне

Для двоичного канала с отсутствием статистических связей между символами этим требованиям удовлетворяет код Шеннона-Фано.

Известно, что V  C выполняется при равной вероятности появления различных сообщений.

В соответствии с этим, построение кода выполняется по следующей последовательности:

А) все буквы алфавита выписывают столбцом в порядке убывания вероятности;

Б) столбец последовательно делят на группы с приблизительно равной суммарной вероятностью.

При этом:

верхней половине  «0»;
нижней половине  «1»;

Приближение V к C было осуществлено за счет:

“качественно” – наиболее часто передаваемые сообщения кодировались наиболее короткой длиной двоичных разрядов, и наоборот.
“количественно” – (более строго) за счет нового кодирования получено равномерное распределение i. После кодирования сообщения, буквы алфавита Zi были заменены на значения двоичных разрядов j.

Причиной C > V(X) и Kотн. эфф. 1 при использовании эффективного способа кодирования является невозможность разбиения сообщений { Xi } на подгруппы с достаточно близкой вероятностью.

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

Коды Шеннона-Фано.

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

при заданной статистике сообщений {Pi}формировать кодовые комбинации, допускающие V(X)  C
возможность однозначного декодирования сигналов на приемной стороне

Для двоичного канала этим требованиям удовлетворяет код Шеннона-Фано.

Известно, что V  C выполняется при равной вероятности появления различных сообщений.

В соответствии с этим, построение кода выполняется по следующей последовательности:

А) все буквы алфавита выписывают столбцом в порядке убывания вероятности;

Б) столбец последовательно делят на группы с приблизительно равной суммарной вероятностью.

При этом:

верхней половине  «0»;
нижней половине  «1»;

В качестве примера рассмотрим алфавит сообщений из 8 букв (для С = 3000 дв.ед./с)

	Pi	Эффективное кодирование								Равномерное кодирование
		1	2	3	4	5	6	7	8		1	2	3
Z1	½	0									0	0	0
Z2	¼	1	0								0	0	1
Z3	⅛	1	1	0							0	1	0
Z4	1⁄₁₆	1	1	1	0						0	1	1
Z5	1⁄₃₂	1	1	1	1	0					1	0	0
Z6	1⁄₆₄	1	1	1	1	1	0				1	0	1
Z7	1⁄₁₂₈	1	1	1	1	1	1	0			1	1	0
Z8	1⁄₁₂₈	1	1	1	1	1	1	1			1	1	1

Особенности

В) Полученный код является неравномерным, т.к. длина кодовых комбинаций находится в обратной зависимости от их вероятности.

Г) Из таблицы видно, что ни одна из кодовых комбинаций не является началом другой. Этим обеспечивается свойство префикса – разделимости кодовых комбинаций, а, следовательно, и возможности однозначного декодирования сообщений.

Оценим скорость передачи информации для методов:

а) статистического кодирования;

V = C *I /ср.

На передачу каждого сообщения в среднем требуется V = C/  1500 сообщ./с

ср. = Pi *i = 163/64 дв.разр. ср.= H(X)

i=1

H(X) = - Pi *log2Pi =163/64 бит/символ. Для C = 3000 дв.ед./с  V(Z) = 3000 бит/с;

i=1

б) равномерного кодирования;

Каждому сообщению требуется 3 двоичных разряда равн.= log2N, а каждое сообщение Zi содержит:

I(Z) = H(Z) = - Pi*log2Pi = 163/64 бит/сообщ.

i=1

Поэтому, при C = 3000 дв.ед./с имеем: V = 1000сообщ./с V(Z) = 1*1000 = 1984 бит/с

В рассмотренном примере получено:

V(Z) = C и Kотн. =1 -идеальный случай.

Это удалось получить потому, что значения P(Zi) заданы так, что подгруппы точно делились пополам.

Метод Хаффмена.

при заданной статистике сообщений {Pi}формировать кодовые комбинации, допускающие V(X)  C
возможность однозначного декодирования сигналов на приемной стороне

Для двоичного канала этим требованиям удовлетворяет код Шеннона-Фано.

Дальнейшим возможным способом повышения скорости передачи информации является кодирование не каждого символа сообщения, а группы из двух символов, что позволяет получить новый набор из 9 групп {XiXj} и возможность деления на более близкие по суммарной вероятности подгруппы:

Сообщение Yk = Xi *Xj Вероятность PYk = PXi *PXj

Рассмотренная процедура кодирования, основанная на методе Шеннона-Фано, не всегда является однозначной, так как возможны различные варианты разбиения сообщения на подгруппы с близкими вероятностями (пример:{Y1}и {Y2÷Y9}). Рассмотрим последовательность кодирования {Yi}по методу Хаффмена, гарантирующему однозначность разбиения на подгруппы и являющегося более рациональным при кодировании достаточно больших групп сообщений.

Метод Хаффмена – гарантирует однозначное построение кода с наименьшим для данного распределения {Pi} - ср. – средним числом двоичных разбиений на сообщения.

1. Буквы алфавита сообщения выписывают в основной столбец в порядке убывания вероятностей.

2. Две последние буквы объединяются в одну вспомогат., которой приписывается суммарная вероятность.

3. Процесс продолжается до получения единственной буквы.

	Вероят -ность	1	2	3	4	5	6	7	8	9
Y1	0,4225	0,4225	0,4225	0,4225	0,4225	0,4225	0,4225	0,5775	1,0000
Y2	0,1495	1495	1495	1495	1560	2720	0,3055	0,4225
Y4	0,1495	1495	1495	1495	1495	1560	0,2720
Y3	0,0780	0780	0780	1225	1495	1495
Y7	0,0780	0780	0780	0780	1225
Y5	0,0529		0696	0780
Y6	0,0276	0420
Y8	0,0276	0276
Y9	0,0144

Кодирование сообщений осуществляется по результатам построения «кодового дерева».

Y1 Y2 Y4 Y3 Y7 Y5 Y6 Y8 Y9

0 110 101 1111 1110 1000 100111 10010 100110

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

характеристики каналов с помехами;
виды каналов;
количество информации, передаваемой по каналу с помехами.

Характеристики каналов с помехами

Так как принимаемые из канала сообщения, вследствие воздействия помех, отличаются от передаваемых в канал ,то рассмотрим две системы дискретных сигналов: xi  {X} к.с. yj {Y}

Передаваемые сообщения Принимаемые сообщения

P(x1) * x1 * y1 P(y1)

P(xi-1) * xi-1 * yi-1 P(yi-1)

P(xi) * xi * yi P(yi)

P(xi+1) * xi+1 * yi+1 P(yi+1)

* yj

P(xn) * xn * yn P(yn)

А) Для канала без помех: Однозначное соответствие xi  yi

Б) Для канала с помехами:

xi может перейти в любой yj  {Y};
прием yj достоверно означает, передан один из xi  {X};

Источник характеризуется априорным распределением P(xi);

После получения на приемной стороне yj , источник информации может быть охарактеризован апостериорным распределением P(xi/yj). Где P(xi/yj) - вероятность, называемая условной вероятностью передачи в канал символа xi при условии, что из канала был получен символ yj.

Вероятностный характер связи {xi} с {yj} (т.е. между алфавитами канала передачи информации) полностью определяется матрицей условных вероятностей:

P11 P12 … P1n основная характеристика к.с.

P21 P22 … P2n с помехами

… P (xi/yj) …

Pn1 Pn2 … Pnn

А) Pij– определяется путем статистической обработки результатов экспериментальных исследований.

Б) Свойства Pij: по диагонали – вероятность безошибочной передачи, остальные – ошибочной передачи.

Виды каналов с помехами.

Каналы без памяти – каналы, у которых на каждый предаваемый сигнал, помехи воздействуют независимо от того, какие сигналы предавались раньше. Вид Pij– постоянный. В настоящее время основные выводы теории информации получены применительно к каналам без памяти. В дальнейшем будем рассматривать каналы без памяти.
Нестационарные каналы – элементы матрицы условных вероятностей зависят от времени {Pij(t)}.
Стационарные каналы имеют матрицу Pij, элементы которой не зависят от времени. Практически все реальные каналы являются нестационарными. Исследования нестационарных каналов является более сложным и трудоемким процессом, поэтому при анализе они представляются как последовательность стационарных каналов. То есть, для конкретных отрезков времени нестационарные каналы апроксимируются стационарными.
Канал, имеющий симметричную Pij, т.е. Pij = Pji , называются симметричными.
Дискретный канал, по которому передаются только два элементарных сигнала, называют бинарным.

Если P10 = P01= q – вероятность ошибочной передачи, и P00 = P11= p – вероятность правильной передачи, то такой канал называют бинарным симметричным:

Количество информации, предаваемой по каналу с помехами.

Для матрицы общего вида Pijоценим кол-во инф., содержится в принятом сообщении yj относительно xi:

А) неопределенность относительно xi до получения yj характеризуется его энтропией: H(xi) = - log2P(xi). Для канала без помех, получив yj из канала связи, мы полностью сняли о нем неопределенность, т.е. получили количество информации: Ii = H(xi) = - log2P(xi).

Б) Вследствие воздействия помех после получения yj мы полностью не сняли неопределенность, а лишь уменьшили её до значения H(xi/yj) = - log2P(xi/yi).

В) Разница неопределённостей до и после получения сообщения yj составила количество информации, содержащееся в сообщении yj относительно xi: I(xi/yi) = H(xi) - H(xi/yj) = log2(P(xi/yi)/P(xi)).

Среднее количество информации о всем множестве X , содержащееся в принятом сообщении yj:

n n

I(X/yi) = P(xi/yj) * I(xi/yj) = P(xi/yj) * log2(P(xi/yi)/P(xi));

i=1 i=1

Среднее количество информации, содержащееся во всей совокупности принятых сообщений Y относительно всей совокупности преданных сообщений X (усреднение по всем yj):

n n n

I(X/Y) = P(yj) * I(X/yj) =   P(yj)* P(xi/yj) * log2(P(xi/yj)/P(xi)); Прим: P(yj)* P(xi/yj) = P(xi ,yj) = P(xi)* P(yj/xi)

j=1 j=1 i=1 P(xi ,yj)

Вывод: Для определения среднего кол-ва инф. передаваемой по каналу с помехами необходимо определение:

А) P(xi/yj) – канальной матрицы условной вероятности;

Б) P(xi) – априорной распределенной вероятности алфавита X.

Проведя соответствующие преобразования, получим:

А) I(X/Y) = - P(xi) * log2P(xi) +   P(xi,yj) * log2P(xi/yj);

i i j

H(X) H(X/Y)

Безусловная энтропия Условная энтропия

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

А) отсутствие помех

между xi и yj  однозначное соответствие (соотношение);
Pij вырождается в единичную диагональную матрицу;
H(X/Y) = 0 –формально следует из подстановки в основное выражение, т.е. I(X/Y) = I(X) = H(X).

Б) при уровне помех, обеспечивающих P(xi/y1) P(xi/y2)…, имеем H(X) = H(X/Y), т.е. безусловная энтропия (до сообщения) = условной энтропии (после сообщения). Таким образом, полученное сообщение yj не снизило на сколько-нибудь неопределенность относительно xi. Иными словами, количество информации, содержащееся в yj относительно xi=0 I =H(X) - H(X/Y) = 0.

Вывод: Информационные характеристики реальных каналов связи лежат между двумя предельными случаями: H(X)  I  0 .

Скорость передачи и пропускная способность дискретного канала с помехами.

Скорость передачи:

V(X/Y) = v * I = v * [H(X) – H(X/Y)] = 1/ * [ -P(xi) * log2P(xi) +P(xi,yj)*log2P(xi/yj) ]

скорость передачи сообщений ↵ ↳ количество информации время ↵ i i j

на одно сообщение передачи первого сообщения

2. Пропускная способность C:

Согласно определения: C= Vmax = max{1/ * I}= 1/*max{-p(xi) * log2p(xi) +P(xi,yj)*log2P(xi/yj)}

i i j

Поиск максимума осуществляется с помощью варьирования значений априорных вероятностей [p(xi)] при постоянных значениях элементов матрицы условных вероятностей, которые являются характеристиками каналов связи, т.е. варьируем статистику источника сообщений.

3. Определим C для бинарного симметричного канала связи.

Анализ выражения

C = 1/ max{-P0 * log2P0 – P1* log2P1} + [p*log2p + q *log2q] , получим его макс. при условии P0 = P1.

H(X) H(X/Y)

При этом: C = 1/ * [ log22 + q* log2q + p* log2p]

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

Вторая теорема Шеннона и её следствие.

Основным условием, обеспечивающим достоверную, т.е. с любой, наперед заданной точностью , передачу информации по каналу связи с помехами является следующее соотношение: Vскор.передачи  C

Возникает вопрос: как обеспечить Vскор. передачи и обеспечить достоверность?

Для дискретного канала с помехами доказана теорема (вторая теорема Шеннона): если скорость информации (эффективность и достоверность переданных сообщений) не превышает пропускную способность канала связи, т.е. справедливо равенство V(X) = C - , где  - любая сколь угодно малая величина, то существует такой способ кодирования, который обеспечит передачу всех сообщений, вырабатываемых источником, а вероятность ошибочного опознавания будет сколь угодно малой.

Следствием теоремы является утверждение, что не существует метола кодирования, позволяющего вести передачу информации со скоростью выше C и с малой вероятностью ошибки. Иными словами, если V*IC, то можно подобрать такой код, который позволяет передавать всю информацию с погрешностью  0.

Очевидно, что при наличии помех достоверность передачи информации можно повысить, например, путем многократного повторения каждой буквы, что ведет к снижению скорости передачи (если  , то и V).

Интуитивно кажется, что для обеспечения нулевой ошибки число повторений должно быть бесконечным, а скорость передачи информации V 0. Однако, теорема утверждает, что при   можно подобрать такой код, при котором V  0 - конечная величина. Таким образом, данная теорема устанавливает соотношения при передаче по каналу с помехами между скоростью сообщений создаваемых источником V, пропускной способностью канала C и достоверностью передачи.

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

Помехи  Pij 

C = F (структура реального канала;  Pij )

P(xi)

V(X)  C - , то существует способ кодирования

xi yj

V(X)

Особенности эффективного кодирования:

Оптимальные (эффективные) коды являются неравномерными.
Неравномерные коды Шеннона и Хаффмана являются префиксными кодами, т.е. для различия кодовых комбинаций не требуется специального разделительного знака.
При практической реализации эффективных кодов неизбежна задержка в передаче информации. Это связано с тем, что наибольший эффект достигается при кодировании длинными сообщениями, а это, в свою очередь, приводит к необходимости накапливать буквы, поступающие от источника информации.

Для двоичного канала.

“С” определяет число двоичных разрядов / с, передаваемых по двоичному каналу: C=1/чувств.
C = max V = max Iсообщ./сообщ. = max Iсообщ./(ср.*сообщ.) = 1/сообщ. * max {Iсообщ./ср.} То есть для случая n2k и {xi} – равновероятные, обеспечение V C достигается только за счет кодирования сложных сообщений с использованием статистических способов кодирования.

Статистическое кодирование:

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

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

в) выполнение 01 или 10  префиксности полученного неравномерного кода.

При использовании статистического кодирования осуществляется:

А) выравнивание вероятности появления 0 и 1;

Б) статистическая независимость 0 и 1;

x1 = 01  p = ½ пример равной вероятности появления

x2 = 10  p = ½ 0 и 1 по их статистической зависимости

Таким образом:

а) если n = 2k , то C = 1/ * max log2n = log2n/ , т.е. C = V для равномерного распределения {xi} с равномерным кодированием, т.к. при этом появлении 0 и 1 независимы.

б) если n  2k ,то C = 1/дв. *max {Iср./ср.} с использованием кодирования сложных сообщений.

Классификация помехоустойчивых кодов.

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

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

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

Основная идея кодирования

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

а) Помехоустойчивые коды делятся на: обнаруживающие ошибки и исправляющие ошибки.

б) Наиболее широкое применение на практике получил двоичный код, код с основанием q = 2

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

г) В зависимости от методов построения кодов и способов введения избыточности коды делятся на 2 класса:

- блоковые коды; - непрерывные коды

Классификация помехоустойчивых кодов.

Код Хэмминга:

а) 1ый блоковый код, исправляющий.1ые ошибки Хеммингом активно, используется и в н.в., но откровенно своей слабостью, по сравнению с обещанным Шенноном более сильными кодами.

б) Основной сдвиг при построении кодов произошел в 5060 годы при использовании серьезной теории теории полей Галуа) и построении на их основе циклических кодов (Однако использование кодов БЧХ и РС стало возможным только с учетом применения средств цифровой техники. Однако коды БЧХ и Рида-Соломона еще далеки от кодов предсказанных Шенноном (при большой длине блока происходит резкое увеличение избыточности). Т.е. коды БЧХ и РС имеют характеристики близкие к предсказанным только при относительно небольшой длине блока.

в) Только в 70е годы в теории блоковых кодов (теоретически) удалось приблизиться к кодам, предсказанным Шенноном, т.е. кодам имеющим большую длину блока и очень хорошие соотношения избыточности и помехозащищенности. На основе кодов БЧХ разработана методика построения н.м. альтернативных кодов, к которым в первую очередь относятся коды Гоппы.

Привлекательность альтернативных кодов состоит в том, что имеются «хорошие» коды большой длины. При этом отношения k/n и dmin/n при бесконечном возрастании n: Lim (k/n(dmin/n))  0. при n  

Принцип построения помехоустойчивых кодов. Пример.

1) Как уже отмечалось выше, основная идея в искусственном введении избыточности.

2) Пусть необходимо передать N различных сообщений.

а) При передаче по двоичным каналам и отсутствии помех длина кодовой комбинации определяется только необходимыми информационными разрядами k: k=[log2N].

б) Кодирование заключается во введен дополнительной избыточности в виде проверочных разрядов r.

в) n = k + r; (n,k) k – информационные разряды;

код

k r r – проверочные разряды;

Значение проверочных разрядов определяется:

выбранным алгоритмом кодирования;
значениями информационных разрядов.

г)

Общее число разрешенных кодовых комбинаций (т.е. пока не содержащих ошибки), передаваемых в канал связи: N1 =2k;
Общее число принимаемых комбинаций (с учетом ошибочных) – возможных кодовых комбинаций – N0 =2n = 2k + r;
Число ошибочных (запрещенных) кодовых комбинаций: N2 = N0 – N1 = 2n – 2k; n, k – коды.

д) Процедура декодирования состоит в определении: к какому подмножеству принадлежит принятая из канала кодовая комбинация:

а) если к разрешенному, то считается что полученная комбинация – не содержит ошибок;

б) если к запрещенному – содержит ошибки.

Передающая сторона Канал связи Принимающая сторона

(этап кодирования) ei (этап декодирования)

разрешенная (нет ошибок)

k r

задано определяется

Ei Ei

запрещенная (исправление

ошибок – для коррктирую-

щих кодов)

Требование к основным параметрам кодов, (k, r, dmin), исходя из методов кодирования и декодирования.

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

а) Пусть требуется построить код ,обнаруживающий все ошибки кратностью t и ниже.Для этого из множества возможных комбинаций N0 необходимо выбрать N1 – разрешенных комбинаций, так, чтобы под действием ошибки разрешенная комбинация не переходила бы в разрешенную. Но поскольку вес вектора e: (e)  t, это значит, что d(Ej, Ej + ei)  t. Для этого необходимо, чтобы Ei, Ej отличалиь более, чем в t разрядах.

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

Dmin  t + 1

2) Для кодов, исправляющих ошибки необходимо, чтобы ошибки обеспечивали переход каждой решенной комбинации в переход в заранее выделенное подмножество запрещенных кодовых комбинаций, сформированное вокруг данной разрешенной комбинации:

По аналогии с кодами, обнаруживающими ошибки: dmin  2t + 1. Т.е. разрешенные кодовые комбинации должны различаться более, чем в 2t разрядах.

Характеристики блоковых кодов.
Количество разрядов (n) в кодовой комбинации называется длиной кода (длиной блока).

101000101 – кодовая комбинация обозначается: E1 = 101000101

n =9

2) Количество “1” в кодовой комбинации называется весом кодовой комбинации ().

(E1) = 4

Расстояние между кодами : d.

Расстояние по Хэммингу между двумя двоичными последовательностями (E1, E2) длины n называется число позиций, в которых они различны. Обозначается: d(E1, E2).

а) E1 = 0100101

d(E1, E2) = 3;

E2 = 1000100

б) d(E1, E2) = (E1  E2)

4) Минимальное кодовое расстояние : dmin.

Минимальное расстояние равно наименьшему из всех расстояний по Хэммингу между различными парами кодовых слов, т.е.

dmin = min (E1, E2),

Ei, Ej – всевозможные кодовые слова, где ij

E1= 0101010

d(E1, E2) = 5 dmin = 5 d(E1, E3) = 5

E2= 0000101 E3= 1110001

d(E2, E3) = 5

Характеристики ошибок (помех)

При прохождении кодовой комбинации по каналу связи под влиянием помех возможно изменение кодовой последовательности.

Ошибки проявляются в том, что в одном или нескольких разрядах кодовой комбинации: 01 10.

а) Если переход происходит в одном разряде – одиночная ошибка;

б) Если в нескольких разрядах – многократная ошибка (двойная, тройная и т.д.).

e – вектор ошибки;

n(e) = n(E);
(e) – называется кратностью ошибки t;
E  e = Ẽ – ошибочная кодовая комбинация;

E = 0100110 – б/ошибочная кодовая комбинация.

в) Многократные ошибки

независимые ошибки пакеты ошибки

(позиция одной ошибки не зависит от другой) связанные между собой (как правило)

единой причиной.

Пакеты ошибок характеризуются длиной пакета (l).

Пакетом ошибок длины l называется комбинация ошибок, расположенных среди l последовательных компонент, первая и последняя из которых отличны от 0.

l = 001011010000

l = 6

Последовательность выбора параметров блочного кода.

Рассмотрим последовательность выбора параметров кода (n, r) для заданной корректирующей способности (t – кратные исправленные ошибки).

Задача: а) объем источника сообщений N – число различных сообщений;

б) число векторов ошибок, которые необходимо исправить Ne,

Определить: k, r, n.

1) Количество информационных символов: k = [log2N];

2) Полное число ошибочных комбинаций, которые необходимо исправить: Ne2k.

По определению – число запрещенных комбинаций: N2 = N0 – N1 = 2n – 2k  Ne2k

3) Отсюда необходимо условие на исправление всех ошибок: 2k(Ne + 1)  2n Отсюда: 2n-k=r  Ne + 1

Следствие: для построения надежного кода необходима полная информация (в виде Ne) о всех ошибках, действующих в к.с. Т.о. построение кода начинается со сбора информации об ошибках, действующих в канале (статистическая обработка).

Т.о. для построения кода, исправляющего t ошибок необходимо одновременное выполнение:

dmin  2t + 1 и 2r  Ne + 1

Заключение.

Рассмотрели:

а) Общий подход к построению корректирующих блочных кодов;

б) Основные параметры кодов и соотношения между ними.

Переходим:

а) К рассмотрению конкретных алгоритмов построения кодов по заданным

характеристикам: k, r, dmin.

б) При этом упор будет сделан: - алгоритмы построения корректирующих кодов;

- их сруктурную реализацию.

Рассмотрим проблему поиска методов построения кодов с заданными параметрами (n, k) и корректирующими свойствами.

Машинный поиск по множеству всех Построение теории кодов.

возможных кодов.

а) Определим число возможных кодов для

заданных n и k: имеется 2k слов каждое длинной n,

т.е. имеем двоичные последовательности: R = n2k;

б) Все коды необходимо («машинно») проверить и

выбрать с требуемыми характеристиками.

Пример: для весьма умеренного (по современным

понятиям) (n, k) = (40, 20) имеем число кодов ~ 10

10.000.000 = 107;

Примеры блочных кодов.

1. Простые коды с проверкой на четность.

Коды с низкой избыточностью и плохими корректирующими характеристиками:

(k +1, k, 2) – коды с dmin = 2 – исправлять не могут, а могут обнаруживать

все одиночные ошибки (все нечетные ошибки, т.е. в общем

случае ~ 50% всевозможных ошибок).

10000  10000.1

Пример: ИРПС – для защиты передаваемых байтов.

2. Простые коды с повторением.

Коды с высокой избыточностью и хорошими корректирующими возможностями. Один информационный символ повторяется n (n – обычно нечетно) раз

0  00000

1  11111

(n, 1, n) dmin, т.е. данный код может исправить ~ код Рида-Маклера (т.н. код с голосованием), т.е. декодирование осуществлялось с помощью мажоритарного метода, был использован при передаче фотографий Марса космическим кораблем «Маритер» в 1972 г. В н.в. для этой цели разработаны более эффективные коды.

Инверсные коды.

В основу построения инверсного кода положен метод повторения исходной комбинации, если она содержит четное число «1» (w – четное), и выбор в качестве проверочных разрядов – инверсии исходной комбинации, если последняя содержит нечетное число «1»

Пример: а.) 0110011 0110011

четное

б.) 0110001 1001110

н/четные

код (2к, к)

а.) Алгоритм декодирования:

-А = информационной части;

А, - если А содержит четное число «1»;

В =

А,- если А содержит нечетное число «1»;

А = В – нет ошибок;

А  В – есть ошибки;

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

Пример: передаваемая

комбинация

0111 1000 01111000 0101.1000

А В

Гипотезы:

Ошибка произошла в В (А принята верно) – тройная ошибка
Ошибка произошла в А в втором (справа) разряде одиночная ошибка т.е. наиболее подходит гипотеза 2.

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

Комбинации n – разрядного двоичного кода можно представить как вершины n-мерного единичного куба (2n вершин).

n=1;

n=2;

00 01

Каждой вершине куба соответствует определенная кодовая комбинация.

n=3;

010 110 а) Искажение кодовых комбинаций

011 111 интерпретируется перемещением из одной

вершины в другие.

б) Кратность ошибки – количеством ребер куба

между вершинами.

000 100 в) Расстояние между кодовыми комбинациями

d – число ребер куба, на которое отстоят друг

001 101 от друга вершины, соответствующие

кодовым комбинациям.

1) Обнаружение одиночной ошибки: dmin  2 ( )

Пояснение: а) где разрешенных кодов комбинации

б) где подмножества запрещенных.

Линейные коды.

Самый большой класс разделимых блочных кодов составляют систематические или линейные коды.

k r

…

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

Для двоичных кодов в качестве линейной операции используются сложение по mod 2.

bj = åai

(основаны на применении мат. аппарата алгебры Жегалкина (Å)).

Основное свойство линейного кода: сумма(разность) кодовых комбинаций является также разрешённой кодовой комбинацией.

Пример: [ ] - разрешённая

[ ] - разрешённая

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

Линейные коды образуют алгебраическую группу по отношению к операции сложения по mod 2. В этом смысле они являются групповыми кодами.

Свойство группового кода: (dmin) Минимальное кодовое расстояние между векторами линейного кода равно линейному весу ненулевых кодовых векторов.

Для построения групповых кодов (т.е. перехода от информационных разрядов к полному кодовому слову, включающему также и проверочные разряды, целесообразно использовать специальные матрицы: n * k = (k + r) * k/

Порождающая матрица может быть представлена в виде 2х матриц И(информационной) и П(проверочной) ||G|| = |[И]| |[П]|

a11 a12 … a1k p11 p12 … p1r

Gn,k = a21 a22 … a2k p21 p22 … p2r k

k ……………… ………………..

ak1 ak2 … akk pk1 pk2 … pkr

k r

Получение кодовой комбинации осуществляется путём суммирования элементов ||И|| и параллельного суммирования строк ||П||.

1). На практике установлено, что в качестве информационной матрицы ||И|| удобно брать единичную матрицу в канонической форме:

100…0

Iи = 010…0

………

000…1

2). Строчки образуют матрицы ||C|| = ||И|| ||П|| представляют собой “К” комбинаций(разрешённых) искомого кода. Остальные комбинации кода строятся при помощи образующей матрицы.

Образующая и проверочная матрицы.

Рассмотрим теперь метод построения образующей матрицы

Из свойств группового кода следует, что W  dmin

С другой стороны Wi = Wнi + Wпi  dmin Wп  dmin – Wн

Т.к. вес всех сторон ||Н|| : W11=1, то имеем

Wп  dmin – 1, dmin  t+1 dmin –1  t

Wп  dmin – 1  t  Wп  t

Отсюда: для кодов, обнаруживающих t – кратные ошибки:

достаточные требования Wп (строки)  t

для построения проверочной для кодов, исправляющих t – кратные ошибки :

матрицы Wп (строки)  2t

Рассмотрим частные случаи:

1.) Коды, обнаруживающие одиночную ошибку. dmin = 2 ( N=15, t=1 ) Wп  1

Единая матрица для dmin  2

100…0 1 k k

010…0 1 b1 = aip1i = ai Не что иное, как

001…0 1 i=1 i=1 проверка на четность.

000…1 1

И П

Для dmin  3 проверочная матрица не может быть представлена в общей (единой) форме, т.к. для dmin  3  r зависит от k.

Построение кодовой комбинации E в матричной форме имеет вид:

образующая матрица

E = IGn,k , где I – вектор длины k, компонентами которой являются

информационные разряды.

кодовый вектор информационный

вектор

Пример

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

1. t = 1; N = 16;

2. dmin = 3; Wп = 2; k = [ log15] = 4; 2r > k + r  r = 3;

3. Gп,к = G7,4 =

a1 ..a4 b1.b3

1000 011 b1 = a2 Å a3 Å a4

0100 101 b2 = a1 Å a3 Å a4

0010 110 b3 = a1 Å a2 Å a4

4. E = IGп,к = 0 100.101

Рассмотрим этап депозирования  S1, S2 … Sr;

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

Sj = bj Å pijai  Sj = bj Å bj’; j1r;

i=1

новый старый из канала до передачи

проверочные символы

б.) Sj – называется проверочным синдромом или синдромом ошибок и имеет число разрядов равное: r ( S1, S2 …Sr ). Если w(Sj’) = 0, но нет ошибок; w(Sj)  0, есть ошибки.

в.) Рассмотрим процедуру исправления ошибки по виду Sj (из предыдущего примера E = 0101.101)

Групповой код построен по матрице

1000.011

0100.101 = G7,4

0010.110

0001.111

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

Согласно правилу построения проверочного синдрома

S1’ = (b1,a2,a3,a4)

S2 = (b2,a1,a3,a4)

S3 = (b3,a1,a2,a4)

Определим соответствие между ошибкой в определенном разряде принятой комбинации и видом проверочного синдрома. (Напоминаю, что для удобства полученную кодовую комбинацию будем рассматривать как суперпозицию (данном случае, как сумму по mod2) правильной (разрешенной, передаваемой) кодовой комбинации A и вектора одиночной ошибки e).

2. Пусть информация принята верно, т.е. ни один из разрядов ai, bj не исказился. В этом случае b1= a2  a3  a4 сохранится равенство для всех трех строчек, а следовательно Si = 0. Это подтверждает необходимый и достаточный признак принятия правильной информации.

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

e1 S1

e2 S2

. .

en Sn

1 0 0 0 0 0 0 0 1 1 Корректирующая матрица H:

ошибка 0 1 0 0 0 0 0 1 0 1 iая строка корректирующей

в информационном 0 0 1 0 0 0 0 1 1 0 матрицы H содержит синдром,

разряде 0 0 0 1 0 0 0 1 1 1 = H который соответствует ошибке

в i-ом разряде кодовой

ошибка 0 0 0 0 1 0 0 1 0 0 комбинации.

в проверочном 0 0 0 0 0 1 0 0 1 0

разряде 0 0 0 0 0 0 1 0 0 1

a1a2a3a4 b1b2b3 S1S2S3

Для e1 из выражений для Si находим S1, S2, S3.

Подчеркнуть, что Si=0, если ошибочная комбинация не попадает в систему проверки для Si.

Мы видим, что проверочная матрица H состоит из двух частиц матрицы П и единичной матрицы.

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

Т.о. процесс декодирования кодовых комбинаций (для линейного группового кода) состоит в следующем:

Определение проверочного синдрома Si в соответствии с видом проверочной матрицы П.
Если Si = 0 – комбинация принята верно, если Si0, произошла ошибка.
Построение проверочной матрицы, которая устанавливает соответствие между значением Si и позиций, в которой произошла ошибка.
Исправление (коррекция [инверсия]) ошибочной позиции.

Мы рассмотрели групповые линейные коды и процедуры кодирования и декодирования, в основе которых лежит построение порождающей (S) и проверочных матриц (H).

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

1. Совершенные коды – коды с min количеством избыточных разрядов. [2r = k+r+1]

2. С точки зрения простой структурной реализации:

экономические коды коды с повышенной

с min количеством проверок на четность корректирующей способностью

Wп = min: 2l, 2l +1, 2l +2, … Wп = max: r, r-1, r-2 …

Min количество проверок на четность, Наиболее высокие корректирующие

min количество аппаратурных затрат способности.

Декодирование линейных кодов.

а) ẼH = S – из условия построения проверочного синдрома.

б) ẼH = (E  e)H = EH  eH = S;

При отсутствие ошибок: Ẽ=E; S=0; отсюда EH=0; eH=S; т.к. E=Gn,k, то Gn,kH=0, и имеем Gn,kH=0, - условие построение H по известной Gn,k.

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

Код Хэмминга.

6.3 Матричное представление кода Хэмминга.

а) а4 а3 а2 а1 b3 b2 b1 a4 a3 a2 b3 a1 b2 b1

1 0 0 0 1 1 1 1 0 0 1 0 1 1

0 1 0 0 1 1 0 G7,4x = 0 1 0 1 0 1 0

0 0 1 0 1 0 1 0 0 1 1 0 0 1

0 0 0 1 0 1 1 0 0 0 0 1 1 1

E = IG7,4 = (0101) G7,4x = 0 1 0 1 1 0 1

a a2 a3 b1 a4 b2 b3 S1 S2 S3

11 0 0 0 0 0 0 1 1 1

0 1 0 0 0 0 0 1 1 0

0 0 1 0 0 0 0 1 0 1

0 0 0 1 0 0 0 1 0 0

0 0 0 0 1 0 0 0 1 1

0 0 0 0 0 1 0 0 1 0

0 0 0 0 0 0 1 0 0 1

б) Этап декодирования.

111

100

101

S = ẼH = Ẽ 100

010

001

S = 0111.101H = 101.

Из определения Н, в которой каждая строка равна синдрому ошибки.

Структурная реализация линейных кодов и Хэмминга это кодирование и декодирование

6.4Модифицированный код Хэмминга.

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

Тогда: b4= bi   ai ; S=EH; S1=  bi   ai

S	S1
0	0	Нет ошибок
0	1	Одиночная ошибка
0	0	Двойная ошибка
?	1	Тройная ошибка

Табл. 6.1 Проверка на ошибки

Достоинство групповых линейных кодов - это эффективны при малой кратности ошибок (как правило, t=1).

Недостаток групповых линейных кодов: при ошибках большей кратности – резкое усложнение кодирующих и (особенно) декодирующих устройств.

Более совершенными являются циклические коды.

Циклические коды.
Из всех известных корректирующих кодов наиболее простыми и эффективными являются циклические коды. Эти коды могут быть использованы как для обнаружения, так и для исправления независимых ошибок, так и, в особенности, для обнаружения и исправления серийных ошибок.
Ц. к. принадлежат линейным кодам. При этом среди всего многообразия линейных разделительных кодов можно выделить коды, у которых кодовые комбинации помимо условия Wmin dmin связаны дополнительным условием цикличности. Т.е. одна разрешенная кодовая комбинация может получаться из другой путем циклического сдвига.

011001101 110011010 100110101 001101011 и т.д.

Коды, удовлетворяющие условию циклического сдвига, называются циклическими.

3. Применение циклического кода основано на записи любой кодовой комбинации в виде полинома

1 0 1 1 0 1 0 1 ,где конкретные значения

x7 x6 x5 x4 x3 x2 x 1 коэффициенты при xi.

x7  x6 +x5 +x4 +x3 +x2 +x +1 Т.е. конкретная кодовая

комбинация  двоичному многочлену.

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

а.) Сдвиг кодовой комбинации влево на i-разрядов эквивалентен умножению на xi, при этом, чтобы степень полинома не стала больше «n», т.е. кодовая комбинация не стала длинней.

Циклический код образуется путем умножения информационного k-значного кода, выраженного в виде полинома Q(x) степени k-1, на некоторый образующий полином G(x) степени (n-k = r).

Q(x)=1010(x3+x); G(x)=(x3+x+1); E(x)=(x6+x3+x2+x).

Отсюда, основное свойство циклического кода: многочлен E, выражающий разрешенную кодовую комбинацию циклического кода, будет делиться на образующий многочлен без остатка.
С другой стороны: ни один многочлен, соответствующий запрещенной кодовой комбинации, на образующий многочлен G(x) без остатка не делится. То есть остаток – это проверочный синдром.

Это основное свойство позволяет определить наличие ошибки в кодовой комбинации.

Отсюда следующее:

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

Если R(x)=0 – нет ошибки,

Если R(x)0 – есть ошибка, и ее надо определить по виду R(x).

Виды двоичных многочленов, их свойства.

а) неприводимый простой многочлен.

Многочлен P(x) степени n называется простым, если он не делится без остатка ни на какой многочлен степени меньшей, чем n (аналогия с простым числом).

n=4: x4+x+1; x4+x3+1

n=5: x5+1=(x+1)(x4+x3+x2+x+1)  составной (непростой)

n=10: x10+x3+1; x10+x7+1 и т.д.

б) примитивный многочлен.

Примитивным называется многочлен P(x) степени m, имеющий максимально возможное число остатков от деления xi/P(x)- 2m-1, где i = 0,1…..

Пример. P(x)=x4+x3+x2+x+1 – непримитивный

P(x)=x4+x+1 – примитивный

R(x) - остаток при xi/P1(x)

R(x) - остаток при xi/P2(x)

<0001

0010

0100 R=1

1000

1111

0001

0010

0100

1000

0011

0001

0010

0100

1000 R>1

0110

1100

1011

0101

1111

0001

0010

0100

1010

0111

1110

1111

1000

1111

0001

0010

1101

1001

0001

0010

0100

1000

1111

 0001

0100

1000

0011

0110

Двойственные полиномы

P*(x) – полином двойственный P(x)

P*(x)=xmP(1/x), где m – степень P(x).

Свойства двойственности:

а) Полином двойственный неприводимому полиному является также неприводимым;

б) Полином двойственный примитивному является также примитивным. P(x)= x4+x3+1.

Сложение, умножение и деление двоичных многочленов.

I. Сложение многочленов.

C(x) = A(x) + B(x), где A(x) = aixi;

i=0

B(x) = bixi;

i=0

C(x) = cixi; где ci = ai  bi;

i=0

II. Умножение многочленов.

2n i

C(x) = A(x)B(x) = cixi , где сi = ajbi-j ;

i=0 j=0

x4 + x + 1 1 0 0 1 1

x3 + x2 + x 1 1 1 0

x5 x2 x 0 0 0 0 0

x6 x3 x2 1 0 0 1 1

x7 x4 x3 1 0 0 1 1

1 0 0 1 1

x7 + x6 + x5 + x4 + x 1 1 1 1 0 0 10

x7x6x5x4x3x2x1 x7 + x6 + x5 + x4 + x

Приведение подобных членов осуществляется сложением по mod 2.

Аппаратное умножение двоичных многочленов

Выход

«1»

«0»

Вход

А(х)

C(x) = A(x)*B(x) = (anxn + an-1xn-1 + … + 1)(bnxn + bn-1xn-1 + … + 1) = bnanx2n + (anbn-1 +an-1bn)x2n-1 + +…..

1ый такт: на вход подается an, а на выходе получаем: anbn.

2ой такт: на вход подается an-1, а на выходе получаем: an-1bn + anbn-1 и т.д.

Пример:

Выход

01001111

Вход

11001

A(x) = x4 + x + 1 C(x) = A(x)*B(x) =

А(х) B(x) = x3 + x2 + x = x7+ x6+ x5+ x4+ x

Nтакта

Вход

a0 a1

Выход

11001

0 0

10 0

1100

110

0 1

111

101

0 0

1 0

1111

01111

0 1

001111

1001111

0 0

01001111

Аппаратное деление многочленов.

Nтакта

Вход

r0 r1

r2 r3

Выход

110 000 001

11 000 000

0 0

1 100 000

110 000

0 0

1 0

1 100

0 0

110

0 0

1 0

1 1

001

0 1

оста

ток

1001

11001

частное

x8+x+1 x4+x+1 1) Делимое и делитель - нормированы

x8+x5+x4 x4+x+1 2) Степень делимого  степени делителя

x5+x4+x+1

x5+x2+x

x4+x2+1

x4+x +1

x2+x

Способы кодирования циклических кодов.

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

. Набор остатков от деления строже

. единичной матрицы, сдвинутой влево на

. Rij  r разрядов, на P(x). При этом, вес каждого

1 остатка Ri  dmin-1, что гарантировано

1 условием выбора P(x).

единичная, но

транспонированная матрица

Пример  (*) r

Выбрать образующий многочлен для случая n= 15 , m= 4. Двучлен x15+1 = x2 -1 +1 можно записать в виде произведения всех неприводимых многочленов, степени которых являются делителями числа 4. Последнее делится на 1,2,4.

В таблице неприводимых многочленов находим,

1 многочлен первой степени x+1

1 многочлен второй степени x2+x+1

3 многочлена четвертой степени x4+x+1, x4+x3+1, x4+x3+x2+x+1

x15+1 = (x+1) *(x2+x+1) *(x4+x+1) *(x4+x3+1) *(x4+x3+x2+x+1)

Один из сомножителей (x4+x+1), (x4+x3+1) может быть взят за образующий многочлен.

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

bj = pij aj , i = 1,2,3, …r

i=1

Декодирование циклических кодов.

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

R(x) = 0 (разрешенные) и R(x)  0 (запрещенные)

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

В данном случае остаток R(x) (от деления E(x) на P(x)) играет роль проверочного синдрома).
Любая принятая по каналу связи кодовая комбинация, содержащая ошибку, может быть представлена в виде

Ế= E + ế

запрещенн. разреш. ошибка

При этом,

Ẽ/ P(x)= (E + ẽ)/ P(x) = E / P(x) + ẽ / P(x),

т.е.

R(x) Ẽ(x) = R(x)ẽ(x)

4. По виду R(x) необходимо определить ẽ. Построение проверочной матрицы  Н , устанавливающей соотношение между вектором ошибки e и величиной остатка (в данном случае синдрома ошибки, аналогичного групповым кодам):

ошибки в информационных разрядах

ẽi 

ошибки 1 0

в проверочных 1

разрядах 1

0 1

Таким образом, процесс коррекции состоит в сопоставлении строки проверочной матрицы Н конкретному R(x).

Анализ строк матрицы Н  показывает, что строки, относящиеся к области ошибок в проверочных и информационных разрядах, различаются качественно:

А) Hi информ. (R(x))  dmin –1 ( для  =1  2 ) – по условию построения матрицы  

Б) Hi провер. (R(x)) = 1

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

Определяют вес (R(x)); если равен 1, то ошибки в проверочных разрядах и R(x) сразу указывает нам место ошибки.
Если (R(x)) > 1, т.е. ошибки в информационных разрядах, осуществляющих циклический сдвиг влево

← ←

Ẽ = E + ẽ, до тех пор, пока (R(x)) = t.

Коррекция ошибки и циклический сдвиг на d разрядов вправо.
Для ускорения операции коррекции целесообразно влево осуществлять сдвиг на r разрядов сразу – максимально возможный сдвиг, чтобы не «проскочить» проверочные разряды.

Последовательность построения циклических кодов, исправляющих одиночные ошибки.

Последовательность построения циклических кодов, исправляющих одиночные ошибки ( =1)

Определение количества информационных разрядов:

k = log 2 N , где N – полное количество передаваемых сообщений.

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

2r > k + r

n = k + r

Примечание. Из всех возможных r , удовлетворяющих неравенству, естественно, выбирают минимальную rmin .

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

А) степень P(x) = r

Б) P(x)  сомножитель xn + 1

В) P(x) примитивный двоичный полином

Построение кодовой комбинации (кодирование заданной комбинации) одним из двух способов:

А) с помощью образующей матрицы

Б) деление заданной кодовой комбинации, сдвинутой влево на r разрядов на образующий полином P(x) и добавление полученного остатка R(x) к заданной кодовой комбинации.

Пример построения матрицы для кода (15,11) с выбором в качестве образующего полинома:

А) нетривиального: x4+x3+x2+x+1;

Б) тривиального: x4+x3+1;

Передача полученной кодовой комбинации в канале связи

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

i i

 

Е; Е; Е; Ẽ

разрешенная запрещенная (содерж. ошибку)

Методика декодирования циклических кодов, исправляющих одиночные ошибки (t =1)

П.1. Получение проверочного синдрома путем деления полученной кодовой комбинации Ẽ(x) на образующий полином G(x).

П.2. Сравнение веса остатка (R(x) с величиной кратности ошибки : если (R(x)  , то - переход к П.4.

П.3. Циклический сдвиг Ẽ(x) влево на 1 (r) разряд и получения нового синдрома ошибки. Переход к П.2.

П.4. Исправление ошибки путем сложения проверочного синдрома с кодовой комбинацией:

i i i

  

Ẽ: Е = Ẽ Ri(x)



Пояснение: Ẽ  кодовая комбинация, полученная путем i-кратного циклического сдвига влево вектора [кодовой комбинации] Ẽ.

П.5. Получение искомых информационных разрядов путем i – кратного циклического сдвига вправо [обратного циклического сдвига] исправленной комбинации



Ẽ.

Коды БЧХ. Пример кода, исправляющего двукратную ошибку
Введение. Для направления независимых ошибок более высокой кратности l2 используются циклические коды БЧХ (первые буквы фамилий Боуз, Чоудхури, Хоквинхем – авторов методики построения цикл. кодов с dmin 5). В н.в. это одни из наиболее распространенных и эффективных корректирующих кодов.

II. Методика построения БЧХ. Методика построения кодов БЧХ аналогична общей методике построения ц. к. и отличается в основном выбором образующего многочлена. Последовательность построения P(x) для кодов БЧХ тоже, что и для обычных ц.к., однако образующий полином является произведением t неприводимых полиномов, G(x) = M1(x)*M2(x)…Mt(x), где t – кратность ошибки. Методика выбора (построения) образующего полинома основана на понятии корня двоичного многочлена и теоремы БЧХ.

Понятие корня двоичного многочлена.

Элемент a является корнем двоичного полинома f(x), если f(a)=0.
Количество корней многочлена равно степени полинома.

Если f(x)=q0+q1x+q2x2+…+qnxn;

qn¹0; тогда a1, a2, a3...an при которых f(ai)=0, i=1,2,n.

Пример: Пусть требуется определить все корни бинома x15+1.

Количество корней a1, a2, a3...a15.
Представление x15+1 в виде произведения неприводимых сомножителей:

f1 f2 f3 f4 f5

x15+1 = (x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1).

Корни полинома получены Питерсеном и сведены в специальную таблицу.

Фрагмент таблицы:

Бином	Неприводимые многочлены	Корни
x15+1	f1(x): x+1	a1
		f2(x): x2+x+1	a6, a11
		f3(x): x4+x+1 f4(x): x4+x3+1 f5(x): x4+x3+x2+x+1	a2, a3, a5, a9 a8, a12, a14, a15 a4, a7, a10, a13

Каждый корень ai является корнем fj(x) и корнем порождающего бинома x15+1, имеет порядковый номер.

Для построения полинома кодов БЧХ используется теорема БЧХ: (без доказательств)

Если образующий полином содержит непрерывную цепь из m корней, то данный порождающий полином обладает корректирующими свойствами кода с dmin=m+1.

При этом ц.к., исправляющие одиночные ошибки являются частным случаем (m=2) из общей теоремы БЧХ.

Пример: 1). Если взять в качестве порождающего

f3(x) a2, a3, a5, a9 m=2

dmin ³3.

f4(x): a8, a12, a14, a15 m=2

2). F=f3(x)*f5(x) a2, a3, a4, a5, a7, a9, a10, a13 m=4 dmin ³5.

Методика этапов кодирования и декодирования кодов БЧХ отличается от кодов, исправляющих одиночные ошибки, только выбором образующего многочлена.

Методика выбора порождающего полинома для кодов БЧХ.

Определение количества информационных разрядов:

k = [log2N].

Определение количества проверочных разрядов:

n = k + r = k + t * h £ 2h – 1;

t – кратность ошибки.

Длины кодовой комбинации n = k + r и степени бинома xn + 1.

3. Разложение (представление) xn + 1 в виде произведения неприводимых сомножителей (по таблице Питерсона).

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

набор корней содержал непрерывную цепь корней длиной не менее чем m=dmin-1=2t;

Представление в виде произведения неприводимых сомножителей.

Этап декодирования аналогичен ц.к. При этом l>1.

Пример.

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

k = [log2N] = [log2100] = 7, dmin ³5.
n = k + r = 7 + 2*h £ 2n – 1; h = 4; r = l*h = 2*4 = 8 n = 15.

f1 f2 f3 f4 f5

x15+1 = (x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1).

a1 a6, a11 a2, a3, a5, a8, a12,  a4, a7, a10, a13

a9 a14, a15

4. f3*f5 = (x4+x+1)(x4+x3+x2+x+1)

В качестве F(x) a2, a3, a4, a5, a7, a9, a10, a13

f4*f5 = (x4+x3+1)(x4+x3+x2+x+1)

a4, a7, a8, a10, a12, a13, a14, a15

m=4

При выборе в качестве пор. F1(x) или F2(x) – корректирующие возможности полученного ц.к. будут равны.

Степень образующего многочлена F(x) = 8;

F(x) = F1(x) = (x4+x+1)(x4+x3+x2+x+1) = x8 + x7 + x6 + x4 + 1.

7 разр. 8 разр.

C15,7 = 0000001 11010001 W(Ei) ³ dmin = 5;

0000010 01110011 W(R(x2) ³ 4.

0000100 11100110

0001000 00011101

0010000 00111010

0100000 01110100

1000000 11101000

10000,00000,00000 111010001

11101,0001

R1(x) 1101,00010

1110,10001

R2(x) 011,10011,0

R3(x) 11,10011,00

11,10100,01

R4(x) 0,00111,01

R5(x) 0,01110,10

R6(x) 0,11101,00

R7(x) 1,11010,00 ®

Необходимо закодировать и передать: Н=1000011

* * ~ * *

1100001 01001101 E(x) = 1101011|01001101,

k r

1). R1(x) = 01101110  W(R1(x)) > 2.

2). Циклический сдвиг на 4 позиции

* *

E2(x) = 0110100|11011101

R2(x) = 01110101  W(R2(x)) > 2;

3). Ц.к. влево на 2 позиции

~ * *

E3(x) = 1010011|01110101;

R3(x) = 00000101  W(R3(x)) = 2;

E3(x) = E3(x) + R3(x).

4). Циклический сдвиг вправо на 4 + 2 = 6 позиций.

После этого получаем направленную кодовую комбинацию.

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

Наряду с независимыми ошибками в каналах часто действуют т.н пакеты ошибок. Рассмотрим устройство кода обнаруживающих пакеты ошибок ( серии ошибок) длиной l.

Примеры векторов пакетов ошибок:

l(x)[l=4] = 001011000; 00011110000

1011-ошибки 1111-ошибки

Пакетом ошибок длиной l называется любая комбинация ошибок число разрядов в которых между первой и последней ошибкой включая эти ошибки.

Теорема 8.3.1: Любой код образованный с помощью простого полинома G(x) степени r = n-k, обнаруживает пакеты ошибок длиной l = n-k или меньше.

Доказательство: Полином пакета ошибок можно представить в виде e(x)= x*e1(x) ,где e1(x) не делится без остатка на образующий полином G(x). Т.к G(x) не содержит множителя x , то e(x) делится на G(x) только тогда ,когда e1(x) делится без остатка на G(x). Но если l, то степень G(x)= r выше, чем степень e1(x) =l-1 ,а поэтому e1(x) не делится на G(x) без остатка, ч.т.д.

Теорема 8.3.2 Циклический код построенный с помощью любого неприводимого полинома, степень которого больше или равна 1 ,обнаруживает все одиночные ошибки

Доказательство:

а) Одиночные ошибки в I- разряде соответствуют: e1(x) =x

б) ;

Чтобы обнаружить ошибку остаток от деления на G(x) должен быть не равен 0 т.е. остаток от деления. Очевидно что не существует G(x) степени 1 такой что R(x)=0 ч.т.д.

Простейший G(x)=X+1, а использование в качестве образующего G(x)=X+1 позволяет обнаруживать все одиночные ошибки.

Лемма 1 Всякий полином, делящийся на 1+X, имеет четное число членов.

Доказательство: F(x) = (x+1)Q(x) содержит четное количество членов. Подставляя вместо Х единицу ,получим F(1)=1+1+…+…=(1+1)+Q(1)=0 т.е. F(1)=0 то это возможно если F(x) имеет четное число членов в которых сумма по модулю 2 дала 0.

Лемма 2 Всякий полином, имеющий сомножитель который содержит четное число членов, также имеет четное число членов.

Теорема 8.3.4: Циклический код построенный с помощью G(x)=x+1 обнаруживает все нечетные ошибки.

Доказательство: (от противного) Предположим что существует комбинация ошибок, содержащая нечетное количество ошибок, такая, что не обнаруживается кодом. Т.е. существует e1(x) =(х+1)Q(x) но из леммы 1 следует что в этом случае e1(x) содержит четное число членов т.е. не существует e1(x) содержащего нечетное количество ошибок дающее остаток 0 при делении на х+1 Ч.т.д.

Используя в качестве образующего G(x) = x+1 позволяет обнаруживать нечетное количество ошибок и эквивалентно кодам проверки на четность.

Теорема 8.3.4 Циклический код, построенный с помощью полинома ,содержащий четное количество членов, обнаруживает все нечетные ошибки. Доказательство: аналогично предыдущему .

Теорема 8.3.5: Для циклического кода образованного с помощью полинома G(x) степени r = n – k, относительное количество не обнаруживаемых пакетов ошибок длиной l> r =n –k равно:

,если l>r +1

,если l= r+1

Доказательство:

1) Вектор ошибки представляется в виде е(x)= e1(x) где e1(x) полином степени l-1.Поскольку e1(x) имеют члены , существуют между ними l-2 членов (0<j<l-1). Коэффициенты при которых 0 и 1 т.е.,

e1(x) = Т.о. имеется различных полиномов e1(x)

Ошибка не будет обнаружена только в том случае если G(x) является множителем e1(x)

e1(x) =G(x)*Q(x)

Т.к. степень G(x) равна r то степень Q(x) равна (l-1 –r)

а) случай когда l = r+1

- степень Q(x) => 0 то Q(x)=1

- имеется только один полином Q(x)=1 не обнаруживающий ошибки e1(x) =G(x)

- =

б) случай когда l>r+1

- полином Q(x) содержит и и имеет между ними (l-2-r) произвольных коэффициента

- имеется различных Q(x) которые соответствуют необнаруживаемым ошибкам

- =

Рассмотрим возможности определения ошибок как независимых так и пакетов ошибок

Теорема.8.3.6:Циклический код образованный с помощью простого полинома G(x) степени r = n –k , обнаруживает все комбинации ошибок за исключением относительного количества

Доказательство:

а) Для любого разрешенного кода длины n существует возможных векторов ошибок E(x) возможных комбинаций.

б) При ‘К’ информационных разрядов существует векторов ошибок которые воспринимаются как разрешенные кодовые комбинации т.е. векторов E(x) делится без остатка на G(x).

в) Остальные векторы представляют запрещенные кодовые комбинации (остаток от деления 0). Поэтому отношение числа не обнаруживаемых ошибок к общему числу ошибок определяется как

N=1000. В канале могут действовать любые сочетания ошибок.

Пример. 8.5

Построить код, который будет обнаруживать 99%всех ошибок.

1)количество не обнаруживающихся ошибок:

д.б.<1/100 поэтому <1/100 отсюда r = 7 >100

2) k =]log21000[=10;

3) n = 10+7=17 G(x)=

При этом из всевозможных сочетаний ошибок 99% будут обнаружены, и 1% будет принят ошибочно за разрешенные кодовые комбинации.

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

Циклический код данного вида позволяет:

А0) обнаруживать все одиночные ошибки

А1) все двойные ошибки если P(x)-примитивный и >n

A2) все нечетные ошибки если G(x) имеет четное число членов;

A3)все пакеты ошибок длиной :lr;

А4) всевозможные сочетания ошибок кроме

Рекуррентные коды.

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

Операции кодирования и декодирования осуществляются над непрерывной последовательностью символов. Кодирование каждого ai осуществляется индивидуально.

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

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

Цепные коды – простейшие рекуррентные коды, обладающие коэффициентом избыточности : r/n=0.5. Т. е. коды, имеющие одинаковое число информационных и проверочных символов

Корректирующие способности кода определяются параметром, который называется шагом сложения: t. Шаг сложения – расстояние между двумя информационными элементами, суммируемыми по mod 2 для получения проверочных элементов bj.

Рассмотрим процедуры кодирования и декодирования и через основной параметр t определим структуру и основные параметры цепного кода.

Структурная схема кодирующего устройства

Каждый информационный элемент ai участвует в формировании 2х проверочных элементов bi:

bi-t = ai ai+t

bi-2t = ai-t  ai

Вместе с тем, каждый проверочный элемент формируется двумя информационными ai+2t , ai+t. Т.о. количество информационных {ai} и проверочных {bi}элементов в кодовой последовательности, поступающей в к. с. – всегда одинаково.

Проверка на наличие ошибки (и корректировке в случае наличия) осуществляется для каждого ai – индивидуально на приемной стороне в декодирующем устройстве.

Структурная схема декодирующего устройства

Примечание: ai, bi – до поступления в к.с., ai’, bi’ – после к.с., т.е. с возможными ошибками

Основной принцип проверки – очень прост: формирование bi-“нов” и сравнение с выделенными символами: bi’.

Наличие не сравнения является признаком ошибки.

Для цепных кодов ( k=r=1 ) проверка на наличие ошибок осуществляется для каждого ai индивидуально.

Данная проверка проводится в соответствии с формулами:

Проверка элемента ai

L1: сравнение bi-t, нов с bi-t’ => L1= bi-t’  (ai’ + ai+t’) (*)

L2: сравнение bi-2t, нов c bi-2t’ => L2 = bi-2t’  (ai-t’ + ai’) (**)

4. Анализируя полученное выражение, определим алгоритм коррекции и структуру цепного кода.

а.) В корректировке ai участвуют ai+t’, ai-t’, bi-t’, bi-2t’, которые в кодовой пследовательности расположены следующем образом : …..ai+t bi+t ….. ai bi …..ai2tbi2t …..ai-2tbi-2t …..

При этом возможны следующие варианты:

а.) ai’ – ошибочен. Тогда это однозначно может быть обнаружено в том случае, если все остальные элементы, входящие в формулу (**) – принять без ошибок.

Тогда: 1.) Признаком того, что ai’ – ошибочен, является: L1=1, L2=1 => F=L1L2=1

2.) Пакет ошибок не должен «накрывать» вместе с ai – ai+t, ai-t, bi-t, bi-2t, а это налагает ограничения на возможную длину пакета ошибок: l  2t.

б.) F=0. Т.е. L1=0 или L2=0 или L1=L2=0. При этом ai принят правильно, и он проходит без всякой коррекции.

в.) Возможен случай, когда в кодовой последовательности (в выделенном нами выше фрагменте) ошибочными оказались крайние : ai+t и bi-2t (а остальные правильные) – случай начала одной пачки и конца другой. Исходя из формулы (**), имеем F=1 и корректируем ai (по алгоритму п. ai-ого), что является ошибочным. Чтобы не происходило ложного исправления символов – требование к интервалу между пачками ошибок:

Расстояние между последним символом предыдущей пачки ошибок и первым символом следующей пачки ошибок L должно удовлетворять соотношению :

L  3*2t+1 ( 3*2t – длина воспроизводимого фрагмента,

внутри которого осуществляется коррекция ai)

Цепной код. Структурная схема реализации цепного кода.

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

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

Структурная схема кодирующего устройства

Каждый информационный элемент ai участвует в формировании 2х проверочных элементов bi:

bi-t = ai ai+t

bi-2t = ai-t  ai

Проверка на наличие ошибки (и корректировке в случае наличия) осуществляется для каждого ai – индивидуально на приемной стороне в декодирующем устройстве.

Структурная схема декодирующего устройства

Примечание: ai, bi – до поступления в к.с., ai’, bi’ – после к.с., т.е. с возможными ошибками

Основной принцип проверки – очень прост: формирование bi-“нов” и сравнение с выделенными символами: bi’.

Наличие не сравнения является признаком ошибки.

Для цепных кодов ( k=r=1 ) проверка на наличие ошибок осуществляется для каждого ai индивидуально.

Данная проверка проводится в соответствии с формулами:

Проверка элемента ai

L1: сравнение bi-t, нов с bi-t’ => L1= bi-t’  (ai’ + ai+t’) (*)

L2: сравнение bi-2t, нов c bi-2t’ => L2 = bi-2t’  (ai-t’ + ai’) (**)

4. Анализируя полученное выражение, определим алгоритм коррекции и структуру цепного кода.

При этом возможны следующие варианты:

Тогда: 1.) Признаком того, что ai’ – ошибочен, является: L1=1, L2=1 => F=L1L2=1

б.) F=0. Т.е. L1=0 или L2=0 или L1=L2=0. При этом ai принят правильно, и он проходит без всякой коррекции.

L  3*2t+1 ( 3*2t – длина воспроизводимого фрагмента,

внутри которого осуществляется коррекция ai)

А также другие работы, которые могут Вас заинтересовать
17591.	Лекция	Ряды распределения. Показатели вариации	310.5 KB
	ТЕМА 3 Ряды распределения. Показатели вариации ПЛАН ЛЕКЦИИ 1. Понятие рядов распределения. 2. Характеристики центра распределения. Средние величины. 3. Характеристики вариации. 4. Характеристики формы распределения. 1. Понятие рядов распределения 1. В результате ...
17592.	Лекция	Выборочное наблюдение. Особенности малой выборки	201 KB
	11 ТЕМА 4 Выборочное наблюдение ПЛАН ЛЕКЦИИ 1. Статистическое наблюдение 2. Выборочное наблюдение причины и условия его применения. 3. Виды и схемы выборки. 4. Ошибки выборки. 5. Определение необходимой численности выборки. 6. Особенности малой вы
17593.	Лекция	Статистические методы измерения взаимосвязей	259 KB
	14 ТЕМА 5 Статистические методы измерения взаимосвязей. ПЛАН ЛЕКЦИИ 1. Виды взаимосвязей между явлениями. 2. Метод аналитического группирования. Дисперсионный анализ. 3. Корреляционно регрессионный анализ. 4. Многофакторная корреляция. 5. Непарам...
17594.	Лекция	Ряды динамики. Определение тенденции развития. Интерполяция и экстраполяция	350 KB
	11 Лекция 6. Ряды динамики ПЛАН ЛЕКЦИИ 1. Понятие и виды рядов динамики. 2. Характеристики рядов динамики. 2.1. Показатели интенсивности изменения уровней ряда динамики 2.2. Средние показатели ряда динамики 3. Определение тенденции развития. Интерпол
17595.	Лекция	Индексы. Использование индексного метода при анализе среднего курса акций	258.5 KB
	ТЕМА 7 Индексы ПЛАН ЛЕКЦИИ 1. Понятие индексов. Индивидуальные и сводныеобщие индексы. 2. Агрегатные индексы. 3. Среднеарифметический и среднегармонический индексы. 4. Система взаимосвязанных индексов факторный анализ. 5. Индексы средних величин. 6. Использовани...

Виды структурной меры

Геометрическая мера

Комбинаторная мера

Особенности

H(X) = - Pi *log2Pi =163/64 бит/символ. Для C = 3000 дв.ед./с  V(Z) = 3000 бит/с;

Б) Вследствие воздействия помех после получения yj мы полностью не сняли неопределенность, а лишь уменьшили её до значения H(xi/yj) = - log2P(xi/yi).

Рассмотрим теперь метод построения образующей матрицы

С другой стороны Wi = Wнi + Wпi  dmin Wп  dmin – Wн

Пример

Вход

Выход

Вход

Бином

Неприводимые многочлены

Корни

А также другие работы, которые могут Вас заинтересовать