Коды для обнаружения ошибок

П

П

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ ГБПОУ ВО «Богучарский многопрофильный колледж»

.

.

2019 г.

л

Коды для обнаружения ошибок

о

Содержание:

• Общие сведения о кодах.
• Блоковые коды.
• Линейные коды общего вида.
• Коды Хемминга.
• Коды CRC.
• Свёрточные коды.

• Каскадное кодирование. Итеративное декодирование

х

Общие сведенья о кодах

• Корректирующие коды  — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием  помех , а также при её хранении. 33,86 19,05
• Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную  избыточную  информацию ( контрольное число ), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
• С  кодами, исправляющими ошибки , тесно связаны  коды обнаружения ошибок . В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.

В содержание -

а

Общие сведенья о кодах

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

В содержание -

я

Блоковые коды

• Пусть кодируемая информация делится на фрагменты длиной  k бит, которые преобразуются в  кодовые слова  длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n, k). При этом число R=k/n называется  скоростью кода .

• Если исходные k бит код оставляет неизменными, и добавляет n-k  проверочных ,

такой код называется  систематическим , иначе —  несистематическим .

• Задать блоковый код можно по-разному, в том числе таблицей, где каждой

совокупности из k информационных бит сопоставляется n бит кодового слова.

Однако хороший код должен удовлетворять как минимум следующим критериям:

В содержание -

П

Блоковые коды

• способность исправлять как можно большее число ошибок,
• как можно меньшая избыточность,
• простота кодирования и декодирования.
• Нетрудно видеть, что приведённые требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.
• Практически все используемые коды являются  линейными . Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.

В содержание -

р

Линейные коды общего вида

• Линейный блоковый код  — такой код, что множество его  кодовых слов  образует k-мерное линейное подпространство (назовём его C) в n-мерном линейном пространстве,  изоморфное  пространству k -битных  векторов.
• Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G, называемую  порождающей матрицей .

В содержание -

е

Коды Хемминга

• Коды Хемминга  — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что  синдром
• где r - принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

В содержание -

з

Коды CRC

• Коды  CRC  (англ .   cyclic redundancy check  — циклическая избыточная проверка) являются  систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

В содержание -

е

Свёрточные коды

• Свёрточные коды , в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.
• Свёрточные коды , как правило, порождаются дискретной  линейной инвариантной во времени системой . Поэтому, в отличие от большинства блоковых кодов, свёрточное кодирование — очень простая операция, чего нельзя сказать о декодировании.
• Кодирование свёрточным кодом производится с помощью  регистра сдвига , отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.
• Декодирование свёрточных кодов, как правило, производится по  алгоритму Витерби , который пытается восстановить переданную последовательность согласно  критерию максимального правдоподобия .

н

Свёрточный кодер ( k=7, R=1/2 )

В содержание -

т

Каскадное кодирование. Итеративное декодирование

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

• Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

В содержание -

а

Каскадное кодирование. Итеративное декодирование

• Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

В содержание -

ция

Вывод

Это круто

В содержание -