Любой циклический (n, k ) – код может быть задан в соответствии с определением 2, порождающим многочленом g(x) или проверочным многочленом .

Знание этих многочленов позволяет построить порождающую матрицу и матрицу проверок. Для циклического (n, k ) – кода существует простой способ нахождения k линейно независимых кодовых комбинаций, образующих порождающую матрицу . Этот способ состоит в следующем. Записывается порождающий многочлен g(x) . В соответствии с определением 2 комбинация, соответствующая порождающему многочлену, принадлежит циклическому (n, k ) – коду. В соответствии с определением 1 циклические сдвиги комбинации, соответствующей g(x) , также должны принадлежать этому же коду. Алгебраически сдвиг соответствует умножению кодовой комбинации на х . Так как степень g(x) равна n-k , то подобным образом мы можем получить кодовые комбинации

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

.

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

Аналогичным образом по проверочному многочлену можно построить матрицу проверок

.

Пример 6.4. Для циклического (7,4) – кода с порождающим многочленом (см. пример 6.3.) построить порождающую матрицу.

Следовательно, порождающая матрица для данного кода имеет вид:

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

Свойство 6.1. Произведение кодовой комбинации циклического кода на произвольный многочлен дает кодовую комбинацию этого же циклического кода.

Действительно , а любое произведение такого вида равно нулю, т.е. принадлежит кодовому подпространству (раздел 6.2).

Более элементарное доказательство:

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

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

Коэффициент при х в произведении равен

Слагаемые, содержащие , появляются вследствие слагаемых в произведении , которые содержат . Но так как , т.е. , то . Равенство для можно представить в виде скалярного произведения:

В этом произведении первый вектор соответствует а(х) . Второй вектор содержит коэффициенты b(х) , расположенные в обратном порядке и сдвинутые циклически на j +1 элемент вправо.

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

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

Пример 6.5. Построить матрицу проверок для циклического (7,4) – кода из предыдущего примера.m , являющихся сомножителями двучленов и не являющихся сомножителями никаких двучленов меньшей степени. Корни этих многочленов имеют порядок 2 m -1, т.е они являются примитивными элементами поля GF(2 m). Это означает, что порождающий многочлен кода Хэмминга порождает поле GF(2 m).

Условимся в любом циклическом коде первые n-k элементов кодовой комбинации, то есть коэффициенты при использовать в качестве проверочных элементов, а последние k элементов, то есть коэффициенты при , - в качестве информационных (рис. 6.0).

a 0 a, ….., a n-1 = a 0 x 0 +a 1 x 1 + …. + a n-1 x n+1

x 0 x 1 x 2 x n-k-1 x n-k x n-2 x n-1

Голосование: 28, 5

Введение

Описание процесса цифровой связи

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

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

Говоря о кодах, контролирующих ошибки, следует различать две стратегии их использования.

1. Непосредственное исправление ошибок за счет избыточности (Forward Error Correction — FEC).
2. Обнаружение ошибок с последующими запросами на повторную передачу ошибочно принятой информации (Automatic Repeat Request — ARQ).

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

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

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

Общие сведения

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

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

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

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

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

Из данного описания можно сделать 2 вывода:

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

Линейные блоковые коды

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

Наиболее известным линейным кодом является блоковый код Хэмминга. Далее описание линейных блоковых кодов будет производиться на примере этого кода. В частности, будет рассмотрен (7,4)-код Хэмминга.

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

Вместо k бит информационного вектора в канал передается n бит кодового вектора. В этом случае говорят об избыточном кодировании со скоростью: R = n ⁄ k .

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

Описание процессов кодирования и декодирования

Исходным материалом для построения кодовых конструкций служит n -мерное двоичное векторное пространство, в котором заданы операции арифметики по модулю 2. В него вложено k -мерное линейное пространство, содержащее 2 k кодовых слов. Код С образуется с помощью 2 k комбинаций k линейно независимых базисных векторов { g 1 ,…, g k }.

Эти векторы образуют строки порождающей матрицы кода С.

Для кода C существует дуальный код C d такой, что скалярное произведение любой пары векторов, один из которых принадлежит пространству С, а другой — пространству C d , всегда равно нулю. Это значит, что векторы кода С d ортогональны векторам кода С. С другой стороны, если некоторый вектор ортогонален всем векторам кода С, то он принадлежит коду С d и наоборот. Дуальное векторное подпространство «натянуто» на n − k линейно независимые базисные векторы { h 1 ,…, h n − k }. Эти векторы образуют строки проверочной матрицы.

Рассмотрим пример порождающей и проверочной матриц (7,4)-кода Хэмминга:

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

Кодирование

Кодовое слово v и информационное слово u связаны соотношением:

где G — порождающая матрица, структура которой была описана выше.

Например, информационный вектор u = (1010) отобразится в кодовый вектор следующим образом:

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

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

G k × n = (P k ×(n − k) I k),

где I k — единичная матрица размерности k × k .

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

Роль проверочных символов и их использование будут подробно разъяснены ниже.

Декодирование

Задача декодера заключается в том, чтобы, используя структуру кода, по принятому слову r , восстановить переданный информационный вектор. Для рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок. Так как рассматриваемый код является систематическим, выразим каждый из трех проверочных символов через символы информационного вектора:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

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

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

Таким образом, из первых трех столбцов порождающей матрицы G мы получили систему трех проверочных уравнений. Если в полученной системе уравнений хотя бы одна из компонент { s 0 , s 1 , s 2 } не равна нулю, то в канале произошла ошибка.

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

H (n − k)× n = (I n − k P T k ×(n − k)).

Тогда систему проверочных уравнений можно записать в виде

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

В качестве примера рассмотрим синдромное декодирование (7, 4)-кода Хэмминга. При передаче информационного слова u = (1010) по каналу без шума r = v = (0011010) . Можем убедиться, что в этом случае синдром равен 0 .

Если, например, в кодовом слове произошла одиночная ошибка на четвертой позиции (r = (0010010)), то синдромом является четвертая строка транспонированной проверочной матрицы.

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

Ошибочный разряд	r 0	r 1	r 2	r 3	r 4	r 5	r 6
Синдром s	100	010	001	110	011	111	101

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

Разновидности ошибок

У линейных блоковых кодов имеются 3 разновидности ошибок:

1. Распознаваемая и исправляемая ошибка
   • Синдром присутствует в таблице синдромов
   • Декодер распознает и исправляет ошибку, а затем передает на приемник корректное слово
2. Распознаваемая ошибка
   • Принятое слово не соответствует ни одному из кодовых слов
   • Синдром не присутствует в таблице синдромов
   • Декодер распознает ошибку и посылает запрос на повторную передачу информационного слова.
3. Нераспознаваемая ошибка
   • Принятое слово соответствует одному из кодовых слов (не соответствующему исходному кодовому слову)
   • Синдром равен 0
   • Декодер не распознает ошибку и выдает потребителю ошибочное информационное сообщение

Заключение

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

Литература

1. Вернер М. Основы кодирования . — М.: Техносфера, 2004.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

Олег Рыбак

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

Приведем матрицу 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.
а) Производительность марковского источника. Избыточность

Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с g(х) = 1+х+х*3

Циклические коды

Циклические коды - это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей кодов Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Одним из классов циклических кодов, способность исправлять многократные ошибки, являются коды БЧХ. Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров. Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова:

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) степени r = n-k, являющийся сомножителем двучлена x n +1, и их корней. Кроме того, вводятся понятия полинома исходного сообщения. Для этих полиномов, представляющих собой, по существу, альтернативную запись чисел в двоичной системе счисления, определяются операции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все эти операции выполняются по модулю 2.

Кодовые слова представляются в виде многочленов:

Основные параметры циклических кодов

Длина кода - n; Длина информационной последовательности - k; Длина проверочной последовательности - r=n-k; Кодовое расстояние кода - d 0 ; Скорость кода - R=k/n; Избыточность кода - R?; Вероятность обнаружения ошибки (искажения) - Р ОО; Вероятность не обнаружения ошибки (искажения) - Р НО.- коэффициенты из поля GF(q).

Основные понятия и определения

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга. Кодовое расстояние кода - это наименьшее расстояние Хэмминга между различными парами кодовых слов. Основные зависимости между кратностью обнаруживаемых ошибок t 0 , исправляемых ошибок t u , исправлением стираний t c и кодовым расстоянием d 0 кода:

Стиранием называется "потеря" значения передаваемого символа в некоторой позиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим. Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q m -1 над GF(q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Результатом деления двучлена x n +1 на многочлен g(x) является проверочный многочлен h(x). При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x). Многочлен ошибок степени не более (n-1) определяется из выражения

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

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

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

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по модулю 2, а затем по модулю x n +1, если степень результата превышает степень (n-1). Примеры.

Допустим, что длина кода n=7, то результат приводим по модулю x 7 +1.

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

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

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

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

Порождающей матрицей линейного -кода называется матрица размера , строки которой – его базисные векторы.

Например,

является порождающей матрицей кода из двух слов {000, 011}.

является порождающей для кода В из примера 6.3.

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

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

Обратимся к задаче декодирования.

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

в котором обозначает скалярное произведение векторов и .

Про такой вектор мы скажем, что он ортогонален. Найдя такой вектор, мы могли бы проверять с помощью тождества (6.2), является ли принятая из канала последовательность кодовым словом.

Заметим, что (6.2) справедливо для всех кодовых слов, если оно справедливо для базисных векторов, т.е. если

где верхний индекс Т обозначает транспонирование.

Чем больше таких «проверок» мы найдем, тем, по-видимому, больше ошибок сумеем обнаружить и исправить.

Упражнение 6.4 . Докажите, что проверки образуют линейное пространство.

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

Упражнение 6.5 . Найдите размерность линейного пространства проверок.

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

Следствием этих рассуждений является теорема

Теорема. Размерность проверочного пространства линейного -кода равна .

Базис проверочного пространства запишем в виде матрицы

называемой проверочной матрицей кода.

Проверочная и порождающая матрицы связаны соотношением

Из этого соотношения мы видим, что для любого кодового слова имеет место

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

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

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

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

где – единичная матрица порядка , а – некоторая матрица размера .

Матрица вида (6.6) называется порождающей матрицей, приведенной к систематическому виду , а соответствующий код называется систематическим . Кодирование для систематического кода немного проще, чем для кода общего вида:

, (6.7)

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

Для систематического кода с порождающей матрицей в форме (6.6) проверочная матрица может быть вычислена по формуле

Упражнение 6.6 . Проверьте (6.7). Подсказка: для этого нужно подставить (6.8) и (6.6) в (6.4).

Как найти проверочную матрицу для несистематического кода?

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