На рис. 1 приняты следующие обозначения: X, Y, Z, W – сигналы, сообщения; f – помеха; ЛС – линия связи; ИИ, ПИ – источник и приемник информации; П – преобразователи (кодирование, модуляция, декодирование, демодуляция).

Существуют различные типы каналов, которые можно классифицировать по различным признакам:

1.По типу линий связи: проводные; кабельные; оптико-волоконные;

линии электропередачи; радиоканалы и т.д.

2. По характеру сигналов: непрерывные; дискретные; дискретно-непрерывные (сигналы на входе системы дискретные, а на выходе непрерывные, и наоборот).

3. По помехозащищенности: каналы без помех; с помехами.

Каналы связи характеризуются:

1. Емкость канала определяется как произведениевремени использования канала T к, ширины спектра частот, пропускаемых каналом F к и динамического диапазона D к . , который характеризует способность канала передавать различные уровни сигналов

V к = T к F к D к. (1)

Условие согласования сигнала с каналом:

V c £ V k ; T c £ T k ; F c £ F k ; V c £ V k ; D c £ D k .

2.Скорость передачи информации – среднее количество информации, передаваемое в единицу времени.

3.

4. Избыточность – обеспечивает достоверность передаваемой информации (R = 0¸1).

Одной из задач теории информации является определение зависимости скорости передачи информации и пропускной способности канала связи от параметров канала и характеристик сигналов и помех.

Канал связи образно можно сравнивать с дорогами. Узкие дороги – малая пропускная способность, но дешево. Широкие дороги – хорошая пропускная способность, но дорого. Пропускная способность определяется самым «узким» местом.

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

Проводные:

1. Проводные – витая пара (что частично подавляет электромагнитное излучение других источников). Скорость передачи до 1 Мбит/с. Используется в телефонных сетях и для передачи данных.

2. Коаксиальный кабель. Скорость передачи 10–100 Мбит/с – используется в локальных сетях, кабельном телевидении и т.д.

3. Оптико-волоконная. Скорость передачи 1 Гбит/с.

В средах 1–3 затухание в дБ линейно зависит от расстояния, т.е. мощность падает по экспоненте. Поэтому через определенное расстояние необходимо ставить регенераторы (усилители).

Радиолинии:

1.Радиоканал. Скорость передачи 100–400 Кбит/с. Использует радиочастоты до 1000 МГц. До 30 МГц за счет отражения от ионосферы возможно распространение электромагнитных волн за пределы прямой видимости. Но этот диапазон сильно зашумлен (например, любительской радиосвязью). От 30 до 1000 МГц – ионосфера прозрачна и необходима прямая видимость. Антенны устанавливаются на высоте (иногда устанавливаются регенераторы). Используются в радио и телевидении.

2.Микроволновые линии. Скорости передачи до 1 Гбит/с. Используют радиочастоты выше 1000 МГц. При этом необходима прямая видимость и остронаправленные параболические антенны. Расстояние между регенераторами 10–200 км. Используются для телефонной связи, телевидения и передачи данных.

3. Спутниковая связь . Используются микроволновые частоты, а спутник служит регенератором (причем для многих станций). Характеристики те же, что у микроволновых линий.

2. Пропускная способность дискретного канала связи

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

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

При передаче каждого символа в среднем по каналу связи проходит количество информации, определяемое по формуле

I (Y, X) = I (X, Y) = H(X) – H (X/Y) = H(Y) – H (Y/X) , (2)

где: I (Y, X) – взаимная информация, т.е.количество информации, содержащееся в Y относительно X ; H(X) – энтропия источника сообщений; H (X/Y) – условная энтропия, определяющая потерю информации на один символ, связанную с наличием помех и искажений.

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

I(Y T , X T) = H(X T) – H(X T /Y T) = H(Y T) – H(Y T /X T) = n . (4)

Скорость передачи информации зависит от статистических свойств источника, метода кодирования и свойств канала.

Пропускная способность дискретного канала связи

. (5)

Максимально-возможное значение, т.е. максимум функционала ищется на всем множестве функций распределения вероятности p(x) .

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

2.1 Дискретный канал связи без помех

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

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

I (X, Y) = H(X) = H(Y); H (X/Y) = 0.

Если Х Т – количество символов за время T , то скорость передачи информации для дискретного канала связи без помех равна

(6)

где V = 1/ – средняя скорость передачи одного символа.

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

(7)

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

. (8)

Первая теорема Шеннона для канала:Если поток информации, вырабатываемый источником, достаточно близок к пропускной способности канала связи, т.е.

, где - сколь угодно малая величина,

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

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

Пример 1. Источник вырабатывает 3 сообщения с вероятностями:

p 1 = 0,1; p 2 = 0,2 и p 3 = 0,7.

Сообщения независимы и передаются равномерным двоичным кодом (m = 2 ) с длительностью символов, равной 1 мс. Определить скорость передачи информации по каналу связи без помех.

Решение: Энтропия источника равна

[бит/с].

Для передачи 3 сообщений равномерным кодом необходимо два разряда, при этом длительность кодовой комбинации равна 2t.

Средняя скорость передачи сигнала

V =1/2 t = 500 .

Скорость передачи информации

C = vH = 500 × 1,16 = 580 [бит/с].

2.2 Дискретный канал связи с помехами

Мы будем рассматривать дискретные каналы связи без памяти.

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

В любой системе связи через канал передается информация. Ее скорость передачи была определена в § 4.2. Как видно из (4.25), эта скорость зависит не только от самого канала, но и от свойств подаваемого на его вход сигнала и поэтому не может характеризовать канал как средство передачи информации. Попытаемся найти способ оценки способности канала передавать информацию. Рассмотрим вначале дискретный канал, через который передаются в единицу времени v символов из алфавита объемом m. При передаче каждого символа в среднем по каналу проходит количество информации

I(A, В) = Н(А) - Н(А|В) = Н(В) - Н(В|А), (4.35)

где А и В - случайные символы на входе и выходе канала. Из четырех фигурирующих здесь энтропий H(A) - собственная информация передаваемого символа определяется источником дискретного сигнала * и не зависит от свойств канала. Остальные три энтропии в общем случае зависят как от источника сигнала, так и от канала.

* (Источником дискретного сигнала в системе связи (см. рис. 1.5) является совокупность источника сообщения и кодера. )

Представим себе, что на вход канала можно подавать символы от разных источников, характеризуемых различными распределениями вероятностей Р(А) (но, конечно, при тех же значениях m и v). Для каждого такого источника количество информации, переданной по каналу, принимает свое значение. Максимальное количество переданной информации, взятое по всевозможным источникам входного сигнала, характеризует сам канал и называется пропускной способностью канала в расчете на один символ

где максимизация * производится по всем многомерным распределениям вероятностей Р(A). Можно также определить пропускную способность С канала в расчете на единицу времени (например, секунду):

* (Если такого максимума не существует (что может быть при бесконечном числе возможных источников), то пропускная способность определяется как наименьшая верхняя грань sup I(А, В), т. е. такая величина, к которой I(А, B) может сколь угодно приблизиться, но не может ее превзойти. )

Равенство (4.37) следует из аддитивности энтропии. В дальнейшем везде, где это особо не оговорено, под пропускной способностью понимать будем пропускную способность в расчете на секунду.

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

Величина

в данном случае легко вычисляется, поскольку условная (переходная) вероятность P(b j |a i) принимает только два значения: p/(m-1), если b j ≠a i и 1-р, если b j = a i . Первое из этих значений возникает с вероятностью р, а второе - с вероятностью 1-р. К тому же, поскольку рассматривается канал без памяти, результаты приема отдельных символов независимы друг от друга. Поэтому

Следовательно, Н(В|А) не зависит от распределения вероятности в ансамбле А, а определяется только переходными вероятностями канала. Это свойство сохраняется для всех моделей канала с аддитивным шумом.

Подставив (4.38) в (4.37), получим

Поскольку в правой части только член Н (В) зависит от распределения вероятностей Р(А), то максимизировать необходимо его. Максимальное значение Н (В) согласно (4.6) равно log m и реализуется оно тогда, когда все принятые символы b j равновероятны и независимы друг от друга. Легко убедиться, что это условие удовлетворяется, если входные символы равновероятны и независимы, поскольку в этом случае

При этом Н(В) = log m и

Отсюда пропускная способность в расчете на единицу времени

Для двоичного симметричного канала (m = 2) пропускная способность в двоичных единицах в единицу времени

С = v (4.42)

Зависимость C/v от р согласно (4.42) показана на рис. 4.3.

При р = 1/2 пропускная способность двоичного канала С = 0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить совсем не передавая сигналы по каналу, а выбирая их наугад (например, по результатам бросания монеты), т. е. при р=1/2 последовательности на выходе и входе канала независимы. Случай С = 0 называют обрывом канала. То, что пропускная способность при р = 1 в двоичном канале такая же, как при р=0 (канал без шумов), объясняется тем, что при р = 1 достаточно все выходные символы инвертировать (т. е. заменить 0 на 1 и 1 на 0), чтобы правильно восстановить входной сигнал.

Пропускная способность непрерывного к а н а- л а вычисляется аналогично. Пусть, например, канал имеет ограниченную полосу пропускания шириной F. Тогда сигналы U(t) и Z{t) соответственно на входе и выходе канала по теореме Котельникова определяются своими отсчетами, взятыми через интервал 1/(2F), и поэтому информация, проходящая по каналу за некоторое время Т, равна сумме количества информации, переданной за каждый такой отсчет * . Пропускная способность канала на один такой отсчет

Здесь U и Z - случайные величины - сечения процессов U(t) и Z(t) на входе и выходе канала соответственно и максимум берется по всем допустимым входным сигналам, т. е. по всем распределениям U.

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

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

Вычислим, например, пропускную способность непрерывного канала без памяти с аддитивным белым гауссовским шумом, имеющим полосу пропускания шириной F, если средняя мощность сигнала (дисперсия U) не превышает заданной величины Р с. Мощность (дисперсию) шума в полосе F обозначим Р ш. Отсчеты входного и выходного сигналов, а также шума N связаны равенством

Z = U + N. (4.44)

Так как N имеет нормальное распределение с нулевым математическим ожиданием, то и условная плотность вероятности w(z|u) при фиксированном и будет также нормальной - с математическим ожиданием и и дисперсией Р ш.

Найдем пропускную способность на один отсчет (4.43):

Согласно (4.34) дифференциальная энтропия h(Z|U) нормального распределения w(Z|U) не зависит от математического ожидания и равна

Поэтому для нахождения С отсч следует найти такую плотность распределения w(U), при которой максимизируется h(Z). Из (4.44) учитывая, что U и N - независимые случайные величины, имеем для дисперсий:

D(Z) = D(U) + D(N) = P c + P ш. (4.45)

Таким образом, дисперсия Z фиксирована, так как Р с и Р ш заданы. Как было отмечено (см. стр. 114), при фиксированной дисперсии максимальная дифференциальная энтропия обеспечивается нормальным распределением. Из (4.44) видно, что при нормальном одномерном распределении U распределение Z будет также нормальным и, следовательно, обеспечивается максимум дифференциальной энтропии (4.34):

Переходя к пропускной способности С в расчете на секунду, заметим, что информация, переданная за несколько отсчетов, максимальна в том случае, когда отсчеты сигналов независимы. Этого можно достичь, если сигнал U(t) выбрать так, чтобы его спектральная плотность была равномерной в полосе F. Как было показано в § 2.2 [см. (2.48)], отсчеты, разделенные интервалами, кратными 1/(2F), взаимно некоррелированы, а для гауссовских величин некоррелированность означает независимость.

Поэтому пропускную способность С (за секунду) можно найти, сложив пропускные способности (4.46) для 2F независимых отсчетов:

С = 2FC отсч = F log (1 +Р с /Р ш). (4.47)

Она реализуется, если U(t) - гауссовский процесс с равномерной спектральной плотностью в полосе частот F (квазибелый шум).

Из (4.47) видно, что если бы мощность сигнала Р с не была ограничена, то пропускная способность была бы сколь угодно большой. Пропускная способность равна нулю, если отношение сигнал-шум Р с /Р ш в канале равно нулю. С ростом этого отношения пропускная способность увеличивается неограниченно, однако медленно, вследствие логарифмической зависимости.

Соотношение (4.47) часто называют формулой Шеннона. Эта формула имеет важное значение в теории информации, так как определяет зависимость пропускной способности рассматриваемого непрерывного канала от таких его технических характеристик, как ширина полосы пропускания и отношение сигнал-шум. Формула Шеннона указывает на возможность обмена полосы пропускания на мощность сигнала, и наоборот. Однако поскольку С зависит от F линейно, а от Р с /Р ш - по логарифмическому закону, компенсировать возможное сокращение полосы пропускания увеличением мощности сигнала, как правило, не выгодно. Более эффективным является обратный обмен мощности сигнала на полосу пропускания.

Заметим, что при Р c /P ш >>1 выражение (4.50) совпадает с характеристикой (1.2), названной в § 1.2 емкостью (объемом) канала.

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

На рис. 4.5 показаны зависимости С/F от среднего отношения Р с /Р ш для канала с постоянными параметрами (1) и канала с рэлеевскими замираниями (2). Из анализа кривых следует, что медленные рэлеевские замирания уменьшают пропускную способность канала не более чем на 17%.

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

При наличии помех часть информации источника теряется и скорость передачи информации оказывается меньшей, чем производительность источника. Одновременно в сообщение на выходе канала добавляется информация о помехах (рис.5).

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

бит/с. (22)

На основании формулы (20) имеем

где H¢(x) - производительность источника;

H¢(x/y) - "ненадёжность" канала(потери) в единицу времени;

H¢(y) - энтропия выходного сообщения в единицу времени;

H¢(y/x) =H’(n) –энтропия помех (шума) в единицу времени.

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

. (24)

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

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

В канале без помех C=max H¢(x) , так как H¢(x/y)=0 . При использовании равномерного кода с основанием k , состоящего из n элементов длительностью tэ , в канале без помех

,

при k =2 бит/c. (25)

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

1-ая теорема (для канала связи без помех):

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

К.Шеннон предложил и метод такого кодирования, который получил название статистического или оптимального кодирования. В дальнейшем идея такого кодирования была развита в работах Фано и Хаффмена и в настоящее время широко используется на практике для “cжатия сообщений”.

2-ая теорема (для каналов связи с помехами):

Если пропускная способность канала равна C, а производительность источника H’(x)C, то можно закодировать источник таким образом, что ненадёжность будет меньше, чем H’(x)-C+e, где e. – сколь угодно малая величина.

Не существует способа кодирования, обеспечивающего ненадёжность, меньшую, чем H"(x)-C.

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

. (26)

Cледовательно, имеет место “обмен” верности передачи на скорость и задержку передачи.

Вопросы

1. Что такое пропускная способность канала связи, как она определяется?
2. Чему равна пропускная способность канала связи без помех?
3. Как влияют помехи на величину пропускной способности?
4. Что утверждает теорема Шеннона для канала связи без помех?
5. Что утверждает теорема Шеннона для канала связи с помехами?

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

Определения:

1. Скорость передачи информации – среднее количество информации, передаваемой через канал за единицу времени.

В случае канала без шума эта скорость равна V к *H к , где V к – количество символов, передаваемых через канал в единицу времени, H к – средняя энтропия одного символа сообщения на входе и выходе канала.

2. Производительность источника – средняя скорость поступления информации от источника сообщений.

Производительность источника находится по формуле V и *H и , где V и – количество символов, генерируемых источником в единицу времени, H и – средняя энтропия одного символа сообщения на выходе источника.

Пропускная способность канала связи – максимально возможная для данного канала скорость передачи информации. Будем обозначать ее С к .

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

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

Учитывая это: С к =V к * H max = V к * log 2 m .

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

В этом случае С к =V к.

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

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

Будем описывать источник информации параметрами V и и H и . Допустим, шум в канале связи отсутствует. Канал связи описывается своей пропускной способностью и объемом m алфавита.

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

С к =V к max * log 2 m = V и * H и.

Таким образом, если известна средняя энтропия одного символа сообщения, поступающего с выхода источника, наиболее эффективного использования канала можно достичь, если скорость поступления этих символов от источника выбрать в соответствии с формулой: V и =V к max * log 2 m / H и или V и =V к max / H и при использовании наиболее часто употребляемого двоичного кодирования.

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

Рассмотрим следующую модель канала связи с помехами (рис. 4.4):

Рис. 4.4. Модель канала связи с помехами.

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

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

С= V k *I m а x ,

где V k – скорость передачи символов алфавита через канал;

I m а x – максимально возможное количество информации, приходящейся на один передаваемый через канал символ.

Количество информации, приходящееся на 1 передаваемый через канал символ зависит от энтропии (степени неопределенности получения символа) на входе и выходе канала. Согласно мере Шеннона

I = H априорная - H апостериорная = H(X) – H(X/Y) .

Здесь H априорная = H(X) и H апостериорная = H(X/Y) – условная энтропия, характеризующая неопределенность о переданном на выход канала символе X по принятому символу Y на выходе. Наличие этой неопределенности – следствие действия на передаваемый через канал символ помех. H(X/Y) – характеристика канала.

Конец работы -

Эта тема принадлежит разделу:

Теория информации и кодирования

Сочинский государственный университет.. туризма и курортного дела.. Факультет информационных технологий и математики..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Твитнуть

Все темы данного раздела:

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

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

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

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

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

Геометрическая мера
Определение количества информации геометрическим методом сводится к измерению длины линии, площади или объема геометрической модели данного носителя информации или сообщения. По геометрическим разм

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

Энтропия и ее свойства
Существует несколько видов статистических мер информации. В дальнейшем будем рассматривать только одну их них ─ меру Шеннона. Мера Шеннона количества информации тесно связана с понятие

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

Метод множителей Лагранжа
Если нужно найти экстремум (максимум, минимум или седловую точку) функции n переменных f(x1, x2, …, xn), связанных k

Вывод формулы среднего значения энтропии на букву сообщения
Предположим, имеется сообщение, состоящее из n букв: , где j=1, 2, …, n ─ номера букв в сообщении по порядку, а i1, i2, … ,in номера букв

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

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

Содержательность информации
Мера содержательности обозначается cont (от английского Content ─ содержание). Содержательность события I выражается через функцию меры содержательности его о

Целесообразность информации
Если информация используется в системах управления, то ее полезность разумно оценивать по тому эффекту, который она оказывает на результат управления. В связи с этим в 1960 г. советским ученым А.А.

Динамическая энтропия
Здесь энтропия рассматривается как функция времени. При этом преследуется цель – избавиться от неопределенности, т.е. добиться положения, когда энтропия равна 0. Такая ситуация характерна для задач

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

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

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

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

Виды дискретизации (квантования)
Наиболее простыми и часто используемыми видами квантования являются: · квантование по уровню (будем говорить просто квантование); · квантование по времени (будем называть

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

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

О практическом использовании теоремы Котельникова
Возможную схему квантования-передачи-восстановления непрерывного сигнала можно представить в виде, изображенном на рис. 2.5. Рис. 2.5. Возможная схема квантования-передачи-

Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения
В результате квантования по времени функции x(t) получается ряд значений x(t1), x(t2), … квантуемой величины x(t) в дискретные моменты времени t

Интерполяция при помощи полиномов Лагранжа
Воспроизводящая функция в большинстве случаев рассчитывается по формуле: , где − некоторые функции. Эти функции обычно стремятся выбрать так, чтобы. (2.14) В этом случае,

Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа
Найдем погрешность интерполяции. Представим ее виде: , (2.16) где K(t) – вспомогательная функция, которую надо найти. Для произвольного t* имеем: (

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

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

Оптимальное квантование по уровню
Рисунком 2.13 иллюстрируется принцип квантования по уровню. Рис. 2.13. Квантование по уровню. Это квантование сводится к замене значения исходного сигнала уровн

Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования
Рис. 2.19. Обозначения Зададимся теперь числом шагов квантования n, границами интервала (xmin, xmax

Общие понятия и определения. Цели кодирования
Кодирование − операция отождествления символов или групп символов одного кода с символами или группами символов другого кода. Код (франц. code), совокупность зна

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

Неравенство Крафта
Теорема 1. Если целые числа n1, n2, …, nk удовлетворяют неравенству, (3.1) существует префиксный код с алфавитом объемом m,

Теорема 2.
Формулировка. Пусть задан код с длинами кодовых слов n1, n2, … , nk и с алфавитом объема m. Если код однозначно декодируем, неравенство Крафта удовле

Теорема 3.
Формулировка. При заданной энтропии H источника и объеме m вторичного алфавита существует префиксный код с минимальной средней длиной nср min

Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)
Рассмотрим теперь случай кодирования не отдельных букв источника, а последовательностей из L букв. Теорема 4. Формулировка. Для данного дискретного источника

Оптимальные неравномерные коды
Определения. Неравномерными называют коды, кодовые слова которых имеют различную длину. Оптимальность можно понимать по-разному, в зависимости о

Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв
Формулировка. Для любого источника с k>=2 буквами существует оптимальный (в смысле минимума средней длины кодового слова) двоичный код, в котором два наименее вероятных сло

Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален
Формулировка. Если некоторый префиксный код редуцированного ансамбля U"является оптимальным, то соответствующий ему префиксный код исходного ансамбля т

Особенности эффективных кодов
1. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р

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

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

Расчет вероятности искажения кодового слова в ДСМК
Положим, кодовое слово состоит из n двоичных символов. Вероятность неискажения кодового слова, как несложно доказать, равна: . Вероятность искажения одного символа (однокра

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

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

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

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

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

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

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

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

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

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

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

Матричное описание циклических кодов
Циклические коды можно, как и любые линейные коды, описывать с помощью матриц. Вспомним, что KC(X) = gm(X)*И(Х) . Вспомним также на примере порядок умножения пол

Выбор образующего полинома
Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином g(X) без остатка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует

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

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

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

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

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

Пропускная способность непрерывного канала при наличии аддитивного шума
Рассмотрим следующую модель канала: 1. Канал способен пропускать колебания с частотами ниже Fm. 2. В канале действует помеха n(t), имеющая нормальный (гау

Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы
При вводе ранее сохраненного текстового файла следует указать тип файла *.*. Это позволит во время выбора видеть в списке все файлы. Укажите свой файл. После этого на экран будет выведено окно М

Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения
Как описано в теоретическом введении, средняя энтропия находится по формулам 1 и 2. В обоих случаях нужно найти вероятности появления букв или двухбуквенных комбинаций.. Вероятности можно

Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты
Результаты вычислений представьте в виде таблицы: <Язык 1> <Язык

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

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

Запись голоса и подготовка сигнала
Запись начинается и заканчивается нажатием кнопки Record (рис. 5), помеченной красный кружком. В процессе записи кнопка Recоrd выглядит вдавленной и более светлой (подсвеченной).

Импорт текстовых данных в Excel
Двойным кликом откройте текстовый файл с экспортированные из программы Wavosaur данными (рис. 23). Рис. 23. Примерный вид данных Видно, что экспортированные

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

Коды Хаффмена
На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году доктором Массачусетского технологического института (США) Дэвидэм Хаффменом: 5) буквы перви

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

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

Особенности эффективных кодов
5. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р

Выполнение работы
Лабораторная работа №4 выполняется под управлением специально написанной управляющей программы. Эта управляющая программа написана на языке Visual Basic 6. Исполняемый файл программы носит и

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

Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||: ||KC1*n|| = ||X

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

Выполнение работы
Лабораторная работа №5, как и работа №4, выполняется под управлением управляющей программы, написанной на алгоритмическом языке Visual Basic 6. Исполняемый файл программы носит имя Помехо

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

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

Пропускная способность рассчитывается по формуле:

Для двоичного симметричного канала (m=2) пропускная способность в двоичных единицах на секунду (Бодах):

При пропускная способность двоичного канала С=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить, совсем не передавая сигналы по каналу, а выбирая их наугад (например, по результатам бросания монеты), т.е. последовательности на выходе и входе канала независимы. Случай С=0 называют обрывом канала. То, что пропускная способность при в двоичном канале такая же, как при (канал без шумов), объясняется тем, что при достаточно все выходные символы инвертировать (т.е. заменить 0 на 1 и 1 на 0), чтобы правильно восстановить входной сигнал.

Производительность источника информации равна:

кбит/с (7.3)

Рассчитаем пропускную способность канала с оптимальным приёмником по формуле

кбит/с(7.2):

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

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

приемник кодирование аналоговый сигнал

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

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

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

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

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

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

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

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

Ошибка обнаруживается всегда, если её кратность, т.е. число искаженных символов в кодовой комбинации: qd, то некоторые ошибки также обнаруживаются. Однако полной гарантии обнаружения ошибок нет, т.к. ошибочная комбинация может совпадать с какой-либо разрешенной комбинацией. Минимальное кодовое расстояние, при котором обнаруживаются любые одиночные ошибки: d=2.

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

Простейший систематический код (n, n-1) строится путём добавления к комбинации из n-1 информационных символов одного проверочного, равного сумме всех информационных символов по модулю 2. Легко видеть, что эта сумма равна нулю, если среди информационных символов содержится чётное число единиц, и равна единице, если число единиц среди информационных символов нечётное. После добавления проверочного символа образуются кодовые комбинации, содержащие только чётное количество единиц. Такой код имеет, поскольку две различные кодовые комбинации, содержащие по четному числу единиц, не могут различаться в одном разряде. Следовательно, он позволяет обнаружить одиночные ошибки. Легко убедиться, что, применяя этот код в схеме декодирования с обнаружением ошибок, можно обнаруживать все ошибки нечетной кратности. Для этого достаточно подсчитать число единиц в принятой комбинации и проверить, является ли оно четным. Если при передаче комбинации произойдут ошибки в нечетном числе разрядов q, то принятая комбинация будет иметь нечетный вес и, следовательно, окажется запрещенной. Такой код называют кодом с одной проверкой на четность.

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

где - число ошибочных комбинаций:

Таким образом, учитывая, что, используя формулы (8.1) и (8.2), найдём вероятность необнаружения ошибки:

Определим избыточность рассчитанного канала связи, используя результаты расчётов, произведённых в параграфе 7, используя результаты формул (7.2) и (7.3):

Избыточность кода Бодо (6,5)

Избыточность кода Хэмминга (7,4)

При сравнении (8.3), (8.4) и (8.5) заметно, что избыточность канала позволяет применить только обнаруживающий код Бодо (6,5) с проверкой на чётность.

Рассчитаем вероятность ошибки корректирующего кода, учитывая оставшееся свободное время (см. п. 3):

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