ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 55
Скачиваний: 0
Пусть на выходе кодера I появляются двоичные кодо вые слова одинаковой длины (х, соответствующие пере даваемым сообщениям. Чтобы декодер I имел возмож ность'обнаруживать и исправлять ошибки, 2-е кодиру ющее устройство по некоторому правилу добавляет |хЛ корректирующих двоичных символов к каждому кодово му слову, поступающему на его вход. В результате полу чаются кодовые слова длиной символов, которые затем .передаются по линии связи с шумами, где некото рые символы искажаются (символ «1» подменяется сим волом «О», а символ «О»— символом «1»).
При этом число различных передаваемых кодовых слов меньше числа всех возможных кодовых слов, полу чаемых на выходе линии связи, т. е.
|
N = «Г < Л'0= |
, |
|
(4.1) |
где т — число различных кодовых символов. |
называют |
|||
N различных передаваемых |
кодовых |
слов |
||
р а з р е ш е н н ы м и , а No— N |
кодовых |
слов |
з а п р е |
|
ще н н ыми . |
Если в результате ошибок переданное (раз |
|||
решенное) |
кодовое слово перейдет в одно из запрещен |
|||
ных, ошибка будет о б и а р у ж е и а декодером |
I при ус |
|||
ловии, что в его запоминающем устройстве хранятся все разрешенные кодовые слова. Если же в результате оши бок переданная комбинация превращается в одну из раз решенных, ошибка декодером I не обнаруживается.
Таким образом, корректирующий код, удовлетворя ющий условию (4.1), способен в N(N0— N) случаях обна руживать ошибки из общего числа NqN. Однако если іѴ < < іѴ0, разрешенные комбинации могут быть выбраны с учетом вероятностных свойств шума так, чтобы вероят ность получения ошибочной разрешенной комбинации была очень мала. Другими словами, при Лгс<С-Ѵ0 в ре зультате ошибочного приема отдельных символов приня тое кодовое слово, как правило, окажется запрещенным, что и укажет на ошибку.
Для принятия однозначного решения о том, какое ко довое слово было отправлено, в общем случае все мно жество принимаемых кодовых слов No разбивается по не которому правилу на N подмножеств. Каждое подмноже ство отождествляется с одним из разрешенных кодовых слов. Если, например, принятое кодовое слово попало в і-е подмножество, считается, что было передано і-е кодо-
88
вое слово. Задача состоит в том, чтобы выяснить, сущест вуют ли такие правила введения корректирующих симво лов в передаваемые кодовые "слова и разбиения на под множества всех возможных принимаемых кодовых слов, при которых вероятность ошибочного приема будет как угодно мала, а скорость передачи как угодно близка к пропускной способности линии связи.
Эта задача в общем виде разрешается теоремами Шеннона, которые мы докажем в § 3 настоящей главы.
§ 2. Пропускная способность дискретного канала связи с шумами
Соотношения (3.1) — (3.3), определяющие скорость пе редачи и пропускную способность канала и линии связи, были получены нами в общем случае. Поэтому они при менимы как для дискретных, так и для непрерывных ка налов, как для каналов без шумов, так и для каналов с шумами. Разница заключается в способе вычисления ко
личества информации. |
|
|
|
|
Задача 1. По линии связи с шумами передаются два |
||
различных сигнала у0 и у\ |
с вероятностями |
соответст |
|
венно Ро и Р 1. На приемной стороне сигнал уо обозначим |
|||
Z0, |
а у 1 через Z\. Заданы вероятности ошибочного прие |
||
ма: |
P(Zo/y\) = Pl; P(Z\/yo) = |
P n. Длительности сигналов- |
|
Уо и у\ одинаковы и равны |
~0. Определить |
пропускную |
|
способность такой линии связи с шумами. |
|
||||
Р е ш е и и е. |
Пропускную способность заданной линии |
||||
связи будем определять по формуле (3.3): |
|
||||
- |
С m ax |
Шах / (Z, |
К") , |
|
|
где |
|
H ( Z r ) - H ( Z T I YT ) |
|
||
/(Z, |
Y) = |
(4.3) |
|||
lim |
Т |
||||
|
|
'P -*■ со |
|
||
Так как длительности сигналов одинаковы, то Т — М^г
где М — число |
сигналов в последовательности |
длитель |
|
ностью Т. Если H(Z)— энтропия, приходящаяся |
на один |
||
сигнал Zt (і = |
0,1), то энтропия, приходящаяся на М та |
||
ких сигналов, |
H (Z r) = M H ( Z ) . |
(4.4) |
|
Аналогично |
|||
N ( Z T/ Y T) = M H { Z / Y ) . |
(4.5) |
||
|
|||
I
Подставляя (4.4) и (4.5) в (4.3), получаем
/(Z , У) = lim
М-СО
MH{Z) — МН(Zf У) |
= 4 [H(Z)-H(Z;Y)\. |
М т |
|
По формуле (4.2) пропускная способность
Сс = 4 п1ах[H(Z) - H(Z/Y)].
Разность H(Z) — Ii(Z/Y) максимальна, когда максималь на энтропия H(Z) и минимальна энтропия H(Z/Y). Но ус ловная энтропия H(Z/Y) зависит только от статистики пе редаваемых сигналов (Po и Р\) и статистики шумов, дей ствующих в линии связи (Р{ и Р п ), которые по условию задачи заданы. Поэтому разность H(Z) — H(Z/Y) макси мальна, когда максимально первое слагаемое; энтропия H(Z) максимальна, когда P(ZQ) = P(Z)i и равна Ii(Z) = 1.
Таким образом,
Cc = 4 [ l - t f ( Z / y ) ] . |
(4.6) |
Вычислим энтропию H(Z/Y) по формуле
H{ZY) = - 2 2 р & ь У]) l°g Р ^ ' У ) ) -
/=0 ;=О
По формуле полной вероятности и теореме умножения
P(Zo) = 2 |
P(Zо, yj) = |
P(Z0, у0) + P(Z0, у,) = |
||
|
;=о |
|
|
|
|
= Р(Уо) P ( Z o ly 0) + Р ( У і ) - Р Р М = |
|||
= Р(Уо)[1 - |
P(Zt/y0)] + Р Ш Р & в!уі) = |
Яо(1 - Р и) + Р ^ г |
||
|
|
|
|
I |
P ( Z i ) |
= 2 |
P ( z 1. yj) = P ( Z u У0) + P { Z X. Уі) = |
||
|
j=o |
|
|
|
= |
P(yо) P(Zb Уо) + |
P(y,)[l - |
P(Zo!yi)] = |
|
|
|
= P0P 1I + |
P1( 1 - P 1). |
|
Подставляя полученные выражения в условную энтро пию, будем иметь:
H(Z y) = —P{Z0, уо) log P(Z0!y0) — P(Zt, |
ijo) log PfZt/y0) — |
— P(Z0, yi) log P(Z0 'yi) — P{Zl, i/i) log PtZi/y,) = . |
|
= — P(Z0, г/o) log [1 — P (Zj/Уо)] - P(Z„ |
y0) log P(Zi/y0) — |
•90
- P(Z0, ІЯ) log P(Z0/Уі) - P(Zlt y t) log [ 1 - P(Z0'yl)] =
« - |
PoV - Prf log (1 - P n) - P0P n log P ,, = |
|
|
= — P \P Xlog p |
P i (1 — Pj) log (1 — P,). |
(4.7) |
|
Наконец, подставим выражение (4.7) в (4.6): |
|
||
сс= 4 т і |
+ р0о - |
P i^ o g o - P iij + PoPniogp,, + |
|
+ P,Pi log Р , - р . (1 - р . ) log ( і - р , ) ] . |
(4.8) |
||
Задача 2. В условиях предыдущей задачи определить пропускную способность симметричной линии связи, в ко торой Р { = Л , = Яоиі=І/2. Объяснить полученный резуль
тат.
Р е ш е н и е . Подставим в формулу (4.8) предыдущей задачи Р{ = Рі{ = Л>ш:
= 4 [1 + (1 — Рош)lo g (1 — Рош) + РошlogP 0,„]. (4.9)
Из (4.9) видно, что с ростом Рош от 0 до 0,5 пропускная способность Сс монотонно убывает от своего максималь
ного значения, равного до 0. Результат Сс= 0 при
Pqui -0,5 станет очевидным, если заметить, что равенства
^ош ^ |
Р(^оіУі) = Р(^о;Уо) = 0*5; |
|
Рош” |
Р{%і!Уо) = Р(^і!Уі) —0)5 |
(4.10) |
1 |
|
сигналы |
показывают, что передаваемые и принимаемые |
||
полностью статистически независимы (см. задачу 2 § 3 гл. 1). При этом, как нам известно, количество получае мой информации равно нулю. Иначе говоря, приняв, к примеру, сигнал Z\ (см. 3.46), мы с равной вероятностью можем утверждать, что был передан сигнал у\ либо сиг нал і/0. Эти утверждения имеют такую же ценность, как если бы передача сигналов вовсе прекращалась и мы принимали решение о передаче того или иного сигнала по результатам бросания монеты.
Задача 3. В памяти ЭВМ накоплено 10е двоичных еди ниц информации. Для ее передачи используют двоичную симметричную линиюсвязи. Техническая скорость пере дачи в линии связи V =500000 бит/с, а вероятность ошиб ки Рош= 0,0035. -Найти минимальное время передачи на копленной в ЭВМ информации.
9
91