Код который всегда содержит постоянное количество информационных и контрольных знаков
Классификация рассматриваемых в данной главе методов кодирования приведена на рис. 5.2. Эта классификация не является исчерпывающей, в нее включены лишь некоторые методы, которые широко используются в современных системах связи.
Коды можно разделить на две самостоятельные группы. К первой относятся коды, использующие все возможные комбинации – неизбыточные коды. В литературе их еще называют простыми, или первичными. Ко второй группе относятся коды, использующие лишь определенную часть всех возможных комбинаций, такие коды называются избыточными. Оставшаяся часть комбинаций используется для обнаружения или исправления ошибок, возникающих при передаче сообщений. В этих кодах количество разрядов кодовых комбинаций можно условно разделить на определенное число разрядов, предназначенных для информации (информационные разряды), и число разрядов, предназначенных для коррекции ошибок (проверочные разряды).
Обе группы кодов, в свою очередь, подразделяются на равномерные и неравномерные. Равномерные коды – это коды, все кодовые комбинации которых содержат постоянное количество разрядов. Неравномерные коды содержат кодовые комбинации с различным числом разрядов. Ввиду того что неравномерные избыточные коды не нашли применения на практике из-за сложности их технической реализации, в дальнейшем их рассматривать не будем.
Все корректирующие (избыточные) коды делятся на два больших класса: блочные и непрерывные коды (рис. 5.2).
При кодировании блочным кодом последовательность 
элементов данных от источника сообщений принимается за блок (сообщение). Каждому возможному блоку из информационных символов ставится в соответствие кодовый блок (слово) длиной 
. Код называется 
– кодом, 
. Кодовый блок в канале связи искажается шумом и декодируется независимо от других кодовых блоков.
В разделимых кодах всегда можно выделить информационные символы, содержащие передаваемую информацию, и контрольные (проверочные) символы, которые являются избыточными и служат исключительно для коррекции ошибок. Неразделимые коды не имеют четкого разделения кодовой комбинации на информационные и проверочные символы. К ним относятся коды с постоянным весом и коды Плоткина [2].
Разделимые блочные коды, в свою очередь, делятся на несистематические и систематические. Наиболее многочисленный класс разделимых кодов составляют систематические коды. Основная их особенность в том, что проверочные символы образуются как линейные комбинации информационных символов. К систематическим кодам относятся коды с проверкой на четность, коды с повторением, корреляционный, инверсный, коды Хэмминга, Голея, Рида-Маллера, Макдональда, Варшамова, с малой плотностью проверок на четность, итеративный код [2].
В несистематических кодах проверочные символы представляют собой суммы подблоков с 
разрядами, на которые разделена последовательность информационных символов. К этим кодам относятся коды Бергера.
Разновидностью систематических кодов являются циклические коды. Кроме всех свойств систематического кода, циклические коды имеют следующее свойство: если некоторая кодовая комбинация принадлежит коду, то получающаяся путем циклической перестановки символов новая комбинация также принадлежит данному коду. К наиболее известным циклическим кодам относятся простейшие коды, коды Хэмминга, Боуза-Чоудхури-Хоквингема, мажоритарные, коды Файра, Абрамсона, Миласа-Абрамсона, Рида-Соломона, компаундные коды.
Отличительной особенностью непрерывных кодов является то, что первичная последовательность символов, несущих информацию, непрерывно преобразуется по определенному закону в другую последовательность, содержащую избыточное число символов. Здесь процессы кодирования и декодирования не требуют деления кодовых символов на блоки.
Систематические коды
Систематические коды относятся к блочным разделимым кодам, т. е. к кодам, где операция кодирования осуществляется независимо в пределах каждой комбинации, состоящей из информационных и контрольных символов.
Остановимся кратко на общих принципах построения систематических кодов. Если обозначить информационные символы буквами с, контрольные — буквами е, то любую кодовую комбинацию, содержащую к информационных и г контрольных символов, можно представить последовательностью:
где с и е в двоичном коде принимают значения 0 или 1.
Процесс кодирования на передающем конце сводится к образованию контрольных символов, которые выражаются в виде линейной функции информационных символов:
Здесь 
— коэффициенты, равные 0 или
— знаки суммирования по модулю два. Значения ctji выбираются по определенным правилам, установленным для данного вида кода. Иными словами, символы е представляют собой суммы по модулю два информационных символов в различных сочетаниях.
Процедура декодирования принятых комбинаций может осуществляться различными методами. Один из них, так называемый метод контрольных чисел, состоит в следующем. Из информационных символов принятой кодовой комбинации 
образуется по правилу (7.9) вторая группа контрольных символов: 
Затем производится сравнение обеих групп контрольных символов путем их суммирования по модулю два:
Полученное число X называется контрольным числом или синдромом. С его помощью можно обнаружить или исправить часть ошибок. Если ошибки в принятой комбинации отсутствуют, то все суммы 
, а следовательно, и
контрольное число X будет равным нулю. При появлении ошибок некоторые значения л: могут оказаться равными 1. В этом случае Х*0, что и позволяет обнаруживать ошибки. Таким образом, контрольное число X определяется путаем г проверок на четность.
Для исправления ошибок знание одного факта их возникновения является недостаточным, необходимо указать номер ошибочно принятых символов. С этой целью каждому сочетанию исправляемых ошибок в комбинации присваивается одно из контрольных чисел, что позволяет по известному контрольному числу определить местоположение ошибок и исправить их.
Контрольное число X записывается в двоичной системе, поэтому общее количество различных контрольных чисел, отличающихся от нуля, равно 2 r —1. Очевидно, это количество должно быть не меньше числа различных сочетаний ошибочных символов, подлежащих исправлению. Например, если код предназначен для исправления одиночных ошибок, то число различных вариантов таких ошибок равно к + r. В этом случае должно выполняться условие:
Формула (7.11) позволяет при заданном количестве информационных символов к определить необходимое число контрольных символов г, с помощью которых исправляются все одиночные ошибки.
Код который всегда содержит постоянное количество информационных и контрольных знаков
Основы передачи дискретных сообщений
Лабораторная работа «Коды Хаффмана»
Изучение принципа эффективного кодирования источника дискретных сообщений.
Таблица 1 Вероятности появления сообщений алфавита
Вариант для построения кода определяется по последней цифре пароля. При N>7 номер варианта равен N-7. Если N=0, то вариант 3.
К числу основных информационных характеристик источника сообщений относятся: количество информации в отдельных сообщениях, энтропия и производительность источника сообщений.
Среднее количество информации, выдаваемое источником в единицу времени, называют производительностью источника и определяют по формуле:
где Т – среднее время, отводимое на передачу одного сообщения.
Выражение для средней длительности сообщения имеет вид
Код 2 декодируется однозначно, поскольку все кодовые комбинации этого кода имеют равные длины и различны.
Код 3 также однозначно декодируемый, поскольку никакая его кодовая комбинация не является началом (префиксом) другой кодового слова.
Код, обладающий тем свойством, что никакая более короткая комбинация не является началом другой более длинной комбинации кода, называют префиксным. Префиксные коды всегда однозначно декодируемы.
Кодовое дерево для множества кодовых слов.
Рисунок 1. Пример двоичного кодового дерева
Наглядное графическое изображение множества кодовых комбинаций можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного кодового дерева изображен на рисунке 1.
Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между “0” и “1” в качестве первого двоичного символа кодовой комбинации: левая ветвь соответствует “0”, а правая – “1”. Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых комбинаций, левая означает “0”, а правая – “1” и т. д. Ясно, что последовательность символов каждой кодовой комбинации определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.
Формально кодовые комбинации могут быть приписаны также промежуточным узлам. Например, промежуточному узлу второго порядка на рисунке 1 можно приписать комбинацию 11, которая соответствует первым двум символам кодовых комбинаций, соответствующих концевым узлам, порождаемых этим узлом. Однако кодовые комбинации, соответствующие промежуточным узлам, не могут быть использованы для представления сообщений, так как в этом случае нарушается требование префиксности кода.
Требование, чтобы только концевые узлы сопоставлялись сообщениям, и обеспечивает условие при котором ни одна из кодовых комбинаций не совпадает с началом (префиксом) более длинной кодовой комбинации. Любой код, кодовые комбинации которого соответствуют различным концевым вершинам некоторого двоичного дерева, является префиксным, т. е. однозначно декодируемым.
На рисунке 2 изображены кодовые деревья, соответствующие кодам 2 и 3 (см. таблицу 2).
Рисунок 2 Кодовые деревья для кодов 2 (а) и 3 (б)
Известно, что нельзя закодировать сообщение двоичным кодом таким образом, чтобы средняя длина кодовых комбинаций была меньше, чем величина энтропии источника сообщений, т.е.
Тогда алгоритм кодирования Хаффмена состоит в следующем:
Так как в процессе кодирования сообщениям сопоставляются только концевые узлы, полученный код (код Хаффмена) является префиксным и следовательно всегда однозначно декодируемым.
В данной работе рекомендуется обозначать “1” ветвь идущую от узла в сторону сообщения с большей вероятностью появления.
Построение кода Хаффмена для восьми сообщений, появляющихся с вероятностями 0,2; 0,2; 0,15; 0,13; 0,12; 0,1; 0,07; 0,03, иллюстрируется рисунками 3 и 4.
Рисунок 4 Кодовое дерево
Из таблицы 4 видно, что полученный код является неравномерным, причем сообщению с максимальной вероятностью появления соответствует минимальная длительность кодовой комбинации (2 ), а сообщению с минимальной вероятностью – максимальная (4 ).
Код Хэмминга. Пример работы алгоритма
Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Также стоит отметить, что существуют более совершенные модификации данного алгоритма, которые позволяют обнаруживать (и если возможно исправлять) большее количество ошибок.
Сразу стоит сказать, что Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты (вычисленные особым образом). Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.
Как это работает.
Для того, чтобы понять работу данного алгоритма, рассмотрим пример.
Подготовка
Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.
На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:
и
После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):
Было:
Стало:
Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».
Вычисление контрольных бит.
Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит (как неожиданно), но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:
Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу. Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
Высчитав контрольные биты для нашего информационного слова получаем следующее:
и для второй части:
Вот и всё! Первая часть алгоритма завершена.
Декодирование и исправление ошибок.
Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.
Заключение.
В данном примере, я взял длину информационного сообщения именно 16 бит, так как мне кажется, что она наиболее оптимальная для рассмотрения примера (не слишком длинная и не слишком короткая), но конечно же длину можно взять любую. Только стоит учитывать, что в данной простой версии алгоритма на одно информационное слово можно исправить только одну ошибку.
Примечание.
На написание этого топика меня подвигло то, что в поиске я не нашёл на Хабре статей на эту тему (чему я был крайне удивлён). Поэтому я решил отчасти исправить эту ситуацию и максимально подробно показать как этот алгоритм работает. Я намеренно не приводил ни одной формулы, дабы попытаться своими словами донести процесс работы алгоритма на примере.
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
Классификация помехоустойчивых кодов
Рис. 12.1. Примеры классов ошибок
Ввиду этого, на рис. 12.2 представлена классификация только избыточных кодов. Однако при всем их многообразии дать абсолютно точное их разделение на самостоятельные группы и подгруппы, чтобы ни одна из них не содержала признаков других групп, практически невозможно. Поэтому в классификации на рис. 12.2 приведено чисто условное разделение кодов. Все коды на рис. 12.2 в той или иной степени обладают корректирующими способностями, однако в классификации не рассматриваются коды типа Лаби Трансформ, исправляющие стирания.
Избыточные коды разделяются на коды для обнаружения и исправления ошибок в работе устройств преобразования данных и коды, позволяющие контролировать ошибки при передаче данных.
К кодам для обнаружения ошибок в работе устройств преобразования данных относятся коды Фибоначчи, AN-коды, остаточные коды, коды «золотой» пропорции, коды, обеспечивающие контроль по вычету, и т. п. Область применения таких кодов: арифметические, логические и управляющие операции, аналого-цифровые и цифро-аналоговые преобразования. В вычислительных системах и комплексах с помощью данного класса кодов осуществляется введение избыточности на самом раннем этапе их проектирования.
По способу ввода избыточности коды можно разделить на блоковые (блочные) и непрерывные (древовидные). Блоковый код состоит из набора кодовых слов фиксированной длины. При блоковом кодировании каждый блок информационных символов обрабатывается отдельно. В свою очередь, непрерывный кодер обладает памятью в том смысле, что кодовая последовательность зависит не только от информационных символов, находящихся на данный момент в процессе кодирования, но и от предыдущих, уже прошедших кодирование ранее.
Рис. 12.2. Классификация помехоустойчивых кодов
В данном курсе класс непрерывных кодов нс рассматривается. Подробнее остановимся на классе блоковых (блочных) кодов.
Блочные коды представляют собой обширную группу помехоустойчивых кодов, в которых каждое сообщение передается строго определенным набором символов. В зависимости от способа разделения проверочных символов эти коды делятся на разделимые и неразделимые.
В разделимых кодах информационные разряды и проверочные позиции всегда расположены на одних и тех же местах.
Неразделимые коды нс имеют четкого разделения кодовой комбинации на информационные и проверочные символы. В неразделимых кодах определение правильности принятого сообщения производится по количественному сопоставлению определенных качественных признаков в переданных и принятых сообщениях. К неразделимым кодам относятся коды с постоянным весом, код Плоткина. К этой группе может быть отнесен и код Грея, который сам по себе не обладает корректирующей избыточностью, но при соответствующих ограничениях может обнаруживать одиночные ошибки. В коде Грея каждая последующая комбинация отличается от предыдущей одним символом. Этот код не может корректировать ошибки какой-либо кратности, поэтому не представляет для нас интереса.