Сайт о телевидении

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

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

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

Рис. 7.1.

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

При передаче сообщения по ДСК в каждом бите сообщения с вероятностью может произойти ошибка, независимо от наличия ошибок в других битах. Ошибка заключается в замене знака 0 на 1 или 1 на 0.

Некоторые типы ошибок:

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

Способы повышения надежности передачи сообщений

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

Тогда закодированное сообщение имеет вид 011011100110. Если в первом знаке произойдет ошибка, то будет принято сообщение 111011100110, которое декодируется в слово . Полное искажение сообщения из-за одной ошибки происходит вследствие того, что одно кодовое слово переходит в другое кодовое слово в результате замены одного или нескольких знаков. Пример показывает, что оптимальное кодирование плохо защищает сообщения от воздействия ошибок.

На практике необходим компромисс между экономностью кода и защитой от ошибок.

Сначала удаляется "бесполезная" избыточность (в основном статистическая), а затем добавляется "полезная" избыточность , которая помогает обнаруживать и исправлять ошибки.

Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие :

1. передача в контексте;
2. дублирование сообщений;
3. передача с переспросом.

Рассмотрим подробней каждый из этих способов.

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

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

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

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

Принципы обнаружения и исправления ошибок с использованием кодов

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

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

Рассмотрим схему передачи данных, показанную на рис.7.3 .

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

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

В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства , где . Точки этого пространства представляют собой последовательности чисел 0 и 1 длины . Пространства для можно представить в виде угловых точек единичного интервала (), вершин квадрата со стороной, равной 1 (), и вершин куба с ребрами длины 1 (). Эти пространства условно изображены на рис.7.5 .

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

Граф переходных вероятностей для такого канала может быть представлен на рис. 9.

Определим С:

Рис. 9. Граф переходных вероятностей К-ичного симметричного канала связи.

Канал со стиранием

Канал со стиранием

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

Рассмотрим двоичный симметричный канал связи со стиранием.

Рис. 10 Граф переходных вероятностей двоичного симметричного канала со стиранием

q – вероятность правильного приема;
p0 – вероятность ошибочного приема символа;
pC – вероятность получения стертого символа;
yЗ – символ стирания.

Если UС> UП2 , то фиксируется символ “1”.
Если UС< UП1 , то фиксируется символ “0”.
Если UП1 Ј UC Ј UП2 , то фиксируется символ стирания.

В канале связи могут возникать ошибки двух типов: ошибки трансформации и ошибки стирания.

Ошибка трансформации возникает с вероятностью p 0и для двоичного канала связи физически означает трансформацию “0” в “1” или “1” в “0”.

Ошибка стирания возникает с вероятностью pC . Под ней понимают прием вместо “1” или “0” какого-то третьего символа (символа стирания), который указывает на позицию искаженного символа.

Для двоичного симметричного канала связи ошибки трансформации и стирания не зависят от значения передаваемого символа.

Для канала со стиранием выполняется соотношение

p 0+ pC+ q = 1.

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

c = B [H (Y ) – H (Y/X )];

max H [Y ] обеспечивается при p (x 1) = p (x 2) = 0,5.

Равная вероятность приема символа yi имеет место при условии равной вероятности передачи xi , которое является необходимым, но еще недостаточным.

Будем считать, что p (x1 ) = p (x2 ) = 0,5. Тогда энтропия приемника будет максимальной.

В силу симметрии

Окончательно можно записать

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

1. pC= 0

· pC = 0, p 0= 0 (двоичный симметричный канал связи без стирания); c = B .

· pC № 0, p 0= 0 ; этот случай иллюстрирует ситуацию при отсутствии помех в канале связи и применении стирания. При этом скорость передачи информации уменьшается за счет применения стирания;

pC № 0, p 0№ 0 ; в этой ситуации канал связи может быть более “скоростным” лишь при выполнении определенных условий, о которых будет сказано ниже.

Обобщим изложенное по поводу ошибок, возникающих в канале связи.

В “обычном” канале связи возможна ошибка только одного вида: символ одного значения преобразуется в символ другого значения (то есть трансформируется). Такая ошибка называется ошибкой трансформации.

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

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

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

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

Описание

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

ДСК часто употребляется теоретиками как простейший канал с шумом . В теории связи множество проблем сводится к ДСК.

Определение

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

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

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

Пропускная способность ДСК

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

Cм. также

Wikimedia Foundation . 2010 .

Смотреть что такое "Двоичный симметричный канал" в других словарях:

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

- (англ. channel, data line) система технических средств и среда распространения сигналов для передачи сообщений (не только данных) от источника к получателю (и наоборот). Канал связи, понимаемый в узком смысле (тракт связи),… … Википедия

Канал связи, переходная функция к рого обладает тем или иным свойством симметрии. Однородный канал без памяти с дискретным временем и конечными пространствами состояний У и компонент сигналов на входе и выходе, задаваемый матрицей переходных… … Математическая энциклопедия

Раздел математики, исследующий процессы хранения, преобразования и передачи информации. В основе его лежит определенный способ измерения количества информации. Возникшая из задач теории связи, теория информации иногда рассматривается как… … Энциклопедия Кольера - Терминология ГОСТ 22670 77: Сеть связи цифровая интегральная. Термины и определения оригинал документа: 10. n ичный сигнал электросвязи n агу digital signal Цифровой сигнал электросвязи, имеющий п возможных состояний представляющего параметра,… … Словарь-справочник терминов нормативно-технической документации

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

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

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

При наличии помехи среднее количество информации в принятом символе сообщении - Y , относительно переданного - X равно:

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

I(Y T , X T ) = H(X T ) - H(X T /Y T ) = H(Y T ) - H(Y T /X T ) = n , в котором каждый символ передается в течении Т s сек. Для этого канала

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

Теорема 7.6.1. Теорема кодирования для канала (теорема Шенно-на).

Для источника X со скоростью R = H (X )/ T S [бит/сек] и R < С существует некоторый код. с помощью которого информация источ-ника X может быть передана но каналу связи с пропускной способ-ностью С 1 [бит/сек] со сколь угодно малой вероятностью ошибки.*

* Теорема кодирования справедлива не только для дискретных каналов, она так-же верна и при передаче дискретных сообщений по непрерывным каналам. Прим. перев.

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

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

Теорема кодирования определяет также верхнюю границу для скорости передачи R .*

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

* Здесь необходимо сделать разъяснение. Существует обратная теорема кодиро-вания, которая говорит о том. что при R > С не существует никакого метода кодирования, позволяющего передавать информацию с как угодно малой веро-ятностью ошибки. Прим. перев.

Глава 8. Непрерывные источники и каналы

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

Рис. 8.1. Сигнал непрерывного источника.

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

8.1. Дифференциальная энтропия

На рисунке 8.2 показаны два непрерывных источника X и Y , свя-занные каналом (аналогично рис. 7.4). Здесь, вместо вероятностей, стоят функции плотностей распределения вероятностей стохастических переменных.

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

Рис. 8.2. Два непрерывных источника без памяти, связан-ных каналом.

Преобразуем непрерывный источник X в дискретный. Для это-го проквантуем значения аналогового выхода источника с шагом Δ (рис. 8.3).

Рис. 8.3. Оцифровка непрерывного источника с интерва-лом квантования Δ в моменты наблюдения t 0 , t 1 и т.д.

Кроме этого, как это обычно делается в теории информации, про-изведем дискретизацию источника но времени. В результате, полу-чим последовательность стохастических переменных Следуя таблице 7.2, определим взаимную информацию символов x i , и y j , где x i - значение выходного символа в момент времени t m , a x j - в момент времени t n

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

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

Замечание. Здесь, для приведения в соответствие обозначений этой главы с результатами таблицы 7.2, вместо Х т используется X , а вместо Y n - Y .

Информация источника определяется исходя из аналогичных рас-суждений

В отличие от выражения (8.3) для взаимной информации, в (8.4) появляется слагаемое, зависящее от интервала квантования Δ.

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

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

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

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

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

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

Замечание. В информационной технике за исходный параметр принимают σ 2 - дисперсию, которая определяет среднюю мощ-ность стохастического процесса [ 10]. Ясно, что с увеличением мощности передатчика, количество передаваемой информации уве-личивается и, наоборот, с увеличением мощности шумов, возрас-тает неопределенность, т.е. в единицу времени передается меньше информации.

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

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

Пример: Дифференциальная энтропия гауссовского источника.

Из (8.5) следует, что дифференциальная энтропия гауссовского источника равна

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

Численные примеры для трех, наиболее употребительных распреде-лений, приведены в таблице 8.1.

Таблица 8.1. Пример дифференциальной энтропии.

Пример: Телефония.

Практическая польза приведенных выше результатов может быть наглядно показана при помощи оценки достижений скорости пере-дачи информации (в битах) в цифровых телефонных линиях. Совре-менные стандартные методы цифровой передачи речи (логарифми-ческие РСМ) требуют затраты 8 бит на кодирование одного отсчета, при частоте отсчетов 8 кГц. Таким образом, скорость передачи речи составляет 64 кбит/сек.

Исходя из равномерного распределения вероятностей в интервале [-1,1], опытным путем получим σ 2 = 1/3. Таким образом, дифферен-циальная энтропия на один отсчет составляет

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