Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2022-11-24 | 52 |
5.00
из
|
Заказать работу |
|
|
Пусть источник вырабатывает 3 символа
x0->p(x0)
x1->p(x1)
x2->p(x2)
Типичная последовательность – если сигнал совпадает со значениями вероятностей, иначе не типичная.
Теорема о равномерности длинных последовательностей.
- все последовательности достаточно большой длины n можно разбить на 2 группы: 1 группа содержит большинство последовательностей, каждая из которых имеет настолько малую вероятность, что даже суммарная вероятность всех таких последовательностей очень мала, и при достаточно большом n будет меньше сколь угодно малого числа. Такие последовательности будут нетипичными для источника.
2 группа включает типичные для источника последовательности, которые отличаются тем, что вероятность их появления практически одинаковые, причем для вероятностей этих последовательностей справедливо утверждение:
p(qi QT)=Const=pT
бесконечно малая величина
Типичные последовательности различаются только содержанием.
Доказательство:
С увеличением длины последовательности () источник с вероятностью близкой к 1 начинает вырабатывать лишь типичные для него последовательности. Если учесть что вероятности у нас одинаковые, то общее число таких последовательностей:
(энтропия Н(х))
X={xi}, mx
n*p(xi)=ni – число повторений i-го символа.
n*p(x1); n*p(x2)… n*p(xn)
pT=p(x1)^(n*p(x1))*…..
доказали)
Отношение кол-ва типичных последовательностей ко всему числу NT/N?
N=mxn = 2n *log2 mx
NT=1/pT
Выразим NT через энтропию H(x)
=>NT<<N
log mx – это Hmax
- избыточность
Если D(x)=0, то все последовательности типичные.
Mx=16, H(x)=3.5bit => Hmax 4 при n=50
NT/N~1/30*106
Возможность (теоретическая основа)экономного кодирования сообщений.
Теорема Шеннона о кодировании канала без помех.
|
Если производительность источника сообщений не превышает пропускной способности канала связи, существует метод кодирования позволяющий передавать по каналу связи все сообщения, выработанным источником без накопления в передающем устройстве.
Если производительность источника не превышает пропускной способности канала без помех, то существует способ кодирования, позволяющий приблизить ср длину кодового слова к энтропии источника: П (х) ≤Скс
|
Скс=максVn=maxVткс*Hmax(Y)
П(x)=Vтн*H(x) б/сек
N=H(x)/Hmax(Y)=Logmymx при равномерном.
n ср H (x) -использование хорошее
T/r=nu – длина сообщения.
VT*T=nk
Nk=mynk – число разнообразных кодовых слов.
=2nk*log my=2T*Vt*log my
CКС=max VT[H(Y)-H(Y\Z)] H(Y/Z) = 0 т.к. нет помех
=VT*log my=2T*Cкс
П(х)<=Скс
NT=2T*П(х) <= NK=2T*Ckc
Для канала связи без помех можно всегда закодировать передаваемое сообщение таким образом, чтобы приблизить скорость передачи к пропускной способности канала связи.ё
Принципы и свойства экономного кодирования.
VTH – скорость выработки сигналов источником.
Если не будет помех(КС без ошибок)
Скорость передачи можно повысить приблизив H(x)->Hmax и
Причины избыточности:
1.
2.
Экономное кодирование применяется при передаче сообщения по каналу без помех для повышения эффективности использования КС, путем повышения скорости передачи информации до величины близкой к пропускной способности канала связи.
Согласование производительности источника сообщений с пропускной способности КС.
Перед отправкой сообщения, их перекодируем таким образом, чтобы на выходе символы были не зависимы, и вероятность была постоянной.
Кодир.первич | вероятность | |
х1 | 000..00 | P1 |
x2 | 000..01 | P2 |
x3 | 000..10 | P3 |
… | ||
xn | 111..11 | Pn |
– пусть символы не взаимосвязаны, нет корелляции.
При посимвольном кодировании ->неравномерная длина слов разная.
|
Выигрыш в случае
Требования к экономному кодированию:
1. Средняя длина кодируемого слова должна быть минимальна – для этого необходимо выбирать длины кодовых слов с учетом вероятности появления символов. Чем больше вероятность, тем меньше длины кодируемых слов. Использование неравномерного кода будет приводить к сложностям при декодировании сообщений.
2. Экономное кодирование должно обеспечивать однозначное декодирование сообщений.
Однозначно декодируемые коды. Неравенство Крафта.
Все возможные коды | |
Инъективные | Для которых кодовые слова не повторяются |
Однозначно-декодируемые | Можно разделить на кодовые слова любую последовательность |
Префиксные коды | Ни одно кодовое слово не начинается с другого более короткого |
Для получения префиксного кодового слова необходимо построить кодовое дерево:
0 ярус: корень дерева, из которого выходит столько ветвей, сколько символов находится в алфавите.
1 ярус: образуются слова единичной длины
Кодовым словом будут считаться соответствующие конечные узлы графа. Двигаемся от корня к конечному узлу.
Предположим, что выбрано распределение длин кодовых слов по символам источника.
Можно ли для заданного распределения длин построить префиксный код (или однозначно-декодируемый)?
Да, с помощью неравенства Крафта.
Необходимым и достаточным условием существования префиксного кода с объемом mx и длинами кодовых слов ni является выполнение условия:
Для любого однозначно-декодируемого кода с длинами слов ni неравенство Крафта будет также выполняться.
n-const=2 4*2-2=4*1/4=1=<1 (01 10 00 11)
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!