2.2. Избыточность кодов.
Понятие избыточности означает, что фактическая энтропия кода или сообщения (Н) меньше, чем максимально возможная энтропия (Hmax), т. е. число символов в сообщении или элементов в символе кода больше, чем это требовалось бы при полном их использовании.
Понятие избыточности легко пояснить следующим примером.
Выделение полезного сигнала на уровне помех — одна из основных проблем передачи информации. Одним из путей повышения надёжности передачи сообщений может быть передача дополнительных символов, т.е. повышение избыточности сообщений.
Действительно, по теореме Котельникова (§ 1.7), непрерывное сообщение (сигнал) можно передать последовательностью мгновенных отсчетов его значений с промежутками между ними :
где fmax – верхняя граничная частота в спектре сигнала.
При наличии помех промежутки между отсчетами (Δtn) необходимо уменьшать, т.е.
В этом случае мы увеличиваем число отсчетов и, следовательно, увеличиваем избыточность сообщения и тем самым повышаем его помехозащищенность.
Пусть сообщение из n символов содержит количество информации I. Если сообщение обладает избыточностью, то его (при отсутствии шума) можно передать меньшим числом символов n0 (n0 < n). При этом, количества информации (I1 и I1max), приходящиеся на один символ сообщения, будут связаны соотношением:
и, следовательно,
За меру избыточности принимается величина R:
Таким образом, избыточность — это свойство, характеризующее возможность представления тех же сообщений в более экономной форме.
При кодировании избыточных сообщений возникает определенная исходная избыточность кодов. Наличие исходной избыточности уменьшает пропускную способность каналов и увеличивает формат сообщений. Вместе с тем в процессе передачи информации избыточность сообщений и кодов является средством, полезным для борьбы с внешними возмущающими воздействиями и помехами.
По наличию избыточности коды также делятся на избыточные и неизбыточные. Для неизбыточных кодов характерно то, что они позволяют просто определить различные символы сообщения. Переход от неизбыточного кода к избыточному осуществляется путем добавления позиций в кодовых символах, которые можно получить либо путем различных логических операций, выполняемых над основными информационными позициями, либо путем использования алгоритмов, связывающих неизбыточный и избыточный коды. Например, если есть символы сообщения А1; А2; А3; А4, то их можно закодировать в двоичном неизбыточном коде:
Для получения избыточного кода можно ввести еще одну позицию, значение которой будет определяться как сумма значений предшествующих символов по модулю два:
Особенностью такого кода является то, что он позволяет обнаружить любую единичную ошибку (ошибку в одной из позиций кода), выявившуюся в процессе передачи кода.
Эффективное кодирование. Алгоритм Шеннона-Фено.
Эффективное кодирование равновероятных символов сообщений.
Эффективное кодирование используется в каналах без шума, т.е. в таких каналах, где помехи отсутствуют, либо ими можно пренебречь. Основной задачей кодирования в таком канале является обеспечение максимальной скорости передачи информации, близкой к пропускной способности канала передачи (§3.4).
В случае, если все символы алфавита кодируемого сообщения независимы и их появление равновероятно, построение оптимального эффективного кода не представляет трудностей. Действительно, пусть Н(х) — энтропия исходного сообщения. Будем считать, что символы сообщения (хi) равновероятны и объем алфавита исходного источника сообщений равен m. Следовательно, вероятность появления любого i-го символа данного сообщения (P(хi)) будет одинакова, т.е.
а энтропия сообщения равна (Н(х)):
Если для кодирования используется числовой код по основанию k (объем алфавита элементов кодовых символов равен k), то энтропия элементов кодовых символов (Н1), при условии, что элементы символов кода появляются равновероятно и взаимнонезависимо, определится из соотношения:
Тогда длина эффективного равномерного кода, т.е. число элементов в кодовом символе (lэфф.), может быть найдена из соотношения:
где m = k n .
Эффективное кодирование неравновероятных символов сообщений
В случае, если символы кодируемого сообщения неравновероятны, в общем виде правило получения оптимального эффективного кода неизвестно. Однако из общих соображений можно представить принципы его построения.
Очевидно, что эффективное кодирование будет оптимальным, если неравномерное распределение вероятностей появления символов алфавита источника сообщений с помощью определенным образом выбранного кода переводят в равновероятное распределение вероятностей появления независимых элементов кодовых символов. В этом случае среднее количество информации, приходящееся на один элемент символа кода, будет максимальным. Для определения вида кода, удовлетворяющего этому требованию, можно рассмотреть «функцию стоимости» (цены передачи символов сообщения) в виде:
где P(xi) — вероятность появления i-го символа алфавита исходного кодируемого сообщения;
m — объем алфавита;
Wi — стоимость передачи i-го символа алфавита, которая пропорциональна длине кодового слова.
Эффективный код должен минимизировать функцию Q. Если передача всех элементов символов кода имеет одинаковую стоимость, то стоимость кодового символа будет пропорциональна длине соответствующего кодового символа. Следовательно, в общем случае (при неравновероятных символах исходного сообщения) код должен быть неравномерным, поэтому построение эффективного кода должно основываться на следующих принципах:
Длина кодового символа (ni) должна быть обратно пропорциональна вероятности появления соответствующего символа исходного кодируемого сообщения (xi);
Начало более длинного кодового символа не должно совпадать с началом более короткого (для возможности разделения кодовых символов без применения разделительных знаков);
В длинной последовательности элементы символов кода должны быть независимы и равновероятны.
Теоретическое обоснование возможности эффективного кодирования передаваемых по каналу сообщений обеспечивает теорема, доказанная К. Шенноном и которая носит название первая теорема Шеннона или основная теорема Шеннона о кодировании для каналов без помех. Эта теорема гласит, что если источник сообщений имеет энтропию Н [бит/символ], а канал обладает пропускной способностью С [бит/сек] (пропускная способность характеризует максимально возможное значение скорости передачи информации), то всегда можно найти способ кодирования, который обеспечит передачу символов сообщения по каналу со средней скоростью
где ε — сколь угодно малая величина.
Обратное утверждение говорит, что передача символов сообщения по каналу со средней скоростью Vср. > Н невозможна и, следовательно,
Эта теорема часто приводится в иной формулировке: сообщения источника сообщений с энтропией Н всегда можно закодировать последовательностями элементов кодовых символов с объемом алфавита k так, что среднее число элементов символов кода на один символ кодируемого сообщения (l ср. ) будет сколь угодно близко к величине H / log2 k, но не менее ее.
Не вдаваясь в доказательство этой теоремы, отметим, что эта теорема показывает возможность наилучшего эффективного кодирования, при котором обеспечивается равновероятное и независимое поступление элементов символов кода, а следовательно, и максимальное количество переносимой каждым из них информации, равное log2 k (бит/элемент) . К сожалению, теорема не указывает конкретного способа эффективного кодирования, она лишь говорит о том, что при выборе каждого элемента кодового символа необходимо чтобы он нес максимальное количество информации, а, следовательно, все элементы символов кода должны появляться с равными вероятностями и взаимнонезависимо.
Исходя из изложенных принципов, разработаны ряд алгоритмов эффективного кодирования как для взаимнонезависимых символов сообщения, так и для взаимнозависимых. Суть их состоит в том, что они сокращают среднюю длину кодовых символов путем присвоения кодовых символов минимальной длины символам исходного сообщения, которые встречаются наиболее часто.
Алгоритм Шеннона-Фено. Суть этого алгоритма, при использовании двоичного кода (объем алфавита элементов символов кода равен 2), заключается в следующем.
Все символы алфавита источника сообщений ранжируют, т. е. располагают в порядке убывания вероятностей их появления. Затем символы алфавита делятся на две группы приблизительно равной суммарной вероятности их появления. Все символы первой группы получают «0» в качестве первого элемента кодового символа, а все символы второй группы — «1». Далее группы делятся на подгруппы, по тому же правилу примерно равных суммарных вероятностей, и в каждой подгруппе присваивается вторая позиция кодовых символов. Процесс повторяется до закодирования всех символов алфавита кодируемого источника сообщений. В кодовый символ, соответствующий последней группе, добавляется в качестве последнего элемента «0» для того, чтобы начальный элемент символов кода не совпадал с конечным, что позволяет исключить разделительные элементы между символами кода.
Таблица 2.2 иллюстрирует процесс построения кода Шеннона–Фено на примере источника сообщений, алфавит которого состоит из восьми символов.
Кодирование информации и избыточность кода
Любое сообщение, может быть представлено в различной форме, то есть закодировано различными способами. Разные способы кодирования неравноценны по занимаемому ими количеству информации. Оптимальным кодом будет тот, при использовании которого среднее значение энтропии, приходящееся на один символ, равно энтропии источника информации.
В большинстве случаев используемые системы кодирования обладают избыточностью, то есть требуют для записи большее количество информации, чем оно содержится в кодируемом сообщении. Избыточность определяется формулой \[E = 1 — \frac\] где \(H\) — энтропия сообщения, \(Q\)- среднее количество информации, приходящееся на один символ кодированного сообщения.
Чем выше избыточность кода, тем больше вероятность безошибочной передачи информации, но тем больший объём требуется для её хранения и большая пропускная способность канала передачи. Естественные человеческие языки характеризуются очень высокой степенью избыточности, также велика избыточность генома высших организмов, хранящегося в молекулах ДНК.
Величина \(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%\).
Электронные средства сбора, обработки и отображения информации
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала.
Построение такого кода достигается ценой введения избыточности. То есть, применяя для передачи информации код, у которого используются не все возможные комбинации, а только некоторые из них, можно повысить помехоустойчивость приема. Такие коды называют избыточными или корректирующими. Корректирующие свойства избыточных кодов зависят от правил построения этих кодов и параметров кода (длительности символов, числа разрядов, избыточности и др.).
В настоящее время наибольшее внимание уделяется двоичным равномерным корректирующим кодам. Они обладают хорошими корректирующими свойствами и их реализация сравнительно проста.
Наиболее часто применяются блоковые коды. При использовании блоковых кодов цифровая информация передается в виде отдельных кодовых комбинаций (блоков) равной длины. Кодирование и декодирование каждого блока осуществляется независимо друг от друга, то есть каждой букве сообщения соответствует блок из п символов.
Блоковый код называется равномерным, если п (значность) остается одинаковой для всех букв сообщения.
Различают разделимые и неразделимые блоковые коды.
При кодировании разделимыми кодами кодовые операции состоят из двух разделяющихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода занимают одни и те же позиции.
При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.
Непрерывными называются такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. Непрерывные коды также могут быть разделимыми и неразделимыми.
Общие принципы использования избыточности
Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На ввод кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из п двоичных символов, причем n>k. Всего может быть различных входных последовательностей и различных выходных последовательностей. Из общего числа выходных последовательностей только последовательностей соответствуют входным. Будем называть их разрешенными кодовыми комбинациями. Остальные ( — ) возможных выходных последовательностей для передачи не используются. Их будем называть запрещенными кодовыми комбинациями.
Искажение информации в процессе передачи сводится к тому, что некоторые из передаточных символов заменяются другими — неверными. Каждая из разрешенных комбинаций в результате действия помех может трансформироваться в любую другую. Всего может быть · возможных случаев. В это число входит:
— случаев безошибочной передачи;
— ·(-1) случаев перевода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;
— ·( — ) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.
Часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи соответствует:
Рассмотрим, например, обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (п=k+1). Общее число выходных последовательностей составит , то есть вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого четного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть обнаруженных ошибок составляет:
Пример кодирующего устройства с проверкой на четность показан на рис.
Основные параметры корректирующих кодов
Основными параметрами, характеризующими корректирующие свойства кодов являются избыточность кода, кодовое расстояние, число обнаруживаемых или исправленных ошибок.
Рассмотрим суть этих параметров.
Избыточность корректирующего кода может быть абсолютной и относительной. Под абсолютной избыточностью понимают число вводимых дополнительных разрядов
Относительной избыточностью корректирующего кода называют величину
Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. Ее еще называют относительной скоростью передачи информации.
Если производительность источника равна Н символов в секунду, то скорость передачи после кодирования этой информации будет равна
поскольку в последовательности из п символов только k информационных.
Рис. 2.5 — Кодер с контролем на четность
Если число ошибок, которое нужно обнаружить или исправить, значительно, необходимо иметь код с большим числом проверочных символов. Скорость передачи информации при этом будет уменьшена, так как появляется временная задержка информации. Она тем больше, чем сложнее кодирование.
Кодовое расстояние характеризует cтепень различия любых двух кодовых комбинаций. Оно выражается числом символов, которыми комбинации отличаются одна от другой.
Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.
Кодовое расстояние может быть различным. Так, в первичном натуральном безызбыточном коде это расстояние для различных комбинаций может различаться от единицы до п, равной значности кода.
Число обнаруживаемых ошибок определяется минимальным расстоянием между кодовыми комбинациями. Это расстояние называется хэмминговым.
В безызбыточном коде все комбинации являются разрешенными, =1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.
Теорема. Чтобы код обладал свойствами обнаруживать одиночные ошибки, необходимо ввести избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух.
Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как =1. Если =2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.
Пусть подмножество разрешенных комбинаций образовано по принципу четности числа единиц. Тогда подмножества разрешенных и запрещенных комбинаций будут такие:
000, 011, 101, 110 — разрешенные комбинации;
001, 010, 100, 111 — запрещенные комбинации.
Очевидно, что искажение помехой одного разряда (одиночная ошибка) приводит к переходу комбинации в подмножество запрещенных комбинаций. То есть этот код обнаруживает все одиночные ошибки.
В общем случае при необходимости обнаруживать ошибки кратности — минимальное хэммингово расстояние должно быть, по крайней мере, на единицу больше , то есть
В этом случае никакая ошибка кратности не в состоянии перевести одну разрешенную комбинацию в другую.
Ошибки можно не только обнаруживать, но и исправлять.
Теорема. Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние должно быть не менее трех.
Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.
Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:
В общем случае исправляемые ошибки кратности связаны с кодовым расстоянием соотношением
Для ориентировочного определения необходимой избыточности кода при заданном кодовом расстоянии d можно воспользоваться верхней граничной оценкой для r = n — k, называемой оценкой Хэмминга:
где — сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).
Если, например, п=7, =1, то из (2.1)
=3, n — k (1+7)=3 .
Нужно отметить, что каждый конкретный корректирующий код не гарантирует исправления любой комбинации ошибок. Коды предназначены для исправления комбинаций ошибок, наиболее вероятных для заданного канала связи.
Групповой код с проверкой на четность
Недостатком кода с четным числом единиц является необнаружение четных групповых ошибок. Этого недостатка лишены коды с проверкой на четность, где комбинации разбиваются на части, из них формируется матрица, состоящая из некоторого числа строк и столбцов:
Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы . Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце:
При таком кодировании четные групповые ошибки обнаруживаются. Не обнаруживаются лишь такие ошибки, при которых искажено четное число символов в столбце.
Можно повысить обнаруживающую способность кода путем одновременной проверки на четность по столбцам и строкам или столбцам и диагоналям (поперечная и диагональная проверка).
Если проверка проводится по строкам и столбцам, то код называется матричным.
Проверочные символы располагаются следующим образом:
В этом случае не обнаруживаются только ошибки четной кратности с кратностью 4, 8, 16 и т.д., при которых происходит искажение символов с попарно одинаковыми индексами строк столбцов. Наименьшая избыточность кода получается в том случае, когда образуемая матрица является квадратной.
Недостатком такого кода является необходимость внесения задержки в передачу информации на время, необходимое для формирования матрицы.
Матричный код позволяет исправлять одиночные ошибки. Ошибочный элемент находится на пересечении строки и столбца, в которых имеется нарушение четности.
Коды с постоянным весом
Весом называется число единиц, содержащихся в кодовых комбинациях.
Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом. Коды с постоянным весом относятся к классу блочных неразделимых кодов, поскольку здесь невозможно выделить информационные и проверочные символы. Наибольшее применение получили коды «3 из 7», «3 из 8», хотя возможны другие варианты. Первая цифра указывает на вес кода, вторая — на общее число символов в комбинации.
Разрешенными комбинациями кода «3 из 7» являются такие, которые содержат три единицы независимо от их места в комбинации, например 1110000 или 1010100 и т.д. Обнаружение ошибок сводится к определению их веса. Если вес отличается от заданного, то считается, что произошла ошибка. Код обнаруживает веса ошибок нечетной кратности и части ошибок четной кратности. Не обнаруживаются ошибки, при которых несколько единиц превращается в нули и столько же нулей — в единицы (ошибки смещения), так как при этом вес кода не изменяется.
В коде «3 из 7» возможных комбинаций сто двадцать восемь (=128), а разрешенных кода только тридцать пять. Относительная избыточность отн = 0,28.
Схема устройства определения веса комбинаций кода «3 из 7» приведена на рис. 2.6.
Рис. 2.6 — Схема определения веса комбинаций кода «3 из 7»
Циклические коды
Циклические коды характеризуются тем, что при циклической перестановке всех символов кодовой комбинации данного кода образуется другая кодовая комбинация этого же кода.
— комбинация циклического кода;
— также комбинация циклического кода.
При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п — 1), п — длина кодовой комбинации.
Например, комбинация 1001111 (п=7) будет представлена многочленом
При таком представлении действия над кодовыми комбинациями сводятся к действиям над многочленами. Эти действия производятся в соответствии с обычной алгебры, за исключением того, что приведение подобных членов осуществляется по модулю 2.
Обнаружение ошибок при помощи циклического кода обеспечивается тем, что в качестве разрешенных комбинаций выбираются такие, которые делятся без остатка на некоторый заранее выбранный полином G(x). Если принятая комбинация содержит искаженные символы, то деление на полином G(x) осуществляется с остатком. При этом формируется сигнал, свидетельствующий об ошибке. Полином G(x) называется образующим.
Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:
- если старшая степень произведения не превышает (п — 1), то полученный полином будет представлять кодовую комбинацию циклического кода;
- если старшая степень произведения больше или равна п, то полином произведения делится на заранее выбранный полином степени п и результатом умножения считается полученный остаток от деления.
Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже п.
Часто в качестве полинома, на который осуществляется деление, берется полином G(x)=+1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.
Большим преимуществом циклических кодов является простота построения кодирующих и декодирующих устройств, которые по своей структуре представляют регистры сдвига с обратными связями.
Число разрядов регистра выбирается равным степени образующего полинома.
Обратная связь осуществляется с выхода регистра на некоторые разряды через сумматоры, число которых выбирается на единицу меньше количества ненулевых членов образующего полинома. Сумматоры устанавливаются на входах тех разрядов регистра, которым соответствуют ненулевые члены образующего полинома.
На рис. 2.7 приведена схема кодирующего регистра для преобразования четырехразрядной комбинации в семиразрядную.
Рис. 2.7 — Схема кодирующего регистра
В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.
Свойства циклического кода:
1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;
2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;
3) циклический код с образующим полиномом G(x) степени r = n — k обнаруживает все групповые ошибки длительностью в r символов.
knigechka
Сайт содержит тексты редких методических пособий, лабораторных и контрольных работ. Вообщем, то что трудно найти в сети но очень нужно для подготовки к экзаменам, в частности на заочной форме обучения.
ОПРЕДЕЛЕНИЕ ИЗБЫТОЧНОСТИ СООБЩЕНИЙ. ОПТМАЛЬНОЕ КОДИРОВАНИЕ.
Если энтропия источника сообщений не равна максимальной энтропии для алфавита с данным количеством качественных признаков (имеются в виду качественные признаки алфавита, при помощи которых составляется сообщения), то это прежде всего означает, что сообщения данного источника могли бы нести большее количество информации.
Абсолютная недогруженность на символ сообщений такого источника
Для определения количества «лишней» информации, которая заложена в структуре алфавита либо в природе кода, вводится понятие избыточности. Избыточность, с которой мы имеем дело в теории информации, не зависит от содержания сообщения и обычно заранее известна из статистических данных1. Информационная избыточность показывает относительную недогруженность на символ алфавита и является безразмерной величиной:
где коэффициент сжатия (относительная энтропия).
Н и Нмакс берутся относительно одного и того же алфавита.
Кроме общего понятия избыточности существует частные виды избыточности Избыточность, обусловленная неравновероятным распределением символов в
Избыточность, вызванная статистической связью между символами сообщения,
Полная информационная избыточность
Избыточность, которая заложена в природе данного кода, получается в результате неравномерного распределения в сообщениях качественных признаков этого кода и не может быть задана одной цифрой на основании статистических испытаний.
Так, при передаче десятичных цифр двоичным кодом максимально загруженными бывают только те символы вторичного алфавита которые передают значения, являющиеся целочисленными степенями двойки. В остальных случаях тем же количеством символов может быть передано большее количество цифр (сообщений). Например, тремя двоичными разрядами мы можем передать и цифру 5, и цифру 8, т. е. На передачу пяти сообщений тратится столько же символов сколько тратится и на восемь сообщений.
Фактически для передачи сообщения достаточно иметь длину кодовой комбинации
где N – общее количество передаваемых сообщений.
L можно представить и как ,
где m1 и m2 – соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для 5 в двоичном коде можно записать дв. символа.
Однако эту цифру необходимо округлить до ближайшего целого числа, так как длина кода не может быть выражена дробным числом. Округление, естественно, производится в большую сторону.
В общем случае избыточность от округления ,
где , k – округлённое до ближайшего целого числа значение . Для нашего примера .
Таким образом, избыточность может быть заложена как в первичном алфавите, так и в природе кода, составленного во вторичном алфавите. Например при передаче русских текстов в двоичном неравномерном коде избыточность будет как за счет неравномерной статистики появления букв алфавита в текстах, так и за счет избыточности, заложенной в двоичном коде, суть которой заключается в том, что в двоичном коде вероятность появления 0 больше вероятности появления 1 (а мы уже знаем, что максимальная энтропия, а следовательно
максимальная нагрузка на символ может быть лишь при равномерном появлении символов). Так, в трёхзначном коде (всего комбинаций 8) в первых пяти общее число нулей в два раза больше числа 1, для первых 11 комбинаций четырёхзначного двоичного кода соотношение нулей и единиц – 27 к 17, но уже в 1,58 раза больше…
Если взять критические точки, а для двоичного кода этими точками будут цифры, стоящие после цифр, являющихся целой степенью двух (именно при целой степени двух сравнивается число нулей и единиц в двоичных кодах), можно убедиться, что избыточность, вызванная неравной вероятностью появления 0 и 1 в двоичном безызбыточном коде, будет уменьшаться по мере увеличения значности, т. е. Длины кода (см. задачу 5.23).
Избыточность – не всегда нежелательное явление. Для повышения помехоустойчивости кодов избыточность необходима и её вводят искусственно в виде добавочных nк символов (см. тему 6). Если в коде всего n разрядов и nн из них несут информационную нагрузку, то nк= n— nн характеризует абсолютную корректирующую избыточность, а величина характеризирует относительную корректирующую избыточность.
Информационная избыточность – обычно явление естественное, заложена она в первичном алфавите. Корректирующая избыточность – явление искусственное, заложена она в кодах, представленных во вторичном алфавите.
Наиболее эффективным способом уменьшения избыточности сообщения является построение оптимального кодов.
Оптимальные коды 1- коды с практически нулевой избыточностью. Оптимальные коды имеют минимальную среднюю длину кодовых слов – L. Верхняя и нижняя границы L определяются из неравенства
где H – энтропия первичного алфавита, m – число качественных признаков вторичного алфавита.
В случае поблочного кодирования, где каждый из блоков состоит им M независимых букв a1, a2, …, aм, минимальная средняя длина кодового блока лежит в пределах
Общее выражение среднего числа элементарных символов в букву сообщения при блочном кодировании
С точки информационной нагрузки на символ сообщения поблочное кодирования всегда выгоднее, чем побуквенное.
Суть блочного кодирования можно уяснить на примере представления десятичных цифр в двоичном коде. Так, при передаче цифры 9 в двоичном коде необходимо затратить 4 символа, т. е. 1001. Для передачи цифры 99 при побуквенном кодировании – при поблочном – 7, так как 7 двоичных знаков достаточно для передачи любой цифры от 0 до 123; при передаче цифры 999 соотношение будет 12 – 10, при передаче цифры 9999 соотношение будет 16 – 13 и т. д. В общем случае «выгода» блочного кодирования получается и за счет того, что в блоках происходит выравнивание вероятностей отдельных символов, что ведёт к повышению информационной нагрузки на символ (см. задачу 5.11) .
При построении оптимальных кодов наибольшее распространение нашли методики Шеннона – Фано и Хаффмена [14,15].
Согласно методике Шеннона – Фано построение оптимального ансамбля из сообщений сводится к следующему:
1-й шаг. Множество из сообщений располагается в порядке убывания вероятностей.
2-й шаг. Первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны. По равной вероятности в подгруппах нельзя достичь, то их делят так, чтоб в верхней части (верхней подгруппе) оставались символы суммарная вероятность которых меньше суммарной вероятность символов в нижней части(в нижней подгруппе).
3-й шаг. Первой группе присваивается символ 0, второй группе символ 1.
4-й шаг. Каждую из образованных подгрупп делит на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны.
5-й шаг. Первым группам каждой из подгрупп вновь присваивается 0, а вторым – 1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырёх групп вновь делится на равные(с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.
Согласно методике Хаффмена, для построения оптимального кода N символы первичного алфавита выписываются в порядке убывания вероятностей. Последние n0 символов, где 1 и целое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединенных символов. Последние символы с учетом образованного символа вновь объединяют, получают новый, вспомогательный символ, опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного символа и т. д. до тех пор, пока сумма вероятностей m оставшихся символов после го выписывания в порядке убывания вероятностей не даст сумме вероятность, равную 1. На практике обычно, не производят многократного выписывания вероятностей символов с учетом вероятности вспомогательного символа, а обходятся элементарным геометрическим построением, суть которых сводится к тому, что символы кодируемого алфавита попарно объединяются в новые символы, начиная с символов, имеющих наименьшую вероятность. Затем с учетом вновь образованных символов, которым присваивается значения суммарной вероятности двух предыдущих, строят кодовое дерево, в вершине которого стоит символ с вероятностью 1. При этом отпадает необходимость в упорядочивании символов кодируемого алфавита в порядке убывания вероятностей (см. задачи 5.48 и 5.60).
Построение по указанным выше (либо подобным) методикам коды с неравновероятным распределением символов, имеющие минимальную среднюю длину кодового слова, называют оптимальными неравновероятными кодами (ОНК). Равномерные коды могут быть оптимальными только для передачи сообщений с равномерным распределением символов первичного алфавита, при этом число символов первичного алфавита должно быть равно целой степени числа, равного количеству качественных признаков вторичного алфавита, а в случае двоичных кодов – целой степени двух.
Максимально эффективными будут те ОНК, у которых .
Для двоичных кодов
так как . Очевидно, что равенство (52) удовлетворяется при условии, что длина кода во вторичном алфавите
Величена li точно равна H, если , где n – любое целое число. Если n не является целым числом для всех значений букв первичного алфавита, то и, согласно основной теории кодирования1, средняя длина кодового слова приближается к энтропии источника сообщений по мере укрупнения кодируемых блоков.
Эффективность ОНК оценивают при помощи коэффициента статистического сжатия:
который характеризует уменьшение количества двоичных знаков на символ сообщения при ОНК по сравнению с применением методов нестатистического кодирования и коэффициента относительной эффективности
который показывает, насколько используется статистическая избыточность передаваемого сообщения.
Для наиболее общего случая неравновероятных и взаимозависимых
Для случаев неравновероятных и взаимозависимых символов
Кроме того, являясь оптимальным с точки зрения скорости передачи информации, код может быть неоптимальным с точки зрения предъявляемых к нему требований помехоустойчивости.
1 m – число качественных признаков строящегося оптимального кода.
1 С основой теоремой кодирования для каналов связи без шумов можно ознакомится в работе К. Шеннона «Работа по теории информации и кибернетики» либо в популярном изложении в работах[18,22].