что такое избыточность кода

Кодирование информации и избыточность кода

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

Чем выше избыточность кода, тем больше вероятность безошибочной передачи информации, но тем больший объём требуется для её хранения и большая пропускная способность канала передачи. Естественные человеческие языки характеризуются очень высокой степенью избыточности, также велика избыточность генома высших организмов, хранящегося в молекулах ДНК.

Величина \(H /Q\) называется экономичностью кода. Для оптимального кода \(H /Q=1\) а избыточность отсутствует, то есть \(E = 0\).

Процесс уменьшения избыточности кодирования называется сжатием информации и применяется для понижения объёма памяти, требуемой для хранения информации. Для сжатия информации, хранящейся в памяти, используются– архиваторы и упаковщики.

Пример: определить энтропию информации, содержащейся в сообщении «ученье − свет, а не ученье – тьма» и избыточность кода. Каждый символ в сообщении кодируется 1 байтом (8 бит).
Решение: Подсчитаем количество символов в сообщении, для простоты игнорируя пробелы: N=26. Найдём частоту повторения каждого символа (вероятность в сообщении), составив следующую таблицу, приведенную на скрине слева.

Удельная энтропия (энтропия одного символа в сообщении) в битах на символ, равна \[\tilde H = 5 \cdot \frac<1><<13>><\log _2>13 + \frac<3><<13>><\log _2>\frac<<13>> <3>+ 2 \cdot \frac<3><<26>><\log _2>\frac<<26>> <3>+ 4 \cdot \frac<1><<26>><\log _2>26 \approx \] \[ \approx \frac<5><<13>> \cdot 3.7004 + \frac<3><<13>> \cdot 2.1155 + \frac<6><<26>> \cdot 3.1155 + \frac<4><<26>> \cdot 4.7004 \approx 3.3535\] Полная энтропия сообщения \(H = 3.3535 \cdot 26 = 87.19\) бит. Количество бит, необходимое для кодирования каждого символа одним байтом, составляет \(Q = 208\;\) бит.
Избыточность кода \(E=1-87.19/208=0.58=58%\).

Источник

2.2. Избыточность кодов.

Понятие избыточности означает, что фактическая энтропия кода или сообщения (Н) меньше, чем максимально возможная энтропия (H_max), т. е. число символов в сообщении или элементов в символе кода больше, чем это требовалось бы при полном их использовании.

Понятие избыточности легко пояснить следующим примером.

Выделение полезного сигнала на уровне помех — одна из основных проблем передачи информации. Одним из путей повышения надёжности передачи сообщений может быть передача дополнительных символов, т.е. повышение избыточности сообщений.

Действительно, по теореме Котельникова (§ 1.7), непрерывное сообщение (сигнал) можно передать последовательностью мгновенных отсчетов его значений с промежутками между ними :

где f_max – верхняя граничная частота в спектре сигнала.

При наличии помех промежутки между отсчетами (Δt_n) необходимо уменьшать, т.е.

В этом случае мы увеличиваем число отсчетов и, следовательно, увеличиваем избыточность сообщения и тем самым повышаем его помехозащищенность.

Пусть сообщение из n символов содержит количество информации I. Если сообщение обладает избыточностью, то его (при отсутствии шума) можно передать меньшим числом символов n₀ (n₀ n .

Источник

Избыточное кодирование, код Хэмминга

Избыточное кодирование (англ. redundant encoding) — вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.

Содержание

Код, определяющий одну ошибку [ править ]

Кодирование Хэмминга [ править ]

По аналогичному принципу можно закодировать любое число бит. Пусть мы имеем исходную строку длиной в [math]2^k[/math] бит. Для получения её кода добавим к ней [math]k[/math] пар бит по следующему принципу:

Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит — [math] \mathrm X \mathrm O \mathrm R[/math] всех битов строки.

Определение и устранение ошибок в общем случае [ править ]

Пусть [math]\Sigma[/math] — исходный алфавит, [math]C: \Sigma \to B^m[/math] — кодирование, [math]B=(0,1)[/math]

[math]d: B^m \times B^m \to \mathbb[/math] — расстояние Хэмминга между двумя кодами.
Определим [math]d_0 = \min[/math] [math]

Тогда легко понять, что код, полученный преобразованием [math]C[/math] может исправлять [math]

Источник

Что такое избыточность кода

3. Избыточность

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

Поскольку энтропия является одновременно и количеством информации, то можно выразить избыточность сообщения и следующим способом:

Если уж приводить для иллюстрации какой-то популярный пример избыточности сообщения, то лучше всего указать на разговорный и письменный язык. Избыточность в языке состоит в растянутости и повторимости, обеспечивающих помехоустойчивость речи, возможность легкого понимания друг друга. Так, например, при разговоре в шумном зале или при обсуждении сложного вопроса речь требует большей избыточности. При малой избыточности, наоборот, концентрированность информации велика, велика и экономичность речи, то есть каждая фраза такой речи содержит что-то новое, что-то неожиданное, большую степень информации; однако при этом даже небольшая помеха приводит к большой потере информации. Простейшим видом избыточности является повторение. Более сложным видом ее является, например, применение так называемых контрольных кодов в передаче сообщений, о которых мы уже упоминали выше. Препятствием для концентрации информации как раз и является повышенный результат действия помех при пониженной избыточности. Кроме того, проблема избыточности сообщения связана также с проблемой времени. Степень отличительности в передаваемом сообщении зависит от времени. Можно понизить помехи и повысить отличительность при передаче сообщения тем, что мы растянем передачу на больший интервал времени, так что, собственно говоря, понизится пропускная способность передающего канала. Речь может идти о замедлении передачи или об использовании повторений, но и то и другое связано с избыточностью. Оба эти процесса облегчают понимание сообщения, прием его адресатом, что известно из процесса обучения; учебный материал лучше усваивается тогда, когда изложение ведется либо достаточно медленно, либо если трудные места изучаемого повторяются в различном виде.

Избыточность сообщения можно сводить к нулю при пользовании оптимальным кодом. При неравномерном распределении вероятностей символов и при наличии их внутренней вероятностной связи (корреляции) уменьшается относительная энтропия и возрастает избыточность сообщения. При создании текста мы делаем меньше выборов, чем число букв в тексте, так как мы действуем в рамках грамматических правил образования слов и предложений. Только примерно от 1 /₄ и до 1 /₃ числа букв мы можем выбирать произвольно: мы можем выбрать данные буквы или не выбрать их. Следовательно, при оптимальном коде мы могли бы выражаться втрое или вчетверо короче. Любая комбинация букв здесь создавала бы слово, полное смысла, так как все буквы и комбинации их встречались бы одинаково часто и каждая таблица букв могла бы годиться для кроссворда. Однако при обычном общении людей избыточность всегда имеет место, она имеется в каждом разговоре, в газетном языке и в научной литературе. Каждый национальный язык имеет значительную степень избыточности. Как уже было сказано, избыточность имеет не только отрицательные, но и положительные, полезные стороны. Она обеспечивает возможность понять друг друга, возможность исправить ошибки, получившиеся при передаче, тогда как при нулевой избыточности ошибки при передаче сильно искажали бы конечное сообщение.

Избыточность можно снизить путем перекодирования, путем изменения статистической структуры сигнала. Так, например, Нейдхардт 1 указывает, что в телевидении можно снизить избыточность путем уменьшения скорости развертывания передаваемого образа в тех местах, где сконцентрировано наибольшее информационное содержание, и путем ускорения развертывания в тех частях, где имеются свободные места и где можно эти промежутки интегрировать во времени. Если переходные вероятности между элементами одинаковы, нет взаимозависимости символов, то корреляция между ними нулевая. Если же, наоборот, они различны, то это дает экономию передачи и уменьшает избыточность. При передаче информацию несет только часть сигналов, остальные сигналы избыточны; в полезной части сообщения одна и та же информация может содержаться несколько раз, что дает возможность дальнейшего сжатия сообщения. Нейдхардт различает холостую (бесполезную) и полезную избыточность. Из неизбыточного сообщения нельзя изъять ни один знак, не изменяя этим его смысл. Если мы хотим установить избыточность сообщения, то мы убираем из этого сообщения знаки до тех пор, пока это не лишает сообщение понятности, то есть пока оно не теряет своего смысла. В противоположность холостой избыточности полезная избыточность обеспечивает или же и повышает верность передачи сообщения, и, наоборот, появление холостой избыточности не повышает ясности сообщения.

1 ( См. Р. Neidehardt, Einf?hrung in die Informationstheorie, Berlin, 1958.)

1 ( W. Meyer-Eppler, Informationstheorie, «Naturwiss.», № 15, 1952, S. 341.)

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

можно заменить буквами

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

Другой пример с более высокой и более низкой избыточностью в коде приводит Черри 1 :

1 ( C. Cherry, On Human Communication, New York, 1957, p. 186.)

Если бы мы закодировали буквы А, В, С и D только с помощью двух бинарных знаков, например, как

то этот код получился бы очень экономичным, имеющим малую степень избыточности. Однако в этом случае даже небольшая помеха привела бы к тому, что сообщение стало бы слишком неразборчивым. Если же мы закодируем эти буквы с помощью четырех бинарных знаков, например, так

то код станет более избыточным, но он будет иметь большую помехоустойчивость. Если, например, помеха коснется одного знака (он исказится), то эту помеху можно обнаружить (но, конечно, не сразу же исправить ее). Так, например, при одной помехе код для A может измениться в 1110, 1101, 1011 (вместо 1111) или же 0111, то есть во всех этих случаях код А нельзя будет спутать с группой кодовых символов для В, С или D, как это может иметь место в случае двухзначного кода при одной помехе (когда получится 0 вместо 1 или 1 вместо 0). Конечно, например, группа 1110 может при одной ошибке получиться при искажении не только кода буквы A, но и кодовых букв В, С или D. Еще большая помехоустойчивость может быть получена при еще большем усложнении кода, при придании ему еще большей избыточности.

Эти пять вопросов можно составить следующим образом:

2. Червовая ли это карта (или бубновая)?

3. Фигура ли это? (При ответе «нет» это значит, что карта цифровая.)

4. Это карта из высшей половины (фигур или цифровых карт)?

5. Это четная карта из данной половины?

После пяти ответов на эти вопросы мы получим ответ, какая именно карта вытянута.

1 ( H. Zemanek, Ungewohnte Zahlen aus der Informations-theory, «Radiotechnik», № 6, 1954, S. 188.)

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

В настоящее время, например, проблемой, имеющей значение для дальнейшего непрерывного развития научного познания, становится чрезмерное возрастание числа научных книг, что связано с большой степенью избыточности в научных книгах, то есть с тем, что в различных книгах идеи повторяются и читатель теряет много времени, так как он вынужден читать в изучаемых книгах такое, что он и без того знает и что не дает ему новой информации. Причем потеря времени на чтение уже знакомого текста непропорциональна выигрышу от закрепления в памяти информации, полученной уже ранее. Поэтому было бы желательно провести какую-то унификацию, централизацию, концентрацию и контроль книжного фонда, чтобы можно было обеспечить лучший учет, обзор научной литературы и снизить избыточность. Как остроумно указывает польский писатель Станислав Лем в своей книге «Магелланово облако», при нынешнем росте книжной продукции дело может дойти до того, что через какое-то время каждому второму человеку в мире придется стать библиотекарем и земной шар превратится в гигантскую библиотеку. Поэтому необходимо найти способы улучшения хранения и переработки научной информации путем внедрения в библиотечное дело электронных вычислительных машин. Введение информации в эти машины было бы значительно более экономичным, чем в книги, и это дало бы значительное снижение избыточности в научных книгах. С помощью этих машин можно было бы также экономично обрабатывать информацию таким образом, что будет выявляться гомоморфизм в научных сообщениях, а это приведет к снижению избыточности, ибо приведет к исключению того, что во многих научных работах является одинаковым и повторяющимся. Одновременно это объединяло бы то подобное, что имеется в работах различных дисциплин.

На первый взгляд существует некоторая ограниченность в повышении информации и в снижении избыточности в нашем познании. Нулевая избыточность могла бы быть достигнута тогда, когда эффективное содержание сообщения было таким же, как содержание, которое может быть нами получено при оптимальном использовании канала, что возможно было бы, например, при полном отсутствии помех. Помехи в передаче сообщений можно уменьшить применением избыточности, путем использования более длительного времени для передачи наряду с некоторыми другими способами борьбы с помехами. Между скоростью передачи и помехами должна, следовательно, существовать определенная зависимость. Нельзя, например, полностью устранить разрыв во времени между входом и выходом при передаче сообщения. Самый быстрый процесс передачи информации может ведь происходить только со скоростью света (если иметь в виду только физическую скорость передачи сообщения; в теории информации скорость передачи сообщения измеряется числом переданных двоичных единиц информации в секунду).

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

Источник

Избыточность кодов.

Понятие избыточности означает, что фактическая энтропия кода или сообщения (Н) меньше, чем максимально возможная энтропия (H_max), т. е. число символов в сообщении или элементов в символе кода больше, чем это требовалось бы при полном их использовании.

Понятие избыточности легко пояснить следующим примером.

Выделение полезного сигнала на уровне помех — одна из основных проблем передачи информации. Одним из путей повышения надёжности передачи сообщений может быть передача дополнительных символов, т.е. повышение избыточности сообщений.

Действительно, по теореме Котельникова (§ 1.7), непрерывное сообщение (сигнал) можно передать последовательностью мгновенных отсчетов его значений с промежутками между ними :

где f_max – верхняя граничная частота в спектре сигнала.

При наличии помех промежутки между отсчетами (Δt_n) необходимо уменьшать, т.е.

В этом случае мы увеличиваем число отсчетов и, следовательно, увеличиваем избыточность сообщения и тем самым повышаем его помехозащищенность.

Пусть сообщение из n символов содержит количество информации I. Если сообщение обладает избыточностью, то его (при отсутствии шума) можно передать меньшим числом символов n₀ (n₀

Дата добавления: 2017-05-18 ; просмотров: 4248 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник