Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Уфимский Государственный Нефтяной Технический Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Рахман П.А. - Кодирование информации

.pdf

Скачиваний:

Добавлен:

17.03.2015

Размер:

2.01 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 / 1715 16 17 > Следующая >>>

141

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

отдельно байта составляет: Pbyte 1 1 1/2 8 255/256. Тогда вероятность отсутствия искажений:

lim P(T 0) 1/256n

(6.4.1)

p 1/2

Соответственно, вероятность восстанавливаемого искажения:

lim

P 1 T t

Ch 255/256 h 1/256 (n h)

255h

(6.4.2)

256n

p 1/2

h 1

Соответственно, вероятность невосстанавливаемого искажения:

lim

P T t

255/256 h 1/256 (n h)

255h

(6.4.3)

p 1/2

h t 1 n

256n h t 1

Нетрудно заметить, что вероятность «невосстанавливаемого» искажения P T t при

вероятности искажения бита p 1/2, весьма существенная, больше 255/256 n, даже при

наибольшей кратности исправляемых ошибок t (n 1)/2 для заданной длины кадра n.

Анализ вероятностей особых случаев невосстанавливаемых искажений

Как мы определили, невосстанавливаемое искажение – это такое искажение, при котором искажается более t байтов (T > t), и восстановление исходного кадра – невозможно. Как мы установили ранее, вероятность невосстанавливаемого искажения кадра равна

P(T t)	n	C	h		8	h	8	(n h)
P(T t)		C	n	1 1 p			1 p	. Однако, при декодировании кадров, у
	h t 1		n

которых искажено более t байтов, возможны три особых случая:

Кадр находится на расстоянии более t от всех возможных «допустимых» кадров и однозначное «притягивание» к какому-либо «допустимому» кадру невозможно. В этом случае декодер принимает правильное решение о «неисправимости» кадра.

Кадр оказывается на расстоянии не более t от некоторого «допустимого» кадра U, который, разумеется, не является исходным, и декодер имеет возможность (и реализует это возможность) «притянуть» искаженный кадр к «допустимому» кадру U. Такой случай мы называем «смежным исправлением», а также «частичным обманом декодера» – факт искажения декодер обнаруживает, но исправление приводит к «смежному» кадру U, поскольку он на расстоянии не более t от искаженного кадра.

Кадр полностью совпадает с некоторым «допустимым» кадром U, который, разумеется, не является исходным. Такое возможно только при искажении более 2·t

байтов. В этом случае сам факт искажения остается необнаруженным, и мы это называем случаем «маскирования искажения», а также «полным обманом декодера».

Теперь обозначим вероятности трех случаев «невосстанавливаемых искажений»:

Pн.и.- вероятность «неисправимого искажения».

Pс.и.- вероятность «смежно-исправимого искажения».

Pм.и.- вероятность «маскируемого искажения».

142

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

Pн.и. Pс.и. Pм.и. P(T t)	(6.5.1)
Из этого равенства также следует «верхняя оценка» для вероятности смежно-
исправимого или маскируемого искажения:
Pс.и. Pм.и. P(T t)	(6.5.2)

Иными словами, вероятность смежно-исправимого или маскируемого искажения всегда меньше вероятности невосстанавливаемого искажения.

Кроме того, поскольку маскирование возможно только при искажении более 2·t байтов, то мы также имеем «верхнюю оценку» для вероятности маскируемого искажения:

Pм.и. P(T 2t)

(6.5.3)

Однако, «верхние оценки» – это, конечно, уже кое-что, но хотелось бы также иметь возможность точно вычислять вероятности для всех трех случаев.

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

качестве «третьей неизвестной» мы выберем Pн.и.- вероятность неисправимого искажения.

Тогда остается выяснить только Pс.и.и Pм.и..

Анализ Pс.и.и Pм.и.требует нетривиального комбинаторного анализа в пространстве кадров, поэтому прибегнем к наглядной геометрической картине (рис. 6.3).

Рис. 6.3. Геометрическая картина смежно-исправимого или маскируемого искажения.

Итак, пусть имеется некоторый исходный кадр F. Рассмотрим множество кадров, которые находятся на расстоянии h от исходного кадра, причем t 1 h n, и при этом находятся на расстоянии от некоторого «допустимого» кадра U, причем 0 t . При этом рассматриваемый «допустимый» кадр U находится на расстоянии от исходного кадра, причем 2t 1 n, поскольку ближе, чем на минимальном кодовом расстоянии d 2t 1, «допустимых» кадров не может быть согласно теории кодирования. Смежное исправление возможно только тогда, когда t 1 h n и 1 t , поскольку только в этом случае искаженный кадр Z с одной стороны не совпадает с «допустимым» кадром U, и в то же время находится от него на расстоянии не более t, и декодер сможет «исправить» искаженный кадр, превратив его в «допустимый» кадр U. Что касается маскируемого искажения, то оно происходит только тогда, когда 2t 1 h n и 0, поскольку в этом случае происходит полное совпадение искаженного кадра с «допустимым» кадром U.

143

Примечание. Особо отметим, что в n-мерном пространстве никакой кадр не может находиться на расстоянии более n от другого кадра. Поэтому в случае рассмотрения «допустимых» кадров U, находящихся на «приграничных» в n-мерном пространстве расстояниях n t от исходного кадра F, кадры Z, отстоящие на расстоянии 1 t от «допустимого» кадра U, находятся на расстояниях не более n от исходного кадра F, даже если n. Однако, это вовсе не означает, что «шар» радиуса t c центром в кадре U, находящемся на расстоянии n t от исходного кадра F, содержит меньшее количество кадров, чем другой «шар» радиуса t c центром в кадре U, находящемся на расстоянииn t от исходного кадра F. Просто «шары» радиуса t с центрами, находящимися на «приграничных» расстояниях n t от исходного кадра F, по форме это уже не совсем «шары», а более сложные n-мерные геометрические объекты. Тем не менее, такие объекты

t
содержат точно такое же количество	Cn	255 кадров, как и любой другой «шар»
0

радиуса t c центром в кадре U, находящемся на расстоянии n t от исходного кадра F.

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

расстоянии h	от исходного кадра, причем t 1 h n, и при этом находящихся на
расстоянии	от некоторого «допустимого» кадра U, причем 0 t . Рассмотрим частный

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

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

Рассмотрим теперь, какими способами можно «отклоняться» от «допустимого» кадра

U. Во-первых, среди n нулевых байтов можно выбрать q байтов (Cnq способами),

причем 0 q n , и заменить каждое из них на одно из 255 ненулевых значений. Во-

вторых, среди ненулевых байтов можно выбрать i байтов (Ci способами), причем

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

j байтов (C j	способами), причем 0 j i, и заменить их нулевым значением.
i

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


ровно h от исходного кадра F, то есть содержать h		ненулевых байтов и	n h	нулевых
байтов. В качестве вариантов «отклонений», мы q		нулевых байтов среди	n	байтов
заменяем ненулевыми значениями, затем	i ненулевых байтов среди байтов заменяем
другим ненулевым значением, наконец,	среди оставшихся i ненулевых j			байтов

заменяем нулями (при этом i j байтов остаются ненулевыми) – в итоге общее число

ненулевых байтов равно q i ( i j) q j,	и, очевидно, только при условии
q j h, «отклоненный» кадр будет находиться на	расстоянии h от исходного кадра F.

144

Ниже приведен простой наглядный пример «отклонения» некоторого «допустимого» кадра U в некоторый кадр Z при заданном исходном кадре F:

								θ

	n				n		n θ	i θ i
		;
F	0 0	;	U		0 0A A	Z	0 0A AB BA A0 0 ;

							q	j
				n θ θ			q	j

D(F,U)

D(U,Z) q i j

D(F,Z) q j

Тогда в итоге чтобы подсчитать общее количество (обозначим его Nh )

искаженных кадров, находящихся на расстоянии h от исходного кадра, и при этом находящихся на расстоянии от некоторого «допустимого» кадра U, находящегося на расстоянии от исходного кадра F, необходимо просуммировать все рассмотренные варианты «отклонений» от «допустимого» кадра при соблюдении двух рассмотренных условий. В итоге получаем следующую тройную сумму с двумя условиями для индексов:

	n		q
Nh	n		q
Nh		Cn
	q 0

255

254

(6.6.1)

i 0

j 0

i j q

q j h

В формуле ключевую роль играют именно

два

условия, которые связывают

«внутренние» индексы

q,i, j

с «внешними» параметрами , ,h . Нетрудно заметить,

что

, вторая сумма при

если убрать эти два условия, то внутренняя сумма:

j 0

Ci 254i 2 i 256 , а третья сумма:

255

этом станет:

256n

i 0

q 0

В итоге получим, что

256n. То есть, само по себе суммирование производится по

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

Заметим также, что если 0, то в силу условия i j q все индексы

суммирования q,i, j смогут принимать только значение 0. Тогда, очевидно, Nh ( 0) 1.

Это вполне логично – существует только один кадр, находящийся на расстоянии 0 от некоторого «допустимого» кадра U, находящегося на расстоянии от исходного кадра F, это сам кадр U. Кроме того, так как из 0 следует i j q 0, то второе условие, очевидно, становится h, что тоже логично, ведь рассматриваемый кадр совпадает с кадром кадр U, и он находится на том же самом расстоянии от исходного кадра F.

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

от суммирования по индексу q. Выразим							q из второго условия и получим:			q h j .
Кроме того, подставляя q h j					в первое условие, получим преобразованное условие:
i 2j h . Тогда получим следующую формулу для расчета Nh :
N				Ci 254i		i	C j	Ch j		(6.6.2)
	h								255h j
		i	0				i	n
					j 0

i 2 j h

145

Таким образом, мы выяснили количество искаженных кадров, находящихся на расстоянии h от исходного кадра F, и при этом также находящихся на расстоянии от некоторого «допустимого» кадра U, находящегося на расстоянии от исходного кадра F.

Теперь же оценим вероятность появления конкретной конфигурации искажения. Как было установлено ранее, вероятность того, что исказится ровно h байтов при заданной вероятности искажения бита, равной p, и размерности пространства кадров n, равна:

C	h		8	h	8	(n h)
C	n	1 1 p			1 p	. Тогда, вероятность того, что исказится конкретный
	n

набор из h байтов, причем в каждом из искаженных байтов будет реализован один из 255

	8	h	8	(n h)
	1 1 p
вариантов искажения, будет равна			1 p	. Для того, чтобы формула
	255

была менее громоздкой, используем ранее полученную формулу вероятности искажения отдельного байта при заданной вероятности искажения отдельного бита Pbyte 1 1 p 8.

	P	h			(n h)
	byte
Тогда окончательно получаем:			1 P		.
	255
				byte

Тогда, мы, используя Nh , можем оценить вероятность того, что искаженный кадр

будет находиться на расстоянии	(причем 0 t ) от некоторого «допустимого» кадра
U, находящегося на расстоянии	(причем 2t 1 n) от исходного кадра F. Для этого

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

по всем h, причем t 1 h n. Обозначим интересующую нас вероятность V и получим:

	n		P	h			(n
	n		byte				(n
V					1 P
V			255		1 P
	h t		255			byte
	h t	1

h)
h)		(6.7.1)
N	h	(6.7.1)
	h

Заметим, что в формуле для расчета вероятности V используется одинарное

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

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

(n h)

h j

byte

h j

254

255

h t 1

byte

i 0

j 0

i 2 j h

h j

Pbyte

(n h)

254

h t

i 0

j 0

byte

255

2 j h

146

Воспользуемся

условием

i 2j h ,

из

которого

можно выразить

h i 2j, и тогда избавимся от внешнего суммирования по индексу h:

i 2 j

i j

Pbyte

(n ( i 2 j))

254

i 0

byte

j 0

255

Заметим, что биномиальный коэффициент C i j

равен нулю,

если i j 0.

Отсюда можно получить дополнительное ограничение на сумму индексов i j . Тогда, поскольку сами по себе индексы i и j могут принимать только неотрицательные значения i 0 и j 0, то, очевидно, что каждый из них в отдельности также не может быть больше ,

иными словами,	0 i	и 0 j	.	А учитывая, что i j , можем переписать пределы
для индексов i	и j :	0 i	и	0 j i. Отметим также, что даже в случае

сознательного нарушения условия 2t 1 n, при котором	может оказаться меньше ,
так же как и i может оказаться меньше i, для всех i	биномиальный коэффициент
Ci будет равен нулю, также как и для всех j i биномиальный коэффициент C j
	i

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

Тогда с учетом вышеприведенных рассуждений получаем:

i 2 j

i j

Pbyte

(n ( i 2 j))

254

1 P

i 0

byte

j 0

255

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

j выразим

как j i. Пределы для нового индекса , учитывая,

что i j , i 0,

j 0, очевидно,

будут следующими:

0 . Пределы для индекса i

останутся прежними: 0 i . Тогда,

заметив также, что i 2j i 2 , получаем следующее выражение:

i 2

(n ( i

Pbyte

2 ))

254

i 0

byte

255

Теперь мы можем переставить порядок суммирования, поскольку пределы

внутреннего суммирования не содержат индекса i

внешнего суммирования:

i 2

(n ( i

Pbyte

2 ))

254

byte

i 0

255

Теперь заметим,

что биномиальный коэффициент C

равен нулю, если i ,

тогда, очевидно,

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

произведение Ci

( i)!

Ci C .

i!( i)!

( i)!( )!

( i)!( )! !

147

Тогда получаем следующее выражение:

i 2

(n ( i 2 ))

Pbyte

1 Pbyte

254i

255 i

i 0

Теперь вынесем все независящие от индекса i составляющие из внутренней суммы:

(n ( 2 ))

1 P

254i

byte

255

255i

i 0

byte

Нетрудно заметить,

что теперь внутренняя сумма представляет собой разложение в

255 P

/255

254

1 P

степенной ряд функции: 1

byte

1 P

255

255 1

byte

Тогда окончательно получаем формулу для расчета вероятности того, что искаженный кадр будет находиться на расстоянии , 0 t , от некоторого «допустимого» кадра U, находящегося на расстоянии , 2t 1 n, от исходного кадра F:

V C

	2			(n ( ))		P
	P	1 P				P
	byte		byte			byte	(6.7.2)
C					1
C					1
n						255
			255

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

Примечание. Отметим, что при значениях n t, появляется возможность того, что

может оказаться больше n , и биномиальный коэффициент Cn в этих случаях равен нулю, и поэтому можно «оптимизировать» нижний предел для индекса : начинать суммирование не с 0, а с величины max 0, (n ) . К тому же такая «оптимизация» обеспечит то, что степень n ( ) (n ) ( ) будет всегда неотрицательной, и избавит нас от проблем в случае, если вероятность искажения бита будет задана равной p 1, при которой 1 Pbyte 0, и возведение нуля в отрицательную степень равносильно

делению на нуль. Аналогично, если сознательно будет задана с нарушением условия 2t 1 n, тогда также возможна ситуация, когда может оказаться больше , и

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

«оптимизировать» для таких случаев верхний предел для индекса : заканчивать суммирование не на , а на min , . К тому же такая «оптимизация» обеспечит то, что степень 2 ( ) ( ) будет также всегда неотрицательной, и избавит нас от проблем, в случае если вероятность искажения бита будет задана равной p 0, при которой

Pbyte 0, и возведение нуля в отрицательную степень равносильно делению на нуль. Мы не

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

148

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

Во-первых, рассмотрим случай 0. В этом случае, суммирование в формуле превращается единственное слагаемое при 0, и, соответственно, получаем:

(n )

lim

1 P

(6.7.3)

255

byte

Во-вторых, рассмотрим случай

В этом случае, поскольку биномиальный

коэффициент C

не равен нулю, только при 0, то получаем:

(n )

lim V

(6.7.4)

1 P

byte

Таким образом,

мы, наконец, получили формулу для расчета вероятности V того,

что искаженный

кадр

окажется на заданном

расстоянии ,

0 t , от

некоторого

«допустимого» кадра U, находящегося на расстоянии ,

2t 1

n, от исходного кадра F.

Здесь особо отметим, что вероятность V

зависит от

расстояний

и , но не

зависит от «направлений». Иными словами, вероятность не зависит от того, в каком конкретном направлении находится «допустимый» кадр U относительно исходного кадра F. Кроме того, в формуле V уже учтены и просуммированы всевозможные «направления»

искаженного кадра Z относительно «допустимого» кадра U. То есть V – это вероятность появления любого из множества кадров, находящихся на «поверхности сферы» радиуса с

центром в некотором «допустимом» кадре U. Наконец, особо подчеркнем, что формула V

учитывает кадры Z только вокруг одного и только одного некоторого «допустимого» кадра U, никакого суммирования по «допустимым» кадрам в формуле нет.

Поэтому, чтобы получить вероятность смежно-исправимого искажения, нам потребуется суммирование по всем расстояниям 1 t (только в этом случае искаженный кадр находится на расстоянии не более t от некоторого «допустимого» кадра и при этом не совпадает с ним), суммирование по всем «допустимым» кадрам, находящимся на расстоянииот исходного кадра, и, наконец, суммирование по всем расстояниям 2t 1 n .

Аналогично, чтобы получить вероятность маскируемого искажения, нам нужно положить 0 (только в этом случае искаженный кадр совпадает с «допустимым» кадром), затем выполнить суммирование по всем «допустимым» кадрам, находящимся на расстоянииот исходного кадра, и, наконец, суммирование по всем расстояниям 2t 1 n .

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

зависит от конкретного «направления», на котором находится тот или иной «допустимый» кадр, то, очевидно, что суммирование сведется к простому умножению на количество A

«допустимых» кадров, находящихся на заданном расстоянии от исходного кадра F.

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

определяется формулой

			A0 1;	A1 A2t 0
C	2t 1				(256 2t i 1)		2t 1 n .
			( 1)i Ci			;
n		i 0

149

Теперь, наконец, у нас имеются все «составляющие части» для вывода формул вероятности смежно-исправимого и вероятности маскируемого искажения.

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

P	n	A		t		(6.8.1)
P		A		V		(6.8.1)
с.и.	2t 1				θ
	2t 1		1

Соответственно, окончательная формула вероятности маскируемого искажения: n

	P				A	lim	V		(6.8.2)
	м.и.		2t 1			0	θ
			1					(n )
Учитывая, что lim	V			P	1 P				, формулу для вычисления
Учитывая, что lim	V	255		P	1 P				, формулу для вычисления
0		255		byte		byte

вероятности маскируемого искажения можно также записать в следующем виде:

(n )

(6.8.2*)

P /255

1 P

м.и.

2t 1

byte

Нетрудно заметить, что P

с.и.

м.и.

Кроме того ранее мы установили,

Pн.и. Pс.и. Pм.и. P(T t), причем

P(T t)

(n h)

. Тогда,

учитывая,

что

P(T t) (P

)

1 P

h t

byte

н.и.

с.и.

м.и.

мы можем записать окончательную формулу для вероятности неисправимого искажения:

(n )

(6.8.3)

1 P

н.и.

byte

2t 1

По сути, эта формула означает следующее: вероятность неисправимого искажения – это вероятность того, что кадр окажется за пределами расстояний 0 t как от исходного кадра F, так и от любого другого «допустимого» кадра U, находящегося на любом из расстояний 2t 1 n от исходного кадра F.

Учитывая, что lim	V	C		P			(n )
			n		1 P		, мы можем полученную
0				byte		byte

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

lim

(6.8.3*)

н.и.

2t 1

Частный случай. Рассмотрим важные частные случаи вероятностей смежного исправления, маскирования искажения и неисправимого искажения, когда вероятность искажения отдельного бита равна p 1/2. То есть любой бит может с шансами «50 на 50» либо исказиться, либо нет. Такая картина может наблюдаться в сильно зашумленных каналах передачи данных, а также на носителях информации, подвергшихся сильному разрушающему воздействию, например, взрыву большой мощности.

	150
Очевидно, что при p 1/2, P	1 1 p 8	255/256. Подставляя это значение
byte

Pbyte 255/256 в формулу для расчета V , получаем следующее выражение:

(n ( ))

255/256

1 255/256

255

1/256 (n ))

255

256

256n

Воспользуемся свойством биномиальных коэффициентов

Свойство нетрудно доказать с помощью «производящих функций». С одной стороны

(1 x)n

x . С другой стороны, раскладывая (1 x)n на два сомножителя, имеем

(1 x) (1 x)n


Обозначая	и выражая , получим		n

		0

C Cn x .

Заметим, что поскольку при 0 и n n коэффициент Cn обращается в нуль, то мы можем, без опасений расширить пределы суммирования по до 0 n, и

		n
получить:

0
	0

C Cn x . Теперь переставим порядок суммирования

n		C	C		и заметим, что C	равен нулю при , так что
		C	C	x	и заметим, что C	равен нулю при , так что
0	0		n		n
0	0

		n
верхний предел суммирования по	можно снизить до :

		0	0

C Cn x .

Сравнивая выражение при x в полученной сумме с аналогичным коэффициентом в сумме

, нетрудно убедиться, что

Тогда в итоге получаем формулу для вероятности V

для частного случая, когда

вероятность искажения отдельного бита равна

p 1/2:

lim

255

. Заметим,

256n

p 1/2

что «асимптотическая» вероятность

lim

V вообще не зависит от расстояния . Также

p 1/2

легко заметить, что при 0: lim

lim

255

256

0 p 1/2

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 / 1715 16 17 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
17.08.201975.78 Кб3Расчетно.doc
#
17.03.201578.79 Кб103Расчетные задания интегралы.docx
#
17.03.2015525.82 Кб13Расчетные задания.doc
#
17.03.2015101.51 Кб25Расчеты.docx
#
06.03.201637.42 Mб26Рахимгулов.rtf
#
17.03.20152.01 Mб50Рахман П.А. - Кодирование информации.pdf
#
27.08.2019197.12 Кб3РГ_лекции .doc
#
21.12.2018378.37 Кб3ргз по механике( вариант со ВСЕМИ перепеч....doc
#
17.03.2015355.33 Кб558РГП-05 Мет_курс_раб.doc
#
29.08.20191.03 Mб8РГР 1 (2семестр).doc
#
17.03.2015775.17 Кб240РГР 1_1 Поз задачи.doc