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

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

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

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

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

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

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

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

Разделимые коды, в свою очередь, делятся на систематические (линейные) и несистематические (нелинейные). Систематическими кодами называются блочные разделимые (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, на которые разделяется блок информационных символов.

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

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

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

Главная характеристика блочного кода состоит в том, что это – канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование) ). Обычно, система блочного кодирования получает на входе k-значное кодовое слово W, и преобразовывает его в n-значное кодовое слово C(W). Это кодовое слово и называется блоком.

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

Последовательность входящих информационных символов разбивается на отрезки (блоки), каждый содержащийсимволов:

В кодере производится преобразование каждого отдельного блока в новый блок :

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

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

или

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

или же искажаться

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

. Кодирующая способность блокового кода Расстояние Хэмминга

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

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

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

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

Пример. Расстояние Хэмминга между векторами иравно.

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

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

Примеры кодирования простыми блоковыми арифметическими кодами

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

или

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

или же искажаться

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

Переходим к кодированию букв в двоичной системе: а ,в ,о ,с , забывая пока о пятой букве. Таким образом длина кода. Предположим, что на каждое передаваемое кодовое слово канал связи дает не более одной ошибки: в каждом блоке длины 2 может менятьнаилина— но не сразу оба бита (и не «затирает» бит полностью). Об этом говорит сайт https://intellect.icu . Что может произойти при передаче закодированного сообщения

по такому каналу? Получатель может увидеть следующие варианты:

или или

но не получит следующие:

или

Итак, выбор самого экономичного способа кодирования — когда четырем символам алфавита соответствуют четыре двоичных блока — не решает задачу надежной коммуникации. Увеличим длину кода, пусть а ,в ,о ,с . Что может произойти с этими кодовыми словами при внесении в них ровно одной ошибки? Составим таблицу всех возможных ситуаций:

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

Этот пример служит примером кода, исправляющего ошибки — в данном случае одну ошибку. Что произойдет если зашумленность канала оказывается более высокой, чем предполагалось? Возможны ситуации, когда полученный в результате передачи блок будет содержаться в таблице. Например, если на вход подается блок , а канал портит два бита, то получатель может увидеть блок, который хоть и содержится в таблице, но декодируется совсем не в ту букву, которая передавалась. А может случиться и так, что на выходе из канала получится блок, который совсем не содержится в таблице. Эта ситуация иногда более выгодна, чем предыдущая: декодер можно заставить извещать пользователя об обнаружении ошибки в случае когда полученный блок не содержится в таблице. Можно заложить в декодере одновременно обе возможности — сигнализации об ошибке и ее исправления. На примере полученного блокапосмотрим, что можно предпринять. Обратим внимание, что этот блок отличается от отправленногоа в двух битах, от блокав — также в двух битах, а от каждого из блоково илис — в трех битах. Поэтому, ввиду гипотезы о не более чем двух зашумленных битах, можно при декодировании отбросить два последних варианта, как невозможные.

Определение количества корректирующих символов блоковых кодов

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

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

число проверочных символов r = n – k. К основным характеристикам корректирующих кодов относятся:

− число разрешенных и запрещенных кодовых комбинаций;

− избыточность кода;

− минимальное кодовое расстояние;

− число обнаруживаемых или исправляемых ошибок;

− корректирующие возможности кодов.

Систематические групповые коды

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

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

Рассмотрим следующие страндарты помехоустойчивого кодирования информации

• коды ldpc
• всн-коды
• код хемминга

Код Хемминга

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

• n – длина в битах кодового слова, n=2m-1;
• k – число информационных битов, k=2m-1-1;
• M – число проверочных разрядов, m=-k;
• T – число ошибок (или dmin – расстояние по Хеммингу или de – дистанция по Евклиду).

Код исправляет единичные ошибки. Для исправления пакетов ошибок применяют систему перемежения. Идея метода заключатся в рассеянии символов кодового слова. Символы должны находиться друг от друга на таком расстоянии, чтобы быть подверженными независимым замираниям [1, 2, 12]. При независимых замираниях пораженные символы будут принадлежать к разным кодовым словам. Появляется возможность с помощью исходного кода исправлять ошибки. В литературе известны некоторые виды пере-межения. В нем кодовые слова размещаются в виде строк прямоугольной матрицы, а их считывание осуществляется по столбцам (рис. 4).

Примечание. Способ перехода от максимального расстояния по Хеммингу dmin к дистанции de по Евклиду в теории кодирования не найден.

В помехоустойчивые коды всегда вводятся избыточные биты n-k (redundant bits). Они используются как средство контроля (биты четности – parity bits, контрольные биты – check bits). Отношение числа избыточных битов к числу информационных (n-k)/k называются избыточностью (redundancy) кода. Отношение числа битов данных к общему числу бит-k/n – степень кодирования (code rate). Максимальная величина избыточного кодирования кода не должна превышать T= r/1-r, где r = r-k/n.

Детектор приемника должен начать работу после приема первого символа кодовой последовательности.

Кодер источника u заменяет на своем выходе информационные слова u кодовым словом v. Приемник производит обратное преобразование. В результате на декодер поступает двоичное принятое слово – r.

Кодер двоичного блока (n, k) отображает множество 2k возможных двоичных слов в множестве 2х n мерных кодовых слов.

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

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

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

Циклическим кодом называется код, множество кодовых комбинаций которого представляется совокупностью многочленов степени n-1 и менее, делящихся на некоторый многочлен G(x) степени n-k, являющийся сомножителем бинома Xn +1.

При операциях с циклическими кодами кодовое слово B = bn-1, bn-2 …b1b0 ) представляют в виде многочлена B(X) степени

B(x) = bn-1xn-1 + bn-2xn-2 + b1x+ b01.

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

Проверочная матрица определяется как: H(x) = (xn+1)/g(x) [8-10] Для кода Хемминга (7,4)

Примечание. Многочлен Xn+1 делится на Xm тогда и только тогда, когда n делится на m.

Коды, в которых возможно исправление ошибок, называются совершенными. Многочлен P(x) степени m называется неприводимым в поле GF(2), если он не делится ни на какой многочлен с коэффициентами из GF(2), степени меньше m, но больше 0.

Неприводимый многочлен P(x) называется примитивным, если наименьшая степень n, при которой многочлен Xn+1 делится на многочлен без остатка, равна n = 2m-1.

Блочные коды создаются на основе порождающей матрицы G(x) или по порождающему многочлену g(x).

В этих кодах каждое кодовое слово представляется полиномом, коэффициент которого является элементом кодового слова.

В состав помехоустойчивого кода Хемминга (n, k, t) входят только те кодовые слова, чьи полиномы делятся на один и тот же полином g(x) степени n-k. Этот полином называется порождающим. C(x) = a (x) g(x). Степень полинома проверяется по проверочной матрице H(x).

G(x). Ht (x) = 0 свидетельствует об отсутствии ошибок, a(x) не превышает k-1.

Контроль ошибок определяется с помощью синдромов:

Синдром - это результат проверки четности,

продолжение следует...

Продолжение:

Часть 1 Стандарты помехоустойчивого кодирования
Часть 2 Циклические коды. Представление двоичного кода в виде полинома - Стандарты
Часть 3 Литература - Стандарты помехоустойчивого кодирования