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

Пропускная способность дискретного (цифрового) канала

Структурная схема цифрового информационного канала показана на рис.1 [1,2].


Рис.1. Структурная схема цифрового канала

На вход такового канала обычно поступают дискретные соотношения х, к примеру, в виде текста. Последние при помощи кодирующего устройства преобразуются в кодированные сигналы у. Как понятно, для кодировки употребляется некий алфавит простых сигналов (знаков Пропускная способность дискретных каналов с шумами) – у1, у2,…, уm, а существо кодировки сводится к представлению отдельных сообщений хi либо последовательностей сообщений некими комбинациями знаков применяемого алфавита. Декодирующее устройство конвертирует кодированные сигналы z в сообщения w в форме, более применимой для получателя, которым может быть не только лишь человек, да и разные технические устройства (принтер Пропускная способность дискретных каналов с шумами, монитор, ПЭВМ и др.). В современных информационно-вычислительных комплексах начальные сообщения х могут быть и в непрерывной форме, но при помощи кодирующих устройств последние конвертируют в кодированные сигналы.

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

Пропускная способность дискретных (цифровых) каналов

При отсутствии шумов

При отсутствии шумов можно считать, что в информационном Пропускная способность дискретных каналов с шумами канале z = y, а w = x, как следует, для сообщений zT = yT, wT = xT, передаваемых за время Т, количество инфы, поступающей к получателю от источника, составит

I(WT, XT) = I(XT, XT) = H(XT),

где Н(ХТ) - энтропия источника сообщений.

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

I(ZT,YT) = I(YT, YT) = H(YT). (1.1)

Если последовательность хТ состоит из m сообщений и средняя продолжительность сигнала, обеспечивающего передачу 1-го сообщения составляет tс, то можно найти скорость передачи инфы как

, (1.2)

где Н(X) – энтропия источника n сообщений:

.

В предстоящем основание 2 логарифма для простоты будет опущено.

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

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

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

(1.3)

Обычно Cс > C.

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

Дискретный канал, в каком передаваемые сообщения представлены двоичным кодом, именуется двоичным каналом. Если код имеет m знаков (разрядов), то разумеется, что Пропускная способность дискретных каналов с шумами всего можно закодировать n = 2m сообщений, а продолжительность 1-го сообщения составит T = mt, где t - продолжительность знака кода с учетом того, что все знаки обычно имеют схожую продолжительность. Двоичные коды, состоящие из схожего числа знаков m, именуются равномерными. Пропускная способность рассматриваемого канала с учетом формул (1.1), (1.2) и Пропускная способность дискретных каналов с шумами (1.3) составит

(1.4)

Выражение (1.4) воспринимает наибольшее значение, когда энтропия ансамбля событий (сообщений) H(YT) будет большей. Из параметров энтропии следует, что H(YT) будет максимальна, если сообщения равновероятны, это наибольшее значение может быть определено мерой Хартли и будет равно logn = log2m = m [2].

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

Разглядим два обычных примера.

Пример 1. Пусть источник сообщений производит четыре сообщения х1, х2, х3, х4, (n = 4). Все сообщения имеют схожие вероятности: P(xi) = 1/n = 0,25. Для их кодировки употребляется двоичный равномерный код, число знаков в каком довольно избрать m = 2. Начальные сообщения х1, х2, х3, х Пропускная способность дискретных каналов с шумами4 в этом примере будут представлены последующими кодами: 00, 01, 10, 11.

Скорость передачи инфы будет определяться по формуле (1.2), в какой энтропия источника равновероятных сообщений будет наибольшей:

а продолжительность каждого из 4 сообщений будет определяться длительностями соответственных кодовых композиций и составит tс = 2t. Для примера 1 по формуле (1.2) находим

Таким макаром, в этом примере, как и Пропускная способность дискретных каналов с шумами следовало ждать, скорость передачи инфы оказалась равной пропускной возможности канала: = Cc = 1/t.

Пример 2. Источник сообщений и метод их кодировки такие же, как и в примере 1, но вероятности сообщения при всем этом не схожи:

Р(х1) = 0,5; Р(х2) = 0,25; Р(х3) = Р(х4) = 0,125.

Для определения скорости передачи инфы вновь воспользуемся Пропускная способность дискретных каналов с шумами формулой (1.2), для которой нужно вычислить соответственное значение энтропии Н(х) для источника разновероятных сообщений х1, х2, х3, х4 (n = 4):

Продолжительности всех сообщений остаются такими же, как и в примере 1:

tс = 2t. Скорость передачи инфы составит

В этом примере скорость передачи инфы оказалась меньше пропускной возможности двоичного канала Cс(0,875/t < 1/t).

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

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

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

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

Записывают сообщения в порядке убывания их вероятностей.

Проводят 1-ое деление всех сообщений на две подгруппы I и II так, чтоб сумма вероятностей сообщений в подгруппах I и II была бы по способности Пропускная способность дискретных каналов с шумами схожей. В этом случае это условие производится точно: при первом делении в подгруппу I заходит сообщение х1, возможность которого равна 0,5, а в подгруппу II входят сообщения х2, х3, х4, сумма вероятностей которых (0,25+0,125+0,125) будет тоже составлять 0,5.

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

Номер подгруппы, в которую попадает данное сообщение при каждом делении, определяет знак на соответственной позиции кода этого сообщения. В рассматриваемой таблице принадлежность к подгруппе I обозначается эмблемой 0, а к подгруппе II – эмблемой 1. Так, а Пропускная способность дискретных каналов с шумами именно, 1-ое деление отдало на первой позиции кода для сообщения x1 знак 0, а для других сообщений – знак 1.

Таблица 1

Сообще-ние xi Вероят- ность р(хi) Номер деления на подгруппы Знак кода Продолжительность кодовой композиции ti
Позиции
х1 0,5 1t
х2 0,25 2t
х3 0,125 3t
х4 0,125 3t

Как надо из таблицы Пропускная способность дискретных каналов с шумами 1, приобретенный код является неравномерным, т.е. сигналы различных сообщений имеют различное число знаков, как следует разную продолжительность. Для наглядности в таблице 2 для сообщений х1, х2, х3, х4 приведены неравномерный код Шеннона - Фано и равномерный, применяемый ранее в примерах 1 и 2. Анализируя неравномерный код Шеннона - Фано, можно убедиться в том, что более Пропускная способность дискретных каналов с шумами возможному сообщению соответствует самая маленькая кодовая композиция, менее возможному – длинноватая. Этим можно разъяснить ускорение передачи инфы при использовании данного кода.

Таблица 2

Сообщение xi Код Шеннона - Фано Равномерный код
x1
x2
x3
x4

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

Для вычисления скорости передачи инфы Пропускная способность дискретных каналов с шумами при использовании кода Шеннона - Фано воспользуемся формулой (1.2), применительно к которой, как и в примере 2, Н(Х) = 1,75, .

Как отмечалось выше, код Шеннона - Фано является неравномерным. Потому целенаправлено найти среднюю продолжительность сигнала tс 1-го сообщения, определяемую по формуле математического ожидания продолжительности ti сообщения xi [по аналогии с энтропией Н Пропускная способность дискретных каналов с шумами(Х)]:

.

Для избранного примера по таблице 1 (n = 4) находим tс = 1,75t, что позволяет считать кодовую комбинацию состоящей в среднем из m = 1,75 знаков.

По формуле (1.2) для приобретенных значений Н(Х) и tс находим скорость передачи:

.

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

Равномерный код, как отмечалось в примере 2, не является действенным. Это можно разъяснить тем, что при использовании действенного кода Шеннона - Фано сигнал каждого сообщения в среднем состоит из 1,75 знаков, а при использовании равномерного кода – из 2-х (таблица 2). Из чего Пропускная способность дискретных каналов с шумами следует, что в единицу времени сообщений, представленных кодом Шеннона - Фано, будет передано больше, чем при использовании равномерного кода.

Нужно увидеть и то, что, действуя по правилу построения кода Шеннона - Фано для 4 равновероятных сообщений, рассмотренных в примере 1, получаем приведенный в таблице 2 равномерный код, который в этом случае является действенным Пропускная способность дискретных каналов с шумами.

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

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

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

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

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

Для дискретного канала с шумами (рис.1) количество инфы, содержащейся в последовательности выходных сигналов zT о входных сигналах YT , cоставит [2]

I(ZT Пропускная способность дискретных каналов с шумами,YT) = H(ZT) – H(ZT|YT) = H(YT) – H(YT|ZT) , (1.5)

где H(ZT|YT) и H(YT|ZT) – условные энтропии.

Для последовательности сообщений продолжительностью Т, содержащей m сигналов источника, имеем

H(ZT)= mH(Z), (1.6)

где H(Z) – энтропия выходного сигнала либо энтропия выхода канала, рассматриваемого как эргодический Пропускная способность дискретных каналов с шумами источник.

Аналогично для условной энтропии выхода канала запишем

H(ZT|YT) = mH(Z|Y). (1.7)

Тогда из (1.5)-(1.7) находим

I(ZT,YT) = mH(Z) - mH(Z|Y) .(1.8)

Скорость передачи в дискретном канале с шумами с учетом (1.8) составит

,(1.9)

где – средняя продолжительность сигнала 1-го сообщения.

Аналогично с учетом (1.5) найдем

. (1.10)

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

Из соотношений (1.9) и (1.10) пропускная способность канала может быть определена из условия:

. (1.11)

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

На выходе канала употребляется решающее устройство (РУ), при помощи которого принимаемые сигналы делятся на две области z0 и z1 так, что если сигнал попадает в область z0, то считается (принимается решение), что был Пропускная способность дискретных каналов с шумами передан сигнал y0, а если в z1, то – у1.

Решающее устройство допускает принятие и неверных решений. К примеру, сигнал у1 может быть искажен помехой так, что он оказывается в области z0, в итоге чего РУ воспринимает неверное решение, возможность которого обозначим P(z0½y1) = PI. Аналогичное неверное решение может Пропускная способность дискретных каналов с шумами быть принято и для сигнала у0. Возможность этого решения составит P(z1½y0) = PII.

Разумеется, что при данных обозначениях вероятности правильного решения будут P(z0½y0) = 1 – PII и P(z1½y1) = 1 - PI. Ради сокращенности записи обозначим априорные вероятности передачи сигналов P(y0) = P0 и P Пропускная способность дискретных каналов с шумами(y1) = P1 = 1 - P0 . Для рассматриваемого двоичного канала введенные обозначения схематично показаны на рис. 2 в виде последующей модели.


Рис. 2. Модель двоичного канала

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

(1.12)

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

либо в принятых обозначениях вероятностей с учетом Пропускная способность дискретных каналов с шумами (1.12)

(1.14)

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

Для иллюстрации изложенного разглядим в качестве примера симметричный двоичный канал без памяти. В Пропускная способность дискретных каналов с шумами этом канале PI = PII = Pош, т.е. вероятности неверного приема сигналов (знаков) у0 и у1 схожи. Тогда из (1.14) находим

.

Разумеется, не находится в зависимости от Р0. В таком случае скорость передачи инфы (1.9) будет наибольшей, когда величина воспринимает наибольшее значение. Из параметров энтропии следует, что это условие производится, когда P(z0) = P(z Пропускная способность дискретных каналов с шумами1) = 0,5 и в данном случае .

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

. (1.15)

Как отмечалось выше, для заслуги наибольшей скорости передачи инфы нужно в кодирующем устройстве обеспечить такое формирование знаков кода, при котором Р0 = Р0опт. Значение Р0опт можно вычислить из выражений (1.12), приняв во внимание PI = PII = Pош Пропускная способность дискретных каналов с шумами и P(z0) = P(z1). Методом вычитания из (1.12) находим

Р0опт(1 – Рош) + (1 – Р0опт)Рош – (1 – Р0опт)(1 – Рош) – Р0оптРош = 0.

Дальше можем получить 1–2Р0опт =2Рош(1–2Р0опт), откуда Р0опт= 0,5.

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

На рис. 3 приведен график зависимости Ссt от Рош, приобретенный из формулы (1.15).

Pош

Рис. 3. График зависимости Ссt от Рош

Как видно из этого графика, при Рош = 0,5 пропускная способность канала Сс = 0. Этот итог станет естественным, если учитывать, что для значения Рош = 0,5 при Пропускная способность дискретных каналов с шумами передаче каждого из знаков на выходе канала с равной вероятностью может быть принято решение z0 и z1. Эти решения могут иметь такую же ценность, как если б передача сигналов закончилась и на выходе канала принималось бы решение по результатам бросания монеты (цифра либо герб). Любопытно также отметить, что Пропускная способность дискретных каналов с шумами если Рош > 0,5, то с повышением Рош пропускная способность канала растет. Этот, на 1-ый взор, феноминальный вывод становится естественным, если принять во внимание, что мы всегда можем поменять правило определения знаков на оборотное, т.е. считать, что решение z1 соответствует передаче знаков у0, а решение z0 – передаче знака у Пропускная способность дискретных каналов с шумами1. Тогда возможность принятия неверного решения станет равной 1 – Рош.

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


pros-and-cons-of-marrying-a-ceo.html
prosba-k-dokladchikam-orgkomitet-konferencii.html
prosba-o-pomoshi-v-sostoyanii-transa.html