Линейные корректирующие коды

 

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

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

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

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

t ≤ d – 1 обнаружимы, а кратности t < или 2t + 1 ≤ d исправимы. Кратность ошибки – это количество единиц в векторе .

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

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

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

…………………………….

или в матричном виде H = 0, где - проверочная матрица, а кодовое слово размера n – = (x₁, …, x_n). Элементы матрицы и кодового слова прини-мают значения только 0 или 1, при этом суммирование производится по моду-лю два (). В этой системе уравнений количество строк m выбирается меньше количества столбцов для того, чтобы система уравнений имела не единственное решение, каждое из которых является разрешенным кодовым словом. Каждое из уравнений уменьшает количество независимых переменных x_i на единицу. Поэтому количество независимых переменных, значения которых и место рас-положения можно выбирать произвольно, равно . Если в качестве неза-висимых переменных выбираются первые k символов x₁,…,x_k, то код называет-ся систематическим. Эти символы называются информационными в отличие от защитных x_k+1,…,x_n, причем защитные символы линейно выражаются через информационные. Таким образом, количество разрешенных кодовых слов равно 2^k, а общее количество входных канальных кодовых слов равно 2ⁿ.

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

,

где и по определению разрешенного кодового слова.

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

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

Поскольку система уравнений линейна (Н – линейный оператор), то спра-ведливы следующие преобразования:

отсюда , т.к по определению разрешенного кодового слова .

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

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

Решение принимается в пользу кодового слова , которое являет-ся разрешенным.

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

Декодирование по минимуму расстояния, по синдрому и по максимуму апостериорной вероятности эквивалентны.

Эквивалентность декодирования по минимуму расстояния и по синдрому следует из равенства , которое показывает, что расстояние между и измеряется весом (количеством единиц) вектора .

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

Рассмотрим некоторые свойства линейных кодов. Количество векторов в каждом из подмножеств, соответствующих различным значениям синдрома, равно количеству разрешенных кодовых слов 2^k. Для любых двух векторов и , принадлежащих одному и тому же подмножеству, справедливы равенст-ва и . Складывая эти равенства и преобразуя суммы с учетом линейности системы уравнений (линейности оператора H) получим

,

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

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

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

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

 

Декодирование по синдрому:

 

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

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

Поскольку система уравнений линейна (Н – линейный оператор), то спра-ведливы следующие преобразования:

отсюда , т.к по определению разрешенного кодового слова .

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

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

Решение принимается в пользу кодового слова , которое являет-ся разрешенным.

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

Декодирование по минимуму расстояния, по синдрому и по максимуму апостериорной вероятности эквивалентны.

Эквивалентность декодирования по минимуму расстояния и по синдрому следует из равенства , которое показывает, что расстояние между и измеряется весом (количеством единиц) вектора .

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

Рассмотрим некоторые свойства линейных кодов. Количество векторов в каждом из подмножеств, соответствующих различным значениям синдрома, равно количеству разрешенных кодовых слов 2^k. Для любых двух векторов и , принадлежащих одному и тому же подмножеству, справедливы равенст-ва и . Складывая эти равенства и преобразуя суммы с учетом линейности системы уравнений (линейности оператора H) получим

,

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

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

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

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

Рассмотрим свойства матрицы H, которые гарантируют заданное значение минимального кодового расстояния. Для каждого кодового слова уравнение …… означает, что сумма некоторого подмножества столбцов матрицы….. равна 0. Приумножении матрицы …… на вектор-столбец …… из матрицы выбираются столбцы, которым соответствуют единицы в векторе ….. Поскольку минимальное кодовое расстояние равно минимальному весу кодовых слов, то должно существовать, по крайней мере, одно подмножество, состоящее из d столбцов матрицы H, сумма которых равна 0. С другой стороны, не может существовать ни одного подмножества из d-1 или менее столбцов, сумма которых равна 0. Если рассматривать столбцы матрицы … как векторы, то можно сказать, что для кода с кодовым расстоянием, равным …, все подмножества из ….. столбцов должны быть линейно независимыми. Это утверждение составляет одну из фундаментальных теорем о групповых кодах. Оно позволяет находить кодовое расстояние … группового кода, заданного матрицей …, а также строить матрицы..,гарантирующие заданное минимальное кодовое расстояние.

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

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

.

При декодировании ошибка отсутствует, когда .

 

Доп. Инфа:

 

Свойства энтропии

Энтропия поскольку p_i удовлетворяет неравенству 0 1. Энтропия H(X)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных — с вероятностью, равной нулю. При этом имеется в виду, что p_ilog p_i=0.

При равномерном распределении (p_i= ) энтропия H(X)=logm_x

Докажем, что это максимальное значение энтропии. Используя равенство =1, можно выполнить следующие тождественные преобразования:

Н(Х)-logm_X=

Для оценки выражения log воспользуемся неравенством lnz z—1, положив z= .

 

 

 

Заменяя на , получим

где log e —модуль перехода. Отсюда

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

.

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q= 0,5.

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

 

а)Энтропия и её свойства.

Энтропия равна количеству информации,

которое необходимо для определения состояния одного раз­ряда.

Величина является характеристикой источника сообщений и называется энтропией.

Из лабораторной 1:

Предельные возможности определяются энтропией. Если она

Энтропия:

p- вер-ть появления еденицы в массиве

Энтропия это количество информации которое приходится на один разряд.

Из лабораторной 2:

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

воспр-я перед-ого сообщ-я.

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

Свойства энтропии

Энтропия поскольку p_i удовлетворяет неравенству 0 1. Энтропия H(X)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных — с вероятностью, равной нулю. При этом имеется в виду, что p_ilog p_i=0.

При равномерном распределении (p_i= ) энтропия H(X) max и определяется как H(X)=logm_x

Докажем, что это максимальное значение энтропии. Используя равенство =1, можно выполнить следующие тождественные преобразования:

Н(Х)-logm_X=

Для оценки выражения log воспользуемся неравенством lnz z—1, положив z= .

 

 

 

 

Заменяя на , получим

где log e —модуль перехода. Отсюда

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

.

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q= 0,5.

 

 

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

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

,

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

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

при ,

а отдельная функция называется нормированной, если

.

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

 

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

.

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

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

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

.

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

.

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

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

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

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

,

 

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

,

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

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

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

 

Билет 7.
а) Взаимная информация и ее свойства
б) Адаптивная дискретизация непрерывных сообщений

1.Взаимная информация и её свойства.

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

. (4)

Поскольку сложная система случайным образом приходит в то или иное состояние, определяемое парой чисел (x_i,y_j), то I (xi,y_j) будет случайной величиной, которую можно усреднить по всему множеству состояний. В результате почленного усреднения (4) получим выражение для средней (полной) взаимной информации:

,

где I(y,x)=

 

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

Поэтому энтропии Н (Х) и H (У) можно интерпретировать как информацию, которая поступает в канал связи, а условные энтропии H (X | Y), H (Y | X) как информацию, которая рассеивается в канале. В [1] доказано, что 1(Х, У)≥0.

При выполнении указанного неравенства из (5) следует, что

Условную энтропию можно представить в виде

где величина называется частной условной энтропией. Она характеризует неопределенность состояния системы А в случае, когда известно состояние y_j наблюдаемой системы В. Зафиксировав состояние y_j системы В, мы тем самым изменяем комплекс условий, при которых может реализоваться событие x_i. Это обнаруживается как изменение вероятности реализации события x_i (i = ) (имеет место статистическая зависимость). Если до изменения условий указанная вероятность была равна безусловной (полной) вероятности p (X_i), то после изменения условий она стала равной условной вероятности p (x_i | y_j). При отсутствии статистической зависимости H (X | y_j)= H (X), поскольку P (x_i | y_j)= p (x_i).

 

Таблица 1

X y	x1	x2	p (yj)
y1 y2	0.5 0.25	0.25	0.5 0.5
p (xi)	0.75	0.25

 

Таблица 2

X y	x1	x2
y1 y2	0.5	0.5

 

При наличии статистической зависимости энтропия H (X | y_j) может оказаться как меньше, так и больше Н (Х). Напомним, что для энтропии H (X | Y) всегда справедливо неравенство H (X | Y)≤ H (X).

В качестве примера вычислим энтропии Н (Х), H (X | Y), H (X | y_j) и взаимную информацию I (Х, У), когда системы А и В описываются двумерным распределением p (x_i, y_j), заданным в виде табл. 1.

Вычисленные значения условной вероятности записаны в табл.2.

Используя записанные в таблицах значения вероятностей, полу

чим

Отсюда