Обработка информации. Кодирование информации как средство обеспечения контроля работы цифрового автомата.
Обработка информации - любое преобразование информации из одного вида в другой, производимое по строгим формальным правилам.
Коды, использующие два различных элементарных сигнала, называются двоичными. Эти сигналы удобно обозначать символами 0 и 1. Тогда кодовое слово будет состоять из последовательностей нулей и единиц.
Двоичное (бинарное) кодирование тесно связано с принципом дихотомии, который реализуется в графическом методе представления двоичной информации в виде графов.
Разработчиками цифрового автомата должны быть предусмотрены меры для создания системы обнаружения возможной ошибки и проработаны меры, позволяющие исправить ошибки. Эти функции следует возложить на систему контроля работы цифрового автомата.
Система контроля - совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки. Система контроля должна строиться с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарушения.
Решение всех задач контроля становится возможным только при наличии определенной избыточности информации. Избыточность может быть создана либо аппаратными (схемными) средствами, либо логическими или информационными средствами.
Задача кодирования информации представляется как некоторое преобразование числовых данных в заданной системе счисления. В частном случае эта операция может быть сведена к группированию символов или представлению в виде символов (цифр) позиционной системы счисления. Так как любая позиционная система не несет в себе избыточности информации и все кодовые комбинации являются разрешенными, использовать такие системы для контроля не представляется возможным.
|
|
|
Методы эффективного кодирования информации. Коды Шеннона-Фано и Хаффмена.
В большинстве случаев буквы сообщений преобразуются в последовательности двоичных символов.
Учитывая статистические свойства источника сообщений, можно минимизировать среднее число двоичных символов, требующихся для выражения одной буквы сообщения, что при отсутствии шума позволяет уменьшить время передачи или объем запоминающего устройства.
Такое эффективное кодирование базируется на основной теореме Шеннона для каналов без шума.
Код Шеннона — Фано строится следующим образом: все имеющиеся К букв располагаются в один столбик в порядке убывания вероятностей. Затем эти буквы разбиваются на две группы: верхнюю и нижнюю так, чтобы суммарные вероятности этих групп были по возможности ближе друг к другу. Для букв верхней группы в качестве первого символа кодового слова используется «1», а для нижней — «0». Далее каждую из двух полученных групп нужно разделить на две части по возможности с близкими суммарными вероятностями; в качестве второго символа кодового слова используется «1» или «0» в зависимости от принадлежности букв верхней или нижней подгруппе и т. д. Данный процесс повторяется до тех пор, пока не приходим к группам, каждая из которых содержит по одной-единственной букве.
|
|
|
Более выгодным, чем код Шеннона — Фано, является так называемый код Хафмена. Пусть буквы (сообщения) входного алфавита A={a1,…, ak} имеют соответственно вероятности p1, p2, …, pk. Предположим, что буквы в алфавите расположены в порядке убывания их вероятностей, т. е. p1≥ p2, …≥ pk-1≥pk Тогда алгоритм кодирования Хафмена состоит в следующем:
1. Два самых маловероятных сообщения объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообщений ak-1, ak, т.е. pk-1+pk. В результате получим сообщения a1, a2, …, ak-2, b, вероятности которых p1, p2, …, pk-2, pk-1+pk. Эти сообщения вновь располагаем в порядке убывания вероятностей.
2. Берем два сообщения, имеющие наименьшие вероятности, объединяем их в одно и вычисляем их в общую вероятность.
|
|
|
3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.
4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно построить, приписывая ветви, которые идут вниз, «0», а вверх — «1».
Так как в процессе кодирования сообщениям сопоставляются только концевые узлы, полученный код является префиксным и всегда однозначно декодируем.
18. Кодирование по методу четности-нечетности.
Кодирование с контролем четности (нечетности) является простейшим видом помехоустойчивого кодирования.
В математическом коде выделяется один контрольный разряд (k). К каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При таком кодировании допускается, что может возникнуть только одна ошибка.
Такое кодирование имеет минимальное кодовое расстояние, равное 2.
|
|
|
Можно представить и несколько видоизмененный способ контроля по методу четности — нечетности, используя так называемые матричные проверки и суммирование производить не только по строкам, но и по столбцам. Длинное число разбивается на группы, каждая из которых содержит j разрядов. Контрольные разряды выделяются всем группам по строкам и по столбцам.
Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить ее. Пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд изменил состояние). Это приведет к тому, что при проверке на четность сумма по соответствующим строкам и столбцам изменится для значений, которые содержат элемент. Следовательно, нарушение четности по этой строке и столбцу можно зафиксировать, что, в конечном счете, означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда можно исправить ошибку.
Дата добавления: 2018-08-06; просмотров: 614; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!