Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Лекция 4-2. Основные понятия теории кодирования

Основные понятия теории кодирования
Основные понятия теории кодирования Проблема распознавания взаимной однозначности кодирования Теорема 3.2.1. Если схема обладает свойством префикса, то алфавитноекодирование является взаимно-однозначным.Таким образом, Алгоритм проверки однозначности кодирования Теорема Маркова о взаимной однозначности алфавитного кодирования:Пусть— некоторое кодирование. Пусть W — Доказательство. Пусть ϕ не является взаимно однозначным. Тогда существует некоторое слово Лемма. Если   — неприводимое слово, то все слова β1, β2, Слова из второго класса разбивают слово не более чем на  L
Слайды презентации

Слайд 2 Основные понятия теории кодирования

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

Слайд 5 Проблема распознавания взаимной однозначности кодирования

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

Слайд 6 Теорема 3.2.1. Если схема обладает свойством префикса, то

Теорема 3.2.1. Если схема обладает свойством префикса, то алфавитноекодирование является взаимно-однозначным.Таким

алфавитное
кодирование является взаимно-однозначным.

Таким образом, свойство префикса является достаточным условием

взаимной
однозначности.

Слайд 8 Алгоритм проверки однозначности кодирования

Алгоритм проверки однозначности кодирования

Слайд 12 Теорема Маркова о взаимной однозначности алфавитного кодирования:
Пусть
— некоторое

Теорема Маркова о взаимной однозначности алфавитного кодирования:Пусть— некоторое кодирование. Пусть W

кодирование. Пусть W — максимальное число кодовых слов, которые

«помещаются» подряд внутри кодового слова. Пусть li — длина слова Bi и

Тогда если кодирование φ не взаимно однозначно, то существуют два различных слова


Слайд 13 Доказательство.
Пусть ϕ не является взаимно однозначным. Тогда

Доказательство. Пусть ϕ не является взаимно однозначным. Тогда существует некоторое слово

существует некоторое слово , которое допускает две

расшифровки. Если слово не является неприводимым, то выбрасывая из куски несколько раз, получим неприводимое слово ; иначе, положим . Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки слова . Разрежем слово в концевых точках кодовых слов каждого из разбиений.
Слова нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).

Слайд 14 Лемма. Если — неприводимое слово, то

Лемма. Если  — неприводимое слово, то все слова β1, β2,

все слова β1, β2, …, βm II класса различны.
Доказательство.

Пусть β' = β''. Тогда, очевидно, слово не будет неприводимым, поскольку при выкидывании отрезка между β' и β'', вместе с любым из этих слов, получим снова две различные расшифровки этого слова (проверьте). Лемма доказана.

Таким образом, все β1, β2, …, βm разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит


Слайд 15 Слова из второго класса разбивают слово не более

Слова из второго класса разбивают слово не более чем на L

чем на L – r + 1 кусков. Рассмотрим

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

а в каждом из них укладывается слов не более чем W + 1. Отсюда число кодовых слов в любом разбиении не превосходит

а поскольку число целое, то не превосходит и целой части

Теорема доказана.


  • Имя файла: lektsiya-4-2-osnovnye-ponyatiya-teorii-kodirovaniya.pptx
  • Количество просмотров: 127
  • Количество скачиваний: 0