метод контрольных суммо

Иностранные языки
Искусство. Культура
История
Психология
Русский язык
Философия. Логика. Этика
Прочие гуманитарные
Естественные науки
Астрономия
Биология
Геология
Математика
Механика
Физика
Химия
Экология
Прочие естественные
Общественные науки
Безопасность жизнедеятельности
Военная подготовка
Педагогика
Право. Юриспруденция
Социология. Политология
Физическая культура
Экономика
Экскурсоведение. Туризм
Прочие общественные
Технические науки
Информатика. Вычислительная техника
Промышленность. Энергетика
Радиоэлектроника. Связь
Строительство
Теория управления
Электротехника
Прочие технические
Кодовое дерево, построенное процедурой Хаффмана.
Прямой подсчет дает среднее значение длины кодового слова L=3.145, что совпадает с результатом, полученным с помощью процедуры Шеннона-Фано (это означает, что в данном примере процедура Шеннона-Фано также оказалась оптимальной).
16. Помехоустойчивое кодирование. Основные принципы помехоустойчивого кодирования.
Основные принципы помехоустойчивого кодирования. Помехоустойчивые коды — одно из наиболее эффективных средств обеспечения высокой верности передачи дискретной информации. Создана специальная теория помехоустойчивого кодирования, быстро развивающаяся в последнее время.
Бурное развитие теории помехоустойчивого кодирования связано с внедрением автоматизированных систем, у которых обработка принимаемой информации осуществляется без участия человека. Использование для обработки информации электронных цифровых вычислительных машин предъявляет очень высокие требования к верности передачи информации.
Теорема Шеннона для дискретного канала с помехами утверждает, что вероятность ошибок за счет действия в канале помех может быть обеспечена сколь угодно малой путем выбора соответствующего способа кодирования сигналов. Из этой теоремы вытекает весьма важный вывод о том, что наличие помех не накладывает принципиально ограничений на верность передачи.
Однако в теореме Шеннона не говорится о том, как нужно строить помехоустойчивые коды.
На этот вопрос отвечает теория помехоустойчивого кодирования.
Рассмотрим сущность помехоустойчивого кодирования, а также некоторые теоремы и определения, относящиеся к теории такого кодирования.
Под помехоустойчивыми или корректирующими кодами понимают коды, позволяющие обнаружить и устранить ошибки, происходящие при передаче из-за влияния помех.
Для выяснения идеи помехоустойчивого кодирования рассмотрим двоичный код, нашедший на практике наиболее широкое применение.

Напомним, что двоичный код — это код с основание m=2.
Количество разрядов n в кодовой комбинации принято называть длиной или значностью кода. Каждый разряд может принимать значение 0 или 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают .
Ошибки, вследствие воздействия помех, появляются в том, что в одном или нескольких разрядах кодовой комбинации нули переходят в единицы и, наоборот, единицы переходят в нули. В результате создается новая ложная кодовая комбинация.
Если ошибки происходят только в одном разряде кодовой комбинации, то такие ошибки называются однократными. При наличии ошибок в двух, трех и т.д. разрядах ошибки называются двукратными, трехкратными и т.д.
Для указания мест в кодовой комбинации, где имеются искажения символов, используется вектор ошибки . Вектор ошибки n-разрядного кода — это n-разрядная комбинация, единицы в которой указывают положение искаженных символов кодовой комбинации. Например, если для пятиразрядного кода вектор ошибки имеет =01100, то это значит, что имеют место ошибки в третьем и четвертом разрядах кодовой комбинации.
Вес вектора ошибки характеризует кратность ошибки. Сумма по модулю для искажений кодовой комбинации и вектора ошибки дает исходную неискаженную комбинацию.
Помехоустойчивость кодирования обеспечивается за счет введения избыточности в кодовые комбинации. Это значит, что из n символов кодовой комбинации для передачи информации используется k ) кодовое расстояние должно удовлетворять условию
7.32
При этом нужно иметь в виду, что если обнаруженная кодом ошибка исправлена быть не может, т.е. в данном случае код только обнаруживает ошибку.
17. Помехоустойчивое кодирование. Помехоустойчивость кода. Корректирующие коды.
Помехоустойчивость кода.
Минимальное кодовое расстояние некоторого кода определяется как минимальное расстояние Хэмминга между любыми разрешенными кодовыми словами этого кода. У безызбыточного кода минимальное кодовое расстояние d min =1. Чем больше минимальное кодовое расстояние, тем больше избыточность кода. Максимальное кодовое расстояние кода, очевидно, равно его размеру, т.е. числу двоичных разрядов в кодовом слове.
Непосредственные вычисления кодовых расстояний у рассмотренного выше кода, построенного методом контрольных сумм, дают следующие значения показателей: d min =3 и d max =7.
Очевидно, что -кратная ошибка приводит к тому, что искаженная кодовая комбинация отодвигается от исходной на расстояние . В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую, тоже разрешенную. Следовательно, способность кода обнаруживать все ошибки некоторой кратности зависит от минимального расстояния между разрешенными кодовыми словами: чем больше минимальное кодовое расстояние, тем большей кратности требуется ошибка для перевода любой разрешенной кодовой комбинации в другую разрешенную. Таким образом, можно утверждать, что код с минимальным кодовым расстоянием d min способен обнаруживать любые ошибки кратностью

У рассмотренного выше кода d min =3, следовательно, он может обнаруживать любые однократные и двукратные ошибки.
Способность кода исправлять обнаруженные ошибки состоит в возможности однозначного отнесения запрещенной кодовой комбинации к единственной разрешенной. Для этого необходимо, чтобы минимальное кодовое расстояние превышало расстояние, порождаемое действием двух любых ошибок. Действительно, в этом случае запрещенные кодовые комбинации, получающиеся в результате ошибок из одного кодового слова, никогда не совпадут с запрещенными комбинациями, получающимися в результате ошибок из любого другого кодового слова, а тем более — с другими разрешенными кодовыми словами. Таким образом, необходимо, чтобы выполнялось условие откуда следует
У рассмотренного выше кода, построенного методом контрольных сумм, d min =3, следовательно, он может исправлять только любые однократные ошибки.
Рассмотрим n-разрядный код, основанный на n -кратном повторении каждого передаваемого символа. У него d min = n. Следовательно, максимальная кратность обнаруживаемых ошибок равна , что соответствует случаю искажения всех символов, кроме одного. Максимальная кратность исправляемых ошибок равна ( n -1) /2, что соответствует искажению «почти» половины всех символов. Это соответствует фиксации ошибки при обнаружении хотя бы одного неодинакового символа и исправлению ошибки на основе определения, каких значений больше.
Рассмотрим n-разрядный код, основанный на введении одного разряда контроля четности. У него d min = 2, и, следовательно, максимальеная кратность обнаруживаемых ошибок равна 1, а исправляемых — 0 (код не способен исправлять ошибки).
Граница Хэмминга. Рассмотрим задачу немного иначе. Возьмём n-разрядный код и зададимся вопросом о том, сколько контрольных разрядов должно быть в каждом кодовом слове, чтобы код мог исправлять все ошибки заданной максимальной кратности (разумеется, ).
Возьмём какое-либо разрешенное кодовое слово и подсчитаем общее число кодовых комбинаций, порождаемых из него всевозможными ошибками кратностью не выше . Ситуация отсутствия ошибок дает одну (исходную комбинацию). Все однократные ошибки, искажающие 1 из n разрядов, очевидно, порождают n комбинаций. Все двукратные ошибки, искажающие 2 из n разрядов, очевидно, порождают комбинаций, где - число сочетаний из n по m . Аналогичным образом все m-кратные ошибки, искажающие m из n разрядов, порождают комбинаций. Учитывая, что формально , получаем следующую формулу для числа кодовых комбинаций, приходящихся на каждое разрешенное кодовое слово:
.Общее число кодовых комбинаций n -разрядного кода составляет , следовательно, чтобы комбинации, порождаемые из одного разрешенного кодового слова, не переходили в комбинации, порождаемые из другого, и могли быть исправлены, необходимо, чтобы число разрешенных кодовых слов Q удовлетворяло условию .
Это есть так называемая граница Хэмминга для числа разрешенных кодовых слов.
Граница Хэмминга позволяет определить минимальное число контрольных разрядов, необходимых для исправления ошибок с заданной максимальной кратностью. Пусть в n-разрядном коде k информационных разрядов, тогда число разрешенных кодовых слов составляет . Подставляя это значение в формулу для границы Хэмминга, получаем
Величина n - k, как раз и есть минимальное число контрольных разрядов.
Коды, у которых число контрольных разрядов в точности совпадает с границей Хэмминга, называются совершенными . Совершенные коды обладают минимальной избыточностью при заданном уровне способности исправлять ошибки. В построенном выше примере 7-разрядного кода, исправляющего все однократные ошибки, использовалось 3 контрольных разряда. Подставляя параметры кода в полученную формулу, убеждаемся, что 3 — это минимальное количество контрольных разрядов, необходимое для решения задач, следовательно, код совершенный. Для более сложных случаев (большей кратности ошибок) не всегда удается построить совершенный код.
Классификация корректирующих кодов.
Математическая теория корректирующих кодов бурно развилась в 50-60-х годах XX века в обширную и практически важную самостоятельную науку, базирующуюся на казавшихся самыми абстрактными и далекими от практики разделах современной математики.
У большинства известных в настоящее время корректирующих кодов помехоустойчивость обеспечивается за счет их алгебраических свойств, в связи с чем их называют алгебраическими кодами.
Алгебраические коды подразделяются на два больших класса : блоковые и непрерывные (реккурентные).
В случае блоковых кодов кодирование заключается в

методы подсчета контрольных сумм

методы контрольных сумм

Интерфейс Checksum определяет методы, применяющиеся при подсчете контрольной суммы. Это методы update, getValue и reset.

Читать

метод контрольного суммирования

Контрольные суммы и CRC. Сергей Парунов дата публикации 18-02-2003 12:25.  Этот метод исторически первый и самый быстрый.