Корректирующая способность кода.

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

Из n-значного двоичного кода можно составить N=2ⁿ комбинаций.

Если в кодовой комбинации 1 знак заменяется ошибочно, то такая ошибка называется одиночной, если 2—двойной.

Если при передаче используются все возможные кодовые комбинации, то ошибка любой кратности остаётся незамеченной.

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

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

Код, позволяющий исправить ошибку строится из кодовой комбинации различающихся не менее чем в 3 знака.

Само исправление происходит путём сравнения принятого кода с разрешёнными комбинациями и если обнаружена ошибка, то истиной считается та комбинация, от которой принятая наименее отличается. Это достаточно сложная задача, приводящая к громоздким техническим решениям.

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

Основными параметрами, характеризующими корректирующие свойства кода, являются:

3. Число обнаруживаемых или исправленных ошибок

Избыточность корректирующего кода может быть абсолютной и относительной.

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

Относительной избыточностью называют величину

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

Если производительность источника равна h символов в секунду, то скорость передачи после кодирования этой информации будет равна:

Поскольку в последовательности r символов, только k будет информационным.

Контроль передачи информации с помощью кода Хемминга

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

Блочные коды с d_min=3 и d_min=4 в литературе обычно называются кодом Хэмминга. Это коды систематические. Могут обнаруживать и исправлять ошибки, ориентированы на двоичные коды.

Коды с d_min=3 предназначены для исправления одиночных ошибок, d_min=4 будут исправлять одиночные и обнаруживать двойные ошибки.

При декодировании производится k групповых проверок на чётность.

Если в результате проверки обнаружено чётное количество 1, в регистр пишет 0, если нечётное, то пишет 1.

Обычно код Хэмминга характеризуется 2 цепными числами(11, 7).

Такая запись говорит о том, что при передаче семи битного кода используется 4 контрольных бита, при этом предполагается, что ошибка могла быть в одном бите.

Чтобы число в регистр ошибок указывало номер позиции ошибочного размера, группы для проверки выбираются по следующему правилу:

Примечание: каждый контрольный знак входит только в одну проверяемую группу.

Коды Рида-Соломона. Код Хаффмана. Оптимальное кодирование Шеннона-Фано

Коды Рида-Соломона были предложены в 1960 г. Ирвином Ридом и Густавом Соломоном, являвшимися сотрудниками Линкольнской лаборатории МТИ. Ключом к использованию этой технологии стало изобретение эффективного алгоритма декодирования Элвином Беликамфом, профессором Калифорнийского университета Беркли. Коды Рида-Соломона базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств. Коды Рида-Соломона применяются для исправления ошибок во многих системах, включая:

· Устройства памяти (включая магнитные ленты, CD, DVD, штриховые коды, и т.д.)

· Беспроводные или мобильные коммуникации (включая сотовые телефоны, микроволновые каналы и т.д.)

Кодировщик Рида-Соломона берет блок цифровых данных и добавляет дополнительные "избыточные" биты. Ошибки происходят при передаче по каналам связи или по разным причинам при запоминании (например, из-за шума или наводок, царапин на CD и т.д.). Декодер Рида-Соломона обрабатывает каждый блок, пытается исправить ошибки и восстановить исходные данные. Число и типы ошибок, которые могут быть исправлены, зависят от характеристик кода Рида-Соломона.

Популярным кодом Рида-Соломона является RS(255,223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами четности. Для этого кода:

Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть, ошибки могут быть исправлены, если число искаженных байт не превышает 16.

При размере символа s, максимальная длина кодового слова (n) для кода Рида-Соломона равна n = 2^s – 1.

Например, максимальная длина кода с 8-битными символами (s=8) равна 255 байтам.

Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некоторого числа информационных символов на входе кодировщика (передавать их в этом случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив.

Код (255,223), описанный выше, может быть укорочен до (200,168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255,223) и передаст только 168 информационных байт и 32 байта четности.

Объем вычислительной мощности, необходимой для кодирования и декодирования кодов Рида-Соломона зависит от числа символов четности. Большое значение t означает, что большее число ошибок может быть исправлено, но это потребует большей вычислительной мощности по сравнению с вариантом при меньшем t.

Основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G, известный обоим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома.

Декодирование осуществляется с точностью до наоборот: если при делении кодового слова C на полином G декодер внезапно получает остаток, то он должен сообщить об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно.

Если степень полинома G (называемого также порождающим полиномом) превосходит степень кодового слова по меньшей мере на две степени, то декодер может не только обнаруживать, но и исправлять одиночные ошибки. Если же превосходство степени порождающего полинома над кодовым словом равно четырем, то восстановлению поддаются и двойные ошибки. Короче говоря, степень полинома k связана с максимальным количеством исправляемых ошибок t следующим образом: k=2*t. Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. В то же время, максимальное количество распознаваемых ошибок равно t, т.е. избыточность составляет один символ на каждую распознаваемую ошибку.

Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты не верны.

Код RS(255,223) может исправить до 16 ошибок в символах. В худшем случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем случае, корректируются 16 полностью неверных байт, при этом исправляется 16x8=128 битовых ошибок.

Коды Рида-Соломона особенно хорошо подходят для корректировки кластеров ошибок (когда неверными оказываются большие группы бит кодового слова, следующие подряд).

Преимущество использования кодов Рида-Соломона заключается в том, что вероятность сохранения ошибок в декодированных данных обычно много меньше, чем вероятность ошибок, если коды Рида-Соломона не используются. Это часто называется выигрышем кодирования.

Пример: Пусть имеется цифровая телекоммуникационная система, работающая с BER (Bit Error Ratio) равной 10-9, т.е. не более 1 из 109 бит передается с ошибкой. Такого результата можно достичь путем увеличения мощности передатчика или применением кодов Рида-Соломона (или другого типа коррекции ошибок). Алгоритм Рида-Соломона позволяет системе достичь требуемого уровня BER с более низкой выходной мощностью передатчика.

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: