Сверточные коды
Сверточные
(или рекуррентные) коды отличаются от
блоковых кодов структурой. В блоковом
коде n символов кода, формируемых
кодером в любой выбранный интервал
времени, зависят только от k
информационных символов, поступивших
на его вход в течение этого же интервала
времени. В сверточном коде блок из n
символов кода, формируемых кодером
в любой выбранный интервал времени,
зависит не только от k
информационных символов, поступивших
на его вход в течение этого же интервала
времени, но и от информационных символов,
поступивших в течение (K–1)
предыдущих интервалов. Параметр K
называется длиной кодового
ограничения. Для сверточных кодов
значение параметров n и k
выбираются малыми. Сверточные коды
могут использоваться для исправления
случайных ошибок, ошибок, группирующихся
в пакеты, и для тех и других. Кодер
двоичного сверточиого кода содержит
kK-разрядный регистр
и n сумматоров по mod
2. Обобщенная структурная схема кодера
сверточного кода приведена на рис.3.3.
Рис.
3.3. Обобщенная структурная схема
кодера сверточного кода
На
рис. 3.4 приведены пример кодера сверточного
кода с параметрами k =1,
n = 2,
K = 3,
Rk = 1/2.
Информационные символы поступают на
вход регистра, а символы кода формируются
на выходе коммутатора. Коммутатор (КМ)
последовательно опрашивает выходы
сумматоров по mod 2 в течение
интервала времени, равного длительности
информационного символа (бита).
Схема
подключения сумматоров по mod
2, значения k, n и K
полностью описывают сверточный код. Их
можно определить с помощью генераторных
векторов или многочленов. Например,
сверточный код, формируемый кодером,
изображенным на рис.3.4,
Рис.
3.4. Структурная
схема кодера несистематического
сверточного кода со скоростью 1/2
Информационные
символы имеет порождающие векторы
g1 = 111
и g2 = 101
и порождающие многочлены g1(х) = х2+х+1
и g2(х)=х2+1.
Кроме того, сверточный код может быть
задан импульсной характеристикой,
определяемой как последовательность
символов кода на выходе кодера при
подаче на его вход единственного символа
1. Легко проверить, что импульсная
характеристика данного кода равна
111011. Так как операция сложения по mod
2 является линейной операцией, то
сверточные коды относятся к классу
линейных, и выходная последовательность
кодера может рассматриваться как
результат свертки входной последовательности
с импульсной характеристикой кодера.
Отсюда и происходит название кода и
метода кодирования.
Процедуры
кодирования и декодирования удобно
описывать с помощью так называемого
кодового дерева, которое отображает
последовательности на выходе кодера
для любой возможной входной
последовательности. На рис. 3.5 приведено
кодовое дерево кодера, изображенного
на рис. 3.4, для блока из пяти информационных
символов. Если первый символ принимает
значение 0, то на выходе кодера формируется
пара символов 00. Если первый символ
принимает значение 1, то на выходе кодера
формируется пара символов 11. Это показано
с помощью двух ветвей, которые выходят
из начального узла. Верхняя ветвь
соответствует 0, нижняя – 1. В каждом из
последующих узлов ветвление происходит
аналогичным образом: из каждого узла
исходит две ветви, причем верхняя ветвь
соответствует 0, а нижняя – 1. Ветвление
будет происходить вплоть до последнего
символа входного блока. Вслед за ним
все входные символы принимают значение
0, и образуется только одна обрывающаяся
ветвь. Таким образом, каждой из возможных
входных комбинаций информационных
символов соответствует своя вершина
на кодовом дереве. В данном случае
имеется 32 вершины. С помощью кодового
дерева легко построить выходную
последовательность символов кода,
соответствующую определенной входной
последовательности. Например, входной
последовательности 11010 соответствует
выходная последовательность, лежащая
на пути, изображенном пунктирной линией.
Рис.3.5.
Кодовое дерево для кодера, изображенного
на рис. 3.4
Обозначим
четыре узла третьего уровня, т.е. узлы,
в которых происходит третье ветвление,
буквами a,b,c,d.
Повторяющаяся структура ветвей имеет
место и для узлов четвертого и пятого
уровней, поэтому их также можно обозначить
этими же буквами. Для узлов пятого уровня
любой из четырех комбинаций (11,10,01, 00)
первых двух входных символов будет
соответствовать один и тот же выходной
символ.
Такое
поведение можно объяснить следующим
образом. Когда входной символ поступает
в регистр (входной разряд R1),
то выходные символы зависят не только
от символа, записанного в R1,
но и от двух предыдущих символов,
хранящихся в R2
и R3.
Имеется четыре возможные комбинации
символов, хранящихся в R2
и R3:
00, 01, 10, 11. Обозначим эти четыре комбинации
или состояния регистра сдвига
соответственно буквами a,
b, c,
d как показано на
рис. 3.5. Количество состояний равно 2K–1.
Входные
символы 0 и 1 будут формировать четыре
различные комбинации выходных символов
в зависимости от состояния кодера. Если
входной символ 0, то на выходе декодера
будут формироваться 00, 10, 11 или 01 в
зависимости от того, в каком состоянии
находился кодер: a, b,
c или d.
To же самое правило можно
применить относительно символа 1.
Таким
образом, поведение кодера можно полностью
описать с помощью диаграммы состояний,
изображенной на рис. 3.6, а или
направленного графа с четырьмя состояниями
(рис. 3.6, б) который устанавливает
однозначное соответствие между входными
и выходными символами кодера. На графе
сплошные линии соответствуют входному
символу 0, а пунктирные – символу 1.
Например, если кодер находится в состоянии
а и на вход поступает 1, то на выходе
декодера будет формироваться комбинация
11 (пунктирная линия) и декодер перейдет
в состояние b,
соответствующее R3 = 0
и R2 = 1
– Аналогичным образом при поступлении
0 декодер останется в состоянии а
(сплошная линия) и на выходе будет
формироваться комбинация 00.
Заметим,
что прямой переход из состояния а в
состояние с или d
невозможен, причем из любого состояния
прямой переход возможен только в одно
из двух состояний. Диаграмма состояний
содержит исчерпывающую информацию о
структуре кодового дерева.
Рис.
3.6. Диаграмма состояний для кодера,
изображенного на рис. 3.4
Другим
полезным способом описания кодового
дерева является решетчатая диаграмма,
изображенная на рис. 3.7. Диаграмма берет
начало из состояния а и на ней
отображаются все возможные переходы
при поступлении на вход очередного
символа. Сплошным линиям соответствуют
переходы, происходящие при поступлении
символа 1 пунктирным – символа 0. При
поступлении на вход двух символов кодер
оказывается в одном из четырех состояний:
a, b,
c или d.
Заметим, что решетчатая диаграмма имеет
повторяющийся характер и может быть
легко построена с помощью диаграммы
состояний.
Рис.
3.7. Решетчатая диаграмма для кодера,
изображенного на рис.3.4
Вероятность ошибочного приема кода
для подготовки к Госэкзамену
Тема Кодирование информации
Кодами, обладающими максимальной защищенностью от помех, являются коды Грея. Они обеспечивают высокую точность преобразования непрерывной величины в код.
В качестве примера рассмотрим двоичный код Грея, применяемый для отображения десятичных чисел. Код использует десять кодовых комбинаций для каждого разряда, т.е. содержит четыре бита на каждый разряд десятичного числа (М = 10 < 24). Так как код двоичный, то каждый элемент кода может принимать значения «0» или «1». Основной особенностью кодов Грея является следующее. Последовательность кодовых комбинаций принята такая, что при изменении непрерывной величины каждый последующий отсчет непрерывной функции отображается кодовой комбинацией, отличающейся от предыдущей только в одном (любом) битовом разряде. Это позволяет свести ошибку считывания к минимуму, тем самым сделать код помехозащищенным.
В таблице приведены десятичные числа и вероятные кодовые комбинации для их отображения.
Для обеспечения помехоустойчивости кода вводят дополнительные разряды. Если, например, для кодирования всех символов внешнего алфавита достаточно иметь k -разрядный первичный код, то для обеспечения помехоустойчивости к разрядам первичного кода добавляется r избыточных разрядов. При этом длина результирующей кодовой комбинации становится равной n = k + r.
Избыточные коды бывают разделимыми и неразделимым и.
В разделимых кодах роль разрядов кодовых комбинаций разграничена: часть разрядов, часто совпадающая с разрядами исходного первичного кода, являются информационными, остальные разряды играют роль проверочных разрядов. В неразделимых кодах все разряды равноправные, и в кодовой комбинации нельзя отделить информационные разряды от проверочных.
В качестве примера неразделимого кода может служить код с постоянным весом «2 из 5». Особенностью этого кода является то, что в любой его кодовой комбинации длины 5 имеется ровно две единицы. Таким образом, всего разрешенных кодовых комбинаций кода «2 из 5 » имеется С25 = 5!/(2!×3!) = 10. Обнаруживающая способность данного кода основывается на свойстве, состоящем в том, что любая одиночная ошибка изменяет число единиц в кодовой комбинации.
Для оценки свойств помехоустойчивых кодов служит коэффициент избыточности кода.
где M – число возможных кодовых комбинаций, N – число разрешенных кодовых комбинаций.
Для разделимых кодов формула упрощается:
где n – длина кодовой комбинации; k – число информационных разрядов.
Видно, что коэффициент избыточности принимает значения от 0 (отсутствие избыточности) до 1 (избыточность неограниченно велика). Коэффициент избыточности характеризует качество помехоустойчивого кода: чем меньше избыточность кода при прочих равных условиях, тем код лучше.
Оптимальным с точки зрения экономичности часто считают такой код, при котором на передачу сообщений затрачивается минимальное время, то есть когда каждая кодовая комбинация передает максимальное количество информации. Если кодируемые значения не равновероятны, то для получения наибольшей информативности каждого элемента кода используют неравномерные коды, получившие название статистических кодов или кодов Шеннона – Фано. При построении неравномерных статистических кодов стремятся повысить информативность каждого символа. В этих кодах длина комбинации тем больше, чем меньше вероятность возникновения отсчета функции. Количество информации, которое содержится в одном элементе хода, определяется энтропией источника.
Характеристикой неравномерного кода является его средняя длина nср, определяемаякак математическое ожидание длин кодов по всему ансамблю кодируемых символов (отсчетов):
где ni – длина кодовой комбинации, соответствующая i-му символу; pi – вероятность i-го символа; М – число символов.
Найдем среднюю информацию, содержащуюся в одном закодированном символе:
Далее можно подсчитать количество информации, которое приходится на один символ кода:
Ik = H/nср
Код будет тем ближе к оптимальному, чем ближе полученное значение к единице.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Определить коэффициент избыточности неразделимого двоичного кода с постоянным весом «3 из 7».
Число возможных кодовых комбинаций длины 7 равно 27 = 128.
Число разрешенных кодовых комбинаций С37 = 7!/(3!*4!) = 35.
КИ = 1 – (log 35)/(log 128) = 0,267.
Определить коэффициент избыточности 8-разрядного разделимого двоичного кода с проверкой на четность.
Длина кодовой комбинации равна 8;
Число информационных разрядов равно 7.
КИ = 1 –7/8 = 0,125.
Требуется построить оптимальный с точки зрения экономичности двоичный код, отображающий 5 дискретных значений (отсчетов), если они возникают с вероятностями 1/2, 1/4, 1/8, 1/16, 1/16. Доказать, что построенный код экономичнее равномерного кода.
Для построения оптимального кода воспользуемся способом, по которому создаются неравномерные статистические коды Шеннона – Фано. Согласно этому способу, кодируемые символы разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0, а для второй группы символов – 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0, а для второй подгруппы – 1 и т.д.
Составим таблицу вероятности появления отсчетов:
Разделим отсчеты на две равновероятные группы, отнеся к первой отсчет х1 уровни, а ко второй – остальные. Для первой группы на первом месте кодовой комбинации поставим 0, а для второй группы – 1. Получим:
Поскольку в первой группе оказался только один отсчет, его кодирование закончено. Далее разделим вторую группу, а на две равновероятные подгруппы, в одну из которых отнесем отсчет х2, а в другую – остальные. Для первой полученной подгруппы на следующем месте кодовой комбинации поставим 0, а для второй подгруппы – 1. Получим:
Разделим оставшиеся отсчеты на следующие равновероятные подгруппы, отнеся к первой х3, а ко второй – остальные. Добавляя символы кода, получим:
Продолжая аналогично, получим окончательную кодовую таблицу:
Оценим оптимальность кода, найдя его среднюю длину и энтропию на один символ.
nср = 1/2 + 2·1/4 + 3·1/8 +2·4·1/16 = 1,875;
H = (-1/2·log21/2 -1/4·log21/4 – 1/8·log21/8 – 2·1/16·log21/16) = 1,.875.
Количество информации, приходящееся на один символ кода
Ik = H/nср = 1
В случае равномерного кода для кодирования пяти отсчетов мы вынуждены использовать кодовые комбинации из трех символов, т.е. длина кода будет равна 3. В этом случае количество информации, приходящееся на один символ кода, будет равно:
I’k = 1,875/3 = 0,625
Таким образом, построенный код более экономичен, чем равномерный.
Определить вероятности возникновения в двоичном симметричном канале нуля, одной, двух, трех ошибок в кодовой комбинации длиной 5, если вероятность ошибочного приема разряда равна 0,1.
Вероятность безошибочного приема
p0,5 = 5!/(0!*5!)*0,10*(1-0,1)5 = 0,59
Вероятность одной ошибки
p1,5 = 5!/(1!*4!)*0,1*(1-0,1)4 = 0,33
Вероятность двух ошибок
p2,5 = 5!/(2!*3!)*0,12*(1-0,1)3 = 0,07
Вероятность трех ошибок
p3,5 = 5!/(3!*2!)*×0,13*(1-0,1)2 = 0,008
Тема Преобразование информации
Преобразователями являются все устройства канала передачи информации: первичные преобразователи (датчики), усилители, антенные устройства, кабельные линии, конечные устройства отображения информации и пр. Все преобразователи вносят некоторые искажения в передаваемую информацию и характеризуются одними и теми же параметрами: чувствительность, линейность, коэффициент преобразования.
Коэффициент преобразования. Данные параметр можно определить, как отношение приращения выходной величины к вызвавшему его приращению входного сообщения:
где KП – коэффициент преобразования; Du – приращение выходной величины (u), Dx – приращение первичного сообщения (x).
Показатель KП однозначно характеризует лишь линейные и безинерционные преобразователи.
Преобразователь называется безинерционным, если значение KП не зависит от длительности (продолжительности) приращений Dx. Любой реальный преобразователь может считаться безинерционным лишь в определенном диапазоне длительностей приращений.
Преобразователь называется линейным, если имеет место зависимость u = u(x) = k0x + b, где k0, b – const. Любой реальный преобразователь может считаться линейным лишь в определенном диапазоне изменения величины x. Для линейного преобразователя KП = k0.
Чувствительность определяется минимальным значением первичного сообщения, которое еще может быть преобразовано в напряжение. Она определяется внутренними шумами преобразователя (датчика) и, следовательно, зависит от физических эффектов, на которых основана его работа.
С математической точки зрения квантование (дискретизация) может рассматриваться, как процесс замены исходной непрерывной функции приближенной дискретной функцией или функцией дискретного аргумента. С этих позиций всегда возникает проблема точности данного преобразования, т.е. проблемы максимального сохранения информации.
После обработки или передачи дискретной информации часто возникает необходимость восстановления информации в аналоговую форму. И в этом случае потери информации и вносимые искажения должны быть сведены к минимуму.
Существует несколько методов дискретизации – квантование по времени и квантование по уровню.
Квантование непрерывного сигнала по времени
С математической точки зрения квантование по времени является процессом замены непрерывной функции непрерывного аргумента F(t) функцией дискретного аргумента F(ti). Полученная функция непрерывна по своим значениям, но определяется лишь для дискретных моментов времени ti.
Нетрудно догадаться, что чем больше интервал квантования (чем меньше частота квантующих импульсов), тем больше должно теряться информации об исходном сигнале. И наоборот, чем выше частота квантования, тем точнее воспроизводятся подробности сигнала. Следовательно, должен существовать некоторый оптимальный интервал квантования Dt такой, который позволяет полностью представить исходный сигнал отсчетами, взятыми в соответствующие моменты времени. Оптимальность интервала понимается в том смысле, что выбор значения интервала больше оптимального приведет к потере информации. Уменьшение же значения интервала квантования по сравнению с оптимальным не приведет к росту информационного содержания сигнала, а приведет лишь к увеличению количества точек отсчета.
Оптимальный интервал квантования позволяет определить теорема Котельникова. Пусть функция x(t) есть реализация сигнала X(t), обладающая ограниченным спектром, т.е. содержит составляющие различных частот, не превышающие какую-то верхнюю граничную (критическую) частоту wкр. Одна из формулировок теоремы Котельникова гласит:
Непрерывный сигнал можно полностью восстановить из импульсного по значениям в точках квантования, если частота квантования не меньше удвоенной критической частоты.
Предположение о существовании некоторой критической частоты не является существенным ограничением для практики передачи информации, так как реальные физические устройства не допускают произвольно высоких частот, они «обрезают» их.
Квантование непрерывного сигнала по уровню
С математической точки зрения квантование по уровню является процессом замены непрерывной функции непрерывного аргумента F(t) дискретной функцией непрерывного аргумента Fi(t). Полученная функция определяется набором конечных дискретных значений на всем интервале t для любого момента времени.
Согласно указанному принципу, непрерывная функция времени заменяется другой, скачкообразной функцией с конечным числом возможных значений (уровней). Квантование по уровню по сути дела есть отображение непрерывного множества возможных значений сигнала на конечное подмножество значений, называемое уровнями квантования.
Правило квантования обычно выбирается таким, чтобы непрерывная величина X, лежащая в диапазоне iD < X < (i+1)D, заменялась значением iD (квантование по нижней границе), (i+1)D (квантование по верхней границе) или (i+1/2)D (квантование по середине). Такой вид квантования называется равномерным. Здесь i – целое число, а величина D является шагом квантования по уровню. При этом выполняется условие:
где Xmax, Xmin – экстремальные значения величины X; n – число уровней квантования.
На практике часто применяют оба рассмотренных вида квантования одновременно, то есть квантованный по времени аналоговый сигнал подвергают квантованию по уровню. При этом исходное непрерывное сообщение X(t) принимает вид дискретной функции дискретного аргумента – Yj(ti).
Восстановление непрерывного сообщения
На практике часто ограничиваются ступенчатой аппроксимацией или трапециевидной аппроксимацией. Если квантование произведено через одинаковые интервалы времени Dt = ТВ, то в первом случае
где П(t) = 1, при 0 < t < TВ, и П(t) = 0, при других t.
То есть в этом случае восстановленная функция имеет ступенчатый вид.
Во втором случае
Это означает, что функция имеет вид прямых линий, проходящих между каждыми двумя выборками.
Определить чувствительность линейного безинерционного преобразователя напряжения, если его коэффициент преобразования составляет 7, а при входном напряжении 0,3 мВ, выходное равно 1,4 мВ.
Для линейного безинерционного преобразователя справедлива зависимость
UВЫХ = aUВХ + b, где a = КП – коэффициент преобразования.
Можем записать: 7 × 0,3 + b = 1,4. Отсюда b = -0,7.
В результате получаем уравнение преобразователя:
UВЫХ = 7UВХ – 0,7.
Чувствительность преобразователя по определению – это минимальное значение входного напряжения, при котором преобразователь начинает работать. Тогда справедливо уравнение
7UВХ(min) – 0,7 = 0
Отсюда получаем: UВХ(min) = 0,1 мВ
Определить значение сигнала U = 2 + 5t – 2t2 в момент времени t = 1,7, если он был квантован по времени с периодом Т = 0,2, а затем восстановлен трапециевидной аппроксимацией.
В соответствии с заданным периодом квантования, отсчеты мгновенных значений сигнала были взяты в моменты времени t¢ = 1,6 и t²= 1,8. Значения сигнала в данные моменты времени составят:
U¢ = 2 + 5×1,6 – 2×1,62 = 4,88; и U² = 2 + 5×1,8 – 2×1,82 = 4,52.
При трапециевидной аппроксимации восстановленная функция имеет вид прямых линий, проходящих между каждыми двумя выборками. Поскольку заданный момент времени расположен ровно посередине между точками выборки, значение сигнала будет равно
Uвосс(1,7) = (U¢ + U²)/2 = (4,88 + 4,52)/2 = 4,7
Непрерывное сообщение квантуется по уровню и по времени. Шаг квантования по уровню равен 0,02 условной единицы. Какова должна быть максимальная величина интервала квантования по времени, если в спектре сигнала не содержится частот выше 1,0 кГц, а его производная изменяется не более, чем на 100 условных единиц в секунду.
Величина интервала квантования, вычисленная на основе теоремы Котельникова, будет равна
Тк1 = 1/2Fкр = 1/(2·1,0*103) = 5·10-4 c.
Исходя из шага квантования по уровню и скорости изменения функции, можно найти другую величину интервала, при которой уровни квантования будут различимы:
Тк2 = D/ v =0,02/100 = 2·10-4 c.
Из двух найденных величин следует выбрать меньшую – 2·10-4 c
Тема Передача информации по каналам связи.
При рассмотрении взаимодействия источника информации и канала передачи возникают понятия: поток информации и пропускная способность канала.
Поток информации это количество информации, передаваемое в единицу времени.
Для дискретного источника, передающего в канал связи N элементов в секунду поток информации (бит/сек) равен:
I = H(x)N
где H(x) – энтропия источника (равная среднему количеству информации на один элемент сообщения).
Максимальный поток информации по передающему каналу может быть записан:
где FК – полоса частот канала; DК – динамический диапазон канала.
Этот параметр называется пропускной способностью канала.
В свою очередь:
где NC – средняя мощность полезного сигнала; NШ – средняя мощность шумов.
Модели дискретных каналов передачи.
Вероятности, связывающие символы с одинаковыми индексами, называются вероятностями прохождения, остальные – вероятности трансформации.
Для определенных соотношений между вероятностями, входящими в данную матрицу можно выделить симметричные каналы, у которых элементы, входящие в строки и столбцы, являются перестановками одних и тех же чисел.
По основанию системы счисления кода на входе канала различают двоичные, десятичные и другие каналы.
Пропускная способность канала на логическом уровне определяется количеством бит на один символ (знак) и не связана со временем. Количество информации, передаваемое одним символом, составит
Imax = Hmax(Y) – Hmin(Y/X).
Если n – количество символов на входе канала, m – количество символов на выходе канала, слагаемые можно подсчитать так.
Максимальная энтропия выходного сигнала:
Определить полосу пропускания канала передачи на видеомонитор изображения, содержащего 5*105 элементов трех основных цветов. Изображение передается с частотой 25 кадров/с. Каждый элемент имеет 8 равновероятных градаций яркости. Полезный сигнал является шумоподобным, отношение мощностей сигнал/шум равно 15
Поток информации, рассчитанный через информационную энтропию, будет равен:
I = -(5*105)*25*3*log2(1/8) = 112,5×106 (бит/с).
Необходимая полоса пропускания:
Определить за какое время можно передать по каналу связи запись музыкального произведения, чтобы при последующем воспроизведении слышимые искажения отсутствовали. Продолжительность произведения 4,5 минуты, полоса частот канала 6 МГц, динамический диапазон канала в 4 раза уже диапазона произведения. Принять, что верхний предел частот, слышимых человеком равен 25 кГц
Объем передаваемой информации:
VC = FCDCTC = 25*103*DC*×4,5*60 = 6,75*106*DC бит.
Поскольку диапазон канала в 4 раза уже диапазона сигнала, т.е. D C = 4DK получим
VC = 27*106×DK бит.
Из выражения для объема канала и условия передачи получим:
TК = VC /(FКDК) = 27*106×DK/(6*106*DK) = 4,5 с
Сигнал подается на вход канала с вероятностью 0,6. Определить количество информации, передаваемое по каналу, если граф канала приведен на рисунке.
Матрица вероятностей будет иметь вид:
Вероятности P(хi) таковы: P(х1) = 0,6; P(х2) = 1 – 0,6 = 0,4.
Рассчитаем вероятности P(yi).
Р(у1) = Р(х1)Р(у1/х1) + Р(х2)Р(у1/х2) = 0,6×0,9 + 0,4×0,3 = 0,66;
Р(у2) = Р(х1)Р(у2/х1) + Р(х2)Р(у2/х2) = 0,6×0,1 + 0,4×0,7 = 0,34
Максимальная энтропия в выходных сигналах:
H(Y) = -Р(у1)×log2Р(у1) – Р(у2)×log2Р(у2) = -0,6× log20,6 – 0,4×log20,4 = 0,925
Энтропия шумов (условная энтропия):
Отсюда количество информации, передаваемое по каналу:
I = H (Y) – H (Y/X) = 0,925 – 0,634 = 0,29 бит/знак.
Определить количество информации, передаваемое по двоичному каналу со стиранием с равновероятными сигналами на входе, если вероятность искажения символа равна нулю, а вероятность стирания 0,1.
Матрица вероятностей передачи:
Вероятности на входе P(х1) = P(х2) = 0,5.
Вероятности на выходе:
Р(у1) = Р(х1)Р(у1/х1) = 0,5×0,9 = 0,45; Р(у2) = Р(у1) = 0,45
Р(уС) = Р(х1)Р(уС/х1) + Р(х2)Р(уС/х2) = 0,5×0,1 + 0,5×0,1 = 0,1
Отсюда максимальная энтропия в выходных сигналах по (6.11):
H(Y) = -Р(у1)×log2Р(у1) – Р(у2)×log2Р(у2) -Р(уС)×log2Р(уС) =
-0,45×log20,45 -0,45×log20,45 -0,1×log20,1 = 1,369
Энтропия шумов по (6.12):
Отсюда количество информации, передаваемое по каналу по (6.10):
I = H (Y) – H (Y/X) = 1,369 – 0,469 = 0,9 бит/знак.
Тема Конечные автоматы
Конечный автомат – одна из схем первичной формализации дискретных устройств и процессов, это математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных.
Конечный автомат имеет один вход и один выход. Он представляет собой объект, функционирующий в дискретные моменты времени tj. В каждый момент времени автомат находится в одном из возможных состояний z(tj) (число возможных состояний предполагается конечным). В каждый момент на вход автомата поступает входной сигнал.
Автомат следующим образом реагирует на поступление входных сигналов.
Во-первых, состояние автомата изменяется в соответствии с одношаговой функцией переходов:
Во-вторых, в каждый момент автоматного времени на выходеавтомата появляется выходной сигнал y(tj), определяемый функцией выходов
Для задания конечного автомата необходимо описать входной, выходной и внутренний алфавиты, а также функции переходов и выходов. При этом наиболее часто используются табличный, графический и матричный способы.
Рассмотрим табличный способ задания автомата. При этом используются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. На пересечении i -ой строки и j -го столбца таблицы переходов помещается соответствующее значение j(zk,xi) функции переходов, а в таблице выходов – y(zk, xi) функции выходов.
При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi с вершиной zj, обозначается xk. Для того, чтобы задать функцию выходов, дуги графа необходимо дополнительно отметить соответствующими выходными сигналами.
На практике наибольшее распространение получили два класса автоматов – автоматы Мили(Mealy) и автоматы Мура(Moore).
Автомат Мили функционирует следующим образом. И состояние автомата и его выходной сигнал зависят от входного сигнала и предыдущего состояния.
Для автомата Мура функция переходов имеет тот же вид, как и у автомата Мили, но функция выходов не зависит от входного сигнала, а является функцией только текущего состояния:
По заданным таблицам переходов и выходов для конечного автомата с тремя состояниями, двумя входными и двумя выходными сигналами построить граф автомата и матрицы переходов и выходов. Определить к какому классу относится данный автомат.
Таблица переходов Таблица выходов.
Граф автомата, заданного исходными таблицами:
Матрицы переходов и выходов:
Поскольку, как состояние автомата, так и его выходной сигнал зависят от входного сигнала и предыдущего состояния, рассматриваемый автомат относится к классу автоматов Мили.
Тема Дискретные цепи Маркова
Если переходы системы из одного состояния в другое возможны в строго определенные, заранее фиксированные моменты времени tj, то такую систему описывает марковский случайный процесс с дискретным временем. Марковский случайный процесс с дискретными состояниями и дискретным временем называют дискретной марковской цепью.
Полным описанием марковской цепи служат матрицы переходных вероятностей:
Кроме того, на каждом шаге Марковская цепь характеризуется вектором вероятностей состояний:
Вероятностью i- го состояния называется вероятность Si(t) того, что в момент t система будет находиться в состоянии Ai. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:
Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. Если переходные вероятности меняются от шага к шагу, марковская цепь называется неоднородной.
Все многообразие Марковских цепей подразделяется на эргодические и разложимые.
Эргодические Марковские цепи описываются сильно связанным графом. Это означает, что в такой системе возможен переход из любого состояния Ai в любое состояние Aj (i = 1.n) за конечное число шагов.
Оценка требуемой исправляющей способности кода для обеспечения заданной верности приема блока
Положим
что вероятность ошибки двоичного
элемента в
Сообщения
источника требуется передавать блоками
по n-двоичных символов.
Требуется
обеспечить вероятность неправильного
приема блока не более некоторой заданной
величины
Рассмотрим
все возможные ситуации при приеме
последовательности из n – элементов.
Совокупность
всех возможных исходов будет составлять
полную группу событий. Поэтому можно
записать:
–
это вероятность того, что в блоке будет
хотя бы одна ошибка. Другими словами –
это есть
,
то необходимо обеспечить исправления
ошибок некоторой кратности в блоке.
Оценим,
ошибки какой кратности нужно исправить.
Найдем
вероятность неправильного приема при
исправлении однократной ошибки. Она
будет равна:
Вновь
проводим сравним Рн.п
и
А, если требования не выполнилось, то
убираем 2х,
3х
и
т.д. кратной ошибки.
Последняя
кратность ошибки, вычитание вероятности
которой привело к выполнению условия
и будет требуемой исправляющей
способностью кода.
При этом
из всех n-элементов блока, часть (r)
необходимо будет отдать на проверочные
элементы, что естественно внесет
избыточность в передаваемое сообщение
и понизит скорость передачи
Контрольные
вопросы по теме:
УПС –
обеспечивают согласование параметров
сигналов источника с параметрами канала
связи.
Согласование
может производиться по:
– полосе
частот;
– уровню;
– скорости.
Согласование
спектра может производиться двумя
путями:
Известно,
что спектр последовательности
прямоугольных импульсов имеет вид (sin
x)/x с максимумом на нулевой частоте.
Основная энергия сигналов в этом случае
сосредоточена в полосе частот
Канал
связи, из-за наличия развязывающих
трансформаторов, не пропускает постоянную
составляющую. Из-за этого однополярные
сигналы будут испытывать значительные
искажение.
При
перекодировании исходные сигналы
заменяются сигналами другой структуры
спектральные характеристики которых
лучше согласуются с параметрами заданного
канала связи.
Помимо
основной задачи – согласования спектров
при перекодировании стараются подобрать
такой код, который обеспечивал бы:
Простейшим
решением является биполярный код (None
return zero NRZ)
Преимущество:
малая полоса пропускания; простая
реализация; нет избыточности.
Недостатки:
потеря
синхронизации при длинных сериях
элементов одного знака.
Обычно при
перекодировании в сигнал вводится
избыточность.
Различают
два способа введения избыточности.
1. Увеличение
в процессе перекодирвания основания
кода (увеличение числа значащих позиций
было две значащих позиции, а стало 3).
Например,
код с чередованием полярности (КЧП он
же AMI)
0 заменяется
на 0, а 1 на ± 1 – чередуется
2. При втором
подходе каждый элемент на единичном
интервале заменяется двумя разнополярными
импульсами
Очевидно,
что избыточность такого кода 0,5 (то есть
больше чем у КЧП)
+ Так как
сигнал изменяется по крайней мере один
раз на единичном интервале, то такой
код обладает хорошими самосинхронизирующими
свойствами.
+ Отсутствие
постоянной составляющей
+ Если
перепада на единичном интервале нет,
то ошибка
Рассмотренный
код называют МАНЧЕСТЕРСКИМ
Он находит
широкое применение в технологиях
локальных сетей, а именно в Ethernet и Token
ring.
Следует
обратить внимание на спектр кода.
При
чередовании 1 и 0 основная гармоника
спектра становиться в два раза ниже (по
частоте) в сравнении с ситуацией, когда
идут элементы одного знака.
(Применительно
к Ethernet со скоростью 10 Мбит /с, частота
несущей 5 или 10 МГц.)
Для вхождения
в синхронизм перед каждым пакетом
передается преамбула, составляющая из
7 байт чередования 10101010 и восьмого
10101011.
Оба подхода
позволяют устранить постоянную
составляющую, чем и достигается
согласование.
В сетях
ISDN и системах xDSL широкое применение
находит код 2B1Q.
Для передачи
используется 4 значащих позиции, при
этом один импульс несёт 2 бита информации
Очевидно,
что для данного кода скорость передачи
информации в два раза выше скорости
модуляции R=2B, или можно сказать при
заданной R требуется меньшая полоса
частот канала.
Применение
логического кодирования для улучшения
свойств потенциальных кодов.
Потенциальные
коды КЧП, Биполярный Код, 2B1Q-имеют более
узкую полосу частот, что является их
преимуществом, но страдают появлением
постоянной составляющей и потерей
синхронизации при передаче длинных
серий одинаковых элементов или групп.
Для борьбы
с этим явлением применяют логическое
кодирование (ЛК).
ЛК –
заменяет длинные последовательности
элементов, приводящих к постоянному
потенциалу другими последовательностями
устраняющими данный недостаток.
Для
логического кодирования характерны 2
метода:
Избыточные
коды основаны на разбиении исходной
последовательности на порции (символы)
и замене исходной порции, новой имеющей
большее количество бит.
Так как
символы содержат избыточные биты, то
общее количество кодовых комбинаций в
них больше, чем в исходных.
Например,
код 4В/5В. Каждые четыре элемента исходной
последовательности заменяются пятью
элементами выходного кода. Выходные
элементы выбираются таким образом,
чтобы избежать длинных серий “опасных”
элементов приводящих к появлению
постоянки или потере синхронизации.
Остальные комбинации выходного кода
считаются запрещёнными, что позволяет
обнаружить ошибки.
устранение
постоянной составляющей
улучшение
синхронизирующих свойств
обнаружение
ошибок.
4В/5В
используется в FDDI и Fast Ethernet.
8B/6T
– Fast Ethernet.
8В/10В
– Gigabit Ethernet
Скремблирование
– обратимое преобразование структуры
цифрового потока без изменения скорости
передачи с целью получения свойств
случайной последовательности.
6.2
Методы преобразования спектра с
использованием несущей
Чаще всего
в качестве несущей используют гармоническое
колебание:
Воздействуя
на соответствующий параметр амплитуду,
частоту или фазу, получаем соответственно
амплитудную, частотную или фазовую
модуляцию
Рассмотрим
данные виды модуляции с точки зрения
их применимости в технике передачи
данных.
Рассмотрим
связь ширины спектра и скорости модуляции.
Известно,
что если на вход идеального фильтра (с
прямоугольной АЧХ и линейной ФЧХ) подать
ступенчатую функцию, то на выходе будет
присутствовать переходной процесс,
длительность которого обратно
пропорциональна граничной частоте ФНЧ.
Длительность
импульса передаваемого через такую
систему не может быть менее чем время
нарастания.
Значит,
минимальная длительность сигнала равна
Так как АМ
сигнал в общем случае содержит и верхнюю
и нижнюю боковые полосы частот, то ширина
спектра АМ сигнала в 2 раза больше
исходного – модулирующего.
Если
задана полоса пропускания канала
,
то необходимо выбирать
Значит
предельная скорость передачи по каналу
при АМ
АМ – модулятор
в простейшем случае:
Спектр
сигнала в этом случае выглядит так
Проведем
оценку предельной скорости модуляции
при ЧМ
Пусть
задана полоса канала
При
максимальном использовании полосы
канала
Определим
ширину полосы канала постоянного тока
Таким
образом, при заданном значении
максимальная
скорость модуляции при ЧМ меньше, чем
при АМ, но помехоустойчивость при
частотной модуляции выше, поэтому она
находит ограниченно применение в
системах передачи дискретных сообщений.
нижняя
полоса для вызывающего модема 1 – 980 Гц,
0 – 1180 Гц
верхняя
полоса (отвечающий ) 1 – 1650 Гц, 0 – 1850 Гц
Протокол
V.21 – является ’’ аварийным ’’
Рекомендация
V.23 R=B=600 или 1200
КТЧ делится
на основной и обратный канал.
основной
при 1200 бит/с fср=1700,
при 600 бит/с
fср=1500,
Обратный
R=75 бит/с для передачи сигналов подтверждения
качества приёма.
В данном
случае амплитуда и частоты постоянны,
изменяется фаза в соответствии с
модулирующим сигналом.
Если
модулирующий сигнал двоичный “1” или
“0”, то значение фазы модулирующего
сигнала тоже две. Это значение отсчитывается
от фазы несущей.
Обычно,
при передачи “1” модулятор формирует
синусоидальный сигнал, фаза которого
совпадает с фазой несущей. При
Спектр
ФМ – сигнала.
Из диаграммы
видно, что ФМ состоит, как бы, из двух АМ
сигналов несущие которых имеют одинаковую
частоту, а фазы сдвинуты на 180°
Поэтому
спектр ФМ сигнала будет таким же, как у
АМ по ширине, а несущая подавляется
из-за противофазности. Но все составляющие
увеличатся в 2 раза. Так как амплитуды
составляющих больше, то у ФМ выше
помехоустойчивость.
Для ФМ
можно записать
Структурные
схемы ФМ – сигнала
Дискретный
канал с ФМ
На приемной
стороне при демодуляции принятый сигнал
сравнивается с опорным сигналом, при
этом если фазы совпадают, то была 1, нет
– 0.
Если фаза
опорного сигнала изменится на 180° , то
1 будет воспринята как 0, а 0
1.
Такой эффект называется “ОБРАТНОЙ
РАБОТОЙ”.
“Обратная
работа” – это основной недостаток
абсолютной фазовой модуляции, именно
по этой причине фазовая модуляция не
нашла широкого применения в технике
ПДС.
Исключение
явление “обратной работы” обеспечивается
относительной фазовой модуляции ОФМ.
При ОФМ
отсчет фазы передаваемого сигнала
производится не относительно несущей,
а относительно предыдущего элемента.
При модуляции
единицы, фаза элементов такая же, как у
предыдущего, при нуле меняется на
противоположную.
Следует
отметить, что фаза первого элемента
неопределенна, так как для него нет
предыдущего. Прием начинается со второго
элемента.
Для получения
ОФМ используют те же модуляторы, что
для АФМ, но перед подачей на модулятор
исходную последовательность перекодируют.
Если в
исходной последовательности 0, то
соответствующий элемент выходной
последовательности изменяется на
противоположный относительно предыдущего.
Если “1”, то текущий элемент такой же,
как предыдущий.
Прием ОФМ
сигналов возможен двумя способами.
1. способом
сравнения фаз (некогерентный прием);
Полосовой
фильтр отсекает помехи вне полосы
сигнала. Элемент памяти задерживает
сигнал на один единичный интервал. Ф Д
– сравнивает сигнал с предыдущим –
задержанным. Если фазы совпадают, то
принята “1”, если нет то “0”.
2. способом
сравнения полярностей (когерентный).
В данном
случае схема устройства выделения
опорного сигнала формирует его из
рабочей последовательности. Далее идет
сравнение фазы каждого единичного
элемента с фазой опорного, как у АФМ.
Полученная в результате последовательность
поступает в ПКУ, где перекодируется, и
на выходе получаем исходную
последовательность, так как информация
заложена в изменении фазы относительно
предыдущего. “ Обратной работы” не
будет. Однако при ошибке в одном элементе
вылетают два, этот и последующий, который
с ним сравнивается.
Правила
перекодирования ПКУ приема:
Если во входной последовательности
изменилась значащая позиция, то в
выходной последовательности – 0, если
нет – 1.
В “сравнении
фаз” при принятии решения используют
два зашумленного сигнала.
В “сравнении
полярностей” один зашумленный и один
“чистый” – опорный.
Поэтому “полярный”
достовернее.
Следует
заметить, что один ошибочный элемент
до ПКУ вызывает две ошибки после ПКУ.
ОФМ
используется в модемах разработанных
по рекомендации V.26 на скорости 1200 бит
/ сек.
Как было
показано ранее, скорость модуляции в
канале определяется шириной спектра
канала:
Канал ТЧ
имеет спектр 0,3 – 3,4 к Гц. D Fтч =3,1 к Гц.
Таким
образом, максимальная скорость модуляции,
которую теоретически можно достичь в
кТЧ 6,2 Бод (передача одной боковой) 3,1
кБод (при передаче двух боковых).
Реально
же в модемах используются скорости
модуляции обычно 1200 и 2400 Бод.
Если для
передачи использовать двухпозиционный
сигнал, то скорость передачи информации
будет такой же низкой R=B=2400 Бит/сек.
Такие
скорости сегодня не устраивают
потребителя.
Выходом в
данном случае является использование
сигналов переносящих более чем 1 бит
информации (то есть многопозиционных
сигналов).
Многопозиционный
сигнал имеет более чем две значащих
позиции
Применение
данного принципа к относительно фазовой
модуляции называется многопозиционной
ОФМ.
Рассмотрим
простейший случай Двукратная ОФМ.
При
ДОФМ два соседних сигнала могут отличаться
по фазе на одно из четырех возможных
значений.
Первоначально
исходная последовательность разбивается
на дибиты (по 2 элемента), а затем каждый
дибит кодируется на единичном интервале
в соответствии с модуляционным кодом.
В данном
случае обеспечивается R=2B.
Диаграмма
ДОФМ на сигнальной плоскости выглядит
так.
B = 600 Бод.
В режиме ОФМ – 600 бит/с. В режиме ДОФМ –
1200 бит/с.
Еще более
повысить скорость R можно используя:
трехкратную
(восьмипозиционную) или
четырехкратную
(шестнадцати позиционную ) модуляции.
Однако при
увеличении числа разрешенных сдвигов
фаз резко уменьшается помехоустойчивость
ОФМ.
Уменьшается
расстояние между разрешенными сигналами
в пространстве. Вследствие этого, ОФМ
кратностью более трех не используется.
Для большего
увеличения скорости передачи используют
амплитудно-фазовую или так называемую
квадратурную – амплитудную модуляцию
КАМ.
В КАМ
изменяется не только фаза, но и амплитуда.
На рисунке показана диаграмма КАМ –
16.
Использование
КАМ – 16 позволяет при скорости модуляции
2400 Бод,
получать
скорость передачи информации 2400 ´ 4 =
9600 бит/с.
Такая
модуляция используется в протоколе
V. 32, R до
9600 в.p.s.
Квадратурная
модуляция имеет большую помехоустойчивость
в сравнении с многократной ОФМ. Но при
увеличении числа позиций свыше 16 и ее
помехоустойчивость оказывается
недостаточно для качественной передачи.
Поэтому
во всех современных высокоскоростных
протоколах КАМ используется, в совокупности
с помехоустойчивым кодированием.
В качестве
ПУ кодирования используется один из
видов сверточных кодов – решетчатый
код. Такое совместное кодирование
получило название “Треллис – модуляции”
(ТСМ).
При
применении Треллис – модуляции число
сигнальных точек увеличивается вдвое
за счет добавления к информационным
битам одного избыточного, образованного
путем сверточного кодирования.
Треллис –
модуляция используется уже в протоколе
V. 32, как альтернатива КАМ – 16. В этом
случае к 4 информационным добавлениям
1 проверочный разряд. Получается 32 точки
из которых выбирается 16 разрешенных.
Треллис – модуляция обеспечивает
большую помехоустойчивость.
Треллис –
модуляции используется в более поздних
протоколах
V.
32 bis – 14.4 b p.s.
V.34 bis – 28.8 b p.s.
Синхронизация
–
это процедура установления и поддержания
определенных временных соотношений
между двумя и более процессами.
Различают
поэлементную, групповую и цикловую
синхронизацию.
При
поэлементной
синхронизации устанавливаются и
поддерживаются требуемые фазовые
соотношения между значащими моментами
переданных и принятых единичных элементов
цифровых сигналов данных. Поэлементная
синхронизация позволяет на приеме
правильно отделить один единичный
элемент от другого и обеспечить наилучшие
условия для его регистрации.
Групповая
синхронизация
– обеспечивает правильное разделение
принятой последовательности на кодовые
комбинации.
Цикловая
синхронизация
– обеспечивает правильное разделение
циклов временного объединения.