Правила – Избыточность -Надежность

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

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

Дублирование данных

Простейшим способом внесения избыточности является полное дублирование данных. Благодаря своей простоте, этот способ иногда применяется на практике, но обладает многочисленными недостатками. Во-первых, избыточность этого метода чрезмерно высока для многих практических применений. Во-вторых, он позволяет только обнаруживать ошибки, но не исправлять их: при отсутствии других правил кодирования, мы не можем знать, какая из копий верна, а какая ошибочна.

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

Бит четности

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

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