Дискретные источники сообщений; теория кодирования

Лекции по теории информации А.А. Соловьев Оглавление 1. Введение 2 2. Количественные информационные характеристики дискретных источников сообщений 2.1 Энтропия и ее свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Условная информация. Условная энтропия. . . . . . . . . . . . . . . . . . . . . . . . 2.3 Кодирование дискретных источников неравномерными кодами . . . . . . . . . . . 2.4 Оптимальные неравномерные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 8 10 16 3. Теоремы кодирования для каналов связи 3.1 Средняя взаимная информация между источниками . . . . . . . . . . . . . . 3.2 Постановка задачи кодирования в дискретном канале . . . . . . . . . . . . . . 3.3 Информационная емкость дискретных каналов без памяти . . . . . . . . . . . 3.4 Методы декодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Помехоустойчивое кодирование в ДСК . . . . . . . . . . . . . . . . . . . . . . . 3.6 Прямая и обратная теорема кодирования для дискретного канала без памяти 3.7 Теорема Шеннона для ДСК канала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 19 24 27 29 32 34 35 4. Конспект лекций по теории кодирования 4.1 Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Циклические коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 39 42 . . . . . . . . . . . . . . . . . . . . Глава 1 Введение Информация, наряду с материей и энергией, является первичным понятием и в строгом смысле не может быть определена. В повседневной жизни под информацией обычно понимают совокупность сведений об окружающем мире, являющихся объектом хранения передачи и преобразования. Знаки и сигналы, организованные в последовательности, несут информацию в силу однозначного соответствия с объектами и понятиями реального мира, например: предметы и слова их обозначающие. Информация, основанная на однозначной связи знаков и сигналов с объектами реального мира, называется семантической или смысловой. Информация, заключенная в характере следования знаков (порядке и взаимосвязи) называется синтаксической. В курсе теории информации изучаются проблемы синтаксического уровня, касающиеся создания теоретических основ построения систем связи, основные показатели функционирования которых были бы близки к предельно возможным. Рассмотрению подлежат вопросы доставки получателю информации как совокупности знаков. При этом полностью игнорируется смысловое и прагматическое содержание информации. Синтаксическая информация также имеет практическую ценность потому, что интересующая в конечном итоге семантическая информация заключена в доставляемой получателю последовательности знаков или сигналов. Введем некоторые понятия и определения. Информация, представленная в какой-либо форме называется сообщением. Для того, чтобы сообщение можно было передать получателю, необходимо воспользоваться некоторым физическим процессом, способного с той или иной скоростью распространяться от источника к получателю сообщения. Изменяющийся во времени физический процесс, отражающий передаваемое сообщение, называется сигналом. Сигнал является функцией времени и их делят на четыре типа: 1) непрерывный или аналоговый сигнал (т.е. аналогичный порожденному процессу); 2) дискретный по времени сигнал или последовательность отсчетов (временной интервал между соседними отсчетами ∆t = tk+1 − tk называется шагом дискретизации); 3) дискретный по уровню или квантованный сигнал (принимает лишь разрешенные значения уровня, отделенные друг от друга шагом квантования ∆x = xk+1 − xk ); 4) дискретный по уровню и по времени. Дискретная информация удобней для обработки, но непрерывная информация встречается чаще. Как например модем, который переводит цифровые данные в звуковой сигнал и наоборот. При дискретизации сигнала часть информации, как правило, теряется. Теорема об отсчетах Найквиста – Шеннона – Котельникова гласит, что для точной дискретизации сигнала частота дискретизации должна быть не менее, чем в два раза выше наибольшей частоты сигнала. Совокупность технических средств, используемых для передачи сообщений от источника к потребителю информации называется системой связи. Приведем пример системы связи: Принятое Принятый Сообщение сообщение Получатель Источник Сигнал сигнал −−−−→ Приемник −−−−−−−→ −−−−−−−→ Передатчик −−−−→ Канал −−− сообщений сообщения x   Источник шума 3 1. Сообщения могут быть разных типов: последовательностью букв или цифр, а также одной или более функцией времени. 2. Передатчик перерабатывает некоторым образом сообщения в сигналы определенного типа. 3. Канал – это комплекс технических средств, обеспечивающих передачу сигналов от передатчика к приемнику по линии связи. Линией связи называется среда, используемая для передачи сигнала от приемника к передатчику (пара проводов, коаксиальный кабель, световод, область распространения радиоволн). Если сигнал на входе и выходе канала непрерывен по уровню (типа 1) или 2)), то канал называется непрерывным. Канал называется дискретным, если на его входе и выходе присутствуют сигналы, дискретные по уровню (типа 3) или 4)). В общем случае в процессе передачи сигнал искажается шумом, что соответствует наличию источника шума. 4. Приемник восстанавливает сообщение по принимаемому сигналу. Процесс преобразования сообщения в сигнал, осуществляющийся в передатчике, называются кодированием и обратный ему процесс, реализуемый в приемнике, – декодированием. Теория информации (ТИ) исследует методы кодирования для экономного представления сообщений различных источников сообщений и для надежной передачи сообщений по каналам связи с шумом. В основе ТИ лежит статистическое описание источников сообшений и понятие количества информации, содержащейся в сообщении. Теория информации является разделом статистической теории связи. На основе ТИ можно ответить на вопросы о предельных возможностях реальных систем и определить в какой мере проектируемая система уступает теоретически возможной. Датой рождения ТИ является 1948 г. В этот год вышла основополагающая статья Клода Шеннона "Математическая теория связи". Начиная с этого времени ТИ интенсивно развивалась в немалой степени благодаря работам и наших соотечественников Колмогорова, Добрушина, Харкевича, Хинчина и других. При подготовке лекций были использованы источники [1- 5]. Глава 2 Количественные информационные характеристики дискретных источников сообщений 2.1 Энтропия и ее свойства Источник сообщений может в каждую единицу времени случайным образом принять одно из возможных состояний. Каждому состоянию источника ставится в соответствие условное обозначение в виде знака. Совокупность знаков u1 , u2 , . . . uN соответствующих всем N состояниям источника называется его алфавитом, а количество состояний N объемом алфавита. Под элементарным дискретным сообщением будем понимать символ uj , генерируемый источником. В течение времени T источник порождает дискретное сообщение в виде последовательность символов. Отдельные состояния источника выбираются им чаще, другие реже. Поэтому каждое состояние uj принимается дискретным источником с определенной вероятностью p(uj ). Определение 1. Дискретным источником сообщений будем называть конечное множество U вместе с заданным на нем распределением вероятностей p(u), x ∈ U и будем обозначать его символом {U, p(u)}. То есть, под дискретным источником сообщений понимается конечное дискретное вероятностное пространство. Пусть X = {x1 , . . . xM } и Y = {y1 , . . . , yN } – два конечных множества. Символом XY будем обозначать декартово произведением множеств X и Y , элементами которого являются упорядоченные пары (xi , yj ), xi ∈ X, uj ∈ Y, i = 1, . . . , M j = 1, . . . , N . Если X = Y то произведение XY будем обозначать через X 2 . Аналогичным образом определяются произведения более чем двух множеств. В частности, X n – это множество всех последовательностей длины n элементов множества X. Пусть на множестве XY задано совместное распределение вероятностей p(x, y), которое каждой паре (xi , yj ), xi ∈ X, yj ∈ Y , сопоставляет вероятность p(xi , yj ). Соотношения X p1 (xi ) = p(xi , yj ), i = 1, . . . , M, yj ∈Y p1 (yj ) = X p(xi , yj ), j = 1, . . . , N, xj ∈X задают распределения вероятностей p1 (x) и p2 (y) на множествах X и Y . Таким образом, при задании источника {XY, p(x, y)} фактически задаются еще два источника {X, p1 (x)} и {Y, p2 (y)}. Источники {X, p1 (x)} и {Y, p2 (y)} будем называть совместно заданными источником {XY, p(x, y)}. Если распределение вероятностей на произведении двух множеств X и Y удовлетворяют условию p(xi , yj ) = p1 (xi )p2 (yj ) для всех xi ∈ X, yj ∈ Y, то источники {X, p1 (x)} и {Y, p2 (y)} называются статистически независимыми. В противном случае, говорят, что эти источники статистически зависимы. В каждом элементарном сообщении содержится для получателя информация о состоянии источника сообщений. При определении количественной меры информации не учитывается ее смысловое содержание. Количество информации, содержащейся в дискретном сообщении измеряется величиной исчезнувшей в ходе эксперимента неопределенности. Поэтому меру неопределенности можно 5 рассматривать как количественную меру информации содержавшейся в сообщении. Определение меры неопределенности обсудим на примере источника U с равновероятными состояниями. Мера должна удовлетворять ряду естественных условий. С увеличением объема выбора, то есть объема алфавита источника, мера неопределенности должна возрасти. Кроме того, вводимая мера неопределенности должна обладать свойством аддитивности: если два независимых источника X и Y с объемами алфавитов M и N объединены в один источник, реализующий пары состояний (xi , yj ), то неопределенность объединенного источника должна быть равной сумме неопределенностей исходных источников. Мера неопределенности в случае равновероятности состояний является функцией объема источника и поскольку объем алфавита объединенного источника равен M N , то искомая функция должна удовлетворять условию f (M N ) = f (M ) + f (N ). Функцией, удовлетворяющей этому соотношению, является логарифмическая функция. Перечисленные требования выполняются, если в качестве меры неопределенности источника с равновероятными состояниями принять логарифм объема алфавита источника с основанием большим единицы H(U ) = log N . Ясно, что а) с ростом N величина H(U ) монотонно возрастает; б) если объем алфавита источника равен N = 1, то H(U ) = log 1 = 0, то есть неопределенность отсутствует; в) величина H(U ) обладает свойством аддитивности log M N = log M + log N . Основание логарифма определяет единицу количества информации. Если основание равно 2, то единица количества информации называется битом и представляет собой информацию, содержащуюся в одном дискретном сообщении источника равновероятных сообщений с объемом алфавита, равным двум. Если основание равно 10, то получаем единицу, называемую дитом. С основанием e единица информации называется натом. Данная мера неопределенности была предложена Хартли в 1928 году. В общем случае, когда вероятности различных состояний источника {U, p(u)} с объемом N не одинаковы, степень неопределенности конкретного состояния зависит не только от объема алфавита источника, но и от вероятности этого состояния. В таком случае количество информации, содержащейся в одном дискретном сообщении uk , имеет смысл определить как функцию вероятности p(uk ) появления этого дискретного сообщения I(uk ) = − log p(uk ) = log 1 . p(uk ) Знак (−) выбирается с тем, чтобы I(uk ) > 0. В случае достоверного сообщения, когда p(uk ) = 1, имеем I(uk ) = 0. Количество информации, содержащейся в дискретном сообщении источника является случайной величиной, так как зависит от степени неожиданности (вероятности) реализуемого источником сообщения. Среднее количество информации, содержащееся в отдельном сообщении, называется энтропией источника N n 1 o X H(U ) = M log p(ui ) log 1p(ui ) . = p(u) i=1 (2.1) Чем больше энтропия источника, тем больше степень неопределенности реализуемых им сообщений в среднем, то есть более неопределенным является ожидание сообщений. Впервые мера (2.1) 6 была предложена Клодом Шенноном в его фундаментальной работе "Математические основы теории связи опубликованной в 1948 году. Название "энтропия" не случайно, так как соотношение (2.1) совпадает с выражением для энтропии Больцмана термодинамической системы. Рассмотрим теперь свойства энтропии: 1. Энтропия любого дискретного источника неотрицательна, H(U ) > 0. Равенство возможно лишь в том случае, когда источник генерирует одно единственное сообщение с вероятностью, равной единице. 2. Пусть N – объем алфавита дискретного источника. Тогда H(U ) 6 log N . Причем равенство имеет место только в том случае, когда все сообщения равновероятны. H(U ) − log N = N X p(uk ) log k=1 Так как ln x < x − 1 при x > 0 и ln x = H(U ) − log N = log e N X G N k=1 k=1 X X 1 1 − log N N P (uk ) = p(uk ) log . p(uk ) p(uk )N log x log e , p(uk ) ln k=1 то N h i X 1 1 6 log e p(uk ) −1 = N p(uk ) N p(uk ) k=1 N h i X 1 − p(uk ) = log e(1 − 1) = 0 . = log e N k=1 то есть Р(U ) 6 log N . 3. Свойство аддитивности – энтропия нескольких совместно заданных статистических дискретных источников сообщений равна сумме энтропий исходных источников. Энтропия совместного источника {XY, p(x, y)} равна H(XY ) = N M X X p(xi )p(yj ) log i=1 j=1 = N X k=1 1 = p(xi )p(yj ) N M X X 1 1 p(yj ) log p(xi ) + = H(X) + H(Y ) . p(xi ) log p(yj ) p(x ) p(y i j) j=1 i=1 i=1 M X Предложение 2.1. Для любых двух вероятностных распределений p(u) и q(u) на алфавите U = {u1 , . . . , uN } справедливо неравенство N X i=1 N p(ui ) log X 1 1 p(ui ) log 6 , p(ui ) q(u i) i=1 которое переходит в равенство тогда и только тогда, когда p(ui ) = q(ui ) для всех ui ∈ U . Доказательство. N X p(ui ) log i=1 6 log e N N N X X X 1 1 q(ui ) q(ui ) p(ui ) log p(ui ) log p(ui ) ln − = = log e 6 p(ui ) i=1 q(ui ) p(u ) p(u i i) i=1 i=1 N N h q(u ) i hX i hX i p(ui ) p(ui ) = log e(1 − 1) = 0 . q(ui ) − log e − 1 = log e p(ui ) i=1 i=1 i=1 N X 7 Следствием этого предложения является, в частности, свойство 2. Избыточностью источника дискретных сообщений с энтропией H и объемом алфавита N называется величина, равная H 1− , log N где log N – максимально возможное значение энтропии при данном объеме алфавита. Избыточность показывает, какая доля возможной при заданном объеме алфавита неопределенности (энтропии) не используется источником. В частности, избыточность английского текста составляет 50%, ихбыточность русского текста – 70% . Пример 1. Энтропия двоичного источника U = {0, 1}, P (0) = p, P (1) = 1 − p равна H(U ) = p log2 1 1 + (1 − p) log2 = h(p) . p 1−p Функция h(p) называется двоичной энтропией. Здесь 0 6 h(p) 6 1 и переходит в равенство при p = 21 . В последнем случае источник называется двоичным симметричным источником (ДСИ) и каждый символ на выходе ДСИ содержит один бит информации. Пример 2. Некто задумал целое число в интервале от 0 до 3. Опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать только "Да" или "Нет". Сколько вопросов мы должны задать, чтобы узнать задуманное число, или иначе, какое количество информации мы должны получить, чтобы полностью снять начальную неопределенность. Решение. Исходами в данном случае являются: A1 ="задуман 0"; A1 ="задумано 1"; A2 ="задумано 2"; A3 ="задумано 3". Естественно предположить, что вероятности "задумать число"у всех чисел одинаковы: N = 4, следовательно, p(Ai ) = 1/4, log2 p(Ai ) = −2 и H = 2 битам. Для полного снятия неопределенности опыта (угадывания задуманного числа) нам необходимы 2 бита информации, то есть ответы на 2 вопроса с двумя возможными вариантами ответов (да – нет). Количество информации должно быть равно числу вопросов с бинарными вариантами ответов, которые необходимо задать, чтобы полностью снять неопределенность задачи. Убедимся, что два полученных ответа полностью снимают неопределенность и, тем самым, позволяют узнать задуманное число. x>1 Question 1 Answer 1 no x>0 Question 2 Answer 2 yes x>2 no x=0 yes x=1 no yes x=2 x=3 Таким образом, действительно, два полученных ответа решают задачу. 8 2.2 Условная информация. Условная энтропия. Пусть {X, p(x)} и {Y, p(y)} совместно заданы источником {XY, p(x, y){. Зафиксируем некоторое элементарное сообщение yj ∈ Y , p(yj ) 6= 0 и рассмотрим условное распределение p(x|yj ) на X. Для каждого сообщения xi ∈ X источника {X, p(x)} определена условная собственная информация I(xi |yj ) = − log p(xi |yj ) , элемента сообщения xi при фиксированном сообщении yj . Функцию I(x|yj ), x ∈ X, можно рассматривать как случайную величину на вероятностном пространстве {X, p(x|yj )}. Ее математическое ожидание H(X|yj ) = M X i=1 p(xi |yj )I(xi |yj ) = − M X i=1 p(xi |yj ) log p(xi |yj ) называется условной энтропией источника {X, p(x)} относительно сообщения yj ∈ Y . В свою очередь, условную энтропию H(X|y), y ∈ Y , можно рассматривать как случайную величину на вероятностном пространстве {Y, p(y)}. Определение 2. Математическое ожидание H(X|Y ) случайной величины H(X|y), определенной на вероятностном пространстве {Y, p(y)} называется условной энтропией источника X относительно источника Y H(X|Y ) = M H(X|y) = N X p(yj )H(X|yj ) = j=1 =− M X N X i=1 j=1 p(yj )p(xi |yj ) log p(xi |yj ) = − M X N X i=1 j=1 p(xi , yj ) log p(xi |yj ) . Рассмотрим свойства условной энтропии. 1. H(X|Y ) 6 H(X), Равенство имеет место тогда и только тогда, когда источники X и Y статистически независимы. H(X|Y ) − H(X) = − = M X N X i=1 j=1 6 log e h p(xi , yj ) log M X N X i=1 j=1 p(xi , yj ) log p(xi |yj ) + M X p(xi ) log p(xi ) = i=1 M X N i X 1 p(xi ) + log p(xi ) = p(xi , yj ) log 6 p(xi |yj ) p(xi |yj ) i=1 j=1 M X N M X N i i hX h p(x ) X i p(xi , yj ) = log e(1 − 1) = 0 . p(xi )p(yj ) − − 1 == log e p(xi , yj ) p(xi |yj ) i=1 j=1 i=1 j=1 i=1 j=1 M X N X Равенство возможно тогда и только тогда, когда p(x|y) = p(x), то есть когда x и y независимы для всех x ∈ X и y ∈ Y . Таким образом, результат опыта Y может уменьшить неопределенность опыта X. 2. Имеет место соотношение, H(XY ) = H(Y ) + H(X|Y ), называемое свойством аддитивности энтропии. В самом деле, с помощью равенства p(x, y) = = p(y)p(x|y), находим H(XY ) = − M X N X i=1 j=1 p(xi , yj ) log p(xi |yj ) − M X N X i=1 j=1 p(xi , yj ) log p(yj ) = H(X|Y ) + H(Y ). 9 Аналогично, пользуясь соотношением p(x, y) = p(x)p(y|x) можно получить равенство H(XY ) = H(X) + H(Y |X) . 3. Теорема о невозрастании информации при отображении. Теорема 2.1. Пусть задан источник {X, p(x)} и на нем определено отображение, ϕ : X → Y . P p(x). Пусть H(X) и H(Y ) – Это отображение определяет источник {Y, p(y)}, где p(y) = x : ϕ(x)=y энтропии источников X и Y , тогда H(Y ) 6 H(X) . Знак равенства имеет место тогда и только тогда, когда отображение ϕ(x) обратимо, то есть ϕ является взаимно однозначным отображением X на Y . Доказательство. Совместное распределение p(x, y) на произведении множеств XY задается соотношением p(x, y) = p(x)p(y|x), где p(y|x) = 1, если y = ϕ(x) и p(x, y) = 0, если y 6= ϕ(x). Тогда либо log p(y|x) = 0, либо p(y|x) = 0. Поэтому H(Y |X) = − M X N X i=1 j=1 p(xi )p(yj |xi ) log p(yj |xi ) = 0 . Из аддитивности и неотрицательности энтропии получим, что H(Y ) 6 H(Y ) + H(X|Y ) = H(X) + H(Y |X) = H(X) . Энтропия сохранится тогда и только тогда, когда H(X|Y ) = 0. Поэтому для всех y ∈ Y имеем H(X|y) = 0, значит, p(x|y)I(x|y) = −p(x|y) log p(x|y) = 0 для всех x ∈ X при каждом y ∈ Y . Тогда для каждого y ∈ Y существует единственный x ∈ X такой, что p(x|y) = 1. Последнее равенство выполняется, если ϕ(x) = y, то есть отображение ϕ обратимо. В случае H(X|Y ) = 0 будем говорить, что источник Y однозначно определяет источник X. 4. Пусть {XY Z, p(x, y, z)} вводит три совместно заданных источника X, Y, Z и пусть I(x|y, z) = − log p(x|y, z) есть условная собственная информация при фиксированной паре сообщений y, z, где Число p(x|y, z) = P H(X|Y Z) = − X p(x, y, z) . x∈X p(x, y, z) p(x, y, z) log p(x|y, z) x∈X y∈Y z∈Z называется условной энтропией источника X относительно пары источников Y, Z. С помощью Предложения 2.1 доказывается следующее неравенство H(X|Y Z) 6 H(X|Y ) . Равенство выполняется в том и только в том случае, когда p(x|y, z) = p(x|y) для всех (x, y, z) ∈ XY Z, 10 то есть когда при данном сообщении y сообщения x статистически независят от z. X XX 1 1 H(X|Y Z) = p(x, y, z) log 6 = H(X|Y ) . p(x, y, z) log p(x|y, z) p(x|y) x∈X y∈Y z∈Z x∈X z∈Z y∈Y В частности, верно неравенство H(X|Y ) 6 H(X) . Это неравенство обобщается на случай n совместно заданных источников. Рассмотрим источник {X1 , . . . , Xn , p(x(1) , . . . , x(n) )}. Тогда для любых s и m, 1 6 s 6 m 6 i, выполняется неравенство H(Xi |Xi−1 . . . Xi−s ) 6 H(Xi |Xi−1 . . . Xi−m ) . 5. Свойство аддитивности допускает обобщение. Если {X1 , . . . , Xn , p(x(1) , . . . , x(n) )} – совместно заданный источник, тогда H(X1 , . . . , Xn ) = H(X1 ) + H(X2 |X1 ) + · · · + H(Xn |Xn−1 . . . X1 ) . Из свойства 4 следует, что H(X1 , . . . , Xn ) 6 n X H(Xi ) i=1 и равенство возможно тогда и только тогда, когда источники {Xi , pi (x(i) } статистически независимы, то есть p(x(1) , . . . , x(n) ) = n Y pi (x(i) ) , i=1 где pi (x(i) ) = X X p(x(1) , . . . , x(n) ) . k6=i x(k) ∈Xk то Если источники {Xi , pi (x(i) )} совпадают с источником {X, p(x)} и статистически независимы, H(X n ) = nH(X) . 2.3 Кодирование дискретных источников неравномерными кодами Определение 3. Дискретным источником без памяти (ДИБП) называется источник сообщений такой, что для любых n = 1, 2, . . . и любой последовательности и любой последовательности (x(1) , . . . , x(n) ), x(i) ∈ X, имеет место равенство p(x(1) , . . . , x(n) ) = n Y p(x(j) ) . j=1 Обозначим через A некоторое множество, состоящее из D, D > 1, элементов: A = {a1 , . . . , aD }. Назовем его алфавитом кода источника. Элементы алфавита A будем называть кодовыми символами. Последовательности кодовых символов будем называть кодовыми словами, а любое семейство кодовых слов – кодом над алфавитом A. Пример 3. Пусть A = {0, 1}. Тогда множества M = {011, 0101, 11, 10} и M = {00, 01, 10, 11} являются двоичными кодами объема 4. 11 Определение 4. Код называется равномерным, если все его слова имеют одинаковую длину m. Это число называется длиной кода. Если хотя бы два кодовых слова имеют различные длины, то код называется неравномерным. Пример 4. Количество различных D-ичных последовательностей длины m равно Dm . Количество различных слов неравномерного кода с максимальной длиной кодовых слов m равно D(Dm − 1)/(D − 1). Определение 5. Кодированием сообщений источника X посредством кода называется отображение (необязательно взаимно однозначное) множества сообщений в множество кодовых слов. Примером неравномерного кода является код Шеннона-Фэно. При кодировании по методу Шеннона-Фэно алфавит расположенный в порядке убывания вероятностей появления символов, разбивается на две группы таким образом, чтобы сумма вероятностей появления символов в каждой группе была приблизительно одинаковой. Каждая группа в свою очередь также разбивается на две по такому же принципу. Операция продолжается до тех пор, пока в каждой группе не останется по одному символу. Каждый символ обозначается двоичным числом, последовательные цифры которого (нули и единицы) показывают в какую группу попал данный символ при очередном разбиении. В коде Шеннона-Фэно часто встречающиеся буквы кодируются относительно короткими двоичными символами, а редкие – длинными. Основной характеристикой неравномерного кодирования является количество символов, затрачиваемых при кодировании одного элементарного сообщения. Обозначим через mi длину слова, кодирующего сообщение xi ∈ X. Пусть p(xi ) – вероятность этого сообщения. Тогда X m(X) = mi p(xi ) xi ∈X есть средняя длина кодовых слов, кодирующих источник сообщений {X, p(x)}. Предположим, что неравномерными кодами кодируется сообщения длины n, то есть кодируется источник сообщений {X n , p(x)}. Определение 6. Число R= m(X n ) n называется средней скоростью неравномерного кодирования посредством двоичного кода при разбиении последовательности сообщений на блоки длины n. Пример 5. Равномерный Неравномерный Xi p(xi ) mi код код x1 1/4 000 00 2 x2 1/4 001 01 2 x3 1/8 010 100 3 x4 1/8 011 101 3 x5 1/16 100 1100 4 x6 1/16 101 1101 4 x7 1/16 110 1110 4 x8 1/16 111 1111 4 Оба кода осуществляют побуквенное кодирование. Энтропия источника сообщений равна 2, 75. Скорость кодирования в первом случае равна 3 бит на элементарное сообщение, во втором случае – 2.75 бит на элементарное сообщение. 12 Пример 6. Предположим, что источник порождает сообщения x1 , x2 , x3 , x4 и эти сообщения кодируются кодовыми словами 0, 01, 10, 011 соответственно. Кодовый алфавит состоит из двух символов 0 и 1. Пусть на выходе источника появилось следующее сообщение x2 x3 x2 x1 . На выходе кодера возникает последовательность 0110010. Эта последовательность допускает несколько способов декодирования. Кроме правильного декодирования возможны варианты: x4 x1 x2 x1 и x4 x1 x1 x3 . Коды, в которых ни одно слово не является началом другого называются префиксными. Префиксные коды являются кодами со свойством однозначного декодирования. Пример 7. Код 0, 01, 011 не является префиксным, но является однозначно декодируемым. Определение 7. Скоростью создания информации источником (X, p(x)) при неравномерном кодировании называется наименьшее число H такое, что для любого R > H найдется n (длина кодируемых сообщений) и неравномерный код со средней скоростью кодирования R, который допускает однозначное декодирование. Будет доказано, что скорость кодирования при неравномерном кодировании, как и при равномерном кодировании, равна энтропии источника элементарных сообщений. Как и ранее нужно доказать прямую и обратную теоремы. Первая из них утверждает, что при всех R > H(X) найдется n и однозначно декодируемый неравномерный код со скорость кодирования R, а вторая будет утверждать, что для любого R < H(X) не существует однозначно декодируемого кода ни при каком n. Теорема 2.2. Предположим, что однозначно декодируемый двоичный код состоит из M слов длины которых равны m1 , . . . , mM и кодовый алфавит двоичный. Тогда M X 2−mi 6 1 . i=1 Доказательство. Пусть L – произвольное положительное число. Имеем M X i=1 2−mi
L = M X i1 =1 ··· M X 2−(mi1 +···+miL ) . (2.2) iL =1 В выражении в правой части равенства каждое слагаемое соответствует каждой возможной последовательности из L кодовых слов. Сумма mi1 + · · · + miL равна суммарной длине соответствующей последовательности кодовых слов. Если через Aj обозначить число последовательностей из L кодовых слов, имеющих суммарную длину j, то (2.2) можно переписать в виде M X 2−mi i=1
L = Lm X Aj 2−j , j=1 где m – максимальное из чисел m1 , . . . , mM . Так как 2j – максимальное количество различных последовательностей длины j, то Aj 6 2j . Поэтому M X 2−mi i=1
L 6 Lm для всех возможных L. Поскольку слева стоит экспоненциальная функция, а справа – линейная функция переменной L, это неравенство может выполняться тогда и только тогда, когда M X i=1 2−mi 6 1. 13 Удобное описание префиксных кодов дают специальные графы, называемые кодовыми деревьями: 2-ичным деревом называется граф, в котором нет петель и в котором из каждого узла выходит не более 2 ребер и каждый узел, кроме корня дерева, входит только одно ребро. Каждому из ребер, выходящему из узла, сопоставляется один символ двоичного кодового алфавита. Различным ребрам, выходящим из одного узла, сопоставляются различные символы. Узлы дерева, отстоящие от корня на i ребер, образуют ярус порядка i. Порядком дерева называется максимальный из порядков его узлов. Узел, из которого не выходит ни одного ребра, называется концевым. Наконец, код является префиксным, если кодовые слова соответствуют только концевым узлам дерева. Теорема 2.3. (Неравенство Крафта.) Для того, чтобы существовал двоичный префиксный код с длинами кодовых слов m1 , m2 , . . . , mM необходимо и достаточно, чтобы M X 2−mi 6 1 . (2.3) i=1 Доказательство. Приведем здесь доказательство необходимости, отличное от приведенного в Теореме 2. Заметим, что максимальное количество узлов на ярусе j равно 2j . Пусть m = max{m1 , . . . . . . , mM }. Рассмотрим концевой узел порядка mi . Этот узел отстоит от яруса m на m − mi ребер и, следовательно, исключает из этого яруса 2m−mi возможных узлов. Так как количество узлов, исключаемых из яруса m всеми концевыми узлами порядков m1 , . . . , mM , не может превосходить максимального количества узлов на этом ярусе, то M X 2m−mi 6 2m (см. Рис. 2.1) . i=1 После деления обеих частей неравенства на Dm получаем (2.3). 2m−mi m 1 1 mi 1 1 Рис. 2..1: Достаточность. При выполнении (2.3) дерево с концевыми узлами порядков m1 , . . . , mM может быть построено. Предположим, что среди этого набора порядков число s встречается ровно αs раз, s = 1, . . . , m. Тогда M X i=1 2−mi = m X s=1 αs 2−s 6 1 . 14 Перепишем это неравенство следующим образом: i−1 X αs 2−s + αi 2−i + s=1 m X αs 2−s 6 1 . s=i+1 Тогда αi 6 2i − i−1 X s=1 αs 2i−s − m X s=i+1 αs 2i−s 6 2i − i−1 X αs 2i−s . (2.4) s=1 Применим метод математической индукции. Убедимся, что дерево, содержащее α1 концевых узлов порядка 1 может быть построено. Так как из (2.3) следует, что α1 2−1 6 1, то α1 6 2. Максимально возможное количество концевых узлов порядка 1 равно 2 и α1 6 2. Поэтому дерево с α1 концевым узлами порядка 1 может быть построено. Предположим, что дерево с αs концевыми узлами порядка s, s = 1, . . . , i − 1, может быть построено. Докажем, что к этому дереву можно добавить еще αiP концевых узлов порядка i. Если i−1 верно предположение индукции, то из яруса порядка i исключается s=1 αs 2i−s возможных концевых узлов (каждый узел из яруса порядка s исключает из яруса порядка i 2i−s возможных узлов). Так как P i−s максимальное количество возможных концевых узлов на этом уровне равно 2i , то 2i − i−1 s=1 αs 2 есть количество свободных узлов на ярусе i. Из (2.4) следует, что количество αi узлов на ярусе i, которые должны быть добавлены, не превосходит количества свободных узлов. Следовательно, к дереву с αs концевыми узлами порядка s, s = 1, . . . , i − 1, могут быть добавлены αi концевых узлов порядка i. Перейдем к доказательству теоремы Шеннона. Докажем два вспомогательных утверждения, относящихся к побуквенному кодированию произвольных источников. Пусть {X, p(x)}, X = (x1 , . . . , xM ) – произвольный дискретный источник и PM пусть m(X) = i=1 mi p(xi ) – средняя длина 2-ичного кода, слова которого длиной mi сопоставляются элементарным сообщениям xi . Теорема 2.4. Для любого неравномерного кода со свойством однозначного декодирования верно неравенство m(X) > H(X) . Доказательство. Среднюю длину кодовых слов m(X) представим в виде m(X) = M X p(xi ) log 2mi . i=1 Рассмотрим разность H(X) − m(X) = − M X p(xi ) log p(xi ) + M X i=1 i=1 p(xi ) log 2−mi = M X p(xi ) log i=1 2−mi . p(xi ) Воспользуемся неравенством ln x < x − 1 при x > 0. В результате получим, что H(X) − m(X) 6 log e (см. Теорему (3)). M   2−mi X
2−mi − 1 6 0 . − 1 = log e p(xi ) p(xi ) i=1 i=1 M X (2.5) 15 Равенство в (2.5) возможно тогда и только тогда, когда p(xi ) = 2−mi , i = 1, . . . , M . Таким образом, если элементарных сообщений являются целыми отрицательными степенями P вероятности −mi = 1, то для соответствующего 2-ичного неравномерного кода имеет место равендвойки и M 2 i=1 ство m(X) = H(X) . Коды, для которых средняя длина кодовых слов равна наименьшему возможному значению, называются оптимальными. Теорема 2.5. Существует 2-ичный неравномерный код со свойством однозначного декодирования, для которого m(X) 6 H(X) + 1 . Доказательство. Пусть mi – наименьшее целое число, удовлетворяющее неравенству m′i > I(xi ), где I(xi ) = − log p(xi ) – собственная информация сообщения xi , i = 1, . . . , M . Ясно, что I(xi ) 6 m′i 6 I(xi ) + 1 . Поскольку M X M X ′ 2−mi 6 i=1 i=1 2−I(xi ) = M X p(xi ) = 1 , i=1 то по теореме 3 существует 2-ичное дерево с концевыми вершинами порядков m′1 , . . . , m′M . Соответствующий код будет иметь среднюю длину m(X) = M X m′i p(xi ) 6 H(X) + 1 . i=1 Пусть кодируются сообщения длины n ДИБП и H(X n ) – энтропия источника {X n , p(x)}. Замечание к теореме 4. Для любого 2-ичного кода, однозначно декодирующего последовательность из X n , среднее число символов, приходящихся на одно сообщение, удовлетворяет неравенству R= m(X n ) H(X n ) > . n n Замечание к теореме 5. Существует 2-ичный код, однозначно декодирующий последовательности из X n , для которого верно неравенство R= m(X n ) H(X n ) 1 6 + . n n n Теорема 2.6. (Обратная теорема кодирования.) Для любого кода, однозначно кодирующего последовательности сообщений длиной n ДИБП , средняя скорость кодирования R удовлетворяет неравенству R > H(X). Доказательство. В самом деле, согласно Замечанию к теореме 4 имеем R> nH(X) H(X n ) = = H(X) . n n 16 Теорема 2.7. (Прямая теорема кодирования.) Пусть ε – произвольное положительное число. Существует n и однозначно декодируемый 2-ичный код, кодирующий последовательности сообщений длиной n ДИБП {X, p(x)}, для которого верно неравенство R < H(X) + ε . Доказательство. Так как H(X n ) = nH(X), согласно Замечанию к теореме 5 существует однозначно декодируемый 2-ичный код скоростью кодирования R, не превосходящим H(X) + 1/n. Выбирем n0 так, чтобы 1/n0 6 ε, тогда для всех n > n0 будем иметь R < H(X) + ε. 2.4 Оптимальные неравномерные коды Оптимальным называется код, средняя длина кодовых слов которого равна минимально возможной. В простейшем случае, когда вероятности элементарных сообщений источника {X, p(x)}, X = {x1 , . . . , xM } являются целыми отрицательными степенями двойки p(xi ) = 2mi , i = 1, . . . , M любой 2-ичный код со свойством однозначно декодируемости является оптимальным, так как средняя длина кодовых слов равна m(X) = H(X) (см. Теорему 4). В таком коде сообщению xi ставится в соответствие слово длины mi . Всякое дерево с набором концевых вершин порядков m1 , . . . , mM и указанным правилом соответствия дает оптимальный код. Будем предполагать, что p(x1 ) > p(x2 ) > · · · > p(xM ) . Ограничимся рассмотрением только префиксных кодов. Лемма 2.1. В оптимальном коде слово, соответствующее наименее вероятному сообщению, имеет наибольшую длину. Доказательство. Пусть mi – длина кодового слова сообщения xi ∈ X, и m – средняя длина кодовых слов m(X) = M X mi p(xi ) . i=1 Предположим, что в оптимальном коде mi > mM для некоторого i < M . Рассмотрим код, в котором i-е и M -е кодовые слова исходного кода заменены одно другим. Средняя длина m′ для этого кода удовлетворяет соотношению m′ = m − p(xi )mi − p(xM )mM + p(xi )mM + p(xM )mi = m − (mi − mM )(p(xi ) − p(xM )) < m , что противоречит предположению об оптимальности кода. Лемма 2.2. В оптимальном двоичном префиксном коде два наименее вероятных сообщения кодируются словами одинаковой длины, которые, можно считать, различаются только в последнем знаке, одно из них оканчивается нулем, а другое – единицей. 17 Доказательство. Обозначим через uj слово, кодирующее сообщение xj . Пусть uM – слово наибольшей длины оптимального кода. Тогда существует по крайней мере еще одно слово, скажем ui , такой же длины оптимального кода. В противном случае единственное слово наибольшей длины кода может быть укорочено без нарушения декодируемости и, тем самым, получим меньшую среднюю длину кодовых слов. Кодовые слова ui и uM должны отличаться в последнем знаке. В противном случае длины кодовых слов можно уменьшить, сохраняя однозначную декодируемость, и получить при этом меньшую среднюю длину кодовых слов. Можем считать, модифицируя кодовое дерево, что mM − 1 первых символов у них совпадают. Покажем теперь, что эти слова кодируют наименее вероятные сообщения. Предположим противное, что i < M − 1. Тогда mi = mM > mM−1 . В этом случае среднюю длину кода можно было бы уменьшить, заменив слово ui на uM−1 и uM−1 на ui . Следовательно, это предположение не верно и наибольшую длину имеют слова uM−1 и uM . Рассмотрим новый источник сообщений X ′ , состоящий из M − 1 элементарных сообщений с вероятностями ( p(xi ), i = 1, . . . , M − 2; p(x′i ) = p(xM−1 ) + p(xM ), i = M − 1 . {x′1 , . . . , x′M−1 } Любой декодируемый префиксный код для источника X ′ может превратиться в декодируемый код для источника X приписыванием к кодовому слову, кодирующему сообщение x′M−1 , символы 0 и 1 для получения слов, кодирующих сообщения xM−1 и xM . Лемма 2.3. Если оптимален однозначно декодируемый префиксный код для источника X ′ , то оптимален, полученый из него префиксный код для источника X. Доказательство. Обозначим через m′ среднюю длину кодовых слов префиксного не обязательно оптимального кода источника X ′ . Тогда средняя длина m кодовых слов для источника X m= M X i=1 M−1 X i=1 mi p(xi ) = M−2 X mi p(xi ) + mM−1 p(xM−1 ) + mM p(xM ) = i=1 m′i p(x′i ) − m′M−1 [p(xM−1 ) + p(xM )] + mM−1 p(xM−1 ) + mM p(xM ) = (2.6) m′ + p(xM−1 )[mM−1 − m′M−1 ] + p(xM )[mM − m′M−1 ] = m′ + p(x′M−1 ) . Здесь учтено, что длины m′i , i = 1, 2, . . . , M − 1,, кодовых слов для источника X ′ связаны с длинами mi , i = 1, . . . , M кодовых слов для источника X следующим соотношением ( mi = m′i , i = 1, . . . , M − 2; mM = mM−1 = m′M−1 + 1 . Из (2.6) следует, что m и m′ отличаются на константу p(x′M−1 ), которая не зависит от выбора кодовах слов. Покажем, что, строя декодируемый код для источника X ′ с минимальным значением m′ , мы получаем декодируемый код для источника X с минимальным значением m. Обозначим через mопт и m′опт средние длины оптимальных кодов для источников {X, p(x)} и ′ {X , p(x′ )}. Для оптимального кода источника {X ′ , p(x′ )} имеем mопт 6 m = m′опт + p(x′M−1 ). (2.7) Модифицируем оптимальный код источника {X, p(x)}, удаляя последние символы 0 и 1 в кодовых словах максимальной длины и объединяя соответствующие им сообщения в одно сообщение, получим код для источника {X ′ , p(x′ )}, для которого верно соотношение mопт = m′ + p(x′M−1 ) > m′опт + p(x′M−1 ) (2.8) 18 Из (2.7) и (2.8) следует, что mопт = m′опт + p(x′M−1 ) . Таким образом, задача построения оптимального префиксного кода сводится к задаче построения оптимального префиксного кода для источника, содержащего на одно сообщение меньше. В этом источнике снова можно выделить два наименее вероятных сообщений и, объединяя их, получить новый источник, содержащий теперь уже на два сообщения меньше, чем исходный. Продолжая эту процедуру, можно дойти до источника, содержащего всего два сообщения, оптимальным кодом для которого являются 0 для одного сообщения и 1 для другого. Описанный метод построения префиксного кода называется методом Хаффмена. Глава 3 Теоремы кодирования для каналов связи 3.1 Средняя взаимная информация между источниками Пусть X и Y – два дискретных множества. Рассмотрим источник {XY, p(x, y)}, алфавит которого состоит из всевозможных пар (x, y) ∈ XY . Задание источника XY определяет также источники {X, p(x)} и {Y, p(y)}, где X X p(x) = p(x, y); p(y) = p(x, y) . y∈Y x∈X Кроме того, для каждого из сообщений y ∈ Y и x ∈ X, для которых p(x) 6= 0 и p(y) 6= 0, определены условные распределения вероятностей p(x|y) и p(y|x), а следовательно, и условные источники {X, p(x|y)} и {Y, p(y|x)}. Пусть I(x) = − log p(x); I(y) = − log p(y) собственная информации I(x|y) = − log p(x|y); I(y|x) = − log p(y|x .) и условная собственная информация сообщений x ∈ X и y ∈ Y . Определение 8. Количеством информации о сообщении y ∈ Y , содержащейся в сообщении x ∈ X, называется величина I(y; x) = log p(y|x) . p(y) Так как p(x, y) = p(x|y)p(y) = p(y|x)p(x), то p(x, y) p(y|x) p(x|y) = = . p(x) p(x)p(y) p(y) Поэтому количество информации о сообщении y ∈ Y в сообщении x ∈ X равно количеству информации о сообщении x ∈ X в сообщении y ∈ Y , или I(x; y) = I(y; x) = log p(x, y) . p(x)p(y) На этом основании I(x; y) называют количеством взаимной информации между сообщениями x и y или просто взаимной информацией между сообщениями x и y. Отметим, что в отличии от I(x) взаимная информация I(x; y) может принимать и отрицательные значения в случае, если p(x|y) < p(x), то I(x; y) < 0. Взаимная информация между сообщениями обладает следующими свойствами: 1. Если сообщения x и y независимы, то есть p(x, y) = p(x)p(y), то сообщение y не дает никакой информации о сообщении x. В этом случае I(x; y) = 0. 2. Если сообщение x влечет сообщение y, то есть p(y|x) = 1, тогда I(y; x) = I(y) (количество информации о сообщении y в сообщении x равно собственной информации сообщения y). Количество взаимной информации будем рассматривать как случайную величину на источнике {XY, p(x, y)}. 20 Определение 9. Математическое ожидание случайной величины I(x; y) на источнике {XY, p(x, y)} называется средним количеством взаимной информации или просто средней взаимной информацией между источниками {X, p(x)} и {Y, p(y)} I(X; Y ) = X p(x, y) log x∈X y∈Y p(x, y) . p(x)p(y) Теорема 3.1. Средняя взаимная информация между источниками X и Y удовлетворяет соотношению XX p(y|x) 0 6 I(X; Y ) 6 p(x, y) log , pb(y) y∈Y x∈X где pb(.) любое другое распределение вероятностей на множестве сообщений Y . В нижней границе равенство достигается тогда и только тогда, когда источники {X, p(x)} и {Y, p(y)} статистически независимы. Доказательство. Нижняя граница находится с помощью неравенства ln x 6 x − 1 следующим образом: XX p(y) = −I(X; Y ) = p(y|x)p(x) log p(y|x) y x h p(y) i XX XX p(y) = log e p(y|x)p(x) ln = 6 log e p(y|x)p(x) p(y|x) p(y|x) y x y x nXX o XX = log e p(x)p(y) − p(y|x)p(x) = 0 y x y x Равенство справедливо тогда и только тогда, когда p(x, y) = p(x)p(y) для всех x ∈ X и y ∈ Y . Верхняя граница для I(X; Y ) вытекает из соотношения: I(X; Y ) = X p(y) log y XX 1 1 − p(y|x)p(x) log p(y) p(y|x) y x (3.1) и предложения 2.1„ в котором утверждается, что X y p(y) log X 1 1 6 , p(y) log p(y) p b (y) y причем равенство достигается тогда и только тогда, когда pb(y) = p(y) для всех y ∈ Y . Рассмотрим теперь источник {XY P Z, p(x, y, z)}, который порождает различные условные и безусловные источники. Так p(x, y) = P z∈Z p(x, y, z) является безусловным распределением вероятностей на парах (x, y) ∈ XY , p(x) = y∈Y p(x, y) – безусловное распределение вероятностей на X. Далее, p(x, y |z) = p(x, y, z) , p(z) 6= 0 p(z) – условное распределение вероятностей на XY при заданном фиксированном сообщении z ∈ Z и p(y |x) = p(x, y) p(x, y, z) , p(x) 6= 0, p(y |xz) = , p(x, z) 6= 0 p(y) p(x, z) – условные распределения вероятностей на сообщениях y ∈ Y при фиксированном x ∈ X и (x, z) ∈ XZ соответственно. 21 Введем условную взаимную информацию I(y; z |x) между сообщениями y ∈ Y и z ∈ Z при данном сообщении x ∈ X: I(y; z |x) = I(y|x) − I(y|x, z) == log p(y |x, z) p(y |x) (3.2) и взаимную информацию между парой сообщений (y, z) ∈ Y Z и сообщением x ∈ X: I((y, z); x) = I(y, z) − I((y, z)|x) (3.3) Воспользовавшись свойством аддитивности собственной информации, получим I(x, y) = − log p(x, y) = − log[p(x)p(y|x)] = I(x) + I(y|x) и I((x, y)|z) = − log p(x, y|z) = − log p(x, y, z) p(x, z) p(x, y, z) = − log − log = I(x|z) + I(y|x, z) . p(z) p(z) p(x, z) Отсюда, а также из (3.2) и (3.3) находим или I((x, y); z) = I(x, y) − I((x, y)|z) = I(x) + I(y|x) − I(x|z) − I(y|x, z) = I(x; z) + I(y; z|x) (3.4) I((x, y); z) = I(y; z) + I(x; z|y) . Эти соотношения называются свойством аддитивности собственной взаимной информации. Определение 10. Математическое ожидание случайной величины I(x; y|z) источника {XY Z, p(x, y, z)} называется средней взаимной информацией между источниками X и Y относительно источника Z и обозначается через I(X; Y |Z) I(X; Y |Z) = M I(x; y|z) = X p(x, y, z) log x,y,z p(x|y, z) X X p(x|yz) = . p(x, y|z)p(z) log p(x|z) p(x|z) z x,y Для источника {XY Z, p(x, y, z)} определено также количество взаимной информации I((x, y); z) между парой сообщений (x, y) ∈ XY и сообщением z ∈ Z. Определение 11. Математическое ожидание случайной величины I((x, y); z) на источнике XY Z представляет собой среднюю взаимную информацию ежду источником XY и источником Z I(XY ; Z) = X x,y,z p(x, y, z) log p((x, y)|z) . p(x, y) Из свойства аддитивности (3.4) следует, что I(XY ; Z) = I(X; Z) + I(Y ; Z|X) = I(Y ; Z) + I(X; Z|Y ), а также из свойства (3.3) следует, что I(XY ; Z) = H(XY ) − H(XY |Z) = H(Z) − H(Z|XY ) . Одно из важнейших свойств средней взаимной информации состоит в том, что она не увеличивается при преобразовании. Пусть ϕ(·) некоторое преобразование, отображающее множество X на другое множество, скажем Z, то есть Z = ϕ(X). Предположим также, что задан источник {XY, p(x, y)} и, тем самым, 22 определена средней взаимной информации I(X; Y ). Преобразование ϕ(·) определяет источник {ZY, p(z, y)}, для которого X p(x, y) . p(z, y) = x:ϕ(x)=z Поэтому средняя взаимная информация I(Z; Y ) определена для каждого отображения ϕ(·) и принимает значения, определяемое выбором ϕ(·). Теорема 3.2. Для любого отображения Z = ϕ(X) источника X в источник Z I(X; Y ) > I(Z; Y ) , причем равенство имеет место всегда, когда отображение обратимо, то есть каждому элементу z ∈ Z соответствует единственный элемент x ∈ X. Доказательство. Рассмотрим множество XY Z. Так как при выбранном сообщении x ∈ X сообщение z ∈ Z однозначно определено и, следовательно, не зависит от сообщения y ∈ Y , то p(z|x, y) = p(z|x) (3.5) или p(x, y, z) = p(x, y)p(z|x) для всех (x, y, z) ∈ XY Z. При заданном x ∈ X с вероятностью 1 имеем z = ϕ(x), то есть ( 1, если z = ϕ(x) , p(z|x) = 0, если z 6= ϕ(x) . Из условия (3.5) следует, что I(z; y|x) = log p(z|x, y) =0 p(z|x) для всех (x, y, z) ∈ XY Z, для которых p(x, y, z) 6= 0, а следовательно, I(Z; Y |X) = 0. Отсюда следует, что I(XZ; Y ) = I(X; Y ) + I(Z; Y |X) = I(X; Y ) . С другой стороны, в силу неотрицательности средней взаимной информации I(X; Y |Z) имеем I(XZ; Y ) = I(Z; Y ) + I(X; Y |Z) > I(Z; Y ). Поэтому I(X; Y ) > I(Z; Y ) . Равенство здесь имеет место только в том случае, когда I(X; Y |Z) = 0. Ясно, что последнее равенство выполняется, если для всех (x, y, z) ∈ XY Z выполняется соотношение p(x|yz) = p(x|z) . Это условие всегда выполняется, если сообщение z однозначно определяет сообщение x, то есть если сообщения x и z однозначно определяют друг друга. Иначе, если отображение ϕ(·) обратимо. Свойство невозрастания средней взаимной информации можно трактовать следующим образом. Пусть X – множество возможных сигналов на выходе некоторого канала связи, а Y – множество различных передаваемых сообщений. Теорема утверждает, что никакая обработка наблюдений, при 23 которой происходит их преобразование, не может увеличить информацию об интересующем нас сообщении. Очевидно, что теорема остается в силе в том случае, когда преобразование осуществляется над источником Y , а также в том случае, когда осуществляется преобразование как источника X, так и источника Y . Пусть U = ϕ(X)и V = ψ(Y ) – два отображения, заданные на X и Y соответственно. Тогда I(X; Y ) > I(U ; V ) . Если оба отображения обратимы, то имеет место равенство. Пример 1. Пусть X = {0, 1} – множество сообщений на входе канала, Y = {0, 1} – множество сообщений на выходе канала и переходы входных сообщений в выходные задаются с помощью графа переходов. Вероятности p(0|1) = p(1|0) неправильных переходов будем считать одинаковыми и равными p. Описанный канал называется двоичным симметричным каналом (ДСК). α 1−p p β p 1−α 1 1 1−β 1−p Рис. 3..1: Вероятности входных сообщений на графе обозначены через α и 1 − α, а выходных сообщений – через β и 1 − β. По формуле полной вероятности находим β = (1 − p)α + p(1α) . Среднюю взаимную информацию I(X; Y ) будем рассматривать как функцию двух параметров α и p и записывать ее как I(α, p). Имеем I(α, p) = H(Y ) − H(Y |X) , где H(Y ) = −β log β − (1 − β) log(1 − β) = h(β) и H(Y |X) = X i p(xi )H(Y |xi ) = H(Y |x1 ) = −p log p − (1 − p) log(1 − p) = h(p) , так как H(Y |xi ) не зависит от xi . Таким образом, имеем I(α, p) = h(β) − h(p) , 24 где β определяется через α. Предположим, что p фиксировано и будем рассматривать I(α, p) как функцию параметра α. Поскольку h(β) выпуклая вверх функция, а β – линейная функция от α, то I(α, p) – выпуклая вверх функция. Пусть теперь зафиксирован параметр α , а p будем изменять. При α = 1/2 имеем β = 1/2 и I(1/2, p) = 1 − h(p). Поэтому I(1/2, p) – выпуклая вниз функция. Если α 6= 1/2, то d2 1 I(α, p) = > 0, p2 p(1 − p) и значит, I(α, p) – выпуклая вниз функция параметра p. 3.2 Постановка задачи кодирования в дискретном канале В системах связи пару "источник – кодер источника"можно рассматривать как новый источник дискретных сообщений и пару "декодер – получатель"можно рассматривать в качестве получателя сообщений. Сообщения источника на входе канала должны быть представлены в форме сигнала, то есть кодированы, а на выходе канала – декодированы. Для теории информации физическая природа сигналов и шумов является несущественной. Поэтому так же как при кодировании источников, будем рассматривать сигналы на входе и выходе канала как элементы некоторых абстрактных множеств. Определение 12. Канал называется дискретным по входу (выходу), если множество входных выходных сигналов конечно. Канал называется каналом с дискретным временем, если сигналы на входе и выходе представляют собой конечные или бесконечные последовательности элементов алфавита X на входе канала и алфавита Y на выходе канала. Дискретный по входу и выходу канал с дискретным временем будем называть дискретным каналом. Наличие шума может привести к тому, что один и тот же входной сигнал канала может перейти в различные выходные сигналы. Такие переходы в теории информации описываются с помощью условных распределений вероятностей. В случае дискретного канала трансформация входных сигналов в выходные задаются условными вероятностями p(y|x). x ∈ X, y ∈ Y , получения на выходе сигнала y, если на вход был послан сигнал x. В дальнейшем X и Y будем рассматривать как множество сигналов на входе и выходе канала, которые появляются в некоторый фиксированный момент времени. Поэтому условные вероятности {p(y|x)} описывают процесс передачи одного сигнала. Однако по каналу, как правило, передается достаточно длинная последовательность сигналов. Определение 13. Будем говорить, что дискретный канал задан, если для любого целого n и любых последовательностей (x(1) , . . . , x(n ) и (y (1) , . . . , y (n ) из элементов X и Y соответственно заданы условные (переходные) вероятности p(y (1) , . . . , y (n) |x(1) , . . . , x(n ) получения на выходе канала последовательности (y (1) , . . . , y (n ), если на входе была последовательность (x(1) , . . . , x(n ). Определение 14. Дискретный канал называется каналом без памяти (ДКБП), если для любого n и любых последовательностей (x(1) , . . . , x(n) ) ∈ X n и (y (1) , . . . , y (n) ) ∈ Y n имеет место равенство p(y (1) , . . . , y (n) |x(1) , . . . , x(n) ) = n Y i=1 p(y (i) |x(i) ) . Дискретный канал без памяти (ДКБП) будем обозначать через {XY, p(y|x)}, где X и Y – входные и выходные алфавиты, а p(y|x), x ∈ X, y ∈ Y , – переходные вероятности канала. 25 Если задано некоторое входное распределение вероятностей, скажем, p(x), то оно вместе с условными распределениями p(y|x) задает совместное распределение вероятностей на парах (x, y) ∈ X nY n p(x, y) = p(y|x)p(x) и распределения вероятностей выходных последовательностей канала X p(x)p(y|x) . p(y) = x∈X n Пример 2. Пусть имеется двоичный симметричный канал (ДСК) без памяти, X = {0, 1}, Y = {0, 1} и пусть p(0|1) = p(1|0) = p – вероятность передачи сигнала с ошибкой. Если x, y – последовательность длины n из нулей и единиц на выходе и входе канала, то p(y|x) = pt (1 − p)n−t , где t количество позиций, в которых последовательности x y различаются, то есть t – количество ошибок при передаче x и получении y. Предположим, что p < 0.5 и требуется передать одно из двух сообщений z1 и z2 . Если закодировать сообщения как z1 → 0 и z2 → 1, то вероятность неправильного приема сообщения равнялась бы p. Рассмотрим другой способ кодирования (передачу с помощью повторений): если надо передать z1 , то по каналу передается последовательность из n нулей, если же надо передать z2 , то по каналу передается последовательность из n единиц. Приемник работает по следующему правилу: если в принятой последовательности количество нулей больше количества единиц, то считается, что передано z1 , в противном случае считается, что передавалось z2 . Ясно, что ошибка декодирования возникает всякий раз, когда при передаче последовательности длины n число ошибок t превосходит или равно n/2. Поэтому вероятность неправильного приема сообщения Pen определяется следующим образом: X Cni pi (1 − p)n−i . Pen = P {t > n/2} = i>n/2 Так как  µn  µn  µn 1 1 1 = > −p> −p ⊂ −p > −p>0 , n 2 n 2 n 2 то при возрастании n по теореме Бернулли вероятность ошибки Pen стремится к нулю: Pen 6 P  µn 1 −p > −p →0 n 2 при n → ∞. Таким образом, вероятность неправильной передачи сообщений по каналу может быть сделана сколь угодно малой, если это сообщение передавать достаточно большое количество раз. Время передачи при таком методе кодирования пропорционально числу повторений, При этом скорость передачи, то есть количество информации, передаваемое в единицу времени, будет стремиться к нулю, так как за все время передачи будет передано одно из двух сообщений или не более одного бита информации. Мы покажем, что произвольно малая вероятность ошибки может быть достигнута и при скоростях передачи, отличных от нуля, за счет усложнения методов кодирования и декодирования. Определение 15. Кодом длины n и объемом M для канала называется множество из M пар {u1 , A1 ; u2 , A2 ; . . . ; uM , AM }, где ui ∈ X n , i = 1, . . . , M – последовательности длины n, образованные входными сигналами канала и называемые кодовыми словами (ui 6= uj при i 6= j), и Ai ⊂ Y n , i = 1, . . . , M , – решающие области, образованные выходными последовательностями канала, причем при i 6= j множества Ai и Aj не пересекаются. Если задан код, то задано как множество кодовых слов, так и правило, по которому приемник принимает решение о переданном кодовом слове: если на выходе канала появляется последовательность y и y ∈ Ai , то приемник принимает решение о том, что передавалось слово ui . 26 Определение 16. Скоростью кода (или скоростью передачи) называется величина R= 1 бит log M , n симв где M – объем кода и n – длина кода. Скорость кода R представляет собой максимальное количество информации, которое может быть передано с помощью одного сигнала (или символа). Такое количество информации передается по каналу, если кодовые слова имеют одинаковую вероятность появления. Скорость кода измеряется в битах на символ. Отметим различие в определениях скорости кода канала и скорость равномерного кода источника. В случае кода источника скорость определяется как отношение логарифма числа кодовых слов к длине отрезков кодируемых сообщений. В случае кода канала скорость определяется как отношение того же числа к длине кодовых слов. Код длины n со скоростью R имеет объем M = 2nR . Такой код будем обозначать через G(n, R). Пример 3. Предположим, что двоичный источник без памяти имеет энтропию H(X) < 1. Как известно, при кодировании сообщений такого источника можно достичь скорости близкой к H(X). Это означает, что при появлении на входе кодера источника n двоичных символов, где n достаточно велико, на выходе кодера появляется примерно nH(X) двоичных символов, что меньше, чем n. Если теперь рассматривать последовательности длины nH(X) как входные сообщения для кодера двоичного канала, осуществляющего кодирование со скоростью R < 1, то длина кодовых слов будет равна n H(X) R , что больше, чем nH(X). Таким образом, кодирование источника понижает длину последовательностей сообщений, а кодирование в канале её увеличивает, то есть кодирование источника устраняет избыточность, а кодирование в канале вводит избыточность. Последовательное применение этих двух операций в большинстве случаев увеличивает эффективность по сравнению с передачей сообщений без кодирования. Ошибка декодирования слова ui возникает, когда последовательность на выходе канала не принадлежит решающей области Ai . Через λi обозначим ошибку в декодировании слова ui X p(y|ui ) . λi = y ∈Ai Мерой надежности канала является средняя вероятность ошибки λ= M X λi p(ui ) , i=1 где p(ui ) – вероятность передачи i-го кодового слова. Так как распределение вероятностей p(ui ), i = 1, . . . , n, характеризует источник сообщений и никак не связано ни с каналом, ни с кодом, то под средней вероятностью ошибки декодирования будем иметь ввиду λ= M 1 X λi . M i=1 В случае оптимального кодирования источника, когда p(ui ) = 1/M , i = 1, . . . , M , оба определения средней вероятности ошибки декодирования совпадают. В качестве другой количественной меры надежности передачи с помощью кода G(n, R) используется максимальная вероятность ошибки. Λ = max{λ1 , . . . , λM } . Определение 17. Пропускной способностью дискретного канала называется максимальное число C такое, что для любого сколь угодно малого δ, δ > 0, и любого R, R < C, существует код G(n, R) такой, что средняя вероятность ошибки удовлетворяет неравенству λ<δ (3.6) 27 Так как C является верхней гранью скоростей кодов, для которых выполняется неравенство (3.6), значит, для любого R, R > C, существует δ ′ > 0 такое, что λ > δ ′ для любого n и любого кода G(n, R). 3.3 Информационная емкость дискретных каналов без памяти Пусть p(y|x), x ∈ X, y ∈ Y , – переходные вероятности задающие дискретный канал без памяти. По определению такого канала p(y|x) = n Y p(y (i) |x(i) ) i=1 для любых последовательностей x ∈ X n и y ∈ Y n , x = (x(1) , . . . , x(n) ), y = (y (1) , . . . , y (n) ). Средняя взаимная информация между последовательностями на входе и выходе канала имеет вид XX I(X n ; Y n ) = p(y|x)p(x) log[p(y|x)/p(y)] , x y P где p(y) = x∈X n p(y|x)p(x). Для любого распределения вероятностей p(x), x ∈ X n , на входе канала введем распределения вероятностей по каждой компоненте последовательности x, полагая X X X pi (x(i) ) = ··· ··· p(x) . x(1) x(j) j6=i x(n) Распределения вероятностей pi (x), P x ∈ X, порождают источники Xi = {X, pi (x)} и Yi = {Y, pi (y)} на входе и выходе канала, где pi (y) = x∈X p(y|x)pi (x). Поскольку рассматривается канал без памяти средняя взаимная информация между источниками Xi и Yi запишется в виде XX I(Xi ; Yi ) = p(y|x)pi (x) log[p(y|x)/pi (y)] . y x Определение 18. Информационная емкость C ∗ дискретного канала без памяти определяется соотношением С∗ = max I(X, Y ) , {p(x)} где максимум берется по всем входным распределениям вероятностей p(x) на X. ство Лемма 3.1. Для произвольного входного распределения p(x), x ∈ X n выполняется неравенI(X n ; Y n ) 6 n X I(Xi ; Yi ) 6 nC ∗ . i=1 Нижняя граница в равенстве достигается тогда, когда источники Xi , i = 1, . . . , n, статистически независимы, а равенство в верхней границе достигается тогда и только тогда, когда для распределений вероятностей по отдельным составляющим на входе канала достигается информационная емкость канала. 28 Доказательство. Пусть p(x) – произвольное распределение вероятностей на входе дискретного канала без памяти. Имеем I(X n ; Y n ) = H(Y n ) − H(Y n |X n ) = X X = H(Y n ) + = H(Y n ) + x∈X n y∈Y n n X X X i=1 = H(Y n ) + x∈X n n X X i=1 p(x)p(y|x) log y (i) ∈Y x(i) ∈Xi n = H(Y ) − y∈Y X n X i=1 n p(y (i) |x(i) ) = p(x)p(y|x) log p(y (i) |x(i) ) = pi (x(i) )p(y (i) |x(i) ) log p(y (i) |x(i) ) = i H(Yi |Xi ) 6 i=1 n Y n X i=1 H(Yi ) − n X i=1 H(Yi |Xi ) = n X I(Xi ; Yi ) . (3.7) i=1 В неравенстве (3.7) имеет место знак равенства, если источники Y1 , . . . , Yn статистически независимы, то есть если n Y p(y) = pi (y (i) ) i=1 для всех y ∈ Y n . Для дискретного канала без памяти это выполняется, если выбрать p(x) = n Y pi (x(i) ) . i=1 Действительно, в этом случае p(y) = X p(x)p(y|x) = x∈X n = X ... x(1) ∈X1 n Y X i=1 x(i) ∈Xi n Y X x(n) ∈Xn i=1 pi (x(i) )p(y (i) |x(i) ) = pi (x(i) )p(y (i) |x(i) ) = n Y pi (y (i) ) . i=1 Далее, для произвольного входного распределения p(x), x ∈ X n , имеем I(X n ; Y n ) 6 n X i=1 max I(Xi ; Yi ) = n max I(X; Y ) = n C ∗ . {pi (x(i) )} {p(x)} Если p(x), x ∈ X, – распределение вероятностей на входе канала такое, что на нём достигается информационная емкость канала, тогда для распределения p(x) = n Y p(x(i) ) i=1 выполняется соотношение I(X n ; Y n ) = n X i=1 Лемма доказана. I(Xi ; Yi ) = n max I(X; Y ) = n C ∗ . {p(x)} 29 Пример 4. (Информационная емкость двоичного симметричного канала.) В обозначениях примера 1 имеем, что I(X; Y ) = I(α, p) = h(β) − h(p). Функция h(β) достигает максимума, равного 1, при β = 1/2. Для ДСК распределение на выходе канала будет равномерным, если равномерно распределение на входе канала. Поэтому C ∗ = 1 − h(p) . Пример 5. (Информационная емкость двоичного симметричного канала со стиранием.) Пусть X = {0, 1} – множество элементарных сообщений на входе канала и Y = {0, 1, ∗} — сигналы на выходе канала. Если полученный сигнал не поддается расшифровке, то его лучше стереть. В симметричном канале вероятность стирания символов 0 и 1 одинакова и равна q. Если стирания не произошло, то оба сигнала 0 и 1 с одинаковой вероятностью 1 − p− q будут правильно расшифрованы, а с вероятностью p будет иметь место ошибка. Так как H(Y |0) = H(Y |1) = H(Y ; X) = −(1 − p − q) log(1 − p − q) − p log p − q log q , средняя взаимная информация между источниками X и Y равна I(X; Y ) = H(Y ) + (1 − p − q) log(1 − p − q) + p log p + q log q . Пусть {α, 1 − α} распределение вероятностей на входе канала. Тогда по формуле полной вероятности находим , что на выходе канала β1 = p(0) = α(1 − p − q) + (1 − α)p и β2 = p(1) = (1 − α)(1 − p − q) + αp . Заметим, что β1 + β2 = 1 − q. Энтропия H(Y ) = −β1 log β1 − β2 log β2 − q log q максимальна, если максимально выражение −β1 log β1 −β2 log β2 , где β1 +β2 = 1−q. Легко проверить, что максимум этого выражения достигается при β1 = β2 = (1 − q)/2. Можно убедиться, что соотношение β1 = β2 = (1 − q)/2 выполняется, если принять α = 1/2. Поэтому 1−q 1−q log − q log q . Hmax (Y ) = −2 2 2 Подставляя это выражение в I(X; Y ) найдем максимальное значение средней взаимной информации, равной информационной емкости канала со стиранием C ∗ = −(1 − q) log 1−q + (1 − p − q) log(1 − p − q) + p log p (бит/симв). 2 В случае p = 0 информационная емкость канала равна C ∗ = 1 − q (бит/симв). 3.4 Методы декодирование Декодирование по максимуму правдоподобия (МП-декодирование). Рассмотрим некоторый ДКБП канал {X n Y n , p(x, y} и обозначим через u1 , . . . uM , ui ∈ X n , его кодовые слова. Предположим, что набор кодовых слов фиксирован. Укажем решающие области A1 , . . . AM , Ai ⊂ Y n , при которых средняя вероятность ошибки декодирования минимизируется. Правило декодирования w будем рассматривать как результат отображения источника Y n в множество кодовых слов. При МП-декодировании заданному y ∈ Y n ставится в соответствие кодовое слово с индексом j, wМП (y) = uj , наименьшим среди чисел i = 1, M , на котором достигается максимум max p(y|ui ) = p(y|uj ) . i∈1,M Для j = 1, M определим AМП = {y : wМП (y) = uj } , j (3.8) 30 Для любого другого кода канала вероятность ошибки при передаче слова ui равна X p(y|ui ) . λi = y∈Ai Поэтому вероятность принятия правильного решения M 1 X 1−λ=1− λi M k=1 можно оценить следующим образом 1−λ= M 1 XX 1 p(y|ui ) = M M k=1 y∈Ai X y∈ M S p(y|w(y)) 6 Ai i=1 6 1 X МП p(y|wМП (y)) = 1 − Pen . M n y∈Y Из этого неравенства следует, что МП-декодирование минимизирует вероятность ошибки. Пример 6. Рассмотрим МП-декодирование в стационарном двоичном симметричном (ДСК) канале. Предположим, что в этом канале вероятность ошибки при передаче одного сигнала p < 21 . Пусть x = (x(1 , . . . , x(n) ) и y = (y (1 , . . . , y (n) ). Тогда p(y|x) = n Y i=1 p(y (i) |x(i) ) = pt (1 − p)n−t , где t – количество позиций, в которых последовательность x отличается от последовательности y. Та как pt+1 (1 − p)n−t−1 p = < 1, t n p (1 − p) − 1 1−p то в случае МП-декодирования последовательность y отображается в то слово используемого кода, которому соответствует минимальное значение t. Количество позиций, в которых последовательность x отличается от последовательности y, называется расстоянием Хемминга между x и y. Поэтому МП-декодирование в ДСК канале отображает выходную последовательность канала в такое кодовое слово, которое находится на минимальном расстоянии Хемминга от него, то есть декодирование происходит по минимуму расстояния Хемминга. Пример 7. Рассмотрим МП-декодирование в стационарном симметричном стирающем канале. Предположим, что в рассматриваемом канале вероятность ошибки равна p и вероятность стирания равна q, причем q + 2p < 1. Имеем p(y|x) = n Y i=1 p(y (i) |x(i) ) = pt q s (1 − p − q)n−s−t , (3.9) где s – число стираний в последовательности y и t – количество нестертых позиций в которых последовательности x и y отличаются. Число s определяется только каналом и не зависит от передаваемого кодового слова. При фиксированном s и при q + 2p < 1 правая часть (3.9) убывает с ростом t. Поэтому МП-декодирование в двоичном симметричном стирающем канале отображает выходную последовательность канала в такое кодовое слово, которому соответствует минимальное значение t, то есть МП-декодирование при фиксированном s определяется по минимуму расстояния Хемминга на нестертых позициях. 31 МП-декодирование со стиранием. При заданном y ∈ Y n положим w bМП (y) = uj , если существует единственное j, j = 1, M , для которого достигается максимум в (3.8), и откажемся от принятия решения, если y ∈ / Aj для всех j = 1, M . Для мягкого МП-декодирования обозначим через χm (y), m = 1, M характеристическую функцию множества bМП bМП (y) 6= um } . A m = {y : w Можем записать, что ( χm (y) = 1, если существует m′ 6= m такое, что p(y|um′ ) > p(y|um ); 0, если для любого m′ = 6 m выполняется p(y|um′ ) < p(y|um ) . В этом случае условная вероятность ошибки примет вид X λm = p(y|um )χm (y) . y Пороговое декодирование. Рассмотрим дискретный канал, задаваемый переходными вероятностями p(y|x), x ∈ X n , y ∈ Y n . Пусть p(x), x ∈ X n , – некоторое распределение вероятностей на входных последовательностях канала и I(x; y) – взаимная информация между двумя последовательностями x ∈ X n и y ∈ Y n , имеющая вид I(x; y) = log p(y|x) , p(y) P где p(y) = x∈X n p(y|x)p(x). Рассмотрим пороговое декодер, который работает следующим образом. Для принятой последовательности y декодер вычисляет статистику θ(i) = I(ui ; y) для каждого подового слова ui , i = 1, . . . , M . Декодер сравнивает все значения статистики θ(i) с числом T n, где T – некоторый фиксированный параметр (порог). Если имеется единственное значение i = j, для которого θ(j) > T n, то декодер принимает решение , что передавалось кодовое слово ui . В противном случае декодер производит стирание. Для данного способа принятия решения при передачи кодового слова um ошибочное решение (необнаруженная ошибка) принимается тогда и только тогда, когда статистика θ(m) 6 T n и существует ровно одно значение m′ 6= m, для которого θ(m′ ) > T n. Правильное решение при передаче слова um принимается тогда и только тогда, когда статистика θ(m) > T n и для всех значений m′ 6= m статистика I(m′ ) 6 T n. (T ) Для рассматриваемого порогового декодирования область декодирования Am , m = 1, M , при использовании порога T > 0 задается следующим образом (T ) Am = {y : θ(m) > T n, и для всех m′ 6= m ввыполняется неравенство θ(m) 6 T n} . Пример 8. Пороговое декодирование для ДСК с вероятностью ошибки p, 0 < p < 1/2. В качестве распределения вероятностей выберем равномерное распределение на входе канала. Тогда распределение вероятностей на выходе канала также будет равномерным, В частности, p(y = 2−n . Поэтому p I(x; y) = n(1 + log(1 − p)) + d(x, y) log , 0 < p < 1/2 . 1−p Выберем порог T и положим T∗ = 1 + log(1 − p) − T , log 1−p p Тогда решающая область будет иметь вид ∗ ′ ∗ ) A(T m = {y : d(um , y) < T n), для других m 6= m выполняется неравенство d(um′ , y) > T n) . 32 3.5 Помехоустойчивое кодирование в ДСК Рассмотрим двоичный симметричный канал (ДСК) без памяти с алфавитом X = {0, 1} на входе канала и алфавитом Y = {0, 1} на выходе канала и пусть p(0|1) = p(1|0) = p < 1/2 — вероятность передачи сигнала с ошибкой. Определение 19. Код длиной n и объемом M называется избыточным, если M < 2n . При использовании кода без избыточности появление ошибки в любом из принятых слов остается незамеченным, поскольку изменение символа хотя бы в одном разряде приводит к одному из кодовых слов. Возможность выявления ошибки в принимаемых кодовых словах появляется только в случае избыточности кода. Будем называть используемые кодовые последовательности (блоки) разрешенными, а остальные (N − M ) блоков — запрещенными. Если последовательность на выходе ДСК оказывается запрещенной, то это свидетельствует об ошибке при приеме. Существует ненулевая вероятность, что принятая последовательность является другим разрешенным кодовым словом. При выборе помехоустойчивого кода стремятся к тому, чтобы вероятность такого события была как можно меньше. Введем код {u1 , A1 ; . . . ; uM , AM } длиной n и объемом M , и функцию принятия решения w(y), y) ∈ Y n . При декодировании принятые запрещенные кодовые слова преобразуются декодером в разрешенные по определенному правилу: если y ∈ Ai , то w(y) = ui . Выбрав подходящим образом решающие области, при декодировании появится возможность исправить ошибки, допущенные при передаче кодовых слов по каналу с шумом. bm обозначим кодовое слово um как элемент Y n , то при декодировании по максиЕсли через u муму правдоподобия b um ∈ Am , так как при p < 1/2 для всех t = 1, . . . , n выполняется неравенство bm |um ) = (1−p)n > pt (1−p)n−t . Поэтому Am состоит из последовательности b p(u um и соответствующих кодовому слову запрещенных блоков, которые декодируются в кодовое слово um . Может случиться T bm и u bm′ . так, что Am Am′ 6= ∅, то есть найдется y минимально равноудаленный по Хеммингу от u Поэтому в некоторых случаях МП-декодер не в состоянии однозначно распознать переданное кодовое слово. Введем понятие кодового расстояния. Определение 20. Наименьшее из расстояний между любыми парами используемых кодовых слов кода G = G(n, R) называется кодовым расстоянием и обозначается через d(G). При МП-декодировании в ДСК исправляющая способность кода характеризуется теоремой Хемминга. Теорема 3.3. Код в ДСК при декодировании по наименьшему расстоянию Хемминга исправляет любые t и менее ошибок в каждом принятом кодовом слове тогда, когда кодовое расстояние d(G) удовлетворяет неравенству d(G) > 2t + 1. bi , u bj ) > 2t+1. Пусть Доказательство. Если d(G) > 2t+1, то для любых кодовых слов ui и uj имеем d(u при передаче некоторого кодового слова uk произошло r 6 t ошибок, в результате чего было принято bk , y) = r 6 q и в то же время расстояние до любой другой последовательности ui слово y. Тогда d(u больше t. Последнее вытекает из неравенства треугольника bi , y) > d(u bk , u bi ) > 2t + 1 . bk , y) + d(u d(u Значит для правильного декодирования принятого слова y необходимо найти кодовое слово u ∈ G, ближайшее в смысле расстояния Хемминга, если число ошибок в принятом слове действительно не превосходит t. Пусть условие d(G) > 2t нарушается и найдутся кодовые слова ui и uj расстояние между которыми d(ui , uj ) = 2t. Допустим, что было передано слово ui . Заменим в слове ui t разрядов на соответствующие разряды из uj , в которых кодовые слова ui и uj различаются. Получим последоbi на расстояние t, d(u bj , y) = d(ui , y) = t и при bi , y) = t. Тогда d(u вательность y, удаленную от u 33 декодировании слова y может быть также отождествлено с кодовым словом uj . Поэтому в этом случае нельзя определить какое на самом деле слово было передано. Поскольку вероятность ошибки кратности t в ДСК определяется биномиальным распределением Pen (t) = Cnt pt (1 − p)n−t , вероятность ошибки декодирования Pen 6 n X Pen (t) = n X t=[d(G)/2] t=[d(G)/2] Cnt pt (1 − p)n−t . Декодирование по минимому расстояния Хэмминга невозможно, если получено кодовое слово, не совпадающее с посланным кодовым словом. Пусть Ai – число кодовых слов (n, k) кода C веса i, тогда вероятность необнаруженной ошибки Pr равно Pr = n X t=d(G) At pt (1 − p)n−t . Пример 9. Пусть код G состоит из четырех слов 00000, 01011, 10110 и 11101, так что каждые два слова отличаются не менее чем в трех разрядах, d(G) = 3. Согласно теореме декодер может исправить одиночную ошибку в любом разряде. При декодировании по наименьшему расстоянию Хемминга каждому из 28 неразрешенных блоков нужно поставить в соответствие наиболее близкое кодовое слово. В таблице под каждым кодовым словом выписываются все возможные блоки, отличающиеся от кодового слова в одном разряде. 00000 10000 01000 00100 00010 00001 ..... 10001 11000 01011 11011 00011 01111 01001 01010 ..... 11010 10011 10110 00110 11110 10010 10100 10111 ..... 00111 01110 11101 01101 10101 11001 11100 11100 ..... 01100 00101 Оставшиеся 8 неразрешенных блоков отличаются от каждого кодового слова не менее чем в двух разрядах. Однозначно их в таблице разместить нельзя. Так блок 10011 находится во 2-м столбце таблицы и в 3-м столбце строки: 00101 01110 10011 11000. При декодировании по наименьшему расстоянию нужно найти столбец, в котором содержится принятый блок и выбрать кодовое слово, находящееся в верхней строке этого столбца. Поэтому задача помехоустойчивого кодирования состоит в поиске кода, обладающего максимальным кодовым расстоянием d(G) при заданной длине n и числе M кодовых слов. В общем виде задача помехоустойчивого кодирования решения не имеет. Рассмотренный табличный метод декодирования даже при умеренных n на практике не реализуем. Поэтому основным направлением современной теории кодирования является поиск кодов, для которых кодирование и декодирование осуществляются на основе алгебраических принципов, без перебора. К числу таких кодов относятся линейные коды, в частности, циклические коды. 34 3.6 Прямая и обратная теорема кодирования для дискретного канала без памяти Пусть задан дискретный канал, то есть заданы множества входных X и выходных Y сигналов, а также при всех n = 1, 2 . . . заданы условные распределения вероятностей p(y|x), y ∈ Y n , x ∈ X n . Предположим, что для передачи по каналу используется код G(n, R) = {u1 , A1 ; u2 , A2 ; . . . ; uM , AM } длины n и объема M = 2nR , где A1 , . . . , AM — решающие области. Введем в рассмотрение среднюю вероятность ошибки λ(G): λ(G) = M 1 X X p(y|ui ) , M i=1 c (3.10) y∈Ai где Aci — дополнение Ai . Обозначим через p вероятностный вектор (p(x1 ). . . . , p(xL )) и положим E0 (ρ, p) = − log XhX y∈Y p(x)p(y|x)1/(1+ρ) x∈X i1+ρ . Функция E0 (ρ, p) называется функцией Галлагера. Введем функцию
E(R) = max − ρR + E0 (ρ, p) , ρ,p где максимум разыскивается по всем ρ, 0 6 ρ 6 1 и по всем распределениям {p(x)} на X. Теорема 3.4. (Прямая теорема кодирования.) Для произвольного дискретного канала без памяти {XY, p(y|x)} существует код со скоростью R, для которого средняя вероятность ошибки декодирования удовлетворяет неравенству λ 6 2−nE(R) , (3.11) где n – длина кода, а экспонента случайного кодирования зависит только от матрицы переходных вероятностей канала и от скорости кода, причем E(R) > 0 при всех R, 0 6 R 6 C ∗ , где C ∗ — информационная емкость канала. Теорема 3.5. (Обратная теорема кодирования для каналов без памяти.) Пусть C ∗ – информационная ёмкость дискретного канала и R = C ∗ + ε, где ε – произвольное положительное число. Тогда существует положительное число δ, зависящее от R, такое, что для всякого кода G(n, R) средняя вероятность ошибки λ удовлетворяет неравенству λ > δ. Следствием двух последних теорем кодирования является теорема кодирования Шеннона для каналов без памяти. Теорема 3.6. Пусть C — пропускная способность канала без памяти, то есть такое число, что для каждого R < C существует код G(n, R) со средней вероятностью ошибки, меньшей чем заданное наперед произвольное положительное число, и что для любого R > C не существует кода с таким свойством. Пусть C ∗ — информационная емкость канала, равная C ∗ = max I(X; Y ) . p Тогда C = C ∗ . 35 3.7 Теорема Шеннона для ДСК канала Рассмотрим двоичный симметричный канал. Пусть 0 < p < 1/2 есть вероятность неверной передачи символа по каналу связи. Пусть C - двоичный код с M равновероятными кодовыми словами u1 , . . . , uM длины n. Пусть λi - вероятность неправильного декодирования кодового слова ui . Тогда средняя вероятность ошибки декодирования λ определим как λ = λC (p) = M 1 X λi , M i=1 где λi зависит от p. Рассмотрим совокупность L всех двоичных кодов длины n мощности M и определим λ∗ (M, n, p) = min{λC }. C∈L Как нам известно, скорость кода R длины n мощности M определяется как (log M )/n, а информационная емкость двоичного симметричного канала с вероятностью ошибки p равна C ∗ = C ∗ (p) = 1 − h(p) = 1|p log p + (1 − p) log(1 − p) . Теорема 3.7. Для любой сколь угодно малой величины ε и любого 0 < R < C ∗ (p) существует двоичный код C длины n мощности M и скорости R такой, что средняя вероятность ошибки декодирования λC < ε. Иначе говоря, для достаточно больших n существует хороший код длины n со скоростью сколь угодно близкой к пропускной способности канала связи. Нам потребуется несколько вспомогательных утверждений. При передачи информации по двоичному симметричному каналу число ошибок в полученном слове является биномиально распределенной случайной величиной ν, принимающей значения 0, 1, . . . , n с математическим ожиданием M ν = np и дисперсией Dν = np(1 − p). Если в кодовом слове произошло t ошибок, то вероятность получить вектор ошибок e веса t равна pt (1 − p)n−t . Выберем произвольное ε > 0. Для случайной величины ν введем следующую величину  Dν 1/2 . b= ε/2 Согласно неравенству Чебышева, имеем P {|τ − M ν| > b} 6 Отсюда следует где P {ν > ρ} 6 Dν ε = . 2 b 2 ε , 2  np(1 − p) 1/2 i   h . ρ = M ν + b = np + ε/2 (3.12) Таким образом, вероятность того, что в результате ν ошибок полученное на приеме слово y находится от переданного кодового слова u на расстояние большее, чем ρ, мала. При фиксированном ε > 0 для достаточно больших n величина ρ не превосходит n/2, поскольку p < 1/2. Рассмотрим шар радиуса [pn] с центром в некоторой точке u ∈ F2n : B[pn] (x) = {y ∈ F2n dH (u, y) 6 [pn]}. Оценим объем шара. 36 Лемма 3.2. Пусть 0 6 p 6 21 . Тогда верна оценка [np] X Cni 6 2nh(p) . i=0 Доказательство. Имеем 1 = (p + (1 − p))n > [np] X [np] X Cni pi (1 − p)n−i > i=0 Cni 2log[(1−p) n p 1−p i=0 [np] X
np [np] ] = X [np] X i=0 Cni pnp (1 − p)n−pn = Cni 2n log(1−p)+pn log p 1−p i=0 Cni 2n(p log p+(1−p) log(1−p)) = 2−nh(p) [np] X
= Cni . i=0 i=0 Отсюда следует [np] X Cni 6 2−nh(p) . i=0   Оценим теперь объём шара радиуса ρ = M ν + b с центром в некоторой точке, используя функцию энтропии h(p).  1/2 Dν Лемма 3.3. Пусть 0 6 p 6 21 и ρ = [M ν + b], где b = ε/2 . Тогда  1  1 log |Bρ (u)| 6 h(p) + O √ при n → ∞. n n Доказательство. По предыдущей лемме имеем ρ
1 ρ ρ
ρ ρ
= − log − 1 − log 1 − = log |Bρ (u)| 6 h n n n n n n     [np + b] [np + b] [np + b] [np + b] log − 1− log 1 − = =− n n n n b  1  при n → ∞. −p log p − (1 − p) log(1 − p) + O = h(p) + O √ n n что доказывает лемму. Перейдем к доказательству теоремы Шеннона для кодирования в двоичном симметричном зашумленном канале. Введем функцию f (y, x). Пусть y, x ∈ F2n , тогда ( 0, d(y, x) > ρ f (y, x) = (3.13) 1, d(y, x) 6 ρ . Функция f (y, x) – характеристическая функция принадлежности вектора y шару Bρ (x) с центром в точке x. 37 Доказательство. Выберем сколь угодно малую величину ε > 0. Рассмотрим случайный двоичный код длины n мощности M , то есть выберем случайным образом кодовые слова u1 , . . . , un . Декодируем полученный вектор y следующим образом: если существует в точности одно кодовое слово ui такое, что d(ui , y) 6 ρ, то y декодируем в ui , в противном случае регистрируем ошибку или, если должны декодировать в любом случае, всегда декодируем в u1 . Пусть λi , как и выше, вероятность того, что на выходе декодера получено слово, отличное от переданного слова ui . Для λi имеем следующую оценку сверху: X X X   P (y|ui ) 1 − f (y, ui ) + P (y|ui ) 6 f (y, uj ) = λi = j6=i y∈F2n y :d(ui ,y )>ρ X X X P (y|ui )(1 − f (y, ui )) + P (y|ui )f (y, uj ), y ∈F2n j6=i y∈F2n   P здесь выражение 1 − f (y, ui ) + j6=i f (y, uj ) равно нулю тогда и только тогда, когда найдется единственное кодовое слово ui такое, что d(ui , y) 6 ρ,   P в противном случае 1 − f (y, ui ) + j6=i f (y, uj ) > 1. Первая сумма в предыдущем неравенстве равна вероятности того, что полученное на выходе слово нвходится на расстоянии большем ρ от переданного кодового слова ui . Согласно неравенству (3.12) вероятность не превышает ε/2. Таким образом, λC (p) 6 M ε 1 X X X P (y|ui )f (y, uj ). + 2 M i=1 y ∈F2n j6=i Основная идея дальнейшего доказательства состоит в том, что величина λ∗ (M, n, p) меньше математического ожидания λC над ансамблем L всех возможных кодов C длины n и мощности M взятых случайно. Отсюда имеем λ∗ (M, n, p) 6 M 1 X X X ε + M (P (y|uj ))M (f (y, uj )) = 2 M i=1 y ∈F2n j6=i M 1 X X X |Bρ | ε M (P (y|uj )) = + 2 M i=1 2n n j6 = i y∈F2 Таким образом, λ∗ (M, n, p) − и деля на n получаем ε 2 M M ε |Bρ | X X X + M (P (y|uj )) = 2 M · 2n i=1 y ∈F2n j=1,j6=i M M   X |Bρ | X X ε P (y|uj ) = + M n 2 M · 2 i=1 j=1,j6=i y ∈F2n ε |Bρ | ε |Bρ | · B · (M − 1) 6 +M n . + n 2 M ·2 2 2 6 M · |Bρ |/2n . Логарифмируя обе части, применяя последнюю лемму   1  1 1 ε 6 log M − (1 − h(p)) + O √ . log λ∗ (M, n, p) − n 2 n n 38 Подставляя M = 2[R·n] в правую часть (вспомним, что по условию число R скольугодно близко к пропускной способности канала C(p) = 1 − h(p)), получаем  1 ε < −β < 0 , log λ∗ (M, n, p) − n 2 где β константа, равная С(p) − R. Отсюда λ∗ (M, n, p) < 2ε + 2−βn . Начиная с некотороо n будет выполняться 2−βn < 2ε , и, следовательно, λ∗ (M, n, p) < ε. Таким образом, λ∗ (M, n, p) → 0 при n → ∞. Теорема доказана. Глава 3 Конспект лекций по теории кодирования 4.1 Линейные коды I. Пусть Fq , (q − простое) – конечное поле, k < n и Fqk → Fqn – инъективное линейное отображение векторного пространства Fqk в пространство Fqn . Вектора a ∈ Fqk будем называть информационными словами (векторами). Символом C, будем обозначать образ пространства Fqk при этом отображении. C является линейным подпространством в пространстве Fqn . Будем называть его (n, k)-пространством кодовых слов. Матрицу G из компонент базисных векторов кодового пространства будем называть порождающей матрицей. Фиксируем в Fqк базис и представим информационный вектор a в виде a = a1 , · · · < ak . В матричнов представлении кодовое отображение запишется в виде C ∋ c = a · G, G − k × n − матрица Pn II. В пространстве Fqn введено скалярное “произведение” (a, b) = i=1 ai bi . Для введенного произведения не выполняется первая аксиома скалярного произведения: ненулевой вектор a может быть ортогонален самому себе. Через C ⊥ обозначим ортогональное дополнение пространства C в Fqn . Из компонент базисных векторов в C ⊥ составим (n − k) × n-матрицу H, называемую проверочной матрицей. Для любого вектора c ∈ C имеем c ⊥ b ∈ C ⊥ . Поэтому Hct = 0. Более того, для любого c = aG выполняется равенство HGt at = 0. Поэтому HGt = GH t = 0. Порождающая и проверочная матрица линейного кода определяются неоднозначно. Если G – порождающая матрица (n,k) кода C в Fqn и H – проверочная матрица, то H является порождающей матрицей двойственного (n,n-k) кода C ⊥ с проверочной матрицей G. III. Перестановка строк и сложение строки с другой строкой в порождающей матрице не изменяют кодового пространства. Перестановка столбцов в порождающей матрице приводит к перестановке компонент кодовых векторов. Коды, полученные фиксированной перестановкой компонент кодовых слов будем называть эквивалентными, а перестановку строк, сложение строк и перестановку столбцов порождающей матрицы будем называть элементарными преобразованиями. Элементарными преобразованиями порождающая матрица приводится к систематическому виду   G = Ek × k : Pk × (n−k) Для порождающей матрицы в систематическом виде несложно построить одну из проверочных матриц   t H = − P(n−k) × n : I(n−k) × (n−k) Если G представлена в систематическом виде, то первые k символов кодового слова являются информационными символами. Теорема 3.8. Каждый линейный код эквивалентен систематическому линейному коду. IV. Вес Хэмминга w(x) вектора x равен числу ненулевых компонент. Расстояние Хэмминга dH (x, y) равно числу различающихся компонент векторов x и y. В линейном пространстве вес Хэмминга и расстояние Хэмминга связаны соотношениями dH (x, y) = w(x − y), w(x) = dH ((x, 0). Расстояние Хэмминга является метрикой 40 V. Предположим, что на вход канала подан информационный вектор c и на выходе канала получен вектор y. Вектор e = y − c называют вектором ошибки. Пусть t ∈ N. Определение. Код C исправляет t ошибок, если для любого вектора y ∈ Fqn существует не более одного кодового вектора c, для которого dH (c, y) 6 t. Другими словами, если при передачи по каналу кодового слова c допущено t ошибок, то c, будет ближайшим к полученному слову. Введем минимальное кодовое расстояние как dC = min dH (u, v) = min w(c) . c∈C u,v ∈C u6=v c6=0 Теорема 3.9. (Хэмминг.) Код с dC > 2t + 1 может исправить не менее t ошибок. VI. Сформулируем лемму о проверочной матрице. Лемма 3.4. Для того, чтобы линейный код C с проверочной матрицей H имел кодовое расстояние dC > s + 1 необходимо и достаточно, чтобы любые s столбцов матрицы H были линейно независимы. Доказательство. Пусть s столбцов матрицы H линейно зависимы. Тогда найдется вектор c такой, что Hct = 0. Это означает, что c ∈ C и w(c) 6 s. Это означает, что dC 6 s. Обратно. Если любые s столбцов матрицы H линейно независимы, то не существует вектора c ∈ C, c 6= 0 такого, что w(c) 6 s такого, что dC 6 s. VII. Пусть C есть (n, k) код и Fqn /C - фактор-пространство. Пространство Fqn распадается на классы смежности. В каждом классе смежности выберем представителя a(i) с минимальным весом, a(0) = 0. Тогда  [  [  n−k Fqn = a(0) + C a(q −1) + C . ··· Пусть y – принятое сообщение, y ∈ a(i) + C и e = y − c – вектор ошибок. Значит, e ∈ a(i) + C. При декодировании по минимуму расстояния Хэмминга вектор ошибок должен иметь минимальный вес, то есть e = a(i) . Элемент минимального веса в смежном классе называется лидером класса. Таким образом, если y ∈ a(i) + C, то получатель считает вектором ошибок лидера смежного класса и декодирует вектор y в кодовое слово c(i) = y − a(i) . VIII. Пусть H – проверочная матрица линейного (n, k) кода C и пусть y ∈ Fqn . Вектор S(y) = H · yt длины (n − k) будем называть синдромом вектора y. Теорема 3.10. Если y, y ∈ Fqn , то (i) S(y) = 0 if and only if y ∈ C (ii) S(y) = S(z) if and only if y − z ∈ C Таким образом, процедура декодирования сводится к построению таблицы лидеров и вычислению соответствующих синдромов. IX. Границы линейных кодов. Теорема 3.11. (Синглтон) Пусть C – (n, k) код над Fq . Тогда dC 6 n − k + 1 . Доказательство. Теорема является следствием леммы о проверочной матрицы. Следствие. dC = n − k + 1 тогда и только тогда, когда любые (n − k) столбцов проверояной матрицы линейно независимы. 41 Теорема 3.12. (Граница Хэмминга) Пусть C – (n, k) код над Fq , исправляющий t ошибок. Тогда t X r=0 Cnr (q − 1)r 6 q n−k . Доказательство. Имеется ровно Cnm (q − 1)m векторов над Fq длины n и веса n в шаре Bt (O) = {x ∈ Fqn : w(x) 6 t. Шары радиуса t с центрами в кодовых словах не пересекаются и каждый содержит t X r=0 Cnr (q − 1)r Fqn . векторов из Общее количество векторов в этих шарах не превосходит числа векторов в Fqn , поэтому верно неравенство t X k q Cnr (q − 1)r 6 q n . r=0 Отсюда следует утверждение теоремы. Определение 21. Код называется совершенным или плотно упакованным, если t X r=0 Cnr (q − 1)r = q n−k , то есть имеет место плотная упаковка F2n шарами радиуса [(dC − 1)/2]. Теорема 3.13. (Гилберт − Варшамов) Если q n−k > d−2 X i=0 i Cn−1 (q − 1)i , то над Fq можно построить линейный (n, k) код с минимальным расстоянием не меньшим d. Доказательство. Построим проверочную (n − k) × n матрицу H такую, что любые d − 1 столбцов линейно независимы. Будем считать, что построено m столбцов таких, что любые d − 1 столбцов линейно независимы, m 6 n−1. Добавить можно столбец, который не является линейной комбинацией не более d − 2 столбцов из m построенных. Подсчитаем количество таких линейных комбинаций. Количество линейных комбинаций из i столбцов с ненулевыми коэффициентами будет равно i i Cm (q − 1)i < Cn−1 (q − 1)i . Поэтому количество столбцов, которые не могут быть добавленными, не превышает d−2 X i=0 i Cn−1 (q − 1)i < q n−k (q n−k - общее число столбцов длины n − k). Значит найдется столбец, который не является линейной комбинацией не более чем d − 2 из уже выбранных столбцов. Его можно взять в качестве (m + 1) столбца. Теорема 3.14. (Плоткин) Для линейного (n, k) кода C с кодовым расстоянием dC выполняется неравенство nq k−1 (q − 1) . dC 6 qk − 1 42 Доказательство. Запишем все кодовые слова построчно в таблице. Через w обозначим средний вес всех кодовых слов в C\0. Ясно, что dC 6 w. Общее число кодовых слов равно |C| = q k и q k − 1 – количество ненулевых кодовых слов. Через C ′ обозначим множество кодовых слов с нулевой i-ой компонентой. Тогда C ′ подпространство в Fqn и |C ′ | равняется q k−1 . Поэтому количество кодовых слов с ненулевой i-ой компонентой равно |C| − |C ′ | = q k−1 (q − 1), значит, вклад i-ой компоненты в суммарный вес кодовых слов равен q k−1 (q − 1). Таким образом суммарный вес кодовых слов равен nq k−1 (q − 1), а средний вес w равен nq k−1 (q − 1) . w= qk − 1 Поэтому dC 6 w = Теорема доказана. nq k−1 (q − 1) . qk − 1 X. Код Хэмминга и его свойства. I. Определим код над полем F2 посредством проверочной матрицы, столбцами которой чвляются все ненулевые векторы длины m. Очевидно, что любые два столбца этой матрицы линейно независимы и найдутся три линейно зависимх столбца, следовательно, по лемме о проверочной матрице кодовое расстояние равно 3 и значит код исправляет одну ошибку. Этот код называется кодом Хэмминга. Длина кодовых слов кода Хэмминга равна n = 2m − 1, длина информационных слов навна k = n − m = 2m − m − 1. Согласно теореме Хэмминга код Хэмминга является совершенным кодом, исправляющим одну ошибку. Код Хэмминга допускает простое декодирование. Представим проверочную матрицу кода Хэмминга столбцы которой записаны в лексикографическом порядке   0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 = [B(1), B(2), . . . , B(n)] , 1 0 1 0 1 0 1 здесь B(i) – двоичное представление числа i. Пусть в канале при передаче вектора x произошла одна ошибка в i-й координате и получен вуктор y = x + ei . Здесь ei – двоичный вектор длины n с единицей только в i-ой компонентею Найдем синдром вектора y: S(y) = Hyt = Hxt + Heti = Heti = B(i) . Таким образом, вектором ошибки является i-ой столбец проверочной матрицы в лексикографическом виде. 4.2 Циклические коды Линейный код C ∈ Fqn называется циклическим кодом, если из условия c = (c0 , c1 , . . . , cn−1 ) ∈ C следует c′ = (c1 , . . . , cn−1 , c0 ) ∈ C. Примером является (7, 4) код Хэмминга с проверочной матрицей   0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 Обозначим через Fq [x] кольцо всех многочленов от переменной x с коэффициентами из поля Fq . Оно ассоциативно, коммутативно и содержит единицу. В кольце Fq [x] рассмотрим фрктор множество Fq [x]/(xn − 1), состоящее из классов вычетов кольца Fq [x] по модулю многочлена xn − 1. Множество Fq [x]/(xn − 1) замкнуто относительно операций сложения (+) и умножения • и, значит, является 43 кольцом, но не является полем. Кольцо Fq [x]/(xn −1) изоморфно n-мерному векторному пространству над Fq : c(x) = c0 + c1 x + C2 x2 + · · · + cn−1 xn−1 ←→ c = (c0 , c1 , c2 , . . . , cn−1 ) Определение 22. Идеалом I кольца Fq [x]/(xn − 1) называется такое его линейное подпространство, что для любых многочленов r(x) ∈ Fq [x]/(xn − 1) и c(x) ∈ I многочлен r(x) • c(x) принадлежит I. Теорема 3.15. Подпространство кольца Fq [x]/(xn −1) является циклическим кодом тогда и только тогда, когда оно образует идеал. Существенным моментом в доказательстве теоремы является тот факт, что умножение многочлена на x соответствует циклическому сдвигу вектора в пространстве Fqn . x • c(x) = x • (c0 + c1 x + c2 x2 + · · · + cn−1 xn−1 ) = cn−1 + c0 x + c1 x2 + · · · + cn−2 xn−1 . II. В циклическом коде C выберем многочлен наименьшей степени. Умножим его на подходящий элемент поля Fq такой, что коэффициент при старшей степени многочлена равнялся 1. Обозначим этот приведенный многочлен через g(x). Предложение 3.1. Циклический код содержит единственный ненулевой приведенный многочлен наименьшей степени. Этот ненулевой приведенный многочлен наименьшей степени называется порождающим многочленом кода. Теорема 3.16. Циклический код состоит из всех многочленов вида f (x) • g(x), где g(x) – порождающий многочлен кода степени r, степеть многочлена f (x) меньше (n-r). Доказательство. Кодовый многочлен поделим на порождающий многочлен с остатком c(x) = q(x)g(x) = s(x) , deg s(x) < deg g(x) . Так как s(x) ∈ C(x) и deg s(x) < r, то g(x) = 0. Теорема 3.17. Циклический код длины n с порождающим многочленом g(x) существует тогда и только тогда, когда g(x) делит xn − 1. Доказательство. Поделим многочлен xn − 1 на порождающий многочлен g(x) с остатком xn − 1 = h(x)g(x) = s(x) . Поэтому h(x) • g(x) = −s(x), s(x) ∈ C(x) и deg s(x) < r. Отсюда следует, что s(x) = 0. Таким образом, xn − 1 = h(x)g(x) . Многочлен h(x) называется проверочным многочленом. Основанием служит следующее рассуждениею. Для любого кодового многочлена c(x) ∈ C(x) имеем h(x)c(x) = h(x)g(x)a(x) = (xn − 1)a(x) . Поэтому c(x) • h(x) = 0. III. Систематическое и несистематическое кодирование. 44 Несистематическое кодирование осуществляется следующим образом. c(x) = i(x)g(x), где deg i(x) 6 k − 1 = n − r − 1. Многочлен i(x) называется информационным многочленом. При систематическом кодировании для информационного многочлена i(x), deg i(x) 6 k − 1 выберем многочлен t(x) так, чтобы многочлен xn−k i(x) + t(x) = c(x) был кодовым многочленом. Так как остаток от деления c(x) на g(x) должен быть равен нулю, имеем xn−k i(x)%g(x)) + t(x)%g(x) = 0 Отсюда находим t(x) = −xn−k i(x)%g(x) . Процедуры систематического и несистематического кодирования дают одно и тоже мнжество кодовых слов. IV. Пусть c(x) ∈ C(x) переданный кодовый многочлен и v(x) ∈ Fq [x]/(xn − 1) принятый многочлен. Многочлен e(x) = v(x) − c(x) называется многочленом ошибок. Многочлен s(x), равный остатку от деления принятого многочлена на порождающий многочлен s(x) = v(x)%g(x) = e(x)%g(x), определяется многочленом ошибок. Будем называть его синдромным многочленом. Теорема 3.18. Если dC – минимальный вес циклического кода C, то каждому многочлену ошибок веса dC /2 соответствует единственный синдромный многочлен. Доказательство. Пусть e1 (x) и e2 (x) многочлены ошибок веса меньше dC /2 и пусть e1 (x)%g(x) =
s(x) и e2 (x)%g(x) = s(x). Тогда e1 (x) − e2 (x) %g(x) = 0. Это означает, что e1 (x) − e2 (x) является кодовым многочленом и вес этого многочлена меньше dC . Что невозможно. V. Порождающая и проверочная матрица циклического кода. Начнем с несистематического кодера. Пусть g(x) = g0 + g1 (x) + · · · + gn−k xn−k – порождающмй многочлен Ясно, что многочлены g(x), xg(x), x2 g(x), . . . , xk−1 g(x) являются кодовыми линейно независимыми многочленами. Поэтому (k × n) матрица   g0 g1 . . . gn−k ......  0 g0 g1  ... gn−k 0 . . .  G=  .........................................  0 0 ... g0 . . . . . . gn−k является порождающей матрицей циклического кода C. Пусть v(x) = a(x)g(x), deg a(x) 6 k − 1. Так как xn − 1 = h(x)g(x), то v(x) · h(x) = a(x) · g(x) · h(x) = a(x)[xn − 1] = a(x)xn − a(x). Это ознчает, что в правой части отсутствуют слагаемы с xk , xk+1 , xk+2 , . . . xn−1 , то есть v0 hk + v1 hk−1 + ... + vk h0 = 0 v1 hk + v2 hk−1 + . . . + vk+1 h0 = 0 ....................................................... vn−k−1 hk + vn−k hk−1 + . . . + vn−1 h0 = 0 t В матричной форме соотношения записываются в виде H · v t = 0 для матрица H = H(n−k)×n имеет вид  hk hk−1 . . . h0 0 . . . . . . 0  0 h h . . . h0 0 . . . 0 k k−1   ....................................... ... 0 hk . . . . . . h0 любого кодового вектора, где     45 Так как строки матрицы H ортогональны кодовым векторам, то матрица H является проверочной матрицей. Многочлен xk h(x−1 ) = hk + hk−1 x + . . . h0 xk является порождающим многочленом (n, n − k) кода C ⊥ – двойственного коду C. Построим порождающую матрицу для систематического кодера. Пусть i(x) – информационный многочлен, deg i(x) 6 k − 1. Процедура систематического кодирования сводится к нахождению многочлена t(x) такого, что c(x) = xn−k · i(x) + t(x) является кодовым многочленом. Таким многочленом является t(x) = −xn−k • i(x) . Для i = 1, . . . k представим xn−i в виде xn−i = qi (x) · g(x) + si (x), si (x) = n−k−1 X sji xj . j=0 Тогда xn−i − si (x) = qi (x) · g(x), i = 1, . . . k являются кодовыми линейно независимыми многочленами. Поэтому порождающая матрица системного кодера запишется в виде   −s0,k −s1,k ... −s(n−k−1),k 1 0 ... 0  −s0,k−1 −s1,k−1 . . . −s(n−k−1),k−1 0 1 . . . 0   G=  ......................................................  −s0,1 −s1,1 ... −s(n−k−1),1 0 0 ... 1 Тогда проверочная матрица систематического кодера примет вид  1 0 ... 0 s0,k s0,k−1 ... s0,1  0 1 ... 0 s s . . . s1,1 1,k 1,k−1 H =  ......................................................... 0 0 . . . 1 s(n−k−1),k s(n−k−1),k−1 . . . s(n−k−1),1     VI. Циклический код Хемминга. Неприводимый многочлен p(x) степени m называется примитивным, если наименьшая степень n, при котором xn −1 делится на p(x) без остатка равна n = 2m −1. Теорема 3.19. Любой циклический код Хэмминга длины 2m − 1 с m > 3 может быть построен с помощью некоторого примитивного многочлена степени m. И обратно, любому примитивному многочлену степени m соответствует некоторый код Хэмминга длины 2m − 1. Рассмотрим поле F8 , для построения поля используем примитивный многочлен p(x) = x3 +x+1 над F2 , α(x) = x является примитивным элементом поля. Перечислим элемениты поля α0 = (001), α1 = (010), α2 = (100), α3 = (011), α4 = (110), α5 = (111), α6 = (101), α7 = (001). Если многочлен c(x) является кодовым многочленом, то c · H t = c · [α0 , α1 , α2 , α3 , α4 , α5 , α6 ] = 6 X ci αi = 0 . i=0 То есть c – кодовое слово тогда и только тогда, когда α корень многочлена c(x). Значит, c(x) делится на минимальный многочлен элемента α. Поэтому многочлен g(x) = (x − α)(x − α2 )(x − α4 ) = x3 + x + 1 является порождающим элементом (7,4) кода Хэмминга. 46 Код, двойственный к (2m − 1, 2m − 1 − m) коду Хэмминга Hm является симплектическим кодом. Все кодовые слова двойственного кода имеют одинаковый вес. m Теорема 3.20. Если Sm – код, двойственный (2m − 1, 2m − 1 − m) коду Хэмминга в F22m −1 , то вес всех кодовых слов равен 2m−1 . Доказательство. По индукции. Пусть m = 2 и  1 0 H2 = 0 1  1 1 проверочная матрица (3, 1) кода Хемминга. Тогда кодовое пространство S 2 состоит из векторов (000), (101), (011), (110) . Вес всех ненулевых кодовых векторов равен 2 = 22−1 . Пусть для m = k теорема верна, то есть для любого x ∈ Sk , x 6= 0, имеем w(x) = 2k−1 . И пусть m = k + 1. Все кодовые слова являются линейными комбинациями строк матрицы Hk+1 . Пусть x = α1 h1 + · · · + αk+1 hk+1 ∈ Sk+1 , где h1 , . . . , hk+1 – строки матрицы Hk+1 и αi ∈ F2 . Рассмотрим два случай: αk+1 = 0 и αk+1 = 1. Переставляя столбцы матрицы Hk+1 , можем эту матрицу представить в виде   t Hk Hk Hk+1 = 0...0 1 1...1 Здесь 0 – нулевой вектор длины k. В первом случае кодовый вектор x будет иметь вид x = (x1 . . . x2k −1 0 x1 . . . x2k −1 ). Тогда w(x) = 2w(e x), w(e x) = 2k−1 и w(x) = 2k . Во втором случае x = α1 h1 + · · · + αk hk + hk+1 = x′ + hk+1 ,
. . 1} . . . 0} 1| .{z где x′ = (x′1 . . . x′2k −1 0 x′1 . . . x′2k −1 ). Можем считать, что hk+1 = 0| .{z 2k −1 2k Пусть x e′ = (x′1 . . . x′2k −1 ) ∈ Hk . x′ )+1+2k −1−w(e x′ )) = Если w(e x′ ) 6= 0, то w(e x′ ) = 2k−1 и w(x′ ) = 2k . Отсюда получаем w(x) = w(e k 2 . Если же w(e x′ ) = 0, то w(x′ ) = 0. Поэтому w(x) = w(hk+1 ) = 2k . VII. Двоичный код Голея. Можно заметить, что   1 2 3 212 = 223 . C23 + C23 + C23 + C23 Это равенство представляет собой необходимое условие существования совершенного двоичного кода, исправляющего три ошибки. Такой код действительно существует и назван был кодом Голея. В основе конструкции лежит равенство x23 − 1 = (x − 1)g1 (x)g2 (x) где g1 (x) = 1 + x2 + x4 + x5 + x6 + +x10 + x11 и g 2 (x) = 1 + x + x5 + x6 + x7 + +x9 + x11 47 В качестве порождающего многочлена можно использовать как g1 (x), так и g2 (x). Шары с центрами в кодовых словах упаковывают пространство F223 . Поэтому кодовое расстояние не может быть больше 7. И можно доказать, что оно не меньше 7. Поэтому заключаем, что кодовое расстояние кода Голея равно 7. Помимо двоичного кода Голея существует совершенный троичный (11, 6) код с кодовым расстоянием, равным 5. Других линейных совершенных кодов, исправляющих более одной ошибки, не существует. VIII. Декодирование по Меггитта. Алгоритм декодирования опирается на следующее утверждение. Предложение 3.2. Пусть s(x) является синдромом принятого из канала слова r(x) некоторого циклического (n, k) кода. Обозначим через s1 (x) остаток от деления многочлена x · s(x) на порождающий многочлен g(x) Тогда s1 (x) является синдромом r1 (x), то есть остатком от деления циклического сдвига на многочлен g(x). Доказательство. Пусть r(x) = r0 + r1 x + · · · + rN −1 xn−1 , x · r(x) = r0 x + r1 x2 + · · · + rN −1 xn и r(1) (x) = x • r(x) . Тогда r(1) (x) = rn−1 + r0 x + · · · + rn−2 xn−1 = rn−1 [xn − 1] + x · r(x) . Положим Тогда r(1) (x) = a(x)g(x) + se(x), r(x) = b(x)g(x) + s(x) и xn − 1 = g(x) · h(x) . r(1) (x) = a(x)g(x) + se(x) =rn−1 + r0 x + · · · + rn−2 xn−1 = rn−1 [xn − 1] + x · r(x) = rn−1 h(x)g(x) + x [b(x)g(x) + s(x)] Отсюда следует, что Предложение доказано.   x · s(x) = a(x) + rn−1 h(x) + x b(x) · g(x) + se(x) . В результате, 1. Между множеством всех исправляемых ошибок и множеством соответствующих синдромов существует взаимно однозначное соответствие. 2. Если s(x) – синдром, соответствующий многочлену ошибок e(x), то xs(x) mod g(x) – синдром, соответствующий xe(x) mod (xn − 1). 3. Пусть s(x) – синдром принятого слова y(x) некоторого циклического (n, k) кода. Пусть s1 (x) = xs(x)%g(x). Тогда s1 (x) является синдромом циклического сдвига принятого слова, то есть xy(x)%g(x). Из вышесказанного следует, что множество всех ошибок можно разбить на классы эквивалентности таким образом, чтобы каждый класс состоял из циклических сдвигов одной комбинации ошибок и сохранять в памяти только синдромы одного из представителей каждого класса эквивалентности. Для определения принадлежности ошибок данному классу нужно выполнить операцию xs(x)%g(x), не более n раз, и сравнить результат с содержимым памяти. При обнаружении такого соответствия ошибки сдвинутого многочлена y(x) исправляются и обратным сдвигом кодовое слово восстанавливается. 48 и Используемая литература 1. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 1982. 2. Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. Ростов на Дону: Феникс, 2002. 3. Котоусов А.С. Теория информации. М.: Радио и связь, 2003. 4. Вернер М. Основы кодирования. М.: Техносфера. 2004. 5. Соловьева Ф.И. Введение в теорию кодирования. Учебное пособие. Новосибирск. 2011. 6. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир. 1986.