Пусть при передаче кодовых слов происходит не более k ошибок.
Для того чтобы код являлся исправляющим все ошибки, число которых не более k, необходимо и достаточно чтобы наименьшее расстояние между кодовыми словами удовлетворяло неравенству:
d(b1, b2) ³ 2k+1.
Достаточность. Пусть для любых двух слов b1 и b2 выполняется неравенство d(b1, b2) ³ 2k+1. Пусть при передаче слова b1 было принято слово c1, причём произошло не более k ошибок, т. d(b1, c1) £ k. Из неравенства треугольника следует: d(b1, c1) + d(c1, b2) ³ d(b1, b2) ³ 2k+1. Отсюда следует, что d(c1, b2) ³ 2k+1 – d(b1, c1) ³ k + 1, т. расстояние от с1 до любого другого кодового слова b2 больше чем k. Благодаря этому можно однозначно определить ближайшее к слову c1 кодовое слово b1, после чего декодировать его, т. исправить ошибку.
Необходимость. Доказательство от противного. Пусть минимальное расстояние между кодовыми словами меньше, чем 2k+1, т. найдутся два таких слова b1 и b2, что d(b1, b2) £ 2k. Пусть при передаче слова b1 получено слово c1, содержащее ровно k ошибок и расположеное на отрезке между b1 и b2.
Тогда d(b1, c1) = k, при этом d(b2, c1) = d(b1, b2) – d(b1, c1) £ k. Это означает, что по слову c1 нельзя однозначно восстановить, какое было передано кодовое слово – b1 или b2. Пришли к противоречию с условием, что код является исправляющим при условии, что имеется не более k ошибок при передаче.
Для задания всех кодовых слов длины n можно их просто перечислить для каждого исходного передаваемого слова. Таких слов всего 2m. Однако существует более удобный способ задания кодовых слов – матричный.
b = aG,
Пример 3. Рассмотрим порождающую матрицу
С помощью этой матрицы можно задавать (3, 4) – коды. Четвёртый символ кодовых слов будет контрольным: он будет равен 0, если исходное слово содержит чётное число единиц, и будет равен 1 в противном случае. Пусть задано слово a =101; его кодом будет b = aG = b1 b2 b3 b4 , где
b1 = (1*1+0*0+1*0 ) mod 2 = 1;
b2 = (1*0+0*1+1*0 ) mod 2 = 0;
b3 = (1*0+0*0+1*1 ) mod 2 = 1;
b4 = (1*1+0*1+1*1 ) mod 2 = 0;
Для слова a =110 кодовым словом является слово b = 1100.
Пример 4. Рассмотрим порождающую матрицу G= (1, 1, 1, 1, 1). Её размерность 1 ´ 5. Поэтому она задаёт (1, 5) – код. Для слова a1 = 0 получим кодовое слово b1 = 00000; для слова a2 =1 получим b2 = 11111. Здесь минимальное расстояние между b1 и b2 равно 5, т. этот код может обнаружить четырёхкратную ошибку (5=k+1 при k=4) и исправить двукратную (5 = 2*k+1 при k=2).
Пример 5. Порождающая матрица
задаёт (2, 5) – код: a1=00 à b1 = 00000; a2=01 à b2 = 01011; a3=10 à b3 = 10101; a4=11 à b4 = 11110.
Кодовые слова, полученные методом матричного кодирования, образуют коммутативную группу по сложению. Это означает, что если b1 = a1*G и b2 = a2*G, то b1+ b2 = a1*G +a2*G = (a1+a2)*G.
Стратегии борьбы с ошибками:
— использование корректирующих кодов или кодами с исправлением ошибок (error-correcting codes), прямое исправление ошибок FEC.
— коды с обнаружением ошибок (error-detecting codes).
Для того чтобы определить, какой метод лучше подойдет в конкретной ситуации, нужно понять, какой тип ошибок более вероятен. Ни код с исправлением ошибок, ни код с обнаружением ошибок не позволят справиться со всеми возможными ошибками, поскольку лишние биты, передаваемые для повышения надежности, также могут быть повреждены в пути.
Коды с исправлением ошибок добавляют к пересылаемой информации избыточные данные. Кадр состоит из m бит данных (то есть информационных бит) и r избыточных или контрольных бит.
Набор из n бит, содержащий информационные и контрольные биты, часто называют n-битовым кодовым словом. Кодовая норма — это часть кодового слова, несущая неизбыточную информацию, или m/n. Количество бит, которыми отличаются два кодовых слова, называется кодовым расстоянием или расстоянием между кодовыми комбинациями в смысле Хэмминга. Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобится d ошибок в одиночных битах.
Коды Хэмминга биты кодового слова нумеруются последовательно слева направо, начиная с 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.
Двоичные сверточные коды не относятся к блочному типу и применяется в развернутых сетях (GSM, 802. 11). Кодировщик обрабатывает последовательность входных бит и генерирует последовательность выходных бит. В отличие от блочного кода, ни- какие ограничения на размер сообщения не накладываются, также не существует грани кодирования. начение выходного бита зависит от значения текущего и предыдущих входных бит — если у кодировщика есть возможность использовать память. Число предыдущих бит, от которого зависит выход, называется длиной кодового ограничения для данного кода. Сверточные коды были очень популярны для практического применения, так как в декодировании очень легко учесть неопределенность значения бита (0 или 1). Например, предположим, что –1 В соответствует логическому уровню 0, а +1 В соот- ветствует логическому уровню 1. Мы получили для двух бит значения 0,9 В и –0,1 В. Вместо того чтобы сразу определять соответствие — 1 для первого бита и 0 для вто- рого, — можно принять 0,9 В за «очень вероятную единицу», а –0,1 В за «возможный нуль» и скорректировать всю последовательность. Для более надежного исправления ошибок к неопределенностям можно применять различные расширения алгоритма Витерби. Такой подход к обработке неопределенности значения бит называется деко- дированием с мягким принятием решений (soft-decision decoding). И наоборот, если мы решаем, какой бит равен нулю, а какой единице, до последующего исправления ошибок, то такой метод называется декодированием с жестким принятием решений (hard-decision decoding).
Коды Рида—Соломона (используются в сетях 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 битах. Коды Рида—Соломона часто используют в сочетании с другими кодами, например сверточными. Сверточные коды эффективно обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они не справятся, особенно если ошибок в полученном потоке бит слишком много. Добавив внутрь сверточного кода код Рида—Соломона, вы сможете очистить поток бит от последовательностей ошибок.
Коды с малой плотностью проверок на четность (LDPC) — это линейные блочные коды, изобретенные Робертом Галлагером. В коде LDPC каждый выходной бит формируется из некоторого подмножества входных бит. Это приводит нас к матричному представлению кода с низкой плотностью единиц. Полученные кодовые слова декодируются алгоритмом аппроксимации, который последовательно улучшает наилучшее приближение, составленное из полученных данных, пока не получает допустимое кодовое слово. Так осуществляется устранение ошибок. Коды LDPC удобно применять для блоков большого размера. По этой причине коды LDPC быстро добавляются в новые протоколы. Они являются частью стандарта цифрового телевидения, сетей Ethernet 10 Гбит/с, сетей, работающих по линиям электропитания, а также последней версии 802.
Коды с обнаружением ошибок:
Код с проверкой на четность.
К отправляемым данным присоединяется бит четности (parity bit), который выбирается так, чтобы число единичных битов в кодовом слове было четным (или нечетным). Для повышения защиты от последовательностей ошибок — биты четности вычисляют не в порядке отправки данных — чередование.
Принцип обнаружения и исправления ошибок корректирующими кодами
Прежде, чем начать рассмотрение специальных корректирующих кодов, следует отметить, что любой код способен обнаруживать и исправлять ошибки, если не все кодовые слова (кодовые комбинации) этого кода используются для передачи сообщений. Нагляднее рассмотреть это на примере блочных кодов, у которых последовательность символов на выходе источника разбивается на блоки (кодовые слова, кодовые комбинации), содержащие одинаковое число символов k. При этом для двоичного кода ансамбль сообщений будет иметь объем Nр=2k. При помехоустойчивом кодировании это множество изNрсообщений отображается на множество N= 2n возможных кодовых слов, такая процедура и называется помехоустойчивым кодированием дискретных сообщений (числоn – число символов в кодовом слове после кодирования,иногда его называют длиной кодовых слов или значностью кода).
В общем случае для блочного равномерного кода с основанием код имеет возможных кодовых слов. Используемые для передачи сообщений кодовые слова из множества называют разрешенными, остальные кодовые слова измножества не используются и называются запрещенными (неразрешенными для передачи).
Рисунок 89 – Обнаружение и исправление ошибок
Способ приема заключается в том, что если принятое кодовое слово принадлежит подмножеству (i), считается переданным -е разрешенное кодовое слово. Ошибка не может быть исправлена (исправляется неверно), если переданное кодовое слово в результате искажений превращается в кодовое слово любого другого подмножества (j),(j¹i). На Рисунок 48б ошибка в запрещенном кодовом слове B1jбудет исправлена, так как это слово принадлежит подмножеству (1), приписанному к переданному разрешенному слову A1; ошибка в кодовых словах B2jили B4jне будет исправлена, так как эти слова относятся к подмножествам, приписанным к другим разрешённым кодовым словам.
Свойства кода по обнаружению и исправлению ошибок характеризуются количественно коэффициентами обнаружения Kоб и исправления ошибок Kис, которые показывают, во сколько раз уменьшается вероятность ошибки после декодирования по сравнению с её величиной на входе приемного устройства (декодера), благодаря обнаружению ошибок или их исправлению соответственно. Ошибки в кодовых словах могут иметь произвольную конфигурацию, что определяется случайным характером помех в канале связи. Число ошибочных символов в принятом кодовом слове называется кратностью ошибки t, при длине кодового слова из nсимволов она изменяется в пределах от 0 до n.
Если это вероятность ошибки кратности t³ 1 в nразрядном кодовом слове на входе декодера, а Pоб – вероятность обнаружения ошибок в декодере, то коэффициент обнаружения определяется следующим выражением
Коэффициент исправления ошибок будет определяться выражением
где Pис- вероятность исправления ошибок в декодере.
Последняя численно равна вероятности ошибок в кодовом слове, кратность которых не превышает величины кратности гарантированно исправляемых ошибок tис, то есть Pис= Pвх(£tис, n).
Коэффициент исправления кода всегда меньше коэффициента обнаружения, что является общим условием для любых корректирующих кодов.
Для реализации потенциальных возможностей кода, исправляющего ошибки, необходимо учитывать статистический характер ошибок в реальных каналах связи, в которых предполагается применение этого кода. Разбиение неразрешенных комбинаций на подмножества (i) должно выполняться таким образом, чтобы исправлялись ошибки, появление которых наиболее вероятно в данном канале связи.
В общем случае передаваемая кодовая комбинация искажается случайным образом, что определяется случайным характером помех в канале связи. В реальных системах связи при многообразии характера действующих в линии связи помех распределение кратностей ошибок в дискретном канале связи может быть самым различным. Поэтому построению декодера, исправляющего ошибки, должно предшествовать изучение статистических свойств канала связи. В качестве примера, на Рисунок 49 приведены кривые распределения кратностей ошибок Pn(t) для двух случаев: для двоичного канала с независимыми ошибками в кодовых символах p – кривая 1 (биномиальное распределение)
Pn(t) = Cntpt(1- p)n-t (1
и кривая 2 для канала, в котором передаваемое кодовое слово с одинаковой вероятностью может превратиться в другое кодовое слово данного кода (из множества N)
Pn(t) = Cnt /mn
Графики соответствуют длине кодового слова.
Рисунок 90 – Распределение кратностей ошибок
Для приведенных на Рисунок 48 распределений кратностей ошибок определим величины коэффициентов исправления для корректирующего кода с параметрами: , ( ), , исправляющего одиночные ошибки:.
Вероятность ошибки в передаваемом кодовом слове в канале с распределением кратностей ошибок Pn(t), соответствующим кривой 1(Рисунок 49), и вероятностью искажения символа кода p = 0,1 равна
Вероятность исправления ошибки (вероятность ошибки с кратностьюt=1):
В канале связи с распределением кратностей ошибок Pn(t), соответствующим кривой 2 (Рисунок 49), вероятность исправления ошибки (вероятность ошибки с кратностьюt=1) равна
где – доля ошибок, кратность которых ис из общего числа возможных ошибок mn. Тогда коэффициент исправления равен
Таким образом, один и тот же код в первом случае исправляет примерно в четыре раза больше ошибок, чем во втором. Это объясняется тем, что в первом случае наибольшее количество ошибок имееткратностьt=1 и исправляется данным кодом, у которого каждому разрешенному кодовому слову приписывается подмножество ближайших неразрешенных слов, а во втором случае наибольшее количество ошибок имееткратностьt>1, которые не исправляются данным кодом.
Очевидно, что, если в канале связи преобладают ошибки большой кратности, целесообразно к разрешенным кодовым словам приписывать подмножество таких неразрешенных слов, которые удалены от данного разрешенного на расстояние, соответствующее этим ошибкам.
Коды с исправлением ошибок
Значительно сложнее исправить ошибку сразу (без повторной передачи данных), однако в некоторых случаях и эту задачу удается решить. Для этого ещё больше увеличивают избыточность кода (добавляют «лишние» биты).
Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.
При передаче сообщения каждый передаваемый бит повторяется три раза подряд. Могли ли быть переданы без ошибок такие сообщения?
3) 111000111010111.
Как вы рассуждали?
При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:
Передавались сообщения, в которых каждый бит был утроен. При передаче произошли ошибки (не более одной в каждой тройке), и были получены следующие битовые цепочки:
3) 110000101010011.
Восстановите битовые цепочки (без утроения), которые передавались.
Код с утроением битов обнаруживает одну или две ошибки. Кроме того, если сделана одна ошибка, он позволяет исправить её, т. является помехоустойчивым.
Помехоустойчивый код — это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?
Кроме простого дублирования битов есть и другие, более сложные помехоустойчивые коды. Например, предположим, что передаются сообщения, содержащие только четыре буквы — «П», «О», «Р», «Т». Для кодирования букв используются 5-битные кодовые слова (рис.
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора различаются не менее чем в трёх битах. В этом случае говорят, что расстояние Хэмминга между кодовыми словами больше или равно трём. Например, слова «П» — 111. 11 и «О» — 11000 различаются в трёх последних битах, а слова «П» — 11111 и «Р» — 00100 — в четырёх битах (они подчёркнуты). Это позволяет обнаруживать и даже исправлять ошибки.
Для передачи данных использовался код, заданный на рис. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.
Для передачи данных использовался код, заданный на рис. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.
Для передачи данных использовался код, заданный на рис. При передаче каждого кодового слова произошло не более двух ошибок. Декодируйте сообщение, исправив ошибки: 00111 11100 11110 11000 00000 01110 11011 11100 00011 11000
Если ошибку исправить нельзя, поставьте символ «*».
В каком случае при использовании кода, заданного на рис
а) можно обнаружить ошибки, а исправить нельзя;
б) нельзя даже обнаружить ошибки?
Если все кодовые слова отличаются друг от друга не менее чем в трёх битах, такой код позволяет обнаружить одну или две ошибки. Если сделана только одна ошибка, код позволяет исправить её. Если же произошли три ошибки и более, в результате мог получиться другой правильный код, и эти ошибки обнаружить нельзя.
Следующая страница Выводы. Интеллект-карта
Cкачать материалы урока