Помехоустойчивые коды

Содержание
  1. 7. Корректирующие коды. Теория передачи сигналов
  2. 7.1. Классификация корректирующих кодов
  3. 7.2. Принципы помехоустойчивого кодирования
  4. Помехоустойчивые коды
  5. Принцип помехоустойчивого кодирования
  6. Классификация помехоустойчивых кодов
  7. Помехоустойчивое кодирование. Коды Хэмминга
  8. Исправление ошибок в помехоустойчивом кодировании
  9. Параметры помехоустойчивого кодирования
  10. Контроль чётности
  11. Классификация помехоустойчивых кодов
  12. Код Хэмминга
  13. Декодирование кода Хэмминга
  14. Расстояние Хэмминга
  15. Помехоустойчивые коды
  16. Компромиссы при использовании помехоустойчивых кодов
  17. Необходимость чередования (перемежения)
  18. 8. Помехоустойчивое кодирование. Классификация помехоустойчивых кодов
  19. Классификация помехоустойчивых кодов
  20. Помехоустойчивое кодирование с иcпользованием различных кодов
  21. Код с проверкой на четность
  22. Код Хэмминга
  23. Коды-произведения

7. Корректирующие коды. Теория передачи сигналов

Помехоустойчивые коды

7.1. Классификация корректирующих кодов

7.2. Принципы помехоустойчивого кодирования

7.3. Систематические коды

7.4. Код с четным числом единиц. Инверсионный код

7.5. Коды Хэмминга

7.6. Циклические коды

7.7. Коды с постоянным весом

7.8. Непрерывные коды

7.1. Классификация корректирующих кодов

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

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

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

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

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

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

В настоящее время известно большое количество корректирующих кодов, отличающихся как принципами построения, так и основными характеристиками. Рассмотрим их простейшую классификацию, дающую представление об основных группах, к которым принадлежит большая часть известных кодов [12]. На рис. 7.1 показана схема, поясняющая классификацию, проведенную по способам построения корректирующих кодов.

Все известные в настоящее время коды могут быть разделены

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

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

Здесь процессы кодирования и декодирования не требуют деления кодовых символов на блоки.

Рис. 7.1. Классификация корректирующих кодов

Разновидностями как блочных, так и непрерывных кодов являются разделимые и неразделимые коды.

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

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

В свою очередь, линейные коды могут быть |разбиты на два подкласса: систематические и несистематические. Все двоичные систематические коды являются групповыми.

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

Вертикальными прямоугольниками на схеме рис. 7.1 представлены некоторые конкретные коды, описанные в последующих параграфах.

7.2. Принципы помехоустойчивого кодирования

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

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

В обычном некорректирующем коде без избыточности, например в коде Бодо, число комбинаций М выбирается равным числу сообщений алфавита источника М0и все комбинации используются для передачи информации. Корректирующие коды строятся так, чтобы число комбинаций М превышало число сообщений источника М0. Однако в.

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

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

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

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

Расстояние между комбинациями  и  условно обозначено на рис. 7.2а, где показаны промежуточные комбинации, отличающиеся друг от друга одним символом.

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

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

Рис. 7.2.  Геометрическое представление разрешенных и запрещенных кодовых комбинаций

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

(7.1)

Если g>d, то некоторые ошибки также обнаруживаются. Однако полной гарантии обнаружения ошибок здесь нет, так как ошибочная комбинация ib этом случае может совпасть с какой-либо разрешенной комбинацией. Минимальное кодовое расстояние, при котором обнаруживаются любые одиночные ошибки, d=2.

Процедура исправления ошибок в процессе декодирования сводится к определению переданной комбинации по известной принятой.

Расстояние между переданной разрешенной комбинацией и принятой запрещенной комбинацией d0 равно кратности ошибок g.

Если ошибки в символах комбинации происходят независимо относительно друг друга, то вероятность искажения некоторых g символов в n-значной комбинации будет равна:

                                                                                                         (7.2)

где — вероятность искажения одного символа. Так как обычно

Источник: https://siblec.ru/telekommunikatsii/teoriya-peredachi-signalov/7-korrektiruyushchie-kody

Помехоустойчивые коды

Помехоустойчивые коды

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

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

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

Пример 1

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

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

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

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

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

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

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

это слово не могло быть передано.

Принцип помехоустойчивого кодирования

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

На рисунке 1а все возможные кодовые слова входят в алфавит кода, шаг Хемминга равен $d=1$. Шаг Хемминга равен количеству символов, которыми отличаются соседние кодовые слова (они соединены ребрами куба). При ошибке в кодовом слове возникает другое слово, входящее в алфавит кода (невозможны ни определение, ни исправление ошибки).

При шаге Хемминга $d=2$ (рис.1б) при возникновении одиночной ошибки появляется кодовое слово, не входящее в алфавит кода (возможно определение ошибки), но появившееся кодовое слово лежит на одинаковом расстоянии от трех разрешенных, поэтому исправление ошибки невозможно.

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

Если же количество ошибок будет четным (рис.1б), то возникнет слово, входящее в алфавит кода, при этом невозможно обнаружение ошибок.

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

Определение 1

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

Рисунок 1. Трехмерная модель трехразрядного кода

При $d=3$ только два кодовых слова из восьми возможных входят в алфавит кода. При возникновении одиночной ошибки получится слово, не входящее в алфавит кода (возможно обнаружение ошибки), при чем это слово будет находиться ближе к исходному, чем и объясняется возможность исправления ошибки.

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

Этим объясняется то, что цифровые системы передач – пороговые: пока количество ошибок не превысило то, на которое рассчитан код, канальный декодер справляется с ними и исправляет правильно; при превышении количеством ошибок разрешенного числа происходит неправильное их исправление, что приводит к невозможности приема цифрового сигнала.

Как видно из рисунка 1, помехоустойчивое кодирование возможно за счет введения в цифровой сигнал избыточности (дополнительных символов). Четыре комбинации (рис.1б) можно передать двумя битами, а две (рис.1в) – одним, но при этом не было бы возможным исправление ошибок.

Помехоустойчивые коды характеризуются числами $k$ и $n$, где $n$ – количество символов в информационном слове, приходящем на помехоустойчивый кодер, а $k$ – количество символов в кодовом слове, выходящем с помехоустойчивого кодера.

Отношение $\frac{k}{n}$ показывает, во сколько раз скорость цифрового потока на выходе помехоустойчивого кодера больше, чем на его входе, это отношение называют скоростью помехоустойчивого кода. Разность ($k-n$) равна количеству дополнительных (проверочных) символов в кодовом слове.

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

Именно поэтому в различных системах передач (спутниковых, кабельных или наземного цифрового вещания) используются отличные друг от друга цифровые системы вещания, в которых определяется компромисс между исправляющей возможностью и скоростью помехоустойчивого кода (DVB-T (наземная), DVB-C (кабельная), DVB-S (спутниковая)).

Классификация помехоустойчивых кодов

Помехоустойчивые коды классифицируются на:

  1. Блоковые и сверточные.
  2. Систематические и несистематические.

В блоковых кодах формирование проверочных символов ведется на основе одного блока информации, например, информационного слова. Декодирование производится на основе одного кодового слова.

В сверточных кодах формирование проверочных символов производится на основе нескольких блоков информации (информационных слов), а декодирование — на основе нескольких кодовых слов.

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

Сверточные коды еще называют решетчатыми (трилистными).

Систематические коды определяют наличие в кодовом слове информационного в явном виде.

В несистематических кодах информационного слова в кодовом нет, т.е. при помехоустойчивом кодировании информационному слову с количеством символов n ставится в соответствие кодовое слово с количеством символов $k$.

Пример 2

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

Операции по определению кодового слова на передающем конце и по определению и исправлению ошибок на приемном конце выполняются как действия с многочленами.

Если кодируемая информация $i$ описывается набором из n символов (информационное слово), то этому слову можно сопоставить многочлен:

$i(x)=in-1xn-1+in-2xn-2+……+i1x1+i0$,

где $x$ – основание системы счисления (для двоичных кодов $x=2$)

$i$ – значение соответствующего бита информационного слова ($0$ или $1$)

Например, информационное слово $11010011$, которое равно $211$ уровню, можно записать в виде многочлена:

$1 \cdot 27+1 cdot 26+0 \cdot 25+1 \cdot 24+0 \cdot 3+0 \cdot 22+1 \cdot 21+1 \cdot 20=211$

Кодовое слово из $k$ символов, которое будет сопоставлено информационному, также можно представить в виде кодового многочлена:

$c(x)=ck-1xk-1+ck-2xk-2+……+c1x1+c0$ ,

где $c$ – значение соответствующего бита кодового слова.

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

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

При этом формируется передаваемое кодовое слово, которое делится на порождающий многочлен, формируя исходное информационное слово.

Для возможности исправления в кодовом слове t ошибок количество проверочных символов в кодовом слове должно быть равно $2t (k-n=2t)$, степень порождающего многочлена также равна количеству проверочных символов. Порождающий многочлен определяется по формуле:

$g(x)=gk-nxk-n+gk-n-1xk-n-1+……+g1x1+g0$

где $g$ – значение соответствующего бита порождающего слова.

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

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

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

Принцип действия такого кода изображён на рисунке 2.

Рисунок 2. Коды-произведения. Схема структурная

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

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

Этот процесс называется перемешиванием или перемежением.

При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи.

Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.

Источник: https://spravochnick.ru/informatika/kodirovanie_informacii/pomehoustoychivye_kody/

Помехоустойчивое кодирование. Коды Хэмминга

Помехоустойчивые коды

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

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

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

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

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

  • запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
  • прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

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

Исправление ошибок в помехоустойчивом кодировании

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

Простейший пример – мажоритарный метод, он же многократная передача, в котором один символ передается многократно, а на приемной стороне принимается решение о том символе, количество которых больше.

Допустим есть 4 символа информации, А, B, С,D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию. 

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

Необходимо найти ошибку с помощью ания, каких символов больше, символов В или символов С? Явно символов В больше, чем символов С, соответственно принимаем решение, что передавался символ В, а символ С ошибочный. 

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

Параметры помехоустойчивого кодирования

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

  • где n – количество символов закодированного сообщения (результата кодирования);
  •   m – количество проверочных символов, добавляемых при кодировании;
  •   k – количество информационных символов.

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов,  Рида-Соломона (15, 11) и т.д. 

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

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

Контроль чётности

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

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

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

1 1 0 0 0 1 0 0 | 1 

Под кратностью понимается, всевозможные ошибки, которые можно обнаружить. В этом случае, кратность исправляемых ошибок 0, так как мы не можем исправить ошибки, а кратность обнаруживаемых 1. 

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности. 

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

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется. 

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные. 

Рассчитаем скорость кода для: 

Здесь R=8/9=0,88

  • И для прямоугольного кода:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

  • Непрерывные — процесс кодирования и декодирования носит непрерывный характер. Сверточный код является частным случаем непрерывного кода. На вход кодера поступил один символ, соответственно, появилось несколько на выходе, т.е. на каждый входной символ формируется несколько выходных, так как добавляется избыточность.
  • Блочные (Блоковые) — процесс кодирования и декодирования осуществляется по блокам. С точки зрения понимания работы, блочный код проще, разбиваем код на блоки и каждый блок кодируется в отдельности. 

По используемому алфавиту:

  • Двоичные. Оперируют битами.
  • Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды. 

Блочные коды делятся на

  • Систематические  — отдельно не измененные информационные символы, отдельно проверочные символы. Если на входе кодера присутствует блок из k символов, и в процессе кодирования сформировали еще какое-то количество проверочных символов и проверочные символы ставим рядом к информационным в конец или в начало. Выходной блок на выходе кодера будет состоять из информационных символов и проверочных. 
  • Несистематические — символы исходного сообщения в явном виде не присутствуют. На вход пришел блок k, на выходе получили блок размером n, блок на выходе кодера не будет содержать в себе исходных данных. 

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

Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.  

Код Хэмминга

Код Хэмминга — наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Позволяет устранить одну ошибку и находить двойную. 

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности. 

Декодирование кода Хэмминга

Декодирование происходит через вычисление синдрома по выражениям:

Синдром это сложение бит по модулю два. Если синдром не нулевой, то исправление ошибки происходит по таблице декодирования:

Расстояние Хэмминга

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух кодовых слов одинаковой длины различны. Если рассматривать два кодовых слова, (пример на картинке ниже, 1 0 1 1 0 0 1 и 1 0 0 1 1 0 1) видно что они отличаются друг от друга на два символа, соответственно расстояние Хэмминга равно 2.

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

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k. 

  • n — количество символов на входе. 
  • k — количество символов на выходе. 
  • t — кратность исправляемых ошибок. 
  • Отношение k/n — скорость кода. 
  • G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

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

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость. 

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель. 

Компромиссы при использовании помехоустойчивых кодов

Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи. 

Компромисс:

  1. Достоверность vs полоса пропускания.
  2. Мощность vs полоса пропускания.
  3. Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

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

В среднем на блок приходится одна, две ошибки, а в нашем примере потерялся целый блок, включая информационные и проверочные биты. Сможет ли помехоустойчивый код исправить такую ошибку? Эта проблема решаема за счет перемежения.

 

Пример блочного перемежения:

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку.

Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам.

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

Источник: https://ZvonDoZvon.ru/radiosvyaz/kody-hemminga

8. Помехоустойчивое кодирование. Классификация помехоустойчивых кодов

Помехоустойчивые коды

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

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

Классификация помехоустойчивых кодов

В непрерывныхкодах  передаваемая информационнаяпоследовательность не разделяется наблоки. Избыточные элементы размещаютсяв определенном порядке междуинформационными.

Равномерные блочныекоды делятся на разделимые и неразделимые.В разделимых кодах элементы информационнойи проверочной частей кодовой комбинациивсегда стоят на определенных местах. Внеразделимых кодах деление наинформационные и проверочные разрядыотсутствует.

Разделимые коды, в свою очередь, делятся насистематические (линейные) инесистематические (нелинейные).Систематическими  кодами называютсяблочные разделимые (n,k)-коды, в которыхпроверочные элементы представляютсобой линейные комбинации информационных,несистематические коды таким свойствомне обладают.

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

Помехоустойчивыйкод характеризуется тройкой чисел (n,k, d0), где n— общее число разрядов впередаваемом сообщении, включаяпроверочные (г), k=n-r — число информационныхразрядов, d0— минимальное кодовоерасстояние между разрешенными кодовымикомбинациями, определяемое как минимальноечисло различающихся бит в этих комбинациях.Число обнаруживаемых (tj и (или) исправляемых(t ) ошибок (разрядов) связано с параметромd0 соотношениями

Иногда используютсядополнительные показатели избыточности,производные от приведенных вышехарактеристик n, k:R = r/n- относительнаяизбыточность, v = k / n — относительнаяскорость передачи.

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

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

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

 Рис.1.1. Классификация помехоустойчивыхкодов

Простейшимисистематическими кодами являются битычетности/нечетности. Они не позволяютобнаружить ошибки четной кратности(т.е. ошибки одновременно в двух, четырехи т.д.

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

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

Одни иг первых математическиобоснованных и практически использовании?помехоустойчивых кодов — коды Хэммингапредставляют собой простс совокупностьперекрестных проверок на четность/нечетность.Циклические коды могут рассматриватьсякак обобщенные проверки на четность/нечетность

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

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

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

Все помехоустойчивыекоды можно разделить на два основныхкласса: блочные и непрерывные (рекурентныеили цепные).

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

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

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

Как блочные, так инепрерывные коды в зависимости отметодов внесения избыточностиподразделяются на разделимые инеразделимые. В разделимых кодах четкоразграничена роль отдельных символов.

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

Разделимые блочные коды называютсяобычно п,k-кодами,где п –длина кодовых комбинаций, k– числоинформационных символов в комбинациях.

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

Разделимые блочныекоды делятся, в свою очередь, нанесистематические и систематические.Несистематические разделимые кодыстроятся таким образом, что проверочныесимволы определяются как сумма подблоковдлины l,на которые разделяется блок информационныхсимволов.

Большинствоизвестных разделимых кодов составляютсистематические коды. У этих кодовзначение проверочных символов определяетсяв результате проведения линейныхопераций над определенными информационнымисимволами.

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

В результате таких проверокдается информация о наличии ошибок, ав случае необходимости – о позициисимволов, где имеются ошибки.

Источник: https://studfile.net/preview/2948025/page:4/

Помехоустойчивое кодирование с иcпользованием различных кодов

Помехоустойчивые коды

Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.

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

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

По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации.

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

Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:
k/(i+k), где k — количество проверочных бит, i — количество информационных бит. Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).

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

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

В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит.

Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно .

Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.

Ниже показана структурная схемы кодера для данного кода и и декодера Пример:Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10110 (изменился второй бит) Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка. Как говорилось ранее, этот метод служит только для определения одиночной ошибки. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным. В этом случае система не определит ошибку, а это не есть хорошо. К примеру:Начальные данные: 1111
Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
Принятые данные: 10010 (изменились 2 и 3 биты) В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку. Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.

Код Хэмминга

Как говорилось в предыдущей части, очень много для помехоустойчивого кодирования сделал Ричард Хэмминг. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит.

Для каждого числа проверочных символов используется специальная маркировка вида (k, i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (15, 11), (31, 26). Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных.

Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3.

Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания:
первый проверочный бит на 20 = 1;
второй проверочный бит на 21 = 2;
третий проверочный бит на 22 = 4;
но можно и разместить их в конце передаваемого блока данных (но тогда формула для их расчета будет другая).

Теперь рассчитаем эти проверочные символы:r1 = i1 + i2 + i4 r2 = i1 + i3 + i4 r3 = i2 + i3 + i4 Итак, в закодированном сообщении у нас получится следующее: r1 r2 i1 r3 i2 i3 i4

В принципе, работа этого алгоритма разобрана очень детально в статье Код Хэмминга. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла.

Вместо этого приведу структурную схему кодера:
и декодера (может быть, довольно запутано, но лучше начертить не получилось) e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:e0 = k1 + k3 + k5 + k7 mod 2 e1 = k2 + k3 + k6 + k7 mod 2 e2 = k4 + k5 + k6 + k7 mod 2
Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.

Коды-произведения

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

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

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

В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема).

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

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

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

P.S.

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

  • 26 марта 2012 в 16:12
  • 27 апреля 2011 в 10:44
  • 27 апреля 2009 в 19:31

Источник: https://habr.com/post/111336/

Booksm
Добавить комментарий