Классификация помехоустойчивых кодов

КОДИРОВАНИЕ ИНФОРМАЦИИ

Простейшие коды

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

Главнейшим показателем кода является значность кода или алфавит выбранных элементарных сигналов (символов), используемых для записи информации в выбранном коде. Если выбирается алфавит из двух элементов (букв), например, 0 и 1, то такой код (алфавит) называют двоичным или бинарным, если число элементарных сигналов (букв) выбирают больше двух, то такой код (алфавит) называют многозначным (например, если количество букв алфавита – десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – такой код называют десятичным). Преобразование информации из одного вида (системы обозначений) в другой вид (систему обозначений) называют кодированием.

Например, в двоично-десятичном кодировании, каждая десятичная цифра (сообщение) представляется группой двоичных символов, состоящих из 4-х элементов. Общее число возможных комбинаций двоичного 4-х разрядного числа составляет N = 2⁴ = 16, используется для представления десятичного числа только 10 комбинаций, 6 являются лишними (избыточными), что дает возможность построить большее количество вариантов кода.

При рассмотрении двоичного представления десятичных цифр видно, что использование первых 4-х степеней цифры 2 (2⁰, 2¹, 2², 2³) приводит к одному из возможных кодов 8-4-2-1. Каждый разряд этого кода имеет постоянный вес. Возможны и другие двоично-десятичные коды с другими весами разрядов двоичного числа, например:

Эти коды представляют десятичное число от 0 до 9, однако, они не имеют однозначности в изображении десятичных чисел. Например, код
4-3-2-1 дает определение числа 6 в виде: 0111 или 1010.

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

Широкое распространение в вычислительной технике нашли самодополняющие коды, как двоично-десятичные коды со свойством самодополнения до 9. Такие коды обусловлены заменой операции вычитания операцией сложения в ЭВМ, выполняемых в обратных и дополнительных кодах. Наиболее распространенными кодами является код 2-4-2-1 (код Айкена) и код 8-4-2-1 с избытком 3.

Из таблицы видно, что при инвертировании цифр всех четырех разрядов (замены 0 на 1 и наоборот) получается дополнение до 9 для кодируемой десятичной цифры.

В двоичных кодах при переходе от изображения одного числа к изображению соседнего (старшего или младшего) возможно изменение символов в нескольких разрядах двоичного числа. Так, при переходе от изображения числа 7 (0111) к изображению числа 8 (1000) одновременно меняются символы во всех четырех разрядах. Это может являться источником ошибок при кодировании непрерывных сигналов в двоичный код.

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

Особенности кода Грея:

1. смена в одном разряде элементов кода при переходе от одной комбинации к следующей;

2. в коде можно выделить оси симметрии (оси отражения), относительно которых наблюдается идентичность в некоторых разрядах (в первом разряде 00-11-00-11-...; во втором 0000-1111-0000-1111-... и т.д.).

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

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

Для перевода простого двоичного кода в код Грея нужно:

1. под двоичным числом записать такое же число со сдвигом вправо на один разряд (при этом младший разряд сдвигаемого числа теряется);

2. произвести поразрядное сложение двух чисел по модулю 2 (четности).

Пример: 11010011 перевести в код Грея.

11010011

Å 1101001(1)

10111010                      получен код Грея.

Обратный перевод кода Грея в простой двоичный код решается следующим способом:

1. цифра старшего разряда остается неизменной;

2. каждая последующая цифра (при движении от старшего разряда к младшему) инвертируется столько раз, сколько единиц ей предшествует в коде Грея.

Пример: 10111010 перевести в простой двоичный код.

11010011.

Литература:

[2] стр. 19. [3] стр. 17.

Контрольные вопросы:

1. Почему в двоично-десятичном кодировании возможно применить несколько разных способов кодирования?

2. Для чего применяются самодополняющие коды?

3. Как построен код с избытком 3?

4. В чем особенность кода Грея?

Помехоустойчивые коды

Классификация помехоустойчивых кодов

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

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

Итак, для передачи некоторого количества информации необходима последовательность из k символов. Для придания последовательности корректирующих свойств она удлиняется до n>k символов. Вводимая при этом избыточность определяется коэффициентом избыточности K_изб = k/n.

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

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

Разновидности блочных и непрерывных кодов - разделимые (систематические) и неразделимые (несистематические). В разделимых кодах всегда можно выделить информационные и проверочные (контрольные) символы, последние являются избыточными, вводимыми для коррекции ошибок. В несистематических кодах нет разделения символов на информационные и проверочные.

Сегодня имеется большое разнообразие кодов. Некоторые из них (наиболее употребляемые) отобразим графически.