Архиваторы: Избыточности не существует.

Существуют модели источников информации, чем ближе модель к реальному источнику, тем меньшую она даёт избыточность...
Прочитай начало статьи до описания эстиматоров, если осилишь - там нормальная понятийная база Учись учиться самостоятельно Извините за тафтологию

 

Конечно не должны: целые числа это не натуральные, хотя натуральные есть целые

 

На самом деле, ныне используемый термин "Теория информации" является только обозначением направления математики, разработанного Клодом Шенноном в сороковых годах двадцатого века.(c) Wikipedia
Я думаю не дурак писал

Лучше чем в учебниках, которые "врут", тут не скажут, имхо. Хотя неизвестно, что за учебники Вы читали, если кит, пингвин, пианино,сапог и поезд - чёрные, то может и врут

 

избыточность необходима в системах передачи и хранения информации и создаётся искусственно - появляется возможность выявления ошибок, всё заморочено... это отдельная область знаний, на изучение которой не хватит жизни...

... ) я помню одно из первых сообщений в прессе про jpeg (само название формата появилось позже)... многие восприняли это как первоапрельскую шутку - и долго не могли поверить, что картинки можно сжимать в 100 раз почти без потери качества

 

многим хватает 1 семестра
а при необходимости и недели перед экзаменом

 

ага , и "первый "Прогресс" с цифровым управлением затоплен в Тихом океане" -

через 70 лет после создания кибернетики, через 60 лет после создания транзистора, через 50 лет после начала космическиих полётов

вот у америкосов просто: не здал - пшол на х., независимо от того кто твой папа, сколько у него денег и т.д.

 

Это вы не по теме. И PPM здесь тоже ни при чем.

 

ECC (Error Correction Codes) - это нечто иное. Я же предлагаю на простейшей модели - static Huffman (фактически, переименование) - пояснить, что происходит с "избыточностью".

 

Blackbeam

думаю, вы их несколько переоцениваете.

 

gazlan
Избыточность - это когда для кодирования символа\сообщения\файла используется большее количество бит, чем это реально необходимо с учетом статистики реального сообщения.
Например, кодировка русского текста в юникоде (ucs-2 = utf-16) является явно избыточной, т.к. из всего огромного набора символов используется лишь одна кодовая страница, поэтому достаточно указать номер этой кодовой страницы и закодировать текст в 8-битным ANSI. Но для осмысленного текста и 8-битная кодировка является избыточной. Наглядным примером устранения этой избыточности в "железе" является стандартная клавиатура - вместо того, чтобы юзать ~256 кнопок на каждый символ, используется разбивка всего алфавита на поддиапазоны с переключением регистра (верхний\нижний) и раскладки (рус\лат). Аналогичный прием разбивки на поддиапазоны используется и в телеграфных кодах - в итоге на каждый символ из одного поддиапазона используется только 5-6 бит, а при смене поддиапазона вставляется соответствующий управляющий префикс и поскольку эти переключения происходят сравнительно редко, то в среднем получается существенная экономия. Другими словами, если символы в тексте группируются в серии по диапазонам, то кодировка каждого символа 8 битами является избыточной, т.к. можно указывать номер диапазона только в начале каждой серии, а не в каждом символе - явное устранение избыточности. Поскольку алгоритм кодирования однозначный, то принимающая сторона может произвести обратное преобразование, добавив недостающие "избыточные" биты в каждый символ.

Что касается кода Хаффмана, то в нем для устранения избыточности используется кодировка символов разным количеством бит в зависимости от вероятности (частоты) их появления в тексте - часто встречающиеся символы кодируются меньшим числом бит, редко встречающиеся - бОльшим (аналогичный подход используется и в коде\азбуке Морзе).
Говорить о том, что здесь все сводится к "мэппингу" и "словарю из 256 кодов" не совсем корректно, т.к. во-первых, за счет ранжировки символов по вероятности, вообще не встречающиеся символы оказыаются в конце таблицы (дерева) и по сути вообще выпадают из преобразования, т.е. происходит сокращение объема алфавита (длинные комбинации просто отсутствуют). Во-вторых, за счет кодирования часто встречающихся символов меньшим числом бит (начиная с 2-х) средняя длина закодированного сообщения оказывается меньше исходной. Для декодирования такого кода достаточно знать порядок ранжировки символов - она м.б. или предопределена заранее или же передаваться в начале самого сообщения

 

Спасибо за подробное изложение вашего видения "избыточности". Но я предпочел бы ограничиться классическим определением Шеннона - как меры уклонения сообщения от чисто случайного. Иначе мы будем обсуждать различные вещи. Скажем, мультипликатор Stiver (#4 с предыдущей страницы) НЕ изменяет "избыточность", так как нет изменения частотностей.
Юникод, коды Бодо и неиспользуемые символы к делу не относятся - очевидно подразумевается, что сообщение реализует всю мощность заданного алфавита.
Работа Хаффмановского кодера описана вами правильно, но хотелось бы услышать, куда прячется "избыточность" в канале связи.

 

количество информации в сообщении не зависит от способа кодирования сообщения, если способ кодирования не приводит к потерям информации
было сообщение длиной 400 двоичных разрядов с 100битами информации, его перекодировали удалив всю избыточность, осталось 100 двоичных разрядов и те же 100 бит информации
перекодировали еще раз добавив коды проверки ошибок, получили сообщение длиной 800 двоичных разрядов и с теми же 100 битами информации
отправили это сообщение кусками по 4 двоичных разряда в аналоговый канал связи с динамическим диапазоном 60дБ (эквивалентно 20 двоичным разрядам, размер сообщения вырос еще в 5 раз), там остались те же 100 бит информации
на конце приемника то же самое - последовательность преобразований и перекодирований и получаем исходные 400 двоичных разрядов со 100битами информации

 

400 двоичных разрядов это (2^400) бит информации , вам не кажется?
некоторая избыточность имеет место быть, мягко говоря...

 

Blackbeam
ниче не перепутал?

 

1 разряд - 0 или 1 = 2 бита информации

2 разряда ... = 4 бита информации, чего тут путать??

или ЧТО? закодировал 1 бит информации 400 разрядным кодом и это считается 1 бит информации?

поясните кто хорошо ловит мышей, ... если я неправ

 

1 дв.разряд - 0 или 1 - всего 2 значения - log2(2)=1бит
2 дв.разряда - 0 .. 3 - всего 4 значения - log2(4)=2бита
в 400 двоичных разрядах может содержаться не более 400 бит информации
да, если закодировать 1бит информации 400 дв.разрядами там всеравно будет 1 бит информации

 

GoldFinch
Признаться, ничего не понял из вашего поста.
Оставим в стороне путаницу с разрядностью.

Это постулат? Или результат экспериментов?
Если я кодирую 100-страничное сообщение как "План Z", как мне подсчитать количество информации в этой строке и убедиться, что оно не изменилось?
Или я постулирую, что оно не изменилось и всю невязку списываю на метод кодирования и "избыточность"?

 

gazlan
это подтверждается как теоретически так и практически, причем примерно одинаково
количество информации в сообщении в битах - это двоичный логарифм числа всех N вариантов сообщения при условии что все варианты сообщения равновероятны
(если не равновероятны то все тоже доказывается)
если кодирование обратимо, т.е. сообщение потом можно раскодировать, и при этом информация не потеряется
то все эти N вариантов сообщения преобразуются в N кодированных сообщений, при этом количество информации равное log2(N) сохранится
после декодирования N вариантов сообщения мы получим N исходных сообщений

например мы передаем в сообщении один из цветов радуги
у нас 7 вариантов сообщения: "красный","оранжевый",..."фиолетовый"
в сообщении log2(7) ~ 2.807 бита информации
как его не кодируй, словом "...", номером цвета, речью, непосредственно цветом (воспринимаемым визуально) в нем всеравно будет 2.807 бита информации

 

Обратимость не обсуждается. Я спрашивал о другом. Если вам не нравится фраза "План Z", обратимся, например, к числу PI (3.1415926...).
Пусть исходное сообщение - это первая 1000 знаков числа PI, закодированное сообщение - фраза (символьный литерал) "первая 1000 знаков числа PI", декодированное сообщение идентично исходному - первая 1000 знаков числа PI (вычисленная декомпрессором).
От чего мы берем двоичный логарифм?
Если такой метод кодирования кажется вам непривычным, назовите его Static Huffman (формально, это так и есть - really!)
В качестве бонуса, поясните, plz, где здесь информация и где - избыточность.

 

gazlan
число Пи известно, единственная информация о которой тут можно говорить, это число его знаков, вы собираетесь ЭТО передать?
другое дело если речь идет о передаче числа из 1000 знаков, тогда все просто, как и в посте выше

когда передается заранее известное сообщение, говорится что передается НОЛЬ информации
поэтому если известно что передается число ПИ то информации в любом сообщении которое его передает 0, а избыточность 100%, потомучто но стороне приема число Пи известно

когда говорят о передаче сообщений, не говорят о конкретном сообщении.