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

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

Из (6.6) следует, умножение любого кодового вектора на транспонированную матрицу дает нуль, в связи с этим матрицу (6.5) называют проверочной матрицей . Кроме того, говорят, что линейный код является нуль–пространством проверочной матрицы, либо что код ортогонален проверочной матрице.

На основании соотношений (6.4) и (6.6) имеем

откуда не составляет труда получить, что проверочные символы кодового слова определены, как

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

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

Доказательство: Рассмотрим линейный код, задаваемый проверочной матрицей размерности в виде

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

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

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

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

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

Рассматривая структуру матриц и можно вынести следующее заключение. Обе матрицы состоят из множества линейно независимых векторов, поскольку наличие в их структуре единичной матрицы делает невозможным существование линейной комбинации строк с нулевой суммой. Следовательно, каждая из матриц может рассматриваться как базис некоторого линейного пространства. Более того, каждое из этих пространств является подпространством векторного пространства, состоящего из всех векторов длины . Учитывая сказанное выше, можно их «поменять ролями» и использовать в качестве порождающей, а – проверочной матрицы некоторого другого кода. Коды, связанные с таким преобразованием, называются дуальными друг другу. Таким образом, если исходным являлся кодом, то дуальным ему будет код.

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

Любой код с кодовым расстоянием , удовлетворяющим соотношению (6.8), называется кодом с максимальным расстоянием .

Замечание. Граница Синглтона (6.8) бесполезна для двоичных кодов, поскольку значительно уступает в точности границам Плоткина и Хэмминга. Однако, она играет значительную роль в случае –ичных кодов.

Пусть x1, x2, ..., xk означают слово из k информационных битов на входе кодера, кодируемое в кодовое слово C размерности n битов:

вход кодера: X =[x 1, x 2, ...,xk ]

выход кодера: C =[c 1, c 2, ..., cn ]

Пусть задана специальная порождающая матрица G n , k ,

задающая блочный код (n ,k ).

Строки матрицы G n , k должны быть линейно независимы.

Тогда разрешенная кодовая комбинация C , соответствующая кодируемому слову X :

C =x 1 g 1 + x 2 g 2 + ... + x k g k .

Систематическая (каноническая) форма порождающей матрицы G размером k xn :

Порождающая матрица систематического кода создает линейный блочный код, в котором первые k битов любого кодового слова идентичны информационным битам, а остальные r =n -k битов любого кодового слова являются линейными комбинациями k информационных битов.

Проверочная матрица H n , k имеет r xn элементов, причем справедливо:

C xH T = 0.

Это выражение используется для проверки полученной кодовой комбинации. Если равенство нулю не выполняется, то получаем матрицу-строку ||c 1 , c 2 , ..., c r ||, называемую синдромом ошибки.

Код Хэмминга. Корректирующая и обнаруживающая способности. Правила выбора соотношения между длиной кодового слова и числом информационных битов. Формирование порождающей и проверочной матриц кода Хэмминга. Толкование синдрома ошибки

Рассмотрим код Хэмминга с кодовым расстоянием d =3, позволяющий исправлять одиночные ошибки (d =2q max +1).

Число разрешенных кодовых комбинаций для кода с d =3, для кода Хэмминга строго равно 2 n /(n +1). Первые k разрядов кодовых комбинаций кода используются в качестве информационных и их число равно

k = log 2 (2 n /(n +1)] = n – log 2 (n +1).

Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, которые и определяют соответствующие коды Хэмминга: (3,1)-код, (7,4)-код, (15,11)-код и т.д. (всегда n =2 w ‑1).

Проверочная матрица H кода Хэмминга (r =n-k строк и n столбцов): для двоичного (n,k)-кода n=2 w -1 столбцов состоят из всех возможных двоичных векторов с r=n-k элементами, исключая вектор со всеми нулевыми элементами .

Легко проверить, что G xH T = 0 (нулевая матрица размером k xr элементов).

Пример. Проверим работу кода при передаче сообщения X =1011. Передаваемая кодовая комбинация будет сформирована в виде линейной комбинации (сложения по модулю 2) строк № 1, 3, 4 матрицы G 7,4:

Предположим, что на передаваемое кодовое слово C воздействовала ошибка 0000100, что привело к получению на приемной стороне слова C "=10111 10.

Тогда при перемножении C" на проверочную матрицу H T получаемматрицу-строку синдрома ошибки, которая соответствует тому столбцу проверочной матрицыH с номером бита, содержащего ошибку.

Сравнивая полученный синдром со строками H T , получаем, что ошибочен бит № 5 слева.

Декодер Хэмминга может работать в двух взаимоисключающих режимах:

Режим исправления (коррекции) ошибок (т.к. d min =3, то он позволяет исправлять одиночные ошибки);

Режим обнаружения ошибок (т.к. d min =3, то он обнаруживает ошибки кратности q £2). Если синдром не равен 0, то декодер выдает сигнал ошибки.

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

Расширенный код Хэмминга. Режимы работы декодера, корректирующая и обнаруживающая способности. Формирование кодового слова. Формирование проверочной матрицы расширенного кода Хэмминга. Толкование синдрома ошибки

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

Длины кодов увеличиваются с 2 w -1 до 2 w , что удобно с точки зрения передачи и хранения информации;

Минимальное расстояние d min расширенных кодов Хэмминга равно 4, что дает возможность обнаруживать (!) 3-кратные ошибки.

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

Рассмотрим расширение (7,4,3)-кода Хэмминга.

Каждый кодовый вектор C a получается из кодового вектораc путем добавления дополнительного разряда проверки на четностьC a = (c 1 , ..., c 7, c 8), где .

Проверочная матрица H (8,4)-кода получается из проверочной матрицы (7,4)-кода в два приема:

К матрице (7,4)-кода дописывается нулевой столбец;

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

Получаем:

При синдромном декодировании

s " = C "ÄH T ,

причем все компоненты s" должны быть равны 0.

При одиночной ошибке s"(4) = 1. По значению синдрома (младшие 3 бита) находим и исправляем (инвертируем) ошибочный бит.

При двойной ошибке компонента s"(4)= 0, а синдром отличен от нуля. В отличие от стандартного кода Хемминга такая ситуация ужеобнаруживается , но не исправляется (передается запрос на повторную передачу слова и т.п.).

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

Для исправления однократных и обнаружения двукратных ошибок;

Для обнаружения трехкратных ошибок.

Линейные коды обладают следующим свойством:

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

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

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

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

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

Образующая матрица получается путем записи в столбец k линейно-независимых слов.

Обозначим кодируемую информационную последовательность X и будем записывать ее в виде матрицы-строки ||X|| размерностью 1* k , например:

||X||=||11001||, где k=5 .

Один из способов построения образующей (порождающей) матрицы следующий: Она строится из единичной матрицы ||I|| размерностью k*k и приписанной к ней справа матрицы добавочных (избыточных) разрядов ||МДР|| размерности k*r .

где при k =4

Такая структура ОМ обеспечивает получение систематического кода.

Порядок построения матрицы МДР будет рассмотрен ниже.

7.4 Порядок кодирования

Кодовое слово КС получается путем умножения матрицы информационной последовательности ||Х|| на образующую матрицу ||ОМ||:

Умножение выполняется по правилам матричного умножения: (ТАК наТАК)

Надо только помнить, что сложение здесь ведется по модулю 2.

допустим, образующая матрица

||ОМ||= 0010 011

и вектор-строка информационной последовательности

Так как множимая матрица имеет всего одну строку, умножение упрощается. В этом случае следует поставить в соответствие строкам образующей(порождающей) матрицы ||ОМ|| разряды матрицы информационной последовательности ||X|| и сложить те строки образующей(порождающей) матрицы, которые соответствуют единичным разрядам матрицы ||Х||.

Заметим, что ||KC|| = ||X, ДР||,

где ||X||- информационная последовательность (т.к. умножается на единичную матрицу ||I|| ),

а ||ДР|| - добавочные разряды, зависящие от матрицы добавочных разрядов ||МДР|| :

|| ДР ||= || Х || * || МДР||

7.5 Порядок декодирования

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

Искажение можно описать с помощью следующей формулы:

|| ПКС || = ||КС || + ||ВО ||,

где ||ВО|| - вектор ошибки - матрица-строка размерностью 1* n , с 1 в тех позициях, в которых произошли искажения.

Декодирование основано на нахождении так называемого опознавателя или синдрома ошибки -матрицы-строки ||ОП|| длиной r разрядов (r - количество добавочных или избыточных разрядов в кодовом слове).

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

Опознаватель находят по следующей формуле:

||ОП|| = ||ПКС||* ||ТПМ||,

где ||ПКС||- принятое и, возможно, искаженное кодовое слово;

||ТПМ||,- транспонированная проверочная матрица, которая получается из матрицы добавочных разрядов ||МДР|| путем приписывания к ней снизу единичной матрицы:

Пример ||ТПМ||:

Поскольку ||ПКС|| = ||КС|| + ||BO||, последнюю формулу можно записать в виде:

||ОП|| = ||КС|| * ||ТПМ||+||ВО|| * ||ТПМ||.

Рассмотрим первое слагаемое.

||КC|| - матрица-строка, причем первые k разрядов - информационные.

Докажем теперь, что произведение кодового слова ||КС|| на ||ТПМ|| приводит к получению нулевой матрицы ||0||.

Поскольку ||КС|| - матрица-строка, возможен упрощенный порядок умножения матриц, рассмотренных выше.

Следовательно, первое слагаемое в

||ОП|| = ||КС|| * ||ТПМ|| + ||ВО|| * ||ТПМ||

всегда равно нулю и опознаватель полностью зависит от вектора ошибки ||ВО||.

Если теперь подобрать такую проверочную матрицу ТПМ , а значит и МДР , чтобы разным векторам ошибки соответствовали разные опознаватели ОП, то по этим опознавателям можно будет находить вектор ошибки ВО, а значит и исправлять эти ошибки.

Соответствие опознавателей векторам ошибки находится заранее путем перемножения векторов исправляемых ошибок на ТПМ;

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

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

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

Приведем матрицу H к треугольному виду:

Система уравнений:

Информационные символы:

Защитные символы:

Порождающая матрица

Информационные символы и соответствующие им защитные:

N	x 1 x 2 x 3 x 4	x 5 x 6 x 7	Вес

Есть черный ящик. L – совокупность преобразований в нем . L подействовала на X.

X 1 и x 2 не взаимодействуют между собой, поэтому это линейная система.

Св-во линейности кодов – сумма двух разрешенных кодовых слов равна разрешенному слову.

Билет 5.
а) Связь между ценностью информации и энтропией
б) Принципы построения линейных кодов. Декодирование по синдрому

Предположение, что множество выходных последовательностей канала является -мерным векторным пространством над полем GF(q}, а множество Y(n,R) входных последовательностей (код) является подпространством размерности nR. существенно облегчает декодирование. В этом случае Y(n,R) является подгруппой аддитивной группы , и, следовательно, может быть разложено на смежные классы по подгруппе . Пусть - все элементы (кодовые слова), тогда все элементы множества будут представлены с помощью стандартного расположения

(1)

(здесь через 0 обозначен единичный элемент группы ).

Каждая строка в (1) образующими элементами соответствующих смежных классов. Если в качестве образующих 0, е 1 , е 2 , ..., е s взяты элементы минимального веса в своем смежном классе, то любая последовательность из i-гo столбца отличается от у в меньшем числе разрядов, чем. от любого другого слова i¹K. Если в смежном классе, содержащем x, существует несколько элементов минимального веса, то найдется столько же кодовых слов, отличающихся от x в одном и том же наименьшем числе разрядов.

Для доказательства предположим, что x=y i +е, где е - элемент минимального веса в своем смежном классе. Очевидно, d{y i . x)=w (e) и d(y k ,x)=w(y k -y i -e). Если е- единственный элемент минимального веса, тоd(y i , x)K¹ i. Если таких элементов несколько (например, w(y j +e)=w(e)) , то d(y i , x)=d(y k , x) то при условии, что y k = y j –y i . Следовательно, для каждого элемента y j +e минимального веса в смежном классе, содержащем e, найдется слово y k = y j –y i , которое находится от у на расстоянии d(y k , i)=w(e).

Таким образом, для всех последовательностей x, входящих в 1-й столбец стандартной расстановки, условная вероятность Р(x\y i) максимальна. Если x находится в смежном классе с несколькими элементами минимального веса, то условная вероятность Р(x\у i)=Р(x\у k) и остается максимальной для всех у k , находящихся на одинаковом расстоянии от x

Правило декодирования может быть сформулировано следующим образом: найти выходную последовательность канала xÎ в (1) и считать, что была передана та последовательность y i ÎY(n.R), которая находится в том же столбце, что и x.

Очевидно, это правило совпадает с декодированием по максимуму правдоподобия и, следовательно, является оптимальным.

Правило декодирования линейного кода можно сформулировать так: после того. как выходная последовательность x; найдена в (1), определить наиболее вероятный вектор ошибки e, отыскивая образующий элемент того смежного класса, который содержит x; переданную последовательность найти из соотношения y=x-e.

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

где e - образующий элемент смежного класса, содержащего x. По найденному синдрому S найти e; определить у из соотношения у= x-e.

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

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

Билет 6.
а) Энтропия и ее свойства

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

e-энтропии – это min кол-во инфы, кот. необх. передать по каналу, чт. восст. сообщение с заданной точностью при заданном распределении p(x) источника.

Модель передачи непр. сообщ-я:

d 2 = e 2 – ошибка при восст-нии сообщения y(t). Нужно установить связь м\д x(t) и x’(t), такую, чтобы x’ несло как можно меньшую инфу об x, но обеспечивало заданную точность.

He = min I (x, x’)

Каждому интервалу ставится в соотв-ие число. x = (b-a)/2 n .

чем > n, тем > интервалов и > точность.

I(x,x’)=H(x’) – H(x’/x) -взаимная инфа по опред-ию.

H(x’/x) = 0 т.к. значение случайной величины x определяет значение случайной величины x’ .

(“при фиксированном x ”)

I(x,x’)= H(x’) - кличество взаимной информации между множествами x и x’ равно энтропии x’ .

(опр-ся инф-ой ёмкостью регистра).

Пусть х равномерно распр. на интевале тогда все x’ равновероятны.

log[(b-a)/ x]=n величина энтропии ~ длине регистра

Надо обеспечить точность d 2 (среднеквадр. ошибка):

При min кол-ве взаимной инфы. Связь м\б x и x’ опр-ся кол-вом и длиной интервалов x. Надо их выбрать так, чт. x’ был распределён равномерно.

Пусть x и x’ непрерывны.

(1) x = x’ – n , где n – погрешн. кот. получается в рез-те апроксимации x x’-ом.

n=0, n 2 =d 2 e =e 2 –заданная ошибка

He =H(x)-max(H(n)), H(n) будет max при гауссовском распр. n

H(n)=/2

Источник чаще всего им. гауссовское распр. с d 2 , тогда: H(n) = /2 = log(d 2 x /d 2 n)/2 = log(d 2 x /e 2)/2 [бит/отсчёт]

Если за 1с. перед-ся 2F отсчётов, то Нe t = 2FHe = F*log(d 2 x /e 2) [бит/c]

По т.Шеннона для гаусс. канала: Нe t < F log(1+q 2) [бит/c]

б) Дискретизация непрерывных сообщений. Теорема Котельникова. Пространство сигналов.

Билет 7.
а) Взаимная информация и ее свойства

Кол-во информации, кот. Yj несет об Xi = кол-ву информации, кот. Xi несет об Yj. И эта информация называется взаимной информацией м-у Yj и Xi: . И она м.б. >0,<0,=0, в зависимости от средней информации.

Для каждой пары (Xi,Yj ) соответствует свое кол-во информации, а т.к. Xi и Yj – случайные величины, то и это кол-во информации случайно. Поэтому мы можем ввести понятие средней информации м-у множествами:

Отдельное состояние – это пара чисел .

I(X,Y)–полная взаимная информация (всегда ≥0, когда системы независимы).

Сделаем тождественные преобразования:

Тогда, взаимную информацию м. записать:

, (*)

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

Поэтому энтропии Н (Х ) и H (Y ) можно интерпретировать как информацию, которая поступает в канал связи, а условные энтропии H (X/Y ), H (Y/X ) как информацию, которая рассеивается в канале.

Согласно теореме I (Х ,Y )≥0 мы получаем из (*):

Когда X и Y независимы, т.е. взаимн. инф-я =0

б) Адаптивная дискретизация непрерывных сообщений

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

если энергия функции конечна.

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

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

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

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

Таким образом, по счетному множеству коэффициентов можно с определенной

точностью восстановить соответствующую функцию можно заменить передачей последовательности коэффициентов . Указанную последовательность можно интерпретировать как вектор в n - мерном Евклидовом пространстве с координатами квадрат длины которого .

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

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

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

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

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

,

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

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

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

Билет 8.
а) Эргодические источники. Производительность источника при независимых символах

б) Относительная энтропия непрерывных случайных величин

Относительной (дифференциальной) энтропией случайной величины Х называется величина

В частности, если интервал d = 1, то

Выясним физический смысл относительной энтропии H(X) .

Пусть источник сообщений вырабатывает последовательность значений случайной величины Х . После квантования получим последовательность значений случайной величины X ’ :

X i 1 ,X i 2 …..X ik …..X in .

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

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

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

Аналогично относительную энтропию можно определить через объем V T , занимаемый типичными последовательностями:

В отличие от дискретного случая относительная энтропия может быть не только положительной, но и отрицательной, а также равной нулю . Чем больше объем V T , занимаемой типичными последовательностями, тем больше неопределенность того, какая из них появится. Единичному объему (V T =1) соответствует энтропия (неопределенность), равная нулю (H(X) =0). Это значение принимается за начало отсчета относительной энтропии.

В частности, относительная энтропия случайной величины с равномерным на единичном интервале (d = 1 ) распределением равна нулю:

В этом случае область n -мерного пространства, занимаемая типичными последовательностями, примерно совпадает с областью определения всех последовательностей и имеет форму куба единичного объема (V T = d n =1 ).

Билет 9.
а) Производительность марковского источника. Избыточность

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

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков - этот подход применяется в основном на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков - такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• исправление ошибок (англ. forward error correction ) применяется на физическом уровне.

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

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

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

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

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

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

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

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

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

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

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

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

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

Линейные пространства

Порождающая матрица

Это соотношение устанавливает связь между векторами коэффициентов и векторами . Перечисляя все векторы коэффициентов можно получить все векторы . Иными словами, матрица G порождает линейное пространство .

Проверочная матрица

Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей .

Пусть - ортогональное подпространство по отношению к C , а H - матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

.

Свойства и важные теоремы

Минимальное расстояние и корректирующая способность

Коды Рида-Соломона

Преимущества и недостатки линейных кодов

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

Оценка эффективности

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

Граница Хемминга и совершенные коды

Пусть имеется двоичный блоковый (n ,k ) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга ):

.

Коды, удовлетворяющие этой границе с равенством, называются совершенными . К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.

Энергетический выигрыш

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

Wikimedia Foundation Википедия

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Циклический код … Википедия

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

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

- (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передаче информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью является малая плотность значимых… … Википедия

Код с малой плотностью проверок на чётность (LDPC код от англ. Low density parity check code, LDPC code, низкоплотностный код) используемый в передачи информации код, частный случай блокового линейного кода с проверкой чётности. Особенностью… … Википедия

структура - (framework): Логическая структура для классификации и организации сложной информации .