Пропускная способность
Определим пропускную способность С дискретного канала связи с помехами как максимум количества информации I(X,Y) по всевозможным распределениям р(х) входа канала, т.е. C = max I(X,Y). Из определения видно, что пропускная способность канала зависит только от свойств самого канала, т.е. входного и выходного алфавитов X, У и заданного на них условного распределения вероятностей р(у\х), ,и не зависит от того источника, который подключён ко входу канала.
Пропускная способность канала имеет следующие свойства:
1. С = m a x { Н ( Y) - H(У|Х)}; 2.C≥0; 3.С = 0, тогда и только тогда, когда вход и выход канала статистически независимы. ; 4.С ≤ logm. ; 5.С = logmпри отсутствии помех в канале связи; 6.С≤ max{H(Y)} ≤ max{H(Y)}.
Помехоустойчивое кодирование.
Принципы помехоустойчивого кодирования. Кодовое расстояние. Число обнаружиеваемых и исправляемых ошибок. Коды Хемминга. Циклические коды. Обнаружение ошибок при циклическом кодировании.
Когда мы передаем сообщение от источника к приемнику, при передаче данных может произойти ошибка (помехи, неисправность оборудования и пр.). Чтобы обнаружить и исправить ошибку, применяют помехоустойчивое кодирование, т.е. кодируют сообщение таким образом, чтобы принимающая сторона знала, произошла ошибка или нет, и при могла исправить ошибки в случае их возникновения. По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
Для того чтобы можно было обнаруживать и исправлять ошибки, разрешенная комбинация должна как можно больше отличаться от неразрешенной. Если ошибки действуют независимым образом (как случайные независимые события), то вероятность преобразования одной кодовой комбинации в другую будет тем меньше, чем большим числом разрядов они различаются. Если интерпретировать кодовые комбинации как точки в пространстве, то отличие выражается в близости этих точек, т. е. в расстоянии между ними.//Кодовое расстояние- количество разрядов, которыми отличаются две кодовые комбинации, можно принять за расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации по модулю 2 и подсчитать число единиц в полученной сумме. Обозначим кодовое расстояние через d. В дальнейшем интерес будет представлять только минимальное кодовое расстояние или расстояние Хэмминга, которое обозначим через d0. Итак, у простого кода dmin=d0=1//Рассмотрим, чему равно d0 помехоустойчивого кода. При d0>2 код способен обнаруживать и исправлять ошибки. При d0=1 такой возможности нет. Нужное кодовое расстояние устанавливается введением определенного количества дополнительных разрядов в кодовую комбинацию. Обозначим число (кратность) обнаруживаемых ошибок через to, а число исправляемых ошибок — через tu. Ошибка не обнаруживается, если одна разрешенная комбинация переходит в другую разрешенную. Следовательно, для обеспечения возможности обнаружения всех ошибок кратностью до t0 включительно необходимо, чтобы кодовое расстояние определялось неравенством: d0 t0+1.
Число обнаруживаемых ошибок определяется минимальным расстоянием dmin между кодовыми комбинациями. Это расстояние называется хэмминговым. Если код используется только для обнаружения ошибок кратностью g0, то необходимо и достаточно, чтобы минимальное кодовое расстояние было равно d≥2g0+1.В этом случае никакая комбинация из go ошибок не может перевести одну разрешенную кодовую комбинацию в другую разрешенную. Таким образом, условие обнаружения всех ошибок кратностью g0 можно записать g0 dmin -1.
Чтобы можно было исправить все ошибки кратностью gи и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию dmin ≥ 2gu, Т.е. dmin ≥ 2gu+1 (1.13) .В этом случае любая кодовая комбинация с числом ошибок gи отличается от каждой разрешенной комбинации не менее чем в gи+1 позициях. Если условие (1.13) не выполнено, возможен случай, когда ошибки кратности g исказят переданную комбинацию так, что она станет ближе к одной из разрешенных комбинаций, чем к переданной или даже перейдет в другую разрешенную комбинацию. В соответствии с этим, условие исправления всех ошибок кратностью не более gи можно записать: gи (dmin-1)/2
Коды Хэмминга относятся к линейным систематическим кодам с do=3 и dо==4, в которых проверочные разряды формируются линейным преобразованием информационных разрядов. Правило нахождения проверочных разрядов является основной задачей корректирующих кодов. Это правило будем определять в виде некоторого линейного оператора R. Существуют два принципиально отличных друг от друга оператора формирования:
1. bi=Ri{aj}, i=l, 2,..., г; П. {br,}=R{a}l<k.
В первом случае каждый элемент bi проверочной части определяется своим оператором Ri .{aj} - обозначает подмножество тех информационных элементов, которые участвуют в формировании bi-го проверочного разряда. Таким образом, для нахождения r проверочных разрядов необходимо последовательное применение r различных операторов Ri (проверок).
2 Во втором случае оператор R действует сразу на все множество разрядов информационной части, определяя тем самым в целом проверочную часть кодовой комбинации. Ко второму случаю относятся циклические коды. Обнаружение и исправление ошибок кодом Хэмминга сводится к определению и последующему анализу «синдрома». Под синдромом понимают совокупность элементов, сформированных суммированием по модулю 2 принятых проверочных элементов и вычисленных проверочных элементовпо принятым информационным элементам по тому же правилу, которое применяется для их определения.
Циклические коды составляют большую группу наиболее широко используемых на практике линейных, систематических кодов. Их основное свойство, давшее им название, состоит в том, что каждый вектор, получаемый из исходного кодового вектора путем циклической перестановки его символов, также является разрешенным кодовым вектором. Принято описывать циклические коды (ЦК) при помощи порождающих полиномов G(Х)степени m = n – k, где m – число проверочных символов в кодовом слове. В связи с этим ЦК относятся к разновидности полиномиальных кодов. Операции кодирования и декодирования ЦК сводятся к известным процедурам умножения и деления полиномов. Для двоичных кодов эти операции легко реализуются технически с помощью линейных переключательных схем (ЛПС), при этом получаются относительно простые схемы кодеков, в чем состоит одно из практических достоинств ЦК.
Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же образующий полином, который использовался для кодирования. Если ошибок в принятой комбинации нет (или они такие, что передаваемую комбинацию превращают в другую разрешенную), то деление на образующий полином производится без остатка. Наличие остатка свидетельствует о присутствии ошибок. При использовании в циклических кодах декодирования с исправлением ошибок остаток от деления может играть роль синдрома. Нулевой синдром указывает на то, что принятая комбинация является разрешенной. Всякому ненулевому синдрому соответствует определенная конфигурация ошибок, которая и исправляется.
Однако, обычно в системах связи исправление ошибок при использовании циклических кодов не производится, а при обнаружении ошибок выдается запрос на повтор испорченной ошибками комбинации. Такие системы называются системами с обратной связью
Пример:
→100 :ошибка в 3-ем разряде.