Теория связи. Основные понятия теории кодирования. Побуквенное кодирование

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

В теории связи существует утверждения, что любой сколь угодно зашумленный канал обладает определенной пропускной способностью – скоростью передачи информации, которая никогда не может быть превышена без ошибок, но в принципе достижима с некоторой произвольно малой вероятностью ошибки. Это утверждение является теоремой о канальном кодировании. Впервые она была сформулирована и доказана К.Э.Шенноном. Наиболее широкое применение получили такие коды как, проверка на четность, коды Хэмминга, циклические проверки для обнаружения ошибок, простейшие сверточные коды и т.п.

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

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

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

Кодирование информации позволяет декодеру с большой вероятностью успеха исправить любые ошибки, возникающие в канале при искажении сигнала помехой. Коды с исправлением ошибок применяются в системах с прямым исправлением, не зависимо от того блочный это код или сверточный. Кодами с исправлением ошибок являются коды Хемминга, симплексные коды, код Голея, коды Рида-Соломона и коды Боуза-Чоудхури-Хокенгема. Методы повышения надежности за счет введения избыточности широко применяются как в различных технических устройствах, так и в повседневной жизни. Например, многие естественные языки обладают избыточностью (русский, японский, английский), за счет чего мы можем понять речь даже при сильном искажении. В технике, например, могут установить два – три одинаковых устройства при выходе из строя одного его можно заменить другим. Или с помощью одного устройства выполняются дважды одни и те же вычисления, и если результаты этих вычислений совпадают, то принимается решение о том, что вычисления выполнены без ошибок. Если же результаты этих вычислений не совпадают, значит, в процессе вычисления произошла ошибка. Вычисления повторяются. Это примеры повышения надежности при наличии избыточности.

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

Циклический, избыточный код – это разновидность полиномиального кода (семейство линейных кодов с исправлением или обнаружением ошибок, алгоритмы кодирования и декодирования которых могут быть выражены соответствующим образом в терминах полиномов над базовым полем, следовательно, могут быть реализованы в понятиях регистров сдвига с комбинационной линейной логикой, Р151). В принципе, каждый блок можно считать полиномом. Этот полином А умножается в кодере на порождающий полином (формально заданный степенной ряд, то есть сумма множества степенных выражений независимых переменных Р150) G, в результате чего формируется полином AG. В процессе передачи или записи этого полинома к нему добавляется полином ошибки E:

AG + E.

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

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

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

Для представления чисел используются непозиционные и позиционные системы счисления.

В непозиционных системах каждая цифра имеет свой вес и ее значение не зависит от положения в числе – от позиции. Пример – римская система. Скажем, число 76 в этой системе выглядит так:

LXXVI, где L=50, X=10, V=5, I=1.

Как видно цифрами здесь служат латинские символы.

В позиционных системах значения цифр зависят от их положения (позиции) в числе.

Так, например, человек привык пользоваться десятичной позиционной системой — числа записываются с помощью 10 цифр. Самая правая цифра обозначает единицы, левее — десятки, ещё левее — сотни и т.д.

В любой позиционной системе число может быть представлено в виде многочлена.

Дата добавления: 2015-04-24