149
Основные понятия теории информации
Лекция
Информатика, кибернетика и программирование
Понятие информации. Виды и структура информации. Геометрическая, комбинаторная и аддитивная мера Хартли. Статистическая мера информации. Связь энтропии с количеством информации. Количество информации дискретных сообщений. Определение бита и байта.
Русский
2012-11-14
517 KB
254 чел.
Понятие информации
Понятие информации (с латинского сообщение или осведомление о чем-либо) связано с моделями реальных вещей, отражающих их сущность в той степени, в кокой это необходимо для практических целей: в виде чисел, формул, символов, чертежей и других абстрактных характеристиках, однако проявляется всегда в виде сигналов.
Циклы обращения информации:
Основные определения
Субьект - часть управляющей системы, оказывающая активное воздействие на ее работу.
Обьект - пассивная часть как информационной так и управляющей системы.
Сообщения конкретные сведения, получаемые об обьекте.
Случайные сообщения например сообщения о дополнительном экзамене.
Детерминированные сообщения например сообщения о траектории полета запущенной ракеты.
Сообщения передаются в систему связи в непрерывном (аналоговом) или дискретном (цифровом) виде.
Канал связи комплекс технических средств, обеспечивающих передачу и прием дискретных или непрерывных сигналов материальных переносчиков сообщений в пространстве и времени.
Кодирование информации преобразование формы представления информации с целью адаптации ее передачи по каналам связи.
Декодирование процесс обратный декодированию, заключающийся в замене принятой кодовой комбинации символами из входного алфавита.
Структурная мера учитывает только дискретное строение информационного комплекса, как носителя неделимых элементов информации (квантов в дискретных системах, букв алфавита в числовых системах). Различают геометрическую, комбинаторную и аддитивную меры информации. Применяется для оценки возможностей аппаратуры (пропускная способность каналов связи, объем запоминающих устройств и т.д.).
Статистическая мера использует энтропию или меру неопределенности, учитывающую вероятность появления, а значит и информативность сообщений. Применяется для количественных оценок хранения и передачи конкретной информации в зависимости с ее статистических характеристик.
Семантическая мера учитывает содержательность, целесообразность, ценность, существенность или полезность информации. Применяется при оценке эффективности логического опыта путем введения:
Определение количества информации геометрическим методом сводится к измерению длины линии, площади или обьема геометрической модели данного информационного комплекса в количестве дискретных величин определенных квантов или букв словаря, например метрах, фунтах, пинтах. Если дискретные отчеты осуществляются по осям соответственно через интервалы x; y; z, то непрерывные координаты распадаются на кванты, количество которых составляет: mx = X/x; my = Y/y; mz = Z/z; Тогда количество информации в полном комплексе XYZ, опр. геометрическим методом равно в квантах: M = mx my mz
Количество информации в комбинаторной мере вычисляется как количество комбинаций элементов.
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 - мера снятие неопределенности при получении сообщения о событии.
Количественно мера информация совпадает с мерой измерения энтропии.
Мера измерения количества информации для дискретных случайных сообщений впервые была предложена Шенноном в 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 бит.
В нашей области науки и техники используется двоичная система счисления, поэтому основание логарифма для вычисления количество информации будет равно двум.
Свойства количества информации дискретных сообщений:
1. Количество информации - вещественная, неотрицательная и ограниченная величина 0=< I(Х)<=M
2. Количество информации детерминированных сообщений равно нулю. I(xi) = 0 для p(xi) = 1
3. Количество информации максимально, если сообщения равновероятны.
Imax (X) = - - log2 р(х ) = log2 1/pi = log2N
I=1
Доказательство 1.
Доказательство 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) к пропускной способности канала утверждает теорема Шеннона для дискретного канала без помех.
Для каждого источника сообщений соотношение 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, называются эффективными (оптимальными) и, впервые, были предложены Шенноном, Фано, Хаффменом.
Под кодированием в широком смысле слова подразумевается представление сообщений в форме, удобной для передачи по данному каналу. Обратная операция называется декодированием.
Кодирование, учитывающее статистические особенности источника сообщений называется статистическим (эффективным) кодированием.
В настоящее время разработано большое количество различных способов оптимального статистического кодирования. Все они должны обеспечивать решение двух основных задач:
Для двоичного канала с отсутствием статистических связей между символами этим требованиям удовлетворяет код Шеннона-Фано.
Известно, что V C выполняется при равной вероятности появления различных сообщений.
В соответствии с этим, построение кода выполняется по следующей последовательности:
А) все буквы алфавита выписывают столбцом в порядке убывания вероятности;
Б) столбец последовательно делят на группы с приблизительно равной суммарной вероятностью.
При этом:
Приближение V к C было осуществлено за счет:
Причиной C > V(X) и Kотн. эфф. 1 при использовании эффективного способа кодирования является невозможность разбиения сообщений { Xi } на подгруппы с достаточно близкой вероятностью.
Дальнейшим возможным способом повышения скорости передачи информации является кодирование не каждого символа сообщения, а группы из двух символов, что позволяет получить новый набор из групп и возможность деления на более близкие по суммарной вероятности подгруппы.
Кодирование, учитывающее статистические особенности источника сообщений называется статистическим (эффективным) кодированием. В настоящее время разработано большое количество различных способов оптимального статистического кодирования. Все они должны обеспечивать решение двух основных задач:
Для двоичного канала этим требованиям удовлетворяет код Шеннона-Фано.
Известно, что V C выполняется при равной вероятности появления различных сообщений.
В соответствии с этим, построение кода выполняется по следующей последовательности:
А) все буквы алфавита выписывают столбцом в порядке убывания вероятности;
Б) столбец последовательно делят на группы с приблизительно равной суммарной вероятностью.
При этом:
В качестве примера рассмотрим алфавит сообщений из 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 сообщ./с
8
ср. = Pi *i = 163/64 дв.разр. ср.= H(X)
i=1
8
i=1
б) равномерного кодирования;
Каждому сообщению требуется 3 двоичных разряда равн.= log2N, а каждое сообщение Zi содержит:
8
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) заданы так, что подгруппы точно делились пополам.
Кодирование, учитывающее статистические особенности источника сообщений называется статистическим (эффективным) кодированием. В настоящее время разработано большое количество различных способов оптимального статистического кодирования. Все они должны обеспечивать решение двух основных задач:
Для двоичного канала этим требованиям удовлетворяет код Шеннона-Фано.
Дальнейшим возможным способом повышения скорости передачи информации является кодирование не каждого символа сообщения, а группы из двух символов, что позволяет получить новый набор из 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
Б) Для канала с помехами:
После получения на приемной стороне yj , источник информации может быть охарактеризован апостериорным распределением P(xi/yj). Где P(xi/yj) - вероятность, называемая условной вероятностью передачи в канал символа xi при условии, что из канала был получен символ yj.
P11 P12 … P1n основная характеристика к.с.
P21 P22 … P2n с помехами
… P (xi/yj) …
Pn1 Pn2 … Pnn
А) Pij определяется путем статистической обработки результатов экспериментальных исследований.
Б) Свойства Pij: по диагонали вероятность безошибочной передачи, остальные ошибочной передачи.
Виды каналов с помехами.
Если P10 = P01= q вероятность ошибочной передачи, и P00 = P11= p вероятность правильной передачи, то такой канал называют бинарным симметричным:
Количество информации, предаваемой по каналу с помехами.
Для матрицы общего вида Pijоценим кол-во инф., содержится в принятом сообщении yj относительно xi:
А) неопределенность относительно xi до получения yj характеризуется его энтропией: H(xi) = - log2P(xi). Для канала без помех, получив yj из канала связи, мы полностью сняли о нем неопределенность, т.е. получили количество информации: Ii = H(xi) = - log2P(xi).
В) Разница неопределённостей до и после получения сообщения yj составила количество информации, содержащееся в сообщении yj относительно xi: I(xi/yi) = H(xi) - H(xi/yj) = log2(P(xi/yi)/P(xi)).
n n
I(X/yi) = P(xi/yj) * I(xi/yj) = P(xi/yj) * log2(P(xi/yi)/P(xi));
i=1 i=1
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)
Безусловная энтропия Условная энтропия
Среднее количество информации, получаемое из канала связи при наличии помех равно разности безусловной энтропии, характеризующей начальную неопределенность сообщений (до принятия сообщения) и условной энтропии, характеризующей остаточную неопределенность (после получения сообщения).
А) отсутствие помех
Б) при уровне помех, обеспечивающих 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*IC, то можно подобрать такой код, который позволяет передавать всю информацию с погрешностью 0.
Очевидно, что при наличии помех достоверность передачи информации можно повысить, например, путем многократного повторения каждой буквы, что ведет к снижению скорости передачи (если , то и V).
Интуитивно кажется, что для обеспечения нулевой ошибки число повторений должно быть бесконечным, а скорость передачи информации V 0. Однако, теорема утверждает, что при можно подобрать такой код, при котором V 0 - конечная величина. Таким образом, данная теорема устанавливает соотношения при передаче по каналу с помехами между скоростью сообщений создаваемых источником V, пропускной способностью канала C и достоверностью передачи.
Следует отметить, что данная теорема не отвечает на вопрос: каким образом нужно осуществлять кодирование, чтобы приблизить скорость передачи информации к пропускной способности канала связи?
Помехи Pij
C = F (структура реального канала; Pij )
P(xi)
V(X) C - , то существует способ кодирования
xi yj
V(X)
Особенности эффективного кодирования:
Для двоичного канала.
Статистическое кодирование:
а) разбиение на подгруппы с приблизительно равной вероятностью обеспечивает стремление к равновероятному закону (чем больше сообщений [сложные сообщения], тем более точно можно поделить пополам и приблизиться к равновероятности);
б) кодирование верхней группы одним двойным символом, а нижний противоположным, обеспечивает статистическую независимость появления «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ые ошибки Хеммингом активно, используется и в н.в., но откровенно своей слабостью, по сравнению с обещанным Шенноном более сильными кодами.
б) Основной сдвиг при построении кодов произошел в 5060 годы при использовании серьезной теории теории полей Галуа) и построении на их основе циклических кодов (Однако использование кодов БЧХ и РС стало возможным только с учетом применения средств цифровой техники. Однако коды БЧХ и Рида-Соломона еще далеки от кодов предсказанных Шенноном (при большой длине блока происходит резкое увеличение избыточности). Т.е. коды БЧХ и РС имеют характеристики близкие к предсказанным только при относительно небольшой длине блока.
в) Только в 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 проверочные разряды;
Значение проверочных разрядов определяется:
г)
д) Процедура декодирования состоит в определении: к какому подмножеству принадлежит принятая из канала кодовая комбинация:
а) если к разрешенному, то считается что полученная комбинация не содержит ошибок;
б) если к запрещенному содержит ошибки.
Передающая сторона Канал связи Принимающая сторона
(этап кодирования) 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 разрядах.
101000101 кодовая комбинация обозначается: E1 = 101000101
n =9
2) Количество “1” в кодовой комбинации называется весом кодовой комбинации ().
(E1) = 4
Расстояние по Хэммингу между двумя двоичными последовательностями (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 всевозможные кодовые слова, где ij
E1= 0101010
d(E1, E2) = 5 dmin = 5 d(E1, E3) = 5
E2= 0000101 E3= 1110001
d(E2, E3) = 5
Характеристики ошибок (помех)
При прохождении кодовой комбинации по каналу связи под влиянием помех возможно изменение кодовой последовательности.
Ошибки проявляются в том, что в одном или нескольких разрядах кодовой комбинации: 01 10.
а) Если переход происходит в одном разряде одиночная ошибка;
б) Если в нескольких разрядах многократная ошибка (двойная, тройная и т.д.).
e вектор ошибки;
E = 0100110 б/ошибочная кодовая комбинация.
в) Многократные ошибки
независимые ошибки пакеты ошибки
(позиция одной ошибки не зависит от другой) связанные между собой (как правило)
единой причиной.
Пакеты ошибок характеризуются длиной пакета (l).
Пакетом ошибок длины l называется комбинация ошибок, расположенных среди l последовательных компонент, первая и последняя из которых отличны от 0.
l = 001011010000
l = 6
Рассмотрим последовательность выбора параметров кода (n, r) для заданной корректирующей способности (t кратные исправленные ошибки).
Задача: а) объем источника сообщений N число различных сообщений;
б) число векторов ошибок, которые необходимо исправить Ne,
Определить: k, r, n.
1) Количество информационных символов: k = [log2N];
2) Полное число ошибочных комбинаций, которые необходимо исправить: Ne2k.
По определению число запрещенных комбинаций: N2 = N0 N1 = 2n 2k Ne2k
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 = n2k;
б) Все коды необходимо («машинно») проверить и
выбрать с требуемыми характеристиками.
Пример: для весьма умеренного (по современным
понятиям) (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
А В
Гипотезы:
Для наглядности и оценки корректирующих способностей кодов рассмотрим геометрическую модель двоичного кода.
Комбинации 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
a1 |
a2 |
a3 |
ai |
… |
ak |
b1 |
b2 |
bi |
br |
n
Линейными называются коды, в которых проверочные символы представляют собой линейные комбинации информационных символов.
Для двоичных кодов в качестве линейной операции используются сложение по 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
n
Получение кодовой комбинации осуществляется путём суммирования элементов ||И|| и параллельного суммирования строк ||П||.
1). На практике установлено, что в качестве информационной матрицы ||И|| удобно брать единичную матрицу в канонической форме:
100…0
Iи = 010…0
………
000…1
2). Строчки образуют матрицы ||C|| = ||И|| ||П|| представляют собой “К” комбинаций(разрешённых) искомого кода. Остальные комбинации кода строятся при помощи образующей матрицы.
Из свойств группового кода следует, что W dmin
Т.к. вес всех сторон ||Н|| : 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;
а.) В процессе депозирования осуществляются проверки, идея которых в общем случае может быть представлена следующем образом :
k
Sj = bj Å pijai Sj = bj Å bj; j1r;
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 состоит из двух частиц матрицы П и единичной матрицы.
Данная методика построения проверочной матрицы является одинаковой для всех образующих матриц.
Т.о. процесс декодирования кодовых комбинаций (для линейного группового кода) состоит в следующем:
Мы рассмотрели групповые линейные коды и процедуры кодирования и декодирования, в основе которых лежит построение порождающей (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 = EH eH = S;
При отсутствие ошибок: Ẽ=E; S=0; отсюда EH=0; eH=S; т.к. E=Gn,k, то Gn,kH=0, и имеем Gn,kH=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 = IG7,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
010
001
S = 0111.101H = 101.
Из определения Н, в которой каждая строка равна синдрому ошибки.
Структурная реализация линейных кодов и Хэмминга это кодирование и декодирование
6.4Модифицированный код Хэмминга.
Для исправления одиночной и обнаружения двойной ошибки, кроме проверок по контрольным позициям, следует проводить еще одну проверку на четность.
Тогда: b4= bi ai ; S=EH; S1= bi ai
S |
S1 |
|
0 |
0 |
Нет ошибок |
0 |
1 |
Одиночная ошибка |
0 |
0 |
Двойная ошибка |
? |
1 |
Тройная ошибка |
Табл. 6.1 Проверка на ошибки
Достоинство групповых линейных кодов - это эффективны при малой кратности ошибок (как правило, t=1).
Недостаток групповых линейных кодов: при ошибках большей кратности резкое усложнение кодирующих и (особенно) декодирующих устройств.
Более совершенными являются циклические коды.
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).
Это основное свойство позволяет определить наличие ошибки в кодовой комбинации.
Отсюда следующее:
Если 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 примитивный
i |
R(x) - остаток при xi/P1(x) |
R(x) - остаток при xi/P2(x) |
<0 1 2 3 4 |
<0001 0010 0100 R=1 1000 1111 |
0001 0010 0100 1000 0011 |
5 6 7 8 |
0001 0010 0100 1000 R>1 |
0110 1100 1011 0101 |
9 10 11 12 |
1111 0001 0010 0100 |
1010 0111 1110 1111 |
13 14 15 16 |
1000 1111 0001 0010 |
1101 1001 0001 0010 |
17 18 19 20 |
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. Сложение многочленов.
n
C(x) = A(x) + B(x), где A(x) = aixi;
i=0
n
B(x) = bixi;
i=0
n
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 |
Выход |
0 |
11001 |
0 0 |
10 0 |
1 2 |
1100 110 |
0 1 |
11 111 |
3 4 |
101 1 |
0 0 1 0 |
1111 01111 |
5 6 |
0 0 |
0 1 |
001111 1001111 |
7 8 |
0 |
0 0 |
01001111 |
Аппаратное деление многочленов.
Nтакта |
Вход |
r0 r1 |
r2 r3 |
Выход |
0 1 |
110 000 001 11 000 000 |
|
0 0 |
0 0 |
2 3 |
1 100 000 110 000 |
0 0 |
1 0 |
0 0 |
4 5 |
1 100 |
|
0 0 |
0 1 |
6 7 |
110 11 |
0 0 |
1 0 1 1 |
01 001 |
8 9 |
1 0 |
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
1
. Набор остатков от деления строже
. единичной матрицы, сдвинутой влево на
. Rij r разрядов, на P(x). При этом, вес каждого
1 остатка Ri dmin-1, что гарантировано
1 условием выбора P(x).
1
1
единичная, но
транспонированная матрица
Пример (*) 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) может быть взят за образующий многочлен.
k
bj = pij aj , i = 1,2,3, …r
i=1
R(x) = 0 (разрешенные) и R(x) 0 (запрещенные)
Это основное свойство используется для обнаружения и коррекции ошибок в принятых кодовых комбинациях.
Ế= E + ế
запрещенн. разреш. ошибка
При этом,
0
Ẽ/ 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
С учетом данных соотношений процедура кодирования существенно упрощается и представляется в виде:
← ←
Ẽ = E + ẽ, до тех пор, пока (R(x)) = t.
Последовательность построения циклических кодов, исправляющих одиночные ошибки ( =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
Пояснение: Ẽ кодовая комбинация, полученная путем i-кратного циклического сдвига влево вектора [кодовой комбинации] Ẽ.
П.5. Получение искомых информационных разрядов путем i кратного циклического сдвига вправо [обратного циклического сдвига] исправленной комбинации
i
Ẽ.
II. Методика построения БЧХ. Методика построения кодов БЧХ аналогична общей методике построения ц. к. и отличается в основном выбором образующего многочлена. Последовательность построения P(x) для кодов БЧХ тоже, что и для обычных ц.к., однако образующий полином является произведением t неприводимых полиномов, G(x) = M1(x)*M2(x)…Mt(x), где t кратность ошибки. Методика выбора (построения) образующего полинома основана на понятии корня двоичного многочлена и теоремы БЧХ.
Понятие корня двоичного многочлена.
Если f(x)=q0+q1x+q2x2+…+qnxn;
qn¹0; тогда a1, a2, a3...an при которых f(ai)=0, i=1,2,n.
Пример: Пусть требуется определить все корни бинома 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.
Пример.
Построить ц.к. для передачи различных символов, исправляющий одну или две ошибки:
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) = 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)
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. При действии в канале связи пачек ошибок данный метод имеет существенные преимущества перед блочными кодами, т. к. предоставляет большие возможности для наиболее полного использования введенной избыточности. Пояснение: Для блочных кодов возможности обнаружения и исправления определяются избыточностью, которая введена в данную кодовую комбинацию. Поскольку ошибки встречаются относительно редко, то избыточность большинства кодовых комбинаций не используется. В то же время при появлении пачки ошибок введенной избыточности не хватает. При применении рекур. кодов достигается усреднение влияния помехи на большую последовательность передаваемых информационных символов.
Цепные коды простейшие рекуррентные коды, обладающие коэффициентом избыточности : r/n=0.5. Т. е. коды, имеющие одинаковое число информационных и проверочных символов
Корректирующие способности кода определяются параметром, который называется шагом сложения: t. Шаг сложения расстояние между двумя информационными элементами, суммируемыми по mod 2 для получения проверочных элементов bj.
Рассмотрим процедуры кодирования и декодирования и через основной параметр t определим структуру и основные параметры цепного кода.
Структурная схема кодирующего устройства
bi-t = ai ai+t
bi-2t = ai-t ai
Вместе с тем, каждый проверочный элемент формируется двумя информационными ai+2t , ai+t. Т.о. количество информационных {ai} и проверочных {bi}элементов в кодовой последовательности, поступающей в к. с. всегда одинаково.
Структурная схема декодирующего устройства
Примечание: ai, bi до поступления в к.с., ai, bi после к.с., т.е. с возможными ошибками
Основной принцип проверки очень прост: формирование bi-“нов” и сравнение с выделенными символами: bi.
Наличие не сравнения является признаком ошибки.
Данная проверка проводится в соответствии с формулами:
Проверка элемента 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 …..ai2tbi2t …..ai-2tbi-2t …..
При этом возможны следующие варианты:
а.) ai ошибочен. Тогда это однозначно может быть обнаружено в том случае, если все остальные элементы, входящие в формулу (**) принять без ошибок.
Тогда: 1.) Признаком того, что ai ошибочен, является: L1=1, L2=1 => F=L1L2=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)
Рекуррентные коды предназначены в основном для исправления пакетов ошибок.
Операции кодирования и декодирования осуществляются над непрерывной последовательностью символов. Кодирование каждого ai осуществляется индивидуально.
1. При действии в канале связи пачек ошибок данный метод имеет существенные преимущества перед блочными кодами, т. к. предоставляет большие возможности для наиболее полного использования введенной избыточности. Пояснение: Для блочных кодов возможности обнаружения и исправления определяются избыточностью, которая введена в данную кодовую комбинацию. Поскольку ошибки встречаются относительно редко, то избыточность большинства кодовых комбинаций не используется. В то же время при появлении пачки ошибок введенной избыточности не хватает. При применении рекур. кодов достигается усреднение влияния помехи на большую последовательность передаваемых информационных символов.
Цепные коды простейшие рекуррентные коды, обладающие коэффициентом избыточности : r/n=0.5. Т. е. коды, имеющие одинаковое число информационных и проверочных символов
Корректирующие способности кода определяются параметром, который называется шагом сложения: t. Шаг сложения расстояние между двумя информационными элементами, суммируемыми по mod 2 для получения проверочных элементов bj.
Рассмотрим процедуры кодирования и декодирования и через основной параметр t определим структуру и основные параметры цепного кода.
Структурная схема кодирующего устройства
bi-t = ai ai+t
bi-2t = ai-t ai
Вместе с тем, каждый проверочный элемент формируется двумя информационными ai+2t , ai+t. Т.о. количество информационных {ai} и проверочных {bi}элементов в кодовой последовательности, поступающей в к. с. всегда одинаково.
Структурная схема декодирующего устройства
Примечание: ai, bi до поступления в к.с., ai, bi после к.с., т.е. с возможными ошибками
Основной принцип проверки очень прост: формирование bi-“нов” и сравнение с выделенными символами: bi.
Наличие не сравнения является признаком ошибки.
Данная проверка проводится в соответствии с формулами:
Проверка элемента 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 …..ai2tbi2t …..ai-2tbi-2t …..
При этом возможны следующие варианты:
а.) ai ошибочен. Тогда это однозначно может быть обнаружено в том случае, если все остальные элементы, входящие в формулу (**) принять без ошибок.
Тогда: 1.) Признаком того, что ai ошибочен, является: L1=1, L2=1 => F=L1L2=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)
А также другие работы, которые могут Вас заинтересовать | |||
22747. | Доктрина Ейзенхауера | 22 KB | |
Доктрина Ейзенхауера. У боротьбі за крісло у Білому домі Дуайт Ейзенхауер використав нову зовнішньополітичну доктрину замінивши політику стримування політикою відкидання звільнення ' від комунізму її теоретиком був Дж.Кеннана що у зовнішніх справах Ейзенхауер був людиною гострого політичного розуму і передбачуваності. Президент зазнав нищівної критики військові вимагали збільшення фінансування на звичайні озброєння але Ейзенхауер вистояв. | |||
22748. | Політика США щодо СРСР у першій половині 80-х рр | 27.5 KB | |
Політика США щодо СРСР у першій половині 80х рр. У зовнішньополітичній діяльності президента Рейгана варто розрізнити два періоди відповідно до термінів президентства: 19811984 рокичас різкої конфронтації з СРСР курсу на військову перевагу США у світі домінування силових методів у розв'язанні міжнародних конфліктів дії доктрини Рейгана доктрини неоглобалізму тобто протистояння з СРСР у будьякому куточку планети; 19851989 рокиперіод пошуку шляхів для виходу із політики глобального протистояння з СРСР нормалізації... | |||
22749. | Зрив США Паризької наради у верхах у 1960 р | 25 KB | |
обследовав сверхсекретные объекты Советского Союза Семипалатинский ядерный полигон авиабазу стратегических бомбардировщиков Ту95 близ него полигон противоракетной обороны в СарыШагане ракетный полигон ТюраТам космодром Байконур U2 выскользнул из пределов СССР южнее города Мары. Отмолчались и продолжили планирование разведывательных полетов над СССР. Дело в том что в мае должно было состояться совещание большой четверки США СССР Великобритании и Франции в Париже где предстояла новая встреча главы американского государства с... | |||
22750. | Теоретичні основи зовнішньої політики адміністрації Р. Рейгана | 30.5 KB | |
У зовнішньополітичній діяльності президента Рейгана варто розрізнити два періоди відповідно до термінів президентства: 19811984 рокичас різкої конфронтації з СРСР курсу на військову перевагу США у світі домінування силових методів у розв'язанні міжнародних конфліктів дії доктрини Рейгана доктрини неоглобалізму тобто протистояння з СРСР у будьякому куточку планети; 19851989 рокиперіод пошуку шляхів для виходу із політики глобального протистояння з СРСР нормалізації стосунків з СРСР підписання кардинальних договорів щодо... | |||
22751. | Провал інтервенції на Кубі 1961 р. та Карибська криза | 23 KB | |
Поскольку он сразу занял антиамериканскую позицию США поддержали противников Кастро и помогли им организовать высадку на Кубе апрель 1961 г. США поддержали высадку контрреволюционных групп на территорию Кубы в 1961 году. Поскольку Куба была расположена в 90 милях от побережья США большая часть их территории оказалась бы в сфере досягаемости ракет. США узнали об этом только из данных военной разведки когда ракеты уже были установлены и на этот раз действовали весьма жестко. | |||
22752. | Американсько-радянські переговори і угоди на найвищому рівні у 1991 р. Договір СНО-1 | 22.5 KB | |
Этот и другие недостатки Договора разный подход к ограничению охватываемых документом видов СНВ вывод за скобки установленных количественных пределов крылатых ракет морского базирования отказ США подтвердить свою приверженность Договору по ПРО по существу ставили под вопрос соответствие этого Договора принципу равенства и одинаковой безопасности США обеспечили себе возможность достижения военностратегического перевеса над СССР не выходя формально за рамки принятых обязательств. В соответствии с Договором СНВ1 более строгому... | |||
22753. | Участь УРСР у розвязанні територіальних проблем на Паризький мирній конференції | 55.5 KB | |
Підходи України до проблем реформування ООН. укладенням угоди про встановлення нового кордону між двома державами і поділом між ними зі згоди ООН Вільної території Трієст. Еритрея після проведення в ній референдуму за рішенням Генеральної Асамблеї ООН була приєднана до Ефіопії на федеративних засадах у 1952 р. Підходи України до проблем реформування ООН. | |||
22754. | Міжнародна громадськість про суть і значення конституційних змін в СРСР 1944р. Полеміка з цих питань | 74 KB | |
Становлення та розвиток відносин України з державами ЦСЄ. Миротворча діяльність України: досягнення та проблеми. При всьому тому членам КУК як українським патріотам імовірно імпонував вихід України на світову арену нехай і в такому ущемленому вигляді.Цегельський інформував громадськість що його делегація мала у СанФранціско зустрічі з усіма представниками Об'єднаних Націй домагаючись включення України в число учасників конференції . | |||
22755. | Участь делегації УРСР в роботі Дунайської конференції | 73 KB | |
право України було відновлено. У 19941996 роках ЄС ухвалив Спільну позицію щодо України 28 листопада 1994 р. Указом Президента України було затверджено Стратегію інтеграції України до ЄС розраховану на період до 2007 року. на Гельсінському самміті Євросоюзу була ухвалена Спільна стратегія ЄС щодо України яка спрямована на зміцнення стратегічного партнерства з Україною. | |||