Кодирование дискретных источников

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

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

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

Дальше сформулируем предельные способности статистических ко­дов.

Разглядим сначала последовательность Вп = (b(1),...,b(n)) сле­дующих вереницей п частей дискретного источника {В,р(b)}. Каждый элемент выбирается из алфавита {bi, ...,bк}, и, таким макаром Кодирование дискретных источников, имеются Кп последовательностей различной длины п, которые могут появляться на выходе источника. Поставим задачку кодировки этих последовательностей в слова кода с фиксированной длиной. Если ко­довый алфавит состоит из m знаков и если длина каждого кодового слова равна l, то есть ml разных кодовых слов. Следова­тельно Кодирование дискретных источников, если необходимо сравнить разные кодовые слова различным по­следовательностям источника (если нужно взаимно однозначное отображение), то получаем . Таким макаром, для кодов с фиксированной длиной при декодировании нужно иметь по мень­шей мере log К/ log M кодовых знаков на одну буковку источника.

Если мы желаем в целях действенного кодировки использовать меньше Кодирование дискретных источников, чем log К/ log M знаков на одну буковку источника, то, оче­видно, необходимо ослабить требование того, чтоб всегда была возмож­ность полного конкретного соответствия.

В доказательство произнесенному разглядим пример [1]. Предполо­жим, что на телеграфе введена автоматическая обработка телеграмм,

записанных в алфавите объемом 64 буковкы (количество букв, содержа Кодирование дискретных источников­щееся в 2-ух регистрах телетайпа). Пусть эффективность обработки ин­формации определяется количеством телеграмм, которые можно вве­сти в запоминающее устройство (ЗУ). Объем ЗУ равен N двоичным ячейкам. Нужно закодировать телеграммы двоичным кодом.

Разглядим сначала побуквенное кодирование. В данном случае ис­пользуется код, содержащий 26 = 64 кодовых слова, и каждой буковке телеграммы сопоставляется Кодирование дискретных источников некое кодовое слово. Пусть использу­ется равномерный код со словами в 6 двоичных знаков. При всем этом в ЗУ можно поместить N/6 букв. Если считать, что средняя длина те­леграммы — 20 слов, а средняя длина слова 8 букв, то в ЗУ можно поместить приблизительно N/960 телеграмм.

2-ой метод кодировки заключается Кодирование дискретных источников в том, что выделяется специ­альный словарь, к примеру, из 213 = 8192 слов (довольно фактически для хоть какой телеграммы). Каждое слово может быть закодировано при помощи двоичной последовательности длиной 13 знаков. В данном случае в ЗУ можно записать N/260 телеграмм, т.е. в 3-4 раза боль­ше, чем в первом случае. (При кодировке и декодировании Кодирование дискретных источников можно считать слово, отсутствующее в словаре, «ошибкой».)

Таким макаром, 2-ой метод является существенно более эффек­тивным исходя из убеждений трудности ЗУ. Эта эффективность является следствием устранения избыточности, хотя при кодировке по второму методу вероятны ошибки, так как существует опасность возникновения слова, не входящего в кодовый словарь. При побуквенном кодировке Кодирование дискретных источников обеспечивается безошибочное декодирование.

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

Постановка задачки равномерного кодировки источника.Пусть А = {а1,..., ат}— алфавит кода источника — некое мно­жество, состоящее из m частей; аi — кодовые знаки. Последо­вательность кодовых знаков задает Кодирование дискретных источников кодовое слово, хоть какое семейство кодовых слов — это код над алфавитом А. (Примеры: огромное количество букв российского алфавита, огромное количество цифр и т.д.) Код именуется равномер­ным, если все его слова имеют схожую длину l, именуемую длиной (значностью) кода. В неприятном случае код именуется неравномер Кодирование дискретных источников­ным. Количество разных слов равномерного кода длины l не пре­восходит т1 —числа разных m-ичных последовательностей длины l.

Определение. Кодировкой сообщений ансамбля В средством кода А именуется отображение огромного количества сообщений Вп в огромное количество кодовых слов.

Предлагается последующий метод равномерного кодировки [1]: огромное количество всех последовательностей сообщений источника Кодирование дискретных источников длиной п делится на два подмножества, одно из которых создается всеми по­следовательностями — блоками длины п, совершенно точно отображаемыми кодовыми словами. Это подмножество именуется обилием одно­значно кодируемых и декодируемых блоков. Другие блоки образуют 2-ое подмножество, которому соответствует одно единственное ко­довое слово. Длина l всех кодовых слов схожа; она определяет­ся Кодирование дискретных источников числом М кодовых слов: l — меньшее целое, удовлетворяющее неравенству ml ≥ М. Процесс кодировки и декодирования заключа­ется в разбиении последовательности сообщений на выходе источника на блоки длиной п и сравнении каждому блоку соответственного кодового слова длины l. Ошибкой процедуры декодирования при всем этом является событие, состоящее в возникновении разносторонне Кодирование дискретных источников кодируемого блока. Количество m-ичных кодовых знаков, приходящихся на од­но сообщение, определяется соотношением l/n ≥ log M/ log m. Число log M/n = R для данных значений М и п именуется скоростью рав­номерного кодировки источника. Скорость R измеряется в двоичных знаках на сообщение. Таким макаром, существо Кодирование дискретных источников равномерного ко­дирования заключается в выборе огромного количества совершенно точно кодируемых n-последовательностей сообщений.

Основная задачка при кодировке равномерными кодами заклю­чается в определении меньшей вероятной скорости кодировки, при которой возможность неверного декодирования может быть сде­лана сколь угодно малой. Меньшая достижимая скорость R является чертой кодируемого источника. Она Кодирование дискретных источников носит заглавие скоро­сти сотворения инфы.

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

Для хоть какого R > Н и случайного положительного δ найдется значение п и код со скоростью R, для которого возможность ошибки не превосходит δ. (Ровная аксиома кодировки источника.)


kogda-bogi-bezhali-s-zemli.html
kogda-chelovek-glupee-muravya-sergej-georgievich-kara-murza-oppoziciya-kak-tenevaya-vlast.html
kogda-chelovek-ochistilsya-ot-karmicheskih-oshibok-na-pervoe-mesto-vihodit-vtoraya-prichina-vibrannaya-cel-zhizni.html