Обнаружение и исправление ошибок. Корректирующее кодирование. Коды с обнаружением ошибок.

Обнаружение и исправление ошибок. Корректирующее кодирование. Коды с обнаружением ошибок.


Стратегии борьбы с ошибками:

— внедрение подкорректирующих кодов либо кодами с исправлением ошибок (error-correcting codes), прямое исправление ошибок FEC.

— коды с обнаружением ошибок (error-detecting codes).

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

Коды с исправлением ошибок добавляют к пересылаемой инфы лишниие данные. Кадр состоит из m бит данных (другими словами информационных бит) и r лишних либо контрольных бит.

Набор из n бит, содержащий информационные и контрольные биты, нередко именуют n-битовым кодовым словом. Кодовая норма — это часть кодового слова, несущая неизбыточную информацию, либо m/n. Количество бит, которыми отличаются два кодовых слова, именуется кодовым расстоянием либо расстоянием меж кодовыми комбинациями в смысле Хэмминга. Смысл этого числа заключается в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования 1-го кодового слова в другое пригодится d ошибок в одиночных битах.

1. Коды Хэмминга биты кодового слова нумеруются поочередно слева вправо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т. д.), являются контрольными. Другие биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются m битами данных.

Каждый контрольный бит обеспечивает сумму по модулю 2 либо четность некоторой группы бит, включая самого себя. Один бит может заходить в несколько вычислений контрольных бит. Чтоб найти, в какие группы контрольных сумм будет заходить бит данных в k-й позиции, следует разложить k по степеням числа 2. К примеру, 11 = 8 + 2 + 1, а 29 = 16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (к примеру, 11-й бит проверяется битами 1, 2 и 8). В нашем примере контрольные биты рассчитываются для проверки на четность в сообщении, представляющем буковку «A» в кодах ASCII.

2. Двоичные сверточные коды не относятся к блочному типу и применяется в развернутых сетях (GSM, 802.11). Кодировщик обрабатывает последовательность входных бит и генерирует последовательность выходных бит. В отличие от блочного кода, ни- какие ограничения на размер сообщения не накладываются, также не существует грани кодировки. начение выходного бита находится в зависимости от значения текущего и прошлых входных бит — если у кодировщика есть возможность использовать память. Число прошлых бит, от которого зависит выход, именуется длиной кодового ограничения для данного кода. Сверточные коды были очень популярны для практического внедрения, потому что в декодировании совсем не сложно учитывать неопределенность значения бита (0 либо 1). К примеру, представим, что –1 В соответствует логическому уровню 0, а +1 В соот- ветствует логическому уровню 1. Мы получили для 2-ух бит значения 0,9 В и –0,1 В. Заместо того чтоб сходу определять соответствие — 1 для первого бита и 0 для вто- рого, — можно принять 0,9 В за «очень возможную единицу», а –0,1 В за «возможный нуль» и скорректировать всю последовательность. Для более надежного исправления ошибок к неопределенностям можно использовать разные расширения метода Витерби. Такой подход к обработке неопределенности значения бит именуется деко- дированием с мягеньким принятием решений (soft-decision decoding). И напротив, если мы решаем, какой бит равен нулю, а какой единице, до следующего исправления ошибок, то такой способ именуется декодированием с жестким принятием решений (hard-decision decoding).



3. Коды Рида—Соломона (употребляются в сетях DSL, для исправления ошибок н DVD и Blu-ray дисках) основываются на том, что каждый многочлен n-й степени уникальным образом определяется n + 1 точкой. К примеру, если линия задается формулой ax + b, то вернуть ее можно по двум точкам. Коды Рида—Соломона определяются как многочлены на конечных полях. Для m-битовых знаков длина кодового слова составляет 2m – 1 знаков. Очень нередко выбирают значение m = 8, другими словами одному символу соответствует один байт. Тогда длина кодового слова — 255 байт. Обширно употребляется код (255,233), он добавляет 32 дополнительных знака к 233 символам данных. Декодирование с исправлением ошибок производится с помощью метода Берлекэмпа—Мэсси, который производит подгонку для кодов средней длины. При добавлении 2t лишних знаков код Рида—Соломона способен поправить до t ошибок в любом из переданных знаков. Это значит, к примеру, что код (255,233) с 32 сверхизбыточными знаками исправляет до 16 ошибок. Потому что знаки могут быть поочередными, а размер их обычно составляет 8 бит, то может быть исправление поочередных ошибок в 128 битах. Коды Рида—Соломона нередко употребляют в купе с другими кодами, к примеру сверточными. Сверточные коды отлично обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они не управятся, в особенности если ошибок в приобретенном потоке бит очень много. Добавив вовнутрь сверточного кода код Рида—Соломона, вы можете очистить поток бит от последовательностей ошибок.

4. Коды с малой плотностью проверок на четность (LDPC) — это линейные блочные коды, придуманные Робертом Галлагером. В коде LDPC каждый выходной бит формируется из некого подмножества входных бит. Это приводит нас к матричному представлению кода с низкой плотностью единиц. Приобретенные кодовые слова декодируются методом аппроксимации, который поочередно улучшает лучшее приближение, составленное из приобретенных данных, пока не получает допустимое кодовое слово. Так осуществляется устранение ошибок. Коды LDPC комфортно использовать для блоков огромного размера. По этой причине коды LDPC стремительно добавляются в новые протоколы. Они являются частью эталона цифрового телевидения, сетей Ethernet 10 Гбит/с, сетей, работающих по линиям электропитания, также последней версии 802.11.

Коды с обнаружением ошибок:

1. Код с проверкой на четность.

К отправляемым данным присоединяется бит четности (parity bit), который выбирается так, чтоб число единичных битов в кодовом слове было четным (либо нечетным). Для увеличения защиты от последовательностей ошибок — биты четности вычисляют не в порядке отправки данных — чередование.





Возможно Вам будут интересны работы похожие на: Обнаружение и исправление ошибок. Корректирующее кодирование. Коды с обнаружением ошибок.:


Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Похожый реферат

Cпециально для Вас подготовлен образовательный документ: Обнаружение и исправление ошибок. Корректирующее кодирование. Коды с обнаружением ошибок.